本文介紹了聚類演算法，內容包括K-means、Fuzzy C-means、 Hierarchical 、Mixture of Gaussians 。

原文鏈接：聚類演算法入門教程

感謝社區用戶Vivian對本文的貢獻！

目錄

  • 1.聚類簡介
    • 1.1聚類的目標
    • 1.2應用
    • 1.3要求
    • 1.4難點
  • 2.聚類演算法
    • 2.1演算法分類
    • 2.2距離度量
    • 2.3閔科夫斯基度規
  • 3.K-Means
    • 3.1演算法
    • 3.2示例
    • 3.3注意
  • 4.Fuzzy C-Means
    • 4.1演算法
    • 4.2示例
  • 5.層次聚類演算法
    • 5.1原理
    • 5.2Single—Linkage
      • 5.2.1演算法
      • 5.2.2示例
      • 5.2.3問題
  • 6.混合高斯模型聚類
    • 6.1基於模型的集群
    • 6.2混合高斯模型
    • 6.3EM演算法

1. 聚類簡介

聚類是什麼? 聚類是一種涉及數據點分組的機器學習技術。

給定一組數據點，我們可以使用聚類演算法將每個數據點分類到特定的組中。理論上，同一組中的數據點應具有相似的屬性或特徵，而不同組中的數據點應具有較大差異的屬性或特徵。

聚類是無監督學習的一種方法，也是用於許多領域中統計數據分析的常用技術。 我們可以用一個簡單的圖形例子來說明:

在上圖中，我們很容易看出可以將數據劃分為4個Cluster（簇）。

相似性的標準是距離:如果兩個或多個物體根據給定的距離(在本例中是幾何距離)「接近」，則它們屬於同一簇。這稱為基於距離的聚類。

另一種聚類是概念聚類:兩個或多個對象屬於同一個簇，如果這個簇定義了所有這些對象共有的概念。換句話說，對象是根據它們對描述性概念的適合程度來分組的，而不是根據簡單的相似性度量。

1.1 聚類的目標

聚類的目標是確定一組未標記數據中的固有分組。但是如何決定什麼構成一個好的簇呢?可以看出，並沒有絕對的「最佳」標準，它獨立於聚類的最終目標。因此，用戶必須提供這個標準，以便聚類的結果能夠滿足他們的需要。

1.2 應用

聚類演算法可以應用於很多領域，例如:

  • 市場營銷:給定一個包含客戶屬性和以往購買記錄的大型客戶數據資料庫，尋找行為相似的客戶群
  • 生物學:根據植物和動物的特徵進行分類
  • 圖書館:圖書訂購
  • 保險:確定平均理賠費用較高的汽車保單持有人群體，識別欺詐行為
  • 城市規劃:根據房屋類型、價值和地理位置，對房屋進行分類
  • 地震研究:聚類觀測震源，識別危險區域
  • WWW:文檔分類，對weblog數據進行聚類，以發現具有類似訪問模式的組。

1.3 要求

聚類演算法需要滿足的主要要求是:

  • 可伸縮性
  • 處理不同類型的數據
  • 發現任意形狀的簇
  • 領域最小化
  • 處理噪音和異常值的能力
  • 對輸入數據的順序不敏感
  • 高維度
  • 可解釋性和可用性

1.4 難點

  • 當前的聚類技術不能充分(同時)滿足所有需求
  • 由於時間的複雜性，處理大量維度和大量數據項可能是有問題的
  • 該方法的有效性取決於「距離」的定義(基於距離的聚類)
  • 如果一個明顯的距離度量不存在，我們必須「定義」它，這並不總是容易的，尤其是在多維空間中
  • 聚類演算法的結果(在許多情況下，聚類演算法本身可以是任意的)可以用不同的方式解釋

2. 聚類演算法

所謂聚類問題，就是給定一個元素集合D，其中每個元素具有n個可觀察屬性，使用某種演算法將D劃分成k個子集，要求每個子集內部的元素之間相異度儘可能低，而不同子集的元素相異度儘可能高。其中每個子集叫做一個簇。

2.1 演算法分類

聚類演算法可以分為以下幾種:

  • Exclusive Clustering
  • Overlapping Clustering
  • Hierarchical Clustering
  • Probabilistic Clustering

1.在第一種情況下，數據以排他性的方式分組，因此，如果某個數據屬於某個簇，那麼它就不能包含在另一個簇中。一個簡單的例子如下圖所示，點的分離是通過二維平面上的一條直線實現的。

2.與此相反，Overlapping Clustering採用模糊集合（fuzzy sets）對數據進行聚類，使每個點可以同時屬於多個群組。當然，這個點與每一個群組的耦合程度是不同的，有的緊密一點，有的疏鬆一點，但都屬於閾值範圍內的。

3.Hierarchical Clustering演算法是基於兩個最近的簇之間的並集。先把每個點都看作一個簇，然後再把最近的兩個簇聚合成為一個新的簇，如此這般，不斷迭代，直到滿足最後設定的要求。

4.Probabilistic Clustering使用完全概率的方法。

在本教程中，我們提出了四種最常用的聚類演算法:

  • k-means
  • Fuzzy C-means
  • 分層聚類
  • 混合高斯模型

這些演算法都屬於上面列出的一種聚類類型。因此，k均值是Exclusive Clustering演算法，模糊c均值是Overlapping Clustering演算法，層次聚類屬於Hierarchical Clustering演算法，高斯混合模型屬於Probabilistic Clustering演算法。我們將在下文中討論每一種聚類方法。

2.2 距離度量

聚類演算法的一個重要內容是數據點之間的距離度量。 如果數據實例向量都在相同的物理單元中，那麼簡單的歐式距離度量就有可能足以成功地對相似的數據實例進行分組。然而，即使在這種情況下，歐式距離有時也會產生誤導。

在下圖中，左圖height刻度每單位0.25，與縱坐標相同，看起來分成上下兩組剛剛好。然而，如果通過重新調整坐標，將橫坐標做拉伸處理，將每單位定義成0.125，肉眼看起來分成左右兩組才更合適了。在左右兩種聚類方式中，點的坐標沒有變，唯一改變的就是橫坐標比例。而就因為如此，分組方式完全變了。

聚類聚得「好不好」，通常無法用絕對值來衡量，主要還是看你的目標是什麼，也就是為何聚類。 同樣，我們需要藉助相關領域的知識來指導如何為每個特定應用制定適當的距離度量。

2.3 閔可夫斯基度規

對於高維數據，最常用的測量方法是閔可夫斯基度規：

d_p(x_i,x_j) = (sum_{K=1}^d |x_{i,k}-x_{j,k}|^p)^frac{1}{p} 其中d為數據的維數。歐式距離是p=2的特殊情況，曼哈頓度規是p=1。

然而，對於為指定的應用選擇度量標準並沒有通用的理論。 通常情況下，數據特徵向量的組成部分不能直接進行比較。它可能不是連續變數(如長度)，而是名義類別(如星期幾)。

在這些情況下，必須再次憑藉相關領域的知識來制定適當的度量。

3. K-Means

3.1 演算法

K-means (MacQueen, 1967)是最簡單的非監督學習演算法之一，解決了眾所周知的聚類問題。該過程遵循一種簡單易行的方法，通過一定數量的簇(假設k個簇)對給定的數據集進行分類。

K-Means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。

該演算法的目標是最小化目標函數，在本例中是平方誤差函數。 目標函數：

J=sum_{j=1}^ksum_{i=1}^n||x_i^{(j)}-c_j||^2 式中 ||x_i^{(j)}-c_j||^2 為數據點 x_i^{(j)} 與聚類中心 c_j 之間選擇的距離度量，為 n 個數據點與各自聚類中心之間距離的指示器。

演算法由以下步驟組成:

  • 將K個點放入由聚集的對象表示的空間中。這些點表示初始群心。
  • 將每個對象分配給最接近質心所在的簇。
  • 分配完所有對象後，重新計算K個質心的位置。
  • 重複步驟2和3，直到重心不再移動。這產生了將對象分成組的簇，從中可以計算要最小化的度量。

雖然可以證明過程總是可以終止的，但是k-means演算法不一定能找到最優的配置，對應的是全局目標函數的最小值。 該演算法對初始隨機選擇的聚類中心也具有顯著的敏感性。k-means演算法可以多次運行以減少這種影響。 K-means是一種簡單的演算法，適用於許多問題領域。正如我們將要看到的，它非常適合處理模糊特徵向量。

3.2 示例

假設我們有n個樣本特徵向量 x_1,x_2...x_n 都來自同一個類，我們知道它們屬於 k 個緊簇， k<n ，設 m_i 為簇 i 中向量的均值，如果簇之間的距離很好，我們可以使用最小距離分類器將它們分離。也就是說，如果 ||x?m_i|| 是所有 k 個距離的最小值，我們可以說 x 在簇 i 中。求 k 的方法如下:

  • 對平均值 m_1,m_2,...,m_n 進行初步猜測
  • until 均值沒有變化
    • 利用估計的方法對樣本進行聚類
    • for i from 1 to k
      • 將 m_i 替換為集群 i 中所有樣本的均值
      • end_for
    • end_until

下面是一個例子，說明均值 m_1 和 m_2 如何移動到兩個集群的中心。

3.3 注意

這是k-means程序的一個簡單版本。它可以看作是一種貪婪演算法，將n個樣本劃分為k個簇，從而最小化到簇中心距離的平方和。它確實有一些缺點:

  • 沒有指定初始化方法。一種常用的開始方法是隨機選擇k個樣本值。
  • 產生的結果依賴於平均值的初值，並且經常會發現分區不是最優的。標準的解決方案是嘗試許多不同的起點。
  • 可能是最接近mi的樣本集為空，導致mi無法更新。這是一個必須在實現中處理的問題，但是我們應該忽略它。
  • 結果取決於用來測量||x?mi||的度規。一個流行的解決方案是通過每個變數的標準差來標準化，儘管這並不總是可取的。
  • 結果取決於k的值。

最後一個問題特別麻煩，因為我們通常無法知道存在多少個簇。在上面的例子中，相同的演算法應用於相同的數據，會產生以下3種聚類方法。它比2均值聚類更好還是更差呢？

不幸的是，對於任何給定的數據集，沒有找到最優的簇的數量的一般理論解決方案。一種簡單的方法是用不同的k類比較多個運行的結果，並根據給定的標準選擇最佳的一個。但是我們需要小心，因為根據定義，增加k會導致更小的誤差函數值，但也會增加過擬合的風險。

4. Fuzzy C-Means

4.1 演算法

Fuzzy C-Means (FCM)是一種聚類方法，它允許一段數據屬於兩個或更多的聚類。這種方法(Dunn在1973年開發，Bezdek在1981年改進)經常用於模式識別。它基於以下目標函數的最小化:

J_m=sum_{i=1}^Nsum_{j=1}^C u_{ij}^m ||x_i-c_j||^2 , 0leq m<infty

m是任何大於1的實數， u_{ij} 是 x_i 在集群 j 中的隸屬度, x_i 是第 i 個d維測量數據, c_j 是簇的d維中心, ||?|| 是表示任意測量數據與中心相似度的任意範數。

對上述目標函數進行迭代優化，對隸屬度 u_{ij} 和聚類中心 c_j 進行更新，進行模糊劃分:

u_{ij}=frac{1}{sum_{k=1}^c lgroupfrac{||x_i-x_j||}{||x_i-c_k|| group}^ frac{2}{m-1}}

C_j=frac{sum_{i=1}^N u_{ij}^m x_i}{sum_{i=1}^Nu_{ij}^m}

迭代將在 max_{ij}lgroup|u_{ij}^{(k+1)}-u_{ij}^k| group<varepsilon 時停止， ε 為0 ~ 1之間的終止準則，而 k 是迭代步驟。這個過程收斂到 J_m 的局部極小值或鞍點。 演算法由以下步驟組成:

如前所述，數據通過隸屬函數綁定到每個簇，該隸屬函數表示該演算法的模糊行為。要做到這一點，我們只需構建一個名為U的適當矩陣，它的因數是0到1之間的數字，並表示數據和簇中心之間的隸屬度。

為了更好地理解，我們可以參考一個簡單的一維示例。 給定一個數據集，假設將其表示為分布在軸上。如下圖所示:

看這幅圖，我們可以在兩個數據集中附近找到兩個簇。我們將用「A」和「B」來指代它們。在本教程中展示的第一種方法k-means演算法—中，我們將每個數據關聯到一個特定的質心;因此，這個隸屬度函數是這樣的:

相反，在FCM方法中，相同的給定數據並不完全屬於定義良好的簇，但是可以將其放在中間位置。在這種情況下，隸屬度函數沿著一條更平滑的線表示每個數據可能屬於幾個具有不同隸屬度係數值的簇。

在上圖中，以紅色標記的點表示的數據更多的屬於B簇，而不是A簇。值「m」=0.2表示該數據到A的隸屬度。現在，我們不使用圖形表示，我們引入一個矩陣U，其因子是從隸屬函數中提取的:

行和列的數量取決於我們正在考慮的數據和簇的數量。更準確地說，我們有C = 2列(C = 2個簇)和N行，其中C是簇的總數，N是數據的總數。通用元素是這樣表示的:uij。 在上面的例子中，我們考慮了k均值(a)和FCM (b)的情況。我們可以注意到在第一種情況下(a)係數總是單一的。這樣做是為了表明每個數據只能屬於一個簇。其他屬性如下所示：

4.2 示例

在這裡，我們考慮FCM的一維應用程序的簡單情況。20個數據和3個簇用於初始化演算法和計算U矩陣。下圖(取自我們的互動式演示)顯示了每個數據和每個簇的成員資格值。根據隸屬度函數，數據的顏色是最近的簇的顏色。

在上圖所示的模擬中，我們使用了一個模糊係數 m = 2 ，並且當 max_{ij}lgroup{|u_{ij}^{(k+1)}-u_{ij}^k| group}<0.3 時強制終止演算法。圖中顯示了模糊分布依賴於聚類特定位置的初始條件。還沒有執行任何步驟，因此不能很好地標識簇。現在我們可以運行該演算法，直到停止條件得到驗證。下表為第8步得到的最終條件， m=2， ε=0.3 :

有可能做得更好嗎?當然，我們可以使用更高的精度，但我們也必須投入更大的計算量。在下一個圖中，我們可以看到使用相同的初始條件和 ε=0.01 得到了更好的結果，但是我們需要37個步驟!

同樣需要注意的是，不同的初始化會導致演算法的不同演進。事實上，它可以收斂到相同的結果，但可能需要不同數量的迭代步驟。

5. 層次聚類演算法

5.1 原理

給定一組要聚類的N個項，以及一個N*N的距離(或相似性)矩陣，層次聚類的基本過程(1967年S.C. Johnson定義)為:

  1. 首先將每個項分配給一個簇，這樣，如果有N個項，那麼現在就有N個簇，每個簇只包含一個項。讓簇之間的距離(相似性)與其包含的項之間的距離(相似性)相同。
  2. 找到最接近(最相似)的一對簇，並將它們合併到單個簇中，這樣可以減少一個簇。
  3. 計算新簇與每箇舊簇之間的距離(相似性)。
  4. 重複步驟2和步驟3，直到所有項都聚集到一個大小為n(*)的簇中。

步驟3可以通過不同的方式來完成，這就是單連鎖（single-linkage）與完全連鎖（complete-linkage）和平均連鎖（average-linkage）聚類的區別所在。

  • 在single-linkage聚類(也稱為連通性或最小值法)中，我們認為一個聚類與另一個聚類之間的距離等於從一個聚類中的任何成員到另一個聚類中的任何成員的最短距離。如果數據包含相似性，我們認為一個簇與另一個簇之間的相似性等於一個簇的任何成員與另一個簇的任何成員之間的最大相似性。
  • 在complete-linkage聚類(也稱為直徑或最大值法)中，我們認為一個聚類與另一個聚類之間的距離等於一個聚類中的任何成員與另一個聚類中的任何成員之間的最大距離。
  • 在average-linkage聚類中，我們認為一個聚類與另一個聚類之間的距離等於從一個聚類中的任何成員到另一個聚類中的任何成員的平均距離。

average-linkage聚類的一種變化是R.DAndrade（1978）的UCLUS方法，它使用中值距離，它比平均距離更具異常性。

這種層次聚類被稱為聚合聚類，因為它是迭代地合併簇。還有一種分裂的層次聚類，它從一個簇中的所有對象開始，並將它們細分為更小的部分，從而實現相反的效果。分裂的方法一般是不可用的，也很少得到應用。

當然，將所有N個項目分組在一個簇中是沒有意義的，但是，一旦你獲得了完整的層次樹，如果想要k個簇，只需刪除k-1最長的鏈接。

5.2 Single-Linkage

5.2.1 演算法

現在讓我們更深入地看看Johnson演算法在Single-Linkage聚類情況下是如何工作的。

該演算法是一種新的聚類演算法，當舊的聚類被合併到新的聚類中時，該演算法將消除鄰近矩陣中的行和列。

N*N鄰近矩陣 D=[D(i,j)] 。聚類的序列編號為 0,1，……， (n-1) 和 L(k) 為第 k 個聚類層次。序號為 m 的簇記為 (m) ，簇 (r) 與簇 (s) 的鄰近度記為 d[(r),(s)] 。 演算法由以下步驟組成:

1、首先以級別 L(0)=0 的不相交聚類開始。

2、根據 d[(r),(s)]=mind[(i),(j)] ，找出當前聚類中最不相似的對，即對 (r),(s) 。其中最小值為當前簇中的所有對簇。 3、增加序號: m = m +1 。將聚類 (r) 和 (s) 合併到單個聚類中，形成下一個聚類 m 。將該聚類的級別設置為 L(m)=d[(r),(s)] 4、更新鄰近矩陣 D ，刪除與簇 (r) 和 (s) 對應的行和列，並添加與新形成的簇對應的行和列。新簇 (r,s) 與舊簇 (k) 的鄰近度定義如下: d[(k), (r,s)] = min d[(k),(r)], d[(k),(s)] 5、如果所有對象都在一個簇中，則停止。否則，轉到步驟2。

5.2.2 示例

現在讓我們看一個簡單的例子:一些義大利城市之間以公里為單位的距離的層次聚類。使用的方法是Single-Linkage 。 輸入距離矩陣 (L = 0) :

最近的兩個城市是MI和TO，距離138。它們被合併到一個名為「MI/TO」的簇中。新簇的級別為L(MI/TO) = 138，新序列號為m = 1。

然後我們計算這個新的複合對象到所有其他對象的距離。在單鏈路聚類中，規則是複合對象到另一個對象的距離等於從簇中的任何成員到外部對象的最短距離。因此，從MI/到RM的距離被選擇為564，也就是從MI到RM的距離，以此類推。

將MI與合併後得到如下矩陣:

min d(i,j) = d(NA,RM) = 219 =>將NA和RM合併成一個新的簇NA/RM L(NA/RM) = 219 m = 2

min d(i,j) = d(BA,NA/RM) = 255 =>將BA和NA/RM合併到一個名為BA/NA/RM的新簇中 L(BA/NA/RM) = 255 m = 3

min d(i,j) = d(BA/NA/RM,FI) = 268 =>將BA/NA/RM與FI合併成一個新的簇BA/FI/NA/RM L(BA/FI/NA/RM) = 268 m = 4

最後，我們在295級合併最後兩個簇。 該過程總結為以下層次樹:

5.2.3 問題

聚類方法的主要缺點是:

  • 它們不能很好地伸縮:時間複雜度至少為O(n2)，其中n為總對象數;
  • 不能撤銷以前做過的事情。

6. 混合高斯模型聚類

6.1 基於模型的簇

還有另一種處理聚類問題的方法:基於模型的方法，其中包括使用某些模型進行聚類並嘗試優化數據和模型之間的擬合。 在實踐中，每個聚類可以通過參數分布在數學上表示，如高斯（連續）或泊松（離散）。因此，整個數據集由這些分布的混合物建模。用於對特定簇建模的單個分布通常稱為組件分布。

具有高可能性的混合模型傾向於具有以下特徵：

  • 組件分布有很高的「峰值」(一個集群中的數據很「緊」);
  • 混合模型很好地「覆蓋」了數據(數據中的主導模式由組件分布捕獲)。

基於模型聚類的主要優點:

  • 已有的統計推斷技術;
  • 組件分布選擇的靈活性;
  • 得到每個簇的密度估計;
  • 「軟」分類是可用的。

6.2 混合高斯模型

這類聚類方法中應用最廣泛的是一種基於高斯混合學習的聚類方法:我們實際上可以把聚類看作是以其質心為中心的高斯分布，如圖所示，其中灰色圓圈表示分布的第一個方差:

演算法是這樣工作的:

  • 它隨機選擇概率為 p(omega_i) 的分量(高斯);
  • 它抽樣一個點 N(mu_i,sigma^2) 。

我們假設有:

  • x_1,x_2,…,x_N
  • p(omega_1),...,p(omega_k),sigma

我們可以得到樣本的概率: P(x|omega_i,mu_1,mu_2,...,mu_k) 我們真正想要的是最大化是 P(x|mu_1,mu_2,...,mu_k) (給定高斯中心的基準概率)

P(x|mu_i)=sum_i P(x|omega_i,mu_1,mu_2,...,mu_k) 以此為基礎寫出似然函數： P(data|mu_i)=prod_{i=1}^N sum_i P(w_i)P(x|omega_i,mu_1,mu_2,...,mu_k) 現在我們應該通過計算 frac{partial L}{partial u_i}=0 來最大化似然函數,但這太困難了。這就是為什麼我們使用簡化演算法EM(期望最大化)。

6.3 EM演算法

在實際應用中，用來尋找對數據集建模的高斯混合的演算法稱為EM (expectzation, Dempster, Laird and Rubin, 1977)。讓我們看一個例子。 假設xk是某門課的學生得到的分數，其概率為:

x_1=30quad P(x_1)=frac{1}{2}

x_2=18quad P(x_2)=mu

x_3= 0quad P(x_3)=2mu

x_4=23quad P(x_4)=frac{1}{2}-3mu

第一個案例:我們觀察到分數在學生中分布得如此之廣:

x_1 : a quad students

x_2 : bquad students

x_3 : c quad students

x_4 : dquad students

通過計算 frac{partial L}{partial u_i}=0 使這個函數最大化。我們來計算函數的對數，並使其最大化:

假設a = 14, b = 6, c = 9, d = 10，我們可以計算出μ=110。

第二種情況:我們觀察到分數在學生中是如此的分散:

x_1+x_2 : h quad students

x_3 : c quad students

x_4 : dquad students

這樣我們就得到了一個循環，它分為兩個步驟:

  • 期望值： mu ightarrow a=frac{frac{1}{2}}{frac{1}{2}+mu}h,b=frac{mu}{frac{1}{2}+mu}h
  • 極大值： a,b ightarrow mu=frac{b+c}{6(b+c+d)}

這種循環性可以用迭代的方法求解。

現在我們來看看EM演算法是如何適用於混合高斯函數的（在第p次迭代中估計的參數用上標(p)標記）：

1、參數初值：

2、求期望：

3、求最大值：

其中R是記錄的個數。

  • 參考： home.deib.polimi.it/mat
推薦閱讀：
相关文章