Exemplar-based clustering via simulated annealing

Michael J. Brusco, Hans Friedrich Köhn

Research output: Contribution to journalArticle

Abstract

Several authors have touted the p-median model as a plausible alternative to within-cluster sums of squares (i.e., K-means) partitioning. Purported advantages of the p-median model include the provision of "exemplars" as cluster centers, robustness with respect to outliers, and the accommodation of a diverse range of similarity data. We developed a new simulated annealing heuristic for the p-median problem and completed a thorough investigation of its computational performance. The salient findings from our experiments are that our new method substantially outperforms a previous implementation of simulated annealing and is competitive with the most effective metaheuristics for the p-median problem.

Original languageEnglish (US)
Pages (from-to)457-475
Number of pages19
JournalPsychometrika
Volume74
Issue number3
DOIs
StatePublished - Sep 2009
Externally publishedYes

Fingerprint

P-median
P-median Problem
Simulated annealing
Simulated Annealing
Cluster Analysis
Clustering
K-means
Sum of squares
Metaheuristics
Outlier
Partitioning
Heuristics
Robustness
Alternatives
Model
Range of data
Experiment
Experiments

Keywords

  • Cluster analysis
  • Heuristics
  • P-median model
  • Partitioning
  • Simulated annealing

ASJC Scopus subject areas

  • Psychology(all)
  • Applied Mathematics

Cite this

Exemplar-based clustering via simulated annealing. / Brusco, Michael J.; Köhn, Hans Friedrich.

In: Psychometrika, Vol. 74, No. 3, 09.2009, p. 457-475.

Research output: Contribution to journalArticle

Brusco, Michael J. ; Köhn, Hans Friedrich. / Exemplar-based clustering via simulated annealing. In: Psychometrika. 2009 ; Vol. 74, No. 3. pp. 457-475.
@article{5c14a459cf384029a1f3b5cd119082ee,
title = "Exemplar-based clustering via simulated annealing",
abstract = "Several authors have touted the p-median model as a plausible alternative to within-cluster sums of squares (i.e., K-means) partitioning. Purported advantages of the p-median model include the provision of {"}exemplars{"} as cluster centers, robustness with respect to outliers, and the accommodation of a diverse range of similarity data. We developed a new simulated annealing heuristic for the p-median problem and completed a thorough investigation of its computational performance. The salient findings from our experiments are that our new method substantially outperforms a previous implementation of simulated annealing and is competitive with the most effective metaheuristics for the p-median problem.",
keywords = "Cluster analysis, Heuristics, P-median model, Partitioning, Simulated annealing",
author = "Brusco, {Michael J.} and K{\"o}hn, {Hans Friedrich}",
year = "2009",
month = "9",
doi = "10.1007/s11336-009-9115-2",
language = "English (US)",
volume = "74",
pages = "457--475",
journal = "Psychometrika",
issn = "0033-3123",
publisher = "Springer New York",
number = "3",

}

TY - JOUR

T1 - Exemplar-based clustering via simulated annealing

AU - Brusco, Michael J.

AU - Köhn, Hans Friedrich

PY - 2009/9

Y1 - 2009/9

N2 - Several authors have touted the p-median model as a plausible alternative to within-cluster sums of squares (i.e., K-means) partitioning. Purported advantages of the p-median model include the provision of "exemplars" as cluster centers, robustness with respect to outliers, and the accommodation of a diverse range of similarity data. We developed a new simulated annealing heuristic for the p-median problem and completed a thorough investigation of its computational performance. The salient findings from our experiments are that our new method substantially outperforms a previous implementation of simulated annealing and is competitive with the most effective metaheuristics for the p-median problem.

AB - Several authors have touted the p-median model as a plausible alternative to within-cluster sums of squares (i.e., K-means) partitioning. Purported advantages of the p-median model include the provision of "exemplars" as cluster centers, robustness with respect to outliers, and the accommodation of a diverse range of similarity data. We developed a new simulated annealing heuristic for the p-median problem and completed a thorough investigation of its computational performance. The salient findings from our experiments are that our new method substantially outperforms a previous implementation of simulated annealing and is competitive with the most effective metaheuristics for the p-median problem.

KW - Cluster analysis

KW - Heuristics

KW - P-median model

KW - Partitioning

KW - Simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=70350191760&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350191760&partnerID=8YFLogxK

U2 - 10.1007/s11336-009-9115-2

DO - 10.1007/s11336-009-9115-2

M3 - Article

AN - SCOPUS:70350191760

VL - 74

SP - 457

EP - 475

JO - Psychometrika

JF - Psychometrika

SN - 0033-3123

IS - 3

ER -