臺灣博碩士論文加值系統

隨著電腦技術的快速進展，數位資料亦隨之急遽產生。因而，許多知識分析與資料探勘的技術應運而生，以歸納並整理大量的資料。其中一個熱門的議題便是關連法則探勘。藉由使用關連法則的探勘技術，可找出資料的項目中之關連性。然而，濫用這些方法卻可能帶來出乎預料的副作用。於是，近年來研究者開始頻繁地探討關連法則的隱藏議題。
在此篇論文當中，我們提出一個可隱藏機密資訊而不致產生任何副作用的方法。我們的方法可分為三個步驟，分別對應至可能遭遇到的三個問題。首先，我們使用一種樣版觀念，藉由此樣版，我們找出可修改的交易與可能受影響的非機密關連法則。另外，為增進效率，我們針對我們的方法提出一種索引結構。接著，在所選擇的交易當中，我們進一步地選擇不會隱藏任何非機密關連法則的交易。在第三個步驟當中，我們檢查這些可修改的交易以避免產生多餘的錯誤法則。反覆進行這些步驟，我們即可隱藏關連法則而不致產生任何非預期的副作用。
在我們的實驗當中，我們針對各種不同的策略，分析我們的方法的效果與效率。除此之外，我們的實驗驗證我們的方法對於資料庫大小有著完美的延展性。值得注意的是，我們考慮所有副作用的情況所耗費的時間，僅比不考慮副作用的情況稍慢一點。由實驗結果，我們可證明我們的方法擁有極佳的效果。

As the growth of computer technology has been advanced, the amount of data has been increasing with an extremely fast rate. A variety of methods for knowledge discovery and data mining have been developed to help people digest the huge number of data. One of the popular data mining research issues is association rule mining. Based on the techniques for mining association rules, the correlations between data items can be identified. However, the misuses of these methods may bring undesired side effects to the people. Recently, researchers have made great efforts at hiding association rules.
In this thesis, we develop a new approach that can hide the sensitive information without generating undesired side effects. Our approach consists of three steps corresponding to three possible problems. At first, we adopt the template concept to identify either the set of modifiable transactions or the set of probably affected association rules. For efficiency, we design indexing facilities for fast retrieval of the required information in the transaction database. Second, among the selected transactions for hiding sensitive rules, we further select the transactions that will not hide any of the non-sensitive rules. At the third step, we examine these selected transactions to avoid generating extra rules. Iteratively, sensitive rules can be hidden and the undesired side effects are avoided.
In the experiments, we show the effectiveness of our approach according to the three conditions and analyze the performance of different methods for database modifications. Moreover, the results also show that our proposed approach has perfect scalability to the database size. Specifically, the time of the approach that considers all the three conditions is just a little bit slower than the time of the one that do not consider the two side effects.

Abstract i
Acknowledgement ii
Contents iii
List of Figures iv
List of Tables vi
1.Introduction 1
2.Related Work 6
3.Problem Definition 10
4.Our Algorithm 27
5.Experimental Results 38
6.Conclusion and Future Work 48
A.Appendix. The Algorithms of Information Hiding System 49
Reference 55

[1]D. Agrawal and C. C. Aggarwal, “On the Design and Quantification of Privacy Preserving Data Mining Algorithms”, Proceedings of 20th ACM Symposium on Principles of Database Systems (PODS), May 2001.
[2]M. Atallah, E. Bertino, A. Elmagarmid, M. Ibrahim and V. Verykios. “Disclosure Limitation of Sensitive Rules”. Proceedings of IEEE Knowledge and Data Engineering Workshop, Chicago, Illinois, November 1999.
[3]R. Agrawal, T. Imielinski and A. Swami. “Mining Association Rules between Sets of Items in Large Databases”. Proceedings of the ACM SIGMOD Conference on Management of Data, pp. 207-216, Washington, D.C., May 1993.
[4]R. Agrawal, H. Mannila, R. Srikant, H. Toivonen and A. I. Verkamo. “Fast Discovery of Association Rules”. Advances in Knowledge Discovery and Data Mining, Chapter 12, pp. 307-328, AAAI/MIT Press, 1996.
[5]R. Agrawal and R. Srikant. “Fast Algorithm for Mining Association Rules”. International Conference on Very Large Data Bases (VLDB), pp. 487-499, 1994.
[6]R. Agrawal and R. Srikant. “Privacy-preserving Data Mining”. Proceedings of the ACM SIGMOD Conference on Management of Data, Dallas, TX, May 14-19 2000.
[7]C. Clifton and D. Marks. “Security and Privacy Implications of Data Mining”. Proceedings of the ACM SIGMOD Workshop on Data Mining and Knowledge Discovery, pp. 15-19, May 1996.
[8]C. Clifton. “Protecting against Data Mining through Sample”. Proceedings of 13th IFIP WG11.3 Conference on Database Security, Seattle, Washington, 1999.
[9]E. Dasseni, V. S. Verykios, A. K. Elmagarmid and E. Bertino. “Hiding Association Rules by Using Confidence and Support”. Proceedings of the 4th Information Hiding Workshop (IHW2001), Pittsburgh, PA, April 2001.
[10]V. Estivill-Castro and L. Brankovic. “Data Swapping: Balancing Privacy against Precision in Mining for Logic Rules”, Data Warehousing and Knowledge Discovery DaWaK-99, pp. 389-398. Springer-Verlag Lecture Notes in Computer Science 1676, 1999.
[11]A. Evfimievski, R. Srikant, R. Agrawal and J. Gehrke, “Privacy Preserving Mining of Association Rules”, Proceedings of 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Edmonton, Alberta, Canada, 2002.
[12]C. Faloutsos, H. V. Jagadish and N. D. Sidiropoulos. “Recovering Inormation from Summary Data”. Proceedings of the 23rd International Conference on Very Large Databases, pp. 36-45, Athens, Greece, 1997.
[13]J. Han, J. Pei and Y. Yin. “Mining Frequent Patterns without candidate generation”. Proceedings of the ACM SIGMOD, 2000.
[14]V. S. Iyengar, “Transforming Data to Satisfy Privacy Constraints”, Proceedings of 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), Edmonton, Alberta, Canada, 2002.
[15]M. Kantarcioglu and C. Clifton. “Privacy-preserving Distributed Mining of Association Rules on Horizontally Partitioned Data”. Proceedings of ACM SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD’02), June 2 2002.
[16]G. J. Kowalski, M. T. Maybury. “Information Storage and Retrieval Systems Theory and Implementation”, Kluwer Academic Publishers, Second Edition, 1997.
[17]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.
[18]J. S. Park, M. S. Chen and P. S. Yu, “An Effective Hash-Based Algorithm for Mining Association Rules”. Proceedings of ACM SIGMOD Record, Vol. 24, No. 2, 1995.
[19]S. J. Rizvi and J. R. Haritsa. “Privacy-preserving Association Rule Mining”. Proceedings of 28th International Conference on Very Large Data Bases (VLDB), August 20-23 2002.
[20]P. Samarati. “Protecting Respondents’ Identities in Microdata Release”. IEEE Transaction on Knowledge and Data Engineering, Vol.13, No. 6, 2001.
[21]R. Srikant and R. Agrawal. “Mining Generalized Association Rules”. Proceedings of the International Conference on Very Large Data Bases (VLDB), pp. 407-419, 1995.
[22]Y. Saygin, V. Verykios and C. Clifton, “Using Unknowns to Prevent Discovery of Association Rules”, Proceedings of ACM SIGMOD Record, Vol. 30, No. 4, 2001.
[23]Y. Saygin, V. Verykios and A. Elmagarmid, “Privacy Preserving Association Rule Mining”, Proceedings of 12th International Workshop on Research Issues in Data Engineering (RIDE), February 2002.
[24]J. Vaidya and C. Clifton. “Privacy Preserving Association Rule Mining in Vertically Partitioned Data”. Proceedings of the 8th ACM SIGMOD International Conference on Knowledge Discovery and Data Mining, Edmonton, Canada, July 2002.
[25]S. J. Yen and A. L. P. Chen "An Efficient Approach to Discovering Knowledge from Large Databases" International Conference on Parallel and Distributed Information Systems, pp. 8-18, 1996.
[26]S. J. Yen and A. L. P. Chen "A Graph-Based Approach for Discovering Various Types of Association Rules " IEEE Transactions on Knowledge and Data Engineering (EI, SCI), Vol. 13, No. 5, pp. 839-845, 2001.