基于频繁模式表的增量更新算法

对大型数据库中关联规则挖掘的频繁模式维护问题进行了研究,提出一种增量更新算法(Update Frequent Pattern List,UFPL).该算法基于频繁模式表(FPL),可以处理数据库数据增加和最小支持度都发生改变的情况下关联规则的维护问题.最后,利用公共测试数据集,对算法性能进行测试,相对于快速更新(Fast Update,FUP)算法和增量维护(Incremental Maintenance,IM)算法,其效率有较大改进.     

增量式隐私保护频繁模式挖掘算法

针对多数隐私保护的频繁模式挖掘算法需要多次数据库扫描以及计数时需要进行多次比较的不足，提出了一种增量的基于位图的部分隐藏随机化回答（IBRRPH）算法。首先，引入bitmap表示数据库中的事务，采用"位与"操作有效提高支持度的计算速度；其次，通过分析增量访问关系，引入增量更新模型，使得在数据增量更新时频繁模式挖掘最大限度地利用了之前挖掘结果。针对增量分别为1000至40000，与顾铖等提出的算法（顾铖，朱保平，张金康.一种改进的隐私保护关联规则挖掘算法.南京航空航天大学学报，2015，47（1）：119-124）进行了对比测试实验。实验结果表明，与顾铖等提出的算法相比，IBRRPH算法的效率提高幅度超过21%。     

一种基于FP-树的最大频繁模式增量更新挖掘算法

挖掘关联规则是数据挖掘领域的一个重要研究方向,人们已经提出了许多用于发现数据库中关联规则的算法,但对关联规则的增量维护问题的研究较少.深入分析了增量更新情况,使用了目前较高效的最大频繁模式挖掘算法FP-Max,并对其进行改进.基本思想:①基于FP-树;②考虑了数据集中,数据增加情况下FP-树的更新;③对FP-Max算法进行改进来更新、维护已经挖掘出来的最大频繁模式.     

基于扩展自然序树的概化关联规则增量挖掘方法

概化关联规则挖掘作为数据挖掘领域一个重要的拓展性研究课题,首先提出了一种概化扩展自然序树(generalized extended canonical-order tree,GECT)结构及其增量挖掘算法GECT-IM.该算法对原始分类事务数据库只扫描一次,就可以将所有交易信息映射至一棵压缩格式的GECT,然后通过对更新交易数据集扫描得到更新数据集中各项集的计数,结合相关性质及运算就可以发现大部分更新后的概化频繁项集;其次,针对GECT规模较大以及GECT-IM 算法仍然可能需要遍历初始GECT树的局限,在界定数据库更新和重构概念的基础上,基于一种可量化度量的准最小支持度阈值,提出了一种改进的准频繁概化扩展自然序树(pre-large generalized extended canonical-order tree,PGECT)结构及其增量挖掘算法PGECT-IM.由于有效避免了对初始GECT进行遍历的情形,从而进一步提升了概化关联规则增量挖掘效率.实验证明,提出的概化关联规则增量挖掘算法 GECT-IM 及其优化算法PGECT-IM,比现有增量挖掘算法具有更高的挖掘效率和更好的扩展性.     

交易数据库的加权关联规则增量更新算法

针对文献犤1犦提出的加权关联规则挖掘算法,文章提出了交易数据库的加权关联规则增量更新算法(DWARIUA算法)。该算法充分利用已存在的频繁项目集,因此,算法是有效而可行的。     

基于FP-Tree的最大频繁项目集挖掘及更新算法

挖掘最大频繁项目集是多种数据挖掘应用中的关键问题,之前的很多研究都是采用Apriori类的候选项目集生成-检验方法.然而,候选项目集产生的代价是很高的,尤其是在存在大量强模式和/或长模式的时候.提出了一种快速的基于频繁模式树(FP-tree)的最大频繁项目集挖掘DMFIA(discover maximum frequent itemsets algorithm)及其更新算法UMFIA(update maximum frequent itemsets algorithm).算法UMFIA将充分利用以前的挖掘结果来减少在更新的数据库中发现新的最大频繁项目集的费用.     

基于充分挖掘增量事务的关联规则更新算法

目前已提出了许多快速的关联规则增量更新挖掘算法，但是它们在处理对新增事务敏感的问题时，往往会丢失一些重要规则。为此，文章提出了一种新的挖掘增量更新后的数据库中频繁项集的算法EUFIA（ Entirety Update Frequent Itemsets Algorithm），该算法先对新增事务数据分区，然后快速扫描各分区，能全面有效地挖掘出其中的频繁项集，且不丢失重要规则。同时，最多只扫描1次原数据库也能获得更新后事务数据库的全局频繁项集。研究表明，该算法具有很好的可测量性。     

一种基于频繁序列树的增量式序列模式挖掘算法

针对目前现有的增量式序列模式挖掘算法没有充分利用先前的挖掘结果,当数据库更新时,需要对数据库进行重复挖掘的问题。本文提出一种基于频繁序列树的增量式序列模式挖掘算法(ISFST),ISFST采用频繁序列树作为序列存储结构,当数据库发生变化时,ISFST算法分两种情况对频繁序列树进行更新操作,通过遍历频繁序列树得到满足最小支持度的所有序列模式。实验结果表明,ISFST算法在时间性能上优于PrefixSpan算法和IncSpan算法。     

一种基于FP-tree的频繁项集增量更新算法

针对频繁项集增量更新的问题，提出算法FIU。该算法将保存了数据库事务的FP-tree存储在磁盘上，当挖掘新支持度阈值的频繁项集时，只需从磁盘上读入FP-tree，再挖掘新支持度阈值下的频繁项集。当新增数据库事务记录后，首先建立新项目表，然后根据新项目表建立新增事务记录的FP-tree，读入存储在磁盘上的FP-tree，抽取出所有的事务记录，再插入到新FP-tree中．从而得到增量更新后的FP-tree。最后在增量更新后的FP-tree上挖掘频繁项集。实验证明，FIU算法执行时间不随数据库大小变化，与其他算法相比有较好的性能。     

缩减投影数据库规模的增量式序列模式算法

在增量式序列模式挖掘算法中,数据库更新只有插入和扩展2种操作,未考虑序列删除的情况。为此,提出一种基于频繁序列树的增量式序列模式更新算法(IUFST)。在数据库和支持度发生变化时,IUFST算法分不同情况对频繁序列树进行更新操作,缩减投影数据库的规模,提高算法效率。实验结果表明,该算法在时间性能上优于PrefixSpan算法和IncSpan算法。     

快速更新全局频繁项目集

数据挖掘中的频繁项目集更新算法研究是重要的研究课题之一.目前已有的频繁项目集更新算法主要针对单机环境,有关分布式环境下的全局频繁项目集的更新算法的研究尚不多见.为此,提出了快速更新全局频繁项目集算法(fast updating algorithm for globally frequent itemsets,简称FUAGFI).该算法主要考虑数据库记录增加时全局频繁项目集的更新情况.FUAGFI利用已建立的各局部频繁模式树(frequent pattern tree,简称FP-tree)及已挖掘的全局频繁项目集,可有效地降低网络通信量,提高全局频繁项目集的更新效率.实验结果表明,所提出的更新算法是行之有效的.     

一种有效的序列模式增量式更新方法

针对序列模式增量式更新挖掘算法产生大量候选项集以及多次扫描数据库的问题,提出了一种有效的增量式更新算法ESPIA,该算法利用基于2-序列矩阵挖掘算法ESPE对原数据库和增加数据库一次扫描产生序列模式,通过对频繁模式和非频繁模式进行相应的剪枝减少了序列的比较和扫描次数,降低了算法时间和空间复杂度,实验证明该算法是有效和准确的。     

Efficient Incremental Maintenance of Frequent Patterns with FP-Tree

Mining frequent patterns has been studied popularly in data mining area. However, little work has been done on mining patterns when the database has an influx of fresh data constantly. In these dynamic scenarios, efficient maintenance of the discovered patterns is crucial. Most existing methods need to scan the entire database repeatedly, which is an obvious disadvantage. In this paper, an efficient incremental mining algorithm, Incremental-Mining (IM), is proposed for maintenance of the frequent patterns when new incremental data come. Based on the frequent pattern tree (FP-tree) structure, IM gives a way to make the most of the things from the previous mining process, and requires scanning the original data once at most. Furthermore, IM can identify directly the differential set of frequent patterns, which may be more informative to users. Moreover, IM can deal with changing thresholds as well as changing data, thus provide a full maintenance scheme. IM has been implemented and the performance study shows it outperforms three other incremental algorithms: FUP, DB-tree and re-running frequent pattern growth (FP-growth).     

PFPonCanTree：一种基于MapReduce的并行频繁模式增量挖掘算法

频繁模式挖掘是最重要的数据挖掘任务之一,传统的频繁模式挖掘算法是以"批处理"方式执行的,即一次性对所有数据进行挖掘,无法满足不断增长的大数据挖掘的需要。MapReduce是一种流行的并行计算模式,在并行数据挖掘领域已得到了广泛的应用。将传统频繁模式增量挖掘算法CanTree向MapReduce计算模型进行了迁移,实现了并行的频繁模式增量挖掘。实验结果表明,提出的算法实现了较好的负载均衡,执行效率有明显提升。     

最小频繁闭树的增量式更新算法

针对树挖掘算法产生大量频繁子树和树数据库随时间变化的问题,提出最小频繁闭树增量式更新算法以及增量式更新策略,能充分利用已有挖掘知识,无须重新运行树挖掘算法,并且只需进行一次数据库扫描操作。给出一种候选子树剪枝方法,能减少树同构判别次数,有效提高算法的运行效率。通过大量实验结果表明,该算法有效可行且效率较高。     

Efficient representative pattern mining based on weight and maximality conditions

As a core area in data mining, frequent pattern (or itemset) mining has been studied for a long time. Weighted frequent pattern mining prunes unimportant patterns and maximal frequent pattern mining discovers compact frequent patterns. These approaches contribute to improving mining performance by reducing the search space. However, we need to consider both the downward closure property and patterns' subset checking process when integrating these different methods in order to prevent unintended pattern losses. Moreover, it is also essential to extract valid patterns with faster runtime and less memory consumption. For this reason, in this paper, we propose more efficient maximal weighted frequent pattern (MWFP) mining approaches based on tree and array structures. We describe how to handle these problems more efficiently, maintaining the correctness of our method. We develop two types of maximal weighted frequent mining algorithms based on weight ascending order and support descending order and compare these two algorithms to conclude which is more suitable for MWFP mining. In addition, comprehensive tests in this paper show that our algorithms are more efficient and scalable than state‐of‐the‐art algorithms, and they also have the correctness of the MWFP mining in terms of their pattern generation results.     

Batch incremental processing for FP-tree construction using FP-Growth algorithm

In the present scenario of global economy and World Wide Web, large sets of evolving and distributed data can be handled efficiently by incremental data mining. Frequent patterns are very important in knowledge discovery and data mining process, such as mining of association rules, correlations. FP-tree is a very versatile data structure used for mining of frequent patterns in knowledge discovery and data mining process. FP-tree is a compact representation of transaction database that contains frequency information of all relevant frequent patterns (FP) of the database. All of the existing incremental frequent pattern mining algorithms, such as AFPIM, CATS, CanTree, CP-tree, and SPO-tree, perform incremental mining by processing one transaction of the incremental part of database at a time and updating it to the FP-tree of initial (original) database. Here, in this paper, we propose a novel method that takes advantage of FP-tree representation of incremental transaction database for incremental mining. We propose a batch incremental processing algorithm BIT_FPGrowth that restructures and merges two small consecutive duration FP-trees to obtain a FP-tree of the FP-Growth algorithm. Our BIT_FPGrowth uses FP-tree as preprocessed data repository to get transactions (i.e., item-sets), unlike other sequential incremental algorithms that read transactions from database. BIT_FPGrowth algorithm takes less time for constructing FP-tree. Our experimental results show that, as the size of the database increases, increase in runtime of BIT_FPGrowth is much less and is least of all the other algorithms.     

改进的频繁模式挖掘算法

为解决传统频繁模式挖掘算法效率不高的问题,提出了一种改进的基于FP-tree （Frequent pattern tree）的Apriori频繁模式挖掘算法.首先,在Apriori算法的连接步加入连接预处理过程;其次,对CP-tree （Compact Pattern tree）进行扩展,构造了一个新的树结构ECP-tree （Extension of Compact Pattern tree）,新的树结构只需对数据库进行一次扫描就能构造出一棵紧凑的前缀树,且支持交互式挖掘与增量挖掘;然后,将改进点与APFT算法结合,用于挖掘频繁模式;最后,使用UCI数据库中两个数据集进行实验.实验结果表明：改进算法具有较高的挖掘效率,频繁模式挖掘速度显著提升.     

分布式Web用户兴趣迁移模式挖掘研究

提出了一个结合Web文本挖掘的分布式Web使用挖掘模型DWLMST，以及基于该模型的局部浏览兴趣迁移模式更新算法LITP和全局浏览兴趣迁移模式更新算法GITP。利用页面聚类来表示用户兴趣。通过将用户事务中的页面替代为相应的聚类号来得到用户浏览兴趣序列。从用户浏览兴趣序列中分析得到用户浏览兴趣迁移模式。算法较好地解决了Web访问信息的异地存储、实时增长等因素给模式分析过程带来的困难，同时也提高了用户浏览兴趣表示的准确性。