Maldição da dimensionalidade: classificador kNN

Estou lendo o livro de Kevin Murphy: Machine Learning - uma perspectiva probabilística. No primeiro capítulo, o autor está explicando a maldição da dimensionalidade e há uma parte que eu não entendo. Como exemplo, o autor declara:

Considere que as entradas são distribuídas uniformemente ao longo de um cubo de unidade D-dimensional. Suponha que estimamos a densidade dos rótulos de classe aumentando um hipercubo em torno de x até que ele contenha a fração desejada dos pontos de dados. O comprimento esperado da aresta deste cubo é .$f$$e_D(f) = f^{\frac{1}{D}}$

É a última fórmula que eu não consigo entender. parece que, se você deseja cobrir, digamos 10% dos pontos, o comprimento da borda deve ser 0,1 ao longo de cada dimensão? Sei que meu raciocínio está errado, mas não consigo entender o porquê.

Esse é precisamente o comportamento inesperado das distâncias em grandes dimensões. Para 1 dimensão, você tem o intervalo [0, 1]. 10% dos pontos estão em um segmento de comprimento 0.1. Mas o que acontece quando a dimensionalidade do espaço de recurso aumenta?

Essa expressão está lhe dizendo que, se você quiser ter 10% dos pontos para 5 dimensões, precisará ter um comprimento para o cubo de 0,63, em 10 dimensões de 0,79 e 0,98 para 100 dimensões.

Como você vê, para aumentar as dimensões, você precisa olhar mais longe para obter a mesma quantidade de pontos. Ainda mais, está lhe dizendo que a maioria dos pontos está no limite do cubo à medida que o número de dimensões aumenta. O que é inesperado.

Eu acho que o principal a notar é que a expressão

é realmente muito íngreme no começo. Isso significa que o tamanho da borda que você precisará abranger uma certa fração do volume aumentará drasticamente, especialmente no início. ou seja, a borda que você precisa se tornará ridiculamente grande à medida que aumentar.$D$

Para tornar isso ainda mais claro, lembre-se da trama que Murphy mostra:

se você observar, para valores de , a inclinação é realmente grande e, portanto, a função cresce muito acentuadamente no início. Isso pode ser melhor apreciado se você usar a derivada de e D ( f ) :$D > 1$$e_D(f)$

$D > 1$$1-D < 0$

$f$$x^{-1} = \frac{1}{x}$$f < 1$$k$$N$$D$$D$

$f^{1 - D}$$\frac{1}{D}$

Sim, portanto, se você tem um cubo de unidade ou, no seu caso, uma linha de unidade, e os dados são distribuídos uniformemente, é necessário um comprimento de 0,1 para capturar 10% dos dados. Agora, à medida que você aumenta as dimensões, D aumenta, que diminui a potência ef menor que 1, aumentará, de modo que se D for ao infinito, você precisará capturar todo o cubo, e = 1.

Eu acho que a distância kNN tem um papel maior. O que acontece com um (hiper) cubo é análogo ao que acontece com a distância entre pontos. À medida que você aumenta o número de dimensões, a proporção entre a distância mais próxima e a distância média aumenta - isso significa que o ponto mais próximo fica quase tão longe quanto o ponto médio e, portanto, possui apenas um poder preditivo um pouco mais do que o ponto médio. Este artigo explica bem

Joel Grus faz um bom trabalho ao descrever esse problema na Data Science from Scratch. Nesse livro, ele calcula as distâncias média e mínima entre dois pontos em um espaço de dimensão à medida que o número de dimensões aumenta. Ele calculou 10.000 distâncias entre pontos, com o número de dimensões variando de 0 a 100. Em seguida, ele passou a plotar a distância média e mínima entre dois pontos, bem como a razão da distância mais próxima da distância média (Distance_Closest / Distance_Average) .

Nessas parcelas, Joel mostrou que a razão da distância mais próxima da distância média aumentou de 0 em 0 dimensões, até ~ 0,8 em 100 dimensões. E isso mostra o desafio fundamental da dimensionalidade ao usar o algoritmo k-vizinhos mais próximos; À medida que o número de dimensões aumenta e a proporção da distância mais próxima da distância média se aproxima de 1, o poder preditivo do algoritmo diminui. Se o ponto mais próximo estiver quase tão longe quanto o ponto médio, ele terá apenas um poder preditivo um pouco mais do que o ponto médio.