Research And Application Of Cluster Analysis Based On DNA Genetic Algorithm

Clustering analysis is a very important branch of unsupervised classificationin pattern recognition.Because the needs of the research to the real problem is increasing,so the study of clustering analysis and the corresponding clustering method is also gradually increasingin recent years.Considering the realistic problems has the characteristic of fuzzyin the classification process,so the fuzzy c-means clustering algorithm which based on the objective function is gradually widely used.At the same time,spectral clustering is also an important trend of the current clustering which can transformed the clustering problem to the undirected weighted graph in graph theory.Both of the clustering algorithm are the hotspot of current research,but every algorithm has its own disadvantages.In order to make up the inadequacy of algorithm,we can use some optimization algorithm to optimize the clustering algorithm can improve the performance of the clustering algorithms.So in this paper we mainly studies the fuzzy c-means clustering algorithm,spectral clustering algorithm and we use the DNA genetic algorithm to utilized the two clustering algorithm.In the every kinds of fuzzy clustering algorithm,the fuzzy c-means clustering(FCM)is widely used in the implementation process,because of it has better local search ability and easy operation.But the fuzzy c-means clustering algorithm also has some inherent flaw and the insufficiency.Firstly,the qualification of the membership degree need to be 1 will lead to the data points are more sensitive to noise and outliers.Secondly,the fuzzy c-means clustering algorithm is sensitive to the initial clustering center and easy to fall into local optimum.In this paper,in order to overcome the disadvantages of the fuzzy c-means clustering algorithm.Firstly,we improved the calculation method of the membership degree,in order to reduce the impact of the noise and outliers on the result of clustering.Secondly,we jointed the density in the calculation of the membership degree,in order to overcome the FCM algorithm is sensitive to the initial clustering center.At the same time,in order to find the globaloptimal solution,we use the DNA genetic algorithm to assist the FCM algorithm to jump out of local optimal.Spectral clustering(Spectral clustering,SC)algorithm is based on Spectral graph theory in graph theory,the essence is translate clustering problem into a graph partition problems.Even through the spectral clustering is an emerging field at present,in many places still exist deficiencies.Original spectral clustering,which is used the Euclidean distance of the gaussian kernel function to construct the similarity matrix,will be affected by the uncertainty gaussian kernel parameter ?.So in this paper we established the similarity matrix based on the adjusted correlation coefficient and don't need to manual setting parameters.And we also combined the improved DNA genetic algorithm with the K-means to complete the clustering process,in order to fall into local optimum.DNA genetic algorithm use the quaternary encoding,which can be more flexible to express the complex information and will have the higher coding accuracy.DNA genetic algorithm also has good global search ability,and the characteristics of stealth parallelism.In this paper,we use the improved DNA genetic algorithm to optimized the spectral clustering algorithm and fuzzy c-means algorithm.In this thesis,we used the Matlab to realized the simulation and experiment.Firstly,we used the test function and artificial data set to proved the effectiveness of the improved DNA genetic algorithm.Secondly,we used the UCI data set to verificate the effectiveness of the improved fuzzy C means algorithm and spectral clustering.The end,the improved fuzzy C means algorithm was used to realizedthe classificated of the sogou lab corpus of text and the result proved the validity of the algorithm.