登录 / 注册
IT168服务器频道
IT168首页 > 服务器 > 服务器资讯 > 正文

深度剖析:数据科学家需懂的5种聚类算法

2018-02-08 09:31    it168网站 原创  作者: 李佳惠 编辑: 李佳惠

  【IT168 资讯】聚类是一种涉及数据点分组的机器学习技术。给定一组数据点,我们可以使用聚类算法将每个数据点分类到一个特定的组中。理论上,属于同一组的数据点应具有相似的属性和特征,而不同组中的数据点应具有高度不同的属性和特征。聚类是无监督学习的一种方法,是在许多领域使用统计数据分析的常用技术。

  在数据科学中,我们可以使用聚类分析,通过在应用聚类算法时查看数据点落入哪些组,从数据中获得一些有价值的见解。今天,我们将看看数据科学家需要知道的5种流行的聚类算法以及它们的优缺点!

  K均值(K-Means)聚类

  K-Means可能是最知名的聚类算法。它在很多介绍性的数据科学和机器学习课程中都有教过。在代码中很容易理解和实现!可以看看下面的图解说明。

  深度剖析:数据科学家需要了解的5种聚类算法

  1.首先,我们首先选择一些要使用的类|组,并随机初始化他们各自的中心点。计算出使用的类的数量,最好快速查看一下数据,尝试确定任何不同的分组。中心点是与每个数据点矢量长度相同的,在上面的图形中是“X”的形状。

  2.每个数据点通过计算该点与每个组中心之间的距离来进行分类,然后将该点分类到中心与其最接近的组中。

  3.根据这些分类点,重新计算组中的所有向量的均值。

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

  K-Means的优点是速度非常快,因为我们真正在做的是计算点和组中心之间的距离,因为它具有线性复杂度O(n),需非常少的计算。

  另一方面,K-Means有一些缺点。首先,你必须选择有多少组,这并不总是微不足道的,理想情况下,我们希望它使用一个聚类算法来帮助我们,因为它的目的是从数据中获得一些见解。 K-means也从随机选择的聚类中心开始,因此可能在算法的不同运行中产生不同的聚类结果。因此,结果可能不可重复,并且缺乏一致性。其他的集群方法更一致。

  K-Medians是与K-Means相关的另一个聚类算法,除了不是用组的中心点重新计算组的中心点,而是使用组的中值向量。这种方法对异常值不太敏感(因为使用中值),但对于较大的数据集要慢得多,因为在计算中值向量时,每次迭代都需要进行排序。

  Mean-Shift聚类

  Mean-Shift聚类是基于滑动窗口的算法,它试图找到密集的数据点区域。这是一个基于中心的算法,这意味着目标是定位每个组/类的中心点,这通过更新中心点的候选者作为滑动窗口内点的平均值来工作。然后这些候选窗口被过滤到后处理阶段,以消除近似的重复,形成最终的中心点集及其相应的组。可以看一下下面的图解。

  深度剖析:数据科学家需要了解的5种聚类算法

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

  1.为了解释均值偏移,我们将在上面的例子中考虑二维空间中的一组点,如上图所示。我们从一个以C点(随机选择)为中心,以半径r为核心的圆滑动窗口开始。Mean-Shift是一种“爬山算法”,它涉及将这个核迭代地移动到每个步骤的较高密度区域,直到收敛。

  2.在每次迭代中,滑动窗口通过将中心点移动到窗口内的点(因此名称)的平均值而移向较高密度的区域。滑动窗口内的密度与其内部的点数成正比。当然,通过转移到窗口点的平均值,它将逐渐走向高点密度区域。

  3.我们继续根据平均值移动滑动窗口,直到没有方向移位可以容纳更多的内核点。看看上面的图表,我们继续移动这个圆,直到不再增加密度(即窗口中的点数)。

  4.步骤1至步骤3的过程用许多滑动窗口完成,直到所有点位于窗口内。当多个滑动窗口重叠时,保留包含最多点的窗口。然后数据点按其所在的滑动窗口聚集。

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

  深度剖析:数据科学家需要了解的5种聚类算法

  Mean-Shift聚类的整个过程

  与K-means 聚类相比,不需要选择聚类数量,因为均值偏移能自动发现这一点。这是一个巨大的优势。聚类中心向最大密度点聚合的事实也是非常理想的,因为它理解和符合自然数据驱动的意义是非常直观的。缺点是窗口大小/半径“r”的选择可能是不重要的。

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

  DBSCAN是一种基于密度的聚类算法,类似于均值偏移,但具有一些显著的优点。看看下面的另一个图表,让我们开始吧!

  深度剖析:数据科学家需要了解的5种聚类算法

  DBSCAN笑脸集群

  1.DBSCAN从一个没有被访问的任意开始数据点开始。这个点的邻域是利用距离epsilon提取的(ε距离内的所有点都是邻域点)。

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

  3.在这个新集群中第一个点,它的ε距离邻域内的点也成为同一个集群的一部分。这个过程使ε邻域内的所有点属于同一个集群,然后对刚刚添加到组中的所有新点重复该过程。

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

  5.一旦我们完成了当前的集群,一个新的未访问的点被检索和处理,导致发现进一步的集群或噪声。这个过程重复,直到所有点被标记为已访问。由于所有点已经被访问完毕,每个点都被标记为属于一个集群或是噪声。

  与其他聚类算法相比,DBSCAN具有很多优点。首先,它根本不需要固定数量的族群。它还将异常值识别为噪声,不同于均值偏移,即使数据点非常不同,也会将它们简单地引入群集中。另外,它能够很好地找到任意大小和任意形状的族群。

  DBSCAN的主要缺点是,当密度不同时,性能不如其他。这是因为当密度变化时,用于识别邻近点的距离阈值ε和minPoints的设置将随着族群而变化。对于非常高维数据也会出现这种缺点,因为距离阈值ε会变得再次难以估计。

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

  K-Means的主要缺点之一就是它对于聚类中心的平均值进行简单de使用。通过查看下面的图片,我们可以明白为什么这不是最好的方法。在左侧,人眼看起来非常明显,有两个不同半径的圆形星团,以相同的平均值为中心。 K-Means不能处理这个,因为这些集群的平均值是非常接近的。 K-Means在集群不是圆形的情况下也失败了,这是使用均值作为集群中心的结果。  

深度剖析:数据科学家需懂的5种聚类算法
▲K-Means的两个失败案例

  高斯混合模型(GMMs)比K-Means更灵活。对于GMM,我们假设数据点是高斯分布的,这是一个限制较少的假设,而不是用均值来表示它们是循环的。这样,我们有两个参数来描述群集的形状:均值和标准差!以二维为例,这意味着这些集群可以采取任何类型的椭圆形(因为我们在x和y方向都有标准偏差)。因此,每个高斯分布被分配给单个集群。

  为了找到每个群集的高斯参数(例如均值和标准差),我们将使用称为期望最大化(EM)的优化算法。请看下面的图表,作为适合群集的高斯图的例证。然后我们可以继续进行使用GMM的期望最大化聚类过程。

  深度剖析:数据科学家需要了解的5种聚类算法

  1.我们首先选择的数量(如K-Means),然后随机初始化每个集群的高斯分布参数。可以通过快速查看数据来尝试为初始参数提供一个很好的猜测。但需要注意,从上图可以看出,这并不是100%必要的。

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

  3.基于这些概率,我们为高斯分布计算一组新的参数,使得我们最大化群内数据点的概率。我们使用数据点位置的加权来计算这些新参数,其中权重是属于该特定群集的数据点的概率。为了用视觉的方式解释这个,我们可以看看上面的图片,特别是黄色的群集。分布从第一次迭代随机开始,但是我们可以看到大部分黄点都在分布的右侧。当我们计算一个按概率加权的和时,即使中心附近有一些点,它们大部分都在右边。因此,分配的均值自然就会接近这些点。我们也可以看到,大部分要点都是“从右上到左下”。因此,标准偏差改变,以创建一个更适合这些点的椭圆,以最大化概率加权的总和。

  4.步骤2和3重复迭代,直到收敛,分布从迭代到迭代的变化不大。

  使用GMM确实有两个关键的优势。首先,GMM在聚类协方差上比K-Means灵活得多。由于标准偏差参数,集群可以呈现任何椭圆形状,而不是被限制为圆形。K-Means实际上是GMM的一个特殊情况,其中每个群集的协方差在所有维度都接近0。其次,由于GMM使用概率,每个数据点可以有多个群集。因此,如果一个数据点位于两个重叠的集群的中间,我们可以简单地定义它的类,将其归类为1类,Y类归属于2类。例如,GMM支持混合成员。

  凝聚层次聚类

  分层聚类算法实际上分为两类:自上而下或自下而上。自下而上的算法首先将每个数据点视为一个单一的聚类,然后连续地合并(或聚合)成对的聚类,直到所有的聚类都合并成一个包含所有数据点的聚类。因此,自下而上的分层聚类被称为分层凝聚聚类或HAC。这个集群的层次表示为树(或树状图)。树的根是收集所有样本的唯一聚类,叶是仅具有一个样本的聚类。在进入算法步骤之前,请查看下面的图解。

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

深度剖析:数据科学家需要了解的5种聚类算法

  凝聚层次聚类

  1.在每次迭代中,我们将两个集群合并成一个集群。这两个要组合的组被选为那些平均联系最小的组。根据我们选择的距离度量,这两个群集之间的距离最小,因此是最相似的,应该结合起来。

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

  3.分层聚类不需要我们指定聚类的数量,我们甚至可以选择哪个数量的聚类看起来最好,因为我们正在构建一棵“树”。另外,该算法对距离度量的选择不敏感,所有算法都能很好的工作,而与其他聚类算法,距离度量的选择是至关重要的。分层聚类方法的一个特别好的用例是基础数据具有层次结构,并且想要恢复层次结构; 其他聚类算法不能做到这一点。与K-Means和GMM的线性复杂性不同,层次聚类的这些优点是以较低的效率为代价的,因为它具有O(n 3)的时间复杂度。

  深度剖析:数据科学家需要了解的5种聚类算法

标签: 聚类算法
  • IT168企业级IT168企业级
  • IT168文库IT168文库

扫一扫关注

行车视线文章推荐
首页 评论 返回顶部