KNN（K-Nearest Neighbor躯砰，K-近鄰算法）算法是一種有監(jiān)督的機器學習算法，可以解決分類問題莺褒，也可以解決回歸問題挖炬。

1.KNN算法原理

K-近鄰算法的核心思想是未標記樣本的類別，由距離其最近的K個鄰居投票來決定料仗。

假設湾盗，我們有一個已經(jīng)標記的數(shù)據(jù)集，即已經(jīng)知道了數(shù)據(jù)集中每個樣本所屬的類別立轧。此時格粪，有一個未標記的數(shù)據(jù)樣本，我們的任務是預測出這個數(shù)據(jù)樣本所屬的類別氛改。K-近鄰算法的原理是帐萎，計算待標記的數(shù)據(jù)樣本和數(shù)據(jù)集中每個樣本的距離，取距離最近的K個樣本胜卤。待標記的數(shù)據(jù)樣本所屬的類別疆导，就由這K個距離最近的樣本投票產(chǎn)生。

假設X_test為待標記的數(shù)據(jù)樣本葛躏，X_train為已標記的數(shù)據(jù)集澈段，算法原理的偽代碼如下：

• 遍歷X_train中的所有樣本，計算每個樣本與X_test的距離舰攒，并把距離保存在Distance數(shù)組中败富。
• 對Distance數(shù)組進行排序，取距離最近的K個點摩窃，記為X_knn兽叮。
• 在X_knn中統(tǒng)計每個類別的個數(shù)，即class0在X_knn中有幾個樣本猾愿，class1在X_knn中有幾個樣本等鹦聪。
• 待標記樣本的類別，就是在X_knn中樣本數(shù)最多的那個類別蒂秘。

1.KNN算法的優(yōu)缺點

• 優(yōu)點：準確度高椎麦，對異常值和噪聲有較高的容忍度。
• 缺點：計算量較大材彪，對內存的需求也較大观挎。從算法原理可以看出來琴儿，每次對一個未標記樣本進行分類時，都需要全部計算一遍距離嘁捷。

2.KNN算法的參數(shù)

其算法參數(shù)是K造成，參數(shù)選擇需要根據(jù)數(shù)據(jù)來決定。K值越大雄嚣，模型的偏差越大晒屎，對噪聲數(shù)據(jù)越不敏感，當K值很大時缓升，可能造成模型欠擬合鼓鲁；K值越小，模型的方差就會越大港谊，當K值太小骇吭，就會造成模型過擬合。

3.KNN算法的變種

K-近鄰算法有一些變種歧寺，其中之一就是可以增加鄰居的權重燥狰。默認情況下，在計算距離時斜筐，都是使用相同的權重龙致。實際上，我們可以針對不同的鄰居指定不同的權重顷链，如距離越近權重越高目代。這個可以通過指定算法的weights參數(shù)來實現(xiàn)。

另外一個變種是嗤练，使用一定半徑內的點取代距離最近的K個點榛了。在scikit-learn里，RadiusNeighborsClassifier類實現(xiàn)了這個算法的變種潭苞。當數(shù)據(jù)采樣不均勻時，該算法變種可以取得更好的性能真朗。

2.示例：使用KNN算法進行分類

在scikit-learn里此疹，使用K-近鄰算法進行分類處理的是sklearn.neightbors.KNeightborsClassifier類。
（1）生成已標記的數(shù)據(jù)集

from sklearn.datasets.samples_generator import make_blobs
# 生成數(shù)據(jù)
centers = [[-2,2],[2,2],[0,4]]
X,y = make_blobs(n_samples=60,centers=centers,random_state=0,cluster_std=0.60)

我們使用sklearn.datasets.samples_generator包下的make_blobs()函數(shù)來生成數(shù)據(jù)集遮婶，這里生成60個訓練樣本蝗碎，這些樣本分布在centers參數(shù)指定的中心點的周圍。cluster_std是標準差旗扑，用來指明生成的點分布的松散程度蹦骑。生成的訓練數(shù)據(jù)集放在變量X里面，數(shù)據(jù)集的類別標記放在y里面臀防。

我們可以把X和y的值打印出來查看眠菇，一個更直觀的方法是使用matplotlib庫边败，它可以很容易地把生成的點畫出來：

import matplotlib.pyplot as plt
import numpy as np
plt.figure(figsize=(16,10),dpi=144)
c = np.array(centers)
plt.scatter(X[:,0],X[:,1],c=y,s=100,cmap='cool')
plt.scatter(c[:,0],c[:,1],s=100,marker='^',c='orange')
plt.show()

figure4_1.png

這些點的分布情況在坐標軸上一目了然，其中三角形的點即各個類別的中心點捎废。
（2）使用KNeighborsClassifier來對算法進行訓練笑窜，我們選擇的參數(shù)是K=5

from sklearn.neighbors import KNeighborsClassifier
k = 5
clf = KNeighborsClassifier(n_neighbors=k)
clf.fit(X,y)

得到的模型如下：

KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=1, n_neighbors=5, p=2,
           weights='uniform')

（3）對一個新樣本進行預測

X_sample = [0,2]
X_sample = np.array(X_sample).reshape(1, -1)
y_sample = clf.predict(X_sample)
neighbors = clf.kneighbors(X_sample,return_distance=False)

我們要預測的樣本是[0,2]，使用kneighbors()方法登疗，把這個樣本周圍距離最近的5個點取出來排截。取出來的點是訓練樣本X里的索引，從0開始計算辐益。
注意：kneighbors()接收一個二維數(shù)組作為參數(shù)断傲，所以X_sample需要變成二維。
（4）把待預測的樣本以及和其最近的5個點標記出來

plt.figure(figsize=(16,10),dpi=144)
plt.scatter(X[:, 0], X[:, 1], c=y, s=100, cmap='cool')    # 樣本
plt.scatter(c[:, 0], c[:, 1], s=100, marker='^', c='k')   # 中心點
plt.scatter(X_sample[0][0],X_sample[0][1],marker="x", s=100, cmap='cool')  #待預測的點
#預測點與距離最近的5個樣本的連線
for i in neighbors[0]:
    plt.plot([X[i][0],X_sample[0][0]],[X[i][1],X_sample[0][1]],'k--',linewidth=0.6)
plt.show()

figure4_2.png

從上圖中可以清楚地看到KNN算法的原理智政。

3.示例：使用KNN算法進行回歸擬合

分類問題的預測值是離散的认罩，我們也可以使用KNN算法對連續(xù)區(qū)間內的數(shù)值進行預測，即進行回歸擬合女仰。在scikit-learn里面猜年，使用KNN算法進行回歸擬合的實現(xiàn)是sklearn.neighbors.KNeighborsRegressor類。
（1）生成數(shù)據(jù)集疾忍，在余弦曲線的基礎上加入了噪聲：

import numpy as np
n_dots = 40
X = 5 * np.random.rand(n_dots,1)
y = np.cos(X).ravel()
y += 0.2*np.random.rand(n_dots)-0.1

（2）使用KNeighborsRegressor來訓練模型：

from sklearn.neighbors import KNeighborsRegressor
k = 5
knn = KNeighborsRegressor(k)
knn.fit(X,y)

生成的模型如下：

KNeighborsRegressor(algorithm='auto', leaf_size=30, metric='minkowski',
          metric_params=None, n_jobs=1, n_neighbors=5, p=2,
          weights='uniform')

可以使用score()方法計算擬合曲線對訓練樣本的擬合準確性：

knn.score(X,y)
0.9596828473009764

有了模型乔外，接下來就是進行回歸擬合。
一個常用的方法是一罩，在X軸上的指定區(qū)域生成足夠多的點杨幼，針對這些足夠密集的點，使用訓練出來的模型進行預測聂渊，得到預測值y_pred差购，然后在坐標軸上，把所有的預測點連接起來汉嗽，這樣就畫出了擬合曲線欲逃。
生成足夠密集的點并進行預測：

T = np.linspace(0,5,500)[:,np.newaxis]
y_pred = knn.predict(T)

（3）把這些預測點連起來，構成擬合曲線：

plt.figure(figsize=(16,10),dpi=144)
plt.scatter(X,y,c='g',label='data',s=100)
plt.plot(T,y_pred,c='k',label='prediction',lw=4)
plt.axis('tight')
plt.title('KNeighborsRegressor (k = %i)' % k)
plt.show()

最終生成的擬合曲線和訓練樣本數(shù)據(jù)如圖：

figure4_3.png

4.示例：糖尿病預測

本節(jié)使用KNN算法及其變種饼暑，對Pima印第安人的糖尿病進行預測稳析。數(shù)據(jù)來源kaggle.com，網(wǎng)址為：https://www.kaggle.com/uciml/pima-indians-diabetes-database
大家可以自己去下載弓叛。

1.加載數(shù)據(jù)

使用Pandas加載數(shù)據(jù)：

import pandas as pd
data = pd.read_csv('E:\code\datasets\pima-indians-diabetes\diabetes.csv')
print('dataset shape {}'.format(data.shape))
data.head()

輸出如下：

dataset shape (768, 9)
Out[23]:
Pregnancies Glucose BloodPressure   SkinThickness   Insulin BMI DiabetesPedigreeFunction    Age Outcome
0   6   148 72  35  0   33.6    0.627   50  1
1   1   85  66  29  0   26.6    0.351   31  0
2   8   183 64  0   0   23.3    0.672   32  1
3   1   89  66  23  94  28.1    0.167   21  0
4   0   137 40  35  168 43.1    2.288   33  1

從打印出的信息可以看到彰居，這個數(shù)據(jù)集一共有768個樣本、8個特征撰筷、1個標簽（Outcome：0表示沒有糖尿病陈惰，1表示有糖尿病）毕籽。8個特征分別如下：

• Pregnancies：懷孕的次數(shù)
• Glucose：血漿葡萄糖濃度抬闯，采用2小時口服葡萄糖耐量試驗測得
• BloodPressure：舒張壓（毫米汞柱）
• SkinThickness：肱三頭肌皮膚褶皺厚度（毫米）
• Insulin：兩個小時血清胰島素（μU/毫升）
• BMI：身體質量指數(shù)井辆，體重除以身高的平方
• DiabetesPedigreeFunction：糖尿病血統(tǒng)指數(shù)，糖尿病和家庭遺傳相關
• Age：年齡
  我們可以進一步觀察數(shù)據(jù)集里的陽性和陰性樣本的個數(shù)：

data.groupby('Outcome').size()

輸出為：

Outcome
0    500
1    268
dtype: int64

其中画髓，陰性樣本500例掘剪，陽性樣本268例。
接著需要對數(shù)據(jù)集進行簡單處理奈虾，把8個特征值分離出來夺谁，作為訓練數(shù)據(jù)集，把Outcome列分離出來作為目標值肉微。然后匾鸥，把數(shù)據(jù)集劃分為訓練數(shù)據(jù)集和測試數(shù)據(jù)集。

X = data.iloc[:,:8]
Y = data.iloc[:,8]
print('shape of X {}; shape of Y {}'.format(X.shape,Y.shape))
from sklearn.model_selection import train_test_split
X_train,X_test,Y_train,Y_test=train_test_split(X,Y,test_size=0.2)

輸出：

shape of X (768, 8); shape of Y (768,)

2.模型比較

分別使用普通的KNN算法碉纳、帶權重的KNN算法和指定半徑的KNN算法對數(shù)據(jù)集進行擬合并計算評分：

from sklearn.neighbors import KNeighborsClassifier, RadiusNeighborsClassifier

models = []
models.append(("KNN", KNeighborsClassifier(n_neighbors=2)))
models.append(("KNN with weights", KNeighborsClassifier(
    n_neighbors=2, weights="distance")))
models.append(("Radius Neighbors", RadiusNeighborsClassifier(
    n_neighbors=2, radius=500.0)))

results = []
for name, model in models:
    model.fit(X_train, Y_train)
    results.append((name, model.score(X_test, Y_test)))
for i in range(len(results)):
    print("name: {}; score: {}".format(results[i][0],results[i][1]))

三種算法的性能如下：

name: KNN; score: 0.6883116883116883
name: KNN with weights; score: 0.6753246753246753
name: Radius Neighbors; score: 0.6233766233766234

帶權重的KNN算法勿负，我們選擇了距離越近、權重越高劳曹。指定半徑的KNN算法的半徑選擇了500奴愉。從上面的輸出結果可以看出，普通的KNN算法性能最好铁孵。問題來了锭硼，這個判斷準確么？答案是不準確蜕劝。因為我們的訓練樣本和測試樣本是隨機分配的檀头，不同的訓練樣本和測試樣本組合可能導致計算出來的算法準確性是有差異的。我們可以試著多次運行上面的代碼岖沛，觀察輸出值是否有變化暑始。

怎么樣更準確地對比算法準確性呢？一個方法是婴削，多次隨機分配訓練數(shù)據(jù)集和交叉驗證數(shù)據(jù)集廊镜，然后求模型準確性評分的平均值。所幸唉俗，我們不需要從頭實現(xiàn)這個過程嗤朴，scikit-learn提供了KFold和cross_val_score()函數(shù)來處理這種問題：

from sklearn.model_selection import KFold
from sklearn.model_selection import cross_val_score
results = []
for name, model in models:
    kfold = KFold(n_splits=10)
    cv_result = cross_val_score(model, X, Y, cv=kfold)
    results.append((name, cv_result))
for i in range(len(results)):
    print("name: {}; cross val score: {}".format(
        results[i][0],results[i][1].mean()))

上述代碼中，我們通過KFold把數(shù)據(jù)集分成10份互躬，其中1份會作為交叉驗證數(shù)據(jù)集來計算模型準確性播赁，剩余的9份作為訓練數(shù)據(jù)集颂郎。cross_val_score()函數(shù)總共計算出10次不同訓練數(shù)據(jù)集和交叉驗證數(shù)據(jù)集組合得到的模型準確性評分吼渡，最后求平均值。這樣的評價結果相對更準確一些乓序。
輸出結果為：

name: KNN; cross val score: 0.7147641831852358
name: KNN with weights; cross val score: 0.6770505809979495
name: Radius Neighbors; cross val score: 0.6497265892002735

3.模型訓練及分析

看起來寺酪，還是普通的KNN算法性能更優(yōu)一些坎背。接下來，我們就使用普通的KNN算法模型對數(shù)據(jù)集進行訓練寄雀，并查看對訓練樣本的擬合情況以及對測試樣本的預測準確性情況：

knn = KNeighborsClassifier(n_neighbors=2)
knn.fit(X_train, Y_train)
train_score = knn.score(X_train, Y_train)
test_score = knn.score(X_test, Y_test)
print("train score: {}; test score: {}".format(train_score, test_score))

輸出結果為：

train score: 0.8273615635179153; test score: 0.6883116883116883

從這個輸出中可以看到兩個問題得滤。一是對訓練樣本的擬合情況不佳，評分才0.82多一些盒犹，這說明算法模型太簡單了懂更，無法很好地擬合訓練樣本。二是模型的準確性欠佳急膀，不到69%的預測準確性沮协。我們可以進一步畫出學習曲線，證實結論卓嫂。

from sklearn.model_selection import ShuffleSplit
from common.utils import plot_learning_curve
knn = KNeighborsClassifier(n_neighbors=2)
cv = ShuffleSplit(n_splits=10, test_size=0.2, random_state=0)
plt.figure(figsize=(10, 6))
plot_learning_curve(plt, knn, "Learn Curve for KNN Diabetes", 
                    X, Y, ylim=(0.0, 1.01), cv=cv);

figure4_4.png

從圖中可以看出來慷暂，訓練樣本評分較低，且測試樣本與訓練樣本距離較大晨雳，這是典型的欠擬合現(xiàn)象行瑞。KNN算法沒有更好的措施來解決欠擬合問題，我們學完本書的其他章節(jié)后餐禁，可以試著用其他算法（如邏輯回歸算法血久、支持向量機等）來對比不同模型的準確性情況。

4.特征選擇及數(shù)據(jù)可視化

有沒有直觀的方法坠宴，來揭示出為什么KNN算法不是針對這一問題的好模型洋魂？一個辦法是把數(shù)據(jù)畫出來，可是我們有8個特征喜鼓，無法在這么高的維度里畫出數(shù)據(jù)副砍，并直觀地觀察。一個解決辦法是特征選擇庄岖，即只選擇2個與輸出值相關性最大的特征豁翎，這樣就可以在二維平面上畫出輸入特征值與輸出值的關系了。

所幸隅忿，scikit-learn在sklearn.feature_selection包里提供了豐富的特征選擇方法心剥。我們使用SelectKBest來選擇相關性最大的兩個特征：

from sklearn.feature_selection import SelectKBest
selector = SelectKBest(k=2)
X_new = selector.fit_transform(X, Y)
X_new[0:5]

把相關性最大的兩個特征放在X_new變量里，同時輸出了前5個數(shù)據(jù)樣本背桐。輸出結果為：

array([[148. ,  33.6],
       [ 85. ,  26.6],
       [183. ,  23.3],
       [ 89. ,  28.1],
       [137. ,  43.1]])

我們可能會好奇优烧，相關性最大的特征到底是哪兩個？對比一下本節(jié)開頭的數(shù)據(jù)即可知道链峭，它們分別是Glucose（血糖濃度）和BMI（身體質量指數(shù)）畦娄。血糖濃度和糖尿病的關系自不必說，身體質量指數(shù)是反映肥胖程度的指標，從業(yè)務角度來看熙卡，我們選擇出來的2個相關性最高的特征還算合理杖刷。好學的讀者可能想打破砂鍋問到底：SelectKBest到底使用什么神奇的方法選擇出了這兩個相關性最高的特征呢？這里涉及到一些統(tǒng)計學的知識驳癌，感興趣的讀者可參閱下一節(jié)內容的延伸閱讀滑燃。

我們來看看，如果只使用這2個相關性最高的特征的話颓鲜，3種不同的KNN算法哪個準確性更高：

results = []
for name, model in models:
    kfold = KFold(n_splits=10)
    cv_result = cross_val_score(model, X_new, Y, cv=kfold)
    results.append((name, cv_result))
for i in range(len(results)):
    print("name: {}; cross val score: {}".format(
        results[i][0],results[i][1].mean()))

這次使用X_new作為輸入表窘，輸出如下

name: KNN; cross val score: 0.725205058099795
name: KNN with weights; cross val score: 0.6900375939849623
name: Radius Neighbors; cross val score: 0.6510252904989747

從輸出可以看出來，還是普通的KNN模型準確性較高甜滨，其準確性也達到了將近73%蚊丐，與所有特征拿來一塊兒訓練的準確性差不多。這也側面證明了SelectKBest特征選擇的準確性艳吠。

回到目標上來麦备，我們是想看看為什么KNN無法很好地擬合訓練樣本。現(xiàn)在我們只有2個特征昭娩，可以很方便地在二維坐標上畫出所有的訓練樣本凛篙，觀察這些數(shù)據(jù)的分布情況：

plt.figure(figsize=(10, 6))
plt.ylabel("BMI")
plt.xlabel("Glucose")
plt.scatter(X_new[Y==0][:, 0], X_new[Y==0][:, 1], c='r', s=20, marker='o');   #畫出樣本
plt.scatter(X_new[Y==1][:, 0], X_new[Y==1][:, 1], c='g', s=20, marker='^');   #畫出樣本

figure4_5.png

橫坐標是血糖值，縱坐標是BMI值栏渺，反映身體肥胖情況呛梆。從圖中可以看出，在中間數(shù)據(jù)集密集的區(qū)域磕诊，陽性樣本和陰性樣本幾乎重疊在一起了填物。假設現(xiàn)在有一個待預測的樣本在中間密集區(qū)域，它的陽性鄰居多還是陰性鄰居多呢霎终？這真的很難說滞磺。這樣就可以直觀地看到，KNN算法在這個糖尿病預測問題上莱褒，無法達到很高的預測準確性击困。

5.拓展閱讀

本節(jié)首先介紹提高KNN算法運算效率方面的知識，這里只給出一些通用的描述和參考資料广凸，感興趣的讀者可以進一步深入研究阅茶。另外，再介紹一下特征選擇時谅海，計算相關性大小的SelectKBest()函數(shù)背后的統(tǒng)計學知識脸哀。

1.如何提高KNN算法的運算效率

根據(jù)算法原理，每次需要預測一個點時扭吁，我們都需要計算訓練數(shù)據(jù)集里每個點到這個點的距離撞蜂，然后選出距離最近的k個點進行投票白筹。當數(shù)據(jù)集很大時，這個計算成本非常高谅摄。針對個樣本，個特征的數(shù)據(jù)集系馆，其算法復雜度為送漠。

為了解決這個問題，一種叫K-D Tree的數(shù)據(jù)結構被發(fā)明出來由蘑。為了避免每次都重新計算一遍距離闽寡，算法會把距離信息保存在一棵樹里，這樣在計算之前從樹里查詢距離信息尼酿，盡量避免重新計算爷狈。其基本原理是，如果A和B距離很遠裳擎，B和C距離很近涎永，那么A和C的距離也很遠。有了這個信息鹿响，就可以在合適的時候跳過距離遠的點羡微。這樣優(yōu)化后的算法復雜度可降低到。感興趣的讀者可參閱論文：Bentley, J.L., Communications of the ACM (1975)惶我。

1989年妈倔，另外一種稱為Ball Tree的算法，在K-D Tree的基礎上對性能進一步進行了優(yōu)化绸贡。感興趣的讀者可以搜索Five balltree construction algorithms來了解詳細的算法信息盯蝴。

2.相關性測試

先通過一個簡單的例子來看假設檢驗問題，即判斷假設的結論是否成立或成立的概率有多高听怕。假設捧挺，在一個城市隨機采樣到程序員和性別的關系的數(shù)據(jù)：

figure4_5_1.png

假設，我們的結論是程序員和性別無關尿瞭，這個假設稱為原假設（null hypothesis）松忍。問：通過我們隨機采樣觀測到的數(shù)據(jù)，原假設是否成立筷厘，或者說原假設成立的概率有多高鸣峭？

卡方檢驗（chi-squared test）是檢測假設成立與否的一個常用的工具。它的計算公式是：

figure4_5_2.png

figure4_5_3.png

figure4_5_4.png

針對我們的問題遍膜，可以查表得到碗硬，自由度為1的卡方分布，在99%處的卡方值為6.63瓢颅。我們計算出來的卡方值為7.670恩尾。由于7.67>6.63，故有99%的把握可以推翻原假設挽懦。換個說法翰意，如果原假設成立，即程序員職業(yè)和性別無關信柿，那么我們隨機采樣到的數(shù)據(jù)出現(xiàn)的概率將低于1%冀偶。我們可以搜索“卡方表”或“Chi Squared Table”找到不同自由度對應的卡方值。

卡方值的大小可以反映變量與目標值的相關性渔嚷，值越大进鸠，相關性越大。利用這一特性形病，SelectKBest()函數(shù)就可以計算不同特征的卡方值來判斷特征與輸出值的相關性大小客年，從而完成特征選擇霞幅。在scikit-learn里，計算卡方值的函數(shù)是sklearn.feature_selection.chi2()量瓜。除了卡方檢驗外司恳，還有F值檢驗等算法，也可以用來評估特征與目標值的相關性绍傲。SelectKBest默認使用的就是F值檢驗算法扔傅，在scikit-learn里，使用sklearn.feature_selection.f_classif來計算F值唧取。關于F值相關的資料，感興趣的讀者可以在英文版維基百科上搜索“Fisher’sexact test”划提，了解更多信息枫弟。