聚类算法

聚类是从数据集中挖掘相似观测值集合的方法。聚类试图将数据集中的样本划分为若干个通常是不相交的子集， 每个子集称为一个"簇"(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,\dots ,x_n\}$$

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

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

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

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

其中:

• $C_{l^{{}^{\prime }}}\underset{l^{{}^{\prime }}\ne l}{\cap }{C}_l=\varnothing$
• $D={\cup }_{l=1}^k{C}_l$

相应的, 用

$${\lambda }_i\in \{1,2,\dots ,k\}$$

表示样本 $x_i$ 的"簇标记”(cluster label)，即

$$x_i\in C_{{\lambda }_i}$$

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

$$\lambda =({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_n)$$

聚类性能度量

聚类距离计算

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

• 非负性：$dist(x_i,x_j)⩾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)⩽dist(x_i,x_k)+dist(x_k,x_j)$ (可不满足)

变量特征：

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

闵可夫斯基距离

Minkowski distance

样本:

$$\{\begin{array}{c}{x}_i=(x_{i1},x_{i2},\dots ,x_{ip}),i=1,2,\dots ,n\\ x_j=(x_{j1},x_{j2},\dots ,x_{jp}),i=1,2,\dots ,n\end{array}$$

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

$$dis{t}_{mk}(x_i,x_j)=||x_i-x_j|{|}^q=(\sum _{u=1}^p|x_{iu}-x_{ju}{|}^q{)}^{\frac{1}{q}}$$

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

$$dis{t}_{man}(x_i,x_j)=\parallel x_i-x_j{\parallel }_1=\sum _{u=1}^p|x_{iu}-x_{ju}|$$

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

$$dis{t}_{ed}(x_i,x_j)=\parallel x_i-x_j{\parallel }_2=\sqrt{\sum _{u=1}^p|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 距离为:

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

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

假设有 $p_c$ 个有序特征，$p-p_c$ 个无序特征，有序特征排列在无序特征之前：

$$MinkovD{M}_q(x_i,x_j)=(\sum _{u=1}^{p_c}|x_{i,u}-x_{j,u}{|}^q+\sum _{u=p_c+1}^{p}VD{M}_q(x_{i,u},x_{j,u}){)}^{\frac{1}{q}}$$

加权闵可夫斯基距离

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

$$dis{t}_{wmk}(x_i,x_j)=(w_1\cdot |x_{i1}-x_{j1}{|}^q+w_2\cdot |x_{i2}-x_{j2}{|}^q+\dots +w_n\cdot |x_{in}-x_{jn}{|}^q{)}^{\frac{1}{q}}$$

其中：

• 权重 $w_i⩾0(i=1,2,\dots ,p)$ 表示不同特征的重要性， 通常 ${\sum }_{i=1}^n{w}_i=1$

聚类算法库

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

参考

• 将聚类聚类