ads:
Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica
Programa de P´os Gradua¸c˜ao em Modelagem Computacional
An´alise de algoritmos de agrupamento para base de
dados textuais
Por
Luiz Gonzaga Paula de Almeida
PETR
´
OPOLIS, RJ - BRASIL
OUTUBRO DE 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
AN
´
ALISE DE ALGORITMOS DE AGRUPAMENTO PARA BASE
DE DADOS TEXTUAIS
Luiz Gonzaga Paula de Almeida
DISSERTA¸C
˜
AO SUBMETIDA AO CORPO DOCENTE DO LABORAT
´
ORIO
NACIONAL DE COMPUTA ¸C
˜
AO CIENT
´
IFICA COMO PARTE DOS REQUI-
SITOS NECESS
´
ARIOS PARA A OBTEN ¸C
˜
AO DO GRAU DE MESTRE EM
MODELAGEM COMPUTACIONAL
Aprovada por:
Prof. Ana Tereza Ribeiro de Vasconcelos, D.Sc -
LNCC
(Presidente)
Prof. Marco Antonio Grivet Mattoso Maia, Ph.D. -
PUC/RJ
Prof. Jack Baczynski, D.Sc. - LNCC
Prof. Alexandre Plastino de Carvalho, D.Sc. - UFF
PETR
´
OPOLIS, RJ - BRASIL
OUTUBRO DE 2007
ads:
Almeida, Luiz Gonzaga Paula de
A447a An´alise de algoritmos de agrupamento para base de dados textuais /
Luiz Gonzaga Paula de Almeida. Petrop´olis, RJ. : Laborat´orio Nacional de
Computa¸c˜ao Cient´ıfica, 2007.
xxii, 139 p. : il.; 29 cm
Orientadore(s): Ana Tereza Ribeiro de Vasconcelos e Marco Antonio Grivet
Mattoso Maia
Disserta¸c˜ao (M.Sc.) – Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica,
2007.
1. An´alise por agrupamento. 2. Sele¸c˜ao de caracter´ısticas. 3. Minera¸c˜ao
de textos. I. Vasconcelos, Ana Tereza Ribeiro de. II. LNCC/MCT. III. T´ıtulo.
CDD 519.53
Ao vencedor, as batatas (Machado de Assis)
iv
Aos meus pais e `a Gisele.
v
Agradecimentos
Agrade¸co `a Gisele, por todo o apoio, compreens˜ao e pelo amor que compar-
tilhamos.
Agrade¸co `as minhas queridas amigas Elo´a, Giovˆania, Lena, Miriam e ao
amigo Bidu, pelo est´ımulo e apoio para enfrentar este desafio.
Aos meus colegas do Laborat´orio de Bioinform´atica e do mestrado, pela
ajuda dada em v´arios momentos.
Aos meus orientadores, Ana Tereza e Marco Grivet, pela inestim´avel ajuda,
apoio e compreens˜ao no desenvolvimento deste trabalho.
Ao Professor Darcy Fontoura, que com o seu entusiasmo p ermanente, con-
tagia a todos que compartilham de sua presen¸ca.
Ao Laborat´orio Nacional de Computa¸c˜ao Cient´ıfica, pelo apoio e suporte
dado a este trabalho.
vi
Resumo da Disserta¸c˜ao apresentada ao LNCC/MCT como parte dos requisitos
necess´arios para a obten¸c˜ao do grau de Mestre em Ciˆencias (M.Sc.)
AN
´
ALISE DE ALGORITMOS DE AGRUPAMENTO PARA BASE
DE DADOS TEXTUAIS
Luiz Gonzaga Paula de Almeida
Outubro , 2007
Orientador: Ana Tereza Ribeiro de Vasconcelos, D.Sc - LNCC
Co-orientador: Marco Antonio Grivet Mattoso Maia, Ph.D. - PUC/RJ
O volume crescente de textos digitalmente armazenados torna necess´aria a
constru¸c˜ao de ferramentas computacionais que permitam a organiza¸c˜ao e o acesso
eficaz e eficiente `a informa¸c˜ao e ao conhecimento nele contidos. No campo do co-
nhecimento da biomedicina este problema se torna extremamente relevante, pois a
maior parte do conhecimento gerado ´e formalizada atrav´es de artigos cient´ıficos e
´e necess´ario que o acesso a estes seja o mais f´acil e r´apido poss´ıvel.
A ´area de pesquisa conhecida como Minera¸c˜ao de Textos (do inglˆes Text
Mining), se prop˜oe a enfrentar este problema ao procurar identificar novas in-
forma¸c˜oes e conhecimentos at´e ent˜ao desconhecidos, em bases de dados textuais.
Uma de suas tarefas ´e a descoberta de grupos de textos correlatos em base de dados
textuais e esse problema ´e conhecido como agrupamento de textos (do inglˆes Text
Clustering). Para este fim, a representa¸c˜ao das bases de dados textuais comumente
utilizada no agrupamento de textos ´e o Modelo Espa¸co-vetorial, no qual cada texto
´e representado por um vetor de caracter´ısticas, que s˜ao as freq
¨
uˆencias das palavras
ou termos que nele ocorrem. O conjunto de vetores forma uma matriz denominada
de documento-termo, que ´e esparsa e de alta dimensionalidade. Para atenuar os
problemas decorrentes dessas caracter´ısticas, normalmente ´e selecionado um sub-
vii
conjunto de termos, construindo-se assim uma nova matriz documento-termo com
um n´umero reduzido de dimens˜oes que ´e ent˜ao utilizada nos algoritmos de agru-
pamento.
Este trabalho se desdobra em: i) introdu¸c˜ao e implementa¸c˜ao de dois algo-
ritmos para sele¸c˜ao de termos e ii) avalia¸c˜ao dos algoritmos k-means, espectral e
de particionamento de grafos, em cinco base de dados de textos previamente clas-
sificadas. As bases de dados s˜ao pr´e-processadas atrav´es de m´etodos descritos na
literatura, produzindo-se as matrizes documento-termo. Os resultados indicam que
os algoritmos de sele¸c˜ao propostos, para a redu¸c˜ao das matrizes documento-termo,
melhoram o desempenho dos algoritmos de agrupamento avaliados. Os algoritmos
k-means e espectral tˆem um desempenho superior ao algoritmos de particiona-
mento de grafos no agrupamento de bases de dados textuais, com ou sem a sele¸c˜ao
de caracter´ısticas.
viii
Abstract of Dissertation presented to LNCC/MCT as a partial fulfillment of the
requirements for the degree of Master of Sciences (M.Sc.)
ANALYSIS OF THE CLUSTERING ALGORITHMS FOR TEXT
DATABASES
Luiz Gonzaga Paula de Almeida
October, 2007
Advisor: Ana Tereza Ribeiro de Vasconcelos, D.Sc - LNCC
Co-advisor: Marco Antonio Grivet Mattoso Maia, Ph.D. - PUC/RJ
The increasing amount of digitally stored texts makes necessary the develop-
ment of computational tools to allow the access of information and knowledge in
an efficient and efficacious manner. This problem is extremely relevant in biome-
dicine research, since most of the generated knowledge is translated into scientific
articles and it is necessary to have the most easy and fast access.
The research field known as Text Mining deals with the problem of iden-
tifying new information and knowledge in text databases. One of its tasks is to
find in databases groups of texts that are correlated, an issue known as text cluste-
ring. To allow clustering, text databases must b e transformed into the commonly
used Vector Space Model, in which texts are represented by vectors composed by
the frequency of occurrence of words and terms present in the databases. The set
of vectors composing a matrix named document-term is usually sparse with high
dimension. Normally, to attenuate the problems caused by these features, a subset
of terms is selected, thus giving rise a new document-term matrix with reduced
dimensions, which is then used by clustering algorithms.
This work presents two algorithms for terms selection and the evaluation of
ix
clustering algorithms: k-means, spectral and graph portioning, in five pre-classified
databases. The databases were pre-processed by previously described methods.
The results indicate that the term selection algorithms implemented increased the
performance of the clustering algorithms used and that the k-means and spectral
algorithms outperformed the graph portioning.
x
Sum´ario
1 Introdu¸c˜ao 1
1.1 Motiva¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Contexto de aplica¸c˜ao da pesquisa realizada . . . . . . . . . . . . . 3
1.3 Trabalhos relacionados . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Contribui¸c˜oes deste trabalho . . . . . . . . . . . . . . . . . . . . . . 17
1.5 Organiza¸c˜ao da disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . 17
2 Prepara¸c˜ao dos Dados 19
2.1 Pr´e-processamento . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1.1 Segmenta¸c˜ao do texto . . . . . . . . . . . . . . . . . . . . . 22
2.1.2 Exclus˜ao de termos . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Remo¸c˜ao dos sufixos das palavras . . . . . . . . . . . . . . . 24
2.1.4 Implementa¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Sele¸c˜ao de caracter´ısticas . . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.1 Pondera¸c˜ao da importˆancia dos termos . . . . . . . . . . . . 29
2.2.2 Medidas da importˆancia dos termos . . . . . . . . . . . . . . 31
2.2.3 Algoritmos de sele¸c˜ao de caracter´ısticas . . . . . . . . . . . . 35
3 T´ecnicas de agrupamento de dados 40
3.1 Medidas de similaridade . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Algoritmos para agrupamento de dados . . . . . . . . . . . . . . . . 43
3.2.1 Algoritmo K-means . . . . . . . . . . . . . . . . . . . . . . . 47
xi
3.2.2 Algoritmos de particionamento kernel k-means e kernel k-
means ponderado . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2.3 Algoritmos de agrupamento espectral . . . . . . . . . . . . . 52
3.2.4 Algoritmos de particionamento de grafos . . . . . . . . . . . 55
3.3 Medidas de avalia¸c˜ao da qualidade do agrupamento . . . . . . . . . 60
3.3.1 Medidas Externas . . . . . . . . . . . . . . . . . . . . . . . . 61
3.3.2 Medidas Internas . . . . . . . . . . . . . . . . . . . . . . . . 65
4 Resultados 70
4.1 Descri¸c˜ao das bases de dados . . . . . . . . . . . . . . . . . . . . . . 70
4.1.1 Avalia¸c˜ao das bases de documentos . . . . . . . . . . . . . . 73
4.2 Ferramentas computacionais desenvolvidas . . . . . . . . . . . . . . 77
4.3 An´alise Qualitativa do Desempenho com Sele¸c˜ao de Caracter´ısticas 80
4.4 Descri¸c˜ao dos testes e resultados . . . . . . . . . . . . . . . . . . . . 85
4.4.1 Escolha de medida de distˆancia . . . . . . . . . . . . . . . . 86
4.4.2 Algoritmo k-means . . . . . . . . . . . . . . . . . . . . . . . 87
4.4.3 Algoritmo espectral . . . . . . . . . . . . . . . . . . . . . . . 94
4.4.4 Algoritmo de particionamento de grafos - Associa¸c˜ao ponde-
rada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4.5 Algoritmo de particionamento de grafos - Corte ponderado . 105
4.4.6 Algoritmo de particionamento de grafos - Associa¸c˜ao norma-
lizada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.5 Discuss˜ao dos resultados . . . . . . . . . . . . . . . . . . . . . . . . 111
5 Conclus˜oes 118
6 Perspectivas Futuras 120
xii
Referˆencias Bibliogr´aficas 121
Apˆendice
A 135
A.1 Exemplo de pr´e-processamento . . . . . . . . . . . . . . . . . . . . 135
B 137
B.1 Medidas de qualidade na escolha do parˆametro σ do algoritmo de
agrupamento esp ectral . . . . . . . . . . . . . . . . . . . . . . . . . 137
xiii
Lista de Figuras
Figura
1.1 Crescimento do n ´umero de artigos cient´ıficos publicados sobre ant´ı-
genos cancer testis . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Diagrama do Sistema para Anota¸c˜ao de Ant´ıgenos Cancer Testis . 6
1.3 Diagrama do m´odulo de recupera¸c˜ao de informa¸c˜oes textuais do
Sistema para Anota¸c˜ao de Ant´ıgenos Cancer Testis . . . . . . . . . 7
1.4 Tela com os resultados do agrupamento de uma consulta no Car-
rot.
`
A esquerda s˜ao mostrados os grupos descobertos e `a direita os
endere¸cos das p´aginas pertencentes ao grupo selecionado . . . . . . 9
3.1 Exemplo de um conjunto de dados com duas dimens˜oes e diferentes
densidades de distribui¸c˜ao dos pontos. As ´areas cinzas cont´em uma
alta densidade de pontos . . . . . . . . . . . . . . . . . . . . . . . . 46
3.2 No eixo x o valor do Coeficiente de Silhueta. No eixo y cada linha
corresponde a cada objeto alocado a cada grupo . . . . . . . . . . . 66
4.1 Matriz de afinidades da base de documentos R01. 5666 termos. . . . 74
4.2 Matriz de afinidades da base de documentos R02. 7735 termos. . . . 75
4.3 Matriz de afinidades da base de documentos R03. 6316 termos. . . . 76
4.4 Matriz de afinidades da base de documentos R04. 3572 termos. . . . 77
4.5 Matriz de afinidades da base de documentos S01. 7272 termos. . . . 77
4.6 Matriz de afinidades da base R01. 58 termos. . . . . . . . . . . . . 81
4.7 Matriz de afinidades da base R01. 38 termos (sele¸c˜ao iterativa). . . 82
4.8 Matriz de afinidades da base R02. 169 termos. . . . . . . . . . . . . 83
xiv
4.9 Matriz de afinidades da base R02. 83 termos (sele¸c˜ao iterativa). . . 83
4.10 Matriz de afinidades da base R03. 185 termos . . . . . . . . . . . . 84
4.11 Matriz de afinidades da base R03. 55 termos (sele¸c˜ao iterativa). . . 84
4.12 Matriz de afinidades da base R04. 28 termos. . . . . . . . . . . . . 84
4.13 Matriz de afinidades da base R04. 33 termos (sele¸c˜ao iterativa). . . 84
4.14 Matriz de afinidades da base S01. 99 termos. . . . . . . . . . . . . . 85
4.15 Matriz de afinidades da base S01. 116 termos (sele¸c˜ao iterativa). . . 85
A.1 Texto original . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
A.2 Texto com todas as letras transformadas em min´usculas . . . . . . . 136
A.3 Texto sem n´umeros . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
A.4 Texto sem palavras sem valor informacional (to, the,for etc) . . . . 136
A.5 Texto ap´os a retirada dos sufixos das palavras e sem caracteres gr´aficos136
B.1 Medidas de qualidade do agrupamento (R01). 38 termos (sele¸c˜ao
iterativa). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
137
B.2 Medidas de qualidade do agrupamento (R01). 58 termos. . . . . . . 137
B.3 Medidas de qualidade do agrupamento (R01). 5666 termos. . . . . . 137
B.4 Medidas de qualidade do agrupamento (R02). 83 termos (sele¸c˜ao
iterativa). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
B.5 Medidas de qualidade do agrupamento (R02). 169 termos. . . . . . 138
B.6 Medidas de qualidade do agrupamento (R02). 7735 termos. . . . . . 138
B.7 Medidas de qualidade do agrupamento (R03). 55 termos (sele¸c˜ao
iterativa) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
B.8 Medidas de qualidade do agrupamento (R03). 185 termos. . . . . . 138
B.9 Medidas de qualidade do agrupamento (R03). 6316 termos. . . . . . 138
B.10 Medidas de qualidade do agrupamento (R04). 33 termos (sele¸c˜ao
iterativa) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
B.11 Medidas de qualidade do agrupamento (R04). 28 termos. . . . . . . 139
B.12 Medidas de qualidade do agrupamento (R04). 3572 termos. . . . . . 139
xv
B.13 Medidas de qualidade do agrupamento (S01). 116 termos (sele¸c˜ao
iterativa). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
B.14 Medidas de qualidade do agrupamento (S01). 99 termos. . . . . . . 139
B.15 Medidas de qualidade do agrupamento (S01). 7272 termos. . . . . . 139
xvi
Lista de Tabelas
Tabela
2.1 Quantidade de palavras e percentual de esparsidade da matriz documento-
termo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Termos mais freq
¨
uentes, sem exclus˜ao de termos sem valor informa-
cional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Termos mais freq
¨
uentes, ap´os a exclus˜ao de termos sem valor infor-
macional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Quantidade de palavras e percentual de esparsidade da matriz documento-
termo, (1) ap´os a remo¸c˜ao de palavras comuns sem valor informaci-
onal, (2) ap´os remo¸c˜ao dos sufixos e (3) percentual de termos sem
sufixos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.5 Tempos de execu¸c˜ao, em segundos, dos algoritmos de sele¸c˜ao de
caracter´ısticas, quantidade e percentual de termos selecionados. (A)
Valor do parˆametro L = 1 . . . . . . . . . . . . . . . . . . . . . . . 38
4.1 Constitui¸c˜ao das bases de documentos Reuters . . . . . . . . . . . . 71
4.2 Distribui¸c˜ao dos documentos das bases Reuters por categoria. Entre
parˆenteses, o n´umero que identifica cada categoria em cada uma das
bases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
xvii
4.3 Compara¸c˜ao das medidas de similaridade cosseno e euclideana (base
R04). (A) termos selecionados com o algoritmo iterativo. (B) ter-
mos selecionados com o algoritmo guloso. Os valores das medidas de
qualidade AA, RS e FM s˜ao percentuais. Os tempo s˜ao medidos
em segundos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.4 Resultados do agrupamento com o algoritmo k-means. (A) termos
selecionados com o algoritmo iterativo. (B) termos selecionados com
o algoritmo guloso. . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.5 Grupos X Categorias (R01). 5666 termos. Algoritmo k-means. . . . 89
4.6 Grupos X Categorias (R01). 38 termos (sele¸c˜ao iterativa). Algo-
ritmo k-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.7 Grupos X Categorias (R01). 58 termos. Algoritmo k-means. . . . . 89
4.8 Grupos X Categorias (R02). 7735 termos. Algoritmo k-means. . . . 90
4.9 Grupos X Categorias (R02). 83 termos (sele¸c˜ao iterativa). Algo-
ritmo k-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.10 Grup os X Categorias (R02). 169 termos. Algoritmo k-means. . . . . 91
4.11 Grup os X Categorias (R03). 6316 termos. Algoritmo k-means. . . . 91
4.12 Grup os X Categorias (R03). 55 termos (sele¸c˜ao iterativa). Algo-
ritmo k-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
4.13 Grup os X Categorias (R03). 185 termos. Algoritmo k-means. . . . . 92
4.14 Grup os X Categorias (R04). 3572 termos. Algoritmo k-means. . . . 93
4.15 Grup os X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algo-
ritmo k-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.16 Grup os X Categorias (R04). 28 termos. Algoritmo k-means. . . . . 93
4.17 Grup os X Categorias (S01). 7272 termos. Algoritmo k-means. . . . 94
4.18 Grup os X Categorias (S01). 116 termos (sele¸c˜ao iterativa). Algo-
ritmo k-means. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.19 Grup os X Categorias (S01). 99 termos. Algoritmo k-means. . . . . 94
xviii
4.20 Resultados do agrupamento com o algoritmo espectral. (A) termos
selecionados com o algoritmo iterativo. (B) termos selecionados com
o algoritmo guloso. . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.21 Grup os X Categorias (R01). 5666 termos. Algoritmo espectral. . . . 97
4.22 Grup os X Categorias (R01). 38 termos (sele¸c˜ao iterativa). Algo-
ritmo espectral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.23 Grup os X Categorias (R01). 58 termos. Algoritmo espectral. . . . . 98
4.24 Grup os X Categorias (R02). 7735 termos. Algoritmo espectral. . . . 98
4.25 Grup os X Categorias (R02). 83 termos (sele¸c˜ao iterativa). Algo-
ritmo espectral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
4.26 Grup os X Categorias (R02). 169 termos. Algoritmo espectral. . . . 99
4.27 Grup os X Categorias (R03). 6316 termos. Algoritmo espectral. . . . 99
4.28 Grup os X Categorias (R03). 55 termos (sele¸c˜ao iterativa). Algo-
ritmo espectral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.29 Grup os X Categorias (R03). 185 termos. Algoritmo espectral. . . . 100
4.30 Grup os X Categorias (R04). 3572 termos. Algoritmo espectral. . . . 100
4.31 Grup os X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algo-
ritmo espectral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.32 Grup os X Categorias (R04). 28 termos. Algoritmo espectral. . . . . 101
4.33 Grup os X Categorias (S01). 7272 termos. Algoritmo espectral. . . . 101
4.34 Grup os X Categorias (S01). 116 termos (sele¸c˜ao iterativa). Algo-
ritmo espectral. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.35 Grup os X Categorias (S01). 99 termos. Algoritmo espectral. . . . . 102
4.36 Resultado do agrupamento com o algoritmo de particionamento de
grafos - associa¸c˜ao ponderada. (A) termos selecionados com o algo-
ritmo iterativo. (B) termos selecionados com o algoritmo guloso. . . 103
4.37 Grup os X Categorias (R02). 83 (sele¸c˜ao iterativa) termos. Algo-
ritmo de particionamento de grafos - associa¸c˜ao ponderada . . . . . 103
xix
4.38 Grup os X Categorias (R02). 169 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada . . . . . . . . . . . . . . . . 103
4.39 Grup os X Categorias (R03). 185 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada . . . . . . . . . . . . . . . . 104
4.40 Grup os X Categorias (R04). 3572 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada . . . . . . . . . . . . . . . . 104
4.41 Grup os X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algo-
ritmo de particionamento de grafos - associa¸c˜ao ponderada . . . . . 105
4.42 Grup os X Categorias (R04). 28 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada . . . . . . . . . . . . . . . . 105
4.43 Resultado do agrupamento com o algoritmo de particionamento de
grafos - corte ponderado. (A) termos selecionados com o algoritmo
iterativo. (B) termos selecionados com o algoritmo guloso. . . . . . 106
4.44 Grup os X Categorias (R01). 5666 termos. Algoritmo de particiona-
mento de grafos - corte ponderado . . . . . . . . . . . . . . . . . . . 106
4.45 Grup os X Categorias (R01). 38 termos (sele¸c˜ao iterativa). Algo-
ritmo de particionamento de grafos - corte ponderado . . . . . . . . 107
4.46 Grup os X Categorias (R01). 58 termos. Algoritmo de particiona-
mento de grafos - corte ponderado . . . . . . . . . . . . . . . . . . . 107
4.47 Resultado do agrupamento com o algoritmo de particionamento de
grafos - associa¸c˜ao normalizada. (A) termos selecionados com o
algoritmo iterativo. (B) termos selecionados com o algoritmo guloso. 108
4.48 Grup os X Categorias (R02). 83 termos (sele¸c˜ao iterativa). Algo-
ritmo de particionamento de grafos - associa¸c˜ao normalizada . . . .
109
4.49 Grup os X Categorias (R02). 169 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada . . . . . . . . . . . . . . . 109
4.50 Grup os X Categorias (R03). 185 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada . . . . . . . . . . . . . . . 109
xx
4.51 Grup os X Categorias (R04). 3572 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada . . . . . . . . . . . . . . . 110
4.52 Grup os X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algo-
ritmo de particionamento de grafos - associa¸c˜ao normalizada . . . . 110
4.53 Grup os X Categorias (R04). 28 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada . . . . . . . . . . . . . . . 110
4.54 Grup os X Categorias (S01). 116 termos (sele¸c˜ao iterativa). Algo-
ritmo de particionamento de grafos - associa¸c˜ao normalizada . . . . 111
4.55 Grup os X Categorias (S01). 99 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada . . . . . . . . . . . . . . . 111
xxi
Lista de Siglas e Abreviaturas
AA - Acur´acia M´edia (do inglˆes Averaged Accuracy)
DF - Freq
¨
uˆencia dos Documentos (do inglˆes Document Frequency)
E - Sele¸c˜ao do Termo Indexador (Entropia)
En - Ordena¸c˜ao Baseada na Entropia
F - Medida-F
P - Precis˜ao
PSO - Particle Swarm Optimization
R - Recall
RS - Estat´ıstica Rand (do inglˆes Rand Statistics)
SC - Coeficiente de Silhueta (do inglˆes Silhouette Coefficient)
SOM - Self Organizing Maps
SNN - Shared Nearest Neighbors
STC - Suffix Tree Clustering
TC - Contribui¸c˜ao do Termo (do inglˆes Term Contribution)
TS - For¸ca do Termo (do inglˆes Term Strength)
TV - Variˆancia do Termo (do inglˆes Term Variance)
TVQ - Qualidade da Variˆancia do Termo (do inglˆes Term Variance Quality)
xxii
Cap´ıtulo 1
Introdu¸c˜ao
1.1 Motiva¸c˜ao
O armazenamento digital de informa¸c˜oes tem estimulado a cria¸c˜ao de fer-
ramentas que permitem a sua organiza¸c˜ao e recupera¸c˜ao eficientes.
`
A medida
que o volume de dados armazenado aumenta continuamente, a complexidade para
organiz´a-los e recuper´a-los tamb´em se torna maior. Paralelamente a este cres-
cimento surgiu uma ´area de pesquisa preocupada n˜ao apenas na organiza¸c˜ao e
recupera¸c˜ao, mas no uso do grande volume de dados armazenados para desco-
brir novas informa¸c˜oes at´e ent˜ao desconhecidas. Esta ´area, que ´e conhecida como
Minera¸c˜ao de Dados (do Inglˆes Data Mining), se refere `a descoberta de novas in-
forma¸c˜oes em fun¸c˜ao de padr˜oes e regras identific´aveis em um grande volume de
dados (Elmasri e Navathe, 2005). A pesquisa em Minera¸c˜ao de Dados teve um
impulso significativo a partir dos anos 90, sendo usada para identificar regras de
associa¸c˜ao em conjunto de vari´aveis, padr˜oes de seq
¨
uˆencias em s´eries temporais,
classifica¸c˜ao e agrupamentos de dados, dentre outros.
Um tipo de informa¸c˜ao comumente encontrada ´e a textual, sendo que prati-
camente todos os textos atualmente produzidos s˜ao armazenados em meio digital.
Com a massifica¸c˜ao do uso de computadores e do acesso a Internet, os meios di-
gitais tornaram-se a forma padr˜ao de circula¸c˜ao de informa¸c˜ao e conhecimento.
Assim ´e necess´ario cada vez mais, tornar eficiente e eficaz o acesso `a informa¸c˜ao
1
e ao conhecimento em textos digitalmente armazenados. De forma semelhante `a
Minera¸c˜ao de Dados, tamb´em surgiu a ´area denominada de Minera¸c˜ao de Textos
(do inglˆes Text Mining), que procura identificar rela¸c˜oes entre diferentes textos,
buscando descobrir um conhecimento novo at´e ent˜ao oculto em bases de dados
deste tipo.
A partir dos anos 70, as pesquisas sobre a recupera¸c˜ao de informa¸c˜oes em
bases de dados de textos tˆem sido realizadas com o objetivo de construir ferramen-
tas eficazes para o armazenamento, organiza¸c˜ao e indexa¸c˜ao destas bases. Estas
ferramentas devem permitir a elabora¸c˜ao de consultas que promovam um acesso
r´apido e preciso na obten¸c˜ao de informa¸c˜oes. Com o crescimento do uso da inter-
net, v´arias ferramentas de recupera¸c˜ao de informa¸c˜ao se popularizaram. Os s´ıtios
de busca Yahoo, Altavista e Google s˜ao exemplos que empregam intensamente
ferramentas de recupera¸c˜ao de informa¸c˜ao. Um problema comum a todas estas
ferramentas ´e a enorme quantidade de endere¸cos de p´aginas fornecidos na resposta
`a consulta, que faz com que as buscas sejam imprecisas, mesmo sendo r´apidas, pois
esta grande quantidade de itens na resposta demanda o refinamento da consulta
ou uma ineficiente visita a v´arios endere¸cos.
Na ´area de biomedicina, uma ferramenta de recupera¸c˜ao da informa¸c˜ao bas-
tante utilizada ´e o Pubmed (NLM, 2006b), mecanismo de busca no banco de
dados textual Medline (NLM, 2006a,c). O Medline tem mais de 15 milh˜oes de
artigos cient´ıficos indexados e semanalmente mais de 10 mil novos artigos s˜ao a ele
adicionados
1
. O Pubmed tem um mecanismo poderoso de busca, que permite
ao usu´ario elaborar consultas complexas, inclusive com sucessivos refinamentos.
Mesmo assim, ele geralmente fornece uma quantidade muito grande de referˆencias,
o que dificulta o seu uso.
1
N´umeros de dezembro de 2006 (NLM, 2006a). URL acessada em 22/05/2007.
2
´
E importante salientar que a recupera¸c˜ao de informa¸c˜ao em bases textuais
n˜ao representa a descoberta de conhecimento novo, que ´e o objetivo da minera¸c˜ao
de textos, mas apenas o acesso `a informa¸c˜ao que de alguma forma j´a ´e conhecida.
A Minera¸c˜ao de Textos se refere `a descoberta de novas informa¸c˜oes e conhecimento
em fontes que cont´em texto livre ou semi-estruturado (Hearst, 1999).
Assim sendo, ´e necess´ario o desenvolvimento de t´ecnicas que funcionem em
conjunto com mecanismos de busca, que facilitem o acesso `a informa¸c˜ao e princi-
palmente que propiciem a descoberta de conhecimento novo.
T´ecnicas de agrupamento de textos por similaridade tˆem sido utilizadas em
conjunto com mecanismos de recupera¸c˜ao de informa¸c˜ao (Yamamoto e Takagi,
2007). Esta abordagem tem por objetivo, a partir do tratamento dos resultados
das buscas, identificar grupos de documentos similares e permitir uma f´acil visu-
aliza¸c˜ao das interconex˜oes destes documentos pelo usu´ario, criando um ambiente
que propicie a descoberta de conhecimento novo.
O objetivo desta disserta¸c˜ao ´e investigar algumas t´ecnicas de agrupamento
de dados e a suas aplica¸c˜oes no contexto espec´ıfico de agrupamento de textos, de
modo a realizar a identifica¸c˜ao e organiza¸c˜ao de textos similares em bases de da-
dos desta natureza. Estas t´ecnicas s˜ao posteriormente utilizadas para a realiza¸c˜ao
do agrupamento de resultados de pesquisa no Medline atrav´es do Pubmed ,
permitindo que os pesquisadores tenham acesso ao conhecimento existente nestas
bases.
1.2 Contexto de aplica¸c˜ao da pesquisa realizada
Uma quantidade imensa de recursos tem sido aplicadas em v´arias frentes de
pesquisa contra o cˆancer a procura por suas causas, tratamentos, preven¸c˜ao, m´e-
3
todos de diagn´ostico etc. Estas p esquisas tˆem gerado uma quantidade imensa de
dados e informa¸c˜oes que s˜ao mantidos em bancos de dados e s˜ao descritos atrav´es
da publica¸c˜ao de textos cient´ıficos. O grande volume destas informa¸c˜oes e a sua
velocidade de crescimento dificultam a an´alise e assimila¸c˜ao no mesmo ritmo em
que s˜ao geradas. Existe, em toda esta informa¸c˜ao armazenada, um conhecimento
que pode, ao ser identificado ou descoberto, apontar novos caminhos e perspectivas
para as pesquisas sobre o cˆancer.
Uma nova ´area na pesquisa do cˆancer, dedicada ao estudo dos ant´ıgenos can-
cer/testis (CT) (Scanlan et al., 2004; Simpson et al., 2005) surgiu recentemente.
Esta ´area de pesquisa tem avan¸cado bastante nos ´ultimos 10 anos. A figura 1.1
mostra a evolu¸c˜ao do n´umero de artigos cient´ıficos publicados para trˆes conjuntos
de respostas `as consultas realizadas no Pubmed . A primeira consulta
2
pro-
cura por artigos relacionados aos ant´ıgenos cancer/testis de uma maneira geral. A
segunda consulta
3
procura por artigos que se refiram `a fam´ılia MAGE de ant´ıge-
nos cancer/testis e a terceira consulta combina as duas consultas anteriores. As
trˆes curvas, ilustradas na figura 1.1, demonstram uma acelera¸c˜ao a partir de mea-
dos dos anos 90, avan¸co este certamente direcionado pelo crescimento da pesquisa
genˆomica.
Estes exemplos demonstram que, devido ao crescimento exponencial das pu-
blica¸c˜oes cient´ıficas, existe a necessidade do desenvolvimento de ferramentas com-
putacionais que sejam capazes de organizar e extrair as informa¸c˜oes existentes
nestes conjuntos de textos cient´ıficos de forma a permitir e facilitar o acesso ao
conhecimento.
Este trabalho de disserta¸c˜ao est´a inserido no ˆambito do Projeto de Desen-
2
Exemplo de consulta por artigos no ano de 2006: (”testis”[MeSH Terms] OR testis[Text
Word]) AND ”Antigens, Neoplasm”[MeSH Terms] AND (”2006”[DP] : ”2006”[DP])
3
Exemplo de consulta por artigos no per´ıodo de 1992 a 2006: MAGE[tiab] AND ”antigen”[all
fields] AND (”1992”[DP] : ”2006”[DP])
4
Figura 1.1: Crescimento do n´umero de artigos cient´ıficos publicados sobre ant´ıgenos
cancer testis
volvimento de Ferramentas de Bioinform´atica Aplicadas ao Estudo do Cˆancer,
executado no Laborat´orio de Bioinform´atica do LNCC, em colabora¸c˜ao com o
Ludwig Institute for Cancer Research
4
. Neste projeto, um dos sistemas a serem
desenvolvidos ´e o Sistema de Anota¸c˜ao de Ant´ıgenos Cancer Testis
5
. Este sistema
fornecer´a um ambiente colaborativo de anota¸c˜ao funcional destes ant´ıgenos e agre-
gar´a, como suporte a esta anota¸c˜ao, informa¸c˜oes recuperadas de bancos de dados
biol´ogicos estruturados e textuais. Um dos seus requisitos ´e que as informa¸c˜oes
textuais, basicamente resumos de artigos cient´ıficos obtidos no Medline , estejam
organizadas de forma a facilitar o seu acesso para os anotadores e demais usu´arios
do sistema, e na medida do poss´ıvel esta organiza¸c˜ao deve refletir o conhecimento
descoberto nestas bases textuais.
Na figura 1.2 as principais partes deste sistema s˜ao apresentadas e na figura
1.3 o m´odulo de recupera¸c˜ao de informa¸c˜oes textuais ´e mostrado em detalhes.
4
http://www.licr.org/
5
http://www.cta.lncc.br
5
Figura 1.2: Diagrama do Sistema para Anota¸c˜ao de Ant´ıgenos Cancer Testis
O m´odulo de recupera¸c˜ao de informa¸c˜oes textuais ´e composto por 4 subm´o-
dulos:
Subm´odulo de interface para elabora¸c˜ao de consultas: nesta interface o
usu´ario do sistema elabora a consulta ao Medline ;
Subm´odulo de expans˜ao de consultas: atrav´es deste m´odulo a consulta ´e
expandida de forma a conter sinˆonimos dos termos utilizados pelo usu´ario,
com o objetivo de maximizar a quantidade de resumos de artigos cient´ıficos.
Este m´odulo formata a consulta expandida de acordo com os padr˜oes do
Pubmed ;
Subm´odulo de submiss˜ao de consultas ao Pubmed e recupera¸c˜ao dos
resultados: este m´odulo realiza o controle de submiss˜ao da consulta, re-
cep¸c˜ao dos resultados e a transforma¸c˜ao dos resumos de artigos cient´ıficos
em documentos do tipo texto puro. Esta transforma¸c˜ao ´e necess´aria pois
os arquivos originais s˜ao gerados com o uso de XML (Extended Markup
Language);
Subm´odulo de prepara¸c˜ao ou pr´e-processamento dos dados e agrupamento
de textos: este m´odulo realiza a prepara¸c˜ao dos dados de forma a construir
6
Figura 1.3: Diagrama do m´odulo de recupera¸c˜ao de informa¸c˜oes textuais do Sis-
tema para Anota¸c˜ao de Ant´ıgenos Cancer Testis
uma representa¸c˜ao dos documentos recuperados, o agrupamento de textos
e tamb´em deve fornecer as informa¸c˜oes necess´arias para a identifica¸c˜ao de
cada grupo formado para o m´odulo de apresenta¸c˜ao (ver figura 1.2). Os
dois primeiros itens, a prepara¸c˜ao de dados e o agrupamento de documentos
s˜ao objetos desta disserta¸c˜ao.
Uma caracter´ıstica da base de textos Medline , determinante na prepara¸c˜ao
dos dados, ´e que 77% de todos os artigos indexados est˜ao na l´ıngua inglesa e este
percentual est´a aumentando constantemente, na medida que a maioria dos novos
artigos publicadas s˜ao escritos nesta l´ıngua. No biˆenio 2005-2006 apenas 8% dos
artigos indexados foram escritos em alguma outra l´ıngua
6
(NLM, 2007).
A prepara¸c˜ao dos dados ´e necess´aria para que se tenha uma representa¸c˜ao dos
documentos, de forma que estes sejam utilizados pelos algoritmos de agrupamento
de dados. Os algoritmos de agrupamentos de dados, por sua vez, geram grupos de
documentos que sejam similares e que devem ser apresentados a fim de permitir a
um usu´ario o acesso mais eficaz aos resultados de consultas ao Medline .
6
Valores de fevereiro de 2007.
7
1.3 Trabalhos relacionados
A organiza¸c˜ao de resultados obtidos em motores de busca na Internet tem
como objetivo contornar o problema de que a resposta a uma consulta ´e consti-
tu´ıda normalmente de centenas ou milhares de endere¸cos, e este tem sido objeto
de v´arios trabalhos cient´ıficos nesta ´area. Uma das linhas de pesquisa consiste na
utiliza¸c˜ao de ferramentas que realizam o agrupamento dos documentos presentes
na resposta com o objetivo de se encontrar e rotular grupos similares (Mecca et al.,
2006). Esta abordagem surgiu no ˆambito de estudos sobre o aumento da qualidade
dos resultados da recupera¸c˜ao de informa¸c˜ao (Rijsbergen, 1979). Alguns dos siste-
mas propostos para esta tarefa s˜ao: Scatter/Gather (Cutting et al., 1992), Grouper
(Zamir e Etzioni, 1999), Carrot (Stanislaw Osi ´nski, 2005) e Vivisimo (sem publica-
¸c˜ao). Estes sistemas funcionam como uma camada intermedi´aria entre o usu´ario e
o motor de busca, recebendo uma consulta formulada por um usu´ario, submetendo-
a ao motor de busca, e por fim recebendo, agrupando e apresentando os resultados.
O Scatter/Gather (Cutting et al., 1992) ´e um sistema interativo. A partir
de uma consulta ´e fornecido um conjunto de resultados agrupados por temas e o
usu´ario seleciona alguns grupos, de acordo com o seu interesse. Os documentos
que pertencem aos grupos selecionados s˜ao reunidos formando um ´unico grupo,
que ´e um subconjunto do resultado inicial. Este grupo ´e redividido, permitindo-se
ao usu´ario selecionar novos grupos. Este processo ´e repetido tantas vezes quantas
o usu´ario desejar.
O Grouper (Zamir e Etzioni, 1999) funciona sobre o meta-motor de busca
MetaCrawler e n˜ao est´a mais dispon´ıvel, mas foi um dos sistemas pioneiros em uti-
lizar outros motores de busca na Internet. O algoritmo de agrupamento utilizado
pelo Grouper ´e o Suffix Tree Clustering (STC) (Zamir e Etzioni, 1998), que realiza
8
o agrupamento identificando frases que s˜ao comuns aos documentos. Frases, neste
contexto, s˜ao uma seq
¨
uˆencia ordenada de uma ou mais palavras.
O Carrot
7
´e um sistema que utiliza diversos algoritmos de agrupamento
de dados (FuzzyAnts, HAOG-STC, Rough k-means, STC, Lingo e Lingo3G), e o
usu´ario no momento da consulta pode escolher um deles e a consulta ´e submetida
para um, dentre os v´arios motores de busca ou bases de dados na Internet (Yahoo,
Google, Wikipedia, Dmoz etc). O resultado mostrado na figura 1.4, ´e apresentado
atrav´es de uma lista dos grupos formados, rotulados com um identificador.
Figura 1.4: Tela com os resultados do agrupamento de uma consulta no Carrot.
`
A
esquerda s˜ao mostrados os grupos descobertos e `a direita os endere¸cos das p´aginas
pertencentes ao grupo selecionado
O Vivisimo
8
apesar de ser uma aplica¸c˜ao comercial, possui um s´ıtio de
demonstra¸c˜ao
9
(ClusterMed) espec´ıfico para busca no Medline atrav´es do Pub-
med e seus resultados s˜ao apresentados de forma semelhante ao Carrot, com um
adicional de permitir que os grupos sejam reorganizados pelo usu´ario de acordo
7
http://demo.carrot2.org/demo-stable/main
8
http://vivisimo.com
9
http://demos.vivisimo.com/clustermed
9
com alguns campos de informa¸c˜ao do Medline (T´ıtulo, resumo, autor, data de
publica¸c˜ao etc).
A identifica¸c˜ao de grupos de resumos de artigos cient´ıficos similares em uma
resposta a uma consulta no Medline , tema de interesse desta disserta¸c˜ao, ´e abor-
dado em diversos trabalhos dispon´ıveis na literatura. Yamamoto e Takagi (2007)
na apresenta¸c˜ao do MCSyBi
10
((Multi-Document Clustering System for Biomedi-
cine) listam alguns: al´em do j´a citado ClusterMed, MedMiner
11
(Tanabe et al.,
1999) e TextQuest, entre outros.
O MedMiner (Tanabe et al., 1999) foi projetado para analisar relacionamen-
tos gene-a-gene identificados em experimentos de microarranjos de cDNA, pesqui-
sando a ocorrˆencia destes genes em resumos de artigo no Medline e em bases
de dados estruturadas. Apesar de ter uma interface muito complexa, o que torna
a elabora¸c˜ao de consultas dif´ıcil e lenta, o MedMiner tem duas caracter´ısticas in-
teressantes: a primeira ´e a integra¸c˜ao de bases de dados estruturadas, como o
GeneCard
12
, com o Medline . A segunda ´e, ao apresentar os resultados da con-
sulta, mostrar nos resumos dos artigos em destaque as ocorrˆencias de nomes de
genes e de palavras que tenham importˆancia para identificar as intera¸c˜oes entre
genes.
O TextQuest (Iliopoulos et al., 2001) realiza agrupamento de respostas do
Pubmed usando o algoritmo k-means (MacQueen, 1967) para identificar concei-
tos que caracterizem os grupos formados para auxiliar a pesquisa relacionada `as
prote´ınas.
O MCSyBi tem o prop´osito de gerar agrupamentos hier´arquicos ou n˜ao-
10
http://textlens.hgc.jp/McSyBi/
11
http://discover.nci.nih.gov/textmining/main.jsp
12
http://www.genecards.org
10
hier´arquicos a partir de resumos de artigos e permitir ao usu´ario que modifique o
resultado inicial do agrupamento fornecendo termos de seu interesse que guiar˜ao o
processo de reagrupamento. Este processo interativo faz com que o agrupamento
de textos seja um processo semi-supervisionado, guiado pelos interesses espec´ıfi-
cos do usu´ario. Os termos fornecidos pelo usu´ario recebem pesos diferenciados
que influenciam o processo de agrupamento. A apresenta¸c˜ao dos resultados tem
uma abordagem semelhante ao ClusterMed, s´o que n˜ao foram usados os campos
de informa¸c˜ao do Medline para organiz´a-la e sim termos da ontologia MeSH
13
(Medical Subject Headings), identificados no agrupamento, que tamb´em s˜ao esco-
lhidos pelo usu´ario.
Estas ferramentas listadas, sejam as de uso geral, como o Vivisimo ou o Car-
rot, sejam as de uso espec´ıfico que organizam resultados de consultas realizadas no
Medline tˆem uma estrutura em comum, composta basicamente por duas partes:
uma realiza a elabora¸c˜ao da consulta e a submiss˜ao ao mecanismo de recupera¸c˜ao
de informa¸c˜ao e a segunda consiste no uso de alguma implementa¸c˜ao do agrupa-
mento de documentos.
Alguns algoritmos de agrupamento de documentos s˜ao listados a seguir e
alguns deles s˜ao discutidos em detalhes no cap´ıtulo 3:
Algoritmo k-means - O algoritmo k-means encontra k grupos em um con-
junto de dados. Em (Larsen e Aone, 1999), o algoritmo k-means ´e utilizado
recursivamente para gerar uma hierarquia de documentos. Em (Steinbach
et al., 2000) ´e proposta uma altera¸c˜ao bem semelhante no m´etodo k-means,
para que este seja utilizado na divis˜ao recursiva de uma cole¸c˜ao de docu-
mentos. Em (Dhillon et al., 2002b) s˜ao propostas modifica¸c˜oes no m´etodo
k-means para contornar uma conhecida limita¸c˜ao deste algoritmo, evitando
que este encontre solu¸c˜oes locais. Algoritmos evolucion´arios s˜ao usados em
13
http://www.nlm.nih.gov/mesh/
11
combina¸c˜ao com o m´etodo k-means para contornar este mesmo problema
(Cui e Potok, 2005; Abraham et al., 2006).
Algoritmo kernel k-means - Uma outra limita¸c˜ao do algoritmo k-means
relatada na literatura ´e a sua incapacidade de agrupar dados que n˜ao se-
jam linearmente separ´aveis. O algoritmo kernel k-means tenta contornar
esta limita¸c˜ao mapeando o conjunto de caracter´ısticas dos objetos em um
espa¸co com um n´umero de dimens˜oes maior. Exemplo de aplica¸c˜ao deste
algoritmo no agrupamento de documentos ´e encontrado em (Karatzoglou
e Feinerer, 2006).
Algoritmos baseados em modelos - Este tipo de algoritmo deduz modelos
a partir de um conjunto de documentos, onde cada modelo corresponde
a um grupo identificado. Em (Zhong e Ghosh, 2005) ´e apresentado um
extenso estudo comparativo destes algoritmos.
Algoritmos Nebulosos (do inglˆes Fuzzy) - Este tipo de algoritmo constr´oi
grupos de forma que um documento tenha diferentes valores de pertinˆencia
em cada um dos grupos. Em (Borgelt e N
¨
urnberger, 2004) ´e aplicado o
algoritmo Fuzzy c-means para agrupar documentos.
Algoritmos de particionamento de grafos - Nestes algoritmos a cole¸c˜ao de
documentos e seus relacionamentos ´e modelada por um grafo, onde os docu-
mentos s˜ao os v´ertices e a similaridade entre os documentos correspondem
aos pesos associados `as arestas do grafo e o agrupamento ´e obtido pelo
particionamento do grafo. Exemplos de algoritmos de particionamento de
grafos para o agrupamento de p´aginas da Web s˜ao encontrados em (Boley
et al., 1999; Dhillon, 2001).
Algoritmos espectrais - Este tipo de algoritmo mapeia a cole¸c˜ao de do-
cumentos em uma matriz, onde cada elemento representa a similaridade
entre dois documentos. S˜ao calculados os autovetores de uma outra matriz
que ´e fun¸c˜ao da matriz de similaridade, que tendem a refletir a estrutura
12
dos grupos existentes nos dados. Exemplos de algoritmos de agrupamento
a partir do espectro da matriz de similaridade est˜ao em (Li et al., 2004;
Karatzoglou e Feinerer, 2006).
Algoritmos SNN (Shared Nearest Neighbors) - Este algoritmo, proposto
inicialmente por Jarvis e Patrick (1973), ´e indicado para agrupar dados com
um n´umero alto de dimens˜oes, densos e de diferentes formatos (Ert
¨
oz et al.,
2003). Em (Ertz et al., 2001) esta t´ecnica ´e aplicada para o agrupamento
de documentos.
Algoritmos SOM (Self Organizing Maps) - SOM ´e um m´etodo para apren-
dizado n˜ao supervisionado baseado em redes neurais que constr´oi um grafo
de similaridades dos dados de entrada. A aplica¸c˜ao do SOM para organi-
zar cole¸c˜oes de documentos ´e proposta por (Kohonen et al., 2000) e como
resultado os documentos s˜ao representados como pontos em um plano bi-
dimensional e as rela¸c˜oes entre os pontos representa a similaridade entre os
documentos. PubCluster
14
´e um sistema (Fattore M, 2004) para agrupar
hierarquicamente resultados de busca no Medline que usa o SOM. Em
(Hung e Wermter, 2004) o SOM ´e usado junto com o dicion´ario WordNet
15
para agrupar documentos.
Algoritmo STC (Suffix Tree Clustering) - O STC, proposto p or (Zamir e
Etzioni, 1998) ´e utilizado, junto com o WordNet, por (zu Eissen et al., 2005)
em um estudo comparativo com algoritmos de agrupamento de grafos, que
demonstra que estes ´ultimos produzem resultados melhores.
Agrupamento Semi-supervisionado - Uma das caracter´ısticas principais
dos algoritmos de agrupamento ´e que este realizam o aprendizado n˜ao-
supervisionado, ou seja, os grup os s˜ao descobertos sem que se tenha qual-
quer conhecimento pr´evio sobre sua composi¸c˜ao e estrutura. Recente-
mente, tˆem surgido algumas propostas a fim de se induzir o processo de
14
http://biocomp.ge.ismac.cnr.it/
15
http://wordnet.princeton.edu/
13
agrupamento atrav´es da inclus˜ao de um conhecimento pr´evio que guie a
descoberta dos grupos. Em (Ji et al., 2000) ´e apresentado um algoritmo
que modela uma cole¸c˜ao de documentos como um grafo e fornece ao al-
goritmo de agrupamento um conjunto de restri¸c˜oes que determinam quais
documentos compartilham o mesmo grupo. O algoritmo deve ent˜ao encon-
trar o melhor corte no grafo, de forma a identificar os grupos, respeitando
estas restri¸c˜oes. Em (Huang e Mitchell, 2006) o algoritmo de agrupamento
´e baseado em modelos e em um processo interativo com o usu´ario. Ap´os
o agrupamento inicial, este pode remover palavras chave ou documentos,
reiniciando o processo de agrupamento incluindo estas informa¸c˜oes.
Conjunto de itens freq
¨
uentes - Esta t´ecnica de minera¸c˜ao de dados, uti-
lizada para descobrir regras de associa¸c˜ao em conjuntos de transa¸c˜oes ´e
aplicada (Beil et al., 2002; Fung et al., 2003) para identificar conjunto de
palavras freq
¨
uentes e construir grupos de documentos que compartilhem
estas palavras.
Ontologias - O uso de ontologias, como o WordNet, apesar de n˜ao consti-
tu´ırem, por si, em uma t´ecnica de agrupamento, tem tido um uso crescente
em implementa¸c˜oes de agrupamentos de documentos (Hotho et al., 2001,
2003) para diminuir os problemas de sinon´ımia, polissemia e de alta di-
mensionalidade da representa¸c˜ao dos documentos. Em (Yoo et al., 2006) ´e
proposto a constru¸c˜ao de um grafo, enriquecido por uma ontologia, como
representa¸c˜ao de uma cole¸c˜ao de documentos e que usa o agrupamento
baseado em modelos para construir os grupos a partir deste grafo.
A lista acima traz apenas um resumo ampliado do que est´a sendo investi-
gado em rela¸c˜ao `as t´ecnicas de agrupamento de documentos e n˜ao se constitui em
um levantamento exaustivo.
´
E relevante destacar que muitas das t´ecnicas listadas
combinam diferentes abordagens com o objetivo de aumentar a qualidade dos re-
sultados, ou seja, n˜ao existe at´e o momento, uma abordagem universal que possa
14
ser aplicada a diferentes conjuntos de documentos e que obtenha o mesmo n´ıvel de
qualidade para todos. A combina¸c˜ao de diferentes t´ecnicas visa contornar uma ou
outra deficiˆencia existente em alguma delas.
Cinco quest˜oes significativas surgem a partir desta lista:
(1) Para todas estas abordagens ´e necess´ario que se construa, a partir da
cole¸c˜ao de documentos, uma representa¸c˜ao que possa ser manipulada pelos
algoritmos de agrupamento. A representa¸c˜ao mais utilizada ´e o modelo de
espa¸co-vetorial (Salton et al., 1975).
(2) Na literatura relacionada ao agrupamento de documentos, um problema
derivado do uso do modelo espa¸co-vetorial ´e que a representa¸c˜ao cons-
tru´ıda possui em geral uma alta dimensionalidade e ´e esparsa (Steinbach
et al., 2003), o que implica diretamente em problemas na velo cidade de
execu¸c˜ao dos algoritmos e na qualidade dos resultados. Isto justifica o em-
prego de t´ecnicas que diminuam o n´umero de dimens˜oes que representem
as caracter´ısticas de cada objeto.
(3) A crescente utiliza¸c˜ao de ontologias para auxiliar a constru¸c˜ao da repre-
senta¸c˜ao dos documentos que ´e utilizada pelos algoritmos de agrupamento
e que podem melhorar sensivelmente os seus resultados.
(4)
´
E not´avel na literatura a grande quantidade de trabalhos que abordam
em conjunto ou em separado os algoritmos kernel k-means, espectrais e de
particionamento de grafos, que por outro lado ainda s˜ao pouco utilizados
para o agrupamento de documentos.
(5) O uso de algoritmos semi-supervisionados, que permitem ao usu´ario influir
no resultado do algoritmo, o que pode ser determinante para qualidade dos
resultados.
Na literatura existem poucos trabalhos que estabele¸cam compara¸c˜oes mais
amplas entre diferentes t´ecnicas de agrupamento de documentos. Geralmente os
15
estudos comparam uma t´ecnica qualquer, que ´e o foco do estudo em quest˜ao, com
uma ou outra t´ecnica, sem estabelecer compara¸c˜oes mais extensas. Como exce¸c˜ao,
existem duas compara¸c˜oes de algoritmos de agrupamento de documentos realiza-
das por (Steinbach et al., 2000) e por (Yoo e Hu, 2006).
Em (Steinbach et al., 2000) a compara¸c˜ao ´e dividida em duas partes: na pri-
meira, s˜ao comparados trˆes algoritmos hier´arquicos (Intra-cluster Similarity Te-
chnique - IST, Centroide Similarity Technique - CST e Unweighted Pair Group
Method with Arithmetic mean - UPGMA). Estes trˆes algoritmos s˜ao utilizados
para agrupar oito cole¸c˜oes de documentos distintas, e em todas estas, o algoritmo
UPGMA obteve os melhores resultados. Nesta compara¸c˜ao foi utilizada a medida
F-measure, como m´etrica de avalia¸c˜ao.
Na segunda parte da compara¸c˜ao realizada por Steinbach et al. (2000), o
UPGMA ´e comparado com o algoritmo k-means e com o algoritmo Bisecting k-
means, introduzido neste mesmo artigo, sobre as mesmas cole¸c˜oes de documentos,
usando-se as medidas Entropia e Similaridade Total para avaliar os resultados. Os
testes realizados apontam que o algoritmo Bisecting k-means tem desempenho su-
perior aos outros dois algoritmos.
Na compara¸c˜ao realizado por Yoo e Hu (2006) s˜ao comparados os algorit-
mos STC, k-means, Bisecting k-means e trˆes algoritmos hier´arquicos (single link,
complete link e UPGMA) no agrupamento de 44 cole¸c˜oes de resumos de artigos
cient´ıficos extra´ıdos do Medline , com tamanhos que variaram de 4000 a 158000
documentos. Os testes realizados comparam tamb´em se o uso da ontologia MeSH
contribui para a melhoria dos resultados. A conclus˜ao final desta avalia¸c˜ao indica
que o algoritmo Bisecting k-means, com o uso do MeSH apresenta os melhores
resultados.
16
Estas compara¸c˜oes, mesmo tendo inclu´ıdo um n´umero maior de algoritmos,
n˜ao inclu´ıram outras abordagens como os algoritmos SOM, SNN, Fuzzy, baseados
em modelos, espectrais, particionamento de grafos, entre os outros que na litera-
tura s˜ao citados como sendo utilizados para o agrupamento de documentos.
1.4 Contribui¸c˜oes deste trabalho
O objetivo principal deste trabalho ´e a investiga¸c˜ao de t´ecnicas de agrupa-
mentos de dados aplicadas para o agrupamento de texto, e este objetivo desdobra-se
em trˆes sub-objetivos espec´ıficos:
(1) Implementa¸c˜ao de estrat´egia de pr´e-processamento de documentos, des-
crita na literatura, para constru¸c˜ao da matriz documento-termo, usada
como entrada dos algoritmos de sele¸c˜ao de caracter´ısticas e de agrupa-
mento. Este estrat´egia contempla apenas documentos escritos na l´ıngua
inglesa;
(2) Apresenta¸c˜ao e implementa¸c˜ao de algoritmos para sele¸c˜ao de caracter´ısti-
cas, visando a redu¸c˜ao da dimensionalidade da matriz documento-termo;
(3) Avalia¸c˜ao do algoritmo espectral e do algoritmo de particionamento de
grafos para o agrupamento de documentos, comparando-os com o algoritmo
k-means.
1.5 Organiza¸c˜ao da disserta¸c˜ao
O restante desta disserta¸c˜ao est´a organizada da seguinte forma: O cap´ıtulo 2
aborda a etapa de prepara¸c˜ao dos dados, incluindo o pr´e-processamento da base de
dados textual a ser submetida `as t´ecnicas de agrupamento e algumas t´ecnicas de
sele¸c˜ao de caracter´ısticas utilizadas de modo a reduzir a dimensionalidade do espa¸co
de representa¸c˜ao dos textos. No capitulo 3 s˜ao apresentados mais detalhes de
algumas t´ecnicas de agrupamento de dados e as m´etricas empregadas na avalia¸c˜ao
17
de resultados. No cap´ıtulo 4 s˜ao apresentadas as bases de dados textuais utilizadas
neste trabalho, as ferramentas computacionais utilizadas, os testes realizados e
a discuss˜ao dos resultados. Os cap´ıtulo 5 e 6 apresentam, resp ectivamente, as
conclus˜oes deste trabalho e as perspectivas futuras.
18
Cap´ıtulo 2
Prepara¸c˜ao dos Dados
Para que o agrupamento de documentos seja realizado, nos moldes de in-
teresse, ´e necess´ario que esta cole¸c˜ao seja preparada para o processamento. Esta
prepara¸c˜ao ´e composta obrigatoriamente por uma etapa de pr´e-processamento,
que constr´oi a sua representa¸c˜ao e elege uma lista de caracter´ısticas para cada
documento, de acordo com algum modelo e por uma segunda etapa, n˜ao obrigat´o-
ria, de sele¸c˜ao ou extra¸c˜ao das caracter´ısticas destes documentos a serem efetiva-
mente utilizadas no agrupamento. Neste cap´ıtulo abordam-se estas duas etapas e
descrevem-se as estrat´egias utilizadas.
2.1 Pr´e-processamento
Para se identificar grupos similares em um conjunto de textos, deve ser pre-
viamente constru´ıda uma representa¸c˜ao para os elementos deste conjunto que, ar-
mazenada em uma estrutura de dados, seja mais apropriada para o processamento.
Para os algoritmos de agrupamento que s˜ao investigados nesta disserta¸c˜ao, a re-
presenta¸c˜ao escolhida ´e o Modelo Espa¸co-vetorial (Salton et al., 1975), que embora
tendo sido proposto para a indexa¸c˜ao de palavras para o uso em Recupera¸c˜ao da
Informa¸c˜ao, ´e a representa¸c˜ao de uso mais comum quando se pretende agrupar
textos (Liu et al., 2005; Hotho et al., 2005). Existem outras representa¸c˜oes citadas
na literatura que s˜ao pouco usadas at´e ent˜ao:
´
Arvore de Sufixos (Zamir e Etzioni,
1998), Conjuntos de Itens Freq
¨
uentes (Beil et al., 2002), Linguagem Universal de
19
Rede (Choudhary e Bhattacharyya, 2002), Grafo de
´
Indice de Documentos (Ham-
mouda e Kamel, 2004).
No Modelo Espa¸co-vetorial, cada documento ´e representado por um ponto
em um espa¸co multidimensional onde cada palavra do texto corresponde a uma
dimens˜ao. Cada ponto corresponde a um vetor d = {w
1
, w
2
, w
3
, . . . , w
n
} onde w
i
´e a freq
¨
uˆencia (absoluta ou relativa) do termo i no documento em quest˜ao, e n ´e
a quantidade total de palavras existentes no conjunto de textos. A freq
¨
uˆencia de
uma palavra pode ser ponderada de forma a refletir, no vetor correspondente a um
documento, a sua importˆancia no conjunto de documentos.
O conjunto de vetores correspondentes aos diferentes documentos, comp˜oem
a matriz documento-termo X, onde seu elemento (i, j) ´e a freq
¨
uˆencia f
(i,j)
, pon-
derada ou n˜ao, da palavra j no texto i. Na constru¸c˜ao dessa matriz o conjunto de
palavras, que correspondem `as suas colunas, ´e a uni˜ao dos diferentes conjuntos de
palavras associados a cada documento.
Uma caracter´ıstica importante desta representa¸c˜ao, ´e que a ordem com que
os termos aparecem no texto n˜ao ´e considerada. O texto ´e representado como uma
s´erie de termos, sem informa¸c˜ao de valor semˆantico e sobre as suas localiza¸c˜oes
(Liu et al., 2005).
Usualmente, esta matriz possui um n´umero elevado de dimens˜oes e ´e com
freq
¨
uˆencia muito esparsa, porque o total de termos da cole¸c˜ao de palavras tende a
ser muito maior que a quantidade de termos usados em um ´unico texto. Na tabela
2.1 s˜ao mostradas as quantidades de palavras que existem em cinco cole¸c˜oes de
documentos
1
e o percentual de freq
¨
uˆencias nulas (esparsidade) que ocorrem nas
matrizes documento-termo correspondentes. Observa-se que este percentual para
1
Estas bases s˜ao descritas em detalhes no cap´ıtulo 4
20
as cinco bases apresenta-se em torno de 99%. Este ´e um problema comum em
processamento de textos (Liu et al., 2005) e ´e analisado com profundidade na pr´o-
xima se¸c˜ao deste cap´ıtulo, quando ent˜ao, s˜ao descritas estrat´egias para contorn´a-lo.
Base Qtde de termos Esparsidade
R01 8537 98,90%
R02 11462 99,26%
R03 9154 99,16%
R04 5382 98,43%
S01 11179 99,24%
Tabela 2.1: Quantidade de palavras e percentual de esparsidade da matriz
documento-termo
O pr´e-processamento de um conjunto de textos para constru¸c˜ao da matriz
documento-termo pode ser minimamente constitu´ıdo de 3 fases:
(1) Segmenta¸c˜ao dos textos em termos;
(2) Remo¸c˜ao de n ´umeros, caracteres n˜ao alfab´eticos e de termos comuns (pro-
nomes, artigos, preposi¸c˜oes, adv´erbios etc) que n˜ao possuem capacidade
discriminativa;
(3) Remo¸c˜ao dos sufixos das palavras para reduzi-las ao seu radical comum.
As duas ´ultimas fases s˜ao necess´arias para que se reduza o n´umero de carac-
ter´ıstica de cada documentos. No apˆendice A ´e mostrado um exemplo do proces-
samento de um documento.
O pr´e-processamento tamb´em deve considerar o idioma utilizado nos textos,
pois tanto as palavras comuns que devem ser retiradas, quanto o processo de re-
mo¸c˜ao dos sufixos s˜ao diretamente dependentes do idioma usado. Portanto, como
este estudo est´a inserido em um projeto que realiza a Minera¸c˜ao de Textos em con-
juntos de resumos de artigos cient´ıficos escritos em sua maioria na l´ıngua inglesa,
estas duas fases s˜ao implementadas considerando o inglˆes como a l´ıngua de todos
21
os documentos.
2.1.1 Segmenta¸c˜ao do texto
Na segmenta¸c˜ao dos textos em palavras, inicialmente todos os sinais de pon-
tua¸c˜ao s˜ao substitu´ıdos por espa¸cos, e todas as palavras tˆem os seus caracteres
convertidos em min´usculos. Estes passos iniciais s˜ao realizados pois tanto os sinais
de pontua¸c˜ao quanto a diferen¸ca de caracteres entre min´usculos e mai´usculos s˜ao
irrelevantes na representa¸c˜ao de documentos para fins de agrupamento.
Ap´os estas substitui¸c˜oes e convers˜oes, cada conjunto de caracteres delimitado
por espa¸cos ´e considerado um termo e o documento ent˜ao ´e considerado como a
uni˜ao destes termos.
Desta lista de termos, os caracteres num´ericos podem ou n˜ao serem man-
tidos
2
, pois os n´umeros, independentemente da quantidade de documentos em
que ocorram, tendem a n˜ao contribuir para a discrimina¸c˜ao dos documentos. Um
exemplo, em favor de sua manuten¸c˜ao, ´e no caso de agrupamento de documentos
de artigos cient´ıficos na ´area de biomedicina. Neste caso, ´e comum que os nomes
de genes, prote´ınas, enzimas etc contenham caracteres num´ericos. Em outros tipos
de texto, onde estes caracteres n˜ao possuem valor discriminativo, a sua remo¸c˜ao ´e
realizada. Por fim, excluem-se os caracteres que n˜ao sejam alfanum´ericos.
2.1.2 Exclus˜ao de termos
Existem termos que n˜ao possuem capacidade para discriminar documentos,
por n˜ao possu´ırem valor informacional ou por terem um uso muito comum, ocor-
rendo em praticamente todos os documentos de uma cole¸c˜ao. Termos sem valor
2
Nos experimentos realizados neste trabalho os caracteres num´ericos s˜ao removidos
22
informacional geralmente pertencem a determinadas classes gramaticais, por exem-
plo, artigos e preposi¸c˜oes. A tabela 2.2 ilustra os cinco termos com maior n´umero
de ocorrˆencias em documentos de trˆes categorias distintas da base S01
3 ,4
. Nas
trˆes categorias, estes termos com maior freq
¨
uˆencia (Um artigo, uma conjun¸c˜ao e
trˆes preposi¸c˜oes) s˜ao comuns e todos tˆem uma freq
¨
uˆencia muito superior ao n´umero
de documentos de cada categoria, indicando que geralmente ocorrem mais de uma
vez no mesmo documento.
Termo cisi cran med
the 2849 4567 3631
of 2426 3020 2883
and 1421 1439 1446
in 1039 1150 1568
to 1016 972 804
Tabela 2.2: Termos mais freq
¨
uentes, sem exclus˜ao de termos sem valor informaci-
onal
A exclus˜ao de termos sem capacidade discriminativa consiste da exclus˜ao
destes da lista de termos formada ap´os a segmenta¸c˜ao. Para que seja realizada
a exclus˜ao s˜ao usadas listas de termos pr´e-definidos. Neste trabalho ´e usada a
lista utilizada para a indexa¸c˜ao de bases de documentos do projeto Smart
5
, que ´e
um projeto de pesquisa para o desenvolvimento de um sistema de recupera¸c˜ao de
informa¸c˜oes que existe desde a d´ecada de 60 e ´e a lista mais citada na literatura.
Cada um dos termos pertencente a esta lista ´e exclu´ıdo da lista inicial de termos.
A tabela 2.3 ilustra os cinco termos com maior freq
¨
uˆencia, ap´os a exclus˜ao dos
termos presentes na lista Smart. Constata-se que os termos mais freq
¨
uentes em
uma categoria, n˜ao s˜ao os mais freq
¨
uentes em outra, tendendo assim a serem bons
discriminadores. Por exemplo, o termo information, que tem freq
¨
uˆencia igual a
364 na categoria cisi, tem freq
¨
uˆencia igual a 10 e 14 nas categorias med e cran
3
Cada uma das trˆes categorias desta base cont´em 300 documentos, totalizando 900 documen-
tos.
4
A base S01 ´e derivada da base Smart
5
ftp://ftp.cs.cornell.edu/pub/smart/english.stop
23
respectivamente. Um outro exemplo, os termos library, shock e blood s˜ao exclu-
sivos em suas respectivas categorias, constituindo-se em excelentes discriminadores.
Categoria termos
cisi information, library, data, research, systems
cran flow, pressure, boundary, layer, shock
med cells, patients, bloo d, normal, found
Tabela 2.3: Termos mais freq
¨
uentes, ap´os a exclus˜ao de termos sem valor informa-
cional
2.1.3 Remo¸c˜ao dos sufixos das palavras
A remo¸c˜ao dos sufixos, tem por objetivo reduzir o tamanho dos vetores cor-
respondentes a cada texto e conseq
¨
uentemente a redu¸c˜ao da matriz documento-
termo. Esta redu¸c˜ao ocorre p orque palavras diferentes que compartilham o mesmo
radical, quando tˆem removidos os sufixos que indicam flex˜oes de n´umero, gˆenero,
grau e conjuga¸c˜ao verbal s˜ao representadas por este radical. Considera-se que este
radical seja representativo destas palavras, mesmos que do ponto de vista ling
¨
u´ıs-
tico isto possa n˜ao ser correto.
Para a l´ıngua inglesa, de acordo com a literatura (Hotho et al., 2005; Liu
et al., 2005), um algoritmo freq
¨
uentemente utilizado para realizar a remo¸c˜ao dos
sufixos ´e o algoritmo Porter (Porter, 1980). Um outro algoritmo tamb´em citado,
por´em pouco utilizado no agrupamento de documentos ´e o algoritmo Lovins (Lo-
vins, 1968).
O algoritmo Porter foi constru´ıdo para ser usado na recupera¸c˜ao da informa-
¸c˜ao, e com um requisito de que o seu processamento seja r´apido, sem a obrigato-
riedade de que os radicais de palavras encontrados serem corretos sob o ponto de
vista ling
¨
u´ıstico. Os erros que ocorrem dizem respeito ao fato dos radicais encon-
trados serem maiores ou menores do que os radicais reais das palavras. Estes erros
24
decorrem de que este algoritmo pertence a uma classe de algoritmos de remo¸c˜ao
de sufixos que n˜ao fazem uso de dicion´arios de radicais de palavras, mas utilizam
uma lista de sufixos, onde para cada sufixo, existem regras que determinam quando
estes podem ser ou n˜ao removidos.
De acordo com a tabela 2.4 o uso do algoritmo Porter reduz em aproxima-
damente 30% a quantidade de termos existentes na matriz documento-termo, sem
alterar significativamente a esparsidade desta.
2.1.4 Implementa¸c˜ao
As trˆes fases do pr´e-processamento foram implementadas em um programa
escrito na linguagem de programa¸c˜ao Perl. Este programa usa duas bibliotecas,
espec´ıficas para a l´ıngua inglesa, al´em da implementa¸c˜ao do algoritmo Porter para
remo¸c˜ao de sufixo. As duas bibliotecas s˜ao:
(1) Lingua::EN::Segmenter, para a segmenta¸c˜ao do documento,
(2) Lingua:EN::StopWords, para exclus˜ao das palavras sem valor informacio-
nal. O conjunto original de palavras desta biblioteca foi substitu´ıdo por
dois conjuntos de termos:
(a) O conjunto usado no projeto Smart, que cont´em as 26 letras do al-
fabeto mais 545 palavras ou contra¸c˜oes de palavras
6
. Esta lista ´e
utilizada nos testes realizados neste trabalho.
(b) O conjunto usado no Pubmed
7
, que cont´em 132 termos.
A codifica¸c˜ao em Perl do algoritmo Porter para remo¸c˜ao de sufixos (Porter,
1980), foi obtida na p´agina
8
mantida por Martin Porter.
6
Exemplos: Either, I’m, It’s, Meanwhile
7
http://www.ncbi.nlm.nih.gov/books/bv.fcgi?rid=helppubmed.table.pubmedhelp.T43
8
http://www.tartarus.org/martin/PorterStemmer/
25
No pr´e-processamento de um conjunto de documentos s˜ao gerados quatro
arquivos:
(1) Um arquivo contendo a matriz documento-termo. As linhas da matriz
correspondem aos documentos e est˜ao organizadas conforme estes s˜ao lidos
pelo programa. As colunas correspondem `as palavras em ordem alfab´etica
e cont´em suas freq
¨
uˆencias absolutas de ocorrˆencia no documento;
(2) Um arquivo contendo os identificadores de cada texto, utilizados para in-
dexar as linhas da matriz documento-termo. Se o conjunto de textos for
uma base de teste previamente classificada, cada documento tamb´em ´e
associado a sua respectiva classe. Esta associa¸c˜ao ´e usada posteriormente
na avalia¸c˜ao dos resultados;
(3) Um arquivo contendo o dicion´ario dos radicais das palavras, em ordem
alfab´etica, e sua respectiva freq
¨
uˆencia absoluta de ocorrˆencia no conjunto
de textos;
(4) Um arquivo contendo o dicion´ario de palavras associadas ao radical ex-
tra´ıdo pelo algoritmo Porter.
Os dois ´ultimos arquivos s˜ao usados para a identifica¸c˜ao dos grupos formados
e n˜ao s˜ao utilizados no escopo deste trabalho.
2.2 Sele¸c˜ao de caracter´ısticas
Como observado anteriormente, o uso do Modelo Espa¸co-Vetorial para re-
presenta¸c˜ao de documentos, usualmente gera uma matriz esparsa e de alta dimen-
sionalidade, o que provoca um baixo desempenho dos algoritmos de agrupamento
de documentos que por sua vez implica no aumento do custo computacional em
rela¸c˜ao ao tempo de processamento e espa¸co de mem´oria. Um outro problema,
de maior impacto, se d´a p ela dificuldade em diferenciar objetos que possuam um
n´umero alto de dimens˜oes, ao se aplicar alguma fun¸c˜ao que calcule a similaridade
26
ou distˆancia entre estes objetos (Beyer et al., 1999; Aggarwal e Yu, 2000).
Algumas das estrat´egias usadas no pr´e-processamento abordadas na se¸c˜ao
anterior, contribuem para minimizar tais problemas. A exclus˜ao de palavras sem
valor informacional e a remo¸c˜ao dos sufixos das palavras, fazem com que o n´umero
de termos seja sensivelmente reduzido. No entanto, a matriz documento-termo re-
sultante, ainda, permanece esparsa e com um n´umero alto de dimens˜oes, conforme
mostrado na tabela 2.4. Nesta se¸c˜ao aborda-se o problema conhecido como Sele¸c˜ao
de Caracter´ısticas, que tem por objetivo reduzir da maior forma poss´ıvel, o n´umero
de temos que efetivamente contribuem para a discrimina¸c˜ao dos documentos.
Base Qtde total Qtde. de Esparsidade Qtde. Esparsidade
de termos termos (1) de termos (2)
R01 8537 8135 99,23% 5666 (69,65%)
3
98,96%
R02 11462 11033 99,48% 7735 (70,11%) 99,31%
R03 9154 8751 99,41% 6316 (72,17%) 99,23%
R04 5382 5023 98,87% 3572 (71,11%) 98,51%
S01 11179 10769 99,47% 7272 (72,72%) 99,27%
Tabela 2.4: Quantidade de palavras e percentual de esparsidade da matriz
documento-termo, (1) ap´os a remo¸c˜ao de palavras comuns sem valor informaci-
onal, (2) ap´os remo¸c˜ao dos sufixos e (3) percentual de termos sem sufixos.
A Sele¸c˜ao de Caracter´ısticas ´e o processo no qual se seleciona um subcon-
junto de caracter´ısticas que mant´em a capacidade de representar e discriminar os
objetos em estudo. Essas exigˆencias s˜ao necess´arias para garantir que o desem-
penho dos algoritmos de agrupamento n˜ao seja comprometido. Outra exigˆencia
que as caracter´ısticas selecionadas devem atender ´e possibilitar a compreens˜ao do
significado de cada grupo formado, ap´os o processo de agrupamento (Beil et al.,
2002; Ma et al., 2003). Esta etapa do processo de agrupamento, que ´e a constru¸c˜ao
de r´otulos para os grupos formados, a partir das caracter´ıstica selecionadas n˜ao ´e
objeto deste trabalho.
Este tipo de sele¸c˜ao ´e diferente de t´ecnicas conhecidas como Extra¸c˜ao de Ca-
27
racter´ısticas, que realizam a transforma¸c˜ao do conjunto inicial de caracter´ısticas,
gerando um novo conjunto com uma quantidade menor de dimens˜oes, atrav´es de
alguma fun¸c˜ao de mapeamento.
Exemplos de t´ecnicas de Extra¸c˜ao de Caracter´ısticas s˜ao a An´alise de Comp o-
nentes Principais (PCA, do inglˆes Principal Component Analysis) (Jolliffe, 1986),
a Decomposi¸c˜ao em Valores Singulares (Wall et al., 2002) dentre outras. As no-
vas caracter´ısticas geradas a partir da utiliza¸c˜ao destas t´ecnicas, apesar de serem
igualmente ´uteis para o agrupamento de textos (Dhillon e Modha, 2001), por serem
resultantes da transforma¸c˜ao do conjunto inicial n˜ao possuem um significado claro,
o que dificulta a sua utiliza¸c˜ao para a interpreta¸c˜ao dos grupos formados (Dash e
Liu, 2000; Liu et al., 2005).
Isto posto, resumem-se em trˆes os objetivos que norteiam o processo de
sele¸c˜ao de caracter´ısticas:
(1) Contornar os problemas que a alta dimensionalidade provoca no c´alculo
da similaridade ou distˆancia entre os documentos;
(2) Diminuir o custo computacional dos algoritmos de agrupamento, em rela-
¸c˜ao ao tempo de processamento e espa¸co de mem´oria;
(3) Fornecer um conjunto de termos que possam caracterizar e discriminar de
forma sucinta e objetiva cada grupo formado.
Existem v´arios m´etodos para Sele¸c˜ao de Caracter´ısticas utilizados no agru-
pamento de textos. A maioria, se caracteriza por selecionar termos que tenham
maior poder discriminat´orio dentre os demais no processo de separa¸c˜ao dos docu-
mentos em grupos, tendo como diferen¸ca a forma como o c´alculo da importˆancia
de cada termo ´e realizado e como se determina a quantidade de termos escolhidos.
28
Os m´etodos de sele¸c˜ao de caracter´ısticas s˜ao dependentes do modelo utili-
zado para a representa¸c˜ao dos documentos. Os m´etodos abordados neste trabalho
s˜ao relacionados ao modelo espa¸co-vetorial. Uma outra abordagem, para a sele¸c˜ao
de caracter´ısticas, ´e a utiliza¸c˜ao de uma t´ecnica comum em minera¸c˜ao de dados
que tem a finalidade de descobrir regras de associa¸c˜ao (Agrawal e Srikant, 1994)
entre itens de uma transa¸c˜ao. No contexto de banco de dados relacionais, este ´e
considerado uma cole¸c˜ao de transa¸c˜oes, e cada transa¸c˜ao ´e um conjunto de itens
(Elmasri e Navathe, 2005). No contexto de bancos textuais, os documentos s˜ao
considerados transa¸c˜oes e os termos s˜ao considerados os seus itens.
A descoberta de regras de associa¸c˜ao ´e uma t´ecnica que identifica, a partir
do conjunto de itens que ocorrem freq
¨
uentemente juntos em diferentes transa¸c˜oes,
qual a rela¸c˜ao existente entre estes itens. O uso desta t´ecnica para sele¸c˜ao de
caracter´ısticas trata cada do cumento como se fosse uma transa¸c˜ao e identifica os
termos que ocorrem juntos com maior freq
¨
uˆencia. Os algoritmos de agrupamento
propostos por (Beil et al., 2002) e (Fung et al., 2003) adotam esta t´ecnica e, a par-
tir dos termos freq
¨
uentes selecionados, realizam o agrupamento al´em de utiliz´a-los
para realizar a descri¸c˜ao dos grupos formados.
Nas duas subse¸c˜oes seguintes abordam-se as t´ecnicas utilizadas de ponde-
ra¸c˜ao da importˆancia de cada termo e como selecion´a-los. Os dois algoritmos de
sele¸c˜ao de caracter´ısticas propostos neste trabalho tamb´em se caracterizam pela
escolha de um subconjunto de termos que tenham a maior capacidade discrimina-
t´oria.
2.2.1 Pondera¸c˜ao da importˆancia dos termos
Pelo fato de determinados termos ocorrerem com freq
¨
uˆencia muito superior
a outros, o uso da freq
¨
uˆencia absoluta pode tornar desequilibrado o c´alculo da
29
similaridade entre os documentos, uma vez que estes termos se sobrep˜oem a ou-
tros que tˆem uma freq
¨
uˆencia absoluta menor, embora estes ´ultimos tenham maior
capacidade discriminat´oria entre os documentos. Para contornar este problema, ´e
adotado um processo de pondera¸c˜ao de cada termo no conjunto de documentos.
O esquema de p ondera¸c˜ao mais largamente empregado ´e o denominado de
tf × idf (do inglˆes Term Frequency × Inverse Document Frequency) (Salton et al.,
1975; Hotho et al., 2005; Liu et al., 2005) proposto por Karen Jones (Jones, 1972).
Este esquema, combina a freq
¨
uˆencia de ocorrˆencia do termo em um documento com
a freq
¨
uˆencia inversa dos documentos em que o termo ocorre. O peso idf representa
a capacidade que o termo tem para discriminar textos e ´e dado por:
idf(t
i
) = idf
i
= log
N
n
i
(2.1)
onde N ´e a quantidade total de documentos da cole¸c˜ao e n
i
´e a quantidade de
documentos onde o termo t
i
ocorre. Assim os termos que ocorrem em muitos do-
cumentos tˆem um menor peso, posto que tˆem pouca capacidade de discrimina¸c˜ao
e vice-versa.
Aplicando-se esta pondera¸c˜ao, tem-se que o termo i no documento j ser´a ca-
racterizado por w
(i,j)
= tf
(i,j)
× idf
i
que aqui ´e usado para a constru¸c˜ao da matriz
documento-termo, onde tf
(i,d)
´e a freq
¨
uˆencia absoluta do termo i no documento j.
Um outro problema a ser contornado ´e a diferen¸ca de tamanhos entre os tex-
tos da cole¸c˜ao. Isto faz com que as palavras presentes em textos maiores tendam
a ter uma freq
¨
uˆencia absoluta maior. Para resolver este problema o valores das
freq
¨
uˆencias ponderadas s˜ao normalizados em rela¸c˜ao ao tamanho do vetor corres-
pondente ao texto (Hotho et al., 2005). Assim tem-se:
w
(i,j)
=
tf
(i,j)
× idf
i
n
k=1
(tf
(k,j)
× idf
k
)
2
(2.2)
30
onde n ´e o n´umero de palavras no documento j e cada w
(i,j)
´e o valor da freq
¨
uˆencia
relativa das palavras usados ao longo do processo do agrupamento dos textos aqui
discutido.
2.2.2 Medidas da importˆancia dos termos
Depois de calculada a importˆancia relativa do termo em rela¸c˜ao aos demais,
´e necess´ario quantificar a importˆancia deste termo para fins de discrimina¸c˜ao de
documentos. Entre as v´arias medidas existentes algumas s˜ao aqui detalhadas:
Freq
¨
uˆencia de Documentos (DF, do inglˆes Document Frequency):
A Freq
¨
uˆencia de Documentos (Yang e Pedersen, 1997; Ma et al., 2003; Liu
et al., 2005) indica, a partir de um conjunto de documentos, a quantidade
de documentos onde um termo espec´ıfico ocorre. Entende-se que termos
pouco freq
¨
uentes que ocorrem em poucos documentos n˜ao s˜ao relevantes
ou n˜ao afetam a eficiˆencia do processo de agrupamento. Este ´e um crit´erio
simples, com uma complexidade computacional linear.
For¸ca do termo (TS, do inglˆes Term Strength):
Dado um par de documentos, a For¸ca do Termo (Wilbur e Sirotkin, 1992;
Yang e Pedersen, 1997; Ma et al., 2003) indica a probabilidade condicio-
nal de um termo t ocorrer no segundo documento d
j
, uma vez que tenha
ocorrido no primeiro documento d
i
. A TS, neste par de documentos, ´e
expressa por:
T S(t) = p(t ∈ d
j
| t ∈ d
i
) (2.3)
A m´edia dos valores de T S(t) na cole¸c˜ao de documentos representa o T S
deste termo e o valor de similaridade entre os documentos do par (d
i
, d
j
)
deve ser maior que o valor dado por um parˆametro β. Este parˆametro
determina a similaridade m´ınima entre os documentos e o valor da simi-
laridade ´e o cosseno do ˆangulo entre os vetores que representam os do-
31
cumentos (d
i
, d
j
) e ´e dado pela equa¸c˜ao 3.3. Como a similaridade deve
ser calculada para todos os pares de documentos, a complexidade desta
medida ´e de ordem quadr´atica em rela¸c˜ao ao n´umero de documentos. Um
inconveniente deste m´etodo ´e o ajuste adequado do valor para o parˆametro
β.
Contribui¸c˜ao do Termo (TC, do inglˆes Term Contribution):
A Contribui¸c˜ao do Termo (Ma et al., 2003; Liu et al., 2005) indica a contri-
bui¸c˜ao total de um termo para a similaridade entre todos os documentos.
Esta grandeza ´e expressa por:
T C(t) =
N
i=1
N
j=1, j=i
w
(t,d
i
)
× w
(t,d
j
)
(2.4)
onde w(t, d) representa o freq
¨
uˆencia ponderada definida em 2.2.1. Esta
medida foi proposta para contornar o vi´es introduzido por palavras comuns
que tenham uma DF alta por´em com uma distribui¸c˜ao uniforme sobre
diferentes grupos, uma vez que a DF assume que cada palavra tem a
mesma importˆancia em documentos diferentes.
Qualidade da Variˆancia do Termo (TVQ, do inglˆes Term Variance
Quality):
A Qualidade da Variˆancia do Termo (Dhillon et al., 2002a; Liu et al., 2005)
´e expressa por:
q(t
i
) =
n
j=1
w
2
(i,d
j
)
−
1
n
n
j=1
w
(i,d
j
)
2
(2.5)
onde n ´e o n ´umero de documentos onde o termo t
i
ocorre pelo menos uma
vez, ou seja, w
(t
i
,d
j
)
≥ 1.
Variˆancia do Termo (TV, do inglˆes Term Variance):
A medida Variˆancia do Termo (Liu et al., 2005) calcula a variˆancia de cada
32
termo no conjunto de documentos e ´e dada por:
v(t
i
) =
n
j=1
w
(i,d
j
)
− w
i
2
(2.6)
onde w
i
´e a m´edia da freq
¨
uˆencia do termo w
i
no conjunto de documentos,
expressa por:
w
i
=
1
n
n
j=1
w
(i,d
j
)
(2.7)
A id´eia b´asica desta medida ´e a mesma da TC, ou seja, contornar o vi´es
introduzido por palavras comuns, que tenham alta freq
¨
uˆencia mas com
distribui¸c˜ao uniforme sobre diferentes grupos. Uma palavra que ocorre em
poucos documentos ou tem uma distribui¸c˜ao uniforme ter´a um baixo valor
de TV
Sele¸c˜ao de Termo Indexador (E):
Para a sele¸c˜ao dos termos proposta por (Borgelt e N
¨
urnberger, 2004) ´e
calculada a entropia E de cada palavra. Palavras que ocorrem em muitos
documentos possuem uma pequena capacidade discriminat´oria, portanto
ter˜ao uma baixa entropia. Por outro lado, palavras cuja entropia for alta
ter˜ao maior capacidade discriminat´oria. A entropia do termo i ´e dada por:
e
i
= 1 +
1
log
2
n
n
j=1
p
(i,j)
log
2
p
(i,j)
, (2.8)
onde a probabilidade p
(i,j)
´e calculada por:
p
(i,j)
=
tf
(i,j)
n
l=1
tf
(i,l)
(2.9)
Ordena¸c˜ao baseada na Entropia (En):
Nesta medida, a qualidade de uma palavra ´e obtida pelo c´alculo da redu¸c˜ao
da entropia entre todos os documentos, quando o termo ´e removido (Dash
e Liu, 2000; Ma et al., 2003). O c´alculo da redu¸c˜ao de entropia associada
33
ao termo t ´e dado por:
E(t) = −
N
i=1
N
j=1
S
i,j
× log(S
i,j
) + (1 − S
i,j
) × log(1 − S
i,j
) (2.10)
onde S
i,j
´e a similaridade entre o documento d
i
e d
j
expressa por:
S
i,j
= e
−α×dist
i,j
(2.11)
onde α ´e dada por:
α = −
ln(0.5)
dist
(2.12)
e dist
i,j
´e a distˆancia entre o documento d
i
e d
j
depois que a palavra t ´e
removida, e dist ´e o valor m´edio dessas distˆancias. A complexidade do c´al-
culo da entropia En ´e quadr´atica em rela¸c˜ao `a quantidade de documentos.
Dois trabalhos comparam algumas destas medidas (Ma et al., 2003; Liu
et al., 2005). Em Ma et al. (2003) s˜ao comparadas as medidas DF, En, TS e
TC. Usando-se estas duas ´ultimas medidas, foram obtidos melhores resultados dos
agrupamentos de textos realizados a partir do conjunto de caracter´ısticas seleci-
onadas, e os autores concluem que a medida TC ´e mais vantajosa em fun¸c˜ao do
menor custo computacional de seu c´alculo em rela¸c˜ao ao custo da TS. Em Liu
et al. (2005) s˜ao comparadas as medidas DF, TVQ,TC e TV, e os resultados dos
agrupamentos de textos foram melhores, de acordo com as medidas de avalia¸c˜ao
de qualidade utilizadas, com as duas ´ultimas medidas, com uma ligeira vantagem
para a TC.
De todas as medidas listadas acima, apenas a E (Borgelt e N
¨
urnberger, 2004)
n˜ao foi comparada com outras, de modo que n˜ao se tˆem elementos para avaliar o
seu comportamento em rela¸c˜ao as demais.
34
2.2.3 Algoritmos de sele¸c˜ao de caracter´ısticas
A Contribui¸c˜ao do Termo (TC) ´e a medida de importˆancia dos termos que
apresentou os melhores resultados, considerando-se a avalia¸c˜ao relatada nos tra-
balhos (Ma et al., 2003; Liu et al., 2005). Em fun¸c˜ao destes resultados, o TC ´e a
medida usada nos algoritmos de sele¸c˜ao de caracter´ısticas propostos e implemen-
tados nesta disserta¸c˜ao, que s˜ao descritos em detalhes nas se¸c˜oes 2.2.3.1 e 2.2.3.2.
Ressalta-se que nestes algoritmos podem ser utilizadas qualquer outra medida de
avalia¸c˜ao da importˆancia das palavras.
A id´eia central nos dois algoritmos de sele¸c˜ao propostos ´e realizar a sele¸c˜ao
de um subconjunto m´ınimo de caracter´ısticas que seja capaz de representar a todos
os documentos de uma cole¸c˜ao.
2.2.3.1 Algoritmo para sele¸c˜ao de termos
O primeiro algoritmo apresentado ´e um algoritmo guloso para sele¸c˜ao de ter-
mos, que caracteriza-se por selecionar os termos mais importantes para discriminar
um conjunto de documentos. A partir do c´alculo da TC (2.4) e ordena¸c˜ao decres-
cente das palavras de acordo com esta grandeza, seleciona-se o n´umero m´ınimo de
termos que representem todos os documentos da cole¸c˜ao, ou seja, garante-se que
todos os documentos possuam pelo menos um termo que tenha freq
¨
uˆencia maior
que zero, gerando uma nova matriz documento-termo. No algoritmo 1 (p´agina 36)
´e mostrado o detalhamento desta prop osta.
2.2.3.2 Algoritmo iterativo para sele¸c˜ao de termos
Uma estrat´egia alternativa `a utilizada no algoritmo 1 ´e a que envolve um
algoritmo iterativo para a sele¸c˜ao de palavras. Este segundo algoritmo proposto,
da mesma forma que o anterior, usa o TC como medida de importˆancia dos termos.
35
Algoritmo 1 Sele¸c˜ao de termos
Entrada: Matriz documento-termo A = N
D
× N
T
Sa´ıda: Matriz documento-termo reduzida B = N
D
× N
T s
In´ıcio
1) Calcule a contribui¸c˜ao TC (2.4) dos termos
2) Ordene decrescentemente os termos de acordo o TC
3) Selecione o n´umero m´ınimo de termos que representem todo o conjunto de
documentos
4) Gera a matriz documento-termo B com as palavras selecionadas
Fim
Neste algoritmo, a cada itera¸c˜ao o TC de cada termo ´e calculado. S˜ao
selecionados os L termos com o maior valor de TC, que juntamente com os docu-
mentos correspondentes s˜ao removidos da matriz documento-termo. Este processo
´e repetido at´e que n˜ao restem mais documentos na matriz original. Assim s˜ao
selecionados n × L termos, onde n ´e o n´umero de itera¸c˜oes o corridas. Com estes
termos selecionados, uma nova matriz documento-termo ´e gerada. Este algoritmo
(denominado aqui de 2) ´e detalhado na p´agina 37. Observe-se que o algoritmo 1
´e um caso particular do algoritmo 2, se L = ∞.
Uma caracter´ıstica importante deste algoritmo ´e a liberdade de escolha do
valor do parˆametro L, pois para diferentes valores s˜ao geradas diferentes matrizes
documento-termo, portanto ´e poss´ıvel utilizar esta caracter´ıstica para se obter me-
lhores resultados do agrupamento de textos.
Espera-se que com o conjunto de termos selecionados pelo algoritmo 2, os
algoritmos de agrupamento apresentem um melhor desempenho considerando o
aspecto do custo computacional, tanto em rela¸c˜ao ao tempo de processamento,
quanto em rela¸c˜ao ao espa¸co de mem´oria ocupado. Espera-se tamb´em que eles
sejam competitivos, de acordo com o resultado do agrupamento, ao serem compa-
rados com os resultados obtidos ao se utilizar o algoritmo 1 e outras t´ecnicas de
sele¸c˜ao de caracter´ısticas.
36
Algoritmo 2 Sele¸c˜ao iterativa de termos
Entrada: Matriz documento-termo A = N
D
× N
T
, L
Sa´ıda: Matriz documento-termo reduzida B = N
D
× N
T s
In´ıcio
1) Calcule a contribui¸c˜ao TC (2.4) dos termos de A
2) Ordene decrescentemente os termos de acordo o TC
3) Selecione L termos com maior TC, colocando-as na lista S
4) Remova de A os documentos (linhas) representados por S e os termos (colu-
nas) associados a S
5) Se A n˜ao cont´em mais documentos, execute o passo 6. Caso contr´ario volte
ao passo 1.
6) Gera a matriz de documento-termo B contendo os documentos e os termos
da lista S
Fim
Estes dois algoritmos s˜ao utilizados para selecionar os termos das cinco bases
apresentadas nas tabelas 2.1 e 2.4. Na tabela 2.5 s˜ao mostrados os tempos de exe-
cu¸c˜ao, a quantidade e o percentual de termos selecionados. Os tempos de execu¸c˜ao
do algoritmo de sele¸c˜ao iterativo s˜ao bem maiores que os tempo de execu¸c˜ao do
algoritmo guloso. Este comportamento pode ser explicado pois a cada itera¸c˜ao o
primeiro algoritmo deve recalcular o TC dos termos restantes.
Esta tabela demonstra a grande redu¸c˜ao do n´umero de termos utilizados para
a constru¸c˜ao das matrizes documento-termo, a partir da sele¸c˜ao de caracter´ısticas.
Uma caracter´ıstica comum ao uso das medidas de importˆancia dos termos,
nos trabalhos descritos em (Dhillon et al., 2002a; Ma et al., 2003; Borgelt e N
¨
urn-
berger, 2004; Liu et al., 2005) ´e a ordena¸c˜ao decrescente dos termos pelos seus
respectivos valores de importˆancia. A partir da´ı, ´e escolhido um n´umero arbitr´ario
de termos com maior valor de importˆancia para formarem o subconjunto de carac-
ter´ısticas que s˜ao usadas na composi¸c˜ao da matriz documento-termo.
Nos testes realizados em (Dhillon et al., 2002a) com a medida TVQ foram
usados 600, dentre um total de 4099 termos, existentes na matriz documento-
37
Sel. gulosa Sel. iterativa
A
Base Termos Tempo Termos Percentual Tempo Termos Percentual
R01 5666 0,92 58 1,02% 7,43 38 0,67%
R02 7735 1,58 169 2,18% 28,33 83 1,07%
R03 6316 1,16 185 2,93% 14,04 55 0,87%
R04 3572 0,46 28 0,78% 3,07 33 0,92%
S01 7272 1,20 99 1,36% 38,96 116 1,60%
Tabela 2.5: Tempos de execu¸c˜ao, em segundos, dos algoritmos de sele¸c˜ao de carac-
ter´ısticas, quantidade e percentual de termos selecionados. (A) Valor do parˆametro
L = 1
termo, para compor a nova matriz. Os resultados obtidos com o algoritmo de
agrupamento foram ligeiramente inferiores que os obtidos com o uso da matriz
documento-termo inicial.
No estudo feito por (Liu et al., 2005) variou-se, de aproximadamente 100%
a 4% do total de termos, o percentual de termos escolhidos para comporem a ma-
triz documento-termo. Com estas matrizes, n˜ao ocorreram perdas no desempenho
do algoritmo de agrupamento de textos, quando estas continham pelo menos 30%
dos termos em rela¸c˜ao a quantidade inicial. Em (Ma et al., 2003) os testes foram
semelhantes e os resultados pr´oximos.
Na abordagem proposta em (Borgelt e N
¨
urnberger, 2004), o processo ´e mais
sofisticado, uma vez que existe a preo cupa¸c˜ao de que todos os documentos estejam
representados ap´os sele¸c˜ao das caracter´ısticas, evitando-se que ocorra uma sub-
representa¸c˜ao dos documentos. Mesmo assim, o algoritmo exige que a quantidade
de termos seja determinada previamente para compor o conjunto de caracter´ısticas
selecionadas.
Existem outras abordagens semelhantes: em (Klose et al., 2000), utilizou-se
a entropia E e escolheu-se um n´umero fixo de palavras entre as que tenham uma
alta freq
¨
uˆencia e alta entropia. Em (Larsen e Aone, 1999) foram escolhidas as 25
palavras com a maior DF, ponderada pelo tf × idf.
38
Nos m´etodos de sele¸c˜ao de caracter´ısticas que ordenam termos em fun¸c˜ao do
seu peso e que definem uma quantidade arbitr´aria para serem selecionados podem
ocorrer dois problemas: a sub-representa¸c˜ao, quando o n´umero de termos selecio-
nados ´e insuficiente para representar todos os documentos ou a super-representa¸c˜ao
quando o n´umero de termos ´e maior que o necess´ario, causando esfor¸co computaci-
onal desnecess´ario. Os dois algoritmos propostos tentam contornar esta limita¸c˜ao,
ao selecionar um n´umero de termos que s˜ao suficientes para representar todos os
documentos.
Como resultado espera-se que a matriz documento-termo possa ser sensivel-
mente reduzida e mesmo assim manter a capacidade de representa¸c˜ao/discrimina¸c˜ao
do conjunto de documentos para fins de o agrupamento de textos.
Neste cap´ıtulo foram descritas a etapa de pr´e-processamento, abordando-se
a segmenta¸c˜ao dos textos, a exclus˜ao de palavras e a remo¸c˜ao de sufixos, e a etapa
de sele¸c˜ao de caracter´ısticas de uma cole¸c˜ao de documentos. Estas duas etapas
s˜ao necess´arias para preparar uma cole¸c˜ao de documentos para o agrupamento.
Apresentaram-se diversas medidas de importˆancia dos termos, que s˜ao utilizadas
nos processo de sele¸c˜ao de caracter´ısticas. Para a sele¸c˜ao de caracter´ısticas foram
apresentados dois algoritmos para a sele¸c˜ao de um n´umero m´ınimo de termos ne-
cess´arios a fim de representar os documentos de uma cole¸c˜ao. No pr´oximo cap´ıtulo
s˜ao descritos algoritmos de agrupamento de dados, especialmente os algoritmos
utilizados para o agrupamento de do cumentos neste trabalho. No cap´ıtulo 4 s˜ao
abordados os testes realizados, com algoritmos de agrupamento de dados.
39
Cap´ıtulo 3
T´ecnicas de agrupamento de dados
A an´alise de grupos, conhecida como Agrupamento de Dados, ´e uma das
mais importantes e essenciais t´ecnicas de an´alise de dados (Berkhin, 2006), e seu
objetivo ´e organizar um conjunto de dados em grupos, de modo que aqueles con-
siderados semelhantes compartilhem o mesmo grupo. Para um conjunto de dados
X = {x
1
, x
2
, x
3
, . . . , x
n
}, o pro cedimento de agrupamento consiste em gerar um
conjunto de k grupos C = {C
1
, C
2
, C
3
. . . , C
k
} de forma que cada grupo C
i
conte-
nha os elementos x que sob algum crit´erio sejam similares.
Os grupos identificados s˜ao potenciais classes existentes em um conjunto de
dados (Tan et al., 2005). O agrupamento de dados ´e um processo de aprendiza-
gem em geral n˜ao supervisionado, pois ´e realizado sem que se tenha conhecimento
pr´evio de amostras dos grupos a serem identificados (Russel e Norvig, 2004; Tan
et al., 2005).
As t´ecnicas de agrupamento de dados apresentam numerosas aplica¸c˜oes em
diversas disciplinas: ecologia, economia, geociˆencias, medicina, biologia, ciˆencias
pol´ıticas, bioinform´atica, computa¸c˜ao gr´afica, minera¸c˜ao de dados, minera¸c˜ao de
textos etc (Kaufman e Rousseeuw, 1990; Berkhin, 2006).
De modo geral o agrupamento de dados envolve os seguintes passos (Jain e
40
Dubes, 1988):
(1) Representa¸c˜ao dos dados, incluindo ou n˜ao a extra¸c˜ao ou sele¸c˜ao de carac-
ter´ısticas;
(2) Defini¸c˜ao de medidas de similaridade apropriadas para os dados;
(3) Agrupamento propriamente dito;
(4) Abstra¸c˜ao dos dados, ou seja como os grupos formados s˜ao rotulados e
apresentados e
(5) Medi¸c˜ao da qualidade do agrupamento produzido.
Ao longo deste cap´ıtulo s˜ao apresentadas as medidas de similaridade geral-
mente utilizadas, s˜ao discutidos alguns algoritmos de agrupamento e as medidas
de qualidade mencionadas.
3.1 Medidas de similaridade
Os algoritmos de agrupamento identificam a semelhan¸ca entre os objetos de
uma cole¸c˜ao e sob algum crit´erio determinam em que grupo cada um destes deve
ser alocado. Tal semelhan¸ca ´e computada atrav´es da medi¸c˜ao da distˆancia ou simi-
laridade entre os objetos. Estas medidas s˜ao complementares, pois se dois objetos
est˜ao distantes, s˜ao pouco similares e vice-versa.
A cada objeto que se quer agrupar, geralmente ´e associado um vetor com
n dimens˜oes pertencente ao espa¸co
n
onde cada dimens˜ao representa uma das
caracter´ısticas que descrevem este objeto. Deste modo as medidas de similaridade
dos objetos s˜ao calculadas em fun¸c˜ao destes vetores de caracter´ısticas.
As duas medidas mais utilizadas para o c´alculo da similaridade entre objetos
s˜ao a Distˆancia Euclideana e o Cosseno do ˆangulo φ (Jain e Dubes, 1988; Kaufman
41
e Rousseeuw, 1990).
A Distˆancia Euclideana ´e um caso particular da m´etrica de Minkowski ou
norma-p. A m´etrica Minkowski, para os objetos x
i
e x
j
com N dimens˜oes ´e definida
por:
d(x
i
, x
j
) = (
N
k=1
|x
ik
− x
jk
|
p
)
1
p
(3.1)
E a Distˆancia Euclideana, onde p = 2 ´e definida por:
d(x
i
, x
j
) =
(
N
k=1
|x
ik
− x
jk
|
2
) (3.2)
Uma limita¸c˜ao apresentada pelo uso da distˆancia euclideana, ´e a tendˆencia
de que caracter´ısticas que tenham valores elevados se tornem dominantes. Uma
solu¸c˜ao para este problema consiste na normaliza¸c˜ao dos valores das caracter´ısti-
cas, fazendo com que a norma euclideana de cada objeto x seja igual a 1.
O Cosseno do ˆangulo ϕ, formado entre os dois vetores x
i
e x
j
no espa¸co
n
, expressa a similaridade entre os objetos representados por estes vetores. Esta
medida ´e dada por:
cos ϕ =
< x
i
, x
j
>
x
i
· x
j
(3.3)
onde < ., . > representa o produto interno dos vetores e representa a norma do
vetor.
Se os vetores x
i
e x
j
estiverem normalizados, como ´e usual, esta medida de
42
similaridade se reduz a:
cos(ϕ) = d(x
i
, x
j
) =< x
i
, x
j
> (3.4)
Existem, na literatura, referˆencias ao uso de outras medidas de similari-
dade ou distˆancia usadas no agrupamento de dados: distˆancia de Manhattan ou
Citeblock, que ´e um outro caso particular da distˆancia Minkowski, onde p = 1
(Kaufman e Rousseeuw, 1990; Bolshakova e Azuaje, 2003; Filippone et al., 2006);
distˆancia de Mahalanobis (Jing et al., 2006); Correla¸c˜ao de Pearson (Kaufman e
Rousseeuw, 1990) e Divergˆencia de Bregman (Banerjee et al., 2005), dentre outras
medidas. Estas medidas no entanto s˜ao pouco utilizadas, e para o agrupamento
de textos, as medidas mais comumente encontradas na literatura s˜ao a distˆancia
euclideana e o cosseno de ϕ.
3.2 Algoritmos para agrupamento de dados
Os algoritmos de agrupamento geralmente s˜ao classificados de acordo com a
abordagem utilizada para a gera¸c˜ao dos grupos e a forma de como s˜ao apresentados
os resultados (Jain et al., 1999; Tan et al., 2005). Uma vez que existe uma grande
quantidade de estrat´egias de agrupamento e em muitas abordagens estas estrat´e-
gias s˜ao complementares, a classifica¸c˜ao destes algoritmos tende a ser arbitr´aria.
Mesmo assim serve de guia para o seu entendimento e na escolha do m´etodo mais
apropriado para um determinado problema.
´
E importante salientar que n˜ao existe uma t´ecnica universal de agrupamento
que seja capaz de identificar grupos em qualquer tipo de dados. Os conjuntos de
dados apresentam diferentes caracter´ısticas que determinam o comp ortamento das
diferentes t´ecnicas. Trˆes aspectos s˜ao determinantes: o tamanho do conjunto de
dados, o n´umero de caracter´ısticas que cada dado p ossui e a natureza geom´etrica
da sua separabilidade. As diferentes t´ecnicas de agrupamento devem considerar
43
estes aspectos.
Em (Jain et al., 1999) ´e apresentada uma taxonomia, que organiza os algo-
ritmos de agrupamento em duas categorias principais: algoritmos hier´arquicos e
algoritmos de particionamento. Os algoritmos hier´arquicos organizam os grupos
em ´arvores, chamadas dendrogramas, onde os grupos est˜ao organizados em n´ı-
veis. Um grupo localizado em um n´ıvel superior cont´em grupos que est˜ao no n´ıvel
inferior imediato. O n´ıvel mais baixo de um dendrograma, as folhas da ´arvore, cor-
respondem aos objetos da cole¸c˜ao. O n´ıvel mais alto, a raiz da ´arvore corresponde
a cole¸c˜ao completa. Os n´ıveis intermedi´arios correspondem aos grupos formados e
como est˜ao relacionados.
Observe-se que se um dendrograma for cortado em um determinado n´ıvel,
eliminando-se os relacionamentos entre os grupos aninhados at´e a raiz, obt´em-se
um conjunto de grupos particionados (Tan et al., 2005).
Os algoritmos de particionamento organizam grupos disjuntos dos objetos
da cole¸c˜ao, sem criar relacionamentos entre os grupos, como s˜ao criados nos algo-
ritmos hier´arquicos. Na aloca¸c˜ao dos objetos aos grupos, a verifica¸c˜ao de todas
as poss´ıveis combina¸c˜oes ´e computacionalmente invi´avel e assim este tipo de algo-
ritmo geralmente busca solu¸c˜oes de forma iterativa (Berkhin, 2006).
Esta mesma classifica¸c˜ao apresentada por (Jain et al., 1999) ´e complemen-
tada por outras ab ordagens que s˜ao utilizadas pelos diferentes algoritmos de agru-
pamento, a saber:
Aglomerativa X divisiva: Os algoritmos aglomerativos iniciam o processo de
agrupamento com grupos unit´arios e, iterativamente os agrupa. Os algo-
ritmos divisivos iniciam o processo com um ´unico grupo e realizam suces-
sivas divis˜oes. Em ambos os casos o processo se repete at´e que o crit´erio
44
de t´ermino seja satisfeito.
Aloca¸c˜ao dos dados: Apesar da maioria dos algoritmos de agrupamento promo-
ver uma parti¸c˜ao nos dados, existem algoritmos que permitem sobreposi¸c˜ao
entre grupos, ou seja, um mesmo dado p ode ser alocado a dois ou mais
grupos ao fim do processo de agrupamento. Os algoritmos que utilizam
l´ogica nebulosa (do inglˆes Fuzzy) s˜ao um exemplo de estrat´egia que alo ca
um mesmo objeto a todos os grupos, determinando para cada objeto o
seu n´ıvel de pertinˆencia ao grupo. Um outro aspecto relacionado a alo-
ca¸c˜ao dos dados ´e discutido por (Tan et al., 2005) e se refere a se todos
os dados s˜ao agrupados, quando se tem um agrupamento completo, ou se
alguns dados n˜ao s˜ao agrupados, quando se tem um agrupamento parcial.
O agrupamento parcial ´e usado quando se deseja eliminar dados ruidosos
do conjunto. Alguns algoritmos baseados na densidade de distribui¸c˜ao dos
objetos s˜ao um exemplo de estrat´egia que elimina os objetos que sob algum
crit´erio sejam considerados como ru´ıdo.
Determin´ıstico X Estoc´astico: Esta abordagem est´a relacionada geralmente a
algoritmos de particionamento e se refere se a busca da solu¸c˜ao ´e determi-
n´ıstica ou estoc´astica.
Alguns autores estendem a classifica¸c˜ao proposta por (Jain et al., 1999) in-
cluindo, ao lado dos algoritmos hier´arquicos e de particionamento, os algoritmos
baseados na densidade de objetos (He et al., 2002; Berkhin, 2006). Esses ´ultimos
tˆem como fundamento a separa¸c˜ao dos grupos de acordo com as diferen¸cas de
densidade em ´areas adjacentes. Um grupo ´e definido como um componente que
conecta os objetos de uma regi˜ao densa e que cres¸ca em todas as dire¸c˜oes em que
a densidade se mant´em acima de um determinado limiar.
Este tipo de algoritmo ´e um caso particular dos algoritmos de particiona-
mento, na medida que ele produz grupos disjuntos de objetos e ´e fortemente indi-
45
cado para conjunto de dados que n˜ao sejam linearmente separados, como o exemplo
mostrado na figura 3.1 e s˜ao normalmente utilizados para o agrupamento de dados
espaciais (Berkhin, 2006). Um algoritmo bem conhecido ´e o DBSCAN (Density-
based Spatial Clustering of Applications with Noise) (Ester et al., 1996) que realiza
o agrupamento de dados espaciais em presen¸ca de ru´ıdo.
Figura 3.1: Exemplo de um conjunto de dados com duas dimens˜oes e diferentes
densidades de distribui¸c˜ao dos pontos. As ´areas cinzas cont´em uma alta densidade
de pontos
Os algoritmos baseados em grade e os algoritmos de particionamento de gra-
fos s˜ao adicionados a esta lista por (Berkhin, 2006; Tan et al., 2005).
Os algoritmos baseados em grade dividem o espa¸co onde est˜ao os dados a
serem agrupados em regi˜oes, armazenando informa¸c˜oes sobre cada uma destas, a
partir das quais as opera¸c˜oes de agrupamento s˜ao realizadas. Este tipo de algo-
ritmo ´e indicado para o agrupamento de dados espaciais e uma aplica¸c˜ao comum ´e a
constru¸c˜ao de sistemas que respondam a consultas sobre bases deste tipo de dado.
O algoritmo STING (Statistical Information Grid-based method), que armazena
informa¸c˜oes estat´ısticas sobre cada regi˜ao, ´e um exemplo de uma implementa¸c˜ao
deste tipo de algoritmo (Wang et al., 1997).
46
Nas subse¸c˜oes seguintes s˜ao descritos com maior detalhe: i) o algoritmo de
particionamento k-means, que ´e o algoritmo mas utilizado em diferentes aplica-
¸c˜oes de agrupamento de dados, ii) algoritmo kernel k-means e o algoritmo kernel
k-means ponderado, iii) o algoritmo de agrupamento espectral e iv) algoritmos de
particionamento de grafos.
3.2.1 Algoritmo K-means
O algoritmo de particionamento mais conhecido e largamente utilizado ´e o
algoritmo K-means (MacQueen, 1967), por dois motivos principais: o primeiro ´e
a sua facilidade de implementa¸c˜ao e o segundo ´e o seu baixo custo computacional,
uma vez que a sua complexidade ´e O(nkl), onde n ´e o n´umero de objetos, k ´e o
n´umero de grupos e l ´e o n´umero de itera¸c˜oes (Choudharil et al., 2005).
O algoritmo k-means promove o particionamento de um conjunto de objetos
X = {x
1
, x
2
, x
3
, . . . , x
n
}, em k grup os disjuntos, C = {C
1
, C
2
, C
3
, . . . , C
k
}. Cada
grupo v ´e caracterizado por um ponto central m
v
, chamado de centr´oide. Con-
siderando que a medida de similaridade utilizada seja a distˆancia Euclideana, o
algoritmo k-means pro cura formar os grupos de modo que a fun¸c˜ao objetivo:
f(x) =
k
v=1
x
i
∈C
v
x
i
− m
v
2
(3.5)
seja minimizada. Se a medida de similaridade ´e o cosseno do ˆangulo ϕ formado
entre os dois vetores x
i
e c
k
, a fun¸c˜ao objetivo:
f(x) =
k
v=1
x
i
∈C
v
< x
i
, m
v
>
x
i
m
v
(3.6)
deve ser maximizada.
Pode ser demonstrado que o centr´oide m
v
que otimiza o valor da fun¸c˜ao f
para uma cole¸c˜ao fixa de pontos ´e a m´edia aritm´etica dos vetores que pertencem
47
ao grupo v. Assim o centr´oide ´e expresso por:
m
v
=
1
n
v
x
i
∈C
v
x
i
(3.7)
onde n
v
´e o n´umero de pontos no grupo v.
Existem referˆencias que citam o algoritmo k-means como tendo sido pro-
posto por (Forgy, 1965). De fato, a diferen¸ca entre os algoritmos propostos por
MacQueen e Forgy ´e m´ınima e est´a localizada no momento em que o centr´oide
de cada grupo ´e calculado. Segundo (Kaufman e Rousseeuw, 1990) no algoritmo
proposto por MacQueen, os centr´oides, dos grupos de origem e de destino, s˜ao
computados no momento da mudan¸ca de um objeto de um grupo para outro, e no
algoritmo de Forgy, os centr´oides s˜ao calculados a cada itera¸c˜ao do algoritmo. No
algoritmo 3 ´e apresentado o m´etodo proposto por (Forgy, 1965).
Algoritmo 3 Agrupamento k-means
Entrada: Matriz contendo n vetores x
i
, representando objetos de uma cole¸c˜ao
qualquer.
Sa´ıda: k grupos que otimizam a fun¸c˜ao f
In´ıcio
1) Gere uma parti¸c˜ao aleat´oria de k grupos e v´a ao passo 2 ou escolha k centr´oides
e v´a ao passo 3.
2) Compute os centr´oides de cada grupo.
3) Realoque cada objeto no grupo cujo centr´oide ´e o mais pr´oximo a esse objeto
e calcule f.
4) Se o crit´erio de convergˆencia n˜ao foi atendido volte ao passo 2.
Fim
O passo 1 deste algoritmo geralmente ´e substitu´ıdo pela escolha aleat´oria de
k objetos que s˜ao os centr´oides iniciais.
´
E sabido que o algoritmo k-means tem duas grandes limita¸c˜oes. A primeira
decorre que as solu¸c˜oes encontradas geralmente convergem para ´otimo locais, e
mesmo ap´os m´ultiplas execu¸c˜oes n˜ao se consegue obter resultados que sejam me-
48
lhores, o que o torna extremamente sens´ıvel `a escolha inicial dos centr´oides. A
segunda limita¸c˜ao ´e que ele s´o apresenta boas solu¸c˜oes para conjunto de dados que
sejam linearmente separ´aveis.
Para a primeira limita¸c˜ao, diversas estrat´egias s˜ao propostas para a escolha
dos objetos que ser˜ao os centr´oides iniciais. Por exemplo, em (Cui e Potok, 2005)
´e proposto um algoritmo h´ıbrido, que une os algoritmos k-means e Particle Swarm
Optimization (PSO) (Kennedy e Eberhart, 1995). O algoritmo PSO ´e um algo-
ritmo que realiza uma busca global no espa¸co de solu¸c˜oes e esta abordagem h´ıbrida
´e utilizada para encontrar os centr´oides iniciais para o algoritmo k-means. Uma
estrat´egia semelhante ´e proposta por (Abraham et al., 2006), onde o algoritmo h´ı-
brido re´une o algoritmo k-means e o algoritmo Differential Evolution (DE) (Storn
e Price, 1997) com o mesmo prop´osito de encontrar os centr´oides iniciais.
Em rela¸c˜ao `a segunda limita¸c˜ao existem estrat´egias como o Kernel K-means,
algoritmos de agrupamento espectral e algoritmos de particionamento de grafos.
O Kernel k-means mapeia os dados originais em um espa¸co
d
com um n´umero
maior de dimens˜oes, de forma que esta representa¸c˜ao se torne linearmente separ´a-
vel (Dhillon et al., 2005). Alguns algoritmos espectrais usam o espectro da matriz
de afinidades para realizar o agrupamento com o k-means. Estes m´etodos s˜ao vis-
tos com mais detalhes nas se¸c˜oes seguintes.
3.2.2 Algoritmos de particionamento kernel k-means e kernel k-
means ponderado
Na tentativa de contornar a limita¸c˜ao do m´etodo k-means em rela¸c˜ao `a sepa-
rabilidade linear, ´e comum a utiliza¸c˜ao de uma fun¸c˜ao φ :
m
→
q
, onde q > m e
assim o conjunto X ´e mapeado em um conjunto em um espa¸co de dimens˜ao maior,
onde eventualmente os grupos deste conjunto s˜ao linearmente separ´aveis (Bie e
49
Cristianini, 2004).
Uma modifica¸c˜ao do algoritmo k-means, chamada de algoritmo kernel k-
means (Scholkopf et al., 1996; Dhillon et al., 2005) usa uma fun¸c˜ao φ de modo
alternativo ao mapeamento do conjunto de dados. Da mesma forma que o algo-
ritmo k-means, este algoritmo procura os grupos de modo que a fun¸c˜ao objetivo:
f(x) =
k
v=1
x
i
∈C
v
φ(x
i
) − m
v
2
(3.8)
seja minimizada, caso a medida de similaridade seja a distˆancia Euclideana. O
valor do centr´oide m
v
´e expresso por:
m
v
=
1
n
v
x
i
∈C
v
φ(x
i
) (3.9)
Definindo um kernel K :
(q×q)
→ , de modo que K
a,b
=< φ(a), φ(b) >
demonstra-se que:
f(x) =
k
v=1
x
i
∈C
v
φ(x
i
) − m
v
2
= (3.10)
=
k
v=1
x
i
∈C
v
K
ii
−
2
|n
v
|
x
j
∈C
v
K
ij
+
1
|n
v
|
2
x
j
∈C
v
x
l
∈C
v
K
jl
(3.11)
onde K
ij
=< φ(x
i
), φ(x
j
) >
Em (Dhillon et al., 2004) ´e prop osta uma varia¸c˜ao do algoritmo Kernel K-
means, chamada de Kernel K-means Ponderado. Neste algoritmo ´e introduzido
um peso para cada objeto x
i
, expresso por w
i
. A partir da equa¸c˜ao 3.8 tem-se:
f(x) =
k
v=1
x
i
∈C
v
w
i
φ(x
i
) − m
v
2
(3.12)
50
que da mesma forma deve ser minimizada e o centr´oide c
k
´e expresso por:
m
v
=
x
i
∈C
v
w
i
φ(x
i
)
x
i
∈C
v
w
i
(3.13)
De forma totalmente semelhante tem-se que:
f(x) =
k
v=1
x
i
∈C
v
w
i
φ(x
i
) − m
v
2
= (3.14)
=
k
v=1
x
i
∈C
v
w
i
K
ii
−
2
x
j
∈C
v
w
j
K
ij
x
j
∈C
v
w
j
+
x
j
∈C
v
x
l
∈C
v
w
j
w
l
K
jl
[
x
j
∈C
v
w
j
]
2
(3.15)
Note-se que no algoritmo Kernel k-means ponderado, se todos os pesos forem
unit´arios, este se reduz ao algoritmo kernel k-means, e do mesmo mo do se a fun¸c˜ao
φ for a fun¸c˜ao identidade, este se reduz ao algoritmo k-means. Ressalte-se tam-
b´em que estes dois algoritmos apresentados tˆem a mesma limita¸c˜ao anteriormente
observada de convergir para m´ınimos locais.
Em (Dhillon et al., 2005) ´e proposta uma abordagem para se contornar o
problema da falta de globalidade das solu¸c˜oes geradas pelos m´etodos descritos
acima. Esta abordagem consiste em considerar que o problema de minimiza¸c˜ao da
fun¸c˜ao objetivo do algoritmo kernel k-means ponderado (eq. 3.12) ´e equivalente a
maximiza¸c˜ao do tra¸co (eq. 3.16) de uma determinada matriz. Definindo que:
S
v
=
x
i
∈C
v
w
i
como a soma dos pesos do grupo v;
Z ´e uma matriz n × k, onde Z
iv
=
1
√
S
v
se x
i
∈ C
v
ou 0 caso contr´ario;
Φ ´e uma matriz q × n , expressa por: Φ = [φ(x
1
) φ(x
2
) φ(x
3
) . . . φ(x
n
)]
K ´e a matriz de kernel n × n K = Φ
T
· Φ, onde K ´e sim´etrica, positiva e
definida;
51
W ´e a matriz W = diag(w
1
, w
2
, w
3
, . . . , w
n
)
˜
Y ´e a matriz n × k
˜
Y = W
1
2
· Z, onde esta matriz ´e ortogonal, ou seja,
˜
Y
T
·
˜
Y = I
k
´
E demonstrado (Dhillon et al., 2005) que:
min f(x) ⇐⇒ max
˜
Y
trace
˜
Y
T
· W
1
2
· K · W
1
2
·
˜
Y
T
(3.16)
O relaxamento da restri¸c˜ao de
˜
Y ser apenas ortogonal para se encontrar a
solu¸c˜ao para este problema ´e discutida na se¸c˜ao sobre os algoritmos de particiona-
mento de grafos.
3.2.3 Algoritmos de agrupamento espectral
Recentemente uma nova abordagem, denominada de agrupamento espectral,
tem sido utilizada para a descoberta de grupos. Inicialmente utilizada para a seg-
menta¸c˜ao de imagens, que nada mais ´e que a descoberta, em uma imagem, de
grupos de pontos que compartilham caracter´ısticas comuns (cor, brilho, contraste
etc), essa t´ecnica pode ser utilizada para agrupamento de outros tipos de dados,
como por exemplo, textos. Esta abordagem ´e fortemente indicada para o agrupa-
mento de dados que n˜ao sejam linearmente separ´aveis, para os quais algoritmos
como o k-means e outros podem n˜ao apresentar bons resultados.
Dado um conjunto de objetos, o agrupamento espectral procura resolver o
problema de dividi-los em grupos, analisando os k maiores autovetores de uma ma-
triz quadrada denominada de matriz afinidade destes objetos. Estes autovetores
refletem a estrutura de grupos que existem na cole¸c˜ao de objetos.
A matriz de afinidade ´e sim´etrica e assim seus autovalores s˜ao reais e seus
autovetores tem cada um de seus componentes associado a um objeto, uma vez
52
que a linha ou coluna i da matriz de afinidade est´a relacionada com o objeto i.
A matriz de afinidade ´e constru´ıda de modo que seu elemento (i, j) descreve
a similaridade entres os objetos i e j. Esta similaridade pode ser definida de v´arias
formas, por´em a mais comum ´e a dada pela fun¸c˜ao kernel RBF (Radial Basis
Function) (Weiss, 1999), tamb´em conhecida como kernel gaussiano:
R
(i,j)
= exp
−d(i,j)
2σ
2
(3.17)
onde σ ´e um parˆametro livre de controle e d(i, j) ´e uma m´etrica arbitr´aria entre os
dois objetos.
Conforme descrito por (Campbell, 2000; Bie et al., 2005) o uso da fun¸c˜ao
RBF ´e indicada quando se quer agrupar dados n˜ao linearmente separ´aveis.
A escolha destes autovetores ´e um ponto que diferencia a maioria dos al-
goritmos de agrupamento espectral. Alguns algoritmos escolhem um autovetor
que divide um conjunto em dois grupos, e assim procedem sucessivamente at´e en-
contrar o n´umero desejado de grupos. Outros algoritmos escolhem o n´umero de
autovetores que corresponde ao n´umero desejado de grupos e aplica o agrupamento
diretamente sobre a matriz formada por estes vetores (Ng et al., 2001).
Em (Weiss, 1999) ´e apresentada uma revis˜ao mais aprofundada de trˆes destes
algoritmos, diferenciando-os pelo tipo de matriz utilizada, em quais autovetores s˜ao
utilizados e pela forma que o agrupamento ´e realizado a partir destes autovetores:
O algoritmo Perona e Freeman (Perona e Freeman, 1998) ´e proposto para
separar o primeiro plano de uma imagem. Este algoritmo usa o autovetor,
associado ao maior autovalor, para realizar a segmenta¸c˜ao. Neste traba-
lho ´e demonstrado que, neste autovetor, os componentes diferentes de zero
correspondem ao grupo dominante, segmentando ent˜ao o conjunto origi-
53
nal em dois grupos, que correspondem ao primeiro e segundo planos da
imagem.
O algoritmo Shi e Malik (Shi e Malik, 1997) utiliza no lugar do maior
autovetor, o segundo menor autovetor para realizar a segmenta¸c˜ao de uma
imagem em duas partes.
O algoritmo Scott e Longuet-Higgins (Scott e Longuet-Higgins, 1990) re-
cebe como entrada uma matriz de afinidades W e o n´umero de grupos
k. Constr´oi-se uma matriz V cujas colunas s˜ao os k maiores autovetores
de W . Normalizam-se as linhas de V para que a sua norma-p seja igual
a 1. Constr´oi-se a matriz Q = V V
T
. Idealmente, nesta matriz os pares
Q
(i,j)
= 1 est˜ao no mesmo grupo e os pares Q
(i,j)
= 0 est˜ao em grupos
diferentes.
Em (Ng et al., 2001) ´e apresentado um outro algoritmo que particiona o con-
junto de dados em k grupos. Este algoritmo encontra os k maiores autovalores da
matriz de afinidade, formando uma nova matriz normalizada com seus respectivos
autovetores e aplica o algoritmo k-means sobre as linhas desta matriz. Este m´e-
todo ´e apresentado em detalhes no algoritmo 4. Em (Zelnik-Manor e Perona, 2004)
tem-se uma modifica¸c˜ao neste algoritmo para automaticamente determinar o valor
´otimo do parˆametro σ e o n´umero de grupos existentes no conjunto de dados.
Este algoritmo e outros que necessitam calcular os autovetores de uma ma-
triz de afinidades tˆem dois problemas que impactam no seu custo computacional: o
primeiro ´e a constru¸c˜ao da matriz de afinidades dos objetos, que tem complexidade
computacional O(n
2
), pois ´e necess´ario que se calcule o valor da fun¸c˜ao de simila-
ridade (eq. 3.17) para cada par de objetos; o segundo ´e o c´alculo dos autovetores,
que tem a complexidade na ordem de O(n
3
). Para este segundo problema, como
n˜ao ´e necess´ario que se compute todos os autovalores, existem m´etodos iterativos,
tais como o m´etodo de Lanczos e o m´etodo de Arnoldi (Golub e Loan, 1996), que
54
Algoritmo 4 Agrupamento Espectral (Ng et al., 2001)
Entrada: Matriz de afinidade W , onde W
(i,j)
= exp
−d(i,j)
2σ
2
Sa´ıda: k grupos
In´ıcio
1) Defina D como a matriz diagonal onde o elemento (i, i) ´e a soma da linha
i-´esima de W e construa a matriz L = D
−1/2
W D
−1/2
2) Encontre os k maiores autovetores v
1
, v
2
, v
3
, . . . , v
k
da matriz L e construa a
matriz V onde sua coluna j ´e v
j
3) Construa a matriz Y a partir da normaliza¸c˜ao de cada linha da matriz V de
acordo com:
Y
ij
=
V
ij
j
V
2
ij
(3.18)
4) Execute o algoritmo k-means sobre as linhas da matriz Y
5) Atribua cada objeto S
i
para o grupo j se e somente se a linha i da matriz Y
foi atribu´ıda ao grupo j.
Fim
calculam apenas um determinado n´umero desejado de autovalores, reduzindo con-
sideravelmente o tempo computacional necess´ario (Zhukov, 2004; Wang e Zhang,
2005; Zhao e Liu, 2007; Klein et al., 2007).
3.2.4 Algoritmos de particionamento de grafos
Um grafo G ´e definido por G = (V, E), onde V representa o conjunto de
v´ertices, de tamanho n = |V| e E representa o conjunto de arestas que interligam
estes v´ertices.
Estendendo esta defini¸c˜ao, tem-se que um grafo aqui neste contexto ´e dado
por G = (V, E, A, W ), onde V e E s˜ao como na defini¸c˜ao anterior, A ´e uma ma-
triz de afinidades |V| × |V| e W ´e o vetor de pesos, com dimens˜ao |V|, onde w
i
representa a “relevˆancia” do v´ertice i. Na matriz de afinidades A, o elemento A
i,j
representa a afinidade entre os v´ertices i e j e o seu valor ´e 0 se os v´ertices i e j n˜ao
s˜ao conectados. A matriz de afinidades ´e sim´etrica e n˜ao-negativa e a afinidade
pode ser calculada usando alguma fun¸c˜ao kernel. Dentre estas, por exemplo, a
fun¸c˜ao expressa na equa¸c˜ao 3.17.
55
O problema de particionamento de um grafo consiste em descobrir grupos de
v´ertices com alguma propriedade de afinidade. Os grupos podem ser descobertos,
por exemplo, pela remo ¸c˜ao de arestas que s˜ao a liga¸c˜ao entre grupos (Shi e Malik,
1997; Berkhin, 2006). Algumas defini¸c˜oes s˜ao aqui relevantes. Sejam A e B dois
subconjuntos de V. Define-se:
links(A, B) =
ı∈A,∈B
A
ı
degree(A) = links(A, V)
w(A) =
ı∈A
w
ı
A partir destas defini¸c˜oes pode-se entender o problema do agrupamento de
um grafo como a gera¸c˜ao de uma parti¸c˜ao (V
1
, V
2
, V
3
, . . . , V
k
) de V em k grupos
de uma das seguintes formas (Dhillon et al., 2005):
(1) Maximiza¸c˜ao da soma das afinidades intra-grupos, que consiste no pro-
blema de associa¸c˜ao ponderada (Shi e Malik, 1997), expresso por:
W A(G) = max
V
1
,V
2
,V
3
,...,V
k
k
c=1
links(V
c
, V
c
)
w(V
c
)
(3.19)
(2) Minimiza¸c˜ao da soma das afinidades entre grupos, que consiste no pro-
blema do corte ponderado, expresso por:
W C(G) = min
V
1
,V
2
,V
3
,...,V
k
k
c=1
links(V
c
, V − V
c
)
w(V
c
)
(3.20)
Para cada um dos problemas acima existem ainda dois casos particulares
de interesse:
(a) Caso raz˜ao (Chan et al., 1994) - quando os pesos s˜ao unit´arios e assim
w(V
c
) = |V
c
|.
W C(G) = min
V
1
,V
2
,V
3
,...,V
k
k
c=1
links(V
c
, V − V
c
)
|V
c
|
(3.21)
56
(b) Caso normalizado (Shi e Malik, 1997) - quando w(V
c
) = degree(V
c
).
W C(G) = min
V
1
,V
2
,V
3
,...,V
k
k
c=1
links(V
c
, V − V
c
)
degree(V
c
)
(3.22)
Os problemas de associa¸c˜ao e corte ponderado podem ser melhor formaliza-
dos (Dhillon et al., 2005) definindo-se um vetor {x
c
} ∈ {0, 1}
n
onde x
c
i
= 1 se o
v´ertice i pertence ao grupo V
c
, caso contr´ario x
c
i
= 0.
´
E poss´ıvel ent˜ao mostrar
que:
W A(G) = max
{x
c
}
k
c=1
x
T
c
· A · x
c
x
T
c
· W · x
c
(3.23)
W C(G) = min
{x
c
}
k
c=1
x
T
c
· (D − A) · x
c
x
T
c
· W · x
c
(3.24)
onde D = diag(d
1
, d
2
, d
3
, . . . , d
n
), d
i
=
n
j=1
A
ij
e os x
c
’s s˜ao mutuamente ortogo-
nais.
Observe-se que L = D − A ´e conhecido na teoria espectral como o laplaciano
do grafo. Definindo o vetor ˜x
c
:
˜x
c
=
x
c
(x
T
c
· W · x
c
)
1
2
(3.25)
Ent˜ao ambos os problemas acima se reescrevem da forma:
W A(G) = max
{x
c
}
k
c=1
˜x
T
c
· A · ˜x
c
(3.26)
W C(G) = min
{x
c
}
k
c=1
˜x
T
c
· (D − A) · ˜x
c
(3.27)
57
Note-se que:
k
c=1
˜x
T
c
· Q · ˜x
c
= trace
˜x
T
1
˜x
T
2
. . .
˜x
T
k
· Q ·
˜x
1
˜x
2
. . . ˜x
k
(3.28)
Tem-se que:
˜x
1
˜x
2
. . . ˜x
k
= W
−
1
2
·
˜
Y (3.29)
onde
˜
Y ´e a mesma matriz definida na p´agina 52 na apresenta¸c˜ao do algoritmo
kernel k-means ponderado.
Logo:
W A(G) = max
˜
Y
˜
Y
T
· W
1
2
· A · W
1
2
·
˜
Y
T
(3.30)
W C(G) = min
˜
Y
˜
Y
T
· W
1
2
· (D − A) · W
1
2
·
˜
Y
T
(3.31)
As equa¸c˜oes 3.30 e 3.31 recaem no mesmo problema de otimiza¸c˜ao do tra¸co
da matriz, que ocorre quando se tenta contornar a falta de globalidade das solu¸c˜oes
geradas pelo algoritmo kernel k-means e kernel k-means ponderado.
Note-se que devido ao fato de
˜
Y ser ortogonal, tem-se que:
˜
Y
T
· W
1
2
· [W − (D − A)] · W
1
2
·
˜
Y
T
= (3.32)
˜
Y
T
·
˜
Y −
˜
Y
T
· W
1
2
· (D − A) · W
1
2
·
˜
Y = (3.33)
I
k
−
˜
Y
T
· W
1
2
· (D − A) · W
1
2
·
˜
Y (3.34)
58
Logo:
W A(G) = max
˜
Y
˜
Y
T
· W
1
2
· A · W
1
2
·
˜
Y
T
(3.35)
W C(G) = max
˜
Y
˜
Y
T
· W
1
2
· (A + W − D) · W
1
2
·
˜
Y
T
(3.36)
As formula¸c˜oes representadas pelas equa¸c˜oes 3.35 e 3.36 s˜ao idˆenticas sob o
ponto de vista conceitual e idˆenticas `a equa¸c˜ao 3.16. Esta demonstra¸c˜ao (Dhillon
et al., 2005) apresenta a equivalˆencia entre estes dois tipos de algoritmos de agru-
pamento, kernel k-means e particionamento de grafos.
Se a restri¸c˜ao de que a matriz
˜
Y seja ortogonal for relaxada, este problema
tem solu¸c˜ao global conhecida. Pode-se mostrar que esta solu¸c˜ao ´otima ´e dada por:
Y
opt
= V
k
·
ˆ
Q (3.37)
onde
ˆ
Q ´e uma matriz k × k ortogonal arbitr´aria e V
k
´e uma matriz formada pelos
k autovetores de W
1
2
· K · W
1
2
associados aos seus maiores autovalores.
Apesar da globalidade desta solu¸c˜ao, esta solu¸c˜ao ´e obtida a partir da relaxa-
¸c˜ao do problema inicial. A partir desta solu¸c˜ao, pode-se ser a gerada a solu¸c˜ao para
o problema original. Em (Dhillon et al., 2005) ´e apresentado o processamento de
Bach e Jordan, dentre outras estrat´egias, para encontrar a solu¸c˜ao do problema ini-
cial. Este processamento aplica o algoritmo k-means nas linhas da matriz W
−
1
2
·V
k
.
A partir da estrat´egia de processamento de Bach e Jordan, os algoritmos de
particionamento de grafos de associa¸c˜ao ponderada, corte ponderado e associa¸c˜ao
normalizada s˜ao constru´ıdos.
59
3.3 Medidas de avalia¸c˜ao da qualidade do agrupamento
Diferentemente do aprendizado supervisionado (onde existem conjuntos de
dados previamente classificados que s˜ao usados para treinamento do algoritmo de
classifica¸c˜ao e que podem posteriormente ser utilizados para avalia¸c˜ao dos resul-
tados), as t´ecnicas de agrupamento usualmente disp˜oem de nenhuma informa¸c˜ao
sobre os poss´ıveis grupos que comp˜oem o conjunto. Isto torna mais complexa a
tarefa de se avaliar o comportamento do algoritmo e a qualidade dos seus resulta-
dos.
O avalia¸c˜ao dos resultados deve considerar tanto a qualidade de todo o agru-
pamento, quanto a qualidade de cada um dos grupos formados. Isto ´e necess´ario
uma vez que ´e poss´ıvel se obter um bom resultado global e ao mesmo tempo um
ou mais grupos que n˜ao reflitam corretamente um adequado particionamento dos
dados. Por outro lado tamb´em se pode obter um agrupamento em que alguns gru-
pos reflitam um particionamento adequado dos dados e ao mesmo tempo a medida
de qualidade global n˜ao seja elevada.
As medidas de avalia¸c˜ao mais usadas podem ser classificadas em dois gru-
pos: Medidas externas ou supervisionadas e medidas internas ou n˜ao supervisi-
onadas. Para o primeiro grupo ´e necess´ario o conhecimento de um conjunto de
dados previamente classificados para que se possa medir a qualidade dos resulta-
dos comparando-os com os associados `as classes existentes. J´a no segundo grupo,
est˜ao as medidas de an´alise da rela¸c˜ao dos dados com os grupos a que est˜ao alo-
cados e a rela¸c˜ao entre os grupos formados, medindo a coes˜ao de cada grupo e a
sua separa¸c˜ao dos demais.
60
3.3.1 Medidas Externas
Existem na literatura v´arias medidas externas concebidas para a avalia¸c˜ao
de qualidade de um agrupamento. Algumas delas s˜ao: Entropia, pureza, precis˜ao,
recall e medida-F (do inglˆes F-measure) (Tan et al., 2005), Coeficiente Jaccard,
Acur´acia M´edia, Estat´ıstica Rand,
´
Indice Fowlkes e Mallows (Liu et al., 2005; Hal-
kidi et al., 2002). Esta lista, apesar de incompleta, cont´em as medidas comumente
utilizadas.
As medidas Coeficiente Jaccard, Acur´acia M´edia, Estat´ıstica Rand e
´
Indice
Fowlkes e Mallows s˜ao usadas para medir a similaridade entre diferentes conjuntos
de dados. Neste caso, significa medir o quanto s˜ao similares as classes de um con-
junto de dados pr´e-classificados com os grupos formados ap´os o agrupamento do
mesmo conjunto. Assim se os grupos forem similares `as classes pr´e-definidas isto
significa que atingiu-se um bom agrupamento.
Essas medidas s˜ao obtidas atrav´es do relacionamento de todos os pares
de objetos, (x
u
, x
v
), do conjunto de dados com outros dois conjuntos: o con-
junto pr´e-determinado de classes P = {p
1
, p
2
, p
3
, . . . , p
k
} e o conjunto de grupos
C = {c
1
, c
2
, c
3
, . . . , c
k
} gerados pelo algoritmo de agrupamento. A partir destes
conjuntos, pode-se verificar a adequa¸c˜ao do agrupamento proposto. O total M de
pares poss´ıveis numa cole¸c˜ao de N objetos ´e expresso por:
M =
N(N − 1)
2
(3.38)
Esta cole¸c˜ao de pares de objetos pode ser particionada em quatro conjuntos
que d˜ao origem `as seguintes estat´ısticas:
a: N de pares de objetos que compartilham o mesmo grupo de C e a
mesma classe de P
b: N de pares de objetos que compartilham o mesmo grupo de C e dife-
61
rentes classes de P
c: N de pares de objetos que compartilham diferentes grupos de C e a
mesma classe de P
d: N de pares de objetos que compartilham diferentes grupos de C e
diferentes classes de P
Com os valores definidos em a, b, c e d, pode-se definir as medidas externas,
atrav´es das seguintes f´ormulas:
Estat´ıstica Rand (RS)
1
(Rand, 1971). Os valores assumidos por esta
medida situam-se entre 0, significando que o agrupamento ´e totalmente
diferente da pr´e-classifica¸c˜ao e 1, significando uma completa similaridade.
A RS ´e expressa por:
RS =
a + d
M
(3.39)
Coeficiente Jaccard. Esta medida ´e semelhante a Estat´ıstica Rand ,
apenas evita o uso da estat´ıstica d em seu c´alculo. A faixa de valores
assumidos situa-se entre 0 e 1.
J =
a
a + b + c
(3.40)
´
Indice Fowlkes e Mallows (FM) (Fowlkes e Mallows, 1983). Esta me-
dida foi proposta inicialmente para realizar a compara¸c˜ao de agrupamentos
hier´arquicos. A faixa de valores assumidos tamb´em situa-se entre 0 e 1.
F M =
a
(a + b)
·
a
(a + c)
(3.41)
Acur´acia M´edia (AA)
2
. Esta medida indica o grau de conformidade do
1
do inglˆes Rand Statistics
2
do inglˆes Averaged Accuracy
62
agrupamento com a pr´e-classifica¸c˜ao.
AA =
a
(a + c)
·
d
(b + d)
(3.42)
Todas estas quatro medidas indicam o grau de similaridade entre C e P e
portanto, valores altos indicam que o resultado do agrupamento ´e similar `a pr´e-
classifica¸c˜ao.
As medidas Precis˜ao, Recall e medida-F foram definidas inicialmente para
serem usadas na avalia¸c˜ao de sistemas de recupera¸c˜ao de informa¸c˜ao (Rijsbergen,
1979). Elas medem o qu˜ao precisa e correta ´e a opera¸c˜ao de recupera¸c˜ao de infor-
ma¸c˜ao em resposta a uma consulta, comparando os resultados com as informa¸c˜oes
pr´e-classificadas. Analogamente, quando usadas para avaliar um agrupamento,
compara-se um grupo a uma classe a este associada, a fim de se determinar o qu˜ao
preciso e correto ´e este grupo. As trˆes medidas s˜ao assim definidas, baseadas na
associa¸c˜ao de cada grupo obtido com uma classe pr´e-definida:
Precis˜ao (P): Mede a propor¸c˜ao de objetos corretamente alocados ao
grupo em rela¸c˜ao ao total de objetos deste grupo.
´
E dada pela seguinte
f´ormula:
P =
n(A)
n(A ∪ B)
(3.43)
onde n(A) ´e o n´umero de elementos do subconjunto A de acertos e n(B) ´e
o n ´umero de elementos do subconjunto B de falsos positivos e n(A ∪ B) ´e
o n´umero total de elementos do grupo.
Recall (R): Mede a propor¸c˜ao de objetos corretamente alocados a grupo
em rela¸c˜ao ao total de objetos da classe associada a este grupo. A Recall
´e dada pela seguinte f´ormula:
R =
n(A)
n(A ∪ D)
(3.44)
63
onde n(A) ´e o n´umero de elementos do subconjunto A de acertos e n(D) ´e
o n´umero de elementos do subconjunto D de falsos negativos
3
e n(A ∪ D)
´e o n´umero total de elementos da classe correspondente.
Medida-F (F):
´
E a m´edia harmˆonica entre a Precis˜ao e o Recall. Como
estas duas medidas tendem a ser inversamente proporcionais, a maximi-
za¸c˜ao da medida-F representa um bom balanceamento entre ambas. A
medida-F ´e dada pela seguinte f´ormula:
F =
2P R
P + R
(3.45)
Cada uma destas medidas ´e calculada para cada um dos grupos obtidos,
fornecendo assim a qualidade de cada grupo. A medida de avalia¸c˜ao para todo o
agrupamento, ´e obtida atrav´es do c´alculo da m´edia entre as medidas de todos os
grupos:
P
t
=
1
k
k
i=1
P
i
; R
t
=
1
k
k
i=1
R
i
; F
t
=
1
k
k
i=1
F
i
; (3.46)
onde k ´e o n´umero de grupos.
A aplica¸c˜ao destas trˆes medidas apresenta limita¸c˜oes uma vez que ´e necess´a-
rio associar um grupo a uma classe e isso nem sempre ´e um processo simples. Se no
grupo formado houver uma classe dominante, ou seja, a maioria de seus membros
pertencem a uma mesma classe, esta associa¸c˜ao ´e simples. No entanto, se para
um grupo n˜ao for poss´ıvel associar uma classe, o que ocorre por exemplo quando o
n´umero de membros deste grupo for igualmente distribu´ıdo em diferentes classes,
obviamente estas medidas n˜ao devem ser aplicadas. Mesmo com esta limita¸c˜ao
alguns trabalhos de agrupamento utilizam estas m´etricas (Larsen e Aone, 1999;
Beil et al., 2002; Fung et al., 2003; Ma et al., 2003; Stein et al., 2003; Rodrigues e
Sacks, 2004; Yoo e Hu, 2006; Zhuang e Dai, 2004).
3
Falsos negativos s˜ao elementos que deveriam ter sido alocados a um grupo e que foram
alo cados a outros grupos.
64
A Entropia (Zhao e Karypis, 2001; Yoo e Hu, 2006) mede como objetos
de diferentes classes s˜ao distribu´ıdos entre os diferentes grupos formados em um
agrupamento. Um valor de entropia pr´oximo de zero indica que o agrupamento
obtido ´e similar `a pr´e-classifica¸c˜ao do conjunto de dados.
´
E necess´ario que se
calcule a probabilidade P (i, j) de um objeto do grupo j pertencer `a classe i. Esta
probabilidade pode ser estimada por meio da medida de precis˜ao P . A Entropia ´e
dada pela seguinte f´ormula:
E = −
j
n
j
n
i
P (i, j) · log
2
P (i, j) (3.47)
onde n ´e o n´umero total de objetos e n
j
´e o n´umero de objetos no grupo j.
3.3.2 Medidas Internas
As medidas internas geralmente procuram estabelecer uma rela¸c˜ao entre a
distribui¸c˜ao dos objetos dentro de cada grupo (que representa a coes˜ao do grupo), e
a distribui¸c˜ao dos objetos ao longo de todos os grupos (que demonstra a separa¸c˜ao
entre os grupos). Um bom agrupamento ´e o que tem uma alta coes˜ao (os objetos
de um grupos s˜ao altamente similares) e tem uma alta separa¸c˜ao ( os grupos for-
mados s˜ao bem distintos).
V´arias medidas baseiam-se neste conceito. Detalham-se aqui trˆes destas me-
didas que s˜ao bastante citadas na literatura: O Coeficiente de Silhueta (SC) e os
´ındices Dunn e Davies-Bouldin.
Coeficiente de Silhueta: Este coeficiente (Kaufman e Rousseeuw, 1990)
´e baseado na id´eia de quanto um objeto ´e similar aos demais membros
do seu grupo e de quanto este mesmo objeto ´e distante dos objetos de
um outro grupo, que lhe seja o mais pr´oximo. Assim este coeficiente ´e
65
calculado para cada objeto, representando sua a rela¸c˜ao com o seu grupo.
A figura 3.2 mostra a plotagem do coeficiente de silhueta de um conjunto
de dados agrupados.
Figura 3.2: No eixo x o valor do Coeficiente de Silhueta. No eixo y cada
linha corresponde a cada objeto alocado a cada grupo
Dado um objeto i e o grupo C
j
que o cont´em, a medida de coes˜ao ´e a
distˆancia m´edia deste objeto para os demais objetos contidos no mesmo
grupo:
a(i) =
1
n
C
j
j∈C
j
,j=i
d(i, j) (3.48)
onde d(i, j) ´e uma fun¸c˜ao que expressa a distˆancia do objeto i ao objeto j
e n
C
j
´e o n´umero de objetos no grupo C
j
.
Para este mesmo objeto i, a medida da sua separa¸c˜ao para um outro grupo
C
l
. ´e dada por:
b(i) = min
l
{
1
n
l
j∈C
l
d(i, j)} (3.49)
Calculados a(i) e b(i), o Coeficiente de Silhueta s(i) do objeto i ´e definido
por:
s(i) =
b(i) − a(i)
max{a(i), b(i)}
(3.50)
66
A m´edia do coeficiente de silhueta (s
k
) para o grupo evidencia a qualidade
deste, e a m´edia do coeficiente (s) de todos os objetos evidencia a qualidade
do agrupamento. Ambas s˜ao dadas por:
s
k
=
1
n
k
n
k
i=1
s(i); s =
1
N
N
i=1
s(i); (3.51)
O valor de s(i) se situa na faixa de -1 a 1. Kaufmann e Rousseeuw estab e-
leceram uma interpreta¸c˜ao emp´ırica para os valores de s de modo a julgar
a qualidade do agrupamento:
0.70 < s ≤ 1.00 Uma evidˆencia forte de um bom agrupamento
0.50 < s ≤ 0.70 Uma evidˆencia razo´avel de um bom agrupamento
0.25 < s ≤ 0.50 Uma evidˆencia fraca de um bom agrupamento
s ≤ 0.25 Sem significado
Provavelmente estes valores foram encontrados a partir do agrupamento
de conjuntos de dados com um n´umero pequeno de dimens˜oes. Como o
coeficiente de silhueta ´e definido em termos de distˆancia, o seu valor para
cada objeto i ´e afetado se estes possu´ırem um n´umero alto de dimens˜oes.
De acordo com (Hotho et al., 2001), quando este aplicou o coeficiente de si-
lhueta para avaliar o seu algoritmo de agrupamento de documentos, o valor
do coeficiente de silhueta caiu de 0.6, quando o n´umero de dimens˜oes era
10, para abaixo de 0.25, quando o n´umero de dimens˜oes aumentou para 30.
´
Indice Dunn: Este ´ındice (Dunn, 1974) tem como princ´ıpio o fato de que
um bom agrupamento minimiza as distˆancias entre os objetos de um grupo
e maximiza a distˆancia entre os grupos. A maximiza¸c˜ao do ´ındice Dunn ´e
indicativa de um bom agrupamento. Este ´ındice ´e dado pela f´ormula:
D = min
1≤i≤c
{ min
1≤j≤c,j=i
{
δ(C
i
, C
j
)
max
1≤k≤c
{∆(C
k
)}
}} (3.52)
67
onde c ´e o n´umero de grupos, δ(C
i
, C
j
) ´e a distˆancia entre os centr´oides
dos grupos C
i
e C
j
, ∆(C
k
) a distˆancia m´edia entre os objetos do grupo k.
´
Indice Davies-Bouldin: Este ´ındice (Davies e Bouldin, 1979) utiliza o
mesmo princ´ıpio envolvido nas duas medidas anteriores. A diferen¸ca agora
´e que o valor deste ´ındice quando se aproxima de 0 representa um bom
agrupamento. O ´ındice Davies-Bouldin ´e dado pela f´ormula:
DB =
1
c
c
i=1
max
i=j
{
∆(C
i
) + ∆(C
j
)
δ(C
i
, C
j
)
} (3.53)
Estas medidas s˜ao comparadas em alguns trabalhos. Segundo (Petrovic,
2006) o Coeficiente de Silhueta e o
´
Indice Davies-Bouldin tem um comportamento
semelhante, com o primeiro tendo resultados ligeiramente melhores, no entanto a
um custo computacional maior.
Em (Kov´acs et al., 2005) ´e realizada a compara¸c˜ao dos ´ındices Dunn e Davies-
Bouldin e duas outras medidas para a avaliar o agrupamento de trˆes conjuntos de
dados distintos: o primeiro com trˆes grupos linearmente separ´aveis, o segundo com
um grupo contido em um outro com formato de anel e o terceiro com dois grupos
sem formato definidos e muito pr´oximos. Para o primeiro grupo, ambos os ´ındices
tiveram o comportamento esperado, ou seja, o ´ındice Dunn foi pr´oximo de 1 e o
´ındice Davies-Bouldin foi b em pr´oximo a 0. Para o segundo grupo, o ´ındice Dunn
teve um comp ortamento bem superior ao ´ındice Davies-Bouldin. Para o terceiro
grupo novamente o ´ındice Dunn foi superior. Este estudo parece indicar que o
´ındice Dunn pode ser apropriado para a avalia¸c˜ao de conjunto de dados que n˜ao
sejam linearmente separ´aveis.
Estas trˆes medidas podem ser usadas para estimar o n´umero de grupos em
um determinado conjunto de dados, uma vez que os melhores resultados para cada
uma delas s˜ao obtidos quando o n´umero correto de grupos ´e especificado para o
68
algoritmo de agrupamento. Esta abordagem j´a havia sido sugerida por (Kaufman
e Rousseeuw, 1990) para o Coeficiente de Silhueta.
Em (Bolshakova e Azuaje, 2003) foi realizado um extenso estudo usando es-
tas trˆes medidas como suporte `a descob erta do n´umero de grupos em um conjunto
de dados de express˜ao genˆomica. Para cada destas medidas foram utilizadas v´arias
fun¸c˜oes para o c´alculo da similaridade intra e inter grupos. Este trabalho apre-
senta bons resultados, ou seja, o n´umero ´otimo de grupos ´e determinado quando
os resultados apresentados por estes ´ındices s˜ao os melhores.
Neste cap´ıtulo abordou-se alguns algoritmos de agrupamento de dados, em
particular, os algoritmos de particionamento indicados para o agrupamento de da-
dos que n˜ao sejam linearmente separ´aveis, tais como os algoritmos kernel k-means,
espectrais e de particionamento de grafos. Por fim apresentou-se algumas medidas
de avalia¸c˜ao da qualidade do agrupamento. No pr´oximo cap´ıtulo s˜ao apresentados:
a avalia¸c˜ao dos algoritmos agrupamento k-means, esp ectral e de particionamento
de grafos e de sele¸c˜ao de caracter´ısticas a partir dos testes realizados sobre bases
de dados de documentos.
69
Cap´ıtulo 4
Resultados
4.1 Descri¸c˜ao das bases de dados
Os conjuntos de documentos utilizados nos experimentos realizados neste
trabalho s˜ao origin´arios de duas bases de documentos: Reuter21578
1
e Smart
2
.
A escolha destas bases justifica-se pois ambas s˜ao largamente utilizadas nos testes
de algoritmos de agrupamento de documentos relatados na literatura e s˜ao previ-
amente classificadas, o que permite a avalia¸c˜ao dos resultados obtidos.
A base Reuters21578 ´e uma base composta por 21758 documentos produzidos
pela agˆencia de not´ıcias Reuters em 1987 e que foram coletados com o prop´osito
de se criar uma base de teste para algoritmos de recupera¸c˜ao de informa¸c˜oes e de
classifica¸c˜ao de textos (Lewis, 1997). Para isto esta base ´e constitu´ıda por dois
grupos de documentos: um grupo utilizado no treinamento dos algoritmos, previa-
mente classificado e identificado por r´otulos e outro para os testes dos algoritmos.
O grupo de treinamento ´e dividido em cinco conjuntos de categorias: exchanges,
orgs, people, places e topics. Nos testes realizados neste trabalho s˜ao utilizados
documentos classificados no conjunto topics, que s˜ao divididos em 120 categorias
econˆomicas, que variam em tamanho de 1 a 3944 documentos. Neste conjunto
existem 9489 documentos classificados em somente um t´opico e 1870 documentos
classificados em mais de um t´opico.
1
http://www.daviddlewis.com/resources/testcollections/reuters21578/
2
ftp://ftp.cs.cornell.edu/pub/smart
70
Base N de documentos N de categorias
R01 848 11
R02 1497 5
R03 1001 7
R04 381 10
Tabela 4.1: Constitui¸c˜ao das bases de documentos Reuters
A partir de um subconjunto de documentos do grupo de treinamento topics
da base Reuters21758 constru´ıram-se quatro conjuntos de documentos, dentre os
classificados por um ´unico t´opico: R01, R02, R03 e R04. Cada um destes con-
juntos combinou documentos de diferentes categorias. Algumas destas categorias
possuem uma grande quantidade de documentos e por isto n˜ao s˜ao utilizadas inte-
gralmente. Neste caso a sele¸c˜ao de documentos que pertencem a estas categorias
foi aleat´oria. Nas tabelas 4.1 e 4.2 ´e detalhada a composi¸c˜ao de cada conjunto. A
escolha destas categorias tem o objetivo de se construir bases com diferentes com-
bina¸c˜oes de categorias com diferentes tamanhos e assim verificar o comportamento
dos algoritmos de agrupamento frente a estas caracter´ısticas.
Categoria Base R01 Base R02 Base R03 Base R04
Acq - 299(2) 199(2) -
Alum 49(5) - - 49(5)
Bop - - - 32(2)
Coffee 116(3) - 116(5) -
Cotton 26(1) - - 26(10)
Crude 403(2) 300(3) 198(3) -
Earn - 299(1) 199(1) -
Housing 18(6) - - -
Gold - - 99(6) -
Ipi - - - 48(1)
continua na pr´oxima p´agina
71
Categoria Base R01 Base R02 Base R03 Base R04
Iron-steel - - 47(7) 47(3)
Jobs 54(7) - - -
Money-fx - 300(5) - -
Nat-gas - - - 45(6)
Orange 22(8) - - -
Potato 5(11) - - -
Rubber - - - 41(7)
Sugar 143(4) - 143(4) -
Tea 6(9) - - -
Tin - - - 30(4)
Trade - 299(4) - -
Veg-oil - - - 37(8)
Wpi - - - 26(9)
Yen 6(10) - - -
Tabela 4.2: Distribui¸c˜ao dos documentos das bases Reuters por categoria. Entre
parˆenteses, o n´umero que identifica cada categoria em cada uma das bases.
A base Smart foi constru´ıda no ˆambito do projeto Smart para desenvolvi-
mento de sistemas de recupera¸c˜ao de informa¸c˜ao e ´e constitu´ıda de 7096 documen-
tos divididos em 4 categorias: cisi, cran, med e cacm. A partir destes conjuntos
construiu-se uma base com 300 documentos, escolhidos aleatoriamente, de cada
uma das categorias cisi(1), cran(2) e med(3)
3
, totalizando 900 documentos. A
categoria cacm n˜ao ´e utilizada.
3
Entre parˆenteses, o n´umero identificador da categoria
72
4.1.1 Avalia¸c˜ao das bases de documentos
Utilizando-se a visualiza¸c˜ao gr´afica de uma matriz Y gerada a partir da ma-
triz de afinidades (a matriz
4
Y ´e gerada de acordo com o algoritmo 4, descrito
na p´agina 55) de cada uma das cinco bases, pode-se estimar o comportamento do
agrupamento dos documentos de cada categoria de cada base. Nas figuras geradas,
onde cada ponto corresponde a afinidade em um par de documentos, cada catego-
ria de documentos ´e separada das outras por linhas vermelhas sendo as categorias
ordenadas crescentemente de acordo com o seu n´umero identificador. Foi feita
uma correspondˆencia entre a similaridade m´ınima entre documentos (cor preta)
e a similaridade m´axima entre documentos (cor branca), construindo-se uma es-
cala de n´ıveis de cinza entre esses valores. Os quadrados, delimitados p or linhas
vermelhas, que se estendem na diagonal da matriz, cont´em os pontos que repre-
sentam a similaridade interna (similaridade entre os pares de documentos de uma
mesma categoria) de cada uma das categorias da base. Numa situa¸c˜ao ideali-
zada, a matriz Y seria formada de blocos “claros” em sua diagonal (representando
a similaridade intra-categoria) cercada de ´areas escuras (representando a simila-
ridade inter-categorias). Para a gera¸c˜ao da matriz Y s˜ao utilizadas as matrizes
documento-termo, listadas na tabela 2.4 na p´agina 27, exclu´ıdos os termos sem va-
lor informacional e realizada a remo¸c˜ao dos sufixos. A freq
¨
uˆencia de cada termo ´e
ponderada pelo tf × idf e ´e normalizada. Cada uma destas cinco bases ´e analisada
a seguir:
R01: esta base (figura 4.1) se caracteriza por ter uma grande disparidade
nos tamanhos de suas categorias, a menor (potato(11)) com cinco documentos e
a maior (crude(2)) com 403 documentos. Dentre as onze categorias desta base,
as categorias crude(2) e sugar(4) apresentam uma similaridade entre os seus do-
cumentos baixa. Outras categorias, como a cotton(1) e alum(5) apresentam uma
similaridade interna maior, no entanto estes tamb´em apresentam uma similari-
4
A valor de σ utilizado ´e 0, 5
73
dade alta com documentos de outras categorias, conforme mostrado nos pontos
mais claros na intersec¸c˜ao destas categorias com outras. A categoria alum(5) pos-
sui documentos similares em praticamente todas as outras categorias, com exce¸c˜ao
das categorias housing(6) e jobs(7). J´a estas duas categorias praticamente se con-
fundem, pois a similaridade entre os seus documentos ´e alta. As quatro ´ultimas
categorias (orange(8), tea(9), yen(10) e potato(11)) tamb´em apresentam uma simi-
laridade alta entre os seus documentos, conforme mostrado na amplia¸c˜ao a direita.
Figura 4.1: Matriz de afinidades da base de documentos R01. 5666 termos.
A partir da an´alise desta matriz, espera-se que no agrupamento desta base,
ocorram os seguintes problemas: (1) dificuldade para encontrar grupos que corres-
pondam as categorias crude e sugar; (2) dificuldade para separar em dois grupos
as categorias housing e jobs e (3) dificuldade para separar em grupos as categorias
orange, tea, yen e potato.
R02: esta base (figura 4.2) se caracteriza por todas as suas categorias te-
rem aproximadamente o mesmo tamanho. Na categoria earn(1) em praticamente
todos os pares de documentos a similaridade ´e baixa. A categoria acq(2) interna-
74
mente tem uma similaridade alta, mas no entanto os seus documentos tamb´em s˜ao
similares aos documentos das outras quatro categorias. Por outro lado, nas cate-
goria crude(3) e trade(4) a similaridade interna ´e um pouco menor. A categoria
money-fx(5) tem uma similaridade interna bem menor e tamb´em praticamente se
confunde com a categoria trade.
Figura 4.2: Matriz de afinidades da base de documentos R02. 7735 termos.
No agrupamento destes documentos espera-se uma dificuldade maior para
separar as categorias acq, trade e money-fx e que em todos os grupos s˜ao alocados
documentos de diferentes categorias, mesmo que para cada grupo se possa identifi-
car uma categoria cujos documentos sejam majoritariamente alocados a este grupo.
R03: nesta base (figura 4.3) a categoria earn(1) apresenta comportamento
semelhante ao apresentado pela mesma categoria na base R02, com a similari-
dade interna baixa. A categoria acq(2) tamb´em tem comportamento semelhante
ao apresentado na base R02 pois tem uma similaridade interna alta e os seus do-
cumentos tamb´em s˜ao similares aos documentos de outras categorias. Nesta base,
aos documentos das categorias gold(6) e iron-steel(7), que por sua vez tamb´em se
confundem. As categorias earn(1) e crude(3) apresentam uma similaridade interna
baixa. As categorias sugar(4) e coffee(5) tem uma similaridade interna alta e n˜ao
se confundem com outras categorias.
75
Figura 4.3: Matriz de afinidades da base de documentos R03. 6316 termos.
Assim espera-se que no agrupamento destas categorias ocorram os seguin-
tes problemas: (1) dificuldade para separar em dois grupos as categorias gold e
iron-steel; (2) que os grupos associados `as categorias earn, acq e crude tenham um
n´umero elevado de documentos de outras categorias.
R04: esta base (figura 4.4) se caracteriza por ter categorias com poucos
documentos (comparando com a base R02) e terem tamanhos aproximados (as
duas menores, wpi(9) e cotton(10), com 26 documentos cada e a maior (alum(5))
com 49 documentos). A similaridade interna da maioria das categorias ´e alta e a
similaridade dos documentos de diferentes categorias ´e baixa, portanto espera-se
que no resultado do agrupamento dos documentos, os dez grupos formados sejam
claramente associados `as dez categorias.
S01: de acordo com a figura 4.5, as trˆes categorias desta base s˜ao bem
separadas, pois a similaridade interna em cada categoria ´e alta e a similaridade
entre os documentos de diferentes categorias ´e baixa.
76
Figura 4.4: Matriz de afinidades da base de documentos R04. 3572 termos.
Figura 4.5: Matriz de afinidades da base de documentos S01. 7272 termos.
4.2 Ferramentas computacionais desenvolvidas
Para a gera¸c˜ao das matrizes documento-termo a partir dos arquivos texto
que cont´em os documentos, foi utilizado o programa (CriaMatriz.pl), escrito
na linguagem de programa¸c˜ao Perl. Este programa ´e descrito na se¸c˜ao 2.1.4 do
cap´ıtulo 2. Este programa possui 5 parˆametros de entrada:
-dir: diret´orio que cont´em os arquivos texto da base de documentos;
-sfx: sufixo que ´e adicionado no nome de cada um dos quatro arquivos
gerados pelo programa - (1) arquivo com a lista de documentos, com o iden-
tificador da categoria de cada documento (se a base for pr´e-classificada);
(2) arquivo a matriz documento-termo (este arquivo cont´em a freq
¨
uˆencia
absoluta de cada termo em cada documento); (3) arquivo com a lista de
77
termos; (4) arquivo com a lista de palavras originais (com sufixos) asso-
ciadas aos termos correspondentes. Nos testes dos algoritmos de sele¸c˜ao
de caracter´ısticas e de agrupamento realizados, apenas os dois primeiros
arquivos s˜ao utilizados;
-sw: tipo de palavras sem valor informacional que s˜ao exclu´ıdas. Este
parˆametro admite dois valores - [1] para a lista do projeto Smart ou [2]
para a lista do Pubmed. Se este parˆametro for omitido, as palavras deste
tipo n˜ao s˜ao exclu´ıdas;
-s: op¸c˜ao para determinar se a remo¸c˜ao dos sufixos das palavras ´e realizada
ou n˜ao.
-pm(op cional): se o parˆametro -s for usado, este parˆametro define se a
remo¸c˜ao de sufixos ´e adaptada para tratar nomes de genes ou n˜ao.
Uma s´erie de programas foi desenvolvida no ambiente Matlab para exe-
cutar as tarefas de c´alculo do peso relativo de cada termo; sele¸c˜ao dos termos
de cada base e implementa¸c˜ao dos diferentes algoritmos de agrupamento testados
neste trabalho. Este programas s˜ao descritos a seguir:
ProcessaMatriz.m: calcula o tf × idf de cada termo, normalizando ou
n˜ao o vetor correspondente a cada documento. O c´alculo do peso e da nor-
maliza¸c˜ao s˜ao realizados conforme descrito na se¸c˜ao 2.2.1. Este programa
recebe quatro parˆametros: (1) arquivo com a lista de documentos; (2) ar-
quivo com a matriz documento-termo; (3) nome do arquivo que conter´a a
nova matriz documento-termo; (4) tipo de normaliza¸c˜ao aplicada - 0 sem
normaliza¸c˜ao ou 1 com normaliza¸c˜ao.
SelecionaTermo01.m: implementa o algoritmo guloso de sele¸c˜ao de ca-
racter´ısticas, descrito na se¸c˜ao 2.2.3.1. Este programa recebe trˆes parˆa-
metros: (1) arquivo com a lista de documentos; (2) arquivo com a ma-
triz documento-termo e (3) nome do arquivo que conter´a a nova matriz
documento-termo.
78
SelecionaTermo02.m: implementa o algoritmo iterativo de sele¸c˜ao de ter-
mos, descrito na se¸c˜ao 2.2.3.2. Este programa recebe quatro parˆame-
tros: (1) arquivo com a lista de documentos; (2) arquivo com a matriz
documento-termo; (3) n´umero de termos L selecionados por itera¸c˜ao e (4)
nome do arquivo que conter´a a nova matriz documento-termo.
Agrupamento01.m: implementa o agrupamento usando o algoritmo k-means
e calcula as medidas de avalia¸c˜ao da qualidade do agrupamento SC, AA,
RS e FM. O algoritmo k-means utilizado e o ´ındice SC s˜ao implementados
na biblioteca do Matlab (fun¸c˜oes kmeans e silhouette). Este programa
recebe seis parˆametros: (1) arquivo com a lista de documentos; (2) arquivo
com a matriz documento-termo; (3) o n´umero de execu¸c˜oes do programa;
(4) o n´umero m´ınimo de grupos; (5) o n´umero m´aximo de grupos e (6) a
medida de distˆancia utilizada.
Os dois parˆametros com o n´umero m´ınimo e m´aximo de grupos podem ser
utilizados para se estimar o n´umero de grupos existentes em uma determi-
nada base, pois se estes forem diferentes, para cada execu¸c˜ao do algoritmo
k-means, os valores das medidas de qualidade refletir˜ao o desempenho do
agrupamento. Espera-se que o melhor desempenho ocorra quando o n´u-
mero de categorias escolhido for o correto.
Ao fim da execu¸c˜ao deste programa, um arquivo ´e gerado contendo o re-
sultado do processamento expresso por uma lista dos grupos formados e os
seus documentos; os valores das medidas de avalia¸c˜ao de qualidade; uma
matriz relacionando a distribui¸c˜ao dos documentos de cada classe em cada
grupo e a dura¸c˜ao, em segundos, da execu¸c˜ao do programa.
Agrupamento02a.m: implementa o agrupamento espectral usando o algo-
ritmo 4 descrito na se¸c˜ao 3.2.3 (p´agina 55). Este programa recebe seis
parˆametros, que com exce¸c˜ao do terceiro parˆametro, s˜ao os mesmos utili-
zados pelo programa anteriormente descrito. Este parˆametro ´e utilizado
para controlar a varia¸c˜ao do valor de σ na procura do valor ´otimo, que
79
maximiza os valores das medidas de qualidade. A sa´ıda ´e a mesma do
programa anterior.
Agrupamento02b.m: ´e o programa anterior acrescido de duas modifica-
¸c˜oes. Na primeira, o terceiro parˆametro determina o n´umero de execu¸c˜oes
do programa e na segunda modifica¸c˜ao existe um s´etimo parˆametro, que
recebe o valor de σ, que pode ser o valor ´otimo, encontrado pelo programa
Agrupamento02a.m ou um outro valor qualquer. A sa´ıda ´e a mesma dos
programas anteriores.
Agrupamento03.m: implementa trˆes tipos de particionamento de grafos
(associa¸c˜ao ponderada, corte ponderado e associa¸c˜ao normalizada), des-
critos na se¸c˜ao 3.2.4. Este programa recebe sete parˆametros, que com
exce¸c˜ao do s´etimo parˆametro, s˜ao os mesmos utilizados pelo programa an-
teriormente descrito. O s´etimo parˆametro ´e usado para se determinar qual
dos trˆes tipos de algoritmo ´e utilizado.
Todos os programas foram executados em um computador Intel Pentium
4 2.80 GHz e 2GB de RAM, sob o sistema operacional Linux vers˜ao 2.6.13-15-smp.
A vers˜ao do interpretador Perl ´e a 5.8.7 e do Matlab ´e a 7.3.0.298 (R2006b).
4.3 An´alise Qualitativa do Desempenho com Sele¸c˜ao de Caracte-
r´ısticas
Para todas as cinco bases foram geradas duas novas matrizes documento-
termo: uma atrav´es da sele¸c˜ao gulosa e outra com a sele¸c˜ao iterativa de termos,
usando-se nesta o valor para o parˆametro L igual a um. Optou-se por se fixar este
parˆametro, apesar de ser de livre escolha, pois em testes preliminares os melhores
resultados dos algoritmos de agrupamento foram obtidos com os termos seleciona-
dos por este algoritmo com este valor para o parˆametro L. A quantidade de termos
de cada matriz foi apresentada na tabela 2.5 na p´agina 38. Para cada uma destas
matrizes foram geradas as matrizes de afinidade para estimar o comportamento de
80
cada base com a utiliza¸c˜ao destes dois m´etodos de sele¸c˜ao.
Na figura 4.6 ´e mostrada a visualiza¸c˜ao da base R01, com a sele¸c˜ao de 58 ter-
mos realizada atrav´es do algoritmo guloso. Nesta figura verificam-se praticamente
os mesmos problemas identificados quando ´e utilizada a matriz documento-termo
com todos os termos (figura 4.1). Na amplia¸c˜ao `a direita constata-se que aumen-
tou a similaridade entre os documentos das categorias orange(8), tea(9), yen(10)
e potato(11).
Figura 4.6: Matriz de afinidades da base R01. 58 termos.
Com o algoritmo de sele¸c˜ao iterativa de termos s˜ao selecionados 38 termos e a
partir desta matriz documento-termo ´e produzida a matriz de afinidades mostrada
na figura 4.7. Com estes termos selecionados, a maioria dos problemas identifica-
dos na matriz ilustrada na figura 4.6 s˜ao minimizados, com exce¸c˜ao da categoria
alum(5) (quinto quadrado na diagonal), na qual a similaridade interna diminuiu.
Pode ser visto na amplia¸c˜ao `a direita que a similaridade entre os documentos das
quatro ´ultimas categorias diminuiu, possivelmente aumentando, a separa¸c˜ao entre
estas. A categoria crude(2) continua apresentando problemas, apesar de em menor
81
quantidade e que se concentram nos documentos que n˜ao s˜ao similares nem com
os outros documentos desta categoria, nem com documentos das outras categorias.
Na inspe¸c˜ao destes documentos em particular, constata-se que em sua maioria s˜ao
documentos pequenos, constitu´ıdos apenas pelo t´ıtulo, sem corpo de texto.
Figura 4.7: Matriz de afinidades da base R01. 38 termos (sele¸c˜ao iterativa).
A partir da an´alise das duas matrizes documento-termo da base R01, res-
pectivamente obtidas atrav´es da sele¸c˜ao de termos, a primeira com 58 termos e a
segunda com 38 termos, ´e esperado que os resultados do agrupamento dos docu-
mentos desta base sejam melhores no segundo caso.
As figuras 4.8 e 4.9 cont´em as visualiza¸c˜oes das matrizes da base R02. Na
primeira figura, a matriz documento-termo tem 169 termos e os problemas identi-
ficados na figura 4.2 tornaram-se piores, p ois: (1) diminuiu a similaridade entre os
documentos da categoria earn; (2) aumentou a similaridade entre os documentos
da categoria acq com os documentos das categorias crude, trade e money-fx; (3)
aumentou a similaridade entre os do cumentos da categorias trade e money-fx. A
´unica melhora nesta base, com esta sele¸c˜ao de caracter´ıstica, ocorre na categoria
82
trade, onde a similaridade interna aumentou.
Na segunda figura, a matriz documento-termo tem 83 termos e diminu´ıram
um pouco os problemas identificados neste base: (1) a similaridade interna da
categoria earn aumentou; (2) diminuiu a similaridade entre os documentos das
categorias trade e money-fx. Por´em, de uma maneira geral, esta base tem o grande
problema da categoria acq ter v´arios documentos que s˜ao similares aos documentos
das categorias crude, trade e money-fx.
Figura 4.8: Matriz de afinidades da
base R02. 169 termos.
Figura 4.9: Matriz de afinidades da
base R02. 83 termos (sele¸c˜ao itera-
tiva).
A base R03, com os 185 termos selecionados por meio do algoritmo guloso,
apresenta, de acordo com a figura 4.10, um comportamento semelhante ao mos-
trado na figura 4.3. Por outro lado, com os 55 termos selecionados por meio do
algoritmo iterativo, o seu comportamento muda, conforme mostrado na figura 4.11,
pois: (1) existe um pequeno aumento na similaridade interna da categoria earn;
(2) a similaridade entre os documentos da categoria acq e as categorias gold e
iron-steel diminuiu e (3) a similaridade entre os documentos destas ´ultimas duas
categorias tamb´em diminuiu. Esp era-se que com esta ´ultima matriz os resultados
dos algoritmos de agrupamento sejam superiores aos obtidos com as outras matri-
zes.
83
Figura 4.10: Matriz de afinidades da
base R03. 185 termos
Figura 4.11: Matriz de afinidades da
base R03. 55 termos (sele¸c˜ao itera-
tiva).
As figuras 4.12 e 4.13, que correspondem `as matrizes de afinidades da base
R04, mostram que a sele¸c˜ao de caracter´ısticas apresentou pouco impacto na si-
milaridade dos documentos, sendo semelhante ao caso da figura 4.4. As exce¸c˜oes
ocorrem com a categoria tin, que com a sele¸c˜ao do algoritmo guloso, teve aumen-
tada a similaridade interna de seus documentos com os de outras categorias e com
as categoria ipi e wpi, que com a sele¸c˜ao do algoritmo iterativo, tiveram um au-
mento consider´avel da similaridade entre os seus documentos. Espera-se que com
estas matrizes, os resultados dos algoritmos de agrupamento revelem um desem-
penho semelhante com os obtidos com a matriz original.
Figura 4.12: Matriz de afinidades da
base R04. 28 termos.
Figura 4.13: Matriz de afinidades da
base R04. 33 termos (sele¸c˜ao itera-
tiva).
84
Na base S01, ap´os a sele¸c˜ao de caracter´ısticas, ocorreu um aumento da simi-
laridade entre documentos de diferentes categorias (figuras 4.14 e 4.15). Espera-se
que com estas matrizes, os resultados dos algoritmos de agrupamento sejam infe-
riores aos obtidos com a matriz original.
Figura 4.14: Matriz de afinidades da
base S01. 99 termos.
Figura 4.15: Matriz de afinidades da
base S01. 116 termos (sele¸c˜ao itera-
tiva).
4.4 Descri¸c˜ao dos testes e resultados
Nesta se¸c˜ao s˜ao descritos os testes realizados e seus resultados. Os testes tˆem
os seguintes objetivos:
(1) Determinar a melhor medida de distˆancia a ser utilizada nos algoritmos de
agrupamento para cole¸c˜oes de documentos;
(2) Verificar o impacto da sele¸c˜ao de caracter´ısticas nos algoritmos de agrupa-
mento em rela¸c˜ao aos aspectos do custo computacional e da qualidade dos
resultados;
(3) Comparar os algoritmos de agrupamento k-means, espectral e de particio-
namento de grafos no agrupamento de documentos.
A descri¸c˜ao dos testes e resultados para o primeiro item ´e realizada na pr´o-
xima se¸c˜ao. Para os dois seguintes, todas as quinze matrizes documento-termo, trˆes
para cada base de documentos, s˜ao utilizadas nos testes de todos os algoritmos e
85
estes dois itens s˜ao descritos conjuntamente em cada uma das se¸c˜oes seguintes.
4.4.1 Escolha de medida de distˆancia
Nos testes para se determinar a melhor medida de distˆancia dentre a eucli-
deana entre os vetores correspondentes a dois documentos e o cosseno do ˆangulo φ
formado entre estes mesmo vetores, foram utilizadas as cinco bases de teste.
O algoritmo k-means ´e executado dez vezes nessa base, atrav´es do programa
Agrupamento01.m, tendo como entrada uma das trˆes matrizes documento-termo
(a matriz com todos os termos gerada pelo programa CriaMatriz.pl e as duas
matrizes geradas pelos programas SelecionaTermo01.m e SelecionaTermo02.m).
Os valores m´edios das medidas AA, RS, FM, SC e do tempo de processamento
s˜ao apresentados na tabela 4.3.
Cosseno Euclideana
Base Termos AA RS FM SC t AA RS FM SC t
R01 5666 68,14 79,52 52,86 0,08167 43,58 61,65 80,11 57,04 0,08149 1445,21
R01 38
A
79,64 84,41 66,85 0,56434 0,31 57,12 79,13 58,68 0,32966 1,32
R01 58
B
64,53 78,86 51,16 0,28977 0,49 36,09 70,57 40,55 0,29671 2,53
R02 7735 70,32 90,30 77,85 0,06089 133,26 34,32 70,73 51,01 0,06649 2367,65
R02 83
A
70,20 90,06 75,32 0,29976 0,65 29,33 65,22 47,99 0,15842 5,11
R02 169
B
78,28 92,93 82,65 0,15819 1,15 26,69 60,31 46,66 0,26226 16,25
R03 6316 79,43 94,04 81,55 0,07745 42,18 42,18 81,37 55,59 0,06725 1694,97
R03 55
A
79,81 94,31 82,54 0,49882 0,27 48,70 83,88 61,60 0,32102 4,11
R03 185
B
84,09 95,39 85,77 0,20796 0,74 32,83 74,62 48,57 0,20347 5,03
R04 3572 70,56 94,47 73,44 0,09562 16,23 42,35 87,62 54,07 0,08991 382,21
R04 33
A
59,88 92,46 65,08 0,58764 0,29 27,01 80,25 40,90 0,43281 0,79
R04 28
B
67,22 93,96 71,91 0,53424 0,45 33,11 83,72 46,67 0,31723 0,87
S01 7272 96,70 98,53 97,79 0,02974 45,41 93,44 97,06 95,59 0,02969 257,59
S01 116
A
70,52 85,87 79,21 0,12675 0,55 27,37 47,26 53,84 0,25970 1,19
S01 99
B
81,57 91,50 87,29 0,10299 0,34 34,74 60,81 54,85 0,25972 5,51
Tabela 4.3: Compara¸c˜ao das medidas de similaridade cosseno e euclideana (base
R04). (A) termos selecionados com o algoritmo iterativo. (B) termos selecionados
com o algoritmo guloso. Os valores das medidas de qualidade AA, RS e FM s˜ao
percentuais. Os tempo s˜ao medidos em segundos.
Esta tabela mostra que o agrupamento de documentos apresenta melhores
resultados quando a medida de similaridade cosseno ´e utilizada. Como estes re-
86
sultados, em sua maioria, superam largamente os resultados obtidos com o uso da
distˆancia euclideana, fixou-se assim o uso da medida cosseno φ nos demais testes
realizados.
4.4.2 Algoritmo k-means
Para se testar o desempenho do algoritmo k-means, em cada uma das quinze
matrizes documento-termo, este algoritmo foi executado 30 vezes atrav´es do pro-
grama Agrupamento01.m, onde se assumiu o n´umero correto de categorias e a
m´etrica cosseno como medida de similaridade. Os valores m´edios das medidas de
qualidade e o tempo de processamento s˜ao apresentados na tabela 4.4.
Para as bases R01, R02, R03 os melhores resultados s˜ao obtidos ao se utilizar
a matriz documento-termo gerada por um algoritmo de sele¸c˜ao (o algoritmo guloso
para a base R02 e o algoritmo iterativo para as bases R01 e R03) e para as bases
R04 e S01 os melhores resultados s˜ao obtidos ao se utilizar a matriz documento-
termo original.
A seq
¨
uˆencia de tabelas 4.5 a 4.19 apresenta as matrizes de confus˜ao que
cont´em a distribui¸c˜ao dos documentos de cada categoria por cada um dos grupos
encontrados pelo algoritmo k-means. A an´alise destas tabelas permite validar ou
n˜ao os resultados das medidas de qualidade e compar´a-los com a an´alise pr´evia de
cada base, realizada a partir das matrizes de afinidade.
4.4.2.1 Agrupamento: base R01
As tabelas 4.5, 4.6 e 4.7 mostram que as categorias coffee e sugar s˜ao sepa-
radas em grupos, independente da matriz documento-termo utilizada. Por outro
lado a categoria crude se fragmenta em diferentes grupos e as categorias housing,
87
Base Termos Esparsidade AA RS FM SC t
R01 5666 98,96 69,19 79,79 53,61 0,08415 87,12
R01 38
A
93,89 80,05 84,72 67,67 0,57132 0,59
R01 58
B
82,24 64,20 78,68 50,55 0,28400 1,02
R02 7735 99,31 67,73 89,53 76,08 0,06222 261,19
R02 83
A
93,91 70,77 90,26 75,77 0,30070 1,27
R02 169
B
89,37 76,73 92,41 81,64 0,15801 2,21
R03 6316 99,23 79,58 94,04 81,50 0,07811 120,99
R03 55
A
93,83 90,96 94,51 82,97 0,49655 0,56
R03 185
B
90,46 80,86 94,52 83,18 0,20646 1,55
R04 3572 98,51 69,68 94,33 72,93 0,09562 16,78
R04 33
A
92,01 60,25 92,52 65,35 0,58519 0,25
R04 28
B
80,21 66,73 93,89 71,64 0,53698 0,22
S01 7272 99,27 96,70 98,53 97,79 0,02974 94,831
S01 116
A
96,63 68,23 84,51 77,50 0,12545 1,09
S01 99
B
88,80 82,04 91,72 87,60 0,10296 0,74
Tabela 4.4: Resultados do agrupamento com o algoritmo k-means. (A) termos
selecionados com o algoritmo iterativo. (B) termos selecionados com o algoritmo
guloso.
tea, yen e potato se misturam em diferentes grupos com outras categorias. So-
mente com a matriz documento-termo gerada pelo algoritmo de sele¸c˜ao iterativo
(tabela 4.6), as categorias cotton, jobs, alum e orange s˜ao separadas em grupos,
com as outras duas matrizes, o resultado mostra que os documentos destas quatro
categorias s˜ao agrupados em grupos que correspondem a outras categorias.
Analisando os resultados por meio das matrizes de afinidades constata-se
que: (1) a categoria crude nas trˆes matrizes de afinidades apresenta uma quan-
tidade grande de pares de documentos com uma similaridade baixa, mesmo na
matriz obtida a partir da sele¸c˜ao iterativa de termos. Este problema ´e confirmado
no agrupamento, com esta categoria fragmentando-se em v´arios grupos; (2) o al-
goritmo k-means n˜ao consegue separar em grupos as quatro categorias com uma
menor quantidade de documentos (housing, tea, yen e potato), confirmando o que
´e mostrado nas figuras 4.1 e 4.6 e mostrando um comportamento diferente do que ´e
mostrado na figura 4.7, pois nesta estas quatro categorias encontram-se separadas.
88
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 26 0 0 1 0 0 0 0 6 0 4
2 0 98 0 0 0 0 0 0 0 0 0
3 0 0 111 0 0 0 0 0 0 0 0
4 0 1 0 139 0 0 1 0 0 0 0
5 0 17 4 1 45 0 0 0 0 0 0
6 0 81 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 17 45 0 0 0 0
8 0 0 0 0 0 0 6 22 0 0 1
9 0 80 0 0 0 1 1 0 0 0 0
10 0 40 0 0 0 0 0 0 0 6 0
11 0 86 1 2 4 0 1 0 0 0 0
Tabela 4.5: Grupos X Categorias (R01). 5666 termos. Algoritmo k-means.
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 26 0 0 1 0 0 0 0 2 0 1
2 0 225 0 0 0 0 0 0 0 0 0
3
0 0 116 0 0 0 0 0 0 0 0
4 0 0 0 140 0 0 0 0 0 0 0
5 0 0 0 0 42 0 0 0 0 0 0
6 0 19 0 0 0 16 2 0 3 0 1
7 0 0 0 0 0 0 50 0 0 0 0
8 0 2 0 0 0 0 0 22 0 0 0
9 0
28 0 1 0 2 1 0 0 0 3
10 0 14 0 1 7 0 0 0 1 6 0
11 0 115 0 0 0 0 1 0 0 0 0
Tabela 4.6: Grupos X Categorias (R01). 38 termos (sele¸c˜ao iterativa). Algoritmo
k-means.
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 25 0 0 4 0 0 0 6 0 0 1
2 0 137 0 0 0 0 0 1 0 0 0
3 0 0 112 1 1 0 0 1 1 0 0
4 0 1 0 133 4 0 1 0 0 0 0
5 1 41 1 2 30 0 3 3 4 4 2
6 0 25 0 0 0 0 0 0 0 0 0
7 0 9 0 1 5 17 43 2 0 0 0
8 0 70 0 0 0 0 0 0 0 0 0
9 0 27 0 0 0 0 0 0 0 0 0
10 0 83 0 0 6 0 0 2 0 0 0
11 0 10 3 2 3 1 7 7 1 2 2
Tabela 4.7: Grupos X Categorias (R01). 58 termos. Algoritmo k-means.
4.4.2.2 Agrupamento: base R02
As tab elas 4.8, 4.9 e 4.10 apresentam os resultados do agrupamento da base
R02. Nestes resultados ´e confirmada a an´alise qualitativa das matrizes de afini-
89
dades (figuras 4.2, 4.8 e 4.9): (1) ao se agrupar usando-se todos os termos ou os
termos selecionados com o algoritmo guloso, as categorias trade e money-fx se con-
fundem e a maioria de seus documentos s˜ao alocados a um ´unico grupo; (2) estas
duas categorias s´o s˜ao corretamente agrupadas ao se utilizar os termos selecionados
com o algoritmo iterativo; (3) com qualquer uma das matrizes documento-termo,
nos resultados do agrupamento, as categorias earn, acq e crude, apesar de serem
majorit´arias em algum grupo, tˆem documentos que se confundem com outras ca-
tegorias.
Categorias
Grupos earn acq crude trade money-fx
1 214 4 0 0 0
2 78 283 6 0 1
3 0 2 284 0 0
4 5 8 8 299 231
5 2 2 2 0 68
Tabela 4.8: Grupos X Categorias (R02). 7735 termos. Algoritmo k-means.
Ressalte-se que na tabela 4.4 os melhores resultados para as medidas AA,
RS e FM s˜ao do agrupamento da base com os termos selecionados com o algo-
ritmo guloso, resultado este que diverge da an´alise acima, onde constata-se que
os melhores resultados s˜ao obtidos com a base com os termos selecionados com o
algoritmo iterativo, principalmente porque com estes termos se consegue separar
as categorias trade e money-fx.
Categorias
Grupos earn acq crude trade money-fx
1 232 1 19 0 0
2 47 267 15 6 8
3 1 5 259 0 0
4 12 6 2 282 32
5 7 20 5 11 260
Tabela 4.9: Grupos X Categorias (R02). 83 termos (sele¸c˜ao iterativa). Algoritmo
k-means.
90
Categorias
Grupos earn acq crude trade money-fx
1 261 5 0 0 0
2 32 276 15 1 2
3 1 1 277 0 0
4 3 12 6 297 228
5 2 5 2 1 70
Tabela 4.10: Grupos X Categorias (R02). 169 termos. Algoritmo k-means.
4.4.2.3 Agrupamento: base R03
Nas tabelas 4.11, 4.12 e 4.13 s˜ao mostrados os resultados do agrupamento
da base R03. Nos trˆes agrupamentos realizados as categorias coffee e sugar s˜ao
corretamente separadas em seus grupos. No agrupamento da base com todos os
termos, aproximadamente 25% dos documentos da categoria earn se juntou ao
grupo correspondente `a categoria acq e aproximadamente 20% dos documentos da
categoria crude constitu´ıram um grupo em separado. As categorias gold e iron-
steel se juntam em um ´unico grupo.
No agrupamento da base com os termos selecionados com o algoritmo guloso
continua ocorrendo a confus˜ao entre os documentos das categorias earn, acq e
crude. As categorias gold e iron-steel s˜ao separadas, no entanto esta se juntou a
documentos da categoria earn. Este ´ultimo problema ´e resolvido no agrupamento
da base com os termos selecionados com o algoritmo iterativo.
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 148 0 0 0 0 0 0
2 49 191 5 1 1 0 0
3 0 0 149 0 0 1 0
4 0 0 0 141 0 0 2
5 0 0 0 1 115 0 0
6 2 7 2 0 0 98 45
7 0 1 42 0 0 0 0
Tabela 4.11: Grupos X Categorias (R03). 6316 termos. Algoritmo k-means.
91
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 175 4 24 1 0 0 2
2 21 184 4 1 0 1 5
3 0 5 170 0 0 0 0
4 0 0 0 140 0 0 1
5 0 0 0 0 116 0 0
6 1 2 0 1 0 98 1
7 2 4 0 0 0 0 38
Tabela 4.12: Grupos X Categorias (R03). 55 termos (sele¸c˜ao iterativa). Algoritmo
k-means.
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 144 0 0 0 0 0 0
2 18 193 8 0 1 0 0
3 0 0 189 0 0 1 3
4 0 0 0 141 0 0 4
5 0 0 0 1 112 0 0
6 0 2 1 0 0 98 2
7 37 4 0 1 3 0 38
Tabela 4.13: Grupos X Categorias (R03). 185 termos. Algoritmo k-means.
4.4.2.4 Agrupamento: base R04
Dentre os trˆes agrupamentos da base R04, apresentados nas tabelas 4.14,
4.15 e 4.16 o melhor resultado ´e obtido com o agrupamento da base com todos
os termos, mesmo assim os dois principais problemas identificados nos outros dois
agrupamentos se repetem neste, pois: (1) as categorias ipi e wpi se confundem em
um ´unico grupo e (2) ´e constitu´ıdo um grupo com documentos de v´arias categorias.
Algumas categorias como alum e iron-steel apesar de se concentrarem em seus
grupos respectivos, tamb´em tˆem uma quantidade consider´avel de documentos que
se distribuem em outros grupos.
Estes resultados confirmam as medidas externas de qualidade (tabela 4.4),
pois nesta, o agrupamento da base com todos os termos ´e ligeiramente superior
que o agrupamento da base com os termos selecionados pelo algoritmo guloso.
92
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 40 0 1 0 0 0 0 1 26 0
2 0 31 2 0 2 0 0 0 0 0
3 0 0 31 0 0 0 0 0 0 0
4 0 0 0 29 0 0 0 1 0 0
5 0 0 0 0 38 0 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 38 0 0 0
8 0 0 5 0 0 0 0 28 0 0
9 8 1 8 1 9 2 3 4 0 1
10 0 0 0 0 0 0 0 3 0 25
Tabela 4.14: Grupos X Categorias (R04). 3572 termos. Algoritmo k-means.
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 44 0 0 0 0 0 1 0 26 8
2 1 27 2 0 1 0 0 0 0 2
3 0 0 32 0 0 0 0 0 0 0
4
0 0 0 28 0 0 0 1 0 0
5 0 0 0 0 23 0 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 1 0 0 0 39 0 0 1
8 1 0 5 1 1 2 0 26 0 1
9 0 0 0 0 19 0 0 0 0 0
10 2
5 7 1 5 0 1 10 0 14
Tabela 4.15: Grupos X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algoritmo
k-means.
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 45 0 1 0 7 0 1 1 26 0
2 0 28 2 0 1 0 0 1 0 0
3 0 0 33 0 1 0 0 0 0 0
4 0 0 0 28 0 0 0 0 0 0
5 0 0 0 0 29 0 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 39 0 0 0
8 1 0 2 1 0 0 0 28 0 0
9 2 4 9 1 11 2 1 5 0 1
10 0 0 0 0 0 0 0 2 0 25
Tabela 4.16: Grupos X Categorias (R04). 28 termos. Algoritmo k-means.
4.4.2.5 Agrupamento: base S01
Nesta base obteve-se um excelente resultado no agrupamento com todos os
termos e por outro lado o processo de sele¸c˜ao de caracter´ısticas impactou nega-
tivamente nos resultados dos dois outros agrupamentos. A tabela 4.17 mostra as
93
trˆes categorias praticamente totalmente separadas, com apenas 10 documentos,
de um total de 900, alocados a grupos que n˜ao correspondem `as suas categorias.
Esta quantidade aumenta consideravelmente nos agrupamentos apresentados nas
tabelas 4.18 e 4.19.
Categorias
Grupos cisi cran med
1 299 3 5
2 1 297 1
3 0 0 294
Tabela 4.17: Grupos X Categorias (S01). 7272 termos. Algoritmo k-means.
Categorias
Grupos cisi cran med
1 278 7 12
2 2 284 31
3 20 9 257
Tabela 4.18: Grupos X Categorias (S01). 116 termos (sele¸c˜ao iterativa). Algoritmo
k-means.
Categorias
Grupos cisi cran med
1 289 6 10
2 5 291 32
3 6 3 258
Tabela 4.19: Grupos X Categorias (S01). 99 termos. Algoritmo k-means.
4.4.3 Algoritmo espectral
4.4.3.1 Determina¸c˜ao do valor do parˆametro σ
Para a determina¸c˜ao do parˆametro σ da fun¸c˜ao gaussiana utilizada no algo-
ritmo de agrupamento espectral, o programa Agrupamento02a.m ´e executado de
forma que valor de σ varie na faixa de 0.10
5
a 1.10, com incremento de 0.02 e desta
forma, 50 valores distintos de σ s˜ao utilizados no algoritmo de agrupamento. Para
5
Este valor m´ınimo foi determinado experimentalmente. Com valores menores, a fun¸c˜ao que
calcula os autovalores e autovetores n˜ao converge com algumas das bases de do cumentos.
94
cada uma destas execu¸c˜oes, as medidas de qualidade s˜ao calculadas e o valor de σ
que maximiza estas medidas ´e utilizado nos testes do algoritmo de agrupamento
espectral, descritos na pr´oxima se¸c˜ao.
Este procedimento foi realizado para cada uma das trˆes matrizes documento-
texto de cada uma das bases de documentos. No anexo B s˜ao apresentados as medi-
das de qualidade de cada um destes procedimentos, que s˜ao usadas na escolha do σ.
4.4.3.2 Agrupamento espectral com o valor de σ escolhido
Nos testes do algoritmo de agrupamento espectral s˜ao adotados os mesmos
procedimentos dos testes do algoritmo k-means. Assim para cada uma das ma-
trizes documento-termo, este algoritmo ´e executado 30 vezes atrav´es do programa
Agrupamento02b.m, com o conhecimento correto do n´umero de categorias. Os
valores m´edios das medidas de qualidade e do tempo de processamento s˜ao apre-
sentados na tabela 4.20, onde esta tabela mostra tamb´em o valor do parˆametro σ
utilizado. O tempo de processamento ´e a soma dos tempos dos passos do algo-
ritmo 4 descrito na se¸c˜ao 3.2.3, que inclui o c´alculo da matriz de afinidades, dos
autovetores, a constru¸c˜ao da matriz Y e o procedimento do k-means.
De uma maneira geral os resultados obtidos refletem um comportamento
semelhante ao algoritmo k-means. Trˆes bases (R01, R02 e R03) tˆem os seus me-
lhores resultados quando s˜ao utilizadas as matrizes documento-termo geradas a
partir da sele¸c˜ao de termos e as outras duas bases tˆem os seus melhores resulta-
dos quando s˜ao utilizadas as matrizes documento-termo sem a sele¸c˜ao. No tempo
de processamento, este algoritmo ´e largamente sup erior ao algoritmo k-means no
agrupamentos das bases com todos os termos e para as bases com termos seleci-
onados, apesar de seus tempos serem maiores, estes s˜ao competitivos. As tabelas
4.21 a 4.35 mostram as matrizes de confus˜ao com a distribui¸c˜ao dos documentos
95
de cada categoria por cada um dos grupos.
Base Termos Esparsidade σ AA RS FM SC t
R01 5666 98,96 0,4 53,91 77,04 49,62 0,07488 2,16
R01 38
A
93,89 0,12 79,43 85,67 70,09 0,55384 2,24
R01 58
B
82,24 0,14 61,36 79,31 54,08 0,30693 2,10
R02 7735 99,31 0,7 48,70 81,65 60,77 0,06754 8,50
R02 83
A
93,91 0,76 67,99 89,30 73,47 0,29937 8,18
R02 169
B
89,37 1,00 65,70 88,72 72,99 0,15460 8,16
R03 6316 99,23 0,94 59,26 88,36 66,87 0,07732 2,95
R03 55
A
93,83 0,46 75,59 93,11 79,00 0,48787 2,91
R03 185
B
90,46 0,32 76,40 93,65 81,06 0,20876 2,99
R04 3572 98,51 0,64 74,68 95,41 78,17 0,08440 0,48
R04 33
A
92,01 0,26 58,60 92,20 64,25 0,59929 0,42
R04 28
B
80,21 0,72 73,72 95,00 75,69 0,49976 0,44
S01 7272 99,27 1,00 81,78 91,71 87,66 0,02802 2,05
S01 116
A
96,63 0,1 70,69 86,15 79,48 0,12639 3,53
S01 99
B
88,80 0,1 75,76 88,69 83,14 0,10062 2,67
Tabela 4.20: Resultados do agrupamento com o algoritmo espectral. (A) termos
selecionados com o algoritmo iterativo. (B) termos selecionados com o algoritmo
guloso.
4.4.3.3 Agrupamento: base R01
No agrupamento desta base destaca-se que com os termos selecionados com
o algoritmo iterativo (tabela 4.22) diminui a fragmenta¸c˜ao da categoria crude e
a categoria yen tornou-se majorit´aria em um grupo, comparando com o agrupa-
mento realizado com o algoritmo k-means. As categorias cotton, coffee, sugar, jobs
e orange s˜ao separadas em grupos distintos. Aumentou a fragmenta¸c˜ao da catego-
ria alum e as categorias housing, tea e potato continuam sendo confundidas com
outras categorias.
Com os termos selecionados com o algoritmo guloso (tabela 4.23), a categoria
crude continua fragmentada e a alum se fragmenta. A categoria jobs se separa da
categoria housing. Com todos os termos (tabela 4.21) a categoria sugar se frag-
menta e diminui a fragmenta¸c˜ao da categoria alum.
96
Um fenˆomeno interessante ´e que a an´alise destas tabelas mostra que os re-
sultados obtidos com os termos selecionados s˜ao superiores aos obtidos com o
algoritmo k-means. No entanto, as medidas externas de qualidade n˜ao refletem
completamente este resultado, pois as medidas AA e FM s˜ao menores e apenas a
RS ´e maior.
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 24 0 3 1 0 0 0 0 0 0 0
2 0 172 1 0 6 0 4 0 0 6 0
3 0 0 107 0 0 0 0 0 0 0 0
4 1 1 2 101 6 0 0 0 0 0 0
5 1 19 3 7 37 1 0 22 6 0 5
6 0 0 0 34 0 0 1 0 0 0 0
7 0 3 0 0 0 17 49 0 0 0 0
8 0 60 0 0 0 0 0 0 0 0 0
9 0 31 0 0 0 0 0 0 0 0 0
10 0 91 0 0 0 0 0 0 0 0 0
11 0 26 0 0 0 0 0 0 0 0 0
Tabela 4.21: Grupos X Categorias (R01). 5666 termos. Algoritmo espectral.
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 26 0 0 0 0 0 0 0 1 0 0
2 0 293 0 0 3 0 1 0 1 0 0
3 0 0 116 0 1 0 0 0 1 0 0
4 0 0 0 138 0 0 0 0 0 0 0
5 0 0 0 0 23 0 0 0 0 0 0
6 0 24 0 4 1 17 2 0 3 0 2
7 0 0 0 0 0 0 50 0 0 0 0
8 0 2 0 1 0 0 0 22 0 0 3
9 0 0 0 0 19 0 0 0 0 0 0
10 0 1 0 0 2 0 0 0 0 6 0
11 0 83 0 0 0 1 1 0 0 0 0
Tabela 4.22: Grupos X Categorias (R01). 38 termos (sele¸c˜ao iterativa). Algoritmo
espectral.
4.4.3.4 Agrupamento: base R02
Os resultados (tabelas 4.24, 4.25 e 4.26) para esta base s˜ao inferiores aos
obtidos com o algoritmo k-means. O n´umero de documentos dos grupos associados
`as categorias earn, acq e crude diminuiu e a confus˜ao entre as categorias trade e
97
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 24 0 0 0 0 0 0 0 0 0 0
2 0 161 1 0 7 0 2 3 3 1 1
3 0 0 109 0 0 0 0 2 0 0 0
4 0 2 0 131 14 0 1 0 0 0 0
5 1 16 0 3 19 1 0 5 2 3 1
6 0 12 1 0 2 13 0 1 1 0 0
7 0 1 0 0 3 3 45 0 0 0 0
8 1 4 5 9 1 1 6 11 0 2 3
9 0 96 0 0 0 0 0 0 0 0 0
10 0 28 0 0 0 0 0 0 0 0 0
11 0 83 0 0 3 0 0 0 0 0 0
Tabela 4.23: Grupos X Categorias (R01). 58 termos. Algoritmo espectral.
money-fx se mant´em, apesar da quantidade de documentos desta ´ultima categoria,
neste grupo ter diminu´ıdo. Esta an´alise est´a em concordˆancia com as medidas de
qualidade.
Categorias
Grupos earn acq crude trade money-fx
1 199 0 0 0 0
2 87 295 52 8 74
3 2 0 238 1 0
4 9 3 8 290 159
5 2 1 2 0 67
Tabela 4.24: Grupos X Categorias (R02). 7735 termos. Algoritmo espectral.
Categorias
Grupos earn acq crude trade money-fx
1 225 1 21 0 0
2 61 258 15 10 19
3 0 2 257 0 0
4 1 2 2 270 16
5 12 36 5 19 265
Tabela 4.25: Grupos X Categorias (R02). 83 termos (sele¸c˜ao iterativa). Algoritmo
espectral.
4.4.3.5 Agrupamento: base R03
Com os termos selecionados com o algoritmo iterativo, os resultados (tabela
4.28) s˜ao praticamente idˆenticos aos obtidos com o algoritmo k-means, apesar
da medida AA sem bem menor. Com os termos selecionados com o algoritmo
98
Categorias
Grupos earn acq crude trade money-fx
1 257 6 0 0 0
2 33 265 15 1 2
3 2 2 273 2 1
4 2 10 8 292 150
5 5 16 4 4 147
Tabela 4.26: Grupos X Categorias (R02). 169 termos. Algoritmo espectral.
guloso os documentos da categoria iron-steel continuam sendo confundidos com
documentos da categoria acq (tabela 4.29) e com todos os termos estes documentos
s˜ao distribu´ıdos em diferentes grupos(tabela 4.27).
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 137 0 0 0 0 0 0
2 55 193 28 11 6 0 17
3 0 0 127 0 0 1 0
4 0 0 0 132 0 0 11
5 0 0 0 0 110 0 0
6 7 6 1 0 0 98 16
7 0 0 42 0 0 0 3
Tabela 4.27: Grupos X Categorias (R03). 6316 termos. Algoritmo espectral.
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 167 2 22 1 0 0 1
2 30 189 10 2 0 1 8
3 0 2 166 0 0 0 0
4 0 0 0 140 0 0 0
5 0 0 0 0 116 0 0
6 0 2 0 0 0 98 0
7 2 4 0 0 0 0 38
Tabela 4.28: Grupos X Categorias (R03). 55 termos (sele¸c˜ao iterativa). Algoritmo
espectral.
4.4.3.6 Agrupamento: base R04
No agrupamento desta base, todas medidas de qualidade ou s˜ao maiores
ou bem pr´oximas `as medidas obtidas com o algoritmo k-means. Estes resultados
(tabelas 4.30, 4.31 e 4.32) refletem, principalmente, que as categorias ipi e wpi s˜ao
99
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 138 0 0 0 0 0 0
2 21 196 10 2 5 0 30
3 0 0 187 0 0 1 6
4 0 0 0 141 0 0 7
5 0 0 0 0 111 0 0
6 0 2 1 0 0 98 4
7 40 1 0 0 0 0 0
Tabela 4.29: Grupos X Categorias (R03). 185 termos. Algoritmo espectral.
separadas em dois grupos no agrupamento da base com todos os termos e da base
com os termos selecionados com o algoritmo guloso.
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 47 0 1 0 0 0 0 0 1 0
2 0 31 0 0 0 0 0 0 0 0
3 0 0 34 0 1 2 1 0 0 0
4 0 0 0 30 0 0 2 1 0 0
5 0 1 6 0 48 0 9 3 1 0
6 0 0 1 0 0 43 0 2 0 0
7 0 0 0 0 0 0 29 0 0 0
8 0 0 5 0 0 0 0 28 0 0
9 1 0 0 0 0 0 0 0 24 0
10 0 0 0 0 0 0 0 3 0 26
Tabela 4.30: Grupos X Categorias (R04). 3572 termos. Algoritmo espectral.
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 42 0 0 0 0 0 1 0 26 7
2 1 27 2 0 1 0 0 0 0 2
3 0 0 31 0 0 0 0 0 0 0
4 0 0 0 28 0 0 0 0 0 0
5 0 0 0 0 23 0 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 39 0 0 1
8 2 0 4 1 0 1 0 26 0 0
9 0 0 0 0 19 0 0 0 0 0
10 3 5 10 1 6 1 1 11 0 16
Tabela 4.31: Grupos X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algoritmo
espectral.
100
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 45 0 2 0 4 0 0 2 0 0
2 0 32 2 1 2 0 1 3 0 0
3 0 0 34 0 3 0 0 0 0 0
4 0 0 0 28 0 0 0 0 0 0
5 0 0 1 0 34 0 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 36 0 0 0
8 1 0 2 1 0 0 0 30 0 0
9 2 0 6 0 6 2 4 0 26 0
10 0 0 0 0 0 0 0 2 0 26
Tabela 4.32: Grupos X Categorias (R04). 28 termos. Algoritmo espectral.
4.4.3.7 Agrupamento: base S01
Nos trˆes agrupamentos desta base, os resultados obtidos (tabelas 4.33, 4.34
e 4.35) s˜ao inferiores aos obtidos com o algoritmo k-means. A categoria med ´e
impactada negativamente nas bases com os termos selecionados e os resultados
para a categoria cran s˜ao inferiores aos obtidos no agrupamento com todos os
termos.
Categorias
Grupos cisi cran med
1 293 2 0
2 0 249 2
3 7 49 298
Tabela 4.33: Grupos X Categorias (S01). 7272 termos. Algoritmo espectral.
Categorias
Grupos cisi cran med
1 281 9 15
2 9 290 60
3 10 1 225
Tabela 4.34: Grupos X Categorias (S01). 116 termos (sele¸c˜ao iterativa). Algoritmo
espectral.
101
Categorias
Grupos cisi cran med
1 286 3 12
2 10 290 47
3 4 7 241
Tabela 4.35: Grupos X Categorias (S01). 99 termos. Algoritmo espectral.
4.4.4 Algoritmo de particionamento de grafos - Associa¸c˜ao ponde-
rada
Para os testes deste algoritmo ´e utilizada a mesma meto dologia usada para
os outros algoritmos atrav´es da execu¸c˜ao do programa Agrupamento03.m.
Na tabela 4.36 s˜ao apresentados os valores m´edios para as medidas de qua-
lidade e do tempo de processamento. Comparando estes resultados com os resul-
tados obtidos com o algoritmo k-means, contata-se que os valores das medidas de
qualidade s˜ao, em geral, bem inferiores e os tempos de processamento s˜ao menores.
Apenas em seis, dos quinze procedimentos de agrupamento, os valores m´edios
das medidas de qualidade s˜ao pr´oximos ou melhores que os resultados mostrados
na tabela 4.4. Em decorrˆencia disto, optou-se para que sejam apresentadas apenas
as tabelas 4.37 a 4.42, correspondentes aos melhores resultados, que mostram as
matrizes de confus˜ao com a distribui¸c˜ao dos documentos das categorias nos grupos.
As tabelas 4.37 e 4.38 apresentam os resultados do agrupamento da base R02
com os termos selecionados, com o algoritmo iterativo e com o algoritmo guloso,
respectivamente. Apesar da quantidade de documentos das categorias earn, acq e
crude nos seus respectivos grupos terem diminu´ıdo (o que significa que aumentou
a confus˜ao entre os documentos destas categorias), ocorreu a separa¸c˜ao entre as
categorias trade e money-fx na base com os termos selecionados com o algoritmo
guloso, diferentemente do que ocorre com o agrupamento desta base com o algo-
ritmo k-means. Comparando com os resultado obtidos com o algoritmo espectral,
102
Base Termos Esparsidade AA RS FM SC t
R01 5666 98,96 53,95 76,09 42,94 0,08183 0,98
R01 38
A
93,89 71,37 80,93 57,23 0,44682 0,87
R01 58
B
82,24 59,81 77,05 44,94 0,25715 0,93
R02 7735 99,31 49,06 81,67 62,01 0,06476 1,41
R02 83
A
93,91 65,66 88,43 71,28 0,29764 1,21
R02 169
B
89,37 77,29 92,51 81,30 0,15600 1,32
R03 6316 99,23 63,88 89,92 70,70 0,08061 0,67
R03 55
A
93,83 69,05 90,90 71,43 0,44653 0,66
R03 185
B
90,46 77,21 93,26 78,85 0,20429 0,82
R04 3572 98,51 73,62 95,06 76,11 0,08464 0,31
R04 33
A
92,01 58,49 92,10 62,75 0,57818 0,28
R04 28
B
80,21 76,82 95,53 78,10 0,49969 0,32
S01 7272 99,27 86,21 93,75 90,65 0,02866 0,40
S01 116
A
96,63 57,82 79,18 69,59 0,12836 0,41
S01 99
B
88,80 76,73 89,15 83,79 0,10193 0,41
Tabela 4.36: Resultado do agrupamento com o algoritmo de particionamento de
grafos - associa¸c˜ao ponderada. (A) termos selecionados com o algoritmo iterativo.
(B) termos selecionados com o algoritmo guloso.
este resultado tamb´em ´e superior pois o grupo correspondente `a categoria money-fx
tem 120 documentos a mais.
Categorias
Grupos earn acq crude trade money-fx
1 228 2 21 0 0
2 58 229 12 8 17
3 0 3 257 0 0
4 2 2 2 273 21
5 11 63 8 18 262
Tabela 4.37: Grupos X Categorias (R02). 83 (sele¸c˜ao iterativa) termos. Algoritmo
de particionamento de grafos - associa¸c˜ao ponderada
Categorias
Grupos earn acq crude trade money-fx
1 257 6 0 0 0
2 33 261 13 1 2
3 2 2 275 1 1
4 1 9 6 286 30
5 6 21 6 11 267
Tabela 4.38: Grupos X Categorias (R02). 169 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada
Na tabela 4.39 ´e mostrado o agrupamento da base R03 com os termos sele-
cionados com o algoritmo guloso. Este resultados s˜ao apresentados p ois o valor da
103
medida de qualidade RS (93,26%) ´e bem pr´oximo ao valor obtido com o algoritmo
k-means (94,54%), apesar das outras medidas terem valores mais distantes. A an´a-
lise desta tabela mostra que os grupos associados `as categorias crude e iron-steel
s˜ao inferiores, comparados aos obtidos com o algoritmo k-means (tabela 4.13).
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 144 0 0 0 0 0 0
2 15 193 8 0 1 0 16
3 0 0 152 0 0 1 6
4 0 0 0 140 0 0 13
5 0 0 0 1 112 0 0
6 0 3 1 1 0 98 7
7 40 3 37 1 3 0 5
Tabela 4.39: Grupos X Categorias (R03). 185 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada
As tabelas 4.40, 4.41 e 4.42 apresentam os resultados do agrupamento da
base R04. Os resultados obtidos s˜ao bem pr´oximos aos obtidos com o algoritmo
espectral e superiores aos obtidos com o algoritmo k-means. Nos agrupamentos da
base com todos os termos e da base com os termos selecionados com o algoritmo
guloso, da mesma forma que ocorre com o agrupamento espectral, as categorias ipi
e wpi s˜ao separadas em grupos.
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 45 0 1 0 0 0 0 0 1 0
2 0 31 0 1 0 0 0 0 0 0
3 0 0 34 0 5 2 1 0 0 0
4 0 0 0 29 0 0 2 1 0 0
5 0 1 6 0 44 0 7 2 0 0
6 0 0 1 0 0 43 0 3 0 0
7 0 0 0 0 0 0 31 0 0 0
8 0 0 5 0 0 0 0 28 0 0
9 3 0 0 0 0 0 0 0 25 0
10 0 0 0 0 0 0 0 3 0 26
Tabela 4.40: Grupos X Categorias (R04). 3572 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada
104
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 38 0 0 0 0 0 1 0 26 4
2 3 27 2 0 2 0 0 0 0 2
3 0 0 30 0 0 0 0 0 0 0
4 0 0 0 28 0 0 0 0 0 1
5 2 0 2 0 24 2 0 5 0 3
6 1 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 39 0 0 0
8 2 0 5 1 0 0 0 26 0 0
9 2 0 2 0 19 0 0 0 0 1
10 0 5 6 1 4 0 1 6 0 15
Tabela 4.41: Grupos X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algoritmo
de particionamento de grafos - associa¸c˜ao ponderada
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 45 0 2 0 2 0 0 2 0 0
2 0 31 2 1 1 0 0 2 0 0
3 0 0 34 0 4 0 1 0 0 0
4 0 0 0 29 0 0 0 0 0 0
5 0 0 1 0 37 1 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 38 0 0 0
8 1 0 2 0 0 0 0 30 0 0
9 2 0 6 0 5 1 2 0 26 0
10 0 1 0 0 0 0 0 3 0 26
Tabela 4.42: Grupos X Categorias (R04). 28 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao ponderada
4.4.5 Algoritmo de particionamento de grafos - Corte ponderado
Na tabela 4.43 s˜ao apresentados os valores m´edios para as medidas de qua-
lidade e do tempo de processamento. Comparando estes resultados com os resul-
tados obtidos com o algoritmo k-means, contata-se que os valores das medidas de
qualidade e os tempos de processamento s˜ao, em geral, bem inferiores. Os tempos
de processamento s˜ao melhores apenas quando as matrizes cont´em todos os termos
de cada base. As medidas de qualidade s˜ao inferiores tamb´em `as obtidas com o
algoritmo de particionamento de grafos de associa¸c˜ao ponderada. Somente para a
base R01, algumas medidas de qualidade s˜ao superiores.
Nas tabelas 4.44, 4.45 e 4.46 s˜ao apresentados os resultados dos agrupa-
105
Base Termos Esparsidade AA RS FM SC t
R01 5666 98,96 60,99 81,17 61,36 0,03968 2,12
R01 38
A
93,89 38,25 85,96 51,72 0,3724 4,64
R01 58
B
82,24 59,85 80,55 60,43 0,07446 1,90
R02 7735 99,31 17,91 37,56 41,09 0,01400 3,94
R02 83
A
93,91 23,21 43,05 47,92 0,04873 3,70
R02 169
B
89,37 19,63 51,29 38,41 0,02579 3,56
R03 6316 99,23 27,39 71,00 42,28 0,01707 2,50
R03 55
A
93,83 17,91 47,48 38,35 0,04318 2,51
R03 185
B
90,46 36,23 78,52 47,97 0,06112 1,72
R04 3572 98,51 37,65 86,37 48,49 0,05872 1,35
R04 33
A
92,01 38,25 85,96 51,72 0,37238 2,01
R04 28
B
80,21 58,70 92,24 64,80 0,43066 3,26
S01 7272 99,27 47,89 71,35 65,95 0,01484 1,50
S01 116
A
96,63 22,28 33,81 57,21 0,05685 2,58
S01 99
B
88,80 51,60 75,00 67,70 0,09113 1,03
Tabela 4.43: Resultado do agrupamento com o algoritmo de particionamento de
grafos - corte ponderado. (A) termos selecionados com o algoritmo iterativo. (B)
termos selecionados com o algoritmo guloso.
mentos da base R01. Com a base com os termos selecionados com o algoritmo
iterativo (tab ela 4.45), o problema de fragmenta¸c˜ao em v´arios grupos que ocorre
com a categoria crude praticamente ´e resolvido, pois a maioria de seus documen-
tos se concentra em um ´unico grupo. No entanto, surgem outros problemas: (1) a
categoria housing se junta ao grupo da categoria crude; (2) as categorias cotton e
orange se juntam em um grupo e (2) a categoria alum se divide em dois grupos.
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 13 2 2 32 0 0 0 2 0 0 0
2 0 178 0 2 1 9 38 0 1 4 0
3 1 1 99 1 1 0 6 0 1 2 0
4 1 4 5 92 1 0 2 0 3 0 0
5 1 1 1 3 25 0 0 0 0 0 0
6 0 20 0 2 0 9 0 0 0 0 0
7 0 45 0 1 0 0 8 0 1 0 0
8 8 0 1 5 0 0 0 20 0 0 5
9 0 152 2 1 2 0 0 0 0 0 0
10 0 0 0 0 19 0 0 0 0 0 0
11 2 0 6 4 0 0 0 0 0 0 0
Tabela 4.44: Grupos X Categorias (R01). 5666 termos. Algoritmo de particiona-
mento de grafos - corte ponderado
No agrupamento da base com os termos selecionados com o algoritmo guloso,
106
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 26 1 0 1 0 0 0 19 1 0 3
2 0 390 1 0 3 13 3 0 1 0 0
3 0 1 113 1 0 4 0 0 2 0 1
4 0 1 2 140 0 0 0 3 1 0 1
5 0 0 0 0 22 0 0 0 0 0 0
6 0 0 0 0 22 0 0 0 0 0 0
7 0 0 0 0 0 0 51 0 0 6 0
8 0 0 0 0 1 1 0 0 0 0 0
9 0 1 0 1 1 0 0 0 0 0 0
10 0 4 0 0 0 0 0 0 1 0 0
11 0 5 0 0 0 0 0 0 0 0 0
Tabela 4.45: Grupos X Categorias (R01). 38 termos (sele¸c˜ao iterativa). Algoritmo
de particionamento de grafos - corte ponderado
apesar da medida RS ser alta (80,55%), a an´alise da tabela 4.46 mostra que este
resultado ´e bem inferior ao obtido com os algoritmos k-means e espectral, pois a
maioria das categorias se fragmentou em diferentes grupos. O mesmo ocorre com
o agrupamento da base com todos os termos (tabela 4.44), pois as medidas RS e
FM s˜ao superiores `as medidas obtidas com o algoritmo k-means e no entanto o
resultado ´e bem inferior.
Categorias
Grupos cotton crude coffee sugar alum housing jobs orange tea yen potato
1 23 0 0 0 0 0 0 0 0 0 0
2 0 288 0 0 8 1 0 1 1 1 0
3 0 0 83 14 5 0 0 0 0 2 1
4 0 0 17 87 4 0 0 0 0 0 0
5 0 41 0 0 10 0 9 1 1 3 0
6 0 21 0 2 1 12 1 1 1 0 0
7 0 43 3 7 17 4 23 4 2 0 1
8 0 0 1 0 0 0 17 2 0 0 0
9 0 5 4 14 1 1 4 2 1 0 0
10 3 5 0 1 2 0 0 3 0 0 0
11 0 0 8 18 1 0 0 8 0 0 3
Tabela 4.46: Grupos X Categorias (R01). 58 termos. Algoritmo de particiona-
mento de grafos - corte ponderado
107
4.4.6 Algoritmo de particionamento de grafos - Associa¸c˜ao norma-
lizada
Para a an´alise dos resultados deste algoritmo, selecionou-se tamb´em apenas
os agrupamentos cujas medidas de qualidade s˜ao pr´oximas das medidas obtidas
com o algoritmo k-means. Na tabela 4.47 s˜ao apresentados os resultados m´edios
para os agrupamentos de todas as bases. Novamente os tempos de processamento
s˜ao competitivos, quando comparados com os tempos do algoritmo k-means. Os
resultados apresentados nesta tabela s˜ao, de uma maneira geral, semelhantes aos
resultados obtidos com o algoritmo de particionamento de grafos com associa¸c˜ao
ponderada (tabela 4.36).
Base Termos Esparsidade AA RS FM SC t
R01 5666 98,96 50,34 75,21 40,66 0,07815 2,14
R01 38
A
93,89 69,11 79,99 54,36 0,43424 3,86
R01 58
B
82,24 58,68 76,79 44,12 0,25936 2,29
R02 7735 99,31 48,49 81,40 61,81 0,06528 8,43
R02 83
A
93,91 64,87 88,14 70,65 0,29389 8,16
R02 169
B
89,37 77,70 92,65 81,63 0,15647 8,27
R03 6316 99,23 64,09 89,97 70,78 0,08081 2,86
R03 55
A
93,83 68,95 90,85 71,21 0,45210 2,79
R03 185
B
90,46 76,51 93,08 78,31 0,20463 2,88
R04 3572 98,51 71,75 94,70 74,40 0,08425 0,41
R04 33
A
92,01 58,33 92,07 62,61 0,57663 0,38
R04 28
B
80,21 77,49 95,63 78,46 0,50248 0,41
S01 7272 99,27 85,35 93,36 90,07 0,02854 1,90
S01 116
A
96,63 54,87 77,47 67,38 0,12730 1,91
S01 99
B
88,80 78,30 89,91 84,89 0,10227 1,91
Tabela 4.47: Resultado do agrupamento com o algoritmo de particionamento de
grafos - associa¸c˜ao normalizada. (A) termos selecionados com o algoritmo iterativo.
(B) termos selecionados com o algoritmo guloso.
As tabelas 4.48 e 4.49 apresentam os agrupamentos da base R02 com os ter-
mos selecionados com os algoritmos iterativo e guloso. Ambos os resultados s˜ao
semelhantes aos obtidos com o algoritmo de particionamento de grafo com associ-
a¸c˜ao ponderada, com a caracter´ıstica de ambos terem separado em dois grupos as
categorias trade e money-fx.
108
Categorias
Grupos earn acq crude trade money-fx
1 229 2 21 0 0
2 57 223 12 8 16
3 0 3 257 0 0
4 2 2 2 273 20
5 11 69 8 18 264
Tabela 4.48: Grupos X Categorias (R02). 83 termos (sele¸c˜ao iterativa). Algoritmo
de particionamento de grafos - associa¸c˜ao normalizada
Categorias
Grupos earn acq crude trade money-fx
1 256 6 0 0 0
2 34 261 13 1 2
3 2 2 276 1 1
4 1 9 6 285 26
5 6 21 5 12 271
Tabela 4.49: Grupos X Categorias (R02). 169 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada
O resultado apresentado na tabela 4.50, do agrupamento da base R03 com
termos selecionados com o algoritmo guloso, ´e praticamente igual ao obtido com
o algoritmo de particionamento de grafo com associa¸c˜ao ponderada, mostrado na
tabela 4.39 e inferior aos resultados obtidos com os algoritmo k-means e espectral.
Categorias
Grupos earn acq crude sugar coffee gold iron-steel
1 145 0 0 0 0 0 0
2 17 193 9 0 1 0 16
3 0 0 149 0 0 1 5
4 0 0 0 140 0 0 13
5 0 0 0 1 112 0 0
6 0 3 1 1 0 98 6
7 37 3 39 1 3 0 7
Tabela 4.50: Grupos X Categorias (R03). 185 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada
As tabelas 4.51, 4.52 e 4.53 apresentam os resultados do agrupamento da base
R04 e s˜ao bem semelhantes `as tabelas 4.40, 4.41 e 4.42 e novamente as categorias
ipi e wpi, quando o agrupamento ´e realizado sobre as bases com todos os termos ou
com os termos selecionados pelo algoritmo guloso, s˜ao separadas em dois grupos
109
distintos.
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 44 0 1 0 0 0 0 0 1 0
2 0 31 0 1 0 0 0 0 0 0
3 0 0 34 0 9 2 1 0 0 0
4 1 0 0 29 0 0 2 1 0 0
5
0 1 6 0 40 0 8 2 1 0
6 0 0 1 0 0 43 0 3 0 0
7 0 0 0 0 0 0 30 0 0 0
8 0 0 5 0 0 0 0 28 0 0
9 3 0 0 0 0 0 0 0 24 0
10 0 0 0 0 0 0 0 3 0 26
Tabela 4.51: Grupos X Categorias (R04). 3572 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 38 0 0 0 0 0 1 0 26 4
2 3 27 2 0 2 0 0 0 0 2
3 0 0 30 0 0 0 0 0 0 0
4 0 0 0 28 0 0 0 0 0 1
5 2 0 3 0 24 2 0 5 0 6
6 1 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 39 0 0 0
8 2 0 5 1 0 0 0 26 0 0
9 2 0 1 0 19 0 0 0 0 1
10 0 5 6 1 4 0 1 6 0 12
Tabela 4.52: Grupos X Categorias (R04). 33 termos (sele¸c˜ao iterativa). Algoritmo
de particionamento de grafos - associa¸c˜ao normalizada
Categorias
Grupos ipi bop iron-steel tin alum nat-gas rubber veg-oil wpi cotton
1 45 0 2 0 2 0 0 1 0 0
2 0 31 2 1 2 0 0 2 0 0
3 0 0 33 0 4 0 1 0 0 0
4 0 0
0 29 0 0 0 1 0 0
5 0 0 3 0 36 2 0 0 0 0
6 0 0 0 0 0 43 0 0 0 0
7 0 0 0 0 0 0 38 0 0 0
8 1 0 2 0 0 0 0 30 0 0
9 2 0 5 0 5 0 2 0 26 0
10 0 1 0 0 0 0 0 3 0 26
Tabela 4.53: Grupos X Categorias (R04). 28 termos. Algoritmo de particiona-
mento de grafos - associa¸c˜ao normalizada
110
Os agrupamentos da base S01 com os termos selecionados s˜ao mostrados nas
tabelas 4.54 e 4.55. Estes resultados s˜ao selecionados para ilustrar o comporta-
mento da medida interna de qualidade SC. Para a base com os termos selecionados
com o algoritmo iterativo o valor do SC ´e um pouco maior do que o obtido com
o algoritmo k-means e para a base com os termos selecionados com o algoritmo
guloso, o valor ´e menor. Apesar destes valores serem bem pr´oximos, a an´alise
destas duas tabelas mostra que ambos os resultados s˜ao inferiores aos obtidos com
o algoritmo k-means.
Categorias
Grupos cisi cran med
1 241 6 4
2 0 212 22
3 59 82 274
Tabela 4.54: Grupos X Categorias (S01). 116 termos (sele¸c˜ao iterativa). Algoritmo
de particionamento de grafos - associa¸c˜ao normalizada
Categorias
Grupos cisi cran med
1 287 5 10
2 6 288 38
3 7 7 252
Tabela 4.55: Grupos X Categorias (S01). 99 termos. Algoritmo de particionamento
de grafos - associa¸c˜ao normalizada
4.5 Discuss˜ao dos resultados
O objetivo deste trabalho ´e a investiga¸c˜ao do desempenho de t´ecnicas de
agrupamento de bases de documentos, compreendendo: o pr´e-processamento des-
tas bases, para a cria¸c˜ao das matrizes documento-termo; a implementa¸c˜ao de al-
goritmos de sele¸c˜ao de caracter´ısticas para redu¸c˜ao da dimensionalidade destas
matrizes, com o objetivo de se obter ganhos na qualidade dos resultados e no
tempo de processamento e por fim avaliar se t´ecnicas de agrupamento espectral e
de particionamento de grafos se aplicam para este tipo de problema.
111
Para se testar e validar os resultados dos algoritmos de sele¸c˜ao de caracte-
r´ısticas e os algoritmos de agrupamento, foram utilizadas cinco bases de documen-
tos pr´e-classificadas com diferentes caracter´ısticas. A base S01, derivada da base
Smart, se caracteriza por ter trˆes categorias de documentos de origens distintas: a
categoria cran cont´em documentos sobre astronomia; a categoria cisi cont´em do-
cumentos sobre ciˆencia da informa¸c˜ao e a categoria med cont´em documentos sobre
biomedicina. As bases R01, R02, R03 e R04, derivadas da base Reuters 21758, se
caracterizam por se constituirem de documentos de not´ıcias curtas sobre diferentes
t´opicos.
Uma caracter´ıstica importante separa a base S01 das outras quatro. Cada
uma de suas trˆes categorias s˜ao de ´areas de conhecimento distintas, com um vo-
cabul´ario pr´oprio que caracteriza cada uma delas. As quatro bases derivadas da
Reuters, como s˜ao constitu´ıdas de not´ıcias, cont´em um vocabul´ario mais coloquial
e bastante comum a todas as suas categorias.
Esta caracter´ıstica explica porque ao se utilizar todos os termos gerados no
pr´e-processamento, sem a sele¸c˜ao de caracter´ısticas, o agrupamento da base S01
obteve um resultado excelente, com 98,88% dos seus documentos corretamente alo-
cados aos grupos associados a cada categoria
6
. Esta caracter´ıstica explica tamb´em
porque algumas categorias das bases Reuters, com uma quantidade muito pequena
de documentos, n˜ao s˜ao separ´aveis, qualquer que seja a quantidade de termos uti-
lizados nas matrizes documento-termo, pois os termos relativos a estas categorias
n˜ao possuem um freq
¨
uˆencia suficiente que possa diferenciar os documentos destas.
Na valida¸c˜ao dos resultados s˜ao utilizadas duas ferramentas: a primeira s˜ao
as medidas de qualidade e a segunda ´e a constru¸c˜ao de uma matriz que relacione os
6
Este valor ´e o percentual da soma dos documentos corretamente alocados aos grupos asso-
ciados a cada categoria em rela¸c˜ao ao total de documentos da base
112
documentos de cada uma das categorias com cada um dos grupos formados. Esta
matriz permite facilmente visualizar se o agrupamento produziu um bom resultado
ou n˜ao. O cruzamento desta informa¸c˜ao com os valores das medidas de qualidade
permite que se validem os resultados.
S˜ao utilizadas quatro medidas de qualidade, uma medida interna, que ´e o
Coeficiente de Silhueta (SC) e trˆes externas: Acur´acia M´edia (AA), Estat´ıstica
Rand (RS) e
´
Indice Fowlkes e Mallows (FM). Estas medidas, dentre outras, s˜ao
largamente utilizadas na valida¸c˜ao de resultados de algoritmos de agrupamento.
Os resultados do Coeficiente de Silhueta para todos os agrupamentos mos-
tram claramente a dependˆencia deste coeficiente com o tamanho do vetor que
representa cada documento. Quanto maior o vetor, menor s˜ao os valores desta
medida, implicando que os valores definidos por Kaufman e Rousseeuw (1990) (ver
p´agina 67) usados para definir a qualidade do agrupamento n˜ao podem ser aplica-
dos para avaliar essa qualidade quando o n´umero de dimens˜oes ´e elevado. Mesmo
com as matrizes produzidas a partir da sele¸c˜ao de caracter´ısticas, os valores do SC
n˜ao podem ser comparados com os valores definidos por Kaufmann e Rousseeuw.
Mesmo com esta limita¸c˜ao e de uma maneira geral, o maior valor entre di-
ferentes valores do Coeficiente de Silhueta, mesmo que muito pequeno, indica que
o agrupamento ´e mais adequado do que aquele que tem um valor menor. No en-
tanto isto n˜ao pode ser considerado como uma regra. Por exemplo, na tabela 4.54,
´e mostrado o resultado de um agrupamento do algoritmo de particionamento de
grafos de associa¸c˜ao normalizada, que tem um SC maior que o do agrupamento
realizado com o algoritmo k-means na mesma base e o resultado deste ´ultimo ´e
melhor.
As medidas externas de qualidade, de uma maneira geral s˜ao adequadas,
113
mesmo que, como o Coeficiente de Silhueta, em alguns resultados um valor maior
de uma dessas trˆes medidas n˜ao represente um melhor resultado do agrupamento,
como demonstrado na compara¸c˜ao entre os resultados do agrupamento com algo-
ritmo de particionamento de grafos e os obtidos com o algoritmo k-means.
Um dos objetivos deste trabalho ´e a implementa¸c˜ao de algoritmos de sele¸c˜ao
de caracter´ısticas com o objetivo de se reduzir o tamanho da matriz documento-
termo para se obter melhores resultados no agrupamento. Das cinco bases testadas,
apenas para a base S01, a redu¸c˜ao do n´umero de termos impactou negativamente
nos resultados do agrupamento. Mesmo na base R04, cujos resultados com a
utiliza¸c˜ao de todos os termos s˜ao superiores, a diferen¸ca, tanto com o algoritmo
k-means, quanto com o algoritmo espectral ´e pequena.
Os dois algoritmos propostos neste trabalho apresentam um bom desempe-
nho, considerando-se a qualidade dos resultados e a redu¸c˜ao do tempo de proces-
samento. Quanto ao tempo ´e importante ressaltar que o pro cedimento do agrupa-
mento deve ser repetido diversas vezes para se escolher a melhor solu¸c˜ao, dentre
todas.
Dentre os cinco algoritmos de agrupamento avaliados, apenas o algoritmo k-
means apresentou um tempo de processamento bem superior aos demais, quando
aplicado sobre as bases sem a sele¸c˜ao de temos. Por exemplo, o agrupamento da
base R04 com todos os termos apresentou uma dura¸c˜ao m´edia de 16, 78 segundos,
o que totaliza, ao fim de 30 execu¸c˜oes, aproximadamente 503 segundos. Com a
sele¸c˜ao de caracter´ısticas gulosa, o agrupamento desta mesma base, consome 6, 6
segundos, com as medidas de qualidade apontando um resultado levemente infe-
rior e com a sele¸c˜ao iterativa, consome 7, 5 segundos. Mesmo considerando-se o
tempo de processamento gasto na sele¸c˜ao de termos (0,46 e 3,07 segundos, para
as sele¸c˜oes gulosa e iterativa, respectivamente - tabela 2.5), o tempo total tamb´em
114
´e bem menor em compara¸c˜ao com o temp o despendido na execu¸c˜ao do algoritmo
k-means sobre a base com todo os temos.
Com os outros quatro algoritmos de agrupamento avaliados, o tempo de pro-
cessamento s˜ao b em menores que os tempos do algoritmo k-means sobre as bases
com todos os termos. Analisando-se as tabelas 4.20, 4.36, 4.43 e 4.47 se constata
que os tempos s˜ao fortemente dependentes da quantidade de documentos da base
e em menor grau, dependentes da quantidade de termos. Este fato tem algumas
exce¸c˜oes, como por exemplo o tempo de processamento da base R01, com o al-
goritmo espectral e com termos selecionados com o algoritmo iterativo, ´e superior
aos outros dois tempos de processamento desta mesma base.
Outro objetivo deste trabalho ´e a avalia¸c˜ao de algoritmos que procuram rea-
lizar o agrupamento de base que n˜ao sejam linearmente separ´aveis. Dentre alguns
algoritmos relatados na literatura, s˜ao implementados um algoritmo do tipo espec-
tral e trˆes algoritmos de particionamento de grafos (associa¸c˜ao ponderada, corte
ponderado e associa¸c˜ao normalizada).
Os resultados obtidos pelo algoritmo espectral foram bem pr´oximos dos re-
sultados obtidos com o algoritmo k-means, que reconhecidamente tem a limita¸c˜ao
de n˜ao encontrar solu¸c˜oes ´otimas em bases n˜ao-linearmente separ´aveis. Por exem-
plo, a base R01, que se caracteriza por uma grande disparidade no tamanho de
suas categorias, o que pode acarretar que os documentos de uma ou outra catego-
ria estejam, parcialmente ou totalmente, contidos em uma categoria maior, ao ser
agrupada com o algoritmo espectral, combinado com a sele¸c˜ao iterativa de termos,
apresentou um resultado superior. Apesar das medidas de qualidade serem leve-
mente inferiores `as medidas obtidas com o algoritmo k-means, aproximadamente
79,48% dos documentos s˜ao corretamente agrupados com o algoritmo espectral,
enquanto que com o algoritmo k-means 73,23% s˜ao corretamente agrupados.
115
Outro exemplo, no qual o algoritmo espectral tem um resultado superior, ´e
o agrupamento da base R04, pois nesta base em dois dos trˆes agrupamentos rea-
lizados (com todos termos e com os termos selecionados com o algoritmo guloso),
as categorias ipi e wpi s˜ao separadas em grupos distintos.
Estes resultados s˜ao encorajadores em rela¸c˜ao ao uso do algoritmo espectral,
e na procura de alternativas que contornem a sua limita¸c˜ao de exigir a atribui¸c˜ao
de uma valor para o parˆametro σ da fun¸c˜ao gaussiana, utilizada na constru¸c˜ao da
matriz de afinidades.
Os resultados obtidos pelos trˆes algoritmos de particionamento de grafos
(associa¸c˜ao ponderada, corte ponderado e associa¸c˜ao normalizada) s˜ao de uma
maneira geral, inferiores aos resultados obtidos com os algoritmos k-means e es-
pectral. Ocorrem trˆes exce¸c˜oes: (1) O algoritmo de associa¸c˜ao ponderada separa
as categorias trade e money-fx da base R02 com os termos selecionados com o al-
goritmo guloso, com um resultado superior que o algoritmo espectral (o algoritmo
k-means n˜ao separa estas duas categorias); (2) Os resultados do agrupamento da
base R04, com esse mesmo algoritmo, s˜ao bem pr´oximos aos obtidos pelo algoritmo
espectral e superiores ao algoritmo k-means; (3) o algoritmo de corte ponderado
resolve a fragmenta¸c˜ao, que ocorre nos resultados obtidos dos algoritmos k-means
e espectral, da categoria crude da base R01 com termos selecionados com o algo-
ritmo iterativo.
A escolha destes algoritmos para serem avaliados se deve justamente pela
sua capacidade, de acordo com a literatura, de contornar a limita¸c˜ao do algoritmo
k-means de separar grupos n˜ao linearmente separ´aveis, limita¸c˜ao esta que pode ser
uma explica¸c˜ao para os problemas detectados na constitui¸c˜ao de grupos que sejam
correspondentes `as categorias trade, money-fx e crude no agrupamento com os al-
116
goritmos k-means e espectral. No entanto este bom desempenho n˜ao se repete no
agrupamento de outras bases e pelo contr´ario, em algumas situa¸c˜oes ´e bem inferior
aos outros algoritmos avaliados.
117
Cap´ıtulo 5
Conclus˜oes
Neste trabalho s˜ao introduzidos dois algoritmos de sele¸c˜ao de caracter´ısticas
e avaliados algoritmos de agrupamentos. Estes algoritmos s˜ao aplicados para a
identifica¸c˜ao de textos correlatos em bases de dados textuais.
Os dois algoritmos de sele¸c˜ao de caracter´ısticas, iterativo ou guloso, reduzem
a quantidade de termos a aproximadamente 1, 3% da quantidade de termos ini-
cial, reduzindo sensivelmente a matriz documento-termo. Os resultados obtidos,
ao se utilizar esta nova matriz documento-termo, apontam claramente que o uso
de algoritmos de sele¸c˜ao de caracter´ısticas impactam positivamente nos resultados
do agrupamento de bases de dados textuais, que compartilhem de um vocabul´ario
comum, tornando mais eficaz o processo de se identificar termos que discriminem
grupos de textos correlatos. Por outro lado, se a base de texto for constitu´ıda por
grupos de textos bem distintos, caracterizando-se por ter uma vocabul´ario comum
reduzido, tem-se a indica¸c˜ao que a sele¸c˜ao de caracter´ısticas, impacta negativa-
mente no processo de agrupamento de textos, provavelmente por selecionar termos
que n˜ao sejam bons discriminantes.
Dentre os algoritmos de agrupamento avaliados, os algoritmos k-means e es-
pectral tˆem resultados semelhantes, com uma ligeira vantagem para o algoritmo
k-means, quando avaliam-se as medidas de qualidade aplicadas. No entanto, em
118
algumas situa¸c˜oes onde algoritmo k-means n˜ao separou em grupos distintos dife-
rentes categorias, o algoritmo espectral tem um desempenho melhor, separando
corretamente estas categorias.
Uma segunda vantagem do algoritmo espectral em rela¸c˜ao ao algoritmo k-
means ´e que em qualquer circunstˆancia, o seu tempo de processamento ´e baixo
e para o algoritmo k-means, quando agrupa bases com todos os termos, o tempo
de processamento ´e bastante alto. Uma desvantagem do algoritmo espectral ´e a
necessidade de se definir o valor do parˆametro σ, para a fun¸c˜ao gaussiana. Os tes-
tes realizados indicam que este parˆametro ´e muito dependente da base de textos
utilizada.
Os algoritmos de particionamento de grafos, apesar de em alguns casos espe-
c´ıficos conseguirem separar categorias que os algoritmos k-means e espectral n˜ao
conseguem, tˆem o problema de obterem resultados bem inferiores na maioria dos
agrupamentos realizados, em particular o algoritmo de corte ponderado.
O conjunto de avalia¸c˜oes realizadas indicam que a sele¸c˜ao de caracter´ısticas
e os algoritmos k-means e espectral podem ser utilizados para o agrupamento de
bases de dados textuais.
119
Cap´ıtulo 6
Perspectivas Futuras
Como continuidade deste trabalho, prop˜oe-se:
Avaliar outras medidas de importˆancia de termos, tais como a TS, TV e
TVQ a serem utilizadas pelos algoritmos de sele¸c˜ao de caracter´ısticas;
Avaliar outros valores para o parˆametro L do algoritmo de sele¸c˜ao de
caracter´ısticas iterativo;
Implementa¸c˜ao de t´ecnicas que contornem a limita¸c˜ao do algoritmo k-
means convergir para solu¸c˜oes locais, tais como o uso de Particle Swarm
Optimization (PSO) para a escolha dos centr´oides iniciais e a utiliza¸c˜ao
desta solu¸c˜ao h´ıbrida para o agrupamento de bases de dados textuais;
Implementa¸c˜ao de t´ecnicas para a identifica¸c˜ao do valor ´otimo para o pa-
rˆametro σ utilizado no algoritmo espectral;
Implementa¸c˜ao de medidas internas de qualidade, tais como os
´
Indices
Dunn e Davies-Bouldin e avalia¸c˜ao do emprego destes ´ındices e do Coe-
ficiente de Silhueta para a determina¸c˜ao do n´umero k de grupos, a ser
utilizado como parˆametro dos algoritmos de agrupamento de bases de da-
dos textuais.
120
Referˆencias Bibliogr´aficas
Ajith Abraham, Swagatam Das, e Amit Konar. Document clustering using diffe-
rential evolution. IEEE Congress on Evolutionary Computation CEC,
p´aginas 1784–1791, July 2006.
Charu C. Aggarwal e Philip S. Yu. Finding generalized projected clusters in high
dimensional spaces. In: Weidong Chen, Jeffrey F. Naughton, e Philip A. Berns-
tein (editores), SIGMOD Conference, p´aginas 70–81. ACM, 2000. ISBN
1-58113-218-2.
Rakesh Agrawal e Ramakrishnan Srikant. Fast algorithms for mining association
rules. Proceedings of the 20th VLDB Conference, 1994.
Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, e Joydeep Guosh. Clus-
tering with bregman divergences. Journal of Machine Learning Research,
6:1705–1749, October 2005.
Florian Beil, Martin Ester, e Xiaowei Xu. Frequent term-based text clustering.
Proceedings of the eighth ACM SIGKDD international conference on
Knowledge discovery and data mining, p´aginas 436–442, 2002.
P. Berkhin. A Survey of Clustering Data Mining Techniques. In: Jacob
Kogan, Charles Nicholas, e Marc Teboulle (editores), Grouping Multidimen-
sional Data: Recent Advances in Clustering. Cap´ıtulo 2, p´aginas 25–71,
Springer, 2006.
Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, e Uri Shaft. When is
121
”nearest neighbor”meaningful? Lecture Notes in Computer Science, 1540:
217–235, 1999. URL citeseer.ist.psu.edu/beyer99when.html.
T. De Bie, N. Cristianini, e R. Rosipal. Eigenproblems in Pattern Recogni-
tion. In: E. Bayro-Corrochano (editor), Handbook of Geometric Compu-
ting : Applications in Pattern Recognition, Computer Vision, Neu-
ralcomputing, and Robotics. p´aginas 129–170, Springer-Verlag, Heidelberg,
2005.
Tijl De Bie e Nello Cristianini. Kernel Methods for Exploratory Pattern
Analysis: A Demonstration on Text Data. In: Ana Fred, Terry Caelli,
Robert P.W. Duin, Aur´elio Campilho, e Dick de Ridder (editores), Structural,
Syntactic, and Statistical Pattern Recognition Joint IAPR Interna-
tional Workshops, SSPR 2004 and SPR 2004. p´aginas 16–29, Springer,
October 2004.
Daniel Boley, Maria Gini, Robert Gross, Eui-Hong Han, George Karypis, Vipin
Kumar, Bamshad Mobasher, Jerome Moore, e Kyle Hastings. Partitioning-based
clustering for web document categorization. Decision Support Systems, 27
(3):329–341, 1999.
N. Bolshakova e F. Azuaje. Cluster validation techniques for genome expression
data. Signal Processing, 83(4):825–833, April 2003.
Christian Borgelt e Andreas N
¨
urnberger. Experiments in document clustering using
cluster specific term weights. Proceedings Workshop Machine Learning
and Interaction for Text-based Information Retrieval, 2004.
Colin Campbell. An introduction to kernel methods. In: R.J. Howlett e
editors L.C. Jain (editores), Radial Basis Function Networks: Design and
Applications. Springer Verlag, 2000.
Pak K. Chan, Martine D.F. Schlag, e Jason Y. Zien. Spectral k-way ratio-cut par-
122
titioning and clustering. IEEE Transactions on Computer-Aided Design
of Integrated Circuits and Systems, 13(9):1088–1096, September 1994.
Ajay Choudharil, Madasu Hanmandlu, Nishchal K. Verma, e R.D. Choudhari.
Mesh based clustering without stopping criterion. Proceedings of the IEEE
Indicon 2005 Conference, p´aginas 11 – 13, Dec 2005.
Bhoop esh Choudhary e Pushpak Bhattacharyya. Text clustering using seman-
tics. Proceedings of the The Eeleventh International World Wide Web
Conference, May 2002.
Xiaohui Cui e Thomas E. Potok. Document clustering analysis based on hybrid pso
+ k-means algorithm. Journal of Computer Sciences, Special Issue:27–33,
2005.
Douglas R. Cutting, David R. Karger, Jan O. Pedersen, e John W. Tukey. Scat-
ter / gather: A cluster-based approach to browsing large document collections.
Proceedings of the 15th annual international ACM SIGIR conference
on Research and development in information retrieval, p´aginas 318–329,
1992.
Manoranjan Dash e Huan Liu. Feature selection for clustering. Proceedings
Knowledge Discovery and Data Mining, Current Issues and New Ap-
plications, 4th Pacific-Asia Conference, PAKDD, 1805:110–121, 2000.
D. L. Davies e D. W. Bouldin. A cluster separation measure. IEEE Transactions
on Pattern Analysis and Machine Learning, 1(2):224–227, 1979.
Inderjit Dhillon, Yuqiang Guan, e Brian Kulis. A unified view of kernel k-means,
spectral clustering and graph cuts. Technical report TR-04-25, Departament of
Computer Sciences, University of Texas at Austin, February 2005.
Inderjit Dhillon, Jacob Kogan, e Charles Nicholas. Feature selection and document
clustering. A Comprehensive Survey of Text Mining - Lecture Notes in
Computer Science, p´aginas 73–100, 2002a.
123
Inderjit S. Dhillon. Co-clustering documents and words using bipartite spectral
graph partitioning. KDD ’01: Proceedings of the seventh ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining,
p´aginas 269–274, 2001.
Inderjit S. Dhillon, Yugiang Guan, e Brian Kulis. Kernel k-means: spectral clus-
tering and normalized cuts. Proceedings of the Tenth ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining,
p´aginas 551–556, 2004.
Inderjit S. Dhillon, Yuqiang Guan, e J. Kogan. Iterative clustering of high di-
mensional text data augmented by local search. Proceedings of the IEEE
International Conference on Data Mining, 2002b.
Inderjit S. Dhillon e Dharmendra S. Modha. Concept decompositions for large
sparse text data using clustering. Machine Learning, 42(1/2):143–175, 2001.
J. Dunn. Well separated clusters and optimal fuzzy partitions. Journal of Cy-
bernetics, 4:95–104, 1974.
Ramez Elmasri e Shamkant B. Navathe. Sistemas de Bancos de Dados. Ad-
dison Wesley, 2005. ISBN 85-88639-17-3.
Levent Ert
¨
oz, Michael Steinbach, e Vipin Kumar. Finding clusters of different
sizes, shapes, and densities in noisy, high dimensional data. Proceedings of
the Third SIAM International Conference on Data Mining, 2003.
L. Ertz, M. Steinbach, e V. Kumar. Finding topics in collections of documents:
A shared nearest neighbor approach. Text Mine ’01, Workshop on Text
Mining, First SIAM International Conference on Data Mining, 2001.
Martin Ester, Hans-Peter Kriegel, Jorg Sander, e Xiaowei Xu. A density-based
algorithm for discovering clusters in large spatial databases with noise. Procee-
dings of the Second International Conference on Knowledge Discovery
and Data Mining, p´aginas 226–231, 1996.
124
Arrigo P Fattore M. Topical clustering of biomedical abstract by self organizing
maps. Proceedings of the Fourth International Conference on Bioin-
formatics of Genome Regulation and Structure, 2, July 2004.
M. Filippone, F. Camastra, F. Masulli, e S. Rovetta. A survey of kernel and
spectral methods for clustering. Technical report DISI-TR-06-19, Dipartimento
di Informatica e Scienze dell’Informazione, Universit`a di Genova e Dipartimento
di Scienze Applicate, Universit`a di Napoli Parthenope, October 2006.
E. W. Forgy. Cluster analysis of multivariate data: Efficiency vs. interpretability
of classifications. Biometrics, 21:768–769, 1965.
E. B. Fowlkes e C. L. Mallows. A method of comparing two hierarchical clusterings.
Journal of the American Statistical Association, 78:553–569, 1983.
Benjamin C. M. Fung, Ke Wang, e Martin Ester. Hierarchical document clustering
using frequent itemsets. Proceedings of the Third SIAM International
Conference on Data Mining, 2003.
Gene H. Golub e Charles F. Van Loan. Matrix Computations. John Hopkins
University Press, 3rd edi¸c˜ao, 1996.
Maria Halkidi, Yannis Batistakis, e Michalis Vazirgiannis. Cluster validity
methods: Part i. ACM SIGMOG Record, 31(2):40–45, June 2002.
Khaled M. Hammouda e Mohamed S. Kamel. Document similarity using a phrase
indexing graph model. Knowledge and Information Systems, 6(6):710–727,
2004.
Ji He, Ah-Hwee Tan, Chew-Lim Tan, e Sam-Yuan Sung. On Quantitative Evalu-
ation of Clustering Systems. In: W. Wu e H. Xiong (editores), Information
Retrieval and Clustering. Kluwer Academic Publishers, 2002.
Marti A. Hearst. Untangling text data mining. Proceedings of ACL’99: the
125
37th Annual Meeting of the Association for Computational Linguis-
tics, p´aginas 3–10, 1999.
A. Hotho, A. Madche, e S. Staab. Ontology-based text clustering. Text Learning:
Beyond Supervision,IJCAI 2001, 2001.
Andreas Hotho, Andreas N
¨
urnberger, e Gerhard Paaß. A brief survey of text
mining. LDV Forum - GLDV Journal for Computational Linguistics
and Language Technology, 20(1):19–62, MAY 2005.
Andreas Hotho, Steffen Staab, e Gerd Stumme. Wordnet improves text document
clustering. Proceedings of the SIGIR 2003 Semantic Web Workshop,
2003.
Yifen Huang e Tom M. Mitchell. Text clustering with extended user feedback.
Proceedings of the 29th annual international ACM SIGIR conference
on Research and development in information retrieval, p´aginas 413–420,
2006.
Chihli Hung e Stefan Wermter. Neural network based document clustering using
wordnet ontologies. International Journal of Hybrid Intelligent Systems,
1(3-4):127–142, 2004.
I. Iliopoulos, A. J. Enright, e C. A. Ouzounis. Textquest: Document clustering of
medline abstracts for concept discovery in molecular biology. Pacific Sympo-
sium on Biocomputing, 6:384–395, 2001.
A. K. Jain e R. C. Dubes. Algorithms for Clustering Data. Prentice-Hall
advanced references. Prentice-Hall, Inc., 1988.
A. K. Jain, M. N Murty, e P. J. Flynn. Data clustering: A review. ACM Com-
puting Surveys, 31(3):264–323, September 1999.
R. A. Jarvis e E. A. Patrick. Clustering using a similarity measure based on shared
126
nearest neighbors. IEEE Transactions on Computers, C-22(11), November
1973.
Xiang Ji, Wei Xu, e Shenghuo Zhu. Document clustering with prior knowledge.
Proceedings of the 23rd annual international ACM SIGIR conference
on Research and development in information retrieval, p´aginas 208–215,
2000.
Liping Jing, Lixin Zhou, Michael K. Ng, e Joshua Zhexue Huang. Ontology-based
distance measure for text clustering. Proceedings of the Fourth Workshop
on Text Mining, Sixth SIAM International Conference on Data Mi-
ning, April 2006.
I. T. Jolliffe. Principal component analysis. Springer Series in Statistics, 1986.
Karen Sp
¨
arck Jones. A statistical interpretation of term specificity and its appli-
cation in retrieval. Journal of Documentation, 28(1):11–21, 1972.
Alexandros Karatzoglou e Ingo Feinerer. Text clustering with string kernels in r.
Report 34, Wirtschafts Universitat Wein, May 2006.
Leonard Kaufman e Peter J. Rousseeuw. Finding Groups in Data: An In-
troduction to Cluster Analysis. John Wiley Sons Inc., 1990. ISBN 0-471-
87876-6.
J. Kennedy e R. Eberhart. Particle swarm optimization. Proceedings of
the IEEE Internation Conference on Neural Networks, 4:1942–1948,
Nov/Dec 1995.
Jan Klein, Philip Bittihn, Peter Ledochowitsch, Horst K. Hahn, Olaf Konrad, Jan
Rexilius, e Heinz-Otto Peitgen. Grid-based spectral fiber clustering. Proce-
edings of SPIE - Medical Imaging 2007: Visualization and Image-
Guided Procedures, 6509, March 2007.
127
A. Klose, A. N
¨
urnberger, R. Kruse, G. Hartamann, e M. Richards. Interactive
text retrieval based on document similarities. Physics ans Chemistry of the
Earth, 25(8):649–654, 2000.
Teuvo Kohonen, Samuel Kaski, Krista Lagus, Jarkko Saloj
¨
arvi, Jukka Honkela,
Vesa Paatero, e Antti Saarela. Self organization of a massive do cument collection.
IEEE Transaction on Neural Networks, 11(3), May 2000.
Ferenc Kov´acs, Csaba Leg´any, e Attila Babos. Cluster validity measuremen tech-
niques. Proceedings of the 6th International Symposium of Hungarian
Researchers on Computational Intelligence, 2005.
Bjornar Larsen e Chinatsu Aone. Fast and effective text mining using linear-time
document clustering. Proceedings of the fifth ACM SIGKDD internatio-
nal conference on Knowledge discovery and data mining, p´aginas 16–22,
1999.
David D. Lewis. Reuters-21578 text categorization test collection. Relat´orio t´ec-
nico, http://kdd.ics.uci.edu/databases/reuters21578/README.txt, September
1997. URL acessada em 30/06/2007.
Wenyuan Li, Wee-Keong Ng, e Ee-Peng Lim. Spectral analysis of text colection for
similarity-based clustering. Advances in Knowledge Discovery and Data
Mining, p´aginas 389–393, 2004.
Luying Liu, Jianchu Kang, Jing YU, e Zhongliang Wang. A comparative study
on unsupervised feature selection methods for text clustering. Proceeding of
Natural Language Processing and Knowledge Engineering’05, October,
November 2005.
Julie Beth Lovins. Development of a stemming algorithm. Mechanical Transla-
tion and Computational Linguistics, 11(1):23–31, 1968.
Wei-Ying Ma, Tao Liu, Shenping Liu, e Zheng Chen. An evaluation on feature
128
selection for text clustering. Proceedings of the Twentieth International
Conference on Machine Learning (ICML-2003), 2003.
James B. MacQueen. Some methods for classification and analysis of multivariate
observations. 5th Berkeley Symp. Math Statist. Prob., 1:281–297, 1967.
Giansalvatore Mecca, Salvatore Raunich, e Alessandro Pappalardo. A
new algorithm for clustering search results. Relat´orio t´ecnico, Di-
partimento di Matematica e Informatica - Universit`a della Basilicata,
http://www.db.unibas.it/projects/noodles, April 2006. URL acessada em
30/06/2007.
A. Ng, M. Jordan, e Y. Weiss. On spectral clustering: Analysis and an algorithm.
Advances in Neural Information Processing Systems, 2001.
NLM. Medline fact sheet. Relat´orio t´ecnico, Natio-
nal Library of Medicine - National Institures of Health,
http://www.nlm.nih.gov/pubs/factsheets/medline.html, December 2006a.
URL acessada em 30/03/2007.
NLM. Pubmed : Medline retrieval on the world wide web. Relat´o-
rio t´ecnico, National Library of Medicine - National Institures of Health,
http://www.nlm.nih.gov/pubs/factsheets/pubmed.html, December 2006b. URL
acessada em 30/03/2007.
NLM. What’s the difference between medline and pubmed ? Relat´o-
rio t´ecnico, National Library of Medicine - National Institures of Health,
http://www.nlm.nih.gov/pubs/factsheets/dif med pub.html, December 2006c.
URL acessada em 30/03/2007.
NLM. Medline : Number of citations to english language ar-
ticles; number of citations containing abstracts. Relat´orio t´ec-
nico, National Library of Medicine - National Institures of Health,
129
http://www.nlm.nih.gov/bsd/medline lang distr.html, February 2007. URL
acessada em 23/05/2007.
P. Perona e W. T. Freeman. A factorization approach to grouping. Proceedings
of the 5th European Conference on Computer Vision, p´aginas 655–670,
1998.
Slobodan Petrovic. A comparison between the silhouette index and the davies-
bouldin index in labelling ids clusters. Proceedings of the 11th Nordic
Workshop on Secure IT-systems, NORDSEC 2006, 2006.
M. F. Porter. An algorithm for suffix stripping. Program, 14(3):130–137, July
1980.
W. M. Rand. Objective criteria for the evaluation of clustering methods. Journal
of the American Statistical Association, 66:846–850, 1971.
C. J. Rijsbergen. Information Retrieval. Butterworths, 2 edi¸c˜ao, 1979.
M. E. S. Mendes Rodrigues e L. Sacks. A scalable hierarchical fuzzy clustering al-
gorithm for text mining. Proceedings of the 4th International Conference
on Recent Advances in Soft Computing - RASC’2004, p´aginas 269–274,
December 2004.
Stuart Russel e Peter Norvig. Inteligˆencia Artificial. Elsevier Editora Ltda., 2
edi¸c˜ao, 2004. ISBN 853521177-2.
G. Salton, A. Wong, e C. S. Yang. A vector space model for automatic indexing.
Communications of the ACM, 18(11):613–620, November 1975.
Matthew J. Scanlan, Andrew J. G. Simpson, e Lloyd J. Old. The cancer/testis ge-
nes: Review, standardization, and commentary. Cancer Immunity, 4, January
2004.
130
Bernhard Scholkopf, Alexander Smola, e Klaus-Robert M
¨
uller. Nonlinear com-
ponent analysis as a kernel eigenvalue problem. Technical Report TR-44, Max
Planck Institut f
¨
ur Biologische Kybernetik, Decemb er 1996.
G. L. Scott e H. C. Longuet-Higgins. Feature grouping by relocalization: eigenva-
lues and eigenvectors. Proceedings of the British Machine Vision Confe-
rence, p´aginas 103–108, 1990.
Jianbo Shi e Jitendra Malik. Normalized cuts and image segmentation. Pro-
ceedings of the IEEE Conference on Computer Vision and Pattern
Recognition, p´aginas 731–737, June 1997.
Andrew J. G. Simpson, Otavia L. Caballero, Achim Jungbluth, Yao-Tseng Chen,
e Lloyd J Old. Cancer/testis antigens, gametogenesis and cancer. Nature
Reviews Cancer, 5(8):615–625, August 2005.
Dawid Weiss Stanislaw Osi´nski. Carrot2: Design of a flexible and efficient web
information retrieval framework. Proceedings of the third International
Atlantic Web Intelligence Conference (AWIC 2005), 3528:439–444, 2005.
Benno Stein, Sven Meyer zu Eissen, e Frank Wibrock. On cluster validity and
the information need of users. 3rd IASTED Int. Conference on Artificial
Intelligence and Applications, p´aginas 216–221, September 2003.
M. Steinbach, G. Karypis, e V. Kumar. A comparison of document clustering
techniques. KDD Workshop on Text Mining, 2000.
Michael Steinbach, Levent Ert
¨
oz, e Vipin Kumar. The challenges of clustering high
dimensional data. New Vistas in Statistical Physics – Applications in
Econophysics, Bioinformatics, and Pattern Recognition, 2003.
Rainer Storn e Kenneth Price. Differential evolution - a simple and efficient heu-
ristic for global optimation over continuos spaces. Jounal of Global Optimi-
zation, 11:341–359, 1997.
131
Pang-Ning Tan, Michael Steinbach, e Vipin Kumar. Introduction To Data
Mining. Addison Wesley, 2005. ISBN 0321321367.
L. Tanabe, U. Scherf, L.H. Smith, J.K. Lee1, L. Hunter, e J.N. Weinstein. Medmi-
ner: An internet text-mining tool for biomedical information, with application
to gene expression profiling. BioTechniques, 27:1210–1217, December 1999.
M. E. Wall, A. Rechtsteiner, e L. M. Rocha. Singular value decomposition and
principal comp onent analysis. ArXiv Physics e-prints, August 2002.
Fei Wang e Changshui Zhang. Spectral clustering for time series. Proceedings
of the International Conference on Advances in Pattern Recognition
(Lecture Notes in Computer Science: Pattern Recognition and Data
Mining), August 2005.
Wei Wang, Jiong Yang, e Richard R. Muntz. Sting: A statistical information
grid approach to spatial data mining. Proceedings of the Twenty-Third
International Conference on Very Large Data Bases, p´aginas 186–195,
1997.
Yair Weiss. Segmentation using eigenvectors: a unifying view. Seventh Interna-
tional Conference on Computer Vision (ICCV’99), 2, 1999.
W. John Wilbur e Karl Sirotkin. The automatic identification of stop words.
Journal of Information Science, 18(1):45–55, 1992.
Yasunori Yamamoto e Toshihisa Takagi. Biomedical knowledge navigation by lite-
rature clustering. Journal of Biomedical Informatics, 40:114–130, 2007.
Yiming Yang e Jan O. Pedersen. A comparative study on feature selection in text
categorization. Proceedings of ICML-97, 14th International Conference
on Machine Learning, p´aginas 412–420, 1997.
Illhoi Yoo e Xiaohua Hu. A comprehensive comparison study of document clus-
tering for a biomedical digital library medline. International Conference on
132
Digital Libraries, Proceedings oh the 6th ACN/IEEE-CS Joint Con-
ference on Digital Libraries, p´aginas 220–229, 2006.
Illhoi Yoo, Xiaohua Hu, e Il-Yeol Song. Clustering ontology-enriched graph repre-
sentation for biomedical documents based on scale-free network theory. Proce-
edings of the IEEE Conference on Intelligent Systems (IEEE IS
´
06),
2006.
Oren Zamir e Oren Etzioni. Web document clustering: A feasibility demonstra-
tion. Proceedings of the 19th International ACM SIGIR Conference
on Research and Development in Information Retrieval, p´aginas 46–54,
1998.
Oren Zamir e Oren Etzioni. Grouper: A dynamic clustering interface to web
search results. Computer Networks (Amsterdam, Netherlands: 1999),
31(11-16):1361–1374, 1999.
Lihi Zelnik-Manor e Pietro Perona. Self-tuning spectral clustering. Advances in
Neural Information Processing Systems, 2004.
Ying Zhao e George Karypis. Criterion function for document clustering - experi-
ments and analysis. Technical Report 01-40, University of Minnesota, Departa-
ment of Computer Science / Army HPC Research Center, November 2001.
Zheng Zhao e Huan Liu. Spectral feature selection for supervised and unsupervi-
sed learning. Proceedings of 24
th
International Conference on Machine
Learning, 2007.
Shi Zhong e Joydeep Ghosh. Generative model-based document clustering: a
comparative study. Knowledge and Information Systems, 8(3):374–384,
2005.
Ling Zhuang e Honghua Dai. A maximal frequent itemset approach for web do-
cument clustering. Proceedings of the Fourth International Conference
on Computer and Information Technology (CIT’04), 2004.
133
Leonid Zhukov. Spectral clustering of large advertiser datasets. Technical report,
Department of Computer Science, California Institute of Technology, January
2004.
Sven Meyer zu Eissen, Benno Stein, e Martin Potthast. The suffix tree document
model revisited. Proceedings of the I-KNOW05, 5th International Con-
ference on Knowledge Management, Journal of Universal Computer
Science, p´aginas 596–603, July 2005.
134
Apˆendice A
A.1 Exemplo de pr´e-processamento
A seq
¨
uˆencia de figuras a seguir (A.1 a A.5) ilustra o pr´e-processamento de
um ´unico texto, at´e se obter o conjunto m´ınimo de palavras, a partir do qual ser´a
constru´ıdo o vetor de freq
¨
uˆencias. A figura A.1 mostra o texto inicial com 136
palavras. Na figura A.5 ´e mostrado o texto ap´os o pr´e-processamento, onde restam
apenas 57 termos. Cada termo corresponde a uma dimens˜ao do vetor de freq
¨
uˆen-
cias.
Figura A.1: Texto original
135
Figura A.2: Texto com todas as letras transformadas em min´usculas
Figura A.3: Texto sem n´umeros
Figura A.4: Texto sem palavras sem valor informacional (to, the,for etc)
Figura A.5: Texto ap´os a retirada dos sufixos das palavras e sem caracteres gr´aficos
136
Apˆendice B
B.1 Medidas de qualidade na escolha do parˆametro σ do algoritmo
de agrupamento espectral
Figura B.1: Medidas de qualidade do
agrupamento (R01). 38 termos (sele-
¸c˜ao iterativa).
Figura B.2: Medidas de qualidade do
agrupamento (R01). 58 termos.
Figura B.3: Medidas de qualidade do
agrupamento (R01). 5666 termos.
Figura B.4: Medidas de qualidade do
agrupamento (R02). 83 termos (sele-
¸c˜ao iterativa).
137
Figura B.5: Medidas de qualidade do
agrupamento (R02). 169 termos.
Figura B.6: Medidas de qualidade do
agrupamento (R02). 7735 termos.
Figura B.7: Medidas de qualidade do
agrupamento (R03). 55 termos (sele-
¸c˜ao iterativa)
Figura B.8: Medidas de qualidade do
agrupamento (R03). 185 termos.
Figura B.9: Medidas de qualidade do
agrupamento (R03). 6316 termos.
Figura B.10: Medidas de qualidade do
agrupamento (R04). 33 termos (sele-
¸c˜ao iterativa)
138
Figura B.11: Medidas de qualidade do
agrupamento (R04). 28 termos.
Figura B.12: Medidas de qualidade do
agrupamento (R04). 3572 termos.
Figura B.13: Medidas de qualidade do
agrupamento (S01). 116 termos (sele-
¸c˜ao iterativa).
Figura B.14: Medidas de qualidade do
agrupamento (S01). 99 termos.
Figura B.15: Medidas de qualidade do agrupamento (S01). 7272 termos.
139
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
