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).

Os métodos de Cluster Analysis baseados em grades dividem o espaço de objetos em um certo número de células. Estas por sua vez são divididas em outras e assim sucessivamente, formando diferentes níveis de resolução. É através destas células que os objetos são  agrupados. Desta forma, tem-se uma estrutura hierárquica que pode ser observada na figura abaixo.

A principal vantagem destes métodos é que sua velocidade depende apenas da resolução da grade (onde os dados são plotados) e não do tamanho da base de dados. Por causa disto, são apropriados para base de dados com grande densidade, ou seja, com um número muito grande de objetos num espaço limitado.

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.

Como o próprio nome sugere, o método hierárquico divisivo é exatamente o oposto do método hierárquico aglomerativo apresentado no post anterior, ou seja, inicialmente os n objetos são considerados como sendo um único agrupamento. A cada passo, através de sucessivas divisões, vão sendo obtidos 2, 3, …, n agrupamentos.

Os métodos divisivos tendem a ser menos utilizados que os métodos aglomerativos, pois não conseguem recuperar facilmente uma partição feita por uma má escolha. Maiores informações sobre os métodos divisivos podem ser encontradas em MICHAUD (1997).