knn聚類算法基礎(chǔ)知識(shí)

1、Knn(K最近鄰分類算法)1.簡介:鄰近算法，或者說K最近鄰(kNN，k-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡單的方法之一。所謂K最近鄰，就是k個(gè)最近的鄰居的意思，說的是每個(gè)樣本都可以用它最接近的k個(gè)鄰居來代表。2.算法核心:kNN算法的核心思想是如果一個(gè)樣本在特征空間中的k個(gè)最相鄰的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別，并具有這個(gè)類別上樣本的特性。該方法在確定分類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 kNN方法在類別決策時(shí)，只及極少量的相鄰樣本有關(guān)。由于kNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確

2、定所屬類別的，因此對(duì)于類域 的交叉或重疊較多的待分樣本集來說，kNN方法較其他方法更為適合。3.例子:上圖中，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。4.算法核心思想:K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個(gè)理論上比較成熟的方法，也是最簡單的機(jī)器學(xué)習(xí)算法之一。該方法的思路是：如果一個(gè)樣本在特征空間中的k個(gè)最相 似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。KNN算法中，所

3、選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在定類決 策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。 KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只及極少量的相鄰樣本有關(guān)。由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方 法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。另外, KNN算法不僅可以用于分類，還可以用于回歸。通過找出一個(gè)樣本的k個(gè)最近鄰居，將這些鄰居的屬性的平均值賦給該樣本，就可以得到該樣本的屬性。更有用的方法是將不同距離的鄰居對(duì)該樣本產(chǎn)生的影響給予不同的權(quán)值(weight)，如權(quán)值及距離成反

4、比。5優(yōu)點(diǎn):1).簡單，易于理解，易于實(shí)現(xiàn)，無需估計(jì)參數(shù)，無需訓(xùn)練；2). 適合對(duì)稀有事件進(jìn)行分類；3).特別適合于多分類問題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)， kNN比SVM的表現(xiàn)要好。6.缺點(diǎn):該算法在分類時(shí)有個(gè)主要的不足是，當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很 大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。 該算法只計(jì)算“最近的”鄰居樣本，某一類的樣本數(shù)量很大，那么或者這類樣本并不接近目標(biāo)樣本，或者這類樣本很靠近目標(biāo)樣本。無論怎樣，數(shù)量并不能影響運(yùn)行 結(jié)果。該方法的另一個(gè)不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要

5、計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。可理解性差，無法給出像決策樹那樣的規(guī)則。7.算法流程:step.1-初始化距離為最大值step.2-計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離diststep.3-得到目前K個(gè)最臨近樣本中的最大距離maxdiststep.4-如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本step.5-重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離都算完step.6-統(tǒng)計(jì)K-最近鄰樣本中每個(gè)類標(biāo)號(hào)出現(xiàn)的次數(shù)step.7-選擇出現(xiàn)頻率最大的類標(biāo)號(hào)作為未知樣本的類標(biāo)號(hào)二、常見問題1、k值設(shè)定為多大？k太小，分類結(jié)果易受噪聲點(diǎn)影響；k太大，近鄰中又可

6、能包含太多的其它類別的點(diǎn)。（對(duì)距離加權(quán)，可以降低k值設(shè)定的影響）k值通常是采用交叉檢驗(yàn)來確定（以k=1為基準(zhǔn)）經(jīng)驗(yàn)規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根2、類別如何判定最合適？投票法沒有考慮近鄰的距離的遠(yuǎn)近，距離更近的近鄰也許更應(yīng)該決定最終的分類，所以加權(quán)投票法更恰當(dāng)一些。3、如何選擇合適的距離衡量？高維度對(duì)距離衡量的影響：眾所周知當(dāng)變量數(shù)越多，歐式距離的區(qū)分能力就越差。變量值域?qū)嚯x的影響：值域越大的變量常常會(huì)在距離計(jì)算中占據(jù)主導(dǎo)作用，因此應(yīng)先對(duì)變量進(jìn)行標(biāo)準(zhǔn)化。4、訓(xùn)練樣本是否要一視同仁？在訓(xùn)練集中，有些樣本可能是更值得依賴的。可以給不同的樣本施加不同的權(quán)重，加強(qiáng)依賴樣本的權(quán)重，降低不可信賴樣本的影響。5、性能問題？kNN是一種懶惰算法，平時(shí)不好好學(xué)習(xí)，考試（對(duì)測(cè)試樣本分類）時(shí)才臨陣磨槍（臨時(shí)去找k個(gè)近鄰）。懶惰的后果：構(gòu)造模型很簡單，但在對(duì)測(cè)試樣本分類地的系統(tǒng)開銷大，因?yàn)?/p>