聚类分析

概述

聚类是无监督机器学习问题,目标是感知样本间的相似度,进行类别归纳,聚类既可以作为一个单独过程,用于寻找数据内在的分布结构,也可以作为分类、稀疏表示等其他学习任务的前驱过程。

影响聚类结果的因素

  1. 属性选择导致不同结果
  2. 相似性度量是判断样本间、类别间的相似的标准
  3. 聚类规则是样本聚集条件,例如,近邻、损失函数。

相似度度量

样本-样本

样本-集合

集合-集合

集合与集合之间的距离常被称作是类间距离

集合内部样本点之间的距离被称作是类内距离

性能度量

聚类性能的外部指标


聚类性能的内部指标

序贯方法

基本方法

逐一比较单个样本与类簇的相似性,有相似类则归类,无相似类则建立新类。相似性度量采用样本-集合的度量方法。

显然,这是一种简单的,快速算法。缺点体现在需要对所有样本过滤一遍后才知道类别总数,而先出现的样本很有可能找不到合适的类别。

两阶段序贯方法

两阶段序贯方法是把基本的序贯方法拆分成了两个阶段,第一个阶段进行类别的确定、第二个阶段才进行样本的分类。

从算法可以看出,不管是基本的序贯方法还是两阶段的序贯方法,聚类效果都依赖于阈值 $\Theta$,不同的阈值对将会产生不同的聚类结果。

双阈值序贯方法

双阈值序贯方法是对以上两种方法的又一个改进,该方法采用两个阈值,弱化阈值作用,形成灰色带。

  • $if \;\; d(x, C) \lt \Theta_1,\; x \in C$
  • $if \;\; d(x, C) \gt \Theta_2,\; x \in new \; C$
  • $if \;\; \Theta_1 \lt d(x, C) \lt \Theta_2 ,\; take\;place\;at\;later\;stage. $



以上三种算法都有共同的缺点,

  • 当类别一旦产生,不可变,尽管后来类簇增加,类别很相近也无法合并
  • 敏感于样本顺序,样本类别未必是最合适的。

增强算法

增强算法通过对样本集合的合并和重置解决了序贯算法基于顺序的问题。

层次聚类

聚类嵌套

层次聚类策略

类簇之间(依据相似性)不断合并、或不断的分化, 直到满足聚类停止条件,按照顺序可以分为自底向上的归并算法和自顶向下的分化算法。

归并方法

第 $i$ 次迭代:计算所有两个类簇的相似性,归并最相似的两个类簇,更新类别划分 $R_i$,缺点来自计算性能方面,没有归并的类簇间相似性,被重复计算。

对于集合间的距离度量,有最大 $similarity$ 和最小 $dissimilarity$ 两种方法,使用不同的方法产生的聚类结果可能不同。

算法实例

基于矩阵的归并算法利用矩阵记录类簇间的相似性,对于一个合并操作,首先删除对应合并的两行和列 随后增加一个新行和新列来表示新类簇与其他类簇的相似度,解决了重复计算“没有合并的类簇间”相似性的问题。

分化方法

分化方法的过程和归并方法相反,对第 $i$ 次迭代:在所有类簇的所有划分中,计算所有两个类簇相似性,选择最不相似的类簇集合划分,更新类别划分 $R_i$,同样,没有划分的类簇间相似性,也会被重复计算。

我们可以使用同样的矩阵形式来优化分化方法,只需对增加的类簇计算相似度。除此之外,通过算法可以看出,分化方法的另一个复杂度是寻找所有划分方法的过程。

K 均值聚类

$K$ 均值算法又被叫做 $K-means$,和高斯混合聚类都属于原型聚类的范畴,其算法思想是:将样本分给最近的类心,然后重新调整类心;通过多次迭代,逐步进行类别划分。

最优准则为最小化误差平方和,即最小化类内距离:

一般方法

根据最近类心原则, 批量划分后修正类心。一般方法存在的问题是:可能会导致空簇,最小化误差平方和可能并不能达到最好的收敛效果。

改进方法

在聚类结束后,按照单个划分最优原则,对类别 $i$ 中的样本 $y$ 寻找与其最为接近的类。

优缺点及改进

优点

  1. 该算法时间复杂度为 $O(TKMN)$,其中,$T$ 为迭代次数,$K$ 为簇的数目,$M$ 为样本数,$N$ 为维数。所以,对于处理大数据集合,该算法非常高效,且伸缩性较好
  2. 原理简单,实现容易

缺点

  1. 聚类中心的个数 $K$ 需要事先给定,但在实际中这个 $K$ 值的选定是非常难以估计的
  2. 聚类效果受初始聚类中心的影响,不同的初始聚类中心可能导致完全不同的聚类结果,改进有 $K-Means++$
  3. 结果不一定是全局最优,只能保证局部最优
  4. 对噪声和离群点敏感

$\bf K-Means++$

  1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心
  2. 对于数据集中的每一个点 $x$,计算它与最近聚类中心的距离 $D(x)$
  3. 选择 $D(x)$ 较大的点作为新的聚类中心
  4. 重复 $2$ 和 $3$ 直到找到选出 $K$ 个聚类中心
  5. 利用这 $K$ 个初始的聚类中心来运行标准的 $K-Means$ 算法

高斯混合聚类

基本概念



算法过程

密度聚类

基本概念

算法思想


算法过程

  1. 任选一个数据集中的核心对象
  2. 由该核心对象出发,按照密度直达收集同一类簇样本
  3. 在收集的样本中,如果样本是核心对象,则返回 $1$ 继续执行,直到所有的核心对象都被访问过

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] 周志华,《机器学习》,清华大学出版社