臺灣博碩士論文加值系統

重覆樣式可以顯示資料項出現的前後關聯性，應用於資料摘要與資訊預測的依據。愈來愈多的應用之資料輸入方式形成資料流型態，傳統對靜態資料庫探勘重覆樣式的探勘方法已不適用。此外，在資料流的動態環境下，若從整個歷史資料序列中探勘出重覆樣式，則無法反應資料流中的最新趨勢。因此，本論文提出有效率偵測動態資料流中的最近重覆樣式的兩個演算法，分別稱為出現位元序列漸進探勘法及保留樣式估算法。出現位元序列漸進探勘法運用出現位元序列表示法計算出資料樣式的出現次數，並保留最大重覆樣式的出現位元序列資訊。當最近視窗序列內容改變，將運用所記錄之最大重覆樣式的出現位元序列方式資訊進行新重覆樣式之漸進探勘，以減少探勘計算成本。保留樣式估算法則保留重覆樣式、潛在候選樣式、及2-資訊樣式，並運用分段計算方式記錄資料樣式最近出現次數，架構一個可有效率存取樣式的保留樣式資料結構，由最大字首子樣式及最大字尾子樣式估算出未保留樣式的出現次數，達到近似探勘出所有資料流中最近視窗內最近重覆樣式的方式。實驗結果顯示出現位元序列漸進探勘法可有效率的正確探勘出最近視窗序列中的最近重覆樣式，而保留樣式估算法則可以更快速的近似探勘出資料流中的最近重覆樣式。

Repeating patterns represent temporal relations among data items, which could be used for data summarization and data prediction. More and more data of various applications is generated as a data stream. Accordingly, the traditional strategies for mining repeating patterns on static database are not suitable in a data stream environment. Besides, in the dynamic environment of a data stream, mining the repeating patterns from the whole history data sequence does not extract the newest trend of patterns in the data stream. For this reason, two algorithms for efficiently mining recently repeating patterns in a data stream are proposed in this thesis. One is named the appearing-bit-sequence-based incremental mining algorithm and the other one is named the basic-patterns estimating-based algorithm. The incremental mining approach applies appearing bit sequences to compute the frequencies of data patterns efficiently within the sliding window. By maintaining the appearing bit sequences of maximal repeating patterns, the newly generated recently repeating patterns are mined from the maintained information to reduce processing cost when the window slides. The estimating-based method maintains the repeating patterns, potential repeating patterns, and 2-item patterns, a partition-based scheme is used to count the frequencies of patterns. By constructing a data structure to support efficiently access of remained patterns, the frequency of an unretained pattern is estimated according to the frequencies of its maximum prefix-subpattern and suffix-subpattern. The experimental results show that the incremental mining method is an efficient way for mining recently repeating patterns correctly. And the estimating-based method provides a even more faster way to discover recently repeating patterns from a data stream approximately.

目錄
附表目錄 ii
附圖目錄 iii
第一章 緒論 1
1-1 研究動機 1
1-2 相關文獻探討 2
1-3 論文方法 6
1-4 論文架構 7
第二章 問題定義及背景知識 8
2-1 問題定義 8
2-2 位元索引結構與運算方式 11
第三章 出現位元序列漸進探勘法 14
3-1 儲存結構 14
3-2 初始視窗序列探勘 15
3-3 重覆樣式漸進探勘 16
3-4 範例說明 19
第四章 保留樣式估算法 23
4-1 最近視窗序列保留樣式 23
4-2 分段最近出現次數 24
4-3 精簡保留樣式 26
4-4 保留樣式儲存結構 28
4-5 方法論述 31
4-6 範例說明 33
第五章 演算法效率評估 39
5-1 資料產生方式 39
5-2 實驗評估 40
5-3 實驗結果總結 50
第六章 結論 51
參考文獻 52

[1] T. Calders , B. Goethals “Depth-First Non-Derivable Itemset Mining” in Proc. of 2005 SIAM Int.Conf. on Data Mining (SDM'05)
[2] J.H. Chang and W.S. Lee “Finding Recent Frequent Itemsets Adaptively over Online Data Streams” in Proc. of the 9th ACM International Conference on Knowledge Discovery and Data Ming, 2003
[3] C.C. Chang, Y.C. Li, J.S. Lee “An Efficient Algorithm for Incremental Mining of Association Rules”in Proc. of RIDE-SDMA’05
[4] D.W Cheung, J.Han, V.T. Ng, and C.Y.Wong, “Maintenance of Discovered Association Rules in Large Databases: An Incremental Update Technique,” in Proc. of the 12th International Conference on Data Engineering (ICDE’96)
[5] Y. Chi, H. Wang, P.S. Yu, R.R. Muntz“ Moment：Maintaining Closed Frequent Itemsets over a Stream Sliding Window ”, in Proc. of 2004 Int. Conf. on Data Engineering (ICDE'04)
[6] B. Goethals , J. Muhonen , H. Toivonen “Mining Non-Derivable Association Rules” in Proc. of 2005 SIAM Int.Conf. on Data Mining (SDM'05)
[7] J.L. Hsu, C.C. Liu, Arbee L.P. Chen, “Discovering Nontrivial Repeating Patterns in Music Data” in Proc. of IEEE Transactions on Multimedia , 2001
[8] J.L. Koh , W.D.C.Yu “Efficient Feature Mining in Music Objects” in Proc. of Lecture Notes in Computer Science:DEXA ’01:Database and Expert Systems Applications,pp.221-231 , Springer-Verlag , 2001
[9] J.L. Koh and Y.T. Kung “An Efficient Approach for Mining Top-K Fault-Tolerant Repeating Patterns.”in Proc. of Lecture Notes in Computer Science:DASFAA’06:Database Systems for Advanced Applications , Springer-Verlag , 2006
[10] H. Li, S. Lee, M.K. Shan “Online Mining (Recently) Maximal Frequent Itemsets over Data Streams” in Proc. of RIDE-SDMA’05
[11] C.H. Lin, D.Y. Chiu, Y.H. Wu, Arbee L.P. Chen “Mining Frequent Itemsets from Data Streams with a Time-Sensitive Sliding Window” in Proc. of SIAM International Conference on Data Mining 2005
[12] C.C. Liu, J.L. Hsu, and Arbee L.P. Chen ,“Efficient Theme and Non-Trivial Repeating Pattern Discovering in Music Databases,” in Proc. of the 15th International Conference on Data Engineering (ICDE’99)
[13] N.H. Liu, Y.H. Wu, Arbee L.P. Chen “An Efficient Approach to Extracting Approximate Repeating Patterns in Music Databases” in Proc. of International Conference on Database Systems for Advanced Applications (DASFAA 05)
[14] G.S. Manku and R.C. Motwani,”Approximate frequent counts over data Streams” in Proc. of the 28th International Conference on Very Large Database,Hong Kong, China Aug, 2002
[15] S. Thomas, S. Bodagala ,K.Alsabti, and S.Ranka, “An Efficient Algorithm for the Incremental Updation of Association Rules in Large Databases” in Proc. of 3rd International conference on Knowledge Discovery and Data Mining (KDD97)
[16] J. Wang and J. Han, “BIDE: Efficient Mining of Frequent Closed Sequences” in Proc. of 2004 Int. Conf. on Data Engineering (ICDE'04)