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

2、數(shù)據(jù)訓(xùn)練一個模型，然后利用測試數(shù)據(jù)測試其誤差率。,cross-validate,（交叉驗證）誤差統(tǒng)計選擇法就是比較不同,K,值時的交叉驗證平均誤差率，選擇誤,差率最小的那個,K,值。例如選擇,K=1,2,3,.,，,對每個,K=i,做,100,次交叉驗證，計算出平均誤差，,然后比較、選出最小的那個。,?,?,經(jīng)驗規(guī)則：,k,一般低于訓(xùn)練樣本數(shù)的平方根。,需要指出的是：取,k=1,常常會得到比其他值好的結(jié)果，特別是在小,數(shù)據(jù)集中。,?,不過仍然要注意：在樣本充足的情況下，選擇較大的,K,值能提高抗,躁能力。,?,歐氏距離,?,計算距離有許多種不同的方法，如歐氏距離、余弦距離、,漢明距離、曼哈頓距

3、離等等，傳統(tǒng)上，,kNN,算法采用的,是歐式距離。,?,也稱歐幾里得距離，它是一個采用的距離定義，他是在,維空間中兩個點之間的真實距離。,?,d,?,(,x,1,?,x,2,),?,(,y,1,?,y,2,),二維的公式：,2,2,?,計算步驟如下：,?,?,1.,計算未知樣本和每個訓(xùn)練樣本的距離,dist,2.,得到目前,K,個最臨近樣本中的最大距離,maxdist,?,3.,如果,dist,小于,maxdist,，則將該訓(xùn)練樣本作為,K-,最近鄰,樣本,?,4.,重復(fù)步驟,2,、,3,、,4,，直到未知樣本和所有訓(xùn)練樣本的,距離都算完,?,5.,統(tǒng)計,K,個最近鄰樣本中每個類別出現(xiàn)的次數(shù),

4、?,注意：,?,該算法不需要花費時間做模型的構(gòu)建。其他大多數(shù)分類,算法，如決策樹等都需要構(gòu)建模型的階段，而且該階段,非常耗時，但是它們在分類的時候非常省時。,?,類別的判定,?,投票決定,：,少數(shù)服從多數(shù)，近鄰中哪個類別的點最多就,分為該類。,?,如果訓(xùn)練數(shù)據(jù)大部分都屬于某一類，投票算法就有很大問題了。這,時候就需要考慮設(shè)計每個投票者票的權(quán)重了。,?,加權(quán)投票法：,根據(jù)距離的遠(yuǎn)近，對近鄰的投票進(jìn)行加權(quán)，,距離越近則權(quán)重越大（權(quán)重為距離平方的倒數(shù)）,?,若樣本到測試點距離為,d,，則選,1/d,為該鄰居的權(quán)重（也就是得到了,該鄰居所屬類的權(quán)重），接下來統(tǒng)計統(tǒng)計,k,個鄰居所有類標(biāo)簽的權(quán),重和，值

5、最大的那個就是新數(shù)據(jù)點的預(yù)測類標(biāo)簽。,?,示例：,?,?,?,如圖，綠色圓要被決定賦予哪個類，是紅色三角形還是藍(lán)色四方形？,如果,K=3,，由于紅色三角形所占比例為,2/3,，綠色圓將被賦予紅色三,角形那個類，如果,K=5,，由于藍(lán)色四方形比例為,3/5,，因此綠色圓被,賦予藍(lán)色四方形類。,?,優(yōu)缺點,?,1,、優(yōu)點,?,?,簡單，易于理解，易于實現(xiàn)，無需估計參數(shù)，無需訓(xùn)練,適合對稀有事件進(jìn)行分類（例如當(dāng)流失率很低時，比如低于,0.5%,，,構(gòu)造流失預(yù)測模型）,?,特別適合于多分類問題,(multi-modal,對象具有多個類別標(biāo)簽,),，例如,根據(jù)基因特征來判斷其功能分類，,kNN,比,SV

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