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

Keywords

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

ASJC Scopus subject areas

  • Psychology(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Clustering qualitative data based on binary equivalence relations: Neighborhood search heuristics for the clique partitioning problem'. Together they form a unique fingerprint.

  • Cite this