并行关联规则挖掘综述关联规则是等人首先提出的的一个重要R.AgrawalKDD研究内容，近年来受到了数据库界的广泛关注。关联规则是寻找在同一个事件中出现的不同项的相关性，即找出事件中频繁发生的项或属性的所有子集，以及它们之间应用相互关联性。关联规则最早用于发现顾客交易数据库中不同商品间的联系，后来诸多的研究人员对关联规则的挖掘问题进行了大量的拓展和研究。他们的工作包括对原有算法的优化，如引入并行的思想，以提高算法的效率，对关联规则的应用进行扩展。关联规则挖掘具有计算量大，负载集中的特点。而I/O且许多关联规则的实际应用涉及到海量数据。在这种情况下，即使对算法进行了优化，在单处理机上使用串行算法进行挖掘所需要的时间可能也是无法接受的。其主要原因在于单处理器本身受到内存和带宽的限制。因此，必须依靠I/O高性能并行计算来有效地完成挖掘任务。关联规则的基本概念1关联规则的形式化描述如下：{}12,,...,miii令为项目集，为事物数据库，其中每I=DIT?个事物是一个项目子集，并另有一个唯一的事物标T()TX?识符。如果，则事物包含项目集。TIDTXYX?IYIX??,一个关联规则是形如的蕴涵式这里并,,YX∩YX?且ф。规则在交易数据库中的支持度=D(是交易数据库中和的交易数与所有交易数之比，support)XYYX?记为，即support()YX?{}DDTTYXT/,:∈?∪support()=YX?规则在交易数据库中的可信度指包D(confidence)含和的交易数与包含的交易数之比，记为XYXYX?，即confidence()confidence(YX?{}{}DTTXTDTTYXT∈?∈?∪,:/,:)=给定一个交易集，关联规则的挖掘问题就是产生支持D度和可信度分别大于用户给定的最小支持度和最(minsupp)小可信度的关联规则。(minconf)关联规则的发掘分为两个步骤：找出所有支持度大(1)于最小支持度的频集；从频集中产生期望的规则。(2)串行关联规则挖掘算法2目前所有并行关联规则算法都是在相应的串行算法的基础上提出的。本文首先对这些串行算法进行介绍和分析。算法2.1Apriori-like在各种关联规则挖掘算法中，最经典、最广泛使用的就是等Agrawal[2]设计的算法，其核心思想是基于频集理Apriori论的递推方法。首先产生频繁项集，然后是频繁项集，1-2-直到有某个值使频繁项集为空，算法停止。这里在第次rr-k循环中，过程先通过对两个只有一个项不同的属于的频k-1集做连接产生候选项集的集合。然后验证候选项集(k-2)-k-k-中的每个元素来决定是否将其加入频集，这里的验证过程k-是算法性能的一个瓶颈。这个方法要求多次扫描数据库，这就需要很大的负载。I/O等提出了一个高效地产生频繁集的基于杂凑Park(hash)的算法：算法。通过实验DynamicHashingandPruning(DHP)可以发现寻找频集的主要计算是在生成频繁项集上。2-DHP利用一个杂凑表在计算频繁项集时先大概计算出项集的1-2-支持度，从而减少了候选项集的数量。还采用了数据2-DHP库修剪技术，通过修剪掉那些不包含频集的事物集以减小下一次循环中数据库的大小。然而，这种修剪技术的优化并不显著。其主要原因在于只能通过过滤对数据库执行逻辑上的并行关联规则挖掘综述尚学群，沈均毅西安交通大学电信工程学院软件研究所，西安(710149)摘要：关联规则发现作为数据挖掘的重要研究内容，在许多实际领域内得到了广泛的应用。因为在挖掘过程中涉及到大量的数据和计算，高性能计算成为大规模数据挖掘应用的一个重要组成部分。该文介绍了当前并行关联规则挖掘方面的研究进展，对一些典型算法进行了分析和评价，从并行度、负载平衡以及和数据库的集成等方面展望了并行关联规则挖掘的研究方向。关键词：数据挖掘；关联规则；并行算法SurveyofParallelAssociationRuleMining，SHANGXuequnSHENJunyi(SoftwareInstitute,SchoolofTelecomEngineering,Xi'anJiaotongUniversity,Xi'an710149)AbstractDuetothehugesizeofdataandamountofcomputationinvolvedindatamining,high-performancecomputingisanessentialcomponentforanysuccessfullarge-scaledataminingapplication.Thispaperprovidesasurveyofthestudyinparallelassociationrulegeneration,reviewsandanalysessometypicalalgorithms,viewsthetrendofpa...