Design, Implementierung und Analyse einer clusterbasierten Datenanalyse mit Hilfe evolutionärer Algorithmen in SAP BI

Diplomarbeit von Hüseyin Bostanci

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 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.

Inhaltsverzeichnis:

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.