El problema de -means consiste en calcular un conjunto de centros (puntos) que minimice la suma de distancias al cuadrado a un conjunto dado de puntos en un espacio métrico. Argumentablemente, el algoritmo más común para resolverlo es -means++ que es fácil de implementar y proporciona un error de aproximación pequeño demostrable en un tiempo que es lineal en . Generalizamos -means++ para admitir valores atípicos en dos sentidos (simultáneamente): (i) en espacios no métricos, por ejemplo, M-estimadores, donde la distancia entre un punto y un centro se reemplaza por una constante apropiada que puede depender de la escala de la entrada. (ii) agrupación de -means con valores atípicos, es decir, donde los puntos más alejados de cualquier centro dado se excluyen de la suma total de distancias. Esto se logra mediante una reducción simple a la agrupación de -means (sin valores atípicos).