二、原型聚类

1. 原型聚类prototype-based clustering假设聚类结构能通过一组原型刻画。

   常用的原型聚类有：

   • k均值算法k-means 。
   • 学习向量量化算法Learning Vector Quantization:LVQ 。
   • 高斯混合聚类Mixture-of-Gaussian 。

2.1 k-means 算法

2.1.1 k-means

1. 给定样本集 ， 假设一个划分为 。

   定义该划分的平方误差为：

   

   其中 是簇 的均值向量。

   • 刻画了簇类样本围绕簇均值向量的紧密程度，其值越小，则簇内样本相似度越高。
   • k-means 算法的优化目标为：最小化 。即： 。

2. k-means 的优化目标需要考察 的所有可能的划分，这是一个NP难的问题。实际上k-means 采用贪心策略，通过迭代优化来近似求解。

   • 首先假设一组均值向量。

   • 然后根据假设的均值向量给出了 的一个划分。

   • 再根据这个划分来计算真实的均值向量：

     • 如果真实的均值向量等于假设的均值向量，则说明假设正确。根据假设均值向量给出的 的一个划分确实是原问题的解。
     • 如果真实的均值向量不等于假设的均值向量，则可以将真实的均值向量作为新的假设均值向量，继续迭代求解。

3. 这里的一个关键就是：给定一组假设的均值向量，如何计算出 的一个簇划分？

   k均值算法的策略是：样本离哪个簇的均值向量最近，则该样本就划归到那个簇。

4. k-means 算法：

   • 输入：

     • 样本集 。
     • 聚类簇数 。

   • 输出：簇划分 。

   • 算法步骤：

     • 从 中随机选择 个样本作为初始均值向量 。

     • 重复迭代直到算法收敛，迭代过程：

       • 初始化阶段：取

       • 划分阶段：令 ：

         • 计算 的簇标记： 。

           即：将 离哪个簇的均值向量最近，则该样本就标记为那个簇。

         • 然后将样本 划入相应的簇： 。

       • 重计算阶段：计算 ： 。

       • 终止条件判断：

         • 如果对所有的 ，都有 ，则算法收敛，终止迭代。
         • 否则重赋值 。

5. k-means 优点：

   • 计算复杂度低，为 ，其中 为迭代次数。

     通常 和 要远远小于 ，此时复杂度相当于 。

   • 思想简单，容易实现。

6. k-means 缺点：

   • 需要首先确定聚类的数量 。

   • 分类结果严重依赖于分类中心的初始化。

     通常进行多次k-means，然后选择最优的那次作为最终聚类结果。

   • 结果不一定是全局最优的，只能保证局部最优。

   • 对噪声敏感。因为簇的中心是取平均，因此聚类簇很远地方的噪音会导致簇的中心点偏移。

   • 无法解决不规则形状的聚类。

   • 无法处理离散特征，如：国籍、性别 等。

1. k-means 性质：

   • k-means 实际上假设数据是呈现球形分布，实际任务中很少有这种情况。

     与之相比，GMM 使用更加一般的数据表示，即高斯分布。

   • k-means 假设各个簇的先验概率相同，但是各个簇的数据量可能不均匀。

   • k-means 使用欧式距离来衡量样本与各个簇的相似度。这种距离实际上假设数据的各个维度对于相似度的作用是相同的。

   • k-means 中，各个样本点只属于与其相似度最高的那个簇，这实际上是硬 分簇。

   • k-means 算法的迭代过程实际上等价于EM 算法。具体参考EM 算法章节。

2.1.2 k-means++

1. k-means++ 属于 k-means 的变种，它主要解决k-means 严重依赖于分类中心初始化的问题。

2. k-means++ 选择初始均值向量时，尽量安排这些初始均值向量之间的距离尽可能的远。

3. k-means++ 算法：

   • 输入：

     • 样本集 。
     • 聚类簇数 。

   • 输出：簇划分 。

   • 算法步骤：

     • 从 中随机选择1个样本作为初始均值向量组 。

     • 迭代，直到初始均值向量组有 个向量。

       假设初始均值向量组为 。迭代过程如下：

       • 对每个样本 ，分别计算其距 的距离。这些距离的最小值记做 。
       • 对样本 ，其设置为初始均值向量的概率正比于 。即：离所有的初始均值向量越远，则越可能被选中为下一个初始均值向量。
       • 以概率分布 （未归一化的）随机挑选一个样本作为下一个初始均值向量 。
     • 一旦挑选出初始均值向量组 ，剩下的迭代步骤与k-means 相同。

2.1.3 k-modes

1. k-modes 属于 k-means 的变种，它主要解决k-means 无法处理离散特征的问题。

2. k-modes 与k-means 有两个不同点（假设所有特征都是离散特征）：

   • 距离函数不同。在k-modes 算法中，距离函数为：

     

     其中 为示性函数。

     上式的意义为：样本之间的距离等于它们之间不同属性值的个数。

   • 簇中心的更新规则不同。在k-modes 算法中，簇中心每个属性的取值为：簇内该属性出现频率最大的那个值。

     

     其中 的取值空间为所有样本在第 个属性上的取值。

2.1.4 k-medoids

1. k-medoids 属于 k-means 的变种，它主要解决k-means 对噪声敏感的问题。

2. k-medoids 算法：

   • 输入：

     • 样本集 。
     • 聚类簇数 。

   • 输出：簇划分 。

   • 算法步骤：

     • 从 中随机选择 个样本作为初始均值向量 。

     • 重复迭代直到算法收敛，迭代过程：

       • 初始化阶段：取 。

         遍历每个样本 ，计算它的簇标记： 。即：将 离哪个簇的均值向量最近，则该样本就标记为那个簇。

         然后将样本 划入相应的簇： 。

       • 重计算阶段：

         遍历每个簇 ：

         • 计算簇心 距离簇内其它点的距离 。

         • 计算簇 内每个点 距离簇内其它点的距离 。

           如果 ，则重新设置簇中心： 。

       • 终止条件判断：遍历一轮簇 之后，簇心保持不变。

3. k-medoids 算法在计算新的簇心时，不再通过簇内样本的均值来实现，而是挑选簇内距离其它所有点都最近的样本来实现。这就减少了孤立噪声带来的影响。

4. k-medoids 算法复杂度较高，为 。其中计算代价最高的是计算每个簇内每对样本之间的距离。

   通常会在算法开始时计算一次，然后将结果缓存起来，以便后续重复使用。

2.1.5 mini-batch k-means

1. mini-batch k-means 属于 k-means 的变种，它主要用于减少k-means 的计算时间。

2. mini-batch k-means 算法每次训练时随机抽取小批量的数据，然后用这个小批量数据训练。这种做法减少了k-means 的收敛时间，其效果略差于标准算法。

3. mini-batch k-means 算法：

   • 输入：

     • 样本集 。
     • 聚类簇数 。

   • 输出：簇划分 。

   • 算法步骤：

     • 从 中随机选择 个样本作为初始均值向量 。

     • 重复迭代直到算法收敛，迭代过程：

       • 初始化阶段：取

       • 划分阶段：随机挑选一个Batch 的样本集合 ，其中 为批大小。

         • 计算 的簇标记： 。

           即：将 离哪个簇的均值向量最近，则该样本就标记为那个簇。

         • 然后将样本 划入相应的簇： 。

       • 重计算阶段：计算 ： 。

       • 终止条件判断：

         • 如果对所有的 ，都有 ，则算法收敛，终止迭代。
         • 否则重赋值 。

2.2 学习向量量化

1. 与一般聚类算法不同，学习向量量化Learning Vector Quantization:LVQ假设数据样本带有类别标记，学习过程需要利用样本的这些监督信息来辅助聚类。

2. 给定样本集 ，LVQ的目标是从特征空间中挑选一组样本作为原型向量 。

   • 每个原型向量代表一个聚类簇，簇标记 。即：簇标记从类别标记中选取。
   • 原型向量从特征空间中取得，它们不一定就是 中的某个样本。

3. LVQ的想法是：通过从样本中挑选一组样本作为原型向量 ，可以实现对样本空间 的簇划分。

   • 对任意样本 ，它被划入与距离最近的原型向量所代表的簇中。

   • 对于每个原型向量 ，它定义了一个与之相关的一个区域 ，该区域中每个样本与 的距离都不大于它与其他原型向量 的距离。

     

   • 区域 对样本空间 形成了一个簇划分，该划分通常称作 Voronoi剖分。

4. 问题是如何从样本中挑选一组样本作为原型向量？ LVQ的思想是：

   • 首先挑选一组样本作为假设的原型向量。

   • 然后对于训练集中的每一个样本 ， 找出假设的原型向量中，距离该样本最近的原型向量 ：

     • 如果 的标记与 的标记相同，则更新 ，将该原型向量更靠近 。
     • 如果 的标记与 的标记不相同，则更新 ，将该原型向量更远离 。
   • 不停进行这种更新，直到迭代停止条件（如以到达最大迭代次数，或者原型向量的更新幅度很小）。

5. LVQ算法：

   • 输入：

     • 样本集
     • 原型向量个数
     • 各原型向量预设的类别标记
     • 学习率

   • 输出：原型向量

   • 算法步骤：

     • 依次随机从类别 中挑选一个样本，初始化一组原型向量 。

     • 重复迭代，直到算法收敛。迭代过程如下：

       • 从样本集 中随机选取样本 ，挑选出距离 最近的原型向量 ： 。
       • 如果 的类别等于 ，则： 。
       • 如果 的类别不等于 ，则： 。

6. 在原型向量的更新过程中：

   • 如果 的类别等于 ，则更新后， 与 距离为：

     

     则更新后的原型向量 距离 更近。

   • 如果 的类别不等于 ，则更新后， 与 距离为：

     

     则更新后的原型向量 距离 更远。

7. 这里有一个隐含假设：即计算得到的样本 （该样本可能不在样本集中） 的标记就是更新之前 的标记。

   即：更新操作只改变原型向量的样本值，但是不改变该原型向量的标记。

2.3 高斯混合聚类

1. 高斯混合聚类采用概率模型来表达聚类原型。

2. 对于 维样本空间 中的随机向量 ，若 服从高斯分布，则其概率密度函数为 ：

   

   其中 为 维均值向量， 是 的协方差矩阵。 的概率密度函数由参数 决定。

3. 定义高斯混合分布： 。该分布由 个混合成分组成，每个混合成分对应一个高斯分布。其中:

   • 是第 个高斯混合成分的参数。
   • 是相应的混合系数，满足 。

4. 假设训练集 的生成过程是由高斯混合分布给出。

   令随机变量 表示生成样本 的高斯混合成分序号， 的先验概率 。

   生成样本的过程分为两步：

   • 首先根据概率分布 生成随机变量 。
   • 再根据 的结果，比如 ， 根据概率 生成样本。

5. 根据贝叶斯定理， 若已知输出为 ，则 的后验分布为：

   

   其物理意义为：所有导致输出为 的情况中， 发生的概率。

6. 当高斯混合分布已知时，高斯混合聚类将样本集 划分成 个簇 。

   对于每个样本 ，给出它的簇标记 为：

   

   即：如果 最有可能是 产生的，则将该样本划归到簇 。

   这就是通过最大后验概率确定样本所属的聚类。

7. 现在的问题是，如何学习高斯混合分布的参数。由于涉及到隐变量 ，可以采用EM算法求解。

   具体求解参考EM 算法的章节部分。