Data Mining mit Standardwerkzeugen

Inhaltsverzeichnis

1 Data Mining - Neuer Ansatz zur Datenanalyse
1.1 Gerichtete Datenanalyse
1.1.1 Query und Reporting
1.1.2 OLAP
1.1.3 Statistische Analyse
1.2 Ungerichtete Datenanalyse
1.2.1 Deduktion versus Induktion
1.2.2 Überwachtes Lernen
1.2.3 Unüberwachtes Lernen

2 Erkenntnisgewinnung aus Datenbanken
2.1 Konzept
2.2 Verwandte Forschungsgebiete
2.3 Aufgaben
2.3.1 Klassifizierung
2.3.1.1 Ziel
2.3.1.2 Techniken
2.3.2 Segmentierung
2.3.2.1 Ziel
2.3.2.2 Techniken
2.3.3 Assoziierung
2.3.3.1 Ziel
2.3.3.2 Techniken
2.3.4 Weitere Aufgaben
2.4 Prozeß
2.4.1 Datenvorbereitung
2.4.1.1 Selektion
2.4.1.2 Reinigung
2.4.1.3 Transformation
2.4.1.4 Data Warehouse als Datenlieferant
2.4.2 Analyse
2.4.3 Ergebnispräsentation und -interpretation

3 Techniken
3.1 Clusteranalyse
3.1.1 Quantifizierung von Ähnlichkeit
3.1.2 Prinzipien der Clusterbildung
3.1.2.1 Nächste-Nachbarn-Verfahren
3.1.2.2 Mittelwertmodelle
3.1.2.3 Repräsentantenverfahren
3.1.2.4 Konstruktion von Clusterzentren
3.1.3 Partitionierende Gruppierungsverfahren
3.1.4 Hierarchische Gruppierungsverfahren
3.1.4.1 Agglomerative Vorgehensweise
3.1.4.2 Divisive Verfahren
3.2 Entscheidungsbäume
3.2.1 Bestandteile und Funktionsweise
3.2.2 Aufbau eines Entscheidungsbaumes
3.2.3 Algorithmen
3.2.3.1 CART
3.2.3.2 ID3 und C4.5
3.2.3.3 CHAID
3.3 Neuronale Netze
3.3.1 Bestandteile und Funktionsweise
3.3.2 Netztopologien
3.3.2.1 Vorwärtsgekoppelte Netze
3.3.2.2 Rekurrente Netze
3.3.3 Netzmodelle und Netztraining
3.3.3.1 Backpropagation
3.3.3.2 Selbstorganisierende Karten (Kohonen-Netze)
3.4 Assoziationsregeln und Sequenzmuster
3.4.1 Assoziationsregeln
3.4.1.1 Assoziationsproblem
3.4.1.2 Aufbau der Algorithmen
3.4.2 Sequenzmuster

4 Betriebswirtschaftliche Anwendungen
4.1 Produktionsplanung und -steuerung
4.1.1 Prozeß- und Qualitätskontrolle
4.1.2 Anlagenüberwachung und -instandhaltung
4.1.3 Auslastungssteuerung
4.1.4 Stochastische Bedarfsermittlung / Absatzprognose
4.2 Vertrieb und Marketing
4.2.1 Preisfindung
4.2.2 Database Marketing
4.2.2.1 Marktsegmentierung und Ranking
4.2.2.2 Individualisierte Kundenansprache
4.2.3 Warenkorbanalyse
4.2.4 Kundenbindung
4.3 Risikomanagement
4.3.1 Bonitätsprüfung
4.3.2 Betrugsentdeckung

5 Vergleich ausgewählter Data Mining-Produkte
5.1 Marktübersicht
5.1.1 Produktentwicklung
5.1.2 Marktsegmente
5.1.2.1 Unternehmensweite Lösungen
5.1.2.2 Client/Server-Lösungen
5.1.2.3 Desktop Produkte
5.2 Testumgebung
5.2.1 Hardware
5.2.2 Daten
5.2.3 Produktauswahl
5.3 Produktvergleich Desktop Data Mining
5.3.1 Allgemeine Produktmerkmale
5.3.1.1 Dokumentation
5.3.1.2 Zielgruppe
5.3.2 Datenvorbereitung
5.3.2.1 Unterstützte Datenquellen vs. Einfachheit der Datenanbindung
5.3.2.2 Selektions- und Transformationsmöglichkeiten vs. Benutzerunterstützung
5.3.2.3 Möglichkeiten zur Stichprobenziehung vs. Automatisierung
5.3.2.4 Möglichkeiten zur Datenreinigung vs. Automatisierung
5.3.2.5 Unterstützung verschiedener Datentypen vs. Transformationsaufwand
5.3.2.6 Automatisierungsmöglichkeiten der Datenvorbereitung vs. Benutzerfreundlichkeit
5.3.3 Analyse
5.3.3.1 Anzahl der Analysemethoden vs. Benutzerfreundlichkeit
5.3.3.2 Automatisierung der Modellbildung vs. Produktivität
5.3.4 Ergebnispräsentation und -interpretation
5.3.4.1 Präsentationsmöglichkeiten vs. Informationsaufbereitung
5.3.4.2 Validierungsmöglichkeiten vs. Automatisierung
5.3.4.3 Integrationsmöglichkeiten in EIS vs. Integrationsaufwand

6 Fazit

Verzeichnisse

Quellenverzeichnis

Abkürzungsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

Erklärung

Anhang: Produktbeschreibungen

A-1 Business Miner 4.0

Produktübersicht

Datenextraktion und -transformation

Musterentdeckung / Modellbildung

Ergebnispräsentation

A-2 Data Engine 2.1

Produktübersicht

Datenextraktion und -transformation

Musterentdeckung / Modellbildung

Ergebnispräsentation

A-3 KnowledgeSeeker 4.2

Produktübersicht

Datenextraktion und -transformation

Musterentdeckung / Modellbildung

Ergebnispräsentation

A-4 Scenario 2.0

Produktübersicht

Datenextraktion und -transformation

Musterentdeckung / Modellbildung

Ergebnispräsentation

A-5 SuperQuery 1.2

Produktübersicht

Datenextraktion und -transformation

Musterentdeckung / Modellbildung

Ergebnispräsentation

We are drowning in information, but starving for knowledge (John Naisbett).

1 Data Mining - Neuer Ansatz zur Datenanalyse

Die Auswirkungen der aufziehenden Informationsgesellschaft spiegeln sich auch in der explosionsartigen Zunahme der gespeicherten Informationen wider. So verdoppeln sich die in Datenbanken abgelegten Bestände eines durchschnittlichen Unternehmens nach Schätzungen alle 5 Jahre [IBM96a]. Das größte, betriebswirtschaftlich genutzte Data Warehouse der Welt wird vom amerikanischen Kaufhauskonzern Wal-Mart unterhalten und umfaßt eine Datenmenge von 25 Terabyte, wobei ca. 90 Millionen Point-of-sale (POS) Transaktionen pro Woche eingespielt werden [WÜRM98, S. 17]. Auf dem naturwissenschaftlichen Sektor entstehen mit dem menschlichen Gen-Datenbank-Projekt oder dem NASA Earth Observing System (mit 50 Gigabyte Bilddaten pro Stunde) in den Petabyte-Bereich (1015 Byte) hineingehende Datenbanken [FAYY96a, S. 2].

Technologisch ist dies kein Problem – die rasanten Steigerungen der zu günstigen Kosten verfügbaren Festplattenkapazitäten und die Leistungsfähigkeit der Prozessoren sowie die enormen Leistungssprünge von Datenbanksystemen (sowohl relational als auch multidimensional) halten hier leicht Schritt. Doch betriebswirtschaftlich machen diese Datensammlungen nur dann Sinn, wenn aus ihnen auch Erkenntnisse abgeleitet werden können, die Unternehmen bei der Verfolgung ihrer individuell unterschiedlichen Ziele unterstützen können. An dieser Stelle setzen Analysewerkzeuge an, die entweder als Ergänzung zu Datenbankprogrammen, betriebswirtschaftlichen Standardanwendungssystemen oder auch als Spezialwerkzeuge angeboten werden. Bis zur Einführung von Data Mining-Lösungen Anfang der 90er Jahre war allen Ansätzen gemein, daß der Antrieb zur Datenanalyse vom Anwender (sei es nun der Entscheider oder eine DV-Abteilung) ausgehen muß. Query & Reporting-, OLAP- und statistische Werkzeuge analysieren die Datenbestände nach zuvor aufgestellten Fragestellungen und liefern Ergebnisse auf zuvor exakt definierte Problemstellungen; es handelt sich also um eine gerichtete (bzw. manuelle [FAYY96b] oder verifikationsgeleitete [SIMO96; IBM96a]) Datenanalyse (Abschnitt 1.1). Dies beschränkt den Erkenntniswert auf die Bereiche, die von den Anwendern als interessant angesehen werden. Unbekannte Datenkonstellationen bleiben so unter Umständen für immer in den Datenbanken des Unternehmens verborgen oder fallen lediglich eher zufällig, sozusagen als Abfallprodukt der geplanten Abfragen an.

Data Mining-Werkzeuge gehen nun weiter und ermöglichen es, den Datenbestand automatisch zu analysieren, ohne zuvor eine exakte Fragestellung zu formulieren. Dem Computersystem wird es überlassen, selbständig interessante Muster in den Daten zu finden oder Modelle der Daten aufzubauen. Diese auch als ungerichtete Datenanalyse bezeichnete Vorgehensweise soll es ermöglichen, bislang unentdeckte Zusammenhänge aus den großen Datenbanken zu extrahieren und dem Unternehmen offenzulegen (Abschnitt 1.2). Die Freiheitsgrade, aber auch die Komplexität der Analysen sind dabei größer, als bei den gerichteten Verfahren (Abb. 1-1).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1-1: Werkzeugklassen zur Datenanalyse

Das Forschungsgebiet, das sich mit dieser Art der Informationsgewinnung beschäftigt, heißt Erkenntnisgewinnung aus Datenbanken (Knowledge Discovery in Databases - KDD). Es systematisiert die Aufgaben für Data Mining-Methoden und betrachtet den gesamten Erkenntnisgewinnungsprozeß in einem stufenweisen Modell, in dem das Data Mining eine zentrale Position einnimmt (Kapitel 2). Wie die meisten Ansätze der Informationstechnologie bestehen auch Data Mining-Lösungen nicht aus wirklich neuen Methoden, sondern integrieren eine Vielzahl bereits seit langem verfügbarer Techniken zur Datenanalyse (Kapitel 3). Die vielfältigen betriebswirtschaftlichen Anwendungen (Kapitel 4) versprechen in einigen Bereichen erhebliche Effizienzsteigerungen bei der Datenanalyse und tragen damit direkt zur Wettbewerbsfähigkeit von Unternehmen bei. Softwarelösungen zum Data Mining befinden sich noch im Übergang vom Projekt- zum Produktgeschäft. Die Implementierung von endbenutzertauglichen Techniken gestaltet sich hier schwieriger, zeitaufwendiger und kostspieliger als erwartet. Ein aktueller Schritt in diese Richtung sind Desktop Data Mining-Produkte, deren Leistungsfähigkeit im 5. Kapitel anhand von 5 getesteten Produkten vorgestellt und verglichen werden soll.

1.1 Gerichtete Datenanalyse

Werkzeuge, die den Datenanalytiker bei der gerichteten Datenanalyse, also dem gezielten Suchen nach Information durch Verifizierung von Hypothesen unterstützen, sind Query & Reporting-, OLAP- und statistische Werkzeuge.

1.1.1 Query und Reporting

Query und Reporting-Werkzeuge gestatten es dem Anwender Abfragen an die Datenbasis zu formulieren, auszuführen und die Ergebnisse der Abfrage weiterzuverarbeiten. Die Funktionen reichen von einfachen SQL-Editoren bis hin zu grafisch orientierten Werkzeugen, mit deren Hilfe die Erstellung und Verteilung standardisierter Berichte ermöglicht wird. Je nach Schwerpunkt können diese etablierten entscheidungsunterstützenden Werkzeuge noch einmal in Managed Reporting Environments (MRE) und Managed Query Environments (MQE) unterteilt werden. MRE sind benutzerfreundliche Berichtsgeneratoren mit Schwerpunkt auf Verteil- und Lieferungsfunktionen während als MQE Abfrage- und Berichtswerkzeuge bezeichnet werden, die bereits einige mehrdimensionale Funktionen unterstützen [MART97].

1.1.2 OLAP

Der Begriff OLAP (On-Line Analytical Processing) wurde 1993 erstmals von Codd in einem Aufsatz geprägt, in dem er die Schwächen des von ihm entwickelten relationalen Datenbankmodells und der Abfragesprache SQL für die Unterstützung mehrdimensionaler komplexer Analysen beschrieb [CODD93, S. 87-89]. Er forderte eine dimen­sionsorientierte Modellierung der Unternehmensdaten in Würfel, die der Sicht- und Analyseweise eines Entscheiders entsprechen und eine schnelle Verarbeitung und Auswertung entscheidungsrelevanter Daten ermöglichen. Die Anwender erhalten sehr leistungsfähige Instrumente zur Navigation in den durchlässigen Hierarchieebenen (drill down, -up und –through). Flexible Sichtweisen auf die Daten werden durch Auswahl verschiedener Dimensionselemente (slice) und eine Verschiebung der Betrachtung des Würfels (dice) erzielt [SCHI97a, S. 38f.].

1.1.3 Statistische Analyse

Während in vielen Query & Reporting-und OLAP-Werkzeugen einfache statistische Funktionen bereits integriert sind, benötigt man zur Verifikation komplexer Hypothesen Software, die umfangreiche statistische Analysefunktionen unterstützt. Statistische Methoden eignen sich vor allem, um Aussagen über numerische Variablen zu treffen. Zur Beschreibung von Daten können Kenngrößen wie Mittelwert, Varianz, Standardabweichung, Minimum, Maximum, Spannweite, Schiefe oder Exzeß interessant sein [MIT97, S. 143]. Im Bereich der statistischen Werkzeuge verschwimmen teilweise die Grenzen zwischen gerichteter und ungerichteter Datenanalyse, da einige statistische Verfahren wie z. B. Regressions- oder Diskriminanzanalyse auch zur ungerichteten Datenanalyse benutzt werden können. Lineare und nicht-lineare Regressionsmethoden erlauben es, Funktionsverläufe zu generalisieren und damit Vorhersagen vor allen in Zeitreihen zu treffen. Mit Hilfe der Diskriminanzanalyse können Klassifizierungen vorgenommen werden [SCHU80, S. 153f.]. Ebenso ist die Clusteranalyse eine klassisches Verfahren zur Segmentierung, das in der statistischen Software, z. B. in den weit verbreiteten Statistikpaketen SPSS und SAS, schon länger implementiert ist. Nachteil der statistischen Methoden ist aber, daß sie nur von Anwendern mit statistischem Wissen bedient werden können, um beispielsweise die geeigneten Verfahrensschritte und Variablen korrekt auszuwählen [MICH94, S. 2]. Eine völlig automatische Musterentdeckung ist somit mit statistischen Werkzeugen häufig nicht möglich.

1.2 Ungerichtete Datenanalyse

Im Gegensatz zur gerichteten Datenanalyse, also dem Verifizieren von Hypothesen des Benutzers, wird bei der ungerichteten Datenanalyse Information aus Daten in Datenbanken möglichst selbständig durch ein autonomes System identifiziert und ausgegeben. Data Mining-Werkzeuge stellen solche ungerichteten Methoden zur Verfügung und komplettieren damit in der Regel bestehende Data Warehouse- und OLAP-Lösungen durch das Hinzufügen dieser neuen Analysemöglichkeit zur herkömmlichen Datenauswertung.

Die selbständige Identifikation von Informationen über Daten in Form von Mustern oder Modellen durch ein Computersystem wird durch ein Lernen des Computersystems, insbesondere in Form eines induktiven Lernens, verwirklicht. Anders als ein Expertensystem, das Probleme durch menschliche Expertenüberlegungen löst, die in einem Computermodell kodiert wurden, trifft ein lernendes System Entscheidungen, die durch die angesammelte Erfahrung von erfolgreich gelösten Fällen fundiert sind [WEIS91, S.1].

1.2.1 Deduktion versus Induktion

Aus logischer Sicht können Informationen, die über das einfache Aufzählen von Daten hinausgehen, hauptsächlich durch zwei Möglichkeiten gewonnen werden: Deduktion oder Induktion [HOLS94, S. 7f.].

Deduktion bezeichnet das Schließen auf Information, die die logische Konsequenz aus vorhandenen Daten ist. Vor allem relationale Datenbankmanagementsysteme bieten einfache Operatoren zur Deduktion von Information an, allen voran den join-Befehl. Werden beispielsweise zwei verschiedene Tabellen durch eine dritte verbunden, so können Zusammenhänge der zwei Ausgangstabellen über die dritte deduziert werden. Die deduktive Aussagefähigkeit der Abfragesprachen zu erhöhen ist Bestandteil des Forschungsgebietes der Deduktiven Datenbanken. Deduktiv gelernte Verknüpfungen von Daten, die eventuell mathematisch oder statistisch weiterverarbeitet wurden, sind Informationen, die durch gerichtete Verfahren der Datenanalyse gewonnen werden können.

Induktion bezeichnet dagegen das Schließen auf Information, die durch Generalisierung der vorhandenen Daten gewonnen wird, z. B. in Form eines Musters oder Modells der Daten. Induktiv gelernte Information stellt Information auf einer höheren Ebene dar und kann den Anwender damit zu besseren Erkenntnissen über die Daten führen. Durch das Finden von Regelmäßigkeiten in den Daten können so Regeln aufgestellt werden, die Werte von Attributen in Zusammenhang mit anderen Attributen vorhersagen können [HOLS94, S. 7] oder generalisierte Aussagen über gleichartige Untergruppen der Daten beschreiben.

Der wichtigste Unterschied zwischen deduktiv und induktiv gewonnener Aussagen ist, daß erstere richtige Aussagen über die Wirklichkeit darstellen, gesetzt den Fall, daß die Daten der Datenbank korrekt sind, während letztere nur für die Daten der Datenbank gelten, aber nicht unbedingt in der Wirklichkeit korrekt sein müssen. Sie können wegen der endlichen Zahl an Beispielen in der Datenbank immer falsifiziert werden [ADRI96, S. 14f.]. Bei induktiv gelernten Aussagen ist also immer auch eine Validierung nötig.

Die gebräuchlichsten Lernparadigmen des induktiven Lernens sind das überwachte und das unüberwachte Lernen [BIGU96, S. 61]. Beide werden in Data Mining-Lösungen verwendet.

1.2.2 Überwachtes Lernen

Das überwachte Lernen von Mustern bzw. Modellen wird i. d. R. für Klassifizierungsaufgaben eingesetzt. Dem lernenden System (z. B. ein Neuronales Netz) werden Beispiele von Elementen verschiedener Klassen gezeigt, anhand derer es die typischen Eigenschaften der Klassen lernen soll. Während der Trainingsphase wird die Differenz des errechneten Ergebnisses zum tatsächlichen Ergebnis bestimmt und dem System eine Rückmeldung gegeben. Ziel ist es, den Zusammenhang der Eingabewerte mit dem Ergebnis zu entdecken und zu generalisieren, also in einem Modell darzustellen. Nach dem Training kann die Klassifizierungsleistung anhand von Testdaten, die dem System bis dahin unbekannt sind, überprüft werden. Überwachtes Lernen kann somit nur vorgenommen werden, wenn eine Datenbank mit Beispielen vorliegt, die sowohl Problemstellung als auch die Antwort des Problems repräsentieren [BIGU96, S. 62].

1.2.3 Unüberwachtes Lernen

Beim unüberwachten Lernen werden dem lernenden System im Gegensatz zum überwachten Lernen von außen keine Beispiele gezeigt oder andere Vorgaben gemacht, um die Daten zu generalisieren. Ziel des unüberwachten Lernprozesses ist das selbständige Entdecken von Zusammenhängen der Daten, insbesondere Ähnlichkeiten in den Attributen von Objekten. Die Aufgabe von Verfahren, die sich auf unüberwachte Lernmethoden stützen, ist üblicherweise eine Segmentierung des Datenbestandes in Cluster.

1 2 Erkenntnisgewinnung aus Datenbanken

Mit dem interdisziplinären Workshop "Knowledge Discovery in Databases" (KDD), der 1989 in Detroit stattfand, wurden die konzeptionellen Grundlagen des gleichnamigen Forschungsgebietes gelegt, das hier mit Erkenntnisgewinnung aus Datenbanken übersetzt werden soll. Nicht die Differenzierung einer wissenschaftlichen Disziplin, sondern die Verschmelzung von Teilbereichen verschiedener, ehemals getrennt operierender Forschungsgebiete machen das besondere der Erkenntnisgewinnung aus Datenbanken aus [HAGE97].

In diesem Kapitel soll das Konzept der Erkenntnisgewinnung aus Datenbanken, die Überschneidungen zu anderen Forschungsgebieten und der Prozeß, in dessen Zentrum das Data Mining steht, dargestellt werden.

2.1 Konzept

Ziel jeder Datenanalyse ist es, Informationen aus Daten zu gewinnen.

Informationen sind Nachrichten, die beim Empfänger etwas bewirken, den Wissenstand erhöhen oder eine Aktion auslösen [THOME90, A2] und aus einer Vielzahl von Ein­zelinformationen zur Beschreibung von Objekten (= Daten [THOM90, D 1.1.1]) generiert werden. Solche Nachrichten können gefundene Muster in Datenbeständen sein.

Gegenstand der Erkenntnisgewinnung aus Datenbanken ist die Extraktion von Datenmustern, genauer gesagt, der nicht triviale Prozeß, gültige, bisher unbekannte, verständliche und potentiell nützliche Muster in Daten zu finden [FAYY96a, S. 6].

Das Wort Muster ist in dieser Definition weiter gefaßt als im alltäglichen Sprachgebrauch und beschreibt eine zusammenfassende Aussage über einen Teil von Daten. Ebenso könnte man auch von einem Modell sprechen, das für diesen Teil der Daten anwendbar ist. Der Zusammenhang zwischen Muster und Modell soll in dieser Arbeit anlehnend an Fayyad folgendermaßen verstanden werden [FAYY96a, S. 11]: Ein Muster beschreibt die Konkretisierung eines Modells, so wie beispielsweise das Muster Abbildung in dieser Leseprobe nicht enthalten eine Konkretisierung des Modells Abbildung in dieser Leseprobe nicht enthalten darstellen kann. Gemäß obenstehender Definition müssen die gefundenen Muster mit einer gewissen Wahrscheinlichkeit gültig sein, insbesondere auch, wenn neue Daten zu den ursprünglichen hinzukommen. Bisher unbekannt sollte ein gefundenes Muster auf jeden Fall dem System, wenn möglich auch dem Benutzer sein, dem es dann verständlich dargestellt wird. Gültigkeit, Neuigkeit und Verständlichkeit führen zur Kernanforderung an die gefundenen Muster: Sie müssen potentiell nützlich sein. Dies bedeutet, daß der Benutzer neue Erkenntnisse über die Daten gewinnt, aus denen er Nutzen ziehen kann. Die Erkenntnisgewinnung erfolgt in einem Prozeß, der neben der Mustererkennung noch weitere Stufen des Vor- und Aufbereitens der Daten und der gefundenen Ergebnisse umfaßt (Abschnitt 2.4) und nicht trivial sein sollte, d. h. es sollen z. B. nicht nur definierte statistische Kennzahlen berechnet, sondern nach Strukturen oder Modellen gesucht werden [FAYY96a, S. 6f.; FAYY96b, S. 30].

Data Mining ist eine Stufe im Prozeß der Erkenntnisgewinnung aus Datenbanken und bezeichnet das automatische Entdecken von Modellen und Mustern in Datenbeständen durch Anwendung von Algorithmen [FAYY96a, S. 9]. Die benutzten Methoden sollen dabei allgemein verwendbar, effizient und autonom aus großen Datenbeständen die bedeutsamsten Muster identifizieren und dem Anwender diese als interessantes Wissen präsentieren [MATH93, S. 903]. Dieses Leitbild ist bewußt visionär angelegt und ist insbesondere hinsichtlich Autonomie, allgemeiner Verwendbarkeit und Bedeutsamkeit der Muster der Maßstab zur Beurteilung heutiger Systeme.

2.2 Verwandte Forschungsgebiete

Data Mining bedeutet die Zusammenführung und Integration verschiedener Methoden und Techniken zur Datenanalyse (Abb. 2-1). Möglich wurde dies erst durch eine fortgeschrittene Datenbanktechnologie, die es erlaubt, große Datenmengen leistungsfähig zu sammeln, zu verwalten und zur Analyse bereitzustellen. Auch wenn einzelne Techniken des Data Mining schon länger bekannt sind, so ist die Integration zur Datenanalyse erst in den letzten Jahren durch effizienzsteigernde Verbesserungen der Algorithmen und die Verfügbarkeit hoher Verarbeitungsgeschwindigkeiten der Prozessoren und Speichermedien zu geringen Kosten ermöglicht worden [DECK95]. Die Entwicklung von unterstützenden Expertensystemen und anwenderfreundlichen Benutzerschnittstellen, die es auch Nicht-Spezialisten auf den einzelnen Gebieten erlauben, ungerichtete Datenanalysen durchzuführen, führen ebenfalls zu einer weiteren Verbreitung der Methoden.

Die Einflüsse aus der Statistik auf das Data Mining sind stark, da teilweise statistische Verfahren eingesetzt werden (z. B. die Clusteranalyse) und sehr häufig statistische Tests zur Validierung von Mustern benötigt werden. Aufgrund der Forderung nach einer möglichst großen Autonomie der Data Mining-Systeme eignet sich vor allem der Einsatz von statistischen Expertensystemen, wie sie beispielsweise Haux beschreibt [HAUX89]. Das System sollte in der Lage sein, anhand seines statistischen Methodenwissens dem Problem und den zu analysierenden Daten angemessene Verfahren korrekt auszuwählen und durchzuführen.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2-1: Herkunft der Data Mining-Verfahren und -Techniken

Viele Methoden des Data Mining wurden außerdem aus dem Gebiet des Maschinellen Lernens übernommen. Auf der Grundlage diverser Theorien zum Erkennen und Lernen in biologischen Systemen wurden Algorithmen und Verfahren für eine maschinelle Umsetzung entwickelt. Als Repräsentationsformen der Erkenntnisse wurden vor allem Entscheidungsbäume und die normalsprachliche Ausgabe von Regeln eingeführt.

Neuronale Netze stammen aus dem interdisziplinären Forschungsgebiet der Neuroinformatik, dessen Ziel es ist, anhand von Erkenntnissen über die Funktionsweise biologischer Gehirne neuartige, in ihren Fähigkeiten flexiblere Computer zu bauen [RITT91, S. 3]. Dazu wird vor allem unter Abkehr von der traditionellen von-Neumann-Rechnerarchitektur die massiv parallele Informationsverarbeitung in Gehirnen imitiert.

Data Mining betrachtet jeweils nur einen kleinen Ausschnitt aus den einfließenden Bereichen. Der Forschungsgegenstand aller beteiligten Gebiete, insbesondere des Maschinellen Lernens und der Neuronalen Netze, sind vor allem bezüglich der verschiedenen Möglichkeiten des Lernens deutlich weiter gesteckt. Gibt es beispielsweise besonders starke Überlappungen hinsichtlich der verwendeten Algorithmen und behandelten Probleme im Bereich des überwachten und unüberwachten Lernens, werden Lernformen wie das Lernen aus Analogien beim Data Mining völlig ausgeklammert [HAGE97, S. 604]. Eine Kodierung der Umwelt erfolgt für das Maschinelle Lernen darüber hinaus i. d. R. in kleinen, speziell angelegten, Trainings-Sätzen. Data Mining-Methoden werden jedoch auf Datenbanken angewandt, die meist unter völlig anderen Gesichtspunkten als eine ungerichtete Datenanalyse angelegt wurden. Im Lernprozeß müssen demnach unweigerlich auftretende Fehler wie falsche, fehlende oder widersprüchliche Daten berücksichtigt werden [HOLS94, S. 16].

2.3 Aufgaben

Die beiden übergeordneten Ziele des Data Mining zur Erkenntnisgewinnung aus Datenbanken sind immer:

- Vorhersage unbekannter oder zukünftiger Werte interessierender Variablen einer Datenmenge durch andere Variablen der Datenmenge, oder

- Beschreibung einer Datenmenge durch verständliche Muster, die in ihr gefunden wurden [FAYY96a, S.12].

Je nach Anwendung unterscheiden sich die Wichtigkeit von Vorhersage oder Beschreibung; häufig werden auch beide Möglichkeiten kombiniert, z. B. eine Segmentierung zum Finden von Klassen für eine spätere Klassifizierung neuer Datensätze.

Drei Hauptaufgaben für Data Mining-Anwendungen im betriebswirtschaftlichen Umfeld zur Vorhersage und Beschreibung von Daten sind die Klassifizierung, Segmentierung und Assoziierung.

2.3.1 Klassifizierung

Das Wort Klassifizierung hat im Sprachgebrauch zwei Bedeutungen. Zum einen bezeichnet es die Einteilung einer Menge an Beobachtungen bzw. Objekten in Klassen. Wenn eine Klasseneinteilung bereits bekannt ist, kann Klassifizieren aber auch die Erstellung einer Regel zur Einordnung neuer Beobachtungen in vorhandene Klassen bedeuten. Erstgenannte Vorgehensweise wird auch unüberwachtes Lernen, genannt, die zweite überwachtes Lernen. Beide Verfahren sind Gegenstand von Data Mining-Techniken, weshalb zur sprachlichen Trennung in dieser Arbeit unter Klassifikation immer das überwachte Lernen, also die Einteilung von Objekten in bekannte Klassenstrukturen gemeint ist, während das unüberwachte Lernen mit dem Begriff Segmentierung oder Clustern beschrieben wird [HENE94, S. 6; CHEE96, S.154].

Die Aufgabe der Vorhersage ist sehr eng mit der Klassifizierung verwandt, weil beispielsweise ein Versuch vorherzusagen, wie ein Kunde auf ein Angebot reagiert, immer eine Klassifizierung des Kunden in eine Gruppe (die ein bestimmtes Verhalten zeigt) impliziert [ADRI96, S. 58].

2.3.1.1 Ziel

Aufgabe der Klassifizierung ist es, ein Verfahren aufzubauen, das auf eine fortlaufende Reihe von Fällen angewandt wird und jeden neuen Fall anhand seiner Variablen bzw. Eigenschaften einer vordefinierten Klasse zuteilt [MICH94, S. 1].

Hierfür wird ein Klassifizierer mit Trainings- und Testdaten, die bereits mit einer Klassenzugehörigkeit versehen sind, aufgebaut. Anhand der gemeinsamen Attribute der Elemente jeder Klasse wird ein Modell zur Beschreibung der Klassen entwickelt und innerhalb des Klassifizierers in Strukturen oder Regeln abgebildet. Training und Test des Klassifizierers erfolgt dabei durch eine außenstehende Instanz, die die Güte der Klassifizierung beurteilt und zurückmeldet (überwachtes Lernen).

Nach dem Training des Klassifizierers muß die Klassifizierungsleistung anhand von Testdaten ermittelt werden. Die wichtigsten Parameter sind dabei Genauigkeit, Lerngeschwindigkeit, Klassifizierungsgeschwindigkeit und Verständlichkeit. Je nach Anwendung können unterschiedliche Prioritäten gesetzt werden. Bei Einsatz im Kreditwesen könnte beispielsweise die Genauigkeit das oberste Ziel sein, da falsche Klassifikationen bei der Einschätzung eines Kreditrisikos sehr teuer sein können. In anderen Gebieten könnte ein Klassifizierer, der 90% aller Fälle richtig klassifiziert einem Klassifizierer mit 95% Genauigkeit vorgezogen werden, wenn er 100 mal schneller lernt. Die Verständlichkeit der Klassifikationsregeln sind wichtig, wenn sie von Menschen nachvollzogen und richtig umgesetzt werden sollen.

Nach Training und Test kann ein Klassifizierer benutzt werden, weitere, bis dahin unbekannte Daten zu klassifizieren. Entstanden ist damit ein Generalisierer, da von einem Satz an Beispielen auf unbekannte externe Daten geschlossen werden kann [DECK95]. Auch wenn ein Generalisierer i. d. R. weniger Dimensionen berücksichtigt, als in den Daten vorhanden sind, sollte die Komplexität des aufgebauten Modells ausreichend hoch sein, um die wichtigsten Eigenschaften der Regelmäßigkeiten in den Daten wiederzugeben. Dabei existiert eine strikte Beziehung zwischen der Komplexität des Modells und der Anzahl der Beispieldaten. Wird ein komplexes Modell mit zu wenig Daten trainiert, wird das Modell die Daten perfekt wiedergeben, aber schlecht generalisieren. Dieses Phänomen wird "over-fitting" genannt [DECK95]. Für komplexe Probleme sollte also immer eine ausreichende Anzahl an Beispieldaten vorhanden sein.

2.3.1.2 Techniken

Ansätze zur Klassifizierung kommen hauptsächlich aus den drei Forschungsrichtungen Statistik, Maschinelles Lernen und Neuronale Netze [MICH94, S. 2] (Abb. 2-2).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2-2: Techniken zur Klassifizierung

Statistische Techniken teilen sich noch einmal in klassische und moderne Techniken. Klassische Techniken beschäftigen sich prinzipiell mit Fortentwicklungen der linearen Diskriminanzanalyse nach Fisher, z. B. in Form der quadratischen oder logistischen Diskriminanzanalyse und der Einbeziehung von Bayes Regeln. Mitchell [MITC94] bietet eine gute Übersicht der klassischen Methoden.

Moderne Techniken benutzen flexiblere Methoden (z. B. muß die zugrundeliegende Dichtefunktion nicht mehr bekannt sein), die häufig versuchen, die Verteilung der Attribute in jeder Klasse zu schätzen, um daraus Klassifikationsregeln abzuleiten. So werden beispielsweise fallbasierte (oder auch k-nächste-Nachbarn) Klassifizierer eingesetzt, die neue Fälle anhand der Ähnlichkeit zu bekannten Fällen einordnen. Bei Molina et al. [MOLI94] werden die modernen Verfahren ausführlich beschrieben.

Generell liegen allen statistischen Methoden oftmals Wahrscheinlichkeitsmodelle zugrunde, die eher die Wahrscheinlichkeit angeben, mit der ein Element zu jeder Klasse gehört, als eine strenge Klassifizierung vorzunehmen [MICH94, S. 2]. Außerdem wird i. d. R. davon ausgegangen, daß Statistiker die Verfahren einsetzen, da zur Variablenauswahl und -transformation und der generellen Strukturierung des Problems noch viel Interaktion mit dem Benutzer verlangt wird. Diese Anforderung statistischer Verfahren widerspricht demnach den Forderungen nach Autonomie und einfacher Bedienbarkeit.

Von den Techniken des Maschinellen Lernens werden vor allem Entscheidungsbäume und -regeln zur Klassifikation eingesetzt, da sie bei ausreichender Anzahl von Trainingsbeispielen in der Lage sind, auch sehr komplexe Probleme abzubilden (Abschnitt 3.2). Interventionen des Benutzers beschränken sich (wenn überhaupt) auf die Lernphase des Baumes [MICH94, S. 2]. Weiterhin gibt es Anwendungen für genetische Algorithmen. Bei ihnen stehen die Elemente einer Population im Wettstreit miteinander, die beste Klassifikation vorzunehmen. Die Klassifikationsleistung wird verbessert durch das Sterben schlecht klassifizierender Elemente und das Überleben der gut klassifizierenden, die dann neue Varianten von sich erzeugen [QUIN93, S. 14].

Neuronale Netze bestehen aus einer Vielzahl von Berechnungseinheiten, die verknüpft sind und nicht-linear auf ihre Eingabewerte reagieren. Die Nicht-Linearität der Ergebnisfindung ermöglicht die Modellierung sehr komplexer und genereller Funktionen (Abschnitt 3.3).

Eine Vergleich verschiedener Algorithmen aus der Statistik, dem Maschinellen Lernen und Neuronaler Netze haben Michie, Spiegelhalter und Taylor vorgestellt [MICH94a]. Als Ergebnis zeigte sich, daß es keine insgesamt überlegene Technik für Klassifikationsaufgaben gibt, sondern die Leistungsfähigkeit der Algorithmen sehr stark von der Art der Daten und dem Ziel der Klassifikation abhängig ist.

2.3.2 Segmentierung

Während die Klassifizierung das überwachte Lernen von Regeln zur Klasseneinteilung beschreibt, so findet bei der Segmentierung ein unüberwachtes Lernen der Datenstruktur statt, um weitestgehend automatisch die „natürlichen“ Klassen eines Datenbestandes zu finden [CHEE96, S. 153].

2.3.2.1 Ziel

Segmentierung bedeutet die Einteilung einer Datenbank in Gruppen (Cluster) zusammengehöriger oder ähnlicher Datensätze. Die in Einheiten zusammengefaßten Datensätze teilen dann eine gewisse Anzahl interessierender Eigenschaften [SIMO96]. Die Segmentierung ist vor allem ein notwendiger Schritt, um Ordnung in große Datenbestände zu bringen, die eine Vielzahl an Objekten beschreiben [MASS83, S. 1]. Eine Segmentierung wird angewandt,

- um eine Zusammenfassung des Inhalts einer Datenbank zu erhalten (betrachtet werden können nun die Charakteristika der verschiedenen Segmente, anstelle jedes einzelnen Datensatzes) oder
- als Vorverfahren anderer Data Mining-Methoden, die dann mit kleineren, homogenen Ausschnitten aus der Datenbank arbeiten können (und damit schneller und effizienter werden) [SIMO96].

2.3.2.2 Techniken

Um Datenbestände zu segmentieren, eignen sich vor allem statistische Clusteranalyseverfahren (Abschnitt 3.1) und eine besondere Form von Neuronalen Netzten, sog. selbstorganisierende Karten oder Kohonen-Netze (Abschnitt 3.3).

Die statistischen Clusteranalyseverfahren werden zum Teil auch durch Techniken des Maschinellen Lernens ergänzt und dann als konzeptionelles Clustern bezeichnet. Neben der Gruppierung der Objekte soll so der Beziehungszusammenhang der Gruppen (Konzept genannt) in Form von Regeln abgeleitet werden. Besondere Bedeutung bei statistischen Lernaufgaben hat die Regel von Bayes über bedingte Wahrscheinlichkeiten. Ein sog. "Bayes-Klassifizierer" nimmt eine Segmentierung vor, indem er versucht, die Wahrscheinlichkeit zu maximieren, daß die vorgenommene Klassenbildung unter Bedingung der vorliegenden Daten der tatsächlichen Datenstruktur entspricht. Das Bayes-Verfahren bestimmt automatisch die Anzahl der Klassen einer Datenmenge und berechnet die Wahrscheinlichkeiten, mit der die Objekte in eine Klasse gehören. Ein Objekt wird also nicht fest einer Klasse zugeordnet, sondern gehört mit unterschiedlichen Wahrscheinlichkeiten zu unterschiedlichen Klassen [BISS93, S. 484; FAYY96b, S. 14f.].

2.3.3 Assoziierung

Die Assoziierung kann wie die Segmentierung als unüberwachtes Lernen von Regeln interpretiert werden, da die Algorithmen ohne Benutzerintervention eine Generalisierung der Daten vornehmen. Die Informationsgewinnung erfolgt durch eine Zusammenfassung gefundener Regelmäßigkeiten im Auftreten verschiedener Elemente des Datenbestandes.

2.3.3.1 Ziel

Bei der Assoziierung werden Muster von korrelierten Elementen in Dateneinheiten gefunden. Dies können Regeln sein, die Zusammenhänge zwischen Elementen eines Datensatzes beschreiben (Assoziationsregeln) [BOLL96, S. 257; IBM96, S. 8], oder Muster im zeitlichen Auftreten von Elementen in zusammengehörigen Datensätzen (Sequenzmuster) [AGRA95, S. 3; SRIK95, S. 3f.] ( Abschnitt 3.4).

2.3.3.2 Techniken

Der Basisalgorithmus zum Finden von Assoziationsregeln in Datenbanken APRIORI wurde 1993 von einer Gruppe um Agrawal im IBM Forschungszentrum Almaden entwickelt [AGRA93]. Aufgabe des Algorithmus ist es, im Datenbestand alle Assoziationsregeln mit einem vorgegebenen Mindestsupport und einer Mindestkonfidenz zu finden). Eine der vielen Erweiterungen ist die Einbeziehung zeitlicher Daten in die Assoziationsregeln, die somit Muster in Zeitreihen (Sequenzmuster) darstellen können. Ist in oben angegebenem Beispiel auch die Identität des Kunden bekannt (z. B. durch Kauf mit Kredit-, EC- oder Kundenkarten), so können aufeinanderfolgende Transaktionen einem Kunden zugeordnet werden und damit das Kaufverhalten im Zeitablauf auf regelmäßige Strukturen, sog. Sequenzmuster, untersucht werden. Ein gefundenes Sequenzmuster könnte lauten: 80% der Kunden, die Grillkohle kaufen, kaufen innerhalb von vier Wochen auch Bratwürstchen.

2.3.4 Weitere Aufgaben

Neben den drei Aufgaben Klassifizierung, Segmentierung und Assoziierung werden teilweise auch andere Aufgaben für Data Mining-Techniken genannt, wie z. B. die Regression und die Änderungs- und Abweichungsentdeckung.

Vor allem zum Aufbau von Vorhersagemodellen wird die mit der Klassifizierung verwandte Regression eingesetzt. Einem Objekt wird hier anhand seiner Attribute jedoch keine Klasse, sondern eine interessierende Zahl wie Umsatz oder Profitabilität zugeordnet. Beispiele sind Nachfragefunktionen für Produkte in Supermärkten, bei denen eine Vielzahl von Variablen eine Rolle spielen (Standort im Geschäft, Größe des Regalplatzes, Preis, Marketingmaßnahmen, Kundenstruktur des Geschäftes, Jahreszeit, Tageszeit, etc.). Besondere Aufmerksamkeit kommt auch der Rekonstruktion von Zeitreihen zu, da bei richtiger Projektion beispielsweise einer Aktienkursfunktion hohe finanzielle Rückflüsse winken. Techniken des Maschinellen Lernens und Neuronale Netze übertreffen hier häufig die statistischen Möglichkeiten (multivariate Regressionsverfahren) bei besonders komplexen nicht-linearen Zusammenhängen [FELS97].

Die Änderungs- und Abweichungsentdeckung soll die signifikantesten Änderungen von vorher gemessenen oder normativen Werten in großen Datenbeständen finden [FAYY96a, S. 16]. Gerade bei "Ausreißern" in Datenreihen kann es sich um interessante Fälle handeln, die bei näherer Betrachtung neue Informationen für den Anwender darstellen können.

2.4 Prozeß

Der Prozeß der Erkenntnisgewinnung aus Datenbanken teilt sich in drei Hauptstufen: Datenpräparation, Analyse und schließlich die Ergebnispräsentation und -interpretation (Abb. 2-3).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2-3: Prozeß der Erkenntnisgewinnung aus Datenbanken

Der gesamte Prozeß läuft interaktiv und iterativ ab. Interaktiv, da der Anwender auf jeder Stufe des Erkenntnisgewinnungsprozesses Entscheidungen über die Qualität der bisher erzielten Ergebnisse und das weitere Vorgehen fällen muß. Voraussetzung hierfür ist wiederum ein etabliertes Domänenwissen des Benutzers, der sich in den Daten auskennen muß und nur so die richtigen Schritte und Verfahren zur Erreichung eines bestimmten Zieles der Erkenntnisgewinnung einsetzten kann [BRAC96]. Der Prozeß wird iterativ durchlaufen, da einzelne Stufen häufig mehrfach ausgeführt werden, um das Ergebnis zu verbessern, oder die Ergebnisse einer Stufe zu Erkenntnissen führen, die Veränderungen in einer Vorstufe verlangen. In der Regel läuft der Erkenntnisgewinnungsprozeß solange als ein hin- und herspringen zwischen den verschiedenen Stufen ab, bis eine weitere Wiederholung keine signifikante Verbesserung das Ergebnisses verspricht [FAYY96a, S. 9-11].

Visualisierungstechniken spielen auf allen Ebenen eine große Rolle. Durch graphische Darstellungen der meist multidimensionalen Daten kann der Anwender ein Verständnis über Inhalt und Struktur der Daten entwickeln, die er niemals durch Betrachten von Tabellen oder statistischen Kennzahlen erlangt hätte. Dieses Verständnis ist von entscheidender Bedeutung für die Interaktion mit den Programmen, sowohl bei der Datenpräparation, als auch bei der Auswahl der richtigen Data Mining-Techniken [BRAC96, S. 45]. Außerdem können die Ergebnisse des Data Mining-Verfahrens durch Visualisierungs-Tools einfacher präsentiert werden [SIMO96].

2.4.1 Datenvorbereitung

Bevor Methoden des Data Mining auf Datenbestände angewandt werden können, müssen diese vorbereitet werden. Hierzu gehört die Selektion der Daten, die verarbeitet werden sollen, das Reinigen der Datenbestände sowie die Transformation der Daten in gewünschte oder benötigte Formen. Bis zu 80% des Gesamtprozesses der Informationsgewinnung in Datenbanken besteht aus der Datenpräparation [GERB96]. Dieser Aufwand ist erforderlich, da die Qualität der Ergebnisse direkt von der Qualität und Sauberkeit der Daten abhängt [META95a].

2.4.1.1 Selektion

Zuerst werden aus dem Gesamtdatenbestand diejenigen Daten, die für die aktuelle Analyse uninteressant sind, ausgeblendet, um so eine Auswahl zu erhalten, die alle möglicherweise relevanten Informationen bezüglich einer bestimmten Fragestellung enthält. Möchte eine Supermarkt-Kette beispielsweise wissen, welche Produkte häufig zusammengekauft werden, um sie entsprechend anzubieten, braucht sie hierfür keine Daten über das Zahlungsverhalten der Kunden. Es werden also die entsprechenden Tabellen aus der Datenbank ausgewählt, wobei eventuell noch joins zwischen den Tabellen angelegt werden müssen [SIMO96]. Da diese Tabellen häufig immer noch sehr groß sind, kann man, um Zeit und Geld zu sparen, auch eine Stichprobe aus den vorhandenen Daten ziehen (Sampling). Bei korrekter Durchführung werden so in dem untersuchten Teil der Daten alle Muster, die auch für den Gesamtdatenbestand gültig sind, mit einer berechenbaren Sicherheit gefunden [KIVI94].

2.4.1.2 Reinigung

Datensätze aus operationalen Datenbanken sind in der Regel unvollständig und mit inhaltlichen und semantischen Fehlern behaftet. Außerdem werden sie aus den verschiedensten Verfahren, Datenbanksystemen und Systemoberflächen zusammengeführt [SIMO96]. In der Datenvorbereitung müssen also z. B. doppelte Datensätze gelöscht, leere Felder gefüllt oder Tabellen umbenannt werden, um eine konsistente Datenbasis zu schaffen. Wie beim Aufbau eines Data Warehouse gehört hierzu auch die Daten nicht nur formal, sondern auch inhaltlich zu standardisieren. Beispielsweise dürfen Umsatzzahlen einheitlich keine Mehrwertsteuer enthalten, Angaben in verschiedenen Währungen müssen umgerechnet werden, etc.

Zur Datenreinigung können verschiedene Techniken verwendet werden. Beispiele sind regelbasierte Techniken, die Inhalte von Datenfeldern anhand von Metawissen bezüglich zulässiger Werte überprüfen. Statistische Techniken benutzen statistische Informationen, um fehlende oder falsche Werte auf neutrale und gültige Werte zu setzen. Visualisierungstechniken können schließlich benutzt werden, um in großen Datenbeständen Ausreißer oder außerhalb bestimmter Grenzen liegender Daten einfach und schnell zu identifizieren [BIGU96, S. 48f.].

2.4.1.3 Transformation

Bei der Transformation der Daten besteht die Möglichkeit der Definition neuer Attribute, die durch mathematische oder logische Operationen aus bereits bestehenden Datenbankattributen abgeleitet werden, oder auch die Zusammenfassung mehrerer Felder durch ein Feld mit mehr Information. Beispiele sind die Einführung von Summenspalten oder die Berechnung von Abweichungs- und Durchschnittswerten [INMO96a, S. 186].

Weiterhin sind zum Teil strukturelle Änderungen nötig wie die Konvertierung von Datentypen, damit bestimmte Data Mining-Techniken mit ihnen arbeiten können. Die meisten Neuronalen Netze können beispielsweise nur numerische Werte zwischen 0 und 1 oder -1 und +1 verarbeiten [BIGU96, S. 50].

2.4.1.4 Data Warehouse als Datenlieferant

Ziel der Datenpräparation im Prozeß der Erkenntnisgewinnung aus Datenbanken ist die Schaffung einer konsistenten und integrierten Datenbasis für die Anwendung von Data Mining-Verfahren. Das von Inmon 1992 formulierte Data Warehouse-Konzept sieht ganz ähnlich den Aufbau einer themenorientierten, integrierten, zeitbezogenen und dauerhaften Sammlung von Informationen zur Datenanalyse und Entscheidungsunterstützung vor [INMO96a, S. 33f.; SCHI96, S. 468f.]. Die Vorbereitungsschritte Datenreinigung und -transformation müssen sowohl beim Aufbau eines Data Warehouse, als auch beim Data Mining vollzogen werden. Die integrierte Datenbasis des Data Warehouse kann also eine große Zeit- und damit Kostenersparnis für den Datenanalytiker bedeuten, da er sich auf seine eigentliche Aufgabe konzentrieren kann und nicht durch die Integration von fehlerhaften und uneinheitlichen Daten aus heterogenen Quellen aufgehalten wird. Weiterhin sind im Data Warehouse historische, detaillierte und zusammengefaßte Daten vorhanden [INMO96b, S. 49]. Jede dieser zusätzlichen Eigenschaften erhöht die Erfolgswahrscheinlichkeit des Data Mining: Historische Daten erlauben ein Verständnis der zyklischen Veränderungen und langfristigen Muster in den Daten. Sehr detaillierte Daten können wichtige Muster verbergen, die in höheren Aggregationsstufen nicht mehr sichtbar sind. Zusammengefaßte Daten auf der anderen Seite erlauben es, die Ergebnisse früherer Analysen zu speichern, um so auf bereits vollbrachter Arbeit aufbauen zu können. Zusätzlich beschreiben die Metadaten eines Data Warehouse den Kontext der gespeicherten Informationen und erlauben somit ein Verständnis der Daten und ein Aufbau vom Domänenwissen.

Data Mining kann ohne ein Data Warehouse durchgeführt werden, jedoch ist das Data Warehouse durch die Natur der in ihm gespeicherten Daten eine sehr gute Ausgangsbasis für erfolgreiches und effizientes Data Mining.

Eine Umfrage Anfang 1998 ergab, daß 25% der Firmen, die ein Data Warehouse betreiben, Data Mining-Verfahren einsetzen. 19% sehen im Data Mining sogar die wichtigste Aufgabe ihres Datenlagers [COMP98].

2.4.2 Analyse

Nachdem die Daten vorbereitet wurden, kann in der Analysephase das Data Mining, also ein Anwenden von Algorithmen zur Suche nach Mustern in Daten, stattfinden. Inwiefern die so gefundenen Muster letztendlich sinnvolle neue Erkenntnisse darstellen, muß im interaktiven Prozeß der Erkenntnisgewinnung aus Datenbanken normalerweise noch vom Anwender bestimmt werden, auch wenn Filter entwickelt werden, die redundante und unwichtige Muster ausblenden sollen.

Für die betrachteten Daten finden Data Mining-Algorithmen Modelle, die bestimmte Aufgaben erfüllen, wie z. B. eine Klassifizierung oder Segmentierung.

Neben seiner Funktion ist die Darstellung eines Modells von großer Bedeutung, da sie die Flexibilität des Modells, Daten zu beschreiben, und die Verständlichkeit des Modells für den Menschen bestimmt [FAYY96b, S. 32]. Nach Auswahl eines Verfahrens müssen die einzusetzenden Data Mining-Techniken wie z. B. Entscheidungsbäume oder Neuronale Netze ausgewählt und angewandt werden (Kapitel 3). Oft ist es nötig, verschiedene Techniken nacheinander oder mehrfach anzuwenden, da die produzierten Ergebnisse wieder Rückschlüsse auf die Qualität der gewählten Datenbasis zulassen oder Ergebnisse liefern, die als Ausgangsdaten für neue Techniken benutzt werden [FAYY96a, S. 11].

2.4.3 Ergebnispräsentation und -interpretation

Die gefundenen Muster und Modelle müssen nun gemäß der Zielsetzung des Informationsgewinnungsprozesses präsentiert und interpretiert werden. Es kann auf vorhergehende Stufen des Prozesses zurückgesprungen werden, um durch Veränderung von Variablen oder Verfahren bessere Ergebnisse zu erzielen. Visualisierungstechniken und verschiedene Repräsentationsformen der Modelle (z. B. Regeldarstellung als Entscheidungsbaum oder in wenn...-dann... Form) sollen dem Anwender helfen, interessante Zusammenhänge schneller zu identifizieren. Eine Validierung der Ergebnisse kann daraufhin durch Verfahren der gerichteten Datenanalyse erfolgen, wobei häufig statistische Verfahren zur Bestimmung der Fehlerwahrscheinlichkeit benutzt werden. Darüber hinaus muß sich der Anwender Gedanken machen, wie er die neuen Erkenntnisse umsetzt, also ob er sie z. B. in das Datenbanksystem einarbeitet, und wie er sie dokumentiert und weitergibt [SIMO96]. Letztendlich sollten die gefundenen Muster in Informationen umgewandelt werden, die dem Unternehmen durch Umsetzung in Entscheidungen und Handlungen einen Mehrwert generieren [BERR97, S. 18].

3 Techniken

Data Mining kombiniert Techniken aus verschiedenen Gebieten wie Statistik oder Maschinellem Lernen zur Datenanalyse. Dabei wird ein Modell der Daten aufgebaut, um diese zu generalisieren und interessante Muster zu finden. Die angewandte Data Mining-Technik bestimmt dabei die Verständlichkeit und Flexibilität des Modells, die Daten zu beschreiben. [FAYY96b, S. 32]. Die beiden übergeordneten Aufgaben von Data Mining Beschreibung und Vorhersage lassen sich durch ein einheitliches Modell verwirklichen, weil beschreibende in vorhersagende Modelle verwandelt werden können, wenn das zu untersuchende Verhalten aus einer zukünftigen Zeitperiode gewählt wird [FERR97]. Beschreibende Modelle der Daten sind somit vergangenheitsbezogen und können für Anwendungen wie eine Marktsegmentierung verwendet werden. Eine gegenwartsbezogene Verarbeitung anfallender Daten ergibt sich bei der Analyse laufender Transaktionen, wobei die Entdeckung von Mustern, die beispielsweise auf betrügerische Handlungen hinweisen, sofortigen Handlungsbedarf signalisieren. Zukunftsbezogene Modelle werden vor allem bei stochastischen Systemen benötigt, da dort aufgrund unvollständiger Information Unsicherheit bezüglich zukünftiger Systemzustände besteht. Data Mining-Techniken können hier i. d. R. bessere Prognosemodelle aufbauen als herkömmlich statistische Verfahren.

Neuere Techniken implementieren häufig nicht-parametrische Methoden, d. h. sie machen keine Annahmen über die Dichteverteilung der Objekte wie z. B. eine Gauß´sche Glockenkurve der Normalverteilung. Statt dessen wird die Leistungsfähigkeit des Computers zu suchen und iterieren ausgenutzt, bis eine gute Anpassung an die Beispieldaten erreicht ist. Die Gefahr einer zu starken Anpassung des Modells und damit einer schlechten Generalisierung wird ohne die Annahme von Populationsparametern jedoch stark erhöht. Eine wichtige Aufgabe ist also, die Modellfunktion den Beispielen soweit anzunähern, daß auch neue Objekte gut klassifiziert werden [WEIS91, S. 12f.].

Aus der Vielzahl der verfügbaren Techniken sollen in diesem Kapitel exemplarisch diejenigen Methoden vorgestellt werden, die in Standardwerkzeugen zum Data Mining hauptsächlich implementiert sind: Clusteranalyse, Entscheidungsbäume, Neuronale Netze sowie Assoziationsregeln und Sequenzmuster.

Weitere verwendete Techniken, deren Darstellung den Rahmen dieser Arbeit übersteigen würde, sind vor allem moderne statistische Techniken zur Klassifizierung und Regression, das fallbasierte Schließen (CBR) und genetische Algorithmen. Der besondere Vorteil evolutionärer Verfahren ist, bei der Anpassung eines Modells an die Daten sicherer die global beste Lösung, statt eventuell nur eine lokal beste Lösung zu finden.

Abb. 3-1 zeigt die hauptsächlichen Einsatzgebiete der beschriebenen Techniken für die in Abschnitt 2.3 vorgestellten Aufgaben des Data Mining.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3-1: Hauptaufgaben der Data Mining-Techniken

3.1 Clusteranalyse

Die Clusteranalyse ist ein statistisches Verfahren zur Segmentierung von Daten. Ziel ist es, Objekte anhand ihrer Eigenschaften zu Gruppen (Clustern) zusammenzufassen. Die Mitglieder einer Gruppe sollen dabei möglichst ähnlich zueinander sein, während zwischen den Gruppen eine möglichst geringe Ähnlichkeit erwünscht ist [SCHU80, S. 107]. Da Verfahren zur Clusteranalyse bereits seit ca. 35 Jahren entwickelt werden, existiert eine große Anzahl unterschiedlicher Ansätze. Bacher differenziert anhand ihrer Zuordnungsprinzipien drei Hauptkategorien von Clusteranalyseverfahren: unvollständige, deterministische und probabilistische Verfahren [BACH96].

Unvollständige Verfahren nehmen lediglich eine Darstellung der zu gruppierenden Objekte in einem niedrigdimensionalen Raum (maximal 3 Dimensionen) vor. Die Bildung der Cluster und die Zuordnung der Objekte zu Clustern bleibt dem Anwender bei der Interpretation der räumlichen Darstellung überlassen [BACH96, S. 4]. Eine Anwendung dieser Verfahren im Umfeld des Data Mining ließe sich also höchstens zur Visualisierung von Daten mit wenigen Dimensionen vorstellen, weshalb die unvollständigen Verfahren in dieser Arbeit nicht weiter betrachtet werden sollen.

Die deutlich leistungsfähigeren deterministischen Verfahren berechnen die Zugehörigkeit der zu gruppierenden Objekte zu Clustern. Je nach Vorgehensweise können partitionierende und hierarchische Verfahren unterschieden werden. Bei den zuerst genannten wird nach einer zufälligen Gruppeneinteilung der Objekte versucht, die Clusterbildung sukzessive durch Austausch von Objekten zu verbessern, um eine möglichst hohe Homogenität in den Gruppen zu erreichen. Beim hierarchischen Ansatz stellt entweder jedes Objekt zu Beginn ein eigenes Cluster dar, die dann mit möglichst geringem Homogenitätsverlust zusammengefaßt werden (agglomerative Methode) oder es wird von einem Cluster mit allen Objekten ausgegangen, das aufgeteilt wird (divisive Methode) [SCHU80].

Die probabilistischen Verfahren stellen letztlich eine Weiterentwicklung des deterministischen K-Means Verfahrens (s. u.) dar, bei dem die Objekte nicht mit einer Wahrscheinlichkeit 0 oder 1 zu einem Cluster gehören, sondern mit einer Wahrscheinlichkeit zwischen 0 und 1. Statt eines diskreten wird also ein kontinuierliches Wahrscheinlichkeitsmaß verwendet.

Sowohl hierarchische als auch partitionierende Gruppierungsverfahren werden in diesem Kapitel nach einer Betrachtung der verschiedenen Prinzipien zur Clusterbildung vorgestellt. Unabhängig von den gewählten Verfahren und Prinzipien muß vor einer Gruppierung jedoch die Ähnlichkeit von zwei Objekten quantifiziert werden können, um einen Vergleich der Eigenschaftsstrukturen von Objekten und Objektgruppen zu ermöglichen (folgender Abschnitt).

3.1.1 Quantifizierung von Ähnlichkeit

Die Ähnlichkeit von Objekten wird durch einen Vergleich der zugehörigen Variablenwerte gemessen. Um verglichen werden zu können, müssen die Werte jedoch das gleiche Skalennivau (vgl. Tab. 3-1) aufweisen, weshalb Variablen mit verschiedenen Skalenniveaus getrennt bewertet oder auf gleiches Niveau transformiert werden [SCHU80, S. 4 und S. 124f.].

Nach dem Herstellen der Vergleichbarkeit muß ein Ähnlichkeitsmaß bestimmt werden. Grundsätzlich eignen sich hierfür Korrelationskoeffizienten (Ähnlichkeit steigt mit steigenden Werten) oder Distanzmaße (Ähnlichkeit sinkt mit steigenden Werten), bzw. aus ihnen abgeleitete Ähnlichkeitsmaße. Üblicherweise werden für die Gruppierung von Objekten Distanzmaße eingesetzt [BACH96, S. 199].

Eine Beeinflussung der Ähnlichkeitsberechnung durch Gewichtung bestimmter Variablen oder Objekte durch den Anwender kann zusätzlich sinnvoll sein, um beispielsweise den Gruppierungsvorgang vorrangig für interessierende Objekte vorzunehmen oder den Einfluß vorbestimmter Gruppierungsmerkmale wie eine unternehmensinterne Produktgruppeneinteilung zu verringern [MERT94, S. 744].

Tab. 3-1: Einteilung der Skalenniveaus [SCHU80, S. 5]

Abbildung in dieser Leseprobe nicht enthalten

Die Möglichkeiten zur Distanzmessung sind vielfältig. Das wohl meist benutzte Maß zum Vergleich zweier Objekte mit metrisch skalierten Variablen ist der Euklidische Abstand [BERR97, S. 198]. Um ihn zu berechnen, wird die Wurzel aus der quadrierten Entfernungssumme der Variablen gezogen. Ebenfalls häufig dokumentiert ist die etwas einfacher zu berechnende City-Block-Distanz, bei der die absoluten Differenzwerte jeder Eigenschaft summiert werden [SCHU80, S. 123; MERT94, S. 744].

Sollen die Ähnlichkeiten von Datenfeldern innerhalb eines Datensatzes eher anhand ihres Verhältnisses zueinander als an ihrer absoluten Höhe gemessen werden, so bedient man sich bei metrisch skalierten Variablen auch des Vektorwinkels als Distanzmaß. Jedem Punkt wird sein Vektor vom Ursprung aus zugewiesen und anhand der Entfernungen zwischen den Steigungswinkeln der Vektoren eine Ähnlichkeit zwischen den Punkten bestimmt. Es handelt sich also um eine andere geometrische Interpretation, die eher Richtung als Werthöhe berücksichtigt. Abb. 3-2 zeigt, daß die gleichen Punkte anhand der Distanzmaße Objektabstand oder Vektorenwinkel in zwei völlig andere Cluster gruppiert werden.

Sollen Objekte, deren Variablen nicht-metrische Skalenniveaus aufweisen (z. B. kategorielle Variablen) segmentiert werden, bestimmt man zunächst die Anzahl der übereinstimmenden Felder zweier Datensätze. Dies ist besonders einfach, wenn die Merkmalsausprägungen binär dargestellt werden können, z. B. beim Geschlecht: männlich=0 und weiblich=1. Variablen mit mehr als 2 möglichen Werten werden häufig in sämtlich mögliche Ausprägungsformen aufgespalten, denen dann ein binärer Bool´scher Wert zugeordnet wird. Vorteil des Verfahrens ist vor allem die effiziente Speichermöglichkeit und hohe Berechnungsgeschwindigkeit der Ähnlichkeitsmatrix [GRAB96]. Nachteilig ist das Auftreten von dünn besiedelten Matrizen, in denen die wenigen Felder, die tatsächlich Information enthalten, dominiert werden. Eine Möglichkeit diesen Effekt zu kompensieren ist eine höhere Gewichtung von Null verschiedener Übereinstimmungen [BERR97, S. 204].

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3-2: Clusterbildung anhand des Objektabstandes oder Vektorwinkels

3.1.2 Prinzipien der Clusterbildung

Allen Verfahren der Clusterbildung liegt eine der folgenden 4 Grundvorstellungen bezüglich einer Zusammenfassung von Objekten zu Gruppen zugrunde [BACH96, S. 142f.]. Welches Prinzip im konkreten Fall angewendet wird, ist insbesondere vom zugrundeliegenden Datenmaterial und den Anforderungen an die zu bildenden Cluster abhängig. Die aufgeführten Prinzipien gelten auch für die Zusammenfassung von Clustern, z. B. bei hierarchischen Gruppierungsverfahren (Abb. 3-5). Ein Data Mining-Werkzeug sollte insbesondere bei der Methodenwahl möglichst viele Entscheidungen selbst übernehmen oder vorbereiten und überwachen, z. B. in Form der Anwenderunterstützung durch ein statistisches Expertensystem.

3.1.2.1 Nächste-Nachbarn-Verfahren

Nachdem die Ähnlichkeit der Objekte zueinander berechnet wurde, können die "Nachbarn" jedes Objektes bestimmt werden. Als nächste Nachbarn werden alle Objekte bezeichnet, deren Ähnlichkeit unter einem vorgegebenen Schwellenwert liegt. Als Gruppenbildungsmerkmal müssen nun von diesen nächsten Nachbarn eine bestimmte Anzahl innerhalb des gleichen Clusters liegen. Die strengste Forderung hinsichtlich der Homogenität innerhalb eines Clusters fordert hierbei das complete-linkage Verfahren (= Methode des weitest entfernten Nachbarn), bei dem alle Objekte eines Clusters nächste Nachbarn zueinander sein müssen. Das single-linkage Verfahren (= Methode des nächsten Nachbarn) fordert entgegengesetzt nur eine schwache Homogenität der Gruppenmitglieder: Es muß nur mindestens einen nächsten Nachbarn innerhalb des zu bildenden Clusters geben [BACH96, S. 142f.].

Nächste-Nachbarn-Verfahren haben manchmal unerwünschte Eigenschaften bezüglich der Gruppenbildung: Single-linkage Verfahren führen häufig zu "verketteten" Clustern, wenn nebeneinander liegende Cluster sich nicht klar voneinander abgrenzen. Statt Cluster in der typischen elipsoiden Form werden dann langgezogenen lineare Cluster gebildet, deren entferntesten Punkte sehr unterschiedlich sein können. Die Anforderungen des complete-linkage Verfahrens haben den gegenteiligen Effekt: Es werden viele kleine Cluster gebildet, auch wenn eine Bildung von größeren Clustern eventuell sinnvoller wäre [MASS83, S. 84].

3.1.2.2 Mittelwertmodelle

Cluster werden bei Mittelwertmodellen durch die durchschnittliche paarweise Ähnlichkeit der Mitglieder innerhalb des Clusters oder verschiedener Cluster untereinander charakterisiert (average-linkage Verfahren) [BACH96, S. 143]. Es kommt hier nicht zu den oben erwähnten unerwünschten Effekten der nächsten-Nachbarn-Verfahren. Das average-linkage Verfahren wurde beispielsweise von Mertens et al. für eine Data Mining-Anwendung in der Ergebnisrechnung ausgewählt [MERT94, S.745]. Vergleiche haben gezeigt, daß die Clusterbildung nach dem average-linkage Verfahren und dem Ward-Verfahren (s. u.) häufig die besten Ergebnisse liefern [MASS83, S. 86].

3.1.2.3 Repräsentantenverfahren

Jedes Cluster soll durch einen typischen Repräsentanten charakterisiert sein, der bei der Clusterung gesucht wird und dem dann alle n nächsten Nachbarn zugeordnet werden. Objekte, die außerhalb der nächste-Nachbar-Schranke aller anderen Objekte bleiben, werden keinem Cluster zugeordnet.

3.1.2.4 Konstruktion von Clusterzentren

Bei diesem Verfahren wird angenommen, daß jedes Cluster durch seinen Mittelpunkt, also den Mittelwert aller in das Cluster einbezogenen Objekte, charakterisiert wird. Bekannte Verfahren dieser Gruppe sind das Median-, Zentroid- oder K-Means Verfahren. Typisch für diese Verfahren ist ihr wanderndes Clusterzentrum, bis die beste Position erreicht ist (bei partitionierenden Verfahren) oder das Verfahren abgeschlossen ist (bei hierarchischen Verfahren). Eine Abwandlung ist das Ward-Verfahren, dessen Ziel es ist, unter Ausnutzung der Objektstreuung um das Clusterzentrum herum möglichst homogene Gruppen zu bilden. Hierzu wird die Varianz der Objekte in den Clustern gemessen und Cluster mit denjenigen Objekten gebildet, die eine möglichst kleine Abweichung vom Mittelwert haben [SCHU80, S. 134].

3.1.3 Partitionierende Gruppierungsverfahren

Bei partitionierenden Gruppierungsverfahren wird versucht, von einer vorgegebenen (zufällig bestimmten) Gruppeneinteilung der Objekte ausgehend, die Clusterbildung durch Austausch von Objekten zu verbessern. Vor Beginn des Verfahrens muß also die Anzahl der zu bildenden Gruppen vorgegeben werden, weshalb das gesamte Verfahren i. d. R. mehrmals mit verschiedenen Gruppenzahlen durchgeführt werden muß, um die aussagekräftigste Objektgruppierung zu finden. Die Bestimmung der besten Clusteranzahl kann auch automatisch unter Verwendung statistischer Kennzahlen wie beispielsweise der Fehlerstreuung geschehen (siehe ausführlich hierzu [BACH96, S. 316f.]), was für Data Mining-Anwendungen sehr interessant ist. Nach der zufälligen Zuteilung der Objekte zu Gruppen wird die Ähnlichkeit der Objekte innerhalb einer Gruppe berechnet. Daraufhin kann bestimmt werden, welcher Austausch von zwei Objekten die größte Steigerung der Gesamtähnlichkeit der Cluster bringt. Dieser Schritt wird solange wiederholt, bis keine Verbesserung der Homogenität mehr erzielt werden kann [SCHU80, S. 141f.].

Graphisch anschaulich ist das K-Means Verfahren, welches nach Berry das meist benutzte Verfahren in der Praxis ist [BERR97, S. 192f.] und deshalb hier an einem 2-dimensionalen Beispiel vorgestellt werden soll. Entsprechend der vorgegebenen Gruppenzahl werden zufällig Objekte als Clusterkerne bestimmt, um die sich die Gruppen dann formieren sollen. Abb. 3-3 zeigt eine Verteilung von Objekten im 2-dimensionalen Raum und die Gruppeneinteilung der Objekte in drei Cluster anhand von drei zufällig gewählten Kernen. Jeder Punkt wird demjenigen Kern zugeteilt, dem er am nächsten ist, wobei als Ähnlichkeits-(=Distanz)maß aus Anschauungsgründen die einfache Punktentfernung gewählt wurde. Gebräuchlich ist beim K-Means Verfahren normalerweise der Euklidischen Abstand [BACH96]. Geometrisch ergibt sich die Grenze zweier Gruppen als eine Gerade (grün eingezeichnet), die rechtwinkelig durch die Hälfte einer Verbindungslinie der beiden Kerne (in der Abb. gestrichelt) verläuft, da alle Punkte auf dieser Geraden von beiden Kernen gleich weit entfernt sind.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3-3: Objektverteilung und Clusterbildung mit zufälligen Kernen.

Nach der zufälligen Gruppeneinteilung im ersten Schritt, muß nun die Homogenität der Cluster durch Zuordnungsveränderungen von Objekten verbessert werden muß. Beim K-Means Verfahren wird dazu als neuer Kern der Clustermittelpunkt (Punkt mit der geringsten Entfernungssumme zu allen Objekten des Clusters) berechnet.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3-4: Clusterbildung mit neu berechneten Kernen

Abb. 3-4 zeigt die Lageveränderung der Kerne. Die neuen Kerne bestimmen nun die neuen Grenzen der Cluster und verändern damit auch die Gruppenzugehörigkeit einiger Objekte (in Abb. 3-4 hellblau dargestellt). Dieses Vorgehen wird solange wiederholt, bis kein Objekt mehr die Gruppe wechselt. Abb. 3-4 zeigt den 2. Schritt und gleichzeitig das Endergebnis des Beispiels.

Die Nachteile dieses ursprünglichen K-Means Algorithmus sind, daß

- schlechte Ergebnisse bei überlappenden Gruppen erzielt werden,
- die Cluster durch Ausreißer schnell aus dem Mittelpunkt gezogen werden und
- keine Aussage über die Höhe der Wahrscheinlichkeit, mit der ein Objekt wirklich zu einem Cluster gehört, gemacht wird.

Um diese Nachteile zu überwinden, sind zahlreiche Variationen und Ergänzungen des Verfahrens erdacht worden. Besonders bemerkenswert ist, daß alle probabilistischen Verfahren der Clusteranalyse als Verallgemeinerung des K-Means Verfahrens betrachtet werden können [BACH96, S. 353]. Bei ihnen wird als Ähnlichkeitsmaß statt der Entfernung eine Wahrscheinlichkeitsverteilung benutzt, um Objekte mit Clustern zu assoziieren. Hierdurch wird auch die Streuung der verschiedenen Objekte berücksichtigt. Ergebnis ist für jedes Objekt die Wahrscheinlichkeit, mit der es zu allen vorhandenen Clustern gehört. Probabilistische Verfahren werden daher manchmal auch als “weiches Clustern“ bezeichnet, im Gegensatz zur "harten" Berechnung bei deterministischen Verfahren [BERR97, S. 206].

3.1.4 Hierarchische Gruppierungsverfahren

Hierarchische Gruppierungsverfahren gehen nicht von einer vorgegebenen Menge an Clustern aus, sondern bauen einen hierarchischen Baum der zu Gruppen zusammengefaßten Objekte auf. Der Stamm des Baumes ist ein einziges Cluster mit allen Objekten des Datenbestandes. In der Spitze befinden sich eine Vielzahl von Clustern, die jeweils nur ein einziges Objekt enthalten. Durch die sukzessiv zunehmende Clusterzahl vom Stamm bis in die Spitzen ergibt sich die Baumstruktur. Je nachdem, ob der Baum von oben oder unten aufgebaut wird, unterscheidet man agglomerative und divisive Vorgehensweisen.

3.1.4.1 Agglomerative Vorgehensweise

Bei der agglomerativen Vorgehensweise wird die Gruppierung mit einer Clusterzahl begonnen, die so groß ist wie die Menge der Objekte. Nach und nach werden diese entsprechend ihrer Ähnlichkeit zusammengefaßt, bis nur noch ein Cluster mit allen Objekten existiert. Für die Berechnung der Ähnlichkeit, d. h. des Abstandes zwischen den Clustern gelten die in Abschnitt 3.1.2 genannten Prinzipien der Clusterbildung, die auch für einen Vergleich von Clustern angewandt werden können [SCHU80, S. 130].

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3-5: Verfahren zur Distanzberechnung von Clustern [BERR97, S. 209]

Abb. 3-5 zeigt die graphische Interpretation dreier ausgewählter Verfahren bei der Zusammenfassung von Clustern. Während beim single- und average-linkage Verfahren (Vergleich der nächsten Objekte bzw. Clusterzentren) Cluster I und II die geringste Distanz zueinander aufweisen und damit im nächsten Schritt des Algorithmus zusammengefaßt würden, wären die ähnlichsten Gruppen nach dem complete-linkage Verfahren (Vergleich der weitest entfernten Objekte) Cluster I und III.

Sämtliche Zusammenfassungsschritte mit den sukzessive abnehmenden Clusterzahlen werden aufgezeichnet und beispielsweise in einem Dendrogramm dargestellt, welches eine übersichtliche graphische Repräsentation des Verfahrensablaufs darstellt (siehe Abb. 3-6). Vorgenommen wurde als Beispiel die Gruppierung einer Anzahl von Menschen anhand ihres Alters mit dem single-linkage Verfahren. In diesem eindimensionalen Beispiel bedeutet dies, daß das größte Element des Clusters mit den jüngeren Mitgliedern mit dem kleinsten Mitglied des "älteren" Clusters verglichen wird. Abb. 3-6 zeigt das Dendrogramm bis zum Zahlenabstand 6, nach dem sich die Ausgangsobjekte auf drei verschiedene Cluster konzentriert haben.

Die generelle Frage, nach welcher Iteration nun für den Anwender aussagekräftige Cluster entstehen, kann beispielsweise anhand eines Vergleiches der Objektähnlichkeit innerhalb der Cluster zur Ähnlichkeit zwischen den Clustern beantwortet werden. Bei hierarchischen Verfahren nimmt die Homogenität innerhalb der Gruppe mit jeder Stufe, auf der zwei Cluster zusammengefaßt werden, ab, während sich die Cluster untereinander immer ähnlicher werden, bis letztendlich nur noch ein einziges übrigbleibt. Überstiegt die durchschnittliche Ähnlichkeit der Cluster untereinander diejenige innerhalb der Cluster, werden die Gruppierungen auf folgenden Iterationsstufen kaum noch große Aussagekraft für den Anwender haben. Der Vergleich der durchschnittlichen Ähnlichkeit ist als generelles Maß brauchbar, da es für Variablen jedes Skalenniveaus anwendbar ist. Ein gutes Anzeichen “starker“ Cluster ist darüber hinaus ein großer Abstand zwischen der Iteration, in der das Cluster geformt wurde, und der Iteration, in der es mit dem nächsten Cluster vereinigt wird. Im Beispiel von Abb. 3-6 wird das Cluster “1- bis 13-jährige“ bereits bei der 3. Iteration gebildet, würde aber erst viel später mit einem anderen Cluster zusammengefaßt.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 3-6: Dendrogramm einer hierarchischen Gruppierung [BERR97, S. 211]

3.1.4.2 Divisive Verfahren

Bei den divisiven Verfahren der hierarchischen Clusteranalyse wird ein Clusterbaum umgekehrt zu den agglomerativen Verfahren aufgebaut. Ausgehend von einem Cluster mit allen Objekten wird anhand der Objektähnlichkeit das Cluster kontinuierlich aufgeteilt, bis sich jedes Objekt in einem einzelnen Cluster befindet.

Die Ähnlichkeit des Verfahrens zum Aufbau von Entscheidungsbäumen drängt sich auf, da die resultierende hierarchische Baumstruktur gleich ist (s. Abschnitt 3.2). Tatsächlich können Algorithmen zum Aufbau von Entscheidungsbäumen wie CART oder CHAID auch zum Clustern benutzt werden. Die Algorithmen versuchen, anhand einer Unterscheidungsfunktion den Gesamtbestand an Objekten in "reinere" Cluster zu gruppieren. Alles was nun noch fehlt den Entscheidungsbaum-Algorithmen in einen Cluster-Algorithmen zu verändern, ist die Vorgabe einer Unterscheidungsfunktion, die entweder die intra-Cluster Homogenität oder die inter-Cluster Homogenität maximiert [BERR97, S. 213].

3.2 Entscheidungsbäume

Entscheidungsbäume wurden im Forschungsgebiet des Maschinellen Lernens entwickelt und ermöglichen eine weitgehend automatisierte Klassifizierung von Objekten, die auch für Vorhersagen genutzt werden kann. Zusammenhänge in Daten werden in Form von Regeln abgeleitet und bilden damit ein symbolisches Konzept der Daten, das die strukturellen Zusammenhänge zwischen Variablen aufzeigt und für Menschen verständlich und nachvollziehbar macht [FENG94, S. 51].

Die Technik wurde vorrangig für Klassifizierungsaufgaben entwickelt, insbesondere zur Erklärung kategorieller Klassifizierungsentscheidungen und zur Vorhersage von Klassen für neue Elemente. Die Objektklassifikationen werden durch induktives Lernen in Form eines überwachten Lernens vorgenommen. Die graphische Darstellung in einer Baumstruktur macht es für den Anwender bis zu einer gewissen Größe des Baumes besonders leicht zu verstehen, welche Variablen die Klassifikation in welcher Weise beeinflussen. Wird der Baum zu groß, dann bietet sich die Umwandlung in natürlichsprachige Entscheidungsregeln an, die aufgrund ihrer Struktur häufig Sachverhalte kürzer darstellen können und sie so für den Anwender transparent machen. Außerdem können Entscheidungsbäume und -regeln sowohl numerische als auch nominal e Attribute verarbeiten, was ein weiterer großer Vorteil dieses Verfahrens ist [CHAM98, S. 319]. Aufwendige Transformationen wie bei Neuronalen Netzen entfallen so. Schwächen zeigen Entscheidungsbäume bei Daten aus Zeitreihen und der Vorhersage kontinuierlicher numerischer Variablen wie Einkommen oder Zinssatz [BERR97, S. 284].

[...]