臺灣博碩士論文加值系統

挖掘序列型樣（mining sequential pattern）的工作主要是根據商家所記錄的交易資料庫來進行分析，以找出大部分顧客採購商品的順序行為，例如大部分顧客的購買行為可能會先買商品A，然後會再買商品B，然後會再買商品C，如此一來，商家便可以利用所分析出來的顧客行為，做一些有助於提昇利潤獲取的決策。不過，單單只有分析出大部分顧客的採購商品順序行為，可能無法提供商家足夠的資訊去做決策，所以這篇論文發展出新的演算法TGSP(time-gap sequential pattern)，找出大部分顧客採購商品的順序和其購買的間隔時間，例如若可找出大部分顧客的購買行為是買商品A後，大約隔了m到n天就會買商品B，然後再隔p到q天就會買商品C，商家便可以利用這些分析出來的資訊，去做更多的決策。譬如若有顧客甲買了A之後，商家便可以在之後的m到n天中寄一些有關商品B的資訊給甲，以吸引甲來購買商品B。

The task of mining sequential pattern is discovering the order of items which the most customer purchase according to the transaction database. An example of such a pattern is that most customers buy item A, then item B, and then item C. The store can use this pattern to make some decision to increase it’s income. But it may lose some useful informations if that only discovering the order of items which the most customers purchase without the time interval between two items. Now we develop a new algorithm TGSP (Time-Gap Sequential Pattern) to discover not only the order of items which the most customers purchasing but also the time interval between two items. An example of time-gap sequential pattern is that most customers buy item A, then buy item B after p to q days, and then buy item C after p to q days. When a customer buys item A, the store can send the customer information about item B according to the timegap sequential pattern.

第一章 導論 ……………… 1
1.1 問題說明 …………………… 2
1.2 相關工作 …………………… 7
第二章 挖掘時間間隔序列型樣 ……………… 9
2.1 找2-頻繁項目序列 …………………… 9
2.2 產生2-項目序列資料庫 …………………… 12
2.3 找出k-頻繁時間間隔序列(k³2) …………………… 15
2.4 產生(k+1)-項目序列資料庫 …………………… 25
2.5 產生時間間隔序列型樣 …………………… 28
第三章 實驗結果比較 ……………… 30
3.1 與episodes的比較 …………………… 30
3.2 實驗結果 …………………… 31
第四章 結論與未來工作 ……………… 35
參考資料 ……………… 36

[1] Rakesh Agrawal and et al.: Fast Algorithm for Mining Association Rules. In Proceedings of International Conference on Very Large Data Bases, pages 487-499, 1994.
[2] Rakesh Agrawal, Johannes Gehrke: Dimitrios Gunopulos, Prabhakar Raghavan. Automatic Subspace Clustering of High Dimensional Data for Data Minig Applications. In Proc. of the ACM SIGMOD Int''l Conference on Management of Data, Seattle, Washington, pages 94-105, June 1998.
[3] Rakesh Agrawal, and et al.: Mining Sequential Patterns. In Proceedings of International Conference on Data Engineering, pages 3-14,1995.
[4] Rakesh Agrawal, and et al.: Mining Sequential Patterns: Generalizations and Performance Improvements. In Proc. of the Fifth Int''l Conference on Extending Database Technology (EDBT), Avignon, France, Pages 3-17, March 1996.
[5] Takeshi Fukuda , Yasuhiko Morimoto , Shimichi Morishita , Takeshi Tokuyam : Data Mining with optimized two-dimensional association rules ACM Transactions on Database Systems (TODS), pages: 179 — 213 ,June 2001.
[6] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, M.-C. Hsu : FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining, Knowledge Discovery and Data Mining ,pages 355-359, 2000.
[7] Jiawei Han, Jian Pei, Yiwen Yin : Mining Frequent Patterns without Candidate Generation. ACM International Conference on Management of Data (SIGMOD), Pages 1-12, 2000.
[8] J. Han, M. Kamber ; A. K. H. Tung : Spatial Clustering Methods in Data Mining: A Survey. Geographic Data Mining and Knowledge Discovery, Taylor and Francis, 2001.
[9] C.-H. Lee, C.-R. Lin and M.-S. Chen : On Mining General Temporal Association Rules in a Publication Database，IEEE International Conference on Data Mining (ICDM) 2001.
[10] Bamshad Mobasher, Honghua Dai, Tao Luo, Miki Nakagawa : Effective personalization based on association rule discovery from web usage data. ACM Web Information and Data Management (WIDM) pages: 9-15, 2001.
[11] H. Mannila and H. Toivonen : Discovering generalized episodes using minimal occurences. In 2nd Intl. Conf. Knowledge Discovery and Data Mining, pages: 146-151, 1996.
[12] H. Mannila, H. Toivonen, and A. I. Verkamo : Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, page 259-289, 1997.
[13] H. Mannila, H. Toivonen, and A. I. Verkamo : Discovering frequent episodes in sequences. In U. M. Fayyad and R. Uthurusamy, editors, Proceedings of the First International Conference on Knowledge Discovery and Data Mining (KDD''95), pages 210 - 215, Montreal, Canada, Aug. 1995.
[14] J.-S. Park, M.-S. Chen and P. S. Yu : An Effective Hash Based Algorithm for Mining Association Rules, ACM International Conference on Management of Data (SIGMOD), pages: 175-186,1995.
[15] J. Pei, J. Han, H. Lu, S. Nishio, S. Tang, and D. Yang : H-Mine: Hyper-Structure Mining of Frequent Patterns in Large Databases. IEEE International Conference on Data Mining (ICDM), pages 441-448, 2001.
[16] Richard Relue , Xindong Wu , Hao Huang : Association Rule Mining: Efficient runtime generation of association rules. ACM, Proceedings of the tenth international conference on Information and knowledge management, Pages: 466 - 473 , October 2001.
[17] Show-Jane Yen and Chung-Wen Cho : An Efficient Approach to Discovering Sequential Patterns from Large Databases. Lecture Notes in Artificial Intelligence, Principles of Data Mining and Knowledge Discovery (PKDD), pages 685-690, 2000.
[18] Mohammed J. Zaki : Fast Mining of Sequential Patterns in Very Large Databases. Proceedings of the seventh international conference on Information and knowledge management, pages:68 — 75 ,November 1998 .
[19] Mohammed J. Zaki : Efficient enumeration of frequent sequences. ACM Proceedings of the seventh international conference on Information and knowledge management, pages: 68 - 75, November 1998.