Lidar com laços, pesos e votação em kNN

Estou programando um algoritmo kNN e gostaria de saber o seguinte:

Tie-breaks:

1. O que acontece se não houver um vencedor claro na votação majoritária? Por exemplo, todos os k vizinhos mais próximos são de classes diferentes, ou para k = 4 existem 2 vizinhos da classe A e 2 vizinhos da classe B?
2. O que acontece se não for possível determinar exatamente k vizinhos mais próximos porque existem mais vizinhos com a mesma distância? Por exemplo, para a lista de distâncias (x1;2), (x2;3.5), (x3;4.8), (x4;4.8), (x5;4.8), (x6;9.2), não seria possível determinar k = 3 ou k = 4 vizinhos mais próximos, porque o terceiro ao quinto vizinhos têm todos a mesma distância.

Pesos:

1. Eu li que é bom ponderar os vizinhos mais próximos antes de selecionar a classe vencedora. Como isso funciona? Ou seja, como os vizinhos são pesados ​​e como é então determinada a classe?

Alternativas de votação por maioria:

1. Existem outras regras / estratégias para determinar a classe vencedora além do voto da maioria?

A maneira ideal de romper um empate para um vizinho mais próximo k , na minha opinião, seria diminuir k em 1 até que você rompa o empate. Isso sempre funcionará independentemente do esquema de ponderação dos votos, já que um empate é impossível quando k = 1. Se você aumentar k , dependendo do seu esquema de ponderação e do número de categorias, não poderá garantir o desempate.

Ao fazer o kNN, você deve ter em mente uma coisa, a saber, que não é um algoritmo estritamente derivado matematicamente, mas um simples classificador / regressor baseado em uma intuição - a função subjacente não muda muito quando os argumentos não mudam Muito de. Ou, em outras palavras, a função subjacente é localmente quase constante. Com essa suposição, é possível estimar o valor da função subjacente em qualquer ponto, por uma média (possivelmente ponderada) dos valores dos k pontos mais próximos.

Tendo isso em mente, você pode perceber que não há um imperativo claro sobre o que fazer quando não há um vencedor claro na votação majoritária. Você sempre pode usar um k ímpar ou usar uma ponderação injetiva.

No caso dos vizinhos 3 a 5 estarem à mesma distância do ponto de interesse, você pode usar apenas dois ou usar todos os 5. Novamente, lembre-se de que o kNN não é um algoritmo derivado de complexa análise matemática, mas apenas um intuição simples. Cabe a você como deseja lidar com esses casos especiais.

$\frac{1}{||x-y||^2}$

Também houve um bom artigo de Samory Kpotufe e Abdeslam Boularias este ano sobre o NIPS abordando a questão de encontrar a ponderação correta. Sua intuição geral é que a função subjacente varia de maneira diferente em direções diferentes (isto é, suas diferentes derivadas parciais são de magnitude diferente); portanto, seria sensato alterar, em certo sentido, as métricas / ponderações de acordo com essa intuição. Eles afirmam que esse truque geralmente melhora o desempenho da regressão do kNN e do kernel, e acho que eles ainda têm alguns resultados teóricos para respaldar essa afirmação (embora eu não tenha certeza do que esses resultados teóricos realmente afirmam, não tive tempo para ir) em todo o artigo). O documento pode ser baixado gratuitamente em seus sites ou após pesquisar no Google "Pesos de gradiente ajudam a regressores não paramétricos".

Agora, você provavelmente desejará saber como encontrar a ação correta de k, métrica, ponderação e ação a ser executada quando houver empates e assim por diante. O triste é que, basicamente, é difícil chegar aos hiperparâmetros certos após uma reflexão profunda, você provavelmente precisará testar diferentes grupos de hiperparâmetros e ver quais funcionam bem em algum conjunto de validação. Se você possui alguns recursos computacionais e deseja chegar automaticamente aos parâmetros corretos em um bom conjunto de hiperparâmetros, existe uma ideia recente (de que eu gosto muito) de usar processos gaussianos para otimização sem derivação nesse cenário.

Deixe-me elaborar - encontrar o conjunto de hiperparâmetros (isto é, que minimiza o erro nos dados de validação) pode ser visto como um problema de otimização. Infelizmente, nessa configuração, não podemos obter o gradiente da função que tentamos otimizar (que é o que geralmente queremos fazer, realizar a descida do gradiente ou alguns métodos mais avançados). Os processos gaussianos podem ser usados ​​nesse cenário, para encontrar conjuntos de hiperparâmetros, com grandes chances, de apresentar um desempenho melhor do que os melhores que encontramos até o momento. Portanto, você pode executar iterativamente o algoritmo com algum conjunto de hiperparâmetros e depois perguntar ao processo gaussiano quais seriam os melhores para tentar a seguir, tentar esses e assim por diante.

Para obter detalhes, procure o artigo "Otimização bayesiana prática de algoritmos de aprendizado de máquina", de Jasper Snoek, Hugo Larochelle e Ryan P Adams (também encontrado em seus sites ou no Google).

Sobre essa parte do empate, a melhor ideia de linha de base para empates é geralmente a quebra aleatória, portanto, a seleção da classe aleatória de todos os que venceram a votação e a seleção aleatória de um subconjunto de objetos vinculados grandes o suficiente para preencher k.

Essa solução enfatiza o fato de que são casos patológicos que simplesmente não fornecem informações suficientes para tomar uma decisão no regime kNN. BTW, se eles são comuns aos seus dados, talvez você deva tentar uma distância mais diferenciadora?

Uma maneira possível é fazer com que o algoritmo aumente ou diminua k automaticamente até obter um vencedor claro.