聚类算法

聚类是从数据集中挖掘相似观测值集合的方法。聚类试图将数据集中的样本划分为若干个通常是不相交的子集， 每个子集称为一个"簇"(cluster)。通过这样的划分，每个簇可能对应于一些潜在的概念(类别)。 聚类过程仅能自动形成簇结构，簇所对应的概念语义需由使用者自己来把握。 聚类既能作为一个单独的过程用于寻找数据内在的分布结构，也可以作为分类等其他学习任务的前驱过程

角度 I:

• 基于原型、质心、中心的聚类 (Prototype-based Clustering)
  • K-Means 聚类 (K-Means)
  • 学习向量量化聚类 (Learning Vector Quantization)
• 基于分布的聚类
  • 高斯混合模型聚类 (Gaussian Mixture Model)
• 基于密度的聚类 (Density-based Clustering)
  • DBSCAN (Density-Based Spatial Clustering of Application with Noise)
  • OPTICS (Ordering Points To Identify the Clustering Structure)
• 基于连通性的聚类、层次聚类 (Hierarchical Clustering)
• 基于模型的聚类 (Model-based Clustering)
  • 混合回归模型 (Mixture Regression Model)
• 基于图论的聚类
  • 亲和力传播 (Affinity propagation)
• 其他聚类方法
  • 谱聚类
  • Chameleon
  • Canopy
  • …

聚类算法比较：

基于原型的聚类

基于原型的聚类(Prototype-based Clustering) 假设聚类结构能通过一组原形刻画。 通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解， 采用不同的原型表示，不同的求解方式，将产生不同的算法

常见的基于原型的聚类有：

• K 均值聚类(K-Means)
• 学习向量量化聚类(Learning Vector Quantization)
• 高斯混合聚类(Mixture-of-Gaussian)

基于密度的聚类

基于密度的聚类(Density-based Clustering) 假设聚类结构能通过样本分布的紧密程度确定。 密度聚类算法从样本密度的角度来考察样本之间的可连续性，并基于可连续样本不断扩展聚类簇以获得最终的聚类结果

常见的基于密度的聚类有：

• DBSCAN(Density-Based Spatial Clustering of Application with Noise)
• OPTICS(Ordering Points To Identify the Clustering Structure)

层次聚类算法

层次聚类(Hierarchical Clustering) 也称为基于连通性的聚类。 这种算法试图在不同层次对数据进行划分，从而形成树形的聚类结构

数据集的划分采用不同的策略会生成不同的层次聚类算法：

• “自底向上” 的聚合策略
  • AGNES(Agglomerative Nesting)
• “自顶向下” 的分拆策略

基于模型的聚类

• 混合回归模型

其他聚类算法

• 谱聚类
• Chameleon
• Canopy
• …

聚类数据

假定样本集 $D$ 包含 $n$ 个无标记样本:

$$D = \{x_1, x_2, \ldots, x_n\}$$

每个样本是一个 $p$ 维特征向量:

$$x_i=(x_{i1}; x_{i2}; \ldots; x_{ip}), i=1,2,\ldots, n$$

聚类算法将样本集 $D$ 划分为 $k$ 个不相交的簇:

$$\{C_l|l=1, 2, \ldots, k\}$$

其中:

• $C_{l^{'}} \underset{l^{'} \neq l}{\cap} C_{l} = \emptyset$
• $D=\cup_{l=1}^{k}C_{l}$

相应的, 用

$$\lambda_{i} \in \{1, 2, \ldots, k\}$$

表示样本 $x_{i}$ 的"簇标记”(cluster label)，即

$$x_{i} \in C_{\lambda_{i}}$$

于是，聚类的结果可用包含 $n$ 个元素的簇标记向量表示

$$\lambda=(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n})$$

聚类性能度量

聚类距离计算

距离度量(distance measure)函数 $dist(,)$ 需满足的基本性质：

• 非负性：$dist(x_{i}, x_{j}) \geqslant 0$
• 同一性：$dist(x_{i}, x_{j})=0$ 当且仅当 $x_{i}=x_{j}$
• 对称性：$dist(x_{i}, x_{j})=dist(x_{j}, x_{i})$
• 直递性：$dist(x_{i}, x_{j}) \leqslant dist(x_{i}, x_{k}) + dist(x_{k}, x_{j})$ (可不满足)

变量特征：

• 连续特征
  • 闵可夫斯基距离
• 离散特征
  • 有序特征: 闵可夫斯基距离
  • 无序特征: VDM(Value Difference Metric)
• 混合特征
  • 闵可夫斯基距离与 VDM 混合距离

闵可夫斯基距离

Minkowski distance

样本:

$$\begin{cases} x_{i}=(x_{i1}, x_{i2}, \ldots, x_{ip}),i=1,2,\ldots, n \\ x_{j}=(x_{j1}, x_{j2}, \ldots, x_{jp}),i=1,2,\ldots, n \end{cases}$$

• $q \geqslant 1$：闵可夫斯基距离(Minkowski distance)

$$dist_{mk}(x_{i}, x_{j})=||x_{i} - x_{j}||^{q} = \bigg(\sum_{u=1}^{p}|x_{iu}-x_{ju}|^{q}\bigg)^{\frac{1}{q}}$$

• $q=1$：曼哈顿距离(Manhattan distance)

$$dist_{man}(x_{i}, x_{j})=\|x_{i}-x_{j}\|_{1}=\sum^{p}_{u=1}|x_{iu}-x_{ju}|$$

• $q=2$：欧氏距离(Euclidean distance)

$$dist_{ed}(x_{i}, x_{j})=\|x_{i}-x_{j}\|_{2}=\sqrt{\sum^{p}_{u=1}|x_{iu}-x_{ju}|^{2}}$$

VDM

VDM，Value Difference Metric，值差异指标

令 $m_{u,a}$ 表示在特征 $u$ 上取值为 $a$ 的样本数， $m_{u, a, i}$ 表示在第 $i$ 个样本簇中在特征 $u$ 上取值为 $a$ 的样本数， $k$ 为样本簇数，则特征 $u$ 上两个离散值 $a$ 与 $b$ 之间的 VDM 距离为:

$$VDM_{q}(a, b)=\sum^{k}_{i=1}\bigg|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}\bigg|^{q}$$

闵可夫斯基距离与 VDM 混合距离

假设有 $p_{c}$ 个有序特征，$p-p_{c}$ 个无序特征，有序特征排列在无序特征之前：

$$MinkovDM_{q}(x_{i}, x_{j})=\bigg(\sum^{p_{c}}_{u=1}|x_{i,u}-x_{j,u}|^{q}+\sum^{p}_{u=p_{c}+1}VDM_{q}(x_{i,u},x_{j,u})\bigg)^{\frac{1}{q}}$$

加权闵可夫斯基距离

当样本在空间中不同特征的重要性不同时：

$$dist_{wmk}(x_{i}, x_{j})=(w_{1}\cdot|x_{i1}-x_{j1}|^{q}+w_{2}\cdot|x_{i2}-x_{j2}|^{q}+\ldots+w_{n}\cdot|x_{in}-x_{jn}|^{q})^{\frac{1}{q}}$$

其中：

• 权重 $w_{i}\geqslant 0(i=1, 2, \ldots, p)$ 表示不同特征的重要性， 通常 $\sum_{i=1}^{n}w_{i}=1$

聚类算法库

• sklearn
  • sklearn.cluster
  • sklearn.feature_extraction
  • sklearn.metrics.pairwise