淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0706200522161100
中文論文名稱 CHSPM:一個完整的混合循序樣式探勘演算法
英文論文名稱 CHSPM: A complete hybrid sequential patterns mining algorithm
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 93
學期 2
出版年 94
研究生中文姓名 原孝任
研究生英文姓名 Hsiau-Ren Yuan
學號 691520307
學位類別 碩士
語文別 中文
口試日期 2005-05-21
論文頁數 46頁
口試委員 指導教授-周清江
委員-陳安斌
委員-陸承志
委員-張昭憲
中文關鍵字 循序樣式  資料探勘  樣式成長 
英文關鍵字 sequential pattern  data mining  pattern-growth 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 現有循序樣式探勘的研究依照樣式中相連的項目是否必須在交易紀錄中緊密相連可粗略的分為以下三類,第一類為找出連續循序樣式;第二類為找出非連續循序樣式;第三類為找出混合循序樣式。過去混合循序樣式探勘的演算法都以Apriori為基礎,但這些方法探勘出的結果並不完整,所以我們針對混合循序樣式探勘,以樣式成長(pattern-growth)方法為基礎,提出一個新的演算法CHSPM(A Complete Hybrid Sequential Patterns Mining Algorithm),以窮舉法來找出完整之混合循序樣式。
CHSPM演算法有以下四個步驟,分別為:1.產生增補一階頻繁樣式;2. 縮減資料庫;3. 分割資料庫,建立投影資料庫;4. 探勘投影資料庫,建立子投影資料庫,直到找出所有的混合循序樣式。
為了驗證CHSPM的探勘結果,我們使用10萬至30萬筆的模擬資料來進行實驗,並與過去探勘混合循序樣式效率最佳的GFP2 演算法比較。實驗結果顯示,雖然CHSPM在效能上不如GFP2,但可以探勘出完整的混合循序樣式。
英文摘要 Based on whether consecutive items in sequential patterns should also be consecutive in the transactions, existing researches about sequential pattern mining could be classified into the following three categories: The first is to find continuous patterns; the second is to find discontinuous patterns; the third is to find hybrid patterns that combine both continuous patterns and discontinuous patterns. Previous hybrid sequential pattern mining algorithms were all based on the Apriori algorithm, but we discovered that their mining results are incomplete. Thus, based on the pattern-growth method, we propose a new algorithm (CHSPM) to find complete hybrid sequential patterns.
The four steps of CHSPM are as follows: 1. Build the supplemented frequent-1-sequence item set; 2. Reduce the database by erasing unimportant items from the transactions. 3. Partition the database, and build projected databases. 4. Recursively mine the projected databases and build sub-projected databases until all hybrid sequential patterns are found.
Finally, we use synthetic databases of 100,000 to 300,000 records to test our algorithm, and to compare our results with those of GFP2, the most efficient algorithm in hybrid sequential pattern mining up to now. The result shows that even though CHSPM is slower than GFP2, it can find out complete hybrid sequential patterns.
論文目次 第1章 緒論 1
1.1 研究動機 1
1.2 研究目的 4
1.3 論文架構 4
第2章 文獻探討 6
2.1 候選樣式產生與測試方法 6
2.2 樣式成長方法 11
第3章 CHSPM演算法 14
3.1 掃瞄資料庫,產生增補一階頻繁樣式 17
3.2 縮減資料庫 19
3.3 分割資料庫,建立一階頻繁樣式投影資料庫 20
3.4 探勘投影資料庫,建立子投影資料庫 23
第4章 完整性證明 31
第5章 實驗 33
5.1 產生交易資料庫 33
5.2 實驗數據與討論 34
第6章 結論 42
參考文獻 44
圖目錄
圖1. GFP2中的候選樹 10
圖2. GFP2中的補償串列 10
圖3. 應用Hash Table 使二階項目集縮減 11
圖4. CHSPM演算法 18
圖5. CHSPM演算法流程圖 18
圖6. 建立增補一階頻繁樣式投影資料庫 19
圖7. 根據表9建構的投影資料庫 23
圖8. CHSPM的Traverse_and_Count函數 26
圖9. CHSPM的getFrequentItem函數 29
圖10. CHSPM的Build_ProjectedDB函數 30
圖11 執行時間與交易筆數的關係圖 40
圖12 記憶體用量與交易筆數的關係圖 40


表目錄
表1. 範例資料庫 7
表2. Apriori-based演算法探勘表1資料庫的過程pass1 7
表3. Apriori-based演算法探勘表1資料庫的過程pass2 7
表4. Apriori-based演算法探勘表1資料庫的過程pass3 7
表5. 根據表1轉換後各項目出現的位置 9
表6. 根據表1建置的投影資料庫以及其循序樣式 13
表7. 範例資料庫2 22
表8. 增補一階頻繁樣式 22
表9. 縮減後資料庫 22
表10. -投影資料庫 27
表11. -投影資料庫中的增補頻繁項目 28
表12. -投影資料庫 28
表13. -投影資料庫中每個項目的支持度計算 28
表14. -投影資料庫中,交易id=5中的項目計算過程 28
表15. 產生模擬資料庫的參數 34
表16. GFP2、CHSPM探勘樣式數比較-1(平均頻繁項目長度2,最小支持度0.015) 35
表17. GFP2、CHSPM探勘樣式數比較-2(平均頻繁項目長度4,最小支持度0.015) 36
表18.CHSPM各階段執行時間比較表 36
表19. CHSPM探勘時樣式較GFP2多找到的部分 36
表20. GFP2探勘時各階段的候選樣式表 37
表21. 樣式<9337>與<8413>在交易中重複出現的交易(資料庫為T15I2D10K) 39
參考文獻 [1] R. Agrawal, T. Imielinski and A. Swami, “Mining association rules between sets of items in large databases,” Proceedings of the 1993 ACM SIGMOD international conference. Management of Data, 1993, pp. 207-216.
[2] R. Agrawal and R. Srikant, “Mining sequential patterns: Generalizations and performance improvements,” Proceedings of the 5th International Conference on Extending Database Technology, 1996, pp. 3-17.
[3] R. Agrawal and R. Srikant, “Mining sequential patterns,” Proceedings of the 11th International Conference on Data Engineering, Taipei, Taiwan, 1995, pp.3-14.
[4] R. Agrawal and R. Srikant, “Fast algorithm for mining association rules,” Proceedings of the 20th International Conference on VLDB, Santiago, 1994, pp.487-499.
[5] M. J. A. Berry and G. S. Linoff, Data Mining Techniques: For Marketing, Sales, and Customer Relationship Management, 2nd Edition, New York: John Wiley & Sons, 2004.
[6] Y. L. Chen, S. S. Chen, and P. Y. Hsu, “Mining hybrid sequential patterns and sequential rules,” Information Systems, 2002, Vol. 27, Issue 5, pp.345-362.
[7] U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusany, Advances in Knowledge Discovery and Data Mining, Cambridge: The AAAI Press/The MIT Press, 1996.
[8] Han, Jiawei and Micheline Kamber, Data Mining: Concepts and Techniques, New York: John Wiley & Son, 2001.
[9] J. Han, J. Pei, B. Mortazavi-Asl and H. Zhu, “Mining access pattern efficiently from web logs,” Proceedings of the 2000 Pacific-Asia Conference on Knowledge Discovery and Data Mining, Tokyo, 2000, pp.396-407.
[10] J. Han, J. Pei, B. Mortazavi-Asl, Q. Chen, U. Dayal, and M-C. Hsu, “Freespan: Frequent pattern-projected sequential pattern mining,” Proceedings of the 6th ACM SIGKDD international conference on Knowledge discovery and data mining, 2000, pp.355-359.
[11] J. W. Han, J. Pei and Y. W. Yin, “Mining frequent patterns without candidate generation,” Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 2000, pp.1-12.
[12] J. Klema, L. Novakova, F. Karel and O. Stepankova, “Trend analysis in stulong data,” Proceedings of the Discovery Challenge 2004 - A Collaborative Effort in Knowledge Discovery from Databases, Prague, 2004, pp.56-67.
[13] L. Kaufman and P. J. Rousseeuw, Finding Groups in Data: An Introduction toCcluster Analysis, New York: John Wiley & Sons, 1990.
[14] J. S. Park, M. Chen, and P. S. Yu, “An effective hash based algorithm for mining association rules,” Proceedings of the 1995 ACM SIGMOD International Conference Management of Data, 1995, pp.175-186.
[15] J. Pei, J. Han, B. Mortazavi-Asl, H. Pinto, Q. Chen, U. Dayal and M-C. Hsu, “PrefixSpan: Mining sequential patterns efficiently by prefix projected pattern growth,” Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany, 2001, pp.106-115.
[16] M. S. Waterman, Introduction to Computational Biology: Maps, sequences, and genomes, Boca Raton: CRC Press, 1995.
[17] S. M. Weiss and C. A. Kulikowski, Computer Systems That Learn: Classification and Prediction Methods from Statistics, Neural Nets, Machine Learning, and Expert Systems, San Mateo: Morgan Kaufmann, , 1991.
[18] M. J. Zaki, “Efficient enumeration of frequent sequences,” Proceedings of the 7th International Conference on Information and Knowledge Management (CIKM’98), 1998, pp.68-75.
[19] M. J. Zaki, “SPADE: An efficient algorithm for mining frequent sequences,” Machine Learning, 2001, Vol. 42, Issue 1-2, pp.31-60.
[20] 孫恬琳,應用資料探勘技術於汽車保險購買行為之研究,國立中正大學企業管理研究所碩士論文,2003。
[21] 陳彥文,有效率的循序樣式探勘系統,淡江大學資管所碩士論文,2004。
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2007-06-16公開。
  • 同意授權瀏覽/列印電子全文服務,於2007-06-16起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信