[西瓜书]学习笔记八:聚类

“物以类聚,人以群分”

聚类是一种经典的无监督学习方法,无监督学习的目标是通过对无标记训练样本的学习,发掘和揭示数据集本身潜在的结构与规律,即不依赖于训练数据集的类标记信息。聚类则是试图将数据集的样本划分为若干个互不相交的类簇,从而每个簇对应一个潜在的类别。

聚类直观上来说是将相似的样本聚在一起,从而形成一个类簇(cluster)。那首先的问题是如何来度量相似性(similarity measure)呢?这便是距离度量,在生活中我们说差别小则相似,对应到多维样本,每个样本可以对应于高维空间中的一个数据点,若它们的距离相近,我们便可以称它们相似。那接着如何来评价聚类结果的好坏呢?这便是性能度量,性能度量为评价聚类结果的好坏提供了一系列有效性指标。

聚类性能度量

由于聚类算法不依赖于样本的真实类标,就不能像监督学习的分类那般,通过计算分对分错(即精确度或错误率)来评价学习器的好坏或作为学习过程中的优化目标。一般聚类有两类性能度量指标:外部指标和内部指标。

外部指标

将聚类结果与某个参考模型的结果进行比较,以参考模型的输出作为标准,来评价聚类好坏。假设聚类给出的结果为λ,参考模型给出的结果是λ*,则我们将样本进行两两配对,定义:

显然a和b代表着聚类结果好坏的正能量,b和c则表示参考结果和聚类结果相矛盾,基于这四个值可以导出以下常用的外部评价指标:

内部指标

内部指标即不依赖任何外部模型,直接对聚类的结果进行评估,聚类的目的是想将那些相似的样本尽可能聚在一起,不相似的样本尽可能分开,直观来说:簇内高内聚紧紧抱团,簇间低耦合老死不相往来。定义:

基于上面的四个距离,可以导出下面这些常用的内部评价指标:

距离度量

谈及距离度量,最熟悉的莫过于欧式距离了,从年头一直用到年尾的距离计算公式:即对应属性之间相减的平方和再开根号。度量距离还有其它的很多经典方法,通常它们需要满足一些基本性质:

最常用的距离度量方法是“闵可夫斯基距离”(Minkowski distance)

当p为1时,为曼哈顿距离:

当p为2时为欧式距离:

我们知道属性分为两种:连续属性和离散属性(有限个取值)。对于连续值的属性,一般都可以被学习器所用,有时会根据具体的情形作相应的预处理,例如:归一化等;而对于离散值的属性,需要作下面进一步的处理:

  • 若属性值之间存在序关系,则可以将其转化为连续值,例如:身高属性“高”“中等”“矮”,可转化为{1, 0.5, 0}。 若属性值之间不存在序关系,则通常将其转化为向量的形式,例如:性别属性“男”“女”,可转化为{(1,0),(0,1)}。

在进行距离度量时,易知连续属性和存在序关系的离散属性都可以直接参与计算,因为它们都可以反映一种程度,我们称其为“有序属性”;而对于不存在序关系的离散属性,我们称其为:“无序属性”,显然无序属性再使用闵可夫斯基距离就行不通了。

对于无序属性,我们一般采用VDM进行距离的计算,例如:对于离散属性的两个取值a和b,定义:

在计算两个样本之间的距离时,我们可以将闵可夫斯基距离和VDM混合在一起进行计算:

若我们定义的距离计算方法是用来度量相似性,例如下面将要讨论的聚类问题,即距离越小,相似性越大,反之距离越大,相似性越小。这时距离的度量方法并不一定需要满足前面所说的四个基本性质,这样的方法称为:非度量距离(non-metric distance)。

原型聚类

原型聚类即“基于原型的聚类”(prototype-based clustering),原型表示模板的意思,就是通过参考一个模板向量或模板分布的方式来完成聚类的过程,常见的K-Means便是基于簇中心来实现聚类,混合高斯聚类则是基于簇分布来实现聚类。

k-means算法

K-Means的思想十分简单,首先随机指定类中心,根据样本与类中心的远近划分类簇,接着重新计算类中心,迭代直至收敛。但是其中迭代的过程并不是主观地想象得出,事实上,若将样本的类别看做为“隐变量”(latent variable),类中心看作样本的分布参数,这一过程正是通过EM算法的两步走策略而计算出,其根本的目的是为了最小化平方误差函数E:

K-Means的算法流程如下所示:

学习向量量化(LVQ)算法

LVQ也是基于原型的聚类算法,与K-Means不同的是,LVQ使用样本真实类标记辅助聚类,首先LVQ根据样本的类标记,从各类中分别随机选出一个样本作为该类簇的原型,从而组成了一个原型特征向量组,接着从样本集中随机挑选一个样本,计算其与原型向量组中每个向量的距离,并选取距离最小的原型向量所在的类簇作为它的划分结果,再与真实类标比较。

  • 若划分结果正确,则对应原型向量向这个样本靠近一些 若划分结果不正确,则对应原型向量向这个样本远离一些

LVQ算法的流程如下所示:

高斯混合聚类

现在可以看出K-Means与LVQ都试图以类中心作为原型指导聚类,高斯混合聚类则采用高斯分布来描述原型。现假设每个类簇中的样本都服从一个多维高斯分布,那么空间中的样本可以看作由k个多维高斯分布混合而成。

对于多维高斯分布,其概率密度函数如下所示:

其中u表示均值向量,∑表示协方差矩阵,可以看出一个多维高斯分布完全由这两个参数所确定。接着定义高斯混合分布为:

α称为混合系数,这样空间中样本的采集过程则可以抽象为:(1)先选择一个类簇(高斯分布),(2)再根据对应高斯分布的密度函数进行采样,这时候贝叶斯公式又能大展身手了:

此时只需要选择PM最大时的类簇并将该样本划分到其中,看到这里很容易发现:这和那个传说中的贝叶斯分类不是神似吗,都是通过贝叶斯公式展开,然后计算类先验概率和类条件概率。但遗憾的是:这里没有真实类标信息,对于类条件概率,并不能像贝叶斯分类那样通过最大似然法美好地计算出来,因为这里的样本可能属于所有的类簇,这里的似然函数变为:

可以看出:简单的最大似然法根本无法求出所有的参数,这样PM也就没法计算。这里就要召唤出之前的EM大法,首先对高斯分布的参数及混合系数进行随机初始化,计算出各个PM(即γji,第i个样本属于j类),再最大化似然函数(即LL(D)分别对α、u和∑求偏导 ),对参数进行迭代更新。

高斯混合聚类的算法流程如下图所示:

密度聚类

密度聚类则是基于密度的聚类,它从样本分布的角度来考察样本之间的可连接性,并基于可连接性(密度可达)不断拓展疆域(类簇)。其中最著名的便是DBSCAN算法,首先定义以下概念:

简单来理解DBSCAN便是:找出一个核心对象所有密度可达的样本集合形成簇。首先从数据集中任选一个核心对象A,找出所有A密度可达的样本集合,将这些样本形成一个密度相连的类簇,直到所有的核心对象都遍历完。DBSCAN算法的流程如下图所示:

层次聚类

层次聚类是一种基于树形结构的聚类方法,常用的是自底向上的结合策略(AGNES算法)。假设有N个待聚类的样本,其基本步骤是:

  • 1.初始化—>把每个样本归为一类,计算每两个类之间的距离,也就是样本与样本之间的相似度;
  • 2.寻找各个类之间最近的两个类,把他们归为一类(这样类的总数就少了一个);
  • 3.重新计算新生成的这个类与各个旧类之间的相似度;
  • 4.重复2和3直到所有样本点都归为一类,结束。

层次聚类法的算法流程如下所示: