Hadoop框架下的一种改进的Apriori算法

常见的基于Hadoop框架的Apriori改进算法在统计支持度时有扫描数据集、候选项集剪枝等方面效率低下且集群间的数据传输有较大的时间开销的问题,提出了一种Apriori的改进算法Apriori_Ind.算法运用Hadoop集群,使用先按事务对数据集分块,再将数据集的格式转换为项,事务集的分块处理策略,使算法充分利用分布式计算优势,实现各节点并行的实现候选项集生成与剪枝操作.并利用前项与后项的新结构表示频繁项集,新结构在各节点进行候选项集生成和剪枝时提高算法效率.Apriori_Ind具有减小集群传输代价、加速剪枝等优势.实验表明新算法适合大规模数据挖掘,特别是项的数量较大的情况下,算法性能有明显的提高.     

基于FP-tree的最大频繁项集挖掘算法

现有的最大频繁项集挖掘算法在支持度阈值较大情况下已达到较高性能,但在支持度阈值较小时,由于候选项集的快速增长,其性能往往不理想。文章提出了一种基于频繁模式树(FP-tree)存储结构的最大频繁项集挖掘算法——DMFIF算法,将FP-tree各分枝作为初始候选项集,并按维数和支持度递减排序,结合子集剪枝策略,自顶向下搜索挖掘最大频繁项集。实验结果表明,该算法在低支持度阈值下稠密数据集中挖掘长模式具有较好性能。     

一种改进的Eclat算法

提出一种改进的Eclat算法.该算法在垂直数据表示方式上执行广度优先搜索和交叉计数.新算法充分利用了垂直数据表示和交叉计数的高效优势,以及Apriori算法的剪枝策略,减少了计数的候选项集的数量.实验结果表明,改进的Eclat算法的运行速度较Eclat算法有了明显的提高.     

基于DSCFCI_tree的带项目约束的数据流频繁闭合模式挖掘算法

根据数据流的特点,提出了一种挖掘约束频繁闭合项集的算法,该算法将数据流分段,用DSCFCI_tree动态存储潜在约束频繁闭合项集,对每一批到来的数据流,首先建立局部DSCFCI_tree,进而对全局DSCFCI_tree进行有效更新并剪枝,从而有效地挖掘整个数据流中的约束频繁闭合模式.实验表明,该算法具有很好的时间和空间效率.     

NB-MAFIA: 基于N-List的最长频繁项集挖掘算法

本文在深度优先搜索的框架上, 引入基于项集前缀树节点链表的项集表示方法N-List, 提出一个高效的最长频繁项集挖掘算法NB-MAFIA。N-List的高压缩率和高效的求交集方法可以实现项集支持度的快速计算, 同时采用对搜索空间的剪枝策略和超集检测策略来提高算法效率。在多个真实和仿真数据集上, 通过实验评估了NB-MAFIA和两个经典算法。实验结果表明NB-MAFIA在多数情况下优于其他算法, 尤其在真实和稠密数据集上优势更为明显。     

一种改进的Apriori算法在精准扶贫中的应用研究

随着精准扶贫建档立卡工作的实施,精准扶贫系统已积累了大量数据,利用高效的关联规则算法挖掘其中隐含的有用信息对助力精准扶贫工作具有重要意义。本文针对贫困户建档立卡数据的数据重复率高,属性多样特点,提出一种改进的Apriori算法,利用对矩阵的数据结构和集合的相关性质来构建候选项集,避免重复扫描数据库以及逐层的剪枝连接运算,提高算法挖掘效率;通过对实际贫困户建档立卡数据进行挖掘,证明了该算法在最小支持度阈值较低的条件下挖掘效率优于传统Apriori算法。     

基于ESCS剪枝策略的闭频繁项集挖掘算法

由于在现有的闭频繁项集挖掘算法中,剪枝策略相对单一,大都是针对1-项集进行剪枝,对2-项集和n-项集(n≥3)的剪枝策略相对匮乏,而有效的剪枝策略可以提前发现并剪掉大量没有希望的项集,因此改进闭频繁项集的剪枝策略对此类算法效率的提升具有很大的帮助。为此在ESCS(Estimated Support Co-occurrence Structure)结构基础上,提出针对2-项集的ESCS剪枝策略,并应用其将经典闭频繁项集挖掘算法DCI＿Closed(Direct Count Intersect Closed)改进为DCI＿ESCS(Direct Count Intersect Estimated Support Co-occurrence Structure)算法,同时对ESCS剪枝策略的效果加以验证。在多个公开数据集上、不同最小支持度阈值下,对改进前后算法时间性能进行比较实验。实验结果表明,改进的DCI＿ESCS算法在事务和项集较长的、较稠密的数据集上表现良好,时间效率均有一定程度的提高。     

分布式全局最大频繁项集更新挖掘算法

提出了针对数据水平分布的分布式数据集下的全局最大频繁项集更新挖掘算法（UDMFI）,用于解决当最小支持度阈值发生变化时全局最大频繁项集的更新挖掘问题.通过提出的带项目头表的频繁模式树（HFP-Tree）来存储数据,然后根据最小支持度阈值变小时,原最大频繁项集的集合中的元素一定是新最大频繁项集的集合中某些元素的子集的特性,以及最小支持度阈值变大时,原最大频繁项集中的一些最大频繁项集将可能不再是新最大频繁项集的集合中的最大频繁项集的特性,充分利用已挖掘的结果,从而减少挖掘过程中的费用.实验结果表明该算法具有较好的效率.     

基于MapReduce的Eclat改进算法研究与应用

针对Eclat算法在挖掘海量数据中的频繁项目集时存在的内存和计算资源不足等问题,将Eclat算法与目前流行的大规模数据集并行编程模型MapReduce结合,解决了Eclat算法在数据挖掘过程存在的瓶颈问题,运用于动车组故障诊断系统中,提高了关联规则挖掘的效率.     

基于动态双重前缀的模糊相似性连接算法

针对相似性连接问题， 提出了动态双重前缀的模糊相似性连接算法.与之前的算法不同的是，本文采用双重前缀，即在查找候选以及构建索引时使用不同的前缀来提高过滤效率，并在此基础上进行了优化.首先通过取各个前缀生成的候选集合的交集来缩小候选集合;其次提出最大区分任选前缀，利用此前缀进行预验证来减少最终进入到验证过程的候选对，以此来减少连接时间.并且在三个真实数据集上进行实验，将本文算法与Silkmoth算法以及MF-Join算法进行比较，结果表明所提算法可以生成更小的候选集集合并且需要更少的连接时间.     

事务约简和2项集支持度矩阵快速剪枝的Apriori改进算法

在Apriori算法的改进算法M-Apriori基础上,为了进一步减少不必要的数据库扫描,引入事务约简技术,提出一种改进的MR-Apriori算法.考虑到M-Apriori算法会产生大量候选项集,为了实现对候选项集快速剪枝,加入一个自定义的2项集支持度矩阵,提出第2种改进的MP-Apriori算法.将事务约简和2项集矩阵快速剪枝一起引入到 M-Apriori算法中,提出第3种改进的MRP-Apriori算法.最后,在mushroom数据集上进行实验.结果表明:加入事务约简的MR-Apriori算法和加入2项集矩阵快速剪枝的MP-Apriori算法,运行时间相比原M-Apriori算法都有较大缩减,而同时结合两种优化策略的MRP-Apriori算法运行时间最短,验证了这两种优化策略的有效性.     

一种改进的Eclat算法

首先,深入分析了频繁模式挖掘算法Eclat和Eclat+,在大数据集上挖掘长模式时,Eclat+的性能不及Eclat。基于此,提出一种改进的Eclat算法,新算法充分利用了垂直数据表示和交叉计数的高效优势,直接在垂直数据表示的数据集上通过广度优先搜索和交叉计数产生频繁模式。实验结果表明,在挖掘长模式时,改进的Eclat算法的运行速度较Eclat、Eclat+均有明显的提高。     

一种基于分治策略与位运算的频繁项集挖掘算法

为提高挖掘频繁项集的效率,在垂直数据格式下,结合分治思想提出一种基于分治策略与位运算频繁项集挖掘算法DC-FIMBII。利用分治将数据库中的事务划分为多个非重叠部分,对每一部分采用位运算求交计算支持度,从而减少操作时项集的规模和项集的比较次数。在mushroom、pumsb_star和T40I10D100K等数据集上,对DC-FIMBII、Apriori、Eclat、DF-FIMBII等算法进行比较。实验表明,DC-FIMBII具有更高的效率。     

基于集合和剪枝原理的关联规则隐藏算法

针对传统关联规则隐藏算法直接遍历数据集,而导致输入输出流资源浪费的问题,提出一种基于集合和剪枝原理的关联规则隐藏算法。该算法首先建立频繁模式树(FP-tree),利用后剪枝原理去除属性相同规则,减少了遍历原始数据集所耗I/O时间;然后通过建立集合来保存真实频繁序列,并以集合为单位隐藏关联规则,既保证数据集质量,又提高频繁序列挖掘效率。实验结果表明,该算法与GSP、SPADE算法相比较,不仅更好地保证了数据集的高质量,而且降低了20%～50%频繁序列挖掘时间,并在隐藏敏感规则上有较好的实用性。     

最大频繁项集挖掘中搜索空间的剪枝策略

最大频繁项集挖掘可以广泛应用在多种重要的Web挖掘工作中.为了有效地削减搜索空间,提出了一种新的最大频繁项集挖掘中的搜索空间剪枝策略.这种策略基于深度优先遍历词典序子集枚举树,利用树中子节点与父节点扩展集中相同项的扩展支持度相等的特性,对搜索空间进行剪枝.应用该策略,对MAFIA算法进行改进优化.实验结果表明,该剪枝策略可以有效削减搜索空间,尤其在稀疏但包含长频繁项集的数据集上,搜索空间削减掉2/3,算法的时间效率比原MAFIA算法提高3～5倍.     

DMBIT：一种有效的序列模式挖掘算法

大量候选序列模式支持度的计算所带来的时间消耗是序列模式挖掘主要问题之一,为此提出了一种有效的序列模式挖掘算法:DMBIT(Data Mining Bitmap),该算法根据位索引表和Seq-list表的结构,采用渐进的事件扩展,事务扩展方法,通过有效的剪枝策略和"与"逻辑运算操作进一步缩小了频繁序列的搜索范围,同时通过序列列表ListX的生成加快了相应候选项支持度的计算,算法分析和实验结果表明,在大数据集环境下的DMBIT算法性能优越,能够明显加速数据库中最大频繁序列的生成.     

一种基于布尔向量的Apriori改进算法

从分析布尔向量与项集支持度的相关性质人手,利用计算机的逻辑"与"运算的高效率性以及通过布尔向量计算项集支持度的简单性,提出了基于布尔向量的关联规则挖掘算法.该算法只需一次扫描数据库,无需候选项集和"剪枝"操作,极大地提高了算法的效率.     

数据挖掘中关联规则算法的研究及应用

针对Apriori和AprioriTid算法中存在的项集生成瓶颈问题,提出了一种基于事务集压缩、候选项集压缩和支持度布尔矩阵的改进AprioriTid算法.该算法中通过删去不必比较的事务来有效缩减数据集;优化频繁项集的自连接方式来减少生成的候选项集个数;使用支持度布尔矩阵来加快候选项集的验证速度.实验结果表明改进算法比原算法执行效率明显提高,同时也验证了该算法在油液监测故障诊断中的有效性.     

基于频繁模式半结构化数据的模式抽取

为克服半结构化数据存储复杂的缺点,提出一种基于动态树的半结构化的存储模型。对该模型进行模式抽取, 并将其引入到Apriori算法。通过设置最小支持度阀值过滤掉不必要的信息, 输出最长频繁路径的集合, 以实现半结构化数据的提取。实验结果表明, 该算法能同时有效地处理分支及环路问题, 避免了死循环的出现。     

一种基于云计算的新的关联规则Apriori算法

Apriori算法是经典的数据挖掘算法之一,它根据置信度和支持度对产生的频繁集进行选择,找出强规则.传统的Apriori算法需要产生大量的侯选集和多次数据库的扫描,存储和通信的开销巨大.云计算环境可以解决存储问题,所以针对Mapreduce的编程框架,提出一种适用于此模式的新关联规则算法,解决传统Apriori算法时间和空间上的缺点,提高挖掘效率.