An Improved Genetic Clustering Algorithm for Feature Extraction of Laser Scanner
YU Jin-Xia1,2, CAI Zi-Xing2, DUAN Zhuo-Hua2,3
1.College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 4540032. College of Information Science and Engineering, Central South University, Changsha 4100833. Department of Computer Science, Shaoguan University, Shaoguan 512003
Abstract:To automatically extract the environmental feature obtained by 2D laser scanner, an improved genetic clustering algorithm is presented. Firstly, a weighted fuzzy clustering algorithm is introduced to realize feature extraction of laser scanner after integrating the spatial neighboring information of range data into fuzzy clustering algorithm. Then, aiming at the unknown clustering number, the validities of different clustering algorithms are estimated by choosing a suitable index function for the fitness function of genetic algorithm. Moreover, to solve the local optimum of clustering algorithm, the genetic clustering algorithm is improved. The population diversity is increased and the genetic operators of elitist rule are improved to enhance the local search capacity and speed up the convergence. Compared with other algorithms, the effectiveness of the proposed algorithms is demonstrated.
[1] Murphy R R. Introduction to AI Robotics. Cambridge, USA: MIT Press, 2004 [2] Duda R O, Hart P E, Stork D G. Pattern Classification. 2nd Edition. New York, USA: Wiley, 2001 [3] Bezdek J C. Pattern Recognition with Fuzzy Objective Function Algorithms. New York, USA: Plenum Press, 1981 [4] Gustafson D E, Kessel W C. Fuzzy Clustering with a Fuzzy Covariance Matrix // Proc of the IEEE Conference on Decision and Control. San Diego, USA, 1979: 761-766 [5] Kaymak U, Setnes M. Fuzzy Clustering with Volume Prototypes and Adaptive Cluster Merging. IEEE Trans on Fuzzy Systems, 2002, 10(6): 705-712 [6] Sun Jixiang. Modern Pattern Recognition. Changsha, China: National University of Defense Technology Press, 2002(in Chinese) (孙即祥.现代模式识别.长沙:国防科技大学出版社, 2002) [7] Borges G A, Aldon M J. Line Extraction in 2D Range Images for Mobile Robotics. Journal of Intelligent and Robotic Systems, 2004, 40(3): 267-297 [8] Bezdek J C. Numerical Taxonomy with Fuzzy Sets. Journal of Mathematical Biology, 1974, 1(1): 57-71 [9] Bezdek J C. Cluster Validity with Fuzzy Sets. Journal of Cybernetics, 1974, 3(3): 58-72 [10] Xie X L, Beni G. A Validity Measure for Fuzzy Clustering. IEEE Trans on Pattern Analysis and Machine Intelligence, 1991, 13(8): 841-847 [11] Davies D L, Bouldin D W. A Cluster Separation Measure. IEEE Trans on Pattern Analysis and Machine Intelligence, 1979, 1(2): 224-227 [12] Kim D W, Lee K H, Lee D. On Cluster Validity Index for Estimation of the Optimal Number of Fuzzy Clusters. Pattern Recognition, 2004, 37(10): 2009-2025 [13] Kim Y I, Kim D W, Lee D, et al. A Cluster Validation Index for GK Cluster Analysis Based on Relative Degree of Sharing. Information Sciences, 2004, 168(1/2/3/4): 225-242 [14] Wu K L, Yang M S. A Cluster Validity Index for Fuzzy Clustering. Pattern Recognition Letters, 2005, 26(9): 1275-1291 [15] Bandyopadhyay S, Maulik U. Nonparametric Genetic Clustering: Comparison of Validity Indices. IEEE Trans on Systems, Man and Cybernetics, 2001, 31(1): 120-125 [16] SICK AG Corp. Technical Description: LMS200/LMS211/LMS220/LMS221/LMS291. Laser Measurement Systems [EB/OL]. [2000-06-06]. http://www.sick.com