聚類算法分析及其性能比較

楊 柳 張俊芝

（河北大學(xué)經(jīng)濟管理實驗教學(xué)中心，河北 保定 071000）

1 k-means算法

k-means（k-平均）算法是一種常用的基于劃分的聚類算法。k-means算法是以k為參數(shù)，把n個對象分成k個簇，使簇內(nèi)具有較高的相似度，而簇間的相似度較低。k-means的處理過程為：首先隨機選擇k個對象作為初始的k個簇的質(zhì)心；然后將其余對象根據(jù)其與各個簇的質(zhì)心的距離分配到最近的簇；最后重新計算各個簇的質(zhì)心。不斷重復(fù)此過程，直到目標(biāo)函數(shù)最小為止。

k-means嘗試找出使平方誤差函數(shù)值最小的k個劃分。當(dāng)數(shù)據(jù)分布較均勻，且簇與簇之間區(qū)別明顯時，它的效果較好。面對大規(guī)模數(shù)據(jù)集，該算法是相對可擴展的，并且具有較高的效率。算法的時間復(fù)雜度為O(nkt)，其中，n為數(shù)據(jù)集中對象的數(shù)目，k為期望得到的簇的數(shù)目，t為迭代的次數(shù)。通常情況下，算法會終止于局部最優(yōu)解。但是，k-means算法只有在簇的平均值被定義的情況下才能使用，這可能不適用于某些應(yīng)用，例如涉及有非數(shù)值屬性的數(shù)據(jù)。其次，這種算法要求事先給出要生成的簇的數(shù)目k，顯然這對用戶提出了過高的要求，并且由于算法的初始聚類中心是隨機選擇的，而不同的初始中心對聚類結(jié)果有很大的影響。另外，k-means算法不適用于發(fā)現(xiàn)非凸面形狀的簇，或者大小差別很大的簇，而且它對于噪音和孤立點數(shù)據(jù)是敏感的。

2 k-medoids算法

k-medoids算法是k-means算法的一個改進(jìn)。在k-means算法中，一個異常數(shù)據(jù)的取值可能會很大，從而會影響對數(shù)據(jù)分布的估計，因此在k-medoids算法中設(shè)想利用一個medoid作為一個參考點來代替k-means算法中各簇的均值。k-medoids算法的基本思想是首先為每個簇找到一個代表對象從而確定k個簇，如果替換一個簇代表能夠改善所獲得劃分質(zhì)量的話，那么就可以用新的代表對象替換老的代表對象。為了判定一個非參照點Orandom是否是當(dāng)前參照點Oj的一個好的替代，對于每一個非參照點p，考慮以下四種情況：

p當(dāng)前隸屬于參照點Oj。若Oj被O－random所替換作為參照點，且p距離一個Oi最近，i≠j，則 p 被重新分配給 Oi；

p當(dāng)前隸屬于參照點Oj。若Oj被O－random所替換作為參照點，且p距離Orandom最近，則p被重新分配給Orandom；

p當(dāng)前隸屬于參照點Oi。i≠j。若Oj被Orandom所替換作為參照點，且p距離Oi最近，則p的隸屬不發(fā)生變化；

p當(dāng)前隸屬于參照點Oi。i≠j。若Oj被Orandom所替換作為參照點，且p距離Orandom最近，則p被重新分配給Orandom。

3 最大最小距離算法

最大最小距離算法是一種在模式識別領(lǐng)域常用的方法，基本思想是取距離盡可能遠(yuǎn)的對象作為簇中心對數(shù)據(jù)進(jìn)行聚類。最大最小距離算法實現(xiàn)簡單，處理大數(shù)據(jù)集的能力較強，但是算法對噪音數(shù)據(jù)敏感，在存在噪音數(shù)據(jù)的情況下，聚類中心可能偏移真正的類別中心較遠(yuǎn)。同時，該算法的輸出結(jié)果也依賴于常數(shù)m的選擇，選擇不同的m得到的聚類結(jié)果也不同。由于算法中的距離也是采用歐氏距離，所以也只適合發(fā)現(xiàn)球形的簇。

4 CURE算法

CURE算法是一個自底向上的層次聚類算法，它把層次算法和劃分算法結(jié)合起來，克服了傾向于發(fā)現(xiàn)球形簇的不足。CURE算法在計算簇間的距離時，既不是用一個質(zhì)心，也不是用所有的點，而是用一組點，也就是說，它是用多個對象而不是一個對象來代表一個簇。實際上，CURE算法是從一個簇中選擇一定數(shù)目散布較好的點來代表該簇，這些點用于確定該簇的形狀和大小。然后把它們按照一定的因子向簇的質(zhì)心收縮。通過調(diào)整收縮因子的值，就可以識別不同類型的聚類。使用這些點收縮之后的位置來代表簇，找出最近的兩個簇，然后把它們進(jìn)行合并。重復(fù)上述過程，直到得到期望得到的簇的數(shù)目。

在大數(shù)據(jù)集的聚類問題上，CURE采取隨機采樣的方法。隨機采樣是在精度與效率之間的折衷，通常情況下，中等規(guī)模的采樣就能較好地保證聚類的質(zhì)量。為加速簇的收縮速度，CURE算法首先對樣本數(shù)據(jù)進(jìn)行劃分，并在每個劃分塊內(nèi)局部聚類，去除孤立點后，再對每個劃分塊中局部的簇進(jìn)行聚類生成最后的簇。

CURE算法克服了利用單個代表點或基于質(zhì)心的方法的缺點，可以發(fā)現(xiàn)非球形及大小差異較大的簇。簇或離散點的收縮降低了CURE算法對孤立點的敏感性。

5 STING算法

STIN算法是一種基于網(wǎng)格的多分辨率聚類方法，它將空間區(qū)域劃分為若干矩形網(wǎng)格單元。針對不同級別的分辨率，通常存在多個級別的矩形單元，這些單元形成了一個層次結(jié)構(gòu)，高層的每個單元被劃分為多個低一層的單元。關(guān)于每個網(wǎng)格單元屬性的統(tǒng)計信息，如平均值、最大值、最小值等，被預(yù)先計算和存儲。

高層單元的統(tǒng)計參數(shù)可以很容易地從低層單元的統(tǒng)計參數(shù)中計算得到。這些統(tǒng)計參數(shù)包括屬性無關(guān)的參數(shù)、計數(shù)count和屬性相關(guān)的參數(shù)、均值m、標(biāo)準(zhǔn)方差s、最小值min、最大值max以及該單元中屬性值遵循的分布(distribution)類型，例如正態(tài)分布、平均分布、指數(shù)分布等。當(dāng)數(shù)據(jù)被裝載進(jìn)數(shù)據(jù)庫時，底層單元的參數(shù)count、m、min和max直接進(jìn)行計算。

6 幾種常用的聚類算法的比較總結(jié)

基于以上分析，下面對常用聚類算法的性能從可伸縮性、發(fā)現(xiàn)聚類的形狀、對“噪音”數(shù)據(jù)的敏感性、對數(shù)據(jù)輸入的順序敏感性和算法效率五個方面進(jìn)行比較，得到表1中的結(jié)果。

?

[1]J.Yi,T.Nasukawa,R.Bunescu,W.Niblack.Sentiment analyzer: Extracting Sentiments about a Given Topic using Natural Language Processing Techniques [A].Proceedings of the 3rd IEEE International Conference on Data Mining[C].November 19-22,2003.

[2]鄒濤，王繼成，黃源等.中文文檔自動分類系統(tǒng)的設(shè)計與實現(xiàn)[J].中文信息學(xué)報，1999，13(3):26-32.

[3]李曉黎，劉繼敏，史忠植.概念推理網(wǎng)絡(luò)及其在文本分類中的應(yīng)用[J].計算機研究與發(fā)展，2000，37(9):1032-1038.

[4]范焱，陳恩紅，王清毅等.超文本協(xié)調(diào)分類器的性能研究[J].計算機研究與發(fā)展，2007，37(9):1027-1031.