什麼是叢集分析？

叢集分析是一種資料分析技術，它在稱為叢集的資料集中探索自然發生的群組。叢集分析不需要將資料點分組到任何預先定義的群組中，這意味著它是一種非監管型學習方法。在非監管型學習中，洞察力源自於沒有任何預先定義標籤或類別的資料。一個好的分群演算法應能確保叢集內的相似度夠高，而叢集之間的相似度卻很低。

資料分群問題的一個範例

根據銷售額對零售店進行分組是叢集分析的一個簡單使用案例。假設一家咖啡館在城市中有八家分店，下表顯示每天卡布奇諾和冰咖啡的銷售量。

下圖顯示相同的資料，其中每家門市的卡布奇諾和冰咖啡銷售量分別繪製在 X 軸和 Y 軸上。在此案例中，由於資料點有限，因此很容易在圖表上繪製兩個自然出現的咖啡店叢集，並手動將它們視覺化。

然而，當涉及到數千個資料點時，就需要使用叢集分析演算法將資料點分離到不同的叢集中。

叢集分析有哪些應用？

叢集分析的主要使用方式通常有兩種：

• 做為獨立工具來解決關於資料分組的問題。
• 做為各種機器學習演算法的預處理步驟。

做為獨立工具的叢集分析

• 行銷：在行銷領域，叢集分析可用於根據客戶的購買模式或興趣而將客戶分為不同的族群，這些被稱為客戶角色。然後，組織可以針對不同的客戶群使用不同的行銷策略。
• 金融風險分析：金融組織使用各種叢集分析演算法，根據客戶的銀行餘額和債務將其劃分為不同的風險類別。在核准貸款、保險或信用卡時，這些叢集用於輔助決策。
• 房地產：基礎設施專家使用叢集技術，根據房屋的大小、位置和市場價值對房屋進行分組，此資訊用於評估城市不同地區的房地產潛力。

叢集分析做為機器學習的預處理步驟

叢集分析通常當做各種機器學習演算法的預處理步驟。

分類演算法會對廣泛的資料集進行叢集分析，以篩選掉可歸屬於明顯群組的資料，然後針對數量已減少、並非顯而易見的資料點使用進階資料分類技術。隨著資料集越變越更小，計算時間將大大減少。也可以反向使用相同的方法，亦即使用叢集分析演算法來篩選掉雜訊或離群資料。

在執行監督型學習演算法之前，可能需要先對輸入的資料進行叢集分析，以找出資料中的自然叢集。

主要的叢集分析演算法有哪些？

叢集分析演算法通常屬於以下幾類：

• 基於分區的演算法
• 階層式演算法
• 基於密度的演算法
• 基於網格的演算法
• 基於模型的演算法
• 基於限制條件的演算法
• 離群值分析演算法

每種演算法本身都很複雜，可能適用於某些分析而不適用於其他分析。

基於分區的叢集分析演算法

在這種方法中，演算法從幾個初始叢集開始，然後迭代地將資料點重新定位到不同的叢集，直到實現最佳分區為止。K 均值 (K-means) 分群演算法就是最流行的分群演算法之一。

下面的 K 均值分群案例顯示它的工作原理。

第 1 步：決定叢集數量

決定叢集數量，即演算法的「K」，例如，K=3，則演算法會將上述十二個資料點劃分為 3 個叢集。數字 K 可以是任意值，而取決於此，叢集的正確性可能會有所不同。還有一些演算法方法可用於找出 K 的最佳值。

第 2 步：選擇資料點

當K=3，取任意三個資料點做為初始均值。在此案例中，選擇 C、D 和 E 點做為初始均值。請注意，K 均值演算法可以將任意點做為初始均值。

第 3 步：計算距離

計算資料集中每個點到每個初始叢集均值的距離。例如本例已隨機選擇三個叢集均值 C、D 和 E，則針對樣本中的其餘每個資料點，計算它們與這三個均值的距離。兩點 (X1, Y1) 和 (X2, Y2) 之間的阿基米德距離計算公式如下：

在第 3 步之後，表格將顯示每個資料點與初始均值 C、D 和 E 的距離。

資料點會根據其最小距離被新增到相關叢集中。例如，點 A 與初始均值 C 的距離最小，這意味著 A 將被分組到均值為 C 的叢集中。經過這一步，就能得到叢集了。

第 4 步：重複，計算新的均值

現在很容易看到初始叢集。下一步是計算三個新的叢集均值，為此，需要將特定叢集中的每個資料點合併算出平均值。

「C」叢集的新叢集平均值 = (5+2+6+1+4+3+6/7, 21+11+22+10+23+14+12/7) = (3.85, 16.14)，我們稱這個點為 X。

「D」叢集的新叢集平均值 = (1+2+5/3, 6+8+4/3) = (2.66, 6)，我們稱這個點為 Y。

「E」叢集的新叢集平均值 = (4+5/2, 10+11/2) = (4.5, 10.5)，我們稱這個點為 Z。

第 5 步：重複，計算每個資料點與新均值的距離

重複第 3 步，找出所有資料點與新算出的叢集均值 X、Y 和 Z 的距離。在這次新的迭代中，很容易看出資料點 C、D、I 和 L 的最小距離改變了，它們現在屬於一個新的叢集，如下所示。

然後，K 均值迭代需要繼續執行下去，因為一些資料點已經改變了它們的叢集。

第 6 步：重複，計算新均值和新叢集

由於資料點 C、D、I、L 已經改變了它們的叢集，因此需要像第 4 步那樣再次計算新的叢集均值。為此，將特定叢集中的每個資料點合併算出平均值，然後像第 5 步那樣，計算每個資料點到新叢集均值的距離，再根據距離，將資料點分配給與它距離最小的叢集。

K 均值演算法到什麼時候結束？

K 均值是一種迭代分區演算法：

• 先決定一開始的叢集數量（K），在上面例子中，K=3。
• 隨機分配 K 個資料點做為初始叢集均值。
• 重複後續步驟，直到沒有資料點更改其叢集為止。
• 計算從資料點到叢集平均值的平均距離。
• 將資料點分配給距離最短的叢集。
• 檢查是否有任何資料點更改了其叢集。

在新的迭代中，如果每個資料點都保留在先前的叢集中，則 K 均值演算法終止，這意味著已經獲得局部最佳解。

基於 K 中間值分區的分群演算法

K 中間值 (K-medoids) 演算法是另一種基於分區的分群演算法，K 中間值演算法選擇中間值做為叢集的代表對象。K 中間值演算法試圖找到特定叢集中與每個其他資料點均差異最小的資料點，然後在差異最小化之前，K 中間值演算法將迭代地劃分資料集。 K 均值演算法經常使用平方誤差距離（阿基米德距離），而 K 中間值演算法則經常使用像曼哈頓距離這樣的絕對值距離，來衡量兩個資料點之間的相異性。

K 中間值演算法的標準做法之一是「圍繞中心點分區」(Partition Around Medoids，PAM) 演算法，以下是 PAM 演算法的基本步驟。

1. 選擇一個 K 值，K 是資料點將被劃分成的叢集數。
2. 隨機選擇 K 個資料點做為中心點。
3. 針對資料集中的每個資料點 (Xi, Yi)，測量該點與上述選定的中心點之間的差異。一個常用的差異性衡量為曼哈頓距離：
   • |Xi – Ci| + | Yi - Cj|，其中 (Ci, Cj) 表示中心點。
4. 每個資料點 (Xi, Yi) 都被分配到差異最小的叢集中。
5. 針對上述每個叢集，計算總成本，即該叢集中每個資料點的差異之和。
6. 接著，隨機選擇一個非中心點做為新的中心點，並重複步驟 3-5。
7. 當叢集不再變化時即可停止。

K 均值和 K 中間值演算法的比較

儘管 K 均值演算法很簡單，但如果資料中存在大量雜訊和離群值，它就難以產生好的結果。在這種情況下，K 中間值方法會更加穩健，然而像 PAM 這樣的 K 中間值演算法，僅在資料集較小時才好用，當資料集大小增加時，K 中間值演算法的計算時間將呈指數增長。

分裂演算法

顧名思義，分裂演算法是在開始時先將所有資料點分配到單一叢集中，再將叢集劃分為最不相似的叢集，然後此演算法會遞迴地劃分這些叢集，直到獲得最佳解為止。分裂演算法也稱為自上而下的分群方法。

凝聚演算法

這類演算法會先將每個資料點分配給不同的叢集，然後，此演算法將遞迴地加入最相似的叢集，直到獲得最佳解為止。凝聚演算法也稱為自下而上的分群方法。

凝聚分群演算法案例

下面是五個資料點的距離矩陣，可以根據阿基米德距離、曼哈頓距離、或任何其他距離公式，來計算出點與點之間的距離。距離矩陣始終是一個對稱矩陣，因為點 X 和 Y 之間的距離與 Y 和 X 之間的距離相同。基於此距離矩陣，我們來舉例說明凝聚（自下而上）分群演算法。

步驟 1：在距離矩陣中，找到距離最小的兩個點。在上面例子中，即點 3 和 5，它們之間的距離是 2。把它們放在一個單獨的叢集中。

步驟 2：刪除點 3 和 5 並用叢集「35」取代它，然後建立一個新的距離矩陣。為此，需要計算所有資料點與叢集「35」之間的距離。有多種方法可以得出此距離。

在此案例中，我們使用以下方法來測量距離：

點 X 到叢集「35」的距離 = 最小值（距離 (X,3), 距離(X,5)）。基於此方法更新的距離矩陣為：

第 3 步：重複第 2 步，直到將所有資料點歸結為一個叢集為止，在目前案例中，它需要六次迭代。下圖顯示叢集的形成，這種表示稱為樹狀圖。在此表示中，Y 軸表示兩個資料點之間的距離。例如，點 3 和 5 之間的距離為 2。

第 4 步：將所有資料點都分群之後，如上所示，接著要決定需要保留多少個叢集。這是一個艱難的決定，因為每個階層式分群演算法最終都只會產生一個叢集。在階層式分群演算法對資料進行分區之後，有幾種方法可用於找出最佳叢集數。

基於密度的分群演算法

這些演算法是基於叢集的資料空間一律比周圍更密集的想法。基於密度的演算法從單一資料點開始，探索其附近的資料點，這個初始點附近的點被包含在單一叢集中，鄰域的定義取決於演算法想要算什麼。基於空間密度並應用雜訊分群 (Density-based spatial clustering of applications with noise，DBSCAN) 是此類別中流行的分群演算法。

基於網格的分群演算法

基於網格的分群演算法類似於基於密度的分群演算法。資料空間被分成幾個更小的單元，稱為網格，並將每個資料點分配給一個特定的網格單元。然後此演算法會計算每個網格的密度，那些密度低於閾值的網格將被淘汰，接著，此演算法會將相鄰的密集網格群組組成叢集。統計資訊網格 (STING) 和任務分群 (CLIQUE) 是兩種流行的基於網格的演算法。

除了上述演算法之外，叢集分析還包括基於模型的叢集、基於限制條件的叢集、離群值分析等一組演算法。

叢集分析演算法的優缺點

演算法	優點	缺點
基於分區的叢集分析演算法	簡單且可擴展。 適用於小巧且能妥善分離成叢集的資料集。	需要提前定義叢集的數量。 不適用於高維度資料空間。 易受雜訊和離群值的影響，不是很穩健。
階層式叢集分析演算法	無需提前定義叢集。 計算所有可能叢集的完整階層結構。 良好的視覺化方法，像樹狀圖。	對何時停止分群的看法模糊。 在高維資料空間的效果變差。 一旦完成叢集的拆分或合併，就很難糾正它。
基於密度的叢集分析演算法	探索任意形狀和大小的叢集。 更好地處理資料中的雜訊和離群值。 不需要預先指定叢集的數量。	如果資料叢集的密度會變動，則此方法可能會失敗。 輸出高度依賴初始設定的輸入參數。
基於網格的叢集分析演算法	不必計算距離。因此演算法很快。 此演算法可以處理大型資料集。	叢集邊界由水平或垂直邊界組成，不包括對角線邊界。