基于BTA算法的数据流频繁项集挖掘

文 凯，耿小海，许萌萌

(1.重庆邮电大学 通信与信息工程学院，重庆 400065；2.重庆邮电大学 通信新技术应用研究中心，重庆 400065；3.重庆信科设计有限公司，重庆 401121)

0 引 言

数据挖掘，也可以称为数据中知识的发现，是从大量数据中挖掘有趣模式或知识的过程，大数据的发展阻碍主要是来自于数据的“流动性”和“可获取性”。大数据从之前的批处理，再到现在的实时处理，以及混合两者的处理，经过了3次技术革新[1]。随着时代在不断的进步，人工智能、模式识别中的搜索算法和建模技术也在数据流挖掘中得到很好的应用，并且吸纳了多个领域中优秀知识和思想[2]。

数据流的数据挖掘中存在着许多的机遇和挑战，这些机遇和挑战同时也给了我们研究的方向和机会，所以数据流频繁项集挖掘已成为当前数据挖掘中的一项重要任务，并随着大数据实时分析发展变得越来越重要。

在数据流处理模型中，目前使用最多的是滑动窗口模型。滑动窗口模型自引入以来就得到广泛应用，SA-Mi-ner[3]、SYSTree[4]、FTK算法[5]采用滑动窗口模型。WOB点阵算法[6]同样也是采用的滑动窗口模型，并且该算法巧妙使用点阵技术可以避免反复重建整个树机构。

近年来孙杜靖等基于FP-tree的结构提出了面向数据流DPFP-Stream[7]算法的设计与实现；国内茹蓓等提出的数据流完全频繁项集挖掘算法[8]采用GroupTree算法挖掘频繁项集；HUISW算法[9]是一种不生成候选项集的算法挖掘频繁项集；而寇香霞等提出的FIUT-Stream算法[10]，用位图压缩数据流，空间效率得到提高。

现在的应用不仅仅是在数据流中挖掘频繁模式，数据流中非频繁模式的挖掘也进入我们视线之中。Hemalatha等[11]提出的MIP-DS方法是一种基于最小非频繁模式的数据流孤立点检测方法；Cagliero等[12]通过提出的算法对不确定数据流汇总的非频繁权重模式进行挖掘。

针对现有数据流频繁项集挖掘算法时间消耗长、空间消耗大等问题，本文对FIUT-Stream算法进行改进。首先采用取余进行窗口更新，然后挖掘频繁项集时采用与操作，最后在支持度更新简单的数学运算即可。实验结果表明，本文改进算法相较于FIUT-Stream算法在时间和空间效率有明显提升。

1 相关知识

定义1 设项目集合I={I1,I2,I3,…，Im}，则该项集中的每一个元素称为项，任何一个项集都是由I中的若干元素组成，包含k个元素的称为k-项集。

定义2 数据流DS是由接连不断到达的事务数据组成的有顺序的序列DS={T1,T2,…}。其中Ti(i=1, 2, 3,…)称为事务，同时，对于数据流中的每个事务Ti都是I中项的集合，即满足Ti⊆I。

定义3 用户设定最小支持度阈值为minsup，倘若项集X出现的频率即sup(X)≥minsup，则称项集X为频繁项集。

定义4 将数据流按w大小等分成若干块，每一块对应一个基本窗口，每一个基本窗口有相同的事物数，这些事物数个数|w|即为基本窗口的大小。

2 频繁项集挖掘

2.1 窗口更新

FIUT-Stream算法采用滑动窗口模型在数据流中挖掘频繁项集。该算法将数据流压缩到位表，即FIUT结构；在得到FIUT结构后以滑动窗口的形式进行数据更新，然后对FIUT结构位表里的数据进行聚类得到所有k-itemsets，再根据k-itemsets构建FIU-tree，最后在FIU-tree中挖掘出所有频繁项集。

相较于其它的算法，FIUT-Stream算法采用位表压缩数据，极大减少了内存消耗，提高了空间效率；但是该算法在构建FIUT结构时使用两个表格，这在处理大量数据的时候内存消耗还是极大，而且在使用FIU-tree挖掘频繁项集的时候有大量的候选项集的产生，使得挖掘效率不高；在有新的数据流到来时，支持度的更新需要对所有的数据进行重新计算，极大地消耗时间。

本文提出的改进算法只需要构建一个位表来进行数据的压缩，而且采用数学的求与运算直接进行频繁项集的挖掘，在支持度计算采用简单的加减运算即可完成，减少了聚类和构建FIU-tree的消耗，在挖掘效率上面有极大的提升。具体思路如下：

表1是本文所用到的数据流，将其分为了4个簇，每一簇包含3个事物，在FIUT-Stream算法中，随着数据流的流动，按表格的方向进行流动，新簇流入，旧簇流出。

表1 数据集

表2为表1前3个盘压缩后的数据集，每一次对3个簇进行挖掘，每个簇包含3个事物，其将数据集压缩存入一个位表里面，这样在进行频繁项集挖掘的时候的效率可以得到提高。另外，每一个簇的最下面一行计算每一簇的每一项的支持度计数，表格最后一行计算所有项的支持度计数，见表2。

FIUT-Stream算法在有新的数据到来的时候，是采用滑动窗口的形式，而本文采用文献[13]取余的方式进行事物更新，当滑动窗口中数据已满，新来的事物Ti，采用i%n将其插入到窗口中覆盖原来旧数据进行数据更新。采用这种方式在有新的数据到来时不需要对所有窗口中所有的数据进行滑动，只需要对需要更新的窗口中的数据覆盖，这对海量数据的更新可以极大提高效率，复杂度从O(m)降到了O(1)，使得挖掘效率得到极大的提升。表3是使用取余的方式将BW4中的数据更新得到的更新表。

2.2 支持度更新

在更新一个BW之后，根据这个BW的支持度计数就可以对更新后的所有项的支持度进行计算，表3是将BW4的数据更新插入BW1。如求a项的支持度时，利用新得到的支持度计算旧的支持度，即3-2=1，1+7=8得到更新后的a项的支持度为8，以此方法就能得到更新后的所有项的支持度，见表3。

表2 压缩位

表3 更新的数据流压缩位

2.3 频繁项集挖掘

在经过一次扫描数据后，就可以得到表3，然后根据最后一行的支持度删除掉非频繁1-项集，得到所有的频繁1-项集。设定最小支持度为4，根据表3得到所有频繁1-项集分别为：a、b、d、f。得到如表4所示数据，利用超集检测减少频繁项集挖掘的项数，使挖掘效率变高。

表4 删除非频繁1-项集的压缩位

接下来就是进行频繁k-项集(k≥2)的挖掘。在挖掘频繁k-项集的时候，本文采用的是数学中的求与操作进行频繁项集的挖掘：如在挖掘频繁2-项集的时候，我们只需要将要求的两项所在的列之间进行与，与之后得到1的个数，即为该项集的支持度计数，代表这两项在同一事物中出现。

算法1：挖掘k频繁项集(k≥2)

输入：删除非频繁1-项集和支持度计数的压缩位表D

输出：所有频繁项集

for(i = 1; i

for(j = i+1; j

s = 0;

//在k值变化的时候， 这里也要进行相关变化

for(h = 1; h

铝是目前应用最广的轻质材料，其密度大约是钢铁的1/3.目前，以铝代钢是轻量化技术的一个发展趋势，铝合金的导热率、吸收碰撞性、耐腐蚀性、加工性能都优于钢铁材料.经过技术的改进，提高了铝材的强度，完全可以满足轻量化要求.同时，研究表明，每千克铝合金可以比高强度钢、钢铁、低碳钢减少13～20 kg 温室气体的排放[24].因此自20世纪70年代开始，铝合金的地位逐渐上升，成为汽车轻量化首选材料.我国也着手将铝合金应用于汽车，长安汽车集团与国家轻量化技术创新战略联盟携手研发了“以铝代钢”的引擎盖，同时，用铝做车头结构的高端车也在被各高端汽车企业所采用[25].

t = D[h][i]*D[h][j];

s+= t;

}

if (s≥minsup){

记录频繁k-项集D[1][i]、D[1][j],…

}

}

}

图1是频繁项集挖掘算法流程。

图1 频繁项集挖掘算法流程

经过以上几个步骤，就可以从数据流中挖掘出所有的频繁项集。该算法的改进在很大程度上提升了FIUT-Stream算法的时间和空间效率。在FIUT结构创建之后，不需要多余创建FIU-tree结构，频繁项集的挖掘直接用位列表进行数学中的与操作就可以挖掘出所有的频繁项集，在支持度更新计算采用简单的加减运算。既减少了构建FIU-tree的空间内存消耗，也通过与操作和新的支持度更新方式提高了时间的效率。

这种高效率的数据流频繁项集挖掘方式在恐怖分子搜查方面可以得到很好应用，在人流中搜寻频繁在一个地方出现的人可以给予很大的怀疑，这可以给警方破案提供很大的帮助；另外，用户在网上浏览新闻、网上购物以及查看股票的变化趋势，都可以通过实时进行分析，给用户进行个性化的推荐，或者给用户做出一些指导，随着信息化社会的发展，这方面的应用也变得越来越广泛。

3 实验结果分析

实验所需要的程序采用的是Java进行编写，实验环境为Intel(R) Core(TM) i5-2400 CPU @ 3.1 GHz，4 GB内存，64位Windows 10操作系统。为了更好体现算法的普遍性，本次实验采用了相对稀疏数据集T40I10D100K和相对稠密数据集connect-4这两个数据集。其中相对稀疏数据集包含了100 000个事物和942个项；而相对稠密数据集包含了67 557个事物，129个项。为了比较真实使实验环境为数据流，先是按时间顺序使用一个线程从数据集中获取基本窗口长的数据，然后依次将数据传送给负责挖掘的线程，这时负责挖掘的线程就具备了时间连续到达的特征。

首先比较了GroupTree算法、FIUT-Stream算法和改进算法BTA在稀疏数据集T40I10D100K和稠密数据集connect-4中的时间开销。在稀疏数据集T40I10D100K的实验中，设定滑动窗口大小为4，支持度分别为(10, 15, 20, 25)；对于稠密数据集connect-4，设定滑动窗口大小2，支持度分别为(85, 88, 91, 94, 97)，得到图2、图3的时间消耗对比。

图2 在数据集T40I10D100K下时间消耗对比

图3 在数据集connect-4下时间消耗对比

由图2、图3可以看出，在较高和较低支持度情况下，BAT算法的时间开销都要比FIUT-Stream算法和GroupTree算法小，在支持度越低效果越明显，随着支持度降低差距越来越大。因为改进算法减少了构建FIU-tree和GroupTree的时间开销，所以在时间效率上比较优越，并且是随着支持度越低的效果越明显。

在考虑完时间开销之后，接下考虑空间开销。设panes=10 K事物，在稀疏数据集T40I10D100K的时候，滑动窗口大小设定分别为3，5，7，9。在稠密数据集connect-4中，设定滑动窗口大小分别为2，3，4，5，实验对比结果如图4、图5所示。

图4 在数据集T40I10D100K下的内存消耗

图5 在数据集connect-4下的内存消耗

由图4、图5可以看出，在稀疏数据集和稠密数据集中，随着Pane数的增加，BTA算法在内存消耗上面都低于FIUT-Stream算法和GroupTree算法，因为FIUT-Stream算法在Pane数越来越多的情况下需要构建的表格消耗内存越来越大，并且在挖掘频繁项集的时候候选项集会越来越多，而GroupTree算法对GroupTree结构构建越来越多，所以随着Pane数的增加，BTA算法的空间优越性越来越明显。

4 结束语

本文针对FIUT-Stream算法在时间、空间效率不高等问题，提出了一种改进算法，改进算法同FIUT-Stream算法一样将数据压缩在位表结构中，但是改进算法只需要构建一个表格即可，然后通过将数据流分成等长的思想来准确挖掘数据流中的频繁项集，而且在滑动窗口更新采用的是取余操作进行数据更新，提升了时间效率。另外，在频繁项集挖掘采用的求与操作，减少了FIUT-Stream算法的构建FIU-tree的开销和候选项集产生的开销，在时间和空间效率都得到一定的提升。最后在进行支持度的更新时，分块计算支持度计数，然后通过数学运算进行支持度更新，只需要小范围计算支持度，进一步提高时间效率。