Study of high dimensional clustering algorithm based on graph partition

In many clustering applications, the data sets are high-dimensional, sparse and binary, resulting to the failure of traditional algorithms in handling these data. In this paper, we present a new clustering algorithm based on graph partition for high-dimensional data, which, by defining the feature vector of attribute-value distribution and the similarity of attribution-value distribution, and creating a sequence of smaller and smaller coarse graphs from the original base graph. The smallest coarse graph is then partitioned using a spectral method, and this partition is propagated back through the hierarchy of graphs. Thus, the corresponding data items in each partition are highly related. The analysis demonstrates that this algorithm is effective in clustering knowledge discover.