此页面由 Cloud Translation API 翻译。

运行聚类算法

在机器学习中，您有时会遇到可以有数百万个样本的数据集。机器学习算法必须高效地扩展到这些大型数据集。但是，许多聚类算法无法扩缩，因为它们需要计算所有点对之间的相似度。这意味着其运行时将增加为点数量的平方，表示为 $O(n^2)$。例如，凝聚式或划分式聚类算法会分别查看所有点对和 $O(n^2 log(n))$ 和 $O(n^2)$的复杂性。

本课程重点介绍 k-average，因为它以 $O(nk)$的形式进行缩放，其中 $k$是聚类的数量。k-} 通过最大限度减小点与其聚类点之间的距离来将点分组到 $k$ 聚类中（如图 1 所示）。集群的形心是集群中所有点的平均值。

如上所示，k-means 会找到大致的圆形聚类。从概念上讲，这意味着 k-average 会将数据有效视为由多个大致的圆形分布组成，并尝试查找与这些分布对应的聚类。实际上，数据包含离群值，可能并不适合这种模型。

在运行 k-平均值之前，您必须选择集群数量： $k$。最初，猜测 $k$。稍后，我们将讨论如何优化此数字。

k-平均值聚类算法

如需将数据聚类为 $k$ 集群，k-} 请按以下步骤操作：

初始化时 k-average 的图 — **图 1：初始化时的 k-average。**

第 1 步

该算法会为每个聚类随机选择一个形心。在我们的示例中，我们从 3 中选择 $k$ ，因此算法会随机选择 3 个形心。

第 2 步

该算法将每个点分配到最接近的形心，以获取 $k$ 初始聚类。

第 3 步

对于每个聚类，该算法通过取聚类中所有点的平均值来重新计算形心。图 3 中用箭头显示了形心的变化。由于形心发生变化，因此该算法会将这些点重新分配给最近的形心。图 4 显示了重新分配后的新集群。

第四步

此算法会重复计算形心和点的分配，直到点停止更改聚类。对大型数据集进行聚类时，您可以在使用其他算法收敛之前停止算法，改用其他条件。

您无需了解本课程中 k-average 的数学知识。不过，如果您想知道数学概念，请参阅下文。

点击加号图标可进行数学证明

对于已分配给 $k$ 聚类的 $n$ 示例，应最大限度降低样本与形心的距离总和。其中：

$A_{nk} = 1$ 第 $n$个示例分配给第 $k$个集群时，$A_{nk} = 1$ 为 0；否则为 0
$\theta_k$ 是聚类的形心 $k$

我们希望将以下表达式最小化： $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ 受以下因素限制： $$A_{nk} \in \{0,1\} \forall n,k$$ $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ 如需使表达式相对于聚类形心 $\theta_k$最小化，请求出相对于 $\theta_k$ 的导数，并对其等于 0。 $$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}}$$ 分子是集群中所有示例形距离的总和。分母是集群中的样本数。因此，聚类的形心$\theta_k$ 是聚类中形心距离的平均值。事实证明，

由于形心位置最初是随机选择的，因此在连续运行中，k-已安装值可能会返回截然不同的结果。要解决此问题，多次运行 k-average 并选择具有最高质量指标的结果。（我们将在本课程的后面部分介绍质量指标。）您需要使用高级 k-average 版本来选择更好的初始形心位置。

总结

解读结果