Abstract:Using the concept of frequent pattern tree of FP_growth, a new frequent pattern tree containing positive and negative items is constructed. The frequent itemsets with positive and negative items are mined through extending frequent patterns on the tree. Compared with the algorithms of directly using FP_growth, the proposed algorithm has no requirement for growing negative item to original database as well as the construction or destruction of additional data structures. Only some modifications to the original frequent pattern tree are needed. Therefore it has certain advantages in time and space costs. Experiments show that the algorithm has better efficiency than the existing mining algorithms and algorithms of directly using FP_growth.
[1] Han Jiawei, Kambr M. Data Mining: Concepts and Techniques. New York, USA: Elsevier, 2001 [2] Boulicaut J F, Bykowski A, Jeudy B. Towards the Tractable Discovery of Association Rules with Negations // Proc of the 4th International Conference on Flexible Query Answering Systems. Warsaw, Poland, 2000: 425434 [3] Wu Pengcheng, Yuan Zhaoshan. Hybrid Association Rules and Their Mining Algorithms. MiniMicro Systems, 2003, 24(5): 895898 (in Chinese) (武鹏程,袁兆山.混合关联规则及其挖掘算法.小型微型计算机系统, 2003, 24(5): 895898) [4] Li Xueming, Liu Yongguo, Peng Jun, et al. The Extended Association Rules and Atom Association Rules. Journal of Computer Research and Development, 2003, 39(12): 17401750 (in Chinese) (李学明,刘勇国, 彭 军,等.扩展型关联规则和原关联规则及其若干性质.计算机研究与发展, 2002, 39(12): 17401750) [5] Lu Yansheng, Rao Dan. A Mining Algorithm for Association Rules with Negation. Computer Engineering and Science, 2004, 26(10): 6365 (in Chinese) (卢炎生,饶 丹.一种挖掘带否定关联规则的算法.计算机工程与科学, 2004, 26(10): 6365) [6] Han Jiawei, Pei Jian, Yin Yiwen. Mining Frequent Patterns without Candidate Generation // Proc of the ACM SIGMOD International Conference on Management of Data. Dallas, USA, 2000: 120 [7] Agrawal R, Imielinaki T, Swami A. Mining Association Rules between Sets of Items in Large Databases // Proc of the ACM SIGMOD Conference on Management of Data. Washington, USA, 1993: 207216 [8] Zhou Haofeng, Zhu Yangyong, Shi Bole. A Mining Algorithm for Association Rules Based on Interest Measure. Journal of Computer Research and Development, 2002, 39(4): 450457 (in Chinese) (周皓峰,朱扬勇,施伯乐.一个基于兴趣度的关联规则的采掘算法.计算机研究与发展, 2002, 39(4): 450457) [9] Brin S, Motwani R, Silverstein C. Beyond Market Baskets: Generalizing Association Rules to Correlations // Proc of the ACM SIGMOD International Conference on Management of Data. Tucson, USA, 1997: 256276