界标窗口中数据流频繁模式挖掘算法研究.doc

2012 年 1 月January 2012计算机工程Computer Engineering第 38 卷第 1 期Vol.38No.1软件技术与数据库文献标识码：A文章编号：10003428(2012)01005504中图分类号：TP311.13界标窗口中数据流频繁模式挖掘算法研究张广路 1，雷景生 2，吴兴惠 1(1. 海南师范大学数学与统计学院，海口 571158；2. 南京邮电大学计算机学院，南京 210046)摘 要：数据流的流量太大会无法被整个存储，或被多次扫描。为此，在研究已有挖掘算法的基础上，提出一种界标窗口中数据流频繁模式挖掘算法 DSMFP_LW。利用扩展前缀模式树存储全局临界频繁模式，实现单遍扫描数据流和数据增量更新。实验结果表明，与 LossyCounting 算法相比，DSMFP_LW 算法具有更好的时空效率。 关键词：界标窗口；频繁模式；数据流；DSMFP_LW 算法；滑动窗口Research on Data Stream Frequent Pattern Mining Algorithmin Landmark WindowZHANG Guang-lu1, LEI Jing-sheng2, WU Xing-hui1(1. School of Mathematics and Statistics, Hainan Normal University, Haikou 571158, China;2. School of Computer Science & Technology, Nanjing University of Posts and Telecommunications, Nanjing 210046, China)【Abstract】For data traffic flow is too large to store the entire data stream or on its scan times and other issues, through the research of algorithmson mining frequent patterns that are proposed, this paper proposes an algorithm on mining frequent patterns over data stream based on Landmark window, named DSMFP_LW. DSMFP_LW has major features as follows: namely single streaming data scan for counting patterns information, extended prefix-tree-based compact pattern representation, and incremental update of data. Experimental results show that DSMFP_LW algorithm has better utilization of time and space efficiency. In addition, it outperforms the well-known algorithm Lossy Counting in the same streaming environment.【Key words】landmark window; frequent pattern; data stream; DSMFP_LW algorithm; sliding windowDOI: 10.3969/j.issn.1000-3428.2012.01.0141 概述数据流广泛出现在传感器网络、金融证券管理、网络监 控、Web 日志以及通信数据在线分析等新型应用领域中。由 于数据流中数据的规模一般都十分庞大、且增长迅速，因此有限的存储空间中无法完整地保存数据流上的全部数据，这给数据流上的数据处理带来了巨大的挑战，数据流频繁模式 挖掘技术逐渐成为数据挖掘领域研究中的问题。针对数据流 中数据的快速变化、规模宏大及单遍扫描的特点，对数据流 上频繁模式挖掘算法提出了更高的要求。在数据流频繁项集挖掘方面，国外许多学者深入研究并 提出了自己的算法1-7。文献2提出 Lossy Counting 算法，将 数据流分成事务数相等的桶，算法使用数据结构 D(e, f, )保 存项集信息，但是由于产生的候选项集数量巨大，而且将数 据存储在辅存中，致使算法效率不高。但是该算法产生了太 多的候选模式集合。文献3提出并实现了 DS-CFP 算法。 DS-CFP 算法将滑动窗口分割为若干个基本窗口，以基本窗 口为更新单位，利用 DSCFP_tree 可以快速地挖掘滑动窗口中 的所有频繁闭合模式。文献4提出了算法 DSFPM，该算法 实现了在滑动窗口中挖掘频繁模式。滑动窗口只关注了最近 的数据信息，忽略历史数据的影响。但是在某些场合下，历 史数据对问题的决策也起到不可忽视的作用，如银行客户的 历史存款信息等。本文在对文献4所提算法进行研究后，提出了一种基于 界标窗口的数据流频繁模式挖掘的 DSMFP_LW 算法，它采 用频繁闭合模式树的结构存储临界频繁闭合模式，有效地挖掘历史数据的所有频繁模式，该算法能兼顾历史数据和最新数据对问题决策的影响。2 相关定义定义 1(事务和模式)4,6 设 I=x1,x2,xm是 m 个项目组成的集合，项集是项目的一个子集也称为模式，用 X 表示，即 X=xi,xj,xn，其中，1i,j,k,nm 数据流 DS 是由不断 到达的事务组成的动态增长事务集，DS=T1,T2,，其中每 个事务 Ti(i=1,2,)是 I 的项集，即 TiI。定义 2(基本窗口、基本窗口长度、界标窗口和界标窗口长度) 将数据流 DS 分段 Bi(i=1,2,)，即 DS=B1,B2,BN,，是无限数据流段，每一个分段对应一个数据流子序列且事务数一定，这样一个数据分段称为一个基本窗口，记为 B。其 中，第 N 个窗口表示为 BN，每个基本窗口包含的事务数(即 窗口的长度)为|Bi|。界标窗口对应一个开始时间固定结束时 间不定的连续个基本窗口，记为 CL。界标窗口的长度:是指 从开始时间到目前为止流入界标窗口的所有基本窗口组成事 务数，记为 CLN，且|CLN|=|B1|+|B2|+|BN|，即 CLN 表示目前 流入界标窗口 N 个基本窗口事务集。 基金项目：海南省自然科学基金资助项目(610221, 109002, 808155)；海南师范大学青年科研基金资助项目(QN0923) 作者简介：张广路(1978)，女，讲师，主研方向：数据库技术， 数据挖掘，模糊信息系统；雷景生，教授、博士；吴兴惠，讲师、 硕士收稿日期：2011-06-28E-mail：zgl_0251163.com定义 3(支持数和支持度) 数据流 DS 中包含模式 X 的事务数称为模式 X 的支持数，记为 fDS(X)。模式 X 的支持度记 为 s(X)。s(X)=fDS(X)/|DS|，其中，|DS|是数据流 DS 中的事务 数。若模式包含了 k 个项目，则称 X 为 k 模式。定义 4(频繁模式、临界频繁模式和非频繁模式) 给定最 小支持度阈值 s 和误差因子 ，|CLk|表示界标窗口长度，|Bi|表示基本窗口长度，对于模式 X，如果有 fCLk(X)(s)|CLk| (fBi(X)(s)|Bi|)，则称模式 X 为界标窗口 CLk(第 Bi 段窗口) 的频繁模式。如果有 fCLk(X)|CLk|(fBk(X)|Bi|)，则称模式 X 为界标窗口 CLk(第 Bi 个基本窗口)的临界频繁模式。如果 有 fCLK(X)|CLk|(fBi(X)|Bi|)，则称模式 X 为界标窗口 CLk (第 Bi 段窗口)的非频繁模式。3 DSMFP_LW 算法3.1 算法基本结构DSMFP_LW 算法用到的概要结构由 4 个部分组成：全局频繁 1-项集列表(fp_list)，项头表(ID_list)，临界频繁模式树(CFP_tree)和全局频繁模式输出列表(FPop_list)。fp_list：记录数据流中频繁项的信息，每个元素由 3 个 域组成(Item_id, support, del) ，其中，Item_id 表示项名； support 表示当前 N 段数据流中项目的计数；del 表示删除不 频繁项的计数。表中的项按计数进行非递增排序，结构如 表 1 所示。FPop_list ：是一个数组结构，有 2 个域组成(support,FI_link)，其中，support 表示模式技术信息，FI_link 是一个 指针，指向每个模式串。CFP_tree 的特点：CFP_tree 树结构与 Pattern-Tree7外观 类似。但 CFP_tree 中分支与 Pattern-Tree 中分支所表示的含义不同，由文献7可知，Pattern-Tree 中一个含有 k 个结点I1,I2,Ik的分支，表示 k 个模式的支持度计数信息(I1, I1, I2, I1, I2, I3,I1, I2, I3,Ik)，而 CFP_tree 中相同长 度的分支则表示 2k1 个模式的计数信息。由此可见，CFP_tree 中的每一个分支包含了该分支上所有结点组成的最长模式和 它的各个子模式的计数信息。另外 CFP_tree 中一个模式的支 持度计数需由包含该模式的所有分支共同确定，例如在图 1中，模式I1, I2, I5的支持度计数为 3，是包含I1, I2, I5的分支I1, I2, I3, I5：2 和I1, I2, I5：1 模式信息之和。3.2 算法基本流程 算法将数据流分成若干等长的数据流段，在第一个数据流段到来时生成一个临界频繁 1-项集的排序表 fp_list，并且 在以后每一个数据流段到来时更新 fp_list，并且对 fp_list 中项按照 support 值进行降序排列，为重构 CFP_tree 提供依据。算法采用 CFP_tree 结构存储 CLi-1 段临界频繁模式集，称为全局频繁模式树。当第 Bi 段数据流到来时，根据更新的 fp_list 对 CFP_tree 进行重构。重构 CFP_tree 分为 3 步进行：(1)对 CLi-1 窗口中的树进行排序，将 CFP_tree (CLi-1 窗 口中)每个分支上的结点都按当前 fp_list 表中临界频繁 1-项 集的支持度计数降序排序，这样可以使得出现频率越高的项目出现在离树根越近的地方，使更多的模式能共用前缀，增 加压缩效率，并能为以后的模式查找和插入以及频繁模式的 输出带来便利。排序后的树命名为 SCFP_tree。(2)以误差因子 为最小支持度阈值，利用传统频繁闭合 模式挖掘算法(CLOSET4)挖掘第 Bi 段数据流的临界频繁闭 合模式集。最后将 Bi 段的频繁闭合模式集中每个模式插入 CLi-1 窗口 SCFP_tree 中，生成 CLi 窗口的 CFP_tree。由于只 需要处理和存储每个数据流段的临界频繁闭合模式集，因此 极大地减少处理时间和数据存储量。(3)算法利用一个频繁模式输出表 FPop_list 来统计保存 在 CFP_tree 中所有临界频繁模式信息，并从 FPop_list 中输 出所有的频繁模式。完整的 DSMFP_LW 算法如下：输入 数据流 DS，支持度 ms 和误差因子 输出 CFP_tree 树中所有的频繁模式将数据流分段 Bi(i=1,2,)，每一段看作是一个基本窗口；for Bi(i=1,2,)表 1B1 段数据流的 fp_listIt_idsupportdelI1I2I3I4I510874485532ID_list：是一个数组结构，有 2 个域(It_id, h_link)，其中，It_id 表示项名；h_link 是链头指针，指向 CFP_tree 树(如下文 介绍)中具有相同项名的第 1 个结点。ID_list 由当前 N 段数 据流的所有临界频繁-1 项集组成，并按照 fp_list 进行排序， 结构如图 1 所示。RootI1 10 0I2 4 0I3 3 0I2 4 0I4 2 0I4 2 0I3 4 0I5 1 0I5 1 0I5 2 0调用 Generater_fp_list(fp_list, Bi)更新频繁 1-项集顺序表 fp_list；/步骤 1重构 CFP_tree if (i!=1)调用 Sort(CFP_tree, fp_list) 对 CFP_tree(CLi-1 窗口)按照 fp_list(CLi 窗口)进行排序；生成 SCFP_tree；调用 CLOSET 算法生成当前段的频繁闭合模式集 B；调用 Insert(SCFP_tree, B)算法，将当前段的频繁闭合模式集插 入 SCFP_tree 树中，生成 CLi 窗口的 CFP_tree 模式树 /步骤 2调用 Output_FI(CFP_tree, FPop_list, ms, ) 输出全局的频繁模 式集；/步骤 3图 1 DSMFP_LW 的基本结构CFP_tree：树中的每个结点有 6 个域(itemname, support, insert, parent, child, nextno del)，其中，item_id 为该结点表示 的项名；support 代表到目前为止到达的数据流中该结点构成 的各个模式的计数信息；insert 是为避免频繁闭合模式重复插 入而设置的一个标志位，当 insert=0 表明没有更新该结点， insert=1 表明该结点已经更新过；parent_link 是指向父接点 指针；child_link 是指向孩子结点指针；nextnode_link 是指向 树中具有相同项名下一个结点的指针。完整的 CFP_tree 结构 如图 1 所示。It_idh_linkI1I2I3I4I5第 38 卷 第 1 期张广路，雷景生，吴兴惠：界标窗口中数据流频繁模式挖掘算法研究571)插入前 CFP_tree 为一颗空树。2) 插入模式 a:3: 首先 计算 插入全局 CFP_tree 中的 a.support 值，根据定义 5 和定理可知，项 a.support 值为 f(a)= f(a)g(M)，其中，g(M)=X|X是 B1 段数据的闭合模式，a X且 X不以a为前缀，满足此条件的 g(M)=0，所以f(a)=30=3；其次将元素 a 插入 CFP_tree 中。3) 插入模式 bc:3: 同 2) ， f(b)=f(bc)g(M) ，其中， f(bc)=3, g(M)=g(abcd)(根据定义 5 和定理可知，bc abc，bc abcd，Xi=b不是abc和abcd的前缀)，3.3 算法执行过程下面以实例的形式说明算法中每步执行的详细过程。设数据流 DS 有 8 条事务，将其分成 2 段，第 1 段数据流 B1 由4 条事务(abc)、(bc)、(abcd)和(a)组成，B2 段数据流由 4 条事务(abd)、(b)、(cd)、(abd)组成，ms=25%，=0.1 ms。(1)读取 B1 段数据流到内存。步骤 1 扫描 B1 段数据，调用算法 Genarater_fp_list(fp_list,B1) ，更新 fp_list 。对项 ek ，如果 ek B1 ek fp_list ，则ek.support=ek.support+1，ek.del=ek.del+1，否则，如果 ekB1则 ek 插入 fp_list 中，且令 ek.suppor=1，ek.del=1。扫描 B1 后，将所有 1 项集按 support 非递增排列，并将所有 1 项集的 del值减 1，如果 del0，则删除该 1 项集，生成一个 CL1 段数据 流的临界频繁 1-项集的排序表 fp_list，见表 2。表 2 CL1 段数据流的临界频繁 1-项集的排序表 fp_listg(abc)=1(因为abc在 B1 段事务集中以最长模式出现 1 次)，同理 g(abcd)=1，所以 f(b)=32=1，同理 f(c)=32=1，将模式 bc 插入 CFP_tree ，同时 置 b.Insert=1 ， b.support=1 ，c.Insert=1，c.support= 1。4) 插入模式abc: 2 ：同模式bc:3 ，其中，f(a)=2 ， f(b)=2，f(c)=2，因为 CFP_tree 中 a.Insert=1，所以 a 结点成 为 abc 的前缀，合并项 a，并且 a.support 值不变，将项 b 和 c 形成分支插在结点 a 的下方。5)插入模式abcd:1：同模式a:3，因为该模式与树中 的模式abc 共用前缀，并且因为 a.insert=1 ，b.insert=1 ，c.insert=1，所以将模式abcd插入后，结点 a、b、c 的 support 值不变，并置 d.insert=1，d.support=1。插入过程及结果如 图 2 所示。图 2 则为对 CL1 段数据流重构后的 CFP_tree，同 时也是全局频繁模式树。It_idsupportdela b c d32313220步骤 2 重新构造 CFP_tree，这一步骤主要包括以下的过程：1)排序 CL0，因为 i=1，CL0 不存在，所以此过程跳过。2)挖掘 B1 段中频繁闭合模式集 B。用经典的频繁闭合模式挖掘算法 CLOSET 挖掘该段数据流的临界频繁闭合模式集，并将 B 中的项集按照模式长度非 递减排序，使尽可能多的模式能够共用前缀，结果为 B=a:3, bc:3, abc:2, abcd:1。3)将模式集 B 的模式插入 SCFP_tree 中。算法 Insert(SCFP_tree, B)实现将 B 中的临界闭合模式插 入到 CLi-1 段排序后的 CFP_tree 中。对任一 X(XB)，首先在 SCFP_tree 中查找是否存在已有的分支与模式 X 有共同前缀， 若存在则共用前缀，把具有共同前缀项进行合并，并计算合并后项的 support 值，X 中其他的部分作为一条新的分支插入 到该共同前缀的最后一个结点；若不存在，则将模式 X 作为 一条新分支插入到根结点，每个项目 support 值等于 X 的 support。由于在 CFP_tree 中，模式 X 在界标窗口中的支持度 计数是所有包含 X 的分支共同确定的，在插入模式 X 的过程 中，要依次计算 X 中项 ei(i=1,2,t)加入到 CFP_tree 对应结 点的 support 值，若插入模式与 CFP_tree 中已有分支有共同 前 缀，且 共同 前缀上 结点的 support 值 之前被 处理过 (Insert=1)，则不用再计算共同前缀上结点的 support 值，直 接计算模式 X 中的其他项的 support 值。下面给出计算插入 计算模式 X 中其他项 support 值的理论依据4。定义 5 g(X)：表示一个事务集中以模式 X 为最长模式的 事务出现的次数，即事务集中仅包含模式 X，而不包含 X 的 任何 超集 的事 务出 现的 次数 。 若 M 是一 个模 式集 ， 则图 2 CL1 段数据的 CFP_tree 的更新过程图示(2)读入 B2 段数据流，重复步骤 1步骤 2 对 B2 段数据流 进行挖掘。步骤 1 调 用算法 Genarater_fp_list(fp_list, B2) ，更 新 fp_list。生成 CL2 段数据流的临界频繁 1-项集的排序表 fp_list， 如表 3 所示。表 3对 CL2 段数据流更新后的全局 fp_listg (M ) =g ( X ) ， f (M ) =f ( X ) 。X MX MIt_idsupportdel定理 设模式 X 为当前数据段的临界频繁闭合模式，X 已按照 fp_list 的顺序排序，X=e1e2et，ei(1it)表示模式 X 中的第 i 个项，则在将模式 X 插入 CFP_tree 中时，则 f(ei)=f(X)g(M)。其中，f(ei)为项目 ei 加入到 CFP_tree 中对 应结点支持度计数，集合 M=(X|X为当前数据段临界频繁闭 合模式且 X X且 X不以 Xi 为前缀，Xi= e1e2ei)。根据定 义 5 和定理给出 B1 段频繁闭合模式集 B 插入到 CFP_tree 的 过程：b a c d65444322步骤 2 重新构 CFP_tree，这一步骤主要包括以下过程：1)CL1 排序。首先删除各个模式中不包含于 fp_list 中的项(包含任何不属于 fp_list 的项的模式一定是非频繁的)；其次将 CFP_tree的每根分支上的结点都按 CL2 段 fp_list 的顺序排序。首先创建一颗只有根结点的新 CFP_tree(new)，然后从 CFP_tree(old)树叶子结点开始，逆序取 CFP_tree(old)项头表中的 ei，沿结 点 ei 链可以得到以 ei 为叶结点的所有分支，将每根分支按 CL2 窗口的 fp_list 顺序重新排序后插入到 CFP_tree(new)中，插入 分支上每个结点的 support 值与 ei 结点上的 support 值相等。 如果插入分支与 CFP_tree(new)中已有的分支有共同前缀，则 合并共同前缀且共同前缀上各结点 support 值分别加上 ei 上 的各结点的 support 值，将其他项目扩展为新的分支，每个插 入 CFP_tree(new)中结点的 insert=0，然后将 CFP_tree(old)分 支上所有结点的 support 值减去 ei 结点 support 值且删除叶子 结点 ei，便可得到新的叶子结点 ej，重复上述操作，直到 CL1 段的 CFP_tree(old)只剩下根结点，删除 CL1 段 CFP_tree(old)， 限于篇幅，图 3 给出 CL1 窗口 CFP_tree 排序过程部分图示， 其中右图为对 CL1 窗口进行排序后生成的 SCFP_tree。和 1 000 000 的总事务数，其他参数使用缺省值。由于采用了批处理思想，因此数据流中的每批事务大小设置为 50k。总 共分为 20 段事务进行处理，最小支持度阈值为 s，允许的误 差为 =0.1s。图 5 给出在不同支持度下算法的时空效率，图 5(a)的运 行时间指的是每读入一个数据流段数据，对全局 fp_list 进行更新；对前 k1 段数据的全局频繁模式树 CFP_tree 进行重构 和更新。图 5(b)所示的内存开销主要指每读入一段数据后生 成是全局 CFP_tree 所占的空间，随着数据流的不断流入，算 法所需要的时间和空间虽略有增加，但趋于稳定，适合数据 流无限性的特点。而且存储容量刚开始的几段增加得较快， 这主要是刚开始临界频繁项集增长较快，而后来经过不断地对 CFP_tree 进行排序，使得支持度较高的项距离根越近，从而使得后来的很多模式能够充分共用前缀，从而节省大量存 储空间。(a)数据处理运行时间图 3 对 CL1 窗口 CFP_tree 排序的图示2) 挖掘 B2 段的临界频繁闭合模式 B=b:3, d:3, cd:1, bad:2。3)同理 B1 段数据流步骤 2 中的 3)项操作，对排序后 CL1的 CFP_tree 更新生成 CL2 窗口 CFP_tree 的过程如图 4 所示。(b)数据处理占用内存量图 5 DSMFP_LW 算法的时间和空间效率从空间 和时 间上对 本文 所提算 法和 经典的 Lossy Counting 算法进行实验，如图 6 所示。实验结果表明算法 CFP_tree 的时间开销和内存使用比算法 Lossy Counting 更小 更稳定。所以，本文所提算法适合数据流频繁模式挖掘。30025020015010050012345 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20增长的数据流段图 4 CL2 窗口的 CFP_tree步骤 3 全局频繁模式集的输出：该过程用算法 OutPut_ FI(CFP_tree, fop_list, ms, )输出每个项集及其计数信息到频 繁模式输出表 FPop_list 中，最后以用户给定的 ms 和 输出 全局频繁项集及其计数信息B:6, A:5, C:4, D:4, BA:4, BC:3, BD:3, AC:2, A D:3, CD:2, BAC:2, BAD:3，算法结束。4性能研究和实验分析实验所使用的语言是 C+语言，编译器是 VC+6.0。实验环境是 Dell PC 机(Pentium(R) 4，CUP 2.80 GHz，384 MB内存，Windows 2003 操作系统。本文采用 IBM 生成器生成3 套数据集 T2.I6.D1M、T30.I2.D1M、T30.I20.D1M。其中，|T|表示数据集中事务的平均长度；|I|表示临界频繁项集的平 均长度；|D|表示总的事务数目，各个项集中都有 1k 个项目(a)占用内存空间比较(b)执行时间比较图 6 DSMFP_LW 算法与 Lossy Counting 算法时空效率比较(下转第 61 页)运行时间/s存储容量/KBLossy Counting算法DSFP_LW算法第 38 卷 第 1 期刘 芳：基于图和双向搜索的频繁项集挖掘算法61项集。比较 DLG 算法可知，项集5,1,3、5,1,2、5,3,2、4,1,3、4,1,2、4,3,2均可直接产生，不用再进行支持度 验证。在候选项集数量巨大时，算法的运算时间可以有效 减少。4.2 实验验证和算法分析 为了进一步验证改进算法的有效性，本文实现了 DLG 算法、GBMFS 算法和 Hybrid-DLG 算法，采用标准数据集 mushroom(http:/fimi.cs.helsinki.fi/下载)进行频繁项集挖掘实 验，该数据库共有 120 个不同的项，8 124 个事务，平均每个 事务有 23 项。表 2 给出了不同支持度下 Hybrid-DLG 算法搜索次数与 最长频繁项集维数的比较结果，从理论上讲，如果最长频繁项集的维数为 k，则 Hybrid-DLG 算法最多只需 k 次搜索就可以发现所有的频繁项集。这是由于在进行第 k 次搜索时，Lk 中所有项集的维数都为 k，如果还可以继续扩展产生频繁项 集，则必然存在维数大于 k 的频繁项集，与假设矛盾。而实 验结果表明 Hybrid-DLG 算法的扫描次数均小于 k ，说明 TFCS(k)对 Lk 的剪枝是有效的。图 2 对不同支持度下的运行 时间进行了比较。表 2 不同支持度下的搜索次数随着支持度的减小，算法的运行时间均有不同程度的增加。当支持度较大时，3 种算法的运行时间相差不大；但是，随着支持度的减小，Hybrid-DLG 算法的优势逐渐显现。这说明随着支持度的减小，频繁项集的数量和频繁项集的长度不 断增加，改进算法中对 TCFS(k)的验证步骤能够有效减少冗余候选项集的数量，提高算法的效率。5 结束语本文针对基于图的关联规则挖掘算法提出了一种改进算法。采用了双向搜索的策略，同时结合有向图的特点，更充 分地利用 Apriori 性质进行剪枝。经实验验证，改进的算法 在最小支持度阈值较小时，有效提高了算法的效率。由于该 算法中一部分频繁项集由较长的频繁项集直接产生，因此丢 失了它们的支持度信息，这在以后的工作中需要进一步研究。参考文献Agrawal R, Srikant R. Fast Algorithms for Mining AssociationRulesC/Proc. of VLDB94. Santiago, Chile: s. n., 1994: 487-499.Han Jiawei, Pei Jian, Yin Yiwen. Mining Frequent Patterns Without Candidate GenerationC/Proc. of SIGMOD00. Dallas, USA: s. n., 2000.张忠平, 李 岩, 杨 静. 基于矩阵的频繁项集挖掘算法J.计算机工程, 2009, 35(1): 84-86.Sunil J, Jain R C. A Dynamic Approach for Frequent Pattern Mining Using Transposition of DatabaseC/Proc. of the 2nd International Confere