Classificação não supervisionada

Como supervisionamos o não supervisionado?

A classificação não supervisionada é um processo onde não sabemos: a classe dos elementos, o processo de geração dos padrões das classes e algumas vezes sequer sabemos quantas classes são envolvidas. E normalmente a única informação disponível são os vetores de características dos elementos.

Photo by Matthew Henry on Unsplash

Agrupamento — Clustering

Uma das abordagens mais utilizadas é o agrupamento, onde com base nas características são realizadas partições entre grupos de instâncias. O que é utilizado para a separação são os atributos disponíveis, que podem ter diferentes distribuições.

Os critérios para agrupamento são sempre com base na similaridade, ou seja, quão mais similares duas instâncias, mais próximas elas estarão no espaço.

Uma das formas de formalizar o critério de similaridade é através da dispersão dos dados. Cada grupo deve conter elementos com baixa dispersão (baixa dispersão intraclasse) e entre os grupos deve existir uma alta dispersão (alta dispersão interclasse).

Antes de definirmos as dispersões mais interessantes, temos a dispersão base definida na matriz:

Matriz de dispersão de todos os atributos

Onde:

• n é o número de elementos;
• fi é o vetor com de cada característica;
• M é o vetor dos valores médios.

E com isso podemos definir as outras matrizes mais interessantes:

Matriz de dispersão dos atributos por classe

Onde ui é a média do atributo naquela classe.

Matriz de dispersão intraclasse

Matriz de dispersão interclasse

Uma propriedade interessante para notarmos em relação às matrizes é que S é igual a Sintra + Sinter. Isso significa que para achar a melhor relação entre as dispersões interclasse e intraclasse podemos nos atentar somente à uma dessas dispersões.

Além da dispersão, uma das noções que podemos ter é a de distância em relação às instâncias e para isso é importante lembrarmos da normalização, já que variáveis de diferentes medidas podem afetar a nossa visão de distância.

Agrupamento hierárquico

Consiste em agrupamentos progressivos de instâncias em classes, de acordo com sua determinada medida de dissimilaridade (por exemplo: distância). Nesse agrupamento dos objetos mais próximos são agrupados em subgrupos antes de objetos mais distantes.

Existem duas técnicas mais utilizadas nesse caso:

Abordagem aglomerativa

Partimos dos elementos individuais e vamos agrupando de acordo com a matriz de distâncias entre os grupos correntes. Dentro dessa abordagem temos algumas maneiras de calcular a dissimilaridade:

• Ward's linkage, a união ocorre entre os dois grupos que menos aumentam a dispersão intraclasse.
• Single linkage utiliza a distância mínima entre as classes vizinhas;
• Complete linkage utiliza a distância máxima;
• Average linkage utiliza a distância média;
• Centróide utiliza um ponto fantasma representando o valor médio dos grupos.

Normalmente utilizamos a distância euclidiana, mas ainda é possível utilizar diferentes distâncias, seguem algumas, caso tenham curiosidade:

• Distância Manhattan;
• Distância Minkovski;
• Distâncias ponderadas;
• Distância chessboard;
• Distância Mahalanobis.

Agrupamento particional — Abordagem divisiva

Partimos de um grupo com todos os elementos e vamos dividindo. A maneira mais simples de pensar nesse método seria realizar uma execução em volta de todo o conjunto de dados alterando as classes das instâncias e verificando se a distância intraclasse diminui ou aumenta.

Nessa abordagem é importante termos um número de grupos fixo, caso contrário o algoritmo tenderia a aumentar o número de grupos já que grupos menores tendem a diminuir a dispersão intraclasse.

Apesar dessa abordagem ter uma rápida convergência ela sofre com o problema de mínimos locais, ou seja, encontrar uma solução que localmente pareça ótima, mas globalmente esteja longe do ideal. Ainda temos outras opções de algoritmos:

• K-médias (k-means), que é o algoritmo mais famoso dessa categoria. Ele utiliza a matriz de distâncias (ao invés da matriz de dispersão) como medida de dissimilaridade. O espaço de divisão é iniciado com K pontos iniciais para representar cada classe, sendo que cada ponto não precisa ser uma instância, mas um ponto relacionado à informação de todas as instâncias de cada classe, inserindo uma informação a priori. Ele utiliza sempre o contróide de cada classe. Um dos maiores desafios aqui é a escolha dos K protótipos iniciais, que acabam afetando bastante a forma de separação dos grupos;
• k-means++, é uma variação do k-means que atribui pesos aos objetos de forma a ter prioridade na escolha de objetos que estejam mais espaçados;
• k-medoids ou PAM (partitioning around medoids), nesse caso o protótipo deve ser um objeto da classe, o que ajuda a diminuir s sensibilidade a outliers. Nesse caso é utilizado a função custo de erro absoluto, o que o torna mais robusto e custoso que o k-means;
• CLARA e outros, variação do k-medoids para grandes conjuntos de dados;
• K-mode para variáveis categóricas;
• K-prototypes, para conjuntos de dados mistos com variáveis numéricas e categóricas;
• Fuzzy k-médias, baseado na lógica fuzzy cada objeto tem uma probabilidade de pertencer a uma classe.

Caso não tivermos um bom chute para K, que é o número de grupos a serem divididos uma boa alternativa é testar vários valores e ver a convergência da média de distância para o contróide de cada grupo.

Outras técnicas de agrupamento

Falamos um pouco sobre algumas técnicas básicas de agrupamentos, mas existem muitas outras, para curiosidade:

• Baseados em densidades;
• Baseados em modelos;
• Baseados em grafos;
• Baseados em redes neurais;
• Baseados em grid;
• Baseados em restrições.

Como em quase todos os modelos de machine learning (não me arrisco a generalizar) existe sempre as melhores aplicações para determinados conjuntos de dados e situações, no caso de agrupamento o tipo da região (convexa ou côncava) pode fazer muita diferença, segue abaixo uma imagem que demonstra bem vários tipos de agrupamentos e seus resultados:

Tipos de agrupamento

Antes mesmo de pensar no agrupamento de um conjunto é interessante verificarmos o quanto esse conjunto está tendendo ao agrupamento, isso pode ser feito utilizando a medida de Hopkins, que quanto mais próxima de 1 maior a tendência.

Também é interessante sempre pensarmos na validação do algoritmo que estamos utilizando, algumas formas simples de validar:

• Testar com vários subconjuntos;
• Testar diferentes algoritmos de agrupamento e verificar a similaridade de resultados.

Gostou do conteúdo?

Siga a Luna no Medium. E não se esqueça de deixar alguns aplausos 👏🏽Qualquer dúvida ou sugestão é só deixar nos comentários!

Obrigado e até mais :)