Preface

This is the presentation page for my master’s thesis project in Computer Science at the School of Computer Science and Engineering at the Royal Institute of Technology (KTH). The project was provided by Findwise AB, a company that specializes in search solutions, and most of the work was conducted in their office in Stockholm. I would like to thank Findwise, and especially my project provider Simon Stenström, for all the support and always making me feel welcome. I also want to thank my supervisor at KTH, Jussi Karlgren, for all his valuable insights and advice during the project.

Data

Report

Thesis Report - Final Version

Code

GitHub Repository

Resources

Stop words

DBpedia

ElasticSearch

MongoDB

Evaluation Datasets

Small Simple Wikipedia Dataset

Large Simple Wikipedia Dataset

Survey Data

Abstract

This report presents a subtopic extraction method using search engine technology, combined with graph centrality ranking of topic candidates. The implemented system uses Wikipedia as a knowledge base to extract and rank topic candidates. Multiple methods of topic extraction are evaluated. Primary methods based on search engine technology are explored. The use of a state-of-the art annotation system of Wikipedia concepts for topic extraction is also explored as comparison to previous work. In this project, the system DBpedia spotlight is used for this comparison. It is also evaluated how graph centrality algorithms can be used to improve the results from the system. This includes using algorithms like PageRank, Degree centrality, Closeness centrality and Betweenness centrality to rank the extracted topic candidates. A good ranking is achieved when relevant topic candidates are given a higher rank than less relevant topic candidates. A topic candidate is considered relevant if it is relevant to the given input data text

The system is implemented using the open source search engine ElasticSearch. The system is evaluated on abstracts from the Simple English Wikipedia. The results show that the system in 85% of the evaluated test cases finds the expected topic of the text in the top 10 ranked topic candidates. A survey was conducted where participants were asked to classify results from the system based on how well they matched a given text. The data from the survey shows that, in most cases, graph centrality ranking does improve the results noticeably, compared to only using the Term Frequency and Inverse Document Frequency (TF-IDF) ranking given by the search engine.

Referat

Delämnesextraktion med grafbaserade metoder

Denna rapport presenterar ett system för delämnesextraktion som använder sökmotorteknologi i kombination med grafcentralitet för att rangordna möjliga ämneskandidater. Det implementerade systemet använder Wikipedia som en kunskapsbas för att extrahera och rangordna möjliga ämnen. Flera metoder för ämnesextraktion undersöks. Primärt utforskas ämnesextraktion baserad på sökmotorteknologi. Som jämförelse med tidigare arbeten undersöks även hur ett ”state-of-the-art”-system för annotering av Wikipedia-koncept kan användas för ämnesextraktion. I detta projekt används systemet DBpedia spotlight för denna jämförelse. I rapporten utvärderas även hur grafcentralitet kan användas för att förbättra resultaten. Detta inkluderar användandet av algoritmer som PageRank, Degree-centralitet, Closeness-centralitet och Betweenness- centralitet för att rangordna de extraherade ämneskandidaterna. En bra rangordning motsvaras av att de relevanta ämneskandidaterna ges en högre rank än mindre relevanta resultat. En ämneskandidat är relevant om den kan anses vara ett representativt ämne för den givna indata-texten.

Systemet är implementerat med ”open source”-sökmotorn ElasticSearch. För att utvärdera systemet användes introduktionsstyckena från Simple English Wikipedia-artiklar. Resultatet visar att i 85% av de utvärderade testfallen finns det förväntade ämnet med bland de topp-10-rankade ämneskandidaterna. En undersökning genomfördes där deltagarna ombads klassifiera resultat från systemet baserat på hur väl de matchade en given text. Data från undersökingen visar att grafcentralitet, i de flesta fall, förbättrar resultaten märkbart, jämfört med att bara använda term-frekvens- och invers dokument-frekvens- (TF-IDF) rankingen given av sökmotorn.