Algoritmo de optimización multiobjetivo para el problema center-based clustering para conjuntos con outliers

Abstract

Clustering (agrupamiento) es usualmente considerado el problema más importante del aprendizaje automático no supervisado. Al igual que los problemas no supervisados, el problema del clustering consiste en descubrir patrones de agrupamiento. En particular, se busca agrupar un conjunto de datos no etiquetados en conjuntos llamados clusters (o grupos). Dada la naturaleza del problema, este aparece en multitud de áreas de investigación como: compresión de datos, análisis de imágenes, bioinformática, y minería de datos. A la fecha, se han diseñado multitud de algoritmos y modelos de clustering. También, se ha generalizado el tipo de datos con los que se puede aplicar esta técnica. Uno de los modelos de clustering más ampliamente utilizados está relacionado con el conjunto de problemas centerbased. Este conjunto de problemas es uno de los más recientemente estudiados debido a su eficiencia con grandes cantidades de datos. En general, un problema de este tipo busca particionar el conjunto inicial de elementos tomando como base algunos elementos centrales. Con el objetivo de mejorar las técnicas actuales en esta rama; la presente investigación desarrolla y propone un nuevo algoritmo de clustering, denominado el algoritmo SSO-C. La metodología seguida para desarrollar el algoritmo consistió en la optimización de una función multiobjetivo que relaciona dos problemas formalmente definidos con el propósito de garantizar la robustez de la solución encontrada. Como búsqueda local para valores iniciales, se tomó soluciones con un cierto factor de aproximación para un problema de optimización combinatoria relacionado, el problema k-center. En la investigación también se desarrolla y propone un segundo algoritmo de clustering, denominado el algoritmo Emax. Este segundo algoritmo es derivado del caso más robusto de la función multiobjetivo. La convergencia del algoritmo Emax es demostrada. Para efectos de comparación, se tomaron los algoritmos k-means y SSO. El primero es uno de los algoritmo más utilizados para hacer clustering, y el segundo es una adaptación delalgoritmo de optimización Social Spider Optimization para clustering; ambospertenecientes al modelo center-based. Se compararon los algoritmos mencionados junto con los propuestos (SSO-C y Emax) tomando un conjunto de 6 conjuntos de datos sintéticamente generados y 7 del mundo real tomados de la literatura. Los experimentos muestran con significación estadística que los algoritmos SSO-C y Emax dan los mejores resultados entre los algoritmos comparados. Se espera que los algoritmos propuestos generen contribuciones significativas para estado del arte.