Métodos Determinísticos com Solução Única

Há vários métodos de seleção de características determinísticos de solução única. A seguir serão descritos alguns desses métodos que são baseados em técnicas de busca.

Melhor Característica Individual [48,12] Esse método consiste na avaliação de todas as características tomadas individualmente e seleção das $d$ melhoreres. Trata-se de um método bastante intuitivo e computacionalmente simples, mas não é garantido que o melhor subconjunto seja determinado, pois algumas características podem ser boas tomadas individualmente, mas podem formar um conjunto ruim quando associadas entre si.

Busca seqüencial para frente (SFS) [48,12] Trata-se de um método botton-up em que, dado um conjunto de características já selecionadas (inicialmente nulo), a cada iteração seleciona a característica que, unida ao conjunto determinado pela iteração anterior, produz a o melhor resultado da função critério. Essa característica é adicionada ao conjunto de características anterior e uma nova iteração é realizada. São realizadas $d$ iterações. A desvantagem desse método é que, uma vez que uma característica tenha sido selecionada, ela não pode ser descartada do subconjunto ótimo. Isso proporciona o chamado efeito ``nesting'' que pode ocorrer quando o subconjunto ótimo não contém elementos do conjunto já selecionado. A vantagem é o custo computacional quando se deseja obter conjuntos pequenos em relação ao total de caracteríscias.

Busca seqüencial para trás (SBS) [48,12] Esse algoritmo é uma versão top-down do algoritmo anterior. A diferença entre SBS e SFS é que o SBS é iniciado com o conjunto de características completo (contendo todas as $D$ características) e vai eliminando as menos importantes, ou seja, as que menos alteram a função critério quando são eliminadas. Assim como o método de busca seqüencial para frente, a desvantagem desse método é que, uma vez eliminada uma característica, ela não retornará ao subconjunto ótimo novamente. Como conseqüência também pode ocorrer o efeito ``nesting'' caso o melhor subconjunto contenha alguma das características que foram eliminadas. A vantagem desse método é o custo computacional, quando se deseja obter conjuntos grandes em relação ao total de características.

Algoritmos de busca seqüencial generalizada (GSFS e GSBS) [53,12] Tratam-se de algoritmos de seleção que inserem (no caso do GSFS) ou removem (no caso do GSBS) tuplas (subconjuntos) de características ao invés de fazerem com apenas uma característica por vez. O que possibilita o funcionamento dos algoritmos generalizados é a utilização de funções que determinam a significância de tuplas.

Mais l - menos r (PTA) [53,12] Esse método, cujo nome original é ``Plus $l$ - Take Away $r$'' (PTA), foi criado visando evitar o efeito ``nesting''. Basicamente, primeiro o algoritmo aumenta o conjunto de características em $l$ elementos usando o método de seleção para frente, e depois elimina $r$ características usando a busca seqüencial para trás. Os valores de $l$ e $r$ devem ser determinados pelo usuário. Na versão botton-up, $l$ deve ser maior que $r$. Já na versão top-down, $l < r$.

Métodos de busca seqüencial flutuante para frente e para trás (SFFS e SFBS) [54,12] Tratam-se de generalizações do método ``mais l - menos r'', em que os valores de $l$ e $r$ são determinados e atualizados dinamicamente. Esses métodos provém soluções muito próximas da solução ótima com um pequeno custo computacional. O método de busca para frente é a versão botton-up, e o de busca para trás, top-down. Segundo Jain et al. [48,13] esses são os métodos que melhor combinam tempo de execução com qualidade dos resultados.

Métodos adaptativos de busca seqüencial flutuante para frente e para trás [53] (ASFFS e ASFBS) Esses métodos são generalizações dos métodos de busca seqüencial flutuante, ou seja, podem ser inseridos e eliminados não somente características, mas também conjuntos (tuplas) de características por vez. Esses conjuntos têm seu tamanho e seu conteúdo determinados dinamicamente. A vantagem desses métodos é que, em termos de resultado da função critério, os resultados obtidos são mais próximos dos resultados ótimos. A desvantagem é que, quando os conjuntos de dados que são inseridos e eliminados por vez é grande, o algoritmo se torna muito mais lento e complexo que os métodos de busca seqüencial flutuante. Esse resultado está descrito na seção 7.2.1 e em [9].