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 {\rm O}(n;{2}) time complexity and O(N) space complexity.
authors.affiliation: Department of Computing, Hong Kong Polytechnic University, Hong Kong. cskfdang@comp.polyu.edu.hk
authors.forename: Edward K F
authors.initials: EK
authors.lastname: Dang
authors.forename: Robert W P
authors.initials: RW
authors.lastname: Luk
authors.forename: D L
authors.initials: DL
authors.lastname: Lee
authors.forename: K S
authors.initials: KS
authors.lastname: Ho
authors.forename: Stephen C F
authors.initials: SC
authors.lastname: Chan
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D003198:Computer Simulation; D003661:Decision Support Techniques; D008962:Models, Theoretical; D010363:Pattern Recognition, Automated / Q000379:methods*