Efficient mining of top correlated patterns based on null-invariant measures

Sangkyum Kim, Marina Barsky, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Mining strong correlations from transactional databases often leads to more meaningful results than mining association rules. In such mining, null (transaction)-invariance is an important property of the correlation measures. Unfortunately, some useful null-invariant measures such as Kulczynski and Cosine, which can discover correlations even for the very unbalanced cases, lack the (anti)-monotonicity property. Thus, they could only be applied to frequent itemsets as the post-evaluation step. For large datasets and for low supports, this approach is computationally prohibitive. This paper presents new properties for all known null-invariant measures. Based on these properties, we develop efficient pruning techniques and design the Apriori-like algorithm NICoMiner for mining strongly correlated patterns directly. We develop both the threshold-bounded and the top-k variations of the algorithm, where top-k is used when the optimal correlation threshold is not known in advance and to give user control over the output size. We test NICoMiner on real-life datasets from different application domains, using Cosine as an example of the null-invariant correlation measure. We show that NICoMiner outperforms support-based approach more than an order of magnitude, and that it is very useful for discovering top correlations in itemsets with low support.

Original languageEnglish (US)
Title of host publicationMachine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2011, Proceedings
Pages177-192
Number of pages16
EditionPART 2
DOIs
StatePublished - Sep 9 2011
EventEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2011 - Athens, Greece
Duration: Sep 5 2011Sep 9 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 2
Volume6912 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherEuropean Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2011
CountryGreece
CityAthens
Period9/5/119/9/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient mining of top correlated patterns based on null-invariant measures'. Together they form a unique fingerprint.

  • Cite this

    Kim, S., Barsky, M., & Han, J. (2011). Efficient mining of top correlated patterns based on null-invariant measures. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2011, Proceedings (PART 2 ed., pp. 177-192). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6912 LNAI, No. PART 2). https://doi.org/10.1007/978-3-642-23783-6_12