改进的频繁项集挖掘算法

频繁项集挖掘是数据挖掘中的一个重要研究课题。在分析Apriori算法与FP-growth 算法特点的基础上,提出了一种改进的频繁项集挖掘算法,即索引生成频繁项集算法IGFA。IGFA算法基于Apriori算法并通过 “索引二元组”生成候选集,减免了候选集的大量冗余,实验及结果分析表明该算法有效提高了频繁项集的挖掘效率。     

基于图的关联规则改进算法

关联规则挖掘是数据挖掘研究的最重要课题之一。基于图的关联规则挖掘DLG算法通过一次扫描数据库构建关联图,然后遍历该关联图产生频繁项集,有效地提高了关联规则挖掘的性能。在分析该算法基本原理基础上,提出了一种改进的算法—DLG#。改进算法在关联图构造同时构造项集关联矩阵,在候选项集生成时结合关联图和Apriori性质对冗余项集进行剪枝,减少了候选项集数,简化了候选项集的验证。比较实验结果表明,在不同数据集和不同支持度阈值下,改进算法都能更快速的发现频繁项集,当频繁项集平均长度较大时性能提高明显。     

一种改进的Apriori算法

关联规则挖掘是数据挖掘研究领域中的一个重要任务,旨在挖掘事务数据库中有趣的关联。Apriori算法是关联规则挖掘中的经典算法。然而Apriori算法存在着产生候选项目集效率低和频繁扫描数据等缺点。提出了一种新的Apriori的改进算法,该算法在生成k(k>1)项频繁集时,不需要重新扫描数据库,只是在生成1项频集时,才需要扫描事务数据库,有效地减少了对事务数据库的读操作,在时间复杂度上较经典的Apriori算法有更加优越的性能。     

高效的一次性弱间隙序列模式挖掘算法

间隙约束序列模式挖掘作为序列模式挖掘的一个重要分支,可以发现模式在序列中的重复出现。然而,当前研究主要针对单项序列进行挖掘,并且序列中每一项都被认为具有相同意义。为解决该问题,提出一次性弱间隙序列模式挖掘（OWP）算法,该算法由准备阶段、支持度计算和候选模式生成3个步骤组成。在准备阶段,建立倒排索引,并对不频繁的项进行剪枝;在支持度计算方面,利用倒排索引结构记录出现位置,避免对原始数据集的重复扫描;在候选模式生成方面,采用模式连接策略,减少冗余候选模式的生成。在项集序列和单项序列共6个真实数据集上的实验结果表明,OWP算法相比OWP-p、Ows-OWP和OWP-e算法在运行时间上分别提升了2.653、1.348、3.592倍,在内存消耗上分别减少了3.51%、0.07%、5%,说明OWP算法可以更高效地挖掘出用户感兴趣的模式。此外,OWP算法在以D1数据集为基础的6倍大小的数据集上的运行时间比D1数据集增长了3.763倍,内存消耗增长了2.310倍,运行时间和内存消耗的增加倍数均小于数据集大小的增加倍数,说明OWP算法具有良好的可扩展性。     

Apriori算法用于频繁子图挖掘的改进方法

AGM算法最早将Apriori思想应用到频繁子图挖掘中。AGM算法结构简单,以递归统计为基础,但面临庞大的图数据集时,由于存在子图同构的问题,在生成候选子图时容易产生很多冗余子图,使计算时间开销很大。基于AGM算法,针对候选子图生成这一环节对原算法进行改进,减少了冗余子图的生成,使改进后的算法在计算时间上具有高效性;测试了在不同最小支持度情况下改进方法的时间开销。实验结果表明改进算法比原算法缩短了计算时间,提高了频繁子图的挖掘效率。     

改进的序列模式挖掘在医院转诊中的应用

为了研究患者在不同医院间的转诊行为模式, 可以使用序列模式挖掘算法. 类Apriori算法是序列模式挖掘中的常用算法, 但该算法存在一些不足之处, 如产生候选序列的数目较多、需要频繁扫描数据库. 针对类Apriori算法存在的不足, 本文提出了相应的改进措施, 采用新的剪枝策略并减少不必要的数据库扫描操作. 实验证明, 改进后的算法能更高效地挖掘频繁转诊序列.     

RAKING:一种高效的不确定图K-极大频繁模式挖掘算法

由于不确定图蕴含了指数级的可能图实例,基于确定图模型的频繁图模式挖掘算法通常难以在不确定图集合上高效运行.文中提出了一种不确定图数据集上的基于随机游走的K极大频繁子模式挖掘算法.首先,将每个不确定图转换为相应的确定图并挖掘候选频繁模式;然后,将候选频繁模式恢复为不确定图并生成极大频繁模式搜索空间;最后,通过随机游走以相同概率随机地选择K个极大频繁模式.理论分析和实验结果表明文中提出的算法能够高效地获得不确定图集合的K-极大频繁模式.     

一种有效的基于图的关联规则挖掘算法

基于图的关联规则挖掘算法是一种通过构建关联图并直接生成候选频繁项集，进而验证得到所有频繁项集的算法。在该算法中，对候选项集的验证操作占用了大量的时间，为此提出了改进算法。改进主要体现在两个方面：按支持度降序对频繁1项重新编号再构建关联图；利用Apriori性质删减用来生成候选项集的冗余扩展项节点。实验结果表明，在最小支持度阈值较小时，改进算法有效减少了冗余的候选频繁项集，提高了算法的性能。     

一种新的改进的Apriori算法

本文通过时关联规则挖掘算法Apriori算法的分析和研究,指出了其在具体应用中存在的主要问题.提出与以往不同的改进策略:在约简数据库事务的同时,生成频繁项目集和保存具有非频繁子集候选项目集的项集,在提高频繁项目集即关联规则生成效率的同时,进一步减少了对候选项目集的重复验证.最后将改进的Apriori算法应用到一个Web交叉销售系统,并和经典的Apriori算法进行了比较,取得了较好的效果.     

基于频繁图模式挖掘的质量管理过程分析

提出了基于频繁图模式挖掘的工作流频繁活动序列分析的方法，分析了质量管理过程中的关键活动链结构，辅助质量管理过程控制和改进。针对质量管理过程循环结构多且复杂的特点，提出了一种基于Apriori的改进频繁活动序列挖掘算法，设计了新的子图连接算子，减少冗余候选频繁子图的产生。以质量外审意见处理流程的分析为例对该算法进行了说明和分析。     

基于Spark的并行频繁模式挖掘算法

在大数据环境下Apriori频繁模式挖掘算法在数据处理过程具有预先设定最小阈值、时间复杂度高等缺陷, 为此采用多阶段挖掘策略实现并行化频繁模式挖掘算法PTFP-Apriori。首先将预处理数据以模式树的形式存储,通过最为频繁的[k]个模式得到最优阈值。然后根据该值删除预期不能成长为频繁的模式以降低计算规模,并利用弹性分布式数据集RDD完成统计项集支持度计数、候选项集生成的工作。实验分析表明相比于传统的频繁模式挖掘算法,该算法具有更高的效率以及可扩展性。     

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

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

一种挖掘带时间约束序列模式的改进算法

针对带时间约束的序列模式，提出了一种改进的挖掘算法TSPM，克服了传统的序列模式挖掘方法时空开销大，结果数量巨大且缺少针对性的缺陷．算法引入图结构表示频繁2序列，仅需扫描一次数据库，即可将与挖掘任务相关的信息映射到图中，图结构的表示使得挖掘过程可以充分利用项目之间的次序关系，提高了频繁序列的生成效率．另外算法利用序列的位置信息计算支持度，降低了处理时间约束的复杂性，避免了反复测试序列包含的过程．实验证明，该算法较传统的序列模式发现算法在时间和空间性能上具有优越性。     

Efficient data mining for calling path patterns in GSM networks

In this paper, we explore a new data mining capability that involves mining calling path patterns in global system for mobile communication (GSM) networks. Our proposed method consists of two phases. First, we devise a data structure to convert the original calling paths in the log file into a frequent calling path graph. Second, we design an algorithm to mine the calling path patterns from the frequent calling path graph obtained. By using the frequent calling path graph to mine the calling path patterns, our proposed algorithm does not generate unnecessary candidate patterns and requires less database scans. If the corresponding calling path graph of the GSM network can be fitted in the main memory, our proposed algorithm scans the database only once. Otherwise, the cellular structure of the GSM network is divided into several partitions so that the corresponding calling path sub-graph of each partition can be fitted in the main memory. The number of database scans for this case is equal to the number of partitioned sub-graphs. Therefore, our proposed algorithm is more efficient than the PrefixSpan and a priori-like approaches. The experimental results show that our proposed algorithm outperforms the a priori-like and PrefixSpan approaches by several orders of magnitude.     

Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach

Mining frequent patterns in transaction databases, time-series databases, and many other kinds of databases has been studied popularly in data mining research. 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 a large number of patterns and/or long patterns.In this study, we propose a novel frequent-pattern tree (FP-tree) structure, which is an extended prefix-tree structure for storing compressed, crucial information about frequent patterns, and develop an efficient FP-tree-based mining method, FP-growth, for mining the complete set of frequent patterns by pattern fragment growth. Efficiency of mining is achieved with three techniques: (1) a large database is compressed into a condensed, smaller data structure, FP-tree which avoids costly, repeated database scans, (2) our FP-tree-based mining adopts a pattern-fragment growth method to avoid the costly generation of a large number of candidate sets, and (3) a partitioning-based, divide-and-conquer method is used to decompose the mining task into a set of smaller tasks for mining confined patterns in conditional databases, which dramatically reduces the search space. Our performance study shows that the FP-growth method is efficient and scalable for mining both long and short frequent patterns, and is about an order of magnitude faster than the Apriori algorithm and also faster than some recently reported new frequent-pattern mining methods.     

基于中医方剂数据库的Top-Rank-k频繁模式挖掘算法

为降低中医（TCM）方剂频繁模式挖掘过程中对经验参数的依赖,提高挖掘结果的准确性,针对中医方剂的数据特点,提出一种基于带权无向图的Top-Rank-k频繁模式挖掘算法。该算法可以直接挖掘出频繁k-itemset（k≥3）而无需产生1-itemset和2-itemset,并随之快速回溯到核心药物组合的频繁项集所对应的方剂信息;此外,采用一种动态位向量（DBV）的压缩机制对无向图中边的权重进行压缩存储,以有效地提高算法的空间存储效率。分别对中医方剂数据集、真实数据集（Chess、Pumsb和Retail）和合成数据集（T10I4D100K和Test2K50KD1）进行测试和比较,结果表明该算法与iNTK和BTK相比具有更高的时间和空间效率,而且也可以应用于其他类型的数据集。     

基于路径的频繁子图挖掘算法研究

图挖掘是数据挖掘的一个重要研究方向,而图挖掘主要集中在图数据集内频繁子图的挖掘。频繁子图挖掘技术的关键是建立有效机制减少冗余候选子图,以便高效计算和处理所需的频繁子图。提出了一种基于路径的频繁子图挖掘算法,该算法首先找出所有频繁边从而挖掘出频繁单路径,然后通过组合、双射和操作扩展出较多的频繁路径,再通过连接操作产生所有频繁子图候选集。通过定理证明了该算法的正确性和完整性,从理论上分析了该算法时间复杂度低于现有的算法,最后进行了2个图数据集实验,在候选集产生的数量和时间性能2方面验证了算法的优越性。     

无候选项的频繁邻近类别集挖掘算法

针对现有的频繁邻近类别集挖掘算法因产生候选项而存在冗余计算,提出一种无候选项的频繁邻近类别集挖掘算法,其适合在海量数据中挖掘空间对象的频繁邻近类别集;该算法以交叉搜索方式,用产生邻近类别集非空真子集的方法来计算支持数,实现一次扫描数据库挖掘频繁邻近类别集。算法无需产生候选频繁邻近类别集,且计算支持数时无需重复扫描数据库,达到了提高挖掘效率的目的。实验结果表明其在海量空间数据中挖掘频繁邻近类别集时,该算法比现有算法更快速更有效。     

基于SQL的不产生候选集的频繁模式挖掘

频繁模式挖掘是数据库挖掘中的一个十分重要的组成部分，然而以前的许多研究都是基于Apriori的产生候选集的测试迭代方法。这些方法普遍存在需要多次扫描数据库，对产生的大量候选集进行迭代测试的缺陷，尤其是对于挖掘长模式时这种缺陷就尤为突出。FP-growth方法采用分而治之的策略，只需对数据库进行二次扫描，而且避免了产生大量候选集的问题。文中的基于SQL的频繁模式挖掘方法既是在此基础上提出的，采用子查询及DBMS扩展技术(如用户定义函数等)对该方法进行了改进。