FILTRAGEM DE INFORMAÇÃO NA WEB USANDO REDE NEURAL DE HOPFIELD E ONTOLOGIA - PDF
Download "FILTRAGEM DE INFORMAÇÃO NA WEB USANDO REDE NEURAL DE HOPFIELD E ONTOLOGIA"
Lucas Nathan Bonilha Lencastre
1 FILTRAGEM DE INFORMAÇÃO NA WEB USANDO REDE NEURAL DE HOPFIELD E ONTOLOGIA Daniel Mandelli Martins Faculdade de Engenharia de Computação CEATEC Juan Manuel Adán Coello Grupo de Pesquisa em Sistemas Inteligentes CEATEC Resumo: A grande quantidade de informação presente na Web torna difícil a recuperação de informações pertinentes aos usuários. Novas ferramentas são necessárias para filtrar informações relevantes. Este artigo detalha o funcionamento de um agente que vasculha a Web à procura de informações e retorna documentos de acordo com os interesses do usuário. O agente opera em dois modos: geração do espaço de conceitos e filtragem de documentos. O espaço de conceitos de um domínio é representado por uma matriz de coeficientes assimétricos de similaridade para cada par de termos relevantes no domínio. Essa matriz é utilizada como uma rede neural de Hopfield, usada juntamente com uma ontologia para filtragem de documentos, onde os termos representam neurônios e os coeficientes de similaridade os pesos das conexões que ligam os neurônios. A ontologia é utilizada para fornecer uma relação entre termos do domínio, quando os termos encontrados no documento a filtrar não forem iguais aos termos do domínio presentes na entrada da neural de Hopfield. Os experimentos realizados até o momento mostram que o uso de ontologia influencia positivamente a capacidade de filtragem do agente, embora seja necessário aprimorá-lo em trabalhos futuros para torná-lo computacionalmente viável. Palavras-chave: Filtragem de informação; Web; Ontologia, Rede neural; Agentes. Área do Conhecimento: Ciências Exatas e da Terra, Ciência da Computação. 1. INTRODUÇÃO Com a expansão da Web, os usuários enfrentam dificuldades crescentes para encontrar informações relevantes. Contribuem para esse cenário a natureza não estruturada dos dados armazenados, principalmente documentos de texto usando a linguagem HTML, e a natureza dinâmica da Web que requer que os usuários continuamente realizem pesquisas para a seleção de novos documentos de interesse. Esta situação tem motivado o desenvolvimento de agentes de software pessoais de filtragem de informações que continuamente buscam a Web à procura de documentos de interesse para seus usuários. As necessidades de informação mudam de usuário para usuário. Portanto, os sistemas de filtragem de informação têm que ser personalizados para satisfazer os interesses de cada usuário, assumindo o papel de assistentes pessoais. Esse tipo de sistema de filtragem de informação tem de preencher três requisitos: (1) Especialização: o sistema seleciona os documentos relevantes para o usuário e descarta os outros; (2) Adaptação: a filtragem da informação é um processo interativo feito por largos períodos de tempo, durante o qual os interesses dos usuários são sujeitos a mudança; (3) Exploração: o sistema deve ser capaz de explorar novos domínios, a fim de encontrar algo novo, potencialmente interessante para o usuário. Diferentes modelos e sistemas foram implementados para recuperação e filtragem de informações. Normalmente, estes sistemas são constituídos por três componentes principais responsáveis por (1) representar os documentos, (2) representar os interesses dos usuários e (3) estabelecer uma correspondência entre os interesses dos usuários e as representações dos documentos [1] [2]. Hopfilter é um agente pessoal que vasculha fontes de informações na Web e recupera documentos de acordo com interesses do usuário [3] [4] [5]. Em linhas gerais, Hopfilter funciona da seguinte maneira: inicialmente, o usuário manualmente seleciona uma coleção de documentos sobre um assunto de interesse. Através de um mecanismo de indexação automática, o sistema gera os termos que melhor representam o conteúdo da coleção. Com o uso de funções estatísticas que calculam a co-ocorrência dos termos na coleção, o sistema gera uma matriz de similaridade, que contêm os termos e os coeficientes que indicam o grau de relacionamento entre cada par de termos. Essa matriz de similaridade é interpretada como uma rede de conhecimento ou um espaço de conceitos. O espaço de conceitos representa uma rede neural com os neurônios (termos) interligados através de pesos sinápticos (coeficientes
2 de relacionamento). O processo de filtragem começa quando um documento a ser filtrado é usado como um padrão de entrada para a rede. Quando a rede converge para o equilíbrio, a quantidade de neurônios ativos indica se o documento é compatível com os conceitos armazenados na memória da rede ou não. Se o documento é considerado relevante, o usuário é notificado de que o documento filtrado contém informações de interesse. O método de filtragem usado possui uma limitação na ativação inicial dos neurônios da rede neural de Hopfield, já que eles são apenas inicializados com valor 0 ou 1 dependendo da presença de um termo no espaço de conceitos e no documento a ser filtrado. O uso de ontologia [6] foi proposto como uma solução, já que fornece relações entre conceitos, possibilitando a determinação de uma relação entre um termo no espaço de conceitos com outro no documento a ser filtrado. Assim é possível inicializar um neurônio não apenas com valor 0 ou 1, mas com qualquer valor no intervalo real [0, 1]. O artigo está organizado da seguinte forma, Introdução nesta seção, a arquitetura do Hopfilter é apresentada na seção 2, a seção 3 apresenta os resultados de alguns experimentos realizados para avaliar o agente e a seção 4 encerra o artigo com as observações finais. 2. ARQUITETURA DO HOPFILTER O agente de filtragem é composto dos seguintes módulos: Interface Usuário (IU), Interface Web (IW), Pré-Processamento de Documento (PPD), Indexação Automática (IA), Geração do espaço de conceitos (GEC), Rede Neural Artificial (RNA), Controle de Ontologia (CO) e String Matcher com Aproximação (SMA). Os módulos IU, IW, PPD, IA, GEC e RNA não estão no foco deste trabalho, portanto serão apenas brevemente descritos com foco em suas relações com o funcionamento do CO e o SMA. O agente de filtragem funciona em dois modos: "geração do espaço de conceitos" e "filtragem de documento. O modo de geração do espaço de conceitos utiliza os módulos PPD, IA, GEC e CO. O modo de filtragem de documentos utiliza os módulos PPD, IA, RNA, CO e SMA. Para executar o modo de "filtragem de documento", um espaço de conceitos para o domínio considerado já deve estar disponível. O funcionamento de cada modo de operação é brevemente descrito a seguir. Inicialmente o CO carrega a ontologia a ser usada e extrai o nome de suas classes, que serão utilizados tanto para a seleção de termos do espaço de conceitos quanto para a filtragem de documentos. Para gerar o espaço de conceitos, uma coleção de n documentos selecionados pelo usuário sobre um domínio específico, deve ser apresentada ao agente. O PPD remove as tags HTML do documento, produzindo texto corrido. Das palavras identificadas, o módulo de IA remove stop words, tags HTML e outros elementos indesejados, e gera os termos. Os termos que melhor representam a coleção de documentos são selecionados pelo GEC com o auxilio do CO, se desejado. O GEC então calcula os coeficientes assimétricos de similaridade para cada par de termos selecionado. Os termos com os respectivos coeficientes assimétricos de similaridade são arranjados em uma matriz de similaridade, ou espaço de conceitos. O agente interpreta o espaço de conceitos como uma rede neural artificial de Hopfield [7], onde os termos correspondem aos neurônios e os coeficientes de similaridade assimétrica aos pesos das conexões dos neurônios. Para filtrar um documento, o agente inicialmente identifica as palavras no documento, usando o PPD, e gera os termos que representam o documento usando a IA. A RNA utiliza os termos gerados pela IA para criar um vetor da forma x = (x 1, x 2,..., x n ), onde n é igual ao número de termos no espaço de conceitos, e x i corresponde ao i-ésimo termo gerado pelo processo. No momento de filtrar um documento, x i será 1 se o i-ésimo termo está presente no documento a filtrar. Caso contrário, x i pode receber um valor entre 0 e 1 se houver um termo no documento que possuir alguma relação com o termo do espaço de conceitos, conforme verificado pelos módulos CO o SMA. Caso não haja relação alguma, x i recebe 0. Esse vetor é então usado para ativar a rede neural de Hopfield. Uma vez ativada, a rede irá procurar um estado de equilíbrio. Quando esse estado é atingido, o número de neurônios ativos indica a relevância do documento filtrado Pre-Processamento (PPD) O módulo de pré-processamento recebe uma página da Web e produz como saída um texto simples. Tags HTML, sinais de pontuação, datas, números e vários outros símbolos são retirados do documento de entrada, restando somente palavras Indexação Automática (IA) Quando um documento é indexado, o resultado é uma lista de termos, ou índices, que representa o conteúdo do documento. A indexação automática consiste em duas operações: a remoção de stop words e formação de termos Geração do Espaço de Conceitos (GEC) Este módulo calcula os coeficientes de similaridade para cada par de termos e gera a matriz de similari-
3 dade que contém os termos e seus respectivos coeficientes. Esta matriz representa o espaço de conceitos. É possível especificar a porcentagem mínima de termos que obrigatoriamente estão presentes na ontologia, utilizando-a como apoio na seleção de termos relevantes ao assunto. A filtragem funciona da seguinte maneira: primeiramente são selecionados apenas os melhores termos presentes na ontologia, que posteriormente são substituídos pelos melhores termos presentes ou não na ontologia, garantindo assim que uma porcentagem mínima de termos estabelecida pelo usuário estará presente na ontologia Rede Neural Artificial de Hopfield (RNA) Este módulo é utilizado para filtrar um documento por meio da rede neural de Hopfield. Inicialmente, o documento a ser filtrado é submetido aos módulos PPD e IA. Ele será representado por um conjunto de termos ou índices, como foi feito para gerar o espaço de conceitos. Estes termos irão definir os elementos de um vetor de tamanho n, que será utilizado como entrada da rede neural, para um espaço de conceitos com n termos. O vetor de entrada terá a forma x = (x 1, x 2,..., x n ), onde x i a maior relação dentre todas as relações entre o termo i no espaço de conceitos e todos os outros termos no documento. A relação entre o termo i do espaço de conceitos e um termo j no documento será 1 se o termo i do espaço de conceitos for igual ao termo j do documento. Caso contrário, a relação pode ainda receber um valor entre 0 e 1 se o termo j do documento possuir alguma similaridade ontológica com o termo i do espaço de conceitos. Para determinar se existe similaridade ontológica, o termo do documento é enviados ao SMA, que utilizando o CO, retorna o termo na ontologia mais próximo, junto com sua similaridade léxica ao termo j do documento, que é um valor de 0 a 1. Se a similaridade léxica for maior que o mínimo aceitável fornecido pelo usuário, o CO calcula a similaridade ontológica entre os termos, que é então multiplicada pelo valor de similaridade léxica, obtendo-se assim a relação entre o termo j do documento e o termo i do espaço de conceitos. Caso não haja similaridade ontológica, a relação recebe 0. Por exemplo, considerando o termo avião do espaço de conceitos, o termo carros do documento, os termos avião e carro da ontologia mostrada na Figura 1, o valor 0,8 para o mínimo de similaridade léxica aceitável e que a similaridade léxica, calculada pelo SMA, entre carro e carros seja 0,9 temos que x i não receberá o valor 1, pois o termo do espaço de conceitos (avião) e o termo do documento (carros) não são iguais, porém também não receberá o valor 0, pois o termo do espaço de conceitos (avião) está presente na ontologia e o termo do documento (carros) possui similaridade léxica com o termo carro da ontologia maior do que a mínima fornecida pelo usuário. Considerando que a similaridade ontológica, calculada pelo CO, entre os termos avião e carro da ontologia seja 0,135, a relação final entre o termo no espaço de conceitos (avião) e o termo no documento (carros) seja 0,1215 (0,9 * 0,135). Supondo que essa relação seja a maior de todas as relações entre o termo no espaço de conceitos (avião) e todos os outros termos no documento, x i receberá o valor 0, String Matcher Aproximado (SMA) Este módulo é utilizado como apoio ao CO, fornecendo uma maneira de usar termos que não estão presentes na ontologia, mas que têm similaridade léxica com termos na ontologia. Utilizando o algoritmo de comparação de strings de White [8], é computada a similaridade léxica do termo j do documento com seu melhor representante na ontologia. Essa similaridade léxica é então multiplicada pela similaridade ontológica entre o termo do espaço de conceitos i com o melhor representante do termo do documento j na ontologia, para obter o valor final da relação entre o termo j do documento e o termo i do espaço de conceitos. O valor dessa relação será atribuído a x i caso ele seja o maior dentre todos os valores das relações entre o termo i do espaço de conceitos com todos os termos do documento Controle de Ontologia (CO) O módulo de Controle de Ontologia (CO) é utilizado para determinar se existe relação entre o termo i, associado à entrada x i da rede neural, e um termo j do documento a filtrar, de modo a calcular o valor x i do vetor de entrada da rede neural de Hopfield. São utilizados o Jena Framework [9] e o editor de ontologias Protégé [10] para criar modelos da ontologia. O modelo criado pelo Protégé [11] é consultado para determinar a profundidade da classe representada pelo termo i, através de um algoritmo recursivo que conta a quantidade de superclasses que a classe do termo i possui, utilizando o método getnamedsuperclasses() do Protégé [12] para determinar a superclasse de uma classe na ontologia. O mesmo processo é utilizado para determinar a profundidade da classe do termo j. As profundidades das classes dos termos i e j são somadas e a soma é guardada para uso no cálculo de similaridade ontológica. O modelo é consultado novamente para determinar a profundidade da classe do menor ancestral comum entre as classes dos termos i e j. Para determinar o menor ancestral comum, o modelo criado
4 pelo Jena [13] é consultado através do método getl- CA() [14]. Essa profundidade é multiplicada por 2 e o resultado é também guardado para uso no cálculo de similaridade ontológica, descrito a seguir: (1) sim ij é a similaridade ontológica entre os termos i e j, e ds ij é a distância semântica entre os termos i e j, segundo a equação: (2) Onde som é a soma das profundidades das classes dos termos i e j, e mult é a profundidade multiplicada por 2 do menor ancestral comum dos termos i e j. Por exemplo, considerando o termo avião do espaço de conceitos, o termo carros do documento, o parâmetro 0,8 mínimo de similaridade léxica, que a similaridade léxica entre carro e carros é 0,9 e a ontologia: Figura 1. Ontologia. Temos que o melhor representante do termo j na ontologia é carro e sua similaridade léxica com o termo j é maior que a mínima permitida, portanto é o que será utilizado no calculo. A profundidade da classe avião é 4 (a classe coisa está presente em todas as ontologias, portanto não é considerada na conta e não é um menor ancestral comum valido) e a profundidade da classe carro é 4, portanto som será 8. O menor ancestral comum entre as classes avião e carro é transporte de pessoas cuja profundidade é 2, portanto mult será 4. Segundo a e- quação (2) ds ij será 2, portanto segundo a equação (1) a similaridade ontológica entre o termo avião do espaço de conceitos e o termo carro do documento será aproximadamente 0,135. Ao final desta etapa, obtêm-se a similaridade ontológica, que é então multiplicada pela similaridade léxica para determinar a relação final entre os termos. Este valor é utilizado pelo RNA como um possível valor para x i no vetor de entrada da rede neural de forma x = (x 1, x 2,..., x n ). 3. AVALIAÇÃO EXPERIMENTAL O agente foi avaliado utilizando documentos retirados da Web em grande maioria da Wikipedia e armazenados em um repositório local, o que permite o cálculo da cobertura e da precisão. Os documentos estão em inglês e tratam de diversos assuntos, sendo cada um deles específico a apenas um assunto. Para determinar se o uso de ontologia foi benéfico ao agente, foi realizado um experimento sem uso de ontologia e outro com uso de ontologia. A ontologia utilizada para o experimento é especifica sobre transporte [15]. Foram criados dois espaços de conceitos utilizando 14 documentos que tratam de transporte sendo que 50% dos termos de um espaço de conceitos foram filtrados pela ontologia. Ambos espaços de conceitos têm 20 termos, cada um com uma a três palavras. O espaço de conceitos filtrado foi utilizado no experimento com ontologia e o outro no experimento sem ontologia. Todos os outros parâmetros são os mesmos nos dois testes. Foram utilizados 48 documentos de diversos assuntos sendo 12 deles sobre transporte e diferentes dos utilizados para gerar o espaço de conceitos, portanto relevantes. Na rede neural foram usados os mesmos parâmetros empregados em [4], isto é energia = 0,025; curvatura = 0,01; e viés (bias) = 0,7. A eficácia do agente de filtragem de documentos foi medida utilizando as taxas de precisão e cobertura, amplamente utilizadas pela comunidade de recuperação de informação [16]. A precisão é calculada dividindo o número de documentos relevantes recuperados pelo número total de documentos recuperados. A cobertura é calculada dividindo o número de documentos relevantes recuperados pelo número de documentos relevantes disponíveis na base de documentos. No experimento com ontologia a precisão foi 43% e a cobertura 100%. No experimento sem ontologia a precisão foi 32% e a cobertura 91%. Estes dados sugerem que o uso de ontologias propicia melhoras relevantes na filtragem realizada pelo agente Hopfilter tanto na precisão como na cobertura. 4. CONCLUSÃO Embora o uso de espaço de conceitos e memória associativa mostra resultados satisfatórios em sistemas de filtragem de informação, esse sistema depende muito da seleção dos termos a serem utilizados para a criação do espaço de conceito. Termos muito comuns no domínio têm baixo poder descritivo e reduzem a taxa de precisão da filtragem. O mecanismo de seleção de termos atual necessita de aprimoramento, pois seleciona termos indesejados que diminuem a precisão do agente.
5 Nos experimentos realizados, o uso de ontologia mostra resultados positivos, porém causou grande perda de desempenho ao agente, que passa a levar muito mais tempo para realizar a busca. É imperativo aprimorar o módulo CO para que ele utilize menos recursos e se torne computacionalmente viável. O uso de caches implementados com tabelas de hash é sugerido, pois o calculo de similaridade ontológica é freqüentemente repetido, já que os termos se repetem em um mesmo documento e em documentos diferentes. Como o método de determinação de relevância de cada documento é independente, outra sugestão é paralelizá-lo para que se beneficie de sistemas com múltiplos processadores, possibilitando que a filtragem do repositório de documentos seja realizada simultaneamente por diferentes processadores. REFERÊNCIAS [1] Salton, G., McGill, M.J. The SMART and SIRE Experimental Retrieval Systems. In: Readings in Information Retrieval, p Morgan Kaufmann Publishers, Pine Street, Sixth Floor. San Francisco, [2] Yan, T.W., Garcia-Molina, H. The SIFT Information Dissemination System. ACM Transactions on Database Systems 24(4), p , [3] Monteiro, P. P. Filtragem de Páginas Web Baseada em Redes Neurais Artificiais de Hopfield. Trabalho de Conclusão de Curso. Faculdade de Engenharia de Computação, PUC-Campinas, [4] Marin, A., Adán Coello, J. M., Rosa, J. L. G., Tobar, C. M., Freitas, R. L. Personalized Web page filtering using a Hopfield neural network. Lecture Notes in Computer Science, v.4669, p , [5] Willens, E. R. Busca e Filtragem De Informações Na Web Uma Abordagem Envolvendo Redes Neurais Artificiais de Hopfield e Ontologias. Trabalho de Conclusão de Curso. Faculdade de Engenharia de Computação, PUC-Campinas, [6] ONTOLOGY. Disponível em: _science). Acesso em: 14 de [7] Hopfield, J. J. Neural networks and physical systems with emergent collective computational properties. Proc. Nat. Acad. Sci. (USA) 79, p , [8] White, S., How to Strike a Match. Disponível em: Cycles/How-to-Strike-a-Match. Acesso em: 11 de [9] JENA FRAMEWORK. Disponível em: Acesso em: 14 de [10] PROTEGE. Disponível em: Acesso em: 14 de [11] PROTEGE OWL, OWLModel. Disponível em: nford/smi/protegex/owl/model/owlmodel.html. Acesso em: 11 de [12] PROTEGE OWL, RDFSClass. Disponível em: wl/edu/stanford/smi/protegex/owl/model/rdfscl ass.html. Acesso em: 11 de [13] JENA FRAMEWORK, OntModel. Disponível em: na/ontology/ontmodel.html. Acesso em: 11 de [14] JENA FRAMEWORK, OntTools. Disponível em: na/ontology/onttools.html. Acesso em: 11 de [15] TRANSPORTATION ONTOLOGY. Disponível em: Acesso em: 14 de [16] Rijsbergen, C.J.: Information Retrieval. Butterworths, London, 1979.
PROPAGAÇÃO DE INFLUÊNCIA EM REDES SOCIAIS
PROPAGAÇÃO DE INFLUÊNCIA EM REDES SOCIAIS Júlia Coelho Furlani Faculdade de Engenharia de Computação / CEATEC juliacfurlani@gmail.com Juan Manuel Adán Coello Grupo de Pesquisa em Sistemas Inteligentes