Adapting the Right Measures for Pattern Discovery: A Unified View

This paper presents a unified view of interestingness measures for interesting pattern discovery. Specifically, we first provide three necessary conditions for interestingness measures being used for association pattern discovery. Then, we reveal one desirable property for interestingness measures: the support-ascending conditional antimonotone property (SA-CAMP). Along this line, we prove that the measures possessing SA-CAMP are suitable for pattern discovery if the itemset-traversal structure is defined by a support-ascending set enumeration tree. In addition, we provide a thorough study on the family of the generalized mean (GM) measure and show their appealing properties, which are exploited for developing the GMiner algorithm for finding interesting association patterns. Finally, experimental results show that GMiner can efficiently identify interesting patterns based on SA-CAMP of the GM measure, even at an extremely low level of support.

I. Introduction

Recent years have witnessed an increasing interest in finding interesting but rare patterns in large-scale high-dimensional data from different application domains, such as Web texts, market-basket transactions, gene expression data, and graphs [5], [6], [9]. However, many previous studies limited their scope to the postevaluation of interesting patterns [23], which can be computationally expensive and often misses some interesting but infrequent patterns. In addition, while some previous studies worked on the interestingness measures [23], [25], these studies did not provide a comprehensive understanding of interestingness measures. In particular, it is not clear how to adapt the right measures for efficiently finding patterns with a low level of support.