Web Analyse Algorithmen für fokussierte Web Crawler. Link-basierte und Inhalts-basierte Algorithmen, URL-Reihenfolge

Web Analyse Algorithmen

Fokussierte Web Crawler basieren auf zwei Arten von Algorithmen um den Fokus auf eine Domäne zu behalten:
Web Analysis Algorithmen werden verwendet, um die Relevanz und Qualität einer Webseite zu bewerten; Web Search Algorithmen, um die optimale Rangfolge zu bestimmen, in der neue URLs abgearbeitet werden.
Diese sind bei einer fokussierten Websuche meist voneinander abhängig; die optimale Rangfolge wird durch die qualitative Analyse der Inhalte beeinflusst.
Web Analysis Algorithmen werden in link-basierte und inhalt-basierte Ansätze unterteilt (vgl. Chau und Chen, 2003, S. 56).

Springen Sie: zu den Lernszenarien für Web Analyse Algorithmen.

Link-Basierte Algorithmen: Die Bedeutung der Web-Struktur

Die Linkstruktur zwischen Webseiten kann, wie bereits erwähnt, dazu benutzt werden die Relevanz und Qualität einer Webseite global zu bewerten. Ähnlich wie beim „Science Citation Index“ werden häufig zitierte bzw. verlinkte Dokumente als wichtiger eingestuft. Unter der Annahme, dass ein Hyperlink eine Empfehlung (bzw. Zitierung) des Autors der Webseite für eine andere Webseite ist, wird eine häufig verlinkte Seite höher bewertet (vgl. Lewandowski, 2005, S. 118).
Co-Citation ist ein weiteres Konzept aus dem „Citation Analysis“ Bereich. Zwei Webseiten sind „co-cited“, wenn sie beide von einer Webseite verlinkt werden. Häufig co-zitierte Webseiten sind verwandt und werden dem gleichen Thema zugeordnet (vgl. Kleinberg, 1998, S. 19). Dies ist vor allem in Domänen hilfreich, deren Webautoren bewusst vermeiden zu anderen relevanten Webseiten zu linken (bspw. in der Tourismusbranche vermeiden Hotelanbieter auf andere konkurrierende Hotels zu verweisen).
Die bekanntesten link-basierten Web Analyse Algorithmen sind PageRank und HITS und werden im Folgenden kurz vorgestellt.
Pagerank (vgl. Page et. al, 1998) ist ein essentieller Bestandteil des Google Ranking-Algorithmus und basiert im Wesentlichen auf der quantitativen Analyse eingehender und ausgehender Links. Die Idee, dass eine Webseite A, eine Webseite B durch einen Hyperlink empfiehlt wird dadurch erweitert, dass Hyperlinks von wichtigen Seiten (mit hohem Pagerank) höher bewertet werden. Die Relevanz (der Pagerank) einer Seite wird demnach rekursiv berechnet: Der Pagerank einer Seite basiert auf dem Pagerank anderer Seiten und beeinflusst ihn gleichzeitig. Anders formuliert erreicht ein Websurfer (sog. „random surfer“), der Links auf Webseiten rein zufällig auswählt, eine Webseite mit einer bestimmten Frequenz. Diese Häufigkeit ist proportional mit dem PageRank einer Seite (vgl. Arasud et. al, 2000, S. 28-32).
Der Pagerank Algorithmus teilt also jeder Webseite einen globalen Prestige-Wert für seine Relevanz zu.
Der HITS (Hypertext Induced Topic Search) Algorithmus (Kleinberg et al, 1998) ist hingegen von einer bestimmten Suchabfrage abhängig und bestimmt für einen Teilbereich des Webs (limitiert durch die Suchabfrage) zwei Werte für die Relevanz einer Webseite: Seine Autorität (authority) und seine Funktion als „Knoten“ bzw. Mittelpunkt (hub). Autoritäre Seiten sind qualitativ hochwertig und inhaltsreich; Hub Seiten enthalten umfassende Listen von Verweisen auf autoritäre Seiten (vgl. Chakrabarti, 2003, S. 212ff). Hub Seiten sind nicht zwangsweise direkt relevant für eine Suchabfrage, zeigen aber auf viele autoritäre Seiten. Sie werden einerseits dazu verwendet die Autorität einer Seite zu berechnen und können andererseits selbst in der Ergebnisliste einer Suchabfrage sein (vgl. Arasud et al, 2000, S. 32 ff).
Der Hauptunterschied von HITS und PageRank sind die hubs. PageRank hat kein Konzept für hubs. Dies ist jedoch nicht zwangsweise als Nachteil zu sehen, möglicherweise deshalb, weil im Web gute hubs (z.B. umfassende Linksammlungen) bald eine signifikante Menge an eingehenden Verweisen anhäufen und deshalb einen hohen PageRank erhalten (vgl. Chakrabarti, 2003, S. 214).

Inhalts-Basierte Algorithmen

Die Klassifizierung von Hypertext Dokumenten ist eine fundamentale Technik, Daten aus dem Web zu verarbeiten und zu organisieren. Allgemein betrachtet kann das klassifizieren weitgehend manuell durch Experten erfolgen, wie dies oft in Webverzeichnissen, z.B. dmoz.org, der Fall ist. Manuelles Klassifizieren ist ein enormer zeitlicher Aufwand und in Anbetracht der Datenmengen im Web unpraktisch zur Erstellung einer domänenspezifischen Dokumentbasis (Subramanian, 2005, S. 1).

Automatische Klassifizierung wird auch „überwachtes Lernen“ (supervised learning) genannt, dabei wird im ersten Schritt eine Trainingsbasis erstellt in der eine Reihe von Dokumenten bestimmten Klassen zugeordnet werden. Neue Dokumente werden anhand von statistischen Methoden und Lernmodellen den vordefinierten Klassen zugeordnet (vgl. Kapitel Data Mining). Die Vorgehensweise bei der Klassifikation von Text ist folgende: Aus einer bereits klassifizierte Teilmenge an Dokumenten werden Merkmale (z.B. Wörter oder Phrasen) extrahiert, die für den Klassifizierer als Trainingsbasis zur Verfügung gestellt werden. Neue Dokumente werden durch diesen Klassifizierer der Klasse zugeordnet, die am besten mit den Merkmalen des Dokuments übereinstimmt (vgl. Glover et. al, 2002, S.3).

Für Hypertext Dokumente ist es nützlich verschiedenste Features für die Repräsentation von Hypertext Dokumenten zu sammeln und zu kombinieren: herkömmliche Begriffe (im eigentlichen Text), Begriffe im Titel, Header-Informationen, Ankertexte, die Struktur der HTML tags in denen Begriffe eingebettet sind, Begriffe aus benachbarten Seiten, Verweise von und zu Seiten die bereits klassifiziert sind. Aus den Hypertexten werden verschiedene Merkmale extrahiert, die dann eine Klasse bzw. ein Thema formell beschreiben (vgl. Chakrabarti, 2003, S. 129ff). Es hat sich zudem als nützlich herausgestellt, anstatt bzw. zusätzlich zum eigentlichen Text der Webseite, Ankertexte und andere Merkmale von Seiten zu verwenden, die auf eine Seite verlinken (vgl. Fürnkranz, 1999, S. 1ff).

Fürnkranz (1999) verwendet anstatt dem eigentlichen Text einer Webseite Informationen von benachbarten Seiten, die auf die Seite zeigen. Dies sind neben dem Ankertext (Text zwischen dem Tag "a") auch vorangestellte Überschriften und der Text im selben Paragraph ("p" Tag) wie der Link. Die Klassifikation erfolgt also durch Ankertexte und Texte in dessen Umgebung von Webseiten, die auf (die zu klassifizierende) Webseiten verlinkt.
Die Ergebnisse zeigen, dass sich die Genauigkeit der Klassifikation signifikant erhöht im Vergleich zur Klassifikation anhand des eigentlichen Textes einer Webseite. Die Verwendung des gesamten Inhalts von Nachbarseiten schadet jedoch der Genauigkeit der Klassifizierung (vgl. Glover et. al, 2002, S. 3). Auch die Verwendung des Ankertextes allein bringt keine signifikante Verbesserung der Klassifikation (vgl. Glover et. al, 2002, S. 15).

Glover et. al (2002, S. 11ff) stellt für eine Kombination von Seiteninhalt und erweiterten Merkmalen der auf die Seite verweisenden Ankertexte, eine signifikante Verbesserung der Klassifizierungsgenauigkeit der positiv klassifizierten Webseiten fest.

Sun, Lim und Ng (2002, S.98-99) zeigen, dass die Verwendung von HTML-Tags – insbesondere Ankertext und Text in dessen Umgebung und Title-Tag – die Klassifizierungsgenauigkeit signifikant erhöhen kann.

Die Verwendung von „externen“ Merkmalen setzt jedoch voraus, dass eine Seite eingehende Links hat bzw. diese gefunden wurden. Dazu muss ein wesentlicher Teil einer Domäne bzw. des Webs indexiert werden.

Lernszenarien für die Text-Klassifizierung

Die IR Forschungsgemeinde hat verschiedene Methoden und Lernszenarien für die Text-Klassifizierung untersucht: Nearest Neighbor (NN) Klassifikator, Naive Bayes Klassifikator, Maximums-Entropie-Methode, Support Vektor Maschinen (SVM), neuronale Netze. Im Folgenden werden NN, naive Bayes und SVM hinsichtlich ihrer Eignung zur Textklassifikation kurz vorgestellt.

Die Kernidee des Nearest Neighbor (NN; deut. „Nächster Nachbar“) Modells ist, dass die Eigenschaften eines bestimmten Elements ähnlich sind wie die Eigenschaften von Elementen in dessen „Nachbarschaft“. Schwierig ist dabei die Definition dieser „Nachbarschaft“ (vgl. Subramanian, 2005, S.4-5). Werden Dokumente anhand des Vektorraummodells dargestellt, ist es möglich die Ähnlichkeit zwischen diesen Vektoren bzw. Dokumenten zu bestimmen (vgl. Subramanian, 2005, S.5). Für die Klassifizierung wird eine Trainingsbasis benötigt, in der Dokumente bereits korrekt den korrekten Klassen zugeordnet worden sind. Für ein unbekanntes (neues) Dokument findet der NN-Algorithmus die nächsten Nachbarn in der Trainingsbasis und verwendet deren Kategorien um zu bestimmen, welcher Kategorie das Dokument angehört (Subramanian A., 2005, S. 4).

Der Naive Bayes Klassifikator basiert auf dem bekannten Bayes-Theorem und erlaubt es die Zugehörigkeit eines Dokuments zu einer Klasse zu bestimmen (vgl. Subramanian, 2005, S. 5-6). „Naive“ bezieht sich dabei auf die Tatsache, dass die Merkmale (Wörter) als unabhängig voneinander betrachtet werden. Obwohl dies in der Praxis bei Texten nicht zutrifft, erzielt der Naive Bayes Klassifikator gute Ergebnisse. Zur Klassifizierung von kurzen Dokumenten ist er jedoch weniger gut geeignet bzw. bewertet diese im Vergleich zu langen unverhältnismäßig schlecht (vgl. Chakrabarti, 2000, S. 3).

Support Vektor Maschine (SVM) ist eine Methode um Funktionen aus einem Satz von etikettierten (labelled) Trainingsdaten abzuleiten. SVM ist für die Klassifizierung von Text effizient und effektiv und gilt als einer der genauesten Klassifizierer für Text (vgl. Subramanian, 2005, S. 7; Sun 2002, S. 7).

Entscheident beim fokussierten Web Crawlern ist, in welcher Reihenfolge die URLs abgearbeitet werden: Der Beste Weg durchs World Wide Web.