聚類就是按照某個特定標準（如距離準則，即數據點之間的距離）把一個數據集分割成不同的類或簇，使得同一個簇內的數據對象的相似性盡可能大，同時不在同一個簇中的數據對象的差異性也盡可能地大。我們可以具體地理解為，聚類后同一類的數據盡可能聚集到一起，不同類數據盡量分離。

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

聚類分析法是理想的多變量統計技術，主要有分層聚類法和迭代聚類法。 聚類分析也稱群分析、點群分析，是研究分類的一種多元統計方法。

例如，我們可以根據各個銀行網點的儲蓄量、人力資源狀況、營業面積、特色功能、網點級別、所處功能區域等因素情況，將網點分為幾個等級，再比較各銀行之間不同等級網點數量對比狀況。

聚類算法的分類

目前，有大量的聚類算法。而對于具體應用，聚類算法的選擇取決于數據的類型、聚類的目的。如果聚類分析被用作描述或探查的工具，可以對同樣的數據嘗試多種算法，以發現數據可能揭示的結果。

主要的聚類算法可以劃分為如下幾類：劃分方法、層次方法、基于密度的方法、基于網格的方法以及基于模型的方法。

目前，聚類問題的研究不僅僅局限于上述的硬聚類，即每一個數據只能被歸為一類，模糊聚類［10］也是聚類分析中研究較為廣泛的一個分支。模糊聚類通過隸屬函數來確定每個數據隸屬于各個簇的程度，而不是將一個數據對象硬性地歸類到某一簇中。目前已有很多關于模糊聚類的算法被提出，如著名的FCM算法等，此方法后面會提及。

常用的聚類方法

1.k-mean聚類分析 適用于樣本聚類；

2.分層聚類 適用于對變量聚類；

3.兩步聚類 適用于分類變量和連續變量聚類；

4.基于密度的聚類算法；

5.基于網絡的聚類；

6.機器學習中的聚類算法；

前3種，可用spss簡單操作實現；

四種常用聚類算法研究

k-means聚類算法

k-means是劃分方法中較經典的聚類算法之一。由于該算法的效率高，所以在對大規模數據進行聚類時被廣泛應用。目前，許多算法均圍繞著該算法進行擴展和改進。

k-means算法目標是，以k為參數，把n個對象分成k個簇，使簇內具有較高的相似度，而簇間的相似度較低。

k-means算法的處理過程如下：首先，隨機地 選擇k個對象，每個對象初始地代表了一個簇的平均值或中心;對剩余的每個對象，根據其與各簇中心的距離，將它賦給最近的簇;然后重新計算每個簇的平均值。 這個過程不斷重復，直到準則函數收斂。通常，采用平方誤差準則，其定義如下：

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

輸入：包含n個對象的數據庫和簇的數目k；

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

步驟：

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

（2） repeat；

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

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

（5） until不再發生變化。

總結：

優點：簡單直接（體現在邏輯思路以及實現難度上），易于理解，在低維數據集上有不錯的效果（簡單的算法不見得就不能得到優秀的效果）。

缺點：對于高維數據（如成百上千維，現實中還不止這么多），其計算速度十分慢，主要是慢在計算距離上（參考歐幾里得距離，當然并行化處理是可以的，這是算法實現層面的問題），它的另外一個缺點就是它需要我們設定希望得到的聚類數k，若我們對于數據沒有很好的理解，那么設置k值就成了一種估計性的工作。

層次聚類算法

根據層次分解的順序是自底向上的還是自上向下的，層次聚類算法分為凝聚的層次聚類算法和分裂的層次聚類算法。

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

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

（1） 將每個對象看作一類，計算兩兩之間的最小距離；

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

（3） 重新計算新類與所有類之間的距離；

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

總結：

優點：

1，距離和規則的相似度容易定義，限制少；

2，不需要預先制定聚類數；

3，可以發現類的層次關系（在一些特定領域如生物有很大作用）；

缺點：

1，計算復雜度太高（考慮并行化）；

2，奇異值也能產生很大影響；

3，算法很可能聚類成鏈狀（一層包含著一層）；

4，算法不需要預定聚類數，但是我們選擇哪個層次的聚類作為我們需要的聚類效果，這需要我們按照實際客觀情況以及經驗來完成，畢竟就凝聚聚類來說，從最底層的每個個體作為一個個體，到最頂層所有個體合并為一個個體，其中的聚類結果可能有許許多多種。

當然針對這個問題也有許多解決方案，其中一個常用的就是凝聚到某個程度其聚類之間的距離都大于某個閾值k，就停止凝聚。

SOM聚類算法

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

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

算法流程：

（1） 網絡初始化，對輸出層每個節點權重賦初值；

（2） 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；

（3） 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；

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

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

FCM聚類算法

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

FCM算法是一種以隸屬度來確定每個數據點屬于某個聚類程度的算法。該聚類算法是傳統硬聚類算法的一種改進。

算法流程：

（1） 標準化數據矩陣；

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

（3） 算法開始迭代，直到目標函數收斂到極小值；

（4） 根據迭代結果，由最后的隸屬矩陣確定數據所屬的類，顯示最后的聚類結果。

總結：

優點：相比起前面的”硬聚類“，FCM方法會計算每個樣本對所有類的隸屬度，這給了我們一個參考該樣本分類結果可靠性的計算方法，我們可以這樣想，若某樣本對某類的隸屬度在所有類的隸屬度中具有絕對優勢，則該樣本分到這個類是一個十分保險的做法，反之若該樣本在所有類的隸屬度相對平均，則我們需要其他輔助手段來進行分類。

缺點：KNN的缺點基本它都有。

四種聚類算法試驗

試驗數據

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

試驗結果說明

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

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

（1）聚錯樣本數：總的聚錯的樣本數，即各類中聚錯的樣本數的和；

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

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

試驗結果分析

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