臺灣博碩士論文加值系統

本研究目的在利用資料分析之方法於決定隱藏馬可夫模型(Hidden Markov Model, HMM)之隱藏狀態數。雖然隱藏馬可夫模型已被廣泛應用於模型識別、語音及手寫識別、股票預測和預防性維護等領域，但僅有少數的研究專注於如何決定隱藏狀態數量。根據過去的文獻中，大多研究著重於利用赤池信息準則(Akaike Information Criteria, AIC)和貝葉斯信息準則(Bayesian Information Criteria, BIC)方法透過極大化概似估計值來決定隱藏狀態數。本研究運用資料分群方法分析隱藏馬可夫模型的原始資料，試圖透過分群方法將原始資料隱藏的結構擷取出來，以協助找出隱藏馬可夫模型之最佳隱藏狀態數量。在執行隱藏馬可夫模型後，運用多目標準則分析方法(柏拉圖最適前緣)，找出隱藏馬可夫模型之計算時間、分群指標及概似估計值的最佳組合。本實驗利用四個預測性維護資料集進行實驗，並驗證所提出的方法能夠找到隱藏狀態，也同時最佳化隱藏馬可夫模型效率的適當隱藏狀態數。

This research proposes the data analysis method for determining the number of hidden states of Hidden Markov Model (HMM). Although HMM has been widely used for pattern recognition, handwriting character recognition, stock prediction, and preventive maintenance and so on. However, there was only a few research has been conducted on the determination of the number of hidden states. Based on the literature review, Akaike Information Criteria (AIC), and Bayesian Information Criteria (BIC) were applied to search the number of hidden states by maximizing the likelihood of each model. In this research, the data clustering method is proposed to study the hidden patterns among the data which will be trained in HMM. The multiple clustering validation measures with computational time are included in the decision making of the number of hidden states. The Pareto Optimal Front is utilized to deal with multi-objective problem based on the multiple criterion. The experimental results conducted on fours datasets regarding preventive maintenance showed that the proposed method is able to find the suitable number of hidden states which also optimize the efficiency of HMM.

CONTENTS 1
LIST OF FIGURES 3
LIST OF TABLES 4
CHAPTER 1. INTRODUCTION 5
1.1. BACKGROUND 5
1.2. DIFFICULTY AND CHALLENGE 6
1.3. RESEARCH PROBLEM 7
1.4. STRUCTURE 7
CHAPTER 2. LITERATURE REVIEW 9
2.1. HMM ON INDUSTRY 9
2.2. METHODOLOGY TO CHOOSE THE STATES? 10
2.2.1. Akaike Information Criterion and Bayesian Information Criterion 10
2.2.2. Clustering Method (K-means and Hierarchical Clustering) 11
2.3. METHODOLOGY TO VERIFY THE NUMBER OF HIDDEN STATES 14
CHAPTER 3. METHODOLOGY 15
3.1. STRUCTURE OF HMM 16
3.1.1. Element of an HMM 16
3.1.2. Basic assumption of HMM 16
3.1.3. Three stages of HMM 17
3.1.4. Continuous HMM 21
3.2. COMPUTE POSSIBLE STATE NUMBER 22
3.3. VERIFY THE NUMBER OF HIDDEN STATES 24
3.3.1. Performance Measurement 24
3.3.2. Numerical Computation 25
3.3.3. Pareto Optimal Front 26
CHAPTER 4. EXPERIMENTAL RESULTS 27
4.1. EXPERIMENT 1: SPEED DATA 27
4.1.1. Introduction of speed data 27
4.1.2. Data structure 27
4.1.3. Data preprocess 28
4.1.4. Result 28
4.2. EXPERIMENT 2: TURBOFAN ENGINE DEGRADATION SIMULATION DATA (TEDS) 29
4.2.1. Introduction of Turbofan Engine Degradation Simulation Data 30
4.2.2. Data structure 30
4.2.3. Data preprocess 32
4.2.4. Result 32
4.3. EXPERIMENT 3: BEARING DATA 34
4.3.1. Introduction of Bearing Data 34
4.3.2. Data structure 34
4.3.3. Result 35
4.4. EXPERIMENT 4: FEMTO BEARING DATA 36
4.4.1. Introduction of FEMTO Bearing Data 36
4.4.2. Data structure 37
4.4.3. Data preprocess 37
4.4.4. Result 38
4.5. CONCLUSION OF FOUR DATA SET 39
CHAPTER 5. CONCLUSION 41
REFERENCES 43
APPENDIX A

1. Abou-Moustafa, K. T., Cheriet, M., & Suen, C. Y. (2004). On the Structure of Hidden Markov Models. Pattern Recognition Letters, 25(8), 923-931. doi:http://dx.doi.org/10.1016/j.patrec.2004.02.005
2. Akaike, H. (1974). A New Look at The Statistical Model Identification. IEEE Transactions on Automatic Control, 19(6), 716-723. doi:10.1109/TAC.1974.1100705
3. Akaike, H. (2011). Akaike’s Information Criterion. In M. Lovric (Ed.), International Encyclopedia of Statistical Science (pp. 25-25). Berlin, Heidelberg: Springer Berlin Heidelberg.
4. Baumgartner, U., Magele, C., & Renhart, W. (2004). Pareto Optimality and Particle Swarm Optimization. IEEE Transactions on Magnetics, 40(2), 1172-1175. doi:10.1109/TMAG.2004.825430.
5. Bicego, M., Dovier, A., & Murino, V. (2001). Designing the Minimal Structure of Hidden Markov Model by Bisimulation. In M. Figueiredo, J. Zerubia, & A. K. Jain (Eds.), Energy Minimization Methods in Computer Vision and Pattern Recognition: Third International Workshop, EMMCVPR 2001 Sophia Antipolis, France, September 3–5, 2001 Proceedings (pp. 75-90). Berlin, Heidelberg: Springer Berlin Heidelberg.
6. Bicego, M., Murino, V., & Figueiredo, M. A. T. (2003). A Sequential Pruning Strategy for the Selection of the Number of states in Hidden Markov Models. Pattern Recognition Letters, 24(9–10), 1395-1407. doi:http://dx.doi.org/10.1016/S0167-8655(02)00380-X
7. Biem, A. (2003, 3-6 Aug. 2003). A Model Selection Criterion for Classification: Application to HMM Topology Optimization. Paper presented at the Seventh International Conference on Document Analysis and Recognition, 2003. Proceedings.
8. Bishnu, P. S., & Bhattacherjee, V. (2012). Software Fault Prediction Using Quad Tree-Based K-Means Clustering Algorithm. IEEE Transactions on Knowledge and Data Engineering, 24(6), 1146-1150. doi:10.1109/TKDE.2011.163
9. Blunsom, P. (2004). Hidden Markov Models.
10. Coello, C. A. C. (2006). Evolutionary Multi-Objective Optimization: A Historical View of the Field. IEEE Computational Intelligence Magazine, 1(1), 28-36. doi:10.1109/MCI.2006.1597059
11. Ertunc, H. M., Loparo, K. A., & Ocak, H. (2001). Tool Wear Condition Monitoring in Drilling Operations Using Hidden Markov Models (HMMs). International Journal of Machine Tools and Manufacture, 41(9), 1363-1384. doi:http://dx.doi.org/10.1016/S0890-6955(00)00112-7
12. Fahad, A., Alshatri, N., Tari, Z., Alamri, A., Khalil, I., Zomaya, A. Y., Bouras, A. (2014). A Survey of Clustering Algorithms for Big Data: Taxonomy and Empirical Analysis. IEEE Transactions on Emerging Topics in Computing, 2(3), 267-279. doi:10.1109/TETC.2014.2330519
13. Giantomassi, A., Ferracuti, F., Benini, A., Ippoliti, G., Longhi, S., & Petrucci, A. (2011). Hidden Markov Model for Health Estimation and Prognosis of Turbofan Engines. (54808), 681-689. doi:10.1115/DETC2011-48174
14. Hassan, M. R., & Nath, B. (2005, 8-10 Sept. 2005). Stock market Forecasting Using Hidden Markov Model: A New Approach. Paper presented at the 5th International Conference on Intelligent Systems Design and Applications (ISDA'05).
15. Horn, J., Nafpliotis, N., & Goldberg, D. E. (1994, 27-29 Jun 1994). A Niched Pareto Genetic Algorithm for MultiObjective Optimization. Paper presented at the Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence.
16. Jain, A. K., Murty, M. N., & Flynn, P. J. (1999). Data Clustering: a Review. ACM Comput. Surv., 31(3), 264-323. doi:10.1145/331499.331504
17. Jen-Tzung, C., & Furui, S. (2005). Predictive Hidden Markov Model Selection for Speech Recognition. IEEE Transactions on Speech and Audio Processing, 13(3), 377-387. doi:10.1109/TSA.2005.845810
18. Johnson, S. C. (1967). Hierarchical Clustering Schemes. Psychometrika, 32(3), 241-254. doi:10.1007/bf02289588
19. Ku, C.-W. (2005). 利用多觀察值型隱馬可夫模型進行人體動作辨識. 71.
20. Lam Thu Bui, & Alam, S. (2008). An Introduction to Multi-Objective Optimization.
21. Liu, Y., Li, Z., Xiong, H., Gao, X., Wu, J., & Wu, S. (2013). Understanding and Enhancement of Internal Clustering Validation Measures. IEEE Transactions on Cybernetics, 43(3), 982-994. doi:10.1109/TSMCB.2012.2220543
22. MacQueen, J. (1967, 1967). Some Methods for Classification and Analysis of Multivariate Observations. Paper presented at the Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics, Berkeley, Calif.
23. Mou-Yen, C., Amlan, K., & Jian, Z. (1994). Off-line Handwritten Word Recognition Using A Hidden Markov Model Type Stochastic Network. IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(5), 481-496. doi:10.1109/34.291449
24. Nectoux, P., Gouriveau, R., Medjaher, K., Ramasso, E., Chebel-Morello, B., Zerhouni, N., & Varnier, C. (2012, 2012-06-18). PRONOSTIA : An Experimental Platform for Bearings Accelerated Degradation Tests. Paper presented at the IEEE International Conference on Prognostics and Health Management, PHM'12., Denver, Colorado, United States.
25. Omran, M. G. H., Engelbrecht, A. P., & Salman, A. (2007). An Overview of Clustering Methods. Intell. Data Anal., 11(6), 583-605.
26. Qiu, H., Lee, J., Lin, J., & Yu, G. (2006). Wavelet Filter-based Weak Signature Detection Method and Its Application On Rolling Element Bearing Prognostics. Journal of Sound and Vibration, 289(4–5), 1066-1090. doi:http://doi.org/10.1016/j.jsv.2005.03.007
27. Rabiner, L. R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE, 77(2), 257-286. doi:10.1109/5.18626
28. Rosenberger, C., & Chehdi, K. (2000, 2000). Unsupervised Clustering Method with Optimal Estimation of the Number of Clusters: Application to Image Segmentation. Paper presented at the Proceedings 15th International Conference on Pattern Recognition. ICPR-2000.
29. Schwarz, G. (1978). Estimating the Dimension of A Model. The Annals of Statistics, 6(2), 461-464. doi:citeulike-article-id:90008 doi: 10.2307/2958889
30. Sloukia, F., Aroussi, M. E., Medromi, H., & Wahbi, M. (2013, 27-30 May 2013). Bearings Prognostic Using Mixture of Gaussians Hidden Markov Model and Support Vector Machine. Paper presented at the 2013 ACS International Conference on Computer Systems and Applications (AICCSA).
31. Stenger, B., Ramesh, V., Paragios, N., Coetzee, F., & Buhmann, J. M. (2001, 2001). Topology Free Hidden Markov Models: Application to Background Modeling. Paper presented at the Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001.
32. Su, W., & Jin, X. (2011, 17-18 Sept. 2011). Hidden Markov Model with Parameter-Optimized K-Means Clustering for Handwriting Recognition. Paper presented at the 2011 International Conference on Internet Computing and Information Services.
33. Tan, P.-N. (2006). Introduction to Data Mining: Pearson Education India.
34. Trentin, E., & Gori, M. (2001). A Survey of Hybrid ANN/HMM Models for Automatic Speech Recognition. Neurocomputing, 37(1–4), 91-126. doi:http://dx.doi.org/10.1016/S0925-2312(00)00308-8
35. Visser, I., & Speekenbrink, M. (2010). depmixS4: An R Package for Hidden Markov Models. 2010, 36(7), 21. doi:10.18637/jss.v036.i07
36. Vrieze, S. I. (2012). Model Selection and Psychological Theory: A Discussion of the Differences Between the Akaike Information Criterion (AIC) and the Bayesian Information Criterion (BIC). Psychological Methods, 17(2), 228-243. doi:10.1037/a0027127
37. Wang, L., Mehrabi, M. G., & Kannatey-Asibu, J. E. (2002). Hidden Markov Model-based Tool Wear Monitoring in Turning. Journal of Manufacturing Science and Engineering, 124(3), 651-658. doi:10.1115/1.1475320
38. Yoon, B.-J. (2009). Hidden Markov Models and Their Applications in Biological Sequence Analysis. Current Genomics, 10(6), 402-415. doi:10.2174/138920209789177575
39. Yu, J. (2012). Health Condition Monitoring of Machines Based on Hidden Markov Model and Contribution Analysis. IEEE Transactions on Instrumentation and Measurement, 61(8), 2200-2211. doi:10.1109/TIM.2012.2184015