ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (1): 163-178.doi: 10.7544/issn1000-1239.2018.20160937

Previous Articles     Next Articles

Fast Self-Adaptive Clustering Algorithm Based on Exemplar Score Strategy

Zhang Yuanpeng1,2, Deng Zhaohong1, Chung Fu-lai3, Hang Wenlong1, Wang Shitong1,3   

  1. 1(School of Digital Media, Jiangnan University, Wuxi, Jiangsu 214122);2(Department of Medical Informatics, Nantong University, Nantong, Jiangsu 226019);3(Department of Computing, Hong Kong Polytechnic University, Hong Kong 999077)
  • Online:2018-01-01

Abstract: Among the exemplar-based clustering algorithms, in order to improve their efficiencies and make them self-adaptive, a fast self-adaptive clustering algorithm based on exemplar score (ESFSAC) is proposed based on our previous work, a fast reduced set density estimator (FRSDE). The proposed ESFSAC is based on three significant assumptions that are stated as: 1) exemplars should come from high-density samples; 2) exemplars should be either the components of the reduced set or their neighbors with high similarities; 3) clusters can be diffused by surrounding both exemplars and its labeled reduced set. Based on the first two assumptions, a quantity called exemplar score is proposed to estimate the possibility of a sample as an exemplar and its rationale is theoretically analyzed. With exemplar score and the third assumption, a fast self-adaptive clustering algorithm is proposed. In this novel algorithm, firstly, all samples are ranked ordered by their exemplar scores descendingly, and stored in a set called exemplar candidate set. Secondly, exemplars in the candidate set are selected one by one and their labels are propagated to their neighbors in the reduced set. Thirdly, with the same strategy, the unlabeled samples gain their labels from the samples in the reduced set. To speed up this process, a sampling algorithm is introduced. The power of the proposed algorithm is demonstrated on several synthetic and real world datasets. The experimental results show that the proposed algorithm can deal with datasets with different shapes and large scale datasets without presetting the number of clusters.

Key words: exemplar score, fast reduced set density estimator (FRSDE), reduced set, label propagation, sampling

CLC Number: