Frequent itemset mining aims at finding the sets of items that occur together frequently in many transactions, which can lay the foundation for further association rule mining. In this paper, to deal with the problem of massive amount of data, we adopt a specific model which expresses the attributes of item hierarchically. Based on the layering attributes, we propose a novel frequent itemset mining method under local differential privacy which deals with the frequent itemset mining problem layer by layer and it greatly improves the search efficiency. Experimental analyses based on real and synthetic datasets show that our method outperforms the state-of-the-art in terms of the computation cost.
Frequent Itemset Mining (FIM) is a key problem in data mining. By mining frequent itemset,
merchants can discover the links between products, and thus predict customers' buying habits and
improve their service quality, which is beneficial both for their own interests and the economic
development of society. However, in the process of collecting users’ information, there is a risk that
some sensitive personal information such as users’ purchase history, browsing preferences may leak
and users do not want to expose their privacy [15]. In recent years, in order to protect privacy, local
differential privacy [
There has been some research on frequent itemset mining of set-valued data under local differential
privacy [
In real world, people may have complex personal requirements. Fortunately, based on the layering structure of category attributes, our scheme can perfectly meet the complex requirements through mining frequent itemset from high layer to low layer. Thus, users are able to obtain the frequent itemset of different layers, rather than a single layer. Compared with other methods, our model is more flexible.
The main contributions of this paper are as follows. 1) We adopt a hierarchical expression of category attributes to improve the search efficiency. In addition, mining frequent itemset at different layers can meet the complex personal needs of users.
2) Based on the layering attributes, we propose a novel frequent itemset mining method which deals with the problem layer by layer.
3) We introduce a specific model of local differential privacy to the method mentioned above, and our experimental results validate the effectiveness of the proposed method.
The rest of the paper is organized in the following order. Section 2 introduces background knowledge and problem definition of frequent itemset mining, Section 3 presents some previous work, Section 4 gives a complete implementation of our scheme, Section 5 shows experimental results of our scheme and compares it with other methods, and Section 6 concludes our work.
Definition 1 ( -Local Differential Privacy ， -LDP) a perturbation mechanism : → satisfies -LDP if and only if for any two users' data , ′ ∈ , and any possible output ∈ satisfies the following inequality (1).
( ( ) = ) ( ( ′) = ) ≤ (1)
Theorem 1 (Sequential Composition Theorem) Let A1, A2, A3, … , A be a series of LDP mechanisms where A implements -LDP, when the mechanism A on the data are run in an independent random on A1( ), A2( ), A3( ), … , A ( ) or run them in some sequential primary order, at this point the mechanism is considered to satisfy the (∑ =1 )-LDP. 2.2.
To cope with the problem of input domain size larger than 2, Generalized Random Response (GRR)
[15] and Unary Encoding (UE) [
Definition 2 (Unary Encoding, UE) first maps the input as a bit length vector where only the bit corresponding to the user input is set as 1. For the vector after the one-hot encoding , UE is perturbed separately for each bit as the following Equation (2).
,
( ′[ ] = 1) = {
,
[ ] = 1
[ ] = 0
(2)
According to the -LDP definition, UE can provide = ln .(1− ) for LDP. In order to minimize the
.(1− )
variance of UE, Wang [
For the frequency estimation of set-valued data, padding-and-sampling protocol [
Wang [
( , , ) = ⟨ ( )( ), ( ). ⟩ (3) 2.4.
In the frequent itemset problem, the data collector knows the set of all items which is referred to as the full set . There is a total of users, and the ℎ user has a set of items ⊆ and we call this a transaction. Similarly, an itemset is a collection of items, and the frequency of any ⊆ is defined as the number of transactions containing that itemset , which is also denoted as = { | ⊆ }.
Our goal is to devise a secure and efficient scheme that enables data collector to implement frequent itemset mining under local differential privacy. We denote the frequency of top-k frequent item as ( ), for the candidates of top-k frequent itemset , our optimization goal is: = argmax ∏ ∈ ( ). The top-k frequent itemset refers to an itemset whose frequency is among the k highest for all itemsets.
There has been some researches devoted to mining frequent itemset under local differential privacy.
To address the problem of the varying number of items owned by users, Qin [
Inspired by LDPMiner, Wang [
Zhang [16] devised a MRR algorithm to perform frequent itemset mining under local differential privacy. It not only takes into account the multiple attributes of users’ data, but also can meet the needs of users' personalized privacy protection. However, the process is inefficient in encoding because items that do not have values in some attributes still consume large computation cost, and the computation of frequent itemset supported by Bayes formula leads to low accuracy. Sharmin [15] proposed a novel method to find frequent itemset on small datasets. The scheme framework is better at maintaining the correlation between items, but the interactions between users and server are too complex to be applied in reality.
In this section, we propose the solution to the problem of mining frequent itemset under local differential privacy. We first introduce the layering structure of category attribute, and then we present the complete implementation of our proposed method under LDP. 4.1.
Different from most of the researches nowadays which focus on the items with only a single category
attribute, we divide the category attributes into many layers and express them hierarchically. The
layering structure is shown in Figure 2. By dividing the attributes into layers, we are able to expand the
original single attribute of an item into multi-dimensional category attribute. Hence, the problem of
massive amount of data can be effectively solved by taking advantage of the correlation between
different layers of attributes [
Based on the layering structure of category attribute, in order to improve the search efficiency, we devise a novel scheme of finding frequent itemset step by step, from high layer to low layer. We find the frequent itemset of large category firstly, and then to search the specific frequent itemset of small category within the given frequent itemset of large category, from coarse to fine, to greatly reduce the problem complexity.
If the number of a small category item is increasing, the number of corresponding large category will also increase, it makes sense that the frequent itemset of large category can be used for the further search of small category frequent itemset. The complexity of the frequent 2-itemset problem is O ( 2). e.g., there are ten large categories, and each large category contains 100 small category items. If we find the top three large categories of frequent 2-itemset, the problem scale will decline to O (3 ∗ 2002), which is much smaller than O (10002). Although there is some loss in accuracy, it greatly improves the search efficiency. 4.2.
We propose a multi-phase scheme framework in which users obtain frequent itemset of each layer after interacting with the server several times. Based on the idea of user pruning, after the itemset frequency estimation of each layer has been performed, only the top-ranked frequent itemsets of the current layer are sent to the next layer for continue mining. The iterative process of the frequent itemset mining for each layer continues and all estimated frequent itemsets of each layer are discovered eventually. The total privacy budget is divided into
parts for layers and each is used in the ℎ layer.
Specifically, we allocate privacy budget equally, which means each layer has the same average of and the whole process satisfies -LDP according to the sequential composition property.
In LDP, a common approach is to partition users into different groups, each answering one separate
question than for all users to answer multiple questions each with part of the total privacy budget [
For each group of users with from the previous layer, each user first finds the items from his own transaction which is in the range domain of the itemset . If a user does not possess any item in the range domain of , he will be regarded as a useless participant and does not need to go through the next series of operations. In other words, the frequent itemset is combined of the items only from the range domain, and any item outside the domain is not considered, which demonstrates the idea of user pruning. Algorithm 1 outlines the specific process of each layer.
Step 1: Padding and Sampling. As the number of items in a user transaction varies, existing FO protocols cannot handle this problem. Hence, it is necessary to adopt padding-and-sampling protocol to select one item to report. If the user’s transaction length is less than , the dummy item is padded; if the user’s transaction length is larger than , he randomly draws items out. Although the dummy item could be sampled, its frequency will be ignored by the server during the frequency estimation process and it definitely could not be considered as a frequent item. the perturbed value is submitted to the server for aggregation.
Step 2: Encoding and Perturbing. Assuming that there are users, each of whom possesses an item obtained by padding and sampling. Then, the sampled item is indexed up to get the value of the ℎ layer category attribute. Each user adopts OUE algorithm to perturb the value with ⁄2. Finally,
Step 3: Aggregation and Estimation. After receiving the perturbed value from users, the server calculates the frequencies of all category attributes by multiplying the estimated results with and dropping the dummy item. Then, the server sorts attributes according to the estimated frequencies and combines them two by two to construct the top-2k frequent itemset candidates. The 2k candidates are sent to users.
The following task is quite similar to the original problem, with the difference that the universe of items becomes the 2k frequent itemset candidates, instead of the full set of items. Specifically, the final top-k frequent itemsets are chosen from the 2k candidates.
Step 4: Candidates Estimation. After receiving 2k frequent itemset candidates, the user selects the set of items he owns in the 2k candidates. He then adopts padding-and-sampling algorithm to randomly select one item from the padded set. Note that at this time the padding length becomes 2k rather than 90% of the number of users. Afterwards, the user adopts OUE algorithm to perturb the value with ⁄ and sends it to the server. frequent itemsets can be obtained.
The server estimates the frequencies of all candidates from the perturbed value and thus top-k
In this section, we experimentally evaluate our method of mining frequent itemset for category data under local differential privacy, and verify that our proposed scheme performs effectively on real and synthetic datasets. Basically, we want to answer the following questions: Firstly, how many frequent itemsets can be effectively identified. Secondly, how much do we improve the search efficiency.
Environment: all algorithms are implemented in Python 3.7 and all the experiments are conducted on an Intel Core i5-9300H 2.4GHz PC with 16GB memory.
Datasets: we use the real dataset (Retail) [15] to show that our proposed method is suitable for real datasets. We show the results of the Retail dataset in Figure 4. We also implement our scheme on a synthetic dataset called norm-user [16] which obeys normal distribution and the result is shown in Figure 5. The synthetic normal distribution has mean of 4 and standard deviation of 0.1.
Our main goal of this experiment is to prove that by taking the correlations between items into
account, our scheme can usually obtain frequent itemset results more accurately and efficiently,
compared to SVSM [
Evaluation metrics: to compare the accuracy of the results of the mining, we adopt the F − Score [16] to measure our performance. Let = { 1, 2, 3, … , } denotes the ground truth for top-k frequent itemset and represents the set of frequent itemset generated by a specific algorithm. Then ∩ is the set of real top-k itemsets that are identified by the algorithm. In this case, F − Score represents the accuracy of the search and is defined as the following Equation (4). In addition, we take the program running time as the expression the computation cost.
− = 2 ∗ (4)
We conduct simulations on two kinds of datasets to compare the performance between three mechanisms. The first algorithm performing is our proposed method, the second one is SVSM algorithm and the last one is called Priv_OA which performs well on small datasets. The privacy budget we employ ranges from 1.0 to 5.0 with intervals of 1. In addition, we also explore the relationship between the accuracy of the results and the value of k through experiments. The value k ranges from 30 to 70 with intervals of 10.
In Figure 4, we evaluate three methods on Retail dataset and plot the F − Score diagram based on the variation of privacy budget and the value of k. As can be observed in Figure 4, the identification accuracy which is denoted as F − Score increases with , and basically maintain, even with a little fluctuation when the value of k increases. It can be observed that our mechanism has an improvement over the other two methods, and with the increase of privacy budget and the value of k, that advantage is more obvious. That means the data utility has been improved under our proposed method. We also can find that with the increase of k, F − Score does not go up that fast. That is probably because the frequency difference of itemset is not that obvious and the error in frequency estimation also increases with k.
In Figure 5, we evaluate three methods on synthetic dataset and plot the F − Score diagram based on the variation of privacy budget and the value of k. Similar to the Retail dataset, it can be observed that the scheme we propose outperforms the other two methods. However, it can be noticed that when the privacy budget = 1, our approach doesn’t perform well compared to Priv_OA, probably because data utility is low when the privacy budget is small, and at this time, users’ privacy can be better protected.
Furthermore, we also explore the relationship between computation time and variables (the privacy budget and k) and the result is shown in Figure 6. This suggests that for the set of real top-k itemsets that are identified by algorithms, our proposed method can greatly reduce the computation cost, thus improve the search efficiency.
In this paper, a novel method is proposed to mine frequent itemset under local differential privacy. To improve the search accuracy, we divide the category attributes into layers and make full use of the correlation between different layer of attributes. Based on the layering attributes, in order to reduce the complexity of processing, frequent itemset mining is implemented step by step, from high layer to low layer. In addition, we have experimentally verified that our approach performs effectively on both real and synthetic datasets. Due to that we only consider the search of frequent 2-itemset in this paper, in the future, we will continue to do research on frequent multi-itemset mining under LDP. Furthermore, there can be more improvements in terms of different expressions of attribute structures.
[10] Wang T, Li N, Jha S. Locally differentially private heavy hitter identification [J]. IEEE
Transactions on Dependable and Secure Computing, 2019. [11] Fanti G, Pihur V, Erlingsson Ú. Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries[J]. Proceedings on Privacy Enhancing Technologies, 2016, 3: 41-61. [12] Bassily R, Nissim K, Stemmer U, et al. Practical Locally Private Heavy Hitters [J]. Advances in
Neural Information Processing Systems, 2017, 30: 2288-2296. [13] Wang N, Xiao X, Yang Y, et al. PrivTrie: Effective frequent term discovery under local differential privacy [C]//2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE, 2018: 821-832. [14] Q. Xue, Y. Zhu and J. Wang, "Joint Distribution Estimation and Naïve Bayes Categoryification Under Local Differential Privacy," in IEEE Transactions on Emerging Topics in Computing, vol. 9, no. 4, pp. 2053-2063, 1 Oct.-Dec. 2021, doi: 10.1109/TETC.2019.2959581. [15] Sharmin Afrose, Tanzima Hashem, and Mohammed Eunus Ali. 2021. Frequent Itemsets Mining with a Guaranteed Local Differential Privacy in Small Datasets. 33rd International Conference on Scientific and Statistical Database Management Association for Computing Machinery, New York, NY, USA, DOI:https://doi.org/10.1145/3468791.3468807 [16] Xinyuan Zhang, Liusheng Huang, Peng Fang, Shaowei Wang, Zhenyu Zhu, and Hongli Xu. 2017.
Differentially Private Frequent Itemset Mining From Smart Devices in Local Setting. in WASA. 433-44