Quando devo ir além de k vizinho mais próximo

9

Para muitos projetos de aprendizado de máquina que realizamos, começamos com o classificador k vizinho mais próximo. Este é um classificador inicial ideal, pois geralmente temos tempo suficiente para calcular todas as distâncias e o número de parâmetros é limitado (k, distância métrica e ponderação)

No entanto, isso geralmente tem o efeito de mantermos o classificador knn, pois mais adiante no projeto não há espaço para alternar para outro classificador. O que seria um bom motivo para tentar um novo classificador. Os óbvios são restrições de memória e tempo, mas há casos em que outro classificador pode realmente melhorar a precisão?

neural-networks classification
fonte
Isso é puramente acadêmico ou deve ser usado na indústria?
Dr. Rob Lang
11
A maioria dos nossos aplicativos são implantados na indústria (para consumo de memória e tempo de cálculo são questões)

Respostas:

3

O k-NN generaliza em um sentido muito restritivo. Simplesmente usa anteriores de suavidade (ou suposição de continuidade). Essa suposição implica que os padrões que estão próximos no espaço de recurso provavelmente pertencem à mesma classe. Nenhuma regularidade funcional na distribuição de padrões pode ser recuperada pelo k-NN.

Portanto, requer amostras de treinamento representativas, que podem ser extremamente grandes, especialmente em casos de espaços de características altamente dimensionais. Pior, essas amostras podem estar indisponíveis. Conseqüentemente, ele não pode aprender invariantes. Se os padrões puderem ser submetidos a algumas transformações sem alterar seus rótulos, e a amostra de treinamento não contiver padrões transformados de todas as maneiras admissíveis, o k-NN nunca reconhecerá padrões transformados que não foram apresentados durante o treinamento. Isso é verdade, por exemplo, para imagens deslocadas ou giradas, se elas não estiverem representadas de alguma forma invariável antes de executar o k-NN. O k-NN não pode sequer abstrair de recursos irrelevantes.

Outro exemplo um tanto artificial está a seguir. Imagine esse padrão pertencente a diferentes classes distribuídas periodicamente (por exemplo, de acordo com seno - se for menor que 0, os padrões pertencerão a uma classe e, se for maior, os padrões pertencerão a outra classe). O conjunto de treinamento é finito. Portanto, ele estará localizado em uma região finita. Fora desta região, o erro de reconhecimento será de 50%. Pode-se imaginar a regressão logística com funções básicas periódicas que terão um desempenho muito melhor neste caso. Outros métodos serão capazes de aprender outras regularidades na distribuição de padrões e extrapolar bem.

Portanto, se alguém suspeitar que o conjunto de dados disponível não é representativo e a invariância a algumas transformações de padrões deve ser alcançada, esse é o caso, no qual se deve ir além do k-NN.


fonte
Obrigado pela sua resposta (e obrigado BartoszKP por tentar melhorá-lo). É verdade que o knn não consegue encontrar padrões que exijam transformação (a menos que você comece a usar uma métrica de distância estranha (e incorreta)). Essa é uma boa razão para tentar outro classificador, acho que o svm é uma escolha óbvia. Não estou suficientemente familiarizado com o svm para dizer, mas não exigiria conhecimento específico sobre o padrão que você está procurando para definir o kernel?
Sim. A escolha do kernel dependerá dos padrões. O kernel gaussiano terá propriedades semelhantes ao método k-NN. Outros kernels padrão também podem parecer inadequados. No entanto, pelo menos, pode-se tentar usá-los.
Conforme implícito por @ Necro0x0Der, qualquer melhoria nesse sentido dependeria do padrão (no exemplo senoidal, periodicidade) ser natural para a parametrização. Ou seja, a parametrização (escolha do kernel) define a estrutura (efetivamente, a métrica) do espaço de representação. Se você pode determinar (talvez por suposição instruída) alguma estrutura apropriada por alguns meios, tente parametrizar o padrão adequadamente. Observe que, no final, isso permite que seu classificador encontre prontamente certos tipos de recursos relevantes.
3

Se você se restringir à complexidade computacional, as árvores de decisão (Quinal, 1986) são difíceis de superar (especialmente quando uma estrutura oferece conversão direta do modelo DT para váriasif instruções - como o Accord.NET ).

Para dados de alta dimensão, a noção de distância, na qual se baseia o k-NN, se torna inútil (Kriegel, Kröger, Zimek, 2009) (também: artigo da Wikipedia ). Portanto, outros classificadores, como SVM (Corter, Vapnik, 1995) ou Random Forests (Breiman, 2001) , podem ter um desempenho melhor.

Referências:

BartoszKP
fonte
A alta dimensão não é um limite fixo, é claro, na maioria dos casos, nossos recursos são suficientemente expressivos para que a distância funcione. Claro que isso pode ser um ponto importante. Talvez eu devesse ter esclarecido com um exemplo. Digamos que tenhamos um classificador com precisão de 93%, isso é aceitável, mas agora podemos tentar melhorar o classificador ou encontrar novos recursos. Tudo depende dos novos recursos e dados possíveis, mas eu estava procurando orientações sobre essa decisão.
@Rhand Parece-me que é uma decisão no nível de gerenciamento de projetos. Se a solução atual é aceitável, por que mexer com ela? É uma perda de tempo. Se não for aceitável, defina com mais precisão o que você deseja melhorar (velocidade, precisão, etc.).
BJSKPP:
Não é apenas o gerenciamento de projetos, a questão é como obter uma precisão máxima (isso é na minha pergunta) e qual direção é a melhor a ser tomada. Você sugere svm e floresta aleatória porque a dimensionalidade pode ser muito alta, é uma possibilidade com a qual eu poderia experimentar para ver se a precisão melhora e esse é o tipo de resposta que eu estava procurando.
Bem, isso, por outro lado, é uma questão muito ampla. Não há regras gerais de que o classificador X seja melhor que Y. Você deve apenas tentar um número de classificadores e executar validação cruzada para seleção de modelo, por exemplo.
BJSBKPPP
3

kNN é útil para grandes amostras de dados

No entanto, suas desvantagens são:

  1. Enviesado pelo valor de k.
  2. Complexidade da computação
  3. Limitação de memória
  4. Sendo um algoritmo de aprendizado supervisionado preguiçoso
  5. Facilmente enganado por atributos irrelevantes.
  6. A precisão da previsão pode diminuir rapidamente quando o número de atributos aumenta.

Geralmente, só é eficaz se os dados de treinamento forem grandes e o treinamento for muito rápido.

Iancovici
fonte
Eu não estou olhando para clustering, mas de classificação
@Rhand aqui vamos nós, obrigado pela iliasfl nota
Iancovici