二、原型聚类

发布于 2023-07-17 23:38:26 字数 13946 浏览 0 评论 0 收藏 0

原型聚类prototype-based clustering假设聚类结构能通过一组原型刻画。
常用的原型聚类有：
- k均值算法k-means 。
- 学习向量量化算法Learning Vector Quantization:LVQ 。
- 高斯混合聚类Mixture-of-Gaussian 。

2.1 k-means 算法

2.1.1 k-means

给定样本集 $ MathJax-Element-470 $ ，假设一个划分为 $ MathJax-Element-473 $ 。
定义该划分的平方误差为：
$ err=\sum_{k=1}^{K}\sum_{\mathbf{\vec x}_i \in \mathbb C_k}||\mathbf{\vec x}_i-\vec \mu_k||_2^{2} $
其中 $ MathJax-Element-145 $ 是簇 $ MathJax-Element-330 $ 的均值向量。
- $ MathJax-Element-148 $ 刻画了簇类样本围绕簇均值向量的紧密程度，其值越小，则簇内样本相似度越高。
- k-means 算法的优化目标为：最小化 $ MathJax-Element-148 $ 。即： $ MathJax-Element-149 $ 。
k-means 的优化目标需要考察 $ MathJax-Element-548 $ 的所有可能的划分，这是一个NP难的问题。实际上k-means 采用贪心策略，通过迭代优化来近似求解。
- 首先假设一组均值向量。
- 然后根据假设的均值向量给出了 $ MathJax-Element-548 $ 的一个划分。
- 再根据这个划分来计算真实的均值向量：
  - 如果真实的均值向量等于假设的均值向量，则说明假设正确。根据假设均值向量给出的 $ MathJax-Element-548 $ 的一个划分确实是原问题的解。
  - 如果真实的均值向量不等于假设的均值向量，则可以将真实的均值向量作为新的假设均值向量，继续迭代求解。
这里的一个关键就是：给定一组假设的均值向量，如何计算出 $ MathJax-Element-548 $ 的一个簇划分？
k均值算法的策略是：样本离哪个簇的均值向量最近，则该样本就划归到那个簇。
k-means 算法：
- 输入：
  - 样本集 $ MathJax-Element-470 $ 。
  - 聚类簇数 $ MathJax-Element-554 $ 。
- 输出：簇划分 $ MathJax-Element-473 $ 。
- 算法步骤：
  - 从 $ MathJax-Element-548 $ 中随机选择 $ MathJax-Element-554 $ 个样本作为初始均值向量 $ MathJax-Element-224 $ 。
  - 重复迭代直到算法收敛，迭代过程：
    - 初始化阶段：取 $ MathJax-Element-225 $
    - 划分阶段：令 $ MathJax-Element-161 $ ：
      - 计算 $ MathJax-Element-523 $ 的簇标记： $ MathJax-Element-229 $ 。
        即：将 $ MathJax-Element-523 $ 离哪个簇的均值向量最近，则该样本就标记为那个簇。
      - 然后将样本 $ MathJax-Element-523 $ 划入相应的簇： $ MathJax-Element-232 $ 。
    - 重计算阶段：计算 $ MathJax-Element-233 $ ： $ MathJax-Element-234 $ 。
    - 终止条件判断：
      - 如果对所有的 $ MathJax-Element-235 $ ，都有 $ MathJax-Element-236 $ ，则算法收敛，终止迭代。
      - 否则重赋值 $ MathJax-Element-237 $ 。
k-means 优点：
- 计算复杂度低，为 $ MathJax-Element-172 $ ，其中 $ MathJax-Element-175 $ 为迭代次数。
  通常 $ MathJax-Element-554 $ 和 $ MathJax-Element-175 $ 要远远小于 $ MathJax-Element-400 $ ，此时复杂度相当于 $ MathJax-Element-177 $ 。
- 思想简单，容易实现。
k-means 缺点：
- 需要首先确定聚类的数量 $ MathJax-Element-554 $ 。
- 分类结果严重依赖于分类中心的初始化。
  通常进行多次k-means，然后选择最优的那次作为最终聚类结果。
- 结果不一定是全局最优的，只能保证局部最优。
- 对噪声敏感。因为簇的中心是取平均，因此聚类簇很远地方的噪音会导致簇的中心点偏移。
- 无法解决不规则形状的聚类。
- 无法处理离散特征，如：国籍、性别 等。

k-means 性质：
- k-means 实际上假设数据是呈现球形分布，实际任务中很少有这种情况。
  与之相比，GMM 使用更加一般的数据表示，即高斯分布。
- k-means 假设各个簇的先验概率相同，但是各个簇的数据量可能不均匀。
- k-means 使用欧式距离来衡量样本与各个簇的相似度。这种距离实际上假设数据的各个维度对于相似度的作用是相同的。
- k-means 中，各个样本点只属于与其相似度最高的那个簇，这实际上是硬 分簇。
- k-means 算法的迭代过程实际上等价于EM 算法。具体参考EM 算法章节。

2.1.2 k-means++

k-means++ 属于 k-means 的变种，它主要解决k-means 严重依赖于分类中心初始化的问题。
k-means++ 选择初始均值向量时，尽量安排这些初始均值向量之间的距离尽可能的远。
k-means++ 算法：
- 输入：
  - 样本集 $ MathJax-Element-470 $ 。
  - 聚类簇数 $ MathJax-Element-554 $ 。
- 输出：簇划分 $ MathJax-Element-473 $ 。
- 算法步骤：
  - 从 $ MathJax-Element-548 $ 中随机选择1个样本作为初始均值向量组 $ MathJax-Element-183 $ 。
  - 迭代，直到初始均值向量组有 $ MathJax-Element-554 $ 个向量。
    假设初始均值向量组为 $ MathJax-Element-185 $ 。迭代过程如下：
    - 对每个样本 $ MathJax-Element-523 $ ，分别计算其距 $ MathJax-Element-187 $ 的距离。这些距离的最小值记做 $ MathJax-Element-188 $ 。
    - 对样本 $ MathJax-Element-523 $ ，其设置为初始均值向量的概率正比于 $ MathJax-Element-190 $ 。即：离所有的初始均值向量越远，则越可能被选中为下一个初始均值向量。
    - 以概率分布 $ MathJax-Element-191 $ （未归一化的）随机挑选一个样本作为下一个初始均值向量 $ MathJax-Element-192 $ 。
  - 一旦挑选出初始均值向量组 $ MathJax-Element-193 $ ，剩下的迭代步骤与k-means 相同。

2.1.3 k-modes

k-modes 属于 k-means 的变种，它主要解决k-means 无法处理离散特征的问题。
k-modes 与k-means 有两个不同点（假设所有特征都是离散特征）：
- 距离函数不同。在k-modes 算法中，距离函数为：
  $ \text{distance}( \mathbf {\vec x}_i, \mathbf {\vec x}_j )=\sum_{d=1}^n I(x_{i,d}=x_{j,d}) $
  其中 $ MathJax-Element-194 $ 为示性函数。
  上式的意义为：样本之间的距离等于它们之间不同属性值的个数。
- 簇中心的更新规则不同。在k-modes 算法中，簇中心每个属性的取值为：簇内该属性出现频率最大的那个值。
  $ \hat\mu_{k,d} = \arg\max_{v} \sum_{\mathbf{\vec x}_i\in \mathbb C_k} I(x_{i,d}=v) $
  其中 $ MathJax-Element-195 $ 的取值空间为所有样本在第 $ MathJax-Element-196 $ 个属性上的取值。

2.1.4 k-medoids

k-medoids 属于 k-means 的变种，它主要解决k-means 对噪声敏感的问题。
k-medoids 算法：
- 输入：
  - 样本集 $ MathJax-Element-470 $ 。
  - 聚类簇数 $ MathJax-Element-554 $ 。
- 输出：簇划分 $ MathJax-Element-473 $ 。
- 算法步骤：
  - 从 $ MathJax-Element-548 $ 中随机选择 $ MathJax-Element-554 $ 个样本作为初始均值向量 $ MathJax-Element-224 $ 。
  - 重复迭代直到算法收敛，迭代过程：
    - 初始化阶段：取 $ MathJax-Element-225 $ 。
      遍历每个样本 $ MathJax-Element-384 $ ，计算它的簇标记： $ MathJax-Element-229 $ 。即：将 $ MathJax-Element-523 $ 离哪个簇的均值向量最近，则该样本就标记为那个簇。
      然后将样本 $ MathJax-Element-523 $ 划入相应的簇： $ MathJax-Element-232 $ 。
    - 重计算阶段：
      遍历每个簇 $ MathJax-Element-209 $ ：
      - 计算簇心 $ MathJax-Element-210 $ 距离簇内其它点的距离 $ MathJax-Element-211 $ 。
      - 计算簇 $ MathJax-Element-330 $ 内每个点 $ MathJax-Element-213 $ 距离簇内其它点的距离 $ MathJax-Element-214 $ 。
        如果 $ MathJax-Element-215 $ ，则重新设置簇中心： $ MathJax-Element-216 $ 。
    - 终止条件判断：遍历一轮簇 $ MathJax-Element-217 $ 之后，簇心保持不变。
k-medoids 算法在计算新的簇心时，不再通过簇内样本的均值来实现，而是挑选簇内距离其它所有点都最近的样本来实现。这就减少了孤立噪声带来的影响。
k-medoids 算法复杂度较高，为 $ MathJax-Element-218 $ 。其中计算代价最高的是计算每个簇内每对样本之间的距离。
通常会在算法开始时计算一次，然后将结果缓存起来，以便后续重复使用。

2.1.5 mini-batch k-means

mini-batch k-means 属于 k-means 的变种，它主要用于减少k-means 的计算时间。
mini-batch k-means 算法每次训练时随机抽取小批量的数据，然后用这个小批量数据训练。这种做法减少了k-means 的收敛时间，其效果略差于标准算法。
mini-batch k-means 算法：
- 输入：
  - 样本集 $ MathJax-Element-470 $ 。
  - 聚类簇数 $ MathJax-Element-554 $ 。
- 输出：簇划分 $ MathJax-Element-473 $ 。
- 算法步骤：
  - 从 $ MathJax-Element-548 $ 中随机选择 $ MathJax-Element-554 $ 个样本作为初始均值向量 $ MathJax-Element-224 $ 。
  - 重复迭代直到算法收敛，迭代过程：
    - 初始化阶段：取 $ MathJax-Element-225 $
    - 划分阶段：随机挑选一个Batch 的样本集合 $ MathJax-Element-226 $ ，其中 $ MathJax-Element-227 $ 为批大小。
      - 计算 $ MathJax-Element-231 $ 的簇标记： $ MathJax-Element-229 $ 。
        即：将 $ MathJax-Element-523 $ 离哪个簇的均值向量最近，则该样本就标记为那个簇。
      - 然后将样本 $ MathJax-Element-231 $ 划入相应的簇： $ MathJax-Element-232 $ 。
    - 重计算阶段：计算 $ MathJax-Element-233 $ ： $ MathJax-Element-234 $ 。
    - 终止条件判断：
      - 如果对所有的 $ MathJax-Element-235 $ ，都有 $ MathJax-Element-236 $ ，则算法收敛，终止迭代。
      - 否则重赋值 $ MathJax-Element-237 $ 。

2.2 学习向量量化

与一般聚类算法不同，学习向量量化Learning Vector Quantization:LVQ假设数据样本带有类别标记，学习过程需要利用样本的这些监督信息来辅助聚类。
给定样本集 $ MathJax-Element-238 $ ，LVQ的目标是从特征空间中挑选一组样本作为原型向量 $ MathJax-Element-267 $ 。
- 每个原型向量代表一个聚类簇，簇标记 $ MathJax-Element-240 $ 。即：簇标记从类别标记中选取。
- 原型向量从特征空间中取得，它们不一定就是 $ MathJax-Element-548 $ 中的某个样本。
LVQ的想法是：通过从样本中挑选一组样本作为原型向量 $ MathJax-Element-267 $ ，可以实现对样本空间 $ MathJax-Element-294 $ 的簇划分。
- 对任意样本 $ MathJax-Element-459 $ ，它被划入与距离最近的原型向量所代表的簇中。
- 对于每个原型向量 $ MathJax-Element-247 $ ，它定义了一个与之相关的一个区域 $ MathJax-Element-246 $ ，该区域中每个样本与 $ MathJax-Element-247 $ 的距离都不大于它与其他原型向量 $ MathJax-Element-248 $ 的距离。
  $ \mathbf R_q=\{\mathbf{\vec x} \in \mathcal X \mid ||\mathbf{\vec x}-\mathbf{\vec p}_q||_2 \le \min_{q^{\prime} \ne q}||\mathbf{\vec x}-\mathbf{\vec p}_{q^{\prime}}||_2\} $
- 区域 $ MathJax-Element-249 $ 对样本空间 $ MathJax-Element-294 $ 形成了一个簇划分，该划分通常称作 Voronoi剖分。
问题是如何从样本中挑选一组样本作为原型向量？ LVQ的思想是：
- 首先挑选一组样本作为假设的原型向量。
- 然后对于训练集中的每一个样本 $ MathJax-Element-523 $ ，找出假设的原型向量中，距离该样本最近的原型向量 $ MathJax-Element-259 $ ：
  - 如果 $ MathJax-Element-523 $ 的标记与 $ MathJax-Element-259 $ 的标记相同，则更新 $ MathJax-Element-259 $ ，将该原型向量更靠近 $ MathJax-Element-523 $ 。
  - 如果 $ MathJax-Element-523 $ 的标记与 $ MathJax-Element-259 $ 的标记不相同，则更新 $ MathJax-Element-259 $ ，将该原型向量更远离 $ MathJax-Element-523 $ 。
- 不停进行这种更新，直到迭代停止条件（如以到达最大迭代次数，或者原型向量的更新幅度很小）。
LVQ算法：
- 输入：
  - 样本集 $ MathJax-Element-261 $
  - 原型向量个数 $ MathJax-Element-262 $
  - 各原型向量预设的类别标记 $ MathJax-Element-266 $
  - 学习率 $ MathJax-Element-264 $
- 输出：原型向量 $ MathJax-Element-267 $
- 算法步骤：
  - 依次随机从类别 $ MathJax-Element-266 $ 中挑选一个样本，初始化一组原型向量 $ MathJax-Element-267 $ 。
  - 重复迭代，直到算法收敛。迭代过程如下：
    - 从样本集 $ MathJax-Element-548 $ 中随机选取样本 $ MathJax-Element-270 $ ，挑选出距离 $ MathJax-Element-270 $ 最近的原型向量 $ MathJax-Element-292 $ ： $ MathJax-Element-272 $ 。
    - 如果 $ MathJax-Element-292 $ 的类别等于 $ MathJax-Element-286 $ ，则： $ MathJax-Element-275 $ 。
    - 如果 $ MathJax-Element-292 $ 的类别不等于 $ MathJax-Element-286 $ ，则： $ MathJax-Element-278 $ 。
在原型向量的更新过程中：
- 如果 $ MathJax-Element-292 $ 的类别等于 $ MathJax-Element-286 $ ，则更新后， $ MathJax-Element-292 $ 与 $ MathJax-Element-523 $ 距离为：
  $ || \mathbf{\vec p_{q_i}}-\mathbf{\vec x}_i||_2=||\mathbf{\vec p_{q_i}}+\eta(\mathbf{\vec x}_i-\mathbf{\vec p_{q_i}})- \mathbf{\vec x}_i||_2\ =(1-\eta)|| \mathbf{\vec p_{q_i}}-\mathbf{\vec x}_i||_2 $
  则更新后的原型向量 $ MathJax-Element-292 $ 距离 $ MathJax-Element-523 $ 更近。
- 如果 $ MathJax-Element-292 $ 的类别不等于 $ MathJax-Element-286 $ ，则更新后， $ MathJax-Element-292 $ 与 $ MathJax-Element-523 $ 距离为：
  $ || \mathbf{\vec p_{q_i}}-\mathbf{\vec x}_i||_2=||\mathbf{\vec p_{q_i}}-\eta(\mathbf{\vec x}_i-\mathbf{\vec p_{q_i}})- \mathbf{\vec x}_i||_2\ =(1+\eta)|| \mathbf{\vec p_{q_i}}-\mathbf{\vec x}_i||_2 $
  则更新后的原型向量 $ MathJax-Element-292 $ 距离 $ MathJax-Element-523 $ 更远。
这里有一个隐含假设：即计算得到的样本 $ MathJax-Element-291 $ （该样本可能不在样本集中）的标记就是更新之前 $ MathJax-Element-292 $ 的标记。
即：更新操作只改变原型向量的样本值，但是不改变该原型向量的标记。

2.3 高斯混合聚类

高斯混合聚类采用概率模型来表达聚类原型。
对于 $ MathJax-Element-434 $ 维样本空间 $ MathJax-Element-294 $ 中的随机向量 $ MathJax-Element-459 $ ，若 $ MathJax-Element-459 $ 服从高斯分布，则其概率密度函数为：
$ p(\mathbf{\vec x}\mid \vec \mu,\Sigma)=\frac {1}{(2\pi)^{n/2}|\Sigma|^{1 /2}}\exp\left(-\frac 12(\mathbf{\vec x}- \vec \mu)^{T}\Sigma^{-1}(\mathbf{\vec x}- \vec \mu)\right) $
其中 $ MathJax-Element-799 $ 为 $ MathJax-Element-434 $ 维均值向量， $ MathJax-Element-299 $ 是 $ MathJax-Element-300 $ 的协方差矩阵。 $ MathJax-Element-459 $ 的概率密度函数由参数 $ MathJax-Element-302 $ 决定。
定义高斯混合分布： $ MathJax-Element-303 $ 。该分布由 $ MathJax-Element-554 $ 个混合成分组成，每个混合成分对应一个高斯分布。其中:
- $ MathJax-Element-305 $ 是第 $ MathJax-Element-306 $ 个高斯混合成分的参数。
- $ MathJax-Element-307 $ 是相应的混合系数，满足 $ MathJax-Element-308 $ 。
假设训练集 $ MathJax-Element-470 $ 的生成过程是由高斯混合分布给出。
令随机变量 $ MathJax-Element-310 $ 表示生成样本 $ MathJax-Element-459 $ 的高斯混合成分序号， $ MathJax-Element-331 $ 的先验概率 $ MathJax-Element-313 $ 。
生成样本的过程分为两步：
- 首先根据概率分布 $ MathJax-Element-314 $ 生成随机变量 $ MathJax-Element-331 $ 。
- 再根据 $ MathJax-Element-331 $ 的结果，比如 $ MathJax-Element-329 $ ，根据概率 $ MathJax-Element-318 $ 生成样本。
根据贝叶斯定理，若已知输出为 $ MathJax-Element-523 $ ，则 $ MathJax-Element-331 $ 的后验分布为：
$ p_{\mathcal M}(Z =k\mid \mathbf{\vec x}_i)=\frac{P(Z =k)p_{\mathcal M}(\mathbf{\vec x}_i \mid Z =k)}{p_{\mathcal M}(\mathbf{\vec x}_i)} = \frac{\alpha_k p(\mathbf{\vec x}_i\mid \vec \mu_k,\Sigma_k)}{\sum_{l=1}^{K}\alpha_l p(\mathbf{\vec x}_i\mid \vec \mu_l,\Sigma_l)} $
其物理意义为：所有导致输出为 $ MathJax-Element-523 $ 的情况中， $ MathJax-Element-329 $ 发生的概率。
当高斯混合分布已知时，高斯混合聚类将样本集 $ MathJax-Element-548 $ 划分成 $ MathJax-Element-554 $ 个簇 $ MathJax-Element-473 $ 。
对于每个样本 $ MathJax-Element-523 $ ，给出它的簇标记 $ MathJax-Element-327 $ 为：
$ \lambda_i=\arg\max_k p_{\mathcal M}(Z =k\mid \mathbf{\vec x}_i) $
即：如果 $ MathJax-Element-523 $ 最有可能是 $ MathJax-Element-329 $ 产生的，则将该样本划归到簇 $ MathJax-Element-330 $ 。
这就是通过最大后验概率确定样本所属的聚类。
现在的问题是，如何学习高斯混合分布的参数。由于涉及到隐变量 $ MathJax-Element-331 $ ，可以采用EM算法求解。
具体求解参考EM 算法的章节部分。