Cluster de dados de alta dimensão

8

TL; DR: dado um grande conjunto de dados de imagem (cerca de 36 GiB de pixels brutos) de dados não rotulados, como posso agrupar as imagens (com base nos valores de pixel) sem saber o número de clusters Kpara começar?

Atualmente, estou trabalhando em um projeto de aprendizado não supervisionado para agrupar imagens; pense nisso como agrupar MNIST com valores de pixel RGB de 16x16x3, apenas que eu tenho cerca de 48 milhões de exemplos que preciso agrupar. Sem conhecer suas identidades, eu sei que algumas das imagens estão definitivamente relacionadas porque são da mesma fonte, mas - digamos - eu também não conheço um apropriado Kpara "apenas" executar o K-means no set ainda .

Eu estava pensando em fazer alguma incorporação 2D manual usando t-SNE e, em seguida, agrupar manualmente no espaço incorporado (uma tarefa mais simples do que fazê-lo manualmente em 16x16x3-d), mas todas as implementações em t-SNE que encontrei exigiam o carregamento dos dados na memória. Também pensei em executar o t-SNE pela primeira vez, depois o K-significa nos dados incorporados do t-SNE, mas se você observar os resultados do t-SNE do MNIST, é muito óbvio que esses clusters podem e provavelmente serão distorcidos e distorcidos de maneiras não lineares. Portanto, mesmo se eu soubesse a K, os grupos provavelmente seriam divididos. Usar distâncias de Mahalanobis para K-significa pode ser uma coisa interessante, mas desde que eu não conheço covariâncias, isso parece ser um beco sem saída também.

Atualmente estou tentando se posso executar a compactação PCA nos exemplos para, pelo menos, recuperar alguma memória do t-SNE, mas isso pode ou não funcionar ... não posso dizer por enquanto.

Alguém pode me dar um ponteiro na direção certa para fazer isso ( idealmente , mas definitivamente não é necessário em um contexto Python, TensorFlow ou Apache Beam / Dataflow)? Eu estava trabalhando na portabilidade de um Streaming / Ball K-meios há um tempo atrás, que tem a boa propriedade de criar novos clusters "sob demanda", mas antes de começar a implementá-lo novamente no Python / TensorFlow / Dataflow, eu esperava que alguém pudesse dê-me algumas idéias por onde começar ou o que evitar.

beira do sol
fonte
Você está definido em k-means? Se você não sabe quantos clusters deseja, por que não usar um método hierárquico?
MissMonicaE
11
@MissMonicaE Definitivamente não está definido para k-means, ele veio à minha mente primeiro. Você pode me dar um método hierárquico que faria sentido nesse contexto?
sunside
11
Infelizmente, os únicos algoritmos com os quais estou familiarizado são AGNES e DIANA, que usam matrizes diferentes (bem, o pacote R pega os dados brutos, mas não tenho certeza se as imagens funcionariam - eu só agrupei dados numéricos simples )
MissMonicaE
2
Tente métodos baseados em densidade; eles são menos heurísticos do que k-means. Eu só recorro ao k-means se for um problema de brinquedo e se os dados forem estritamente de uma distribuição normal. Consulte stats.stackexchange.com/questions/133656/…
Jon
11
Também vou encaminhá-lo para esta apresentação no DBSCAN youtube.com/watch?v=5cOhL4B5waU
Jon

Respostas:

11

Eu não acho que nenhuma das técnicas de agrupamento "apenas" funcione em tal escala. O mais escalonável é o k-means (apenas não use Spark / Mahout, eles são muito ruins) e o DBSCAN (existem algumas boas versões distribuídas disponíveis).

Mas você enfrentará muitos outros desafios além da escala, porque o agrupamento é difícil . Não é apenas o suficiente para executar o algoritmo e, em seguida, você tem clusters. O agrupamento é uma técnica exploratória. Não há cluster "correto". Mas, em vez disso, você precisará executar o clustering repetidamente e examinar cada cluster . Porque não haverá uma única configuração de parâmetro que faça tudo certo. Em vez disso, clusters diferentes podem aparecer apenas em parâmetros diferentes.

Mas o principal desafio no seu caso provavelmente será a função de distância. Exceto para configurações idealizadas como MNIST, a distância euclidiana não funcionará. Nem nada trabalhando nos pixels brutos. Então, primeiro você precisa fazer a extração de recursos e depois definir uma função de similaridade.

Quando se trata de cluster, trabalhe com uma amostra . Agrupe a amostra, identifique agrupamentos interessantes e, em seguida , pense em uma maneira de generalizar o rótulo para todo o conjunto de dados. Por exemplo, por classificação (os pontos de dados rotulados são o seu conjunto de treinamento, preveja os rótulos dos pontos não rotulados).

Possui QUIT - Anony-Mousse
fonte
0

Se você está tentando reduzir a dimensionalidade, deve usar o Mahout - é o melhor da classe e o único projeto de código aberto disponível para oferecer versões verdadeiramente distribuídas do PCA / SVD.

http://mahout.apache.org/docs/0.13.1-SNAPSHOT/algorithms/linear-algebra/d-spca.html

http://mahout.apache.org/docs/0.13.1-SNAPSHOT/algorithms/linear-algebra/d-ssvd.html

Mahout também possui a implementação do DBSCAN, o WIP, como parte de um projeto do Google Summer of Code, que vale a pena ficar de olho.

Suponho que a observação "Mahout is Bad" de Anony (eu concordo que o Spark é) é relevante para a versão obsoleta do Mahout do MapReduce (já que a nova versão ainda não implementou o K-Means imediatamente, embora haja uma discussão sobre lista de discussão sobre como fazer isso com bastante facilidade).

rawkintrevo
fonte