Introdução aos métodos de seleção de atributos
Exemplos, prós e contras, saiba alguns conceitos fundamentais
A redução da dimensionalidade de um conjunto de dados é um aspecto muito relevante, ainda mais quando consideramos a grande quantidade de dados que continua a crescer em diversas áreas. Ela nos ajuda a combinar ou selecionar atributos, permitindo o trabalho subsequente com uma dimensão reduzida, mas bem proveitosa do conjunto de dados original.
Dessa forma conseguimos evitar a famosa maldição da dimensionalidade. Esse artigo busca explorar alguns métodos de seleção de atributos para reduzir a dimensionalidade.
Algoritmos completos
Essa categoria busca a solução ótima e tem duas subdivisões:
- Exaustivo, todos os subconjuntos são testados;
- Busca e backtracking, alguns subconjuntos são testados.
Vamos agora implementar alguns métodos básicos.
Branch and bound
É escolhido um determinado número D de características do total N, e uma boa escolha para esse D normalmente é a raiz quadrada de N.
Os dados são então organizados em forma de árvore, onde:
- Cada nó representa um subconjunto de características;
- A raiz possui todas as características (N);
- Um nó filho tem uma característica a menos que seu pai;
- Folhas tem subconjuntos com D características.
A busca em profundidade será feita para achar o nó melhor avaliado. Para isso será definida uma função de avaliação, que como critério deve ser monotonicamente crescente na dimensão, ou seja, o seu resultado de avaliação deve acompanhar a quantidade de atributos. Para isso funções de avaliação baseadas em distância são uma boa escolha.
Então considere que estamos avaliando uma árvore, esse critério também nos permite deduzir que determinados nós com avaliações inferiores à minha melhor medida atual e com quantidade de atributos igual ou maior sequer merecem ser avaliados. 😃
Algumas observações sobre esse método:
- Dependendo da configuração da árvore, ele pode ser exaustivo (caso os nós com maior número de atributos estejam sempre à esquerda e as notas deles sejam maiores que os nós à esquerda);
- Apesar de não necessariamente ser exaustivo, ele ainda pode ser computacionalmente intenso, dependendo dos valores de N e D;
- A árvore não precisa ser criada de fato, é apenas uma organização lógica que ajuda no entendimento.
Algoritmos heurísticos
Esses algoritmos não olham todos os subconjuntos de atributos, mas utilizam heurísticas para determinar o comportamento de busca.
Eles são divididos em duas categorias: incrementais e baseados em pesos.
Incremental — Forward selection
A cada iteração novas características são adicionadas ao subconjunto atual, um exemplo seria o Sequential Forward Selection (SFS).
Esse algoritmo constrói uma árvore, começando com um conjunto vazio na raiz e adiciona um novo nó composto pelo subconjunto atual + um novo atributo faltante, e caso melhor avaliado ele se torna o novo subconjunto atual.
Essa construção da árvore é feita até alcançar um conjunto predefinido de D características ou até terminar de adicionar todos os atributos.
Temos o problema de depois que uma característica entra, ela não sai, mesmo que ela não fosse tão relevante pode ser que ela faça parte do subconjunto ótimo selecionado.
Incremental — Backward selection
A cada iteração características são deletadas do subconjunto atual, um exemplo seria o Sequential Backward Selection (SBS).
Possui lógica parecida com o algoritmo anterior, mas faz o caminho contrário, começa com uma árvore com todas as características na raiz e vai removendo uma característica em cada nós, sendo que o melhor avaliado se torna o nó atual.
Também é realizado até até um conjunto predefinido D ou até todas as características serem testadas.
Também possuí o problema de ser guloso, depois que uma característica saí, ela não entra mais.
Incremental — Forward-Backward
Combinação dos dois anteriores, um exemplo seria plus t — take away r.
Busca resolver os problemas anteriores, adicionando t características e removendo r características em cada nó.
Incremental — MRMR
Minimum redundance maximum relevance busca explorar o ponto de que alguns algoritmos incrementais podem permitir redundância, então ele busca minimizar a redundância ao mesmo tempo que busca as características com maior relevância, dessa forma ele é baseado na informação mútua dos atributos em relação à classe.
A cada iteração ele seleciona um novo atributo que cumpra dois requisitos:
- Minimizar a informação mútua do atributo atual em relação aos já selecionados;
- Maximizar a informação mútua entre o atributo atual e a classe.
Baseado em peso — Relief
Durante a execução são atribuídos pesos às características, no final são selecionadas as que têm peso maior que um limiar.
Dentro de um certo número de instâncias são sorteados dois elementos para cada uma:
- Near hit (instância mais próxima da mesma classe);
- Near miss (instância mais próxima de classe diferente).
E os atributos tem seus pesos atualizados considerando mais relevantes se distinguem a instância de seu near miss e menos relevantes se distinguem a instância do seu near hit.
Um algoritmo que é mais utilizado atualmente, baseado no Relief é o Relief-F que utiliza um conjunto de near hits e near miss ao invés de uma unidade apenas para cada um. Além de diminuir os ruídos, ele também consegue lidar com dados faltantes e é multi classe.
Nesse algoritmos Relief é levado em consideração o efeito combinado das características, o que pode ser bom. Entretanto ele não consegue detectar redundância entre características relevantes.
Randômicos
Nos métodos randômicos o novo subconjunto a ser avaliado é gerado aleatoriamente.
LVF — Las Vegas Filter
Avalia um número pre-determinado de subconjunto de características, sendo que cada subconjunto é escolhido aleatoriamente em tamanho e elementos.
Analisa os próximos subconjuntos apenas se sua cardinalidade for menor ou igual à cardinalidade do subconjunto atual (melhor até agora).
Sua análise de cada subconjunto é realizada com base na taxa de inconsistência, que verifica e igualdade dos valores de suas características em relação à igualdade dos valores das classes. A taxa de inconsistência é a soma de todos os contadores de inconsistência dividido pelo número de contadores.
No final da análise retorna uma lista de subconjuntos que cumpram o limiar do critério de inconsistência.
Esse método não é apropriado para valores contínuos, pois a chance de valores contínuos serem iguais entre as instâncias seria baixa, então precisaríamos de variáveis discretizadas.
O limiar padrão definido por alguns altores é 0, mas também pode ser a inconsistência já definida no conjunto de dados.
O critério de parada foi empiricamente definido pelos autores como 77 * N, que traz um balanço entre o tempo e a qualidade da solução.
Baseado em algoritmos genéricos
A ideia dessa categoria de algoritmos é combinar as soluções de subconjuntos de dados criando novas para conseguir encontrar as soluções otimizadas (ideia de evolução).
Cada indivíduo é avaliado por uma função fitness, os mais aptos geram descendentes (que herdam as características) e os menos aptos morrem.
Então acontece o crossover, onde metade dos atributos são alterados de acordo com os pais. E a mutação, onde são inseridas mudanças mais pontuais em cada pai.
Gostou do conteúdo?
Siga a Luna no Medium. E não se esqueça de deixar alguns aplausos 👏🏽Qualquer dúvida ou sugestão é só deixar nos comentários!
