Por favor, use este identificador para citar o enlazar este ítem:
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 | |
| Aparece en las colecciones: | Maestría en Ciencias Computacionales |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| TecuanhuehueVP.pdf | 1.67 MB | Adobe PDF | Visualizar/Abrir |