粗略不相似度量及其在层次聚类中的应用

Rough Dissimilarity Measurement and Its Application in Hierarchical Clustering

局部结构特征在数据分析过程中具有重要的作用.为获得简单有效的数据集局部结构化特征检测方法,本文结合重采样误差分析和传统的近邻选择方法提出了一种检测局部结构特征的方向一致性度量—粗略不相似性度量.该度量是一种优化的近邻选择方法,不仅考虑了传统的欧氏距离排序,而且考虑了局部方向结构特征.因其计算和存储复杂度小以及具有优越的结构检测性能,可应用于无监督学习形成一种层次化的子图聚类算法—RDClust,与经典聚类算法相比,其优势在于:一是计算复杂度较小,是近似线性算法;二是无需对类的形状和分布形式做任何的假设,可自动体现数据集的局部结构;三是有一个近邻参数,且该参数对结果较鲁棒.在人工和真实数据集上的实验显示了新的度量方式应用于新算法的优越性能.

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