一种实时挖掘数据流近似频繁项的算法

数据流的无限性和流动性使得传统的频繁项挖掘算法难以适用.针对数据流的特点,提出了一种实时的挖掘数据流近似频繁项的算法.在允许的偏差范围内,新算法只需扫描一次数据项,使用的存储空间远远小于数据流的规模,能动态地挖掘数据流中的所有频繁项.将数据项存储到一种新的数据结构中,利用该数据结构可以快速地删除非频繁项.最后,理论分析和实验表明这种方法的有效性.     

一种轮转的数据流频繁项挖掘算法

挖掘数据流的频繁项已受到广泛关注,研究者们提出了一些高效的数据流上挖掘频繁项的算法,尽管这些算法能够比较好地找到频繁项,但对频繁项支持度的估计往往存在较大误差.而新的算法REC(rotative efficient count) 除了能够保证频率超过一定阈值的数据项都能被找到,并且能够尽可能准确地返回其频率.分析和实验表明,相比当前最好的两种算法,REC算法空间在同样空间代价下,对数据项频率的估计更为准确,尤其在数据分布比较平缓时表现得尤为明显.     

数据流中频繁项近似挖掘算法

提出新的数据结构ESBF(Extensible and Scalable Bloom Filter)-可扩展的Bloom Filter.并提出基于ESBF的数据流中频繁项近似挖掘算法,该算法在保证较高精度的同时,实现比同类算法具有更好的时间效率且在一般情况下具更好的空间效率,并证明只需ln(-M/lnρ)·e/ε·1/(ε·M)个计数器就能保证满足用户规定的误差ε及可信度ρ要求.     

挖掘数据流近似频繁项的改进算法

数据流的无限性、连续性和速度快等特点,使得挖掘出所有准确的数据流频繁项通常是不可能的.算法的空间复杂度和时间复杂度通常是评价频繁项挖掘算法优劣的两个主要度量.通过引入局部性原理改进数据流近似频繁项的挖掘算法,该算法的空间复杂性为O（1/ε）,数据流每个数据项的最坏处理时间是O（1/ε）,其最好处理时间是O（1）,输出结果的频率值误差为∑_(i=2)^j（1-μ_i）×k_i。     

SWFPM:一种有效的数据流频繁项挖掘算法*

分析了数据流频繁项挖掘算法EC的不足之处,如不能准确地挖掘最近一段时间内数据流的频繁项。提出了一种频繁项样本特征复合四元组的数据结构来保存样本集合,在此基础上,提出了一种基于滑动窗口的数据流频繁项挖掘算法——SWFPM。该算法能准确地挖掘出该滑动窗口中的频繁项。实验数据采用IBM合成数据发生器产生的顾客购物数据和1998年世界杯官方网站的访问日志数据。实验结果表明,该算法具有很高的频繁项挖掘准确度、快速的数据处理能力。     

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

挖掘数据流的频繁项已受到广泛关注,经典的频繁项挖掘算法尽管能够比较好地找到频繁项,但对频繁项频数的估计往往存在较大误差.SRoEC(segment rotative efficient count),SReEC(segment reserve efficient count)和RFreq(reserve frequent)算法针对该问题,继承基于计数的算法思想,将计数器进行划分并定义相应的操作,以期提高频数统计准确度并减小噪音影响.实验和数据分析表明,这些算法不仅能够保证频数超过阈值的数据项都能被找到,而且大大提高了频繁项频数统计的准确性.在同样空间代价下,算法无论在模拟数据集和真实数据集实验中,都表现出较高的频数准确率、较低的频数偏差率和较高的频数保有率,尤其是数据分布较平缓时,算法优势更加明显.     

挖掘滑动窗口中的数据流频繁项算法

滑动窗口是一种对最近一段时间内的数据进行挖掘的有效的技术,本文提出一种基于滑动窗口的流数据频繁项挖掘算法.算法采用了链表队列策略大大简化了算法,提高了挖掘的效率.对于给定的阈值S、误差ε和窗口长度n,算法可以检测在窗口内频度超过Sn的数据流频繁项,且使误差在εn以内.算法的空间复杂度为O(ε-1),对每个数据项的处理和查询时间均为O(1).在此基础上,我们还将该算法进行了扩展,可以通过参数的变化得到不同的流数据频繁项挖掘算法,使得算法的时间和空间复杂度之间得到调节.通过大量的实验证明,本文算法比其它类似算法具有更好的精度以及时间和空间效率.     

数据流的频繁模式挖掘算法浅析

介绍了数据流的定义和特点及数据流频繁模式的基本概念。针对数据流的特性,讨论分析了目前国内外数据流频繁模式挖掘算法、算法特性及应用情况,最后展望了数据流频繁模式挖掘的进一步研究工作。     

数据流上的频繁闭项集挖掘算法

针对频繁闭项集挖掘算法中数据结构与处理机制复杂的问题,提出窗口快速滑动的数据流频繁闭项集挖掘算法——MFWSR。算法通过采用紧致的数据结构和简化的判断过程提高时空效率,支持响应不同用户支持度阈值的查询。实验结果表明,在保持已有算法精度的情况下,MFWSR具有更高的时空效率。     

一种高效的离线数据流频繁模式挖掘算法

数据流频繁模式挖掘是当前数据挖掘领域中的研究热点之一,数据流连续性、无序性、无界性及实时性的特点为挖掘算法在时间及空间性能方面提出了更高的要求.数据流中模式频度的震荡现象,迫使现有算法对概要数据结构频繁维护,致使其时间、空间效率均受到较大影响.构造了具备较高空间性能的概要数据结构SP-tree,同时定义了震荡性因子χ以量化震荡信息,提出了一种高效的离线数据流频繁模式挖掘算法SPDS,有效降低了数据震荡对算法性能的影响;在处理新到数据集时,算法采取分而治之的分离映射策略,进一步提升了时间效率;同时在查询结果方面提高了部分模式的计数精度.     

在线挖掘数据流闭频繁项集的高效算法

数据流闭频繁项集挖掘算法得到了广泛的研究,其中一个典型的工作就是NewMomen、算法。针对New- Moment算法存在搜索空间大而造成算法时间效率低的问题,提出了一种改进的数据流闭频繁项集挖掘算法A-Ncw- Moment。它设计了一个二进制位表示项目与扩展的频繁项目列表相结合的数据结构,来记录数据流信息及闭频繁项 集。在窗体初始阶段,首先挖掘频繁1一项集所产生的支持度为最大的最长闭频繁项集,接着提出新的“不需扩展策略” 和“向下扩展策略”来避免生成大量中间结果,快速发现其余闭频繁项集,达到极大缩小搜索空间的目的。在窗体滑动 阶段,提出“动态不频繁剪枝策略”来从已生成的闭频繁项集中快速删除非闭频繁项集,并提出“动态不搜索策略”来动 态维护所有闭频繁项集的生成,以降低闭频繁项集的维护代价,提高算法的效率。理论分析与实验结果表明,A-New- Moment算法具有较好的性能。     

数据流上近似非可导项集的挖掘算法

频繁项集是通过对大规模数据进行挖掘获取的代表数据模式的知识结构.非可导频繁项集作为频繁项集的有效压缩方式,能够高效深入地挖掘海量数据、稠密数据与数据流当中的规律.针对项集在计算界限值时代价昂贵的缺点,提出了近似可导项集的概念,并基于纵向数据格式实现了挖掘算法MANDI,能够提高支持度计算和项集间操作的速度.另外,为了满足数据流实时、快速的特点,讨论并证明了近似可导项集的增量性质,提出了可动态更新的算法UANDI.通过实验验证了两种算法的可行性和有效性.     

一种基于滑动窗口的数据流频繁闭项集挖掘算法

频繁项集挖掘是数据流挖掘中的一个热点问题.提出了一种新的数据流频繁闭项集挖掘算法MFCI-SW.首先设计了两个新的数据结构:频繁闭项集表FCIL和频繁闭合模式树MFCI-SW-Tree,在此基础上以滑动窗口中的基本窗口为更新单位,在每个基本窗口中提取出频繁闭项集的数据项,将其支持度F和窗口序列号K存到FCIL中;然后随着新基本窗口的到来,通过删除频繁闭项集表中K值最小的数据项和插入新数据项完成对FCIL的更新和MFCI-SW-Tree树的裁剪;最后在MFCI-SW-Tree中可以迅速挖掘出满足用户需要的频繁闭项集.实验结果证明了该算法在执行效率上明显优于DS-CFI算法.     

数据流中频繁闭合模式的挖掘

频繁闭合模式集可唯一确定频繁模式完全集。根据数据流的特点,提出一种挖掘频繁闭合项集的算法,该算法将数据流分段,用DSFCI_tree动态存储潜在频繁闭合项集,对每一批到来的数据流,建立局部DSFCI_tree,进而对全局DSFCI_tree进行更新并剪枝,从而有效地挖掘整个数据流中的频繁闭合模式。实验表明,该算法具有良好的时间和空间效率。     

基于矩阵的数据流Top-k频繁项集挖掘算法

传统的数据挖掘算法在挖掘频繁项集时会产生大量的冗余项集,影响挖掘效率。为此,提出一种基于矩阵的数据流Top-k频繁项集挖掘算法。引入2个0-1矩阵,即事务矩阵和二项集矩阵。采用事务矩阵表示滑动窗口模型中的事务列表,通过计算每行的支持度得到二项集矩阵。利用二项集矩阵得到候选项集,将事务矩阵中对应的行做逻辑与运算,计算出候选项集的支持度,从而得到Top-k频繁项集。把挖掘的结果存入数据字典中,当用户查询时,能够按支持度降序输出Top-k频繁项集。实验结果表明,该算法在挖掘过程中能避免冗余项集的产生,在保证正确率的前提下具有较高的时间效率。     

一种基于Chernoff Bound的数据流上近似频繁项集的挖掘方法

数据流高速、无限和动态的特点决定了必须在有限的内存中以尽快的计算速度完成流数据上的频繁项集挖掘。将数据流中的数据按照段进行划分,采用二元组列表的数据结构进行保存,提出了一种基于滑动窗口的近似频繁项集挖掘方法AFIoDS,以实时获取频繁项集集合的真子集,并引入了概率参数,利用Chernoff Bound来动态改变支持度的近似值,保证真子集中的频繁项集被限制在一定的误差范围之内。此外,为了进一步节省内存,AFIoDS采用闭合项集的形式压缩每个段中获取的频繁项集。通过在3种真实数据集上的实验表明,AFIoDS算法与现有算法相比,在精度没有下降的情况下,具有更快的处理速度,同时其存储开销大大降低。     

一种面向高速度数据流的频繁模式挖掘算法

数据流频繁模式挖掘是从实时、连续、有序的数据序列中寻找频繁模式的过程,以往的相关研究通常将该过程分为两个阶段:首先监测数据流中各模式的频率,由于数据流环境对空间与时间的限制,需要对监测模式进行剪裁,因而频率的计算和剪裁需要重复进行;当用户提交查询时,从监控的模式中筛选出满足要求的输出.现有研究都注重解决如何对观测对象进行剪裁,而事实上在计算模式频率时,数据项集中不同数据项间的组合使得频率计算非常耗时.因此,对于高速数据流,算法通常没有足够的时间来处理数据流中的每个事务,这会影响挖掘结果的正确性.针对这一问题提出了一种新的面向高速数据流的频繁模式挖掘算法Delay. 在Delay算法中将模式频率的统计延迟到第2阶段进行,第1阶段只记录"必要信息",这样大大提高了算法所能处理的数据流流动速度的上限.实验结果表明,算法在效率上优于已有算法,LossyCounting和FDPM,尤其是在处理长数据项集数据流时优势更为明显.     

一种开采频繁项目集集合的快速算法

在大的数据集合中,开采其中的频繁项目集集合是数据挖掘中极具挑战的重要任务。已经有很多高效的算法被总结了出来。本文提出了一种思想,即开采频繁项目集集合的一 个子集,我们称之为频繁无析取规则集集合,而并非开采完全的频繁项目集集合。我们证明能借助它不读取数据库而还原出频繁项目集集合的全集和它们的支持度。本文还提 提出了一个开采无析取规则集集合的算法HOPE-Ⅱ,实验结果显示了其高效性。我们将它与另一种称为频繁封闭集的精简集进行对比,几乎所有的实验结果都显示使用无析取规则集集合比使用封闭集集合来开采频繁项目集集合更有效。