Analyse und Entwicklung dynamischer Clusterverfahren für eine kundenorientierte Produktempfehlung
©2005
Diplomarbeit
124 Seiten
Zusammenfassung
Inhaltsangabe:Problemstellung:
Seit Ende der neunziger Jahre unterliegt der E-Commerce Sektor einer wachsenden Dynamik. Immer mehr Menschen verfügen über einen Internetanschluss und nutzen diesen nicht nur für den Austausch von Informationen, sondern bestellen immer häufiger auch Produkte und nehmen Dienstleistungen über das Internet in Anspruch. Mittlerweile steht fest, dass sich das Internet als Distributionskanal eignet. Beim Kauf über das Internet gibt es keinen Ladenschluss, keine Standortprobleme oder lange Wartezeiten. All dies macht den Onlineeinkauf so bequem und letztlich auch immer attraktiver für die Kunden. Aufgrund dieser Entwicklung ist es nicht verwunderlich, dass auch die Umsätze, die über das Internet erwirtschaftet werden, weiter ansteigen und dadurch vermehrt neue Anbieter angezogen werden. Durch die steigende Zahl der Anbieter verschärft sich mittlerweile auch der Konkurrenzkampf im Internet.
Eine weitere erkennbare Entwicklung ist die steigende Produktvielfalt. Hierbei ist zu vermerken, dass einerseits die Anzahl der Produkte rasant zunimmt, während die Produkte andererseits immer ähnlicher und damit schwerer vergleichbar werden. Dies ist eine Entwicklung, die es speziell für weniger fachkundige Interessenten oftmals schwierig macht, die möglichen Alternativen zu überblicken. Die Fülle an verschiedenen aber doch ähnlichen und sogar austauschbaren Produkten macht es fast unmöglich, sich schnell für ein Produkt zu entscheiden.
Um dem Kunden diese Qual der Wahl zu ersparen, sind neue Methoden für eine Produktauswahl nötig. Auch ohne großes Fachwissen muss es möglich sein, die Produktvielfalt zu überschauen und für die eigenen Wünsche positiv zu nutzen.
Ziel dieser Arbeit ist es, Methoden zu entwickeln, die den Auswahlprozess für den Kunden deutlich vereinfachen. Ohne großes Fachwissen soll es jedem Interessenten möglich sein, sich schnell und einfach eine Liste der für ihn relevanten Produkte erstellen zu lassen.
Hierzu wird untersucht, ob mit Hilfe von Clustermethoden des Data Minings eine Entscheidungsunterstützung für den Bereich des E-Commerce entwickelt werden kann. Idee ist es, Produkte nach Ähnlichkeiten zu gruppieren und dem Nutzer so eine Hilfestellung bei der Auswahl der für ihn interessanten Produkte zu geben.
Im Mittelpunkt dieser Arbeit stehen die Analyse der existierenden Clusteralgorithmen sowie die Anpassung und Entwicklung eigener Verfahren zur Produktauswahl. Clusteralgorithmen bezeichnen Verfahren, die […]
Seit Ende der neunziger Jahre unterliegt der E-Commerce Sektor einer wachsenden Dynamik. Immer mehr Menschen verfügen über einen Internetanschluss und nutzen diesen nicht nur für den Austausch von Informationen, sondern bestellen immer häufiger auch Produkte und nehmen Dienstleistungen über das Internet in Anspruch. Mittlerweile steht fest, dass sich das Internet als Distributionskanal eignet. Beim Kauf über das Internet gibt es keinen Ladenschluss, keine Standortprobleme oder lange Wartezeiten. All dies macht den Onlineeinkauf so bequem und letztlich auch immer attraktiver für die Kunden. Aufgrund dieser Entwicklung ist es nicht verwunderlich, dass auch die Umsätze, die über das Internet erwirtschaftet werden, weiter ansteigen und dadurch vermehrt neue Anbieter angezogen werden. Durch die steigende Zahl der Anbieter verschärft sich mittlerweile auch der Konkurrenzkampf im Internet.
Eine weitere erkennbare Entwicklung ist die steigende Produktvielfalt. Hierbei ist zu vermerken, dass einerseits die Anzahl der Produkte rasant zunimmt, während die Produkte andererseits immer ähnlicher und damit schwerer vergleichbar werden. Dies ist eine Entwicklung, die es speziell für weniger fachkundige Interessenten oftmals schwierig macht, die möglichen Alternativen zu überblicken. Die Fülle an verschiedenen aber doch ähnlichen und sogar austauschbaren Produkten macht es fast unmöglich, sich schnell für ein Produkt zu entscheiden.
Um dem Kunden diese Qual der Wahl zu ersparen, sind neue Methoden für eine Produktauswahl nötig. Auch ohne großes Fachwissen muss es möglich sein, die Produktvielfalt zu überschauen und für die eigenen Wünsche positiv zu nutzen.
Ziel dieser Arbeit ist es, Methoden zu entwickeln, die den Auswahlprozess für den Kunden deutlich vereinfachen. Ohne großes Fachwissen soll es jedem Interessenten möglich sein, sich schnell und einfach eine Liste der für ihn relevanten Produkte erstellen zu lassen.
Hierzu wird untersucht, ob mit Hilfe von Clustermethoden des Data Minings eine Entscheidungsunterstützung für den Bereich des E-Commerce entwickelt werden kann. Idee ist es, Produkte nach Ähnlichkeiten zu gruppieren und dem Nutzer so eine Hilfestellung bei der Auswahl der für ihn interessanten Produkte zu geben.
Im Mittelpunkt dieser Arbeit stehen die Analyse der existierenden Clusteralgorithmen sowie die Anpassung und Entwicklung eigener Verfahren zur Produktauswahl. Clusteralgorithmen bezeichnen Verfahren, die […]
Leseprobe
Inhaltsverzeichnis
ID 9186
Reindler, David: Analyse und Entwicklung dynamischer Clusterverfahren für eine
kundenorientierte Produktempfehlung
Hamburg: Diplomica GmbH, 2005
Zugl.: Technische Universität Carolo-Wilhelmina zu Braunschweig, Diplomarbeit, 2005
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die
Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine
Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.
Diplomica GmbH
http://www.diplom.de, Hamburg 2005
Printed in Germany
I
Inhaltsverzeichnis
Inhaltsverzeichnis ...I
1. Einleitung... 1
1.1. Problemstellung... 1
1.2. Zielsetzung... 1
1.3. Aufbau der Arbeit ... 2
2. Knowledge Discovery in Databases... 4
2.1. Phasen des Knowledge Discovery in Databases ... 4
2.2. Normalisierung der Daten ... 8
2.3. Aufgaben des Data Minings ... 10
2.3.1.
Explorative Datenanalyse ... 12
2.3.2.
Deskriptive Datenanalyse ... 12
2.3.3.
Predictive Modeling ... 13
2.3.4.
Pattern Discovery... 13
2.3.5.
Retrieval by Content ... 14
3. Deskriptive Analyse im Data Mining: Clustering ... 15
3.1. Distanzberechnung beim Clustering ... 16
3.1.1.
Distanzberechnung bei Intervallbasierten Variablen... 18
3.1.2.
Distanzberechnung bei Binären Variablen... 20
3.1.3.
Distanzberechnung bei Nominalen Variablen ... 21
3.1.4.
Distanzberechnung bei Ordinalen Variablen ... 21
3.1.5.
Distanzberechnung bei gemischt skalierten Daten ... 21
3.1.6.
Distanzberechnung bei fehlenden Werten ... 23
3.1.7.
Distanzberechnung bei speziellen Strukturen ... 24
3.1.8.
Standardisierung der Distanzwerte... 24
3.2. Clusterverfahren... 25
3.2.1.
Partitionierende Algorithmen... 27
3.2.2.
Hierarchische Algorithmen... 34
3.2.3.
Dichtebasierte Algorithmen... 38
3.2.4.
Gitterbasierte Algorithmen ... 42
3.2.5.
Modellbasierte Algorithmen ... 44
4. Dynamisches Clustering ... 48
4.1. Anforderungen des Produktclustering... 49
II
4.2. Aktueller Forschungsstand ... 50
5. Problemmodellierung... 53
5.1. Lösungsansätze... 55
5.2. Einflussfaktoren... 58
5.2.1.
Verfahren ... 58
5.2.2.
Daten... 59
5.2.3.
Benutzer... 59
5.3. Vergleichsmöglichkeiten... 60
6. Testergebnisse... 62
6.1. Ausgewählte Anwendungsfälle ... 63
6.1.1.
Bildschirme ... 63
6.1.2.
Festplatten... 65
6.2. Einfluss des Verfahrens ... 66
6.2.1.
Spezifische Parameter ... 67
6.2.2.
Clusteranzahl... 68
6.2.3.
Distanzfunktion... 70
6.2.4.
Algorithmen ... 73
6.3. Einfluss der Daten... 77
6.3.1.
Fehlende Werte ... 77
6.3.2.
Normalisierung der Daten ... 77
6.3.3.
Spezialprodukte ... 80
6.4. Einfluss des Benutzers... 81
6.4.1.
Gewichtung ... 81
6.4.2.
Vorabauswahl... 85
6.5. Repräsentation der Cluster... 87
6.6. Laufzeit der Verfahren... 89
6.7. Zusammenfassung der Ergebnisse ... 90
7. Schlussbetrachtung ... 94
Anhang ... 97
Literaturverzeichnis... 108
Abbildungsverzeichnis ... 113
Tabellenverzeichnis... 114
Glossar ... 116
Einleitung Kapitel
1
1
1. Einleitung
1.1. Problemstellung
Seit Ende der neunziger Jahre unterliegt der E-Commerce Sektor einer wachsenden Dynamik
[Fri01a]. Immer mehr Menschen verfügen über einen Internetanschluss und nutzen diesen
nicht nur für den Austausch von Informationen, sondern bestellen immer häufiger auch
Produkte und nehmen Dienstleistungen über das Internet in Anspruch [Kor00]. Mittlerweile
steht fest, dass sich das Internet als Distributionskanal eignet. Beim Kauf über das Internet
gibt es keinen Ladenschluss, keine Standortprobleme oder lange Wartezeiten [Sch04]. All
dies macht den Onlineeinkauf so bequem und letztlich auch immer attraktiver für die Kunden.
Aufgrund dieser Entwicklung ist es nicht verwunderlich, dass auch die Umsätze, die über das
Internet erwirtschaftet werden, weiter ansteigen [Sch04] und dadurch vermehrt neue Anbieter
angezogen werden. Durch die steigende Zahl der Anbieter verschärft sich mittlerweile auch
der Konkurrenzkampf im Internet [GKD00].
Eine weitere erkennbare Entwicklung ist die steigende Produktvielfalt. Hierbei ist zu
vermerken, dass einerseits die Anzahl der Produkte rasant zunimmt, während die Produkte
andererseits immer ähnlicher und damit schwerer vergleichbar werden [BNHH04]. Dies ist
eine Entwicklung, die es speziell für weniger fachkundige Interessenten oftmals schwierig
macht, die möglichen Alternativen zu überblicken. Die Fülle an verschiedenen aber doch
ähnlichen und sogar austauschbaren Produkten macht es fast unmöglich, sich schnell für ein
Produkt zu entscheiden.
Um dem Kunden diese ,,Qual der Wahl" zu ersparen, sind neue Methoden für eine
Produktauswahl nötig. Auch ohne großes Fachwissen muss es möglich sein, die
Produktvielfalt zu überschauen und für die eigenen Wünsche positiv zu nutzen.
1.2. Zielsetzung
Ziel dieser Arbeit ist es, Methoden zu entwickeln, die den Auswahlprozess für den Kunden
deutlich vereinfachen. Ohne großes Fachwissen soll es jedem Interessenten möglich sein, sich
schnell und einfach eine Liste der für ihn relevanten Produkte erstellen zu lassen.
Hierzu wird untersucht, ob mit Hilfe von Clustermethoden des Data Minings eine
Entscheidungsunterstützung für den Bereich des E-Commerce entwickelt werden kann. Idee
ist es, Produkte nach Ähnlichkeiten zu gruppieren und dem Nutzer so eine Hilfestellung bei
der Auswahl der für ihn interessanten Produkte zu geben.
Einleitung Kapitel
1
2
Im Mittelpunkt dieser Arbeit stehen die Analyse der existierenden Clusteralgorithmen sowie
die Anpassung und Entwicklung eigener Verfahren zur Produktauswahl. Clusteralgorithmen
bezeichnen Verfahren, die es ermöglichen, eine Menge von Objekten in unterschiedliche
Cluster einzuteilen. Dabei sollen Objekte innerhalb desselben Clusters möglichst homogen
sein, während Objekte aus unterschiedlichen Clustern möglichst heterogen sein sollen. Mit
Hilfe solcher Algorithmen könnte es dem Nutzer ermöglicht werden, sich schrittweise durch
die Menge von Produkten zu arbeiten. Bei jedem Schritt werden die Produkte in mehrere
Cluster aufgeteilt und nach Ähnlichkeit gruppiert. Durch die Auswahl eines speziellen
Clusters kann der Kunde die Produktgruppe nach und nach einschränken. Im Idealfall ergibt
sich dadurch am Ende eine Auswahl aller Produkte, die die speziellen Anforderungen des
Kunden erfüllen. Alle irrelevanten Produkte, die diesen Anforderungen nicht entsprechen,
sind durch die Entscheidung für ein spezielles Cluster bereits weggefallen.
Auf dem Gebiet des Clusterings könnten hierzu bereits einige anwendbare Algorithmen
existieren. In dieser Arbeit werden daher die Anforderungen an die Clusterverfahren anhand
eines konkreten Beispielmarktes herausgearbeitet. Durch einen Vergleich der Anforderungen
mit den Eigenschaften der Algorithmen könnte so ein geeignetes Verfahren ermittelt und
implementiert werden.
1.3. Aufbau der Arbeit
Die Struktur der Arbeit gliedert sich in sieben Kapitel. Im Anschluss an die Einleitung wird in
Kapitel zwei und drei auf die theoretischen Grundlagen des Data Minings eingegangen. Der
Knowledge Discovery Prozess bildet den Einstieg in das Thema. In Kapitel zwei werden die
Phasen dieses Prozesses kurz beschrieben und die für die Problemstellung relevanten Aspekte
herausgearbeitet. Die entscheidende Phase ist dabei das Data Mining, der eigentliche Schritt
der Informationsgewinnung. Im Abschnitt 2.2 werden die verschiedenen Aufgabengebiete des
Data Minings kurz vorgestellt, der Fokus wird aber auf das Clustering gelegt, da diese
Methoden eine mögliche Problemlösung darstellen. Das Kapitel drei soll einen umfassenden
Einblick in diesen Forschungsbereich geben und die unterschiedlichen Verfahren
gegeneinander abgrenzen.
Aufbauend auf diesen Grundlagen wird in Kapitel vier und fünf die Problemstellung näher
beschrieben, und es wird ein erster Lösungsansatz vorgeschlagen. Zunächst werden die
speziellen Probleme des dynamischen Clusterings dargestellt. Die Herausforderung beim
dynamischen Clustering stellt die Interaktion mit dem Benutzer dar. Durch die aktive
Beeinflussung des Clusterprozesses treten aber neue Probleme auf, die in Kapitel vier genauer
Einleitung Kapitel
1
3
dargestellt werden. Außerdem wird der aktuelle Stand der Forschung näher untersucht. Das
Kapitel fünf soll die Grundlagen Clustering in einen engeren Zusammenhang mit der
Problemstellung bringen. Hierbei werden die verschiedenen Aspekte miteinander verknüpft
und die möglichen Einflussfaktoren näher beschrieben.
Abschließend soll das Kapitel sechs der Arbeit diese Lösungsansätze durch ein praktisches
Beispiel evaluieren und die Auswirkungen der Einflussfaktoren detailliert untersuchen.
Anschließend werden die Ergebnisse in Kapitel sieben zusammengefasst, es werden
Potentiale identifiziert und eine Handlungsempfehlung für die Zukunft gegeben.
Des Weiteren befindet sich am Ende der Arbeit ein Glossar, dieses dient dazu, einzelne
Begriffe der Arbeit näher zu erläutert. Begriffe, die im Glossar definiert wurden, sind in der
Arbeit kursiv gedruckt. Der darauf folgende Anhang stellt detaillierte Testergebnisse zur
Verfügung.
Knowledge Discovery in Databases
Kapitel 2
4
2. Knowledge Discovery in Databases
Durch die enormen Fortschritte auf dem Gebiet der Informationstechnik ist es seit einiger Zeit
möglich, immer größere Datenmengen zu erfassen [BR99]. Daten werden von fast allen
Geschäftsbereichen gespeichert. Diese können Umsatzzahlen von Supermarktketten,
Kundeninformationen von Banken, aber auch physikalische Messreihen oder ähnliches
enthalten. Kapazitätsgrenzen gibt es beim Speichern von Daten fast keine mehr. Die sinnvolle
Auswertung dieser Datenbestände kann einen entscheidenden Wettbewerbsvorteil schaffen,
ist aber keinesfalls als trivial anzusehen. Vor allem die Größe vieler Datenbanken macht eine
Auswertung kompliziert und aufwendig, aber auch die Struktur der Daten kann den
Analyseprozess erschweren. Auf die Probleme, die während des KDD Prozesses auftreten
können, wird in der Arbeit noch detaillierter eingegangen.
Unter dem Begriff Knowledge Discovery in Databases (KDD) ist Anfang der 90er Jahre ein
Forschungsgebiet entstanden, das sich mit den Problemen der Datenauswertung befasst. Eine
häufig verwendete Definition stammt von Fayyad et al. [FPS96]: "Knowledge Discovery in
databases is the non-trivial process of identifying valid, novel, potentially useful, and
ultimately understandable patterns in data." Diese Definition deutet bereits an, dass unter dem
Begriff KDD ein Prozess verstanden wird, der aus mehreren Phasen besteht. Der Inhalt der
verschiedenen Phasen wird im folgenden Abschnitt beschrieben. Das Ziel dieses Prozesses ist
es, die Struktur der Daten näher zu untersuchen und verborgene Informationen zu ermitteln.
Dabei sollten die gefundenen Informationen stichhaltig, bisher unbekannt und für den
Benutzer hilfreich sein. Die Abbildung 1 zeigt den von Han [HK00] definierten Prozess des
KDD.
Startpunkt aller Auswertungen ist natürlich eine Datenbank, wobei auch Textdateien oder
ähnliches als Grundlage dienen können. Um diese Daten analysieren zu können, müssen sie
zunächst gegebenenfalls gereinigt werden und können anschließend nach eventuellen
Transformationen von den eigentlichen Data Mining Algorithmen ausgewertet werden.
Abschließend entstehen durch die Visualisierung der Ergebnisse aus den ursprünglichen
Daten Informationen.
2.1. Phasen des Knowledge Discovery in Databases
Im Folgenden wird der von Han definierte KDD Prozess detaillierter beschrieben. Dabei soll
jede der Phasen durch ein kleines Beispiel veranschaulicht werden. Um dies mit Hilfe eines
Knowledge Discovery in Databases
Kapitel 2
5
zusammenhängenden Anwendungsfalls zu tun, werden die Anforderungen der
Supermarktkette Euromarkt herangezogen. Im Rahmen einer Umfrage wurden zusätzlich zu
den ohnehin gespeicherten Umsatzdaten auch das Alter und das Jahreseinkommen der
Kunden abgefragt. Das Management möchte diese Daten nutzen, um Kundengruppen zu
identifizieren und Rückschlüsse auf das Kaufverhalten zu ermöglichen.
1. Data Cleaning: Dieser Schritt der Datenaufbereitung konzentriert sich auf die
Fehlerbeseitigung. Ausreißer innerhalb der Daten können das Analyseergebnis stark
beeinflussen und zu auffälligen, aber falschen Mustern führen. Aus diesem Grund wurden
einige Verfahren entwickelt, um fehlerhafte Werte zu identifizieren, zu korrigieren oder
endgültig aus der Datenmenge zu entfernen. Im Rahmen des Anwendungsfalls von Euromarkt
ist es beispielsweise wichtig, zunächst mögliche Tippfehler festzustellen. Wird die
Altersangabe eines Kunden in der Datenbank mit 288 angezeigt, ist es besonders deutlich,
dass hier ein Tippfehler vorliegen muss. In diesem Fall sollte der Datensatz gelöscht werden,
aufgrund der großen Menge von Daten ist dieser Verlust an Informationen akzeptabel.
2. Data Integration: Da heutzutage die Daten zunehmend in Verteilten Netzwerken
aufbewahrt werden und nicht mehr zentral gespeichert sind [BR99], ist es zunächst nötig, alle
relevanten Daten aus den verschiedenen Datenquellen zusammenzuführen. Brauchbare
Datenquellen können einerseits Datenbanken sein, andererseits müssen einige Daten aus
Dateien eingelesen und in ein Datenbankformat überführt werden. Das hierdurch entstehende
Data Warehouse bietet eine einheitliche und strukturierte Sichtweise auf die
unterschiedlichen Datenbestände.
Euromarkt muss in dieser Phase zunächst die Daten aus den einzelnen Filialen
zusammentragen. Dabei können Inkonsistenzen auftreten, zum Beispiel kann die
Kundenidentifikation in den unterschiedlichen Datenbanken jeweils eine andere Bezeichnung
haben. In Filiale X kann die Identifikation unter Kunden-ID gespeichert sein, während sie von
Filiale Y als Kunden-Nr dargestellt wird. Damit die Datenbestände integriert werden können,
müssen zunächst solche Inkonsistenzen behoben werden.
3. Data Selection: Nach der Integration der Datenbestände müssen die für die Fragestellung
relevanten Daten identifiziert werden. Nicht immer sind alle gespeicherten Informationen für
eine spezielle Analyse relevant, und daher sollte zunächst eine Auswahl der benötigten Daten
getroffen werden. Für die Supermarktkette kann bei der Identifizierung von Kundengruppen
Knowledge Discovery in Databases
Kapitel 2
6
zum Beispiel nur eine bestimmte Altersklasse oder ein bestimmtes Jahresgehalt von Interesse
sein. Die Einschränkung der Daten bezüglich der Zielsetzung ist daher von besonderer
Bedeutung.
Abbildung 1 - KDD Prozess nach [HK00]
4. Data Transformation: Wurden die relevanten Teildaten ausgewählt, müssen diese
zunächst transformiert werden. Die genaue Transformation der Daten hängt stark von der
nachfolgenden Data Mining Aufgabe ab. Je nach Analysemethode müssen die Daten speziell
aufbereitet werden. Für das Clustering wird von Han [HK00] beispielsweise die
Normalisierung der Daten empfohlen. Betrachtet man die Umfragedaten von Euromarkt, so
ist festzustellen, dass besonders die Attribute Alter und Jahresgehalt sehr unterschiedliche
Ausprägungen haben. Aufgrund dieser Tatsache würde bei einer Distanzberechnung ohne
Knowledge Discovery in Databases
Kapitel 2
7
Normalisierung das Alter kaum eine Rolle spielen, da der Wert des Gehaltes diesen um ein
Vielfaches übersteigt. Die Normalisierung der Daten auf ein einheitliches Intervall kann soll
nach Han [HK00] dieses Problem beheben und den gleichen Einfluss aller Attribute auf die
Gesamtdistanz sicherstellen.
5. Data Mining: Im Anschluss an die Aufbereitung der Daten erfolgt der wesentliche Schritt
zur Gewinnung von Informationen, das Data Mining. Dieser Schritt ermöglicht die
automatische Auswertung großer Datenmengen. Angewendet werden können dazu eine Reihe
unterschiedlicher Analysemethoden. Ein grober Überblick über die verschiedenen Verfahren
des Data Minings wird in Abschnitt 2.3 gegeben. Ein vertiefter Einstieg in die verschiedenen
Methoden des Clusterings ist in Kapitel drei dargestellt. Mit Hilfe des Clusterings kann
Euromarkt nun nach der abgeschlossenen Datenaufbreitung die Kundensegmentierung
durchführen. Dazu werden die Kunden nach Ähnlichkeit gruppiert und in Cluster eingeteilt.
Dabei wird vor allem das Kaufverhalten berücksichtigt, um später wichtige Informationen für
das Management zu liefern.
6. Pattern Evaluation: Die Interpretation der gefundenen Muster sowie deren Beurteilung
sind ein entscheidender Schritt der Analyse. Hier wird über die Interessantheit und Relevanz
von Mustern entschieden. Nur wenn die Ergebnisse erfolgreich validiert wurden, ist der
Prozess beendet, andernfalls können vorhergehende Phasen erneut durchlaufen werden. Für
die Auswertung von Euromarkt heißt dies, dass entschieden werden muss, ob gefundene
Kundengruppen von Interesse sind. Ein wichtiges Kriterium könnte dabei die Größe des
Clusters sein. Sind nur wenige Personen einer Kundengruppe zugeordnet, so kann diese
Gruppe nur wenige Informationen liefern und ist daher uninteressant. Bei sehr großen
Kundengruppen könnte es hingegen vorteilhaft sein, diese weiter zu unterteilen und dadurch
detailliertere Beschreibungen zu erlangen.
7. Knowledge Presentation: Die Darstellung der Ergebnisse schließt den KDD Prozess
endgültig ab. Die Visualisierungstechniken stehen hierbei im Vordergrund. Der Nutzer soll
einen schnellen und umfassenden Überblick über die Ergebnisse geliefert bekommen. Auch
die Kundensegmentierung kann durch ausgewählte Visualisierungstechniken dargestellt
werden. Zum Beispiel können Zusammenhänge einzelner Attribute als Punktdiagramm
abgebildet werden. Visualisierungstechniken stammen häufig aus dem Bereich der Statistik
und werden für die abschließenden Ergebnisse des KDD Prozesses verwendet.
Knowledge Discovery in Databases
Kapitel 2
8
2.2. Normalisierung der Daten
Die Normalisierung der Daten wird von Han [HK00] vor allem dann empfohlen, wenn die
Distanz zweier Objekte berechnet werden muss. Unter einem Objekt wird dabei ein Datensatz
verstanden, dieser kann zum Beispiel ein spezielles Produkt darstellen. Die Distanz zwischen
zwei solchen Objekten beschreibt nun deren Ähnlichkeit. Betrachtet man die Objekte als
Punkte innerhalb eines n-dimensionalen Raumes, so kann die Ähnlichkeit zweier Punkte
durch die räumliche Distanz dargestellt werden. Eine Distanz von Null bedeutet, dass die
Objekte identisch sind, also alle Eigenschaften dieselbe Ausprägung haben.
Mit Hilfe der Normalisierung der Daten auf einen festgelegten Wertebereich soll der Einfluss
der verschiedenen Attribute auf die Distanz den gleichen Stellenwert erhalten. Zur
Normalisierung der Daten haben sich in der Literatur [Kan03] drei unterschiedliche Verfahren
durchgesetzt. Dabei handelt es sich um die Dezimalmethode, die MinMax sowie die Z
Score Methode.
Die Dezimalmethode ist von den drei genannten das einfachste Verfahren. Hierbei wird
lediglich die Position des Kommas derart verändert, dass alle Werte nach der Berechnung
in das Intervall (0,1) fallen. Um wie viele Positionen das Komma dabei verschoben wird,
hängt vom Maximalwert des Attributes ab.
Dezimal Methode:
j
v
v
10
'
=
v:
Ursprungswert
v':
normalisierter
Wert
j wird so gewählt, dass Max(|v'|) < 1
Beispiel: Betrachtet man den Preis eines Produktes, so wird bei einem Maximalwert von
9240 der Wert von 350 auf 0,035 abgebildet.
4
=
j
und
035
,
0
10
350
10
'
4
=
=
=
j
v
v
.
Die Min-Max Methode bildet die Ursprungswerte ebenfalls auf das Intervall (0,1) ab.
Der ehemalige Minimalwert wird dabei zu null und der Maximalwert zu eins, alle Werte
dazwischen werden entsprechend auf Werte zwischen null und eins abgebildet.
Knowledge Discovery in Databases
Kapitel 2
9
Min Max Methode:
min
max
min
'
-
-
=
v
v
min: Minimum
max: Maximum
Beispiel: Bei der Min-Max Methode wird der Preis von 350, bei einer Spanne der Werte
von 77 bis 9240, auf 0,0298 abgebildet.
0298
,
0
9163
273
77
9240
77
350
min
max
min
'
=
-
-
=
-
-
=
v
v
Die Z-Score Methode bildet die Werte nicht auf ein geschlossenes Intervall ab, sondern
die Grenzen sind nach oben und unten offen. Der Mittelwert der ursprünglichen
Verteilung wird auf Null abgebildet. Die Varianz beträgt nach der Normalisierung jeweils
eins. Die Z-Score Methode ist vorteilhaft, wenn die Minimal- und Maximalwerte nicht
bekannt sind, oder das Ergebnis durch den Einfluss von Ausreißern beeinflusst werden
könnte.
Z-Score Methode:
A
A
v
v
-
=
'
A : Mittelwert
A
: Standardabweichung
Beispiel: Bei der Z-Score Methode muss zunächst die Standardabweichung und der
Mittelwert berechnet werden. Für das Beispiel betragen diese Werte 732 und 280. Für
den Wert von 350 ergibt sich daher ein neuer Wert von 0,0956.
0956
,
0
732
70
732
280
350
'
=
-
=
-
=
A
A
v
v
Aufgrund der unterschiedlichen statistischen Verteilung, die die Attribute haben können, ist
es nach der Normalisierung noch nötig, den Mittelwert [HTF03] der Attribute auf einen
einheitlichen Wert zu standardisieren. Hierzu wird jeder Einzelwert durch den Mittelwert des
Knowledge Discovery in Databases
Kapitel 2
10
Attributes dividiert, so ergibt sich ein standardisierter Mittelwert von eins. Dadurch ist das
Gleichgewicht der unterschiedlichen Attribute bei weitergehenden Analysen sichergestellt.
Auf die Problematik der Normalisierung und der Standardisierung wird im Kapitel sechs auf
Seite 77 noch einmal detaillierter eingegangen.
Nach der erfolgreichen Transformation der Daten kann die eigentliche Gewinnung von
Informationen beginnen. Dieser Abschnitt des KDD ist die Phase des Data Minings. Im
folgenden Abschnitt wird daher näher auf die einzelnen Aufgaben des Data Minings
eingegangen.
2.3. Aufgaben des Data Minings
Das Data Mining stellt eine Phase des KDD Prozesses dar. Eine weit verbreitete Definition
wurde von Hand et al. [HMS01] aufgestellt: "Data mining is the analysis of (often large)
observational data sets to find unsuspected relationships and to summarize the data in novel
ways that are both understandable and useful to the data owner." Unter Data Mining versteht
man demnach die Analyse und Auswertung von Beobachtungsdaten. Das heißt, es handelt
sich nicht um speziell für die Analyse gesammelte Daten, sondern es werden bestehende
Datenmengen ausgewertet, die eventuell für ganz andere Zwecke gesammelt wurden. Daraus
resultieren besondere Anforderungen an die Algorithmen, da sie besonders anpassungsfähig
und flexibel sein müssen. In der Regel handelt es sich bei der Analyse um eine sehr große
Datenmenge, die ist aber nicht zwingend erforderlich. Ziel der Auswertung ist, bisher
unbekannte Beziehungen innerhalb der Daten zu finden, also die Struktur der Daten besser zu
verstehen. Wichtig ist dabei, dass die gefundenen Strukturen tatsächlich neue Informationen
darstellen und verständlich für den Benutzer sind.
Oftmals wird der Begriff Data Mining mit dem KDD Prozess gleichgesetzt. Diese Definition
ist jedoch nicht richtig, da es sich beim Data Mining lediglich um einen Teilschritt des
Knowledge Discovery Prozesses handelt, wie zu Beginn des zweiten Kapitels auf Seite 7
definiert wurde. Data Mining ist zwar der entscheidende Schritt bei der Wissensextration,
macht aber lediglich 15% 20% [BA96] des gesamten Rechenaufwands aus. Der Großteil der
Arbeit entfällt auf Vor- und Nachbereitungsaufgaben.
Der Bereich des Data Minings steht für eine Vielzahl von unterschiedlichen Methoden, die es
ermöglichen, bisher unbekannte aber potentiell nützliche Informationen aus einer Sammlung
von Daten zu extrahieren. Die Aufgaben des Data Minings können nach Hand [HMS01] in
fünf unterschiedliche Bereiche gegliedert werden. Jeder der fünf Bereiche hat eine
Knowledge Discovery in Databases
Kapitel 2
11
unterschiedliche Zielsetzung und verwendet eigene Methoden zur Analyse und Auswertung
der Daten.
Zur näheren Beschreibung dieser Aufgaben ist eine Differenzierung von Modellen und
Mustern
erforderlich. Modelle beschreiben die gesamte Datenmenge und machen es möglich,
Aussagen über einzelne Punkte dieser Datenmenge zu treffen. Häufig sollen mit Hilfe von
Modellen Werte vorhergesagt werden. Man kann mit Modellen also neue Werte zuordnen und
Prognosen erstellen. Muster hingegen beschreiben immer nur eine bestimmte Region der
Datenmenge. Mit Hilfe von Mustern lassen sich keine Werte vorhersagen oder berechnen.
Man kann allerdings Zusammenhänge einzelner Variablen erkennen und beschreiben. Die
unterschiedlichen Aufgaben der Data Mining bestehen nun aus dem Erstellen von Modellen,
beziehungsweise aus dem Erkennen von Mustern.
Die erste Aufgabe ist die Explorative Datenanalyse, die sich hauptsächlich mit
Visualisierungstechniken beschäftigt. Zweitens die Deskriptive Datenanalyse, die Daten
beschreiben und zusammenfassen soll. Die dritte Aufgabe ist das ,predictive modeling', mit
Hilfe dieser Methoden werden Modelle erzeugt, die zur Vorhersage von Werten
herangezogen werden können. Den vierten Aufgabebereich bezeichnet man als ,pattern
discovery'. Hierunter werden Verfahren zur Identifikation von Mustern und dem Aufstellen
von Regeln verstanden, die diese Muster beschreiben. Letzter Aufgabenbereich des Data
Minings ist das ,retrieval by content'. Verfahren dieser letzten Gruppe können vom Nutzer
definierte Muster innerhalb großer Datenbanken suchen. Ein Anwendungsgebiet ist
beispielsweise die Dokumentensuche mit Hilfe von Suchmaschinen. Diese fünf
Aufgabenbereiche sind in Abbildung 2 dargestellt und werden in den folgenden Abschnitten
kurz beschrieben.
Abbildung 2 - Aufgaben des Data Minings
Knowledge Discovery in Databases
Kapitel 2
12
2.3.1. Explorative Datenanalyse
Die explorative Datenanalyse (EDA) ist ein in der Praxis häufig verwendetes Mittel. Nach
Abschluss der Datenaufbereitung sollen diese mit Hilfe der EDA Techniken die Daten
dargestellt werden, häufig werden diese Techniken jedoch auch nach Abschluss anderer Data
Mining Aufgaben eingesetzt, um die Ergebnisse auszuwerten. Eine genaue Zielvorstellung
steht dabei in der Regel noch nicht fest, und so soll durch eine möglichst gute Visualisierung
der Daten ein umfassender Überblick gewährleistet werden. Überraschungen sind nach Tukey
[Tuk77] dabei durchaus erwünscht. Denn gerade Ergebnisse, die nicht erwartet wurden, sind
besonders wertvoll. Mit Hilfe dieser neuen Erkenntnisse nimmt das Verständnis über die
Daten zu, und so kann beispielsweise die Zukunftsplanung optimiert werden. Im
Zusammenhang mit EDA Techniken wird häufig auch von Dimensionen gesprochen. Dieser
Begriff wird in einer Vielzahl von Zusammenhängen gebraucht. In diesem Fall versteht man
unter einer Dimension eine bestimmte Eigenschaft eines Objektes. Solche Eigenschaften
werden als Attribut bezeichnet und können zum Beispiel den Preis eines Objektes
beschreiben. Die Darstellung der Daten bei nur zwei Dimensionen ist noch recht
unkompliziert, da dies mittels eines xy-Diagramms geschehen kann. Aufwendiger wird es
jedoch, wenn mehr als zwei Dimensionen betrachtet werden. Dann sollten Techniken
angewendet werden, die in der Lage sind, diese Dimensionen auf eine niedrigere Anzahl
abzubilden. Typische EDA Techniken sind Diagramme verschiedenster Art, wie
Streuungsdiagramme, Boxplots oder ähnliches. Im Allgemeinen stammen die EDA
Techniken aus dem Bereich der Statistik und wurden für die Data Mining Aufgaben
übernommen.
2.3.2. Deskriptive Datenanalyse
Die deskriptive Datenanalyse verfolgt das Ziel, die Daten zu beschreiben und ein passendes
Modell zu erstellen. Hierbei liegt das Augenmerk auf den wichtigsten Eigenschaften der
Daten. Es soll mit Hilfe der deskriptiven Datenanalyse eine Zusammenfassung der Daten
erstellt werden. Dabei kommt es durch die Verdichtung zwar zu gewissen Verlusten von
Details, dem gegenüber steht aber im Idealfall ein Gewinn an Aussagekraft. Zu diesen
Verfahren zählen unter anderem: density estimation, partitioning und dependency modeling.
Unter density estimation versteht man die grobe Abschätzung einer Verteilung der Daten. Die
Fragestellung lautet hier, ob aus Messungen und bekannten Daten eine Aussage über die
Wahrscheinlichkeitsverteilung getroffen werden kann.
Knowledge Discovery in Databases
Kapitel 2
13
Die Partitionierung oder auch Clustering ist die Unterteilung von Daten in abgrenzbare
Cluster. Die Daten sollen hier nicht nach einem vorgegebenen Zweck unterteilt werden,
sondern es soll die Struktur der Daten möglichst stark berücksichtigt werden. Ziel ist es, die
Daten nicht in vordefinierte Klassen zu unterteilen sondern zunächst solche natürlichen
Klassen zu finden. Auf diesen Bereich der deskriptiven Datenanalyse wird in der Arbeit noch
detaillierter eingegangen.
Die dritte Anwendung, das so genannte dependency modeling oder Abhängigkeitsanalyse,
beschreibt die Beziehungen unterschiedlicher Variablen, besser gesagt deren Abhängigkeiten.
Mit Hilfe dieser Information versucht man Kausalzusammenhänge zu erkennen und somit
Rückschlüsse auf die Gründe für die Abhängigkeiten zu gewinnen.
2.3.3. Predictive Modeling
Im Gegensatz zum descriptive modeling soll es das predictive modeling ermöglichen,
Vorhersagen über einzelne Variablen zu machen. Die Daten sollen also nicht mehr nur
beschrieben werden, sondern es sollen auf Grundlage von bekannten Variablen Modelle
erstellt werden, die es ermöglichen, bestimmte unbekannte Werte zu berechnen. Dabei lassen
sich zwei verschiedene Techniken unterscheiden. Hierbei handelt es sich um die
Klassifikation sowie die Regression der Daten.
Der wesentliche Unterschied dieser beiden Techniken liegt im Wertebereich der zu
bestimmenden Variablen. Bei der Klassifikation hat die zu bestimmende Variable einen
nominalen Wert, also einen diskreten Wertebereich. Ein Beispiel wäre die Entscheidung der
Kreditwürdigkeit eines Kunden. Der Wertebereich entspräche dann den Werten:
,,kreditwürdig" und ,,nicht kreditwürdig". Bei der Regressionsanalyse hingegen wird eine
reellwertige Variable gesucht. Durch eine Regressionsanalyse könnte man einen
Zusammenhang zum Beispiel zwischen dem Umfang und Alter bestimmter Baumsorten
ermitteln. Durch Messen des Umfangs könnte man dann auf das Alter des Baums schließen.
2.3.4. Pattern Discovery
Bei dieser Aufgabe des Data Minings geht es nicht um die Erstellung von Modellen wie bei
den vorherigen drei Aufgabentypen, sondern um die Identifikation von Mustern und
Erzeugung von Regeln. Die zwei bekanntesten Techniken sind das Aufstellen von
Assoziationsregeln sowie das Erkennen von Ausreißern.
Assoziationsregeln beschreiben Zusammenhänge innerhalb der Datenmenge. Die bekannteste
Form einer solchen Analyse ist wohl die Warenkorbanalyse. Dabei sollen Regeln gefunden
Knowledge Discovery in Databases
Kapitel 2
14
werden, die definieren, welche Produkte häufig gemeinsam gekauft werden. Kauft ein Kunde
beispielsweise einen Computer, so kauft er wahrscheinlich auch einen Monitor. Derartige
Regeln kann man entwickeln, indem man vorhandene Verkaufsdaten auswertet. Solche
Verkaufsdaten bestehen häufig aus einfachen Kassenzetteln, die digital gespeichert wurden.
Die Datensätze enthalten die Information, welche Produkte zusammen gekauft wurden, und
durch die Auswertung solcher Daten können Rückschlüsse über das Kaufverhalten der
Kunden gemacht werden. Der Apriori [AS94] Algorithmus ist das am meisten verbreitete
Verfahren für derartige Analysen und wurde 1994 von Agrawal veröffentlicht.
2.3.5. Retrieval by Content
Algorithmen dieses Typs haben die Aufgabe bestimmte, Muster zu erkennen. In diesem Fall
geht es aber um die Suche spezieller Muster. Diese werden dabei zu Beginn vom Nutzer
eingegeben, der Algorithmus versucht nun identische Muster zu finden. Anwendungsgebiete
sind für derartige Verfahren vor allem die Textsuche, aber auch neuere Verfahren wie die
Bildersuche sind damit gemeint.
Bei der Textsuche gibt der Benutzer einige Suchbegriffe oder Stichwörter ein, und der
Algorithmus versucht dazu passende Dokumente zu finden. Besonders bekannt sind auf
diesem Gebiet natürlich die Suchmaschinen im Internet, die anhand von Stichwörtern
relevante Webseiten aber auch Dokumente oder Bilder suchen.
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
15
3. Deskriptive Analyse im Data Mining:
Clustering
Dieses Kapitel soll einen Überblick über die aktuellen Verfahren des Clusterings verschaffen.
Dabei werden die verschiedenen Algorithmentypen vorgestellt und einzelne ausgewählte
Verfahren detaillierter beschrieben. Zunächst wird aber die Zielsetzung des Clusterings näher
erläutert.
Unter Clustering versteht man ,,die Analyse einer heterogenen Gesamtheit von Objekten mit
dem Ziel, homogene Teilmengen von Objekten aus der Objektgesamtheit zu identifizieren."
[Bac93]. Es geht also darum, eine gute Einteilung der Objekte in verschiedene Gruppen zu
finden. Die Abbildung 3 zeigt ein solches zweidimensionales Beispiel. Die Einteilung bei nur
zwei Dimensionen ist auch graphisch gut nachzuvollziehen. Die Objekte innerhalb einer
Gruppe sollen dabei möglichst homogen sein, während sie zu Objekten aus anderen Gruppen
möglichst heterogen sein sollen. Die Ähnlichkeitsberechnung erfolgt dabei in der Regel über
eine Distanzfunktion. Die genaue Berechnung von Distanzen wird im Abschnitt 3.1 näher
erläutert. Zunächst genügt uns die Definition, dass die Distanz zwischen zwei Objekten den
Grad der Ähnlichkeit dieser Objekte ausdrückt.
Abbildung 3 - Clustering Beispiel
In der Literatur werden die Begriffe Clustering und Klassifizierung häufig synonym
verwendet. Hier ist jedoch eine klare Abgrenzung zu machen. Bei der Klassifizierung sind die
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
16
Gruppen, in die die Objekte unterteilt werden, vorab bereits definiert und festgelegt. Die
Klassifizierung berechnet lediglich die Zuordnung der Objekte zu diesen Gruppen. Zum
Beispiel die Einteilung von Hotels nach Qualität in die Gruppen 1-Sterne Hotels, 2-Sterne
Hotels usw. Beim Clustering hingegen müssen die Gruppen zunächst ermittelt werden. Dabei
sollen möglichst natürliche Grenzen gefunden werden. Die Identifizierung dieser Grenzen ist
also die wesentliche Aufgabe des Clusterings. Ein weiterer verwendeter Begriff ist die
Segmentierung. Hierbei handelt es sich tatsächlich um einen anderen Ausdruck für das
Clustering.
Für die Berechnung von Clustern sind im Laufe der Zeit sehr viele unterschiedliche Verfahren
entwickelt worden. Jedes Verfahren hat dabei eine bestimmte Zielsetzung und ist nur bei
speziellen Voraussetzungen einsetzbar. Die Abbildung 4 stellt die unterschiedlichen Typen
von Verfahren dar. Dabei handelt es sich um die partitionierenden Algorithmen, hierarchische
und dichtebasierte Methoden sowie gitterbasierte und modellbasierte Methoden. Die genauen
Stärken und Schwächen der Verfahren werden in Abschnitt 3.2 vorgestellt.
Abbildung 4 Einteilung der Clusteralgorithmen nach Hand [HB02]
Eine wichtige Grundlage für die partitionierenden, die hierarchischen sowie die
dichtebasierten Algorithmen ist die Distanzberechnung. Im folgenden Abschnitt wird daher
zunächst auf die Ähnlichkeitsbestimmung mit Hilfe einer Distanzfunktion eingegangen.
3.1. Distanzberechnung beim Clustering
Mit Hilfe einer definierten Distanzfunktion kann die Ähnlichkeit von Objekten bestimmt
werden. Die Wahl der Distanzfunktion hat dementsprechend einen hohen Einfluss auf das
Ergebnis des Verfahrens. Für quantitative Variablen ist die Berechnung von Distanzen noch
relativ unkompliziert, problematischer wird es jedoch bei den qualitativen Attributen. Eine
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
17
Differenzierung der verschiedenen Variablentypen ist daher auch bei der Distanzberechnung
von Bedeutung.
Die folgenden Abschnitte stellen das unterschiedliche Vorgehen bei den einzelnen
Variablentypen dar. Dabei werden die intervallbasierten, die binären, die nominalen sowie die
ordinalen Variablen unterschieden. Diese Typen lassen sich in zwei Hauptgruppen einteilen.
Erstens die quantitativen Variablen, die stetige Messwerte aufweisen und prinzipiell beliebig
genau gemessen werden können. Beispiele hierfür sind die Körpergröße oder das Gewicht.
Die zweite Gruppe stellt die qualitativen Variablen dar. Diese können nur diskrete Werte
annehmen, die zuvor definiert wurden. Hier kann als Beispiel die Schulnotenskala angegeben
werden.
Zur Gruppe der quantitativen Variablen gehören die intervallskalierten, zu den qualitativen
gehören die nominalen, die binären sowie die ordinalen Variablen. Die Tabelle 1 stellt eine
Übersicht der Variablentypen dar, die im Folgenden detaillierter beschrieben werden.
Tabelle 1 - Variablentypen
Variablentyp
Wertebereich
Bedeutung
nominal qualitativ
diskret
Zustände
(z.B. Haarfarbe: blond, braun...)
binär
qualitativ
diskret [0,1]
Tritt Merkmal auf: Ja oder Nein?
ordinal qualitativ
stetig
Rangordnung (z.B. Schulnoten)
intervallskaliert quantitativ stetig
Differenzen haben gleiche Bedeutung
Wenn wir von nominalen Variablen sprechen geht es in der Regel um qualitative Merkmale.
Die Werte, die die Variable annehmen kann, sind also nicht numerisch, sondern das Objekt
kann nur bestimmte Zustände annehmen. Ist die Anzahl der Zustände auf zwei beschränkt,
spricht man auch von binären Variablen. Bei diesem Spezialfall stellt sich meistens die
Frage, ob eine bestimmte Eigenschaft vorhanden ist oder nicht. Sind mehr als zwei Zustände
denkbar, liegt eine mehrklassige Einteilung vor. Alle möglichen Kategorien müssen dabei
genau definiert sein. Die einzige bei nominalen Variablen zugelassene Rechenoperation ist
das Zählen. Die Auswertungsmöglichkeiten sind also sehr eingeschränkt, die Berechnung
eines Mittelwertes ist beispielsweise sinnlos, da die Werte alle gleichgestellt sind und keine
Hierarchie der Werte existiert. Für das angeführte Beispiel der Haarfarbe lässt sich demnach
kein Mittelwert berechnen, lediglich durch Zählen der Zustände können Aussagen über die
Verteilung gemacht werden.
Im Gegensatz zu Nominalen Variablen sind ordinale Variablen etwas ,informativer'. Zwar
handelt es sich dabei auch um qualitative Werte, aber diesen Werten kann eine gewisse
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
18
Rangfolge zugeordnet werden. Zwischen verschiedenen Messwerten kann eine Beziehung
hergestellt werden, man kann sie also bezüglich ihrer Größe sortieren. Für Ordinale Variablen
sind zusätzlich noch die Operationen kleiner, größer oder gleich zugelassen. Eine häufig
verwendete Ordinalskala ist das Schulnotensystem.
Abschließend gilt es noch die Intervallskala einzuführen. Hierbei handelt es sich um eine
quantitative Skala. Erst diese Skala erlaubt es, Differenzen zu bilden und diese auch sinnvoll
interpretieren zu können. Intervallskalen sind z.B. die Temperaturskala oder auch die
Gewichtsskala.
Für die Distanzfunktion gelten dabei die folgenden Eigenschaften:
)
,
( y
x
d
bezeichnet die Distanz zwischen den Werten x und y
0
)
,
(
y
x
d
Distanz ist niemals negativ
0
)
,
(
=
y
x
d
wenn x = y
)
,
(
)
,
(
x
y
d
y
x
d
=
symmetrische Funktion
)
,
(
)
,
(
)
,
(
y
z
d
z
x
d
z
x
d
+
3.1.1. Distanzberechnung bei Intervallbasierten Variablen
Dieser Abschnitt befasst sich mit der Fragestellung, wie die Berechnung der Distanz zwischen
zwei Objekten mit jeweils intervallbasierten Variablen durchgeführt werden kann. Die am
häufigsten verwendete Distanzfunktion ist die Euklidische Distanz. Diese berechnet sich
über die Quadratwurzel der quadratischen Differenzen der jeweiligen Variablen. Die Formel
ist eine Erweiterung des Satz des Pythagoras und die Distanz entspricht somit der ,Luftlinie'
also der direkten Verbindung zwischen den Objekten.
Eine weitere verbreitete Distanzfunktion ist die Manhattan Distanz. Diese beschreibt die
Distanz zwischen zwei Objekten durch die Länge des Weges, wenn man sich auf den
Koordinatenachsen bewegt. Daher wird sie häufig auch City-Block Distanz genannt.
Euklidische Distanzfunktion:
²
|
|
...
²
|
|
²
|
|
)
,
(
)
(
2
)
2
(
1
)
1
(
jp
ip
j
i
j
i
x
x
x
x
x
x
j
i
d
-
+
+
-
+
-
=
Manhattan Distanz:
|
|
...
|
|
|
|
)
,
(
)
(
2
)
2
(
1
)
1
(
jp
ip
j
i
j
i
x
x
x
x
x
x
j
i
d
-
+
+
-
+
-
=
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
19
Die Abbildung 5 stellt die beiden unterschiedlichen Verfahren noch einmal graphisch dar. Die
Manhattan Distanz verzichtet auf die Quadrierung der Differenzen und wird dadurch weniger
stark von Ausreißern beeinflusst.
Abbildung 5 - Euklidische und Manhattan Distanz
Beide Varianten der Distanzberechnung können auf eine gemeinsame Formel verallgemeinert
werden. Diese Funktion wird als Minkowski Distanz bezeichnet. Für
1
=
q
erhält man die
Ergebnisse der Manhattan Distanz, und bei
2
=
q
bestimmt man die Euklidische Distanz. Für
jedes dieser Verfahren ist es erlaubt, eine Gewichtung der verschiedenen Variablen zu
definieren. Diese Gewichtung geht direkt als Faktor in die Formel mit ein und macht es
möglich, einzelne Attribute stärker zu betonen und den Einfluss dieser Attribute auf die
Gesamtdistanz zu erhöhen.
Minkowski Distanz ohne Gewichtung:
(
)
q
q
jp
ip
q
j
i
q
j
i
x
x
x
x
x
x
j
i
d
/
1
)
(
2
)
2
(
1
)
1
(
|
|
...
|
|
|
|
)
,
(
-
+
+
-
+
-
=
Minkowski Distanz mit Gewichtung:
(
)
q
q
jp
ip
p
q
j
i
q
j
i
x
x
w
x
x
w
x
x
w
j
i
d
/
1
)
(
2
)
2
(
2
1
)
1
(
1
|
|
...
|
|
|
|
)
,
(
-
+
+
-
+
-
=
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
20
3.1.2. Distanzberechnung bei Binären Variablen
Binäre Variablen lassen sich in zwei unterschiedliche Typen einteilen. Der erste Typ sind die
symmetrischen binären Variablen
. Hier sind die beiden Zustände, die angenommen werden
können, gleich gewichtet. Keiner der beiden Zustände ist also dem anderen vorzuziehen. Ein
Beispiel für eine solche symmetrische Variable ist das Geschlecht. Der zweite Typ sind die
asymmetrischen binären Variablen
. Bei diesen sind die Zustände unterschiedlich
gewichtet, das heißt, einer der beiden Zustände wird bevorzugt. Dies ist zum Beispiel bei
Krankheitstests der Fall, hier würde natürlich die negative Variable also das Fehlen der
Krankheit vorgezogen.
Für beide Typen lässt sich zunächst eine Häufigkeitsmatrix erstellen. Eine solche Matrix ist in
Tabelle 2 dargestellt. Die Zustände werden dabei mit null und eins beschrieben. Mit eins kann
man das Auftreten einer Eigenschaft, also den positiven Fall darstellen und mit einer Null den
negativen Fall. Dargestellt wird mit der Häufigkeitstabelle die Anzahl der Attribute, bei denen
die beiden Objekte einen unterschiedlichen oder denselben Zustand angenommen haben. Bei
der anschließenden Berechnung der Distanz muss dann zwischen den beiden Typen
unterschieden werden.
Tabelle 2 - Häufigkeitsmatrix für binäre Variablen
Objekt j
1
0
Summe
1 q
r
q+r
Objekt i
0 s
t
s+t
Summe
q+s
r+t
p
Bei symmetrischen Variablen wird der simple matching Koeffizient angewendet. Dieser
beschreibt den Quotienten aus der Anzahl aller Attribute, bei denen die Objekte einen
unterschiedlichen Zustand haben, dividiert durch die Anzahl aller Attribute. Bei
asymmetrischen Variablen wird der Fall, dass beide Variablen einen negativen Wert
annehmen, also den bevorzugten Zustand haben, ignoriert. Diese Anzahl fließt daher nicht mit
in die Berechnung ein. Die zu verwendende Formel ist der Jaccard Koeffizient.
Simple matching Koeffizient:
t
s
r
q
s
r
j
i
d
+
+
+
+
=
)
,
(
Jaccard Koeffizient:
s
r
q
s
r
j
i
d
+
+
+
=
)
,
(
Deskriptive Analyse im Data Mining: Clustering
Kapitel 3
21
3.1.3. Distanzberechnung bei Nominalen Variablen
Nominale Variablen haben mehr als nur zwei Zustände, zum Beispiel die Farbe eines Autos,
hier können die Zustände rot, grün, schwarz usw. angenommen werden. Die Distanz d(i,j),
zwischen zwei Objekten i und j mit derartigen Variablen lässt sich mit Hilfe des ,simple
matching approach' berechnen. Entscheidend ist dabei die Anzahl der Übereinstimmungen,
also die Zahl aller Attribute, bei denen beide Objekte denselben Zustand haben. Dieser Wert
m wird in Relation mit der Gesamtzahl p aller Attribute gesetzt.
Simple matching approach:
p
m
p
j
i
d
-
=
)
,
(
p: Gesamtanzahl an Variablen
m: Anzahl an Übereinstimmungen
3.1.4. Distanzberechnung bei Ordinalen Variablen
Ordinale Variablen sind zwar ähnlich wie nominale, aber aufgrund der vorhandenen
Rangfolge ist die Distanzberechnung sehr unterschiedlich. Zunächst müssen die Variablen auf
eine intervallbasierte Skala transformiert werden, anschließend kann mit Hilfe der in
Abschnitt 3.1.1 beschriebenen Distanzfunktionen die Ähnlichkeit bestimmt werden. Die
Transformation von ordinalen Variablen in eine intervallbasierte Skala erfolgt über den Rang
der Variablen, also über die Position innerhalb der Rangfolge. Der erste Wert der Rangfolge
wird dabei immer auf null abgebildet, der letzte Wert immer auf eins. Alle dazwischen
liegenden Werte werden linear auf das Intervall von null bis eins verteilt.
1
1
-
-
=
f
if
if
M
r
z
if
z
ist der intervallbasierte Wert der Variable f des Objekts i.
if
r
ist der Rang der Variable.
f
M
bezeichnet die Anzahl der Zustände der Variablen f.
3.1.5. Distanzberechnung bei gemischt skalierten Daten
In den vorigen Abschnitten wurden Formeln eingeführt, die es ermöglichen, Distanzen
zwischen Objekten zu berechnen, bei denen jeweils nur ein Variablentyp vorhanden ist.
Häufig sind jedoch mehrere verschiedene Variablentypen relevant. Die Objekte bestehen also
meistens nicht nur aus einem Typ von Attributen, sondern es sind unterschiedliche
Variablentypen vorhanden. Damit auch für solche Objekte eine Distanz berechnet werden
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2005
- ISBN (eBook)
- 9783832491864
- ISBN (Paperback)
- 9783838691862
- DOI
- 10.3239/9783832491864
- Dateigröße
- 2.8 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Technische Universität Carolo-Wilhelmina zu Braunschweig – Fakultät für Wirtschafts- und Sozialwissenschaften, Wirtschaftswissenschaften
- Erscheinungsdatum
- 2005 (Dezember)
- Note
- 1,0
- Schlagworte
- clustering ähnlichkeitsanalyse produktrecherche e-commerce online shopping
