Please use this identifier to cite or link to this item:
Title: Optimal combination of nested clusters by a greedy approximation algorithm
Authors: Dang, KF
Luk, RWP 
Ho, KS
Lee, DL
Chan, SCF 
Issue Date: 2009
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on pattern analysis and machine intelligence, 2009, v. 31, no. 11, p. 2083-2087 How to cite?
Journal: IEEE transactions on pattern analysis and machine intelligence 
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.
ISSN: 0162-8828
EISSN: 1939-3539
DOI: 10.1109/TPAMI.2009.75
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

Last Week
Last month
Citations as of Aug 13, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.