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: |
| id |
I19-R120-10915-141773 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Español |
| topic |
Ciencias Informáticas Programación lineal entera Clustering |
| spellingShingle |
Ciencias Informáticas Programación lineal entera Clustering Marenco, Javier Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| topic_facet |
Ciencias Informáticas Programación lineal entera Clustering |
| description |
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. |
| format |
Objeto de conferencia Resumen |
| author |
Marenco, Javier |
| author_facet |
Marenco, Javier |
| author_sort |
Marenco, Javier |
| title |
Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| title_short |
Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| title_full |
Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| title_fullStr |
Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| title_full_unstemmed |
Modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| title_sort |
modelos de programación lineal entera para el problema de clustering con regiones hiper-rectangulares y outliers |
| publishDate |
2021 |
| url |
http://sedici.unlp.edu.ar/handle/10915/141773 http://50jaiio.sadio.org.ar/pdfs/siiio/SIIIO-18.pdf |
| work_keys_str_mv |
AT marencojavier modelosdeprogramacionlinealenteraparaelproblemadeclusteringconregioneshiperrectangularesyoutliers |
| bdutipo_str |
Repositorios |
| _version_ |
1764820459739676675 |