第九章：聚类

1. 聚类任务

2. 性能度量

3. 距离计算

4. 原型聚类

4.1 k均值算法

4.2 学习向量量化

4.3 高斯混合聚类

5. 密度聚类

6. 层次聚类

二、实验

1. K-means算法

2. DBSCAN

3. 层次聚类

1. 聚类任务

监督学习	无监督学习
分类	聚类
回归	密度估计
类	簇

在“无监督学习”任务中研究最多、应用最广
目标:将数据样本划分为若干个通常不相交的“簇”既可以作为一个单独过程（用于找寻数据内在的分布结构)也可作为分类等其他学习任务的前驱过程

2. 性能度量

性能度量：评估好坏

物以类聚：同一簇的样本尽可能彼此相似,不同簇的样本尽可能不同.（聚类结果的“簇内相似度”高且“簇间相似度”低.）
两类聚类性能度量：

一类是将聚类结果与某个“参考模型”进行比较,称为“外部指标”;
一类是直接考察聚类结果而不利用任何参考模型,称为“内部指标”.

集合SS是参考模型和聚类中处于同一簇的样本;

集合SD是聚类中以属于同一簇，但在参考模型中不是同一簇的样本，公式如下：

$a=|SS|,SS=\left \{ (x_i,x_j)|\lambda _i=\lambda _j,\lambda _i^*=\lambda _j^*,i<j \right \}$

$b=|SD|,SD=\left \{ (x_i,x_j)|\lambda _i=\lambda _j,\lambda _i^*\neq \lambda _j^*,i<j \right \}$

聚类性能度量外部指标：

Jaccard系数：

$JC=\frac{a}{a+b+c}$

FM指数：

$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$

Rand指数：

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

值越大，性能越好

样本间的平均距离：

$avg(C)=\frac{2}{|C|(|C)-1}\sum_{1\leqslant i<j\leqslant |C|}dist(x_i,x_j)$

样本间的最远距离：

$diam(C)=max_{1\leqslant i<j\leqslant |C|}dist(x_i,x_j)$

2个簇间最近样本的距离：

$d_{min}(C_i,C_j)=min_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)$

2个簇中心点的距离：

$d_{cen}(C_i.C_j)=dist(u_i,u_j)$

聚类性能度量内部指标：

DB指数：

$DBI=\frac{1}{k}\sum_{i=1}^{k}max_{j\neq i}(\frac{avg(C_i)+avg(C_j)}{d_{cen}(u_i,u_j)})$

Dunn指数：

$DI=min_{1\leqslant i\leqslant k}\left \{ min_{j\neq i}(\frac{d_{min}(C_i,C_j)}{max_{1<i<k}diam(C_i)}) \right \}$

DBI的值越小越好,而DI 则相反,值越大越好.

3. 距离计算

距离度量需满足的基本性质:

非负性
同一性
对称性
直递性

常用的距离形式：

闵可夫斯基距离：

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

p=2,欧氏距离
p=1，曼哈顿距离

对无序属性，可使用VDM：令 $m_{u,a}$ 表示属性u上取值为α的样本数，表示在第i个样本簇中在属性u上取值为α的样本数，k 为样本簇数，则属性u 上两个离散值α与b之间的VDM距离

$VDM_p(a,b)=\sum_{i=1}^{k}|\frac{m_{u,a,i}}{m_{u,a,i}}-\frac{m_{u,b,i}}{m_{u,b}}|^p$

对混合属性，可使用MinkovDM：

$MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^{n}VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}$

相似度度量: 基于某种形式的距离来定义,距离越大,相似度越小．

相似度度量的距离未必一定要满足距离度量的所有基本性质,尤其是直递性

例如,“人”和“人马”相似，“马”也和“人马”相似，但“人”和“马”却不相似，这破坏了直递性，如下图所示：

4. 原型聚类

亦称“基于原型的聚类”(prototype-based clustering)
假设:聚类结构能通过一组原型刻画
过程:先对原型初始化，然后对原型进行迭代更新求解
代表:k均值聚类,学习向量量化(LvQ)，高斯混合聚类

4.1 k均值算法

最小平方误差：

$E=\sum_{i=1}^{k}\sum_{x\in C_{i}}||x-\mu_{i}||_{2}^{2} ,$

E值越小则簇内样本相似度越高.

取最小值：考察样本集D所有可能的簇划分

采用：贪心策略,通过迭代优化来近似求解式．

假定聚类簇数k = 3,算法开始时随机选取三个样本作为初始均值向量,即u1,u2,u3
考察样本x1与当前均值向量u1,u2,u3的距离,选择距离最小的，将其划入相应簇中.类似的,对数据集中的所有样本考察一遍后,可得当前簇划分
再求三个簇的均值向量
更新当前均值向量后,不断重复上述过程
迭代产生的结果相同,于是算法停止,得到最终的簇划分.

如下图所示：

4.2 学习向量量化

与一般聚类算法不同的是,LVQ假设数据样本带有类别标记,学习过程利用样本的这些监督信息来辅助聚类.

LVQ关键在于如何更新原型向量，若最近的原型向量 $p_i*$ 与 $x_j$ 的类别标记相同,新原型向量如下所示：

$p^{\prime}=p_{i^{*}}+\eta\cdot(x_{j}-p_{i^{*}}) ,$

距离为：

$\begin{aligned} \|\boldsymbol{p}^{\prime}-\boldsymbol{x}_{j}\|_{2}& =||p_{i^{*}}+\eta\cdot(\boldsymbol{x}_{j}-\boldsymbol{p}_{i^{*}})-\boldsymbol{x}_{j}||_{2} \\ &=(1-\eta)\cdot||p_{i^{*}}-x_{j}||_{2} . \end{aligned}$

令学习率 $\eta$ ∈ (0,1)，则原型向量 $p_i*$ 在更新为p'之后将更接近 $x_j$ .

类似的,若 $p_i*$ 与 $x_j$ 的类别标记不同,则更新后的原型向量与 $x_j$ 之间的距离将增大为(1＋ $\eta$ )·ll $p_i*$ - $x_j$ l2,从而更远离 $x_j$ .

样本会被划入距离最近的原型向量所在的簇。每个样本与最近的原型向量的距离不大于其他原型向量，

$R_{i}=\{\boldsymbol{x}\in\mathcal{X}\mid||\boldsymbol{x}-\boldsymbol{p}_{i}||_{2}\leqslant||\boldsymbol{x}-\boldsymbol{p}_{i^{\prime}}||_{2}, i^{\prime}\neq i\} .$

由此形成了对样本空间X的簇划分{R1, R2,.. . , Rq}，该划分通常称为“Voronoi剖分”(Voronoi tessellation).

过程如下所示：

4.3 高斯混合聚类

高斯聚类：采用概率模型来表达聚类原型.

概率密度函数：

$p(\boldsymbol{x})=\frac{1}{(2\pi)^{\frac{n}{2}}|\boldsymbol{\Sigma}|^{\frac{1}{2}}} e^{-\frac{1}{2}(\boldsymbol{x}-\boldsymbol{\mu})^{\mathrm{T}}\boldsymbol{\Sigma}^{-1}(\boldsymbol{x}-\boldsymbol{\mu})} ,$

其概率函数记为：p(x|u, $\sum$ )

高斯混合分布：

$p_{\mathcal{M}}(\boldsymbol{x})=\sum_{i=1}^{k}\alpha_{i}\cdot p(\boldsymbol{x}\mid\mu_{i},\Sigma_{i}) ,$

假设样本的生成过程由高斯混合分布给出:

首先,根据 $\alpha _1,\alpha _2,...\alpha _k$ 定义的先验分布选择高斯混合成分,其中αi为选择第i个混合成分的概率;
然后,根据被选择的混合成分的概率密度函数进行采样,从而生成相应的样本.
使用得到的样本，使用EM算法。

EM算法：

在每步迭代中,先根据当前参数来计算每个样本属于每个高斯成分的后验概率 $\gamma _{ji}$ (E步)，
再更新模型参数{( $\alpha _i,u_i,\sum_i$ )| 1≤i≤k}(M步).

如下图所示：

5. 密度聚类

亦称“基于密度的聚类”(density-based clustering)

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

过程:从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇

代表:DBSCAN,OPTICS, DENCLUE

DBSCAN：基于一组“领域”参数来刻画样本分布的紧密程度

相关概念：

$\epsilon$ -邻域:对 $x_j$ ∈ D,其c-邻域包含样本集D中与 $x_j$ 的距离不大于 $\epsilon$ 的样本,即 $N_{\epsilon}(\boldsymbol{x}_{j})=\{\boldsymbol{x}_{i}\in D\mid\mathrm{dist}(\boldsymbol{x}_{i},\boldsymbol{x}_{j})\leqslant\epsilon\};$
核心对象(core object):若 $x_j$ 的 $\epsilon$ -邻域至少包含MinPts个样本，即 $N_{\epsilon}(\boldsymbol{x}_{j})$ ≥ MinPts，则 $x_j$ 是一个核心对象;
密度直达(directly density-reachable):若 $x_j$ 位于 $x_i$ 的 $\epsilon$ -邻域中,且 $x_j$ 是核心对象，则称 $x_j$ 由 $x_i$ 密度直达;
密度可达(density-reachable):对 $x_i$ 与 $x_j$ ,若存在样本序列p1,P2,... , Pn，其中p1= $x_i$ , Pn = $x_j$ 且p+1由pi密度直达,则称 $x_j$ 由 $x_i$ 密度可达;
密度相连(density-connected):对 $x_i$ 与 $x_j$ ,若存在 $x_k$ 使得 $x_i$ 与 $x_j$ 均由k密度可达,则称 $x_i$ 与 $x_j$ 密度相连.

概念如下图所示：

DBSCAN的簇：由密度可达关系导出的最大的密度相连样本集合.

满足下列性质：

连接性(connectivity): $x_i$ ∈ C, $x_j$ ∈C→ $x_i$ 与 $x_j$ 密度相连
最大性(maximality): $x_i$ ∈ C, $x_j$ 由 $x_i$ 密度可达→ $x_j$ ∈ C

聚类簇：若x为核心对象，由x密度可达的所有样本组成的集合记为X = {x'∈ Dlx'由x密度可达}

DBSCAN算法：

先任选数据集中的一个核心对象为“种子”(seed),
再由此出发确定相应的聚类簇

如下图所示：

6. 层次聚类

假设:能够产生不同粒度的聚类结果

过程:在不同层次对数据集进行划分，从而形成树形的聚类结构

代表:AGNES(自底向上)，DIANA(自顶向下)

AGNES：

它先将数据集中的每个样本看作一个初始聚类簇,
然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，
该过程不断重复,直至达到预设的聚类簇个数.

每个簇是一个样本集合,只需采用关于集合的某种距离即可.

最小距离： $\begin{aligned} &d_{\operatorname*{min}}(C_{i},C_{j})=\operatorname*{min}_{\boldsymbol{x}\in C_{i},\boldsymbol{z}\in C_{j}}\operatorname{dist}(\boldsymbol{x},\boldsymbol{z}) \\ & \\ &\end{aligned}$
最大距离： $d_{\max}(C_{i},C_{j})=\max_{x\in C_{i},\boldsymbol{z}\in C_{j}}\mathrm{dist}(\boldsymbol{x},\boldsymbol{z})$
平均距离： $d_{\mathrm{avg}}(C_{i},C_{j})=\frac{1}{|C_{i}||C_{j}|}\sum_{\boldsymbol{x}\in C_{i}}\sum_{\boldsymbol{z}\in C_{j}}\mathrm{dist}(\boldsymbol{x},\boldsymbol{z}) .$

最小距离由两个簇的最近样本决定,

最大距离由两个簇的最远样本决定,

平均距离则由两个簇的所有样本共同决定．

如下图所示：

二、实验

1. K-means算法

算法步骤

初始化：随机选择 K 个数据点作为初始簇中心。
分配：将每个数据点分配给最近的簇中心。
更新：重新计算每个簇的中心（即簇内所有点的均值）。
迭代：重复步骤 2 和 3 直到簇中心不再发生变化或达到预设的迭代次数

import numpy as np
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt# 创建一个示例数据集
X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0)# 使用K均值算法进行聚类
kmeans = KMeans(n_clusters=4)
kmeans.fit(X)# 获取簇中心和簇分配结果
centers = kmeans.cluster_centers_
labels = kmeans.labels_# 绘制聚类结果
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.scatter(centers[:, 0], centers[:, 1], marker='o', s=200, color='red')
plt.show()

2. DBSCAN

一种基于密度的聚类算法，特别适用于具有噪声的数据集和能够发现任意形状簇的情况。它不需要事先指定簇的数量，能有效处理异常点。

算法步骤

标记所有点为核心点、边界点或噪声点。
删除噪声点。
为剩余的核心点创建簇，如果一个核心点在另一个核心点的邻域内，则将它们放在同一个簇中。
将每个边界点分配给与之关联的核心点的簇。

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
import matplotlib.pyplot as plt# 创建示例数据集
X, _ = make_moons(n_samples=200, noise=0.1)# 使用DBSCAN算法进行聚类
dbscan = DBSCAN(eps=0.2, min_samples=5)
labels = dbscan.fit_predict(X)# 绘制聚类结果
plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis')
plt.title('DBSCAN Clustering')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.show()

3. 层次聚类

步骤：

将所有数据样本整体当成一个初始簇；
在所有簇中挑出具有最大直径的簇；
找出所挑簇里与其它数据样本平均相异度最大的一个数据样本放入splinter group，剩余的放入old party中；
在old party里找出到splinter group中数据样本的最近距离不大于到old party 中数据样本的最近距离的数据样本，并将该数据样本加入splinter group；
循环step2到step4直到没有新的old party数据样本分配给splinter group；
splinter group和old party为被选中的簇分裂成的两个簇，与其他簇一起组成新的簇集合。

from sklearn import datasets
from sklearn.cluster import AgglomerativeClustering
import matplotlib.pyplot as plt
from sklearn.metrics import confusion_matrix
import pandas as pd
iris = datasets.load_iris()
irisdata = iris.data
clustering = AgglomerativeClustering(linkage='ward', n_clusters= 4)
res = clustering.fit(irisdata)
print ("各个簇的样本数目：")
print (pd.Series(clustering.labels_).value_counts())
print ("聚类结果：")
print (confusion_matrix(iris.target, clustering.labels_))
plt.figure()
d0 = irisdata[clustering.labels_ == 0]
plt.plot(d0[:, 0], d0[:, 1], 'r.')
d1 = irisdata[clustering.labels_ == 1]
plt.plot(d1[:, 0], d1[:, 1], 'go')
d2 = irisdata[clustering.labels_ == 2]
plt.plot(d2[:, 0], d2[:, 1], 'b*')
d3 = irisdata[clustering.labels_ == 3]
plt.plot(d3[:, 0], d3[:, 1], 'c.')
plt.xlabel("Sepal.Length")
plt.ylabel("Sepal.Width")
plt.title("AGNES Clustering")
plt.show()