二分K均值聚類算法在Iris上的測試

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

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

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

聚類效果比較理想的情況圖4效果較好的聚類結(jié)果鳶尾花數(shù)據(jù)集上的測試結(jié)果1.聚類效果不太理想的情況圖5聚類效果欠佳的情況此時準確率如圖6所示為66.7%：step1:loaddata,-.step2:showthedata...step3:clustering...Congratulationsjclusterusingmeanscomplete!Congratulatio匚lusterusingmeans匸ompleteJCongratulationsjclusterusingmeanscomplete!Congratulations;」匚lusterusingbi-taneans;completeJstep4:showtheresult..-step5:conparedwiththelabelofthereal?wo「lddata0.666666666667圖6聚類準確率展示2.聚類效果比較理想的情況圖7聚類效果較好的情況此時準確率如圖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聚類準確率展示四、觀察分析由于在二分K均值算法中，使用誤差平方和來度量聚類的質(zhì)量的好壞，對各個樣本點的誤差采用歐式距離進行計算，然后計算誤差的平方：初始化全部點的質(zhì)心，并建立所需要的數(shù)據(jù)存儲結(jié)構(gòu)對每一個簇嘗試二分（最開始就是一個簇），選出最好的更新各個簇的元素個數(shù)二分K均值算法沒有初始化問題，其每一步操作實際上就是從m對子簇中找到誤差平方和最小的一對子簇，然后再進行基本的K均值操作。從對模擬數(shù)據(jù)和Iris數(shù)據(jù)集的聚類實驗可以看出二分K均值的聚類效果：首先，二分K均值克服了K均值受K個初始點選擇影響的缺點，不需要人工選定初始點。其次,K均值算法是二分K均值建模的主要思想，它們的聚類原理是一致的,本課程在附錄中隨附了K均值和二分K均值在模擬數(shù)據(jù)集上的測試。二分K均值算法能夠克服K均值收斂于局部最小的局限，在聚類效果上展示出比較穩(wěn)定的性能，圖4和圖7為二分K均值算法在模擬數(shù)據(jù)集和Iris數(shù)據(jù)集上聚類效果比較好的情況，另外，在Iris數(shù)據(jù)集上能展示出86.7%的預測準確率。另外，在圖3和圖5顯示，實驗運行代碼結(jié)果會出現(xiàn)不太好的情況。這是由于雖然二分K均值能克服K均值收斂于局部最小的局限，但并不能保證收斂到全局最優(yōu)值。參考文獻⑴張嬌.基于二分K均值和SVM決策樹的數(shù)據(jù)挖掘算法研究[D].陜西師范大學,2012.⑵汪萬紫,裘國永，張兵權(quán).基于線性判別分析和二分K均值的高維數(shù)據(jù)自適應聚類方法[J].鄭州輕工業(yè)學院學報（自然科學版）,2011,02:106-110.⑶張軍偉，王念濱,黃少濱，蔄世明.二分K均值聚類算法優(yōu)化及并行化研究[J].計算機工程,2011,17:23-25.⑷蔣大宇.快速有效的并行二分K均值算法[D].哈爾濱工程大學,2013.⑸劉廣聰,黃婷婷,陳海南?改進的二分K均值聚類算法J].計算機應用與軟件,2015,02:261-263+277.⑹王桐遠.基于二分K均值聚類的二部圖網(wǎng)絡(luò)推薦算法J].經(jīng)營管理者,2015,25:3.⑺李梅.改進的K均值算法在中文文本聚類中的研究[D].安徽大學,2010.⑻張嬌，裘國永,張奇.基于二分K均值的SVM決策樹的高維數(shù)據(jù)分類方法[J].赤峰學院學報（自然科學版）,2012,07:13-15.⑼裘國永,張嬌.基于二分K-均值的SVM決策樹自適應分類方法[J].計算機應用研究,2012,10:3685-3687+3709.[10]鄒海,李梅.一種用于文本聚類的改進二分 K-均值算法[J].微型機與應用,2010,12:64-67.附錄附錄1實驗數(shù)據(jù)匯總結(jié)果展示1.K模擬測試數(shù)據(jù)3.二分K均值鳶尾花測試附錄2二分K均值算法功能實現(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#