O que é análise de cluster?

A análise de cluster é uma técnica de análise de dados que explora os grupos que ocorrem naturalmente dentro de um conjunto de dados, conhecidos como clusters. A análise de cluster não precisa agrupar pontos de dados em nenhum grupo predefinido, o que significa que é um método de aprendizado não supervisionado. No aprendizado não supervisionado, as informações são derivadas dos dados sem rótulos ou classes predefinidos. Um bom algoritmo de agrupamento (clustering) garante alta similaridade intracluster e baixa similaridade entre clusters.

Um exemplo de um problema de agrupamento de dados

Agrupar lojas de varejo com base em suas vendas é um caso de uso simples de análise de agrupamento. Suponha que um café tenha oito pontos de venda na cidade. A tabela abaixo mostra as vendas de cappuccino e iced coffee por dia.

O gráfico abaixo mostra os mesmos dados, onde as vendas de cappuccino e iced coffee para cada ponto de venda são plotadas nos eixos X e Y, respectivamente. Neste exemplo, como havia pontos de dados limitados, foi fácil traçar os dois clusters naturais de pontos de venda de café em um gráfico e visualizá-los manualmente.

No entanto, quando se trata de milhares de pontos de dados, os algoritmos de análise de cluster precisam ser usados para segregar os pontos de dados em diferentes clusters.

Quais são as aplicações da análise de cluster?

A análise de cluster é frequentemente usada de duas maneiras principais:

• Como uma ferramenta autônoma para resolver problemas relacionados ao agrupamento de dados.
• Como uma etapa de pré-processamento para vários algoritmos de aprendizado de máquina.

Análise de cluster como uma ferramenta autônoma

• Marketing: em marketing, a análise de cluster pode ser usada para separar os clientes em diferentes grupos com base em seus padrões ou interesses de compra. Estes são conhecidos como personas do cliente. As organizações então usam diferentes estratégias de marketing para diferentes grupos de clientes.
• Análise de risco em finanças: as organizações financeiras usam vários algoritmos de análise de cluster para segregar seus clientes em várias categorias de risco com base em seu saldo bancário e dívida. Ao aprovar empréstimos, seguros ou cartões de crédito, esses clusters são usados para auxiliar na tomada de decisões.
• Imóveis: especialistas em infraestrutura usam clusters para agrupar casas de acordo com seu tamanho, localização e valor de mercado. Essas informações são usadas para avaliar o potencial imobiliário de diferentes partes de uma cidade.

Análise de cluster como uma etapa de pré-processamento para aprendizado de máquina

A análise de cluster é frequentemente usada como uma etapa de pré-processamento para vários algoritmos de aprendizado de máquina.

Os algoritmos de classificação executam a análise de cluster em um extenso conjunto de dados para filtrar dados que pertencem a grupos óbvios. Técnicas avançadas de classificação de dados podem então ser usadas nos pontos de dados reduzidos e não óbvios. À medida que o conjunto de dados se torna menor, o tempo de computação é altamente reduzido. O mesmo método pode ser usado de maneira oposta, onde um algoritmo de análise de cluster é usado para filtrar o ruído ou os dados discrepantes.

Antes de executar um algoritmo de aprendizado supervisionado, pode-se primeiro fazer uma análise de cluster nos dados de entrada para descobrir os clusters naturais nos dados.

Quais são os principais algoritmos de análise de cluster?

Os algoritmos de análise de cluster geralmente pertencem às seguintes categorias:

• Algoritmos baseados em partição
• Algoritmos hierárquicos
• Algoritmos baseados em densidade
• Algoritmos baseados em grade
• Algoritmos baseados em modelo
• Algoritmos baseados em restrições
• Algoritmos de análise de pontos discrepantes

Cada algoritmo é complexo em si mesmo e pode ser adequado para algumas análises e não para outras.

Algoritmos baseados em partição para análise de cluster

Neste método, um algoritmo começa com vários clusters iniciais. Em seguida, ele realoca iterativamente os pontos de dados para diferentes clusters até que uma partição ideal seja alcançada. O algoritmo de agrupamento K-means é um dos algoritmos de agrupamento mais populares.

Um exemplo de agrupamento K-means abaixo mostra como isso funciona.

Etapa 1: decida sobre os clusters

Decida o número de clusters, “K” para o algoritmo, por exemplo, K=3. O algoritmo irá particionar os doze pontos de dados acima em 3 clusters. O número K pode ser qualquer valor. Dependendo disso, a exatidão do agrupamento pode variar. Existem também métodos algorítmicos que podem ser usados para determinar o valor ótimo para K.

Etapa 2: escolha os pontos de dados

Como K=3, tome quaisquer três pontos de dados como a média inicial. Neste exemplo, os pontos C, D e E são escolhidos como médias iniciais. Observe que o algoritmo K-means pode tomar qualquer ponto como a média inicial.

Passo 3: calcule as distâncias

Calcule a distância de cada ponto no conjunto de dados para cada média de cluster inicial. Três médias de cluster C, D e E foram escolhidas aleatoriamente. Para cada ponto de dados na amostra, calcule a distância dessas três médias. A distância euclidiana entre dois pontos (X1, Y1) e (X2, Y2) é usada como abaixo:

Após a etapa 3, uma tabela mostraria a distância de cada ponto de dados das médias iniciais C, D e E.

Um ponto de dados é adicionado a um cluster com base em sua distância mínima. Por exemplo, o ponto A tem uma distância mínima de uma média inicial C. Isso significa que A está no cluster com média igual a C. Após a primeira etapa, os clusters são obtidos.

Passo 4: reiteração – cálculo de nova média

Agora é fácil ver os clusters iniciais. O próximo passo é calcular três novas médias de cluster. Para isso, cada ponto de dados em um determinado cluster é obtido e uma média é calculada.

Nova média de cluster para o cluster “C” = (5+2+6+1+4+3+6/7, 21+11+22+10+23+14+12/7) = (3,85; 16,14), Vamos chamar este ponto de X.

Nova média de cluster para o cluster “D” = (1+2+5/3, 6+8+4/3) = (2,66; 6), vamos chamar este ponto de Y.

Nova média de cluster para o cluster “E” = (4+5/2, 10+11/2) = (4,5; 10,5). Vamos chamar este ponto de Z.

Etapa 5: reiteração—calcule a distância de cada ponto de dados da nova média

Repita a etapa 3 para descobrir a distância de todos os pontos de dados das médias de cluster recém-calculadas, X, Y e Z. Nesta nova iteração, é fácil ver que a distância mínima dos pontos de dados C, D, I, e L mudou. Eles agora pertencem a um novo cluster, conforme mostrado abaixo.

Em seguida, a iteração K-means precisa continuar, pois alguns dos pontos de dados mudaram seus clusters.

Etapa 6: reiteração - cálculo de novas médias e novos clusters

Como os pontos de dados C, D, I, L mudaram seus clusters, novas médias de cluster precisam ser calculadas como na etapa 4. Para isso, cada ponto de dados em um determinado cluster é obtido e uma média é calculada. Então, como na etapa 5, a distância de cada ponto de dados para a nova média do cluster é calculada. Com base na distância, os pontos de dados são atribuídos a um cluster ao qual tem uma distância mínima.

Quando o algoritmo K-means termina?

K-means é um algoritmo de partição iterativo:

• Decida o número de clusters (K) para começar. No exemplo acima, K=3.
• Atribua aleatoriamente o número K de pontos de dados como a média inicial do cluster.
• Repita as etapas abaixo até que nenhum ponto de dados altere seu cluster.
• Calcule a distância média do ponto de dados para a média do cluster.
• Atribua um ponto de dados ao cluster com a menor distância.
• Verifique se algum ponto de dados mudou seu cluster.

Em uma nova iteração, se cada ponto de dados permanecer em seu cluster anterior, o algoritmo K-means será encerrado. Isso significa que uma solução localmente ótima foi obtida.

Algoritmo de cluster baseado em partição K-Medoid

O algoritmo K-medoids é outro algoritmo de agrupamento baseado em partição. Os algoritmos K-medoid escolhem medoids como um objeto representativo de um cluster. O algoritmo K-medoid tenta encontrar tais pontos de dados que tenham uma dissimilaridade mínima de todos os outros pontos de dados em um determinado cluster. Até que a dissimilaridade seja minimizada, o algoritmo K-medoid particiona iterativamente o conjunto de dados. O algoritmo K-means geralmente usa a distância de erro quadrático (distância euclidiana), e os algoritmos K-medoid geralmente usam uma distância de valor absoluto, como a distância de Manhattan, para medir a dissimilaridade entre dois pontos de dados.

Uma implementação padrão do algoritmo K-medoid é o algoritmo Partition Around Medoids (PAM). Aqui estão os passos básicos do algoritmo PAM.

1. Escolha um valor para K, onde K é o número de clusters em que os pontos de dados serão divididos.
2. Escolha o número K de pontos de dados aleatoriamente como medoids.
3. Para cada ponto de dados (Xi, Yi) no conjunto de dados, meça a dissimilaridade entre o ponto e os medoids selecionados acima. Uma medida frequentemente usada para dissimilaridade é a distância de Manhattan:
   • | Xi – Ci| + | Yi - Cj|, onde (Ci, Cj) representa um medoid.
4. Cada ponto de dados (Xi, Yi) é atribuído a um cluster onde a dissimilaridade é mínima.
5. Para cada um dos clusters acima, calcule o custo total – a soma das dissimilaridades de cada um dos pontos de dados nesse cluster.
6. Agora, selecione aleatoriamente um ponto não-medoid para ser o novo medoid e repita as etapas 3-5.
7. Pare quando não houver alterações nos clusters.

Comparação de algoritmos K-Means e K-Medoid

Embora o algoritmo K-means seja simples, ele não produz bons resultados quando os dados têm muito ruído e valores discrepantes. O método K-medoid é mais robusto nesses casos. No entanto, os algoritmos K-medoid como o PAM são úteis apenas quando o conjunto de dados é pequeno. Quando o tamanho do conjunto de dados aumenta, o tempo de computação para o algoritmo K-medoid aumenta exponencialmente.

Algoritmos divisivos

Como o nome sugere, os algoritmos divisivos atribuem todos os pontos de dados em um único cluster no início. Em seguida, ele divide o cluster em clusters menos semelhantes. O algoritmo então divide recursivamente esses clusters até que uma solução ótima seja alcançada. Algoritmos divisivos também são conhecidos como um método de agrupamento de cima para baixo.

Algoritmos aglomerativos

Esses algoritmos começam com a atribuição de cada ponto de dados a um cluster diferente. Então, o algoritmo une recursivamente os clusters mais semelhantes até que uma solução ótima seja alcançada. Os algoritmos aglomerativos também são conhecidos como método de agrupamento de baixo para cima.

Exemplo de um algoritmo de agrupamento aglomerativo

Abaixo está uma matriz de distância para cinco pontos de dados. A distância entre os pontos pode ser calculada com base na distância euclidiana ou distância de Manhattan ou qualquer outra fórmula de distância. A matriz de distância é sempre uma matriz simétrica, pois a distância entre os pontos X e Y é a mesma que entre Y e X. Com base nessa matriz de distância, um exemplo de algoritmo de agrupamento aglomerativo (de baixo para cima).

Passo 1: na matriz de distância, encontre os dois pontos cuja distância é a menor. No exemplo acima, são os pontos 3 e 5. A distância entre eles é 2. Coloque-os em um único cluster.

Passo 2: remova os pontos 3 e 5 e substitua-os por um cluster “35” e crie uma nova matriz de distância. Para isso, é necessário calcular a distância entre todos os pontos de dados e o cluster “35”. Existem várias maneiras de determinar essa distância.

Neste exemplo, o seguinte método foi usado para medir a distância:

Distância do ponto X do cluster “35” = mínimo (distância (X, 3), distância (X, 5)). A matriz de distância atualizada com base neste método é:

Etapa 3: repita a etapa 2 até que todos os pontos de dados sejam agrupados em um único cluster. No exemplo atual, são necessárias seis iterações. O diagrama abaixo mostra a formação de clusters. Esse tipo de representação é conhecido como dendrograma. Nesta representação, o eixo Y representa a distância entre dois pontos de dados. Por exemplo, a distância entre os pontos 3 e 5 é 2.

Etapa 4: depois que todos os pontos de dados estiverem agrupados, conforme mostrado acima, decida quantos agrupamentos precisam ser retidos. É uma decisão difícil porque todo algoritmo de agrupamento hierárquico finalmente produz um único cluster. Existem vários métodos disponíveis para decidir o número ideal de clusters após um algoritmo de agrupamento hierárquico particionar os dados.

Algoritmos de clustering baseados em densidade

Esses algoritmos são baseados na ideia de que os clusters são sempre mais densos que o espaço de dados circundante. Os algoritmos baseados em densidade começam com um único ponto de dados e exploram os pontos de dados em sua vizinhança. Os pontos na vizinhança do ponto inicial são incluídos em um único cluster. A definição de vizinhança varia dependendo da implementação do algoritmo. O agrupamento espacial baseado em densidade de aplicativos com ruído (DBSCAN) é um algoritmo de agrupamento popular nesta categoria.

Algoritmos de agrupamento baseados em grade

Os algoritmos de agrupamento baseados em grade são semelhantes aos baseados em densidade. O espaço de dados é dividido em várias unidades menores, conhecidas como grades. Cada ponto de dados é atribuído a uma célula de grade específica. O algoritmo então calcula a densidade de cada grade. Aquelas grades cuja densidade é inferior a um limite são eliminadas. Em seguida, o algoritmo forma clusters a partir de grupos adjacentes de grades densas. Os algoritmos STING (Statistical information Grid) e CLIQUE (Clustering in Quest) são dois algoritmos populares baseados em grade.

Além dos algoritmos discutidos acima, a análise de agrupamento inclui um grupo de algoritmos de agrupamento baseado em modelo, de agrupamento baseado em restrição e de análise de valores discrepantes.

Vantagens e desvantagens dos algoritmos de análise de clustering