K-means聚类算法介绍

c0d3n4m

上次给大家介绍了分类和聚类的区别和聚类的进一步介绍，大家看懂了吗？今天给想给大家进一步地介绍K-means聚类算法。
下面的段落内容从3开始算起，1的内容来自分类和聚类的区别,2的内容来自聚类的进一步介绍。

3K-means算法

目前常用的聚类算法k-means、k-modes、k-medoids等。

下面就让我们一起来学习其中最基本，也是最有代表性的“k-means”算法。

3.1 “k-means”算法步骤

在笔者的认知里，k-means聚类算法的步骤有5步，分别是：

        Step1：准备好要聚类的数据，并且决定要聚类的类别数（cluster_num）

        Step2：从所有的数据对象中随机选择k个数据对象作为k个类别中心。

（这k个数据对象是k个类别的中心）

（k一定要等于cluster_num!!!）

Step3：计算所有数据对象到类别中心的距离，并且判断数据对象属于哪一个类别

Step4：更换类别中心。

再次计算所有数据对象到类别中心的距离，并且判断数据对象属于哪一个类别。

判断更换类别中心前后所有数据对象所属的类别是否发生变换。

如果：

• 更换类别中心前后所有数据对象所属的类别没有发生变换，执行Step5。
  
• 更换类别中心前后存在数据对象所属的类别发生了变换，再次执行Step4。
  

Step5：确定聚类结果

>>  “k-means”算法流程图

>> “k-means”算法流程图 -END

估计大家看到这里都会懵圈，上面的文字和流程图确实理解起来是有困难的！但是接下来，我们就会用一个简单的例子来让大家明白“k-means”算法具体是怎么执行的！大家不要灰心，继续往下学吧！

3.2 “k-means”算法具体实例

Step1：

首先准备好需要聚类的数据。（为了便于大家理解，我们这里使用的是表2-1中的数据）

然后决定聚类的类别数量。本例中设置“聚类的类别数”为4，也就是说，所有的数据对象会被分为4个类别，即在这个实例中，cluster_num=4。
至此，Step1完成。
Step2：
接着要做的事是：从所有的数据中随机选择k个数据对象作为k个类别的中心，(k一定要等于cluster_num!!!）
在这个实例中，我们人为地设定: k=4=cluster_num，并且随机选了4个数据对象, 这四个对象的“学生姓名”属性是“方琪”、“吴豪”、“张三”、“李四”,见下图。

图3-2 4个类别中心
Step3:
接着，我们计算每一个数据对象到这4个类别中心点的距离，这里的“距离”指的是欧几里得距离。

---

还是不太理解“欧几里得”距离？
以上面的例子为例，方琪同学的成绩是（57，60），刘丹同学的成绩是（54，59），这两位同学的欧几里得距离是：

王一同学的成绩是（98，94），李力同学的成绩是（93，95），这两位同学的欧几里得距离是：

还是不太理解“欧几里得”距离？-END

---

接着，我们计算每一个数据对象与这4个类别中心的“欧几里得”距离。得到如表3-2所示的“距离矩阵”。
表3-2 “欧几里得”距离矩阵

根据表3-2, 我们可以把所有的学生分别归为4个类别：
①　类别1的学生：刘丹、方琪
②　类别2的学生：吴豪、宋渝
③　类别3的学生：张三
④　类别4的学生：王一、李力、李四
(注:具体的归类方法是看数据对象与哪个类别中心的“距离”最小；例如，王一同学与类别4中心的距离是他与所有类别中心的距离中最小的。故在此情况下，王一同学被归类为”“类别1”)

图3-3 第一次聚类的结果
Step4:
接着就使用k-means的方法重新计算4个类别的“新”中心
4类别的“新”中心计算过程是：
类别2、3、4的“新”中心坐标轴的计算步骤是：
类别2中的两个数据对象的成绩是（65，70）和（71，66）。那么新的类别中心的坐标轴是(68, 68)。
具体的计算公式是：

类别3中的数据对象的成绩是（84，85）。那么新的类别中心的坐标轴是(84, 85)。
具体的计算公式是：

类别4中的三个数据对象的成绩是（98，94）、（93、95）、（82，96）。那么新的类别中心的坐标轴是(91, 95)。
具体的计算公式是：

---

重新得到了4个类别的“新”中心后，我们需要判断“k-means”算法是否要继续执行下去。
判断条件：
①　得到这4个“新”中心的前后，所有的数据对象所属的类别没有变化过，则“k-means”算法结束。
②　得到这4个“新”中心的前后，有任何一个数据对象所属的类别变化了，则“k-means”算法继续执行（注：这两句话可能让你“云里雾里”的，但没关系！下面一起来看看这个实例！）
在更换类别中心前：
①　类别1的学生：刘丹、方琪
②　类别2的学生：吴豪、宋渝
③　类别3的学生：张三
④　类别4的学生：王一、李力、李四

---

更换类别中心前的“欧几里得”距离矩阵

更换类别中心前的“欧几里得”距离矩阵-END

---

得到4个类别的“新”中心后，我们需要重新计算所有数据对象与这4个“新”中心的“欧几里得”距离，得到表3-3。
表3-3 “欧几里得”距离矩阵（重新计算类别中心）

由表3-3可知，更换类别中心后：
①　类别1的学生：刘丹、方琪
②　类别2的学生：吴豪、宋渝
③　类别3的学生：张三
④　类别4的学生：王一、李力、李四
也就是说，所有的数据对象所属的类别都没有变过，那么“k-means”算法就结束了！
Step5：
在这样的情况下，我们取最后得到的聚类结果作为最终的聚类结果：
①　类别1的学生：刘丹、方琪
②　类别2的学生：吴豪、宋渝
③　类别3的学生：张三
④　类别4的学生：王一、李力、李四

---

如果您有看不懂的地方，欢迎在评论区留下你的“吐槽”！