基于压缩FP-树和数组技术的频繁模式挖掘算法

FP-growth算法是目前较高效的频繁模式挖掘算法之一.它只需扫描数据库两次,而且不需要产生和测试候选集,避免了这些费时的工作,因此该算法具有较高的效率.然而,FP-growth算法需要递归地生成大量的条件FP-树,这耗费了大量的存储空间和时间.综合已有的几项优势技术,提出了一种频繁模式挖掘算法CFPmine. 一是采用了基于压缩FP-树的约束子树的挖掘方法,避免在挖掘过程中生成条件FP-树,减少内存占用;二是采用基于数组的技术,减少FP-树的遍历时间,提高算法的效率.另外,在算法中还实现了统一的内存管理.实验结果表明,CFPmine是一个高效的频繁模式挖掘算法,其性能优于Apriori,Eclat和FP-growth算法,而需要的内存却少于FP-growth算法.     

一种高效的多层和概化关联规则挖掘方法

通过对分类数据的深入研究,提出了一种高效的多层关联规则挖掘方法:首先,根据分类数据所在的领域知识构建基于领域知识的项相关性模型DICM(domain knowledge-based item correlation model),并通过该模型对分类数据的项进行层次聚类;然后,基于项的聚类结果对事务数据库进行约简划分;最后,将约简划分后的事务数据库映射至一种压缩的AFOPT树形结构,并通过遍历AFOPT树替代原事务数据库来挖掘频繁项集.由于缩小了事务数据库规模,并采用了压缩的AFOPT结构,所提出的方法有效地节省了算法的I/O时间,极大地提升了多层关联规则的挖掘效率.基于该方法,给出了一种自顶向下的多层关联规则挖掘算法TD-CBP-MLARM和一种自底向上的多层关联规则挖掘算法BU-CBP-MLARM.此外,还将该挖掘方法成功扩展至概化关联规则挖掘领域,提出了一种高效的概化关联规则挖掘算法CBP-GARM.通过大量人工随机生成数据的实验证明,所提出的多层和概化关联规则挖掘算法不仅可以确保频繁项集挖掘结果的正确性和完整性,还比现有同类最新算法具有更好的挖掘效率和扩展性.     

挖掘事务间频繁闭项集的高效率算法

事务间频繁项集将传统的单维事务内关联规则扩展到多维跨事务关联规则,但事务问频繁项集的数量随滑 动时同间窗口的增大而迅速增加.利用频繁闭项集的特点.提出事务间频繁闭项集的概念及其挖掘算法(FCITA).该算法采用分割和条件数据库技术,避免生成庞大的扩展数据库;利用扩展二进制形武压缩事务,从而提高支持度的计算效事.此外,动态排序和哈希表极大地减少了频繁闭项集的测试次数.仿真比较表明,FCITA算法具有较高的挖掘效率.     

基于FP-Tree的共享前缀频繁项集挖掘算法

在数据挖掘中发现关联规则是一个基本问题,而发现频繁项集是关联规则挖掘中最基本、最重要的问题。提出了基于FP-Tree的共享前缀频繁项集挖掘算法－FP-SPMA算法。构造FP-Tree来压缩事务数据库,通过共享前缀和前瞻剪枝快速减小候选项集,无需递归构造条件模式树,算法性能有明显的提高。     

一种基于MFP树的快速关联规则挖掘算法

在关联规则挖掘FP-Growth算法的基础上,提出一种基于MFP树的快速关联规则挖掘算法。文中给出了MFP算法的工作原理。MFP算法能在一次扫描事务数据库的过程中,把该数据库转换成MFP树,然后对MFP树进行关联规则挖掘。MFP算法比FP-Growth算法减少一次对事务数据的扫描,因此具有较高的时间效率。     

一种基于MFP树的快速关联规则挖掘算法

在关联规则挖掘FP-Growth算法的基础上,提出一种基于MFP树的快速关联规则挖掘算法。文中给出了MFP算法的工作原理。MFP算法能在一次扫描事务数据库的过程中,把该数据库转换成MFP树,然后对MFP树进行关联规则挖掘。MFP算法比FP-Growth算法减少一次对事务数据的扫描,因此具有较高的时间效率。     

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

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

一种改进的加权频繁项集挖掘算法

FP-growth算法是挖掘频繁项集的经典算法,它利用FP-树这种紧凑的数据结构存储事务数据库与频繁项集挖掘相关的全部信息,但对于挖掘加权频繁项集并不合适。分析了现有加权频繁项集挖掘算法中存在的问题,并对FP-树进行改进,构造新的加权FP-树,提出了有效挖掘加权频繁项集的算法。最后举例说明了算法的挖掘过程,并通过实验验证了算法的有效性。     

一种面向布尔时间序列的关联规则挖掘算法

布尔时间序列中的关联规则挖掘较难处理,因为多数关联规则仅挖掘不同事务共同出现的规则,难以体现同一事件在不同时间内动态变化间的关联性.鉴于此,提出一种新的关联规则挖掘框架,利用常量化表示布尔数据的时间属性,结合聚类算法和关联分析,提高规则的支持度,从而解决布尔时间序列数据在关联规则挖掘中的时间值表示问题,并使用多种指标评价规则与传统算法比较.在真实的中风病预后好转数据预测中验证了所提出算法的有效性.     

挖掘数据库中的负频繁模式

传统的关联规则挖掘研究事务中所包含的项与项之间的关联性,而负关联规则挖掘不仅要考虑事务中包含的项,还要考虑事务中不包含的项。给出了完全负关联规则的定义,提出一种基于树的算法Free-PNP,通过此算法挖掘数据库中的负频繁模式,继而得到所要挖掘的完全负关联规则。通过实验验证了算法的有效性。     

A template model for multidimensional inter-transactional association rules

Multidimensional inter-transactional association rules extend the traditional association rules to describe more general associations among items with multiple properties across transactions. “After McDonald and Burger King open branches, KFC will open a branch two months later and one mile away” is an example of such rules. Since the number of potential inter-transactional association rules tends to be extremely large, mining inter-transactional associations poses more challenges on efficient processing than mining traditional intra-transactional associations. In order to make such association rule mining truly practical and computationally tractable, in this study we present a template model to help users declare the interesting multidimensional inter-transactional associations to be mined. With the guidance of templates, several optimization techniques, i.e., joining, converging, and speeding, are devised to speed up the discovery of inter-transactional association rules. We show, through a series of experiments on both synthetic and real-life data sets, that these optimization techniques can yield significant performance benefits. Edited by M.T. ?zsu. Received: February 16, 2001 / Accepted: June 1, 2002 Published online: September 25, 2002     

事务间数值型关联规则的挖掘

关联规则的发现是整个数据挖掘课题中的重要组成部分。在归纳现有关联规则研究的基础上提出了事务间数值型关联规则的数据挖掘问题，并对该问题进行了定义。应用模糊理论和相关的数据挖掘技术，提出了解决该问题的E—QA算法，并以实例对算法可行性进行验证，指出了算法存在的一些问题以及今后解决这些问题的思路。     

基于时序关联规则的商品需求预测

为了满足商品销售企业对商品需求预测的需求,提出一种时序关联规则挖掘算法。利用企业商品销售数据与客户相关的特点,提出客户模式数据模型,针对该数据模型,给出时序关联规则挖掘算法。利用该算法对超市销售数据进行时序关联规则挖掘,得到了正确的结果,验证了其在实际应用中的有效性。     

一个最优分类关联规则算法

分类和关联规则发现是数据挖掘中的两个重要领域。使用关联规则算法挖掘分类规则被叫做分类关联规则算法,是一个有较好前景的方法。本文提出了一个最优分类关联规则算法——OCARA。该算法使用最优关联规则挖掘算法挖掘分类规则,并对最优规则集排序,从而获得一个分类精度较高的分类器。将OCARA与传统分类算法C4.5和一般分类关联规则算法CBA、RMR在8个UCI数据集上进行实验比较,结果显示OCARA具有更好的性能,证明OCARA是一个有效的分类关联规则挖掘算法。     

一种新的关联规则挖掘方法

关联规则挖掘是数据挖掘的主要任务之一。为了进一步提高关联规则挖掘算法的认知特性和运算效果,提出了一种新的关联规则挖掘思想并由此构造了一种基于规则模糊认知图的关联规则挖掘算法。该算法使用规则模糊认知图进行知识表示,对每个挖掘到的关联规则进行可达模糊推理,从而减少了与数据库交互的次数。实验证明该方法与Apriori的关联规则算法相比,提高了关联规则挖掘的效率,增强了智能化程度。     

基于关联规则的网络故障告警相关性分析

针对网络故障复杂、告警数据库信息量大等问题,提出一种改进的增量式关联规则挖掘算法。采用关联规则挖掘技术,对告警数据库中的更新规则进行增量关联规则挖掘,将传统告警分析方法与挖掘出的关联规则相结合,应用于网络故障告警相关性分析中。实验结果表明,该算法能减少冗余规则,提高挖掘效率。     

Efficient rule mining and compression for RDF style KB based on Horn rules

The volume of published linked open datasets in RDF format is growing exponentially in the last decades. With this continuous proliferation of this growth, demands for managing, accessing, and compressing the RDF dataset have become increasingly important. Most approaches are focused on the structured compression technique while a very few researches have been done for compact representation of the RDF dataset. In this paper, we have proposed an efficient rule mining and compression approach for RDF datasets through various meaningful semantic association rules determined from the RDF graph. We have introduced grammar-based pattern system, clustering of rules, rules pruning, and Top-k scheme to improve the expressiveness of rule patterns, identify the similarity within the random pair of rules, extract the most delicate rules, find the accurate mining threshold, and efficiently learn the rules during the rule mining process from RDF Knowledge Base. Our proposed system uses Horn rules to achieve better compression through storing the triples matched with the precedent part while deleting the triples matched with the head part of the rules. For decreasing the mining time, we have introduced the ranking of the rules. The experimental result on the benchmark dataset asserts that our proposed rule mining and compression scheme has achieved approximately 22.10%, 40.5%, and 44% better compression than the exiting AMIE+, Rule-based compression, and TripleBit approaches, respectively. Our system also has achieved better performance both in terms of compression time and rule mining cost.

     

基于AR_TSM的时间序列motif关联规则挖掘方法研究

挖掘时间序列motif间潜在的关联规则可以在预测未来趋势方面发挥重要作用,时间序列motif即时间序列中先前未知的重复出现的模式。针对符号化时间序列提取motif导致信息丢失的问题,提出基于剪枝技术的motif提取算法PM_Motif,实现了保留原始信息的motif的精准快速提取;针对分割motif来发现其内部关联规则导致的规则不一致的问题,从motif间的关联规则入手,给出了基于AR_TSM方法的时间序列motif关联规则挖掘算法,从根本上避免了因motif分割引起的不确定性,保证了规则的一致性;最后,引入了关联规则评价参数RM,在多数据集上证明了关联规则的预测性能。     

基于基集与概念格的关联规则挖掘算法

传统关联规则挖掘算法的挖掘效率较低,且挖掘结果中存在大量冗余。针对该问题,提出一种基于概念格与基集的关联规则挖掘算法。利用规定种子项分布范围的基集代替原始数据库以缩小挖掘源规模,从而建立概念格快速求解出关联规则。实验结果表明,该算法在时间效率方面优于Base和Apriori算法。     

基于序号索引的空间关联规则挖掘算法

针对空间关联规则挖掘算法的冗余计算问题,提出一种基于序号索引的空间关联规则挖掘算法。该算法适用于挖掘单层横向空间的关联规则,在自底向上和自顶向下的搜索过程中,用定序操作产生序号索引,通过序号索引在双向挖掘过程中修剪重复候选项和删除冗余计算,以提高算法效率。实验结果证明该算法比现有的算法更快速有效。