數(shù)據(jù)挖掘?qū)嶒?yàn)報(bào)告

1、大數(shù)據(jù)理論與技術(shù)讀書報(bào)告 -K最近鄰分類算法指導(dǎo)老師 : 陳 莉 學(xué)生姓名 : 李陽(yáng)帆 學(xué) 號(hào) : 201531467 專 業(yè) : 計(jì)算機(jī)技術(shù) 日 期 : 2016年8月31日 摘 要 數(shù)據(jù)挖掘是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究的知識(shí)領(lǐng)域，是將人工智能技術(shù)和數(shù)據(jù)庫(kù)技術(shù)緊密結(jié)合，讓計(jì)算機(jī)幫助人們從龐大的數(shù)據(jù)中智能地、自動(dòng)地提取出有價(jià)值的知識(shí)模式，以滿足人們不同應(yīng)用的需要。K 近鄰算法（KNN）是基于統(tǒng)計(jì)的分類方法，是大數(shù)據(jù)理論與分析的分類算法中比較常用的一種方法。該算法具有直觀、無(wú)需先驗(yàn)統(tǒng)計(jì)知識(shí)、無(wú)師學(xué)習(xí)等特點(diǎn)，目前已經(jīng)成為數(shù)據(jù)挖掘技術(shù)的理論和應(yīng)用研究方法之一。本文主要研究了 K 近鄰分類算法，首先簡(jiǎn)要地

2、介紹了數(shù)據(jù)挖掘中的各種分類算法，詳細(xì)地闡述了K 近鄰算法的基本原理和應(yīng)用領(lǐng)域，最后在matlab環(huán)境里仿真實(shí)現(xiàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，提出了改進(jìn)的方法。 關(guān)鍵詞：K 近鄰，聚類算法，權(quán)重，復(fù)雜度，準(zhǔn)確度 1.引言12.研究目的與意義13.算法思想24.算法實(shí)現(xiàn)24.1 參數(shù)設(shè)置24.2數(shù)據(jù)集24.3實(shí)驗(yàn)步驟34.4實(shí)驗(yàn)結(jié)果與分析35.總結(jié)與反思4附件161.引言隨著數(shù)據(jù)庫(kù)技術(shù)的飛速發(fā)展，人工智能領(lǐng)域的一個(gè)分支機(jī)器學(xué)習(xí)的研究自 20 世紀(jì) 50 年代開始以來(lái)也取得了很大進(jìn)展。用數(shù)據(jù)庫(kù)管理系統(tǒng)來(lái)存儲(chǔ)數(shù)據(jù)，用機(jī)器學(xué)習(xí)的方法來(lái)分析數(shù)據(jù)，挖掘大量數(shù)據(jù)背后的知識(shí)，這兩者的結(jié)合促成了數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)（Kn

3、owledge Discovery in Databases，簡(jiǎn)記 KDD）的產(chǎn)生，也稱作數(shù)據(jù)挖掘（Data Ming，簡(jiǎn)記 DM）。 數(shù)據(jù)挖掘是信息技術(shù)自然演化的結(jié)果。信息技術(shù)的發(fā)展大致可以描述為如下的過(guò)程：初期的是簡(jiǎn)單的數(shù)據(jù)收集和數(shù)據(jù)庫(kù)的構(gòu)造；后來(lái)發(fā)展到對(duì)數(shù)據(jù)的管理，包括：數(shù)據(jù)存儲(chǔ)、檢索以及數(shù)據(jù)庫(kù)事務(wù)處理；再后來(lái)發(fā)展到對(duì)數(shù)據(jù)的分析和理解，這時(shí)候出現(xiàn)了數(shù)據(jù)倉(cāng)庫(kù)技術(shù)和數(shù)據(jù)挖掘技術(shù)。數(shù)據(jù)挖掘是涉及數(shù)據(jù)庫(kù)和人工智能等學(xué)科的一門當(dāng)前相當(dāng)活躍的研究領(lǐng)域。 數(shù)據(jù)挖掘是機(jī)器學(xué)習(xí)領(lǐng)域內(nèi)廣泛研究的知識(shí)領(lǐng)域，是將人工智能技術(shù)和數(shù)據(jù)庫(kù)技術(shù)緊密結(jié)合，讓計(jì)算機(jī)幫助人們從龐大的數(shù)據(jù)中智能地、自動(dòng)地抽取出有價(jià)值的知識(shí)模式

4、，以滿足人們不同應(yīng)用的需要1。目前，數(shù)據(jù)挖掘已經(jīng)成為一個(gè)具有迫切實(shí)現(xiàn)需要的很有前途的熱點(diǎn)研究課題。2.研究目的與意義近鄰方法是在一組歷史數(shù)據(jù)記錄中尋找一個(gè)或者若干個(gè)與當(dāng)前記錄最相似的歷史紀(jì)錄的已知特征值來(lái)預(yù)測(cè)當(dāng)前記錄的未知或遺失特征值14。近鄰方法是數(shù)據(jù)挖掘分類算法中比較常用的一種方法。K 近鄰算法（簡(jiǎn)稱 KNN）是基于統(tǒng)計(jì)的分類方法15。KNN 分類算法根據(jù)待識(shí)樣本在特征空間中 K 個(gè)最近鄰樣本中的多數(shù)樣本的類別來(lái)進(jìn)行分類，因此具有直觀、無(wú)需先驗(yàn)統(tǒng)計(jì)知識(shí)、無(wú)師學(xué)習(xí)等特點(diǎn)，從而成為非參數(shù)分類的一種重要方法。 大多數(shù)分類方法是基于向量空間模型的。當(dāng)前在分類方法中，對(duì)任意兩個(gè)向量：x=和存在 3

5、種最通用的距離度量：歐氏距離、余弦距離16和內(nèi)積17。有兩種常用的分類策略：一種是計(jì)算待分類向量到所有訓(xùn)練集中的向量間的距離：如 K 近鄰選擇K個(gè)距離最小的向量然后進(jìn)行綜合，以決定其類別。另一種是用訓(xùn)練集中的向量構(gòu)成類別向量，僅計(jì)算待分類向量到所有類別向量的距離，選擇一個(gè)距離最小的類別向量決定類別的歸屬。很明顯，距離計(jì)算在分類中起關(guān)鍵作用。由于以上 3 種距離度量不涉及向量的特征之間的關(guān)系，這使得距離的計(jì)算不精確，從而影響分類的效果。3.算法思想K最近鄰(K-Nearest Neighbor,KNN)算法，是著名的模式識(shí)別統(tǒng)計(jì)學(xué)方法，在機(jī)器學(xué)習(xí)分類算法中占有相當(dāng)大的地位。它是一個(gè)理論上比較成熟

6、的方法。既是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一，也是基于實(shí)例的學(xué)習(xí)方法中最基本的，又是最好的文本分類算法之一。其基本思想是：假設(shè)每一個(gè)類包含多個(gè)樣本數(shù)據(jù)，而且每個(gè)數(shù)據(jù)都有一個(gè)唯一的類標(biāo)記表示這些樣本是屬于哪一個(gè)分類， KNN就是計(jì)算每個(gè)樣本數(shù)據(jù)到待分類數(shù)據(jù)的距離，如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來(lái)決定待分樣本所屬的類別。K-最臨近分類方法存放所有的訓(xùn)練樣本，在接受待分類的新樣本之前不需構(gòu)造模型，并且直到新的（未標(biāo)記的）樣本需要分類時(shí)才建立分類。K-最臨近分類基于類比學(xué)習(xí)

7、，其訓(xùn)練樣本由N維數(shù)值屬性描述，每個(gè)樣本代表N維空間的一個(gè)點(diǎn)。這樣，所有訓(xùn)練樣本都存放在N維模式空間中。給定一個(gè)未知樣本，k-最臨近分類法搜索模式空間，找出最接近未知樣本的K個(gè)訓(xùn)練樣本。這K個(gè)訓(xùn)練樣本是未知樣本的K個(gè)“近鄰”?！芭R近性”又稱為相異度（Dissimilarity），由歐幾里德距離定義，其中兩個(gè)點(diǎn) X（x1,x2,xn）和Y（y1,y2,yn）的歐幾里德距離是：未知樣本被分配到K個(gè)最臨近者中最公共的類。在最簡(jiǎn)單的情況下，也就是當(dāng)K=1時(shí)，未知樣本被指定到模式空間中與之最臨近的訓(xùn)練樣本的類。4.算法實(shí)現(xiàn)4.1 參數(shù)設(shè)置K值的設(shè)定K值設(shè)置過(guò)小會(huì)降低分類精度；若設(shè)置過(guò)大，且測(cè)試樣本屬于訓(xùn)

8、練集中包含數(shù)據(jù)較少的類，則會(huì)增加噪聲，降低分類效果。通常，K值的設(shè)定采用交叉檢驗(yàn)的方式（以K=1為基準(zhǔn)），通過(guò)查找相關(guān)資料，K一般低于訓(xùn)練樣本數(shù)的平方根，本實(shí)驗(yàn)中的訓(xùn)練樣本數(shù)為100個(gè)，因此選取k=7。4.2數(shù)據(jù)集本文的實(shí)驗(yàn)數(shù)據(jù)采用軟木塞的數(shù)據(jù)集，軟木塞的樣本可分為三類，分別用1，2，3代表，共150個(gè)樣本，我們選取其中的100個(gè)樣本為訓(xùn)練集，其余的50個(gè)樣本為測(cè)試集。每個(gè)樣本均包含10維特征，由于用10維特征計(jì)算量太大，本實(shí)驗(yàn)的目的主要是明白K-最近鄰算法的思想，重點(diǎn)不在計(jì)算，因此我們選取其中的兩個(gè)屬性作為本實(shí)驗(yàn)的數(shù)據(jù)，實(shí)驗(yàn)數(shù)據(jù)的部分截圖如圖1所示。圖1.部分實(shí)驗(yàn)數(shù)據(jù) 4.3實(shí)驗(yàn)步驟第一步，

9、初始化距離為最大值。第二步，計(jì)算未知樣本和每個(gè)訓(xùn)練樣本的距離dist。第三步，得到目前K個(gè)最臨近樣本中的最大距離maxdist。第四步，如果dist小于maxdist，則將該訓(xùn)練樣本作為K-最近鄰樣本。第五步，重復(fù)步驟2、3、4，直到未知樣本和所有訓(xùn)練樣本的距離都算完。第六步，統(tǒng)計(jì)K-最近鄰樣本中每個(gè)類標(biāo)號(hào)出現(xiàn)的次數(shù)。第七步，選擇出現(xiàn)頻率最大的類標(biāo)號(hào)作為未知樣本的類標(biāo)號(hào)。4.4實(shí)驗(yàn)結(jié)果與分析按照上述實(shí)驗(yàn)步驟，在matlab中仿真實(shí)現(xiàn)k-近鄰分類算法的結(jié)果如下圖2所示，圖中的第一列數(shù)據(jù)表示樣本編號(hào)，第二列和第三列表示軟如塞數(shù)據(jù)的兩位特征的值，第三列的數(shù)字表示本實(shí)驗(yàn)的分類結(jié)果圖，第四列表示樣本實(shí)際

10、所屬類別。圖3中列出了詳細(xì)錯(cuò)誤信息。第一行和第一列表示樣本類別，第i行第j列的元素表示第i類樣本被分為第j類樣本的個(gè)數(shù)（2i,j4），第五列表示每類樣本分類錯(cuò)誤總數(shù)，第六列表示錯(cuò)誤率。由圖中數(shù)據(jù)易得，本實(shí)驗(yàn)的平均正確率為86.7%。 圖2.7-最近鄰分類結(jié)果圖圖3.錯(cuò)誤統(tǒng)計(jì)圖KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本的不平衡問(wèn)題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來(lái)確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來(lái)說(shuō)，KNN方法較其他方法更為適合。 該方法的不足之處是計(jì)算量較

11、大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。5.總結(jié)與反思模式分類在現(xiàn)實(shí)領(lǐng)域有著非常廣泛的應(yīng)用。K近鄰算法是模式分類算法中一類常用的算法。本文針對(duì)傳統(tǒng)的 KNN 算法的不足之處，提出了兩點(diǎn)改進(jìn)措施。 1.針對(duì) KNN 算法的計(jì)算量大、速度慢的缺點(diǎn)，對(duì)訓(xùn)練數(shù)據(jù)采用了預(yù)處理的方法。首先采用某一聚類方法對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類，然后再與K近鄰方法相結(jié)合來(lái)判斷待測(cè)樣本的類別?，F(xiàn)有的方法都是經(jīng)

12、過(guò)聚類之后確定類別，按一定的規(guī)則挑選出來(lái)具有代表性的數(shù)據(jù)。然后再將這些挑選出來(lái)的數(shù)據(jù)作為訓(xùn)練樣本。但這類方法能去除的數(shù)據(jù)非常有限，因此對(duì)計(jì)算量大的改進(jìn)不大，而本文提出的新的算法：在聚類之后，首先計(jì)算出來(lái)各個(gè)類別的中心，然后只需要考慮待測(cè)樣本和聚類中心的距離就可以。然后再根據(jù)最終得到的距離的大小判斷該點(diǎn)所屬的類別。通過(guò)實(shí)例驗(yàn)證表明，該方法在算法的時(shí)間復(fù)雜度方面有一定的改進(jìn)。 2.關(guān)于準(zhǔn)確度的問(wèn)題，我們主要是舍棄了原來(lái)常用的歐式距離的計(jì)算公式，主要考慮了屬性對(duì)分類的影響，在歐式距離的計(jì)算中引入了權(quán)值。盡管權(quán)值的確定在一定程度上增加了計(jì)算時(shí)間的代價(jià)，但是從改進(jìn)分類準(zhǔn)確率上來(lái)說(shuō)仍然是必要的，尤其是在數(shù)

13、據(jù)中無(wú)關(guān)屬性比較多，傳統(tǒng)的分類算法誤差較大的情況下學(xué)習(xí)特征權(quán)值尤其適用。權(quán)值的確定也已經(jīng)有了不少的方法，如可以通過(guò)神經(jīng)網(wǎng)絡(luò)來(lái)確定權(quán)值等。本文從訓(xùn)練樣本出發(fā)，逐一統(tǒng)計(jì)計(jì)算每一個(gè)屬性對(duì)分類結(jié)果的影響，根據(jù)影響的大小來(lái)確定權(quán)值。通過(guò)實(shí)例驗(yàn)證，可知這種方法得到的權(quán)值和其他常用的方法相比，在分類準(zhǔn)確度方面有一定的提高。 參考文獻(xiàn)1鄧箴,包宏.用模擬退火改進(jìn)的 KNN 分類算法J計(jì)算機(jī)與應(yīng)用化學(xué)，2010,27(3):3033072郭躬德，黃杰，陳黎飛.基于 KNN 模型的增量學(xué)習(xí)算法J模式識(shí)別與人工智能，2010，23( 5):7017073黃杰，郭躬德，陳黎飛.增量 KNN 模型的修剪策略研究J小型微

14、型計(jì)算機(jī)系統(tǒng)，2011，5(5):8458494李歡，焦建民簡(jiǎn)化的粒子群優(yōu)化快速 KNN 分類算法J計(jì)算機(jī)工程與應(yīng)用，2008，44( 32): 57595王曉曄，王正歐K最近鄰分類技術(shù)的改進(jìn)算法J電子與信息學(xué)報(bào)，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余小鵬，

15、周德翼一種自適應(yīng)k最近鄰算法的研究J計(jì)算機(jī)應(yīng)用研究，2006(2): 7072附件1：源代碼 KNN.m% KNN.m K-最近鄰分類算法%A=xlsread('E:上課機(jī)器學(xué)習(xí)模式識(shí)別課件數(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 %對(duì)計(jì)

16、算出的每個(gè)樣本和其他150個(gè)樣本（包括自己）的距離排序，選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 %對(duì)每個(gè)樣本分類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 %錯(cuò)誤計(jì)算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,