基于剪枝概念格模型的频繁项集表示及挖掘

发现频繁项集是关联规则挖掘的关键步骤。然而,大多数频繁项集求解算法因需要产生大量候选集而降低了效率。该文在研究概念格和频繁项集关系的基础上,将剪枝概念格PCL模型引入数据库中频繁项集的表示,利用概念间的关系性质,在不丢失信息的同时能有效压缩频繁项集的规模,并提出基于PCL模型的频繁项集求解算法。该算法基于Apriori性质,在构造过程中及时、动态地剪枝,删除与频繁项集求解无关的概念,从而有效地改善了频集挖掘算法的时空性能;实验证实了算法良好的性能。     

基于概念格的数据流频繁项集挖掘

提出一个数据流环境下的基于概念格和滑动窗口的频繁项集挖掘算法DSFMCL。算法在滑动窗口内分批挖掘新流入的基本窗口频繁概念后,生成概念格的Hasse图。引入最小支持度ζ和误差因子ε对非频繁概念节点进行剪枝操作。Hasse图中各节点包含频繁项集及其支持度信息。随着新基本窗口的Hasse图的生成与滑动窗口进行概念格纵向合并,最终通过对全部Hasse图节点的扫描可以输出所有频繁项集。实验结果表明,该算法具有良好的性能。     

快速更新最小频繁概念格

更新挖掘最大频繁项目集是研究动态数据库挖掘的重要方面;文章在量化概念格的基础上,引进最小频繁概念格的概念,提出了一种快速的更新挖掘最大频繁项目集的算法,该算法能够在原有挖掘结果的基础上,快速有效地挖掘出更新后的数据库中隐含的新最大频繁项目集.     

基于量化概念格的关联规则挖掘

在概念格的内涵中引入等价关系并将其外延量化 ,得到量化概念格。利用量化概念格可以清晰地表示知识 ,从而便于挖掘包括关联规则在内的多种规则 ,与经典的 A priori算法相比较 ,规则表示更简捷、直观 ,尤其重要的是用户可根据自己的兴趣交互地挖掘关联规则 ,不需要计算频繁项目集 ,因而提高了挖掘规则的效率 ,适用于大型数据库中关联规则的挖掘     

基于空间划分的频繁模式挖掘算法

对关联规则挖掘问题建立了完全格描述并给出了问题规模下限,提出了一种基于搜索空间划分的项集频度计算模型.在对FP-树进行改造的基础上提出基于划分思想的频繁项集挖掘算法UPM,算法的项集频度计算和非频繁项目裁剪都基于空间划分的思想.性能实验表明,与FP-Growth算法相比,UPM算法的时空效率有较大提高.     

基于概念格的数据挖掘方法研究

分析了概念格与关联规则之间的关系,提出了将频繁项集及其支持度存储在概念格上,然后在创建好的概念格上提取关联规则的方法,概念格的每个节点本质上是一个最大项目集,非常有利于关联规则的提取。然而目前对于概念格的研究,一般都假定由属性集所组成的概念格的内涵同等重要,而在现实数据库中,组成内涵的属性重要性往往是不同的,因此,内涵并非同等重要。为了充分利用概念格实现关联规则提取,提出了一种新的概念格结构:加权概念格,并给出其渐进式构造算法及基于该格结构上的关联规则提取算法。     

基于概念格的数据挖掘方法研究

分析了概念格与关联规则之间的关系,提出了将频繁项集及其支持度存储在概念格上,然后在创建好的概念格上提取关联规则的方法,概念格的每个节点本质上是一个最大项目集,非常有利于关联规则的提取。为了充分利用概念格实现关联规则提取,提出了一种新的概念格结构:加权概念格,并给出其渐进式构造算法及基于该格结构上的关联规则提取算法。     

关联规则挖掘的一种多剪枝概念格方法

多数据源上关联规则挖掘方法,由于各数据节点间相互通信的候选项集数目过于庞大或者挖掘过程需要对数据库进行多次扫描,导致挖掘算法效率不高。研究剪枝概念格(pruned con-cept laffice,PCL)中概念与频繁项集表示关系,定义剪枝格上的导出频繁项集,设计了一个利用多剪枝概念格从多数据源上挖掘近似所有关联规则的算法UMPCL(union algorithm of multiplepruned concept lattice)。利用一个频繁概念表示一些频繁项集以减少挖掘过程中产生的侯选项集数,使用与全局支持度相等的局部支持度对各子概念格进行剪枝,最后融合、剪枝各子剪枝格并提取全局关联规则。理论分析和实验验证表明该算法是有效的。     

基因表达数据的频繁模式挖掘算法

使用关联规则的方法来挖掘基因表达数据,在研究分析经典关联规则挖掘算法优缺点的基础上,立足于基因表达数据所呈现的新特征,提出一种基于BSC_tree的分段与运算基因表达数据频繁模式挖掘新算法BSC-AND.实验结果表明,与FP-growth和FIS算法相比,所提出的算法具有更低的时间复杂性.     

利用FP-树挖掘有约束的频繁模式

探索有约束限制的频繁模式的挖掘问题,目的是要建立一个基本框架,通过构造一种新的数据结构--约束树,解决了确定一个项集的最小约束值的关键问题.在此基础上进一步提出了一种有约束限制的模式增长算法,并进行了初步的实验验证.实验结果表明,新的算法比以前类似算法在性能上有显著提高.     

基于最小完美哈希函数的数据挖掘算法

提出了一种基于最小完美哈希函数的关联规则的挖掘算法.这一基于Apriori的算法在综合了传统哈希剪枝技术的同时,充分利用了最小完美哈希函数的优点,从而在保证静态数据库关联规则挖掘的同时,使对关联规则的哈希结构数据进行动态调整成为可能.这一算法不仅提高了挖掘效率,而且通过抑制哈希地址冲突提高了算法的稳定性和可用性.     

基于MapReduce的频繁模式挖掘算法的优化

分布式数据挖掘计算是大数据研究中非常重要的技术,现有的对频繁模式的分布式挖掘方法在处理大量数据集时仍然存在许多局限,如并行Apriori算法在多次扫描数据库过程中对I/O产生很大负担,并且有大量候选集产生.本文使用的FP-growth算法包括Fp-tree构建和频繁模式挖掘两个阶段.主要思想是在map阶段构建FP-tree之前,根据步长值及项目元素编码对FP-tree节点合并,并在shuffle阶段依据平衡算法划分给不同的reducer.平衡算法用来均衡工作负载.利用该算法来降低数据分配的随机性,避免数据挖掘阶段由于数据划分不均衡导致部分reducer开销过大的缺点.实验结果表明:与现有方法相比,在较大数据集情况下改进后的算法具有更好地运算效率和可伸缩性.     

Incremental frequent tree-structured pattern mining from semi-structured data

The paper studies the problem of incremental pattern mining from semi-structrued data. When a new dataset is added into the original dataset, it is difficult for existing pattern mining algorithms to incrementally update the mined results. To solve the problem, an incremental pattern mining algorithm based on the rightmost expansion technique is proposed here to improve the mining performance by utilizing the original mining results and information obtained in the previous mining process. To improve the efficiency, the algorithm adopts a pruning technique by using the frequent pattern expansion forest obtained in mining processes. Comparative experiments with different volume of initial datasets, incremental datasets and different minimum support thresholds demonstrate that the algorithm has a great improvement in the efficiency compared with that of non-incremental pattern mining algorithm.     

一种基于模式增长的频繁模式挖掘算法

提出了一种基于模式增长的频繁模式挖掘算法(简称为PGMiner算法).这种算法是一种深度挖掘的算法,不产生任选项集,便于发现较长的模式,避免了Apriori和FP-growth方法存在的问题.通过一种简单的索引结构在映射数据库中不断地增加模式长度.这种索引结构占用较少的内存,使得这种基于内存的算法有很高的执行效率.采用现实数据集以及IBM人工数据集对PGMiner算法进行测试.试验结果显示,对于一般类型的特别是较为稀疏的数据集,PGMiner算法比Apriori和FP-growth方法有更好的性能.     

Constructing Projection Frequent Pattern Tree for Efficient Mining

Frequent Pattern mining plays an essential role in data mining. Most of the previous studies adopt an Apriori-like candidate set generation-and-test approach. However, candidate set generation is still costly, especially when there exist prolific patterns and/or long patterns.In this study, we introduce a novel frequent pattern growth (FP-growth) method, which is efficient and scalable for mining both long and short frequent patterns without candidate generation. And build a new projection frequent pattern tree (PFP-tree) algorithm on this study, which not only heirs all the advantages in the FP-growth method, but also avoids it's bottleneck in database size dependence when constructing the frequent pattern tree (FP-tree). Efficiency of mining is achieved by introducing the projection technique, which avoid serial scan each frequent item in the database, the cost is mainly related to the depth of the tree, namely the number of frequent items of the longest transaction in the database, not the sum of all     

基于概念格的web log分布式挖掘算法

提出一种有效的基于概念格的分布式挖掘算法,重点讨论由部分量化规则格提取的部分关联规则的合并技术,由于能对已存在关联规则的再利用,从而更有利于用概念格来挖掘关联规则.该算法根据对局部关联规则挖掘结果的分布式合成,有利于减轻网络频繁的通讯负担,体现并行计算、异步异构数据挖掘的优点.     

概念格及其应用进展

概念格是近年来获得飞速发展的数据分析的有力工具。从数据集中生成概念格的过程实质上是一种概念聚类过程。然而 ,概念格可以用于许多机器学习的任务 ,例如分类 ,关联规则的挖掘等。论文介绍了概念格的基本概念 ,讨论了现有的几种建格算法和在格上提取规则的方法及相关系统和应用。另外 ,还介绍了格的剪枝及概念格和另一个新型数据分析工具粗糙集之间的关系。     

挖掘频繁波动的Web访问模式算法研究

考虑到Web访问数据的动态特性,给出了一个从Web访问日志历史演变中挖掘频繁波动的Web访问模式的方法.首先采用无序树结构表示用户历史访问页面序列集合,然后给出了频繁波动Web访问模式的详细定义以及挖掘算法描述,最后,根据数据集中访问序列的大小和数量变化对于算法扩展性和性能的影响进行了实验.结果表明,该算法具备良好扩展性的同时,能够比较高效地提取出频繁波动的Web访问模式.