Maßzahlen für die Assoziationsanalyse im Data Mining

Diplomarbeit von Stephan Hagemann

Einleitung:

Measurement does not necessarily mean progress. Failing the possibility of measuring that which you desire, the lust for measurement may, for example, merely result in your measuring something else - and perhaps forgetting the difference - or in your ignoring some things because they cannot be measured. (George Udny Yule in einem Brief an Maurice Kendall).

Problemstellung:

Die Assoziationsanalyse ist innerhalb des Knowledge Discovery in Databases (KDD) eine sehr populäre Methode zur Gewinnung von Wissen aus großen Datenmengen. Ein wesentlicher Grundstein für dieses Werkzeug wurde mit der Einführung der Warenkorbanalyse im Jahre 1993 durch Agrawal et al. gelegt. Seit dem haben sich eine Fülle von Veröffentlichungen mit ihrer Erweiterung, Verbesserung und änderung befasst. Die Intention der Assoziationsanalyse ist die Gewinnung von Regeln zwischen den Attributen von Objekten, wobei die Akzeptanz einer Regel bedeutet, dass das Auftreten der Konsequenz einer Regel stark vom Auftreten der Vorbedingung abhängig ist, diese beiden also stark assoziiert sind.

Die Menge potentieller Regeln, die für ein Objekt gebildet werden können, wächst exponentiell mit der Anzahl der Attribute dieses Objekts. Um diese Zahl zu reduzieren, werden den Regeln verschiedene Arten von Restriktionen auferlegt. Im Zentrum der Frage der Akzeptanz einer Regel steht die Bewertung ihrer Stärke oder auch confidence, welche als die bedingte Wahrscheinlichkeit der Konsequenz unter der Vorbedingung definiert ist. Dieses Maß als Aussage über die überzeugung in die Stärke einer Regel stand und steht in der Literatur unter viel Kritik, da es auch einige Fälle von approximativer stochastischer Unabhängigkeit als stark abhängig bewertet und als Regeln akzeptiert, was als irreführend empfunden wird.

Viele Beiträge in der Literatur befassen sich mit diesem Problem und schlagen verschiedene Lösungen vor. In einigen Arbeiten werden nachgelagerte Verarbeitungsschritte untersucht, die z. B. mit Hilfe statistischer Verfahren versuchen, aus der Menge der akzeptierten Regeln diejenigen zu eliminieren, die keine Abhängigkeit darstellen. Außerdem werden Zusammenfassungen, Gruppierungen und Visualisierungen untersucht, die bei der Untersuchung der Regeln durch den Nutzer helfen sollen. In anderen Literaturbeiträgen sind alternative Maße zur Bestimmung der Stärke einer Regel entwickelt worden. Die Hoffnung ist, durch die Anwendung sinnvoller Maße die Akzeptanz von irreführenden Regeln zu vermeiden.

Gang der Untersuchung:

In den Arbeiten, die eine neue Maßzahl als Ersatz für confidence vorschlagen, werden häufig Tests verwendet um die Bewertungen der Maße zu vergleichen. Es fehlt jedoch für das KDD an einer allgemeinen Definition wünschenswerter Eigenschaften für Assoziationsmaße, die einen Vergleich der Maße unabhängig von konkreten Daten ermöglichen würde. Für den Fall stetiger Zufallsvariablen gibt es jedoch in der Literatur verschiedene Axiomatisierungen für Assoziationsmaße. Diese bilden für diese Arbeit die Grundlage bei der Entwicklung einer Axiomatisierung für Maße in der Assoziationsanalyse. Im Umfeld des KDD verwendete Maße werden desweiteren vorgestellt und auf die Erfüllung der neu definierten Eigenschaften hin untersucht. So werden die Maße im Hinblick auf ihre Anwendung in der Assoziationsnalyse fundiert.

Als weiterer Schritt wird anhand zweier sehr unterschiedlicher Testdatenbanken untersucht, in wie fern sich die Erfüllung oder Nicht-Erfüllung der Eigenschaften in den Ergebnissen einer Assoziationsanalyse widerspiegelt. Dazu wird eine Reihe von sowohl qualitativen als auch quantitativen Beobachtungen verglichen.

Den Kern dieser Arbeit stellen somit die Fundierung und Untersuchung der Maße aus der Assoziationsanalyse und deren empirische Testung dar. Um diese beiden Teile in die bisherigen Forschungen einordnen zu können, folgt in Abschnitt 2 eine Einordnung der Arbeit in das KDD. Zunächst werden hierzu relevante Begriffe KDD und Data Mining (DM) definiert und erläutert, bevor die Grundlagen der Assoziationsanalyse vorgestellt werden. Den Abschluss dieses heranführenden Abschnitts bildet die Darstellung verschiedener Vorschläge zur Verbesserung und Erweiterung des ursprünglichen Ansatzes.

Abschnitt 3 befasst sich mit der Fundierung von Assoziationsmaßen und der Vorstellung von in verschiedenen Kontexten verwendeten Maßen. Zunächst werden hierbei frühere Axiomatisierungen zusammengetragen und zur Entwicklung einer neuen, speziell auf die Assoziationsanalyse ausgerichteten Axiomatisierung verwendet. Danach folgt ihre Prüfung auf die geforderten Eigenschaften hin.

Dem empirischen Teil dieser Arbeit wendet sich Abschnitt 4 zu. Anhand einer Visualisierung der Funktionsverläufe der Maße wird zunächst eine optische Klassifizierung versucht. Dann werden die Testdaten und die zur Analyse verwendeten Algorithmen erläutert, bevor verschiedene Eigenschaften der durch die Maße akzeptierten Regeln untersucht werden. Dies erlaubt die Prüfung und den Vergleich der unterschiedlichen Regelakzeptanz der verschiedenen Maßzahlen.

Inhaltsverzeichnis:

	Abbildungsverzeichnis	IV
	Tabellenverzeichnis	V
	Symbolverzeichnis	VI
1.	Einleitung	1
1.1	Problemstellung	1
1.2	Zielsetzung und Aufbau dieser Arbeit	2
2.	Assoziationsanalyse im Kontext des Knowledge Discovery in Databases	3
2.1	Grundlagen	3
2.1.1	Knowledge Discovery in Databases und Data Mining - eine Abgrenzung	3
2.1.2	Der Knowledge Discovery in Databases-Prozess	4
2.1.3	Methoden des Data Mining	8
2.2	Grundlagen der Assoziationsanalyse	11
2.2.1	Warenkorbanalyse	11
2.2.2	Frequent Itemset Mining	13
2.2.3	Ausweitung des Assoziationsanalyse-Ansatzes	16
2.2.4	Herausforderungen und Probleme	17
2.3	Verbesserungen und Erweiterungen	19
2.3.1	Pruning	19
2.3.2	Gruppierung und Zusammenfassung	20
2.3.3	Visualisierung	22
2.3.4	Interessantheitsmaße	23
2.4	Zwischenfazit	24
3.	Assoziationsmaße	25
3.1	Grundlagen	25
3.1.1	Assoziationsmaße in der Statistik	25
3.1.2	Bisherige Axiomatisierungen	26
3.2	Maße für die Assoziationsanalyse im Data Mining	28
3.2.1	Grundraum und Anforderungen	28
3.2.2	Einschränkungen	30
3.2.3	Diskussion der Axiomatisierung für Assoziationsmaße	32
3.2.4	Axiomatisierung für Assoziationsmaße	38
3.2.5	Beispiele für Forderungen der Axiome	38
3.3	Von Korrelation zu Assoziation	42
3.4	Mögliche Maßzahlen	45
3.4.1	Vorstellung der Maße	45
3.4.2	Gegenüberstellung	56
3.5	Zwischenfazit	58
4	Vergleich der Maßzahlen	59
4.1	Anwendbarkeit der alternativen Maße im Data Mining	59
4.2	Visualisierung	61
4.2.1	Die Idee	61
4.2.2	Erweiterungen	62
4.2.3	Visuelle Auswertung der Maßzahlen	67
4.3	Testdaten und Algorithmen	74
4.3.1	Testdaten	74
4.3.2	Algorithmen	76
4.4	Regeln in Abhängigkeit von ?	76
4.5	Vergleich akzeptierter Regeln	78
4.5.1	Auswertung	80
4.5.2	Standardisierung der Randverteilungen	85
4.6	Zwischenfazit	88
5	Zusammenfassung und Ausblick	90
	Literatur	92
	Anhang	98

Textprobe:

Kapitel 3.2.3, Diskussion der Axiomatisierung für Assoziationsmaße:

Die in Abschnitt 3.1.2 beschriebenen Axiomatisierungen für Assoziationsmaße enthielten keine Definition einer Isotoniebedingung. Im Hinblick darauf, dass es für Korrelationsmaße möglich ist, mehrere unterschiedlich strenge Definitionen zu formulieren, ist es nicht nachvollziehbar, dass dies für Assoziationsmaße so noch nicht geschehen ist. Zumindest für den sehr eingeschränkten Fall, der hier betrachtet wird, soll im Folgenden eine solche Axiomatisierung versucht werden. Des Weiteren sollen die anderen Aspekte der bisherigen Axiomatisierungen diskutiert werden, damit im Abschnitt 3.2.4 diese in eine umfangreichere Formalisierung eingefügt werden können.

Permutationsinvarianz: Da Assoziationsmaße den Grad der Abhängigkeit zwischen zwei Zufallszahlen messen, nicht jedoch eine wie auch immer definierte Richtung dieser Abhängigkeit, sollte die Benennung der Dimensionen keine Rolle spielen. Es sollte im hier betrachteten Fall also möglich sein, die Zeilen und Spalten der Kontingenztafel beliebig umzuordnen, ohne dass sich die Maßzahl dadurch ändert.

Diese Forderung ist eine Ableitung der Forderung nach Bijektionsinvarianz von Re'nyi (vgl. Abschnitt 3.1.2). Sie entspricht einer Ausweitung der Forderung nach betragsmäßiger Invarianz gegenüber der Orientierung bei Korrelationsmaßen. Im hier betrachteten Fall eines endlichen, diskreten Grundraums, kann die Bijektionsinvarianz auch als Permutationsinvarianz bezeichnet werden.

Die Forderung nach Maßstabsinvarianz ist in einer Forderung nach Permutationsinvarianz enthalten, weshalb sie bei der Axiomatisierung als eigener Punkt weggelassen werden kann.

Isotonie und Symmetrie: Als Hinführung zu einer Isotoniebedingung für Assoziationsmaße folgt nun eine Diskussion wünschenswerter Eigenschaften dieser Maße anhand einiger Beispiele.

Relationen können nur dann bijektive Funktionen und damit symmetrisch sein, wenn die zu Grunde liegenden Mengen gleich groß sind. Sind Mengen unterschiedlich groß, kann es in einer (von der kleineren zur größeren Menge), aber nicht in beiden Richtungen injektive funktionale Abhängigkeit geben.

Beispiel 10: Gegeben sei die Kontingenztafel in Tabelle 1, in der nur die dunkelgrau hinterlegten Feldern positive relative Häufigkeiten aufweisen. In der Relation R = (X, Y, R^) seien x 2 X und y 2 Y dann in R^ enthalten, wenn sie gemeinsam auftreten (die relative Häufigkeit von x ^ y positiv ist). (siehe Tabelle 1: Approximative funktionale Abhängigkeit).

Man sieht leicht, dass die Relation (K, L, R^) eine Funktion ist. Denn in R^ ={ (1, 1), (2, 2), (3, 4), (4, 1), (5, 3), (6, 3)} ist zu jedem Wert in K genau einen Wert in L zugeordnet. Umgangssprachlich würde man sagen, dass L von K abhängig ist, weil man für jeden Wert von K weiß, welchen Wert L annehmen wird. Die Relation (L, K, R^) dagegen ist keine Funktion. Im Falle von L = 1 und L = 3 sind mehrere Werte aus K zugeordnet.

Funktionale Abhängigkeit ist also nicht immer symmetrisch. Dies stellt einen Gegensatz zur Symmetrie der linearen (monotonen) Abhängigkeit bei den Korrelationsmaßen.

Was passiert jedoch, wenn das hellgraue Feld eine sehr kleine relative Häufigkeit „ > 0 trägt? In diesem Fall ist L nicht mehr von K funktional abhängig. Umgangssprachlich würde man sagen, dass es aber „fast vollständig abhängig“ ist. Dies entspricht dem Begriff der approximativen funktionalen Abhängigkeit, der in der Literatur verwendet wird.

Das hier beschriebene Phänomen tritt übrigens auch in 2x2-Feldertafeln (und allgemein in quadratischen Tafeln) auf, falls die Zahl der Zeilen und Spalten mit positiven relativen Häufigkeiten nicht gleich ist (womit die Tafel de facto zu einer nicht-quadratischen entartet).

Eine Axiomatisierung für Assoziationsmaße sollte fordern, dass eine größere approximative funktionale Abhängigkeit eine höhere Assoziierung mit sich bringt. Außerdem sollte Symmetrie nicht unbedingt gefordert werden, da auch die Abhängigkeiten nicht symmetrisch sein müssen.

Speziell bei der Warenkorbanalyse ist Symmetrie eine unerwünschte Eigenschaft, da es um die Ermittlung von gerichteten Abhängigkeiten geht. Der Fall, dass bei Kaufentscheidungen eine ungerichtete Abhängigkeit besteht dürfte sehr viel seltener sein, als der Fall einer gerichteten Abhängigkeit.