上一节:
下一节:

  MapReduce 算法

  • MapReduce 算法

    MapReduce算法包含两个重要任务，即Map和Reduce。
    • Map - 任务是通过Mapper类完成的
    • reduce - 任务是通过Reducer类完成的。
    Mapper类接受输入，对其进行标记，映射和排序。Mapper类的输出由Reducer类用作输入，然后Reducer类搜索匹配对并精简它们。
    mapreduce
    MapReduce实现了各种数学算法，可以将任务分成小部分，然后将它们分配给多个系统。用技术单词来说，MapReduce算法有助于将Map＆Reduce任务发送到群集中的适当服务器。
    这些数学算法可能包括以下内容-
    • 排序
    • 搜寻
    • 索引
    • TF-IDF

  • 排序

    排序是处理和分析数据的基本MapReduce算法之一。MapReduce实现了排序算法，可以根据映射器的键自动对映射器的输出键值对进行排序。
    • 排序方法在Mapper类中实现。
    • 在Shuffle和Sort阶段中，在标记了Mapper类中的值之后，Context类（用户定义的类）将匹配的有值键作为集合进行收集。
    • 为了收集相似的键值对（中间键），Mapper类利用RawComparator类对键值对进行排序。
    • Hadoop将自动对给定Reducer的一组中间键值对进行排序，以形成键值（K2，{V2，V2，…}），然后再将其提供给Reducer。

  • 搜索

    搜索在MapReduce算法中起着重要作用。它在组合器阶段（可选）和Reducer阶段有帮助。让我们尝试借助示例来了解搜索的工作方式。
    例 - 以下示例显示了MapReduce如何使用Searching算法查找给定员工数据集中薪水最高的员工的详细信息。
    让我们假设我们在四个不同的文件A，B，C和D中拥有员工数据。我们还假设在四个文件中都有重复的员工记录，因为重复从所有数据库表中导入了员工数据。请参见下图。
    mapreduce
    Map阶段处理每个输入文件，并以键值对（<k，v>：<emp name，Salum>）提供员工数据。请参见下图。
    mapreduce
    组合器阶段（搜索技术）将接受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;
}
    预期结果如下- 
    
<satish, 26000>  -  <gopal, 50000>  <kiran, 45000>  - <manisha, 45000>
    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。
上一节:
下一节: