分群演算法

機器學習資料集可能有數百萬個 ,但不是所有分群演算法都能有效調度資源。分群 演算法會計算所有樣本組合的相似度, 執行階段會隨著樣本數的平方而增加。 \(n\) 會以複雜標記法表示。 \(O(n^2)\) \(O(n^2)\) 演算法不是 我們會用數百萬個範例 分析資料集的執行情況

k-means 演算法具有 \(O(n)\)的複雜程度,代表演算法是與 \(n\)線性擴充。 這套演算法將成為本課程的焦點。

分群法類型

如需不同分群方法的完整清單,請參閱 全方位叢集演算法問卷調查 Xu, D.& Tian, Y. 安資料。科學(2015) 2:165。每種方法 特定資料分佈情形本課程會簡單討論四種 。

基於中心點的分群法

叢集的「質心」是 計算所有引數的算術平均數 物件中心型分群法將資料整理成非階層式 叢集內基於中心點的分群演算法有效率但較敏感 初始條件和離群值其中 k-means 是 廣受使用者歡迎這需要使用者定義群集中心數量、k 數量和 能搭配大致相同大小的叢集使用

使用基於群集點為基礎的分群法將樣本分組為叢集。
           線條代表集群的框線。
圖 1:群集中心的分群法範例。

以密度為基礎的分群法

以密度為基礎的分群法將高密度的連續區域串連成 叢集內這可讓您探索任意數量的叢集。 未將離群值指派給叢集。這些演算法在 包含各種密度和高維度資料的叢集

以密度為基礎的分群法分為兩個集群。
      叢集無法以線性方式分隔。
圖 2:密度為基礎的分群範例。

以分佈為基礎的叢集

這種分群法假設資料由機率性構成 分佈情形,例如 高斯分佈。於 圖 3:分佈式演算法叢集資料分成三大高斯 發行。隨著與分銷中心的距離增加, 資料點屬於分佈的機率下降。樂團表演 一些機率下降當您不放心地假設 您需要使用不同的演算法。

使用分佈為基礎的分群法建立叢集範例。每個叢集中範例密度的陰影,顯示了集群與分佈情形的對應關係。
圖 3:分佈式分群法範例。

階層分群法

階層分群法會建立叢集的樹狀結構。階層分群 因此,不適合用於階層式資料,例如分類。詳情請見 比較 61 個序列的 Escherichia 科利基因體 由 Oksana Lukjancenko、Trudy Wassenaar 和例如 Dave Ussery。 如要選擇任意數量的叢集,只要切斷正確的樹狀結構即可。

以階層式樹群聚集的動物。
圖 4:將動物分群的階層樹狀圖範例。