Interactive mining and knowledge reuse for the closed-itemset incremental-mining problem

ABSTRACT

Using concept lattices as a theoretical background for finding association rules [11] has led to designing algorithms like Charm [10], Close [7] or Closet [8]. While they are considered as extremely appropriate when finding concepts for association rules, due to the smaller amount of results, they do not cover a certain area of significant results, namely the pseudo-intents that form the base for global implications. We have proposed an approach that, besides finding all proper partial implications, also finds the pseudo-intents. The way our algorithm is devised, it allows certain important operations on concept lattices, like adding or extracting items, meaning we can reuse previously found results. It is a well-known fact that mining association rules may lead to a large amount of results. Since, the mining results are meant to be understood by the user, we have come to the conclusion that he will benefit more from starting small, with some of the items in the data base, understand a small amount of results, and then add items receiving only the extra-results. This way the number of human interventions during the "full" mining process is increased and the process becomes user-driven.

REFERENCES

• 1: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 2: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 3: Usama M. Fayyad, Data Mining and Knowledge Discovery: Making Sense Out of Data, IEEE Expert: Intelligent Systems and Their Applications, v.11 n.5, p.20-25, October 1996 [doi>10.1109/64.539013]
• 4: Ganter B.: Algoritmen zur formalen begriffsanalyse, Beitrage zur Beigriffanalyse (Ganter, Wille, Wolf, eds), Wissenschaft-Verlag (1987).
• 5: Godin, R., Missaoui, R., Alaoui, H.: Incremental concept formation algorithms based on Galois (concept) lattices. Computational Intelligence, 11(2):246-267 (1995).
• 6: Gupta, S. K., Bhatnagar, V., Wasan, S. K., Somayajulu, D., Intension Mining: A New Paradigm in Knowledge Discovery. Technical Report No. IITD/CSE/TR2000/001, Indian Institute of Technology, Delhi, INDIA, (2000)
• 7: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Discovering Frequent Closed Itemsets for Association Rules, Proceeding of the 7th International Conference on Database Theory, p.398-416, January 10-12, 1999
• 8: Pei, J., Han, J., Mao, R.: CLOSET: An efficient algorithm for mining frequent closed itemsets. In Proc. of DMKD 2000, pp. 11-20 (2000).
• 9: Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts, Ordered Sets, pp. 445-470, (1982).
• 10: Zaki, M. J., Hsiao, C. J.: CHARM: An Efficient Algorithm for Closed Association Rule Mining, RPI Technical Report 99-10 (1999).
• 11: Zaki, M. J., Ogihara, M.: Theoretical Foundations of Association Rules, in Proc. of the 3rd SIGMOD'98 Workshop on Research Issues in Data Mining and Knowledge Discovery (DMKD), Seattle, WA, pp 7:1-7:8 (1998).

INDEX TERMS

Keywords:
Frequent itemsets, association rules, formal concept analysis