Please use this identifier to cite or link to this item: http://inaoe.repositorioinstitucional.mx/jspui/handle/1009/806
Escalamiento multidimensional sobre datos mezclados usando algoritmos genéticos
PEDRO TECUANHUEHUE VERA
JESUS ARIEL CARRAZCO OCHOA
JOSE FRANCISCO MARTINEZ TRINIDAD
Acceso Abierto
Atribución-NoComercial-SinDerivadas
Multidimensional scalling
Genetic algorithms
Divide and conquer methods
Heterogeneous databases
This work introduces a genetic algorithm that aims to make multidimensional scaling over mixed and incomplete data. Multidimensional scaling attempts to represent, on the Euclidean plane, objects that are in high-dimensional spaces, trying to keep as much as possible the distances among the original objects. Multidimensional scaling aims to display on the Euclidean plane the structure that objects in the original space keep. Current algorithms make multidimensional scaling over numerical data sets using classical optimization techniques, which easily fall into local optima. This work presents a genetic algorithm, AGP, to make multidimensional scaling over mixed and incomplete data, and a divide and conquer strategy, AGPG, that can process large data sets of objects. AGP aims to better explore the solutions space in order to find better representations of the original objects on the Euclidean plane. The AGP algorithm uses mutation and crossover operations introduced in this thesis, which were specifically designed for the problem of multidimensional scaling. In addition, to accelerate the search and to allow finding good solutions in fewer generations, we designed a strategy for creating an initial population, which is based on generating two-dimensional projections of the original objects. The divide and conquer strategy, AGPG, to make multidimensional scaling over mixed and incomplete data arises from the need to accelerate the search of good representations for large datasets. The AGP algorithm can find better solutions than the AGPG strategy, however, AGPG may find appropriate solutions faster than the AGP algorithm. The AGPG strategy divides the original dataset into smaller groups and make multidimensional scaling using the AGP algorithm on each group. To find a global representation of the large data set, AGPG positioned representations of each smaller group using the representation obtained from a dataset constructed from a small sample of each group of the partition. The results of our AGP algorithm and AGPG strategy have been compared against the results obtained by MDSCAL algorithm [Kru64b], for which we have used some databases from UCI repository [Mer98], as well as different values for some of the parameters used by our algorithms. From these experiments we found that for mixed and incomplete databases our AGP algorithm find better representations that the AGPG strategy and the MDSCAL and ISOMAP algorithms.
En el presente trabajo se introduce un algoritmo genético que tiene por objetivo realizar escalamiento multidimensional sobre conjuntos de datos mezclados e incompletos. El escalamiento multidimensional busca representar sobre el plano Euclidiano a objetos que se encuentren en espacios de alta dimensión, tratando de mantener lo mejor posible las distancias que existen entre los objetos originales. El escalamiento multidimensional tiene por objetivo visualizar sobre el plano Euclidiano la estructura que mantienen los objetos en el espacio original. Los algoritmos existentes realizan escalamiento multidimensional sobre conjuntos de datos numéricos, utilizando técnicas clásicas de optimización las cuales pueden caer fácilmente en óptimos locales. En este trabajo se presenta un algoritmo genético (AGP) para realizar escalamiento multidimensional sobre datos mezclados e incompletos y una estrategia de tipo divide y vencerás (AGPG) que permite procesar conjuntos grandes de objetos. Con el algoritmo genético AGP se busca explorar mejor el espacio de soluciones para encontrar mejores representaciones de los objetos originales sobre el plano Euclidiano. El algoritmo AGP hace uso de operaciones de mutación y cruza introducidas en este trabajo; las cuales fueron diseñadas específicamente para el problema de escalamiento multidimensional. Además, para acelerar la búsqueda y permitir encontrar buenas soluciones en menos generaciones, se diseñó una estrategia para la creación de una población inicial, la cual está basada en generar proyecciones bidimensionales de los objetos originales. La estrategia de tipo divide y vencerás para realizar escalamiento multidimensional sobre datos mezclados e incompletos, AGPG, surge debido a la necesidad de acelerar la búsqueda de soluciones para conjuntos grandes de datos. El algoritmo AGP puede encontrar mejores soluciones que la estrategia AGPG, sin embargo, AGPG puede encontrar soluciones adecuadas más rápidamente que el algoritmo AGP en conjuntos grandes de datos. La estrategia AGPG consiste en dividir el conjunto de datos originales en grupos de menor tamaño y realizar escalamiento multidimensional mediante el algoritmo AGP sobre cada grupo obtenido. Para encontrar una representación global del conjunto grande de datos, AGPG posiciona las representaciones de cada grupo de menor tamaño usando una representación obtenida a partir de un conjunto construido con una pequeña muestra de cada grupo de la partición.
Instituto Nacional de Astrofísica, Óptica y Electrónica
2013-01
Tesis de maestría
Español
Estudiantes
Investigadores
Público en general
Tecuanhuehue-Vera P.
CIENCIA DE LOS ORDENADORES
Versión aceptada
acceptedVersion - Versión aceptada
Appears in Collections:Maestría en Ciencias Computacionales

Upload archives


File SizeFormat 
TecuanhuehueVP.pdf1.67 MBAdobe PDFView/Open