Embed Size (px)
Citation preview
MATEUS DALTO PIVETA
DETECÇÃO DE LIGAÇÃO ENTRE HISTÓRIASCOM RECONHECIMENTO DE ENTIDADES NO
LONDRINA–PR
2013
MATEUS DALTO PIVETA
DETECÇÃO DE LIGAÇÃO ENTRE HISTÓRIASCOM RECONHECIMENTO DE ENTIDADES NO
Trabalho de Conclusão de Curso apresentadoao curso de Bacharelado em Ciência da Com-putação da Universidade Estadual de Lon-drina para obtenção do título de Bacharel emCiência da Computação.
Orientador: Prof. Dr. Daniel dos Santos Kas-ter
LONDRINA–PR
2013
MATEUS DALTO PIVETA
DETECÇÃO DE LIGAÇÃO ENTRE HISTÓRIASCOM RECONHECIMENTO DE ENTIDADES NO
Trabalho de Conclusão de Curso apresentadoao curso de Bacharelado em Ciência da Com-putação da Universidade Estadual de Lon-drina para obtenção do título de Bacharel emCiência da Computação.
BANCA EXAMINADORA
Prof. Dr. Daniel dos Santos KasterUniversidade Estadual de Londrina
Orientador
Prof. Dr. Segundo Membro da BancaUniversidade/Instituição do Segundo
Membro da Banca
Prof. Msc. Terceiro Membro da BancaUniversidade/Instituição do Terceiro
Membro da Banca
Londrina–PR, 24 de novembrode 2013
LONDRINA–PR2013
AGRADECIMENTOS
À minha família, pelo amor e apoio de sempre. A meu pai Fábio e minha mãeSandra pelo apoio e por tudo que sempre fizeram por mim, pela simplicidade, exemplo ecarinho, fundamentais na construção do meu caráter.
Aos meus amigos por todo apoio e cumplicidade. Porque mesmo quando distantes,estavam presentes em minha vida.
Ao orientador Daniel Kaster, pelo apoio e conhecimento transmitido.
A todos que de alguma forma ajudaram, agradeço por acreditarem no meu poten-cial, nas minhas idéias, nos meus devaneios, principalmente quando nem eu mais acredi-tava.
Sem vocês nada disso seria possível.
PIVETA, M. D.. Detecção de Ligação entre Histórias com Reconheci-mento de Entidades no Twitter. 41 p. Trabalho de Conclusão de Curso(Graduação). Bacharelado em Ciência da Computação – Universidade Esta-dual de Londrina, 2013.
RESUMO
As redes sociais emergiram como ferramentas valiosas para a comunicação etroca de informação dos mais diferentes tipos. Como resultado do rápido crescimentodas redes sociais, o volume de dados com o qual o usuário é exposto é desproporcionalao tempo disponível para o seu consumo. Técnicas são encontradas na literatura paralidar com o problema do excesso de informação. Este trabalho aborda as técnicas deStory Link Detection aplicadas a redes sociais. O objetivo é o desenvolvimento de ummétodo para detectar com precisão quando dois ou mais tweets tratam do mesmoassunto utilizando métodos abordados na literatura para detecção de similaridade.
Através dos experimentos realizados, foi proposto um novo método para aDetecção de Ligação entre Histórias que usa o valor de relevância retornado pelo Re-conhecedor de Entidades. Tal método obteve um desempenho muito acima daquelesutilizados em sistemas de processamento de texto padrão.
Palavras-chave: detecção de ligação entre histórias, reconhecimento de enti-dades, twitter, sobrecarga de informação
PIVETA, M. D.. Story Link Detection with Named Entity Recogniza-tion on Twitter. 41 p. Final Project (Undergraduation). Bachelor of Sciencein Computer Science – State University of Londrina, 2013.
ABSTRACT
Social networks have emerged as valuable tools for communication and in-formation exchange of many different types. As a result of the fast growth of themain social networks, the volume of data that the user is exposed is disproportionalto the time available for its consumption. Techniques are found in the literature todeal with the problem of information overload. This work address the Story LinkDetection technique applied to social networks. The objective of the work is todevelop a method to accurately detect when two or more tweets are in the samesubject using methods discussed in the literature for similarity detection.
Through the experiments, was proposed a new method for the Story LinkDetection using the relevance score returned by Entity Recognizer. This methodachieved a performance far above those used in standard text processing systems.
Keywords: story link detection, named entity recognization, twitter, infor-mation overload
LISTA DE ILUSTRAÇÕES
Figura 1 – Cálculo de similaridade utilizando o TF-IDF . . . . . . . . . . . . . . . 28Figura 2 – Cálculo de similaridade utilizando o score . . . . . . . . . . . . . . . . 29Figura 3 – Cálculo de similaridade utilizando o score e elimininando tweets com
menos de 10 entidades . . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figura 4 – Cálculo de similaridade utilizando o score e filtrando pelo tipo de entidade 30Figura 5 – Cálculo de similaridade utilizando o score, quebra de entidades, remo-
ção de entidades e comparação com plurais . . . . . . . . . . . . . . . . 30Figura 6 – Resultados utilizando o TF-IDF . . . . . . . . . . . . . . . . . . . . . . 31Figura 7 – Resultados utilizando o score . . . . . . . . . . . . . . . . . . . . . . . 32Figura 8 – Resultados utilizando o score e removendo tweets com menos de 5 en-
tidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Figura 9 – Resultados utilizando o score e removendo tweets com menos de 10
entidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33Figura 10 –Resultados utilizando o score com filtragem por tipos de entidades . . . 34Figura 11 –Cálculo utilizando o score, removendo stopwords em todos os tweets . . 34Figura 12 –Cálculo utilizando o score, removendo stopwords e filtrando por tipos
de entidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35Figura 13 –Cálculo utilizando o score e fazendo comparações utilizando o plural . . 36Figura 14 –Cálculo utilizando o score, removendo stopwords e fazendo comparações
utilizando o plural . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
SUMÁRIO
1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Definição do Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.1 O Twitter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 A era da sobrecarga de informação . . . . . . . . . . . . . . . . . . . . . 152.3 O Twitter como veículo de informação gerador de ruído . . . . . . . . . . 162.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 Conceitos e Técnicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.1 Detecção de Ligação entre Histórias . . . . . . . . . . . . . . . . . . . . . 193.2 Reconhecimento de Entidades Nomeadas . . . . . . . . . . . . . . . . . . 203.3 Medidas de similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.1 TF-IDF e Similaridade de Cossenos . . . . . . . . . . . . . . . . . 213.3.2 Soft TF-IDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.3.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Proposta para Detecção de Ligação entre Histórias com a utilizaçãode Reconhecimento de Entidades Nomeadas . . . . . . . . . . . . . . . 254.1 Gold Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Detecção de Entidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.3 Cálculo de similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.3.1 Soft TF-IDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3.2 TF-IDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.3.3 Utilização do score retornado pelo extrator de entidades . . . . . 28
4.4 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
13
1 INTRODUÇÃO
Mensagens divulgadas em sites de mídia social como o Facebook e o Twitter apre-sentam um estilo novo e desafiador para as tecnologias de linguagem devido à sua naturezaruidosa e informal. No entanto, os tweets – postagens feitas na rede social Twitter – forne-cem uma compilação única de informação que, em geral, é mais atualizada e abrangentedo que artigos de notícias, devido à pequena barreira para sua divulgação e a proliferaçãode dispositivos móveis.
É cada vez maior o volume de informação com que o usuário é exposto na Internet.Segundo a pesquisa da Global Information Industry da Universidade da Califórnia em SanDiego [1], o usuário americano comum consome cerca de 34 Gigabytes de informação pordia, consumo que se dá através da TV, rádio, Internet, jogos, etc. Porém muitas dasinformações que são recebidas – principalmente através da Internet – são duplicadas,como por exemplo, notícias que tratam de um mesmo assunto ou evento.
Devido ao enorme volume de tweets publicados cada dia, é impraticável, desneces-sário e à beira do impossível conseguir monitorar o fluxo de dados que é disponibilizadoao usuário. Ferramentas têm sido criadas com o intuito de remover o “ruído social”, osdenominados agregadores de conteúdos como o Flipboard1, TrapIt2 e Zite3, que têm porobjetivo diminuir o número de postagens duplicadas, spams, etc. e formatar a informaçãode modo que fique mais acessível e prazerosa para ser consumida.
O trabalho aqui apresentado encaixa-se no contexto dos agregadores de conteúdos etem por objetivo criar um método que possa determinar a similaridade entre duas históriaspara assim poder agrupá-las. Trata-se da Detecção de Ligação entre Histórias (Story LinkDetection – SLD), um dos itens que pertecem à pesquisa Topic Detection and Tracking,patrocinada pela agência de defesa americana DARPA (The Defense Advanced ResearchProjects Agency), cujo estudo piloto foi realizado entre setembro de 1996 e outubro de1997 [2] e vem sendo discutido desde então.
A proposta é aplicar técnicas de Story Link Detection juntamente com as de Reco-nhecimento de Entidades Nomeadas (Named Entity Recognization – NER) e suas respec-tivas combinações para identificar documentos – aqui chamados de tweets – semelhantes,que tratam do mesmo assunto, na rede social Twitter. Trata-se de uma área com pesquisasrecentes e muitos problemas ainda em aberto, mas que vem ganhando uma notoriedademundial junto com temas como Big Data e Web Semântica. Controlar o ruído social é umobjetivo onde grandes empresas têm investido milhões em pesquisa e desenvolvimento,
1 http://flipboard.com2 http://trap.it3 http://zite.com
14 Capítulo 1. Introdução
mas que ainda é de díficil execução e os resultados muitas vezes não demonstram a qua-lidade esperada.
O trabalho está organizado da seguinte forma: no capítulo 2 é abordado a definiçãodo problema, seu surgimento, suas causas e o objetivo proposto; no capítulo 3 são expostosos conceitos e técnicas utilizados para a resolução do problema; no capítulo 4 é propostauma abordagem para a resolução do problema utilizando conceitos e técnicas apresentadosanteriormente; por fim no capítulo 5 são apresentadas as conclusões obtidas ao fim dosestudos.
15
2 DEFINIÇÃO DO PROBLEMA
2.1 O Twitter
Twitter é um popular site de mídia social que permite aos usuários enviar men-sagens curtas textuais, ou tweets, que possuem o máximo de 140 caracteres. Os usuáriosdo Twitter podem usar um formato de anotação conhecido por hashtag (por exemplo,#SB45) para indicar que o tema ou assunto de suas mensagens estão associadas a um tó-pico (por exemplo, “ver Superbowl 45 #SB45”). Além disso, o Twitter permite a interaçãoentre os usuários utilizando o símbolo @. O Twitter atualmente emprega um algoritmoproprietário para exibir trending topics, consistindo de termos e frases que apresentamcomportamento “tendências” [3].
As mensagens publicadas no Twitter refletem as informações sobre um evento útildentre uma variedade de eventos de diferentes tipos e dimensões. Um evento é definidocomo “algo que acontece em algum tempo e lugar específico” (TDT, 2002) [4]. Estasmensagens podem fornecer um conjunto de perspectivas únicas, que refletem os pontosde vista de usuários que estão interessados ou participam de um evento [3].
Com uma base de usuários de 485 milhões – 288 milhões considerados ativos – noquarto trimestre de 2012 [5] e com uma média de 500 milhões de tweets publicados pordia [6], o Twitter tem transformado a maneira como as pessoas transmitem informações [7].
Dentre as principais características do Twitter, a brevidade, o comprimento curtoe a simultaneidade têm influenciado particularmente no modelo de distribuição de notíciaspelos veículos de informação ao redor do mundo. É comum encontrar um link nas páginasoficiais de grandes portais para seu perfil no Twitter, e muitos de seus editores tambémpossuem perfis pessoais por onde divulgam lançamentos de novas colunas, artigos queacharam interessantes ou opiniões curtam sobre algum novo produto ou serviço.
2.2 A era da sobrecarga de informação
A sobrecarga de informações tornou-se um problema reconhecido na sociedade deinformação intensiva de hoje. É considerado um problema urgente associado à diminuiçãoda satisfação no trabalho, estresse e perda de desempenho [8].
Quando uma pessoa está com excesso de oferta de informações, ou quando aquantidade de informações excede a capacidade cognitiva de um indivíduo, a pessoa éconfrontada com o que os pesquisadores definiram como o “problema da sobrecarga deinformação” [9].
16 Capítulo 2. Definição do Problema
Tarefas baseadas em computador muitas vezes envolvem altas cargas cognitivasque podem estar sujeitos a interferências e interrupções. Uma pesquisa recente descobriuque 50% da administração de empresas da Fortune 1000 “foram interrompidas seis ou maisvezes por hora, deixando-as sobrecarregadas pelo número de mensagens que recebem” [10].
Com o surgimento da Internet e a popularização dos gadgets, como tablets esmartphones, hoje somos interrompidos frequentemente, seja com um novo email, umanova mensagem ou até mesmo com notícias em tempo real. As redes sociais, desde queusadas moderadamente não atrapalham de modo significativo a capacidade produtiva deuma pessoa, mas com as relações, sejam elas sociais, emotivas ou profissionais dependendocada vez mais de tais meios para a comunicação, é quase que impossível não ficar imersoem tal realidade.
2.3 O Twitter como veículo de informação geradorde ruído
Sites de mídia social, como o Twitter, surgiram como poderosos meios de comuni-cação para as pessoas que buscam compartilhar e trocar informações sobre uma grandevariedade de eventos do mundo real [3]. O Twitter é um exemplo extremo de um gêneroinformal, pois os usuários são obrigados frequentemente a abreviar seus posts para quecaibam no limite de 140 caracteres.
Como é possível acompanhar as mais variadas e ilimitadas fontes de notícias atra-vés do recurso de seguir outros perfis, é comum o usuário do Twitter deparar-se com oproblema do ruído informacional. Trata-se de conteúdos duplicados, comumente notíciassobre o mesmo acontecimento que acabam sendo publicadas por diferentes veículos, oumesmo opiniões de outros usuários sobre tal acontecimento ou notícia. O ruído não possuinenhum valor agregado, pois o usuário acaba investindo tempo e energia no processamentode dados que já foram processados e não lhe interessam mais.
Uma das formas que o Twitter encarou este problema foi através da criação deum algoritmo que gera um ranking com têndencias chamado de Trending Topics, ondeatravés da análise em tempo real é gerado uma lista com os assuntos mais comentadosno momento. Porém a identificação de eventos em tempo real no Twitter é um problemadesafiador, devido à heterogeneidade e imensa escala dos dados. Os usuários do Twitterpublicam mensagens com uma variedade de tipos de conteúdo, incluindo atualizaçõespessoais e vários pedaços de informação [3].
Enquanto o Trending Topics do Twitter, por vezes, reflete eventos atuais (porexemplo, “copa do mundo”), muitas vezes inclue palavras-chave para tópicos de conversa-ção populares (por exemplo, “#BieberFever”, “preparando”), sem discriminação entre os
2.4. Objetivos 17
diferentes tipos de conteúdo [3]. Além disso, ele funciona apenas como um classificador enão consegue determinar com precisão ou agrupar tweets que tratam do mesmo assuntosem o uso de palavras-chave específicas ou hashtags.
2.4 Objetivos
Espera-se que os estudos aqui desenvolvidos contribuam com a discussão sobredetecção de textos duplicados, principalmente voltados para os novos meios sociais aosquais os usuários são expostos na Internet, abordando a dificuldade que é lidar com ainformação destes meios, uma vez que suas principais características são a brevidade einformalidade.
Além disto, através deste trabalho é esperado o desenvolvimento de uma soluçãoeficiente que resolva o problema da detecção de tweets duplicados, ou seja, que tratam domesmo assunto. Eficiente aqui possui um duplo sentido: o de qualidade e o de custo com-putacional. Logo, o algoritmo deverá retornar resultados considerados ótimos ou bonsquando comparados com uma classificação manual feita por uma pessoa da área a serabordada, sendo que no escopo deste trabalho será a área de tecnologia. Além disso,o algoritmo deve ser otimizado para a implementação em um ambiente real de produ-ção, fazendo com que o custo computacional dos métodos envolvidos sejam levados emconsideração durante a fase de testes.
É importante destacar que os tweets das fontes escolhidas possuem normalmente otítulo do artigo e um link para o local de publicação original, comumente no próprio site ouportal do veículo em questão. Portanto, será possível analisar não somente os metadadosprovidos pelo Twitter, como também os metadados disponíveis na página original, comonome do autor, data, etc.
Outros objetivos são: melhorar a qualidade da informação que é dirigida ao usuáriopelas das redes sociais, através da aplicação de algoritmos desenvolvidos neste trabalho eo desenvolvimento de um Gold Standard que poderá ser utilizado para futuras pesquisasna área.
19
3 CONCEITOS E TÉCNICAS
3.1 Detecção de Ligação entre Histórias
Detecção de Ligação entre Histórias, conforme definido na competição de Detecçãode Tópicos e Acompanhamento (Topic Detection and Tracking – TDT ) promovida peloprograma DARPA Translingual Information Detection, Extraction, and Summarization(TIDES1), é a tarefa de determinar se duas histórias, tais como artigos de notícias e/ouprogramas de rádio, são sobre o mesmo evento, ou possuem ligação.
A importância da detecção de histórias ligadas reside no seu potencial de criar apli-cações relevantes como o monitoramento de cobertura midiática ou o fluxo de um eventoem particular ao redor do mundo, como a gripe suína, conflitos, derramamento de óleo,etc [11]. Na aplicação da técnica em um sistema já existente seu potencial é de estabalecerfiltros para o controle do volume de informação ao qual o usuário é exposto, eliminandoou agrupando conteúdos que sejam semelhantes facilitando assim o seu processamento.
De acordo com TDT, duas histórias estão ligadas se o evento nelas ocorrem emuma mesma data e local específicos [12]. Logo, uma história que não possue ligações comnenhuma das histórias anteriores deve ser considerada a primeira sobre um novo evento,enquanto que a história que está ligada à alguma das anteriores já reconhecida para umevento deverá ser seguida [13].
Atualmente, o método comumente utilizado para a detecção de ligação entre his-tórias baseia-se na utilização de uma medida de similaridade que leva em consideração asemelhança de cossenos entre vetores de termos com peso TF-IDF [14], onde como termossão utilizadas todas as palavras de um documento.
Para determinar se dois documentos estão vinculados, os sistemas clássicos reali-zam três principais passos de processamento:
1. Pré-processamento para criar um conjunto normalizado de termos para representarcada documento como um vetor de contagem, ou termo vetor;
2. Adaptação dos modelos de parâmetros (isto é, IDF) assim que novas histórias sãointroduzidas, calculando a similaridade dos termo vetores;
3. Determinação se um par de histórias estão ligadas com base na pontuação de simi-laridade [4].
1 http://ciir.cs.umass.edu/research/tides.html
20 Capítulo 3. Conceitos e Técnicas
Foi comprovado em Kumaran and Allan [2005] que usar conhecimento prévio temajudado em tarefas TDT similares à SLD. Uma das possíveis melhorias ao sistema éa utilização de um extrator de entidades nomeadas. Pesquisas realizadas por Shah et al.[2006] e Chen and Ku [2002] sugerem que utilizar o reconhecimento de entidades nomeadaspode levar à uma melhoria na detecção de ligações entre histórias [15]. Portanto, nestetrabalho é proposto que um novo passo de processamento seja executado previamenteaos três citados anteriormente, consistindo exatamente em um reconhecedor de entidadesnomeadas.
3.2 Reconhecimento de Entidades Nomeadas
O Reconhecimento de Entidades Nomeadas (Named Entity Recognization – NER)é geralmente entendido como a tarefa de identificar menções de designadores rígidos apartir de texto pertencentes ao chamado entidade-tipo, tais como pessoas, organizações elocais [16] e estão no centro de muitas das aplicações de mineração de dados.
Abordagens NER dominantes são baseadas em técnicas que por sua vez são basea-das em gramática linguísticas ou em modelos estatísticos. Abordagens NER baseadas emgramática são dependentes de um idioma específico, enquanto abordagens NER estatísti-cas normalmente requerem uma grande quantidade de dados de treinamento manualmenteanotados. Estes métodos NER tradicionais têm sido aplicados em vários domínios, porexemplo, bioquímica (Li et al., 2009), reconhecimento de voz (Meyer e Schramm, 2006),sistemas de informações geográficas (Silva et al., 2006) [17].
Porém, a eficácia das ferramentas existentes é seriamente comprometida quandoaplicado à dados do Twitter, uma vez que as mensagens são concisas, mal redigidas epublicadas em diversos idiomas [18]. Dentre as principais razões para este problema es-tão: tweets contêm uma infinidade de distintos tipos de entidades nomeadas (empresas,produtos, bandas, filmes e outros). Quase todos estes tipos (exceto para pessoas e locais)são relativamente pouco frequentes, e por isso, mesmo com uma amostra grande de tweetsanotados manualmente vão conter poucos exemplos para treinamento; devido ao limitede 140 caracteres do Twitter, tweets muitas vezes não têm um contexto suficiente paradeterminar o tipo de uma entidade sem o auxílio de conhecimento externo ou anterior [19].
Dentre as mudanças necessárias para a adequação do reconhecedor de entidadespara o Twitter, em [19] é proposto uma abordagem distante supervisionada em que éaplicado LabeledLDA (Ramage et al., 2009) para alavancar grandes quantidades de dadosnão marcados junto com grandes dicionários de entidades adquiridos a partir da Freebase,e combinar informações sobre o contexto de uma entidade dentre suas menções. Outraproposta é feita em [16], em que é utilizado um classificador baseado no algoritmo K-vizinhos próximos (K-Nearest Neighbors – KNN ) seguido por métodos de agregação por
3.3. Medidas de similaridade 21
predição (Krishnan and Manning, 2006), como resultados pré-rotulados, junto com outrossistemas NER estado-da-arte.
A ferramenta que foi utilizada para este estudo é a ClearForest SWS, uma fer-ramenta comercial criada pela ClearForest Ltd. e adquirida pela Reuters que permite aanálise de textos em inglês e a identificação de tipos ENAMEX utilizando o processa-mento de linguagem natural (NLP) e aprendizado de máquina dentre outros métodos.Atualmente, ela evoluiu para uma ferramenta chamada OpenCalais, que em meio a ou-tros serviços permite o estabelecimento de relações entre entidades e a detecção de eventoscriando metadados semânticos para o conteúdo enviado em bem menos de um segundo.
Em questão de performance no reconhecimento de entidades, observou-se que asmelhores ferramenta foram o Supersense-WNSS2 e o ClearForest. O ClearForest (Open-Calais)3 se destaca, obtendo uma precisão de 90% [20].
3.3 Medidas de similaridade
3.3.1 TF-IDF e Similaridade de Cossenos
Existem diferentes maneiras de resolver o problema de correspondência entre en-tidades nomeadas, sendo que a mais confiável consiste em estudar as características es-pecíficas dos dados e depois usar qualquer ferramenta disponível para criar um métodoespecializado para a tarefa correspondente. Esta abordagem geralmente leva vantagempela especificidade de linguagem ou de domínio, de quaisquer recursos externos (porexemplo, banco de dados, nomes de dicionários, etc), e de todas as informações sobreas entidades para processar, por exemplo, seu tipo (nome pessoa, organização, etc), ouestrutura interna [21]. A melhor tecnologia para detecção de ligação entre histórias utilizaa similaridade de cossenos entre vetores de termos com pesos TF-IDF para decidir se duasnovas histórias discutem sobre o mesmo assunto [13] [4].
Em um modelo TF-IDF, a frequência de um termo (TF) é ponderada pela frequên-cia inversa de documentos (IDF), o inverso do número de documentos contendo o termo [4].Essencialmente, o TF-IDF funciona determinando a frequência relativa de palavras emum documento específico em comparação com a proporção inversa da palavra ao longo detodo o corpus (conjunto grande e estruturado de textos) do documento. Intuitivamente,esse cálculo determina o quão relevante uma determinada palavra está em um documentoparticular. Palavras que são comuns em um único ou um pequeno grupo de documentostendem a ter uma maior medida TF-IDF do que palavras comuns, tais como artigos epreposições.
2 http://medialab.di.unipi.it/wiki/SuperSense_Tagger3 http://www.opencalais.com
22 Capítulo 3. Conceitos e Técnicas
Assim sendo, o TF-IDF é definido como a combinação do TF e IDF para os pesosdos termos. A combinação de pesos de uma característica 𝑡 em um vetor de documento 𝑑
é dado por
𝑡𝑓𝑖𝑑𝑓(𝑡, 𝑑) = 𝑇𝐹 (𝑡, 𝑑) * 𝐼𝐷𝐹 (𝑡)
onde o 𝑇𝐹 (𝑡, 𝑑) é a frequência da característica 𝑡 no documento 𝑑 e o fator 𝐼𝐷𝐹 de umacaracterística 𝑡 é dado por
𝐼𝐷𝐹 (𝑡) = log 𝑁
𝑑𝑓(𝑡)
onde 𝑁 é o número de documentos no corpus e 𝑑𝑓(𝑡) é o número de documentos quepossui a característica 𝑡.
Como função de similaridade de linha de base foi escolhido a função de cosseno, queé bem conhecida na literatura e uma medida popular de similaridade para text clustering.Trata-se do cosseno do ângulo entre dois vetores e é dado por
𝐶𝑂𝑆(𝑑1, 𝑑2) = 𝑑1𝑑2√︁∑︀𝑖 𝑑2
1𝑖
√︁∑︀𝑖 𝑑2
2𝑖
Uma propriedade forte da similaridade de cossenos é que ela independe do com-primento da palavra: 𝐶𝑂𝑆(𝛼𝑑1, 𝑑2) = 𝐶𝑂𝑆(𝑑1, 𝑑2) para 𝛼 > 0. Isso faz com que ela sejaa medida mais popular para documentos de texto.
3.3.2 Soft TF-IDF
Experiências mostram que medidas baseadas em sequência de caracteres detec-tam somente NE (Named Entity) correferentes que diferem por poucos caracteres. Osmétodos de bolsa de palavras (bag-of-words) se adaptam melhor para o problema de cor-respondência de NE, já que são mais flexíveis à posição e ordem das palavras. Mas muitosdesses pares não são indentificados justamente por pequenas mudanças entre palavras,por exemplo, “Bill Gates” e “Bil Gates”. Por esse motivo, o segundo nível de medidas desimilaridade são relevantes: seu princípio se baseia em aplicar uma sub-medida 𝑠𝑖𝑚′ emtodos os pares de palavras entre duas NE e computar o valor final baseado nestes valores.
O Soft TF-IDF visa precisamente tirar proveito dos bons resultados obtidos no TF-IDF com similaridade de cossenos, sem descartar palavras que não são idênticas. Segue adefinição original encontrada em [21]:
Seja CLOSE(𝜃, 𝑋, 𝑌 ) o conjunto de palavras 𝑤 ∈ 𝑋 tal que exista uma palavra 𝑣 ∈𝑌 que satisfaça 𝑠𝑖𝑚′(𝑤, 𝑣) > 𝜃. Seja 𝑁(𝑤, 𝑌 ) = max(𝑠𝑖𝑚′(𝑤, 𝑣)|𝑣 ∈ 𝑌 ). Para qualquer
3.3. Medidas de similaridade 23
𝑤 ∈ CLOSE(𝜃, 𝑋, 𝑌 ), considere 𝑆𝑤,𝑋,𝑌 = 𝑤𝑒𝑖𝑔ℎ𝑡(𝑤, 𝑋) · 𝑤𝑒𝑖𝑔ℎ𝑡(𝑤, 𝑌 ) · 𝑁(𝑤, 𝑌 ), onde𝑤𝑒𝑖𝑔ℎ𝑡(𝑤, 𝑍) = 𝑡𝑓𝑖𝑑𝑓(𝑤,𝑍)√∑︀
𝑤∈𝑍𝑡𝑓𝑖𝑑𝑓(𝑤,𝑍)2 .
FinalmenteSoft TF-IDF =
∑︁𝑤∈𝐶𝐿𝑂𝑆𝐸(𝜃,𝑋,𝑌 )
𝑆𝑤,𝑋,𝑌
3.3.3 Considerações Finais
Neste capítulo foram apresentados os conceitos e técnicas que serão utilizados nodesenvolvimento de um sistema de ligação entre histórias. Experimentos serão realizadosutilizando os diferentes cálculos de similaridade de modo a definir o que melhor se ajustaa característica do problema em questão.
25
4 PROPOSTA PARA DETECÇÃO DE LIGAÇÃOENTRE HISTÓRIAS COM A UTILIZAÇÃO DERECONHECIMENTO DE ENTIDADES NOME-ADAS
A proposta deste trabalho é executar o reconhecimento de entidades em cadatweet e no texto original disponível através dos links embutidos no mesmo, e utilizar estainformação semântica no processo de reconhecimento e ligação entre histórias. Para oreconhecedor de entidades, foram utilizados sistemas prontos, treinados e utilizados poroutros pesquisadores. Para a detecção de ligação de histórias foram abordadas técnicasreconhecidas na literatura assim como proposto um novo método utilizando um valorsemântico retornado pelo extrator de entidades.
Para a avaliação da eficiência do sistema foi desenvolvido um Gold Standard, con-sistindo em um conjunto de tweets classificados manualmente quanto ao assunto abordadopelo mesmo.
4.1 Gold Standard
Através da API (application programming interface) pública de streaming do Twit-ter foi possível obter em tempo real os tweets das fontes escolhidas, que constituem osprincipais portais e blogs de tecnologia existentes atualmente na Internet, que agrupa-dos produzem uma enorme quantidade de artigos sobre questões ligadas a tecnologia,celulares, startups, etc. e contam com milhares se seguidores cada uma. Tais fontes estãolistadas abaixo:
∙ All Things D (@allthingsd)
∙ Ars Technica (@arstechnica)
∙ CNET News (@CNETNews)
∙ Engadget (@engadget)
∙ Forbes Tech News (@ForbesTech)
∙ GigaOM (@gigaom)
∙ Guardian Tech (@guardiantech)
∙ Mashable (@mashable)
26Capítulo 4. Proposta para Detecção de Ligação entre Histórias com a utilização de Reconhecimento de
Entidades Nomeadas
∙ Read Write Web (@RWW)
∙ Slashdot (@slashdot)
∙ TechCrunch (@TechCrunch)
∙ The Next Web (@TheNextWeb)
∙ The Verge (@verge)
∙ Wired (@WIRED)
Foi desenvolvido um script em Python para o acesso a API e a conexão como banco de dados MySQL. Devido a característica de streaming do Twitter, o scriptficou em execução durante dois dias consecutivos, recebendo um total de 1.007 tweetsdas fontes listadas acima. Cada tweet consiste nos seguintes campos: tweetid, userid,username, screenname, datecreated, url e text.
Após a fase de captação foi criado o Gold Standard, que no contexto desse trabalhoé a classificação manual de cada tweet, e que será utilizado como modelo ótimo paracomparação com testes dos algoritmos. Nesta etapa, foi criado um campo adicional natabela de tweets consistindo em um valor inteiro relativo ao assunto tratado no tweet.Através da análise manual do texto de cada tweet, foi atribuído um número de acordocom o assunto tratado, sendo que números diferentes correspondem a assuntos diferentes,e tweets números iguais correspondem ao mesmo assunto.
Após realizada a classificação manual foi possível perceber que os dados apresenta-vam uma taxa de 23,5% de ruído, ou seja, dos 1.007 tweets recebidos, 236 possuem ligaçãoentre histórias.
4.2 Detecção de Entidades
O reconhecedor de entidades que foi utilizado durante os testes iniciais foi o Stan-ford NER, disponível para download em código aberto1. Stanford NER (também conhe-cido como CRFClassifier) é uma implementação Java de um reconhecedor de entidadesnomeadas que utiliza de modelos sequenciais gerais de cadeia linear de Campo Condicio-nal Aleatório (Conditional Random Field – CRF), juntamente com extratores de recursospara reconhecimento de entidades nomeadas [22].
Porém, através dos conjuntos treinados disponibilizados com o reconhecedor nãofoi possível obter resultados satisfatórios quando utilizados para identificar entidades nostweets, seja pela limitação no reconhecimento de somente três tipos de entidades – pessoa,1 http://nlp.stanford.edu/software/CRF-NER.shtml#Download
4.3. Cálculo de similaridade 27
organização e local – ou pela qualidade em que as entidades foram extraídas, nem semprereconhecendo a totalidade das entidades presentes no texto.
Através de pesquisas, foi identificado em [20] a ferramenta ClearForest (Open-Calais), que obteve uma taxa de precisão de 90% nos testes realizados no artigo e quereconhece mais de 30 entidades. Utilizou-se então o Web Service2 provido pela própriaempresa para a utilização do reconhecedor de entidades.
O Web Service foi consumido através de um script desenvolvido em Python, utili-zando a biblioteca Python-Calais3 e os resultados foram salvos no mesmo banco de dadosem que foi armazenado o Gold Standard, em uma tabela com os seguintes campos: id,idTweet, entityType, value e score.
Após o processamento dos 1.007 tweets pelo reconhecedor de entidades, foramgeradas 3.197 entidades, ou seja, uma média de três entidades por tweet. Os tipos deentidades que mais ocorreram foram: Company, com 692 ocorrências, IndustryTerm com528 e Person com 427.
4.3 Cálculo de similaridade
Para a avaliação dos métodos de cálculo de similaridade foram selecionados 200tweets, sendo que destes, 131 pares possuem ligação entre histórias. Esta seleção foi ne-cessária para diminuir o tempo de execução durante a fase de experimentos.
4.3.1 Soft TF-IDF
Primeiramente foi considerado o método Soft TF-IDF, que se adequaria melhor aoproblema, visto que os tweets apresentam muitos erros de sintaxe, principalmente letrasfora de ordem e abreviaturas. Como a análise neste trabalho foi realizada em cima deentidades nomeadas, e uma vez que através de testes foi detectado que o reconhecedor deentidades ignora totalmente palavras escritas de forma incorreta, não se viu motivos parausar um método mais custoso para o cálculo de similaridade.
4.3.2 TF-IDF
Foram realizados experimentos com o uso do TF-IDF e similaridade de cossenos.Nesta etapa, cada tweet foi considerado como um “documento” e todas as suas entidadesforam adicionadas ao sistema e vinculadas à sua identificação. Realizado o processo paratodos os pares de tweets, os resultados normalizados foram salvos no banco de dados naseguinte forma: idTweet1, idTweet2 e similaridade. A Figura 1 ilustra o processo realizado.2 http://www.opencalais.com/documentation/calais-web-service-api3 http://code.google.com/p/python-calais/
28Capítulo 4. Proposta para Detecção de Ligação entre Histórias com a utilização de Reconhecimento de
Entidades Nomeadas
Figura 1 – Cálculo de similaridade utilizando o TF-IDF
Pré-Processamento Cálculo de Similaridade
Detecção de Entidades TF-IDF
4.3.3 Utilização do score retornado pelo extrator de entidades
Durante a fase de reconhecimento de entitdades utilizando a ferramenta OpenCa-lais foi obtido um valor denominado score para cada entidade. Como se trata de umaferramenta comercial de código fechado, foi necessário pesquisar na documentação oficial4
e nos fórums de suporte5 para encontrar uma definição para tal valor. Segundo [23], acapacidade relevância detecta a importância de cada entidade única e atribui uma pontu-ação de relevância na faixa de 0-1 (sendo 1 a mais relevante e importante). A pontuaçãotem precisão de 3 dígitos e leva em conta a desambiguação de empresas e regiões, para quecada entidade tenha uma única relevância, mesmo que seja referenciada de várias formasao longo do texto.
Através de análises das entidades reconhecidas, foi verificado que o valor de scoredas entidades correspondem ao assunto tratado no texto, como por exemplo, em um tweetsobre o lançamento do PlayStation 4, entidades como Company:Sony e Product:PlayStationobtém um valor maior do que entidades como Currency:USD, todas identificadas nomesmo documento. Devido à tal significado semântico, foi desenvolvido um novo métodocom a proposta de aproveitar o valor do score para detectar ligações entre histórias.
Seja 𝑡1 e 𝑡2 dois tweets, define-se como 𝐸1 o conjunto de entidades nomeadas de 𝑡1
e 𝐸2 o conjunto de entidades nomeadas de 𝑡2. A similaridade é calculada por
𝑠𝑖𝑚(𝑡1, 𝑡2) =∑︁
𝑒1∈𝐸1𝑒2∈𝐸2
𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑐𝑖𝑎(𝑒1, 𝑒2)
onde
𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑐𝑖𝑎(𝑒1, 𝑒2) =
⎧⎪⎨⎪⎩0 se 𝑒1.𝑡𝑦𝑝𝑒 ̸= 𝑒2.𝑡𝑦𝑝𝑒 e 𝑒1.𝑣𝑎𝑙𝑢𝑒 ̸= 𝑒2.𝑣𝑎𝑙𝑢𝑒
𝑒1.𝑠𝑐𝑜𝑟𝑒+𝑒2.𝑠𝑐𝑜𝑟𝑒2 se 𝑒1.𝑡𝑦𝑝𝑒 = 𝑒2.𝑡𝑦𝑝𝑒 e 𝑒1.𝑣𝑎𝑙𝑢𝑒 = 𝑒2.𝑣𝑎𝑙𝑢𝑒
A Figura 2 ilustra o processo realizado neste método.4 http://www.opencalais.com/documentation/calais-web-service-api5 http://www.opencalais.com/forum/3
4.3. Cálculo de similaridade 29
Figura 2 – Cálculo de similaridade utilizando o score
Pré-Processamento Cálculo de Similaridade
Detecção de Entidades Cálculo do score para os pares de tweets
A partir deste ponto foram feitas análises no conjunto de dados com o objetivo deestudar novas abordagens para o problema, ainda utilizando o valor do score no cálculode similaridade.
Primeiramente, foi detectado que existiam vários tweets que possuiam um númeromuito pequeno de entidades. Isso se deve ao fato de o reconhecedor de entidades não serotimizado para tratar este tipo específico de dados, que requer mudanças como propostasna seção 3.2. Foram então eliminados tweets com menos de 𝑥 entidades, sendo 𝑥 = 10 e𝑥 = 5 os valores adotados neste trabalho. O processo é exemplificado na Figura 3.
Figura 3 – Cálculo de similaridade utilizando o score e elimininando tweets com menos de 10 entidades
Pré-Processamento Cálculo de Similaridade
Detecção de EntidadesRemoção de tweets com menos de x entidades
Cálculo do score para os
pares de tweets
Em um segundo ponto de análise, foi identificado que certos tipos de entidadestinham uma maior correlação com o assunto em geral abordado pelos tweets. Como a pro-posta do trabalho é detectar a ligação entre histórias sobre tecnologia, o método originalproposto foi modificado de forma a utilizar somente alguns tipos de entidades, descar-tando todos os outros. Foram consideradas as entidades dos seguintes tipos: Company,IndustryTerm, Person, Position, Technology, Organization, City, Product e Country. Oprocesso está ilustrado na Figura 4.
No terceiro e último ponto de análise dos dados foi detectado que existiam enti-dades que poderíam ter matching parcial quando comparadas com as demais, e que nosoutros métodos as mesmas eram descartadas uma vez que não possuíam um matching to-tal. Como exemplo disto temos entidades como The White House e White House Office,ou ainda Google e Google Images, que apesar de não serem a mesma entidade, possuemum grau de correspondência semântica que pode ser usado na detecção de ligações.
30Capítulo 4. Proposta para Detecção de Ligação entre Histórias com a utilização de Reconhecimento de
Entidades Nomeadas
Figura 4 – Cálculo de similaridade utilizando o score e filtrando pelo tipo de entidade
Pré-Processamento Cálculo de Similaridade
Detecção de EntidadesFiltragem pelo
tipo de entidade
Cálculo do score para os
pares de tweets
Foi então proposto a quebra das entidades em unidades atômicas (palavras), porémpreviamente a isso foi necessário a passagem das entidades por um extrator de stopwords,de modo a eliminar palavras como o The ou of como vistos nos exemplos. Para isso foidesenvolvido um algoritmo em Python utilizando a biblioteca NTLK – Natural LanguageToolkit6 que além de executar a extração de stopwords, divide a entidade em palavras, eatribuí à cada palavra um score cujo valor é determinado por 𝑠𝑐𝑜𝑟𝑒(𝑒)
𝑁, sendo 𝑒 a entidade
não particionada e 𝑁 o número de palavras na qual ela foi dividida. Desta forma foigarantido que em um matching total o valor do score continuaria o mesmo retornado peloextrator de entidades, e que ao remover as stopwords o valor do score seria distribuídoigualmente entre palavras de maior valor semântico.
Outro ajuste realizado na fase de cálculo de similaridade foi a comparação entre aspalavras das entidades com seus plurais, visto que o significado semântico para o problemanão muda com a pluralidade da palavra. Desta forma, uma entidade Apple iPhone e outraiPhones possuem um matching parcial na palavra iPhone/iPhones. A verificação de pluralfoi realizada através da biblioteca Inflect7. A Figura 5 ilustra as etapas que integram estemétodo.
Figura 5 – Cálculo de similaridade utilizando o score, quebra de entidades, remoção de entidades ecomparação com plurais
Pré-Processamento Cálculo de Similaridade
Detecção de EntidadesQuebra de
entidade em palavras
Cálculo do score
utilizando plurais
Remoção das stopwords e
distribuição do score
6 http://nltk.org7 https://pypi.python.org/pypi/inflect
4.4. Experimentos 31
4.4 Experimentos
Na análise dos resultados, foram considerados pares de tweets ligados aqueles cujoambos os tweets continham o mesmo número inteiro que corresponde ao assunto tratadopor eles, assim como descrito na seção 4.1. Uma vez que ambos possuem o mesmo nú-mero de assunto e estão dentro do limite de grau de similaridade estipulado, eles foramcategorizados de forma correta, ou seja, foi realizada a ligação entre as histórias.
Para a avaliação dos resultados foram utilizados dois índices: a precisão e revoca-ção. Precisão é o número de verdadeiros positivos (tweets ligados corretamente) divididopelo número total de tweets retornados (soma de verdadeiros positivos e falsos positivos).Revocação é o número de verdadeiros positivos divido pelo número total de elementos quepertencem a classe positiva (número total de tweets que deveriam ter sido retornados).Formalmente, a precisão e a revocação são definidos por
Precisão = 𝑣𝑝
𝑣𝑝 + 𝑓𝑝Revocação = 𝑣𝑝
𝑣𝑝 + 𝑓𝑛
onde 𝑣𝑝 é o número de verdadeiros positivos, 𝑓𝑝 o número de falsos positivos e 𝑓𝑛 o númerofalsos negativos (resultados que estão faltando no grupo de verdadeiros positivos).
No primeiro experimento foi utilizado o TF-IDF e a Similaridade de Cossenosdescritos na seção 4.3.2 para o cálculo de similaridade, cujo resultados estão dispostos naFigura 6.
Figura 6 – Resultados utilizando o TF-IDF
0.1 0.2 0.30 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
Como é possível notar, a medida em que há o aumento do grau de similaridade, aprecisão aumenta cerca de 10% enquanto que a revocação caí a quase 0%.
32Capítulo 4. Proposta para Detecção de Ligação entre Histórias com a utilização de Reconhecimento de
Entidades Nomeadas
Foi proposta então uma nova abordagem na qual é utilizado o valor do score retor-nado pelo extrator de entidades descrita na seção 4.3.3, cujo resultados são apresentadosna Figura 7.
Figura 7 – Resultados utilizando o score
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
Através do método proposto foi possível observar um aumento da precisão e di-minuição da revocação para graus de similaridade altos, porém é possível notar que paraum grau de 0.2 o método supera o anterior, onde este possui uma precisão de cera de 89%para uma revocação de cerca de 38% e o anterior, que usa o TF-IDF, possue uma precisãode cerca de 43% para 18% de revocação. É indiscutível a melhora do reconhecimento deligações quando utilizado o método proposto comparado ao método que utiliza o TF-IDF.
Uma das modificações propostas para novo método é descrita na seção 4.3.3 econsiste na filtragem dos tweets de modo a excluir os que possuem menos de 5 ou 10entidades. Os resultados desta modificação, com a remoção de tweets com menos de 5entidades estão apresentados na Figura 8 e com a remoção de tweets com menos de 10entidades na Figura 9.
Com a remoção dos tweets com menos de 10 entidades é possível observar umaqueda de cerca de 40% na revocação para graus de similaridade entre 0.1 e 0.2 quandocomparado com o método proposto originalmente enquanto que a precisão tende a semanter a mesma. Isso se deve ao fato de que dentre os tweets com menos de 10 entidades,muitos fazem parte do conjunto que deveriam estar ligados e uma vez que eles são retira-dos, a revocação tende a cair. Já com a remoção dos tweets com menos de 5 entidades nãofoi observada nenhuma mudança na precisão e revocação quando comparado ao métodooriginal.
Uma segunda modificação proposta ao método original e descrita na seção 4.3.3,consiste na filtragem das entidades pelo seu tipo, sendo selecionados apenas os tipos
4.4. Experimentos 33
Figura 8 – Resultados utilizando o score e removendo tweets com menos de 5 entidades
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
Figura 9 – Resultados utilizando o score e removendo tweets com menos de 10 entidades
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
que possuem maior significado para o assunto abordado no trabalho, que neste caso étecnologia. Os resultados dessa modificação são mostrados na Figura 10.
Com a segunda modificação foi possível alcançar uma precisão extremamente alta,com mais de 90% a partir do grau de similaridade 0.2 e atingindo 98% para o grau 0.25.Como é possível notar, para um grau de similaridade de 0.2 foi obtido 91% de precisãopara 54% de revocação, enquanto que no método original para o mesmo grau foi obtido89% e 38%, respectivamente.
Uma última modificação proposta ao método original, descrita na seção 4.3.3, tempor objetivo quebrar entidades em unidades atômicas e usar o plural no cálculo da simi-laridade. Ambas as modificações foram separadas e aplicadas junto com as modificações
34Capítulo 4. Proposta para Detecção de Ligação entre Histórias com a utilização de Reconhecimento de
Entidades Nomeadas
Figura 10 – Resultados utilizando o score com filtragem por tipos de entidades
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
previamente propostas.
No primeiro resultado, apresentado na Figura 11, as entidades são divididas empalavras, é feita a remoção de stopwords e o score é distribuído entre a quantidade depalavras em que cada entidade foi dividida. O processo é realizado em todos os tweets.
Figura 11 – Cálculo utilizando o score, removendo stopwords em todos os tweets
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
Quando comparado este método com o proposto originalmente e apresentado naFigura 7, é possível notar que há um aumento da precisão em cerca de 15% sem diminuiçãoda revocação, para graus de similaridade maiores que 0.2. Este aumento da precisão é ex-plicado pelo matching parcial que ocorre entre as entidades, uma vez que são comparadaspalavra por palavra.
4.4. Experimentos 35
O próximo resultado, apresentado na Figura 12, compreende as mesmas etapasdescritas anteriormente com a inclusão da filtragem por tipos de entidades. A propostaé aplicar a nova modificação à uma outra realizada antes que obteve um bom resultado,como mostrado na Figura 10.
Figura 12 – Cálculo utilizando o score, removendo stopwords e filtrando por tipos de entidades
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
Com a inclusão da quebra de entidades e remoção de stopwords foi possível observarum aumento de 10% a 15% na revocação e a diminuição de cerca de 15% na precisão,comparado a modificação anterior, sem a filtragem de tipos de entidades. Pode-se concluirque a aplicação da modificação, apesar dos benefícios no aumento da revocação, nãodemonstram um bom resultado uma vez levado em conta o custo computacional necessáriopara tais mudanças.
Os últimos resultados a serem apresentados compreendem a adição da comparaçãopor plurais no método original e após a modificação de quebra de entidades e remoção destopwords. Os resultados desta modificação são apresentados na Figura 13 para o métodooriginal, e na Figura 14 para o método modificado.
Pouco se alterou tanto na precisão quanto na revocação com a inclusão da compa-ração com plurais em ambos os métodos. Como é possível observar, somente em algunspontos há uma melhora, como para o grau de similaridade 0.25 onde ambos aumentama precisão em cerca de 4%, porém o comportamento da curva segue o mesmo padrãodos métodos sem a inclusão desta modificação. Estas pequenas mudanças se caracterizampela existência de poucas palavras/entidades na forma plural. Assim como na modificaçãoanterior, os custos computacionais envolvidos não compensam o pouco ganho de precisãoem pontos isolados.
36Capítulo 4. Proposta para Detecção de Ligação entre Histórias com a utilização de Reconhecimento de
Entidades Nomeadas
Figura 13 – Cálculo utilizando o score e fazendo comparações utilizando o plural
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
Figura 14 – Cálculo utilizando o score, removendo stopwords e fazendo comparações utilizando o plural
0.1 0.15 0.2 0.25 0.3 0.350 %
20 %
40 %
60 %
80 %
100 %
Grau de Similaridade
PrecisãoRevocação
37
5 CONCLUSÃO
Nos últimos anos, as redes sociais tornaram-se imensamente populares e muitasdas informações consumidas no dia-a-dia são adquiridas através delas. Com todo essevolume de dados, o usuário tem uma difícil tarefa de filtrar o que realmente é de seuinteresse do que não é.
Conforme os objetivos estabelecidos, este trabalho consiste na tentativa de contro-lar o volume excessivo de informação que é recebido via meios digitais, com enfoque naárea de tecnologia na rede social Twitter.
Atráves de abordagens reconhecidas na literatura, assim como a integração comsistemas estado-da-arte em reconhecimento de entidades nomeadas, foi desenvolvido ummétodo que visa identificar a ligação entre histórias com a utilização de uma medidasemântica retornada pelo detector de entidades. Tal método se provou mais preciso doque a utilização de abordagens clássicas para textos longos, uma vez que no Twitter asmensagens possuem o padrão de serem pequenas (140 caracteres).
Foram feitas modificações no método proposto de modo a melhorar sua eficiência.Algumas modificações melhoraram a precisão e diminuíram a revocação, enquanto outrastiveram efeito contrário. O que se pode concluir através dos experimentos é que este é umproblema que deve ser tratado, assim como a extração de entidades, no nível semântico,e que as propostas apresentadas aqui – que caracterizam o problema como sintático –apesar de obterem bons resultados, ainda não solucionam completamente o problema desobrecarga de informação.
Este trabalho possibilitou um maior contato com a área de Processamento de Lin-guagem Natural, assim como levantar a discussão ao redor do tema dentre a comunidadeacâdemica. Trata-se de um problema de díficil resolução, que envolve a intersecção de áreascomo Banco de Dados, Inteligência Artificial, Text Mining e Big Data dentre outros.
5.1 Trabalhos Futuros
Como trabalhos futuros almeja-se abordar o problema de forma semântica, coma utilização de sistemas de Inteligência Artificial e conceitos de Web Semântica e DataLinking, assim como o desenvolvimento de um sistema em tempo real que implemente asolução.
39
REFERÊNCIAS
1 CENTER, G. I. I. How Much Information? 2009 Report on American Consumers.2009. http://hmi.ucsd.edu/howmuchinfo_research_report_consum.php. [Online;accessed 12-April-2013].
2 ALLAN, J. et al. Topic detection and tracking pilot study final report. In: InProceedings of the DARPA Broadcast News Transcription and Understanding Workshop.[S.l.: s.n.], 1998. p. 194–218.
3 BECKER, H.; NAAMAN, M.; GRAVANO, L. Beyond trending topics: Real-worldevent identification on twitter. In: Fifth International AAAI Conference on Weblogs andSocial Media. [S.l.: s.n.], 2011.
4 CHEN, F.; FARAHAT, A.; BRANTS, T. Multiple similarity measures and source-pairinformation in story link detection. In: In HLT-NAACL 2004. [S.l.: s.n.], 2004. p. 2–7.
5 INDEX, G. W. Twitter The Fastest Growing So-cial Platform. 2013. http://globalwebindex.net/thinking/twitter-the-fastest-growing-social-platform-infographic/. [Online; ac-cessed 12-April-2013].
6 TERDIMAN, D. Twitter hits half a billion tweets aday. 2012. http://news.cnet.com/8301-1023_3-57541566-93/report-twitter-hits-half-a-billion-tweets-a-day/. [Online; accessed 12-April-2013].
7 PHUVIPADAWAT, S.; MURATA, T. Breaking news detection and tracking in twitter.In: Web Intelligence and Intelligent Agent Technology (WI-IAT), 2010 IEEE/WIC/ACMInternational Conference on. [S.l.: s.n.], 2010. v. 3, p. 120–123.
8 JANSSEN, R.; POOT, H. de. Information overload: why some people seem to suffermore than others. In: Proceedings of the 4th Nordic conference on Human-computerinteraction: changing roles. New York, NY, USA: ACM, 2006. (NordiCHI ’06), p. 397–400.ISBN 1-59593-325-5. Disponível em: <http://doi.acm.org/10.1145/1182475.1182521>.
9 HO, J.; TANG, R. Towards an optimal resolution to information overload: aninfomediary approach. In: Proceedings of the 2001 International ACM SIGGROUPConference on Supporting Group Work. New York, NY, USA: ACM, 2001. (GROUP ’01),p. 91–96. ISBN 1-58113-294-8. Disponível em: <http://doi.acm.org/10.1145/500286-.500302>.
10 SPEIER, C.; VALACICH, J. S.; VESSEY, I. Printed in the U.S.A. The Influence ofTask Interruption on Individual Decision Making: An Information Overload Perspective.
11 NOMOTO, T. Two-tier similarity model for story link detection. In: Proceedingsof the 19th ACM international conference on Information and knowledge management.New York, NY, USA: ACM, 2010. (CIKM ’10), p. 789–798. ISBN 978-1-4503-0099-5.Disponível em: <http://doi.acm.org/10.1145/1871437.1871539>.
40 Referências
12 WANG, L.; LI, F. Story link detection based on event words. In: Proceedings of the12th international conference on Computational linguistics and intelligent text processing- Volume Part II. Berlin, Heidelberg: Springer-Verlag, 2011. (CICLing’11), p. 202–211.ISBN 978-3-642-19436-8. Disponível em: <http://dl.acm.org/citation.cfm?id=1964750-.1964768>.
13 BROWN, R. D. Dynamic stopwording for story link detection. In: Proceedings ofthe second international conference on Human Language Technology Research. SanFrancisco, CA, USA: Morgan Kaufmann Publishers Inc., 2002. (HLT ’02), p. 190–193.Disponível em: <http://dl.acm.org/citation.cfm?id=1289189.1289194>.
14 MANNING, C. D.; RAGHAVAN, P.; SCHüTZE, H. Introduction to InformationRetrieval. New York, NY, USA: Cambridge University Press, 2008. ISBN 0521865719,9780521865715.
15 SHAH, C.; CROFT, W. B.; JENSEN, D. Representing documents with namedentities for story link detection (sld). In: Proceedings of the 15th ACM internationalconference on Information and knowledge management. New York, NY, USA: ACM,2006. (CIKM ’06), p. 868–869. ISBN 1-59593-433-2. Disponível em: <http://doi.acm-.org/10.1145/1183614.1183771>.
16 LIU, X. et al. Recognizing named entities in tweets. In: Proceedings of the 49thAnnual Meeting of the Association for Computational Linguistics: Human LanguageTechnologies - Volume 1. Stroudsburg, PA, USA: Association for ComputationalLinguistics, 2011. (HLT ’11), p. 359–367. ISBN 978-1-932432-87-9. Disponível em:<http://dl.acm.org/citation.cfm?id=2002472.2002519>.
17 JUNG, J. J. Online named entity recognition method for microtexts in socialnetworking services: A case study of twitter. Expert Syst. Appl., Pergamon Press, Inc.,Tarrytown, NY, USA, v. 39, n. 9, p. 8066–8070, jul. 2012. ISSN 0957-4174. Disponívelem: <http://dx.doi.org/10.1016/j.eswa.2012.01.136>.
18 OLIVEIRA, D. M. de et al. Fs-ner: a lightweight filter-stream approach tonamed entity recognition on twitter data. In: Proceedings of the 22nd internationalconference on World Wide Web companion. Republic and Canton of Geneva,Switzerland: International World Wide Web Conferences Steering Committee, 2013.(WWW ’13 Companion), p. 597–604. ISBN 978-1-4503-2038-2. Disponível em:<http://dl.acm.org/citation.cfm?id=2487788.2488003>.
19 RITTER, A. et al. Named entity recognition in tweets: an experimental study. In:Proceedings of the Conference on Empirical Methods in Natural Language Processing.Stroudsburg, PA, USA: Association for Computational Linguistics, 2011. (EMNLP ’11),p. 1524–1534. ISBN 978-1-937284-11-4. Disponível em: <http://dl.acm.org/citation-.cfm?id=2145432.2145595>.
20 MARRERO, M. et al. Evaluation of named entity extraction systems. Disponívelem: <http://www.cicling.org/2009/RCS-41/047-058.pdf>.
21 MOREAU, E.; YVON, F.; CAPPÉ, O. Robust similarity measures for named entitiesmatching. In: Proceedings of the 22nd International Conference on ComputationalLinguistics - Volume 1. Stroudsburg, PA, USA: Association for ComputationalLinguistics, 2008. (COLING ’08), p. 593–600. ISBN 978-1-905593-44-6. Disponível em:<http://dl.acm.org/citation.cfm?id=1599081.1599156>.
Referências 41
22 GROUP, T. S. N. L. P. Stanford Named Entity Recognizer (NER). http://nlp.stanford.edu/software/CRF-NER.shtml#About. [Online; accessed 21-October-2013].
23 OPENCALAIS. English Semantic Metadata: Entity Relevance Score. http://www.opencalais.com/documentation/calais-web-service-api/api-metadata/entity-relevance-score. [Online; accessed 25-October-2013].
