一、KNN算法原理

1、原理概述

KNN 的英文叫 K-Nearest Neighbo，應(yīng)該算是數(shù)據(jù)挖掘算法中最簡(jiǎn)單的一種，也是相對(duì)最簡(jiǎn)單的一種分類方法，屬于監(jiān)督學(xué)習(xí)范疇。所謂K最近鄰，就是K個(gè)最近的鄰居的意思，每個(gè)樣本都可以用它最接近的K個(gè)鄰居來(lái)代表。與其他機(jī)器學(xué)習(xí)算法不一樣的是：KNN沒(méi)有顯式的學(xué)習(xí)過(guò)程，也就是說(shuō)沒(méi)有訓(xùn)練階段，數(shù)據(jù)集事先已有了分類和特征值，待收到新樣本后直接進(jìn)行處理。

KNN思路大致為：一個(gè)訓(xùn)練數(shù)據(jù)集事先對(duì)每個(gè)訓(xùn)練樣本標(biāo)記好對(duì)應(yīng)的標(biāo)簽。當(dāng)來(lái)了一個(gè)新的測(cè)試樣本預(yù)測(cè)分類時(shí)，K近鄰的方法就是找到測(cè)試樣本到原先的訓(xùn)練數(shù)據(jù)集中尋找每一個(gè)樣本的相似度，然后根據(jù)相似度大小對(duì)訓(xùn)練數(shù)據(jù)集中樣本排序，取前K個(gè)最相近的樣本的標(biāo)簽的眾數(shù)作為測(cè)試樣本的標(biāo)簽（即前K個(gè)樣本投票決定）。測(cè)試樣本到原先訓(xùn)練數(shù)據(jù)集中每個(gè)訓(xùn)練樣本的距離度量，一般用的是歐氏距離，也可以使用p范數(shù)（歐氏距離是2范數(shù)）。

工作原理總結(jié)：

1、計(jì)算待分類樣本與其他樣本之間的距離；

2、統(tǒng)計(jì)距離最近的K個(gè)鄰居；

3、對(duì)于K個(gè)最近的鄰居，它們屬于哪個(gè)分類最多，待分類物體就屬于哪一類。K 值如何選擇。

2、K值的取值

K：臨近數(shù)，即在預(yù)測(cè)目標(biāo)點(diǎn)時(shí)取幾個(gè)臨近的點(diǎn)來(lái)預(yù)測(cè)。

K值得選取非常重要，因?yàn)槿绻?K 值比較小，就相當(dāng)于未分類物體與它的鄰居非常接近才行。這樣產(chǎn)生的一個(gè)問(wèn)題就是，如果鄰居點(diǎn)是個(gè)噪聲點(diǎn)，那么未分類物體的分類也會(huì)產(chǎn)生誤差，這樣 KNN 分類就會(huì)產(chǎn)生過(guò)擬合。

如果 K 值比較大，相當(dāng)于距離過(guò)遠(yuǎn)的點(diǎn)也會(huì)對(duì)未知物體的分類產(chǎn)生影響，雖然這種情況的好處是魯棒性強(qiáng)，但是不足也很明顯，會(huì)產(chǎn)生欠擬合情況，也就是沒(méi)有把未分類物體真正分類出來(lái)。

所以 K 值應(yīng)該是個(gè)實(shí)踐出來(lái)的結(jié)果，并不是我們事先而定的。在工程上，我們一般采用交叉驗(yàn)證的方式選取 K 值。交叉驗(yàn)證的思路就是，把樣本集中的大部分樣本作為訓(xùn)練集，剩余的小部分樣本用于預(yù)測(cè)，來(lái)驗(yàn)證分類模型的準(zhǔn)確性。所以在 KNN 算法中，我們一般會(huì)把 K 值選取在較小的范圍內(nèi)，同時(shí)在驗(yàn)證集上準(zhǔn)確率最高的那一個(gè)最終確定作為 K 值。

3、距離的選取

距離就是平面上兩個(gè)點(diǎn)的直線距離

關(guān)于距離的度量方法，常用的有：歐氏距離、曼哈頓距離、閔可夫斯基距離、切比雪夫距離、余弦值、相關(guān)度或其他。

1）歐氏距離

歐氏距離是我們最常用的距離公式，也叫做歐幾里得距離。在二維空間中，兩點(diǎn)的歐式距離就是：

圖片

同理，我們也可以求得兩點(diǎn)在 n 維空間中的距離：

圖片

2）曼哈頓距離

曼哈頓距離在幾何空間中用的比較多，等于兩個(gè)點(diǎn)在坐標(biāo)系上絕對(duì)軸距總和。用公式表示就是：

圖片

3）閔可夫斯基距離

閔可夫斯基距離不是一個(gè)距離，而是一組距離的定義。對(duì)于 n 維空間中的兩個(gè)點(diǎn) x(x1,x2,…,xn) 和 y(y1,y2,…,yn) ， x 和 y 兩點(diǎn)之間的閔可夫斯基距離為：

圖片

其中 p 代表空間的維數(shù)，當(dāng) p=1 時(shí)，就是曼哈頓距離；當(dāng) p=2 時(shí)，就是歐氏距離；當(dāng) p→∞時(shí)，就是切比雪夫距離。

二、sklearn庫(kù)函數(shù)調(diào)用

1、預(yù)測(cè)案例

1）案例代碼

這個(gè)案例是我目前學(xué)習(xí)課程中的案例--使用 KNN 對(duì)手寫數(shù)字進(jìn)行識(shí)別分類。手寫數(shù)字?jǐn)?shù)據(jù)集是個(gè)很有名的用于圖像識(shí)別的數(shù)據(jù)集。數(shù)字識(shí)別的過(guò)程就是將這些圖片與分類結(jié)果 0-9 一一對(duì)應(yīng)起來(lái)。完整的手寫數(shù)字?jǐn)?shù)據(jù)集 MNIST 里面包括了 60000 個(gè)訓(xùn)練樣本，以及 10000 個(gè)測(cè)試樣本。我使用的是 sklearn 自帶的手寫數(shù)字?jǐn)?shù)據(jù)集做 KNN 分類，這個(gè)數(shù)據(jù)集可理解為一個(gè)簡(jiǎn)版的 MNIST 數(shù)據(jù)集。

# 導(dǎo)入依賴包
import numpy as np
import matplotlib 
import matplotlib.pyplot as plt
 
# 用來(lái)做數(shù)據(jù)集的分割，把數(shù)據(jù)分成訓(xùn)練集和測(cè)試集，這樣做的目的是為了評(píng)估模型
from sklearn.model_selection import train_test_split
# 導(dǎo)入了KNN的模塊，是sklearn提供的現(xiàn)成的算法
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
# 導(dǎo)入數(shù)據(jù)集
digits=datasets.load_digits()
# X存儲(chǔ)的是數(shù)據(jù)的特征，y存儲(chǔ)的每一個(gè)樣本的標(biāo)簽或者分類
X=digits.data
y=digits.target
# 查看數(shù)據(jù)結(jié)構(gòu)
X.shape
y.shape
digits.keys()
digits.target_names
X[:10]
# 數(shù)據(jù)探索
some_digit=X[666]
some_digit_image=some_digit.reshape(8,8)
plt.imshow(some_digit_image,cmap=matplotlib.cm.binary)
plt.show()

圖片

# 分割數(shù)據(jù)，將20%的數(shù)據(jù)作為測(cè)試集，其余作為訓(xùn)練集（
X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.2,random_state=666) #設(shè)置隨機(jī)種子random_st
# 調(diào)用庫(kù)函數(shù)里的KNN，選擇K值
# 定義了一個(gè)KNN object，帶有參數(shù)叫做n_neighbors=3， 即K值是3
knn_clf=KNeighborsClassifier(n_neighbors=3)
knn_clf.fit(X_train,y_train)
# 預(yù)測(cè)以及計(jì)算準(zhǔn)確率
y_predict=knn_clf.predict(X_test)
accuracy_score(y_test,y_predict)
correct=accuracy_score(y_test,y_predict)
print("正確率:",correct)

運(yùn)行結(jié)果：
正確率: 0.988888888888888

案例代碼構(gòu)造一個(gè) KNN 分類器 knn_clf，把訓(xùn)練集的數(shù)據(jù)傳入構(gòu)造好的 knn_clf，并通過(guò)測(cè)試集進(jìn)行結(jié)果預(yù)測(cè)，與測(cè)試集的結(jié)果進(jìn)行對(duì)比，得到 KNN 分類器準(zhǔn)確率為0.9889

2）參數(shù)概述

KNN分類器的常用構(gòu)造參數(shù)有：

1、n_neighbors 代表鄰居的數(shù)量。

2、weights： 代表所有鄰居的權(quán)重，其中 uniform 代表所有鄰居權(quán)重相同， distance 代表權(quán)重是距離的倒數(shù)。還可以自定義。

3、algorithm: 計(jì)算鄰居的方法，auto代表 根據(jù)數(shù)據(jù)的情況自動(dòng)選擇，kd_tree 是kd樹(shù)，適用于維數(shù)不超過(guò)20的情況。ball_tree是球樹(shù)，可以用于維度更大的情況。brute 是暴力搜索。

4、leaf_size:是kd樹(shù)或者球樹(shù)的葉子數(shù)量，默認(rèn)是20.

2、KNN超參數(shù)

在KNN里，通過(guò)交叉驗(yàn)證，我們即可以得出最合適的K值。它的核心思想無(wú)非就是把一些可能的K逐個(gè)去嘗試一遍，然后選出效果最好的K值。

1）手寫超參數(shù)

# 尋找最好的k
best_method=""
best_score=0.0
best_k=-1
# 循環(huán)每一個(gè)K值
for method in["uniform","distance"]:
    for k in range(1,11):
        knn_clf=KNeighborsClassifier(n_neighbors=k,weights=method)
        knn_clf.fit(X_train,y_train)
        score=knn_clf.score(X_test,y_test)
        if score>best_score:
            best_k=k
            best_score=score
            best_method=method
        
print("best_k=:",best_k)
print("best_score=:",best_score)
print("best_method=:",best_method)

運(yùn)行結(jié)果：
best_k=: 1

best_score=: 0.9888888888888889

best_method=: uniform

2）使用sklearn獲取最優(yōu)k值

# 通過(guò)網(wǎng)格方式來(lái)獲取參數(shù) Grid Search
from sklearn.model_selection import GridSearchCV
param_grid=[
    {
        'weights':['uniform'],
        'n_neighbors':[i for i in range(1,11)]
    },
    {
        'weights':['distance'],
        'n_neighbors':[i for i in range(1,11)],
        'p':[i for i in range(1,6)]
    }
]
# 通過(guò)GridSearchCV來(lái)搜索最好的K值
knn_clf_best=KNeighborsClassifier()
grid_Search=GridSearchCV(knn_clf_best,param_grid)
grid_Search.fit(X_train,y_train)
grid_Search.best_estimator_
grid_Search.best_score_
best_score=grid_Search.best_score_
# 輸出最好的參數(shù)以及對(duì)應(yīng)的準(zhǔn)確率
best_score=grid_Search.best_score_
print("最優(yōu)準(zhǔn)確率:",best_score)

運(yùn)行結(jié)果：
最優(yōu)準(zhǔn)確率****: ****0.988****16****9****7****9****81****9****0675

通過(guò)網(wǎng)格方式尋找最優(yōu)k值方法計(jì)算出來(lái)的準(zhǔn)確率為0.9882，對(duì)比上面實(shí)驗(yàn)結(jié)構(gòu)，準(zhǔn)確率有細(xì)微的下降，但這并不代表通過(guò)網(wǎng)格方式來(lái)獲取參數(shù)的方法有問(wèn)題，這兩者的差異只是因?yàn)槟Ｐ驮u(píng)判標(biāo)準(zhǔn)不一致形成的。

三、總結(jié)

1、 KNN算法是最簡(jiǎn)單有效的分類算法，簡(jiǎn)單且容易實(shí)現(xiàn)。當(dāng)訓(xùn)練數(shù)據(jù)集很大時(shí)，需要大量的存儲(chǔ)空間，而且需要計(jì)算待測(cè)樣本和訓(xùn)練數(shù)據(jù)集中所有樣本的距離，所以非常耗時(shí)。

2、 KNN對(duì)于隨機(jī)分布的數(shù)據(jù)集分類效果較差，對(duì)于類內(nèi)間距小，類間間距大的數(shù)據(jù)集分類效果好，而且對(duì)于邊界不規(guī)則的數(shù)據(jù)效果好于線性分類器。

3、KNN對(duì)于樣本不均衡的數(shù)據(jù)效果不好，需要進(jìn)行改進(jìn)。改進(jìn)的方法時(shí)對(duì)k個(gè)近鄰數(shù)據(jù)賦予權(quán)重，比如距離測(cè)試樣本越近，權(quán)重越大。