机器学习：K-means

发表于 更新于 分类于

聚类算法

用于将未知类别的样本集划分为若干簇的的算法就是聚类算法。

聚类没有任何关于关于类别的预先设立的知识，直接依据样本之间的相似性来决定哪些样本属于同类；

算法原理

  • 确定参数：根据参数 K，把数据分成 K 个簇；
  • 初始化簇中心：随机选择 K 个初始数据对象点作为初始的聚类中心；
  • 计算距离并分类：计算其余各个数据与 K 个聚类中心的距离，把数据划分到离它最近的那个中心所在的类中；
  • 调整簇中心：根据新加入的分类结果计算新的簇中

注意：

  • 在划分完所有数据对象的类别后，才需要更新聚类中心

  • 可以设置最大迭代次数来替代收敛条件

  • 收敛条件是看与上一次迭代的准则函数结果差是否超过指定数值，未超过则判断为收敛，准则函数：

    Jc(i)=∑j=1K∑k=1nj∣∣xkj−Zj(i)∣∣2J_c(i)=\sum^K_{j=1}\sum^{n_j}_{k=1}||x_k^j-Z_j(i)||^2

    jj 是中心点的索引，i 是迭代次数的索引。njn_j 表示第 jj 个中心点所在类的数据对象的个数，Zj(i)Z_j(i) 表示第 ii 次迭代第 jj 个中心点，xkjx_k^j 表示第 jj 类下的第 kk 个数据对象。该函数的意义为计算所有类中所有数据对象离中心点的距离之和。

距离

闵可夫斯基距离

dist(X,Y)=(∑k=1n(∣xk−yk∣p))1pdist(X,Y) = (\sum^n_{k=1}(|x_k - y_k|^p))^{\frac{1}{p}}

p = 2 时，即为欧氏距离（欧几里得距离）；

p = 1 时，即为曼哈顿距离；

p 趋近于无穷大时，即为切比雪夫距离；

缺点

  • 依赖用户参数的指定
  • 只能发现球状的簇，很难发现其他情况的

image-20211225115601878

  • 初始中心的随机选取，导致结果波动较大，稳定性差

确定 K 值

SSE=∑i=1k∑p∈Ci∣p⃗−mi⃗∣2SSE = \sum^k_{i=1}\sum_{p \in C_i}| \vec{p} - \vec{m_i} |^2

SSE （Sum of the Squared Errors），误差平方和。

CiC_i 表示第 i 个簇，mim_i 表示第 i 个簇的质心，SSE 代表了聚类结果的好坏。

构建 K 与 SSE 的函数关系，当 K:

  • 小于正确聚类数时：K 的增大会大幅增加每个簇的聚合程度，所以 SSE 会迅速下降。
  • 到达正确聚类数时：K 的增大，SSE 的下降幅度减少
  • 以上两点使得 K 与 SSE 的函数关系图像呈现手肘的形状，去手肘的拐点作为我们的 K
image-20211225120420811

K-means ++

通过尽可能地选择互相之间距离远的质心来减少质心对算法的影响。

  1. 从样本集 X 中随机挑选一个初始质心

  2. 从样本中取出样本点 x，计算其与现有的所有质心的距离，取离它最近的质心，设距离为 D(x)

  3. 计算样本点 x 被选为下一个质心的概率为：

    P(x)=D(x)2∑x∈XD(x)2P(x) = \frac{D(x)^2}{\sum_{x \in X}D(x)^2}

  4. 使用轮盘法选出下一个质心：将所有 P(xi)P(x_i) 拼为一个区间 sum，选取 [0, 1] 中的一个随机值，判断它落在 sum 中的哪个样本点的区间内。