Inhaltsverzeichnis

1  Einleitung  1

1.1  Markenwechselverhalten und Loyalität  1

1.2  Der Begriff der sequentiellen Muster  2

1.3  Ziele und Aufbau der Arbeit  3

2  Die Sequenzanalyse in der Marketingforschung  5

2.1  Definitionen  5

2.2  Sequential Pattern Mining  8

2.3  Basisalgorithmen nach Agrawal und Srikant.  10

2.4  Ausgewählte Weiterentwicklungen  13

2.4.1  GSP  13

2.4.2  PrefixSpan  14

2.5  Web-Usage Mining  17

3  Analyse von Kaufhistorien mit einem modifizierten Assoziationsregelalgorith-  

mus   19

3.1  Probleme und Aufgaben des Ansatzes  19

3.2  Theoretische Betrachtungen  20

3.3  Modifizierter Apriori-Algorithmus  23

3.4  Ein Loyalitätsmaß für Switching Regeln  27

3.5  Kodierung der Kaufhistorien mit Promotionsmaßnahmen  29

4  Modellierung des Markenwechselverhaltens mittels Markov-Ketten  35

4.1  Motivation und Überblick  35

4.2  Definitionen und Merkmale von Markov-Ketten  36

4.3  Modellprämissen  40

4.4  Markov-Modelle höherer Ordnung  42

II

4.5  Weiterentwicklungen  45

5  Empirische Betrachtungen  46

5.1  Datenbeschreibung und Voranalyse  46

5.2  Implementierung des Apriori-Algorithmus  49

5.3  Generierung der Switching-Regeln  51

5.4  Ergebnisse der empirischen Analysen  52

5.5  Aspekte des Markov-Modells  56

5.5.1  Test auf Stationarität  57

5.5.2  Test auf Ordnung des Markenwahlprozesses  58

5.6  Implementierung des Markovmodells  58

5.7  Vergleichende Betrachtung  62

6  Abschließende Betrachtungen  64

Literaturverzeichnis   66

Anhang 71   

III

Abbildungsverzeichnis   

Abbildung  2.1: AprioriAll-Algorithmus (Quelle: Agrawal, Srikant (1995, S. 7))  

Abbildung  2.2: Ergebnisse des AprioriAll-Algorithmus (Quelle: Agrawal (1995, S. 10))  

Abbildung  3.1: Modifizierter Apriori-Algorithmus (Quelle: Säuberlich (2000, S. 178))  

Abbildung  3.2: Häufige Itemmengen des modifizierten Apriori-Algorithmus für Kauffolgen (Eige-  

ne  Erstellung)  

Abbildung  3.3: Generierte Switching Regeln (Eigene Erstellung)  

Abbildung  3.4: Häufige Teilfolgen des modifizierten Apriori-Algorithmus für Kauffolgen mit Ko-  

dierung  der Werbemaßnahmen (Eigene Erstellung)  

Abbildung  3.5: Switching-Regeln für Kauffolgen mit Kodierung der Werbemaßnahmen (Eigene  

Erstellung  )  

Abbildung  3.6: Häufige Teilmengen des modifizierten Apriori-Algorithmus für Kauffolgen mit  

Kodierung  der Werbemaßnahmen (Eigene Erstellung)  

Abbildung  3.7: Switching-Regeln für Kauffolgen mit Kodierung der Werbemaßnahmen (Eigene  

Erstellung  )  

Abbildung  4.1: Übergangsmatrix (Quelle: Meffert, Steffenhagen (1977, S. 103))  

Abbildung  4.2: Übergangsmatrix (Eigene Erstellung)  

Abbildung  4.3: Berechnung Käuferanteile in Periode t 2 (Eigene Erstellung)  

Abbildung  4.4: Periodenspezifische Fluktuationsmatrizen F 2 , , F 6 (Eigene Erstellung)  

Abbildung  5.1: Switching-Regeln für Kauffolgen (Eigene Erstellung S min 20)  

Abbildung  5.2: Switching-Regeln für Kauffolgen mit beworbener Marke I (Eigene Erstellung)  

Abbildung  5.3: Fuktuationsmatrix F bei Periodenlänge von einem Monat (Eigene Erstellung)  

Abbildung  5.4: Übergangsmatrix P bei der Periodenlänge von einem Monat (Eigene Erstellung)  

Abbildung  5.5: Fuktuationsmatrix F bei einer Periodenlänge von 2 Monaten (Eigene Erstellung)  

Abbildung  5.6: Übergangsmatrix P mit der Periodenlänge von 2 Monaten (Eigene Erstellung)  

IV

Tabellenverzeichnis

Tabelle 2.1: Transaktionsdatenbank sortiert nach Kunden-ID und Transaktionszeit (Eigene Erstellung). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

Tabelle 2.2: Kundensequenzen (Eigene Erstellung). . . . . . . . . . . . . . . . . . . . . . 7

Tabelle 2.3: Ergebnisse einer Sequenzanalyse (Eigene Erstellung). . . . . . . . . . . . . . . 8

Tabelle 2.4: Itemmengen der Litemsetphase (Eigene Erstellung). . . . . . . . . . . . . . . . 9

Tabelle 2.5: Transformierte Datenbank (Eigene Erstellung). . . . . . . . . . . . . . . . . . 10

Tabelle 2.6: Kundensequenzen nach Mapping (Quelle: Agrawal, Srikant (1995, S. 9)). . . . . . 12

Tabelle 2.7: Sequenzdatenbank (Quelle: Pei et al. (2001, S. 217)). . . . . . . . . . . . . . . 16

Tabelle 2.8: Projezierte Datenbank und sequentielle Muster (Quelle: Pei et al. (2001, S. 219)). . . 16

Tabelle 2.9: Sequentielle Muster für a projezierte Datenbank (Eigene Erstellung). . . . . . . 17

Tabelle 4.1: Käuferwanderung (Eigene Erstellung) . . . . . . . . . . . . . . . . . . . . . 38

Tabelle 4.2: Individuelle Kaufhistorien (Eigene Erstellung). . . . . . . . . . . . . . . . . . 43

Tabelle 4.3: Aggregierte Fluktuationsmatrix (Eigene Erstellung). . . . . . . . . . . . . . . . 44

Tabelle 4.4: Übergangsmatrix P (Eigene Erstellung). . . . . . . . . . . . . . . . . . . . . 44

Tabelle 5.1: Teilmärkte der Warengruppe Fenster-/Teppich/WC-Reiniger (Eigene Erstellung). . . 47

Tabelle 5.2:Marktanteile der untersuchten Marken (Eigene Erstellung). . . . . . . . . . . . . 48

Tabelle 5.3: Zahl der Haushalte und die Mindestanzahl der Kaufakte (Eigene Erstellung). . . . . 49

Tabelle 5.4: Support-Werte des ersten Schrittes (Eigene Erstellung). . . . . . . . . . . . . . 50

Tabelle 5.5: Häufigkeiten (S 3 ) des zweiten Schrittes (S min ≥ 20) (Eigene Erstellung). . . . . . 50

Tabelle 5.6: Kodierung beworbener Marken (Eigene Erstellung). . . . . . . . . . . . . . . . 54

Tabelle 5.7: Kontingenztafel zum χ ² -Stationaritätstest ( Quelle: Röhle, Wagner, Decker (1998, S. 4)). 57

V

Kapitel 1

Einleitung

1.1 Markenwechselverhalten und Loyalität

Im Hinblick auf eine steigende Wettbewerbsintensität und vermehrt auch die von den Kunden empfundene Austauschbarkeit der Marken, kommt dem Aufbau von Markenloyalität als Ziel eines jeden Unternehmen eine zentrale Bedeutung zu. Im strategischen Marketing Management wird Kundenloyalität als ein fundamentales Konzept (vgl. Wernerfelt (1991, S. 229)) und sogar als ein Vermögenswert (vgl. Aaker (1984, S. 140)) betrachtet. Der Aufbau langfristiger Geschäftsbedingungen und in besonderer Weise zufriedene Kunden sind primäre Ziele der Marketingmanager. Um diesem anspruchsvollen Ziel gerecht zu werden, müssen sowohl loyale Käufer und ihre Größe entdeckt als auch deren Eigenschaften sowie die Reaktionen auf Marketing-Mix Variablen untersucht werden (vgl. Sharp, Sharp (1997, S. 473)). Anknüpfend daran ist es nicht uninteressant auch die Abwanderung eigener Kunden zu untersuchen (vgl. Bass (1974, S. 1)).

Im Bereich der Konsumentenverhaltensforschung ist der hohe Stellenwert der Analyse des Markenwechselverhaltens unbestritten. Besonders die Analyse der durch den Einsatz von Marketingaktivitäten induzierten Markenwechsel und daraus resultierende Marketingstrategien, sind die am meisten in der Fachliteratur diskutierten Problemstellungen (vgl. Allenby, Rossi (1991, S. 185), Carpenter, Lehmann (1985, S. 1) und Herrmann, Gutsche (1992, S. 63)). Nach den Überlegungen zahlreicher Autoren wird das Markenwechselverhalten oder besser gesagt die Markenwechselneigung als ein Bedürfnis aufgefasst, zwischen verschiedenen Marken zu wechseln (vgl. Lattin, McAlister (1985, S. 330), Jeuland, Bass, Wright (1980, S. 255)). McAllister (1982, S. 141) bemerkt zum Markenwechsel: „Switching can be induced by the manipulation of marketing Variables, by the accessability of the product, by

1

the situation in which the product is consumed or by the desire of variety”, was die Tatsache der mehrdimensionalen Entscheidung eines Konsumenten für ein gewisses Produkt untermauert (vgl. Kroeber-Riel (1992, S. 160). Auf der anderen Seite wird in der Fachliteratur dem Begriff der Markenloyalität eine zentrale Rolle in der Konsumentenverhaltensforschung konstatiert (vgl. Jacoby, Chestnut (1978, S. 1-6). Dieser Begriff wird jedoch in der Literatur oft unterschiedlich beschrieben. Mowen und Minor (1997, S. 435) sehen die Markenloyalität als: „ the degree to which the customer holds a positive attitude toward a brand, has a commitment to it, and intends to continue purchasing in the future”.

1.2 Der Begriff der sequentiellen Muster

Ausgehend von der Betrachtung der ständig wachsenden Menge gespeicherten Daten, wird in der modernen Datenverarbeitung nach Verfahren gesucht, welche die bisher in den Daten verborgenen Informationen extrahieren. Dieser Prozeß wird in der Fachliteratur als KDD-Prozeß bezeichnet (vgl. Säuberlich (2000, S. 7-9).

Die Sequenzanalyse oder im englischen sequential pattern mining basiert auf dem Prozeß des KDD und ist ein Verfahren, um in zeitbezogenen Daten häufig auftretende Muster zu entdecken, und diese Informationen zur Entscheidungsunterstützung in unterschiedlichen Wissenschaftsbereichen zu nutzen ¹ . In der Fachlitertur wird die Sequenzanalyse, wie auch das Time-series-mining und das Web-log mining zu dem „zeitlichen” Data Mining oder im englischen Time-related data mining eingeordnet. Die Sequenzanalyse und die mit ihr einhergehenden Algorithmen unterschiedlichster Form, wurden durch die pionierhafte Arbeit der Autoren Agrawal und Srikant 1994 eingeführt (vgl. Agrawal, Srikant (1995, S. 3-14 )). Die Basis eines solchen Verfahrens bilden die von großen Handelsunternehmen durch moderne Kassensysteme gesammelte Daten. Durch den in den letzten Jahren immer häufigeren Einsatz von Kunden-und Kreditkarten lassen sich die getätigten Transaktionen direkt den Kunden zuordnen, wodurch Aussagen über das Konsumentenverhalten gemacht werden können (vgl. Hippner et al. (2001, S. 441)).

Sequenzanalysen untersuchen also Kundentransaktionen mit dem Ziel, die zeitlichen Beziehungen berücksichtigen und häufige Sequenzen als Muster entdecken zu können (vgl. Han

¹ Im Kontext der Medizin wäre eine Datensequenz eine sortierte Aufzeichnung von Arztbesuchen eines Patienten. In dieser sind dann beispielsweise Symptome und Diagnosen gespeichert. Der Nutzen von sequen-

tiellen Mustern liegt vor allem im Auffinden von Symptomen und Diagnosen, die anderen Diagnosen zeitlich

vorangehen.

2

et al. (2000, S. 355)). Diese Kaufmuster geben Auskunft darüber, welche Produkte oder Dienstleistungen von einer bestimmten Kundengruppe in einem Zeitraum nachgefragt werden. Ein solches sequentielles Muster wäre z.B die Nachfrage eines Kunden nach Produkt A, dann nach Produkt B und schließlich nach C. Besonderer Beachtung bedarf die Tatsache, dass es unbedeutend ist, ob der Kunde zwischen diesen Käufen andere Produkte erworben hatte ² . Insofern wird die Sequenzanalyse für die Fragestellungen der Warenkorbanalyse interessant, da die Informationen aus der Sequenzanalyse in die Assoziationsanalyse einge-bunden werden, mit dem Ziel den Aussagegehalt deutlich zu erhöhen. Auch im Bereich der Logfile-Analyse kann die Anwendung der Sequenzanalyse erfolgen (vgl. Hettich, Hippner, Wilde (2000, S. 976)).

1.3 Ziele und Aufbau der Arbeit

Die vorliegende Diplomarbeit ist insgesamt in sechs Kapitel gegliedert. Das erste Kapitel soll den Leser in die Hauptproblemstellungen, nämlich das Markenwechselverhalten und Loyalität, sowie den Begriff der sequentiellen Muster einführen. Dieses Kapitel dient zur Abgrenzung zentraler Begriffe und der Positionierung der Schwerpunkte dieser Arbeit. Das zweite Kapitel behandelt detailliert die Problematik der Sequenzanalyse in der Marke-tingforschung. Dabei wird zuerst auf die dieser Methode zugrundeliegenden Definitionen eingegangen und gleichzeitig anhand von selbsterstellten Beispielen die Verdeutlichung und Interpretationsmöglichkeiten von sequentiellen Mustern im Marketing angestrebt. Im Anschluss daran liegt der Focus auf dem Aufbau und der Vorgehensweise bei einer Sequenzanalyse. Hier werden die verschiedenen Phasen dieser begleitet von Beispielen aufgezeigt. Die von Agrawal zur Generierung von sequentiellen Mustern in Kundendatenbanken entwickelten Basisalgorithmen bilden die eigentlichen Methoden der Sequenzanalyse. Die Ausführungen hierzu haben das Ziel der korrekten Darstellung und Verdeutlichung der so genannten Sequenzphase, welcher die größte Bedeutung in der Sequenzanalyse beigemessen wird. Darüber hinaus werden ausgewählte Weiterentwicklungen und neue Algorithmen aus der Fachliteratur präsentiert, wobei die Auswahl der dargestellten Verfahren nach der Einsetzbarkeit im Marketing erfolgt. Ein ganz neuer Ansatz, nämlich der PrefixSpan-Algorithmus wird detailliert dargestellt. Das Hauptanliegen besteht hier in der Präsentation der Möglichkeiten und der Entwicklung des Forschungsgebietes des sequential pattern mining. Schlußendlich wird die Einsetzbarkeit und der Nutzen der Sequenzanalyse verknüp-

² WeitereBeispiele für sequentielle Muster befinden sich z.B bei Agrawal, Srikant (1995, S. 4).

3

fend bei Fragen des web-log mining thematisiert.

Das dritte Kapitel stellt das Hauptkapitel dieser Diplomarbeit dar. Dabei handelt es sich um ein Verfahren zur Analyse von Kaufhistorien mit Hilfe eines modifizierten Apriori-Algorithmus. Zuerst wird der Ansatz anhand von Definitionen detailliert vorgestellt. Begleitend durch ein Beispiel wird dem Leser der modifizierte Apriori-Algorithmus, seine Funktionsweise und der mit ihm verbundene Aufbau von so genannten Switching-Regeln präsentiert. Das Ziel dieser Ausführungen liegt in der Darstellung und Erklärung des Verfahrens mit Hilfe von generierten Beipielen. Im Anschluss an diese Ausführungen wird ein Loyalitätsmaß für die generierten Switching-Regeln dargestellt. Den Abschluss dieses Kapitels bildet eine neue Idee der Einbindung beworbener Marken in die Analyse von Kaufhistorien, was einer Weiterentwicklung des modifizierten Verfahrens gleichkommt. Es werden zwei Beispiele generiert, an denen die Grundidee veranschaulicht werden soll. Kapitel 4 widmet sich der Modellierung des Markenwechselverhaltens anhand von Markov-Ketten. Gegenstand der Betrachtung ist zuerst die einschlägige Literatur zum Ansatz der Markov-Ketten, um einen Einstieg in die Thematik zu bekommen. Ausführlicher wird dann auf die eigentliche Modellierung eingegangen, wobei wieder anhand von Beispielen die theoretischen Zusammenhänge veranschaulicht werden. Besonderes Gewicht erfahren die Prämissen des Ansatzes und die Modellierung von Markov-Ketten höherer Ordnung. Mit ausgewählten Weiterentwicklungen zur Thematik der markovschen Übergangsstrukturen endet dieses Kapitel.

Die Ausführungen im Kapitel 5 widmen sich der empirischen Untersuchungen. Eine ausführliche Datenbeschreibung und Voranalyse stehen einführend für dieses Kapitel. Der vorgestellte Apriori-Algorithmus wird nachfolgend implementiert. Darüber hinaus erfolgt eine Beschreibung der Generierung von Switching-Regeln sowie die Darstellung und Interpretation der empirischen Analyse. Bevor mit der Implementierung und der Vorstellung der Ergebnisse des Markovmodells begonnen wird, werden wichtige Aspekte des Markovmodells dargestellt, nämlich die Stationarität und Ordnung des Markenwahlprozesses. Ausklang findet dieses Kapitel mit einer vergleichenden Betrachtung der Erkenntnisse aus den empirischen Ergebnissen der Untersuchungen.

Das letzte Kapitel fasst die Ergebnisse der Diplomarbeit nochmal zusammen und gibt einen Ausblick in Bezug auf die angesprochene Thematik.

4

Kapitel 2

Die Sequenzanalyse in der

Marketingforschung

Gegenstand der Betrachtungen dieses Abschnittes ist die Sequenzanalyse bezogen auf die Anwendung in der Betriebswirtschaftslehre und speziell im Bereich des Marketing. Exemplarisch wird die Vorgehensweise und die Methodik sowie Weiterentwicklungen bei einer Sequenzanalyse vorgestellt.

2.1 Definitionen

Um dem Problem der Erkennung zeitlich-sequentieller Assoziationen gerecht zu werden, müssen im Vorfeld einer Sequenzanalyse einige unabdingbare Definitionen Berücksichtigung finden. Die wohl wichtigste Voraussetzung ist das Vorhandensein geeigneter Eingabedaten. Diese benötigen zum einen ein zeitliches Ordnungskriterium der Transaktionen, zum anderen ein weiteres Bezugsobjekt, das im Kontext der Warenkorbanalyse, eine für die in der berücksichtigten Zeit getätigte Transaktion verantwortliche Person darstellt. Im Rahmen der Sequenzanalyse gelten folgende Definitionen (vgl. Agrawal, Srikant (1995, S. 3)): Definition 2.1: (Datenbasis)

Gegeben sei eine Datenbasis D aus Kundentransaktionen, wobei jede Transaktion eine Kundenidentifikation, Transaktionszeit und die in der Transaktion erworbene Itemmenge ¹ enthält. Kein Kunde kann mehrere Käufe mit der identischen Transaktionszeit aufweisen. Es werden keine Quantitäten von Käufen berücksichtigt, lediglich die Tatsache des Kaufes oder Nicht-Kaufes.

¹ Eine Itemmenge besteht aus einer nichtleeren Menge von Items. Items können erworbene Produkte darstellen.

5

Als nächstes muss der Begriff einer Sequenz deutlich gemacht werden. In diesem Fall wird diese Kundensequenz genannt. In ihr sind alle Transaktionen eines Kunden zusammengefasst (vgl. Hippner et al. (2001, S. 442)). Definition 2.2: (Sequenz)

Eine Sequenz ist definiert als eine geordnete Liste von Itemmengen. Eine Itemmenge wird mit i bezeichnet, wobei i = (i 1 , i 2 , ..., i m ) gilt. Die Elemente i j der Itemmenge i stellen die einzelnen Items dar. Als Sequenz s ist die Menge < s 1 , s 2 , ..., s n > definiert. Die Elemente s j bezeichnen die Itemmengen. In einer Sequenz s werden die Itemmengen aller Transaktionen eines Kunden durch den Index der Transaktionszeit T 1 , T 2 , ..., T n in aufsteigender Form angeordnet.

Bevor mit der Analyse der eben definierten Sequenzen begonnen werden kann, ist eine Definition der Subsequenz unabdingbar (vgl. Agrawal, Srikant (1995, S. 3)). Damit soll gelten: Definition 2.3: (Subsequenz)

Eine Sequenz < a 1 , a 2 , ..., a n > ist in einer anderen Sequenz < b 1 , b 2 , ..., b n > enthalten, ² . falls ganze Zahlen i 1 < i 2 <, ..., < i n existieren, so dass a 1 ⊆ b ⁱ 1 , a 2 ⊆ b ⁱ 2 , ..., a n ⊆ b ⁱⁿ Nachdem der Zusammenhang der Sequenzen untereinander definiert worden ist, kann nun der Begriff eines sequentiellen Musters aufgestellt werden. Definition 2.4: (Sequentielle Muster)

Sequentielle Muster sind Sequenzen, welche in keiner anderen Sequenz enthalten sind. Diese Sequenzen bezeichnet man dann als maximal.

Letztendlich fehlt noch die Definition eines aus der Assoziationsanalyse bekannten Begriffes, nämlich des Supports einer Sequenz (vgl. Hippner et al. (2000, S. 977)). Definition 2.5: (Support)

Der Support einer Sequenz ist der Anteil der Kunden, die eine Sequenz unterstützen, im Verhältnis zur Grundgesamtheit aller Kunden. Die Unterstützung einer Sequenz s basiert darauf, dass eine andere Kundensequenz in s enthalten ist. Agrawlal und Srikant (1995, S. 4) bemerken zum Ziel der Sequenzanalyse: „Given a database D of customer transactions, the problem of mining sequential patterns is to find the maximal sequences among all sequences that have a certain user-specified minimum support. Each such maximal sequence represents a sequential pattern”.

² Einige Zahlenbeispiele zur Verdeutlichung dieses Sachverhaltes befinfen sich z.B bei Hippner et al. (2001, S. 442).

6

Anhand eines kleinen Beispieles sollen nun kurz die eben vorgestellten Definitionen verdeutlicht werden. Allgemein wird verkürzt der Ablauf einer exemplarischen Sequenzanalyse gezeigt. Der kritische Supportfaktor (minsup) beträgt hier beispielhaft 25%. Beispiel 2.1:

Ausgangspunkt einer Sequenzanalyse sind die durch Handelsunternehmen gesamelten Kun-deninformationen in Form einer Datenbank. Diese enthält die jeweilige Kundenidentifikation, den Zeitpunkt der Transaktion sowie die gekauften Produkte (Items). Tabelle 2.1 zeigt eine solche Datenbank.

Tabelle 2.1: Transaktionsdatenbank sortiert nach Kunden-ID und Transaktionszeit (Eigene Erstellung).

Wichtig für das Verfahren der Sequenzanalyse ist der Aufbau einer solchen Datenbank. Die Zugehörigkeit einer Kundenidentifikation zu einer im gewissen Zeitpunkt durch einen Kunden verursachten Transaktion ist erkennbar. Die Produktkennung in der letzten Spalte berücksichtigt keine Quantitäten der gekauften Items, sondern steht lediglich zur Kodierung dieser. Eine so konstruierte Datenbank wird bei der Suche nach sequenziellen Mustern zunächst in so genannte Kundensequenzen transformiert. Tabelle 2.2 veranschaulicht die sich aus der in Tabelle 2.1 gegebenen Datenbank ergebende Kundensequenzen.

Gemäß Definition 2.2 erhält man Kundensequenzen, die in aufsteigender Form aufgestellt sind. Beispielsweise besteht die Sequenz des dritten Kunden aus dem Kauf der Produkte (90 50 40) zum Zeitpunkt T 1 und (30) bei T 2 . Bei einer vom Anwender vorgegebe-

7

nen Support-Schranke (in diesem Fall 25%) erhält man die maximalen Sequenzen, welche gleichzeitig die gesuchten sequentiellen Muster darstellen ³ . Das sequentielle Muster (10) (20) wird unterstützt von den Kundensequenzen 1 und 2, wohingegen das zweite Muster (90 40) (30) den Support seitens Kunde 3 und 4 erhält. Die Tatsache, des Kaufes der Produkte (30 70) zwischen (10) und (20) bei Kunde 2, ändert nichts am Festhalten des sequentielen Musters (10) (20).

Aus der Tabelle 2.2 und 2.3 lässt sich ableiten, dass

• 40% der Kunden das Produkt mit der Kennung 10 und dann das Produkt 20 kaufen (Kunde 1 und 2).

• 40% der Kunden die Produkte 90 und 40, dann das Produkt 30 kaufen (Kunde 3 und 4).

In diesem speziellen Beispiel ist das Auftauchen der Sequenz (40) (30) interessant. Diese scheint den Support von 25% zu erfüllen, kann jedoch nicht maximal sein, denn (40) (30) ist im sequentiellen Muster (90 40) (30) enthalten.

Bereits aus diesem kleinen Beispiel ist die vielfältige Anwendbarkeit der Sequenzanalyse in der Betriebswirtschaftslehre erkennbar. Besonders große Handelsunternehmen können durch das extrahierte Wissen aus den gesammelten Daten, Rückschlüsse auf das eigene Bestellwesen verbunden mit der Lagerhaltung und den enormen Ersparungen sowie effizienten Auslastung in diesem Bereich ziehen.

2.2 Sequential Pattern Mining

Nachdem nun die Problematik und die Aufgaben der Sequenzanalyse behandelt worden sind, kommt es in diesem Abschnitt auf die Durchführung einer solchen Analyse mit entsprechenden Techniken. Das Finden von sequentiellen Mustern mittels geeigneter Algorithmen steht im Vordergrund dieser sogenannten Sequenzgenerierung. Der Generierungsprozeß dieser Sequenzen wird in der Fachliteratur in 5 Phasen unterteilt (vgl. Agrawal, Srikant (1995, S. 5)).

³ Die Ergebnisse dieses kleinen Beispieles ergeben sich durch den sukzessiven Vergleich der Sequenzen. Die Anwendung von Algorithmen zu dieser Problematik wird später thematisiert.

8

1. Die Sortierungsphase

Die erste Phase der Sequenzgenerierung basiert, wie der Name schon andeutet, auf einer Sortierung der vorhandenen Datenbasis. Diese wird analog zum Beispiel 2.1 in eine Kundensequenzdatenbank konvertiert. Der erste Bezugspunkt in der Datenbank besteht aus der Kundenidentifikation, also der Kundennummer. Im Anschluss daran wird nach der Transaktionszeit sortiert. Erst in dieser neu entstandenen Datenbank kann von Kundensequenzen, in aufsteigender Transaktionszeit angeordnet, gesprochen werden.

2. Die Litemsetphase

Als Litemset wird ein Itemset bezeichnet, das die anwenderbezogene Supportschranke erfüllt. Der Support eines Itemsets i ist definiert als der Anteil der Kunden, welche die Items in irgendeiner Transaktion in i gekauft haben ⁴ .

Die Aufgabe dieser Litemset Phase besteht darin, alle häufigen Litemsets L zu entdecken. Bei der Bestimmung der häufigen Litemsets wird zuerst nach den häufigen Mengen der Sequenzen der Länge 1 gesucht ⁵ . Diese Menge ist definiert als :

{{l | l ∈ L} (2.1)

Für die im Beispiel 2.1 dargestellten Kundensequenzen ergeben sich für die Litemsets:

3. Die Transformationsphase

In der Transformationsphase werden die in den Kundensequenzen auftretenden Transaktionen (Itemsets) durch die in ihnen vorkommenden häufigen Itemmengen ersetzt. Es entsteht eine neue transformierte Datenbasis. Falls eine Transaktion keinen Litemset enthält, so wird sie nicht in die transformierte Sequenz übernommen. Ähnlich wird auch bei einer Kundensequenz verfahren. Falls diese keine Litemsets beinhaltet, wird sie aus der transformierten Datenbasis entfernt. Eine Kundensequenz wird dann in einer transformierten Datenbasis D T als eine Liste von Litemses präsentiert. Die Sequenz wird dargestellt durch {l 1 , l 2 , ..., l n }, wobei l i ein Litemset ist. Im konkreten Beispiel sieht die Transformation folgendermaßen aus:

⁴ Die Definition des Supports unterscheidet sich von der üblichen Definition der Assoziationsanalyse insofern, dass der Support nur einmal pro Kunde gezählt wird (vgl. Hippner et al. (2001, S. 443)).

⁵ Die Länge einer Sequenz ist definiert als die Menge der in ihr enthaltenen Itemsets.

9

Die Kundensequenz 2 (10) (30 70) (20) ist beispielsweise durch die in der Sequenz enthaltenen häufigen Litemsets {(10)} {(30)} {(20)}} ersetzt worden.

4. Die Sequenzphase

Im Rahmen der Suche nach sequentiellen Mustern, wird der Sequenzphase die größte Bedeutung beigemessen. Die Aufgabe dieser Phase besteht aus der Ermittlung der gesuchten Sequenzen mit Hilfe der häufigen Itemmengen (vgl. Hippner et al. (2001, S. 443)). Hierzu wurden von Agrawal und Sriknat 1994 die ersten Algorithmen auf diesem Gebiet, nämlich der CuontAll und CountSome-Algorithmus, entwickelt (vgl. Agrawal, Srikant (1995, S. 7)). Bis heute sind im Rahmen der Forschungsarbeiten auf diesem Feld unzählige neue Algorithmen entstanden. Deshalb beschäftigt sich das komplette nächste Kapitel mit ausgewählten Algorithmen aus der bisherigen nationalen, wie internationalen Forschung.

5. Die Maximalphase

In der letzten Phase erfolgt die Ermittlung der maximalen Sequenzen. In manchen Algorithmen wird jedoch die Maximalphase mit der Sequenzphase verknüpft.

2.3 Basisalgorithmen nach Agrawal und Srikant.

In diesem Kapitel soll auf die von Agrawal und Srikant entwickelten Algorithmen näher eingegangen werden. Ein Algorithmus, nämlich der AprioriAll wird detailliert diskutiert und anhand eines Beispieles verdeutlicht. Die übrigen Basisalgorithmen sind im Rahmen dieser Arbeit nicht ausführlich behandelt und erfahren daher lediglich einer kurzen Erwähnung. Der AprioriAll-Algorithmus basiert auf dem in der klassischen Assoziationsanalyse entwickelten Apriori-Algorithmus (vgl. z.B. Agrawal et al. (1996, S. 312)). Die vorbereiteten Daten werden von so genannten multiplen Pässen durchlaufen, wobei jeder Pass mit einem Anfangsbestand an großen Sequenzen beginnt und als Bestand der Kandidatensequenzen

10

genannt wird. Während eines jeden Durchlaufes wird gleichzeitig der Support der Kandidatensequenzen bestimmt. Das Ziel ist hierbei herauszufinden, welche der Sequenzen aktuell zu den großen gehören (vgl. Agrawal, Srikant (1995, S. 7)). Abbildung 2.1 zeigt den AprioriAll Algorithmus. Interessant ist in diesem Zusammenhang die Generierung der Kandidatensequenzen in Zeile 4 der Abbildung 2.1. Dazu wird, wenn auch modifiziert, die schon früher bekannte und in Anwendungen der Assoziationsregeln verwendete Apriori-gen-Funktion verwendet (vgl. Bollinger (1996, S. 259)).

L k bezeichnet in diesem Algorithmus die Menge von allen großen k-Sequenzen, wobei C ^k die Menge der generierten Kandidaten aus L k−1 darstellt. Im Grunde genommen wird bei diesem Verfahren, mit Ausnahme feiner Modifikation analog wie in der Anwendung der Assoziationsregeln verfahren. Im Rahmen der Generierung der Kandidatensequenzen bei der Sequenzanalyse werden Elemente mit der Verkettung, d.h. bei denen die k − 2 ersten Elemente identisch sind, zu einer neuen Itemmenge zusammengesetzt. Nach dieser Operation werden solche Sequenzen, für die eine k − 1 elementige Teilsequenz nicht häufig ist, aussortiert. Darüber hinaus sind diese nicht in L k−1 enthalten. Der Unterschied zur traditionellen Assoziationsanalyse liegt daran, dass die Elemente der Kandidatensequenzen nicht in aufsteigender Reihenfolge angeordnet sind ⁶ . Anhand des folgenden Beispieles soll zum besseren Verständnis kurz das Vorgehen der Generierung vorgestellt werden. Beispiel 2.2:

Gegeben sei folgende, nach der Transformationsphase konvertierte ⁷ , Datenbank der

⁶ Dazu vergleiche die Ausführungen und Beispiele zur Generierung von Kandidatensequenzen von Agrawal, et al. (1996, S. 313) und Agrawal, Srikant (1995, S. 7).

⁷ Die Zahlen 1 bis 5 stellen die Items dar, da 5 unterschiedliche Items zur Auswahl stehen. Diese Vorgehensweise wird auch Mapping genannt.

11

Kundensequenzen:

Tabelle 2.6: Kundensequenzen nach Mapping (Quelle: Agrawal, Srikant (1995, S. 9)).

Der anwendungsbezogene Support liegt in diesem Fall bei 40%. Nach der Anwendung des AprioriAll Algorithmus ergeben sich die Mengen der vier Durchläufe L 1 -L 4 .

Abbildung 2.2: Ergebnisse des AprioriAll-Algorithmus (Quelle: Agrawal (1995, S. 10))

Abbildung 2.2 zeigt die vier Durchgänge des AprioriAll-Algotithmus. Am Ende eines jeden Durchlaufes erhält man die häufigen Sequenzen, welche die vordefinierte Supportgrenze erfüllen müssen. Es gibt keinen fünften Durchlauf, da es keine weitere Sequenz der Länge vier außer 1 2 3 4 gibt, deren k − 2 Elemente identisch sind und diese zu den häufigen Sequenzen zählen würde. In diesem Moment beendet der Algorithmus seine Arbeit. Die maximalen Sequenzen in diesem Beispiel sind : 1 2 3 4 , 1 3 5 und 4 5, da sie gemäß Definition 2.3 nicht in anderen Sequenzen enthalten sind. Jede dieser Sequenzen repräsentiert das gesuchte sequentielle Muster.

Der hier vorgestellte AprioriAll Algorithmus gehört zu der Familie der CountAll Algorithmen, welche alle häufigen Sequenzen ermitteln.

Eine zweite Art der von Agrawal und Srikant entwickelten Algorithmen sind die so genannten CountSome Algorithmen, bei denen die Sequenzphase und die Maximalphase zusammengefügt werden. Die CountSome Familie ⁸ versucht sich sofort auf die Ermittlung der maximalen Sequenzen zu konzentrieren, wobei mit der Überprüfung der langen Sequenzen begonnen wird. Falls die langen Sequenzen häufig sind, verzichten die Algorithmen auf die

⁸ Hierzu gehören die Algorithmen AprioriSome und DynamicSome. Näheres dazu findet man z.B. bei Agrawal, Srikant (1995, S. 8-10).

12

Entdeckung von Teilsequenzen (vgl. Hippner et al. (2001, S. 443)). Dies ermöglicht vielleicht eine effiziente Ermittlung der häufigen langen Sequenzen, bringt aber den Nachteil, dass vielleicht nicht maximale häufige Sequenzen, die interessant für die Interpretation sein dürften, nicht sofort ermittelt werden.

2.4 Ausgewählte Weiterentwicklungen

Selbstverständlich sind die von Agrawal und Srikant entdeckten Algorithmen bis zum heutigen Tag verbessert und eine große Menge an neuen Algorithmen mit der Forschungsrichtung des „sequential pattern mining” entwickelt worden. In diesem Kapitel der Diplomarbeit soll dem Leser der aktuelle Forschungsstand auf dem Feld der Sequenzanalyse und ihr Einsatz für Fragen des Marketing, präsentiert werden. Die Auswahl der Algorithmen erfolgte grundsätzlich nach der Einsetzbarkeit im Marketing und der Aktualität in der Fachliteratur.

2.4.1 GSP

Der behandelte Algorithmus ist die erste Weiterentwicklung auf dem Gebiet des „sequential pattern mining” und wurde, abgeleitet von „Generalized Sequential Patterns”, 1995 von den Entwicklern Agrawal und Srikant GSP genannt. Die Erweiterungen dieses Algorithmus liegen auf drei Ebenen und heben somit die Begrenzungen der früheren Forschung auf diesem Feld zum Teil auf (vgl. Srikant, Agrawal (1996, S. 4)). Die erste ist die Einführung von Zeitrahmen, in dem sich das gesuchte sequentielle Muster befinden muss. Speziell für die Anwendung im Marketing ist die erweiterte Funktionalität nützlich, denn der Anwender eines sequentiellen Verfahrens erweckt vielleicht das Interesse, dass die Kaufmuster in einem gewissen zeitlichen Abstand auftreten. Außerdem ist es aus der Sicht von Marketingfachleuten uninteressant, wenn zwischen den in den Kaufmustern auftretenden Transaktionen ein großer Zeitraum vergeht. Ein Musterbeispiel mit Anwendung eines Zeitrahmens könnte lauten :

„Wenn eine Person ein Produkt A kauft, so wird sie innerhalb der nächsten drei Monate Produkt B kaufen”.

Die zweite wesentliche Verbesserung ist die Einführung von Taxonomien. Anwender könnten unter Umständen daran interessiert sein, bei Annahme einer vorgegebenen Taxonomie in der Datenbasis, sequentielle Muster auf verschiedenen Ebenen der Taxonomie zu entdecken. Aus marketingtechnischer Sicht lassen sich hier Beziehungen der einzelnen Produkte in Pro-

13

dukthierarchien festhalten und eine verbesserte Visualisierungsform als bei traditionellen Mustern anführen (vgl. Srikant, Agrawal (1996, S. 4)).

Die dritte Erweiterung besteht in der Lockerung der rigiden Definition einer Transaktion im Ansatz der Sequenzanalyse (vgl. Hippner et al. (2001, S. 443)). Die Bedingungen einer Transaktion werden insofern gelockert, dass die Itemmengen in einem sequentiellen Muster nicht aus einer einzelnen Transaktion bestehen muss, solange die Transaktionszeiten in einem bestimmten Zeitfenster (sliding Time window) liegen (vgl. Srikant, Agrawal (1996, S. 4)). Durch diese Aufhebung der harten Restriktion, kann beliebig nach der anwenderorientierten Definition des Zeitfensters, Mustererkennung betrieben werden. Der GSP Algorithmus ist von der Struktur dem im letzten Kapitel behandelten AprioriAll ähnlich. Begonnen wird wie immer mit der der häufigen Itemmengen der Länge 1 (L 1 ). Danach erfolgt die Generierung der Kandidatensequenzen der Länge 2 (C 2 ), wobei der Support sofort ermittelt wird und die neue Menge L 2 entsteht. Allgemein werden die Kandidatensequenzen (C k ) der Länge k in der Join Phase der großen Sequenzen der Länge k − 1 aus L k−1 ermittelt. Die Generierung der Kandidaten erfolgt dadurch, dass bei einer Sequenz s ¹ das erste Item und einer anderen Sequenz s 2 das letzte Item „abgeschnitten” wird. Wenn die durch das Abschneiden entstandene Subsequenz bei beiden Sequenzen s 1 und s 2 identisch ist, so werden die beiden Sequenzen verknüpft, indem die s 1 mit dem letztem Item aus s ² erweitert wird (vgl. Srikant, Agrawal (1996, S. 11)). Die anschließende Prune Phase sortiert die Sequenzen mit einem niedrigerem Support als Suppmin aus. Dies geschieht solange bis keine weitere Generierung möglich ist. Die vorgestellten Erweiterungen des AprioriAll Algorithmus stellen im Grunde genommen neue Bedingungen dar, um sequentielle Muster zu erhalten und Anwendbarkeit für neue Fragestellungen zu finden. Die Grundstruktur der Algorithmen bleibt jedoch erhalten ⁹ .

2.4.2 PrefixSpan

Eine bedeutende Weiterentwicklung auf dem Gebiet des „sequential pattern mining” ist der im Jahre 2001 erforschte PrefixSpan Algorithmus. PrefixSpan (Prefix-projected Sequential pattern mining), der nicht die Methodik und Struktur der Apriori basierten Ansätze in sich verbirgt, sondern einen komplett neuen Ansatz liefert, setzt an der Kritik und den Schwie-

⁹ Kritikdes GSP besteht in der riesigen Menge der zu generierenden Kandidatensequenzen, in der Erfordernis vieler Datendurchläufe und in den Schwierigkeiten des Umgangs mit langen sequenziellen Mustern

(vgl. Pei et al.(2001, S. 216)). Diesen begegnet der 1998 von Masseglia entwickelte PSP Algorithmus (vgl.

Masseglia, Cathala, Poncelet (1998, S. 176-184)).

14

rigkeiten des Apriori basierten GSP Algorithmus an (vgl. Pei et al. (2001, S. 216)). Dennoch ist es ein neues Verfahren der sequentiellen Mustergenerierung. Bei der Entwicklung dieses Verfahrens spielte der im Jahre 2000 entstandene FreeSpan Algorithmus eine nicht unwesentliche Rolle. Dieser beschäftigte sich erstmals mit der aufwendigen Generierung der Kandidatensequenzen bei den Apriori Verfahren (vgl. Han et al. (2000, S. 355)) und setzte somit den Anstoß zur einer raschen Bewegung in der Erforschung eines neuen Verfahrens ¹⁰ . Die grundlegende Idee des PrefixSpan Algorithmus liegt in der Projektion der Sequenzdatenbanken bei der Betrachtung aller möglichen Auftritte von häufigen Subsequenzen. Außerdem basiert diese Projektion nur auf häufigen, sogenannten Präfixen, um den Algorithmus effizient zu gestalten (vgl. Pei et al. (2001, S. 218)). Die Idee soll nun anhand einer theoretischen Grundlage und eines Beispieles verdeutlicht werden. Definition 2.6: 1. Gegeben sind zwei Sequenzen α = e 1 e 2 , ..., e n und β = e m wobei 1 e 2 , ..., e

(m ≤ n) gilt. Die Sequenz β ist nur dann ein Präfix von α, falls:

• e i = e i für (i ≤ m − 1), • e m ⊆ e m , • alle Items in (e m − e m ) alphabetisch angeordnet sind nach Items in e m .

2. Gegeben sind die Sequenzen α und β, so dass β eine Subsequenz von α ist (β ⊆ α).

der Sequenz α (α ⊆ α) wird eine Projektion von α im Bezug Eine Subsequenz α auf β genannt, falls:

ein Präfix β hat, • α von α eine Subsequenz von α ist vorhanden ist, so dass α • keine Sequenz α und ein Präfix β hat.

= e 1 e 2 , ..., e n von α im Bezug auf das Präfix 3. Gegeben sei die Projektion α

β = e 1 e 2 , ..., e m−1 e m , wobei (m ≤ n) gilt.Die Sequenz γ = e m e m+1 , ..., e n m = (e m − wird Postfix in Bezug auf Präfix β genannt. Dabei gilt γ = α/β, mit e

e m ).

Beispielsweise sind a, aa, a(ab) und a(abc) Präfixe der Sequenz a(abc)(ac)d(cf ). Dagegen ist (abc)(ac)d(cf ) Postfix der Sequenz a(abc)(ac)d(cf ) (vgl. Pei et al. (2001, S. 218).

¹⁰ Die Vorgehensweise sowie Beispiele, Ausführung und Vergleich des FreeSpan mit GSP befinfden sich bei Han et al. (2000, S. 355-359).

15

Nach der Definition der Hauptbegriffe des PrefixSpan Verfahrens, wird anhand eines kleinen Beispieles versucht kurz die Vorgehensweise ¹¹ zu verdeutlichen. Gegeben sei nun die zu verwendende Datenbasis S mit einer Sequenzidentifikation und den zugehörigen Sequenzen.

Der PrefixSpan Algorithmus beginnt seine Arbeit mit einem Durchlauf der Datenbank mit dem Ziel der Bestimmung aller häufigen Sequenzen der Länge 1. Die miminale Supportgrenze ist auf 2 gesetzt, wobei die in der Datenbank auftretenden Items aus der Menge { a , b , c , d , e , f , g } bestehen. Die durch den ersten Durchlauf ermittelten Itemsets sind in der Form Item : Support angegeben. Es ergibt sich a : 4 , b : 4 , c : 4 , d : 3 , e : 3 , f : 3. In dem nächsten Durchlauf des Algorithmus wird die gegebene Datenbank S in der Weise aufgeteilt, dass die projezierten Datenbanken die häufigen Itemsets als ein Präfix benutzen. Veranschaulicht wird dieses durch Tabelle 2.8.

Tabelle 2.8: Projezierte Datenbank und sequentielle Muster (Quelle: Pei et al. (2001, S. 219)).

Zuerst werden sequentielle Muster entdeckt die als Präfix ein a besitzen, so dass nur die a enthaltenden Sequenzen generiert werden. Im Zuge dieser Generierung werden nur die nach dem Präfix auftauchenden Items berücksichtigt, was beispielsweise bei der gegebenen Sequenz a (abc) (ac) d, (cf ) zum Ergebnis (abc)(ac)d(cf ) hat. Das erste Item a wird in der projezierten Datenbasis für die Suche nach sequentiellen Mustern nicht berücksichtigt.

¹¹ Auf eine ausführliche Beschreibung der einzelnen Phasen und weiterführender Definitionen wird hier bewusst verzichtet.Sie befinden sich bei Pei et al.(2001, S. 218-219)

16

Analog wird mit dem Präfix b-f verfahren. Beim Durchlaufen der a projezierten Datenbasis bestimmt der Algorithmus dann die sequentiellen Muster der Länge 2, wobei gleichzeitig auch der Support errechnet wird (vgl. Pei et al. (2001, S. 219)). Im konkreten Beispiel ergeben sich sequentielle Muster : aa, ab, (ab), ac, ad, af , welche den Support von 2 erfüllen. Im nächten Schritt wird jedes sequentielle Muster mit dem Präfix a in 6 Untergruppen aufgeteilt, nämlich mit dem Präfix aa dann mit dem Präfix ab usw.. Tabelle 2.9 zeigt die sich ergebende Gruppierung.

Tabelle 2.9: Sequentielle Muster für a projezierte Datenbank (Eigene Erstellung).

Analog zu dieser Vorgehensweise behandelt man alle Elemente a bis f und ermittelt die sequentielen Muster für diese Datenbasis S ¹² . Die Vorteile des PrefixSpan liegen in der Tatsache, dass keine Kandidatensequenzen gebildet werden müssen und der immer kleiner werdenden projezierten Datenbasis. Auf der anderen Seite müssen immer projezierte Datendanken ermittelt werden, was als Nachteil des Algorithmus ausgelegt werden kann (vgl. Pei et al. (2001, S. 220)). Dennoch sollte die Überlegenheit gegenüber den Apriori-Algorithmen aufgrund empirischer Studien anerkannt werden. Außerdem ist es für die Forschung in diesem Bereich nicht uninteressant sich mit anderen effizienten Algorithmen, wie z.B. dem SPADE zu beschäftigen (vgl. Zaki (2001, S. 31-60)).

Im Grunde genommen finden die in diesem Kapitel vorgestellte Algorithmen in vielen Wissenschaftsbereichen ihre Anwendung. Speziell in der Analyse des Konsumentenverhaltens und des Web-log Mining kann im Marketingbereich der Einsatz erfolgen. Deshalb wird im nächsten Kapitel die Anwendung der Sequenzanalyse für Fragen des Web-Usage Mining diskutiert.

2.5 Web-Usage Mining

Das Web Mining ist eine relativ neue Disziplin in der Wissenschaft. Es beschäftigt sich allgemein mit der Extraktion des Wissens aus den im World Wide Web verstreuten, riesigen

¹² Zusätzliche Definitionen sowie die Studie befindet sich bei Pei et al. (2001, S. 219 ff.).

17

Mengen  an Informationen (vgl. Gaul, Schmidt-Thieme (2000, S. 429)) Mit anderen Worten  

werden  hier die Verfahren des Data Mining auf das Web angewendet. Beim Web Mining  

werden  verschiedene Arten unterscheiden (vgl. Zaiane (1998, S. 19-20))  

Das  so genannte Web Content mining zielt darauf ab, Informationen in Datenbanken zu  

  filtern und gewisse Strukturen zu entdecken. Cooley, Mobasher, Srivastava (1997) unter-  

scheiden  den Prozeß des Web Content Mining in einen agentenbasierten und einen daten-  

bankorientierten  Ansatz. Zum Ersten ist zu bemerken, dass hier mit Hilfe effizienter KI-  

Systeme  des Anwenders versucht wird, webbasierte Informationen zu entdecken und später  

auch  zu klassifizieren. Beim datenbankorientieren Ansatz werden Verfahren eingesetzt, um  

semi  -strukturierte Daten im Netz in strukturierte Informationen zu bringen.  

Die  Richtung der Forschung beim Web-Usage Mining geht in die Entdeckung und Analy-  

se  des Benutzerverhaltens im Web (vgl. Gaul, Schmidt-Thieme (2000, S. 429)) Es eignet  

sich  somit hervorragend um Benutzerprofile zu erstellen, wobei die Daten mittels Log-Files  

ermittelt  werden. Das Web-Usage Mining wird aufgeteilt in general access pattern tracking  

und  customized usage tracking. Beim Ersten handelt es sich um eine Methode der Verfol-  

gung  von Zugriffsmustern. Hier werden die Logs ausgewertet mit dem Ziel der Ermittlung  

von  Mustern und Trends. Das customized usage tracking hat die Aufgabe der Bereitstellung  

einer  auf den Kunden zugeschnittenen Webseite.  

Den  letzten Teil des Web Mining nennt man Web Structure Mining. Der Schwerpunkt liegt  

hier  auf dem Aufbau der Strukturen des Web (vgl. Zaiane (1998, S. 19-20)) Häufig wird  

dieser  Teil zum Web Content Mining gezählt.  

Die  in diesem Kapitel vorgestellte Sequenzanalyse kann auch mit einigen Modifikationen,  

im  Bereich des Web-Usage Mining Anwendung finden. Interessant ist in diesem Zusammen-  

hang  der Aufsatz von Chen (vgl. Chen, Park, Yu (1998, S. 209-221)) Es werden effiziente  

Algorithmen  zur Ermittlung von Mustern vorgestellt.  

Dar  über hinaus wird das Problem der Sequenzanalyse in der Anwendung des Web-Mining  

anschaulich  bei Gaul 2001 dargestellt (vgl. Gaul, Schmidt-Thieme (2001, S. 429-445)) Die  

in  diesem Kontext benutzte Sequenzanalyse hat als Hauptziel die Aufstellung von Prognosen  

  über wahrscheinliches Nutzerverhalten. Dieses kann verwendet werden, um gezielte Marke-  

tingstrategien  zu formulieren.  

18

Kapitel 3

Analyse von Kaufhistorien mit einem

modifizierten

Assoziationsregelalgorithmus

In vorliegendem Abschnitt der Arbeit wird ein neuer Ansatz zur Analyse des Markenwechselverhaltens vorgestellt. Gegenstand der Betrachtung ist ein modifizierter Assoziationsregel Algorithmus zur Analyse von Kaufhistorien und die in diesem Zusammenhang entwickelte theoretische Grundlage. Eine neue Idee der Kodierung der Kaufgeschichten beim Auftreten von Promotion wird anhand selbsterstellter Beispiele aufgezeigt. Darüber hinaus wird ein Loyalitätsmaß für die generierten Switching-Regeln höherer Ordnung vorgestellt.

3.1 Probleme und Aufgaben des Ansatzes

Im Bereich der Konsumentenverhaltensforschung ist dem Phänomen des Markenwechselverhaltens unbestritten eine hohe Bedeutung beizumessen. Nicht nur aus Gründen der ableitbaren Aussagen zur Loyalität sondern besonders zum allgemeinen Verständnis des Kaufverhaltens sowie zur Formulierung effektiver Marketingstrategien werden Muster des Kaufverhaltens als Basis für das Forschungsfeld des Wechselverhaltens betrachtet (vgl. Säuberlich (2000, S. 172)). Der in den nachfolgenden Ausführungen dargelegte Ansatz stellt ein neues Data Mining Verfahren dar, um Fragestellungen des Markenwechelverhaltens und der eng damit verbundenen Loyalität, behandeln zu können. Als Grundlage zur Analyse des Markenwechselverhaltens dienen hier Paneldaten von Konsumenten, die nach einer Aufbereitung mit Hilfe des modifizierten Assoziationsregel Algorithmus analysiert werden können.

19

Im Gegensatz zu den traditionellen, auf einer Switching-Matrix basierenden Verfahren zur Analyse des Wechselverhaltens, können mit dem neuen Data Mining Verfahren Assoziationen höherer Ordnung, d.h. zwischen mehr als zwei Kaufzeitpunkten bestimmt werden (vgl. Gaul, Schader (1999, S. 11)).

3.2 Theoretische Betrachtungen

Basis des generalisierten Ansatzes zur Analyse des Markenwechselverhaltens sind individuelle Kauffolgen von Konsumenten. Zuerst ist eine Menge M = {q, r, ...} von Marken einer Produktkategorie zu definieren. Diese Menge enthält die in den individuellen Kaufhistorien auftretenden zulässigen Marken. Eine individuelle Kauffolge eines Konsumenten kann dann wie folgt formal modelliert werden: F = (f 1 → ... → f j → ... → f n(F ) ). Die zu aufeinanderfolgenden Kaufzeitpunkten gekauften Marken f j ∈ M bilden eine Sequenz ab. Dabei wird die Gesamtzahl der in einer Kauffolge F gekauften Marken mit n(F ) bezeichnet. Besondere Beachtung verdient die Tatsache, dass die gleiche Marke zu verschiedenen Kaufzeitpunkten ¹ erworben werden kann (vgl. Gaul, Säuberlich (1998, S. 151)). Im Folgenden werden weiterführende Definitionen zur Erläuterung des Ansatzes vorgestellt. (vgl. Säuberlich (2000, S. 175)). Definition 3.1:

1. Eine Teilfolge X von F heißt zusammenhängende Teilfolge, wenn ein Index j(X) ∈ N ⁰ existiert, so dass X in der Form X = (f j(X)+1 → f j(X)+2 → ... → f j(X)+n(X) ) geschrieben werden kann, mit j(X) + n(X) ≤ n(F ). Das Symbol ⊂ bezeichnet eine solche Teilfolge.

⊂ Y bezeichnet b(X) die erste sowie e(X)

die letzte innerhalb von X gekaufte Marke. l(X)[:= n(X) − 1] gibt die Zahl der direkt hintereinander gekauften Markenpaare an.

⊂F Indizes j(X), j(Y ) ∈ N 0 ,

mit j(X) ≤ j(Y ) sowie j(X) + n(X) = j(Y ) + k, k = k(X, Y ) ∈ {1, ..., n(Y )}, so ∪ k Y = (f j(X)+1 → ... → f j(X)+n(X) → f j(Y )+k+1 → ... → f j(Y )+n(Y ) ) die so genannte k-überlappende Komposition von X und Y . Dabei gilt (X ⊂ F .

¹ Die Transaktionsdefinition bei traditionellen Assoziationsregeln steht im Konflikt zu dieser Tatsache (vgl. Säuberlich (2000, S. 174)).

20

⊂ F bezeichnet m(X, F, l) die Zahl, wie oft X als zusammenhängende Teilfol- ⊂ F ,mit j(Z) = 0 und l(F ) − l(Z) = l, auftritt.

Die Eigenschaften von k-überlappenden Kompositionen lassen sich wie folgt zusammenfassen: Bemerkung 3.1: ⊂ F mit k = k(X, Y ) ∈ {1, ..., n(Y )} dann gilt:

∪ k Y ) = b(X),

∪ k Y ) = e(Y ),

∪ k Y ) = l(X) + l(Y ) − k + 1.

Der bisherige Ansatz der generalisierten Analyse des Markenwechselverhaltens basierte auf genau einer Kauffolge eines Konsumenten. In der nächsten Definition wird eine Menge J von Individuen vorausgesetzt, für welche solche Kauffolgen vorliegen. Es erfolgt eine Verallgemeinerung des Ansatzes auf eine riesige Datenmenge von individuellen Kauffolgen. Definition 3.2:

Für die Menge D 0 := {F t | t ∈ J } von individuellen Kauffolgen lassen sich folgende Beziehungen herleiten :

1. Die Größe

zählt das Auftreten einer zusammenhängenden Kauffolge X in der Menge

⊂ F t , l(F t ) − l(Z t ) = l, j(Z t ) = 0, t ∈ J } (3.2)

und heißt der l-generalisierte Support von X.

2. Die so genannte generalisierte Konfidenz von X und Y für 1-überlappende Komposi- ∪ 1 Y istfolgendermaßen definiert:

3. Zwei Teilfolgen X und Y mit (0-)generalisiertem Support s 0 (X ∪ 1 Y ) und generali-

sierter Konfidenz c(X, Y ) werden generalisierte Switching-Regel (X, Y ) genannt.

21

Der l-generalisierte Support gibt die Häufigkeit an, mit der eine Teilfolge in der Menge aller betrachteten Kauffolgen vorkommt. Dabei ist zu beachten, dass jeweils die l letzten Käufe nicht berücksichtigt werden, denn bei der Berechnung der Konfidenz für zwei Teilfolgen X und Y wird gewährleistet, dass im Nenner nur solche Kauffolgen in die Berechnung ein- ∪ 1 Y ) Käufeenthalten. Die generalisierte Konfidenz von X

und Y gibt den Prozentsatz von Individuen an, welche von X nach Y wechseln. Sie wird nicht durch Kauffolgen verfälscht, die zwar X als Teilfolge enthalten, jedoch später zu keinem Kauf mehr führen (vgl. Säuberlich (2000, S. 176)).

Die Einträge der bedingten Switching-Matrix liefert Definition 3.2. Die geschätzte bedingte Wahrscheinlichkeit, dass Marke r gekauft wird unter der Bedingung, dass vorher Marke q erworben wurde, beschreibt die generalisierte Konfidenz für X = (q) und Y = (q → r). Formal gilt:

Im Zähler der Größe c((q), (q → r)) wird das Auftreten der Wechsel von (q → r) in der Menge D 0 betrachtet. Die Menge D 0 enthält alle in den Kauffolgen der Konsumenten getätigten Kaufakte, wohingegen im Nenner von c((q), (q → r)) das Vorkommen von (q) in der Menge D 1 ( Menge der Kauffolgen ohne Berücksichtigung des letzten Kaufes ) verwendet wird. Beispiel 3.1:

Im folgenden sehr vereinfachten Beispiel sollen nun die zentralen Begriffe, nämlich der des l- generalisierten Supports und der generaliesierten Konfidenz deutlich gemacht werden. Besonderes Gewicht liegt auf der Bestimmung dieser zentralen Größen und ihrer weiteren Verwendung.

Die Menge M = {A, B, C} enthält die zulässigen in den Kauffolgen enthaltenen Marken. Weiterhin ist die Menge der individuellen Kauffolgen der Konsumenten gegeben durch die Größe D 0 = {F 1 , F 2 , F 3 , F 4 , F 5 }:

F 1 = (A → A → B → A → B)

F 2 = (B → A → A → A → B → C) F 3 = (B → B → C → A → A → A) F 4 = (A → A → B → C → B) F 5 = (A → B → C → C → B)

22