Klassifikator (Informatik)

Ein Klassifizierer (Informatik) sortiert Dokumente in Klassen ein. Diese Methodik kommt vor allem im Webmining zum Einsatz.

Trainieren

Ein Klassifizierer wird zunächst trainiert, das heißt er bekommt Daten, von denen die Kategorisierung bekannt ist, um anhand derer neue Beispiele einordnen zu können. Man unterscheidet folgende Lernarten:

• betreutes Lernen (supervised learning): Ein "Lehrer" gibt die Werte der Zielfunktion für alle Trainingsbeispiele an
• halb-betreutes Lernen (semi-supervised learning): Nur ein Teil der Trainingsbeispiele wird klassifiziert
  • aktives Lernen (active learning): Der Klassifizierer wählt die Beispiele aus, die vom "Lehrer" eingeordnet werden sollen
  • Selbst-Training (self-training): Der Klassifizierer ordnet die Beispiele selbst ein
  • Co-Training: Zwei Klassifizierer ordnen gegenseitig ihre Beispiele ein
  • Mutli-View-Lernen: Zwei identische Klassifizierer, die unterschiedlich trainiert wurden, ordnen gegenseitig ihre Beispiele ein
• unterstütztes Lernen (reinforcment learning): Ein "Lehrer" gibt die Werte der Zielfunktion an, die sich der Klassifizierer aussucht (z.B. Beispiele bei denen er sich sehr unsicher ist)
• unbetreutes Lernen (unsupervised learning): Abgesehen von den Trainingsbeispielen gibt es keine Informationen für den Klassifizierer

Lernmethoden

Klassifizierer können auf sehr unterschiedliche Weise lernen und ihre Trainingsbeispiele verwerten. Die Wahl ist abhängig von der Art der Trainingsdaten sowie den verfügbaren Leistungsreserven. Folgende Lernmethoden werden eingesetzt:

• Entscheidungsbäume und Regressionsbäume
• Induktive logische Programmierung
• Neuronale Netzwerke
• Support-Vector-Maschine
• Clustering z.B. k-means-Clustering
• Genetische Algorithmen
• kNN-Klassifizierer
• Rocchio Klassifizierer
• statistische Modellierung z.B. Naive Bayes Klassifizierer
• Regelbasierte Klassifizierer

Weitere Lernansätze sind beispielsweise

• Lernen als Suchen
• Generalisierung mit Bias (Der Lerner hat bestimmte "Vorlieben", zieht Klassen vor)
• Teile und Herrsche-Strategien
• Overfitting-Avoidance: Das Modell generalisieren um die Fehleranfälligkeit zu reduzieren (Bsp.: (Ockhams Rasiermesser)

Evaluierung

Zur Evaluierung des gelernten Modells werden folgende Verfahren eingesetzt

• Validierung durch Expretern
• Validerung auf Daten
• Online Validierung

Die Valdierung auf Daten hat als Nachteil, dass Trainingsdaten zur Validierung "verschwendet werden(Out-of-Sample Testing).Dieses Dilemma wird durch die Quer-Validierung (Cross-Validation) gelöst: Man Teilt die Datensätze in n (meist 10) Teile. Dann Nutzt man für jede Partition p die anderen n-1 Partitionen zum lernen und die Partition p zum testen.

Zur Bewertung eines Klassifizieres werden gängigerweise drei Größen angegeben, die auf folgender Tabelle basieren

	classified as positive	classified as negative
is positive	a	c	a+c
is negative	b	d	b+d
	a+b	c+ d	n

Treffergenauigkeit (Accuracy)

Die Treffergenauigkeit gibt den Prozentsatz der korrekt klassifizierten Beispiele an.

$accuracy={\frac {a+d}{n}}$

Erinnerung (Recall)

Die Erinnerung gibt den Prozentsatz der positiven Beispiele an, die korrekt klassifiziert wurden.

$recall={\frac {a}{a+c}}$

Präzision (Precision)

Die Präzision gibt den Prozentsatz der korrekten Beispiele an, die positiv klassifiziert wurden.

$precision={\frac {a}{a+b}}$

zusätzliche Eigenschaften (Feature Engineering)

Die Ansätze zur Erweiterung von Klassifizierern gliedern sich wie folgt:

• textabhängige Eigenschaften
  • n-Gramme: Ausnutzen des Kontextes durch Verwendung von Sequenzen der Länge n anstelle einzelner Worte (z.B. web mining vs. coal mining)
  • Positionsinformationen
• Linguistische Eigenschaften
  • Stemming: gebeugte Verben auf ihren Wortstamm zurükführen
  • noun phrases: Fokus von n-Grammen auf "echte" Sätze beschränken (z.B. nur Bigramme mit Noun-Noun und Adverb-Noun)
  • linguistic phrases: Finde alle Vorkommnisse eines sysntaktischen Templates (z.B. noun aux-verb <d-obj> findet I am <_>)
• Strukturelle Eigenschaften
  • structural markup
  • Hypertexte
• Feature Subset Selection
  • Häufigkeitsbasiert
  • TF-IDF
  • Maschinelles Lernen
• Feature Construction
  • Latent Semantic Indexing: Die Probleme von Mehrdeutigkeit und Synonymen durch Trennung der Beispiele mit Hyperebenen mittels Singular Value Decomposition lösen.
• Stopp-Listen

Feature Subset Selection

Der Filter-Ansatz

Berechne ein Maß zur Unterscheidung von Klassen. Messe das Gewicht der Features und wähle die besten n aus. Auf diese Feature Subset wird der Lernalgorithmus angewendet. Nachteile:

• Rundandte Features (Verwandte Features werden aähnliche Gewichtung haben)
• Abhängige Features (Einige Features werden nur in Kombination relevant sein)

Der Wrapper-Ansatz

Durchsuche die Menge aller möglichen Feature Subsets. Auf jedes Subset wird der Lernalgorithmus angewendet. Vorteile:

• Findet ein Feature Subset, dass optimal zum Lernalgorithmus passt
• Bezieht auch Kombinationen von Features ein und nicht nur jedes Feature einzeln
• Entfernt redundante Features

Nachteile:

• Sehr ineffizient

Wrapper-Arten

• Forward selection: Starte mit einer leeren Menge von Features und füge immer das Features hinzu, dass die Accuracy am meisten erhöht bis die Accuracy nicht mehr deutlich zunimmt.
• Backward elimination: Starte mit allen Features und versuche ungeignete zu entfernen
• Simple heuristic search: Füge ein Feature nach dem anderen hinzu, bis die Accuracy nicht mehr deutlich zunimmt

Verwendung von Dokumentbezügen

Dokumente stehen für gewöhnlich nicht alleine, sondern befinden sich gerade im Netz in gegenseitigem Bezug, vor allem durch Links. Die Informationen aus diesen Links und der Vernetzungsstruktur lassen sich von Klassifizierern verwenden.

Hubs & Authorities

• Authorities sind Seiten die viele Informationen zum gesuchten Thema enthalten
• Hubs sind Seiten, die viele Links auf gute Authorities haben

Hierdurch ergibt sich eine gegenseitige Verstärkung Durch iterative Berechnung der Scores mittels Hub score $h(x)=\sum a(y)$ und Authority score $a(x)=\sum h(y)$ sowie anschließende Normalisierung konvergiert das Verfahren. Probleme:

• Effizienz
• Irrelevante Links (z.B. Werbelinks)
• Gegenseitige Verstärkung von Hosts
• Abweichungen vom Thema

Verbesserungen:

• Verbesserte Verbindungsanalyse: Die Wertungen nach Anzahl der Links normalisieren (Mehrere Links von einem Host werden schwächer gewertet)
• Relevanz-Gewichtung: Dokumente die einge ungenügende Ähnlichkeit zu einem Durchschnittsdokument des Root-Sets haben werden nicht betrachtet

Page Rank

Siehe auch den Artikel PageRank.

Die Idee hinter dem Page Rank ist der "Random Surfer", der mit Wahrscheinlichkeit d auf einen zufälligen Link auf einer Seite klickt.

Der Page RAnk bevorzugt Seiten mit

• vielen eingehenden Links
• Vorgängern mit hohem Page Rank
• Vorgägern mit wenig ausgehenden Links

Hypertext Klassifizierung

Häufig enthalten Webseiten nur wenig Text und/oder viele Bilder. Sie sind in einer anderen Sprache geschrieben, enthalten irrietierende Begriffe oder enthalten gar keine nützliche Information. Links hingegen sind von mehreren Autoren geschrieben, enthalten ein reicheres Vokabular, redundante Informationen, erschliessen unterschiedliche Aspekte einer Seite und haben ihren Fokus auf den wichtigen Inhalten von Seiten. Sie sind daher zur Klassifizierung von vernetzten Dokumenten sehr geeignet. Die besten Ergebnisse lassen sich erzielen wenn man zur Klassifizierung einer Seite die Klassen der Vorgänger sowie den Text betrachtet

Hyperlink Ensembles

• Der Seitentext ist nicht interessant
• Jeder Link zur Seite wird ein eigenes Beispiel
• Linkankertext, Überschrift und den Paragraphen, in dem der Link vorkommt erfassen
• die Trainingsbeispiele (einer pro Link) klassifizieren und daraus die Klassifizierung für das aktuelle Dokument berechnen

Quellen

J. Fürnkranz: Webminig - Data Mining im Web http://www.ke.informatik.tu-darmstadt.de/lehre/ss05/web-mining.html