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

doi:10.1109/TPAMI.2009.75

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 publication › Journal article › Academic research › peer-review

1 Citation (Scopus)

Abstract

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 language	English
Pages (from-to)	2083-2087
Number of pages	5
Journal	IEEE Transactions on Pattern Analysis and Machine Intelligence
Volume	31
Issue number	11
DOIs	https://doi.org/10.1109/TPAMI.2009.75
Publication status	Published - 21 Aug 2009

Keywords

Classification
Clustering
Optimization
Performance evaluation

ASJC Scopus subject areas

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

More information

10.1109/TPAMI.2009.75

Cite this

@article{1bbd7570417a4d4790316a79771b46ce,

title = "Optimal combination of nested clusters by a greedy approximation algorithm",

abstract = "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.",

keywords = "Classification, Clustering, Optimization, Performance evaluation",

author = "Dang, {Edward K.F.} and Luk, {Wing Pong Robert} and Lee, {Dik Lun} and Ho, {Kei Shiu} and Chan, {Stephen C.F.}",

year = "2009",

month = aug,

day = "21",

doi = "10.1109/TPAMI.2009.75",

language = "English",

volume = "31",

pages = "2083--2087",

journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",

issn = "0162-8828",

publisher = "IEEE Computer Society",

number = "11",

}

TY - JOUR

T1 - Optimal combination of nested clusters by a greedy approximation algorithm

AU - Dang, Edward K.F.

AU - Luk, Wing Pong Robert

AU - Lee, Dik Lun

AU - Ho, Kei Shiu

AU - Chan, Stephen C.F.

PY - 2009/8/21

Y1 - 2009/8/21

N2 - 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.

AB - 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.

KW - Classification

KW - Clustering

KW - Optimization

KW - Performance evaluation

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

U2 - 10.1109/TPAMI.2009.75

DO - 10.1109/TPAMI.2009.75

M3 - Journal article

C2 - 19762933

SN - 0162-8828

VL - 31

SP - 2083

EP - 2087

JO - IEEE Transactions on Pattern Analysis and Machine Intelligence

JF - IEEE Transactions on Pattern Analysis and Machine Intelligence

IS - 11

ER -

Optimal combination of nested clusters by a greedy approximation algorithm

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this