臺灣博碩士論文加值系統

本論文主要內容有兩個部分，第一部分我們設計一個新的、更有效率的演算法來採掘資料庫中具有多層次關係時間週期性質的calendar-based association rules。不同於一般使用apriori-like的方法，我們的方法利用最多掃瞄資料庫兩次的架構，可避免多次掃瞄資料庫，以節省大量的資料庫掃瞄時間，並且利用時間週期的特性來減少掃瞄資料庫過程中所要搜尋的candidate calendar patterns數目以增進程式執行的速度。以上這兩個特點使我們的方法能夠更有效率的採掘出整個資料庫中所有具有時間週期的association rules。
在第一部分中，我們所考慮的是具有嚴格限制，必須在週期上固定時間點循環出現的calendar-based association rules，沒有考慮到異位（非同步）的情形，但是在真實世界所收集到的資料中，很可能具有非同步週期出現的規則存在，而這些規則可能是有用的。因此，我們在論文的第二部份透過membership function來定義所要找尋的非同步週期fuzzy calendar pattern，並進一步搜尋出資料庫中符合fuzzy calendar pattern的association rules，以得到fuzzy periodical association rules。
由實驗結果得知，我們的方法能更有效率的從資料庫中挖掘出calendar-based及具有非同步週期的fuzzy periodical association rules。

There are two main contributions in the thesis . Firstly, we design a novel and efficient algorithm for mining calendar-based association rules which have multilevel time granularities in temporal databases. Unlike apriori-like approaches , our method scans the database twice at most. By avoiding multiple scans over the database , our method can reduce the database scanning time.
Secondly, we use membership functions to construct fuzzy calendar patterns which represent asynchronous periods. With the use of fuzzy calendar patterns, we can discover fuzzy periodical association rules which are association rules occurring in asynchronous periods.
Experimental results have shown that our method is more efficient than others, and we can find fuzzy periodical association rules satisfactorily.

摘要......................................................i
Abstract.................................................ii
目錄....................................................iii
圖表目錄.................................................iv

第一章、論文內容簡介.......................................1

第二章、Mining calendar-based periodical association rules ..3
1.Introduction....................................3
2.Problem definition..............................7
2.1 Association rule............................7
2.2 Calendar-based pattern......................9
2.3 Calendar-based periodical association rules 14
3.Algorithms.....................................17
3.1 Temporal apriori...........................17
3.2 Our method.................................21

第三章、Mining fuzzy periodical association rules...........28
1. Introduction...................................28
2. Problem definition..............................29
2.1 Fuzzy calendar pattern......................29
2.2 Fuzzy periodical association rule............30
3. Algorithm......................................36

第四章、Experiments.......................................38
Experiment 1.....................................39
Experiment 2.....................................41
Experiment 3.....................................44
Experiment 4.....................................46

第五章、Conclusion........................................52

參考文獻.................................................54

[1]R. Agrawal, T. Imielinski, A. N. Swami, “Mining association rules between sets of items in large data bases”, in : Proceedings of the 1993 ACM-SIGMOD International Conference on Management of Data, pages 207-216, Washington , DC, USA, May 1993.
[2]R. Agrawal, R. Srikant, “Fast algorithm for mining association rules in large databases”, in : Proceedings of the 20th International Conference on Very Large Data Bases, pages 487-499, Santiago, Chile, September 1994.
[3]R. Agrawal, J. C. Shafer, “Parallel mining of association rules”, IEEE Transactions on Knowledge and Data Engineering ,Vol. 8, NO. 6,pages 962-969 , December 1996.
[4] R. Agrawal, R. Srikant, “Mining sequential patterns”, in: Proceedings of the 11th International Conference on Data Engineering, pages 3-14, Taipei, Taiwan, March 1995.
[5]B. Özden, S. Ramaswamy, A. Sillberschatz, “Cyclic association rules”, in : Proceedings of the 14th International Conference on Data Engineering, pages 412-421, Orlando, Florida, USA , February 1998.
[6]S. Ramaswamy, S. Mahajan, A. Sillberschatz, “On the discovery of interesting patterns in association rules”, in : Proceedings of the 1998 International Conference on Very Large Data Base, pages 368-379, New York, USA, August 1998.
[7]Y. Li, P. Ning, X. S. Wang, S. Jajodia, “Discovering calendar-based temporal association rules”, Data and Knowledge Engineering , Vol. 44, NO. 2, pages 193-218, 2003.
[8]J. S. Park, M. -S. Chen, P. S. Yu, “Using a hash-based method with transaction trimming for mining association rules”, IEEE Transactions on Knowledge and Data Engineering, Vol. 9, NO. 5, pages 813-825, September 1997.
[9]C. -H. Lee, C. -R. Lin, M. -S. Chen, “Sliding-window filtering : an efficient algorithm for incremental mining”, in : Proceedings of the ACM 10th International Conference on Information and Knowledge Management(CIKM01), pages 263-270, Atlanta, Georgia, USA, October
2001.
[10] J. Han, J. Pei, Y. Yin, “Mining frequent patterns without candidate generation”, in: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Vol.29, NO. 2, pages 1-12, Dallas, Texas, USA, May 2000.
[11]J. Han, G. Dong, Y. Yin, “Efficient mining of partial periodic patterns in time series database”, in: Proceedings of the 15th International Conference on Data Engineering, pages 106-115, Sydney, Australia, March 1999.
[12]J. M. Ale, G. H. Rossi, “An approach to discovering temporal association rules”, in: Proceedings of the 2000 ACM Symposium on Applied Computing, pages 294-300, Como, Italy, March 2000.
[13] J. Ayres , J. Flannick , J. Gehrke , T. Yiu, “Sequential Pattern mining using a bitmap representation”, in : Proceedings of the 8th ACM SIGKDD international conference on Knowledge Discovery and Data mining, pages 529-534, Edmonton, Alberta, Canada, July 2002.
[14]G. Zimbrão, J. M. de Souza, V. T. de Almeida, W. A. da Silva, “An algorithm to discover calendar-based temporal association rules with item''s lifespan restriction”, in: Proceedings of the Eight ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - 2nd Workshop on Temporal Data Mining, Vol.8, pages 701–706, Edmonton, Alberta, Canada, July 2002.
[15]J. Yen, R. Langari, Fuzzy logic: intelligence, control, and information, Prentice-Hall, Inc. Upper Saddle River, New Jersey , 1999.
[16]R. Chandra, A. Segev, M. Stonebraker, “Implementing calendars and temporal rules in next generation database”, in : Proceeding of 10th International Conference on Data Engineering, pages 264-273, Houston, Texas, February 1994.
[17] W.-J. Lee, and S.-J. Lee, “Constructing Fuzzy Calendars for Mining Temporal Rules”, in: Proceedings of the 8th Conference on Artificial Intelligence and Applications, pages 147-152, December 2003.
[18]C. M. Kuok, A. Fu, M. H. Wong, “Mining fuzzy association rules”, in: Proceedings of the sixth international conference on Information and Knowledge Management, pages 209-215, Las Vegas, Nevada, United States, 1997.