Como saber se os dados estão “agrupados” o suficiente para que os algoritmos de agrupamento produzam resultados significativos?

78

Como você saberia se seus dados (de alta dimensão) exibem agrupamentos suficientes para que os resultados de kmeans ou outro algoritmo de agrupamento sejam realmente significativos?

Para o algoritmo k-means, em particular, quanto de redução na variação dentro do cluster deve haver para que os resultados reais do cluster sejam significativos (e não espúrios)?

O agrupamento deve ser aparente quando uma forma de dados reduzida dimensionalmente é plotada e os resultados de kmeans (ou outros métodos) não fazem sentido se o agrupamento não puder ser visualizado?

xuexue
fonte
1
Dígitos manuscritos fazem um bom teste para agrupar: seria de esperar 10 grupos bem separados, mas isso não mostra joelho em k = 10, pelo menos na métrica euclidiana em 64d.
Denis
Veja também stackoverflow.com/q/15376075/134830
Richie Cotton
2
Esta questão está relacionada, até certo ponto, à questão de como verificar a validade dos resultados do cluster e como selecionar um método "melhor". Veja, por exemplo, stats.stackexchange.com/q/195456/3277 .
ttnphns

Respostas:

77

Sobre o k-means especificamente, você pode usar as estatísticas do Gap. Basicamente, a idéia é calcular uma boa medida de agrupamento com base na dispersão média em comparação com uma distribuição de referência para um número crescente de clusters. Mais informações podem ser encontradas no artigo original:

Tibshirani, R., Walther, G. e Hastie, T. (2001). Estimando o número de clusters em um conjunto de dados por meio da estatística de gap . JR Statist. Soc. B, 63 (2): 411-423.

A resposta que forneci a uma pergunta relacionada destaca outros índices gerais de validade que podem ser usados ​​para verificar se um determinado conjunto de dados exibe algum tipo de estrutura.

Quando você não tem idéia do que você esperaria encontrar se houvesse apenas ruído, uma boa abordagem é usar a reamostragem e estudar a estabilidade dos clusters. Em outras palavras, resample seus dados (via bootstrap ou adicionando pouco ruído) e calcule a "proximidade" das partições resultantes, conforme medido pelas semelhanças de Jaccard . Em resumo, permite estimar a frequência com que clusters semelhantes foram recuperados nos dados. Este método está prontamente disponível no pacote fpc R como clusterboot(). Ele assume como entrada dados brutos ou uma matriz de distância e permite aplicar uma ampla variedade de métodos de agrupamento (métodos hierárquicos, k-means, fuzzy). O método é discutido nas referências vinculadas:

Hennig, C. (2007) Avaliação em cluster da estabilidade de cluster . Estatística Computacional e Análise de Dados , 52, 258-271.

Hennig, C. (2008) Ponto de dissolução e robustez do isolamento: critérios de robustez para métodos gerais de análise de agrupamentos . Journal of Multivariate Analysis , 99, 1154-1176.

Abaixo está uma pequena demonstração com o algoritmo k-means.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

Os resultados são bastante positivos nesse conjunto de dados artificial (e bem estruturado), pois nenhum dos três clusters ( krange) foi dissolvido entre as amostras, e a similaridade média do Jaccard em cluster é> 0,95 para todos os clusters.

Abaixo estão os resultados nas 20 amostras de inicialização. Como pode ser visto, as unidades estatísticas tendem a ficar agrupadas no mesmo cluster, com poucas exceções para as observações intermediárias.

insira a descrição da imagem aqui

Você pode estender essa idéia a qualquer índice de validade, é claro: escolha uma nova série de observações por autoinicialização (com substituição), calcule sua estatística (por exemplo, largura da silhueta, correlação copenética, gama de Hubert, dentro da soma dos quadrados) para uma variedade de números de cluster (por exemplo, 2 a 10), repita 100 ou 500 vezes e observe o gráfico de caixa da sua estatística como uma função do número de cluster.

Aqui está o que eu recebo com o mesmo conjunto de dados simulado, mas usando o agrupamento hierárquico de Ward e considerando a correlação copenética (que avalia como a informação de distância é reproduzida nas partições resultantes) e a largura da silhueta (uma medida combinada que avalia a homogeneidade intra-cluster e inter- separação de cluster).

A correlação copenética varia de 0,6267 a 0,7511 com um valor mediano de 0,7031 (500 amostras de autoinicialização). A largura da silhueta parece ser máxima quando consideramos três grupos (mediana 0,8408, intervalo 0,7371-0,8769).

insira a descrição da imagem aqui

chl
fonte
Obrigado por esta resposta MUITO informativa! Parece que clusterboot é exatamente o que estou procurando. Obrigado também por incluir os links.
Xuexue
1
Alguns números mágicos para interpretar os valores da silhueta: stats.stackexchange.com/a/12923/12359
Franck Dernoncourt
1
Qual foi o comando que você usou para criar esses gráficos no gif?
Travis Heeter
2
@Travis As imagens foram salvas como arquivos PNG separados e depois convertidas em um arquivo GIF animado usando o ImageMagick . Veja também este post .
chl 28/11
10

Uma maneira de visualizar rapidamente se os dados de alta dimensão exibem cluster suficiente é usar a Incorporação estocástica de vizinhos distribuída por t ( SNE ). Ele projeta os dados em algum espaço de baixa dimensão (por exemplo, 2D, 3D) e faz um bom trabalho em manter a estrutura do cluster, se houver.

Por exemplo, conjunto de dados MNIST :

insira a descrição da imagem aqui

Olivetti enfrenta o conjunto de dados:

insira a descrição da imagem aqui

Franck Dernoncourt
fonte
1
Existe uma maneira de aplicar os rostos (ou quaisquer imagens) no R?
Travis Heeter
1
@TravisHeeter Eu não sei
Franck Dernoncourt
4
Não agrupe os dados projetados do tSNE. Veja, por exemplo, esta resposta: stats.stackexchange.com/a/264647/7828
Anony-Mousse 10/10
9

Certamente, a capacidade de discernir visualmente os clusters em um número plotável de dimensões é um critério duvidoso para a utilidade de um algoritmo de clustering, especialmente se essa redução de dimensão for feita independentemente do próprio clustering (ou seja: em uma tentativa vã de descobrir se cluster funcionará).

De fato, os métodos de agrupamento têm seu valor mais alto em encontrar os agrupamentos onde o olho / mente humanos é incapaz de vê-los.

A resposta simples é: faça cluster e descubra se funcionou (com qualquer um dos critérios de seu interesse, veja também a resposta de @ Jeff).

Nick Sabbe
fonte
1
Sim, e os clusters não são necessariamente bons grupos redondos de pontos, que é basicamente o que kmeans assume.
Wayne
@chl Você produziu esta imagem animada com R?
Stéphane Laurent
7

Quando os resultados são significativos, afinal? Em particular, resultados de médias médias?

O fato é que o k-means otimiza uma certa estatística matemática. Não há "significativo" associado a isso.

Em particular em dados de alta dimensão, a primeira pergunta deve ser: a distância euclidiana ainda é significativa ? Caso contrário, não use k-means. A distância euclidiana é significativa no mundo físico, mas rapidamente perde significado quando você tem outros dados. Em particular, quando você transforma dados artificialmente em um espaço vetorial, existe alguma razão para que sejam Euclidianos?

Se você pegar o conjunto de dados "velho fiel" clássico e executar o k-means nele sem normalização, mas com uma distância euclidiana pura, ele já não será mais significativo. O EM, que de fato usa alguma forma de distância "local do cluster" de Mahalanobis, funcionará muito melhor. Em particular, adapta-se aos eixos com escalas muito diferentes.

Aliás, um dos pontos fortes do k-means é que ele realmente sempre particiona os dados, não importa como eles sejam. Você pode usar o k-means para particionar ruído uniforme em k clusters . Pode-se afirmar que, obviamente, os grupos k-means não são significativos. Ou pode-se aceitar isso como: o usuário queria particionar os dados para minimizar as distâncias euclidianas quadradas, sem precisar que os clusters fossem "significativos".

Anony-Mousse
fonte
@ Anony-Mousse E caso de uso para 'particionar ruído uniforme em k clusters'?
CodeFarmer 29/01
Não há nenhum. O ponto é que o k-means não se importa, ele particionará dados uniformes em "clusters", ou seja, produz clusters sem sentido.
Anony-Mousse
6

Eu comecei a usar algoritmos de cluster recentemente, por isso espero que alguém com mais conhecimento possa fornecer uma resposta mais completa, mas aqui estão alguns pensamentos:

"Significativo", como tenho certeza de que você sabe, é muito subjetivo. Portanto, se o armazenamento em cluster é bom o suficiente depende completamente do motivo pelo qual você precisa fazer o cluster. Se você estiver tentando prever a participação em um grupo, é provável que qualquer cluster faça melhor que o acaso (e não seja pior), portanto os resultados devem ser significativos até certo ponto.

Se você quiser saber o quão confiável é esse cluster, precisará de alguma métrica para compará-lo. Se você tiver um conjunto de entidades com associações conhecidas, poderá usar a análise discriminante para ver se as previsões foram boas. Se você não possui um conjunto de entidades com associações conhecidas, precisará saber qual variação é típica dos clusters em seu campo. É provável que atributos físicos de entidades com categorias rígidas apresentem uma variação no grupo muito menor do que dados psicométricos em humanos, mas isso não necessariamente torna o aglomerado 'pior'.

Sua segunda pergunta faz alusão a 'Qual valor de k devo escolher?' Novamente, não há resposta difícil aqui. Na ausência de um conjunto de categorias a priori, você provavelmente deseja minimizar o número de clusters e também minimizar a variação média do cluster. Uma abordagem simples pode ser plotar 'número de clusters' vs 'variação média de cluster' e procurar o "cotovelo" - onde adicionar mais clusters não afeta significativamente a variação de cluster.

Eu não diria que os resultados do k-means não têm sentido se não puderem ser visualizados, mas certamente são atraentes quando os clusters são visualmente aparentes. Isso, novamente, apenas leva de volta à pergunta: por que você precisa fazer cluster e qual a confiabilidade? Por fim, essa é uma pergunta que você precisa responder com base em como você usará os dados.

Jeff
fonte
3

Para saber se um cluster é significativo, você pode executar um algoritmo para contar o número de clusters e verificar se ele gera algo maior que 1.

kk

kk

raegtin
fonte