分群演算法

機器學習資料集可能包含數百萬個示例,但並非所有叢集演算法都能有效擴充。許多叢集演算法會計算所有一對樣本之間的相似度,這表示其執行時間會隨著樣本數量平方而增加 n,在複雜度符號中以 O(n2) 表示。 O(n2) 演算法不適合用於包含數百萬個樣本的資料集。

k-means 演算法的複雜度為 O(n),表示演算法會以 n線性縮放。本課程將著重於這個演算法。

分群類型

如需各種分群方法的完整清單,請參閱 Xu, D. 的《A Comprehensive Survey of Clustering Algorithms》。& Tian, Y. Ann. Data. Sci. (2015) 2: 165。每種方法都最適合特定的資料分布。本課程將簡要介紹四種常見方法。

以群集中心為依據的分群

叢集的質心是叢集中所有點的算術平均值。以中心點為基礎的叢集會將資料整理成非階層叢集。以中心點為基礎的叢集演算法雖然效率高,但對初始條件和異常值相當敏感。其中,k 均值是最常用的演算法。使用者必須定義中心點數量 k,並與大致相同大小的叢集搭配使用。

使用以重心為基礎的叢集功能將資料分組的範例。線條代表叢集之間的邊界。
圖 1:以重心為基礎的叢集示例。

以密度為依據的分群

以密度為依據的叢集會將相鄰的高密度範圍連結成叢集。這可讓您探索任意形狀的叢集。系統不會將異常值指派至叢集。這些演算法無法處理不同密度的叢集和高維度資料。

使用密度為基礎的叢集功能將示例分為兩個叢集。叢集無法以線性方式分離。
圖 2:密度為依據的分群範例。

依分布方式進行分群

這個分群方法假設資料是由機率分布所組成,例如高斯分布。在圖 3 中,以分布為基礎的演算法將資料分為三個高斯分布。離散布圖中心的距離越遠,點屬於該散布圖的機率就越低。這些頻帶代表機率降低。如果您不確定資料的特定底層分佈情形,應使用其他演算法。

使用以分布為依據的分群方式進行叢集的範例。每個叢集中的示例密度陰影顯示叢集如何對應至分布情形。
圖 3:以分布為依據的叢集範例。

階層分群法

階層式叢集會建立叢集樹狀結構。階層分群法很適合階層式資料,例如分類法。如需範例,請參閱 Oksana Lukjancenko、Trudy Wassenaar 和 Dave Ussery 撰寫的「Comparison of 61 Sequenced Escherichia coli Genomes」。只要在正確的層級切割樹狀結構,即可選擇任意數量的叢集。

使用階層式樹狀圖將動物分組。
圖 4:動物階層樹狀叢集範例。