Clustering qualitative data based on binary equivalence relations: Neighborhood search heuristics for the clique partitioning problem

Michael J. Brusco, Hans Friedrich Köhn

Research output: Contribution to journalArticle

Abstract

The clique partitioning problem (CPP) requires the establishment of an equivalence relation for the vertices of a graph such that the sum of the edge costs associated with the relation is minimized. The CPP has important applications for the social sciences because it provides a framework for clustering objects measured on a collection of nominal or ordinal attributes. In such instances, the CPP incorporates edge costs obtained from an aggregation of binary equivalence relations among the attributes. We review existing theory and methods for the CPP and propose two versions of a new neighborhood search algorithm for efficient solution. The first version (NS-R) uses a relocation algorithm in the search for improved solutions, whereas the second (NS-TS) uses an embedded tabu search routine. The new algorithms are compared to simulated annealing (SA) and tabu search (TS) algorithms from the CPP literature. Although the heuristics yielded comparable results for some test problems, the neighborhood search algorithms generally yielded the best performances for large and difficult instances of the CPP.

Original languageEnglish (US)
Pages (from-to)685-703
Number of pages19
JournalPsychometrika
Volume74
Issue number4
DOIs
StatePublished - Dec 1 2009
Externally publishedYes

Fingerprint

Neighborhood Search
Binary relation
Equivalence relation
Clique
Cluster Analysis
Partitioning
Taboo
Clustering
Heuristics
Tabu search
Tabu Search
Search Algorithm
Costs and Cost Analysis
Attribute
Relocation
Social sciences
Social Sciences
Tabu Search Algorithm
Simulated annealing
Costs

Keywords

  • Clique partitioning
  • Clustering
  • Equivalence relation
  • Heuristics
  • Neighborhood search
  • Simulated annealing
  • Tabu search

ASJC Scopus subject areas

  • Psychology(all)
  • Applied Mathematics

Cite this

Clustering qualitative data based on binary equivalence relations : Neighborhood search heuristics for the clique partitioning problem. / Brusco, Michael J.; Köhn, Hans Friedrich.

In: Psychometrika, Vol. 74, No. 4, 01.12.2009, p. 685-703.

Research output: Contribution to journalArticle

@article{16ebce609d32469aac95e951a9c3829f,
title = "Clustering qualitative data based on binary equivalence relations: Neighborhood search heuristics for the clique partitioning problem",
abstract = "The clique partitioning problem (CPP) requires the establishment of an equivalence relation for the vertices of a graph such that the sum of the edge costs associated with the relation is minimized. The CPP has important applications for the social sciences because it provides a framework for clustering objects measured on a collection of nominal or ordinal attributes. In such instances, the CPP incorporates edge costs obtained from an aggregation of binary equivalence relations among the attributes. We review existing theory and methods for the CPP and propose two versions of a new neighborhood search algorithm for efficient solution. The first version (NS-R) uses a relocation algorithm in the search for improved solutions, whereas the second (NS-TS) uses an embedded tabu search routine. The new algorithms are compared to simulated annealing (SA) and tabu search (TS) algorithms from the CPP literature. Although the heuristics yielded comparable results for some test problems, the neighborhood search algorithms generally yielded the best performances for large and difficult instances of the CPP.",
keywords = "Clique partitioning, Clustering, Equivalence relation, Heuristics, Neighborhood search, Simulated annealing, Tabu search",
author = "Brusco, {Michael J.} and K{\"o}hn, {Hans Friedrich}",
year = "2009",
month = "12",
day = "1",
doi = "10.1007/s11336-009-9126-z",
language = "English (US)",
volume = "74",
pages = "685--703",
journal = "Psychometrika",
issn = "0033-3123",
publisher = "Springer New York",
number = "4",

}

TY - JOUR

T1 - Clustering qualitative data based on binary equivalence relations

T2 - Neighborhood search heuristics for the clique partitioning problem

AU - Brusco, Michael J.

AU - Köhn, Hans Friedrich

PY - 2009/12/1

Y1 - 2009/12/1

N2 - The clique partitioning problem (CPP) requires the establishment of an equivalence relation for the vertices of a graph such that the sum of the edge costs associated with the relation is minimized. The CPP has important applications for the social sciences because it provides a framework for clustering objects measured on a collection of nominal or ordinal attributes. In such instances, the CPP incorporates edge costs obtained from an aggregation of binary equivalence relations among the attributes. We review existing theory and methods for the CPP and propose two versions of a new neighborhood search algorithm for efficient solution. The first version (NS-R) uses a relocation algorithm in the search for improved solutions, whereas the second (NS-TS) uses an embedded tabu search routine. The new algorithms are compared to simulated annealing (SA) and tabu search (TS) algorithms from the CPP literature. Although the heuristics yielded comparable results for some test problems, the neighborhood search algorithms generally yielded the best performances for large and difficult instances of the CPP.

AB - The clique partitioning problem (CPP) requires the establishment of an equivalence relation for the vertices of a graph such that the sum of the edge costs associated with the relation is minimized. The CPP has important applications for the social sciences because it provides a framework for clustering objects measured on a collection of nominal or ordinal attributes. In such instances, the CPP incorporates edge costs obtained from an aggregation of binary equivalence relations among the attributes. We review existing theory and methods for the CPP and propose two versions of a new neighborhood search algorithm for efficient solution. The first version (NS-R) uses a relocation algorithm in the search for improved solutions, whereas the second (NS-TS) uses an embedded tabu search routine. The new algorithms are compared to simulated annealing (SA) and tabu search (TS) algorithms from the CPP literature. Although the heuristics yielded comparable results for some test problems, the neighborhood search algorithms generally yielded the best performances for large and difficult instances of the CPP.

KW - Clique partitioning

KW - Clustering

KW - Equivalence relation

KW - Heuristics

KW - Neighborhood search

KW - Simulated annealing

KW - Tabu search

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

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

U2 - 10.1007/s11336-009-9126-z

DO - 10.1007/s11336-009-9126-z

M3 - Article

AN - SCOPUS:77949264354

VL - 74

SP - 685

EP - 703

JO - Psychometrika

JF - Psychometrika

SN - 0033-3123

IS - 4

ER -