A Unified Framework for Clustering Constrained Data Without Locality Property
A Unified Framework for Clustering Constrained Data Without Locality Property
复制标题
DOI：
10.1007/s00453-019-00616-2
复制
发表时间：
2015-01
期刊：
影响因子：
1.1
通讯作者：
Hu Ding;Jinhui Xu
中科院分区：
文献类型：
--
作者：
Hu Ding;Jinhui Xu
在这篇文章中，我们考虑了中的一类点的约束聚类问题，其中可能是相当高的。这些问题的一个共同特征是，它们的最优聚类不再具有局部性属性(由于附加的约束)，而局部性属性是许多算法对其无约束的对等算法所要求的关键属性。为了克服局部性丢失带来的困难，本文提出了一个称为剥离和包围的统一框架来迭代地解决约束k-均值聚类(k-CMeans)和约束k-中值聚类(k-CMedian)这两种约束聚类问题。我们的框架将Kumar等人(J ACM 57(2)：5,2010)的Elegantk-Means聚类方法从无约束数据推广到有约束数据，并基于两种独立的几何技术，分别称为单纯形引理和Weaker单纯形引理，Fork-CMeans和k-CMedian。单纯形引理(或较弱单纯形引理)使我们能够通过在单纯形(或单纯形的周围区域)中搜索独立于空间维度的小尺寸网格来有效地逼近未知点集合的平均值(或中值)点，从而可用于处理高维数据。如果kand是固定的数，我们的框架在近线性的时间内(即，)产生k-均值或中点的k-字节组候选者，其中之一诱导a-近似分叉-CMeans或k-CMedian，其中是点数。结合这个统一的框架和特定于问题的选择算法(确定最佳元组候选)，我们得到了每个约束聚类问题的-近似。我们的框架大大改进了解决这些问题的最著名的结果。我们期望我们的技术将适用于其他变体的K-均值和k-中值聚类问题，而不需要局部性。
In this paper, we consider a class of constrained clustering problems of points in, wheredcould 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, calledPeeling-and-Enclosing, to iteratively solve two variants of the constrained clustering problems,constrained k-means clustering(k-CMeans) andconstrained k-median clustering(k-CMedian). Our framework generalizes Kumar et al.’s (J ACM 57(2):5, 2010) elegantk-means clustering approach from unconstrained data to constrained data, and is based on two standalone geometric techniques, calledSimplex LemmaandWeaker Simplex Lemma, fork-CMeans andk-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. Ifkandare fixed numbers, our framework generates, in nearly linear time (i.e.,),k-tuple candidates for thekmean or median points, and one of them induces a-approximation fork-CMeans ork-CMedian, wherenis the number of points. Combining this unified framework with a problem-specific selection algorithm (which determines the bestk-tuple candidate), we obtain a-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 variants ofk-means andk-median clustering problems without locality.