k-means 聚类算法

K-Means 聚类算法 #

一、聚类算法简述 #

聚类简言之就是通过静态分类方法，把一组数据分成不同的子集，由于研究对象和使用场景的各不相同，聚类算法纷繁多样，典型的有：Connectivity, Centroid 等模型，K-Means 就是 Centroid 模型的代表之一。

二、Centroid-based Clusting #

此类型聚类中，每个子集都有一个可以作为代表的重心，该重心甚至都可以不属于所在子集。

三、K-Means 聚类算法过程简述 #

  1. 在集合中随机选取 k 个点，并以这些点作为重心(Centroid)
  2. 根据 k 个重心划分出 k 个子集，这样一来，每个自己都有自己的重心
  3. 将集合中所有向量都和重心做距离计算，并根据距离将其划分到为重心对应子集
  4. 给每个子集重新选举出更均匀的重心，往复 2、3 迭代 i 次

经过 i（有限）次迭代，就能得到相对均匀的子集分布

3.1 如何选举更均匀的重心 #

  1. 数据集合重心 \[{\displaystyle \mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{k}} in {\displaystyle \mathbb {R} ^{n}}\]
\[{\displaystyle \mathbf {C} ={\frac {\mathbf {x} _{1}+\mathbf {x} _{2}+\cdots +\mathbf {x} _{k}}{k}}.}\]
  1. 几何重心

3.2 如何优化最初的 k 个重心 #

k-means 算法起初会随机选取 k 个数据作为聚类重心，这样可能初始选举出来的 k 个重心比较集中，以至于大幅增加迭代次数。而 k-means++ 并非完全随机，中心思想是尽可能选择离散的 k 个重心，大致步骤如下

  1. 随机选择第一个重心
  2. 对每个未被当作重心的点 x，并计算其与最近被选举出的重心的距离 d(x, centriod)
  3. 每个 x 被选举为重心的概率和 d(x, centriod) 的平方成正比（距离越远，被选举成为下一个重心的概率越大）
  4. 重复 2、3 步骤，直到 k 个重心全部选举完成
  5. 如此，初始重心全部选举完成

3.3 迭代多少次合适 #

最坏情况下我们需要的迭代次数是：

\[{\displaystyle i=2^{\Omega ({\sqrt {n}})}}{\displaystyle i=2^{\Omega ({\sqrt {n}})}}\]

因此，这最坏情况下的时间复杂度是超越多项式时间的。

四、K-Means 检索加速 #

当我们要做向量相似性检索时，默认需要和所有重心做距离计算，这里比较耗时，实际我们可以把重心之间的距离保存下来，利用三角不等式做查询优化，

  1. 假设我们有两个重心 c1，c2，需要检索的向量为 x
  2. x 和 c1 距离为 d(x, c1)； c1, c2 间距离我们已经保存，这里表示为 d(c1,c2)
1
2
3
4

# if 
d(x, c1) <= 1/2 * d(c1,c2)
# then
d(x, c1) <= d(x, c2)

原理很简单，只有当 c1, c2, x 三点共线的时候，才可能存在距离相等，这部分我们可以减少一次距离计算，提高性能。

reference:

me#leftshadow.com © 2014 - 2022