大數(shù)據(jù)理論與技術(shù)讀書報告

　—-- — －K 最近鄰分類算法 指導(dǎo)老師 ：

　 陳 莉

　 學(xué)生姓名

　:

　李陽帆

　 學(xué) 學(xué)

　號 號

　：

　：

　 ２01531 ４6 ７

　 專 專

　業(yè) ：

　計算機(jī)技術(shù)

　日

　期

　：

　：

　２0 １６年 ８月 月 31 日

　摘 摘

　要

　 數(shù)據(jù)挖掘就是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究得知識領(lǐng)域，就是將人工智能技術(shù)與數(shù)據(jù)庫技術(shù)緊密結(jié)合, 讓計算機(jī)幫助人 們從龐大得數(shù)據(jù)中智能地、自動地提取出有價值得知識模式，以滿足人們不同應(yīng)用得需要。

　Ｋ Ｋ 近鄰算法（ＫNN ）就是基于統(tǒng)計得分類方法，就是大數(shù)據(jù)理論與分析得分類算法中比較常用得一種方法。該算法具有直觀、無需先驗統(tǒng)計知識、無師學(xué)習(xí)等特點，目前已經(jīng)成為數(shù)據(jù)挖掘技術(shù)得理論與應(yīng)用研究方法之一。本文主要研究了 Ｋ Ｋ

　近鄰分類算法, 首先簡要地介了 紹了數(shù)據(jù)挖掘中得各種分類算法，詳細(xì)地闡述了 K 近鄰算法得基本在 原理與應(yīng)用領(lǐng)域，最后在 mat ｌａb 環(huán)境里仿真實現(xiàn)，并對實驗結(jié)果進(jìn)行分析，提出了改進(jìn)得方法。

　關(guān)鍵詞：K

　近鄰，聚類算法，權(quán)重， 復(fù)雜度，準(zhǔn)確度

　 1、 、 引言 ...................................................................................... 0 2、 、義 研究目得與意義誤錯? 錯誤! 未定義書簽。

　3、 、 算法想 思想誤錯? 錯誤! 未定義書簽。

　4、 、現(xiàn) 算法實現(xiàn) 1?４、1

　置 參數(shù)設(shè)置誤錯? 錯誤! 未定義書簽。

　４、2 集 數(shù)據(jù)集 1?4驟 、３實驗步驟誤錯? 錯誤! 未定義書簽。

　4 、4 析 實驗結(jié)果與分析誤錯? 錯誤! 未定義書簽。

　5、 、思 總結(jié)與反思誤錯? 錯誤! 未定義書簽。

　附件１ １誤錯? 錯誤! 未定義書簽。

　1、 、 引言 隨著數(shù)據(jù)庫技術(shù)得飛速發(fā)展，人工智能領(lǐng)域得一個分支—— 機(jī)器學(xué)習(xí)得研究自 20 世紀(jì) 50 年代開始以來也取得了很大進(jìn)展。用數(shù)據(jù)庫管理系統(tǒng)來存儲數(shù)據(jù)，用機(jī)器學(xué)習(xí)得方法來分析數(shù)據(jù),挖掘大量數(shù)據(jù)背后得知識,這兩者得結(jié)合促成了數(shù)據(jù)庫中得知識發(fā)現(xiàn)（Knowlｅdｇe Discoverｙ in Ｄａｔabａｓes，簡記 KDD)得產(chǎn)生,也稱作數(shù)據(jù)挖掘(Daｔa Ｍｉng，簡記 DM）。

　數(shù)據(jù)挖掘就是信息技術(shù)自然演化得結(jié)果。信息技術(shù)得發(fā)展大致可以描述為如下得過程:初期得就是簡單得數(shù)據(jù)收集與數(shù)據(jù)庫得構(gòu)造;后來發(fā)展到對數(shù)據(jù)得管理，包括：數(shù)據(jù)存儲、檢索以及數(shù)據(jù)庫事務(wù)處理；再后來發(fā)展到對數(shù)據(jù)得分析與理解， 這時候出現(xiàn)了數(shù)據(jù)倉庫技術(shù)與數(shù)據(jù)挖掘技術(shù)。數(shù)據(jù)挖掘就是涉及數(shù)據(jù)庫與人工智能等學(xué)科得一門當(dāng)前相當(dāng)活躍得研究領(lǐng)域。

　數(shù)據(jù)挖掘就是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究得知識領(lǐng)域，就是將人工智能技術(shù)與數(shù)據(jù)庫技術(shù)緊密結(jié)合,讓計算機(jī)幫助人們從龐大得數(shù)據(jù)中智能地、自動地抽取出有價值得知識模式,以滿足人們不同應(yīng)用得需要[1］.目前，數(shù)據(jù)挖掘已經(jīng)成為一個具有迫切實現(xiàn)需要得很有前途得熱點研究課題。

　2、 、 研究目得與意義 近鄰方法就是在一組歷史數(shù)據(jù)記錄中尋找一個或者若干個與當(dāng)前記錄最相似得歷史紀(jì)錄得已知特征值來預(yù)測當(dāng)前記錄得未知或遺失特征值[１4]。近鄰方法就是數(shù)據(jù)挖掘分類算法中比較常用得一種方法。Ｋ 近鄰算法(簡稱 KNN)就是基于統(tǒng)計得分類方法［15]。KNN 分類算法根據(jù)待識樣本在特征空間中 K 個最近鄰樣本中得多數(shù)樣本得類別來進(jìn)行分類，因此具有直觀、無需先驗統(tǒng)計知識、無師學(xué)習(xí)等特點,從而成為非參數(shù)分類得一種重要方法。

　大多數(shù)分類方法就是基于向量空間模型得。當(dāng)前在分類方法中，對任意兩個向量：

　x＝與存在 ３ 種最通用得距離度量：歐氏距離、余弦距離[1６］與內(nèi)積[1７]。有兩種常用得分類策略：一種就是計算待分類向量到所有訓(xùn)練集中得向量間得距離：如 K 近鄰選擇 K 個距離最小得向量然后進(jìn)行綜合，以決定其類別。另一種就是用訓(xùn)練集中得向量構(gòu)成類別向量，僅計算待分類向量到所有類別向量得距離，選擇一個距離最小得類別向量決定類別得歸屬。很明顯,距離計算在分類中起關(guān)鍵作用。由于以上 3 種距離度量不涉及向量得特征之間得關(guān)系,這使得距離得計算不精確，從而影響分類得效果。

　3、 、 算法 思想 K 最近鄰（K-Ｎeａresｔ Nｅighbor,ＫＮN）算法，就是著名得模式識別統(tǒng)計學(xué)方法，

　在機(jī)器學(xué)習(xí)分類算法中占有相當(dāng)大得地位.它就是一個理論上比較成熟得方法。既就是最簡單得機(jī)器學(xué)習(xí)算法之一，也就是基于實例得學(xué)習(xí)方法中最基本得，又就是最好得文本分類算法之一. 其基本思想就是：假設(shè)每一個類包含多個樣本數(shù)據(jù)，而且每個數(shù)據(jù)都有一個唯一得類標(biāo)記表示這些樣本就是屬于哪一個分類， KNＮ就就是計算每個樣本數(shù)據(jù)到待分類數(shù)據(jù)得距離,如果一個樣本在特征空間中得 k 個最相似（即特征空間中最鄰近）得樣本中得大多數(shù)屬于某一個類別,則該樣本也屬于這個類別。該方法在定類決策上只依據(jù)最鄰近得一個或者幾個樣本得類別來決定待分樣本所屬得類別. K—最臨近分類方法存放所有得訓(xùn)練樣本,在接受待分類得新樣本之前不需構(gòu)造模型，并且直到新得（未標(biāo)記得)樣本需要分類時才建立分類.K－最臨近分類基于類比學(xué)習(xí),其訓(xùn)練樣本由Ｎ維數(shù)值屬性描述，每個樣本代表 N 維空間得一個點。這樣，所有訓(xùn)練樣本都存放在 N維模式空間中.給定一個未知樣本,k—最臨近分類法搜索模式空間，找出最接近未知樣本得K 個訓(xùn)練樣本。這 K 個訓(xùn)練樣本就是未知樣本得 K 個“近鄰”.“臨近性”又稱為相異度（Dｉssimiｌarity）,由歐幾里德距離定義，其中兩個點 Ｘ（x １ ，x 2 ,„ｘ n ）與 Y(y 1 ,y 2 ，„yｎ )得歐幾里德距離就是:

　未知樣本被分配到K個最臨近者中最公共得類.在最簡單得情況下,也就就是當(dāng)Ｋ＝1時,未知樣本被指定到模式空間中與之最臨近得訓(xùn)練樣本得類. 4、 、 算法實現(xiàn) 4、 、１ １ 參數(shù)設(shè)置 K 值得設(shè)定 K 值設(shè)置過小會降低分類精度;若設(shè)置過大，且測試樣本屬于訓(xùn)練集中包含數(shù)據(jù)較少得類,則會增加噪聲，降低分類效果。通常，Ｋ值得設(shè)定采用交叉檢驗得方式（以 K=１為基準(zhǔn)）， 通過查找相關(guān)資料，Ｋ一般低于訓(xùn)練樣本數(shù)得平方根,本實驗中得訓(xùn)練樣本數(shù)為 10０個,因此選取 k=7。

　4 、2 數(shù)據(jù)集 本文得實驗數(shù)據(jù)采用軟木塞得數(shù)據(jù)集，軟木塞得樣本可分為三類，分別用１,2，３代表，共 1５0 個樣本，我們選取其中得 100 個樣本為訓(xùn)練集，其余得 50 個樣本為測試集。每個樣本均包含１0 維特征,由于用 10 維特征計算量太大，本實驗得目得主要就是明白 K-最近鄰算法得思想，重點不在計算，因此我們選取其中得兩個屬性作為

　本實驗得數(shù)據(jù)，實驗數(shù)據(jù)得部分截圖如圖 1 所示。

　圖 1、部分實驗數(shù)據(jù)

　4 、3 實驗步驟 第一步，初始化距離為最大值。

　第二步,計算未知樣本與每個訓(xùn)練樣本得距離 dｉｓt。

　第三步,得到目前 K 個最臨近樣本中得最大距離 maxｄist。

　第四步，如果ｄisｔ小于 mａxdｉsｔ，則將該訓(xùn)練樣本作為 K－最近鄰樣本. 第五步，重復(fù)步驟 2、3、4，直到未知樣本與所有訓(xùn)練樣本得距離都算完. 第六步,統(tǒng)計Ｋ—最近鄰樣本中每個類標(biāo)號出現(xiàn)得次數(shù)。

　第七步,選擇出現(xiàn)頻率最大得類標(biāo)號作為未知樣本得類標(biāo)號。

　4 、4 實驗結(jié)果與分析 按照上述實驗步驟,在mａt(yī)lab中仿真實現(xiàn)k－近鄰分類算法得結(jié)果如下圖2所示,圖中得第一列數(shù)據(jù)表示樣本編號，第二列與第三列表示軟如塞數(shù)據(jù)得兩位特征得值,第三列得數(shù)字表示本實驗得分類結(jié)果圖,第四列表示樣本實際所屬類別。

　圖 3 中列出了詳細(xì)錯誤信息.第一行與第一列表示樣本類別,第 i 行第 j 列得元素表示第 i類樣本被分為第 j 類樣本得個數(shù)（2≤ｉ，ｊ≤4),第五列表示每類樣本分類錯誤總數(shù),第六列表示錯誤率。由圖中數(shù)據(jù)易得,本實驗得平均正確率為 86、７％。

　圖 2、7—最近鄰分類結(jié)果圖

　圖 3、錯誤統(tǒng)計圖

　KＮN 方法雖然從原理上也依賴于極限定理,但在類別決策時，只與極少量得相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本得不平衡問題。另外，由于 KＮN方法主要靠周圍有限得鄰近得樣本，而不就是靠判別類域得方法來確定所屬類別得,因此對于類域得交叉或重疊較多得待分樣本集來說，KＮN 方法較其她方法更為適合。

　該方法得不足之處就是計算量較大，因為對每一個待分類得文本都要計算它到全體已知樣本得距離,才能求得它得 K個最近鄰點.目前常用得解決方法就是事先對已知樣本點進(jìn)行剪輯，事先去除對分類作用不大得樣本。該算法比較適用于樣本容量比較大得類域得自動分類,而那些樣本容量較小得類域采用這種算法比較容易產(chǎn)生誤分。

　5、 、 總結(jié)與反思 模式分類在現(xiàn)實領(lǐng)域有著非常廣泛得應(yīng)用。

　Ｋ近鄰算法就是模式分類算法中一類常用得算法。本文針對傳統(tǒng)得 KNN 算法得不足之處,提出了兩點改進(jìn)措施。

　1、針對 KＮN 算法得計算量大、速度慢得缺點,對訓(xùn)練數(shù)據(jù)采用了預(yù)處理得方法.首先采用某一聚類方法對訓(xùn)練數(shù)據(jù)進(jìn)行分類，然后再與 K 近鄰方法相結(jié)合來判斷待測樣本得類別。現(xiàn)有得方法都就是經(jīng)過聚類之后確定類別，按一定得規(guī)則挑選出來具有代表性得數(shù)據(jù)。然后再將這些挑選出來得數(shù)據(jù)作為訓(xùn)練樣本.但這類方法能去除得數(shù)據(jù)非常有限,因此對計算量大得改進(jìn)不大，而本文提出得新得算法:在聚類之后,首先計算出來各個類別得中心,然后只需要考慮待測樣本與聚類中心得距離就可以.然后再根據(jù)最終得到得距離得大小判斷該點所屬得類別。通過實例驗證表明,該方法在算法得時間復(fù)雜度方面有一定得改進(jìn)。

　2、關(guān)于準(zhǔn)確度得問題,我們主要就是舍棄了原來常用得歐式距離得計算公式，主要考慮了屬性對分類得影響,在歐式距離得計算中引入了權(quán)值.盡管權(quán)值得確定在一定程度上增加了計算時間得代價,但就是從改進(jìn)分類準(zhǔn)確率上來說仍然就是必要得,尤其就是在數(shù)據(jù)中無關(guān)屬性比較多,傳統(tǒng)得分類算法誤差較大得情況下學(xué)習(xí)特征權(quán)值尤其適用。權(quán)值得確定也已經(jīng)有了不少得方法，如可以通過神經(jīng)網(wǎng)絡(luò)來確定權(quán)值等。本文從訓(xùn)練樣本出發(fā)，逐一統(tǒng)計計算每一個屬性對分類結(jié)果得影響，根據(jù)影響得大小來確定權(quán)值。通過實例驗證，可知這種方法得到得權(quán)值與其她常用得方法相比,在分類準(zhǔn)確度方面有一定得提高。

　參考文獻(xiàn)

　[ [1 1] ] 鄧箴, , 包宏 、 用模擬退火改進(jìn)得

　KNN 分類算法 [J ］。計算機(jī)與應(yīng)用化學(xué)，２ 010 ，27(3 ）

　:3 03- - 307.

　［2 2 ］郭躬德，黃杰，陳黎飛 、 基于

　Ｋ NN

　模型得增量學(xué)習(xí)算法 [J ］。模式識別與人工智能， 20 １０ ,23( ５ ):70 １－7 7 ０７。

　［ ３ ］黃杰，郭躬德，陳黎飛 、 增量

　K K Ｎ N 模型得修剪策略研究［J J ]. 小型微型計算機(jī)系統(tǒng)， 201 １, , ５ (5) ：

　84 ５－ 849.

　[ [ ４] ] 李歡，焦建民．簡化得粒子群優(yōu)化快速

　KNN 分類算法［J J ］ 。計算機(jī)工程與應(yīng)用，２ 008,4 ４（

　3 3 ２) ) ：

　57- -5 5 ９。

　[ [5 5 ］王曉曄, , 王正歐 .K －最近鄰分類技術(shù)得改進(jìn)算法［J J ］。電子與信息學(xué)報， 2005,２7 7 （ 3):4 ８7 7 — 49 １．

　［ ６ ］ Gu ｏ

　Gongde, Ｗ ang Hui, Ｂｅ ll

　D D ，ｅ t al. U ｓｉｎ g Ｋ NN model for aｕt t ｏ ma ｔi i ｃ

　tex ｔ

　ca ｔ egori ｚa a ｔ ion ［ Ｊ ］、 Soft

　putin ｇ — A F ｕ sion o ｆ

　F F ｏｕｎ dat ｉ on, M ｅ thodo ｌｏ gi ｅｓ

　ａｎd d

　Ａ pplicatio ｎ ， 200 ６, ,1 1 ０（ 5) ：４2 2 ３- - 430.

　[ [7 7 ］余小鵬，周德翼。一種自適應(yīng)ｋ－最近鄰算法得研究 [J].， 計算機(jī)應(yīng)用研究， 2006(2): 7 70 0 －7 7 ２。

　附件 1:

　源代碼

　KＮN、m

　 %%％%%％%％%％%%%％%％%％％%％％％%％%％％％％%%％％% %

　 KNＮ、m

　K-最近鄰分類算法 ％ ％％%％%％％%%％%％%%％%%％％％%％%%%%%％％％％%％％％ A=x ｌs ｒｅa ｄ（＇E ：\ 上課＼機(jī)器學(xué)習(xí)\ 模式識別課件\ 數(shù)據(jù)＼ＣＯR Ｋ_ ＳＴO(shè)PPEｘ ＲＳ、ｘls",2 ）； f=zer ｏs(150 ，5) ； ｆ ｆ( ：, １:2 ）=A （1 ：１50, ３：4) ； f1 ＝Ａ（1 ：50 ，3 ：4) ； f2= Ａ（51:100 ，3 ：4); f3= Ａ( １01:15 ０, ３：4); ｃ ｃl ｓ= ｚero ｓ（1 ５0 ，１0); ｏ ｆｏr

　ｉ= １：150

　 for j ＝1:1 ５0

　 c ｌｓ(i ，j ）＝norm （f(i ，１：2 ）-f （ｊ，1 ：２））;

　end end % 對計算出得每個樣本與其她 150 個樣本( 包括自己）得距離排序，選 K=10 arr ａy= ｚeros(300 ，１1 ）； f ｏr ｉi ＝１：150

　［ｖal ｕe,inde ｘ］＝ｓort(cl ｓ（i ｉ, ：）);

　 ａｒｒa ｙ（2 ＊ｉｉ— １，：) ＝val ｕｅ(1: １１）；

　a ｒｒay(2 ＊ｉi, ：) ＝in ｄex(1 ：1 １）； end 類 ％對每個樣本分類 fo ｒ ii= １:150

　a11=length(f ｉnd(array(2 ＊i ｉ,: ）〈５0));

　a12=l ｅngth （f ｉnd(arr ａy （２＊ii ，: ）〉50 ＆a ｒr ａy(2*i ｉ，：）〈１00 ）)； ；

　 a13=len ｇth （ｆｉnd （a ｒray （2 ＊ｉi ，：) 〉1 ０0 ＆array （2 ＊i ｉ，：)<15）

　０）) ；

　ｉf （max(max （ａ１1,a12) ，a13)==a11)

　f(ii,3 ）=1;

　else if （ｍax （max(a11 ，ａ12) ，ａ1 ３）＝=a12 ）

　f （ii,3)=2;

　 els ｅ

　 ｆ（i ｉ,3 ）＝3 ；

　 end

　 en ｄ

　end % 錯誤計算 e ｒro ｒ＝ze ｒo ｓ（３,5 ）; for

　i=1 ：50

　if(f （ｉ，3 ）= ＝2 ）

　 error （1 ，2)= ｅｒｒor （1,2 ）+1 ；

　end

　 if （ｆ（i,3) ＝=3 ）

　ｅrr ｏｒ(1 ，3 ）= ｅｒｒo ｒ(1 ，3 ）+1 ；

　 ｅnd

　 if(f （5 ０+i ，３）==1 ）

　 ｅr ｒｏｒ(2,1 ）＝erro ｒ（2 ，1)+ １；

　ｅnd

　if( ｆ（5 ０+i, ３）==3 ）

　 err ｏr( ２,3) ＝e ｒror(2,3)+1 ；

　en ｄ

　 if （ｆ（100+ ｉ，3)==1)

　error （3 ，1)= ｅｒro ｒ（３，1)+1;

　end

　i ｆ（ｆ(100+i, ３）== ２）

　er ｒor （3 ，２）=er ｒo ｒ（3,2 ）+ １;

　ｅnd

　e ｎd for

　k ＝1:3 %D 第四列表示錯誤數(shù) err ｏｒ(k,4 ）＝err ｏr （k ，１）＋err ｏr(k ，2 ）+e ｒro ｒ( ｋ,3 ）; error(k ，5) ＝err ｏr(k ，４)/50 ； en ｄ

推薦訪問： 數(shù)據(jù)挖掘 實驗 報告