Machine Learning

机器学习系列—10.聚类

Contents

  1. 1. 性能度量
    1. 1.1. 外部指标
    2. 1.2. 内部指标
  2. 2. 距离计算
  3. 3. 原型聚类
    1. 3.1. KMeans（k均值算法）
    2. 3.2. 学习向量量化
    3. 3.3. 高斯混合聚类（Mixture-of-Gaussian）
    4. 3.4. 密度聚类
  4. 4. 层次聚类

在“无监督学习”中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律。聚类试图将数据集中的样本划分为若干个通常是不想交的子集，每个子集称为一个“簇”（cluster）。聚类既能作为一个单独过程，用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。其实异常检测（anomaly detection）也常借助聚类或距离计算进行，如将远离所有簇中心的样本作为异常点，获奖密度极低处的样本作为异常点。
基于不同的学习策略，人们设计出多种类型的聚类算法，主要划分及设计到的聚类算法如下：

  1. 原型聚类：
    (1)用原型向量刻画聚类结构：
    a.Kmean
    b.LVQ（学习向量量化）
    (2)概率模型（高斯分布）：GMM（高斯混合模型
  2. 密度聚类（样本分布的紧密程度）：DBSCAN
  3. 层次聚类（树形的聚类结构）：
    (1)“自底向上”的聚合策略：AGNES (2)“自顶向下”的分拆策略：
    本文会先讨论聚类算法涉及到的两个基本问题——性能度量和距离计算，然后对上面涉及到的不同类型的聚类进行介绍。

    性能度量

    通常我们希望聚类结果的“簇内相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低。聚类性能度量大致有两类：一类是将聚类结果与某个“参考模型”（reference model）进行比较，称为“外部指标”（external index）；另一类是直接考查聚类结果而不利于任何参考模型。称为“内部指标”（internal index）

    外部指标


    基于上式导出常用的聚类性能度量外部指标：
    1. Jaccard系数（Jaccard Coefficient，JC）

    2. FM指数（Fowlkes and Mallows Index，FMI）

    3. Rand指数（Rand Index，RI）

    上述三值均在[0,1]区间，值越大越好。

    内部指标


    簇C内样本间的平均距离：

    簇C内样本间最远距离：

    簇Ci与Cj最近样本件的距离

    簇Ci与Cj中心点间的距离：

    基于上式可导出常用的聚类性能度量内部指标：
    1. DB指数（Davies-Bouldin Index，DBI）
    类比簇间相似度

    2. Dunn指数（Dunn Index，DI）
    类比簇内相似度

    DBI的值越小越好，DI相反，越大越好

    距离计算

    “距离度量”需满足一些基本性质：非负性、同一性、对称性、直递性（i到j的距离小于等于i到k与k到j的距离之和）。
    最常用的是“闵可夫斯基距离”（Minkowski distance）

    p=2时，闵可夫斯基距离即欧氏距离（Euclidean distance）

    p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）

    我们常将属性划分为“连续属性”（continuous attribute）（数值属性）和“离散属性”（categorical attribute）（列名属性）。但在讨论距离计算时，属性上是否定义了“序”关系更为重要。能直接在属性值上计算距离的称为“有序属性”，不能直接在属性值上计算距离的称为“无序属性”。显然，闵可夫斯基距离可用于有序属性。
    对无序属性可采用VDM（Value Difference Metric）。令Mu,a表示在属性u上取值为a的样本数，Mu,a,i表示在第i个样本簇中在属性u上取值为a的样本数，k为样本簇数，则属性u上两个离散值a与b之间的VDM距离为：

    将闵可夫斯基距离和VDM结合可处理混合属性。不失一般性，令有序属性排列在无序属性之前，则

    当样本空间中不同属性的重要性不同时，可使用“加权距离”，以加权闵可夫斯基距离为例：通常权值之和为1。

    原型聚类

    原型聚类亦称“基于原型的聚类”（prototype-based clustering）。此类算法假设聚类结构能通过一组原型刻画。原型是指样本空间中具有代表性的点。下面介绍几种著名的原型聚类算法。

    KMeans（k均值算法）

    给定样本集D={x1,x2,…,xm},“k均值”（k-means）算法针对聚类所得簇划分C={C1，C2,…,Ck}最小化平方误差

    最小化式（9.24）并不容易，找到它的最优解需考察样本集D所有可能的簇划分，这是一个NP难问题。k均值算法采用了贪心策略，通过迭代优化来近似求解式。以下是k均值算法描述

    为避免运行时间过长，通常设置一个最大运行轮数或最小调整幅度阈值，若达到最大轮数或调整幅度小于阈值，则停止运行。

    学习向量量化

    与k均值算法类似，“学习向量量化”（Learning Vector Quantization，LVQ）也是试图找到一组原型向量来刻画聚类结构，LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。LVQ算法描述如下：

    首先对原型向量进行初始化，然后对原型向量进行迭代优化，在每一轮迭代中，算法随机选取一个有标记训练样本，找出与其距离最近的原型向量，并根据两者的类别标记是否一致来对原型向量进行更新。LVQ的关键是第6-10行的更新原型向量，对样本Xj，若最近的原型向量pi与Xj的类别标记相同，则令pi向Xj的方向靠。若标签不同，则远离Xj。
    在学得一组原型向量后，即可实现对样本空间X的簇划分。对任意样本x，它将被划入于其距离最近的原型向量所代表的簇中；

    高斯混合聚类（Mixture-of-Gaussian）

    与k均值、LVQ用原型向量来刻画聚类结构不同，高斯混合聚类采用概率模型来表达聚类原型。
    高斯分布的定义，对n维样本空间X中的随机向量x，若x服从高斯分布，其概率密度函数为

    高斯分布完全由均值向量和协方差矩阵这两个参数确定。
    根据概率密度函数可定义高斯混合分布：

    该分布共由k个混合成分组成，每个混合成分对应一个高斯分布。假设样本的生成过程由高斯混合分布给出。令随机变量Zj∈{1,2,…,k}表示生成样本Xj的高斯混合成分，根据贝叶斯定理，Zj的后验分布对应于：

    换言之，PM(Zj=i|Xj)给出了样本Xj由第i个高斯混合成分生成的后验概率，为方便叙述，将其简记为γji(i=1,2,…,k)。当高斯混合分布(9.29)已知时，高斯混合聚类将把样本集D划分为k个簇C={C1,C2,…,Ck},每个样本Xj的簇标记λj如下确定：

    即将样本划分进后验概率最大的那个高斯混合成分。因此，从原型聚类的角度来看，高斯混合聚类是采用概率模型（高斯分布）对原型进行刻画，簇划分则由原型对应后验概率确定。对于式(9.29)模型参数{(αi,μi,Σi)|1≤i≤k}如何求解呢？可以采用极大似然估计，即最大化（对数）似然（这块知识的具体介绍可查看贝叶斯决策理论部分）

    LL（D）是对数似然的期望值。上式常采用EM算法进行迭代优化求解。EM算法步骤在此简要复习一下：
    EM（Expectation-Maximization）算法是常用的估计参数隐变量（隐变量：未观测变量的学名）的利器，它是一种迭代式地方法，基本思想是：若参数θ已知，则可根据训练数据推断出最优隐变量Z的值（E步）；反之，若Z的值已知，则可方便地对参数θ做极大似然估计（M步）。EM算法可看作是一种非梯度优化方法（坐标下降法）。
    简要来说，EM算法使用E步和M步交替计算：
    E步（期望E步）：利用当前估计的参数计算对数似然的期望值
    M步（最大化M步）：寻找能使E步产生的似然期望最大化的参数值
    重复E步、M步直至收敛。
    根据上述的EM算法步骤可得高斯混合模型的EM算法：在每步迭代中，先根据当前参数来计算每个样本属于每个高斯成分的后验概率（E步），再根据更新公式更新模型参数，包括均值向量、协方差矩阵以及新混合系数。具体高斯混合聚类算法步骤如下：

    密度聚类

    密度聚类亦称“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。
    DBSCAN是一种著名的密度聚类算法，它基于一组“领域”（neighborhood）参数来刻画样本分布的紧密程度，给定数据集D，定义如下几个概念：

    下图是上述概念的直观显示：

    ps：
  4. 密度直达关系不满足对称性，因为Xj不一定是另一个e-领域中的核心对象。
  5. 密度可达关系满足直递性，但不满足对称性。
  6. 密度直达、密度可达、密度相连，这三者的紧密性依次递减。

基于这些概念，DBSCAN将“簇”定义为：由密度可达关系导出的最大的密度相连样本集合。形式化地说，给定领域参数(ε,MinPts),簇C∈D满足以下性质的非空样本子集：
连接性（connectivity）：Xi∈C，xj∈C => Xi与Xj密度相连 （9.39）
最大性：Xi∈C，Xj由Xi密度可达 => Xj∈C
于是，DBSCAN算法先任选数据集中的一个核心对象为“种子”（seed），再由此出发确定相应地聚类簇，算法描述如图9.9所示。在第1~7行中，算法先根据给定的领域参数找出所有核心对象；然后再第10~24行中，以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。第23行是若该核心对象包含在其他聚类簇中，则从核心对象集合中去除。

层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚合策略，也可采用“自顶向下”的分拆策略。
AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数，这里的关键是如何计算聚类簇之间的距离。可根据如下式子计算距离：

显然，最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，而平均距离则有两个簇的所有样本共同决定。当聚类簇距离分别由这三个距离计算时，AGNES算法被相应地称为“单链接”（single-linkage）、“全链接”（complete-linkage）或“均链接”（average-linkage）算法。AGNES算法描述如下：