Departamento de Computación

La Máquina de Soporte Vectorial o Máquina de vectores de soporte (SVM, por sus siglas en inglés) es un clasificador del estado del arte cuyo modelo es un hiperplano de margen máximo. Las SVMs alcanzan una elevada precisión de clasificación, generan un modelo compacto y tienen un poder de generalización extraordinario. A pesar de estas atractivas características, este clasificador tiene la desventaja de no ser apropiado para conjuntos de datos grandes, debido a que su fase de entrenamiento es costosa. En esta investigación, se proponen dos métodos para disminuir el tamaño de conjuntos de datos, estos mejoran el tiempo de entrenamiento de las SVMs. El primer método presentado en este trabajo usa una cubierta cóncava-convexa para detectar objetos localizados en los bordes externos de conjuntos de datos; este método es adecuado para conjuntos de datos de baja dimensionalidad. El segundo método usa el concepto de entropía para detectar objetos que se encuentran cerca de otros de clase opuesta; este método puede trabajar con un número arbitrario de dimensiones. Los métodos de reducción de datos propuestos permiten aplicar SVM sobre conjuntos de datos grandes. De hecho, estos métodos también mejoran el tiempo de entrenamiento en conjuntos de datos medianos. Los métodos propuestos fueron validados usando conjuntos de datos disponibles públicamente y comparando su desempeño con respecto al de otros métodos del estado del arte. Después de aplicar los nuevos métodos, el tiempo de entrenamiento de las SVMs mejora de manera considerable, mientras que la precisión alcanzada sólo es disminuida ligeramente.

Abstract

Support Vector Machine (SVM) is a state-of-the-art classification method whose model is a hyperplane of maximum margin. SVMs produce a high classification accuracy, a compact model and have an extraordinary generalization capability. In spite of these attractive features, this classifier has the disadvantage of being unsuitable for large data sets, because its training phase is costly. In this research, two methods to decrease the size of the training data sets are proposed, in order to improve the training time of a SVM. The first method presented in this work uses a convex-concave hull to detect objects in data sets that are located on the outer boundaries of data, this method is suitable for low dimensional data sets. The second method uses the concept of entropy to detect objects that are close to others with opposite label; this method can work with an arbitrary number of dimensions. Our methods allow to apply SVMs on large data sets. In fact, these methods also improve the training time on medium-size data sets. The proposed methods were validated using publicly available data sets and comparing performance against other state of the art methods. After applying the novel methods, the training time of SVM is considerably improved whereas the achieved classification accuracy is only slightly degraded.