循序樣式探勘是一種資料探勘的方法，通常是應用在找出循序資料庫中的頻繁循序樣式。這種傳統的循序資料探勘方法可以被分成二大類，分別是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.