Maldição da dimensionalidade: classificador kNN

11

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 é .feD(f)=f1 1D

É 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ê.

user42140
fonte
6
Tente imaginar a situação em duas dimensões primeiro. Se eu tiver uma folha de papel de 1m * 1m e cortar um quadrado de 0,1m * 0,1m no canto inferior esquerdo, não removi um décimo do papel, mas apenas um centésimo .
David Zhang

Respostas:

13

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.

jpmuc
fonte
4

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

eD(f)=f1 1D

é 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:

insira a descrição da imagem aqui

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 1eD(f)

eD(f)=1 1Df1 1D-1 1=1 1Df1 1-DD

D>1 11 1-D<0 0

eD(f)=1 1D(f1 1-D)1 1D

fx-1 1=1 1xf<1 1kNDD

f1 1-D1 1D

Charlie Parker
fonte
2

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.

plumSemPy
fonte
0

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.

David Refaeli
fonte