Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Google Scholar, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

Texto completo
Autor(es):
Ris‚ M. ; Barrera‚ J. ; Martins Jr‚ D.C.
Número total de Autores: 3
Tipo de documento: Artigo Científico
Fonte: PATTERN RECOGNITION; v. 43, n. 3, p. 557-568, 2010.
Resumo

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 01/09401-0 - Aproximação genômica e pós-genômica ao estudo das malárias humanas de Plasmodium vivax e Plasmodium falciparum na Amazônia brasileira
Beneficiário:Hernando Antonio del Portillo Obando
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 04/03967-0 - Reducao de dimensionalidade para identificacao de arquitetura de redes de regulacao genica e projeto de operadores.
Beneficiário:David Corrêa Martins Junior
Modalidade de apoio: Bolsas no Brasil - Doutorado
Processo FAPESP: 99/12765-2 - Desenvolvimento e avaliação de métodos originais e precisos em análise de formas e imagens e visão computacional
Beneficiário:Luciano da Fontoura Costa
Modalidade de apoio: Auxílio à Pesquisa - Temático