各種聚類算法的比較

1、聚類分析是一種重要的人類行為，早在孩提時代，一個人就通過不斷 改進下意識中的聚類模式來學會如何區(qū)分貓狗、動物植物。目前在許 多領域都得到了廣泛的研究和成功的應用，如用于模式識別、數(shù)據(jù)分 析、圖像處理、市場研究、客戶分割、Web文檔分類等。聚類就是按照某個特定標準（如距離準則）把一個數(shù)據(jù)集分割成不 同的類或簇，使得同一個簇內的數(shù)據(jù)對象的相似性盡可能大，同時不 在同一個簇中的數(shù)據(jù)對象的差異性也盡可能地大。即聚類后同一類的 數(shù)據(jù)盡可能聚集到一起，不同數(shù)據(jù)盡量分離。聚類技術正在蓬勃發(fā)展，對此有貢獻的研究領域包括數(shù)據(jù)挖掘、統(tǒng) 計學、機器學習、空間數(shù)據(jù)庫技術、生物學以及市場營銷等。各種聚 類方法也被不斷提

2、出和改進，而不同的方法適合于不同類型的數(shù)據(jù)， 因此對各種聚類方法、聚類效果的比較成為值得研究的課題。1聚類算法的分類目前，有大量的聚類算法。而對于具體應用，聚類算法的選擇取決 于數(shù)據(jù)的類型、聚類的目的。如果聚類分析被用作描述或探查的工具， 可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結果。主要的聚類算法可以劃分為如下幾類：劃分方法、層次方法基于 密度的方法、基于網(wǎng)格的方法以及基于模型的方法4-6。每一類中都存在著得到廣泛應用的算法，例如：劃分方法中的 k-means聚類算法、層次方法中的凝聚型層次聚類算法、基于模型方 法中的神經(jīng)網(wǎng)絡聚類算法等。目前，聚類問題的研究不僅僅局限于上述的硬聚類

3、，即每一個數(shù)據(jù) 只能被歸為一類，模糊聚類也是聚類分析中研究較為廣泛的一個分 支。模糊聚類通過隸屬函數(shù)來確定每個數(shù)據(jù)隸屬于各個簇的程度，而 不是將一個數(shù)據(jù)對象硬性地歸類到某一簇中。目前已有很多關于模糊 聚類的算法被提出，如著名的FCM算法等。本文主要對k-means聚類算法、凝聚型層次聚類算法、神經(jīng)網(wǎng)絡聚 類算法之SOM,以及模糊聚類的FCM算法通過通用測試數(shù)據(jù)集進行聚 類效果的比較和分析。2四種常用聚類算法研究2.1 k-means聚類算法k-means是劃分方法中較經(jīng)典的聚類算法之一。由于該算法的效率 高，所以在對大規(guī)模數(shù)據(jù)進行聚類時被廣泛應用。目前，許多算法均 圍繞著該算法進行擴展和改進。

4、k-means算法以k為參數(shù)，把n個對象分成k個簇，使簇內具有較 高的相似度，而簇間的相似度較低。k-means算法的處理過程如下： 首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值 或中心;對剩余的每個對象，根據(jù)其與各簇中心的距離，將它賦給最 近的簇；然后重新計算每個簇的平均值。這個過程不斷重復，直到準 則函數(shù)收斂。通常，采用平方誤差準則，其定義如下：/-= X lp-叫 za 尹 E這里E是數(shù)據(jù)庫中所有對象的平方誤差的總和，p是空間中的點， mi是簇Ci的平均值。該目標函數(shù)使生成的簇盡可能緊湊獨立，使用 的距離度量是歐幾里得距離當然也可以用其他距離度量。k-means聚類算法的

5、算法流程如下：輸入：包含n個對象的數(shù)據(jù)庫和簇的數(shù)目k ；輸出：k個簇，使平方誤差準則最小。步驟：任意選擇k個對象作為初始的簇中心；repeat；根據(jù)簇中對象的平均值，將每個對象(重新)賦予最類似的 簇；更新簇的平均值，即計算每個簇中對象的平均值；until不再發(fā)生變化。2.2層次聚類算法根據(jù)層次分解的順序是自底向上的還是自上向下的，層次聚類算法分 為凝聚的層次聚類算法和分裂的層次聚類算法。凝聚型層次聚類的策略是先將每個對象作為一個簇，然后合并這些 原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結 條件被滿足。絕大多數(shù)層次聚類屬于凝聚型層次聚類，它們只是在簇 間相似度的定義上有所不同

6、。四種廣泛采用的簇間距離度量方法如 下：最距離：*Lnt,i1 |最大距離：心E&Jfhk,匚S 卜十 |平均值的距離：也50用二 mi-TUj |平均距離：= L iiCii .Xp.Cii -p |這里，p-pr是兩個對象P和P，之間的距離，叫是 除n的平均值，牌是簇如中對象的數(shù)目o這里給出采用最小距離的凝聚層次聚類算法流程：將每個對象看作一類，計算兩兩之間的最小距離；將距離最小的兩個類合并成一個新類；重新計算新類與所有類之間的距離；重復(2)、(3)，直到所有類最后合并成一類。2.3 SOM聚類算法SOM神經(jīng)網(wǎng)絡是由芬蘭神經(jīng)網(wǎng)絡專家Kohonen教授提出的，該算法 假設在輸入對象中存在一

7、些拓撲結構或順序，可以實現(xiàn)從輸入空間(n 維)到輸出平面(2維)的降維映射，其映射具有拓撲特征保持性質與 實際的大腦處理有很強的理論聯(lián)系。SOM網(wǎng)絡包含輸入層和輸出層。輸入層對應一個高維的輸入向量， 輸出層由一系列組織在2維網(wǎng)格上的有序節(jié)點構成，輸入節(jié)點與輸出 節(jié)點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單 元，即獲勝單元，對其更新。同時，將鄰近區(qū)域的權值更新，使輸出 節(jié)點保持輸入向量的拓撲特征。算法流程:網(wǎng)絡初始化，對輸出層每個節(jié)點權重賦初值；將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的 權重向量；定義獲勝單元，在獲勝單元的鄰近區(qū)域調整權重使其向輸入向 量靠攏；提供新

8、樣本、進行訓練；收縮鄰域半徑、減小學習率、重復，直到小于允許值，輸出聚 類結果。2.4 FCM聚類算法1965年美國加州大學柏克萊分校的扎德教授第一次提出了 集合 的概念。經(jīng)過十多年的發(fā)展，模糊集合理論漸漸被應用到各個實際應 用方面。為克服非此即彼的分類缺點，出現(xiàn)了以模糊集合論為數(shù)學基 礎的聚類分析。用模糊數(shù)學的方法進行聚類分析，就是模糊聚類分析。FCM算法是一種以隸屬度來確定每個數(shù)據(jù)點屬于某個聚類程度的 算法。該聚類算法是傳統(tǒng)硬聚類算法的一種改進。設數(shù)冤集上=任心,.,，它的摸糊c劃分可用模糊矩陣t/=| i.-J表示，偶陣(7的元素與表7F第r fr = I .2 , , .I個數(shù)據(jù)點屬于

9、第隸屬度,*滿垣址下條件：Vj - y I ： Vtjuf(= |0,1 ; Uy0LI前被廣泛使用的聚類準則為取類內如權誤差平方和的極值，即：5弓氣項1；：|丁二】心其| V為聚類中心或為加權指數(shù)，4 國，珀)二 II II算法流程:標準化數(shù)據(jù)矩陣；建立模糊相似矩陣，初始化隸屬矩陣；算法開始迭代，直到目標函數(shù)收斂到極小值；根據(jù)迭代結果，由最后的隸屬矩陣確定數(shù)據(jù)所屬的類，顯示最 后的聚類結果。3四種聚類算法試驗3.1試驗數(shù)據(jù)實驗中，選取專門用于測試分類、聚類算法的國際通用的UCI數(shù)據(jù) 庫中的IRIS13數(shù)據(jù)集，IRIS數(shù)據(jù)集包含150個樣本數(shù)據(jù)，分別取 自三種不同的鶯尾屬植物setosa、ve

10、rsicolor和virginica的花朵 樣本，每個數(shù)據(jù)含有4個屬性，即萼片長度、萼片寬度、花瓣長度， 單位為cm。在數(shù)據(jù)集上執(zhí)行不同的聚類算法，可以得到不同精度的 聚類結果。3.2試驗結果說明文中基于前面所述各算法原理及算法流程，用matlab進行編程運 算，得到表1所示聚類結果。表1 一神聚類方法的實驗對比結果聚類A , 4 十耘行d* 1 方法 樣本數(shù) 時間壓 L準確世n瑚)L |瞄時H 知TF邱I，雌匚故聚類51. .-0.12P44-J- 成心1 以任門104可1co SKI225.267 2fi3S6如表1所示，對于四種聚類算法，按三方面進行比較：(1)聚錯樣 本數(shù)：總的聚錯的樣本數(shù)，即各類中聚錯的樣本數(shù)的和；運行時 間：即聚類整個過程所耗費的時間，單位為s； (3)平均準確度：設 原數(shù)據(jù)集有k個類，用ci表示第i類，ni為ci中樣本的個數(shù)，mi為 聚類正確的個數(shù)則mi/ni為第i類中的精度，則平均精度為：IE二! gw3.3試驗結果分析四種聚類算法中，在運行時間及準確度方面綜合考慮，k-means和FCM 相對優(yōu)于其他。但是，各個算法還是存在固定缺點:k-means聚類算 法的初始點選擇不穩(wěn)定，是隨機選取的，這就引起聚類結果的不穩(wěn)定， 本實驗中雖是經(jīng)過多次實驗取的平均值，但是具體初始點的選擇方法 還需進一步研究；層次聚類雖然不需要