第九章 聚类

9.1 聚类任务

• 无监督学习（unsupervised learning）中，训练样本的标记信息未知。
  • 目的：通过对无标记训练样本的学习来揭示数据的内在性质及规律
• 聚类：试图将数据集中的样本划分为若干个通常是不想交的子集。
  • 每个子集称为一个“簇”。
  • 每个簇可能对应于一些潜在的概念类别。对于聚类算法而言事先是未知的。
• 假定样本集$D={(x_1,x_2,…,x_m)}$包含$m$个无标记样本，每个样本$x_i=(x_{i1};x_{i2};…;x_{im})$是一个$n$维特征向量，聚类算法将样本集$D$划分为$k$个不想交的簇${C_l\mid l=1,2,…,k}$，其中$C_{l’}\bigcap_{l’\neq l}C_l=\emptyset$，且$D=\bigcup_{l=1}^kC_l$。相应地，我们用$\lambda_j\in{1,2,…,k}$表示样本$x_j$的“簇标记”（cluster label），即$x_i\in C_{\lambda_j}$。聚类的结果可以用包含$m$个元素的簇标记向量$\lambda=(\lambda_1;\lambda_2;…;\lambda_m)$表示。
• 聚类既能作为一个单独过程，用于找寻数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。

9.2 性能度量

• 聚类性能度量亦称“有效性指标”（validity index）。
• 聚类结果的“簇内相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低
• 聚类性能度量大致分两类：
  • 将聚类结果与某个“参考模型”（reference model）进行比较，称为“外部指标”（external index）
  • 直接考察聚类结果而不利用任何参考模型，称为“内部指标”（internal index）
• 对数据集$D={x_1,x_2,…,x_m}$，假定通过聚类给出的簇划分为$C={C_1,C_2,…,C_k}$，参考模型给出的划分簇划分为$C^{\ast}={C_1^{\ast},C_2^{\ast},…,C_s^{\ast}}$。相应地，令$\lambda$与$\lambda^{\ast}$分别表示与$C$和$C^{\ast}$对应的簇标记向量。将样本两两配对考虑。定义：
  • $a=\lvert SS\rvert,SS={(x_i,x_j)\mid\lambda_i=\lambda_j,\lambda_i^{\ast}=\lambda_j^{\ast};i<j}$
  • $b=\mid SD\mid,SD={(x_i,x_j)\mid\lambda_i=\lambda_j,\lambda_i^{\ast}\neq\lambda_j^{\ast};i<j}$
  • $c=\lvert DS\rvert,DS={(x_i,x_j)\mid\lambda_i\neq\lambda_j,\lambda_i^{\ast}=\lambda_j^{\ast};i<j}$
  • $d=\lvert DD\rvert,DD={(x_i,x_j)\mid\lambda_i\neq\lambda_j,\lambda_i^{\ast}\neq\lambda_j^{\ast};i<j}$
  • 其中集合$SS$包含了在$C$中隶属于相同簇且在$C^\ast$中也隶属于相同簇的样本对，集合$SD$包含了在$C$中隶属于相同簇但在$C^\ast$中隶属于不同簇的样本对。
  • 每个样本对$(x_i,x_j)(i<j)$仅能出现在一个集合中，因此$a+b+c+d=m(m-1)/2$
• 常用的聚类性能度量外部指标：[0,1]之间，越大越好

• 考虑聚类结果的簇内划分$C={C_1,C_2,…,C_k}$，定义：
  • $avg(C)=\frac2{\lvert C\rvert(\lvert C\rvert-1)}\sum_{1\leq i<j\leq\lvert C\rvert}dist(x_i,x_j)$
    • 对应于簇$C$内样本间的平均距离
  • $diam(C)=max_{1\leq i<j\leq\lvert C\rvert}dist(x_i,x_j)$
    • 对应于簇$C$内样本间的最远距离
  • $d_{min}(C_i,C_j)=min_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)$
    • 对应于簇$C_i$与簇$C_j$最近样本间的距离
  • $d_{cen}(C_i,C_j)=dist(\mu_i,\mu_j)$
    • $d_{cen}(C_i,C_j)$对应于簇$C_i$与簇$C_j$中心点的距离
    • $dist(·,·)$用于计算两个样本样本之间的距离；
    • $\mu$代表簇$C$的中心点$\mu=\frac1{\lvert C\rvert}\sum_{1\leq i\leq \lvert C\rvert}x_i$
• 常用的聚类性能度量内部指标

9.3 距离计算

• 对函数$dist(·,·)$，如果它是一个“距离度量”(distance measure)，则满足一些基本性质：
  • 非负性：$dist(x_i,x_j)\geq 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)\leq dist(x_i,x_k)+dist(x_k,x_j)$
• 给定样本$x_i=(x_{i1},x_{i2},…,x_{in})$与$x_j=(x_{j1},x_{j2},…,x_{jn})$，最常用的是“闵可夫斯基距离”（Minkowski distance）：$dist_{mk}(x_i,x_j)=(\sum_{u=1}^n\mid x_{iu}-x_{ju}\mid^p)^{\frac1p}$
  • 对$p\geq 1$，上式满足基本性质；
  • $p=2$时，闵可夫斯基距离即欧氏距离（Euclidean distance）：$dist_{ed}(x_i,x_j)=\lVert x_i-x_j\rVert_2=\sqrt{\sum_{u=1}^n\lvert x_{iu}-x_{ju}\rvert^2}$
  • $p=1$时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）：$dist_{man}(x_i,x_j)=\lVert x_i-x_j\rVert_1=\sum_{u=1}^n\lvert x_{iu}-x_{ju}\rvert$
• 属性分类：
  • 连续属性（continuous attribute）：在定义域上有无穷多个取值
  • 离散属性（categorical attribute）：在定义域上有限个取值
• 有序属性
  • 可以用闵可夫斯基距离
• 无序属性
  • VDM（Value Difference Metric）。
• 将闵可夫斯基距离和VDM结合可以处理混合属性。
• 通常基于某种形式的距离来定义“相似度度量”（similarity measure）
  • 距离越大，相似度越小。
  • 用于相似度度量的距离未必一定满足距离度量的所有基本属性。（尤其是直递性）
  • 不满足直递性的距离称为“非度量距离”（non-metric distance）

9.4 原型聚类

• 原型聚类亦称“基于原型的聚类”（prototype-based clustering），此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常见。
• 算法先对原型进行初始化，然后对原型进行接待更新求解。

9.4.1 k均值算法

• 给定样本集$D={x_1,x_2,…,x_m}$，k均值（k-means）算法针对聚类所得簇划分$C={C_1,C_2,…,C_k}$最小化平方误差：$E=\sum_{k=1}^k\sum_{x\in C_i}\lVert x-\mu_i\rVert_2^2$
  • $\mu_i=\frac1{\lVert C_i\rVert}\sum_{x\in C_i}x$是簇$C_i$的均值向量。
  • $E$值越小，簇内样本相似度越高。
  • 找到最优解需要考察样本集$D$所有可能的簇划分，是一个NP难的问题。

9.4.2 学习向量量化

• “学习向量量化”（Learning Vector Quantization，简称LVQ）：试图找到一组原型向量来刻画聚类结构。
• LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。
• 给定样本集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，每个样本$x_j$是由$n$个属性描述的特征向量$(x_{j1};x_{j2};…;x_{jn})$，$y_i\in Y$是样本$x_j$的类别标记。
• LVQ的目标是学得一组$n$维原型向量${p_1,p_2,…,p_n}$，每个原型向量代表一个聚类簇，簇标记$t_i\in Y$。

9.4.3 高斯混合聚类

• 采用概率模型来表达聚类原型
• 高斯分布定义：对$n$维样本空间$X$中的随机向量$x$，若$x$服从高斯分布，其概率密度函数为$p(x)=\frac1{(2\pi)^{\frac n2}\lvert\sum\rvert^\frac12}e^{-\frac12(x-\mu)^T\sum^{-1}(x-\mu)}$
  • $\mu$是$n$维均值向量
  • $\sum$是$n\times n$的协方差矩阵
• 定义高斯混合分布$p_M(x)=\sum_{i=1}^k\alpha_i·p(x\mid\mu_i,\sum_i)$
  • 该分布由$k$个混合成分组成，每个混合成分对应一个高斯分布。
  • $\mu_i$与$\sum_i$是第$i$个高斯混合成分的参数。
  • $\alpha_i>0$为相应的“混合系数”（mixture coefficient），$\sum_{i=1}^k\alpha_i=1$

9.5 密度聚类

• 密度聚类亦称“基于密度的聚类”（density-based clustering）：假设聚类结构能通过样本分部的紧密程度确定。
• DBSCAN算法：基于一组“邻域”（neighborhood）参数$(\epsilon,MinPts)$来刻画样本分部的紧密程度。
• 给定数据集$D={x_1,x_2,…,x_m}$，定义以下几个概念：
  • $\epsilon-$邻域：对$x_j\in D$，其$\epsilon-$邻域包含样本集$D$中与$x_j$的距离不大于$\epsilon$的样本，即$N_{\epsilon}(x_j)={x_j\in D\mid dist(x_i,x_j)\leq\epsilon}$；
  • 核心对象（core object）：若$x_j$的$\epsilon-$邻域至少包含$MinPts$个样本，即$\lvert N_{\epsilon}(x_j)\rvert\geq MinPts$，则$x_j$是一个核心对象；
  • 密度直达（directly density-reachable）：若$x_j$位于$x_i$的$\epsilon-$邻域中，且$x_i$是核心对象，则称$x_j$由$x_j$密度直达；
  • 密度可达（density-reachable）：对$x_i$与$x_j$，若存在样本序列$p_1,p_2,…,p_n$，其中$p_1=x_i,p_n=x_j$且$p_{i+1}$由$p_i$密度直达，则称$x_j$由$x_i$密度可达；
  • 密度相连（density-connected）：对$x_i$与$x_j$，若存在$x_k$使得$x_i$与$x_j$均由$x_k$密度可达，则称$x_i$与$x_j$密度相连。

• DBSCAN将“簇”定义为：由密度可达关系导出的最大密度相连样本集合。
• 给定邻域参数$(\epsilon,MinPts)$，簇$C\subseteq D$是满足以下性质的非空样本子集：
  • 连接性（connectivity）：$x_i\in C$，$x_j\in C\Rightarrow x_i$与$x_j$密度相连
  • 最大性（maximality）：$x_i\in C$，$x_j$由$x_i$密度可达$\Rightarrow x_j\in C$
• 若$x$为核心对象，由$x$密度可达的所有样本组成的集合标记为$X={x’\in D\mid x’$由$x$密度可达}

9.6 层次聚类

• 层次聚类（hierarchical clustering）在不同层次对数据集进行划分，从而形成树形的聚类结构。
• AGNES：采用自底向上聚合策略的层次聚类算法，先将数据集中的每个样本看做一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，不断重复该过程，直至达到预设的聚类簇个数。
• 给定聚类簇$C_i$与$C_j$：
  • 最小距离：$d_{min}(C_i,C_j)=\mathop{min}\limits_{x\in C_i,z\in C_j}dist(x,z)$
  • 最大距离：$d_{max}(C_i,C_j)=\mathop{max}\limits_{x\in C_i,z\in C_j}dist(x,z)$
  • 平均距离：$d_{avg}(C_i,C_j)=\frac1{\lvert C_i\rvert\lvert C_j\rvert}\sum_{x\in C_i}\sum_{z\in C_j}dist(x,z)$

• Previous
  第八章 集成学习
• Next
  第十章 降维与度量学习