关联规则中频繁与高效用项集挖掘算法研究

发布时间：2018-05-06 12:10

本文选题：频繁项集 + 事务约简　；参考：《华侨大学》2017年硕士论文

【摘要】：关联规则最早是挖掘频繁项集,以支持度为度量,挖掘数据库中频繁出现的项集模式。考虑到数据库中每个项目在事务中可以出现多次,并且不同项目可以有不同的权重,频繁项集被扩展到高效用项集挖掘,高效用项集挖掘能使用用户期望的效用度量方式挖掘出更符合用户需求的结果。本文主要围绕关联规则中的频繁项集挖掘算法与高效用项集挖掘算法的时间效率提升展开,具体内容包括以下2个方面:1)基于事务约简和2-项集支持度矩阵快速剪枝的Apriori改进算法。首先自定义了保存频繁1-项集的数据结构,计算候选项集支持度时,依据这个自定义的数据结构决定扫描的事务,之后引入事务约简优化,进一步对数据库中项目和事务进行约简,提出改进的MR-Apriori算法。随后,定义一种2-项集支持度矩阵,对候选项集进行快速剪枝,提出了改进后的MP-Apriori算法。再次,结合MR-Apriori和MP-Apriori算法改进策略,提出了改进的MRP-Apriori算法。最后,在mushroom和T10I4D100K进行实验,结果表明:改进的MRApriori算法和改进的MP-Apriori算法,运行时间都比原Apriori算法减少,而结合这两种改进策略的MRP-Apriori算法运行时间最短,从而最终验证了三种算法改进的时间效率。2)基于数组伪投影和事务合并的频繁高效用项集挖掘算法。在分析了单独考虑支持度或效用值的缺陷后,本文提出一种基于数组伪投影数据结构、递归构造前缀项集的投影数据库挖掘频繁高效用项集的算法。算法将支持度和效用值这两种度量手段同时考虑,挖掘数据库中那些出现次数频繁且效用值高的项目集合。为减小算法的搜索空间,提出了局部效用剪枝和子树效用剪枝两种剪枝方案,基于算法模型和上述剪枝方案提出FUIM-P算法。随后,观察到数据库中有许多可以合并的事务,根据FUIM-P算法的特点,将这种合并被扩展到投影数据库,引入了事务(投影事务)合并技术。同时,提出了一种自定义排序规则,以在线性时间内找到满足可以快速合并的条件的事务,提出最终的FUIM-MP算法。最后在mushroom、chess和accident数据集上进行实验,结果表明:FUIM-P算法的运行时间相比对比的FHIMA-ALL算法缩短,而加入了事务(投影事务)合并技术的FUIM-MP算法则较前两者时间效率有非常大的提升;另外,实验中mushroom、chess和accident数据集中大量可合并事务(投影事务)数目也很好地证明了事务(投影事务)合并提高算法运行时间的有效性。
[Abstract]:Association rules are the earliest mining frequent itemsets, which are measured by support degree, and mining itemsets patterns that occur frequently in database. Considering that each item in the database can occur multiple times in a transaction and that different items can have different weights, frequent itemsets are extended to highly effective itemsets mining, High utility itemsets mining can use the expected utility metrics to extract the results that are more suitable to the users' needs. This paper mainly focuses on the time efficiency improvement of frequent itemset mining algorithm and high effective itemset mining algorithm in association rules. The specific contents include the following two aspects: 1) an improved Apriori algorithm based on transaction reduction and 2-item set support matrix fast pruning. Firstly, the data structure with frequent 1-itemsets is defined, and when the support degree of candidate itemsets is calculated, the scanned transactions are determined according to this self-defined data structure, and then the optimization of transaction reduction is introduced. Furthermore, the project and transaction in the database are reduced, and an improved MR-Apriori algorithm is proposed. Then, a 2-item set support matrix is defined, and the candidate item set is pruned quickly, and an improved MP-Apriori algorithm is proposed. Thirdly, an improved MRP-Apriori algorithm is proposed based on the improved strategy of MR-Apriori and MP-Apriori algorithm. Finally, the experiments on mushroom and T10I4D100K show that both the improved MRApriori algorithm and the improved MP-Apriori algorithm have less running time than the original Apriori algorithm, but the MRP-Apriori algorithm with these two improved strategies has the shortest running time. Finally, the improved time efficiency. 2) algorithm based on array pseudo projection and transaction merging for mining frequent and high effective itemsets is verified. After analyzing the defect of considering support degree or utility value separately, this paper presents an algorithm of mining frequent and high-utility item sets in projection database based on array pseudo projection data structure and recursively constructing prefix item set. The algorithm takes both support and utility measures into account to mine the set of items in the database that occur frequently and have high utility value. In order to reduce the search space of the algorithm, two kinds of pruning schemes, local utility pruning and sub-tree utility pruning, are proposed. The FUIM-P algorithm is proposed based on the algorithm model and the above pruning schemes. Then, it is observed that there are many transactions in the database that can be merged. According to the characteristics of the FUIM-P algorithm, the merging is extended to the projection database, and the technology of transaction merging is introduced. At the same time, a custom collation rule is proposed to find the transaction satisfying the condition of fast merging in linear time, and the final FUIM-MP algorithm is proposed. Finally, experiments are carried out on the mush roomless and accident datasets. The results show that the running time of the accident / FUIM-P algorithm is shorter than that of the contrast FHIMA-ALL algorithm, while the FUIM-MP algorithm which adds the transaction (projection transaction) merging technique has a great improvement on the time efficiency of the former two algorithms. In addition, the number of merge transactions (projection transactions) in mush room ess and accident datasets also proves the effectiveness of transaction merging to improve the running time of the algorithm.
【学位授予单位】：华侨大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13

【相似文献】