Clustering algorithm based on minimal spanning tree

Abstract

The invention discloses a clustering algorithm based on a minimal spanning tree. The clustering algorithm includes the steps of S1, inputting a data set to be clustered and the number of categories K; S2, constructing a minimal spanning tree of the data set; S3, traversing the minimal spanning tree sequentially in a descending order of priority values of nodes; S4, merging between nodes; S5, calculating attributes of a new node after merging; S6, judging whether to end this traversal or not; and S7, judging whether to end the clustering. According to the invention, a skeleton of data points is constructed using the minimal spanning tree, multiple times of traversals and node merging are carried out according to the priority values of the nodes, and the clustering not is ended until the total number of nodes is equal to the number of categories K.

Description

technical field [0001] The invention relates to the fields of machine learning and data mining, in particular to a clustering algorithm based on minimum spanning trees. Background technique [0002] Clustering is to divide the set of data points into multiple clusters composed of similar objects according to the principle of similarity, so that the data belonging to the same cluster are similar to each other, and the data in different clusters are different from each other. Clustering has been very successfully applied in many fields such as business, biology, geography, Internet, etc. In the current era of big data, the research on fast and accurate clustering algorithms is particularly important. So far, typical clustering algorithms include: clustering algorithms based on hierarchy, clustering algorithms based on partition, clustering algorithms based on density and clustering algorithms based on grid, etc. [0003] The k-means clustering algorithm proposed by Forgy bel...

AI Technical Summary

Problems solved by technology

The hierarchical process of the clustering algorithm makes the clustering process clear, but the time cost of the algorithm is very expensive

In order to solve the problem of time complexity, Zhang et al. proposed the BRICH convergent clustering algorithm, which compresses data through clustering features and clustering feature numbers. This method not only reduces the amount of data to be processed, but also compresses The data still carry all the information needed by the BRICH algorithm, but the algorithm is only applicable to spherical data sets

The CURE algorithm proposed by Guha et al. can identify data of many complex shapes and handle outliers well. However, the algorithm is particularly sensitive to the input of parameters.

Images