标题：部分k-means避免异常值的影响，数学规划形式和复杂度分析摘要： Min-Sum-of-Square Clustering (MSSC，即著名的$k$-means问题)的一个著名瓶颈是解决异常值的影响。本文提出一种部分聚类变量——PMSSC，该算法考虑设置一定数量的异常值来删除。我们通过整数规划形式和复杂性分析来解决PMSSC，这一部分扩展了MSSC的相应研究。当维度或聚类数大于2时，PMSSC在欧几里得空间中是NP难题。最后，我们研究了一维情况：非加权的PMSSC在此情况下是多项式复杂度，并通过动态规划算法进行求解，扩展了区间聚类的MSSC最优性质。在此情况下，非加权的$k$-medoids也具有异常值和最优性质。加权的PMSSC具有较弱的最优性质，在一维情况下，NP难度或者不是NP难问题仍然是一个开放性问题。 (Partial k-means to avoid outliers, mathematical programming formulations, complexity results)

翻译：标题：部分k-means避免异常值的影响，数学规划形式和复杂度分析摘要： Min-Sum-of-Square Clustering (MSSC，即著名的$k$-means问题)的一个著名瓶颈是解决异常值的影响。本文提出一种部分聚类变量——PMSSC，该算法考虑设置一定数量的异常值来删除。我们通过整数规划形式和复杂性分析来解决PMSSC，这一部分扩展了MSSC的相应研究。当维度或聚类数大于2时，PMSSC在欧几里得空间中是NP难题。最后，我们研究了一维情况：非加权的PMSSC在此情况下是多项式复杂度，并通过动态规划算法进行求解，扩展了区间聚类的MSSC最优性质。在此情况下，非加权的$k$-medoids也具有异常值和最优性质。加权的PMSSC具有较弱的最优性质，在一维情况下，NP难度或者不是NP难问题仍然是一个开放性问题。

Nicolas Dupin,Frank Nielsen

A well-known bottleneck of Min-Sum-of-Square Clustering (MSSC, the celebrated $k$-means problem) is to tackle the presence of outliers. In this paper, we propose a Partial clustering variant termed PMSSC which considers a fixed number of outliers to remove. We solve PMSSC by Integer Programming formulations and complexity results extending the ones from MSSC are studied. PMSSC is NP-hard in Euclidean space when the dimension or the number of clusters is greater than $2$. Finally, one-dimensional cases are studied: Unweighted PMSSC is polynomial in that case and solved with a dynamic programming algorithm, extending the optimality property of MSSC with interval clustering. This result holds also for unweighted $k$-medoids with outliers. A weaker optimality property holds for weighted PMSSC, but NP-hardness or not remains an open question in dimension one.

翻译：