搜索
＊总第３２０期２０１６年第６期计算机与数字工程Ｃｏｍｐｕｔｅｒ＆ＤｉｇｉｔａｌＥｎｇｉｎｅｅｒｉｎｇＶｏｌ．４４Ｎｏ．６１０５７基于Ｈａｄｏｏｐ的图书推荐系统研究与设计南磊１，２（１．江苏省信息中心南京２１００１３）（２．计算机软件新技术国家重点实验室（南京大学）南京２１００２３）摘要经过近些年的发展，图书市场在种类规模和总体数量等方面有了长足的进步。但是同时也带来了图书过多，使得读者难以选择合适图书的困难。常规的明细分类使得读者可以针对每一种类型的书进行选择，但是其每个分类下依然有成千上万中书籍。论文完成的是一种基于Ａｐｒｉｏｒｉ算法创建关联规则的图书推荐在Ｈａｄｏｏｐ上的实现。利用在豆瓣读书上获取的图书评论数据，使用Ｈａｄｏｏｐ生成图书的Ｋ－频繁集，并计算相关的图书推荐置信度。论文实现的算法能够高效地为读者提供推荐服务。关键词ＭａｐＲｅｄｕｃｅ；并行计算；关联规则；图书推荐；Ｈａｄｏｏｐ中图分类号ＴＰ３１１ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７２－９７２２．２０１６．０６．０１６ＲｅｓｅａｒｃｈａｎｄＤｅｓｉｇｎｏｆＨａｄｏｏｐ－ＢａｓｅｄＢｏｏｋＲｅｃｏｍｍｅｎｄａｔｉｏｎＳｙｓｔｅｍＮＡＮＬｅｉ１，２（１．ＪｉａｎｇｓｕＩｎｆｏｒｍａｔｉｏｎＣｅｎｔｅｒ，Ｎａｎｊｉｎｇ２１００１３）（２．ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙｆｏｒＮｏｖｅｌＳｏｆｔｗａｒｅＴｅｃｈｎｏｌｏｇｙ（ＮａｎｊｉｎｇＵｎｉｖｅｒｓｉｔｙ），Ｎａｎｊｉｎｇ２１００２３）ＡｂｓｔｒａｃｔＡｆｔｅｒｙｅａｒｓｏｆｄｅｖｅｌｏｐｍｅｎｔ，ｔｈｅｂｏｏｋｍａｒｋｅｔｉｎｔｈｅｔｙｐｅｏｆｓｃａｌｅａｎｄｔｈｅｏｖｅｒａｌｌｎｕｍｂｅｒｏｆｓｕｃｈａｒｅａｓｈａｖｅｍａｄｅｃｏｎｓｉｄｅｒａｂｌｅｐｒｏｇｒｅｓｓ．Ｂｕｔａｔｔｈｅｓａｍｅｔｉｍｅ，ｉｔｂｒｉｎｇｓｔｏｏｍａｎｙｂｏｏｋｓ，ｗｈｉｃｈｍａｋｅｓｉｔｄｉｆｆｉｃｕｌｔｆｏｒｒｅａｄｅｒｓｔｏｃｈｏｏｓｅｔｈｅｒｉｇｈｔｂｏｏｋｓ．Ｔｈｅｇｅｎｅｒａｌｃｌａｓｓｉｆｉｃａｔｉｏｎａｌｌｏｗｓｔｈｅｒｅａｄｅｒｔｏｃｈｏｏｓｅｆｒｏｍｅａｃｈｔｙｐｅｏｆｂｏｏｋ，ｂｕｔｔｈｅｒｅａｒｅｓｔｉｌｌｔｈｏｕｓａｎｄｓｏｆｂｏｏｋｓｕｎｄｅｒｅａｃｈｃａｔｅｇｏｒｙ．Ｉｎｔｈｉｓｐａｐｅｒ，ａｋｉｎｄｏｆｂｏｏｋｒｅｃｏｍｍｅｎｄａｔｉｏｎｂａｓｅｄｏｎｔｈｅＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｔｏｃｒｅａｔｅｔｈｅａｓｓｏｃｉ－ａｔｉｏｎｒｕｌｅｓｉｓｒｅａｌｉｚｅｄｉｎＨａｄｏｏｐ．Ｕｓｉｎｇｔｈｅｂｏｏｋｒｅｖｉｅｗｄａｔａｏｂｔａｉｎｅｄｆｒｏｍｔｈｅｂｏｏｋｒｅｖｉｅｗ，ＨａｄｏｏｐｉｓｕｓｅｄｔｏｇｅｎｅｒａｔｅｔｈｅＫ－ｆｒｅｑｕｅｎｔｓｅｔｓｏｆｂｏｏｋｓ，ａｎｄｔｈｅｒｅｌｅｖａｎｔｂｏｏｋｓｒｅｃｏｍｍｅｎｄｅｄｃｏｎｆｉｄｅｎｃｅｉｓｃａｌｃｕｌａｔｅｄ．Ｔｈｅａｌｇｏｒｉｔｈｍｃａｎｅｆｆｉｃｉｅｎｔｌｙｐｒｏｖｉｄｅｔｈｅｒｅｃｏｍｍｅｎｄａｔｉｏｎｓｅｒｖｉｃｅｆｏｒｒｅａｄｅｒｓ．ＫｅｙＷｏｒｄｓＭａｐＲｅｄｕｃｅ，ｃｏｎｃｕｒｒｅｎｔｃｏｍｐｕｔａｔｉｏｎ，ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，ｂｏｏｋｒｅｃｏｍｍｅｎｄａｔｉｏｎ，ＨａｄｏｏｐＣｌａｓｓＮｕｍｂｅｒＴＰ３１１１引言近几年，由于多终端接入网络的便利性，越来越多的读者开始利用因特网来记录自己对各种事务的评价，这就形成了针对不同商品的庞大的评论数据集。其中图书的种类繁多，内容相对于小商品、电影、音乐等需要比较长的时间才可以被读者体会，利用其他读者对不同书籍的评价和感兴趣程度为其他读者提供阅读推荐成为推广文化和扩大书籍销售的一种重要手段。传统上要实现这样的推荐系统可以采用Ａｐｒｉｏｒｉ算法［２］。这个算法基于关联规则，挖掘出数据集中有较大联系的数据项。并以此作为依据给读者推荐其可能感兴趣的书籍。但Ａｐｒｉｏｒｉ算法存在一个问题，就是它需要不断地去扫描整个数据库，效率很低。在面对一些访问量较大的网站时，客户的数量和其留下的有用信息都是以百万的数量级来表示的，在面对这种海量数据时Ａｐｒｉｏｒｉ算法在单机上的运行比较慢，并且可能超出了普通主机、大型机的性能限制。基于以上想法，我们采用了基于ＭａｐＲｅｄｕｃｅ的方法［１］，用并行优化后的算法来进行处理，期望以一种可以接＊收稿日期：２０１５年１２月５日，修回日期：２０１６年１月２６日基金项目：国家自然科学基金面上项目（编号：６１２７２４１８）资助。作者简介：南磊，男，博士研究生，助理研究员，研究方向：大数据、无线网络、软件工程等。１０５８南磊：基于Ｈａｄｏｏｐ的图书推荐系统研究与设计第４４卷受的成本快速地实现Ａｐｒｉｏｒｉ算法在图书推荐上的应用。２相关技术２．１网络爬虫网络爬虫是捜索引擎抓取系统的重要组成部分。爬虫的主要目的是将互联网上的网页下载到本地形成一个或联网内容的镜像备份［７］。２．１．１网络爬虫的基本结构及工作流程一个通用的网络爬虫的框架如图１所示。２．２数据挖掘相关算法２．２．１关联规则关联规则是用来描述事物之间的联系，是用来挖掘事物之间的相关性。挖掘关联规则的核心是通过统计数据项获得频繁项集，现有的算法主要有Ａｐｒｉｏｒｉ、ＰＡＲＴＩＴＩＯＮ、ＦＰ２ｇｒｏｗｔｈ及抽样算法等。设Ｉ＝｛ｉ１ｉ２，…ｉｍ｝是项的集合，设任务相关的数据Ｄ是数据库事务的集合，其中每个事务Ｔ是项的集合，使得Ａ包含于Ｉ。每一个事务有一个标志符，称作ＴＩＤ，设Ａ是一个项集，事务Ｔ包含Ａ，关联规则是形如Ａ→Ｂ的蕴涵式，并且Ａ∩Ｂ＝。图１网络爬虫基本原理图网络爬虫的基本工作流程如下：１）首先选取一部分精心挑选的种子ＵＲＬ；２）将这些ＵＲＬ放入待抓取ＵＲＬ队列；３）从待抓取ＵＲＬ队列中取出待抓取在ＵＲＬ，解析ＤＮＳ，并且得到主机的ＩＰ，并将ＵＲＬ对应的网页下载下来，存储进已下载网页库中。此外，将这些ＵＲＬ放进已抓取ＵＲＬ队列；４）分析已抓取ＵＲＬ队列中的ＵＲＬ，分析其中的其他ＵＲＬ，并且将ＵＲＬ放入待抓取ＵＲＬ队列，从而进入下一个循环。２．１．２抓取策略在爬虫系统中，待抓取ＵＲＬ队列是很重要的一部分。待抓取ＵＲＬ队列中的ＵＲＬ以什么样的顺序排列也是一个很重要的问题，因为这涉及到先抓取那个页面，后抓取哪个页面。而决定这些ＵＲＬ排列顺序的方法，叫做抓取策略。下面是几种常见的抓取策略：１）深度优先遍历策略；２）宽度优先遍历策略；３）反向链接数策略；４）ＰａｒｔｉａｌＰａｇｅＲａｎｋ策略；５）ＯＰＩＣ策略策略；６）大站优先策略。定义１：可信度／置信度（Ｃｏｎｆｉｄｅｎｃｅ）。可信度即是“值得信赖性”。设Ａ，Ｂ是项集，对于事务集Ｄ，Ａ∈Ｄ，Ｂ∈Ｄ，Ａ∩Ｂ＝，Ａ→Ｂ的可信度定义为：可信度（Ａ→Ｂ）＝包含Ａ和Ｂ的元组数／包含Ａ的元组数。定义２：支持度（Ｓｕｐｐｏｒｔ）。支持度（Ａ→Ｂ）＝包含Ａ和Ｂ的元组数／元组总数。支持度描述了Ａ和Ｂ这两个项集在所有事务中同时出现的概率。定义３：强关联规则。设ｍｉｎ＿ｓｕｐ是最小支持度阈值；ｍｉｎ＿ｃｏｎｆ是最小置信度阈值。如果事务集合Ｔ中的关联规则Ａ→Ｂ同时满足Ｓｕｐｐｏｒｔ（Ａ→Ｂ）＞＝ｍｉｎ＿ｓｕｐ，Ｃｏｎｆｉｄｅｎｃｅ（Ａ→Ｂ）＞＝ｍｉｎ＿ｃｏｎｆ，则Ａ→Ｂ称为Ｔ中的强关联规则。而关联规则的挖掘就是在事务集合中挖掘强关联规则。２．２．２Ａｐｒｉｏｒｉ算法［１］Ａｐｒｉｏｒｉ算法是Ｒ．Ａｇｒａｗａｌ和Ｒ．Ｓｒｉｋａｎｔ在１９９４年提出的基本关联规则挖掘算法。该算法的核心思想是基于频集理论的一种递推方法，目的是从数据库中挖掘出那些支持度和信任度都不低于给定的最小支持度阈值和最小信任度阈值的关联规则。算法通过迭代的方法反复扫描数据库来发现所有的频繁项目集。通过频繁项集的性质知道，只有那些确认是频繁项的候选集所组成的超集才可能是频繁项集。故只用频繁项集生成下一趟扫描的候选集，即Ｌｉ－１生成Ｃｉ（其中：Ｌ为频繁项集的集合，Ｃ为候选项集的集合ｉ为当前扫描数据库的次数），在每次扫描数据库时只考虑具有同数目数据项的集合。Ａｐｒｉｏｒｉ算法可以生成相对较少的候选数据项集，候选数据项集不必再反复地根据数据库中的记录产生，而是在寻找ｋ频繁数据项集的过程中由前一次循环产生的ｋ－１频繁数据项集一次产生。算法的描述如下所示。［５］［６～８］２０１６年第６期计算机与数字工程１０５９ｋ＝０；／／ｋ表示扫描的次数Ｌ＝；Ｃ１＝Ｉ；／／初始把所有的单个项目作为候选集Ｒｅｐｅａｔｋ＝ｋ＋１；Ｌｋ＝；ＦｏｒｅａｃｈＩｉ∈ＣｋｄｏＣｉ＝０；／／每个项目集的初始计数设为０Ｆｏｒｅａｃｈｔｊ∈ＤｄｏＦｏｒｅａｃｈＩｉ∈ＣｋｄｏＩｆＩｉ∈ｔｊｔｈｅｎＣｉ＝Ｃｉ＋１；ＦｏｒｅａｃｈＩｉ∈ＣｋｄｏＩｆＣｉ＞＝（ｓ×｜Ｄ｜）ｔｈｅｎ／／｜Ｄ｜为数据库中事务项的总数Ｌｋ＝Ｌｋ∪Ｉｉ；Ｌ＝Ｌ∪Ｌｋ；Ｃｋ＋１＝Ａｐｒｉｏｒｉ－Ｇｅｎ（Ｌｋ）；ＵｎｔｉｌＣｋ＋１＝２．３并行计算相关技术２．３．１ＭａｐＲｅｄｕｃｅＭａｐＲｅｄｕｃｅ是一种编程模型，用于大规模数据集（大于１ＴＢ）的并行运算。概念“Ｍａｐ（映射）”和“Ｒｅｄｕｃｅ（化简）”和它们的主要思想都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。它极大地方便了编程人员在不会分布式并行编程的情况下，将自己的程序运行在分布式系统上。当前的软件实现是指定一个Ｍａｐ（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Ｒｅｄｕｃｅ（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。２．３．２ＨａｄｏｏｐＨａｄｏｏｐ是一个分布式基础架构，可以在不了解分布式底层信息的情况下，开发分布式或秉性应用程序，充分利用集群的威力高速运算和存储，它是云计算的主要架构之一。Ｈａｄｏｏｐ具有以下一些特点：·扩容能力：能可靠地存储和处理ＰＢ级别数据；·成本低：可以通过普通微机组成的集群来分发以及处理数据。这些服务器群总计可达数千个节点；·高效率：通过分发数据，Ｈａｄｏｏｐ可以并行地处理数据，这使得处理非常的快速；·可靠性：Ｈａｄｏｏｐ能自动地维护数据的多份复制，并且在任务失败后能自动地重新部署计算任务。Ｈａｄｏｏｐ是ＧｏｏｇｌｅＭａｐＲｅｄｕｃｅ算法的开源实现，ＭａｐＲｅｄｕｃｅ的执行流程主要包括Ｍａｐ和Ｒｅ－ｄｕｃｅ两步。一个任务启动后，会在集群上按各个节点的能力配置产生相应个数的Ｍａｐ进程。每个Ｍａｐ进程处理一个具有ｋｅｙ－ｖａｌｕｅ特性的数据分块，产生一组ｋｅｙ－ｖａｌｕｅ对形式的结果。当一个节点上的某个Ｍａｐ进程执行结束后，集群的Ｈａｄｏｏｐ架构会在这个节点上启动一个新的Ｍａｐ进程处理下一个分块。而Ｒｅｄｕｃｅ进程对每个Ｍａｐ进程产生的ｋｅｙ－ｖａｌｕｅ对进行合并，完成计算。３总体设计通过以下几个步骤实现图书推荐系统：１）网络源数据获取；２）对源数据进行抽取和清洗，以达到实验算法的需求；３）Ａｐｒｉｏｒｉ算法在Ｈａｄｏｏｐ上的实现；４）最终界面的实现以及相关测试。其中数据来源有两个部分：１）图书列表由图书馆网站获得；２）以图书馆图书为基础，获取每一本图书在豆瓣读书（ｂｏｏｋ．ｄｏｕｂａｎ．ｃｏｍ）上的用户评论。３．１设计思路基于ＭａｐＲｅｄｕｃｅ的Ａｐｒｉｏｒｉ并行策略，其候选项集的支持数统计类似于单词计数过程，因此在海量数据且支持度较低时，算法产生了大量的候选项集，从而产生了大量〈ｉｔｅｍｓｅｔ，１〉的〈键，值〉对，增加了ＭａｐＲｅｄｕｃｅ系统的负担。比较单词计数与候选项集的支持数统计不难看出，单词计数要统计的单词是未知，因此，单词计数思想较适合找出１－频繁项集。然而，候选项集的支持数统计要统计的候选项集是已知的，它是由频繁项集通过自身的连接而生成的。因此，为提高候选项集支持数统计的效率，大量减少键／值对的产生，将Ａｐｒｉｏｒｉ数据分割的分组思想应用在候选项集的支持数统计阶段，实现候选项集支持数的分组统计，较大幅度地提高了算法的运行效率。实验拟采用的最基本的ＭａｐＲｅ－ｄｕｃｅ并行的Ａｐｒｉｏｒｉ分组统计算法思路为：采用类似单词计数的过程并行扫描数据库