Utilizando Medidas de Centralidade na Extração de Palavras-Chave de Grafos Textuais

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

2 abilhoa.willyan@gmail.com

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

3 abilhoa.willyan@gmail.com

Modificações Abordadas

4 abilhoa.willyan@gmail.com

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

5 abilhoa.willyan@gmail.com

6 abilhoa.willyan@gmail.com

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:

7 abilhoa.willyan@gmail.com

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

8 abilhoa.willyan@gmail.com

Novo Funcionamento da Técnica

9 abilhoa.willyan@gmail.com

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

𝑐𝑖𝑘𝑘∈𝑉

Novo Funcionamento da Técnica

Coleção de Documentos (Tweets):

10 abilhoa.willyan@gmail.com

Novo Funcionamento da Técnica

11 abilhoa.willyan@gmail.com

Árvores Geradoras Mínima e Máxima

12 abilhoa.willyan@gmail.com

Árv. Ger. Min. (1): Árv. Ger. Max. (1):

Medidas de Centralidade Utilizadas

13 abilhoa.willyan@gmail.com

Excentricidade: Proximidade

A excentricidade equivale ao complemento da proximidade.

14 abilhoa.willyan@gmail.com

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.