最大频集的挖掘方法

在对树生成的策略、模式支持集表示与投影、闭合性剪裁方法研究的基础上，提出了挖掘最大频繁集的两个新算法cap-max和op-max。cap-max是基于闭合频集的二阶段挖掘算法，先挖掘闭合频集，再从中求得最大频集；op-max是直接剪裁完全频集的算法，在频集生成过程中，通过前窥和包含关系检查及时剪裁搜索空间。实验表明，cap—max的时间效率比maxminer高1．5～4倍，op-cap的时间效率比maxminer高2～lO倍。     

基于前缀项集的Apriori算法改进

关联规则的挖掘是数据挖掘中一个重要内容,主要目的是找到事务数据库中的有趣的模式。Apriori算法是关联规则挖掘的最经典算法之一,但是它本身存在着效率上的瓶颈。在深入了解Apriori算法前提下,提出基于前缀项集的候选集存储结构,并利用哈希表在快速查找上的优势,大大提高了经典Apriori算法在连接步骤和剪枝步骤中的效率。实验证明改进后的Apriori算法在一定支持度下比经典Apriori算法有着更大的效率优势,并且支持度越小时提升效率越大。     

基于事务映射区间求交的高效频繁模式挖掘算法

关联规则挖掘是数据挖掘重要研究课题,大数据处理对关联规则挖掘算法效率提出了更高要求,而关联规则挖掘的最耗时的步骤是频繁模式挖掘。针对当前频繁模式挖掘算法效率不高的问题,结合Apriori算法和FP-growth算法,提出一种基于事务映射区间求交的频繁模式挖掘算法IITM（interval interaction and transaction mapping）,只需扫描数据集两次来生成FP树,然后扫描FP树将每个项的ID映射到区间中,通过区间求交来进行模式增长。该算法解决了Apriori算法需要多次扫描数据集,FP-growth算法需要迭代地生成条件FP树来进行模式增长而带来的效率下降的问题。在真实数据集上的实验显示,在不同的支持度下IITM算法都要要优于Apriori、FP-growth以及PIETM算法。     

关联规则挖掘在游戏视频销售中的研究与应用

数据挖掘是一项热门技术,该技术融合了数据库、统计学等领域知识,关联规则的挖掘则能找出商品销售中商品之间的联系。本文针对Apriori算法,及其改进算法FP-Growth进行了研究,对比了Apriori算法与FPGrowth算法的效率,得出FP-Growth算法由于只需要对数据进行一次扫描即可生成相应的数据集,使其生成数据集的整体效率要高于Apriori算法。     

从不确定图中挖掘频繁子图模式

研究不确定图数据的挖掘,主要解决不确定图数据的频繁子图模式挖掘问题.介绍了一种数据模型来表示图的不确定性,以及一种期望支持度来评价子图模式的重要性.利用期望支持度的Apriori性质,给出了一种基于深度优先搜索策略的挖掘算法.该算法使用高效的期望支持度计算方法和搜索空间裁剪技术,使得计算子图模式的期望支持度所需的子图同构测试的数量从指数级降低到线性级.实验结果表明,该算法比简单的深度优先搜索算法快3～5个数量级,有很高的效率和可扩展性.     

挖掘最大频繁模式的新方法

由于其内在的计算复杂性，挖掘密集型数据集的频繁模式完全集非常困难，解决方案之一是挖掘最大频繁模式集．该文在频繁模式完全集挖掘算法Opportune Project基础上，提出了挖掘最大频繁模式的新算法MOP．它采用宽度与深度优先相结合的混合搜索策略，能恰当地选择不同的支持集表示和投影方法，将闭合性剪裁和一般性剪裁相结合，并适时前窥，实现搜索与剪裁效率最优化．实验表明，MOP效率是MaxMiner的2～8倍，比MAFIA高2个数量级以上．     

基于频繁2项集支持矩阵的Apriori改进算法

捕要：Apriori算法在关联规则挖掘过程中需要多次扫描事务数据库,产生大量候选项目集,导致计算量过大。为解决该问题,提出一种基于频繁2项集支持矩阵的Apriori改进算法,通过分析频繁k＋1项集的生成机制,将支持矩阵与频繁2项集矩阵相结合实现快速剪枝,并大幅减少频繁k项集验证的计算量。实验结果表明,与Apriori算法和ABTM算法相比,改进算法明显提高了频繁项集的挖掘效率。     

改进的频繁模式挖掘算法

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

基于混合投影的频繁模式挖掘算法

频繁模式挖掘是最基本的数据挖掘问题，由于内在复杂性，提高挖掘算法性能一直是个难题．耶是通过数据库混合投影来挖掘频繁模式完全集的全新算法．HP混合投影思想是：任意数据集都不能简单地归入某个单一特性类别，挖掘过程应根据局部数据子集的特性变化动态地调整频繁模式树构造策略、事务子集表示形式、投影方法．HP提出基于树表示的虚拟投影与基于数组表示的非过滤投影，较好地解决了提高时间效率与节省内存空间的矛盾．实验表明，HP时间效率比Apriori，FP—Growth和H-Mine高出1～3个数量级，并且空间可伸缩性也大大优于这些算法．     

压缩FP-Tree的改进搜索算法

为克服Apriori算法候选频繁项集的支持数计算效率过低和频繁模式增长算法 FP‐Grow th多次建立条件模式树时内存耗费大的问题,提出基于压缩频繁模式树（CFP‐Tree）的改进搜索算法（MCFP‐Tree）。利用Apriori算法候选项集生成的思想和压缩频繁模式树紧凑的数据结构,采用自底向上的搜索策略,快速挖掘压缩频繁模式树及其子树,更快得到候选项集的支持数。实验结果表明,该算法可以高效计算出候选频繁项集出现的频次,挖掘效率明显优于 Apriori和 FP‐Grow th算法。     

挖掘闭合模式的高性能算法

频繁闭合模式集惟一确定频繁模式完全集并且尺寸小得多,然而挖掘频繁闭合模式仍然是时间与存储开销很大的任务.提出一种高性能算法来解决这一难题.采用复合型频繁模式树来组织频繁模式集,存储开销较小.通过集成深度与宽度优先策略,伺机选择基于数组或基于树的模式支持子集表示形式,启发式运用非过滤虚拟投影或过滤型投影,实现复合型频繁模式树的快速生成.局部和全局剪裁方法有效地缩小了搜索空间.通过树生成与剪裁代价的平衡实现时间效率与可伸缩性最大化.实验表明,该算法时间效率比其他算法高5倍到3个数量级,空间可伸缩性最佳.它可以进一步应用到无冗余关联规则发现、序列分析等许多数据挖掘问题.     

Mining frequent closed patterns in pointset databases

In this paper, we proposed an efficient algorithm, called PCP-Miner (Pointset Closed Pattern Miner), for mining frequent closed patterns from a pointset database, where a pointset contains a set of points. Our proposed algorithm consists of two phases. First, we find all frequent patterns of length two in the database. Second, for each pattern found in the first phase, we recursively generate frequent closed patterns by a frequent pattern tree in a depth-first search manner. Since the PCP-Miner does not generate unnecessary candidates, it is more efficient and scalable than the modified Apriori, SASMiner and MaxGeo. The experimental results show that the PCP-Miner algorithm outperforms the comparing algorithms by more than one order of magnitude.     

基于线索频繁模式树的关联规则产生算法

虽然FP-Growth算法能够有效地从数据库中挖掘频繁模式,但如何由其挖掘出的频繁模式中高效地产生关联规则仍是一个相当复杂的问题。该文提出了用于组织频繁模式的线索频繁模式树(TFPT)和一个从TFPT中挖掘关联规则的高效算法—最短模式优先算法(SPF)。挖掘模式Y的关联规则时,SPF算法应用了两个优化策略,避免了对大量的不可能成为规则XY-X左部的Y的子集的检查,从而获得了很好的性能。实验表明:与类FP-Growth算法结合时,SPF算法运行速度远远快于Apriori算法,并有相当好的可伸缩性。     

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.     

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.     

Fast Discovery Of Long Patterns For Association Rules

The most time consuming process in discovering association rules is identifying the frequent patterns especially in the cases when the database contains long patterns. An algorithm called Flex for identifying frequent patterns especially efficient when the patterns are long is proposed by successive construction of the nodes lexicographic tree. The vertical counting strategy to facilitate fast discovery is used in support computation. The experimental result shows that Flex outperform Apriori, a well-known and widely used algorithm for patterns discovery.     

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     

基于Apriori算法的改进算法

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

基于日历的时序关联规则挖掘算法

以日历格作为框架来研究时序关联规则，提出了一个有效的挖掘算法。在用户指定的日历模式下，首先通过一次扫描产生所有的频繁2项集及相应的1*日历模式，在此基础上产生k*日历模式，并利用聚集性质产生候选K项集及相应的日历模式，最后扫描事务数据库产生所有的频繁项集及其日历模式。实验证明，该算法具有较好的性能。