Quantitative Rule Lattice and Its Incremental Construction
LI Yun1, LIU ZongTian2, CHEN Ling1, CAI JunJie1
1.Institute of Information Engineering, Yangzhou University, Yangzhou 225009 2.School of Computer Engineering and Science, Shanghai University, Shanghai 200072
Abstract The key for extracting the minimal nonredundant rule is to obtain the least itemsets in the Set of Frequent Itemsets with the Same Tidset(SFIST) which corresponds to the frequent closed itemset. To extract such rules using the concept lattice conveniently, the Quantitative Rule Lattice(QRL) with new data structure is presented, the way obtaining the set of the least itemsets in the SFIST of the node in QRL is discussed and the relevant algorithm is provided. Due to incremental formation of QRL and the set of the least itemsets, the QRL is very suitable for both extracting the minimal nonredundant rules from the dynamic database and realizing the rule updated incrementally.
[1] Agrawal R, Imielinski T, Swami A. Mining Association Rules between Sets of Items in Large Databases. In: Proc of the ACM SIGMOD Conference on Management of Data. Washington, USA, 1993, 207-216 [2] Han J W, Kamber M. Data Mining: Concepts and Techniques. Orlando, USA: Morgan Kaufmann Publisher, 2000 [3] Li Y, Liu Z T, et al. Extracting Minimal Non-Redundant Implication Rules by Using Quantized Closed Itemset Lattice. In: Proc of the 16th International Conference on Software Engineering and Knowledge Engineering. Banff, Canada, 2004, 402-405 [4] Li Y, Liu Z T, et al. Extracting Minimal Non-Redundant Approximate Rules Based on Quantitative Closed Itemset Lattice. Journal of Fudan University (Natural Science), 2004, 43(5): 801-804 [5] Bastide Y, Pasquier N, et al. Mining Minimal Non-Redundant Association Rules Using Frequent Closed Itemsets. In: Proc of the 1st International Conference on Computational Logic. London, UK, 2000, 972-986 [6]Ganter B, Wille R. Formal Concept Analysis: Mathematical Foundations. Berlin, Germany: Springer-Verlag, 1999 [7] Waiyamai K, Lakhal L. Knowledge Discovery from Very Large Databases Using Frequent Concept Lattices. In: Proc of the 11th European Conference on Machine Learning. Barcelona, Spain, 2000, 437-445 [8]Xie Z P, Liu Z T. Concept Lattice and Association Rule Discovery. Journal of Computer Research and Development, 2000, 37(12): 1415-1421 (in Chinese) (谢志鹏,刘宗田.概念格与关联规则发现.计算机研究与发展, 2000, 37(12): 1415-1421) [9] Pasquier N, Bastide Y, et al. Efficient Mining of Association Rules Using Closed Itemset Lattices. Information Systems, 1999, 24(1): 25-46 [10]Zaki M J, Hsiao C J. Charm: An Efficient Algorithm for Closed Association Rule Mining. Technical Report, 99-10, Rensselaer Polytechnic Institute, 1999 [11]Valtchev P, Missaoui R, Godin R, Meridji M. Generating Frequent Itemsets Incrementally: Two Novel Approaches Based on Galois Lattice Theory. Journal of Experimental and Theoretical Artificial Intelligence, 2002, 14(2-3): 115-142 [12] Li Y, Liu Z T, et al. Extracting Minimal Non-Redundant Associate Rules from QCIL. In: Proc of the 4th International Conference on Computer and Information Technology. Wuhan, China, 2004, 986-991 [13] Gao F, Xie J Y. Algorithm for Generating Non-Redundant Association Rules. Journal of Shanghai Jiaotong University, 2001, 35(2): 256-258 (in Chinese) (高 峰,谢剑英. 一种无冗余的关联规则发现算法.上海交通大学学报, 2001, 35(2): 256-258) [14]Godin R, Missaoui R, Alaoui H. Incremental Concept Formation Algorithms Based on Galois (Concept) Lattices. Computational Intelligence, 1995, 11(2): 246-267
2006, Vol. 19 
