编制程序模型在日记分析方面包车型大巴采用

from:http://www.ibm.com/developerworks/cn/java/java-lo-mapreduce/index.html

简介

日记分析往往是商业智能的根基,而增进的日志新闻条目使得周边数据处理平台的产出成为一定。MapReduce
处理数据的得力为日志分析提供了可信赖的支柱。

本文将以对走访网页用户的日记举办解析,进而挖掘出用户兴趣点这一完好流程为例,详细分解
MapReduce 模型的相应完结,涵盖在 MapReduce
编制程序中对于十分规题材的拍卖技术,比如机械学习算法、排序算法、索引机制、连接机制等。文章分三有个别开始展览:首先介绍
MapReduce
编制程序模型,对其规律、对任务处理流程以及适用意况开始展览介绍;接下去描述了日志分析的例证

  • 用户兴趣点挖掘的处理流程;最终对处理流程的多少个模块分别开始展览了 MapReduce
    的完结。本文的意在通过 MapReduce 在日记分析世界的实际达成,使读者对
    MapReduce 对实际难点的处理有比较形象的认识。

回页首

MapReduce
编制程序模型简介

随着音讯化的愈狠抓化,在各样领域,如邮电通讯、交通、金融、零售、航天、医药等,数据量级都显现飞速增进趋势。如何快捷并且无误地囤积、分析、明白以及选择那几个大规模数据,成为多个宗旨难题。

为了酬答常见数据处理的难点,MapReduce 编制程序模型应运而生。谷歌(Google)建议的这一模子,由于能够的易用性和可扩充性,获得了工产业界和科学界的宽广协助。Hadoop,MapReduce
的开源完毕,已经在 Yahoo!, 推特, IBM, 百度 ,
中国邮电通讯等多家单位中动用。

MapReduce 编制程序模型

MapReduce 以函数格局提供了 Map 和 Reduce 来进展分布式计算。Map
绝对独立且互相运营,对存款和储蓄系统中的文件按行处理,并发出键值(key/value)对。Reduce
以 Map 的输出作为输入,相同 key 的笔录汇集到同一 reduce,reduce
对那组记录举行操作,并发生新的数码集。全体 Reduce
任务的出口组成最后结果。情势化描述如下:

Map: (k1,v1) -> list(k2,v2)

Reduce:(k2,list(v2)) ->list(v3)

MapReduce 对职分的处理流程如图 1 所示。主要分为几步:

  1. 用户提交 MapReduce
    程序至主要控制节点,主要控制节点将输入文件划分成多少分片(split)。主控节点
    Master 和办事节点 worker 运行相应进度;
  2. 主要控制节点依据办事节点实况,进行 map 使命的分红;
  3. 被分配到 map 任务的节点读取文件的四个分片,按行进行 map
    处理,将结果存在本地。结果分成 LAND 个分片进行仓库储存,牧马人 对应的是 Reduce
    数目;
  4. Map 节点将积存文件的消息传送给 Master 主要控制节点,Master 钦赐 Reduce
    职务运维节点,并告知数据获得节点新闻;
  5. Reduce 节点依据 Master 传递的音讯去 map 节点远程读取数据。因为
    reduce 函数按分组进行拍卖,key 相同的笔录被联合处理,在 reduce
    节点标准拍卖前,对负有的记录依据 key 排序;
  6. Reduce 将处理结果写入到分布式文件系统中。

图 1 . MapReduce 处理流程图
航天科工 1 

MapReduce 适用景况

出于 MapReduce
编制程序模型是对输入按行顺次处理,它更适用于对批量数量进行拍卖。由于优异的可扩大性,MapReduce
特别适用于对广大数据的拍卖。

然则,对寻找等只是亟需从大量数码中选用某几条专门的操作,MapReduce
绝对于拥有完善索引的体系而言,不再持有优势。因为它必要对每条数据开始展览匹配,并与追寻条件相匹配的数量提取出来。而一旦应用索引系统,并不需求遍历全部的数目。

别的,由于每回操作供给遍历全数数据,MapReduce
并不适用于必要实时响应的种类。相反地,对于搜索引擎的预处理工科作比如网页爬虫、数据清洗,以及日志分析等实时性须要不高的后台处理工作,MapReduce
编程模型是能够胜任的。

回页首

日记分析应用

互连网或然大型应用种类中,日志的发出和记录是老大主要的事务。日志分析则是开始展览多少挖掘进而推进下一步工作的基本功。比如,在购物网站,针对用户访问网页的音信,能够挖掘出用户的兴趣点,进而开始展览物品推荐;又比如说,在行使种类中,通过分析用户对系统部件的行使处境,能够挖掘出该种类中的热点部件,进而选取对应的主意抓好管理;典型地,对于一个医卫系统,依照医务人士对两样病情开处方的日志记录,可以挖掘出某种病情和药物的附和关系,进而建立三个专家推荐系统等。

乘机互连网行业的扩大和行使种类规模的扩张,记录相应音讯的日志数量级也在可以扩充。守旧的单机版分析程序已经无法满意日志分析的须要,为此,大规模数据处理平台成为日志分析的名牌产品特产产品优品平台。另一方面,日志分析并从未很高的实时性须要,MapReduce
编制程序模型由于易用性强、处理多少规模大,成为日志分析的利器。

正文下边部分会以用户访问网页日记为例,解说怎么着利用 MapReduce
来分析日志,进而挖掘出相应新闻。

回页首

用户访问网页行为建立模型

一般而言 , 用户每访问网页时 , 系统日志中会存款和储蓄一条记录 : 用户 + url +
访问时间。用户访问的一密密麻麻网页记录正是揣摸用户兴趣点的底蕴,即:用户 +
urlSet。

怎么依据用户访问的多重 UCR-VL
新闻来揆度用户兴趣点?一般而言,由以下多少个步骤构成:

  • 单纯性网页音讯挖掘。依据 U安德拉L
    得到网页内容新闻,并对网页内容举行拍卖,获得代表此网页的多少个重庆大学词,一般要借助机器学习算法或然专家经验来抢劫较有价值的词。
  • 用户访问关键词音讯集中。汇总用户访问的依次 UPAJEROL
    中的全体首要词信息,进而获取用户关注的根本词列表。每一个首要词均有不相同权重,视该词在
    U君越L 中冒出的次数而定。
  • 注重词扩大及归约。对用户关注首要词列表举行自然的恢弘或归约操作,获得更为富有普遍意义的词音信,以更好地特色用户的兴趣点。

图 2 .用户兴趣挖掘流程图
航天科工 2 

单纯性网页音信挖掘

从 UTiggoL 获得该网页中有价值的词信息,首先要对 U途乐L
实行重复爬取,以博取其对应的网页内容。从网页中领取关键词,则须要肯定的算法援救。在一篇网页中,分歧词因为在不一致岗位照旧以不一致的格式出现,对应影响程度也比不上。比如,在网页的标题恐怕网页内容每一自然段段首恐怕段尾的词大概更为主要;在网页中有一定格式,比如加粗只怕字体较大照旧标记颜色的词大概更为主要。

而给定3个词,怎样标记其主要性照旧对网页的价值?能够将各样词用向量的款式来拓展描述,向量中每一维度
d 表示区别的测量标准,比如
TF(在该网页中出现的次数)、DF(在具有网页中冒出的次数)、是不是在标题中出现、是或不是在段首
/ 段尾出现、是或不是在句首 / 句尾出现、颜色有无分裂其它词、词的词性是名词 /
动词 / 形容词 / 助词,等等。形如 w = (v1, v2, v3, v4, … ),每种维度 v
对词是网页根本词的控制造进程度差异,这些影响因子能够透过机器学习算法磨练而得。即:由事先钦定关键词的网页来进展磨练,获得特征权重。

收获特征权重后,对于网页中的每一种词,可以透过 w = sum(vi*fi)
的法门来获得其看成关键词的百分比。从网页中选取能表示其内容的多少个词,应对富有计算出权重的词按权重从大到小各类排序,接纳前几名恐怕高于有些阈值的词即可。

焚薮而田思路如图 3 所示。

图 3 .网页重视词挖掘流程图
航天科工 3 

用户访问关键词汇总

获取每一种网页的意味第2词后,对于用户访问的重庆大学词,即可通过集中用户访问的具备网页的根本词拿到。不难而言,用户访问每一个词的次数能够当做该词为用户关怀词的权重。因为背后还要开始展览进一步的最主要词扩展/
归约,为预防数值过大的气象,能够对权重进行归一化。当然,也足以再到场别的策略,对词的权重举办特别调整,比如通过黑名单也许词的共现频率等形式将垃圾词(对描述用户兴趣点无意义的词,比如“博客园”、“Taobao”等)地点后调,此处不再详加展开。

根本词扩大及归约

  • 关键词增添

上一步得到的结果是用户在日记所记录的光阴内访问的重中之重词汇总,而词与词之间反复是相互关系的。比如,用户访问了“篮球”这一个词,这其实该用户也很有可能对“球星”这么些词感兴趣,因为“篮球”和“球星”两词存在必然关联。能够透过重点词扩张,推断出用户对“球星”一词也感兴趣。

什么获得七个词之间的相关度?一般而言,同时在三个网页元音信(meta)的
keyword 域里的词相当大程度是有关的。由此,总结 meta
中词,就足以总括出来词与词的相关度消息。因为用户访问的词与词之间并不是孤立完全非亲非故的,而是有早晚关系的。把
meta
中词与词的相关性音信加入到用户对种种词的关注度中,能够更好地展现用户的关切地方。到场meta 相关词新闻后,便获取了进一步纯粹的用户对词的关怀度列表。

网页 meta 中 keyword 区域放置的再三是该网页的分类消息 ( 导航类网页
),恐怕是该网页的主要词(正文类网页)。假若是前者,meta
中的词反复相关度较大。而各异网站的 meta
内容是什么,是由网站的编写决定的。所以把分化网站的 meta
里面共现的词提取出来并汇总到手拉手,其实是汇聚了逐一网站编辑们的公共智慧。那么些词的共现音信应该力所能及很好地球表面现出词与词之间的相关性。如若五个词总在一块儿出现,它们极有或者是有关的。

切实流程为:首先,总括 meta
中一起出现的词对以及它们一起出现的次数;然后,总结那几个共现的词对中的词每种词出现的次数;最终,应用公式进行共现频率的计量,得到的正是词与词之间的相关度。总括公式为

航天科工 4 

其中,pij代表词 i 和词 j
的相关度,mi、mj、mij分级表示词 i、词 j
以及词 i 和 j 共同在网页元新闻(meta)的 keyword 中出现的次数。

图 4 .用户访问关键词扩大流程图
航天科工 5 

图 4
描述了将词之间的相关度参加用户访问关键词列表中的流程:首先取得全体词对之间的相关度新闻,并以索引格局储存;然后,对前边得到的用户访问关键词列表中的各类词,查找索引得到有关的词,即使该词未被用户访问过,直接将其加入到用户访问列表中;不然,对八个词的权重都需进行调整。

  • 主要词归约

与根本词扩大相对应的是主要词归约。用户访问的网页中挖掘出的第壹词反复是切实的,比如用户关注的网页中领到出的词是“足球”、“篮球”,而这几个词在划分的时候都属于体育类,通过首要词归约,能够测算出该用户对”体育”相比较感兴趣。

而分类标准应该如何取得呢?在各大门户网站如博客园、天涯论坛的首页,都有诸如天气、新闻、教育、军事等各大类,在每一大类里又有各小类;在天猫、易趣等网上交易平台,更是有对商品的一种类详细分类。关键词归约,便是基于用户访问的首要词追溯到用户对怎么样类型的内容感兴趣。

不论是关键词扩充依然归约,都会拿走更进一步可信的用户访问关键词列表,对负有词按权重由大到小举行排列,描述的正是用户的兴趣点。

回页首

MapReduce
对用户兴趣挖掘的实现

上部分介绍了用户兴趣点挖掘的流水生产线,本有的将针对种种模块进行 MapReduce
的贯彻。整个应用的输入是用户访问网页记录组成的公文,文件每行表示用户访问网页的一条记下,形为:

“用户
U奥迪Q5L”。期望输出为用户的兴趣点文件,文件每行存款和储蓄各样用户的兴趣点,形为:

“用户 词 1 权重 1 词 2 权重 2 词 3 权重 3 ”。

下边会对八个步骤分别授课 MapReduce 实现。

纯净网页音信挖掘

纯净网页音讯挖掘的目标是选项出网页中相对主要的首要词。策略为各样词赋予权重,并选拔权重较大的词。词的权重获取公式
v = sum(vi*fi) 由两有些决定:该词在每一种特征上的取值和该特征的权重。

各个特征的权重,可由练习取得,输入为付出关键词的俯拾正是网页。特征权重磨炼经常有一定的算法,比如
SCGIS
算法,因为操练集相对于完整的输入集较小,而算法常常也较复杂,并不吻合并行化,可在
MapReduce 职务初阶以前进行特征权重磨炼。

而词在各样特征维度上相应的取值,视特征的不及,难易程度也比不上。比如词的现身岗位、大小写、词性等,在对网页进行扫描时,可以及时得到。而
TF( 词在网页中出现的次数
)、DF(词在享有网页中冒出的次数)等性格并不可能随词现身时立刻赢得,但出于每一个词处理的主次都一样,所以能够运用
MapReduce 编制程序模型并行化。上面进行具体描述。

单一网页音信挖掘部分的 MapReduce 流程如图 5 所示。

图 5.MapReduce 完成单一网页音信挖掘
航天科工 6 

  • TF 词在网页中冒出次数信息总结

Map:输入为用户 +url 列表,对于单条记录,进行 url
爬虫和分词,获得用户访问的该网页中涵盖全部词的音讯。每碰到三个词,Map
举办3遍输出,key 为用户 + 网页 + 词,value 为 1。当然,此时 Map
还是能总括别的新闻,比如词性(名词 /
动词)等,为简化描述,此处不再详加展开。

Reduce:Map 输出结果中 key 相同的集纳到手拉手,Reduce
对每组总括其涵盖记录条数,将用户 + 网页 + 词仍旧作为 key
进行输出,将每组中著录条数作为 value 进行输出。

那般,Reduce 的出口结果文件每行对应记录为“ 用户 + 网页 + 词 词的 TF”。

清单 1. MapReduce 统计 TF

                
 public class TFCal extends Configured implements Tool, 
 Mapper<Text, Text, Text, IntWritable>,Reducer<Text, IntWritable, Text, IntWritable>{ 
    public void map(Text usr, Text url, OutputCollector<Text, IntWritable> output, 
 Reporter reporter)throws IOException { 
        Text[] words = callCrawl(url);   // 调用爬虫程序
        for(Text word: words)   // 每个词进行输出
            output.collect(usr + url + word, new IntWritable(1)); 
    } 

    public void reduce(Text key, Iterator<IntWritable> iter,OutputCollector<Text, 
 IntWritable> output, Reporter reporter) throws IOException { 
        tf = iter 中包含元素的数目 ; 
        output.collect(key, tf); 
    } 

    public void runCal(Path input, Path output) throws IOException { 
        JobConf job = new JobConf(getConf(), TFCal.class); 
        job.setInputPath(input); 
        job.setOutputPath(output); 
        job.setMapperClass(TFCal.class); 
        job.setMapperClass(TFCal.class); 
        job.setInputFormat(SequenceFileInputFormat.class); 
        job.setOutputKeyClass(Text.class); 
        job.setOutputValueClass(IntWritable.class); 
        JobClient.runJob(job); 
    } 
 } 

比方网页中剧情能够在内部存款和储蓄器中处理,也足以只在 Map 阶段实现对各样词 TF
的总结,那样能够节省 Map 和 Reduce
之间多量多少传输的时光消耗。具体处理思路为:选用3个数据结构
hashMap<String, value>,Map 的每行输入仍为用户 +url 新闻,对 url
网页爬虫的结果,每蒙受1个词,将其新闻参预到 hashMap 中,key 为词,value
为本来 value+1,与此同时,仍是可以计算该词的任何特征值,比如词性等。因为
Map 阶段即可到位 TF 计算,能够将 Reduce 数目设为 0。

清单 2. Map 统计 TF

                
 public class TFCal2 extends Configured implements Tool, Mapper<Text, Text, Text, 
 IntWritable>{ 
    public void map(Text usr, Text url, OutputCollector<Text, IntWritable> output, 
 Reporter reporter)throws IOException { 
        HashMap<Text, int> wordCount = new HashMap<Text, int>();   //HashMap 统计 TF 
        Text[] words = callCrawl(url);   // 调用爬虫程序
        for(Text word: words){   // 统计词次数信息
            int cnt = wordCount.get(word); 
            wordCount.put(word,(cnt>0)?(cnt+1):1); 
        } 
        Iterator<Text,int> iter = wordCount.entrySet().iterator(); 
        while(iter.hasNext()){ 
            Map.Entry<Text, int> entry = iter.next(); 
           // Map 输出,key 为用户 +url+ 词,value 为 TF 
           output.collect(usr + url + entry.getKey(), entry.getValue()); 
        } 
    } 

    public void runCal(Path input, Path output) throws IOException { 
        JobConf job = new JobConf(getConf(), TFCal2.class); 
        设置 InputPath, outPath, MapperClass, InputFormat, OutputFormat, …
        job.setReduceNum(0);   //Reduce 数目设为 0,不进行 Reduce 操作。
        JobClient.runJob(job); 
    } 
 } 

  • DF 词在享有网页中出现次数消息总计

Map 输入为 TF 总括阶段输出,key 为用户 + 网页 + 词,value 为词的 TF。Map
阶段处理,将网页音信去除,输出 key 为用户 + 词,输出 value 为 1。

Reduce 以 Map 输出为输入,用户访问词相同的会被同贰个 reduce 处理,reduce
中执会调查总计局计该组包蕴记录的数目,正是词的
DF。由于在计算每个词权重时,供给获得各样特征的值,而在盘算 TF
的时候能够赢得该词除 DF 外别的特征的音信,所以需求额内地获取 DF
音信。为方便查询 DF 的新闻,应将 Reduce
阶段的输出以索引文件的花样展开输出。Lucene 是可在 MapReduce 开源框架
Hadoop 上配备的目录机制,可在 Reduce 输出时接纳,key 为用户 + 词,value
为 DF。

清单 3. MapRedcue 统计 DF

                
 public class DFCal extends Configured implements Tool, Mapper<Text, IntWritable, Text, 
 IntWritable>,Reducer<Text, IntWritable, Text, LuceneDocumentWrapper>{ 
    public void map(Text key, IntWritable url, OutputCollector<Text, IntWritable> output, 
 Reporter reporter)throws IOException { 
        将 key 拆分成 user,url,word 三部分
        output.collect(user+word, new IntWritable(1); 
    } 

    public void reduce(Text key, Iterator<IntWritable> iter, OutputCollector<Text, 
 LuceneDocumentWrapper> output, Reporter reporter)throws IOException { 
        int df = iter 中包含元素数目 ; 
        // 建立 Lucene 索引,以 user+word 为 key,DF 作为 value,进行存储
        Document doc = new Document(); 
        doc.add(new Field("word", key.toString(), Field.Store.NO, 
            Field.Index.UN_TOKENIZED)); 
        doc.add(new Field("DF", df, Field.Store.YES,Field.Index.NO)); 
        output.collect(new Text(), new LuceneDocumentWrapper(doc)); 
    } 

    public void runDFCal(Path input, Path output) throws IOException { 
        JobConf job = new JobConf(getConf(), DFCal.class); 
        设置 InputPath, outPath, MapperClass, InputFormat, …
        job.setOutputFormat(LuceneOutputFormat);   // 设置输出格式为 LuceneOutputFormat 
        JobClient.runJob(job); 
        合并各个 reduce 生成的索引文件为一个完整索引文件(Lucene 的 IndexWriter 类提供了相应接口)
    } 
    … . 
 } 

在清单 3 中出现的 LuceneDocumentWrapper 和 LuceneOutputFormat 均是为在
MapReduce 上运用 Lucene 索引文件作为 Map/Reduce
输出添加的类,两者分别继承自 WritableComparable 和
FileOutputFormat。清单 4 提供了两边的定义。

清单 4. Lucene 在 MapReduce 上的选用

                
 public class LuceneDocumentWrapper implements Writable { 
    private Document doc; 
    public LuceneDocumentWrapper(Document doc) { 
        this.doc = doc; 
    } 
    public void set(Document doc_) { 
        doc = doc_; 
    } 
    public Document get() { 
        return doc; 
    } 
    public void readFields(DataInput in) throws IOException { 
        // intentionally left blank 
    } 
    public void write(DataOutput out) throws IOException { 
        // intentionally left blank 
    } 
 } 

 public class OutputFormat extends 
 org.apache.hadoop.mapred.FileOutputFormat<WritableComparable, LuceneDocumentWrapper> { 
    public RecordWriter<WritableComparable, LuceneDocumentWrapper> getRecordWriter(final 
 FileSystem fs,JobConf job, String name, final Progressable progress) 
   throws IOException { 
        final Path perm = new Path(FileOutputFormat.getOutputPath(job), name); 
        final Path temp = job.getLocalPath("index/_" + Integer.toString( 
 new Random().nextInt()));   // 设置临时输出路径为 Reduce 节点本地局部路径
        final IndexWriter writer = new IndexWriter(fs.startLocalOutput(perm, 
 temp).toString(), new StandardAnalyzer(), true); // 初始化 IndexWriter 

        return new RecordWriter<WritableComparable, LuceneDocumentWrapper>() { 

            public void write(WritableComparable key, LuceneDocumentWrapper value) 
 throws IOException {  // 将 document 加入到索引之中
                Document doc = value.get(); 
                writer.addDocument(doc); 
                progress.progress(); 
            } 

            public void close(final Reporter reporter) throws IOException { 
                boolean closed = false;   // 标识索引是否已经输出完毕
                Thread prog = new Thread() { 
                    public void run() { 
                        如果索引未输出完毕 closed != true,保持等待,并设置 reporter 状态为 closing 
                    } 
                }; 
                try { 
                    prog.start(); 
                    writer.optimize();  // 索引进行优化并关闭
                    writer.close(); 
                    拷贝本地输出至全局文件系统 HDFS 中
                }finally{ 
                    closed = true; 
                } 
            } 
        }; 
    } 
 } 
  • 网页根本词总括

赢得 DF 新闻后,即可在多个新的 Map
进度中对网页中各类词计算其权重,即变成网页根本词的票房价值,此处能够内定多个阈值,若可能率大于该阈值,认为该词能够表示网页,将其出口;不然忽略。

清单 5. Map 总结网页根本词

                
 public class KeyWordCal extends Configured implements Tool, Mapper<Text, Text, Text, 
 IntWritable>{ 
    String fWeights[];   // 记录特征权重
    IndexSearcher searcher = null;   // 用于查询 Lucene 索引文件
    public void map(Text key, Text wordInfo, OutputCollector<Text, IntWritable> output, 
 Reporter reporter)throws IOException { 
        解析 key,从中得到 word 信息
        // 查找索引文件,得到 DF 
        Term t = new Term("word", word); 
        Query query = new TermQuery(t); 
        Hits hits = searcher.search(query); 
        if (hits.length() == 1) { 
            Document doc = hits.doc(0); 
            String df = doc.get(“DF”); 
            从 wordInfo 中提取出来每个特征对应取值 , 存储在数组 val 中
            weight = sum(val[i] × fWeights[i]);   // 计算该词作为关键词权重
            if(weight >= threshold)   // 权重大于阈值的视为网页关键词
           output.collect(key, new Writable(1));  // 关键词输出,key 包含用户 + 关键词,value 为 1
           } 
    } 

    // configure 函数会在每个 Map 节点运行 Map 函数对文件按行处理之前调用,通常用来做全局操作
    public void configure(JobConf job) { 
        String fWeightPath = job.getStrings(“fWeight.path”)[0]; /// 内部获得特征权重路径
        读取特征权重文件,得到特征权重列表,填入 fWeights; 
        String dfPath = job.getStrings(“DF.path”)[0]; 
        FsDirectory fsDirectory = new FsDirectory(FileSystem.get(getConf()),dfpath, 
        false, getConf()); 
        searcher = new IndexSearcher(fsDirectory); 
    } 

    public void runkeyWordCal(String input, String output, String DFPath){ 
        String featureWeightFile;
        SCGIS(featureWeightFile);   // 调用机器学习算法,计算特征权重,并将权重存储在指定文件中
        JobConf job = new JobConf(getConf(),KeyWordCal.class); 
        设置 InputPath, outPath, MapperClass, InputFormat, OutputFormat, …
        job.setStrings(“fWeight.path”, featureWeightFile);// 设置参数,以传入 Map 和 configure
        job.setStrings(“DF.path”, DFPath);   // 设置 DF 索引文件位置
        JobClient.run(job); 
    } 
    … . 
 } 

用户访问关键词汇总

在用户首要词汇总模块,一共供给七个总体的 Reduce,流程图如图 6 所示。

图 6.MapReduce 完毕用户首要词汇总
航天科工 7 

  • 用户访问词次数汇总

经过单一网页音信挖掘模块的拍卖,对每种网页处理完结,输出的记录形为“用户

  • 网页根本词”,所以只需通过3个 Reduce
    就能总结出用户访问各个词的次数。为方便后续对各种用户的关心词实行集中处理,本
    Reduce 的出口 key 为用户,value 为词 + 用户访问该词的次数。

  • 用户访问词按次数排序

第三个 Reduce 的输入为首个 Reduce 的出口,在本 Reduce
中,同一用户访问的词会被集结到联合,为了更好地讲述用户的兴趣点,应对拥有词按访问次数实行从大到小实行排序,能够由此Reduce 内部对成熟排序算法,比如飞速排序的调用来贯彻。

  • 词权重归一化

因为不一样词的访问次数大概差别较大,比如最常见词访问 二十三次,而次常见词只怕拜会 10次,如此大的出入并不方便人民群众对词权重的愈加调整。所以采纳数据挖掘领域广泛的归一化策略来对词权重进行调整,将其调整到
[0,1]
区间内。最简便易行的国策是将最常见词的拜访次数去除访问每一个词的次数。Weight(w)=Times(w)/Times(MAX)。那一个权重归一化的历程一样能够在其次个
Reduce 进度中成功。

清单 6. 多个 Reduce 汇总用户访问关键词

                
 public class UserWordCal1 extends Configured implements Tool, Reducer<Text, IntWritable, 
 Text,Text>{ 
    public void reduce(Text key, Iterator<IntWritable> iter, OutputCollector<Text, Text> 
 output, Reporter reporter)throws IOException { 
        解析 key,分别得到 user 信息和 word 信息
        output.collect(user, new Text(word + iter 中包含元素的个数 ));   //value 为用户访问该词次数 
    } 
    … . 
 } 

 public class UserWordCal2 extends Configured implements Tool, Reducer<Text, Text, Text, 
 Text>{ 
    public void reduce(Text key, Iterator<Text> iter, OutputCollector<Text, Text> 
 output, Reporter reporter)throws IOException { 
        Struct<Text, int> Word;   // 定义一个数据结构,包含两项,分别存储 word 和次数信息
        ArrayList<Word> wList; 
        遍历 iter,将访问词的信息填入 wList; 
        QuickSort(wList);   // 对 wList 按次数排序
        Normalize(wList);   // 对 wList 进行权重归一化
        String wordInfo = “”; 
        for(Word word: wList)   // 将词和对应的权重信息拼接
            wordInfo = wordInfo + word + word.getWeight(); 
        output.collect(user, new Text(wordInfo)); 
    } 
    … . 
 } 
  • MapReduce 本人对排序的帮衬

实则,MapReduce 本身的建制也足以实现排序功效。数据从 Map 方法输出到
Reduce 方法输入是要因而多少个步骤的,包罗:Map 端依照 Reduce
数目对地点输出举行分组;Map 和 Reduce 之间的多少传输 shuffle;Reduce
端对来源四个 Map 的多寡按 key 举办排序并分组,每组传入给 Reduce
方法开始展览处理。

从那个进程能够看来,同二个 Reduce 处理的多寡实际上是遵照 key
排序的,假诺将 Reduce 数目设为
1(job.setReduceNum(1)),并将排序基准字段在 Map 方法中设为
key,就足以兑现多少的大局排序。

重中之重词扩大及归约

重要词增添和归约对用户访问词列表举行的八个例外倾向的调动,本节详细介绍多个大方向,对第二词扩大进行进行。

  • 词与词相关度音信获得

重视词扩大的最重假如获取词与词的相关度,并基于此相关度对用户访问词列表进行调整。词与词之间相关度的总结公式已在后面小节列出。

航天科工 8 

图 7 .MapReduce 达成词与词相关度总计
航天科工 9 

图 7 展示了 MapReduce 计算 pij的流程。

  1. 计算词对共现次数

    Map:以用户访问 url 音信为输入,在 Map
    内部举办网页爬虫,并只爬取网页的 meta 中 keyword
    域的词音信,各种网页中对应的词两两组成词对举办输出,词对中率先个词的拼音序
    / 字母序要优化第二个词。输出 key 为词 1+ 词 2,value 为 1。

    Reduce 总计词 i 和词 j 共同出现的次数 mij,在 Reduce
    内部总括每组包罗记录的数量,依旧以词 1+ 词 2 作为
    key,将共现次数作为 value 举办输出。

**清单 7. 词与词相关度计算 -1 (词对共现次数统计)**  

<table>
<colgroup>
<col style="width: 100%" />
</colgroup>
<tbody>
<tr class="odd">
<td><pre class="displaycodeliquid"><code>              
public class WordsCorrCal1 extends Configured implements Tool, Mapper&lt;Text, 
Text, Text, IntWritable&gt;, Reducer&lt;Text, IntWritable, Text, IntWritable&gt;{ 
    public void map(Text key, Text url, OutputCollector&lt;Text, IntWritable&gt; 
 output, Reporter reporter)throws IOException { 
        Text[] words = callCrawlKeyWord(url);   // 对网页爬虫,获取 meta 中 keyword 域的词
        for(int i = 0; i &lt; words.length(); i++) 
           for(int j = i + 1; j &lt; words.length(); j++) 
            output.collect((words[i] &lt; words[j])? (
            words[i] + words[j]) : (words[j] + words[i]), new IntWriable(1)); 
    } 

    public void reduce(Text key, Iterator&lt;IntWritable&gt; iter, OutputCollector&lt;Text, 
 IntWritable&gt; output, Reporter reporter)throws IOException { 
        output.collect(key, iter 中包含元素的数目 );   //value 为两个词共现次数
    } 
    … . 
 } 

  1. 总计单个词出现次数

    为计算词与词的相关度,除获得两词共现次数外,还应取得每一种词的出现次数。能够通过贰个非凡的
    Map/Reduce 来进展总结。个中,Map 以率先个 Reduce
    的输出为输入,对每一个词对 i 和 j,输出两条记下,key 分别为词 i 和词
    j,value 均为两词共现次数 ;Reduce 完成词次数的计算。

**清单 8. 词与词相关度计算 -1 (单个词次数统计)**  

<table>
<colgroup>
<col style="width: 100%" />
</colgroup>
<tbody>
<tr class="odd">
<td><pre class="displaycodeliquid"><code>              
public class WordsCorrCal2 extends Configured implements Tool, Mapper&lt;Text, 
IntWritable, Text, IntWritable&gt;, Reducer&lt;Text, IntWritable, Text, 
LuceneDocumentWrapper &gt;{ 
    public void map(Text wordPair, IntWritable cnt, OutputCollector&lt;Text, 
 IntWritable&gt; output, Reporter reporter)throws IOException { 
        将 wordPair 分为两个词 word1, word2 
        output.collect(word1, cnt); 
        output.collect(word2, cnt); 
    } 

public void reduce(Text key, Iterator&lt;IntWritable&gt; iter, OutputCollector&lt;Text, 
 LuceneDocumentWrapper&gt; output, Reporter reporter)throws IOException { 
        int wordCnt = 0; 
        while(iter.hasNext()) 
            wordCnt += iter.next().get(); 
        // 建立 Lucene 索引,以 word 为 key,出现次数作为 value,进行存储
        Document doc = new Document(); 
        doc.add(new Field(&quot;word&quot;, key.toString(), Field.Store.NO, 
            Field.Index.UN_TOKENIZED)); 
        doc.add(new Field(&quot;count&quot;, wordCnt, Field.Store.YES,Field.Index.NO)); 
        output.collect(new Text(), new LuceneDocumentWrapper(doc)); 
    } 
    … . 
 } 

  1. 总括词对相关度

    今昔有八个公文:多个文件中著录的是单个词出现的次数;另一文书记录的则是词对出现的次数。怎么着从那五个文件得到词与词的相关度?最直观的思绪是将单个词出现次数作为目录文件输出,key
    为词,value 为词的次数;再进行2个Map,以第词对共现次数文件为输入,在处理每条记下时,查询索引文件一遍,然后遵照共现频率公式计算获得结果。

**清单 9. 词与词相关度计算 -1 (查找索引文件)**  

<table>
<colgroup>
<col style="width: 100%" />
</colgroup>
<tbody>
<tr class="odd">
<td><pre class="displaycodeliquid"><code>              
public class WordsCorrCal3 extends Configured implements Tool, Mapper&lt;Text,
 IntWritable, Text, FloatWritable &gt;{ 
    public void map(Text wordPair, IntWritable cnt, OutputCollector&lt;Text, 
 FloatWritable &gt; output, Reporter reporter)throws IOException { 
        将 wordPair 分为两个词 word1, word2 
        查找 Lucene 索引文件 , 得到 word1 出现次数 cnt1 
        查找 Lucene 索引文件 , 得到 word2 出现次数 cnt2 
        计算 Pij。Pij = cnt/(cnt1 + cnt2 – cnt); 
        output.collect(wordPair, new FloatWritable(Pij)); 
    } 
    … . 
 } 

  • MapReduce 中的连接 — 合并数据集的策略

当词音讯文件较大,查询 Lucene
索引文件的频率也会回落,因为对每一个词对,都要物色四次词的目录文件,所以查找索引文件的次数量级在
O(n2),查询代价也会相对较大。可以用其它一种政策形成词对相关度的测算。将多个文本同时作为
Map 的输入,在 Map 内部判断记录来自于哪个文件,进行对应处理,在 Reduce
中形成数据集的联合。图 8 体现了对应流程。

图 8.MapReduce 完毕词与词相关度计算 -2
航天科工 10 

  1. 第 1 个 map-reduce 合并单个词次数文件和词对次数文件。

    Map 输入来自多个差别文件:单个词次数文件和词对共现次数文件。Map
    内部对来源多个公文的记录进行分化操作,最终拼成相同格式举行输出。输出的
    key 为单个词,value 形如 “第三个词 + 共现次数 \t
    单个词次数”。没有的有个别,以空字符补齐。那样,对于第贰种情景,value
    中以 \t 相隔的第2有的便是空字符;而对此第三种状态,value 中以 \t
    相隔的第叁有个别为空字符。

    Reduce 遍历迭代器中著录,对第2局地为空字符的,将 key
    词对应次数提取出来,不然,记录对应的是与该词相关的其它词及共现次数新闻,把这么些音信放到多少个数组。遍历完结,对数组中各类成分,进行输出,输出
    key 为词 1+ 词 2+ 共现次数 ( 字典序在前的词在前 ),value 为 Reduce
    输入 key 词(词 1 只怕词 2)的次数音讯。

**清单 10. 词与词相关度计算 -2 (拼成统一格式)**  

<table>
<colgroup>
<col style="width: 100%" />
</colgroup>
<tbody>
<tr class="odd">
<td><pre class="displaycodeliquid"><code>              
 public class WordsCorrCal_21 extends Configured implements Tool, Mapper&lt;Text, 
 IntWritable,  Text, Text&gt;, Reducer&lt;Text, Text, Text, IntWritable &gt;{ 
    public void map(Text key, IntWritable cnt, OutputCollector&lt;Text,Text&gt; output, 
    Reporter  reporter)throws IOException { 
        String[] words = key.toString.split(“[\t]”); 
        // 如果对应的是词对的输入文件
        if(words.length() == 2){ 
            output.collect(new Text(words[0]), new Text(
            words[1] + ”\t” + cnt + “\t”)); 
            output.collect(new Text(words[1]), new Text(
            words[0] + ”\t” + cnt + “\t”)}; 
        ) else if(words.length() == 1) { // 如果对应的是单个词的输入文件
            output.collect(key, new Text(“\t” + cnt); 
        ) 
 } 

    public void reduce(Text key, Iterator&lt;Text&gt; iter, OutputCollector&lt;Text,
    IntWritable&gt; output,Reporter reporter)throws IOException { 
        ArrayList&lt;String&gt; corrWords = new ArrayList&lt;String&gt;(); 
        int wordCnt; 
        while(iter.hasNext()){ 
            String val = iter.next().toString(); 
            String[] vals = val.split(“[\t]”); 
            if(vals.length() == 2)   //val 存储的是单个词出现次数
                wordCnt = Integer.parse(vals[1]); 
            else   //val 存储的是词对的信息,前两项分别是共现词及共现次数
                corrWords.add(vals[0]+”\t”+vals[1]); 
        ) 
        for(String corrWord: corrWords){   // 输出 key 为:词 1+ 词 2+ 共现次数;
        //输出 value:单个词次数
            String[] cor = corrWords.split(“[\t]”); 
            output.collect((key &lt; cor[0])?(key + “\t” + corrWord):(
            cor[0] + “\t” + key + cor[1]),wordCnt); 
        } 
    } 
    … . 
 } 

  1. 第 2 个 map-reduce 计算共现频率。

    含蓄3个 Reduce,输入为上一 map-reduce 的出口,key 为词 1+ 词 2+
    共现次数,value
    为单个词的次数。迭代器里分别收获七个词的次数消息,然后利用共现频率公式计算七个词的相关度。Reduce
    的输出 key 为词 1+ 词 2,value 为多少个词的共现频率。

**清单 11. 词与词相关度计算 -2 (计算相关度)**  

<table>
<colgroup>
<col style="width: 100%" />
</colgroup>
<tbody>
<tr class="odd">
<td><pre class="displaycodeliquid"><code>              
 public class WordsCorrCal_22 extends Configured implements Tool, Reducer&lt;Text, 
 IntWritable,Text, FloatWritable &gt;{ 
    public void reduce(Text key, Iterator&lt;IntWritable&gt; iter, 
 OutputCollector&lt;Text,FloatWritable&gt; output,Reporter reporter)throws IOException { 
        int word1Cnt = iter.next().get(); 
        int word2Cnt = iter.next().get(); 
        将 key 解析成 word1,word2,共现次数 corrCnt。
        float pij = corrCnt/(word1Cnt + word2Cnt - corrCnt); 
        output.collect(new Text(word1 + word2), new FloatWritable(pij)); 
    } 
    … . 
 } 

  1. 第 3 个 map-reduce 建立词相关度音信索引文件。

    航天科工,第 3 个 map-reduce 获得每一个词的相干词音信,并树立目录文件。Lucene
    索引文件的多个域分别为“word”和“corrInfo”。

    Map 的输入 key 为词 1+ 词 2,value 为相关度。Map 将词 1 和词 2
    拆开进行输出。输出 key 为词 1,value 为词 2+ 相关度;输出 key 为词
    2,value 为词 1+ 相关度。

    Reduce 把 key
    相同的集聚到一块,并把迭代器中的词及关切度音信拼在一起,形成二个字符串,作为
    corrInfo 域的内容。

**清单 12. 词与词相关度计算 -2 (输出索引文件)**  

<table>
<colgroup>
<col style="width: 100%" />
</colgroup>
<tbody>
<tr class="odd">
<td><pre class="displaycodeliquid"><code>              
 public class WordsCorrCal_23 extends Configured implements Tool, Mapper&lt;Text, 
 FloatWritable, Text, Text&gt;, Reducer&lt;Text, Text,Text, LuceneDocumentWrapper&gt;{ 
    public void map(Text wordPair, FloatWritable corr, 
 OutputCollector&lt;Text,Text&gt; output,Reporter reporter)throws IOException { 
        将 key 解析成 word1,word2 
        output.collect(new Text(word1), new Text(word2 + “\t” + corr.get()); 
        output.collect(new Text(word2), new Text(word1 + “\t” + corr.get()); 
    } 

    public void reduce(Text key, Iterator&lt;Text&gt; iter, OutputCollector&lt;Text, 
 LuceneDocumentWrapper&gt; output,Reporter reporter)throws IOException { 
        String corrInfo = “”; 
        while(iter.hasNext()) 
            corrInfo = corrInfo + iter.next() + “\t”; 
        // 建立 Lucene 索引,以 word 为 key,共现词信息作为 value,进行存储
        Document doc = new Document(); 
        doc.add(new Field(&quot;word&quot;, key.toString(), Field.Store.NO, 
            Field.Index.UN_TOKENIZED)); 
        doc.add(new Field(&quot;corrInfo&quot;, corrInfo, Field.Store.YES,Field.Index.NO)); 
        output.collect(new Text(), new LuceneDocumentWrapper(doc)); 
    } 
    … . 
 } 

  • 用户访问词列表调整

图 9.MapReduce 达成用户访问关键词扩张
航天科工 11 

取得词对相关度后,即能够对用户访问关键词列表举行扩充。如图 9
所示,只需二个 Map 即可到位操作。Map 以用户访问词列表为输入,key
为用户,value 为机要词列表。对于主要词列表中的各个词
A,都会寻找词相关度索引文件,获得与词 A 相关的词列表 AL。遍历
AL,如果 AL中的词 B
也被用户访问过,那么要将用户访问词 B 的值× A 和 B 的相关度的结果插足到 A
的旧值上;假如 AL中的词 C 用户没有访问过,则要把词 C
出席到用户访问词列表中,并将词 A 的旧值× A 和 C 的相关度插手到词 C
值上。Map 的输出 key 仍为用户,value
为用户访问的词列表及相应的新的关心度值。

清单 13. Map 实现重庆大学词增加

                
 public class WordExp extends Configured implements Tool, Mapper<Text, Text, 
 Text, Text >{ 
    IndexSearcher searcher = null;   // 用于查询 Lucene 索引文件
    public void map(Text key, Text val, OutputCollector<Text,Text> output,Reporter 
 reporter)throws IOException { 
        HashMap<String, float> words;   //key 为词,value 为用户访问该词的权重
        HashMap<String, float> wordNewInfo;   // 存储调整后的列表信息
        将 val 关键词信息进行解析,依次置入 words; 
        拷贝 words 中信息至 wordNewInfo 中 ; 
        for(words 中每一个关键词 word){ 
            float w1 = words.get(word); 
            查找 Lucene 索引文件,得到该词相关词列表 corrWords; 
            for(corrWords 中每个词 corrW){ 
                // 如果 corrW 也被用户访问,修改两个词的权重
                if((float w2 = words.get(corrW)) != null){ 
                    wordsNewInfo.put(word, wordsNewInfo.get(word) + w2 * corrW.pij); 
                    wordsNewInfo.put(corrW, wordsNewInfo.get(corrW) + w1 * corrW.pij); 
                }else{   // 如果未被访问,将词加入到用户访问列表中
                    wordsNewInfo.put(corrW, w1 * corrW.pij); 
                } 
            } 
        } 
        String wordListNew = “”; 
        for(wordNewInfo 中每个元组 entry) 
            wordListNew = wordListNew + entry.getKey() + entry.getVal(); 
        output.collect(key, new Text(wordListNew); 
    } 

    // configure 函数会在每个 Map 节点运行 Map 函数对文件按行处理之前调用,通常用来做全局操作
    public void configure(JobConf job) { 
        String corListPath = job.getStrings(“corrList.path”)[0]; /// 内部获得特征权重路径
        FsDirectory fsDirectory = new FsDirectory(FileSystem.get(getConf()),corListPath, 
 false,getConf()); 
        searcher = new IndexSearcher(fsDirectory); 
    } 

    public void runWordExp(String input, String output, String corPath){ 
        JobConf job = new JobConf(getConf(),WordExp.class); 
        设置 InputPath, outPath, MapperClass, InputFormat, OutputFormat, …
        job.setStrings(“corrList.path”, corPath);   // 设置相关词列表索引信息
        JobClient.run(job); 
    } 
    … . 
 } 

回页首

结束语

MapReduce
编制程序模型由于其百战不殆的计算能力、优良的可扩大性和易用性,在工产业界和知识界获得了科学普及应用。对广大数据批量处理的特色,使得
MapReduce 特别适用于日志分析类应用。MapReduce 编程模型的底子是 Map 和
Reduce
函数,如何将动用全部依然某个更换成那两类总括形式,即将应用并行化,是有肯定技术的。本文对用户兴趣点挖掘利用进行MapReduce 的兑现,除在多少挖掘领域提议意见,MapReduce
的贯彻形式也为用户展开利用并行化提供了参考。

参考资料

学习

讨论

有关小编

航天科工 12

马丽女士丽,就职于IBM
CDL,在广泛数据处理领域,特别是MapReduce编制程序模型方面有两年多切磋经历,分别以率先我

发表评论

电子邮件地址不会被公开。 必填项已用*标注