Data Mining

O algoritmo BIC (Bayesian Information Criterion) baseia-se num conceito que, numa livre tradução, pode ser chamado de densidades de mistura finita. Uma mistura de máxima verossimilhança, fator de Bayes e um modelo probabilístico - o paraíso para quem gosta de matemática e estatística.

Para nao usar matemática e estatística, até porque elas não fazem parte da minha área de atuação, pode-se dizer que o BIC é na verdade o valor da máxima verossimilhança com uma penalização para o número de parâmetros no modelo, o que permite comparar modelos com diferentes parametrizações e/ou diferentes número de agrupamentos. Através desse valor o algoritmo determina o provável modelo a ser usado de acordo uma aproximação baseada no critério de informação Bayesiana.

Complexo? O detalhamento completo do funcionamento do algoritmo (e também das equações matemáticas que fazem parte dele) pode ser encontrado no artigo Model-based Clustering, Discriminant Analysis, and Density  Estimation de FRALEY e RAFTERY (veja a referência completa clique aqui).

Conforme HAN e KAMBER (2001), o algoritmo DBSCAN (Density-Based Spatial Clustering of Applications with Noise) descobre agrupamentos com forma arbitrária em bases de dados espaciais com ruídos, ou seja, encontra regiões densas que são separadas por regiões de baixa densidade e agrupa os objetos na mesma região densa.

Iniciando por um objeto qualquer, o que o torna insensível a ordem dos elementos, o método encontra  agrupamentos  verificando a vizinhança  r de cada ponto da base de dados. Se a vizinhança r de um ponto qualquer contém mais do que MinPts, então um novo agrupamento é criado e este ponto passa a ser um centro. Então, iterativamente o método coleta objetos alcançáveis por densidade diretamente destes centros até que nenhum novo ponto possa ser adicionado a qualquer agrupamento.

Diferentemente dos métodos de partição, que exigem como entrada o número  de agrupamentos a serem formados, este método exige apenas  r e MinPts. O problema é que em bancos de dados do mundo real estes parâmetros são normalmente definidos empiricamente, como o algoritmo é sensível aos seus valores, ajustes ligeiramente diferentes  podem resultar na união de dados muito diferentes.

O desempenho do algoritmo depende da utilização ou não de um índice indexador de bases espaciais. Independente da utilização ou não do indexador, seu custo computacional é comparável ao de um método hierárquico, já que necessita comparar todos os elementos presentes na base de dados.

Para finalizar, por hora, os Métodos Hierárquicos de Análise de Agrupamentos, vou falar rapidamente sobre dois de seus principais algoritmos: o AGNES e o DIANA. Para maiores informações sobre os mesmos, sugiro a leitura da referência bibliográfica utilizada por mim para escrever este post, o livro Finding Groups in Data: An Introduction to Cluster Analysis de KAUFMAN e ROUSSEEUW.

AGNES

O AGNES (AGglomerative NESting), é um algoritmo baseado no método hierárquico aglomerativo, ou seja, no início c ada objeto forma um agrupamento e a cada nova interação os agrupamentos mais próximos são unidos, formando um só, de acordo com um critério pré-estabelecido.

Entre os critérios de junção é possível citar o que une os agrupamentos de acordo com a média da dissimilaridade (average linkage) entre os pontos de um agrupamento e outro, o método do vizinho mais próximo ( single  linkage) que usa a menor distância entre os dois agrupamentos e o método do vizinho mais longe (complete linkage) que usa a maior distância entre os dois agrupamentos.

Comparado a outros algoritmos aglomerativos, o AGNES apresenta as duas vantagens: (1) utiliza um coeficiente que mede a quantia de estruturas de agrupamentos descobertas, que procura minimizar as buscas e (2) a partir da árvore gráfica usualmente usada para representá-lo é possível prover novas representações.

DIANA

O DIANA (DIvisive ANAlysis) é um algoritmo hierárquico divisivo, ou seja, no início todos os objetos estão no mesmo agrupamento. A cada interação o agrupamento é divido em outros dois, de acordo com um critério pré-definido (os mesmos do AGNES),  até que cada agrupamento contenha apenas uma observação.

A escolha de qual agrupamento dividir se  dá  a cada etapa do processo, sendo selecionado sempre o agrupamento que tiver o  maior diâmetro (maior dissimilaridade entre qualquer duas de suas observações). Para dividir o agrupamento selecionado, o algoritmo primeiro procura pela observação mais dissimilar dentro do grupo, esta observação  será  o primeiro elemento do novo agrupamento. A seguir, ele reagrupa as observações  que porventura estejam mais próximas do novo grupo do que do grupo original. O resultado do processo é a divisão em dois novos grupos.

Para entender melhor o processo descrito no post anteior, pode-se imaginar um conjunto hipotético contendo 5 elementos {A, B, C, D, E}. Deseja-se agrupar estes elementos de acordo com o número de vezes em que compraram em determinada loja no último ano. O número de compras é representado pelo conjunto { 0,  2, 4,  5,  8}. Um possível cenário de execução é demonstrado a partir de agora.

Passo 1: É calculada  a distância entre todos os objetos (usei a medida Euclideana neste exemplo). Este cálculo forma a matriz de distância, apresentada a seguir:

Passo 2: Os dois objetos mais similares são agrupados e o valor do centróide do grupo é calculado (usaremos a média aritmética). Os elementos  C e  D são os mais similares, já que d(4,5) =  1 e o novo centróide é 4.5.  Assim, o  novo  agrupamento é  formado  e o conjunto inicial é reduzido em um elemento {A, B, CD, E}.

Passo 3: São calculadas as distâncias de  A, B e  E em relação a  novo elemento (CD). Não é necessário recalcular as demais distâncias já que isto foi feito no primeiro passo. A seguir, tem-se a nova matriz de distância, onde a linha grifada mostra que apenas três distâncias foram calculadas, as demais são inalteradas:

Passo 4: Os dois objetos mais semelhantes, A e B, são agrupados e o valor do centróide é recalculado. O conjunto é novamente reduzido em uma unidade.

Passo 5: As novas distâncias são calculadas.

Passo 6: Como ocorreu um empate, já que d(4.5, 1) = d(4.5, 8), a escolha dos elementos a serem unidos dependerá do método de formação escolhido, supomos ser  CD e  E os escolhidos. O conjunto que inicialmente possuía 5  agrupamentos, possui agora apenas dois, um formado pelos elementos {C, D, E} e outro formado pelos elementos {A, B). No próximo passo, o conjunto de elementos estará todo em um único agrupamento.

A  Figura a seguir mostra o fluxo de execução para o exemplo apresentado. O quadrado destacado  representa cada novo grupo formado. As linhas  contínuas representam as medidas de distância calculadas no primeiro passo. As linhas  tracejadas  representam as medidas calculadas no segundo passo. As medidas de distância dos demais passos não foram representadas para não “poluir” a imagem. Observando-se estas linhas, é possível  ver claramente que o número de medidas de distância diminui significativamente a cada passo do processo.

Para completar o post anterior, segue o Algoritmo de k-means em Portugol:

Especifique k;

Selecione os k objetos que serão os centróides dos agrupamentos;

para todos os objetos restantes faça

Calcule a distância entre o elemento e os centróides;

Adicione o elemento ao agrupamento que possuir a menor distância;

Recalcule o centróide do agrupamento;

fim para

para todos os k agrupamentos faça 

Calcule a Soma de Quadrados Residual;

fim para 

repita

para todos os n elementos faça

Mova o elemento para os outros agrupamentos;

Recalcule a Soma de Quadrados Residual;

se soma dos Quadrados Residual diminuiu então

O objeto passa a fazer parte do agrupamento que produzir maior ganho;

Recalcule a Soma de Quadrados Residual dos agrupamentos alterados;

fim se

fim para

até Número de interações = i ou Não ocorra mudança de objetos