臺灣博碩士論文加值系統

由於資訊化時代的來臨，資料呈現巨量的成長。在如此巨大的資料庫中，可能隱含著對企業有用的訊息，因此必須藉助資料探勘來挖掘出有利的資訊以協助公司進行決策。另外由於跨國企業、區域性等環境因素，使得現今資料的分佈多以分散式架構來部署，在面對資料分散、協同合作等環境下，這也讓分散式相關議題成為近年來相當熱門的議題之ㄧ。企業為了創造共同利益，可能會採取策略聯盟等合作方式，而不同公司合作時，並非所有資料都能夠完全公開，因此合作的同時也必須保護企業獨一無二的資料不被其他公司所取得，所以分散式決策樹探勘的過程中必須達到保護隱私的目的。因此我們提出了一個多單位合作之決策樹隱私權防護的方法，此方法採以C4.5為基礎並利用垂直屬性切割在水平資料庫環境下進行運作，此方法主要是保護不同單位間的規則不被其他單位所得知，同時又能達到準確無誤差的共同探勘結果。

As the recent development of the computer science, the data quantity of enterprise database increases rapidly. To extract the usefulness information from huge databases, many efficient data mining technologies have been applied. In recent years, the data mining tools are more and more powerful, and the risk of privacy leak has become an urgent problem. Privacy preserving data mining is a relatively new research area in data mining and knowledge discovery. In a common situation, databases are distributed among several organizations who would like to cooperate mining to extract global knowledge, but each party needs prevent it’s privacy not directly sharing the data. Therefore, this study presents an algorithm for privacy preserving distributed decision tree based on C4.5. While this has been done for horizontally partitioned data, this study presents an algorithm for vertically partitioned attributes. Each site computes a portion of data, and then they exchange the result to each other. The goal of this paper is to obtain correct data mining results and preserve the privacy of each site.

摘要 i
Abstract ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
一、 緒論 1
1.1 研究背景 1
1.2 研究動機 3
1.3 研究目的 4
1.4 論文架構與內容 4
二、 文獻探討 5
2.1 資料探勘與決策樹 5
2.2 隱私權防護 15
2.3 決策樹隱私權防護 20
三、 分散式決策樹隱私權防護 22
3.1 方法架構與設計 22
3.1.1 水平分散式資料散佈 22
3.1.2 資料交換與運作架構 23
3.2 垂直屬性資料交換 24
四、 安全性與通訊分析 29
4.1 安全性分析 29
4.2 惡意單位 37
4.3 通訊量分析 38
五、 結論與未來研究方向 40
參考文獻 41
附錄一 44
附錄二 45
附錄三 46

[1]R. Agrawal and R. Srikant, "Fast Algorithms for Mining Association Rules," in Proceedings of 20th International Conference on Very Large Data Bases, Santiago, Chile, 1994, pp. 487-499.
[2]R. Agrawal and R. Srikant, "Mining Sequential Patterns " in 11th International Conference on Data Engineering (ICDE''95), Taipei, Taiwan, 1995, pp. 3-14.
[3]R. Agrawal and R. Srikant, "Privacy-Preserving Data Mining," in Proceedings of the 2000 ACM SIGMOD Conference on Management of Data, Dallas, Texas, 2000, pp. 439 - 450.
[4]A. Ambainis, M. Jakobsson, and H. Lipmaa, "Cryptographic Randomized Response Techniques," Lecture Notes in Computer Science, vol. 2947, pp. 425-438, 2004.
[5]M. J. Berry and G. Linoff, Data Mining Techniques: For Marketing, Sales, and Customer Support: Wiley, 1997.
[6]BOINC, "http://boinc.berkeley.edu/."
[7]L. Breiman, J. Friedman, C. J. Stone, and R. A. Olshen, Classification and Regression Trees: Chapman & Hall/CRC, 1984.
[8]C5.0, "http://www.rulequest.com/see5-info.html."
[9]Chris Clifton, Murat Kantarcioglu, and J. Vaidya, "Defining Privacy for Data Mining," in National Science Foundation Workshop on Next Generation Data Mining Baltimore, MD, 2002, pp. 126-133.
[10]Chris Clifton, Murat Kantarcioglu, Xiaodong Lin, and M. Y. Zhu, "Tools for Privacy Preserving Distributed Data Mining," ACM SIGKDD Explorations, vol. 4, pp. 28-34, 2002.
[11]C. Clifton, "Privacy Preserving Distributed Data Mining " 2001.
[12]C. Clifton and D. Marks, "Security and Privacy Implications of Data Mining," in Proceedings of the ACM SIGMOD Workshop on Data Mining and Knowledge Discovery, Montreal, Canada, 1996, pp. 15-19.
[13]A. Evfimievski, "Randomization in Privacy Preserving Data Mining," SIGKDD Explorations: Newsletter of the ACM Special Interest Group on Knowledge Discovery and Data Mining, vol. 4, pp. 43-48, 2002.
[14]A. Evfimievski, R. Srikant, R. Agrawal, and J. Gehrke, "Privacy Preserving Mining of Association Rules," in Proceeding of 8th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining, 2002, pp. 217-228.
[15]F. Emekci, O. D. Sahin, D. Agrawal, and A. E. Abbadi, "Privacy Preserving Decision Tree Learning over Multiple Parties," Data & Knowledge Engineering vol. 63, pp. 348-361, November 2007.
[16]Folding@Home, "http://folding.stanford.edu/."
[17]J. Han and M. Kamber, Data Mining Concepts and Techniques, second ed.: Morgan Kaufmann 2006.
[18]Hillol Kargupta, Souptik Datta, Qi Wang, and K. Sivakumar, "Random Data Perturbation Techniques and Privacy Preserving Data Mining," Knowledge and Information Systems, vol. 7, pp. 387-414, 2005.
[19]B. Hiram and P. William, "A Model-free Approach for Analysis of Complex Contingency Data in Survey Research," Journal of Marketing Research vol. 17, pp. 503-515, 1980.
[20]L. Hyafil and R. L. Rivest, "Constructing Optimal Binary Trees is NP-complete," Information Processing Letters, vol. 5, pp. 15-17, 1976.
[21]Jaideep Vaidya, Chris Clifton, and M. Zhu, Privacy Preserving Data Mining: Springer, 2005.
[22]C. C. Jaideep Vaidya, "Privacy-Preserving K-Means Clustering over Vertically Partitioned Data," in The Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Washington, DC, 2003, pp. 206 - 215.
[23]S. L. Matthias Klusch, Gianluca Moro, "Distributed Clustering Based on Sampling Local Density Estimates," in Proceedings of International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 2003, pp. 485-490.
[24]T. Mitchell, Machine Learning: McGraw Hill, 1997.
[25]Murat Kantarcioglu and C. Clifton, "Privacy-preserving Distributed Mining of Association Rules on Horizontally Partitioned Data," in The ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD''02), 2002.
[26]J. V. Murat Kantarcioglu, "Privacy Preserving Naive Bayes Classifier for Horizontally Partitioned Data," in IEEE ICDM Workshop on Privacy Preserving Data Mining, 2003, pp. 3-9.
[27]B. Pinkas, "Cryptographic Techniques for Privacy-Preserving Data Mining," SIGKDD Explorations, vol. 4, pp. 12 -19, December 2002.
[28]H. Polat and W. Du, "Privacy-Preserving Collaborative Filtering using Randomized Perturbation Techniques," in The Third IEEE International Conference on Data Mining (ICDM''03) Melbourne, FL, 2003.
[29]J. R. Quinlan, "Introduction of Decision Tree," Machine Learning, vol. 1, pp. 81-106, 1986.
[30]J. R. Quinlan, C4.5: programs for machine learning: Morgan Kaufmann Publishers Inc. , 1993.
[31]MIT. Technology Review, "10 Emerging Technologies That Will Change the World, http://www.globalfuture.com/mit-trends2001.htm," 2001.
[32]E. Suthampan and S. Maneewongvatana, "Privacy Preserving Decision Tree in Multi Party Environment," Lecture Notes in Computer Science, vol. 3689, pp. 727-732, November 15 2005.
[33]J. Vaidya, "Privacy Preserving Data Mining over Vertically Partitioned Data." vol. PhD thesis: Purdue University, 2003.
[34]J. Vaidya and C. Clifton, "Privacy Preserving Association Rule Mining in Vertically Partitioned Data," in The Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002.
[35]V. S. Verykios, E. Bertino, I. N. Fovino, L. P. Provenzaand, Y. Saygin, and Y. Theodoridis, "State-of-the-Art in Privacy Preserving Data Mining," ACM SIGMOD Record, vol. 33, pp. 50-57, March 2004.
[36]Weka, "http://www.cs.waikato.ac.nz/ml/weka/."
[37]D. Wenliang and Z. Zhijun, "Building Decision Tree Classifier on Private Data," in IEEE ICDM Workshop on Privacy, Security and Data Mining (PSDM 2002). vol. 14 Maebashi City, Japan, 2002, pp. 1-8.
[38]Worldcommunitygrid, "http://www.worldcommunitygrid.org/."
[39]M.-J. Xiao, K. Han, L.-S. Huang, and J.-Y. Li, "Privacy Preserving C4.5 Algorithm over Horizontally Partitioned Data," in Proceedings of the Fifth International Conference on Grid and Cooperative Computing 2006, pp. 78-85.
[40]M.-J. Xiao, L.-S. Huang, Y.-L. Luo, and H. Shen, "Privacy Preserving ID3 Algorithm over Horizontally Partitioned Data," in Proceedings of the Sixth International Conference on Parallel and Distributed Computing Applications and Technologies(PDCAT05), 2005, pp. 239-243.