Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers
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 cantid...
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Español |
| Publicado: |
2021
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/141773 http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-18.pdf |
| Aporte de: |
| Sumario: | 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. |
|---|