Textmining – Clustering von Dokumenten

Dept. Informatik 8 (Künstliche Intelligenz)Friedrich-Alexander-Universität Erlangen-Nürnberg

(Informatik 8) Clustering 1 / 25

Clustering

DefinitionClustering ist die Gruppierung von Dokumenten, so dass dieDokumente innerhalb einer Gruppe möglichst ähnlich zueinander undzu den Elementen der anderen Gruppen möglichst verschieden sind

Zwei generelle Unterscheidungsdimensionen beim Clusterings:Flaches Clustering – hierarchisches Clusteringdiskretes Clustering – modellbasiertes (weiches) Clustering

Empfohlene Literatur:C.Manning, P.Raghavan, H.Schütze: Introduction to InformationRetrieval , Cambridge University Press, 2008 – Kapitel 16 und 17

(Informatik 8) Clustering 2 / 25

Anwendungen des Clusterings

Clustering HypotheseDokumente im gleichen Cluster erfüllen ähnliche Anforderungenbezüglich eines Informationsbedürfnisses

Clustering von Suchergebnissen – bessere Präsentation vonSuchergebnissenClustern aller Dokumente – Exploration der DokumenteScatter-Gather – Zur Verbesserung der Suchanfrage: BieteCluster, User wählt mehrere Cluster aus – beginne erneutLanguage Modelling – Bestimmung ähnlicher TermeIR – Suche erst den passenden Cluster, dann die passendenDokumente (Effizienzgewinn)

(Informatik 8) Clustering 3 / 25

Flaches diskretes Clustering

(Informatik 8) Clustering 4 / 25

Problemstellung

GegebenD = {d1, . . . ,dN} und KK – die Anzahl der zur erstellenden ClusterEine Bewertungsfunktion

berechne eine Zuordnung γ : D 7→ {1, . . . ,K}, die dieBewertungsfunktion minimiert (maximiert)

Bewertungsfunktion verwendet oft ein Ähnlichkeitsmaß fürDokumenteThematische Ähnlichkeit⇒ Kosinus-Maß für TF-IDF Vekoren(zuvor Stoppwörter entfernen, Morphologische Normierung)Ähnliche Sprachen⇒ Ähnlichkeit der Häufigkeit von Bigrammen(hier keine Stoppwörter entfernen!)

(Informatik 8) Clustering 5 / 25

K-means (1)‘K Mittelpunkte’Dokumente sind Längennormiert!Mittelpunkt eine Clusters ω:

~µ(ω) =1|ω|∑~x∈ω

~x

Am besten geeignet für Daten mit hyperkugelförmigen ClusternBewertungsfunktion für einen Cluster k :

RSSk =∑~x∈ωk

|~x − ~µ(ωk )|2

Bewertungsfunktion für einen Aufteilung in Cluster:

RSS =K∑

k=1

RSSk

RSS = “residual sum of squares”(Informatik 8) Clustering 6 / 25

K-means (2)Input: { ~d1, ~d2, . . . , ~dN},KOutput: { ~µ1, . . . , ~µK}( ~µ1, ~µ2, . . . , ~µK )←SELECTRANDOMSEEDS({ ~d1, . . . , ~dN},K );while Endekriterium nicht erreicht do

for k → 1 to K doωk → {};

for n→ 1 to N doj → argminj ′ | ~µj ′ − ~dn|;ωj → ωj ∪ { ~dn} (Vektoren neu zuweisen);

for k → 1 to K do~µk → 1

|ωk |∑

~d∈ωk~d (Zentren neu berechnen)

Mögliche Endekriterien

Vorgegebene Zahl von Iterationen erreicht

Fixpunkt erreicht

RSS unterschreitet gewisse Grenze / RSS Verbesserung unter gewisser Schwelle

(Informatik 8) Clustering 7 / 25

Beispiel

(Tafel)

(Informatik 8) Clustering 8 / 25

K-means – Konvergenz (1)

Konvergenz zeigen:I Es gibt nur endlich viele Cluster-ZuordnungenI Den Iterationsschritten des Algorithmus entpricht eine monoton

fallende Folge (möglicherweise gleichbleiben)I Bei gleichbleibenden Kosten kann es Zyklen geben! (Abfangen)

Wähle die Folge der RSS-Wertezu zeigen:

I RSS nimmt bei der Neuzuweisung der Vektoren abI RSS nimmt bei der Neuberechnung der Zentren ab

Neuzuweisung der Vektoren: Jeder Vektor ~x wird dem nächstenZentroid zugewiesen, somit wird der Beitrag zu RSS pro Vektorkleiner oder bleibt gleich, somit wird RSS kleiner oder bleibt gleich

(Informatik 8) Clustering 9 / 25

K-means – Konvergenz (2)RSSk nimmt beim Neuberechen der Zentroiden ab (somit auchRSS)Beweis (dm und vm seien die m-ten Komponenten von ~d und ~v )

RSSk (~v) =∑~d∈ωk

|~v − ~d |2 =∑~d∈ωk

M∑m=1

(vm − dm)2

I Wo für welche Vektoren ist RSSk minimal?

∂ RSSk (~v)

∂vm=∑~d∈ωk

2(vm − dm)

I Null setzen∑~d∈ωk

2(vm − dm) = |ωk |vm −∑~d∈ωk

dm = 0

vm =1|ωk |

∑~d∈ωk

dm

I ⇒ genau die m-te Komponente des Zentroiden(Informatik 8) Clustering 10 / 25

Flaches modellbasiertesClustering

(Informatik 8) Clustering 11 / 25

Modellbasiertes (flaches) Clustering

K-means als Modell der Daten (Erzeugung der Daten):1 Wähle zufällig einen Zentroiden2 Addiere Rauschen (zufällige Abweichung)3 Bei normalverteiltem Rauschen erhält man hyperkugelige Gebilde

Modellbasierte Datenanalyse nimmt ein Modell für dieDatenerzeugung an und rekonstruiert die Modellparameter ausden DatenModellbasiertes Clustern nimmt ein Clustermodell an⇒ mussZuordnung Cluster↔Dokument liefernMeist: Wähle die Modellparameter so, dass die Wahrscheinlichkeitdie gegebenen Daten zu erzeugen maximal ist

(Informatik 8) Clustering 12 / 25

Likelihood der DatenLikelihood L(D|Θ): Wahrscheinlichkeit, dass gegebenen Daten Dbei gegebenen Modellparametern Θ erzeugt werdenBei K-means:

I Θ = { ~µ1, . . . , ~µk}I e−RSS ∝ L(D|Θ)I Maximales L(D|Θ) äquivalent zu minimaler RSS

Log-Likelihood

Θ = argmaxΘ

L(D|Θ) = argmaxΘ

logN∏

n=1

P(dn|Θ)

= argmaxΘ

N∑n=1

log P(dn|Θ)

⇒ Es gilt die Modellparameter so zu ändern, dass die Likelihoodmaximal wird→ die Likelihood nimt die Rolle derCLuster-Bewertungsfunktion ein

(Informatik 8) Clustering 13 / 25

Art des Modells

Gleichverteilt in Hyperkugel (K-Means)Bernoulli-VerteilungGauß-VerteilungBei bekanntem Modell kann für jedes Dokument-Cluster-Paar dieZugehörigkeitswahrscheinlichkeit P(d |ωk ; Θ) bestimmt werden(wenn ωk gewählt ist)⇒ weiches ClusteringOptimierung der Modellparamter: ExpectationMaximization-Algorithmus

(Informatik 8) Clustering 14 / 25

Bernoulli-Modell für DokumenteGrundlage: Binäre Dokument-Term-Vektoren, Terme werden alsunabhängig angenommen;Wahrscheinlichkeit der Generierung eines Dokuments d imCluster ωk bei bekannten Modellparametern Θ und mbetrachteten Termen:

P(d |ωk ; Θ) =

∏tm∈d

qmk

∏tm 6∈d

(1− qmk )

(1)

wobeiI Θ = {Θ1, . . . ,ΘK}I Θk = (αk ,q1k , . . . ,qMk ) undI qmk ist die Wahrscheinlichkeit, dass Term tm in Dokumenten aus

Cluster ωk auftritt; αk ist die Wahrscheinlichkeit des Clusters ωk

Beachte: Auftreten der Terme wird als unabhängig angenommen⇒ einfache Multiplikation; (vlg. Naive-Bayes-Annahme)

(Informatik 8) Clustering 15 / 25

Bernoulli-Modell für Dokumente (2)Wahrscheinlichkeit der Generierung des Dokuments d gegeben alleCluster (Modellparameter Θ):

P(d |Θ) =K∑

k=1

αk

∏tm∈d

qmk

∏tm 6∈d

(1− qmk )

(2)

Wahrscheinlichkeit der Generierung der Dokumentsammlung D(Likelihood):

L(D|Θ) =

|D|∏i=1

P(di |Θ)

Log-Likelihood:

log L(D|Θ) = log|D|∏i=1

P(di |Θ) =

|D|∑i=1

log P(di |Θ)

(Informatik 8) Clustering 16 / 25

EM zur Optimierung der Zuordnung

EM = ’Expectation Maximization’Grundlage: Liklihood-Funktion: Wie gut erklärt ein Modell mitModellparametern θ die beobachteten Daten?Vorgehen

I Bestimme die Likelihood der Daten bei gegebenenModellparameternZwischenprodukt: Eine Erklärung der einzelnen Beobachtungen(Expectation)

I Ändere die Modellparameter so, dass die Likelihood steigt(Maximization)

Iteriere bis Abruchkriterium (Fixpunkt, maximale Anzahl vonIterationen) erreicht

(Informatik 8) Clustering 17 / 25

EM (2)

Expectation-Schritt rnk (Wahrscheinlichkeit, dass Dokument dndurch Cluster k erzeugt wird):

rnk =αk(∏

tm∈dnqmk

) (∏tm 6∈dn

(1− qmk ))

∑Kk=1 αk

(∏tm∈dn

qmk) (∏

tm 6∈dn(1− qmk )

)=

αk · Formel 1Formel 2

=α ·Wkeit, dass ωk dn erzeugtWkeit, dass dn erzeugt wird

Maximization-Schritt (bei gegebenen rnk ):

qmk =

∑Nn=1 rnk I(tm ∈ dn)∑N

n=1 rnk, αk =

∑Nn=1 rnk

N

I(tm ∈ dn) ist 1, wenn Term tm in Dokument dn auftritt, ansonsten 0Formuliere den Maximization-Schritt in Worten!

(Informatik 8) Clustering 18 / 25

Diskussion

Modellbasiertes Clustering erlaubt eine ‘weiche’ Zuordnung derDokumente zu den ClusternFlaches clustering⇒ Cluster stehen nebeneinander (keineStruktur)Clusteranzahl muss vorgegeben werdenKein deterministisches Ergebnis (abhängig von anfangs zufälligerDokument-Cluster Zuweisung)Vorteil: Flache Clusterverfahren haben lineare Laufzeit

(Informatik 8) Clustering 19 / 25

Hierarchisches Clustering

(Informatik 8) Clustering 20 / 25

Bottom-Up Anfangs: Jedes Dokument ist ein (einelementiger)ClusterIteriere:

I Verschmelze Paare von ClusternI (behalte Verweise auf die Ausgangscluster)I Bis nurt noch ein Cluster mit allen Elementen übrig ist

⇒ hierarchical agglomerative clustering (HAC)Top-Down Beginne mit einem Cluster der alle Dokumkente

enthältTeile den aktuellen Cluster auffahre rekursiv fort

(Informatik 8) Clustering 21 / 25

HAC

Clusterähnlichkeit: SIM(di ,dj)

Clusterähnlichkeit 2: SIM(i ,m, j) Ähnlichkeit von Cluster j mit derVerschmelzung der Cluster i und mGrundannahme: Verschmelzungsoperation ist monotonBei gegebener Folge

s1, s2, . . . , sK−1

von Verschmelzungen gilt

SIM′(s1) ≥ SIM′(s2) ≥ . . .SIM′(sK−1)

monoton genau dann, wenn immer die ähnlichsten Clusterverschmolzen werden

(Informatik 8) Clustering 22 / 25

SimpleHACInput: (d1, . . . ,dN)Output: Afor n← 1toN do

for i ← 1toN doC[n][i]← SIM(dn,di);

I[n]← 1 (notiert die aktiven Cluster);

A← [] (sammelt Cluster als Verschmelzungssequenz);for k ← 1toN − 1 do〈i ,m〉 ← argmax{〈i,m〉:i 6=m∧I[i]=1∧I[m]=1}C[i][m];A.APPEND(〈i ,m〉) (Verschmelzung speichern);for j ← 1toN do

C[i][j]← SIM(i ,m, j);C[j][i]← SIM(i ,m, j);

I[m]← 0 (notiert die aktiven Cluster);

In Worten: ....

(Informatik 8) Clustering 23 / 25

Clusterähnlichkeit

Single link die Ähnlichkeit von zwei Clustern ist die Ähnlichkeit derzwei ähnlichsten Clusterlemente aus den jeweiligenClustern (maximale Ähnlichkeit)

Complete link die Ähnlichkeit von zwei Clustern ist die Ähnlichkeit derzwei unähnlichsten Clusterlemente aus den jeweiligenClustern (minimale Ähnlichkeit)

Zentroid Ähnlichkeit der Cluster-Zentren (durchschnittlicheÄhnlichkeit der Elemente verschiedener Cluster)

Gruppendurchschnitt Ähnlichkeit aller Elemente (gleich welcherCluster)

(Informatik 8) Clustering 24 / 25

Top-Down Clustering

Verwende flaches Cluster-Verfahren als UnterfunktionBilde K = 2 ClusterRufe rekursiv auf

(Informatik 8) Clustering 25 / 25