臺灣博碩士論文加值系統

近年來，資料串流探勘已成為熱門的研究議題，並常被用來解決日益龐大的交易資料。然而，傳統的探勘方式，大多僅用單一模式(model)尋找交易頻繁的樣式，卻容易忽略了實際存在於交易活動中的交易行為模式。譬如，冰品在白天比熱食更為暢銷，將使熱食的交易行為不易被發現並容易被忽略。本研究使用動態串流樹(Dynamic Data Stream Tree)探勘多元關聯法則。使用動態多個循環模式找尋交易的行為樣式，遠比採用單一模式演算法更具多樣化、更準確，且更符合實際存在的交易模式。

Data stream mining is a hot research topic in recent years ,which can sovle the increasingly extensive transactions data. However, the traditional mining methods merely use the single model to find out these frequent trading patterns, which may ignore the practial trading activities in trading patterns easily. For instance, if the ices are sold much better than the hot foods in the daytime, the trading patterns of the hot foods may not be find out and it may be ignored esaily. The study uses dynamic data stream tree and mining multiple association rules. Using the multiple dynamic cycle models to look for the numerous transactions patterns would be more various, accurate and correspondent with the practical transaction patterns than the single model algorithm.

中文摘要i
ABSTRACTii
誌謝iii
目錄iv
表目錄vi
圖目錄vii
一、緒論1
1.1研究背景1
1.2研究動機及目的2
1.3論文架構與內容3
二、文獻探討4
2.1資料串流探勘4
2.2視窗模式4
2.2.1標界模式4
2.2.2傾斜式視窗模式4
2.2.3滑動視窗模式4
2.3相關演算法5
2.3.1精確演算法5
2.3.2近似演算法6
2.4關聯法則6
2.4.1Apriori演算法 7
2.4.2Fp-tree演算法 9
三、動態串流樹探勘演算法12
3.1介紹12
3.2DDST演算法12
3.2.1建立樹狀結構12
3.2.2新生模型樹17
3.2.3合併模型樹20
四、實驗結果與效能分析23
4.1實驗環境與評估方式23
4.2實驗資料集23
4.3效能評估24
五、結論與未來研究方向28

中文部份
陳柏宏(2007)。針對時空性交易資料提供動態視窗關聯法則探勘之研究，國立台南大學數位學習科技研究所碩士論文，未出版。
英文部分
[1]R. Agrawal, T. Imielinski, and A. Swami, "Mining association rules between sets of items in large databases," ACM SIGMOD Record, vol. 22, pp. 207-216, 1993.
[2]R. Agrawal and R. Srikant, "Fast algorithms for mining association rules," Proc. 20th Int. Conf. Very Large Data Bases, VLDB, vol. 1215, pp. 487-499, 1994.
[3]J. H. Chang and W. S. Lee, "Finding recent frequent itemsets adaptively over online data streams," Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 487-492, 2003.
[4]J. H. Chang and W. S. Lee, "A Sliding Window Method for Finding Recently Frequent Itemsets over Online Data Streams," Journal of Information Science and Engineering, vol. 20, pp. 753-762, 2004.
[5]M. Charikar, K. Chen, and M. Farach-Colton, "Finding frequent items in data streams," Theoretical Computer Science, vol. 312, pp. 3-15, 2004.
[6]Y. Chi, H. Wang, P. S. Yu, and R. R. Muntz, "Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window," Proc. of, vol. 1401, 2004.
[7]G. Cormode and S. Muthukrishnan, "What''s hot and what''s not: tracking most frequent items dynamically," ACM Transactions on Database Systems (TODS), vol. 30, pp. 249-278, 2005.
[8]M. M. Gaber, A. Zaslavsky, and S. Krishnaswamy, "Mining data streams: a review," ACM SIGMOD Record, vol. 34, pp. 18-26, 2005.
[9]C. Giannella, J. Han, J. Pei, X. Yan, and P. S. Yu, "Mining Frequent Patterns in Data Streams at Multiple Time Granularities," Next Generation Data Mining, vol. 212, 2003.
[10]J. Han, J. Pei, Y. Yin, and R. Mao, "Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach," Data Mining and Knowledge Discovery, vol. 8, pp. 53-87, 2004.
[11]N. Jiang, "CFI-Stream: mining closed frequent itemsets in data streams," Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 592-597, 2006.
[12]N. Jiang, "Research issues in data stream association rule mining," ACM SIGMOD Record, vol. 35, pp. 14-19, 2006.
[13]C. Jin, W. Qian, C. Sha, J. X. Yu, and A. Zhou, "Dynamically maintaining frequent items over a data stream," Proceedings of the twelfth international conference on Information and knowledge management, pp. 287-294, 2003.
[14]W. Jinlong, X. Congfu, C. Weidong, and P. Yunhe, "Survey of the study on frequent pattern mining in data streams," Systems, Man and Cybernetics, 2004 IEEE International Conference on, vol. 6, 2004.
[15]R. M. Karp, S. Shenker, and C. H. Papadimitriou, "A simple algorithm for finding frequent elements in streams and bags," ACM Transactions on Database Systems (TODS), vol. 28, pp. 51-55, 2003.
[16]J. L. Koh and S. N. Shin, "An Approximate Approach for Mining Recently Frequent Itemsets from Data Streams," presented at DaWaK, 2006.
[17]C. K. S. Leung and Q. I. Khan, "DSTree: A Tree Structure for the Mining of Frequent Sets from Data Streams," Proceedings of the Sixth International Conference on Data Mining, pp. 928-932, 2006.
[18]H. F. Li, C. C. Ho, F. F. Kuo, and S. Y. Lee, "A New Algorithm for Maintaining Closed Frequent Itemsets in Data Streams by Incremental Updates," Data Mining Workshops, 2006. ICDM Workshops 2006. Sixth IEEE International Conference on, pp. 672-676, 2006.
[19]H. F. Li, S. Y. Lee, and M. K. Shan, "An efficient algorithm for mining frequent itemsets over the entire history of data streams," Proc. of the 1st Intl. Workshop on Knowledge Discovery in Data Streams, 2004.
[20]G. S. Manku and R. Motwani, "Approximate frequency counts over data streams," Proc. VLDB, vol. 2, pp. 346–357, 2002.
[21]G. Mao, X. Wu, C. Liu, X. Zhu, G. Chen, Y. Sun, and X. Liu, "Online Mining of Maximal Frequent Itemsequences from Data Streams," 2005.
[22]L. Yang and M. Sanver, "Mining Short Association Rules with One Database Scan," Int''l, 2004.
[23]J. X. Yu, Z. Chong, H. Lu, and A. Zhou, "False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams," Proceedings of the 30th ACM VLDB International Conference on Very Large Data Bases, pp. 204–215, 2004.