DATABASESYSTEMSGROUP

Globaler Ansatz

• Hough-Transformation– stammt aus Computer-Graphik– 2-dimensional (Bild-Verarbeitung)

• Verallgemeinerung auf d-dimensionale Räume• Übertragung des Clustering in einen neuen Raum

(“Parameter-Raum” der Hough-Transformation)• Einschränkung des Suchraumes

(von nicht-abzählbar unendlich auf O(n!))• übliche Suchheuristik für Hough-Transformation: O(2d) effiziente Suchheuristik!

Zimek: Correlation Clustering 1

DATABASESYSTEMSGROUP

Hough-Transformation

• gegeben:• gesucht: lineare Unterräume, in denen viele Punkte

liegen• Idee: Abbildung von Punkten im Datenraum (Bild-Raum) auf

Funktionen im Parameter-Raum

Zimek: Correlation Clustering 2

dD Dx

p1

x

y

picture space parameter space

DATABASESYSTEMSGROUP

• ei, 1 i d: Orthonormal-Basis

• x = (x1,…,xd)T: d-dimensionaler Vektor auf Hypersphäre um den Ursprung mit Radius r

• ui: Einheitsvektor in Richtung der Projektion von x auf den Unterraum span(ei,…,ed)

1,…,d-1: i Winkel zwischen ui und ei

span(e 2,e 3

)

d-dimensionale Polarkoordinaten

Zimek: Correlation Clustering 3

e1

e2

e3

x

u11

u22u3

3=0

i

i

jji rx cossin

1

1

DATABASESYSTEMSGROUP

Parametrisierungsfunktion

Länge des Normalenvektors mit mit den Winkeln 1,…,d-1

für die Gerade durch Punkt p:

Zimek: Correlation Clustering 4

i

i

jj

d

iidp pnpf cossin,,,

1

1111

1n

n

parameter space

p1f

p2f

p3f

picture space x

y

(s, s)

p1

p2

p3

s

s

s

DATABASESYSTEMSGROUP

Eigenschaften der Transformation

Zimek: Correlation Clustering 5

• Punkt im Datenraum Sinusoid im Parameterraum• Punkt im Parameterraum Hyperebene im Datenraum• Punkte auf gemeinsamer Hyperebene im Datenraum Sinusoide mit

gemeinsamem Schnittpunkt im Parameterraum• Schnitt von Sinusoiden im Parameterraum Hyperebene durch die

entsprechenden Punkte im Datenraum

DATABASESYSTEMSGROUP

Correlation Clustering mittels Hough-Transformation

• dichte Regionen im Parameterraum lineare Strukturen im Datenraum (Hyperebenen mit d-1)

• exakte Lösung: Bestimmung aller Schnittpunkte– nicht durchführbar– zu exakt

• approximative Lösung: Grid-basiertes Clustering im Parameterraum

finde Zellen, die von mindestens m Sinusoiden geschnitten werden– Suchraum begrenzt, aber in O(rd)

– möglichst reine Cluster erfordern großes r (Auflösung des Grids)

Zimek: Correlation Clustering 6

DATABASESYSTEMSGROUP

Algorithmus CASH:effiziente Suchheuristik

CASH: Clustering in Arbitrary Subspaces based on the Hough-Transform [SIAM DM08, special issue SAM]

• Parameterraum wird rekursiv achsenweise geteilt mit einer festen Ordnung der Achsen [1, … , d-1, ]

• Fortsetzung immer mit dem Hyperquader, der die meisten Punkte repräsentiert (Prioritätssuche)

Zimek: Correlation Clustering 7

DATABASESYSTEMSGROUP

Algorithmus CASH:effiziente Suchheuristik

• Hyperquader, die weniger als m Punkte repräsentieren, können ausgeschlossen werden frühzeitiges Ende des Suchpfades

• Hyperquader, die nach s rekursiven Teilungen von mindestens m Sinusoiden geschnitten werden, repräsentieren ein Correlation Cluster (mit d-1)– Punkte des Clusters (bzw. entsprechende Sinusoide) werden aus

allen anderen Hyperquadern entfernt– rekursive Untersuchung des Clusters nach Transformation in den

entsprechenden d-1-dimensionalen Unterraum, um Correlation Cluster mit d-2 etc. zu finden

Zimek: Correlation Clustering 8

DATABASESYSTEMSGROUP

Algorithmus CASH:Eigenschaften

• findet beliebige Anzahl von Clustern• Benutzerangaben:

– Suchtiefe (Anzahl der Splits maximale Größe einer Cluster-Zelle/Genauigkeit)

– Mindestdichte einer Zelle ( minimale Anzahl von Punkten im Cluster)

• Dichte einer Zelle bezüglich Parameterraum beruht nicht auf der “locality assumption” für Datenraum globales Verfahren für Correlation Clustering

• Suchheuristik skaliert linear in Anzahl der Punkte, aber durchschnittlich mit ~ d3

• ABER: worst case-Degeneration zu vollständiger Aufzählung (exponentiell in d) ist theoretisch möglich

Zimek: Correlation Clustering 9