二分K均值聚類算法在Iris上的測(cè)試

2015—2016學(xué)年第1學(xué)期碩士研究生 多媒體信息處理技術(shù) 課程設(shè)計(jì)年級(jí)與專業(yè)一計(jì)算機(jī)應(yīng)用技術(shù) 學(xué)號(hào) 姓名蒲朝儀二分K均值聚類算法在Iris上的測(cè)試目錄TOC\o"1-5"\h\z\o"CurrentDocument"一、問題背景 1\o"CurrentDocument"二、解決思路 2（1）K均值算法思想 2\o"CurrentDocument"（2）二分K均值算法 2\o"CurrentDocument"三、實(shí)驗(yàn)結(jié)果 3\o"CurrentDocument"（1）數(shù)據(jù)集 3（2）實(shí)驗(yàn)結(jié)果 5\o"CurrentDocument"四、觀察分析 7\o"CurrentDocument"參考文獻(xiàn) 8\o"CurrentDocument"附錄 9附錄1實(shí)驗(yàn)數(shù)據(jù)匯總結(jié)果展示 9附錄2二分K均值算法功能實(shí)現(xiàn)主要代碼 11一、問題背景目前，對(duì)于聚類問題的研究普遍存在于社會(huì)生活中的各個(gè)領(lǐng)域，如模式識(shí)別，圖像處理、機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)等。關(guān)于對(duì)生活中各種各樣的數(shù)據(jù)的聚類分類問題己經(jīng)成為眾多學(xué)者的研究熱題之一［1］。聚類和分類的區(qū)別在于，聚類沒有任何先驗(yàn)知識(shí)可循，要通過數(shù)據(jù)自身的特點(diǎn)，將數(shù)據(jù)自動(dòng)的劃分到不同的類別中。聚類的基本形式定義為“在已給的數(shù)據(jù)集合中尋找數(shù)據(jù)點(diǎn)集的同類集合。每一個(gè)集合叫做一個(gè)類，并確定一個(gè)區(qū)域，在區(qū)域中對(duì)象的密度高于其他區(qū)域中的密度”［2］。聚類方法有很多種，其中最簡單的形式便是劃分式聚類，劃分式聚類試圖將給定的數(shù)據(jù)集合分割成不相交的子集，使具體的聚類準(zhǔn)則是最優(yōu)的。實(shí)際中應(yīng)用最廣泛的準(zhǔn)則是聚類誤差平方和準(zhǔn)則，即對(duì)于每一個(gè)點(diǎn)都計(jì)算它到相應(yīng)的聚類中心點(diǎn)的平方距離，并對(duì)數(shù)據(jù)集合上的所有點(diǎn)的距離進(jìn)行求和。一種最流行的基于最小聚類誤差平法和的聚類方法是K-均值算法。K-均值算法是一種基于劃分的聚類算法，它通過不斷的迭代來進(jìn)行聚類，當(dāng)算法收斂到一個(gè)結(jié)束條件時(shí)就終止迭代過程，輸出聚類結(jié)果。由于其算法思想簡便，又容易實(shí)現(xiàn)對(duì)大規(guī)模數(shù)據(jù)的聚類，因此K-均值算法己成為一種最常用的聚類算法之一⑶。K-均值算法能找到關(guān)于聚類誤差的局部的最優(yōu)解，是一個(gè)能應(yīng)用在許多聚類問題上的快速迭代算法。它是一種以點(diǎn)為基礎(chǔ)的聚類算法，以隨機(jī)選取的初始點(diǎn)為聚類中心，迭代地改變聚類中心來使聚類誤差最小化。K-均值算法由于其聚類過程簡單，易于實(shí)現(xiàn)，因此已經(jīng)成為當(dāng)前最常用的聚類算法之一。但是K-均值的算法的聚類結(jié)果容易受到初始聚類中心點(diǎn)的選取的影響，不穩(wěn)定，且容易受到數(shù)據(jù)中的噪聲點(diǎn)、離群點(diǎn)的影響4］。并且在K-均值方法的迭代過程中由于初值的選取就有隨機(jī)性就會(huì)導(dǎo)致聚類容易陷入局部最優(yōu)，而找不到全局最優(yōu)。K-均值缺點(diǎn)詳細(xì)介紹如下：第一，K-均值算法中的K值必須由用戶輸入，在算法的流程圖中我們可以看出，K-值是必須是一個(gè)用戶最先確定的參數(shù)。K-均值方法必須在K-值已知的前提下才能進(jìn)行聚類。但是在一些實(shí)際問題的求解過程中，自然簇的個(gè)數(shù)K是沒有事先給出的，通常是用戶所不知道的。第二，K-均值聚類算法對(duì)于噪聲和離群點(diǎn)數(shù)據(jù)非常敏感，聚類結(jié)果很容易受到數(shù)據(jù)中所含有的噪聲和離群點(diǎn)的影響。該算法中在簇的質(zhì)心求解過程中，是通過對(duì)每個(gè)簇求均值得到的，當(dāng)數(shù)據(jù)集中含有噪聲和離群點(diǎn)數(shù)據(jù)時(shí)，在計(jì)算質(zhì)心時(shí)將導(dǎo)致聚類中心偏離數(shù)據(jù)真正密集的區(qū)域，而得到的聚類中心將向噪聲和離群點(diǎn)數(shù)據(jù)所在的區(qū)域偏移，然后在此基礎(chǔ)上進(jìn)行數(shù)據(jù)點(diǎn)的重新分配，這必然會(huì)引起聚類結(jié)果的不準(zhǔn)確［5,6］。二、解決思路本課程主要針對(duì)K均值的有點(diǎn)以及對(duì)K值的初始選擇這一限制，設(shè)計(jì)一種改進(jìn)的K-均值聚類方法，即二分K均值算法。通過查閱資料總結(jié)，二分K均值算法可以加速K-均值算法的執(zhí)行速度，因?yàn)樗南嗨贫扔?jì)算少了⑺。另外二分K均值算法不受初始化問題的影響，因?yàn)檫@里不存在隨機(jī)點(diǎn)的選取，且每一步都保證了誤差最小。(1)K均值算法思想K均值算法是一種經(jīng)典的基于歐氏距離的硬劃分算法，這種算法采用誤差平方和函數(shù)作為優(yōu)化的目標(biāo)函數(shù)，誤差平方和函數(shù)SSE的定義如所示［8］：SSE=工工x-C『j=1xeCi '(1)C-1YxjmjxwCjj(2)式中：K——聚類的數(shù)目；C卩=1,2,…k)――聚類的第j個(gè)簇；一—簇C沖的任意一組數(shù)據(jù)對(duì)象；Cj 含有m.個(gè)數(shù)據(jù)對(duì)象的C.質(zhì)心。可以看出SSE表示數(shù)據(jù)樣本點(diǎn)和簇間中心間差異度平方之和，簇的中心會(huì)影響到SSE的值。很顯然，如果SSE的值越小，那么就代表這種劃分方法聚類的質(zhì)量就越好。因此，K均值聚類的目標(biāo)就是要設(shè)法找出能夠使聚類準(zhǔn)則函數(shù)SSE的值達(dá)到最小的聚類結(jié)果。(2)二分K均值算法二分k均值(bisectingk-means)算法的主要思想是：首先將所有點(diǎn)作為一個(gè)簇，然后將該簇一分為二。之后選擇能最大程度降低聚類代價(jià)函數(shù)(也就是誤差平方和)的簇劃分為兩個(gè)簇。以此進(jìn)行下去，直到簇的數(shù)目等于用戶給定的數(shù)目k為止。二分K均值算法思想具體如下:設(shè)X={x1,x2,...xi，...,xn}為n個(gè)Rd空間的數(shù)據(jù)，在開始聚類前，指定K為聚類個(gè)數(shù)。為了得到K個(gè)簇，將所有點(diǎn)的集合分裂成兩個(gè)類，放到簇表S中。從簇表中選取一個(gè)簇C用基本的K均值聚類算法對(duì)選定的簇^進(jìn)行二分聚類。從二分實(shí)驗(yàn)中選擇具有最小總SSE的兩個(gè)簇，將這兩個(gè)簇添加到簇表S中，更新簇表。如此下去，知道產(chǎn)生K個(gè)簇。在二分K均值算法中，使用結(jié)果簇的質(zhì)心作為基本K均值的初始質(zhì)心。使用誤差平方和SSE作為度量聚類質(zhì)量的目標(biāo)函數(shù)，也稱SSE為散度。對(duì)于多次運(yùn)行K均值產(chǎn)生的初級(jí)，選擇誤差平方和最小的那個(gè)，使得聚類的質(zhì)心可以更好地代表簇中的點(diǎn)。其中SSE的定義如公式（3）。其中c為簇Cj的聚類中心，X為該簇中的一個(gè)樣本［9,10］。3）SSE=工工dist(c,x3）iixeCj以上隱含著一個(gè)原則是：因?yàn)榫垲惖恼`差平方和能夠衡量聚類性能，該值越小表示數(shù)據(jù)點(diǎn)月接近于它們的質(zhì)心，聚類效果就越好。所以我們就需要對(duì)誤差平方和最大的簇進(jìn)行再一次的劃分，因?yàn)檎`差平方和越大，表示該簇聚類越不好越有可能是多個(gè)簇被當(dāng)成一個(gè)簇了，所以我們首先需要對(duì)這個(gè)簇進(jìn)行劃分。二分K均值算法受初始化問題的影響較小，因?yàn)樗鼒?zhí)行了多次二分試驗(yàn)并選擇最小SEE的實(shí)驗(yàn)結(jié)果，且每步只有兩個(gè)質(zhì)心。但仍然受用戶指定的聚類個(gè)數(shù)K的影響。三、實(shí)驗(yàn)結(jié)果（1）數(shù)據(jù)集第一個(gè)測(cè)試數(shù)據(jù)是人工設(shè)置的二維數(shù)據(jù)，這些數(shù)據(jù)值主要分布在-6到6之間，均為浮點(diǎn)型數(shù)據(jù)。本課程的模擬測(cè)試集數(shù)據(jù)共80個(gè)樣本，有4個(gè)類。該數(shù)據(jù)集分布如圖1所示：

圖1隨機(jī)二維數(shù)據(jù)分布Iris數(shù)據(jù)集是常用的分類和聚類的實(shí)驗(yàn)數(shù)據(jù)集，也稱鳶尾花卉數(shù)據(jù)，由Fisher,1936收集整理，于1988年7月公開。Iris是一類多重變量分析的數(shù)據(jù)集，花萼長度，花萼寬度，花瓣長度，花瓣寬度4個(gè)屬性預(yù)測(cè)鳶尾花卉屬于（Setosa，Versicolour,Virginica）三個(gè)種類中的哪一類。通過iris以鳶尾花的特征作為數(shù)據(jù)來源，常用在分類操作中。該數(shù)據(jù)集由3種不同類型的鳶尾花的50個(gè)樣本數(shù)據(jù)構(gòu)成，即總共有150條鳶尾花數(shù)據(jù)。其中的一個(gè)種類與另外兩個(gè)種類是線性可分離的，后兩個(gè)種類是非線性可分離的。該數(shù)據(jù)集包含了5個(gè)屬性，如下表1所示：表1Iris數(shù)據(jù)集屬性數(shù)據(jù)格式備注Sepal.Length（花萼長度）浮點(diǎn)型（單位cm）種類有三種類型：IrisSetosa（山鳶尾）、IrisVersicolour（雜色鳶尾），以及IrisVirginica（維吉尼亞鳶尾）Sepal.Width（花萼寬度）浮點(diǎn)型（單位cm）Petal.Length（花瓣長度）浮點(diǎn)型（單位cm）Petal.Width（花瓣寬度）浮點(diǎn)型（單位cm）種類字符型為方便進(jìn)行數(shù)據(jù)聚類測(cè)試，對(duì)次數(shù)據(jù)做了一定的調(diào)整：將Iris數(shù)據(jù)集最后一個(gè)分類標(biāo)簽，及種類的這一列數(shù)據(jù)去除形成新的數(shù)據(jù)集作為二分K均值進(jìn)行聚類的數(shù)據(jù)集;將Iris數(shù)據(jù)集種類中的數(shù)據(jù)改為整形數(shù)據(jù)作為評(píng)估二分K均值準(zhǔn)確

率的樣本數(shù)據(jù)，其中IrisSetosa的值改為1，IrisVersicolour為2，IrisVirginica為3。該數(shù)據(jù)的分布如圖2所示：圖2鳶尾花數(shù)據(jù)分布（2）實(shí)驗(yàn)結(jié)果本課程是在python環(huán)境下完成二分K均值聚類算法的實(shí)現(xiàn)的。上文中提到,為了驗(yàn)證二分K均值算法在聚類上的有效性，本課程設(shè)計(jì)了兩組實(shí)驗(yàn)，包括模擬數(shù)據(jù)集上的測(cè)試和真實(shí)數(shù)據(jù)集上的測(cè)試。另外,預(yù)測(cè)準(zhǔn)確率是由得到的聚類結(jié)果和真實(shí)數(shù)據(jù)集分類標(biāo)簽進(jìn)行比較,按預(yù)測(cè)正確的結(jié)點(diǎn)個(gè)數(shù)占比得來模擬數(shù)據(jù)集上的測(cè)試結(jié)果聚類效果不太理想的情況Ef -4 -2 u 2 4 hf-6 -4 -2 C 2 4 fc圖3效果較差的聚類結(jié)果

聚類效果比較理想的情況圖4效果較好的聚類結(jié)果鳶尾花數(shù)據(jù)集上的測(cè)試結(jié)果1.聚類效果不太理想的情況圖5聚類效果欠佳的情況此時(shí)準(zhǔn)確率如圖6所示為66.7%：step1:loaddata,-.step2:showthedata...step3:clustering...Congratulationsjclusterusingmeanscomplete!Congratulatio匚lusterusingmeans匸ompleteJCongratulationsjclusterusingmeanscomplete!Congratulations;」匚lusterusingbi-taneans;completeJstep4:showtheresult..-step5:conparedwiththelabelofthereal?wo「lddata0.666666666667圖6聚類準(zhǔn)確率展示2.聚類效果比較理想的情況圖7聚類效果較好的情況此時(shí)準(zhǔn)確率如圖8所示為86.7%：step1:loaddata..?step2:showthedata..?3:eluEtering? C-ongratula七丄口門三」clusterusin呂k-meansconplete[Ccngra±ulistian5jclu5±erusingk-ineanaconpletcICongratuIdticnsjclusterusingk-tmeanaconpleteJtongratulations;,clusterusingbi-kmeansconplete￡step4:showtheresult.■step5:c-Dinparedwiththelabelofthereal-worlddata0-8666666&6567圖8聚類準(zhǔn)確率展示四、觀察分析由于在二分K均值算法中，使用誤差平方和來度量聚類的質(zhì)量的好壞，對(duì)各個(gè)樣本點(diǎn)的誤差采用歐式距離進(jìn)行計(jì)算，然后計(jì)算誤差的平方：初始化全部點(diǎn)的質(zhì)心，并建立所需要的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)對(duì)每一個(gè)簇嘗試二分（最開始就是一個(gè)簇），選出最好的更新各個(gè)簇的元素個(gè)數(shù)二分K均值算法沒有初始化問題，其每一步操作實(shí)際上就是從m對(duì)子簇中找到誤差平方和最小的一對(duì)子簇，然后再進(jìn)行基本的K均值操作。從對(duì)模擬數(shù)據(jù)和Iris數(shù)據(jù)集的聚類實(shí)驗(yàn)可以看出二分K均值的聚類效果：首先，二分K均值克服了K均值受K個(gè)初始點(diǎn)選擇影響的缺點(diǎn)，不需要人工選定初始點(diǎn)。其次,K均值算法是二分K均值建模的主要思想，它們的聚類原理是一致的,本課程在附錄中隨附了K均值和二分K均值在模擬數(shù)據(jù)集上的測(cè)試。二分K均值算法能夠克服K均值收斂于局部最小的局限，在聚類效果上展示出比較穩(wěn)定的性能，圖4和圖7為二分K均值算法在模擬數(shù)據(jù)集和Iris數(shù)據(jù)集上聚類效果比較好的情況，另外，在Iris數(shù)據(jù)集上能展示出86.7%的預(yù)測(cè)準(zhǔn)確率。另外，在圖3和圖5顯示，實(shí)驗(yàn)運(yùn)行代碼結(jié)果會(huì)出現(xiàn)不太好的情況。這是由于雖然二分K均值能克服K均值收斂于局部最小的局限，但并不能保證收斂到全局最優(yōu)值。參考文獻(xiàn)⑴張嬌.基于二分K均值和SVM決策樹的數(shù)據(jù)挖掘算法研究[D].陜西師范大學(xué),2012.⑵汪萬紫,裘國永，張兵權(quán).基于線性判別分析和二分K均值的高維數(shù)據(jù)自適應(yīng)聚類方法[J].鄭州輕工業(yè)學(xué)院學(xué)報(bào)（自然科學(xué)版）,2011,02:106-110.⑶張軍偉，王念濱,黃少濱，蔄世明.二分K均值聚類算法優(yōu)化及并行化研究[J].計(jì)算機(jī)工程,2011,17:23-25.⑷蔣大宇.快速有效的并行二分K均值算法[D].哈爾濱工程大學(xué),2013.⑸劉廣聰,黃婷婷,陳海南?改進(jìn)的二分K均值聚類算法J].計(jì)算機(jī)應(yīng)用與軟件,2015,02:261-263+277.⑹王桐遠(yuǎn).基于二分K均值聚類的二部圖網(wǎng)絡(luò)推薦算法J].經(jīng)營管理者,2015,25:3.⑺李梅.改進(jìn)的K均值算法在中文文本聚類中的研究[D].安徽大學(xué),2010.⑻張嬌，裘國永,張奇.基于二分K均值的SVM決策樹的高維數(shù)據(jù)分類方法[J].赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版）,2012,07:13-15.⑼裘國永,張嬌.基于二分K-均值的SVM決策樹自適應(yīng)分類方法[J].計(jì)算機(jī)應(yīng)用研究,2012,10:3685-3687+3709.[10]鄒海,李梅.一種用于文本聚類的改進(jìn)二分 K-均值算法[J].微型機(jī)與應(yīng)用,2010,12:64-67.附錄附錄1實(shí)驗(yàn)數(shù)據(jù)匯總結(jié)果展示1.K模擬測(cè)試數(shù)據(jù)3.二分K均值鳶尾花測(cè)試附錄2二分K均值算法功能實(shí)現(xiàn)主要代碼1.歐式距離函數(shù)defeuclDistance(vector1,vector2):returnsqrt(sum(power(vector2-vector1,2)))2.K均值聚類函數(shù)defkmeans(dataSet,k):numSamples=dataSet.shape[0]#firstcolumnstoreswhichclusterthissamplebelongsto,#secondcolumnstorestheerrorbetweenthissampleanditscentroidclusterAssment=mat(zeros((numSamples,2)))clusterChanged=True#step1:initcentroidscentroids=initCentroids(dataSet,k)whileclusterChanged:clusterChanged=False#foreachsampleforiinxrange(numSamples):minDist=100000.0minIndex=0#foreachcentroid#step2:findthecentroidwhoisclosestforjinrange(k):distance=euclDistance(centroids[j,:],dataSet[i,:])ifdistance<minDist:minDist=distanceminIndex=j#step3:updateitsclusterifclusterAssment[i,0]!=minIndex:clusterChanged=TrueclusterAssment[i,:]=minIndex,minDist**2#step4:updatecentroidsforjinrange(k):pointsInCluster=dataSet[nonzero(clusterAssment[:,0].A==j)[0]]centroids[j,:]=mean(pointsInCluster,axis=0)print'Congratulations,clusterusingk-meanscomplete!'returncentroids,clusterAssment3?二分K均值函數(shù)defbiKmeans(dataSet,k):numSamples=dataSet.shape[0]#firstcolumnstoreswhichclusterthissamplebelongsto,#secondcolumnstorestheerrorbetweenthissampleanditscentroidclusterAssment=mat(zeros((numSamples,2)))#step1:theinitclusteristhewholedatasetcentroid=mean(dataSet,axis=0).tolist()[0]centList=[centroid]foriinxrange(numSamples):clusterAssment[i,1]=euclDistance(mat(centroid),dataSet[i,:])**2whilelen(centList)<k:#minsumofsquareerrorminSSE=100000.0numCurrCluster=len(centList)#foreachclusterforiinrange(numCurrCluster):#step2:getsamplesinclusteripointsInCurrCluster=dataSet[nonzero(clusterAssment[:,0].A==i)[0],:]#step3:clusteritto2sub-clustersusingk-meanscentroids,splitClusterAssment=kmeans(pointsInCurrCluster,2)#step4:calculatethesumofsquareerroraftersplitthis#clustersplitSSE=sum(splitClusterAssment[:,1])notSplitSSE=sum(clusterAssment[nonzero(clusterAssment[:,0].A!=i)[0],1])currSplitSSE=splitSSE+notSplitSSE#