1.0 算法介紹
1.1 基本思想
????????kNN是最簡單的機器算法之一，其基本原理通過對某個例的若干特征進行分析，進而對該個例的進行歸類，通過對該類別的先驗認知加深對個例的理解。簡單舉例，當我們去蛋糕店時，看到棕咖色的蛋糕一般情況下都會自動認為這個蛋糕是巧克力味道的，粉紅色的蛋糕會認為是草莓味的，白色的蛋糕是奶油味的，等等。這里，每個蛋糕就是一個個例，特征就是顏色。由于對蛋糕味道的判斷是基于先驗認知（即記憶）進行推斷的，因此kNN也叫memory based reasoning，MBR法。
1.2 應用場景
? ? ? ? 基于上述買蛋糕的場景可以發(fā)現(xiàn)，kNN一般用來對未知事物進行分類或者預測。而通過劃分類別，有時也可以作為降維的一種手段。
1.3 算法原理
? ? ? ? kNN的原理簡言之就是“近朱者赤，近墨者黑”。通過比較個例與先驗已知樣本的緊密程度，進而對個例進行判斷。簡單理解就是看一個人鄰近往來的是朱者多還是墨者多，如果朱者多則這個人可能也是個朱者，反之亦然。
? ? ? ? kNN算法中，對于鄰近的描述就是通過距離進行的，這里的距離一般默認為歐式空間距離。使用曼哈頓距離或其他自定義的距離形式完全取決于個人實際需求。
? ? ? ? 當然，要判斷朱者多還是墨者多，應該給定一個具體的界限范圍，否則有可能就計不清數(shù)量了。這個界限可以是限定數(shù)量，即距離最近的k個人，也可以是限定距離，即距離為r以內的所有人。
2.0 算法實現(xiàn)
2.1 偽碼實現(xiàn)
? ? ? ? Step 0：準備數(shù)據(jù)，包括但不限于檢查數(shù)據(jù)（如分類or連續(xù)、量綱差異、量級差異、數(shù)據(jù)有效性/準確性、分布形式等），數(shù)據(jù)轉換（如標準化、啞變量化等），分割數(shù)據(jù)為訓練集和測試集等；
? ? ? ? Step 1：模型訓練。通過訓練集建立樣本特征與類別的映射關系；
? ? ? ? Step 2：計算距離。計算測試集中的每個未分類個體與訓練集中所有樣本的距離；
? ? ? ? Step 3：選擇近鄰。若以數(shù)量為限，選擇與未分類個體最近的k個樣本；若以距離為限，選擇距未分類個體半徑r以內的所有樣本；
? ? ? ? Step 4：類別統(tǒng)計。統(tǒng)計未分類個體的近鄰類別，一般按照投票法進行，即取眾數(shù)；若連續(xù)變量時則取平均數(shù)。
? ? ? ? Step 5：分類判斷。將近鄰中頻次最多的類別賦予個體。
2.2 python算法演示
? ? ? ? （算法的手動實現(xiàn)就略過了，本質就是算距離和排序，這里直接演示調用sklearn實現(xiàn)）
2.2.1?按數(shù)量尋找近鄰 KNeighborsClassifier
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.neighbors import RadiusNeighborsClassifier
from sklearn.metrics import accuracy_score
from sklearn.preprocessing import StandardScaler
"""準備數(shù)據(jù)"""
cancers = datasets.load_breast_cancer()? ? #導入數(shù)據(jù)集，sklearn自帶數(shù)據(jù)集，此外還有iris，boston等數(shù)據(jù)集
X = cancers['data']????#特征值
y = cancers['target']????#類別標簽
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=20)? ? #
train_test_split將數(shù)據(jù)集隨機分割為訓練集和測試集，test_size為測試集比例，random_state為隨機種子
kNC = KNeighborsClassifier(n_neighbors=5)????#類的實例化，設置近鄰數(shù)量，默認n_neighbors=5
kNC.fit(X_train, y_train)????#模型訓練
y_predict_kNC = kNC.predict(X_test)? ? #模型預測：計算距離、篩選近鄰、統(tǒng)計類別、預測類別
accuracy_score(y_test, y_predict_kNC)? ? #結果評價，準確率0.9300699300699301，調整n_neighbors的值，可得不同結果
2.2.2?按半徑尋找近鄰 RadiusNeighborsClassifier
rNC = RadiusNeighborsClassifier(radius=10) ???? #類的實例化，默認半徑radius=1
rNC.fit(X_train, y_train)? ? #模型訓練
y_predict_rNC = rNC.predict(X_test)? ? #模型預測
accuracy_score(y_test, y_predict_rNC)
? ? ? ? 上段代碼中，到y(tǒng)_predict_rNC這一步會報出錯誤?ValueError: No neighbors found for test samples [0, 1, 2,...]，意思是測試集中的這些個例在半徑r內沒有找到近鄰。因此需要放大radius?？墒褂肗earestNeighbors查看測試個例與近鄰的距離。
2.2.3?查看近鄰信息 NearestNeighbors
from sklearn.neighbors import NearestNeighbors
NN = NearestNeighbors(n_neighbors=3).fit(X_test)
NN.kneighbors(X_train[:1])? ? #查看測試集中第一個個例的最近3個近鄰
? ? ? ? 上段代碼的最終返回結果為 (array([[10.34234317, 12.30153886, 12.46914998]]), array([[183, 335, 115]]))，其中包含了兩個array。array([[10.34234317, 12.30153886, 12.46914998]]是三個近鄰與個例的距離，array([[183, 335, 115]])是這三個近鄰的索引號。可以發(fā)現(xiàn)最近的距離都在10以上，這就說明了2.2.2中以半徑為10找不到近鄰的原因。
? ? ? ? 事實上，這個樣本中，個例間的距離離散程度比較大，比如X_train[115:116]這個個例與其最近近鄰的距離都達到1100以上。此時如果要使用半徑查找近鄰則需要將radius設置在1100以上。而個例X_train[:1]與近鄰的距離僅在12左右，說明數(shù)據(jù)整體是分布非常不均勻的，這種情況下用半徑法可能難以達到較高的預測準確性，此時就要考慮使用其他分類方法或對數(shù)據(jù)進行標準化。（注:RadiusNeighborsClassifier(radius=1200)時，準確率為0.7552447552447552）
