大數(shù)據(jù)理論與技術讀書報告 -K最近鄰分類算法指導老師 : 陳 莉 學生姓名 : 李陽帆 學 號 : 201531467 專 業(yè) : 計算機技術 日 期 : 2016年8月31日 摘 要 數(shù)據(jù)挖掘是機器學習領域內廣泛研究的知識領域，是將人工智能技術和數(shù)據(jù)庫技術緊密結合，讓計算機幫助人們從龐大的數(shù)據(jù)中智能地、自動地提取出有價值的知識模式，以滿足人們不同應用的需要。K 近鄰算法（KNN）是基于統(tǒng)計的分類方法，是大數(shù)據(jù)理論與分析的分類算法中比較常用的一種方法。該算法具有直觀、無需先驗統(tǒng)計知識、無師學習等特點，目前已經(jīng)成為數(shù)據(jù)挖掘技術的理論和應用研究方法之一。本文主要研究了 K 近鄰分類算法，首先簡要地介紹了數(shù)據(jù)挖掘中的各種分類算法，詳細地闡述了K 近鄰算法的基本原理和應用領域，最后在matlab環(huán)境里仿真實現(xiàn)，并對實驗結果進行分析，提出了改進的方法。 關鍵詞：K 近鄰，聚類算法，權重，復雜度，準確度 1.引言12.研究目的與意義13.算法思想24.算法實現(xiàn)24.1 參數(shù)設置24.2數(shù)據(jù)集24.3實驗步驟34.4實驗結果與分析35.總結與反思4附件161.引言隨著數(shù)據(jù)庫技術的飛速發(fā)展，人工智能領域的一個分支機器學習的研究自 20 世紀 50 年代開始以來也取得了很大進展。用數(shù)據(jù)庫管理系統(tǒng)來存儲數(shù)據(jù)，用機器學習的方法來分析數(shù)據(jù)，挖掘大量數(shù)據(jù)背后的知識，這兩者的結合促成了數(shù)據(jù)庫中的知識發(fā)現(xiàn)（Knowledge Discovery in Databases，簡記 KDD）的產(chǎn)生，也稱作數(shù)據(jù)挖掘（Data Ming，簡記 DM）。 數(shù)據(jù)挖掘是信息技術自然演化的結果。信息技術的發(fā)展大致可以描述為如下的過程：初期的是簡單的數(shù)據(jù)收集和數(shù)據(jù)庫的構造；后來發(fā)展到對數(shù)據(jù)的管理，包括：數(shù)據(jù)存儲、檢索以及數(shù)據(jù)庫事務處理；再后來發(fā)展到對數(shù)據(jù)的分析和理解，這時候出現(xiàn)了數(shù)據(jù)倉庫技術和數(shù)據(jù)挖掘技術。數(shù)據(jù)挖掘是涉及數(shù)據(jù)庫和人工智能等學科的一門當前相當活躍的研究領域。 數(shù)據(jù)挖掘是機器學習領域內廣泛研究的知識領域，是將人工智能技術和數(shù)據(jù)庫技術緊密結合，讓計算機幫助人們從龐大的數(shù)據(jù)中智能地、自動地抽取出有價值的知識模式，以滿足人們不同應用的需要1。目前，數(shù)據(jù)挖掘已經(jīng)成為一個具有迫切實現(xiàn)需要的很有前途的熱點研究課題。2.研究目的與意義近鄰方法是在一組歷史數(shù)據(jù)記錄中尋找一個或者若干個與當前記錄最相似的歷史紀錄的已知特征值來預測當前記錄的未知或遺失特征值14。近鄰方法是數(shù)據(jù)挖掘分類算法中比較常用的一種方法。K 近鄰算法（簡稱 KNN）是基于統(tǒng)計的分類方法15。KNN 分類算法根據(jù)待識樣本在特征空間中 K 個最近鄰樣本中的多數(shù)樣本的類別來進行分類，因此具有直觀、無需先驗統(tǒng)計知識、無師學習等特點，從而成為非參數(shù)分類的一種重要方法。 大多數(shù)分類方法是基于向量空間模型的。當前在分類方法中，對任意兩個向量：x=和存在 3 種最通用的距離度量：歐氏距離、余弦距離16和內積17。有兩種常用的分類策略：一種是計算待分類向量到所有訓練集中的向量間的距離：如 K 近鄰選擇K個距離最小的向量然后進行綜合，以決定其類別。另一種是用訓練集中的向量構成類別向量，僅計算待分類向量到所有類別向量的距離，選擇一個距離最小的類別向量決定類別的歸屬。很明顯，距離計算在分類中起關鍵作用。由于以上 3 種距離度量不涉及向量的特征之間的關系，這使得距離的計算不精確，從而影響分類的效果。3.算法思想K最近鄰(K-Nearest Neighbor,KNN)算法，是著名的模式識別統(tǒng)計學方法，在機器學習分類算法中占有相當大的地位。它是一個理論上比較成熟的方法。既是最簡單的機器學習算法之一，也是基于實例的學習方法中最基本的，又是最好的文本分類算法之一。其基本思想是：假設每一個類包含多個樣本數(shù)據(jù)，而且每個數(shù)據(jù)都有一個唯一的類標記表示這些樣本是屬于哪一個分類， KNN就是計算每個樣本數(shù)據(jù)到待分類數(shù)據(jù)的距離，如果一個樣本在特征空間中的k個最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。該方法在定類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。K-最臨近分類方法存放所有的訓練樣本，在接受待分類的新樣本之前不需構造模型，并且直到新的（未標記的）樣本需要分類時才建立分類。K-最臨近分類基于類比學習，其訓練樣本由N維數(shù)值屬性描述，每個樣本代表N維空間的一個點。這樣，所有訓練樣本都存放在N維模式空間中。給定一個未知樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的K個訓練樣本。這K個訓練樣本是未知樣本的K個“近鄰”?！芭R近性”又稱為相異度（Dissimilarity），由歐幾里德距離定義，其中兩個點 X（x1,x2,xn）和Y（y1,y2,yn）的歐幾里德距離是：未知樣本被分配到K個最臨近者中最公共的類。在最簡單的情況下，也就是當K=1時，未知樣本被指定到模式空間中與之最臨近的訓練樣本的類。4.算法實現(xiàn)4.1 參數(shù)設置K值的設定K值設置過小會降低分類精度；若設置過大，且測試樣本屬于訓練集中包含數(shù)據(jù)較少的類，則會增加噪聲，降低分類效果。通常，K值的設定采用交叉檢驗的方式（以K=1為基準），通過查找相關資料，K一般低于訓練樣本數(shù)的平方根，本實驗中的訓練樣本數(shù)為100個，因此選取k=7。4.2數(shù)據(jù)集本文的實驗數(shù)據(jù)采用軟木塞的數(shù)據(jù)集，軟木塞的樣本可分為三類，分別用1，2，3代表，共150個樣本，我們選取其中的100個樣本為訓練集，其余的50個樣本為測試集。每個樣本均包含10維特征，由于用10維特征計算量太大，本實驗的目的主要是明白K-最近鄰算法的思想，重點不在計算，因此我們選取其中的兩個屬性作為本實驗的數(shù)據(jù)，實驗數(shù)據(jù)的部分截圖如圖1所示。圖1.部分實驗數(shù)據(jù) 4.3實驗步驟第一步，初始化距離為最大值。第二步，計算未知樣本和每個訓練樣本的距離dist。第三步，得到目前K個最臨近樣本中的最大距離maxdist。第四步，如果dist小于maxdist，則將該訓練樣本作為K-最近鄰樣本。第五步，重復步驟2、3、4，直到未知樣本和所有訓練樣本的距離都算完。第六步，統(tǒng)計K-最近鄰樣本中每個類標號出現(xiàn)的次數(shù)。第七步，選擇出現(xiàn)頻率最大的類標號作為未知樣本的類標號。4.4實驗結果與分析按照上述實驗步驟，在matlab中仿真實現(xiàn)k-近鄰分類算法的結果如下圖2所示，圖中的第一列數(shù)據(jù)表示樣本編號，第二列和第三列表示軟如塞數(shù)據(jù)的兩位特征的值，第三列的數(shù)字表示本實驗的分類結果圖，第四列表示樣本實際所屬類別。圖3中列出了詳細錯誤信息。第一行和第一列表示樣本類別，第i行第j列的元素表示第i類樣本被分為第j類樣本的個數(shù)（2i,j4），第五列表示每類樣本分類錯誤總數(shù)，第六列表示錯誤率。由圖中數(shù)據(jù)易得，本實驗的平均正確率為86.7%。 圖2.7-最近鄰分類結果圖圖3.錯誤統(tǒng)計圖KNN方法雖然從原理上也依賴于極限定理，但在類別決策時，只與極少量的相鄰樣本有關。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。 該方法的不足之處是計算量較大，因為對每一個待分類的文本都要計算它到全體已知樣本的距離，才能求得它的K個最近鄰點。目前常用的解決方法是事先對已知樣本點進行剪輯，事先去除對分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。5.總結與反思模式分類在現(xiàn)實領域有著非常廣泛的應用。K近鄰算法是模式分類算法中一類常用的算法。本文針對傳統(tǒng)的 KNN 算法的不足之處，提出了兩點改進措施。 1.針對 KNN 算法的計算量大、速度慢的缺點，對訓練數(shù)據(jù)采用了預處理的方法。首先采用某一聚類方法對訓練數(shù)據(jù)進行分類，然后再與K近鄰方法相結合來判斷待測樣本的類別?，F(xiàn)有的方法都是經(jīng)過聚類之后確定類別，按一定的規(guī)則挑選出來具有代表性的數(shù)據(jù)。然后再將這些挑選出來的數(shù)據(jù)作為訓練樣本。但這類方法能去除的數(shù)據(jù)非常有限，因此對計算量大的改進不大，而本文提出的新的算法：在聚類之后，首先計算出來各個類別的中心，然后只需要考慮待測樣本和聚類中心的距離就可以。然后再根據(jù)最終得到的距離的大小判斷該點所屬的類別。通過實例驗證表明，該方法在算法的時間復雜度方面有一定的改進。 2.關于準確度的問題，我們主要是舍棄了原來常用的歐式距離的計算公式，主要考慮了屬性對分類的影響，在歐式距離的計算中引入了權值。盡管權值的確定在一定程度上增加了計算時間的代價，但是從改進分類準確率上來說仍然是必要的，尤其是在數(shù)據(jù)中無關屬性比較多，傳統(tǒng)的分類算法誤差較大的情況下學習特征權值尤其適用。權值的確定也已經(jīng)有了不少的方法，如可以通過神經(jīng)網(wǎng)絡來確定權值等。本文從訓練樣本出發(fā)，逐一統(tǒng)計計算每一個屬性對分類結果的影響，根據(jù)影響的大小來確定權值。通過實例驗證，可知這種方法得到的權值和其他常用的方法相比，在分類準確度方面有一定的提高。 參考文獻1鄧箴,包宏.用模擬退火改進的 KNN 分類算法J計算機與應用化學，2010,27(3):3033072郭躬德，黃杰，陳黎飛.基于 KNN 模型的增量學習算法J模式識別與人工智能，2010，23( 5):7017073黃杰，郭躬德，陳黎飛.增量 KNN 模型的修剪策略研究J小型微型計算機系統(tǒng)，2011，5(5):8458494李歡，焦建民簡化的粒子群優(yōu)化快速 KNN 分類算法J計算機工程與應用，2008，44( 32): 57595王曉曄，王正歐K最近鄰分類技術的改進算法J電子與信息學報，2005，27(3):4874916Guo Gongde，Wang Hui，Bell D，et al Using KNN model for automatic text categorizationJ.Soft Computing-A Fusion of Foundation， Methodologies and Application,2006,10(5):4234307余小鵬，周德翼一種自適應k最近鄰算法的研究J計算機應用研究，2006(2): 7072附件1：源代碼 KNN.m% KNN.m K-最近鄰分類算法%A=xlsread(E:上課機器學習模式識別課件數(shù)據(jù)CORK_STOPPERS.xls,2);f=zeros(150,5);f(:,1:2)=A(1:150,3:4);f1=A(1:50,3:4);f2=A(51:100,3:4);f3=A(101:150,3:4); cls=zeros(150,10);for i=1:150 for j=1:150 cls(i,j)=norm(f(i,1:2)-f(j,1:2); endend %對計算出的每個樣本和其他150個樣本（包括自己）的距離排序，選K=10array=zeros(300,11);for ii=1:150 value,index=sort(cls(ii,:); array(2*ii-1,:)=value(1:11); array(2*ii,:)=index(1:11);end %對每個樣本分類for ii=1:150 a11=length(find(array(2*ii,:)<50); a12=length(find(array(2*ii,:)>50&array(2*ii,:)<100); a13=length(find(array(2*ii,:)>100&array(2*ii,:)<150); if(max(max(a11,a12),a13)=a11) f(ii,3)=1; else if(max(max(a11,a12),a13)=a12) f(ii,3)=2; else f(ii,3)=3; end end end %錯誤計算error=zeros(3,5);for i=1:50 if(f(i,3)=2) error(1,2)=error(1,2)+1; end if(f(i,3)=3) error(1,3)=error(1,3)+1; end if(f(50+i,3)=1) error(2,1)=error(2,1)+1; end if(f(50+i,3)=3) error(2,3)=error(2,3)+1; end if(f(100+i,3)=1) error(3,1)=error(3,1)+1; end if(f(100+i,3)=2) error(3,2)=error(3,2)+1; end endfor k=1:3%D第四列表示錯誤數(shù)error(k,4)=error(k,1)+error(k,2)+error(k,3);error(k,5)=error(k,4)/50;end