《机器学习》-- 第九章 聚类
正文共：4100 字 预计阅读时间：11 分钟
前文推送
本文目录：
- 9.1 聚类任务
- 9.2 性能度量
- 9.3 距离度量
- 9.4 原型聚类
- 9.5 密度聚类
- 9.6 层次聚类
- 9.7 应用问题
第九章 聚类算法
9.1 聚类任务
聚类是一种经典的无监督学习(unsupervised learning)方法，无监督学习的目标是通过对无标记训练样本的学习，发掘和揭示数据集本身潜在的结构与规律，即不依赖于训练数据集的类标记信息。
聚类试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个“簇”( cluster)。通过这样的划分,每簇可能对应于一些潜在的概念(类别),如“浅色瓜”“深色瓜”,“有籽瓜”“无籽瓜”,甚至“本地瓜”“外地瓜”等;需说明的是,这些概念对聚类算法而言事先是未知的,聚类过程仅能自动形成簇结构, 簇所对应的概念语义需由使用者来把握和命名。
聚类既能作为一个单独过程,用于找寻数据内在的分布结构,也可作为分类等其他学习任务的前驱过程。例如,在一些商业应用中需对新用户的类型进行判别,但定义“用户类型”对商家来说却可能不太容易,此时往往可先对用户数据进行聚类,根据聚类结果将每个簇定义为一个类,然后再基于这些类训练分类模型,用于判别新用户的类型。
直观上来说，聚类是将相似的样本聚在一起，从而形成一个类簇（cluster）。涉及两个问题
- 如何度量相似性（similarity measure），这便是距离度量(distance measure)，在生活中我们说差别小则相似，对应到多维样本，每个样本可以对应于高维空间中的一个数据点，若它们的距离相近，我们便可以称它们相似。
- 如何评价聚类结果，这便是性能度量(validity index)
9.2 性能度量
由于聚类算法不依赖于样本的真实类标，就不能像监督学习的分类那般，通过计算分对分错（即精确度或错误率）来评价学习器的好坏或作为学习过程中的优化目标。
直观上看,我们希望“物以类聚”,即同一簇的样本尽可能彼此相似,不同簇的样本尽可能不同换言之,聚类结果的“簇内相似度”( intra-cluster similarity)高且“簇间相似度” inter-cluster similarity)低
聚类性能度量有两类
- “外部指标”(external index)：将聚类结果与某个“参考模型”(reference model)进行比较
- “内部指标”( internal index)：直接考察聚类结果而不利用任何参考模型
9.2.1 外部指标
即将聚类结果与某个参考模型(比如领域专家给出的划分结果)的结果进行比较，以参考模型的输出作为标准，来评价聚类好坏。
对数据集
，假设经过聚类后得到的簇划分为
, ，参考模型给出的簇划分为
,(通常k≠s)， 相应的，令
和
分别表示
和
对应的簇标记向量(类结果)，我们将样本两两配对考虑，可定义
显然a和d代表着聚类结果好坏的正能量，b和c则表示参考结果和聚类结果相矛盾，由于每个样本对仅能出现在一个集合中，因此有 a+b+c+d = m(m-1)/2
基于a,b,c,d这四个值可以导出以下常用的外部评价指标：
- Jaccard系数(Jaccard Coefficient，简称 JC)
- FM系数(Fowlkes and Mallows Index，简称FMI)
- Rand指数(Rand Index，简称RI)
JC, FMI, RI 的取值范围都在[0,1]，数值越大则聚类效果越好。
9.2.2 内部指标
内部指标不依赖任何外部模型，直接对聚类的结果进行评估：簇内高内聚紧紧抱团，簇间低耦合易分离。考虑聚类结果的簇划分
, 定义：
其中，
用于计算两个样本间的距离，
代表簇 C 中心点。基于上面的四个距离，可以导出下面这些常用的内部评价指标：
- DB指数(Davies-Bouldin Index，简称DBI)(越小越好)
它刻画的是: 给定两个簇,每个簇样本之间平均值之和比上两个簇的中心点之间的距离作为度量。然后考察该度量对所有簇的平均值。显然 DBI 越小越好。如果每个簇样本之间的平均值越小(即簇内样本距离都很近),则 DBI 越小;如果簇间中心点的距离越大(即簇间样本距离相互都很远),则 DBI 越小
- Dunn指数(Dunn Index，简称DI)(越大越好)
它刻画的是:任意两个簇之间最近的距离的最小值, 除以任意一个簇内距离最远的两个点的距离的最大值。DI 越大越好。如果任意两个簇之间最近的距离的最小值越大(即簇间样本距离相互都很远),则 DI 越大;如果任意一个簇内距离最远的两个点的距离的最大值越小(即簇内样本距离都很近),则 DI 越大。
- 轮廓系数(Silhouette Coefficient)(越大越好)
轮廓系数( Silhouette coefficient)适用于实际类别信息未知的情况。对于单个样本, a是它与它同类别中其他样本的平均距离, b是与它距离最近不同类别中样本的平均距离。对于一个样本集合, 它的轮廓系数是所有样本轮廓系数的平均值。
轮廓系数取值范围是[-1,1]，同类别样本越距离相近且不同类别样本距离越远,分数越高。
簇内内聚度高意味着a越小，簇间耦合低意味着b越大，簇间越容易区分，则s越趋近于1；反之则簇间不容易区分。
轮廓系数的缺点在于对于突形簇其值会高于其他形状簇形，简单来说就是轮廓系数更适用于KMeans算法适用的场景。
9.3 距离度量
9.3.1 距离度量的基本性质
最熟悉的距离度量莫过于欧式距离：即对应属性之间相减的平方和再开根号。度量距离还有其它的很多经典方法，通常它们需要满足一些基本性质：
最常用的距离度量方法是“闵可夫斯基距离”（Minkowski distance)：
当p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）：
当p=2时，闵可夫斯基距离即欧氏距离（Euclidean distance）：
9.3.2 距离度量的选择
我们知道属性分为两种：连续属性(continuous attribute)和离散属性（catergorical attribute有限个取值）。对于连续值的属性，一般都可以被学习器所用，有时会根据具体的情形作相应的预处理，例如：归一化等；而对于离散值的属性，需要作下面进一步的处理：
若属性值之间存在序关系(ordinal attribute)，则可以将其转化为连续值，例如：身高属性“高”“中等”“矮”，可转化为{1, 0.5, 0}。 若属性值之间不存在序关系(non-ordinal attribute)，则通常将其转化为向量的形式，例如：性别属性“男”“女”，可转化为{（1,0）,（0,1）}。
连续属性和存在序关系的离散属性都可以直接参与计算，而不存在序关系的无序属性，我们一般采用VDM（Value Difference Metric）进行距离的计算，例如：令
表示在属性
上取值为
的样本数,
表示在第
个样本簇中在属性 u 上取值为
的样本数, k 为样本簇数, 则属性
上两个离散值
与
之间的 VDM 距离为：
VDM距离刻画的是属性取值在各簇上的频率分布之间的差异。
在计算两个样本之间的距离时，假定有 n~c~ 个有序属性、n-n~c~个无序属性,不失一般性,令有序属性排列在无序属性之前, 则我们可以将闵可夫斯基距离和VDM混合在一起进行计算：
需注意的是,通常我们是基于某种形式的距离来定义“相似度度量”( similarity measure),距离越大,相似度越小。然而,用于相似度度量的距离未必一定要满足距离度量的所有基本性质,尤其是直递性。
例如在某些任务中我们可能希望有这样的相似度度量:“人”“马”分别与“人马”相似,但“人”与“马”很不相似;要达到这个目的,可以令“人”“马”与“人马”之间的距离都比较小,但“人”与“马”之间的距离很大,此时该距离不再满足直递性;这样的距离称为“非度量距离”(non- metric distance)。
non-metric distance
在现实任务中,有必要基于数据样本来确定合适的距离计算式, 这可通过“距离度量学习”( distance metric learning)来实现。
9.4 原型聚类
原型聚类即“基于原型的聚类”（prototype-based clustering），原型表示模板的意思，就是通过参考一个模板向量或模板分布的方式来完成聚类的过程，通常情形下算法先对原型进行初始化,然后对原型进行迭代更新求解。采用不同的原型表、不同的求解方式,将产生不同的算法。
常见的K-Means便是基于簇中心（原型向量）来实现聚类，混合高斯聚类则是基于簇分布（概率模型）来实现聚类。
9.4.1 K-Means
K-Means的思想十分简单，首先随机指定类中心，根据样本与类中心的远近划分类簇，接着重新计算类中心，迭代直至收敛。但是其中迭代的过程并不是主观地想象得出，事实上，若将样本的类别看做为“隐变量”（latent variable）,类中心看作样本的分布参数，这一过程正是通过EM算法的两步走策略而计算出，其根本的目的是为了最小化平方误差函数E：
K-Means的算法流程如下所示：
kmeans_algorithm.png
9.5 密度聚类
密度聚类是基于密度的聚类（density-based clustering），它从样本分布的角度来考察样本之间的可连接性，并基于可连接性（密度可达）不断拓展疆域（类簇）。其中最著名的便是DBSCAN算法，首先定义以下概念：
对于给定数据集
简单来理解DBSCAN：找出一个核心对象所有密度可达的样本集合形成簇。首先从数据集中任选一个核心对象A，找出所有A密度可达的样本集合，将这些样本形成一个密度相连的类簇，直到所有的核心对象都遍历完。DBSCAN算法的流程如下图所示：
9.6 层次聚类
层次聚类(hierarchical clustering)是一种基于树形结构的聚类方法，常用的是自底向上的结合策略（AGNES算法, AGglomerative NESting），另外还有自顶向下的拆分策略（Divisive Analysis）。假设有N个待聚类的样本，其基本步骤是：
1.初始化-->把每个样本归为一类，计算每两个类之间的距离，也就是样本与样本之间的相似度； 2.寻找各个类之间最近的两个类，把他们归为一类（这样类的总数就少了一个）； 3.重新计算新生成的这个类与各个旧类之间的相似度； 4.重复2和3直到所有样本点都归为一类，结束。
可以看出其中最关键的一步就是计算两个类簇的相似度，这里有多种度量方法：
* 单链接（single-linkage）:取类间最小距离。
* 全链接（complete-linkage）:取类间最大距离
* 均链接（average-linkage）:取类间两两的平均距离
很容易看出：单链接的包容性极强，全链接则是坚持到底，只要存在缺点就坚决不合并，均连接则是从全局出发顾全大局。
层次聚类法的算法流程如下所示：
9.7 应用问题
传统的聚类算法已经比较成功的解决了低维数据的聚类问题。但是由于实际应用中数据的复杂性，在处理许多问题时，现有的算法经常失效，特别是对于高维数据和大型数据的情况：
①高维数据集中存在大量无关的属性使得在所有维中存在簇的可能性几乎为零；
②高维空间中数据较低维空间中数据分布要稀疏，其中数据间距离几乎相等是普遍现象，而传统聚类方法是基于距离进行聚类的，因此在高维空间中无法基于距离来构建簇。
本文项目地址：
https://github.com/firewang/lingweilingyu/blob/master/contents/Machine_Learning_Zhi-Hua_Zhou.md
(喜欢的话，Star一下)
参考网址：
- 周志华 著. 机器学习, 北京: 清华大学出版社, 2016年1月.
- https://github.com/Vay-keen/Machine-learning-learning-notes
零维领域，由内而外深入机器学习
dive into machine learning
微信号：零维领域
英文ID：lingweilingyu