TwoStep Cluster: Análise comparativa do algoritmo e proposta de melhoramento da medida de verossimilhança

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

TwoStep Cluster: Análise comparativa do algoritmo e proposta de melhoramento da medida de verossimilhança Rafael Leão Brazão, Pedro A. Barbetta, Dalton F. Andrade Departamento de Informática e Estatística – Universidade Federal de Santa Catarina (UFSC) Campus Universitário – Trindade – Florianópolis – SC – Brazil {brazaor,barbetta,dandrade}@inf.ufsc.br

Abstract. In this paper we made comparisons of the algorithm TwoStep Cluster (TSC) with other clustering algorithms for large databases. The comparisons were made using simulated data, whose variations of the parameters were made in according to the Design of Experiments methodology. The results showed that TSC had better accuracy when the clusters had different variances; however it was shown to be slower than the traditional K-means algorithm. In this work we also propose an improvement in the measure of the log-likelihood considered in the algorithm. It allows incorporating information about the correlations between the variables. Resumo. Neste artigo foram feitas comparações do algoritmo TwoStep Cluster (TSC) com outros algoritmos de agrupamentos para grandes bases de dados. As comparações foram realizadas utilizando dados simulados, cujas variações dos parâmetros foram feitas de acordo com a metodologia de Planejamento de Experimentos. Os resultados mostraram que o TSC teve melhor acurácia quando os grupos tinham diferentes variâncias, no entanto se mostrou mais lento que o tradicional algoritmo K-médias. Neste artigo também foi proposto um melhoramento à medida de log da verossimilhança utilizada no TSC, permitindo a incorporação de informação sobre as correlações entre as variáveis.

1. Introdução O algoritmo TwoStep Cluster (TSC) (Chiu et al., 2001) (SPSS, 2001) é um melhoramento do BIRCH (Balanced Iterative Reducing and Clustering using Hierarquies) (Zhang, 1997) e tem um grande apelo por ser capaz de reduzir um grande arquivo de dados, lido em seqüência, em pré-agrupamentos que contêm estatísticas sobre os registros da base de dados. Outra vantagem deste algoritmo é possibilitar o uso de variáveis quantitativas e categóricas, além de encontrar um número apropriado de agrupamentos, caso este número não seja fornecido previamente à execução do algoritmo. Os estudos comparativos para avaliar a acurácia e o tempo de processamento dos algoritmos de agrupamentos têm sido feitos utilizando simulação Monte Carlo. Zhang et al. (1996) e Zhang (1997) realizaram vários testes com o algoritmo BIRCH. Um estudo comparativo mais elaborado entre vários métodos de agrupamentos foi realizado por Mingoti e Lima (2006), onde foram geradas amostras com diferentes números de 13

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

grupos, quantidade de variáveis, nível de correlação entre as variáveis, nível de superposição entre grupos e presença ou não de registros discrepantes, mas esse estudo não incluía o BIRCH ou o TSC. Prass (2004) realizou simulações com alguns algoritmos de agrupamentos disponíveis na linguagem R. O resultado dessas simulações apontou que os algoritmos de partição foram melhores em grandes bases de dados e, por este motivo, dois algoritmos de partição, o CLARA (Clustering Large Applications) proposto por Kaufman e Rousseeuw (2005), e o K-médias, proposto em MacQueen (1967), foram escolhidos para comparações com o TSC. Pretende-se, neste artigo, usar a Metodologia de Planejamento de Experimentos na comparação dos algoritmos e mostrar como é possível incorporar correlação entre as variáveis no TSC, possibilitando um melhoramento na identificação dos agrupamentos.

2. TwoStep Cluster (TSC) O algoritmo TSC baseia-se no algoritmo BIRCH (Zhang et al., 1996), que consiste, inicialmente, em criar uma árvore, a CF-tree, gerando pré-agrupamentos,. O TSC utiliza a distância log da verossimilhança, proposta em Banfield and Raftery (1993), acomodando adequadamente variáveis quantitativas e categóricas. Considere uma base de dados com Q + C variáveis (Q quantitativas e C categóricas) e N registros divididos em K clusters ou grupos: G1, G2, ..., GK. Seja o grupo Gk com Nk registros. Para o conjunto das Q variáveis quantitativas, o valor máximo da função de logverossimilhança é dado por: ∧ (Q ) Q N (1) l k = − k [ Q {log( 2 π ) + 1} + ∑ log( σˆ 2 )] 2

j =1

kj

sendo σˆ kj2 a estimativa de máxima verossimilhança da variância da j-ésima variável, no cluster Gk. E para o conjunto das C variáveis categóricas: ∧ (C ) lk

C Mj

= N k ∑ ∑ pˆ kjm log( pˆ kjm )

(2)

j =1 m =1

sendo pˆ kjm a proporção de observações da categoria m da j-ésima variável categórica, no k-ésimo grupo. E o valor máximo da função de log-verossimilhança, associada a todas as variáveis, no grupo Gk, é dado por: ∧

∧ (Q ) ∧ (C ) k =lk +lk

l (3) A distância entre dois agrupamentos é baseada na redução no log da verossimilhança pela união dos dois agrupamentos. Assim, para o cálculo dessa distância, basta se ter armazenado, para cada agrupamento, o vetor CF (Cluster Feature):

r r r r CFk = ( N k , SLk , SQk , Pk ) (4) r S L onde Nk é o número de registros do agrupamento k; k é um vetor cujos elementos são formados pelas somas dos valores de cada variável quantitativa;

SQ k

é um vetor r formado pelas somas dos quadrados dos valores das variáveis quantitativas; e Pk é um

14

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

vetor cujos elementos são as proporções de ocorrências de cada categoria, em cada variável categórica. A primeira etapa do algoritmo é a construção de uma árvore: a CF-tree. Realizada a primeira etapa, uma coleção de pré-agrupamentos, sintetizados por CFs, é armazenada nos nós folhas da CF-tree. Na segunda etapa, é utilizado um algoritmo hierárquico aglomerativo para se encontrar os agrupamentos finais.

3. Planejamento do experimento Para avaliar o tempo de processamento e, principalmente, a qualidade dos resultados gerados pelos algoritmos de agrupamentos (ou acurácia), foi realizado um experimento em que os registros foram gerados segundo distribuições de probabilidades (simulação tipo Monte Carlo). Em cada simulação, os subgrupos de registros gerados por uma dada distribuição de probabilidade, com parâmetros estabelecidos, foram assumidos como pertencentes a um agrupamento verdadeiro. A acurácia de um dado algoritmo de agrupamento foi avaliada pela porcentagem de registros gerados por uma dada distribuição de probabilidades que ficaram num mesmo agrupamento. Para gerar casos com distribuições multivariadas foi usada a metodologia de cópulas, que permite agregar distribuições univariadas em distribuições multivariadas, considerando determinada correlação entre as variáveis (Andrade et al, 2006; Anjos et al., 2004). Em especial, foi utilizada a cópula gaussiana que, no caso de L distribuições normais univariadas, gera a normal multivariada L-dimensional (Song, 2000). As cópulas também aceitam diferentes distribuições univariadas, formando uma nova distribuição multivariada com determinada dependência entre as variáveis. Para a geração das amostras foi utilizada a ferramenta de cópulas da linguagem livre R. As bases de dados foram simuladas com variações planejadas do número de registros, quantidade de variáveis, quantidade de grupos, presença ou não de variáveis categóricas, correlação nula ou não-nula entre as variáveis, distribuição geradora dos dados (normal ou gama) e variâncias iguais ou diferentes entre os grupos. Observa-se que características dos dados e variáveis são importantes na comparação dos algoritmos, porque algumas delas violam suposições intrínsecas de uma ou outra técnica. Por exemplo, dados com grupos de variâncias diferentes violam suposições do K-médias, mas são pertinentes de serem analisados (minerados) pelo TSC. Já correlações não-nulas entre as variáveis, ou variáveis com distribuições assimétricas são características indesejáveis para os três algoritmos em estudo. A Tabela 1 mostra os níveis (ou categorias) estudados (as) dos sete fatores de interesse. Com o objetivo de comparar os algoritmos de agrupamento e verificar o efeito de cada fator nesses algoritmos, as simulações foram feitas segundo a Metodologia de Planejamento de Experimentos (Montgomery, 2005), considerando um projeto (design) fatorial fracionário do tipo 27-3. Este projeto é composto de dezesseis condições experimentais (combinações de níveis dos fatores da Tabela 1), balanceadas de tal forma que é possível realizar a avaliação do efeito de cada fator isoladamente – o que geralmente não tem sido feito nos trabalhos correlatos. As combinações de níveis dos fatores (design points) são apresentadas na Tabela 2.

15

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

Tabela 1. Níveis dos fatores do experimento Fatores

Níveis -1

+1

dez mil

um milhão

2 - quantidade de variáveis

2

10

3 - número de agrupamentos

2

10

Ausência

50% do tipo 0-1

normal

gama

1 - número de registros

4 - variáveis categóricas 5 - distribuição das variáveis quantitativas 6 - correlação entre as variáveis

0

0,7

7 - variâncias nos agrupamentos

iguais

diferentes

Os dados foram gerados pela normal ou gama, mas sempre com valor esperado 3,4142 e variância unitária. Para que as bases de dados tivessem diferentes grupos com variâncias iguais foram adicionadas constantes aos valores gerados de variáveis aleatórias (o que só altera a média). Para os ensaios que exigiam variâncias diferentes, os valores das variáveis aleatórias também foram multiplicados por constantes, escolhidas de tal forma que o desvio padrão ficasse sempre proporcional à média. As variáveis do tipo 0-1 foram construídas recodificando os valores gerados por distribuições contínuas. Tabela 2. Condições experimentais efetivamente realizadas, baseadas no projeto 27-3 Ensaio 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Número de registros dez mil dez mil um milhão dez mil um milhão um milhão dez mil dez mil um milhão um milhão dez mil dez mil um milhão um milhão um milhão dez mil

Número de variáveis 10 10 2 10 2 10 2 10 10 10 2 2 2 10 2 2

Número de grupos 2 10 10 10 2 2 10 2 10 10 2 2 2 2 10 10

Variáveis categóricas 50% 0 0 50% 50% 50% 0 0 50% 0 0 50% 0 0 50% 50%

Correlação 0,7 0 0 0 0,7 0 0,7 0,7 0,7 0,7 0 0 0,7 0 0 0,7

Distribuição dos dados normal normal gama gama gama normal gama gama gama normal normal gama normal gama normal normal

Variâncias diferentes diferentes iguais iguais iguais iguais diferentes iguais diferentes iguais iguais diferentes diferentes diferentes diferentes iguais

4. Resultados Foi usada a implementação do TSC do SPSS®, versão 14, e a implementação do CLARA da linguagem R, versão 2.4.1, disponível em http://www.r-project.org. O Kmédias foi rodado tanto no SPSS quanto no R. Para todos os algoritmos foi fornecido o número correto de agrupamentos. A Tabela 3 apresenta a acurácia (porcentagem de casos agrupados corretamente) em cada uma das dezesseis bases de dados geradas. No caso das bases de dez mil registros, o experimento foi feito em triplicata; e os valores apresentados na Tabela 3 referentes aos ensaios 1, 2, 4, 7, 8, 11, 12 e 16 correspondem às médias dos resultados dessas triplicatas. Observa-se na Tabela 3 que, em média, o TSC obteve a melhor acurácia, seguido do CLARA e, por último, o K-médias. Mas isto não aconteceu em todas as bases de dados. A Figura 1 mostra um detalhamento da análise dos resultados, onde se visualiza o efeito de cada fator em estudo.

16

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

Tabela 3. Porcentagem de casos agrupados corretamente Ensaio 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Média:

TSC 83,20 79,71 96,07 42,55 93,27 90,96 96,22 91,41 40,62 53,37 93,11 88,61 77,88 98,95 58,02 70,77 78,42

Algoritmo K-médiasSPSS K-médiasR 62,60 61,02 57,03 70,86 83,72 85,02 69,57 73,66 69,80 70,49 98,80 98,80 78,77 76,63 96,94 96,96 37,03 40,57 52,18 60,83 94,33 94,31 71,23 71,47 82,98 82,97 99,03 99,03 54,43 51,65 57,79 55,73 72,89 74,38

CLARA 78,80 48,79 94,19 61,55 83,62 97,63 94,99 97,64 39,88 65,36 93,67 89,56 83,16 94,72 54,12 58,29 77,25

90.0

A c u r á c ia(% )

85.0

TSC_SPSS

80.0

K-médias_SPSS

75.0 70.0

K-médias_R

65.0

Clara_R

60.0 dez mil

um milhao

90.0

90.0

85.0

85.0 Acurácia (%)

Acurácia (%)

quantidade de r e gis tr os

80.0 75.0 70.0 65.0

80.0 75.0 70.0 65.0

60.0

60.0 duas

dez

dois

dez quantidade de grupos

90.0

90.0

85.0

85.0 Acurácia (%)

Acurácia (%)

quantidade de variáveis

80.0 75.0 70.0 65.0

80.0 75.0 70.0 65.0

60.0

60.0 ausentes

presentes

não-correlacionadas

correlacionadas

Correlação entre variáveis

90.0

90.0

85.0

85.0 Acurácia (%)

Acurácia (%)

variáveis categóricas

80.0 75.0 70.0 65.0

80.0 75.0 70.0 65.0

60.0

60.0 normal

gama

iguais

Distribuição dos dados

diferentes Variâncias

Figura 1. Porcentagem média de casos agrupados corretamente, por algoritmo e por característica da base de dados.

17

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

A Figura 1 mostra que a mudança no número de registros (tamanho das amostras) e no número de grupos praticamente não altera a análise comparativa entre os algoritmos. Mas em termos do número de variáveis, observa-se que o TSC e o CLARA têm acurácias relativamente melhores para duas variáveis, mas com dez variáveis os resultados são praticamente iguais ao K-médias. Na presença de variáveis categóricas o TSC e CLARA se apresentam um pouco melhor que o K-médias, já na presença de correlações não-nulas eles têm acurácia bem melhor que o K-médias. Para dados com distribuição normal o TSC é o melhor, enquanto que para dados com distribuição gama (assimétrica) o CLARA cresce em acurácia comparativamente aos outros. O resultado mais expressivo ocorre quando os grupos têm variâncias diferentes. Neste caso o TSC tem a melhor acurácia e o K-médias perde drasticamente em relação aos outros. Os resultados da mudança dos dois últimos fatores (distribuição e variância) têm relação direta com o algoritmo TSC, pois ele se baseia na função de verossimilhança da distribuição normal com variâncias diferentes entre grupos. A Tabela 4 apresenta a média do tempo de processamento nos dezesseis ensaios do experimento realizado. Observa-se que os algoritmos executados na linguagem R foram bem mais rápidos do que os algoritmos executados no SPSS®. Isso deve ter ocorrido por mecanismos internos de cada um dos programas. Restringindo-se aos resultados do SPSS®, verifica-se que o tempo de processamento do TSC foi bem maior do que o K-médias, porém o percentual de aumento do tempo quando se aumenta o número de registros é menor no TSC do que no K-médias. Assim, estes resultados são parcialmente compatíveis com SPSS (2001) e Chiu et al. (2001), que apontam a escalabilidade como uma vantagem do TSC. Tabela 4. Média do tempo de processamento (s). Algoritmo TSC

K-médiasSPSS

K-médiasR

CLARA

65,28

17,67

7,21

3,56

5. Melhoramento no TSC Uma deficiência na maioria dos algoritmos de agrupamento é que eles não consideram a correlação entre as variáveis de entrada. A Figura 2 mostra a importância de se considerar a correlação entre as variáveis de entrada. Observe que o ponto P (um registro em uma base de dados) está mais próximo do agrupamento G2 do que do agrupamento G1 (em termos da distância euclidiana), mas se considerarmos uma possível correlação positiva entre as variáveis X1 e X2, então o ponto P está mais próximo de G1 do que de G2 (a distância de Mahalanobis). X2

P

x o

o

G2

G1

X

Figura 2. Representação da distribuição das curvas de nível de dois agrupamentos

18

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

Considerando os dados de Q variáveis quantitativas relativas ao k-ésimo agrupamento e supondo distribuição normal multivariada, o valor máximo da função de log da verossimilhança pode ser escrito como (baseado nos resultados descritos em Johnson e Wichern , 2002): Q N Lˆ k = − k [ Q {log( 2π ) + 1} + ∑ log(| Σˆ kj |)] 2 j =1

(5)

ˆ Σ

onde kj é a estimativa máxima de verossimilhança das matrizes de variância e covariância, com os elementos dados por:  Nk

Nk

 N k



σˆ (jlk ) = N k ∑ x (jik ) xli( k ) − ∑ x (jik )  ∑ xli( k ) 

(6)  i =1  i =1  Considerando as correlações positivas entre as variáveis quantitativas, a distância de log da verossimilhança entre os agrupamentos t e s é: i =1

d (t , s) = Bt + Bs − B< t , s > com:

Bv = − N v {

C M j 1 Q ∑ log(| Σˆ vj |) − ∑ ∑ pˆ vjm log( pˆ vjm )} 2 j =1 j =1m =1

(7) (8)

onde ν pode representar s, t ou os dois grupos unidos: . Assim, para incorporar as correlações, os CFs devem incluir um vetor de dimensão Q(Q − 1) 2 , representado por SP, cujos elementos são as somas dos produtos das variáveis quantitativas. Para o agrupamento k: r r r r r CFk* = ( N k , SLk , SQk , SPk , Pk ) (9) As modificações sugeridas na distância de log da verossimilhança podem aumentar consideravelmente o tempo de processamento, porque a cada etapa seria necessário calcular as variâncias e covariâncias, além de calcular o determinante de uma matriz. As covariâncias podem ser mal estimadas quando o número de registros em um agrupamento em formação for pequeno. A nossa proposta é que a distância definida em (7) e (8) seja adotada somente na segunda etapa do algoritmo: a construção dos agrupamentos baseada nos pré-agrupamentos. Dessa forma, o aumento no tempo de processamento deverá ser pequeno e o algoritmo permitirá a formação de agrupamentos em forma elipsóide, unindo registros em agrupamentos de maneira mais confiável.

6. Considerações Finais Foram feitas comparações do TSC com os algoritmos K-médias e CLARA, onde se observou que o TSC tem melhor acurácia que os outros algoritmos. A vantagem do TSC aumenta quando se têm poucas variáveis e estas têm variâncias bem diferentes nos agrupamentos; no entanto, o TSC foi mais lento. Uma modificação foi proposta na medida de distância do log da verossimilhança para o TSC, que permite incorporar a correlação entre variáveis quantitativas. Como trabalho futuro, pretende-se implementar no TSC a medida de distância proposta e avaliar a escalabilidade e acurácia do algoritmo modificado.

19

WAAMD 2007

III Workshop em Algoritmos e Aplicações de Mineração de Dados

7. Referências bibliográficas Andrade, D. F.; Barbetta; P. A.; Freitas, P. J.; Zunino, N. A. M. e Jacinto, C. M. C. Using copulas in risk analysis. 2006 Winter Simulation Conference. 2006. Anjos, U.U., Ferreira, F.H., Kolev, N.V., Mendes, B.V.M. Modelando Dependências via Cópulas. São Paulo: Associação Brasileira de Estatística, 2004. Banfield J. D.; Raftery, A. E.. Model-based Gaussian and non-Gaussian clustering, 1993. Biometrics, 49. p. 803–821; Chiu, Tom; Fang, DongPing; Chen, John; Wang, Yao; Jeris, Christopher. A robust and scalable clustering algorithm for mixed type attributes in large database environment. Nos anais de ACM KDD 01, 2001. Pages 263-268, São Francisco, Califórnia. Johnson, R. A.; Wichern, D. W. Applied Multivariate Statistical Analysis. Fifth Edition. Prentice Hall, 2002. Kaufman, Leonard; Rousseeuw, Peter. Finding Groups in Data – An Introduction to Cluster Analysis. John Wiley & Sons, 2005. MacQueen, J. B. Some Methods for Classification and Analysis of Multivariate Observations. Nos anais do 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967 p. 281-297. Montgomery, Douglas C. Design and Analysis of Experiments. Sixth Edition. John Wiley & Sons, 2005. Prass, F. S. Um estudo comparativo entre algoritmos de Análise de Agrupamentos em mineração de dados. Dissertação de mestrado - UFSC. Florianópolis, 2004. Song, Xue-Kun P. Multivariate dispersion models generated from gaussian copula. Scandinavian Journal of Statistics v. 27, p. 305-330, 2000. Mingoti, Sueli A. e Lima, Joab O.. Comparing SOM neural network with Fuzzy cmeans, K-means and traditional hierarchical clustering algorithms European Journal of Operational Research, Volume 174, Issue 3, 1 November pp. 1742-1759, 2006. The SPSS TwoStep Cluster Component – A scalable component enabling more efficient customer segmentation. White paper – technical report. USA, 2001. Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron. Birch: an efficient data clustering method for very large databases. Nos anais de ACM SIGMOD Conference on Management of Data, Montreal, Canada, 1996. Zhang, Tian. Data clustering for very large datasets plus applications. Tese de doutorado. University of Wisconsin-Madison, 1997.

20