用Mahout实现K-means算法

Mahout中K-Means算法实现原理

在Mahout中，K-Means算法由两大部分组成：其一，外部的循环，即算法的准则函数不满足时要继续的循环；其二，循环的主体部分，即算法的主要计算过程。Mahout中实现的K-Means算法和上面对应，分别使用KmeansDriver来设置循环，使用KmeansMapper、KmeansReducer（KmeansCombiner设置后算法运行速度会提高）作为算法的主体部分。该算法的输入主要包含两个路径（或者说文件），其中一个是数据的路径，还有一个是初始聚类中心向量的路径，即包含k个聚类中心的文件。这里要求数据都是序列化的文件，同时要求输入数据的key设置为Text（这个应该是没有做硬性要求的），value设置为VectorWritable（这个是硬性要求的，和Canopy Clustering一样）。其实在该算法中可以通过设置参数来自动提取原始数据中的k个值作为初始中心点的路径，当然，如果读者要自己提供初始中心点的文件，也可以通过Canopy算法来得到聚类的中心点作为K-Means算法的初始中心点文件。

该算法在KmeansDriver中通过不断循环使用输入数据和输入中心点来计算输出（这里的输出都定义在一个clusters-N的路径中， N是可变的）。输出同样是序列文件，key是Text类型，value是Cluster类型。该算法的原理图如图3-11所示。

KmeansDriver通过判断算法计算的误差是否达到阈值或者算法循环的次数是否达到给定的最大次数来控制循环。在循环过程中，新的聚类中心文件路径，一般命名为“clusters-N”且被重新计算得到，这个计算结果是根据前一次的中心点和输入数据计算得到的。最后一步，是通过一个KmeansMapper根据最后一次的中心点文件来对输入文件进行分类，计算得到的结果放入到文件名为“clusteredPoints”文件夹中，这次任务没有combiner和Reducer操作。

KmeansMapper在setup函数中读取输入数据，然后根据用户定义的距离计算方法把这些输入放入到最近的聚类中心簇中，输出的key是类的标签，输出的value是类的表示值；KmeansCombiner通过得到Mapper的输出，然后把这些输出进行整合，得到总的输出；KmeansReducer通过设定一个Reducer来进行计算，接收所有的combiner的输出，把相同的key的类的表示值进行整合并输出。