实例思路

Top K问题

问题描述
在搜索引擎领域中，常常需要统计最近最热门的K个查询词
从海量查询中统计出现频率最高的前K个

解决思路
该问题可分解成两个MapReduce作业，分别完成统计词频和找出词频最高的前K个查询词的功能
两个作业存在依赖关系，第二个作业需要依赖前一个作业的输出结果
第一个作业是典型的WordCount问题
对于第二个作业，首先map()函数中输出前K个频率最高的词，然后由reduce()函数汇总
每个Map任务得到的前K个查询词，并输出频率最高的前K个查询词

K-means聚类

问题描述
K-means是一种基于距离的聚类算法。
它采用距离作为相似性的评价指标，认为两个对象的距离越近，其相似度就越大
该算法解决的问题可抽象成：给定正整数K和N个对象，如何将这些数据点划分为K个聚类？

解决思路
首先随机选择K个对象作为初始中心点
然后不断迭代计算，直到满足终止条件（达到迭代次数上限或者数据点到中心点距离的平方和最小）
在第I轮迭代中，map()函数计算每个对象到中心点的距离，选择距每个对象object最近的中心点center_point，并输出<center_point, object>对
reduce()函数计算每个聚类中对象的距离均值，并将这K个均值作为下一轮初始中心点