Wissensexploration.de Knowledge Mining & Discovery: Text, Web und Data Mining, Suchtechnologien, explorative Datenanalyse
| Web Crawling Strategien und Information Retrieval im Web, fokussierte Web Crawler, semantisches Wissen
und Informationsextraktion | > Empowering Business Intelligence.
Web Such Algorithmen werden in (fokussierten) Web Crawlern dazu verwendet, um die optimale Reihenfolge zu bestimmen in der URLs besucht und verarbeitet werden. Eine Vielzahl an verschiedensten Algorithmen und Vorgehensmodellen wurden seit dem bestehen des Internets entwickelt. Im Folgenden werden die verschiedenen Ansätze wie folgt unterteilt:
Link-topologische Ansätze zur Bestimmung der optimalen URL-Reihenfolge unterteilen Baeza-Yates et. al (2002, S. 867) in 3 verschiedene Strategien, abhängig von den bereits vorhandenen Informationen:
(1) Strategien mit keinen zusätzlichen Informationen verwenden nur Informationen aus dem aktuellen Crawling Prozess. Dazu werden folgende Strategien beschrieben: „Breadth-First“, „Backlink-count“, „Batch-Pagerank“, „OPIC“ und „Larger sites first“.
Breadth-First Suche (Breitensuche) ist einer der einfachsten Algorithmen der für das Web Crawlen verwendet wird. Es wird keinerlei Heuristik verwendet, um URLs zu gewichten bzw. in der Abarbeitung zu bevorzugen. Alle URLs einer Seite werden sukzessiv in der Reihenfolge ihres Auffindens abgearbeitet; gefundene URLs auf tieferen Ebenen gelangen ans Ende der Warteschleife. Derartige Suchalgorithmen eignen sich nur sehr beschränkt zum Erstellen einer domänen-spezifischen Webseitensammlung unter der Annahme, dass im nahen Umfeld einer Seite auf relevante Seiten verlinkt wird. Bei zunehmender Suchtiefe verliert die Breitensuche ihren Fokus und findet übermäßig nicht relevante Dokumente (vgl. Qin, Zhou und Chau, 2004, S. 136)
Backlink-count: Bei dieser Strategie werden jene Seiten zuerst herunter geladen, auf die am meisten Links verweisen.
Die Batch-Pagerank Strategie berechnet in regelmäßigen Abständen einen Pagerank der bisher indexierten Seiten; Seiten mit hohem Pagerank werden zuerst abgearbeitet.
OPIC (On-line Page Importance Computation) ist eine Art gewichtete backlink-count Strategie. Jede Seite erhält zu Beginn einen bestimmten Wert („cash“) zugewiesen. Dieser wird auf alle Verweise gleichmäßig aufgeteilt; Seiten mit einem hohen Betrag (die von vielen Seiten verlinkt werden) werden bevorzugt abgearbeitet. Diese Strategie ist ähnlich dem Pagerank, jedoch weniger rechenintensiv und ohne zufällige Link Priorisierung. (vgl. Baeza-Yates et. al, 2005, S. 867)
Larger-sites-first („größere Seiten zuerst“) ist eine einfache Strategie, bei der Webseiten, die viele Links auf andere Seiten enthalten, bevorzugt abgearbeitet werden.
(2) Strategien mit historischen Informationen:
Darunter sind Strategien zu verstehen, die Relevanzwerte (z.B. den Pagerank) eines früheren Crawls verwenden, um die Priorität von neuen Seiten zu bestimmen. Moderne Suchmaschinen verwenden wahrscheinlich historische Informationen in irgendeiner Form, doch sind dazu weder exakten Mechanismen, noch deren Performance publiziert (vgl. Baeza-Yates et. al, 2005, S. 867).
(3) Strategien mit allen Informationen. Bei dieser Strategie wird ein allwissendes „Oracle“ vorausgesetzt, das den aktuellen Pagerank jeder Seite berechnet hat. Seiten mit dem höchsten Pagerank werden bevorzugt abgearbeitet.
Inhaltliche Analyse zur Bestimmung der URL-Reihenfolge Best-First Suchalgorithmen verwenden eine Heuristik (meist Ergebnisse aus Web Analysis Algorithmen) um gefundene URLs zu gewichten und arbeiten besser gewichtete URLs zuerst ab. Schlecht gerankte URLs werden am Ende der Warteschleife hinzugefügt. Der Vorteil gegenüber der Breitensuche ist die Vermeidung von irrelevanten Seiten, wodurch die Suche fokussiert bleibt (vgl. Qin, Zhou und Chau, 2004, S. 136). Da es sich um einen „Local Search“ Algorithmus handelt, läuft man mit Best-First Algorithmen jedoch Gefahr relevante Seiten, die sich „hinter“ irrelevanten Seite befinden, zu übersehen. Ein Lösungsansatz ist die bereits erwähnte „Tunneling“ Technik von Bergmark et al (2002): URLs irrelevanter Seiten werden dabei bis zu einer bestimmten Tiefe weiterhin abgearbeitet, wodurch eine Art „Tunnel“ zwischen relevanten Seiten geschaffen wird.
URL Text Durch die Analyse der URL kann die Abarbeitungsreihenfolge zudem gewichtet werden. Z.B. kann der URL „http://www.innsbruck.at/Webseiten/Statistiken_und_Zahlen/Tourismus“ entnommen werden, dass sie auf eine Seite zeigt, die sich mit Statistiken rund um den Tourismus in Innsbruck beschäftigt, in der AT-Domäne liegt und mit hoher Wahrscheinlichkeit auf Deutsch verfasst ist (vgl. Chau und Chen, 2003, S. 57).
URL Kontext Auch dieser Ansatz bewertet eine Webseite über dessen eingehende Links, ohne die Zielseite zu kennen. Dazu werden Ankertext, Ziel-URL und Merkmale in URL-Umgebung themenspezifisch klassifiziert. In Chakrabarti, Punera und Subramayam (2002) wird die URL-Reihenfolge und die Relevanz einer Seite von eigenständigen Modulen bestimmt. Das „Apprentice“ Module bestimmt dabei die Reihenfolge der Abarbeitung der einzelnen URLs. Dazu werden Merkmale in der Umgebung eines Links extrahiert und die Relevanz einer (noch unbekannten) Zielseite bestimmt. Die Reihenfolge der Abarbeitung wird letztlich durch die Relevanz der Ursprungsseite (baseline classifier) und die vom „Apprentice“ Modul bestimmte Relevanz bestimmt. Die Anzahl der falsch klassifizierten Seiten reduzierte sich in einem Experiment um 30-90% (vgl. Chakrabarti, Punera und Subramayam, 2002, S. 11).
Endlich! Fokussierte Web Crawler Software für die Praxis