Source-linked AI summary
PrivBasis: Frequent Itemset Mining with Differential Privacy
Ninghui Li, Wahbeh Qardaji, Dong Su, Jianneng Cao
TL;DR
Frequent itemset publication can reveal individual transaction information, creating a need for differentially private mining in high-dimensional transaction databases. PrivBasis addresses this need with privately constructed basis sets that support frequency reconstruction and itemset selection. Experiments on five real datasets show that it greatly outperforms the current state of the art, while the existing top-k approach scales poorly for larger k.
Problem
Publishing frequent itemsets may compromise transaction privacy, while high-dimensional transactional data limits existing differentially private data-publishing techniques.
Method
PrivBasis privately constructs basis sets that cover itemsets above a frequency threshold, projects data onto selected dimensions, and reconstructs subset frequencies for itemset selection.
Results
PrivBasis greatly outperforms the current state of the art across five real datasets; its false negative rate is close to 0 even when ϵ is 0.5 on two datasets.
Takeaways & Limitations
Basis sets provide a way to publish frequent itemsets with differential privacy guarantees while avoiding top-k selection from very large candidate sets.
Takeaways & Limitations
The existing top-k method scales poorly when k is larger because its pruning can disappear and its utility guarantee can become meaningless.
Abstract
from arXiv · showhide
The discovery of frequent itemsets can serve valuable economic and research purposes. Releasing discovered frequent itemsets, however, presents privacy challenges. In this paper, we study the problem of how to perform frequent itemset mining on transaction databases while satisfying differential privacy. We propose an approach, called PrivBasis, which leverages a novel notion called basis sets. A theta-basis set has the property that any itemset with frequency higher than theta is a subset of some basis. We introduce algorithms for privately constructing a basis set and then using it to find the most frequent itemsets. Experiments show that our approach greatly outperforms the current state of the art.
1. INTRODUCTION
The paper frames private frequent itemset mining as a high-dimensional problem and introduces PrivBasis, which uses basis sets to avoid inaccurate selection from large candidate sets.
- Frequent itemsets support association-rule mining, user-behavior prediction, and correlation discovery, but publishing them may compromise transaction privacy.
- Private frequent itemset mining must satisfy differential privacy despite the high dimensionality of transactional datasets.Techniques effective for low-dimensional data do not apply directly to this setting.
- The prior approach selects top k itemsets from candidates of at most m items, but larger k requires larger candidate sets and reduces selection accuracy.
- PrivBasis uses theta-basis sets so every itemset above threshold θ is contained in some basis, enabling frequency reconstruction and subsequent selection.A good basis set has few bases with short lengths.
- The paper reports extensive experiments and states that PrivBasis greatly outperforms the existing approach.
- PrivBasis projects the dataset onto selected dimension sets, with each basis representing one projection and techniques choosing helpful dimensions for finding the k most frequent itemsets.
2. PRELIMINARIES
The preliminaries define differential privacy, its composition and noise-based mechanisms, and frequent itemset mining together with standard mining algorithms and problem formulations.
- Differential Privacy: Differential privacy requires outputs to remain approximately similar when one tuple is added to or removed from the input database.
- Differential Privacy: The paper defines neighboring datasets as datasets differing by one added or removed tuple, protecting the privacy of that tuple.
- Differential Privacy: Combining mechanisms with privacy parameters ϵ1 through ϵm yields total privacy budget ϵ equal to their sum.
- Differential Privacy: The Laplacian mechanism privately computes a function by adding random noise whose magnitude depends on the function’s global sensitivity.
- Differential Privacy: The exponential mechanism samples possible answers with probabilities increasing with a quality function’s accuracy score.
- Frequent Itemset Mining: Frequent itemset mining finds itemsets that frequently occur in transactional data, measured by the fraction of transactions containing each itemset.
- Frequent Itemset Mining: FIM can return all itemsets above threshold θ or the top k itemsets, each with its frequency.
- Frequent Itemset Mining: Apriori generates longer candidates from shorter frequent itemsets, whereas FP-Growth avoids candidate generation.
3. THE EXISTING APPROACH
The TF method privately selects and releases the top k itemsets from all itemsets up to length m, using truncated frequencies to avoid exhaustive enumeration. Its scalability and accuracy degrade when the candidate set is large, especially for larger k.
- TF method: The TF method releases the top k itemsets of length at most m, dividing privacy between selection and noisy frequency release.It adds noise to the frequencies of the selected itemsets after choosing them.
- Candidate-set construction: The candidate set U contains all itemsets of length at most m, and its size is exponential in m.Enumerating all elements of U can therefore be computationally expensive.
- Candidate-set construction: Truncated frequencies replace frequencies below fk − γ with fk − γ, allowing the method to avoid explicitly enumerating every itemset in U.The parameter γ is chosen to control the probability of selecting an itemset below the threshold.
- Scalability limitations: The method works well for small k but scales poorly when fk − γ ≤ 0, because pruning disappears and its utility guarantee becomes meaningless.This occurs when γ is at least fk.
- Scalability limitations: For large k, γ can approach or exceed fk, while choosing larger m to capture larger frequent itemsets further increases γ and can make the mechanism unfeasible.The top k itemsets may include itemsets of size 3, 4, or higher, creating a tension between coverage and accuracy.
- Scalability limitations: A large candidate set creates both running-time and accuracy problems: pruning addresses enumeration but not the selection of infrequent items caused by the many candidates.The accuracy requirement can force γ to be large, preventing the running-time goal from being achieved as well.
4. THE PRIVBASIS METHOD
PrivBasis addresses high-dimensional private frequent itemset mining by selecting multiple useful item dimensions, organizing them into basis sets, and reconstructing noisy frequencies for candidate itemsets. The method then selects frequent itemsets from these candidates while providing differential privacy and a runtime that is typically dominated by dataset scanning.
- Overview: PrivBasis targets publishing all itemsets above a threshold by finding the corresponding top k itemsets and applying its private mining procedure.The method computes k from the threshold boundary, then uses PrivBasis to find the top k frequent itemsets.
- Basis sets: A θ-basis set covers every θ-frequent itemset as a subset of at least one basis, with width and maximum basis length measuring its size.The candidate set consists of itemsets covered by some basis, so all θ-frequent itemsets are included when B is a θ-basis set.
- Algorithm: PrivBasis privately selects λ frequent items and frequent pairs, constructs a small-width, small-length basis set, and reconstructs noisy frequencies for covered itemsets before selecting the top k.Its projections use multiple dimension sets when one set would contain too many dimensions, and each basis corresponds to one projection.
- Generating noisy counts: Each basis partitions transactions into 2^|Bi| disjoint bins, whose noisy counts are combined to recover frequencies for itemsets covered by the basis.For example, the frequency of {a,b} under basis {a,b,c} is obtained by summing the two bins containing a and b.
- Privacy and efficiency: Algorithm 1 is ǫ-differentially private, and its time complexity is O(w|D| + w3^ℓ), with ℓ having an exponential effect on runtime.For large datasets the runtime is dominated by O(w|D|); experiments limit ℓ to at most 12, often 10 or smaller.
5. EXPERIMENTS
The experiments evaluate PrivBasis against Truncated Frequency across five transaction datasets using utility measures including false negative rate and relative error. PrivBasis consistently outperforms Truncated Frequency, especially for larger k, while dataset structure affects the comparative advantage.
- Evaluation setup: The evaluation compares PrivBasis with Truncated Frequency across five datasets using false negative rate, false positive rate, and relative error of published itemset counts.Experiments vary privacy parameter ǫ, k, and TF’s maximum itemset length m; results are averaged over three repetitions with standard errors.
- Small λ, single basis: For Mushroom and Pumsb Star, PrivBasis consistently and significantly outperforms Truncated Frequency in false negative rate and relative error.PrivBasis with larger k also significantly outperforms Truncated Frequency with smaller k.
- Small λ, single basis: PrivBasis has false negative rate close to 0 on Mushroom and Pumsb Star even when ǫ = 0.5, whereas Truncated Frequency exceeds 0.6 or 0.7 for larger-k tasks even when ǫ = 1.For top 50 itemsets at ǫ = 0.5, Truncated Frequency has false negative rate about 0.6 and 0.4 on the two datasets.
- Larger λ, small number of basis: On Retail and Kosarak, PrivBasis again outperforms Truncated Frequency, remaining accurate up to k = 400, although Retail has worse false negative rates than the other datasets.Retail’s weaker results are attributed to many itemsets having frequencies close to the kth itemset frequency.
- λ ≈ k, large number of basis: On AOL, Truncated Frequency performs closest to PrivBasis because frequent singleton items cover many frequent itemsets and the task approaches top-item mining.Truncated Frequency becomes unfeasible for m > 1 on this dataset, which contains 171 singletons and 29 pairs.
6. RELATED WORK
Related work covers differential-privacy methods for private frequent-itemset release, transaction-data publication, and search-log publishing. PrivBasis differs from prior approaches in its privacy model, released output, and support for itemsets beyond singletons.
- Differentially private release: The work most closely related to PrivBasis releases differentially private frequent itemsets, while other differential-privacy research addresses statistical queries, histograms, contingency tables, and record matching.The paper identifies Bhaskar et al. as the most related prior work and discusses it in detail.
- Anonymization and synthetic data: Some prior methods modify frequent-itemset supports under k-anonymity or release synthetic transaction datasets, rather than directly releasing privacy-preserving mining results.The paper characterizes k-anonymity as weaker than differential privacy and describes taxonomy-guided noisy leaf counts for synthetic-data generation.
- Private search logs: Private search-log methods release frequent keywords but do not release information about frequent itemsets of size 2 or higher, effectively mining only length-1 itemsets.These approaches also assume that keywords in the dataset are not sensitive, unlike the setting considered here.
7. CONCLUSION
PrivBasis privately constructs basis sets and reconstructs subset frequencies to publish frequent itemsets under differential privacy. Experiments on five real datasets show it greatly outperforms the current state of the art.
- PrivBasis publishes frequent itemsets with differential privacy guarantees.
- A basis set ensures every itemset with frequency higher than θ is a subset of some basis.
- The method privately constructs basis sets and reconstructs frequencies for their subsets before selecting the most frequent itemsets.
- Experiments on 5 real datasets show that PrivBasis greatly outperforms the current state of the art.
- PrivBasis can be viewed as dimension reduction for addressing the curse of dimensionality in private data analysis and anonymization.