5. Mining in hochdimensionalen Daten
Inhalt dieses Kapitels
5.1 Einführung
Motivation, Überblick
5.2 Dimensionsreduktion
Grundlagen, Techniken, Diskussion
5.3 Projected Clustering
Grundlagen, Techniken, Diskussion
5.4 Subspace Clustering
Grundlagen, Techniken, Diskussion
5.5 CCCC: Computing Correlation Connected Clusters
Grundlagen, Techniken, Diskussion
210
5.1 Einführung
„Reale Daten sind meist sehr hochdimensional“
Beispiel:
• Clustering von Fernsehbildern
- Fernsehbilder werden in Farbhistogramme
zerlegt
...
- Je nach Farbauflösung erhält man ca.
100-1.000 dimensionale Feature-Vektoren pro Bild
...
• Biologie: Clustering von Microarray Daten
- Ein Feature entspricht z.B. einem Gen
im menschlichen Körper
- Man erhält 20.000 dimensionale Vektoren
211
Einführung
Probleme für das Data Mining
1.
Eine hohe Anzahl an irrelevanten Attributen (Features) „verwischt“
die Klassen
Je mehr Features, desto höher die Wahrscheinlichkeit
irrelevanter Features
2.
„Fluch der Dimensionalität“ (Curse of Dimensionality)
Distanz zum nächsten Nachbarn unterscheidet sich
im Hochdimensionalen kaum von der Distanz zu einem
beliebigen Nachbarn
3.
Klassen in verschiedenen Unterräumen
Für zwei Klassen können zwei verschiedene Mengen an Attributen
relevant/irrelevant sein
212
Einführung
Beispiele
Keine Cluster im gesamten Featurespace, aber in Unterräumen
Punkte unterschiedlich geclustert in verschiedenen Unterräumen
A
C
3
1
2
5
2
4
3
6
B
4 5
1 6
D
213
Einführung
1. Konsequenzen für die Klassifikation
•
Nicht so schlimm, da Klassen bereits bekannt und irrelevante Features
als auch entsprechende Unterräume anhand der Trainingsdaten leichter
erkannt werden können.
2. Konsequenzen für das Clustering
•
•
Cluster sind a priori nicht bekannt, daher auch nicht die irrelevanten
Features oder die entsprechenden Unterräume der Cluster
Viele (speziell distanzbasierte) Clusterverfahren sind für
hochdimensionale Daten unbrauchbar
Grund: „übliche“ Distanzfunktionen (z.B. Lp-Normen)
berücksichtigen alle Feature gleich stark
214
Einführung
Übersicht: Clustering hochdimensionaler Daten
1. Dimensionsreduktion / Attributsselektion
2. Projected Clustering
3. Subspace Clustering
4. Clustering mit Correlation-Connections
215
5.2 Dimensionsreduktion
Idee:
• Daten-Vorverarbeitung: Reduktion der Dimensionalität durch Selektion
der (für das Clustering) relevanten Features
• Verwende Datensatz mit reduzierter Dimensionalität zum Clustern
Allgemein:
• Gegeben: n Datenpunkte (Featurevektoren) X = {x1,...,xn}
mit
Dimensionalität d
• Gesucht: Transformation der Datenpunkte in (d-k)-dimensionale
Featurevektoren, so daß der dabei gemachte Fehler möglichst klein ist
Einfacher Ansatz:
• Abgeleitete Attribute (Summe, Durchschnitt, etc.) statt urspr. Attribute
- erfordert Expertenwissen
- kaum automatisierbar
(+) teilweise gute Ergebnisse (hängt vom Experten ab)
216
Dimensionsreduktion
Hauptachsentransformation (PCA)
Ziel: Rotiere den Datenraum so, dass
• die Abhängigkeiten zwischen den Merkmale verschwinden
• Abstände und Winkel der Vektoren erhalten bleiben
Gesucht ist also...
• eine orthonormale Abbildung,
• die die Richtung stärkster Varianz auf die erste Achse abbildet
• die Richtung zweitstärkster Varianz auf die zweite usw.
217
Dimensionsreduktion
• Wir beginnen mit der Kovarianz-Matrix: S = SxD(x-m)(x-m)T
• Die Matrix wird zerlegt in
• eine Orthonormalmatrix V = [e1,...,ed] (Eigenvektoren)
• und eine Diagonalmatrix L = diag (l1,...,ld) (Eigenwerte)
• so dass gilt: S = V L VT
• Bei Weglassen von k Basisvektoren ej entsteht ein neuer
Unterraum. Die Transformation der Vektoren aus X in diesen
neuen Unterraum hat den quadratischen Fehler:
 Wähle die k Eigenvektoren mit den kleinsten Eigenwerten
218
Dimensionsreduktion
Dimensionsreduktion via PCA
1. Berechne Kovarianzmatrix S
2. Berechne Eigenwerte und Eigenvektoren von S
3. Bestimme die k kleinsten Eigenwerte und „lösche“ deren Eigenvektoren
4. Die resultierenden Eigenvektoren bilden die Basis für den neuen Unterraum
(ggf. kann diese Basis durch unitäre Transformationen in eine andere Basis
desselben Unterraumes umgewandelt werden)
5. Entwickle die Vektoren der Daten X = {x1,...,xn} nach dieser neuen
Unterraumbasis:
 Resultierende Daten Y = {y1,...,yn} sind (d-k)-dimensional
219
Dimensionsreduktion
Beispiel
3
Daten: X = {
(-3,-2), (-2,-1), (-1,0), (0,1), (1,2), (2,3)
(-2,-2), (-1,-1), (0,0), (1,1), (2,2)
(-2,-3), (-1,-2), (0,-1), (1,0), (2,1), (3,2)
}
2
1
0
-1
-2
Kovarianzmatrix:
-3
-2
-1
0
1
2
3
Eigenwerte und
Eigenvektoren:
Transformierte Daten Y = {
(-3.53), (-2.12), (-0.71), (0.71), (2.12), (3.53)
(-2.82), (-1.41), (0.0), (1.41), (2.82)
(-3.53), (-2.12), (-0.71), (0.71), (2.12), (3.53)
}
0
220
Dimensionsreduktion
Diskussion
+ Mathematisch fundiert
- transformierte Daten sind nur schwer interpretierbar
(Unterraum ist nicht notwendigerweise achsenparallel)
- Informationen der „gelöschten“ Dimensionen werden nicht berücksichtigt
Weitere Verfahren
• Wavelet-Transformation
• (diskrete) Fourier-Transformation
• (diskrete) Cosinus-Transformation
221
5.3 Projected Clustering
Beobachtung:
• Dimensionsreduktion ist zu unflexibel
• Cluster können in verschiedenen Unterräumen des Feature-Raumes
existieren
Idee des Projected Clusterings:
• Jeder Cluster darf in einem speziellen Unterraum liegen
• Ermittle Paare (Ci, Si) wobei:
- Ci ist die Menge der Punkte, die zu Cluster i gehören
- Si ist der Unterraum, in dem Ci existiert, d.h. ein Clusteringkriterium ist
optimal erfüllt
222
Projected Clustering
PROCLUS [Aggarwal & Procopiuc 1999]
•
•
•
Erweitert k-Medoid Verfahren CLARANS um die Idee, jedem Cluster
seinen entsprechenden Unterraum zuzuordnen
Verwendet Manhattan Distanz (L1) geteilt durch die
Unterraumdimension, um Objekt-Distanzen aus verschiedenen
Unterräumen „objektiv“ zu vergleichen
Benötigt Anzahl der Cluster k und durchschnittliche Dimension der
Cluster l als Eingabe
Phase 1 Initialisierung: Bestimmen der initialen Medoide durch
„Greedy“-Methode auf DB-Sample
-
Beginne mit einem zufälligen Medoid
Wähle den weitest entferntesten Punkt zu allen bisherigen Medoiden als
neuen Medoid bis k Medoide ausgewählt sind.
223
Projected Clustering
Phase 2 Iteration: Optimierung der Medoide und der Cluster-Unterräume
- Medoid-Optimierung wie bei CLARANS
- Unterraumoptimierung:
di = minimale Distanz des Medoiden mi zu allen anderen Medoiden
Li = {Punkte, die zu mi einen kleineren Abstand als di haben}
Xi,j = durchschnittliche Distanz aller Punkte aus Li zu mi in Dimension j
Je kleiner Xi,j desto näher liegen die Punkte in Li,j entlang Dimension j bei mi
Wähle Unterräume Si, so dass insgesamt k . l Dimensionen zu den Medoiden
zugeordnet wurden (Greedy-Verfahren)
Zuordnung der Punkte zu den mi unter Berücksichtigung der ausgewählten Si
224
Projected Clustering
Diskussion
• Nachteile lokal optimierender Verfahren wie k-Medoids
-
Konvergiert evtl. nur gegen ein lokales Minimum
Eingabeparameter k schwer zu bestimmen
Anfällig gegen Rauschen
Berechnet nur konvexe Cluster
• Weitere Nachteile:
- Inputparameter l schwer zu bestimmen
- Findet nur achsenparallele Projektionen
x
z
Q
x
P
P
Q
P
y
z
Q
y
Q
P
y
y
225
Projected Clustering
ORCLUS [Aggarwal & Yu 2000]
•
•
•
•
Verbesserung von PROCLUS
Verwendet k-Means statt k-Medoid Ansatz
Berechnet Unterräume, die nicht achsenparallel sind
Verwendet Korrelationsmatrix, um für jeden Cluster die Eigenvektoren
mit den kleinsten Eigenwerten zu berechnen
• Eingabe: k Anzahl der Cluster, l durchschnittliche Dimensionalität der
Cluster-Unterräume
• Ergebnis: k Cluster (Ci) mit zugeordneten Eigenvektoren (Si)
• Probleme:
- Nachteile von k-Means
- Input-Parameter l
- Laufzeit: O (l3 + l . n . d + l2 + d3)
226
5.4 Subspace Clustering
Beobachtung:
• Projected Clustering Methoden finden Cluster in verschiedenen
Unterräumen
• ABER: Punkte können in verschiedenen Unterräumen in verschiedenen
Clustern liegen
Idee des Subspace Clusterings:
• Berechne Clustering für mehrere Unterräume
• Vollständige Suche ist nicht effizient (O (2d) mögliche Unterräume)
• Daher: Finde alle (möglichst viele) Unterräume, in denen Cluster liegen
227
Subspace Clustering
CLIQUE [Agrawal, Gehrke, Gunopulos & Raghavan 1998]
1. Identifikation von Unterräumen mit Clustern
2. Identifikation von Clustern
•
Cluster: „dichtes Gebiet“ im Datenraum
•
Dichte-Grenzwert t
Region ist dicht, wenn sie mehr als t Punkte enthält
Region = Gitterzelle
•
Gitterbasierter Ansatz
jede Dimension wird in  Intervalle aufgeteilt
Cluster ist Vereinigung von verbundenen dichten Regionen
228
Subspace Clustering
Identifikation von Unterräumen mit Clustern
• Aufgabe: Entdecken dichter Regionen
• Greedy-Algorithmus (Bottom-Up), ähnlich wie Apriori-Algorithmus bei der
Warenkorbanalyse:
- beginne mit der leeren Menge
- nehme jeweils eine Dimension dazu
• Grundlage dieses Algorithmus: Monotonie-Eigenschaft
wenn eine Region R im k-dimensionalen Raum dicht ist, dann ist auch jede
Projektion von R in einen (k-1)-dimensionalen Unterraum dicht
• Umkehrung:
Wenn eine (k-1)-dimensionale Region R nicht dicht ist, sind alle k-dimensionalen
Regionen, die R als Projektion besitzen, nicht dicht.
229
Subspace Clustering
Beispiel
2-dim. dichte Regionen
3-dim. Kandidaten-Region
2-dim. Region, die geprüft
werden muß
• auch die Regionen, die in Unterräumen dicht sind, müssen

noch auf der DB gezählt werden (enthalten sie wirklich mehr
als t Punkte?)
• heuristische Reduktion der Anzahl der Kandidaten-Regionen
230
Subspace Clustering
Identifikation von Clustern
• Aufgabe: Finden maximaler Mengen verbundener dichter Regionen
• Gegeben: alle dichten Regionen in demselben k-dimensionalen Unterraum
• „depth-first“-Suche in folgendem Graphen (Suchraum)
Knoten: dichte Regionen
Kanten: gemeinsame Hyperflächen / Dimensionen der beiden
dichten Regionen
• Laufzeitkomplexität
dichte Regionen im Hauptspeicher (z.B. Hashbaum)
für jede dichte Region 2 k Nachbarn zu prüfen
 Zahl der Zugriffe zur Datenstruktur: O (2 . k . n)
231
Subspace Clustering
Experimentelle Untersuchung
Laufzeit in Abhängigkeit von n
Laufzeit in Abhängigkeit von d
Laufzeitkomplexität von CLIQUE
linear in n, superlinear in d
232
Subspace Clustering
Diskussion
+ automatische Entdeckung von Unterräumen mit Clustern
+ automatische Entdeckung von Clustern
+ keine Annahme über die Verteilung der Daten
+ Unabhängigkeit von der Reihenfolge der Daten
+ gute Skalierbarkeit mit der Anzahl n der Datensätze
- Genauigkeit des Ergebnisses hängt vom Parameter  ab
- braucht eine Heuristik, um den Suchraum aller Teilmengen der Dimensionen
einzuschränken
 findet u.U. nicht alle Unterräume mit Clustern
233
Subspace Clustering
Erweiterungen von CLIQUE
• ENCLUS [Cheng, Fu & Zhang 1999]
- Unterschied zu CLIQUE:
Anderes Dichtekriterium für Regionen: Entropie H(X) fürMenge von Regionen
H(X) = - SxX d(x) . log d(x)
(d(x) Anteil der Datenpunkte in Region x)
- Entropie verhält sich ebenfalls monoton
• MAFIA [Goil, Nagesh & Choudhary 1999]
- Adaptives Gitter  weniger Regionen variabler Größe
- Finde Regionen, die um Faktor  dichter sind als der erwartete
Durchschnitt (relativ zum Volumen)
- Keine Monotonie-Eigenschaft, daher Brute-Force Navigation durch den
Suchraum aller möglichen Unterräume
234
Subspace Clustering
RIS [Kailing, Kriegel, Kröger & Wanka 2003]
Motivation:
• Nachteil der gitterbasierten Ansätze
Wahl von  und t
Cluster für t = 4
C1
(ist C2 Cluster?)
Für t > 4: keine Cluster
(insb. C1 geht verloren!)
C2
 Verwende dichte-basiertes Clustering
235
Subspace Clustering
Idee:
• Cluster enthalten mindestens einen Kernpunkt
• Anzahl der Kernpunkte ist proportional zur
- Anzahl der verschiedenen Cluster
und/oder
- Größe der Cluster
und/oder
- Dichte der Cluster
Anzahl
size
density
236
Subspace Clustering
Algorithmus SUBCLU:
1. Berechne für jeden Punkt p der Datenbank die Unterräume, in denen p
noch Kernpunkt ist
 Berechnet alle relevanten Unterräume
2. Sammle für jeden berechneten Unterraum statistische Informationen
um über die „Interessantheit“ des Unterraumes entscheiden zu können
 Qualität der Unterräume (z.B. Anzahl der Kernpunkte)
 Sortierung der Unterräume nach „Interessantheit“ möglich
3. Entferne Unterräume, die redundante Informationen enthalten
 Cluster in einem Unterraum S sind in allen Unterräumen T  S enthalten
237
Subspace Clustering
Schritt 1
Suche Unterräume, die mindestens einen Kernpunkt enthalten:
• Erschöpfende Suche wieder O (2d)
• Lemma (Monotonie der Kernpunkteigenschaft):
Wenn p ein Kernpunkt in Featureraum S ist, dann ist p auch ein Kernpunkt in
allen Unterräumen T  S
Wenn p in T kein Kernpunkt ist, kann p auch in allen S  T kein Kernpunkt sein.
 Verwende Apriori-Algorithmus (Warenkorbanalyse)
238
Subspace Clustering
Schritt 2
Qualität der gefundenen Unterräume:
• count[S] = Summe (der Anzahl) aller Punkte, die in der -Nachbarschaft aller
Kernpunkte eines Unterraumes S liegen
• NaiveQuality(S) = count[S] – Kernpunkte(S)
- Anzahl der erwarteten Punkte in einer -Nachbarschaft sinkt mit steigender
Dimension
- NaiveQuality favorisiert niedrig dimensionale Unterräume
• Skalierung in Abhängigkeit der Dimensionalität:
- Periodische Randbedingungen um Punkte, die am Rand des Datenraumes liegen,
nicht zu benachteilen
239
Subspace Clustering
Schritt 3
Entfernen redundanter Unterräume:
• „Überflüssige“ Unterräume:
- Cluster im Raum S haben eine Projektion in Unterräumen von S
- Durch die Hinzunahme von irrelevanten Dimensionen muß ein Cluster
zunächst noch nicht verschwinden
• Pruning-Schritte:
- Abwärts-Pruning:
Wenn es einen (k-1)-dimensionalen Unterraum S mit einer höheren Qualität
als ein k-dimensionaler Unterraum T (T  S) gibt, lösche T.
- Aufwärts-Pruning:
Wenn der Count-Wert eines echten (k-1)-dimensionaler Unterraumes von S
„besonders stark“ vom Mittelwert der Count-Werte aller echten
(k-1)-dimensionalen Unterräume von S abweicht, lösche S
240
Subspace Clustering
Experimentelle Untersuchung
Laufzeit in Abhängigkeit von n
Laufzeit in Abhängigkeit von d
Laufzeit in Abhängigkeit der Samplegröße
Skaliert superlinear in n und d
 Random Sampling
auch bei kleinen Samplegrößen
hohe Qualität
241
Subspace Clustering
Diskussion
Vorteile:
• Findet alle Unterräume, in denen beliebig geformte Cluster existieren
• Cluster können durch Anwendung beliebiger Clusteringverfahren
erzeugt werden (DBSCAN und OPTICS wegen gleicher/ähnlicher
Formalisierung zu empfehlen)
• Mathematisch fundierte Kriterien für die Parameterwahl
Verbesserungsmöglichkeiten:
• Parameterwahl von  bestimmt indirekt die Dimensionalität der
gefundenen Unterräume
• Basiert auf der Idee der flachen dichte-basierten Dekomposition
 hierarchische Cluster ???
242

7. Mining in hochdimensionalen Daten