KNN算法課案-算法課案

KNN:K最近鄰分類(fēnlèi)算法K-NearestNeighborClassification第一頁，共44頁。數(shù)據(jù)挖掘十大算法(suànfǎ)KNNC4.5K-MeansSVMAprioriEMPageRankAdaBoostNaiveBayesCART第二頁，共44頁。分類(fēnlèi)輸入數(shù)據(jù)是記錄的集合。每條記錄也稱為樣本或樣例，用元組（x，y）表示。x是屬性集合，y是類標(biāo)號(hào)（分類屬性或目標(biāo)屬性）。類標(biāo)號(hào)是離散的。（回歸的目標(biāo)屬性y是連續(xù)(liánxù)的）分類：通過學(xué)習(xí)得到一個(gè)目標(biāo)函數(shù)（分類函數(shù)）f，把每個(gè)屬性集x映射到一個(gè)預(yù)先定義的類標(biāo)號(hào)y。分類任務(wù)：確定對象屬于哪個(gè)預(yù)定義的目標(biāo)類。脊椎動(dòng)物的數(shù)據(jù)表名字體溫冬眠有腿胎生類標(biāo)號(hào)人類恒溫否是是哺乳類蝙蝠恒溫是是是哺乳類青蛙冷血是是否兩棲類蟒蛇冷血是否否爬行類第三頁，共44頁。分類(fēnlèi)第四頁，共44頁。分類(fēnlèi)第五頁，共44頁。分類(fēnlèi)性能預(yù)測的類類=1類=0實(shí)際的類類=1f11f10類=0f01f00使用性能度量來衡量分類模型性能的信息，如準(zhǔn)確率和錯(cuò)誤率。準(zhǔn)確率=正確預(yù)測數(shù)/預(yù)測總數(shù)(zǒngshù)=（f11+f00）/（f11+f10+f01+f00）錯(cuò)誤率=錯(cuò)誤預(yù)測數(shù)/預(yù)測總數(shù)(zǒngshù)=（f10+f01）/（f11+f10+f01+f00）表1二類問題(wèntí)的混淆矩陣第六頁，共44頁。KNN算法(suànfǎ)怎么來的？第七頁，共44頁。KNN算法(suànfǎ)是怎么來的電影名稱打斗次數(shù)接吻次數(shù)電影類型CaliforniaMan

3104RomanceHe’sNotReallyintoDudes

2100RomanceBeautifulWoman

181RomanceKevinLongblade

10110ActionRoboSlayer3000

995ActionAmpedII

982Action未知1890Unknown猜猜看：最后(zuìhòu)一行未知電影屬于什么類型的電影。第八頁，共44頁。KNN算法(suànfǎ)是怎么來的點(diǎn)X坐標(biāo)Y坐標(biāo)點(diǎn)類型A點(diǎn)

3104RomanceB點(diǎn)

2100RomanceC點(diǎn)

181RomanceD點(diǎn)

10110ActionE點(diǎn)

995ActionF點(diǎn)

982ActionG點(diǎn)1890Unknown猜猜看：最后一行(yīxíng)未知點(diǎn)屬于什么類型的點(diǎn)。第九頁，共44頁。最近(zuìjìn)鄰算法由此，我們引出最近鄰算法的定義：為了(wèile)判定未知樣本的類別，以全部訓(xùn)練樣本作為代表點(diǎn)，計(jì)算未知樣本與所有訓(xùn)練樣本的距離，并以最近鄰者的類別作為決策未知樣本類別的唯一依據(jù)。最近鄰算法的缺陷——對噪聲數(shù)據(jù)過于敏感，為了(wèile)解決這個(gè)問題，我們可以把未知樣本周邊的多個(gè)最近樣本計(jì)算在內(nèi)，擴(kuò)大參與決策的樣本量，以避免個(gè)別數(shù)據(jù)直接決定決策結(jié)果。由此，引進(jìn)K-近鄰（knearestneighbor）算法。第十頁，共44頁。KNN算法(suànfǎ)是用來干什么的K-最近鄰算法是最近鄰算法的一個(gè)延伸?；舅悸肥牵哼x擇距離未知樣本最近的K個(gè)樣本，該K個(gè)樣本大多數(shù)屬于某一類型，則未知樣本判定為該類型。問題：有一個(gè)未知形狀X(圖中綠色(lǜsè)的圓點(diǎn))，如何判斷X是什么形狀?右圖中，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于(yóuyú)紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5，由于(yóuyú)藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。第十一頁，共44頁。KNN算法基本(jīběn)描述k-近鄰法:基本規(guī)則是，在所有N個(gè)樣本中,找到測試樣本的k(k<=N)個(gè)最近鄰者，當(dāng)k=1時(shí)，knn問題就變成了最近鄰問題。其中各類別所占個(gè)數(shù)表示成ki,i＝1，…，c。定義判別函數(shù)為：

gi(x)=ki,i=1,2,…,c。k-近鄰一般(yībān)采用k為奇數(shù)，跟投票表決一樣，避免因兩種票數(shù)相等而難以決策。多數(shù)表決決策規(guī)則為：計(jì)算步驟如下：

1）算距離：給定測試對象，計(jì)算它與訓(xùn)練(xùnliàn)集中的每個(gè)對象的距離

2）找鄰居：圈定距離最近的k個(gè)訓(xùn)練(xùnliàn)對象，作為測試對象的近鄰

3）做分類：根據(jù)這k個(gè)近鄰歸屬的主要類別，來對測試對象分類

第十二頁，共44頁。距離(jùlí)度量KNN算法中，距離如何定義？就是如何度量鄰居之間的相識(shí)度，也就是如何選取鄰居的問題，我們知道相似性的度量方式在很大程度上決定了選取鄰居的準(zhǔn)確性，也決定了分類的效果(xiàoguǒ)，因?yàn)榕卸ㄒ粋€(gè)樣本點(diǎn)的類別是要利用到它的鄰居的，如果鄰居都沒選好，準(zhǔn)確性就無從談起。因此我們需要用一個(gè)量來定量的描述鄰居之間的距離，也可以形象的表述為鄰居之間的相似度，具體的距離度量方式有很多，不同的場合使用哪種需要根據(jù)不同問題具體探討，如文本類型，一般用余弦相似度。

第十三頁，共44頁。距離(jùlí)度量曼哈頓距離(ManhattanDistance)

從名字就可以猜出這種距離的計(jì)算方法了。想象你在曼哈頓要從一個(gè)十字路口開車到另外一個(gè)十字路口，駕駛距離是兩點(diǎn)間的直線距離嗎？顯然不是，除非你能穿越大樓。實(shí)際(shíjì)駕駛距離就是這個(gè)“曼哈頓距離”。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區(qū)距離(CityBlockdistance)。兩個(gè)n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的曼哈頓距離

第十四頁，共44頁。距離(jùlí)度量

歐氏距離(EuclideanDistance)

歐氏距離是最易于理解的一種距離計(jì)算方法，源自歐氏空間(kōngjiān)中兩點(diǎn)間的距離公式。

兩個(gè)n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的歐氏距離：第十五頁，共44頁。距離(jùlí)度量切比雪夫距離

(ChebyshevDistance)

國際象棋的玩法。國王走一步能夠移動(dòng)到相鄰的8個(gè)方格中的任意一個(gè)。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你會(huì)發(fā)現(xiàn)最少步數(shù)總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法(fāngfǎ)叫切比雪夫距離。

兩個(gè)n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的切比雪夫距離

這個(gè)公式的另一種等價(jià)形式是

第十六頁，共44頁。距離(jùlí)度量閔可夫斯基距離(MinkowskiDistance)閔氏距離不是一種距離，而是一組距離的定義。閔氏距離的定義

兩個(gè)n維變量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的閔可夫斯基距離定義為：其中p是一個(gè)變參數(shù)。當(dāng)p=1時(shí)，就是曼哈頓距離當(dāng)p=2時(shí)，就是歐氏距離當(dāng)p→∞時(shí)，就是切比雪夫距離

根據(jù)變參數(shù)的不同，閔氏距離可以(kěyǐ)表示一類的距離。第十七頁，共44頁。KNN算法的實(shí)現(xiàn)(shíxiàn)步驟算法(suànfǎ)步驟：1：令k是最近鄰數(shù)目，D是訓(xùn)練樣例的集合2：for每個(gè)測試樣例zdo3：計(jì)算z和每個(gè)訓(xùn)練樣例之間的距離d4：對d進(jìn)行升序排序5：取前k個(gè)訓(xùn)練樣例的集合6：統(tǒng)計(jì)K個(gè)最近鄰樣本中每個(gè)類別出現(xiàn)的次數(shù)7：選擇出現(xiàn)頻率最大的類別作為未知樣本的類別8：endfor第十八頁，共44頁。KNN算法(suànfǎ)MATLAB%KNNclassifiers,%trainingistrainingset,testingistestset,%Disthedistance,D=1is曼哈頓距離;D=2is歐氏距離；D=3是切比雪夫%距離%Kisthenumberofselectedneighborsfunctionlabel=KNN(training,testing,D,K)[row,column]=size(training)；%%%row行（樣本），column列（屬性(shǔxìng)）[row1,column1]=size(testing);%計(jì)算測試集與訓(xùn)練集的距離第十九頁，共44頁。KNN算法(suànfǎ)MATLAB%數(shù)據(jù)標(biāo)準(zhǔn)化Tr_m=min(training);%%%每列（屬性(shǔxìng)）取最小值，得到一個(gè)行向量Tr_s=max(training);%%%每列（屬性(shǔxìng)）取最大值，得到一個(gè)行向量Tr=[];Te=[];fori=1:(column-1)%%%最后一列是類標(biāo)號(hào)Tr_mi=(training(:,i)-Tr_m(i))/Tr_s(i);%%每列中的數(shù)據(jù)減該列最小值，再除以該列最大值Te_mi=(testing(:,i)-Tr_m(i))/Tr_s(i);Tr=[Tr,Tr_mi];Te=[Te,Te_mi];endtraining=[Tr,training(:,column)];%%%加上類標(biāo)號(hào)testing=Te;%%%training比testing多一列類標(biāo)號(hào)第二十頁，共44頁。KNN算法(suànfǎ)MATLAB%%%%%計(jì)算距離%%D=1曼哈頓距離%%%%%%%%%%%%%%%%distance=[];ifD==1fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]‘;%%變?yōu)閮蓚€(gè)列向量d=mandist(temp);%%%mandist函數(shù)(hánshù)求曼哈頓距離distance(i,j)=d(1,2);%%兩個(gè)列向量求mandist，得出endendend第二十一頁，共44頁。KNN算法(suànfǎ)MATLAB%%%%%計(jì)算(jìsuàn)歐幾里得距離%%%%%%%%%%%%%%%%%%ifD==2fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]';d=dist(temp);%%%%dist函數(shù)計(jì)算(jìsuàn)距離distance(i,j)=d(1,2);endendend第二十二頁，共44頁。KNN算法(suànfǎ)MATLAB%%%%%計(jì)算(jìsuàn)切比雪夫距離%%%%%%%%%%%%%%%%%%ifD==3fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)];%%兩個(gè)行向量d=max(abs(temp(1,:)-temp(2,:)));%%兩個(gè)行向量求距離distance(i,j)=d;endendend第二十三頁，共44頁。KNN算法(suànfǎ)MATLAB%%%%尋找k個(gè)近鄰%%%%算法核心部分%%%%%%%%%%%%%%label=[];fori=1:row1[a,b]=sort(distance(i,:));%%針對第i個(gè)測試樣本與所有訓(xùn)練樣本的距離，進(jìn)行升序排序，距離越小，離的越近，a返回(fǎnhuí)排序后的距離，b返回(fǎnhuí)排序后的下標(biāo)neighbors=b(1:K)‘;%%選取前k個(gè)下標(biāo)neighbors_D=training(neighbors,column);%%對應(yīng)下標(biāo)找到k個(gè)類標(biāo)號(hào)[x,y]=sort(neighbors_D);%對K個(gè)類標(biāo)號(hào)排序，x返回(fǎnhuí)類標(biāo)號(hào)，y返回(fǎnhuí)下標(biāo)temp=find(diff(x)~=0);nei_d=[x(1);x(temp+1)];%對前k個(gè)樣本的標(biāo)簽進(jìn)行分類第二十四頁，共44頁。KNN算法(suànfǎ)MATLABNum_D=[];forj=1:length(nei_d)num=length(find(neighbors_D==nei_d(j)));Num_D=[Num_D,num];end%%%%%計(jì)算(jìsuàn)樣本的類別號(hào)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%[a,b]=max(Num_D);%取標(biāo)簽較多的那個(gè)類作為測試樣本的類別label(i)=nei_d(b);end%label=label';

第二十五頁，共44頁。KNN算法(suànfǎ)的缺陷觀察下面的例子，我們看到，對于未知樣本X，通過KNN算法，我們顯然可以(kěyǐ)得到X應(yīng)屬于紅點(diǎn)，但對于未知樣本Y，通過KNN算法我們似乎得到了Y應(yīng)屬于藍(lán)點(diǎn)的結(jié)論，而這個(gè)結(jié)論直觀來看并沒有說服力。第二十六頁，共44頁。KNN算法的具體(jùtǐ)實(shí)現(xiàn)由上面的例子可見：該算法在分類時(shí)有個(gè)重要的不足是，當(dāng)樣本不平衡時(shí)，即：一個(gè)類的樣本容量很大，而其他類樣本數(shù)量很小時(shí)，很有可能導(dǎo)致當(dāng)輸入一個(gè)未知樣本z=(x’,y’)時(shí)，該樣本的K個(gè)鄰居中大數(shù)量類的樣本占多數(shù)。但是這類樣本并不接近目標(biāo)樣本，而數(shù)量小的這類樣本很靠近目標(biāo)樣本。這個(gè)時(shí)候，我們有理由認(rèn)為該未知樣本屬于數(shù)量小的樣本所屬的一類，但是，KNN卻不關(guān)心這個(gè)問題，它只關(guān)心哪類樣本的數(shù)量最多，而不去把距離遠(yuǎn)近考慮在內(nèi)，因此(yīncǐ)，我們可以采用權(quán)值的方法來改進(jìn)。和該樣本距離小的鄰居權(quán)值大，和該樣本距離大的鄰居權(quán)值則相對較小，由此，將距離遠(yuǎn)近的因素也考慮在內(nèi)，避免因一個(gè)樣本過大導(dǎo)致誤判的情況。距離加權(quán)表決：第二十七頁，共44頁。KNN算法(suànfǎ)的缺陷 從算法實(shí)現(xiàn)的過程大家可以發(fā)現(xiàn)，該算法存兩個(gè)嚴(yán)重的問題，第一個(gè)是需要存儲(chǔ)全部(quánbù)的訓(xùn)練樣本，第二個(gè)是需要進(jìn)行繁重的距離計(jì)算量。對此，提出以下應(yīng)對策略。兩類改進(jìn)的方法：一種是對樣本集進(jìn)行組織與整理，分群分層，盡可能將計(jì)算壓縮到在接近測試樣本鄰域的小范圍內(nèi)，避免盲目地與訓(xùn)練樣本集中每個(gè)樣本進(jìn)行距離計(jì)算。另一種則是在原有樣本集中挑選出對分類計(jì)算有效的樣本，使樣本總數(shù)合理地減少，以同時(shí)達(dá)到既減少計(jì)算量，又減少存儲(chǔ)量的雙重效果。

第二十八頁，共44頁。KNN算法(suànfǎ)的改進(jìn)：分組快速搜索近鄰法 其基本思想是：將樣本集按近鄰關(guān)系分解成組，給出每組質(zhì)心的位置，以質(zhì)心作為代表點(diǎn)，和未知樣本計(jì)算距離(jùlí)，選出距離(jùlí)最近的一個(gè)或若干個(gè)組，再在組的范圍內(nèi)應(yīng)用一般的knn算法。由于并不是將未知樣本與所有樣本計(jì)算距離(jùlí)，故該改進(jìn)算法可以減少計(jì)算量。第二十九頁，共44頁。KNN算法的改進(jìn)：壓縮(yāsuō)近鄰算法 利用現(xiàn)在的樣本集，采取一定(yīdìng)的算法產(chǎn)生一個(gè)新的樣本集，該樣本集擁有比原樣本集少的多的樣本數(shù)量，但仍然保持有對未知樣本進(jìn)行分類的能力。 基本思路：定義兩個(gè)存儲(chǔ)器，一個(gè)用來存放生成的樣本集，稱為output樣本集；另一個(gè)用來存放原來的樣本集，稱為original樣本集。 1.初始化：output樣本集為空集，原樣本集存入original樣本集，從original樣本集中任意選擇一個(gè)樣本移動(dòng)到output樣本集中； 2.在original樣本集中選擇第i個(gè)樣本，并使用output樣本集中的樣本對其進(jìn)行最近鄰算法分類，若分類錯(cuò)誤，則將該樣本移動(dòng)到output樣本集中，若分類正確，不做任何處理； 3.重復(fù)2步驟，直至遍歷完original樣本集中的所有樣本，output樣本集即為壓縮后的樣本集。 通過這種方式也能減少算法的計(jì)算量。第三十頁，共44頁。KNN算法(suànfǎ)幾大問題1、k值設(shè)定為多大？

k太小，分類結(jié)果易受噪聲(zàoshēng)點(diǎn)影響；k太大，近鄰中又可能包含太多的其它類別的點(diǎn)。k值通常是采用交叉檢驗(yàn)來確定。經(jīng)驗(yàn)規(guī)則：k一般低于訓(xùn)練樣本數(shù)的平方根

第三十一頁，共44頁。KNN算法(suànfǎ)幾大問題2、類別如何判定最合適？

投票法沒有考慮近鄰的距離的遠(yuǎn)近，距離更近的近鄰也許更應(yīng)該決定最終的分類，所以加權(quán)投票法更恰當(dāng)一些。3、如何選擇合適的距離衡量？

高維度對距離衡量的影響：眾所周知當(dāng)變量數(shù)越多，歐式距離的區(qū)分能力就越差。變量值域?qū)嚯x的影響：值域越大的變量常常會(huì)在距離計(jì)算中占據(jù)主導(dǎo)作用，因此應(yīng)先對變量進(jìn)行標(biāo)準(zhǔn)化。

4、訓(xùn)練樣本是否要一視同仁？

在訓(xùn)練集中，有些樣本可能是更值得依賴的?？梢越o不同的樣本施加不同的權(quán)重，加強(qiáng)(jiāqiáng)依賴樣本的權(quán)重，降低不可信賴樣本的影響。

第三十二頁，共44頁。分類學(xué)習(xí)(xuéxí)算法的種類積極學(xué)習(xí)法(決策樹歸納)：先根據(jù)訓(xùn)練集構(gòu)造出分類(fēnlèi)模型，根據(jù)分類(fēnlèi)模型對測試集分類(fēnlèi)。5、性能問題？

kNN是一種懶惰算法，平時(shí)不好好學(xué)習(xí)，考試(kǎoshì)（對測試樣本分類）時(shí)才臨陣磨槍（臨時(shí)去找k個(gè)近鄰）。消極學(xué)習(xí)法(基于實(shí)例的學(xué)習(xí)法):推遲建模，當(dāng)給定訓(xùn)練元組時(shí)，簡單地存儲(chǔ)訓(xùn)練數(shù)據(jù)(或稍加處理)，一直等到給定一個(gè)測試元組。消極學(xué)習(xí)法在提供訓(xùn)練元組時(shí)只做少量工作，而在分類或預(yù)測時(shí)做更多的工作。懶惰的后果：構(gòu)造模型很簡單，但在對測試樣本分類地的系統(tǒng)開銷大，因?yàn)橐獟呙枞坑?xùn)練樣本并計(jì)算距離。

第三十三頁，共44頁。Multi-LabelLearning(MLL)Multi-labelobjectsareubiquitous!第三十四頁，共44頁。KNN算法(suànfǎ)的擴(kuò)展：ML-KNN（Multi-labelKNN）Min-LingZhang,Zhi-HuaZhou.ML-KNN:AlazylearningapproachtoMulti-labellearning.PatternRecognition,40(2007):2038-2048.第三十五頁，共44頁。KNN算法(suànfǎ)的擴(kuò)展：ML-KNN（Multi-labelKNN）未知樣本(yàngběn)dt的3個(gè)最近鄰是d4，d5，d6.則nt=<0,1,0>+<0,1,1>+<1,1,0>=<1,3,1>.運(yùn)用maximumaposteriori(MAP）那么(nàme)對于此例子，對類1：P（H1=1|E=1）？P（H1=0|E=1）對類2：P（H2=1|E=3）？P（H2=0|E=3）對類3：P（H3=1|E=1）？P（H3=0|E=1）第三十六頁，共44頁。KNN算法(suànfǎ)的擴(kuò)展：ML-KNN（Multi-labelKNN）由貝葉斯公式(gōngshì)：第一步：先求出先驗(yàn)概率：第三十七頁，共44頁。KNN算法(suànfǎ)的擴(kuò)展：ML-KNN（Multi-labelKNN）設(shè)平滑參數(shù)s=1.則P（H1=1）=（1+4）/（2*1+6）=0.625.第二步：求條件(tiáojiàn)概率和將訓(xùn)練集中的每一個(gè)樣本看成是一個(gè)測試樣本，找其最近鄰。第三十八頁，共44頁。KNN算法(suànfǎ)的擴(kuò)展：ML-KNN（Multi-labelKNN）然后計(jì)算(jìsuàn)概率：設(shè)平滑(pínghuá)參數(shù)s