1. Chine King
  2. Kmeans

Wiki

Clone wiki

Kmeans / Home

介绍

海量数据分析(Massive Data Processing)课程实验。主要用hadoop来实现Kmeans聚类算法。实验主要是要求将一系列的电影数据用Kmeans算法进行分类。

说明

实验所使用的kmeans语料默认放在HDFS下的“/kmeans/in”中。运行的结果在“/kmeans/result“中。

原理

k-means算法是数据挖掘中的基础算法。它要求把一个点集聚合成若干个簇,簇间的点尽可能的聚合在一起。k-means 算法接受输入量 k,然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。

k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。

对于使用MapReduce来处理此程序,需要多次的迭代过程,所以k-means程序也可以代表需要不断迭代的程序集合。在每一次的迭代过程中,Map任务读入点集数据中的一个子集,并把中心点向量读入,以中心点向量来判断每一个点是否应该输入那个中心下的簇。它计算出每个点和中心点向量中的距离并把点分派给最近的簇。而Reduce任务把相同簇的点都聚合到一起,然后重新计算它们的中心点,然后更新中心点向量。一轮迭代结束后,k-means程序会继续迭代直到满足收敛条件为止。收敛的条件一般为两轮对比各个簇没有大的变化就可以停止迭代。

由于初始数据集较大,迭代的效率会比较低,为了提高效率,在采用K-Means算法之前,我们采用了Canopy算法,将所有n个对象划分为若干有交叉的Canopy(每个对象至少落入一个Canopy中,一个对象可属于多个Canopy),这样做的好处是,在后续K-Means算法中,可以减少大量的距离计算,任意一个对象只和与它同在一个Canopy的中心点计算距离(可以证明,若两个对象不在同一个Canopy中,那么他们也不会在同一个聚类中),从而大大提高算法的效率。关于Canopy算法的更多信息,可以参见:www.kamalnigam.com/papers/canopy-kdd00.pdf

步骤分为以下几步:

  1. 解析原始数据
  2. 生成Canopy中心点
  3. 输入解析的原始数据,生成每个电影所落在的Canopy中心点
  4. 计算Kmeans中心点,并进行迭代
  5. 输出结果

解析原始数据

原始数据为一系列文件。每个文件的第一行为电影id,如“1:”。从第二行开始,每行由“,”分隔的三部分组成,分别是评价的UserId,评分,以及timestamp。这里我们只需要UserId和评分,所以在Map任务中我们以MovieId作为key,“,”分隔的UserId和评分作为value输出。在reduce任务中,我们把一系列的value值以“;”分隔。这个任务在包com.chine.kmeans.mapreduce.dataprep中。

生成Canopy中心点

接下来我们要计算一系列的Canopy中心点。我们保存一个列表,并迭代解析生成的数据,如果该电影和列表中的一个电影评价的共同好友数大于一定阈值(这里我们设这个阈值为T1,并设为8),我们就不会将该电影加入到这个列表中。map和reduce做同样的事情,区别在于map任务对每个分片执行以上任务,reduce任务得到map的数据,并再次计算,最后得出一系列的中心点,它们之间两两共同好友数都是小于T1值的。值得注意的是,这里的reduce任务数量必须只为1。这里我们输出电影的id作为key,以及电影的一系列数据(评价用户id和评价值)作为value。这个任务在包com.chine.kmeans.mapreduce.canopymaker中。

输入解析的原始数据,生成每个电影所落在的Canopy中心点

对于解析的原始数据,我们与每个Canopy中心点进行比较,如果共同的评价用户数大于一个阈值(这里设阈值为T2,并设为2,T1和T2称为Canopy中一远一近两个阈值),我们就认为这个电影属于这个Canopy中心点。最后,我们把MovieId作为key,一系列的Canopy中心点、MovieId、电影数据(MovieId和电影数据主要为了方便后面计算才输出)用“:”分割,作为value输出。这个任务在包com.chine.kmeans.mapreduce.canopydata中。

计算Kmeans中心点,并进行迭代

在这个任务开始之前,我们需要进行一些处理。我们读入Canopy中心数据,以及Kmeans中心数据(在第一次迭代时,就读入Canopy中心数据,Kmeans中心数据是迭代计算的结果),对于每个Canopy中心数据,如果每个Kmeans中心点与这个Canopy中心点的共同用户数大于T1,则把这个Kmeans中心点加入到属于这个Canopy中心点的列表中(这里我们用一个HashMap,键为Canopy中心点MovieId,值为一个List,其中保存一系列的Kmeans中心点)。

在接下来的说明之前,有必要说明一个电影Movie1和Movie2的距离,它是这么计算的:我们首先计算出共同评价的用户的评分,求其平方和,设为v1,再求出只在Movie1中评分用户评分的平方和v2,以及只在Movie2中评分的用户的评分平方和v3,那么复杂距离就是v1/sqrt(v2*v3),我们计算的时候计算(v1^2)/(v2*v3),这里要注意的是,如果两个电影之间全部由相同的用户评价,v2*v3就为0,作为除数,显然不合理,于是,我们重新计算结果为:(v1^2)/(v2*v3+1)。由于这种计算代价较大(对于大数据集来说,所以才需要采用Canopy算法预划分)。

完成了预处理之后,我们开始Map任务,拿上一步算到的Canopy数据,对于每个电影,我们知道它所在的Canopy中心,而这个Canopy中心又对应一系列的Kmeans中心。所以,这里我们计算每个电影与这些Kmeans中心点的距离,最后得到距离最大的,我们认为当前电影属于这个Kmeans中心,于是将Kmeans中心作为key输出,当前电影数据作为value输出。

在Reduce任务中,我们对于某个电影id的一系列的values,我们首先得到,某个用户他的评论的分数,求其平均数,最后输出userId1,averageRating1:userId2,averageRating2...,最后我们把它作为value,中心点的movieId作为key输出。这样就计算出了每个Kmeans中心点的数据。

接着重复以上过程,以进行迭代过程。处理在包com.chine.kmeans.mapreduce.kmeansiter中。

输出结果

最后的步骤中,我们简单地将kmeans中心点作为key,与这个中心点最近的电影作为value输出。处理在包com.chine.kmeans.mapreduce.resultsview中。

运行

下载Kmeans.jar。并运行:

hadoop jar Kmeans.jar

获得源码

$ hg clone https://bitbucket.org/chineking/kmeans

Updated