Seleção de Características com Busca Ordenada e Classificadores de Larga Margem
Autores
5168 |
1914,47,1664
|
|
5169 |
1914,47,1664
|
|
5170 |
1914,47,1664
|
Informações:
Publicações do PESC
Título
Seleção de Características com Busca Ordenada e Classificadores de Larga Margem
Linha de pesquisa
Inteligência Artificial
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
14/12/2011
Resumo
Classificadores de larga margem, como as máquinas de vetores suporte, têm sido amplamente utilizados com bastante eficiência em problemas que possuem uma grande quantidade de variáveis ou características. Nesse sentido, torna-se importante o desenvolvimento de novas estratégias para a solução desse tipo de problema que se utilizem de critérios de seleção associados a esse tipo de classificador. Nesse trabalho propõe-se um novo método para a seleção de subconjuntos de variáveis que utiliza um processo de busca ordenada, também conhecido como best-first, para exploração do espaço de possíveis candidatos. O algoritmo, denominado AOS, utiliza como medida de avaliação os valores de margem calculados a partir da utilização de um classificador de larga margem. Esse classificador, de grande eficiência computacional, permite grande flexibilidade e rapidez na obtenção dos valores de margem possibilitando a solução de problemas de tamanho razoável, com centenas de características, sem que ocorra explosão combinatória. O algoritmo foi testado em vários problemas da literatura e seus resultados comparados à outras técnicas de seleção de subconjuntos. Uma importante contribuição teórica do trabalho se refere ao desenvolvimento do conceito de margem projetada. A utilização desse valor, computado como a projeção da margem real de um espaço em cada subespaço de dimensão inferior permitiu maior eficiência e rapidez na solução dos problemas de classificação e, portanto, no processo de busca como um todo.
Abstract
Large margin classifiers, as support vector machines, have been widely used quite effectively on high dimensional problems. In this sense, it is important to develop new feature selection strategies that are associated with this type of classifier. In this work, we propose a new method for feature selection based on an ordered search process, also known as best-first, to explore the space of possible candidates. The algorithm, called AOS, uses as a search measure the margin values calculated using a large margin classifier. This highly efficient classifier allows great flexibility and speed in obtaining the margin values, enabling the solution of problems of reasonable size, with hundreds of features, and avoiding combinatorial explosion. The algorithm was tested on several problems from the literature and the results were compared to other methods. An important theoretical contribution of the paper refers to the concept of the projected margin. This value, computed as the projection of the maximal margin vector on a lower dimensional subspace, is used as an upper bound to the actual maximal margin. This enables greater efficiency and speed in solving problems of classification and, therefore, in the search process as a whole.
Arquivo