基于数据流的频繁闭项集挖掘.docx

基于数据流的频繁闭项集挖掘文／陈凤娟摘要：关联规则挖掘是数据挖掘的一项重要技术，它主要是通过频繁闭项集挖掘得到关联规则。因此，频繁项集挖掘算法的性能对关联规则挖掘算法起到了决定性的作用。基于数据流的频繁闭项集挖掘能针对数据流有效地挖掘频繁闭项集，本文主要分析基于数据流的频繁闭项集挖掘算法及其在关联规则挖掘中的应用。关键词：关联规则，数据流，频繁闭项集，A-Close,CFI_Stream引言近几年，计算机和网络技术飞速发展，各个行业中存储了海量的数据，并且这些数据的数量还在增长。这些海量数据蕴含着丰富的知识，如何找出数据中蕴含的知识，为各种决策提供帮助成为了一个迫切需要解决的问题。数据挖掘技术运用了机器学习和模式识别等多个领域的知识，为解决这个实际问题提供了有力的工具。关联规则是数据挖掘的一个主要技术，它能从给定的数据集中，通过关联规则挖掘算法，找出各个属性之间的关联关系，以及多个属性域之间的依赖关系，这种依赖关系对决策和预测有作用。传统的数据库中存储的数据是基于集合的数据，这种数据虽然数量大但是相对变化较小，而随着网络的发展，产生了大量的、无限的、快速的、随时间变化的数据，这种连续到达且有顺序的序列称为数据流。本文主要分析关联规则的基本概念，然后分析基于数据流的频繁闭项集挖掘的常用算法，并探讨算法的优劣。1、关联规则的基本概念关联规则的挖掘是分两步来实现的，首先按照用户给定的最低阈值，找出数据集中的所有频繁项目集，然后从频繁项目集中构造规则，要求构造的规则的可信度大于等于用户设定的最低值。支持度是对关联规则代表的重要性进行度量的指标，它体现了关联规则的频度。如果某个项集的支持度的值太小，则表明相应的规则很可能只是偶然发生的。频繁项集挖掘就是要在事务数据库里找出所有大于给定的最小支持度的频繁项集。频繁闭项集是一组事务都包含的项的最大项集。频繁闭项集和频繁项集的信息量相等，但是频繁闭项集比频繁项集的元素少很多，因此挖掘频繁闭项集能够满足用户的需求并且对减少了算法的开销，提升了频繁项集挖掘的效率，同时还减少了冗余信息的输出。2、频繁闭项集挖掘由于频繁闭项集的个数远远小于频繁项集的个数，通过频繁闭项集还能计算出所有的频繁项集及其支持度，因此对于频繁闭项集的挖掘频繁成为一个新的研究热点。A-Coles算法是一个基于Apriori算法的挖掘频繁闭项集的算法，它与Apriori算法类似，是通过对数据集进行多次扫描，通过计算得到所有的频繁闭项集的一种算法，它属于自底向上的宽度优先的搜索。A-Coles算法主要由两步组成，第一步是通过宽度优先的搜索策略发现所有的频繁闭项集的生成器，第二步是对每一个生成器，使用相应的函数来计算该生成器对应的频繁闭项集。由于A-Coles算法是宽度优先的算法，它需要多次扫描数据集，其中包括用来计算生成器的支持度的扫描次数，还要加上1次用来计算生成器对应的频繁闭项集。A-Close通过引入剪裁技术减小搜索范围，但是该算法对数据集的扫描次数较多，在算法的运算过程中会产生大量的候选项集，对内存的消耗较大。Closet算法是一个基于频繁模式树的频繁闭项集挖掘算法，它使用频繁模式树存储数据集中的事务间的关联信息，通过这种方式压缩信息，然后使用生成的频繁模式树计算每一个频繁项的条件频繁模式树，在每一个条件模式树中存储了该频繁项的信息，并且只存储支持度大于等于给定支持度的频繁模式。Closet算法只需遍历两次原始数据集，降低了对数据集的访问，不需要生成任何侯选项集，有效地提高了挖掘效率。但是当数据量大的时候，Closet算法生成的频繁模式树的规模过大，导致算法性能下降。3、面向数据流的频繁闭项集挖掘由于数据流的特性，使原有的频繁闭项集挖掘算法不能直接应用于数据流的挖掘。目前，出现了一些数据流的频繁闭项集挖掘算法，其中较具代表性的是CFI-stream算法。CFI-stream算法是一种基于滑动窗口的频繁闭项集挖掘算法，不需要判断结点类型，也不需要额外存储频繁闭项集以外的项集，就能直接生成和更新频繁闭项集。相对于其他算法，CFI-stream算法的时间和空间效率有很大地提高，在数据流中的事务之间关联度高时，该算法的效率更高。CFI-Stream算法的核心是DIU树(DirectUpdateTree)，DIU树包含k+l层，其中k为数据流中闭项集的最大长度。DIU树的第0层是根节点，其值为空(null)，第一层存储闭合1-项集，第二层存储闭合2-项集，第i层存储闭合i-项集i(i=1，2，，，k)，每个父节点是子节点的子集，且为闭集。除了根节点外，DIU树中的每个节点都表示一个闭项集，在这个节点中保存闭项集的当前支持度信息。每个结点包含的信息有：当前滑动窗口的支持数、指向父结点的指针、指向孩子结点的指针。CFI-Stream算法对