Resampling approach for cluster model selection

Creative Commons License

Volkovich Z., Barzily Z., Weber G., Toledano-Kitai D., Avros R.

MACHINE LEARNING, vol.85, pp.209-248, 2011 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 85
  • Publication Date: 2011
  • Doi Number: 10.1007/s10994-011-5236-9
  • Journal Name: MACHINE LEARNING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.209-248
  • Middle East Technical University Affiliated: Yes


In cluster analysis, selecting the number of clusters is an "ill-posed" problem of crucial importance. In this paper we propose a re-sampling method for assessing cluster stability. Our model suggests that samples' occurrences in clusters can be considered as realizations of the same random variable in the case of the "true" number of clusters. Thus, similarity between different cluster solutions is measured by means of compound and simple probability metrics. Compound criteria result in validation rules employing the stability content of clusters. Simple probability metrics, in particular those based on kernels, provide more flexible geometrical criteria. We analyze several applications of probability metrics combined with methods intended to simulate cluster occurrences. Numerical experiments are provided to demonstrate and compare the different metrics and simulation approaches.