臺灣博碩士論文加值系統

本論文針對交易資料庫提出一個容錯常見項目集之有效率探勘方法，稱為FFT-Mine(Fast Fault-Tolerant Pattern Mining)演算法。本方法以出現位元序列表示法來儲存交易資料，並將此表示法擴展成容錯出現位元序列來表示一個容錯資料項集合在資料庫中出現的情形。FFT-Mine演算法以深先搜尋的方式產生候選項目集，可系統化地算出代表候選項目集出現情況的容錯出現位元序列，並由序列運算結果快速判別出一個候選項目集是否為一個容錯常見項目集。整個探勘過程僅需掃描資料庫一次，可以大量節省讀取資料所需時間。由實驗結果顯示此方法較之前已提出的容錯常見項目集探勘演算法FT-Apriori及FPT-Mine有更好的執行效率。

In this thesis, an algorithm, called FFT-Mine (Fast Fault—Tolerant Frequent Itemsets Mining), is proposed for mining fault-tolerant frequent itemsets in transaction databases efficiently. In this approach, information in transaction data is represented in the form of appearing bit sequences. By extending bit sequences representation, fault—tolerant appearing bit sequences are designed to represent the distribution that the candidate itemsets contained in transaction records with fault-tolerance. FFT-Mine algorithm applies pattern growth method to construct candidate itemsets. The fault-tolerant appearing bit sequences of candidate itemsets are obtained systematically, and the algorithm decides whether a candidate itemset is a fault-tolerant frequent itemsets quickly by performing vector operations on bit sequences. The whole mining process needs scanning database only once, such that much cost for reading data repeatedly is reduced. The experimental results show that FFT-Mine algorithm has better performance on execution time than FT-Apriori and FTP-Mine algorithms proposed previously.

附表目錄 .......................................................Ⅰ
附圖目錄 .......................................................Ⅱ
第一章 緖論 ...................................................1
1.1 研究動機 .................................................1
1.2 相關文獻探討 .............................................3
1.3 論文方法 .................................................7
1.4 論文架構 .................................................7
第二章 問題定義與相關研究 ............................8
2.1 問題描述 .................................................8
2.2 名詞定義.................................................10
第三章 以位元序列為基礎之常見容錯項目集探勘.12
3.1出現位元序列 .............................................12
3.2 容錯出現位元序列 .........................................17
3.3 項目集容錯出現位元序列產生法..............................19
3.4 FFT-Mine演算法............................................27
第四章 實驗結果...........................................45
4.1 交易資料產生方式 .........................................45
4.2 實驗評估..................................................46
4.3 實驗結果總結 .............................................56
第五章 結論 ................................................57
參考文獻.......................................................58

[1] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” in Proc. of Int. Conf. on Very Large Data Bases, 1994.
[2] J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” in Proc. of ACM-SIGMOD Int. Conf. on Management of Data, 2000.
[3] J. Pei, J. Han, H. Lu, S. Nishio, S. Tang, and D. Yang, “H-Mine: Hyper-structure Mining of Frequent Patterns in Large Databases,” in Proc. of IEEE Int. Conf. on Data Mining (ICDM'01), 2001.
[4] J. Han and J. Pei, “Pattern Growth Methods for Sequential Pattern Mining: Principles and Extensions,” in Proc. of ACM-SIGKDD Int. Conf. on Temporal Data Mining, 2001.
[5] J. Pei, A.K.H. Tung, and J. Han, “Fault-Tolerant Frequent Pattern Mining: Problems and Challenges,” in Proc. of ACM-SIGMOD Int. Workshop on Research Issues on Data Mining and Knowledge Discovery (DMKD'01), 2001.
[6] J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal, and M.-C. Hsu, “PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth,” in Proc. Int. Conf. on Data Engineering (ICDE'01), 2001.
[7] K. Wang, L. Tang, J. Han, J. Liu, “Top down FP-Growth for Association Rule Mining,” in Proc. of the 6th Pacific Area Conference on Knowledge Discovery and Data Mining (PAKDD-2002).
[8] S.-S. Wang and S.-Y. Lee, “Mining Fault-Tolerant Frequent Patterns In Large Database,” in Proc. of Workshop on Software Engineering and Database Systems, International Computer Symposium, Taiwan, 2002.
[9] M.-S. Chen, J. Han, P. Yu, “Data Mining: An Overview from Database Perspective,” IEEE Transactions on Knowledge and Data Engineering, 8(6): 866-883, 1996.
[10] H. Pinto, J. Han, J. Pei, K. Wang, Q. Chen, and U. Dayal, “Multi-Dimensional Sequential Pattern Mining,” in Proc. of ACM Int. Conf. on Information and Knowledge Management, 2001.
[11] M. Garofalakis, R. Rastogi, K. Shim, “SPIRIT: Sequential Pattern Mining with Regular Expression Constraints,” in Proc. of Int. Conf. on Very Large Data Bases, 1999.
[12] M. J. Zaki, “Generating Non-Redundant Association Rules,” in Proc. of ACM-SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, 2000.
[13] J. Pei, J. Han, and R. Mao, “CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets,” in Proc. of ACM-SIGMOD Int. Workshop on Data Mining and Knowledge Discovery, 2000.