Jun 07 2007
Wie ticken Suchmaschinen? Sicht aus dem Bereich Text-Mining
Derzeit schreibe ich an meiner Diplomarbeit im Bereich Text-Mining und hab mich deshalb seit längerem damit beschäftigt, wie Texte analysiert und wie relevante Stellen innerhalb einer Text-Kollektion ermittelt werden können. Da mein letzter Beitrag phpBB – schlecht fürs Ranking recht viel Aufmerksamkeit bekommen hat, möchte ich kurz grundlegende Techniken vorstellen, die erklären, wie man Blogs und Foren (oder Seiten allgemein) suchmaschinenfreundlicher gestalten kann. Ich stelle diese Analyse nicht als Fakt hin (niemand außer Google weiß, wie Google arbeitet) und freue mich schon jetzt auf eine Diskussion. Bei den vorgestellten Techniken handelt es sich nur um Grundprinzipien, dass eine Suchmaschine feiner arbeitet, dürfte klar sein.
Text-Repräsentation
Um Texte miteinander vergleichen zu können, ist es notwendig, sie in ein einheitliches Format zu bringen. Das bedeutet, dass wir eine Repräsentation benötigen, in die jeder Text passt. Hier hat sich in der Praxis das Vektorraum-Model von G. Salton (1975) durchgesetzt. Die Grundidee besteht darin, sowohl Dokumente als auch Anfragen als sehr hochdimensionalen Vektor aufzufassen, in dem jede Dimension für einen Term steht. Ein Term ist dabei z.B. ein Wort. Das bedeutet, dass die Größe des Vektors mit der Anzahl aller möglichen Worte übereinstimmt.
Man nimmt nun alle Terme eines Dokuments und steckt sie in diesen Vektor. Dabei wird die Anzahl der Terme berücksichtigt – wenn wir also in einem Text 5 mal das Wort “Google” haben, dann steht im Vektor an Stelle des Terms “Google” der Wert “5″. Es geht dabei aber die Information verloren, an welcher Stelle das Wort genau stand (Sack of words). Das scheint eigentlich ein kritischer Fehler zu sein. Es hat sich in der Praxis aber gezeigt, dass die Information zwar hilfreich sein kann, in den meisten Fällen jedoch irrelevant ist.
Warum hat sich das Vektor-Raum-Modell durchgesetzt?
Es ist sehr einfach, Berechnungen durchzuführen: Die Ähnlichkeit zwischen zwei Vektoren kann mit Hilfe des eingeschlossenen Winkels berechnet werden. Hierzu gibt es mehrere Techniken, die beliebteste ist jedoch schlicht, den Cosinus auszurechnen:
- sind zwei Dokumentenvektoren identisch, erhalten wir 1 (maximaler Treffer)
- sind sie komplett unterschiedlich, erhalten wir 0 (minimaler Treffer, Dokumente haben nichts gemeinsam und stehen damit rechtwinklig zueinander)
Wir berücksichtigen jetzt, dass Dokumente als auch Anfragen als Dokumentenvektoren aufgefasst werden und die Ähnlichkeitsbestimmung somit unsere Suchergebnisse liefert.
Das Cosinus-Maß ist einfach zu berechnen und leicht verständlich. Es geht jedoch schneller. Wenn alle Dokumentenvektoren normiert sind (also die Länge 1 haben), dann kann man anstelle des Cosinus einfach das Skalar-Produkt zweier Vektoren berechnen. Das ist ein extremer Geschwindigkeitsgewinn bei hohen Dimensionen und wird deshalb heute in jeder aktuellen Suchmaschine eingesetzt.
Was bedeutet das in der Praxis? Dazu muss man sich fragen: Wie wird ein Vektor normiert? Wir addieren einfach alle Vektor-Einträge zusammen (Betrag des Vektors) und dividieren jeden Vektor-Eintrag durch diese Summe. Das heißt: Je weniger Einträge mein Vektor hat – also je weniger Terme in meinem Text vorkommen – desto höher sind die Werte eines einzelnen Terms. Das heißt also:
Je mehr unnötige Begriffe auf der Seite vorkommen, desto weniger gewichtet sind relevante Begriffe und desto unwahrscheinlicher erhalten wichtige Begriffe eine starke Gewichtung.
Es gilt also: Regel 1: Man muss sich auf das Wesentliche konzentrieren!
Das Lexikon ist das Problem
Wir haben bis jetzt also festgehalten, dass unnötige Texte die Bewertung relevanter Text-Abschnitte abschwächt. Das ist jedoch nur die eine Seite. In der Praxis ist die Größe unserer Vektoren ein Problem. Aus diesem Grund gibt es mehrere Verfahren, die Größe eines Vektors zu beschränken. Die wichtigste Methode wird dabei als zipfsches Gesetz bezeichnet:
Nach George Kingsley Zipf folgt die natürliche Sprache in vielen Belangen dem “Prinzip der geringsten Anstrengung”. So sind die am häufigsten benutzten Wörter sogenannte Funktionswörter (“der”, “die”, “das”, …). Diese Funktionswörter sind für Suchanfragen natürlich völlig uninteressant, weil sie in fast jedem Text vorkommen. Aus diesem Grund zählt man alle Texte einer Kollektion (also eines Internetauftritts) zusammen. Sehr häufig aufkommende Wörter werden dabei ignoriert (Stopp-Wörter), sehr selten aufkommende Wörter ebenfalls (Rechtschreibfehler). Die relevanten Begriffe haben eine mittlere Häufigkeit. Damit können wir die Dimension des Vektors beschränken. In Kombination mit anderen Verfahren (Stemming, n-Gramme) erhalten wir “handhabbare” Vektor-Größen.
Was bedeutet das in der Praxis? Wörter, die auf allen Seiten mehrmals auftauchen, werden als Stopp-Wörter aufgefasst, wenn die Häufigkeit eine gewisse Schwelle erreicht. Große Seiten wie das Abakus-Forum können es sich also teilweise leisten, unwichtigen Text auf ihren Seiten zu führen, da dieser einfach nicht berücksichtigt wird. Das selbe Forum mit weniger Inhalt würde jedoch aufgrund Regel 1 vom unnötigen Text Schaden nehmen.
Also: Regel 2: Große Seiten können sich unwichtigen Text eher leisten als kleine.
Loading ...
