Research On Multi-Level Clustering Algorithms And Their Applications

Clustering algorithms are the techniques used for categorization in the field of data mining and have been applied in a variety of engineering and scientific fields such as medicine,sociology,psychology,biology,pattern recognition and image processing and so on.Clustering can be described as finding classes in a data set,that is,the similarity between data in the same class is high,and the similarity between data in different classes is low.Clustering algorithm is an unsupervised learning method and its typical application is the image segmentation in the field of machine learning.Image is the most intuitive and effective way for people to obtain information.Furthermore,image segmentation is to segment the useful or meaningful parts of the image into the next step of analysis and processing.With the continuous development of image segmentation technology,image segmentation has been well applied in many fields such as communication,medical diagnosis,remote sensing image analysis,traffic command,agriculture and industrial development,military field and so on.Because clustering algorithms are simple and easy to implement,they are widely used in image segmentation.Therefore,how to accomplish the image segmentation rapidly and with high quality becomes the hot topic and the key point in the field of image segmentation using the clustering algorithm.In this thesis,the disadvantages of clustering algorithms and applications in the image segmentation are discussed and studied.The main innovations of this paper are as follows:(1)In order to overcome the shortcomings that the traditional K-means algorithm needs to specify the number of classes and easily converges to the local optimum,a new K-means algorithm which automatically determines the number of classes by using gravitation and provides better initial centers simultaneously is proposed in this thesis.Compared with the traditional K-means algorithm,the proposed algorithm can automatically determine the number of classes without specifying the number of classes.As the proposed algorithm can give better initial centers,it is not easy to converge to the local optimal solution.(2)Aiming at the existing problems of distributing the remaining data after finding the clustering center by the algorithm FDP,a new method based on density clustering algorithm DBSCAN is proposed.The proposed method uses the DBSCAN algorithm to allocate the remaining data to the correct category after finding the cluster center by the algorithm FDP.This method considers the relationships between the data are considered in the allocation of the rest of the data,rather than directly and simply allocating the data to the nearest center.Compared with the original FDP algorithm,the proposed algorithm can deal with the nonconvex data and get better clustering results.(3)In view of the high space complexity in the image segmentation by using the algorithm AP,and in order to reduce the sensitivity of the algorithm to the parameters,a multi-level clustering algorithm based on spectral clustering is proposed in this paper.The proposed method is divided into three stages.In the first stage,the sparse AP algorithm is used to separate the data set approximately,which requires to give the initial value of the parameter ?preference?.In this thesis,the initial value of the parameter ?preference? is the minimum value in the similarity matrix.In addition,we only compute the similarity between each point and its t nearest neighbors,instead of seeking the full similarity matrix.With this coarsening AP algorithm,the data will be partitioned into more large number clusters.After the coarsening,we select a representative point from every cluster to enter the second stage.In the second stage,we use SSC algorithm to cluster these representative points,and the amount of data processed by SSC algorithm is very small relative to all data.In the third stage,it will yield a final partition of all the data by emerging the results of the first two phases.The proposed algorithm combines the advantages of AP and SSC algorithms,and it can be applied to different types of data sets.Experiments show that using the proposed algorithm for image segmentation can get more ideal results.(4)In order to improve the time efficiency of the image segmentation,this thesis proposes a multi-level clustering algorithm based on density peak algorithm by combining the FDP and AP algorithms,because the FDP algorithm has small amount of calculation and fast speed.Firstly,we use the sparse AP algorithm to separate all the data roughly,and then use the FDP algorithm to subdivide the representative points.Lastly,we combine the two-stage results to get a division of all the data.Experiments show that the algorithm reduces the dependency of the parameters,and achieves less time complexity and better texture image segmentation results.In addition,aiming at the huge amount of astronomical data which can not be directly clustered by some clustering algorithm,this thesis applies the proposed multi-level algorithm based on density peak in the classification of galaxies and stars.Moreover,according to the data volume for astronomical data is huge and cannot be directly clustered by a clustering algorithm,this paper use the multi-level algorithm based on density peak algorithm in astronomy that is the classification of galaxies and stars.The classification of galaxies and stars is a fundamental task in astronomy,which is very important for humans to understand the formation and evolution of stars and galaxies and to find special objects in space.Experiments show that the algorithm proposed in this paper has a higher correct rate in dividing stars and galaxies.