最近鄰分類算法

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

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

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

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

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