Clustering with Constraints: Feasibility Issues and the k-Means Algorithm
Clustering with Constraints: Feasibility Issues and the k-Means Algorithm
复制标题
DOI：
10.1137/1.9781611972757.13
复制
发表时间：
2005
影响因子：
2.3
通讯作者：
I. Davidson;S. Ravi
中科院分区：
文献类型：
--
作者：
I. Davidson;S. Ravi
最近的工作着眼于扩展k-Means算法，以实例级必须链接和不能链接约束的形式纳入背景信息。我们介绍了两种方式来指定额外的背景信息的δ和约束的形式，操作所有的实例，但可以被解释为实例级约束的合取或析取，因此很容易实现。我们提出的复杂性结果的可行性聚类下每种类型的约束单独和几种类型在一起。一个关键的发现是，确定是否有一个可行的解决方案，满足所有的约束，一般来说，NP完全。因此，像k-Means这样的迭代算法不应该在每次迭代时都试图找到一个可行的划分。这促使我们推导出一个新版本的k-Means算法，该算法最大限度地减少了受约束的矢量量化误差，但在每次迭代时并不试图满足所有约束。使用标准的UCI数据集，我们发现使用约束可以提高精度，正如其他人所报道的那样，但我们也表明我们的算法减少了迭代次数，直到收敛。最后，我们说明了这些好处和我们的新的约束类型上的一个复杂的真实的世界的物体识别问题，使用红外探测器的爱宝机器人。
Recent work has looked at extending the k-Means algorithm to incorporate background information in the form of instance level must-link and cannot-link constraints. We introduce two ways of specifying additional background information in the form of δ and constraints that operate on all instances but which can be interpreted as conjunctions or disjunctions of instance level constraints and hence are easy to implement. We present complexity results for the feasibility of clustering under each type of constraint individually and several types together. A key finding is that determining whether there is a feasible solution satisfying all constraints is, in general, NP-complete. Thus, an iterative algorithm such as k-Means should not try to find a feasible partitioning at each iteration. This motivates our derivation of a new version of the k-Means algorithm that minimizes the constrained vector quantization error but at each iteration does not attempt to satisfy all constraints. Using standard UCI datasets, we find that using constraints improves accuracy as others have reported, but we also show that our algorithm reduces the number of iterations until convergence. Finally, we illustrate these benefits and our new constraint types on a complex real world object identification problem using the infra-red detector on an Aibo robot.