antonino

O K-NN é um dos algoritmos mais simples e intuitivos de classificação. Ele não assume nenhuma forma paramétrica para os dados. Primeiramente, o algoritmo armazena todos os exemplos de treinamento. Durante a classificação, ele calcula a distância do novo ponto para todos os exemplos armazenados. Em seguida, seleciona os K exemplos mais próximos (vizinhos). A classe mais frequente entre estes K vizinhos define a classificação. Por exemplo, com K=3, dois vizinhos da classe A e um da classe B resulta em A. Portanto, o K-NN é um método baseado em instâncias (lazy learning).

escolha do parâmetro k e métricas de distância

A escolha do parâmetro K é crucial para o desempenho do algoritmo. Valores pequenos de K (ex: 1) tornam o modelo sensível a ruídos. Valores grandes de K, por outro lado, suavizam demais as fronteiras de decisão. A validação cruzada ajuda a encontrar o K ótimo para cada problema. Além disso, a métrica de distância também impacta o resultado. A distância euclidiana é a mais comum e intuitiva. Para dados categóricos, a distância de Hamming pode ser mais adequada. Em espaços de alta dimensão, a distância de Manhattan às vezes supera a euclidiana. Portanto, normalize os atributos para que todos tenham a mesma escala. Atributos com escalas maiores dominariam a distância indevidamente.

vantagens e limitações do k-nn

O K-NN oferece várias vantagens importantes para classificação. Primeiramente, ele é extremamente simples de entender e implementar. Não requer treinamento explícito, apenas armazenamento dos dados. Além disso, o algoritmo é naturalmente multiclasse e não-linear. Ele pode modelar fronteiras de decisão complexas e arbitrárias. Contudo, o K-NN tem limitações significativas. O custo computacional na classificação é alto (O(N)). Para cada novo ponto, calcula-se distância para todos os exemplos de treinamento. Outra desvantagem é a necessidade de armazenar todo o conjunto de treinamento. Em grandes bases de dados, isto consome muita memória. Além disso, o K-NN sofre com a maldição da dimensionalidade. Em altas dimensões, a distância entre os pontos torna-se menos discriminativa.

quando utilizar o classificador k-nn

Utilize o K-NN quando o conjunto de treinamento for moderadamente pequeno. Por exemplo, até alguns milhares de exemplos. Outra aplicação adequada é quando as fronteiras de decisão são complexas. O K-NN também funciona bem como baseline para problemas mais elaborados. Por exemplo, sistemas de recomendação usam K-NN para encontrar itens similares. Reconhecimento de dígitos manuscritos é outro caso clássico de sucesso. Contudo, evite o K-NN em bases de dados muito grandes (milhões de exemplos). O custo computacional na predição torna-se proibitivo. Nestes casos, use redes neurais ou árvores de decisão. Além disso, evite o K-NN em espaços de altíssima dimensão (centenas de atributos). A redução de dimensionalidade (PCA) pode ser aplicada como pré-processamento. Em resumo, escolha o K-NN pela sua simplicidade e eficácia em problemas de pequena e média escala.

O classificador Bayesiano representa a solução estatisticamente ótima para classificação. Ele minimiza a probabilidade média de erro de decisão. Primeiramente, o método utiliza o teorema de Bayes para calcular probabilidades a posteriori. A classe com a maior probabilidade a posteriori é a escolhida. Por exemplo, se P(c1|x) > P(c2|x), escolhemos a classe c1. O classificador considera tanto a verossimilhança dos dados quanto as probabilidades a priori. Consequentemente, ele incorpora conhecimento prévio sobre a ocorrência das classes. Portanto, o classificador Bayesiano é a referência teórica contra a qual outros métodos são comparados.

função de decisão e regra de bayes

A regra de decisão de Bayes maximiza a probabilidade a posteriori. Primeiramente, calculamos P(cj|x) = P(x|cj) * P(cj) / P(x). O denominador P(x) é comum a todas as classes e pode ser ignorado. Portanto, maximizar P(x|cj) * P(cj) é suficiente para a decisão. A função discriminante Bayesiana tem a forma dj(x) = P(x|cj) * P(cj). Para dados Gaussianos, esta função torna-se uma quadrática. Quando as covariâncias são iguais, a função simplifica para uma forma linear. O classificador de mínima distância é um caso especial do Bayesiano. Ele assume covariâncias iguais e probabilidades a priori iguais.

estimando parâmetros e a maldição da dimensionalidade

Na prática, as densidades P(x|cj) são desconhecidas e precisam ser estimadas. Geralmente, assume-se uma distribuição Gaussiana (normal) para os dados. Os parâmetros a estimar são o vetor de médias (μj) e a matriz de covariância (Σj). As amostras de treinamento fornecem as estimativas destes parâmetros. Por exemplo, μj é a média das amostras da classe j. Contudo, o número de parâmetros cresce quadraticamente com a dimensionalidade. Para dados de alta dimensão, precisamos de muitas amostras para estimativas precisas. Este fenômeno é conhecido como a “maldição da dimensionalidade”. Portanto, técnicas de redução de dimensionalidade (como PCA) são frequentemente aplicadas antes do classificador Bayesiano.

quando utilizar o classificador bayesiano

Utilize o classificador Bayesiano quando as suposições Gaussianas forem razoáveis. Por exemplo, dados de sensores que seguem distribuições normais. Outra aplicação é em problemas com poucas dimensões (menos de 20). O método também é excelente quando as probabilidades a priori são conhecidas. Por exemplo, em controle de qualidade, a taxa de defeitos é conhecida antecipadamente. Contudo, evite o classificador Bayesiano em dados de alta dimensão com poucas amostras. Redes neurais ou SVM podem generalizar melhor nestes casos. Além disso, quando os dados não seguem uma distribuição Gaussiana, o desempenho degrada. Versões não-paramétricas (como Parzen) podem ser usadas, mas são mais caras. Em resumo, escolha o classificador Bayesiano pela sua base teórica sólida e desempenho ótimo sob as suposições corretas.