臺灣博碩士論文加值系統

近年來由於越來越多的個人資料被公開、資料探勘演算法的日益精密、及對隱私侵犯的持續關注，使得隱私保護資料探勘之研究最近變的非常重要。對於關聯性法則藉由抑制其中的ㄧ些敏感的關聯規則以保護隱私也有很多實際應用。目前大部分的關聯規則隱藏技術都採行在單一的資料集內進行處理。然而在現實世界中，數據可能存在於分散環境中且被非信任的有意願合作之夥伴所擁有。此本論文中，我們提出了一個隱藏合作推薦關聯規則之架構，而其所處理之資料是水平分佈在彼此不信任的群體所擁有。我們也設計了演算法以在此架構下隱藏合作推薦關聯規則並且整合被消除後的資料集。此外我們也分析所提方法所產生的效能和不同的副作用並與用可靠第三方方法所做的結果加以比較。我們發現本研究所提出的非信任第三方的作法可在類似的副作用下具有較好的處理時間。

The study of privacy preserving data mining has become more important in recent years due to the increasing amount of personal data in public, the increasing sophistication of data mining algorithms to leverage this information, and the increasing concern of privacy breaches. Association rule hiding in which some of the association rules are suppressed in order to preserve privacy has been identified as a practical privacy preserving application. Most current association rule hiding techniques assume that the data to be sanitized are in one single data set. However, in the real world, data may exist in distributed environment and owned by non-trusting parties that might be willing to collaborate. In this work, we propose a framework to hide collaborative recommendation association rules where the data sets are horizontally partitioned and owned by non-trusting parties. Algorithms to hide the collaborative recommendation association rules and to merge the sanitized data sets are introduced. Performance and various side effects of the proposed approach are analyzed numerically. Comparisons with trusting-third-party approach are reported. The proposed non-trusting-third-party approach shows better processing time, with similar side effects.

CHINESE ABSTRACT III
ABSTRACT IV
ACKNOWLEDGEMENTS VI
CONTENT VII
LIST OF FIGURES IX
LIST OF TABLES XI
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND AND MOTIVATION 1
1.2 CONTRIBUTIONS 3
1.3 THESIS ORGANIZATION 4
CHAPTER 2 REVIEW OF RELATED WORKS 5
2.1 REVIEW OF PRIVACY PRESERVING DATA MINING 5
2.2 RELATED THREE BASIC APPROACHES OF ASSOCIATION RULE HIDING 6
CHAPTER 3 PROBLEM STATEMENT 9
3.1 COLLABORATIVE RECOMMENDATION ASSOCIATION RULES 9
3.2 PROBLEM DESCRIPTION 11
3.3 The Representation of Coding 11
CHAPTER 4 PROPOSED FRAMEWORK AND ALGORITHMS 13
4.1 HIDING FRAMEWORK 13
4.2 SANITIZATION STRATEGY 14
4.3 PATTERN-INVERSION TREE 15
4.4 SANITIZATION ALGORITHMS 17
4.5 EXAMPLE 24
CHAPTER 5 NUMERICAL EXPERIMENTS 30
5.1 EXPERIMENTAL RESULTS FOR THE TRANSACTION SIZE DISTRIBUTION 30
5.2 EXPERIMENTAL RESULTS FOR ONE AND TWO RECOMMENDED ITEMS 32
5.3 EXPERIMENTAL RESULTS FOR MTH AND HTM APPROACHES 34
CHAPTER 6 CONCLUSION 41
REFERENCES 42
LIST OF FIGURES
FIGURE 1A. A HTM APPROACH TO HIDE CRAR ON HORIZONTALLY PARTITIONED DATA SETS 14
FIGURE 1B. A MTH APPROACH TO HIDE CRAR ON HORIZONTALLY PARTITIONED DATA SETS 14
FIGURE 2. THE PI-TREE FOR DATA SET D1 16
FIGURE 3. THE PI-TREE FOR DATA SET D2 17
FIGURE 4. THE PI-TREE FOR DATA SET D1'' 26
FIGURE 5. THE PI-TREE FOR DATA SET D2'' 26
FIGURE 6. THE PI-TREE FOR DATA SET D1''+ D2'' 27
FIGURE 7. THE PI-TREE FOR THE DATA SET D1 + D2 28
FIGURE 8. THE PI-TREE FOR THE DATA SET (D1 + D2)'' 29
FIGURE 9. DATA SET TRANSACTION SIZE DISTRIBUTION 31
FIGURE 10. NUMBERS OF TOTAL AND HIDDEN RULES (IBM-ARTIFICIAL) 33
FIGURE 11. NUMBERS OF TOTAL AND HIDDEN RULES (BMS-WEBVIEW-1) 33
FIGURE 12. TIME EFFECTS (IBM-ARITIFICIAL) 34
FIGURE 13. TIME EFFECTS (BMS-WEBVIEW-1) 35
FIGURE 14. DATA SET EFFECTS (IBM-ARITIFICIAL) 35
FIGURE 15. DATA SET EFFECTS (BMS-WEBVIEW-1) 36
FIGURE 16. ONE-ITEM SIDE EFFECTS OF MTH (IBM-ARITIFICIAL) 37
FIGURE 17. ONE-ITEM SIDE EFFECTS OF HTM (IBM-ARITIFICIAL) 37
FIGURE 18. ONE-ITEM SIDE EFFECTS OF MTH (BMS-WEBVIEW-1) 38
FIGURE 19. ONE-ITEM SIDE EFFECTS OF HTM (BMS-WEBVIEW-1) 38
LIST OF TABLES
TABLE 1. DATA SET D1 10
TABLE 2. DATA SET D2 12
TABLE 3. JOINTED DATA SET 12
TABLE 4. THE DATASET D1 + D2 BEFORE AND AFTER HIDING ITEM C USING THE MTH AND HTM APPROACHES 29
TABLE 5. DATA SET CHARACTERISTICS 31
TABLE 6. COMPARISONS OF AVERAGE EFFECTS 39

[1]A. Atallah, E. Bertino, A. Elmagarmid, M. Ibrahim, and V. Verykios, "Disclosure Limitation of Sensitive Rules", In proceedings of IEEE Knowledge and Data Engineering Workshop, 45-52, Chicago, Illinois, November 1999.
[2]A. Evfimievski, "Randomization in Privacy Preserving Data Mining", In Proceedings of the SIGKDD Explorations, 4(2), Issue 2, 43-48, Dec. 2002.
[3]A. Evfimievski, J. Gehrke and R. Srikant, "Limiting Privacy Breaches in Privacy Preserving Data Mining", In Proceedings of the PODS 2003, 212-222, June 9-12, 2003, San Diego, CA.
[4]A. Evfimievski, R. Srikant, R. Agrawal, and J. Gehrke, "Privacy Preserving Mining of Association Rules", In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 217-228, Edmonton, Canada, July 2002.
[5]C. Aggarwal, P. S. Yu, Privacy-Preserving Data Mining: Models and Algorithms, Springer, 2008.
[6]C. Clifton and D. Marks, "Security and Privacy Implications of Data Mining", in SIGMOD Workshop on Research Issues on Data Mining and knowledge Discovery, 15-19, 1996.
[7]C. Clifton, "Using Sample Size to Limit Exposure to Data Mining", Journal of Computer Security, 8(4), 281-307, 2000.
[8]C. Clifton, M. Kantarcioglu, X. D. Lin and M. Y. Zhu, "Tools for Privacy Preserving Distributed Data Mining", SIGKDD Explorations, 4(2), 1-7, Dec. 2002.
[9]D. Agrawal and C. C. Aggarwal, "On the Design and Quantification of Privacy Preserving Data Mining Algorithms", In Proceedings of the 20th Symposium on Principles of Database Systems, 247-255, Santa Barbara, California, USA, May 2001.
[10]D. Shah, S. Zhong, "Two Methods for Privacy Preserving Data Mining with Malicious Participants", Information Sciences, Vol. 177, No. 23, 5468-5483, 2007.
[11]E. Dasseni, V. Verykios, A. Elmagarmid and E. Bertino, "Hiding Association Rules by Using Confidence and Support", In Proceedings of 4th Information Hiding Workshop, 369-383, Pittsburgh, PA, 2001.
[12]H. Huang, X. Wu, and R. Relue, "Association Analysis with One Scan of Databases", In Proceedings of IEEE International Conference on Data Mining, Maebashi City, Japan, December, 629-632, 2002.
[13]IBM. Almaden. Quest Synthetic Data Generation Code. http://www.almaden.ibm.com/cs/disciplines/iis/.
[14]J. Han, J. Pei, and Y. Yin, "Mining Frequent Patterns without Candidate Generation", In Proceedings of ACM International Conference on Management of Data (SIGMOD), 1-12, 2002.
[15]J. Vaidya and C. Clifton. "Privacy Preserving Association Rule Mining in Vertically Partitioned Data", In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 639-644, Edmonton, Canada, July 2002.
[16]J. Vaidya, C. Clifton, and M. Zhu, Privacy Preserving Data Mining, Springer, 2006.
[17]M. Kantarcioglu and C. Clifton, "Privacy-preserving distributed mining of association rules on horizontally partitioned data", In ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery, 24-31, June 2002.
[18]R. Agrawal and R. Srikant, "Privacy Preserving Data Dining", In Proceedings of ACM SIGMOD Conference on Management of Data, 439-450, Dallas, Texas, May 2000.
[19]R. Agrawal, T. Imielinski, and A. Swami, "Mining Association Rules between Sets of Items in Large Databases", In Proceedings of ACM SIGMOD International Conference on Management of Data, 207-216, Washington DC, May 1993.
[20]S. J. Rizvi and J. R. Haritsa, "Maintaining data privacy in association rule mining", In Proceedings of the 28th Int''l Conference on Very Large Databases, 682-693, August 2002.
[21]S. Oliveira, O. Zaiane, "A Unified Framework for Protecting Sensitive Association Rules in Business Collaboration", Int. J. Business Intelligence and Data Mining, Vol. 1, No. 3, 247-287, 2006.
[22]S. Oliveira, O. Zaiane, "Algorithms for Balancing Privacy and Knowledge Discovery in Association Rule Mining", In Proceeding of 7th International Database Engineering and Applications Symposium (IDEAS03), pp.54, Hong Kong, July 2003.
[23]S. Oliveira, O. Zaiane, "An Efficient On-Scan Sanitization for Improving the Balance Between Privacy and Knowledge Discovery", Technical Report TR 03-15, Department of Computing Science, University of Alberta, Canada, June 2003.
[24]S. W. Kim, S. Park, J.I. Won, and S.W. Kim, "Privacy Preserving Data Mining of Sequential Patterns for Network Traffic Data", Information Sciences, Vol. 178, No. 3, 694-713, 2008.
[25]S.L. Wang, D. Patel, A. Jafari, and T.P. Hong, "Hiding Collaborative Recommendation Association Rules", Applied Intelligence, Vol. 26, No. 1, 66-77, 2007.
[26]S.L. Wang, T.P. Hong, "One-Scan Sanitization of Collaborative Recommendation Association Rules", In Proceedings of National Computer Symposium, November, 2007, Taichun, Taiwan, 170-176.
[27]S.L. Wang, T.P. Hong, "Privacy-Preserving Algorithms for Distributed Mining of Frequent Itemsets", Information Sciences, Vol. 177, No. 2, 490-503, 2007.
[28]V. Verykios, A. Elmagarmid, E. Bertino, Y. Saygin, and E. Dasseni, "Association Rules Hiding", IEEE Transactions on Knowledge and Data Engineering, Vol. 16, No. 4, 434-447, April 2004.
[29]V. Verykios, E. Bertino, I.G. Fovino, L.P. Provenza, Y. Saygin, and Y. Theodoridis, "State-of-the-art in Privacy Preserving Data Mining", SIGMOD Record, Vol. 33, No. 1, 50-57, March 2004.
[30]Y. Lindell and B. Pinkas, "Privacy Preserving Data Mining", In CRYPTO, 36-54, 2000.
[31]Y. Saygin, V. Verykios, and C. Clifton, "Using Unknowns to Prevent Discovery of Association Rules", SIGMOND Record 30(4): 45-54, December 2001.
[32]Y.H. Wu, C.M. Chiang, and A.L.P. Chen, "Hiding Sensitive Association Rules with Limited Side Effects", IEEE Transactions on Knowledge and Data Engineering, Vol. 19, No. 1, 29-42, 2007.
[33]Z. Zheng, R. Kohavi, L. Mason, "Real World Performance of Association Rules Algorithms", In Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 401-206, San Francisco, CA, USA, August, 2001.