Clusterbasierte Datenanalyse auf Grundlage genetischer Algorithmen in SAP-BI - Ein Verfahren zur selbständigen Ermittlung der optimalen Anzahl Cluster (eBook)

Ein Verfahren zur selbständigen Ermittlung der optimalen Anzahl Cluster

eBook Download: PDF | EPUB

2011 | 1. Auflage
141 Seiten
Diplomica Verlag GmbH
978-3-8428-1609-1 (ISBN)

Infos

"Diese Studie beschäftigt sich mit der Erweiterung des SAP-BI um eine Data Mining Methode zur clusterbasierten Datenanalyse. Die Motivation dieses Buches ist, einen Algorithmus zu implementieren, welcher nicht nur eine Datenmenge in Clustern gruppiert, sondern parallel dazu die optimale Clusteranzahl selbstständig ermittelt. Aus dieser Motivation heraus wird im Verlauf der Studie ein zweistufiges Konzept zur ""gleichzeitigen"" Optimierung verschieden dimensionierter Daten auf Basis eines genetischen Algorithmus erarbeitet. Auf Grundlage dieses Konzeptes erfolgt anschließend die Implementierung des Verfahrens in der Programmiersprache ABAP."

Autor

Hüseyin Bostanci wurde 1976 in Gifhorn(Niedersachsen) geboren. Der Autor studierte Angewandte Informatik an der Hochschule Fulda mit dem Studienschwerpunkt Wirtschaftsinformatik. Sein Studium schloss er mit dem akademischen Grad Dipl. Inf. (FH) 2010 ab. Bereits während des Studiums sammelte der Autor umfassende praktische Erfahrungen in der Entwicklung kommerzieller Anwendungen durch verschiedene betriebliche Praktika. Im Verlauf seines Studiums entwickelte der Autor ein besonderes Interesse für algorithmische Grundlagen von Datenanalyseverfahren sowie deren Einsatz in betriebswirtschaftlichen Anwendungen. Aus diesem Interesse heraus widmete sich der Autor der Thematik des vorliegenden Buches. Zurzeit arbeitet der Autor als SAP-BI Berater.

Inhalt

Kurzzusammenfassung 3
Inhaltsverzeichnis 5
1 Einleitung 7
2 Grundlagen 9
2.1 Clusteranalyse 9
2.2 Partitionierende Verfahren 11
2.3 Evolutionäre Algorithmen 16
3 Clusteranalyse auf Basis eines Genetischen Algorithmus 25
3.1 Genetischer Algorithmus 25
3.2 Ermittlung einer Lösung mit optimaler Clustermenge 37
4 Implementierung 41
4.1 Der Analyseprozess 41
4.1.1 Die Architektur 41
4.1.2 Komponenten des Analyseprozesses 43
4.2 Das Analyseverfahren 46
4.2.1 Modellierung genetischer Begriffe 46
4.2.2 Distanzfunktion 49
4.2.3 Genetischer Algorithmus 53
5 Test und Vergleich 79
5.1 Analyse der Datenreihe 1 mit Genetischen Algorithmus 79
5.2 Analyse der Datenreihe 1 mit SAP-BI Clustering 82
5.3 Analyse der Datenreihe 2 mit Genetischen Algorithmus 83
5.4 Analyse der Datenreihe 2 mit SAP-Clustering 85
6 Diskussion der Ergebnisse 89
7 Abbildungsverzeichnis 91
8 Tabellenverzeichnis 92
9 Literaturverzeichnis 93
Anhang 95
1 Quellcode 96
1.1 Globale Daten 96
1.2 Rahmenfunktion 98
1.3 Distanzfunktion 100
1.4 Genetischer Algorithmus 102
2 Daten 122
2.1 Testdaten 122
2.1.1 Datenreihe 1 122
2.1.2 Datenreihe 2 122
2.2 Resultate der Testläufe 125
2.2.1 Datenreihe 1 125
2.2.2 Datenreihe 2 127

Textauszug

Textprobe: Kapitel 3.2, Konzept: Um den im vorherigen Kapitel beschriebenen Effekt der Distanzsummenabnahme mit Genetischen Algorithmen in ein Konzept zu bringen, müssen verschiedene Überlegungen bezüglich der Gestaltung des Algorithmus vorhergehen. Die Haltung verschieden dimensionierter Teilpopulationen innerhalb einer Population erfordert eine Anpassung derbisher vorgestellten Genetischen Algorithmen in Bezug auf Selektion- und Rekombination von Individuen, sowie die Beachtung des Suchfortschritts in den jeweiligen Teilpopulationen. Durch die Kostenfunktion werden alle Individuen einer Population in ihrer Fitness vergleichbar gemacht, sodass über eine fitnessproportionale Selektion ein Individuum aus der Gesamtpopulation zur Rekombination ausgesucht werden kann. Die Selektion des ersten Elters ist unabhängig von der Teilpopulation und erfolgt auf Basis der Fitnessberechnung der Gesamtpopulation. Die Auswahl des zweiten Elters zur Rekombination hingegen erfolgt innerhalb der Teilpopulation des ersten Elters, da Rekombination nur innerhalb gleich dimensionierter Lösungen einen Sinn macht. Durch entsprechende Restriktionen, wie zum Beispiel die Rekombination lediglich aufwärtskompatibel9 zu gestalten, wäre dies auch unter ungleich dimensionierten Individuen zwar möglich, ist aber für den Zweck dieser Arbeit ungeeignet. Eine Begründung dafür erfolgt im weiteren Verlaufe der Erarbeitung des Konzeptes. Um wiederrum einen geeigneten Paarungspartner aus der Teilpopulation zu bestimmen, muss innerhalb dieser, ebenfalls eine Fitnessberechnung durchgeführt werden, da sich die bisherige Fitness lediglich auf die Gesamtpopulation bezieht und nicht zur Ermittlung des erfolgversprechendsten Individuums aus einer Teilpopulation herangezogen werden kann. Für die Rekombination müssen also folgende Restriktionen aufgestellt werden. 1. Auswahl des ersten Elters, also indirekt auch auf welche Teilpopulation ein Genetischer Operand angewandt werden kann, erfolgt über die Berechnung der Fitness der Gesamtpopulation. Dabei werden alle Individuen so behandelt als wären sie gleich dimensioniert, somit hat jede Teilpopulation ungefähr gleiche Chancen bei der Auswahl zur Rekombination. Dies dient auch der Vereinheitlichung des Suchfortschrittes der Teilpopulationen. 2. Rekombination zwischen Individuen ist nur innerhalb einer Teilpopulation möglich, damit ein Suchfortschritt innerhalb der jeweiligen Gruppe sukzessiv stattfinden kann und dieser in allen Teilpopulation gleichermaßen fortschreitet. 3. Aus Punkt 2 folgt, zur Bestimmung eines geeigneten Paarungspartners erfolgt eine Neubewertung aller in Betracht kommenden Individuen, diesmal bezieht sich also die Fitnessberechnung auf die jeweilige Teilpopulation. Um den Suchfortschritt in allen Teilpopulationen gleichermaßen zu gewährleisten reicht allein die Gleichstellung der Teilpopulationen bei der Auswahl zur Rekombination nicht aus. Der Suchfortschritt kann verzerrt werden, falls sich die Teilpopulationen in ihrer Größe unterscheiden. In diesem Fall wäre die Wahrscheinlichkeit für Individuen ausgewählt zu werden umso höher, je größer die jeweilige Teilpopulation ist. Im Schnitt wäre also innerhalb einer Generation der Suchfortschritt bei größeren Teilpopulationen weiter als bei kleineren Populationen. Um dem entgegenzuwirken, ist die Gesamtpopulation so aufzuteilen, dass die Teilpopulationen die gleiche Anzahl von Lösungen beinhalten. Die Umweltselektion erfolgt auf Basis der Fitnesswerte bezogen auf die Gesamtpopulation. Das bedeutet, alle Individuen werden gleich behandelt, unabhängig von ihrer jeweiligen Dimension. Dabei werden die schlechtesten Elternindividuen einer Generation von besseren Kinderindividuen verdrängt. Diese Vorgehensweise ermöglicht die Kostenfunktion, welche den Effekt der Distanzsummenverringerung entgegenwirkt und somit Individuen ausverschiedenen Teilpopulationen vergleichbar macht. Unter Umständen kann aber bei einem solchen Vorgehen eine Teilpopulation gänzlich aus der Population verdrängt werden. Das passiert, wenn zum Beispiel durch Zufall eine Teilpopulation über einige Generationen hinweg weniger Kinder zeugt: Dann können die Kinder anderer Teilpopulationen diese verdrängen, da deren Suchfortschritt dann bereits vorangeschritten ist und sie somit vergleichsweise bessere Fitnesswerte aufweisen, werden diese immer häufiger zur Rekombination ausgesucht bis schließlich die immer kleiner werdende Teilpopulation so wenig Nachkommen hat, dass sie gänzlich verdrängt wird. Im ungünstigsten Fall könnte es die Teilpopulation mit der optimalen Dimensionierung sein, welche verdrängt wird. Aus dieser Überlegung heraus ist zu gewährleisten, dass die anfängliche Diversität bezogen auf die Anzahl der Dimensionen über den gesamten Verlauf des Verfahrens konstant bleibt. Durch Beibehaltung aller Teilpopulationen über die gesamte Verfahrensdauer kann dieser unerwünschte Zufallseffekt ausgeschlossen werden. Dieses kann durch den in Kapitel 'Selektion' beschriebenen Crowding Selektionsmechanismus erreicht werden, indem nicht wahllos die schlechtesten Elternindividuen durch bessere Kindindividuen verdrängt werden, sondern Kinder lediglich ihre eigenen Eltern in der Population ersetzten dürfen, sofern sie eine bessere oder mindestens äquivalente Güte aufweisen. Dadurch wird zum einen eine sukzessive Verbesserung der Teilpopulationen erreicht, und zum anderen der Erhalt aller Teilpopulationen einer Population gesichert. Durch die Vereinheitlichung der Fitnesswerte ist es möglich, am Ende des Verfahrens die Lösung mit dem besten Fitnesswert bezogen auf die Gesamtpopulation zu ermitteln. Im günstigsten Fall ist das die Lösung mit der optimalen Clusteranzahl und weist entweder bereits eine fortgeschrittene Optimierung bezüglich der Distanzsummen auf, oder ist sogar ein globales Optimum.

Produkt-Details

• Erscheint lt. Verlag: 1.6.2011
• Zusatzinfo: 68 Abb.
• Sprache: deutsch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Schlagworte: Clusteranalyse • Data Mining • Datenanalyse • Genetische Algorithmen • SAP BI • Wirtschaftsinformatik
• ISBN-10: 3-8428-1609-X / 384281609X
• ISBN-13: 978-3-8428-1609-1 / 9783842816091