Weighted Association Rule Mining using weighted support and significance framework

ABSTRACT

We address the issues of discovering significant binary relationships in transaction datasets in a weighted setting. Traditional model of association rule mining is adapted to handle weighted association rule mining problems where each item is allowed to have a weight. The goal is to steer the mining focus to those significant relationships involving items with significant weights rather than being flooded in the combinatornal explosion of insignificant relationships. We identify the challenge of using weights in the iterative process of generating large itemsets. The problem of invalidation of the "downward closure property" in the weighted setting is solved by using an improved model of weighted support measurements and exploiting a "weighted downward closure property". A new algorithm called WARM (Weighted Association Rule Mining) is developed based on the improved model. The algorithm is both scalable and efficient in discovering significant relationships in weighted settings as illustrated by experiments performed on simulated datasets.

REFERENCES

• 1: R. Agrawal et al, "The Quest Data Mining System" Technical report, IBM Almaden Research Center, http://www.almaden.ibm.com/cs/quest/, 1996.
• 2: 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
• 3: 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
• 4: Fernando Berzal , Juan-Carlos Cubero , Nicolás Marín , José-Maria Serrano, TBAR: An efficient method for association rule mining in relational databases, Data & Knowledge Engineering, v.37 n.1, p.47-64, April 2001 [doi>10.1016/S0169-023X(00)00055-0]
• 5: Sergey Brin , Rajeev Motwani , Jeffrey D. Ullman , Shalom Tsur, Dynamic itemset counting and implication rules for market basket data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.255-264, May 11-15, 1997, Tucson, Arizona, United States
• 6: Toon Calders , Bart Goethals, Mining All Non-derivable Frequent Itemsets, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.74-85, August 19-23, 2002
• 7: Jiawei Han , Yongjian Fu, Discovery of Multiple-Level Association Rules from Large Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.420-431, September 11-15, 1995
• 8: Bing Liu , Wynne Hsu , Yiming Ma, Mining association rules with multiple minimum supports, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.337-341, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312274]
• 9: Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal, Efficient mining of association rules using closed itemset lattices, Information Systems, v.24 n.1, p.25-46, March 1999 [doi>10.1016/S0306-4379(99)00003-4]
• 10: G. D. Ramkumar, Sanjay Ranka, and Shalom Tsur, "Weighted Association Rules: Model and Algorithm" KDD1998, 1998.
• 11: Feng Tao, "Mining Binary Relationships from Transaction Data in Weighted Settings" PhD Thesis, School of Computer Science, Queen's University Belfast, UK, 2003.
• 12: Wei Wang , Jiong Yang , Philip S. Yu, Efficient mining of weighted association rules (WAR), Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.270-274, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347149]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Keywords:
WARM algorithm, Weighted Association Rule Mining, significant relationship, weighted downward closure property, weighted support