报告题目：A Unified Framework for Clustering Constrained Data without Locality Property

报告人：Jinhui Xu (徐金辉) 教授（State University of New York at Buffalo）

时间：2016年7月18日上午9:30-10:30

地点：天赐庄校区理工楼633室

报告摘要：In this paper, we consider a class of constrained clustering problems of points in Rd space, where d could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of

locality, we present in this paper a unified framework, called Peeling-and-Enclosing, to iteratively solve two variants of the constrained clustering problems, constrained k-means clustering (k-CMeans) and constrained k-median clustering (k-CMedian). Our framework generalizes Kumar et al.’s elegant k-means clustering approach [35] from unconstrained data to constrained data, and is based on two standalone geometric techniques, called Simplex Lemma and Weaker Simplex Lemma, for k-CMeans and k-CMedian, respectively. Simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent of the dimensionality of the space, in a simplex (or the surrounding region of a simplex), and thus can be used to handle high dimensional data. With these techniques, our framework generates, in nearly linear time (i.e., O(n(log n) k+1d)), O((log n) k) k-tuple candidates for the k mean or median points, and one of them induces a (1 +ε)-approximation for k-CMeans or k-CMedian, where n is the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the best k-tuple candidate), we obtain a (1 +ε)-approximation for each of the constrained clustering problems. Our framework improves considerably the best known results for these problems. We expect that our technique will be applicable to other constrained clustering problems without locality.

 报告人介绍：Dr. Xu is currently a professor of Computer Science and Engineering at the University at Buffalo (the State University of  New York). He received his B.S. and M.S. degrees in Computer Science from the University of Science and Technology of China (USTC), and his Ph.D. degree in Computer Science and Engineering from the University of Notre Dame in 2000. Dr. Xu's research interest lies in the fields of Algorithms, Computational Geometry, Combinatorial Optimization, Machine Learning, and their applications in several applied areas. His recent research has focused on the development of geometric algorithms and machine learning methods for problems arising in medicine (medical imaging and interventional procedures for intracranial aneurysms), biology (determining the spatial patterns of chromosome organization inside the cell nucleus, as well as their alterations in cell differentiation, cell cycle, and progression of diseases such as cancer), networking, and 3D printing. Dr. Xu's research has been supported by National Science Foundation (NSF), National Institute of Health (NIH), NYSTAR, IBM, and University at Buffalo. He is a recipient of UB Exceptional Scholar: Sustained Achievement Award (2015), SEAS Senior Researcher of the Year Award (2015), the NSF CAREER Award (2005) and the IBM Faculty Partnership Award (2001).