Please enable JavaScript.
Coggle requires JavaScript to display documents.
Completo: encontra solução ótima (Busca + backtracking: nem todos são…
Completo: encontra solução ótima
Exaustivo: testa todos os subconjuntos
Busca + backtracking: nem todos são avaliados
branch and bound
Quero selecionar D características de um total de N
Crio uma árvore onde
Cada nó possui um conjunto de características
A raiz possui o subconjunto contendo todas as N características
Um nó filho tem uma característica a menos que seu pai
Folhas tem subconjuntos com D características
Busca em profundidade para encontrar a folha melhor avaliada
Entrada
Função critério M()
amostra de treinamento rotulada
D - nº desejado de características
árvore de caracteristicas
Saída
Conjunto melhor avaliado
A função de avaliação utilizada deve ser monotonicamente crescente na dimensão (nr de características), isto é, para subconjuntos A e B, M(A)<= M(AUB)
Se eu tirar elementos de um subconjunto, a medida de avaliação do subconjunto resultante não pode aumentar (fca igual ou piora)
Se eu já sei que um subconjunto de tamanho D tem uma medida m1, não vou analisar subconjuntos maiores com medidas <= m1, pois esse valor só pode piorar ao remover algumas características
Melhor usar com funções de avaliação baseadas em distância
best first search
beam search