2018/10/02 by Hu Ding, Ding, Hu, Jinhui Xu +1
Business, Management and Accounting · Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #Facility Location and Emergency Management #Machine Learning (cs.LG)
paper · pdf · doi:10.48550/arxiv.1810.01049
openalex publication_date 2018/10/02 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
In this paper, we consider a class of constrained clustering problems of points in ℝd, 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 \em Peeling-and-Enclosing (PnE), to iteratively solve two variants of the constrained clustering problems, \em constrained k-means clustering (k-CMeans) and \em constrained k-median clustering (k-CMedian). Our framework is based on two standalone geometric techniques, called \em Simplex Lemma and \em Weaker Simplex Lemma, for k-CMeans and k-CMedian, respectively. The 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. If k and \frac1ε are fixed numbers, our framework generates, in nearly linear time (\em 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. We expect that our technique will be applicable to other constrained clustering problems without locality.