Clustering via Concave Minimization
Abstract
The problem of assigning m points in the n-dimensional real space Rn to k clusters is formulated as that of determining k centers in Rn such that the sum of distances of each point to the nearest center is minimized. If a polyhedral distance is used, the problem can be formulated as that of minimizing a piecewise-linear concave function on a polyhedral set which is shown to be equivalent to a bilinear program: minimizing a bilinear function on a polyhe(cid:173) dral set. A fast finite k-Median Algorithm consisting of solving few linear programs in closed form leads to a stationary point of the bilinear program. Computational testing on a number of real(cid:173) world databases was carried out. On the Wisconsin Diagnostic Breast Cancer (WDBC) database, k-Median training set correct(cid:173) ness was comparable to that of the k-Mean Algorithm, however its testing set correctness was better. Additionally, on the Wisconsin Prognostic Breast Cancer (WPBC) database, distinct and clini(cid:173) cally important survival curves were extracted by the k-Median Algorithm, whereas the k-Mean Algorithm failed to obtain such distinct survival curves for the same database.
Cite
Text
Bradley et al. "Clustering via Concave Minimization." Neural Information Processing Systems, 1996.Markdown
[Bradley et al. "Clustering via Concave Minimization." Neural Information Processing Systems, 1996.](https://mlanthology.org/neurips/1996/bradley1996neurips-clustering/)BibTeX
@inproceedings{bradley1996neurips-clustering,
title = {{Clustering via Concave Minimization}},
author = {Bradley, Paul S. and Mangasarian, Olvi L. and Street, W. Nick},
booktitle = {Neural Information Processing Systems},
year = {1996},
pages = {368-374},
url = {https://mlanthology.org/neurips/1996/bradley1996neurips-clustering/}
}