Como sei que meu algoritmo de agrupamento k-means está sofrendo com a maldição da dimensionalidade?

12

Eu acredito que o título desta pergunta diz tudo.

mathieu
fonte
3
Acho que você terá que esclarecer para nós o que você quer dizer com sintoma.
Mdewey 30/08/16
Se "sintoma" for uma versão manual de "teste", talvez você possa coletar subamostras de seu conjunto de dados - talvez 66% do tamanho da amostra, realizar sua análise (kmeans, no seu caso) e ver como está nervoso. os resultados são. Por exemplo, você pode ver com que frequência determinadas observações são atribuídas ao mesmo cluster. Por outro lado, pode não valer a pena o esforço. Se você está preocupado com a possibilidade de um problema de dimensionalidade, é provável que tenha um. Você pode considerar outras abordagens de cluster que reduzem um pouco a dimensionalidade.
generic_user
@generic_user se que o comentário fosse uma resposta, eu contaria isso como uma resposta aceita :)
Mathieu
11
Esta questão é clara o suficiente para permanecer aberta, IMO.
gung - Restabelece Monica
11
Freqüentemente, você se depara com problemas muito mais graves de meios k antes da "maldição da dimensionalidade". O k-means pode funcionar com 128 dados dimensionais (por exemplo, vetores de cores SIFT) se os atributos forem de boa índole. Até certo ponto, pode até funcionar com dados de texto com 10000 dimensões. O modelo teórico da maldição nunca se aplica a dados reais. Os problemas maiores são recursos incomparáveis, esparsidade e incapacidade de visualizar e verificar o resultado.
Saiu - Anony-Mousse 31/08/16

Respostas:

18

Ajuda a pensar sobre o que é a maldição da dimensionalidade . Existem vários tópicos muito bons no CV que valem a pena ler. Aqui está um ponto de partida: Explique a “maldição da dimensionalidade” para uma criança .

Observo que você está interessado em como isso se aplica ao cluster mean. Vale a pena estar ciente de que -eans é uma estratégia de busca para minimizar (apenas) a distância euclidiana ao quadrado. À luz disso, vale a pena pensar em como a distância euclidiana se relaciona com a maldição da dimensionalidade (ver: Por que a distância euclidiana não é uma boa métrica em grandes dimensões? ). kkk

A resposta curta desses encadeamentos é que o volume (tamanho) do espaço aumenta a uma taxa incrível em relação ao número de dimensões. Até dimensões (o que não me parece muito "dimensional") podem trazer a maldição. Se seus dados foram distribuídos uniformemente por todo esse espaço, todos os objetos se tornam aproximadamente equidistantes um do outro. No entanto, como @ Anony-Mousse observa em sua resposta a essa pergunta, esse fenômeno depende de como os dados são organizados no espaço; se eles não são uniformes, você não necessariamente tem esse problema. Isso leva à questão de saber se os dados de alta dimensão uniformemente distribuídos são muito comuns (consulte: “A maldição da dimensionalidade” realmente existe em dados reais? ). 10

Eu argumentaria que o que importa não é necessariamente o número de variáveis ​​(a dimensionalidade literal de seus dados), mas a dimensionalidade efetiva de seus dados. Sob a suposição de que dimensões são 'muito altas' para médias, a estratégia mais simples seria contar o número de recursos que você possui. Mas se você quiser pensar em termos da dimensionalidade efetiva, poderá executar uma análise de componentes principais (PCA) e observar como os valores próprios diminuem. É bastante comum que a maior parte da variação exista em algumas dimensões (que geralmente abrangem as dimensões originais do seu conjunto de dados). Isso implicaria que é menos provável que você tenha um problema com significa no sentido de que sua dimensionalidade efetiva é realmente muito menor. k k10kk

Uma abordagem mais envolvida seria examinar a distribuição das distâncias aos pares em seu conjunto de dados, ao longo das linhas sugeridas por hxd1011 em sua resposta . Observar distribuições marginais simples dará a você uma dica da possível uniformidade. Se você normalizar todas as variáveis ​​para ficarem dentro do intervalo , as distâncias em pares devem estar dentro do intervalo . Distâncias altamente concentradas causarão problemas; por outro lado, uma distribuição multimodal pode ser esperançosa (você pode ver um exemplo na minha resposta aqui: Como usar variáveis ​​binárias e contínuas juntas no clustering? ).[ 0 , [0, 1][0, D]

No entanto, se significa 'funcionará' ainda é uma questão complicada. Sob a suposição de que existem agrupamentos latentes significativos em seus dados, eles não existem necessariamente em todas as suas dimensões ou em dimensões construídas que maximizam a variação (isto é, os principais componentes). Os clusters podem estar nas dimensões de menor variação (consulte: Exemplos de PCA em que PCs com baixa variação são “úteis” ). Ou seja, você pode ter clusters com pontos próximos e bem separados entre apenas algumas de suas dimensões ou em PCs de menor variação, mas não são remotamente semelhantes em PCs de alta variação, o que causaria médias para ignorar os clusters que você procura e escolher clusters falsos (alguns exemplos podem ser vistos aqui:kkkComo entender as desvantagens do K-means ).

- Reinstate Monica
fonte
Acontece que já existe uma etiqueta para o aprendizado múltiplo (deveria ter olhado primeiro!). Para resumir para aqueles que talvez não saibam, a idéia é que, embora os dados de alta dimensão tendam a ser escassos em termos de todo o espaço, eles podem ser densos em alguma hiper-superfície dentro desse espaço.
GeoMatt22
+1 para a excelente resposta. Você poderia elaborar um pouco mais sobre a parte dos autovalores? Se a dimensionalidade efetiva for pequena, você recomenda fazer PCA e reter apenas as primeiras pontuações com altos valores próprios?
DataD'oh
@ DataD'oh, essa é certamente uma possibilidade, mas o que estou dizendo é que você não precisa fazer isso. Na verdade, os dados não são de alta dimensão (quando apenas os primeiros vetores próprios têm altos valores próprios), portanto você não precisa necessariamente fazer nada - a maldição da dimensionalidade simplesmente não se aplica.
gung - Restabelece Monica
@ postou uma nova pergunta . Espero que não seja muito trivial.
precisa saber é o seguinte
7

Minha resposta não se limita a K significa, mas verifique se há maldição de dimensionalidade para métodos baseados em distância. O K-significa é baseado em uma medida de distância (por exemplo, distância euclidiana)

Antes de executar o algoritmo, podemos verificar a distribuição da métrica de distância, ou seja, todas as métricas de distância para todos os pares de dados. Se você tiver pontos de dados, deverá ter métricas de distância de . Se os dados forem muito grandes, podemos verificar uma amostra disso.0,5 N ( N - 1 )N0.5N(N1)

Se temos o problema da maldição da dimensionalidade, o que você verá é que esses valores estão muito próximos um do outro. Isso parece muito contra-intuitivo, porque significa que todos estão próximos ou distantes de cada um e a distância é basicamente inútil.


Aqui está uma simulação para mostrar esses resultados contra-intuitivos. Se todos os recursos forem distribuídos uniformemente e se houver muitas dimensões, todas as métricas de distância deverão estar próximas a , que vem de . Sinta-se livre para alterar a distribuição uniforme para outras distribuições. Por exemplo, se mudarmos para a distribuição normal (mudar para ), ela convergirá para outro número com grandes dimensões numéricas. 1 x i = 0 1 x j = 0 (xi-xj)2dxidxj16xi=01xj=01(xixj)2dxidxjrunifrnorm

Aqui está a simulação para a dimensão de 1 a 500, os recursos são de distribuição uniforme de 0 a 1.

plot(0, type="n",xlim=c(0,0.5),ylim=c(0,50))
abline(v=1/6,lty=2,col=2)
grid()

n_data=1e3
for (p in c(1:5,10,15,20,25,50,100,250,500)){
    x=matrix(runif(n_data*p),ncol=p)
    all_dist=as.vector(dist(x))^2/p
    lines(density(all_dist))
}

insira a descrição da imagem aqui

Haitao Du
fonte
11
O que é ? P
ameba
11
Eu havia votado por causa de uma demonstração do fenômeno do encolhimento euclidiano sob altas dimensões. Mas a resposta não demonstra um sofrimento de k-means agrupados da maldição. O sofrimento implicaria que, em grandes dimensões, agrupamentos razoavelmente bem separados (e não dados aleatórios uniformes como o seu) podem não ser descobertos com tanto sucesso quanto em dimensões baixas. Você não tocou neste tópico.
ttnphns
@amoeba é o número de dimensões. Vou revisar o enredo e adicionar o código. Obrigado. P
Haitao Du
@ttnphns obrigado pelo seu comentário e voto positivo. Vou ver Se posso adicionar um parágrafo para discutir o impacto em k significa.
Haitao Du