论文部分内容阅读
关联规则挖掘是数据挖掘领域中的一个重要分支,其任务是发现所有满足最小支持度和最小置信度阈值的强规则。近年来,其在市场营销、决策辅助等领域广泛而成功的应用,使其成为数据挖掘研究中的一个热点。频繁模式挖掘是关联规则挖掘的关键,也是关联规则挖掘研究的重点。在关联规则挖掘中,常用的频繁模式有频繁项集、频繁闭项集以及最大频繁项集。最初,关联规则是通过挖掘频繁项集来产生的,然而频繁项集的规模往往较大,这严重的影响了关联规则的挖掘效率。由于频繁闭项集的数量远小于频繁项集,而且通过频繁闭项集能得到所有的频繁项集,通过频繁闭项集产生的关联规则能得到所有的规则,因此当前通常的做法是使用频繁闭项集代替频繁项集来挖掘关联规则。然而,为了加快关联规则产生的速度,仅仅有频繁闭项集是不够的,还需要将频繁闭项集之间的包含关系用某种有效的数据结构保存起来,比如频繁闭项集格。通过格,一个项集能够容易的找到它所有的子集和超集,从而加快规则产生的速度。并行化是提高问题解决效率的有效方法。随着数据集规模的不断增大,为了更有效的解决关联规则挖掘的实际问题,并行技术被引入其中,并得到了广泛而深入的研究。然而现有的关联规则并行挖掘算法,几乎都是针对频繁项集的,而对于频繁闭项集的并行挖掘算法几乎没有。本文对关联规则挖掘进行了一般性的论述;分析了国内外研究的现状;研究了典型的频繁项集、频繁闭项集挖掘算法以及频繁项集并行挖掘算法的算法思想和优缺点;提出了并行挖掘频繁闭项集的有效算法P-CHARM,以及并行挖掘频繁闭项集并建格的有效算法P-Q-CFIsL。P-CHARM有两个版本,P-CHARM I和P-CHARM II。其中,P-CHARM II是P-CHARM I的改进。P-Q-CFIsL是Q-CFIsL的并行化,Q-CFIsL是本课题组提出的快速挖掘频繁闭项集并建格的有效算法。本文通过实验证明了P-CHARM和P-Q-CFIsL的有效性。