最近鄰分類算法

——K最近鄰分類(KNN)數(shù)據(jù)挖掘算法K最近鄰分類（KNN）該方法的思路是：如果一個樣本在特征空間中的k個最相近(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。即—“近朱者赤，近墨者黑”，由你的鄰居來推斷出你的類別。用下面的諺語最能說明：“如果走像鴨子，叫像鴨子，看起來還像鴨子，那么它很可能就是一只鴨子?！盞值選取k值通常是采用交叉檢驗來確定（以k=1為基準）交叉驗證的概念：將數(shù)據(jù)樣本的一部分作為訓練樣本，一部分作為測試樣本，比如選擇95%作為訓練樣本，剩下的用作測試樣本。通過訓練數(shù)據(jù)訓練一個模型，然后利用測試數(shù)據(jù)測試其誤差率。cross-validate（交叉驗證）誤差統(tǒng)計選擇法就是比較不同K值時的交叉驗證平均誤差率，選擇誤差率最小的那個K值。例如選擇K=1,2,3,...，對每個K=i做100次交叉驗證，計算出平均誤差，然后比較、選出最小的那個。經(jīng)驗規(guī)則：k一般低于訓練樣本數(shù)的平方根。需要指出的是：取k=1常常會得到比其他值好的結果，特別是在小數(shù)據(jù)集中。不過仍然要注意：在樣本充足的情況下，選擇較大的K值能提高抗躁能力。歐氏距離計算距離有許多種不同的方法，如歐氏距離、余弦距離、漢明距離、曼哈頓距離等等，傳統(tǒng)上，kNN算法采用的是歐式距離。也稱歐幾里得距離，它是一個采用的距離定義，他是在維空間中兩個點之間的真實距離。二維的公式：

計算步驟如下：1.計算未知樣本和每個訓練樣本的距離dist2.得到目前K個最臨近樣本中的最大距離maxdist3.如果dist小于maxdist，則將該訓練樣本作為K-最近鄰樣本4.重復步驟2、3、4，直到未知樣本和所有訓練樣本的距離都算完5.統(tǒng)計K個最近鄰樣本中每個類別出現(xiàn)的次數(shù)6.選擇出現(xiàn)頻率最大的類別作為未知樣本的類別注意：該算法不需要花費時間做模型的構建。其他大多數(shù)分類算法，如決策樹等都需要構建模型的階段，而且該階段非常耗時，但是它們在分類的時候非常省時。類別的判定投票決定：少數(shù)服從多數(shù)，近鄰中哪個類別的點最多就分為該類。如果訓練數(shù)據(jù)大部分都屬于某一類，投票算法就有很大問題了。這時候就需要考慮設計每個投票者票的權重了。加權投票法：根據(jù)距離的遠近，對近鄰的投票進行加權，距離越近則權重越大（權重為距離平方的倒數(shù)）若樣本到測試點距離為d，則選1/d為該鄰居的權重（也就是得到了該鄰居所屬類的權重），接下來統(tǒng)計統(tǒng)計k個鄰居所有類標簽的權重和，值最大的那個就是新數(shù)據(jù)點的預測類標簽。示例：

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