Trabajo de grado - Doctorado
Generación automática de resúmenes extractivos de múltiples documentos basada en algoritmos meméticos
Date
2015-11-13Author
Mendoza Becerra, Martha Eliana
Institutions
Abstract
Recientemente los algoritmos basados en metaheurísticas han mostrado buenos resultados para generar resúmenes automáticos comparados con otros métodos del estado del arte, sin embargo, aunque los algoritmos meméticos han contribuido en la resolución de diversos problemas de optimización combinatoria con excelentes resultados, no han sido usados para resolver el problema de generación automática de resúmenes. Esta tesis doctoral está enmarcada en el área de investigación de generación automática de resúmenes de textos, y propone dos algoritmos meméticos para generar automáticamente resúmenes extractivos, uno para un solo documento y otro para múltiples documentos. Los algoritmos meméticos propuestos se componen de: una función objetivo que busca que el resumen contenga las principales temáticas de los documentos, esquemas de evolución a nivel de población (selección, cruce, mutación y reemplazo de los agentes) buscando mantener un balance entre calidad y diversidad de los agentes, y un algoritmo de búsqueda local que permite la explotación de la vecindad de las soluciones generadas incluyendo conocimiento del problema. La experimentación de los algoritmos se realiza sobre conjuntos de datos estándar, midiendo la calidad del resumen generado (comparándolo con resúmenes de referencia) por medio de medidas aceptadas por la comunidad científica. En la experimentación los algoritmos propuestos se comparan con otros métodos del estado del arte, logrando que el algoritmo para un documento ocupe el primer puesto y que el algoritmo para múltiples documentos se ubique de segundo. Abstract. Recently, algorithms based on metaheuristics have shown good results for generating automatic summaries compared with other methods in published studies, however, although the Memetic algorithms have contributed to solving a number of diverse, combinatorial optimization problems, with excellent results. They have not been used for solving the problem of automatic text summarization. This doctoral thesis falls within the research area of automatic text summarization and proposes two memetic algorithms for automatically generating extractive summaries - one for a single document and another for multiple documents. The memetic algorithms proposed consist of an objective function to ensure that the summary contains the main themes of the documents, an evolution scheme at the population level (selection, crossover, mutation and replacement of agents), seeking to maintain a balance between the quality and diversity of the agents, and a local search algorithm that allows the exploitation of the vicinity of the generated solutions, including knowledge of the problem. Testing of the algorithms is performed on standard data sets, measuring the quality of the summary generated (compared to reference summaries) through measures accepted by the scientific community. In the testing, the proposed algorithms are compared to other published methods, with the algorithm for a single document achieving first place and the algorithm for multiple documents being placed second.