华章计算机 + 关注
手机版

《Hadoop与大数据挖掘》一2.5.3 Hadoop K-Means算法实现思路

  1. 云栖社区>
  2. 华章计算机>
  3. 博客>
  4. 正文

《Hadoop与大数据挖掘》一2.5.3 Hadoop K-Means算法实现思路

华章计算机 2017-06-26 10:22:00 浏览1554 评论0

摘要: 本节书摘来华章计算机《Hadoop与大数据挖掘》一书中的第2章 ,第2.5.3节,张良均 樊 哲 位文超 刘名军 许国杰 周 龙 焦正升 著 更多章节内容可以访问云栖社区“华章计算机”公众号查看。 2.5.3 Hadoop K-Means算法实现思路 针对K-Means算法,本节给出两种实现思路。

本节书摘来华章计算机《Hadoop与大数据挖掘》一书中的第2章 ,第2.5.3节,张良均 樊 哲 位文超 刘名军 许国杰 周 龙 焦正升 著 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.5.3 Hadoop K-Means算法实现思路

针对K-Means算法,本节给出两种实现思路。思路1相对比较直观,但是效率较低;思路2在实现上需要自定义键值类型,但是效率较高。下面是对两种思路的介绍。
思路1
如图2-47所示,算法描述如下:
1)根据原始文件生成随机聚类中心向量(需指定聚类中心向量个数k),指定循环次数;
2)在map阶段,setup函数读取并初始化聚类中心向量;在map函数中读取每个记录,计算当前记录到各个聚类中心向量的距离,根据到聚类中心向量最小的聚类中心id判断该记录属于哪个类别,输出所属聚类中心id和当前记录;
3)在reduce阶段,reduce函数接收相同聚类中心id的数据;把这些数据的每列进行求和,并记录每列的个数;计算新的聚类中心向量(每列的和除以每列的个数),然后输出聚类中心id和新的聚类中心向量;
4)判断前后两次聚类中心向量之间的误差是否小于某阈值;如果小于,则跳转到步骤5),否则跳转到步骤2);
5)针对最后一次生成的聚类中心向量对原始数据进行分类,得到每个记录的类别。
其MR数据流如图2-48所示。


image


思路2
如如图2-49所示,算法描述如下:
1)根据原始文件生成随机聚类中心向量(需指定聚类中心向量个数k),指定循环次数。
2)在map阶段,setup函数读取并初始化聚类中心向量,同时初始化聚类中心向量和;在map函数中读取每个记录,计算当前记录到各个聚类中心向量的距离,根据到聚类中心向量最小的聚类中心id判断该记录属于哪个类别,然后把所属的类别加入到聚类中心向量和中(需要记录个数及和,即需要自定义类型);在cleanup函数中输出所属聚类中心id和其对应的聚类中心向量和。

image


3)在reduce阶段,reduce函数接收相同聚类中心id的数据;把这些数据的每列进行求和,并记录每列的个数;计算新的聚类中心向量(每列的和除以每列的个数),然后输出聚类中心id和新的聚类中心向量。
4)判断前后两次聚类中心向量之间的误差是否小于某阈值;如果小于,则跳转到步骤5),否则跳转到步骤2)。
5)针对最后一次生成的聚类中心向量对原始数据进行分类,得到每个记录的类别。
其MR数据流如图2-50所示。

【云栖快讯】阿里巴巴小程序繁星计划,20亿补贴第一弹云应用免费申请,限量从速!  详情请点击

网友评论