hadoop kmeans中文网页聚类实验文档.pdf-资料库

sysu_arui-5033921-4744300845240702461.pdf-第1页.png

第1页 / 共7页

sysu_arui-5033921-4744300845240702461.pdf-第2页.png

第2页 / 共7页

sysu_arui-5033921-4744300845240702461.pdf-第3页.png

第3页 / 共7页

sysu_arui-5033921-4744300845240702461.pdf-第4页.png

第4页 / 共7页

sysu_arui-5033921-4744300845240702461.pdf-第5页.png

第5页 / 共7页

sysu_arui-5033921-4744300845240702461.pdf-第6页.png

第6页 / 共7页

sysu_arui-5033921-4744300845240702461.pdf-第7页.png

第7页 / 共7页

用 Kmeans 算法对大规模中文网页聚类摘要：本文先分析了基本Kmeans 算法的思想，然后详细论述如何用该算法对中文网页进行聚类。 Kmeans 算法的基本思想：（1）随机选取k 个样本点 Sample 作为初始质心 Centroid（2）计算各样本点到 k 个质心的距离（如欧氏距离），把样本划分到最近的质心所代表的Cluster （3）重新计算 Centroid，对 Cluster 里面的 Sample 求平均值（4）重复步骤（2）（3）直到 Centroid 不再变化，或者达到最大迭代次数。既然我们是利用 Kmeans 算法对网页进行聚类，就要把各网页表示成向量。由给出的测试数据，我们可以通过提取网页正文得到一个 document，然后通过分词得到文档中的各个单词，从而将网页聚类转化为对文本进行聚类。由于是对中文网页聚类，实验中先通过汉字的 Unicode 编码范围\u4e00-\u9fa5 提取出所有的汉字，然后利用分词软件 IKAnalyzer 进行中文分词得到文档的各个单词。该软件在切词的过程中会自动过滤掉一些停止词 stopwords，停止词列表和扩展词列表都是可以自定义的。接下来就是计算整个文档集 Corpus 中的单词对各个文档的权重，我们采用 tfidf 值来衡量。计算完单词的 tfidf 值后，我们可以设置一个阀值 threshold 提取出文档的关键字集合 vocabulary，进而生成各个文档的特征向量，然后进行 Kmeans 算法迭代直至收敛，最后对网页所属的 Cluster 进行标注。整个实验过程可以分为两部分，第一部分生成文档向量，第二部分就是 Kmeans 的迭代过程。下面先依次介绍这两部分的实现，最后讨论实验中遇到的一些问题和实验方法的一些不足之处。实验中所有和 MapReduce 相关的类都在 cn.edu.sysu.arui.mapred 包里，其它 domain 包，tools 包，test 包都是一些辅助类。一、计算文档向量（document vector） 0、 DocsCountInCorpus.java 用来统计文档集中的文档数，Reduce 输出 key 为 null，value 为 LongWritable 即所有网页数。注意，该 Job，Reduce 节点只有一个，也就是最终结果会写入一个文件 part-r-00000，后面我们会读取该文件获得文档总数，以便计算 TFIDF 值。第 1 页，共 7 页

1、 WordFrequenceInDocument.java 该类主要用来统计文档中的单词，内含两个静态内部类 WordFrequenceInDocMapper 和 WordFrequenceInDocReducer。 (1)、Map 输入和输出：< LongWritable，Text > < Text，IntWritable> 输入：key 为网页全局 ID 号，后面也称其为文档 ID，docid，value 为网页 body。输出：key 为 word@docid，value 为 1 注：在 map 函数中处理网页 body 时，利用 tools 包内封装好的分词类 TextExtractor 和 TermSplit 可以的得到文档的单词集。 (2)、Reduce 输入和输出：< Text，IntWritable > < Text，IntWritable > 输入：见 map 的输出输出：key 为 word@docid，value 为 #，其中#为 word 在 docid 所标识的文档中出现的次数。注：（1）为了简洁，下面不再给出内部类，直接给出 Map 任务和 Reduce 任务的输入和输出，读者自己去看相应的源代码即可。（2）所有输出文件的格式都是 TextOutputFormat，所以下一个 Job 的输入的 key 为 LongWritable，即行偏移量，后面不再说明。 2、 WordCountsInDocuments.java (1)、Map 输入和输出：< LongWritable，Text > < Text，Text> 输入：key 为行偏移量，value 为 word@docid # （见 1 中 Reduce 输出）输出：key 为 docid，value 为 word=# (2)、Reduce 输入和输出：< Text，Text > < Text，Text > 输入：见 map 的输出输出：key 为 word@docid，value 为 #/n，其中#为 word 在 docid 所标识的文档中出现第 2 页，共 7 页

的次数，n 为 docid 所标识的文档中的单词的总数。 3、 WordsInCorpusTFIDF.java (1)、Map 输入和输出：< LongWritable，Text > < Text，Text> 输入：key 为行偏移量，value 为 word@docid #/n （见 2 中 Reduce 输出）输出：key 为 word，value 为 docid =# (2)、Reduce 输入和输出：< Text，Text > < Text，DoubleWritable > 输入：见 map 的输出输出：key 为 word@docid，value 为 tfidf 值。 4、 GenerateVocabulary.java (1)、Map 输入和输出：< LongWritable，Text > < Text，DoubleWritable > 输入：key 为行偏移量，value 为 word@docid tfidf （见 3 中 Reduce 输出）输出：key 为 word，value 为 tfidf (2)、Combine 输入和输出：< Text，DoubleWritable > < Text，DoubleWritable > 输入：key 为 word，value 为 tfidf 输出：key 为 word，value 为 max_tfidf (某一分片 FileSplit 中，单词的最大 tfidf 值) (3)、Reduce 输入和输出：< Text，DoubleWritable > < Text，NullWritable > 输入：见 combine 的输出输出：key 为 word，value 为 null，其中为 word 被选为关键词，因为其对某一文档的权重大于某一阀值 threshold。注：该 job 的 Reduce 任务结点只设置为一个，以便所有的关键词都输出到一个文件里， part-r-00000，该文件在下一个任务 GenerateDocVectors 中会被缓存到各个结点，在其 Reduce 任务的 setup（）函数中读取关键字集合，遍历关键字集合，某一文档若含有该关键字，则文档向量相应分量为其 tfidf 值，若文档中不含有该关键字，则相应分量为 0.0D。DistributedCache 技术，在后面会反复用到，我们可以视其为“全局变量”。第 3 页，共 7 页

5、 GenerateDocVectors.java (1)、Map 输入和输出：< LongWritable，Text > < LongWritable，Text> 输入：key 为行偏移量，value 为 word@docid tfidf （见 3 中 Reduce 输出）输出：key 为 docid，value 为 word=tfidf (2)、Reduce 输入和输出：< LongWritable，Text > < LongWritable，Text > 输入：见 map 的输出输出：key 为 docid，value 为文档向量，其中文档向量为用\t 分隔的 double 型 tfidf 值。注：该任务的 map 输入为 3 WordsInCorpusTFIDF 中的输出。二、 Kmeans 算法的实现 1、 ChineseDocIDSet.java (1)、Map 输入和输出：< LongWritable，Text > < LongWritable，NullWritable> 输入：key 为行偏移量，value 为文档向量（见 5 中 Reduce 输出）输出：key 为 docid，value 为 null (2)、Reduce 输入和输出：< LongWritable，Text > < LongWritable，NullWritable > 采用默认的 Reducer 注：此 job 得到的是所有中文网页 ID 的集合，同样只设置一个 Reduce 结点，使得结果输出到一个文件 part-r-00000，该文件会来检测随机生成的网页 ID 号，是否是中文网页的 ID，以避免后面生成的初始中心小于 k 个。 2、 GenerateInitialCenters.java 先根据中文网页 ID 集合文件，随机生成一个初始中心网页的 id 号文件，这个过程是通过工具类 Corpus 的静态函数 generateKInitialCenters（…）来完成的。然后作业配置中把生成的文件缓存起来，在 Map 任务的 setup（）函数中读取初始网页 id 集。 (1)、Map 输入和输出：< LongWritable，Text > < NullWritable，Text> 第 4 页，共 7 页

输入：key 为行偏移量，value 为文档向量（见 5 中 Reduce 输出）输出：key 为 null，value 为文档向量 (2)、Reduce 输入和输出：< NullWritable，Text > < NullWritable，Text > 采用默认的 Reducer 注：该 job 的 Reduce 任务同样设置为一个，以便生成的初始中心写入到一个文件，该文件在 Kmeans 任务中会被缓存。 3、 KmeansCluster.java DataPro 类型请看 domain 包下的类，该类实现了 Writable 接口，内含两个成员 count 和 centerSum，其中 count 记录局部簇中的样本数，centerSum 记录局部簇的所有样本（文档向量）的和（各分量相加）。 (1)、Map 输入和输出：< LongWritable，Text > < IntWritable，DataPro > 输入：key 为行偏移量，value 为文档向量（见 5 中 Reduce 输出）输出：key 为 clusterid，value 为<1，文档向量> (2)、Combine 输入和输出：< IntWritable，DataPro > < LongWritable，Text > 输入：见 map 的输出输出：key 为 clusterid，value 为，即某一分片中的局部簇中心 (3)、Reduce 输入和输出：< IntWritable，DataPro > < NullWritable，Text > 输入：见 Combine 的输出输出：key 为 null，value 为新生成的聚类中心注： (1) 该 job 的 reduce 任务设置为一个，以便新的质心输出到一个文件，然后缓存起来进行下一次迭代。 (2) 迭代终止条件：当新生成的质心文件和上一次的质心文件几乎相同时（差异小于某一阀值），或达到最大迭代次数时，停止迭代。第 5 页，共 7 页

(3) 最后再一次读取 5 中生成文档向量，根据最终的质心文件对文档进行聚类标号，这个比较简单，详情请看 KmeansCluster 类。三、问题和总结 1、实验题目为“大规模（百万以上）中文网页聚类”，但是不知到为什么给出的测试数据里面有非中文网页？带来的问题：我们通过一个 job 计算了所有网页的数量 N，为了生成初始聚类中心，我们随机生成 0-N-1 之间的 k 个不重复的数，但是问题来了，这 k 个不重复的 ID 可能不是中文网页的标号，从而会导致生成质心文件的 job 的输出不足 k 行，因为某些非中文网页早在前面我们分词的时候就过滤掉了，它是不会出现在 5 中生成的文档向量中的。解决方案 1：读取 5 中 job 生成的文档向量集的某一文件比如 part-r-00000，取 k 行，比如取前 k 行即可。解决方案 2：对于 5 中生成的文档向量集，我们提取出 key，也就是 docid，输出到一个文件，构成中文网页 ID 集。然后在每次随机生成 docid 时，保证生成的 ID 在 ChineseDocIDSet 里面，重复 k 次即可。在实验中，采取的是解决方案2，但是这里面还有一个问题，就是计算tfidf 值时，用的是所有网页的数量 N，而不是中文网页的数量。 2、网页正文题提取我们过滤了所有英文网页，这没什么大不了的，因为是中文网页聚类，且英文网页是少数，但是实验中采用的是简单的中文字符抽取方式，这样导致提取出的网页正文包含大量无关的单词，比如某以网站网页的页眉和页脚，还有一些广告信息。这可能会影响聚类效果，这是本实验的一个不足之处。 3、特征选择和维度灾难特征选择有很多方式，比如根据单词的文档频率 DF，根据卡方值，信息增益等，我在实验中采用的是根据 tfidf 值进行选择，如果某一单词对所有文档的权重的最大值大于某一阀值，就将其选为关键字。但是该阀值不好控制，阀值的选择直接影响生成的文档向量的维数，进而影响聚类的效率和效果。第 6 页，共 7 页

改进方案：对所有单词的 tfidf 值的最大值，进行排序，选取 K 个关键词即可，虽然说 K 值的选取仍然需要经验值，但是至少可以有效的防止纬度灾难。 4、聚类中 k 值和收敛阀值的选择最后在利用 Kmeans 进行迭代时，我们根据阀值判断当前的质心文件和上一次的质心文件是否相同，即迭代是否已经收敛，但是该阀值的选取需要经验值。阀值选的太大，迭代两次就停止了；阀值选得太小，会不停的迭代增加运行时间。 5、代码优化由于对 Hadoop 不熟悉，实现中采用的都是最简单的方式，如使用的都是内置的类型，各种数据类型转换，而没有采用 Hadoop 的高级技术，代码还有很大的改善空间。参考资料 [1] 一个在 Hadoop 上计算 TFIDF 的例子： http://code.google.com/p/hadoop-clusternet/wiki/RunningMapReduceExampleTFIDF [2] 一个 Hadoop 上 Kmeans 算法的实现： http://www.linuxidc.com/Linux/2012-10/71538.htm [3] 一个有关 NLP 的 Blog ，里面有关于文本分类的资料： http://www.cnblogs.com/finallyliuyu/ [4] IKAnalyer 的下载： http://code.google.com/p/ik-analyzer/ [5] Hadoop the Definitive Guide. Haoop 权威指南（中文第 2 版）第 7 页，共 7 页

资料库

hadoop kmeans中文网页聚类实验文档.pdf

相关推荐

开发技术

热门标签

最新资料