聚類算法：從開始到最先進

成為一名數據科學家並不是一個糟糕的時期。 如果你把話題轉向“大數據”，嚴肅的人可能會對你產生興趣，而當你提到“人工智能”和“機器學習”時，其他派對人群會很感興趣。 甚至谷歌也認為你還不錯，而且你正在變得更好。 有很多“智能”算法可以幫助數據科學家發揮作用。 這一切可能看起來很複雜，但如果我們稍微了解和組織算法，找到並應用我們需要的算法就不是那麼難了。

數據挖掘或機器學習課程通常從聚類開始，因為它既簡單又有用。 它是更廣泛的無監督學習領域的重要組成部分，我們想要描述的數據沒有被標記。 在大多數情況下，這是用戶沒有向我們提供有關預期輸出的太多信息的地方。 該算法只有數據，它應該盡其所能。 在我們的例子中，它應該執行聚類——將數據分成包含相似數據點的組（集群），而組之間的差異盡可能高。 數據點可以代表任何事物，例如我們的客戶。 例如，如果我們想要對相似的用戶進行分組，然後在每個集群上運行不同的營銷活動，集群就會很有用。

K-Means 聚類

在必要的介紹之後，數據挖掘課程總是繼續使用 K-Means； 一種有效的、廣泛使用的、全方位的聚類算法。 在實際運行它之前，我們必須定義數據點之間的距離函數（例如，如果我們想在空間中對點進行聚類，則為歐幾里得距離），並且我們必須設置我們想要的聚類數（k）。

該算法首先選擇 k 個點作為起始質心（集群的“中心”）。 我們可以選擇任意 k 個隨機點，或者我們可以使用其他方法，但選擇隨機點是一個好的開始。 然後，我們迭代地重複兩個步驟：

1. 分配步驟：我們數據集中的 m 個點中的每一個都被分配給一個由 k 個質心中最近的一個表示的集群。 對於每個點，我們計算到每個質心的距離，然後簡單地選擇距離最小的一個。

2. 更新步驟：對於每個集群，計算一個新的質心作為集群中所有點的平均值。 從上一步開始，我們有一組分配給集群的點。 現在，對於每個這樣的集合，我們計算一個平均值，我們聲明一個新的集群質心。

每次迭代後，質心都在緩慢移動，每個點到其指定質心的總距離越來越小。 這兩個步驟交替進行，直到收斂，這意味著直到集群分配不再有變化。 經過多次迭代，相同的點集將分配給每個質心，因此再次導致相同的質心。 K-Means 保證收斂到局部最優。 但是，這不一定是最佳的整體解決方案（全局最優）。

最終的聚類結果可能取決於初始質心的選擇，因此對這個問題進行了很多思考。 一個簡單的解決方案是使用隨機初始分配運行 K-Means 幾次。 然後，我們可以通過從每個點到其集群的距離總和最小的結果來選擇最佳結果——我們首先試圖最小化的誤差值。

選擇初始點的其他方法可以依賴於選擇遠點。 這可以帶來更好的結果，但我們可能會遇到異常值的問題，那些罕見的單獨點只是“關閉”，可能只是一些錯誤。 由於它們遠離任何有意義的集群，因此每個這樣的點最終都可能成為自己的“集群”。 一個很好的平衡是 K-Means++ 變體 [Arthur and Vassilvitskii, 2007]，其初始化仍然會選擇隨機點，但概率與與先前分配的質心的平方距離成正比。 距離較遠的點將更有可能被選為起始質心。 因此，如果有一組點，則從該組中選擇一個點的概率也會隨著它們的概率相加而變得更高，從而解決了我們提到的異常值問題。

K-Means++ 也是 Python 的 Scikit-learn K-Means 實現的默認初始化。 如果您使用 Python，這可能是您的首選庫。 對於 Java，Weka 庫可能是一個好的開始：

爪哇 (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (Scikit-學習)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

在上面的 Python 示例中，我們使用了標準示例數據集“鳶尾花”，其中包含三種不同鳶尾花的花瓣和萼片尺寸。 我們將這些聚類成三個聚類，並將獲得的聚類與實際物種（目標）進行比較，以查看它們完美匹配。

在這種情況下，我們知道存在三個不同的集群（物種），並且 K-Means 正確識別了哪些集群在一起。 但是，我們一般如何選擇大量的集群 k 呢？ 這類問題在機器學習中很常見。 如果我們請求更多的集群，它們會更小，因此總誤差（從點到分配的集群的距離總和）會更小。 那麼，設置更大的 k 是否是個好主意？ 我們可能以 k = m 結束，也就是說，每個點都是它自己的質心，每個簇只有一個點。 是的，總誤差為 0，但我們沒有得到更簡單的數據描述，也不足以涵蓋一些可能出現的新點。 這稱為過擬合，我們不希望這樣。

處理這個問題的一種方法是對更多的集群進行一些懲罰。 所以，我們現在不僅要盡量減少錯誤，還要盡量減少錯誤+懲罰。 隨著我們增加集群的數量，誤差只會收斂到零，但懲罰會增加。 在某些時候，添加另一個集群的收益將小於引入的懲罰，我們將獲得最佳結果。 為此目的使用貝葉斯信息準則 (BIC) 的解決方案稱為 X-Means [Pelleg and Moore, 2000]。

我們必須正確定義的另一件事是距離函數。 有時這是一項簡單的任務，考慮到數據的性質，這是一項合乎邏輯的任務。 對於空間中的點，歐幾里得距離是一個明顯的解決方案，但對於不同“單元”的特徵、離散變量等可能會很棘手。這可能需要大量的領域知識。 或者，我們可以致電機器學習尋求幫助。 我們實際上可以嘗試學習距離函數。 如果我們有一個訓練集的點，我們知道它們應該如何分組（即用它們的簇標記的點），我們可以使用監督學習技術來找到一個好的函數，然後將它應用到我們尚未聚類的目標集.

K-Means 中使用的方法具有兩個交替步驟，類似於期望最大化 (EM) 方法。 實際上，它可以被認為是一個非常簡單的 EM 版本。 然而，它不應該與更複雜的 EM 聚類算法相混淆，即使它具有一些相同的原理。

EM聚類

因此，通過 K-Means 聚類，每個點都被分配給一個單獨的聚類，並且一個聚類僅由其質心描述。 這不太靈活，因為我們可能會遇到重疊集群或非圓形集群的問題。 使用 EM 聚類，我們現在可以更進一步，通過質心（均值）、協方差（這樣我們可以擁有橢圓聚類）和權重（聚類的大小）來描述每個聚類。 點屬於集群的概率現在由多元高斯概率分佈（多元 - 取決於多個變量）給出。 這也意味著我們可以計算一個點在高斯“鐘”下的概率，即一個點屬於一個簇的概率。

我們現在通過計算每個點屬於每個當前集群的概率來開始 EM 過程（同樣，這些集群可能在開始時隨機創建）。 這是E步驟。 如果一個集群是一個非常好的候選點，它的概率將接近 1。 但是，兩個或更多集群可以是可接受的候選者，因此該點在集群上具有概率分佈。 算法的這種特性，即不屬於一個簇的點被稱為“軟聚類”。

M 步現在使用分配給前一組集群的點重新計算每個集群的參數。 為了計算聚類的新均值、協方差和權重，每個點數據按照其屬於聚類的概率加權，如上一步中計算的那樣。

交替這兩個步驟將增加總對數似然，直到它收斂。 同樣，最大值可能是局部的，因此我們可以多次運行該算法以獲得更好的集群。

如果我們現在想為每個點確定一個集群，我們可以簡單地選擇最可能的一個。 有了概率模型，我們也可以用它來生成相似的數據，也就是抽取更多與我們觀察到的數據相似的點。

親和傳播

Affinity Propagation (AP) 由 Frey 和 Dueck 於 2007 年發布，並且由於其簡單性、普遍適用性和性能而變得越來越流行。 它正在將其狀態從最先進的技術轉變為事實上的標準。

K-Means 和類似算法的主要缺點是必須選擇聚類的數量，並選擇初始點集。 相反，Affinity Propagation 將數據點對之間的相似性度量作為輸入，同時將所有數據點視為潛在的樣本。 在數據點之間交換實值消息，直到逐漸出現一組高質量的樣本和相應的集群。

作為輸入，算法要求我們提供兩組數據：

1. 數據點之間的相似性，表示一個點作為另一個樣本的適合程度。 如果兩點之間沒有相似性，因為它們不能屬於同一個簇，則可以省略這種相似性或將其設置為 -Infinity ，具體取決於實現。

2. 首選項，表示每個數據點是否適合作為示例。 我們可能有一些先驗信息，哪些點可能適合這個角色，因此我們可以通過偏好來表示它。

相似性和偏好通常通過單個矩陣表示，其中主對角線上的值代表偏好。 矩陣表示適用於密集數據集。 在點之間的連接稀疏的情況下，更實際的做法是不要將整個 nxn 矩陣存儲在內存中，而是保留與連接點的相似性列表。 在幕後，“點之間交換信息”與操縱矩陣是一回事，只是視角和實現的問題。

然後該算法運行多次迭代，直到收斂。 每次迭代都有兩個消息傳遞步驟：

1. 計算責任：責任 r(i, k) 反映了積累的證據，即 k 點作為 i 點的示例有多合適，同時考慮了 i 點的其他潛在示例。 責任從數據點 i 發送到候選樣本點 k。

2. 計算可用性：可用性 a(i, k) 反映了積累的證據，即 i 點選擇 k 點作為其樣本是多麼合適，同時考慮到其他點對 k 點應該作為樣本的支持。 可用性從候選示例點 k 發送到點 i。

為了計算責任，該算法使用在先前迭代中計算的原始相似性和可用性（最初，所有可用性都設置為零）。 責任被設置為點 i 和點 k 之間的輸入相似性作為其樣本，減去點 i 和其他候選樣本之間的相似性和可用性和中的最大值。 計算一個點對樣本的適用程度背後的邏輯是，如果最初的先驗偏好更高，則它更受青睞，但當有一個相似的點認為自己是一個很好的候選者時，責任就會降低，所以有一個 '兩者之間的競爭”，直到在某個迭代中決定一個。

然後，計算可用性使用計算的責任作為每個候選人是否會成為一個好榜樣的證據。 可用性 a(i, k) 設置為自我責任 r(k, k) 加上候選樣本 k 從其他點獲得的積極責任的總和。

最後，我們可以有不同的停止標準來終止過程，例如當值的變化低於某個閾值或達到最大迭代次數時。 在通過 Affinity Propagation 過程的任何點，將責任 (r) 和可用性 (a) 矩陣求和為我們提供了我們需要的聚類信息：對於點 i，最大 r(i, k) + a(i, k) 的 k 表示點我是榜樣。 或者，如果我們只需要一組樣本，我們可以掃描主對角線。 如果 r(i, i) + a(i, i) > 0，則點 i 是一個示例。

我們已經看到，使用 K-Means 和類似算法，確定集群的數量可能很棘手。 使用 AP，我們不必明確指定它，但如果我們獲得的集群比我們可能找到的最優值更多或更少，它可能仍需要一些調整。 幸運的是，只需調整偏好，我們就可以降低或提高集群的數量。 將偏好設置為更高的值將導致更多的集群，因為每個點都“更確定”它是否適合成為一個樣本，因此更難“擊敗”並將其包含在其他點的“支配”之下。 相反，設置較低的偏好將導致更少的集群； 好像他們在說“不，不，拜託，你是一個更好的榜樣，我會加入你的集群”。 作為一般規則，我們可以將所有偏好設置為中到大量集群的中值相似度，或者對於中等數量的集群，設置為最低相似度。 但是，可能需要進行幾次調整偏好的運行才能獲得完全符合我們需求的結果。

分層相似性傳播也值得一提，它是處理二次復雜度的算法的一種變體，它通過將數據集分成幾個子集，分別對它們進行聚類，然後執行第二級聚類。

到底…

有一系列的聚類算法，每一種算法都有各自的優缺點，包括它們使用的數據類型、時間複雜度、弱點等等。 提到更多算法，例如有層次凝聚聚類（或鏈接聚類），適用於我們不一定有圓形（或超球面）聚類，並且不知道預先知道聚類數量的情況。 它從每個點都是一個單獨的集群開始，並通過在每個步驟中加入兩個最近的集群來工作，直到所有東西都在一個大集群中。

使用分層凝聚聚類，我們可以通過在我們認為合適的地方水平切割樹狀圖（樹形圖）來輕鬆確定聚類的數量。 它也是可重複的（總是對相同的數據集給出相同的答案），但也具有更高的複雜性（二次）。

那麼，DBSCAN（Density-Based Spatial Clustering of Applications with Noise）也是一個值得一提的算法。 它將緊密堆積在一起的點分組，在附近有點的任何方向擴展簇，從而處理不同形狀的簇。

這些算法值得單獨寫一篇文章，我們可以稍後在單獨的文章中探討它們。

需要經過反複試驗才能知道何時使用一種算法或另一種算法。 幸運的是，我們有一系列不同編程語言的實現，所以嘗試它們只需要一點點玩的意願。