Como entender as desvantagens do cluster hierárquico?

19

Alguém pode explicar os prós e os contras do cluster hierárquico?

O cluster hierárquico tem as mesmas desvantagens que K significa?
Quais são as vantagens do cluster hierárquico sobre o K significa?
Quando devemos usar os meios K sobre o cluster hierárquico e vice-versa?

As respostas a este post explicam muito bem as desvantagens de k. Como entender as desvantagens do K-means

clustering k-means unsupervised-learning hierarchical-clustering GeorgeOfTheRF
fonte

2

Em esta resposta Toquei algumas das facetas potencialmente problemáticas da análise de cluster agglomerative hierárquica. A principal "desvantagem" é que é um algoritmo ganancioso de passagem única e não -iterativo. Com um algoritmo ganancioso, você otimiza a tarefa da etapa atual, que - para a maioria dos métodos HC - não garante necessariamente a melhor partição em uma etapa futura distante. A principal vantagem do HC é que ele é flexível com relação à escolha da medida de proximidade a ser usada. O @Mic já deu uma boa resposta abaixo, então estou apenas ecoando.

ttnphns

13

Considerando que -means tenta otimizar um objetivo global (variação dos clusters) e alcança um cluster hierárquico aglomerado ideal local, visando encontrar a melhor etapa em cada fusão de cluster (algoritmo ganancioso), que é feita exatamente, mas resultando em uma solução potencialmente subótima . $k$

Deve-se usar o cluster hierárquico quando os dados subjacentes tiverem uma estrutura hierárquica (como as correlações nos mercados financeiros) e você desejar recuperar a hierarquia. Você ainda pode aplicar os meios $k$ para fazer isso, mas pode acabar com partições (do mais grosseiro (todos os pontos de dados de um cluster) até o mais fino (cada ponto de dados é um cluster)) que não está aninhado e, portanto, não é uma hierarquia adequada.

Se você deseja se aprofundar nas propriedades mais refinadas do cluster, talvez não queira opor o cluster simples, como -eans, ao cluster hierárquico, como os Links Único, Médio e Completo. Por exemplo, todos esses clusters economizam espaço, ou seja, quando você está construindo clusters, não distorce o espaço, enquanto um cluster hierárquico como Ward não economiza espaço, ou seja, a cada etapa da fusão, distorce o espaço métrico. $k$

Para concluir, as desvantagens dos algoritmos hierárquicos de clustering podem ser muito diferentes entre si. Alguns podem compartilhar propriedades semelhantes a $k$ -means: Ward visa otimizar a variação, mas o Single Linkage não. Mas eles também podem ter propriedades diferentes: Ward é dilatador de espaço, enquanto o Single Linkage é conservador de espaço, como $k$ médias.

- edite para precisar as propriedades de conservação e dilatação de espaço

D_{i j} \in [min_{x \in C_{i}, y \in C_{j}} d (x, y), max_{x \in C_{i}, y \in C_{j}} d (x, y)]

$D_{ij} \in \left[ \min_{x \in C_i, y \in C_j} d(x,y), \max_{x \in C_i, y \in C_j} d(x,y) \right]$ onde

é a distância entre os agrupamentos

e

você deseja mesclar

D_{i j}

$D_{ij}$

C_{i}

$C_i$

C_{j}

$C_j$

d

$d$ é a distância entre os pontos de dados.

Dilatação de espaço: ou seja, mediante a fusão e o algoritmo vai empurrar mais longe do cluster.

D (C_{i} \cup C_{j}, C_{k}) \geq max (D_{i k}, D_{j k}),

$D(C_i \cup C_j, C_k) \geq \max(D_{ik}, D_{jk}),$

C_{i}

$C_i$

C_{j}

$C_j$

C_{k}

$C_k$

microfone
fonte

Você pode dar mais alguns exemplos de dados com estrutura hierárquica? Não seguiu o exemplo do mercado financeiro.

GeorgeOfTheRF 27/11

Certo. cf. arxiv.org/pdf/cond-mat/9802256.pdf ou simplesmente Figura 7 em arxiv.org/pdf/1506.00976.pdf, que descreve uma matriz de correlação que possui uma estrutura de bloco de correlação hierárquica (barulhenta): você pode observar blocos nas principais diagonal, que são divididos em mais blocos, cada um dividido em ainda mais blocos. Corresponde aproximadamente a uma subdivisão nas regiões (Europa, EUA, Ásia, exceto Japão, Japão) e, em seguida, cada região é dividida pela qualidade dos ativos (por exemplo, alta qualidade versus lixo eletrônico) e depois dividida pelos grandes setores industriais (varejo, indústria, media), subdivide-se ainda mais em (aeroespacial, automático ...)

mic

3

+1. No entanto,

should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchy

não necessariamente. Na maioria dos casos, pelo contrário. A hierarquia do HC é mais uma história do algo do que uma estrutura dos dados . Ainda assim, essa questão é filosófica / lógica, não tão estatística.

ttnphns

Ward is not space-conserving, i.e. at each merging step it will distort the metric space. Você pode escrever mais sobre isso? Isso não está muito claro.

ttnphns

Ward is space-dilating, whereas Single Linkage is space-conserving like k-means. Você gostaria de contratar contratos de espaço para ligação única?

ttnphns

13

Escalabilidade

significa é o vencedor claro aqui. é muito melhor do que o (em um dos casos alguns ) escalabilidade de agrupamento hierárquico porque geralmente ambos e e são pequenos (infelizmente, tende a crescer com , então faznão $k$ $O(n\cdot k\cdot d\cdot i)$ $O(n^3 d)$ $O(n^2 d)$ $k$ $i$ $d$ $i$ $n$ $O(n)$ normalmente segure). Além disso, o consumo de memória é linear, ao contrário de quadrático (geralmente existem casos especiais lineares).

Flexibilidade

método é extremamente limitado em aplicabilidade. É essencialmente limitado a distâncias euclidianas (incluindo euclidianas em espaços de núcleo e divergências de Bregman, mas são bastante exóticas e ninguém as usa com médias). Pior ainda, significa apenas funciona em dados numéricos (que na verdade devem ser contínuos e densos para ser um bom ajuste para significa). $k$ $k$ $k$ $k$

O cluster hierárquico é o vencedor claro aqui. Nem sequer requer uma distância - qualquer medida pode ser usada, incluindo funções de similaridade, simplesmente preferindo valores altos a valores baixos. Dados categoriais? Certifique-se de usar, por exemplo, Jaccard. Cordas? Experimente a distância de Levenshtein. Séries temporais? certo. Dados do tipo misto? Distância de Gower. Existem milhões de conjuntos de dados nos quais você pode usar o cluster hierárquico, mas onde não pode usar -means. $k$

Modelo

Nenhum vencedor aqui. significa pontuação alta porque gera uma grande redução de dados. Os centróides são fáceis de entender e usar. O agrupamento hierárquico, por outro lado, produz um dendrograma. Um dendograma também pode ser muito, muito útil para entender seu conjunto de dados. $k$

Anony-Mousse -Reinstate Monica
fonte

A falha hierárquica como k significa quando os agrupamentos são 1) não esféricos 2) têm raio diferente 3) têm densidade diferente?

GeorgeOfTheRF 28/11

2

Ambos podem funcionar e ambos podem falhar. É por isso que coisas como dendrogramas são úteis. Nunca confie que um resultado de cluster esteja "correto", nunca.

Anony-Mousse -Reinstala Monica 28/11

O cluster hierárquico pode fornecer clusters otimizados localmente, pois é baseado em uma abordagem gananciosa, mas K significa fornecer clusters otimizados globalmente. Eu também experimentei que a explicação do cluster hierárquico é relativamente fácil para as pessoas de negócios compararem com os meios K.

Arpit Sisodia

7

Eu só queria acrescentar às outras respostas um pouco sobre como, em certo sentido, há uma forte razão teórica para preferir certos métodos hierárquicos de agrupamento.

Uma suposição comum na análise de cluster é que os dados são amostrados de alguma densidade de probabilidade subjacente qual não temos acesso. Mas suponha que tivéssemos acesso a ele. Como definiríamos os grupos de ? $f$ $f$

Uma abordagem muito natural e intuitiva é dizer que os grupos de $f$ são as regiões de alta densidade. Por exemplo, considere a densidade de dois picos abaixo:

Ao desenhar uma linha no gráfico, induzimos um conjunto de clusters. Por exemplo, se traçarmos uma linha em , obteremos os dois clusters mostrados. Mas se traçarmos a linha em $\lambda_1$ $\lambda_3$ , obteremos um único cluster.

Para tornar isso mais preciso, suponha que temos um arbitrário . Quais são os clusters de no nível ? Eles são o componente conectado ao conjunto de superníveis . $\lambda > 0$ $f$ $\lambda$ $\{x : f(x) \geq \lambda \}$

$\lambda$ $\lambda$ $f$ $f$

$f$ $\mathcal X$ $C_1$ $\{ x : f(x) \geq \lambda_1 \}$ $C_2$ $\{ x : f(x) \geq \lambda_2 \}$ $C_1$ $\lambda_1$ $C_2$ $\lambda_2$ $\lambda_2 < \lambda_1$ $C_1 \subset C_2$ $C_1 \cap C_2 = \emptyset$

Então agora eu tenho alguns dados amostrados de uma densidade. Posso agrupar esses dados de maneira a recuperar a árvore do cluster? Em particular, gostaríamos que um método fosse consistente no sentido de que, à medida que reunimos mais e mais dados, nossa estimativa empírica da árvore de cluster se aproxima cada vez mais da verdadeira árvore de cluster.

$A$ $B$ $f$ $n$ $f$ $X_n$ $X_n$ $A_n$ $A \cap X_n$ $B_n$ $B \cap X_n$ $\Pr(A_n \cap B_n) = \emptyset \to 1$ $n \to \infty$ $A$ $B$

Essencialmente, a consistência de Hartigan diz que nosso método de agrupamento deve separar adequadamente regiões de alta densidade. Hartigan investigou se o clustering de ligação única pode ser consistente e descobriu que é não consistente em dimensões> 1. O problema de encontrar um método geral e consistente para estimar a árvore de cluster estava aberto até poucos anos atrás, quando Chaudhuri e Dasgupta introduziram ligação única robusta , comprovadamente consistente. Eu sugiro ler sobre o método deles, como é bastante elegante, na minha opinião.

Portanto, para responder às suas perguntas, há um sentido em que cluster hierárquico é a coisa "certa" a ser feita ao tentar recuperar a estrutura de uma densidade. No entanto, observe as aspas em torno de "corretas" ... Em última análise, os métodos de agrupamento com base na densidade tendem a apresentar um desempenho ruim em altas dimensões devido à maldição da dimensionalidade e, mesmo assim, uma definição de agrupamento com base em agrupamentos sendo regiões de alta probabilidade é bastante limpo e intuitivo, geralmente é ignorado em favor de métodos com melhor desempenho na prática. Isso não quer dizer que a ligação única robusta não seja prática - ela realmente funciona muito bem em problemas de dimensões inferiores.

Por fim, direi que, em certo sentido, a consistência de Hartigan não está de acordo com nossa intuição de convergência. O problema é que a consistência Hartigan permite que um método de agrupamento ultrapasse os clusters de maneira muito segmentada , de modo que um algoritmo possa ser consistente com o Hartigan, mas produza agrupamentos muito diferentes da verdadeira árvore de agrupamentos. Este ano, produzimos trabalhos sobre uma noção alternativa de convergência que aborda essas questões. O trabalho apareceu em "Além da consistência de Hartigan: métrica de distorção de mesclagem para cluster hierárquico" no COLT 2015.

jme
fonte

Essa é uma maneira interessante de pensar sobre cluster hierárquico. Acho que é fortemente reminiscente de agrupamento por estimativa não paramétrica densidade ( pdf ), que é implementado em Rno pdfCluster pacote. (Discuto aqui .)

gung - Restabelece Monica

HDBSCAN * usa uma abordagem semelhante.

Anony-Mousse -Reinstala Monica 28/11

3

$k$ sem a necessidade de criar agrupamentos separados. O Dedrogram também pode fornecer uma excelente visão da estrutura de dados, ajudar a identificar valores discrepantes etc. O cluster hierárquico também é determinístico, enquanto o k-means com inicialização aleatória pode fornecer resultados diferentes quando executado várias vezes nos mesmos dados. No k-means, você também pode escolher métodos diferentes para atualizar os meios de cluster (embora a abordagem Hartigan-Wong seja de longe a mais comum), o que não é problema com o método hierárquico.

EDITAR graças ao ttnphns: Um recurso que o cluster hierárquico compartilha com muitos outros algoritmos é a necessidade de escolher uma medida de distância. Isso geralmente depende muito da aplicação e dos objetivos específicos. Isso pode ser visto como uma complicação adicional (outro parâmetro para selecionar ...), mas também como um ativo - mais possibilidades. Pelo contrário, o algoritmo K-means clássico usa especificamente a distância euclidiana.

Jacek Podlewski
fonte

3

Suponho que "problema" em seu último parágrafo seja visto positivamente como um ativo. O K-significa, no entanto, baseia-se implicitamente apenas na distância euclidiana .

ttnphns

Muitas opções possíveis podem ser um problema e um ativo, de fato :) Obrigado pelo comentário sobre k-means, melhorarei esse parágrafo.

Jacek Podlewski

k

$k$

k

$k$

Acredito que a pergunta original foi feita com relação aos meios K "clássicos" e não com a menor intenção de investigar as divergências de Bregman. Observação agradável, porém, vou verificar este artigo com mais detalhes.

Jacek Podlewski

@mic ninguém usa divergências de Bregman além das variações da distância euclidiana ... é apenas uma classe minúscula. Mas as pessoas gostariam de usar, por exemplo, a distância de Manhattan, Gower etc., que não são divergências de Bregman, pelo que sei.

Anony-Mousse - Re: Monica Monica 28/11

Como entender as desvantagens do cluster hierárquico?

Respostas:

Escalabilidade

Flexibilidade

Modelo