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

1、大數(shù)據(jù)理論與技術(shù)讀書報(bào)告K最近鄰分類算法指導(dǎo)老師:陳莉?qū)W生姓名:李陽帆學(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ù)庫技術(shù)緊密結(jié)合,讓計(jì)算機(jī)幫助人們從龐大得數(shù)據(jù)中智能地、自動(dòng)地提取出有價(jià)值得知識(shí)模式，以滿足人們不同應(yīng)用得需要。K近鄰算法（KNN）就是基于統(tǒng)計(jì)得分類方法，就是大數(shù)據(jù)理論與分析得分類算法中比較常用得一種方法。該算法具有直觀、無需先驗(yàn)統(tǒng)計(jì)知識(shí)、無師學(xué)習(xí)等特點(diǎn)，目前已經(jīng)成為數(shù)據(jù)挖掘技術(shù)得理論與應(yīng)用研究方法之一。本文主要研究了K近鄰分類算法,首先簡(jiǎn)要地介紹了數(shù)據(jù)挖掘中得各種分類算法，詳細(xì)地闡述了

2、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、引言02、研究目得與意義。錯(cuò)誤!未定義書簽。3、算法思想。錯(cuò)誤!未定義書簽。4、算法實(shí)現(xiàn)1。4、1參數(shù)設(shè)置。錯(cuò)誤!未定義書簽。4、2數(shù)據(jù)集1。4、3實(shí)驗(yàn)步驟。錯(cuò)誤!未定義書簽。4、4實(shí)驗(yàn)結(jié)果與分析。錯(cuò)誤!未定義書簽。5、總結(jié)與反思。錯(cuò)誤!未定義書簽。附件1。錯(cuò)誤!未定義書簽。1、引言隨著數(shù)據(jù)庫技術(shù)得飛速發(fā)展，人工智能領(lǐng)域得一個(gè)分支機(jī)器學(xué)習(xí)得研究自20世紀(jì)50年代開始以來也取得了很大進(jìn)展。用數(shù)據(jù)庫管理系統(tǒng)來存儲(chǔ)數(shù)據(jù)，用機(jī)器學(xué)習(xí)得方法來分析數(shù)據(jù)

3、,挖掘大量數(shù)據(jù)背后得知識(shí),這兩者得結(jié)合促成了數(shù)據(jù)庫中得知識(shí)發(fā)現(xiàn)(KnowledgeDiscoveryinDatabases，簡(jiǎn)記KDD)得產(chǎn)生，也稱作數(shù)據(jù)挖掘(DataMing，簡(jiǎn)記DM)。數(shù)據(jù)挖掘就是信息技術(shù)自然演化得結(jié)果。信息技術(shù)得發(fā)展大致可以描述為如下得過程:初期得就是簡(jiǎn)單得數(shù)據(jù)收集與數(shù)據(jù)庫得構(gòu)造;后來發(fā)展到對(duì)數(shù)據(jù)得管理，包括：數(shù)據(jù)存儲(chǔ)、檢索以及數(shù)據(jù)庫事務(wù)處理；再后來發(fā)展到對(duì)數(shù)據(jù)得分析與理解，這時(shí)候出現(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)廣泛研究得知識(shí)領(lǐng)域，就是將人工智能技術(shù)與數(shù)據(jù)庫技術(shù)緊密結(jié)合，讓計(jì)

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

5、模型得。當(dāng)前在分類方法中，對(duì)任意兩個(gè)向量：x=與存在3種最通用得距離度量：歐氏距離、余弦距離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-NearestNeighbor,KNN)算法，就是著名得模式識(shí)別統(tǒng)計(jì)學(xué)方法,在機(jī)器學(xué)習(xí)

6、分類算法中占有相當(dāng)大得地位.它就是一個(gè)理論上比較成熟得方法。既就是最簡(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è)樣本得類別來決定待分樣本所屬得類別.K最臨近分類方法存放所有得訓(xùn)練樣本,在接受待分類得新樣本之前不需構(gòu)造模型，并且直到新得（未

7、標(biāo)記得）樣本需要分類時(shí)才建立分類K最臨近分類基于類比學(xué)習(xí)，其訓(xùn)練樣本由N維數(shù)值屬性描述，每個(gè)樣本代表N維空間得一個(gè)點(diǎn)。這樣，所有訓(xùn)練樣本都存放在N維模式空間中給定一個(gè)未知樣本,k最臨近分類法搜索模式空間，找出最接近未知樣本得K個(gè)訓(xùn)練樣本。這K個(gè)訓(xùn)練樣本就是未知樣本得K個(gè)“近鄰”“臨近性”又稱為相異度（Dissimi1arity）,由歐幾里德距離定義，其中兩個(gè)點(diǎn)X（x，x?,乂丿與丫丫，丫）得歐幾里德距離就是：n未知樣本被分配到K個(gè)最臨近者中最公共得類在最簡(jiǎn)單得情況下，也就就是當(dāng)K=1時(shí),未知樣本被指定到模式空間中與之最臨近得訓(xùn)練樣本得類.4、算法實(shí)現(xiàn)4、1參數(shù)設(shè)置K值得設(shè)定K值設(shè)置過小會(huì)降低分

8、類精度;若設(shè)置過大，且測(cè)試樣本屬于訓(xùn)練集中包含數(shù)據(jù)較少得類，則會(huì)增加噪聲，降低分類效果。通常，K值得設(shè)定采用交叉檢驗(yàn)得方式（以K=1為基準(zhǔn)），通過查找相關(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所示。12

9、221556123200912411461251786626925027165632814551296324圖1、部分實(shí)驗(yàn)數(shù)據(jù)4、3實(shí)驗(yàn)步驟第一步，初始化距離為最大值。第二步，計(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é)果

10、如下圖2所示,圖中得第一列數(shù)據(jù)表示樣本編號(hào)，第二列與第三列表示軟如塞數(shù)據(jù)得兩位特征得值,第三列得數(shù)字表示本實(shí)驗(yàn)得分類結(jié)果圖,第四列表示樣本實(shí)際所屬類別。圖3中列出了詳細(xì)錯(cuò)誤信息第一行與第一列表示樣本類別，第i行第j列得元素表示第i類樣本被分為第j類樣本得個(gè)數(shù)(2i,j4)，第五列表示每類樣本分類錯(cuò)誤總數(shù)，第六列表示錯(cuò)誤率。由圖中數(shù)據(jù)易得，本實(shí)驗(yàn)得平均正確率為86、7%。圖2、7最近鄰分類結(jié)果圖12345103030.0600230190.1800308080.1600圖3、錯(cuò)誤統(tǒng)計(jì)圖KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量得相鄰樣本有關(guān)。因此，采用這種方法可以較好地避

11、免樣本得不平衡問題。另外，由于KNN方法主要靠周圍有限得鄰近得樣本，而不就是靠判別類域得方法來確定所屬類別得，因此對(duì)于類域得交叉或重疊較多得待分樣本集來說，KNN方法較其她方法更為適合。該方法得不足之處就是計(jì)算量較大，因?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算法

12、得不足之處，提出了兩點(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é)合來判斷待測(cè)樣本得類別?，F(xiàn)有得方法都就是經(jīng)過聚類之后確定類別，按一定得規(guī)則挑選出來具有代表性得數(shù)據(jù)。然后再將這些挑選出來得數(shù)據(jù)作為訓(xùn)練樣本.但這類方法能去除得數(shù)據(jù)非常有限，因此對(duì)計(jì)算量大得改進(jìn)不大，而本文提出得新得算法:在聚類之后，首先計(jì)算出來各個(gè)類別得中心，然后只需要考慮待測(cè)樣本與聚類中心得距離就可以.然后再根據(jù)最終得到得距離得大小判斷該點(diǎn)所屬得類別。通過實(shí)例驗(yàn)證表明，該方法在算法得時(shí)間復(fù)雜度方面有一定得改進(jìn)。2、關(guān)于準(zhǔn)確度得

13、問題，我們主要就是舍棄了原來常用得歐式距離得計(jì)算公式，主要考慮了屬性對(duì)分類得影響，在歐式距離得計(jì)算中引入了權(quán)值.盡管權(quán)值得確定在一定程度上增加了計(jì)算時(shí)間得代價(jià)，但就是從改進(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)計(jì)計(jì)算每一個(gè)屬性對(duì)分類結(jié)果得影響，根據(jù)影響得大小來確定權(quán)值。通過實(shí)例驗(yàn)證，可知這種方法得到得權(quán)值與其她常用得方法相比，在分類準(zhǔn)確度方面有一定得提高。參考文獻(xiàn)1鄧箴，包宏、用模擬退火改進(jìn)得KNN分類算法J。計(jì)算機(jī)與應(yīng)用化學(xué)，

14、2010,27(3):303-307.2郭躬德，黃杰，陳黎飛、基于KNN模型得增量學(xué)習(xí)算法J。模式識(shí)別與人工智能，2010,23(5):701707。3黃杰，郭躬德，陳黎飛、增量KNN模型得修剪策略研究J.小型微型計(jì)算機(jī)系統(tǒng)，2011,5(5)：845849.4李歡，焦建民.簡(jiǎn)化得粒子群優(yōu)化快速KNN分類算法J。計(jì)算機(jī)工程與應(yīng)用，2008,44(32)：57-59。5王曉曄，王正歐.K最近鄰分類技術(shù)得改進(jìn)算法J。電子與信息學(xué)報(bào)，2005,27(3):487491.6GuoGongde,WangHui,BellD，etal.UsingKNNmodelforautomatictextcategor

15、izationJ、SoftputingAFusionofFoundation,MethodologiesandApplication，2006,10(5)：423-430.7余小鵬，周德翼。一種自適應(yīng)k最近鄰算法得研究J.計(jì)算機(jī)應(yīng)用研究，2006(2):7072。附件1:源代碼KNN、m%KNN、mK-最近鄰分類算法%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)；fl=A(1：50，3：4)；f2=A(51:100，3：4);f3=A(101:150,3：4);cls=ze

16、ros(150，10);fori=1：150forj=1:150cIs(i,j)=norm(f(i,1：2)-f(j,1：2);endend%對(duì)計(jì)算出得每個(gè)樣本與其她150個(gè)樣本(包括自己)得距離排序,選K=10array=zeros(300,11)；forii=1：150valuejndex=sort(cls(ii,：);array(2*ii1,：)=value(1：11)；array(2*ii,：)=index(1:11)；end對(duì)每個(gè)樣本分類forii=1:150a11=length(find(array(2ii,:)50);a12=length(find(array(2ii,:)50array(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;elseif(max(max(a11,a12),a13)=a12)f(ii,3)=2;elsef(ii,3)=3；endendend%錯(cuò)誤計(jì)算error=zeros(3,5);fori=1：50if(f(i，3)=2)error(1,2)=error(1,2)+1；endif(f(i,3)=3)error(1,3)=error(1,3)+1