SIN5007-Tema03-ReducaoDimens_SelecaoDeCaracteristicas

Prévia do material em texto

SISTEMAS DE
INFORMAÇÃO
1
1
1
1SISTEMAS DE
INFORMAÇÃO
1
1SISTEMAS DE
INFORMAÇÃO
1
1
1
Professora:
Ariane Machado Lima
Tema 3
Redução de 
Dimensionalidade
Seleção de Características 
(e medidas de distância para classificação)
SISTEMAS DE
INFORMAÇÃO
2
2
2
2SISTEMAS DE
INFORMAÇÃO
2
2SISTEMAS DE
INFORMAÇÃO
2
2
2
Ciclo de aprendizado 
supervisionado
mundo
Coleta de dados
Análise exploratória
Pré-processamento
Redução de dimensionalidade
Escolha do alg. indutor
Treinamento do classificador
Avaliação do classificador
Retreinamento do classificador
Fusão de características (PCA)
Aula passada
SISTEMAS DE
INFORMAÇÃO
3
3
3
3SISTEMAS DE
INFORMAÇÃO
3
3SISTEMAS DE
INFORMAÇÃO
3
3
3
Ciclo de aprendizado 
supervisionado
mundo
Coleta de dados
Análise exploratória
Pré-processamento
Redução de dimensionalidade
Escolha do alg. indutor
Treinamento do classificador
Avaliação do classificador
Retreinamento do classificador
Fusão de características (PCA)
Aula de hoje
Seleção de características 
SISTEMAS DE
INFORMAÇÃO
4
4
4
4SISTEMAS DE
INFORMAÇÃO
4
4SISTEMAS DE
INFORMAÇÃO
4
4
4
Seleção de Características
• Dados com N características
• Problema: escolher um subconjunto 
contendo D características que seja melhor 
que os outros subconjuntos (D < N)
• Número de possíveis subconjuntos de 
tamanho D:
SISTEMAS DE
INFORMAÇÃO
5
5
5
5SISTEMAS DE
INFORMAÇÃO
5
5SISTEMAS DE
INFORMAÇÃO
5
5
5
Seleção de Características
• Dados com N características
• Problema: escolher um subconjunto 
contendo D características que seja melhor 
que os outros subconjuntos (D < N)
• Número de possíveis subconjuntos de 
tamanho D:
N = N!
D (N-D)! D!
• Número de possíveis subconjuntos (se eu 
não limitar a D características): 2N
SISTEMAS DE
INFORMAÇÃO
6
6
6
6SISTEMAS DE
INFORMAÇÃO
6
6SISTEMAS DE
INFORMAÇÃO
6
6
6
Seleção de Características
• N = 20, D = 10: 2x105 subconjuntos! 
SISTEMAS DE
INFORMAÇÃO
7
7
7
7SISTEMAS DE
INFORMAÇÃO
7
7SISTEMAS DE
INFORMAÇÃO
7
7
7
Seleção de Características
• N = 20, D = 10: 2x105 subconjuntos! 
• N = 40, D = 10: ~ 109 subconjuntos! 
SISTEMAS DE
INFORMAÇÃO
8
8
8
8SISTEMAS DE
INFORMAÇÃO
8
8SISTEMAS DE
INFORMAÇÃO
8
8
8
Seleção de Características
• N = 20, D = 10: 2x105 subconjuntos! 
• N = 40, D = 10: ~ 109 subconjuntos! 
• N = 40 e D não definido: 240 ~ 1012
• Milagre (ou maldição) da combinatória!!!
SISTEMAS DE
INFORMAÇÃO
9
9
9
9SISTEMAS DE
INFORMAÇÃO
9
9SISTEMAS DE
INFORMAÇÃO
9
9
9
Seleção de Características
• Questões relevantes:
• Como encontrar o melhor subconjunto? 
Avaliar todos, um a um?
• O que é um subconjunto ser melhor que 
outro?
SISTEMAS DE
INFORMAÇÃO
10
10
10
10SISTEMAS DE
INFORMAÇÃO
10
10SISTEMAS DE
INFORMAÇÃO
10
10
10
Características de um algoritmo 
de seleção de Características
 Relação com o classificador
 Função de avaliação (define métrica do que é 
“melhor”)
 Forma de percorrer o espaço de busca 
(subconjuntos de características)
 Critério de parada: quando me dou por 
satisfeito
SISTEMAS DE
INFORMAÇÃO
11
11
11
11SISTEMAS DE
INFORMAÇÃO
11
11SISTEMAS DE
INFORMAÇÃO
11
11
11
Características de um algoritmo 
de seleção de Características
 Relação com o classificador
 Função de avaliação (define métrica do que é 
“melhor”)
 Forma de percorrer o espaço de busca 
(subconjuntos de características)
 Critério de parada: quando me dou por 
satisfeito
SISTEMAS DE
INFORMAÇÃO
12
12
12
12SISTEMAS DE
INFORMAÇÃO
12
12SISTEMAS DE
INFORMAÇÃO
12
12
12
Relação com o classificador
• Filtro: 
• seleção de características é um passo anterior e 
independente da classificação (não tem relação 
nenhuma com o classificador)
• Camada (wrapper): 
• o subconjunto de características é avaliado 
usando o próprio classificador (avaliação pelo 
desempenho da classificação) 
• Embutidos: 
• A seleção é feita pelo próprio classificador
SISTEMAS DE
INFORMAÇÃO
13
13
13
13SISTEMAS DE
INFORMAÇÃO
13
13SISTEMAS DE
INFORMAÇÃO
13
13
13
Relação com o classificador
• Filtro: 
• seleção de características é um passo anterior e 
independente da classificação (não tem relação 
nenhuma com o classificador): Ex: filtro de 
correlação
SISTEMAS DE
INFORMAÇÃO
14
14
14
14SISTEMAS DE
INFORMAÇÃO
14
14SISTEMAS DE
INFORMAÇÃO
14
14
14
Relação com o classificador
• Camada (wrapper): 
• o subconjunto de características é avaliado 
usando o próprio classificador (avaliação pelo 
desempenho da classificação – ex: acurácia) 
SISTEMAS DE
INFORMAÇÃO
15
15
15
15SISTEMAS DE
INFORMAÇÃO
15
15SISTEMAS DE
INFORMAÇÃO
15
15
15
Relação com o classificador
• Embutidos: 
• A seleção é feita pelo próprio classificador (ex: 
árvore de decisão)
Feature selection
and Classification
SISTEMAS DE
INFORMAÇÃO
16
16
16
16SISTEMAS DE
INFORMAÇÃO
16
16SISTEMAS DE
INFORMAÇÃO
16
16
16
Características de um algoritmo 
de seleção de Características
 Relação com o classificador
 Função de avaliação (define métrica do que é 
“melhor”)
 Forma de percorrer o espaço de busca 
(subconjuntos de características)
 Critério de parada: quando me dou por 
satisfeito
SISTEMAS DE
INFORMAÇÃO
17
17
17
17SISTEMAS DE
INFORMAÇÃO
17
17SISTEMAS DE
INFORMAÇÃO
17
17
17
Função de avaliação 
(função critério)
• Dentre vários subconjuntos de características, 
qual é o melhor?
• Otimalidade é sempre relativa a uma função de 
avaliação que faz alguma medida do subconjunto 
corrente.
• Exemplos de tipos de medidas: baseadas em
• Distância
• Informação
• Dependência
• Consistência
• Taxa de erro do classificador
SISTEMAS DE
INFORMAÇÃO
18
18
18
18SISTEMAS DE
INFORMAÇÃO
18
18SISTEMAS DE
INFORMAÇÃO
18
18
18
Função de avaliação 
(função critério)
• Medidas de distância
• Ex: distância euclidiana: d(u,v) = ||v-u||
• Subconjunto (de características) X é melhor do 
que o subconjunto Y se:
X consegue fazer com que as duas classes fiquem 
mais distantes do que Y consegue
• Qual é a distância entre duas classes?
SISTEMAS DE
INFORMAÇÃO
19
19
19
19SISTEMAS DE
INFORMAÇÃO
19
19SISTEMAS DE
INFORMAÇÃO
19
19
19
Distância entre duas classes A e B
• Single linkage (vizinhos mais próximos):
• dist(A,B) = min dist(a,b), a ∈ A, b ∈ B
• Distância mínima entre qualquer ponto da classe 
A e qualquer ponto da classe B 
SISTEMAS DE
INFORMAÇÃO
20
20
20
20SISTEMAS DE
INFORMAÇÃO
20
20SISTEMAS DE
INFORMAÇÃO
20
20
20
Distância entre duas classes A e B
• Complete linkage (vizinhos mais distantes):
• dist(A,B) = max dist(a,b), a ∈ A, b ∈ B
• Distância máxima entre qualquer ponto da classe 
A e qualquer ponto da classe B 
SISTEMAS DE
INFORMAÇÃO
21
21
21
21SISTEMAS DE
INFORMAÇÃO
21
21SISTEMAS DE
INFORMAÇÃO
21
21
21
Distância entre duas classes A e B
• Distância média:
• dist(A,B) = 1/(NANB) ∑ dist(a,b), a ∈ A, b ∈ B
• Distância média de todos os pares de pontos das 
classes A e B
SISTEMAS DE
INFORMAÇÃO
22
22
22
22SISTEMAS DE
INFORMAÇÃO
22
22SISTEMAS DE
INFORMAÇÃO
22
22
22
Distância entre duas classes A e B
• Distância entre centróides:
• dist(A,B) = dist (CA,CB)
• Distância entre os centros de massa (centróides) da 
classe A (CA) e da classe B (CB)
• I-ésimo componente do centróide da classe k (Ci
K) é valor 
médio dos i-ésimos componentes de todos os elementos 
(vetores de características) da classe k 
SISTEMAS DE
INFORMAÇÃO
23
23
23
23SISTEMAS DE
INFORMAÇÃO
23
23SISTEMAS DE
INFORMAÇÃO
23
23
23
Função de avaliação 
(função critério)
• Medidas de informação
• Ex: informação mútua, entropia
SISTEMAS DE
INFORMAÇÃO
24
24
24
24SISTEMAS DE
INFORMAÇÃO
24
24SISTEMAS DE
INFORMAÇÃO
24
24
24
Função de avaliação 
(função critério)
• Medidas de informação
• Ex: informação mútua
• Subconjunto X é melhor que Y se 
a informação mútua entre X e a classe é maior 
que a informação mútua entre Y e a classe
(ie, olhando para X você acerta mais a classe do 
que olhando Y)
ou seja, I(X, c) > I(Y, c) ?
SISTEMAS DE
INFORMAÇÃO
25
25
2525SISTEMAS DE
INFORMAÇÃO
25
25SISTEMAS DE
INFORMAÇÃO
25
25
25
Função de avaliação 
(função critério)
• Medidas de informação
• Ex: entropia
Subconjunto X é melhor que Y se (entropia):
a incerteza (entropia) sobre a classe diminui mais 
olhando para X do que para Y
(ie, X fornece mais informação sobre a classe do 
que Y)
ou seja, H(Cx) < H(Cy) ?
Ex: cara ou coroa 
(n=2)
SISTEMAS DE
INFORMAÇÃO
26
26
26
26SISTEMAS DE
INFORMAÇÃO
26
26SISTEMAS DE
INFORMAÇÃO
26
26
26
Função de avaliação 
(função critério)
• Medidas de dependência
• Ex: correlação
Subconjunto X é melhor que Y se:
correlação (X, classe) > correlação(Y, classe)
ou
correlação(X, Y) é alta, um deles pode ser 
descartado
SISTEMAS DE
INFORMAÇÃO
27
27
27
27SISTEMAS DE
INFORMAÇÃO
27
27SISTEMAS DE
INFORMAÇÃO
27
27
27
Função de avaliação 
(função critério)
• Medidas de consistência
Ex: Subconjunto X é consistente se todas as 
instâncias com o mesmo valor de X possuem a mesma 
classificação
SISTEMAS DE
INFORMAÇÃO
28
28
28
28SISTEMAS DE
INFORMAÇÃO
28
28SISTEMAS DE
INFORMAÇÃO
28
28
28
Função de avaliação 
(função critério)
• Medidas baseadas na taxa de erro do 
classificador 
• Subconjunto A de características é melhor que o 
subconjunto B se o classificador apresentou 
menor erro considerando A do que considerando 
B
• Relação com o classificador: wrapper
• Veremos na próxima aula diferentes 
métodos para medir esse erro
SISTEMAS DE
INFORMAÇÃO
29
29
29
29SISTEMAS DE
INFORMAÇÃO
29
29SISTEMAS DE
INFORMAÇÃO
29
29
29
Avaliação das funções de 
avaliação
• Generalidade
• O subconjunto selecionado é bom para vários 
algoritmos de classificação?
• Complexidade de tempo
• Tempo gasto para selecionar o subconjunto
• Desempenho
• Desempenho da classificação (ex: acurácia) 
usando o subconjunto selecionado
SISTEMAS DE
INFORMAÇÃO
30
30
30
30SISTEMAS DE
INFORMAÇÃO
30
30SISTEMAS DE
INFORMAÇÃO
30
30
30
Avaliação das funções de 
avaliação
Medida Generalidade Complex. 
Tempo
Acurácia
Distância Sim Baixa -
Informação Sim Baixa -
Dependência Sim Baixa -
Consistência Sim Moderada -
Taxa de erro do 
classificador
Não Alta Alta
- : nada se pode afirmar
SISTEMAS DE
INFORMAÇÃO
31
31
31
31SISTEMAS DE
INFORMAÇÃO
31
31SISTEMAS DE
INFORMAÇÃO
31
31
31
Características de um algoritmo 
de seleção de Características
 Relação com o classificador
 Função de avaliação (define métrica do que é 
“melhor”)
 Forma de percorrer o espaço de busca 
(subconjuntos de características)
 Critério de parada: quando me dou por 
satisfeito
SISTEMAS DE
INFORMAÇÃO
32
32
32
32SISTEMAS DE
INFORMAÇÃO
32
32SISTEMAS DE
INFORMAÇÃO
32
32
32
Forma de percorrer o espaço de 
subconjuntos de características 
Isto é:
 Em que ordem eu avalio os vários conjuntos 
de características?
 Quando páro de olhar novos subconjuntos?
 
SISTEMAS DE
INFORMAÇÃO
33
33
33
33SISTEMAS DE
INFORMAÇÃO
33
33SISTEMAS DE
INFORMAÇÃO
33
33
33
Forma de percorrer o espaço de 
subconjuntos de características 
• Completo: encontra a solução ótima
Exaustivo
Busca + backtracking (nem todos são avaliados)
Ex: branch and bound, best first search, beam search
• Heurístico: incremental
a cada iteração, uma nova característica integra o 
subconjunto corrente (ou é removida dele). O(N2) 
• Randômico:
SISTEMAS DE
INFORMAÇÃO
34
34
34
34SISTEMAS DE
INFORMAÇÃO
34
34SISTEMAS DE
INFORMAÇÃO
34
34
34
Forma de percorrer o espaço de 
subconjuntos de características 
• Completo: encontra a solução ótima
• Exaustivo (testa todos os subconjuntos)
• Busca + backtracking (nem todos são avaliados)
• Ex: branch and bound, best first search, beam 
search
• Heurístico: incremental
a cada iteração, uma nova característica integra o 
subconjunto corrente (ou é removida dele). O(N2) 
• Randômico:
SISTEMAS DE
INFORMAÇÃO
35
35
35
35SISTEMAS DE
INFORMAÇÃO
35
35SISTEMAS DE
INFORMAÇÃO
35
35
35
Forma de percorrer o espaço de 
subconjuntos de características 
• Completo: encontra a solução ótima
• Exaustivo (testa todos os subconjuntos)
• Busca + backtracking (nem todos são avaliados)
• Ex: branch and bound, best first search, beam 
search
• Heurístico: incremental ou baseado em 
pesosncremental
ação, uma nova característica integra o subconjun
• Randômico:
SISTEMAS DE
INFORMAÇÃO
36
36
36
36SISTEMAS DE
INFORMAÇÃO
36
36SISTEMAS DE
INFORMAÇÃO
36
36
36
Forma de percorrer o espaço de 
subconjuntos de características 
• Completo: encontra a solução ótima
 Exaustivo (testa todos os subconjuntos)
• Busca + backtracking (nem todos são avaliados)
• Ex: branch and bound, best first search, beam 
search
• Heurístico: incremental ou baseado em 
pesos
 
• Randômico: cada novo subconjunto é 
gerado aleatoriamente. 
• Definição de um número máximo de iterações
SISTEMAS DE
INFORMAÇÃO
37
37
37
37SISTEMAS DE
INFORMAÇÃO
37
37SISTEMAS DE
INFORMAÇÃO
37
37
37
Forma de percorrer o espaço de 
subconjuntos de características 
• Completo: encontra a solução ótima
• Exaustivo (testa todos os subconjuntos)
• Busca + backtracking (nem todos são avaliados)
• Ex: branch and bound, best first search, beam 
search
SISTEMAS DE
INFORMAÇÃO
38
38
38
38SISTEMAS DE
INFORMAÇÃO
38
38SISTEMAS DE
INFORMAÇÃO
38
38
38
Branch and bound (completo)
• Quero selecionar D características de um total de 
N (um “bom chute” é a raiz quadrada de N)
• “Crio” (sob demanda) uma árvore na qual 
• Cada nó possui um subconjunto de 
características
• A raiz possui o subconjunto contendo TODAS (N) 
as características
• Um nó filho tem uma característica a menos 
que seu pai
• Folhas têm subconjuntos com D características
• Busca em profundidade para achar a folha melhor 
avaliada
SISTEMAS DE
INFORMAÇÃO
39
39
39
39SISTEMAS DE
INFORMAÇÃO
39
39SISTEMAS DE
INFORMAÇÃO
39
39
39
SISTEMAS DE
INFORMAÇÃO
40
40
40
40SISTEMAS DE
INFORMAÇÃO
40
40SISTEMAS DE
INFORMAÇÃO
40
40
40
Branch and bound
Entrada: 
• uma amostra de treinamento (rotulada)
• D (número desejado de características)
• a árvore de características (Ti(n) é o i-ésimo nó do 
nível n; nível contado de D a N (das folhas até a 
raiz)
SISTEMAS DE
INFORMAÇÃO
41
41
41
41SISTEMAS DE
INFORMAÇÃO
41
41SISTEMAS DE
INFORMAÇÃO
41
41
41
SISTEMAS DE
INFORMAÇÃO
42
42
42
42SISTEMAS DE
INFORMAÇÃO
42
42SISTEMAS DE
INFORMAÇÃO
42
42
42
Branch and bound
Entrada: 
• uma amostra de treinamento (rotulada)
• D (número desejado de características)
• a árvore de características (Ti(n) é o i-ésimo nó do 
nível n; nível contado de D a N (das folhas até a 
raiz)
• Uma função critério F
1. melhor_medida ← 0 
2. S ← ∅ 
3. Explore_no(T1(N))
Saída: S terá o subconjunto melhor avaliado
//melhor valor de F até o momento
//S = melhor subconjunto de caract. 
até o momento (F(S) = melhor_medida)
SISTEMAS DE
INFORMAÇÃO
43
43
43
43SISTEMAS DE
INFORMAÇÃO
43
43SISTEMAS DE
INFORMAÇÃO
43
43
43
Função critério do branch and bound
• A função de avaliação utilizada deve ser 
monotonicamente crescente na dimensão (nr de 
características), isto é, para subconjuntos A e B, F(A) 
<= F(AUB) ,
isto é, se eu tirar elementos de um subconjunto (descer 
na árvore), a medida de avaliação do subconjunto 
resultante não pode aumentar (fica igual ou piora)
– Ex: funções baseadas em distância
Ideia: Se eu já sei que um subconjunto S de tamanho D 
possui F(S)=melhor_medida, não vou analisar 
subconjuntos maiores que com medidas <= 
melhor_medida, pois esse valor só pode piorar ao 
remover algumas características
SISTEMAS DE
INFORMAÇÃO
44
44
44
44SISTEMAS DE
INFORMAÇÃO
44
44SISTEMAS DE
INFORMAÇÃO
44
44
44
SISTEMAS DE
INFORMAÇÃO
45
45
45
45SISTEMAS DE
INFORMAÇÃO
45
45SISTEMAS DE
INFORMAÇÃO
45
45
45
Ex: F(T2(4)) = 180
Ent o n o preciso ã ã
avaliar seus 
descendentes
SISTEMAS DE
INFORMAÇÃO
46
46
46
46SISTEMAS DE
INFORMAÇÃO
46
46SISTEMAS DE
INFORMAÇÃO
46
46
46
Explore_no(Ti(n)):
Se (F(Ti(n)) ≤ melhor_medida) retorna; // se o nó não é promissor, não 
siga sua subárvore,pois tirar características desse subconjunto não vai 
aumentar F()
Se (n = D) então // F(Ti(n)) > melhor_medida, senão teria retornado acima 
melhor_medida ← F(Ti(n)) 
S ← Ti(n)
retorna //ie, melhor_medida é sempre de uma folha (com exceção da 
inicialização)
// para um nó não-folha ser avaliado, ele precisa ter um F maior do que a da 
melhor folha avaliada até o momento
Para todos (Tk(n-1) ⊂ Ti(n)) // filhos do nó Ti(n) 
Explore_no(Tk(n-1))
retorna
 
SISTEMAS DE
INFORMAÇÃO
47
47
47
47SISTEMAS DE
INFORMAÇÃO
47
47SISTEMAS DE
INFORMAÇÃO
47
47
47
Branch and bound
• Observações
• A função de avaliação utilizada deve ser 
monotonicamente crescente na dimensão
• Melhor usar com funções de avaliação baseadas 
em distância
• Encontra a solução ótima
• Apesar de não exaustivo, ainda pode ser 
computacionalmente intenso (dependendo de N e D)
• Pode dar o azar de ser exaustivo… quando?
• A árvore não precisa ser criada de verdade, é só uma 
representação lógica do que ocorre na recursão 
SISTEMAS DE
INFORMAÇÃO
48
48
48
48SISTEMAS DE
INFORMAÇÃO
48
48SISTEMAS DE
INFORMAÇÃO
48
48
48
Forma de percorrer o espaço de 
subconjuntos de características 
• Completo: encontra a solução ótima
 Exaustivo (testa todos os subconjuntos)
• Busca + backtracking (nem todos são avaliados)
• Ex: branch and bound, best first search, beam 
search
• Heurístico: incremental ou baseado em 
pesos
 
• Randômico: cada novo subconjunto é 
gerado aleatoriamente. 
• Definição de um número máximo de iterações
SISTEMAS DE
INFORMAÇÃO
49
49
49
49SISTEMAS DE
INFORMAÇÃO
49
49SISTEMAS DE
INFORMAÇÃO
49
49
49
Heurísticos 
 Backward selection: começa com todas as 
características; a cada iteração características são 
deletadas do subconjunto corrente
– Ex: sequential backward selection (SBS)
 Forward selection: começa com o conjunto vazio; 
a cada iteração novas características são 
adicionadas ao subconjunto corrente
– Ex: sequential forward selection (SFS)
• Forward-Backward: combinação de ambos
– Ex: plus t – take away r
• Weighting: durante a execução as características 
recebem pesos; no final são selecionadas as que 
têm peso maior que um limiar
SISTEMAS DE
INFORMAÇÃO
50
50
50
50SISTEMAS DE
INFORMAÇÃO
50
50SISTEMAS DE
INFORMAÇÃO
50
50
50
Heurísticos – 
Sequential Backward Selection
• Início: conjunto de N características (raiz da 
árvore) 
• A cada iteração: testa o novo subconjunto 
composto pelo subconjunto corrente – 
(menos) uma de cada característica. O novo 
subconjunto corrente será o melhor avaliado
• Continua até alcançar D características
• Figura (semelhante à da branch and bound)
SISTEMAS DE
INFORMAÇÃO
51
51
51
51SISTEMAS DE
INFORMAÇÃO
51
51SISTEMAS DE
INFORMAÇÃO
51
51
51
Heurísticos – 
Sequential Backward Selection
• Início: conjunto de N características (raiz da 
árvore) 
• A cada iteração: testa o novo subconjunto 
composto pelo subconjunto corrente – 
(menos) uma de cada característica. O novo 
subconjunto corrente será o melhor avaliado
• Continua até alcançar D características
• Figura (semelhante à da branch and bound)
• Problema:
SISTEMAS DE
INFORMAÇÃO
52
52
52
52SISTEMAS DE
INFORMAÇÃO
52
52SISTEMAS DE
INFORMAÇÃO
52
52
52
Heurísticos – 
Sequential Backward Selection
• Início: conjunto de N características (raiz da 
árvore) 
• A cada iteração: testa o novo subconjunto 
composto pelo subconjunto corrente – 
(menos) uma de cada característica. O novo 
subconjunto corrente será o melhor avaliado
• Continua até alcançar D características
• Figura (semelhante à da branch and bound)
• Problema: depois que uma característica sai, 
não entra mais
SISTEMAS DE
INFORMAÇÃO
53
53
53
53SISTEMAS DE
INFORMAÇÃO
53
53SISTEMAS DE
INFORMAÇÃO
53
53
53
Heurísticos – 
Sequential Forward Selection
• Início: conjunto vazio (raiz da árvore) 
• A cada iteração: testa o novo subconjunto 
composto pelo subconjunto corrente + uma 
de cada característica faltante. O novo 
subconjunto corrente será o melhor avaliado
• Continua até alcançar D características, ou o 
melhor de todos
SISTEMAS DE
INFORMAÇÃO
54
54
54
54SISTEMAS DE
INFORMAÇÃO
54
54SISTEMAS DE
INFORMAÇÃO
54
54
54
Heurísticos – 
Sequential Forward Selection
• Início: conjunto vazio (raiz da árvore) 
• A cada iteração: testa o novo subconjunto 
composto pelo subconjunto corrente + uma 
de cada característica faltante. O novo 
subconjunto corrente será o melhor avaliado
• Continua até alcançar D características
• Problema:
SISTEMAS DE
INFORMAÇÃO
55
55
55
55SISTEMAS DE
INFORMAÇÃO
55
55SISTEMAS DE
INFORMAÇÃO
55
55
55
Heurísticos – 
Sequential Forward Selection
• Início: conjunto vazio (raiz da árvore) 
• A cada iteração: testa o novo subconjunto 
composto pelo subconjunto corrente + uma 
de cada característica faltante. O novo 
subconjunto corrente será o melhor avaliado
• Continua até alcançar D características
• Problema: depois que uma característica 
entra, não sai mais
SISTEMAS DE
INFORMAÇÃO
56
56
56
56SISTEMAS DE
INFORMAÇÃO
56
56SISTEMAS DE
INFORMAÇÃO
56
56
56
Incremental forward
SISTEMAS DE
INFORMAÇÃO
57
57
57
57SISTEMAS DE
INFORMAÇÃO
57
57SISTEMAS DE
INFORMAÇÃO
57
57
57
Heurísticos – 
plus l – take away r (l > r)
• Início: conjunto vazio (raiz da árvore) 
• A cada iteração: 
• A) testa o novo subconjunto composto pelo 
subconjunto corrente + l novas características. O 
novo subconjunto corrente será o melhor avaliado 
dentre as várias possibilidades (de + l caract.)
• B) testa o novo subconjunto composto pelo 
subconjunto corrente – r características. O novo 
subconjunto corrente será o melhor avaliado 
dentre as várias possibilidades (de - r caract.)
SISTEMAS DE
INFORMAÇÃO
58
58
58
58SISTEMAS DE
INFORMAÇÃO
58
58SISTEMAS DE
INFORMAÇÃO
58
58
58
Heurísticos –Weighting
• Ex: RELIEF (distância euclidiana): (KIRA & RENDELL, 1992)
• Para cada instância (de um certo número de instâncias 
m) são encontrados:
– NearHit (instância mais próxima da mesma classe)
– NearMiss (instância mais próxima de classe 
diferente)
SISTEMAS DE
INFORMAÇÃO
59
59
59
59SISTEMAS DE
INFORMAÇÃO
59
59SISTEMAS DE
INFORMAÇÃO
59
59
59
Heurísticos –Weighting
• Ex: RELIEF (distância euclidiana):
• Para cada instância (de um certo número de instâncias 
m) são encontrados:
– NearHit (instância mais próxima da mesma classe)
– NearMiss (instância mais próxima de classe 
diferente)
• As características têm seus pesos atualizados, sendo 
consideradas:
– Mais relevantes se distinguem a instância de seu 
nearMiss
– Menos relevantes se distinguem a instância de seu 
nearHit
SISTEMAS DE
INFORMAÇÃO
60
60
60
60SISTEMAS DE
INFORMAÇÃO
60
60SISTEMAS DE
INFORMAÇÃO
60
60
60
Heurísticos –Weighting
Relief (Dataset, m, relevancia_min):
S = vazio //características selecionadas
Para j =1 a N Wj = 0 //pesos de cada uma das N características fj's
Para i =1 a m
Escolha aleatoriamente uma instância x no Dataset
Encontre seus NearHit e NearMiss (de um sorteio de instâncias)
Para cada característica fj, j = 1 a N
Wj = Wj – diff(xj, NearHitj)2 + diff(xj, NearMissj)2
Para j = 1 a N
 relevanciai = Wj / m
Se relevanciaj >= relevancia_min S = S “+” fj
Retorna S
SISTEMAS DE
INFORMAÇÃO
61
61
61
61SISTEMAS DE
INFORMAÇÃO
61
61SISTEMAS DE
INFORMAÇÃO
61
61
61
Heurísticos –Weighting
diff (xj, yj):
Se fj é uma variável nomimal:
diff(xj, yj) = 0 se xj = yj
1 caso contrário
Se fj é uma variável numérica:
diff(xj, yj) = (xj – yj) / nj 
no qual nj é um valor para normalizar diff em [0,1] 
SISTEMAS DE
INFORMAÇÃO
62
62
62
62SISTEMAS DE
INFORMAÇÃO
62
62SISTEMAS DE
INFORMAÇÃO
62
62
62
Heurísticos –Weighting
Relief (Dataset, m, relevancia_min):
S = vazio //características selecionadas
Para j =1 a N Wj = 0 //pesos de cada uma das N características fj's
Para i =1 a m
Escolha aleatoriamente uma instância x no Dataset
Encontre seus NearHit e NearMiss (de um sorteio de instâncias)
Para cada característica fj, j = 1 a N
Wj = Wj – diff(xj, NearHitj)2+ diff(xj, NearMissj)2
Para j = 1 a N
 relevanciai = Wj / m
Se relevanciaj >= relevancia_min S = S “+” fj
Retorna S
SISTEMAS DE
INFORMAÇÃO
63
63
63
63SISTEMAS DE
INFORMAÇÃO
63
63SISTEMAS DE
INFORMAÇÃO
63
63
63
Heurísticos –Weighting
Relief (Dataset, m, relevancia_min):
S = vazio //características selecionadas
Para j =1 a N Wj = 0 //pesos de cada uma das N características fj's
Para i =1 a m
Escolha aleatoriamente uma instância x no Dataset
Encontre seus NearHit e NearMiss (de um sorteio de instâncias)
Para cada característica fj, j = 1 a N
Wj = Wj – diff(xj, NearHitj)2 + diff(xj, NearMissj)2
Para j = 1 a N
 relevanciai = Wj / m
Se relevanciaj >= relevancia_min S = S “+” fj
Retorna S
SISTEMAS DE
INFORMAÇÃO
64
64
64
64SISTEMAS DE
INFORMAÇÃO
64
64SISTEMAS DE
INFORMAÇÃO
64
64
64
SISTEMAS DE
INFORMAÇÃO
65
65
65
65SISTEMAS DE
INFORMAÇÃO
65
65SISTEMAS DE
INFORMAÇÃO
65
65
65
SISTEMAS DE
INFORMAÇÃO
66
66
66
66SISTEMAS DE
INFORMAÇÃO
66
66SISTEMAS DE
INFORMAÇÃO
66
66
66
Randômicos
• Cada novo subconjunto é gerado 
aleatoriamente
• Exemplos:
• LVF – Las Vegas Filter
• Baseados em algoritmo genético
SISTEMAS DE
INFORMAÇÃO
67
67
67
67SISTEMAS DE
INFORMAÇÃO
67
67SISTEMAS DE
INFORMAÇÃO
67
67
67
Randômico – LVF 
(Las Vegas Filter)
Avalia um número pré-determinado de subconjuntos 
de características (MAX_TENTATIVAS)
• Cada subconjunto S é escolhido aleatoriamente 
(tamanho e elementos)
• Há a melhor solução corrente (Sbest)
• Cbest é a cardinalidade do subconjunto Sbest
• O próximo subconjunto só é analisado se sua 
cardinalidade for menor ou igual a Cbest
• Se sua análise for boa (taxa de inconsistência 
menor ou igual a um limiar), torna-se Sbest 
SISTEMAS DE
INFORMAÇÃO
68
68
68
68SISTEMAS DE
INFORMAÇÃO
68
68SISTEMAS DE
INFORMAÇÃO
68
68
68
Randômico – LVF 
(Las Vegas Filter)
Entrada: 
MAX_TENTATIVAS
D (dataset)
N (número total de características)
L (limiar de taxa de inconsistência)
Saída:
Subconjuntos (vários) que satisfazem o 
critério de inconsistência 
SISTEMAS DE
INFORMAÇÃO
69
69
69
69SISTEMAS DE
INFORMAÇÃO
69
69SISTEMAS DE
INFORMAÇÃO
69
69
69
Randômico – LVF 
(Las Vegas Filter)
• Critério de inconsistência (S, D)
• Duas instâncias são inconsistentes se seus valores das 
características de S são iguais mas suas classes não
• Considerando que existam q conjuntos de instâncias 
inconsistentes (cada conjunto contendo as instâncias com os 
mesmos valores das características S). Para cada conjunto:
• n instâncias inconsistentes = c1 + c2 + …. (onde ci é o 
número de instâncias da classe i neste conjunto)
• O contador de inconsistência deste conjunto = 
n-cmax, onde cmax = max (c1, c2, ….)
• Taxa de inconsistência = soma dos contadores de 
inconsistência dos q conjuntos / | D |
• Observação: não apropriado para valores contínuos de 
características
SISTEMAS DE
INFORMAÇÃO
70
70
70
70SISTEMAS DE
INFORMAÇÃO
70
70SISTEMAS DE
INFORMAÇÃO
70
70
70
Randômico – LVF 
(Las Vegas Filter)
Cbest = N
Para i = 1 até MAX_TENTATIVAS
S=sorteiaSubconjunto(semente)
C = cardinalidade(S)
se (C ≤ Cbest)
se (taxaInconsistencia(S, D) < L)
imprime (C, S)
se (C < Cbest)
Cbest = C 
 
SISTEMAS DE
INFORMAÇÃO
71
71
71
71SISTEMAS DE
INFORMAÇÃO
71
71SISTEMAS DE
INFORMAÇÃO
71
71
71
Randômico – LVF 
(Las Vegas Filter)
• Limiar L:
– Pode ser = taxaInconsistência (SA, D), onde 
SA é o conjunto de todas as características 
SISTEMAS DE
INFORMAÇÃO
72
72
72
72SISTEMAS DE
INFORMAÇÃO
72
72SISTEMAS DE
INFORMAÇÃO
72
72
72
Randômico – LVF 
(Las Vegas Filter)
Critério de parada?
• número máximo de tentativas (sugestão 
experimental: 77*N)
• Balanço entre tempo e qualidade da solução
• Na verdade pode-se parar a qualquer momento (e 
escolher o último subconjunto impresso)
SISTEMAS DE
INFORMAÇÃO
73
73
73
73SISTEMAS DE
INFORMAÇÃO
73
73SISTEMAS DE
INFORMAÇÃO
73
73
73
Randômico – Algoritmos Genéticos
Primeiro vamos entender a lógica por trás de 
algoritmos genéticos como um todo.
Finalidade: otimização aleatória → encontra uma boa 
solução (dentre as possíveis) percorrendo o 
espaço de busca de forma aleatória, mas usando 
um algoritmo mais sofisticado para sortear a 
próxima solução a ser analisada
SISTEMAS DE
INFORMAÇÃO
74
74
74
74SISTEMAS DE
INFORMAÇÃO
74
74SISTEMAS DE
INFORMAÇÃO
74
74
74
Randômico – Algoritmos Genéticos
• População de indivíduos (tamanho constante): amostra 
do espaço de busca (de soluções)
• Cada indivíduo (uma possível solução) é um 
“cromossomo” contendo “genes” (vetor de valores)
– No contexto de seleção de características:
N
SISTEMAS DE
INFORMAÇÃO
75
75
75
75SISTEMAS DE
INFORMAÇÃO
75
75SISTEMAS DE
INFORMAÇÃO
75
75
75
Randômico – Algoritmos Genéticos
• Cada indivíduo (uma possível solução) é avaliado 
por uma função fitness
• Os indivíduos mais aptos (com melhor avaliação) 
geram descendentes (que herdam parte de suas 
características)
• Crossover: mistura de 2 pais (origem a 2 filhos)
• Mutação: alteração de 1 pai
• Os indivíduos menos aptos morrem
• MAX_GERACOES: número de gerações que são 
produzidas (critério de parada)
SISTEMAS DE
INFORMAÇÃO
76
76
76
76SISTEMAS DE
INFORMAÇÃO
76
76SISTEMAS DE
INFORMAÇÃO
76
76
76
Randômico – Algoritmo Genético para 
Seleção de Características
[VAFAIE & IMAM, 1994]
• Indivíduo: vetor binário de tamanho n (0 na i-ésima 
posição indica a ausência da característica i, e 1 sua 
presença)
• Crossover: dada uma posição, concatena a primeira 
parte de um com a segunda parte de outro (gerando 2 
filhos distintos)
• Mutação: altera aleatoriamente um ou mais 
componentes de um pai
• Função fitness: desempenho do classificador 
(wrapper)
SISTEMAS DE
INFORMAÇÃO
77
77
77
77SISTEMAS DE
INFORMAÇÃO
77
77SISTEMAS DE
INFORMAÇÃO
77
77
77
SISTEMAS DE
INFORMAÇÃO
78
78
78
78SISTEMAS DE
INFORMAÇÃO
78
78SISTEMAS DE
INFORMAÇÃO
78
78
78
SISTEMAS DE
INFORMAÇÃO
79
79
79
79SISTEMAS DE
INFORMAÇÃO
79
79SISTEMAS DE
INFORMAÇÃO
79
79
79
SISTEMAS DE
INFORMAÇÃO
80
80
80
80SISTEMAS DE
INFORMAÇÃO
80
80SISTEMAS DE
INFORMAÇÃO
80
80
80
Em resumo...
• Cada algoritmo de seleção de características pode ser 
entendido a partir dessas informações:
– É do tipo filtro, camada ou embutido
– Qual função critério é utilizada? (pode ser a combinação 
de uma ou mais
– Como ele percorre o espaço de busca?
• Acha o ótimo dentre todas as combinações possíveis? 
(logo, a função critério deve avaliar o subconjunto 
como um todo)
• Usa alguma heurística para escolher um subconjunto? 
(selecionando heuristicamente cada subconjunto a ser 
avaliado, ou dando uma nota para cada característica 
separadamente e arbitrariamente escolhendo as 
melhores)
• De forma aleatória 
SISTEMAS DE
INFORMAÇÃO
81
81
81
81SISTEMAS DE
INFORMAÇÃO
81
81SISTEMAS DE
INFORMAÇÃO
81
81
81
Exemplos
• CFS: Correlation-based feature selection - 
características altamente correlacionadas com a classe 
alvo, porém pouco correlacionadas entre si (HALL, 1990)
• mRMR: Minimum Redundance Maximum Relevance - 
dois critérios: mínima redundância entre pares de 
caracteríssticas e relevância máxima por meio da medida 
de informação mútua (DING; PENG, 2005)
SISTEMAS DE
INFORMAÇÃO
82
82
82
82SISTEMAS DE
INFORMAÇÃO
82
82SISTEMAS DE
INFORMAÇÃO
82
82
82
Atividade 3 (para 01/09)
Seleção de características usando ao menos método à 
escolha (se 2 ou mais, de preferência o mais distintos 
possível) 
Métodos: uso de quais rotinas, parâmetros utilizados e 
por quê, outras informações relevantes
 Por ex: no caso do Relief, como selecionou as 
características com base nos pesos e por quê 
Resultados: quantas e quais características foram 
selecionadas
Discussão: o que você achou dos resultados? Reduziu 
bastante? 
SISTEMAS DE
INFORMAÇÃO
83
83
83
83SISTEMAS DE
INFORMAÇÃO
83
83SISTEMAS DE
INFORMAÇÃO
83
83
83
Observações sobre o trabalho
- Para a maioria dos métodos de seleção de 
características precisa usar uma colunade 
classificação (supervisionados)
SISTEMAS DE
INFORMAÇÃO
84
84
84
84SISTEMAS DE
INFORMAÇÃO
84
84SISTEMAS DE
INFORMAÇÃO
84
84
84
Referências
• DASH, M., LIU, H., Feature Selection for Classification. 
Intelligent Data Analysis 1, 131-156, 1997.
• DING, C.; PENG, H. Minimum redundancy feature selection 
from microarray gene expression data. Journal of 
bioinformatics and computational biology, World Scientic, 
v.3, n. 02, p. 185-205, 2005.
• HALL, M. A. Correlation-based feature selection for machine 
learning. University of Waikato Hamilton, 1999.
• LIU, H., SETIONO, R., A Probabilistic Approach to Feature 
Selection - A Filter Solution. In: Proceedings of International 
Conference on Machine Learning, 319-327, 1996. (alg. LVF)
• VALFAIE, H., IMAM, I.F., Feature selection methods: genetic 
algorithms vs. greedy-like search. In: Proceedings of the 
International Conference on Fuzzy and Intelligent Control 
Systems, 1994
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84