Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/64466
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.
URI: http://hdl.handle.net/10397/64466
ISSN: 0162-8828
EISSN: 1939-3539
DOI: 10.1109/TPAMI.2009.75
Appears in Collections:Journal/Magazine Article

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

Page view(s)

24
Last Week
1
Last month
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



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