《大數(shù)據(jù)處理與智能決策 》課件-12-KNN

KNN算法是怎么來(lái)的電影名稱打斗次數(shù)接吻次數(shù)電影類型CaliforniaMan

3104RomanceHe’sNotReallyintoDudes

2100RomanceBeautifulWoman

181RomanceKevinLongblade

10110ActionRoboSlayer3000

995ActionAmpedII

982Action未知1890Unknown猜猜看：最后一行未知電影屬于什么類型的電影。KNN算法是怎么來(lái)的點(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猜猜看：最后一行未知點(diǎn)屬于什么類型的點(diǎn)。最近鄰算法由此，我們引出最近鄰算法的定義：為了判定未知樣本的類別，以全部訓(xùn)練樣本作為代表點(diǎn)，計(jì)算未知樣本與所有訓(xùn)練樣本的距離，并以最近鄰者的類別作為決策未知樣本類別的唯一依據(jù)。

最近鄰算法的缺陷——對(duì)噪聲數(shù)據(jù)過(guò)于敏感，為了解決這個(gè)問(wèn)題，我們可以把未知樣本周邊的多個(gè)最近樣本計(jì)算在內(nèi)，擴(kuò)大參與決策的樣本量，以避免個(gè)別數(shù)據(jù)直接決定決策結(jié)果。由此，引進(jìn)K-近鄰（knearestneighbor）算法。KNN算法是用來(lái)干什么的

K-最近鄰算法是最近鄰算法的一個(gè)延伸?；舅悸肥牵哼x擇距離未知樣本最近的K個(gè)樣本，該K個(gè)樣本大多數(shù)屬于某一類型，則未知樣本判定為該類型。問(wèn)題：有一個(gè)未知形狀X(圖中綠色的圓點(diǎn))，如何判斷X是什么形狀?右圖中，綠色圓要被決定賦予哪個(gè)類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形那個(gè)類，如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類。KNN算法基本描述k-近鄰法:基本規(guī)則是，在所有N個(gè)樣本中,找到測(cè)試樣本的k(k<=N)個(gè)最近鄰者，當(dāng)k=1時(shí)，knn問(wèn)題就變成了最近鄰問(wèn)題。其中各類別所占個(gè)數(shù)表示成ki,i＝1，…，c。定義判別函數(shù)為：

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

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

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

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

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

KNN算法是怎么來(lái)的想一想：下面圖片中只有三種豆，有三個(gè)豆是未知的種類，如何判定他們的種類？1968年，Cover和Hart提出了最初的近鄰法。最近鄰算法

提供一種思路，即：未知的豆離哪種豆最近就認(rèn)為未知豆和該豆是同一種類。由此，我們引出最近鄰算法的定義：為了判定未知樣本的類別，以全部訓(xùn)練樣本作為代表點(diǎn)，計(jì)算未知樣本與所有訓(xùn)練樣本的距離，并以最近鄰者的類別作為決策未知樣本類別的唯一依據(jù)。但是，最近鄰算法明顯是存在缺陷的，我們來(lái)看一個(gè)例子。KNN算法是怎么來(lái)的問(wèn)題：有一個(gè)未知形狀X(圖中綠色的圓點(diǎn))，如何判斷X是什么形狀?K-最近鄰算法

顯然，通過(guò)上面的例子我們可以明顯發(fā)現(xiàn)最近鄰算法的缺陷——對(duì)噪聲數(shù)據(jù)過(guò)于敏感，為了解決這個(gè)問(wèn)題，我們可以可以把位置樣本周邊的多個(gè)最近樣本計(jì)算在內(nèi)，擴(kuò)大參與決策的樣本量，以避免個(gè)別數(shù)據(jù)直接決定決策結(jié)果。由此，我們引進(jìn)K-最近鄰算法。

KNN算法是用來(lái)干什么的

K-最近鄰算法是最近鄰算法的一個(gè)延伸?；舅悸肥牵哼x擇未知樣本一定范圍內(nèi)確定個(gè)數(shù)的K個(gè)樣本，該K個(gè)樣本大多數(shù)屬于某一類型，則未知樣本判定為該類型。

下面借助圖形解釋一下。KNN算法的實(shí)現(xiàn)步驟算法步驟：step.1---初始化距離為最大值step.2---計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離diststep.3---得到目前K個(gè)最臨近樣本中的最大距離maxdiststep.4---如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近

鄰樣本step.5---重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的

距離都算完step.6---統(tǒng)計(jì)K個(gè)最近鄰樣本中每個(gè)類別出現(xiàn)的次數(shù)step.7---選擇出現(xiàn)頻率最大的類別作為未知樣本的類別KNN算法的實(shí)現(xiàn)步驟算法步驟：1：令k是最近鄰數(shù)目，D是訓(xùn)練樣例的集合2：for每個(gè)測(cè)試樣例zdo3：計(jì)算z和每個(gè)訓(xùn)練樣例之間的距離d4：對(duì)d進(jìn)行升序排序5：取前k個(gè)訓(xùn)練樣例的集合6：統(tǒng)計(jì)K個(gè)最近鄰樣本中每個(gè)類別出現(xiàn)的次數(shù)7：選擇出現(xiàn)頻率最大的類別作為未知樣本的類別8：endforKNN算法MATLAB%KNNclassifiers,%trainingistrainingset,testingistestset,%Disthedistance,D=1is曼哈頓距離;D=2is歐氏距離；D=3是切比雪夫%距離%Kisthenumberofselectedneighborsfunctionlabel=KNN(training,testing,D,K)[row,column]=size(training)；%%%row行（樣本），column列（屬性）[row1,column1]=size(testing);%計(jì)算測(cè)試集與訓(xùn)練集的距離KNN算法MATLAB%數(shù)據(jù)標(biāo)準(zhǔn)化Tr_m=min(training);%%%每列（屬性）取最小值，得到一個(gè)行向量Tr_s=max(training);%%%每列（屬性）取最大值，得到一個(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)KNN算法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ù)求曼哈頓距離distance(i,j)=d(1,2);%%兩個(gè)列向量求mandist，得出endendendKNN算法MATLAB%%%%%計(jì)算歐幾里得距離%%%%%%%%%%%%%%%%%%ifD==2fori=1:row1forj=1:rowtemp=[training(j,[1:(column-1)]);testing(i,:)]';d=dist(temp);%%%%dist函數(shù)計(jì)算距離distance(i,j)=d(1,2);endendendKNN算法MATLAB%%%%%計(jì)算切比雪夫距離%%%%%%%%%%%%%%%%%%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;endendendKNN算法MATLAB%%%%尋找k個(gè)近鄰%%%%算法核心部分%%%%%%%%%%%%%%label=[];fori=1:row1[a,b]=sort(distance(i,:));%%針對(duì)第i個(gè)測(cè)試樣本與所有訓(xùn)練樣本的距離，進(jìn)行升序排序，距離越小，離的越近，a返回排序后的距離，b返回排序后的下標(biāo)neighbors=b(1:K)‘;%%選取前k個(gè)下標(biāo)neighbors_D=training(neighbors,column);%%對(duì)應(yīng)下標(biāo)找到k個(gè)類標(biāo)號(hào)[x,y]=sort(neighbors_D);%對(duì)K個(gè)類標(biāo)號(hào)排序，x返回類標(biāo)號(hào)，y返回下標(biāo)temp=find(diff(x)~=0);nei_d=[x(1);x(temp+1)];%對(duì)前k個(gè)樣本的標(biāo)簽進(jìn)行分類KNN算法MATLAB

Num_D=[];forj=1:length(nei_d)num=length(find(neighbors_D==nei_d(j)));Num_D=[Num_D,num];end%%%%%計(jì)算樣本的類別號(hào)%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%[a,b]=max(Num_D);%取標(biāo)簽較多的那個(gè)類作為測(cè)試樣本的類別

label(i)=nei_d(b);end%label=label';

KNN算法的缺陷

觀察下面的例子，我們看到，對(duì)于位置樣本X，通過(guò)KNN算法，我們顯然可以得到X應(yīng)屬于紅點(diǎn)，但對(duì)于位置樣本Y，通過(guò)KNN算法我們似乎得到了Y應(yīng)屬于藍(lán)點(diǎn)的結(jié)論，而這個(gè)結(jié)論直觀來(lái)看并沒(méi)有說(shuō)服力。KNN算法的具體實(shí)現(xiàn)

由上面的例子可見(jiàn)：該算法在分類時(shí)有個(gè)重要的不足是，當(dāng)樣本不平衡時(shí)，即：一個(gè)類的樣本容量很大，而其他類樣本數(shù)量很小時(shí)，很有可能導(dǎo)致當(dāng)輸入一個(gè)未知樣本時(shí)，該樣本的K個(gè)鄰居中大數(shù)量類的樣本占多數(shù)。但是這類樣本并不接近目標(biāo)樣本，而數(shù)量小的這類樣本很靠近目標(biāo)樣本。這個(gè)時(shí)候，我們有理由認(rèn)為該位置樣本屬于數(shù)量小的樣本所屬的一類，但是，KNN卻不關(guān)心這個(gè)問(wèn)題，它只關(guān)心哪類樣本的數(shù)量最多，而不去把距離遠(yuǎn)近考慮在內(nèi)，因此，我們可以采用權(quán)值的方法來(lái)改進(jìn)。和該樣本距離小的鄰居權(quán)值大，和該樣本距離大的鄰居權(quán)值則相對(duì)較小，由此，將距離遠(yuǎn)近的因素也考慮在內(nèi)，避免因一個(gè)樣本過(guò)大導(dǎo)致誤判的情況。KNN算法的缺陷

從算法實(shí)現(xiàn)的過(guò)程大家可以發(fā)現(xiàn)，該算法存兩個(gè)嚴(yán)重的問(wèn)題，第一個(gè)是需要存儲(chǔ)全部的訓(xùn)練樣本，第二個(gè)是需要進(jìn)行繁重的距離計(jì)算量。對(duì)此，提出以下應(yīng)對(duì)策略。

KNN算法的改進(jìn)：分組快速搜索近鄰法

其基本思想是：將樣本集按近鄰關(guān)系分解成組，給出每組質(zhì)心的位置，以質(zhì)心作為代表點(diǎn)，和未知樣本計(jì)算距離，選出距離最近的一個(gè)或若干個(gè)組，再在組的范圍內(nèi)應(yīng)用一般的knn算法。由于并不是將未知樣本與所有樣本計(jì)算距離，故該改進(jìn)算法可以減少計(jì)算量，但并不能減少存儲(chǔ)量。KNN算法的改進(jìn)：壓縮近鄰算法

利用現(xiàn)在的樣本集，采取一定的算法產(chǎn)生一個(gè)新的樣本集，該樣本集擁有比原樣本集少的多的樣本數(shù)量，但仍然保持有對(duì)未知樣本進(jìn)行分類的能力。

基本思路：定義兩個(gè)存儲(chǔ)器，一個(gè)用來(lái)存放生成的樣本集，稱為output樣本集；另一個(gè)用來(lái)存放原來(lái)的樣本集，稱為original樣本集。1.初始化：output樣本集為空集，原樣本集存入original樣本集，從original樣本集中任意選擇一個(gè)樣本移動(dòng)到output樣本集中；2.在original樣本集中選擇第i個(gè)樣本，并使用output樣本集中的樣本對(duì)其進(jìn)行最近鄰算法分類，若分類錯(cuò)誤，則將該樣本移動(dòng)到output樣本集中，若分類正確，不做任何處理；3.重復(fù)2步驟，直至遍歷完original樣本集中的所有樣本，output樣本集即為壓縮后的樣本集。通過(guò)這種方式也能減少算法的計(jì)算量，但仍然無(wú)法減少存儲(chǔ)量。KNN算法幾大問(wèn)題1、k值設(shè)定為多大？

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

KNN算法幾大問(wèn)題2、類別如何判定最合適？

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

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

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

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

分類學(xué)習(xí)算法的種類

積極學(xué)習(xí)法(決策樹(shù)歸納)：先根據(jù)訓(xùn)練集構(gòu)造出分類模型，根據(jù)分類模型對(duì)測(cè)試集分類。5、性能問(wèn)題？

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

Multi-LabelLearning(MLL)Multi-labelobjectsareubiquitous!KNN算法的擴(kuò)展：ML-KNN（Multi-labelKNN）Min-LingZhang,Zhi-HuaZhou.ML-KNN:AlazylearningapproachtoMulti-labellearning.PatternRecognition,40(2007):2038-2048.KNN算法的擴(kuò)展：ML-KNN（Multi-labelKNN）未知樣本dt的3個(gè)最近鄰是d4，d5，d6.則nt=<0,1,0>+<0,1,1>+<1,1,0>=<1,3,1>.運(yùn)用maximumaposteriori(MAP）那么對(duì)于此例子，對(duì)類1：P（H1=1|E=1）？P（H1=0|E=1）對(duì)類2：P（H2=1|E=3）？P（H2=0|E=3）對(duì)類3：P（H3=1|E=1）？P（H3=0|E=1）KNN算法的擴(kuò)展：ML-KNN（Multi-labelKNN）由貝葉斯公式：第一步：先求出先驗(yàn)概率：KNN算法的擴(kuò)展：ML-KNN（Multi-labelKNN）設(shè)平滑參數(shù)s=1.則P（H1=1）=（1+4）/（2*1+6