共查询到20条相似文献,搜索用时 17 毫秒
1.
基于向量和矩阵的频繁项集挖掘算法研究 总被引:1,自引:0,他引:1
为了能快速、高效地从事务数据库中挖掘所有的频繁项集,提出了一种基于向量和矩阵的VMA高效算法.该算法只需扫描数据库一次,将事物数据库转化到布尔向量中,对频繁1-项集按支持度大小进行非递减排序,排序后在很大程度上减少了用于扩展的k-项集(k>2),生成一个2-项集支持度矩阵,由频繁k-项集(k≥2)扩展生成频繁(k+1)-项集.大量实验结果表明,VMA算法的性能不但明显优于Apriori算法,而且适应于大型事务数据库中频繁项集挖掘. 相似文献
2.
针对经典Apriori算法在迭代过程中频繁扫描数据库,且动态数据更新后需要重新处理数据的不足,提出一种基于二进制编码的增量更新改进CBEF-Apriori算法。该算法的核心思想是将添加增量后的项集、事务转换成二进制编码,从而将计算项集支持度转化为项集与事务数据库的二进制编码位运算过程。改进算法筛选原数据库生成的频繁项集与增量数据库新生成的候选项集,有效减少了候选项集的规模,提高算法效率的同时更符合现实需要。实验结果表明,相比于经典Apriori算法和CBE-Apriori算法,改进算法在挖掘出正确频繁项集的数量不降低的情况下,明显提升了计算效率,在小数据规模下相比经典Apriori算法最高提升3.6倍,相比CBE-Apriori算法最高提升1.4倍。在较大数据规模下相比经典Apriori算法最高提升10.41倍,相比CBE-Apriori算法最高提升11.53倍。 相似文献
3.
捕要:Apriori算法在关联规则挖掘过程中需要多次扫描事务数据库,产生大量候选项目集,导致计算量过大。为解决该问题,提出一种基于频繁2项集支持矩阵的Apriori改进算法,通过分析频繁k+1项集的生成机制,将支持矩阵与频繁2项集矩阵相结合实现快速剪枝,并大幅减少频繁k项集验证的计算量。实验结果表明,与Apriori算法和ABTM算法相比,改进算法明显提高了频繁项集的挖掘效率。 相似文献
4.
Apriori算法是数据挖掘领域挖掘关联规则频繁项目集的经典算法,但该算法存在产生大量的候选项目集及需要多次扫描数据库的缺陷。为此提出一种新的挖掘关联规则频繁项目集算法( CApriori算法):利用分解事务矩阵来压缩存放数据库的相关信息,进而对分解事务矩阵进行关联规则挖掘;优化了由频繁k -1项目集生成频繁k项目集的连接过程;提出了一种不需要扫描数据库,利用行集“与运算”快速计算支持数的方法,改进算法挖掘所有的频繁项目集只需扫描数据库两次。实验结果表明,改进算法在最小支持度较小时效率高于Apriori算法。 相似文献
5.
6.
7.
8.
9.
10.
11.
通过研究项集之间的关系,发现大项集之间存在着一种特定的关系,即k-项集一定是由一个(k-1)-项集加上一个单独的项构成的。基于这种项集关系,本文提出基于前缀树的TIUA算法,算法摆脱了传统算法多次迭代的不足,并利用挖掘出的结果,只需扫描一次数据库,就能满足各种要求,通过以空间换时间,达到提高挖掘效率的目的。 相似文献
12.
Komate Amphawan Philippe Lenca Athasit Surarerks 《Expert systems with applications》2012,39(2):1924-1936
Temporal regularity of itemset appearance can be regarded as an important criterion for measuring the interestingness of itemsets in several applications. A frequent itemset can be said to be regular-frequent in a database if it appears at a regular period. Therefore, the problem of mining a complete set of regular-frequent itemsets requires the specification of a support and a regularity threshold. However, in practice, it is often difficult for users to provide an appropriate support threshold. In addition, the use of a support threshold tends to produce a large number of regular-frequent itemsets and it might be better to ask for the number of desired results. We thus propose an efficient algorithm for mining top-k regular-frequent itemsets without setting a support threshold. Based on database partitioning and support estimation techniques, the proposed algorithm also uses a best-first search strategy with only one database scan. We then compare our algorithm with the state-of-the-art algorithms for mining top-k regular-frequent itemsets. Our experimental studies on both synthetic and real data show that our proposal achieves high performance for small and large values of k. 相似文献
13.
根据粗糙集中多属性的等价类求解方法,提出一种事务数据库频繁项集的挖掘算法,该算法只在发现1-频繁项集时需扫描数据库,算法效率比Apriori算法要高. 相似文献
14.
为了提高经典关联规则Apriori算法的挖掘效率,针对Apriori算法的瓶颈问题,提出了一种链式结构存储频繁项目集并生成最大频繁项目集的关联规则算法.该算法采用比特向量方式存储事务,生成频繁项目集的同时,把包含此频繁项目的事务作为链表连接到频繁项目之后,生成最大频繁项目集.该算法能够减小扫描事物数据库的次数和生成候选项目集的数量,从而减少了生成最大频繁项目集的时间,实验结果表明,该算法提高了运算效率. 相似文献
15.
司晓梅 《计算机与数字工程》2009,37(11):25-27,32
Apriori算法是经典的频繁项目集生成算法,在数据挖掘界起着里程碑的作用。但是该算法要求多次扫描可能非常大的交易数据库。文章在Apriori算法的基础上,提出了一种改进的关联规则挖掘算法-GBARM。该算法能够使得每次扫描的事务数大大减少,并且能够逐步减小候选k-项集的规模,从而改善算法的性能。 相似文献
16.
Apriori算法必须反复地扫描数据库才能求出频繁项集,效率较低,且不支持更新挖掘。为了解决这些问题,提出了一种基于粗糙集、单事务项组合和集合运算的关联规则挖掘算法。本算法首先利用粗糙集进行属性约简,对新决策表中的每个事务进行“数据项”组合并标记地址,然后利用集合运算的方法计算支持度和置信度即可挖掘出有效规则。本算法只需要一次扫描数据库,同时有效地支持了关联规则的更新挖掘。应用实例和实验结果表明,本算法明显优于Apriori算法,是一种有效且快速的关联规则挖掘算法。 相似文献
17.
《Knowledge》2007,20(4):329-335
Mining frequent itemsets in transaction databases, time-series databases and many other kinds of databases is an important task and has been studied popularly in data mining research. The problem of mining frequent itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying those itemsets that meet the frequent itemset requirement within this candidate set. Most of the previous research mainly focuses on pruning to reduce the candidate itemsets amounts and the times of scanning databases. However, many algorithms adopt an Apriori-like candidate itemsets generation and support count approach that is the most time-wasted process. To address this issue, the paper proposes an effective algorithm named as BitTableFI. In the algorithm, a special data structure BitTable is used horizontally and vertically to compress database for quick candidate itemsets generation and support count, respectively. The algorithm can also be used in many Apriori-like algorithms to improve the performance. Experiments with both synthetic and real databases show that BitTableFI outperforms Apriori and CBAR which uses ClusterTable for quick support count. 相似文献
18.
现有的数据挖掘方法大致有两类:有候选项集和无候选项集,有候选项集的挖掘以Apriori算法为代表,其特点是产生大量的候选项集,重复多次扫描数据库,挖掘效率低,不适合大型数据库的挖掘。无候选项集的挖掘以FP-T方法为代表,但它不能同时挖掘多概念层的关联规则,对具有超大项ID的大型数据库,无法生成“树”结构,使用也受到限制。该文将FP-T原理引入多层关联规则的并发挖掘,通过构建一个特殊节点链的指针表,可实现超大规模数据库的并发、多层挖掘。对实现物流系统信息自动化及其它数据挖掘应用领域都具有极其重要的指导意义。 相似文献
19.
Jong Soo Park Ming-Syan Chen Yu P.S. 《Knowledge and Data Engineering, IEEE Transactions on》1997,9(5):813-825
We examine the issue of mining association rules among items in a large database of sales transactions. Mining association rules means that, given a database of sales transactions, to discover all associations among items such that the presence of some items in a transaction will imply the presence of other items in the same transaction. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items that appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying, within this candidate set, these itemsets that meet the large itemset requirement. Generally, this is done iteratively for each large k-itemset in increasing order of k, where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate sets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we develop an effective algorithm for the candidate set generation. It is a hash-based algorithm and is especially effective for the generation of a candidate set for large 2-itemsets. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. The advantage of the proposed algorithm also provides us the opportunity of reducing the amount of disk I/O required. An extensive simulation study is conducted to evaluate performance of the proposed algorithm 相似文献