The information age has enabled organizations to gather large volumes of data. However, the usefulness of this data is negligible if “meaningful information” cannot be extracted from it. Data mining answers this need. The problem of privacy-preserving data mining has become important recently because of the increasing ability to store personal data and the sophistication of data mining algorithms to leverage information. Many researches have been done in this field but few with quantitative data had drawbacks of high number of rules generated and few number of item hidden. This study, proposes a perturbation association rules hiding algorithm for privacy of quantitative data to provide a better algorithm for preserving quantitative data. In hiding of rules, the noise associated with each item was calculated. The noise was used to calculate the support and confidence of rules which were then compared with minimum support and confidence. Item whose support/confidence is less than or equal to minimum support or confidence would be hidden. Experimental result shows that the algorithm hides more rules than the existing works.
CCS Concepts • Information systems ➝ Information systems applications ➝ Data mining ➝ Association rules • Security and privacy ➝ Human and societal aspects of security and privacy ➝Privacy protection
The problem of mining quantitative association rule was first introduced by Evfimievski et al [7]. Two works have been done in the field of hiding fuzzy association rule in quantitative data according to Manoj and Joshi [8] and Berberoglu [9]. However, little or no work has been done in the aspect of perturbation of association rules for quantitative data using the concept of noise. Manoj and Joshi [8] proposed a hiding algorithm that integrates the fuzzy set concepts and Apriori mining algorithm to find useful fuzzy association rules from a quantitative database and then hide them using privacy preserving technique. Unlike previous approaches which mainly deals with association rules in binary database, the approach deals with hiding the association rules in quantitative database. Numerical experiments were performed to measure the performance of the algorithm according to three criteria: the number of rules hidden, side effects and database effects of the algorithm. However, the algorithm only deals with association rule in small dataset in which the algorithm generated much rules but the algorithm is not efficient since a large part of the rules generated resulted into lost rules.
In this paper, we attempt to present a perturbation association rules hiding algorithm for privacy preservation of quantitative data with few rules and hides higher percentage of the rules by decreasing the support of the rule. The support of rule is decreased by decreasing the support of A. This is achieved by decreasing the support value of either A or B of the rule until either the support or confidence is below the minimum support or minimum confidence value respectively.
The rest of this paper is organized as follows. Privacy preserving quantitative association rule hiding was defined in Section II, our approach to hide useful association rules in quantitative data was presented in Section III, the perturbation association rule hiding process was presented in Section IV, and the proposed algorithm related example was presented in Section V. Section VI includes the conclusion and future works. 2. PROBLEM STATEMENT The objective of privacy preserving data mining is to hide certain information so that they cannot be discovered through data mining techniques. There have been two broad approaches for privacy preserving data mining. The first approach, called output privacy, is to alter the data before delivery to data miner so that real data is obscured and mining result will not disclose certain privacy. For example, perturbation, blocking, merging, swapping and sampling are some methods that have been proposed for this type of output privacy. The second approach, called input privacy, is to manipulate the data using data distribution methods in which the privacy of the data is protected before releasing to the user. In this approach, mining result is not affected or minimally affected. Almost all of studies that have been proposed in this research area concentrated on hiding Boolean association rules which are concerned only with whether an item is present in a transaction or not, without considering its quantity.
However, transactions with quantitative values are commonly found in real world application. For example, in a patient’s blood test, many attributes could be found. In addition, attribute’s quantity instead of just presence/absence of the attribute in blood is more important for determination of the illness. Furthermore, many people have the problem of sugar but this does not mean that one is sick or not, the only criterion to used to determine the illness is the surplus/deficiency in sugar ’s quantity.
Some works have been done to discover association rules from quantitative data which generate set of rules but hides less than 30% of the rules generated. This paper proposes a privacy preserving data mining algorithm (that uses the output privacy approach in which the data is preserved before it will be released to the miner) that improves on the association rule hiding algorithms for quantitative data by combining the perturbation method for privacy and association rule mining technique for privacy. Furthermore, the paper addresses the challenges of applying privacy algorithm to only Boolean data by applying the algorithm to quantitative data and not just the presence or absence of data. 3. PROPOSED ALGORITHM In order to hide an association rule, A→B we can either decrease its support to be smaller than minimum support value or its confidence to be smaller than its minimum confidence value. To decrease the confidence of a rule, two strategies can be used. The first one is to increase the support count of A i.e. LHS of the rule, but not support count of A→B. The second one is to decrease the support count of A→B. For the second case, if we only decrease the support of B, the right hand side of the rule, it would reduce the confidence faster than simply reducing the support of A∪B. Based on these two strategies, we propose a privacy preserving data mining algorithm for hiding sensitive quantitative data items called perturbation of association rule for quantitative data using the concept of noise. This algorithm first calculates the value of noise for each data items and the column with the highest noise value form the rule with the sensitive column. Secondly, the algorithm find useful association rule that consist of only one item on both sides of the rule and then hide them using privacy preserving technique. For hiding purpose, the algorithm tries to decrease the support of rule A→B by decreasing the support count of itemset AB until either support or confidence value of the rule goes below minimum support or minimum confidence value respectively.
(
Algorithm 1.
Compute the support of rule
( (( )) ) = ( )
√
for ) = Maximum Value such that k =
1-itemset = { }
Sensitive column = {
and STEP 4: join the 1-itemset to the sensitive column in a way similar to that of apriori algorithm to form a 2- itemset. The 2itemset is use to find the useful association rule by placing at the LHS and at the RHS similar to that of apriori algorithm STEP 5 (a): in order to hide sensitive rule, calculate the support and confidence of each rule )) ( ( ( ) and ) ) ( ( ) ) 5. ILLUSTRATION OF THE ALGORITHM In this section, we give an example to illustrate how the proposed algorithm can be used.
Let the original data be depicted below:
) ( ) ( ( ) )= ( )
( ) 11. if Sup(LHS,RHS) ≤ MST or conf(LHS,RHS) ≤ MCT = X+
= 12. go to line 8 13. select the next rule 14. repeat // line 9,10 and 11 on each new rule 15. if is empty
3.1 Explanation to Abbreviations in the Algorithm
RHS (right hand side): this is the right hand side of the rule generated MST (minimum support threshold): this is the support specified by the user of the algorithm MCT (minimum confidence threshold): this is the confidence threshold specified by the user min = minimum
Sup/Supp = support 4. STEPS TO THE PROPOSED ALGORITHM n = total number of transaction data m= total number of attributes (items) D= attribute 1 ≤ i ≤ n
= attribute 1 ≤ j ≤ m V= noise X= original data
= inverse of original data MCT= minimum confidence threshold MST= minimum support threshold
= each noisy attribute 1≤ k ≤ i STEP 1: for each transaction data D, i =1 to n, and for each attribute (item) j= 1 to m, transform the quantitative value into a noisy quantitative attribute value using the randomly generated formula
√ For X =
=
= ∑ on the STEP 3: for each noisy attribute 1≤j≤m and 1≤k≤m check for the that has the maximum value. If satisfies the above condition then the column whose has the maximum value is put in the set of 1- itemset which form the left hand side (LHS) of the rule i.e ={ }
T1 T2 T3 T4 T5 T1 T2 T3 T4 T5 (( )) Or STEP 3: for each noisy attribute 1≤j≤m and 1≤k≤m check for the that has the maximum value. if satisfies the above condition then the column whose has the maximum count is put in the set of 1- itemset which form the left hand side (LHS) of the rule i.e = * }
* } STEP 4: join the 1-itemset to the sensitive column in a way similar to that of apriori algorithm to form a 2- itemset. The 2itemmset is use to find the useful association rule by at the LHS and at the RHS similar to that of apriori algorithm STEP 5 (a): in order to hide sensitive rule, calculate the support and confidence of each rule (( ( ( (
) ( ) ) ( ) ( ) ( ) ) ) > MST but conf( ) < MCT, hence i.e (
(
is hidden i.e
+ = Since Sup( is hidden i.e = + = ) ) (
( = ( ( 6. DISCUSSION OF RESULT From the result shown in the transformed database, the algorithm was able to hide 4 out of the 5 items on the sensitive column resulting into 80% privacy protection of the sensitive column B. Comparing with the previous works of Manoj and Joshi [8] and Berberoglu and Kaya [9] on the same dataset, which hide only 1 out of the 5 items, resulting into 20% privacy protection of the sensitive column B of the data while the proposed algorithm hides 80% of the sensitive column B. 7. CONCLUSION AND FUTURE WORK In this work, we proposed an improved algorithm for hiding sensitive quantitative data that combines the concept of noise with association rule mining to generate the useful association rules in quantitative data and then hide them using privacy concept. The algorithm works on association rules in quantitative data unlike previous work done in this field which works on binary data. In the future we plan to apply the algorithm to real life dataset; also (( )) Or ) ) )
) Since Sup( is hidden i.e
+ = ( ( ( Since Sup( is not hidden ( 8/5=0.49 )) and ( ( ( )
) ( ( ) ( ( ( ( ( ( ) ) ) ) ) ( ) ( ) ( )
) ) ( ( )
) ( ) ( ) ( ) ) ) < MST but conf(
) > MCT ,hence ) > MST and conf( ) > MCT, hence we propose that in the proposed algorithm the association rule should contain more than one item on each side of the rule and that the algorithm should be used for text data after they might have been normalized into quantitative data.