Machine learning algorithms for visual pattern detection on web pages

Abstract

Diese Masterarbeit bearbeitet die Forschungsfrage, wie Webobjekte auf bisher unbekannten Webseiten robust identifiziert werden können. Das TAMCROW-Team stellt einen neuen Ansatz vor, um visuelle Charakteristika von Webobjekten und deren umliegenden Objekten zu verarbeiten. Dieser Ansatz ist unabhängig von Text-Labels und dadurch auch sprachunabhängig. Ein weiterer Vorteil ist, dass er mit einer geringeren Anzahl an Beispielen auskommt. Desweiteren sind visuelle Merkmale essentiel für die menschliche Wahrnehmung. Webusability hängt von dieser Wahrnehmung ab. Da der Erfolg eines Webauftritts von einer hohen Benutzerfreundlichkeit abhängt, sind Webdesigner bemüht, ihre Webseiten für die menschliche Wahrnehmung zu optimieren.<br />Für den Prozess der Objektidentifizierung werden supervised Machine-Learning-Techniken eingesetzt. Dabei ist das Wissen auf Eigenschaften beschränkt, welche die visuellen Attribute eines Webobjektes beschreiben. Eine zusätzliche Frage ist, ob es möglich ist, dass Webobjekte anhand von ihrer visuellen Erscheinung klassifiziert werden können. Im Rahmen dieser Masterarbeit wurden folgende Machine-Learning-Techniken im Detail für den oben beschriebenen Einsatz untersucht: Logistische Regression, K-Nearest-Neighbor, Klassifizierungsbäume (c.4.5 von Quinlan) und Support-Vector-Machines.<br />Für die letztgenannte Technik wurden folgende Kernelfunktionen verwendet: linear, polynomisch, radial und sigmoid. Darüber hinaus, werden unterschiedliche Techniken für die Datenaufbereitung und die erforderlichen Parameteroptimierungen für einige der oben beschriebenen Techniken erläutert.<br />Andere wissenschaftliche Ansätze lösen ähnliche Probleme mit einem regelbasierten Ansatz (siehe [24,37,94]) oder wie in dieser Masterarbeit mit Machine-Learning-Techniken (siehe [56, 74, 75]). Grundsätzlich ist es nicht möglich die Resultate der anderen Arbeiten direkt zu vergleichen, da die Webpage-Korpora und die Ziele nicht genau übereinstimmen.<br />Die Resultate dieser Arbeit finden sich im Kaptel \ref{ch:evaluationResults}. Sie zeigen, dass der Ansatz des TAMCROW-Teams äußerst vielversprechend ist. Der Workflow für die Identifizierung von Webobjekte wird in mehreren Szenarien evaluiert.<br />Diese Szenarien beinhalten eine Suche nach Bussen, Flügen und Zügen, sowie eine für Unterkünfte. Im Weiteren wurde eine k-page cross-validation angewendet, um die Ergebnisse zu bewerten. Als Leistungsmerkmal wurde der Mittelwert der Präzision (precision) verwendet. Die Resultate sind für alle Klassifikationstechniken beachtlich. Besonders die support vector machine mit der radialen und polynomischen Kernelfunktion können durch exzellente Ergebnisse überzeugen.<br />Diese beachtlichen Klassifikationsraten basieren auf folgenden Begründungen: Das TAMCROW-Projekt verwendet eine vielfältige Auswahl an visuellen Eigenschaften, besonders im Vergleich mit anderen Arbeiten. Es scheint, als ob die Klassfikationsalgorithmen dadurch leichter zu unterscheiden lernen. Weiters ist die Verwendung einer Distanzberechnung, welche im Kapitel~\ref{ch:featDistances} erklärt wird, zum einen äußerst hilfreich, um die Anzahl der positiven Beobachtungen zu erhöhen und zum anderen werden einige Eigenschaften dadurch erst quantifizierbar (z.B. Farbe und Text). Als zusätzlichen Punkt lässt sich anführen, dass durch das Postprocessing die Ergebnisse der einzelnen Klassifikationsalgorithmen robust gegen falsche Klassifizierung werden.<br />

In this thesis the question how to robustly identify web objects across different sites is tackled. TAMCROW introduces a novel approach exploiting visually perceivable characteristics of a web object and its surrounding objects. This approach is entirely independent of textual labels, and hence has the noteworthy advantage of being language-agnostic. Another main advantage of the visual detection approach is sample parsimony. Fewer examples are required for the learning process to learn how to find certain web objects on previously unknown pages. Moreover, visual cues are crucial for the human perception and as a consequence also for the usability of a web page.<br />Therefore, web designers create web pages coherent with the human perception in order to yield a high usability.<br />Supervised machine learning techniques are applied for the object identification process. The knowledge is limited to features representing the visual appearance of the different web objects. An additional question is whether it is possible to predict the role of a web object by its visual appearance which is formally a classification problem. Within the scope of this master thesis, the following machine learning techniques are investigated in detail: logistic regression, k~nearest-neighbor, classification trees (in particular, c4.5 of Quinlan) and support vector machines. For support vector machines the following kernels are applied: linear, polynomial, radial and sigmoid.<br />Furthermore, different techniques for data preprocessing/preparation and parameter optimization for some of the classification techniques mentioned above are discussed.<br />Other scientific papers solve similar problems with either a rule-based approach (see [24,37,94]) or like this master thesis, with machine learning techniques (see [56, 74, 75]). In general, it is not possible to compare the results of these scientific papers directly since the web page corpora and aims are differnt.<br />Possible reasons for the favorable classification results are the following ones: Firstly, the TAMCROW project uses a vast number of visual features especially compared with other approaches. Therefore, the different classification algorithms seem to learn more easily how to distinguish between the different web objects. Secondly, the methodology of the distance computation (introduced in chapter~\ref{ch:featDistances}) helps to exponentially increase the number of positively classified observations on the one hand and makes some features numerically comparable on the other hand (e.g. color, text). Thirdly, the postprocessing applied after the classification makes the results very robust against misclassifications.<br />