Exploiting a support-based upper bound of Pearson's correlation coefficient for efficiently identifying strongly correlated pairs
Authors:
Open Access
- 22 August 2004
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 334-343
Abstract
Given a user-specified minimum correlation threshold θ and a market basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold θ. However, when the number of items and transactions are large, the computation cost of this query can be very high. In this paper, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient but also exhibits a special monotone property which allows pruning of many item pairs even without computing their upper bounds. A Two-step All-strong-Pairs corrElation que Ry (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent or improves when the number of items is increased in data sets with common Zipf or linear rank-support distributions. Experimental results from synthetic and real data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives.Keywords
This publication has 11 references indexed in Scilit:
- Playing hide-and-seek with correlations2003
- Efficient mining of constrained correlated sets2002
- Finding interesting associations without support pruning2002
- Mining optimized association rules with categorical and numeric attributesIEEE Transactions on Knowledge and Data Engineering, 2002
- DualMiner2002
- Empirical bayes screening for multi-item associations2001
- Mining frequent patterns without candidate generation2000
- Exploratory mining via constrained frequent set queries1999
- Beyond market baskets1997
- Mining association rules between sets of items in large databases1993