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

7/7二分K均值聚類算法在Iris上的測試2015—2016學(xué)年第1學(xué)期

碩士研究生多媒體信息處理技術(shù)課程設(shè)計(jì)

年級與專業(yè)計(jì)算機(jī)應(yīng)用技術(shù)學(xué)號1120150620姓名蒲朝儀

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

目錄

一、問題背景(1)

二、解決思路(2)

（1）K均值算法思想(2)

（2）二分K均值算法(2)

三、實(shí)驗(yàn)結(jié)果(3)

（1）數(shù)據(jù)集(3)

（2）實(shí)驗(yàn)結(jié)果(5)

四、觀察分析(7)

一、問題背景

目前，對于聚類問題的研究普遍存在于社會生活中的各個(gè)領(lǐng)域，如模式識別，圖像處理、機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)等。關(guān)于對生活中各種各樣的數(shù)據(jù)的聚類分類問題己經(jīng)成為眾多學(xué)者的研究熱題之一[1]。聚類和分類的區(qū)別在于，聚類沒有任何先驗(yàn)知識可循，要通過數(shù)據(jù)自身的特點(diǎn)，將數(shù)據(jù)自動(dòng)的劃分到不同的類別中。聚類的基本形式定義為“在已給的數(shù)據(jù)集合中尋找數(shù)據(jù)點(diǎn)集的同類集合。每一個(gè)集合叫做一個(gè)類，并確定一個(gè)區(qū)域，在區(qū)域中對象的密度高于其他區(qū)域中的密度”[2]。

聚類方法有很多種，其中最簡單的形式便是劃分式聚類，劃分式聚類試圖將給定的數(shù)據(jù)集合分割成不相交的子集，使具體的聚類準(zhǔn)則是最優(yōu)的。實(shí)際中應(yīng)用最廣泛的準(zhǔn)則是聚類誤差平方和準(zhǔn)則，即對于每一個(gè)點(diǎn)都計(jì)算它到相應(yīng)的聚類中心點(diǎn)的平方距離，并對數(shù)據(jù)集合上的所有點(diǎn)的距離進(jìn)行求和。一種最流行的基于最小聚類誤差平法和的聚類方法是K-均值算法。K-均值算法是一種基于劃分的聚類算法，它通過不斷的迭代來進(jìn)行聚類，當(dāng)算法收斂到一個(gè)結(jié)束條件時(shí)就終止迭代過程，輸出聚類結(jié)果。由于其算法思想簡便，又容易實(shí)現(xiàn)對大規(guī)模數(shù)據(jù)的聚類，因此K-均值算法己成為一種最常用的聚類算法之一[3]。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ī)性就會導(dǎo)致聚類容易陷入局部最優(yōu)，而找不到全局最優(yōu)。K-均值缺點(diǎn)詳細(xì)介紹如下：

第一，K-均值算法中的K值必須由用戶輸入，在算法的流程圖中我們可以看出，K-值是必須是一個(gè)用戶最先確定的參數(shù)。K-均值方法必須在K-值已知的前提下才能進(jìn)行聚類。但是在一些實(shí)際問題的求解過程中，自然簇的個(gè)數(shù)K是沒有事先給出的，通常是用戶所不知道的。

第二，K-均值聚類算法對于噪聲和離群點(diǎn)數(shù)據(jù)非常敏感，聚類結(jié)果很容易受

到數(shù)據(jù)中所含有的噪聲和離群點(diǎn)的影響。該算法中在簇的質(zhì)心求解過程中，是通過對每個(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)的重新分配，這必然會引起聚類結(jié)果的不準(zhǔn)確[5,6]。

二、解決思路

本課程主要針對K均值的有點(diǎn)以及對K值的初始選擇這一限制，設(shè)計(jì)一種改進(jìn)的K-均值聚類方法，即二分K均值算法。通過查閱資料總結(jié)，二分K均值算法可以加速K-均值算法的執(zhí)行速度，因?yàn)樗南嗨贫扔?jì)算少了[7]。另外二分K均值算法不受初始化問題的影響，因?yàn)檫@里不存在隨機(jī)點(diǎn)的選取，且每一步都保證了誤差最小。

（1）K均值算法思想

K均值算法是一種經(jīng)典的基于歐氏距離的硬劃分算法，這種算法采用誤差平方和函數(shù)作為優(yōu)化的目標(biāo)函數(shù)，誤差平方和函數(shù)SSE的定義如所示[8]：

2

1jjkjxCSxCSE=∈=-∑∑（1）

1

jxjCjxCm∈=∑（2）

式中：K——聚類的數(shù)目；Cj(j=1,2,...k)——聚類的第j個(gè)簇；X——簇Cj中的任意一組數(shù)據(jù)對象；Cj——含有mj個(gè)數(shù)據(jù)對象的Cj質(zhì)心。

可以看出SSE表示數(shù)據(jù)樣本點(diǎn)和簇間中心間差異度平方之和，簇的中心會影響到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è)簇Ci，用基本的K均值聚類算法對選定的簇Ci進(jìn)行二分聚類。從二分實(shí)驗(yàn)中選擇具有最小總SSE的兩個(gè)簇，將這兩個(gè)簇添加到簇表S中，更新簇表。如此下去，知道產(chǎn)生K個(gè)簇。在二分K均值算法中，使用結(jié)果簇的質(zhì)心作為基本K均值的初始質(zhì)心。使用誤差平方和SSE作為度量聚類質(zhì)量的目標(biāo)函數(shù)，也稱SSE為散度。對于多次運(yùn)行K均值產(chǎn)生的初級，選擇誤差平方和最小的那個(gè)，使得聚類的質(zhì)心可以更好地代表簇中的點(diǎn)。其中SSE的定義如公式

（3）。其中ci為簇Ci的聚類中心，x為該簇中的一個(gè)樣本[9,10]。

2

(,)iikCixSSEdistxc∈=∑∑（3）

以上隱含著一個(gè)原則是：因?yàn)榫垲惖恼`差平方和能夠衡量聚類性能，該值越小表示數(shù)據(jù)點(diǎn)月接近于它們的質(zhì)心，聚類效果就越好。所以我們就需要對誤差平方和最大的簇進(jìn)行再一次的劃分，因?yàn)檎`差平方和越大，表示該簇聚類越不好，越有可能是多個(gè)簇被當(dāng)成一個(gè)簇了，所以我們首先需要對這個(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è)測試數(shù)據(jù)是人工設(shè)置的二維數(shù)據(jù)，這些數(shù)據(jù)值主要分布在-6到6之間，均為浮點(diǎn)型數(shù)據(jù)。本課程的模擬測試集數(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ù)測鳶尾花卉屬于（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ù)集

為方便進(jìn)行數(shù)據(jù)聚類測試，對次數(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ù)作為評估二分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ù)集上的測試和真實(shí)數(shù)據(jù)集上的測試。另外，預(yù)測準(zhǔn)確率是由得到的聚類結(jié)果和真實(shí)數(shù)據(jù)集分類標(biāo)簽進(jìn)行比較，按預(yù)測正確的結(jié)點(diǎn)個(gè)數(shù)占比得來模擬數(shù)據(jù)集上的測試結(jié)果

1.聚類效果不太理想的情況

圖3效果較差的聚類結(jié)果

2.聚類效果比較理想的情況

圖4效果較好的聚類結(jié)果

鳶尾花數(shù)據(jù)集上的測試結(jié)果

1.聚類效果不太理想的情況

圖5聚類效果欠佳的情況此時(shí)準(zhǔn)確率如圖6所示為66.7%：

圖6聚類準(zhǔn)確率展示

2.聚類效果比較理想的情況

圖7聚類效果較好的情況

此時(shí)準(zhǔn)確率如圖8所示為86.7%：

圖8聚類準(zhǔn)確率展示

四、觀察分析

由于在二分K均值算法中，使用誤差平方和來度量聚類的質(zhì)量的好壞，對各個(gè)樣本點(diǎn)的誤差采用歐式距離進(jìn)行計(jì)算，然后計(jì)算誤差的平方：

1.初始化全部點(diǎn)的質(zhì)心，并建立所需要的數(shù)據(jù)存儲結(jié)構(gòu)

2.對每一個(gè)簇嘗試二分（最開始就是一個(gè)簇），選出最好的

3.更新各個(gè)簇的元素個(gè)數(shù)

二分K均值算法沒有初始化問題，其每一步操作實(shí)際上就是從m對子簇中找到誤差平方和最小的一對子簇，然后再進(jìn)行基本的K均值操作。從對模擬數(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ù)集上的測試。二分K均值算法能夠克服K均值收斂于局部最小的局限，在聚類效果上展示出比較穩(wěn)定的性能，圖4和圖7為二分K均值算法在模擬數(shù)據(jù)集和Iris數(shù)據(jù)集上聚類效果比

較好的情況，另外，在Iris數(shù)據(jù)集上能展示出86.7%的預(yù)測準(zhǔn)確率。

另外，在圖3和圖5顯示，實(shí)驗(yàn)運(yùn)行代碼結(jié)果會出現(xiàn)不太好的情況。這是由于雖然二分K均值能克服K均值收斂于局部最小的局限，但并不能保證收斂到全局最優(yōu)值。

附錄

附錄1實(shí)驗(yàn)數(shù)據(jù)匯總結(jié)果展示

1.K模擬測試數(shù)據(jù)

由于二分

算法改進(jìn)而來，

理相同，本課程在做二分均值聚類實(shí)驗(yàn)前測試了一遍

K不同聚類效果

2.二分K均值模擬數(shù)據(jù)

二分問題，是從方和最小的一對子簇，進(jìn)行基本的

3.二分K均值鳶尾花測試

1.K局限，到全局最優(yōu)值

2.聚類結(jié)果和真實(shí)數(shù)據(jù)集

分類標(biāo)簽進(jìn)行比較，測正確的結(jié)點(diǎn)個(gè)數(shù)占比

得來

附錄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:initcentroids

centroids=initCentroids(dataSet,k)

whileclusterChanged:

clusterChanged=False

#foreachsample

foriinxrange(numSamples):

minDist=100000.0

minIndex=0

#foreachcentroid

#step2:findthecentroidwhoisclosest

forjinrange(k):

distance=euclDistance(centroids[j,:],dataSet[i,:])

ifdistance<minDist:

minDist=distance

minIndex=j

#step3:updateitscluster

ifclusterAssment[i,0]!=minIndex:

clusterChanged=True

clusterAssment[i,:]=minIndex,minDist**2

#step4:updatecentroids

forjinrange(k):

pointsInCluster=dataSet[nonzero(clusterAssment[:,0].A==j)[0]]

centroids[j,:]=mean(pointsInCluster,axis=0)

print'Congratulations,clusterusingk-meanscomplete!'

returncentroids,clusterAssment

3.二分K均值函數(shù)

defbiKmeans(dataSet,k):

numSamples=dataSet.shape[0]

#firstcolumnstoreswhichclusterthissamplebelongsto,

#secondcolumnstorestheerrorbetweenthissampleanditscentroid

clusterAssment=mat(zeros((numSamples,2)))

#step1:theinitclusteristhewholedataset

centroid=mean(dataSet,axis=0).tolist()[0]

centList=[centroid]

foriinxrange(numSamples):

clusterAssment[i,1]=euclDistance(mat(centroid),dataSet[i,:])**2

whilelen(centList)<k:

#minsumofsquareerror

minSSE=100000.0

numCurrCluster=len(centList)

#foreachcluster

foriinrange(numCurrCluster):

#step2:getsamplesinclusteri

pointsInCurrCluster=dataSet[

nonzero(clusterAssment[:,0].A==i)[0],:]

#step3:clusteritto2sub-clustersusingk-means

centroids,splitClusterAssment=kmeans(pointsInCurrCluster,2)

#step4:calculatethesumofsquareerroraftersplitthis

#cluster

splitSSE=sum(splitClusterAssment[:,1])

notSplitSSE=sum(clusterAssment[nonzero(

clusterAssment[:,0].A!=i)[0],1])

currSplitSSE=splitSSE+notSplitSSE

#step5:findthebestsplitclusterwhichhastheminsumof

#squareerror

ifcurrSplitSSE<minSSE:

minSSE=currSplitSSE

bestCentroidToSplit=i

bestNewCe