隱私保護資料探勘是一個受歡迎的研究方向，但到目前為止，在利潤探勘的隱私保護上尚未被討論。如何在分享的過程中取得隱私保護與知識發掘間的平衡是一個重要的議題。本研究專注在利潤探勘的隱私保護並且提出HHUIF及MSICF兩個有效率的演算法來達成隱藏敏感項目集的目標，使得競爭對手不能從修改過的資料庫中探勘出敏感項目集。除此之外，我們在隱藏敏感項目集的過程中盡可能將處理過的資料庫影響降至最低。實驗結果顯示在兩個人造的資料集中，HHUIF演算法相較於MSICF演算法有較低的意外隱藏，此外，MSICF演算法相較於HHUIF演算法在原始資料庫與處理後資料庫間總是有較低的差異除了在MinUtility = 4000的情況下。

Privacy Preserving Data Mining (PPDM) is a popular research direction in data mining, but so far privacy preserving utility mining was not discussed. How to strike a balance between privacy protection and knowledge discovery in the sharing process is an important issue. This study focuses on the privacy preserving utility mining and present two effective algorithms, HHUIF and MSICF, to achieve the goal of hiding sensitive itemsets so that the adversaries can not mine them from the modified database. In addition, we minimize the impact on the sanitized database in the process of hiding sensitive itemsets. In our experimental results, HHUIF has the lower miss costs than MSICF does in two synthetic datasets. Besides, MSICF has the lower difference between the original and sanitized databases than HHUIF has, except in the case where MinUtility = 4000.

Contents
Abstract i
Chinese Abstract ii
Acknowledgements iii
Contents iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
Chapter 2 Related Works 4
2.1 Association Rule Mining 4
2.2 Utility Mining 8
2.3 Privacy Preserving of Association Rule Mining 11
2.4 The Sanitization Process 15
Chapter 3 Proposed Algorithms 16
3.1 The General Approach 16
3.2 The Sanitization Algorithms 17
3.2.1 Hiding High Utility Item First Algorithm 17
3.2.2 Maximum Sensitive Itemsets Conflict First Algorithm 21
Chapter 4 Experimental Results 24
4.1 IBM Synthetic Data Generator 24
4.2 Datasets 25
4.3 Effectiveness Measurement 25
4.4 Comparison of Hiding Failure 27
4.5 Comparison of Miss Cost 28
4.6 Comparison of Difference between the Original and Sanitized Databases 32
Chapter 5 Conclusions and Future Work 34
Reference 35

[1] R. Agrawal, T. Imielinski, and A. N. Swami, “Mining association rules between sets of items in large databases,” In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, pp. 207-216, Washington, 1993.
[2] R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” In Proceedings
of 20th International Conference on Very Large Data Bases, pp. 487-499, Morgan Kaufmann, 1994.
[3] M. Atallah, E. Bertino, A. Elmagarmid, M. Ibrahim, and V. Verykios, “Disclosure limitation of sensitive rules,” In Proceedings of IEEE Knowledge and Data Engineering Workshop, pp. 45-52, Chicago, Illinois, November 1999.
[4] B. Barber, and H. J. Hamilton, “Extracting share frequent itemsets with infrequent subsets,” Data Mining and Knowledge Discovery, vol. 7, no. 2, pp.153-185, April 2003.
[5] C. H. Cai, W. C. Fu, C. H. Cheng, and W. W. Kwong, “Mining association rules with weighted items,” In Proceedings of 1998 Intl. Database Engineering and Applications Symposium, pp. 68-77, Cardiff, Wales, U.K., 1998.
[6] R. Chan, Q. Yang, and Y. D. Shen, “Mining high utility itemsets,” In Proceedings of the 2003 IEEE International Conference on Data Mining (ICDM 2003), pp. 19-26, Melbourne, FL, 2003.
[7] C. Clifton and D. Marks, “Security and privacy implications of data mining,” In Proceedings of the 1996 ACM SIGMOD Workshop on Data Mining and Knowledge Discovery, pp.15-19, 1996.
[8] E. Dasseni, V. S. Verykios, A. K. Elmagarmid, and E. Bertino, “Hiding association rules by using confidence and support,” In Proceedings of the 4th Information Hiding Workshop, pp. 369-383, Pittsburg, PA, April 2001.
[9] 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, Edmonton, Canada, July 2002.
[10] J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” In
Proceedings of 2000 ACM-SIGMOD Intl. Conf. on Management of Data, pp. 1-12, Dallas, TX, 2000.
[11] IBM Almaden Research Center. Synthetic data generation code for associations and sequential patterns.
http://www.almaden.ibm.com/cs/projects/iis/hdb/Projects/data_mining/mining.shtml
[12] Y. C. Li, J. S. Yeh, and C. C. Chang, "Efficient algorithms for mining share-frequent itemsets," in Fuzzy Logic, Soft Computing and Computational Intelligence - 11th World Congress of International Fuzzy Systems Association (IFSA 2005), Springer Tsinghua, China, pp. 534-539, 2005.
[13] Y. Liu, W. K. Liao, and A. Choudhary, “A two-phase algorithm for fast discovery of high utility itemsets,” in PAKDD 2005, Springer Verlag, Berlin Heidelberg, vol. 3518, pp. 689-695, 2005.
[14] H. Mannila, H. Toivonen, and A. I. Verkamo, “Efficient algorithms for discovering association rules,” In AAAI Workshop on Knowledge Discovery in Databases (KDD’94), pp. 181-192, Seattle, Washington, 1994. AAAI Press.
[15] S. Mingjun, R. Sanguthevar, “A transaction mapping algorithm for frequent itemsets mining,” IEEE Transactions on Knowledge and Data Engineering, vol. 18, no. 4, pp. 472-481, 2006.
[16] S. R. M. Oliveira and O. R. Zaïne, “A framework for enforcing privacy in mining frequent patterns,” Technical Report, TR02-13, Computer Science Department, University of Alberta, Canada, June 2000.
[17] S. R. M. Oliveira and O. R Zaïane, ”Privacy preserving frequent itemset mining,” In Proceedings of the IEEE ICDM Workshop on Privacy, Security, and Data Mining, pp. 43–54, Maebashi City, Japan, December 2002.
[18] S. R. M. Oliveira, O. R. Zaïane, and Y. Saygin, “Secure association rule sharing,” In Proceedings of 8th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’04), pp. 74-85, Australia, May 2004.
[19] J. S. Park, M. S. Chen, and P. S. Yu, “An effective hash-based algorithm for mining association rules,” In Proceedings of 1995 ACM-SIGMOD International Conference on Management of Data, pp. 175-186, San Jose, CA, May 1995.
[20] S. Rizvi, and J. Haritsa, “Maintaining data privacy in association rule mining,” In Proceedings of 28th Intl. Conf. on Very Large Databases (VLDB), August 2002.
[21] S. J. Rizvi and J. R. Haritsa, “Privacy-preserving association rule mining”, In Proceedings of the 28th Int’l Conference on Very Large Databases, August 2002.
[22] Y. Saygin, V. S. Verykios, and C. Clifton, “Using unknowns to prevent discovery of association rules,” SIGMOD Record, vol. 30, no. 4, pp.45-54, 2001.
[23] A. Veloso, B. Rocha, M. d. Carvalho, and W. Meira, ”Real world association rule mining,” Lecture Notes in Computer Science 2405 - Proceedings of the 19th British National Conference on Databases: Advances in Databases, B. Eaglestone, S. North, and A. Poulovassilis, Eds., Springer-Verlag, London, pp.77-89, 2002.
[24] 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, pp. 50-57, March 2004.
[25] 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, pp.434-447, April 2004.
[26] W. Wang, J. Yang, and P. Yu, “Efficient mining of weighted association rules (WAR),”
In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 270-274, 2000.
[27] H. Yao, H. J. Hamilton, and C. J. Butz, “A foundational approach to mining itemset utilities from Databases,” In Proceedings of the 4th SIAM International Conference on Data Mining, Florida, USA, 2004.