大數據理論與技術讀書報告

　—-- — －K 最近鄰分類算法 指導老師 ：

　 陳 莉

　 學生姓名

　:

　李陽帆

　 學 學

　號 號

　：

?。?/p>

　 ２01531 ４6 ７

　 專 專

　業 ：

　計算機技術

　日

　期

?。?/p>

?。?/p>

?。? １６年 ８月 月 31 日

　摘 摘

　要

　 數據挖掘就是機器學習領域內廣泛研究得知識領域，就是將人工智能技術與數據庫技術緊密結合, 讓計算機幫助人 們從龐大得數據中智能地、自動地提取出有價值得知識模式，以滿足人們不同應用得需要。

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

　近鄰分類算法, 首先簡要地介了 紹了數據挖掘中得各種分類算法，詳細地闡述了 K 近鄰算法得基本在 原理與應用領域，最后在 mat ｌａb 環境里仿真實現，并對實驗結果進行分析，提出了改進得方法。

　關鍵詞：K

　近鄰，聚類算法，權重， 復雜度，準確度

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

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

　4、 、現 算法實現 1?４、1

　置 參數設置誤錯? 錯誤! 未定義書簽。

?。?、2 集 數據集 1?4驟 、３實驗步驟誤錯? 錯誤! 未定義書簽。

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

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

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

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

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

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

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

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

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

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

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

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

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

　本實驗得數據，實驗數據得部分截圖如圖 1 所示。

　圖 1、部分實驗數據

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

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

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

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

　第七步,選擇出現頻率最大得類標號作為未知樣本得類標號。

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

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

　圖 2、7—最近鄰分類結果圖

　圖 3、錯誤統計圖

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

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

　5、 、 總結與反思 模式分類在現實領域有著非常廣泛得應用。

?。私徦惴ň褪悄Ｊ椒诸愃惴ㄖ幸活惓Ｓ玫盟惴?。本文針對傳統得 KNN 算法得不足之處,提出了兩點改進措施。

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

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

　參考文獻

　[ [1 1] ] 鄧箴, , 包宏 、 用模擬退火改進得

　KNN 分類算法 [J ］。計算機與應用化學，２ 010 ，27(3 ）

　:3 03- - 307.

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

?。?NN

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

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

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

　84 ５－ 849.

　[ [ ４] ] 李歡，焦建民．簡化得粒子群優化快速

　KNN 分類算法［J J ］ 。計算機工程與應用，２ 008,4 ４（

　3 3 ２) ) ：

　57- -5 5 ９。

　[ [5 5 ］王曉曄, , 王正歐 .K －最近鄰分類技術得改進算法［J J ］。電子與信息學報， 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 ］余小鵬，周德翼。一種自適應ｋ－最近鄰算法得研究 [J].， 計算機應用研究， 2006(2): 7 70 0 －7 7 ２。

　附件 1:

　源代碼

　KＮN、m

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

　 KNＮ、m

　K-最近鄰分類算法 ％ ％％%％%％％%%％%％%%％%%％％％%％%%%%%％％％％%％％％ A=x ｌs ｒｅa ｄ（＇E ：\ 上課＼機器學習\ 模式識別課件\ 數據＼ＣＯR Ｋ_ ＳＴOPPEｘ ＲＳ、ｘ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

?。郏鯽l ｕ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 ）

?。錼r ｏｒ(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 ）+ １;

?。錸d

　e ｎd for

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

推薦訪問： 數據挖掘 實驗 報告