關聯規則(Association Rule) 可幫助企業更了解客戶的消費行為，更精準地擬定各種行銷策略。頻繁型樣探勘(Frequent pattern mining)是產生關聯規則最重要也是最基本的工作，相對地，頻繁型樣探勘效能的好壞，將直接或間接地影響資料探勘(Data Mining)的工作。
頻繁型樣樹法(Frequent pattern tree)與頻繁型樣串列法(Frequent pattern list)皆是屬於不需要先產生候選人亦可完成頻繁型樣探勘的方法，可有效地改進Apriori演算法將花費大量的時間、記憶體空間在產生候選人，及重覆多次讀取交易資料庫以進行頻繁型樣確認工作的兩個瓶頸；在本論文中將深入探討頻繁型樣樹法與頻繁型樣串列法如何改進Apriori演算法，以及兩種方法的儲存空間需求狀況。
本論文提出以儲存交易記錄型樣(Transaction pattern)取代儲存交易記錄的方式，改善頻繁型樣串列法儲存交易資料庫的空間需求，對於緊密資料庫而言，可以大幅節省儲存空間且大幅提昇執行效能；對於較中型以上稀疏資料庫亦因為儲存空間需求較少，可有不錯的執行效能；對空間需求不高的小型資料庫而言，節省儲存空間對執行效能助益不大。

第一章 緒論 1
1.1 前言 1
1.2 關聯規則探勘 1
1.3 研究動機 2
第二章 頻繁型樣探勘與Apriori演算法 5
2.1 頻繁型樣探勘 5
2.2 基本定義 6
2.3 Apriori演算法 7
第三章 頻繁型樣樹法 12
3.1 頻繁型樣樹法的設計理念 13
3.2 頻繁型樣樹的資料結構 14
3.3 頻繁型樣樹的建構 15
3.4 頻繁型樣樹法的特性 21
3.5 頻繁型樣探勘 23
第四章 頻繁型樣串列法 28
4.1 頻繁型樣串列法的設計理念 28
4.2 頻繁型樣串列的資料結構 30
4.3 頻繁型樣串列的建構 31
4.4 頻繁型樣串列法的特性 34
4.5 頻繁型樣探勘 37
第五章 分析比較 44
5.1 測試資料庫 44
5.2 頻繁型樣樹的空間需求探討 46
5.3 頻繁型樣串列的空間需求探討 52
5.4 遞迴呼叫次數比較 55
第六章 頻繁型樣串列之交易記錄型樣 60
6.1 交易記錄型樣的設計理念 60
6.2 儲存空間與執行效能探討 61
第七章 結論與未來工作 68
參考文獻 70

[1]R. Agrawal and R. Srikant, ‘Fast Algorithms for Mining Association Rules in Large Databases’ Proc. of the 20th Int’l Conference on Very large Databases, pp.487-499, Santiago, Chile, Sep 1994
[2]R. Agrawal and R. Srikant, ‘Mining Sequential Patterns’ Proc. of the Int''l Conference on Data Engineering (ICDE), pp 3-14, Taipei, Taiwan, March 1995.
[3]J. Han and M. Kamber, ‘Data Mining Concepts and Techniques’ Morgan Kaufmann Publisher, 2000
[4]J. Han, J. Pei, and Y. Yin, ‘Mining Frequent Patterns without Candidate Generation’ Proc. of ACM SIGMOD, pp.1-12, Dallas, TX, May 2000
[5]Jian Pei, Jiawei Han, Runying Mao, ‘CLOSET: An Efficient Algorithm for Mining Frequent Closed Itemsets’ Data Mining and Knowledge Discovery, 2000
[6]M. Kamber, J. Han, and J. Y. Chiang, ‘Metarule-Guided Mining of Multi-Dimensional Association Rules Using Data Cubes’ Proc of Int’l Conference on Knowledge Discovery and Data Mining, pp.207-210, Newport Beach, CA, Aug 1997.
[7]J. Pei, J. Han, H. Pinto, Q. Chen, U. Dayal, and M. Hsu, ‘PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth’ Proc. of 2001 Int’l Conference on Data Engineering (ICDE''01), Heidelberg, Germany, April 2001
[8]J. Pei, and J. Han, ‘Can we push more constraints into frequent pattern mining? ’ Proceedings of international conference on Knowledge discovery and data mining, pp350-354, Boston, MA, USA. ACM, 2000
[9]Fan-Chen Tseng and Ching-Chi Hsu, ‘Creating Frequent Patterns with the Frequent Pattern List’ Proc of Asia Pacific Conference of Data Mining and Knowledge Discovery, pp.376-386, Hong Kong, 2001
[10]Fan-Chen Tseng, Ching-Chi Hsu, H. Chen, ‘Mining Frequent Closed Itemsets with the Frequent Pattern List’ IEEE International Conference on Data Mining (ICDM’01), Hong Kong, 2001
[11]Z. Zheng, R. Kohavi, and L. Mason, ‘Real World Performance of Association Rule Algorithms’ In proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, California, August 2001