TextMining Flashcards
Anwendungsbereiche des Text Mining
- konzeptbasierte Suche / Finden ähnlicher Texte (Dokumenten-Management-Systeme, ähnliche Artikel, …)
- Dokumentenklassifikation und Clustering (automatische Archivierung, Workflow-Optimierung, Spamfilter)
- Informationsstrukturierung und -extraktion (Aufbau von Ontologien/Taxonomien, Name/Orte/Institutionen/Daten/Zahlen/…)
Einordnung des Text Mining
- zw. Information Retrieval und linguistischer Informatik
- inhaltlich orientierter Zugriff auf unstrukturierte Daten
Forschungsansätze
- wissensbasierte/regelbasierte Ansätze
- Mustersuche
- neuronale Netze
- statistische/korpuslinguistische Ansätze
Arten von Kookurrenzen
+ Anwendung
- Nachbarschaftskook. = unmittelbar nebeneinander
- Satzkookkurrenz
- auffällig: gemeinsames Auftreten wahrscheinlicher als Einzelwahrscheinlichkeiten vermuten ließen
-> mit Kookurrenzen lassen sich Cluster zu einem Wort bilden = Disambiguierung!
Formeln für Ähnlichkeitsmaße (Kookurrenzen)
- Tanimoto-Ähnlichkeit: Anteil Doppeltreffer bzgl. Anteil Einzeltreffer
- Mutual Information: Abweichung von statistischer Unabhängigkeit
- G-Test: Wahrscheinlichkeit simultaner seltener Ereignisse
- Poisson-Signifikanz
Tanimoto-Ähnlichkeit
(Ähnlichkeitsmaß Kookkurrenzen)
Anteil Doppeltreffer bzgl. Anteil Einzeltreffer
simT(A,B) = nAB / (nA+nB-nAB)
Mutual Information
(Ähnlichkeitsmaß Kookkurrenzen)
Abweichung von statistischer Unabhängigkeit
i(A,B) = log(nABnges / (nAnB))
[=log(pAB/(pApB))]
if A and B are independent, then pAB=(pApB) and therefore: log(pAB/(pApB)) = log 1 = 0
G-Test
(Ähnlichkeitsmaß Kookkurrenzen)
Wahrscheinlichkeit simultaner seltener Ereignisse
x = nAnB / nges
sig(A,B) = x - nAB log x + log nAB!
(für 2.5x < nAB)
Kookkurrenz-Graph mit Simulated Annealing
Benachbarte Knoten ziehen sich nach Kookurrenzstärke an, nicht benachbarte stoßen einander ab
ges.: energetisch günstigste Position der Knoten in der Ebene
- hohe Temperatur -> starke Schwingung der Knoten ->Verhinderung der Stabilisierung in lokalem Minimum
- durch wirkende Kräfte und Temp. in jedem Iterationsschritt zur optimalen Position bewegt
- Temperatur abgekühlt -> relat. Lage der Knoten stabil, nur noch Abstände optimiert
Birthday Problem + Co-occurrence Problem
Modification: What is the probability p of the existence of k couples with the same birthday - a boys and b girls randomly chosen?
-> Poisson Distribution
Poisson Signifikanz
(Ähnlichkeitsmaß Kookkurrenzen)
beruhend auf common birthday problem
λ = ab / n (=npapb)
k = Anzahl Kookkurrenzen
Eigenschaften von sig(n,k,a,b)
Poisson Signifikanz
(Ähnlichkeitsmaß Kookkurrenzen)
- einmalige Kookurrenz in sig(n,1,1,1) -> 1
- independence: sig(n,npq,np,nq) -> 0 (p,q propabilities for A,B)
- negativ: häufige Wörter, die nicht gemeinsam auftreten
- enlarging corpus by factor m: sig(mn,mk,ma,mb) = m*sig(n,k,a,b) = umso häufiger gesehen, umso mehr steigt Signifikanz (nicht bei Tanimoto/Mutual Information)
-
additivity: für k/b ~ k’/b’, unification of words B, B’:
- sig(n,k,a,b)+sig(n,k’,a,b’) ~sig(n,k+k’,a,b+b’)
- Zusammenführen von Wörtern hinterher möglich statt vorherige Lemmatisierung
- Maximum: max(B) sig(A,B) ~ a = am größen, wenn immer mit A auftritt und A möglichst selten einzeln
Zipf’sches Gesetz
- “Prinzip der geringsten Anstrengung” in natürlicher Sprache
- Wortformen eines Textes nach absteigender Häufigkeit ordnen
- Rang r einer Wortform * Häufigkeit n ~ konstant mit textabhängiger Konstante k
r * n ~k
n ~ 1/r
Zipf’sches Gesetz
- Frequenz des häufigsten Wortes (n maximal)
- Größe des Vokabulars = Anzahl der types (m=1)
Konstante c
- k ~ rmax
- k ~ r1
k steigt linear mit Korpusgröße N -> Konstante c = k/N unabhängig von Korpusgröße, aber evtl. einzelsprachenabgängig
Zipf’sches Gesetz
Abschätzung über Anzahl an Wortformen, die n mal im Text vorkommen (= rn)
- N: Gesamtanzahl aller Wortformen des Textes (tokens)
- t: Umfang des Vokabulars (types)
- rn: größter Rang der Wortformen, die genau n mal auftreten
- In: Anzahl der Wortformen, die genau n mal auftreten
rn ~ c * N/n
Zipf’sches Gesetz
Abschätzung des Zuwachses des Vokabulars, wenn sich die Textmenge erhöht (= In)
Besonderheit I1
- N: Gesamtanzahl aller Wortformen des Textes (tokens)
- t: Umfang des Vokabulars (types)
- rn: größter Rang der Wortformen, die genau n mal auftreten
- In: Anzahl der Wortformen, die genau n mal auftreten
In = rn - rn+1
= (cN/n) - (cN/(n+1))
= cN / (n(n+1))
I1 = c*N/(1+2) = t/2
Zipf’sches Gesetz
D
- exakte Herleitung ergibt n ~ (r+V)-1/D
- D = (fraktale) Dimension nahe 1, die charakteristisch für die jeweilige Sprache ist
- 1/D = Anstieg der Gerade in der doppelt-logarithmischen Darstellung und eben nur näherungsweise 1
Zipf’sches Gesetz
Korpusgröße
- unendlich viele Wörter: mit Korpusgröße steigt Anzahl an Wörtern (types) geradlinig
- auch nur endlich viele möglich: Kurve s.o. gekrümmt
Neologismen
Fragestellungen
- Neu: wann erstmalig beobachtet
- Nachhaltig: Wird man in zehn Jahren das Wort noch kennen?
- Tendenz: Wird Häufigkeit zunehmen?
- Korrelation: Wie wirkt ein Wort auf die Tendenz eines anderen?
Neologismen
Typen
- Echter Neologismus, völlige Neuschöpfung
- Tendenz wachsend oder
- Nach starkem Anfang fallende Tendenz
- Vorher niederfrequentes Wort,
- dessen Häufigkeit unaufhaltsam steigt (DVD) oder
- das plötzlich (z.B. wegen eines Ereignisses) in der Allgemeinsprache auffällt, dann fällt
- Ereignisabhängige Wörter, die in Abständen mit großer Häufigkeit auftreten (Papstwahl)
- Wort mit neuer Bedeutung (Kurzmitteilung)
- Bezeichner für Einzelobjekte oder Gruppen (Hotelerbin, Terroristenchef)
- Wörter mit kurzer Lebensdauer (UMTS-Auktion)
Clustering & Klassifikation
Unterscheidung
Cluster:
- entstehen “von selbst” aus der inneren Struktur der Daten, interpretiert als Ähnlichkeit
- Gruppen nicht vorgegeben
- Anzahl der Gruppen vorgegeben o. muss vom Algorithmus ermittelt werden.
Klassifikation: Klassen sind vorgegeben, beispielsweise durch Trainingsdaten
Clustering und Klassifikation
Maschinelles Lernen
- Funktion f: M → {0, 1 , …, n-1}, die jedem Element x∈M seine Klasse f(x) zuordnet
- f unüberwacht gelernt = Clustering: Bekannt sein kann die Anzahl n der Klassen,Aufteilung kann nur über Ähnlichkeit der Attribut-Werte gelernt werden
- f überwacht lernen = Klassifikation: f ist auf Teil der Menge M bekannt und soll für restlichen Teil ermittelt werden
Clustering und Klassifikation
Anforderungen an Unterteilung
- Homogenität innerhalb der Cluster
- Heterogenität zwischen verschiedenen Clustern
Clustering
Darstellungsform
Dendrogramm
- Cluster werden zu Instanzen, die wieder mit verarbeitet werden
- Cluster können zu größeren Clustern zusammengefasst werden
- zeigt Beziehungen zwischen Clustern mit an
Clustering
Unterschiede bei Algorithmen/Modellen
- Cluster disjunkt o. überlappend
- Verfahren deterministisch o. probabilistisch
- Cluster hierarchisch o. nicht
- Algorithmus lernt inkrementell o. nur global
Hierarchisches Clustering
-
bottom up:
- Start mit Clustern aus je einem Objekt
- jeweils benachbarte Cluster verschmelzen
-
top down: meist sehr schnell
- zerlege Gesamtmenge in zwei Cluster.
- wiederholt auf den entstandenen Clustern ausführen
Clustering
Abstand zwischen Clustern bei verschiedenen Attributarten berechnen
- numerisches Attribut: Differenz der Werte
- mehrere numerische Attribute: normiere die Attribute & wähle Euklidischen Abstand
- Nominale Attribute: Abstand 0 oder 1 je nachdem, ob die Werte gleich oder verschieden sind
- Cluster durch eines seiner Elemente oder durch ein fiktives Element (Zentroid) vertreten
- Single Link: Abstand zw. 2 Clustern = min. Abstand zwischen 2 Elementen der versch. Cluster
- Zentroid: fiktives Element mit Mittelwert der (numerischen) Attribute der Elemente
Clustering
k-means-Algorithmus
- Daten werden vom Algorithmus in vorgeg. Anzahl von k Clustern geteilt
- Initialisierung: k Clusterzentren werden zufällig gewählt
- Zuordnung: Instanzen werden jeweils Cluster mit dem nächstgelegenen Clusterzentrum zugeordnet.
- Zentroid: Zentroiden der so entstandenen Cluster werden als neue Clusterzentren benutzt.
- Schleife: Gehe zu 2, solange sich noch Zuordnungen einzelner Elemente zu Clustern ändern.
Clustering
k-means-Algorithmus
Probleme + Lösung
- Konvergenz ist nicht gesichert.
- Konvergenz verläuft nur zu einem lokalen Minimum, nicht unbedingt zum globalen Minimum -> Clustering muss nicht optimal sein
- Lösung: Algorithmus mehrfach starten.
Clustering
CobWeb
Idee, Vorgehen, Nachteil
- inkrementelles Clustering: sukzessive Dendrogramm aufbauen
- Start: leerer Baum -> Instanzen nacheinander an der am besten passenden Stelle einfügen
- möglich: Umstrukturierung nach Einfügeschritt
- Maß für „am besten passenden Stelle“ ist Kategoriennützlichkeit
- Nachteil: entstehende Clustering kann von Reihenfolge abhängen
Clustering
CobWeb
Einfügeschritt
- Auswahl nach größter Kategoriennützlichkeit
- bei Einfügen getestet:
- Hinzufügen zu bestehenden Cluster
- Anlegen neues Cluster mit nur dieser Instanz
- wenn Hinzufügeschritt -> zusätzlich Verschmelzungsschritt und Aufteilungsschritt für Cluster, in das hinzugefügt wurde testen -> ausführen, falls Kategoriennützlichkeit verbessert
- Verschmelzungsschritt: verschmolzen mit zweitbesten Cluster, zu dem sie „beinahe hinzugefügt worden wäre“.
- Aufteilungsschritt: Instanzen eine Hierarchiestufe höher als einzelne, neue Cluster gewählt
Evaluierung
einfache Lösungen
- auf Trainingsdaten testen = kein guter Indikator
- Aufteilung in Test- und Trainingsdaten, aber:
- bestimmte Daten sind von ihrer Natur her beschränkt, z.B. Aussagen über Feiertage, 29. Februar
- Datenqualität ist häufig von Experten abhängig, sind knapp
Evaluierung
statistische Tests: Messungen
- bei Klassifikation
- Anzahl der korrekten Klassifizierungen
- Genauigkeit von Wahrscheinlichkeitsvorhersagen
- Genauigkeit von numerischen Vorhersagen
- Kosten
Klassifizierung: Fehllerate
Evaluierung
Holdout-Methode
Problem+Stratifikation
- 1/3 zum Testen, 2/3 zum Trainieren
- Problem: Trainingsmenge ist vielleicht nicht repräsentativ
- Stratifikation: jede Klasse sollte in beiden Mengen etwa im gleichen Verhältnis auftreten wie in der Gesamtmenge
-
wiederholt: Kompensation der Fehler durch wiederholtes Training und Testen mit verschiedenen Daten-Stichproben
- Fehlerraten werden einfach gemittelt
- Vermeidung der Überlappung der Datenmengen : Kreuzvalidierung
Evaluierung
Holdout-Methode
Kreuzvalidierung
- Schritt: Aufteilung der Daten in k Mengen gleicher Größe
- Schritt: pro Durchlauf wird eine Menge für den Test benutzt, der Rest für das Training (3 Mengen = 3 Durchläufe)
- populär: k=3, dreifache Kreuzvalidierung
- mit Stratifikation: stratifizierte dreifache Kreuzvalidierung
- Standardmethode: stratifizierte zehnfache Kreuzvalidierung
- besser: zehn zehnfache Kreuzvalidierungen und danach Mitteln (wiederholte Kreuzvalidierung)
Evaluierung
Holdout-Methode
Leave-One-Out-Kreuzvalidierung
- Vor- und Nachteile
- k-fache Kreuzvalidierung mit k = Anzahl der Instanzen
- eine Instanz wird weggelassen und nach der korrekten Vorhersage dieser Instanz bewertet
- das Ergebnis aller k Beurteilungen wird gemittelt
- Vorteile:
- Benutzung der größtmöglichen Datenmenge
- kein Zufall möglich, deterministisch
- Nachteile:
- sehr rechenaufwendig
- keine Stratifizierung möglich
Evaluierung
Confusion Matrix
- bei einfacher ja/nein-Klassifikation
- gute Matrix: große Zahlen auf der Hauptdiagonalen
Text Mining
Objekte und Attribute
-
Objekte für Klassifikation:
- Dokumente
- Wörter und Wortgruppen
-
Attribute:
- Teile der Objekte (z.B. Buchstaben für Wörter, Wörter für Dokumente)
- Metadaten (für Dokumente), Wörterbuchdaten (für Wörter)
- Zusätzlich daraus abgeleitete Größen
Attribute
Dokumente
- Metadaten: Autor, Titel, Erscheiningsdatum, Quelle (Verlag), Sprache
-
Dokumententext:
- Text als “Bag of Words”
- Wort-N-Gramme, speziell Eigennamen (Personen, geogr. Namen, Firmen), Zahlen mit Maßeinheiten
Attribute
Wörter
-
Teile des Wortes
- Buchstaben-N-Gramme, speziell am Wortanfang und –ende
- Präfixe, Wortstamm, Suffixe
-
Klassifikation des Wortes:
- Grundform, Wortart
- Zugehörigkeit zu Sachgebiet, Information aus Thesaurus
-
Kontext des Wortes
- Nachbarschafts- und Satzkookkurrenzen
- Kompliziertere Nachbarschaftsmuster (mehrere Wörter, evtl. mit Platzhaltern)
- Relationen zwischen solchen Objekten?
Text Mining
Grundaufgaben
- Klassifikation der “Lücken” zwischen Buchstaben
- Klassifikation durch Kontext
- Erkennen und Klassifikation von Mustern
Text Mining - Grundaufgaben
- Klassifikation der “Lücken” zwischen Buchstaben
Beschreibung u. Aufgaben
- Lücken zwischen jeweils zwei aufeinanderfolgenden Buchstaben
- typisch: “eng zusammengehörende” Buchstabenpaare + Bruchstellen
- Für Wörter: Silbentrennung, morphologische Zerlegung von Wörtern, Kompositazerlegung, fehlende arabische kurze Vokale einfügen
- Für Sätze: Tokenisierung für Chinesisch und Japanisch
Text Mining - Grundaufgaben
- Klassifikation durch Kontext
- Kontext, Aufgaben
- Kontext bei Buchstaben: Umgebende Buchstaben (Fenster)
- Kontext bei Wörtern: Wörter als Nachbarn oder in größerem Fenster (Satz, Dokument)
-
Für Wörter
- Aussprache eines Wortes: Phonem zu Graphem
- Betonte Silbe finden = Klassifikation von Vokalen
- Silbenzahl: Klassifikation von Vokalen als Silbengipfel
-
Klassifikation eines Wortes mittels Kookkurrenzen
- Zugehörigkeit zu Sachgebiet
- Unterschied zw. normalen Substantiven und Eigennamen
- Clustering von Wörtern mittels Kookkurrenzen: Finden semantisch ähnlicher Wörter
-
Für Sätze
- Ermittlung der Wortart eines Wortes im Text (POS-Tagging)
- Disambiguierung eines mehrdeutigen Wortes
- Klassifikation eines Textes: Zugehörigkeit zu Sachgebiet
- Dokumentenclustering: Finden ähnlicher Dokumente
Text Mining - Grundaufgaben
Erkennen und Klassifikation von Mustern
- Aufgaben
- oft mit regulären Ausdrücken beschreibbar
- für mittel- und hochfrequente Wörter oft typische (= signifikante) Kontexte als Muster
-
in Wörtern:
- Sprachidentifikation für Sprachen mit speziellen Zeichen
- Grundformreduktion: wiederholende Gruppen von Endungen zu einer Grundform
- Erkennung von Fremdwörtern: Typische Präfixe und Suffixe
-
in Sätzen:
- Personennamenerkennung: Muster wie Titel-Vorname-Nachname
- Erkennen von Redewendungen (von X zu X)
- Paraphrasierung von Komposita als Beschreibung, Blumenvase = Vase für Blumen, Glasvase = Vase aus Glas
- Semantik von Präpositionen, z.B. mit (Bestandteil, Werkzeug, Eigenschaft)
-
in Dokumenten:
- Sprachindentifikation durch typische hochfrequente Wörter
- Sachgebietsklassifikation
- Spamfilter
- Plagiatserkennung
Text Mining
Eigennamenerkennung
Teilaufgaben
- Wiedererkennen bekannter Objekte
- Listen mit Eigennamen (Wikipedia, Telefonbücher, GNS/Gazetteer für Ortsnamen) oder wiederkehrende Strukturen (Titel-Vorname-Name)
- sprachabhängig, Mehrdeutigkeiten, Ausnahmen
- Erkennen von Namen als Klassifikation
- Kontext des zu klassifizierenden Wortes im Text
- Vorname vor potenziellem Nachname, aber kein Artikel
- in, aus, nach vor potentiellem Ortsnamen, aber kein Artikel
- Wortähnlichkeiten
- Stringähnlichkeit (Obermayer Nachname -> Obermeyer)
- Häufige Wortbestandteile (wie -stadt, -walde usw.)
- Kontext des zu klassifizierenden Wortes im Text
Text Mining
Wörter in Teile zerlegen
- Aufgaben, Speicherung
- Grundformreduktion: intuitiv = Endungen abschneiden
- Kompositazerlegung: ein vorhandenes Wort abschneiden, so dass ein Wort übrig bleibt
- Zerlege Worte so, dass Teile bekannt sind (Wörter, Endungen)
- verwende
- Ähnlichkeiten der Wörter vom Wortende her (bei 1 und 2)
- Ähnlichkeiten der Wörter vom Wortanfang her (bei 2)
- Datenstrukturen, die Wortanfang oder Wortende „benutzen“: CPT
Speicherung
Möglichkeiten
- relationale DB: viel Speicherplatz, Elementaroperationen implementiert, Zusatzinformationen speicherbar, aber langsam, v.a. kompleye Operationen wie partial match
- Wortlisten: Reihenfolge unwichtig, strukturelle Redundanzen (gleiche Präfixe/Suffixe), eingeschränktes Alphabet mit 26 Buchstaben + Sonderzeichen
- Trie: Ausnutzen gleicher Präfixe/Suffixe, Knoten haben 0 bis N Töchter (N Anzahl möglicher Characters
Speicherung
Eigenschaften von Tries
- abgeleitet von Information Retrieval
- Spezielle m-Wege Bäume, m = Kardinalität des Alphabets
- Knoten ist Vektor mit m Zeigern auf Töchterknoten, implizite Zuordnung Alphabetzeichen und Position
- Baumhöhe: Länge des längsten gespeicherten Wortes -> Suchzeit linear in Wortlänge
- Gestalt unabhängig von Einfügereihenfolge
- Schlechte Speicherplatzausnutzung (viele leere Pointer) vermeiden durch
- Zusammenfassen von Unterbäumen, falls diese nicht verzweigen
- nur Abspeichern der besetzten Zeiger, Angabe über Position erforderlich
Speicherung
CPT: Compact Patricia Trie
- Prinzip, Suchen, Einfügen
- Reduzieren der Kanten durch Speicherung von mehreren Characters in einen Knoten
-
Suche:
- Rekursives Absteigen, Suchwort von vorn verkleinern
- Zurückliefern des letzten erreichten Knotens.
- falls restliches Suchwort leer: exact match, sonst partial match
-
Einfügen von w:
- Suche nach w liefert den Zielknoten k
- falls exact match: Wort schon vorhanden
- falls partial match: Inhalt des Zielknotens k aufteilen, Töchterknoten einfügen.
- Es gilt im Zielknoten k: w=uv, k.inhalt=ux
- Suche nach w liefert den Zielknoten k
Speicherung von Zusatzinformationen in CPTs
z.B. Grundformreduktion
- Knoten werden um Feld erweitert, das die Zusatzinformation + zusammengezählte Klassifizierungen der Unterbäume aufnimmt
- Beispiel: CPT wird aus rückwärts gelesenen Wörtern aufgebaut, “<” ist Wortanfang-Zeichen
- Reduktionsregel in letztem gefundenen Knoten wird angewendet
Speicherung: CPT
Pruning
- wenn CPT nur zum Klassifizieren und nicht zum Speichern von Wörtern verwendet
- redundante Teilbäume abschneiden
- Strings in den Blättern ohne Änderung des Verhaltens auf Länge 1 kürzen
Speicherung: CPT
weitere Anwendungen
- Kompositazerlegung:
- 2 CPTs, Schnittstellen von vorn und hinten
- Morphologieklasse
- Geschlechter von Namen
- Wortarterkennung
- Terminologie
- …
CPT
Vor- und Nachteile
+ alle Trainingsdaten werden im Test reproduziert
+ beliebige Sonderfälle trainierbar
- Trainingsmenge muss gewisse Größe haben
- ohne Trainingsmenge ist Algorithmus hilflos
Klassifikation
Entscheidungsbäume
- Aufbau ist rekursiv
- wähle 1 Attribut als Wurzel und verzweige für jeden möglichen Wert -> Beispielmenge in Untermengen zerlegt
- für jeden Zweig rekursiv ausführen mit nur noch jenen Instanzen, die die Verzweigung auch erreichen
- Abbruch, wenn alle Instanzen in einem Knoten dieselbe Klasse aufweisen
Auswahl der Attribute nach Informationsgewinn
Klassifikation: Entscheidungsbäume
Vorgehen bei numerischen und nominalen Attributen
- nominal: Anzahl der Tochterknoten entspricht Anzahl der möglichen Werte (z.B. alle Buchstaben)
-
numerisch: Vergleich auf größer/kleiner
- Alternativen: Dreifachverzweigungen
- Integer: kleiner, gleich, größer
- Intervall: unterhalb, innerhalb, oberhalb
- Alternativen: Dreifachverzweigungen
Klassifikation: Entscheidungsbaum
1R-Algorithmus
For each attribute:
For each value of the attribute, make a rule as follows:
count how often each class appears find the most frequent class make the rule assign that class to this attribute-value
Calculate the error rate of the rules
Choose the set of rules for the attibute with the smallest error rate
-> z.B. wähle Regelmenge für das Attribut “outlook”
Klassifikation: Entscheidungsbäume
Entropie
Beispiel: Entropie für ‘outlook’
Entropie einer Wahrscheinlichkeitsverteilung p={p1, p2,…, pn} (d.h. pi≥0, Σpi=1):
entropie(p1, p2,…, pn) = - Σpi log(pi)
Klassifikation: Entscheidungsbäume
Information eines Knotens
Beispiel: ‘outlook’
Verteilung der Instanzen einbeziehen:
info(outlook) = info([2,3], [4,0], [3,2])
= 5/14 x 0.971 + 4/14 x 0 + 5/14 x 0.971
= 0.693
Entropie für sunny, overcast, rainy
Klassifikation: Entscheidungsbäume
Informationszuwachs
(Info vor dem Split) – (Info nach dem Split)
gain(outlook) = info([9,5]) - info([2,3], [4,0], [3,2] )
= 0.940 – 0.693
= 0.247
-> erstes Attribute im Entscheidungsbaum ist das mit höchstem Informationsgewinn
Klassifikation: Entscheidungsbaum
numerische Attribute
Beispiel: temperature
- Standardmethode: binäre bzw. Zwei-Wege-Aufteilung
- Unterschied zu nominalen Attributen: viele Splitpunkte möglich
- Lösung:
- berechne Informationsgewinn für jeden Splitpunkt
- wähle besten Punkt
- Informationsgewinn für diesen Punkt entspricht Informationsgewinn des Attributs
- Splitpunkte werden in der Mitte zwischen zwei Werten gesetzt
- Test aller Splitpunkte in nur einem Durchlauf
Klassifikation: Entscheidungsbaum
Pruning: Strategien
- „Beschneiden“ von Bäumen zur Vereinfachung
- 2 Strategien:
- Postpruning = nachträgliche Beschneidung des vollständigen Baums
- Prepruning = Entscheidung während des Baumbildungsverfahrens, z.B. Entwicklung weiterer Unterbäume einzustellen
- In der Praxis wird Postpruning bevorzugt
- Problem bei Prepruning: zu frühes Stoppen
Kombination vor Ergebnissen aus Klassifikationsverfahren
Experten-Forum
Beispiel: 3 Experten
- je mehrere Experten für 1 Fragetyp zuständig
- Experten antworten mit verschiedenen Methoden
- jeder Experte beantwortet eine Frage mit Wahrscheinlichkeiten p,q,r richtig, gar nicht oder falsch.
- Expertenrunde entscheidet nach folgenden Regeln: Entscheidung angenommen, wenn
- es stimmen mind. 2 Experten zu
- zugestimmt wird mit einer Mehrheit von mindestens 75% (ohne Berücksichtigung der Enthaltungen)
- z.B. richtige Entscheidung angenommen mit p3+3p2q
- Wahrscheinlichkeiten für falsche Ergebnisse hängen nicht von Größe des Expertenforums ab
Klassifikation
Precision und Recall
precision = tp / (tp+fp)
recall = tp / (tp + fn)
tp = true positive
Klassifikation
Meta-Lernen
Annahmen + Algorithmen
- mehrere, teil-korrekte Klassifikatoren
- versch. Algorithmen + versch. Trainingsdaten
- gewisse Mindestgüte
- können auf verschiedenen Teilen des Instanzenraums unterschiedlich gut sein
- Kombination der Einzelergebnisse, um Gesamtverhalten signifikant zu verbessern
- Algorithmen: Bagging + Boosting + Stacking
Klassifikation
Meta-Lernen
- Bagging
- (ungewichtete) Mehrheitsentscheidung
- jedes Modell erhält das gleiche Gewicht
- ideale Version:
- mehrere Trainingsdatenmengen gleicher Größe herausgreifen
- 1 Klassifizierer für jede Menge bilden
- Vorhersagen der Klassifizierer kombinieren
- führt fast immer zur Leistungsverbesserung bei „unstabilen“ Lernverfahren (z.B. Entscheidungsbaum)
Klassifikation
Meta-Lernen
- Boosting
- Mehrheitsentscheidungen mit Gewichtung in Abhängigkeit von der Leistung
- gewichtet werden Instanzen
- belohnt wird das Lösen einer „schwierigen“ (d.h. hoch bewerteten) Aufgabe.
-
iterativ: neue Modelle durch Leistung älterer beeinflusst
- neue Modelle ermutigt, Experten für Instanzen zu werden, die von früheren Modellen unkorrekt gehandhabt wurden
- intuitiv: Modelle sollten sich ergänzen statt sich zu überlagern
Klassifikation
Meta-Lernen
Stacking
Stacked Generalisation (gestapelte Generalisierung)
- Abstimmungsverfahren wird durch Metalernverfahren ersetzt
- Vorhersagen der Basislernsysteme (Level-0-Modelle) werden als Eingabe für das Metalernverfahren (Level-1-Modell) benutzt
- Level-1-Verfahren benutzt Ausgaben der Level-0-Verfahren, um Entscheidung zu treffen
- Basislernsystem benutzten Modelle verschiedenen Typs
weniger oft eingesetzt als Bagging und Boosting + theoretisch schwer zu analysieren
Klassifikation
Bayessches Lernen
allgemein
- zw. verschiedenen Attributen wird Kausalität vermutet
- damit Vorhersage für ein unbekanntes Attribut gemacht
- aus Trainingsinstanzen wird Art der Abhängigkeit gelernt
- jede beobachtete Trainingsinstanz kann erwarteten Wahrscheinlichkeiten verändern
- explizites Vorwissen (z.B. Richtung der Zusammenhänge) kann ausgedrückt werden
- vorhergesagt werden Wahrscheinlichkeiten
Klassifikation
Bayessches Formel
Beispiel: Wir haben eine blaue Kugel gezogen. Wie groß ist die Wahrscheinlichkeit, dass sie aus Sack Nr. 1 stammt
- P(h|D) = a posteriori Wahrscheinlichkeit von h
- P(h) = a priori Wahrscheinlichkeit von h
- P(D|h) = Wahrscheinlichkeit des Ereignisses D unter der Hypothese h
- P(D) = Wahrscheinlichkeit des Ereignisses D unabhängig von einer Hypothese
P(h|D) = (P(D|h) * P(h)) / P(D)
D: blaue Kugel gezogen
h: vorher Sack 1 ausgewählt.
Klassifikation
Bayessches Lernen
MAP: Maximum a posteriori Propability
P(weather=’rainy’|grass=’wet’) = 0.1
P(sprinkler=’on’|grass=’wet’) = 0.08
-> wähle weather=’rainy’, weil Wahrscheinlichkeit, dass Gras durch Regen nass ist höher ist, als durch Sprinkler
Klassifikation
Bayessches Lernen
Maximum Likelihood Hyotheses
falls alle Hypothesen die gleiche a priori Wahrscheinlichkeit haben
Klassifikation
BOC: Bayesscher optimaler Klassifikator
- wahrscheinlichste Klassifikation einer neuen Instanz unter Berücksichtigung der Trainingsdaten
- {V} = Menge der Klassen
- Klasse = einzelne Hypothese o. Menge von Hypothesen
- BOC berechnet a posteriori Wahrscheinlichkeit jeder Hypothese und kombiniert Voraussagen für Klassifikation der neuen Instanz
- innerhalb der Hypothesenraums und des Vorwissens BOC im Mittel unschlagbar
- rechenaufwändig.
Klassifikation
Naive Bayes bei Dokumentenklassifikation
+ Beispiel
- Dokumente auf vorgegebene Klassen verteilen
- Annahme: Klassen lassen sich durch Wörter beschreiben, die in den Dokumenten der entsprechenden Klassen auftauchen
- Attribute: Wörter, unabhängig von ihrer Position im Text mit Werten ja/nein
- z.B. Spamfilter: Initiales Training vom Hersteller mittels bekannter Spam-Emails und Nicht-Spam + handgemachte Wortgruppen als Features +nachträgliches Trainieren durch Nutzer
Greedy vs. Lazy Learning
-
Greedy: Entscheidungsbaum, Regelbasiert, probabilistisch (Naive Bayes, max. Entropie), …
- Modellbindung während/nach Trainieren
-
Lazy: kNN
- Modellbindung zur Zeit der Anfrage
Baum vs. Vektorraum
- jedes Objekt beschrieben durch Attribut-Wert- Paare
- feste Reihenfolge der Attribute erzeugt Vektor von Attributwerten.
- Entscheidungsbäume nutzen die Attribute nacheinander.
- Im Vektorraum können wir alle Attribute gleichzeitig nutzen
kNN
Definition - instance based learning
- Learning: store all the data instances
- Performance: when a new query instance is encountered
- retrieve a similar set of related instances from memory
- use to classify the new query
-
kNN: most basic type of instance learning
- all instances are points in n-dimensional space
- distance measure to determine “closeness” of instances
- Classify an instance by finding its nearest neighbors and picking the most popular class among the neighbors
kNN
Instance Based Learning
Vor- und Nachteile
+ Can construct a different approximation to the target function for each distinct query instance to be classified
+ Can use more complex, symbolic representations
– Cost of classification can be high
– Uses all attributes (not most important)
K-D Tree
- Multiple dimensional data
- Extending BST from one dimensional to k-dimensional
- binary tree
- Organized by levels (root is at level 0, its children level 1, etc.)
- Tree branching at level 0 according to the first key, at level 1 according to the second key, etc.
- KdNode: has a vector of keys, in addition to the pointers to its subtrees.
K-D Tree
2-D Tree: insert
- new node is inserted as a leaf
- different keys are compared at different levels
approximative NN-Suche
nächsten Nachbarn mit max. Abstand d zu einem Punkt x zu finden:
- suche Clusterzentrum entsprechend Grob-Quantisierung
- betrachte die dazugehörige Voronoi-Zelle sowie alle Nachbarzellen mit geeignet kleinem Abstand
- wähle alle Punkte daraus und berechne näherungsweisen Abstand zu x
- Ausgabe in Reihenfolge der Abstände.
Memory Based Language Processing
durch Analogien
- With a memory filled with instances of language mappings
– from text to speech,
– from words to syntactic structure,
– … - With the use of analogical reasoning,
- Process new instances from input (text, words) to output (speech, syntactic structure)
More Data Effect
allgemein
- Differences between algorithms flip or disappear
- Differences between representations disappear
- Growth of curve seems log-linear (constant improvement with exponentially more data) -> effect persists
- Explanation sought in “Zipf’s tail”
- More observations of words already seen
- More new words become known (the tail)
More Data Effect
Klassifikationsaufgaben: Trends bei more data
- Tend do go upwards because of Zipf’s tail
- upward trend may slow down
- more examples add more of the same information w.r.t. classification
- trend may revert to going down
- additional data contains errors, noise, or is sampled in a different manner than before
- trend stops
- 100% mark or the annotation accuracy is reached
- input representation lacks expressiveness to resolve more ambiguity
Memory Based Learning
Example Storage - instance editing
(Prinzip, Algorithmus)
- store a subset of the most informative training examples in order to focus the system and to make it more efficient: instance editing
- Edit superfluous regular instances
- evidence that keeping all training instances
is best in exemplar-based approaches to NLP - e.g. IB2 Algorithmus
Memory Based Learning
Example Based Learning
- EBL methods base decisions on similarity to specific past instances rather than constructing abstractions
- abandon the goal of maintaining concept “simplicity”
- trade decreased learning time for increased classification time
- store all examples = all exceptions = very important for NLP tasks
Memory Based Learning and Classification
Learning + Classification
Learning: store instances in memory
Classification:
- given new test instance X,
- compare it to all memory instances
- compute a distance between X and memory instance Y
- update the top k of closest instances (NNs)
- take the majority class of the k NNs as the class of X
Memory Based Learning
TiMBL: schwach besetzte Attribute
Wenn für viele Attribute Nullwerte vorliegen
0000010200001000 -> 6:1 8:2 13:1
0010010001200000 -> 3:1 6:1 10:1 11:2
Memory Based Learning
TiMBL: Ergebnisse bei Vornamen
- verschränkt > rechtsbündig > linksbündig
- 2000 häufige > 20000 > 2000 zufällige
- kNN (IB1 mit k=3) > Entscheidungsbaum (IGTree)
POS Tagging
Voraussetzungen
-
Lexicon of words
- all: closed classes
- not all: open classes (Subst., Verben, Adjektive, Adverben)
- For each word in the lexicon information about all its possible tags according to a chosen tagset
- 40-1300 Tags
- Wortarten, grammatische Informationen,…
- Different methods for choosing the correct tag for a word:
– Rule-based methods
– Statistical methods
– Transformation Based Learning (TBL) methods
POS Tagging
Rule Based Methods
- Start with a dictionary
- Assign all possible tags to words from the dictionary
- Write rules by hand to selectively remove tags
- Leaving the correct tag for each word
POS Tagging
Statistical Methods
- Most Frequent Tag Algorithm
- Most Frequent Tag Algorithm
Training:
– Take a tagged corpus
– Create dict containing every word in the corpus with all its possible tags
– Count number each tag occurs for a word and compute the probability P(tag|word); save all probabilities
Tagging:
– geg. new sentence
– for each word, pick the most frequent tag from the corpus
POS Tagging
Statistical Methods
Bigram HMM Tagger
HMM = Hidden Markov Model
Training:
– Create dict containing every word in the corpus with all its possible tags
– Compute the probability of each tag generating a certain word + the probability each tag is preceded by a specific tag (Bigram HMM Tagger => dependent only on the previous tag)
Tagging:
– Given a new sentence
– for each word, pick the most likely tag for that word using the parameters obtained after training
– HMM Taggers choose the tag sequence that maximizes this formula: P(word|tag) * P(tag|previous tag)
POS Tagging
Transformation Based Methods
Prinzip
Combination of rule-based and stochastic tagging methodologies
– rule templates are used to learn transformations
– stochastic: machine learning is used - with tagged corpus as input
Input: tagged corpus, lexicon
basic idea: Set the most probable tag for each word as a start value
– Change tags according to rules of type “if word-1 is a determiner and word is a verb then change the tag to noun” in a specific order
Tagger-Architektur
Konstruktion eines POS-Taggers
- geg: neues annotiertes Korpus
- 3 Datenstrukturen werden automatisch extrahiert:
- Lexikon
- Fallbasierung für known words
- Fallbasierung für unknown words
- (beide Fallbasierungen als IGTree implementiert)
- Fall = Information über ein Wort das getaggt werden soll, seinem linken und rechten Kontext und einer dazugehörigen Kategorie für das Wort in diesem Kontext
Tagger-Architektur
Ablauf des Taggen
- Jedes Wort wird im Lexikon nachgeschaut
- Wird es gefunden:
- lexikalische Repräsentation wird abgefragt
- Kontext wird bestimmt
- resultierendes Muster wird in der known words - Fallbasierung nachgeschlagen
- Wird es nicht gefunden:
- lexikalische Repräsentation wird auf Grundlage seiner Form berechnet
- Kontext wird bestimmt
- resultierendes Muster wird in der unknown words Fallbasierung nachgeschlagen
Memory Based Learning
IGTree
Prinzip, Knoten, Performanz
= Entscheidungsbaum nach Information Gain
- kombiniert 2 Algorithmen:
– Komprimieren von Fallunterscheidungen in Bäumen
– Zurückholen von Klassifikationsinformationen - Fälle als Wege von verbundenen Knoten gespeichert
- Blattknoten: eindeutige Klassifikation
- Knoten: Infos über wahrscheinlichste Klassifikation o. Default-Klassifikation
- Verwenden der Default-Klassifikation des letzten abgefragten nicht-terminierenden Knotens, falls eine feature-value-Abfrage fehlschlägt
- IGTree-Abfrage 100-200 mal schneller als eine normale speicherbasierte Abfrage und nutzt über 95% weniger Speicher
Topic Models
Idee, Posterior Distribution
- Topic Model: model topics as distribution over words
- Annahme: wenige Topics (100-200)
- Only documents are observable
- Infer underlying topic structur:
- Topics that generated the documents
- For each document, distribution of topics
- For each word, which topic generated the word
- Algorithmic challenge: Finding the conditional distribution of all the latent variables, given the observation.
Topic Models
Inference
- Three sets of latent variables
– topic mixtures θ
– word distributions φ
– topic assignments z - Integrate out θ and φ and estimate topic assignments
- Use MCMC with Gibbs sampling for approximate inference
Topic Models
Gibbs Sampling
- mit zufälliger Verteilung starten und schauen, ob bei minimalen Änderungen Idealzustand annäherungsweise erreicht wird
Start with random assignments of words to topics
Repeat M iterations
- Repeat for all words i
- Sample a new topic assignment for word i conditioned on all other topic assignments
Topic Models
theoretische Idee vs. praktische Umsetzung
Latent Semantic Analysis: Produkt von kleineren Matrizen
Topic Models
praktisches Vorgehen
- Texte nehmen, in denen wir die relevanten Topics vermuten (Zeitungsartikel, Wikipedia-Artikel)
- Auswahl der zuzuordnenden Wörter, da Wörter mit breiter Verteilung die Topics möglicherweise „verschlechtern“ (keine Stoppwörter, nur Substantive)
- Anzahl der Topics (50 … 500, meist 100 oder 200)
- Schwellwert, wie lange Wörter als zu einem Topic zugehörig betrachtet werden sollen (p>0.004)
Topic Models
Anzahl, Größe, Bezeichnung
- wenig große, viele kleine Topics (~Zipfsches Gesetz)
- große Topics aufgesplittet, kleine unpassend zusammengefasst
- am besten 100-200
- Namen: markanteste Wörter o. Bezeichnungen von Menschen
Topic Models
Kookkurrenzen, künstliche Dokumente
Kookkurrenzen:
- geg: Eingabewort und vorhandenes Topic Model
- untersucht wird Verteilung der Satzkookkurrenzen auf vorberechnete Topics
künstliche Dokumente:
- damit Wort mehrere (z.B. mind. 10) Kookkurrenzen hat, braucht es eine Mindestfrequenz von ca. 50.
- seltenere Wörter/noch nie gesehene: typische Kontexte (=Kookkurrenzen) durch tatsächliche Kontexte (=Beispielsätze) ersetzen
- aus Beispielsätzen künstliches Dokument erzeugen und für dieses die Topicverteilung ermitteln
Topic Models
Wörter des Tages
bisher - Änderungen
- Automatische Auswahl der heute auffälligen Wörter (heute viel häufiger als im Mittel, nur Substantive (Großschreibung))
- Einmalige Klassifikation der Wörter von Hand
- vorgegebene, praktisch sinnvolle Klassen
- keine flektierten Formen erlaubt
- automatische Wiederverwendung klassifizierter Wörter.
Probleme: nur fürs Deutsche, Klassifikation muss nicht stabil sein, (z.B. Schwarzenegger Schauspieler/Politiker)
- *Neu:** vorgefertigte Klassifikation mittels Topics, abgeleitet aus Wikipedia-Kategorien
- *Vorteile:** für viele Sprachen
- *Nachteile:** POS-Tagging + Grundformreduktion nötig
Word Embedding
Prinzip, semantisches Embedding
- Objekte durch Vektoren in einem hochdimensionalen Raum beschreiben
- Zuordnung = “word/sentence/… embedding”
-
semantisch:
- Semantisch ähnliche Objekte werden nahe beieinanderliegenden Vektoren zugeordnet
- Umgedreht entsprechen nahe beienanderliegende Vektoren semantisch ähnlichen Objekten
- Dimension des Vektorraums ist gleich der Anzahl der berücksichtigten Beschreibungswörter
Word Embedding
Wortähnlichkeit durch Kookkurrenzen
Version 1
- Ähnlichkeit zweier Wörter als Vektorabstand berechnen
- nur für Wörter mit Mindesthäufigkeit. (Rang<200.000)
Version 1: Wortkookkurrenzen. Wortvektor von Wort A
- 1 an Position b, wenn Wort B mit Id=b Satzkookkurrenz zu A ist.
- 1 an Position 200000+b, wenn Wort B mit Id=b NB-Kookkurrenz zu A ist.
Vergleich zweier Vektoren für Wörter A und B über das Skalarprodukt: berechnet Anzahl der gemeinsamen Kookkurrenzen von A und B.
- Vorteil: Die V ektoren sind schwach besetzt, nur 0 oder 1.
- Nachteile: Bewertet werden die Gemeinsamkeiten, nicht bestraft werden die Unterschiede, rechte und linke Nachbarn werden nicht unterschieden.
Word Embedding
Wortähnlichkeit durch Kookkurrenzen
Version 2
Version 2: Wortkookkurrenzen. Wortvektor von Wort A
- 1 an Position b, wenn Wort B mit Id=b Satzkookkurrenz zu A ist.
- 1 an Position 200000+b, wenn Wort mit Id=b linke NB-Kookkurrenz zu A ist.
- 1 an Position 400000+b, wenn Wort mit Id=b rechter NB-Kookkurrenz zu A ist
- Vektoren normiert
Vergleich zweier Vektoren für Wörter A und B über das Skalarprodukt: Cosinus des Winkels zwischen den Vektoren
Word Embedding
Wortähnlichkeit durch Kookkurrenzen
Dimensionsreduktion
- Projeziere Vektorraum auf z.B. 500 zufällig erzeugte paarweise (fast) orthogonale Einheitsvektoren.
- Nachteil: Vektoren nicht mehr schwach besetzt.
Word Embedding
Wortähnlichkeit - Version 3: Word2Vec
- Word2Vec
- Konstruktion des Vektors durch neuronales Netz
- inkl. Dimensionsreduktion.
- mit variablem Fenster über den Text gelesen und Kontext der einzelnen Wörter berücksichtigt
- ähnlich zu Kookkurrenzen.
Word Embedding
Word2Vec: Reduzierung des Featureraums
- Semantisch ähnlichen Wörtern entsprechen ähnliche Spalten in der Kookkurrenzmatrix, damit ist eine große Rangreduktion möglich auf 50-200 Features.
- Ermittlung der Matrix F: iterativ mittels neuronaler Netze. Optimierungskiterium: Jedes Wort soll sich selbst als ähnlichstes Wort behalten.
- Features entsprechen nicht (wie bei Topics) mit Wahrscheinlichkeiten gewichteten Mengen von Wörtern, sondern beliebigen Linearkombinationen.
Word Embedding
Möglichkeiten, Wörter darzustellen + Dimensionsreduktion
Word Embedding
Vektoralgebra
(Polen : Warschau = Ungarn : X)
Verbindungen (=Differenzvektoren) fast identisch
Polen : Warschau = Ungarn : X folgender Maßen lösen:
X ist das Wort mit dem dazugehörigen Vektor am nächsten zu vec(Ungarn) – vec(Polen) + vec(Warschau)
Word Embedding
ähnliche Sätze finden
- Bag-of-words-Ansatz: Beschreibe einen Satz durch die Menge seiner Wörter = Summe seiner Wortvektoren, evtl. noch normiert
- zusätzliche Forderung: Gleiche oder ähnliche Satzbaupläne
Disambiguität
Ebenen
- lexikalische Ebene: Ball – Ball
- semantische Ebene (strukturelle/kompositionell-semantische): Jeder Mann tanzte mit einer Frau
- syntaktische Ebene: Mann mit dem Fernrohr sehen
- Phonemebene: Miene – Mine
- morphologische Ebene: Staubecken – Staubecken
durch etymologische Entwicklungen, semantische Zusammenhänge und v. a.
Diambiguität
Auflösungen
- durch Redundanz in Sprache und Kontext für Menschen kein Problem
- normal: Paraphrasierung (z.B. “Herrschaftshaus” statt “Schloss”
- außerdem: grammatische Analyse, außersprachlicherKontext
Disambiguität
Arten von Bedeutungsdefinitionen + Berechnung
- konstruktiv: keine vollständig vorhanden
- beschreibend: kurz, in ein einem oder zwei Sätzen für einen durchschnittlichen Menschen verständlich erläutert
- differenzierend: für jede Bedeutung soviele Begriffe gegeben, dass die konkrete Bedeutung klar von allen anderen abgrenzbar wird -> für Algorithmen
Methode der Berechnung von Kookkurrenzen / Wortassoziationen und Clustering dieser für lediglich distinktive Definition von Bedeutungen
Disambiguität
SIGIL
- Sense Induction by Greedy Iterative Labeling
- Hauptannahme: Nur eine Bedeutung pro Kookkurrenz
- Precision von ca. 63%
- Berechne Kookkurrenzen aus Korpus
- Zu Ausgangswort W, Auswahl “relevanter” Wörter mit hohen Wahrscheinlichkeiten P(W | wi), ergibt Ähnlichkeitsmatrix
- Auswahl von Saatwörtern für jede zu induzierende Bedeutung von W
- Zuordnung weiterer Wörter aus der relevanten Menge aufgrund von in 1. berechneten Kookkurrenzen
- Iteriert 4, bis für jedes Wort wahrscheinlichkeitsbasierte Zuordnung von relevanten Wörtern zu den zu induzierenden Bedeutungen von W
- Schritt 1 und 2 ist Berechnen von Kookkurrenzen
- Schritt 4 und 5 ist eigentlich Clustering
Grapheigenschaft der Kookkurrenzen
+ allgemeine Eigenschaften
- durch Satzkookkurrenzen wird implizit ein Graph definiert
- stark zusammenhängende Knoten liegen nah beieinander
- Graph zusammenhängend
- dünner Graph, sehr wenige Kanten
- Zipfsches Gesetz der Verbundenheitsgrade: einige wenige Knoten, die zu fast allen verbunden sind (Artikel) und absteigend Funktionswörter, Adjektive, Verben, etc.
- sehr hoher lokaler Clusterwert -> überall im Graphen abgrenzbare Häufungen
- sehr kurze Wege zwischen einzelnen Punkten des Graphen
-> Small World Graph
Grapheigenschaft der Kookkurrenzen
Eigenschaften der Cluster
- Lokale Cluster sind omnipräsent, jedes Wort befindet sich in einem oder mehreren Clustern:
- Cluster sind semantischer Natur
- Cluster sind Kontext-Homogen (wenn Wörter ‘zusammenpassen’, ist Schnittmenge kontext-homogen)
