[机器学习]第九章聚类

2018-09-17 本文已影响0人两全丶

9.1 聚类任务

常见的无监督学习任务

密度估计
异常检测
聚类

聚类任务将数据集划分为若干个不相交的子集，为每一个样本标上一个簇标记(表示这个样本属于哪个簇)，于是得到一个簇标记向量

9.2 性能度量

在开始一项机器学习任务之前，首先必须要定义好性能度量指标，以便量化的评估模型的好坏。

聚类性能度量的基本想法

“物以类聚”，相同簇内的样本应该尽可能的相似；“人以群分”，不同簇内的样本应该经可能的不同。需要定义距离来度量相似性。

两类度量指标

外部指标通过和一个参考模型比较（即和一个专家进行比较）
内部指标不借助任何参考模型

外部指标

假定通过聚类给出的簇划分为 $C = \{C_1...C_K\}$ , 参考模型给出的簇划分为 $C^* = \{C_1^*...C_K^*\}$ , 令 $\lambda$ 与 $\lambda^*$ 分别表示聚类给出的簇标记向量以及参考模型给出的簇标记向量, 定义如下量

其中 $a$ 表示在中属于同一个簇的且在中也属于同一个簇的点对的集合，其他依次类推。显然我们希望 $a$ 和 $b$ 越大越好。

由于一个点对只能出现在一个集合中，共有个点对，所以 $a + b + c + d = \frac{m(m - 1) }{2}$

Jaccard系数

显然当 $a$ 和 $b$ 越大时，该系数越大，直观的表达了聚类性能度量的基本想法

$JC = \frac{a}{a + b + c} = \frac{a}{S - b}$
FM系数

$FMI = \sqrt{\frac{a}{a + b}\frac{a}{a +c}}$
Rand指数

$RI = \frac{2(a + d)}{m(m - 1)}$

内部指标

簇内样本间平均距离

描述簇内的聚合程度

簇内样本间最大距离

描述簇内的聚合程度

簇间样本最小距离

描述两簇之间的距离

两簇间样本中心距离

描述两簇簇之间的距离

DB指数

显然任意两簇样本内平均距离越小，样本中心越远越好，所以DB指数越小越好
Dunn指数

显然任意两簇，簇内最远距离越小，簇间最小距离越大越好，所以该指数越大越好

9.4 原型聚类

此类算法假设聚类结构能够通过一组原型刻画，在聚类任务中较为通用。一般先对原型进行初始化，然后再对原型进行迭代更新求解

9.4.1 k均值算法

给定样本,k均值算法针对聚类所得簇划分最小化平方误差,

$E = \sum^k_{i = 1}\sum_{x \in C_i}||x - \mu_i||^2_2$

E值越小，簇内样本相似程度越高，求解该最优划分为NP难问题，k均值算法采用贪心策略通过迭代优化来近似求解

算法流程

image

可设定最大迭代次数，或的最小更新幅度阈值来防止迭代过久

9.4.2 学习向量量化(Learning Vector Quantization)

LVQ假设数据样本带有类别标记，利用这些监督信息来辅助聚类

算法流程

image

初始化原型向量可如下操作，对第个簇，从类别标记相同的样本中随机选取一个作为原型向量
LVQ根据样本与原型向量的距离来划分簇，因此学得一组原型向量后，就得到了样本空间上的一组划分，称为"Voronoi"划分
学习率越大，每次原型向量更新的幅度就越大
若将簇所对应的划分区域中的样本全用原型向量表示，则可实现数据的有损压缩，称为“向量量化”

9.4.3 高斯混合聚类

k均值和LVQ通过原型向量来刻画聚类结构，而高斯混合聚类通过概率模型来表达聚类原型

高斯分布

由 $n$ 维均值向量和 $n \times n$ 的协方差矩阵决定

高斯混合分布

数据分布由k个高斯成分混合而成，每个高斯分布都有一个混合系数 $\alpha_i$ ,且 $\sum_{i=1}^{k}\alpha_i = 1$ ，则为样本在生成过程中，选择第个高斯分布的概率 $P(z_j = i)$ 对应与 $\alpha_i$

聚类

训练集，令 $z_j \in \{1,2....k\}$ 表示生成样本的高斯混合成分, 设后验概率为 $p_M(z_j = i | x_j)$ , 简记为 $\gamma_{ji}$ 由贝叶斯定义得的后验分布为

image

高斯混合聚类把样本D划分为k个簇（对应k个混合成分），每个样本的簇标记如下确定，选取簇标记后验概率最大的一个做为样本的簇标记,

image

模型参数由EM算法求取

由表达式看，参数通过样本加权平均来估计，权重为每个样本属于该成分的后验概率

算法流程

image

9.5 密度聚类

密度聚类假设聚类结构能通过样本分布的紧密程度确定。

DBSCAN聚类

使用一组“邻域”参数来刻画样本分布的紧密程度,数据集 $D = \{x_1....x_m\}$

$\epsilon$ -邻域

对于样本 $x_j \in D$ , $N_\epsilon = \{x_i \in D | dist(x_i,x_j) \leq \epsilon\}$ , 即与样本之间的距离小于 $\epsilon$ 的样本的集合
核心对象

若 $x_j$ 的 $\epsilon$ -邻域内至少包含个 $MinPts$ 样本，则 $x_j$ 是一个核心对象
密度直达

若 $x_j$ 位于 $x_i$ 的 $\epsilon$ -邻域中，且 $x_i$ 是核心对象，则 $x_j$ 由 $x_i$ 密度直达
密度可达

若存在样本序列 $p_1....p_n$ , 其中 $p_1 = x_i, p_n = x_j$ ,且 $p_{i + 1}$ 由 $p_i$ 密度直达，则 $x_j$ 由 $x_i$ 密度可达

即存在一条路径使得可以到达的 $x_i$ 的 $\epsilon-$ 邻域内
密度相连

若 $x_i$ 与 $x_j$ 存在 $x_k$ , 使的 $x_i$ 与 $x_j$ 均由 $x_k$ 密度可达，则称 $x_i$ 与 $x_j$ 密度相连