Data Mining

Proposto por J. MacQueen em 1967, o algoritmo de k-means (ou algoritmo das k-médias) este é um dos mais conhecidos e utilizados, além de ser o que possui o maior número de variações. O algoritmo inicia com a escolha dos  k elementos que formaram as sementes iniciais. Esta escolha pode ser feita de muitas formas, entre elas:

• selecionando as k primeiras observações;
• selecionando k observações aleatoriamente; e
• escolhendo k observações de modo que seus valores sejam bastante diferentes. Por exemplo, ao se agrupar uma população em três grupos de acordo com a altura dos indivíduos, poderia se escolher um indivíduo de baixa estatura, um de estatura mediana e um alto.

Escolhidas as sementes iniciais, é calculada a distância de cada elemento em relação às sementes, agrupando o elemento ao grupo que possuir a menor distância (mais similar) e recalculando o centróide do mesmo. O processo é repetido até que todos os elementos façam parte de um dos clusters.

Após agrupar todos os elementos, procura-se encontrar uma partição melhor do que a gerada arbitrariamente. Para isto, calcula-se o grau de homogeneidade interna dos grupos através da Soma de Quadrados Residual (SQRes), que é a medida usada para avaliar o quão boa é uma partição.

Após o cálculo, move-se o primeiro objeto para os demais grupos e verifica-se se existe ganho na Soma de Quadrados Residual, ou seja, se ocorre uma diminuição no valor da SQRes. Existindo, o objeto é movido para o grupo que produzir o maior ganho, a SQRes dos grupos é recalculada e passa-se ao objeto seguinte. Depois de um certo número de iterações ou não havendo mais mudanças, o processo é interrompido.

Exemplo de execução do algoritmo de k-means

A  figura  mostra a execução do algoritmo das  k-médias  para formar dois agrupamentos a partir da população composta pelos elementos {2, 6, 9, 1, 5, 4, 8}. Pode-se observar que como sementes foram escolhidos os dois primeiros e como critério para definir o valor do centróide após a união foi usada a média. Na figura,  c1 e c2 apresentam os valores dos centróides de cada um dos agrupamentos após a adição de um novo elemento.

O algoritmo  de k-means  é bastante escalar e confiável, porém apresenta alguns problemas. Os dois principais problemas são:

• Exige que as variáveis sejam numéricas ou binárias  e freqüentemente aplicações envolvem dados categorizados, neste caso, uma alternativa é converter os dados categorizados em valores numéricos ou utilizar uma das muitas variações do método; e
• É sensível a valores  outliers, um único objeto com valor muito extremo pode modificar, substancialmente, a distribuição dos dados.

Análise de Agrupamentos (AA), ou Cluster Analysis, é uma técnica para reunir objetos em grupos, de tal forma que os objetos que estão no mesmo grupo são mais similares entre si do que objetos que estão em outro grupo definido, segundo uma medida de similaridade pré-estabelecida. Em outras palavras, o objetivo da AA é identificar os objetos que possuem características em comum e separá- los em subconjuntos similares, determinando o número e as características desses grupos (HUANG, 1997).

A partição de objetos em grupos mais homogêneos é uma operação fundamental para mineração de dados, já que a operação é necessária para um grande número de tarefas, como a classificação não supervisionada e a sumarização de dados, bem como na divisão de grandes conjuntos heterogêneos de dados em conjuntos menores, que são mais fáceis de gerenciar e modelar.

Existem inúmeros algoritmos baseados em medidas de similaridade ou modelos probabilísticos para a formação dos agrupamentos (assim que possível publicarei alguns aqui). Os algoritmos de AA exigem de seus usuários a tomada de diversas decisões, o que faz surgir à necessidade do conhecimento das propriedades de cada um deles (aliás isto serve para a grande maioria dos algoritmos de DM). Conhecendo-se os diferentes algoritmos, é possível determinar qual deles é a melhor escolha para atingir os objetivos estabelecidos, fazendo assim com que o tempo e o custo de recuperação diminua.

Para finalizar, a melhor referência em português sobre Análise de Agrupamentos é, sem dúvida nenhuma, o trabalho intitulado Introdução à Análise de Agrupamentos de Wilton de Oliveira Bussab, Édina S. Miazaki e Dalton F. de Andrade (ps: é preciso gostar muito de estatística).