O que é clustering?

Há várias maneiras de usar o clustering no aprendizado de máquina, desde as explorações iniciais de um conjunto de dados até o monitoramento de processos em andamento. Você pode usá-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 usando a redução de dimensionalidade. Nesses casos, o clustering pode ser uma etapa do pré-processamento.

Exemplos de clusters podem incluir gêneros musicais, diferentes grupos de usuários, segmentos-chave de uma segmentação de mercado, tipos de tráfego de rede em um cluster de servidores, grupos de amigos em uma rede social ou muitos outros tipos de categories. O processo de clustering pode usar apenas uma funcionalidade dos dados ou pode usar todas as funcionalidades presentes nos dados.

É útil pensar no clustering 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 funcionalidades ou características são compartilhadas entre as categorias. Dependendo do algoritmo de clustering utilizado, você pode remover valores discrepantes dos seus dados ou rotulá-los como valores discrepantes. O clustering também pode ajudar na detecção de anomalias, ao detectar 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 clustering também pode ser utilizado para reduzir a complexidade de grandes conjuntos de dados, ao reduzir o número de dimensões dos dados. Se você perceber que as categorias são definidas por apenas dois ou três funcionalidades, poderá remover funcionalidades estranhas ou usar técnicas de redução de dimensionalidade como o PCA. O clustering 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 clusters.

Os algoritmos de clustering às vezes são diferenciados por realizar hard clustering, em que cada ponto de dados pertence a somente um único cluster e tem um valor binário de estar ou não em um cluster, ou por realizar soft clustering, onde cada ponto de dados recebe uma probabilidade de pertencer a cada cluster identificado. Não há um processo de clustering 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 clustering 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 clusters no conjunto de dados. Vale a pena notar que um algoritmo pode funcionar muito bem para um conjunto de dados e muito mal para outro. Esta seção descreve cinco das abordagens comumente utilizadas com clustering. Há outras técnicas, como clustering espectral ou clustering Mean-Shift, que estão fora do escopo deste artigo.

O clustering baseado em centroides é 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 clustering baseado em centroides mais comumente utilizadas é o algoritmo de clustering 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 centroide. Para inicializar o clustering, você fornece um número de clusters esperados, que representa o "k" em k-means, e o algoritmo tenta encontrar clusters razoáveis nos dados para corresponder a esse número. Os k clusters ideais em um determinado conjunto de dados são identificados ao minimizar iterativamente a distância total entre cada ponto e seu centroide de cluster atribuído.

O k-means é uma abordagem de clustering rígido, o que significa que cada ponto de dados é atribuído a um cluster separado e nenhuma probabilidade é associada à filiaçã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 valores discrepantes, pois tenta estabelecer centroides com base nos valores médios de todos os valores no cluster e, portanto, é suscetível a overfitting para incluir esses valores discrepantes.

Outra abordagem baseada em centroides para o k-means é o k-medoids. Medoides 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 centroide arbitrário como centro do gráfico, o algoritmo cria clusters utilizando pontos de dados individuais como medoide 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 clustering baseado em conectividade, agrupa pontos de dados com base na proximidade e conectividade de seus atributos. Esse método determina os clusters 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 clustering cria uma rede gráfica dos clusters 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 clusters hierárquicos podem ser representados graficamente com um dendrograma para ajudar a resumir e organizar visualmente os clusters descobertos e a hierarquia que eles podem conter.

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

Aglomerativo: no clustering aglomerativo, uma abordagem ascendente começa com pontos de dados individuais e mescla sucessivamente os clusters ao calcular 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 clustering. No clustering 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 naturalmente têm viés 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 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 clustering 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 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 clustering baseado em distribuições, também conhecido como clustering probabilístico, agrupa pontos de dados com base em sua distribuição de probabilidades. Essa abordagem pressupõe que há um processo gerando distribuições normais para cada dimensão dos dados que criam os centros de dos clusters. É diferente do clustering baseado em centroides 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 clustering são as médias da distribuição gaussiana em cada dimensão. O clustering baseado em distribuições é uma abordagem baseada em modelos 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 clustering baseado em distribuições é criação do modelo de mistura gaussiana (GMM) por meio da maximização de expectativas. Um GMM tem esse nome 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 maximização de expectativas começa com uma estimativa aleatória para essas duas distribuições ao longo de cada eixo e, então, prossegue para melhorar iterativamente ao alternar 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 cluster. Isso significa que o clustering via maximização de expectativas é uma abordagem de clustering suave e que um determinado ponto pode ser probabilisticamente associado a mais de um cluster. 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 densidades funciona por meio da detecção de áreas onde os pontos estão concentrados e onde estão separados por áreas vazias ou dispersas. Ao contrário de abordagens baseadas em centroides, como k-means, ou abordagens baseadas em distribuições, como maximização de expectativas, o clustering baseado em densidades pode detectar clusters 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ífico. Ao contrário de outros algoritmos de clustering, como k-means e clustering hierárquico, um algoritmo baseado em densidades pode descobrir clusters de qualquer forma, tamanho ou densidade em seus dados. O clustering baseado em densidades também pode distinguir entre pontos de dados que fazem parte de um cluster e aqueles que devem ser rotulados como ruído. O clustering baseado em densidades é 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 clusters nos dados.

O DBSCAN é um exemplo de algoritmo de clustering que adota uma abordagem baseada em densidades para o clustering. Ele usa uma abordagem de clustering espacial baseado em densidades para criar clusters 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 “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 baseado 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 clustering 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 clustering.

Um algoritmo popular de clustering 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 horizontal ou verticalmente, e o algoritmo não consegue detectar limites de clusters 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 clustering baseadas em grade e em densidades. Nesse algoritmo, o espaço de dados é dividido em uma grade, 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 clusters de formas arbitrárias em dados de alta dimensão.

Há várias métricas de avaliação para análise de clusters, e a seleção da métrica apropriada depende do tipo de algoritmo de clustering e do conjunto de dados correspondente. As métricas de avaliação geralmente podem ser divididas em duas categorias principais: extrínsecas e intrínsecas.

Medidas intrínsecas são métricas de avaliação para análise de clusters 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. Elas podem ser utilizadas quando não temos conhecimento prévio ou rótulos dos dados. Medidas intrínsecas comuns incluem:

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

Índice de Calinski–Harabasz: também conhecido como critério de razão de variância, mede a razão entre a variância entre os clusters e a variância dentro dos clusters. Quanto maior a razão de 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 clustering, otimizar parâmetros de clustering e validar a precisão e a qualidade dos resultados de clustering.

As medidas extrínsecas usam a verdade fundamental ou informações externas para avaliar a validade do desempenho do algoritmo de clustering. 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 de sua análise de clustering com métricas frequentemente usadas na precisão da classificação. As medidas extrínsecas comuns incluem:

Pontuação F (também chamada de medida F): essa métrica determina a precisão do algoritmo de clustering ao analisar a precisão e o recall ao comparar um clustering proposto com uma verdade fundamental. No caso de uma pontuação F, quanto maior, 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 clustering, variando de 0 a 1. Um valor mais alto indica um melhor desempenho de clustering.

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 clusterings. Isso pode ser feito entre um clustering de verdade fundamental e um clustering gerado por algoritmo ou entre dois clusterings diferentes. Um número menor é melhor, pois mostra uma distância menor entre dois resultados de clusterings.

Há muitas áreas de aplicação onde o clustering é 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 clustering pode ajudar a descobrir anomalias ao medir quais pontos de dados não estão incluídos na estrutura de clustering definida pela análise de clusters. Pontos de dados que pertencem a clusters pequenos ou muito dispersos ou que estão distantes do cluster atribuído podem ser considerados anomalias. Métodos baseados em densidade, como a maximização de expectativas, são utilizados para identificar pontos de dados em regiões densas como normais e aqueles em regiões de baixa densidade como anomalias.

Ao tentar 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 em clusters 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 clustering processam os pixels na imagem e definem áreas dentro da imagem que representam o cluster.

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