ads:
AGRUPAMENTO ÓTIMO DE INFORMAÇÕES NÃO-ESTRUTURADAS
IMPLEMENTADO EM UM GERENCIADOR DE BANCO DE DADOS
RELACIONAL
Renan Cavalcanti Filgueiras de Souza
DISSERTAÇÃO SUBMETIDA AO CORPO DOCENTE DA COORDENAÇÃO DOS
PROGRAMAS DE PÓS-GRADUAÇÃO DE ENGENHARIA DA UNIVERSIDADE
FEDERAL DO RIO DE JANEIRO COMO PARTE DOS REQUISITOS
NECESSÁRIOS PARA A OBTENÇÃO DO GRAU DE MESTRE EM CIÊNCIAS EM
ENGENHARIA CIVIL.
Aprovada por:
________________________________________________
Prof. Nelson Francisco Favilla Ebecken, D.Sc.
________________________________________________
Prof. Alexandre Gonçalves Evsukoff, Dr.
________________________________________________
Prof. Claudio Luiz Curotto, D.Sc.
RIO DE JANEIRO, RJ - BRASIL
AGOSTO DE 2007
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
SOUZA, RENAN CAVALCANTI FILGUEIRAS DE
Agrupamento Ótimo de Informações Não-
Estruturadas Implementado em um Gerenciador de
Banco de Dados Relacional [Rio de Janeiro] 2007
IX, 75 p. 29,7 cm (COPPE/UFRJ, M. Sc.,
Engenharia Civil, 2007)
Dissertação - Universidade Federal do Rio de
Janeiro, COPPE
1. Text mining
2. Clustering
3. Banco de dados
I. COPPE/UFRJ II. Título (série)
ii
ads:
Agradecimentos
A Deus, em primeiro lugar.
Minha família, em especial meu pai, Tadeu, pelo incentivo nos momentos difíceis, pelos
conselhos, que sempre levo muito a sério e pelo exemplo profissional e moral, que nunca
me faltaram dentro de casa. Exemplos esses que me fazem a cada dia mais tentar ser um
homem melhor para deixá-lo sempre orgulhoso.
Meu irmão Denis pelos risos e momentos agradáveis durante o almoço.
Minha irmã Suyan pela amizade e sinceridade no dia a dia.
Minha namorada, Rosemery, pelos momentos de apoio e conforto quando necessitei.
Meu orientador e amigo, Prof. Nelson Francisco Favilla Ebecken pelo companheirismo,
norteamento e incentivo.
Aos amigos Ângelo, Daniel, Egna, Gilberto, Graziella, Guilherme, Moreira, Rogério e
Valeria, que fazem do meu dia-a-dia de trabalho mais feliz.
Meus amigos, pelo companheirismo e entendimento nos momentos em que me fiz
ausente para a conclusão desta pesquisa.
Aos Srs. Bogdan Crivat e Jamie MacLennan, do time de desenvolvimento do SQL Server
2005 da Microsoft, pelas dúvidas prontamente tiradas online.
A todos os envolvidos na Rede de Tecnologias Convergentes.
Ao CNPq, pela viabilização financeira desta pesquisa.
iii
Resumo da Dissertação apresentada à COPPE/UFRJ como parte dos requisitos
necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)
AGRUPAMENTO ÓTIMO DE INFORMAÇÕES NÃO-ESTRUTURADAS
IMPLEMENTADO EM UM GERENCIADOR DE BANCO DE DADOS
RELACIONAL
Renan Cavalcanti Filgueiras de Souza
Agosto/2007
Orientador: Nelson Francisco Favilla Ebecken
Programa: Engenharia Civil
O presente trabalho descreve uma aplicação de clustering de informações não-
estruturadas em um ambiente de e-ciência para a análise do conhecimento. A
metodologia utilizada consiste de diversos passos e cada um é explicado. Os textos são
comentários de especialistas de diversas áreas participantes da rede temática e o que se
busca encontrar é a fusão de seus conhecimentos em clusters e a determinação da
relevância de seus comentários. Foi importante também que a concepção dos clusters
fosse integrada ao banco de dados relacional utilizado. Para tanto, uma série de métodos,
tanto a nível técnico quanto a nível de data mining foram implementados e são
detalhados nesta dissertação.
iv
Abstract of Dissertation presented to COPPE/UFRJ as a partial fulfillment of the
requirements for the degree of Master of Science (M.Sc.)
OPTIMAL CLUSTERING OF NON-STRUCTURED INFORMATION
IMPLEMENTED ON A RELATIONAL DATABASE MANAGER
Renan Cavalcanti Filgueiras de Souza
August/2007
Advisor: Nelson Francisco Favilla Ebecken
Department: Civil Engineering
This work presents a clustering application of non-structured information
embedded in an environment of e-science for knowledge analysis. The used methodology
consists of diverse steps and each one is detailed. The texts are comments of experts
related to many areas of a thematic network and what the aim is to find the fusion of their
knowledge in clusters and the determination of the relevance of their comments. It was
also important that the conception of clusters was integrated to the used relational
database. In such a way, various methods in the technical level and in the data mining
level had been implemented and they are also commented in this work.
v
Sumário
1. Introdução..................................................................................................................... 10
1.1. E-ciência .................................................................................................................... 2
1.2. A Rede de Tecnologias Convergentes....................................................................... 3
2. Metodologia.................................................................................................................... 6
2.1. Arquitetura do processo............................................................................................. 8
3. Descrição da tecnologia................................................................................................ 10
3.1. SQL Server 2005...................................................................................................... 10
3.1.2 Plugin................................................................................................................... 11
3.1.2.1. Tratamento de excessões................................................................................ 12
3.2. J2EE......................................................................................................................... 13
3.3. STL .......................................................................................................................... 13
3.4 DLL........................................................................................................................... 14
3.5. COM ........................................................................................................................15
3.6. ATL.......................................................................................................................... 16
4. Pré-processamento........................................................................................................ 18
4.1. Remoção de caracteres indesejados......................................................................... 20
4.2. Integração da caixa .................................................................................................. 20
4.3. Tokenização............................................................................................................. 21
4.4. Remoção de termos alheios à linha portuguesa....................................................... 22
4.5. Remoção de stopwords ............................................................................................ 22
4.6. Stemming................................................................................................................. 23
4.6.1. Formato das regras do stemming........................................................................ 27
4.7. Geração da BOW..................................................................................................... 28
4.8. Armazenamento da BOW........................................................................................ 31
5. Processamento............................................................................................................... 34
5.1. Clustering.................................................................................................................34
5.1.1. Cálculo da distância inter-cluster ....................................................................... 35
5.1.1.1. Single-Link .................................................................................................... 36
5.1.1.2. Complete-Link............................................................................................... 37
5.1.1.3. Average-Link................................................................................................. 38
5.1.2. K-Means.............................................................................................................. 38
5.1.3. Métricas de distância........................................................................................... 40
5.1.3.1. Distância euclidiana....................................................................................... 41
5.1.3.2. Coseno............................................................................................................ 41
5.1.3.3. Distância de Manhattan.................................................................................. 42
5.1.3.4. Aproximação minimax................................................................................... 42
5.2. Validação do número de clusters............................................................................. 42
5.2.1. Índice PBM......................................................................................................... 43
5.3. O plugin PBM_K-Means......................................................................................... 45
6. Pós-processamento........................................................................................................ 53
vi
7. Análise de resultados .................................................................................................... 57
8. Conclusão...................................................................................................................... 61
8.1 Trabalhos futuros..................................................................................................... 61
Apêndice 1: Glossário de abreviaturas ............................................................................. 63
Apêndice 2: Comentários mais relevantes de cada cluster............................................... 65
Bibliografia....................................................................................................................... 71
vii
Índice de figuras
Figura 1. 1: As etapas do data mining................................................................................. 1
Figura 2. 1: Estágios da metodologia.................................................................................. 6
Figura 2. 2: Analise da convergência.................................................................................. 8
Figura 2. 3: Abstração das etapas da analise da convergência. .......................................... 9
Figura 3. 1: Tipos de acesso.............................................................................................. 20
Figura 3. 2: Arquitetura COM. ......................................................................................... 16
Figura 4. 1: Interface do programa de pré-processamento. .............................................. 18
Figura 4. 2: Tarefas do pré-processamento....................................................................... 19
Figura 4. 3: Fluxograma do Portuguese Stemming. ......................................................... 25
Tabela 4. 1: Exemplo ilustrativo....................................................................................... 31
Tabela 4. 2: Exemplo ilustrativo....................................................................................... 32
Tabela 4. 3: Frequencias zeradas descartadas................................................................... 33
Figura 5. 1: Clustering hierárquico nas abordagens aglomerativa e divisiva................... 36
Figura 5. 2:O funcionamento do algoritmo K-Means....................................................... 39
Figura 5. 3:Esquema de execução do algoritmo K-Means............................................... 40
Figura 5. 4: Criação do data source. ................................................................................. 45
Figura 5. 5: Criação do data source view.......................................................................... 46
Figura 5. 6: Escolha da técnica de mineração................................................................... 47
Figura 5. 7: Parâmetros do PBM_K-Means...................................................................... 48
Figura 5. 8: A estrutura de mineração criada.................................................................... 50
Figura 5. 9:Execução da estrutura com a técnica de mineração....................................... 51
Figura 5. 10: Fim da execução do algoritmo. ................................................................... 52
viii
Figura 6. 1: O programa de pós-processamento............................................................... 53
Figura 6. 2: Comentários do cluster selecionado.............................................................. 53
Figura 6. 3: A relevância dos comentários dentro de seus clusters. ................................. 54
Figura 6. 4: Matriz de distâncias inter-cluster. ................................................................. 55
Figura 6. 5: Evolução do índice PBM............................................................................... 55
Figura 7. 1: O pré-processamento em execução............................................................... 57
Figura 7. 2: Registros criados pelo pré-processamento (Database Engine)..................... 58
Figura 7. 3: Evolução do índice PBM............................................................................... 59
Tabela 1: Os três comentários mais relevantes do cluster 1 (Hidrogênio)....................... 65
Tabela 2: Os três comentários mais relevantes do cluster 2 (Biodiesel).......................... 68
ix
1. Introdução
Text mining (análise inteligente de textos, text data mining) é a tarefa de descobrir
informações novas, anteriormente desconhecidas e pontecialmente úteis de dados não-
estruturados [1].
Text mining é relacionado ao data mining, brevemente exemplificado pela figura
1.1, que se propõe a extrair padrões úteis de dados estruturados normalmente
armazenados em grandes repositórios de dados. Text mining é um campo multidisciplinar
que inclui várias tarefas como categorização, clustering, sumarização, etc. [13].
Figura 1. 1: As etapas do data mining.
Por ser um meio conveniente de armazenamento, os textos trazem agregados uma
significante quantidade de informação. De fato, algo em torno de 85% de toda a
informação encontrada nas empresas é exclusivamente armazenada em algum tipo de
dado não-estruturado [50]. Estes dados podem vir de diversas fontes tais como livros,
publicações em geral, e-mails, blogs, listas de discussão e fóruns via web, dentre muitas
outras.
O grande desafio de se trabalhar com este tipo de dado, os textos, está justamente
na falta de uma estruturação, o que impossibilita a criação de analisadores sintáticos para
obtenção das informações. Muitas vezes os textos encontram-se em formatos que
possuem estruturas e podem ser lidos com muita facilidade (XML e RSS, HTML ou
XHTML, CSV, etc.), contudo os dados (os textos em si) continuam não-estruturados, e
na maioria dos casos, sem revisão gramatical.
Por esta razão, é de grande valia um pré-processamento (tratamento ou preparação
do dado) adequado para que se garanta passar os dados da melhor forma possível aos
algoritmos de text mining propriamente ditos, que executarão a tarefa de descoberta de
conhecimento.
Ferramentas que auxiliem a interpretação dos resultados obtidos pela etapa de
processamento também são de ampla importância. A esta etapa é dado o nome de pós-
processamento. Um sistema de pós-processamento deve ser capaz de receber os
resultados da etapa anterior e possuir artifícios que capacitem o utilizador a tirar
conclusões sobre os dados.
No presente trabalho serão descritas ferramentas implementadas baseadas em uma
metodologia específica. Os requisitos técnicos também serão detalhados nas sessões
posteriores.
1.1. E-ciência
A internet é uma ferramenta essencial para o intercâmbio de informações de todos
os fins. Este intercâmbio é encorajado por diversas razões: em primeiro lugar por a web
ser uma fonte de informações tão grande que praticamente qualquer tipo de conteúdo
pode ser encontrado. Em segundo lugar, porque o acesso é relativamente barato e em
terceiro lugar, pela inexistência de uma triagem central, então qualquer pessoa pode dar a
sua contribuição de informação [39].
Esta troca de informações pode ser feita por meio da publicação em páginas web,
gerenciada por meio de aplicativos, e muitas outras maneiras regidas por protocolos de
comunicação bem definidos.
O termo e-ciência foi introduzido por John Taylor. Taylor percebeu que diversas
áreas da ciência estavam ficando cada vez mais próximas em modos de colaboração e
interdisciplinariedade [8].
A prática da ciência já foi afetada dramaticamente pela tecnologia da informação,
em especial pela internet [2]. Por esta razão, justifica-se a implementação e utilização de
sistemas capazes de auxiliar a comunicação, troca de dados e conhecimento neste
ambiente integrado.
Para explorar estas grandes quantidades de dados científicos levantados por
experimentos diversos, os cientistas necessitam do auxílio de máquinas de busca
especializadas, ferramentas de data mining e modos de visualização de dados que possam
ser usados para fazer levantar questionamentos e compreender respostas [10].
Desta maneira, a fim de atender estes requisitos, existem diversas metodologias
para a prática da e-ciência baseadas em grids computacionais e fluxos de conhecimento.
1.2. A Rede de Tecnologias Convergentes
A Rede de Tecnologias Convergentes (TECONV) é um sistema de e-ciência que
nasceu com o intuito de identificar tecnologias inerentes a pesquisa de tecnologias de
interesse da Petrobrás, mantenedora da Rede. Através de processos de text mining
(clustering) dos comentários gerados pelos participantes, busca-se estabelecer a
convergência do conhecimento dos especialistas.
Os participantes da Rede de Tecnologias Convergentes são renomados
pesquisadores de diversos centros de pesquisa do Brasil. Estes participantes interagem
entre si através da publicação de artigos científicos da sua área, dentro dos temas
estabelecidos pela Petrobrás e também comentando os artigos submetidos, gerando
discussões.
Todo o processo é feito online em um sistema web de login remoto desenvolvido
especialmente para este projeto. As figuras subsequentes ilustram as interfaces deste
sistema.
O sistema está hospedado no endereço eletrônico http://www.teconv.net
, e
requisita o uso de login e senha de acesso.
Pelo sistema web também é possível ter acesso aos comentários por artigo. Existe
também a possibilidade de acessar artigos de iterações passadas, visto que estas
permanecem armazenadas.
Deve-se ressaltar que os comentários são exportados em RSS e que todos os
dados estão armazenados no SGBD Microsoft SQL Server 2005. Esta ferramenta
disponibiliza procedimentos de mineração de dados e permite que o usuário acrescente
novas funcionalidades através da implementação de plugins [4,5].
Podem-se destacar dois casos de uso fundamentais no sistema web da TECONV,
como ilustram as descrições resumidas de caso de uso das figuras 1.2 e 1.3.
Nome
Submeter Artigo
Descrição
Submeter artigo ao sistema para que este fique à disposição dos demais participantes
Atores
Especialista
Pré-Condições
Especialista estar logado ao sistema
Figura 1. 2: Descrição resumida do caso de uso Submeter Artigo
Nome
Pontuar artigo
Descrição
Marcar um artigo como relevante ou irrelevante
Atores
Especialista
Pré-Condições
Especialista estar logado ao sistema.
Figura 1. 3: Descrição resumida do caso de uso Pontuar Artigo.
O foco do presente trabalho está nestes comentários uma vez que é neles que a
convergência será analisada através do text mining destes textos.
O objetivo da presente dissertação foi efetuar a implementação de ferramentas de
text mining no portal TECONV para disponibilizar as facilidades de análise da
convergência no próprio ambiente de banco de dados, onde os comentários estão
armazenados.
Este trabalho está organizado da seguinte maneira:
No capítulo 2 serão descritas cada uma das etapas da metodologia aplicada na
Rede de Tecnologias Convergentes.
O capítulo 3 dissertará sobre a tecnologia adotada a nível de software,
especificações técnicas em geral, e algumas particularidades relevantes ao
desenvolvimento.
O capítulo 4 descreve o pré-processamento dos dados, passando detalhadamente
por cada etapa e ilustrando os algoritmos mais importantes implementados neste estágio.
No capítulo 5 o processamento e os métodos implementados serão descritos e os
procedimentos algoritmicos inerentes serão detalhados.
O capítulo 6 se refere ao pós-processamento, ilustrando com figuras as interfaces
mais importantes do programa de pós-processamento e o seu funcionamento.
No capítulo 7 são apresentados os resultados sob uma massa de dados
representativa e a análise dos clusters propriamente ditos será apresentada. Para tanto,
toda a parametrização utilizada será descrita e informações técnicas relevantes como o
tempo de execução dos programas serão mostrados.
No capítulo 8, é feita uma reflexão geral sobre os demais capítulos e a conclusão
deste trabalho.
Finalmente, no capítulo 9, serão apresentadas e sugestões de outras aplicações em
potencial onde o sistema desenvolvido e a metodologia utilizada poderiam ser aplicados.
Existem apêndices posteriores que explicam as abreviaturas amplamente
utilizadas durante o texto e tabelas referentes ao resultado citadas no capítulo 7. A
referência bibliográfica encontra-se ao final.
2. Metodologia
A metodologia adotada para o funcionamento da rede é composta de cinco
estágios, como ilustra a figura 2.1.
Figura 2. 1: Estágios da metodologia.
Como a figura 2.1 sugere, o processo é cíclico. Semanalmente cada um dos
estágios é executado para que um novo ciclo tenha início. Os ítens subsequentes
descrevem cada estágio da metologia:
• Priorização de temas: Os analistas da Petrobrás indicam temas de interesse
da companhia através do portal da rede. Este é o ponto de partida de uma nova
iteração.
• Prospecção de artigos científicos: os pesquisadores participantes da Rede
submetem ao portal artigos científicos (preferencialmente de terceiros) inerentes
ao tema estabelecido no ítem anterior, dentro da sua área específica de
conhecimento. Os pesquisadores também fazem uma votação em cada artigo,
indicando se, na sua opinião, ele é relevante ou não ao tema estabelecido. Se o
assunto do artigo fugir da área de conhecimento do votante ao ponto deste prefirir
abster-se de votar, o participante possui a opção de abstenção do voto, que por sua
vez, não é interpretado pelo sistema como simplesmente não votar.
• Identificação de oportunidades: esta etapa consiste na identificação dos
artigos mais interessantes do ponto de vista do comitê científico. Alguns dos
artigos mais votados como relevantes na etapa passada serão selecionados por
este comitê para as etapas posteriores. Os artigos que eventualmente não forem
selecionados permanecerão no sistema e poderão ser consultados livremente.
• Fusão de fluxos de conhecimento: nesta etapa são submetidos comentários
sobre os artigos de maior relevância. Desta forma, os participantes poderão
interagir entre si dando informações e opiniões, gerando debates e oferecendo
soluções inovadoras inerentes ao assunto do artigo comentado.
Os comentários deverão ser escritos em português, de forma clara e objetiva, o
que facilitará a etapa seguinte. Quaisquer comentários podem também,
opcionalmente, serem votados como relevantes ou não relevantes por qualquer
um dos participantes.
• Análise da convergência: o intuito da etapa de análise da convergência é
encontrar clusters dentro do corpo de comentários utilizando as técnicas de text
mining, sendo que estes comentários não se reportam necessariamente a um
mesmo artigo, mas sim a um tema comum. Estes resultados são analisados pelo
comitê científico da Petrobrás que poderá requerir um novo processamento ou
refino dos comentários. Uma vez o comitê satisfeito com os resultados da iteração
vigente, estes serão publicados no sistema web da Rede de Tecnologias
Convergentes e novos temas serão sugeridos para que tenha início um novo ciclo,
como indicado na figura 2.2.
Figura 2. 2: Analise da convergência.
Nota-se pela figura 2.2 que todos os comentários de todos os assuntos são levados
à etapa de análise da convergência.
2.1. Arquitetura do processo
A análise da convergência propriamente dita requer etapas de pré-processamento,
processamento e pós-processamento. Estas etapas são de cunho técnico e podem
funcionar como caixa-preta para a análise da convergência (análise dos clusters).
Contudo, o entendimento algoritmico do processo é de grande valia para uma boa análise.
Os capítulos posteriores explicarão cada uma das etapas e suas sub-etapas. De uma
maneira mais abstrata, todo o procedimento ocorre como na figura 2.3.
Artigos
Submetidos
Comentários
Comentários
Comentários
Análise
da
Convergência
Tema Priorizado
Figura 2. 3: Abstração das etapas da analise da convergência.
O processo como um todo pode ser representado pelos algoritmos e tarefas mais
importantes. Na etapa de pré-processamento serão utilizadas técnicas de redução da
dimensionalidade, como a retirada de stopwords e stemming.
Na etapa de processamento o clustering será executado pelo algoritmo K-Means,
auxiliado pelo índice PBM. Finalmente, na etapa de pós-processamento, os resultados
poderão ser visualizados e analisados.
Cada etapa e seus métodos são explicados detalhadamente nos itens subseqüentes.
Pré-processamento Análise da convergência
SQL Server
2005
Plugin
Stopwords
Stemming
BOW
PBM
K-Means
Visualização
Avaliação
3. Descrição da tecnologia
Nesta sessão são descritos os requisitos de software utilizados para a
implementação dos sistemas de pré-processamento, processamento e pós-processamento.
A sua utilização e escolha são justificados e a arquitetura de funcionamento mais
relevantes das ferramentas são descritas. O detalhamento algorítmico de cada passo é
apresentado nas sessões posteriores.
3.1. SQL Server 2005
Foi interessante ao projeto que o ambiente do banco de dados fosse integrado à
tarefa de mineração de textos. Assim sendo, com a indicação dos especialistas
interessados, foi utilizada a ferramenta SQL Server 2005, da Microsoft, que é um robusto
ambiente de banco de dados bastante utilizado comercialmente.
A ferramenta SQL Server 2005 acompanha diversas funcionalidades que auxiliam
a análise de dados. O acesso no ambiente é baseado em COM, utilizando
ADO/ADO.NET, inclusive com suporte OLE DB para cubos. Também é possível o
acesso da máquina de banco de dados via ODBC.
A figura 3.1 ilustra os tipos de acesso de diversos aplicativos hipotéticos ao
SGBD.
Apesar da ferramenta acompanhar um algoritmo integrado com suporte DMX
para o clustering de dados [3] (Microsoft Clustering), este algoritmo não leva em conta a
estimativa do número de clusters e a visualização do clustering para textos é inadequada.
E como será explicado posteriormente, há limitações técnicas comuns a qualquer banco
de dados relacional que farão com que os dados necessitem de reshape para que os
cálculos sejam efetuados de forma adequada, impossibilitando o input dos dados no
Microsoft Clustering.
Figura 3. 1: Tipos de acesso.
Contudo a ferramenta SQL Server desde a versão 2000 possibilita a integração de
algoritmos implementando interfaces COM [5] para serem executados dentro do seu
ambiente. Isso foi uma grande motivação para a utilização deste ambiente, porque desta
forma foi possível desenvolver um plugin [4] (funcionalidade específica da versão 2005)
específico para os interesses da rede integrado ao banco de dados, ficando assim o
processamento encapsulado.
3.1.2 Plugin
Para a implementação do plugin foi utilizado um sample distribuido gratuitamente
pela Microsoft que acompanha os tutoriais de costumização. O sample implementa todo o
shell do plugin, que trata da comunicação das interfaces COM necessárias para a
integração com o SQL Server 2005.
A adequação deste shell ao problema de clustering e, mais especificamente à
implementação dos algoritmos adequados para esta tarefa, e também o reader necessário
para ler cada caso foram implementados em linguagem C++. As interfaces
Aplicativo Aplicativo
ADO
ADO.NET
OLE DB
Cubo
Aplicativo
Tabelas
relacionais
Aplicativo
ODBC
Aplicativo
JDBC
OLE DB 2
OLE DB 1
implementadas também tiveram que ser adequadas a um problema de clustering, visto
que há interfaces COM específicas no SQL Server 2005 para cada tipo de tarefa de
mineração.
A Microsoft distribui samples tanto em C++ quanto em C#. Para a implementação
do presente trabalho, foi utilizada a linguagem C++.
3.1.2.1. Tratamento de excessões
O tratamento de excessões dentro do plugin deve ser feito de forma adequada,
visto que erros tratados de forma incorreta ou simplesmente não tratados, não gerarão
mensagens de erro amigáveis quando o algoritmo eventualmente divergir ao ser
executado no SQL Server 2005. O não entendimento deste tipo de erro poderá
comprometer o debug do plugin.
O tratamento de excessões na arquitetura COM e nos containers STL baseiam-se
em alguns macros e tipos específicos. Dentre os quais podem-se destacar:
• CHECK_STL_MEM: Deve ser chamado sempre que um vetor dinâmico é
instanciado. Serve para verificar se o espaço em memória requisitado foi alocado
corretamente.
• HRESULT: A maioria dos métodos do shell retornam um HRESULT (inteiro
de 32 bits com sinal), utilizado para informar o estado em que o método terminou
(sucesso, warnings, erros, etc). Na realidade, quase todos os métodos e interfaces
de componentes COM retornam este tipo [11]. O tipo HRESULT pode assumir
diversos valores: S_OK, S_FALSE, E_UNEXPECTED, E_ERROR, etc.
Macros para tratamento de HRESULTs: diversos macros tratam e identificam
a fatalidade ou não expressa por um HRESULT. Dentre eles estão: RETURN_ON_FAIL,
SUCCEEDED, HRESULT_FROM_WIN32, etc.
3.2. J2EE
Também foi necessário criar um aplicativo para pré-processar os dados. Para tanto
foi escolhida a distribuição J2EE [6]. Esta distribuição, além de gratuita, conta com a
própria JVM pois inclui também a distribuição JRE, além da J2SDK e todas as
funcionalidades do J2SE [6].
O uso de Java se justifica para a criação destes aplicativos pela facilidade de
implementação de interface gráfica. Também é justificável pela portabilidade dos
componentes e facilidade de implementação dos padrões de projeto e outras boas práticas
de desenvolvimento. A linguagem possui características que organizam o fonte, fazendo
da tarefa de manutenção mais simplificada.
O IDE Eclipse [14] foi utilizado no desenvolvimento por ser uma ferramenta leve,
porém robusta, e com a capacidade de integração de pacotes automaticamente, pacotes
estes que foram amplamente utilizados no desenvolvimento dos programas de pré-
processamento e pós-processamento. A ferramenta eclipse é gratuita.
3.3. STL
A linguagem C++ possui apenas três estruturas de dados built-in:
• Arrays: estruturas n-dimensionais de tamanho fixo cujo acesso é feito pelo
índice ou por ponteiros.
• Classes e structs: estruturas de registros cujos campos são acessados pelo
nome.
A STL é uma biblioteca, definida no ANSI C++, que se utiliza do conceito de
templates do C++ para criar estruturas de dados de usos diversos. A biblioteca define
containers e iterators para facilitar o acesso aos containers.
O uso da STL justifica-se pela sua ampla utilização em aplicativos C++ [37, 40]
e pela facilidade de utilização das estruturas de dados da biblioteca: strings (diferentes
das C-strings (char*) de tamanho fixo), árvores balanceadas, vetores dinâmicos, listas,
etc.
Grande parte dos ambientes mais conhecidos acompanham a biblioteca STL,
como o Microsoft Visual C++, Borland C++ Builder, etc [37]. A biblioteca também
pode ser carregada à parte na maioria dos ambientes C++.
3.4 DLL
Existem diversas maneiras de se exportar uma funcionalidade para que ela seja
utilizada sozinha ou em conjunto com outros programas. Uma forma bastante usual é a
linkagem estática.
A linkagem estática é muito simples: exportando a funcionalidade como sendo
uma biblioteca tradicional, o programa principal que utiliza esta funcionalidade fará
chamadas estáticas à biblioteca e terá acesso às suas rotinas e atributos [12].
Contudo, a linkagem estática possui suas desvantagens [12]:
• Redundância: caso diversos programas utilizem a biblioteca, cada programa
terá a sua própria cópia, o que resultará em desperdício de recursos.
• Alto acoplamento: caso uma nova versão da biblioteca seja disponibilizada,
seja para a inclusão de novas funcionalidades ou para correção de erros, o
programa principal que a utiliza estaticamente terá de ser reconstruido com a nova
versão da biblioteca. Esta dificuldade na manutenibilidade pode transformar-se
em um sério problema no caso de sistemas de grande porte e uma dificuldade se a
reconstrução se der a cargo do usuário.
Entretanto, existe também a possibilidade de se utilizar as bibliotecas de linkagem
dinâmica, ou DLLs.
Ao contrário da linkagem estática, a DLL é uma biblioteca que pode ser
compartilhada por diversos aplicativos. Para isso basta que a DLL esteja devidamente
registrada no sistema, que será o intermediador da chamada entre o aplicativo e a DLL
em si.
DLLs são pedaços de fonte executáveis que aguardam uma chamada. Quando um
cliente requisita a funcionalidade de uma DLL, ele pode carregá-la e ter acesso às suas
rotinas em tempo de execução [12]. Isso é feito facilmente através das interfaces que cada
DLL implementa e disponibiliza publicamente. Uma DLL é capaz de receber valores
dinamicamente, processar arquivos, etc.
Este não é um conceito novo: o Windows, por exemplo, já o utiliza desde suas
primeiras versões. Existem, claro, diversos formatos para outros sistemas operacionais
que também desempenham o papel de linkagem dinâmica.
3.5. COM
COM é uma arquitetura de software desenvolvida pela Microsoft para a
comunicação e interoperabilidade de aplicativos. Ela é a arquitetura por trás de serviços
de mais alto nível, como o OLE. A comunicação COM se dá através da implementação e
requisições a interfaces.
Cada componente COM possui dados privados que não podem ser acessados por
outros componentes, e também interfaces públicas com ponteiros para VLTBs acessíveis.
Cada VLTB é composta de ponteiros para as rotinas implementadas naquela interface.
Em COM, todas as interfaces têm como base a interface IUnknown (todas herdam de
IUnknown) [
7] e um componente pode implementar mais de uma interface. A figura 3.2
exemplifica:
Figura 3. 2: Arquitetura COM.
Aplicativo
Componente
COM
Interface
(Ponteiro para VLTB)
Área Privada
VLTB
Ponteiro para Função 1
Ponteiro para Função 2
Ponteiro para Função 3
…
void funcao2(arg1,arg2…)
Tipicamente, os componentes COM são exportados para DLLs, e dependendo do
ambiente de desenvolvimento, a atualização do arquivo contruido (a DLL em si) bem
como suas informações de registro ficam sob responsabilidade do próprio ambiente,
facilitando em muito o trabalho, criando e excluindo automaticamente arquivos
temporários e gerenciando quaisquer bibliotecas utilizadas.
3.6. ATL
ATL é uma biblioteca C++ criada pela Microsoft cuja proposta é a rápida
implementação de componentes COM. A biblioteca possui classes e macros que
encapsulam grande parte da implementação dos componentes, fazendo desta tarefa mais
simples e rápida.
A cada nova interface criada, não é necessário simplesmente a implementação
dos métodos específicos desta nova interface, mas também da interface IUnknown e de
seus métodos. Além, é claro, de outras interfaces pré-definidas que o componente pode
vir a utilizar. Com o uso de ATL estas tarefas tornam-se menos onerosas, visto que
grande parte do trabalho é feita automaticamente pelo ambiente, deixando o
desenvolvedor focado apenas no problema específico da aplicação que está construindo.
A biblioteca possui classes pré-fabricadas de usos diversos como smart pointers,
conversores de tipos, e também componentes que encapsulam estruturas de dados como
árvores, arrays, etc.
4. Pré-processamento
A etapa de pré-processamento consiste em um tratamento e armazenamento
adequado dos dados. Esta etapa se caracteriza pela identificação dos termos dentro da
coleção de documentos e também pela determinação da sua importância dentro do todo,
para que só então tenha início a etapa de processamento deste dado.
A figura 4.1 mostra a tela principal do programa de pré-processamento
desenvolvido.
Figura 4. 1: Interface do programa de pré-processamento.
Como sugere a figura 4.1, o programa requer toda uma parametrização para que o
pré-processamento seja executado com sucesso, desde parâmetros da connectionstring
(parâmetros de acesso ao banco de dados) até parâmetros específicos de um problema de
pré-processamento de textos como descartar radicais pequenos demais, ignorar palavras
com letras fora do alfabeto, o tipo de ponderação para a geração da BOW, etc. Os ítens
subsequentes explicam com detalhes cada uma das tarefas do pré-processamento.
Esta etapa de pré-processamento é muito custosa e requer a implementação de
diversas tarefas a nível de documento e termo. Muitas vezes faz-se necessário executar
esta etapa várias vezes, à medida que comportamentos indesejados são identificados e
necessitam ser corrigidos.
Desta forma, as listas utilizadas nesta etapa terão de ser atualizadas cada vez que
algo indesejado ocorra a fim de que o pré-processamento seja refinado e preparado para
tratar estes casos. Isto pode se caracterizar pela identificação de alguma nova stopword
ou nome próprio, understemmings ou overstemmings, trechos com erros de digitação,
substrings específicas de outro idioma, etc.
Visto que com isso todo o esquema do cálculo das frequencias dos demais termos
fica inconsistente, os mesmos acabam necessitando de recálculo, ou seja: todo o processo
terá que ser realizado novamente. Com o passar do tempo e a constante atualização das
listas, o processo vai tornando-se cada vez menos dispendioso, uma vez que, dentro do
contexto específico dos textos submetidos ao pré-processamento, grande parte dos casos
vai sendo prevista.
As tarefas de pré-processamento são ilustradas na figura 4.2, enumeradas e
descritas nos ítens subsequentes:
Figura 4. 2: Tarefas do pré-processamento.
4.1. Remoção de caracteres indesejados
Em um texto existem sinais de pontuação que são indesejados dentro de uma
análise. Podem também existir palavras com símbolos desconhecidos por erros de
digitação, ou simplesmente caracteres esparsos sem significado semântico. É comum
ainda a existência de caracteres matemáticos (“%”, “+”, “<”, etc), monetários (“$”, “
€”,
etc), números, caracteres de formatação (retorno de carro, newlines, caracter de
tabulação, etc), entre outros que devem ser extirpados do texto.
Para executar esta tarefa, é necessário identificar os caracteres que se deseja
excluir do texto, ou o contrário: identificar os que não devem ser excluídos e remover os
demais. Isso é feito com o auxílio de uma lista em disco, ou acoplada no próprio fonte do
método responsável.
Um exemplo pode ser mostrado na sentença abaixo:
“Não creio que seja nada grave, mas o senhor deverá fazer um exame mais
detalhado – disse o médico.”
Remoção de caracteres
indesejados
Integração da caixa
Tokenização
Remoção de stopwords
Stemming
Geração da BOW
Armazenamento da BOW
Remoção de
termos alheios à
língua portuguesa
O trecho acima contém caracteres que representam sinais de pontuação (“,” “-”
“.”) e também o caracter de tabulação, utilizado para formatar o texto. Assim sendo, estes
caracteres deverão ser removidos para que tenha início a próxima etapa. Depois da
remoção de caracteres indesejados, o texto ficará da seguinte forma:
“Não creio que seja nada grave mas o senhor deverá fazer um exame mais
detalhado disse o médico”
4.2. Integração da caixa
É necessário integrar todos os caracteres restantes da etapa anterior dentro de uma
mesma caixa para utilização posterior: letras maiúsculas ou letras minúsculas. No sistema
desenvolvido, os textos foram todos passados para caixa baixa. As sentenças seguintes
exemplificam:
“Princesa Isabel assinou a Lei Áurea”
A frase acima contém caracteres em caixa alta. Depois da etapa de integração da
caixa, a sentença ficará como abaixo:
“princesa isabel assinou a lei aurea”
Diversas linguagens de programação acompanham em suas bibliotecas padrão
mecanismos automáticos para a integração da caixa (método toLowerCase() da classe
String em Java, rotina LowerCase em Delphi, etc). Caso contrário, é possível alterar
facilmente a caixa fazendo simples cálculos utilizando o código ASCII de cada caracter.
4.3. Tokenização
A tarefa de tokenização consiste na identificação dos termos dentro do texto. Isso
é feito utilizando o espaço (“ ”), que é o único caracter fora do alfabeto restante da etapa
de remoção de caracteres indesejados, e que por natureza é um caracter separador de
palavras.
Cada grupo de caracteres entre espaços é denominado token, que é o termo em si.
O texto, que é visto como uma sequencia de caracteres, será transformado em uma
coleção de tokens, como mostra o exemplo abaixo:
“o menino brincava com a bola quando começou a chuva”
Utilizando os espaços como separadores, os tokens (termos) da sentença acima
serão os seguintes:
“o”, “menino”, “brincava”, “com”, “a”, “bola”, “quando”, “começou”, “a” e
“chuva”.
Esta tarefa é muito importante uma vez que todas as etapas posteriores a este
ponto utilizarão os textos em um granulosidade nova: o termo. Muitas linguagens de
programação já acompanham bibliotecas e classes que auxiliam nesta etapa (biblioteca
strtok.h em C, classe StringTokenizer em Java, etc). Caso contrário, também é simples
determinar os tokens pela posição dos caracteres espaço, tratando o texto como um vetor
de caracteres.
4.4. Remoção de termos alheios à linha portuguesa
Muitos termos possuem substrings que são tipicamente estrangeiros, ou ainda
infrigem as regras gramaticais do português visto que as regras de construção das
palavras variam de idioma para idioma.
Existem termos ainda que contém caracteres fora do nosso alfabeto. Estes
caracteres não poderiam ter sido retirados na etapa de remoção de caracteres indesejados,
visto que a sua eliminação ou substituição por espaços ou caracter branco criaria palavras
sem significado.
Desta forma, tokens que contivessem certas expressões regulares foram
eliminados, como “*w*”, “*y*”, “*k*”, “*ff*”, “*bb*”, etc.
Esta etapa reduz a dimensionalidade do problema.
4.5. Remoção de stopwords
As stopwords são palavras que não possuem ou possuem muito pouca
importância semântica. São exemplos de stopwords os artigos, interjeições, conjunções,
pronomes de tratamento comuns, verbos auxiliares, nomes próprios, etc. As stopwords
também podem ser associadas a um contexto específico.
A remoção das stopwords é feita com o auxílio de uma lista, tipicamente em
disco, denominada stoplist [45]. A stoplist e o analisador sintático que a lê necessitam de
escalabilidade, uma vez que a lista deverá crescer à medida que mais stopwords forem
identificadas. Em um contexto especificamente científico, como o caso da presente
aplicação, palavras como, por exemplo, “experimento”, “resultado”, “exemplo” e outras
foram acrescentadas na stoplist.
Os termos dos textos são comparados um a um com as stopwords, e os que forem
identificados como stopwords serão descartados. O pseudo-código a seguir exemplifica o
processo:
Documentos ← OBTER_DOCUMENTOS;
Stopwords ← LER_STOPLIST;
PARA_CADA Documento EM Documentos
Termos ← OBTER_TERMOS;
PARA_CADA Termo EM Termos
PARA_CADA Stopword EM Stopwords
SE Termo = Stopword
DESCARTAR(Termo);
FIM_SE
FIM_PARA_CADA
FIM_PARA_CADA
FIM_PARA_CADA
Além de eliminar palavras que em nada auxiliarão em análise futura, a etapa de
remoção de stopwords reduz a dimensionalidade da massa, visto que menos palavras
(variáveis) sobrarão ao término desta etapa.
4.6. Stemming
A tarefa de stemming consiste em reduzir um termo ao seu radical. Este processo
é de suma importância para que nas etapas posteriores termos com o mesmo radical
sejam processados em conjunto, visto que na mineração de textos diversas palavras cujo
radical é o mesmo podem ser consideradas como equivalentes. O processo de stemming
também reduz drasticamente o número de variáveis da massa de dados.
O processo de stemming consiste da eliminação de sufixos que identificam
plurais, gênero ou formas verbais transformando termos equivalentes em uma única
Representação [36]. Desta forma, palavras como “petroleiro”, “petrolífero” e “petróleo”,
por exemplo, serão todas reduzidas ao radical “petro” e a sua frequencia será calculada
baseada no radical, e não no termo original.
O processo de stemming se utiliza de uma lista de sufixos que deverão ser
removidos ou substituídos dependendo do caso, bem como uma lista de excessões. As
excessões são muito importantes visto que existem diversas palavras que fogem às regras
de remoção de sufixos.
Por se tratar de um processo linguístico, a fase de stemming pode aprensentar
falhas, uma vez que é muito difícil englobar todas as excessões de um idioma em uma
lista. Bem como também é muito difícil estabelecer regras para remoção de sufixos que
contemplem todas as palavras de uma língua. Há ainda a possibilidade de existirem
palavras digitadas erroneamente e isto acarretará em um radical incorreto. Por estas
razões existem duas falhas comuns na etapa de stemming:
• Understemming: ocorre quando uma palavra foi reduzida insuficientemente e
o resultado não expressa o radical correto da palavra. Ex: “facilitador” foi
reduzido ao radical “facilit”, quando o correto seria o radical “facil”.
• Overstemming: ocorre quando uma termo foi reduzido mais que o necessário
e o resultado não expressa o radical correto da palavra. Ex: a palavra “gramática”
foi reduzida ao radical “grama”. O radical correto seria “gramat”.
Verifica-se o radical ao final da etapa de stemming para corrigir understemmings e
overstemmings. Isto é feito com o auxílio de uma lista que indica o radical correto caso a
palavra tenha sido reduzida a um radical incorreto contido na lista.
O algoritmo de Porter [17] é amplamente utilizado para textos na língua inglesa.
Ele consiste na remoção e re-escrita de sufixos utilizando algo em torno de 60 regras e
executa todo o processo em dois passos.
Visto que as regras de formação das palavras, bem como sua lógica e ordem
dentro do texto variam de idioma para idioma, existem metodologias de stemming
variados e bastante específicos para diversos idiomas, como [34], que é específico para o
espanhol. Existem também abordagens para a língua persa [35].
O algoritmo implementado foi o Portuguese Stemming [9], que dos algoritmos de
stemming é um dos mais utilizados para a língua portuguesa. Originalmente este
algoritmo foi desenvolvido em linguagem C, mas o presente trabalho apresenta uma
implementação em Java para adequá-lo à tecnologia descrita nos ítens supracitados.
Portuguese Stemming é composto de um total de oito passos, que serão
executados ou não dependendo do termo. Isto ocorre porque o termo fluirá por diferentes
caminhos dentro do algoritmo de acordo com a sua natureza gramatical. O Portuguese
Stemming consiste na remoção e re-escrita de termos baseado em sufixos pré-
estabelecidos. O fluxograma da figura 4.3 ilustra o algoritmo e os ítens subsequentes
explicam o funcionamento de cada processo.
Figura 4. 3: Fluxograma do Portuguese Stemming.
• Redução de plural: Caso o termo termine em “s”, o processo irá retirar este
sufixo, a menos que o termo submetido encontre-se na lista de excessões.
• Redução de feminino: Nesta etapa o termo, caso esteja no feminino, irá ser
transformado no seu correspondente no masculino, a não ser que ele se encontre
na lista de excessões.
• Redução de aumentativos e diminutivos: Caso o termo termine com sufixos
que indiquem aumentativos ou diminutivos (ex: “casinha”, “homenzarrão”, etc.),
este será reduzido.
• Redução de advérbios: O termo será reduzido caso ele termine com “mente”,
que é um sufixo típico de advérbios, caso ele não se encontre na lista de
excessões.
• Redução de substantivos: Nesta etapa os substantivos e adjetivos são
reduzidos ao seu radical.
• Redução de verbos: Este é o processo mais custoso da etapa de stemming,
por ser a etapa com o maior número de regras e excessões. Nesta etapa os verbos
são reduzidos aos seus radicais.
• Redução da última vogal: Caso o termo tenha passado pelo processo de
redução de verbos e termine com as vogais “a”, “e” ou “o”, esta última vogal
deverá ser extirpada do termo.
• Remoção de acentos: Etapa final e comum a todos os termos. Este processo
irá retirar tanto a acentuação (acentos agudos, circunflexos e crases) quanto os
sinais gráficos (tils, tremas, etc.) restantes.
Um outro problema que ocorre é quando o radical é pequeno demais para ser
utilizado em uma análise. Isso ocorre tipicamente com termos pequenos, que ao passarem
pela etapa de stemming, tornam-se menores ainda. Se, ao final da etapa de stemming, o
radical for menor do que um limite previamente estabelecido, este será desconsiderado
para as etapas posteriores.
4.6.1. Formato das regras do stemming
Cada uma das oito etapas do Portuguese Stemming possui regras para a remoção
do sufixo e excessões a estas regras. Desta forma, foram criados arquivos referentes a
cada processo da etapa de stemming. Cada um destes arquivos obedece a um formato
comum que é lido por um analisador sintático, que constrói as estruturas internas para
cada redução. O exemplo abaixo mostra uma linha do arquivo que contém as regras de
remoção de sufixo e excessões para o processo de redução de feminino:
“esa,ês,mesa,obesa,princesa,turquesa,ilesa,pesa,presa”
Esta linha é entendida pelo analisador sintático como “encontrar o sufixo “esa” e
substitui-lo por “ês”, a menos que o termo seja “mesa”, “obesa”, “princesa”, “turquesa”,
“ilesa”, “pesa” ou “pressa””. Desta forma, por exemplo, a palavra “inglesa” será reduzida
a “inglês”.
Também existem regras que não substituem o sufixo, mas simplesmente o
removem do radical, bem como regras que não possuem excessões. Assim sendo, as
linhas dos arquivos de regras e excessões também podem ser da seguinte forma:
“ador,”
E esta linha é entendida como “encontrar o sufixo “ador” e removê-lo, já que não
há excessões”. Assim sendo, por exemplo, o termo “escavador” será reduzido ao radical
“escav”.
Como as regras e excessões encontram-se em arquivos texto, elas podem ser
editadas e adicionadas livremente, fazendo com que o stemming fique escalável e em
constante aperfeiçoamento.
4.7. Geração da BOW
A BOW (Bag of Words) é uma estrutura organizada em forma de tabela que
mostra o peso de cada termo dentro de cada documento. Para isso, a BOW é gerada
utilizando alguma métrica de ponderação, usada para medir a relevância do termo em um
documento específico [46]. Os pesos dos termos dos documentos são atribuídos de várias
maneiras, onde os mais comuns deles são: binária, TF e TFxIDF [26].
Os ítens subsequentes detalham as ponderações implementadas no sistema de pré-
processamento.
• Linear: a ponderação linear é uma ponderação bastante simples. Ela consiste
na contagem de determinado termo no documento atual. Consideremos os radicais
abaixo:
Documento 1: “banan” “banan” “morang” “abacat”
Documento 2: “banan” “cerej” “cerej” “cerej”
Utilizando a ponderação linear, cada radical será contado dentro do documento
em questão. A BOW deverá ficar da seguinte forma:
banan morang abacat cerej
Documento 1 2 1 1 0
Documento 2 1 0 0 3
Esta ponderação é inadequada porque mostra uma importância do termo dentro do
documento e somente dele, sem levar em conta os demais documentos. E como
não há nenhum tipo de normalização, os valores da BOW podem ficar grandes
demais.
• Binária: a ponderação binária também é uma ponderação muito simples. Esta
ponderação apenas nos dá a noção de existência ou inexistência do termo no
documento dado, como no exemplo abaixo:
Documento 1: “banan” “banan” “morang” “abacat”
Documento 2: “banan” “cerej” “cerej” “cerej”
Assumindo o valor 1 para a existência e 0 para a inexistência do termo no
documento, a BOW ficaria como abaixo:
banan morang abacat cerej
Documento 1 1 1 1 0
Documento 2 1 0 0 1
• TF: a ponderação TF (Term Frequency) é uma frequencia normalizada pelo
total de termos no documento, como mostra (4.1):
∑
=
k
k
i
i
n
n
tf
(4.1)
Onde o numerador é o número de ocorrências do termo i e o denominador é o
número de ocorrência de todos os termos no documento k.
Desta forma, utilizando os dois documentos dos ítens anteriores como exemplo, a
BOW ficaria da seguinte forma:
banan
morang abacat cerej
Documento 1 0.5 0.25 0.25 0
Documento 2 0.25 0 0 0.75
Na realidade ela é uma ponderação linear, mas normalizada pelo número de
termos no documento.
• TFxIDF: das principais ponderações de termos, uma amplamente utilizada é a
ponderação TFxIDF (Term Frequency x Inverse Document Frequency). Esta
ponderação dá uma noção da importância do termo dentro do documento onde ele
aparece levando em conta a sua existência em outros documentos. O cálculo do
IDF dá-se por (4.2):
}td:d{
D
logidf
i
i
∋
=
(4.2)
Onde o numerador é o número total de documentos na massa de dados e o
denominador representa o número de documentos onde o termo i aparece. Nota-se
logo que caso um termo apareça em todos os documentos, este termo ficará com
IDF igual a zero, o que acarretará também em um TFxIDF igual a zero, visto que
a ponderação é dada pela multiplicação dos dois termos, assim como (4.3). Este
comportamento pode ser interpretado como se um termo aparece em todos os
documentos que estão sendo analisados, ele não é importante (a sua ponderação é
igual a zero). Nota-se também que se um termo aparece em vários, porém não em
todos os documentos, o seu IDF será reduzido, ao passo que caso o termo esteja
contido em poucos documentos, o IDF será alto [47]. Isso favorece termos
inesperado e desencoraja termos mais comuns, sempre levando também o TF em
consideração (4.3):
idftfidftf
⋅
=
×
(4.3)
Mais uma vez utilizando como exemplo os documentos hipotéticos dos ítens
anteriores, a BOW ficará da seguinte maneira:
banan
morang abacat cerej
Documento 1 0 0.075257 0.075257 0
Documento 2 0 0 0 0.225772
Mesmo aplicando as técnicas que reduzem a dimensionalidade como a redução de
stopwords e stemming, para documentos extensos a BOW fica com proporções muito
grandes, e ainda com muitos zeros, que representam a inexistência de termos no
documento considerado. Por esta razão, um armazenamento adequado se justifica para a
melhor utilização dos recursos.
4.8. Armazenamento da BOW
Como citado no final do ítem anterior, a BOW tende a ficar muito grande quando
a coleção de documentos é extensa, ou seja: quando existem muitos termos.
Há uma limitação técnica no número de colunas de qualquer banco de dados
relacional. No caso do SQL Server 2005, por exemplo, o máximo de colunas por tabela é
1024 tanto na versão 32 bits quanto na versão 64 bits.
Desta forma, problemas multivariados, em especial a mineração de textos, cujo
número de variáveis (termos) em geral é muito grande, necessitam de uma atenção
especial no que se refere ao armazenamento e criação de colunas.
Como a limitação na criação do número de registros é física, a escalabilidade
baseando-se no aumento do número de registro faz-se uma boa solução. Considerando a
BOW da tabela 4.1, onde a
ij
f
representa a frequencia do radical j no documento i:
Radical 1 Radical 2 Radical 3 Radical 4 Radical 5 Radical 6
Documento 1
11
f
12
f
0 0 0
16
f
Documento 2 0
22
f
23
f
24
f
0 0
Documento 3 0 0 0 0
35
f
0
Tabela 4. 1: Exemplo ilustrativo.
A tabela será transformada em uma nova tabela, contendo uma identificação do
documento, uma identificação do radical e por fim, a frequencia, como ilustra a tabela
4.2.
Nesta estrutura, não importa mais a quantidade de termos (variáveis) da massa de
dados, visto que eles serão armazenados e o número de colunas da tabela permanecerá
igual a três. Mais registros serão inseridos de acordo com as necessidades do problema.
Na etapa de processamento será necessário que mais uma vez os dados retornem ao
formato original, onde cada documento será representado como um vetor. Por isso,
dentro do algoritmo será feita uma transposição dos dados, e para isso é que os índices
estão sendo armazenados.
Tabela 4. 2: Exemplo ilustrativo.
Contudo, também se faz útil uma atenção especial quanto ao número de registros.
Por mais que o número de registros por tabela varie de acordo com a porção livre em
disco disponível para alocação das páginas, é indesejável armazenar informações
desnecessárias tanto pela questão de poupar espaço em disco (8KB por página incluindo
os 96B de cabeçalho), quanto pela performance de retorno do comando SQL, que
decresce com o aumento desgovernado do número de registros.
Assim sendo, é injustificável o armazenamento dos valores zerados encontrados
dentro da BOW, que em geral, são maioria. Como na etapa de processamento serão
executados cálculos vetoriais para determinar a similaridade (ou a distância) entre os
documentos, e para tanto os zeros serão necessários para igualar o tamanho dos vetores,
estes serão reconstruidos em tempo de execução do algoritmo.
Desta maneira, na realidade apenas as frequencias não zeradas da tabela 4.2 são
armazenadas, tendo como resultado lógico a tabela 4.3:
ID_DOC ID_RADICAL FREQUENCIA
Registro 01 1 1
11
f
Registro 02 1 2
12
f
Registro 03 1 3 0
Registro 04 1 4 0
Registro 05 1 5 0
Registro 06 1 6
16
f
Registro 07 2 1 0
Registro 08 2 2
22
f
Registro 09 2 3
23
f
Registro 10 2 4
24
f
Registro 11 2 5 0
Registro 12 2 6 0
Registro 13 3 1 0
Registro 14 3 2 0
Registro 15 3 3 0
Registro 16 3 4 0
Registro 17 3 5
35
f
Registro 18 3 6 0
ID_DOC ID_RADICAL FREQUENCIA
Registro 01 1 1
11
f
Registro 02 1 2
12
f
Registro 03 1 6
16
f
Registro 04 2 2
22
f
Registro 05 2 3
23
f
Registro 06 2 4
24
f
Registro 07 3 5
35
f
Tabela 4. 3: Frequencias zeradas descartadas.
Assim sendo, a reconstrução da estrutura original será feita utilizando uma matriz
de
SELECT DISTINCT COUNT(ID_DOC) linhas por SELECT DISTINCT
COUNT(ID_RADICAL)
colunas. Esta reconstrução se dará zerando toda a matriz e
utilizando os índice ID_DOC e ID_RADICAL para colocar as frequencias armazenadas
nas posições corretas.
5. Processamento
No presente capítulo são descritos de forma detalhada os métodos implementados
na etapa de processamento. Além do método de
clustering utilizado também são
discutidos algoritmos complementares que auxiliarão no pocesso de análise da
convergência.
5.1. Clustering
Os métodos de
clustering buscam encontrar grupos (clusters) densos e separados
dentro da massa de dados. O processo de
clustering automático de textos é baseado em
alguma métrica de similaridade e algum critério para o agrupamento [48].
O processo consiste em agrupar os dados em subclasses representativas em que a
similaridade intra-classe seja maximizada e a similaridade inter-classe seja minimizada
[23]. Esta tarefa tem sido estudada no campo do aprendizado de máquina e
reconhecimento de padrões [24] e desempenha um importante papel nas aplicações de
data mining como exploração de dados científicos, recuperação da informação e text
mining
[25].
A aplicabilidade do clustering é bastante vasta, sendo eficiente na identificação
de comportamentos distintos nos dados, traçar perfis de usuários, categorização de genes
no campo da biologia, classificação de documentos na web, etc. Uma metodologia
bastante empregada é a particional, que consiste em dividir a massa de dados em
clusters
tais que os pontos dentro de um
cluster são mais similares entre si do que com elementos
de outros
clusters [28,51].
Dentre as metodologia de
clustering, existem os métodos de particionais são
muito populares e eficazes, sendo encontrados em grande parte dos programas comerciais
de
data mining. Existem dois tipos de clustering particional [41, 42]:
• Hard clustering: a cada dado é atribuido um
label e ele pertence a um e
somente um
cluster.
• Fuzzy clustering: a cada dado pode ser atribuído mais de um
label ponderado
em função de uma métrica de distância. O dado pode pertencer a um ou mais
clusters, regido por uma pertinência a cada cluster.
O que mais espera-se encontrar em um problema de
clustering, são clusters de
baixa distância
intra-cluster, ou seja, clusters densos e compactos. E também clusters
com alta distância
inter-cluster, ou, clusters de alta separabilidade.
Muitas vezes a massa de dados não propicia
clusters com esta configuração, mas
os algoritmos de
clustering, particionais ou não, procuram encontrar clusters homogêneos
e bem separados [44, 45] e para isso podem utilizar artifícios que otimizem o número
desejado de
clusters, entre outras medidas.
No caso da presente aplicação, a intenção do
clustering é encontrar clusters nos
comentários dos especialistas de forma com que estes grupos representem bem o
conhecimento expresso nos textos.
5.1.1. Cálculo da distância inter-cluster
Existem diversas formas de calcular a distância inter-cluster. Dentre as mais
comuns estão os métodos
Single-Link, Complete-Link e Average-Link. Estes
procedimentos também são bem comuns para a execução dos tradicionais métodos de
clustering hierárquico [15], onde utilizando algum destes critérios dois a dois entre os
clusters, obtem-se uma nova configuração de clusters com uma granulosidade diferente,
até que se obtém convergência quando encontra-se um grande
cluster contendo todos os
dados (aglomerativo, abordagem
botton-up) ou diversos pequenos clusters, com cada
dado representando um
cluster (divisivo, abordagem top-down) como ilustra a figura 5.1.
Em ambas as metodologias, aglomerativa ou divisiva, a visualização por meio de um
dendrograma ilustra toda a evolução do processo, além de facilitar a determinação de um
bom número de
clusters.
Figura 5. 1: Clustering hierárquico nas abordagens aglomerativa e divisiva.
O
clustering hierárquico possui algumas desvantagens quando comparados aos
métodos particionais [20]:
• É impraticável para massas de dados muito grandes pela alta complexidade
computacional.
• Não incorpora nenhum conhecimento
apriori.
• O clustering é estático, ou seja, dados incluidos em um cluster no início do
processo não podem mudar de cluster nas configurações posteriores.
• O entendimento do dendrograma fica comprometido quando a massa de dados
é grande demais.
5.1.1.1. Single-Link
O método
Single-Link consiste em atribuir a distância inter-cluster ao par de
objetos mais próximos pertencentes a
clusters diferentes como indicado na equação (5.1).
)',(min),(
'
ppdCCSLink
ji
CpCp
ji
∈∧∈
=
(5.1)
Onde d é uma métrica de distância qualquer.
5.1.1.2. Complete-Link
Single-Link
Cluster
1
Clust
er
2
O método Complete-Link atribui a distância inter-cluster ao par de objetos mais
distântes pertencentes a
clusters diferentes, como representado na equação (5.2).
)',(max),(
'
ppdCCCLink
ji
CpCp
ji
∈∧∈
=
(5.2)
5.1.1.3. Average-Link
O método Average-Link atribui a distância inter-cluster à média das distâncias de
todos os pares de objetos pertencentes a
clusters diferentes e pode ser traduzido pela
equação (5.3).
Com
p
lete-
L
ink
Cluster
1
Cluster
2
(
)
)',(/1),(
'
ppdCpCpnnCCALink
jijiji
∈⋅∈=
∑
∑
(5.3)
Desta forma o Average-Link é dado pelo somatório das distâncias entre cada par
de objetos
inter-cluster divididos pelo número de ligações de objetos inter-cluster.
Tipicamente todos os métodos de distância
inter-cluster citados utilizam a
distância euclidiana, contudo, para problemas de
text mining tradicionalmente utiliza-se a
medida do coseno.
5.1.2. K-Means
Dentre os métodos de
clustering particionais mais conhecidos está o K-Means
[15, 31] e suas muitas variantes (
K-Medoids, K-Harmonic Means, etc.). O algoritmo é
escalável e funcional para grandes massas de dados [21].
O propósito do algoritmo é encontrar
clusters e centróides em dados não
classificados [22]. O entendimento do algoritmo e sua implementação são bem simples:
Dado um K qualquer, será realizado o particionamento dos dados utilizando K
pontos (centróides) inicializados aleatoriamente (abordagem típica – sem
seeding). Estes
centróides serão recalculados pela média dos registros mais próximos a cada um [16] e o
algoritmo alcançará convergência quando estes centróides não se alterarem mais ou
Average-Link
Cluster
1
Cluster
2
alterarem-se menos do que um limiar previamente estabelecido, como ilustra o
fluxograma da figura 5.2 e o esquema da figura 5.3.
Figura 5. 2:O funcionamento do algoritmo K-Means.
1. Centróides inicializados
randomicamente.
2. Centróides associados e movidos aos
registros mais próximos.
Obter
K
Inicializar K centróides
randomicamente
Calcular distância entre os
centróides e os registros
Associar centróides aos seus
registros mais próximos
Reposicionar centróides na
média de seus registros
Centróides
alterados
S N
3. Mais uma vez as distâncias são
calculadas.
4. Configuração final dos clusters, uma vez
que os centróides se estabilizaram.
Figura 5. 3: Esquema de execução do algoritmo K-Means.
5.1.3. Métricas de distância
Como mostrado no ítem anterior, é necessário estabelecer métricas de distância
para o cálculo vetorial entre os centróides e os registros. Para tanto, existem várias
métricas de distância, que devem ser minimizadas, e de similaridade, que devem ser
maximizadas. Os ítens subsequentes listam os medidas implementadas.
5.1.3.1. Distância euclidiana
Medida não normalizada bastante comum e utilizada (5.4).
()
2
1
∑
=
−=
p
i
ii
yxDeuclid
(5.4)
5.1.3.2. Coseno
Métrica de similaridade mais utilizada [48] em problemas de
clustering de textos.
Para problemas de alta dimensionalidade como documentos de textos (representados por
vetores de frequencias TFxIDF), a similaridade do coseno (5.6) tem se mostrado uma
métrica superior à distância euclidiana [19]:
∑∑
∑
==
=
⋅
=
n
i
i
n
i
i
n
i
ii
dq
dq
dq
1
2
1
2
1
),cos(
(5.6)
Onde
),...,(
21 n
qqqq =
é o vetor da consulta com os pesos de cada termo da
consulta
i
q
e
),...,(
2 ni
dddd =
é o vetor do documento com os respectivos pesos de cada
termo
i
d
[38].
5.1.3.3. Distância de Manhattan
Medida de distância também conhecida como distância cityblock ou distância
taxicab (5.7):
∑
=
−=
p
i
ii
yxDmh
1
(5.7)
5.1.3.4. Aproximação minimax
Métrica de distância também conhecida como distância Chebyshev ou distância
chessboard (5.8).
ii
yxD −= maxmaxmin
(5.8)
5.2. Validação do número de clusters
Como dito anteriormente, o algoritmo K-Means é eficiente e amplamente
utilizado em problemas de
clustering de textos. Todavia, o parâmetro K necessita ser
informado, e em se tratando de um método de aprendizado não-supervisionado, esta
informação pode não estar sempre disponível e tampouco ser de simples descoberta [29].
Quantos são os
clusters existentes nos dados, ou ainda, como esta massa de dados
pode agrupar-se da melhor forma possível não são perguntas simples de serem
respondidas. Este é um processo comum tanto aos problemas de
clustering particionais
quanto para os de classificação baseada em vizinhos mais próximos.
Uma solução trivial seria executar o
K-Means várias vezes com diversos valores
para o parâmetro K e levar em consideração o resultado mais satisfatório como correto,
semelhantemente ao FA (
Forgy Approach), que consiste em, no lugar de inicializar os
centróides aleatoriamente, escolher ao acaso K registros da massa de dados e utilizá-los
como centróides iniciais e observar o comportamento do algoritmo em diversas rodadas
[32, 33]. O problema deste tipo de abordagem é que muitas vezes uma rodada não
necessariamente será igual a anterior por causa da inicialização aleatória do algoritmo,
dificultando uma conclusão sobre o resultado do
clustering.
Além disso a massa de dados pode simplesmente agrupar-se de várias formas
diferentes. Por estas razões, utilizar algum tipo de índice estatístico semi-empírico para
validar o número de
clusters (K) é de grande valia. Existem várias propostas neste
sentido. Neste trabalho utilizou-se o índice conhecido como PBM.
5.2.1. Índice PBM
Dentre os índices de melhor resultado está o índice PBM.
O índice PBM pontua o
clustering levando em conta os centróides finais e os
registros a eles associados. Para isso o índice utiliza um
range, que tipicamente varia de 2
até um limiar previamente estabelecido. O índice consiste em executar o algoritmo de
clustering (no caso, o K-Means) com cada um destes valores de 2 até o limiar como
valores de K e pontuar cada rodada. O K de maior índice PBM é considerado como o
melhor número de grupos dentro do
range. O índice PBM é calculado por (5.9):
2
1
1
)(
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
⋅⋅=
k
k
D
E
E
K
KPBM
(5.9)
Como se pode observar, o índice é composto de três parcelas. Cada uma é
explicada nos ítens subsequentes:
•
A primeira parcela serve para priorizar clusterings com o menor K possível.
Quanto menor o K, maior será o valor que esta parcela assumirá.
•
A segunda parcela é formada por
1
E e
k
E
.
1
E é constante para a massa de
dados [18] e
k
E
é calculado pelo somatório das distâncias intra-cluster. Quanto
menor for a distância
intra-cluster, maior será o valor da parcela, favorecendo
assim,
clusters compactos:
∑
=
=
k
k
kk
EE
1
(5.10)
Sendo que,
∑
=
−=
n
j
kjkjk
zxuE
1
(5.11)
•
A terceira parcela, o DK (5.12), é a maior distância inter-centróides. Quanto
maior for a distância inter-centróides, maior será o valor da parcela, favorecendo
assim,
clusters de grande separabilidade. Assim sendo, o valor de DK é calculado
por uma métrica de distância qualquer entre o par de centróides mais distantes
entre si:
ji
k
ji
k
zzD −=
=1,
max
(5.12)
5.3. O plugin PBM_K-Means
Neste item serão apresentadas as interfaces referentes à execução do
plugin
implementado. Todas as telas exibidas subsequentemente foram extraídas do BI
Development Studio [27], que é a ferramenta integrante do SQL Server 2005 para a
execução das tarefas de mineração.
Primeiramente é necessário criar um
data source, que é a instância que representa
a base de dados. No caso da presenta aplicação, esta instância vem de um banco de dados
e por isso todas as informações necessárias sobre a conectividade a este banco de dados
devem ser informadas (
login, senha, nome do servidor, etc.), como mostrado na figura
5.3.
Figura 5. 4: Criação do data source.
Também é necessária a criação de um
data source view, que é a instância que
representa os objetos selecionados no
data source que serão utilizados na resolução do
problema. Estes objetos podem ser tabelas relacionais,
views, etc. O data source view é
exemplificado na figura 5.4.
Figura 5. 4: Criação do data source view.
O próximo passo é a escolha da técnica de mineração. Diversas técnicas estão
disponíveis, todas
built-in desenvolvidas pela Microsoft. Mas quaisquer plugins
desenvolvidos também serão listados, no caso, o
plugin PBM_K-Means, como mostra a
figura 5.6.
Figura 5. 5: Escolha da técnica de mineração.
A figura 5.7 mostra os parâmetros utilizados pelo PBM_K-Means. Ele já possui uma
configuração
default. Mais detalhes sobre a parametrização são dados nos ítens
posteriores.
Figura 5. 6: Parâmetros do PBM_K-Means.
O
plugin PBM_K-MEANS possui uma parametrização padrão mas os valores
podem ser alterados. A seguir são listados os parâmetros e os valores que os mesmos
podem assumir:
•
DIST: parâmetro inteiro que significa a métrica de distância ou medida de
similaridade utilizada pelo método K-Means. Este parâmetro pode assumir os
seguintes valores:
1 – Distância euclidiana
2 – Distância de Manhattan
3 – Aproximação Minimax
4 – Coseno
• K: Número de clusters. Este número, por padrão, é estimado pelo índice
PBM. Porém se ele for informado, o índice PBM será ignorado e o
clustering será
executado com o K informado. K pode assumir os seguintes valores:
-1 – Desconhecido. O K será estimado pelo índice PBM.
[2,INT_MAX] – O K dado dentro deste intervalo será utilizado.
•
MAX_LOOP: Número máximo de iterações do algoritmo K-Means. Caso os
centróides se estabilizem antes deste valor ser atingido, o algoritmo irá
interromper a sua execução automaticamente. Este parâmetro é utilizado também
para cada rodada do K-Means na tentativa de estimar o índice PBM.
•
MET_INTER_CLUSTER: O algoritmo irá gerar uma matriz de distâncias
inter-cluster para auxiliar a análise do resultado. Esta matriz poderá ser gerada
pelo métodos
Single-Link, Complete-Like ou Average-Link. O método default é o
Single-Link:
1 – Método
Single-Link
2 – Método Complete-Link
3 – Método
Average-Link
• PBM_RANGE: Range para o cálculo do índice PBM. O algoritmo será
rodado de 2 até PBM_RANGE e o
clustering em si será feito utilizando o K de
maior índice PBM, a menos que o K tenha sido informado.
Com todas as intâncias criadas, a estrutura de mineração ganhará destaque na tela
principal do BI Development Studio, como exibido na figura 5.8.
Figura 5. 7: A estrutura de mineração criada.
A execução da estrutura com a técnica de mineração de dados escolhida é
mostrada em um tela à parte, como mostra a figura 5.8. Caso seja a primeira execução, o
ambiente executará o
deploy automaticamente.
Figura 5. 8:Execução da estrutura com a técnica de mineração.
Uma vez o processo concluído, o ambiente exibirá uma mensagem de sucesso ou
de erro (conforme o tipo do erro e o seu tratamento), conforme a figura 5.10.
Figura 5. 9: Fim da execução do algoritmo.
6. Pós-processamento
Neste capítulo o programa de pós-processamento será apresentado. O intuito deste
programa é ser uma ferramenta de análise do resultado gerado pela etapa anterior, a etapa
de processamento.
O programa desenvolvido possui uma tela principal, que é mostrada na figura 6.1.
Figura 6. 1: O programa de pós-processamento.
Além de exibir os radicais de maior frequencia no
cluster selecionado (em verde),
o programa também exibe uma tela contendo os comentários de cada
cluster, assim como
mostra a figura 6.2.
Figura 6. 2: Comentários do cluster selecionado.
A etapa de pós-processamento tem a ver com a visualização e análise dos
resultados obtidos na etapa anterior.
Por esta razão, dentro do contexto da convergência na rede se fez importante
saber quais eram os comentários mais relevantes dentro de cada
cluster. Isso se deu pela
similaridade dos documentos aos centróides a eles associados. Estas similaridades foram
calculadas pelo
plugin na etapa de processamento dos dados e exportadas para um
arquivo. O programa de pós-processamento lê o arquivo, faz o
sort pelas similaridades,
exibe uma lista de comentários por
cluster em um treeview e mostra os comentários
propriamente ditos com um identificador do autor, como mostra a figura 6.3.
Figura 6. 3: A relevância dos comentários dentro de seus clusters.
Quanto às distâncias
inter-cluster, também calculadas pelo plugin durante o
processamento, a visão matricial através de uma tabela foi uma visualização adequada e
simples, como na figura 6.4.
Figura 6. 4: Matriz de distâncias inter-cluster.
A evolução do índice PBM também é algo importante de se analizar para ter uma
noção de outros possíveis bons agrupamentos. O programa de pós-processamento
também é capaz de exibir esta informação baseado em um
log gerado pelo plugin na
etapa de processamento, exemplificado na figura 6.5.
Figura 6. 5: Evolução do índice PBM.
O visualizador do índice PBM ajusta o espaço entre cada rodada a fim de
acomodar o resultado na tela sem que o gráfico ultrapasse o limite do
frame. Esta
funcionalidade é um programa à parte integrado em um JAR ao programa de pós-
processamento propriamente dito. Ele foi separado do programa de visualização
propositalmente para que a visualização da evolução do índice PBM pudesse ser feita
sem a execução do programa de pós-processamento.
7. Análise de resultados
Neste capítulo é exemplificada a utilização da metodologia implementada. Para
tal foram considerados 256 comentários efetuados pelos especialistas cujo conteúdo é
representativo de um período analisado.
Ao longo deste período, os temas, e por conseguinte, o conteúdo expresso pelos
textos foram variados e alvo de discussão entre os especialistas participantes da rede.
Mediu-se o tempo que cada etapa levou para convergir. Este tempo foi impresso
no começo e no final da execução dos programas de pré-processamento e processamento,
visto que o pós-processamento é apenas uma leitura dos resultados gerados pela etapa
anterior. Vale ressaltar que os tempos calculados são referentes a um microcomputador
de processador Intel Pentium 4 a 2.0GHz com 512MB de memória RAM e 768MB de
memória virtual (apesar de não ter sido utilizada a memória virtual) rodando Windows
2000 SP4.
Em primeiro lugar, foi efetuado o pré-processamento destes comentários
utilizando a ferramenta desenvolvida detalhada no capítulo 4 (figura 7.1).
Figura 7. 1: O pré-processamento em execução.
Foi utilizada a redução de
stopwords, stemming, exclusão de expressões regulares
pré-definidas e ponderação TFxIDF, além dos parâmetros específicos de conectividade
com o banco de dados.
Ao fim da etapa de pré-processamento, tendo sido feita a remoção de
stopwords e
stemming, foram contabilizados 4995 registros não zerados no banco de dados, como
indica a figura 7.2, que mostra uma
query ao Database Engine, aplicativo integrante do
SQL Server 2005 para o manejo da máquina de banco de dados.
Confirmando a importância do cuidado com a geração da BOW, contando os
registros zerados, teriam sido registros 110696 inseridos. O processo de pré-
processamento levou 00:07:44:678 (sete minutos, 44 segundos e 678 milissegundos),
sendo que mais da metade do tempo foi tomado pelo
stemming.
Documentos considerados pequenos demais foram descartados. Diversos valores
foram utilizados na tentativa de encontrar um bom número que determinasse um mínimo
de radicais em um documento. Após vários testes, um bom valor foi 20, por isso,
documentos que, após a etapa de
stemming, contivessem menos do que 20 radicais foram
considerados pequenos demais e foram descartados.
Figura 7. 2: Registros criados pelo pré-processamento (Database Engine).
Com os dados pré-processados, foi utilizado o BI Development Studio para o
processamento. Foram criados o
data source, o data source view e a estrutura de
mineração escolhida foi o
plugin PBM_K-Means.
A variação para o índice PBM foi de dois a dez, que é a escolha típica. Após a sua
execução, o índice PBM acusou dois
clusters, vide figura 7.3. Por esta razão, o K
utilizado automaticamente pelo algoritmo K-Means foi dois. O processo consumiu
00:00:52 (52 segundos) ao todo.
Figura 7. 3: Evolução do índice PBM. Apesar da oscilação, o melhor K foi dois.
Um fator interessante examinado na etapa de pós-processamento, foi a análise dos
comentários em cada
cluster, que é a tarefa essencial dos programas construídos.
Como dito anteriormente, os comentários são
rankeados pela sua similaridade ao
centróide, no intuito de determinar os comentários mais relevantes dentro de cada
cluster
(quanto mais próximos ao centróide, mais pertinente é o comentário). O apêndice 2
contém tabelas que mostram os três comentários mais relevantes de cada
cluster.
Os comentários agruparam-se nos
clusters majoritariamente da seguinte forma:
comentários sobre hidrogênio em um
cluster, e comentários sobre biodiesel no outro
cluster. Comentários sobre demais assuntos ficaram em ambos os clusters, porém, com
baixa relevância.
Com estes resultados em mãos, é possível concluir que os temas que foram
apontados como soluções no período analisado utilizam tecnologia de biodiesel e
hidrogênio. As tabelas do apêndice 2 estão ordenadas pela relevância dos comentários,
portanto, os comentários expressos no apêndice foram considerados os mais relevantes do
período. Por uma questão de sigilo, os nomes dos especialistas não serão divulgados,
tampouco a sua área de especialização ou a instituição de ensino em que trabalham.
Conclui-se também que o centróide de cada
cluster posicionou-se mais próximo
dos comentários sobre biodiesel e hidrogênio porque os textos sobre estes temas foram
mais bem desenvolvidos, possuindo termos de grande significância (alto TFxIDF). Além
disso ambos os temas geraram mais discussões que os demais, o que significa mais
comentários e, portanto, um posicionamento da média mais característico dos textos
sobre estes assuntos do que os demais.
Entretanto, analisando o alto índice PBM para K = 2 sobre os demais, também
não há indícios fortes de que os outros comentários configurassem um novo
cluster além
dos dois já citados.
8. Conclusão
Neste trabalho foi desenvolvida uma ferramenta de mineração de textos utilizando
os ambientes SQL Server 2005, C++ e Java no intuito de criar uma solução para a analise
da convergência da Rede TECONV. Os métodos implementados para tanto são
amplamente difundidos, e a sua implementação se deu conforme bibliografia referente.
Foi implementado o algoritmo de
clustering K-Means e para auxiliá-lo, também
foi utilizado o índice PBM. Métricas determinantes da distância entre os
clusters foram
utilizadas para complementar o entendimento dos dados processados.
Pode-se concluir que o ambiente apresentou resultados satisfatórios a nível de
tempo computacional e as ferramentas desenvolvidas foram adequadas para uma analise
consistente dos resultados. A massa de dados utilizada agrupou-se consistentemente e os
assuntos mais importantes e que foram amplamente debatidos pelos especialistas da rede
formaram
clusters distintos.
Deve-se ressaltar que este ambiente, apesar de desenvolvido para uma aplicação
específica, pode ser utilizado em diversas outras áreas como
call centers, clustering de
textos corporativos, documentos em geral e muitas outras aplicações referentes ao
clustering de textos.
8.1 Trabalhos futuros
Nesta sessão são apresentados tópicos interessantes para trabalhos posteriores
tanto a nível de aplicação, quanto a nível de crescimento, aprimoramento e demais
utilizações para as ferramentas desenvolvidas. São sugestões de futuras implementações
que podem configurar boas soluções em outras aplicações.
•
Implementação dos métodos necessários para DMX no plugin PBM_K-
Means, a fim de que este possa ser incorporado e utilizado automaticamente em
querys comuns.
• Implementação de demais métodos de validação do número de clusters
além do índice PBM e comparativos de seu funcionamento em
benchmarks e dados
da vida real.
•
Utilização dos programas implementados em demais problemas de
clustering de textos em outras áreas de interesse.
•
Implementação da possibilidade de acoplamento de um thesaurus,
específico para cada tipo de aplicação.
•
Comparativo de custo computacional entre o ambiente utilizado contra
demais ambientes disponíveis.
•
Disponibilização das regras de stemming também no banco de dados para
evitar I/O excessivo nos arquivos e assim ganhar tempo e implementar uma
interface amigável para esta funcionalidade.
•
Aplicação do ambiente a cubos, visto que o SQL Server 2005 também dá
suporte a esta fonte de dados.
•
Implementação de métodos de seeding com comparativos em benchmarks
e dados da vida real.
Apêndice 1: Glossário de abreviaturas
Este apêndice dá um breve significado às várias abreviaturas utilizadas no texto
do presente trabalho
ADO:
ActiveX Data Objects – Série de objetos que desempenham o papel de
middleware entre a aplicação e o OLE.
ATL: Active Template Library – Biblioteca Microsoft para a rápida
implementação de componentes COM.
COM: Component Object Model – Arquitetura de software para a comunicação
de aplicativos.
CSV: Comma-Separated Values – Formato de arquivo onde os dados são
separados por vírgula.
DMX: Data Mining Extensible – Interfaces COM específicas para utilização de
algoritmos de mineração diretamente em
querys.
HTML: Hyper-Text Markup Language – Linguagem de formatação baseada em
tags. Padrão em páginas web.
IDE: Integrated Development Environment – Ambiente de desenvolvimento que
integra várias funcionalidades além do compilador em si, como editor de textos,
drivers, interface gráfica, etc.
J2EE: Java 2 Enterprise Edition – Pacote Java que engloba grande parte das
distribuições menores.
J2SDK: Java 2 Standard Development Kit – Pacote Java para o desenvolvimento
de aplicativos. É necessário para o uso de qualquer IDE Java.
J2SE: Java 2 Standard Edition – Distribuição Java padrão. Inclui classes básicas
para a implementação de aplicativos.
JAR: Java Archive – Tipo de compactação específico para fontes e arquivos
compilados Java. Pode ser usado como executável.
JDBC: Java Database Connectivity – Abstração Java para conexões ODBC.
JRE: Java Runtime Environment – Distribuição para a execução de aplicativos
Java.
JVM: Java Virtual Machine – Máquina virtual para a qual o código-objeto Java é
compilado.
ODBC: Open Database Connectivity – Meio de acesso padrão a bancos de dados.
OLE: Object Linking and Embedding – Meio de acesso abstrato a diferentes
bases de dados.
RSS: Really Simple Syndication – Formato baseado em XML utilizado para
publicação de notícias na
web.
SQL: Structured Query Language – Linguagem padrão para construção de
consultas para acesso a bancos de dados relacionais.
STL: Standard Template Library – Biblioteca C++ para containers e iterators.
VTBL: Virtual Table – Tabela que retém ponteiros para funções.
XHTML: Extensible Hyper-Text Markup Language – Série de sugestões e
padrões para a confecção de HTML. Não passa de HTML puro seguindo boas práticas de
implementação.
XML: Extensible Marckup Language – Linguagem de marcação baseada em tags
para diversos fins. Muito utilizada para a troca de dados e conversação de aplicativos.
Apêndice 2: Comentários mais relevantes de cada
cluster
Neste apêndice são exibidas duas tabelas (tabela 1 e tabela 2) que mostram os
comentários mais relevantes de cada
cluster, citados no capítulo 7.
Rank Comentário
1
Arrisco-me aos comentários a seguir por certa familiaridade com as idéias de J
Rifikin, autor de The Hydrogen Economy. Rifikin mostra-se muito otimista
sobre a utilização do hidrogêneo como combustível - "the forever fuel."
Segundo ele, seria possível o armazenamento e o provimento de energia em
pequena escala, utilizando-se células combustíveis como fontes energéticas
locais, geradas em cooperativas e residências. Haveria assim a convergência
entre as redes descentralizadas de comunicação mundial (internet) e o sistema
energético com base no hidrogeneo (os consumidores seriam também os
produtores). Rifikin propõe a produção de hidrogêneo através de fontes
energéticas renováveis, como a hídrica, eólica e solar, sem emissão de CO2.
Segundo ele, as vantagens seriam: células de energia eficientes; energia gerada
localmente; como resíduos, apenas água e calor. As desvantagens seriam a
dupla geração de eletricidade e o alto custo do processo. Outros comentaristas,
apontam para as distintas vias de obtenção do hidrogênio a) a dos Estados
Unidos - produzir hidrogênio de fontes fósseis e investir, sobretudo, na
pesquisa de tecnologias para capturar o CO2 emitido; b) a via européia -
utilizando-se da energia nuclear ou das energias renováveis acima
mencionadas. Não há, no entanto, consenso sobre a utilização econômica de
hidrogênio. Segundo alguns, sua obtenção economicamente viável ainda estaria
longe; esta seria uma alternativa dos países do Norte carentes de energia solar,
a qual os países do Sul têm em abundância. Nesse sentido, argumentam que
países como o Brasil deveriam concentrar seus esforços em energias renováveis
que depedam da energia solar.
2
Devido ao fato do hidrogênio não estar disponível na natureza da mesma forma
que os combustíveis fósseis, ele não é considerado uma fonte primária de
energia. Tal como a eletricidade, o hidrogênio também precisa ser produzido. A
grande diferença entre eletricidade e o hidrogênio como transportador de
energia é que o hidrogênio pode ser armazenado para uso futuro. Várias fontes
de energia podem ser usadas para produzi-lo, usando uma variedade de
processos. A opção por uma delas dependerá principalmente de critérios
econômicos e ambientais, embora todo o ciclo de vida do hidrogênio deva ser
eficiente para que se consolide como uma alternativa energética. No tocante aos
aspectos econômicos há diferentes estudos que apontam algumas conclusões
coincidentes. A produção de hidrogênio pela energia nuclear e renováveis tem
uma característica similar. Ambas as tecnologias tem altos custos de capital e
baixos custos operacionais. O custo da energia de uma tecnologia intensiva em
capital pode ser baixo se a usina geradora operar a plena potência. Em não
operando a plena potência, o custo aumenta de forma considerável. Estudos
recentes [p.ex. Hammerschlag e Mazza, Energy Policy 33 (2005)] examinaram
a produção de hidrogênio, em sistemas de produção de energia em larga escala,
e a conclusão geral é que as energias renováveis são mais apropriadas para a
produção direta de eletricidade, do que a produção de hidrogênio e subseqüente
conversão em eletricidade. Ainda no aspecto econômico, estes estudos sugerem
que a produção de hidrogênio via nuclear poderá ser mais vantajosa. No caso
da produção via nuclear, é um tema para ser analisado no presente, embora sua
aplicação só ocorra na metade final da próxima década. Atualmente institutos
no Japão, França, Alemanha e Estados Unidos estão concluindo protótipos para
demonstrar a produção de hidrogênio através do calor gerado em usinas
nucleares do tipo HTGR (High-Temperature Gas Reactor). A sugestão para que
a Petrobras avalie a opção de produção de hidrogênio, prende-se ao fato de
considerar que esta aplicação pode ser um segmento de atuação da empresa, em
futuro próximo. E neste caso, estudos prospectivos devem ser realizados, sem
desprezar nenhuma das opções.
3
Dentre os vários desafios relacionados a geração de energia com hidrogênio
são: i) geração e ii) estocagem. As Células de Combustível, utilizando
hidrogênio e ar como combustível, para geração de eletricidade com alta
eficiência e sem impacto ambiental têm o potencial para substituir motores de
combustão veiculares e até mesmo para a geração de energia elétrica em
geradores estacionários ou portáteis. Para aplicações móveis, entretanto é
altamente desejável a utilização de um processo de geração de hidrogênio
interno que evite a necessidade de estocar hidrogênio molecular devido aos
riscos associados. É esperado um incremento muito grande na demanda de
hidrogênio de alta pureza a medida que leis ambientais tornem mais restritivo a
utilização de combustíveis fósseis. Os processos atuais para a geração de
hidrogênio se baseiam em dois principais processos: i) Pela reação de reforma
ou oxidação parcial de hidrocarbonetos ou ii) de-hidrogenação catalítica de
alcanos. Ambos processos requerem processos de purificação complexos, o que
inviabilizaria sua aplicação pratica como fontes portáteis de hidrogênio. OO
hidrogênio é adaptável à maior parte das tecnologias de utilização de energia
existentes atualmente sem modificações maiores e é reconhecido como o
combustível com a maior eficiência de conversão em energia, sendo a produção
deste um tópico extremamente importante. O uso do hidrogênio pode ser
efetuado através da adaptação dos equipamentos atualmente utilizados para a
queima de combustíveis fósseis, mas, de maneira muito mais nobre, pode ser
utilizado em Células de Combustível nas quais ele é recombinado com
oxigênio, regenerando água e liberando a quantidade de energia que foi
armazenada durante sua formação a partir da energia solar. Tal processo é
totalmente limpo, tem total economia atômica (não existem perdas com a
formação de subprodutos) e é extremamente eficiente, constituindo, portanto,
uma das maiores esperanças tecnológicas da atualidade.
Tabela 1: Os três comentários mais relevantes do cluster 1 (Hidrogênio).
Rank Comentário
1
Os autores fazem uma análise realista sobre as características necessárias para
a viabilidade de um biocombustível como alternativa ao combustível fóssil:
benefícios ao meio ambiente, competitividade econômica, rendimento em
relação a energia utilizada na sua produção e produção em quantidade
suficiente para suprir a demanda. Utilizaram dados extraídos principalmente do
Departamento de Agricultura dos USA com relação ao etanol produzido de
milho e biodiesel produzido de soja, no período de 2002 a 2004. Os dados
indicam que o biodiesel obtido de soja leva vantagem significativa sobre o
etanol obtido de milho, ambos produzidos totalmente em áreas já utilizadas na
agricultura para produção de alimentos. As vantagens do biodiesel são relativas
principalmente ao ganho energético em relação a energia fóssil utilizada na sua
produção (biodiesel 93% versus etanol 25%) e quanto ao impacto ambiental ( a
produção de milho gera maior poluição ambiental - pesticidas, nitrato, nitrito,
etc.- em relação a soja). Em 2005, 14,3% do milho produzido nos USA foi
convertido em etanol e isto correspondeu energeticamente a 1,72 % da
gasolina usada no país, enquanto 1,5% da soja produzida contribuiu com
0,009% do diesel. Isto significa que toda produção de milho e soja de 2005
teria contribuido com apenas 12% e 6% da demanda do país, respectivamente.
Levando-se em conta o combustível fóssil utilizado na produção de milho e
soja no período, o rendimento líquido destes processos cairia para 2,4% para o
etanol e de 2,9% para o biodiesel. Conclue-se que em vista do aumento de
demanda de alimentos e de combustíveis renováveis para o futuro próximo,
estes processos parecem não ser adequados em nenhum dos requisitos
considerados necessários a sua viabilidade. Os autores sugerem que a produção
de etanol celulósico a partir de madeira de reflorestamento em áreas não muito
apropriadas à agricultura (o Brasil tem vastas áreas com estas características)
teria vantagens sobre o etanol.
2
Com relação à produção do biodiesel, destaco três pontos: 1. O Programa
Nacional de Produção e Uso de Biodiesel (PNPB), instituído como ação
estratégica para o país, tem como objetivo implementar de forma sustentável a
produção e uso do biodiesel, com enfoque na inclusão social e no
desenvolvimento regional, via geração de emprego e renda, baseando-se no
incentivo à agricultura familiar (Instituição do Selo Combustível Social). Para
tanto são previstas medidas de assistência técnica multidisciplinar e integral
aos agricultores, desde a análise do solo e o acompanhamento das fases de
plantio até a colheita e a comercialização. 2. A utilização de oleaginosas (por
ex., soja) e de cana-de-acúcar para a produção de combustíveis, como o
biodiesel, tem sido criticada tendo em vista possível comprometimento de
áreas agriculturáveis, com prejuízo à produção de alimentos. Entretanto, alguns
dados, se corretos, indicam que tal preocupação, no Brasil, seria infundada: o
Brasil teria mais de 90 milhões de hectares disponíeis para a agricultura, dos
quais apenas 56 milhões ha. seriam utilizados. Haveria ainda 30 milhoes de
hectares (do total de 225 milhoes) ocupados com pastagens, que poderiam ser
disponibilizados com aumento da produtividade. 3. O Prof. Miguel J.
Dabdoub, Coordenador do Projeto Biodiesel da USP em 2003, afirmou em
depoimento ao Grupo de Trabalho Interministerial – Biodiesel, que o soja seria
a melhor alternativa para a implantação inicial de um programa de biodiesel
em nível nacional. (Relatório Final, s/d, vide http://www.biodiesel.gov. br).
Nessa proposta, trata-se de fazer convergir a produção de tecnologia energética
com tecnologia social, para geração de emprego e renda.
3
O crescimento da produção de biodiesel na Uniao Européia é signifcativo: de
65% em 2005 em relação a 2004 (European Biodiesel Board). Alemanha é o
maior produtor mundial do biocombustível, extraído principalmente da canola.
A França é o segundo maior produtor mundial. Comparado com esses países, a
produção brasileira é insignificante. Apesar disso, o Brasil estabeleceu a
obrigatoriedade de adição de 2% de biodiesel até 2008 e 5%, até 2013. Estudos
mostram que o Brasil apesar de contar com diversidade de insumos agrícolas
para a produção de biodiesel, muitas dessas culturas encontram-se ainda em
fase extrativista, com baixo padrão de organização, o que dificulta uma
avaliação real de suas potencialidades em termos de econômicos. Nesse
sentido, há restrições em relação, p. ex., ao óleo de dendê, cuja extraordinária
produtividade é atingida apenas 5 anos após o plantio; quanto ao babaçu, a
produção de óleo por hectare é considerada baixa. Por outro lado, vegetais
como a mamona e o soja, com percentual significativo na exportação, têm sua
viabilidade econômica dependente do preço no mercado externo. Outras
matérias-primas têm sido consideradas, como o nabo forrageiro, o girassol, a
borra do processo siderúrgico, o processo de refino do óleo de soja e o sebo
bovino. O que se pode concluir dos debates é que não haveria um único tipo de
matéria-prima; talvez, a abordagem regional fosse a mais adequada.
Entretanto, parece certo que quaisquer que fossem as matérias-primas, pesados
investimentos em pesquisa e desenvolvimento seriam necessários para o
desenvolvimento de variedades agrícolas mais aptas à fabricação do biodiesel,
de forma a torná-lo competitivo . Outros aspectos como logística, isenções e
incentivos fiscais, problemas de ordem gerencial e organizacional, são também
cruciais para obter-se melhor competitividade para o produto.
Tabela 2: Os três comentários mais relevantes do cluster 2 (Biodiesel).
Bibliografia
[1] Dursun Delen, Martin D. Crossland, 2007, “
Seeding the survey and analysis of
research literature with text mining
”. In Expert Systems with Applications, Tulsa, United
States.
[2] Ian Foster, 2005, “
Service-oriented science”. In Science, 6 May 2005, pp:814
– 817.
[3] Jamie MacLennan, ZhaoHui Tang, 2005, “
Data mining with SQL Server
2005
”. Wiley Publishing Inc., Indianapolis, United States.
[4] Max Chickering, Raman Iyer, 2004, “
A tutorial for constructing a plug-in
algorithm
”. Microsoft Technical Articles, July 2004.
[5] Raman Iyer, Bogdan Crivat, 2004, “
SQL Server data mining: plugin
algorithms
”. Microsoft Technical Articles, July 2004.
[6] Disponível em <http://java.sun.com>
[7] Microsoft Corporation, 1994, “
The Component Object Model: a technical
overview
”. Microsoft Technical Articles, December 1994.
[8] Tony Hey, Anne E. Trefethen, 2002, “
The UK e-science core programme and
the grid
”. In Future Generation Computer Systems, Swindon, United Kingdom, 18
(2002) pp:1017 – 1031.
[9] Orengo, V. M., Huyck, C., 2001 “
A Stemming Algorithm for the
Portuguese Language
”. In Proceedings.Eighth International Symposium on String
Processing and Information Retrieval (SPIRE 2001)
, pp: 186 – 193.
[10] Tony Hey, Anne E. Trefethen, 2005 “Cyberinfrastructure for e-Science”. In
Science, 6 May 2005, pp:817 – 821
[11] The MSDN Library. Disponível em <http://msdn.microsoft.com>
[12] George Shepherd, Brad King, 1999,“Inside ATL”. Microsoft Press.
[13] Juan José García Adeva, Juan Manuel Pikatza Atxa, 2007, “Intrusion
Detection in Web Applications Using Text Mining
”. In Engineering Applications of
Arti.cial Intelligence
20 (2007) pp:555–566.
[14] The Eclipse Project. Disponível em <http://www.eclipse.org>
[15] Sueli A. Mingoti, Joab O. Lima, 2006, “Comparing SOM neural network
with fuzzy c-means, k-means and traditional hierarchical clustering algorithms”. In
European Journal of Operational Research, Volume 174, Issue 3, 1 November
2006, pp: 1742-1759.
[16] M. Peña, J. A. Lozano, P. Larrañaga, 1999, “An empirical comparison of
four initialization methods for the K-Means algorithm”. In
Pattern Recognition
Letters
, Volume 20, Issue 10, October 1999, pp: 1027-1040.
[17] M.F. Porter, 1980, “
An algorithm for suffix stripping”. Program, vol 14, no
3, pp: 130-130.
[18] Malay K. Pakhiraa, Sanghamitra Bandyopadhyayb, Ujjwal Maulikc, 2004,
“
Validity index for crisp and fuzzy clusters”. In Pattern Recognition, Issue 37, pp: 487-
501.
[19] Shi Zhong, 2005, “
Efficient streaming text clustering”. In Neural Networks,
Issue 18, pp: 790–798.
[20] Wu S., Chow T.W.S., 2004, “
Clustering of the self-organizing map using a
clustering validity index based on inter-cluster and intra-cluster density
”. In Pattern
Recognition, Volume 37, Number 2, February 2004, pp: 175-188.
[21] Judong Shen, Shing I. Chang, E. Stanley Lee, Youping Deng, Susan J.
Brown, 2005, “
Determination of cluster number in clustering microarray data”. In
Applied Mathematics and Computation 169 (2005) 1172–1185.
[22] J.M. Górriz, J. Ramírez, E.W. Lang, C.G. Puntonet, 2006, “
Hard C-means
clustering for voice activity detection
”. In Speech Communication 48 (2006) 1638–1649.
[23] Zhonghui Feng, Bing Zhou, Junyi Shen, 2007, “A parallel hierarchical
clustering algorithm for PCs cluster system
”. In Neurocomputing 70 (2007) pp: 809–818.
[24] R.O. Duda, P.E. Hart, D.G. Stork, 2001, “Pattern Classification”. Second
edition, Wiely, New York, 2001.
[25] Pradeep Kumar, P. Radha Krishna, Raju. S. Bapi, Supriya Kumar De, 2007,
“
Rough clustering of sequential data”. In Data & Knowledge Engineering 63 (2007)
183–199.
[26] Salton, G., “
Automatic Text Processing”, Addison-Wesley, 1989.
[27] Alex Payne, 2004, “Business Intelligence and Data Warehousing in SQL
Server 2005
”. Microsoft Technical Articles, July 15, 2004.
[28] S. Guha, R. Rastogi, K. Shim, 1998, “The Proceedings of the ACM
SIGMOD Conf., 1998.
[29] Yun Xu, Richard G. Brereton, 2005, “
A comparative study of cluster
validation indices applied to genotyping data
”. In Chemometrics and Intelligent
Laboratory Systems 78 (2005) pp: 30–40.
[30] Simon Günter, Horst Bunke, 2003, “Validation indices for graph clustering”.
In Pattern Recognition Letters 24 (2003) pp: 1107–1113.
[31] MacQueen, J.B., 1967. “
Some methods for classification and analysis of
multivariate observation
”. In: Le Cam, L.M., Neyman, J. (Eds.), Berkeley Symposium on
Mathematical Statistics and Probability.
[32] Stephen J. Redmond, Conor Heneghan, 2007, “
A method for initialising the
K-means clustering algorithm using kd-trees
”. In Pattern Recognition Letters 28 (2007)
pp: 965–973.
[33] J.M. Peña, J.A. Lozano, P. Larrañaga, 1999, “
An empirical comparison of
four initialization methods for the K-Means algorithm
”. In Pattern Recognition Letters 20
(1999) pp: 1027-1040.
[34] Figuerola C. G., Gómez R., Rodríguez A. F. Z. e Berrocal J. L. A.,
“
Stemming in Spanish: A First Approach to its Impact on Information Retrieval”,
In Carol Peters, editor, Working notes for the CLEF 2001 Workshop, Darmstadt,
Germany, September 2001.
[35] Taghva K., Beckley R., and Sadeh M., “A Stemming Algorithm for the
Farsi Language
”. In Proceedings of International Symposium on Information
Technology: Coding and Computing (ITCC 2005), Volume 1, 4-6, April 2005,
Las Vegas, Nevada, USA. IEEE Computer Society 2005.
[36] Bastos, V. M., 2006, “Ambiente de Descoberta de Conhecimento na Web
para a Língua Portuguesa
”. Rio de Janeiro, 2006.
[37] Scott Meyers, 2001, “Effective STL”, Addison-Wesley Professional. 1st
edition (June 6, 2001).
[38] Salton, G., Wong, A., Yang, C., “
A vector space model for automatic
indexing
”, Communications of the ACM, v. 18, pp. 163-620, 1975.
[39] Hsin-Chang Yang, Chung-Hong Lee, “
A text mining approach on automatic
generation of web directories and hierarchies
”. In Expert Systems with Applications 27
(2004) 645–663.
[40] H.M. Deitel, P.J Deitel, “C++: Como Programar”, Bookman, 3ª edição,
Porto Alegre 2001.
[41] Mingqin Liu, Ashok Samal, 2002, “
Cluster validation using legacy
delineations
”. In Image and Vision Computing.
[42] N. Zahid, O. Abouelala, M. Limouri, A. Essaid, 1999, “Unsupervised fuzzy
clustering
”. In Pattern Recognition Letters 20 (1999) pp: 123-129.
[43] John W.T. Lee, Daniel S.Yeung, Eric C.C. Tsang, 2005, “
Hierarchical
clustering based on ordinal consistency
”. In Pattern Recognition 38 (2005) pp: 1913–
1925.
[44] Fattori M, Pedrazzi G, Turra R., “
Text mining applied to patent mapping: a
practical business case
”. World Patent Informat 2003 25:335–42.
[45] Antoine Blanchard, 2007, “
Understanding and customizing stopword lists for
enhanced patent mapping
”. In World Patent Information.
[46] Akiko Aizawa, 2003, “
An information-theoretic perspective of tf–idf
measures
”. In Information Processing and Management 39 (2003) pp: 45–65.
[47] Kishore Papineni, “
Why inverse document frequency?”. IBM T. J. Watson
Research Center, Yorktown Heighs, NY 10598, USA.
[48] Aurora Pons-Porrata, Rafael Berlanga-Llavori, José Ruiz-Shulcloper, 2007,
“
Topic discovery based on text mining techniques”. In Information Processing and
Management 43 (2007) pp: 752–768.
[49] Sung-Shun Weng, Chih-Kai Liu, 2004, “Using text classification and
multiple concepts to answer e-mails
”. In Expert Systems with Applications 26 (2004)
529–543.
[50] A.A. Lopes, R. Pinho, F.V. Paulovich, R. Minghim, 2007, “
Visual text
mining using association rules
”. In Computers & Graphics 31 (2007) pp: 316–326.
[51] Dmitri G. Roussinov, Hsinchun Chen, 1999, “
Document clustering for
electronic meetings: an experimental comparison of two techniques
”. In Decision
Support Systems 27 1999 67–79.
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
