Agrupamento hierárquico - Hierarchical clustering

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Clustering Regressão Detecção de anomalia Limpeza de Dados AutoML Regras de associação Aprendizagem por reforço Previsão estruturada Engenharia de recursos Aprendizagem de recursos Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendendo a classificar Indução gramatical
Aprendizagem supervisionada ( classificação  • regressão ) Árvores de decisão Conjuntos Ensacamento Boosting Floresta aleatória k -NN Regressão linear Baías ingénuas Redes neurais artificiais Regressão logística Perceptron Máquina de vetor de relevância (RVM) Máquina de vetores de suporte (SVM)
Clustering BÉTULA CURA Hierárquico k- significa Expectativa-maximização (EM) DBSCAN ÓPTICA Mudança média
Redução de dimensionalidade Análise Fatorial CCA ICA LDA NMF PCA PGD t-SNE
Previsão estruturada Modelos gráficos Rede Bayes Campo aleatório condicional Markov Oculto
Detecção de anomalia k -NN Fator de outlier local
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformador Spiking rede neural Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Q-learning SARSA Diferença temporal (TD)
Teoria Compensação de polarização-variância Teoria de aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv: cs.LG
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa de aprendizado de máquina Esboço do aprendizado de máquina
v t e

Na mineração de dados e estatísticas , o clustering hierárquico (também chamado de análise de cluster hierárquico ou HCA ) é um método de análise de cluster que busca construir uma hierarquia de clusters. As estratégias de clustering hierárquico geralmente se enquadram em dois tipos:

• Aglomerativo : Esta é uma abordagem "de baixo para cima ": cada observação começa em seu próprio agrupamento e pares de agrupamentos são mesclados à medida que se sobe na hierarquia.
• Divisiva : Esta é uma abordagem "de cima para baixo ": todas as observações começam em um agrupamento e as divisões são realizadas recursivamente à medida que se desce na hierarquia.

Em geral, as fusões e divisões são determinadas de maneira gananciosa . Os resultados do agrupamento hierárquico são geralmente apresentados em um dendrograma .

O algoritmo padrão para clustering aglomerativo hierárquico (HAC) tem uma complexidade de tempo de e requer memória, o que o torna muito lento até mesmo para conjuntos de dados médios. No entanto, para alguns casos especiais, métodos aglomerativos eficientes ideais (de complexidade ) são conhecidos: SLINK para ligação única e CLINK para agrupamento de ligação completa . Com um heap , o tempo de execução do caso geral pode ser reduzido a uma melhoria no limite mencionado acima , ao custo de aumentar ainda mais os requisitos de memória. Em muitos casos, a sobrecarga de memória dessa abordagem é muito grande para torná-la utilizável na prática. ${\ displaystyle {\ mathcal {O}} (n ^ {3})}$${\ displaystyle \ Omega (n ^ {2})}$${\ displaystyle {\ mathcal {O}} (n ^ {2})}$${\ displaystyle {\ mathcal {O}} (n ^ {2} \ log n)}$${\ displaystyle {\ mathcal {O}} (n ^ {3})}$

Exceto para o caso especial de ligação única, nenhum dos algoritmos (exceto pesquisa exaustiva em ) pode ser garantido para encontrar a solução ótima. ${\ displaystyle {\ mathcal {O}} (2 ^ {n})}$

O agrupamento divisivo com uma pesquisa exaustiva é , mas é comum usar heurísticas mais rápidas para escolher divisões, como k -means . ${\ displaystyle {\ mathcal {O}} (2 ^ {n})}$

Diferença de cluster

Para decidir quais clusters devem ser combinados (para aglomerativo), ou onde um cluster deve ser dividido (para divisivo), é necessária uma medida de dissimilaridade entre conjuntos de observações. Na maioria dos métodos de agrupamento hierárquico, isso é obtido pelo uso de uma métrica apropriada (uma medida de distância entre pares de observações) e um critério de ligação que especifica a dissimilaridade dos conjuntos como uma função das distâncias entre pares de observações nos conjuntos.

Métrica

A escolha de uma métrica apropriada influenciará a forma dos clusters, pois alguns elementos podem estar relativamente mais próximos uns dos outros em uma métrica do que em outra. Por exemplo, em duas dimensões, na métrica de distância de Manhattan, a distância entre a origem (0,0) e (0,5, 0,5) é a mesma que a distância entre a origem e (0, 1), enquanto sob a distância euclidiana métrica, a última é estritamente maior.

Algumas métricas comumente usadas para clustering hierárquico são:

Nomes	Fórmula
Distância euclidiana	${\ displaystyle \ | ab \ | _ {2} = {\ sqrt {\ sum _ {i} (a_ {i} -b_ {i}) ^ {2}}}}$
Distância euclidiana quadrada	${\ displaystyle \ | ab \ | _ {2} ^ {2} = \ sum _ {i} (a_ {i} -b_ {i}) ^ {2}}$
Distância de Manhattan (ou quarteirão)	${\ displaystyle \ | ab \ | _ {1} = \ sum _ {i} | a_ {i} -b_ {i} |}$
Distância máxima (ou distância de Chebyshev)	${\ displaystyle \ | ab \ | _ {\ infty} = \ max _ {i} | a_ {i} -b_ {i} |}$
Distância de Mahalanobis	${\ displaystyle {\ sqrt {(ab) ^ {\ top} S ^ {- 1} (ab)}}}$onde S é a matriz de covariância

Para texto ou outros dados não numéricos, métricas como a distância de Hamming ou distância de Levenshtein são freqüentemente usadas.

As distâncias euclidiana e de Manhattan são os casos especiais de distância de Minkowski generalizada com p = 1 (para Manhattan) ep = 2 (para Euclidiana).

Existem várias outras medidas de dissimilaridade. Particularmente, distâncias baseadas em correlação - distâncias de correlação de Pearson, Eisen co-seno, Spearman, Kendall, que são amplamente utilizadas para análises de dados de expressão gênica. A distância baseada em correlação é definida subtraindo o coeficiente de correlação de 1. Falando estritamente, as distâncias baseadas em correlação não podem ser usadas como métricas, enquanto a raiz quadrada pode ser.

Uma revisão da análise de agrupamento em pesquisas em psicologia da saúde descobriu que a medida de distância mais comum em estudos publicados nessa área de pesquisa é a distância euclidiana ou a distância euclidiana quadrada.

Critérios de ligação

O critério de ligação determina a distância entre conjuntos de observações como uma função das distâncias aos pares entre as observações.

Alguns critérios de ligação comumente usados ​​entre dois conjuntos de observações A e B são:

Nomes	Fórmula
Clustering de ligação máxima ou completa	${\ displaystyle \ max \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$
Clustering mínimo ou de ligação única	${\ displaystyle \ min \, \ {\, d (a, b): a \ in A, \, b \ in B \, \}.}$
Agrupamento de ligação média não ponderada (ou UPGMA )	${\ displaystyle {\ frac {1} {| A | \ cdot | B |}} \ sum _ {a \ in A} \ sum _ {b \ in B} d (a, b).}$
Agrupamento de ligação média ponderada (ou WPGMA )	${\ displaystyle d (i \ cup j, k) = {\ frac {d (i, k) + d (j, k)} {2}}.}$
Agrupamento de ligação centróide ou UPGMC	${\ displaystyle \ | c_ {s} -c_ {t} \ |}$onde e são os centróides dos clusters s e t , respectivamente. ${\ displaystyle c_ {s}}$${\ displaystyle c_ {t}}$
Agrupamento mínimo de energia	${\ displaystyle {\ frac {2} {nm}} \ sum _ {i, j = 1} ^ {n, m} \ | a_ {i} -b_ {j} \ | _ {2} - {\ frac {1} {n ^ {2}}} \ sum _ {i, j = 1} ^ {n} \ | a_ {i} -a_ {j} \ | _ {2} - {\ frac {1} { m ^ {2}}} \ sum _ {i, j = 1} ^ {m} \ | b_ {i} -b_ {j} \ | _ {2}}$

onde d é a métrica escolhida. Outros critérios de ligação incluem:

• A soma de todas as variâncias intracluster.
• O aumento da variância para o cluster que está sendo mesclado ( critério de Ward ).
• A probabilidade de que os clusters candidatos gerem a mesma função de distribuição (V-linkage).
• O produto do grau de entrada e do grau de saída em um gráfico de k-vizinho mais próximo (vínculo de grau do gráfico).
• O incremento de algum descritor de cluster (ou seja, uma quantidade definida para medir a qualidade de um cluster) após a fusão de dois clusters.

Discussão

O agrupamento hierárquico tem a vantagem distinta de que qualquer medida válida de distância pode ser usada. Na verdade, as observações em si não são necessárias: tudo o que é usado é uma matriz de distâncias.

Exemplo de agrupamento aglomerativo

Dados não tratados

Por exemplo, suponha que esses dados sejam agrupados e a distância euclidiana seja a métrica da distância .

O dendrograma de agrupamento hierárquico seria como tal:

Representação tradicional

Cortar a árvore em uma determinada altura dará um agrupamento de particionamento em uma precisão selecionada. Neste exemplo, o corte após a segunda linha (do topo) do dendrograma produzirá clusters {a} {bc} {de} {f}. Cortar após a terceira linha produzirá clusters {a} {bc} {def}, que é um cluster mais grosso, com um número menor, mas clusters maiores.

Este método constrói a hierarquia dos elementos individuais mesclando clusters progressivamente. Em nosso exemplo, temos seis elementos {a} {b} {c} {d} {e} e {f}. A primeira etapa é determinar quais elementos fundir em um cluster. Normalmente, queremos levar os dois elementos mais próximos, de acordo com a distância escolhida.

Opcionalmente, também se pode construir uma matriz de distância neste estágio, onde o número na i -ésima linha j -ésima coluna é a distância entre os i- ésimos e j- ésimos elementos. Então, conforme o clustering progride, linhas e colunas são mescladas conforme os clusters são mesclados e as distâncias atualizadas. Esta é uma maneira comum de implementar esse tipo de cluster e tem o benefício de distâncias de armazenamento em cache entre os clusters. Um algoritmo de agrupamento aglomerativo simples é descrito na página de agrupamento de ligação única ; pode ser facilmente adaptado a diferentes tipos de ligação (veja abaixo).

Suponha que fundimos os dois elementos b e c mais próximos , agora temos os seguintes clusters { a }, { b , c }, { d }, { e } e { f }, e queremos fundi-los ainda mais. Para fazer isso, precisamos medir a distância entre {a} e {bc} e, portanto, definir a distância entre dois clusters. Normalmente, a distância entre dois clusters e é um dos seguintes: ${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {B}}}$

• A distância máxima entre os elementos de cada cluster (também chamado de clustering de ligação completa ):

${\ displaystyle \ max \ {\, d (x, y): x \ in {\ mathcal {A}}, \, y \ in {\ mathcal {B}} \, \}.}$

• A distância mínima entre os elementos de cada cluster (também chamado de cluster de ligação única ):

${\ displaystyle \ min \ {\, d (x, y): x \ in {\ mathcal {A}}, \, y \ in {\ mathcal {B}} \, \}.}$

• A distância média entre os elementos de cada cluster (também chamado de agrupamento de ligação média, usado, por exemplo, em UPGMA ):

${\ displaystyle {1 \ over {| {\ mathcal {A}} | \ cdot | {\ mathcal {B}} |}} \ sum _ {x \ in {\ mathcal {A}}} \ sum _ {y \ in {\ mathcal {B}}} d (x, y).}$

• A soma de todas as variâncias intracluster.
• O aumento da variância para o cluster que está sendo mesclado ( método de Ward )
• A probabilidade de que os clusters candidatos gerem a mesma função de distribuição (V-linkage).

No caso de distâncias mínimas empatadas, um par é escolhido aleatoriamente, podendo assim gerar vários dendrogramas estruturalmente diferentes. Alternativamente, todos os pares amarrados podem ser unidos ao mesmo tempo, gerando um dendrograma único.

Sempre se pode decidir interromper o agrupamento quando houver um número suficientemente pequeno de agrupamentos (critério de número). Algumas ligações também podem garantir que a aglomeração ocorra a uma distância maior entre os clusters do que a aglomeração anterior, e então pode-se parar o cluster quando os clusters estão muito distantes para serem mesclados (critério da distância). No entanto, este não é o caso, por exemplo, da ligação centróide, onde as chamadas reversões (inversões, desvios da ultrametricidade) podem ocorrer.

Agrupamento divisivo

O princípio básico do agrupamento divisivo foi publicado como o algoritmo DIANA (DIvisive ANAlysis Clustering). Inicialmente, todos os dados estão no mesmo cluster, e o maior cluster é dividido até que cada objeto seja separado. Como existem maneiras de dividir cada cluster, heurísticas são necessárias. DIANA escolhe o objeto com a dissimilaridade média máxima e então move todos os objetos para este cluster que são mais semelhantes ao novo cluster do que ao restante. ${\ displaystyle O (2 ^ {n})}$

Programas

Implementações de código aberto

Hierárquica agrupamento dendrograma do conjunto de dados da íris (usando R ). Fonte

Clustering hierárquico e visualização de dendrograma interativo no pacote de mineração de dados Orange .

• ALGLIB implementa vários algoritmos de agrupamento hierárquico (link único, link completo, Ward) em C ++ e C # com memória O (n²) e tempo de execução O (n³).
• ELKI inclui vários algoritmos de agrupamento hierárquico, várias estratégias de ligação e também inclui os algoritmos SLINK, CLINK e Anderberg eficientes, extração de agrupamento flexível de dendrogramas e vários outros algoritmos de análise de agrupamento .
• Octave , o GNU análogo ao MATLAB implementa clustering hierárquico na função "linkage".
• Orange , um pacote de software de mineração de dados, inclui clustering hierárquico com visualização interativa de dendrogramas.
• R tem muitos pacotes que fornecem funções para clustering hierárquico.
• SciPy implementa clustering hierárquico em Python, incluindo o algoritmo SLINK eficiente.
• scikit-learn também implementa clustering hierárquico em Python.
• Weka inclui análise de cluster hierárquica.

Implementações comerciais

• O MATLAB inclui análise de cluster hierárquica.
• O SAS inclui análise hierárquica de cluster no PROC CLUSTER.
• O Mathematica inclui um Pacote Hierárquico de Cluster.
• NCSS inclui análise de cluster hierárquica.
• O SPSS inclui análise de cluster hierárquica.
• Qlucore Omics Explorer inclui análise de cluster hierárquica.
• Stata inclui análise de cluster hierárquica.
• CrimeStat inclui um algoritmo de cluster hierárquico vizinho mais próximo com uma saída gráfica para um Sistema de Informação Geográfica.

Veja também

Referências

Leitura adicional

• Kaufman, L .; Rousseeuw, PJ (1990). Encontrando Grupos em Dados: Uma Introdução à Análise de Cluster (1 ed.). Nova York: John Wiley. ISBN 0-471-87876-6.
• Hastie, Trevor ; Tibshirani, Robert ; Friedman, Jerome (2009). "14.3.12 Clustering hierárquico" . Os Elementos de Aprendizagem Estatística (2ª ed.). Nova York: Springer. pp. 520–8. ISBN 978-0-387-84857-0. Arquivado do original (PDF) em 10/11/2009 . Página visitada em 2009-10-20 .