Agrupamento na saída do t-SNE

78

Eu tenho um aplicativo em que seria útil agrupar um conjunto de dados barulhento antes de procurar efeitos de subgrupos nos clusters. Olhei pela primeira vez para o PCA, mas são necessários ~ 30 componentes para atingir 90% da variabilidade; portanto, agrupar apenas alguns PCs descartará muita informação.

Eu tentei o t-SNE (pela primeira vez), o que me dá uma forma estranha em duas dimensões que é muito passível de agrupamento via k-means. Além disso, a execução de uma floresta aleatória nos dados com a atribuição de cluster como resultado mostra que os clusters têm uma interpretação bastante sensata, dado o contexto do problema, em termos das variáveis ​​que compõem os dados brutos.

Mas se eu vou relatar sobre esses clusters, como os descrevo? Clusters de médias K em componentes principais revelam indivíduos que estão próximos um do outro em termos das variáveis ​​derivadas que compreendem X% da variação no conjunto de dados. Que afirmação equivalente pode ser feita sobre os clusters de t-SNE?

Talvez algo com o efeito de:

O t-SNE revela contiguidade aproximada em um coletor de alta dimensão subjacente; portanto, agrupamentos na representação em baixa dimensão do espaço de alta dimensão maximizam a "probabilidade" de que indivíduos contíguos não estejam no mesmo cluster

Alguém pode propor uma sinopse melhor do que isso?

generic_user
fonte
1
Eu pensaria que o truque é descrever os clusters com base nas variáveis ​​originais, e não nas variáveis ​​no espaço reduzido.
Tim
1
Certo, mas sem uma descrição concisa e intuitiva de qual objetivo o algoritmo de atribuição de cluster minimiza, posso estar aberto a acusações de escolher um algoritmo de clustering que facilite a obtenção dos resultados desejados.
generic_user
1
Para algumas ressalvas e visuals agradável no t-SNE também ter um olhar para distill.pub/2016/misread-tsne
Tom Wenseleers

Respostas:

96

O problema com o t-SNE é que ele não preserva distâncias nem densidade. Até certo ponto, preserva os vizinhos mais próximos. A diferença é sutil, mas afeta qualquer algoritmo baseado em densidade ou distância.

Para ver esse efeito, basta gerar uma distribuição gaussiana multivariada. Se você visualizar isso, terá uma bola densa e muito menos densa para o exterior, com alguns outliers que podem estar muito distantes.

Agora, execute o t-SNE nesses dados. Você normalmente obterá um círculo de densidade bastante uniforme. Se você usa uma baixa perplexidade, pode até ter alguns padrões estranhos lá. Mas você não pode mais distinguir os valores discrepantes.

Agora vamos tornar as coisas mais complicadas. Vamos usar 250 pontos em uma distribuição normal em (-2,0) e 750 pontos em uma distribuição normal em (+2,0).

Dados de entrada

Supõe-se que seja um conjunto de dados fácil, por exemplo com o EM:

Cluster EM

Se executarmos t-SNE com perplexidade padrão de 40, obteremos um padrão de formato estranho:

t-PND p = 40

Não é ruim, mas também não é tão fácil de agrupar, não é? Você terá dificuldade em encontrar um algoritmo de agrupamento que funcione aqui exatamente como desejado. E mesmo se você pedir aos seres humanos para agrupar esses dados, provavelmente eles encontrarão muito mais do que 2 grupos aqui.

Se executarmos o t-SNE com uma perplexidade muito pequena, como 20, obteremos mais desses padrões que não existem:

t-PND p = 20

Isso irá agrupar, por exemplo, o DBSCAN, mas produzirá quatro agrupamentos. Portanto, cuidado, o t-SNE pode produzir padrões "falsos"!

A perplexidade ideal parece estar em torno de 80 para este conjunto de dados; mas não acho que esse parâmetro funcione para todos os outros conjuntos de dados.

t-PND p = 80

Agora, isso é visualmente agradável, mas não é melhor para análise . Um anotador humano provavelmente poderia selecionar um corte e obter um resultado decente; O k-means, no entanto, falhará mesmo neste cenário muito muito fácil ! Você já pode ver que as informações de densidade são perdidas , todos os dados parecem viver em uma área quase da mesma densidade. Se, em vez disso, aumentarmos ainda mais a perplexidade, a uniformidade aumentará e a separação diminuirá novamente.

Em conclusão, use t-SNE para visualização (e tente parâmetros diferentes para obter algo visualmente agradável!), Mas não execute agrupamentos posteriormente , em particular não use algoritmos baseados em distância ou densidade, pois essas informações foram intencionalmente (!) perdido. As abordagens baseadas em gráficos de vizinhança podem ser boas, mas você não precisa primeiro executar o t-SNE antes, basta usar os vizinhos imediatamente (porque o t-SNE tenta manter esse nn-gráfico em grande parte intacto).

Mais exemplos

Esses exemplos foram preparados para a apresentação do trabalho (mas ainda não podem ser encontrados no trabalho, como fiz mais tarde)

Erich Schubert e Michael Gertz.
Incorporação intrínseca do vizinho t-estocástico para visualização e detecção externa - um remédio contra a maldição da dimensionalidade?
In: Anais da 10ª Conferência Internacional sobre Pesquisa e Aplicações de Similaridade (SISAP), Munique, Alemanha. 2017

Primeiro, temos esses dados de entrada:

Peixe

Como você pode imaginar, isso é derivado de uma imagem "color me" para crianças.

Se executarmos isso através do SNE ( NÃO o t-SNE , mas o predecessor):

Peixe SNE

Uau, nosso peixe se tornou um monstro marinho! Como o tamanho do kernel é escolhido localmente, perdemos grande parte das informações de densidade.

Mas você ficará realmente surpreso com a saída do t-SNE:

peixe t-PND

Na verdade, tentei duas implementações (as implementações ELKI e sklearn) e ambas produziram esse resultado. Alguns fragmentos desconectados, mas cada um parece um pouco consistente com os dados originais.

Dois pontos importantes para explicar isso:

  1. O SGD depende de um procedimento de refinamento iterativo e pode ficar preso nos ótimos locais. Em particular, isso torna difícil para o algoritmo "inverter" uma parte dos dados que ele espelhou, pois isso exigiria pontos móveis através de outros que deveriam estar separados. Portanto, se algumas partes do peixe são espelhadas e outras não, pode ser que não seja possível corrigir isso.

  2. O t-SNE usa a distribuição t no espaço projetado. Em contraste com a distribuição gaussiana usada pelo PND regular, isso significa que a maioria dos pontos se repele , porque eles têm 0 afinidade no domínio de entrada (o gaussiano fica zero rapidamente), mas> 0 no domínio de saída. Às vezes (como no MNIST), isso facilita a visualização. Em particular, pode ajudar a "dividir" um conjunto de dados um pouco mais do que no domínio de entrada. Essa repulsão adicional geralmente também faz com que os pontos usem a área de maneira mais uniforme, o que também pode ser desejável. Mas aqui neste exemplo, os efeitos repelentes realmente fazem com que fragmentos de peixe se separem.

Podemos ajudar (neste conjunto de dados de brinquedos ) a primeira questão usando as coordenadas originais como posicionamento inicial, em vez de coordenadas aleatórias (como geralmente usadas com o t-SNE). Desta vez, a imagem é sklearn em vez de ELKI, porque a versão sklearn já tinha um parâmetro para passar as coordenadas iniciais:

Peixe, t-SNE, com coordenadas originais como inicialização

Como você pode ver, mesmo com um posicionamento inicial "perfeito", o t-SNE "quebrará" o peixe em vários locais que foram originalmente conectados porque a repulsão de Student-t no domínio de saída é mais forte que a afinidade gaussiana na entrada espaço.

Como você pode ver, t-SNE (e SNE também!) São técnicas interessantes de visualização , mas precisam ser manuseadas com cuidado. Prefiro não aplicar k-means no resultado! porque o resultado será muito distorcido e nem as distâncias nem a densidade serão preservadas. Em vez disso, use-o para visualização.

Erich Schubert
fonte
1
Obrigado pela resposta. Posso imaginar métodos de cluster adaptativo baseados em vizinhança, mas existem métodos específicos bem desenvolvidos que você poderia recomendar?
generic_user 01/03
1
CHAMAELEON é provavelmente o mais citado, mas parece que há apenas um binário disponível para a etapa principal. A ideia parece boa, mas você experimentará rapidamente os mesmos efeitos que o t-SNE torna visível. Tal como a tendência para "rebanho" como pode ser visto com p = 20, problemas com cubos e anti-cubos, etc.
Erich Schubert
2
@AlexR: A perplexidade é usada para calcular as semelhanças no espaço de alta dimensão que t-sne está tentando combinar em 2D. Mudar a perplexidade significa mudar as semelhanças, por isso não vejo como comparar as divergências resultantes de KL pode ser significativo.
Ameba diz Reinstate Monica
1
@AlexR. "Somente a probabilidade condicional do espaço dimensional inferior depende da perplexidade" - esta afirmação está errada. A perplexidade é usada para escolher sigmas necessários para a eq (1), de modo que influencia cond. probs. em todo o espaço.
Ameba diz Reinstate Monica
1
Para algumas ressalvas e visuals agradável no t-SNE também ter um olhar para distill.pub/2016/misread-tsne
Tom Wenseleers
34

Gostaria de fornecer uma opinião um tanto divergente à resposta bem argumentada (+1) e altamente votada por @ErichSchubert. Erich não recomenda o agrupamento na saída t-SNE e mostra alguns exemplos de brinquedos em que isso pode ser enganoso. Sua sugestão é aplicar o agrupamento aos dados originais.

use t-SNE para visualização (e tente parâmetros diferentes para obter algo visualmente agradável!), mas não execute o clustering posteriormente; em particular, não use algoritmos baseados em distância ou densidade, pois essas informações foram intencionalmente perdidas (!).

Estou ciente das maneiras pelas quais a saída t-SNE pode ser enganosa (consulte https://distill.pub/2016/misread-tsne/ ) e concordo que ela pode produzir resultados estranhos em algumas situações.

Mas vamos considerar alguns dados reais de alta dimensão.

Obtenha dados MNIST : 70000 imagens de um dígito. Sabemos que existem 10 classes nos dados. Essas classes parecem bem separadas para um observador humano. No entanto, o agrupamento de dados MNIST em 10 clusters é um problema muito difícil. Não conheço nenhum algoritmo de cluster que agrupe corretamente os dados em 10 clusters; mais importante, não conheço nenhuma heurística de cluster que indique que há 10 (não mais e nem menos) clusters nos dados. Estou certo de que as abordagens mais comuns não seriam capazes de indicar isso.

Mas vamos fazer o t-SNE. (Pode-se encontrar muitos números de t-SNE aplicados ao MNIST on-line, mas geralmente são abaixo do ideal. Na minha experiência, é necessário executar exageros precoces por algum tempo para obter bons resultados. Abaixo, estou usando perplexity=50, max_iter=2000, early_exag_coeff=12, stop_lying_iter=1000). Aqui está o que eu recebo, à esquerda sem rótulo, e à direita colorido de acordo com a verdade básica:

MNIST t-SNE

Eu argumentaria que a representação t-SNE não marcada sugere 10 grupos. A aplicação de um bom algoritmo de cluster baseado em densidade, como o HDBSCAN, com parâmetros cuidadosamente selecionados permitirá agrupar esses dados 2D em 10 clusters.

Caso alguém duvide que o gráfico esquerdo acima realmente sugere 10 clusters, eis o que recebo com o truque de "exagero tardio", no qual também executo max_iter=200iterações exaggeration=4(esse truque é sugerido neste ótimo artigo: https://arxiv.org /abs/1712.09005 ):

MNIST t-SNE com exagero tardio

Agora deve ser muito óbvio que existem 10 clusters.

Encorajo todo mundo que pensa que agrupar após t-SNE é uma má idéia para mostrar um algoritmo de agrupamento que alcançaria resultados comparativamente bons.

E agora ainda mais dados reais.

No caso MNIST, conhecemos a verdade básica. Considere agora alguns dados com base desconhecida. O agrupamento e o t-SNE são rotineiramente usados ​​para descrever a variabilidade celular em dados de RNA-seq de célula única. Por exemplo, Shekhar et al. 2016 tentou identificar aglomerados entre 27.000 células da retina (existem cerca de 20k genes no genoma do mouse, portanto a dimensionalidade dos dados é, em princípio, de cerca de 20k; no entanto, geralmente se começa com a redução da dimensionalidade com o PCA para 50 ou mais). Eles fazem t-SNE e fazem cluster separadamente (um pipeline de cluster complicado seguido por algumas mesclagens de cluster etc.). O resultado final parece agradável:

insira a descrição da imagem aqui

A razão pela qual parece tão agradável é que o t-SNE produz clusters claramente distintos e o algoritmo de cluster produz exatamente os mesmos clusters. Agradável.

No entanto, se você olhar nos suplementares, verá que os autores tentaram muitas abordagens diferentes de agrupamento. Muitos deles parecem horríveis no gráfico t-SNE porque, por exemplo, o grande cluster central é dividido em muitos subclusters:

insira a descrição da imagem aqui

Então, em que você acredita: a saída do seu algoritmo de clustering favorito, juntamente com sua heurística favorita para identificar o número de clusters, ou o que você vê no gráfico t-SNE? Para ser sincero, apesar de todas as deficiências do t-SNE, tenho a tendência de acreditar mais no t-SNE. Ou, de qualquer forma, não vejo por que devo acreditar menos .

ameba diz Restabelecer Monica
fonte
2
E, para o último exemplo, não é essencialmente o que o @ErichSchubert observou acima: você pode obter resultados visualmente "agradáveis" - que estão obviamente errados? Tal como acontece com a perplexidade 20? Que o tSNE gosta de separar partes (como no peixe) que não foram separadas? Então, você sabe que os grupos que você vê são realmente grupos separados? Eu não gosto dessa "caixa preta" lá dentro. Sim, tendemos a acreditar mais nessas tramas, mas e se estiverem erradas?
Anony-Mousse
1
Bem, o tSNE é baseado em NN. É esperado um acordo com isso. TSNE é uma boa opção para visualizar NN. Porém, ela não preserva bem as semelhanças, portanto deve ser interpretada com cuidado, pelo que entendi. Uma lacuna no tSNE não implica uma grande distância.
Anony-Mousse
1
+1 Curioso sobre o desempenho do UMAP em comparação com o t-SNE.
Paul
1
@Paul: o autor reivindica a superioridade do UMAP, em termos de tempo de computação, é. No conjunto de dados MNIST, acho que o UMAP gera melhor incorporação do que o t-SNE, mas não tenho certeza de outros conjuntos de dados. Tanto quanto sei, há recentemente uma versão CUDA do t-SNE, que é muito mais rápida que o t-SNE mais rápido anterior, mas não consegui instalar e testar.
SiXUlm 03/04
1
O @SiXUlm github.com/KlugerLab/FIt-SNE funciona muito mais rápido que o Barnes-Hut t-SNE e geralmente é mais rápido que o UMAP. Além disso, em muitos casos, é possível obter incorporação muito semelhante ao t-SNE usando alguns ajustes adicionais, por exemplo, no MNIST, o t-SNE com pequeno exagero produz quase a mesma coisa que UMAP, veja o exemplo de caderno Python no repositório FIt-SNE.
amoeba diz Restabelecer Monica em
6

Eu acho que com grande perplexidade, o t-SNE pode reconstruir a topologia global, conforme indicado em https://distill.pub/2016/misread-tsne/ .

A partir da imagem do peixe, coletei 4000 pontos para o t-SNE. Com uma grande perplexidade (2000), a imagem do peixe foi praticamente reconstruída.

Aqui está a imagem original. Imagem original

Aqui está a imagem reconstruída por t-SNE com perplexidade = 2000. Imagem reconstruída t-SNE (perplexidade = 2000)

renxwise
fonte
8
Se você escolher essas perplexidades tão altas, não será mais tSNE. Cada ponto é vizinho aproximadamente todos os dias. Não é mais local. Sim, uma imagem 2D pode então ser reconstruída aproximadamente, porque é 2D. Mas não fazer a coisa toda é mais fácil.
Anony-Mousse
1
Minha opinião é que o SNSE com grande perplexidade pode reconstruir a topologia global. A 2d imagem é um exemplo porque sua dimensionalidade intrínseca é 2. A aplicação real do tSNE deve selecionar a perplexidade adequada de acordo com o objetivo de capturar as características locais ou globais.
Renxwise
1
Perplexidades tão altas significam que você usa um "kernel" muito grande e efetivamente usa distâncias. Provavelmente degenera para um MDS aproximado e muito caro. Basta usar o MDS então. O SNE / tSNE realmente deve ser usado com pequenas perplexidades e bairros locais.
Erich Schubert
3
Exatamente. Quando a perplexidade é grande o suficiente, o tSNE é realmente aproximado do MDS, o que ilustra que o tSNE também pode capturar a estrutura global. Portanto, declarações de que o tSNE pode capturar apenas estruturas locais não estão corretas. Diferente do MDS, o tSNE pode se equilibrar entre estruturas locais e globais através da seleção de perplexidade. Obviamente, a seleção de perplexidade depende do conjunto de dados.
Renxwise
Existe alguma regra prática para escolher perplexidade plausível?
Catbuilts
5

Com base nas evidências matemáticas que temos, esse método pode tecnicamente preservar distâncias! Por que todos vocês ignoram esse recurso! O t- SNE está convertendo as distâncias euclidianas de alta dimensão entre amostras em probabilidades condicionais que representam similaridades. Eu tentei o t- SNE com mais de 11.000 amostras (no contexto genômico) em paralelo com diferentes algoritmos de agrupamento por consenso, incluindo agrupamento espectral, afinidade e, principalmente, com agrupamento GMM (que é um algoritmo de agrupamento baseado em densidade!). Como resultado, achei um resultado concordante muito bom entre duas abordagens ( tAlgoritmos de agrupamento PND vs. consenso). Acredito que a integração do t-SNE com algoritmos de agrupamento de consenso poderia fornecer a melhor evidência das estruturas locais e globais existentes de dados.

Reza Rafiee
fonte
Existem parâmetros que influenciarão a probabilidade de o t-SNE preservar distâncias?
Keith Hughitt 19/01
Esses não são algoritmos de agrupamento de consenso. O clustering de consenso é um tipo de aprendizado de conjunto que agrega os resultados da repetição do algoritmo de clustering com alguma variação nos parâmetros ou nos dados de entrada, para obter um resultado final do clustering. Você pode usar abordagens de agrupamento por consenso com agrupamento espectral ou GMM ou mesmo qualquer algoritmo de agrupamento, mas meu argumento em sua terminologia é um pouco complicado, só isso :)
Christopher John
1

Você pode tentar o algoritmo de cluster DBSCAN. Além disso, a perplexidade de tsne deve ser aproximadamente do mesmo tamanho que o menor cluster esperado.

James LI
fonte
0

Pessoalmente, já experimentei isso uma vez, mas não com t-SNE ou PCA. Meus dados originais estão no espaço 15-dimensional. Usando o UMAP para reduzi-lo a incorporações 2D e 3D, obtive dois clusters perfeitamente e visualmente separados em gráficos 2D e 3D. Muito bom para ser verdade. Mas quando "examinei" os dados originais do diagrama de persistência, percebi que havia muito mais clusters "significativos", não apenas 2.

O agrupamento na saída da técnica de redução de dimensão deve ser feito com muita cautela; caso contrário, qualquer interpretação pode ser muito enganadora ou errada, pois a redução da dimensão certamente resultará em perda de recurso (talvez barulhentos ou verdadeiros, mas, a priori, não sabemos " não sei qual). Na minha opinião, você pode confiar / interpretar os clusters, se:

  • Os clusters nos dados projetados correspondem / confirmam a alguma classificação definida a priori (pense no conjunto de dados MNIST, onde os clusters de dados projetados correspondem muito bem à classificação dos dígitos) e / ou

  • Você pode confirmar a presença desses clusters nos dados originais usando outros métodos, como diagramas de persistência. Contar apenas o número de componentes conectados pode ser feito em um período bastante razoável.

SiXUlm
fonte
Por que você confiou mais no "diagrama de persistência" do que no UMAP? Eu não acho que olhar para o diagrama de persistência possa ser descrito como "olhar para os dados originais" ...
ameba diz Reinstate Monica
Você está certo. O diagrama de persistência mostra apenas algumas características dos dados originais, na maioria das vezes, componentes conectados, orifícios unidimensionais e muito mais raros, orifícios 2 ou mais dimensionais devido ao cálculo caro. Então, eu deveria ter dito que só posso "olhar" parcialmente para os dados originais observando o diagrama de persistência correspondente. Mas posso confiar no que observo neste diagrama de persistência porque ele é construído diretamente a partir dos dados originais.
SiXUlm 03/04
Por outro lado, usando o UMAP ou qualquer outra técnica de redução de dimensão, trabalhamos apenas com uma versão projetada / modificada dos dados originais. Como apontou a resposta mais votada, o agrupamento pode ser diferente para as diferentes opções de parâmetros.
SiXUlm 03/04