聚类算法

聚类的基本概念

相似度和距离

闵可夫斯基距离

在聚类中，可将样本集合看作是向量空间中点的集合，以该空间的距离表示样本之间的相似度。常用距离有闵可夫斯基距离，特别是欧氏距离。闵可夫斯基距离越大，相似度越小

定义：给定样本集合矩阵 \(X\)，\(X\) 是 \(m\) 维实数向量空间中点的集合，其中 \(x_i,x_j \in X\)，\(x_i = (x_{1i},x_{2i},...,x_{mi})^T\)，样本\(x_i,x_j\)的闵可夫斯基距离定义为 \[ d_{ij} = (\sum_{k = 1}^{m}{|x_{ki} - x_{kj}|}^p)^{\frac{1}{p}} \] 这里 \(p \geq 1\)，当 \(p = 2\) 时称为欧氏距离，\(p = 1\) 时称为曼哈顿距离， \(p = \infty\) 时称为切比雪夫距离，取各个坐标数值差的绝对值的最大值，即 \[ d_{ij} = {max}_{k} |x_{ki} - x_{kj}| \]

马哈拉诺比距离

马哈拉诺比距离简称马氏距离，是另一种常用的相似度，考虑各个分量(特征)之间的相关性并与各个分量的尺度无关。马哈拉诺比距离越大，相似度越小

定义：给定一个样本集合矩阵 \(X\)，其协方差矩阵记为 \(S\)。样本 \(x_i\) 和样本 \(x_j\) 之间的马哈拉诺比距离 \(d_{ij}\) 定义为： \[ d_{ij} = [(x_i - x_j)^TS^{-1}(x_i - x_j)]^{\frac{1}{2}} \] 其中， \[ \begin{align*} x_i &= (x_{1i},x_{2i},...,x_{mi})^T \\ x_j &= (x_{1j},x_{2j},...,x_{mj})^T \\ \end{align*} \]

容易看出当 \(S\) 为单位阵时，马哈拉诺比距离就是欧氏距离，所以马氏距离也是欧氏距离的推广

相关系数

样本之间的相似度也可以用相关系数表示。相关系数越接近1表示越相似；相关系数越接近0表示越不相似

定义：样本 \(x_i\) 和 \(x_j\) 之间的相关系数定义为 \[ r_{ij} = \frac{\sum_{k = 1}^m(x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j)}{[\sum_{k = 1}^m(x_{ki} - \bar{x}_i)^2 \sum_{k = 1}^m(x_{kj} - \bar{x}_j)^2]^{\frac{1}{2}}} \] 其中， \[ \begin{align*} \bar{x}_i &= \frac{1}{m}\sum_{k = 1}^{m}x_{ki} \bar{x}_j &= \frac{1}{m}\sum_{k = 1}^{m}x_{kj} \end{align*} \]

夹角余弦

样本之间的相似度也可以用夹角余弦来表示。夹角余弦越接近1，表示样本越相似；越接近0，表示样本越不相似 定义：样本 \(x_i\) 和 \(x_j\) 之间的夹角余弦定义为 \[ s_{ij} = \frac{\sum_{k = 1}^{m}x_{ki}x_{kj}}{(\sum_{k = 1}^{m}x_{ki}^2\sum_{k = 1}^{m}x_{kj}^2)^{\frac{1}{2}}} \]

由上述定义可见，用距离度量相似度时，距离越小样本越相似；用相关系数度量时，相关系数越大样本越相似。注意不同相似度度量得到的结构并不一定一致

类或簇

通过聚类得到类或簇的本质是样本的子集，如果一个聚类方法假定一个样本只能属于一个类或类的交集为空集，那么成为硬聚类方法；否则称为软聚类方法。此处我们只讨论硬聚类方法，聚类的方法有多种，在此我们列举一种最常见的定义，且由该种定义可推出其他的定义方法

定义；设 \(T\) 为给定的正数，若对于集合 \(G\) 种任意两个样本 \(x_i,x_j\)，有 \[ d_{ij} \leq T \] 则称 \(G\) 为一个类或簇 其中 \(d_{ij}\) 表示样本 \(x_i,x_j\) 之间的距离

类的特征可以通过不同角度来刻画，常用的有以下三种： 1. 类的均值 \(\bar{x}_{G}\)，又称类的中心 \[ \bar{x}_{G} = \frac{1}{n_{G}}\sum_{i = 1}^{n_G}x_i \] 其中 \(n_G\) 表示类 \(G\) 的样本数量 2. 类的直径 \(D_G\)，其表示类种任意两个样本之间的最大距离，即 \[ D_G = \mathop{max}_{x_i,x_j \in G}d_{ij} \] 3. 类的样本散布矩阵 \(A_{G}\) 与样本协方差矩阵 \(S_G\) 类的样本散布矩阵 \(A_G\) 为 \[ A_G = \sum_{i = 1}^{n_G}(x_i - \bar{x}_G)(x_i - \bar{x}_G)^T \] 样本协方差矩阵 \(S_G\) 为 \[ \begin{align*} S_G &= \frac{1}{n_G - 1}A_G \\ &= \frac{1}{n_G - 1}\sum_{i = 1}^{n_G}(x_i - \bar{x}_G)(x_i - \bar{x}_G)^T \end{align*} \]

类与类之间的距离

下面考虑类 \(G_p\) 与类 \(G_q\) 之间的距离 \(D(p,q)\)，也称为连接。类与类之间的距离也有多种定义。

设类 \(G_p\) 包含 \(n_p\) 个样本， \(G_q\) 包含 \(n_q\) 个样本，分别用 \(\bar{x}_p\) 和 \(\bar{x}_q\) 表示 \(G_p\) 和 \(G_q\) 的均值，即类的中心 1. 最短距离或单连接 定义类 \(G_p\) 的样本与类 \(G_q\) 的样本之间的最短距离为两类之间的距离 2. 最长距离或完全连接 定义类 \(G_p\) 的样本与类 \(G_q\) 的样本之间的最长距离为两类之间的距离 3. 中心距离 定义类 \(G_p\) 的样本与类 \(G_q\) 的中心 \(\bar{x}_p\) 和 \(\bar{x}_q\) 之间的距离为两类之间的距离 4. 平均距离 定义类 \(G_p\) 的样本与类 \(G_q\) 任意两个样本之间距离的平均值为两类之间的距离

层次聚类

层次聚类假设类别之间存在层次结构，将样本聚到层次化的类中。层次聚类又有聚合和分裂两种方法，由于每个样本只属于一个类，所以层次聚类属于硬聚类。

我们在这里介绍聚合聚类的方法，其具体过程如下：对于给定的样本集合，开始将每个样本分到一个类；然后按照一定规则(eg: 类间距离最小)，将最满足规则条件的两个类进行合并；如此反复进行，每次减少一个类，直到满足停止条件，如所有样本聚为一类

由此可知，聚合聚类需要预先确定下面三个要素： 1. 距离/相似度 2. 合并规则 3. 停止条件

根据要素的不同组合，就可以构成不同的聚类方法。(距离/相似度的选取；合并规则是哪种类之间距离；停止条件的选取)

在这里我们介绍一种特定的聚合聚类算法 算法： 输入： \(n\) 个样本组成的样本集合及样本之间的距离 输出：对样本集合的一个层次化聚类

1. 计算 \(n\) 个样本两两之间的欧氏距离\(\{d_{ij}\}\)，记作矩阵 \(D = [d_{ij}]_{n \times n}\)
2. 构造 \(n\) 个类，每个类只包含一个样本
3. 合并类间距离最小的两个类，其中最短距离为类间距离，构架你个新类
4. 计算新类与当前各类的距离。若类的个数为1，停止计算；否则回到步骤3

k均值聚类

k均值聚类是基于样本集合划分的聚类算法。k均值聚类将样本集合划分为k个子集，构成k个类，将n个样本分到k个类中，每个样本到其所属类的中心的距离最小。每个样本只能属于1个类，所以k均值聚类是硬聚类。下面我们介绍k均值聚类算法

策略

k均值聚类归结为样本集合 \(X\) 的划分，或者从样本到类的函数的选择问题。k均值聚类的策略是通过最小化损失函数来选取最优的划分函数 \(C^*\)

首先，采取欧氏距离平方作为样本之间的距离 \[ \begin{align*} d(x_i,x_j) &= \sum_{k = 1}^{m}(x_{ki} - x_{kj})^2 \\ &= ||x_i - x_j||^2 \end{align*} \] 然后定义样本与其所属类的中心之间的距离总和为损失函数 \[ \begin{align*} W(C) = \sum_{l = 1}^{k}\sum_{C(i) = l}||x_{i} - \bar{x}_l||^2 \end{align*} \] 式中 ${x}l = ({x}{1l},{x}{2l},...,{x}{ml})^T是第 \(l\) 个类的均值或中心

k均值聚类就是求解最优化问题： \[ \begin{align*} C^* &= arg\, min_{C} W(C) \\ &= arg \, min_{C}\sum_{l = 1}^{k}\sum_{C(i) = l}||x_{i} - \bar{x}_l||^2 \end{align*} \]

相似的样本被聚到同类时，损失函数值最小，这个目标函数的最优化能达到聚类的目的。但是这个组合优化问题的所有可能分类方法过多，只能通过迭代的方法求解

算法

k均值聚类的算法是一个迭代的过程，每次迭代包括两个步骤： * 首先选择k个类的中心，将样本诸葛指派到与其最近的中心的类中，得到一个聚类结果； * 然后更新每个类的样本的均值，作为类的新的中心； * 重复以上步骤直到收敛为止

算法： 输入：\(n\) 个样本的集合 \(X\) 输出：样本集合的聚类 \(C^*\) 1. 初始化：令 \(t = 0\)，随机选择 \(k\) 个样本点作为初始聚类中心 \(m^{(0)} = (m_1^{(0)},...,m_l^{(0)},...,m_k^{(0)})\) 2. 对样本进行聚类。对固定的类中心 \(m^{(t)} = (m_1^{(t)},...,m_l^{(t)},...,m_k^{(t)})\)，其中 \(m_l^{(t)}\) 为类 \(G_l\) 的中心，计算每个样本到类中心的距离，将每个样本指派到与其最近的中心的类中，构成聚类结果\(C^{(t)}\)。 3. 计算新的类中心。对聚类接过 \(C^{(t)}\)，计算当前各个类中的样本的均值，作为新的类中心 \(m^{(t + 1)} = (m_1^{(t + 1)},...,m_l^{(t + 1)},...,m_k^{(t + 1)})\) 4. 如果迭代收敛或符合停止条件，输出 \(C^* = C^{(t)}\); 否则，令 \(t = t + 1\)，返回步骤2