KNN算法簡(jiǎn)介

首先介紹一下KNN算法的幾個(gè)特點(diǎn)：

• KNN，全稱K-Nearest Neighbor，中文名為K近鄰
• 思想極度簡(jiǎn)單，最基礎(chǔ)的分類算法，非常適合入門
• 應(yīng)用數(shù)學(xué)知識(shí)極少，近乎為零
• 效果卻很好
• 可以解釋機(jī)器學(xué)習(xí)算法使用過(guò)程中的很多細(xì)節(jié)問(wèn)題，更完整的刻畫機(jī)器學(xué)習(xí)應(yīng)用的流程

KNN算法原理

下面我們開(kāi)始用一個(gè)簡(jiǎn)單的例子來(lái)解釋KNN的原理：

假設(shè)已有了一組關(guān)于腫瘤的樣本數(shù)據(jù)，其中X軸為腫瘤大小，Y軸為發(fā)現(xiàn)腫瘤的時(shí)間，紅色的點(diǎn)為良性腫瘤，藍(lán)色的點(diǎn)為惡性腫瘤

假設(shè)現(xiàn)在新出現(xiàn)了一個(gè)已知大小和發(fā)現(xiàn)時(shí)間的腫瘤，如何判斷該腫瘤屬于良性還是惡性呢？

首先需要取一個(gè)k值，k值代表了新來(lái)的腫瘤需要比對(duì)k個(gè)樣本數(shù)據(jù)，具體K值怎么取后續(xù)會(huì)有詳細(xì)的介紹

這里先假設(shè)k=3，意味著新來(lái)的腫瘤需要去比對(duì)離新腫瘤最近的3個(gè)樣本數(shù)據(jù)的距離

而后，這3個(gè)樣本數(shù)據(jù)以它們自身的類別進(jìn)行投票，比如上圖中，這3個(gè)點(diǎn)的投票結(jié)果為藍(lán)色：紅色 = 3：0（概率為100%）。所以新來(lái)的腫瘤將被KNN算法判定為藍(lán)色，也就是惡性腫瘤。

綜上所述，KNN算法的性質(zhì)就是，在已知數(shù)據(jù)樣本的特征與分類的情況下，新的數(shù)據(jù)將會(huì)比對(duì)距離已知樣本最近的k個(gè)數(shù)據(jù)，而后根據(jù)這k個(gè)數(shù)據(jù)各自分類數(shù)量的比例，即每個(gè)分類會(huì)計(jì)算出各自的概率，將新數(shù)據(jù)將判定給概率最大的那個(gè)類別。

關(guān)于k值與樣本數(shù)據(jù)的距離

計(jì)算ab兩點(diǎn)之間的距離的方式有幾種，這里我們通常會(huì)采用歐拉距離，下圖是歐拉距離在平面幾何中的計(jì)算方式

在立體幾何中，歐拉距離變得有些抽象了，由于多了第三個(gè)z軸，所以需要在加上z軸方向的值

在真實(shí)機(jī)器學(xué)習(xí)中，脫離了幾何的概念會(huì)變得有些抽象，且樣本的特征可能會(huì)更多，所以我們需要統(tǒng)計(jì)每個(gè)特征的距離，其中大X表示樣本集，X右下角的數(shù)字角標(biāo)表示是第幾個(gè)特征值

簡(jiǎn)潔的表示為

算法實(shí)現(xiàn)

import numpy as np
import matplotlib.pyplot as plt

# 定義一組腫瘤的樣本的特征
raw_data_X = [[3.39, 2.33],
              [3.11, 1.78],
              [1.34, 3.36],
              [3.58, 4.67],
              [2.28, 2.86],
              [7.42, 4.69],
              [5.75, 3.53],
              [9.17, 2.51],
              [7.79, 3.42],
              [7.93, 0.79]]

# 對(duì)應(yīng)樣本已知的類別，0為良性，1為惡性
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

# 用numpy封裝為訓(xùn)練集
X_train = np.array(raw_data_X)
y_train = np.array(raw_data_y)

# 繪制已知腫瘤分類為0和1的散點(diǎn)圖
plt.scatter(X_train[y_train == 0, 0],
            X_train[y_train == 0, 1], color='g')  # 綠色為良性
plt.scatter(X_train[y_train == 1, 0],
            X_train[y_train == 1, 1], color='r')  # 紅色為惡性

# 現(xiàn)在新來(lái)的腫瘤
x_new = np.array([8.09, 3.34])

plt.scatter(X_train[y_train == 0, 0],
            X_train[y_train == 0, 1], color='g')  # 綠色為良性
plt.scatter(X_train[y_train == 1, 0],
            X_train[y_train == 1, 1], color='r')  # 紅色為惡性

# 單獨(dú)繪制一下新腫瘤
plt.scatter(x_new[0], x_new[1], color='b')  # 藍(lán)色為新腫瘤

# 手寫一遍kNN算法過(guò)程
from collections import Counter
from math import sqrt

# 定義一個(gè)空的數(shù)組，用于保存新數(shù)據(jù)與已知樣本數(shù)據(jù)的歐氏距離
distances = []

# 這里可以回顧一下歐氏距離的數(shù)學(xué)公式
for x_train in X_train:
    d = sqrt(np.sum((x_train - x_new)**2))
    distances.append(d)

# 此時(shí)的distances中就已經(jīng)包含了新腫瘤與每一個(gè)樣本的距離，打印一下看看
distances

# 可以用更簡(jiǎn)介生成表達(dá)式的語(yǔ)法計(jì)算
distances = [sqrt(np.sum((x_train-x_new)**2)) for x_train in X_train]

# 再打印一下看看，一樣的吧
distances

# 對(duì)距離排序看看
np.sort(distances)

# 但是現(xiàn)在我們需要的是：distance數(shù)組在排序后所對(duì)應(yīng)排序前的index
np.argsort(distances)

# 我們將這個(gè)索引值保存為nearest變量
nearest = np.argsort(distances)

# 現(xiàn)在拍腦袋定義一個(gè)k值6，which means我們將比對(duì)距離新數(shù)據(jù)最近的6個(gè)樣本，讓這6個(gè)樣本vote
k = 6

# 遍歷nearest對(duì)象，將正確排序的索引引用到已知分類的結(jié)果集y，得到距離最近的6個(gè)y的結(jié)果
topk_y = [y_train[i] for i in nearest[:k]]

# 打印一下6個(gè)樣本的投票結(jié)果，可以看到是分類1 VS 分類0是5：1
topk_y

# 調(diào)用一個(gè)計(jì)數(shù)函數(shù)，返回一個(gè)kv對(duì)象，會(huì)自動(dòng)根據(jù)value將key從大到小排序，打印一下可以看到分類1有5票，分類0有1票
votes = Counter(topk_y)
votes

# 由于剛才的結(jié)果是個(gè)對(duì)象，我們用most_common函數(shù)轉(zhuǎn)換成tuple
votes.most_common()

# 由于我們只關(guān)心計(jì)數(shù)最多的那個(gè)key值（即分類結(jié)果），所以我們只需要取第一個(gè)tuple的key值
predict_y = votes.most_common(1)[0][0]

# 打印一下，新數(shù)據(jù)屬于分類1，也就是惡性腫瘤
predict_y

scikit-learn中的KNN算法

from sklearn.neighbors import KNeighborsClassifier

KNN_classifier = KNeighborsClassifier(n_neighbors=6)
KNN_classifier.fit(X_train, y_train)

# 直接predict會(huì)報(bào)一個(gè)錯(cuò)，原因是x_new是一個(gè)一維向量，而X_train是一個(gè)二維矩陣，我們需要將x_new也reshape成一個(gè)一行的二維矩陣
y_predict = KNN_classifier.predict(x_new) 

y_predict = KNN_classifier.predict(x_new.reshape(1, -1))

# 再打印一下，problem solved
y_predict

# 強(qiáng)迫癥同學(xué)還是取一下具體的值吧，就是1了
y_predict[0]

/** 上述的predict會(huì)直接給出具體的分類值，但是我們也可以調(diào)用predict_proba看一下是0還是1的概率，可以看到0的概率是0.1666，1的概率是0.8333，也就是1：5啦**/
KNN_classifier.predict_proba(x_new.reshape(1, -1))[0]

小結(jié)

• KNN似乎不用建模？
• KNN算法是非常特殊的，可以認(rèn)為是沒(méi)有模型的算法
• 但是為了和其他算法統(tǒng)一，可以換個(gè)角度理解，認(rèn)為訓(xùn)練的樣本集就是模型本身

TBC……