Diseño e implementación de un algoritmo de aglomeraciones no sensible a valores atípicos 

Raymundo Domínguez Colín

            
Texto completo de la Tesis    



Resumen

El problema de análisis de aglomeraciones (cluster analysis) ha estado abierto por décadas. Los algoritmos de aglomeración que se han desarrollado tales como el k medias, c-medias difuso entre otros, proponen diversos metodologías para tratar este problema. A la fecha aún no existe una solución óptima que funcione para todos los problemas de aglomeración. Uno de los factores que más afectan el desempeño de estos algoritmos es la presencia de valores atípicos (outliers). Los valores atípicos son muestras que numéricamente no pertenecen al conjunto de datos. Siempre se requiere remover los valores atípicos de un conjunto de datos para que un algoritmo de aglomeración funcione correctamente. En la literatura se ha tratado el problema de los valores atípicos con una metodología llamada aglomeración de ruido (noise clustering). En ésta se considera una entidad conocida como aglomerado de ruido, separada de todos los datos de un conjunto por medio de una distancia de ruido (noise distance).

Uno de los principales problemas de este método es que considera que el aglomerado de ruido es equidistante a todos los puntos, es decir, que la distancia de ruido que los separa es la misma, pero ésta no es una apreciación realista. En esta tesis se proponen algunas variantes al método de aglomerado de ruido. Entre estas variantes se maneja una manera distinta de estimar la distancia de ruido y se proponen nuevas ideas para desarrollar este tipo de algoritmos. Nuestro método fue validado con muchas pruebas sobre diferentes conjuntos de datos. Se ha desarrollado una aplicación de este método sobre un problema de la vida real.

          Abstract

The problem of cluster analysis has been open for many decades. Clustering algorithms as k-means; Fuzzyc-means among others, propose diverse methodologies to solve this problem. To date there does not exist an optimal solution that works for all kind of clustering problems. One of the causes that affect the performance of clustering algorithms is the presence of outliers. The outliers are points which are numerically distant from the rest of the data. In order to make a clustering algorithm works properly, it is necesary to remove the outliers from the data set. In the literature the problem of outliers have been treated with a specific methodology called noise clustering. Where it is assume the existance of a separate noise cluster and also there is a noise distance from the noise cluster to all data points.

One of the main drawbacks of the previous methods was that they assume that the noise prototype is equidistant from all data points, i.e., the noise distance is the same for all data. This assumption is unrealistic. In this thesis we propose several variants of noise clustering. We propose a new noise distance which does not suffer from this unrealistic assumption. In this thesis we propose some variants to this noise cluster method. We handle a new noise distance and further propose new ideas to develop this kind of algorithms. We provide extensive simulations on different data sets. Finally we describe an application of the new algorithm in a real life problem.