Clustering via Concave Minimization
Paul Bradley, UW Computer Sciences
2:30 pm Fri Nov 22 2310 CS & Stats
The problem of assigning points in n-dimensional real space
to k clusters is formulated as that of determining k centers
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 a 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
from the database by the k-Median Algorithm, whereas the
k-Mean Algorithm failed to obtain such distinct survival
curves for the same database.