Kmeans 聚类算法

一、Kmeans 聚类算法

Kmeans是一种无监督学习的代表。聚类是没有样本的标签的情况下，通过数据之间的内在关系把样本划分为若干的类别。增大类内聚，减少类间距。

聚类是通过迭代寻找K个簇(cluster) 的一种划分方案，使得聚类结果对应的损失函数最小。其中损失函数我们可以定义为各个样本到所属簇中心点的误差平方和：

J(c,\mu) = \sum_{i = 1}^{M}||x_i-\mu_{c_i}||^2

1.数据预处理。主要是标准化，异常点过滤

2.随机选取K 个中心点，记为 $\mu_1^{(0)},\mu_2^{(0)},\mu_3^{(0)},...,\mu_k^{(0)}$

3.定义损失函数： $J(c,\mu) = min\sum_{i = 1}^{M}||x_i-\mu_{c_i}||^2$

4.令 t = 0,1,2,3,…为迭代步数，重复如下过程直到 $J(c,\mu)$ 收敛

对于每一个样本 $x_i$ ,将其分配到距离最近的中心： $c_i^t:=argmin_k||x_i-\mu_k^t||^2$

对于每一个类中心K,重新计算该类的中心： $\mu_k^{t+1} :=argmin_\mu\sum_{i:c_i^t = k}^b||x_i-\mu ||^2$

1.优点：

复杂度O(KNt)接近于线性，收敛速度快。

2.缺点：

受初始值和异常点影响，聚类结果可能不是全局最优而是局部最优。

K是超参数，一般需要按经验选择。

样本点只能划分到单一的类中。