鄰近算法

?鎖定

本詞條由“科普中國”百科科學(xué)詞條編寫與應(yīng)用工作項目?審核 。 鄰近算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。所謂K最近鄰，就是k個最近的鄰居的意思，說的是每個樣本都可以用它最接近的k個鄰居來代表。 kNN算法的核心思想是如果一個樣本在特征空間中的k個最相鄰的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別，并具有這個類別上樣本的特性。該方法在確定分類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 kNN方法在類別決策時，只與極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，kNN方法較其他方法更為適合。 中文名

k最鄰近分類算法

外文名

k-NearestNeighbor

用????途

用于分類，對未知事物的識別

目錄

1?簡介

2?算法流程

3?優(yōu)點

4?缺點

5?改進策略

簡介

右圖中，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。 KNN算法的決策過程 K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學(xué)習算法之一。該方法的思路是：如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。 KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個樣本的k個最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值與距離成反比。

算法流程

1. 準備數(shù)據(jù)，對數(shù)據(jù)進行預(yù)處理 2. 選用合適的數(shù)據(jù)結(jié)構(gòu)存儲訓(xùn)練數(shù)據(jù)和測試元組 3. 設(shè)定參數(shù)，如k 4.維護一個大小為k的的按距離由大到小的優(yōu)先級隊列，用于存儲最近鄰訓(xùn)練元組。隨機從訓(xùn)練元組中選取k個元組作為初始的最近鄰元組，分別計算測試元組到這k個元組的距離，將訓(xùn)練元組標號和距離存入優(yōu)先級隊列 5. 遍歷訓(xùn)練元組集，計算當前訓(xùn)練元組與測試元組的距離，將所得距離L 與優(yōu)先級隊列中的最大距離Lmax 6. 進行比較。若L>=Lmax，則舍棄該元組，遍歷下一個元組。若L < Lmax，刪除優(yōu)先級隊列中最大距離的元組，將當前訓(xùn)練元組存入優(yōu)先級隊列。 7. 遍歷完畢，計算優(yōu)先級隊列中k 個元組的多數(shù)類，并將其作為測試元組的類別。 8. 測試元組集測試完畢后計算誤差率，繼續(xù)設(shè)定不同的k值重新進行訓(xùn)練，最后取誤差率最小的k 值。[1]

優(yōu)點

1.簡單，易于理解，易于實現(xiàn)，無需估計參數(shù)，無需訓(xùn)練； 2. 適合對稀有事件進行分類； 3.特別適合于多分類問題(multi-modal,對象具有多個類別標簽)， kNN比SVM的表現(xiàn)要好。[1]

缺點

該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。 該算法只計算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標樣本，或者這類樣本很靠近目標樣本。無論怎樣，數(shù)量并不能影響運行結(jié)果。 該方法的另一個不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。 可理解性差，無法給出像決策樹那樣的規(guī)則。[1]

改進策略

kNN算法因其提出時間較早，隨著其他技術(shù)的不斷更新和完善，kNN算法的諸多不足之處也逐漸顯露，因此許多kNN算法的改進算法也應(yīng)運而生。 針對以上算法的不足，算法的改進方向主要分成了分類效率和分類效果兩方面。 分類效率：事先對樣本屬性進行約簡，刪除對分類結(jié)果影響較小的屬性，快速的得出待分類樣本的類別。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。 分類效果：采用權(quán)值的方法（和該樣本距離小的鄰居權(quán)值大）來改進，Han等人于2002年嘗試利用貪心法，針對文件分類實做可調(diào)整權(quán)重的k最近鄰居法WAkNN (weighted adjusted k nearest neighbor)，以促進分類效果；而Li等人于2004年提出由于不同分類的文件本身有數(shù)量上有差異，因此也應(yīng)該依照訓(xùn)練集合中各種分類的文件數(shù)量，選取不同數(shù)目的最近鄰居，來參與分類。

一、算法概述

1、kNN算法又稱為k近鄰分類(k-nearest neighbor classification)算法。
最簡單平凡的分類器也許是那種死記硬背式的分類器，記住所有的訓(xùn)練數(shù)據(jù)，對于新的數(shù)據(jù)則直接和訓(xùn)練數(shù)據(jù)匹配，如果存在相同屬性的訓(xùn)練數(shù)據(jù)，則直接用它的分類來作為新數(shù)據(jù)的分類。這種方式有一個明顯的缺點，那就是很可能無法找到完全匹配的訓(xùn)練記錄。

kNN算法則是從訓(xùn)練集中找到和新數(shù)據(jù)最接近的k條記錄，然后根據(jù)他們的主要分類來決定新數(shù)據(jù)的類別。該算法涉及3個主要因素：訓(xùn)練集、距離或相似的衡量、k的大小。

2、代表論文
Discriminant Adaptive Nearest Neighbor Classification
Trevor Hastie and Rolbert Tibshirani
IEEE TRANSACTIONS ON PAITERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 18, NO. 6, JUNE 1996
http://www.stanford.edu/~hastie/Papers/dann_IEEE.pdf

3、行業(yè)應(yīng)用
客戶流失預(yù)測、欺詐偵測等（更適合于稀有事件的分類問題）

二、算法要點

1、指導(dǎo)思想
kNN算法的指導(dǎo)思想是“近朱者赤，近墨者黑”，由你的鄰居來推斷出你的類別。

計算步驟如下：
????1）算距離：給定測試對象，計算它與訓(xùn)練集中的每個對象的距離
????2）找鄰居：圈定距離最近的k個訓(xùn)練對象，作為測試對象的近鄰
????3）做分類：根據(jù)這k個近鄰歸屬的主要類別，來對測試對象分類

2、距離或相似度的衡量
什么是合適的距離衡量？距離越近應(yīng)該意味著這兩個點屬于一個分類的可能性越大。
覺的距離衡量包括歐式距離、夾角余弦等。
對于文本分類來說，使用余弦(cosine)來計算相似度就比歐式(Euclidean)距離更合適。

3、類別的判定
投票決定：少數(shù)服從多數(shù)，近鄰中哪個類別的點最多就分為該類。
加權(quán)投票法：根據(jù)距離的遠近，對近鄰的投票進行加權(quán)，距離越近則權(quán)重越大（權(quán)重為距離平方的倒數(shù)）

三、優(yōu)缺點

1、優(yōu)點
簡單，易于理解，易于實現(xiàn)，無需估計參數(shù)，無需訓(xùn)練
適合對稀有事件進行分類（例如當流失率很低時，比如低于0.5%，構(gòu)造流失預(yù)測模型）
特別適合于多分類問題(multi-modal,對象具有多個類別標簽)，例如根據(jù)基因特征來判斷其功能分類，kNN比SVM的表現(xiàn)要好

2、缺點
懶惰算法，對測試樣本分類時的計算量大，內(nèi)存開銷大，評分慢
可解釋性較差，無法給出決策樹那樣的規(guī)則。

四、常見問題

1、k值設(shè)定為多大？
k太小，分類結(jié)果易受噪聲點影響；k太大，近鄰中又可能包含太多的其它類別的點。（對距離加權(quán)，可以降低k值設(shè)定的影響）
k值通常是采用交叉檢驗來確定（以k=1為基準）
經(jīng)驗規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根

2、類別如何判定最合適？
投票法沒有考慮近鄰的距離的遠近，距離更近的近鄰也許更應(yīng)該決定最終的分類，所以加權(quán)投票法更恰當一些。

3、如何選擇合適的距離衡量？
高維度對距離衡量的影響：眾所周知當變量數(shù)越多，歐式距離的區(qū)分能力就越差。
變量值域?qū)嚯x的影響：值域越大的變量常常會在距離計算中占據(jù)主導(dǎo)作用，因此應(yīng)先對變量進行標準化。

4、訓(xùn)練樣本是否要一視同仁？
在訓(xùn)練集中，有些樣本可能是更值得依賴的。
可以給不同的樣本施加不同的權(quán)重，加強依賴樣本的權(quán)重，降低不可信賴樣本的影響。

5、性能問題？
kNN是一種懶惰算法，平時不好好學(xué)習，考試（對測試樣本分類）時才臨陣磨槍（臨時去找k個近鄰）。
懶惰的后果：構(gòu)造模型很簡單，但在對測試樣本分類地的系統(tǒng)開銷大，因為要掃描全部訓(xùn)練樣本并計算距離。
已經(jīng)有一些方法提高計算的效率，例如壓縮訓(xùn)練樣本量等。

6、能否大幅減少訓(xùn)練樣本量，同時又保持分類精度？
濃縮技術(shù)(condensing)
編輯技術(shù)(editing)
1. 綜述 1.1 Cover和Hart在1968年提出了最初的鄰近算法 1.2 分類(classification)算法 1.3 輸入基于實例的學(xué)習(instance-based learning), 懶惰學(xué)習(lazy learning)
2. 例子：




3. 算法詳述
3.1 步驟： 為了判斷未知實例的類別，以所有已知類別的實例作為參照 選擇參數(shù)K 計算未知實例與所有已知實例的距離 選擇最近K個已知實例 根據(jù)少數(shù)服從多數(shù)的投票法則(majority-voting)，讓未知實例歸類為K個最鄰近樣本中最多數(shù)的類別
3.2 細節(jié): 關(guān)于K 關(guān)于距離的衡量方法: 3.2.1 Euclidean Distance 定義
未知電影屬于什么類型？
電影屬于什么類型？



4. 算法優(yōu)缺點： 4.1 算法優(yōu)點 簡單 易于理解 容易實現(xiàn) 通過對K的選擇可具備丟噪音數(shù)據(jù)的健壯性 4.2 算法缺點
需要大量空間儲存所有已知實例 算法復(fù)雜度高（需要比較所有已知實例與要分類的實例） 當其樣本分布不平衡時，比如其中一類樣本過大（實例數(shù)量過多）占主導(dǎo)的時候，新的未知實例容易被歸類為這個主導(dǎo)樣本，因為這類樣本實例的數(shù)量過大，但這個新的未知實例實際并木接近目標樣本

5. 改進版本 考慮距離，根據(jù)距離加上權(quán)重 比如: 1/d (d: 距離） 1 數(shù)據(jù)集介紹：
虹膜
150個實例
萼片長度，萼片寬度，花瓣長度，花瓣寬度 (sepal length, sepal width, petal length and petal width）
類別： Iris setosa, Iris versicolor, Iris virginica.
2. 利用Python的機器學(xué)習庫sklearn: SkLearnExample.pyfrom sklearn import neighbors from sklearn import datasetsknn = neighbors.KNeighborsClassifier()iris = datasets.load_iris()print irisknn.fit(iris.data, iris.target)predictedLabel = knn.predict([[0.1, 0.2, 0.3, 0.4]])print predictedLabel3. KNN 實現(xiàn)Implementation:# Example of kNN implemented from Scratch in Pythonimport csv import random import math import operatordef loadDataset(filename, split, trainingSet=[] , testSet=[]):with open(filename, 'rb') as csvfile:lines = csv.reader(csvfile)dataset = list(lines)for x in range(len(dataset)-1):for y in range(4):dataset[x][y] = float(dataset[x][y])if random.random() < split:trainingSet.append(dataset[x])else:testSet.append(dataset[x])def euclideanDistance(instance1, instance2, length):distance = 0for x in range(length):distance += pow((instance1[x] - instance2[x]), 2)return math.sqrt(distance)def getNeighbors(trainingSet, testInstance, k):distances = []length = len(testInstance)-1for x in range(len(trainingSet)):dist = euclideanDistance(testInstance, trainingSet[x], length)distances.append((trainingSet[x], dist))distances.sort(key=operator.itemgetter(1))neighbors = []for x in range(k):neighbors.append(distances[x][0])return neighborsdef getResponse(neighbors):classVotes = {}for x in range(len(neighbors)):response = neighbors[x][-1]if response in classVotes:classVotes[response] += 1else:classVotes[response] = 1sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)return sortedVotes[0][0]def getAccuracy(testSet, predictions):correct = 0for x in range(len(testSet)):if testSet[x][-1] == predictions[x]:correct += 1return (correct/float(len(testSet))) * 100.0def main():# prepare datatrainingSet=[]testSet=[]split = 0.67loadDataset(r'D:\MaiziEdu\DeepLearningBasics_MachineLearning\Datasets\iris.data.txt', split, trainingSet, testSet)print 'Train set: ' + repr(len(trainingSet))print 'Test set: ' + repr(len(testSet))# generate predictionspredictions=[]k = 3for x in range(len(testSet)):neighbors = getNeighbors(trainingSet, testSet[x], k)result = getResponse(neighbors)predictions.append(result)print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))accuracy = getAccuracy(testSet, predictions)print('Accuracy: ' + repr(accuracy) + '%')main()



3.3 舉例

總結(jié)

以上是生活随笔為你收集整理的邻近算法(KNN算法)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。