研究共識聚類以表示多次聚類算法的共識，並分析聚類關於採樣變異性的穩定性。

介紹

在本文中，我們將討論一種稱為共識聚類的技術，以評估聚類算法針對數據集中的小擾動生成的聚類的穩定性。我們將回顧使用Apache Spark機器學習庫構建的示例應用程序，以顯示如何使用K-means，Bisecting K-means和Gaussian Mixture（三種不同的聚類算法）可以使用共識聚類。

機器學習中的聚類分析[1]旨在根據數據點之間的相似性度量將數據劃分為單獨的，不重疊的集合。同一集群中的數據點必須儘可能相近（相似），並且不同集群中的數據點必須儘可能相距（不相似）。聚類分析在生物學，生物信息學，醫學，商業，計算機科學和社會科學等各種科學學科中有很多應用[1]。以下是一些例子。

• 聚類可用於醫學圖像的像素分類，以輔助醫學診斷[2]。
• 為了分析患者的預期壽命取決於他們屬於哪一個群，[3]，癌症患者的數據可以根據某些屬性（例如“區域節點陽性”和“階段組群”）聚類為一組。
• 癌細胞的基因表達可通過聚類技術進行分析，以分析細胞結構並預測生存[4]。

許多不同的技術和算法可用於聚類分析，其中[5]和[6]提供了極好的評論。

問題陳述

不同的聚類算法可以為相同的數據集創建不同的聚類。在不同的執行過程中，即使是相同的算法也會產生不同的簇，例如由於隨機啟動。作為一個例子，我們從美國國家癌症研究所GDC數據門戶網站下載了關於多形性成膠質細胞瘤（GBM）和低級別膠質瘤（LGG）患者的數據集，並使用K均值聚類算法將它們分成三個聚類。

結果如圖1.a，1.b所示，用於兩種不同的處理。

圖1.a. 通過K-means算法獲得的用於GBM和LGG患者的一組聚類。

圖1.b. 通過K-means算法獲得的另一組集群用於GBM和LGG患者。

在每個圖表中，有三個由黑色，深藍色和淺藍色組成的群集。橫軸表示變異分類（與患者中觀察到的TP53基因突變有關的變異等位基因的特定特徵）和腫瘤分級。縱軸表示施用於患者的化學治療次數。

請注意，集群集不一致。如果算法在不同的執行過程中為相同的數據集產生顯著不同的集群，我們可以相信該算法嗎？我們如何選擇一種算法來對群集結構感到最自信？

在本文中，我們將討論稱為共識聚類的分析技術，以表示在多次聚類算法運行中的共識，並分析發現的聚類在採樣變異性方面的穩定性[7]。

條款的組織

在下一節中，我們將討論共識聚類的基礎知識。以下部分涉及用Apache Spark MLLib機器學習庫[8]開發的樣例應用程序的代碼審查，該樣例應用程序使用三種不同的聚類算法，K均值，平分K均值和高斯混合[5] ，[6]。最後一節給出結論。

共識聚類

共識聚類基於這樣的假設：每次在稍微不同的數據集版本上執行時，可靠的聚類算法應該創建類似的聚類。換句話說，數據集上的微小擾動不應該顯著改變所得到的聚類。

為了實現共識聚類，原始數據集被隨機二次採樣m次，以創建比原始數據集略小的m個不同數據集。然後聚類算法重複m次（迭代），每個子採樣數據集一次。

接下來，對於原始數據集中的每對數據點，確定該對在該聚類算法的特定迭代中在相同聚類中出現多少次。這個想法是，如果這對數據點是“相似的”，那麼當對應於迭代的二次採樣數據集同時包含這兩個數據點時，它們理想情況下應當放置在每次迭代中的相同群集中。類似地，如果數據點是“不相似的”，則當與迭代相對應的二次採樣數據集同時包含兩者時，它們應該在每次迭代中置於不同的聚類中。

為了量化共識，構建了所謂的“共識矩陣”。讓原始數據集由N個數據點組成。然後，一致矩陣是一個對稱的N×N矩陣，其中元素（i，j）等於數據點a i和被分配到同一個簇中的j的次數除以數據點a i的次數和j一起被選中。一致矩陣的對角線元素始終為1，任何非對角元素都在0和1之間（包括0和1）。

作為一個非常簡單的例子，考慮在二維空間中由5個數據點{a 1，a 2，a 3，a 4，a 5 } 組成的數據集。

圖2.二維空間中5個數據點的示例

這些數據點的共識矩陣可能如下所示：

考慮突出顯示的元素（1,3），其對應於數據點對a 1，a 3。該要素的價值意味著：

（將1和3分配給同一簇的次數）/ （1和3一起選擇的次數）= 0.9

因此，在數據樣本中一起選擇點a 1和a 3的 90％時間，算法將它們放在同一個群集中。另一方面，共識矩陣意味著只有10％的時間算法放在一起（元素（1,4））選擇一個1和4在相同的群集。

令人滿意的共識意味著共識矩陣的任何非對角元素都非常接近1，因為特定的數據點對是相似的，因此算法在大多數迭代中將它們分配給相同的群集，或者非常接近0 ，因為特定的數據點對是不相似的，因此算法在大多數迭代中將它們分配給不同的群集。另一方面，遠離0和1的條目意味著較差的共識。例如，值為0.5的條目意味著該算法已將相應的一對數據點放置在50％的迭代中的相同群集中，並且在剩餘的50％的迭代中放置在單獨的群集中。

共識矩陣的行和列可以被置換，以使最近的數據點儘可能地彼此相鄰，從而產生對稱的熱圖，然後通過視覺檢查幫助決定共識[9]。參見[10]查看從共識矩陣生成熱圖的算法。

對於視覺檢查，熱圖的另一種方法是開發與共識矩陣有關的直方圖，稱為共識指數直方圖[7]。直方圖的水平軸表示一對兩個不同數據點出現在同一個群集中的次數與所有迭代中同一子樣本中該對次數的比率。直方圖的縱軸顯示達到特定比率的次數。在理想情況下，直方圖只趨向於接近1和0的兩個倉，其中1附近的倉代表同一集群中的一對不同數據點，而0附近的倉代表一對不同的數據點，它們分別是在大部分時間跨越所有迭代的不同群集中。

對於每個K均值，平分K均值和高斯混合算法，我們將一致的聚類技術應用於我們的數據集，以創建m= 20次迭代的三個聚類。在每次迭代中，隨機子樣本由原始數據集的〜90％組成。每種算法的直方圖如下所示（生成這些圖表的應用程序的源代碼將在下一節中進行介紹）。

圖3. K-means算法的直方圖。

圖4.平分K均值算法的直方圖。

圖5.高斯混合算法的直方圖。

對於平分K均值和高斯混合算法，數據主要累積在0和1附近的箱中，特別是在區間[0,0.2]和[0.8,1.0]中。另一方面，對於K均值算法，0到1之間的分箱包含太多的數據點，特別是在區間[0.4,0.7]中。因此，我們得出這樣的結論：對於特定的數據集，K均值算法沒有達到像平分K均值或高斯混合一樣令人滿意的共識。

代碼審查

我們實施了一個示例Java應用程序來演示共識聚類。應用程序使用Apache Spark機器學習庫API用於K-means，Bisecting K-means和Gaussian Mixture（Spark版本2.3.0）。一個名為抽象類的 ConsensusCluster存儲所有用於計算直方圖的邏輯。三個具體的類， BisectingKMeansClustering， KMeansClustering 和， GaussianMixtureClustering每個代表一個特定的聚類算法，創建實際的簇。

圖6.演示應用程序的類圖。

示例應用程序使用一個數據集，如前面在美國國家癌症研究所GDC數據門戶網站下載的關於多形性成膠質細胞瘤（GBM）和低級別膠質瘤（LGG）患者['11]中的'問題陳述'中所述。它由76個不同的數據點組成。對於一致計算，我們運行了20次迭代。在每次迭代中，數據被隨機二次採樣，每個子採樣包含原始（完整）數據集的約90％。

使用每種算法，我們在每次迭代中創建了三個群集。我們在所有迭代完成後生成直方圖數據。圖3,4,5給出了每種算法的直方圖圖。

結論

在本文中，我們討論了共識聚類，這是一種用於在多次聚類算法運行中表示共識的技術，並分析了發現聚類在採樣變異性方面的穩定性。我們回顧了使用Apache Spark機器學習庫構建的示例應用程序，以顯示如何使用K-means，Bisecting K-means和高斯混合（三種不同的聚類算法）可以使用共識聚類。對於應用程序中考慮的示例數據集，我們計算並繪製了共識指數的直方圖。直方圖表明，平分K均值和高斯混合算法比K均值算法提供更穩定的聚類。一些結論性意見如下。

• 共識聚類可應用於任何聚類算法，並可用於比較同一數據集上的不同算法。然而，一致聚類的目的不是決定哪些聚類算法比其他算法更穩定一般。結果取決於特定的數據集和數據點之間關係的性質。例如，層次聚類算法可能無法達到令人滿意的本質上不分層次的數據集的共識，反之亦然。
• 另外可以使用共識聚類來確定數據集和聚類算法的最佳聚類數。共識矩陣也可以用作相似性度量，是其他度量的替代方法，例如歐幾里得距離[7]。
• 圖1.a，1.b中的樣本簇的三維圖由基於Java的jzy3d框架[12]獲得，圖3-5中的直方圖由Microsoft Excel繪製。
• 示例應用程序的完整源代碼可以在[13]中找到。