Design, Implementierung und Analyse einer clusterbasierten Datenanalyse mit Hilfe evolutionärer Algorithmen in SAP BI
©2010
Diplomarbeit
136 Seiten
Zusammenfassung
Inhaltsangabe:Einleitung:
Der Einsatz von Datenanalyseverfahren zur Planung und Entscheidungsunterstützung gewinnt durch die enorm ansteigende Menge an zu verarbeitenden Daten für Unternehmen immer mehr an Bedeutung. Datenanalyseverfahren werden vielseitig eingesetzt, zum Beispiel die Clusteranalyse einer Kundendatenbank mit dem Ziel der Marktsegmentierung. Aus der Marktsegmentierung lassen sich wiederum Kundengruppen identifizieren, Zielgruppen ableiten sowie geeignete Marketingstrategien entwickeln. Ein weiteres Beispiel ist das Spotlight-System, welches Verkaufsdaten von Supermärkten analysiert. Das System findet Änderungen von Verkaufsmengen eines Produktes und entdeckt Zusammenhänge zwischen diesen Änderungen und möglichen Ursachen wie etwa Preis oder Qualitätsänderungen.
Der Vorteil solcher Verfahren für Unternehmen, die im Wettbewerb stehen, wird in den obigen Beispielen deutlich. So gibt es eine Reihe von Softwareherstellen wie SAP oder IBM, die Lösungen zu diesem Thema anbieten. Diese Arbeit befasst sich mit der SAP Lösung, speziell mit der Clusteranalyse.
Die Clusteranalyse im SAP BI basiert auf einer hocheffizienten und robusten Form des k-means Algorithmus. Dieser Algorithmus ist in der Lage, auch eine relativ große Datenmenge mit hoher Genauigkeit zu analysieren. Der Nachteil dieses Verfahrens besteht in der Angabe der Clusteranzahl als Parameter. Die richtige Clusteranzahl ist jedoch dem Benutzer in den meisten Fällen nicht bekannt. Arbeitet ein Algorithmus mit einer fest vorgegebenen Clustermenge, können unter Umständen wichtige Zusammenhänge verloren gehen, falls diese von der optimalen Clustermenge abweicht. Abbildung 1-1 verdeutlicht den Zusammenhang zwischen optimaler und nicht optimaler Clustermenge:
(an dieser Stelle befindet sich im Original eine Abbildung)
Um die richtige Clusteranzahl automatisch zu ermitteln, existieren verschiedene Lösungsansätze. Ein Beispiel ist die Bestimmung des Parameters k mittels des sogenannten Silhouetten-Koeffizienten. Dieser bestimmt die Güte einer Clusteranalyse unabhängig von der Anzahl der Cluster. Dazu wird die Clusteranalyse mit verschiedenen Werten für den Parameter k durchgeführt, anschließend wird aus der Menge der über den Silhouetten-Koeffizienten bewerteten Ergebnisse das beste Clustering ausgewählt. Eine weitere Möglichkeit stellt die Erweiterung des k-means, der x-means Algorithmus von Pelleg und Moore, dar. Bei diesem Verfahren wird ebenfalls keine feste Clusteranzahl […]
Der Einsatz von Datenanalyseverfahren zur Planung und Entscheidungsunterstützung gewinnt durch die enorm ansteigende Menge an zu verarbeitenden Daten für Unternehmen immer mehr an Bedeutung. Datenanalyseverfahren werden vielseitig eingesetzt, zum Beispiel die Clusteranalyse einer Kundendatenbank mit dem Ziel der Marktsegmentierung. Aus der Marktsegmentierung lassen sich wiederum Kundengruppen identifizieren, Zielgruppen ableiten sowie geeignete Marketingstrategien entwickeln. Ein weiteres Beispiel ist das Spotlight-System, welches Verkaufsdaten von Supermärkten analysiert. Das System findet Änderungen von Verkaufsmengen eines Produktes und entdeckt Zusammenhänge zwischen diesen Änderungen und möglichen Ursachen wie etwa Preis oder Qualitätsänderungen.
Der Vorteil solcher Verfahren für Unternehmen, die im Wettbewerb stehen, wird in den obigen Beispielen deutlich. So gibt es eine Reihe von Softwareherstellen wie SAP oder IBM, die Lösungen zu diesem Thema anbieten. Diese Arbeit befasst sich mit der SAP Lösung, speziell mit der Clusteranalyse.
Die Clusteranalyse im SAP BI basiert auf einer hocheffizienten und robusten Form des k-means Algorithmus. Dieser Algorithmus ist in der Lage, auch eine relativ große Datenmenge mit hoher Genauigkeit zu analysieren. Der Nachteil dieses Verfahrens besteht in der Angabe der Clusteranzahl als Parameter. Die richtige Clusteranzahl ist jedoch dem Benutzer in den meisten Fällen nicht bekannt. Arbeitet ein Algorithmus mit einer fest vorgegebenen Clustermenge, können unter Umständen wichtige Zusammenhänge verloren gehen, falls diese von der optimalen Clustermenge abweicht. Abbildung 1-1 verdeutlicht den Zusammenhang zwischen optimaler und nicht optimaler Clustermenge:
(an dieser Stelle befindet sich im Original eine Abbildung)
Um die richtige Clusteranzahl automatisch zu ermitteln, existieren verschiedene Lösungsansätze. Ein Beispiel ist die Bestimmung des Parameters k mittels des sogenannten Silhouetten-Koeffizienten. Dieser bestimmt die Güte einer Clusteranalyse unabhängig von der Anzahl der Cluster. Dazu wird die Clusteranalyse mit verschiedenen Werten für den Parameter k durchgeführt, anschließend wird aus der Menge der über den Silhouetten-Koeffizienten bewerteten Ergebnisse das beste Clustering ausgewählt. Eine weitere Möglichkeit stellt die Erweiterung des k-means, der x-means Algorithmus von Pelleg und Moore, dar. Bei diesem Verfahren wird ebenfalls keine feste Clusteranzahl […]
Leseprobe
Inhaltsverzeichnis
Hüseyin Bostanci
Design, Implementierung und Analyse einer clusterbasierten Datenanalyse mit Hilfe
evolutionärer Algorithmen in SAP BI
ISBN: 978-3-8428-0299-5
Herstellung: Diplomica® Verlag GmbH, Hamburg, 2010
Zugl. Fachhochschule Fulda, Fulda, Deutschland, Diplomarbeit, 2010
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 der Verlag, die Autoren oder
Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.
verbliebene fehlerhafte Angaben und deren Folgen.
© Diplomica Verlag GmbH
http://www.diplomica.de, Hamburg 2010
Kurzzusammenfassung
Diese Diplomarbeit beschäftigt sich mit der Erweiterung des SAP-BI um eine Data
Mining Methode zur clusterbasierten Datenanalyse. Die Motivation dieser Arbeit
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 Diplomarbeit ein
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.
P.
Inhaltsverzeichnis
1
Einleitung ... 1
2
Grundlagen ... 3
2.1
Clusteranalyse ... 3
2.2
Partitionierende Verfahren ... 5
2.3
Evolutionäre Algorithmen ...10
3
Clusteranalyse auf Basis eines Genetischen Algorithmus ...19
3.1
Genetischer Algorithmus ...19
3.2
Ermittlung einer Lösung mit der optimaler Clustermenge ...31
4
Implementierung ...35
4.1
Der Analyseprozess ...35
4.1.1
Die Architektur ...35
4.1.2
Komponenten des Analyseprozesses ...37
4.2
Das Analyseverfahren ...40
4.2.1
Modellierung genetischer Begriffe ...40
4.2.2
Distanzfunktion ...43
4.2.3
Genetischer Algorithmus ...47
5
Test und Vergleich ...73
5.1
Analyse der Datenreihe 1 mit Genetischen Algorithmus ...73
5.2
Analyse der Datenreihe 1 mit SAP-BI Clustering ...76
5.3
Analyse der Datenreihe 2 mit Genetischen Algorithmus ...77
5.4
Analyse der Datenreihe 2 mit SAP-Clustering ...80
6
Diskussion der Ergebnisse ...82
7
Abbildungsverzeichnis ...84
8
Tabellenverzeichnis ...85
9
Literaturverzeichnis ...86
10
Anhang ...87
10.1 Implementierung ...87
10.1.1
Globale Daten ...87
10.1.2
Rahmenfunktion ...88
10.1.3
Distanzfunktion ...90
10.1.4
Genetischer Algorithmus ...92
10.2 Daten ... 112
10.2.1
Datenreihe 1... 112
10.2.2
Datenreihe 2... 112
10.3 Resultate der Testläufe ... 115
10.3.1
Datenreihe 1... 115
10.3.2
Datenreihe 2... 117
1 | S e i t e
1
Einleitung
Der Einsatz von Datenanalyseverfahren zur Planung und Entscheidungsunterstützung
gewinnt durch die enorm ansteigende Menge an zu verarbeitenden Daten für Unternehmen
immer mehr an Bedeutung. Datenanalyseverfahren werden vielseitig eingesetzt, zum Beispiel
die Clusteranalyse einer Kundendatenbank mit dem Ziel der Marktsegmentierung. Aus der
Marktsegmentierung lassen sich wiederum Kundengruppen identifizieren, Zielgruppen
ableiten sowie geeignete Marketingstrategien entwickeln. Ein weiteres Beispiel ist das
Spotlight-System[Anand & Kahn 1992], welches Verkaufsdaten von Supermärkten analysiert.
Das System findet Änderungen von Verkaufsmengen eines Produktes und entdeckt
Zusammenhänge zwischen diesen Änderungen und möglichen Ursachen wie etwa Preis oder
Qualitätsänderungen.
Der Vorteil solcher Verfahren für Unternehmen, die im Wettbewerb stehen, wird in den
obigen Beispielen deutlich. So gibt es eine Reihe von Softwareherstellen wie SAP oder IBM,
die Lösungen zu diesem Thema anbieten. Diese Arbeit befasst sich mit der SAP Lösung,
speziell mit der Clusteranalyse.
Die Clusteranalyse im SAP BI basiert auf einer hocheffizienten und robusten Form des k-
means Algorithmus. Dieser Algorithmus ist in der Lage, auch eine relativ große Datenmenge
mit hoher Genauigkeit zu analysieren. Der Nachteil dieses Verfahrens besteht in der Angabe
der Clusteranzahl als Parameter. Die ,,richtige" Clusteranzahl ist jedoch dem Benutzer in den
meisten Fällen nicht bekannt. Arbeitet ein Algorithmus mit einer fest vorgegebenen
Clustermenge, können unter Umständen wichtige Zusammenhänge verloren gehen, falls
diese von der optimalen Clustermenge abweicht. Abbildung 1-1 verdeutlicht den
Zusammenhang zwischen optimaler und nicht optimaler Clustermenge:
Abbildung 1-1: Nicht Optimale & optimale Clustermenge
Um die ,,richtige" Clusteranzahl automatisch zu ermitteln, existieren verschiedene
Lösungsansätze. Ein Beispiel ist die Bestimmung des Parameters k mittels des sogenannten
Silhouetten-Koeffizienten[Kau90]. Dieser bestimmt die Güte einer Clusteranalyse unabhängig
von der Anzahl der Cluster. Dazu wird die Clusteranalyse mit verschiedenen Werten für den
Parameter k durchgeführt, anschließend wird aus der Menge der über den Silhouetten-
2 | S e i t e
Koeffizienten bewerteten Ergebnisse das ,,beste" Clustering ausgewählt. Eine weitere
Möglichkeit stellt die Erweiterung des k-means, der x-means Algorithmus von Pelleg und
Moore[Pel00], dar. Bei diesem Verfahren wird ebenfalls keine feste Clusteranzahl angegeben,
sondern ein Bereich, bei dem die optimale Anzahl Cluster wahrscheinlich liegen wird. Der
Algorithmus teilt die zu analysierende Datenmenge zunächst auf die Unterschranke k des
vorgegeben Bereichs auf. Anschließend wird k solange durch Teilung erhöht bis die obere
Grenze des Bereichs erreicht ist. Nach jeder Iteration wird eine Bewertung auf Basis eines
Bewertungskriteriums der vorhandenen Konstellation vorgenommen. Die Entscheidung, ob
und welche Cluster aufgespalten werden, erfolgt auf Grundlage des Bewertungskriteriums.
Anschließend wird das Modell mit der Clusteranzahl k, welche den höchsten Wert nach dem
Bewertungskriterium erreicht hat, ausgegeben. Eine andere Vorgehensweise zur
automatischen Ermittlung des Parameters k bieten Evolutionäre Algorithmen an. Diese
Kategorie
von
Optimierungsverfahren
orientiert
sich
an
den
natürlichen
Evolutionsprozessen. Im Rahmen dieser Optimierungsverfahren wird versucht, die
Selektionsmechanismen und Problemlösungsstrategien der Natur grob nachzubilden. Die
Basis für die meisten Evolutionären Algorithmen ist das Populationskonzept, welches eine
Menge von Lösungskandidaten beinhaltet. Durch zufällige Kreuzung und Mutation der
Lösungskandidaten wird iterativ versucht, eine hinreichend genaue Lösung zu generieren.
Das Populationskonzept ist relativ flexibel bezüglich der Lösungskandidaten, so besteht die
Möglichkeit dieses Konzept um die der Teilpopulationen zu erweitern. Im Kontext des
Problems des Parameters k stellt eine Teilpopulation die Lösungsmenge eines bestimmten
Wertes für k dar. Im Laufe des Verfahrens werden die Lösungskandidaten aller
Teilpopulation gleichermaßen optimiert. Durch eine einheitliche Bewertung ließe sich auf
diesem Wege der Lösungskandidat mit der optimalen Clusteranzahl ermitteln.
Im Rahmen dieser Diplomarbeit wird ein Genetischer Algorithmus aus der Kategorie
Evolutionärer Algorithmen implementiert. Die wesentliche Aufgabenstellung dabei ist es ein
Konzept zu erarbeiten, welches die Haltung und Optimierung von Teilpopulationen
ermöglicht. Aufgrund der Restriktionen seitens SAP ist die Implementierung selbst nicht im
SAP BI möglich, sodass die Implementierung extern erfolgen muss. Durch eine geeignete
Schnittstelle muss der Zugriff auf das Verfahren über den Analyseprozessdesigner(APD)
gewährleistet sein. Die Struktur der zu analysierenden Daten ist bei Clusteranalysen im
Allgemeinen variabel, somit muss die generische Verarbeitung im zu implementierenden
Verfahren ebenfalls gewährleitet sein.
3 | S e i t e
2
Grundlagen
2.1
Clusteranalyse
Das Ziel von Clusteringverfahren ist, eine zu untersuchende Datenmenge in Gruppen
einzuteilen, sodass Daten innerhalb einer Gruppe möglichst ähnlich und Daten verschiedener
Gruppen möglichst unähnlich sind. Abbildung 2-1 zeigt verschiedene Beispiele für
Clusterstrukturen, wobei die Ähnlichkeit zwischen Datenobjekten durch den Abstand der
Punkte dargestellt ist[Est00].
Abbildung 2-1: Beispiel für 2 Dimensionale Clusterstrukturen
Ähnlichkeit zwischen Datenobjekten
Um eine Clusteranalyse durchführen zu können, ist zunächst eine geeignete Modellierung der
Ähnlichkeit zwischen Datenobjekten erforderlich. Dies wird meist durch eine Distanz-
funktion realisiert, die für Paare von Objekten definiert ist. Die Abstände zwischen je zwei
Objekten werden dabei folgendermaßen interpretiert:
o
kleine Distanzen ähnliche Objekte,
o
große Distanzen unähnliche Objekte.
Die Wahl einer konkreten Definition der Distanzfunktion hängt von den Objekten und
der Anwendung ab. Unabhängig von der jeweiligen Form der Funktion müssen aber
mindestens die folgenden Bedingungen für alle Objekte
aus der Menge der
betrachteten Objekte gelten[Est00]:
1.
(
)
2.
(
)
3.
(
) (
) ( )
4 | S e i t e
Die Funktion ist eine Metrik, wenn zusätzlich die Dreiecksgleichung gilt, d.h. wenn für
alle
gilt:
4.
(
) (
) (
)
Distanzfunktion
Die Auswahl einer geeigneten Distanzfunktion hängt vom Datentyp der Objekte und der
Auswahl des Analyseverfahrens ab. Nachfolgend werden einige Distanzfunktionen für
unterschiedliche Datentypen vorgestellt.
1.
Für Datensätze
mit numerischen Attributwerten
:
·
Euklidische Distanz: ( )
(
)
,
·
Manhattan Distanz: ( ) |
|
,
·
Maximums-Metrik: ( ) (|
| |
|),
·
Allg. Lp-Metrik:
( ) (
)
.
2.
Für Datensätze mit
mit kategorischen Attributwerten
:
Anzahl der verschiedenen Komponenten in x und y:
( )
(
)
Wobei (
) {
(
)
(
)
3.
Für endliche Mengen
Anteil der verschiedenen Elemente in x und y: ( )
| | | |
| |
Verfahrensvarianten einer Clusteranalyse
Grundsätzlich lassen sich Clusterverfahren in 4 Kategorien einordnen, partitionierende
Verfahren, hierarchische Verfahren, Neuronale Netze und Optimierungsverfahren.
Gegenstand dieser Diplomarbeit ist der k-means Algorithmus aus der Kategorie
partitionierende Verfahren und Evolutionäre Algorithmen aus der Kategorie
Optimierungsverfahren. Daher werden nur diese beiden Verfahrensvarianten ausführlich
behandelt. Nachfolgend ein kurzer Überblick über die Verfahrensvarianten.
5 | S e i t e
Partitionierende Verfahren
Partitionierende Verfahren zerlegen eine Menge von Objekten zufällig in k Cluster, wobei
jedem Cluster mindestens ein Objekt zugewiesen sein muss und jedes Objekt nur einem
Cluster angehören darf. Im Verlauf des Verfahrens werden nun diese Objekte immer wieder
neu zugeordnet, bis schließlich keine Verbesserung durch Umordnung der Objekte zu
anderen Clustern mehr möglich ist.
Hierarchische Verfahren
Im Gegensatz zu partitionierenden Verfahren erzeugen hierarchische Clusteringverfahren
keine einfache Zerlegung der Datenmenge, sondern eine hierarchische Repräsentation der
Daten, aus der man eine Clusterstruktur ableitet[Est00]. Hierarchische Verfahren lassen sich
in zwei Gruppen gliedern. Bei der ersten Variante geht man von der feinsten Partitionierung
der Ausgangspunkte aus (jedes Objekt ist ein Cluster). Im Laufe des Verfahrens werden nun
die Objekte sukzessiv verdichtet. Die zweite Variante arbeitet genau anders herum, dabei
werden zu Beginn alle Objekte einem Cluster zugeordnet. Im Laufe des Verfahrens wird
dieser Cluster immer wieder aufgeteilt.
Neuronale Netze SOM ( Self Organizing Map )
Die künstlich neuronalen Netze der Kategorie SOM haben sich als sehr leistungsfähiges
Verfahren zur Clusteranalyse herausgestellt. Mit diesen Netzen werden die Ausgangsdaten
unter Beibehaltung der topologischen Eigenschaften auf ein auf das Wesentliche reduziertes
Netz abgebildet[Kie07].
Optimierungsverfahren
Sehr viele Optimierungsverfahren lassen sich für das Clustern von Daten einsetzen. Darunter
befinden sich analytische Verfahren sowie verschieden Evolutionäre Algorithmen, letztere
sind Teil der Diplomarbeit und werden ausführlich in den Folgekapiteln behandelt.
2.2
Partitionierende Verfahren
Partitionierende Clusterverfahren teilen eine Datenmenge n in k Cluster auf unter Beachtung
folgender Restriktionen:
1.
jeder Cluster enthält mindestens ein Datenobjekt.
2.
jedes Datenobjekt gehört genau zu einem Cluster.
Die Ähnlichkeit wird meist durch die Euklidische Distanzfunktion modelliert. Bezogen auf
die Ähnlichkeit bedeutet dies, je kleiner der über die Distanzfunktion ermittelte Abstand,
umso ähnlicher sind sich zwei Datenobjekte. Je größer der Abstand, umso unähnlicher sind
sich zwei Datenobjekte.
6 | S e i t e
Centroide
Ein Cluster wird durch ein sogenanntes Centroid repräsentiert, es stellt den
Clustermittelpunkt dar, um welchen sich die Datenpunkte eines Clusters gruppieren.
Centroide sind bei partitionierenden Clusterverfahren von zentraler Bedeutung, sie fassen
eine Menge von Datenobjekten in Teilmengen zusammen und bilden die Grundlage für die
Gütebestimmung einer Clusteranalyse.
Abbildung 2-2: Beispiel Centroid
Der Centroid
eines Cluster wird folgendermaßen ermittelt:
(
( )
( )
( ))
,
wobei
der Mittelwert der j-ten Dimension aller Punkte in
ist,
ist die Anzahl der Objekte in .
Güte und Kompaktheit eines Clusters
Ziel eines partitionierenden Clusterverfahrens ist es, eine Konstellation aller Datenpunkte zu
finden, in der die Summe aller Abstände (Güte) zu den jeweiligen Clusterzentren
(Centroiden) minimal ist. Die Gütebestimmung eines Clusters allein durch die Summe der
Abstände zum Centroid ist unter Umständen nicht ausreichend, um die optimale
Konstellation aller Datenpunkte zu finden. Abbildung 2-3 verdeutlicht die Kompensierung
eines Ausreißers in einem Cluster durch benachbarte Datenobjekte. Obwohl die Summen der
Abstände beider Cluster gleich sind, ist mit bloßem Auge zu erkennen, dass Cluster 1 eine
bessere Qualität bezüglich der Ähnlichkeit von Datenobjekten aufweist.
7 | S e i t e
Abbildung 2-3: Beispiel Kompaktheit von Clustern
Dieser Qualitätsunterschied lässt sich durch die Kennzahl Kompaktheit in die Güte-
bestimmung miteinbeziehen. Die Kompaktheit eines Clusters wird durch das Quadrieren der
einzelnen Abstände zum Centroid berechnet. Dadurch gehen große Distanzen über-
proportional in die Summenberechnung ein und werden von benachbarten Datenobjekten
nicht mehr so stark kompensiert.
Maß für die Kompaktheit eines Clusters
Summe der quadrierten euklidischen Distanzen zum Centroid:
( )
(
)
.
Beispiel k-means Algorithmus
,K-means ist die bekannteste und am häufigsten angewendete partitionierende Clustering-
Methode` (Ester & Sander, 2000). Wie bereits in der Einleitung erwähnt, basiert das
Clusteringverfahren im SAP BI auf der Grundlage einer Form des k-means Algorithmus,
welcher Firmengeheimnis der SAP AG ist.
Der k-means Algorithmus ist ein iterativ arbeitendes Verfahren, welches eine Menge von
Objekten in k Clustern unter Beachtung der Restriktionen aus Kapitel 2.2.1. aufteilt. Ziel ist
es, die Objektmenge so zu zerlegen, das die Summe der Abstände zu den jeweiligen
Centroiden minimal ist. Meist wird dazu die euklidische Distanzfunktion verwendet. Die
Summe aller Abstände innerhalb eines Clusters stellt seine Güte bzw. Qualität dar. Der
Centroid eines Clusters wird folgendermaßen berechnet:
(
( )
( )
( ) )
,
wobei
( )
.
8 | S e i t e
Arbeitsweise
Eine Clusteranalyse läuft in zwei sich iterativ wiederholenden Schritten ab:
Initiale Zerlegung
Zufällige Zuordnung von Datenobjekten zu Clustern, in der nachfolgenden Abbildung
werden 5 Datenobjekte auf 2 Cluster zufällige verteilt.
Abbildung 2-4: Ablauf k-means I
Schritt 1a
Berechnung der Centroide über den Mittelwert aller Objekte der jeweiligen Cluster (siehe
Centroide 0 )
Abbildung 2-5: Ablauf k-means II
Schritt 1b
Berechnung der Entfernungen der Abstände zu den jeweiligen Centroiden. Die Pfeile
deuten auf näherliegende Clusterzentren(siehe Güte & Kompaktheit 0).
Abbildung 2-6: Ablauf k-means III
9 | S e i t e
Schritt 2
Neuzuordnung aller Datenpunkte zum jeweils nächstliegenden Clusterzentrum.
Abbildung 2-7: Ablauf k-means IV
Terminierung
Schritt 1 bis 2 wird solange wiederholt, bis keine Veränderung durch Umordnung der
Datenobjekte zu anderen Centroiden mehr möglich ist[Est00].
Eigenschaften
·
Konvergiert gegen ein (möglicherweise lokales) Optimum
·
Anzahl der Iterationen ist im Allgemeinen klein
·
Ergebnis und Laufzeit hängen stark von der initialen Zerlegung ab
·
Aufwand O(ndkt), wobei n die Anzahl der Objekte, d die Anzahl der Dimensionen, k
die Zahl der zu findenden Cluster und t die Anzahl der Iterationen darstellt
Der k-means Algorithmus kann die optimale Konstellation von Objekten zu Clustern finden,
muss es aber nicht. Das Verfahren konvergiert nicht zwingend gegen ein globales Optimum,
sondern kann auch gegen ein lokales Optimum konvergieren
.
Im ungünstigsten Fall ist das
Ergebnis einer gegen ein lokales Optimum konvergierten Clusteranalyse unbrauchbar. Die
vorzeitige Konvergenz hängt stark von der Initialisierung der Datenobjekte zu Beginn des
Verfahrens ab. Das Ergebnis ist im Allgemeinen reihenfolgeabhängig, das bedeutet bei
gleicher initialer Zerlegung kann das Resultat unterschiedlich ausfallen. Ist die Initialisierung
ungünstig ausgefallen, besteht die Gefahr der vorzeitigen Konvergenz. Um dem
entgegenzuwirken, gibt es Methoden und Heuristiken, welche die Initialisierung von k-means
verbessern. Es ist anzunehmen, dass der in SAP BI implementierte Algorithmus zur
Clusteranalyse auch in dieser Hinsicht optimiert wurde.
10 | S e i t e
2.3
Evolutionäre Algorithmen
,,Lebewesen sind vollendete Problemlöser. In der Vielzahl der Aufgaben, die sei bewältigen,
übertreffen sie die besten Computerprogramme bei weitem - zur besonderen Frustration der
Programmierer, die Monate oder gar Jahre harter geistiger Arbeit für einen Algorithmus
aufwenden, während Organismen ihre Fähigkeiten durch den scheinbar ziellosen
Mechanismus der Evolution erwerben" (Holland, Evolution, 1992).
Das Zitat von John Holland zielt weniger auf die biologische Evolution, sondern mehr auf
die Idee, durch das Nachahmen evolutionärer Prozesse alternative Verfahren zur Lösung von
Optimierungsproblemen zu beschreiben. Evolutionäre Algorithmen sind eine Kategorie von
Optimierungsverfahren, durch die Problemlösungen automatisch generiert werden, nach dem
Vorbild der natürlichen Evolutionsprozesse. Durch verschiedene Ansätze diese Prozesse
abzubilden, entstanden seit den 1950er Jahren unterschiedliche Modelle. Sie lassen sich in
folgende Untergruppen gliedern:
·
Genetische Algorithmen
·
Evolutionsstrategien
·
Evolutionäres Programmieren
·
Genetisches Programmieren
Die verschiedenen Untergruppen basieren auf einer einheitlichen Terminologie, welche sich
an die Darwin'schen Evolutionstheorie lehnt. Gegenstand dieser Arbeit ist der Genetische
Algorithmus. Aus diesem Grund begrenzt sich die Ausführung über Evolutionäre
Algorithmen lediglich auf diesen Bereich. An dieser Stelle ist anzumerken, dass Evolutionäre
Algorithmen im Vergleich zu anderen Optimierungsverfahren einen größeren Aufwand
bezüglich der Rechenzeit benötigen. Dieser wird bei einfachen Problemstellungen durch die
immer größer werdende Rechnerkapazität kompensiert. Bei umfangreicheren Optimierungs-
problemen ist mit einer entsprechend hohen Laufzeit zu rechnen. Der Vorteil Evolutionärer
Algorithmen besteht in dem vergleichbar geringerem Formalisierungs- oder Modellierungs-
aufwand gegenüber anderen Optimierungsverfahren[Ger04].
Natürliche Evolution
Um einen evolutionär arbeitenden Algorithmus zur Clusteranalyse zu beschreiben, ist es
zunächst erforderlich, sich mit den ursprünglichen, biologischen Begriffen und Konzepten
vertraut zu machen. Die natürliche Evolution hat komplexe Strategien für die Bildung,
Bewahrung und Anpassung von Arten entwickelt. Für die Entwicklung Evolutionärer
Algorithmen genügen jedoch relativ geringe Kenntnisse der biologischen Evolution. Ziel ist
es, sich von den natürlichen Vorgängen inspirieren zu lassen, nicht aber diese möglichst
genau abzubilden. Daher beschränkt sich diese Arbeit nur auf die für die Entwicklung
Evolutionärer Algorithmen notwendigen Begriffe und Konzepte der biologischen Evolution.
11 | S e i t e
Die Fähigkeit der Natur sich durch Adaption an veränderte Umweltbedingungen anzupassen
und die Lösung komplexer Probleme durch das Prüfen einer relativ geringen Anzahl von
Möglichkeiten steht im Fokus dieser Arbeit. Um diese Fähigkeiten in einem Algorithmus
abbilden zu können, werden nachfolgend wichtige Begriffe der Genetik aufgeführt:
Chromosom
Chromosomen enthalten die Erbinformationen von Lebewesen und sind sozusagen die
Baupläne, auf deren Grundlage sich ein Organismus entwickelt. Sie kommen in allen Zellen
von zelltragenden Organismen vor und bestimmen deren Eigenschaften. Die Gesamtheit
aller Chromosomen bildet den kompletten Bauplan für einen Organismus, einzelne
Chromosomen beschreiben jeweils eine Teilmenge seiner Eigenschaften.
Gen
Chromosomen bestehen aus einzelnen, aneinandergereihten Genen, welche wiederum
einzelne Eigenschaften darstellen die ein Organismus haben kann, wie zum Beispiel das
Vorhandensein von Augen, Armen oder Beinen. Gene bilden die Grundlage für die
Vererbung von Informationen.
Allel
Als Allel bezeichnet man die Ausprägung eines Gens, welche sich an einem bestimmten Ort
(Locus) auf einem Chromosom befindet. Gene beschreiben jeweils die Eigenschaften, die ein
Organismus haben kann, wie zum Beispiel Anzahl Arme oder Augen, Allelen sind konkrete
Ausprägungen wie zum Beispiel Augenfarbe blau.
Phänotyp
Der Phänotyp ist das Erscheinungsbild eines Lebewesens, also die Summe aller seiner
Merkmale. Er bezieht sich nicht nur auf die strukturellen Eigenschaften, wie der Form,
sondern auch auf die physiologischen und psychologischen Eigenschaften.
Genotyp
Genotyp oder Erbbild bezeichnet die Gesamtheit aller Gene in einem Organismus. Genauer
gesagt bezieht sich der Genotyp auf die vollständige Kombination aller Allelen, wohingegen
sich der Phänotyp auf die tatsächlichen körperlichen Merkmale bezieht.
Population
Als Population wird eine Menge von Lebewesen gleicher Art bezeichnet, welche sich einen
gemeinsamen Lebensraum zur gleichen Zeit teilen und eine Fortpflanzungsgemeinschaft
bilden. Eine Population wird durch Ausprägung und Gestalt, Häufigkeit und durch
Variationsbreite der Allelen, Genotypen und Phänotypen charakterisiert.
12 | S e i t e
Fitness
Als Fitness wird die Überlebens- bzw. Vermehrungswahrscheinlichkeit eines Lebewesens
bezeichnet, also die Wahrscheinlichkeit, möglichst oft im Genpool der nächsten Generation
vertreten zu sein. Gene von Individuen mit einer hohen Fitness setzen sich im Laufe der Zeit
besser in der Population durch als die derer mit schlechter Fitness.
Generation
Eine Population zu einem bestimmten Zeitpunkt wird als Generation bezeichnet. Eine
Generation ist durch Abstammung mit der vorherigen verbunden und bildet die Grundlage
von Individuen für die jeweils nächste Generation.
Reproduktion
Reproduktion ist die Erzeugung von Individuen durch Kreuzung von Paaren aus einer
Generation. Die erzeugten Kinder sind weitgehend den Eltern ähnlich und bilden die
Grundlage für die nächste Generation einer Population.
Evolutionsfaktoren
Die Ableitung der Evolutionsfaktoren erfolgt aus der Überlegung, unter welchen Umständen
sich die Häufigkeit von Genen in einer Population verändert. Sie bildet ein Teilgebiet der
Genetik und wird als Populationsgenetik bezeichnet[Wei07].
Eine Evolution findet statt, wenn sich die Genfrequenz
1
einer stabilen Population
2
verändert.
Dies kann in den folgenden Fällen eintreten:
1.
Durch Vervielfältigungsfehler können neue Allelen eingeführt werden und diese können
das Verhältnis der Allelen ändern (Mutation).
2.
Durch eine ungleiche Fortpflanzungsrate und/oder Überlebenschancen tritt eine
Veränderung der Genfrequenz ein (Rekombination & Selektion).
3.
In sehr kleinen Populationen kann der zufällige Tod von Individuen das Verhältnis der
Allelen stark beeinflussen (Gendrift).
4.
Das Zu- oder Abwandern von Individuen kann die Genfrequenz ändern (Genfluss).
Mutation
Während der Reproduktion der Erbinformationen können Übermittlungsfehler bei einzelnen
Allelen entstehen. Diese Fehler bei der Kopierung des Erbgutes werden als Mutation
bezeichnet, sie sind Grundlage für Veränderungen in der Evolution. Große Veränderungen in
einer Population finden in der Regel durch Addition vieler kleiner Mutationen statt. Erfolgen
große Veränderungen in einem Schritt, so werden diese schnell aus der Population verdrängt,
1
D
ie Häufigkeit und das Verhältnis der Allelen in einer Population.
2
Unter einer stabilen Population ist das konstante Verhältnis der Allelen auch nach mehreren Generationen zu
verstehen.
13 | S e i t e
da durch Verknüpfung und Wechselwirkung der Gene elementare negative Eigenschaften bei
Großmutationen kaum vermeidbar sind[Wei07].
Rekombination
Durch Paarung zweier Individuen einer Population wird deren genetisches Material neu
kombiniert und erzeugt ein den Eltern weitgehend ähnliches Individuum. Da eigentlich keine
Neuerungen eingeführt werden, sondern nur vorhandenes Genmaterial kombiniert wird,
handelt es sich aus Sicht der klassischen Evolutionstheorie bei der Rekombination um keinen
Evolutionsfaktor. Diese Sicht hat sich inzwischen durch die Erkenntnis der genregulierenden
Netzwerke
3
geändert, und so zählt die Rekombination heute zu den Evolutionsfaktoren. Es
wird angenommen dass der evolutionäre Einfluss der Rekombination weitaus höher ist als
der der Mutation.
Selektion
Unter Selektion als Evolutionsfaktor ist die Veränderung der Allelenhäufigkeit in einer
Population durch unterschiedlich viele Nachkommen zu verstehen. Bei der Selektion
unterscheidet man zwischen Umweltselektion und sexueller Selektion. Ursachen für
Schwankungen der einzelnen Individuen in Tauglichkeit und Reproduktivität können
unterschiedliche Überlebenschancen, zum Beispiel in der Lebensfähigkeit oder dem
Behauptungsvermögen gegen Rivalen oder natürlich Feinde sein. In diesem Fall spricht man
von Umweltselektion. Eine weitere Ursache besteht in der Fähigkeit, Geschlechtspartner zu
finden. Diese variieren bekanntlich bei Individuen und können ebenfalls zur Veränderung der
Genfrequenz einer Population führen. Weitere mögliche Ursachen sind Unterschiede in der
Fruchtbarkeit der Individuen oder unterschiedliche Längen der Generationsdauer. Die
Selektion wird durch den Fitnesswert gemessen. Hierunter ist die Fähigkeit von Genotypen
zu verstehen, möglichst häufig im Genpool der nächsten Generation vertreten zu sein.
Die relative Fitness eines Genotyps G ist über die Anzahl der überlebenden Nachkommen in
einer Population definiert als:
Fitness (G) =
wobei G' der Genotyp mit den meisten Nachkommen in der Population ist[Wei07].
Selektion ist der einzige gerichtete Vorgang in der Natur Die fittesten Individuen jeder
Generation haben bessere Überlebens- und Fortpflanzungschancen nach dem von Darwin
formulierten Prinzip ,,Survival of the fittest". Somit wird der Erhalt gut angepasster Gene
über Generationen hinweg gesichert. Daraus lässt sich allerdings nicht schlussfolgern, dass
sich langfristig nur die vorteilhaftesten Gene durchsetzten. Zu beobachten ist, dass in der
Natur eine gewisse Diversität sich auch über Generationen hinweg erhält.
3
Nach Vorstellung der genregulierenden Netzwerke sind Gene hochgradig voneinander abhängig, weiter wird
angenommen das nur die starke Vernetzung und Verknüpfung in den genotypischen Strukturen viele phänotypische
Merkmale hervorbringen kann[Wei07].
14 | S e i t e
Gendrift
Der evolutionäre Faktor durch Gendrift ist lediglich bei kleinen Populationen
ausschlaggebend. Dabei sterben durch Zufallseffekte Allelen aus und werden, durch das nicht
Vorhandensein ähnlicher Individuen, nicht kompensiert, was eine Veränderung der
Genfrequenz zur Folge hat. Bei großen Populationen wird dieser Effekt durch die Anzahl
ähnlicher Individuen kompensiert, verliert somit also an Bedeutung. Gendrift kann unter
Umständen eine stark beschleunigte Evolution bewirken. Dieser Effekt tritt auf, wenn eine
Population eine Kolonie mit geringer Anzahl Individuen gründet. Diese muss zunächst von
der Mutterpopulation isoliert sein. In dieser kleinen Kolonie kann die Evolution durch
Gendrift und Mutation zunächst völlig andere Wege einschlagen, als es in der großen
Population möglich wäre. Unter den neuen Bedingungen kann sie eventuell in kurzer Zeit
entscheidende Verbesserungen bewirken. Gelangen nun Individuen aus der Kolonie durch
Genfluss in die Mutterpopulation, so kann unter Umständen die gesamte Population davon
profitieren.
Genfluss
Zu- und Abwanderungen von Individuen in Teilpopulation derselben Art können ebenfalls
die Genfrequenz einer Population verändern, sofern die Teilpopulationen örtlich
voneinander getrennt und anderen Umwelteinflüssen unterworfen sind. Dabei passt sich jede
Population den jeweiligen Umweltbedingungen an, wodurch sich der Unterschied in den
ursprünglich gleichen Genfrequenzen erklären lässt. Der Grad des evolutionären Faktors bei
Genfluss hängt nicht nur von der Anzahl der Ab- und Zuwanderungen von Individuen ab. In
örtlich stark getrennten Teilpopulationen können sich Varianten derselben Art bilden, bei
langer Isolation kann sich eine Art in verschiedene Arten aufspalten, welche jeweils
verschiedene Strategien zum Überleben entwickeln. Diese Strategien sind ihrer jeweiligen
Umwelt angepasst, zum Beispiel kann sich eine Art Gift entwickelt haben, womit es sich
gegen bestimmte Raubtiere schützen lässt. Erfolgt diese Veränderung über einen langen
Zeitraum, so wird sich auch die Umwelt der neuen Art anpassen und Gegenstrategien
entwickeln, um das Gleichgewicht zu halten. Findet nun ein plötzlicher Austausch von
Individuen statt, können diese unter Umständen nicht nur die eigene Art sondern auch die
neue Umwelt sehr schnell dominieren. In diesem Fall spricht man von einer Plage. Ein sehr
berühmtes Beispiel ist die Froschplage in Australien. 1935 wurde von den Briten eine
Kolonie von Bufo Marilus Fröschen nach Australien importiert, diese sollten die damals
herrschende Maikäferplage beenden. Durch ihr Gift waren diese Frösche jedoch sehr gut
gegen natürliche Feinde in der neuen Heimat geschützt. Da die Umwelt in der neuen Heimat
keine Zeit hatte Gegenstrategien zu entwickeln, wurden diese Frösche schnell selbst zur
Plage, gegen die Australien heutzutage noch kämpft.
15 | S e i t e
Simulation evolutionärer Zyklen
Um die natürliche Evolution auf Lösung von Optimierungsproblemen anwenden zu können,
ist es zunächst erforderlich, die aus dem vorherigen Kapitel herausgearbeiteten
Evolutionsfaktoren in einem geschlossenen Zyklus darzustellen. Die Idee dabei ist, die
Evolutionsfaktoren als Operationen auf einer Population von Lösungen anzusehen, und
diese in einem Kreislauf mit definiertem Start- und Endpunkt zu integrieren. Abbildung 2-8
verdeutlicht den schematischen Ablauf einer solchen Simulation.
Abbildung 2-8: Schematischer Ablauf evolutionärer Algorithmen
Der Startpunkt wird durch die Initialisierung einer Population mit zufälligen
Lösungskandidaten simuliert. Dabei ist die Größe der Population begrenzt und umfasst in
der Regel 30 100 Lösungskandidaten. Anschließend erfolgt eine Bewertung der Individuen
nach einer Bewertungsfunktion. Diese Funktion ist die Grundlage für die simulierte
Umweltselektion und bestimmt die Qualität eines Lösungskandidaten. In Anlehnung an
natürliche Evolution bezieht sich die Güte eines Individuums in Relation zu anderen
Individuen einer Population, nicht auf ein globales Optimierungskriterium wie bei
herkömmlichen Optimierungsverfahren. Im weiteren Verlauf pflanzen sich ausgewählte
Paare von Individuen fort, wobei die am besten bewerteten Individuen höhere
Auswahlwahrscheinlichkeiten besitzen. Aus der Rekombination erzeugte Kinder werden nun
einer simulierten Mutation unterworfen, welche den natürlich Vorgang der
Übertragungsfehler von Allelen imitiert. Die Rekombination dient in der Regel zur
Durchmischung der Population wogegen die Mutation mit einer geringen Rate zur
Veränderung beiträgt. Ist die Mutationsrate zu hoch angesetzt, so gehen die Eigenschaften
der Eltern gänzlich verloren. Anschließend erfolgt eine Neubewertung der Individuen
inklusiv der erzeugten Kinder. Die Umweltselektion wird durch die begrenzte Größe der
Population simuliert. Dabei wird die Population wieder auf die vorgegebene
Populationsgröße dezimiert, wobei entweder einzelne Individuen aus der Elternpopulation
ersetzt werden oder die komplette Elternpopulation durch die Kinder ersetzt wird. Im ersten
16 | S e i t e
Fall lässt sich der Selektionsdruck durch die Anzahl der zu erzeugenden Kinder einstellen: je
mehr Kinder pro Generation erzeugt werden umso höher ist der Selektionsdruck. Im zweiten
Fall kann der Selektionsdruck durch bestimmte Strategien indirekt beeinflusst werden. Am
Ende jeder Iteration wird geprüft, ob die Terminierungsbedingung erfüllt ist. Es gibt
verschiedene Ansätze für Terminierungsbedingungen. Dabei kommt die Anzahl der
Iterationen in Frage oder die Verweilzeit des Verfahrens. Denkbar ist auch die Erreichung
einer bestimmten Güte des besten Individuums oder die Konvergenz einer Generation gegen
ein Optimum. Auch eine Kombination aus den genannten Möglichkeiten ist denkbar.
Formale Grundlagen
Optimierungsproblem
Um ein Optimierungsproblem zu formulieren muss zunächst ein Suchraum spezifiziert
werden. Dieser setzt sich aus der Menge aller möglichen Lösungen zusammen. Jede Lösung
muss eine eindeutig berechenbare Güte oder Qualität aufweisen, damit Lösungskandidaten
verglichen werden können.
Definition 2.1 (Optimierungsproblem):
Ein Optimierungsproblem (, f, ) ist gegeben durch einen Suchraum , eine
Bewertungsfunktion f:
, die jedem Lösungskandidaten eine Güte zuweist, sowie eine
Vergleichsrelation {<>}. Dann ist die Menge der globalen Optima
definiert als:
= { |
: f ( ) f (
) }.
Dekodierungsfunktion
,,Für jedes beliebige Optimierungsproblem können Lösungskandidaten unterschiedlich
dargestellt werden und dadurch jeweils andere Operationen in effizienter Zeit ermöglichen.
Daher trennen wir die natürliche Struktur des Suchraums , den so genannten Phänotypen,
von der Darstellung des Lösungskandidaten in einem Individuum, den so genannten
Genotypen G." (Weicker, 2007).
Definition 2.2 (Dekodierungsfunktion)
Eine Dekodierungsfunktion dec: G
ist eine Abbildung vom Genotypen G auf den
Phänotypen , wobei die Bewertungsfunktion gemäß Definition 2.1 auf dem Phänotypen
und die Mutation sowie die Rekombination auf den Genotypen formuliert ist.
17 | S e i t e
Abbildung 2-9: Zusammenspiel Genotyp, Phänotyp und Dekodierungsfunktion
Abbildung 2-9 verdeutlicht das Zusammenspiel zwischen dem Genotyp, dem Phänotyp und
der Dekodierungsfunktion. Anzumerken ist, dass eine solche Funktion lediglich dann
benötigt wird wenn der Genotyp kodiert werden muss um darauf genetischer Operanden
ausführen zu können. Das ist zum Beispiel dann der Fall, wenn die Operanden auf binärer
Basis arbeiten, dann muss ein reellwertiger Genotyp entsprechend umgewandelt werden.
Diese Umwandlung führt dann die entsprechende Dekodierungsfunktion durch.
Individuum
Ein Individuum besteht aus dem Genotyp, welcher nach der Dekodierung seine
phänotypischen Informationen erhält, und aus seiner Güte. Falls Zusatzinformationen(Z) für
ein Verfahren notwendig sind, kann die Struktur des Individuums entsprechend angepasst
werden. Nachfolgend eine beispielhafte, dreistrukturierte Definition für ein Individuum:
Definition 2.3 (Individuum)
Ein Individuum A ist ein Tupel (A.G, A.S, A.F) bestehend aus dem Lösungs-
kandidaten(Genotyp) A.G G, den Zusatzinformationen A.S Z und dem Gütewert A.F
f:( dec ( A.G ) ) .
Abbildung 2-10:Schematische Darstellung Individuum
Operatoren
Der Mutationsoperator für einen Genotyp G wird durch folgende Abbildung
: G
Z
G
Z
definiert, wobei E
einen Zustand des Zufallsgenerators darstellt.
18 | S e i t e
Analog wird der Rekombinationsoperator mit r
2 Eltern und s
1 Kindern (r, s )
durch folgende Abbildung definiert:
: (
)
(
)
Der Selektionsoperator wird auf eine Population P =(
, ...,
) angewandt.
: (
)
(
)
( )
(
(
) )
mit
( )
= (
).
Die dabei zugrundeliegende Indexselektion hat die Form:
:
r
,...,
1
.
Nachfolgende Abbildung veranschaulicht anhand eines Beispiels wie die Selektion auf die
Indexselektion zurückgeführt wird.
:
{
Abbildung 2-11:Demonstration Selektion/Indexselektion
19 | S e i t e
3
Clusteranalyse auf Basis eines
Genetischen Algorithmus
Durch seine Fähigkeit, große Suchräume systematisch zu durchsuchen, eignet sich der
Genetische Algorithmus besonders gut zur Clusteranalyse. Die Suchräume bei
Clusterproblemen haben in der Regel einen exponentiellen Charakter, woraus sich eine sehr
große Menge von möglichen Lösungen ergibt. Der Genetische Algorithmus ist in der Lage,
durch das Probieren von relativ wenigen Lösungen ein breites Feld des Suchraumes nach der
optimalen Lösung zu durchsuchen. Diese Fähigkeit basiert zum Einen auf der Haltung einer
Menge von möglichen Lösungen (Population), zum Anderen auf der Anwendung genetischer
Operanden auf dieser Menge, welches das gleichzeitige Suchen in verschiedene Richtungen
ermöglicht, sowie verschiedene Strategien um zum Beispiel der vorzeitigen Konvergenz
4
entgegenzuwirken. Ausschlaggebend für die Designentscheidung ist jedoch die Flexibilität der
Genetischen Algorithmen bezüglich der Problemstellungen. So ist im Rahmen dieser
Diplomarbeit nicht nur ein Algorithmus zum Clustern von Daten zu implementieren, dieser
soll dazu noch parallel die optimale Clustermenge ermitteln. Durch Erweiterung des
Populationskonzepts um die der Teilpopulationen
5
besteht die Möglichkeit verschieden
dimensionierte Lösungen
6
zu einem Clusterproblem in derselben Population zu halten.
Durch den Einsatz einer Kostenfunktion lassen sich wiederum die Teilpopulationen in ihrer
Güte gewichten, sodass parallel zum Clustern der Daten das Individuum mit der optimalen
Clustermenge als bestes Individuum der Gesamtpopulation am Ende des Verfahrens
ausgegeben wird. So kann die Fähigkeit des Genetischen Algorithmus in verschiedene
Richtungen im Suchraum suchen zu können, ausgedehnt werden, um nicht nur Lösungen in
einem Lösungsraum zu suchen, sondern in mehreren. Nachfolgend werden in Kapitel 3.1 die
Grundlagen Genetischer Algorithmen sowie deren Prinzipien und verschiedene Strategien
zur Effizienzsteigerung behandelt.
3.1
Genetischer Algorithmus
Charakteristisch für Genetische Algorithmen sind im Wesentlichen das Populationskonzept,
die Rekombination als primärerer Suchoperator, die Mutation als Hintergrundoperator und
eine probabilistische Elternselektion. Grundsätzlich lassen sich zwei Grundalgorithmen
unterscheiden: der sogenannte Standard GA ersetzt am Ende jeder Generation die
Elternpopulation komplett durch die Kindindividuen. Im Gegensatz dazu arbeitet der
sogenannte Steady-State GA mit überlappender Population, welches immer nur ein
Individuum pro Generation erzeugt und gegebenenfalls ein Individuum aus der Population
verdrängt. Abbildung 3-1 führt schematisch die verschiedenen Abläufe der
Verfahrensvarianten vor.
4
Unter vorzeitiger Konvergenz ist das konvergieren einer Population gegen ein nur lokales Optimum zu verstehen.
5
Verschiedene Arten(Teilpopulationen) welche einen Lebensraum teilen, also Gesamtheit aller Teilpopulationen.
6
Unter Dimension eines Clusterproblems ist die Anzahl der Cluster einer Lösungsart zu verstehen.
20 | S e i t e
Abbildung 3-1:Unterschiedlicher Ablauf Standard GA & Steady-State GA
Beim Standard GA Verfahren erfolgt zunächst die sexuelle Selektion auf Basis der Fitness der
Individuen. Diese bestimmt auch, wie viel Kinder ein Individuum zeugen darf, also wie oft
der Rekombinationsoperator pro Generation auf das jeweilige Individuum angewandt wird.
Die Anzahl der zu zeugenden Kinder muss gleich dem der Elterngeneration sein, diese wird
anschließend gänzlich von der Kindergeneration ersetzt. Beim Steady-State GA erfolgt die
sexuelle Selektion ebenfalls auf Grundlage der Fitness, allerdings wird jeweils nur ein
Elternpaar ausgewählt, dieses zeugt zwei Kinder und das bessere Kind ersetzt ein Individuum
aus der Elterngeneration, zum Beispiel das Individuum mit der schlechtesten Fitness aus der
Generation t-1. Die beiden Verfahrensvarianten unterscheiden sich lediglich in den Abläufen.
Sämtliche genetische Operationen sowie die Fitnessbestimmung können auf beide Varianten
gleichermaßen angewandt werden. Die theoretische Grundlage für Genetische Algorithmen
bildet das von Holland[Hol94] entwickelte Schema Theorem, in welchem die Auswirkungen
der Selektion und der genetischen Operatoren Crossover und Mutation auf die in einer
Population vertretenen Schemata untersucht werden.
Wechselspiel zwischen Variation & Selektion
Das Wechselspiel zwischen Variation und Selektion ist als Prinzip Genetischer Algorithmen
zu verstehen. Durch das Kreuzen von Individuen und die Mutation werden immer neue
Lösungsvarianten hervorgebracht. Die Selektion hat die Aufgabe, der simulierten Evolution
eine Richtung vorzugeben, indem schlechte Individuen von guten ersetzt werden, sodass im
Laufe des Verfahrens die Population im günstigsten Fall gegen ein globales Optimum
konvergiert. Um ein globales Optimum zu erreichen, reicht es jedoch nicht aus, nur gute
Lösungen zu produzieren und schlechte Lösungen zu verdrängen, es muss auch eine gewisse
Diversität in der Population möglichst lange aufrecht erhalten werden. Verfolgt man lediglich
die Strategie, nur gute Lösungen zu produzieren und schlechte Lösungen aus der Population
zu entfernen, wird die Gefahr des lokalen Optimums stark erhöht, sodass die Population
nicht das globale Optimum erreicht. Grund dafür ist, dass die Güte von Individuen relativ zu
anderen Individuen der Population beurteilt wird, also nicht nach einem globalen Kriterium.
Folglich muss das beste Individuum in einer Generation nicht der optimalen Lösung
entsprechen. Bei der Strategie immer bessere Lösungen auf Basis lokal guter Individuen zu
21 | S e i t e
produzieren, werden eben diese Individuen überproportional bei der sexuellen Selektion
begünstigt, sodass nach wenigen Generationen die Kinder dieser lokal guten Individuen die
gesamte Population dominieren. Anschließend konvergiert die Population im ungünstigsten
Fall gegen ein sehr schlechtes, lokales Optimum. Um dem entgegenzuwirken ist es
notwendig, die Diversität möglichst lange aufrecht zu erhalten, sodass auch schlechte
Lösungen, mit einer vielleicht geringeren Paarungswahrscheinlichkeit, als gute Lösungen in
den Selektionsmechanismus mit einbezogen werden. Durch diese Strategie ist es möglich,
lokalen Optima zu entkommen, indem unter Umständen die Kreuzung zwischen einem guten
und einem schlechtem Individuum zu einer wesentlichen Verbesserung führt und somit die
Population aus einem lokalen Optimum ausbricht. Ziel also ist es, diese teilweise
gegenläufigen Strategien - Produzieren immer besserer Individuen und Erhalt von Diversität
- harmonisch zu verbinden, sodass das Ausbrechen aus lokalen Optima möglich wird und das
Erreichen zumindest hinreichend guter Lösungen gewährleistet ist.
Populationskonzept
Eine Population besteht aus einer Menge von Lösungskandidaten (Individuen gemäß
Definition 2.3), welche in der Initialisierungsphase zufällig generiert werden. Sinn und Zweck
der Haltung vieler Lösungsmöglichkeiten ist das gleichzeitige Absuchen des Lösungsraumes
an verschiedenen Stellen. Das Populationskonzept ermöglicht im Allgemeinen die breite
Erforschung des Lösungsraumes, die dabei möglicherweise auftretenden Schwierigkeiten
wurden im vorherigen Abschnitt kurz erläutert. Darüber hinaus ermöglicht erst das
Populationskonzept die Einführung der Rekombination als weiteren Suchoperator. Es
existieren Evolutionäre Algorithmen, die ohne eine Population auskommen. Dabei wird
versucht, ein zufällig generiertes Individuum nur durch verschiedene Mutationsoperatoren so
nah wie möglich an ein globales Optimum heranzuführen.
Diversität
Die Haltung einer Menge von Lösungskandidaten allein reicht für die breite Erforschung des
Suchraumes nicht aus. Dies wird erst durch die Menge an verschiedenen Lösungen innerhalb
einer Population möglich. Diese Analogie zur natürlichen Vielfalt ermöglicht die breite
Erforschung des Suchraumes, es gilt, je vielfältiger eine Population, desto breiter kann der
Suchraum erforscht werden und je ähnlicher Individuen sind, desto kleiner wird der
erreichbare Lösungsraum innerhalb einer Population. Wie bereits in vorherigen Abschnitten
erwähnt, ist es ein grundlegendes Prinzip populationsbasierter Algorithmen, die Diversität
möglichst lange aufrecht zu erhalten.
Definition 3.1 (Diversität)
Als Maß für die Diversität einer Population wird der mittlere Abstand der Individuen
definiert, sei Population
zu den Genotypen
gegeben,
.
wobei
ein beliebiges Abstandmaß ist
22 | S e i t e
Konvergenz
Konvergenz hat bezüglich Evolutionärer Algorithmen zwei unterschiedliche Bedeutungen.
Zum einen ist darunter die mathematische Konvergenz, also die Annährung der Gütewerte
gegen ein lokales oder globales Optimum gemeint und zum anderen ist darunter der Verlust
der Vielfalt in einer Population zu verstehen.
Definition 3.2 (Konvergierte Population)
Population
heißt konvergiert, sobald alle seine Individuen identisch sind, d.h.
für alle gilt
.
Das Problem der vorzeitigen Konvergenz gegen ein lokales Optimum wurde bereits
angesprochen, es ist eines der großen Probleme bei Evolutionären Algorithmen. Es entsteht
immer, wenn das Optimum nicht in der Population enthalten ist und die Bewertung für die in
der Population enthaltenen Vertreter
einer suboptimalen Lösung über dem Durchschnitt
liegt
[Ger04]
. Um dem entgegenzuwirken wurden eine Reihe von Strategien, Verfahren und
genetische Operanden entwickelt, welche die Diversität in einer Population künstlich
hochhalten. Grundsätzlich muss dabei ein Gleichgewicht zwischen dem breiten
Durchsuchen des Lösungsraumes und der Weiterentwicklung guter, in der Population
vorkommender Individuen gefunden werden. Nachfolgend einige Beispiele für Diversität
erhaltende Operatoren
[Ger04]
:
Fitnessteilung
Die Fitness eines Individuums wird in Abhängigkeit von seiner Ähnlichkeit zum Rest der
Population berechnet.
Verbot von Inzest
Rekombination wird nur zwischen Individuen durchgeführt deren Ähnlichkeit über
einem Schwellenwert liegt, wobei dieser Schwellenwert mit der Zeit sinkt.
Populationsabhängige Selektion
Kindindividuen werden nur übernommen, wenn sie noch nicht in der Population
vorkommen, bzw. alte Individuen werden nach einer bestimmten Generationsanzahl aus
der Population entfernt.
Fitnessfunktion
Die Fitnessfunktion dient der Beurteilung von Individuen innerhalb einer Genration. Anhand
des Fitnesswertes werden die Fortpflanzungs- sowie die Überlebenswahrscheinlichkeit
ermittelt. Sie entspricht der Zielfunktion eines Optimierungsproblems. Die grundlegende
Idee dabei ist, Individuen einer Generation relativ zueinander zu bewerten. Die Bewertung
jedes Individuums erfolgt dabei auf Basis des Individuums mit dem schlechtesten Gütewert
7
einer Generation. Nachfolgende Tabelle führt eine beispielhafte Berechnung der Fitness
sowie der Auswahl- und Überlebenswahrscheinlichkeit vor.
7
Bei Clusterverfahren bezieht sich die Güte auf die Summe der Distanzen aller Cluster innerhalb einer
Lösungsmöglichkeit.
23 | S e i t e
Beispielhafte Berechnung des Fitnesswertes:
Im obigen Beispiel dient Individuum 5 mit dem schlechtesten Gütewerten als Basis der
Berechnung. Die Fitness eines Individuums c ist somit der Güteabstand zum Individuum 5.
Die Auswahl- und Überlebenswahrscheinlichkeit für jedes Individuum erhält man durch den
Quotienten des jeweiligen Fitnesswertes und der Summe der Fitnesswerte einer Generation.
Der daraus resultierende p-Wert kann sowohl für die sexuelle Selektion als auch für die
Umweltselektion benutzt werden. Nachfolgend werden einige Varianten zur Bestimmung des
Fitnesswertes vorgestellt.
Linear Skalierte Fitness
1989 stellten Greffenstette und Baker die grundlegende Skalierungsformen in der folgenden
Definition für Maximierungsprobleme vor.
Definition 3.2 (Linear skalierte Fitness)
Sei
:
·
Lineare statische Skalierung[Gre89]:
·
Lineare dynamische Skalierung:
|
Exponentielle Skalierung
Die exponentielle Skalierung ist eine Erweiterung der Linearen Skalierung, welche zusätzlich
populationsabhängige Faktoren berücksichtigt. Der Hintergedanke dabei ist, Individuen mit
guter Fitness überproportional zu berücksichtigen.
Definition 3.3 (Exponentiell skalierte Fitness)
Sei
und
einer reellwertige Funktion.
·
Exponentielle Skalierung[Gol89,Gre89]:
Individuum (c)
Güte
Fitness(c)
p(c)
1
5
10
0.33
2
7
8
0.26
3
8
7
0.23
4
10
5
0.16
5
15
0
0
30
1
Tabelle 3-1: Beispiel Fitnessberechnung
24 | S e i t e
Geteilte Fitness(Fitness Sharing)
Geteilte Fitness ist eine Technik, um der vorzeitigen Konvergenz und dem Diversitätsverlust
bei fortschreitendem Generationsverlauf entgegenzuwirken. Die Grundidee dabei ist, die
Fitness von Individuen abhängig von ihrer Ähnlichkeit nachträglich zu modifizieren, damit
isolierte Individuen einen Evolutionsvorteil und viele ähnliche Individuen einen
Evolutionsnachteil bekommen. Dabei wird zunächst die Fitness auf herkömmlichen Weg
berechnet, anschließend erfolgt eine Modifizierung durch eine Funktion. Die Ähnlichkeit
wird als Abstand der Individuen
berechnet, und durch eine ,,Sharing"-Funktion
(
)
in das Intervall [0,1] abgebildet. Dabei gilt, je größer die Ähnlichkeit, desto
höher sollte der Sharing-Wert sein. Die Fitness ergibt sich dann aus:
Der unter dem Bruchstrich stehender Anteil wird als ,,Nischenzähler" bezeichnet,
nachfolgende Funktion wurde von Goldberg und Richardson vorgeschlagen[Gol87]:
(
) { (
)
ist die Distanz zwischen 2 Individuen
bestimmt die Form der Sharing Funktion
Nur innerhalb des Radius wird die Fitness beeinflusst
Die Einbeziehung der Sharing-Funktion in die Fitnessberechnung kann die Diversität in einer
Population länger aufrechterhalten und somit das gründliche Durchsuchen des
Lösungsraumes begünstigen. Nachteilig ist jedoch der relativ große Aufwand. Da jedes
Individuum mit jedem Individuum verglichen werden muss, ist der zusätzliche
Rechenaufwand quadratisch zur
Populationsgröße je Runde.
Selektionsmechanismen
In Analogie zur natürlichen Evolution unterscheidet man bei Evolutionären Algorithmen
zwischen der Umwelt- und Paarungsselektion. Die Aufgabe der Umweltselektion besteht in
der Aufrechterhaltung eines Gleichgewichtes zwischen einer Population und dessen Umwelt.
Dabei sterben in jeder Generation eine bestimmte Anzahl Individuen durch Umwelteinflüsse,
meist sind das ältere, schwache, kranke oder schlecht angepasste Individuen. Simuliert wird
dieser Vorgang bei Genetischen Algorithmen auf Grundlage des im Kapitel Fitnessfunktion
beschriebenen Fitnesswertes. Der Fitnesswert ist das Beurteilungskriterium für die Selektion,
pro Generation wird dabei eine Menge von Individuen ausgesondert. Je besser der
Fitnesswert eines Individuums ist, desto höher stehen seine Chancen der Umweltselektion
nicht zum Opfer zu fallen. Ziel der Umweltselektion ist es, eine möglichst große Vielfalt in
der Population zu erhalten, und dabei das Überleben der besten Individuen zu sichern.
Grundsätzlich gibt es hierbei zwei mögliche Möglichkeiten: die reine Auswahl der besten
Individuen und die zufällige Auswahl, wobei Individuen mit besseren Fitnesswerten eine
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Erscheinungsjahr
- 2010
- ISBN (eBook)
- 9783842802995
- DOI
- 10.3239/9783842802995
- Dateigröße
- 2.4 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Hochschule Fulda – angewandte Informatik, Studiengang Wirtschaftsinformatik
- Erscheinungsdatum
- 2010 (August)
- Note
- 1,7
- Schlagworte
- data mining sap-bi clusteranalyse evolutionäre algorithmen genetischer algorithmus
- Produktsicherheit
- Diplom.de