手把手聚类算法之K-means算法原理及python实现

vlambda
2021-07-08

手把手聚类算法之K-means算法原理及python实现

数据视觉PPman

以数据为基础，通过数据分析、建模和数据可视化为手段，目的是描述真实，探索量化的世界，服务数据挖掘，数据建模和计量实证研究。

29篇原创内容

Official Account

概述

- Happy Halloween -

说到聚类算法，首先需要先介绍一下无监督学习。所谓无监督学习，就是训练样本中的标记信息是位置的，目标是通过对无标记训练样本的学习来揭示数据的内在性质以及规律。通俗地说，就是根据数据的一些内在性质，找出其内在的规律。而这一类算法，应用最为广泛的就是“聚类”。

聚类算法可以对数据进行数据归纳，即在尽可能保证数据完整的前提下，减少数据的量级，以便后续处理。也可以对聚类数据结果直接应用或分析。

而K-means 算法可以说是聚类算法里面较为基础的一种算法。

K-means算法

- Happy Halloween -

K-means算法采用距离作为相似性的评价指标，认为两个对象的距离越近，其相似度就越大。该算法认为簇是由距离靠近的对象组成的，因此把得到紧凑且独立的簇作为最终目标。

算法过程

1. 从n个文档中随机选取k个文档作为中心点；

2. 对剩余对每个文档测量其到每个中心点的距离，并把它归到最近的中心的类；

3. 重新计算已经得到的各个类的中心点；

4. 迭代m步直至新的中心与原来的中心相等或小于指定阈值，算法结束。

算法优缺点

优点：

1.对处理大数据集，该算法保持可伸缩性和高效性

2.算法快速、简单，易于理解;

缺点：

1.在K-means算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的，具体应用中只能靠经验选取；

2.对噪声和孤立点数据敏感，导致均值偏离严重；

3.当数据量非常大时，算法的时间开销是非常大的；

4.初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果。

代码演示

- Happy Halloween -

假设有两组数据X0和X1

import matplotlib.pyplot as pltimport numpy as npX0 = np.array([7, 5, 7, 3, 4, 1, 0, 2, 8, 6, 5, 3])X1 = np.array([5, 7, 7, 3, 6, 4, 0, 2, 7, 8, 5, 7])plt.figure()plt.axis([-1, 9, -1, 9])plt.grid(True)plt.plot(X0, X1, 'k.')

1. 随机选取中心：假设K-Means初始化时，随机设定两个中心，将第一个类的中心设置在第5个样本，第二个类的中心设置在第11个样本.那么我们可以把每个实例与两个中心的距离都计算出来，将其分配到最近的类里面。计算结果如下表所示：

新的中心位置和初始聚类结果如下图所示。第一类用X表示，第二类用点表示。中心位置用稍大的点突出显示。

C1 = [1, 4, 5, 9, 11]#属于C1的indexC2 = list(set(range(12)) - set(C1))#属于C2的indexX0C1, X1C1 = X0[C1], X1[C1]#属于C1的坐标X0C2, X1C2 = X0[C2], X1[C2]#属于C2的坐标plt.figure()plt.axis([-1, 9, -1, 9])plt.grid(True)plt.plot(X0C1, X1C1, 'rx')plt.plot(X0C2, X1C2, 'g.')plt.plot(4,6,'rx',ms=15.0)plt.plot(5,5,'g.',ms=15.0)

2. 重新计算中心：接下来我们需要重新计算两个类的中心，把中心移动到新位置，并重新计算各个样本与新中心的距离，并根据距离远近为样本重新归类。结果如下表所示：

C1 = [1, 2, 4, 8, 9, 11]C2 = list(set(range(12)) - set(C1))X0C1, X1C1 = X0[C1], X1[C1]X0C2, X1C2 = X0[C2], X1[C2]plt.figure()plt.axis([-1, 9, -1, 9])plt.grid(True)plt.plot(X0C1, X1C1, 'rx')plt.plot(X0C2, X1C2, 'g.')plt.plot(3.8,6.4,'rx',ms=12.0)plt.plot(4.57,4.14,'g.',ms=12.0)

3. 重复计算：接下来再重复一次上面的做法，把中心移动到新位置，并重新计算各个样本与新中心的距离，并根据距离远近为样本重新归类。结果如下表所示：

C1 = [0, 1, 2, 4, 8, 9, 10, 11]C2 = list(set(range(12)) - set(C1))X0C1, X1C1 = X0[C1], X1[C1]X0C2, X1C2 = X0[C2], X1[C2]plt.figure()plt.axis([-1, 9, -1, 9])plt.grid(True)plt.plot(X0C1, X1C1, 'rx')plt.plot(X0C2, X1C2, 'g.')plt.plot(5.5,7.0,'rx',ms=12.0)plt.plot(2.2,2.8,'g.',ms=12.0)