机器学习入门笔记系列（9） | K-means 算法

2018-10-01 本文已影响5人胖三斤66

$c^{(i)} =$ 样本 $x^{(i)}$ 被分配到的簇的索引{1,2, ..., K}
$u_k =$ 第 k 簇的聚类中心

一、K-means 执行过程

K-Means 算法是最流行和广泛使用的无监督学习算法，用于自动将数据分组为相干子集。K-Means 算法属于聚类算法

下图展示 K = 2 时 K-means 算法执行过程实例。

K-means 聚类过程

用文字总结一下 K=2时， K-means 算法的执行过程：

通过上述的执行过程，K-means 算法实现如下：

K-means 算法

Tips : 如果出现有一个聚点在归类完成后，没有一个样本点属于该簇。通常做法是删除该聚点，此时变成 K-1 means；也可以没有初始化聚类中心

K-means 代价函数

简单的来解释，代价函数 = 每个样本与所在簇的聚类中心的距离平方的平均值

我们的优化目标就是 $min_{c,u}~J(c,u)$ 。如何实现这优化目标呢？

其实实现 $min_{c,u}~J(c,u)$ 一直贯穿于 K-means 算法。

簇分配：我们固定了聚类中心，即固定了 $\{u_1,..,u_K\}$ ，将样本分配到离它最近的聚类中心所在的簇中，这相当于当固定 $\{u_1,..,u_K\}$ ，通过改变 $\{c^{(1)}, .., c^{(m)}\}$ 来 $min_{c,u}~J(c,u)$ ；
更新聚类中心：我们固定了每个样本所在的簇，即固定了 $\{c^{(1)}, .., c^{(m)}\}$ ，计算每个簇的所有点的平均值并更新为簇的新的聚类中心，即改变了 $\{u_1,..,u_K\}$ ，这就实现 $min_{c,u}~J(c,u)$ 。