交易型資料庫應用的領域非常廣泛，舉凡賣場交易系統與國軍裝備採購系統等，而運用傳統頻繁項目集探勘方式對資料庫探勘出的頻繁項目集，僅代表在整體資料庫中出現的頻率，並不能完全反映出項目集真正的重要性。本研究以效益探勘(Utility Mining)的方式，考慮項目的數量、價值或使用者的偏好設定，可探勘出項目集真正的重要性。
雖然資料庫的分享能給使用者帶來許多益處，但同時又擔心機敏資訊洩漏，例如國防主力武器裝備、大量採購的裝備修護零組件等，這些機敏資訊恐成為敵方攻擊或防禦的重點，因此有關隱私保護資料探勘(Privacy Preserving Data Mining, PPDM）之研究議題也逐漸熱門；此外，現實資料庫已發展為線上動態環境，探討能即時保護機敏資訊不被洩漏且使用者可立即獲得回饋資訊。
本研究首先提出三種靜態機敏項目集隱藏演算法SIHMU、SIHMW及MIHMW，改進2010年Yeh所提出的HHUIF及MSICF演算法，可降低資料變動率並減少遺失非機敏高效益項目集的副作用；此外，亦提出三種動態機敏項目集隱藏演算法ITDSI、ISIDMU與ISIDMW。實驗結果顯示，就資料變更率、非機敏高效益項目集遺失率而言，本研究提出的演算法能適用於現實的動態環境。

Transactional databases are used in a broad range of applications, such as trading systems and　military equipment procurement systems. Traditional frequent itemset mining only considers the frequency of an itemset in a database, but not fully reflecting the real importance of the itemset. On the other hand, utility mining takes into accout cost, profit, or other expressions of user preference.
Although database sharing will give users many benefits, it could lead to leakage of sensitive information, such as the main battle weapon and the major components for equipment repair in national defense procurement systems. This information explored would be used by enemy to predict our development trend and to obtain strengths and weaknesses of one’s armed forces. Therefore, privacy preserving data mining has become more important research issues in recent years. In addition, for online applications, systems must achieve high performance and should feedback information in real time.
This study develops privacy preservation algorithms for high utility itemsets mining. We first propose three static sensitive itemsets hiding algorithms SIHMU, SIHMW and MIHMW. Then, we also propose three online algorithms for sensitive itemsets hiding, namely ITDSI, ISIDMU and ISIDMW. Expermental results show that the proposed alogrithms outperform other state-of-the-art algorithms in terms of side effects generated.

誌謝 ii
摘要 iii
ABSTRACT iv
目錄 v
表目錄 vii
圖目錄 x
1.緒論 1
1.1 研究動機 1
1.2 研究目的 4
1.3 論文架構 6
2.效益探勘相關文獻探討 7
2.1 符號定義 7
2.2 效益探勘定義 8
2.3 高效益項目集探勘 10
2.4 漸增式資料庫探勘高效益項目集方法 14
2.5 機敏高效益項目集隱藏 22
2.5.1 高效益項目集隱藏定義 22
2.5.2 機敏高效益項目集隱藏副作用 23
3.機敏項目集隱藏演算法 29
3.1 機敏項目集快速隱藏方法 31
3.2 靜態資料庫機敏項目集隱藏問題定義 31
3.2.1 SIHMU架構與演算法 32
3.2.2 SIHMU範例 33
3.2.3 SIHMW架構與演算法 35
3.2.4 SIHMW範例 37
3.2.5 MIHMW架構與演算法 39
3.2.6 MIHMW範例 43
3.3動態資料庫機敏項目集隱藏問題定義 45
3.3.1 ITDSI架構與演算法 46
3.3.2 ITDSI範例 47
3.3.3 ISIDMU架構與演算法 48
3.3.4 ISIDMU範例 50
3.3.5 ISIDMW架構與演算法 51
3.3.6 ISIDMW範例 53
4.實驗設計與結果分析 55
4.1 實驗設計 55
4.2 靜態資料庫機敏項目集隱藏實驗結果分析 57
4.3 動態資料庫機敏項目集隱藏實驗結果分析 61
5.結論及未來研究方向 65
5.1 結論 65
5.2 未來研究方向 66
參考文獻 67
自傳 71

[1] Agrawal, R., Imielinski, T. and Swami, A., “Mining Association Rules between Sets of Items in Large Database,” Proceedings of the ACM SIGMOD Conference on Management of Data, Washington, D.C., USA, pp. 207-216, May, 1993.
[2] Yao, H., Hamilton, H. J. and Butz, C. J., “A foundational approach to mining itemset utilities from databases,” In Proceedings of the 4th SIAM international conference on data mining, pp. 482–486, 2004.
[3] Chan, R., Yang, Q. and Shen, Y. D., “Mining High utility Itemsets,” Proceedings of the Third IEEE International Conference on Data Mining (ICDM’03), pp.19-26, 2003.
[4] Atallah, M., Elmagarmid, A., Ibrahim, M., Bertino, E. and Verykios, V., “Disclosure limitation of sensitive rules,” CERIAS Tech Report, No. 02, 2000.
[5] 林士閔，“資料探勘技術應用於國防機敏資訊防護之研究”，國防大學理工學院資訊科學研究所碩士論文，桃園，2009。
[6] Wang, S.L., Parikh, B. and Jafari, A., “Hiding Informative Association Rule Sets,” Expert Systems with Applications, Vol. 33, pp. 316-323, August, 2007.
[7] Wang, S.L., Maskey, R., Jafari, A. and Hong, T.P., “Efficient Sanitization of Informative Association Rules,” Expert Systems with Applications, Vol. 35, pp.442-450, 2008.
[8] 張淵琮、陳善泰，“機敏關聯規則集快速完全隱藏演算法”，第十八屆資訊安全會議(CISC)論文集，花蓮，第547-560頁，2008。
[9] Wu, Y. H., Chiang, C.M. and Chen, A.L.P., “Hiding Sensitive Association Rules with Limited Side Effects,” IEEE Transactions on Knowledge and Data Engineering, Vol. 19, pp. 29-42, January, 2007.
[10] Amiri, A., “Dare to Share: Protecting Sensitive Knowledge with Data Sanitization,” Decision Support Systems, Vol. 43, pp. 181-191, February, 2007.
[11] Moustakides, G.V. and Verykios, V.S., “A Max-Min Approach for Hiding Frequent Itemsets,” Proceedings of the Sixth IEEE International Conference on Data Mining, Washington, D.C., USA, pp. 502-506, 2006.
[12] Weng, C.C., Chen, S.T. and Chang, Y.C., “Novel Algorithms for Hiding Sensitive Frequent Itemsets,” Proceedings of the eighth International Symposium on Advanced Intelligent Systems, Sokcho-City, Korea, pp. 753-757, September, 2007.
[13] Li, H. F., Huang, H. Y., Chen, Y.C., Liu, Y. J. and Lee, S. Y., “Fast and Memory Efficient Mining of High Utility Itemsets in Data Streams,” Proceedings of the Eighth IEEE International Conference on Data Mining, pp. 881-886, 2008.
[14] Ahmed, C. F., Tanbeer, S. K., Jeong, B. S. and Lee, Y. K., “Mining High Utility Patterns in Incremental Databases,” ICUIMC-09, Suwon, S. Korea, pp. 656-663, 2009.
[15] Chu, C. J., Tseng, V. S. and Liang, T., “An efficient algorithm for mining temporal high utility itemsets from data streams,” The Journal of Systems and Software , Vol.81, pp. 1105–1117, 2008.
[16] Liu, Y., Liao, W. and Choudhary, A., “A Two Phase algorithm for fast discovery of High Utility of Itemsets,” In Proceedings of the 9th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD’05), pp. 689-695, 2005.
[17] Lee, C.H., Lin, C.R. and Chen, M.S., “Sliding-window filtering: an efficient algorithm for incremental mining on a time-variant database,” International Conference on Information and Knowledge Management (CIKM01), pp. 263–270, November, 2001.
[18] Shin, S. J. and Lee, W. S., “On-line generation association rules over data streams,” Information and Software Technology , Vol. 50, pp. 569-578, 2008.
[19] Han, J., Pei, J., Yin, Y. and Mao, R., “Mining frequent patterns without candidate generation: A frequent-pattern tree approach,” Data Mining and Knowledge Discovery, Vol.8, pp. 53–87, 2004.
[20] Sun, X. and Yu, P. S., “A Border-Based Approach for Hiding Sensitive Frequent Itemsets,” Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM'05), pp. 426-433, 2005.
[21] 張淵淙，“關聯規則探勘於資訊分享環境中機敏資料隱藏之研究”，國防大學理工學院資訊科學研究所碩士論文，桃園，2008。
[22] Yeh, J. S. and Hsu, P. C., “HHUIF and MSICF: Novel algorithms for privacy preserving utility mining,” Expert Systems with Applications, Vol. 37, pp. 4779-4786, 2010.
[23] Weng, C. C., Chen, S. T. and Lo, H. C., “A Novel Algorithm for Completely Hiding Sensitive Association Rules,” Proceedings of the Eighth IEEE International Conference on Intelligent Systems Design and Applications, pp. 202-208, 2008.
[24] Ma, C. X. and Zhang, J., “DHUI: A New Algorithm For Mining High Utility Itemsets,” Proceedings of the Eighth International Conference on Machine Learning and Cybernetics, pp. 173-177, 2009.
[25] Shankar, S., Purusothaman, T. and Jayanthi, S., “Novel Algorithm for Mining High Utility Itemsets,” Proceedings of the 2008 International Conference on Computing, Communication and Networking (ICCCN 2008), pp. 1-6, 2008.
[26] Lin, C. W., Hong, T. P. and Lu, W. H., “The Pre-FUFP algorithm for incremental mining,” Expert Systems with Applications, Vol. 36, pp. 9498-9505, 2009.
[27] Woo, H. J. and Lee, W. S., “estMax: Tracing Maximal Frequent Itemsets over Online Data Streams,” Proceedings of the Seventh IEEE International Conference on Data Mining, pp. 709-714, 2007.
[28] Liu, Y. C. and Hsu, P. Y., “Toward supporting real-time mining for data residing on enterprise systems,” Expert Systems with Applications, Vol.34, pp. 877–888, 2008.
[29] Tseng, V. S., Wu, C. W., Shie, B. E. and Yu, P. S., “UP-Growth: An Efficient Algorithm for High Utility Itemset Mining,” Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 253-262, 2010.
[30] 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/datasets/
syndata.html.