对于基于搜索方法的关联规则发现算法的研究

摘要：挖掘关联规则是数据挖掘领域的一个重要研究方向,本文首先介绍了一种基于层次的Apriori算法和一种基于搜索算法的QAIS算法，通过二者的比较，指出了QAIS算法中的优点以及不足之处。然后有针对性的提出了解决的方案，形成了ImprovedQAIS算法。

关键词：关联规则；数据挖掘；基于搜索；算法

中图分类号：TP311文献标识码：A 文章编号：1009-3044(2008)12-20000-00

Research Of Association Rule Finding Based on Searching Algorithm

LIU Jin-zhong

(Hunan Medical secondary specialized schools,Changsha 410014,China)

Abstract:Mining association rules are major aspect of data mining Domain. This paper first introduces Apriori algorithm, and then show a mining association rule algorithm based on searching algorithm, which can be called NewQAIS. By comparing to Apriori algorithm, we can realize that NewQAIS algorithm is better in some aspects. The paper also points out some drawbacks of NewQAIS algorithm. On the basis of the comprehension, a method to solve the above drawbacks is pointed out, which leads to the ImprovedQAIS algorithm.

Key words:data mining; association rules; searching algorithm

1 数据挖掘中的关联规则发现

随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数据急剧的增加，可是目前用于对这些数据进行分析处理的工具却很少。数据挖掘（DM，Data Mining）是近年来随着数据库和人工智能技术的发展而出现的一种全新信息技术，它从大量的、不完全的、有噪声的、模糊的、随机的数据中，提取隐含在其中的、新颖的、潜在有用的信息和知识的过程，也就是从数据资料中发掘信息或知识（KDD，Knowledge Discover in Database）。数据挖掘首先应该依据对问题的定义明确挖掘的任务或目的，然后决定使用什么样的算法。常见的挖掘任务有分类或预测模型发现、数据总结、聚类、关联规则发现、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等。

关联规则发现是在数据库中寻找数据对象间的关联模式。挖掘关联规则需要根据最小只吃度找出数据集中所有的频繁集，然后根据频繁项目集和最小置信度产生关联规则。

2 基于层次的Apriori算法和基于搜索的QAIS算法

2.1 典型层次发现算法――Apriori先验算法

现有的多数挖掘关联规则的算法均是以Apriori先验算法为基础，Apriori算法是一个基于两阶段频繁集的方法，将关联规则挖掘算法分解为两个子问题：（1）求出数据库D 中满足最小支持度minsup的所有频繁项目集，记为Lk；（2）利用频繁集生成满足最小可信度minconf的所有关联规则。其中第一个问题是算法的关键，Apriori算法用基于频繁集理论的递推方法来解决这一问题。寻找频繁集是规则发现的核心部分，该算法使用一种称作逐层搜索的迭代方法，频繁k项集Lk用于搜索频繁(k+1)项集Lk+1，寻找每一个Lk需要扫描一次数据库。

为了尽可能地减少项集的组合和扫描次数，以提高频繁项集逐层产生的效率，发现算法在产生频繁项集时使用了Apriori性质，即：频繁项集的所有非空子集也都是频繁集的。可以解释为：任何频繁集的子集都是频繁集；任何非频繁集的包含（超集）都是非频繁集。Apriori性质是基于这样的事实：由定义知，如果项集I不满足最小支持度minsup，则I不是频繁集。如果一个项A添加到I中，则结果项集不可能比I更频繁，因此I∪A也不是频繁集，即P(I∪A)＜minsup。

Apriori 算法出现较早，它强调的是如何高效地发现初始数据库中的频繁集，而关联规则的更新可以说不在它的考虑范围之内。但从规则更新的角度来看，当定义频繁集的条件稍做变动，在这被丢弃的项集中就有可能是在新频繁集里。正因为如此，以Apriori算法为基础的关联规则更新算法诸如FUP 算法、IUA 算法都较复杂。Apriori 算法的另一个很显著的特点是在寻找频繁集的过程中不可避免的生成了许多的中间候选项集。中间候选项集的数目即便是对同一个初始数据库也不是一个常量，它依赖于给定的最小支持度。一般来说，最小支持度越小，中间候选项集的数目的也就越多，在算法执行过程中占用的空间也就越多。

2.2 快速关联规则挖掘算法――QAIS先验算法

QAIS算法通过对事务数据库DB 中的每一条事务求出所有的项目子集，保存在项目集聚集之中，并记录每一个项目集的出现的次数（支持度），然后遍历整合项集过滤出大于给定最小支持度的项目集，形成频繁集，最后根据给定的置信度生成优化了的关联规则。

QAIS算法只要对数据库进行一次的扫描，即可建立一个具有支持度计数整合项集(AggItemSet)，整理后的数据集可以取代原始的数据库，减少了反复搜寻数据库的时间，由于频繁项目集的合并与分解都在这个整合项目集中就可完成，所以可以显著降低找出所有频繁项目集所需要的时间。QAIS 算法可用于初始数据库关联规则的挖掘。

QAIS 算法对初始数据库中的信息进行某种整合，这种整合不仅是想满足寻找初始数据库中的频繁集，它还更有意识的为以后的关联规则的更新作铺垫。当寻找频繁集所需要的最小支持度发生变化时，对QAIS 算法来说，它只要重新扫描一遍（或不用一遍）整合项集就可以了；而对Apriori 算法来说，要么重新运行Apriori 算法，要么运行以Apriori 算法为基础的关联规则更新算法，二者无论那一个，都要比扫描一遍QAIS 算法早已形成的整合项集要复杂的多。

事实上，即便是对初始频繁集的形成，整合项集也有它有利的一方面。一般来说，为了发现事先未知的关联规则，用户必然需要通过对最小支持度和最小可信度这两个阈值的不断调整来逐步聚焦到那些真正令人感兴趣的关联规则上去，这将是一个动态的交互过程。而QAIS 算法可以说满足了这种对时间要求较高的交互过程，从这一方面来说，Apriori 算法对这种交互过程的适应性是比较差的。

而且，QAIS算法不存在系统要给算法分配多少内存空间的不确定性。对于QAIS算法用到的两个数据结构来说，任一给定的初始数据库，事务的所有非空子集SubItemSet与整合项集 占用的空间都是可以预见的。若每一个内存单元都能存储一个项集，而数据库中有n 个交易，数据库中交易所能形成的SubItemSet占用空间的大小是??2x-n，（x 为交易的长度），那么 所能占用的最大空间是n×（??2x -n）。