Visão geral da análise de cluster hierárquica
Antes de prosseguirmos e entendermos sobre a análise hierárquica de clustering, primeiro tentemos entender o que é um cluster? E o que é análise de cluster? Um cluster é uma coleção de objetos de dados; os pontos de dados dentro de um cluster são mais semelhantes entre si e diferentes dos pontos de dados no outro cluster. A análise de cluster é basicamente um agrupamento desses pontos de dados no cluster. O clustering é um tipo de algoritmo de aprendizado de máquina não supervisionado, em que não há conjuntos de dados rotulados de treinamento. Existem vários tipos de análise de cluster, um desses tipos é o cluster hierárquico.
O cluster hierárquico ajudará na criação de clusters em uma ordem / hierarquia adequada. Exemplo: o exemplo diário mais comum que vemos é como ordenamos nossos arquivos e pastas em nosso computador pela hierarquia adequada.
Tipos de cluster hierárquico
O cluster hierárquico é ainda classificado em dois tipos, ou seja, cluster aglomerativo e cluster divisivo (DIANA)
Agrupamento aglomerativo
Nesse caso de cluster, a decomposição hierárquica é feita com a ajuda da estratégia de baixo para cima, onde começa criando clusters atômicos (pequenos) adicionando um objeto de dados por vez e depois os mesclando para formar um grande cluster no final, onde este cluster atende a todas as condições de finalização. Este procedimento é iterativo até que todos os pontos de dados sejam colocados em um único grande cluster.
AGNES (AGglomerative NESting) é um tipo de cluster aglomerativo que combina os objetos de dados em um cluster com base na similaridade. O resultado desse algoritmo é um estruturado baseado em árvore chamado Dendrogram. Aqui, ele usa as métricas de distância para decidir quais pontos de dados devem ser combinados com qual cluster. Basicamente, ele constrói uma matriz de distância e verifica o par de clusters com a menor distância e os combina.
A figura acima mostra o agrupamento aglomerativo vs. divisivo
Com base em como a distância entre cada cluster é medida, podemos ter 3 métodos diferentes
- Ligação única : onde a menor distância entre os dois pontos em cada cluster é definida como a distância entre os clusters.
- Ligação completa : neste caso, consideraremos a maior distância entre os pontos em cada cluster como a distância entre os clusters.
- Ligação média: Aqui, levaremos a média entre cada ponto em um cluster para todos os outros pontos no outro cluster.
Agora vamos discutir sobre os pontos fortes e fracos do AGNES; esse algoritmo tem uma complexidade de tempo de pelo menos O (n 2 ), portanto, não se sai bem no dimensionamento, e uma outra grande desvantagem é que tudo o que foi feito nunca pode ser desfeito, isto é, se agruparmos incorretamente qualquer cluster no estágio inicial do o algoritmo não será capaz de alterar o resultado / modificá-lo. Mas esse algoritmo também tem um lado positivo, uma vez que existem muitos clusters menores, ele pode ser útil no processo de descoberta e produz uma ordem de objetos que é muito útil na visualização.
Clustering Divisivo (DIANA)
Diana basicamente significa Análise Divisiva; esse é outro tipo de agrupamento hierárquico, no qual, basicamente, funciona com base no princípio da abordagem descendente (inversa do AGNES), onde o algoritmo começa formando um grande agrupamento e divide recursivamente o agrupamento mais diferente em dois e continua até que nós ' re todos os pontos de dados semelhantes pertencem aos seus respectivos clusters. Esses algoritmos de divisão resultam em hierarquias altamente precisas do que a abordagem aglomerativa, mas são computacionalmente caros.
A figura acima mostra o processo passo a passo do agrupamento divisivo
Clustering hierárquico multifásico
Para melhorar a qualidade dos clusters gerados pelas técnicas de cluster hierárquico mencionadas acima, integramos nossas técnicas de cluster hierárquico a outras técnicas de cluster; isso é chamado de cluster multifásico. Os diferentes tipos de clustering multifásico são os seguintes:
- BIRCH (Redução Iterativa Balanceada e Clustering Usando Hierarquias)
- ROCK (Clustering de RObust usando links)
- CAMALEÃO
1. Redução Iterativa Balanceada e Clustering Usando Hierarquias
Esse método é usado principalmente para agrupar grandes quantidades de dados numéricos, integrando nosso clustering hierárquico / micro na fase inicial e o clustering de macro / particionamento iterativo na fase posterior. Esse método ajuda a superar o problema de escalabilidade que enfrentamos no AGNES e a incapacidade de desfazer o que foi feito na etapa anterior. BIRCH usa dois conceitos importantes em seu algoritmo
uma. Recurso de cluster (Ajuda no resumo do cluster)
CF é definido como (n - número de pontos de dados no cluster, a soma linear de n pontos, a soma quadrada de n pontos). Armazenar o recurso de um cluster dessa maneira ajuda a evitar o armazenamento de informações detalhadas sobre ele e o CF é de natureza aditiva para diferentes clusters.
CF 1 + CF 2 =
b. Árvore de recursos de cluster (ajuda na representação de um cluster como uma hierarquia)
A árvore CF é uma árvore balanceada com fator de ramificação B (número máximo de filhos) e limite T (número máximo de subclusters que podem ser armazenados nos nós das folhas).
O algoritmo basicamente funciona em 2 fases; na fase 1, ele varre o banco de dados e constrói uma árvore CF na memória; na fase 2, usa o algoritmo de clustering que ajuda no clustering dos nós de folha, removendo os outliers (clusters esparsos) e agrupando o cluster com densidade máxima. A única desvantagem desse algoritmo é que ele lida apenas com o tipo de dados numéricos.
2. Cluster robusto usando links
Link é definido como o número de vizinhos comuns entre dois objetos. O algoritmo ROCK é um tipo de algoritmo de agrupamento que usa esse conceito de vínculo com o conjunto de dados categóricos. Como sabemos que os algoritmos de agrupamento medidos à distância não fornecem clusters de alta qualidade para o conjunto de dados categóricos, mas no caso do ROCK, ele também considera as vizinhanças dos pontos de dados, ou seja, se dois pontos de dados têm a mesma vizinhança, eles são provavelmente pertencer ao mesmo cluster. O algoritmo construirá um gráfico esparso na primeira etapa, levando em consideração a matriz de similaridade com o conceito de vizinhança e limiar de similaridade. Na segunda etapa, ele usa a técnica de agrupamento hierárquico aglomerativo no gráfico esparso.
3. Camaleão
Esse tipo de algoritmo de cluster hierárquico usa o conceito de modelagem dinâmica. Querendo saber por que é chamado dinâmico? É chamado de dinâmico porque tem a capacidade de se adaptar automaticamente às características internas do cluster, avaliando a similaridade do cluster, ou seja, quão bem conectado os pontos de dados em um cluster e na proximidade de clusters. Uma das desvantagens do camaleão é que o custo de processamento é muito alto (O (n 2 ) para n objetos é a pior complexidade de tempo).
Fonte da imagem - Google
Conclusão
Neste artigo, aprendemos o que é um cluster e o que é análise de cluster, diferentes tipos de técnicas de cluster hierárquicas, suas vantagens e desvantagens. Cada uma das técnicas discutidas tem seus próprios pontos positivos e negativos, portanto, antes de prosseguir com um algoritmo, precisamos entender nossos dados com uma análise exploratória apropriada e escolher o algoritmo com cautela.
Artigos recomendados
Este é um guia para a Análise Hierárquica de Clustering. Aqui discutimos a visão geral, clustering aglomerativo, clustering divisivo (DIANA) e cluster hierárquico multifásico. Você também pode consultar os seguintes artigos para saber mais
- Clustering hierárquico em R
- Algoritmo de cluster
- aglomerados
- Métodos de agrupamento
- Clustering no Machine Learning
- Clustering hierárquico | Clustering Aglomerativo e Divisivo