53b52b4373758f98ff4581f0c47dfd89
聚类算法(下)

0、前言

聚类算法上中讲了大名鼎鼎的K-Means算法及其优化变种,在这篇中几种讲述两位两种不同思路的聚类算法。

1、层聚类算法

1.1、传统层聚类算法—AGNES和DIANA算法

层次聚类和K-Means的思路不太一样,它的思路有点像是决策树,按照层次进行分解,知道满足某种条件为止,传统的层次聚类分为自底而上,和自上而下两类:

  • 凝聚的层次聚类:
    这类算法是采用采用自底向上的策略,其中的代表便是AGNES算法(AGglomerative Nesting),它的核心思想是:最初将每个对象作为一个簇,然后这些簇根据某些准则被一步一步合并,两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定。聚类的合并过程反复进行直到所有的对象满足簇数目。
  • 分裂的层次聚类:
    和凝聚的层次聚类相反,这种是采用自顶向下的策略,代表算法为DIANA算法(Divisive Analysis)。其核心思想是:首先将所有对象置于一个簇中,然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式 距离),直到达到某个终结条件(簇数目或者簇距离达到阈值)。

在AGNES算法中都提到了,簇是根据某些原则进行分裂或者合并的,而这个原则就是簇间距离。计算簇间距离的方法有最小距离(SL聚类),最大距离(CL聚类)以及平均距离(AL聚类),具体的说明如下:

  • 最小距离(SL聚类)
    选择两个聚簇中最近的两个样本之间的距离(Single/Word-Linkage)
    注:得到的模型容易形成链式结构
  • 最大距离(CL聚类)
    选择两个聚簇中最圆的两个眼本的距离(Complete-Linkage)
    注:如果出现了异常值的话,那他们的构建很容易受这个异常值的影响。
  • 平均距离(AL聚类)
    选择两个聚类中的平均值(Average-Linkage聚类算法)或者中值(Median-Linkage聚类法)

AGNES和DIANA算法优缺点如下:

  1. 简单,理解容易。
  2. 合并点/分裂点选择不太容易。
  3. 合并/分类的操作不能进行撤销。
  4. 由于执行效率较低$O(t*n^2)$,$t$为迭代次数,$n$为样本点数。

1.2、层次聚类优化算法

之前我们看到了传统的层次聚类算法,由于其执行效率太低,且不能动构建的的特点,显然不适合大数据集。于是我们在此基础上引入了BIRCH算法CURE算法

BIRCH算法

BIRCH (balanced iterative reducing and clustering using hierarchies) 算法,英文的全称翻译过来以后是平衡迭代削减聚类算法,其构成和我们考研数据结构中学过的B+树非常的类似,甚至很多特性都是相同的,具体的说它构建的树叫做CF(Cluster Feature)-Tree。

  1. 节点,即簇的结构:
    既然是树,那么就不得不提它的节点的结构了。在BIRCH构建CF树的过程中,每个节点等于说是存放了它之下所有节点的特征,于是他在节点中存放了如下的三部分数据。
    • N,指在这个节点中有多少个样本点。
    • LS,指的是这个节点中的样本相应特征的和。
    • LS,指的是这个节点中的样本相应特征的特征的平方和。
  2. 节点之间,节点和子节点,以及叶子结点之间的关系
    节点和其子节点是包含的关系,也就是父节点中的N,LS以及SS是其所有子节点的和。而相应的样本点的具体信息指包含在底层节点中(叶子结点的子节点),同时叶子结点构成一个单项链表,同时有一个指针指向其表头。这点的特性是同B+树高度一致的
  3. 最多子女个数,以及分裂判定
    和B+树一样,对于树构建中的分叉个数是有限制的,这个限制需要提前给出,即分支因子。同时,值得注意的是,一般而言在构建节点簇的中心点的时候,一般选用第一个进入这个节点的样本点作为中心点,然后根据指定的该簇和中心点限定的距离,即类直径,其往往通过LS和SS算出。判断新入的点是否可以划入该簇,而分裂节点的时候,往往以这个初始点进行分割。
    综上我们可以看出,BIRCH算法的本质其实就是动态的插入样本点,然后动态的根据规则构建一个类B+树。它的优点是动态建树且效率高是线性效率,即每个样本点都是一次性插入的,同时也节省内存,所以非常适合大数据集。不过遗憾的是它也是采用距离作为分类标准,故只适合分布呈凸形或者球形的数据集、且需要给定聚类个数和簇之间的相关参数,而这些对节点CF的限制可能导致簇类结果和真实不太一致
  • 注1:BIRCH不依赖给定的待分类簇数量K,但是给定了K值最好,若不一定K值,最终CF-Tree的叶子结点树木就是最终分类的簇的数目。
  • 注2:BIRCH算法在训练大规模数据集的时候,和mini-batch K-Means相比,BIRCH算法更加适合类别数量K比较多的情况。
  • 注3:由于类直径是通过LS和SS算出的,所以当特征维度超过20~30左右的时候,不建议使用该算法。

CURE算法(使用代表点的聚类法)

CURE(Clustering Using REpresentatives),该算法先把每个数据点看成一类,然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是:取消了使用所有点,或用中心点+距离来表示一个类,而是从每个类中抽取固定数量、 分布较好的点作为此类的代表点,并将这些代表点乘以一个适当的收缩因子,使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景,而且收缩因子的使用可以减少噪音对聚类的影响

CURE算法的优点是能够处理非球形分布的应用场景,同时彩娱乐随机抽样和分区的方式可以提高算法的执行效率。

2、密度聚类算法

密度聚类方法的指导思想是:只要样本点的密度大于某个阀值,则将该样本添加到最近的簇中。这类算法可以克服基于距离的算法只能发现凸聚类的缺点,可以发现任意形状的聚类,而且对噪声数据不敏感。不过这种计算的复杂度高,计算量大。
密度聚类算法的常用算法有DBSCAN密度最大值算法

2.1、DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise),将簇定义为密度相连的点的最大集合,能够将足够高密度的区域划分为簇,并且在具有噪声的空间数据上能够发现任意形状的簇。其核心思路是用一个点的ε邻域内的邻居点数衡量该点所在空间的密度,该算法可以找出形状不规则的cluster,而且聚类的时候事先不需要给定cluster的数量。

DBSCAN算法流程

它的算法流程如下:

  • 如果一个点$x$的$\varepsilon$领域内包含m个对象,则创建一个x作为核心对象的新簇。
top Created with Sketch.