K-means

Posted by Pelhans on September 11, 2019

K-means 算法

k-means 算法

k-means 算法是一种无监督聚类方法.给定数据集, 假设我们要分为 k 个类别 , 算法步骤如下:

  • 选择初始化的 k 个样本作为初始聚类中心 $ a = a_{1}, a_{2}, \dots, a_{k}$
  • 针对数据集中每个样本 $x_{i}$ 计算它到聚类中心的距离, 并将其分到距离最小的聚类中心所对应的的类别中
  • 针对每个类别, 重新计算它的聚类中心(质心)
  • 由于类别中心发生了变化, 因此重新执行2,3 两步进行重分类. 直到到达某个终止条件(迭代次数, 最小误差变化等)

定义划分的平方误差为:

其中 是类别 k 的聚类中心. 整个损失表示簇类样本围绕聚类中心的紧密程度, 它的值越小, 则 簇内样本相似程度越高, 越紧密.

k-means 优缺点

K-means 的优点:

  • 算法复杂度低, 为 O(Nkt), t 是迭代次数, 空间复杂度是 O(m(N+k)). m 是样本点维度
  • 核心思想简单, 聚类效果不错, 可以得到局部最优解

缺点

  • 样本类别 k 是一个超参数, 且对结果影响较大
  • 分类结果严重依赖于分类中心的初始化, 通常进行多次k-means,然后选择最优的那次作为最终聚类结果。
  • 只能得到局部最优解
  • 对噪声敏感。因为簇的中心是取平均,因此聚类簇很远地方的噪音会导致簇的中心点偏移。
  • 不适合太离散的分类
  • 样本类别不平衡的分类, k-means 假设各个簇的先验概率相同,但是各个簇的数据量可能不均匀。
  • 非凸形状的分类。k-means 实际上假设数据是呈现球形分布,实际任务中很少有这种情况。
  • 赋予各个特征维度相同的权重来计算距离, 可能与实际情况不符

针对上面的一些缺点, 可以有一些调优的办法:

  • K 值的选取: 一种方法是逐个尝试, 找到使得损失函数曲线处于下降缓慢区域的 k. 另一种方法可以通过如 Gap statistic 等方法利用蒙特卡洛模拟得到 k 值的估计
  • 数据预处理: 对数据进行归一化, 标准化, 异常点检测等预处理
  • 采用核方法: 将数据映射到高维空间, 解决非凸数据等分布的问题

k-means 与 EM 的等价性

在 k-means 算法中, 潜变量就是每个样本所属的类别, 模型参数是每个类别的质心,根据 EM 算法, 我们要先写出 Q 函数. 为此我们假设 类别的先验概率为

再定义后验概率

因此Q函数就可以写作

距离$x_{j}$ 最近的聚类中心为 $\mu_{tj}^{old}$, 也就是属于类别 $t_{j}$.则有

最大化这个期望 Q 的解 $\lambda^{new}$ 是我们想要的. 再给它变个形, 定义集合 , 它表示属于簇 k 的样本的下表的集合.则有

我们要最小化上式并求得参数 $\lambda$. 而这个式子恰好是 k-means 的优化目标:最小化平方误差. 因此可以说K-means 算法迭代步骤中的 每次确认中心点以后重新进行标记 对应 EM 算法中的 E 步 求当前参数条件下的 Expectation.

由于求和的每一项都是非负的, 则当每一个内层求和 都最小时, 总和最小, 对其求导解得

因此EM 算法中的 M 步 求似然函数最大化时(损失函数最小时)对应的参数对应于根据标记重新求中心点.

k-means++

k-means++ 改进了分类中心初始化的策略. k-means++ 选择初始均值向量时,尽量安排这些初始均值向量之间的距离尽可能的远. 这个假设还是比较合理的, 毕竟聚类中心当然离的越远越好. 具体来说

  • 随机选取一个中心点 $\mu_{1}$
  • 计算当前数据点 $x_{i}$ 到各中心点的距离, 并将距离最小值记作 $d_{i}$.
  • 当遍历计算完所有数据点的距离后, 得到 $d_{1}, d_{2}, \dots, d_{N}$, 此时每个点有概率 $\frac{d_{i}}{\sum_{k=1}^{N}d_{k}}$ 的可能被选为下一个初始中心点
  • 重复2-3 步, 得到 k 个中心点为止, 之后就和正常的 k-means 一样了

k-modes

k-modes 属于 k-means 的变种,它主要解决k-means 无法处理离散特征的问题. k_modes 与 k-means 有两个不同点(假设特征都是离散的):

  • 距离函数不同: k-modes 中距离函数为: , 即样本之间的距离等于它们不同属性值的个数
  • 簇中心的更新规则不同. 在 k-modes 算法中, 簇中心每个属性的取值为 簇内该属性出现频率最大的那个值

KNN 与 k-means 的区别与联系

联系就是二者都用到了近邻算法去寻找数据集中离目标点最近的点.

区别:

  • KNN 是分类算法, k-means 是聚类算法
  • KNN 是监督学习, k-means 是无监督学习
  • KNN 没有前期训练过程, k-means 需要训练才能使用