王秉政[1]2003年在《基于FP-树的频繁模式和长模式挖掘》文中研究指明数据库的规模急剧膨胀，数据库应用的不断深化，但是数据库管理系统却没有提供有效的工具和方法来利用这些数据，出现了数据丰富而知识贫乏的状况，导致了数据挖掘的出现。作为数据挖掘中重要任务之一的频繁模式的挖掘，被应用在关联规则、相关分析、序列模式、显露模式、最长模式等许多重要数据挖掘任务中，得到了广泛研究。 长期以来，挖掘频繁模式主要采用Apriori算法及其改进形式，这类算法需要产生大量候选项集，并反复扫描数据库，降低了挖掘的效率。FP-Growth算法是一种基于模式增长的频繁模式挖掘算法，避免了大量候选项集的产生，只需要两次扫描数据库。效率比Apriori算法快一个数量级。然而，此算法及其改进形式在挖掘频繁模式时不可避免地需要递归地创建附加数据结构，并且每当模式增长时就要创建一次。动态地创建如此大量的附加数据结构，将耗费大量时间和空间。并且以上算法对于不同特点的数据库没有较好的适应性。 本文基于模式增长的思想，提出两种新的频繁模式挖掘算法：最小项优先的挖掘方法和最大项优先的挖掘方法。其通过采用一定的挖掘策略，使整个挖掘过程直接在初始生成的压缩的数据结构中进行，而不需要另外递归创建附加的数据结构。使频繁模式挖掘的效率得到了进一步的提高。使用相同的数据集，性能研究表明：算法速度大约是FP-Growth算法3～4倍，而所需要的存储空间不到FP-Growth算法的一半。对于稠密数据集，算法的优势更加显着。 利用深度优先的方法符合最长模式挖掘的性质，基于最小项优先的频繁模式挖掘算法，提出了新的挖掘长模式算法。采用挖掘尽可能长的频繁模式和忽略对与约束项集具有相同支持计数的项处理的策略，大大地减少了算法的搜索空间；具有分而治之性质的过滤策略较大地提高了算法的效率。在相同条件下使用相同的数据集，与最近出现的同类算法相比，效率提高几倍，特别是对于稠密数据集，效率更加明显。
王洪立[2]2008年在《基于频繁模式树的关联规则算法研究》文中进行了进一步梳理数据挖掘是近年来迅速发展的信息处理技术,从大量的、不完全的、有噪声的、模糊的、随机的数据中,提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。它涉及数据库、人工智能、机器学习、模式识别、知识工程、面向对象、信息检索和可视化等一系列技术。关联规则挖掘作为数据挖掘领域的一个重要研究分支,它的任务是发现所有满足支持度阈值和置信度阈值的强关联规则。关联规则挖掘算法是关联规则挖掘研究的主要内容,迄今为止已经提出了许多高效的关联规则挖掘算法。本文对经典的Apriori和AprioriTid算法以及不产生候选集的FP-Growth算法进行了分析和研究。FP-Growth算法比Apriori算法在性能上有了很大提高,它仅需要扫描数据库两次,并且避免了产生大量的候选项集。但FP-Growth算法主要的瓶颈之一就是空间开销大。为了节省空间,提高频繁项的发现效率,本文对传统的频繁模式树和项头表进行了优化,采用动态构造哈希链地址的方法来构造项头表,FP-Tree的每个结点只存储该项在项头表中的地址,避免了在地址上出现空指针,节省了存储空间的开销,同时增加树结点的域实现了方便的双向遍历。此外还通过对事务数据库按一定的规则进行了划分,得到若干个数据库子集,然后分别对每个数据库子集进行数据挖掘,因而占用内存小,解决了内存无法装入频繁模式树的问题,使数据挖掘得以顺利进行。最后通过实验对基于频繁模式树的关联规则挖掘的优化算法与传统的频繁模式树的FP-Growth算法进行了比较,实验结果表明在挖掘大量数据信息时更有效。
刘慧玲[3]2009年在《频繁模式挖掘算法LPS-Miner及其并行模式研究》文中研究表明从大型数据库中挖掘频繁模式是数据挖掘研究的一类基本问题,也是该领域经久不衰并迅速发展的热点。由于实际应用数据规模之大维数之多的特性,使得对于具有高性能和良好可扩展性的关联规则挖掘算法的研究一直是该领域的研究热点。本文的研究内容就是围绕设计高效的频繁模式挖掘算法以及将其向并行环境的移植展开的,主要包括:1、设计和实现高效的频繁模式挖掘算法LPS-Miner本文对频繁模式挖掘的经典算法进行了深入研究,提出了适应较大规模数据集下频繁模式挖掘的LPS-Miner算法,该算法提出了两种数据结构LPS-FP-Tree和LPS-FP-Forest来表示事务数据库,通过消除父亲-孩子指针,压缩了节点的大小,并在很大程度上降低了访问树的代价。LPS-Miner算法极大地应用了分治的策略,保证每棵操作树相对较小并且相互独立。而且,非递归挖掘单频繁分枝,高性能内存管理,频繁模式输出I/O优化以及剪枝技术的运用,都保证了LPS-Miner达到较好的性能。实验结果表明,不论在稠密或者稀疏的数据集上,LPS-Miner算法都能比较高效的完成频繁模式挖掘任务。2、基于分布式内存的LPS-Miner并行算法的研究和设计本文针对分布式内存并行计算环境,设计了LPS-Miner的并行算法。由于LPS-Miner充分利用了分治的策略,各个LPS-FP-Tree之间相互独立且挖掘结果没有交集。所以,LPS-Miner并行化的工作是相对简单和有效的。并行LPS-Miner采用主从模式,由主节点向从节点分配任务和收集结果,并对数据划分、通信和负载均衡等问题进行了优化,使得LPS-Miner并行算法对于处理大规模数据集上的频繁模式挖掘问题具有更高的效率和可扩展性。
王斌, 刘向宇, 杨晓春, 王国仁[4]2012年在《频繁模式溯源》文中研究说明数据起源是关于数据来源、转换和更新过程的研究。基于频繁模式挖掘的性质和特点,提出了FP+树来记录频繁模式来源。给出了频繁模式溯源的相关理论和证明,根据不同追溯机制提出了叁种频繁模式溯源方法,并对方法的正确性和执行代价给出了理论证明和推导。在进行频繁模式挖掘时,在不增加额外负担的情况下实现了频繁模式溯源。针对条件FP+树结构特点和频繁模式性质,提出了采用α-剪枝求解条件FP+树的投影操作,加快了频繁模式挖掘和数据溯源的执行效率。实验结果显示,采用基于FP+树的频繁模式溯源方法,可以高效地实现频繁模式溯源,并且条件FP+树的α-剪枝策略的有效性得到验证。
李志洁[5]2004年在《一种基于模式变换的高效关联规则挖掘算法》文中提出挖掘事务数据库、时间序列数据库中的频繁模式已经成为数据挖掘中很受关注的研究方向。以前的研究大致可以归纳为两类：一类是类似于Apriori的候选集产生与测试方法，但是在频繁模式较长时，生成候选集需要很大开销；另一类是不产生候选集的算法如FP-growth算法，它比Apriori算法有较大的性能提高，但仍存在着一定的缺点：通过条件模式基的分析产生频繁模式仍然需要大量的开销。 本文针对FP-growth算法的不足，给出一种基于频繁模式树的频繁模式挖掘算法FP-reduce。它采用FP-tree的数据结构来存储所有的频繁模式信息并对FP-树的每一个结点都进行剩余保存，即对每一项集中的每一项都复制一份除去该项的剩余项集，并将其添加到FP-树中，这样就可以在保存了原来项集的信息的基础上对原来的项集进行处理：保留或者删除，而不丢失信息。剩余保存使得所需计算的频繁模式不断地缩短，最终可得到所有的二项以上的频繁项集形成的FP-树。 理论和实验表明，该算法具有优良的性能，特别是当数据集扩大到一定程度后，FP-reduce在线性方面要优于FP-growth。
阮幼林[6]2004年在《频繁模式挖掘算法及在入侵检测中的应用研究》文中研究说明随着网络和其它信息技术的广泛应用,网络系统的安全变得至关重要。入侵检测系统是保护网络系统安全的关键技术和重要手段,但现行的入侵检测不仅对新的攻击或特征未知的入侵无能为力,而且检测的准确性与实时性均达不到实际应用的需求。频繁模式挖掘是数据挖掘研究中一个重要的研究内容,可以从海量数据中发现正常和异常的行为模式, 将其用于入侵检测不仅可以有效地检测已知入侵, 而且还具有检测未知攻击模式的能力,具有更高的准确性和适应性。因此,针对入侵检测中的数据特点,研究频繁模式的高效挖掘算法及其并行化方法对于提高入侵检测的准确性和时效性具有非常重要的理论意义和实用价值。针对现有挖掘算法存在的多趟扫描数据、动态维护复杂、更新效率低等问题,提出了一种基于前缀树的频繁模式挖掘算法 PT-Mine 和更新算法 UPT-Mine。PT-Mine 算法利用前缀树压缩存放数据,通过调整前缀树中相关节点信息和节点链直接在前缀树上采用深度优先的策略挖掘频繁模式,不需要任何附加的数据结构, 而且每次挖掘只需前缀树的一棵子树即可。因此,本算法既有效地节省了存储空间,又提高了挖掘的效率和可扩展性。更新算法 UPT-Mine 利用事务树及通过事务树的转换实现前缀树的更新,只需对新增数据扫描一次而无须扫描原始数据,从而大大提高了频繁模式的更新效率。由于最大频繁模式隐含了所有频繁模式, 因此可以用来描述系统的正常行为模型和攻击行为模型。随着网络环境的变化和新的攻击模式的不断出现,入侵检测模型需要不断更新和完善。因此,研究最大频繁模式的高效挖掘和更新算法对于提高入侵检测的准确性和可扩展性是非常重要的。为此,在挖掘算法 PT-Mine 的基础上,提出了一种基于前缀树的最大频繁模式快速挖掘算法 DMFP。本算法不需要产生大量候选集和创建条件模式树,挖掘效率明显优于其它算法。针对现有算法更新难、代价大等问题,提出了增量式更新算法 IUMFP 和阈值更新算法 UMFP。这两种更新算法充分利用 I<WP=5>已有的挖掘结果, 高效地发现最新事务数据库中所有的最大频繁模式。 对于网络入侵数据的高维数和大尺寸以及分布性,高性能的并行挖掘算法是提高检测效率的有效途径。针对传统的并行算法存在的诸如大量候选集的生成、通信代价高、多次同步等问题,提出了一种基于分布数据的并行频繁模式挖掘算法 PMFP。本算法通过分析局部频繁模式和全局频繁模式的关系,尽可能地让每个处理器独立地挖掘, 并通过相关性质尽量减少候选全局频繁模式的规模,从而减少网络的通信量和同步次数以提高挖掘效率。由于候选全局频繁模式的挖掘只需搜索事务树中对应该模式的路径即可,无须对各站点的原始数据进行扫描,从而大大提高全局频繁模式的挖掘效率。考虑各站点的数据量比较悬殊、负载不平衡的情况,提出了一种基于复制的平衡调度算法 TDBS。TDBS 算法充分考虑各站点的负载和利用处理机的空闲时间段,把任务尽量分配到已用的处理机上以均衡负载、提高利用率, 进而提高并行挖掘算法PMFP 的加速比和总体效率。 由于现行的入侵检测系统建立的正常模式和异常模式不够准确、完善, 容易造成误警或漏警, 往往会给网络系统造成巨大损失。据此,提出了一种基于频繁模式挖掘的入侵检测方法。本方法首先通过挖掘训练数据集中的最大频繁模式建立系统和用户的正常行为模型和攻击模型,并通过滑动窗口对实际数据进行并行挖掘和标记,能够更加精确、快速地区分用户的正常行为和异常行为;并及时更新、不断优化入侵检测模型,从而提高入侵检测的准确性和可靠性。实验结果表明,通过不断更新和选择合适的相关参数,本方法可以提高检测的精度和时效性。
刘乃丽[7]2005年在《基于FP-树的关联规则挖掘算法的设计与实现》文中认为数据挖掘技术是解决数据丰富而知识贫乏的有效途径,当属信息科学领域的前沿研究课题之一,有关的研究和应用极大提高了决策支持的能力,它已被公认为是数据库研究中一个极富应用前景的领域。本文描述了数据挖掘的概念、功能以及发现模式的分类。在众多的数据挖掘算法中,挖掘关联规则是数据挖掘领域中的重要研究内容,其中挖掘频繁项目集是挖掘关联规则中的关键问题之一,又最大频繁项目集已经隐含了所有的频繁项目集,所以可以将发现频繁项目集的问题转化为发现最大频繁项目集的问题,因而发现最大频繁项目集对数据挖掘具有重大意义。 以前的许多挖掘最大频繁项目集算法是先生成候选集,再进行检验,然而候选项目集产生的代价是很高的,尤其是存在大量长模式的时候。本文主要在以下几个方面对基于FP-树的关联规则挖掘问题进行研究:第一是研究了FP-树的定义和构造过程以及多种改进算法,并分析了基于FP-树进行挖掘的可行性和完整性,然后提出了基于FP-树的快速挖掘最大频繁项目集的算法Max-FI(Maximal Frequent Itemset),该算法不需要生成最大频繁候选项目集。改进的FP-树是单向的,每个节点只保留指向父节点的指针,这大约节省了叁分之一的树空间。试验结果表明该算法比同样基于FP-树的DMFIA算法挖掘最大频繁项目集的效率更高。 第二是研究了挖掘有效且无冗余关联规则的问题。传统算法在生成关联规则时,或者生成规则的效率很低,或者生成的关联规则之间存在着大量的冗余,或者挖掘出的规则的支持度和可信度都很高,但却是无趣的、甚至是虚假的规则,且不能产生带有否定项的规则。本文提出了一种新的算法MVNR(Mining Valid and non-Redundant Association Rules Algorithm),在该算法中,首先对频繁项集集合进行检查,删除了那些只能生成冗余关联规则的频繁项集,然后对分析过的频繁项集集合中的每一个频繁项集生成他们的极小子集集合,
孙杜靖[8]2017年在《基于Storm的流关联挖掘算法实现及应用》文中进行了进一步梳理从海量数据中发现关联规则一直是数据挖掘研究的热点,尽管学术界已提出了许多基于静态数据集的关联挖掘算法,但由于流数据具有持续、无限、高速产生的特性,在流数据中隐藏的知识很可能随着时间的推移而产生变化,因而仍需要研究新的面向流数据的关联挖掘算法。为了更好地分析在线流数据,基于不同的时间粒度从流数据中抽取关联规则,并提高流数据的关联挖掘的效率,本文基于FP-Stream算法,借助MapReduce并行编程模型,设计了针对流数据的关联挖掘算法DPFP-Stream(Distributed Parallel Frequent Patterns Mining Algorithm for Stream Data,简称DPFP-Stream);并将该算法在Storm平台上实现。在实现方案中,数据源采用消息中间件Kafka,并将中间结果通过序列化技术存入内存数据库Redis中。多方位的实验结果与分析表明,该算法从高速的数据流中发现关联规则的效率很高且性能稳定,且支持不同时间粒度。为了验证该算法的实用性,本文将DPFP-Stream算法应用到穿搭购物推荐系统中去,通过分析达人穿衣搭配规律及用户购买规律,实时更新关联规则,根据用户浏览的商品推荐其搭配的衣服。经正确性测试和性能测试,发现该系统响应时延小,用户体验良好,说明基于Storm实现的DPFP-Stream算法能很好地应用到穿搭购物推荐系统中去,能实现推荐商品的准确、高效投放。
刘君强, 潘云鹤[9]2003年在《一种基于树的频繁模式挖掘算法》文中研究说明提出了一种基于树的频繁模式挖掘算法 TBA-FP.它以树表示法压缩数据库所含模式信息 ,将挖掘问题转化为按深度优先策略构造频繁模式树 ,并引入了虚拟裁剪等优化技术 .实验表明 ,TBA-FP挖掘“长”模式的时间效率与空间可伸缩性远远优于经典算法 Apriori
陈向华[10]2016年在《一种改进的关联规则算法研究与应用》文中进行了进一步梳理随着数据挖掘技术迅速而深入的发展,关联规则及其相关技术也得到越来越多的学者和研究人员的关注。关联规则挖掘能从大量的数据集中挖掘出隐含的、对决策有潜在价值的项集之间的有趣关联和相关关系,其应用的背景也从最初的购物篮分析扩展到网络入侵检测、用户消费习惯分析、关联规则分类、交通事故模式分析、软件bug挖掘等。因此,对关联规则技术的研究具有重要的实际意义,本文选择了这一主题进行了分析和研究。本文首先介绍了数据挖掘领域的研究内容、挖掘的方法和技术、当前的研究现状以及应用和发展趋势,接着对关联规则挖掘技术中的经典算法(Apriori、FP-growth等)进行了概述、分析和总结,在此基础上提出了一种基于最大频繁项集的关联规则挖掘算法MFIP-Miner算法。该算法将数据库中的事务通过频繁模式树(FP-Tree)压缩存储,并充分利用频繁模式树的性质,严格控制在挖掘过程中递归调用的终结条件,从而达到提升算法的性能的目的。其次,本文完成了实验平台的搭建,选用R语言,在Eclipse +StatET编程环境中实现了 MFIP-Miner算法,并对比MFIP-Miner算法与FP-growth算法、Mafia算法在选定数据库上的运行效率。实验结果显示,该算法的性能具有优越性。最后,将MFIP-Miner算法运用于天气敏感性疾病预报系统中,完成了该系统的设计和实现,通过对该系统各模块的测试,验证了预报的准确性。
参考文献：
[1]. 基于FP-树的频繁模式和长模式挖掘[D]. 王秉政. 郑州大学. 2003
[2]. 基于频繁模式树的关联规则算法研究[D]. 王洪立. 哈尔滨工程大学. 2008
[3]. 频繁模式挖掘算法LPS-Miner及其并行模式研究[D]. 刘慧玲. 兰州大学. 2009
[4]. 频繁模式溯源[J]. 王斌, 刘向宇, 杨晓春, 王国仁. 计算机科学与探索. 2012
[5]. 一种基于模式变换的高效关联规则挖掘算法[D]. 李志洁. 大连理工大学. 2004
[6]. 频繁模式挖掘算法及在入侵检测中的应用研究[D]. 阮幼林. 华中科技大学. 2004
[7]. 基于FP-树的关联规则挖掘算法的设计与实现[D]. 刘乃丽. 山东大学. 2005
[8]. 基于Storm的流关联挖掘算法实现及应用[D]. 孙杜靖. 南京邮电大学. 2017
[9]. 一种基于树的频繁模式挖掘算法[J]. 刘君强, 潘云鹤. 系统工程理论与实践. 2003
[10]. 一种改进的关联规则算法研究与应用[D]. 陈向华. 北京邮电大学. 2016
标签：计算机软件及计算机应用论文; 数据挖掘论文; 关联规则论文; fp-growth论文; 数据挖掘算法论文; 入侵检测技术论文; 算法论文;