PG Intelligence Service

PG Intelligence Service

Vortrag : Semi-supervised ClusteringVortragender: Erkan Kaz

Veranstalterin: Prof. Dr. Katharina MorikBetreuer: Dipl. Informatiker Felix Jungermann

Gliederung

1. Einleitung 2. Clusteranalyse 2.1 Allgemein 2.2 Algorithmen 2.3 Beispiel 3. Supervised Clustering 4. Unsupervising Clustering 5. Semi-supervised Clustering (with User Feedback) 5.1 Allgemein 5.2 Constraints (Bedingungen) 5.2.1 Typen von Instance-Level Constraints 5.3 Beispiele 5.4 Feedback 6. Vergleich der Performance 6.1 Constraints vs. Labels 7. Fazit

1. Einleitung

neues Verfahren für Clusteranalyse vorstellen Semi-supervised Clustering, User kann Algorithmus

Feedback geben dies in Form von Bedingungen (Constraints) User kann Clusterprozess steuern es existieren natürlich schon bekannte Verfahren!

Unsupervised/ Supervised Clustering

2. Clusteranalyse

2.1 Allgemein: Einteilung einer Menge von Objekten in Cluster automatisierte Bildung von Cluster Teilgebiet der Statistik verborgene Muster und Strukturen in Daten erkennen Problem nicht nur im Web sondern auch z.B. Biologie,

Marketing usw.

2.2 Algorithmen

Es wird unterschieden zwischen Algorithmen:

ü b e rw a ch te K la ss if ika tion

A g g lo m e ra tive V erfa h ren D iv is ive V e rfa h ren

H ie ra rch isch e s C lu s te rn P a rtit io n ie re n d e s C lu s te rn

u n ü b e rw a ch te K la ssif ika tion

C lu s te ra n a lyse

2.2

- für partitionierende Cluster z.B. : + EM-Algorithmus + k-means- für hierarchisches Clustern z.B. : + Complete-Link-Algorithmus + Single-Link-Algorithmus + agglomerierende- dazu kommen noch Kriterien wie: stochastisch, deterministisch, exat, fuzzy

2.3 Beispiel

Aufgabe:

Bestimme Cluster nach k-means (hier k=2) Verfahren mit

euklidischem Abstand und wähle als Zentroiden (6,5) und (11,10).

Für die Beobachtungen:

B= { (2,4), (2,8), (4,9), (7,7), (11,10), (11,7), (6,5), (9,2), (12,5), (14,4) }

2.3

C1= { ( 6,5),(2,4), (2,8), (4,9), (7,7),(9,2) }

C2= { (11,10), (11,7) (14,4), (12,5) }

- Nun neue Zentroiden berechnen und fortfahren bis sich die Cluster nicht mehr ändern.

- Wähle neue Zentroiden (Mittelpunkt seiner Instanzen)

=> C1‘= { ( 6,5),(2,4), (2,8), (4,9), (7,7) }

C2‘= { (11,10), (11,7) (14,4), (12,5),(9,2) }

3. Supervised Clustering

Allgemein: angenommen Klassenstruktur bekannt einige Instanzen mit Bezeichnungen nehmen und

Klassen zuordnen präzise und gezielte Zuordnung für neue Objekte Labels (Klassenbezeichnungen vorhanden) => feste und

geringe Anzahl vorhanden! Beziehungen der Objekte dem User sichtbar

4.Unsupervised Clustering

Standard Clustering Algorithmus Daten unbezeichnet kein Hintergrundwissen vorhanden ähnliche Objekte zusammengruppieren und

unterschiedliche Objekte auseinander Gruppierung nach Ähnlichkeitsgrad => meiste Arbeit liegt bei Ähnlichkeitskriterium => beobachten und experimentieren

5.Semi-Supervised Clustering (with User Feedback) 5.1 Allgemein: Liegt zwischen den beiden oben

genannten Verfahren. Es wird Hintergrundwissen in die Clusteranalyse integriert um:

- resultierende Cluster zu verbessern

- Laufzeit für Berechnung zu reduzieren

=> Hintergrundwissen in Form von Constraints (Bedingungen)

5.1

- machen z.B. Aussagen darüber, ob Instanzen in selbe Cluster gehören oder in andere

- dadurch Lösungsraum begrenzt, Suchraum reduziert

- Nutzer steuert Clusterprozess um:

=> gute Partitionierung zu erzielen

=> minimaler Zeitaufwand

5.1

Vorteil: - Nutzer interagiert und arbeitet mit den Daten, um diese besser zu verstehen => System lernt Kriterien, den Nutzer zufrieden zustellen - System erwartet keine Funktionseingaben vom Nutzer - Kriterien, die User im Kopf hat werden erfüllt- Beziehung zu aktivem LernenNachteil:- Es gibt viele mögliche Bedingungen

5.1

Wann Semi-supervised Clustering vorziehen ?- falls viele verschiedene gleichwertige Clustereinteilungen

vorhanden => aktiv lernendes System würde viele unnötige Anfragen machen!

- falls Endcluster noch nicht bekannt => Constraints einfacher zu verstehen als Labels- einsetzen wo Labels nicht leicht benutzbar

5.2 Constraints

Allgemein: Sind Bedingungen, die eingehalten werden sollen verschiedene Arten vorhanden

=> Als Beispiel Instance-Level Constraints:

- Aussagen über Beziehungen der einzelnen Objekte zu nennen wären noch :

+ δ- Constraints

+ γ- Constraints (für hierarchisches Clustering)

5.2

5.2.1 Haupttypen

+ Must-Link Constraints: legen fest, dass zwei Instanzen in

selbe Cluster gehören

+ Cannot-Link Constraints: zwei Instanzen nicht im selben

Cluster

=> Aussagen über die paarweise Beziehungen von zwei Objekten einer Datenmenge machbar

5.3 Beispiele

5.3.1

Für Beziehungen: Falls ML(a, b) und ML(b, c) => ML(a, c)

aber auch Aussagen über CL möglich.

5.3.2

Clusterprozess mit Einbindung von Constraints:

Dazu nehme ich eine partitionierenden Cluster mit Hilfe der

Methode von k-means.

5.3

Verbesserungen einfügen um:

- Leistung zu erhöhen

- Genauigkeit zu erhöhen

- Laufzeit zu verringern

=> Bedingungen in Form von ML u. CL für Objekte!

5.3

Pseudo- Code:

5.3

5.3.3 : Das Yahoo Problem

- habe 100.000 Dokumente (Texte, Artikel usw.)

- will diese in passende Gruppen partitionieren

- es wird nicht angegeben welche Klassenbezeichnungen verwendet werden sollen (z.B. Sport, Politik usw.)

5.3

Lösungsansatz:

1. Die Dokumente in Unsupervised Clustering Algorithmus geben und clustern lassen

2. User geht Cluster durch und sagt dem System welches Cluster er mag/ nicht mag.

=> Nicht für alle Cluster tun sondern nur einige. Gebe Feedback hinzu:

5.3

- das Dokument gehört nicht hier her

- bewege das Dokument zu diesem Cluster

- die Dokumente im selben oder unterschiedlichen Cluster

=> nicht für alle sondern nur für diejenigen die am unpassensten sind!

3. Nach der Kritik, neu clustern lassen mit Feedback

4. Wiederholen bis zufrieden!

5.4 Feedback

Es gibt unterschiedliche Formen, hier einige Beispiele:

- Dokumente gehören/ gehören nicht in selbe Cluster - dieses Dokument gehört hier nicht hin - bewege das Dokument in dieses Cluster - Cluster zu grob oder zu fein - Cluster ist gut oder nicht gut=> Constraints an individuellen Punkten=> keine clusterspezifischen Feedbacks geben

6. Vergleich der Performance

Schwierig Supervised und Semi-supervised Clustering zu vergleichen, denn :

- die Trainingsdokumente werden nicht berücksichtigt- Labels vs. Constraints Semi-supervised Clustering=>gemessen wird wie viel Prozent der Instanzen korrekt

eingeordnet werden!- nachdem 10 Constraints eingefügt wurden, wird die

asymptotische Performance erreicht (70-80%)

6

- aber mit Zunahme der Constrains wird keine höhere Performance erreicht

=> höhere Performance als Unsupervised clustering (50%)

=> um die gleiche Performance zu erreichen braucht Supervised 3 bis 6 fach mehr Labels.

6.1 Constraints vs. Labels

bei Supervised kenne ich Zielklassen

=> habe gekennzeichnete Objekte, ordne diese zu bei Semi-supervised kenne ich die Klassen nicht

=> aber System bekommt Infos durch Nutzer! Constraints Constraints leichter anzugeben aber weniger informativ es gibt bestimmte Anzahl von Klassen aber tausende

von möglichen Constraints

=> Labels und Constraints sind zu unterschiedlich

7. Fazit

neues Verfahren kennen gelernt Hintergrundwissen einbinden => qualitativere Cluster gibt User die Möglichkeit sich in Prozess einzubinden System lernt vom Nutzer menschliches Vorgehen kann Wegweiser für die

Entdeckung sein, was Gruppen aussagen!

=> Ziel: Feedback während des Clusterprozesses

einzubinden!

Literatur

Semi-Supervised Clustering with User Feedback; David Cohn and Rich Caruana and Andrew McCallum. Technical report, 2000.

http://www.informatik.uni-ulm.de/ni/Lehre/SS06/SeminarNI/index.html ( Eberhardt, Zhou)

Wikipedia; http://de.wikipedia.org/wiki/Clusteranalyse http://wwwi2.informatik.uni-wuerzburg.de/lehre/se0506/

ausarbeitungen/jost.pdf.

Danke für die Aufmerksamkeit