关键词: 图论, 聚类, k近邻

Abstract: A novel clustering algorithm based on graph theory named NeiMu is proposed.NeiMu first analyzes all the objects in data，searching k-nearest neighbors for each object and constructing directed graph of k-nearest neighbors.Then it constructs k-clustering graph according to the k-mutual neighbor in directed graph of k-nearest neighbors.Finally，it discovers natural clusters in data on the basis of k-clustering graph.The significant characteristic of NeiMu is the ability of determining natural clusters by mutual neighbor relations in data，instead of introducing other partition methods to divide data into small clusters.As a consequence，NeiMu guarantees that all the objects will not be clustered erroneously but be merged into bigger clusters with other small clusters.This advantage will ensure the clustering quality of NeiMu algorithm.Furthermore，NeiMu，which presents results similar to bottom-up hierarchical clustering algorithm，facilitates users to determine the best k according to the gradually merging results.The experiments show that NeiMu exhibits good clustering quality for data with variable densities，variable sizes and arbitrary shapes.It is also robust with outliers.

Key words: graph theory, clustering, k-neighbor