數(shù)據(jù)分析課程設(shè)計(jì)論文

1、基于K-均值的ms數(shù)據(jù)聚類分析姓名謝穩(wěn)學(xué)號(hào)1411010122班級(jí)信科14-1成績數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)基于K-均值的ms數(shù)據(jù)聚類分析姓名：謝穩(wěn)信息與計(jì)算科學(xué)14-1班摘要數(shù)據(jù)挖掘在當(dāng)今大數(shù)據(jù)新起的時(shí)代是一項(xiàng)必須掌握的技能，聚類分析是數(shù)據(jù)挖掘技術(shù)中一項(xiàng)重要的研究課題，在很多領(lǐng)域都有具有廣泛的應(yīng)用，如模式識(shí)別、數(shù)據(jù)分析等。聚類分析的目的是將數(shù)據(jù)對(duì)象分成若干個(gè)類或簇，使得在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象之間相似度較低5。通過聚類分析，人們能夠識(shí)別出數(shù)據(jù)分布密集和稀疏的區(qū)域，發(fā)現(xiàn)全局的分布模式以及數(shù)據(jù)屬性之間一些意想不到的相互關(guān)系。本文對(duì)R.A.Fisher在1936年發(fā)表的I

2、ris數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，使用聚類分析中的K-Means對(duì)該問題進(jìn)行進(jìn)一步分析研究。實(shí)驗(yàn)證明兩種方法都是適合的解決此類問題的。關(guān)鍵詞Iris數(shù)據(jù)；聚類分析；K-均值聚類.0前言本文對(duì)聚類分析的原理進(jìn)行闡述，并聚類分析中的譜系聚類法和K-means對(duì)R.A.Fisher的Iris數(shù)據(jù)進(jìn)行了數(shù)據(jù)分析，得到了幾乎相同的結(jié)論，數(shù)據(jù)量太少，回帶誤差大約是20%1 數(shù)據(jù)分析預(yù)處理1.1 數(shù)據(jù)來源分析的數(shù)據(jù)來自R.A.Fisher在1936年發(fā)表的Iris數(shù)據(jù)（見附錄B表B.1）,據(jù)表可知前50個(gè)數(shù)據(jù)為牽牛一類，再50個(gè)數(shù)據(jù)為雜色一類，后50個(gè)數(shù)據(jù)為錦葵一類。將數(shù)據(jù)樣本X變量放入matlab變量名X,保存為m

3、atlab的huaban.mat文件。1.2 數(shù)據(jù)分析采用譜系聚類分析方法和K-means聚類法解決例如Iris類的分類等問題。2 聚類分析2.1 聚類的概述聚類分析是研究對(duì)樣品或指標(biāo)進(jìn)行分類的一種多元統(tǒng)計(jì)方法，是依據(jù)研究對(duì)象的個(gè)體的特征進(jìn)行分類的方法；聚類分析把分類對(duì)象按一定規(guī)則分成若干類，這些類非事先指定的，而是根據(jù)數(shù)據(jù)特征確定的。在同一類中這些對(duì)象在某種意義上趨向于彼此相似，而在不同類中趨向于不相似；職能是建立一種能按照樣品或變量的相似程度進(jìn)行分類的方法。聚類準(zhǔn)則為“親者相聚，疏者相分”。2.2 分類2.2.1 R型聚類分析R型聚類分析是對(duì)變量（指標(biāo)）的分類，其主要作用：不但可以了解個(gè)別

4、變量之間的親疏程數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)度，而且可以了解各個(gè)變量組合之間的親疏程度。2.2.2 Q型聚類分析Q型聚類分析是對(duì)樣品的分類，其主要作用：可以綜合利用多個(gè)變量的信息對(duì)樣本進(jìn)行分析；分類結(jié)果直觀，聚類譜系圖清楚地表現(xiàn)數(shù)值分類結(jié)果；所得結(jié)果比傳統(tǒng)分類方法更細(xì)致、全面、合理。其常用的統(tǒng)計(jì)量是距離。常用的聚類方法為譜系聚類法等。2.3 譜系聚類法2.3.1 概念譜系聚類法是目前應(yīng)用較為廣泛的一種聚類法。譜系聚類是根據(jù)生物分類學(xué)的思想對(duì)研究對(duì)象進(jìn)行分類的方法。在生物分類學(xué)中，分類的單位是：門、綱、目、科、屬、種。其中種是分類的基本單位，分類單位越小，它所包含的生物就越少，生物之間的共同特征就越多。

5、利用這種思想，譜系聚類首先將各樣品自成一類，然后把最相似(距離最近或相似系數(shù)最大)的樣品聚為小類，再將已聚合的小類按各類之間的相似性(用類間距離度量)進(jìn)行再聚合，隨著相似性的減弱，最后將一切子類都聚為一大類，從而得到一個(gè)按相似性大小聚結(jié)起來的一個(gè)譜系圖。2.3.2 選擇距離(參考文獻(xiàn)1p209頁)在使用系統(tǒng)聚類法進(jìn)行聚類的過程中，尤其是Q型聚類是建立在樣品之間距離矩陣的基礎(chǔ)上的，通常需要對(duì)原始數(shù)據(jù)進(jìn)行參考點(diǎn)的建立和去量綱化的處理，然后求出樣品距離矩陣D,我們采用比較廣泛的閔可夫斯基(Minkowski)距離：mp1.=(.二|xik-Xjk|)k1mp1-)2當(dāng)p=2時(shí)日即為歐幾里得CEucl

6、idean)距離。然后進(jìn)行類的搜索、合并于距離矩陣的更新涉及類間距離的計(jì)算，需要事先計(jì)算類與類之間的距離。依據(jù)類問距離不同的計(jì)算方法，我們可以把系統(tǒng)聚類法分為最短距離法、最長距離法、重心法、離差平方和法(ward)等。設(shè)Gp,Gq為前一輪操作中形成的某兩個(gè)聚類，在本輪操作中歸聚為新類Gr=GpuGq則新類Gr與前一輪操作中形成噸，Gq之外的任意一類G,的距離遞推公式如最短距離法drl=min(d*dql),其中l(wèi)=p,q.最長距離法dd=min(d*dq)其中l(wèi)*p,q.中間距離法dM=：d2Pl+"2d2佝dpq，-1-：-0.中心距離法,2np,2nq,2.npnq2nrnrnr

7、drl一dpl+dlqdpq,Hr_np+nq一+數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)其中，丁和5分別為Gp和Gr包含的聚類對(duì)象個(gè)數(shù),Ward法2rlni+np2Q+nq25/7n;dpi+癡dlq-d注意，Ward法要求初始距離矩陣采用歐式距離公式計(jì)算各個(gè)對(duì)象的距離。2.4 得到閔可夫斯基(Minkowski)距離譜系聚類法函數(shù)(見附錄A.1)(1) pdist創(chuàng)建聚類對(duì)象的Minkowski距離矩陣。(2) squarform拉直矩陣Db(3) linkage用D或其拉直矩陣創(chuàng)建信息矩陣G,默認(rèn)的類間距離為最短距離法。(4) dendrogram創(chuàng)建G的譜系聚類圖。(5) cluster創(chuàng)建G的指定個(gè)數(shù)類

8、。2.5 畫譜系聚類圖(見圖2.1)圖2.1Iris花瓣數(shù)據(jù)譜系聚類圖2.6 得出分類2,3,5由圖2.1得出Iris花瓣數(shù)據(jù)截?cái)嗵幙蛇x擇d=1,d=0.8,d=0.666對(duì)應(yīng)的分類個(gè)數(shù)為2.7 cluster創(chuàng)建G的指定個(gè)數(shù)類。(matlab程序見A.3)2.7.1 分3類圖(見圖2.2)數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)第二類3.5*米米*12.5*米米*舉簿祥來*舉來*米米米布米*東*來奈來米米素奈米米*率率*米磷基類*來案崇*第一類一*柒-*44.555.566.57.58圖2.2譜系聚類分析分為三類圖2.8 結(jié)論3類不太恰當(dāng)，應(yīng)該兩類K-means我們將更改距離。由圖2.2將數(shù)據(jù)譜系聚類分析分為三

9、類圖可知，將數(shù)據(jù)分為或者5類更合適，不過也有可能是我們選擇的距離有問題。下面3k-均值聚類3.1 K-Means算法思想1967年Macqueen提出了K-means算法4，基本思想是把數(shù)據(jù)集中的數(shù)據(jù)點(diǎn)隨機(jī)生成k組，把每組的均值作為中心點(diǎn)。重新計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與各組的中心點(diǎn)的相似性，根據(jù)數(shù)據(jù)點(diǎn)相似性的度量準(zhǔn)則，把每個(gè)數(shù)據(jù)點(diǎn)重新分組，計(jì)算每組新的均值作為中心點(diǎn)。不斷重復(fù)上述過程，直到中心點(diǎn)的均值收斂，停止迭代過程。K-means算法是一種比較快速的聚類方法，時(shí)間復(fù)雜度為O(nkt),其中n是數(shù)據(jù)點(diǎn)的數(shù)目，k是分組數(shù)目，t是迭代次數(shù)。K-means算法也存在不足，最大問題要指定分組數(shù)目并且在運(yùn)行過程

10、中容易導(dǎo)致局部最優(yōu)。3.1.1 K-均值算法K-均值算法是一種已知聚類個(gè)數(shù)的“無監(jiān)督學(xué)習(xí)”算法。首先指定表示聚類個(gè)數(shù)的K值，然后對(duì)數(shù)據(jù)集聚類，算法結(jié)束時(shí)用K個(gè)聚類中心表示聚類結(jié)果。對(duì)于設(shè)定的目標(biāo)準(zhǔn)則函數(shù)，通過向目標(biāo)準(zhǔn)則函數(shù)值減小的方向進(jìn)行迭代更新，目標(biāo)準(zhǔn)則函數(shù)值達(dá)到極小值時(shí)算法結(jié)束，得到較優(yōu)的聚類結(jié)果。設(shè)數(shù)據(jù)集為X=ix"xiRd；,代距離中心為V1,V2,.,Vk。令Cj(j=1,2,.,k)表示代聚類的類別，則:數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)、，.1Vi='、x(l)IG|xCi定義目標(biāo)準(zhǔn)則函數(shù)為：k|C|SSE=Zdd(xj,Vi)(2)i1j1其中|CiI表示Ci類包含樣本的個(gè)

11、數(shù)，使用歐式距離dXi，Xj=(X-Xj)(Xi-Xj)T(3)度量樣本間的相似性。歐式距離適用于類內(nèi)數(shù)據(jù)對(duì)象符合超球形分布的情況，目標(biāo)準(zhǔn)則函數(shù)SSEI示為每個(gè)數(shù)據(jù)對(duì)象到相應(yīng)聚類中心距離的平方和，即聚類均方誤差的最小值。3.1.2 K-均值算法的流程如下：(1)隨機(jī)選取K個(gè)初始聚類中心V1,V2,.,Vk;(2)按照最小距離原則，對(duì)數(shù)據(jù)集聚類，確定每個(gè)樣本的類屬關(guān)系；(3)使用公式(1)更新K個(gè)簇的中心；(4)重復(fù)執(zhí)行(2)到(4),直到目標(biāo)準(zhǔn)則函數(shù)收斂或聚類中心穩(wěn)定。顯然，初始聚類中心對(duì)K-均值算法產(chǎn)生很大的影響，簇集中易存在平均誤差較大的簇，聚類結(jié)果僅能收斂到局部最優(yōu)。即使選取不同的初始聚

12、類中心執(zhí)行多次K-均值算法，也只是在龐大的初值空間里進(jìn)行簡單的搜索，聚類結(jié)果很難達(dá)到全局最優(yōu)。當(dāng)數(shù)據(jù)集中存在較多噪音或孤立點(diǎn)時(shí)，已有的初始聚類中心優(yōu)化方法很難發(fā)現(xiàn)合適的初始聚類中心。3.2 復(fù)合相關(guān)系數(shù)的計(jì)算(計(jì)算過程見附錄A.4)分別記最短、最長、類平均、重心、離差平方和距離為G1、G2、G3G4G5,相對(duì)應(yīng)的復(fù)合相關(guān)系數(shù)分別記為R1、R2、R3、R4R5,以歐式距離為樣本間距離計(jì)算得到表3-1表3-1復(fù)合相關(guān)系數(shù)R1R2R3R4R50.86390.72760.87680.87700.8728由表2可知以重心距離進(jìn)行聚類分析效果應(yīng)該最為理想3.3聚類結(jié)果(見圖3.1)以重心距離為類間距離進(jìn)行

13、譜系聚類分析得到(matlab程序參考附錄A.1-4)數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)圖3.1譜系聚類圖3.4譜系聚類結(jié)果（見圖3.2）3.5系宰米米米興*米第琶類*44.555.566.57第類一米M*米米帶東送來卓7.58圖3.2譜系聚類結(jié)果3.4K-Means聚類結(jié)果（見圖3.3）4.5米米數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)第二類*米米*米*來來*辛*殺逑米米辛辛辛*米來*第二類*2L44.55.56.5圖3.3K-Means聚類結(jié)果3.5分析結(jié)果由圖3.2結(jié)果可得第1類有36個(gè)樣本，第2類有64個(gè)樣本，第3類有50個(gè)樣本，由圖3.3可知第1類有62個(gè)樣本，第2類有49個(gè)樣本，第3類有39個(gè)樣本兩種方法基本得到的

14、結(jié)論基本一致，不過都不太理想。這可能是數(shù)據(jù)量太小了的原因。大數(shù)據(jù)時(shí)代，需要大量的數(shù)據(jù)。參考文獻(xiàn)1包研科.數(shù)據(jù)分析教程.北京：清華大學(xué)出版社，20112曾繁慧.數(shù)值分析.徐州：中國礦業(yè)大學(xué)出版社，20093袁方，周志勇，宋鑫.初始聚類中心優(yōu)化的K-mean既發(fā)J.計(jì)算機(jī)工程，2007,33(3):65-66(4 MacQueen,James."Somemethodsforclassificationandanalysisofmultivariateobservations."ProceedingsofthefifthBerkeleysymposiumonmathematica

15、lstatisticsandprobability.Vol.1.No.281-297.1967.5余立強(qiáng).LAMP架構(gòu)搭建與網(wǎng)站運(yùn)行實(shí)例J.網(wǎng)絡(luò)與信息，2011(8):50-526吳夙慧，成穎，鄭彥寧，潘云濤.K-means算法研究綜述J.現(xiàn)代圖書情報(bào)技術(shù)，2011,(5 :28-35.數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)附錄A.1譜系聚類法函數(shù)functionf=test4()loadhuaban.matD=pdist(X,'minkowski');G=linkage(D);dendrogram(G);T=cluster(G,3)A.2自編k-means聚類分析xwKmeans.m函數(shù)fun

16、ctioncid,nr,centers=xwKmeans(x,k,nc)%CID,NR,CENTERS=CSKMEANS(X,K,NC)PerformsK-means%X輸入聚合數(shù)據(jù)%K通過觀察得到的經(jīng)驗(yàn)分組數(shù)據(jù)%每行一個(gè)觀測，N聚類指數(shù)，來源于初始的聚類中心值，默認(rèn)情況下為隨機(jī)的觀測%輸出：IDX為最終分類%nr為每個(gè)每個(gè)聚合的中心值%CENTERSisamatrix,whereeachrow%correspondstoaclustercenter.n,d=size(x);ifnargin<3ind=ceil(n*rand(1,k);nc=x(ind,:)+randn(k,d);end

17、cid=zeros(1,n);oldcid=ones(1,n);nr=zeros(1,k);maxiter=100;iter=1;whileisequal(cid,oldcid)&iter<maxiterfori=1:ndist=sum(repmat(x(i,:),k,1)-nc).A2,2);m,ind=min(dist);cid(i)=ind;endfori=1:kind=find(cid=i);nc(i,:)=mean(x(ind,:);nr(i)=length(ind);end數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)iter=iter+1;endmaxiter=2;iter=1;move=1

18、;whileiter<maxiter&move=0move=0;fori=1:n%找到與所有聚合的距離dist=sum(repmat(x(i,:),k,1)-nc).A2,2);r=cid(i);dadj=nr./(nr+1).*dist'm,ind=min(dadj);%最小的就是聚合的分類ifind=rcid(i)=ind;ic=find(cid=ind);nc(ind,:)=mean(x(ic,:);move=1;endenditer=iter+1;endcenters=nc;ifmove=0disp('初始化聚類后沒有點(diǎn)移動(dòng),)elsedisp('

19、初始化后開始進(jìn)行聚合分類,)endcid=cid'A.3k-means聚類分析分類圖matlab的main.m函數(shù)functionf=main(X,k)n,d=size(X);bn=round(n/k*rand);%第一個(gè)隨機(jī)數(shù)在前1/K的范圍內(nèi)%；表不按列顯木，都好表不按行顯布%初始聚類中心%X(bn,:)選擇某一行數(shù)據(jù)作為聚類中心，其列值為全部%炊據(jù)源，k聚類數(shù)目，nc表示k個(gè)初始化聚類中心%cid表示每個(gè)數(shù)據(jù)屬于哪一類，nr表示每一類的個(gè)數(shù)，centers表示聚類中心cid,nr,centers=xwKmeans(X,k)fori=1:150ifcid(i)=1數(shù)據(jù)分析課程設(shè)計(jì)作

20、業(yè)plot(X(i,1),X(i,2),'r*')%顯示第一類holdonelseifcid(i)=2,plot(X(i,1),X(i,2),'b*')%顯示第二類plot(X(i,2),'b*')%顯示第一類holdonelseifcid(i)=3,plot(X(i,1),X(i,2),'g*')%t示第三類%plot(X(i,2),'g*')%顯示第一類holdonelseifcid(i)=4,plot(X(i,1),X(i,2),'k*')減示第四類%plot(X(i,2),'k*&#

21、39;)%顯示第一類holdonendendendendendtext(7.5,3.5,'第一類')；text(5,4,'第二類');text(5.5,2.5，第三類');text(-1,-1,'第四類)；A.4相關(guān)系數(shù)matllab指令d=pdist(x);G1=linkage(d);G2=linkage(d,'complete');G3=linkage(d,'centroid');G4=linkage(d,'average');G5=linkage(d,'ward');R1=co

22、phenet(G1,d);R2=cophenet(G2,d);R3=cophenet(G3,d);R4=cophenet(G4,d);R5=cophenet(G5,d);B.1:R.A.Fisher在1936年發(fā)表的bis數(shù)據(jù)表B.1Iris數(shù)據(jù)樣本號(hào)萼片長萼片寬花瓣長花瓣寬不慨15.13.51.40.2牽牛24.931.40.2牽牛數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)34.73.21.30.2牽牛44.63.11.50.2牽牛553.61.40.2牽牛65.43.91.70.4牽牛74.63.41.40.3牽牛853.41.50.2牽牛94.42.91.40.2牽牛104.93.11.50.1牽牛115.4

23、3.71.50.2牽牛124.83.41.60.2牽牛134.831.40.1牽牛144.331.10.1牽牛155.841.20.2牽牛165.74.41.50.4牽牛175.43.91.30.4牽牛185.13.51.40.3牽牛195.73.81.70.3牽牛205.13.81.50.3牽牛215.43.41.70.2牽牛225.13.71.50.4牽牛234.63.610.2牽牛245.13.31.70.5牽牛254.83.41.90.2牽牛26531.60.2牽牛2753.41.60.4牽牛285.23.51.50.2牽牛295.23.41.40.2牽牛304.73.21.60.2牽

24、牛314.83.11.60.2牽牛325.43.41.50.4牽牛335.24.11.50.1牽牛345.54.21.40.2牽牛354.93.11.50.2牽牛3653.21.20.2牽牛375.53.51.30.2牽牛384.93.61.40.1牽牛394.431.30.2牽牛405.13.41.50.2牽牛4153.51.30.3牽牛424.52.31.30.3牽牛434.43.21.30.2牽牛4453.51.60.6牽牛455.13.81.90.4牽牛464.831.40.3牽牛數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)475.13.81.60.2牽牛484.63.21.40.2牽牛495.33.71.5

25、0.2牽牛5053.31.40.2牽牛5173.24.71.4雜色526.43.24.51.5雜色536.93.14.91.5雜色545.52.341.3雜色556.52.84.61.5雜色565.72.84.51.3雜色576.33.34.71.6雜色584.92.43.31雜色596.62.94.61.3雜色605.22.73.91.4雜色61523.51雜色625.934.21.5雜色6362.241雜色646.12.94.71.4雜色655.62.93.61.3雜色666.73.14.41.4雜色675.634.51.5雜色685.82.74.11雜色696.22.24.51.5雜色7

26、05.62.53.91.1雜色715.93.24.81.8雜色726.12.841.3雜色736.32.54.91.5雜色746.12.84.71.2雜色756.42.94.31.3雜色766.634.41.4雜色776.82.84.81.4雜色786.7351.7雜色7962.94.51.5雜色805.72.63.51雜色815.52.43.81.1雜色825.52.43.71雜色835.82.73.91.2雜色8462.75.11.6雜色855.434.51.5雜色8663.44.51.6雜色876.73.14.71.5雜色886.32.34.41.3雜色895.634.11.3雜色905.52.541.3雜色數(shù)據(jù)分析課程設(shè)計(jì)作業(yè)915.52.64.41.2雜色926.134.61.4雜色935.82.641.2雜色9452.33.31雜色955.62.74.21.3雜色965.734.2