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

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?

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.

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).

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 :

Olivetti enfrenta o conjunto de dados:

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).

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".

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.

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.

$k$$k$

$k$$k$