聚类算法：从开始到最新

本文概述

• K均值聚类
• EM集群
• 亲和力传播
• 到底…

成为一名数据科学家并不是一个坏时机。如果你将对话转向”大数据”, 那么认真的人可能会对你感兴趣, 而当你提到”人工智能”和”机器学习”时, 会吸引其他党派人士。甚至Google都认为你还不错, 而且你正在变得更好。有很多”智能”算法可以帮助数据科学家完成向导。这看起来似乎很复杂, 但是如果我们稍微了解并组织算法, 那么找到并应用所需的算法就不难了。

数据挖掘或机器学习课程通常从群集开始, 因为它既简单又有用。它是无监督学习领域中重要的一部分, 我们要描述的数据未标记。在大多数情况下, 这是用户未向我们提供多少有关预期输出的信息的地方。该算法仅包含数据, 并且应尽其所能。在我们的案例中, 它应该执行聚类-将数据分成包含相似数据点的组(集群), 而组之间的差异尽可能大。数据点可以代表任何事物, 例如我们的客户。例如, 如果我们想对相似的用户进行分组, 然后在每个集群上运行不同的营销活动, 那么集群将非常有用。

K均值聚类

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

该算法首先选择k个点作为起始质心(聚类的”中心”)。我们可以选择任意k个随机点, 也可以使用其他方法, 但是挑选随机点是一个好的开始。然后, 我们迭代地重复两个步骤：

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

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

每次迭代之后, 质心缓慢移动, 并且每个点到其指定质心的总距离越来越小。这两个步骤交替进行, 直到收敛为止, 这意味着直到群集分配中没有更多更改为止。经过多次迭代后, 会将相同的点集分配给每个质心, 从而再次导致相同的质心。保证K-Means收敛到局部最优。但是, 这不一定是最佳的整体解决方案(全局最佳)。

最终的聚类结果可能取决于初始质心的选择, 因此已经对该问题进行了很多思考。一个简单的解决方案是使用随机初始分配多次运行K-Means。然后, 我们可以选择最佳结果, 方法是从每个点到其簇的距离之和为最小, 这就是我们首先要最小化的误差值。

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

K-Means ++也是Python的Scikit-learn K-Means实现的默认初始化。如果你使用的是Python, 则可以选择该库。对于Java, Weka库可能是一个不错的开始：

Java(安装)

// 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均值聚类, 每个点仅分配给单个聚类, 并且聚类仅由其质心描述。这不太灵活, 因为我们可能会遇到重叠的群集或非圆形群集的问题。借助EM聚类, 我们现在可以更进一步, 并通过质心(均值), 协方差(这样我们可以拥有椭圆形聚类)和权重(聚类的大小)来描述每个聚类。现在, 一个点属于聚类的概率由多元高斯概率分布(多元-取决于多个变量)给出。这也意味着我们可以计算出一个点处于高斯”钟形”之下的概率, 即一个点属于一个簇的概率。

现在, 我们通过为每个点计算属于每个当前聚类的概率来开始EM程序(再次可能在开始时随机创建)。这是电子步骤。如果一个聚类是某个点的非常好的候选者, 那么它的概率将接近一个。但是, 可以接受两个或多个聚类, 因此该点在聚类上具有概率分布。不属于一个聚类的点的算法的这种属性称为”软聚类”。

现在, M步骤使用对先前集群集的点分配来重新计算每个集群的参数。为了计算聚类的新均值, 协方差和权重, 每个点数据均按其在聚类中的概率进行加权, 如上一步中所述。

改变这两个步骤将增加总的对数似然率, 直到收敛为止。同样, 最大值可能是局部的, 因此我们可以多次运行该算法以获得更好的聚类。

如果现在要为每个点确定一个聚类, 则可以简单地选择最可能的一个。有了概率模型, 我们还可以使用它来生成相似的数据, 即对与我们观察到的数据相似的更多点进行采样。

亲和力传播

亲和力传播(AP)由Frey和Dueck于2007年发布, 由于其简单性, 通用性和性能而越来越受欢迎。它正在将其地位从最新状态转变为事实上的标准。

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

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

1. 数据点之间的相似性, 代表一个点适合作为另一个例子。如果两点之间不存在相似性(例如它们不能属于同一群集), 则可以根据实现方式将这种相似性忽略或设置为-Infinity。

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

相似性和偏好通常都通过一个矩阵表示, 其中主对角线上的值代表偏好。矩阵表示法适用于密集数据集。在点之间的连接稀疏的地方, 更实际的做法是不将整个n x n矩阵存储在内存中, 而是保留与连接点的相似性列表。在幕后, “在两点之间交换消息”与处理矩阵是一回事, 这仅是透视和实现的问题。

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

1. 计算职责：责任r(i, k)反映了累积的证据, 其中考虑到了点i的其他潜在示例, 非常适合点k充当点i的示例。责任从数据点i发送到候选示例点k。

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

为了计算责任, 该算法使用在先前迭代中计算出的原始相似性和可用性(最初, 所有可用性均设置为零)。责任设置为点i和点k之间的输入相似性作为其示例, 减去点i和其他候选示例之间的相似性和可用性总和中的最大值。计算一个点对示例的合适程度的逻辑是, 如果先验先验偏好较高, 则优先考虑该点, 但是当相似点认为自己是好的候选人时, 责任就会降低, 因此存在一个”两者之间的竞争”, 直到某个迭代决定了。

然后, 计算可用性将计算出的责任用作每个候选人是否会做一个好的榜样的证据。可用性a(i, k)设置为自我责任r(k, k)加上候选样例k从其他点接收的肯定责任的总和。

最后, 我们可以有不同的停止标准来终止该过程, 例如, 当值的变化降至某个阈值以下或达到最大迭代次数时。在通过亲和传播过程的任何点上, 将责任矩阵(r)和可用性(a)相加即可得出我们所需的聚类信息：对于点i, 最大r(i, k)+ a(i, k)的k代表点我的榜样。或者, 如果仅需要示例集, 则可以扫描主对角线。如果r(i, i)+ a(i, i)> 0, 则点i是一个示例。

我们已经看到, 使用K-Means和类似的算法, 确定簇数可能很棘手。使用AP, 我们不必明确指定它, 但是如果我们获得的簇数多于或少于最优值, 则可能仍需要进行一些调整。幸运的是, 仅通过调整首选项, 我们就可以减少或增加集群的数量。将首选项设置为较高的值将导致更多的聚类, 因为每个点”更加确定”其是否适合作为示例, 因此很难”击败”并将其包含在其他点的”统治”下。相反, 设置较低的首选项将导致群集更少。好像他们在说”不, 不, 请, 你是一个更好的榜样, 我会加入你的集群”。通常, 对于中等数量到大量的群集, 我们可以将所有首选项设置为相似性的中位数, 对于中等数量的群集, 可以将所有偏好设置为最低的相似性。但是, 可能需要进行几次带有调整首选项的运行才能获得完全符合我们需求的结果。

分层亲和传播也值得一提, 它是一种处理二次复杂度的算法, 它通过将数据集分为几个子集, 分别对其进行聚类, 然后执行第二级聚类。

到底…

群集算法的种类繁多, 每一种都有其优缺点, 涉及它们使用的是哪种数据类型, 时间复杂度, 弱点等等。要提到更多算法, 例如, 分层聚类聚类(或链接聚类), 适用于我们不一定具有圆形(或超球形)聚类且事先不知道聚类数量的情况。它以每个点为一个单独的群集开始, 并在每一步中将两个最接近的群集连接起来, 直到所有内容都在一个大群集中为止。

使用分层聚集聚类, 我们可以通过在适合的地方水平切割树状图(树形图), 轻松地确定簇的数量。它也是可重复的(对于相同的数据集总是给出相同的答案), 但是复杂度更高(二次)。

然后, DBSCAN(带有噪声的应用程序的基于密度的空间聚类)也是值得一提的算法。它将紧密堆积在一起的点分组, 在附近点的任何方向扩展簇, 从而处理不同形状的簇。

这些算法值得一读, 以后我们可以在另一篇文章中进行探讨。

知道何时使用一种算法或另一种算法需要一些反复试验的经验。幸运的是, 我们有一系列使用不同编程语言的实现, 因此尝试它们仅需一点点的意愿。

相关：机器学习理论及其应用简介