KDD (Kap 3: Klassische Data-Mining Verfahren)

• Clustering
  • partitionierende Verfahren
  • dichtebasierte Verfahren
• Frequent Pattern Mining
  • Apriori-Verfahren
  • ohne Kandidatengenerierung
• Entscheidungsbaumverfahren (Klassifikation)

Unter Clusteranalyse (Clustering-Algorithmus, gelegentlich auch: Ballungsanalyse) versteht man Verfahren zur Entdeckung von Ähnlichkeitsstrukturen in (großen) Datenbeständen. (-> Häufungspunkt von Objekten im multidimenstionalen Raum)

Die so gefundenen Gruppen von „ähnlichen“ Objekten werden als Cluster bezeichnet, die Gruppenzuordnung als Clustering. Die gefundenen Ähnlichkeitsgruppen können hierarchisch oder agglomerativ (dichtebasiert) sein, also Untergruppen oder Teilgruppen in Gruppen kennzeichnen.

Die Clusteranalyse ist eine wichtige Disziplin des Data-Mining, dem Analyseschritt des Knowledge Discovery in Databases Prozesses.

Clusterverfahren unterscheiden sich in

• dichtebasierte Verfahren
• hierarschische Verfahren

Identifikation einer endlichen Menge von Kategorien/Klassen (Clustern) um Daten so zu beschreiben, dass

(a) Objekte im gleichen Cluster möglichst ähnlich und

(b) Objekte aus verschiedenen Clustern möglichst unähnlich zueinander

sind

• Ähnlichkeitsbegriff
• Cluster unterschiedlicher Größe, Form und Dichte
• Cluster können hierarchisch ineinander verschachtelt sein

• Kundensegmentierung
  • Clustering der Kundentransaktionen
• Bestimmung von Benutzergruppen auf dem Web
  • Clustering der Web-Logs
• Strukturierung von großen Mengen von Textdokumenten
  • Hierarchisches Clustering der Textdokumente
• Erstellung von thematischen Karten aus Satellitenbildern
  • Clustering der aus den Rasterbildern gewonnenen Featurevektoren

Ähnlichkeit

Ein Maß für die „Nähe“ von Paaren von Objekten o1, o2 wird durch eine Distanzfunktion dist modelliert, die sich auf direkte oder abgeleitete Eigenschaften der Objekte stützt.

• kleine Distanzen = ähnliche Objekte
• große Distanzen = unähnliche Objekte

Clusteranalyse wird manchmal auch als „Distanzgruppierung“ bezeichnet

Die Güte einer Clusteranalyse hängt stark von der Adäquatheit der Distanzfunktion dist ab

• L-Metrik (Minkowski-Distanz)
• Euklidische Distanz
• Manhattan Distanz
• Maximums-Metrik

s. Abb.

Partitionierende Verfahren zerlegen eine Datenmenge in k Cluster, wobei gilt:

• jeder Cluster enthält mindestens ein Objekt
• jedes Objekt gehört genau zu einem Cluster

Voraussetzung ist, dass die Objekte Punkte in einem d-dimensionalen euklidischen Vektorraum sind. -> Verwendung der euklidischen Distanz für die Ähnlichkeit.

Zentroide:

Jeder Cluster wird durch seinen Zentroid repräsentiert. Zentroid eines Clusters ist anschaulich der Mittelwert aller Punkte des Clusters.

Das Ziel ist es, die Cluster so kompakt wie möglich zu bilden (s.Abb.). Die k Klassen werden so gebildet, dass die Varianz bezüglich der gegebenen Mittewerte minimal wird („Varianz minimierende Techniken“).