Aplicaciones de la programación matemática a la selección de variables en algunos problemas de clasificación

Abstract

Whether for how individuals are distributed in a population or recognize factors that cause diseases, classification is one of the fundamental objectives in science. Recognize patterns having a group of individuals (or objects) and makes them similar has various applications in other fields such as medicine, psychology, economics, marketing, engineering ... Since centuries is studied the science of classification, known as taxonomy, in order to gain a better understanding of the world in which we live. In this paper, Cluster analysis is proposed as a method for classifying individuals or entities characterized by a number of features. Given a set of entities, Cluster Analysis aims at finding subsets, called clusters, which are homogeneous and/or well separated. As many types of clustering and criteria for homogeneity or separation are of interest, this is a vast field. A survey is given from a mathematical programming viewpoint. However, this is not the main purpose of it. Cluster Analysis process goes through a pre-selection of variables that significantly affect the outcome of the analysis. Clustering high-dimensional data is a difficult task if data contain variables with no relevant information. When those variables are not detected and discarded from the analysis, the analysis is blurred and biased by their presence. The problem becomes more and more important as the the number of variables increases. Because of this, we need algorithms that select the important variables and eliminate those that adversely affect the clustering process. This previous process is known as Variable Selection, and it is formulated as a linear optimization problem with binary variables representing the 0-1 decision of rejecting or selecting. The search of the subset of variables is a NP-hard problem (Kohavi, 1995), so that the use of metaheuristics obtains solutions without the need to explore the whole space of solutions.Therefore, it is useful to apply mathematical programming to address these problems. In this paper, we propose a mathematical programming viewpoint for Analysis Cluster and Variable Selection, besides certain models thereof.

Tanto por conocer la distribución de individuos en una población o reconocer los factores que causan enfermedades, la clasificación es uno de los objetivos fundamentales de la ciencia. Reconocer los patrones que tienen un grupo de individuos (u objetos) y los hace similares tiene diversas aplicaciones en campos como la medicina, la psicología, la economía, marketing, ingeniería... Durante siglos se ha estudiado la ciencia de la clasificación, conocida como Taxonomía, con el fin de obtener una mejor comprensión del mundo en que vivimos. En este trabajo, el Análisis Cluster (Análisis de Conglomerados) se propone como método para la clasificación de personas o entidades que se caracterizan por una serie de variables. Dado un conjunto de entidades, Análisis Cluster tiene como objetivo la búsqueda de subconjuntos, llamados clusters, que son homogéneas y/o se encuentren bien separados. Existen muchos tipos de agrupación y diversos criterios de homogeneidad o separación son de interés, haciendo de éste un campo amplio. Sin embargo, este no es el propósito principal del mismo. El proceso de análisis de cluster pasa por un previo proceso de selección de las variables que afectan de manera significativa el resultado del análisis. La agrupación de los datos de alta dimensión es una tarea difícil si los datos contienen variables con poca o ninguna información relevante. Cuando no se detectan y descartan el análisis se ve influenciado por su presencia. Este problema se vuelve más y más importante según se hace aumentar el número de variables. Es por esto que se necesitan algoritmos que seleccionen las variables importantes y eliminen aquellas que afecten negativamente el proceso de clasificación. Este proceso previo se conoce como selección de variables, y se formula como un problema de optimización lineal con variables binarias que representan mediante 0-1 la decisión de rechazar o seleccionar. La búsqueda del subconjunto de variables es un problema NP-duro (Kohavi, 1995), por lo que el uso de metaheurísticas obtiene soluciones sin la necesidad de explorar todo el espacio de soluciones. Por lo tanto, es útil aplicar la programación matemática para abordar estos problemas. En este trabajo, se propone un enfoque basado en programación matemática para el Análisis Cluster y selección de variables, junto con ciertos modelos de ambos.