| Coordination of cluster ensembles via exact methods. | |
| | |
MedLine Citation:
|
PMID: 20421664 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
We present a novel optimization-based method for the combination of cluster ensembles for the class of problems with intracluster criteria, such as Minimum-Sum-of-Squares-Clustering (MSSC). We propose a simple and efficient algorithm-called EXAMCE-for this class of problems that is inspired from a Set-Partitioning formulation of the original clustering problem. We prove some theoretical properties of the solutions produced by our algorithm, and in particular that, under general assumptions, though the algorithm recombines solution fragments so as to find the solution of a Set-Covering relaxation of the original formulation, it is guaranteed to find better solutions than the ones in the ensemble. For the MSSC problem in particular, a prototype implementation of our algorithm found a new better solution than the previously best known for 21 of the test instances of the 40-instance TSPLIB benchmark data sets used in [1], [2], and [3], and found a worse-quality solution than the best known only five times. For other published benchmark data sets where the optimal MSSC solution is known, we match them. The algorithm is particularly effective when the number of clusters is large, in which case it is able to escape the local minima found by K-means type algorithms by recombining the solutions in a Set-Covering context. We also establish the stability of the algorithm with extensive computational experiments, by showing that multiple runs of EXAMCE for the same clustering problem instance produce high-quality solutions whose Adjusted Rand Index is consistently above 0.95. Finally, in experiments utilizing external criteria to compute the validity of clustering, EXAMCE is capable of producing high-quality results that are comparable in quality to those of the best known clustering algorithms. |
| | |
Authors:
|
Ioannis T Christou |
Related Documents
:
|
15624994 - Rerouting nucleophilic substitution from the 4-position to the 2- or 6-position of 2,4-... 21853624 - Violent youth groups in indonesia: the cases of yogyakarta and nusa tenggara barat. 149004 - Tissue-puncher and loop-ligation--new aids for surgical-therapeutic pelviscopy (laparos... 10294004 - The adult training centre problem: a case study. 20728304 - Frequency and severity of challenging behaviour in people with profound intellectual an... 17951844 - Improving the design of genechip arrays by combining placement and embedding. |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: IEEE transactions on pattern analysis and machine intelligence Volume: 33 ISSN: 1939-3539 ISO Abbreviation: IEEE Trans Pattern Anal Mach Intell Publication Date: 2011 Feb |
Date Detail:
|
Created Date: 2011-04-20 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9885960 Medline TA: IEEE Trans Pattern Anal Mach Intell Country: United States |
Other Details:
|
Languages: eng Pagination: 279-93 Citation Subset: IM |
Affiliation:
|
Athens Information Technology, Paiania, Greece. ichr@ait.edu.gr |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Popping pneumothorax.
Next Document: Resolution enhancement in multi-image stereo.