機器學習筆記——KNN演算法
highlight: github
KNN針對的是分類問題
KNN針對分類問題,通過改變決策規則也可用於迴歸問題。
分類預測規則:一般採用多數表決法或者加權多數表決法
迴歸預測規則:一般採用平均值法或者加權平均值法
定義
K Nearest Neighbor演算法,如果一個樣本在特徵空間中的k個最近似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別,則該樣本也屬於這個類別。
注意:KNN 演算法是有監督學習中的分類演算法,注意與K-means演算法區分
K-means為無監督學習演算法,二者有本質區別,一個是分類,一個是聚類。
核心思想
KNN 的全稱是 K Nearest Neighbors,意思是 K 個最近的鄰居。 KNN 的原理就是當預測一個新的值 x 的時候,根據它距離最近的 K 個點是什麼類別來判斷 x 屬於哪個類別。
以下圖為例,綠色點為要預測的點,不同的K取值將產生不同的結果。
距離計算
要度量空間中點距離的話,有好幾種度量方式,比如常見的曼哈頓距離計算、歐式距離計算等等。不過通常 KNN 演算法中使用的是歐式距離。這裡只是簡單說一下,拿二維平面為例,二維空間兩個點的歐式距離計算公式如下: $$ \rho = \sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}} $$ 拓展到多維空間,則公式變成
$$ d(x, y):=\sqrt{\left(x_{1}-y_{1}\right)^{2}+\left(x_{2}-y_{2}\right)^{2}+\cdots+\left(x_{n}-y_{n}\right)^{2}}=\sqrt{\sum_{i=1}^{n}\left(x_{i}-y_{i}\right)^{2}} . $$ KNN 演算法最簡單粗暴的就是將預測點與所有點距離進行計算,然後儲存並排序,選出前面 K 個值看看哪些類別比較多。但其實也可以通過一些資料結構來輔助,比如最大堆,這裡就不多做介紹,有興趣可以百度最大堆相關資料結構的知識。
K值選擇
- 對於K值的選擇,一般根據樣本分佈選擇一個較小的值,然後通過交叉驗證來選擇一個比較合適的最終值;
- 當選擇比較小的K值的時候,表示使用較小領域中的樣本進行預測,訓練誤差會減小,但是會導致模型變得複雜,容易導致過擬合;
- 當選擇較大的K值的時候,表示使用較大領域中的樣本進行預測,訓練誤差會增大,同時會使模型變得簡單,容易導致欠擬合;
交叉驗證(將樣本資料按照一定比例,拆分出訓練用的資料和驗證用的資料,比如6:4拆分出部分訓練資料和驗證資料),從選取一個較小的 K 值開始,不斷增加 K 的值,然後計算驗證集合的方差,最終找到一個比較合適的 K 值。通過交叉驗證計算方差後你大致會得到下面這樣的圖
這個圖其實很好理解,當你增大 K 的時候,一般錯誤率會先降低,因為有周圍更多的樣本可以借鑑了,分類效果會變好。但注意,和 K-means 不一樣,當 K 值更大的時候,錯誤率會更高。這也很好理解,比如說你一共就35個樣本,當你 K 增大到30的時候,KNN 基本上就沒意義了。
所以選擇 K 點的時候可以選擇一個較大的臨界 K 點,當它繼續增大或減小的時候,錯誤率都會上升,比如圖中的 K=10。
演算法實現
Sklearn KNN引數概述
要使用 Sklearn KNN 演算法進行分類,我們需要先了解 Sklearn KNN 演算法的一些基本引數:
def KNeighborsClassifier(n_neighbors = 5,
weights='uniform',
algorithm = '',
leaf_size = '30',
p = 2,
metric = 'minkowski',
metric_params = None,
n_jobs = None
)
其中:
- n_neighbors:這個值就是指 KNN 中的 “K”了。前面說到過,通過調整 K 值,演算法會有不同的效果。
-
weights(權重):最普遍的 KNN 演算法無論距離如何,權重都一樣,但有時候我們想搞點特殊化,比如距離更近的點讓它更加重要。這時候就需要 weight 這個引數了,這個引數有三個可選引數的值,決定了如何分配權重。引數選項如下:
* ‘uniform’:不管遠近權重都一樣,就是最普通的 KNN 演算法的形式。 * ‘distance’:權重和距離成反比,距離預測目標越近具有越高的權重。 * 自定義函式:自定義一個函式,根據輸入的座標值返回對應的權重,達到自定義權重的目的。
-
algorithm:在 Sklearn 中,要構建 KNN 模型有三種構建方式:
- 暴力法,就是直接計算距離儲存比較的那種方式。
- 使用 Kd 樹構建 KNN 模型。
- 使用球樹構建。
其中暴力法適合資料較小的方式,否則效率會比較低。如果資料量比較大一般會選擇用 Kd 樹構建 KNN 模型,而當 Kd 樹也比較慢的時候,則可以試試球樹來構建 KNN。引數選項如下:
* ‘brute’ :蠻力實現。 * ‘kd_tree’:KD 樹實現 KNN。 * ‘ball_tree’:球樹實現 KNN。 * ‘auto’: 預設引數,自動選擇合適的方法構建模型。
不過當資料較小或比較稀疏時,無論選擇哪個最後都會使用 ‘brute’。
-
leaf_size:如果是選擇蠻力實現,那麼這個值是可以忽略的。當使用 Kd 樹或球樹,它就是停止建子樹的葉子節點數量的閾值。預設30,但如果資料量增多這個引數需要增大,否則速度過慢不說,還容易過擬合。
- p:和 metric 結合使用,當 metric 引數是 “minkowski” 的時候,p=1 為曼哈頓距離, p=2 為歐式距離。預設為p=2。
-
metric:指定距離度量方法,一般都是使用歐式距離。
* ‘euclidean’ :歐式距離。 * ‘manhattan’:曼哈頓距離。 * ‘chebyshev’:切比雪夫距離。 * ‘minkowski’: 閔可夫斯基距離,預設引數。
-
n_jobs:指定多少個CPU進行運算,預設是-1,也就是全部都算。
KNN程式碼示例
Sklearn 鳶尾花
鳶尾花資料集主要包含了鳶尾花的花萼長度、花萼寬度、花瓣長度、花瓣寬度4個屬性(特徵),以及鳶尾花卉屬於『Setosa、Versicolour、Virginica』三個種類中的哪一類。
在使用 KNN 演算法之前,我們要先決定 K 的值是多少。要選出最優的 K 值,可以使用 Sklearn 中的交叉驗證方法,程式碼如下
``` from sklearn.datasets import load_iris from sklearn.model_selection import cross_val_score import matplotlib.pyplot as plt from sklearn.neighbors import KNeighborsClassifier
讀取鳶尾花資料集
iris = load_iris() x = iris.data y = iris.target k_range = range(1, 31) k_error = []
迴圈,取k=1到k=31,檢視誤差效果
for k in k_range: knn = KNeighborsClassifier(n_neighbors=k) #cv引數決定資料集劃分比例,這裡是按照5:1劃分訓練集和測試集 scores = cross_val_score(knn, x, y, cv=6, scoring='accuracy') k_error.append(1 - scores.mean())
畫圖,x軸為k值,y值為誤差值
plt.plot(k_range, k_error) plt.xlabel('Value of K for KNN') plt.ylabel('Error') plt.show() ``` 有了這張圖,我們就能明顯看出 K 值取多少的時候誤差最小,這裡明顯是 K=11 最好。當然在實際問題中,如果資料集比較大,那為減少訓練時間,K 的取值範圍可以縮小。
有了 K 值能執行 KNN 演算法了,具體程式碼如下 ``` import matplotlib.pyplot as plt from numpy import * from matplotlib.colors import ListedColormap from sklearn import neighbors, datasets
n_neighbors = 11
# 匯入一些要玩的資料 iris = datasets.load_iris() x = iris.data[:, :2] # 我們只採用前兩個feature,方便畫圖在二維平面顯示 y = iris.target
h = .02 # 網格中的步長
# 建立彩色的圖 cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA', '#AAAAFF']) cmap_bold = ListedColormap(['#FF0000', '#00FF00', '#0000FF'])
weights是KNN模型中的一個引數,上述引數介紹中有介紹,這裡繪製兩種權重引數下KNN的效果圖
for weights in ['uniform', 'distance']: # 建立了一個knn分類器的例項,並擬合數據 clf = neighbors.KNeighborsClassifier(n_neighbors, weights=weights) clf.fit(x, y)
# 繪製決策邊界,為此,我們將為每個分配一個顏色
# 來繪製網格中的點 [x_min, x_max]x[y_min, y_max].
x_min, x_max = x[:, 0].min() - 1, x[:, 0].max() + 1
y_min, y_max = x[:, 1].min() - 1, x[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
# 將結果放入一個彩色圖中
Z = Z.reshape(xx.shape)
plt.figure()
plt.pcolormesh(xx, yy, Z, cmap=cmap_light)
# 繪製訓練點
plt.scatter(x[:, 0], x[:, 1], c=y, cmap=cmap_bold)
plt.xlim(xx.min(), xx.max())
plt.ylim(yy.min(), yy.max())
plt.title("3-Class classification (k = %i, weights = '%s')" % (n_neighbors, weights))
plt.show() ```
演算法特點
KNN是一種非參的、惰性的演算法模型。
非參的意思並不是說這個演算法不需要引數,而是意味著這個模型不會對資料做出任何的假設,與之相對的是線性迴歸(我們總會假設線性迴歸是一條直線)。也就是說 KNN 建立的模型結構是根據資料來決定的,這也比較符合現實的情況,畢竟在現實中的情況往往與理論上的假設是不相符的。
惰性又是什麼意思呢?想想看,同樣是分類演算法,邏輯迴歸需要先對資料進行大量訓練(tranning),最後才會得到一個演算法模型。而 KNN 演算法卻不需要,它沒有明確的訓練資料的過程,或者說這個過程很快。
演算法優缺點
優點
- 簡單易用。相比其他演算法,KNN 算是比較簡潔明瞭的演算法,即使沒有很高的數學基礎也能搞清楚它的原理。
- 模型訓練時間快,上面說到 KNN 演算法是惰性的,這裡也就不再過多講述。
- 預測效果好。
- 對異常值不敏感。
缺點
- 對記憶體要求較高,因為該演算法儲存了所有訓練資料。
- 預測階段可能很慢。
- 對不相關的功能和資料規模敏感。