K-means 是经典的聚类算法。

1.思想

给定 {n,k,{x(1),...,x(n)}}, 它们分别是样本个数， 要划分为k类， 和样本点。

1. 随机标出k个质心， 对每个样本计算出离它最近的质心， 这样就得到了最初的划分。
2. 根据已有的划分重新计算每类样本的质心， 于是得到了k个质心的新的位置。
3. 对每个样本计算出离它最近的质心， 这样就得到了迭代后的划分。
4. 重复步骤2与步骤3， 直至质心的位置变化相对稳定。 此时得到了最终的划分。

图1-1 K-means 迭代步骤的图解

该图中的k=2， 质心用不同颜色的×表示。

1.2 复杂度

O(point_count * dimension * center_count * loop), 即 样本个数 * 样本维度 * 聚类k的值 * 循环次数.

2. spherical k-means

spherical ,[‘sferɪk(ə)l], adj. 球形的，球面的；天体的
普通的距离度量用的是 Euclidean Distance, 使用 cosine similarity 的话, 那就是 spherical k-means.

3.备注

Q： 随机选取质心的位置， 会不会影响最终的划分？
A: 待解答。应该是会的.

Q： 如何证明随机选取质心位置，最终一定会收敛?
A : 待解答， 先参考他人博客

Q: 怎么选取一批样本的质心位置？
A: 样本都是用向量表示， 那么用简单的平均法x(centrioid)j=∑ix(i)j可以求得质心第j维分量的大小。

参考

1. quora, How-can-I-use-cosine-similarity-in-clustering-For-example-K-means-clustering