kmeans

1. kmean算法

* 步骤

设输入样本：$S=x_1,x_2,...,x_m$

• 初始化选择k个中心：$\mu_1,...,\mu_k$

• 对于每个样本$x_i$,将其标记为距离类别中心最近的类别

$label=arg\min\limits_{1\leq j\leq k}||x_i-\mu_j||$

• 将每个类别的中心更新为隶属该类别的所有样本的均值

$\mu_j=\frac{1}{|c_j|}\sum\limits_{i\in c_j}x_i$

• 重复最后两步，知道中心点变化小于某阈值

1.1 kmeans++

初始化的seed点应该尽可能远

* 算法

• 从输入的数据点集合中随机选择一个点作为第一个聚类中心
• 对于数据集中的每一个点x，计算它与最近聚类中心(指已选择的聚类中心)的距离D(x)
• 选择一个新的数据点作为新的聚类中心，选择的原则是：D(x)较大的点，被选取作为聚类中心的概率较大
• 重复2和3直到k个聚类中心被选出来
• 利用这k个初始的聚类中心来运行标准的k-means算法

从上面的算法描述上可以看到，算法的关键是第3步，如何将D(x)反映到点被选择的概率上，一种算法如下

• 先从我们的数据库随机挑个随机点当“种子点”
• 对于每个点，我们都计算其和最近的一个“种子点”的距离D(x)并保存在一个数组里，然后把这些距离加起来得到Sum(D(x))。
• 然后，再取一个随机值，用权重的方式来取计算下一个“种子点”。这个算法的实现是，先取一个能落在Sum(D(x))中的随机值Random，然后用Random -= D(x)，直到其<=0，此时的点就是下一个“种子点”。
• 重复2和3直到k个聚类中心被选出来
• 利用这k个初始的聚类中心来运行标准的k-means算法

1.2 k-mediods(中值聚类)

它到其他所有（当前cluster中的）点的距离之和最小

1.3 缺点

• 需要知道k值
• 对初始点敏感
• 不适合非凸形状的簇