李挥剑（交通运输部管理干部学院信息技术应用研究所，北京１０１６０１）摘　要：多种频繁项集挖掘（ＦＩＭ）方法组合用来对大数据进行挖掘会暴露很多问题。针对暴露的问题，在ＭａｐＲｅｄｕｃｅ平台上对两种频繁项集挖掘算法进行了研究。采用两种新的大数据集挖掘方法：Ｄｉｓｔ－Ｅｃｌａｔ和ＢｉｇＦＩＭ，前者侧重于速度，利用基于ｋ－ＦＩｓ的简易负荷平衡方案来解决问题。而后者通过先验变体对ｋ－ＦＩｓ进行挖掘后将找出的频繁项集分配给映射程序，通过优化后在真正大的数据集上运行。最后通过实验证明该方法时间复杂度较低，数据量越大优势将越明显，扩展效果越好。关键词：分布式数据挖掘；频繁项集挖掘；ＭａｐＲｅｄｕｃｅ；Ｈａｄｏｏｐ；Ｅｃｌａｔ算法中图分类号：ＴＰ　３０１．６　　　文献标志码：ＡＲｅｓｅａｒｃｈ　ｏｎ　Ｆｒｅｑｕｅｎｔ　Ｉｔｅｍｓｅｔｓ　Ｍｉｎｉｎｇ　ｉｎ　Ｌａｒｇｅ　Ｄａｔａ　ＥｎｖｉｒｏｎｍｅｎｔＬＩ　Ｈｕｉ－ｊｉａｎ（Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ　Ａｐｐｌｉｃａｔｉｏｎ，Ｍｉｎｉｓｔｒｙ　ｏｆ　Ｔｒａｎｓｐｏｒｔ　ＭａｎａｇｅｍｅｎｔＣａｄｒｅ　Ｉｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ　１０１６０１，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ａ　ｖａｒｉｅｔｙ　ｏｆ　ｍｉｎｉｎｇ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔｓ（ＦＩＭ）ｃｏｍｂｉｎａｔｉｏｎ　ｍｅｔｈｏｄ　ｕｓｅｄ　ｆｏｒｍｉｎｉｎｇ　ｏｎ　ｌａｒｇｅ　ｄａｔａ　ｗｉｌｌ　ｅｘｐｏｓｅ　ｍａｎｙ　ｐｒｏｂｌｅｍｓ．Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｅｘｐｏｓｅｄ　ｐｒｏｂｌｅｍｓ　ｔｏｔｗｏ　ｋｉｎｄｓ　ｏｆ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔｓ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗｅｒｅ　ｒｅｓｅａｒｃｈｅｄ　ｉｎ　ｔｈｅ　ｐｌａｔｆｏｒｍ　ｏｆ　ＭａｐＲｅｄｕｃｅ，Ｔｈｉｓ　ｐａｐｅｒ　ａｄｏｐｔｓ　ｔｗｏ　ｋｉｎｄｓ　ｏｆ　ｂｉｇ　ｎｅｗ　ｄａｔａ　ｓｅｔ　ｍｉｎｉｎｇ　ｍｅｔｈｏｄ：Ｄｉｓｔ－Ｅｃｌａｔａｎｄ　ＢｉｇＦＩＭ．Ｔｈｅ　ｆｏｒｍｅｒ　ｆｏｃｕｓｅｓ　ｏｎ　ｓｐｅｅｄ，ｕｓｉｎｇ　ｓｉｍｐｌｅ　ｌｏａｄ　ｂａｌａｎｃｉｎｇ　ｓｃｈｅｍｅ　ｂａｓｅｄ　ｏｎｋ－ＦＩｓ　ｔｏ　ｓｏｌｖｅ　ｔｈｅ　ｐｒｏｂｌｅｍ．Ｔｈｅ　ｌａｔｔｅｒ　ｂｙ　ｍｉｎｉｎｇ　ｔｈｅ　ｋ－ＦＩｓ　ｔｈｒｏｕｇｈ　ａ　ｐｒｉｏｒｉ　ｖａｒｉａｎｔｓ　ｗｉｌｌｆｉｎｄ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍ　ｓｅｔｓ　ａｓｓｉｇｎｅｄ　ｔｏ　ｍａｐｐｉｎｇ　ｐｒｏｃｅｄｕｒｅｓ，ｔｈｒｏｕｇｈ　ｏｐｔｉｍｉｚｅｄ　ｏｐｅｒａｔｉｏｎ　ｉｎａ　ｒｅａｌ　ｌａｒｇｅ　ｄａｔａ　ｓｅｔｓ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｐｒｏｖｅ　ｔｈａｔ　ｔｈｅ　ｔｉｍｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｔｈｅ　ｍｅｔｈｏｄ　ｉｓｌｏｗ．Ｔｈｅ　ａｄｖａｎｔａｇｅ　ｗｉｌｌ　ｂｅ　ｍｏｒｅ　ｏｂｖｉｏｕｓ　ａｎｄ　ｔｈｅ　ｅｆｆｅｃｔ　ｏｆ　ｅｘｐａｎｓｉｏｎ　ｉｓ　ｂｅｔｔｅｒ，ｗｈｅｎ　ｄａｔａｑｕａｎｔｉｔｙ　ｉｓ　ｂｉｇｇｅｒ．Ｋｅｙ　ｗｏｒｄｓ：ｄｉｓｔｒｉｂｕｔｅｄ　ｄａｔａ　ｍｉｎｉｎｇ；ＦＩＭ；ＭａｐＲｅｄｕｃｅ；Ｈａｄｏｏｐ；Ｅｃｌａｔ　Ａｌｇｏｒｉｔｈｍ收稿日期：２０１４－０４－１２基金项目：交通运输部应用基础研究（主干学科）项目（２０１２－３１９－２２６－３２０）．作者简介：李挥剑（１９７６—），男，高级工程师．　　近年来，大数据的智能分析对企业和学术界变得意义重大。从一开始，频繁项集挖掘（ＦＩＭ）就是数据分析和数据挖掘不可分割的一部分。ＦＩＭ 试图根据频繁发生的一个或一系列事件来从数据库中提取信息。根据用户设定的最低频率阀值，如果某个事件频繁出现在数据里，则该事件具有研究意义。有人提出了许多技术以试图对频繁事件的数据库进行挖掘［１］。这些技术在一些代　第２期　　李挥剑：大数据环境下频繁项集挖掘的研究表性的数据集上进行了很好的实践检验，但并不适合真正的大数据［２－３］。将频繁项集应用到大型数据库中存在一定问题。首先，非常大的数据库并不适应主存储。对此，一个解决办法就是利用基于逐层宽度优先搜索的算法，如众人皆知的先验算法。在该算法下，频率计数是通过反复读取数据集来获取不同大小的候选项集而得到［４］。但处理完整一组候选项集所需的内存增速过快，导致基于先验的算法应用在单一机器上的效率非常低下；其次，已有方案通过提高最低频率阀值来达到控制输出和运行时间的目的，自动降低候选项集和频繁项集的数量。但是，推荐系统方面的研究表明频率较低的项集更具有研究意义。因此，清楚地意识到仍需要有能处理大数据的低频阀值问题的方法［５－６］。文献［７］提出了可适用在ＭａｐＲｅｄｕｃｅ上的３种先验算法。这些算法均将数据集分布到映射程序上，然后以并行方式按步骤进行计数操作。单通计数算法（ＳＰＣ）利用一个ＭａｐＲｅｄｕｃｅ阶段来表示各个候选生成和频率计数步骤。在某个数据库里对它们的频率扫描ｐ 个阶段和计数后，静态通过组合－计数算法（ＦＰＣ）开始生成ｎ个不同长度的候选项集，这里，ｎ和ｐ 都是参数。动态通过计数算法（ＤＰＣ）与ＦＰＣ类似，只是和ｐ 的值取决于各阶段所生成的候选项集的数目。并行频繁模式增长（ＰＦＰ）是大家熟知的ＦＰ增长的并行模式［８］。ＰＦＰ对数据项进行分组后将它们的条件数据库分配给各映射程序。每个映射程序创建对应的ＦＰ树后单独对其进行挖掘。文献［９］利用频繁项的出现频率来使ＰＦＰ的分组达到平衡。ＰＦＰ的分组策略不论在内存还是速度上都是效率低下。某些结点将整个数据库读取到内存就有可能了，这在大数据领域是不可行的。文献［９］提议利用单件模式来平衡快速执行所需的数据分布，但随着研究的深入发现利用单个项对搜索空间进行分区的做法还不是最有效的。文献［１０］讨论了ＭａｐＲｅｄｕｃｅ编程模型实现Ｅｃｌａｔ挖掘算法，但它没有研究数据集降低数据通信开销和数据集分块处理的方法，并且在挖掘中存在频繁集缺失的现象。文献［１１－１２］利用ＭａｐＲｅｄｕｃｅ编程模型对ＡＰＲＩＯＲＩ算法进行改进实现了ＨＡＤＯＯＰ分布式架构下数据挖掘过程。本研究提出两种新方法以并行方式在ＭａｐＲｅｄｕｃｅ框架上挖掘频繁项集频率阀值可以设置较低。第一种方法是Ｄｉｓｔ－Ｅｃｌａｔ，一种将搜索空间在映射程序之间尽可能均衡分布的纯粹Ｅｃｌａｔ方法。该技术可以挖掘出大的数据集，但面对庞大的数据时又显得无能为力。因此引入第二种方法即组合法。首先利用基于先验的方法来提取ｋ长度的频繁项集，然后当映射后的数据库适应内存时再转换成Ｅｃｌａｔ算法（ＢｉｇＦＩＭ），本文采用ＢｉｇＦＩＭ 算法利用组合方案集中于解决大数据库的挖掘问题，得到的工作负荷分布效果更佳［１３］。尽管ＭａｐＲｅｄｕｃｅ框架最初的设计理念与频繁项集挖掘问题并非完全吻合，但鉴于其在行业的实用性且应用广泛，为ＭａｐＲｅｄｕｃｅ发明高效、简便地利用数据挖掘方法的方案具有重要意义。本研究引入以下两种算法来解决ＦＩＭ 算法在ＭａｐＲｅｄｕｃｅ框架上处理大数据面临的问题：１）Ｄｉｓｔ－Ｅｃｌａｔ：执行ＭａｐＲｅｄｕｃｅ的著名的Ｅｃｌａｔ算法，在数据的某项特定编码适应内存后通过优化速度来完成；２）ＢｉｇＦＩＭ：优化后通过组合算法在ＭａｐＲｅｄｕｃｅ上来对真正的大数据进行处理，组合原理源自Ａｐｒｉｏｒｉ和Ｅｃｌａｔ算法。１　ＭａｐＲｅｄｕｃｅ框架上频繁项集的挖掘　　本研究提出了２种新的方法在并行挖掘频繁项集的ＭａｐＲｅｄｕｃｅ框架上，频率阈值设置低。第一个方法称为Ｄｉｓｔ－Ｅｃｌａｔ，是一个纯粹的分配的搜索空间之间均匀地映射Ｅｃｌａｔ方法。这一技术能够挖掘大型数据集，但处理大量数据的能力较弱。因此，引入一个混合的方法，使用一个基于Ａｐｒｉｏｒｉ的方法提取长度为ｋ 的频繁项集称之为Ｂｉｇ－ＦＩＭ 方法。１．１　Ｄｉｓｔ－Ｅｃｌａｔ第一种算法是Ｅｃｌａｔ的分布式版本，将搜索空间更均衡地在不同处理单元之间进行划分。分区算法）往往通过将事务数据库划分成大小均等的子数据库来实现对工作负荷的分配。分开对各子数据库进行挖掘，然后将结果组合。不过，应当对所有局部频繁项集进行组合计数，以便对全局不频繁项集进行修剪，但这么做代价大。首先，该方法的通信成本高，也就是有待挖掘的数据集数量巨大，而且，需要反复进行数据统计，工作量大。因此，在Ｈａｄｏｏｐ上执行这种分区技术有很大局限性。对此，可以通过挖掘阀值较２２５青岛科技大学学报（自然科学版） 第３６卷低的子数据库来减少可能遗漏的项集的数量。但出现另一个问题，事实上，每个数据库分区负责界定一个局部子数据库，其局部结构与其余的又大不同。因此，某些分区的频繁项集的计算工作量会突然增大，尽管许多这样的项集其实是局部结构，对全局来说也没有任何意义。本研究算法不需要解决上述问题，因为划分的是搜索空间而非数据空间。所以，映射程序之间不需要有额外的通信，也不必检查挖掘结果是否存在重叠。再者认为Ｅｃｌａｔ，尤其是差集型Ｅｃｌａｔ，基于内存的解决办法最适合挖掘大数据集。首先，Ｅｃｌａｔ利用深度优先法，这样即便是在寻找长频繁模式时也只有非常小部分的候选项集留在内存里。相反，宽度优先的先验算法在对ｋ＋１大小的候选项集进行计算时必须将所有ｋ－大小的频繁集合留在内存里才行。其次，利用差集的做法使得内存负荷限制在只有当前分支的原始ｔｉｄ－ｌｉｓｔ根的大小。显然：一个差集代表必须从父代的ｔｉｄ－ｌｉｓｔ里除去以获取到该结点ｔｉｄ－ｌｉｓｔ的ｔｉｄｓ。因此，一个完整的扩展分支上可以除去的ｔｉｄｓ最大也只是原始ｔｉｄ－ｌｉｓｔ的大小。Ｅｃｌａｔ操作有３步的方法。每个步骤可以分布在多个映射，从集群环境得到的最大受益。１）发现频繁项：在这一步，垂直的数据库划分成相同大小的块（片）和分配给可用的映射。每个映射器从它的碎片中提取独立频繁项。在减少的阶段，所有的频繁项不进一步处理。２）ｋ－ＦＩｓ：在这一步，ＰＫ通过规模为ｋ的频繁项集的集合产生。首先独立频繁项分布在Ｍ 映射。然后每个的映射发现的频繁ｋ－大小超项运行Ｅｃｌａｔ水平为Ｋ．最后，减速器将ＰＫ推向一个新的Ｍ 映射。３）子树挖掘：这最后一步是挖掘的前缀树从指定的ｅｃｌａｔ前缀开始。每个映射不需要信息可以独立完成子树。１．２　ＢｉｇＦＩＭ第二种方法克服了Ｄｉｓｔ－Ｅｃｌａｔ的两个固有问题：其一，对ｋ－ＦＩｓ的挖掘已经是不可能了。最坏的情况下，一个映射程序需要有完整的数据集来构建所有的２－ＦＩｓ对。考虑到大数据，即便是一个单一项，它的ｔｉｄ－ｌｉｓｔ也可能无法适应内存；其二，多数映射程序要求整个数据集在内存里才可实现对子树进行挖掘。因此，完整的数据集必须与不同的映射程序进行通信，但现有网络基础架构还没法满足这个要求。１）ｋ－ＦＩｓ涵盖：Ｂｉｇｆｉｍ产生大的ｔｉｄ表问题采用广度优先的方法生成ｋ－ＦＩｓ。可以通过调整文件计数问题来实现，即每个映射器接收数据库的一部分（文件）并报告项目／项目集。减速器将所有本地繁项集和报告合并成全局频繁项目／项目集。这些频繁项集可以分配到所有映射为广度优先搜索下一步的候选项。这些步骤可以重复ｋ次，得到ｋ－ＦＩｓ集。２）寻找潜在的扩展：在计算前缀后，然后计算可能的扩展，即获得ｔｉｄ列表（ｋ ＋１）－ＦＩｓ。减速器将从所有地方的ｔｉｄ表映射一个全局ｔｉｄ，并且从不同的映射分配完整的前缀组。３）子树挖掘：该映射器完成个人的前缀组。一个前缀组定义了一个完全符合条件的数据库存储。挖掘部分通过深度优先搜索获取数据库的频繁项集。１．３　执行细节在本研究方法里，利用映射程序可以挖掘出频繁项集，然后传达给缩减器。为降低网络流量，利用每一批模式的压缩树字符串表示法来对挖掘到的项集进行编码。基本上，定界符反映的是前缀树是自上而下还是自下而上遍历，以及是否指定了某个支点。本研究算法对事务数据集里发现的闭合项集进行超集计算。通过允许单个的映射程序只报告各自子树上的闭合集我们可以很容易做到这一点。尽管完全有可能挖掘出闭合项集的正确集合，但这里省去了后处理环节。２　实验分析与结果２．１　实验环境与数据使用２台机器组成Ｈａｄｏｏｐ的局部数据群进行实验。每台机器含有３２个因特尔处理单元，３２ＧＢ　ＲＡＭ。不过将每台机器每次运行的映射程序最多只有６个。采用ＭａｐＲｅｄｕｃｅ编程模型及Ｊａｖａ语言编程实现算法，针对实验，采用４组不同的数据集：Ａｂｓｔｒａｃｔｓ数据集、Ｔ１０Ｉ４Ｄ１００Ｋ、Ｍｕｓｈｒｏｏｍ和Ｐｕｍｓｂ数据进行频繁项集性能测试。两台机器同时在Ｕｂｕｎｔｕ　１２．０４和Ｈａｄｏｏｐ１．１．２上运行。２．２　实验评测２．２．１　负荷平衡从这２个方面来研究负荷平衡：１）工作量与２２６　第２期　　李挥剑：大数据环境下频繁项集挖掘的研究分布式前缀长度之间的关系；２）工作量与分配方案之间的关系。设ｋ前缀集合Ｐｋ ＝ ｛ｐ１，ｐ２，…，ｐｍ｝，可划分给ｎ个工作者，Ｐ１ ｋ，Ｐ２ ｋ，…，ｐｎｋ，其中Ｐｊｋ是分配给工作者ｊ 的前缀的集合，然后利用下列方法将这些前缀再分配工作者结点：循环法：Ｐｉ分配给工作者ｐ（ｉｍｏｄｎ）ｋ 。均等权重法：当Ｐｉ分配给一个工作者时，ｓｕｐｐｏｒｔ（Ｐｉ）添加到该工作者的得分里。Ｐｉ＋１分配给得分最低的工作者，分配工作受次序先后影响。区块分区法：｛Ｐ１，…，Ｐ［ｍ／ｎ］｝分配给Ｐ１ ｋ，｛Ｐ［ｍ／ｎ］＋１，…，Ｐ（２×［ｍ／ｎ］）｝分配给Ｐ２ｋ，以此类推。随机法：每个Ｐｉ分配给一个随机工作者。针对这组实验，采用４组不同的数据集：Ａｂｓｔｒａｃｔｓ数据集通过Ｄｅ　Ｂｉｅ获得［１２］、Ｔ１０Ｉ４Ｄ１００Ｋ、Ｍｕｓｈｒｏｏｍ 和Ｐｕｍｓｂ 数据集从ＦＩＭＩ数据库提［１３］。这些数据集见表１。表１　实验研究的数据集性能Ｔａｂｌｅ　１　Ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　ｄａｔａｓｅｔｓ　ｆｏｒ　ｏｕｒ　ｅｘｐｅｒｉｍｅｎｔｓ数据集项目数事务数Ａｂｓｔｒａｃｔｓ　４　９７６　８５９Ｔ１０Ｉ４Ｄ１００Ｋ ８７０　１００　０００Ｍｕｓｈｒｏｏｍ　１１９　８　１２４Ｐｕｍｓｂ　２１　１３４　４９　０４６Ｔａｇ　４５　４４６　８６３　６　２０１　２０７先对数据集进行挖掘以找出长度分别为１、２、３的前缀，然后利用上述分配方法将它们分配给１２８个工作者。根据每个工作者产生的ＦＩｓ数量来估算他所承担的工作量。根据树高度越低修剪率越高，可以准确估算一个工作者的总工作量。另外，第一步发现的ＦＩｓ的数量随着前缀长度的增大而增加，而分布式负荷量反而降低。表２是工作量最大与最小值（Ｍａｘ－Ｍｉｎ）之间的标准偏差，平均偏差和一般偏差对比结果。由于试图通过平衡工作量来缩短总运行时间，衡量平衡的一个最重要指标就是最大最小值。图１给出了通过循环法对长度分别为１、２、３的前缀进行分配后８名工作者所产生的频繁项集的数量。实验表明分配方法是相互独立的：利用较长前缀的算法会使负荷达到更好平衡。生成较长前缀要求进行额外的初始计算工作。但对大数据库图１　分区产生的频繁项集数Ｆｉｇ．１　Ｎｕｍｂｅｒ　ｏｆ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔｓ　ｇｅｎｅｒａｔｅｄ　ｂｙ　ｐａｒｔｉｔｉｏｎｓ而言，这种计算相对于整个挖掘过程可以忽略不计。表３是不同数据库里长度为１、２和３的频繁项集及这些项集的总数。例如，在Ａｂｓｔｒａｃｔｓ这组小数据集里，找出３－ＦＩｓ只占到总工作的一半；另一方面，在Ｐｕｍｓｂ这组较大数据集里，３－ＦＩｓ的数相对于总的ＦＩｓ数可以忽略不计，于是，在发现长的前缀后对余下工作进行分配还是可行的。本研究实验采用的分配方案能够将搜索空间很好地在不同计算单元之间进行分配来达到工作量的平衡。但是发现这类方案使得几乎所有结点对完整数据集形成依赖。因此，也有必要向所有结点传达完整数据。表４提供了采用均等权重分配法时结点所要求的数据率的统计数据。由表４可知，对于３－ＦＩｓ，平均率几乎都是１，说明几乎所有结２２７青岛科技大学学报（自然科学版） 第３６卷表２　前缀分配不同的方法和前缀长度Ｔａｂｌｅ　２　Ｐｒｅｆｉｘ　ａｓｓｉｇｎｍｅｎｔｓ　ｗｉｔｈ　ｄｉｆｆｅｒｅｎｔ　ｍｅｔｈｏｄｓ　ａｎｄ　ｐｒｅｆｉｘ　ｌｅｎｇｔｈｓ数据集参数　　　循环法ｐ１ ｐ２ ｐ３均等权重法ｐ１ ｐ２ ｐ３Ａｂｓｔｒａｃｔｓ 标准差１　０７１　３１１　１０７　１　０７１　３７１　１１８平均值３　０２５　２　７４４　１　６９６　３　０２５　２　７４４　１　６９６最大与最小值之差４　４８８　１　６９５　４８２　４　４８８　２　２２３　６７５Ｔ１０Ｉ４Ｄ１００Ｋ 标准差１０３　５７　３４　１０３　６４　３２平均值２１３　１４２　８５　２１３　１４２　８５最大与最小值之差６６６　３８４　１８３　６６６　４９９　１７９Ｍｕｓｈｒｏｏｍ 标准差１３　２８７　６　４４９　４　０９６　１３　２８７　６　０５２　３　５９６平均值４　４８８　４　４８２　４　４４６　４　４８８　４　４８２　４　４４６最大与最小值之差９８　３０３　３６　３４８　２３　８１４　９８　３０３　３３　４５３　２４　７１１Ｐｕｍｓｂ 标准差３　８９７　６８３　１　９５５　５０３　１　１１２　２３７　３　８９７　６８３　２　０７７　８４５　１　００３　７２４平均值１　２９６　１２１　１　２９６　１１３　１　２９６　０３７　１　２９６　１２１　１　２９６　１１３　１　２９６　０３７最大与最小值之差２１　３４２　９４３　９　８０９　６１２　６　１６７　９７０　２１　３４２　９４３　１０　０８９　４３２　４　８１５　３９１数据集参数　　　区块分区法ｐ１ ｐ２ ｐ３随机法ｐ１ ｐ２ ｐ３Ａｂｓｔｒａｃｔｓ 标准差７　２３５　４　８５０　１　８３５　２　２６０　４３２　１５０平均值３　０２５　２　７４４　１　６９６　３　０２５　２　７４４　１　６９６最大与最小值之差３５　３１４　２９　６０６　９　８４０　１１　５４０　２　７５６　６８６Ｔ１０Ｉ４Ｄ１００Ｋ 标准差１３８　１３７　６８　１３０　６２　３２平均值２１５　１４２　８７　２１３　１４０　８５最大与最小值之差７２３　６９９　４７１　１　００２　３３３　２３９Ｍｕｓｈｒｏｏｍ 标准差１３　２８７　１０　０２６　７　５１８　１３　２８７　５　７３６　３　６７９平均值４　４８８　４　４８２　４　４４６　４　４８８　４　４８２　４　４４６最大与最小值之差９８　３０３　６９　６２６　４０　４０６　９８　３０３　３０　９９１　２４　８３０Ｐｕｍｓｂ 标准差３　８９７　６８３　３　４４２　１５９　２　５９８　８２５　３　８９７　６８３　２　０６５　４４１　１　１９１　９４５平均值１　２９６　１２１　１　２９６　０３７　１　２９６　１１３　１　２９６　１２１　１　２９６　１１３　１　２９６　０３７最大与最小值之差２１　３４２　９４３　２０　０５９　５５３　１４　５０７　５６７　２１　３４２　９４３　１０　５３４　９３１　５　８２７　０８８点要求有完整的数据集。这一特性在处理大数据时是不可行的。表３　１号，２号，３号和全部的长频繁项目集的数据集Ｔａｂｌｅ　３　Ｎｕｍｂｅｒ　ｏｆ　ｔｏｔａｌ　ａｎｄ　１，２ａｎｄ　３ｌｅｎｇｔｈ　ｆｒｅｑｕｅｎｔｉｔｅｍｓｅｔｓ　ｆｏｒ　ｄａｔａｓｅｔｓ数据集最小支持度总数１－ＦＩｓ　２－ＦＩｓ　３－ＦＩｓＡｂｓｔｒａｃｔｓ　５　３８８　６３１　１　３９３　３７　３６３　１７１　５５３Ｔ１０Ｉ４Ｄ１００Ｋ １００　２７　１６９　７９７　９　６２７　１６　７４２Ｍｕｓｈｒｏｏｍ　８１２　１１　２４２　５６　６６４　２　８１６Ｐｕｍｓｂ　２４　５２３　２２　４０２　４１１　５２　９６８　９　４１６表４　不同计算单元所需的数据比Ｔａｂｌｅ　４　Ｄａｔａ　ｒａｔｉｏ　ｎｅｅｄｅｄ　ｆｏｒ　ｄｉｆｆｅｒｅｎｔ　ｃｏｍｐｕｔａｔｉｏｎ　ｕｎｉｔｓ数据集ＦＩｓ 平均值最大值最小值标准差Ａｂｓｔｒａｃｔｓ　１　０．２９　０．６６　０．２０　０．０９２　０．９１　０．９３　０．８６　０．０１３　０．９５　０．９６　０．９３　０．０１Ｐｕｍｓｂ　１　０．７８　０．９９　０．５１　０．１７２　０．９９　１．００　０．９９　０．００３　１．００　１．００　１．００　０．００Ｍｕｓｈｒｏｏｍ　１　０．３８　１．００　０．１０　０．２３２　０．８２　０．９９　０．５７　０．０９３　０．９９　１．００　０．９７　０．０１２２８　第２期　　李挥剑：大数据环境下频繁项集挖掘的研究２．２．２　执行时间针对运行时间实验，使用了ＤＡＩ－Ｌａｂｏｒ提供的一组有趣数据集。原始数据集包含了２００４—２００７之间的标签内容，有时间戳、用户、ＵＲＬ、以及一个固定的标签名。创建一组事务数据集，事务代表上述标签。该数据集的特性见表１。将Ｄｉｓｔ－Ｅｃｌａｔ和ＢｉｇＦＩＭ 方法在Ｈａｄｏｏｐ平台上的执行实验所用的运行时间与Ｍａｈｏｕｔ实验室的ＰＦＰ 执行做了比较。ＰＦＰ 被设计成一个ｔｏｐ－ｋ级的挖掘器。强迫算法将这次执行实验发现的相同数量的模式导出来以求得公平的对比效果，见图２。ｘ 轴是不同运行点的ＭｉｎＳｕｐ阀值；ｙ轴是以秒为单位的计算时间。Ｄｉｓｔ－Ｅｃｌａｔ运行最快，ＢｉｇＦＩＭ 次之。不过，ＭｉｎＳｕｐ值越低，数量次序就越慢。但ＢｉｇＦＩＭ 的目标是对庞大数据库进行挖掘。更重要的是，ＰＦＰ总是比本文算法要慢很多。而且当最小支持度降低时，发现ＰＦＰ要么需要很长时间（大约一周后停止了执行实验），要么耗尽内存。继续实验输出结果没有频繁项集。本研究关注的是挖掘速度而非数据的传输。图２　标签的不同方法定时比较Ｆｉｇ．２　Ｔｉｍｉｎｇ　ｃｏｍｐａｒｉｓｏｎ　ｆｏｒ　ｄｉｆｆｅｒｅｎｔ　ｍｅｔｈｏｄｓ　ｏｎ　ｔａｇ根据长度分别是１、２和３的种子对本研究算法的速度进行了分析。当ＭｉｎＳｕｐ为１５．５ｋ时对Ｔａｇ数据集进行挖掘，得到不同时段的结果，见图３。ｘ 轴是每次运行使用到的映射程序数；ｙ轴的单位是秒。由数据可知，利用２－和３－ＦＩｓ所需的运行次数最少，所以这两者实际上在完整运行时间方面与该数据集是相似的。图４深入展示了单个映射程序对Ｔａｇ的时间分布情况。ｘ 轴是给出了不同的ＩＤｓ的８个映射程序；ｙ 轴的单位是秒。看到１－ＦＩｓ存在明显不平衡：映射程序Ｍ８完成任务速度比Ｍ１要快１０倍。２－ＦＩｓ由于负荷图３　标签σ＝１５．５ｋ总的执行时间Ｆｉｇ．３　Ｔｏｔａｌ　ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ｏｎ　ｔａｇ　ｗｉｔｈσ ＝１５．５ｋ图４　标签σ＝１５．５ｋ映射器的执行时间Ｆｉｇ．４　Ｅｘｅｃｕｔｉｏｎ　ｔｉｍｅ　ｏｆ　ｍａｐｐｅｒｓ　ｆｏｒ　ｔａｇ　ｗｉｔｈσ ＝１５．５ｋ平衡能力更佳所以效果更理想，但偏差仍旧较大。利用３－ＦＩｓ的话，挖掘时间可得到均匀分配。另外，对最小支持度为１２ｋ的Ｐｕｍｓｂ数据集进行了实验研究。只将３－ＦＩｓ当成种子，而将映射程序的数量在１～１２０之间变化。有关统计数据见表５。表５　Ｐｕｍｓｂ数据集在３－ＦＩｓ和σ＝１２ｋ时挖掘时间统计Ｔａｂｌｅ　５　Ｍｉｎｉｎｇ　ｔｉｍｅ　ｓｔａｔｓ　Ｐｕｍｓｂ　ｗｉｔｈ　３－ＦＩｓ　ａｎｄσ ＝１２ｋ映射平均值／ｓ 最大值／ｓ 最小值／ｓ 标准差／ｓ 平均ＦＩｓ１　３６　５４６　３６　５４６　３６　５４６　０　１８　８８５５　７　７７５　８　１４７　７　０４２　４００　３　７７７１０　３　８１１　４　６１６　２　５９１　７１０　１　８８９１５　２　５１６　３　７２６　１　７３３　６１６　１　２５９２０　１　９１３　３　５３３　８７５　７５４　９４４４０　９４４　２　０１６　２７８　４５７　４７２６０　６３０　１　５７９　１４６　３４４　３１５８０　４７２　１　４２２　６９　３２６　２３６１００　３７６　２　１７７　６０　３１４　１８９１２０　３１６　１　５４２　２９　２６５　１５７由表５可知，不仅每个结点的平均运行时间大大缩短，而且最大挖掘时间也几乎直线减少。后者最终对运行时间影响最大。关于结果当映射程序达到１００个时，运行时间急剧增加。认为这２２９青岛科技大学学报（自然科学版） 第３６卷纯属巧合。事实是由于分配方案简单的缘故，有些映射程序或许会获取到许多大的种子，所以运行时间才增加。图５给出了与每个结点平均前缀相比较的运行时间降低情况。靠下方的曲线代表理想的扩展性行为。它表明当只增加了几个结点后还不生成新结点的情况下这种扩展性是有限的，因为待分配的种子数目达到了饱和。还必须指出的是在映射程序初始化过程中，数据必须分配给所有这些程序，使得总计算时间增加，这与利用更少结点的做法正好相反。图５　σ＝１２ｋ的Ｐｕｍｓｂ计时结果Ｆｉｇ．５　Ｔｉｍｉｎｇ　ｒｅｓｕｌｔｓ　Ｐｕｍｓｂ，σ ＝１２ｋ最后，在真实的数据群上对Ｔａｇ进行了上述实验，采用到亚马逊弹性ＭａｐＲｅｄｕｃｅ框架。使用的数据群大小都在２０～８０ 个映射程序之间，ｍ１．ｘ大的内存和高Ｉ／Ｏ性能事例。每个事例由只执行一个映射任务的多个内核组成。这些事例负责运行红帽企业版Ｌｉｎｕｘ和亚马逊的ＭａｐＲｅｄｕｃｅ分布程序。表６是实验统计数据。显然，比表６　３－ｆｉｓ和σ＝１５ｋ挖掘时间属性标签Ｔａｂｌｅ　６　Ｍｉｎｉｎｇ　ｔｉｍｅ　ｓｔａｔｓ　Ｔａｇ　ｗｉｔｈ　３－ＦＩｓ　ａｎｄσ＝１５ｋ映射平均值／ｓ 最大值／ｓ 最小值／ｓ 标准差／ｓ 平均ＦＩｓ２０　２５　８５１　４２　９００　１１　１６０　８　７２５　８４４４０　１３　５９６　２８　６２０　７　４３２　６　４３９　４２２６０　８　５０８　２４　２４０　１　４４０　５　１９６　２８１８０　６　５４８　２３　７６０　１　３２０　４　０６６　２１１例扩大情况不及Ｐｕｍｓｂ的那么显著。一个原因就是一些无法进行再分配的３－ＦＩｓ的子树骤然变大。对此唯一的解决办法就是增加前缀的长度。３　ＢｉｇＦＩＭ 算法和传统算法的频繁模式比较　　首先对传统的主要算法ＡＰＲＩＯＲＩ，ＰＦＰ，Ｅｃｌａｔ和ＢｉｇＦＩＭ 进行频繁模式精度进行对比，采用４ 组不同的数据集：Ａｂｓｔｒａｃｔｓ 数据集、Ｔ１０Ｉ４Ｄ１００Ｋ、Ｍｕｓｈｒｏｏｍ 和Ｐｕｍｓｂ数据进行频繁项集，Ａｂｓｔｒａｃｔｓ数据集由８５９条记录组成，Ｔ１０Ｉ４Ｄ１００Ｋ 数据集由１００　０００ 条记录组成，Ｍｕｓｈｒｏｏｍ数据集由８　１２４条记录组成，Ｐｕｍｓｂ数据集由４９　０４６条记录组成，ＡＰＲＩＯＲＩ，ＰＦＰ算法，Ｅｃｌａｔ和ＢｉｇＦＩＭ 算法最小支持度设置为１０％。所有算法的最小信任度均为５０％。验证方式采用十字交叉验证法。即将数据集划分为１０份，每次选取其中９份做为训练集，用于测试另外１份中的数据。重复该实验１０次，取平均值作为最终的结果。结果如表７所示。其中ＢｉｇＦＩＭ 算法的平均精度比传统算法精度高１０．０９％左右。表７　各算法精度比较Ｔａｂｌｅ　７　Ｃｏｍｐａｒｉｓｏｎ　ｏｆ　ａｃｃｕｒａｃｙ　ｏｆ　ｅａｃｈ　ａｌｇｏｒｉｔｈｍ数据集算法精度ＡＰＲＩＯＲＩ　ＰＦＰ　Ｅｃｌａｔ　ＢｉｇＦＩＭＡｂｓｔｒａｃｔｓ　９０．２９　９４．２１　９６．３６　９８．９９Ｔ１０Ｉ４Ｄ１００Ｋ ８１．４　８５．２　８７．３　９２．２Ｍｕｓｈｒｏｏｍ　８９．８４　９０．１０　９１．４８　９４．５８Ｐｕｍｓｂ　８４．３　８６．３３　８９．５５　９０．２５其次，根据精度评估了ＢｉｇＦＩＭ 算法的速度，对于不同的数据集，采用不同的绝对支持度作为最小支持度，结果如表８所示，其中分别列出了所有算法挖掘出的频繁项集（ＦＩｓ）数目，以及算法表８　ＢｉｇＦＩＭ 算法与传统算法的挖掘频繁项集的速度比较Ｔａｂｌｅ　８　Ｃｏｍｐａｒｅｄ　ｓｐｅｅｄ　ｗｉｔｈ　ｔｈｅ　ｔｒａｄｉｔｉｏｎａｌ　ａｌｇｏｒｉｔｈｍ　ｏｆ　ＢｉｇＦＩＭ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｍｉｎｉｎｇ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔ数据集最小支持度ＡＰＲＩＯＲＩＦＩｓ数目时间／ｓＰＦＰＦＩｓ数目时间／ｓＥｃｌａｔＦＩｓ数目时间／ｓＢｉｇＦＩＭＦＩｓ数目时间／ｓＡｂｓｔｒａｃｔｓ　１０　１　３９３　４５．２　３７　３６３　３８．９　１７１　５５３　３４．２　２７　１５５　１．４５Ｔ１０Ｉ４Ｄ１００Ｋ ６０　７９７　３４．５　９　６２７　２５．６　１６　７４２　１８．９　１８　６７５　３．４３Ｍｕｓｈｒｏｏｍ　８０　５６　５６．９８　６６４　３０．７３　２　８１６　２０．８７　１２　３８９　４．３２Ｐｕｍｓｂ　２０　５２　４３．５　９６８　３０．８　９　４１６　２４．４２　７　６８９　６．３４２３０　第２期　　李挥剑：大数据环境下频繁项集挖掘的研究的总运行时间。从表８可以看出对于稠密数据集，频繁项集和数目相差巨大，挖掘频繁项集具有较大时间优势。另外，由于频繁项集的数目更多，因此由频繁项集产生的初始类关联规则的数目也更多。显然若后续规则剪枝算法相同时，处理由频繁项集产生的初始规则更耗时。因此，对于ＭａｐＲｅｄｕｃｅ框架上稠密、大型的训练集来说，ＢｉｇＦＩＭ 算法速度更快。４　结　语本研究对两种频繁项集挖掘算法进行研究后在ＭａｐＲｅｄｕｃｅ框架上执行了实验。Ｄｉｓｔ－Ｅｃｌａｔ关注速度，利用基于ｋ－ＦＩｓ的简易负荷平衡方案来解决问题。ＢｉｇＦＩＭ 算法利用组合方案集中于解决大数据库的挖掘问题。通过先验变体对ｋ－ＦＩｓ进行挖掘后将找出的频繁项集分配给映射程序，然后再通过Ｅｃｌａｔ方法来找出频繁项集。本研究设计的新方法在处理大规模数据时所需时间少于传统的频繁项集算法，时间复杂度较低，数据量越大优势将越明显。本研究提到了平衡ｋ－ＦＩｓ负荷的好几种技术。实验结果表明３－ＦＩｓ与基础的循环分配方案相结合可产生良好的工作负荷分布效果。沿着前缀树继续，得到的工作负荷分布效果更佳，只是中间频繁项集的数量会骤然增多。如何找到能产生更好工作负荷分布结果的分配方案是下一步将要深入的话题。最后，通过在ＭａｐＲｅｄｕｃｅ框架进行实验，本文算法对大数据的挖掘表现出了较现代ＦＩＭ 方法还优越的性能。参　考　文　献［１］Ａｇｒａｗａｌ　Ｒ，Ｓｒｉｋａｎｔ　Ｒ．Ｆａｓｔ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｍｉｎｉｎｇ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ　ｉｎ　ｌａｒｇｅ　ｄａｔａｂａｓｅｓ ［Ｃ］∥ＶＬＤＢ，Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ２０ｔｈ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　ｖｅｒｙ　Ｌａｒｇｅ　Ｄａｔａ　Ｂａｓｅｓ，Ｓａｎｔｉａｇｏ　Ｃｈｉｌｅ，２００４：４８７－４９９．［２］Ｂａｙａｒｄｏ　Ｒ　Ｊ．Ｅｆｆｉｃｉｅｎｔｌｙ　ｍｉｎｉｎｇ　ｌｏｎｇ　ｐａｔｔｅｒｎｓ　ｆｒｏｍ　ｄａｔａｂａｓｅｓ　［Ｃ］∥Ｓｐｅｃｉａｌ　Ｉｎｔｅｒｅｓｔ　Ｇｒｏｕｐｏｎ　Ｍａｎａｇｅｍｅｎｔ　ｏｆ　Ｄａｔａ，ＳｅａｔｔｌｅＷａｓｈｉｎｇｔｏｎ，２００４：８５－９３．［３］Ｚａｋｉ　Ｍ，Ｐａｒｔｈａｓａｒａｔｈｙ　Ｓ，Ｏｇｉｈａｒａ　Ｍ，ｅｔ　ａｌ．Ｐａｒａｌｌｅｌ　ａｌｇｏｒｉｔｈｍｓｆｏｒ　ｄｉｓｃｏｖｅｒｙ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ［Ｃ］∥Ｄａｔａ　Ｍｉｎｉｎｇａｎｄ　Ｋｎｏｗｌｅｄｇｅ，２００７：３４３－３７３．［４］Ｍｏｂａｓｈｅｒ　Ｂ，Ｄａｉ　Ｈ，Ｌｕｏ　Ｔ，ｅｔ　ａｌ．Ｅｆｆｅｃｔｉｖｅ　ｐｅｒｓｏｎａｌｉｚａｔｉｏｎｂａｓｅｄ　ｏｎ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅ　ｄｉｓｃｏｖｅｒｙ　ｆｒｏｍ　ｗｅｂ　ｕｓａｇｅ　ｄａｔａ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　ＷｅｂＩｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｄａｔａ　Ｍａｎａｇｅｍｅｎｔ，２００１：９－１５．［５］Ｄｅａｎ　Ｊ，Ｇｈｅｍａｗａｔ　Ｓ．ＭａｐＲｅｄｕｃｅ：Ｓｉｍｐｌｉｆｉｅｄ　ｄａｔａ　ｐｒｏｃｅｓｓｉｎｇｏｎｌａｒｇｅ　ｃｌｕｓｔｅｒ［Ｃ］∥ＵＳＥＮＩＸ　Ａｓｓｏｃｉａｔｉｏｎ，６ｔｈ　Ｓｙｍｐｏｓｉｕｍｏｎ　Ｏｐｅｒａｔｉｎｇ　Ｓｙｓｔｅｍｓ　Ｄｅｓｉｇｎ　ａｎｄ　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，２００４：１２３－１２９．［６］Ａｇｒａｗａｌ　Ｒ，Ｓｈａｆｅｒ　Ｊ．Ｐａｒａｌｌｅｌ　ｍｉｎｉｎｇ　ｏｆ　ａｓｓｏｃｉａｔｉｏｎ　ｒｕｌｅｓ［Ｃ］∥ＩＥＥＥ　Ｔｒａｎｓａｔｉｏｎｓ　Ｋｎｏｗｌｅｄｇｅ　Ｄａｔａ　Ｅｎｇｉｎｅｅｒｉｎｇ，２００６：９６２－９６９．［７］Ｌｉｎ　Ｍ　Ｙ，Ｌｅｅ　Ｐ　Ｙ，Ｈｓｕｅｈ　Ｓ　Ｃ．Ａｐｒｉｏｒｉ－ｂａｓｅｄ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔ　ｍｉｎｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｏｎ　ＭａｐＲｅｄｕｃｅ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｕｂｉｑｕｉｔｏｕｓ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｍａｎａｇｅｍｅｎｔ　ａｎｄ　Ｃｏｍｕｎｃｉａｔｉｏｎ，２０１２：２６－３０．［８］Ｌｉ　Ｈ，Ｗａｎｇ　Ｙ，Ｚｈａｎｇ　Ｄ，ｅｔ　ａｌ．Ｐａｒａｌｌｅｌ　ｆｐ－ｇｒｏｗｔｈ　ｆｏｒ　ｑｕｅｒｙｒｅｃｏｍｍｅｎｄａｔｉｏｎ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００８ＡＣＭ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｒｅｃｏｍｍｅｎｄｅｒ　Ｓｙｓｔｅｍｓ，Ｎｅｗ　Ｙｏｒｋ，２００８：１０７－１１４．［９］Ｚｈｏｕ　Ｌ，Ｚｈｏｎｇ　Ｚ，Ｃｈａｎｇ　Ｊ，ｅｔ　ａｌ．Ｂａｌａｎｃｅｄｐａｒａｌｌｅｌ　ＦＰｇｒｏｗｔｈ　ｗｉｔｈ　ＭａｐＲｅｄｕｃｅ［Ｃ］∥ＩＥＥＥ　Ｙｏｕｔｈ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎＩｎｆｏｒｍａｔｉｏｎ，Ｃｏｍｐａｔｉｎｇ　ａｎｄ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２０１０：２４３－２４６．［１０］Ｍａｌｅｋ　Ｍ，Ｋａｄｉｍａ　Ｈ．Ｓｅａｒｃｈｉｎｇ　ｆｒｅｑｕｅｎｔ　ｉｔｅｍｓｅｔｓ　ｂｙ　ｃｌｕｓｔｅｒｉｎｇ　ｄａｔａ：Ｔｏｗａｒｄｓ　ａ　ｐａｒａｌｌｅｌ　ａｐｐｒｏａｃｈ　ｕｓｉｎｇ　ｍａｐｒｅｄｕｃｅ［Ｃ］∥Ｐｒｏｃｅｅｄｉｎｇ　ＷＩＳＥ　２０１１ａｎｄ　２０１２Ｗｏｒｋｓｈｏｐｓ　ＳｐｒｉｎｇｅｒＢｅｒｌｉｎ　Ｈｅｉｄｅｌｂｅｒｇ，２０１３：２５１－２５８．［１１］Ｒｉｏｎｄａｔｏ　Ｍ，ＤｅＢｒａｂａｎｔ　Ｊ　Ａ，Ｆｏｎｓｅｃａ　Ｒ，ｅｔ　ａｌ．ＰＡＲＭＡ：ａｐａｒａｌｌｅｌ　ｒａｎｄｏｍｉｚｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ａｐｐｒｏｘｉｍａｔｅ　ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ　ｍｉｎｉｎｇ　ｉｎ　ＭａｐＲｅｄｕｃｅ［Ｃ］∥Ｔｈｅ　２３ｒｄ　ＡＣＭ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　ａｎｄ　Ｋｎｏｗｌｅｄｇｅ　Ｍａｎａｇｅｍｅｎｔ，２０１２：８５－９４．［１２］Ｄｅ　Ｂｉｅ　Ｔ．Ａｎ　ｉｎｆｏｒｍａｔｉｏｎ　ｔｈｅｏｒｅｔｉｃ　ｆｒａｍｅｗｏｒｋ　ｆｏｒ　ｄａｔａ　ｍｉｎｉｎｇ［Ｃ］∥ＡＣＭ　Ｋｏｎｗｌｅｄｇｅ　Ｄｉｓｃｏｖｅｒｉｎｇ　ａｎｄ　Ｄａｔａ　Ｍｉｎｉｎｇ，２０１１：５６４－５７２．［１３］Ｗｅｔｚｋｅｒ　Ｒ，Ｚｉｍｍｅｒｍａｎｎ　Ｃ，Ｂａｕｃｋｈａｇｅ　Ｃ．Ａｎａｌｙｚｉｎｇ　ｓｏｃｉａｌｂｏｏｋｍａｒｋｉｎｇ　ｓｙｓｔｅｍｓ：Ａ　ｄｅｌｉｃｉｏｕｓ　ｃｏｏｋｂｏｏｋ［Ｃ］∥ＥＣＡＩ２００８Ｍｉｎｉｎｇ　Ｓｏｃｉａｌ　Ｄａｔａ　Ｗｏｒｋｓｈｏｐ，Ｐａｔｒａｓ，Ｇｒｅｅｃｅ，２００８：２６－３０．（责任编辑　姜丰辉）２３１