K-significa rápido como algoritmo para 10 ^ 10 pontos?

14

Eu estou olhando para fazer k-significa agrupar em um conjunto de 10 pontos dimensionais. O problema: há 10 ^ 10 pontos .

Estou procurando apenas o centro e o tamanho dos maiores aglomerados (digamos 10 a 100); Não me importo com o cluster em que cada ponto termina. Usar k-means especificamente não é importante; Estou apenas procurando um efeito semelhante, qualquer k-mean aproximado ou algoritmo relacionado seria ótimo (minibatch-SGD significa, ...). Como o GMM é, de certo modo, o mesmo problema que o k-means, fazer GMM com os mesmos dados de tamanho também é interessante.

Nesta escala, a subamostragem dos dados provavelmente não altera o resultado significativamente: as chances de encontrar os mesmos 10 principais clusters usando uma amostra de 1/10000 dos dados são muito boas. Mas, mesmo assim, esse é um problema de 10 ^ 6 pontos que está na / além da borda do tratável.

Alex I
fonte
1
Vários algoritmos são descritos no livro "Mineração de conjuntos de dados maciços", que você pode baixar gratuitamente aqui . Leia o capítulo 7 "Agrupamento".
lanenok

Respostas:

12

k-médias é baseada em médias .

Ele modela clusters usando meios e, portanto, a melhoria adicionando mais dados é marginal. O erro da estimativa média diminui com 1 / sqrt (n); adicionar mais dados compensa cada vez menos ...

As estratégias para dados tão grandes sempre giram em torno da amostragem:

Se você deseja tempo de execução sublinear, é necessário fazer amostragem!

De fato, os Mini-Lotes-Kmeans, etc., fazem exatamente isso: amostras repetidas do conjunto de dados.

No entanto, a amostragem (em particular a amostragem imparcial) também não é exatamente gratuita ... geralmente, você terá que ler seus dados linearmente para amostrar, porque não obtém acesso aleatório a registros individuais.

Eu iria com o algoritmo de MacQueen. Está online; por padrão, ele faz uma única passagem sobre seus dados (embora seja popular para iterar isso). Não é fácil distribuir, mas acho que você pode ler seus dados linearmente, digamos, 10 vezes a partir de um SSD?

Tem QUIT - Anony-Mousse
fonte
Eu não sabia sobre o algoritmo online de MacQueen! Geralmente, obtém os mesmos resultados que os meios K "clássicos"? Que tal usar a amostragem de reservatório? Dessa forma, o OP tem uma amostra para executar novamente o K-means, caso vários valores de K devam ser testados.
Victor Ma
6

Como comentário lateral, observe que o uso de meios K para dados 10D pode acabar em lugar algum, de acordo com a maldição da dimensionalidade. É claro que varia um pouco de acordo com a natureza dos dados, mas uma vez que tentei determinar o limite em que o K-Means começa a se comportar de maneira estranha em relação à dimensionalidade, obtive algo como 7D. Após 7 dimensões, ele começou a perder clusters corretos (meus dados foram gerados manualmente de acordo com 4 distribuições gaussianas bem separadas e usei a função kmeans do MATLAB para meu pequeno experimento).

Kasra Manshaei
fonte
Isso é possível e, é claro, sempre depende dos dados. No entanto, dado que o pôster possui 10 ^ 10 amostras (presumivelmente independentes), parece que 10 dimensões não seriam um problema muito grande aqui.
Ryan J. Smith
2
Obrigado pelo seu comentário @ RyanJ.Smith. seu comentário está exatamente na mesma direção que a minha. Eu simplesmente não vi nada sobre esse problema no post. E sobre o número de amostras; no entanto, ele tem muitos pontos de amostra e ainda pode ficar preso no problema da dimensionalidade. Eu acho que você está discutindo o lado oposto do problema de tamanho baixo da amostra, que eu acho que não é válido. Se ele tiver dados de alta dimensão, o tamanho reduzido da amostra será um problema, mas acho que uma grande quantidade de dados não significa necessariamente nada.
Kasra Manshaei
10 dimensões ainda não são muito.
Saiu - Anony-Mousse
1
Como você determina meu amigo? o que eu disse foi o resultado de um experimento desenvolvido para responder a essa pergunta, no entanto, NÃO PODE ser respondida em geral! O que é "muito" no seu comentário exatamente? depende de muitas circunstâncias, como mencionei na minha resposta. em algumas situações, 10D pode ser problemático.
Kasra Manshaei