MapReduce 算法
MapReduce 算法包含两个重要任务，即 Map 和 Reduce。
- map任务是通过Mapper Class来完成的
- reduce 任务是通过 Reducer 类完成的。
Mapper 类接受输入，对其进行标记、映射和排序。 Mapper 类的输出被Reducer 类用作输入，Reducer 类依次搜索匹配对并减少它们。
MapReduce 实现了各种数学算法来将任务分成小部分并将它们分配给多个系统。在技术方面，MapReduce 算法有助于将 Map & Reduce 任务发送到集群中的适当服务器。
这些数学算法可能包括以下内容：
- Sorting
- 搜索
- Indexing
- TF-IDF
Sorting
排序是处理和分析数据的基本 MapReduce 算法之一。 MapReduce 实现了排序算法，通过键对映射器的输出键值对进行自动排序。
-
排序方法在映射器类本身中实现。
-
在 Shuffle 和 Sort 阶段，在对映射器类中的值进行标记后， Context class(用户定义的类)将匹配的值键收集为一个集合。
-
为了收集相似的键值对(中间键)，Mapper 类借助 原始比较器 类对键值对进行排序。
-
给定 Reducer 的中间键值对集合由 Hadoop 自动排序以形成键值(K2，{V2，V2，...})，然后再呈现给 Reducer。
搜索
搜索在 MapReduce 算法中起着重要的作用。它有助于组合器阶段(可选)和减速器阶段。让我们试着通过一个例子来理解搜索是如何工作的。
例子
以下示例显示了 MapReduce 如何使用搜索算法来找出给定员工数据集中获得最高薪水的员工的详细信息。
-
假设我们在四个不同的文件中有员工数据：A、B、C 和 D。我们还假设由于重复从所有数据库表中导入员工数据，所有四个文件中都有重复的员工记录。请参见下图。
-
地图阶段 处理每个输入文件并以键值对 (
) 的形式提供员工数据。请参见下图。
-
合路器阶段 (搜索技术)将接受来自 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;
}
预期结果如下：
|
-
减速器阶段 ： 形成每个档案，你会找到薪水最高的员工。为避免冗余，请检查所有
<gopal, 50000>
Indexing
通常索引用于指向特定数据及其地址。它对特定 Mapper 的输入文件执行批量索引。
MapReduce 中通常使用的索引技术称为 倒排索引。 谷歌和必应等搜索引擎使用倒排索引技术。让我们尝试通过一个简单的示例来了解索引是如何工作的。
例子
以下文本是倒排索引的输入。这里 T[0]、T[1] 和 t[2] 是文件名，它们的内容用双引号引起来。
T[0] = "it is what it is" T[1] = "what is it" T[2] = "it is a banana"
应用 Indexing 算法后，我们得到以下输出：
"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 次。 TF 为 hive 那么 (50 / 1000) = 0.05。
现在，假设我们有 1000 万个文档和单词 hive 出现在其中的 1000 个中。然后，IDF 计算为 log(10,000,000 / 1,000) = 4。
TF-IDF 权重是这些量的乘积： 0.05 × 4 = 0.20。