ｅｓｓｌｙ　ｆｕｓｅｓ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｍｉｎｉｎｇ　ａｎｄ　ｔｈｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｃｏｍｐｕｔｉｎｇ．Ｆｉｒｓｔｌｙ，ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｓｕｍｍａｒｉｚａｔｉｏｎ　ｏｆ　ｅｘｉｓｔｉｎｇ　ｒｕｌｅ－ｂａｓｅｄ　ａｐｐｒｏａｃｈｅｓ，ａ　ｔｒｅｅ－ｔｙｐｅ　ｓｔｒｕｃｔｕｒｅ　ｃａｌｌｅｄＯｒｄｅｒｅｄ　Ｐａｔｔｅｒｎｓ　Ｆｏｒｅｓｔ（ＯＰＦ）ｉｓ　ｄｅｓｉｇｎｅｄ　ｆｏｒ　ｔｈｅ　ｃｏｍｐａｃｔ　ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ａｎｄ　ｓｔｏｒａｇｅ　ｏｆ　ｆｒｅｑｕｅｎｔｐａｔｔｅｒｎｓ，ｗｉｔｈｏｕｔ　ｍｉｓｓｉｎｇ　ａｎｙ　ｂａｓｉｃ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｈａｔ　ｗｉｌｌ　ｂｅ　ｕｓｅｆｕｌ　ｆｏｒ　ｔｈｅ　ｓｕｂｓｅｑｕｅｎｔ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎｓｕｃｈ　ａｓ　ｓｕｐｐｏｒｔ　ｏｆ　ａ　ｐａｔｔｅｒｎ　ａｎｄ　ｉｔｓ　ｎｅｓｔｅｄ　ｐａｔｔｅｒｎｓ．Ｓｅｃｏｎｄｌｙ，ｗｅ　ｔｒａｎｓｆｏｒｍ　ｔｈｅ　ｔｗｏ－ｓｔｅｐ　ｒｕｌｅｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｔｏ　ａ　ｓｅｒｉｅｓ　ｏｆ　ｏｐｅｒａｔｉｏｎｓ　ｏｎ　ｔｈｅ　ｄａｔａ　ｓｔｒｕｃｔｕｒｅ，ａｎｄ　ｔｈｅｎ　ｄｅｖｅｌｏｐ　ｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇ　ｅｆｆｉｃｉｅｎｔ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｈｅｓｅ　ｏｐｅｒａｔｉｏｎｓ　ｗｈｉｃｈ　ａｒｅ　ｒｅｓｐｏｎｓｉｂｌｅ　ｆｏｒ　ｍｉｎｉｎｇ　ｅｌｉｇｉｂｌｅｐａｔｔｅｒｎｓ　ａｓ　ｗｅｌｌ　ａｓ　ｃｏｍｐｕｔｉｎｇ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｓｃｏｒｅｓ．Ｓｐｅｃｉｆｉｃａｌｌｙ，ｗｅ　ｔｒａｎｓｆｏｒｍ　ｔｈｅ　ｃａｎｄｉｄａｔｅｒｕｌｅｓ　ｍｉｎｉｎｇ　ｉｎｔｏ　ａ　ｐａｔｈ　ｓｅａｒｃｈｉｎｇ　ｐｒｏｂｌｅｍ　ｏｎ　ｔｈｅ　ＯＰＦ　ａｎｄ　ｔｈｕｓ　ｐｒｅｓｅｎｔ　ａ　ｐａｔｈ　ｓｅａｒｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍｒｕｎｎｉｎｇ　ｏｎ　ｔｈｅ　ｓｉｎｇｌｅ　ｍａｃｈｉｎｅ．Ｆｉｎａｌｌｙ，ｔｈｅ　ｒｅａｌ－ｔｉｍｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｉｓ　ｉｍｐｏｓｓｉｂｌｅ　ｔｏ　ｂｅ　ｃｏｍｐｌｅｔｅｄｉｎ　ａ　ｓｉｎｇｌｅ　ｍａｃｈｉｎｅ．Ｈｅｎｃｅ，ｉｎ　ｏｒｄｅｒ　ｔｏ　ｈａｎｄｌｅ　ｔｈｅ　ｅｖｅｒ－ｉｎｃｒｅａｓｉｎｇ　ｏｆ　ｏｎｌｉｎｅ　ｃｕｓｔｏｍｅｒｓ　ａｎｄ　ｐａｔｔｅｒｎｓ，ｗｅ　ｄｅｖｉｓｅ　ａ　ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｍｐｕｔｉｎｇ　ｆｒａｍｅｗｏｒｋ　ｉｎ　ｗｈｉｃｈ　ａ　ｎｏｖｅｌ　ｌｏａｄ　ｂａｌａｎｃｅｄ　ｓｔｒａｔｅｇｙ　ｆｏｒ　ｄａｔａｐａｒｔｉｔｉｏｎｉｎｇ　ｉｓ　ａｌｓｏ　ｐｒｏｐｏｓｅｄ　ｔｏ　ｒｅｄｕｃｅ　ｔｈｅ　ｒｕｎｎｉｎｇ　ｔｉｍｅ　ｏｆ　ｔｈｅ　ｔａｓｋ　ｔｈａｔ　ｆｉｎｉｓｈｅｓ　ｌａｓｔｌｙ　ａｎｄ　ｔｈｕｓｆｕｒｔｈｅｒ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｏｖｅｒａｌｌ　ｐｅｒｆｏｒｍａｎｃｅ．Ａｔ　ｌａｓｔ，ｗｅ　ｉｍｐｌｅｍｅｎｔ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｆｒａｍｅｗｏｒｋ　ａｎｄａｌｇｏｒｉｔｈｍｓ　ｏｎ　Ｓｐａｒｋ，ａ　ｗｉｄｅｌｙ　ｕｓｅｄ　ｍｅｍｏｒｙ－ｂａｓｅｄ　ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｍｐｕｔｉｎｇ　ｅｎｇｉｎｅ，ａｎｄ　ｅｖａｌｕａｔｅ　ｔｈｅｆｒａｍｅｗｏｒｋ　ａｎｄ　ａｌｇｏｒｉｔｈｍｓ　ｏｎ　ｔｈｒｅｅ　ｒｅａｌ－ｗｏｒｌｄ　ｄａｔａｓｅｔｓ，ｉ．ｅ．，Ａｃｃｉｄｅｎｔｓ，Ｗｅｂｄｏｃｓ　ａｎｄ　Ａｍａｚｏｎ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｄｅｍｏｎｓｔｒａｔｅ　ｔｈａｔ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｉｍｐｒｏｖｅｄ　ｂｙ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ＯＰＦ　ｗｉｔｈ　ｔｈｅｐａｔｈ　ｓｅａｒｃｈｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｍｏｒｅ　ｔｈａｎ　ｓｉｘ　ｔｉｍｅｓ　ｔｈａｔ　ｏｆ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ｂｒｕｔｅ　ｆｏｒｃｅ　ｍｅｔｈｏｄ．Ｍｏｒｅｏｖｅｒ，ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｌｏａｄ　ｂａｌａｎｃｅｄ　ｓｔｒａｔｅｇｙ　ｉｓ　ｅｆｆｅｃｔｉｖｅ　ｔｏ　ｆｕｒｔｈｅｒ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｔｈｅ　ｐｒｏｐｏｓｅｄｄｉｓｔｒｉｂｕｔｅｄ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｆｒａｍｅｗｏｒｋ，ｗｈｉｃｈ　ｃａｎ　ａｃｈｉｅｖｅ　ｎｅａｒｌｙ　ｌｉｎｅａｒｓｃａｌａｂｉｌｉｔｙ　ａｌｏｎｇ　ｗｉｔｈ　ｔｈｅ　ｉｎｃｒｅａｓｅ　ｏｆ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｎｏｄｅｓ．Ｋｅｙｗｏｒｄｓ　ｒｅｃｏｍｍｅｎｄｅｒ　ｓｙｓｔｅｍｓ；ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ；ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎｓ；ＦＰ－ｇｒｏｗｔｈ；Ｓｐａｒｋ；ｌｏａｄｂａｌａｎｃｉｎｇ１　引　言推荐系统在近十年来受到学术界的充分重视和深入研究，并在电子商务网站、社交平台及视频音乐网站上得到广泛应用［１－２］．各种各样的推荐模型和方法相继被提出，主要包含基于内容的方法、协同过滤模型、混合式模型、基于关联规则的方法等［３－４］．关联规则最早应用于购物篮分析，可揭示一组经常被一起购买的商品，因此自然而然地成为一种简明且可解释性极佳的推荐模型．例如，由于集合｛单反相机，单反镜头，三脚架｝中的商品经常一起被购买，当用户购买或频繁浏览“单反相机”和“单反镜头”时，就将“三脚架”推荐给用户．基于关联规则的推荐本质上利用了项目（ｉｔｅｍ）之间的关联性，其机理类似于基于项 目 的 协 同 过 滤 模 型 （Ｉｔｅｍ－ｂａｓｅｄ　Ｃｏｌｌａｂｏｒａ－ｔｉｖｅ　Ｆｉｌｔｅｒｉｎｇ）［５］，因而很多文献如［３，６］将基于关联规则的推荐归类于协同过滤模型．关联规则推荐是一类非常流行的推荐方法，大量电子商务网站将基于关联规则的方法作为其商用推荐 引 擎，比 如：ＹｏｕＴｕｂｅ 使 用 关 联 规 则 推 荐 视频［７］、淘宝和亚马逊网站上的“购买此商品的顾客也同时购买”及“经常一起购买的商品”等推荐方式也依托于关联规则构建．关联规则推荐能获得大量实际应用的原因是：（１）推荐结果可由用户操作动态触发，即用户浏览或购买记录发生变化时，经过与关联规则库的快速匹配，推荐结果可以快速更新；（２）关联规则能揭示推荐结果与浏览或已购买商品之间的共现关联，这使得推荐结果具有良好的可解释性．由于频繁模式的反单调性，一个频繁模式包含很多频繁子模式，而一个频繁模式也能导出多个关联规则，因此关联规则数量巨大、且多个规则蕴含同个目标项目的情况广泛存在．为了提升推荐准确率，大量研究工作围绕如何挑选高质量规则展开．早期的研究大多挑选置信度（ｃｏｎｆｉｄｅｎｃｅ）最高的规则来推荐［８－１０］，文献［１１］挑选最长规则，文献［１２］则提出综合利用置信度、支持度（ｓｕｐｐｏｒｔ）和长度对规则进行排序．近年来，一些新指标能进一步提升关联规则６期 李昌盛等：关联规则推荐的高效分布式计算框架２１９１ 如 校 正 置 信 度 （ａｄｊｕｓｔｅｄ　ｃｏｎｆｉ－ｄｅｎｃｅ）［１３］、分离置信度（ｄｉｓｊｕｎｃｔｉｖｅ　ｃｏｎｆｉｄｅｎｃｅ）［１４］、互信息［１５］等．还有一些研究认为需融合与目标项目相同的规则集以此来得到综合推荐分值，文献［１６－１７］将多个规则的统计量相加获得推荐分值，文献［１８］引入 Ｄ－Ｓ证据理论合成多规则的分段支持度值（ｐａｒ－ｔｉｔｉｏｎｅｄ　ｓｕｐｐｏｒｔ）作为推荐分值．上述研究工作的本质区别在于推荐分值计算方式不同，而候选规则集的匹配过程是相同的，设有规则“｛单反相机，单反镜头｝→三脚架”，若其前项｛单反相机，单反镜头｝包含用户的浏览或购买记录，但结果项｛三脚架｝却不包含，则该规则就是此用户的一条候选规则，结果项为待推荐的目标项目．在实际电子商务网站上，用户并发访问量极高，据统计，淘宝并发在线用户经常高达千万［１９］，而关联规则数量又十分庞大．如何为如此大量在线用户搜索候选规则的计算效率，成为制约关联规则推荐实际应用的瓶颈问题，尤其是当用户浏览和购买记录动态变化，推荐结果需实时生成的情形．但是，大部分已有研究主要关注关联规则推荐的准确性及关联规则的挖掘效率，而面向大规模在线用户和规则的匹配计算效率却未曾得到关注．本文试图提出面向关联规则推荐的可扩展性计算框架，能无缝兼容已有研究所提出的推荐分值计算方法，缓解关联规则推荐面临的大数据挑战．本文第２节总结相关工作；第３节正式定义问题并总体介绍面向关联规则推荐的可扩展分布式框架；第４节针对分布式框架中各个模块的展开详细介绍；第５节为实验结果和分析；第６节总结全文．２　相关工作本文将提出分布式计算框架旨在将规则挖掘与推荐计算两个阶段无缝衔接，并能支撑现有的推荐分值计算方法．因此，本节将从关联规则挖掘和基于关联规则推荐两个方面回顾相关工作．２．１　关联规则挖掘关联规则由频繁模式生成，频繁模式挖掘的核心是提升计算效率，所有挖掘方法均基于反单调性质对格空间进行剪枝，已有挖掘方法的区别仅在于格 空 间 的 遍 历 次 序 以 及 原 始 数 据 的 组 织 方 式．Ａｇｒａｗａｌ等人［２０］基于广度优先遍历提出第一个频繁模式挖掘算法 Ａｐｒｉｏｒｉ，随后 Ｈａｎ等人［２１］利用树型结构 组 织 原 始 数 据 并 基 于 深 度 优 先 遍 历 提 出ＦＰ－ｇｒｏｗｔｈ算法，Ｚａｋｉ等人［２２］利用垂直方式组织原始数据、同 样 基 于 深 度 优 先 遍 历 提 出 Ｅｃｌａｔ算 法．上述三种算法成为 频 繁模式挖 掘 领域公认 的经典方法．随着数据量的增大，频繁模式挖掘算法的可扩展性日益突出，大量研究围绕如何将 Ａｐｒｉｏｒｉ、ＦＰ－ｇｒｏｗｔｈ和 Ｅｃｌａｔ算法的分布式化展开．由于 Ａｐｒｉｏｒｉ和 Ｅｃｌａｔ算法均需要从ｋ 项集生成ｋ＋１ 项集，即本轮计算依赖于上一轮计算的结果，因此其分布式机制需要在共享内存架构中实现［２３］．而在 Ｈａｎ等人［２１］提出ＦＰ－ｇｒｏｗｔｈ时就指出可以按每个项目形成投影数据集，将原始数据集划分成独立的若干个投影数据集，从而可将 ＦＰ－ｇｒｏｗｔｈ 挖掘分解 成 若干独立 的子任务．Ｇｒａｈｎｅ等人［２４］将单项投影扩展至组投影，有效控制了独立子任务的数量，成为 ＦＰ－ｇｒｏｗｔｈ分布式实现中数据逻辑分割的核心技术．尽管 Ｓｐａｒｋ内存计算模式的出现，能极大地 提 升分布式 Ａｐｒｉｏｒｉ和Ｅｃｌａｔ算法的效率，但是 ＦＰ－ｇｒｏｗｔｈ依然是最适合分布式化的算法，这也是本文在挖掘频繁模式时选择 ＦＰ－ｇｒｏｗｔｈ作为基准方法的原因．基于组投影技术，文献［２５］在 Ｈａｄｏｏｐ平台上基于 ＭａｐＲｅｄｕｃｅ 提 出 了 ＦＰ－ｇｒｏｗｔｈ 分 布 式 版 本ＰＦＰ，但是任务间的负载均衡问题未得到考虑，而是简单地将 ＦＬｉｓｔ分 割成均等长 度 的组．ＭＬｉｂ库［２６］沿用 ＰＦＰ 的 思 路，提 供 了 Ｓｐａｒｋ 环 境 下 的 开 源ＦＰ－ｇｒｏｗｔｈ实现．Ｚｈｏｕ等人［２７］注意到负载均衡对分布式 ＦＰ－ｇｒｏｗｔｈ算法性能的重要影响，提出用项目在 ＦＬｉｓｔ中 排序位置 的 对数值衡 量 挖掘项目的 负载，缓解了均等分割法导致的负载极度不均衡问题．本文的ＦＰ－ｇｒｏｗｔｈ分布式方案依然采用经典的组投影思路［２４］，但对 ＦＬｉｓｔ的负载均衡分割方案做了进一步优化，提出投影数据集规模的估测指标，并以此作为 ＦＬｉｓｔ 的 划 分 依 据，既 汲 取 了 分 布 式 ＦＰ－ｇｒｏｗｔｈ优势，又提升了现有分布式ＦＰ－ｇｒｏｗｔｈ的性能．在实验部分将给出本文分布式 ＦＰ－ｇｒｏｗｔｈ算法与分布式 Ａｐｒｉｏｒｉ和 Ｅｃｌａｔ算法以及采取其他不同负载均衡策 略 的分布式 ＦＰ－ｇｒｏｗｔｈ 算法之 间的性能比较结果．值得一提地是，最近一些研究尝试从其他角度提升频繁模式的挖掘效率，比如 Ｃｈｏｎ等人［２８－２９］的研究利用 ＢｉｔＭａｐ技术压缩表示数据，以提升 Ａｐｒｉｏｒｉ候选项集生成和支持度计数的速度，并用 ＧＰＵ 编程２１０２ 计　　算　　机　　学　　报 ２０１９年ａｐ计算速度；Ｓｏｎｇ等人［３０］则提出增量频繁模式挖掘方法，并在 Ｈａｄｏｏｐ上将增量挖掘方法并行化．２．２　基于关联规则推荐围绕高质量关联规则选择以及推荐分值计算方法，国内外学者展开了广泛研究，以期提升基于关联规则推荐的准确率．除了以置信度作为挑选高质量关联规则的依据［８－１０］，Ｒｕｄｉｎ等人［１３］将校正置信度作为选取关联规则的依据，Ｇｈｏｓｈａｌ等人［１４－１５］相继提出分离置信度和互信息两个指标．Ｌｉ等人［１２］则提出多规则排序方法选取关联规则，依次优先考虑置信度、支持度和前项长度．针对蕴含同个目标项目的多个关联规则，很多研究提出将这些关联规则的统计量融合以获得合理的推荐分值，Ｌｉｎ等人［１６］认为待推荐项目的推荐分值应该由多条以此项目为结果的关联 规 则 的 支 持 度 和 置 信 度 乘 积 之 和 来 确 定．Ｗａｎｇ等人［１７］在计算推荐分值时，将具有相关结果的关联规则的余弦值进行求和．Ｗｉｃｋｒａｍａｒａｔｎａ等人［１８］引入 Ｄ－Ｓ证据理论合成多规则的分段支持度值作为推荐分值．此外，文献［３１］对如何选择关联规则推荐以提升冷门商品的覆盖率做了研究．已有的研究均认为制约基于关联规则的推荐在于频繁模式的挖掘阶段，例如文献［２５］利用关联规则进行查询推荐，但是仅考虑了关联规则的快速挖掘问题．因此，关联 规则挖掘出来之后的推荐计算（即匹配用户记录与关联规则集合以获得候选规则集合）效率尚未获得充分的重视，而这恰恰是在针对大规模在线用户时实现近实时推荐的关键．本文试图将关联规则挖掘和推荐计算两阶段无缝衔接，提出一个面向关联规则推荐的可 扩展分布式总体框架．同时，本文提出的计算框架具有优良的通用性，能支撑已有的不同推荐分值计算方案，这将在 ４．３节中进行讨论．３　问题描述和总体框架３．１　关联规则推荐的可扩展性问题假设Ｉ＝｛ｉ１，ｉ２，…，ｉｍ｝是 ｍ 个不同项目的集合，事务数据集 Ｄ 表示所有用户的历史浏览或购买记录．在关联分析中，包含多个项目的集合称为项集或模式，项集 Ｘ 的支持度为包含Ｘ 的事务个数占Ｄ中事务的百分比，用ｓｕｐｐ（Ｘ）表示．给定支持度阈值 ｍｉｎｉｓｕｐｐ，在数据集 Ｄ 上 挖掘获得的频繁模式集记为Ｐ＝｛ｐ１，ｐ２，…，ｐｓ｝，其中任意一条频繁模式ｐｊ＝｛ｉｊ１，ｉｊ２，…，ｉｊ｜ｐｊ｜｝，｜ｐｊ｜表示频繁模式ｐｊ中包含的项目的个数．令 Ｒｊｋ：Ａｊｋ→ｉｊｋ为频繁模式ｐｊ产生的一条关联规则，Ａｊｋ是关联规则前项，ｉｊｋ是关联规则后项，其中 Ａｊｋ＝ｐｊ／｛ｉｊｋ｝．在推荐中，规则后项仅包含一 个 项 目，因 此 频 繁 模 式ｐｊ可 以 产 生 至 多｜ｐｊ｜个能用于推荐的关联规则．令 Ｔｕ为在线用户ｕ的当前浏 览 或 购 买 记 录，Ｔｕ的 候 选 规 则 集 合 定 义如下．定义１．　候选规则集合．给定用户ｕ 当前浏览或购买的记录Ｔｕ和关联规 则集合Ｒ，用户ｕ 的候选规则集合定义为：Ｒｕ＝｛Ｒｋ：Ａｋ→ｉｋ｜ＡｋＴｕ，ｉｋＴｕ，Ｒｋ∈Ｒ｝．由定义１，候选规则（ｅｌｉｇｉｂｌｅ　ｒｕｌｅ［１２－１３］）是前项包含于 Ｔｕ、且后项不被 Ｔｕ包 含 的 规 则 集 合，这 些规则是目标 项 目 推 荐 分 值 的 计 算 依 据．尽 管 选 择高质量规则和计 算 推 荐 分 值 的 方 法 千 差 万 别 （如２．２节所述），根据 Ｔｕ搜索出候选规则集合是关联规则推荐的基础步骤，也是制约推荐效率 的 关键．对于给定的 Ｔｕ和任意一条关联规则Ｒｊ，判定当前规则是否为 Ｔｕ的候选规则最朴素的方法就是判断关联规则前项和后项的每一个项目是否包含于 Ｔｕ中，显然 这 种 匹 配 策 略 极 为 耗 时．在 最 坏 的 情 况下，挖掘一 个 用 户 所 有 候 选 规 则 的 时 间 复 杂 度 是Ｏ∑Ｒｊ∈Ｒ（Ｒｊ Ｔ ）ｕ，其中 Ｔｕ和 Ｒｊ分 别表示 Ｔｕ和Ｒｊ所包含项目的个数．当用户数和关联规则数目都很庞大时，候选规则集合搜索代价将无法忍受，严重制约着各种基于关联规则推荐的真正应用．３．２　总体框架本节给出面向关联规则推荐的可扩展分布式总体框架，如图１所示，框架主要包含两个模块：频繁模式挖掘及推荐计算．第一个模块从全量用户历史事务数据集 Ｄ 中挖掘频繁模式，通常采用定期离线计算方式，如每３小时更新频繁模式库，由于事务数据集 Ｄ 规模通常极大，我们利用 Ｓｐａｒｋ封装的分布式 ＦＰ－ｇｒｏｗｔｈ算法加速关联规则挖掘过程．分布式ＦＰ－ｇｒｏｗｔｈ算法包含两次 ＭａｐＲｅｄｕｃｅ过程［２５－２６］：首先，对 水 平 分 割 存 储 在 Ｓｐａｒｋ　ＲＤＤ（Ｒｅｓｉｌｉｅｎｔ　Ｄｉｓ－ｔｒｉｂｕｔｅｄ　Ｄａｔａｓｅｔｓ）中的各数据片进行局部计算，由Ｒｅｄｕｃｅ函 数 汇 总排 序获 得 频 繁 １－项 集 ＦＬｉｓｔ；然后，设计 ＦＬｉｓｔ负载均衡分割算法（见４．４节），获得一定数量 的 分 组，将 各 分 组 结 果 广 播 到 水 平 分 割ＲＤＤ；最后，触发第２次 ＭａｐＲｅｄｕｃｅ过程，以组投影６期 李昌盛等：关联规则推荐的高效分布式计算框架２１１２０１－１５；在线出版日期：２０１８－１２－２４．本课题得到国家自然科学基金项目（７１５７１０９３，９１６４６２０４，７１８０１１２３）资助．李昌盛，硕士，主要研究方向为数据挖掘和推荐系统．Ｅ－ｍａｉｌ：ｌｉｃｈｓｈｅ＠ｈｏｔｍａｉｌ．ｃｏｍ．伍之昂（通信作者），博士，教授，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为数据挖掘和推荐系统．Ｅ－ｍａｉｌ：ｚａｗｕｓｔｅｒ＠ｇｍａｉｌ．ｃｏｍ．张　璐，博士，讲师，主要研究方向为数据挖掘．曹　杰，博士，教授，主要研究领域为数据挖掘和商务智能．关联规则推荐的高效分布式计算框架李昌盛１）　伍之昂１），２）　张　璐１），２）　曹　杰１），２）１）（南京财经大学信息工程学院　南京　２１０００３）２）（南京财经大学江苏省电子商务重点实验室　南京　２１０００３）摘　要　关联规则推荐模型是在电子商务网站应用最广泛的商用推荐引擎之一，目前已有的工作大多聚焦于如何挑选高质量规则，以提升推荐精度．然而，关联规则数量庞大，且用户并发访问量通常极大，如何快速匹配用户浏览记录和关联规则库，为海量在线用户产生近实时推荐，成为制约关联规则推荐能否胜任真实电子商务网站推荐的重要因素．为此，本文研究关联规则推荐的效率问题，提出服务于高效关联规则推荐的分布式计算框架，将规则挖掘与推荐计算无缝衔接．具体而言，本文首先设计有序模式森林，用于压缩存储频繁模式；然后将候选规则挖掘转化为森林上的路径搜索计算，并提出高效的单机路径搜索算法；最后提出负载均衡的数据分割策略，同时降低分布式规则挖掘与推荐计算中的任务最迟完成时间．在３个公开数据集的实验结果表明基于有序模式森林的推荐计算比传统穷举匹配策略降低６倍以上时间，同时所提出的分布式计算框架可随计算节点数量达到近线性扩展．关键词　推荐系统；关联规则；频繁模式；ＦＰ－ｇｒｏｗｔｈ算法；Ｓｐａｒｋ；负载均衡中图法分类号 ＴＰ１８　　　ＤＯＩ号 １０．１１８９７／ＳＰ．Ｊ．１０１６．２０１９．０１２１８Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ｄｉｓｔｒｉｂｕｔｅｄ－Ｃｏｍｐｕｔｉｎｇ　Ｆｒａｍｅｗｏｒｋ　ｆｏｒＡｓｓｏｃｉａｔｉｏｎ－Ｒｕｌｅ－Ｂａｓｅｄ　ＲｅｃｏｍｍｅｎｄａｔｉｏｎＬＩ　Ｃｈａｎｇ－Ｓｈｅｎｇ１）　ＷＵ　Ｚｈｉ－Ａｎｇ１），２）　ＺＨＡＮＧ　Ｌｕ１），２）　ＣＡＯ　Ｊｉｅ１），２）１）（Ｓｃｈｏｏｌ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎａｎｊｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ　ａｎｄ　Ｅｃｏｎｏｍｉｃｓ，Ｎａｎｊｉｎｇ　２１０００３）２）（Ｊｉａｎｇｓｕ　Ｐｒｏｖｉｎｃｉａｌ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｅ－Ｂｕｓｉｎｅｓｓ，Ｎａｎｊｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｆｉｎａｎｃｅ　ａｎｄ　Ｅｃｏｎｏｍｉｃｓ，Ｎａｎｊｉｎｇ　２１０００３）Ａｂｓｔｒａｃｔ　 Ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｍｏｄｅｌ　ｉｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｗｉｄｅｌｙ　ｕｓｅｄｃｏｍｍｅｒｃｉａｌ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ｅｎｇｉｎｅｓ　ｉｎ　ｅ－ｃｏｍｍｅｒｃｅ　ｗｅｂｓｉｔｅｓ．Ａ　ｖａｒｉｅｔｙ　ｏｆ　ｔｅｃｈｎｉｑｕｅｓ，ｍａｉｎｌｙｉｎｃｌｕｄｉｎｇ　ｅｌｉｇｉｂｌｅ　ｒｕｌｅ　ｓｅｌｅｃｔｉｏｎ　ａｎｄ　ｍｕｌｔｉｐｌｅ　ｒｕｌｅｓ　ｃｏｍｂｉｎａｔｉｏｎ，ｈａｖｅ　ｂｅｅｎ　ｄｅｖｅｌｏｐｅｄ　ｔｏ　ｃｒｅａｔｅｅｆｆｅｃｔｉｖｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ．Ｕｎｆｏｒｔｕｎａｔｅｌｙ，ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎｈａｓ　ｂｅｅｎ　ｐａｉｄ　ｆｏｒ　ｌｉｔｔｌｅ　ａｔｔｅｎｔｉｏｎ．Ｉｎ　ｒｅａｌ－ｌｉｆｅ　ｏｎｌｉｎｅ　ｓｈｏｐｐｉｎｇ　ｓｉｔｅｓ，ｔｈｅ　ｃｏｎｃｕｒｒｅｎｃｙ　ｔｒａｆｆｉｃ　ｉｓ　ｕｓｕａｌｌｙｖｅｒｙ　ｈｉｇｈ，ｔｈａｔ　ｉｓ，ｔｈｅｒｅ　ａｒｅ　ａ　ｖａｓｔ　ａｍｏｕｎｔ　ｏｆ　ｕｓｅｒｓ　ｖｉｓｉｔｉｎｇ　ｓｉｔｅｓ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ　ａｎｄ　ｐｅｒｓｉｓｔｅｎｔｌｙａｄｄｉｎｇ　ｃｏｍｍｏｄｉｔｉｅｓ　ｉｎｔｏ　ｔｈｅｉｒ　ｂａｓｋｅｔｓ．Ｉｎ　ｔｈｅ　ｍｅａｎｗｈｉｌｅ，ｔｈｅ　ｖｏｌｕｍｅ　ｏｆ　ｆｒｅｑｕｅｎｔ　ｐａｔｔｅｒｎｓ　ａｒｅｕｓｕａｌｌｙ　ｖｅｒｙ　ｌａｒｇｅ　ａｎｄ　ｔｈｕｓ　ｔｈｅ　ｎｕｍｂｅｒ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｄｅｒｉｖｅｄ　ｆｒｏｍ　ｔｈｅｓｅ　ｐａｔｔｅｒｎｓ　ｉｓ　ｍｕｃｈｌａｒｇｅｒ　ｂｅｃａｕｓｅ　ａ　ｐａｔｔｅｒｎ　ｉｓ　ａｂｌｅ　ｔｏ　ｇｅｎｅｒａｔｅ　ｓｅｖｅｒａｌ　ｒｕｌｅｓ．Ａｓ　ｔｈｅ　ｌａｒｇｅ　ａｍｏｕｎｔ　ｏｆ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ　ａｎｄ　ｔｈｅ　ｃｏｎｃｕｒｒｅｎｔ　ａｃｃｅｓｓ　ｏｆ　ｕｓｅｒｓ，ｈｏｗ　ｔｏ　ｍａｔｃｈ　ｔｈｅ　ｂｒｏｗｓｉｎｇ　ｈｉｓｔｏｒｉｅｓ　ｏｆ　ｕｓｅｒｓ　ｗｉｔｈ　ｔｈｅｌａｒｇｅ　ｓｅｔ　ｏｆ　ｒｕｌｅｓ　ｅｆｆｉｃｉｅｎｔｌｙ　ｉｎ　ｏｒｄｅｒ　ｔｏ　ｏｆｆｅｒ　ｎｅａｒｌｙ　ｒｅａｌ－ｔｉｍｅ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎｓ　ｆｏｒ　ｍａｓｓｉｖｅ　ｏｎｌｉｎｅｕｓｅｒｓ，ｈａｓ　ｂｅｃｏｍｅ　ａ　ｖｉｔａｌ　ｃｏｎｃｅｒｎ　ｗｈｉｃｈ　ｒｅｓｔｒｉｃｔｓ　ｗｈｅｔｈｅｒ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎｍｏｄｅｌ　ｃｏｕｌｄ　ｂｅ　ｕｓｅｄ　ｏｎ　ｔｈｅ　ｒｅａｌ－ｌｉｆｅ　ｅ－ｃｏｍｍｅｒｃｅ　ｗｅｂｓｉｔｅｓ．Ｔｏ　ａｄｄｒｅｓｓ　ｔｈｉｓ　ｐｒｏｂｌｅｍ，ｔｈｉｓ　ｐａｐｅｒｆｏｃｕｓｅｓ　ｏｎ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｔｈｅ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ　ａｎｄ　ｄｅｖｅｌｏｐｓ　ａ　ｄｉｓｔｒｉｂｕｔｅｄｃｏｍｐｕｔｉｎｇ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｉｍｐｒｏｖｉｎｇ　ｔｈｅ　ｃｏｍｐｕｔａｔｉｏｎａｌ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｆ　ｒｕｌｅ　ｂａｓｅｄ　ｒｅｃｏｍｍｅｎｄａｔｉｏｎ，图 １　面向关联规则推荐的可扩展分布式总体框架方法（见 ４．１ 节）形 成 新 的 逻 辑 分 割 ＲＤＤ，并 调 用ＦＰ－ｇｒｏｗｔｈ进行局部挖掘．在分布式关联规则挖掘中，提出 ＦＬｉｓｔ负载均衡分割算法，提升传统分布式ＦＰ－ｇｒｏｗｔｈ挖掘框架的效率．图１给出的分布式框架也可 以 在 传 统 的 Ｈａｄｏｏｐ　ＭａｐＲｅｄｕｃｅ框架上实现，Ｓｐａｒｋ的优势在于以内存计算的方式大幅度降低了Ｉ／Ｏ 代价，文献［２６］验证了 Ｓｐａｒｋ在内存计算较传统 ＭａｐＲｅｄｕｃｅ计算框架在支撑分布式数据挖掘算法上的性能优势．推荐计算模块为实时在线计算任务，我们提出有序模式森林存储挖掘出的频繁模式（见４．２节），有序模式森林包含跨节点存储的一系列树型结构，在每个节点上存储由 ＦＰ－ｇｒｏｗｔｈ 局部挖掘获得的部分频繁模式．将大批量在线访问用户，即大量 Ｔｕ，广播到所有计算节点，为每个 Ｔｕ挖掘候选规则集，将候选规则挖掘转化为有序模式森林中的路径搜索问题（见４．３节）．注意，推荐分值计算往往可以融入到路径搜索过程中，以进一步提升效率．最终，将每个Ｔｕ在所有节点上的推荐分值汇总排序，生成最终的推荐列表．４　技术细节４．１　组投影与分布式 ＦＰ－ｇｒｏｗｔｈ算法ＦＰ－ｇｒｏｗｔｈ算法分布式实现的核心是 Ｇｒａｈｎｅ和 Ｚｈｕ提出的组投影方法［２４］，通过将 ＦＬｉｓｔ划分成Ｋ 组，根据每组包含的项集，在事务数据集 Ｄ 上进行投影，从而将 Ｄ 分割成互不相交的 Ｋ 个数据子集，然后分别对 Ｋ 个数 据 子 集 构 建 ＦＰ 树［２１］并 利用 ＦＰ－ｇｒｏｗｔｈ算法 挖 掘．我 们 在 Ｓｐａｒｋ 上 实 现 的ＦＰ－ｇｒｏｗｔｈ分布式算法也将利用组投影方法对原始数据进行逻辑分割．组投影的形式化定义如下．定义２．　组投影［２４］．设 ＦＬｉｓｔ被划分成 Ｋ 组，即 ＦＬｉｓｔ＝β１∪β２∪…∪βＫ，其中βｋ＝｛ｉｋ１，ｉｋ２，…，ｉｋｒ｝，ｋ∈｛１，２，…，Ｋ｝，是由ＦＬｉｓｔ当中ｒ个连续的项目组成，于 是 Ｄｋ＝｛Ｔｐ∩（∪ｋｊ＝１βｊ）｜Ｔｐ∩βｋ≠ ，Ｔｐ∈Ｄ｝表示事务数据集Ｄ 在βｋ上的组投影数据集．由定义２可知，Ｄｋ上的每条记录需满足两个条件：（１）至少包含βｋ中的一个项；（２）不包含排在βｋ中支持度最小项ｉｋｒ之后的所有项．设有表１所示的事务数据集，按支持度降序的ＦＬｉｓｔ为｛Ｇ，Ｆ，Ｅ，Ｄ，Ｃ，Ｂ，Ａ｝．如果将 ＦＬｉｓｔ分成连续的３组：β１＝｛Ｇ，Ｆ｝、β２＝｛Ｅ，Ｄ｝、β３＝｛Ｃ，Ｂ，Ａ｝，根据组投影定义，将得到如表２所示的３个事务数据子集，其 中 小 括 号 内 数 字 表 示 该 条 记 录 重 复 出现的次数．以第１分组β１＝｛Ｇ，Ｆ｝为例，｛Ｆ，Ｇ｝（４）表示｛Ｆ，Ｇ｝重复出现４次，由表１事务ＩＤ　１、５、６和８导出，值得注意地是，表１事务ＩＤ 为１０ 的记录｛Ａ，Ｂ，Ｄ，Ｅ｝与｛Ｇ，Ｆ｝的交集为空，因此事务ＩＤ　１０在｛Ｇ，Ｆ｝上不产生任何投影记录．表 １　事务数据集示例事务ＩＤ 事务 事务ＩＤ 事务１　 Ｂ，Ｃ，Ｆ，Ｇ　 ６　 Ｃ，Ｆ，Ｇ２　 Ｄ，Ｅ，Ｇ　 ７　 Ｂ，Ｃ，Ｄ，Ｇ３　 Ｂ，Ｃ，Ｄ，Ｅ，Ｇ　 ８　 Ｅ，Ｆ，Ｇ４　 Ａ，Ｄ，Ｅ，Ｆ　 ９　 Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ５　 Ａ，Ｃ，Ｆ，Ｇ　 １０　 Ａ，Ｂ，Ｄ，Ｅ表 ２　组投影分割数据集示例组 组投影数据｛Ｇ，Ｆ｝ ｛Ｆ，Ｇ｝（４），｛Ｇ｝（３），｛Ｆ｝（２）｛Ｅ，Ｄ｝ ｛Ｄ，Ｅ，Ｇ｝（２），｛Ｄ，Ｅ，Ｆ｝（２），｛Ｄ，Ｇ｝，｛Ｅ，Ｆ，Ｇ｝，｛Ｄ，Ｅ｝｛Ｃ，Ｂ，Ａ｝｛Ｂ，Ｃ，Ｆ，Ｇ｝，｛Ｂ，Ｃ，Ｄ，Ｅ，Ｇ｝，｛Ａ，Ｄ，Ｅ，Ｆ｝，｛Ａ，Ｃ，Ｆ，Ｇ｝，｛Ｃ，Ｆ，Ｇ｝，｛Ｂ，Ｃ，Ｄ，Ｇ｝，｛Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ｝，｛Ａ，Ｂ，Ｄ，Ｅ｝组投影过程结束后，数据事务集 Ｄ 被划分成了Ｋ 个互不相交的数据子集，Ｋ 个计算节点在得到各自的组投影数据集 Ｄｋ后，分别建立 ＦＰ 树，利用ＦＰ－ｇｒｏｗｔｈ算法，挖掘每个分组的频繁模式．需要注２１２２ 计　　算　　机　　学　　报 ２０１９年ｒｏｗｔｈ自上而下遍历 ＦＬｉｓｔ递归构建 ＦＰ 树时仅需遍历βｋ分组中的项，而非 ＦＬｉｓｔ全部；（２）在 Ｄｋ上挖掘出包含βｋ分组中项的所有频繁模式．４．２　有序模式森林的定义分布式 ＦＰ－ｇｒｏｗｔｈ 将 在 每 个 计 算 节 点 上 挖 掘出部分频繁模式，即包含βｋ分组中至少一个项的频繁模式．同时，ＦＰ－ｇｒｏｗｔｈ自底向上的遍历方式使得挖掘出的每个频繁模式遵循 ＦＬｉｓｔ偏序关系．类似于 ＦＰ树可以对每条记录进行压缩存储一样，本节提出一种树型结构压缩存储频繁模式．由于频繁模式分布式存储于 Ｋ 个节点，这种树型结构本质上是一个森林，称为有序模式森林，定义如下．定义３． 有序模式森林（Ｏｒｄｅｒｅｄ－Ｐａｔｔｅｒｎｓ　Ｆｏｒｅｓｔ，ＯＰＦ）．有序模式森林由多棵多叉树组成，每个多叉树的 节 点 包 含 四 个 域：ｉｔｅｍ、ｃｈｉｌｄ＿ｌｉｓｔ、ｐａｒｅｎｔ 和ｓｔａｔｉｎｆｏ，分别对应项目名称、孩子节点、父亲节点与用于推荐计算的统计量．在有序模式森林中，节点的ｐａｒｅｎｔ域保存指向父节点的指针，可以通过回溯到根节点的方式获取完整的频繁模式；ｓｔａｔｉｎｆｏ 域保存根据关联规则推荐的不同机制灵活定义的统计量，参与推荐分值的计算，将在４．３节进一步阐明．算法１给出了构建有序模式森林的伪代码，其中虚根节点ｖ０用来保存指向多叉树根节点的指针．算法１．　有序模式森林构建算法．输入：在 Ｄｋ上得到的局部频繁模式集Ｐｋ输出：虚根节点ｖ０１．创建指针ｆ 和虚根节点ｖ０２．ＦＯＲ 每一条频繁模式ｐｊ∈Ｐｋ ＤＯ３．　ｆ←ｖ０ ／＊ｆ 指针指向虚根节点ｖ０＊／４．　ＦＯＲ 每一个项目ｉｊｋ∈ｐｊＤＯ５．　　ＩＦ 存在ｆ 孩子节点ｘ 的名称等于ｉｊｋＴＨＥＮ６．　　　ｆ←ｘ ／＊ｆ 指针下移一层＊／７．　　ＥＬＳＥ８．　　　创建节点ｙ，ｙ．ｉｔｅｍ←ｉｊｋ，ｙ．ｐａｒｅｎｔ←ｆ９．　　　将ｙ添加到ｆ．ｃｈｉｌｄ＿ｌｉｓｔ，ｆ←ｙ１０．　　ＥＮＤ　ＩＦ１１．　ＥＮＤ　ＦＯＲ１２．　将ｐｊ的统计量保存到ｙ．ｓｔａｔｉｎｆｏ中１３．ＥＮＤ　ＦＯＲ１４．ＲＥＴＵＲＮ　ｖ０以表１数据集为例，当 ｍｉｎｉｓｕｐｐ 为２０％时，在β１、β２、β３分组对应的 ３ 个计算节点上共挖掘出 ４１条频繁模式，利用算法１可以构建出如图２所示的有序模式森林．图中的节点展示了ｉｔｅｍ 和ｓｔａｔｉｎｆｏ属性，ｓｔａｔｉｎｆｏ存储了频繁模式的支持数．以β３分组中Ｃ 为根节点的多叉树为例，除根节点 Ｃ 外，其它每个节点都代表一条频繁模式．例如，第２层节点 Ｅ到根节点的路径为〈Ｃ，Ｅ〉，代表频繁模式｛Ｃ，Ｅ｝，该模式的统计量存放在尾项节点Ｅ 上．图 ２　有序模式森林示例ＯＰＦ中每条始于根节点止于任意节点的路径对应一 条 频 繁 模 式，因 此 ＯＰＦ 的 空 间 复 杂 度 为Θ（｜Ｐ｜），即等同于频繁模式集合的大小．Ｍｏｂａｓｈｅｒ等人［１０］设计频繁项集图（Ｆｒｅｑｕｅｎｔ　Ｉｔｅｍｓｅｔ　Ｇｒａｐｈ，ＦＩＧ）用于存储频繁模式，ＦＩＧ 中每个节点存储一条完整的频繁模式，包含模式所有项及其支持度．ＯＰＦ通过排序 以 频 繁 模 式 尾 项 代 表 一 条 模 式，相 比 于ＦＩＧ极大地降低了存储空间．另外，Ｇｒａｈｎｅ等人［３２］提出 ＭＦＩ树型结构保存最大频繁模式，无法支撑所有频繁模式的存储，容易丢失关联规则推荐所需的信息．４．３　基于路径搜索的推荐计算有序模式森林完成了频繁模式在内存中的压缩存储，本节将讨论如何基于有序模式森林挖掘 Ｔｕ的候选规则集合．具体地，首先定义目标路径集合，并证明其与 Ｔｕ的候选规则集合呈现出一一对应关系．然后提出一种目标路径集合搜索算法，可在单机上完成对 Ｔｕ候选规则集合的高效挖掘．定义４．　目标路径集合．给定用户记录 Ｔｕ，令Ｖｕｌ＝〈ｖ０，ｖ１，…，ｖｌ〉为 ＯＰＦ上的一条路径，若Ｖｕｌ为目标路径集合Ｖｕ中的一条目标路径，则Ｖｕｌ满足如下条件：（１）ｖ０是 ＯＰＦ中的一棵多叉树的根节点，对６期 李昌盛等：关联规则推荐的高效分布式计算框架２１３２于任意０ｊ＜ｌ，ｖｊ＋１∈ｖｊ．ｃｈｉｌｄ＿ｌｉｓｔ；（２）存在ｖｔ，ｖｔ．ｉｔｅｍＴｕ，并且对于任意１ｊｌ，ｊ≠ｔ，ｖｊ．ｉｔｅｍ∈Ｔｕ．ｖｔ．ｉｔｅｍ 被称为目标项目．由定义 ４ 可知，如果某条路径是 Ｔｕ的目 标 路径，则该条路径可以 拆分成 一条或多条目标路 径，且这些目 标 路 径 具 有 相 同 的 目 标 项 目．例 如，令〈Ｂ，Ｃ，Ｄ，Ｅ〉是 Ｔｕ的 目 标 路 径，目 标 项 目 为 Ｃ，则〈Ｂ，Ｃ，Ｄ〉和〈Ｂ，Ｃ〉是Ｔｕ的目标路径，目标项目均为Ｃ．定理１．　给定用户记录 Ｔｕ和有序模式森林，Ｔｕ的目标路径集合和候选规则集合是一一对应的．证明．　给定目标路径集合Ｖｕ和候选规则集合Ｒｕ，首先证明目标路径集合中的每条路径与候选规则集合 中 一 条 候 选 规 则 相 对 应．由 ４．２ 节 可 知，Ｔｕ 的任意目标路径Ｖｕｌ∈Ｖｕ都代表一条频繁模式ｐｌ．由于目标项目不属于 Ｔｕ，因此ｐｌ产生一条规则Ｒｕｌ：Ａｌ→ｉｌ．根据定义 １，Ｒｕｌ是 Ｔｕ的 候 选 规 则，即Ｒｕｌ∈Ｒｕ．其次证明候选规则集合中的每条候选规则与目标路径集合中的一条目标路径相对应．对于 Ｒｕ中的任意一条候选规则Ｒｕｌ：Ａｌ→ｉｌ，由于产生此条候选规则的频繁模式ｐｌ被保存在有序模式森林的一条路径Ｖｕｌ上，又 因 为 有 且 仅 有 一 个 项 目ｉｌＴｕ，因此根据定义 ４，该条路径是 Ｔｕ的一条目标路径，即Ｖｕｌ∈Ｖｕ．综上，Ｔｕ的目标路径集合和候选规则集合是一一对应的． 证毕．由定理１可知，每条目标路径都对应一条候选规则，因此，搜索出 Ｔｕ所有的目标路径，就可以获得Ｔｕ所有的候选规则．算法２和３给出了搜索 Ｔｕ目标路径集合的伪代码．总体而言，目标路径搜索算法的骨架是多叉树深度优先遍历（算法２第１～１０行，由堆栈Ｓ 控制），其中通过在每个节点引入ｃｏｌｏｒ变量巧妙地区分搜索状态．具 体 地，ｃｏｌｏｒ 变 量 取 值 为：ｗｈｉｔｅ、ｇｒａｙ 和ｂｌａｃｋ．初始化时所有节点着 ｗｈｉｔｅ色，当路径上每次发现不包含于 Ｔｕ中的项时（算法３第１～２行），算法３第２行的 ＤｅｅｐｅｎＣｏｌｏｒ函数将ｃｏｌｏｒ 变量加深一级．因此，ｇｒａｙ 色表示第一次发现未在Ｔｕ中的项，即发现目标项目，ｂｌａｃｋ 色表示路径上出现第二个未包含于Ｔｕ中的项，这意味着本次路径搜索可以停止（算法２第５行）．算法２．　目标路径搜索算法．输入：虚根节点ｖ０，用户记录Ｔｕ输出：字典结构Ｖｕ用于保存Ｔｕ的目标路径集合１．创建堆栈Ｓ，Ｓ．ＰＵＳＨ（ｖ０．ｃｈｉｌｄ＿ｌｉｓｔ，ｗｈｉｔｅ）２．ＷＨＩＬＥ　Ｓ≠ ＤＯ３．　ｖ←Ｓ．ＰＯＰ（）４．　Ｖｕ←ＰａｔｈＯｐｅｒａｔｏｒ（ｖ，Ｔｕ）／＊见算法３＊／５．　ＩＦ　ｖ．ｃｏｌｏｒ≠ｂｌａｃｋ　ＴＨＥＮ６．　　ＦＯＲｖｖｉｎ　ｖ．ｃｈｉｌｄ＿ｌｉｓｔ　ＤＯ７．　　　Ｓ．ＰＵＳＨ（ｖｖ，ｖ．ｃｏｌｏｒ）８．　　ＥＮＤ　ＦＯＲ９．　ＥＮＤ　ＩＦ１０．ＥＮＤ　ＷＨＩＬＥ１１．ＲＥＴＵＲＮ　Ｖｕ算法３．　ＰａｔｈＯｐｅｒａｔｏｒ函数．输入：节点ｖｖ和用户记录Ｔｕ输出：字典结构Ｖｕ用于保存Ｔｕ的目标路径集合１．ＩＦ　ｖｖ．ｉｔｅｍＴｕ ＴＨＥＮ２． ＤｅｅｐｅｎＣｏｌｏｒ（ｖｖ．ｃｏｌｏｒ）３． ＩＦ　ｖｖ．ｃｏｌｏｒ＝ｇｒａｙ　ＴＨＥＮ４． ｉｑ＝ｖｖ．ｉｔｅｍ，Ｕｐｄａｔｅ（Ｖｕ［ｉｑ］）／＊ｉｑ是目标项目＊／５． ＥＮＤ　ＩＦ６．ＥＮＤ　ＩＦ７．ＩＦ　ｖｖ．ｉｔｅｍ∈Ｔｕ ＡＮＤｖｖ．ｃｏｌｏｒ＝ｇｒａｙ　ＴＨＥＮ８． Ｕｐｄａｔｅ（Ｖｕ［ｉｑ］）／＊更新ｉｑ的目标路径＊／９．ＥＮＤ　ＩＦ１０．ＲＥＴＵＲＮ　Ｖｕ为更清晰地说明目标路径搜索算法过程，我们给出如图３的一个简单例子，其中 Ｔｕ＝｛Ａ，Ｃ，Ｄ｝．首先 查 看 路 径 〈Ａ，Ｂ，Ｄ，Ｅ〉，Ａ 先 入 栈 并 初 始 化ｃｏｌｏｒ为ｗｈｉｔｅ，Ａ 出栈，由于Ａ∈Ｔｕ，不做任何操作．此时Ｂ 入栈，继承父节点的ｃｏｌｏｒ变量（算法２第７行），在Ｂ 出栈时，由于ＢＴｕ，Ｂ 节点的ｃｏｌｏｒ 加深为ｇｒａｙ，表示目标项目为Ｂ，获得第一条以Ｂ 为目标项 目 的 目 标 路 径 〈Ａ，Ｂ〉，对 应 的 频 繁 模 式 为｛Ａ，Ｂ｝．接着Ｄ 继承父节点的ｃｏｌｏｒ 入栈，当Ｄ 出栈时，由于 Ｄ∈Ｔｕ且Ｄ 的ｃｏｌｏｒ 值为ｇｒａｙ，挖掘出第二条以Ｂ 为目标项目的目标路径〈Ａ，Ｂ，Ｄ〉．Ｅ 继承父节点的ｃｏｌｏｒ 入栈，在 Ｅ 出栈时，由于 Ｅ Ｔｕ，Ｅ的ｃｏｌｏｒ 值被加深为ｂｌａｃｋ，此时该条路径上遍历结束．当遍历完整个多叉树，将得到如图３所示的每个节点的匹配状态，其中方框标注节点代表每条路径的目标项目．图 ３　目标路径搜索示例２１４２ 计　　算　　机　　学　　报 ２０１９年