臺灣博碩士論文加值系統

在機器學習的過程中，特徵選取被認為是一個全域最佳化搜尋的問題，就是將特徵的數量減少，去除不相關的雜訊特徵，使得分類正確率達到可接受的標準。 因此，特徵選取在資料分析、資訊擷取、圖形分類與資料探勘的應用領域非常重要。
在分類問題的特徵數量篩選上，一個好的特徵選取方法，需要具備快速的處理效率、預測的準確率，並且要避免難以理解的問題發生。本文利用二進位粒子族群最佳化，以全域最佳化搜尋結合區域的最佳化搜尋，將演算法改良成巢狀搜尋的模式，也就是利用二進位粒子族群最佳化在全域範圍做最佳化搜尋，達到一個固定疊代時間的時候，再以二進位粒子族群最佳化執行區域最佳化的搜尋。文中以K個最近鄰居法，做為演算法的適應函式。實驗結果顯示，巢狀式搜尋結果比非巢狀式更有效率。

The feature selection process can be considered a problem of global combinatorial optimization in machine learning, which reduces the number of features, removes irrelevant, noisy and redundant data, and results in acceptable classification accuracy. Feature selection is of great importance in the fields of data analysis and information retrieval processing, pattern classification, and data mining applications.
Therefore, a good feature selection method for sample classification, based on the number of features investigated, is needed to speed up the processing rate, predictive accuracy, and avoid incomprehensibility. In this paper, we propose to combine global optimization search and local optimization search for feature selection by nested binary PSO (NBPSO). NBPSO serves as a local optimizer each time and it has been run for a single generation as global optimizer. The K-nearest neighbor (K-NN) method with leave-one-out cross-validation (LOOCV) serves as an evaluator of the fitness function. Experimental results show the method simplifies features effectively and either obtains a higher classification accuracy or uses fewer features compared to other feature selection methods.

目 錄
中文摘要 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ i
英文摘要 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ ii
誌謝 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ iii
目錄 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ iv
表目錄 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ v
圖目錄 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ vi

一、 緒論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 1
1.1 研究動機‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 1
1.2 研究目的‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 2
1.3 論文架構‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 2
二、 文獻探討‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 3
2.1 特徵選取‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 3
2.2 粒子族群最佳化‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 9
三、 研究方法‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 19
3.1 研究架構‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 20
3.2 二進位粒子族群最佳化‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 24
3.3 巢狀式二進位粒子族群最佳化用於特徵選取‧‧‧‧‧‧ 26
3.3.1 巢狀式搜尋‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 31
3.3.2 巢狀式二進位粒子族群最佳化演算方法‧‧‧‧‧‧‧‧ 45
四、 結果與討論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 50
4.1 UCI測試資料集‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 50
4.2 微陣列基因表現資料集‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 55
4.3 討論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 61
五、 結論與未來研究‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 63
5.1 結論‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 63
5.2 未來研究‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 63
參考文獻 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 65
附錄一 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 68
附錄二 ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ 86

A. E. Eiben, E. Marchiori, V. A. Valko, (2004) Evolutionary algorithms with on-the-fly population size adjustment. Proc. 8th conference on Parallel Problem Solving from Nature, Birmingham, UK, Lecture Notes in Computer Science, Vol 3242, Springer, Berlin, pp.41-50.
Brandstatter, B. and Baumgartner, U. (2002). Particle swarm optimization-mass-spring system analogon. IEEE Transactions on Magnetics, Vol 38, pp.997-1000.
D. E. Goldberg, (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA
Dorigo, M. and Maniezzo, V. and Coleni, (1996). The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems and Cybernetics-Part B, Vol 26-1, pp.29-41.
Eberhart, R.C. and Kennedy, J. (1995). A new optimizer using particle swarm theory. Proc. Sixth Intl. Symposium on Micro Machine and Human Science (Nagoya, Japan), IEEE Service Center, Piscataway, NJ, 39-43.
Eberhart, R.C. and Shi. Y. (1998). Comparison between genetic algorithms and particle swarm optimization. 1998 Annual Conference on Evolutionary Programming, San Diego.
Eberhart, R. C. and Shi. Y. (2001). Particle swarm optimization: developments, applications and resources. Proc. IEEE Int. Conf. On Evolutionary Computation, pp.81-86.
Fukuyama, Y. and Yoshida, H. (2001). A particle swarm optimization for reactive power and voltage control in electric power systems. Congress Evolutionary Computation, Vol 1, pp.87-93.
I. Guyon, J. Weston, S. Barnhill and V. Vapnik, (2002) Gene selection for cancer classification using support vector machines. Machine Learning, Vol. 46, pp.389-422.
I. S. Oh, J. S. Lee, B. R. Moon, (2004) Hybrid Genetic Algorithms for Feature Selection. IEEE Transactions on pattern analysis and Machine Intelligence, Vol. 26 pp.1424-1437.
J. H. Holland, (1975). Adaptation in Natural and Artificial system. The University of Michigan Press, Ann Arbor, MI
J. Arabas, Z. Michalewicz, J. Mulawka, (1994). GAVaPS : a genetic algorithm with varying population size. Proc. IEEE conference on Evolutionary Computation, Orlando, FL, IEEE Service Center, Piscataway, NJ, pp.73-78.
James Kennedy and Russell C. Eberhart. (1997). A Discrete Binary Version of The Particle Swarm Algorithm. Proc. Conf. on systems, Man, AND Cybernetics, IEEE Service Center, Piscataway, NJ.4104-4108
Junying Chen, Zheng Qin, Yu Liu, and Jiang Lu, (2005). Particle Swarm Optimization with Local Search. Proc. IEEE Intl. Conf. on Neural Networks and Brain, pp.481-484
Kennedy, J. and Eberhart, R. C. (1995). Particle swarm optimization. Proc. IEEE International Conference on Neural Networks(Perth, Australia), IEEE Service Center, Piscataway, NJ, pp. IV:192-1948
Kennedy, J. (1997). The Particle swarm: Social adaptation of knowledge. Proc. IEEE Intl. Conf. on Neural Networks (Indianapolis, Indiana), IEEE Service Center, Piscataway, NJ, 303-308.
Lei Xu, (1988). Some applications of simulated annealing to pattern recognition. IEEE conference ICPR pp.1040-1042.
M. L. Raymer, W. F. Punch, E. D. Goodman, L. A. Kuhn and A. K. Jain. (2000) Dimensionality Reduction Using Genetic Algorithms. IEEE Trans. Evolutionary Computation. Vol. 4 pp.164-171.
P. Pudil, J. Novovicova, and J. Kittler, (1994). Floating Search Methods in Feature Selection. Pattern Recognition Letters, vol. 15, pp. 1119-1125.
P. M. Murphy and D. W. Aha, (1994) UCI Repository for Machine Learning Databases. technical report, Dept. of Information and ComputerScience, Univ. of California, Irvine, Calif, http://www.ics.uci.edu/mlearn/MLRepository.html.
R. Kohavi and G. John. (1997).Wrappers for feature subset selection. Artificial Intelligence pp. 273-324
Shi, Y. and Eberhart, R. C. (1998). A modified particle swarm optimizer. IEEE International Conference on Evolutionary Programming, Alaska, May 4-9.
Suganthan, P. N. (1999). Particle swarm optimizer with neighbourhood operator. Proc. Congress on Evolutionary Computation, pp.1958-1962.
Shi, Y. and Eberhart, R. C. (1999). Empirical study of particle swarm optimization. Proc. Congress on Evolutionary Computation, Vol 3, pp.1945-1950
Srinivasan, D. and Loo, W.H. and Cheu, R.L. (2003). Traffic incident detection using particle swarm optimization. IEEE Proc. Swarm Intelligence Symposium, pp.144-151.
T. Back, A. E. Eiben, N. A. L. van der Vaart. (2000) An empirical study on Gas without parameters. Proc. 6th conference on Parallel Problem Solving from Nature, Paris, France, Lecture Notes in Comput. Sci., Vol. 1917, Springer, Berlin, 2000, pp.315-324.
W. Siedlecky and J. Sklansky.(1988) On automatic feature selection. International Journal of Pattern Recognition and Artificial Intelligence, PP.197-220.
X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu, L. M. Wang. (2005) An improved GA and a novel PSO-GA-based hybrid algorithm. Information Processing Letters. pp.255-261