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

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

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

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

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

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

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

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

滑动窗口中数据流最大频繁项集挖掘算法研究

数据流最大频繁项集的项集数目相对很少并且已隐含所有的频繁项集,所以数据流中最大频繁项集的挖掘具有很好的时空效率并且有很大的意义,也受到了业界更多的关注。针对数据流最大频繁项集的挖掘,提出了在滑动窗口中基于矩阵的数据流最大频繁项集挖掘方法SWM-MFI,主要采用两个矩阵来存储数据信息：一个矩阵是事务矩阵,存储事务数据;一个矩阵是二项集矩阵,存放频繁2-项集。通过二项集矩阵扩展得到频繁k-项集,基于SWM-MFI算法挖掘出最大频繁项集。经过理论和实验证明该算法具有很好的时效性。     

改进的多维关联规则算法研究及应用

关联规则是数据挖掘研究中最主要、最活跃的领域之一。以Apriori算法为前提,借助Apri-oriTid算法事务压缩的思想,减少了重复扫描数据库的时间;并提出了一种利用事务标识列表,该列表长度即是对应候选项集的支持度计数,在计算支持度计数时,仅需要得到对应列表长度即可,从而缩短了计算计数时的比较时间;同时,在生成频繁项集时引入地址索引机制,在剪枝过程中,利用候选项集的首元素在地址索引表中快速定位,减少了多次扫描事务数据库,有效地缩短了计数时间和占用的内存空间。利用改进的算法对科研管理系统数据进行关联关系分析,从中萃取数据中隐含的、有价值的信息,辅助下一阶段的科研管理工作。并通过试验进行性能比较得出,改进后的算法效率更高。     

TWCT-Stream:数据流上的频繁模式挖掘算法

提出一种结合倾斜时间窗的TWCT树结构,可以保存不同时间粒度下频繁模式的完全集,并设计了其顺序更新和删除算法,使其能够存储在外存,从而有效地降低算法的内存空间需求。结合TWCT树结构特点,提出了数据流上的频繁模式挖掘算法TWCT-Stream,其模式生长的TWCT-Growth算法按字典顺序生成频繁模式,以配合TWCT结构的顺序更新。实验证实算法的内存需求低于FP-Stream等同类算法。     

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

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

关联规则挖掘中对Apriori算法的研究

针对Apriori寻找频繁项集问题,提出了基于垂直事务列表的树形结构的挖掘算法。该算法结合项集的有序特性,使生成树的每一层结点从左往右按支持度大小升序排列,这样得到的候选频繁项集的集合是最小的,大大减少了候选频繁项集的数量,而且能保持频繁项集的完整性,从而节约了计算开销,提高了算法的效率。     

位序互补的空间关联规则挖掘算法

为有效地提高基于空间事务的挖掘算法效率,提出一种基于位序的互补空间挖掘算法,其适合在海量数据中挖掘任何长度的频繁项;该算法用定序项目集的方法来减少现有算法存在的冗余判断操作和计算,同时也用非频繁项目集的补集来快速生成候选项,删除了现有双向挖掘算法中的空闲操作,可以有效地降低算法的运行时间。实验结果表明此法在空间数据挖掘中比现有算法更快速而有效。     

压缩UF-tree挖掘不确定数据频繁项

针对UF-growth算法构造大量树节点和分支的局限性, 且不断计算候选数据项支持度的不足, 提出压缩UF-tree算法。压缩UF-tree算法改变建树条件：事务中数据项与树中某个分支节点的数据项匹配时, 将该数据项合并到分支中; 否则, 从该分支节点创建新的分支, 叶节点保存当前事务编号。构建单项数据项的概率向量, 搜索树分支产生候选项, 通过事务编号和概率向量计算候选数据项的支持度进而挖掘频繁项。通过实验对比与分析, 压缩UF-tree算法可行且更高效。     

基于概率衰减窗口模型的不确定数据流频繁模式挖掘

考虑到不确定数据流的不确定性,设计了一种新的概率频繁模式树PFP-tree和基于该树的概率频繁模式挖掘方法PFP-growth.PFP-growth使用事务性不确定数据流及概率衰减窗口模型,通过计算各概率数据项的期望支持度以发现概率频繁模式,其主要特点有:考虑到窗口内不同时间到达数据项的贡献度不同,采用概率衰减窗口模型计算期望支持度,以提高模式挖掘准确度;设置数据项索引表和事务索引表,以加快频繁模式树检索速度;通过剪枝删除不可能成为频繁模式的结点,以降低模式树的存储及检索开销;对每个结点都设立一个事务概率信息链表,以支持数据项在不同事务中具有不同概率的情形.实验结果表明,PFP-growth在保证挖掘模式准确度的前提下,在处理时间和内存空间等方面都具有较好的性能.     

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

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

基于链表数组的最大频繁项集挖掘算法

挖掘密集型数据集的全部频繁项集代价高昂,针对该问题,提出一种数据结构链表数组和基于链表数组的最大频繁项集快速生成算法。该方法使用链表数组为每个项目建立事务链表,并且链表的创建过程只需扫描数据库1次。使用深度优先搜索得到所有候选最大频繁项集,利用约束条件缩小搜索空间。使用标准数据集进行验证测试并与其他算法进行比较,实验结果表明,该算法具有较快的挖掘速度。     

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

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

一种基于Spark框架的并行FP-Growth挖掘算法

Apriori和FP-Growth算法是频繁模式挖掘中的经典算法,由于Apriori存在更多缺陷,因此FP-Growth是单机计算环境下比较高效的算法。然而,对于非并行计算在大数据时代遇到的瓶颈,提出一种基于事务中项间联通权重矩阵的负载平衡并行频繁模式增长算法CWBPFP。算法在Spark框架上实现并行计算,数据分组时利用负载均衡策略,存入分组的数据是相应频繁项的编码。每个工作节点将分组数据中每一个事物中项的联通信息存入一个下三角联通权重矩阵中,使用被约束子树来加快每个工作节点挖掘频繁模式时创建条件FP-tree的速度,再用联通权重矩阵避免每次挖掘分组中频繁模式时对条件模式基的第一次扫描。由于联通权重矩阵和被约束子树的结合应用于每一个工作节点的FP-tree挖掘过程,因此提升了并行挖掘FP-tree性能。通过实验表明,所提出的并行算法对大的数据有较高性能和可扩展性。     

基于Spark框架的FP-Growth大数据频繁项集挖掘算法

针对大数据中的频繁项集挖掘问题,提出一种基于Spark框架的FP-Growth频繁项集并行挖掘算法。首先,根据垂直布局思想将数据按照事务标识符垂直排列,以此解决扫描整个数据集的缺陷。然后,通过FP-Growth算法构建频繁模式树,并生成频繁1-项集。接着,通过扫描垂直数据集来计算项集的支持度,从而识别出非频繁项,并将其从数据集中删除以降低数据尺寸。最后,通过迭代过程来生成频繁 -项集。在标准数据集上的实验结果表明,该算法能够有效挖掘出频繁项集,在执行时间方面具有很大的优越性。