机器学习算法(一):K-means

K-means 算法是一种聚类算法,用于将数据集划分到 k 个簇中,使得每个点都属于离它最近的质心(Centroid)所属的簇中。

算法过程

  1. 值域范围内随机 k 个质心;
  2. 将点指派到距离最近的质心,形成 k 个簇;
  3. 计算每个簇所有点的均值,指定新的质心;
  4. 重复第 2 步和第 3 步,直到收敛或满足最大迭代次数。

k-means

算法描述

给定数据集 $S = {x _{1}, x _{2},...,x _n}$,划分为 k 个簇。

损失函数,簇内平方差(WCSS within-cluster sum of squares):

$${\sum _{i=1} ^{k} {\sum _{x\in S _{i}}{{\left\| x-\mu _{i} \right\|} ^{2}}}}$$

k-means 实际上就是找到满足下式的 $S _{i}$:

$$\underset{S}{\arg\min}{\sum _{i=1} ^{k} {\sum _{x\in S _{i}}{{\left\| x-\mu _{i} \right\|} ^{2}}}}$$

其中,$\mu _{i}$ 是簇内所有点的均值。

K-means++

TODO

Q & A

Q:如何选择合适的 k 值?

A:采用手肘法,尝试不同的 k 值,并将对应的损失函数的值画成一条折线。

参考