系統識別號 | U0002-1506200819303000 |
---|---|
DOI | 10.6846/TKU.2008.00374 |
論文名稱(中文) | 一個能發掘更具意義循序樣式的探勘流程 |
論文名稱(英文) | 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支持度計算說明(<ab>代表的時間間隔) 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. |
論文全文使用權限 |
如有問題,歡迎洽詢!
圖書館數位資訊組 (02)2621-5656 轉 2487 或 來信