機器學習-K近鄰(KNN)演算法詳解

一、KNN演算法描述

  KNN（K Near Neighbor）：找到k個最近的鄰居，即每個樣本都可以用它最接近的這k個鄰居中所佔數量最多的類別來代表。KNN演算法屬於有監督學習方式的分類演算法，所謂K近鄰演算法，就是給定一個訓練數據集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的K個實例（就是上面提到的K個鄰居），如果這K個實例的多數屬於某個類，就將該輸入實例分類到這個類中，如下圖所示。

                            

  上圖中有兩種不同類別的樣本數據，分別用藍色正方形和紅色三角形表示，最中間綠色的圓表示的數據則是待分類的數據。我們現在要解決的問題是：不知道中間的圓是屬於哪一類（正方形類還是三角形類）？我們下面就來給圓分類。

  從圖中還能看出：如果K=3，圓的最近的3個鄰居是2個三角形和1個正方形，少數從屬於多數，基於統計的方法，判定圓標示的這個待分類數據屬於三角形一類。但是如果K=5，圓的最近的5個鄰居是2個三角形和3個正方形，還是少數從屬於多數，判定圓標示的這個待分類數據屬於正方形這一類。由此我們可以看到，當無法判定當前待分類數據從屬於已知分類中的哪一類時，可以看它所處的位置特徵，衡量它周圍鄰居的權重，而把它歸為權重更大的一類，這就是K近鄰演算法分類的核心思想。

二、程式碼實現

演算法步驟：

  1. 計算已知類別數據集中的點與當前點之間的距離；
  2. 按照距離遞增依次排序；
  3. 選取與當前點距離最小的K個點；
  4. 確定前k個點所在類別的出現頻率；
  5. 返回前k個點出現頻率最高的類別作為當前點的預測分類
"""
kNN: k Nearest Neighbors

Input:      inX: vector to compare to existing dataset (1xN)
            dataSet: size m data set of known vectors (NxM)
            labels: data set labels (1xM vector)
            k: number of neighbors to use for comparison (should be an odd number)
            
Output:     the most popular class label
"""

from numpy import *
import operator
from os import listdir

def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize,1)) - dataSet #將inX重複成dataSetSize行1列，tile(A,n)，功能是將數組A重複n次，構成一個新的數組
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1) #sum(axis=1)就是將矩陣的每一行向量相加
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort() #argsort()得到的是排序後數據原來位置的下標   
    classCount={}           
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]#確定前k個距離最小元素所在的主要分類labels
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        #計算各個元素標籤的出現次數(頻率)，當voteIlabel在classCount中時，classCount.get()返回1，否則返回0
        #operator.itemgetter(1)表示按照第二個元素的次序對元組進行排序，reverse=True表示為逆序排序，即從大到小排序
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]   #最後返回發生頻率最高的元素標籤

  classify0()函數有4個輸入參數：用於分類的輸入向量是inX，輸入的訓練樣本集為dataSet，標籤向量為labels，最後的參數k表示用於選擇最近鄰居的數目，其中標籤向量的元素數目和矩陣dataSet的行數相同。除了K值之外，kNN演算法的另一個核心參數是距離函數的選擇。上述程式碼使用的是歐式距離，在日常生活中我們所說的距離往往是歐氏距離，也即平面上兩點相連後線段的長度。歐氏距離的定義如下：

                         

除此之外，在機器學習中常見的距離定義有以下幾種：

  • 漢明距離：兩個字元串對應位置不一樣的個數。漢明距離是以理查德·衛斯里·漢明的名字命名的。在資訊理論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。換句話說，它就是將一個字元串變換成另外一個字元串所需要替換的字元個數；

  • 馬氏距離：表示數據的協方差距離。計算兩個樣本集相似度的距離；

  • 餘弦距離：兩個向量的夾角作為一種判別距離的度量；

  • 曼哈頓距離：兩點投影到各軸上的距離總和；

  • 切比雪夫距離：兩點投影到各軸上距離的最大值；

  • 標準化歐氏距離： 歐氏距離里每一項除以標準差。

還有一種距離叫閔可夫斯基距離，如下：

                       

當q為1時，即為曼哈頓距離。當q為2時，即為歐氏距離。

在這裡介紹距離的目的一個是為了讓大家使用k近鄰演算法時，如果發現效果不太好時，可以通過使用不同的距離定義來嘗試改進演算法的性能。

KNN演算法的優缺點

優點：

  1. 理解簡單，數學知識基本為0；

  2. 既能用於分來，又能用於回歸；

  3. 支援多分類。

kNN演算法可以用於回歸，回歸的思路是將離待測點最近的k個點的平均值作為待測點的回歸預測結果。

kNN演算法在測試階段是看離待測點最近的k個點的類別比分，所以不管訓練數據中有多少種類別，都可以通過類別比分來確定待測點類別。

註：當然會有類別比分打平的情況，這種情況下可以看待測點離哪個類別最近，選最近的類別作為待測點的預測類別。

缺點：

當然kNN演算法的缺點也很明顯，就是當訓練集數據量比較大時，預測過程的效率很低。這是因為kNN演算法在預測過程中需要計算待測點與訓練集中所有點的距離並排序。可想而知，當數據量比較大的時候，效率會奇低。對於時間敏感的業務不太適合。

三、使用sklearn進行KNN分類與回歸演算法

1.使用sklearn中的kNN演算法進行分類

sklearn中KNeighborsClassifier的參數

比較常用的參數有以下幾個：

  • n_neighbors，即K近鄰演算法中的K值，為一整數，默認為5；

  • metric，距離函數。參數可以為字元串（預設好的距離函數）或者是callable（可調用對象，大家不明白的可以理解為函數即可）。默認值為閔可夫斯基距離；

  • p，當metric為閔可夫斯基距離公式時，上文中的q值，默認為2。

程式碼實現：

from sklearn.neighbors import KNeighborsClassifier

def classification(train_feature, train_label, test_feature):
    '''
    使用KNeighborsClassifier對test_feature進行分類
    :param train_feature: 訓練集數據
    :param train_label: 訓練集標籤
    :param test_feature: 測試集數據
    :return: 測試集預測結果
    '''

    clf = KNeighborsClassifier()
    clf.fit(train_feature, train_label)
    predict_result = clf.predict(test_feature)
    return predict_result

 

2.使用sklearn中的kNN演算法進行回歸

當我們需要使用kNN演算法進行回歸器時，只需要把KNeighborsClassifier換成KNeighborsRegressor即可。KNeighborsRegressor和KNeighborsClassifier的參數是完全一樣的，所以在優化模型時可以參考上述的內容。

程式碼實現：

from sklearn.neighbors import KNeighborsRegressor

def regression(train_feature, train_label, test_feature):
    '''
    使用KNeighborsRegressor對test_feature進行分類
    :param train_feature: 訓練集數據
    :param train_label: 訓練集標籤
    :param test_feature: 測試集數據
    :return: 測試集預測結果
    '''

    clf = KNeighborsRegressor()
    clf.fit(train_feature, train_label)
    predict_result = clf.predict(test_feature)
    return predict_result

上述為KNN演算法的簡述

VirMach 便宜 VPS

QNews

QNews