unknowing
数据挖掘中常用的关联规则挖掘算法
摘 要：文中首先介绍了数据挖掘中关联规则的经典算法—Apriori算法。再从宽度、深度、划分、采样、增量式更新等几个角度对关联规则挖掘进行了分类讨论。然后运用文献查询和比较分析的方法对常见的关联规则挖掘算法进行了概述，主要包括FP-growth算法、DHP算法、Partition算法、FUP算法、CD等算法。最后对关联规则挖掘的发展远景进行了展望。 关键词：数据挖掘；关联规则；频繁项集；挖掘算法南京翻译
Common Algorithms of Association Rules Mining in Data Mining
Computer Science and Communication Engineering, Pattern Recognition and Intelligent Systems
Abstract: This paper first introduces the data mining association rules in the classical algorithm-Apriori algorithm. Again from the depth, width and division, sampling, incremental updating aspects of association rules mining are classified discussions. Then u the literature arch and the method of comparison to the common algorithm for mining associ
ation rules are summarized, including the FP-growth algorithm, Partition algorithm, the algorithm, DHP, FUP algorithm, CD. The association rules mining development prospect is discusd.
Key words: Data mining; Association rule; Frequent itemts; Mining algorithm
1引言
airpollution数据挖掘(Data Mining)，又称数据库中的知识发现(Knowledge Discovery In Databa)，是从大量的、不完整的、有噪声的、模糊的、随机的大型数据中提取隐含在其中的、人们事先未知的、具有潜在价值的信息和知识的过程[1]。简单的说，数据挖掘就是从大量数据中提取或“挖掘”出人们有用的知识。面对当前“海量数据，微量信息”的现状，数据挖掘的重要研究分支—关联规则，作为一种高级和智能的数据处理和分析技术的研究正方兴未艾。 通过关联规则挖掘，可以得到隐含于海量数据中具有潜在价值的有用信息。关联规则的目标是以有效的方式提取最有趣的模式。 关联规则挖掘是数据挖掘领域一个重要的研究课题。关联规则一般可分为布尔型关联规则和多值属性关联规则。Agrawal于1993年提出布尔型关联规则问题，之后提出了经典的Apriori和Apriori TID算法[2]。多值属
性分为类别属性和数值属性，很多算法在解决多值属性关联规则挖掘时，都是将连续数值离散化，得到相应的模糊文字描述，然后其处理方法类似于布尔型关联规则挖掘。传统的关联挖掘算法 认为数据库中各个项的重要程度相同，然而在现实中各个项的重要性往往不同。例如，决策者往往会优先考虑利润较高的项目，而忽略利润较低的项目。另外，时间的推移以及消费习惯的改变也会对关联规则产生影响，时间间隔较短的事务所产生的关联规则尽管支持度不太高，却能很好地反映新的消费趋势，因此，在实际分析数据时，利用加权关联规则是有意义的。文献[2]提出布尔型属性加权关联规则的概念，并给出2种加权关联规则的挖掘算法：MINWAL(O)算法和MINWAL(W)算法，但前者的加权支持度可能大干I，后者的加权支持度不一定支持含有属性数多的加权关联规则，也不能很好地突出重点项目，文献[3]采用权重集归一化的思想对这2种算法做了改进。文献[4]提出了一种基于概率的加权关联规则算法。文献[5]提出了基于Apriori算法的水平加权关联规则挖掘方法，较好地突出了权值的作用。
2 关联规则的基本概念
设集合I={i1，i2，…，im}，其中,ik(k=1，2，…，m)表示项。如果X∈I，集合X被称为项
集。当|X|=k，则X被称为k-项集。事务二元组T=(tid，X)，tid是事务唯一的标识，符称为事务号。数据集D={t1，-t2，t3，…，tn}是由t1，t2，t3，…，tn事务组成的集合。 关联规则可以描述为：形如A => B的蕴涵式，其中A∈I，B∈I，并且A∩B=￠。项集X的支持度s是D中包含X的事务数占所有事务数的百分比，记为 。项集x的置信度c是D中同时包 含英文报纸X∪Y的事务数占包含X的所有事务数的百分比，记为c(X)=P(X|Y)=。至于最小支持度“will是什么意思minsup和最小置 信度重金兼紫minconf都是由用户所给定，如果项集X的sup(X)≥minsup，那么项集X被称为频繁项集，其中生成的关联规则中所有支持度和置信度都不小于minsup和minconf的被称为强关联规则。 关联规则的支持度表示在整个数据库中的重要性，而置信度则反映其可靠程度。只有支持度和置信度均为较高的关联规则才是用户感兴趣的、有用的关联规则。
3 关联规则的种类
根据不同的标准，关联规则可以用很多不同的方法分成若干类型[2]，根据挖掘模式的完全性可以把关联规则分为闭频繁项集、挖掘频繁项集的完全性、极大频繁项集和被约束的频繁项集。根据规则涉及的数据的层和维可以把关联规则分为单层关联规则、多层关联规则、单维关联规则和多维关联规则的挖掘。根据规则所处理的值的类型可以把关联规则分
为挖掘布尔 型关联规则和量化关联规则。根据所挖掘的规则类型可以把关联规则分为关联规则和相关规则挖掘。根据所挖掘的模式类型可以把关联规则分为频繁项集挖掘、序列模式挖掘、结构模式挖掘等。根据所挖掘的约束类型可以把关联规则分为知识类型约束、数据约束、维／层约束、兴趣度约束、规则约束。
4 关联规则挖掘算法
4.1 经典的关联规则挖掘算法
1994年Agrawal提出的Apriori算法是挖掘完全频繁项集中最具有影响力的算法。算法有两个关键的步骤：一是发现所有的频繁项集；二是生成强关联规则。 发现频繁项集是关联规则挖掘中的关键步骤。在Apriori算法中还利用了“频繁项集的子集是频繁项集，非频繁项集的超集是非频繁项集”这一个性质有效的对频繁项集进行修剪。 算法核心思想： 给定一个数据库，第一次扫描数据库，搜索出所有支持度大于等于最小支持度的项集组成频繁1-项集即为L1，由Ll连接得到候选1-项集Cl； 第二次扫描数据库，搜索出Cl中所有支持度大于等于最小支持度的项集组成频繁2-项集即为L2，由L2连接得到候选2-项集C2；ball 同理第k次扫描数据库，搜索出Ck-1中所有支持度大于等于最小支持度的项集组成频繁k-奥巴马上海演讲项集即为L
k，由Lk连接得到候选k-项集Ck，直到没有新的候选集产生为止。 Apriori算法需扫描数据库的次数等于最大频繁项集的项数。Apriori算法有两个致命的性能瓶颈：产生的候选集过大(尤其是2-项集)，算法必须耗费大量的时间处理候选项集；多次扫描数据库，需要很大的l/0负载，在时间、空间上都需要付出很大的代价。
4.2 常用的关联规则挖掘算法
目前常见的关联规则挖掘算法大致可分为宽度优先算法、深度优先算法、数据集划分算法、采样算法、增量式更新算法等。下面对一些常用算法做简单的介绍。
4.2.1 宽度优先算法
宽度优先算法又称为分层算法，包括由Agrawal等人提出的Apriori、AprioriTid[7]和AprioriHybrid[8]算法，Park等人提出的DHP算法[9]等等。 Apriori算法也是宽度优先算法，AprioriTid算法是在Apriori算法的基础上演化而来的。该算法第一趟扫描数据库时采用Apriori算法，当再次扫描时不再是扫描整个数据库，而只是扫描上次生成的候选项集，扫描的同时还会计算出频繁项集的支持度，以减少扫描数据库的时间来提高算法的效率。Apr
iori算法和AprioriTid算法的融合产生了AprioriHybird算法，初始扫描数据库时使用Apriori算法，当生成的候选项集大小可以存放到内存中进行处理时再转向AprioriTid算法，直到找出所有的频繁项集。DHP算法采用哈希(Hash)表技术对数据集和候选项集进行修剪来降低算法的时间和空间的开销。它利用哈希表在计算(k-1)-项集时先粗略计算出k-项集的支持度，排除无意义的候选k-项集来减少候选k-项集的数量，尤其是 对候选2 -项集的数量控制特别突出。总的来说，宽度优先算法的不足之处还是在于需要生成大量候选项集，需要多次扫描数据库。
4.2.2 深度优先算法
深度优先算法中常见的算法有FP-growth算法[10]、0P算法[11]、手续费英语TreeProjection算法[12]等。FP-growth算法是深度优先算法中最新最高效的且从本质上不同于Apriori算法的经典算法。基本思想是：采取分而治之的策略，首先在保留项集关联信息的前提下，将数据库压缩到一棵频繁模式树(FP-tree)中；然后将这种压缩后的FP-tree分成一些条件数据库并分别挖掘每个数据库。在算法中有两个关键步骤：一是生成频繁模式树FP-tree；二是在频繁模式树FP-tree上挖掘频繁项集。 与Apriori算法相比，FP-growth算法具有以下优点：FP-gro
wth算法只需扫描数据库两次，避免多次扫描数据库；不需要产生庞大的候选项集，在挖掘过程中大大减少了搜索空间，在时间效率、空间效率上都有一个量级的提高。但它的应用难点在于处理很大的且很稀疏的数据库时，在挖掘处理、递归运算中都需要相当大的空间。
4.2.3 数据集划分算法
数据集划分算法包括SavaSere等人提出的Partition算法[13]，Brin等人提出的DIC算法[13]等。Partition宋体英文算法是从逻辑上将整个数据库划分成几个相互独立的可以存放在内存中进行处理的数据块，节省访问外存时I/O的开销。它单独考虑每个逻辑块生成相应的频集，然后利用“频繁项集至少在一个分区中是频繁的”这一性质把所有逻辑块生成的所有频集合并生成所有可能的全局候选项集，最后再次扫描数据库计算项集的支持度进行全局计数。整个过程只需对数据库进行两次扫描，但是产生的候选项集数量比较大。DIC算法同样采取数据库划分的思想，将数据库划分为若干个分区并在每个分区的开始部分做标记，在扫描数据库过程中可以在各个分区的标记点添加候选项集，在计算项集时并行计算可能为频集的支持度。算法扫描数据库的次数基本上是少于最大频集的项数。在数据块划分恰到好处
时只需通过两次扫描数据库就能找出所有的频繁项集。 但是该类型的算法具有高度的并行性，只需扫描两次数据库，大大减少了I/O操作从而提高了算法效率。在基于划分的算法中主要瓶颈是算法执行的时间，同时产生的频繁项集的精度也不是很高。
