本頁面由 Cloud Translation API 翻譯而成。

執行分群演算法

在機器學習中，您有時候可能會遇到數百萬個範例的資料集。機器學習演算法必須有效率地調度資源，以處理這些大型資料集。不過，許多叢集演算法並不會擴充，因為演算法需要計算所有兩點之間的相似性。這表示執行階段會隨著點數數量的平方增加，表示為 $O(n^2)$。舉例來說，匯總或分割階層式分群法演算法會考量所有端點，並且分別具有 $O(n^2 log(n))$ 和 $O(n^2)$的複雜性。

本課程著重於 k-means，因為擴充範圍為 $O(nk)$，其中 $k$是叢集數量。k-means 會將點與叢集 centroid 之間的距離降到最低，如下圖指出 $k$ 叢集 (如圖 1 所示)。叢集的「centroid」是指叢集內所有點的平均值。

如上所示，k-means 會找出大致圓形的叢集。從概念上來說，這表示 k-means 會以相當近乎的圓形分散式資料有效處理資料，並嘗試找出與這些發行內容對應的叢集。但實際上，資料可能含有離群值，因此可能不符合這類模型。

在執行 k-means 之前，您必須選擇叢集數量 $k$。一開始，請先猜測 $k$的值。我們稍後會探討如何修正這個數字。

k-means 分群演算法

如要將資料分群到 $k$ 叢集，k-means 請按照下列步驟操作：

初始化時的 k-means 圖表 — **圖 1：初始化時的 k-means。**

第一步

演算法會為每個叢集隨機選擇質心。在我們的範例中，我們選擇 3 的 $k$ ，因此演算法會隨機選擇 3 個質心。

第二步

演算法會將每個點指派給最接近的 centroid，以便取得 $k$ 初始叢集。

第三步

演算法會針對每個叢集，計算叢集中所有點的平均值。質心圖的變更內容在圖 3 以箭頭中顯示。由於質感設計有所改變，演算法隨後會將點重新指派給最接近的質心。圖 4 顯示重新指派後的新叢集。

第四步

演算法會重複計算 centroid，並指派點數，直到分數停止變更叢集為止。將大型資料集分群時，系統會先停止演算法，然後再進行融合，然後再使用其他條件。

你不需要瞭解本課程的 k-means 幕後數學。不過，如果您有興趣，請參閱下文中的數學證明。

按一下數學圖示的加號圖示

只要將 $n$ 範例指派給 $k$ 叢集，盡量將範例的距離與其質心的距離相加。地點：

$A_{nk} = 1$ 第 $n$個範例指派給 $k$叢集時為 0，而非為 0
$\theta_k$ 是集群的質心 $k$

我們希望盡可能減少以下運算式： $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ subject: $$A_{nk} \in \{0,1\} \forall n,k$$ 和 $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ 為減少叢集 centroid 的運算式 $\theta_k$，根據變化瞭解 $\theta_k$ $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ 分子是叢集中的所有範例質心距離總和。分母是叢集中的範例數量。因此，叢集 centroid$\theta_k$ 是叢集內範例中心距離的平均值。事實證明，

由於質心位置最初是隨機選擇，因此 k-means 會在連續執行作業上傳回明顯不同的結果。如要解決這個問題，請多次執行 k-means，並選擇最高品質的指標。(本課程稍後會說明品質指標)。您需要進階版本的 k-means 才能選擇更好的初始 centroid 位置。

摘要

解讀結果