中国统计网来源

一文盘点5种聚类算法,数据科学家必备!

本文为你分析基本聚类方法的实现概念,并给出每种算法的优缺点及实际的应用场景。

聚类是一种将数据点按一定规则分群的机器学习技术。

给定一组数据点,我们可以使用聚类算法将每个数据点分类到一个特定的簇中。理论上,属于同一类的数据点应具有相似的属性或特征,而不同类中的数据点应具有差异很大的属性或特征。

聚类属于无监督学习中的一种方法,也是一种在许多领域中用于统计数据分析的常用技术。

一、K-均值聚类

K-Means可能是最知名的聚类算法,没有之一。并且该算法的代码很容易理解和实现!你可以通过看下面的插图来理解它。

1. 首先,我们选择一些要使用的类/组,并随机初始化他们各自的中心点(质心)。要计算出簇(类)的使用数量,最好的方法是快速查看一下数据并尝试鉴别有多少不同的分组。中心点是一个矢量,它到每个数据点的矢量长度相同,在上图中用“X”来表示。

2. 每个数据点通过计算该点与每个簇中心之间的距离来进行分类,根据最小距离,将该点分类到对应中心点的簇中。

3. 根据这些已分类的点,我们重新计算簇中所有向量的均值,来确定新的中心点。

4. 重复以上步骤来进行一定数量的迭代,或者直到簇中心点在迭代之间变化不大。你也可以选择多次随机初始化簇中心点,然后选择看起来像是最佳结果的数据,再来重复以上步骤。

K-Means算法的优势在于它的速度非常快,因为我们所做的只是计算点和簇中心之间的距离; 这已经是非常少的计算了!因此它具有线性的复杂度O(n)。

但是,K-Means算法也是有一些缺点。首先,你必须手动选择有多少簇。

这是一个很大的弊端,理想情况下,我们是希望能使用一个聚类算法来帮助我们找出有多少簇,因为聚类算法的目的就是从数据中来获得一些有用信息。

K-means算法的另一个缺点是从随机选择的簇中心点开始运行,这导致每一次运行该算法可能产生不同的聚类结果。

因此,该算法结果可能具有不可重复,缺乏一致性等性质。而其他聚类算法的结果则会显得更一致一些。

K-Medians是与K-Means类似的另一种聚类算法,它是通过计算类中所有向量的中值,而不是平均值,来确定簇的中心点。

这种方法的优点是对数据中的异常值不太敏感,但是在较大的数据集时进行聚类时,速度要慢得多,造成这种现象的原因是这种方法每次迭代时,都需要对数据进行排序。

二、Mean-Shift聚类算法

Mean-Shift是一种基于滑动窗口的聚类算法。也可以说它是一种基于质心的算法,这意思是它是通过计算滑动窗口中的均值来更新中心点的候选框,以此达到找到每个簇中心点的目的。然后在剩下的处理阶段中,对这些候选窗口进行滤波以消除近似或重复的窗口,找到最终的中心点及其对应的簇。看看下面的图解。

用于单个滑动窗口的Mean-Shift聚类算法

1. 为了阐释Mean-shift算法,我们可以考虑二维空间中的一组点,如上图所示。我们从一个以C点(随机选择)为中心,以半径r为核心的圆滑动窗口开始。Mean-shift可以看作是一种等高线算法,在每次迭代中,它能将核函数(圆滑动窗口)移动到每个迭代中较高密度的区域,直至收敛

2. 在每次迭代中,通过将中心点移动到窗口内点的平均值处(因此得名),来使滑动窗口移向更高密度的区域。滑动窗口内的数据密度与其内部点的数目成正比。当然,通过移动窗口中点的平均值,它(滑动窗口)就会逐渐移向点密度更高的区域。

3. 我们继续根据平均值来移动滑动窗口,直到不能找到一个移动方向,使滑动窗口可以容纳更多的点。看看上面图片的动画效果;直到滑动窗口内不再增加密度(即窗口中的点数),我们才停止移动这个圆圈。

4. 步骤1至步骤3的过程是由许多滑动窗口来完成的,直到所有的点都能位于对应窗口内时才停止。当多个滑动窗口重叠时,该算法就保留包含最多点的窗口。最终所有数据点根据它们所在的滑动窗口来确定分到哪一类。

下图显示了所有滑动窗口从头到尾的整个移动过程。每个黑点代表滑动窗口的质心,每个灰点代表一个数据点。

Mean-Shift聚类的整个过程

与K-means聚类算法相比,Mean-shift算法是不需要选择簇的数量,因为它是自动找寻有几类。这是一个相比其他算法巨大的优点。而且该算法的聚类效果也是非常理想的,在自然数据驱动的情况下,它能非常直观的展现和符合其意义。算法的缺点是固定了窗口大小/半径“r”。

三、基于密度的噪声应用空间聚类(DBSCAN)

DBSCAN是一种基于密度的聚类算法,类似于Mean-shift算法,但具有一些显着的优点。我们从看下面这个奇特的图形开始了解该算法。

DBSCAN笑脸人脸聚类

1. DBSCAN算法从一个未被访问的任意的数据点开始。这个点的邻域是用距离epsilon来定义(即该点ε距离范围内的所有点都是邻域点)

2. 如果在该邻域内有足够数量的点(根据minPoints的值),则聚类过程开始,并且当前数据点成为新簇中的第一个点。否则,该点将被标记为噪声(稍后,这个噪声点可能成为聚类中的一部分)。在这两种情况下,该点都会被标记为“已访问”。

3. 对于新簇中的第一个点,它的ε距离邻域内的点也会成为同簇的一部分。这个过程使ε邻域内的所有点都属于同一个簇,然后对才添加到簇中的所有新点重复上述过程。

4. 重复步骤2和3两个过程直到确定了聚类中的所有点才停止,即访问和标记了聚类的ε邻域内的所有点。

5. 一旦我们完成了当前的聚类,就检索和处理新的未访问的点,就能进一步发现新的簇或者是噪声。重复上述过程,直到所有点被标记为已访问才停止。由于所有点已经被访问完毕,每个点都被标记为属于一个簇或是噪声。

与其他聚类算法相比,DBSCAN具有很多优点。首先,它根本不需要确定簇的数量。不同于Mean-shift算法,当数据点非常不同时,会将它们单纯地引入簇中,DBSCAN能将异常值识别为噪声。另外,它能够很好地找到任意大小和任意形状的簇。

DBSCAN算法的主要缺点是,当数据簇密度不均匀时,它的效果不如其他算法好。这是因为当密度变化时,用于识别邻近点的距离阈值ε和minPoints的设置将随着簇而变化。在处理高维数据时也会出现这种缺点,因为难以估计距离阈值ε。

四、使用高斯混合模型(GMM)的期望最大化(EM)聚类

K-Means算法的主要缺点之一就是它对于聚类中心平均值的使用太单一。

通过查看下面的图例,我们可以明白为什么它不是使用均值最佳的方式。

在左侧,人眼看起来非常明显的是,具有相同均值的数据中心点,却是不同半径长度的两个圆形簇。

而K-Means算法不能解决这样的数据问题,因为这些簇的均值是非常接近的。K-Means算法在簇不是圆形的情况下也一样无效,也是由于使用均值作为集群中心。

K-Means算法两个失败的案例

相较于K-means算法,高斯混合模型(GMMs)能处理更多的情况。对于GMM,我们假设数据点是高斯分布的; 这是一个限制较少的假设,而不是用均值来表示它们是圆形的。这样,我们有两个参数来描述簇的形状:即均值和标准差!以二维为例,这意味着这些簇可以是任何类型的椭圆形(因为GMM在x和y方向上都有标准偏差)。因此,每个高斯分布都被单个簇所指定。

为了找到每个簇的高斯参数(例如平均值和标准差),我们将使用期望最大化(EM)的优化算法。请看下面的图表,可以作为匹配簇的高斯图的阐释。然后我们来完成使用GMM的期望最大化聚类过程。

使用GMM的EM聚类

1. 我们首先选择簇的数量(如K-Means),然后随机初始化每个簇的高斯分布参数。可以通过快速查看数据的方式,来尝试为初始参数提供一个较好的猜测。不过请注意,从上图可以看出,这不是100%必要的,因为即使是从一个很差的高斯分布开始,算法也能很快的优化它。

2. 给定每个簇的高斯分布,计算每个数据点属于特定簇的概率。一个点越靠近高斯的中心,它越可能属于该簇。在使用高斯分布时这应该是非常直观的,因为我们假设大部分数据更靠近簇的中心。

3. 基于这些概率,我们为高斯分布计算一组新的参数,使得我们能最大化簇内数据点的概率。我们使用数据点位置的加权和来计算这些新参数,其中权重是数据点属于该特定簇的概率。为了更直观的解释这个,我们可以看看上面的图片,特别是黄色的簇。

第一次迭代时,分布是随机开始,但是我们可以看到大部分黄点都在分布的右侧。当我们计算按概率加权的和时,即使中心附近的点大部分都在右边,通过分配的均值自然就会接近这些点。我们也可以看到,大部分数据点都是“从右上到左下”。因此,改变标准差的值,可以找到一个更适合这些点的椭圆,以最大化概率加权的总和。

4. 重复迭步骤2和3,直到收敛,也就是分布在迭代中基本再无变化。

使用GMM方法有两个很重要的优点。 首先,GMM方法在聚类协方差上比K-Means灵活得多; 由于使用了标准偏差参数,簇可以呈现任何椭圆形状,而不是被限制为圆形。 K-mean算法实际上是GMM的一个特殊情况,即每个簇的协方差在所有维度上都接近0。其次,由于GMM使用了概率,每个数据点可以有多个簇。因此,如果一个数据点位于两个重叠的簇的中间,我们可以简单地定义它的类,即属于类1的概率是百分之X,属于类2的概率是百分之Y。即,GMM支持混合类这种情况。

五、凝聚层次聚类

分层聚类算法实际上分为两类:

  • 自上而下

  • 自下而上

自下而上的算法首先将每个数据点视为一个单一的簇,然后连续地合并(或聚合)成对的簇,直到所有的簇都合并成一个包含所有数据点的簇。

因此,自下而上的分层聚类被称为合成聚类或HAC。

这个簇的层次可以用树(或树状图)表示。树的根是收集所有样本的唯一簇,叶是仅具有一个样本的簇。

在进入算法步骤之前,请查看下面的图解。

合成聚类

1. 我们首先将每个数据点视为一个单一的簇,即如果我们的数据集中有X个数据点,那么我们就有X个簇。然后,我们选择一个距离度量,来度量两个簇之间距离。作为一个例子,我们将使用平均关联度量,它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。

2. 在每次迭代中,我们将两个簇合并成一个簇。选择平均关联值最小的两个簇进行合并。根据我们选择的距离度量,这两个簇之间的距离最小,因此是最相似的,所有应该合并。

3. 重复步骤2直到我们到达树的根,即我们只有一个包含所有数据点的簇。通过这种方式,我们可以选择最终需要多少个簇。方法就是选择何时停止合并簇,即停止构建树时!

分层次聚类不需要我们指定簇的数量,我们甚至可以在构建树的同时,选择一个看起来效果最好的簇的数量。

另外,该算法对距离度量的选择并不敏感,与其他距离度量选择很重要的聚类算法相比,该算法下的所有距离度量方法都表现得很好。

当基础数据具有层次结构,并且想要恢复层次结构时,层次聚类算法能实现这一目标;而其他聚类算法则不能做到这一点。

与K-Means和GMM的线性复杂性不同,层次聚类的这些优点是以较低的效率为代价,即它具有O(n3)的时间复杂度

THU数据派
THU数据派

THU数据派"基于清华,放眼世界",以扎实的理工功底闯荡“数据江湖”。发布全球大数据资讯,定期组织线下活动,分享前沿产业动态。了解清华大数据,敬请关注姐妹号“数据派THU”。

入门高斯混合模型层次聚类最大期望算法DBSCAN聚类无监督学习聚类算法Mean-Shiftk-means
3
相关数据
数据分析技术

数据分析是一类统计方法,其主要特点是多维性和描述性。有些几何方法有助于揭示不同的数据之间存在的关系,并绘制出统计信息图,以更简洁的解释这些数据中包含的主要信息。其他一些用于收集数据,以便弄清哪些是同质的,从而更好地了解数据。 数据分析可以处理大量数据,并确定这些数据最有用的部分。

权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

高斯分布技术

正态分布是一个非常常见的连续概率分布。由于中心极限定理(Central Limit Theorem)的广泛应用,正态分布在统计学上非常重要。中心极限定理表明,由一组独立同分布,并且具有有限的数学期望和方差的随机变量X1,X2,X3,...Xn构成的平均随机变量Y近似的服从正态分布当n趋近于无穷。另外众多物理计量是由许多独立随机过程的和构成,因而往往也具有正态分布。

核函数技术

核函数包括线性核函数、多项式核函数、高斯核函数等,其中高斯核函数最常用,可以将数据映射到无穷维,也叫做径向基函数(Radial Basis Function 简称 RBF),是某种沿径向对称的标量函数。最常应用于SVM支持向量机中

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

层次聚类技术

层次聚类通过对数据集在不同层次进行划分,从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合(agglomerative)策略,也可采用“自顶向下”的分拆(divisive)策略。“自底而上”的算法开始时把每一个原始数据看作一个单一的聚类簇,然后不断聚合小的聚类簇成为大的聚类。“自顶向下”的算法开始把所有数据看作一个聚类,通过不断分割大的聚类直到每一个单一的数据都被划分。

高斯混合模型技术

高斯混合模型(Gaussian Mixture Model,GMM)是单一高斯概率密度函数的延伸,就是用多个高斯概率密度函数(正态分布曲线)精确地量化变量分布,是将变量分布分解为若干基于高斯概率密度函数(正态分布曲线)分布的统计模型。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

推荐文章
暂无评论
暂无评论~