Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers

Abstract

Dado un conjunto X de puntos en Rd y un entero k, el problema de clustering con regiones hiper-rectangulares consiste en determinar k hiper-rectángulos en Rd con el menor volumen posible de modo tal que cada punto de X esté incluido en al menos un hiper-rectángulo. Si además se especifica una cantidad p de posibles outliers, entonces se pueden tener hasta p puntos de X no incluidos en ningún hiper-rectángulo. Las técnicas de clustering con hiper-rectángulos han sido propuestas como una alternativa de clustering interpretable, dado que es sencillo explicar los clusters obtenidos en función de sus límites. Existen métodos geométricos para este problema, y también se han explorado alternativas basadas en programación lineal entera para variantes de este problema. En todos estos trabajos se asume p = 0. En este trabajo estudiamos el problema de clustering con regiones hiper- rectangulares con una linealización de la función objetivo y para el caso p > 0. Es decir, se puede descartar una cantidad prefijada de puntos, que son declarados como outliers. Presentamos un modelo natural de programación lineal entera para este problema y estudiamos el poliedro asociado. Además, consideramos un esquema heurístico basado en generación de columnas, y presentamos experimentos computacionales para comparar los dos esquemas.