Novel biobjective clustering (BiGC) based on cooperative game theory

Vikas K. Garg*, Y. Narahari, Murty Narasimha

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

32 Citations (Scopus)


We propose a new approach to clustering. Our idea is to map cluster formation to coalition formation in cooperative games, and to use the Shapley value of the patterns to identify clusters and cluster representatives. We show that the underlying game is convex and this leads to an efficient biobjective clustering algorithm that we call BiGC. The algorithm yields high-quality clustering with respect to average point-to-center distance (potential) as well as average intracluster point-to-point distance (scatter). We demonstrate the superiority of BiGC over state-of-the-art clustering algorithms (including the center based and the multiobjective techniques) through a detailed experimentation using standard cluster validity criteria on several benchmark data sets. We also show that BiGC satisfies key clustering properties such as order independence, scale invariance, and richness.

Original languageEnglish
Article number6175898
Pages (from-to)1070-1082
Number of pages13
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number5
Publication statusPublished - 2013
MoE publication typeA1 Journal article-refereed


  • (k)-means
  • clustering
  • Cooperative game theory
  • multiobjective optimization
  • Shapley value


Dive into the research topics of 'Novel biobjective clustering (BiGC) based on cooperative game theory'. Together they form a unique fingerprint.

Cite this