机器学习个人笔记——（一）分类算法3、k-means

时间 2021-06-06 标签个人笔记

k-means

k-means概念

K-Means算法是无监督的聚类算法，也是一个比较简单的聚类算法，效果明显。

例如在二维平面上，存在以下点，点的类别未知

通过k-means算法，可以得到以下三个簇。使用不同颜色标注出，点集被分为3个类别。

算法思想

现有样本集X，包含m个样本，每个样本n个特征
$\mathbf{X} =\begin{bmatrix} x_{11}&x_{12} & ...& x_{1n}\\ x_{21}&x_{22} & ...& x_{2n}\\ ...&...& ...& ...\\ x_{m1}&x_{m2} & ...& x_{mn}\\ \end{bmatrix}$
其中第i个样本为
$\mathbf{x_i} =\begin{bmatrix} x_{i1}&x_{i2} & ...& x_{in} \end{bmatrix}$

假设我们要把数据分成K个类，可以分为以下几个步骤：

k为人为设定

1. 随机选取k个点，作为聚类中心；
$\mathbf{R} =\begin{bmatrix} r_{11}&r_{12} & ...& r_{1n}\\ r_{21}&r_{22} & ...& r_{2n}\\ ...&...& ...& ...\\ r_{k1}&r_{k2} & ...& r_{kn}\\ \end{bmatrix},r_{ij}随机选取$

其中第i个聚类中心为
$\mathbf{r_i} =\begin{bmatrix} r_{i1}&r_{i2} & ...& r_{in} \end{bmatrix}$

2. 计算每个点分别到k个聚类中心的距离，然后将该点分到最近的聚类中心;
$\begin{aligned} dist(\mathbf{x_{i}},\mathbf{R}) & = dist(\begin{bmatrix} x_{i1}&x_{i2} & ...& x_{in} \end{bmatrix},\begin{bmatrix} r_{11}&r_{12} & ...& r_{1n}\\ r_{21}&r_{22} & ...& r_{2n}\\ ...&...& ...& ...\\ r_{k1}&r_{k2} & ...& r_{kn}\\ \end{bmatrix})\\&=\begin{bmatrix} d_{1}\\ d_{2}\\ ...\\ d_{k}\\ \end{bmatrix} \end{aligned}$
其中：
$d_{1}=\sqrt{(x_{i1}-r_{11})^{2}+(x_{i2}-r_{12})^{2}+...+(x_{in}-r_{1n})^{2}}$
$d_{2}=\sqrt{(x_{i1}-r_{21})^{2}+(x_{i2}-r_{22})^{2}+...+(x_{in}-r_{2n})^{2}}\\....$

每个样本与k个中心计算，得到k个距离

取距离最近的中心，其所对应的类别。 $l=getGroup(\min (d_{1},d{2},...,d_{k}))$
将该样本类别设置为 $l$

3. 重复步骤2直到所有点完成分类

4. 重新计算每个簇的质心（均值）；

当所有样本分类完成，分为了k个类别(簇)后
$\begin{aligned} &l_1:m_{1}个样本\\ &l_2:m_{2}个样本\\ &...\\ &l_k:m_{k}个样本 \end{aligned}$

分别求各个簇中样本的均值，将簇的质心变为该均值

5. 重复以上2~4步，直到质心的位置不再发生变化或者达到设定的迭代次数；