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


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-0403201010530200
中文論文名稱 植基於貝氏認知網路的循序資料探勘方法
英文論文名稱 A Sequential Data Mining Method Based on Bayesian Belief Network
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 98
學期 1
出版年 99
研究生中文姓名 譚如芳
研究生英文姓名 Ju-Fang Tan
學號 696631547
學位類別 碩士
語文別 中文
口試日期 2010-01-15
論文頁數 69頁
口試委員 指導教授-徐煥智
委員-黃承龍
委員-陳穆臻
委員-周清江
中文關鍵字 資料探勘  循序樣式  貝氏認知網路  動態機率 
英文關鍵字 Data Mining  Sequential Pattern  Bayesian Belief Network  Dynamic Probability 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 循序樣式探勘是一種資料探勘的方法,通常是應用在找出循序資料庫中的頻繁循序樣式。這種傳統的循序資料探勘方法可以被分成二大類,分別是Apriori-like方法和樣式成長方法。而在這二種方法中都使用最小支持度來當做門檻值,並利用最小支持度找出資料庫中的頻繁循序樣式。一般來說,在一個循序樣式之中,每一個事件的機率值都可以提供更多的資訊以供決策者來分析和預測關聯樣式之間的行為。然而,在過去的研究中,並沒有一種技術是可以同時地在樣式挖掘的過程中也發掘出樣式的機率值。因此,為了能夠在循序樣式探勘時也能找出機率的相關資訊,我們提供一個延伸PrefixSpan演算法的方法;該方法為每一個第二階頻繁樣式考慮到機率值。根據這樣的結果,可以建構出一個有方向性的圖形,而這個圖形可以建構成一個所謂的貝氏認知網路。利用貝氏認知網路,可以估計出循序樣式中每一個事件的機率值。
英文摘要 Sequential Pattern Mining is a data mining method that is used to find frequent sequential patterns in a sequential database. The conventional sequence data mining methods can be divided into two categories: Apriori-like methods and Pattern-growth methods. Both of the methods use the minimum support value to be a threshold to discover the sequential patterns. The probability of each event in a sequential pattern can provide more information for decision maker to analyze and predict the behavior of correlated pattern. However, in the previous studies there is no technique developed to simultaneously discover the probability in the pattern mining process. Thus, to provide such information, we will extend the PrefixSpan method with considering the probability for each level 2 pattern. According to the results, a directed graph will be constructed to build a Bayesian Belief Network (BBN). Using the BBN, the probability of each event in a sequential pattern can be evaluated.
論文目次 圖目錄 V
表目錄 VI
第1章 緒論 1
1.1 研究動機與目的 1
1.2 研究方法 3
1.3 論文架構 6
第2章 文獻探討 7
2.1 循序樣式探勘方法之發展過程 7
2.2 PrefixSpan演算法 8
2.3 貝氏認知網路 12
第3章 貝氏認知網路之循序樣式探勘方法 21
3.1 模式建構 21
3.1.1 模式流程 21
3.1.2 Lv2-PrefixSpan演算法 23
3.1.3 建構貝氏認知網路 26
3.1.4 資料更新 35
3.2 建立模式 39
第4章 系統驗證 49
4.1 系統與範例說明 49
4.2 範例驗證 50
第5章 結論與未來研究 58
5.1 結論 58
5.2 未來研究 59
參考文獻 60
附錄一 模擬資料庫之操作 64
附錄二 原始交易資料 67

圖 2–1 PrefixSpan演算法 10
圖 2–2 子節點的貝氏認知網路和條件機率表 17
圖 2–3父節點的貝氏認知網路和條件機率表 18
圖 3–1貝氏認知網路之循序樣式探勘方法 22
圖 3–2 lv2-PrefixSpan演算法演算法 24
圖 3–3 局部貝氏認知網路 27
圖 3–4 建構中之貝氏認知網路 28
圖 3–5 發生迴圈之貝氏認知網路 29
圖 3–6 經過迴圈處理之貝氏認知網路 29
圖 3–7 條件機率估計演算法 33
圖 3–8 局部貝氏認知網路 34
圖 3–9新增節點之貝氏認知網路 38
圖 3–10 新增關係之貝氏認知網路 39
圖 3–11 初步網路圖 45
圖 3–12 貝氏認知網路 46
圖 4–1 初步網路圖 51
圖 4–2 貝氏認知網路圖 53


表 2–1 PrefixSpan演算法範例交易資料庫 11
表 2–2 一階頻繁樣式項目的映射資料庫 11
表 2–3 循序樣式 12
表 3–1 交易序列資料表 25
表 3–2 第一階頻繁樣式之Postfix和Complement-Postfix 26
表 3–3 第二階頻繁樣式 26
表 3–4 二階頻繁樣式序列 27
表 3–5 節點f的條件機率表 35
表 3–6 更新之交易資料庫 37
表 3–7 更新之Postfix和Complement Postfix 37
表 3–8更新之第二階頻繁樣式 38
表 3–9 交易資料庫 40
表 3–10 一階映射資料庫 41
表 3–11 頻繁項目的Postfix和Complement Postfix 42
表 3–12 建立初步網路的節點映射資料庫 44
表 3–13 路徑表 44
表 3–14 建立貝氏認知網路的節點映射資料庫 45
表 3–15節點f的條件機率表 47
表 4–1第二階頻繁樣式 50
表 4–2 節點映射資料庫 51
表 4–3 路徑表 52
表 4–4 情境一機率變動 54
表 4–5 情境二機率變動 55
表 4–6 範例三機率變動 56
表 4–7 範例四機率變動 56
表 4–8 範例五機率變動 57
參考文獻 [1]王偉如,“利用順序型樣於貝氏網路以建構血液透析臨床路徑” 國立中山大學資訊管理學系研究所碩士論文,2001
[2]Agrawal, D. and Aggarwal, C. C. “On the Design and Quantification of Privacy Preserving Data Mining Algorithms,” Proceedings of the 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,2001, pp. 247-255
[3]Agrawal, R., Imielinski, T., and Swami, A. “Mining association rules between sets of items in large databases” International Conference on Management of Data, (22:2) ,1993, pp207-216
[4]Agrawal, R. and Srikant, R. “Mining sequential patterns”, 11th International Conference on Data Engineering (ICDE'95), 1995, pp. 3-14,.
[5]Agrawal, R. and Srikant R. ”Mining Sequential Patterns: Generalizations and Performance Improvements”, Proceedings of the 5th International Conference on Extending Database Technology, 1996, pp. 3-17
[6]Cheng, J., Bell, D.A., and Liu, W. “An algorithm for Bayesian belief network construction from data”, in: Proceedings of AI & STAT'97, 1997, pp. 83–90.
[7]Heckerman, D. “A Tutorial on Learning With Networks ” Technical Report MSR-TR-95-06, Microsoft Research, Microsoft Corporation, March 1995.
[8]Heckerman, D. "Bayesian Networks for Data Mining" Data Mining and Knowledge Discovery, (1:1) , 1997, pp79-119
[9]IBM.http://www.almaden.ibm.com./software/quest/Resources/index.shtml. Quest Data Mining Project, IBM Almaden Research Center, San Jose, CA95120.
[10]Jaroszewicz, S., Scheffer, T., and Simovici, D.A. "Scalable pattern mining with Bayesian networks as background knowledge" Data Mining and Knowledge Discovery, 2008, pp. 1-45.
[11]Li, X. “Two essays on mining market basket data: Models and applications in marketing". Ph.D. diss., The George Washington University. In Dissertations & Theses: A&I 2008
[12]Lindell, Y. and Pinkas, B. “Privacy Preserving Data Mining,” Journal of Cryptology, 2000, pp. 177-206.
[13]Neapolitan, R.E., “Probabilistic reasoning in expert systems: theory and algorithms”, John Wiley & Sons, 1990.
[14]Parthasarathy, S. Zaki, M. J. Ogihara, M. and Dwarkadas, S. "Incremental and Interactive Sequence Mining", 8th International Conference on Information and Knowledge Management, 1999, pp251-258.
[15]Pearl, J., “Probabilistic reasoning in intelligent systems: networks of plausible inference”, Morgan Kaufmann, 1988.
[16]Pearl, J.,”Causality: models, reasoning and inference.” Cambridge, 2000.
[17]Pei, J., Han, J., Mao, R., 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. New York: ACM Press, 2000, pp.1-12.
[18]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, pp.355-359.
[19]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, pp. 215-224.
[20]Roiger,RJ. and Geatz,MW. "Data Mining: A tutorial-based primer" ,2003,Addison Wesley Boston
[21]Wang, C.-Y. Hong, T.-P. and Tseng, S.-S. "Maintenance of sequential patterns for record modification using Pre-large Sequences" IEEE International Conference on Data Mining, 2002, pp. 693-696.
[22]Wright, R., and Yang, Z. “Privacy-preserving Bayesian network structure computation on distributed heterogeneous data”, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, 2004, pp22-25.
[23]Yang, J., Wang, W., and Yu, P. S. “Mining surprising periodic patterns” Data Mining and Knowledge Discovery, (9:2), 2004, pp. 189-216.
[24]Zaki , M. J. ”SPADE: An Efficient Algorithm for Mining Frequent Sequences”, Proceeding of Machine Learning Journal, Special Issue on Unsupervised Learning, (42:1/2), 2001, pp.31-60.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2011-03-05公開。
  • 同意授權瀏覽/列印電子全文服務,於2010-03-05起公開。


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