基于劃分的聚類分析算法的改進(jìn)

范多鋒，徐俊剛

(中國科學(xué)院 研究生院，北京100097)

作為統(tǒng)計(jì)學(xué)的一個(gè)分支，聚類分析已經(jīng)被研究了許多年[1-5]，但主要集中在基于距離的聚類分析上。在機(jī)器學(xué)習(xí)領(lǐng)域，聚類是無指導(dǎo)學(xué)習(xí)的一個(gè)例子。與分類不同，聚類不依賴于預(yù)先定義的類和帶標(biāo)號(hào)的訓(xùn)練實(shí)例，可見，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)[1]。在概念聚類中，一組點(diǎn)只有當(dāng)它們可以被一個(gè)概念描述時(shí)才形成一個(gè)簇。這不同于基于幾何距離來度量相似度的傳統(tǒng)聚類。目前在文獻(xiàn)中存在著大量的聚類算法，算法的選擇取決于數(shù)據(jù)集的類型、聚類的目的和應(yīng)用。如果聚類分析被用作描述或探查的工具，可以對(duì)同樣的數(shù)據(jù)集嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)集可能揭示的結(jié)果。

1 基于劃分的聚類分析算法及改進(jìn)

聚類分析，一般認(rèn)為就是試圖發(fā)現(xiàn)數(shù)據(jù)點(diǎn)集中內(nèi)在的結(jié)構(gòu)，使同一簇內(nèi)的數(shù)據(jù)點(diǎn)相似度高，不同簇之間的數(shù)據(jù)點(diǎn)相異度高[3]。由于相似度、相異度的定義往往根據(jù)具體情況而定，而且什么是最好的聚類結(jié)果，往往也與具體問題、具體要求有關(guān)。將聚類問題轉(zhuǎn)化為一種優(yōu)化問題，再通過數(shù)學(xué)規(guī)劃的方法來進(jìn)行求解是研究聚類分析的一個(gè)重要方向。

給定n個(gè)對(duì)象或者數(shù)據(jù)元組的數(shù)據(jù)庫，應(yīng)用劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一簇，k≤n。也就是說，將數(shù)據(jù)劃分為k組，并滿足如下要求：(1)每一組至少包含一個(gè)對(duì)象；(2)每個(gè)對(duì)象必須只屬于一組。

給定要構(gòu)建的劃分?jǐn)?shù)目k，應(yīng)用劃分方法創(chuàng)建一個(gè)初始劃分。然后采用迭代重定位技術(shù)，嘗試通過對(duì)象在組間移動(dòng)來改進(jìn)劃分。

設(shè)在m維歐氏空間中有n個(gè)點(diǎn)，在這個(gè)空間中的某個(gè)范圍內(nèi)選取 k個(gè)中心位置 mi(i=1，2，…，k)，使得這 n個(gè)點(diǎn)到各自最近的中心位置的距離平方之和最小。這是最初的一種優(yōu)化目標(biāo)函數(shù)。

1.1 傳統(tǒng)的K-均值算法[1]

K-均值算法(K-means)是最基本的聚類分析算法，以k為參數(shù)，把n個(gè)對(duì)象分為k個(gè)簇，以使簇內(nèi)具有較高的相似度，而簇間的相似度較低。相似度的計(jì)算根據(jù)一個(gè)簇中點(diǎn)的平均值(被看作簇的重心)來進(jìn)行。K-means聚類算法的描述和處理流程[1-2]如下：

K-means是用于劃分的K-均值算法，每個(gè)簇的中點(diǎn)用簇中對(duì)象的均值表示。其輸入為簇的數(shù)目k和包含n個(gè)對(duì)象的數(shù)據(jù)集，輸出為k個(gè)簇的集合。

算法流程：

(1)從D中隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表一個(gè)簇的平均值或質(zhì)心；

(2)repeat；

(3)根據(jù)簇中對(duì)象的均值，將每個(gè)對(duì)象（重新）指派給最相似的簇；

(4)更新每個(gè)簇的平均值，即計(jì)算每個(gè)簇中點(diǎn)的均值；

(5)直到準(zhǔn)則函數(shù)收斂。

這里把偏差準(zhǔn)則函數(shù)作為算法的優(yōu)化目標(biāo)函數(shù)，定義如下：

其中，E是數(shù)據(jù)集中所有對(duì)象的平方誤差和；p是空間中的點(diǎn)，表示給定對(duì)象；mi是 Ci的均值（p和 mi都是多維的）；|p-mi|2表示p與mi之間的度量，這里采用歐式距離度量。通過求這個(gè)目標(biāo)函數(shù)的最小值來試圖使生成的結(jié)果簇盡可能地緊湊和獨(dú)立。

1.2 K-means算法的不足

K-means算法有以下不足：(1)算法對(duì)初始值的選取依賴性極大。初始值不同，往往得到不同的局部極小值。(2)由于將均值點(diǎn)作為聚類中心進(jìn)行新一輪計(jì)算，遠(yuǎn)離數(shù)據(jù)密集區(qū)的孤立點(diǎn)和噪聲點(diǎn)會(huì)導(dǎo)致聚類中心偏離真正的數(shù)據(jù)密集區(qū)，所以K-均值算法對(duì)噪聲點(diǎn)和孤立點(diǎn)很敏感。

1.3 K-中心點(diǎn)輪換算法

K-平均算法在計(jì)算簇內(nèi)平均值時(shí)很容易被 “噪聲”和孤立點(diǎn)所影響。為了改進(jìn)這個(gè)缺點(diǎn)，可以采用用簇中位置最中心的點(diǎn)（中心點(diǎn)）來取代K-平均算法中簇中點(diǎn)的平均值。這種劃分方法仍然是基于最小化所有點(diǎn)與其參照點(diǎn)之間的相異度(如常采用歐氏距離來度量)之和的原則來執(zhí)行的。

K-中心點(diǎn)輪換算法(K-mediods)是以k為輸入?yún)?shù)，試圖以窮舉的方式重復(fù)地使用目標(biāo)函數(shù)值更小的對(duì)象來代替當(dāng)前的中心點(diǎn)，從而將n個(gè)對(duì)象分為k個(gè)簇。具體的算法過程描述如下：對(duì)基于中心點(diǎn)的劃分的一種K-中心點(diǎn)變種算法，其輸入為結(jié)果簇的數(shù)目k、包含n個(gè)對(duì)象的數(shù)據(jù)集；輸出為k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的偏差準(zhǔn)則函數(shù)最小。

K-mediods算法流程如下：

(2)repeat；

(3)將每個(gè)對(duì)象（重新）指派給離它最近的中心點(diǎn)所代表的簇，按照式(1)計(jì)算當(dāng)前的目標(biāo)函數(shù)值；

(4)對(duì) n 個(gè)對(duì)象中的每一個(gè)對(duì)象 Oj（j=1，2，…，n）依次執(zhí)行下面的過程：試圖用當(dāng)前對(duì)象Oj去依次替換現(xiàn)有的 k 個(gè)中心點(diǎn)中的每一個(gè)中心點(diǎn) mi（i=1，2，…，k），并計(jì)算試圖替換后的目標(biāo)函數(shù)值，最終選擇替換后能獲得目標(biāo)函數(shù)值最小的那個(gè)中心點(diǎn)進(jìn)行替換。如果這k個(gè)待替換的中心點(diǎn)所對(duì)應(yīng)的目標(biāo)函數(shù)值比當(dāng)前的目標(biāo)函數(shù)值還要大，則不進(jìn)行替換；

(5)直到不發(fā)生變化；

(6)最終得到一個(gè)中心點(diǎn)集，根據(jù)這個(gè)集合，按照最近鄰原則分配所有對(duì)象到它所歸屬的簇中，得到的k個(gè)簇就是所有對(duì)象的一個(gè)局部優(yōu)化聚類結(jié)果。

1.4 算法對(duì)比分析

1.4.1 K-means算法性能

K-均值算法在步驟(3)和步驟(4)之間交互迭代，每一步都使目標(biāo)函數(shù)逐步下降，從而產(chǎn)生一個(gè)使目標(biāo)函數(shù)值逐步減小的迭代序列，它嘗試找出使目標(biāo)函數(shù)值取得最小的一個(gè)k劃分，但通常只能獲得一個(gè)局部優(yōu)化結(jié)果。算法的復(fù)雜度是O(nkt)，其中，n是所有點(diǎn)的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。

1.4.2 K-mediods算法性能

從算法的過程描述，可以看出該算法是一種單純型思想的算法，它以犧牲時(shí)間復(fù)雜度來獲取更好的聚類效果，下面簡(jiǎn)單分析一下該算法的時(shí)間復(fù)雜度。

病癥較輕微時(shí)，一般采取觀察并對(duì)癥療法?；痉椒ㄅc感冒一樣，需要一個(gè)可靜養(yǎng)的環(huán)境，注意水分的補(bǔ)充。并盡量避免傳染給其他人。

該算法由于要用到所有對(duì)象的距離度量矩陣，其時(shí)間復(fù)雜度是O(n2)。算法步驟(3)中將n個(gè)對(duì)象賦給k個(gè)中心點(diǎn)所代表的簇，需要時(shí)間復(fù)雜度為O(nk)；計(jì)算目標(biāo)函數(shù)值需要時(shí)間復(fù)雜度為O(n)；算法步驟(4)中在每一次試圖替換中心點(diǎn)后都需要重新將所有點(diǎn)賦給新的中心點(diǎn)所代表的簇并計(jì)算新的目標(biāo)函數(shù)值以供比較，所以這一步的時(shí)間復(fù)雜度是O(n2k2)。

1.4.3 K-mediods算法優(yōu)缺點(diǎn)

K-中心點(diǎn)輪換算法是一種使目標(biāo)函數(shù)下降最快的方法，它屬于啟發(fā)式搜索算法，能從n個(gè)對(duì)象中找出以k個(gè)中心點(diǎn)為代表的一個(gè)局部優(yōu)化劃分聚類。與K-均值算法比較，K-中心點(diǎn)輪換算法解決了K-均值算法本身的缺陷：

(1)解決了K-均值算法對(duì)初始值選擇依賴度大的問題。K-均值算法對(duì)于不同的初始值，結(jié)果往往得到不同的局部極小值。而K-中心點(diǎn)輪換算法采用輪換替換的方法替換中心點(diǎn)，從而與初始值的選擇沒有關(guān)系。

(2)解決了K-均值算法對(duì)噪聲和離群點(diǎn)的敏感性問題。由于該算法不使用平均值來更改中心點(diǎn)而是選用位置最靠近中心的對(duì)象作為中心代表點(diǎn)，因此并不容易受極端數(shù)據(jù)的影響，具有很好的魯棒性。

K-中心點(diǎn)輪換算法也存有以下缺點(diǎn)：

(1)由于K-中心點(diǎn)輪換算法是基于劃分的一種聚類算法，仍然要求輸入要得到的簇的數(shù)目k，所以當(dāng)k的取值不正確時(shí)，對(duì)聚類的結(jié)果影響甚大。

(2)從以上的時(shí)間復(fù)雜度也可以看出，當(dāng)n和k較大時(shí)，計(jì)算代價(jià)很高，所以將該算法應(yīng)用于大數(shù)據(jù)集時(shí)不是很理想。

1.5 K-means與K-mediods對(duì)比測(cè)試結(jié)果與分析

本次測(cè)試采用weka Iris數(shù)據(jù)集對(duì)比K-均值算法與K-中心點(diǎn)輪換算法對(duì)初始值的依賴性，對(duì)比結(jié)果如表1所示。通過改變初始隨機(jī)數(shù)種子，使初始值產(chǎn)生變化。

表1 K-means與K-mediods算法對(duì)比

由上述對(duì)比實(shí)驗(yàn)可以得出結(jié)論：通過改變隨機(jī)數(shù)從而使初始值選取不同時(shí)，K-means算法隨著初始值選擇的不同而不同，聚類結(jié)果差別很大；而K-mediods算法聚類結(jié)果與初始值的選擇沒有關(guān)系。

對(duì)兩種算法的聚類效果進(jìn)行對(duì)比實(shí)驗(yàn)，對(duì)比結(jié)果如表2所示。

表2 K-mediods、K-means算法的聚類錯(cuò)誤率比較

從表2可以看出，對(duì)于同一個(gè)數(shù)據(jù)集，K-mediods算法比K-means算法的聚類平均錯(cuò)誤率低。

2 K-mediods算法的改進(jìn)方向

針對(duì)K-中心點(diǎn)輪換算法的不足，可以從以下兩個(gè)方面對(duì)其加以改進(jìn)。

2.1 基于抽樣的K-mediods算法

K-中心點(diǎn)輪換算法對(duì)小數(shù)據(jù)集非常有效，但對(duì)大數(shù)據(jù)集沒有良好的可伸縮性。為了處理較大的數(shù)據(jù)集，可以采用基于抽樣的方法，即不考慮整個(gè)數(shù)據(jù)集合，而是選擇實(shí)際數(shù)據(jù)的一小部分作為數(shù)據(jù)的代表。在抽樣過程中，抽樣算法盡可能保證數(shù)據(jù)不失真，又能體現(xiàn)數(shù)據(jù)的原始分布特征(如圖1所示)，然后對(duì)抽樣數(shù)據(jù)集使用K-中心點(diǎn)輪換算法。當(dāng)然基于抽樣的算法的有效性取決于抽樣數(shù)據(jù)集與原數(shù)據(jù)集的相似度。在實(shí)際使用中，可以抽取原始數(shù)據(jù)集D的多個(gè)樣本，然后對(duì)每一個(gè)樣本Di進(jìn)行K-中心點(diǎn)輪換算法，從中選擇目標(biāo)準(zhǔn)則函數(shù)E最小的結(jié)果作為輸出。

2.2 簇?cái)?shù)目的確定[4]

本文介紹了一種直觀簡(jiǎn)便可行的確定簇?cái)?shù)目的方法：爬山法——最優(yōu)聚類數(shù)的邏輯判定法。

在類別數(shù)未知的情況下使用K-中心點(diǎn)輪換算法時(shí)，可以假設(shè)類別數(shù)是逐步增加的，例如對(duì) K＝1，2，3，…分別使用該算法。顯然準(zhǔn)則函數(shù)EK是隨K的增加而單調(diào)減少的。如果樣本集的合理聚類數(shù)為K類，當(dāng)類別數(shù)繼續(xù)增大時(shí)，相當(dāng)于將聚類很好的類別又分成子類，則EK值雖然繼續(xù)減少但會(huì)呈現(xiàn)平緩趨勢(shì)，如果作一條EK值隨 K變化的曲線(如圖 2、圖 3所示)，則其拐點(diǎn)對(duì)應(yīng)的類別數(shù)就比較接近于最優(yōu)聚類數(shù)。對(duì)weka中Iris和weather數(shù)據(jù)集分別進(jìn)行8次實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖2、圖 3所示。結(jié)果表明K＝3是較合適的聚類數(shù)。這個(gè)結(jié)果也與數(shù)據(jù)集實(shí)際類別數(shù)相一致。

從采用K-中心點(diǎn)輪換算法對(duì)同一數(shù)據(jù)文件的聚類結(jié)果可以看到，最終目標(biāo)函數(shù)值與聚類數(shù)目K大致滿足一個(gè)規(guī)律：合適的聚類數(shù)目往往就在平均最終目標(biāo)函數(shù)值與聚類數(shù)目K所形成的關(guān)系折線的拐角位置。因?yàn)檫@個(gè)目標(biāo)函數(shù)在距離空間中取的是所有點(diǎn)到其最近的中心點(diǎn)的距離的總和，一種極端情況是每個(gè)點(diǎn)都是中心點(diǎn)，聚類數(shù)目等于所有點(diǎn)數(shù)目，顯然目標(biāo)函數(shù)的值是0。從直觀上可以推測(cè)，聚類數(shù)目越大，目標(biāo)函數(shù)值就越小，而最終目標(biāo)函數(shù)值的下降由快到慢的那個(gè)轉(zhuǎn)折位置往往就是一個(gè)關(guān)鍵位置。

通過對(duì)K-中心點(diǎn)輪換算法進(jìn)行抽樣改進(jìn)，成功地解決了K-中心點(diǎn)輪換算法時(shí)間復(fù)雜度問題，使其能夠處理大數(shù)據(jù)集的聚類分析問題。同時(shí)，拐點(diǎn)法是通過實(shí)踐總結(jié)出的一套簡(jiǎn)單有效的判斷最優(yōu)聚類數(shù)的方法。實(shí)驗(yàn)表明，該方法簡(jiǎn)單可行，計(jì)算量小，同時(shí)不影響現(xiàn)有的算法結(jié)構(gòu)。通過上述兩個(gè)改進(jìn)措施，使K-中心點(diǎn)輪換算法真正擁有更好的實(shí)際應(yīng)用價(jià)值。

[1]HAN J W，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)[M].范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2004：119-124，188-196.

[2]鄭人杰，殷人昆，陶永雷.實(shí)用軟件工程[M].北京：清華大學(xué)出版社，1999：51-53.

[3]JAIN A K，DUBES R C.Algorithms for clustering data[M].NJ，USA：Prentice-Hall，Inc.，1988.

[4]周世兵，徐振源，唐旭清.新的 K-均值算法最佳聚類數(shù)確定方法[J].計(jì)算機(jī)工程與應(yīng)用，2010，46(16)：27-31.

[5]KAUFMAN L，ROUSSEEUW P J.Finding groups in data：an introduction to cluster analysis[M].New York：John Wiley&Sons，1990.