基于数据流的频繁闭项集挖掘

关联规则挖掘是数据挖掘的一项重要技术,它主要是通过频繁闭项集挖掘得到关联规则。因此,频繁项集挖掘算法的性能对关联规则挖掘算法起到了决定性的作用。基于数据流的频繁闭项集挖掘能针对数据流有效地挖掘频繁闭项集,本文主要分析基于数据流的频繁闭项集挖掘算法及其在关联规则挖掘中的应用。     

基于FP树的最大频繁项集挖掘

频繁项集的挖掘是数据挖掘中的一个基础和核心问题,具有广泛的应用领域。而频繁项集挖掘可分为完全频繁项集挖掘、频繁闭项集挖掘和最大频繁项集挖掘三类,其中,最大频繁项集的数目最少。频繁项集的挖掘是一个搜索问题,剪枝优化技术是提高频繁项集挖掘效率的一个重要手段。对于最大频繁项集的挖掘可以从宽度优先和深度优先两个角度来考虑,而基于FP树的深度优先算法比宽度优先算法扫描数据集的次数要少很多,因此,具有较好的性能。本文主要分析宽度优先的最大频繁项集挖掘算法和基于FP树的深度优先最大频繁项集挖掘算法。     

基于图论的频繁闭项集挖掘

利用了有向项集图来存储事务数据库中有关频繁项集的信息,提出了有向项集图的三叉链表式存储结构和基于有向项集图的频繁闭项集挖掘算法。不仅实现了事务数据库的一次扫描,减少了I/O代价,而且提高了数据结构的存储空间效率和频繁闭项集挖掘算法的执行时间效率。     

基于矩阵的数据流频繁模式预测算法

随着数据挖掘的广泛应用,许多实际的数据挖掘应用需要用过去和当前数据对未来数据状态进行预测,针对这一现状,文中提出基于矩阵的数据流频繁模式预测算法（MFP）.MFP算法可预测在下一时间窗口中可能性较大的频繁项集,以满足用户需要.该算法首先将数据转换为0-1矩阵;然后通过矩阵剪裁和位运算更新矩阵,并从中挖掘频繁项集;最后,利用当前窗口数据预测下一时间窗口中可能出现的频繁项集.实验结果表明,MFP算法在不同实验环境下能有效预测频繁项集,该算法是可行的.     

基于渐增最小支持度函数的数据流频繁项挖掘

目前数据流频繁项近似挖掘算法大多采用误差参数控制挖掘的结果,时间与内存开销越高,挖掘结果的正确性越低.针对这样一个问题,提出了渐增最小支持度函数作为误差参数.如果某数据项在滑动窗口中的保存时间越长,则该数据项的出现频率必须相应的增加才能继续保存在滑动窗口中.这样,在滑动窗口中需要保存的数据项的数量将减少,时间开销与内存开销也相应的减少.在此基础上,提出了一种基于渐增最小支持度函数的数据流频繁项挖掘算法GFFPM.该算法能准确的挖掘出滑动窗口中的频繁项.实验结果表明,该算法具有很高的正确性.     

频繁项集快速挖掘及更新算法

为了克服Apriori发现频繁项集存在的问题,提出了一种基于三维项集矩阵和向量(TIMV)的频繁项集挖掘算法.该算法摆脱了Apriori框架的束缚,仅需扫描数据库一次,不产生候选项目集.当事务数据库和最小支持度发生变化时,该算法只需重新遍历一次项集矩阵,即可得到新的频繁项集.实验结果表明,算法能有效提高频繁项目集的挖掘和更新效率.     

逆向索引FP-tree挖掘频繁项集

在对逆向FP-tree的研究基础上提出了逆向索引FP-tree挖掘频繁项集的算法。该算法构造了逆向索引FP-tree,通过寻找扩展频繁项集与合并第一棵子树的方法挖掘频繁项集,给出了逆向索引FP-tree的性质和挖掘算法。     

在流滑动窗体上挖掘Top-K高效用项集的有效算法

数据流上的频繁项集挖掘是数据挖掘的一个重要话题,并在现实生活中应用广泛.可是这个问题存在两个限制:(1)项在数据流中的权重没有被考虑;(2)项在每条事务中的数量没有被考虑.因此,研究人员提出了"数据流上的高效用项集挖掘"的研究问题.在这一问题中,项的权重及项在事务中的数量被考虑,数据流上的高效用项集挖掘是指在数据流中挖掘所有效用值不小于用户指定最小效用阈值的项集.对用户而言,由于不了解数据流中数据的统计特性,很难设置一个合适的最小效用阈值,如果最小效用阈值设置过高,则挖掘算法返回高效用项集的数量过少,使得用户无法准确分析;如果最小效用阈值设置过低,则挖掘算法返回太多的高效用项集,使得用户需要对结果集二次分析,为此研究人员提出了"数据流上的Top-K高效用项集挖掘"的研究问题.数据流上的Top-K高效用项集挖掘是指在数据流中寻找前k个具有最高效用值的项集,通过设置k值取代最小效用阈值,可有效地控制算法的输出规模,对用户而言更直观.与静态数据相比,数据流具有如下特点:快速的数据到达速率、数据流的尺寸未知和不能访问以前到达数据的特点,因此很难将整个数据流放入内存中处理,通常研究人员采用流滑动窗体模型.流滑动窗体是由固定数量的、最近到达的批数据组成,每个批数据包含一组事务集.现有的挖掘流滑动窗体上Top-K高效用项集的研究方法通常包含两个阶段:(1)采用高估技术高估项集在流滑动窗体中的效用,将高估效用不小于由阈值提升技术获得的最小效用阈值的项集选定为Top-K高效用项集候选项集;(2)通过扫描流滑动窗体内的批数据,计算第一阶段生成的候选项集的真实效用.可是,这个方法存在两个问题:(1)第一阶段生成的候选项集通常数量巨大,需要大量的存储空间;(2)计算第一阶段生成的候选项集的真实效用是非常耗时的.因此,本文提出一个在挖掘过程中不生成候选项集的流滑动窗体上Top-K高效用项集挖掘算法TK-HIS,TK-HIS采用提出的HUIL-Tree和效用数据库存储流滑动窗体中的项集及其在窗体事务中的效用,在HUIL-Tree和效用数据库的构建过程中提出两个阈值提升策略提升初始值为0的最小效用阈值,在挖掘过程中TK-HIS维护前k个具有最高效用值的项集,使用模式增长的方法生成搜索空间中的项集,对每一个项集通过效用数据库直接计算其在流滑动窗体中的效用.研究在稀疏数据流上进行了大量的实验评估TK-HIS的性能,并与当前最好的流滑动窗体Top-K高效用项集挖掘算法T-HUDS进行比较,实验结果表明在稀疏数据流上TK-HIS显著优于T-HUDS:运行时间最快可提升一个数量级.     

一种基于滑动窗口模型的数据流加权频繁模式挖掘方法

相对于传统的频繁模式挖掘,加权频繁模式挖掘能发现更有价值的模式信息.针对数据流中的数据只能一次扫描,本文提出了一种基于滑动窗口模型的数据流加权频繁模式挖掘方法WFP-SW(Sliding Window based Weighted Frequent Pattern minig),算法采用WE-tree(Weighted Enumeration Tree)存储模式和事务信息,利用虚权支持度维持模式的向下闭合特性,同时获取临界频繁模式.对临界频繁模式进一步计算其加权支持度获取加权频繁模式,使得计算更新模式更加便捷.实验结果显示算法具有较高的挖掘效率并且所需的内存更少.     

加权频繁项集挖掘算法在超市商品捆绑销售中的应用

引入一种新的加权关联规则支持度和置信度的计算方法,并利用矩阵的存储结构提出一种新的加权关联规则挖掘算法,从而改进了加权频繁项集的挖掘效率.该算法在Apriori算法的基础上,对数据库仅需扫描一次,能很快地计算项集的支持度,大大减少了I/O次数,有效提高了加权频繁项集的生成效率.通过应用于超市捆绑销售,证明了该算法能有效地提取商品间的关联信息,有助于商品的销售.     

数据流中的频繁项集挖掘

频繁模式挖掘是数据挖掘的精髓,并且在上个世纪被广泛研究.概述了数据流频繁模式挖掘的技术发展水平和发展背景.然后给出一些概念定义,就目前经典的数据流频繁模式算法作了分析,并在此基础上总结了前人的方法理论,采用混合的方法,扩展了新的算法——FLY.最后,总结分析新的算法,并与前人算法在内存消耗和准确性方面进行了比较.     

加权最大频繁项目集挖掘算法

关联规则是数据挖掘领域的一个重要分支,而发现最大频繁项目集是关联规则挖掘中的重要问题.最大频繁项目集挖掘是在数据库中各属性之间是平等的情况下进行的,但现实中并非如此.频繁模式树(Frequent Pattern Tree,FP-Tree)已不能满足要求.为此提出了一个有效的基于加权FP-Tree的加权最大频繁项目集挖掘算法,其挖掘过程中不需要产生候选项目集.并通过实例说明了此算法的挖掘过程.实验结果表明此算法是有效的并且有较好的扩展性.     

快速挖掘最大频繁项集

提出了一种基于布尔矩阵的最大频繁项集挖掘算法，通过将FP-tree映射成布尔矩阵和权值表，运用布尔逻辑运算进行矩阵投影操作得到最大频繁项集，算法在挖掘过程中不用生成最大频繁候选项集，从而大大提高了算法的时间效率和空间可伸缩性。     

基于层次的最大频繁项集挖掘算法

关联规则的研究是数据挖掘中的重要问题,如何高效地发现频繁项集是关联规则研究中的关键问题。根据数据库事务的统计性规律,在最大频繁项集发现算法Apriori及其变种算法的基础上,提出一种新的基于层次的最大频繁项集的发现算法。首先从整体上判断候选集的频繁性,然后在发现最大频繁项集的过程中,通过引入整体性策略、排序策略、最小策略有效地减少了候选集与数据库事务之间的比较次数。实验结果表明,采用该算法处理数据库事务数量大的最大频繁项集的发现任务．其效率相比Aoriori算法有显著的提高。     

一种基于极大完全子图的最大频繁项集并行挖掘算法

提出一种基于极大完全子图的最大频繁项集并行挖掘算法PMFIM,通过遍历由频繁2-项集构成的用邻-接矩阵表示的图,寻找图的极大完全子图,从而由极大完全子图顶点序列实现对项集的划分,即挖掘子任务的划分.在同类算法中,将找到的最大频繁项划分为局部最大频繁项集LMFI、可能最大频繁项集PMFI和邻接项集的最大频繁项集的超集SMFI,减少了该类算法合并最大频繁项集的开销,并对算法进行了实现和优化.     

双数组穷举法挖掘医药销售数据库频繁集

为了挖掘医药销售数据库频繁集,采用双数组穷举算法DAEA。该算法主要使用两个数组和穷举算法,实现挖掘医药销售数据库的频繁集功能。该算法的优点是只需对医药销售数据库进行数据预处理就可以直接挖掘该数据库的频繁集,无需把医药销售数据库转换成相应的事务数据库。根据DAEA算法,开发了医药销售数据库频繁集挖掘系统,使用该系统挖掘医药销售数据库的频繁集,挖掘的结果与实际相吻合,说明该算法是可行的和有效的。     

基于团的频繁项集挖掘算法

高效地找出所有的频繁项集是关联规则挖掘中的核心问题。通过对已有的基于矩阵的频繁项集挖掘算法的研究,提出一种基于团的频繁项集快速生成算法。该算法采用关联图存储频繁两项集信息,找关联图中团,逐步减少团中项来搜索所有最大频繁项集,并且其扫描数据库仅需一次。通过使用标准数据集进行验证测试并与其他算法进行比较,实验结果表明,该算法具有较快的挖掘速度。