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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1506200819303000
中文論文名稱 一個能發掘更具意義循序樣式的探勘流程
英文論文名稱 A Procedure to Discover More Meaningful Sequential Patterns
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 96
學期 2
出版年 97
研究生中文姓名 顏志祐
研究生英文姓名 Chih-Yu Yen
學號 695630078
學位類別 碩士
語文別 中文
口試日期 2008-05-24
論文頁數 63頁
口試委員 指導教授-徐煥智
委員-吳瑞堯
委員-翁頌舜
委員-候永昌
委員-周清江
中文關鍵字 資料探勘  循序樣式  樣式成長  信賴度 
英文關鍵字 data mining  sequential pattern  pattern- growth  confidence 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 循序樣式探勘主要是從序列資料庫中,找出與時間相關的行為樣式。過去針對循序樣式探勘所提出的方法中,多半沒有考慮到樣式的可信程度(confidence)。除此之外,探勘循序樣式雖然能夠得到事件發生的先後順序,但對於事件間的時間資訊卻非常有限。
本篇論文提出一個新的演算法E-PrefixSpan,目的是從序列資料庫中探勘頻繁且更具可信度的關聯規則。我們以PrefixSpan演算法[20]為基礎,利用樣式成長(pattern-growth)[21]的探勘方法,來發掘時間相關的循序樣式。E-PrefixSpan演算法會記錄項目間的時間間隔,並建立映射資料庫來降低資料庫的掃描次數,在產生樣式過程中會依據樣式的可信度,來減少探勘中會產生龐大的樣式數量,同時確保不會造成重要樣式資訊的遺漏。
我們與現存的循序樣式演算法比較,並說明我們演算法在其他方法上更能補足的地方。效能評估實驗顯示E-PrefixSpan能有效縮減所產生的關聯樣式,更能提供探勘結果額外的時間間隔資訊。
英文摘要 Sequential pattern mining technique is developed to determine time-related behavior in sequence databases. Most of the previous proposed methods discover frequent subsequences as patterns but do not consider the confidence issue. Besides, although the discovered sequential patterns can reveal the order of events, but the time between events is not well determined.
This dissertation presents, E-PrefixSpan, a new method for mining frequent and more confident association rules from sequential databases. The method is based on the PrefixSpan[20] algorithm. To take the advantage of the pattern-growth[21] mining approach and discover the time related sequential patterns, E-PrefixSpan records the time-intervals between items and creates projected databases to reduce the times of database scanning. Sequential pattern mining often generates a huge number of rules. To reduce the number of the correlated pattern without information loss, E-PrefixSpan applys the confidence pattern mining technique .
The proposed approach is compared to existing sequential pattern mining methods to show how they complement each other to discover association rules. Our performance study shows that E-PrefixSpan is a valuable approach to condense the correlated patterns and provide additional time-interval information for sequential pattern.
論文目次 目錄
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 5
1.3 論文架構 6
第2章 文獻探討 7
2.1 關聯式規則 7
2.2 候選樣式產生與測試方法 10
2.3 樣式成長方法 18
2.4 I-PrefixSpan演算法 20
第3章 E-PrefixSpan演算法 25
3.1 時間間隔定義 25
3.2 支持度計算 27
3.3 信賴度篩選定義 28
3.4 E-PrefixSpan演算法 31
3.5 E-PrefixSpan範例說明 34
3.6 頻繁樣式討論與比較 38
第4章 實驗 41
4.1 模擬資料的產生 41
4.2 E-PrefixSpan與PrefixSpan效能之比較 41
4.3 E-PrefixSpan與I-PrefixSpan探勘樣式比較 47
第5章 結論 53
參考文獻 55
附錄一 59
附錄二 61

圖目錄
圖2.1 Taxonomy項目階層分類例子 15
圖2.2 I-PrefixSpan時間間隔定義 21
圖3.1 E-PrefixSpan時間間隔的定義 27
圖3.2 機率觀點下的Confidence說明 29
圖3.3 E-PrefixSpan演算法 32
圖3.4 E-PrefixSpan的Get-TimeInterval函數 33
圖3.5 E-PrefixSpan的Get-TimeInterval函數 34
圖4.1 執行時間的比較 43
圖4.2 產生樣式數的比較 43
圖4.3 資料庫大小和執行時間的比較 44
圖4.4 資料庫大小和產生樣式數比較 44
圖4.5 信賴度提升對執行時間的變化 46
圖4.6 信賴度提升對產生樣式數的變化 46

表目錄
表2.1交易資料庫 9
表2.2 依顧客ID及交易時間排序的資料庫 11
表2.3 轉換後的顧客序列資料庫 11
表2.4 頻繁項目集轉換表 12
表2.5 轉換頻繁項目集後的顧客序列資料庫 12
表2.6 序列資料庫 12
表2.7 AprioriAll-長度1的頻繁序列 13
表2.8 AprioriAll-長度2的頻繁序列 13
表2.9 AprioriAll-長度3的頻繁序列 13
表2.10 AprioriAll-長度4的頻繁序列 13
表2.11 水平資料庫範例 16
表2.12 根據表2.11所建立的Id-list 17
表2.13 Id-list時序結合 17
表2.14 PrefixSpan範例資料庫 19
表2.15 Prefix映射後的資料庫及最終的循序樣式 19
表2.16 I-PrefixSpan範例資料 21
表2.17 以(a)為prefix所分割的映射資料庫 22
表2.18 以(a)為prefix,支持度計算表 23
表2.19 以(a)為prefix的2-時間區間頻繁樣式 23
表2.20 以(a)為prefix的4-時間區間頻繁樣式 23
表3.1 PrefixSpan以(a)為prefix的2-頻繁樣式 25
表3.2 E-PrefixSpan時間間隔計算規則 28
表3.3 序列資料庫-信賴度說明 30
表3.4 E-PrefixSpan範例資料庫 35
表3.5 E-PrefixSpan以L1建立的映射資料庫 36
表3.6支持度計算說明(代表的時間間隔) 37
表3.7 E-PrefixSpan以(a)為prefix的2-時間間隔頻繁樣式 37
表3.8 (a)-映射資料庫最後探勘結果 38
表3.9 頻繁樣式比較表 39
表4.1 模擬資料庫的參數 42
表4.2 頻繁樣式各階長度個數比較 45
表4.3 E-PrefixSpan與I-PrefixSpan頻繁樣式比較 49
表4.4 I-PrefixSpan頻繁樣式計算 50
表4.5 E-PrefixSpan頻繁樣式計算<529,770> 51
表4.6 E-PrefixSpan頻繁樣式計算<529,781> 51
表4.7 E-PrefixSpan頻繁樣式計算<529,991> 51
附表1:資料庫產生器可用之參數 59
附表2:C10T8S4I1.25資料庫前10筆序列 63
參考文獻 [1] 江美靜、陳彥良,有時間區間的循序挖掘,中央大學資訊管理所碩士論文,2002年。
[2] 林旻宏、許中川,探勘醫療時間序列資料,雲林科技大學資訊管理所碩士論文,2003年。
[3] 林昭妏、蔡介元,發展一個序列樣式變化之偵測模型-考慮間隔時間因素,元智大學工業工程與管理學系碩士論文,2006年。
[4] 黃盈彬、謝浩明,不連續序列資料挖掘之研究-以股市為例,中央大學資訊管理所碩士論文,2002年。
[5] 許俊傑、周清江,MIHSPM:一個多項目集的混合循序樣式探勘演算法,淡江大學資訊管理所碩士論文,2007年。
[6] Agrawal R. and Srikant R., “Fast Algorithms for Mining Association Rules in Large Databases”, Proceeding of the 20th International Conference on Very Large Data Bases, 1994, 487-499.
[7] Agrawal R. and Srikant R., “Mining sequential patterns”, Proceedings of the 11th International Conference on Data Engineering , 1995, 3-14.
[8] Agrawal R. and Srikant R., “Mining Sequential Patterns: Generalizations and Performance Improvements”, Proceedings of the 5th International Conference on Extending Database Technology, 1996, 3-17.
[9] Brin, S., Motwani, R., Ullman, J. D., & Tsur, S., “Dynamic Itemset Counting and Implication Rules for Market Basket Data”, ACM SIGMOD Conference on Management of Data, 1997, 255-264.
[10] Coker J. S. and Davies E., “Identifying Adaptor Contamination When Mining DNA Sequence Data”, Bio Techniques, Vol. 37, No.2, 2004, 194-198.
[11] Chen C.-J., “A Pre-fetch Mechanism for Proxy Servers: Using Association Rules”, Master Thesis, Institute of Computer Science, National Chung-Hsing University, 1998.
[12] Chen Y. L., Chiang M.C., Ko M.T., “Discovering time-interval sequential patterns in sequence databases”, Proceedings of the Expert Systems with Applicatons 25, 2003, 343-354.
[13] Chen Y. L., Chen S. S., and Hsu P. Y., “Mining hybrid sequential patterns and sequential rules”, Information Systems, Vol.27, No.5, 2002, 345-362.
[14] Chen Y. L., Hu Y. H., “Constraint-based sequential pattern mining: The consideration of recency and compactness”, Decision Support Systems (DSS’42), 2006, 1203-1215.
[15] Han, Jiawei and Micheline kamber, “Data Mining: Concepts and Techniques”, New York: John Wiley & Son, 2001.
[16] IBM.http://www.almaden.ibm.com./software/quest/Resources/index.shtml. Quest Data Mining Project, IBM Almaden Research Center, San Jose, CA95120.
[17] Jea K.F. and Lai L.J., “Mining Sequential Paths from XML Documents to Support XML Indexing”. Proceedings of the 7th Conference on Artificial Intelligence and Applications, 2002, 323-350.
[18] Pei J., Han J., Mortazavi-Asl B., and Zhu H., “Mining access pattern efficiently from web logs”, Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2000, 396-407.
[19] Pei J., Han J., Mortazavi-Asl B., Chen Q., Dayal U., and Hsu M., “FreeSpan: Frequent pattern-projected sequential pattern mining”, Proceedings of the sixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, 355-359.
[20] Pei J., Han J., Pinto H., Chen Q., Dayal U., and Hsu M. C., “PrefixSpan: mining sequential patterns efficiently by prefix-projected pattern growth”. Proceedings of the 17th International Conference on Data Engineering, 2001, 215-224.
[21] Pei J., Han J. and Yin Y., “Mining frequent patterns without candidate generation” In: Chen WD, Naughton J. F., Bernstein P. A., Eds. Proceeding of the 2000 ACM SIGMOD International Conference on Management of Data, 2000, 1-12.
[22] Orlando S., Perego R, Silvestri C., “A new algorithm for gap constrained sequence mining”. Symposim on Applied Computing (SAC’04), 540-547, 2004.
[23] Wu P. H., Peng W. C. and Chen M. S. “Mining Sequential Alarm Patterns in a Telecommunication Database.” Workshop on Databases in Telecommunications, Sept. 2001.
[24] Zaki M. J., “SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Proceeding of Machine Learning Journal, Special Issue on Unsupervised Learning, 2001, Vol.42 Nos. 1/2, 31-60.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2008-06-23公開。
  • 同意授權瀏覽/列印電子全文服務,於2008-06-23起公開。


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