《Hadoop与大数据挖掘》——2.6　TF-IDF算法原理及Hadoop MapReduce实现

本节书摘来自华章计算机《Hadoop与大数据挖掘》一书中的第2章，第2.6节，作者 张良均 樊哲 位文超 刘名军 许国杰 周龙 焦正升，更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.6　TF-IDF算法原理及Hadoop MapReduce实现

2.6.1　TF-IDF算法原理

原理：在一份给定的文件里，词频（Term Frequency，TF）指的是某一个给定的词语在该文件中出现的次数。这个数字通常会被正规化，以防止它偏向长的文件（同一个词语在长文件里可能会比在短文件里有更高的词频，而不管该词语重要与否）。逆向文件频率（Inverse Document Frequency，IDF）是一个词语普遍重要性的度量。某一特定词语的IDF可以由总文件数目除以包含该词语的文件的数目，再将得到的商取对数得到。某一特定文件内的高词语频率，以及该词语在整个文件集合中的低文件频率，可以产生出高权重的TF-IDF。因此，TF-IDF倾向于过滤掉常见的词语，保留重要的词语。

举个例子来说，假如一篇文件的总词语数是100个，而词语“母牛”出现了3次，那么“母牛”一词在该文件中的词频就是3/100＝0.03。一个计算文件频率的方法是测定有多少份文件出现过“母牛”一词，然后除以文件集里包含的文件总数。所以，如果“母牛”一词在1000份文件出现过，而文件总数是10 000 000份的话，其逆向文件频率就是log(10 000 000/1 000)＝4。最后的TF-IDF的分数为0.03×4＝0.12。

2.6.2　Hadoop TF-IDF编程思路

这里不再给出TF-IDF的单机算法实现，而直接给出其Hadoop算法实现思路，如图2-52所示。

具体算法描述如下。

Job1：针对每个文件集中的每个输入文件，分别统计其各个单词出现的次数，输出为<单词w|文件名f，该单词w在文件f中出现的次数f-w-count>。

Job2：针对Job1的输出，统计文件f中所有单词的个数（及一共有多少个唯一的单词），输出为<单词w|文件名f，该单词w在文件f中出现的次数f-w-count |文件f中的单词数f-length>。

Job3：先统计文件集的文件个数length；然后，根据Job2的输出，统计每个单词在所有文件集中出现的文件个数，输出<单词w, [文件名f1=f1-w-count|f1-length, 文件名f2=f2-w-count|f2-length,…]>（根据这里的数据即可得到单词w一共在k个文件中出现）。根据这样的记录即可求得<单词w|文件名f1, f1-w-count|f1-length log(length/k)>, 单词w|文件名f2, f2-w-count|f2-length log(length/k)>，即：<单词w|文件名f1,tf-idf-f1-w>，也就是每个单词在文件中的权重TF-IDF。

其MapReduce数据流如图2-53所示。

2.6.3　Hadoop TF-IDF编程实现

这里给出的TF-IDF算法的测试数据使用的是Avro格式的。这里只对Avro进行简单介绍，如读者需要深入了解，可以上网查找相关资料。

1. Avro简介

Avro是一个数据序列化的系统，它可以将数据结构或对象转化成便于存储或传输的格式。Avro设计之初就用来支持数据密集型应用，适合于远程或本地大规模数据的存储和交换。

Avro依赖于模式（Schema）。通过模式定义各种数据结构，只有确定了模式才能对数据进行解释，所以在数据的序列化和反序列化之前，必须先确定模式的结构。

Schema通过JSON对象表示。Schema定义了简单数据类型和复杂数据类型，其中复杂数据类型包含不同属性。通过各种数据类型用户可以自定义丰富的数据结构。

Avro定义了几种简单数据类型，表2-10是对其简单说明。

Avro定义了6种复杂数据类型，分别是record、enum、array、map、union和fixed，每一种复杂数据类型都具有独特的属性。表2-11就record这一种复杂数据类型进行了简要说明（后面也只会用到这种数据类型）。

（1）动手实践：Java基于Avro的序列化和反序列化

简单来说，Avro就是提供一个数据文件的说明文档，然后可以直接根据该说明文档进行序列化和反序列化的一个框架而已。

举个例子，比如现在有一个数据描述文件，如代码清单2-46所示。

有定义一个Java类和该描述文件匹配，如代码清单2-47所示。

代码清单2-46中的name:User或者name:name、name:favorite_number等，不需要与代码清单2-47中的名字User类或者方法setName、setFavoriteColor名字一模一样，只需一一对应即可。

那么怎么进行序列化呢？参考代码清单2-48，即可把用户user1、user2、user3序列化到本地磁盘的users.avro文件。

如何进行反序列化呢？参考代码清单2-49，即可把序列化后的users.avro文件内容读取出来了，并且代码清单2-49中的代码还把文件内容也打印出来了。

参考上面的示例，进行下面的实验。

实验步骤如下：

1）新建Java工程，引入avro-1.7.4.jar、avro-tools-1.7.4.jar（非必需）、jackson-core-asl-1.9.13.jar、jackson-mapper-asl-1.9.13.jar、junit-4.11.jar、hamcrest-core-1.3.jar。
2）参考代码清单2-46、代码清单2-47、代码清单2-48、代码清单2-49，缩写对应程序实现，运行程序查看结果。
（2）动手实践：Hadoop基于Avro的反序列化
这里增加一点Hadoop Job Counter的知识，Hadoop Job Counter可以在Hadoop Map-Reduce程序运行的过程中定义全局计数器，对一些必要的参数进行统计，通过doc api查看该用法，如图2-54所示。

在Java代码中遍历所有Hadoop MapReduce Counter，可参考代码清单2-50。

实验步骤如下：
1）拷贝avro-mapred-1.7.4-hadoop2.jar到Hadoop集群lib目录，上传hadoop/data/mann.avro数据到HDFS。
2）设置读取Avro文件的FileInputFormat为AvroKeyInputFormat。
3）参考示例程序2.5_004_avro_mr，读懂程序代码，运行程序，查看结果。

1. Job1：统计单个文件某个单词个数

针对2.6.2节分析的Hadoop MapReduce实现TF-IDF的流程中的Job1，分析如下。

驱动程序Driver：只需要设置Mapper以及Reducer，需要注意这里的输入需要使用AvroKeyInputFormat，这里考虑到编程方便以及效率，输出使用SequenceFileOutput-Format，如代码清单2-51所示。

Mapper要做的工作只是读取Avro数据，然后针对数据分隔各个单词（注意这里有些单词是不需要进行统计的，可以直接忽略）。Mapper的功能描述如下：

1）读取Avro格式数据，获取文件名和文件内容（类似Java单机程序），如代码清单2-52所示。

2）分隔文件的内容，这里需要注意不用统计的单词，具体单词如代码清单2-53所示。

分隔采用Match类正则进行分隔，如代码清单2-54所示。

3）只须输出单词、文件名和计数1即可，如代码清单2-55所示。

Reducer类直接采用Hadoop内部类IntSumReducer即可，即把相同的key的所有value值全部加起来，其输入输出描述如表2-12所示。

1. Job2：统计某个文件所有单词个数

Job2的Driver驱动程序是统计某个文件的所有单词个数，输入是Job1的输出，所以输入格式为SequenceFileInputFormat，输出格式也设成SequenceFileOutputFormat，方便Job3的读取，其设置参考代码清单2-56。

Mapper类只需把Job1的输出的键值对进行重构即可，这里即可以利用MapReduce按照key进行分组的特性，输出<文件名,文件中的单词|文件中单词的个数>这样的键值对，如代码清单2-57所示。

在Reucer中利用分组的特性（每个键值对按照键进行分组，所以会得到每个文件的所有单词作为一个列表），统计每个文件的所有单词个数，如代码清单2-58所示。

1. Job3：计算单个文件某个单词的TF-IDF

Job3综合前面两个的输出结构，得到最终每个文件每个单词的TF-IDF值。Driver需要配置输入输出以及格式，这里注意需要把Job1统计的总文件个数传入Job3中，这里为了便于观察，输出格式使用默认值TextFileOutputFormat，其示例代码如代码清单2-59所示。

Mapper类根据Job2的输入进行重构，再次使用word作为key，使用filename、word-Count、sumOfWordsInDoc作为value，如代码清单2-60所示。

Reducer根据Mapper的输出，同时利用相同的key聚合的特性，即可统计出每个单词在多少个文件中存在；在所有需要的参数计算完成后，即可利用TF-IDF的公式进行最后的计算，如代码清单2-61所示。

（1）动手实践：Hadoop实现TF-IDF算法

理解上面Hadoop MapReduce框架实现TF-IDF算法的原理，结合部分示例代码，完成该动手实践。

实验步骤如下：

1）参考“动手实践：Hadoop基于Avro的反序列化”内容，建立程序开发环境（主要是Avro相关开发包）；
2）参考工程2.5_005_tf-idf示例代码，结合前面的分析，理解代码功能；
3）修复工程功能（TODO提示），运行程序；
4）查看输出，对结果进行解释。

（2）思考

请读者思考，针对Hadoop MapReduce实现TF-IDF算法是否还有优化的空间？如果有优化的空间，怎么做呢？可以考虑下面几点：

1）是否可以缩减Job的个数？（提示：输出多目录、自定义键值对）
2）如果使用自定义键值对技术，应该如何修改程序？