Data stability in clustering: A closer look
Data stability in clustering: A closer look
复制标题
聚类中的数据稳定性：仔细观察
DOI：
10.1016/j.tcs.2014.09.025
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
L. Reyzin
中科院分区：
文献类型：
--
作者：
S. Ben;L. Reyzin
我们考虑Bilu和Linial（2010）[13]引入的模型，他们研究了当距离扰动时最优聚类不会改变的问题。他们表明，即使当一个问题是NP-难的，它有时是可能的，以获得有效的算法的实例弹性某些乘法扰动，例如在O（n）的顺序为最大割聚类。Awasthi等人（2012）[6]考虑基于中心的目标，Balcan和Liang（2012）[9]分析了k-中位数和最小和目标，为某些常数乘法扰动的实例提供了有效的算法。在这里，我们的动机是在多大程度上这些假设可以放松，同时允许有效的算法的问题。我们发现，通过为k-中位数和最小和目标提供NP-硬度下限，几乎没有改善这些结果的空间。另一方面，我们表明，常数乘法弹性参数可以如此强大，使聚类问题微不足道，只留下一个狭窄的范围内的弹性参数聚类是有趣的。我们还考虑了加性扰动模型，并给出了加性和乘性稳定性概念之间的对应关系。我们的研究结果提供了一个仔细检查的后果，假设稳定的数据。
We consider the model introduced by Bilu and Linial (2010)[13], who study problems for which the optimal clustering does not change when distances are perturbed. They show that even when a problem is NP-hard, it is sometimes possible to obtain efficient algorithms for instances resilient to certain multiplicative perturbations, eg on the order of O (n) for max-cut clustering. Awasthi et al.(2012)[6] consider center-based objectives, and Balcan and Liang (2012)[9] analyze the k-median and min-sum objectives, giving efficient algorithms for instances resilient to certain constant multiplicative perturbations. Here, we are motivated by the question of to what extent these assumptions can be relaxed while allowing for efficient algorithms. We show there is little room to improve these results by giving NP-hardness lower bounds for both the k-median and min-sum objectives. On the other hand, we show that constant multiplicative resilience parameters can be so strong as to make the clustering problem trivial, leaving only a narrow range of resilience parameters for which clustering is interesting. We also consider a model of additive perturbations and give a correspondence between additive and multiplicative notions of stability. Our results provide a close examination of the consequences of assuming stability in data.