Non IT configurable adaptive data mining solution used in transforming raw data to

structured data

Bachelor’s Thesis in Artificial Intelligence Radboud University Nijmegen

Franc Grootjen  Alessandro Paula
RU  Hyperleap

Mart Lubbers s4109053

November 3, 2014

Contents

1 Introduction 7 1.1 Hyperleap and their methods . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Goal & Research question . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Why RSS/Atom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.4 Scientific relevance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2 Methods 9 2.1 Application overview and workflow . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Input application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.1 Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Crawler application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.2 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3.3 Directed acyclic graphs(DAG) . . . . . . . . . . . . . . . . . . . . . 10 2.3.4 Defining categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.5 Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3 Conclusion 13 3.1 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

4 Appendices 15 4.1 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Abstract

5

1 Introduction

1.1 Hyperleap and their methods

Hyperleap^{1} is a small company founded in the early years of the internet and is located in Nijmegen. Hyperleap is a company that presents infotainment. Infotainment is a concatenation of the words entertainment and information and is a specialized form of information, namely about the entertainment industry. Hyperleap manages the largest database containing infotainment containing over 10.000 events per week on average. It also manages a database containing over 54.000 venues delivering the entertainment. Next to the factual information, Hyperleap also provides reviews, previews, background information and more via several popular websites specialized on genres or categories.

Hyperleap stands compared to other infotainment providers because of the quality and completeness of the data is comparatively high. This is because all information is checked and matched to existing information before it enters the database. To ensure the quality of the databases all information enters the database in roughly two steps.

In the first step the information is extracted from the raw data sources using crawlers or via venue channels. Crawlers are specialized applications that are programmed to extract information from one single source. Venue channels are specially made XML feeds that contain already very structured information. The extracted information is put in the so called Temporum, the Temporum is a stopping place for the gathered information before it is entered in the real database.

The second step in the path of the information is the matching of the data. This step is the actual quality checking and matching. Using several techniques, employees have to match the incoming information to existing events or create new events. This is also a safety net for malfunctioning crawlers, when a crawler provides wrong information in the Temporum the programmer of the crawler has to be informed then. A large amount of the time the programmers are busy with repairing crawlers because it is a specialized task only doable by people with a computer science background. Because of this it is expensive to repair the crawlers.

1.2 Goal & Research question

1 Introduction

The goal of the project is to relieve the programmer of repairing crawlers all the time and make the task of adapting, editing and removing crawlers doable for someone without programming experience. In practice this means building an application that lets the user create, edit or remove crawlers. For this project we focus on RSS^{2} and Atom^{3} publishing feeds only. The program will maintain crawlers that are able to isolate categories of information so that the information will appear structured in the Temporum and make the task of matching the data and entering it less expensive.

1http://hyperleap.nl

The program is built so that a programmer can easily add fields or categories to the application to reduce programming costs and complex modifications.

1.3 Why RSS/Atom

Information from venues comes in various different format with for each format several positive and negative points. For this project we chose to focus on RSS/Atom feeds because they are in general already structured and consistent in their structure. For example websites change a lot in structure and layout and thus making it hard to keep crawlers up to date. RSS/Atom feeds generally only change structure because the website or content management system gets migrated or upgraded.

RSS/Atom feeds in comparison to websites doesn’t have a structural dimension in the data. Because of this we have to use different techniques of isolation of information than present techniques used for extracting information from websites. RSS/Atom feeds are basically two fields with plain text, however the text almost always has the same structure and keywords and therefore the information can be extracted learning from keywords and structure.

1.4 Scientific relevance

Currently the techniques for conversion from non structured data to structured data are static and mainly only usable by computer science experts. There is a great need of data mining in non structured data because the data within companies and on the internet is piling up and are usually left to catch dust.

The project is a side project of the past project done by Roelofs et al.[3]. Roelofs et al. describes a technique to recognize date strings using an adapted Levensteins algorithm. This technique can be fitted in the current project because it works on a low level and the technique we describe works on a high level. The algorithm only works on already isolated data.

2http://rssboard.org/rss-specification 3http://tools.ietf.org/html/rfc5023

2 Methods

2.1 Application overview and workflow

The program can be divided into two main components namely the Crawler application and the Input application. The components are strictly separated by task and by application. The crawler is an application dedicated to the sole task of periodically crawling the sources asynchronously. The input is a web interface to a set of tools that can create, edit, remove and test crawlers via simple point and click user interfaces that can be worked with by someone without a computer science background.

2.2 Input application

2.2.1 Components

Add new crawler Editing or remove crawlers Test crawler Generate xml

2.3 Crawler application

2.3.1 Interface

2.3.2 Preprocessing

When the data is received by the crawler the data is embedded as POST data in a HTTP request. The POST data consists of several fields with information about the feed and a container that has the table with the user markers embedded. After that the entries are extracted and processed line by line.

The line processing converts the raw string of html data from a table row to a string. The string is stripped of all the html tags and is accompanied by a list of marker items. The entries that don’t contain any markers are left out in the next step of processing. All data, including entries without user markers, is stored in the object too for possible later reference, for example for editing the patterns.

2 Methods

The last step is when the entries with markers are then processed to build node-lists. Node-lists are basically lists of words that, when concatenated, form the original entry. A word isn’t a word in the linguistic sense. A word can be one letter or a category. The node-list is generated by putting all the separate characters one by one in the list and when a user marking is encountered, this marking is translated to the category code and that code is then added as a word. The nodelists are then sent to the actual algorithm to be converted to a graph representation.

2.3.3 Directed acyclic graphs(DAG)

Directed acyclic graphs are a special kind of graph that is used to store big sets of words and has a complexity of O(L), meaning the length of the word you are searching. Figure 2.1 shows a DAG that accepts the words aa and ab. Final states are marked with a double circle and intermediate states are marked with a single circle.

Figure 2.1: Sample DAG

The first algorithm to generate DAG’s was proposed by Hopcroft et al[2]. The algorithm they described wasn’t incremental and had a complexity of O(N log N). [1] et al. later extended the algorithm and created an incremental one without increasing the computational complexity. The non incremental algorithm from Daciuk et al. is used to convert the nodelists to a graph.

For example constructing a graph that from the entry: a,bc and a.bc goes in the following steps:

Figure 2.2: Sample DAG, first entry

2.3 Crawler application

Figure 2.3: Sample DAG, second entry

2.3.4 Defining categories

pass

2.3.5 Process

Proposal was written First html/mail/fax/rss, worst case rss After some research and determining the scope of the project we decided only to do

RSS, this because RSS tends to force structure in the data because RSS feeds are often generated by the website and thus reliable and consistent. We found a couple of good RSS feeds.

At first the general framework was designed and implemented, no method yet. Started with method for recognizing separators. Found research paper about algorithm that can create directed acyclic graphs from

string, although it was designed to compress word lists it can be (mis)used to extract information.

Implementation of DAG algorithm found and tied to the program. Command line program ready. Conversation with both supervisors, gui had to be

made.

Step by step gui created. Web interface as a control center for the crawlers. Gui optimized. Concluded that the program doesn’t reach wide audience due to lack of well structured

rss feeds.

3 Conclusion

3.1 Discussion

4 Appendices

4.1 Algorithm 4.2 Progress

Bibliography

[1] Jan Daciuk, Stoyan Mihov, Bruce W. Watson, and Richard E. Watson. Incremental Construction of Minimal Acyclic Finite-State Automata. Computational Linguistics, 26(1):3–16, March 2000.

[2] John Hopcroft. An N log N algorithm for minimizing states in a finite automaton. Technical report, 1971.

[3] Wouter Roelofs, Alessandro Tadeo Paula, and Franc Grootjen. Programming by Clicking. In Proceedings of the Dutch Information Retrieval Conference, pages 2–3, 2009.