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

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

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

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