Embed Size (px)
Citation preview
Utilizando Medidas de Centralidade na Extração de Palavras-Chave de Grafos
Textuais
Willyan Daniel Abilhoa Orientador: Prof. Dr. Leandro Nunes de Castro
Laboratório de Computação Natural (LCoN)
Universidade Presbiteriana Mackenzie
Pós-graduação em Engenharia Elétrica
LCoN Meetings
Roteiro
Introdução
Modificações Abordadas
Medidas Anteriores
Antigo Funcionamento da Técnica
Novo Funcionamento da Técnica
Árvores Geradoras Mínima e Máxima
Medidas de Centralidade Utilizadas
Referências Bibliográficas
Introdução
Foco de aplicação da técnica (Twitter):
O Twitter é um serviço de microblog fundado em 2006
É uma rica fonte de informações sobre os mais diversos assuntos.
Isso desperta o interesse tanto do mercado quando da academia
Esse conteúdo está mantido em Tweets
Tweets são mensagens de 140 caracteres
Base de dados textuais:
Cada tweet corresponde a um documento de texto
Os tweets coletados são relacionados ao programa “Agora é Tarde” da
emissora de TV Bandeirantes (Band)
O período de coleta foi realizada entre os dias 6 e 7 de julho de 2012
Modificações Abordadas
Critério Anterior Atual
Janelas de Co-ocorrência
Tamanho 2 Tamanho |D|
Atr. de i V g(i) + f(i) + s(i) g(i), f(i)
Atr. de e E f(i, j) f(i, j), p(i, j), p(j, i)
Orientação Não-Orientação Não-Orientação
Ranking Soma dos pesos de i Centralidade
Medidas Utilizadas:
Medidas de um vértice:
𝑑𝑖 = 𝛽𝑖𝑘
𝑘∈𝐸
|𝛽𝑖𝑘 = 1 𝑠𝑒 𝑖 ∈ 𝑘0 𝑐𝑐
𝑓𝑖 = 𝛼𝑡
𝑡∈𝐿
|𝛼𝑡 = 1, 𝑠𝑒 𝑡 = 𝑡𝑖0, 𝑐𝑐
𝑠𝑖 = 𝑓𝑒𝑘𝑒𝑘∈𝐸𝑖
| 𝐸𝑖 ⊂ 𝐸
𝑤𝑖 = 𝑑𝑖 + 𝑓𝑖 + 𝑠𝑖
𝑓𝑒𝑖𝑗= 𝛾𝑒
𝑒∈𝐸|𝛾𝑒 =
1, 𝑠𝑒 𝑒 = 𝑒𝑖𝑗 𝑜𝑢 𝑒 = 𝑒𝑗𝑖0, 𝑐𝑐
Grau:
Frequência:
Peso Total:
Medidas de uma aresta:
Frequência de Co-
ocorrência:
Soma da Freq.
das Arestas:
Medidas Anteriores
Antigo Funcionamento da Técnica
Passo 1: Passo 2:
L =
p1 day, beautiful,
p2 car, washed,
p3 car, washed, beautiful, day,
p4 drive, car, beautiful, day, car, washed
Passo 3:
• Exemplo de Funcionamento:
Antigo Funcionamento da Técnica
Grafo obtido:
v t f g s w
1 day 3 2 4 9
2 beautiful 3 3 5 11
3 car 4 4 6 14
4 washed 3 2 4 9
5 drive 1 1 1 3
Ranking v T w
1 3 Car 14
2 2 beautiful 11
3 1 day 9
4 4 washed 9
5 5 drive 3
Novo Funcionamento da Técnica
Novas Medidas:
Probabilidade de Transição de (i, j) ∈ E:
Centralidade de Excentricidade de i ∈ V:
Centralidade de Proximidade de i ∈ V:
Sendo: i e j – dois vértices de V cij – a frequência de co-ocorrência de (i, j) S – o conjunto de sucessores de i
𝑃𝑖𝑗 = 𝑐𝑖𝑗
𝑐𝑖𝑘𝑘∈𝑆
𝐸𝑐𝑖 = max𝑘∈𝑉
1 𝑐𝑖𝑘
𝐶𝑙𝑖 =1
𝑐𝑖𝑘𝑘∈𝑉
Medidas de Centralidade Utilizadas
Excentricidade: Proximidade
A excentricidade equivale ao complemento da proximidade.
Referências Bibliográficas
• JIN, W.; SRIHARI, R. K. Graph-based text representation and knowledge
discovery. Proceedings of the 2007 ACM symposium on Applied computing. v. 7,
p. 807-811, 2007.
• Palshikar, G. K. Keyword Extraction from a Single Document using Centrality
Measures. LNCS, p. 503-510, 2007.
