《机器学习》 第九章 聚类

第九章 聚类

9.1 聚类任务

前面讲的都是有监督的任务，对于无标签的数据，我们想要知道数据内在规律。

聚可以将无标签的数据划分成若干个通常是不想交的子集（簇），每个簇可能有一些潜在的概念，如本地瓜、浅色瓜、深色瓜等等，这些概念通常是使用者来命名的。

9.2 性能度量

性能度量既可以评估聚类的好坏，还可以知道聚类过程。

我们希望的是：同一类样本尽可能近，不同类样本尽可能远。也就是簇内相似度高，簇间相似度低。

两类度量模型：外部指标（利用参考模型）和内部指标（不使用参考模型）。

外部指标

声明：

• Jaccard系数：（JC）

$$\begin{align} JC=\frac a {a+b+c} \end{align}$$

• FM指数

$$\begin{align} JC= \sqrt{\frac a {a+b}\frac a {a+c}} \end{align}$$

• Rand指数

$$\begin{align} JC=\frac {2(a+d)} {m(m-1)} \end{align}$$

均在0-1之间，越大越好。

内部指标

声明：

• DB指数（DBI）（越小越好）

$$\begin{align} DBI=\frac 1 k \sum_{i=1}^k{\max_{j\neq i} \left ( \frac {avg(C_i)+avg(C_j)}{d_{cen}(C_i,C_j)} \right) } \end{align}$$

• Dunn指数（DI）（越大越好）

$$\begin{align} DI = \min_{1\leq i\leq k}{\left \{ \min_{j\neq i} (\frac{d_{min}(C_i,C_j)}{\max_{1\leq l\leq k}diam(C_l)}) \right \} } \end{align}$$

9.3 距离计算

距离度量需要满足一些性质：

• 非负性
• 同一性（同一个样本距离为0）
• 对称性（函数交换位置，距离相等）
• 直递性

$$\begin{align} dist(x_i,x_j)\leq dist(x_i,x_k)+dist(x_k,x_j) \end{align}$$

闵可夫斯基距离

$$\begin{align} dist_{mk}(x_i,x_j)=\left ( \sum_{u=1}^n|x_{iu}-x_{ju}|^p \right)^{\frac 1 p} \end{align}$$

类似p范数

曼哈顿距离

p=1

$$\begin{align} dist_{mk}(x_i,x_j)= \sum_{u=1}^n|x_{iu}-x_{ju}| \end{align}$$

欧氏距离

p=2

$$\begin{align} dist_{mk}(x_i,x_j)= \sqrt { \sum_{u=1}^n|x_{iu}-x_{ju}|^2 } \end{align}$$

这些距离可用于有序属性，对于无序属性，可以使用VDM方法。

9.4 原型聚类

对于原型聚类的几种方法，大体思想都是假设能够通过一组原型来刻画，也就是一组向量，一个向量表示一个簇心。

k均值聚类

算法思想：有k个中心，每类样本到中心的平方误差最小化。（思想简单，但是计算不易）

$$\begin{align} E= \sum_{i=1}^k\sum_{x\in C_i}||x-\mu_i||_2^2 \end{align}$$

这是一个NP难问题，于是采用贪心策略，迭代优化。

基本思想：对均值向量初始化，依次对当前簇划分的均值向量迭代更新，若更新后的聚类结果保持不变，则分会结果。

学习向量量化-LVQ【较略】

LVQ的关键是如何更新原型向量。

高斯混合聚类【较略】

高斯混合聚类采用概率模型来表达聚类原型。由若干个高斯分布加权而得：

求解方法为：EM算法。

9.5 密度聚类-DBSCAN【较略】

基于密度的聚类能够根据密度来考察样本的可连接性。DBSCAN是代表性算法。

9.6 层次聚类

层次聚类试图在不同层次上对数据集进行划分，形成树状结构，即可自上而下，也可自下而上。

AGNES是自底向上聚合的代表性算法：先将每个样本当做是一类，然后将距离最近的两类聚合，不断合并，直至达到目标。