CENTRO DE INVESTIGACIÓN Y DE ESTUDIOS AVANZADOS DEL INSTITUTO POLITÉCNICO NACIONAL DEPARTAMENTO DE COMPUTACIÓN Clasificación de grandes conjuntos de datos vía Máquinas de Vectores Soporte y aplicaciones en sistemas biológicos Tesis que presenta: Jair Cervantes Canales Para obtener el grado de Doctor en Ciencias En la especialidad de Ingeniería Eléctrica Opción: Computación Directores de Tesis: Dra. Xiaoou Li Zhang Dr. Wen Yu Liu México D.F. 18 Agosto 2009 A mis padres y hermanos A Raquel y Benito Agradecimientos Quiero expresar mi agradecimiento a mis asesores Dra. Xiaoou Li y Dr. Wen Yu por todo su apoyo, confianza y guía a lo largo de la tesis. A los revisores que me ayudaron enormemente con sus comentarios para mejorar este trabajo Dr. Debrup Chakraborty, Dr. Miguel González, Dr. Ivan Lopez y Dr. Luis Rocha. A mis compañeros y amigos del CINVESTAV: Arturo, Erasmo, Farid, Francisco Javier, Héctor, Israel, Luis Omar, Luis, Juan, Roberto. Un especial agradecimiento a Sofy, Felipa y Flor por su ayuda administrativa. Agradezco su apoyo a CONACyT por la beca proporcionada durante mi estancia en el programa de doctorado en el CINVESTAV. Abstract Support Vector Machines (SVM) has demonstrated highly competitive performance in many real-world applications. However, despite its good theoretical foundations and generalization performance, SVM is not suitable for large data sets classification, because training kernel matrix grows in quadratic form with the size of the data set, which provokes that training of SVM on large data sets is a very slow process. In the literature, most fast SVM implementations use completely the input data set in order to obtain good classification accuracy. However, the principal disadvantage of SVM is due its excessive computational cost in large data sets. Some algorithms have been proposed in the literature, but the training time is still very large and prohibitive in large data sets. In this thesis, we present different algorithms that tackle this problem. The proposed algorithms reduce the training time considerably, recovering the most important data points of entire data set and eliminating data points that are not important. The proposed algorithms use two stages of SVM. A first stage on a small data set in order to obtain a sketch of support vectors (SVs) distribution and recovery data points with most chance to be SVs, and a second stage of SVM in order to improve the first classification hyperplane obtained. Our research is divided into three main parts. First, three algorithms for large data set classification are introduced, the main novelty of the proposed approaches consists in using clustering and sectioning techniques in order to reduce the SVM training time. Second, a multiclassification algorithm is proposed, the main novelty of the approach proposed with respect first three techniques consists on the implementation of a method that search support vectors candidate between the space of support vectors with different label obtained in the first stage, the algorithm reduce even more the support vectors candidate, because the search of support vectors candidate is restricted to a small space. Finally, a SVM algorithm for classification of introns and exons is proposed. Classification of gene sequence into regions that code for genetic material and regions that do not is a challenging task in DNA sequence analysis. Due to enormous quantities of DNA sequence and to the fact that regions that encode in proteins (exons) can be interrupted by regions that do not encode (introns), recognition of genes is not an easy challenge The proposed algorithms overcome the main limitation of SVM without affecting in a significant way the quality of results. Moreover, experimental results show that the accuracy obtained by the proposed approach is comparable with other fast SVM implementations. Furthermore, results indicate that our approach is a viable alternative since it improves the training time of the best fast SVM implementations known to date. Resumen Las Máquinas de Soporte Vectorial Vectores Soporte (SVM) han demostrado tener un gran desempeño en muchas aplicaciones del mundo real. Sin embargo, a pesar de sus buenos fundamentos teóricos y buen desempeño al generalizar, las SVM no son adecuadas para clasificación con grandes conjuntos de datos, ya que la matriz del kernel crece de forma cuadrática con el tamaño del conjunto de datos, provocando que el entrenamiento de las SVM sobre conjuntos de datos grandes sea un proceso muy lento. En la literatura, la mayoría de los métodos de agilización de SVM usan el conjunto de datos entero con el objetivo de obtener buenas precisiones de clasificación. Sin embargo, la principal desventaja de las SVM es debido a su excesivo costo computacional en conjuntos de datos grandes. Algunos algoritmos han sido propuestos en la literatura pero el tiempo de entrenamiento sigue siendo muy grande y prohibitivo en conjuntos de datos grandes. En esta tesis, presentamos varios algoritmos que enfrentan este problema. Los algoritmos propuestos reducen considerablemente el tiempo de entrenamiento recuperando los datos más importantes del conjunto de datos entero y eliminando aquellos que no son importantes. Los algoritmos propuestos usan dos etapas de SVM. Una primera etapa sobre un conjunto de datos pequeño con el objetivo de obtener un esbozo de la distribución de los vectores soporte (VS) y recuperar los datos con más probabilidades de ser VS y una segunda etapa de SVM con el objetivo de mejorar el primer hiperplano de clasificación obtenido. Nuestra investigación está dividida en tres partes principales. Primero, tres algoritmos para clasificación de grandes conjuntos de datos son presentados, la principal novedad de los enfoques propuestos consiste en emplear agrupamiento y/o técnicas de seccionamiento con el objetivo de reducir el tiempo de entrenamiento de las SVM. Segundo, un algoritmo de multiclasificación es propuesto, la principal novedad del algoritmo propuesto con respecto a las tres primeras técnicas consiste en la implementación de un método de búsqueda de candidatos a SVs entre el espacio de los SVs con diferente etiqueta obtenidos en la primera etapa. El algoritmo reduce aún más el conjunto de candidatos a vectores soporte debido a que la búsqueda de candidatos a VS es restringida a un pequeño espacio. Finalmente, un algoritmo para clasificación de Intrones y Exones es propuesto. La clasificación de secuencias de genes en regiones que codifican en material genético y regiones que no, es un reto en análisis de secuencias de ADN. Debido a que enormes cantidades de secuencias de ADN y al hecho de que las regiones que codifican en proteínas (exones) pueden ser interrumpidas por regiones que no codifican (intrones), el reconocimiento de genes no es un reto fácil Los algoritmos propuestos superan la principal limitación de las SVM sin afectar de forma significativa la calidad de los resultados, además los resultados experimentales muestran que la precisión obtenida mediante los enfoques propuestos es comparable con otras implementaciones de SVM. Además, los resultados indican que los enfoques propuestos son una alternativa viable ya que estos mejoran el tiempo de entrenamiento de las mejores implementaciones de SVM conocidas a la fecha.