MapReduce - 算法

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

• 地图任务是通过Mapper Class完成的/li>

• reduce任务是通过Reducer Class完成的.

Mapper类接受输入，标记化它，映射并对其进行排序. Mapper类的输出被Reducer类用作输入，后者又搜索匹配的对并减少它们.

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

这些数学算法可能包括以下 :

• 排序

• 搜索

• 索引

• TF-IDF

排序

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

• 实现排序方法在mapper类本身.

• 在Shuffle and Sort阶段，在映射器类中对值进行标记后， Context 类(用户定义的类)将匹配的值键收集为集合.

• 要收集类似的键值对(中间键)，Mapper类将采用帮助 RawComparator 类对键值对进行排序.

• 给定Reducer的中间键值对的集合是在呈现给Reducer之前，由Hadoop自动排序以形成键值(K2，{V2，V2，...}).

搜索

搜索在MapReduce算法中起着重要作用.它有助于组合器阶段(可选)和减速器阶段.让我们尝试通过示例来理解搜索是如何工作的.

示例

以下示例显示了MapReduce如何使用搜索算法查找在给定员工数据集中绘制最高薪水的员工的详细信息.

• 让我们假设我们有员工数据四个不同的文件和减号; A，B，C和D.我们还假设所有四个文件中都有重复的员工记录，因为重复从所有数据库表导入员工数据.请参阅下图.

• 地图阶段处理每个输入文件，并以键值对提供员工数据(< k，v>:< emp name，salary>).请参阅下图.

• 组合器阶段(搜索技术)将接受来自Map阶段的输入作为键值与员工姓名和薪水配对.使用搜索技术，组合器将检查所有员工薪水，以找到每个文件中受薪最高的员工.请参阅以下代码段.

Max= the salary of an first employee. Treated as max salaryif(v(second employee).salary > Max){   Max = v(salary);}else{   Continue checking;}

预期结果如下 :

• 减速阶段 : 从每个文件中，您将找到薪水最高的员工.为避免冗余，请检查所有< 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]文件中.类似地，"是":{0,1,2}意味着术语"是"出现在文件T [0]，T [1]和T [2]中.

TF-IDF

TF-IDF是一种文本处理算法，它是Term Frequency : 的缩写;反文档频率.它是常见的Web分析算法之一.这里，术语"频率"是指术语在文档中出现的次数.

术语频率(TF)

它衡量如何通常，特定术语出现在文档中.它的计算方法是单词出现在文档中的次数除以该文档中单词的总数.

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

反向文档频率(IDF)

它衡量一个术语的重要性.它是通过文本数据库中的文档数除以特定术语出现的文档数来计算的.

在计算TF时，所有术语都被视为同等重要.这意味着，TF计算正常单词的术语频率，如"是"，"a"，"什么"等.因此，我们需要通过计算以下和减去来扩展稀有单词时知道常用术语;

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.