Optimal combination of nested clusters by a greedy approximation algorithm.
Where this comes from
- Record sourced from PubMed, PMID 19762933.
- Also identified by DOI 10.1109/TPAMI.2009.75.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
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.
Medical subject headings
- Algorithms
- Artificial Intelligence
- Decision Support Techniques
- Models, Theoretical
- Pattern Recognition, Automated