Improving clustering with pairwise constraints: A discriminative approach

Hong Zeng*, Aiguo Song, Yiu Ming CHEUNG

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

4 Citations (Scopus)


To obtain a user-desired and accurate clustering result in practical applications, one way is to utilize additional pairwise constraints that indicate the relationship between two samples, that is, whether these samples belong to the same cluster or not. In this paper, we put forward a discriminative learning approach which can incorporate pairwise constraints into the recently proposed two-class maximum margin clustering framework. In particular, a set of pairwise loss functions is proposed, which features robust detection and penalization for violating the pairwise constraints. Consequently, the proposed method is able to directly find the partitioning hyperplane, which can separate the data into two groups and satisfy the given pairwise constraints as much as possible. In this way, it makes fewer assumptions on the distance metric or similarity matrix for the data, which may be complicated in practice, than existing popular constrained clustering algorithms. Finally, an iterative updating algorithm is proposed for the resulting optimization problem. The experiments on a number of real-world data sets demonstrate that the proposed pairwise constrained two-class clustering algorithm outperforms several representative pairwise constrained clustering counterparts in the literature.

Original languageEnglish
Pages (from-to)489-515
Number of pages27
JournalKnowledge and Information Systems
Issue number2
Publication statusPublished - Aug 2013

Scopus Subject Areas

  • Software
  • Information Systems
  • Human-Computer Interaction
  • Hardware and Architecture
  • Artificial Intelligence

User-Defined Keywords

  • Discriminative approach
  • Maximum margin clustering
  • Pairwise constraints
  • Robust pairwise loss function


Dive into the research topics of 'Improving clustering with pairwise constraints: A discriminative approach'. Together they form a unique fingerprint.

Cite this