O que é clustering?

Há diversas maneiras de utilizar o clustering (agrupamento) no aprendizado de máquina, desde explorações iniciais de um conjunto de dados até o monitoramento de processos em andamento.

Você pode utilizá-lo na análise exploratória de dados com um novo conjunto de dados para entender tendências, padrões e valores discrepantes subjacentes. Ou então, você pode ter um conjunto de dados maior que precisa ser dividido em vários conjuntos de dados ou reduzido com redução de dimensionalidade. Nesses casos, o agrupamento pode ser uma etapa do pré-processamento.

Exemplos de clusters podem ser gêneros musicais, diversos grupos de usuários, segmentos-chave de uma segmentação de mercado, tipos de tráfego de rede em um cluster de servidor , grupos de amigos em uma rede social ou muitos outros tipos de categorias. O processo de agrupamento pode utilizar somente um recurso dos dados ou pode utilizar todos os recursos presentes nos dados.

É útil pensar em agrupamento como uma tentativa de encontrar agrupamentos naturais em dados para ver quais categorias podem existir e o que define essas categorias. Os clusters podem ajudar a encontrar relacionamentos subjacentes entre pontos de dados para ver quais recursos ou características são compartilhados entre as categorias.

Dependendo do algoritmo de agrupamento utilizado, você pode remover valores discrepantes dos seus dados ou rotulá-los como valores discrepantes. O agrupamento pode também ajudar na detecção de anomalias, detectando quais pontos de dados não estão contidos em um cluster ou estão apenas fracamente associados a um cluster e portanto podem ser uma anomalia no processo de geração de dados.

O armazenamento em cluster também pode ser utilizado para reduzir a complexidade de grandes conjuntos de dados, reduzindo o número de dimensões dos dados. Se você perceber que as categorias são definidas por apenas dois ou três recursos, poderá remover recursos estranhos ou usar técnicas de redução de dimensionalidade como o PCA. O agrupamento também é muito útil na criação de visualizações dos conjuntos de dados para ver as propriedades emergentes dos dados, bem como a densidade e as relações entre os agrupamentos.

Os algoritmos de clustering às vezes são diferenciados por hard clustering, em que cada ponto de dado pertence a somente um único cluster e tem um valor binário de estar ou não em um cluster, ou por fazer soft clustering, onde cada ponto de dado recebe uma probabilidade de pertencer a cada cluster identificado. Não há um processo de clusterização melhor: você deve escolher a abordagem que faz mais sentido para suas necessidades e para os dados com os quais estiver trabalhando.

Há muitos algoritmos de agrupamento diferentes, pois há várias maneiras de definir um cluster. Diversas abordagens funcionarão bem com diversos tipos de modelos, dependendo do tamanho dos dados de entrada, da dimensionalidade dos dados, da rigidez das categorias e do número de agrupamentos no conjunto de dados. Vale a pena notar que um algoritmo pode funcionar muito bem para um conjunto de dados e muito mal em outro.

Esta seção descreve cinco das abordagens comumente utilizadas com clustering. Há outras técnicas, como agrupamento espectral ou agrupamento Mean-Shift, que estão fora do escopo deste artigo.

O clustering baseado em centroide é um tipo de método de clustering 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 cluster é a média ou a mediana de todos os pontos no cluster, 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 clustering hierárquico, às vezes chamado de cluster 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 e Divisivo.

Aglomerativo

No clustering aglomerativo, uma abordagem ascendente começa com pontos de dados individuais e mescla sucessivamente os clusters calculando a matriz de proximidade de todos os clusters 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 clusters é 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 clusters 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 têm naturalmente o viés de 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 clustering hierárquico divisivo, uma abordagem descendente 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 agrupamento plano como o k-means. Os clusters com a maior soma dos erros quadráticos (SSE) são, então, divididos utilizando-se um método de agrupamento 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 agrupamento hierárquico divisivo pode ser mais rápido do que o agrupamento hierárquico aglomerativo, especialmente quando os dados não exigem a construção da árvore até os pontos de dados individuais.

O clustering 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 cluster, 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 cluster. Em seguida, repita a etapa de Expectativa até que a equação convirja nas distribuições observadas para cada cluster.

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 clustering 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.

Valor discrepante: um ponto de dados é um valor discrepante se não for um ponto central nem um ponto de borda. Essencialmente, essa é a classe “outro”.

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.

Há várias métricas de avaliação para análise de cluster e a seleção da métrica apropriada depende do tipo de algoritmo de agrupamento e do conjunto de dados correspondente. As métricas de avaliação geralmente podem ser divididas em duas categorias principais: Extrínseca e Intrínseca.

Medidas intrínsecas são métricas de avaliação para análise de cluster que utilizam somente as informações dentro do conjunto de dados. Podem ser úteis quando se está trabalhando com dados não rotulados. A qualidade da análise baseia-se inteiramente nas relações entre pontos de dados. Eles podem ser utilizados quando não temos conhecimento prévio ou rótulos dos dados. Medidas intrínsecas comuns são:

Pontuação de silhueta: essa métrica mede a semelhança e a diferença de cada ponto de dados em relação ao seu próprio cluster e a todos os outros clusters. Os valores das métricas variam de -1 a +1. Um valor alto indica que o objeto é bem compatível com seu próprio cluster e não é compatível com os clusters vizinhos.

Índice de Davies-Bouldin: Essa métrica calcula a razão entre a distância dentro do cluster e a distância entre clusters. Quanto menor for a pontuação do índice, melhor será o desempenho do agrupamento.

Índice de Calinski–Harabasz: também conhecido como Critério de Razão da Variância, mede a razão da variância entre os clusters e a variância dentro do cluster. Quanto maior a proporção Calinski-Harabasz, mais bem definido será um cluster.

Essas métricas de avaliação podem nos ajudar a comparar o desempenho de diversos algoritmos e modelos de agrupamento, otimizar parâmetros de agrupamento e validar a precisão e a qualidade dos resultados do agrupamento.

As medidas extrínsecas usam informações básicas ou externas para avaliar a validade do desempenho do algoritmo de agrupamento. Isso requer alguma forma de dados de rótulo que confirme a classe ou cluster ao qual cada ponto de dados pertence. Nesse caso, você pode comparar a precisão da sua análise de agrupamento com métricas frequentemente usadas na precisão da classificação. As medidas extrínsecas comuns são:

Pontuação F (também chamada de medida F): essa métrica determina a precisão do algoritmo de agrupamento analisando a precisão e o recall ao comparar um agrupamento proposto com uma verdade fundamental. No caso de uma pontuação F, quanto mais alta, melhor.

Pureza: esta métrica mede a fração de pontos de dados que são corretamente atribuídos à mesma classe ou cluster ao qual pertencem. No caso de uma medida de pureza, quanto maior, melhor.

Índice Rand: é uma medida da semelhança entre os rótulos verdadeiros e previstos do algoritmo de agrupamento, variando de 0 a 1. Um valor mais alto indica um melhor desempenho do agrupamento.

Variação de informações (também chamada de distância de informações compartilhadas): mede a quantidade de informações perdidas e ganhas entre dois agrupamentos. Isso pode ser feito entre um agrupamento de verdade e um agrupamento gerado por algoritmo ou entre dois agrupamentos diferentes. Um número menor é melhor, pois mostra uma distância menor entre dois resultados de agrupamentos.

Há muitas áreas de aplicação onde o agrupamento é uma ferramenta valiosa para mineração de dados ou análise exploratória de dados, podemos listar apenas uma pequena amostra das áreas de aplicação aqui para dar uma noção da importância desse tipo de análise.

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.