期刊
INFORMATION AND COMPUTATION
卷 245, 期 -, 页码 165-180出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2015.09.002
关键词
Exact recovery; k-Medoids; Linear programming; Separated balls
资金
- Alfred P. Sloan Foundation
- ONR [N00014-12-1-0743]
- NSF CAREER Award
- AFOSR Young Investigator Program Award
- National Institutes of Health [R01CA163336]
For a certain class of distributions, we prove that the linear programming relaxation of k-medoids clustering - a variant of k-means clustering where means are replaced by exemplars from within the dataset-distinguishes points drawn from nonoverlapping balls with high probability once the number of points drawn and the separation distance between any two balls are sufficiently large. Our results hold in the nontrivial regime where the separation distance is small enough that points drawn from different balls may be closer to each other than points drawn from the same ball; in this case, clustering by thresholding pairwise distances between points can fail. We also exhibit numerical evidence of high-probability recovery in a substantially more permissive regime. (C) 2015 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据