29
PG Intelligence Service Vortrag : Semi-supervised Clustering Vortragender: Erkan Kaz Veranstalterin: Prof. Dr. Katharina Morik Betreuer: Dipl. Informatiker Felix Jungermann

PG Intelligence Service

  • Upload
    tabib

  • View
    34

  • Download
    0

Embed Size (px)

DESCRIPTION

PG Intelligence Service. Vortrag : Semi-supervised Clustering Vortragender: Erkan Kaz Veranstalterin: Prof. Dr. Katharina Morik Betreuer: Dipl. Informatiker Felix Jungermann. Gliederung. 1. Einleitung 2. Clusteranalyse 2.1 Allgemein 2.2 Algorithmen 2.3 Beispiel - PowerPoint PPT Presentation

Citation preview

Page 1: PG Intelligence Service

PG Intelligence Service

Vortrag : Semi-supervised ClusteringVortragender: Erkan Kaz

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

Page 2: PG Intelligence Service

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

Page 3: PG Intelligence Service

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

Page 4: PG Intelligence Service

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.

Page 5: PG Intelligence Service

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

Page 6: PG Intelligence Service

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

Page 7: PG Intelligence Service

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) }

Page 8: PG Intelligence Service

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) }

Page 9: PG Intelligence Service

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

Page 10: PG Intelligence Service

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

Page 11: PG Intelligence Service

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)

Page 12: PG Intelligence Service

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

Page 13: PG Intelligence Service

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

Page 14: PG Intelligence Service

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

Page 15: PG Intelligence Service

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)

Page 16: PG Intelligence Service

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

Page 17: PG Intelligence Service

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.

Page 18: PG Intelligence Service

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!

Page 19: PG Intelligence Service

5.3

Pseudo- Code:

Page 20: PG Intelligence Service

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.)

Page 21: PG Intelligence Service

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:

Page 22: PG Intelligence Service

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!

Page 23: PG Intelligence Service

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

Page 24: PG Intelligence Service

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%)

Page 25: PG Intelligence Service

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.

Page 26: PG Intelligence Service

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

Page 27: PG Intelligence Service

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!

Page 28: PG Intelligence Service

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.

Page 29: PG Intelligence Service

Danke für die Aufmerksamkeit