Escolhendo o método de ligação correto para armazenamento em cluster hierárquico

Estou executando um cluster hierárquico de dados que reuni e processei no despejo de dados do reddit no Google BigQuery.

Meu processo é o seguinte:

• Receba as últimas 1000 postagens em / r / policy
• Reúna todos os comentários
• Processar os dados e calcular uma n x mmatriz de dados (n: usuários / amostras, m: postagens / recursos)
• Calcular a matriz de distância para armazenamento em cluster hierárquico
• Escolha um método de ligação e execute o armazenamento em cluster hierárquico
• Plote os dados como um dendograma

Minha pergunta é: como determino qual é o melhor método de vinculação ? Eu estou usando atualmente Ward, mas como eu sei se eu deveria estar usando single, complete, average, etc?

Sou muito novo nesse assunto, mas não consigo encontrar uma resposta clara on-line, pois não tenho certeza de que exista uma. Então, o que pode ser uma boa ideia para o meu aplicativo? Observe que os dados são relativamente escassos no sentido de que a n x mmatriz possui muitos zeros (a maioria das pessoas não comenta mais do que algumas publicações).

Visão geral dos métodos

Referência curta sobre alguns métodos de ligação da análise hierárquica de agrupamentos aglomerados (HAC).

A versão básica do algoritmo HAC é uma genérica; isso significa atualizar, a cada etapa, pela fórmula conhecida como fórmula de Lance-Williams, as proximidades entre o cluster emergente (mesclado de dois) e todos os outros clusters (incluindo objetos singleton) existentes até o momento. Existem implementações que não usam a fórmula de Lance-Williams. Mas usá-lo é conveniente: permite codificar vários métodos de vinculação pelo mesmo modelo.

A fórmula de recorrência inclui vários parâmetros (alfa, beta, gama). Dependendo do método de ligação, os parâmetros são definidos de maneira diferente e, portanto, a fórmula não empacotada obtém uma visualização específica. Muitos textos sobre HAC mostram a fórmula, suas visões específicas ao método e explicam os métodos. Eu recomendaria artigos de Janos Podani como muito detalhados.

O espaço e a necessidade dos diferentes métodos surgem do fato de que uma proximidade (distância ou semelhança) entre dois grupos ou entre um cluster e um objeto singleton pode ser formulada de várias maneiras. O HAC mescla a cada etapa os dois clusters ou pontos mais próximos, mas como calcular a proximidade acima mencionada na face em que a matriz de proximidade de entrada foi definida apenas entre objetos singleton, é o problema a ser formulado.

Portanto, os métodos diferem em relação à forma como definem a proximidade entre dois clusters a cada etapa. "Coeficiente de coligação" (saída no cronograma / histórico de aglomeração e formação do eixo "Y" em um dendrograma) é apenas a proximidade entre os dois clusters mesclados em uma determinada etapa.

• Método de ligação única ou vizinho mais próximo . A proximidade entre dois grupos é a proximidade entre os dois objetos mais próximos. Este valor é um dos valores da matriz de entrada. A metáfora conceitual dessa construção de cluster, seu arquétipo, é espectro ou cadeia . As correntes podem ser retas ou curvilíneas, ou podem ser como a vista "floco de neve" ou "ameba". Dois membros do cluster mais diferentes podem ser muito diferentes em comparação com os dois mais semelhantes. O método de ligação única controla apenas a similaridade de vizinhos mais próximos.

• Método de ligação completa ou vizinho mais distante . A proximidade entre dois grupos é a proximidade entre seus dois objetos mais distantes. Este valor é um dos valores da matriz de entrada. A metáfora dessa construção de aglomerado é círculo (no sentido, por hobby ou enredo), onde dois membros mais distantes um do outro não podem ser muito mais diferentes do que outros pares bastante diferentes (como em círculo). Esses aglomerados são contornos "compactos" pelas bordas, mas não são necessariamente compactos por dentro.

• Método de ligação média entre grupos (UPGMA). A proximidade entre dois grupos é a média aritmética de todas as proximidades entre os objetos de um, de um lado, e os objetos do outro, do outro lado. A metáfora desse agrupamento construído é bastante genérica, apenas classe unida ou coletivo unido; e o método é frequentemente definido como padrão nos pacotes de cluster hierárquico. Podem ser produzidos conjuntos de formas e contornos diversos.

• Média simples , ou método de ligação média entre grupos equilibrada (WPGMA) é o anterior modificado. A proximidade entre dois grupos é a média aritmética de todas as proximidades entre os objetos de um, de um lado, e os objetos do outro, do outro lado; enquanto os sub-clusters dos quais cada um desses dois clusters foram mesclados recentemente tiveram influência igualizada nessa proximidade - mesmo que os sub-clusters diferissem no número de objetos.

• Método de ligação média dentro do grupo (MNDIS). A proximidade entre dois aglomerados é a média aritmética de todas as proximidades em seu aglomerado conjunto. Este método é uma alternativa ao UPGMA. Geralmente ele perde em termos de densidade de cluster, mas às vezes descobre formas de cluster que o UPGMA não.

• Método centróide (UPGMC). A proximidade entre dois aglomerados é a proximidade entre seus centróides geométricos: distância euclidiana ao quadrado entre eles. A metáfora deste agrupamento construído é a proximidade de plataformas (política). Como nos partidos políticos, esses grupos podem ter frações ou "facções", mas, a menos que suas figuras centrais estejam separadas umas das outras, o sindicato é consistente. Os agrupamentos podem ser variados por esboço.

• O método mediano ou centróide equilibrado (WPGMC) é o anterior modificado. Proximidade entre dois aglomerados é a proximidade entre seus centróides geométricos (distância euclidiana quadrática) entre eles; enquanto os centróides são definidos de modo que os subconjuntos dos quais cada um desses dois clusters foram mesclados recentemente tenham influência equalizada em seu centróide - mesmo se os subclusters diferirem no número de objetos.

• $SS_{12}-(SS_1+SS_2)$$2$. Intuitivamente, um tipo é uma nuvem mais densa e concêntrica em relação ao meio, enquanto os pontos marginais são poucos e podem ser dispersos relativamente livremente.

Alguns dos métodos menos conhecidos (ver Podany J. Novos métodos combinatórios de agrupamento // Vegetatio, 1989, 81: 61-77.) [Também implementados por mim como uma macro SPSS encontrada em minha página da web]:

• $SS_{12}$$2$

• $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$$4$

• $MS_{12} = SS_{12}/(n_1+n_2)$$4$

Os primeiros 5 métodos permitem qualquer medida de proximidade (semelhanças ou distâncias) e os resultados dependerão, naturalmente, da medida escolhida.

Os últimos 6 métodos exigem distâncias; e totalmente correto será usar apenas distâncias euclidianas quadradas com eles, porque esses métodos calculam centróides no espaço euclidiano. Portanto, as distâncias devem ser euclidianas para fins de correção geométrica (esses 6 métodos são chamados de métodos de ligação geométrica juntos ). Na pior das hipóteses, você pode inserir outra métricadistâncias em admitir análises mais heurísticas e menos rigorosas. Agora sobre isso "ao quadrado". A computação dos centróides e os desvios deles são mais convenientes matematicamente / programaticamente para executar em distâncias ao quadrado, é por isso que os pacotes HAC geralmente requerem entrada e são ajustados para processar os quadrados. No entanto, existem implementações - totalmente equivalentes, mas um pouco mais lentas - com base em distâncias não-quartas e exigindo essas; veja por exemplo a implementação "Ward-2" para o método de Ward. Você deve consultar a documentação do seu programa de clustering para saber quais distâncias quadradas ou não ele espera na entrada de um "método geométrico" para fazê-lo corretamente.

Os métodos MNDIS, MNSSQ e MNVAR exigem etapas, além de atualizar apenas a fórmula de Lance-Williams, para armazenar uma estatística dentro do cluster (que depende do método).

Métodos que são usados ​​com mais freqüência em estudos onde se espera que os clusters sejam sólidos mais ou menos nuvens redondas, - são métodos de ligação média, método de ligação completo e método de Ward.

O método de Ward é o mais próximo, por suas propriedades e eficiência, do agrupamento K-means; eles compartilham a mesma função objetivo - minimização do SS agrupado dentro do cluster "no final". Obviamente, o K-means (sendo iterativo e se for fornecido com centróides iniciais decentes) geralmente é um minimizador melhor do que Ward. Entretanto, Ward me parece um pouco mais preciso do que o K-significa na descoberta de aglomerados de tamanhos físicos desiguais (variações) ou aglomerados lançados sobre o espaço de maneira muito irregular. O método MIVAR é estranho para mim, não consigo imaginar quando poderia ser recomendado, não produz clusters densos o suficiente.

Métodos centróide, mediano, aumento mínimo de variância - podem dar às vezes as chamadas reversões : um fenômeno em que os dois grupos que estão sendo mesclados em algum momento parecem mais próximos um do outro do que pares de grupos mesclados anteriormente. Isso ocorre porque esses métodos não pertencem ao chamado ultramétrico. Essa situação é inconveniente, mas teoricamente está OK.

Os métodos de ligação única e centróide pertencem à chamada contratação espacial , ou "encadeamento". Isso significa - grosso modo - que eles tendem a anexar objetos um a um aos clusters e, portanto, demonstram um crescimento relativamente suave da curva “% de objetos em cluster”. Pelo contrário, os métodos de ligação completa, Ward, soma dos quadrados, aumento da variação e variação geralmente recebem uma parcela considerável de objetos agrupados mesmo nas etapas iniciais e, em seguida, continuam a mesclá-los - portanto, sua curva “% de objetos agrupados ”É íngreme desde os primeiros passos. Esses métodos são chamados de dilatação do espaço . Outros métodos se enquadram no meio.

Versões flexíveis . Ao adicionar o parâmetro adicional à fórmula de Lance-Willians, é possível fazer com que um método se torne especificamente auto-ajustável em suas etapas. O parâmetro traz a correção para a proximidade entre os clusters, que depende do tamanho (quantidade de descompactação) dos clusters. O significado do parâmetro é que ele torna o método de aglomeração mais dilatador ou contratante de espaço do que o método padrão está fadado a ser. A implementação mais conhecida da flexibilidade até agora é a média dos métodos de ligação UPGMA e WPGMA (Belbin, L. et al. Uma Comparação de Duas Abordagens ao Clustering Beta-Flexível // Multivariate Behavioral Research, 1992, 27, 417-433. )

Dendrograma. Em um eixo "Y" do dendograma, normalmente é exibida a proximidade entre os clusters mesclados - conforme definido pelos métodos acima. Portanto, por exemplo, no método centróide, a distância ao quadrado é tipicamente medida (em última análise, depende do pacote e das opções) - algumas pesquisas não estão cientes disso. Além disso, por tradição, com métodos baseados no incremento de não densidade, como os de Ward, geralmente mostrados no dendrograma, é um valor cumulativo - é mais cedo por razões de conveniência do que as teóricas. Assim, (em muitos pacotes), o coeficiente plotado no método de Ward representa o total, em todos os clusters, da soma dos quadrados dentro do cluster observados no momento de uma determinada etapa.

Deve-se abster-se de julgar qual método de ligação é "melhor" para seus dados, comparando a aparência dos dendrogramas: não apenas porque a aparência muda quando você altera a modificação do coeficiente que você planeja lá - como foi descrito recentemente -, mas porque a aparência será diferente mesmo nos dados sem clusters.

Para escolher o método "certo"

Não existe um critério único . Algumas diretrizes sobre como selecionar um método de análise de cluster (incluindo um método de ligação no HAC como um caso específico) são descritas nesta resposta e em todo o segmento.

A correlação entre a matriz de distância e a distância copenética é uma métrica para ajudar a avaliar qual ligação de agrupamento selecionar. De ?cophenetic:

Pode-se argumentar que um dendrograma é um resumo apropriado de alguns dados se a correlação entre as distâncias originais e as distâncias cofenéticas for alta.

Esse uso de cor(dist,cophenetic(hclust(dist)))métrica de seleção de ligação é referenciado na página 38 desta vegan vinheta .

Veja o código de exemplo abaixo:

# Data
d0=dist(USArrests)

# Hierarchical Agglomerative Clustering
h1=hclust(d0,method='average')
h2=hclust(d0,method='complete')
h3=hclust(d0,method='ward.D')
h4=hclust(d0,method='single')

# Cophenetic Distances, for each linkage
c1=cophenetic(h1)
c2=cophenetic(h2)
c3=cophenetic(h3)
c4=cophenetic(h4)

# Correlations
cor(d0,c1) # 0.7658983
cor(d0,c2) # 0.7636926
cor(d0,c3) # 0.7553367
cor(d0,c4) # 0.5702505

# Dendograms
par(mfrow=c(2,2))
plot(h1,main='Average Linkage')
plot(h2,main='Complete Linkage')
plot(h3,main='Ward Linkage')
plot(h4,main='Single Linkage')
par(mfrow=c(1,1))

Vemos que as correlações para averagee completesão extremamente semelhantes e seus dendogramas parecem muito semelhantes. A correlação de wardé semelhante ao averagee completemas o dendograma parece bastante diferente. singleligação está fazendo a sua própria coisa. O melhor julgamento profissional de um especialista no assunto ou a precedência em relação a um determinado link no campo de interesse provavelmente devem substituir a saída numérica de cor().