机器学习之聚类

聚类

一、聚类任务

聚类是一种经典的无监督学习方法，无监督学习的目标是通过对无标记训练样本的学习，发掘和揭示数据集本身潜在的结构与规律，即不依赖于训练数据集的类标记信息。
聚类试图将数据集的样本划分为若干个互不相交的子集，每个子集称为一个簇（cluster）,从而每个簇对应一个潜在的类别。

二、性能度量

聚类性能度量也称聚类“有效性指标”（validity index）。对聚类结果，我们需要通过某种性能度量来衡量其好坏。另一方面，若明确了最终要使用的性能度量，则可将其作为聚类过程的优化目标，从而更好得到符合要求的聚类结果。

直观上看，我们希望“物以类聚”，即同一簇的样本尽可能相似，不同簇的样本尽可能不同。换言之，聚类结果的“簇类相似度”（intra-cluster similarity）高且“簇间相似度”（inter-cluster similarity）低。

聚类性能度量大致有两类：

• 外部指标（external index）：将聚类结果与某个参考模型（reference model）进行比较。
• 内部指标（internal index）：直接考察聚类结果而不利用任何参考模型。

1.外部指标

对数据集$D=\{x_1,x_2,...,x_m\}$，假设通过聚类给出的簇划分为$C=\{C_1,C_2,...,C_k\}$，参考模型给出的簇划分为$C^{\ast }=\{C_1^{\ast },C_2^{\ast },...,C_k^{\ast }\}$。相应地，令$\lambda$与${\lambda }^{\ast }$分别表示$C$和$C^{\ast }$对应的簇标记向量，将样本两两配对考虑，定义：

其中集合$SS$包含了在$C$中隶属与相同簇且在$C^{\ast }$也隶属与相同簇的赝本对，集合$SD$包含了在$C$中隶属与相同簇但在$C^{\ast }$隶属于不同簇的样本对…

2.内部指标

考虑聚类结果的簇划分$C=\{C_1,C_2,...,C_k\}$，定义

基于上面的四个距离，可以导出下面这些常用的内部指标：

三、距离计算

对函数$dist(\cdot ,\cdot )$，若它是一个距离度量（distance measure），则需满足一些基本性质：

• 非负性：$dist(x_i,x_j)\ge 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)\le dist(x_i,x_k)+dist(x_k,x_j)$

给定样本，最常用的是“闵可夫斯基距离”（Minkowski distance）
$$dis{t}_{mk}(x_i,x_j)=(\sum _{u=1}^n|x_{iu-x_{ju}}{|}^p{)}^{\frac{1}{p}}$$
p=2时，闵可夫斯基距离即欧式距离（Euclidean distance）
$$dis{t}_{ed}(x_i,x_j)=||x_i-x_j||=(\sum _{u=1}^n|x_{iu-x_{ju}}{|}^2{)}^{\frac{1}{2}}$$
p=1时，闵可夫斯基距离即曼哈顿距离（Manhattan distance）
$$dis{t}_{man}(x_i,x_j)=||x_i-x_j||=\sum _{u=1}^n|x_{iu-x_{ju}}|$$

四、原型聚类

原型聚类即“基于原型的聚类”（prototype-based clustering）。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解，采用不同的原型表示，不同的求解方式将产生不同的算法。

4.1 k均值聚类

K-Means的思想是首先随机指定类中心，根据样本与类中心的远近划分类簇，接着重新计算类中心，迭代直至收敛。
k均值算法针对聚类划分$C=\{C_1,C_2,...C_K\}$最小化平方误差：
$$E=\sum _{i=1}^k\sum _{x\in C_i}||x-{\mu }_i|{|}_2^2$$
K-Means的算法流程如下所示：

五、层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用自底向上的聚合策略，也可采用自顶向下的分拆策略。

AGNES是一种采用自底向上聚合策略的层次聚类算法，先将每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数。

关键是如何计算聚类簇之间的距离，可通过下面式子计算：
$$\begin{gathered} 最小距离：d_{min}(C_i,C_j)=min(dist(x,z)),x\in C_i,z\in C_j \\ 最大距离：d_{max}(C_i,C_j)=max(dist(x,z)),x\in C_i,z\in C_j \\ 平均距离：d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{x\in C_i}\sum _{x\in C_j}dist(x,z) \end{gathered}$$

• 最小距离：由两个簇最近样本决定
• 最大距离：由两个簇最远样本决定
• 平均距离：由两个簇最所有样本共同决定

当聚类簇聚类由$d_{min}、d_{max}、d_{avg}$计算时，AGENS算法被相应称为单连接（single-linkage）、全连接（complete-linkage）、均连接（average-linkage）