K近鄰算法：以"同類相吸"解決分類問題！
前言
KNN（k-nearest neighbors）又叫做K近鄰，是機(jī)器學(xué)習(xí)中相對簡單好理解的算法，并且它是個(gè)幾乎不需要訓(xùn)練就可以得到預(yù)測結(jié)果的模型。
我們常說物以類聚，人以群分，大家之所以能夠成為朋友，多少是因?yàn)樯砩系哪承┨刭|(zhì)是相近的，K近鄰算法借助的就是這個(gè)思想。它使用某種方法找到樣本空間中距離測試點(diǎn)最近的K個(gè)點(diǎn)，以投票表決的方式?jīng)Q定該測試點(diǎn)的標(biāo)簽。
本文將結(jié)合阿里云提供的機(jī)器學(xué)習(xí)算法(三): K近鄰(k-nearest neighbors)初探與清華大學(xué)李航老師的PPT，來具體解釋這其中的理論基礎(chǔ)和代碼實(shí)例。
1. KNN理論基礎(chǔ)
1.1 背景介紹
大家通過視頻軟件挑選電影的時(shí)候，通常會(huì)先按照電影的類別進(jìn)行挑選，例如動(dòng)作片、愛情片、歌舞片。這些電影有各自的特點(diǎn)，像是動(dòng)作片的打斗場景一定比愛情片多，它也不會(huì)像歌舞片一樣一言不合就開始跳舞，但又不能完全排除有出現(xiàn)的可能。
總結(jié)這三類型的影片所具有的顯著特點(diǎn)：打斗、親吻、跳舞。假設(shè)現(xiàn)在用一個(gè)元組(a, b, c)來表示，值在0～1之間，Movie = (0.8, 0.1, 0.1)時(shí)，就認(rèn)為這個(gè)電影是動(dòng)作片。那么很自然的，提出了使用一個(gè)三維空間作為該數(shù)據(jù)集的樣本空間，每一部電影在空間中都有屬于自己的點(diǎn)。
假定現(xiàn)在把一堆電影在這個(gè)空間中表示出來，大概率會(huì)發(fā)現(xiàn)它們具有一定的聚集性，動(dòng)作片中點(diǎn)與點(diǎn)的距離會(huì)比動(dòng)作片和愛情片中點(diǎn)與點(diǎn)的距離更短。如果不能理解，也可以拿二維的做類比。
根據(jù)這個(gè)特點(diǎn)，提出了K近鄰算法。對于給定的一個(gè)測試電影，將它在空間中標(biāo)注出來，使用曼哈頓距離或者歐式距離等，選出K個(gè)距離該測試點(diǎn)最近的點(diǎn)，而我們已經(jīng)事先知道了這些被選出來的最近點(diǎn)的電影類型，接著對其進(jìn)行類型統(tǒng)計(jì)投票，選擇票數(shù)最多的那個(gè)作為該測試電影的類型。
比如當(dāng)K=5時(shí)，用a、b、c分別表示三類型電影的票數(shù)，如果a = 4, b = 1, c = 0，我們就認(rèn)為這部電影是動(dòng)作片。
從這個(gè)過程你可以看出，它只需要一個(gè)多維空間、帶標(biāo)簽的訓(xùn)練集，因此它也是個(gè)有監(jiān)督學(xué)習(xí)。
1.2 工作原理與特點(diǎn)
K近鄰算法的工作原理如下：
首先，存在一個(gè)樣本數(shù)據(jù)集合，也稱作訓(xùn)練樣本集，并且樣本集中每個(gè)數(shù)據(jù)都存在標(biāo)簽，即我們知道樣本集中每個(gè)數(shù)據(jù)與所屬分類的對應(yīng)關(guān)系。
其次，輸入沒有標(biāo)簽的新數(shù)據(jù)后，將新數(shù)據(jù)的每個(gè)特征與樣本集中數(shù)據(jù)對應(yīng)的特征進(jìn)行比較，然后算法提取樣本集中特征最相似數(shù)據(jù)（最近鄰）的分類標(biāo)簽。一般來說，只選擇樣本數(shù)據(jù)集中前N個(gè)最相似的數(shù)據(jù)。K一般不大于20。
最后，選擇k個(gè)中出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。
借個(gè)《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》中的例子，下圖是每部電影的打斗鏡頭數(shù)、接吻鏡頭數(shù)以及電影評估類型，其中有一部未知電影的接吻鏡頭有90次，打斗18次，電影類型是未知的。
那么接下來通過計(jì)算未知電影與樣本集合中其他電影的距離：
現(xiàn)在我們得到了樣本集中所有電影與未知電影的距離，按照距離遞增排序，可以找到k個(gè)距離最近的電影。假定k=3，則三個(gè)最靠近的電影依次是He's Not Really into Dudes、Beautiful Woman和California Man。k-近鄰算法按照距離最近的三部電影的類型，決定未知電影的類型，而這三部電影全是愛情片，因此我們判定未知電影是愛情片。K近鄰算法的特點(diǎn)也顯而易見，由于選擇了K個(gè)鄰近的參考點(diǎn)，因此它的精度較高，且對異常值不敏感，無數(shù)據(jù)輸入假定，使用于數(shù)值型和標(biāo)稱型的數(shù)據(jù)。缺點(diǎn)是計(jì)算復(fù)雜度和空間復(fù)雜度雙高。
1.3 處理流程
收集數(shù)據(jù)：可以使用任何方法。 準(zhǔn)備數(shù)據(jù)：距離計(jì)算所需要的數(shù)值，最好是結(jié)構(gòu)化的數(shù)據(jù)格式。 分析數(shù)據(jù)：可以使用任何方法。 訓(xùn)練算法：此步驟不適用于k-近鄰算法。 測試算法：計(jì)算錯(cuò)誤率。 使用算法：首先需要輸入樣本數(shù)據(jù)和結(jié)構(gòu)化的輸出結(jié)果，然后運(yùn)行k近鄰算法判定輸入數(shù)據(jù)分別屬于哪個(gè)分類，最后應(yīng)用對計(jì)算出的分類執(zhí)行后續(xù)的處理。
1.4 距離計(jì)算
如果你認(rèn)真的看到這里，比較迷惑的點(diǎn)大概就在于距離應(yīng)該如何計(jì)算度量。
樣本之間的距離的計(jì)算，我們一般使用對于一般使用Lp距離進(jìn)行計(jì)算。
當(dāng)p=1時(shí)候，稱為曼哈頓距離(Manhattan distance)。
當(dāng)p=2時(shí)候，稱為歐氏距離(Euclidean distance)。
當(dāng)p=∞時(shí)候，稱為極大距離(infty distance)，表示各個(gè)坐標(biāo)的距離最大值,另外也包含夾角余弦等方法。
一般采用歐式距離較多，但是文本分類則傾向于使用余弦來計(jì)算相似度。
對于兩個(gè)向量,一般使用距離進(jìn)行計(jì)算。假設(shè)特征空間是n維實(shí)數(shù)向量空間 , 其中,,?,?的距離定義為:
這里的. 當(dāng)時(shí)候，稱為歐氏距離(Euclidean distance)：
當(dāng)時(shí)候，稱為曼哈頓距離(Manhattan distance)：
當(dāng)時(shí)候，稱為極大距離(infty distance), 表示各個(gè)坐標(biāo)的距離最大值：
需要注意的一點(diǎn)是，對于那些存在缺失值的數(shù)據(jù)，應(yīng)該如何使用歐式距離進(jìn)行計(jì)算呢？
接下來我們來詳細(xì)舉例說明：
正常的歐式距離：每個(gè)維度上都有數(shù)值。
帶有空值的歐式聚類：某個(gè)或多個(gè)維度上的值為空NaN。
只計(jì)算所有非空的值，對所有空加權(quán)到非空值的計(jì)算上，上例中，我們看到一個(gè)有3維，只有第二維全部非空，將第一維和第三維的計(jì)算加到第二維上，所有需要乘以3。
當(dāng)然這個(gè)空值我們也是需要處理一下的，需要計(jì)算每個(gè)樣本最近的k個(gè)樣本，使用簡單的加權(quán)平均進(jìn)行填充。
比如當(dāng)k=2時(shí)，樣本[1, 2, np.nan] 最近的2個(gè)樣本是: [3, 4, 3] [np.nan, 6, 5], 計(jì)算距離的時(shí)候使用歐式距離，只關(guān)注非空樣本。[1, 2, np.nan] 填充之后得到 [1, 2, (3 + 5) / 2] = [1, 2, 4]。
| 帶有空值的樣本 | 最相近的樣本1 | 最相近的樣本2 | 填充之后的值 |
|---|---|---|---|
| [1, 2, np.nan] | [3, 4, 3]; 3.46 | [np.nan, 6, 5]; 6.93 | [1, 2, 4] |
| [np.nan, 6, 5] | [3, 4, 3]; 3.46 | [8, 8, 7]; 3.46 | [5.5, 6, 5] |
所以，這樣我們碰到缺失值就再也不用害怕啦！
1.5 K值選擇
另外一個(gè)困惑就是K值的選擇。
如果選擇較小的K值，“學(xué)習(xí)”的近似誤差（approximation error)會(huì)減小，但 “學(xué)習(xí)”的估計(jì)誤差（estimation error) 會(huì)增大，噪聲敏感，K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合。
如當(dāng)K=1時(shí)，預(yù)測的結(jié)果只和最近的一個(gè)訓(xùn)練樣本相關(guān)，此時(shí)很容易發(fā)生過擬合。
如果選擇較大的K值，可以減少學(xué)習(xí)的估計(jì)誤差，但缺點(diǎn)是學(xué)習(xí)的近似誤差會(huì)增大。K值的增大就意味著整體的模型變得簡單。
如當(dāng)K=20時(shí)，預(yù)測的結(jié)果和最近的20個(gè)樣本相關(guān)，假如我們只有20個(gè)樣本，此時(shí)是所有樣本的平均值，此時(shí)所有預(yù)測值都是均值，很容易發(fā)生欠擬合。
一般情況下，使用KNN的時(shí)候，根據(jù)數(shù)據(jù)規(guī)模我們會(huì)從[3, 20]之間進(jìn)行嘗試，選擇最好的K。
2. 代碼實(shí)踐
我們借助鳶尾花的案例案例，了解在無缺失數(shù)值的數(shù)據(jù)集中，如何實(shí)現(xiàn)KNN算法。再借助馬絞痛數(shù)據(jù)來練習(xí)數(shù)據(jù)預(yù)處理，以及KNN分類的pipeline。
2.1 鳶尾花案例
第一步，首先庫函數(shù)導(dǎo)入：
import numpy as np
import matplotlib.pyplot as plt
# 導(dǎo)入KNN分類器
from sklearn.neighbors import KNeighborsClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split
第二步，載入鳶尾花的數(shù)據(jù)集，并按照8:2的比例劃分訓(xùn)練集與測試集：
# 載入鳶尾花數(shù)據(jù)集
# iris是一個(gè)對象類型的數(shù)據(jù)，其中包括了data（鳶尾花的特征）和target（也就是分類標(biāo)簽）
iris = datasets.load_iris()
# 將樣本與標(biāo)簽分開
x = iris['data']
y = iris['target']
print(x.shape, y.shape) # (150, 4) (150,)
# 劃分?jǐn)?shù)據(jù)集
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2) # 8:2
print(x_train.shape, x_test.shape, y_train.shape, y_test.shape)
# (120, 4) (30, 4) (120,) (30,)
第三步，使用KNeighborsClassifier來訓(xùn)練模型，這里我們設(shè)置參數(shù)k(n_neighbors)=5, 使用歐式距離(metric=minkowski & p=2)：
clf = KNeighborsClassifier(n_neighbors=5, p=2, metric="minkowski")
clf.fit(x_train, y_train) # fit可以簡單的認(rèn)為是表格存儲(chǔ)
# KNeighborsClassifier()
第四步，使用predict函數(shù)進(jìn)行模型預(yù)測，并計(jì)算出預(yù)測準(zhǔn)確率：
y_predict = clf.predict(x_test)
y_predict.shape # (30,)
acc = sum(y_predict == y_test) / y_test.shape[0]
acc
得到最終的準(zhǔn)確率為0.933。
2.2 馬絞痛案例
馬可能會(huì)發(fā)生一些病變，該數(shù)據(jù)集可以這么下載：
# 下載需要用到的數(shù)據(jù)集
!wget https://tianchi-media.oss-cn-beijing.aliyuncs.com/DSW/3K/horse-colic.csv
第一步，首先庫函數(shù)導(dǎo)入：
import numpy as np
import pandas as pd
# kNN分類器
from sklearn.neighbors import KNeighborsClassifier
# kNN數(shù)據(jù)空值填充
from sklearn.impute import KNNImputer
# 計(jì)算帶有空值的歐式距離
from sklearn.metrics.pairwise import nan_euclidean_distances
# 交叉驗(yàn)證
from sklearn.model_selection import cross_val_score
# KFlod的函數(shù)
from sklearn.model_selection import RepeatedStratifiedKFold
from sklearn.pipeline import Pipeline
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
第二步，讀出csv文件，并且簡要觀察其數(shù)據(jù)特點(diǎn)：
temp = pd.read_csv('KNN.csv', header=None)
temp # 數(shù)據(jù)的第23列表示是否病變，1為yes，2為no
明顯發(fā)現(xiàn)數(shù)據(jù)有些小'?'，比如第一行的第8列和第20、21列。
所以我們應(yīng)該在讀取的時(shí)候就把這些問號改成NaN，以便之后的處理：
df = pd.read_csv('KNN.csv', header=None, na_values='?') # na_values='?'
df
現(xiàn)在我們知道，該原始數(shù)據(jù)有300行，28列，并且存在NaN值待處理，其中數(shù)據(jù)的第23列表示是否病變，1為yes，2為no。
第三步，單獨(dú)提取出了病變結(jié)果列，并統(tǒng)計(jì)每一列的數(shù)據(jù)缺失個(gè)數(shù)：
data = df.values # 原始數(shù)據(jù)有300行，28列
x_index = [i for i in range(data.shape[1]) if i != 23]
x, y = data[:, x_index], data[:, 23] # 單獨(dú)提取出了病變結(jié)果列
print(x.shape, y.shape) # (300, 27) (300,)
cols_null=[]
for i in range(x.shape[1]):
cols_null.append(df[i].isnull().sum()) # 每一列的數(shù)據(jù)缺失個(gè)數(shù)
cols_null # [1, 0, 0,60, 24, 58, ...]
第四步，處理空值，進(jìn)行數(shù)值填充。這里我們使用KNNImputer進(jìn)行空值填充，其填充方法和之前在距離計(jì)算那里提到的計(jì)算方式是一樣的，所以就不再贅述：
imputer = KNNImputer()
# 填充數(shù)據(jù)集中的空值
x1 = imputer.fit_transform(x) # 或者是fit和transform分開寫
print(sum(np.isnan(x1))) # 處理后不再存在空值
print(sum(np.isnan(x)))
# [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
# [ 1 0 0 60 24 58 56 69 47 32 55 44 56 104 106 247 102 118 29 33 165 198 1 0 0 0 0]
接著你可以使用KNeighborsClassifier來處理該數(shù)據(jù)，詳細(xì)參考鳶尾花案例。
這里我們再介紹一種數(shù)據(jù)管道Pipeline的方式，任何有序的操作有可以看做pipeline，例如工廠流水線，對于機(jī)器學(xué)習(xí)模型來說，也就是數(shù)據(jù)流水線。是指數(shù)據(jù)通過管道中的每一個(gè)節(jié)點(diǎn)，結(jié)果除了之后，繼續(xù)流向下游。
對于我們這個(gè)例子，數(shù)據(jù)是有空值，我們會(huì)有一個(gè)KNNImputer節(jié)點(diǎn)用來填充空值，之后繼續(xù)流向下一個(gè)kNN分類節(jié)點(diǎn)，最后輸出模型。
所以將第四和第五步結(jié)合，使用數(shù)據(jù)管道來處理：
# 使用數(shù)據(jù)管道來處理
pipe = Pipeline(steps=[('imputer', KNNImputer(n_neighbors=5)), ('model', c())])
# 得到訓(xùn)練集合和驗(yàn)證集合, 8: 2
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.2)
# 驗(yàn)證model
pipe.fit(x_train, y_train)
score = pipe.score(x_test, y_test)
score # 0.8166
最終得到分?jǐn)?shù)為0.817，其實(shí)結(jié)果并不是很高，可能和K值的設(shè)定有關(guān)，具體設(shè)置為多少效果會(huì)更好，就留給你自己去探究。
參考資料
《機(jī)器學(xué)習(xí)實(shí)戰(zhàn)》 https://developer.aliyun.com/ai/scenario/febc2223e46f419dae84df47b1760ffc