基于定量更新滑动窗口频繁闭项集挖掘算法研究

采用定量更新滑动窗口策略挖掘数据流频繁闭项集,提出TW-CFI(Time Windwos-Closed Frequent Itemsets)算法更好的解决了数据流频繁模式挖掘问题,挖掘过程中采用一种CFIT(Closed Frequent Itemsets Tree)存储结构,不仅包含当前数据流中的频繁闭项集,还通过时间窗口保存频繁闭项集的历史频繁计数.     

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

NewMoment算法在数据挖掘过程中频繁地进行左检测操作,导致算法运行效率低下.针对该问题,提出一种改进的数据流频繁闭项集挖掘算法——LevelMoment.在该算法中,给出一种新的加入层次节点的数据结构LevelCET,在此结构上通过层次检测策略与最佳频繁闭项集检测策略,快速地挖掘数据流滑动窗口中的所有频繁闭项集....     

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

为提高数据流频繁闭项集的查找效率,提出一种改进的NewMoment频繁闭项集挖掘算法,通过在LevelCET数据结构中加入层次结点,并利用层次检测策略与最佳频繁闭项集检测策略快速挖掘数据流滑动窗口中所有的频繁闭项集。实验结果证明,与NewMoment算法相比,改进的算法性能更优。     

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

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

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

数据流的流动性与连续性,使得数据流所蕴含的知识会随着时间的推移而发生变化。挖掘数据流中的频繁项集是一项意义重大且具有挑战性的工作。提出一种基于滑动窗口数据流的频繁项集挖掘——FIUT-Stream算法,FIUT-Stream算法分块挖掘数据流,在内存中维持一个滑动窗口数据的概要结构,随着窗口滑动动态更新该存储结构,利用FIUT算法进行频繁项集挖掘。实验表明,该算法能节省内存空间、精确获得频繁项集。     

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

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

挖掘数据流滑动时间窗口内Top-K频繁模式

由于数据流滑动时间窗口中流数据包含模式的支持度是动态变化的,很难给出一个合适的支持度门限来挖掘数据流滑动时间窗口内的频繁模式.在研究数据流滑动时间窗口内流数据变化特点的基础上,论文提出了一种挖掘数据流滑动时间窗口内Top-k频繁模式的方法,该方法能够在保证模式挖掘误差基础上快速删除窗口内不频繁模式信息,保留重要的模式信息,并能按照支持度降序输出Top-k频繁模式.仿真实验结果表明,该算法具有较好的效率和正确性,并优于其它同类算法.     

数据流中基于事务链表组的频繁闭项集挖掘

挖掘频繁项集是挖掘数据流的基本任务.许多近似算法能够对数据流进行频繁项集的挖掘,但不能有效控制内存资源消耗和挖掘运行时间.为了提高数据流挖掘的效率,通过挖掘数据流中的频繁闭项集来减少挖掘结果项集的数量,并借鉴Relim算法和Manku算法,引入事务链表组作为概要数据结构,提出了一种新的数据流频繁闭项集的挖掘算法.最后通过实验,证明了该算法的有效性.     

一种基于变尺度滑动窗口的数据流频繁集挖掘算法

基干传统滑动窗口机制的数据流频繁集挖掘算法较多地考虑快速且精确的效果,而较少考虑数据流的时变特性,对传统的滑动窗口机制进行改进.同时考虑数据流的海量特性和时变特性,提出一种基于变尺度滑动窗口机制的数据流频繁集挖掘算法V-Stream.该算法采用事务链表组的概要数据结构.能够根据数据流的数据分布变化自适应调整窗口大小.Eclipse上的仿真实验结果表明,V-Stream相比Manku算法提高了挖掘数据流频繁集的时间与空间效率.     

基于滑动窗口的不确定性数据流频繁项集挖掘算法

为了提高频繁项集挖掘算法的准确性,在不确定性数据流频繁项集挖掘算法SRUF-mine的基础上引入最大可能误差,提出一种基于滑动窗口的false-positive挖掘算法UFIM。UFIM算法对数据流进行分块处理,在内存中维护一个存储滑动窗口内频繁项集的概要数据结构,随着窗口的滑动对该概要结构进行增量更新。实验表明,与SRUF-mine相比,UFIM算法能获得较高的频繁项集挖掘的准确性。     

基于滑动窗口的数据流闭合频繁模式的挖掘

频繁闭合模式集惟一确定频繁模式完全集并且数量小得多,然而,如何挖掘滑动窗口中的频繁闭合模式集是一个很大的挑战．根据数据流的特点,提出了一种发现滑动窗口中频繁闭合模式的新方法DS_CFI．DS_CFI算法将滑动窗口分割为若干个基本窗口,以基本窗口为更新单位。利用已有的频繁闭合模式挖掘算法计算每个基本窗口的潜在频繁闭合项集,将它们及其子集存储到一种新的数据结构DSCFI_tree中,DSCFI_tree能够增量更新,利用DSCFI_tree可以快速地挖掘滑动窗口中的所有频繁闭合模式．最后,通过实验验证了这种方法的有效性．     

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

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

滑动窗口中数据流频繁项集挖掘方法

根据数据流的流动性与连续性,提出了一种滑动窗口中频繁项集挖掘算法NSW,满足了人们快速获取最近到达数据中频繁项集的需求。该算法采用二进制矩阵表示滑动窗口中的事务列表,通过直接删除最老事务、不产生候选项集等方法控制时间和空间的开销。实验表明,该算法具有较好的时间和空间效率。     

对数据流频繁项集挖掘算法WSW-Imp的改进

近年来随着新的应用的出现,比如网络流量分析、在线事物分析和网络欺诈检测等,对数据流的挖掘成了一个越来越重要的课题。对于数据流频繁项集的挖掘,目前绝大部分的研究都集中在传统的窗口模式下进行,即时间衰退窗口模式、界标窗口模式和滑动窗口模式。Pauray S.M.Tsai于2009年提出了一种新的窗口模式：加权滑动窗口模式,并设计了两个基于此窗口模式的数据流频繁项集挖掘算法WSW和WSW-Imp,其中WSW-Imp是对WSW算法的改进。在研究了加权滑动窗口模式以及WSW-Imp算法的基础上,对WSW-Imp算法作了进一步的改进,设计了算法WSW-Imp2,并从理论上证明了WSW-Imp2算法比WSW-Imp算法更高效,实验结果也表明了这一点。     

数据流最大频繁项挖掘方法

提出基于事务矩阵挖掘最大频繁项集的方法AFMI,该方法采取迭代精简事务矩阵的方式求解所有事务中的最大频繁项集,从精简后的事务向量交集的子集中搜索最大频繁项集,并运用逻辑运算和剪枝方法提高挖掘效率。基于AFMI方法,研究挖掘滑动窗口数据流最大频繁项集算法AFMI+,该算法可使用户周期性地挖掘当前窗口中的最大频繁项集。实验结果表明,AFMI和AFMI+算法均具有较好的性能。     

改进的多数据流协同频繁项集挖掘算法

针对已有的多数据流协同频繁项集挖掘算法存在内存占用率高以及发现频繁项集效率低的问题,提出了改进的多数据流协同频繁项集挖掘（MCMD-Stream）算法。首先,该算法利用单遍扫描数据库的字节序列滑动窗口挖掘算法发现数据流中的潜在频繁项集和频繁项集;其次,构建类似频繁模式树（FP-Tree）的压缩频繁模式树（CP-Tree）存储已发现的潜在频繁项集和频繁项集,同时更新CP-Tree树中每个节点生成的对数倾斜时间表中的频繁项计数;最后,通过汇总分析得出在多条数据流中多次出现的且有价值的频繁项集,即协同频繁项集。相比A-Stream和H-Stream算法,MCMD-Stream算法不仅能够提高多数据流中协同频繁项集挖掘的效率,并且还降低了内存空间的使用率。实验结果表明MCMD-Stream算法能够有效地应用于多数据流的协同频繁项集挖掘。     

窗口模式下在线数据流中频繁项集的挖掘*

拟采用一种基于滑动窗模式的单遍挖掘算法,专注于处理近期数据;为了减少处理时间和占用的内存,设计了一种新的事务表示方法。通过处理这个事务的表达式,频繁项集可以被高效输出,并解决了使用基于Apriori理论的算法时,由候选频繁1-项集生成频繁2-项集时数据项顺序判断不准确问题。该算法称为MRFI-SW算法。     

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

用挖掘频繁闭合模式集代替挖掘频繁模式集是近年来提出的一个重要策略。根据数据流的特点,提出了一种基于滑动窗口的频繁闭合模式的新方法DSFC_Mine。该算法以滑动窗口中的基本窗口为更新单位,利用改进的CHARM算法计算每个基本窗口的潜在频繁闭合项集,将它们存储到一种新的数据结构中,利用该数据结构可以快速地挖掘滑动窗口中的所有频繁闭合项集。实验验证了该算法在时间上和空间上的可行性和有效性。     

在线挖掘数据流闭合频繁项集CMNL-SW算法

提出了一种新的CMNL-SW(Closed map and num list-sliding window)挖掘算法。具体使用数据结构Closedmap存储挖掘到的闭合项集和Num list存储所有不同项的序号,通过对添加新事务和删除旧事务包含的项序号进行简单的并集和该事务与之相关已经挖掘到的闭合项集进行交集运算来更新当前滑动窗口,使之能够根据用户任意指定的支持度阈值在线输出数据流上闭合频繁项集信息。通过理论分析和对真实数据集Mushroom,Retail-chain和人工合成数据集T40I10D100K的挖掘结果表明,提出的算法在时空效率上明显优于同类经典算法Moment和CFI-Stream,并且随着数据流上处理事务数的递增和快速改变表现出良好的稳定性。