Machine learning approach for Web ranking identification based on visual features

Abstract

In dieser Arbeit beschreiben wir Wres, ein System um Informationen in Web Rankings zu identifizieren und zu extrahieren. Web Rankings sind geordnete Listen von Webobjekten, die häufig auf Webseiten verwendet werden. Unser System benutzt visuelle Eigenschaften, um diese Objekte zu identifizieren, indem es deren gemeinsame Designsprache bedient. Daher können wir mit einer geringen Menge an Beispielen einen Klassifizierer trainieren und damit Daten von Webseiten mit einem anderen Quelltext extrahieren. Wir präsentieren auch eine Erweiterung für Google Chrome, um Beispiele von Web Rankings zu annotieren. Die Wres Annotation Erweiterung haben wir mit einer großzögigen Open Source Lizenz veröffentlicht. Sie basiert auf W3C Standards. Durch die Annotierung direkt in einem kommerziellen Browser können wir unser Annotierungswerkzeug rasch an neue Versionen des Browsers anpassen und stets die gleiche Browser-Version wie ein Großteil der Benutzer_innen verwenden. Mit unserem Annotierungswerkzeug haben wir ein Trainingsset erstellt, das Beispiele von verschiedenen, häufig gebrauchten Layouts von Web Rankings enthält. Wir stellen außerdem ein Modell vor, um Web Rankings formal zu beschreiben. Semi-supervised Machine Learning Techniken werden benutzt um Klassifizierer für die Web Ranking Identifizierung zu erstellen. Für das Training und die Ausführung des Klassifizierers setzen wir Weka ein. Unsere Arbeit enthält eine Beschreibung von supervised und semi-supervised Techniken. Zusätzlich beschreiben wir die folgenden Machine Learning Techniken im Detail: Decision Tree, Random Forests, PART Rule-learning algorithm und Support Vector Machines. Wir werten unsere Klassifizierer aus und vergleichen die Resultate der verschiedenen Machine Learning Techniken. In unserer Auswertung zeigen wir, dass unser System am besten für Label funktioniert, die mehrere Male wiederholt werden und markante visuelle Kennzeichen besitzen. Mit dem Random Forest Algorithmus können wir eine Präzision von 0.9427 für wiederholende Label und eine Präzision von 0.7573 für nicht wiederholende Label erzielen. Zusätzlich vergleichen wir unser System mit zwei kommerziell verfügbaren, proprietären Web Extraction Systemen: Diffbot und Import.io. Die Analyse der Leistungen dieser beiden Systeme hat gezeigt, dass Diffbot keine geeignete Lösung ist um Web Rankings zu extrahieren, da es nur Daten von 2% der Webseiten in unserem Datenset Rankings extrahieren konnte. Import.io kann von 53% der Webseiten in unserem Datenset Web Rankings extrahieren; die Leistung ist hier abhängig von der Art der Web Rankings. Wir haben beobachtet, dass unser System mit 71% korrekt extrahierten Web Rankings die Web Data Extraction Systeme Diffbot und Import.io übertrifft, indem wir uns auf Web Rankings spezialisieren.

In this thesis, we introduce an approach to web ranking extraction, which is based on the analysis of visual features. Web rankings are ordered lists of web objects that are commonly used on websites. Our system uses visual features to identify these objects based on the fact that web rankings share a strong visual language. Therefore we can efficiently train a classifier with a small set of examples and extract data from websites with a different source code. We also present an extension for Google Chrome to annotate examples of web rankings. The Wres Annotation Extension is available publicly under a permissive Open Source license and relies on W3C standards. Using our annotation tool we build a training set containing examples using commonly used web ranking layouts, namely table, list, simple list, grid and tiling layouts. We also present a model to formally describe web rankings. Semi-supervised machine learning techniques are used to build classifiers for web ranking identification. We use Weka to train and run our classifiers throughout the thesis. Our thesis includes description of supervised and semi-supervised techniques. In our comparison of Machine Learning algorithms we include BayesNet, NaiveBayes, LibSVM, MultilayerPerceptron, SimpleLogistic, IBk, KStar, LWL, DecisionTable, JRip, OneR, PART, ZeroR, DecisionStump, HoeffdingTree, J48, LMT, RandomForest, RandomTree, and REPTree. We evaluate our classifiers and compare the results of different machine learning techniques. In our evaluation we found that our system works best for labels that repeat multiple times and have a distinctive visual representation. With the Random Forest algorithm we could achieve a precision of 0.9427 for repeating labels and a precision of 0.7573 for non-repeating labels. Addtionally we compare our system to two commercial available, proprietary web extraction systems: Diffbot and Import.io. We analyze the performance of both these systems and find that Diffbot is not an appropriate solution to extract web rankings since it can only extract data from 2% of rankings in our dataset. Import.io can extract web rankings from 53% of web pages in a our dataset, with better performance for some types of web rankings and worse for others. We found that our system outperforms Diffbot and Import.io with 71% correctly extracted web rankings by specialising solely on web rankings.