臺灣博碩士論文加值系統

在高維度的空間中進行屬性篩選已被證明是NP完備問題(NP-complete problem)。傳統的最佳化演算法在處理大尺寸屬性篩選問題時是較沒有效率的，因此啟發式演算法廣泛使用在此類問題中。
本研究的目的在於發展出二種以粒子最佳化演算法(Particle Swarm Optimization)為基礎的方法：改良型粒子最佳化演算法使用相反符號檢驗(Opposite Sign Test)和以迴歸為基礎的粒子最佳化演算法(Regression-Based Particle Swarm Optimization)。這二種演算法可增加粒子的多變性，讓粒子最佳化演算法可以跳脫區域最佳解，以增進粒子最佳化演算法的解題能力。
為了測試與評估本研究所提出的方法，本研究從UCI機器學習資料庫選取資料，以分類正確率為指標，結果顯示本研究所提出的方法優於基因演算法(Genetic Algorithms)和循環搜尋演算法(Sequential Search Algorithms)。
此外，本研究使用睡眠呼吸中止症的實際資料，來說明本研究提出的方法的有效性。結果顯示本方法可做睡眠呼吸中止症早期診斷工具，使醫療資源獲得更有效的利用。

Searching for an optimal feature subset from a high-dimensional feature space is an NP-complete problem; hence, traditional optimization algorithms are inefficient when solving large-scale feature selection problems. Therefore, meta-heuristic algorithms are extensively adopted to solve such problems efficiently. This study proposes two approaches: opposite sign test and regression-based particle swarm optimization for feature selection problem. The proposed algorithms can increase population diversity and avoid local optimal trapping by improving the jump ability of flying particles. The data sets collected from UCI machine learning data bases are used to evaluate the effectiveness of the proposed approaches. Classification accuracy is used as a criterion to evaluate classifier performance. Results show that our proposed approaches outperform both genetic algorithms and sequential search algorithms.
In addition, a real case about the diagnosis of obstructive sleep apnea (OSA) using the proposed approach is presented. Through the implementation of this real case study, we found that the proposed approach could be applied as a screening tool for early OSA diagnosis. As a result, PSO can be applied to assist doctors in foreseeing the diagnosis of OSA before running the PSG test, allowing the medical resources to be used more effectively.

摘要 i
ASBTRACT ii
誌謝 iv
CONTENTS v
TABLES vii
FIGURES viii
NOTATION ix
1 INTRODUCTION 1
1.1 Overview and Motivations 1
1.2 Objectives 2
1.3 Organization 3
2 RELATED WORKS 5
2.1 Feature Selection Problem 5
2.2 Feature Selection Algorithms 6
2.2.1 Enumeration Algorithms 6
2.2.2 Sequential Search Algorithms 7
2.2.3 Stochastic Algorithms 7
2.2.4 Discussion 9
2.3 PSO Algorithm 10
2.4 k-Nearest Neighbor Algorithms 13
3 PROPOSED APPROACHES 15
3.1 Simple PSO for Feature Selection 15
3.1.1 Particles Encoding 15
3.1.2 Initial Population 15
3.1.3 Measure the Fitness of Each Particle in Population 15
3.2 An Improved PSO for Feature Selection 17
3.3 A Regression-Based PSO for Feature Selection 20
4 PERFORMANCE ANALYSIS 25
4.1 Environment 25
4.2 Numerical Experiments 31
4.3 Discussion 37
5 A CASE STUDY 40
5.1 Obstructive Sleep Apnea 40
5.2 Case Description 41
5.3 Implementation 42
5.4 Discussions 45
6 CONCLUSIONS 46
References 48

[1] A. Cervantes, I. M. Garia and P. Isasi, AMPSP: A New Particle Swarm Method for Nearest Neighborhood Classification, IEEE Transactions on Systems, Man, and Cybernetics -Part B 39 (2009) 1082–1091.
[2] A. Qureshi and R. D. Ballard, Obstructive sleep apnea, Journal of Allergy and Clinical Immunology 112 (2003) 643–651.
[3] A. Tsanas, M. A. Little, P. E. McSharry and L. O. Ramig, Accurate Telemonitoring of Parkinsons Disease Progression by Noninvasive Speech Tests, IEEE Transactions on Biomedical Engineering 57 (2010) 884–893.
[4] Anonymous, Sleep-Related Breathing Disorders in Adults: Recommendations for Syndrome Definition and Measurement Techniques in Clinical Research, Sleep 22 (1999) 667–689.
[5] C. A. Lewis, T. E. Eaton, W. Fergusson, K. F. Whyte, J. E. Garrettand and J. Kolbe, Home Overnight Pulse Oximetry in Patients with COPD: More Than One Recording May be Needed, Chest 123 (2003) 1127–1133.
[6] D. D. Lewis, Feature Selection and Feature Extraction for Text Categorization, Proceedings Speech and Natural Language workshop (1992) 212–217.
[7] D. K. Agrafiotis and W. Cedeno, Feature Selection for Structure-Activity Correlation Use Binary Particle Swarms, Journal of Medicinal Chemistry 45 (2002) 1098–1107.
[8] D. K. Agrafiotis and W. Cedeño, Feature Selection for Structure-Activity Correlation Using Binary Particle Swarms, Journal of Medicinal Chemistry 45 (2002) 1098–1107.
[9] F. Kapsimalis and M. H. Kryger, Gnder and Ostructive Sleep Apnea Syndrome, Sleep 25 (2002) 497–504.
[10] F. Melgani and Y. Bazi, Classification of Electrocardiogram Signals with Support Vector Machine and Particle Swarm Opt, Information Technology in Biomedicine 12 (2008) 667–677.
[11] F. E. Fix and J. L. Hodges, Discriminatory Analysis-Nonparametric Discrimination: Consistency Properties, School of Mathematical Sciences 4 (1951) 261–279.
[12] H. Schäfer, S. Ewig, E. Hasper and B. Lüderitz, Predictive Diagnostic Value of Clinical Assessment and Nonlaboratory Monitoring System Recordings in Patients with Symptoms Suggestive of Obstructive Sleep Apnea Syndrome, NCBI 64 (1997) 194–199.
[13] I. Gurubhagavatula and G. Maislin, An Algorithm to Stratify Sleep Apnea Risk in a Sleeps is Orders Clinic Population, American Journal of Respiratory and Critical Care Medicine 170 (2001) 371–376.
[14] I. Ziari and A. Jalilian, A New Approach for Allocation and Sizing of Multiple Active Power-Line Conditioners, IEEE Transactions on Power Delivery 25 (2010) 1026–1035.
[15] I. A. Gheyas and L. S. Smith, Feature Subset Selection in Large Dimensionality Domains, Pattern Recognition 43 (2010) 5–13.
[16] I. S. Oh, J. S. Lee and B. R. Moon, Hybrid Genetic Algorithms for Feature Selection, IEEE Transactions on Pattern Analysis Machine Intelligence 26 (2004) 1424–1437.
[17] J. Ai and V. Kachitvichyanukul, A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery, Computers and Operations Research 36 (2009) 1693–1702.
[18] J. Chen, Z. Ren and X. Fan, Particle Swarm Optimization with Adaptive Mutation and Its Application Research in Tuning of PID Parameters, Systems and Control in Aerospace and Astronautics (2006).
[19] J. Gertheiss and G. Titz, Feature Selection and Weighting by Nearest Neighbor Ensembles, Chemometrics and Intelligent Laboratory Systems 99 (2009) 30–38.
[20] J. Kennedy, R. C. Eberhart and Y. Shi, Swarm Intelligence, Morgan Kaufman (2001).
[21] J. Wright, R. Johns, I. Watt, A. Melvilleand T. Sheldon, Health Effects of Obstructive Sleep Apnea and the Effectiveness of Continuous Positive Airway Pressure: A Systematic Review of the Research Evidence, British Medical Journal 314 (1997) 851–860.
[22] J. B. Park, Y. W. Jeong, J. R. Shin and K. Y. Lee, An Improved Particle Swarm Optimization for Nonconvex Economic Dispatch Problems, IEEE Transactions on Power System 25 (2010) 156–166.
[23] J. B. V. Reddy, P. K. Dash, R. Samantaray and A. K. Moharana, Fast Tracking of Power Quality Disturbance Signals Using an Optimized Unscented Filte, IEEE Transactions on Instrumentation and Measurement 58 (2009) 3943–3952.
[24] J. H. Lee and G. H. Cha, A Model for K-Nearest Neighbor Query Processing Cost in Multidimensional Data Space, Information Processing Letters 69 (1999) 69–76.
[25] J. H. Yang and V. Honavar, Feature Subset Selection Using a Genetic Algorithm, IEEE Intelligent System 13 (1998) 44–49.
[26] K. P. Pang, D. J. Terris and R. Podolsky, Screening for Obstructive Sleep Apnea: an Evidence-Based Analysis, American Journal of Otolaryngology 27 (2006) 112–118.
[27] L. D. Rosenthal and D. C. Diana, The Epworth Sleepiness Scale in the Identification of Obstructive Sleep Apnea, The Journal of Nervous and Mental Disease 196 (2008) 429–431.
[28] L. Y. Chuang, H. W. Chang and C. H. Yang, Improved Binary PSO for Feature Selection Using Gene Expression Data, Computational Biology and Chemistry 32 (2008) 29–38.
[29] M. Dash and H. Lin, Feature Selection for Classification, Intelligent Data Analysis 1 (1997) 131–156.
[30] M. Kubat and S. Matwin, Addressing the Curse of Imbalanced Training Set: One-Sided Selection, Proceedings 14th International Conference on Machine Learning (ICML ’97) (1997).
[31] M. Kudo and J. Sklansky, Comparison of Algorithms that Select Features for Pattern Recognition, Pattern Recognition 33 (2000) 25–41.
[32] M. F. Tasgetiren and Y. C. Liang, A Binary Particle Swarm Optimization Algorithm for Lot Sizing Problem, Journal of Economic and Social Research 5 (2007) 1–20.
[33] M. P. Song and G. C. Gu, Research on Particle Swarm Optimization: A Review, Proceedings of the International Conference on Machine Learning and Cybernetics 4 (2004) 2236–2241.
[34] M. R. Shepertycky, K. Banno and M. H. Kryger, Differences Between Men and Women in Clinical Presentation of Patients Diagnosed with Obstructive Sleep Apnea Syndrome, Sleep 28 (2005) 309–314.
[35] M. W. Bollmfield, J. E. Herencia and P. M. Weaver, Analysis and Benchmarking of Meta-Heuristic Techniques for Lay-Up Optimization, Computers and Structures 88 (2010) 272–282.
[36] N. Netzer, A. H. Eliasson, C. Netzer and D. A. Krisco, Overnight Pulse Oximetry for Sleep-Disordered Breathing in Adults-A Review, Chest 12 (2001) 625–633.
[37] R. E. Gliklich and P. C. Wang, Validation of the Snore Outcomes Survey for Patients with Sleep-Disordered Breathing, Arch Otolaryngol Head Neck Surg 128 (2002) 819–824.
[38] R. O. Duda, P. E. Hart and D. G. Stork, Pattern Classification, Wiley-Interscience, (2000).
[39] S. Maximiliano and T. Yuji, Conformational Analyses and SAR Studies of Antispermatogenic Hexahydroindenopyridines, Journal of Molecular Structure: Theochem 633 (2003) 93–104.
[40] S. Tan, Neighbor-Weighted K-Nearest Neighbor for Unbalanced Text Corpus, Expert System with Applications 28 (2005) 667–671.
[41] S. Theodoridis and K. Koutroumbas, Pattern Recognition, Academic press, New York (1999).
[42] S. S. Durbha, R. L. King and N. H. Younan, Wrapper -Based Feature Subset Selection for Rapid Image Information Mining, IEEE Geoscience and Remote Sensing 7 (2010) 43–47.
[43] S. V. Jacob, A. Morielli, M. A. Mograss, F. M. Ducharme, M. D. Schlossand R. T. Brouillette, Home Testing for Pediatric Obstructive Sleep Apnea Syndrome Secondary to Adenotonsillar Hypertrophy, Pediatr Pulmonol 20 (1995) 241–252.
[44] T. Young, M. Palta, J. Dempsey, J. Skatrud, S. Weber and S. Badr, He Occurrence of Sleep-Disordered Breathing Among Middle-Aged Adults, New England Journal of Medicine 328 (1993) 1230–1235.
[45] T. Young, P. E. Peppard and D. J. Gottlieb, Obstructive Sleep Apnea: a Population Health Perspective, American Journal of Respiratory and Critical Care Medicine 165 (2002) 1217–1239.
[46] T. H. Lin, H. T. Li and K. C. Tsai, Implementing the Fisher’s Discriminant Ratio in a k-Means Clustering Algorithm for Feature Selection and Data Set Trimming, Journal of Chemical Information and Computer Sciences 44 (2004) 76–87.
[47] X. Hu and R. Eberhart, Multiobjective Optimization Using Dynamic Neighborhood Particle Swarm Optimization, IEEE Congress on Evolutionary Computation 2 (2002) 1677–1681.
[48] X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu and L. M. Wang, An Improved GA and a Novel PSO-GA-Based Hybrid Algorithm, Information Processing Letters 93 (2005) 255–261.
[49] Y. Shi and R. C. Eberhart, A Modified Particle Swarm Optimizer, IEEE International Conference on Evolutionary Computation Anchorage Alaska (1998) 69–73.
[50] Y. J. Fan and W.A. Chaovalitwongse, Optimizing Feature Selection to Improve Medical Diagnosis, Annals of Operations Research 174 (2010) 169–183.