language: en

Clustering via Concave Minimization

P. S. Bradley and O. L. Mangasarian W. N. Street
Computer Sciences Department Computer Science Department University of Wisconsin Oklahoma State University
1210 West Dayton Street 205 Mathematical Sciences Madison, WI 53706 Stillwater, OK 74078
email: paulb@cs.wisc.edu, olvi@cs.wisc.edu email:nstreet@cs.okstate.edu

Abstract The problem of assigning m points in the n-dimensional real space R n to k clusters is formulated as that of determining k centers in R n 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 polyhedral 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-world databases was carried out. On the Wisconsin Diagnostic Breast Cancer (WDBC) database, k-Median training set correctness 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 clinically 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.

1 Introduction