论文部分内容阅读
摘要：挖掘关联规则是数据挖掘领域的一个重要研究方向,本文首先介绍了一种基于层次的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）。
3 QAIS算法的改进算法——ImprovedQAIS算法
3.1 QAIS算法存在的问题
QAIS 算法的关键是只需要对初始数据库一次扫描就要生成所有的频繁项目集的最大超集。对每一个包含n个项目的交易都将产生2n-1个非空项目集。由这些交易形成的项集的并集组成了这个最大超集。而一般要挖掘的初始数据库都有成千上万个交易，所需计算和存储的候选项目集的数量往往非常庞大，这样，如果不对该算法进行一定的改进，它只能适应于交易数量较少并且交易本身的长度较短的数据库关联规则挖掘。
3.2 改进的QAIS算法——ImprovedQAIS算法
针对上述问题，必须对原程序做一些变化。首先，可以将SubItemSet这种数据结构弃之不用。然后，为适应新算法，对 的数据结构做一个改动：由于知道最长的交易为max_T，所以首先可先建立一个长度为max_T的一维数组。其次，分别建立max_T个单链表，分别用于存储长度是从1 到max_T的项集，该链表的每个节点将有三个域：一个存项集，一个存该项集的支持数，一个存指向下一个节点的指针。最后，这max_T个链表的首地址分别存储在先前建立的一维数组中，存储时按照其指向的项集的长短来进行，即：数组的单元1 存指向长度为1 的链表首地址，单元2 存指向长度为2 的链表首地址，依次类推。第三，设立一个固定的存储单元，允许项目作为集合元素存放入该单元。
3.3 新旧QAIS算法的比较
新旧QAIS 算法的最显著的不同在于：ImprovedQAIS算法改进了交易非空子集的生成方法，废除了SubItemSet结构，改变了通过集合并交运算进行记数的方法，使用了一种适应新算法的项目集存储结构 。
新的子集生成方法大大地降低了项目子集生成的复杂度。同时，由于复杂度的降低，非空子集元素（项集）生成过程中占用的空间大大减少，这将使该算法能够处理较大的数据集，在某种程度上增强了算法的适应性。
废除SubItemSet结构，直接将生成的项集送入 整合项集合，节约了内存空间，用简单的查找代替并交运算进行记数，也降低了算法的复杂度。我们知道，能够寻找到给定最小支持度下的频繁集是形成关联规则的基础，而项集是不是频繁集并不是一成不变的，关键就是看它们的支持度能否满足最小支持度。而项集支持度只能通过直接的或间接的方法从初始数据库中获取。Apriori算法对项集支持数的获取是通过一遍又一遍扫描初始数据库直接实现的。QAIS 算法不同于Apriori算法的一个显著特点就是将初始数据库中有关于频繁集的信息进行了整合，归并到了一起集中管理，方便查询，QAIS 算法虽然指出了整合的概念，但并没有提出一个切实可行的方案，可操作性不强。ImprovedQAIS算法使用了一种适应于整合信息的数据结构，在这个结构中，将不同长度的项集分开存储，同一长度的项又按计数值大小排列，方便而又节省查询时间。该结构的一个特点是采用了链表结构，方便插入操作。
另外需强调的是，ImprovedQAIS算法还比QAIS 算法避免了项集的重复生成，节省了时间和空间。
参考文献：
[1] 邵峰晶．数据挖掘——原理与算法，北京：中国水利水电出版社，2003.
[2] 颜雪松，蔡之华．一种基于Apriori算法的高效关联规则挖掘算法的研究[J].计算机工程与应用，2002，38（10）.
[3] 李绪成，王保保．挖掘关联规则中Apriori 算法的改进[J].计算机工程，2002，28(7).
收稿日期：2008-03-27
作者简介：刘金忠（1972-），男，湖南桃源人，中级职称，就只于湖南省医药中等专业学校，研究方向：计算机教育。
关键词：关联规则；数据挖掘；基于搜索；算法
中图分类号：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）。
3 QAIS算法的改进算法——ImprovedQAIS算法
3.1 QAIS算法存在的问题
QAIS 算法的关键是只需要对初始数据库一次扫描就要生成所有的频繁项目集的最大超集。对每一个包含n个项目的交易都将产生2n-1个非空项目集。由这些交易形成的项集的并集组成了这个最大超集。而一般要挖掘的初始数据库都有成千上万个交易，所需计算和存储的候选项目集的数量往往非常庞大，这样，如果不对该算法进行一定的改进，它只能适应于交易数量较少并且交易本身的长度较短的数据库关联规则挖掘。
3.2 改进的QAIS算法——ImprovedQAIS算法
针对上述问题，必须对原程序做一些变化。首先，可以将SubItemSet这种数据结构弃之不用。然后，为适应新算法，对 的数据结构做一个改动：由于知道最长的交易为max_T，所以首先可先建立一个长度为max_T的一维数组。其次，分别建立max_T个单链表，分别用于存储长度是从1 到max_T的项集，该链表的每个节点将有三个域：一个存项集，一个存该项集的支持数，一个存指向下一个节点的指针。最后，这max_T个链表的首地址分别存储在先前建立的一维数组中，存储时按照其指向的项集的长短来进行，即：数组的单元1 存指向长度为1 的链表首地址，单元2 存指向长度为2 的链表首地址，依次类推。第三，设立一个固定的存储单元，允许项目作为集合元素存放入该单元。
3.3 新旧QAIS算法的比较
新旧QAIS 算法的最显著的不同在于：ImprovedQAIS算法改进了交易非空子集的生成方法，废除了SubItemSet结构，改变了通过集合并交运算进行记数的方法，使用了一种适应新算法的项目集存储结构 。
新的子集生成方法大大地降低了项目子集生成的复杂度。同时，由于复杂度的降低，非空子集元素（项集）生成过程中占用的空间大大减少，这将使该算法能够处理较大的数据集，在某种程度上增强了算法的适应性。
废除SubItemSet结构，直接将生成的项集送入 整合项集合，节约了内存空间，用简单的查找代替并交运算进行记数，也降低了算法的复杂度。我们知道，能够寻找到给定最小支持度下的频繁集是形成关联规则的基础，而项集是不是频繁集并不是一成不变的，关键就是看它们的支持度能否满足最小支持度。而项集支持度只能通过直接的或间接的方法从初始数据库中获取。Apriori算法对项集支持数的获取是通过一遍又一遍扫描初始数据库直接实现的。QAIS 算法不同于Apriori算法的一个显著特点就是将初始数据库中有关于频繁集的信息进行了整合，归并到了一起集中管理，方便查询，QAIS 算法虽然指出了整合的概念，但并没有提出一个切实可行的方案，可操作性不强。ImprovedQAIS算法使用了一种适应于整合信息的数据结构，在这个结构中，将不同长度的项集分开存储，同一长度的项又按计数值大小排列，方便而又节省查询时间。该结构的一个特点是采用了链表结构，方便插入操作。
另外需强调的是，ImprovedQAIS算法还比QAIS 算法避免了项集的重复生成，节省了时间和空间。
参考文献：
[1] 邵峰晶．数据挖掘——原理与算法，北京：中国水利水电出版社，2003.
[2] 颜雪松，蔡之华．一种基于Apriori算法的高效关联规则挖掘算法的研究[J].计算机工程与应用，2002，38（10）.
[3] 李绪成，王保保．挖掘关联规则中Apriori 算法的改进[J].计算机工程，2002，28(7).
收稿日期：2008-03-27
作者简介：刘金忠（1972-），男，湖南桃源人，中级职称，就只于湖南省医药中等专业学校，研究方向：计算机教育。