对于不确定性数据,传统判断项集是否频繁的方法并不能准确表达项集的频繁性,同样对于大型数据,频繁项集显得庞大和冗余。针对上述不足,在水平挖掘算法Apriori的基础上,提出一种基于不确定性数据的频繁闭项集挖掘算法UFCIM。利用置信度概率表达项集频繁的准确性,置信度越高,项集为频繁的准确性也越高,且由于频繁闭项集是频繁项集的一种无损压缩表示,因此利用压缩形式的频繁闭项集替代庞大的频繁项集。实验结果表明,该算法能够快速地挖掘出不确定性数据中的频繁闭项集,在减少项集冗余的同时保证项集的准确性和完整性。

For the uncertain data, traditional method of judging whether an itemset is frequent cannot express how close the estimate is, meanwhile frequent itemsets are large and redundant for large datasets. Regarding to the above two disadvantages, this paper proposes a mining algorithm of frequent closed itemsets based on uncertain data called UFCIM to mine frequent closed itemsets from uncertain data according to frequent itemsets mining method from uncertain data, and it is based on level mining algorithm Apriori. It uses probability of confidence to express how close the estimate is, the larger that probability of confidence is, the itemsets are more likely to be frequent. Besides as frequent closed itemsets are compact and lossless representation of frequent itemsets, so it uses compacted frequent closed itemsets to take place of frequent itemsets which are of huge size. Experimental result shows the UFCIM algorithm can mine frequent closed itemsets effectively and quickly. It can reduce

频繁项集挖掘是数据挖掘研究领域的一个基本问题,其瓶颈在于频繁项集全集的结果过多,冗余现象严重,而频繁闭项集能唯一确定频繁项集且规模小得多。针对如何快速生成频繁闭项集,分析不可分辨矩阵、概念格和频繁闭项集之间的关系,提出一种新的更有利于生成频繁闭项集的格结构,并给出相应的渐进式生成算法和频繁闭项集提取算法。实验表明该方法能够高效地挖掘频繁闭项集。

Frequent itemset mining is one of the fundamental problems in data mining research field.The crux of frequent itemsets mining is that the resultant itemsets of full sets of frequent itemset are usually extremely much, and hence the redundancy phenomenon is serious. The frequent closed itemset is the one can only exactly determine the frequent itemsets and with much smaller size.In this paper, for generating the frequent closed itemset rapidly, we analyse the relationship among the indistinguishable matrix, the concept lattice and the frequent closed itemsets, and propose a new lattice structure which benefits more to generating the frequent closed itemsets. The corresponding algorithms of incremental generation and frequent closed itemsets extraction are also presented.Experiments demonstrate that the method can efficiently mine the frequent closed itemsets.

研究频繁项集模式挖掘优化问题。传统的挖掘算法常产生大规模的候选项集,并且反复扫描数据库,导致频繁项集挖掘时间过长,空间效率太低。为了改进频繁项集挖掘时时间与空间效率低的问题,提出一种高效频繁项集挖掘算法CPT-Mine。此算法利用编码模式树存储事务数据库中的频繁项集信息,构建FP数组,加快产生频繁项集,引入CPT-Mine算法,快速地挖掘数据库中所包含的频繁项集,无需递归构造条件模式树,只需两次扫描数据库即可生成所有频繁项集。最后的实验证明了该算法能缩短挖掘时间3～10 s,空间效率提高43%。

The frequent itemsets mining optimization model is researched. Traditional mining is often produce large-scale candidate itemsets, and repeatedly scanning database, the time is too long, lead to frequent itemsets mining space efficien-cy is too low. Frequent itemset mining is to improve the problem of low efficiency of time and space, put forward an efficient algorithm for mining frequent itemsets CPT-Mine. The algorithm using encoding scheme tree store information of frequent itemsets of transaction databases construction of FP array, to speed up the produce frequent itemsets, the introduction of CPT-Mine algorithm, fast, frequent itemsets mining database contains no recursive model tree structure conditions, only two times of scanning database can generate all frequent itemsets. The experiment proves that this algorithm can shorten the mining time 3~10 s, space efficiency increased by 43%.

Apriori算法在关联规则挖掘过程中需要多次扫描事务数据库,产生大量候选项目集,导致计算量过大。为解决该问题,提出一种基于频繁2项集支持矩阵的Apriori改进算法,通过分析频繁k+1项集的生成机制,将支持矩阵与频繁2项集矩阵相结合实现快速剪枝,并大幅减少频繁k项集验证的计算量。实验结果表明,与Apriori算法和ABTM算法相比,改进算法明显提高了频繁项集的挖掘效率。

As Apriori algorithm used for mining association rules can lead to a large number of candidate itemsets and huge computations, an improved Apriori algorithm based on frequency 2-item set support matrix is proposed. By analyzing the generation mechanism of frequent k+1 item sets, the improved algorithm combines assistant matrix and frequent 2-item matrix to realize rapid purning, it can trim infrequent item set quickly and reduce the amount of calculation of k frequent item set verification. Experimental result shows that frequent itemsets mining efficiency of improved algorithm increases significantly compared with Apriori algorithm and ABTM algorithm.

为了进一步降低扫描数据库的次数和减轻内存负担,从而更好地提高挖掘频繁项集的效率,一种基于Apriori的优化算法(M-Apriori)被提出.该方法通过构建频繁状态矩阵来存放项集的频繁状态,构建事务布尔矩阵来存放事务与项集的关系,此算法只需在初始化阶段扫描一次数据库产生初始的频繁状态矩阵和事务布尔矩阵,并在此基础上直接递推产生所有的频繁项集.实验证明,与Apriori算法相比,M-Apriori算法具有更好的性能与效率.

To reduce the number of database scanning and reduce the burden of memory further, also to improve the efficiency of mining frequent itemsets better, an Apriori-based optimization algorithm (M-Apriori) is proposed. The method stores frequent itemsets state by constructing the frequent state matrix and store the relationship between the transaction and itemsets by constructing the Boolean matrix. The algorithm scans the database only once and generates the initial frequent state matrix and the Boolean matrix during the initialization phase. On this basis, all frequent itemsets can be found directly without scanning the database repeatedly. Experiments show that M-Apriori algorithm has better performance and efficiency compared with the Apriori algorithm.