英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料

Index-CloseMiner:一种改进的频繁闭项集挖掘算法

Wei Songa,lowast;, Bingru Yangb and Zhangyan Xuc

aCollege of Information Engineering, North China University of Technology, Beijing, 100144, China

bSchool of Information Engineering, University of Science and Technology Beijing, Beijing, 100083, China

cDepartment of Computer, Guangxi Normal University, Guilin, 541004, China

摘要：频繁闭项集唯一确定频繁项集且规模小得多，但挖掘频繁闭项集仍然是很费时的，为提高挖掘效率，提出了一种改进的频繁闭项集挖掘算法DCI-Closed-Index。该算法用“索引数组”来组织数据，通过为每个项目增加包含索引，找出频繁共同出现的项集，利用二进制位图技术，给出了一个求包含索引的快速算法，然后根据项目在包含索引中出现的频率由高到低进行排序，并利用包含索引作为启发信息，合并同时出现并且支持度相等的频繁项，得到初始生成子，从而大大缩小了搜索空间。同时利用索引数组对每一个生成子的前序集和后序集进行约简，得到新的、较小的约简前序集和约简后序集，并证明了约简前序集和后序集与原来的前序集和后序集功能是一样的，从而减少了候选生成子的集合包含判断的操作。实验结果表明，该算法的性能优于其他主流算法。

关键词：数据挖掘, 关联规则, 频繁闭项集, 索引数组, 包含索引

1. 介绍

1.1 目的

频繁项集挖掘是数据挖掘研究中的一个重要内容. 它一开始是作为发现关联规则的依据[1],但是已经被独立概括为许多模式.例如, 频繁序列 [2], 插曲 [3], 和频繁子图 [4].

频繁项集挖掘的问题可以如下概括: 假设 I ={i₁, i₂, . . . , i_M } 是一个特定的项 且 D 是一个事务集包含N个事务, 每一个事务 t D 是一系列特定的项 t ={i ₁, i₂,. . . , i_|t|}, i_j I(1 j |t|). 假设 X 是一个 k-itemset, 当 X ={i₁, i₂, . . . , i_k } 时一个k项集. 假设一个k项集X, supp(X) 是他的支持度, 被定义为D中含有X的事务的个数. 从D中挖掘出所有的频繁项集需要发现所有的支持度大于等于最小支持度的项集。这需要从I给出的大量的搜索空间中搜索。

FIM问题已经被研究了许多年. 一些原始算法的改进算法同一些新的算法被提出[6–9]. 大多数优秀的频繁闭项集挖掘算法，包括Apriori，ECLAT，和FP-Growth，挖掘出了完整的频繁项集。

这些算法也许在处理支持度阈值高和稀疏数据集时性能较好。然而，当支持度阈值低，频繁项集的数量急剧上升时，这些算法的性能下降很快因为构造大量的项集。而且，挖掘完整序列的效率也会急剧下降因为它构造了大量的冗余项集。

目前主要有两种处理这个问题的方法。第一个就是仅仅挖掘出最大频繁项集，其序列大小小于所有的频繁项集。然而挖掘最大项集帮助理解稠密领域的长项集，它们导致信息的缺失，因为子集的频繁性未知。因此，最大频繁项集不适合构造关联规则。

第二种就是仅仅挖掘频繁闭项集。频繁项集是所有频繁项集项集及其频繁性的无损表示。同时，频繁闭项集的大小也小于频繁项集，尤其是稠密数据库。更重要的是，从频繁闭项集中得出的关联规则被证明对分析更有意义，因为没有冗余。在这片文章中，我们研究了一个挖掘频繁闭项集的有效算法。

1.2 相关工作

在1999年，Pasquier等人提出以挖掘频繁闭项集替代完整集合。他们设计了一种基于Apriori算法的A-Close算法。该算法采用自底向上、宽度优先的搜索策略，通过构造“生成子集合”，逐层求出所有频繁闭项集。尽管利用剪枝策略可以缩小搜索空间，但没有解决重复扫描数据库的问题。其他构造测试的算法包括Close和Titanic。

以FP-Growth为基础，Pei等人提出了Closet算法。Closet使用深度优先搜索策略，其困难是，递归构造“条件FP-Tree”的CPU开销和存储开销很大。同时，Closet采用分割法处理大型数据集，检查局部频繁闭项集的全局闭合性和频繁性的代价非常大。使用相同的策略，这个算法的改进算法主要有Closet ，Afopt-Close和FP-Close。

和仅仅利用闭项集搜索空间的算法不同，CHARM算法使用了一个垂直的形式，并且同时对闭项集搜索空间和事务的一种被称为IT-Tree的数据结构搜索。IT-Tree中的每一个结点都包含FCI的一个候选和它属于的一系列事务。CHARM采用深度优先搜索策略，并不用分割数据集。然而，它一次只生成一个候选。然后，它尝试判断它是否属于FCI，使用tid集合和子集检测。而且，diffset 技术被用来减少rowid表的数量和计算复杂度。尽管不同的路径指向相同的闭项集，CHARM利用hash表快速分离出已经挖掘出的闭项集。

Y包含给定的频繁项集 X. CloseMiner [21] 是ChARM的一个变形. 主要思想是将完整的项集组队放进non-overlapping 集群中，并且每一个集群都是被tid集合独特定义的。

LCM和DCI-Closed算法都继承了在CHARM算法中提出的tid集合的使用。它们使用深度优先策略遍历搜索空间。在发现一个FCI Z后，它们构造了一个新的生成子gen通过将Z与一个频繁项i进行关联。使用一个完整的次序关联，LCM和DCI-Closed算法会变化，如果gen违反了这个次序通过性能测试。如果gen未被声明，gen是一个保序的新的FCI的生成子。它的闭合性使用以前的提过的tid集合进行计算。这些算法不需要在主存中存储，这个集合包含以前挖掘出的FCIs。LCM和DCI-Closed算法的不同在于他们存储闭合性和采取的数据结构。

1.3 我们的贡献

通过介绍生成子的前序属性，DCI-Closed提议了一个一般性的和存储效率的技术去避免重复的构造。它被证明，对每一个闭项集，它能够生成前序生成的唯一序列。为了检查一个给定的生成子是否是保序的，DCI-Closed介绍了前序集合后序集的概念。保序生成子序列通过检查候选生成子的tid集合是否包含在前序集和后序集的tid集合中来获得。然而，在前序集和后序集中都有大量的元素，尤其当数据集包含大量的项时。因此，这些检查操作有时候非常耗时间。

为了解决以上问题，我们提出了一个改进算法Index-CloseMiner 来挖掘频繁闭项集。这篇论文的贡献如下所示：

1. 提出了索引数组的概念，它可以用来发现那些从事结伴出现的项集。然后，通过使用二进制位图技术，给出了一个计算索引数组的算法。
2. 基于索引数组，我们可以直接定义一些闭项集。在我们的算法中，这些闭项集被用来构造保序生成子。
3. 基于索引数组，提出了约简前序集和约简后序集。实验证明了约简前序集和约简后序集与原来的DCI-Closed算法中的前序集和后序集功能是一样的。因此，它们减少了大量冗余的候选生成子的集合判断操作。

实验数据表明所提算法在密集型数据库上效率显著。剩下的论文按如下方式组织：在第二章，我们回顾了频繁闭项集挖掘的定义问题。 在第三章，我们介绍了索引数组的定义和构造索引数组的相关算法。在第四章，我们提出了算法Index-CloseMiner，该算法利用了索引数组所提供的启发信息。尽管第五章我们报告了Index-CloseMiner 算法与其它算法的性能对比，我们还是在第六章做出了总结。

2. 问题陈述

设T 和 X, T sube; D 且 X sube; I, 分别是出现在D中的所有事物和项目的子集。

闭项集的概念基于两个方法，f 和 g：

f (T ) = {iisin;I |forall; tisin;T , iisin;t}

g(X) = {tisin;D |forall; iisin;X, iisin;t}

图1 示例数据库

方法 f 与T 中所有相同的项集 tisin;T 相关联而且g 与 X 中的对象相联系，且iisin;X。

定义1. 一个项集X是闭项集当且仅当：

c(X) = f (g(X)) = f ◦ g(X) = X

相反的操作 c = f ◦ g 被称为Galois操作或者闭操作。一个闭项集X是频繁的当它的支持度大于等于给定的支持度阈值min sup。

闭操作定义了一系列等价类基于频繁项集点阵：两个项集属于同一个等价类当且仅当他们有相同的闭合性。他们被同样的事务集所支持。我们同样可以表明一个项集X是频繁的当且仅当不存在与X支持度相同的超集。因此，挖掘所有等价类中最大元素等同于挖掘所有的闭项集。

图1中给出了一个示例数据库。为方便起见，我们将项集{A, B, C}写作ABC，并且，一系列事务的标识符 {2,4,5}写作245。在示例数据库中， f (14) = f (1) cap; f (4) =ABCDEFcap;

ABCDF=ABCDF，且 g(BCF)=g(B) cap; g(C) cap; g(F ) = 1345cap;1345cap;1345=1345. 当c(BCF)=f ◦ g(BCF)=f (1345)=BCF, BCF是一个闭项集。

3. 索引数组的构造

为了减少搜索空间和前序集及后序集的大小，我们介绍了索引数组的定义。

定义 2. An index array 是一个大小为 m1的数组，m1 是频繁1项集的数量。数组中的每一个元素与一个二元组(item, subsume)相关联，item是一个项目，subsume(item)={j I|j =item g(item) g(j)}. 对索引数组中的每一个元素，我们可以item出每一个代表性的项目，然后找出包含项集的包含索引。

项的子项索引是一个项集，其含义是如果j子项（项），则项的tidset是j的tidset的子集。例如，在示例数据集（如图1所示）中，d的子项索引是abcf。通过使用子项索引，这些项集可以同时出现并共享相同的支持，可以合并在一起。

生成索引数组的伪代码如算法1所示。

在算法1中，首先扫描数据库D一次，以确定频繁的单个项目（步骤1）。在步骤2中，频繁项目按一定的顺序排序（例如字典顺序），排序后的频繁项目作为代表性项目逐个分配给索引数组的元素（步骤3-4）。在步骤5中，构建了数据库D的位图表示。那就是说，对于一个事务T，如果一个频繁1-项集i被T包含，然后将设置与t中的i对应的位。索引数组由主循环计算（步骤6-13）。子项索引的新候选项是通过将包含项索引[J].项的所有事务交叉形成的（步骤7-8）。然后根据定义2（步骤9）获得子项指数。接下来，启发式信息

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[19626]，资料为PDF文档或Word文档，PDF文档可免费转换为Word