在現實的社會中，不同的群組間在某些特質上會具有明顯的差異，譬如說在大學裡頭，學生可以區分為理工學院、文學院、管理學院三類群組，不同學院的學生彼此之間存在相當多的差異，但要確實指出所謂的不同之處，通常對我們來說是相當不容易，因此造成人們多半只能憑藉自身的主觀印象來看待這類問題，無法說出完整正確的答案。為了解決這類問題，Bay與 Pazzani提出探勘對比集的概念，藉由資料探勘中的關聯性法則模式來找尋存在於不同群組間具有的差異，這些差異就是由一群有著高度依存關係的屬性所組成的集合，也是對比集定義的由來。不過，根據Bay與 Pazzani提出的STUCCO演算法所探勘出的結果，只能提供資料所隱含的部分資訊，造成決策者不能依據完整的資訊來制訂決策，因此如何自資料去挖掘出其他潛藏的資訊，來識別不同群組間的差異，是本研究所要探究的問題。

　　本研究結合對比集的基本概念、負向關聯性的定義及多重檢定的方法，來找出不具高度依存關係的屬性所組成的集合，稱之為負向對比集，這些負向對比集可以提供決策者一些額外的訊息。整個探勘負向對比集演算法的建置過程中，遭遇不少問題，包括改善著名的Apriori演算法在計算各種屬性組合支持度的效率、透過機率論相關基本概念解決各個負向關係組合的支持度計算，非一昧採用掃瞄資料檔的低效率方式來完成；另外還發現一項重要的性質，幫助我們在喜好度篩選步驟能更為簡化；最後再利用Holm所提出的方法修正STUCCO在多重檢定針對個別檢定的型一誤差設定，以避免檢定力不足的問題。

摘要 I
誌謝 II
目錄 III
表目錄 V
圖目錄 VI
第一章 緒論 1
1.1 簡介 1
1.2 研究背景與動機 3
1.3 研究目的 4
1.4 研究的步驟與流程 5

第二章 相關文獻之探討 7

2.1 關聯性模式 7

2.1.1 關聯性法則 7
2.1.2 負向關聯性法則 9

2.2 探勘對比集 9

2.2.1 問題定義 10
2.2.2 STUCCO演算 10

2.3 正向對比集的選取方法 12

2.4 多階層關聯性法則 13

第三章 研究方法 15

3.1 搜尋樹樹狀架構 16

3.2 以負向關聯性定義篩選候選負向對比集 18

3.3負向對比集在不同搜尋樹架構下的比較 25

3.4 卡方獨立性檢定與型一誤差的訂定 32

3.5 演算法流程 34

3.6 範例說明 35

第四章 實證研究 41

4.1人工產生資料的演算法流程驗證 41

4.2保險交易資料實證 46

第五章 結論與建議 54


參考文獻 56

中文

張洲期 (2000),“應用資料挖掘技術於產品替代性及互補性之研究”，中正大學資訊管理學系碩士班碩士論文。

彭文正譯 (2001), 資料採礦：顧客關係管理暨電子行銷之應用，臺北市/數博網資訊出版。麥可.斐瑞 (Michael J. A. Berry), 戈登.林諾夫 (Gordon S. Linoff) 原著。

英文

Agrawal, R., Imielinski, T., and Swami, A. (1993), Mining Association Rules Between Sets of Items in Large Databases, Proceedings of the ACM SIGMOD Conference on Management of Data, 207-216.

Agrawal, R. and Srikant, R. (1994), Fast Algorithms for Mining Association Rules, Proceedings of International Conference on Very Large Data Bases, 487-499.

Bay, S. D. and Pazzani, M. J. (1999), Detecting Change in Categorical Data: Mining Contrast Sets, Proceedings of the fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 302 – 306.

Brin, S., Motwani, R., and Silverstein C. (1997), Beyond Market Baskets:Generalizing Association Rules to Correlations, Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, 265-276.

Delgado, M., Sánchez, D., Martín-Bautista, M. J., and Vila, M. (2001), Mining Association Rules with Improved Semantics in Medical Databases, Artificial Intelligence in Medicine, 21:241-245.

Han, J. and Fu, Y. (1995), Discovery of Multiple-level Association Rules from Large Databases, Proceedings of the Very Large Data Bases Conference, 420-431.

Han, J., Pei, J., and Yin, Y. (2000), Mining Frequent Patterns without Candidate Generation, Proceedings of the ACM SIGMOD International Conference on Management of Data, 1-12.

Han, J., Koperski, K., and Stefanovic, N. (1997), GeoMiner: A System Prototype for Spatial Data Mining, Proceedings of the ACM-SIGMOD International Conference on Management, 553-556.

Holm, S. (1979), A Simple Sequentially Rejective Multiple Test Procedure, Scandinavian Journal of Statistics, 6: 65 -70.

Liu, H., Lu, H., Feng, L., and Hussain, F. (1999), Efficient Search of Reliable Exceptions, Proceedings of The Third Pacific Asia Conference on Knowledge Discovery and Data Mining, 194-204.

Piatetsky-Shapiro, G. (1991), Discovery, Analysis, and Presentation of Strong Rules, Knowledge Discovery in Databases, Menlo Park,CA:AAAI Press, 229-248.

Pramudiono, I., Shintani, T., Takahashi, K., and Kitsuregawa, M. (2002), User Behavior Analysis of Location Aware Search Engine, Mobile Data Management, January 08 - 11: 139-145.

Quinlan, J.R. (1993), C4.5: Programs for Machine Learning, Morgan Kaufmann, San Mateo, CA.

Savasere, A., Omiecinski, E., and Navathe, S. (1998), Mining for Strong Negative Associations in a Large Database of Customer Transactions, Proceedings of the International Conference on Data Engineering, 494-502.

Shaffer, J.P. (1995), Multiple Hypothesis Testing, Annual Review Psychology, 46:561-584.

Webb, G..I. (2000), Efficient Search for Association Rules, Proceedings of International Conference on Knowledge Discovery and Data Mining, 99-107.

Webb, G. I., Butler, S., and Newlands, D. (2003), On Detecting Differences Between Groups, citeseer.nj.nec.com/576632.html.

Witten, I.H. and Frank, E. (2000), Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations, Morgan Kaufmann, San Francisco.

Zhang, C. and Zhang, S. (2002), Association Rule Mining: Models and Algorithms, Springer-Verlag, Berlin.