FEATURE SELECTION
Introdução


Estudo de metodologias relacionadas a seleção de
atributos
Maldição da dimensionalidade


O número de atributos do desenvolvedor do sistema de
classificação é geralmente muito grande
Necessidade de reduzir o número de atributos a um
mínimo suficiente
Complexidade Computacional
 Duas características : individual x combinada
 Grande número de parâmetros dos classificadores

Preprocessing

Outlier Removal


Normalização dos dados


Um outlier é definido como um ponto que está muito longe
da média da variável aleatória correspondente
Normalizar os atributos de modo que seus valores fiquem
dentro de um intervalo similar
Dados desconhecidos

Tornar o número de dados válidos os mesmos para todos os
atributos
Descartar
 Substituir

Seleção de atributos a partir de Testes
de Hipótese

Testar cada atributo individualmente

Sua capacidade discriminatória para o problema em
questão
Descartar facilmente más escolhas
 Utilizar as técnicas mais elaboradas


x : variável aleatória representando um atributo.
Verificaremos se seus valores para classes diferentes se
diferem significativamente
H I : Os valores se diferem significativamente
 Ho: Os valores não se diferem significativamente

Seleção de atributos a partir de Testes
de Hipótese





Iremos calcular a diferença pl - p2 entre as médias dos valores de um
atributo em duas classes.
Se xi, i = 1,2, . . . , N, são os valores de um atributo na classe w1 e
possuem média µ1.
De maneira correspondente, temos µ2 para a classe w2.
Assuma que a variância dos valores do atributo nas duas classes é
igual a s1² = s2² = s².
Para tomar a decisão baseados na proximidade dos valores das duas
médias, iremos realizar um teste de hipótese:
Exemplo de Aplicação
Exemplo de valores de duas classes:

Esse atributo possui informações suficientes?
Iremos testar quando os valores do atributo nas duas classes
diferem de maneira significativa.
 O nível de significância é p = 0.05.
Em seguida temos:

Para N = 10 nós temos:

Retirados da tabela...


Exemplo de Aplicação



D = [-xp, xp] = [-3.2, 3.2]
Visto que 4.25 reside fora do intervalo D, decidimos
a favor de HI; isto é, o valor das médias diferem
significantemente no nível 0.05.
Logo, o atributo é selecionado.
The Receiver Operating Characteristics
CROC Curve


Análise de informações sobre a sobreposição de duas
classes.
Essa decisãoé associada a um erro de probabilidade, a, por obter uma decisão
errada em relação à classe w1 (a probabilidade de uma decisão correta é 1 – a)
e corresponde à área sombreada na curva.
The Receiver Operating Characteristics
CROC Curve

Quanto menor a sobreposição das classes, maior a
área entre a curva e a linha reta.
Medidas de Separação de Classes




Alguns atributos possuem dependência ou influência
sobre os valores de outros.
Os métodos de discriminação de atributos não
levam em conta as co-relações entre atributos.
Classificação acaba sendo influenciada pela
aparente falta de relação entre atributos.
Como medir a efetividade da discriminação dos
vetores de atributos.
Divergência

Regra de Bayes.
duas classes w1 e w2 e um vetor de
características x, selecionamos w1 se:
 Dadas


Logo, a razão
pode nos mostrar informações
úteis a respeito da capacidade disriminatória associada ao
vetor x.
Para classes completamente sobrepostas essa razão é igual
a zero.
Divergência


Já que x pode assumir diferentes valores…
A soma d12 = D12 + D21 é conhecida como
divergência.
medidas de separação das classes w, em relação
ao vetor x.
 As
Divergência


Para um problema com várias classes a divergência é
calculada para cada par de classes, wi e wj.
Assumindo que as funções de densidade são Gaussianas
N(mi, ∑i ) e N(mj, ∑j ) respectivamente, o cálculo da
divergência pode ser simplificado:
 Se as matrizes de covariância das duas distribuições
Gaussianas são iguais, então
∑i
e

=∑j=∑
Divergência


Não é possível, para distribuições mais gerais, uma relação direta da
divergência com o erro bayesiano.
Dependências específicas do valor da divergência entre os vetores
médios pode levar a resultados equivocados.
 Para evitar isso, uma variação da divergência foi criada, é chamada de
divergência transformada:
Limite de Chernoff

O mínimo erro de classificação alcançado pelo classificador de Bayes
para duas classes w1 e


w2 é:
Um limite superior pode ser derivado baseado na igualdade:
Combinando as duas expressões chegamos à expressão conhecida
como Limite de Chernoff.
Distância de Bhattacharyya



O limite mínimo pode ser calculado minimizando ECB em relação a s.
Uma forma especial desse limite é encontrada para s = ½ :
Para as distribuições gaussianas N(mi, ∑i ) e N(mj, ∑j ) e após alguns
cálculos, obtemos:
O termo B é conhecido como Distância de Bhattacharyya e é usado
como uma medida de separação de classes. e corresponde ao Limite
de Chernoff otimizado quando ∑i = ∑j
Scatter Matrices


Isso é bruxaria!

Seleção de Subconjuntos de
Características


Após definir os critérios, temos que selecionar um
subconjunto de l atributos.
Scalar Feature Selection
Adotar qualquer critério de medida de separabilidade de
classes.
 O valor do critério C(k) é computado para cada atributo,
k =1, 2, . . ., m.
 Os atributos são ordenados em ordem decrescente de
valores do C(k).
 Os l melhores valores são selecionados para formar o
feature vector.

Seleção de Subconjuntos de
Características

Scalar Feature Selection
Divergência unidimensional é um critério para computar o
C(k).
 Esse critério é executado para todos pares de classes.
 Para cada um dos atributos, o C(k) correspondente
é igual a:
que é o menor divergence value de
todas as classes
