欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

计算机论文
当前位置:首页 > 计算机论文
关联规则推荐的高效分布式计算框架
来源:一起赢论文网     日期:2019-12-13     浏览数:301     【 字体:

 essly fuses the association rule mining and the recommendation computing.Firstly,based on the summarization of existing rule-based approaches,a tree-type structure calledOrdered Patterns Forest(OPF)is designed for the compact representation and storage of frequentpatterns,without missing any basic information that will be useful for the subsequent recommendationsuch as support of a pattern and its nested patterns.Secondly,we transform the two-step rulebased recommendation to a series of operations on the data structure,and then develop thecorresponding efficient algorithms for these operations which are responsible for mining eligiblepatterns as well as computing recommendation scores.Specifically,we transform the candidaterules mining into a path searching problem on the OPF and thus present a path searching algorithmrunning on the single machine.Finally,the real-time recommendation is impossible to be completedin a single machine.Hence,in order to handle the ever-increasing of online customers and patterns,we devise a distributed computing framework in which a novel load balanced strategy for datapartitioning is also proposed to reduce the running time of the task that finishes lastly and thusfurther improves the overall performance.At last,we implement the proposed framework andalgorithms on Spark,a widely used memory-based distributed computing engine,and evaluate theframework and algorithms on three real-world datasets,i.e.,Accidents,Webdocs and Amazon.The experimental results demonstrate that the efficiency improved by the proposed OPF with thepath searching algorithm is more than six times that of the traditional brute force method.Moreover,the proposed load balanced strategy is effective to further improve the performance of the proposeddistributed association rule based recommendation framework,which can achieve nearly linearscalability along with the increase of computational nodes.Keywords recommender systems;association rules;frequent patterns;FP-growth;Spark;loadbalancing1 引 言推荐系统在近十年来受到学术界的充分重视和深入研究,并在电子商务网站、社交平台及视频音乐网站上得到广泛应用[1-2].各种各样的推荐模型和方法相继被提出,主要包含基于内容的方法、协同过滤模型、混合式模型、基于关联规则的方法等[3-4].关联规则最早应用于购物篮分析,可揭示一组经常被一起购买的商品,因此自然而然地成为一种简明且可解释性极佳的推荐模型.例如,由于集合{单反相机,单反镜头,三脚架}中的商品经常一起被购买,当用户购买或频繁浏览“单反相机”和“单反镜头”时,就将“三脚架”推荐给用户.基于关联规则的推荐本质上利用了项目(item)之间的关联性,其机理类似于基于项 目 的 协 同 过 滤 模 型 (Item-based Collabora-tive Filtering)[5],因而很多文献如[3,6]将基于关联规则的推荐归类于协同过滤模型.关联规则推荐是一类非常流行的推荐方法,大量电子商务网站将基于关联规则的方法作为其商用推荐 引 擎,比 如:YouTube 使 用 关 联 规 则 推 荐 视频[7]、淘宝和亚马逊网站上的“购买此商品的顾客也同时购买”及“经常一起购买的商品”等推荐方式也依托于关联规则构建.关联规则推荐能获得大量实际应用的原因是:(1)推荐结果可由用户操作动态触发,即用户浏览或购买记录发生变化时,经过与关联规则库的快速匹配,推荐结果可以快速更新;(2)关联规则能揭示推荐结果与浏览或已购买商品之间的共现关联,这使得推荐结果具有良好的可解释性.由于频繁模式的反单调性,一个频繁模式包含很多频繁子模式,而一个频繁模式也能导出多个关联规则,因此关联规则数量巨大、且多个规则蕴含同个目标项目的情况广泛存在.为了提升推荐准确率,大量研究工作围绕如何挑选高质量规则展开.早期的研究大多挑选置信度(confidence)最高的规则来推荐[8-10],文献[11]挑选最长规则,文献[12]则提出综合利用置信度、支持度(support)和长度对规则进行排序.近年来,一些新指标能进一步提升关联规则6期 李昌盛等:关联规则推荐的高效分布式计算框架2191 如 校 正 置 信 度 (adjusted confi-dence)[13]、分离置信度(disjunctive confidence)[14]、互信息[15]等.还有一些研究认为需融合与目标项目相同的规则集以此来得到综合推荐分值,文献[16-17]将多个规则的统计量相加获得推荐分值,文献[18]引入 D-S证据理论合成多规则的分段支持度值(par-titioned support)作为推荐分值.上述研究工作的本质区别在于推荐分值计算方式不同,而候选规则集的匹配过程是相同的,设有规则“{单反相机,单反镜头}→三脚架”,若其前项{单反相机,单反镜头}包含用户的浏览或购买记录,但结果项{三脚架}却不包含,则该规则就是此用户的一条候选规则,结果项为待推荐的目标项目.在实际电子商务网站上,用户并发访问量极高,据统计,淘宝并发在线用户经常高达千万[19],而关联规则数量又十分庞大.如何为如此大量在线用户搜索候选规则的计算效率,成为制约关联规则推荐实际应用的瓶颈问题,尤其是当用户浏览和购买记录动态变化,推荐结果需实时生成的情形.但是,大部分已有研究主要关注关联规则推荐的准确性及关联规则的挖掘效率,而面向大规模在线用户和规则的匹配计算效率却未曾得到关注.本文试图提出面向关联规则推荐的可扩展性计算框架,能无缝兼容已有研究所提出的推荐分值计算方法,缓解关联规则推荐面临的大数据挑战.本文第2节总结相关工作;第3节正式定义问题并总体介绍面向关联规则推荐的可扩展分布式框架;第4节针对分布式框架中各个模块的展开详细介绍;第5节为实验结果和分析;第6节总结全文.2 相关工作本文将提出分布式计算框架旨在将规则挖掘与推荐计算两个阶段无缝衔接,并能支撑现有的推荐分值计算方法.因此,本节将从关联规则挖掘和基于关联规则推荐两个方面回顾相关工作.2.1 关联规则挖掘关联规则由频繁模式生成,频繁模式挖掘的核心是提升计算效率,所有挖掘方法均基于反单调性质对格空间进行剪枝,已有挖掘方法的区别仅在于格 空 间 的 遍 历 次 序 以 及 原 始 数 据 的 组 织 方 式.Agrawal等人[20]基于广度优先遍历提出第一个频繁模式挖掘算法 Apriori,随后 Han等人[21]利用树型结构 组 织 原 始 数 据 并 基 于 深 度 优 先 遍 历 提 出FP-growth算法,Zaki等人[22]利用垂直方式组织原始数据、同 样 基 于 深 度 优 先 遍 历 提 出 Eclat算 法.上述三种算法成为 频 繁模式挖 掘 领域公认 的经典方法.随着数据量的增大,频繁模式挖掘算法的可扩展性日益突出,大量研究围绕如何将 Apriori、FP-growth和 Eclat算法的分布式化展开.由于 Apriori和 Eclat算法均需要从k 项集生成k+1 项集,即本轮计算依赖于上一轮计算的结果,因此其分布式机制需要在共享内存架构中实现[23].而在 Han等人[21]提出FP-growth时就指出可以按每个项目形成投影数据集,将原始数据集划分成独立的若干个投影数据集,从而可将 FP-growth 挖掘分解 成 若干独立 的子任务.Grahne等人[24]将单项投影扩展至组投影,有效控制了独立子任务的数量,成为 FP-growth分布式实现中数据逻辑分割的核心技术.尽管 Spark内存计算模式的出现,能极大地 提 升分布式 Apriori和Eclat算法的效率,但是 FP-growth依然是最适合分布式化的算法,这也是本文在挖掘频繁模式时选择 FP-growth作为基准方法的原因.基于组投影技术,文献[25]在 Hadoop平台上基于 MapReduce 提 出 了 FP-growth 分 布 式 版 本PFP,但是任务间的负载均衡问题未得到考虑,而是简单地将 FList分 割成均等长 度 的组.MLib库[26]沿用 PFP 的 思 路,提 供 了 Spark 环 境 下 的 开 源FP-growth实现.Zhou等人[27]注意到负载均衡对分布式 FP-growth算法性能的重要影响,提出用项目在 FList中 排序位置 的 对数值衡 量 挖掘项目的 负载,缓解了均等分割法导致的负载极度不均衡问题.本文的FP-growth分布式方案依然采用经典的组投影思路[24],但对 FList的负载均衡分割方案做了进一步优化,提出投影数据集规模的估测指标,并以此作为 FList 的 划 分 依 据,既 汲 取 了 分 布 式 FP-growth优势,又提升了现有分布式FP-growth的性能.在实验部分将给出本文分布式 FP-growth算法与分布式 Apriori和 Eclat算法以及采取其他不同负载均衡策 略 的分布式 FP-growth 算法之 间的性能比较结果.值得一提地是,最近一些研究尝试从其他角度提升频繁模式的挖掘效率,比如 Chon等人[28-29]的研究利用 BitMap技术压缩表示数据,以提升 Apriori候选项集生成和支持度计数的速度,并用 GPU 编程2102 计  算  机  学  报 2019年ap计算速度;Song等人[30]则提出增量频繁模式挖掘方法,并在 Hadoop上将增量挖掘方法并行化.2.2 基于关联规则推荐围绕高质量关联规则选择以及推荐分值计算方法,国内外学者展开了广泛研究,以期提升基于关联规则推荐的准确率.除了以置信度作为挑选高质量关联规则的依据[8-10],Rudin等人[13]将校正置信度作为选取关联规则的依据,Ghoshal等人[14-15]相继提出分离置信度和互信息两个指标.Li等人[12]则提出多规则排序方法选取关联规则,依次优先考虑置信度、支持度和前项长度.针对蕴含同个目标项目的多个关联规则,很多研究提出将这些关联规则的统计量融合以获得合理的推荐分值,Lin等人[16]认为待推荐项目的推荐分值应该由多条以此项目为结果的关联 规 则 的 支 持 度 和 置 信 度 乘 积 之 和 来 确 定.Wang等人[17]在计算推荐分值时,将具有相关结果的关联规则的余弦值进行求和.Wickramaratna等人[18]引入 D-S证据理论合成多规则的分段支持度值作为推荐分值.此外,文献[31]对如何选择关联规则推荐以提升冷门商品的覆盖率做了研究.已有的研究均认为制约基于关联规则的推荐在于频繁模式的挖掘阶段,例如文献[25]利用关联规则进行查询推荐,但是仅考虑了关联规则的快速挖掘问题.因此,关联 规则挖掘出来之后的推荐计算(即匹配用户记录与关联规则集合以获得候选规则集合)效率尚未获得充分的重视,而这恰恰是在针对大规模在线用户时实现近实时推荐的关键.本文试图将关联规则挖掘和推荐计算两阶段无缝衔接,提出一个面向关联规则推荐的可 扩展分布式总体框架.同时,本文提出的计算框架具有优良的通用性,能支撑已有的不同推荐分值计算方案,这将在 4.3节中进行讨论.3 问题描述和总体框架3.1 关联规则推荐的可扩展性问题假设I={i1,i2,…,im}是 m 个不同项目的集合,事务数据集 D 表示所有用户的历史浏览或购买记录.在关联分析中,包含多个项目的集合称为项集或模式,项集 X 的支持度为包含X 的事务个数占D中事务的百分比,用supp(X)表示.给定支持度阈值 minisupp,在数据集 D 上 挖掘获得的频繁模式集记为P={p1,p2,…,ps},其中任意一条频繁模式pj={ij1,ij2,…,ij|pj|},|pj|表示频繁模式pj中包含的项目的个数.令 Rjk:Ajk→ijk为频繁模式pj产生的一条关联规则,Ajk是关联规则前项,ijk是关联规则后项,其中 Ajk=pj/{ijk}.在推荐中,规则后项仅包含一 个 项 目,因 此 频 繁 模 式pj可 以 产 生 至 多|pj|个能用于推荐的关联规则.令 Tu为在线用户u的当前浏 览 或 购 买 记 录,Tu的 候 选 规 则 集 合 定 义如下.定义1. 候选规则集合.给定用户u 当前浏览或购买的记录Tu和关联规 则集合R,用户u 的候选规则集合定义为:Ru={Rk:Ak→ik|AkTu,ikTu,Rk∈R}.由定义1,候选规则(eligible rule[12-13])是前项包含于 Tu、且后项不被 Tu包 含 的 规 则 集 合,这 些规则是目标 项 目 推 荐 分 值 的 计 算 依 据.尽 管 选 择高质量规则和计 算 推 荐 分 值 的 方 法 千 差 万 别 (如2.2节所述),根据 Tu搜索出候选规则集合是关联规则推荐的基础步骤,也是制约推荐效率 的 关键.对于给定的 Tu和任意一条关联规则Rj,判定当前规则是否为 Tu的候选规则最朴素的方法就是判断关联规则前项和后项的每一个项目是否包含于 Tu中,显然 这 种 匹 配 策 略 极 为 耗 时.在 最 坏 的 情 况下,挖掘一 个 用 户 所 有 候 选 规 则 的 时 间 复 杂 度 是O∑Rj∈R(Rj T )u,其中 Tu和 Rj分 别表示 Tu和Rj所包含项目的个数.当用户数和关联规则数目都很庞大时,候选规则集合搜索代价将无法忍受,严重制约着各种基于关联规则推荐的真正应用.3.2 总体框架本节给出面向关联规则推荐的可扩展分布式总体框架,如图1所示,框架主要包含两个模块:频繁模式挖掘及推荐计算.第一个模块从全量用户历史事务数据集 D 中挖掘频繁模式,通常采用定期离线计算方式,如每3小时更新频繁模式库,由于事务数据集 D 规模通常极大,我们利用 Spark封装的分布式 FP-growth算法加速关联规则挖掘过程.分布式FP-growth算法包含两次 MapReduce过程[25-26]:首先,对 水 平 分 割 存 储 在 Spark RDD(Resilient Dis-tributed Datasets)中的各数据片进行局部计算,由Reduce函 数 汇 总排 序获 得 频 繁 1-项 集 FList;然后,设计 FList负载均衡分割算法(见4.4节),获得一定数量 的 分 组,将 各 分 组 结 果 广 播 到 水 平 分 割RDD;最后,触发第2次 MapReduce过程,以组投影6期 李昌盛等:关联规则推荐的高效分布式计算框架211201-15;在线出版日期:2018-12-24.本课题得到国家自然科学基金项目(71571093,91646204,71801123)资助.李昌盛,硕士,主要研究方向为数据挖掘和推荐系统.E-mail:lichshe@hotmail.com.伍之昂(通信作者),博士,教授,中国计算机学会(CCF)高级会员,主要研究领域为数据挖掘和推荐系统.E-mail:zawuster@gmail.com.张 璐,博士,讲师,主要研究方向为数据挖掘.曹 杰,博士,教授,主要研究领域为数据挖掘和商务智能.关联规则推荐的高效分布式计算框架李昌盛1) 伍之昂1),2) 张 璐1),2) 曹 杰1),2)1)(南京财经大学信息工程学院 南京 210003)2)(南京财经大学江苏省电子商务重点实验室 南京 210003)摘 要 关联规则推荐模型是在电子商务网站应用最广泛的商用推荐引擎之一,目前已有的工作大多聚焦于如何挑选高质量规则,以提升推荐精度.然而,关联规则数量庞大,且用户并发访问量通常极大,如何快速匹配用户浏览记录和关联规则库,为海量在线用户产生近实时推荐,成为制约关联规则推荐能否胜任真实电子商务网站推荐的重要因素.为此,本文研究关联规则推荐的效率问题,提出服务于高效关联规则推荐的分布式计算框架,将规则挖掘与推荐计算无缝衔接.具体而言,本文首先设计有序模式森林,用于压缩存储频繁模式;然后将候选规则挖掘转化为森林上的路径搜索计算,并提出高效的单机路径搜索算法;最后提出负载均衡的数据分割策略,同时降低分布式规则挖掘与推荐计算中的任务最迟完成时间.在3个公开数据集的实验结果表明基于有序模式森林的推荐计算比传统穷举匹配策略降低6倍以上时间,同时所提出的分布式计算框架可随计算节点数量达到近线性扩展.关键词 推荐系统;关联规则;频繁模式;FP-growth算法;Spark;负载均衡中图法分类号 TP18   DOI号 10.11897/SP.J.1016.2019.01218An Efficient Distributed-Computing Framework forAssociation-Rule-Based RecommendationLI Chang-Sheng1) WU Zhi-Ang1),2) ZHANG Lu1),2) CAO Jie1),2)1)(School of Information Engineering,Nanjing University of Finance and Economics,Nanjing 210003)2)(Jiangsu Provincial Key Laboratory of E-Business,Nanjing University of Finance and Economics,Nanjing 210003)Abstract  The association rule based recommendation model is one of the most widely usedcommercial recommendation engines in e-commerce websites.A variety of techniques,mainlyincluding eligible rule selection and multiple rules combination,have been developed to createeffective recommendation.Unfortunately,the efficiency of the association rule based recommendationhas been paid for little attention.In real-life online shopping sites,the concurrency traffic is usuallyvery high,that is,there are a vast amount of users visiting sites simultaneously and persistentlyadding commodities into their baskets.In the meanwhile,the volume of frequent patterns areusually very large and thus the number of association rules derived from these patterns is muchlarger because a pattern is able to generate several rules.As the large amount of the associationrules and the concurrent access of users,how to match the browsing histories of users with thelarge set of rules efficiently in order to offer nearly real-time recommendations for massive onlineusers,has become a vital concern which restricts whether the association rule based recommendationmodel could be used on the real-life e-commerce websites.To address this problem,this paperfocuses on the efficiency of the association rule based recommendation and develops a distributedcomputing framework for improving the computational performance of rule based recommendation,图 1 面向关联规则推荐的可扩展分布式总体框架方法(见 4.1 节)形 成 新 的 逻 辑 分 割 RDD,并 调 用FP-growth进行局部挖掘.在分布式关联规则挖掘中,提出 FList负载均衡分割算法,提升传统分布式FP-growth挖掘框架的效率.图1给出的分布式框架也可 以 在 传 统 的 Hadoop MapReduce框架上实现,Spark的优势在于以内存计算的方式大幅度降低了I/O 代价,文献[26]验证了 Spark在内存计算较传统 MapReduce计算框架在支撑分布式数据挖掘算法上的性能优势.推荐计算模块为实时在线计算任务,我们提出有序模式森林存储挖掘出的频繁模式(见4.2节),有序模式森林包含跨节点存储的一系列树型结构,在每个节点上存储由 FP-growth 局部挖掘获得的部分频繁模式.将大批量在线访问用户,即大量 Tu,广播到所有计算节点,为每个 Tu挖掘候选规则集,将候选规则挖掘转化为有序模式森林中的路径搜索问题(见4.3节).注意,推荐分值计算往往可以融入到路径搜索过程中,以进一步提升效率.最终,将每个Tu在所有节点上的推荐分值汇总排序,生成最终的推荐列表.4 技术细节4.1 组投影与分布式 FP-growth算法FP-growth算法分布式实现的核心是 Grahne和 Zhu提出的组投影方法[24],通过将 FList划分成K 组,根据每组包含的项集,在事务数据集 D 上进行投影,从而将 D 分割成互不相交的 K 个数据子集,然后分别对 K 个数 据 子 集 构 建 FP 树[21]并 利用 FP-growth算法 挖 掘.我 们 在 Spark 上 实 现 的FP-growth分布式算法也将利用组投影方法对原始数据进行逻辑分割.组投影的形式化定义如下.定义2. 组投影[24].设 FList被划分成 K 组,即 FList=β1∪β2∪…∪βK,其中βk={ik1,ik2,…,ikr},k∈{1,2,…,K},是由FList当中r个连续的项目组成,于 是 Dk={Tp∩(∪kj=1βj)|Tp∩βk≠ ,Tp∈D}表示事务数据集D 在βk上的组投影数据集.由定义2可知,Dk上的每条记录需满足两个条件:(1)至少包含βk中的一个项;(2)不包含排在βk中支持度最小项ikr之后的所有项.设有表1所示的事务数据集,按支持度降序的FList为{G,F,E,D,C,B,A}.如果将 FList分成连续的3组:β1={G,F}、β2={E,D}、β3={C,B,A},根据组投影定义,将得到如表2所示的3个事务数据子集,其 中 小 括 号 内 数 字 表 示 该 条 记 录 重 复 出现的次数.以第1分组β1={G,F}为例,{F,G}(4)表示{F,G}重复出现4次,由表1事务ID 1、5、6和8导出,值得注意地是,表1事务ID 为10 的记录{A,B,D,E}与{G,F}的交集为空,因此事务ID 10在{G,F}上不产生任何投影记录.表 1 事务数据集示例事务ID 事务 事务ID 事务1  B,C,F,G  6  C,F,G2  D,E,G  7  B,C,D,G3  B,C,D,E,G  8  E,F,G4  A,D,E,F  9  A,B,C,D,E,F5  A,C,F,G  10  A,B,D,E表 2 组投影分割数据集示例组 组投影数据{G,F} {F,G}(4),{G}(3),{F}(2){E,D} {D,E,G}(2),{D,E,F}(2),{D,G},{E,F,G},{D,E}{C,B,A}{B,C,F,G},{B,C,D,E,G},{A,D,E,F},{A,C,F,G},{C,F,G},{B,C,D,G},{A,B,C,D,E,F},{A,B,D,E}组投影过程结束后,数据事务集 D 被划分成了K 个互不相交的数据子集,K 个计算节点在得到各自的组投影数据集 Dk后,分别建立 FP 树,利用FP-growth算法,挖掘每个分组的频繁模式.需要注2122 计  算  机  学  报 2019年rowth自上而下遍历 FList递归构建 FP 树时仅需遍历βk分组中的项,而非 FList全部;(2)在 Dk上挖掘出包含βk分组中项的所有频繁模式.4.2 有序模式森林的定义分布式 FP-growth 将 在 每 个 计 算 节 点 上 挖 掘出部分频繁模式,即包含βk分组中至少一个项的频繁模式.同时,FP-growth自底向上的遍历方式使得挖掘出的每个频繁模式遵循 FList偏序关系.类似于 FP树可以对每条记录进行压缩存储一样,本节提出一种树型结构压缩存储频繁模式.由于频繁模式分布式存储于 K 个节点,这种树型结构本质上是一个森林,称为有序模式森林,定义如下.定义3. 有序模式森林(Ordered-Patterns Forest,OPF).有序模式森林由多棵多叉树组成,每个多叉树的 节 点 包 含 四 个 域:item、child_list、parent 和statinfo,分别对应项目名称、孩子节点、父亲节点与用于推荐计算的统计量.在有序模式森林中,节点的parent域保存指向父节点的指针,可以通过回溯到根节点的方式获取完整的频繁模式;statinfo 域保存根据关联规则推荐的不同机制灵活定义的统计量,参与推荐分值的计算,将在4.3节进一步阐明.算法1给出了构建有序模式森林的伪代码,其中虚根节点v0用来保存指向多叉树根节点的指针.算法1. 有序模式森林构建算法.输入:在 Dk上得到的局部频繁模式集Pk输出:虚根节点v01.创建指针f 和虚根节点v02.FOR 每一条频繁模式pj∈Pk DO3. f←v0 /*f 指针指向虚根节点v0*/4. FOR 每一个项目ijk∈pjDO5.  IF 存在f 孩子节点x 的名称等于ijkTHEN6.   f←x /*f 指针下移一层*/7.  ELSE8.   创建节点y,y.item←ijk,y.parent←f9.   将y添加到f.child_list,f←y10.  END IF11. END FOR12. 将pj的统计量保存到y.statinfo中13.END FOR14.RETURN v0以表1数据集为例,当 minisupp 为20%时,在β1、β2、β3分组对应的 3 个计算节点上共挖掘出 41条频繁模式,利用算法1可以构建出如图2所示的有序模式森林.图中的节点展示了item 和statinfo属性,statinfo存储了频繁模式的支持数.以β3分组中C 为根节点的多叉树为例,除根节点 C 外,其它每个节点都代表一条频繁模式.例如,第2层节点 E到根节点的路径为〈C,E〉,代表频繁模式{C,E},该模式的统计量存放在尾项节点E 上.图 2 有序模式森林示例OPF中每条始于根节点止于任意节点的路径对应一 条 频 繁 模 式,因 此 OPF 的 空 间 复 杂 度 为Θ(|P|),即等同于频繁模式集合的大小.Mobasher等人[10]设计频繁项集图(Frequent Itemset Graph,FIG)用于存储频繁模式,FIG 中每个节点存储一条完整的频繁模式,包含模式所有项及其支持度.OPF通过排序 以 频 繁 模 式 尾 项 代 表 一 条 模 式,相 比 于FIG极大地降低了存储空间.另外,Grahne等人[32]提出 MFI树型结构保存最大频繁模式,无法支撑所有频繁模式的存储,容易丢失关联规则推荐所需的信息.4.3 基于路径搜索的推荐计算有序模式森林完成了频繁模式在内存中的压缩存储,本节将讨论如何基于有序模式森林挖掘 Tu的候选规则集合.具体地,首先定义目标路径集合,并证明其与 Tu的候选规则集合呈现出一一对应关系.然后提出一种目标路径集合搜索算法,可在单机上完成对 Tu候选规则集合的高效挖掘.定义4. 目标路径集合.给定用户记录 Tu,令Vul=〈v0,v1,…,vl〉为 OPF上的一条路径,若Vul为目标路径集合Vu中的一条目标路径,则Vul满足如下条件:(1)v0是 OPF中的一棵多叉树的根节点,对6期 李昌盛等:关联规则推荐的高效分布式计算框架2132于任意0j<l,vj+1∈vj.child_list;(2)存在vt,vt.itemTu,并且对于任意1jl,j≠t,vj.item∈Tu.vt.item 被称为目标项目.由定义 4 可知,如果某条路径是 Tu的目 标 路径,则该条路径可以 拆分成 一条或多条目标路 径,且这些目 标 路 径 具 有 相 同 的 目 标 项 目.例 如,令〈B,C,D,E〉是 Tu的 目 标 路 径,目 标 项 目 为 C,则〈B,C,D〉和〈B,C〉是Tu的目标路径,目标项目均为C.定理1. 给定用户记录 Tu和有序模式森林,Tu的目标路径集合和候选规则集合是一一对应的.证明. 给定目标路径集合Vu和候选规则集合Ru,首先证明目标路径集合中的每条路径与候选规则集合 中 一 条 候 选 规 则 相 对 应.由 4.2 节 可 知,Tu 的任意目标路径Vul∈Vu都代表一条频繁模式pl.由于目标项目不属于 Tu,因此pl产生一条规则Rul:Al→il.根据定义 1,Rul是 Tu的 候 选 规 则,即Rul∈Ru.其次证明候选规则集合中的每条候选规则与目标路径集合中的一条目标路径相对应.对于 Ru中的任意一条候选规则Rul:Al→il,由于产生此条候选规则的频繁模式pl被保存在有序模式森林的一条路径Vul上,又 因 为 有 且 仅 有 一 个 项 目ilTu,因此根据定义 4,该条路径是 Tu的一条目标路径,即Vul∈Vu.综上,Tu的目标路径集合和候选规则集合是一一对应的. 证毕.由定理1可知,每条目标路径都对应一条候选规则,因此,搜索出 Tu所有的目标路径,就可以获得Tu所有的候选规则.算法2和3给出了搜索 Tu目标路径集合的伪代码.总体而言,目标路径搜索算法的骨架是多叉树深度优先遍历(算法2第1~10行,由堆栈S 控制),其中通过在每个节点引入color变量巧妙地区分搜索状态.具 体 地,color 变 量 取 值 为:white、gray 和black.初始化时所有节点着 white色,当路径上每次发现不包含于 Tu中的项时(算法3第1~2行),算法3第2行的 DeepenColor函数将color 变量加深一级.因此,gray 色表示第一次发现未在Tu中的项,即发现目标项目,black 色表示路径上出现第二个未包含于Tu中的项,这意味着本次路径搜索可以停止(算法2第5行).算法2. 目标路径搜索算法.输入:虚根节点v0,用户记录Tu输出:字典结构Vu用于保存Tu的目标路径集合1.创建堆栈S,S.PUSH(v0.child_list,white)2.WHILE S≠ DO3. v←S.POP()4. Vu←PathOperator(v,Tu)/*见算法3*/5. IF v.color≠black THEN6.  FORvvin v.child_list DO7.   S.PUSH(vv,v.color)8.  END FOR9. END IF10.END WHILE11.RETURN Vu算法3. PathOperator函数.输入:节点vv和用户记录Tu输出:字典结构Vu用于保存Tu的目标路径集合1.IF vv.itemTu THEN2. DeepenColor(vv.color)3. IF vv.color=gray THEN4. iq=vv.item,Update(Vu[iq])/*iq是目标项目*/5. END IF6.END IF7.IF vv.item∈Tu ANDvv.color=gray THEN8. Update(Vu[iq])/*更新iq的目标路径*/9.END IF10.RETURN Vu为更清晰地说明目标路径搜索算法过程,我们给出如图3的一个简单例子,其中 Tu={A,C,D}.首先 查 看 路 径 〈A,B,D,E〉,A 先 入 栈 并 初 始 化color为white,A 出栈,由于A∈Tu,不做任何操作.此时B 入栈,继承父节点的color变量(算法2第7行),在B 出栈时,由于BTu,B 节点的color 加深为gray,表示目标项目为B,获得第一条以B 为目标项 目 的 目 标 路 径 〈A,B〉,对 应 的 频 繁 模 式 为{A,B}.接着D 继承父节点的color 入栈,当D 出栈时,由于 D∈Tu且D 的color 值为gray,挖掘出第二条以B 为目标项目的目标路径〈A,B,D〉.E 继承父节点的color 入栈,在 E 出栈时,由于 E Tu,E的color 值被加深为black,此时该条路径上遍历结束.当遍历完整个多叉树,将得到如图3所示的每个节点的匹配状态,其中方框标注节点代表每条路径的目标项目.图 3 目标路径搜索示例2142 计  算  机  学  报 2019年

[返回]

下一篇:Permanent Scatterers in SAR Interferometry