关键词: 聚类, 近邻域, 第$k$个近邻点连接, 层次连接图

Abstract: Local structural feature is important in data analysis procedure. In order to obtain a simple and effective feature detection method for data set's local structures, this paper proposed for detecting local structure a direction consistence measurement, rough dissimilarity, by combing re-sampling and a classical neighborhood selection method. This measurement is a optimized selection method for neighborhood, which considers not only the classical sorting method based on Euclidean distance but also the local structures of the data set. The new dissimilarity measurement can be used in unsupervised learning to construct a hierarchical subgraph clustering, RDClust, because of the advantages of a low computation load and a good direction structure detection performance. The new clustering based on direction consistence measurement has three advantages: 1) It has a low computation load and is an approximately linear method; 2) It needs no assumption for the shape and the distribution of cluster, and can detect local structures of a data set automatically; 3) It has only one parameter which is relatively robust to clustering results. The new clustering based on direction consistence dissimilarity has good performance in testing with synthetic and real data sets.

Key words: clustering, nearest neighborhood, $k$-th nearest neighbor connection, hierarchical connection graph