Clustering — Conceitos básicos, principais algoritmos e aplicações

Escrito por Felipe Azank e Gustavo Corrêa

Fonte: scikit learn

Olá, sejam bem vindos a mais um Turing Talks, hoje falaremos sobre uma das atividades mais realizadas na Área de Ciência de Dados: os processos de Clustering ou Agrupamento.

Esse texto tem como objetivo explicar as principais técnicas de Clustering, assim como o funcionamento geral de um algoritmo de aprendizagem não-supervisionada. Para isso, seguiremos a seguinte estrutura:

1. Definição
2. Tipos de algoritmos de Clustering
3. Principais Algoritmos de Clustering (com exemplos)
4. Conclusão

Definição

Clustering, ou agrupamento, consiste na implementação de técnicas computacionais para separar um conjunto de dados em diferentes grupos com base em suas semelhanças. Diferentemente de algoritmos de classificação e regressão, o Agrupamento faz parte do universo da Aprendizagem Não Supervisionada, na qual os algoritmos devem entender as relações entre dados sem estarem rotulados a nenhuma categoria prévia.

Processo de clustering ilustrado (fonte: eCloud Valley)

Exemplos

No universo de Data Science, as técnicas de agrupamento costumam ser utilizadas para múltiplas funcionalidades, entre as principais temos:

• Em problemas de análise de dados, nos quais os processos de clustering ajudam na extração de padrões da base estudada. Esse processo costuma ser muito comum na segmentação de clientes de uma empresa, na qual o agrupamento permite que sejam entendidos os principais perfis dos usuários, permitindo a otimização de estratégias de aquisição e retenção destes. Esse processo se chama “Customer Segmentation” e será nosso exemplo de aplicação mais a frente.
• Na identificação de outliers, na qual dividir os dados em diferentes grupos permite que seja possível identificar com mais facilidade dados que não apresentam semelhança com nenhum outro, ou que não evidenciam nenhum ganho de informação. Um exemplo dessa técnica seria a identificação de valores muito diferentes de altura e largura de um animal em um dataset de raças de cachorro, caso a observação de um único indivíduo não fique próximo de nenhum agrupamento (raças de cachorro), esse dado pode ser identificado como “anômalo”

Exemplo de caso de um “outlier” no que tange raças de cachorro

• Em Feature Engineering, na qual novos dados não classificados (sem rótulo) podem ganhar um rótulo com base em qual agrupamento estabelecido pelo método de clustering o dado se encontra mais próximo. Como aplicação, por exemplo, vemos a tentativa de adicionar um novo dado de altura e peso de uma pessoa em uma pesquisa, mas sem ter a informação do sexo, neste caso, podemos utilizar um agrupamento dos dados totais e tentar inserir no grupo mais próximo.
• Em casos de criação de filtros automáticos, nos quais as técnicas de Clustering podem ser usadas de maneira a separar dados. Um exemplo são os filtros de spam não-supervisionado, no quais se pode agrupar os dados em dois grupos de maneira a separar aqueles com mensagens semelhantemente suspeitas, por exemplo, agrupando mensagens que contêm palavras como “ganhou”, “parabéns”, “sorteio”, “venceu” e “três numerinhos de trás”.

Tipos de algoritmos de Clustering

Agora que já temos uma ideia geral do significa de Clustering e onde esses processos podem ser aplicados, vamos aos diferentes tipos de algoritmos de agrupamentos de dados.

Existem diversos tipos de algoritmos de Clustering, a grande diferença entre eles está em como sua complexidade aumenta com o crescimento do dataset. Dessa forma, entender os diferentes tipos de algoritmos mostra-se interessante para escolher aqueles que agregam os melhores resultados para os seus dados. Esses tipos podem ser agrupados em em 4 grupos: Clusterização Baseada em Centróides, Clusterização baseada em Densidades, Clusterização, Clutserização baseada em Distribuições e Clusterização Hierárquica.

Clusterização Baseada em Centróides (centroid-based clustering)

As técnicas de agrupamento baseadas em centróide apresentam a missão de, partindo de uma quantidade determinada de grupos, encontrar quais são os centróides (centros geométricos) os quais representam o “meio” de cada cluster e, a partir deles, identificar qual cluster cada um dos pontos pertence com base nas suas distâncias para cada um dos centróides.

Exemplo de algoritmo baseado em centróide (fonte: THEAN C. LIM)

Uma vez que a identificação dos centróides é finalizada, a classificação de todos os pontos nos clusters torna-se muito simples, uma vez que é baseada apenas no cálculo da distância dos pontos em relação aos centróides, portanto, algoritmos desse tipo costumam ser eficientes. Contudo, como desvantagem, acabam por ser mais sensíveis a condições iniciais (uma vez que, para se encontrar os centróides, partem-se de um conjunto de pontos aleatórios, que são ajustados a cada iteração, até se encontrar um conjunto final) e funcionam melhor quando os dados estão bem separados entre si. Ademais, graças à formulação dos algoritmos, esse tipo de clusterização não costuma lidar adequadamente com outliers, os inserindo no cluster de centróide mais próximo.

Mais a frente, veremos representantes desse tipo de algoritmo (K-Means e Mini Batch K-Means), cujos procedimentos serão explicados mais detalhadamente.

Clusterização Baseada em Densidade (density-based clustering)

Algoritmos de clustering baseados em densidade têm como objetivo identificar regiões de alta concentração de pontos e os conectar em agrupamentos, identificando, dessa forma, os clusters.

Esse tipo de método permite que seja possível a identificação de clusters com geometrias arbitrárias e também permite que seja possível identificar outliers. Contudo, esse tipo de abordagem não costuma se sair bem com dados que apresentam agrupamentos com densidades distintas entre si.

fonte: https://www.usm.uni-muenchen.de/people/burkert/clusters/

O representante mais conhecido desse tipo de clusterização é o DBScan, que terá seu funcionamento e aplicação explicados mais a frente.

Clusterização Baseada em Distribuições (distribution-based clustering)

Algoritmos desse tipo tentam assumir diferentes distribuições a partir dos dados e definir cada distribuição encontrada como um agrupamento diferente. Em outras palavras, os algoritmos tentam ajustar diferentes distribuições aos dados, de maneira a relacionar cada distribuição com um cluster.

Com base nisso, a classificação de cada ponto nos grupos pode ser feita de modo probabilístico, no qual, dada as distribuições de cada grupo, pode-se estimar a probabilidade do ponto pertencer a essa distribuição.

Fonte: Google Developers

Esse tipo de algoritmo encontra diversos problemas, uma vez que a criação de cada uma das distribuições que descrevem os grupos pode sofrer com overfitting caso não exista condições que limitem o ajuste de parâmetros.

Ademais, é possível também notar que esses algoritmos não apresentam grande utilidade quando não se sabe qual o tipo de distribuição dos dados ou quando, por algum motivo, os clusters de dados pertencerem a diferentes tipos de distribuições (Gaussiana, Poisson, Pearson e etc).

Um exemplo de utilização desse tipo está no algoritmo Gaussian Mixture, que tenta adequar diferentes modelos gaussianos aos dados.

OBS: Muitas vezes, quando queremos exemplificar ou testar algoritmos de clustering, geramos dados aleatórios a partir de distribuições, usando comandos como “make_classification” do sklearn. Se olharmos com atenção, esse processo de selecionar aleatoriamente dados de diferentes distribuições para gerar um dataset acaba por ser o processo reverso do que esse algoritmo baseado em distribuições realiza, o que gera, em muitos casos, uma performance excelente desse quando usamos esses dados gerados aleatoriamente, criando assim, uma sensação de engano sobre a performance dos algoritmos em dados reais.

Clusterização Hierárquica (hierarchical clustering)

Algoritmos desse tipo têm como objetivo agrupar dados similares entre si usando ferramentas como a distância entre eles. A diferença desse tipo de algoritmo para os demais está na criação de diversos clusters (alguns agrupamentos dentro de outros), o que, por fim, acaba gerando uma árvore de clusters, na qual um dado pertence a grupos menores e maiores, criando, dessa forma, uma hierarquia.

Fonte: David Sheehan

Tendo essa hierarquia de clusters, podemos, então, controlar o quanto queremos que os dados sejam semelhantes entre si a ponto de pertencerem a um mesmo grupo, o que fará com que o algoritmo “suba” ou “desça” na hierarquia dos agrupamentos. Ademais, podemos, inversamente, informar quantos clusters desejamos ter, levando a uma configuração da hierarquia que fornecerá esse número.

Contudo, esses algoritmos apresentam duas desvantagens principais:

• Não lidam muito bem com outliers, tendo em vista que, graças a lógica do algoritmo, tendem a classificar o dado distante como um novo cluster, ou, em piores casos, acabam deformando outro cluster para incluí-lo.
• Não costumam ser utilizados em larga escala e em quantidades grandes de dados devido a sua complexidade e ineficiência com muitos dados. Por isso, estuda-se esses métodos uma vez que servem de base para soluções mais sofisticadas (como o density-based).

Os principais exemplos desse tipo são o Agglomerative Clustering e o BIRCH, ambos explicados mais ao fim.

Principais Algoritmos de Clustering

Após entendermos como os métodos de Clusterização podem ser divididos, assim como suas vantagens e desvantagens em geral, vamos analisar mais em detalhes os principais algoritmos utilizados nessas tarefas. Como este Turing Talks consiste em um texto introdutório ao universo de clustering, todos estes métodos também estão bem documentados e apresentam uma aplicação simples através de bibliotecas como o scikit learn.

Os algoritmos que conheceremos agora serão:

1. K-Means
2. Mini Batch K-Means
3. BDScan
4. Affinity Propagation
5. BIRCH
6. Agglomerative Clustering

K-Means

Um dos algoritmos mais conhecido assim como bem antigo (proposto em 1967), esse algoritmo baseado em centróides, tem como objetivo, encontrar os agrupamentos nos dados nos quais a variância dentro de cada cluster seja mínima.

fonte: notebook

Parâmetros principais de entrada:

• n_clusters: número de clusters que queremos obter/acreditamos que existe

Funcionamento

O funcionamento do algoritmo tem como base inserir K centróides aleatórios (sendo K o número de clusters) e, a partir desses pontos, ajustá-los com base nos dados, a fim de encontrar o centro dos clusters. De maneira mais detalhada, o algoritmo realiza as seguintes etapas:

• O algoritmo escolhe k pontos aleatórios dentre os dados, sendo k o número de clusters que foram definidos como parâmetro e serão esses os centros dos clusters “provisórios” (antes de iniciarmos o ajuste).
• Após isso, é computada a distância de cada ponto ao centróide (ponto aleatório definido anteriormente) mais próximo. Dessa forma, criamos a divisão dos dados entre os clusters, sendo cada cluster o conjunto de dados mais próximos aos centróides.
• Com esses grupos definidos, os novos valores dos centróides (pontos centrais dos clusters) serão as médias dos dados de cada cluster.
• Com os novos valores dos centróides, realizamos as mesmas etapas novamente: identificamos os pontos mais próximos aos centróides e criamos novos clusters, e a partir desses clusters, calculamos o valor médio para gerar novos valores para os centróides. Com isso, faz-se uma lógica Centróides → Clusters → Média dos clusters → Novos centróides → Novos Clusters.
• Realiza-se esse processo de achar centróides e clusters até a posição dos centróides não mudar mais.

O funcionamento ilustrado permite entender facilmente cada uma das etapas: http://shabal.in/visuals/kmeans/2.html

Resumo do algoritmo

Vantagens

• Algoritmo bem simples e que pode ser aplicado com um grande número de dados.
• Sua lógica de implementação apresenta uma convergência garantida.
• Consegue resolver problemas simples de forma consistente, tendo uso em diversos setores, como segmentação de mercado, astronomia e visão computacional. Pode ser usado como algoritmo de pré-tratamento de dados. Um exemplo seria a de utilizar KMeans para identificar a distância média entre os pontos de um mesmo cluster e utilizar essas informações como parâmetros para o DBScan (que será visto mais a frente).
• Sua simplicidade e eficiência geralmente fazem desse algoritmo um dos primeiros a serem usados como “teste” em problemas de clustering

Desvantagens

• Uma vez que o algoritmo se baseia em centróides, o k-means não consegue, de maneira efetiva, identificar clusters não convexos, tendo em vista que se baseia na distância euclidiana dos fatores. Isso pode ser mostrado facilmente com o exemplo abaixo, do próprio scikit learn.

Exemplo do scikit learn (K-means a esquerda e DBScan a direita), evidenciando a dificuldade do K-means em identidicar formas não convexas.

• A escolha inapropriada do número k de clusters faz com que se gere resultados muito abaixo do esperado, por isso, no uso do algoritmo, é ideal ter-se uma ideia geral do número de agrupamentos nos dados (existem métodos para encontrar o número de clusters, como o Elbow Method, contudo, para não estender esse Turing Talks, abordaremos eles em um próximo texto).
• O algoritmo não lida bem com outliers e esses, por sua vez, podem prejudicar fortemente o algoritmo, uma vez que eles deverão ser incluídos em algum grupo, o que, com o cálculo da média, irá deslocar a posição do centróide na direção do outlier, gerando um resultado pior do que poderia ser realizado caso o outlier não existisse.

Aplicação

Para a aplicação do K-means e de todos os outros algoritmos desse Turing Talks, foi-se utilizado o Mall Customer Segmentation Data, uma base de dados didática e simplificada de usuários de um shopping. A base contém 4 colunas: “Gênero”,”Idade”, “Renda Anual (em milhares de dólares)” e “Spending Score” (uma classificação de 0 a 100 dada pelo shopping com base no comportamento de gasto do cliente).

Como esse texto se trata de um texto introdutório e mais focado nos algoritmos e conceitos, vamos relevar alguns processos realizados nos dados e aplicar os algoritmos de Clustering considerando apenas duas features: Renda Anual e Pontuação de Gastos, que podem ser vistos no gráfico a seguir.

Dados a serem clusterizados (relação Renda X Pontuação de Gastos)

Por fins de simplicidade, vamos definir o número de clusters para 5, uma vez que visualmente esse parece ser o caso (existem formas matemáticas para a definição disso, que abordarem em próximos textos).

Para implementar o algoritmo de K-Means, basta utilizarmos a biblioteca sklearn.clusters, que contém diversas implementações dos algoritmos de Clustering mais populares na área de Ciência de Dados. Adiciona-se que, para que seja possível obter resultados mais consistentes, é necessário a normalização das features.

O código gera o seguinte gráfico:

Resultados da clusterização K-means

Como pode ser visto, o algoritmo identificou 5 clusters bem definidos, sem apresentar dificuldade com os dados esparsos. Contudo, podemos perceber também que alguns dados bem distantes foram inseridos em agrupamentos, uma vez que esse algoritmo não identifica outliers.

Mini Batch K-Means

Esse algoritmo entra como uma alteração do K-means, com o objetivo principal de otimizar o processo de clusterização e utilizar menos memória em comparação com a abordagem clássica.

Parâmetros principais de entrada:

• n_clusters: número de clusters que queremos obter/acreditamos que existe, assim como o K-means
• batch_size: tamanho dos mini-batches (quantidade de dados que serão carregados na memória para que sejam computados os novos centróides).

Funcionamento

• Esse algoritmo, diferentemente do clássico, usa apenas uma quantidade menor e aleatória dos dados durante a computação dos novos valores do centróide, de modo a atualizar os valores mais rapidamente
• Para que seja possível que o algoritmo chegue a uma convergência (valor dos centróides não mude), aplica-se uma taxa de aprendizado (learning rate), a qual decresce com o número de iterações, de forma que, com o passar do processo, o algoritmo tenha convergência.

Vantagens e desvantagens

Por assemelhar-se muito com o K-Means, esse algoritmo apresenta as mesmas vantagens e desvantagens em comparação com os demais, entretanto, é válido ressaltar alguns contrastes:

• O resultado do Mini-Batch não é exatamente o mesmo do que o clássico, uma vez, que o algoritmo modificado não considera todos os dados disponíveis. Contudo, isso reduz o tempo de computação, alocação de memória e processamento conforme o tamanho do dataset e o número de clusters aumenta, tornando dessa forma, o Mini-Batch preferível quando tratamos de muitos dados e clusters.
• É possível afirmar que, uma vez que o algoritmo modificado não utiliza sempre a quantidade total de dados nas iterações, eventualmente o algoritmo não contabilizará os outliers, podendo melhorar a formação dos clusters quando comparados com o K-means clássico.

Aplicação

Utilizando o scikit learn, a aplicação pode ser vista abaixo:

gerando o gráfico:

Resultados da clusterização Mini Batch K-means

Como já esperado, é possível notar que o resultado se assemelha muito com o K-means, contudo, um fato curioso a se notar está na ordem nos quais os “labels” do gráfico estão dispostos, o que demonstra que a ordem com que se foi elaborado os clusters e direcionado os dados é diferente do algoritmo anterior.

DBScan

fonte: Digital Vidya

Partindo agora para os algoritmos baseados em densidade, o DBScan (Density-Based Spatial Clustering of Applications with Noise) visa encontrar áreas de alta densidade no domínio e expandir essas áreas de forma a encontrar os clusters. Esse algoritmo é mais recente do que o K-Means, tendo sua primeira publicação em 1996.

Ao contrários dos métodos ja vistos, este por sua vez não exige que seja inserido, a priori, o número de clusters, uma vez que elabora os grupos com base no número de vizinhos a um ponto e no raio da vizinhança.

Parâmetros principais de entrada:

• min Pts: número mínimo de pontos que devem estar ao redor de um ponto central (core) em uma distância ε
• ε: raio de vizinhança de um determinado ponto
• Função distância: como será computada a distância entre os pontos (por padrão, usa-se a distância euclidiana).

Funcionamento

Em linhas gerais, o algoritmo busca criar uma “rede” de pontos vizinhos, de maneira a entender quais pontos estão “juntos” entre si e, portanto, fazem parte do mesmo cluster. O funcionamento mais detalhado pode ser entendido pelas seguintes etapas:

• O algoritmo identifica os vizinhos de cada ponto no dataset (vendo quais pontos estão a uma distância menor do que ε) e, com isso, detecta quais são os Pontos Centrais (Core), pontos os quais, para um raio ε apresentam uma quantidade de vizinhos maior ou igual a minPts (incluindo o próprio ponto).
• Após obter os pontos core, o algoritmo identitica se os pontos não-core são vizinhos de algum outro ponto core; em caso afirmativo, esses serão os pontos de “fronteira” do cluster, que será formado por todos os pontos core vizinhos entre si e demais pontos de fronteira.
• No caso em que pontos não-core não sejam vizinhos de nenhum outro Ponto Central, eles serão rotulados como “outlier” ou “ruído”

Um exemplo ilustrado pode ser visto abaixo. Nele, temos minPts = 4, ou seja, vemos que os pontos em A, para seus raios de vizinhança, contêm 4 pontos ou mais em seus arredores, desta forma, todos os pontos em vermelho são identificados como Pontos Centrais (Core). Os pontos em B e C, por sua vez, não apresentam uma quantidade maior ou igual a minPts em seus arredores, contudo, são vizinhos de Pontos Core, o que faz com que eles sejam identificados como pontos de fronteira do cluster (amarelo). Por fim, o ponto N não apresenta nenhum vizinho para seu arredor de raio ε, o que faz com que seja identificado como um Outlier (azul).

Fonte: Wikipedia

Vantagens

• Não necessita especificar o número de clusters anteriormente, uma vez que se baseia na vizinhança.
• Consegue identificar clusters de formas arbitrárias e não convexas, como visto na imagem exemplo do scikit learn, mostrada anteriormente.
• O DBSCan apresenta uma eficiência algoritmica ideal para grandes datasets, o posicionamando na frente de muitos no que tange performance, com uma complexidade média de execução de O(n log n). Em um possível próximo Turing Talks, veremos mais em detalhe a complexidade algoritmica de cada um dos principais algoritmos de clustering.
• Noção clara de ruído e identificação de outliers, podendo até, em muitos casos, ser utilizado para essa própria finalidade.

Desvantagens

• O DBSCAN pode apresentar resultados diferentes para pontos que se encontram no limite entre um cluster e outro, podendo ter seus grupos trocados dependendo da ordem em que os dados são processados.
• Uma vez que utiliza como padrão a distância euclidiana entre pontos, o algoritmo pode ter sua efetividade extremamente reduzida com o aumento do número de features devido a Maldição da Dimensionalidade.
• O algoritmo não consegue apresentar um resultado satisfatório no caso em que os clusters apresentam densidades muito diferente, umas vez que fixa os parâmetros minPts e ε para todos (necessidade de normalizar os dados torna-se ainda mais importante).

Aplicação

gerando o gráfico:

Resultados da clusterização DBScan

O resultado, diferentemente dos anteriores, mostra a label “-1”, evidenciando a presença de outliers, dados que não pertencem a nenhum outro grupo. Ademais, vemos claramente a presença da última desvantagem listada: na qual a diferença de densidade entre os clusters ocasionou na criação de grupos menores.

Affinity Propagation

É uma abordagem para a clusterização baseada em grafos em que não é necessário especificar o número de clusters. Seu funcionamento se dá a partir da comunicação entre os datapoints (como uma rede), o loop de troca de informações ocorre da seguinte forma:

1. Um ponto manda uma mensagem para os outros informando sua distância relativa
2. Os receptores da mensagem respondem com sua disponibilidade de se associar com o emissário
3. Os parâmetros iniciais de proximidade são redefinidos

Fonte: Geeksforgeeks

Parâmetros principais de entrada:

• damping: fator no intervalo (0.5, 1.0[ que define o quanto o valor original é mantido em relação às mudanças geradas pelos valores recebidos. Serve para evitar oscilações na atualização dos valores;
• max_iter: número máximo de iterações;
• convergence_iter: número de iterações sem mudanças no número estimado de clusters para parar a convergência;
• preference: preferências para cada ponto. Quanto maior a preferência de um ponto maior a chance de ele ser pego como um exemplar (parâmetro principal para definir o cluster);
• affinity: medida de afinidade usada, e.g. distância euclidiana;

Funcionamento:

Para facilitar ainda mais o entendimento do algoritmo segue o seguinte exemplo de seu funcionamento, dividido em:

• Construção da matriz de similaridade
• Construção da matriz de responsabilidade
• Construção da matriz de disponibilidade
• Construção da matriz de critério

Construção da matriz de similaridade

A similaridade entre duas pessoas é calculada como a negação da soma dos quadrados das diferenças das coordenadas deles:

Exemplo da célula entre Bob e Edna

A tabela final fica no seguinte formato

O número de cluster gerados será menor quanto menor for a diagonal, então preencheremos ela com o menor número de todas as células, -22.

Construção da matriz de responsabilidade

Todas as células começam com 0 e para preencher as células usamos a seguinte fórmula:

A reponsabilidade da pessoa A para a pessoa B é a similaridade da pessoa A para B menos a máxima similaridade da pessoa B.

Depois de calcular todas as responsabilidades obtemos:

Construção da matriz de disponibilidade

Primeiramente preenchemos a diagonal principal com a soma das responsabilidades da pessoa, que são os valores acima de zero excluído a responsabilidade dela com ela mesma.

Depois disso, para preencher a disponibilidade de uma pessoa A para uma pessoa B, somamos a responsabilidade de A com A com os valores positivos restante das responsabilidades de A desconsiderando a responsabilidade de A para B.

Depois de calcular as disponibilidades obtemos:

Construção da matriz de critério

É a soma da matriz de responsabilidade com a de disponibilidade célula a célula, isto é, a célula (1,2) da matriz de critério é a soma das células (1,2) das matrizes de responsabilidade e disponibilidade.

O resultado é:

Para definir os grupos pegamos o critério mais alto de cada coluna e usamos como exemplar para juntar as pessoas em grupos. Daí:

• Alice: 5
• Bob: 5
• Cary:5
• Doug: -5
• Edna: -5

Visto isso, os grupos gerados são: (Alice, Bob e Cary) e (Doug, Edna)

Vantagens

• Não há necessidade de especificar os clusters

Desvantagens

• Alta complexidade do algoritmo acaba por deixa-lo mais lento que os demais.
• O fato de construir diversas matrizes obriga o carregamento de todos os dados na memória.
• O processo assume clusters esféricos ou elípticos, fazendo com que o algoritmo não se saia bem com dados em formatos mais complexos.

Aplicação

Resultados da clusterização Affinity Propagation

Como listado nas desvantagens, o algoritmo recorre a construção de clusters esféricos ou elípticos, gerando resultados nem sempre ideiais para dados complexos. Ademais, é possível perceber que a quantidade de clusters encontrados no exemplo pode ser controlada com o parâmetro preferences, uma vez que, quanto menor esse número, menor a quantidade de clusters que o modelo tende a encontrar. Portanto, podemos ver que, no caso do Affinity Propagation, é necessário uma estimativa clara dos parâmetros para atingir bons resultados.

BIRCH

A maior parte dos algoritmos de clustering hierárquico não são eficientes, isso gera um problema quando você tem que trabalhar com um número grande de dados com recursos limitados. Assim surgiu um método hierárquico chamado BIRCH, o qual, além de visar resolver os desafios da complexidade elevada, foi um dos primeiros algoritmos a lidava com outliers.

Conceitos fundamentais

Antes de entendermos o funcionamento em si do algoritmo, vale entender alguns conceitos fundamentais para esse algortmo de Clustering, esses conceitos são: Clustering Feature e Clustering Feature Tree.

Um Clustering Feature consiste nas informações a respeito de uma subdivisão dos dados criada pelo BIRCH, um subcluster. O CF é definido por 3 valores principais: N, LS e SS:

• N: número de datapoints do subcluster
• LS: soma linear dos datapoints
• SS: Soma ao quadrado dos datapoints

A partir deles pode-se calcular outras características dos clusters, como:

• Centroide C:

• Raio do cluster CR:

• Distância d entre clusters:

Assim, um CF é um agrupamento dos dados que contém essas características. Por fim, o conjunto dos CF em forma de árvore é conhecido como CF Tree, que consiste em uma árvore na qual cada folha contém um sub-cluster. Cada entrada da árvore é um CF por si só e, caso não seja uma folha, apresenta um ramo que aponta para os nós filhos.

Parâmetros principais de entrada:

• threshold: o raio do cluster criado pela junção de dois sub clusters deve ser menor que o threshold
• branching factor: máximo de CFs em cada nó
• n_clusters: número de cluster retornados depois que o algoritmo esteja completo

Funcionamento

O processo de funcionamento do BIRCH tem início com a criação da CF Tree. Para entender esse passo vamos utilizar de um exemplo, criaremos uma CF Tree com base num threshold de 2 e no seguinte conjunto de pontos:

• Começamos inserindo o primeiro ponto

• Inserimos o segundo ponto, como a distância entre o ele e o ponto já no nó é maior que o threshold adicionamos ele ao nó sem agrupamento

• Inserimos o terceiro ponto e como a distância entre ele e o CF1 é menor que o threshold aglomeramos eles

• Inserimos o quarto ponto e como a distância em relação aos CFs é maior que o threshold não ocorre aglomeração

• Inserimos o quinto e como a distância é maior que o threshold e o limite de CFs no nó foi atingido gera-se dois novos nós filhos.

Tendo isso definido, o processo completo de funcionamento do algoritmo se dá de duas formas: Construção da árvore e Clustering global

Possui 3 fases obrigatórias e uma opcional:

• Fase 1: Construir a CF Tree
• Fase 2: Juntar subclusters cheios em clusters maiores para diminuir a árvore
• Fase 3: Usar outro algoritmo de clustering (adaptando eles para os CFs), e.g. K-Means
• Fase 4 (opcional): Repassar pelo dataset para corrigir erros e opcionalmente descartar outliers

Vantagens

• Usa totalmente a memória disponível para definir os melhores clusters
• Não precisa do dataset inteiro logo no início, permitindo menores custos computacionais
• Mais eficiente que os demais algoritmos hierárquicos, mostrando-se uma boa opção para esse tipo de algoritmo
• Pode remover outliers

Para cada decisão de clustering não é necessário analisar todos os data points e clusters existentes. Para isso, ele explora a ideia que o espaço dos dados não é geralmente uniformemente ocupado e, por isso, nem todo datapoint é importante.

Desvantagens

• Tem um funcionamento otimizado apenas para dados numéricos, encontrando dificuldade para lidar com dados categóricos.
• É um algoritmo pouco determinístico, uma vez que a ordem de inserção dos pontos afeta a árvore.
• Duplicatas podem ser classificadas diferentemente, pelo mesmo motivo determinístico.
• Clusters finais podem não ser muito naturais por causa do tamanho das folhas.
• Pelo uso das médias os resultados são em geral esféricos.

Aplicações

Resultados da clusterização BIRCH

Como pode ser visto no resultado aplicado, apesar de identificar facilmente alguns clusters evidentes, a parte superior direita acaba por dividir os clusters de maneira estranha. Isso ocorreu possívelmente pela esparsialidade dos dados, o que pode ter deslocado o cluster 2 de local, fazendo com que o aglomerado de dados com label 1 (verde) na parte superior direita tenha sido relacionada com os dados do centro, e não da extremidade.

Agglomerative Clustering

É um método de clustering hierárquico que funciona tratando cada datapoint como um cluster (chamado de folha) e aglomerando eles em pares gerando um cluster maior (chamado de nó). O processo segue até que todos os pontos estejam aglomerados em um único cluster, obtendo assim, uma árvore hierárquica chamada de dendrograma.

Exemplo de Dendrograma gerado a partir dos dados

Parâmetros Iniciais de Entrada

• n_clusters: número de clusters que queremos obter/acreditamos que existe
• affinity: forma de medir a distância (afinidade) entre os datapoints
• connectivity: matriz de conectividade que define os vizinhos para cada ponto
• compute_full_tree: parâmetro que permite a “parada” do algoritmo caso o dendograma já apresente o número de clusters previsto em n_clusters. É útil para reduzir o tempo de computação dos Clusters.
• linkage: critério de ligação escolhido
• distance_threshold: limite o qual permite que os pontos possam ser agrupados em um cluster. Se essa distância for maior, o algoritmo não os junta

Funcionamento

Como descrito anteriormente o algoritmo se dá da seguinte forma:

1. Ache dois pontos que estejam o mais próximos
2. Substitua eles por um ponto com a média dos valores deles
3. Repita o processo até que todos que haja um único cluster

A proximidade dos pontos é definida pelo cálculo da sua distância, sendo o método mais comum para isso a distância euclidiana.

Isso é bem lógico para os casos entre pontos, mas como isso funciona com os nós?

Para juntar os nós existem alguns diferentes critérios de ligação (Linkage Criterion):

• Single-Linkage: distância entre os pontos mais próximos dos nós
• Complete-Linkage: distância entre os pontos mais distantes dos nós
• Average-Linkage: distância média de todos os pontos pertencentes aos nós
• Centroid-Linkage: distância entre os centróides dos nós

Depois de terminado o dendrograma, faz-se um corte horizontal de acordo com o número de clusters finais desejados.

Vantagens

• Não precisa especificar o número de nós para seu funcionamento, uma vez que cria o máximo possível, e os ajusta posteriormente para o número de clusters especificado.
• É de fácil implementação, servindo de base para diversos outros tipos de algoritmos.
• A produção do Dendrograma é um diferencial claro no que tange o processo de análise de dados, uma vez que permite entender a hierarquia do grupo de dados de modo mais objetivo, sendo muito utilizado nesses casos.

Desvantagens

• Por ser um algoritmo progressivo, o sistema, ao encontrar um cluster, não pode desfaze-lo mesmo se, com a progressão do algoritmo, seja encontrado grupos melhores.
• Por ser um algoritmo rústico e por criar diversos clusters, o algoritmo apresenta uma complexidade e tempo de execução mais elevada do que os demais.

Aplicação

Resultados da clusterização Agglomerative Clustering

Conclusão

Problemas de Clusterização estão presentes cada vez mais e podem servir como chave para diversos setores e empresas que desejam potencializar suas decisões e análises com o uso de dados.

Como visto hoje neste Turing Talks, esse universo compreende diversos algoritmos, cada um com suas vantagens e desvantagens, cabendo a nós estudarmos e compreendermos quais deles são as melhores opções para a resolução de cada problema.

Este texto apesar de bem carregado com muito conteúdo, ainda toca na superfície dos problemas e algoritmos de Clusterização, abrindo portas para muitas oportunidades de aprofundamento nos próximos Turing Talks. Estamos nos primeiros passos de um longo caminho :)

Esperamos que você tenha gostado e muito obrigado por chegar até aqui. Se quiserem conhecer um pouco mais sobre o que fazemos no Turing-USP, não deixem de nos seguir nas redes sociais: Facebook, Instagram, LinkedIn e, claro, acompanhar nossos posts no Medium. Para acompanhar também mais de perto e participar de nossas discussões e eventos, entre no nosso servidor do Discord.

Até a próxima!