Métodos ótimos

Em termos da qualidade do conjunto de características obtido, o único método realmente ótimo é o da busca exaustiva. Nesse método, todos os $(^{N}_m)$ subconjuntos possíveis de tamanho $m$ são avaliados. Essa abordagem é muito cara computacionalmente, mesmo para conjuntos não muito grandes, pois sua complexidade é exponencial.

Algumas funções critério possuem uma propriedade chamada monotonicidade. Uma função é monotônica se $J(\mathcal{X} \bigcup \mathcal{Z}) \geq J(\mathcal{X})$, para todo $\mathcal{X}, \mathcal{Z} \subseteq \mathcal{Y}$. Ou seja, o valor da função critério é sempre maior para conjuntos de características maiores. Para este caso, há o algoritmo de busca em árvores chamado branch-and-bound, proposto em [Narendra and Fukunaga, 1977]. Esse algoritmo pode retornar a solução ideal sem verificar todas as possibilidades, mas sabemos que, devido ao problema da dimensionalidade (vide seção 2.3), para situações em que o conjunto de treinamento não é grande o suficiente, normalmente a função critério não é monotônica. Por esse fato, o algoritmo branch-and-bound não pode ser aplicado em quaisquer situações.

Outra desvantagem desse método é que, no pior caso, todas as configurações são consultadas, o que faz com que o algoritmo tenha complexidade exponencial no pior caso, tornando impraticável para conjuntos de características grandes. Por essas razões existem os métodos sub-ótimos, os quais não garantem que o conjunto de características obtido seja o melhor possível, mas são eficientes em termos de tempo de execução, pois eles não consultam todas as possibilidades para determinar a(s) solução(ões). A seguir serão comentados alguns dos métodos sub-ótimos.