最近鄰分類算法

1、 K最近鄰分類(KNN)數(shù)據(jù)挖掘算法 K最近鄰分類（KNN）Y該方法的思路是：如果一個樣本在特征空間中的k個最相近(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。即“近朱者赤，近墨者黑”，由你的鄰居來推斷出你的類別。Y用下面的諺語最能說明：“如果走像鴨子，叫像鴨子，看起來還像鴨子，那么它很可能就是一只鴨子?！?K值選取Yk值通常是采用交叉檢驗來確定（以k=1為基準）Y交叉驗證的概念：將數(shù)據(jù)樣本的一部分作為訓(xùn)練樣本，一部分作為測試樣本，比如選擇95%作為訓(xùn)練樣本，剩下的用作測試樣本。通過訓(xùn)練數(shù)據(jù)訓(xùn)練一個模型，然后利用測試數(shù)據(jù)測試其誤差率。 cross-validat

2、e（交叉驗證）誤差統(tǒng)計選擇法就是比較不同K值時的交叉驗證平均誤差率，選擇誤差率最小的那個K值。例如選擇K=1,2,3,. ， 對每個K=i做100次交叉驗證，計算出平均誤差，然后比較、選出最小的那個。Y經(jīng)驗規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根。Y需要指出的是：取k=1常常會得到比其他值好的結(jié)果，特別是在小數(shù)據(jù)集中。Y不過仍然要注意：在樣本充足的情況下，選擇較大的K值能提高抗躁能力。 歐氏距離Y計算距離有許多種不同的方法，如歐氏距離、余弦距離、漢明距離、曼哈頓距離等等，傳統(tǒng)上，kNN算法采用的是歐式距離。Y也稱歐幾里得距離，它是一個采用的距離定義，他是在維空間中兩個點之間的真實距離。Y二維的公式：

3、 221212() ()dx xy y 計算步驟如下：Y1.計算未知樣本和每個訓(xùn)練樣本的距離distY2.得到目前K個最臨近樣本中的最大距離maxdistY3.如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本Y4.重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離都算完 Y5.統(tǒng)計K個最近鄰樣本中每個類別出現(xiàn)的次數(shù)Y6.選擇出現(xiàn)頻率最大的類別作為未知樣本的類別Y注意：注意：Y該算法不需要花費時間做模型的構(gòu)建。其他大多數(shù)分類算法，如決策樹等都需要構(gòu)建模型的階段，而且該階段非常耗時，但是它們在分類的時候非常省時。 類別的判定Y投票決定：少數(shù)服從多數(shù)，近鄰中哪個類別的點最多就分為該

4、類。Y如果訓(xùn)練數(shù)據(jù)大部分都屬于某一類，投票算法就有很大問題了。這時候就需要考慮設(shè)計每個投票者票的權(quán)重了。Y加權(quán)投票法：根據(jù)距離的遠近，對近鄰的投票進行加權(quán)，距離越近則權(quán)重越大（權(quán)重為距離平方的倒數(shù)）Y若樣本到測試點距離為d，則選1/d為該鄰居的權(quán)重（也就是得到了該鄰居所屬類的權(quán)重），接下來統(tǒng)計統(tǒng)計k個鄰居所有類標簽的權(quán)重和，值最大的那個就是新數(shù)據(jù)點的預(yù)測類標簽。 示例：Y Y如圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍色四方形？Y如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個類，如果K=5，由于藍色四方形比例為3/5，因此綠色圓被賦予藍色四方形類。 優(yōu)缺點Y1、

5、優(yōu)點、優(yōu)點Y簡單，易于理解，易于實現(xiàn)，無需估計參數(shù)，無需訓(xùn)練Y適合對稀有事件進行分類（例如當流失率很低時，比如低于0.5%，構(gòu)造流失預(yù)測模型）Y特別適合于多分類問題(multi-modal,對象具有多個類別標簽)，例如根據(jù)基因特征來判斷其功能分類，kNN比SVM的表現(xiàn)要好Y對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。 優(yōu)缺點Y2、缺點、缺點Y懶惰算法，就是說直到預(yù)測階段采取處理訓(xùn)練數(shù)據(jù)。Y對測試樣本分類時的計算量大，內(nèi)存開銷大，評分慢。Y可解釋性較差，無法給出決策樹那樣的規(guī)則。Y由于沒有涉及抽象過程，kNN實際上并沒有創(chuàng)建一個模型，預(yù)測時間較長。Y該算法在分類時有個主要的不足是，當樣本不平衡時，如一個類的樣本容量很大，而其他類樣本容量很小時，有可能導(dǎo)致當輸入一個新樣本時，該樣本的K個鄰居中大容量類的樣本占多數(shù)。 改進Y分組快速搜索近鄰法分組快速搜索近鄰法Y其基本思想是：將樣本集按近鄰關(guān)系分解成組，給出每組質(zhì)心的位置，以質(zhì)心作為代表點，和未知樣本計算距離，選出距離最近的一個或若干個組，再在組的范圍內(nèi)應(yīng)用一般的knn算法。由于并不是將未知樣本與所有樣本計算距離，故該改進算法可以減少計算量，但并不能減少存儲量 行業(yè)應(yīng)用Y客戶流失預(yù)測、欺詐偵測等（更適合于稀有事件的分類問題）