Método Grid-Quadtree para seleção de parâmetros do algoritmo support vector classification (SVC)

Abstract

Resumo: O algoritmo Support Vector Classification (SVC) é uma técnica de reconhecimento de padrões, cuja eficiência depende da seleção de seus parâmetros: constante de regularização C, função kernel e seus respectivos parâmetros. A escolha equivocada dessas variáveis impacta diretamente na performance do algoritmo, acarretando em fenômenos indesejáveis como o overfitting e o underfitting. O problema que estuda a procura de parâmetros ótimos para o SVC, em relação às suas medidas de desempenho, é denominado seleção de modelos do SVC. Em virtude do amplo domínio de convergência do kernel gaussiano, a maioria dos métodos destinados a solucionar esse problema concentra-se na seleção da constante C e do parâmetro ? do kernel gaussiano. Dentre esses métodos, a busca por grid é um dos de maior destaque devido à sua simplicidade e bons resultados. Contudo, por avaliar todas as combinações de parâmetros (C, ?) dentre o seu espaço de busca, a mesma necessita de muito tempo de processamento, tornando-se impraticável para avaliação de grandes conjuntos de dados. Desta forma, o objetivo deste trabalho é propor um método de seleção de parâmetros do SVC, usando o kernel gaussiano, que combine a técnica quadtree à busca por grid, para reduzir o número de operações efetuadas pelo grid e diminuir o seu custo computacional. A ideia fundamental é empregar a quadtree para desenhar a boa região de parâmetros, evitando avaliações desnecessárias de parâmetros situados nas áreas de underfitting e overfitting. Para isso, desenvolveu-se o método grid-quadtree (GQ), utilizando-se a linguagem de programação VB.net em conjunto com os softwares da biblioteca LIBSVM. Na execução do GQ, realizou-se o balanceamento da quadtree e criou-se um procedimento denominado refinamento, que permitiu delinear a curva de erro de generalização de parâmetros. Para validar o método proposto, empregaram-se vinte bases de dados referência na área de classificação, as quais foram separadas em dois grupos. Os resultados obtidos pelo GQ foram comparados com os da tradicional busca por grid (BG) levando-se em conta o número de operações executadas por ambos os métodos, a taxa de validação cruzada (VC) e o número de vetores suporte (VS) associados aos parâmetros encontrados e a acurácia do SVC na predição dos conjuntos de teste. A partir das análises realizadas, constatou-se que o GQ foi capaz de encontrar parâmetros de excelente qualidade, com altas taxas VC e baixas quantidades de VS, reduzindo em média, pelo menos, 78,8124% das operações da BG para o grupo 1 de dados e de 71,7172% a 88,7052% para o grupo 2. Essa diminuição na quantidade de cálculos efetuados pelo quadtree resultou em uma economia de horas de processamento. Além disso, em 11 das 20 bases estudadas a acurácia do SVC-GQ foi superior à do SVC-BG e para quatro delas igual. Isso mostra que o GQ é capaz de encontrar parâmetros melhores ou tão bons quanto os da BG executando muito menos operações.

Abstract: The Support Vector Classification (SVC) algorithm is a pattern recognition technique, whose efficiency depends on its parameters selection: the penalty constant C, the kernel function and its own parameters. A wrong choice of these variables values directly impacts on the algorithm performance, leading to undesirable phenomena such as the overfitting and the underfitting. The task of searching for optimal parameters with respect to performance measures is called SVC model selection problem. Due to the Gaussian kernel wide convergence domain, many model selection approaches focus in determine the constant C and the Gaussian kernel ? parameter. Among these, the grid search is one of the highlights due to its easiest way and high performance. However, since it evaluates all parameters combinations (C, ?) on the search space, it requires high computational time and becomes impractical for large data sets evaluation. Thus, the aim of this thesis is to propose a SVC model selection method, using the Gaussian kernel, which integrates the quadtree technique with the grid search to reduce the number of operations performed by the grid and its computational cost. The main idea of this study is to use the quadtree to determine the good parameters region, neglecting the evaluation of unnecessary parameters located in the underfitting and the overfitting areas. In this regard, it was developed the grid-quadtree (GQ) method, which was implemented on VB.net development environment and that also uses the software of the LIBSVM library. In the GQ execution, it was considered the balanced quadtree and it was created a refinement procedure, that allowed to delineate the parameters generalization error curve. In order to validate the proposed method, twenty benchmark classification data set were used, which were separated into two groups. The results obtained via GQ were compared with the traditional grid search (GS) ones, considering the number of operations performed by both methods, the cross-validation rate (CV) and the number of support vectors (SV) associated to the selected parameters, and the SVC accuracy in the test set. Based on this analyzes, it was concluded that GQ was able to find excellent parameters, with high CV rates and few SV, achieving an average reduction of at least 78,8124% on GS operations for group 1 data and from 71,7172% to 88,7052% for group 2. The decrease in the amount of calculations performed by the quadtree lead to savings on the computational time. Furthermore, the SVC-GQ accuracy was superior than SVC-GS in 11 of the 20 studied bases and equal in four of them. These results demonstrate that GQ is able to find better or as good as parameters than BG, but executing much less operations.