Classes básicas de algoritmos
Agrupamento hierárquico
- Busca reunir sucessivamente grupos menores, formando grupos maiores, ou dividir grupos grandes em outros de maior similaridade
interna. Os métodos diferem pela regra adotada para decidir quais grupos devem ser reunidos ou divididos. O resultado do algoritmo é um gráfico tipo árvore chamado de "dendograma" que mostra como os grupos são inter-relacionados
- Dendograma: http://pt.wikipedia.org/wiki/Dendrograma
Agrupamento particional
- Busca dividir o conjunto de dados em um conjunto de grupos distintos entre si, maximizando as dissimilaridades dos diferentes grupos. As técnicas que seguem o agrupamento particional, incluindo K-means e diversas outras, geralmente são baseadas na otimização de uma função de custo, que envolve, por exemplo, a minimização do erro quadrático, e são de natureza combinatorial.
Abordagem de agrupamento particional
- Agrupamento k-medio?
- Cada grupo é associado com um centróide (ponto central)
- Cada ponto é assinalado ao grupo com o centróide mais próximo
- Número de grupos, K, deve ser especificado
- O algoritmo básico é muito simples
- Em função do tamanho dos arquivos, o tempo de processamento é muito grande. Por isto, técnicas de otimização tais como simulated annealing e algoritmos genéticos são empregadas para acelerar o processamento.
Tipos de agrupamentos
PBM
- O Índice PBM, desenvolvido por PAKHIRA, BANDYOPADHYAY e MAULIK, pode ser utilizado para avaliar a qualidade de segmentação de bases de dados em diferentes partições, podendo ser aplicado tanto em segmentações clássicas quanto difusas. Este índice é obtido pela composição de três fatores, conforme apresentado na equação, e a sua maximização dá-se em torno de formações com pequeno número de grupos compactos e com uma grande separação entre dois deles, ao menos
CALINSKI E HARABASZ
- Este índice foi desenvolvido por Calinski e Harabasz. É um método estatístico para encontrar a melhor distribuição de pontos para um conjunto de grupos. Este procedimento primeiramente recebe a quantidade de grupos (k). Posteriormente divide a base de dados em k grupos e realiza, aleatoriamente, uma distribuição eqüitativa dos pontos em cada grupo formado.
- Após esta divisão em k grupos, o método verifica a que grupo cada ponto pertence através da medida de distância entre o ponto e o centro de cada grupo. O grupo que apresentar a menor distância recebe este ponto. Sempre que acontece para um ponto uma troca de grupos, o método calcula novamente seu centro. Este procedimento acontece até que acabe a troca de pontos entre os grupos.