O agrupamento baseado em centroide é um tipo de método de agrupamento que particiona ou divide um conjunto de dados em grupos semelhantes com base na distância entre seus centroides. O centroide ou centro de cada agrupamento é a média ou a mediana de todos os pontos no agrupamento, dependendo dos dados.

Uma das técnicas de agrupamento baseadas em centroides mais comumente utilizadas é o algoritmo de agrupamento k-means. O K-means assume que o centro de cada cluster define o cluster utilizando uma medida de distância, geralmente a distância euclidiana, até o centróide. Para inicializar o agrupamento, você apresenta um número de agrupamentos esperados, que representa o 'K' em K-means, e o algoritmo tenta encontrar agrupamentos razoáveis nos dados para corresponder a esse número. Os k clusters ideais em um determinado conjunto de dados são identificados minimizando iterativamente a distância total entre cada ponto e seu centroide de cluster atribuído.

K-means é uma abordagem de agrupamento rígido, o que significa que cada ponto de dados é atribuído a um cluster separado e nenhuma probabilidade é associada à associação ao cluster. O K-means funciona bem quando os clusters têm tamanho aproximadamente equivalente e não há valores discrepantes ou alterações significativas na densidade dos dados. O K-means geralmente tem desempenho ruim quando os dados são de alta dimensão ou quando os clusters têm tamanhos ou densidades consideravelmente diferentes. O K-means também é especialmente sensível a outliers, pois tenta estabelecer centróides com base nos valores médios de todos os valores no cluster e, portanto, é suscetível a overfitting para incluir esses outliers.

Outra abordagem baseada em centroides para K-means é o K-medoids. Medóides são objetos representativos de um conjunto de dados ou um cluster dentro de um conjunto de dados cuja soma das distâncias para outros objetos no cluster é mínima. Em vez de ter um centróide arbitrário como centro do gráfico, o algoritmo cria clusters utilizando pontos de dados individuais como medoid ou centro do cluster. Como o algoritmo K-medoids usa pontos de dados existentes em vez de centroides arbitrários, ele é menos sensível a valores discrepantes.

O agrupamento hierárquico, às vezes chamado de agrupamento baseado em conectividade, agrupa pontos de dados com base na proximidade e conectividade de seus atributos. Esse método determina os agrupamentos com base na proximidade entre os pontos de dados em todas as dimensões. A ideia é que objetos mais próximos estão mais intimamente relacionados do que aqueles que estão longe uns dos outros. Ao contrário do k-means, não há necessidade de pré-especificar o número de clusters. Em vez disso, o algoritmo de agrupamento cria uma rede gráfica dos agrupamentos em cada nível hierárquico. Essa rede é hierárquica, o que significa que qualquer nó fornecido nela tem apenas um nó pai, mas pode ter vários nós filhos. Os agrupamentos hierárquicos podem ser representados graficamente com um dendrograma para ajudar a resumir e organizar visualmente os agrupamentos descobertos e a hierarquia que eles podem conter.

Há duas abordagens para realizar a análise hierárquica de clusters:

Aglomerativo: no agrupamento aglomerativo, uma abordagem ascendente começa com pontos de dados individuais e mescla sucessivamente os agrupamentos calculando a matriz de proximidade de todos os agrupamentos no nível atual da hierarquia para criar uma estrutura semelhante a uma árvore. Uma vez que um nível de clusters tenha sido criado, onde todos os clusters têm nenhuma ou baixa similaridade entre clusters, o algoritmo se move para o conjunto de clusters recém-criados e repete o processo até que haja um nó raiz no topo do gráfico hierárquico. Há uma variedade de opções possíveis em termos de como esses clusters devem ser mesclados uns com os outros, com compensações em termos de qualidade e eficiência do agrupamento. No agrupamento de ligação única, a menor distância entre qualquer par de pontos de dados em dois agrupamentos é utilizada como uma medida de similaridade. Na ligação de todos os pares é utilizada a média em todos os pares de pontos de dados, enquanto na ligação por amostragem, é utilizada uma amostragem dos pontos de dados nos dois agrupamentos para calcular a distância média. Na ligação do centroide é utilizada a distância entre os centroides. Um desafio com os métodos aglomerativos é que eles podem exibir encadeamento, onde clusters maiores são naturalmente tendenciosos a ter distâncias mais próximas de outros pontos e portanto continuam a ficar cada vez maiores e a atrair mais pontos de dados para seu cluster. Outra desvantagem é que os métodos aglomerativos podem ser muito mais lentos do que os métodos divisivos de construção da hierarquia.

Divisivo: nos métodos de agrupamento hierárquico divisivo, uma abordagem de cima para baixo particiona sucessivamente os pontos de dados em uma estrutura semelhante a uma árvore. A primeira etapa é dividir o conjunto de dados em clusters utilizando um método de clustering plano como o K-Means. Os clusters com a maior Soma de Erros Quadrados (SSE) são então divididos utilizando-se um método de clustering plano. O algoritmo é interrompido quando atinge nós individuais ou algum SSE mínimo. O particionamento divisivo permite maior flexibilidade em termos da estrutura hierárquica da árvore e do nível de equilíbrio nos diferentes clusters. Não é necessário ter uma árvore perfeitamente equilibrada em termos das profundidades dos diferentes nós ou uma árvore em que o grau de cada ramo seja exatamente dois. Isso permite a construção de uma estrutura de árvore que possibilita diversas compensações no equilíbrio das profundidades dos nós e dos pesos dos nós (número de pontos de dados no nó). O clustering hierárquico divisivo pode ser mais rápido do que o clustering hierárquico aglomerativo, especialmente quando os dados não exigem a construção da árvore até os pontos de dados individuais.

O agrupamento baseado em distribuição, também conhecido como agrupamento probabilístico, agrupa pontos de dados com base em sua distribuição de probabilidade. Essa abordagem pressupõe que há um processo gerando distribuições normais para cada dimensão dos dados que criam os centros de agrupamento. É diferente do clustering baseado em centróides porque não utiliza uma métrica de distância como a distância Euclidiana ou de Manhattan. Em vez disso, as abordagens baseadas em distribuição procuram uma distribuição bem definida que apareça em cada dimensão. As médias do agrupamento são as médias da distribuição gaussiana em cada dimensão. O clustering baseado em distribuição é uma abordagem baseada em modelo para o clustering, pois exige o ajuste de uma distribuição várias vezes em cada dimensão para encontrar clusters, o que significa que pode ser computacionalmente caro no trabalho com grandes conjuntos de dados.

Uma abordagem comumente utilizada para agrupamento baseado em distribuição é criação do Modelo de Mistura Gaussiana (GMM) por meio da Expectativa-Maximização. Um GMM é nomeado devido à suposição de que cada cluster é definido por uma distribuição gaussiana, geralmente chamada de distribuição normal.

Considere um conjunto de dados com dois clusters distintos, A e B, ambos definidos por duas distribuições normais diferentes: uma ao longo do eixo x e outra ao longo do eixo y. A Expectativa-Maximização começa com uma estimativa aleatória para essas duas distribuições ao longo de cada eixo e então prossegue para melhorar iterativamente alternando duas etapas:

Expectativa: atribua cada ponto de dados a cada um dos clusters e calcule a probabilidade de que ele tenha vindo do Cluster A e do Cluster B.

Maximização: atualize os parâmetros que definem cada agrupamento, uma localização média ponderada e uma matriz de variância-covariância, com base na probabilidade de cada ponto de dados estar no agrupamento. Em seguida, repita a etapa de Expectativa até que a equação convirja nas distribuições observadas para cada agrupamento.

Cada ponto de dados recebe uma probabilidade de ser associado a um agrupamento. Isso significa que o agrupamento via Maximização de Expectativas é uma abordagem de agrupamento suave e que um determinado ponto pode ser probabilisticamente associado a mais de um agrupamento. Isso faz sentido em alguns cenários, uma música pode ser um pouco folk e um pouco rock ou um usuário pode preferir programas de televisão em espanhol, mas às vezes também assistir a programas em inglês.

O agrupamento baseado em densidade funciona por meio da detecção de áreas onde os pontos estão concentrados e onde estão separados por áreas vazias ou esparsas. Ao contrário de abordagens baseadas em centroides, como K-means, ou abordagens baseadas em distribuição, como Maximização de Expectativas, o agrupamento baseado em densidade pode detectar agrupamentos de uma forma arbitrária. Isso pode ser extremamente útil quando os clusters não são definidos em torno de um local ou distribuição específica. Ao contrário de outros algoritmos de agrupamento, como K-means e agrupamento hierárquico, um algoritmo baseado em densidade pode descobrir agrupamentos de qualquer forma, tamanho ou densidade em seus dados. O agrupamento baseado em densidade também pode distinguir entre pontos de dados que fazem parte de um agrupamento e aqueles que devem ser rotulados como ruído. O agrupamento baseado em densidade é especialmente útil no trabalho com conjuntos de dados com ruído ou valores discrepantes ou quando não temos conhecimento prévio sobre o número de agrupamentos nos dados.

O DBSCAN é um exemplo de algoritmo de agrupamento que adota uma abordagem baseada em densidade para o agrupamento. Ele usa uma abordagem de agrupamento espacial baseada em densidade para criar agrupamentos com uma densidade passada pelo usuário que gira em torno de um centroide espacial. A área imediatamente ao redor do centroide é chamada de vizinhança e o DBSCAN tenta definir vizinhanças de clusters que tenham a densidade especificada. Para cada cluster, o DBSCAN definirá três tipos de pontos de dados:

Pontos centrais: um ponto de dados é um ponto central se a vizinhança em torno desse ponto de dados contiver pelo menos tantos pontos quanto o número mínimo de pontos especificado pelo usuário.

Pontos de borda: um ponto de dados é um ponto de borda se a vizinhança em torno desse ponto de dados contiver menos do que o número mínimo de pontos de dados, mas a vizinhança em torno desse ponto contiver um ponto central.

Outlier: Um ponto de dados é um outlier se não for um ponto central nem um ponto de fronteira. Essencialmente, esta é a classe “outra”.

O HDBSCAN é uma variante do DBSCAN que não exige a definição de nenhum parâmetro; isso pode torná-lo ainda mais flexível do que o original. O HDBSCAN é menos sensível a ruídos e valores discrepantes nos dados. Além disso, o DBSCAN às vezes pode ter problemas para identificar clusters com densidade não uniforme. Essa foi a principal motivação para o HDBSCAN e portanto lida com clusters de densidade variável de forma muito mais eficaz.

Os algoritmos de clustering baseados em grade não são utilizados com tanta frequência quanto as quatro abordagens anteriores, mas podem ser úteis em clustering de alta dimensão onde outros algoritmos de clustering podem não ter o mesmo desempenho. Nessa abordagem, o algoritmo particiona um conjunto de dados de alta dimensão em células. Cada célula recebe um identificador exclusivo chamado ID de célula, e todos os pontos de dados que se enquadram em uma célula são considerados parte do mesmo cluster.

O agrupamento baseado em grade é um algoritmo eficiente para analisar grandes conjuntos de dados multidimensionais, pois reduz o tempo necessário para procurar vizinhos mais próximos, que é uma etapa comum em muitos métodos de agrupamento.

Um algoritmo popular de agrupamento baseado em grade chama-se STING, que significa STatistical INformation Grid. No STING, a área espacial é dividida em células retangulares e vários níveis de células em diferentes níveis de resolução. As células de alto nível são divididas em várias células de baixo nível. O STING pode ser muito eficiente na computação de clusters em cenários de big data em que os conjuntos de dados são extremamente grandes, pois simplesmente particiona o conjunto de dados iterativamente em grades mais refinadas e avalia o número de pontos dentro dessa grade. Uma desvantagem do STING é que os limites dos clusters precisam ser definidos horizontalmente ou verticalmente, o algoritmo não consegue detectar limites de cluster não retangulares.

Outro algoritmo baseado em grade que é particularmente eficiente com dados de alta dimensão é o algoritmo Clustering In Quest ou CLIQUE. O CLIQUE combina abordagens de agrupamento baseadas em grade e em densidade. Nesse algoritmo, o espaço de dados é dividido em uma grade e a densidade relativa dos pontos dentro das células da grade é comparada e os subespaços que têm densidades semelhantes são mesclados. Essa abordagem encontra unidades densas em todos os subespaços de interesse e, em seguida, mede se clusters semelhantes devem ser conectados entre si. Isso significa que o CLIQUE pode detectar grupos de formas arbitrárias em dados de alta dimensão.

O agrupamento pode ajudar a descobrir anomalias ao medir quais pontos de dados não estão incluídos na estrutura de agrupamento definida pela análise de agrupamento. Pontos de dados que pertencem a clusters pequenos ou muito esparsos ou que estão distantes do cluster atribuído podem ser considerados anomalias. Métodos baseados em densidade, como a Maximização de Expectativa, são utilizados para identificar pontos de dados em regiões densas como normais e aqueles em regiões de baixa densidade como anomalias.

Tentando entender quais personas de clientes ou subconjuntos de mercados podem existir, o clustering pode ser uma ferramenta poderosa para ajudar a realizar a segmentação de clientes. Você pode combinar dados demográficos com dados de comportamento do cliente para descobrir quais tipos de características e padrões de compra se correlacionam com mais frequência.

As imagens podem ter seus pixels agrupados de várias maneiras que podem ajudar a cortar a imagem em diferentes seções para dividir um primeiro plano de um plano de fundo, detectar objetos utilizando semelhanças de cor e brilho ou dividir imagens em regiões de interesse para processamento adicional. Com imagens, os métodos de agrupamento processam os pixels na imagem e definem áreas dentro da imagem que representam o agrupamento.

A análise de clustering pode ser útil no processamento de documentos de várias maneiras. Os documentos podem ser agrupados por semelhança para mostrar quais documentos são mais semelhantes entre si. Isso pode ser baseado no tamanho do documento, distribuição de frequência de palavras ou outras várias maneiras de quantificar as principais características do documento. Outro caso de uso comum é analisar grupos de seções de um documento com base na frequência de palavras-chave, comprimento da frase ou distribuições de termos. Isso pode ajudar a fazer o resumo de documentos ou a dividir documentos maiores em conjuntos de dados menores para análise posterior.