Research Of Clustering Algorithm Based On Improved Minimum Spanning Trees

Data mining refers to extracting implicit, previously unknown and usable knowledge from large amounts of data, it is one of the frontiers research in the fields of database and DSS. Cluster analysis is one of important research subject in it. Researching on the subject deeply has most important value in theory and application. Today many scholars attempt to solve clustering problem by different methods. As Clustering belongs to the unsupervised pattern recognition, each method has its own shortage, so the existing clustering technology need be improved, and new clustering method need be put forward to fit new application.The thesis utilizes the advanced thinking of traditional MST (minimum spanning tree) clustering algorithm and analyzes the shortage of time complexity and clustering efficiency , a new clustering algorithm based on IMST ( improved minimum spanning tree )which is applied to common problems is put forward. Firstly, a new method is adopted to construct minimum spanning tree by dealing with the data set and the middle set, which enhances the efficiency of constructing minimum spanning tree; secondly, while it can solve sorting problem that clusters are connected by shorter edges or weight-same edges in minimum spanning trees, by making use of matrix to figure spanning tree divided primarily, making the node with maximal degree be the center of clustering and finishing clustering according to center algorithm; finally, by analyzing multidimensional data and computing difference of every attribute, that is to say, some attributes have a little effect or no effect on constructing spanning tree, the efficiency can be improved and the complexity can also be decreased by deleting these attributes.The algorithm proposed solves the problem of traditional MST clustering algorithm, and the method to reduce data dimension is adopted in the algorithm to enhance the efficiency. The experiment shows the algorithm proposed has important values both in theory and practice.