Mining influential attributes that capture class and group contrast behaviour

ABSTRACT

Contrast data mining is a key tool for finding differences between sets of objects, or classes, and contrast patterns are a popular method for discrimination between two classes. However, such patterns can be limited in two primary ways: i) They do not readily allow second order differentiation - i.e. discovering contrasts of contrasts, ii) Mining contrast patterns often results in an overwhelming volume of output for the user. To address these limitations, this paper proposes a method which can identify contrast behaviour across both classes and also groups of classes. Furthermore, to increase interpretability for the user, it presents a new technique for finding the attributes which represent the key underlying factors behind the contrast behaviour. The associated mining task is computationally challenging and we describe an efficient algorithm to handle it, based on binary decision diagrams. Experimental results demonstrate that our technique can efficiently identify and explain contrast behaviour which would be difficult or impossible to isolate using standard techniques.

REFERENCES

• 1: C. Aggarwal , S. Yu, An effective and efficient algorithm for high-dimensional outlier detection, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.211-221, April 2005 [doi>10.1007/s00778-004-0125-5]
• 2: Guozhu Dong , Jinyan Li, Efficient mining of emerging patterns: discovering trends and differences, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.43-52, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312191]
• 3: Guozhu Dong , Xiuzhen Zhang , Limsoon Wong , Jinyan Li, CAEP: Classification by Aggregating Emerging Patterns, Proceedings of the Second International Conference on Discovery Science, p.30-42, December 01, 1999
• 4: H. Fan and K. Ramamohanarao. Noise tolerant classification by chi emerging patterns. In Proc. of PAKDD 2004, pages 201--206, 2004.
• 5: U. Fayyad and K. Irani. Multi-interval discretization of continuous-valued attributes for classification. In Proc. of 13th International Joint Conference on Artificial Intelligence, pages 1022--1029, 1993.
• 6: S. Hettich and S. D. Bay. The UCI KDD archive {http://kdd.ics.uci.edu}, 1999.
• 7: Michael Edward Houle , Nizar Grira, A correlation-based model for unsupervised feature selection, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321570]
• 8: J. Li and L. Wong. Identifying good diagnostic gene groups from gene expression profiles using the concept of emerging patterns. Bioinformatics, 18(5):725--34, 2002.
• 9: J. Li and Q. Yang. Strong compound-risk factors: Efficient discovery through emerging patterns and contrast sets. IEEE Trans. on Information Technology in Biomedicine, 11(5):544--552, 2007.
• 10: Elsa Loekito , James Bailey, Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150438]
• 11: Elsa Loekito , James Bailey, Are zero-suppressed binary decision diagrams good for mining frequent patterns in high dimensional datasets?, Proceedings of the sixth Australasian conference on Data mining and analytics, December 03-04, 2007, Gold Coast, Australia
• 12: U. Roessner, J. H. Paterson, M. G. Forbes, G. B. Fincher, P. Langridge, and A. Bacic. An investigation of boron toxicity in barley using metabolomics. Plant Physiology, 142(3):1087--1101, November 2006.
• 13: Amit Satsangi , Osmar R. Zaiane, Contrasting the Contrast Sets: An Alternative Approach, Proceedings of the 11th International Database Engineering and Applications Symposium, p.114-119, September 06-08, 2007 [doi>10.1109/IDEAS.2007.23]
• 14: Jilles Vreeken , Matthijs van Leeuwen , Arno Siebes, Characterising the difference, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281274]
• 15: Geoffrey I. Webb , Shane Butler , Douglas Newlands, On detecting differences between groups, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956781]

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Design

Keywords:
contrast patterns, emerging patterns, group contrast, influential attributes, second-order contrast patterns