论文部分内容阅读
摘要：针对Apriori算法的缺陷，引入一种新结构—链表数组来压缩存放数据的相关信息，并结合修剪频繁集和连接优化策略，得到一种新的关联规则挖掘算法FAA算法。该算法只须扫描两遍数据库，优化了连接操作，提高了候选项集的支持事务计数的效率，减少了候选项集的数目，较好地提高了算法的效率。实验结果表明FAA算法是可行有效的。
关键词：数据挖掘；频繁项集；链表数组
中图分类号：TP311 文献标识码：A 文章编号：1007-9599 （2012） 19-0000-03
1 引言
数据挖掘是从大量的数据中，发掘出潜在有用的模式和信息的技术。当前主要的数据挖掘方法有关联规则、分类和聚类。其中，关联规则致力于发现数据中的频繁模式，它最早由R.Agrawal等人针对购物篮问题提出，其目的是为了发现交易数据库中不同商品间的联系，以帮助商家进行商品目录和货架设计，科学安排进货和库存，实施交叉销售。
最经典的频繁项集挖掘算法是Apriori算法[1]。它首次采用了基于频繁项集性质的自底向上的广度优先逐层搜索迭代技术，即利用已知的频繁k-项集推导出频繁（k+1）-项集。Apriori算法有三个主要步骤：（1）用频繁（k-1）-项集进行自连接来产生候选k-项集。（2）用Apriori性质进行对候选k-项集进行剪枝操作。（3）扫描数据库得到候选项集支持度。由上述分析可知，Apriori算法需要多次扫描数据库，I/O开销较大。另外，子集计算、共同前缀项集计算等也极大增加了算法的开销。为提高Apriori算法的效率，先后出现了许多基于Apriori的改进算法。文献[2]提出DHP算法，它利用哈希技术压缩候选项集集合Ck，同时也缩减了数据库的大小，降低I/O开销。此算法缺点在于哈希表会增加算法的内存开销，而且实现起来也较为麻烦。文献[3]提出Partition算法，它采用划分技术成功解决内存不足的问题，具有较好的可扩展性。然而，Partition算法可能产生大量虚假的候选项集。文献[4]提出选样技术，在给定数据的一个子集中挖掘频繁模式。Sampling算法简单并减少了I/O代价，但其产生的结果不精确，即存在所谓的数据扭曲。文献[5]提出DIC算法，它放松了产生候选项集和计数的严格界限，采用动态模式计数法以减少数据库的扫描次数，具有较好效率。
尽管有如上所述的诸多改进方法，但时间效率还不尽理想，为更进一步提高算法性能，提出一种基于Apriori的改进型算法FAA（Fast Apriori Algorithm）。FAA算法通过构造链表数组来快速产生频繁2-项集并减少数据库的扫描次数，优化对项集计数操作；改进连接策略来简化连接算法复杂度。
2 FAA算法思想
2.1 链表数组定义及生成算法。链表数组定义：数组为n个指针的一维数组P[n]，对应数据库中的频繁项I1，I2，…，In，对应数组长度n为数据库中频繁项的数量。结点为事务结点，分为事务域、计数域和指针域。事务域是以频繁项为后缀的事务编码。计数域是该事务编码的数量，指针域是指向下一结点的指针。
编码方法：设数据库中有n个频繁项I1，I2，…，In。事务t的编码就是长度为n的0、1位串。在t中出现的项，其相应位置用1表示，否则填0。例如，有四个频繁项a，b，c，d。那么，一个包含a和c的事务就被映射为1010。
链表数组的构造过程如下：（1）扫描事务数据库，产生所有频繁1-项集及支持度计数，依据支持度计数降序排列，生成FI-List。（2）再次扫描数据库，将每条记录中不满足最小支持度计数的项删除，并将剩余项按照FI-List重新排序。设形成的新序列为{m1，m2， …，mn}，依次取出序列中的前k（1≤k≤n）项组成子序列{m1，m2， …，mk}，对每个子序列进行编码并建立一个与之对应的事务结点，并按照子序列中最后一项追加到P[n]中相应链上。
例1：表1是事务数据库，最小支持度计数为3。扫描整个数据库后，链表数组如图1所示。
关键词：数据挖掘；频繁项集；链表数组
中图分类号：TP311 文献标识码：A 文章编号：1007-9599 （2012） 19-0000-03
1 引言
数据挖掘是从大量的数据中，发掘出潜在有用的模式和信息的技术。当前主要的数据挖掘方法有关联规则、分类和聚类。其中，关联规则致力于发现数据中的频繁模式，它最早由R.Agrawal等人针对购物篮问题提出，其目的是为了发现交易数据库中不同商品间的联系，以帮助商家进行商品目录和货架设计，科学安排进货和库存，实施交叉销售。
最经典的频繁项集挖掘算法是Apriori算法[1]。它首次采用了基于频繁项集性质的自底向上的广度优先逐层搜索迭代技术，即利用已知的频繁k-项集推导出频繁（k+1）-项集。Apriori算法有三个主要步骤：（1）用频繁（k-1）-项集进行自连接来产生候选k-项集。（2）用Apriori性质进行对候选k-项集进行剪枝操作。（3）扫描数据库得到候选项集支持度。由上述分析可知，Apriori算法需要多次扫描数据库，I/O开销较大。另外，子集计算、共同前缀项集计算等也极大增加了算法的开销。为提高Apriori算法的效率，先后出现了许多基于Apriori的改进算法。文献[2]提出DHP算法，它利用哈希技术压缩候选项集集合Ck，同时也缩减了数据库的大小，降低I/O开销。此算法缺点在于哈希表会增加算法的内存开销，而且实现起来也较为麻烦。文献[3]提出Partition算法，它采用划分技术成功解决内存不足的问题，具有较好的可扩展性。然而，Partition算法可能产生大量虚假的候选项集。文献[4]提出选样技术，在给定数据的一个子集中挖掘频繁模式。Sampling算法简单并减少了I/O代价，但其产生的结果不精确，即存在所谓的数据扭曲。文献[5]提出DIC算法，它放松了产生候选项集和计数的严格界限，采用动态模式计数法以减少数据库的扫描次数，具有较好效率。
尽管有如上所述的诸多改进方法，但时间效率还不尽理想，为更进一步提高算法性能，提出一种基于Apriori的改进型算法FAA（Fast Apriori Algorithm）。FAA算法通过构造链表数组来快速产生频繁2-项集并减少数据库的扫描次数，优化对项集计数操作；改进连接策略来简化连接算法复杂度。
2 FAA算法思想
2.1 链表数组定义及生成算法。链表数组定义：数组为n个指针的一维数组P[n]，对应数据库中的频繁项I1，I2，…，In，对应数组长度n为数据库中频繁项的数量。结点为事务结点，分为事务域、计数域和指针域。事务域是以频繁项为后缀的事务编码。计数域是该事务编码的数量，指针域是指向下一结点的指针。
编码方法：设数据库中有n个频繁项I1，I2，…，In。事务t的编码就是长度为n的0、1位串。在t中出现的项，其相应位置用1表示，否则填0。例如，有四个频繁项a，b，c，d。那么，一个包含a和c的事务就被映射为1010。
链表数组的构造过程如下：（1）扫描事务数据库，产生所有频繁1-项集及支持度计数，依据支持度计数降序排列，生成FI-List。（2）再次扫描数据库，将每条记录中不满足最小支持度计数的项删除，并将剩余项按照FI-List重新排序。设形成的新序列为{m1，m2， …，mn}，依次取出序列中的前k（1≤k≤n）项组成子序列{m1，m2， …，mk}，对每个子序列进行编码并建立一个与之对应的事务结点，并按照子序列中最后一项追加到P[n]中相应链上。
例1：表1是事务数据库，最小支持度计数为3。扫描整个数据库后，链表数组如图1所示。