A unique property of single-link distance and its application in data clustering

作者：Song Yuqing^*; Jin Shuyuan; Shen Jie

来源：Data & Knowledge Engineering, 2011, 70(11): 984-1003.

DOI：10.1016/j.datak.2011.07.003

• Hierarchical clustering
• Single-link cluster
• Icluster
• Isolation compactness
• Monotonic sequence

We prove a unique property of single-link distance, based on which an algorithm is designed for data clustering. The property states that a single-link cluster is a subset with inter-subset distance greater than intra-subset distance, and vice versa. Among the major linkages (single, complete, average, centroid, median, and Ward's), only single-link distance has this property. Based on this property we introduce monotonic sequences of iclusters (i.e., single-link clusters) to model the phenomenon that a natural cluster has a dense kernel and the density decreases as we move from the kernel to the boundary. A monotonic sequence of iclusters is a sequence of nested iclusters such that an icluster in the sequence is a dominant child (in terms of size) of the icluster before it. Our data clustering algorithm is monotonic sequence based. We classify a dataset of one monotonic sequence into to two classes by splitting the sequence into two parts: the kernel part and the surrounding part. For a data set of multiple monotonic sequences, each leaf monotonic sequence represents the kernel of a class, which then "grows" by absorbing nearby non-kernel points. This algorithm, proved by experiments, compares favorable in effectiveness to other clustering algorithms.

• 出版日期2011-11
• 单位中国科学院; 天津职业技术师范大学