Clusterização

Uma das habilidades mais básicas dos organismos vivos é a capacidade de agrupar objetos similares para produzir uma taxonomia, uma classificação, ou um agrupamento.

Humanos se interessam por categorizações…

Diversas ciências se baseiam na organização de objetos de acordo com suas similaridades

Existem muitas situações nas quais não sabemos de antemão uma maneira apropriada de agrupar uma coleção de objetos de acordo com suas similaridades

Imagine que você tem uma cesta cheia de frutas diferentes. Como você poderia agrupá-las?

A clusterização é uma técnica de mineração de dados que nos permite descobrir padrões e estruturas ocultas em conjuntos de dados. Ela agrupa objetos similares e os separa dos demais, formando clusters.

Os grupos são formados de maneira a maximizar a similaridade entre os elementos de um grupo (similaridade intra-grupo) e minimizar a similaridade entre elementos de grupos diferentes (similaridade inter-grupos)

Métodos de clusterização

Já conhecemos…

• Métodos hierárquicos
• Métodos não-hierárquicos

Métodos baseados em densidade

São técnicas utilizadas na mineração de dados para identificar agrupamentos ou padrões em conjuntos de dados com base na densidade dos elementos amostrais.

Esses métodos levam em consideração a proximidade entre os indivíduos, agrupando aqueles que estão próximos uns dos outros em regiões densas.

Uma região densa é uma região onde cada ponto tem muitos pontos em sua vizinhança.

Método DBSCAN

O método DBSCAN (Density-Based Spatial Clustering of Applications with Noise) é um dos algoritmos baseados em densidade mais conhecidos.

Vamos definir densidade como sendo o número de pontos dentro de um raio específico (Eps)

Um ponto é um ponto de núcleo (core point) se ele tem mais que um número especificado de pontos (MinPts) dentro de Eps

Estes são os pontos que estão no interior de um grupo

Um ponto de fronteira (border point) tem menos que MinPts dentro de Eps mas está na vizinhança de um ponto núcleo

Um ponto de ruído (noise point) é um ponto que não é nem um ponto núcleo nem um ponto de fronteira.

Para encontrar os agrupamentos, o algoritmo DBSCAN faz uma varredura nas observações determinando todos os pontos núcleo.

Faz-se a seguir uma varredura dos pontos núcleo fazendo as conexões a todos os pontos que estejam a uma distância menor do que (Eps).

Cada subconjunto de pontos conectados entre si (conectividade), forma um cluster.

Vantagens do DBSCAN

• Eficiente em tratar grandes bases de dados
• Menos sensível a ruídos
• Forma clusters de formato arbitrário
• Usuário não precisa determinar a quantidade de clusters

Desvantagem do DBSCAN

Sensível aos parâmetros de entrada (Eps e MinPts)

Determinação dos valores de Eps e MinPts

• Verificar a distância ao k-ésimo vizinho mais próximo: k-dist

• Para objetos que estão dentro de um cluster: se k for menor ou igual ao tamanho do cluster então k-dist é pequeno.

• Para objetos que não estão dentro de um cluster: k-dist é grande
• Seleciona-se os k-dist para cada objeto, para um determinado valor de k.
• Ordena-se os objetos pelos valores de k-dist

• No ponto onde houver uma grande variação do número k-dist, significa que foi atingido um valor adequado para Eps.
• Valor de Eps depende do número k escolhido.
• Na prática, o valor k = 4 é utilizado para a maioria dos banco de dados, com bons resultados

Problema: Clusters com densidades diferentes

Se Eps é alto suficiente para que C e D sejam detectados como clusters então A e B e a região a sua volta se tornarão um único cluster

Se Eps é baixo suficiente para que A e B sejam detectados como clusters separados então C e D (e os objetos a seu redor) serão considerados outliers!