摘  要： 對(duì)傳統(tǒng)的K-平均算法作了簡(jiǎn)單的介紹和討論，提出了一種具有單純型法思想的K-中心點(diǎn)輪換法。分別對(duì)比了K-均值算法與K-中心點(diǎn)輪換算法的時(shí)間復(fù)雜度，針對(duì)K-中心點(diǎn)輪換算法的時(shí)間復(fù)雜度提出了一種基于抽樣原理的改進(jìn)算法，并對(duì)K-中心點(diǎn)輪換算法聚類數(shù)目的選擇進(jìn)行了各種改進(jìn)方法的探索。同時(shí)，基于主流的weka開(kāi)源數(shù)據(jù)挖掘工具實(shí)現(xiàn)了改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明了算法的有效性。
關(guān)鍵詞： K-均值；K-中心點(diǎn)輪換；抽樣；聚類數(shù)目；weka

    作為統(tǒng)計(jì)學(xué)的一個(gè)分支，聚類分析已經(jīng)被研究了許多年[1-5]，但主要集中在基于距離的聚類分析上。在機(jī)器學(xué)習(xí)領(lǐng)域，聚類是無(wú)指導(dǎo)學(xué)習(xí)的一個(gè)例子。與分類不同，聚類不依賴于預(yù)先定義的類和帶標(biāo)號(hào)的訓(xùn)練實(shí)例，可見(jiàn)，聚類是觀察式學(xué)習(xí)，而不是示例式學(xué)習(xí)[1]。在概念聚類中，一組點(diǎn)只有當(dāng)它們可以被一個(gè)概念描述時(shí)才形成一個(gè)簇。這不同于基于幾何距離來(lái)度量相似度的傳統(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é)果，往往也與具體問(wèn)題、具體要求有關(guān)。將聚類問(wèn)題轉(zhuǎn)化為一種優(yōu)化問(wèn)題，再通過(guò)數(shù)學(xué)規(guī)劃的方法來(lái)進(jìn)行求解是研究聚類分析的一個(gè)重要方向。
    給定n個(gè)對(duì)象或者數(shù)據(jù)元組的數(shù)據(jù)庫(kù)，應(yīng)用劃分方法構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一簇，k≤n。也就是說(shuō)，將數(shù)據(jù)劃分為k組，并滿足如下要求：(1)每一組至少包含一個(gè)對(duì)象；(2)每個(gè)對(duì)象必須只屬于一組。
    給定要構(gòu)建的劃分?jǐn)?shù)目k，應(yīng)用劃分方法創(chuàng)建一個(gè)初始劃分。然后采用迭代重定位技術(shù)，嘗試通過(guò)對(duì)象在組間移動(dòng)來(lái)改進(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)的平均值(被看作簇的重心)來(lái)進(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ù)收斂。
   
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)）來(lái)取代K-平均算法中簇中點(diǎn)的平均值。這種劃分方法仍然是基于最小化所有點(diǎn)與其參照點(diǎn)之間的相異度(如常采用歐氏距離來(lái)度量)之和的原則來(lái)執(zhí)行的。
    K-中心點(diǎn)輪換算法(K-mediods)是以k為輸入?yún)?shù)，試圖以窮舉的方式重復(fù)地使用目標(biāo)函數(shù)值更小的對(duì)象來(lái)代替當(dāng)前的中心點(diǎn)，從而將n個(gè)對(duì)象分為k個(gè)簇。具體的算法過(guò)程描述如下：對(duì)基于中心點(diǎn)的劃分的一種K-中心點(diǎn)變種算法，其輸入為結(jié)果簇的數(shù)目k、包含n個(gè)對(duì)象的數(shù)據(jù)集；輸出為k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的偏差準(zhǔn)則函數(shù)最小。
    K-mediods算法流程如下：
    (1)隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的中心點(diǎn)，這k個(gè)對(duì)象就組成了當(dāng)前的中心點(diǎn)集；
    (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í)行下面的過(guò)程：試圖用當(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è)局部?jī)?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è)局部?jī)?yōu)化結(jié)果。算法的復(fù)雜度是O(nkt)，其中，n是所有點(diǎn)的數(shù)目，k是簇的數(shù)目，t是迭代的次數(shù)。
1.4.2 K-mediods算法性能
    從算法的過(guò)程描述，可以看出該算法是一種單純型思想的算法，它以犧牲時(shí)間復(fù)雜度來(lái)獲取更好的聚類效果，下面簡(jiǎn)單分析一下該算法的時(shí)間復(fù)雜度。
    該算法由于要用到所有對(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è)局部?jī)?yōu)化劃分聚類。與K-均值算法比較，K-中心點(diǎn)輪換算法解決了K-均值算法本身的缺陷：
    (1)解決了K-均值算法對(duì)初始值選擇依賴度大的問(wèn)題。K-均值算法對(duì)于不同的初始值，結(jié)果往往得到不同的局部極小值。而K-中心點(diǎn)輪換算法采用輪換替換的方法替換中心點(diǎn)，從而與初始值的選擇沒(méi)有關(guān)系。
    (2)解決了K-均值算法對(duì)噪聲和離群點(diǎn)的敏感性問(wèn)題。由于該算法不使用平均值來(lái)更改中心點(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所示。通過(guò)改變初始隨機(jī)數(shù)種子，使初始值產(chǎn)生變化。

    從表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ù)集沒(méi)有良好的可伸縮性。為了處理較大的數(shù)據(jù)集，可以采用基于抽樣的方法，即不考慮整個(gè)數(shù)據(jù)集合，而是選擇實(shí)際數(shù)據(jù)的一小部分作為數(shù)據(jù)的代表。在抽樣過(guò)程中，抽樣算法盡可能保證數(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é)果作為輸出。

    從采用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)鍵位置。
    通過(guò)對(duì)K-中心點(diǎn)輪換算法進(jìn)行抽樣改進(jìn)，成功地解決了K-中心點(diǎn)輪換算法時(shí)間復(fù)雜度問(wèn)題，使其能夠處理大數(shù)據(jù)集的聚類分析問(wèn)題。同時(shí)，拐點(diǎn)法是通過(guò)實(shí)踐總結(jié)出的一套簡(jiǎn)單有效的判斷最優(yōu)聚類數(shù)的方法。實(shí)驗(yàn)表明，該方法簡(jiǎn)單可行，計(jì)算量小，同時(shí)不影響現(xiàn)有的算法結(jié)構(gòu)。通過(guò)上述兩個(gè)改進(jìn)措施，使K-中心點(diǎn)輪換算法真正擁有更好的實(shí)際應(yīng)用價(jià)值。
參考文獻(xiàn)
[1] HAN J W，KAMBER M．?dāng)?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.