MapReduce – 算法

MapReduce 算法包含两个重要的任务，即 Map 和 Reduce。

• map任务通过Mapper类完成
• reduce 任务是通过 Reducer 类完成的。

Mapper 类接受输入，对其进行标记化、映射和排序。Mapper 类的输出被 Reducer 类用作输入，它依次搜索匹配对并减少它们。

MapReduce 实现了各种数学算法，将任务分成小部分并将它们分配给多个系统。在技​​术方面，MapReduce 算法有助于将 Map & Reduce 任务发送到集群中的适当服务器。

这些数学算法可能包括以下内容 –

• 排序
• 搜索
• 索引
• TF-IDF

排序

排序是处理和分析数据的基本 MapReduce 算法之一。MapReduce 实现了排序算法，以自动按键对映射器的输出键值对进行排序。

• 排序方法在映射器类本身中实现。

• 在 Shuffle and Sort 阶段，在对 mapper 类中的值进行标记化后，Context类（用户定义的类）将匹配的 value键收集为一个集合。

• 为了收集相似的键值对（中间键），Mapper 类借助RawComparator类对键值对进行排序。

• 给定 Reducer 的一组中间键值对由 Hadoop 自动排序以形成键值 (K2, {V2, V2, …})，然后再将它们呈现给 Reducer。

搜索

搜索在 MapReduce 算法中扮演着重要的角色。它有助于组合器阶段（可选）和减速器阶段。让我们通过一个例子来理解搜索是如何工作的。

例子

下面的例子展示了 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 phase – 形成每个文件，你会找到最高薪水的员工。为避免冗余，请检查所有 <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 是一种文本处理算法，它是 Term Frequency – Inverse Document Frequency 的缩写。它是常见的网络分析算法之一。这里，术语“频率”是指术语在文档中出现的次数。

词频 (TF)

它衡量特定术语在文档中出现的频率。它的计算方法是一个单词在文档中出现的次数除以该文档中的单词总数。

TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)

逆向文档频率 (IDF)

它衡量一个术语的重要性。它的计算方法是文本数据库中的文档数除以出现特定术语的文档数。

在计算 TF 时，所有术语都被认为同等重要。这意味着，TF 会计算“is”、“a”、“what”等普通单词的词频。因此，我们需要通过计算以下公式来了解频繁词，同时扩大稀有词的比例 –

IDF(the) = log_e(Total number of documents / Number of documents with term ‘the’ in it).

下面通过一个小例子来解释该算法。

例子

考虑一个包含 1000 个单词的文档，其中单词hive出现了 50 次。hive的 TF 为(50 / 1000) = 0.05。

现在，假设我们有 1000 万个文档，其中1000 个中出现了hive一词。然后，IDF 计算为 log(10,000,000 / 1,000) = 4。

TF-IDF 重量是这些量的乘积 − 0.05 × 4 = 0.20。