8. Clustering Flashcards
Allgemein/Definition Clustering
Cluster = Sammlung von ähnlichen Objekten Clustering = unüberwachte Segementierung (unsupervised)
Anwendungsgebiete:
> Erkennen von Mustern/Gemeinsamkeiten in den Daten
> Datenreduktion (Einheitliche Behandlung von Instanzen eines Clusters) > durhc Repräsentanten
= hier wird also nach gemeinschaftlichem Muster gesucht
Typische Anwendungen/Applikationen von Clustering
> Erkennung von Kundengruppen
Datenverteilungen untersuchen
Vorverarbeitung der Daten für die Klassifikation
Was sind die Voraussetzungen fpr Clustering?
bei numerischen Attributen
> Instanzen sind als Punkte im Raum beschreibbar
- Punkte = Vektor reeler Zahlen
- Länge des Vector = Anzahl Dimensionen im raum
Distanz zwischen zwei Punkten ist berechenbar = Ähnlichkeit zwsichen den Punkten
- Typische Distanzmaße (Euklidische Distanz, Mannhatten,…)
Was sind die Anwendungsfälle für Clustering?
> gut geeignet für Daten m it wenigen Dimensionen
Problem:
> Hochimensionale Daten (mehrere Attribute/Dimensionen)
Bsp.: Clustern nach Titel eines Dokuments
- hier beliebig viele Wörter, schwer zu clustern
> nichtnumerische Attribute
- Verwendung alternativer Distanzmaße
z.B.: Jaccard, Cosine, Edit
- Clustering Ansatz
Welche zwei Vorgehen gibt es hierbei?
Art 1: Bottom Up
> Start: Jeder Punkt = sein eigenes Cluster
> Kombination der Punkte zu Cluster gemäß ihrer “Nähe”, bis Endbedingungen erfüllt ist
> Mögliche Endbedingungen:
- Festgelegte Anzahl Cluster erreicht
- Maß für die Kompaktheit des Clusters erfüllt
Art 2: Top-Down
> Start: Ein Cluster
> Rekursives Splitten der Cluster gemäß ihrer “Nähe” bis Endbedingungen erfüllt ist
Was sind Strategien der hierarchischen Clustering Algorithmen?
Punktzuordnungsalgorithmen
> Start: Punkte werden der Reihe nach verarbeitet
> Jeder Punkt wird dem Cluster zugeordnet, zu dem er am ehesten passt
> Festlegung der initialen Cluster erfolgt in Evaluationsphase
Nennen Sie drei Clustering Algorithmen
> HIerarchisches Clustering
K-Means/Nearesst Neighbor Clustering
CURE Clustering (Repräsentant statt Zentroid)
Was beschreibt der Fluch der Dimensionalität?
in hochdim. Räumen sind fast alle Punktpaare gleich weit voneinander entfernt
> es gibt kaum Punkte in hochdim. Räumen die nah beieinander liegen
> durchschnittliche Distanz entspricht deshalb nahezu der maximalen Distanz zwischen zwei Punkten
> Finden von Clustern daher sehr schwer
Vorgehen bei dem hierarchischen Clustern im Detail
> Wahl einer geeigneten Distanzfunktion
- Euklidische Distanz, Manhatten
Repräsentation des Cluster durch dessen Zentroid (Schwerpunkt der Fläche) oder dem Durchschnitt der Punkte
Start: Jeder Punkt ist ein Cluster i(der Zentroid)
Berechnung der Distanzen zwischen den Zentroiden der Cluster
Die Cluster mit der geringsten Distanz werden zusammengelegt => Bestimmung des Zentroids des neuen Clusters
Nennen Sie drei Stoppbedingungen für hierarchisches CLustering
> Festgelegte Anzahl an Clustern ist erreicht
Maß für die Kompaktheit des Clusters ist erfüllt
Es ist nur noch ein CLuster vorhanden
Vorgehen für ein optimales und effizientes hierarchisches Clustering
> Bei jedem Schritt muss die Distanz zwischen allen CLustern berechnet werden
Optimierungen
- Alle Distanzen Berechnen
- Clusterpaare nach ihrer Distanz sortiert ablegen
- Beim Vereinigen zweier Cluster die nun obsoleten Einträge aus der sortierten Liste entfernen
- Neuberechnung der DIstanen des neuen Clusters mit allen anderen Clustern und ablegen der DIstanen in die sortierte Liste
(Nur Schritt 3 und 4 müssen mehrmals durchgeführt werden)
Nennen Sie alternative Clusterauswahlen für hierarchisches CLustering
- Singe Linkage (kürzester Abstand zwischen den Punkten aus zwei Clustern)
- Complete Linkage (größter Abstand zwischen den Punkten aus zwei Clustern)
- Average Linkage: Distanz = der durchschnittliche Abstand aller Punkt x und y
- Radius: maximaler Abstand eines Punkts des Clusters zum Zentroid
- DUrchmesser: maximaler ABstand zwsichen zwei Punkten innerhalb des CLusters
Vorgehen beim CLustern von nichtnumerischen Attributen
> DIstanzberechnung durch Jaccard, Cosine, Edit DIstanzmaße
Zentroid zur Repräsentation eines Clusters steht nicht zur Verfügung
Lösung: Auswahl eines Punktes als Repräsentatn des CLuster => Clustorid
K-Means Algorithmus (Clustering), Nennen Sie: Voraussetzung Vorgehen Stopp des Verfahrens Alternativen Problem
Voraussetzung:
> Euklidischer Raum => Numerische Attribute
(nichtnummerische Attribute nicht möglich)
> Festlegung der Anzahl der zu erzeugenden Cluster k
(k = Clustermenge)
Vorgehen:
1. Wahl von k Punkten als Anfangszentren
= Initiale Zentroiden der k Cluster
—wiederhole
2. Ordne jeden Punkt dem Cluster zu, zu dessen Zentrum er am nähesten liegt
3. Berechne Clusterzentren neu
—-bis sich die Zentren nicht mehr ändern
- Für alle übrigen Punke p
- Finde den Zentroid mit minimalen Abstand zu p
- Füge p dem Cluster hinzu und korrigiere dessen Zentroid entsprechend
(Also Distanz wieder imit Euklidischer Funktion neu berechnen)
Stopp des Verfahrens:
> bei der Überprüfung keine Punkte mehr anderen Clustern zugeordnet werden müssen
Alternativen
> Mehrfache Anwendung des Verfahrens und danach Auswahl des besten Modells
> Messung der Verzerrung der Cluster
Problem:
> jeder Punkt einem Cluster zugewiesen, somit gibt es keine Möglichkeit Ausreißer zu erkennen
Ermittlung des optimalen k Werts?
> Austesten verschiedener Werte für k
> Abstand sinkt zunächst stark bis zum optimalen k, dann nur noch gering
> wenig k großer Abstand mit steigendem k ABstand zwischen Zentroiden immer geringe
