聚类算法：从开始到最先进

成为一名数据科学家并不是一个糟糕的时期。 如果你把话题转向“大数据”，严肃的人可能会对你产生兴趣，而当你提到“人工智能”和“机器学习”时，其他派对人群会很感兴趣。 甚至谷歌也认为你还不错，而且你正在变得更好。 有很多“智能”算法可以帮助数据科学家发挥作用。 这一切可能看起来很复杂，但如果我们稍微了解和组织算法，找到并应用我们需要的算法就不是那么难了。

数据挖掘或机器学习课程通常从聚类开始，因为它既简单又有用。 它是更广泛的无监督学习领域的重要组成部分，我们想要描述的数据没有被标记。 在大多数情况下，这是用户没有向我们提供有关预期输出的太多信息的地方。 该算法只有数据，它应该尽其所能。 在我们的例子中，它应该执行聚类——将数据分成包含相似数据点的组（集群），而组之间的差异尽可能高。 数据点可以代表任何事物，例如我们的客户。 例如，如果我们想要对相似的用户进行分组，然后在每个集群上运行不同的营销活动，集群就会很有用。

K-Means 聚类

在必要的介绍之后，数据挖掘课程总是继续使用 K-Means； 一种有效的、广泛使用的、全方位的聚类算法。 在实际运行它之前，我们必须定义数据点之间的距离函数（例如，如果我们想在空间中对点进行聚类，则为欧几里得距离），并且我们必须设置我们想要的聚类数（k）。

该算法首先选择 k 个点作为起始质心（集群的“中心”）。 我们可以选择任意 k 个随机点，或者我们可以使用其他方法，但选择随机点是一个好的开始。 然后，我们迭代地重复两个步骤：

1. 分配步骤：我们数据集中的 m 个点中的每一个都被分配给一个由 k 个质心中最近的一个表示的集群。 对于每个点，我们计算到每个质心的距离，然后简单地选择距离最小的一个。

2. 更新步骤：对于每个集群，计算一个新的质心作为集群中所有点的平均值。 从上一步开始，我们有一组分配给集群的点。 现在，对于每个这样的集合，我们计算一个平均值，我们声明一个新的集群质心。

每次迭代后，质心都在缓慢移动，每个点到其指定质心的总距离越来越小。 这两个步骤交替进行，直到收敛，这意味着直到集群分配不再有变化。 经过多次迭代，相同的点集将分配给每个质心，因此再次导致相同的质心。 K-Means 保证收敛到局部最优。 但是，这不一定是最佳的整体解决方案（全局最优）。

最终的聚类结果可能取决于初始质心的选择，因此对这个问题进行了很多思考。 一个简单的解决方案是使用随机初始分配运行 K-Means 几次。 然后，我们可以通过从每个点到其集群的距离总和最小的结果来选择最佳结果——我们首先试图最小化的误差值。

选择初始点的其他方法可以依赖于选择远点。 这可以带来更好的结果，但我们可能会遇到异常值的问题，那些罕见的单独点只是“关闭”，可能只是一些错误。 由于它们远离任何有意义的集群，因此每个这样的点最终都可能成为自己的“集群”。 一个很好的平衡是 K-Means++ 变体 [Arthur and Vassilvitskii, 2007]，其初始化仍然会选择随机点，但概率与与先前分配的质心的平方距离成正比。 距离较远的点将更有可能被选为起始质心。 因此，如果有一组点，则从该组中选择一个点的概率也会随着它们的概率相加而变得更高，从而解决了我们提到的异常值问题。

K-Means++ 也是 Python 的 Scikit-learn K-Means 实现的默认初始化。 如果您使用 Python，这可能是您的首选库。 对于 Java，Weka 库可能是一个好的开始：

爪哇 (Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python (Scikit-学习)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

在上面的 Python 示例中，我们使用了标准示例数据集“鸢尾花”，其中包含三种不同鸢尾花的花瓣和萼片尺寸。 我们将这些聚类成三个聚类，并将获得的聚类与实际物种（目标）进行比较，以查看它们完美匹配。

在这种情况下，我们知道存在三个不同的集群（物种），并且 K-Means 正确识别了哪些集群在一起。 但是，我们一般如何选择大量的集群 k 呢？ 这类问题在机器学习中很常见。 如果我们请求更多的集群，它们会更小，因此总误差（从点到分配的集群的距离总和）会更小。 那么，设置更大的 k 是否是个好主意？ 我们可能以 k = m 结束，也就是说，每个点都是它自己的质心，每个簇只有一个点。 是的，总误差为 0，但我们没有得到更简单的数据描述，也不足以涵盖一些可能出现的新点。 这称为过拟合，我们不希望这样。

处理这个问题的一种方法是对更多的集群进行一些惩罚。 所以，我们现在不仅要尽量减少错误，还要尽量减少错误+惩罚。 随着我们增加集群的数量，误差只会收敛到零，但惩罚会增加。 在某些时候，添加另一个集群的收益将小于引入的惩罚，我们将获得最佳结果。 为此目的使用贝叶斯信息准则 (BIC) 的解决方案称为 X-Means [Pelleg and Moore, 2000]。

我们必须正确定义的另一件事是距离函数。 有时这是一项简单的任务，考虑到数据的性质，这是一项合乎逻辑的任务。 对于空间中的点，欧几里得距离是一个明显的解决方案，但对于不同“单元”的特征、离散变量等可能会很棘手。这可能需要大量的领域知识。 或者，我们可以致电机器学习寻求帮助。 我们实际上可以尝试学习距离函数。 如果我们有一个训练集的点，我们知道它们应该如何分组（即用它们的簇标记的点），我们可以使用监督学习技术来找到一个好的函数，然后将它应用到我们尚未聚类的目标集.

K-Means 中使用的方法具有两个交替步骤，类似于期望最大化 (EM) 方法。 实际上，它可以被认为是一个非常简单的 EM 版本。 然而，它不应该与更复杂的 EM 聚类算法相混淆，即使它具有一些相同的原理。

EM聚类

因此，通过 K-Means 聚类，每个点都被分配给一个单独的聚类，并且一个聚类仅由其质心描述。 这不太灵活，因为我们可能会遇到重叠集群或非圆形集群的问题。 使用 EM 聚类，我们现在可以更进一步，通过质心（均值）、协方差（这样我们可以拥有椭圆聚类）和权重（聚类的大小）来描述每个聚类。 点属于集群的概率现在由多元高斯概率分布（多元 - 取决于多个变量）给出。 这也意味着我们可以计算一个点在高斯“钟”下的概率，即一个点属于一个簇的概率。

我们现在通过计算每个点属于每个当前集群的概率来开始 EM 过程（同样，这些集群可能在开始时随机创建）。 这是E步骤。 如果一个集群是一个非常好的候选点，它的概率将接近 1。 但是，两个或更多集群可以是可接受的候选者，因此该点在集群上具有概率分布。 算法的这种特性，即不属于一个簇的点被称为“软聚类”。

M 步现在使用分配给前一组集群的点重新计算每个集群的参数。 为了计算聚类的新均值、协方差和权重，每个点数据按照其属于聚类的概率加权，如上一步中计算的那样。

交替这两个步骤将增加总对数似然，直到它收敛。 同样，最大值可能是局部的，因此我们可以多次运行该算法以获得更好的集群。

如果我们现在想为每个点确定一个集群，我们可以简单地选择最可能的一个。 有了概率模型，我们也可以用它来生成相似的数据，也就是抽取更多与我们观察到的数据相似的点。

亲和传播

Affinity Propagation (AP) 由 Frey 和 Dueck 于 2007 年发布，并且由于其简单性、普遍适用性和性能而变得越来越流行。 它正在将其状态从最先进的技术转变为事实上的标准。

K-Means 和类似算法的主要缺点是必须选择聚类的数量，并选择初始点集。 相反，Affinity Propagation 将数据点对之间的相似性度量作为输入，同时将所有数据点视为潜在的样本。 在数据点之间交换实值消息，直到逐渐出现一组高质量的样本和相应的集群。

作为输入，算法要求我们提供两组数据：

1. 数据点之间的相似性，表示一个点作为另一个样本的适合程度。 如果两点之间没有相似性，因为它们不能属于同一个簇，则可以省略这种相似性或将其设置为 -Infinity ，具体取决于实现。

2. 首选项，表示每个数据点是否适合作为示例。 我们可能有一些先验信息，哪些点可能适合这个角色，因此我们可以通过偏好来表示它。

相似性和偏好通常通过单个矩阵表示，其中主对角线上的值代表偏好。 矩阵表示适用于密集数据集。 在点之间的连接稀疏的情况下，更实际的做法是不要将整个 nxn 矩阵存储在内存中，而是保留与连接点的相似性列表。 在幕后，“点之间交换信息”与操纵矩阵是一回事，只是视角和实现的问题。

然后该算法运行多次迭代，直到收敛。 每次迭代都有两个消息传递步骤：

1. 计算责任：责任 r(i, k) 反映了积累的证据，即 k 点作为 i 点的示例有多合适，同时考虑了 i 点的其他潜在示例。 责任从数据点 i 发送到候选样本点 k。

2. 计算可用性：可用性 a(i, k) 反映了积累的证据，表明 i 点选择 k 点作为其样本是多么合适，同时考虑到其他点对 k 点应该作为样本的支持。 可用性从候选示例点 k 发送到点 i。

为了计算责任，该算法使用在先前迭代中计算的原始相似性和可用性（最初，所有可用性都设置为零）。 责任被设置为点 i 和点 k 之间的输入相似性作为其样本，减去点 i 和其他候选样本之间的相似性和可用性和中的最大值。 计算一个点对样本的适用程度背后的逻辑是，如果最初的先验偏好更高，则它更受青睐，但当有一个相似的点认为自己是一个很好的候选者时，责任就会降低，所以有一个 '两者之间的竞争”，直到在某个迭代中决定一个。

然后，计算可用性使用计算的责任作为每个候选人是否会成为一个好榜样的证据。 可用性 a(i, k) 设置为自我责任 r(k, k) 加上候选样本 k 从其他点获得的积极责任的总和。

最后，我们可以有不同的停止标准来终止过程，例如当值的变化低于某个阈值或达到最大迭代次数时。 在通过 Affinity Propagation 过程的任何点，将责任 (r) 和可用性 (a) 矩阵求和为我们提供了我们需要的聚类信息：对于点 i，最大 r(i, k) + a(i, k) 的 k 表示点我是榜样。 或者，如果我们只需要一组样本，我们可以扫描主对角线。 如果 r(i, i) + a(i, i) > 0，则点 i 是一个示例。

我们已经看到，使用 K-Means 和类似算法，确定集群的数量可能很棘手。 使用 AP，我们不必明确指定它，但如果我们获得的集群比我们可能找到的最优值更多或更少，它可能仍需要一些调整。 幸运的是，只需调整偏好，我们就可以降低或提高集群的数量。 将偏好设置为更高的值将导致更多的集群，因为每个点都“更确定”它是否适合成为一个样本，因此更难“击败”并将其包含在其他点的“支配”之下。 相反，设置较低的偏好将导致更少的集群； 好像他们在说“不，不，拜托，你是一个更好的榜样，我会加入你的集群”。 作为一般规则，我们可以将所有偏好设置为中到大量集群的中值相似度，或者对于中等数量的集群，设置为最低相似度。 但是，可能需要进行几次调整偏好的运行才能获得完全符合我们需求的结果。

分层相似性传播也值得一提，它是处理二次复杂度的算法的一种变体，它通过将数据集分成几个子集，分别对它们进行聚类，然后执行第二级聚类。

到底…

有一系列的聚类算法，每一种算法都有各自的优缺点，包括它们使用的数据类型、时间复杂度、弱点等等。 提到更多的算法，例如有层次凝聚聚类（或链接聚类），适用于我们不一定有圆形（或超球形）集群，并且不知道预先知道集群数量的情况。 它从每个点都是一个单独的集群开始，并通过在每个步骤中加入两个最近的集群来工作，直到所有东西都在一个大集群中。

使用分层凝聚聚类，我们可以通过在我们认为合适的地方水平切割树状图（树形图）来轻松确定聚类的数量。 它也是可重复的（总是对相同的数据集给出相同的答案），但也具有更高的复杂性（二次）。

那么，DBSCAN（Density-Based Spatial Clustering of Applications with Noise）也是一个值得一提的算法。 它将紧密堆积在一起的点分组，在附近有点的任何方向扩展簇，从而处理不同形状的簇。

这些算法值得单独写一篇文章，我们可以稍后在单独的文章中探讨它们。

需要经过反复试验才能知道何时使用一种算法或另一种算法。 幸运的是，我们有一系列不同编程语言的实现，所以尝试它们只需要一点点玩的意愿。