日志

网站聚类kmeans的mapreduce实现

已有 1634 次阅读2017-8-20 11:24

由于前段时间期末考和放假，这篇文章推后了很多才出来。这是一个课程设计，主要是应用mapreduce对大规模的中文网站使用kmeans进行聚类，最后将相关的网站标记为同一类输出。

输入的每一行是网站的全局编号，对应有该网站的所有内容，包括未经处理的html等格式标记，输出为网站的全局编号，对应该网站属于的聚类编号。主要代码已经同步到github中，https://github.com/shenguojun/hadoop/tree/master/WebKmeans具体处理如下。

一概述

大规模中文网站聚类可以应用在检测相似内容网页,以及对大量网页进行分类的应用中由于在互联网中有大量的中文的网页,普通的计算机无法对百万数量级以上的网页进行处理,因此使用 Hadoop 分布式计算平台对这些大规模的网页进行存储以及Mapreduce计算模型进行聚类分析处理。

编程环境 Hadoop 版本是 1.0.4,编程环境是 Eclipse Indigo,测试使用 pseudo 伪分布模式,运行机器使用四核 Intel(R) Core(TM)2 Quad Q6600 @ 2.40GHz CPU,4G 内存。

输入数据说明(未经处理的原始网页):

Key (LongWritable) 每一个网页的全局 ID 号
Value (Text) 网页内容

输出数据说明(对每一个网页进行聚类标注):
Key (LongWritable) 每一个网页的全局 ID 号
Value (IntWritable) 该网页所属聚类中心编号

实现流程

主要的流程分别为:提取中文字符,分词,去除停用词,统计每个单词在每个网页中出现的次数以及在多少个网页中出现、每个网页的总词数以及总共有多少个网页并计算 Tfidf值,生成网页向量,建立词表,随机选取 k 个网页作为中心点,迭代进行 kmeans 计算,经过最大的迭代次数或者中心点不再改变时输出最终的中心点,最后根据最终的中心点判断一次每个网页属于哪个哪一类并输出最后结果。关键的流程如下图所示。

项目类说明（代码请见 https://github.com/shenguojun/hadoop/tree/master/WebKmeans） WordFrequenceInDocument:提取中文,分词,去停词,统计词频
WordCountsInDocuments:统计每个网页的单词数目
WordsInCorpusTFIDF:统计单词在多少个网页出现,计算 TFIDF,建立词表
DocumentVetorBuid:建立网页向量,随机选取 K 个网页作为中心点
Kmeans:判断网页属于哪一类,更新中心点,最后输出网页所属中心标号
KmeansDriver:控制 Mapreduc 的 Job 顺序,以及 Kmeans 迭代流程,设置参数
DocTool:根据网页向量以及所有中心点向量输出网页所属的中心编号

下面对每个类进行具体的说明。

二输入数据前期处理数据的前期处理分为提取中文、分词以及去除停用词三个部分。这些功能主要在WordFrequenceInDocument 类中的 Mapper 部分进行。

在其中提取中文使用正则表达式完成,主要代码如下:

// 匹配中文正则表达式

private static final Pattern PATTERN = Pattern.compile("[\u4e00-\u9fa5]");

Matcher m = PATTERN.matcher(value.toString());

while (m.find()) {

String matchkey = m.group();

valueBuilder.append(matchkey);

}

分词和去除停用词使用开源的 IKanayzer 工具包实现,详见:

http://code.google.com/p/ik-analyzer/

项目中主要代码如下:

StringReader retext = new StringReader(text);

IKSegmenter ikseg = new IKSegmenter(retext, false);

Lexeme lex = null

while ((lex = ikseg.next()) != null ){

// 在每个单词后面加上对应的所在网站

this.word.set(lex.getLexemeText() + "@" + key.toString());

}

三计算 Tfidf(Term Frequency Inverse Document Frequency)及词表建立计算 TFIDF 主要由 WordFrequenceInDocument(提取中文,分词,去停词,统计词频) WordCountsInDocuments、(统计每个网页的单词数目) WordsInCorpusTFIDF、(统计单词在多少个网页出现,计算 TFIDF,建立词表)这三个类进行。
三个类中的 Mapreduce 工作如下表所示。

输出类似如下:
中国公民@783 4
中国共产党@36 2
中国共产党@519 7

输出类似如下:
中国公民@783 4/1232
中国共产党@36 2/2895
中国共产党@519 7/3240

输出类似如下:
中国公民@783   0.02922078
中国共产党@36   0.00563378
中国共产党@519 0.01761862
词表:
中国公民   1859
中国共产党   1860

###############

主要是文档向量的建立以及kmeas的实现。

四网页向量以及初始中心点选取网页向量以及初始中心点的选取在 DocumentVetorBuid 中的一个 Mapreduce 中完成,中间过程如下表所示。

输出类似如下:
16 26272:0.00587873/22456:0.00264058/22502:0.00289516/23702:0.00278015/
五 Kmeans 聚类实现 DocTool 功能简介为了简化 Kmeans 过程中的代码,将计算网页向量与中心点向量之间的余弦距离,并根据最大的余弦距离判断网页属于哪一类的方法抽象出来, Kmeans 的迭代过程中可以直接在调用,简化了 Kmeans 主类的代码复杂度。
其中,DocTool类中主要方法为:
public static int returnNearestCentNum(Map<Long, Double> doc,Map<Integer, Map<Long, Double>> centers, long dictSize)
输入:doc 指代网页向量,centers 指代所有的中心点向量的集合,dictSize 指代词表中词的总数。

输出:网页所归属的中心点编号。

详细请见github代码 https://github.com/shenguojun/hadoop/blob/master/WebKmeans/src/edu/sysu/shen/hadoop/DocTool.java
Kmeans 主要 Mapreduce 介绍 Kmeans 主类由两个 Mapreduce 组成,一个是在迭代过程中更新中心点,一个是生成最后的结果,这两个 Mapreduce 的 Mapper 和 Rducer 的详细说明如下面两表所示。

输出类似如下:
16 26272:0.00587873/22456:0.00264058/22502:0.00289516/23702:0.00278015/
上述的 Mapreduce 是在迭代过程的进行的,输入的是网页向量,并借助中心点向量通过计算后得到新的中心点向量作为输出。在迭代完毕后,需要最后一个 Mapreduce 输出符合格式的最终文件。最后一个 Mapreduce 详细说明如下表。

输出类似如下:
2977 34
2978 46
2979 36
2980 34
2981 34
2982 34
2983 34
KmeansDriver 流程 KmeansDriver 负责控制所有 MapduceJob 的执行流程,以及建立 configuration 传入每个Mapreduce 所需要的参数。
控制流程如第一部分的实现流程图所示。其中较为关键是 Kmeans过程中的迭代过程,在迭代过程中由两个因素控制循环的结束,一个是输入参数中的最大迭代次数,当达到最大迭代次数后循环就会结束。另一个是判断新生成的中心点与就的中心点是否相等,如果相等的话就会提前结束,在实验中,设置 20 个中心点,平均在迭代 10 次左右就会达到收敛条件。
其中判断中心点是否收敛的代码如下。
详细代码请见 https://github.com/shenguojun/hadoop/blob/master/WebKmeans/src/edu/sysu/shen/hadoop/KmeansDriver.java

//计算是否提前结束

StringBuilder oldCentroid = new StringBuilder();

StringBuilder newCentroid = new StringBuilder();

Path oldCenPath = new Path(tmpPath + "/clustering/depth_"+ (iteration - 1) + "/part-r-00000");

SequenceFile.Reader oldReader = new Reader(fs5, oldCenPath, conf);

IntWritable key = new IntWritable();

Text value = new Text();

//得到旧的中心点向量

while (oldReader.next(key, value)) {

oldCentroid.append(key.toString() + value.toString());

}

oldReader.close();