MapReduce 算法基础教程文档
收录于 2023-04-20 00:10:05 · بالعربية · English · Español · हिंदीName · 日本語 · Русский язык · 中文繁體
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 阶段 处理每个输入文件并以键值对(
<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 中通常使用的索引技术被称为
倒排索引。 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。