共查询到19条相似文献,搜索用时 93 毫秒
1.
频繁项集挖掘FIM是最重要的数据挖掘任务之一,被挖掘数据集的特征对FIM算法的性能有着显著影响。在大数据时代,稀疏是大数据的典型特征之一,对传统FIM算法的性能带来严峻挑战。针对在稀疏数据中如何高效进行FIM的问题,从稀疏数据的特征出发,分析了稀疏数据对3种类型FIM算法性能的主要影响,对已经提出的稀疏数据FIM算法进行了综述,对算法中采用的优化策略进行了讨论,最后通过实验对代表性的稀疏数据FIM算法进行了性能分析。实验结果表明,采用伪构造策略的模式增长算法最适合用于稀疏数据的FIM,在运算时间和存储空间上,相比其他算法该算法具有较大的优势。 相似文献
2.
3.
4.
5.
基于频繁项集挖掘算法的改进与研究 总被引:1,自引:1,他引:1
关联规则挖掘是数据挖掘领域中重要的研究内容,频繁项集挖掘又是关联规则挖掘中的关键问题之一。针对已有的频繁项集挖掘算法存在的问题,通过对Apriori算法的分析,提出了Inter-Apriori频繁项集挖掘算法。该算法使用交集策略减少扫描数据库的次数,从而使算法达到较高的效率。实验结果表明,Inter-Apriori算法是Apriori算法效率的2~4倍。 相似文献
6.
7.
程杰 《数字社区&智能家居》2009,5(5):3486-3488
频繁项集挖掘是数据挖掘中的一个经典的问题。然而,大部分算法需要扫描数据库多次,算法效率比较低。该文提出了一个效率比较好的挖掘频繁项集的新算法,在这个算法中,所有的事务都是以二进制的形式表示,所以挖掘极大频繁项集的任务就变成了从二进制集中发现频繁模式。而且,这种算法只需要扫描原始数据库一次。最后,利用试验来证明这种算法的效率和优势。 相似文献
8.
模式树是目前频繁项集挖掘最常用的数据结构,使用模式树可以有效地将数据库压缩于内存,并在内存中完成对频繁项集的挖掘。为了进一步提高频繁项集挖掘算法的可扩展性,本文对模式树进行了细致的研究,在此基础上提出了一种挖掘频繁项集的新算法,FP-DFS算法。该算法通过对模式树的各种操作简化了对频繁项集的搜索过程。实验表明,该算法对于频繁项集挖掘具有比较高的效率。 相似文献
9.
程杰 《数字社区&智能家居》2009,(13)
频繁项集挖掘是数据挖掘中的一个经典的问题。然而,大部分算法需要扫描数据库多次,算法效率比较低。该文提出了一个效率比较好的挖掘频繁项集的新算法,在这个算法中,所有的事务都是以二进制的形式表示,所以挖掘极大频繁项集的任务就变成了从二进制集中发现频繁模式。而且,这种算法只需要扫描原始数据库一次。最后,利用试验来证明这种算法的效率和优势。 相似文献
10.
一种改进的基于矩阵的频繁项集挖掘算法 总被引:1,自引:0,他引:1
如何从海量数据信息中挖掘出有用的关联规则已经成为人们广泛关注的问题,而在关联规则挖掘中,首要的问题就是如何高效地挖掘出频繁项集.针对已有FIMM算法作出改进,提出了一种改进的基于矩阵的频繁项集挖掘算法NFIMM,该算法在FIMM基础上去除大量冗余的非频繁项集的项集,减少计算可能频繁项集的工作量,同时缩小了矩阵规模,提高了空间效率.通过对矩阵操作,一次性地产生所有的频繁项集.试验结果表明,该算法对已有的基于矩阵的频繁项集挖掘算法有了很大的改进,提高了挖掘效率. 相似文献
11.
针对PrePost算法中需要建立复杂的前序和后序编码树(PPC-tree)和节点链表(N-list)的问题,提出一种基于间隔链表(I-list)改进的高效频繁项集挖掘算法。首先,该算法采用了比频繁模模式树(FP-tree)更加压缩的数据存储结构间隔编码的频繁模式树(IFP-tree),无需迭代地建立条件FP-tree;其次,该算法利用更简洁的I-list代替了PrePost中复杂的N-list,从而提高了建树和挖掘速度;最后,对于单分支路径的情况,该算法通过组合的方法,直接求得某些频繁项集,以提高算法的时间性能。实验结果表明:一方面,对于同一数据集在相同支持数下挖掘的结果相同,验证了改进算法的正确性;另一方面,无论在时间还是空间上改进算法的整体性能均比PrePost算法提高约10%;且对于稀疏型数据库或密集型数据库的挖掘都有较好的应用。 相似文献
12.
基于FP-tree的最大频繁模式挖掘算法是目前较为高效的频繁模式挖掘算法,针对这些算法需要递归生成条件FP-tree、产生大量候选最大频繁项集等问题,在分析FPMax、DMFIA算法的基础上,提出基于降维的最大频繁模式挖掘算法(BDRFI)。该算法改传统的FP-tree为数字频繁模式树DFP-tree,提高了超集检验的效率;采用的预测剪枝策略减少了挖掘的次数;基于降低项集维度的挖掘方式,减少了候选项的数目,避免了递归地产生条件频繁模式树,提高了算法的效率。实验结果表明,BDRFI的效率是同类算法的2~8倍。 相似文献
13.
对于频繁项集挖掘,采用一种FP-数组技术来减少FP-tree的遍历时间,减少数据集的扫描次数,在此基础上提出了一种基于FP-tree进行频繁项集挖掘的FP-growth+算法,提高了算法的效率。最后的实验证明了该算法的有效性。 相似文献
14.
发现最大频繁项目集是数据挖掘应用中的关键问题;为寻求避免生成大量的候选项集,或生成频繁模式树的挖掘算法,提出一种从事务项集对应的最大频繁项集求全部属性项集的最大频繁项集的新算法IPA(Intersection Pruning Algorithm)。该算法通过交集剪枝实现自顶向下和自底向上的搜索最大频繁项集,并使用属性项的分布数据和已生成的交集等多种信息来减少求交集的次数;该算法最多只用求(1-最小支持度)×|D|+1个事务项集和其他事务项集的交集,从而可有效降低算法的时间复杂度;实验表明该算法有效可行,并且该算法易于实现。 相似文献
15.
基于改进FP-tree的最大频繁项集挖掘算法 总被引:7,自引:1,他引:7
现有的最大频繁项集挖掘算法在挖掘过程中需要进行超集检测,基于FP-tree的算法需要递归的建立条件频繁模式树,挖掘效率不高.提出了一种基于改进FP-tree高效挖掘最大频繁项集的算法(MMFI).该算法修改了FP-tree结构并采用NBN策略,在挖掘过程中既不需要进行超集检测也不需要递归的建立条件频繁模式树.算法分析和实验结果表明,该算法是一种有效、快速的算法. 相似文献
16.
17.
18.
Amol Ghoting Gregory Buehrer Srinivasan Parthasarathy Daehyun Kim Anthony Nguyen Yen-Kuang Chen Pradeep Dubey 《The VLDB Journal The International Journal on Very Large Data Bases》2007,16(1):77-96
Algorithms are typically designed to exploit the current state of the art in processor technology. However, as processor technology evolves, said algorithms are often unable to derive the maximum achievable performance on these modern architectures. In this paper, we examine the performance of frequent pattern mining algorithms on a modern processor. A detailed performance study reveals that even the best frequent pattern mining implementations, with highly efficient memory managers, still grossly under-utilize a modern processor. The primary performance bottlenecks are poor data locality and low instruction level parallelism (ILP). We propose a cache-conscious prefix tree to address this problem. The resulting tree improves spatial locality and also enhances the benefits from hardware cache line prefetching. Furthermore, the design of this data structure allows the use of path tiling, a novel tiling strategy, to improve temporal locality. The result is an overall speedup of up to 3.2 when compared with state of the art implementations. We then show how these algorithms can be improved further by realizing a non-naive thread-based decomposition that targets simultaneously multi-threaded processors (SMT). A key aspect of this decomposition is to ensure cache re-use between threads that are co-scheduled at a fine granularity. This optimization affords an additional speedup of 50%, resulting in an overall speedup of up to 4.8. The proposed optimizations also provide performance improvements on SMPs, and will most likely be beneficial on emerging processors. 相似文献
19.
FrequentItemsetMining (FIM) is one of the most important data mining tasks and is the foundation of many data mining tasks. In Big Data era, centralized FIM algorithms cannot meet the needs of FIM for big data in terms of time and space, so Distributed Frequent Itemset Mining (DFIM) algorithms have been designed to meet the above challenges. In this paper, LocalGlobal and RedistributionMining which are two main paradigms of DFIM algorithm are discussed; Two algorithms of these paradigms on MapReduce named LG and RM are proposed while MapReduce is a popular distributed computing model, and also the related work is discussed. The experimental results show that the RM algorithm has better performance in terms of computation and scalability of sites, and can be used as the basis for designing the DFIM algorithm based on MapReduce. This paper also discusses the main ideas of improving the DFIM algorithms based on MapReduce. 相似文献