臺灣博碩士論文加值系統

資料挖掘的模式有很多種，其中以關聯式規則的挖掘方式最常被應用。關於關聯式規則的研究，大都偏向於探討如何在大量資料中有效率地挖掘單一階層的規則，雖然有少數學者研究多階層關聯式規則的問題，但只是針對Is-A Hierarchy架構挖掘概括性的關聯式規則。在競爭的現代，我們可能需要挖掘更深入、更細緻的關聯式規則以在商場上靈活地運用，因此本研究針對一個新的問題：從組成結構(Has-A Hierarchy)中挖掘多階層關聯式規則。挖掘多階層關聯式規則的步驟首先是找尋跨越Has-A Hierarchy各層的高頻項目集，其次是根據高頻項目集找尋關聯式規則。因此在本研究中我們主要探討如何挖掘跨越在Has-A Hierarchy各階層且有意義的高頻項目集，並提出有效率的演算法來解決這個問題。
本研究提出兩個演算法：RFApiroi+ 、Degrade ，挖掘跨越在組成結構中各階層的高頻項目集，其中RFApriori+演算法是直接應用Apriori演算法，並且加以改進；Degrade演算法則是以組成結構為觀點，每次僅合併最高層的高頻項目集，並且根據Has-A Hierarchy有順序地退化求得非冗餘、非微關高頻項目集，以減少不必要項目集的產生所造成的計算量。時間複雜度方面，Degrade演算法在“合併候選項目集計算量”以及“比對累計候選項目集支持度的計算量”較RFApriori+ 演算法低，但Degrade演算法每次退化則需IO時間以及退化額外的時間耗費；在空間複雜度方面，Degrade演算法較RFApriori+演算法低。實驗結果顯示，在三組不同相關性的資料庫以及不同參數的Has-A Hierarchy資料的情形下Degrade演算法比RFApriori+演算法提高約5%-53%的效率。

第一章、簡介……………………………………………………………………… 1
第二章、相關研究……………………………………………………………….. 6
2.1 關聯式規則………………………………………………………… 6
2.2 單一階層關聯式規則之挖掘技術…………………………………… 8
2.2.1 Apriori演算法……………………………………………… 8
2.2.2 DHP演算法………………………………………………………………………………………9
2.3 多階層關聯式規則之挖掘技術………………………………………… 10
2.3.1 ML_T2L1演算法………………………………………………. 12
2.3.2 JB Tree演算法以及JT Tree演算法…………………………… 13
2.3.3 結論與比較……………………………………………………… 14
第三章、問題和方法描述………………………………………………………… 15
3.1 問題分析與定義………………………………………………………… 15
3.2 RFApriori+……………………………………………………………… 18
3.2.1 方法描述………………………………………………………… 19
3.2.2 演算法…………………………………………………………… 22
　　3.2.3 複雜度分析………………………………………………………24
3.2.3.1 時間複雜度…………………………………………… 24
3.2.3.2 空間複雜度…………………………………………… 25
3.3 Degrade………………………………………………………………… 26
3.3.1 基本構想………………………………………………………… 26
3.3.1.1 退化過程……………………………………………… 27
3.3.1.2 退化順序……………………………………………… 28
3.3.1.3 合併最高層退化候選項目集………………………… 30
3.3.1.4 提早探測不可能成為高頻項目集的候選項目集…… 31
3.3.1.5 改進掃描資料庫……………………………………… 31
3.3.2 方法描述…………………………………………………………………………………… 32
3.3.3 演算法…………………………………………………………… 34
3.3.4 複雜度分析……………………………………………………… 37
3.3.4.1 時間複雜度…………………………………………… 37
　　　3.3.4.2 空間複雜度…………………………………………… 38
3.4 演算法比較……………………………………………………………… 38
第四章、實驗及結果分析………………………………………………………… 40
4.1實驗環境與模擬資料的產生……………………………………………………………… 40
4.1.1 實驗環境……….………………………………………………… 40
4.1.2 產生測試資料庫………………………………………………… 41
4.1.3產生Has-A Hierarchy測試資料………………………………………… 42
4.2 實驗設計……………………………………………………………………………43
4.3 實驗結果與分析………………………………………………………… 44
4.3.1 實驗一結果……………………………………………………… 44
4.3.2 實驗二結果……………………………………………………… 47
4.3.3 實驗三結果……………………………………………………… 49
第五章、結論及未來工作………………………………………………………… 52
參考文獻………………………………………………………………………… 54

[AIS93] R. Agrawal, T. Imielinski, and A. Swami, “Mining Association Rules Between Sets of Items in Large Databases,” Proc. of the ACM SIGMOD Conference, 1993, pp. 207-216.
[AS94] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” Proc. of the 20th VLDB Conference, 1994, pp. 487-499.
[BC94] D. J. Berndt and J. Clifford, “Using Dynamic Time Warping to Find Patterns in Times Series,” Proc. of the KDD-94 :AAAI Workshop on Knowledge Discovery in Database, 1994, pp. 359-370.
[Berr94] J. Berry, “Database Marketing: A Poent New Tools for Selling,” Business Week, September 5, 1994, pp. 56.
[BMUT97] S. Brin, R. Motwani, J. D. Ullman, and S. Tsur, “Dynamic Itemset Counting and Implication Rules for Market Basket Data,” Proc. of the ACM SIGMOD, 1997, pp. 255-264.
[CHSVZ98] P. Cabeba, P. Hadjinian, R. Stadler, J. Verhees, and A. Zanasi, Discovering Data Mining from Concept to Implementation, New Jersey, Prentice Hall PTR, 1998.
[Che96] C. J. Chen, A Pre-Fetch Mechanism for Proxy Servers: Using Association Rules, Master Thesis, Institute of Computer Science, National Chung-Hsing University, Taiwan, 1996.
[HF95] J. Han and Y. Fu, “Discovery of Multiple-Level Association Rules from Large Databases,” Proc. of 1995 Int''l Conference on Very Large Data Bases (VLDB''95), Zürich, Switzerland, September 1995, pp. 420-431.
[HF99] J. Han and Y. Fu, “Discovery of Multiple-Level Association Rules from Large Databases,” IEEE Transactions on Knowledge and Data Engineering, 11(5), 1999, pp. 798-804.
[KR94] T. Kolarik and G. Rudorfer, “ Time Series Forecasting Using Neural Networks,” Proc. of the International Conference on APL: the Language and Its Applications, 1994, pp. 86-94.
[MSB97] S. Madan, W. K. Son, and K. E. Bollinger, “Applications of Data Mining for Power Systems,” Proc. of the Engineering Innovation: Voyage of Discovery IEEE 1997 Canadian Conference, Vol.2, 1997, pp. 403-406.
[MLW92] B. Masand, G. Linoff, and D. Waltz, “Classifying News Stories Using Memory Based Reasoning,” Proc. of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1992, pp. 59-65.
[NRV96] J. Nearhos, M. Rothman, and M. Viveros, “Applying Data Mining Techniques to A Health Insurance Information System,” Proc. of the 22nd VLDB Conference, 1996, pp. 286-294.
[PCY95] J. S. Park, M. S. Chen, and P. S. Yu, “An Effective Hash Based Algorithm for Mining Association Rules,” Proc. of the ACM SIGMOD, 1995, pp. 175-186.
[Quin86] J. R. Quinlan, “Induction of Decision Trees,” In Machines Learning, Kluwer Academic Publishers, 1986, pp. 81-106.
[Rat97] T. Rathburn, “Data-Mining in the Financial Markets,” PC AI, Vol. 11, No. 4, 1997, pp. 19-20.
[RH94] T. N. Raymond and J. Han, “Efficient and Effective Clustering Methods for Spatial Data Mining,” Proc. of the 20th the VLDB Conference, Santiago, Chile, September 1994, pp. 144-155.
[SON95] A. Savasee, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining Association Rules in Large Databases,” Proc. of the 21st VLDB Conference, 1995, pp. 432-444.
[Schi96] E. Schikuta, “Grid-Clustering: An Efficient Hierarchical Clustering Method for Very Large Data Set,” Proc. of International Conference on Pattern Recognition（ICPR）, 1996, pp. 101-105.
[Toi96] H. Toivonen, “Sampling Large Databases for Association Rules,” Proc. of the 22nd VLDB Conference, 1996, pp. 134-145.
[ZPLO96] M. J. Zaki, S. Parthasarathy, W. Li, and M. Ogihara, “Evaluation of Sampling for Data Mining of Association Rules,” Proc. of the 7th International Workshop on Data Engineering, 1997, pp. 42-50.
[IBM96] “IBM Almaden-Quest Data Mining Synthetic Data Generation Code”, http://www.almaden.ibm.com/cs/quest/syndata.html, 1996.
[YW00] 武家慶, 適用於挖掘多層次聯結規則的架構, 碩士論文, 逢甲大學資訊工程研究所, 中華民國九十年六月.