机器学习_分类_数据聚类

K-Means(k-平均或k-均值)

可以称的上是知名度最高的一种聚类算法

首先,我们确定要几个的聚类(cluster,也称簇),并为它们随机初始化一个各自的聚类质心点(cluster centroids),它在上图中被表示为“X”。要确定聚类的数量,我们可以先快速看一看已有的数据点,并从中分辨出一些独特的数据。
其次,我们计算每个数据点到质心的距离来进行分类,它跟哪个聚类的质心更近,它就被分类到该聚类。
需要注意的是,初始质心并不是真正的质心,质心应满足聚类里每个点到它的欧式距离平方和最小这个条件。因此根据这些被初步分类完毕的数据点,我们再重新计算每一聚类中所有向量的平均值,并确定出新的质心。
最后,重复上述步骤,进行一定次数的迭代,直到质心的位置不再发生太大变化。当然你也可以在第一步时多初始化几次,然后选取一个看起来更合理的点节约时间。
K-Means的优点是速度非常快,因为我们所做的只是计算数据点和质心点之间的距离,涉及到的计算量非常少!因此它的算法时间复杂度只有O(n)。

另一方面,K-Means有两个缺点。一是你必须一开始就决定数据集中包含多少个聚类。这个缺点并不总是微不足道的,理想情况下,我们的目标其实是用一种算法来分类这些数据,并从结果中观察出一些规律,而不是限制几个条件强行聚类。二是一开始质心点的选取是随机的,算法可能会初始化出差异巨大的点。这个缺点导致的结果是质心点的位置不可重复且缺乏一致性。

K-Medians是与K-Means相关的另一种聚类算法,不同之处在于它使用簇的中值向量来重新计算质心点。该方法对异常值不敏感(因为使用中值),但在较大数据集上运行时速度会慢很多,因为每次计算中值向量,我们都要重新排序。

Mean-Shift聚类

Mean shift算法,又称均值漂移算法,这是一种基于核密度估计的爬山算法,可用于聚类、图像分割、跟踪等。它的工作原理基于质心,这意味着它的目标是定位每个簇/类的质心,即先算出当前点的偏移均值,将该点移动到此偏移均值,然后以此为新的起始点,继续移动,直到满足最终的条件(找出最密集的区域)。

1、为了理解均值漂移,我们可以像上图一样想象二维空间中的一组数据点,然后先随机选择一个点C,以它为圆心画一个半径为r的圆开始移动。之前提到了,这是个爬山算法,它的核函数会随着迭代次数增加逐渐向高密度区域靠近。
2、在每轮迭代中,算法会不断计算圆心到质心的偏移均值,然后整体向质心靠近。漂移圆圈内的密度与数据点数成正比。到达质心后,算法会更新质心位置,并继续让圆圈向更高密度的区域靠近。
3、当圆圈到达目标质心后,它发现自己无论朝哪个方向漂移都找不到更多的数据点,这时我们就认为它已经处于最密集的区域。
4、这时,算法满足了最终的条件,即退出。

Mean-Shift不需要实现定义聚类数量,因为这些都可以在计算偏移均值时得出。这是一个巨大的优势。同时,算法推动聚类中心在向密度最大区域靠近的效果也非常令人满意,这一过程符合数据驱动型任务的需要,而且十分自然直观。如果要说Mean-Shift有什么缺点,那就是对高维球区域的半径r的定义,不同选择可能会产生高度不同的影响。

EM聚类

均值→质心,方差→椭圆聚类,权重→聚类大小。
K-Means算法的主要缺点之一是它直接用了距离质心的平均值。

1、首先,我们确定聚类的数量(如K-Means),并随机初始化每个聚类的高斯分布参数。你也可以尝试通过快速查看数据来为初始参数提供更好的猜测,但从上图可以看出,这其实不是很必要,因为算法会很快进行优化。
2、其次,根据每个聚类的高斯分布,计算数据点属于特定聚类的概率。如果数据点越接近高斯质心,那它属于该聚类的概率就越高。这很直观,因为对于高斯分布,我们一般假设大部分数据更靠近聚类质心。
3、在这些概率的基础上,我们为高斯分布计算一组新的参数,使聚类内数据点的概率最大化。我们用数据点位置的加权和来计算这些新参数,其中权重就是数据点属于聚类的概率。为了可视化这个过程,我们可以看看上面的图片,特别是黄色的聚类。第一次迭代中,它是随机的,大多数黄点都集中在该聚类的右侧。当我们按概率计算加权和后,虽然聚类的中部出现一些点,但右侧的比重依然很高。随着迭代次数增加,黄点在聚类中的位置也完成了“右下→左下”的移动。因此,标准差的变化调整着聚类的形状,以使它能更适合数据点的分布。
4、迭代步骤2和步骤3,直至收敛。

GMM有两个关键优势。首先它比K-Means更灵活,由于标准差的引入,最后聚类的形状不再局限于圆形,它还可以是大小形状不一的椭圆形——K均值实际上是GMM的一个特例,其中每个聚类的协方差在所有维上都接近0。其次,权重的引入为同一点属于多个聚类找到了解决方案。如果一个数据点位于两个聚类的重叠区域,那我们就可以简单为它定义一个聚类,或者计算它属于X聚类的百分比是多少,属于Y聚类的百分比是多少。简而言之,GMM支持混合“成员”。

谈及缺点,和K-Means相比,GMM每一步迭代的计算量比较大。另外,它的求解办法基于EM算法,因此有可能陷入局部极值,需要经过多次迭代。
最后修改:2020 年 07 月 18 日 11 : 30 AM
如果觉得我的文章对你有用,请随意赞赏