Optimal combination of nested clusters by a greedy approximation algorithm

Edward K.F. Dang, Wing Pong Robert Luk, Dik Lun Lee, Kei Shiu Ho, Stephen C.F. Chan

Research output: Journal article publicationJournal articleAcademic researchpeer-review


Given a set of clusters, we consider an optimization problem which seeks a subset of clusters that maximizes the microaverage F-measure. This optimal value can be used as an evaluation measure of the goodness of clustering. For arbitrarily overlapping clusters, finding the optimal value is NP-hard. We claim that a greedy approximation algorithm yields the global optimal solution for clusters that overlap only by nesting. We present a mathematical proof of this claim by induction. For a family of n clusters containing a total of N objects, this algorithm has an O(n2}) time complexity and O(N) space complexity.
Original languageEnglish
Pages (from-to)2083-2087
Number of pages5
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Issue number11
Publication statusPublished - 21 Aug 2009


  • Classification
  • Clustering
  • Optimization
  • Performance evaluation

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computational Theory and Mathematics
  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Optimal combination of nested clusters by a greedy approximation algorithm'. Together they form a unique fingerprint.

Cite this