k-means

假设我们有一个样本集​，我们想将这些数据聚成指定数量的几类。这里，​。因为没有与​对应的标签​，因此，这是一个非监督的学习问题。

用k-means做聚类的具体步骤如下：

1. 随机初始化​个质心​，​

2. 重复以下操作，直到每个质心​的值不再改变

   • 对每个样本，找到离其最近的质心，即：
     
   • 根据属于质心的点来更新质心的值，即：
     
     其中，​为指示函数，即：
     

k-means存在的问题：

(1). 在最坏的情况下，k-means的时间复杂度是样本数量的超多项式(super-polynomial )

(2). k-means的聚类效果非常依赖于质心的初始值的选取

k-means++

k-means++可以很好的改善k-means对于质心初始值的依赖，k-means++的具体步骤如下：

1. 从样本集中随机选择一个样本作为第一个质心。

2. 从样本集中以概率选取下一个质心，为样本到质心的距离。如此循环，直到完成所有的个质心的选取。

3. 剩下的步骤与k-means中的第二步一样:

   • 对每个样本，找到离其最近的质心，即：
     
   • 根据属于质心的点来更新质心的值，即：
     

Refences:

1. stanford cs229 lecture notes

2. k-means++: The Advantages of Careful Seeding