Show simple item record

dc.contributor.authorStreet, W.N.
dc.contributor.authorBradley, P.S.
dc.contributor.authorMangasarian, O.L.
dc.date.accessioned2013-04-29T19:01:57Z
dc.date.available2013-04-29T19:01:57Z
dc.date.issued1996
dc.identifier.citation96-03en
dc.identifier.urihttp://digital.library.wisc.edu/1793/65420
dc.description.abstractThe 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 distance of each point to the nearest center in 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.en
dc.titleClustering via Concave Minimizationen
dc.typeTechnical Reporten


Files in this item

Thumbnail

This item appears in the following Collection(s)

  • Math Prog Technical Reports
    Math Prog Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record