Un algoritmo de ramificación y poda para realizar agrupamientos óptimos

Abstract

Los algoritmos de Clustering, i.e. algoritmos para el agrupamiento de datos por su similitud en «clusters», son una de las herramientas más populares dentro del campo de la Inteligencia Artificial y la Minería de Datos. Una de las de razones de su popularidad es su simplicidad conceptual, lo que permite una formulación matemática basada en la resolución de un problema combinatorio. La heurística más utilizada en la práctica es la dada por Lloyd y es la que se basa el algoritmo k-means para encontrar los centros de masa de los diferentes «clusters». Aunque el algoritmo es a la vez sencillo de implementar y eficiente, un problema importante es que solo hay una garantía probabilista de que devuelva una solución cercana a la óptima. Ello plantea la necesidad de encontrar algoritmos «óptimos», en otras palabras, que devuelvan siempre la solución óptima para un conjunto de datos de entrada. Aunque se sabe que este problema es NP-duro, la investigación de nuevos algoritmos óptimos ayuda a entender el comportamiento y las limitaciones de k-means y sus variantes. Este trabajo propone varias mejoras algorítmicas para resolver el problema de optimización, centrándonos dentro del paradigma de programación conocido como ramificación y poda. Los experimentos computacionales que hemos realizado con nuestra implementación en Sage muestran una mejora con respecto a la implementación del mejor algoritmo óptimo conocido.

Clustering (partitioning a set into different subsets) is among the most widely used type of algorithms for unstructured data. Its popularity comes from the simple basis behind it which often means solving a combinatorial problem of finding the minimum of an objective function. The most popular clustering algorithm in practice is Lloyd’s heuristic approximation algorithm to the k-means optimum centroids. A crucial issue of this approach is that there is only a probabilistic guarantee regarding the goodness of the solution. Indeed, it is possible to construct datasets where Lloyd’s heuristic approximation algorithm only finds local minimums. A challenging problem is finding the global optimum for any given dataset. Although this problem is NP-hard, new algorithms for finding optimal clustering offer many benefits for the research of new heuristic algorithms. This work analyses possible improvements for solving this problem, focusing on optimizing the global searches with branch-andbound techniques. The numerical results show a promising computational advantage for the case of the partitioning of two sets over previous proposals.