臺灣博碩士論文加值系統

隨著網路科技的蓬勃發展，資訊分享與交流日漸頻繁，資料探勘技術雖能幫助人們發現資料之間的重要法則，卻也讓人們承擔敏感資訊外流的風險。近來研究除了隱藏敏感性法則，也開始探討減低或避免邊際效應，包括隱藏非敏感性法則（遺失法則）、和產生不存在的法則（錯誤法則）。本論文以少量的交易修改為目標，提出隱藏法則的方法，並保持已完成隱藏敏感性法則的狀態下，盡可能還原遺失法則。另外，我們針對隱藏過程需快速檢索交易的需求，提出有效率的索引結構。實驗驗證我們的方法能有效隱藏所有敏感性法則且最多可還原40%遺失法則，於索引結構則平均減少約85%的檢索時間。

As the prevalent development of network technology, information sharing and communication is frequent in daily life. Although data mining techniques help people find the important rules among data, people also have to take the risk of sensitive information disclosed. In addition to hiding sensitive rules, recent researches also start discussing the reduction or avoidance of unexpected side effects, including the hiding of non-sensitive rules (lost rules) and the creation of non-existent rules (false rules). This thesis aims at a small amount of transaction modifications and proposes a method of rule hiding. The method can recover lost rules and keep sensitive rules hidden. Besides, we propose an efficient index structure for a quick retrieval of transactions during the hiding process. The experiments verify that our method can hide all sensitive rules and recover at most 40% lost rules. The index structure reduces about 85% retrieval time on average.

摘 要 ............................................................................................................... I
ABSTRACT ......................................................................................................... II
誌謝 .....................................................................................................................III
目 錄 ............................................................................................................ IV
附表目錄 ............................................................................................................ VI
附圖目錄 ........................................................................................................... VII
第一章 緒論......................................................................................................... 1
第二章 相關研究與問題定義 .......................................................................... 11
2.1 相關研究 ............................................................................................. 11
2.2 問題定義 .............................................................................................12
第三章 以交易分群為基礎之法則隱藏 ..........................................................17
3.1 隱藏敏感性法則 .................................................................................17
3.2 還原遺失的法則 .................................................................................22
第四章 與樣板相關交易筆數之檢索 ..............................................................25
4.1 樣板比對 .............................................................................................25
4.2 建立質數特徵樹 .................................................................................27
第五章 實驗.......................................................................................................31
5.1 遺失法則效能評估 .............................................................................32
5.2 法則隱藏效能評估 .............................................................................35
第六章 結論.......................................................................................................38
參考文獻 .............................................................................................................40
附錄 .....................................................................................................................43



附表目錄
表格一、CSP範例 .............................................................................................. 5
表格二、樣板範例 ............................................................................................12
表格三、敏感交易之法則影響度 ....................................................................18
表格四、敏感性法則紀錄 ................................................................................19
表格五、交易檢索 ............................................................................................20
表格六、範例，敏感交易之法則影響度 ........................................................20
表格七、鎖定表格 ............................................................................................21
表格八、還原樣板範例 ....................................................................................22
表格九、隱藏法則與隱藏後交易 ....................................................................24
表格十、還原樣板表 ........................................................................................24
表格十一、法則abcd 樣板 ..........................................................................26
表格十二、法則 25 樣板 ............................................................................27
表格十三、質數交易 ........................................................................................28


附圖目錄
圖一、系統架構 16
圖二、質數特徵樹範例 ....................................................................................27
圖三、樹中加入第4筆交易 ............................................................................28
圖四、樹中加入第5筆交易 ............................................................................29
圖五、樹中加入第6筆交易 ............................................................................30
圖六、樹中加入第9筆交易 ............................................................................30
圖七、遺失法則比較 ........................................................................................32
圖八、所需時間比較 ........................................................................................33
圖九、還原遺失法則比例 ................................................................................34
圖十、還原遺失法則時間 ................................................................................34
圖十一、隱藏時間 ............................................................................................35
圖十二、遺失法則評估 ....................................................................................36
圖十三、TYPE1 檢索 ......................................................................................37
圖十四、TYPE2 檢索 ......................................................................................37
圖十五、隱藏法則演算法 ................................................................................45
圖十六、還原遺失法則演算法 ........................................................................47

[1].M. Atallah, E. Bertino, A. Elmagarmid, M. Ibrahim, and V. S. Verykios, “Disclosure limitation of sensitive rules”, In Proceedings of the 1999 IEEE Knowledge and Data Engineering Exchange Workshop (KDEX’99).
[2].R. Agrawal and R. Srikant, “Privacy-Preserving Data Mining”, Proc. of ACM SIGMOD Intl. Conf. on Management of Data, May 2000.
[3].Rakesh Agrawal, Ramakrishnan Srikant, ”Fast algorithms for mining association rules”, VLDB 1994 :487-499.
[4].A. Gkoulalas-Divanis and V. S. Verykios, “An Integer Programming Approach for Frequent Itemset Hiding”, In Proceedings of the 2006 ACM Conference on Information and Knowledge Management (CIKM 2006).
[5].Yuhoung Guo “Reconstruction-Based Association Rule Hiding”, SIGMOD2007 Ph.D. Workshop on Innovative Database Research 2007(IDAR2007).
[6].Ya-Ping Kuo, Pai-Yu Lin, and Bi-Ru Dai, “Hiding Frequent Patterns under Multiple Sensitive Thresholds”, Database and Expert Systems Applications, 19th International Conference, DEXA 2008.
[7].Nikos Mamoulis, David W. Cheung, and Wang Lian, “Similarity Search in Sets and Categorical Data Using the Signature Tree”, Proceedings of the 19th International Conference on Data Engineering (ICDE’03).
[8].S. Menon, S. Sarkar, and S. Mukherjee, “Maximizing accuracy of shared databases when concealing sensitive patterns”, Information Systems Research, 16(3):256–270, 2005.
[9].Vassilios S. Verykios, Ahmed K. Elmagarmid, Elisa Bertino and Yucel Saygin, M, “Association Rule Hiding”, IEEE Transaction on Knowledge and Data Engineering (TKDE 2004).
[10].Vassilios S. Verykios and Aris Gkoulalas-Divanis, “A Survey of Association Rule Hiding Methods for Privacy”, Privacy-Preserving Data Mining, Chapter11.
[11].Y. Saygin, V.S. Verykios, and A.K. Elmagarmid, “Privacy Preserving Association Rule Mining”, Proc. IEEE Workshop Research Issues in Data Engineering, 2002.
[12].Xingzhi Sun, Philip S. Yu, “Hiding Sensitive Frequent Itemsets by a Border-Based Approach”, Journal of Computing Science and Engineering (JCSE 2007).
[13].George V.Moustakides, Vassilios S.Verykios, “A Max-Min Approach for Hiding Frequent Itemsets”, In Workshops Proceedings of the 6th IEEE International Conference on Data Mining (ICDM 2006), pages 502-506.
[14].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(TKDE 2007).
[15].http://www.almaden.ibm.com/software/quest/Resources/index.shtml, 2003.