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

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

2、ris數(shù)據(jù)進行數(shù)據(jù)挖掘，使用聚類分析中的K-Means對該問題進行進一步分析研究。實驗證明兩種方法都是適合的解決此類問題的。關(guān)鍵詞Iris數(shù)據(jù)；聚類分析；K-均值聚類.0前言本文對聚類分析的原理進行闡述，并聚類分析中的譜系聚類法和K-means對R.A.Fisher的Iris數(shù)據(jù)進行了數(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個數(shù)據(jù)為牽牛一類，再50個數(shù)據(jù)為雜色一類，后50個數(shù)據(jù)為錦葵一類。將數(shù)據(jù)樣本X變量放入matlab變量名X,保存為m

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

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

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

6、idean)距離。然后進行類的搜索、合并于距離矩陣的更新涉及類間距離的計算，需要事先計算類與類之間的距離。依據(jù)類問距離不同的計算方法，我們可以把系統(tǒng)聚類法分為最短距離法、最長距離法、重心法、離差平方和法(ward)等。設(shè)Gp,Gq為前一輪操作中形成的某兩個聚類，在本輪操作中歸聚為新類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è)計作業(yè)其中，丁和5分別為Gp和Gr包含的聚類對象個數(shù),Ward法2rlni+np2Q+nq25/7n;dpi+癡dlq-d注意，Ward法要求初始距離矩陣采用歐式距離公式計算各個對象的距離。2.4 得到閔可夫斯基(Minkowski)距離譜系聚類法函數(shù)(見附錄A.1)(1) pdist創(chuàng)建聚類對象的Minkowski距離矩陣。(2) squarform拉直矩陣Db(3) linkage用D或其拉直矩陣創(chuàng)建信息矩陣G,默認的類間距離為最短距離法。(4) dendrogram創(chuàng)建G的譜系聚類圖。(5) cluster創(chuàng)建G的指定個數(shù)類

8、。2.5 畫譜系聚類圖(見圖2.1)圖2.1Iris花瓣數(shù)據(jù)譜系聚類圖2.6 得出分類2,3,5由圖2.1得出Iris花瓣數(shù)據(jù)截斷處可選擇d=1,d=0.8,d=0.666對應(yīng)的分類個數(shù)為2.7 cluster創(chuàng)建G的指定個數(shù)類。(matlab程序見A.3)2.7.1 分3類圖(見圖2.2)數(shù)據(jù)分析課程設(shè)計作業(yè)第二類3.5*米米*12.5*米米*舉簿祥來*舉來*米米米布米*東*來奈來米米素奈米米*率率*米磷基類*來案崇*第一類一*柒-*44.555.566.57.58圖2.2譜系聚類分析分為三類圖2.8 結(jié)論3類不太恰當，應(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ù)點隨機生成k組，把每組的均值作為中心點。重新計算每個數(shù)據(jù)點與各組的中心點的相似性，根據(jù)數(shù)據(jù)點相似性的度量準則，把每個數(shù)據(jù)點重新分組，計算每組新的均值作為中心點。不斷重復上述過程，直到中心點的均值收斂，停止迭代過程。K-means算法是一種比較快速的聚類方法，時間復雜度為O(nkt),其中n是數(shù)據(jù)點的數(shù)目，k是分組數(shù)目，t是迭代次數(shù)。K-means算法也存在不足，最大問題要指定分組數(shù)目并且在運行過程

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

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

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

13、譜系聚類分析得到(matlab程序參考附錄A.1-4)數(shù)據(jù)分析課程設(shè)計作業(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è)計作業(yè)第二類*米米*米*來來*辛*殺逑米米辛辛辛*米來*第二類*2L44.55.56.5圖3.3K-Means聚類結(jié)果3.5分析結(jié)果由圖3.2結(jié)果可得第1類有36個樣本，第2類有64個樣本，第3類有50個樣本，由圖3.3可知第1類有62個樣本，第2類有49個樣本，第3類有39個樣本兩種方法基本得到的

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

15、lstatisticsandprobability.Vol.1.No.281-297.1967.5余立強.LAMP架構(gòu)搭建與網(wǎng)站運行實例J.網(wǎng)絡(luò)與信息，2011(8):50-526吳夙慧，成穎，鄭彥寧，潘云濤.K-means算法研究綜述J.現(xiàn)代圖書情報技術(shù)，2011,(5 :28-35.數(shù)據(jù)分析課程設(shè)計作業(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)驗分組數(shù)據(jù)%每行一個觀測，N聚類指數(shù)，來源于初始的聚類中心值，默認情況下為隨機的觀測%輸出：IDX為最終分類%nr為每個每個聚合的中心值%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è)計作業(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('初始化聚類后沒有點移動,)elsedisp('

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

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ù)樣本號萼片長萼片寬花瓣長花瓣寬不慨15.13.51.40.2牽牛24.931.40.2牽牛數(shù)據(jù)分析課程設(shè)計作業(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è)計作業(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è)計作業(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