MapReduce 算法
MapReduce 算法包含两个重要任务,即 Map 和 Reduce。
map 任务是通过 Mapper 类完成的
reduce 任务是通过 Reducer 类完成的。
Mapper 类接受输入、标记它、映射和排序它。 Mapper 类的输出被 Reducer 类用作输入,后者依次搜索匹配对并减少它们。
MapReduce 实现了各种数学算法,将任务分成小部分并将它们分配给多个系统。在技术方面,MapReduce 算法有助于将 Map & Reduce 任务发送到集群中的适当服务器。
这些数学算法可能包括以下内容-
Sorting
Searching
Indexing
TF-IDF
Sorting
排序是处理和分析数据的基本 MapReduce 算法之一。 MapReduce 实现了排序算法,自动按键对映射器的输出键值对进行排序。
排序方法在映射器类本身中实现。
在 Shuffle 和 Sort 阶段,在对映射器类中的值进行标记化后,Context 类(用户定义的类)将匹配的值键收集为一个集合。
为了收集相似的键值对(中间键),Mapper 类借助 RawComparator 类对键值对进行排序。
给定 Reducer 的一组中间键值对由 Hadoop 自动排序以形成键值(K2、{V2、V2、...}),然后再将它们呈现给 Reducer。
Searching
搜索在 MapReduce 算法中扮演着重要的角色。它有助于组合器阶段(可选)和减速器阶段。让我们通过一个例子来尝试理解搜索是如何工作的。
示例
以下示例显示MapReduce 如何使用 Searching 算法找出给定员工数据集中薪水最高的员工的详细信息。
假设我们有四个不同文件中的员工数据-A、B、C 和 D。我们还假设所有四个文件中都有重复的员工记录,因为重复从所有数据库表中导入员工数据。请参阅下图。
Map 阶段 处理每个输入文件并以键值对(
:
)的形式提供员工数据。请参阅下图。
组合器阶段(搜索技术)将接受来自 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 阶段-形成每个文件,您将找到薪水最高的员工。为避免冗余,请检查所有
对并消除重复条目(如果有)。在来自四个输入文件的四个
对之间使用相同的算法。最终输出应如下-
Indexing
通常索引用于指向特定数据及其地址。它对特定 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 的缩写。它是常见的网络分析算法之一。此处,术语"频率"是指术语在文档中出现的次数。
Term Frequency (TF)
它衡量特定术语在文档中出现的频率。它的计算方法是某个词在文档中出现的次数除以该文档中的总词数。
TF(the) = (Number of times term the ‘the’ appears in a document) / (Total number of terms in the document)
Inverse Document Frequency (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 万个文档,并且
hive 一词出现在其中的 1000 个中。然后,IDF 计算为 log(10,000,000/1,000) = 4、
TF-IDF 的重量是这些量的乘积 − 0.05 × 4 = 0.20。