傳統的關聯式法則，是對所有的交易進行分析，將所有交易隱含的關聯找出來，在沒有針對特定目標處理的情況下，往往落入兩種困境，一是處理的時間過長，另外則是產生的關聯法則過多。使用傳統的關聯式法則，過程中需要同時處理龐大的非特定目標，再從中取得特定目標的結果，雖然最後也能取得特定目標的關聯，事實上，決策者可能只對及時的、特定目標發生的關聯有濃厚的興趣，例如：行銷人員於新促銷檔期開始後，觀察消費者對促銷型錄產品購買的行為，以預期銷售額能否達成營業目標。資訊的時效性與準確性，在選擇處理的方式時就已經決定。因此我們提出針對特定目標，進行關聯式法則分析的方式，稱為目標關聯式法則資料探勘演算法(Goal Association Rule，簡稱GAR)。

The association rule analysis all transaction in order to find out unknown rules between items. Mining millions transactions without specific target often fail into a corner: one is taking time process, another is more than sufficient rules.Although traditional association rule eventually will obtain association of specific target after dealing with huge unwanted datum. Acturally timely association on specific targets might be most evaluated by decision makers. For example, marketing people observe customer behavior about catalog products during new promotion activity to predict sales amount reaching profit targets.Therefore, we proposed Goal Association Rule algorithm(GAR) aim at specific targets mining desired association rule.

目    錄
目錄 Ⅰ
圖目錄 III
第一章 緒論	1
1.1 研究動機	1
1.2 研究內容	2
1.3組織架構	3
第二章 背景知識	5
2.1 關聯式法則分析	5
2.2 Apriori演算法	13
2.3 DIC(Dynamic Itemset Count)演算法	17
2.4 Pincer-Search演算法	18
2.5 DLG(Direct Large itemsets Generation)演算法	20
2.6 Partition演算法	24
第三章 研究方法	27
3.1目標關聯式法則	27
3.2目標關聯式法則分析的六個階段	31
第四章 實驗結果	62
4.1實驗說明	62
4.2 實驗結果	65
第五章 結論	75
參考文獻	76
英文論文	79

 
圖  目  錄

Fig 2.1一般化(分類階層)示意圖	8
Fig 2.2 support與confidence定義	11
Fig 2.3 Apriori 演算法之架構圖	14
Fig 2.4 Apriori演算法	15
Fig 2.5聯結及刪除程序	16
Fig 2.6 DLG資料庫	22
Fig 2.7 DLG中L1和Bit-Map	22
Fig 2.8 DLG有向圖	23
Fig 2.9 Partition 演算法	26
Fig 3.1 Class設定示意圖	31
Fig 3.2 Distinct count演算法	32
Fig 3.3 Distinct_count_gen運作流程圖	33
Fig 3.4目標關聯式法則支持度與信賴度定義	36
Fig 3.5目標關聯式法則符合最小支持度的交易筆數定義門檻值	37
Fig 3.6傳統關聯式法則產生不需要的候選項目集示意圖	41
Fig 3.7 Class exists exclusive(CEE)定義	43
Fig 3.8 Class exists exclusive演算法	43
Fig 3.9 Large 1-itemsets	45
Fig 3.10 Large 2-itemsets	48
Fig 3.11 Large 3-itemsets	49
Fig 3.12 Large 4-itemsets	50
Fig 3.13 Large 5-itemsets	51
Fig 3.14 Candidate Rule內所有項目集的Confidence值	52
Fig 3.15 Class exists exclusive with composite item演算法	53
Fig 3.16不達Min_Sup 的Candidate 2-itemsets合併產生複合後項	56
Fig 3.17 Candidate 2-itemsets複合後項產生複合後項關聯式法則	57
Fig 3.18 Candidate 2-itemsets產生更長長度複合後項	58
Fig 3.19所有顯著的關聯式法則	60
Fig 4.1資料筆數分布情形	62
Fig 4.2購買顧客年齡Class設定	64
Fig 4.3傳統關聯式法則產生的Candidate筆數	65
Fig 4.4目標關聯式法則只用distinct_item產生Candidate筆數	66
Fig 4.5目標關聯式法則GAR1產生的Candidate筆數	68
Fig 4.6目標關聯式法則GAR1產生的Large Item筆數	68
Fig 4.7目標關聯式法則GAR2產生的Candidate筆數	70
Fig 4.8目標關聯式法則GAR2產生的Large Item筆數	70
Fig 4.9 所有顯著的關聯式法則	71
Fig 4.10顯著的複合式後項關聯式法則	72
Fig 4.11各種關聯式法則產生候選項目集的筆數	73
Fig 4.12各種關聯式法則產生Large itemset的處理時間	74

參考文獻

[1].	R. Agrawal, T. Imielinski, A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proceedings of the 1993 ACM SIGMOD Conferencen on Management of Data, Washington D.C., pp. 207-216, May 1993.

[2].	R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, and A. I. Verkamo, “Fast Discovery of Association Rules,” Advances in Knowledge Discovery and Data Mining, U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, eds., AAAI/MIT Press, pp. 307-328, 1996.

[3].	S. Brin, R. Motwani, J. Ullman, and S. Tsur, “Dynamic Itemset Counting and Implication Rule for Market Basket Data,” Proceedings of the 1997 SIGMOD Conference on Management of Data, pp. 255-264, 1997.

[4].	J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” Proceedings of the 2000 ACM SIGMOD Conference on Management of Data, Dallas, Texas, USA, pp. 1-12, May 2000.

[5].	J. Hipp, U. Güntzer, and G. Nakhaeizadeh, “Algorithms for Association Rule Mining – A General Survey and Comparison,” SIGKDD Explorations, Vol. 2, Issue 1, pp. 58-64, 2000.

[6].	Osmar R. Zaïane and Maria-Luiza Antonie, “Classifying text documents by associating terms with text categories,” Australian Computer Science Communications ,Vol. 24 ,  Issue 2,pp. 215- 222, Jan.-Feb. 2002.

[7].	Jiawei Han & Micheline, “Data Mining Concepts and Techniques,” MORGAN KAUFMANN Publishers, ISBN 1-55860-489-8.

[8].	J. Han and Y. Fu, “Mining Multiple-level Association Rules in Large Databases,” IEEE Trans. on Knowledge and Data Eng., Vol. 11. No. 5, pp. 798-805, 1999.

[9].	A. Savasere, E. Omiecinski, S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Database,” Proc. 21th VLDB, Zurich, Switzerland, pp. 432-444, 1995. 

[10].	H. Toivonen, “Sampling large databases for association rules,” In Proc. 22nd VLDB Conference, Bombay, India, pp. 134-145,Sep. 1996.

[11].	J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” Proc. of the ACM SIGMOD Int’l Conf. on Management of Data, Dallas, Texas, USA, pp. 1-12, May 2000. 
 
[12].	J.S. Park, M.S. Chen, and P.S. Yu, “Using a Hash-Based Method with Transaction Trimming for Mining Association Rules,” IEEE Trans. on Knowledge and Data Eng., vol. 9, no. 5, pp. 813-825, Sep./Oct. 1997. 

[13].	Roberto J. Bayardo Jr., “Efficiently Mining Long Patterns from Databases,” Proc. of the ACM SIGMOD Int’l Conf. On Management of Data, Seattle, Washington, pp. 85-93, June 1998.

[14].	J. Han and Y. Fu, “Discovery of Multiple-Level Association Rules from Large Databases,” Proc. of the 21th VLDB, pp. 420-431, 1995.

[15].	J. Hipp, A. Myka, R. Wirth, and U. Guntzer, “A New Algorithm for Faster Mining of Generalized Association Rules,” Technischer Bericht des Wilhelm-Schickard-Instituts, WSI-98-4, 1998.

[16].	R. Srikant and R. Agrawal, “Mining Generalized Association Rules,” Proc. Of the 21st Int'l Conference on VLDB, Zurich,Switzerland, pp. 407-419, Sep. 1995.

[17].	Ding-An Chiang,Yi-Jen Hu and Cheng-Jung Lin,“Data Mining － Disjunctive Consequent Association Rule Research in Insurance Industry,” Taiwan Insurance Institute Journal, Taiwan.