每周学点大数据 | No.54聚类算法——k-means

NO.54

聚类算法——k-means

首先我们从聚类算法说起。前面讲过，聚类算法是在没有训练集的情况下对要分析的数据进行一个类别划分。简单来说，就是直接观察数据的分布，将它们“聚集”成多个类别。聚类算法最经典的一个问题叫作k-cluster。简单来说，就是现在有一批数据，我们要根据这批数据

的值将它们划分成k 类。

对其进行一个形式化的定义，就是：

输入——在一个n 维特征空间里面的数据项集合。

输出——划分为k 个类别的数据项。

小可：这个n 维特征空间是什么？

Mr. 王：有一个数据域的数据我们叫它一维数据，有两个数据域的数据就是二维数据。相应的，n 维数据有n 个数据域，n 维数据可以取值的范围就是一个n 维空间。比如最简单的二维数据就是平面上的点，它有横坐标x 和纵坐标y，它们构成的数据对(x,y) 就在一个平面上，这个平面就是一个二维空间。在比较复杂的数据中，可以是温度、质量、体积、硬度这样的高维数据，它们就在温度、质量、体积、硬度取值范围组成的一个四维空间里面。我们要做的，就是对这个空间内的这些数据进行一个类别划分，分成k 类。k 的值是预先确定的，比如现在平面上有100 个点，我们要将它们分成3 类。

小可：如果是把平面上的点分成3 类的话，我就看哪些点离得近，在图上看是一堆，那就是一类呗。

Mr. 王：其实这就是聚类算法的思想。我们直观感受到的那些距离近的点，在各个数据维度上就会比较相近，我们就更倾向于认为它们是一类的。

这就是一个非常典型的k-cluster 问题。在一个二维空间xOy 中，有很多个点，这些点就代表有X 和Y 这两个数据域的一些数据项（item），而它们就可以直观地根据距离进行一个聚类划分，变成cluster。

小可：那么能将数据项划分成cluster 的具体算法是什么呢？

Mr. 王：在聚类算法中，最经典也是最具代表性的就是k-means 算法，也称作k- 均值算法。为了方便起见，我们用二维空间进行举例，通过一个实例来看看k-means 算法是怎么做的。假设有这样一组数据：

这是由年龄和支出组成的二维空间，空间中的点都是由( 年龄, 支出) 这样的二元组构成的数据项。如果k 为2，也就是将这些点分成两类，我们看看k-means 是如何解决的。

第1 步：在空间中随机选取k 个点，在这里由于k=2，所以我们选择两个点。一般为了方便起见，所选择的点就是某一个数据项，所以这一步也可以改为从数据项中随机选取k 个点。所选出来的k 个点，我们称之为均值。

第2 步：现在有了k 个均值，接下来让所有的点去计算其与哪个均值的距离更近。每一个

点都会选择距离最近的一个均值，将其归入到该均值代表的类别中。

小可：从目前的结果来看，左下角的两个点(10,10),(15,12) 被归为一类，(11,16),(18,20),(20,21),(30,21) 这四个点被归为一类。但是好像不是很准确，(11,16) 这个点还是归入到左下角这一类更加准确，左下角的这三个点从直观上来看更加接近啊。

Mr. 王：别急，下面是算法的第3 步。

第3 步：计算已经在前一步中形成的类别的均值。所采用的方法就是求这一类别中所有的点在各个数据维度上的算术平均数，这样就可以得到一个新的均值。就像下面的图一样，左下角的五角星是左下角两个点的均值，右上角的五角星是右上角四个点的均值。此时的均值很有可能不再是某一个数据项。

第4 步：现在我们又有了k 个均值，再次让所有的点去计算其与哪个均值的距离更近。每一个点都会重新选择距离最近的一个均值，将其归入到该均值代表的类别中，此时新的类别划分就产生了。上图中的红色箭头，就是每一个点新发现的最近的均值。重复执行第3 步和第4 步，直到类别的结果不再发生变化为止。

小可：也就是产生了不动点？

Mr. 王：是的。

小可：这回从直观上看结果好像已经不错了，相近的点都已经聚集在一起了。不过还有一个小问题，一开始我们随机选择均值，真的没有问题吗？

Mr. 王：你注意到了这个问题很好。其实可以证明，最初的均值随机选择并不会影响最终的聚类结果。但是并不意味它对算法是毫无影响的，如果所选择的点恰巧比较接近分类完成后的均值，那么算法收敛的速度就会变得快一些；如果所选择的点不够好，那么就会造成算法经过很多轮迭代才能收敛。也就是说，最初的均值随机选择，虽然不会影响算法的结果，但是会影响算法收敛的速度。

小可：怪不得要选择一些数据项作为初始点呢，这样比在空间中随机选择更接近聚类完成

后的均值。

Mr. 王：不过这个算法也不是完美的，它也有缺陷。

小可：看起来得出的结果挺准确啊，哪里不好呢？

Mr. 王：在实际使用的数据中，非常有可能出现噪声或者离群点。大部分点都集中在某个区域里面，但是有几个点距离其他的点都非常远。你可以想一想，这样的点会使得我们求出的均值非常偏离大部分点所在的小区域，会造成聚类在一定程度上不准确。我们说k-means 对于含有噪声和离群点的数据是不健壮的。

小可：那么怎么解决呢？

Mr. 王：后来计算科学家们提出了一种对k-means 的改进算法，这种算法叫作k- 中心点算法。

小可：哦，它和k-means 有什么区别呢？

Mr. 王：它对k-means 确定均值的方法做了一个小小的改进。k-means 的每一步直接采用每一个聚类中点的均值作为该聚类的中心；而k- 中心点算法在求出了均值之后，会选择一个距离均值最近的数据项作为这个聚类的中心，这样可以非常有效地避免求出来的中心处在一个非常偏离大量数据点的位置上。

小可：嗯，这样的话计算步骤不就变多了吗？每一轮多了一个操作，而且确定这个中心点对于海量的数据点来说也是开销很大的吧？

Mr. 王：没错，不难看出，k- 中心点算法的开销要比k-means 大得多。所以在实际应用中，我们就要权衡哪一种算法更适合于解决所要进行聚类的大数据集合。后来，科学家们也开发出了各种数据预处理技术，可以预先对数据进行离群点检测和清洗，我们也可以采用数据离群点清洗的方法来加强k-means 运行稳定性。

小可：那么k-means 在MapReduce 平台上又该如何实现呢？

Mr. 王：好，接下来我们看看如何把k-means 套用到MapReduce 框架中。显然这也需要多轮迭代MapReduce。我们可以做如下的设计：别忘了，在设计MapReduce 算法时，首先要设计键值对。

数据点ID → < 位置, 均值 ID, [ 均值ID 集合和位置集合]>其中，数据点ID 表示数据项编号，用于区分数据项，位置是该数据点在空间中的位置；均值ID 是每一轮中已经确定的，它目前属于的均值ID ；后面的两个集合是目前已有的所有的均值ID 及其位置。这里的均值ID 可以用于最终标注分类的结果，比如可以称它们为第一类、第二类、第三类等。于是，在Map #1 中，输入数据点ID → < 位置, 均值ID, [ 均值ID 集合和位置集合]> 键值对每个数据点要去距离最近计算自己最近的均值，然后发出均值 ID → < 数据点 ID, 位置> 键值对，这样就可以表示出一个在某特定位置、编号为数据点ID 的点本轮被划归到具有某一个均值ID 的类别中。

在Reduce #1 中，Reducer 会收集到大量的均值ID → < 数据点ID, 位置>，以便于重新计算属于一个均值ID 的数据点的均值。这可以通过这些数据点的实际位置进行计算。然后输出为数据点ID → < 数据点ID 集合, 位置集合>，并且对于除了自己以外的那些均值ID, 还要发出其他均值ID →位置( 均值ID 集合, 位置)，以便于这些均值可以有效地知道其他均值所在

的位置。

在Map #2 中，直接将一轮MapReduce 的值结果发送给Reduce #2。

在Reduce #2 中，对于在当前均值所代表的类别中的每一个节点，会输出数据点ID → <位置, 均值ID, [ 均值ID 集合和位置集合]> 键值对。不难看出，它与Map #1 的输入是一样的，这样就可以让MapReduce 进行一轮轮迭代，最后得出结论。同时，Reduce #2 还要输出

如果MapReduce 能够在这一轮中停止，那么后面输出的这一项将成为最终结果。

当整个过程达到不动点时，也就是在执行过程中各节点归属的类别不再发生变化时，整个算法执行完毕，系统停机即可。

上述过程形成一个规范的MapReduce 流，如下所示

Map #1 ：

输入：数据点ID → < 位置, 均值ID, [ 均值ID 集合和位置集合]>

发出：均值 ID → < 数据点 ID, 位置>

Reduce #1 ：

输入：均值ID → < 数据点 ID, 位置>

重新计算属于一个均值ID 的数据点的均值。

输出：数据点ID → < 数据点ID 集合, 位置集合>

其他均值ID →位置( 均值ID 集合, 位置)

Map #2 ：

直接将一轮MapReduce 的值结果发送给Reduce #2。

Reduce #2 ：

输入：Map #2 传递过来的数据。

输出：数据点ID → < 位置, 均值ID, [ 均值ID 集合和位置集合]> 键值对

这样我们就成功地通过MapReduce 实现了k-means 算法。在实际应用中，k-means 算法的输入数据量往往是非常大的，使用像MapReduce 这种并行平台是非常常见的。另外，当我们希望使用并行工具来解决一些数据挖掘问题时，可以使用一些现有的开源工具包，这样可以让我们的工作变得更加简捷。

一个很有代表性的工具就是由Apache 基金会推出的开源数据挖掘工具包Mahout。Apache Mahout 基于Apache Hadoop（Hadoop 是一个MapReduce 开源实现版本），是一种可伸缩的数据挖掘工具包，可伸缩性可以非常有效地面对各种较大的数据规模。它可以帮助我们非常方便地完成频繁模式挖掘、分类和聚类的一些操作，其中有很多使用非常方便的API，可以直接调用它们，使得数据挖掘工作变得轻松容易。在Apache Mahout 中，已经为我们预先实现了一些较好的聚类算法，包括k-means、k-means的模糊版本、Canopy、Mean Shift 等。当我们要进行一些简单的聚类时，可以直接使用这些组件包的库函数。

其实不论是k-means 还是k- 中心点算法在思想上都有一个小缺陷。K- 中心点虽然有效地降低了噪声和离群点对算法的影响，但是依然没有解决一个问题，就是像k-means 这样的k-cluster 问题，也就是都需要先指定一个k 出来。所以在有些情况下，指定这个k 值可能会成

为一个麻烦。如果大量的数据分布非常的密集、杂乱，很难从直观上看出这些大量杂乱的点应该分成几类时，我们所指定的不准确的k 值也有可能影响聚类结果。

小可：的确，k-means 的每一轮都要算出k 个均值，如果不知道k 是多少，那就无法运行了。如果给出一个不准确的，又不能最好地代表数据的分布情况。

Mr. 王：所以k-means 也不是一种万能的聚类方法。至于对这种问题的解决，科学家们提出了基于密度的聚类方法，在这里我就不展开谈了。如果你有兴趣，可以去查阅一些关于DBSCAN 算法的书籍和论文，相信会很有帮助的。

文章作者：王宏志

文章编辑：秦革