| Título: |
Comparación de métodos Kernel aplicados a la clasificación de objetos representados como grafos Comparison of Kernel methods applied to the classification of objects represented as graphs |
| Autores: | Martín Gerardo Marmolejo Varela |
| Fecha: | 2012 |
| Publicador: | CICESE |
| Fuente: |
 |
| Tipo: | info:eu-repo/semantics/masterThesis |
| Tema: |
info:eu-repo/classification/Autor/Métodos Kernal para grafos,Aprendizaje de máquina,Clasificación de objetos info:eu-repo/classification/cti/1 info:eu-repo/classification/cti/12 info:eu-repo/classification/cti/1203 |
| Descripción: |
El reconocimiento de patrones tiene como objetivo el descubrimiento automático deregularidades en datos y mediante el uso de estas regularidades tomar acciones como laclasificación de dichos datos en diferentes categorias. Tiene muchas aplicaciones entre lasque se encuentran la minería de datos, detección de fraudes bancarios, reconocimiento deobjetos en imágenes, bio-informática, entre otras. Dentro del reconocimiento de patrones,existen métodos llamados kernels que se aplican, entre otras cosas, a la clasificación deobjetos. Los métodos kernel habían sido aplicados casi exclusivamente en datos con valoresreales y pocos tipos de datos especiales, como cadenas o grafos.Cada vez es más común tener datos no estructurados que necesitan ser representadosmediante objetos abstractos como lo son los grafos. Debido a esto, se han propuesto variosmétodos kernel para lidiar con el problema de clasificación de grafos para distintos fines,sin embargo, todavía es difícil elegir el método más adecuado para una situación específica.En este trabajo se estudian y evalúan principalmente dos clases de métodos kernel paragrafos del estado del arte conocidos como kernel de caminos más cortos y kernel rápido desubárboles, así como una serie de variantes propuestas. Esto con la finalidad de realizaruna comparación entre ellos y determinar el desempeño relativo de los mismos, tanto enporcentaje de clasificación como en tiempo de ejecución.Se realizaron experimentos con dos tipos de conjuntos de datos: conjuntos de datosreales que incluyen Mutag, PTC y Pseudocentros y conjuntos de datos sintéticos. Resultadosexperimentales muestran que las variantes que obtuvieron mejores resultados (algunasvariantes del kernel de conteo de caminos más cortos y del kernel rápido de sub-árbolessobre grafos de caminos más cortos), a pesar de sus diferencias técnicas, son competitivasentre si ya que ninguna sobresale como la mejor en tiempo de ejecución ni en precisiónde clasificación sobre todos los casos de prueba. Además, se puede notar la importancia yutilidad del proceso de conversión, de los grafos originales a grafos de caminos más cortos,ya que este es utilizado por la mayoría de estas variantes. The objective of pattern recognition is to automatically discover regularities in dataand by using these regularities perform tasks such as the classification of data in differentcategories. It has many applications in diverse areas such as data mining, fraud detection,object recognition in images, and bio-informatics, to name a few. In pattern recognition,there are approaches known as kernel methods that are applied, among other things, to theclassification of objects. Kernel methods were initially applied almost exclusively to realvalued data and to few special types of data, such as strings or graphs.It is increasingly common to have unstructured data which need to be represented byabstract objects such as graphs. Because of this, many kernel methods have been proposedto deal with the problem of classification of graphs for different purposes. However, it isstill difficult to choose the most appropriate method for a specific situation.A study and evaluation of state-of-the-art graph kernel methods (shortest path kerneland fast subtree kernel) as well as a series of proposed variations is presented in orderto make a comparison between them and determine their relative performance, in bothclassification rate and computation time.A series of experiments were performed with two types of datasets: real datasets thatinclude Mutag, PTC and Pseudocenters, and a group of synthetic datasets. Experimentalresults show that the variants that perform better (some variants of the shortest pathcount kernel and the fast subtree kernel over shortest path graphs), despite their technicaldifferences, are competitive with each other as none stand out as the best in classificationrate or computation time, over all test cases. Furthermore, one can see the importance andusefulness of the conversion process, from the original graphs to shortest path graphs, sinceit is used by most variants that showed better results. |
| Idioma: | spa |
1 | 6 |
2 | 7 |
3 | 8 |
4 | 9 |
5 | 10 |