• Português
  • English
  • Español
  • k-Nearest Neighbors

    Por: em 10 de abril de 2018

    Problemas de classificação surgem das diversas necessidades de categorização existentes na sociedade – como, por exemplo, gênero e classe social – ou para responder questões de negócios (como determinar se uma pessoa possui ou não um bom perfil de crédito?). No DataLab, utilizamos diversos modelos de classificação tanto para melhorar os modelos de perfil já existentes quanto para projetos completamente inovadores, como o projeto Sunny, em que a detecção de telhados é parte fundamental do processo de viabilidade de instalação de painéis solares. Nesse caso, queremos determinar se cada pixel de uma determinada imagem é um telhado ou não e, para esse problema, foram aplicados métodos de classificação.

    Neste post, vamos discutir um pouco sobre o algoritmo de classificação k-Nearest Neighbors (kNN): um método muito simples, mas que pode gerar ótimos resultados quando aplicado em bases de dados com pouca dimensionalidade.

    O modelo kNN é tão simples quanto seu nome. Para cada exemplo a ser classificado, escolhemos no conjunto de treino (aquele em que sabemos qual os rótulos reais) os k exemplos mais próximos. Dentre os k exemplos mais próximos, a classe mais frequente é a predição do modelo.

    Figura 1: Nessa imagem vemos que há o mesmo número de exemplos de cada classe entre os 4 vizinhos mais próximos, quando há empate escolhemos aleatoriamente.

    A forma de classificação pode ser melhorada usando a distância para os vizinhos como peso ou utilizando outras distâncias. A escolha de um k ótimo para uma base de dados deve ser feita com o processo cross-validation. É importante lembrar, ao utilizar o kNN, do fato de que ele leva em conta a estrutura local dos seus dados. Caso não exista nenhuma estrutura aparente, provavelmente ele não será o melhor modelo para o problema.

    Isso nos leva ao problema principal do kNN, que é a baixa performance em modelos com alta dimensionalidade, ou seja, modelos que possuem muitas variáveis (features) – isso é conhecido como “a maldição da dimensionalidade” (the curse of dimensionality). Quando aumentamos muito a dimensionalidade de nosso problema, a informação, tipicamente, fica esparsa e perde suas estruturas locais. Temos que olhar para vizinhos que estão muito longe e não representam verdadeiramente as classes que pertencem.

    O kNN é um exemplo de modelo não-paramétrico, ou seja, é um modelo que não possui um número fixo de parâmetros. Ele depende do número de exemplos que estão disponíveis para comparação. Isso pode se mostrar muito prático quando queremos algo rápido e simples, porém pode se tornar um problema quando o tamanho do conjunto de treinamento é muito grande.

    Aplicação do kNN em Classificação de terrenos

    A base de dados STATLOG-LANDSAT é uma base gerada pela NASA de imagens de satélite de vários canais. Essas imagens são tiradas de uma área rural australiana, específica para atividade agrícola, em que se deseja saber qual é o tipo de uso de cada região, como plantação de algodão, solo vermelho ou solo cinza.

    As features foram construídas com os valores dos 4 canais disponíveis: vermelho, verde, azul e infravermelho. Selecionamos todos os valores dos pixels adjacentes e o próprio pixel a ser classificado. A figura abaixo exemplifica como um vetor de features é criado.

     

    X=(R1,G1,B1,I1,…,R8,G8,B8,I8,Rx,Gx,Bx,Ix)

    O desempenho do kNN nessa forma possui uma taxa de erro de 9.5%. A Figura 2 mostra como os resultados são exibidos.

     

     

    Figura 2: As primeiras 4 imagens representam cada um dos canais, a duas últimas imagens são o uso real e o uso predito do terreno.
     

    Referências

    Friedman, J., Hastie, T., & Tibshirani, R. (2001). The elements of statistical learning (Vol. 1, pp. 337-387). New York: Springer series in statistics. (https://web.stanford.edu/~hastie/ElemStatLearn/)

    Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. Adaptive Computation and Machine Learning. (https://www.cs.ubc.ca/~murphyk/MLbook/)

    10 de abril de 2018

    Filtre por mês

    Filtre por autor