引言

　　聚類分析是人類的區(qū)分標志之一，從孩提時代開始，一個人就下意識地學會區(qū)分動植物，并且不斷改進。這一原理在如今不少領域得到了相應的研究和應用，比如模式識別、數(shù)據(jù)分析、圖像處理、Web文檔分類等。

　　將物理或抽象對象的集合分成由類似的對象組成的多個類的過程被稱為聚類。由聚類所生成的簇是一組數(shù)據(jù)對象的集合，這些對象與同一個簇中的對象彼此相似，與其他簇中的對象相異?！拔镆灶惥郏艘匀悍帧?，在自然科學和社會科學中，存在著大量的分類問題。

　　聚類技術正在蓬勃發(fā)展，對此有貢獻的研究領域包括數(shù)據(jù)挖掘、統(tǒng)計學、機器學習、空間數(shù)據(jù)庫技術、生物學以及市場營銷等。各種聚類方法也被不斷提出和改進，而不同的方法適合于不同類型的數(shù)據(jù)，因此對各種聚類方法、聚類效果的比較成為值得研究的課題。

　　1 聚類算法的分類

　　現(xiàn)在有很多的聚類算法，而在實際應用中，正確選擇聚類算法的則取決于數(shù)據(jù)的類型、聚類的目的等因素。如果聚類分析被用作描述或探查的工具，可以對同樣的數(shù)據(jù)嘗試多種算法，以發(fā)現(xiàn)數(shù)據(jù)可能揭示的結果。

　　已知的聚類算法可以大致劃分為以下幾類：劃分方法、層次方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。

　　每一個類型的算法都被廣泛地應用著，例如：劃分方法中的k-means聚類算法、層次方法中的凝聚型層次聚類算法、基于模型方法中的神經(jīng)網(wǎng)絡聚類算法等。

　　聚類問題的研究早已不再局限于上述的硬聚類，即每一個數(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ù)進行聚類時廣泛應用。目前，許多算法均圍繞著該算法進行擴展和改進。

　　k-means算法以k為參數(shù)，把n個對象分成k個簇，使簇內(nèi)具有較高的相似度，而簇間的相似度較低。k-means算法的處理過程如下：首先，隨機地選擇k個對象，每個對象初始地代表了一個簇的平均值或中心；對剩余的每個對象，根據(jù)其與各簇中心的距離，將它賦給近的簇；然后重新計算每個簇的平均值。這個過程不斷重復，直到準則函數(shù)收斂。通常，采用平方誤差準則，其定義如下：

　　這里E是數(shù)據(jù)庫中所有對象的平方誤差的總和，p是空間中的點，mi是簇Ci的平均值。該目標函數(shù)使生成的簇盡可能緊湊獨立，使用的距離度量是歐幾里得距離，當然也可以用其他距離度量。k-means聚類算法的算法流程如下：

　　輸入：包含n個對象的數(shù)據(jù)庫和簇的數(shù)目k；

　　輸出：k個簇，使平方誤差準則。

　　步驟：

　?。?） 任意選擇k個對象作為初始的簇中心；

　?。?） repeat；

　　（3） 根據(jù)簇中對象的平均值，將每個對象（重新）賦予類似的簇；

　?。?） 更新簇的平均值，即計算每個簇中對象的平均值；

　?。?） until不再發(fā)生變化。

　　2.2  層次聚類算法

　　根據(jù)層次分解的順序，層次聚類算法分為凝聚的層次聚類算法和分裂的層次聚類算法。

　　凝聚型層次聚類的策略是先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。絕大多數(shù)層次聚類屬于凝聚型層次聚類，它們只是在簇間相似度的定義上有所不同。四種廣泛采用的簇間距離度量方法如下：

　　這里給出采用距離的凝聚層次聚類算法流程：

　?。?） 將每個對象看作一類，計算兩兩之間的距離；

　　（2） 將距離的兩個類合并成一個新類；

　?。?） 重新計算新類與所有類之間的距離；

　　（4） 重復（2）、（3），直到所有類合并成一類。

　　2.3 SOM聚類算法

　　SOM神經(jīng)網(wǎng)絡是由芬蘭神經(jīng)網(wǎng)絡Kohonen教授提出的，該算法假設在輸入對象中存在一些拓撲結構或順序，可以實現(xiàn)從輸入空間（n維）到輸出平面（2維）的降維映射，其映射具有拓撲特征保持性質(zhì)，與實際的大腦處理有很強的理論聯(lián)系。

　　SOM網(wǎng)絡包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網(wǎng)格上的有序節(jié)點構成，輸入節(jié)點與輸出節(jié)點通過權重向量連接。學習過程中，找到與之距離短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區(qū)域的權值更新，使輸出節(jié)點保持輸入向量的拓撲特征。

　　算法流程：

　?。?） 網(wǎng)絡初始化，對輸出層每個節(jié)點權重賦初值；

　?。?） 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離的權重向量；

　?。?） 定義獲勝單元，在獲勝單元的鄰近區(qū)域調(diào)整權重使其向輸入向量靠攏；

　　（4） 提供新樣本、進行訓練；

　　（5） 收縮鄰域半徑、減小學習率、重復，直到小于允許值，輸出聚類結果。

　　2.4 FCM聚類算法

　　1965年美國加州大學柏克萊分校的扎德教授次提出了‘集合’的概念。經(jīng)過十多年的發(fā)展，模糊集合理論漸漸被應用到各個實際應用方面。為克服非此即彼的分類缺點，出現(xiàn)了以模糊集合論為數(shù)學基礎的聚類分析。用模糊數(shù)學的方法進行聚類分析，就是模糊聚類分析。

　　FCM算法是一種以隸屬度來確定每個數(shù)據(jù)點屬于某個聚類程度的算法。該聚類算法是傳統(tǒng)硬聚類算法的一種改進。

　　算法流程：

　?。?） 標準化數(shù)據(jù)矩陣；

　　（2） 建立模糊相似矩陣，初始化隸屬矩陣；

　?。?） 算法開始迭代，直到目標函數(shù)收斂到極小值；

　?。?） 根據(jù)迭代結果，由的隸屬矩陣確定數(shù)據(jù)所屬的類，顯示的聚類結果。

　　3 試驗

　　3.1 試驗數(shù)據(jù)

　　實驗中，選取專門用于測試分類、聚類算法的國際通用的UCI數(shù)據(jù)庫中的IRIS數(shù)據(jù)集，IRIS數(shù)據(jù)集包含150個樣本數(shù)據(jù)，分別取自三種不同的鶯尾屬植物setosa、versicolor和virginica的花朵樣本，每個數(shù)據(jù)含有4個屬性，即萼片長度、萼片寬度、花瓣長度，單位為cm。在數(shù)據(jù)集上執(zhí)行不同的聚類算法，可以得到不同的聚類結果。

　　3.2 試驗結果說明

　　文中基于前面所述各算法原理及算法流程，用matlab進行編程運算，得到表1所示聚類結果。

　　如表1所示，對于四種聚類算法，按三方面進行比較：

　?。?）聚錯樣本數(shù)：總的聚錯的樣本數(shù)，即各類中聚錯的樣本數(shù)的和；

　?。?）運行時間：即聚類整個過程所耗費的時間，單位為s；

　　（3）平均準確度：設原數(shù)據(jù)集有k個類，用ci表示第i類，ni為ci中樣本的個數(shù)，mi為聚類正確的個數(shù)，則mi/ni為第i類中的，則平均為：

　　3.3 試驗結果分析

　　四種聚類算法中，在運行時間及準確度方面綜合考慮，k-means和FCM相對優(yōu)于其他。但是，各個算法還是存在固定缺點：k-means聚類算法的初始點選擇不穩(wěn)定，是隨機選取的，這就引起聚類結果的不穩(wěn)定，本實驗中雖是經(jīng)過多次實驗取的平均值，但是具體初始點的選擇方法還需進一步研究；層次聚類雖然不需要確定分類數(shù)，但是一旦一個分裂或者合并被執(zhí)行，就不能修正，聚類質(zhì)量受限制；FCM對初始聚類中心敏感，需要人為確定聚類數(shù)，容易陷入局部解；SOM與實際大腦處理有很強的理論聯(lián)系。但是處理時間較長，需要進一步研究使其適應大型數(shù)據(jù)庫。

　　4 結語

　　聚類分析因其在許多領域的成功應用而展現(xiàn)出誘人的應用前景，除經(jīng)典聚類算法外，各種新的聚類方法正被不斷被提出。