MapReduce - 算法
MapReduce 算法包含两个重要任务，即 Map 和 Reduce。
- map 任务通过 Mapper 类完成
- reduce 任务通过 Reducer 类完成。
Mapper 类获取输入、对其进行标记、映射和排序。Mapper 类的输出被 Reducer 类用作输入，Reducer 类依次搜索匹配对并对其进行归约。
MapReduce 实现各种数学算法，将任务划分为小部分并将它们分配给多个系统。从技术角度来说，MapReduce 算法有助于发送 Map &将任务减少到集群中的适当服务器。
这些数学算法可能包括以下内容 −
- 排序
- 搜索
- 索引
- TF-IDF
排序
排序是处理和分析数据的基本 MapReduce 算法之一。 MapReduce 实现了排序算法，可以按键自动对来自映射器的输出键值对进行排序。
排序方法在映射器类本身中实现。
在 Shuffle 和 Sort 阶段，在对映射器类中的值进行标记后，Context 类（用户定义类）将匹配的值键收集为一个集合。
为了收集相似的键值对（中间键），Mapper 类借助 RawComparator 类对键值对进行排序。
对于给定的 Reducer，Hadoop 自动对中间键值对集合进行排序，以形成键值（K2、{V2、V2、…}），然后再将它们呈现给 Reducer。
搜索
搜索在数据挖掘中起着重要作用在 MapReduce 算法中的作用。它有助于组合器阶段（可选）和 Reducer 阶段。让我们尝试借助示例了解搜索的工作原理。
示例
以下示例显示了 MapReduce 如何使用搜索算法找出给定员工数据集中薪水最高的员工的详细信息。
假设我们在四个不同的文件中有员工数据 - A、B、C 和 D。我们还假设由于重复从所有数据库表导入员工数据，所有四个文件中都有重复的员工记录。请参阅下图。
Map 阶段处理每个输入文件并以键值对 (<k, v> : <emp name, salary>) 的形式提供员工数据。请参阅下图。
组合器阶段（搜索技术）将接受来自 Map 阶段的输入，作为包含员工姓名和薪水的键值对。使用搜索技术，组合器将检查所有员工薪水，以在每个文件中找到薪水最高的员工。请参阅以下代码片段。
<k: employee name, v: salary>
Max= the salary of an first employee. Treated as max salary
if(v(second employee).salary > Max){
Max = v(salary);
}
else{
Continue checking;
}
预期结果如下 −
|
Reducer 阶段 − 从每个文件中找到薪水最高的员工。为避免冗余，请检查所有 <k, v> 对并消除重复条目（如果有）。来自四个输入文件的四个 <k, v> 对之间使用相同的算法。最终输出应如下所示 −
<gopal, 50000>
索引
通常使用索引来指向特定数据及其地址。它对特定 Mapper 的输入文件执行批量索引。
MapReduce 中通常使用的索引技术称为倒排索引。Google 和 Bing 等搜索引擎使用倒排索引技术。让我们借助一个简单的例子来理解索引是如何工作的。
示例
以下文本是倒排索引的输入。这里 T[0]、T[1] 和 t[2] 是文件名，其内容用双引号括起来。
T[0] = "it is what it is" T[1] = "what is it" T[2] = "it is a banana"
应用索引算法后，我们得到以下输出 −
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
这里 "a": {2} 表示术语 "a" 出现在 T[2] 文件中。类似地，"is"：{0, 1, 2} 表示术语"is"出现在文件 T[0]、T[1] 和 T[2] 中。
TF-IDF
TF-IDF 是一种文本处理算法，是词频减去逆文档频率的缩写。它是常见的网络分析算法之一。这里的"频率"是指术语在文档中出现的次数。
词频 (TF)
它衡量特定术语在文档中出现的频率。计算方法是将文档中单词出现的次数除以文档中的单词总数。
TF(the) = (文档中单词'the'出现的次数) / (文档中的单词总数)
逆文档频率 (IDF)
它衡量一个术语的重要性。计算方法是将文本数据库中的文档数除以出现特定术语的文档数。
在计算 TF 时，所有术语都被视为同等重要。这意味着，TF 会计算"is"、"a"、"what"等普通单词的词频。因此，我们需要了解频繁出现的术语，同时扩大罕见术语的规模，方法是计算以下 −
IDF(the) = log_e(文档总数 / 包含术语'the'的文档数)。
下面通过一个小例子来解释该算法。
示例
考虑一个包含 1000 个单词的文档，其中单词 hive 出现了 50 次。那么 hive 的 TF 就是 (50 / 1000) = 0.05。
现在，假设我们有 1000 万个文档，单词 hive 出现在其中的 1000 个文档中。那么 IDF 的计算方式为 log(10,000,000 / 1,000) = 4。
TF-IDF 权重是这些数量的乘积减去 0.05 × 4 = 0.20。
