Uma Proposta para CombinarClassificadores e Colaboração de

Usuários na Resolução do Problemade Ambiguidade de Nomes de

Autores

Emilia Alves de SouzaUniversidade Federal de Ouro Preto

UNIVERSIDADE FEDERAL DE OURO PRETO

Orientador: Anderson Almeida Ferreira

Dissertação submetida ao Instituto de CiênciasExatas e Biológicas da Universidade Federal deOuro Preto para obtenção do título de Mestreem Ciência da Computação

Ouro Preto, Setembro de 2014

ii

Uma Proposta para CombinarClassificadores e Colaboração de

Usuários na Resolução do Problemade Ambiguidade de Nomes de

Autores

Emilia Alves de SouzaUniversidade Federal de Ouro Preto

Orientador: Anderson Almeida Ferreira

ii

Catalogação: sisbin@sisbin.ufop.br

S729p Souza, Emília Alves de.

Uma proposta para combinar classificadores e colaboração de usuários na

resolução do problema de ambiguidade de nomes de autores [manuscrito] / Emília

Alves de Souza. – 2014.

86 f.: il. color., grafs., tabs.

Orientador: Prof. Dr. Anderson Almeida Ferreira.

Dissertação (Mestrado) - Universidade Federal de Ouro Preto. Instituto de

Ciências Exatas e Biológicas. Departamento de Computação.

Área de concentração: Ciência da Computação

1. Sistemas de recuperação da informação - Teses. 2. Bibliotecas digitais -

Teses. I. Ferreira, Anderson Almeida. II. Universidade Federal de Ouro Preto.

III. Título.

CDU: 168.35:808.1

CDU: 669.162.16

iii

iv

À minha família, que nos momentos de minha ausência sempre se fizeram presentes e

aos meus amigos, minha segunda família.

v

Uma Proposta para Combinar Classificadores e

Colaboração de Usuários na Resolução do Problema

de Ambiguidade de Nomes de Autores

Resumo

O problema de ambiguidade de nomes em citações bibliográficas tem sido amplamenteestudado principalmente pela comunidade científica de bibliotecas digitais envolvendonomes de autores. Normalmente, os métodos propostos na literatura seguem abordagenssupervisionadas ou não supervisionadas. Os métodos supervisionados são normalmenteos mais efetivos, mas geralmente requerem que uma grande quantidade de exemplossejam manualmente rotulados e, além disso, também não são capazes de resolver aambiguidade para todos os nomes devido a inerente dificuldade do problema. Recente-mente, com o objetivo de melhorar o resultado do processo de desambiguação, algunstrabalhos têm utilizado a colaboração de usuários na desambiguação manual de algunsregistros. Neste trabalho é proposto um método para combinar resultados de técnicassupervisionadas de aprendizado de máquina com a colaboração de usuários para resolvertal problema. Inicialmente, o método explora os atributos dos registros de citações paraagrupar registros que pertençam a um único autor. A partir desses grupos, classifica-dores são combinados para gerar uma função de similaridade que, juntamente com acolaboração do usuário, contribuem para agrupar grupos separados de registros de cita-ções que pertencem a um mesmo autor real. Apesar de usar técnicas supervisionadas, oúnico esforço exercido por parte do usuário é fornecer a sua colaboração desambiguandoalguns nomes de autores. O método foi comparado com outros métodos representativose o ganho em relação a eles atinge cerca de 20% nos resultados de desambiguação.

vi

vii

A Proposal for Combining Classifiers and User

Feedback for Solving the Author Name Ambiguity

Problem

Abstract

The author name ambiguity problem in bibliographic citations has been widely studiedby the scientific community, mostly, about author name ambiguity problem by the di-gital library research comunity. Usually, the methods proposed in the literature followsupervised or unsupervised approaches. The supervised methods are usually the mosteffective ones, but they generally require that a large amount of manually labeled exam-ples and futhermore, they are not capable of solving the author name ambiguity forall names due to its inherent difficulty. Recently, aiming to improve the disambiguationperformance, user feedback have been used in some works. This work proposes a methodto combine results of supervised machine learning techniques along with users feedbackto solve such a problem. Initially, the method exploits attributes present in citations togroup ones with similar author names. From these groups, three classifiers are combinedto produce a similarity function of pairs of records between two groups to, along withusers feedback, group ones that belong to the same author. Although, it uses supervisedtechniques, the only effort applied by the user is to provide feedback for disambiguatingauthor names. We compare our method with other representative ones and our gainsreaches up to 20% in the disambiguation performance.

viii

ix

Declaração

Esta dissertação é resultado de meu próprio trabalho, exceto onde referência explícita éfeita ao trabalho de outros, e não foi submetida para outra qualificação nesta nem emoutra universidade.

Emilia Alves de Souza

x

xi

Agradecimentos

Primeiro gostaria de agradecer ao meu orientador Anderson Almeida Ferreira, queofereceu o tópico de pesquisa para este trabalho e pelo suporte dado durante toda a suaorientação.

Agradeço a todos os professores e membros do Programa de Pós-graduação em Ci-ência da Computação, pelos ensinamentos e apoio durante a minha pesquisa, além daFundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG) pelo incentivofinanceiro.

Aos meus pais, irmãos e toda minha família pela imensa compreensão, paciência eestímulo durante o mestrado.

Além disso, gostaria de agradecer os meus colegas e amigos, que me acompanharame contribuíram de alguma forma para realização deste trabalho.

xii

Sumário

Lista de Figuras xv

Lista de Tabelas xvii

Lista de Algoritmos xix

Nomenclatura 1

1 Introdução 3

1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.1 Objetivo Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3.2 Objetivos Específicos . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.5 Organização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Referencial Teórico 11

2.1 Funções de similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.1.1 Coeficiente de Jaccard . . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.2 Distância de edição . . . . . . . . . . . . . . . . . . . . . . . . . . 13

xiii

xiv SUMÁRIO

2.1.3 Algoritmo de Comparação por Fragmentos . . . . . . . . . . . . . 13

2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3 Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.1 Support Vector Machines . . . . . . . . . . . . . . . . . . . . . . . 15

2.3.2 K-Nearest-Neighbor . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3.3 Random Forests . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3.4 Combinação de classificadores . . . . . . . . . . . . . . . . . . . . 18

3 Trabalhos Relacionados 21

3.1 Métodos baseados em agrupamento de autores . . . . . . . . . . . . . . . 22

3.2 Métodos baseados em atribuição a autores . . . . . . . . . . . . . . . . . 23

3.3 Métodos automáticos de desambiguação que usam colaboração de usuá-rios e combinação de classificadores . . . . . . . . . . . . . . . . . . . . . 24

4 Método proposto 27

4.1 Visão geral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4.2 Passo 1 - Geração de Clusters Potencialmente Puros . . . . . . . . . . . . 28

4.3 Passo 2 - Geração de exemplos de treinamento . . . . . . . . . . . . . . . 32

4.4 Passo 3 - Combinação de classificadores . . . . . . . . . . . . . . . . . . . 34

4.5 Passo 4 - Colaboração dos Usuários . . . . . . . . . . . . . . . . . . . . . 36

4.6 Passo 5 - Fusão de Clusters . . . . . . . . . . . . . . . . . . . . . . . . . 38

5 Resultados e Discussões 39

5.1 Coleções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.1.1 DBLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.1.2 KISTI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

5.2 Métodos representativos . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

SUMÁRIO xv

5.3 Métricas de avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.3.1 Métrica K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.3.2 Métrica PF1 entre pares . . . . . . . . . . . . . . . . . . . . . . . 42

5.4 Configuração experimental . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.5 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.6 Discussões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6 Conclusão 59

6.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

Referências Bibliográficas 61

xvi

Lista de Figuras

1.1 Citações separadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Citações misturadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1 Distância de edição entre nomes de autores . . . . . . . . . . . . . . . . . 13

2.2 Um hiperplano para a classificação de exemplos das classes 1 e 2. Fonte: (Hanand Kamber, 2006) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.3 A classificação de exemplos usando k = 4 para duas classes . . . . . . . . 18

2.4 Fusão de classificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5 Seleção de classificadores. Fonte: (Oliveira et al., 2005) . . . . . . . . . . 20

4.1 Uma visão geral do método proposto . . . . . . . . . . . . . . . . . . . . 28

4.2 Formação e fusão hierárquica dos clusters iniciais . . . . . . . . . . . . . 31

4.3 Seleção de clusters iniciais para a geração dos exemplos de treinamento . 33

4.4 Combinação de múltiplos classificadores . . . . . . . . . . . . . . . . . . . 35

5.1 Comparação entre CCUF e os métodos de referência sob a métrica K naDBLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5.2 Comparação entre CCUF e os métodos de referência sob a métrica pF1na DBLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.3 Comparação entre CCUF e os métodos de referência sob a métrica K naKISTI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

xvii

xviii LISTA DE FIGURAS

5.4 Comparação entre CCUF e os métodos de referência sob a métrica pF1na KISTI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

5.5 Desempenho de CCUF sem a colaboração dos usuários e sem o Passo 5separadamente sob as métricas K e PF1 na coleções DBLP e KISTI . . 55

5.6 Desempenho de CCUF com a rotulagem negativa, sob as métricas K ePF1 na DBLP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.7 Desempenho de CCUF com a rotulagem negativa, sob as métricas K ePF1 na KISTI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Lista de Tabelas

1.1 Coleção de registros de citações do nome ambíguo “A. Gupta” . . . . . . 6

2.1 Atributos dos registros de citações do autor “A. Gupta” . . . . . . . . . . 12

5.1 Resultado (com desvio padrão) da variação dos valores para a constantec na geração do limiar automático %min . . . . . . . . . . . . . . . . . . . 44

5.2 Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração de clusterspuros) para cada grupo ambíguo na DBLP após a formação dos clustersiniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.3 Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração de clusterspuros) para cada grupo ambíguo na DBLP após a fusão hierárquica dosclusters iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.4 Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração de clusterspuros) para cada grupo ambíguo na KISTI após a formação dos clustersiniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.5 Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração de clusterspuros) para cada grupo ambíguo na KISTI após a fusão hierárquica dosclusters iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.6 Resultados (com desvio padrão) obtidos pelo Passo 5(Fusão de clusters)para cada grupo ambíguo na DBLP . . . . . . . . . . . . . . . . . . . . . 48

5.7 Resultados (com desvio padrão) obtidos pelo Passo 5 (Fusão de clusters)para cada grupo ambíguo na KISTI . . . . . . . . . . . . . . . . . . . . . 49

xix

xx LISTA DE TABELAS

5.8 Comparação do desempenho individual dos classificadores para a cole-ção DBLP com o número de instâncias preditas para a classe 1 em cadaclassificador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Lista de Algoritmos

4.1 Formação dos clusters iniciais . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.2 Fusão Hierárquica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.3 Fusão de pares de clusters de registros de citações por Colaboração deUsuários . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

xxi

xxii

Nomenclatura

AAP Average Author Purity

ACP Average Custer Purity

DBLP Digital Bibliography & Library Project

DLs Digital Libraries

GP Genetic Programming

IC Intervalo de Confiança

KNN K-Nearest Neighbor

NER Named Entity Recognition

NB Naïve Bayes

OPF Optimum-Path Forest

PFG Pairwise Factor Graph

pF1 Pairwaise F1

pP Pairwise precision

pR Pairwise recall

RBF Radial Basis Function

RF Random Forests

SAND Self-Training Author Name Disambiguation

SVM Support Vector Machines

1

2

Capítulo 1

Introdução

1.1 Motivação

As divulgações das pesquisas científicas e tecnológicas são fornecidas por meio das pu-blicações científicas. As informações que representam uma publicação específica estãoarmazenadas e disponíveis livremente na Internet, em diversos sistemas. Dentre elesestão a plataforma LATTES1 e as bibliotecas digitais (Digital Libraries - DLs) como aBDBCOMP2, CITESEER3, PubMed4 e DBLP5, que servem como repositórios de dadossobre os pesquisadores e suas publicações científicas, além de oferecer outros serviçosque envolvem o gerenciamento do conteúdo de suas coleções, recuperação e organizaçãoda informação e preservação dos metadados.

Particularmente, as bibliotecas digitais incluem dados e metadados que podem serobtidos de diversas fontes (texto, imagens, som, etc). Os metadados são compostos porum conjunto de atributos que descrevem o conteúdo dos dados e podem ser definidoscomo registros de citações bibliográficas que contém informações sobre: os nomes dosautores, o título do trabalho e o título do veículo de publicação (Borgman, 1999).

O uso desses repositórios de dados tem como objetivo, por exemplo, avaliar a qua-lidade das publicações científicas através do valor de impacto de cada publicação e apartir disso gerar indicadores de produção, pesquisa e influência. No entanto, a evidente

1http://lattes.cnpq.br2http://www.lbd.dcc.ufmg.br/bdbcomp3http://citeseer.ist.psu.edu4http://www.ncbi.nlm.nih.gov/pubmed5http://dblp.uni-trier.de

3

4 Introdução

necessidade do usuário em localizar e selecionar informações de forma rápida e precisa,está longe de ser alcançada, porque os dados coletados de diversas fontes normalmentenão são mantidos de forma consistente e atualizada. Além disso, surgem problemas quepodem dificultar a recuperação de informação nas bibliotecas digitais, entre eles existeo problema da ambiguidade.

1.2 Problema

A ambiguidade é um problema comum inserido em diversos domínios e ocorre na lin-guagem humana quando palavras podem assumir mais de um sentido. No contexto decitações bibliográficas, nomes ambíguos podem causar atribuição indevida de autoria eafetar a qualidade dos serviços oferecidos por bibliotecas digitais.

O problema da ambiguidade de nomes de autores inclui dois subproblemas: citaçõesseparadas (split citation) e citações misturadas (mixture citation) (Lee, 2007). Quandoum autor publica seu trabalho sob diferentes nomes, essas variações de nomes causamo problema das citações separadas, dividindo a sua produção científica. Já o problemade citações misturadas ocorre quando autores distintos podem compartilhar o mesmonome ou abreviações de seus nomes, agrupando as citações de diferentes autores comose elas pertencessem a um único autor.

Na Microsoft Academic Search6 é possível extrair exemplos para o problema da am-biguidade de nomes de autores. A Figura 1.1 mostra o nome do autor “Ashish KumarGupta” submetido a uma busca, sendo retornadas todas as suas citações bibliográficas.Nas citações marcadas estão “A. K. Gupta” e “Ashish Gupta”, dois nomes diferentes parao mesmo autor, caracterizando assim as citações separadas. Já a Figura 1.2 evidenciacitações misturadas, em que a busca pelo nome “A. Gupta” mostra as citações que sereferem aos autores “Arunava Gupta” e “Anil Gupta”, duas pessoas diferentes mas comnomes semelhantes.

O grande desafio é balancear e resolver estes subproblemas ao mesmo tempo. Paraisso, um método automático pode ser aplicado à uma coleção de citações bibliográficasdividindo-as em diversas partições, onde cada partição contém todas e somente todas ascitações de um determinado autor. A definição formal para a tarefa de desambiguaçãode nomes de autores é introduzida por Ferreira et al. (2010) da seguinte forma: C =

6Disponível em http://academic.research.microsoft.com

Introdução 5

Figura 1.1: Citações separadas

Figura 1.2: Citações misturadas

{c1, c2, . . . , ck} é considerada uma coleção de registros de citações onde cada registrocontém ao menos os atributos: nomes de autores, título do trabalho e título do veículode publicação. Cada atributo tem um valor específico que pode ser composto por umalista de elementos. Um elemento do atributo “nomes de autores” é o nome de um únicoautor e é uma referência rj a um autor. Um método de desambiguação deve dividiro conjunto de referências {r1, r2, . . . , rm} em um conjunto de grupos {a1, a2, . . . , an}com o objetivo de ter em cada grupo ai todas (e somente todas) as referências a umdeterminado autor.

Uma coleção com quatro registros de citações {c1, c2, c3, c4}, compreendida na Ta-

6 Introdução

bela 1.1, é um exemplo com os dois tipos de ambiguidade de nomes de autores. Nesseconjunto, cada registro de citação contém uma lista de nomes de autores, onde cadanome é identificado por rj, uma referência a um único autor, e os atributos título dotrabalho e título do veículo de publicação.

Os autores dos registros {c1, c3} têm nomes iguais, mas são pessoas diferentes nomundo real (r3 refere-se ao autor “Anoop Gupta” e r9 refere-se ao autor “Anurag Gupta”),lidando com o problema das citações misturadas. Dos registros de citações {c1, c2} e{c3, c4}, estão autores que dizem respeito à mesma pessoa ({r3, r6} referem-se a “AnoopGupta” e {r9, r12} referem-se a “Anurag Gupta”) mas com nomes diferentes, retratandoo problema de citações separadas. Seguindo a definição, um método de desambiguaçãodeve estabelecer para todo o conjunto de referências {r3, r6, r9, r12} os grupos de autoresaos quais elas pertencem: {r3, r6} ∈ a1 e {r9, r12} ∈ a2, sendo a1 o grupo de referênciasao autor “Anoop Gupta” e a2 o grupo de referências ao autor “Anurag Gupta”.

Tabela 1.1: Coleção de registros de citações do nome ambíguo “A. Gupta”

ID Registro de Citação

c1 High-Speed Implementations of Rule-Based Systems. (r1) A. Newell, (r2) C. Forgy, (r3) A. Gupta. TOCS.

c2 Autmatically extracting highlights for TV Baseball. (r4) Y. Rui, (r5) A. Acero, (r6) Anoop Gupta. ACMMM.

c3 Supply chain agent decision aid system (SCADAS). (r7) L Whitman, (r8) R Agarwal, (r9) A. Gupta. WSC.

c4 A silicon compiler for fault-tolerant ROMs. (r10) K Chakraborty, (r11) P Mazumder, (r12) Anurag Gupta. DFT.

Diversos métodos têm sido propostos na literatura (Ferreira et al., 2012a). Entre osmais efetivos estão aqueles que aplicam técnicas de aprendizado de máquina supervisio-nadas no processo de desambiguação, mas nesses casos o usuário normalmente tem quefornecer uma enorme quantidade de exemplos rotulados manualmente, que exige esforçopor parte do usuário em um processo de alto custo.

Recentemente, alguns trabalhos (Ferreira et al., 2014, 2010; Torvik and Smalhei-ser, 2009) propõem gerar os exemplos de rotulagem automaticamente. E outros méto-dos (Ferreira et al., 2012b; Godoi et al., 2013) incorporam a colaboração (feedback) deusuários no processo de desambiguação para ajudar a resolver o problema, mas todos osmétodos propostos não o resolvem completamente.

Introdução 7

1.3 Objetivos

1.3.1 Objetivo Geral

O propósito desta dissertação é melhorar o processo de desambiguação de nomes deautores em citações bibliográficas. Para isso este trabalho tem como objetivo propor ummétodo que combine classificadores e colaboração de usuários para melhorar o resultadoda desambiguação de registros de citações.

1.3.2 Objetivos Específicos

Considerando o objetivo principal deste trabalho, são apresentados os seguintes objetivosespecíficos:

1. Agrupar citações com nomes de autores similares explorando todos os atributosbásicos presentes nos registros de citações: nomes de autores e coautores, título dotrabalho e do veículo de publicação;

2. Elaborar uma estratégia para combinar os resultados de classificadores para oproblema de ambiguidade de nomes de autores.

3. Usar a colaboração de usuários (administradores) no processo de desambiguação.

4. Comparar o desempenho do método proposto com métodos representativos nadesambiguação de nomes de autores utilizando colaboração de usuários.

1.4 Contribuições

Nesta dissertação, é proposto um método que propõe uma solução para o problema daambiguidade de nomes em registros de citações bibliográficas, combinando os resultadosde diversos classificadores e a colaboração de usuários para aumentar a eficiência doprocesso de desambiguação. O método trabalha em cinco passos.

No primeiro passo os registros de citações são comparados em pares e agrupadosusando atributos discriminativos (similar aos propostos por Ferreira et al. (2014)), queservem como evidências para produzir clusters potencialmente puros, isto é, clusters

8 Introdução

com registros de citações para um único autor real. No segundo passo, alguns destesclusters são selecionados para compor os dados de treinamento, ou seja, seus registrosde citações são usados para produzir os exemplos, para treinar os classificadores.

No terceiro passo, os exemplos de treinamento são usados para treinar um conjunto(ensemble) de classificadores e para combinar seus resultados usando uma simples maseficiente forma de prever se dois registros de citações de clusters diferentes pertencemao mesmo autor. A partir da combinação dos classificadores são calculadas e propostasduas medidas a serem usadas nos próximos passos, para inferir se dois clusters pertencemao mesmo autor. Se este for o caso, os dois clusters são fundidos para formar um únicocluster.

De forma iterativa, os usuários analisam as predições ordenadas através das medidasque foram calculadas, onde a colaboração é definida somente indicando se dois clusterspertencem ao mesmo autor ou a autores diferentes. Somente um registro de citaçãorepresentativo de cada cluster é usado para a decisão final dos usuários. Embora ométodo utilize técnicas supervisionadas, o único esforço exercido pelos usuários é fornecercolaborações, desambiguando registros de citações que estão em clusters diferentes e quenão foram desambiguados automaticamente pelo método.

Apesar de existir uma ampla quantidade de métodos que combinam classificadores(para outros problemas, como resolução de entidades nomeadas) e outros que utilizam acolaboração de usuários (ver Capítulo 3), não foram encontrados na literatura métodospara tratar o problema da ambiguidade utilizando a colaboração de usuários e a com-binação de classificadores como foi feito neste trabalho, por esse motivo são listadas assuas principais contribuições:

1. Uma simples e eficiente regra de combinação (fusão) de classificadores que exploraos rótulos das classes de saída retornadas pelos classificadores individuais.

2. Uma técnica para combinar classificadores com a resposta do usuário que utilizamedidas computadas através do modelo produzido pelo conjunto de classificadores.

Foram realizados experimentos usando duas coleções de registros de citações extraídasda biblioteca digital DBLP e dois métodos representativos baseados na colaboração deusuários. Os resultados obtidos superaram os outros métodos nas coleções avaliadas.Além disso, o método proposto alcança melhor desempenho de desambiguação, usandopoucas intervenções dos usuários se comparado ao melhor método.

Introdução 9

1.5 Organização

O restante desta dissertação está organizada da seguinte maneira. O Capítulo 2 descrevealguns conceitos básicos. O Capítulo 3 discute os trabalhos relacionados. O Capítulo 4descreve o método proposto para desambiguação de nomes de autores e explica as es-tratégias para aumentar a eficiência de desambiguação com a colaboração de usuários.O Capítulo 5 apresenta a avaliação do método através de experimentos. Finalmente oCapítulo 6 conclui o trabalho e sugere possíveis trabalhos futuros.

10

Capítulo 2

Referencial Teórico

Os métodos propostos para automaticamente desambiguar nomes de autores em regis-tros de citações bibliográficas podem ser divididos em métodos baseados em técnicasde aprendizado supervisionadas ou não supervisionadas (Klaas, 2007). Os métodos ba-seados em técnicas não supervisionadas geralmente agrupam os registros de citaçõesusando funções para medir a similaridade entre os registros. Os métodos baseados emtécnicas supervisionadas usam um conjunto de exemplos de treinamento (conjunto detreinamento) para inferir uma função de desambiguação ou de similaridade a ser aplicadasobre os registros ambíguos.

Para facilitar o entendimento da descrição do método proposto, são descritos, aseguir, os conceitos pertinentes à técnicas de aprendizado de máquina relacionados aeste trabalho. Inicialmente, na Seção 2.1, são descritas algumas funções de similaridade.A Seção 2.2 descreve o processo de clustering. Finalmente, na Seção 2.3, é descrito oprocesso de classificação.

2.1 Funções de similaridade

Para verificar a relação (similaridade) entre dois registros de citações, pode-se usar asimilaridade, calculada por meio de funções, entre os seus atributos. Desse modo, cadaum dos atributos são comparados individualmente. Para se comparar os quatro registrosde citações da Tabela 2.1, pode-se verificar por exemplo, a similaridade entre os nomesde autores (Cohen et al., 2003).

11

12 Referencial Teórico

Tabela 2.1: Atributos dos registros de citações do autor “A. Gupta”ID Nomes de autores Título de publicação Título do Veículo de

publicaçãoc1 A. Newell, C. Forgy,

A. Gupta.High-Speed Implementations ofRule-Based Systems.

TOCS

c2 Y. Rui, A. Acero,Anoop Gupta

Autmatically extracting high-lights for TV Baseball.

ACMMM

c3 L Whitman, RAgarwal, A. Gupta.

Supply chain agent decision aidsystem (SCADAS).

WSC

c4 K Chakraborty, PMazumder, AnuragGupta.

A silicon compiler for fault-tolerant ROMs.

DFT.

Uma função de similaridade aplicada sobre dois valores normalmente retorna umvalor entre 0 e 1 indicando o grau de similaridade entre os dois valores, onde 0 indicaque os dois valores são totalmente diferentes e 1 que os dois valores são iguais. A seguir,são descritas algumas funções de similaridade consideradas neste trabalho.

2.1.1 Coeficiente de Jaccard

O coeficiente de Jaccard (Levandowsky and Winter, 1971) é uma função que calcula asimilaridade entre dois conjuntos, mostrada na Equação 2.1:

J(A,B) =|A ∩B||A ∪B|

(2.1)

Seja A = {Anoop,Gupta} o conjunto de palavras do primeiro autor e B = {Anurag,Gupta} o conjunto de palavras do segundo autor, o coeficiente de Jaccard, 0.3333334,é referente à razão (1

3) do número de palavras na interseção dos dois conjuntos, que

é unicamente o sobrenome de ambos os autores “Gupta”, pelo número de palavras daunião, formado pelas três palavras “Anoop, Anurag, Gupta”.

Referencial Teórico 13

2.1.2 Distância de edição

Também chamada de distância de Levenshtein (Levenshtein, 1966), corresponde ao nú-mero mínimo de operações para converter uma cadeia de caracteres (string) em outra.As operações típicas de conversão são: inserção, remoção, substituição e cópia, quecarregam pesos (custo 1, exceto cópia que tem custo 0) para cada transformação. NaFigura 2.1, o número mínimo de transformações admitidas entre os nomes de autores“Anurag Gupta” e “Anoop Gupta” é quatro. Para seguir o padrão das funções de simi-laridade, dentro do intervalo de 0 e 1, a distância de edição é normalizada pelo tamanhoda maior string subtraído por 1 . No exemplo, doze é o tamanho da maior string dadopor “Anurag Gupta” (incluindo o espaço em branco), pela normalização têm-se a razão412

= 0.3333334 e o resultado final 1− 0.3333334 = 0.6666667.

a n u r a g _ g u p t a

| | | | | | | |

a n o o p _ g u p t a

0 0 1 1 1 1 0 0 0 0 0 0

Figura 2.1: Distância de edição entre nomes de autores

2.1.3 Algoritmo de Comparação por Fragmentos

Oliveira (2005) propôs um algoritmo para comparar fragmentos de palavras utilizandoa função de distância de edição. Assim, como o coeficiente de Jaccard, os fragmentos sãopalavras que representam as partes dos nomes separados por espaços em branco. Nessecaso, dois nomes são similares se possuem pelo menos as mesmas iniciais do primeironome e o mesmo último sobrenome (a distância de edição computada entre os fragmentosdeve ser menor que um limiar).

Por exemplo, os nomes “A. Gupta” e “Anurag Gupta”, que podem referenciar o mesmoautor, quando comparados usando o coeficiente de Jaccard e a distância de edição re-tornam os valores 0.3333334 e 0.5833334, respectivamente. Os valores retornados nãoindicam uma alta proximidade entre os nomes, já com o algoritmo comparação porfragmentos, o valor retornado será verdadeiro, uma vez que os dois nomes possuem asmesmas iniciais do primeiro nome e o mesmo último sobrenome.

14 Referencial Teórico

2.2 Clustering

Nos algoritmos de agrupamento (ou clustering) o objetivo é dividir um conjunto deobjetos (dados) em subconjuntos (grupos) disjuntos, maximizando a intra-similaridade eminimizando a inter-similaridade, isto é, os objetos de um mesmo grupo (cluster) devemser similares, ao passo que objetos de grupos distintos devem ser dissimilares. Clusteringé um tipo de aprendizado não-supervisionado no qual a análise sobre o conjunto de dadosnão necessita de supervisão. Deste modo, clustering pode ser usado para descobrircategorias (classes) de um conjunto de dados, em que cada cluster formado é visto comouma classe que representa aqueles dados (Han and Kamber, 2006).

Um algoritmo de clustering hierárquico aglomerativo, por exemplo, pode obter dosregistros de citações de autores ambíguos “A. Gupta”, como os da Tabela 2.1, 2 clusterscorrespondendo à diferentes pessoas no mundo real. Cada cluster inicial contém somenteum registro de citação e são sucessivamente fundidos, de acordo com alguma medida desimilaridade até uma condição ser atingida (por exemplo, nomes dos autores similarese pelo menos um coautor similar), idealmente tendo todos os registros de citações paraum mesmo autor em um só cluster. Existem vários algoritmos de clustering na lite-ratura (Jain and Dubes, 1988). No entanto, eles nem sempre geram clusters corretos,uma vez que sem o intermédio de um método supervisionado que forneça exemplos cominformações sobre as classes dos dados, pode não ser possível entender o que os clustersencontrados representam.

2.3 Classificação

A tarefa de identificar objetos e atribuí-los a uma classe conhecida a priori por um con-junto de exemplos rotulados é definida como aprendizagem supervisionada ou simples-mente classificação. A classe, ou seja, o rótulo, determina o significado (a semântica) doobjeto. Métodos supervisionados exigem uma quantidade de exemplos rotulados (con-junto de treinamento) para treinar um classificador e gerar um modelo (ou função) capazde prever as classes de um conjunto de dados , onde as classes são desconhecidas (Wittenand Frank, 2005). Contudo, adquirir exemplos de treinamento pode tornar-se um pro-cesso inviável e, além disso, a aprendizagem é cara e demorada se o conjunto de treinocontém volumes enormes de dados. Uma alternativa é empregar métodos que exploramambos dados não rotulados e rotulados usando clustering para classificação.

Referencial Teórico 15

No contexto de registros de citações, os classificadores podem construir uma funçãode desambiguação que representa os autores de cada registro ou aprender uma funçãode similaridade entre os atributos dos registros para agrupar os mais similares. Usandouma função de desambiguação, os registros de citações apresentados pela Tabela 2.1, sãodiretamente atribuídos aos respectivos autores, utilizando um modelo obtido por meiode exemplos (instâncias) com registros de citações em que o autor correto é conhecido.Cada exemplo é composto por um conjunto de características e um rótulo, em que orótulo representa um autor para cada registro de citação. Ao treinar o classificador comos exemplos de treinamento, uma função de desambiguação que mapeia o conjunto decaracterísticas para o conjunto de rótulos, é aprendida e usada para prever os autorescorretos para outros registros de citações no conjunto de teste onde as característicassão conhecidas mas os autores não.

É possível ainda construir um modelo para calcular a similaridade entre os registrosde citações. Para os registros da Tabela 2.1, um algoritmo de clustering produz clusters,que podem ser utilizados para construir uma função de similaridade específica, a partirda comparação entre registros de um mesmo cluster (classe 1 - mesmo autor) e entreclusters distintos (classe 0 - autores distintos). Pode-se usar um vetor de característica,juntamente com um rótulo, para representar cada comparação. Cada característica éa relação entre os atributos de dois registros de citações gerados por outras funçõesde similaridade (ex: nome de autor é 1.0 dado pelo coeficiente de Jaccard) ou algumaheurística. O rótulo indica a classe, que se o par de registros de citações pertencem aomesmo cluster significa que eles são do mesmo autor; senão, são de autores diferentes.Dessa forma, os exemplos de treino são gerados automaticamente pelo algoritmo declustering e a função de similaridade aprendida serve para classificar os clusters e garantirque estejam corretos.

SVM, KNN e RF são exemplos de classificadores propícios em gerar um modelo paraaprender tanto uma função de similaridade quanto uma função de desambiguação. Elestrabalham de formas diferentes para gerar modelos específicos que são combinados nestetrabalho. As próximas subseções descrevem os classificadores individualmente e umaúltima subseção descreve o processo de combinação de classificadores.

2.3.1 Support Vector Machines

Seguindo a teoria de aprendizagem estatística, Máquinas de Vetores de Suporte (Sup-port Vector Machines - SVM (Cortes and Vapnik, 1995)) representam os exemplos do

16 Referencial Teórico

conjunto de treinamento como pontos em um espaço dimensional, mapeados por meiode suas características. Então, é traçado um hiperplano (ou fronteira de decisão) quesepara todos os pontos através de margens associadas (linhas paralelas) que determinama qual lado (classe) cada ponto pertence, esse processo é chamado de separação ou clas-sificação linear. Os pontos no limite que estão, sob ou bem próximos às margens entreas classes servem como suporte, chamados vetores de suporte, para que o hiperplanoseja desenhado no espaço. Um exemplo pode ser visualizado na Figura 2.2, cujos pontoscorrespondendo às classes 1 e 2 estão distribuídos no espaço de características.

F(n)

F(n+1)

vetores de suporte

Margem

Margem

Hiperplano

classe 1

classe 2

Figura 2.2: Um hiperplano para a classificação de exemplos das classes 1 e 2. Fonte: (Hanand Kamber, 2006)

O objetivo é encontrar o hiperplano de separação ótima que minimiza o erro declassificação (alta generalização) para os novos pontos, ainda não vistos, do conjunto deteste. Por isso, a ideia é maximizar a distância entre as margens e os pontos, mas manteriguais as distâncias para cada classe. Um hiperplano com máxima margem nem semprepode ser obtido quando os dados não são linearmente separáveis. Em tais casos, umafunção kernel calcula os vetores de suporte para cada um dos pontos para em seguidaprojetá-los em uma alta dimensão onde os dados se tornam linearmente separáveis.Depois, o processo mapeia no mesmo espaço os pontos do conjunto de teste utilizandoa função de decisão, mostrada na Equação 2.2, que encontra o hiperplano com máximamargem e mapeia o novo ponto no espaço em que sua classe é atribuída em função dequal lado do hiperplano o ponto está posicionado.

Referencial Teórico 17

f(XT ) =l∑

i=1

yiαiK(Xi, Xj) + b (2.2)

ondeXT é um dado do conjunto teste, l é o número de vetores de suporte, yi é o rótulo daclasse do vetor de suporte, αi e b são os parâmetros encontrados durante o treinamento,e K(Xi, Xj) é a função kernel que calcula o produto do dado do conjunto de teste paracada um dos vetores de suporte.

2.3.2 K-Nearest-Neighbor

Os K -vizinhos mais próximos (K-Nearest-Neighbor - KNN (Altman, 1992)) são classifi-cadores baseados em instâncias, onde todo o aprendizado é essencialmente dependentedos exemplos de treinamento. Cada exemplo representa um ponto no espaço de n dimen-sões, que corresponde ao número de características, sendo todos os exemplos de treinoarmazenados até classificar um objeto desconhecido do conjunto de teste. Na classi-ficação, o novo objeto é mapeado no espaço e o classificador busca pelos k exemplosde treino (vizinhos) que estão mais próximos. A proximidade é determinada por umamedida de distância entre os pontos, a mais utilizada é a distância Euclidiana 2.3, quecalcula a diferença entre os valores dos pontos dispostos no espaço de características. Aclasse do novo objeto é atribuída pelo voto majoritário dos rótulos da classe dos vizinhosmais próximos.

d(X, Y ) =

√√√√ n∑i=1

(xi − yi)2 (2.3)

O problema do classificador é escolher um bom valor para k, pois a classificação podemudar de acordo com o seu valor. Quanto maior o número de exemplos de treinamentomaior será o valor de k. Se o valor for muito pequeno a classificação pode ser dependentede pontos ruidosos, aqueles que são exceção e não seguem a mesma distribuição (padrão)dos pontos em geral, já se o valor for muito grande a vizinhança pode incluir elementosde outras classes. Na Figura 2.3, a classificação de uma nova instância é mostradatomando k = 4. Nesse caso, o rótulo da classe da maioria dos pontos vizinhos ao novo

18 Referencial Teórico

ponto atribuído é a classe 2.

F(n)

F(n+1)

classe 1

classe 2

Figura 2.3: A classificação de exemplos usando k = 4 para duas classes

2.3.3 Random Forests

Random Forests - RF (Breiman, 2001) é a combinação de uma coleção de classificadoresestruturados por árvores de decisão (florestas), que são construídas por amostras ale-atórias do conjunto de treinamento. Dado D o conjunto de exemplos de treinamento,cada árvore é cultivada por uma amostra aleatória Di do conjunto de treinamento, emque Di é construído de forma independente mas com a mesma distribuição para todasas árvores na floresta. Dado F o conjunto de características, o classificador selecionaaleatoriamente em F as característica candidatas para dividir o nó de cada árvore, ondecada nó recebe um novo subconjunto de características Fi. Durante a classificação, umanova instância é submetida a cada árvore que vota pela classe mais popular, sendo estaatribuída à nova instância.

2.3.4 Combinação de classificadores

Combinação de múltiplos classificadores, também conhecida como conjunto (ensemble)de classificadores, tem sido abordada por diferentes métodos para aumentar o poderda classificação. Há duas estratégias principais amplamente aceitas para esse tipo detécnica: fusão e seleção de classificadores (Kuncheva, 2004). Na fusão, classificadores

Referencial Teórico 19

paralelos devem cobrir todo o espaço de características em que cada classificador pro-duz uma saída (rótulo da classe ou valor contínuo), que são fundidas usando diferentesfunções. Na seleção, supõe-se que cada classificador conhece bem uma região local noespaço de características e é perito somente por esta parte do espaço, onde um conjuntodesses classificadores são combinados em série e um único classificador é selecionado. Emrelação ao esquema de combinação, os quatro níveis de saída são distinguidos de acordoà informação obtida dos classificadores individuais, que são: abstrato (rótulo da classe),hierárquico (lista de possíveis classes de saída), probabilidade (lista de probabilidadesdas possíveis classes) e óraculo (decisão correta ou errada).

Especificamente, a estrutura paralela para a fusão de classificadores pode ser visua-lizada na Figura 2.4, e as regras de fusão mais utilizadas são: voto majoritário, soma,produto, média, mínimo e máximo. No voto majoritário, os rótulos da classe, defini-dos individualmente pelos classificadores, são levados em consideração e aquele que temmaior número de votos é atribuído à nova instância. Faz-se o uso das regras de soma,produto e média para as probabilidades das classes de cada classificador e a classe cujoresultado de alguma das operações for o mais elevado, é declarada vencedora. O mí-nimo e máximo são regras de decisão simples, onde a classe com a menor e a maiorprobabilidade respectivamente é a vencedora.

.

.

.

Fusão classefinal

C 2

C1

Cn

Figura 2.4: Fusão de classificadores

Por outro lado, a estrutura serial para a seleção de classificadores pode ser vista naFigura 2.5, sendo que as combinações possíveis dos classificadores, servem para a re-dução e re-avaliação das classes. Cada classificador fica responsável por uma parte do

20 Referencial Teórico

espaço de características, a Saída indica o nível de confiança (probabilidades) das classescandidatas, se este for baixo a classe é descartada e um outro classificador é chamado, asRejeições indicam as probabilidades das classes descartadas pelo classificador anteriorque são re-avaliadas pelo classificador atual. Assim, assume-se que na seleção de classi-ficadores há um oráculo que decide qual o melhor classificador para o dado de entradaespecífico.

.

.

.

classefinal

C 2

C1

Cn

Saída

Saída

Rejeição

Rejeição

Saída

Figura 2.5: Seleção de classificadores. Fonte: (Oliveira et al., 2005)

Capítulo 3

Trabalhos Relacionados

Uma organização hierárquica dos diversos métodos é proposta por Ferreira et al. (2012a)em uma nova taxonomia baseada nos tipos de técnicas (agrupamento e atribuição aautores) ou nas evidências exploradas (atributos das registros de citações, informaçãoda Web ou dados implícitos). Os trabalhos que se concentram no primeiro grupo sãodivididos em duas categorias: (i) agrupamento de autores tenta colocar os registros decitações que contém atributos similares em um mesmo grupo e (ii) atribuição a autoresvisa atribuir diretamente os registros de citações a seus respectivos autores.

Ambas as abordagens podem utilizar técnicas de aprendizado de máquina (super-visionadas ou não supervisionadas) tanto para definir funções de similaridade ou dedesambiguação, quanto para agrupar as citações do mesmo autor real. O segundo grupoé dividido em três categorias de acordo com os tipos de informações extraídas sobre aspublicações: evidências das citações (as mais comuns são: nomes de autores, título dotrabalho e do veículo de publicação), evidências de páginas da Web (informações cole-tadas por uma busca na Web) ou evidências implícitas (são inferidas através de técnicasque exploram as evidências das citações).

Como este trabalho se insere no primeiro grupo da taxonomia, as seções a seguir irãomostrar os principais métodos em desambiguação de nomes de autores relacionados aoprimeiro grupo e suas duas categorias. As Seções 3.1 e 3.2 apresentam os métodos queabordam o agrupamento e a atribuição de autores, respectivamente. A Seção 3.3 descreveos novos métodos automáticos que usam a colaboração de usuários para aumentar odesempenho de desambiguação, além de trabalhos relacionados ao uso de conjunto declassificadores.

21

22 Trabalhos Relacionados

3.1 Métodos baseados em agrupamento de autores

Nesses métodos, alguma técnica de clustering é utilizada junto com uma função de si-milaridade para resolver o problema da ambiguidade de nomes de autores agrupandoregistros de citações de um mesmo autor. A função de similaridade pode ser (i) pre-definida, baseada em funções existentes e aplicadas sobre os atributos (Bhattacharyaand Getoor, 2007; Carvalho et al., 2011; Cota et al., 2010; Han et al., 2005b; On andLee, 2007; Soler, 2007), (ii) aprendida usando alguma técnica de aprendizado de má-quina supervisionada (Culotta et al., 2007; Huang et al., 2006; Levin et al., 2012; Torvikand Smalheiser, 2009), ou (iii) extraída de relacionamentos entre autores e coautores,normalmente representados como um grafo (On et al., 2006).

Alguns trabalhos (Bhattacharya and Getoor, 2007; Carvalho et al., 2011; Cota et al.,2010) exploram funções de similaridade predefinidas (Jaccard, TFIDF, Jaro, Jaro-Winkler,Comparação por Fragmentos-Levenshtein, distância do cosseno, entre outras) para osatributos mais básicos dos registros de citações, que são usados por um algoritmo declustering aglomerativo a fim de agrupar os registros com nome de autor similar e umou mais coautores em comum.

Outros (Han et al., 2005b; On and Lee, 2007) são caracterizados por utilizar méto-dos de clustering que representam os registros de citações como vértices de um grafoconectado e o peso das arestas é dado pela similaridade do cosseno e TFIDF entre osatributos dos registros. Soler (2007) apresenta uma nova função de similaridade baseadanas probabilidades calculadas usando os atributos: nomes de autores, e-mail, endereço,palavras-chaves, campo de pesquisa, nomes de veículo e ano da publicação.

Dos métodos que seguem abordagens supervisionadas para aprender uma função desimilaridade a partir de características dos registros de citações, vale destacar Culottaet al. (2007), que considera todas as características da coleção (ao contrário de pares deregistros de citações) para aprender um score baseado em ranking, em que os scores notopo indicam as desambiguações corretas.

Torvik and Smalheiser (2009) exploram os algoritmos de clustering para gerar auto-maticamente os exemplos de treinamento que são usados para aprender uma função einferir se dois registros de citações pertencem ou não ao mesmo autor. Levin et al. (2012)usam conjunto de regras para produzir clusters de registros de citações do mesmo au-tor gerados para produzir automaticamente exemplos de treinamento fornecidos a umclassificador logístico para inferir uma função de similaridade entre os clusters que são

Trabalhos Relacionados 23

fundidos por um algoritmo aglomerativo.

Huang et al. (2006) usam algoritmo DBSCAN para agrupar os registros de citaçõessimilares. A similaridade é definida pelo classificador LASVM que aprende através devetores de características, onde cada característica é definida pelas funções de simila-ridade TFIDF, Jaccard e Levenshtein para os atributos nomes de autores, endereço,afiliação, e-mail e da página da publicação.

On et al. (2006) propõem um método baseado em grafo que usa a informação decoautoria para agrupar citações dos mesmos autores, de modo a representar cada vérticecomo o nome de um autor e cada aresta uma coautoria entre dois autores. Então ométodo encontra a distância quasi-clique entre dois vértices que é usada como medidade similaridade entre os nomes de autores.

3.2 Métodos baseados em atribuição a autores

Esses métodos tentam resolver o problema atribuindo diretamente as citações aos seuscorrespondentes autores usando técnicas de classificação supervisionada (Ferreira et al.,2010; Han et al., 2004; Veloso et al., 2012) ou técnicas de clustering baseado em mo-delos (Han et al., 2005a). Tais métodos inferem modelos que representam os autores(por exemplo, a probabilidade de um autor publicar um artigo com outros autores, emum dado veículo de publicação e usando uma lista de termos específicos no título dotrabalho).

Han et al. (2004) usam características comuns dos registros de citações para comporos vetores de características. Os vetores derivam um modelo de desambiguação que éusado para atribuir os registros. O modelo é aprendido pelo classificador Naïve Bayes(NB) que usa somente exemplos positivos para aprender os padrões de escrita dos re-gistros de citações, e o SVM que requer tanto exemplos positivos quanto negativos paraaprender a representar um autor.

Veloso et al. (2012) propõem um sistema que aprende a prever autores corretos paraos registros de citações através de um classificador baseado em regras de associação. Oclassificador aprende uma função de desambiguação que associa um conjunto (vetor) decaracterísticas dos registros de citações a um autor específico. Esse método foi estendidopor Ferreira et al. (2010) para reduzir o custo na geração dos exemplos de treinamento.Ao criar clusters potencialmente puros, contendo registros de citações para um mesmo

24 Trabalhos Relacionados

autor, somente os mais dissimilares são selecionados para o conjunto de treino. Os re-gistros dos clusters restantes são classificados pela função de desambiguação aprendidabaseada nas regras que associam os exemplos de treinamento produzidos automatica-mente e os autores corretos.

Han et al. (2005a) apresentam uma versão hierárquica não supervisionada do métodoNB para aprender o modelo que representa cada autor. A probabilidade P (cj|ai) de umregistro de citação cj pertencer a um determinado autor ai é definida de forma hierárquicaatravés de cada atributo dos registros.

3.3 Métodos automáticos de desambiguação que usam

colaboração de usuários e combinação de classi-

ficadores

Colaboração de usuários tem sido incorporada por alguns métodos (Ferreira et al., 2012b;Godoi et al., 2013; Li et al., 2011; Wang et al., 2011) juntamente com técnicas de apren-dizado de máquina para aprender uma função de desambiguação e, consequentemente,aumentar os resultados do processo de desambiguação.

Ferreira et al. (2012b) acrescentam a colaboração dos usuários ao sistema SAND (Fer-reira et al., 2010), visto na Seção 3.2, como um desambiguador de nomes de autores quetrabalha em dois passos. No primeiro passo, os registros de citações são agrupados emclusters usando a relação de coautoria e seleciona alguns destes clusters cujos registrosde citações serão usados como exemplos de treinamento iniciais para um próximo passo.Os registros restantes irão compor o conjunto de teste. No segundo passo, um clas-sificador associativo, que é capaz de detectar novos autores (ou seja, novas classes), éusado. Inicialmente, o classificador seleciona um percentual de predições duvidosas, ouseja, predições em que o método não é capaz de afirmar a autoria correta, e solicitaaos usuários que as atribuam aos autores corretos. Depois, as predições com autorescorretos são inseridas no conjunto de treinamento e usadas para prever os autores dascitações do conjunto de teste.

O método proposto por Godoi et al. (2013), detecta nomes ambíguos combinandoProgramação Genética (GP) e classificador de Florestas de Caminhos Ótimos (OPF )com a colaboração de usuários. Godoi et al. (2013) usam o GP para aprender funções de

Trabalhos Relacionados 25

similaridade e o OPF para rotular os registros de citações. O classificador OPF modela oproblema como um problema de partição em grafo e usa funções de similaridade geradaspelo GP para fornecer os pesos das arestas. O método seleciona um número fixo deregistros de citações que são os mais duvidosos rotulados pelo OPF e em uma formaiterativa, pede aos usuários os rótulos corretos (autores).

Li et al. (2011) propõem um classificador Perceptron baseado em restrições que in-corpora a colaboração de usuários com um conjunto de características extraídas de cadapar de registros de citações. Primeiro, as características são usadas como entrada parao treinamento do classificador. Depois, os autores usam a função de similaridade apren-dida pelo classificador para desambiguar os registros. E, finalmente, quando os usuáriosencontram qualquer erro resultante do processo de desambiguação, eles os corrigem. Ascorreções são retornadas como novas características para melhorar o modelo de classifi-cação.

Wang et al. (2011) propõem ADANA (Active Name Disambiguation) um sistemade desambiguação ativa de nomes. Os autores formalizam o modelo de desambiguaçãodefinido em grafo de fator pareado (Pairwise Factor Graph - PFG), com o objetivo deassociar automaticamente pares de registros de citações da mesma pessoa. Baseado nosresultados de desambiguação obtidos pelo modelo PFG, um algoritmo de desambiguaçãoativa escolhe pares de registros de citações, denotados como os mais incertos, de modo aperguntar para os usuários quais artigos pertencem ao mesmo autor ou não. ADANA usamuitos atributos no processo de desambiguação, incluindo afiliação e página do autor,por exemplo.

O método proposto por este trabalho usa somente os atributos comumente encontra-dos nos registros de citações, compostos pelos nomes de autores e coautores, título dotrabalho e do veículo de publicação. É também proposto um método simples para com-binar os resultados de diversos classificadores e um limiar automático para desambiguaros registros de citações.

Conjunto de classificadores (Kuncheva, 2004) tem sido usado para atingir alta acu-rácia de classificação em outros problemas. Por exemplo, em (Saha and Ekbal, 2013)é proposta uma combinação das classes preditas por diferentes classificadores usando ovoto majoritário ponderado, com o objetivo de classificar qualquer palavra ou termo emdocumentos de acordo com categorias pré-definidas como nomes de: pessoas, lugares,organizações, etc., processo também conhecido como reconhecimento de entidade nome-adas (NER). O método que será descrito no capítulo seguinte simplesmente combina as

26 Trabalhos Relacionados

classes preditas pelos classificadores usando um operador lógico.

Capítulo 4

Método proposto

Este capítulo descreve o método proposto que gera uma função de similaridade paracomparar registros de citações combinando os resultados de três classificadores, além decontar com a colaboração de usuários para aumentar o desempenho da desambiguação.Primeiro, uma visão geral do método é apresentada e depois seus detalhes são descritos.

4.1 Visão geral

A Figura 4.1 mostra uma visão geral do método de desambiguação proposto. O métodorecebe como entrada um grupo ambíguo, isto é, um conjunto de registros de citaçõescom nomes de autores ambíguos e produz como saída um conjunto de clusters, ondecada cluster contém idealmente um subconjunto de registros de citações que pertencemao mesmo autor. O método é dividido em cinco passos. O primeiro passo (Geraçãode clusters potencialmente puros) tem como objetivo produzir clusters potencialmentepuros, ou seja, clusters com a maioria dos registros de citações de um mesmo autor.Alguns destes clusters serão selecionados pelo segundo passo (Geração de exemplos detreinamento) para produzir os exemplos de treinamento iniciais. O terceiro passo (Com-binação de classificadores) usa diversos classificadores, na avaliação experimental foiusado os classificadores: SVM, KNN e RF, para aprender uma função de similaridadeque verifica se dois registros de citações pertencem ao mesmo autor e, assim, gerar me-didas capazes de verificar quais os clusters contém registros de citações que pertencemao mesmo autor. O quarto passo (Colaboração de usuários) tem o objetivo de selecionariterativamente os registros de citações para consultar os usuários, se pertencem ou não

27

28 Método proposto

ao mesmo autor. A colaboração dos usuários pode mudar os exemplos de treinamento.E finalmente, o quinto passo (Fusão de clusters) funde os clusters restantes (produzidospelo primeiro passo e que ainda não foram fundidos pelo passo anterior) que o métodoconsidera pertencer ao mesmo autor, usando a função de similaridade aprendida e umlimiar, que é automaticamente definido baseado no número de registros de citações dosclusters.

3

4

2

5

função de similaridade

Grupo ambíguo

Geração de clusters

potencialmente puros

clusterspuros

ConjuntoClustersPuros

Geração de exemplos

de treinamento

1

Conjuntode treino

amostrade treinamento

Combinação declassificadores

Colaboraçãodo usuário

Fusão de clusters

pares de clustersfundidos

Grupodesambiguado

pares de clusters

pares de clusters

PROCESSO ITERATIVO

Figura 4.1: Uma visão geral do método proposto

4.2 Passo 1 - Geração de Clusters Potencialmente

Puros

Conforme descrito anteriormente, o Passo 1 produz clusters potencialmente puros paraos próximos passos, utilizando para isso algumas estratégias. Os clusters inicialmentesão gerados usando os atributos autor e coautor, em uma maneira similar a realizadapor Cota et al. (2010) e Ferreira et al. (2014). Então, algumas estratégias que utilizamos atributos título do trabalho e do veículo de publicação, fundem os clusters iniciaismantendo-os potencialmente puros.

Como em (Cota et al., 2010), os registros de citações de grupos ambíguos são divididosem duas listas: a lista de registros de citações com nomes curtos (lista de nomes curtos),composta por registros de citações cujos nomes de autores tem somente a inicial doprimeiro nome e o último nome completo, e a lista de registros de citações com nomeslongos (lista de nomes longos), composta pelos registros de citações restantes. Primeirose processa a lista de nomes longos e depois a lista de nomes curtos, pois os nomeslongos são mais representativos. As listas são formadas e processadas nessa ordem paraevitar erros logo no início do processamento, já que é difícil formar clusters de registrospara autores diferentes com a comparação entre os nomes longos como ocorre com a

Método proposto 29

comparação entre nomes curtos. O Algoritmo 4.1 mostra este processo.

Algoritmo 4.1: Formação dos clusters iniciaisEntrada: grupo de autores ambíguosSaída: lista de clusters Linício1

R⇐ lista de Registros de Citações r;2

L⇐ lista de Clusters l;3

A.adiciona(R.obtemNomesAutorLongo());4

S.adiciona(R.obtemNomesAutorCurto());5

para cada r em A faça6

se L 6= ∅ então7

para cada l em L faça8

se (Similaridade(r.autor.nome, l.autor.nome)) então9

se (Similaridade(r.coautores.nome, l.coautores.nome) ou10

(r.veiculo = l.veiculo)) entãose (listaNomesComuns ⊂ (r.coautores.nome)) então11

l.insere(r);12

senão13

L.adiciona(l.NovoCluster(r));14

para cada r em S faça15

se L 6= ∅ então16

para cada l em L faça17

se (Similaridade(r.autores.nome, l.autores.nome)) então18

se (Similaridade(r.coautores.nome, l.coautores.nome)) então19

se (listaNomeComuns ⊂ (r.coautores.nome)) então20

l.insere(r);21

senão22

L.adiciona(l.NovoCluster(r));23

fim24

Pares de registros de citações são comparados verificando se têm autores similarese pelo menos um coautor em comum ou título do veículo de publicação iguais (linhas9 e 10). Caso positivo, os registros de citações são considerados do mesmo autor e sãocolocados no mesmo cluster (linha 12). A hipótese é que existem autores com nomesambíguos que podem publicar em um mesmo veículo de publicação, mas são poucos osque publicam com um mesmo coautor. Essa estratégia foi aplicada à lista de nomes deautores longos, cujos os nomes longos similares certamente referem-se ao mesmo autorreal. Na lista de nomes curtos, a comparação do título do veículo de publicação não se

30 Método proposto

aplica, somente compara-se os nomes de autores e coautores (linhas 18 e 19), já que émais difícil formar clusters potencialmente puros para esta lista. No caso do sobrenomedos coautores, se estes forem considerados nomes comuns (linhas 11 - 20), usa-se pelomenos dois nomes de coautores para considerar que os registros de citações pertençamao mesmo autor. A lista de sobrenomes comuns é a mesma utilizada por Ferreira et al.(2014).

Percebe-se que se dois registros de citações tem título do trabalho e do veículo depublicação similares, bem como nome de autor em comum, certamente estes registrossão do mesmo autor. Assim, após criar os clusters inciais, outra estratégia é aplicadapelo Algoritmo 4.2 para fundir alguns deles e mantê-los potencialmente puros.

Algoritmo 4.2: Fusão HierárquicaEntrada: lista de clusters iniciais L, limiarSaída: lista de clusters Linício1

para i← 0 até i < L.size()− 1 faça2

l1 ←− L(i) ;3

para j ← i+ 1 até j < C.size() faça4

l2 ←− L(j) ;5

se (Similaridade(l1.autores.nome, l2.autores.nome)) então6

O ← Similaridade(l1.titulo, l2.titulo);7

V ← Similaridade(l1.veiculo, l2.veiculo);8

se (O > limiar e V > limiar) então9

l1 ← l2;10

L.remove(l2);11

fim12

Dado como entrada a lista de clusters iniciais, o algoritmo computa para os pares declusters (linhas 2 à 5) com nomes de autores similares (linha 6), a similaridade do títulodo trabalho e do veículo de publicação (linha 7 e 8) e se esta estiver acima de um limiar(linha 9), os cluster são fundidos (linha 10 e 11). Para medir a similaridade entre doisnomes de autores ou coautores, é usado o algoritmo comparação por fragmentos e paraos atributos títulos do trabalho e do veículo de publicação foram usados o coeficientede Jaccard. Os resultados dos experimentos mostrados no Capítulo 5 levam em consi-deração a similaridade mínima entre os títulos do trabalho e do veículo de publicação(com o valor de 0.1 para ambos os limiares), a maneira mais simples encontrada é pelocoeficiente de Jaccard, não importando, por exemplo, considerar a frequência de termosmais informativos (raros), como é considerado por outras medidas (cosseno).

Método proposto 31

A Figura 4.2, ilustra todo o processo de formação e fusão hierárquica dos clustersiniciais. Cada figura geométrica representa um registro de citação e as figuras com amesma forma são registros de citações escritos por um mesmo autor.

(a) Registros de citações de um grupo am-bíguo

1 - c forgy, a gupta

2 - c forgy, r wedig, a gupta

3 - a newell, c forgy, anoop gupta

4 - a acharya, m tambe, a gupta

(b) Aplicando estratégias para a criação declusters iniciais explorando os nomes dosautores e coautores dos registros de cita-ções

(c) Criação de clusters iniciais

�

1 - j parallel distrib comput

2 - symposium comput architectur

3 - tran comput syst

4 - tran parallel distrib syst

(d) Aplicando estratégias para fusão declusters iniciais explorando os título do tra-balho e do veículo de publicação dos regis-tros de citações

Figura 4.2: Formação e fusão hierárquica dos clusters iniciais

A Figura 4.2(a) mostra todos os registros de citações do grupo do autor ambíguo“A. Gupta”. Assim, para formar os clusters, os registros de citações, comparados par apar, são verificados se possuem nomes de autores similares e pelo menos um coautor emcomum. Para a Figura 4.2(b), os registros de 1 à 3 satisfazem a verificação, pois os nomesdos autores são similares (“A. Gupta” e “Anoop Gupta”) e todos possuem coautores emcomum (“C. Forgy”), com exceção do registro 4, que possui nome de autor similar mas nãotem coautoria em comum. Essas estratégias produzem em sua grande maioria clustersdos mesmos autores reais, chamados clusters potencialmente puros, porém partes dos

32 Método proposto

registros de citações de um mesmo autor real estão fragmentadas (separadas) em diversosclusters, como mostrado na Figura 4.2(c). Por isso, são realizadas fusões hierárquicas,que reduzem a fragmentação sem perder a qualidade interna dos grupos formados. AFigura 4.2(d) mostra o processo de fusão de registros de citações separados em doisclusters diferentes, utilizando apenas os atributos título do veículo de publicação.1 Aslinhas tracejadas e contínuas indicam que o registro de citação 4 tem palavras em comum,do conjunto de palavras que formam o título do veículo de publicação, com os registros1 e 3, respectivamente.

4.3 Passo 2 - Geração de exemplos de treinamento

De modo a fornecer automaticamente os exemplos de treinamento para o Passo 3, sãoselecionados dos clusters fornecidos pelo Passo 1, aqueles clusters que certamente per-tencem a autores diferentes, garantindo assim que clusters potencialmente puros sejamselecionados descartando os que são fragmentados. Inicialmente, a lista de clusters éordenada em ordem decrescente pela quantidade de registros de citações. Então, o pri-meiro cluster é adicionado ao conjunto de clusters do treino S. Os próximos clusters aserem inseridos em S não devem pertencer ao mesmo autor dos clusters que já estão emS. Uma comparação dos nomes de autores representativos de cada cluster é feita paradecidir se não pertencem ao mesmo autor. O nome do autor do primeiro registro decitação inserido em um cluster é usado como nome de autor representativo. Para cadacluster em S, supõe-se que os registros de citações em um mesmo cluster pertencem aomesmo autor e os que estão em clusters diferentes são de autores diferentes.

O conjunto de exemplos de treinamento T é construído da seguinte forma: calcula-sea similaridade da comparação entre cada par de registros de citações pertencentes aomesmo cluster (intra-cluster) ou a diferentes clusters (inter-clusters) em S. Em cadacomparação, um exemplo de treinamento ei é adicionado ao conjunto de treinamentoT , onde ei contém um conjunto de k características {f1, f2, · · · , fk} com uma variávelespecial c ∈ {0, 1} chamada classe. O valor de cada característica fj corresponde aosresultados da comparação entre os atributos de dois registros de citações. Pode-se usarqualquer função de similaridade/dissimilaridade para comparar os atributos. Na avalia-ção experimental (Capítulo 5), as características f1, f2 e f3 correspondem à comparaçãoentre os nomes de coautores, título do trabalho e do veículo de publicação, respecti-

1No processo de fusão hierárquica dos clusters, o título do trabalho também é considerado.

Método proposto 33

vamente, usando o coeficiente de Jaccard (atributos numéricos). Além destas, existemmais três características, f4 compara os nomes dos autores usando a comparação porfragmentos (atributo binário), f5 verifica se o título do veículo de publicação são iguais(atributo binário) e f6 corresponde ao número de termos em comum entres dois títulosdo trabalho (atributo numérico). O valor da variável classe indica se dois registros decitações pertencem ao mesmo autor (c = 1) ou não (c = 0).

A Figura 4.3 ilustra todo o processo de geração dos exemplos de treinamento.

(a) Ordenação dos clusters iniciais

r - anoop gupta

r - anurag gupta

(b) Comparação dos nomes de autoresdos registros representativos entre pares declusters

21 3

(c) Clusters selecionados (figuras preenchi-das) que irão gerar os exemplos de treina-mento

c=0 f :0.0 f :0.168 f :0.0 f :0 f :0 f :0

c=1 f :1.0 f :0.33 f :0.33 f :1 f :0 f :2

T

1

1

2 3 4 5 6

2 3 4 5 6

(d) Conjunto de exemplos de treinamento

Figura 4.3: Seleção de clusters iniciais para a geração dos exemplos de treinamento

Inicialmente os clusters são ordenados de acordo com a quantidade de registros decitações presentes em cada cluster, como visto na Figura 4.3(a). Após a ordenação, aFigura 4.3(b) mostra a seleção dos clusters com os registros de citações que irão geraros exemplos de treinamento. O cluster com maior quantidade de registros de citações éo primeiro a ser selecionado para o conjunto de treino, os próximos a serem selecionados

34 Método proposto

devem ser os clusters com maior número de registros de citações associados a nomes deautores dissimilares dos registros de citações dos clusters que já foram selecionados. Osclusters selecionados, nesse caso os clusters 1, 2 e 3, são mostrados na Figura 4.3(c).Finalmente, na Figura 4.3(d) o conjunto de treinamento é gerado a partir da comparaçãoentre pares de registros de citações dos clusters selecionados. A comparação de registrosdentro do mesmo cluster, indica que os registros de citações são do mesmo autor (c = 1) eos registros de citações de clusters diferentes são de autores distintos (c = 0). As demaiscaracterísticas, f1, f2, f3, f4, f5 e f6, representam a comparação entre os atributos dosregistros de citações.

4.4 Passo 3 - Combinação de classificadores

Nesse caso, os classificadores frequentemente inferem dois registros de citações do mesmoautor real como se pertencessem a autores diferentes, mas raramente erram na prediçãode registros de autores diferentes como sendo do mesmo autor. Além disso, algumasvezes um classificador prevê c = 1 corretamente quando um outro prevê c = 0, istoé, as predições para a classe por vários classificadores são complementares (ver Capí-tulo 5). Estas situações ocorrem devido ao desbalanceamento entre as classes, poiscomo os clusters selecionados contém uma grande quantidade de registros de citações esão dissimilares uns dos outros, há um grande número de exemplos de treinamento entreregistros de citações de autores diferentes (c = 0) do que registros de citações do mesmoautor (c = 1).

Existem diversas técnicas para melhorar a predição de dados com classes desbalance-adas. Algumas selecionam aleatoriamente exemplos de uma das classes para que sejameliminados ou replicados, a fim de mudar a distribuição dos exemplos de treinamento,de modo que a classe rara (c = 1) seja bem representada. Há outras que utilizamum conjunto de classificadores, sem que a quantidade de exemplos de treinamento sejamodificada, como foi proposto neste trabalho.

Ao invés de usar um conjunto de classificadores complexo como sugerido por Kun-cheva (2004), é proposto o uso de uma maneira simples e eficiente de combinar os rótulosdas predições de diferentes classificadores (para o problema da desambiguação) com o ob-jetivo de aumentar a resposta para a classe 1 (c = 1). O classificador gerado F , combinaos resultados de outros classificadores, aplicando somente o OU lógico nos resultadosdos rótulos das classes inferidas por cada classificador no processo de classificação, ou

Método proposto 35

seja, se pelo menos um classificador prevê c = 1, o resultado será c = 1; caso contrárioc = 0. A Figura 4.4 ilustra a combinação de múltiplos classificadores.

.

.

.

OU lógico

1: mesmo autor0: autores diferentes

F

classefinalC 2

C1

Cp

Conjuntode treino

1: mesmo autor0: autores diferentes

1: mesmo autor0: autores diferentes

1: mesmo autor0: autores diferentes

ConjuntoTeste

Figura 4.4: Combinação de múltiplos classificadores

Todos os classificadores C1, C2, · · · , Cp recebem como entrada o mesmo conjunto detreinamento T para aprender suas funções de classificação F1, F2, · · · , Fp, respectiva-mente e um conjunto de teste formado pela comparação de pares de registros entre doisclusters diferentes formados pelo Passo 1. Na fase de teste, cada classificador Ci exe-cuta paralelamente sobre o mesmo conjunto de teste, para inferir o seu valor da classe(c1, c2, · · · , cp). O resultado final corresponde ao OU lógico aplicado ao valor de cadaclasse predita (c1∨c2∨· · ·∨cp). A partir da classe de saída do conjunto de classificadoressão calculadas duas medidas que servem para selecionar os pares de clusters gerados peloPasso 1 que serão fundidos nos Passos 4 e 5.

Taxa de classes raras

A primeira delas verifica a quantidade de classes raras. Formalmente, Li = {ri,1, · · · , ri,l}e Lj = {rj,1, · · · , rj,m} são clusters de registros de citações formados inicialmente peloPasso 1. Cada par (ri,u, rj,v) de registros de citações é comparado gerando um registroe que é adicionado ao conjunto de teste U . O classificador F infere a classe de todos osregistros em U e então é calculado a taxa que define a razão entre o número de registros

36 Método proposto

em U classificados como classe 1 (classe rara), pelo número total de registros, definidana Equação 4.1:

tcr =#registrosc1#registros

(4.1)

onde, #registrosc1 é o número de registros e classificados na classe 1 e #registros é onúmero total de registros e em U .

Geração de limiar automático

Para fundir dois clusters distintos, contendo poucos registros de citações, o número deregistros preditos em U da classe c = 1 deve ser alto. Por outro lado, quando existemmuitos registros de citações em ambos os clusters, o número de registros preditos em U

para a classe c = 1 pode ser baixo. A hipótese é que um autor não publica seu trabalhono mesmo tópico/tema, assim, dado dois clusters diferentes do mesmo autor, algunssubconjuntos destes clusters são similares. Para encontrar automaticamente um valorpara cada comparação entre clusters, foi proposto um limiar mostrado na Equação 4.2:

%min =1

log2 (c ∗ (|Li| ∗ |Lj|))(4.2)

onde |Li| e |Lj| são o número de registros de citações nos clusters Li e Lj, respectiva-mente. A constante c não permite ter um denominador igual a 0. O melhor valor parac foi encontrado empiricamente, como pode ser visto no Capítulo 5. De acordo com aproporção de registros de citações nos clusters, o uso do logaritmo diminui suavementeo valor do limiar quando o número de registros de citações aumenta e eleva levemente olimiar se o número de registros diminui.

4.5 Passo 4 - Colaboração dos Usuários

Neste passo, os usuários (ou administradores das DLs) ajudam o método a aumentar odesempenho da desambiguação, usando sua colaboração de forma iterativa. Em cada

Método proposto 37

iteração, o método consulta os usuários que verificam se dois clusters de registros decitações, gerados pelo Passo 1, pertencem ao mesmo autor, ao invés de fornecer o autorcorreto de cada cluster. O esforço despendido pelos usuários no método é pouco secomparado aos métodos propostos por Ferreira et al. (2012b) e Godoi et al. (2013).

A tarefa deste passo é compreendida no Algoritmo 4.3. O método adiciona todos ospares de clusters de registros de citações que possuem nomes de autores similares a umalista (linhas 4 à 9). Os pares de clusters são ordenados de acordo com a diferença dataxa de classes raras e do limiar automático (linha 10). Um número fixo, n, dos paresde clusters que estão topo da lista e contém a menor diferença são considerados a cadaiteração para que os usuários indiquem se são ou não do mesmo autor (linhas 11 e 12).

Se a resposta é sim, ambos os clusters são mantidos em uma lista para que no finaldas comparações a cada iteração possam ser fundidos em somente um cluster (linhas13 à 15); caso contrário, os clusters permanecem separados e o método não os comparanovamente nas próximas iterações (linhas 16 e 17).

Algoritmo 4.3: Fusão de pares de clusters de registros de citações por Colaboraçãode UsuáriosEntrada: lista de clusters L, %min, razãoSaída: lista de clusters P que devem ser fundidosT ⇐ conjunto de treino;1

U ⇐ conjunto de teste;2

início3

para i← 0 até i < L.size()− 1 faça4

l1 ←− L(i) ;5

para j ← i+ 1 até j < L.size() faça6

l2 ←− L(j) ;7

se (Similaridade(l1.autor.nome, l2.autores.nome)) então8

D ← predições de U usando T ;9

D ← ordena usando tcr −%min;10

n← porção de D;11

R← resposta do usuário;12

se (R) então13

P.adiciona(l1, l2);14

L.remove(l2);15

senão16

D.remove(l1, l2);17

fim18

38 Método proposto

4.6 Passo 5 - Fusão de Clusters

O Passo 5 tem a meta de fundir os clusters restantes gerados pelo Passo 1, que pertencemao mesmo autor real diminuindo a fragmentação destes clusters. Se dois registros decitações entre pares de clusters possuem nomes de autores similares, estes são fundidosquando, a taxa de classes raras é menor ou igual ao limiar automático, como pode servisto na Equação 4.3:

tcr ≥ %min (4.3)

Capítulo 5

Resultados e Discussões

Neste capítulo são apresentados os resultados experimentais para avaliação do métodoproposto. Primeiro são descritas as coleções utilizadas, os métodos representativos (com-parativos) e as métricas de avaliação. Então é discutida a eficiência do método proposto.

5.1 Coleções

Para avaliar experimentalmente o método proposto, foram usadas duas coleções obtidas apartir da Digital Bibliography & Library Project Computer Science Bibliography (DBLP).

5.1.1 DBLP

A primeira coleção derivada da DBLP, definida neste trabalho como DBLP, acumula4.287 registros de citações associadas a 220 autores diferentes, quem tem em médiacerca de 20 registros por autor. Pequenas variações desta coleção têm sido usadas emdiversos outros trabalhos Ferreira et al. (2012b, 2010); Han et al. (2004, 2005a). Suaversão original foi criada por Han et al. (2004), rotulando os registros manualmente.Para isso, eles usaram as páginas dos autores, afiliação, e-mail, e nomes de coautores,além de e-mails enviados aos autores para confirmar sua autoria. Han et al. (2004)também substituíram as abreviações do título e veículo de publicação, por uma versãocompleta obtida da DBLP. Foram usados 11 grupos ambíguos extraídos por Han et al.

39

40 Resultados e Discussões

(2004) com algumas correções.1.

5.1.2 KISTI

A segunda coleção derivada da DBLP, definida neste trabalho como KISTI, foi construídapelo Korea Institute of Science and Technology Information Kang et al. (2011) paraa desambiguação de nomes de autores homônimos. Os 1000 nomes de autores maisfrequentes da DBLP foram obtidos juntamente com os seus registros no final do ano de2007. Então, para cada nome de autor um registro de citação foi construído.

Para desambiguar esta coleção, foram submetidas consultas ao Google, compostas dosobrenome do autor e do título de cada registros de citação, com o objetivo de encontrarpáginas de publicações dos autores. As primeiras 20 páginas da web retornadas paracada consultas foram verificadas manualmente e a página de publicação pessoal para cadaautor foi corretamente identificada. Estas páginas foram então usadas para desambiguaros registros.

Esta coleção tem 37.613 registros de citação, 881 grupos de pessoas com o mesmonome e 6.921 autores 2. Devido ao grande número de experimentos e comparações, foramutilizados na avaliação do método os grupos ambíguos mais frequentes, isto é, os gruposcom o maior número de autores ambíguos. Este grupos são os mais difíceis de seremdesambiguados e contém 7.841 registros de citações, 40 grupos de pessoas com o mesmonome e 1.132 autores, com uma média de 28.3 autores ambíguos diferentes por grupo(com um máximo de 59).

5.2 Métodos representativos

Foram utilizados como referência de comparação, dois métodos representativos que utili-zam a colaboração dos usuários propostos por Ferreira et al. (2012b), referenciado comoSANDRef, e Godoi et al. (2013), referenciado como GOPFRef. Como discutido no Capí-tulo 3, ambos os métodos realizam a atribuição a autores, isto é, cada registro de citaçãoé atribuído a um autor. Usando o SANDRef, os usuários devem informar os autores deuma porcentagem de predições mais duvidosas, enquanto que, usando o GOPRef, os

1Disponível em http://www.lbd.dcc.ufmg.br/lbd/collections/disambiguation (acessado emJul. 2014).

2Disponível em http://www.kisti.re.kr (acessado em Jul. 2014).

Resultados e Discussões 41

usuários devem informar os autores de uma quantidade de predições duvidosas em cadaiteração.

Na avaliação experimental, para SANDRef, o usuário informa o autor de 100% daspredições duvidosas. GOPFRef e o método proposto por este trabalho funcionam emuma forma iterativa. Em cada iteração, para GOPFRef, o usuário deve informar osautores das primeiras n predições duvidosas. Neste trabalho, o usuário informa se doisclusters pertencentes ao mesmo autor para os primeiros n pares mais duvidosos.

Vale enfatizar que os métodos de referência foram comparados com outros métodossupervisionados e não supervisionados e obtiveram os melhores desempenhos em suascomparações.

5.3 Métricas de avaliação

Para avaliar a eficiência do método em desambiguar nomes de autores, foram usadasas métricas K e F1. Elas já foram usadas antes, por outros métodos de desambigua-ção (Ferreira et al., 2012b; Godoi et al., 2013) para avaliar a qualidade e o desempenho.Estas métricas permitem ter um valor numérico que representa a qualidade dos clustersgerados.

5.3.1 Métrica K

A métrica K (Lapidot, 2002) implementa uma relação entre a média da pureza dosclusters (ACP) e a média da fragmentação dos autores (AAP). Dado um grupo ambíguo,ACP avalia a pureza dos clusters empíricos (aqueles gerados pelo método) em relaçãoaos clusters teóricos (aqueles gerados manualmente) para este grupo ambíguo. Assim,se os clusters empíricos forem puros (isto é, se eles contêm somente registros de citaçõesassociados ao mesmo autor) o valor ACP correspondente será 1. ACP é definido naEquação 5.1:

ACP =1

N

e∑i=1

t∑j=1

n2ij

ni

, (5.1)

42 Resultados e Discussões

onde, N é o número total de registros de citações no grupo ambíguo, t é o número declusters teóricos no grupo ambíguo, e é o número de clusters empíricos para o grupoambíguo, ni é o número total de registros de citação no cluster empírico i e nij é onúmero total de registros de citação no cluster empírico i que também estão no clusterteórico j.

Para um dado grupo ambíguo, AAP avalia a fragmentação dos clusters empíricos emrelação aos clusters teóricos. Se os clusters empíricos não estão fragmentados, o valorAAP correspondente será 1. AAP é definido pela Equação 5.2:

AAP =1

N

t∑j=1

e∑i=1

n2ij

nj

, (5.2)

onde, nj é o número total de registros de citações nos clusters teóricos j.

A métrica K é definida pela Equação 5.3 como a média geométrica entre os valoresde ACP e AAP:

K =√ACP×AAP. (5.3)

Ela avalia a pureza e coesão de clusters empíricos extraídos por cada método.

5.3.2 Métrica PF1 entre pares

F1 calculada entre pares (PF1) é a métrica F1 (Rijsbergen, 1979) usando os valores daprecisão e revocação sobre pares de registros. Precisão par a par (pP ) é calculada comopP= a

a+c, onde a é o número de pares de registros de citações em um clusters empírico

que são (corretamente) do ao mesmo autor, e c é o número de pares de registros decitações em um clusters empírico que não são do mesmo autor. Revocação par a par(pR) é calculado como pR= a

a+b, onde b é o número de pares de registros do mesmo autor

que não estão no mesmo cluster empírico. A métrica F1 é definida pela Equação 5.4:

pF1 = 2× pP × pRpP + pR

. (5.4)

Resultados e Discussões 43

5.4 Configuração experimental

Os experimentos para avaliar o método proposto foram baseados em um protocolo ex-perimental descrito em (Ferreira et al., 2012b). O método utiliza Weka (Witten et al.,1999), uma coleção de algoritmo de aprendizagem de máquina em JAVA, para treinar etestar os classificadores SVM, KNN e RF.

A configuração dos parâmetros dos classificadores SVM, KNN e RF foi realizadadividindo as bases em 10 folds, por meio de validação cruzada sobre o conjunto detreinamento.

Para aprender o modelo pelo SVM, é usado o kernel Gaussian Radial Basis Function(RBF ), bastante empregado por trabalhos de desambiguação (Ferreira et al., 2012b; Ve-loso et al., 2012) e um algoritmo chamado GridSearch que encontra a melhor combinaçãodos parâmetros avaliados (constante de regularização C e gamma). Para o classificadorRF, o GridSearch também é usado para ajustar os parâmetros numFeatures e numTrees,de modo a verificar se o classificador utiliza todos ou um subconjunto dos atributos (ca-racterísticas) e se encontra o número ótimo de árvores geradas, respectivamente. E, parao classificador KNN, com variação do número de K de 5.0 até 15.0, foi obtido o valorigual a 5 (K = 5).

Para comparar os resultados aqui alcançados com os obtidos em (Ferreira et al.,2012b; Godoi et al., 2013), o método proposto e os métodos de referência foram execu-tados dez vezes para cada grupo ambíguo, utilizando uma seleção aleatória de 50% dosregistros de cada grupo. Os valores dos resultados são comparados com um intervalo deconfiança (IC) de 99% usando teste-t.

Para a escolha da constante c na geração do limiar automático %min da comparaçãoentre clusters, a Tabela 5.1 apresenta os valores definidos empiricamente.

Os método de desambiguação (com somente uma iteração no Passo 4) foi avaliadocom diferentes valores para a constante c utilizando a base de dados da DBLP. Durante afase de treinamento a base é separada em dois grupos (treino e teste) mediante validaçãocruzada de 5-folds, variando os valores da constante em cada combinação. O experimentofoi executado dez vezes e ao final (Passo 5) os clusters são fundidos obtendo os valorespara as métricas de avaliação.

O valor para c selecionado foi 1.5, em que não foram identificados melhores resultados

44 Resultados e Discussões

Tabela 5.1: Resultado (com desvio padrão) da variação dos valores para aconstante c na geração do limiar automático %min

Valor de c ACP AAP K pP pR pF1

1.5 0.982±0.003 0.410±0.017 0.629±0.013 0.972±0.008 0.311±0.018 0.457±0.0181.6 0.983± 0.003 0.404± 0.010 0.624± 0.008 0.974± 0.005 0.300± 0.015 0.446± 0.016

1.7 0.982± 0.003 0.409± 0.014 0.627± 0.010 0.972± 0.007 0.309± 0.027 0.455± 0.029

1.8 0.982± 0.003 0.403± 0.009 0.623± 0.007 0.969± 0.010 0.300± 0.016 0.445± 0.018

1.9 0.982± 0.003 0.400± 0.015 0.621± 0.011 0.971± 0.007 0.292± 0.023 0.437± 0.023

2.0 0.981± 0.004 0.389± 0.012 0.611± 0.010 0.968± 0.009 0.277± 0.017 0.418± 0.019

2.1 0.983± 0.003 0.401± 0.012 0.621± 0.010 0.971± 0.007 0.293± 0.018 0.437± 0.019

2.2 0.981± 0.003 0.404± 0.017 0.623± 0.013 0.970± 0.005 0.301± 0.024 0.445± 0.025

2.3 0.982± 0.004 0.400± 0.006 0.621± 0.005 0.971± 0.006 0.291± 0.011 0.436± 0.013

2.4 0.982± 0.003 0.405± 0.012 0.625± 0.010 0.972± 0.008 0.303± 0.018 0.448± 0.021

2.5 0.983± 0.002 0.404± 0.018 0.624± 0.014 0.975± 0.004 0.295± 0.023 0.439± 0.025

2.6 0.983± 0.003 0.404± 0.012 0.624± 0.009 0.974± 0.004 0.301± 0.024 0.446± 0.026

com outras variações dos valores.

5.5 Resultados

Pureza dos resultados do Passo 1

As Tabelas 5.2 e 5.3 mostram os resultados e as médias obtidos pelo método propostoquando é executado somente o primeiro passo (Geração de clusters puros) na DBLP,formando os clusters iniciais seguido pela fusão hierárquica dos clusters iniciais.

Em todos os grupos ambíguos na Tabela 5.2, os valores de ACP e pP são próximoa 1, indicando que os clusters inicialmente gerados por este passo são muito puros, istoé, quase todas os registros no mesmo cluster pertencem ao mesmo autor. No entanto,existem registros de citação do mesmo autor em diferentes clusters. Tal situação pode sernotada pelos valores de AAP e pR que não estão próximo a 1. Na Tabela 5.3, os valoresde AAP e pR sofrem um leve aumento que contribuem para diminuir a fragmentaçãodos clusters e consequentemente aumentar os valores de K e pF1.

Nas Tabelas 5.4 e 5.5 são mostrados os resultados e a média do primeiro passo(Geração de clusters puros) do método proposto na coleção KISTI, quando a formaçãodos clusters iniciais e a fusão hierárquica são executadas, respectivamente.

Resultados e Discussões 45

Tabela 5.2: Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração declusters puros) para cada grupo ambíguo na DBLP após a formação dos clustersiniciais

Grupos ambíguos ACP AAP K pP pR pF1

A Gupta 0.999± 0.002 0.368± 0.027 0.606± 0.022 1.000± 0.001 0.293± 0.050 0.451± 0.058

A Kumar 1.000± 0.000 0.240± 0.038 0.489± 0.038 1.000± 0.000 0.082± 0.025 0.150± 0.041

C Chen 0.961± 0.007 0.293± 0.008 0.531± 0.008 0.839± 0.029 0.085± 0.011 0.153± 0.018

D Johnson 1.000± 0.000 0.251± 0.035 0.499± 0.034 1.000± 0.000 0.187± 0.044 0.313± 0.059

J Martin 1.000± 0.000 0.546± 0.042 0.739± 0.028 1.000± 0.000 0.302± 0.047 0.462± 0.057

J Robinson 1.000± 0.000 0.385± 0.029 0.620± 0.024 1.000± 0.000 0.276± 0.052 0.431± 0.066

J Smith 0.992± 0.004 0.156± 0.010 0.393± 0.012 0.992± 0.006 0.095± 0.017 0.173± 0.027

K Tanaka 1.000± 0.000 0.379± 0.023 0.616± 0.019 1.000± 0.000 0.225± 0.034 0.366± 0.044

M Brown 1.000± 0.000 0.392± 0.043 0.625± 0.034 1.000± 0.000 0.253± 0.069 0.400± 0.086

M Jones 1.000± 0.000 0.295± 0.035 0.542± 0.032 1.000± 0.000 0.229± 0.051 0.370± 0.066

M Miller 0.999± 0.004 0.410± 0.046 0.639± 0.036 1.000± 0.002 0.347± 0.055 0.513± 0.061

Média 0.996± 0.001 0.338± 0.009 0.573± 0.008 0.985± 0.003 0.216± 0.012 0.344± 0.016

Tabela 5.3: Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração declusters puros) para cada grupo ambíguo na DBLP após a fusão hierárquica dosclusters iniciais

Grupos ambíguos ACP AAP K pP pR pF1

A Gupta 0.984± 0.009 0.430± 0.054 0.649± 0.042 0.989± 0.012 0.376± 0.080 0.541± 0.083

A Kumar 0.997± 0.006 0.280± 0.037 0.527± 0.036 0.996± 0.008 0.106± 0.023 0.191± 0.037

C Chen 0.920± 0.007 0.315± 0.015 0.538± 0.013 0.794± 0.017 0.103± 0.011 0.181± 0.016

D Johnson 0.968± 0.014 0.291± 0.044 0.529± 0.041 0.977± 0.019 0.226± 0.064 0.363± 0.084

J Martin 1.000± 0.000 0.590± 0.035 0.768± 0.023 1.000± 0.000 0.356± 0.055 0.523± 0.062

J Robinson 0.996± 0.008 0.413± 0.043 0.640± 0.035 0.996± 0.009 0.306± 0.059 0.465± 0.069

J Smith 0.971± 0.009 0.226± 0.023 0.467± 0.024 0.981± 0.010 0.177± 0.034 0.299± 0.049

K Tanaka 0.994± 0.008 0.421± 0.021 0.647± 0.017 0.984± 0.018 0.276± 0.031 0.431± 0.038

M Brown 0.999± 0.007 0.443± 0.050 0.664± 0.038 0.998± 0.007 0.328± 0.077 0.489± 0.090

M Jones 0.995± 0.008 0.331± 0.029 0.574± 0.025 0.997± 0.006 0.274± 0.037 0.428± 0.046

M Miller 0.996± 0.008 0.500± 0.062 0.704± 0.047 0.994± 0.013 0.458± 0.073 0.623± 0.072

Média 0.984± 0.002 0.385± 0.016 0.610± 0.013 0.973± 0.002 0.271± 0.025 0.412± 0.029

A Tabela 5.4 mostra que os clusters iniciais gerados são puros, tendo 12 de 40 gruposambíguos com valores de ACP e pP iguais a 1. O restante dos grupos ambíguos tambémtem valores bem próximos a 1 para as duas métricas. Mas, este passo ainda produzclusters fragmentados, como pode ser visto pelos valores de AAP e pR que estão maispróximos à 0.

Na Tabela 5.5, os valores de AAP e pR sofrem um pequeno aumento, o que ajuda

46 Resultados e Discussões

Tabela 5.4: Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração declusters puros) para cada grupo ambíguo na KISTI após a formação dos clustersiniciais

Grupos ambíguos ACP AAP K pP pR pF1

A Choudhary 1.000± 0.000 0.362± 0.107 0.596± 0.090 1.000± 0.000 0.354± 0.108 0.515± 0.119

A Gupta 0.999± 0.004 0.432± 0.054 0.656± 0.040 1.000± 0.002 0.368± 0.111 0.530± 0.110

D Eppstein 1.000± 0.000 0.071± 0.023 0.264± 0.040 1.000± 0.000 0.062± 0.023 0.115± 0.039

D Lee 1.000± 0.000 0.340± 0.042 0.582± 0.036 1.000± 0.000 0.109± 0.034 0.195± 0.055

H Chen 0.979± 0.014 0.570± 0.033 0.747± 0.019 0.896± 0.071 0.204± 0.045 0.330± 0.060

H Wang 0.988± 0.007 0.483± 0.031 0.691± 0.022 0.986± 0.011 0.303± 0.065 0.460± 0.077

J Chen 0.994± 0.006 0.480± 0.022 0.691± 0.016 0.995± 0.006 0.128± 0.028 0.225± 0.043

J Dongarra 1.000± 0.000 0.192± 0.098 0.426± 0.105 1.000± 0.000 0.181± 0.099 0.296± 0.133

J Halpern 0.966± 0.015 0.071± 0.014 0.261± 0.025 0.913± 0.041 0.054± 0.012 0.102± 0.021

J Kim 0.979± 0.020 0.797± 0.033 0.883± 0.022 0.920± 0.099 0.501± 0.073 0.646± 0.072

J Lee 0.973± 0.014 0.680± 0.024 0.813± 0.014 0.891± 0.070 0.357± 0.036 0.508± 0.037

J Li 0.993± 0.009 0.579± 0.033 0.758± 0.023 0.982± 0.023 0.218± 0.047 0.355± 0.063

J Liu 0.994± 0.010 0.522± 0.038 0.720± 0.026 0.987± 0.021 0.195± 0.066 0.321± 0.088

J Mitchell 1.000± 0.000 0.227± 0.041 0.475± 0.043 1.000± 0.000 0.168± 0.043 0.285± 0.062

J Smith 0.991± 0.013 0.478± 0.047 0.687± 0.036 0.985± 0.024 0.180± 0.042 0.302± 0.061

J Wang 0.998± 0.004 0.496± 0.024 0.703± 0.017 0.998± 0.004 0.246± 0.031 0.394± 0.039

J Wu 1.000± 0.000 0.187± 0.025 0.431± 0.029 1.000± 0.000 0.055± 0.019 0.103± 0.033

J Zhang 0.994± 0.006 0.587± 0.031 0.764± 0.021 0.993± 0.008 0.333± 0.042 0.498± 0.047

L Zhang 0.991± 0.009 0.627± 0.049 0.788± 0.032 0.984± 0.016 0.448± 0.092 0.611± 0.089

M Chen 0.997± 0.006 0.326± 0.034 0.570± 0.030 0.998± 0.004 0.147± 0.041 0.254± 0.061

M Pedram 1.000± 0.000 0.054± 0.006 0.233± 0.013 1.000± 0.000 0.042± 0.007 0.081± 0.012

M Vardi 0.976± 0.013 0.158± 0.026 0.392± 0.031 0.979± 0.014 0.135± 0.023 0.236± 0.035

N Jennings 1.000± 0.000 0.095± 0.019 0.307± 0.030 1.000± 0.000 0.083± 0.019 0.152± 0.032

N Jha 1.000± 0.000 0.318± 0.121 0.556± 0.102 1.000± 0.000 0.310± 0.122 0.463± 0.134

N Lynch 1.000± 0.000 0.109± 0.022 0.328± 0.035 1.000± 0.000 0.098± 0.022 0.177± 0.037

P Yu 1.000± 0.000 0.159± 0.034 0.397± 0.042 1.000± 0.000 0.119± 0.033 0.212± 0.051

Q Yang 0.963± 0.018 0.188± 0.036 0.423± 0.042 0.956± 0.031 0.074± 0.036 0.135± 0.060

S Jajodia 0.989± 0.005 0.127± 0.034 0.351± 0.047 0.996± 0.003 0.110± 0.035 0.196± 0.056

S Kim 0.986± 0.015 0.767± 0.056 0.869± 0.032 0.983± 0.023 0.642± 0.098 0.773± 0.077

S Lee 0.989± 0.012 0.619± 0.052 0.781± 0.034 0.962± 0.044 0.257± 0.051 0.404± 0.065

T Henzinger 1.000± 0.000 0.353± 0.103 0.589± 0.087 1.000± 0.000 0.346± 0.105 0.506± 0.114

W Wang 0.958± 0.021 0.444± 0.032 0.652± 0.018 0.860± 0.075 0.141± 0.024 0.240± 0.032

X Li 0.964± 0.009 0.451± 0.020 0.659± 0.014 0.874± 0.042 0.176± 0.029 0.291± 0.040

X Zhou 0.982± 0.010 0.525± 0.041 0.717± 0.027 0.980± 0.016 0.417± 0.099 0.579± 0.095

Y Chen 0.995± 0.007 0.540± 0.019 0.733± 0.012 0.994± 0.008 0.271± 0.023 0.425± 0.029

Y Liu 0.990± 0.009 0.610± 0.028 0.777± 0.017 0.986± 0.013 0.419± 0.054 0.586± 0.054

Y Wang 0.994± 0.008 0.548± 0.022 0.738± 0.014 0.978± 0.028 0.225± 0.035 0.364± 0.045

Y Yang 0.996± 0.008 0.433± 0.030 0.657± 0.024 0.987± 0.025 0.121± 0.022 0.215± 0.035

Y Zhang 0.991± 0.009 0.637± 0.048 0.794± 0.032 0.976± 0.035 0.288± 0.069 0.441± 0.084

Z Zhang 0.961± 0.017 0.461± 0.033 0.665± 0.023 0.902± 0.055 0.196± 0.024 0.321± 0.032

Média 0.989± 0.002 0.403± 0.006 0.603± 0.006 0.974± 0.005 0.227± 0.006 0.346± 0.006

Resultados e Discussões 47

Tabela 5.5: Resultados (com desvio padrão) obtidos pelo Passo 1 (Geração declusters puros) para cada grupo ambíguo na KISTI após a fusão hierárquica dosclusters iniciais

Grupos ambíguos ACP AAP K pP pR pF1

A Choudhary 1.000± 0.000 0.432± 0.110 0.653± 0.082 1.000± 0.000 0.425± 0.111 0.589± 0.106

A Gupta 0.998± 0.006 0.454± 0.071 0.671± 0.050 1.000± 0.002 0.389± 0.142 0.548± 0.138

D Eppstein 1.000± 0.000 0.086± 0.017 0.291± 0.029 1.000± 0.000 0.077± 0.017 0.141± 0.029

D Lee 1.000± 0.000 0.351± 0.044 0.591± 0.036 1.000± 0.000 0.118± 0.049 0.207± 0.075

H Chen 0.973± 0.015 0.576± 0.016 0.748± 0.015 0.887± 0.070 0.214± 0.038 0.342± 0.049

H Wang 0.983± 0.008 0.522± 0.033 0.716± 0.022 0.985± 0.009 0.380± 0.052 0.546± 0.055

J Chen 0.995± 0.006 0.507± 0.055 0.709± 0.037 0.997± 0.004 0.155± 0.078 0.261± 0.109

J Dongarra 1.000± 0.000 0.196± 0.086 0.435± 0.087 1.000± 0.000 0.185± 0.087 0.305± 0.112

J Halpern 0.936± 0.029 0.090± 0.013 0.288± 0.021 0.897± 0.067 0.074± 0.013 0.135± 0.022

J Kim 0.984± 0.014 0.790± 0.038 0.881± 0.025 0.941± 0.067 0.490± 0.090 0.641± 0.088

J Lee 0.966± 0.020 0.699± 0.033 0.822± 0.023 0.846± 0.091 0.379± 0.083 0.517± 0.077

J Li 0.991± 0.008 0.608± 0.029 0.776± 0.020 0.979± 0.025 0.254± 0.044 0.402± 0.060

J Liu 0.988± 0.013 0.530± 0.033 0.723± 0.024 0.975± 0.032 0.182± 0.043 0.305± 0.063

J Mitchell 1.000± 0.000 0.256± 0.046 0.504± 0.046 1.000± 0.000 0.198± 0.053 0.328± 0.073

J Smith 0.994± 0.012 0.484± 0.041 0.693± 0.029 0.980± 0.046 0.175± 0.052 0.294± 0.074

J Wang 0.993± 0.006 0.534± 0.028 0.728± 0.020 0.992± 0.007 0.311± 0.052 0.471± 0.062

J Wu 0.995± 0.006 0.197± 0.034 0.441± 0.036 0.998± 0.003 0.076± 0.025 0.140± 0.041

J Zhang 0.994± 0.006 0.626± 0.033 0.789± 0.021 0.994± 0.007 0.409± 0.065 0.577± 0.068

L Zhang 0.987± 0.015 0.637± 0.055 0.792± 0.034 0.985± 0.017 0.496± 0.101 0.654± 0.088

M Chen 0.997± 0.006 0.345± 0.032 0.586± 0.028 0.999± 0.004 0.159± 0.031 0.273± 0.046

M Pedram 1.000± 0.000 0.067± 0.011 0.258± 0.022 1.000± 0.000 0.055± 0.012 0.104± 0.020

M Vardi 0.987± 0.014 0.163± 0.044 0.398± 0.050 0.987± 0.022 0.146± 0.045 0.252± 0.065

N Jennings 1.000± 0.000 0.118± 0.022 0.342± 0.032 1.000± 0.000 0.106± 0.022 0.190± 0.036

N Jha 1.000± 0.000 0.454± 0.109 0.670± 0.084 1.000± 0.000 0.448± 0.111 0.612± 0.109

N Lynch 1.000± 0.000 0.139± 0.034 0.370± 0.044 1.000± 0.000 0.128± 0.034 0.225± 0.053

P Yu 1.000± 0.000 0.199± 0.069 0.440± 0.071 1.000± 0.000 0.160± 0.074 0.271± 0.102’

Q Yang 0.971± 0.016 0.199± 0.020 0.439± 0.022 0.980± 0.013 0.101± 0.016 0.183± 0.027

S Jajodia 0.992± 0.010 0.177± 0.029 0.418± 0.033 0.998± 0.003 0.154± 0.038 0.265± 0.057

S Kim 0.981± 0.014 0.793± 0.037 0.882± 0.021 0.975± 0.022 0.686± 0.091 0.803± 0.064

S Lee 0.990± 0.009 0.649± 0.027 0.802± 0.017 0.984± 0.013 0.273± 0.043 0.426± 0.053

T Henzinger 1.000± 0.000 0.545± 0.153 0.731± 0.107 1.000± 0.000 0.540± 0.155 0.689± 0.136

W Wang 0.947± 0.035 0.460± 0.041 0.659± 0.035 0.803± 0.132 0.168± 0.034 0.276± 0.048

X Li 0.960± 0.014 0.506± 0.024 0.697± 0.015 0.825± 0.082 0.250± 0.042 0.380± 0.049

X Zhou 0.995± 0.010 0.529± 0.035 0.725± 0.023 0.996± 0.009 0.390± 0.039 0.559± 0.039

Y Chen 0.993± 0.006 0.554± 0.024 0.741± 0.017 0.991± 0.007 0.309± 0.045 0.470± 0.052

Y Liu 0.995± 0.006 0.613± 0.020 0.781± 0.013 0.995± 0.007 0.414± 0.052 0.583± 0.053

Y Wang 0.990± 0.012 0.576± 0.024 0.755± 0.015 0.969± 0.042 0.278± 0.047 0.429± 0.057

Y Yang 0.989± 0.007 0.468± 0.032 0.680± 0.024 0.978± 0.016 0.158± 0.032 0.270± 0.047

Y Zhang 0.982± 0.008 0.639± 0.036 0.792± 0.022 0.955± 0.038 0.287± 0.054 0.439± 0.062

Z Zhang 0.966± 0.020 0.483± 0.033 0.682± 0.021 0.922± 0.063 0.228± 0.055 0.363± 0.072

Média 0.988± 0.002 0.431± 0.011 0.628± 0.009 0.970± 0.006 0.261± 0.014 0.387± 0.015

48 Resultados e Discussões

a diminuir a fragmentação dos clusters, mas, ainda mantê-los tão puros quanto possível(mantendo o valor de ACP e pP igual a 1, para 11 grupos ambíguos).

Resultados obtidos sem a colaboração dos usuários

As Tabelas 5.6 e 5.7 mostram a média dos resultados obtidos pelo método propostosem usar colaborações de usuários, ou seja, foram executados todos os passos exceto oquarto passo. Comparando os resultados da Tabela 5.6 com os da Tabela 5.3, na DBLP,nota-se que os valores de K e pF1 aumentam cerca de 22% e 61%, respectivamente. Afragmentação dos clusters diminui, sendo que os valores de AAP e pR aumentam cercade 58% e 104%, respectivamente. Mas, a pureza dos clusters diminuem cerca de 5%para ambas métricas ACP e pP .

Tabela 5.6: Resultados (com desvio padrão) obtidos pelo Passo 5(Fusão declusters) para cada grupo ambíguo na DBLP

Grupos ambíguos ACP AAP K pP pR pF1

A Gupta 0.914± 0.037 0.588± 0.062 0.731± 0.029 0.910± 0.045 0.546± 0.089 0.677± 0.061

A Kumar 0.927± 0.095 0.495± 0.126 0.669± 0.049 0.902± 0.137 0.394± 0.189 0.514± 0.124

C Chen 0.867± 0.026 0.387± 0.028 0.579± 0.024 0.721± 0.061 0.164± 0.028 0.266± 0.037

D Johnson 0.894± 0.039 0.543± 0.063 0.695± 0.038 0.926± 0.040 0.561± 0.108 0.693± 0.083

J Martin 0.998± 0.010 0.634± 0.067 0.794± 0.043 0.995± 0.019 0.430± 0.123 0.591± 0.110

J Robinson 0.963± 0.029 0.546± 0.051 0.724± 0.030 0.950± 0.056 0.517± 0.065 0.666± 0.050

J Smith 0.873± 0.066 0.677± 0.037 0.768± 0.026 0.876± 0.111 0.732± 0.052 0.793± 0.054

K Tanaka 0.943± 0.049 0.662± 0.092 0.787± 0.044 0.948± 0.048 0.614± 0.146 0.733± 0.096

M Brown 0.971± 0.043 0.663± 0.099 0.799± 0.051 0.959± 0.057 0.628± 0.157 0.746± 0.108

M Jones 0.955± 0.029 0.570± 0.080 0.736± 0.051 0.944± 0.043 0.546± 0.112 0.685± 0.089

M Miller 0.942± 0.028 0.922± 0.018 0.932± 0.020 0.961± 0.033 0.958± 0.019 0.959± 0.020

Média 0.932± 0.011 0.608± 0.010 0.747± 0.008 0.918± 0.019 0.554± 0.019 0.666± 0.017

Na comparação das Tabelas 5.7 e 5.5 para a KISTI, o aumento dos valores deK e pF1são muito expressivos, cerca de 44% e 250%, respectivamente. Sobre os valores de AAP epR, o ganho é expressivo também, cerca de 116% e 250%, respectivamente. Mas, similara situação que ocorre na DBLP, na KISTI a pureza dos clusters diminui. Os valoresde ACP e pP caem cerca de 10% e 14%, respectivamente. A diminuição da pureza dosclusters em ambas as coleções ocorre devido a fusão de alguns clusters pertencentes àdiferentes autores reais. Então, as colaborações dos usuários são fornecidas ao métodopara melhorar os resultados e garantir que esse problema não ocorra.

Resultados e Discussões 49

Tabela 5.7: Resultados (com desvio padrão) obtidos pelo Passo 5 (Fusão declusters) para cada grupo ambíguo na KISTI

Grupos ambíguos ACP AAP K pP pR pF1

A Choudhary 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

A Gupta 0.877± 0.037 0.896± 0.029 0.886± 0.021 0.855± 0.043 0.913± 0.028 0.883± 0.031

D Eppstein 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

D Lee 0.750± 0.076 0.954± 0.093 0.843± 0.033 0.640± 0.116 0.958± 0.112 0.753± 0.059

H Chen 0.728± 0.038 0.943± 0.038 0.828± 0.033 0.602± 0.072 0.955± 0.056 0.737± 0.068

H Wang 0.836± 0.014 0.976± 0.028 0.903± 0.018 0.806± 0.034 0.985± 0.026 0.886± 0.030

J Chen 0.911± 0.033 0.934± 0.024 0.922± 0.017 0.958± 0.028 0.972± 0.020 0.965± 0.019

J Dongarra 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

J Halpern 0.848± 0.037 1.000± 0.000 0.921± 0.020 0.846± 0.037 1.000± 0.000 0.917± 0.022

J Kim 0.918± 0.047 0.883± 0.034 0.900± 0.024 0.744± 0.163 0.723± 0.073 0.722± 0.077

J Lee 0.944± 0.050 0.731± 0.067 0.829± 0.029 0.818± 0.127 0.475± 0.133 0.583± 0.080

J Li 0.930± 0.047 0.890± 0.115 0.906± 0.050 0.841± 0.109 0.891± 0.189 0.843± 0.098

J Liu 0.934± 0.068 0.823± 0.187 0.868± 0.090 0.933± 0.088 0.731± 0.347 0.758± 0.273

J Mitchell 1.000± 0.000 0.998± 0.005 0.999± 0.003 1.000± 0.000 1.000± 0.001 1.000± 0.001

J Smith 0.764± 0.057 0.872± 0.046 0.816± 0.045 0.711± 0.110 0.925± 0.040 0.802± 0.087

J Wang 0.832± 0.033 0.893± 0.024 0.862± 0.020 0.744± 0.060 0.840± 0.042 0.787± 0.036

J Wu 0.983± 0.013 0.882± 0.192 0.924± 0.117 0.988± 0.014 0.900± 0.232 0.922± 0.174

J Zhang 0.737± 0.029 0.961± 0.021 0.842± 0.015 0.550± 0.041 0.969± 0.022 0.701± 0.037

L Zhang 0.669± 0.034 0.987± 0.018 0.812± 0.023 0.485± 0.046 0.983± 0.026 0.649± 0.042

M Chen 0.836± 0.036 0.948± 0.026 0.890± 0.026 0.893± 0.057 0.991± 0.009 0.939± 0.035

M Pedram 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

M Vardi 0.985± 0.016 1.000± 0.000 0.993± 0.008 0.985± 0.016 1.000± 0.000 0.992± 0.008

N Jennings 1.000± 0.000 0.961± 0.014 0.981± 0.007 1.000± 0.000 0.961± 0.014 0.980± 0.008

N Jha 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

N Lynch 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

P Yu 0.982± 0.015 1.000± 0.000 0.991± 0.008 0.981± 0.016 1.000± 0.000 0.991± 0.008

Q Yang 0.911± 0.030 0.979± 0.014 0.945± 0.019 0.954± 0.021 0.995± 0.004 0.974± 0.013

S Jajodia 0.873± 0.022 1.000± 0.000 0.934± 0.012 0.871± 0.022 1.000± 0.000 0.931± 0.013

S Kim 0.901± 0.024 0.896± 0.031 0.898± 0.022 0.804± 0.062 0.913± 0.045 0.854± 0.045

S Lee 0.977± 0.022 0.829± 0.086 0.898± 0.038 0.971± 0.030 0.691± 0.204 0.790± 0.125

T Henzinger 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000 1.000± 0.000

W Wang 0.565± 0.044 0.913± 0.029 0.717± 0.027 0.328± 0.040 0.927± 0.032 0.483± 0.044

X Li 0.718± 0.036 0.910± 0.025 0.808± 0.021 0.518± 0.068 0.860± 0.047 0.643± 0.055

X Zhou 0.987± 0.014 0.957± 0.026 0.972± 0.017 0.979± 0.023 0.983± 0.022 0.981± 0.015

Y Chen 0.695± 0.044 0.880± 0.029 0.781± 0.030 0.516± 0.059 0.778± 0.050 0.619± 0.054

Y Liu 0.822± 0.136 0.855± 0.134 0.829± 0.020 0.785± 0.174 0.802± 0.209 0.752± 0.055

Y Wang 0.804± 0.076 0.911± 0.066 0.853± 0.019 0.693± 0.101 0.887± 0.112 0.765± 0.037

Y Yang 0.893± 0.029 0.965± 0.024 0.928± 0.015 0.858± 0.037 0.976± 0.018 0.912± 0.020

Y Zhang 0.835± 0.124 0.861± 0.146 0.838± 0.037 0.725± 0.202 0.745± 0.314 0.650± 0.138

Z Zhang 0.906± 0.036 0.868± 0.071 0.885± 0.031 0.898± 0.055 0.833± 0.120 0.858± 0.056

Média 0.884± 0.006 0.934± 0.013 0.905± 0.007 0.832± 0.008 0.914± 0.022 0.851± 0.015

50 Resultados e Discussões

Comparação do método proposto com os métodos de referência

As Figuras 5.1 e 5.2 mostram a comparação do método proposto, chamado de CCUF,com SANDRef e GOPFRef para ambas as métricas K e PF1 na coleção DBLP. Em cadaiteração, os usuários rotulam 3 (CCUF-3 e GOPFRef-3) ou 5 (CCUF-5 e GOPFRef-5) comparações para CCUF e autores para GOPFRef. No total foram executadas 8iterações. A iteração 0 corresponde a execução de CCUF e GOPFRef sem usar ascolaborações de usuários.

DBLP K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.60

0.65

0.70

0.75

0.80

0.85

0.90

0.95

1

●

●

●●

● ●● ●

●

● CCUF−5CCUF−3GOPFRef−5GOPFRef−3SANDRef

Figura 5.1: Comparação entre CCUF e os métodos de referência sob a métrica K naDBLP

Na coleção DBLP, sob a métrica K, CCUF-3 e CCUF-5 aumentam seu desem-penho em aproximadamente 11,48% e 15,29%, respectivamente (de K=0.74582 paraK=0.83145, com CCUF-3, e de K=0.74582 para K=0.85986, com CCUF-5). Sob a mé-trica pF1, CCUF-3 e CCUF-5 aumentam seu desempenho em cerca de 20,77% e 26,63%,respectivamente (de pF1=0.67352 para pF1=0.81344, com CCUF-3, e de pF1=0.67352para pF1=0.85292, com CCUF-5).

CCUF supera SANDRef após somente 3 iterações sob as métricas K e pF1. CCUF-3supera GOPFRef-3 em todas as iterações sob ambas as métricas. Depois de 8 iterações,o ganho obtido pelo CCUF-3 contra GOPFRef-3 é de aproximadamente 10,86% e 19,97%para as métricas K e pF1, respectivamente. Comparando CCUF-5 com GOPFRef-5,

Resultados e Discussões 51

DBLP PF1−Métrica

Iterações

PF

1

0 1 2 3 4 5 6 7 8

0.50

0.60

0.70

0.80

0.90

1

●

●

●

●● ●

●●

●

● CCUF−5CCUF−3GOPFRef−5GOPFRef−3SANDRef

Figura 5.2: Comparação entre CCUF e os métodos de referência sob a métrica pF1 naDBLP

em todas as iterações, CCUF-5 também supera GOPFRef-5 e, após 8 iterações, ganhaem cerca de 5,76% e 10,76% sob as métricas K e pF1, respectivamente. Após somente4 iterações, CCUF-5 supera GOPFRef-5 após 8 iterações sob a métrica pF1.

As Figuras 5.3 e 5.4 comparam o método proposto com os métodos de referência sobas métricas K e PF1, para a coleção KISTI. Na KISTI, CCUF supera todas os métodosde referência em todas as iterações rotulando 3 ou 5 comparações por iterações. Osresultados obtidos por CCUF sem a colaboração dos usuários é muito bom, K=0.905 epF1=0.851. Assim, o ganho após 8 iterações é menor comparado aos obtidos na coleçãoDBLP. Comparando com GOPFRef e SANDRef, após 8 iterações, os ganhos estão emtorno de 8,92% e 16,01%, respectivamente, sob a métrica K.

Quanto a eficiência do método proposto, o tempo computacional gasto para que osregistros de citações de toda a base (DBLP) sejam comparados entre si é em média de 0.2segundos, uma vez que a complexidade inicial é O(n2) sendo reduzida pela comparaçãodos registros de citações que contém nomes de autores similares. Com 50% dos registrosda base o treinamento, dos classificadores selecionados e a fusão automática utilizandoa combinação dos classificadores consomem em média 7 segundos e 61 segundos. Talavaliação foi realizada em um Intel Core i5 com 2.67GHz e 8GB de RAM.

52 Resultados e Discussões

KISTI K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.70

0.75

0.80

0.85

0.90

0.95

1

●● ● ● ● ● ● ● ●

● CCUF−5CCUF−3GOPFRef−5GOPFRef−3SANDRef

Figura 5.3: Comparação entre CCUF e os métodos de referência sob a métrica K naKISTI

KISTI PF1−Métrica

Iterações

PF

1

0 1 2 3 4 5 6 7 8

0.50

0.60

0.70

0.80

0.90

1

●

● ● ● ●● ● ● ●

● CCUF−5CCUF−3GOPFRef−5GOPFRef−3SANDRef

Figura 5.4: Comparação entre CCUF e os métodos de referência sob a métrica pF1 naKISTI

Resultados e Discussões 53

5.6 Discussões

Os classificadores combinados obtêm os mesmos resultados se

forem usados isoladamente?

Cada um dos 3 classificadores foi analisado separadamente, considerando todos os regis-tros de citações dos grupos ambíguos da DBLP para os quais a combinação dos classi-ficadores obteve predições confiáveis para a classe 1, isto é, as comparações entre doisregistros do mesmo autor real foram classificadas para a classe de interesse (c = 1). ATabela 5.8 mostra que as predições dos classificadores são complementares, de modo quepara cada autor um classificador pode ser especialista, mostrando uma discrepância paraos grupos ambíguos (dos 11 grupos ambíguos, SVM é especialista em 5 e ambos KNN eRF especialistas em 3). Mas se os classificadores forem combinados eles diminuem o erroem relação ao número total de instâncias, já que individualmente eles cometem erros emdiferentes instâncias para diferentes grupos ambíguos.

Tabela 5.8: Comparação do desempenho individual dos classificadores paraa coleção DBLP com o número de instâncias preditas para a classe 1 em cadaclassificador

Autores RF KNN SVM CombinaçãoA Gupta 261 258 192 300A Kumar 77 13 25 109C Chen 40 43 96 56D Johnson 236 224 266 374J Martin 4 3 7 7J Robinson 56 80 81 100J Smith 1928 2097 1856 2410K Tanaka 8 34 19 36M Brown 3 13 16 24M Jones 108 64 52 120M Miller 873 924 883 1015Total 3595 3732 3459 4551

54 Resultados e Discussões

Os ganhos do método proposto são obtidos devido somente à

colaborações de usuários?

Para responder esta questão, foram realizados experimentos sem o Passo 5 (Fusão declusters) e seus resultados são comparados com os resultados obtidos pela execuçãodo método sem o Passo 4 (Colaboração do Usuário) e executando todos os passos. AFigura 5.5 mostra os resultados para ambas coleções DBLP e KISTI. CCUF-3 e CCUF-5refere-se ao método proposto rotulando 3 e 5 comparações para cada iteração. CCUF(Passo 5) refere-se ao método sem a colaboração dos usuários. CCUF-3 (Passo 4) eCCUF-5 (Passo 4) executa todos os passos exceto o quinto passo (Fusão de clusters).

Nota-se que na coleção DBLP, o desempenho do método sem o Passo 5, i.e., CCUF-3(Passo 4) e CCUF-5(Passo 4), é no máximo igual ao desempenho somente pelo Passo5 sem as colaborações de usuários no Passo 4, i.e., CCUF (Passo 5). A combinaçãode todos os passos melhora o resultado final. Na coleção KISTI, como mencionadoanteriormente, os resultados obtidos sem a colaboração dos usuários já superam todosos outros métodos comparados em todas as iterações, assim a contribuição de usuáriosno resultado final é mínima.

Qual o impacto dos resultados se a contribuição de usuários não

é correta?

Para estudar o comportamento do método, foram realizados experimentos ilustradosnas Figura 5.6 e 5.7, usando a colaboração negativa, ou seja, quando o usuários rotulamincorretamente os pares de registros de citação tanto para o mesmo autor quanto paraautores diferentes.

As comparações submetidas aos usuários são rotuladas erroneamente, ou seja, noscasos em que as comparações indicam que os registros pertencem ao mesmo autor osusuários rotulam os dois registros comparados como pertencentes a autores diferentes.No caso contrário, das comparações indicando que os registros pertencem a autoresdiferentes os usuários rotulam os dois registros como pertencentes ao mesmo autor.CCUF3-1, CCUF3-2, CCUF3-3 e CCUF5-1, CCUF5-2, CCUF5-3,CCUF5-4, CCUF5-5propõem 3 e 5 comparações onde 1 até 5 exemplos são rotulados de forma negativa.

Tendo em vista o valor inicial de dúvidas rotuladas para cada iteração, nesses expe-rimentos foram rotulados negativamente uma grande quantidade de exemplos, cerca de

Resultados e Discussões 55

DBLP K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.40

0.50

0.60

0.70

0.80

0.90

1

●●

●●

● ●● ●

●

● CCUF−5CCUF−3CCUF (Passo 5)CCUF−5(Passo 4)CCUF−3(Passo 4)

(a) K-métrica para a coleção DBLP

DBLP PF1−Métrica

Iterações

PF

10 1 2 3 4 5 6 7 8

0.40

0.50

0.60

0.70

0.80

0.90

1

●

●●

●● ●

●●

●

● CCUF−5CCUF−3CCUF (Passo 5)CCUF−5(Passo 4)CCUF−3(Passo 4)

(b) PF1-métrica para a coleção DBLP

KISTI K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.40

0.50

0.60

0.70

0.80

0.90

1

● ● ● ● ● ● ● ● ●

● CCUF−5CCUF−3CCUF (Passo 5)CCUF−5(Passo 4)CCUF−3(Passo 4)

(c) K-métrica para a coleção KISTI

KISTI PF1−Métrica

Iterações

PF

1

0 1 2 3 4 5 6 7 8

0.40

0.50

0.60

0.70

0.80

0.90

1

●● ● ● ● ● ● ● ●

● CCUF−5CCUF−3CCUF (Passo 5)CCUF−5(Passo 4)CCUF−3(Passo 4)

(d) PF1-métrica para a coleção KISTI

Figura 5.5: Desempenho de CCUF sem a colaboração dos usuários e sem o Passo 5separadamente sob as métricas K e PF1 na coleções DBLP e KISTI

33% para CCUF-3 (1 de 3 dúvidas) e 20% para CCUF-5 (1 de 5 dúvidas).

Na coleção DBLP, considerando CCUF3-1 e CCUF5-1 não houve diminuição nodesempenho pois não há diferença estatística para as métricas avaliadas. Com exceção deCCUF3-1 sob a métrica pF1 que diminui o seu desempenho em 7,02% (de pF1=0.67352para pF1=0.62621).

56 Resultados e Discussões

DBLP K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.35

0.45

0.55

0.65

0.75

0.85

0.95

● ●●

● ● ● ● ● ●

●

CCUF3−1CCUF3−2CCUF3−3

(a) K-métrica com 3 dúvidas rotuladaspara a coleção DBLP

DBLP PF1−Métrica

Iterações

PF

10 1 2 3 4 5 6 7 8

0.35

0.45

0.55

0.65

0.75

0.85

0.95

●●

●● ●

●● ● ●

●

CCUF3−1CCUF3−2CCUF3−3

(b) PF1-métrica com 3 dúvidas rotuladaspara a coleção DBLP

DBLP K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.35

0.45

0.55

0.65

0.75

0.85

0.95

● ● ●● ● ● ●

● ●

●

CCUF5−1CCUF5−2CCUF5−3CCUF5−4CCUF5−5

(c) K-métrica com 5 dúvidas rotuladaspara a coleção DBLP

DBLP PF1−Métrica

Iterações

PF

1

0 1 2 3 4 5 6 7 8

0.35

0.45

0.55

0.65

0.75

0.85

0.95

● ● ●● ● ●

●●

●

●

CCUF5−1CCUF5−2CCUF5−3CCUF5−4CCUF5−5

(d) PF1-métrica com 5 dúvidas rotuladaspara a coleção DBLP

Figura 5.6: Desempenho de CCUF com a rotulagem negativa, sob as métricas K e PF1na DBLP

Na coleção KISTI, sob a métricaK, CCUF3-1 e CCUF5-1 diminuem seu desempenhoem aproximadamente 7,23% e 4,74%, respectivamente (de K=0.90589 para K=0.84031,com CCUF3-1, e de K=0.90589 à K=0.86287, para CCUF5-1). Sob a métrica pF1,CCUF3-1 e CCUF5-1 diminuem seu desempenho em cerca de 8,73% e 3,87%, res-

Resultados e Discussões 57

KISTI K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.65

0.75

0.85

0.95

●●

●●

●●

●● ●

●

CCUF3−1CCUF3−2CCUF3−3

(a) K-métrica com 3 dúvidas rotuladaspara a coleção KISTI

KISTI PF1−Métrica

Iterações

PF

10 1 2 3 4 5 6 7 8

0.65

0.75

0.85

0.95

●

●

●

●●

●●

● ●

●

CCUF3−1CCUF3−2CCUF3−3

(b) PF1-métrica com 3 dúvidas rotuladaspara a coleção KISTI

KISTI K−Métrica

Iterações

K

0 1 2 3 4 5 6 7 8

0.65

0.75

0.85

0.95

●●

●

●

●●

● ●●

●

CCUF5−1CCUF5−2CCUF5−3CCUF5−4CCUF5−5

(c) K-métrica com 5 dúvidas rotuladaspara a coleção KISTI

KISTI PF1−Métrica

Iterações

PF

1

0 1 2 3 4 5 6 7 8

0.65

0.75

0.85

0.95

●●

●●

● ●

● ●

●

●

CCUF5−1CCUF5−2CCUF5−3CCUF5−4CCUF5−5

(d) PF1-métrica com 5 dúvidas rotuladaspara a coleção KISTI

Figura 5.7: Desempenho de CCUF com a rotulagem negativa, sob as métricas K e PF1na KISTI

pectivamente (de pF1=0.8477 para pF1=0.77672, com CCUF3-1, e de pF1=0.8477 àpF1=0.81486, para CCUF5-1).

Na coleção DBLP, a rotulagem negativa não influencia no desempenho da desambi-guação, em relação aos resultados obtidos pelo método automático (somente pelo Passo

58 Resultados e Discussões

5, sem a colaboração de usuários). Na coleção KISTI, como os resultados do métodoautomático supera todos os outros métodos e as colaborações não o aumentam signi-ficativamente, a rotulagem negativa leva a uma pequena queda da eficácia do método.Estas observações podem ser sustentadas pelas características específicas de cada base,sendo que a DBLP acumula mais registros por autor do que a KISTI e em razão disso,a atribuição de padrões errados na classificação dos poucos registros para cada grupoambíguo pode prejudicar a desambiguação desta base.

Capítulo 6

Conclusão

Nesta dissertação, um novo método de desambiguação de nomes de autores é propostode modo a incluir colaborações de usuários e combinar de forma eficiente os resultadosde três classificadores.

As predições fornecidas pelos classificadores são usadas, juntamente com um limiarautomático, para agrupar citações de um mesmo autor. Para ajudar o método, emsituações onde ele tem dúvida, foi solicitado aos usuários que atribuíssem a comparaçãocorreta entre dois grupos de citações, isto é, se estes dois grupos pertencem ao um mesmoautor ou não.

O método foi comparado com dois métodos baseados na colaboração de usuários e,com poucas iterações e baixo esforço de rotulagem, supera todos os métodos compa-rados. A avaliação experimental mostra que os ganhos obtidos pelo método propostocontra os métodos comparativos atingem 6% à 20%. Nos experimentos em relação aodesempenho do método sob colaborações negativas dos usuários, ainda que com 33% e20% de exemplos rotulados, os resultados obtidos pelo método mostram que o impactoda colaboração negativa é baixo.

6.1 Trabalhos futuros

Como trabalhos futuros, a intenção é:

• Analisar as características das bases de dados aqui escolhidas, para melhor justi-ficar o comportamento dos resultados obtidos pelo método proposto nas questões

59

60 Conclusão

do desempenho dos passos individuais (Por que a KISTI obtém um desempenhoelevado sem o uso de colaborações dos usuários?) e da rotulagem negativa (Porque na KISTI a rotulagem negativa diminui o desempenho de desambiguação?);

• Comparar o método proposto com outros métodos representativos em desambi-guação de nomes de autores, mesmo não abrangendo colaborações de usuários noprocesso;

• Avaliar o método em outras bases de dados reais (BDBComp, ArnetMiner), bemcomo em outros domínios além da Computação, como por exemplo bases de dadoscom artigos médicos (PubMed);

• Estudar a aplicação do método na desambiguação de outras entidades, como porexemplo nomes de lugares (topônimos).

Referências Bibliográficas

Altman, N. S. (1992). An introduction to kernel and nearest-neighbor nonparametricregression. The American Statistician, 46(3):175–185.

Bhattacharya, I. and Getoor, L. (2007). Collective entity resolution in relational data.ACM Transactions on Knowledge Discovery from Data, 1(1):1–36.

Borgman, C. L. (1999). What are digital libraries? competing visions. InformationProcessing & Management, 35(3):227–243.

Breiman, L. (2001). Random forests. Machine learning, 45(1):5–32.

Carvalho, A. P., Ferreira, A. A., Laender, A. H. F., and Gonçalves, M. A. (2011).Incremental Unsupervised Name Disambiguation in Cleaned Digital Libraries. Journalof Information and Data Management, 2(3):289–304.

Cohen, W. W., Ravikumar, P. D., and Fienberg, S. E. (2003). A Comparison of StringDistance Metrics for Name-Matching Tasks. In Proceedings of the IJCAI-03 Workshopon Information Integration on the Web, pages 73–78, Acapulco, Mexico.

Cortes, C. and Vapnik, V. (1995). Support-vector networks. Machine Learning,20(3):273–297.

Cota, R. G., Ferreira, A. A., Gonçalves, M. A., Laender, A. H. F., and Nascimento, C.(2010). An unsupervised heuristic-based hierarchical method for name disambiguationin bibliographic citations. Journal of the American Society for Information Scienceand Technology, 61(9):1853–1870.

Culotta, A., Kanani, P., Hall, R., Wick, M., and McCallum, A. (2007). Author Di-sambiguation using Error-driven Machine Learning with a Ranking Loss Function. InProceedings of the International Workshop on Information Integration on the Web,pages 32–37, Vancouver, Canada.

61

62 REFERÊNCIAS BIBLIOGRÁFICAS

Ferreira, A. A., Gonçalves, M. A., and Laender, A. H. F. (2012a). A Brief Survey ofAutomatic Methods for Author Name Disambiguation. SIGMOD Record, 41(2):15–26.

Ferreira, A. A., Machado, T. M., and Gonçalves, M. A. (2012b). Improving authorname disambiguation with user relevance feedback. Journal of Information and DataManagement, 3(3):332–347.

Ferreira, A. A., Veloso, A., Gonçalves, M. A., and Laender, A. H. (2014). Self-trainingauthor name disambiguation for information scarce scenarios. Journal of the Associ-ation for Information Science and Technology, 65(6):1257–1278.

Ferreira, A. A., Veloso, A., Gonçalves, M. A., and Laender, A. H. F. (2010). EffectiveSelf-Training Author Name Disambiguation in Scholarly Digital Libraries. In Proce-edings of the 2010 ACM/IEEE Joint Conference on Digital Libraries, pages 39–48,Gold Coast, Queensland, Australia.

Godoi, T. A., da Silva Torres, R., Carvalho, A. M. B. R., Gonçalves, M. A., Ferreira,A. A., Fan, W., and Fox, E. A. (2013). A relevance feedback approach for the authorname disambiguation problem. In 13th ACM/IEEE-CS Joint Conference on DigitalLibraries, pages 209–218, Indianapolis.

Han, H., Giles, C. L., Zha, H., Li, C., and Tsioutsiouliklis, K. (2004). Two SupervisedLearning Approaches for Name Disambiguation in Author Citations. In Proceedingsof the 4th ACM/IEEE-CS Joint Conference on Digital Libraries, pages 296–305, NewYork, NY, USA.

Han, H., Xu, W., Zha, H., and Giles, C. L. (2005a). A hierarchical Naive Bayes MixtureModel for Name Disambiguation in Author Citations. In Proceedings of the 2005 ACMSymposium on Applied Computing, pages 1065–1069, Santa Fe, New Mexico, USA.

Han, H., Zha, H., and Giles, C. L. (2005b). Name Disambiguation in Author Citationsusing a K-way Spectral Clustering Method. In Proceedings of the 5th ACM/IEEEJoint Conference on Digital Libraries, pages 334–343, Denver, CO, USA.

Han, J. and Kamber, M. (2006). Data Mining: Concepts and Techniques. MorganKaufmann Publishers Inc., San Francisco, CA, USA.

Huang, J., Ertekin, S., and Giles, C. L. (2006). Efficient Name Disambiguation forLarge-Scale Databases. In Proceedings of the European Conference on Principles andPractice of Knowledge Discovery in Databases, pages 536–544, Berlin, Germany.

REFERÊNCIAS BIBLIOGRÁFICAS 63

Jain, A. K. and Dubes, R. C. (1988). Algorithms for clustering data. Prentice-Hall, Inc.

Kang, I.-S., Kim, P., Lee, S., Jung, H., and You, B.-J. (2011). Construction of a large-scale test set for author disambiguation. Information Processing and Management,47(3):452–465.

Klaas, V. C. (2007). Who’s who in the world wide web: Approaches to name disambi-guation. Master’s thesis, Diplomarbeit, LMU München, Informatik.

Kuncheva, L. I. (2004). Combining pattern classifiers: methods and algoritms. JohnWiley & Sons.

Lapidot, I. (2002). Self-Organizing-Maps with BIC for Speaker Clustering. Technicalreport, IDIAP Research Institute, Martigny, Switzerland.

Lee, D. (2007). Practical maintenance of evolving metadata for digital preservation:algorithmic solution and system support. International Journal on Digital Libraries,6(4):313–326.

Levandowsky, M. and Winter, D. (1971). Distance between sets. Nature, 234(5323):34–35.

Levenshtein, V. I. (1966). Binary codes capable of correcting deletions, insertions andreversals. Soviet physics doklady, 10(8):707–710.

Levin, M., Krawzyk, S., Bethard, S., and Jurafsky, D. (2012). Citation-based boots-trapping for large-scale author disambiguation. Journal of the American Society forInformation Science and Technology, 63(5):1030–1047.

Li, Y., Wen, A., Lin, Q., Li, R., and Lu, Z. (2011). Incorporating User Feedbackinto Name Disambiguation of Scientific Cooperation Network. In Proceedings of the12th International Conference on Web-age Information Management, WAIM’11, pages454–466, Wuhan, China.

Oliveira, J. (2005). Uma Estratégia para Remoção de Ambigüidades na Identificação deAutoria de Objetos Bibliográficos. PhD thesis, Dissertação de Mestrado, Departamentode Ciência da Computação, UFMG, Belo Horizonte.

Oliveira, L., Britto, A., and Sabourin, R. (2005). Improving cascading classifiers withparticle swarm optimization. In Document Analysis and Recognition, 2005. Procee-dings. Eighth International Conference on, pages 570–574. IEEE.

64 REFERÊNCIAS BIBLIOGRÁFICAS

On, B.-W., Elmacioglu, E., Lee, D., Kang, J., and Pei, J. (2006). Improving Grouped-Entity Resolution Using Quasi-Cliques. In Proceedings of the 6th IEEE InternationalConference on Data Mining, pages 1008–015, Hong Kong, China. IEEE ComputerSociety.

On, B.-W. and Lee, D. (2007). Scalable Name Disambiguation using Multi-level GraphPartition. In Proceedings of the 7th SIAM International Conference on Data Mining,pages 575–580, Minneapolis, Minnesota, USA.

Rijsbergen, C. J. V. (1979). Information Retrieval, 2nd edition. Butterworths, London.

Saha, S. and Ekbal, A. (2013). Combining multiple classifiers using vote based classifierensemble technique for named entity recognition. Data & Knowledge Engineering,85(Complete):15–39.

Soler, J. M. (2007). Separating the articles of authors with the same name. Scientome-trics, 72(2):281–290.

Torvik, V. I. and Smalheiser, N. R. (2009). Author name disambiguation in medline.ACM Transactions on Knowledge Discovery from Data, 3(3):1–29.

Veloso, A., Ferreira, A. A., Gonçalves, M. A., Laender, A. H., and Meira Jr., W. (2012).Cost-effective on-demand associative author name disambiguation. Information Pro-cessing & Management, 48(4):680 – 697.

Wang, X., Tang, J., Cheng, H., and Yu, P. (2011). ADANA: Active Name Disambi-guation. In Proceedings of the 11th International Conference on Data Mining, pages794–803, Vancouver,Canada.

Witten, I. H. and Frank, E. (2005). Data Mining: Practical machine learning tools andtechniques. Morgan Kaufmann.

Witten, I. H., Frank, E., Trigg, L., Hall, M., Holmes, G., and Cunningham, S. J. (1999).Weka: Practical machine learning tools and techniques with java implementations.