K-means 算法

时间:2022-11-07 08:51:39

本学习笔记参考自吴恩达老师机器学习公开课

聚类算法是一种无监督学习算法。k均值算法是其中应用最为广泛的一种,算法接受一个未标记的数据集,然后将数据聚类成不同的组。K均值是一个迭代算法,假设我们想要将数据聚类成K个组,其方法为:

  1. 随机选择K个随机的点(称为聚类中心);
  2. 对与数据集中的每个数据点,按照距离K个中心点的距离,将其与距离最近的中心点关联起来,与同一中心点关联的所有点聚成一类;
  3. 计算每一组的均值,将该组所关联的中心点移动到平均值的位置;
  4. 重复执行2-3步,直至中心点不再变化

算法的数学表示

算法的输入(input):

K – 聚类的类别数

K-means 算法K-means 算法 - 无标签训练集,其中每个输入K-means 算法K-means 算法是都是一个n维的实数向量,即K-means 算法K-means 算法

假设K-means 算法K-means 算法分别表示K个类别的聚类中心,用K-means 算法K-means 算法来存储与第i个实例数据最近的聚类中心的索引(1,2,…,k),则K-均值算法的伪代码如下:

K-means 算法K-means 算法

算法分为2个步骤,第一个for循环是赋值步骤,即:对于每一个样例i,计算其应该属于的类。第二个for循环是聚类中心的移动,即:对于每一个类k,重新计算该类的质心。(注:算法执行过程中若出现没有分配点的聚类中心,可以直接移除该聚类中心)

目标函数及其执行细节

目标函数

K均值最小化的问题,是要最小化所有数据点与其所关联的聚类中心点之间的距离之和。因此k均值的代价函数为:

K-means 算法K-means 算法

K-means 算法K-means 算法

随机初始化

K均值算法执行开始时,通常随机初始化聚类中心点,即:随机选择K个训练实例,然后令K个聚类中心分别等于这K个训练实例。这就使得Kmeans算法存在一个缺陷:最后结果会依赖于初始化的情况,并且有可能使得代价函数停留在局部最小值处。

为了解决该问题,我们通常需要多次(50到1000次)运行K均值算法,每一次都重新进行初始化,最后再比较多次运行K-均值的结果,选择代价函数最小的结果。通常这种方法在K较小的时候(2-10)还是可行的;但是K较大,这么做可能不会有明显的改善,并且K较大时,通常第一次执行K均值也会得到一个不错的结果。典型的执行次数为100次。伪代码如下:

K-means 算法K-means 算法

选择聚类数K

没有所谓最好的选择聚类数的方法,通常是需要根据不同的问题,人工的进行选择。但是,当你想要确定最优聚类数K时,有一个值得一试的方法 - “肘部法则(Elbow method)”。该方法所做的就是不断的改变K值(from 1 to x),执行k-均值,然后画出代价函数与K值的变化曲线,选择“肘点处”的值作为K的取值。如下图:

K-means 算法K-means 算法

事实上,该方法并不常用,因为大多数情况下,我们通常会得到一个光滑下降的曲线,没有一个清晰的“肘点”,这样就不能果断的确定K的取值;即便若此,该方法还是值得推荐和尝试的。