Data Mining: The Textbook

Yüklə 17,13 Mb. səhifə 403/423 tarix 07.01.2024 ölçüsü 17,13 Mb. #211690

1-Data Mining tarjima

20.8. EXERCISES

693

11. 
    Show that the monotonicity property is satisfied by (a) t-closeness with variational distances, and (b) t-closeness with KL-measure.
    

11. 
    Consider any group-based anonymity quantification measure f (P ), in which the anonymity condition is of the form f (P ) ≥ thresh. (An example of such a measure is entropy in -diversity.) Here, P = (p₁ . . . p_r) is the sensitive attribute distribu-tion vector. Show that if f (P ) is concave, then the anonymity definition will satisfy the monotonicity property with respect to generalization. Also show that convexity ensures monotonicity in the case of anonymity conditions of the form f (P ) ≤ thresh.
    
12. 
    Implement the (a) Incognito, and (b) Mondrian algorithms for variational distance-based, and KL distance-based t-closeness, by making changes to your code for Exercise
    

4. 
   

11. 
    Suppose that you had an anonymized binary transaction database containing the items bought by different customers on a particular day. Suppose that you knew that the transactions of your family friend contained a particular subset B of items, although you did not know the other items bought by her. If every item is bought independently with probability 0.5, show that the probability that at least one of n other customers buys exactly the same pattern of items, is given by at most n/2B . Evaluate this expression for n = 104 and B = 20. What does this imply in terms of the privacy of her other buying patterns?
    

11. 
    Repeat Exercise 14 for movie ratings taking on one of R possible values instead of
    

2. 
   Assume that each rating possibility has identical probability of 1/R, and the rat-ings of different movies are independent and identically distributed. What are the corresponding probabilities of re-identification with B known ratings, and n different individuals?
   

16. 
    Write a computer program to re-identify the subject of a database with B known sensitive attributes.
    

Bibliography

1. 
   N. Adam, and J. Wortman. Security-control methods for statistical databases. ACM Computing Surveys, 21(4), pp. 515–556, 1989.
   

2. 
   G. Adomavicius, and A. Tuzhilin. Toward the next generation of recommender sys-tems: A survey of the state-of-the-art and possible extensions. IEEE Transactions on Knowledge and Data Engineering, 17(6), pp. 734–749, 2005.
   

3. 
   R. C. Agarwal, C. C. Aggarwal, and V. V. V. Prasad. A tree projection algorithm for generation of frequent item sets. Journal of parallel and Distributed Computing, 61(3), pp. 350–371, 2001. Also available as IBM Research Report, RC21341, 1999.
   

4. 
   R. C. Agarwal, C. C. Aggarwal, and V. V. V. Prasad. Depth-first generation of long patterns. ACM KDD Conference, pp. 108–118, 2000. Also available as “Depth-first generation of large itemsets for association rules.”IBM Research Report, RC21538, 1999.
   

5. 
   C. Aggarwal. Outlier analysis. Springer, 2013.
   

6. 
   C. Aggarwal. Social network data analytics. Springer, 2011.
   

7. 
   C. Aggarwal, and P. Yu. The igrid index: reversing the dimensionality curse for simi-larity indexing in high-dimensional space. KDD Conference, pp. 119–129, 2000.
   

8. 
   C. Aggarwal, and P. Yu. On static and dynamic methods for condensation-based privacy-preserving data mining. ACM Transactions on Database Systems (TODS), 33(1), 2, 2008.
   

9. 
   C. Aggarwal. On unifying privacy and uncertain data models. IEEE International Conference on Data Engineering, pp. 386–395, 2008.
   

10. 
    C. Aggarwal. On k-anonymity and the curse of dimensionality, Very Large Databases Conference, pp. 901–909, 2005.
    

11. 
    C. Aggarwal. On randomization, public information and the curse of dimensionality.
    

Yüklə 17,13 Mb.

Dostları ilə paylaş: