无项头表的FP-Growth算法

针对FP-Growth算法中频繁模式树的遍历低效问题,提出了一种无项头表的频繁模式增长算法。该算法利用递归回溯的方式遍历频繁模式树以求取条件模式基,解决了对同一树路径多次重复遍历的问题。从理论分析和实际挖掘能力两方面,将新算法与FP-Growth算法进行了对比。结果表明,新算法有效减少了条件模式基的搜索开销,使频繁模式挖掘的效率提高了2~5倍,在时间和空间性能上均优于FP-Growth算法。将该算法应用于通信告警关联规则挖掘,较快地挖掘出了关联规则结果,且正确规则的覆盖率达到了83.3%。     

智能交通系统开发中关联规则挖掘算法的应用

重点介绍了关联规则挖掘算法中的FP-Growth(Frequent Pattern Growth,频繁模式增长)算法,并给出FP-Growth算法的编程实现以及在智能交通系统中的应用实例。研究结果表明,其挖掘结果可对交通违法行为的预测提供重要的决策支持。     

基于FP-Growth的战略绩效关联分析算法研究

在处理战略绩效KPI关联规则挖掘的问题时,由于FP-Growth不能根据业务的需要简化计算过程,从而产生了许多冗余计算,影响了算法的效率。因此,提出了一种基于FP-Growth的战略绩效关联分析算法。通过采用基于规则的约束方法对FP-Growth算法进行改进。一方面,在挖掘的过程中添加剪枝操作,提高频繁项集的挖掘效率;另一方面,在关联规则产生过程中,添加规则约束,生成符合业务要求的关联规则,从而减少了冗余计算,提高了算法的效率。最后,以"某高校科研服务质量指标"为例,验证了该算法的可行性。     

一种面向高校学生体测数据的模式挖掘方法

目前,每年测试高校大学生的体质健康,会产生大量的数据,为了提高关联规则对体测数据的挖掘效率,提出了一种面向高校学生体质测试数据的模式挖掘方法。利用经典的关联规则挖掘方法如Apriori算法和频繁模式树（Frequent Pattern Tree,FP-Growth）算法,对体测数据进行关联规则挖掘。实验结果表明,该模式挖掘的最小数据集能有效提高关联规则算法对体测数据的模式挖掘效率。     

分布式并行关联规则挖掘算法研究

关联规则挖掘算法FP-Growth虽然效率比Apriori要快一个数量级,但存在频繁模式树可能过大而内存无法容纳和数据挖掘过程串行处理等两大缺点。提出一种分布式并行关联规则挖掘算法,该算法针对分布式应用数据架构,不需要产生全局FPtree,避免全局FP-tree可能过大而内存无法容纳的问题,算法在各个主要步骤上都实现了并行处理。算法测试结果和分析表明,与传统的关联规则挖掘算法FP-Growth相比,该算法通过多节点分布式并行处理显著提高了执行效率和处理能力。     

支持个性化推荐的Web页面关联规则挖掘算法

分析了应用于个性化推荐的Web页面关联规则的特点,提出了“壹支持数下k关联规则”的思想,根据这一思想设计、实现了一种应用于个性化推荐的Web页面关联规则挖掘算法——PARM(Pageview Association Rule Mining)及频繁项集的Freq-Set-Tree存储结构,在产生频繁项的同时挖掘关联规则,因而能提高效率。实验证明在个性化推荐系统中PARM算法的效率明显高于FP-Growth算法。     

改进关联规则挖掘算法在入侵检测中的应用

在关联规则挖掘算法中基于FP-树的FP-Growth挖掘算法在挖掘频繁模式的过程中需要递归产生大量的条件FP—树,效率不高,FP-Growth算法不太适合应用到入侵中多种要素交叉的关联关系的挖掘中.因为入侵的方法及要素很多,在检测中需要对入侵样本进行条件约束下的定量分析.文中分析入侵检测的特点,提出基于条件频繁项的频繁模式树CP-Tree以及在此树挖掘的改进算法MineCPT.分析与实验结果表明,MineCPT算法在效率和可靠性等方面比FP-Growth 算法更优越,在入侵检测中取得了较好的效果.     

基于Spark的并行频繁项集挖掘算法

关联规则挖掘是数据挖掘领域的重要研究方向之一。频繁项集的挖掘是关联规则挖掘的第一步,也是最重要的步骤。FP-Growth(Frequent Pattern-Growth)算法因其挖掘效率以及空间复杂度方面的优势被广泛应用于频繁项集挖掘任务中。面对海量数据,FP-Growth算法挖掘效率变得极低甚至失效。在Hadoop大数据平台上实现的基于MapReduce框架的并行FP-Growth算法——PFP算法解决在处理大规模数据时传统算法失效的问题,但是由于其将每次执行之后的中间结果输出到磁盘,降低算法执行效率。为提高并行FP-Growth算法执行效率,提出一种基于Spark的SPFPG算法。该算法运用负载均衡思想对分组策略进行改进,综合考虑分区计算量和FP-Tree规模两个因素,保证每个组之间负载总和近似相等。在Spark上实现FP-Growth算法——SFPG算法的基础上,实现优化后的SPFPG算法。实验结果表明,SPFPG算法相比SFPG算法挖掘效率更高,且算法具有良好的扩展性。     

支持个性化推荐的Web面关联规则挖掘算法

分析了应用于个性化推荐的Web页面关联规则的特点，提出了“壹支持数下k关联规则”的思想，根据这一思想设计、实现了一种应用于个性化推荐的Web页面关联规则挖掘算法——PARM(Pageview Association Rule Mining)及频繁项集的Freq-Sdt-Tree存储结构，在产生频繁项的同时挖掘关联规则，因而能提高效率。实验证明在个性化推荐系统中PARM算法的效率明显高于FP-Growth算法。     

一种改进的FP-Growth算法及其在业务关联中的应用

基于FP-树的FP-Growth算法在挖掘频繁模式过程中需要递归地产生大量的条件FP-树,效率不高,并且不太适合应用在移动通信业务交叉销售等具有业务约束的关联规则挖掘中。因此,提出了基于项目约束的频繁模式树ICFP-树和直接在此树上进行挖掘的新算法——ICFP-Mine。理论分析和实验结果表明,ICFP-Mine算法在内存占用和时间开销等方面比FP-Growth算法更优越,在移动通信业务交叉销售领域的应用中取得了较好的效果。     

图像纹理特征挖掘*

借助数据挖掘方法在图像中的应用,提出了一种利用图像降阶结合基元模式匹配对纹理特征进行挖掘的新思路。采用关联规则挖掘算法对图像纹理的频繁模式进行挖掘,通过联合关联规则来表达纹理。实验结果显示,挖掘出的关联规则不仅能够表达规则纹理,而且能够较好地表达随机纹理。     

Mining spatial association rules in image databases

In this paper, we propose a novel spatial mining algorithm, called 9DLT-Miner, to mine the spatial association rules from an image database, where every image is represented by the 9DLT representation. The proposed method consists of two phases. First, we find all frequent patterns of length one. Next, we use frequent k-patterns (k ? 1) to generate all candidate (k + 1)-patterns. For each candidate pattern generated, we scan the database to count the pattern’s support and check if it is frequent. The steps in the second phase are repeated until no more frequent patterns can be found. Since our proposed algorithm prunes most of impossible candidates, it is more efficient than the Apriori algorithm. The experiment results show that 9DLT-Miner runs 2-5 times faster than the Apriori algorithm.     

Mining closed patterns in multi-sequence time-series databases

In this paper, we propose an efficient algorithm, called CMP-Miner, to mine closed patterns in a time-series database where each record in the database, also called a transaction, contains multiple time-series sequences. Our proposed algorithm consists of three phases. First, we transform each time-series sequence in a transaction into a symbolic sequence. Second, we scan the transformed database to find frequent patterns of length one. Third, for each frequent pattern found in the second phase, we recursively enumerate frequent patterns by a frequent pattern tree in a depth-first search manner. During the process of enumeration, we apply several efficient pruning strategies to remove frequent but non-closed patterns. Thus, the CMP-Miner algorithm can efficiently mine the closed patterns from a time-series database. The experimental results show that our proposed algorithm outperforms the modified Apriori and BIDE algorithms.     

基于Apriori算法的改进算法

关联规则挖掘是数据挖掘研究的一项重要内容.为了快速挖掘关联规则,分析了挖掘关联规则的Apriori算法,并在此基础上给出了一种改进的算法:NApriori算法,利用频繁1项集重新组织事务数据库来挖掘关联规则,此方法仅需扫描数据库2次,且避免了Apriori算法繁琐的连接和删除步骤,实验结果表明此方法比Apriori算法有更好的性能.     

挖掘多支持率分类规则的虚拟投影算法

本文首先提出了一种挖掘频集的高效算法PP。它采用了一种基于树的模式支持集表示，避免了反复扫描数据库和递归建造个数与频繁模式数相同的模式支持集，其效率比Apriori和FPGrowth高1—3个数量级。PP被进一步扩展成发现分类规则的有效算法CRM-PP。CRM-PP将多支持率剪裁集成到频集发现阶段，将二阶段挖掘法改进为单阶段挖掘法。CRM-PP的效率也比基于Apriori和FPGrowth的二阶段算法高1—3个数量级。     

Alattin: mining alternative patterns for defect detection

To improve software quality, static or dynamic defect-detection tools accept programming rules as input and detect their violations in software as defects. As these programming rules are often not well documented in practice, previous work developed various approaches that mine programming rules as frequent patterns from program source code. Then these approaches use static or dynamic defect-detection techniques to detect pattern violations in source code under analysis. However, these existing approaches often produce many false positives due to various factors. To reduce false positives produced by these mining approaches, we develop a novel approach, called Alattin, that includes new mining algorithms and a technique for detecting neglected conditions based on our mining algorithm. Our new mining algorithms mine patterns in four pattern formats: conjunctive, disjunctive, exclusive-disjunctive, and combinations of these patterns. We show the benefits and limitations of these four pattern formats with respect to false positives and false negatives among detected violations by applying those patterns to the problem of detecting neglected conditions.     

基于有限个条件FP_树中挖掘频繁模式

在数据挖掘中发现关联规则是一个基本问题,而关联规则发现中最昂贵的步骤便是寻找频繁模式。FP_growth(frequent-patern growth)方法在产生长短频繁项集时不产生候选项集,从而大大提高了挖掘的效率,但是FP_growth在挖掘频繁模式时候产生大量的条件FP树从而占用大量空间,对FP_growth进行研究提出一种改进算法不仅利用FP_growth 算法所有优点,而且避免FP_growth的缺陷。主要通过建立有限棵条件FP树（数目为事务数据库的属性个数）来挖据长短频繁模式,大大节省FP_growth算法所需要空间,实验证明本文算法是有效的。     

基于FPclose算法挖掘强亲密度关联模式

基于FPclose算法提出了一种挖掘强亲密度关联模式的算法。算法引入客观兴趣度度量h-置信度来识别强亲密度关联模式,利用其反单调性质和交叉支持度性质进行剪枝。实验证明,该算法能够高效地挖掘出倾斜数据集中的强亲密度关联模式。     

A Pattern Decomposition Algorithm for Data Mining of Frequent Patterns

Efficient algorithms to mine frequent patterns are crucial to many tasks in data mining. Since the Apriori algorithm was proposed in 1994, there have been several methods proposed to improve its performance. However, most still adopt its candidate set generation-and-test approach. In addition, many methods do not generate all frequent patterns, making them inadequate to derive association rules. We propose a pattern decomposition (PD) algorithm that can significantly reduce the size of the dataset on each pass, making it more efficient to mine all frequent patterns in a large dataset. The proposed algorithm avoids the costly process of candidate set generation and saves time by reducing the size of the dataset. Our empirical evaluation shows that the algorithm outperforms Apriori by one order of magnitude and is faster than FP-tree algorithm. Received 14 May 2001 / Revised 5 September 2001 / Accepted in revised form 26 October 2001 Correspondence and offprint requests to: Qinghua Zou, Department of Computer Science, California University–Los Angeles, CA 90095, USA. Email: zou@cs.ucla.eduau