Precision-Enhanced Differentially-Private Mining of High-Confidence Association Rules

Association rule mining discovers patterns in large data repositories, and benefits diverse application domains such as healthcare, marketing, etc. However, mining datasets that contain data about individuals may cause significant privacy breaches. Recent research addresses the privacy threats that arise when mining sensitive data, and several techniques allow data mining with differential privacy guarantees. However, existing methods only discover rules that have very large support, i.e., occur in a large fraction of the dataset transactions (typically, more than 50 percent). This is a serious limitation, as numerous high-quality rules do not reach such high frequencies (e.g., rules about rare diseases, or luxury merchandise). We propose a method that focuses on mining high-quality association rules with moderate and low frequencies. We employ a novel technique for rule extraction that combines the exponential mechanism of differential privacy with reservoir sampling. The proposed algorithm allows us to directly mine association rules, without the need to compute noisy supports for large numbers of itemsets. Our experimental evaluation shows that our technique is able to sample low- and moderate-support rules with good precision, clearly outperforming existing solutions.