树-投影关联规则挖掘方法的水平优化与搜索策略研究
Research on Horizontal Optimization and Search Strategy for the Mining of Association Rules Based on TreeProject
-
摘要: 基于树 -投影的TreeProject关联规则挖掘算法有效解决了现有各种算法在数据量过大时会失效的问题 通过对该算法及相关算法的研究 ,发现在现有这类算法中存在冗余投影 ,为此提出的水平优化策略通过消除这种冗余投影 ,既可减少树 -投影的搜索空间 ,加快频繁项的挖掘 ;还可减少树 -投影算法需要的内存空间 ,克服了原有树 -投影算法对内存要求较大的不足 ;该优化策略包括挖掘时的合并策略和挖掘后的生成策略两大部分 此外 ,冗余投影的判断 ,可从投影数据库T间的关系简化为相应事务编号数据库Tid间的关系 ,这种简化极大减少了判断的计算量 ,而且可用于投影 ,从而使得进行水平优化无需增加额外开销 基于水平优化策略的HOPTreeProject算法从时间和空间上都对现有的树-投影算法有很大改进 实验结果表明 ,HOPTreeProject在性能上显著优于TreeProjectAbstract: The TreeProject algorithm is the most efficient solution to the problem that can be described as “the algorithm will not run if the dataset is very large”, but there are redundant projects in this algorithm In order to remove the redundant projects, the horizontal optimizing strategies are presented which consist of the combining strategy used in the mining process and the generating strategy used at the end of mining The advantages of this algorithm not only can reduce the search space and the memory requirements of the TreeProject algorithm, but also promote the mining of frequency items Furthermore, the judgment of the horizontal redundancy can be simplified from the two project databases into the two corresponding sets of transaction number, which can save the time, and can also improve the project operation without adding extra time From the time complexity and the space complexity, the HOP TreeProject algorithm based on this horizontal optimizing strategies greatly improves the TreeProject algorithm The experimental results also demonstrate the correctness of the above conclusions
下载: