Fuzzy-Rule-Learner Dokumentationcleve/vorl/projects/dm/ss13/FuzzyRule/frl... · 3 1. Algorithmus 1.1. Fuzzy-Rule-Learner Der Fuzzy-Rule-Learner ist ein Algorithmus, der Regeln in

Fuzzy-Rule-Learner

Dokumentation

Wissensextraktion / Data-Mining

Wirtschaftsinformatik Master

Hochschule Wismar

Bearbeiter:

Adil Khalat, Tobias Oeberst, Marian Sakowski

2

Inhalt 1. Algorithmus ......................................................................................................................................... 3

1.1. Fuzzy-Rule-Learner ....................................................................................................................... 3

1.2. Shrink ............................................................................................................................................ 3

1.3. Fuzzy-Normen .............................................................................................................................. 4

2. Datensatz ............................................................................................................................................. 5

3. Datenvorbereitung .............................................................................................................................. 6

4. Knime Aufbau ...................................................................................................................................... 7

5. Ergebnisse............................................................................................................................................ 8

Literatur ................................................................................................................................................... 9

Anhang .................................................................................................................................................. 10

Ergebnisübersicht .............................................................................................................................. 10

Knime-Workspace ............................................................................................................................. 17

Präsentation ...................................................................................................................................... 17

3

1. Algorithmus

1.1. Fuzzy-Rule-Learner

Der Fuzzy-Rule-Learner ist ein Algorithmus, der Regeln in Form von Fuzzy-Zugehörigkeitsfunktionen

zur Klassifizierung von Daten generiert. Dabei kann der Algorithmus metrische und ordinale Werte

verarbeiten. Das Zielattribut kann auch nominal sein. Zur Erstellung von Regeln müssen die

betrachteten Eigenschaften und Klassifizierungen angegeben werden. Iterativ werden folgende

Schritte durchgeführt. Erster Schritt „Cover“: Wenn ein neues Muster innerhalb des Support-Bereiches

einer existierenden Fuzzy-Funktion der angegebenen Klasse liegt, wird der Kernbereich erweitert, um

das neue Muster zu umfassen. Zweiter Schritt „Commit“: Falls das neue Muster mit seiner Klasse noch

nicht abgedeckt ist, wird eine neue Fuzzy-Funktion erstellt, zu den bestehenden hinzugefügt und das

neue Muster als Kernbereich gekennzeichnet. Zusätzlich wird dessen Support-Bereich als „infinite“

(unbegrenzt) gekennzeichnet, um zunächst alle Bereiche abzudecken. Im dritten Schritt „Shrink“ wird

geprüft, ob neue Muster falsch durch vorhandene Regeln abgedeckt werden und der Support-Bereich

der entsprechenden Regel verkleinert werden muss, um Konflikte zu vermeiden. Für diesen Schritt

stehen 3 Shrink-Heuristiken zur Verfügung.

1.2. Shrink

Die Shrink-Heuristiken sind Methoden zur Verkleinerung der Kern- und Support-Bereiche. Es stehen

für den Kern(K)- und Support(S)-Bereich jeweils eine Funktion zur Verfügung:

��, b ≤ x ≤ c�: ��∗��, �� = �� − ��, �� ≤ �� − ��, �� , a < x < b ˅ c < x < d�: ��∗��, ��= �� − �, �� ≤ ��

�� − �� , ��

Da diese noch eine Gewichtung für die Verkleinerung benötigt, werden im Folgenden drei Alternativen

aufgezeigt.

1. Rule-based shrink: Gewichtet mit Bezug auf die Fuzzy-Regel-Verteilung (spread).

��: ��!��, �� = �� − �� : ��!��, �� = �� − �

2. Anchor-based shrink: Gewichtet mit Bezug auf den Abstand zw. Initialvektor und Grenze des

Support-Bereiches.

��: ��!��, �� = �� − ��, �� ≤ �� − ��, �� : ��!��, �� = �� − � , �� ≤ �� − ��, ��

3. Area-based shrink: Gewichet mit Bezug auf den Abstand zw. Grenze des Support-Bereiches und des

Kernbereiches.

��: ��!��, �� = �� − �� : ��!��, �� = �� − �, �� ≤ �� − ��, ��

4

1.3. Fuzzy-Normen

Fuzzy-Normen können mit Hilfe der im Fuzzy-Rule-Learner erstellten Regeln neue unbekannte Klassen

klassifizieren. Die eindimensionale Originalregel zusammen mit der Fuzzy t-norm in Verbindung mit

dem Erfüllungsgrad aller Regeln einer Klasse zusammen mit der t-conorm resultieren in einem

Zugehörigkeitsgrad für jede Klasse. Die Auswahl der Normen hat spürbare Auswirkungen auf die

endgültige Klassifizierung.

Min/Max Norm:

⊤#$��, $�%�& = min*$��, $�%�+,⊥ #$��, $�%�& = min*$��, $�%�+

⊤() (t-norm) = Fuzzy Verbindungsoperator

$() = Grad der Zugehörigkeit

⊥() (t-conorm) = „disjunction-operator“

Produkt Norm:

⊤#$��, $�%�& = $�� ∗ $�%�,⊥ #$��, $�%�& = $�� + $�%� − $�� ∗ $�%�

Łukasiewicz Norm:

⊤#$��, $�%�& = max*0, $�� + $�%� − 1+,⊥ #$��, $�%�& = min*1, $�� + $�%�+

Und Yager Norm:

⊤0#$��, $�%�& = 1 − min �1, [#1 − $��&0 + #1 − $�%�&0]304 ,

⊥0 #$��, $�%�& = min �1, [$��0 + $�%�0]304 , 5 ∈]0, ∞[

5

2. Datensatz

Zur Bearbeitung wurde der Datensatz des Data-Mining-Cups 2002 ausgewählt. Dieser enthält

Kundendaten eines Stromerzeugers. Für eine zielgerichtete Marketing-Maßnahme sollen die Kunden

in Kündiger und Nicht-Kündiger sortiert und über die folgende Kundenwertmatrix der mögliche

Kundenwert vorhergesagt werden.

Kundenwert/Jahr Kunde Kündiger

Erhält kein Angebot 72,00 € 0,00 €

Erhält Angebot 66,30 € 43,80 € Tabelle 1: Kundenwertmatrix

Der zu klassifizierende Datensatz enthält 10.000 Einträge mit 32 Merkmalen und es wurde ein

Trainingsdatensatz mit 1.000 Einträgen zur Verfügung gestellt.

6

3. Datenvorbereitung

Während der Datenvorbereitung wurden zunächst für die Verständlichkeit die Merkmale (Spalten) neu

benannt (siehe im Workflow Knoten „Column Rename“).

Um einige Merkmale aus der Verarbeitung entfernen zu können, wurde ein Knoten „Cloumn Filter“ im

Workflow aufgenommen. Entfernte Merkmale werden im Bereich Ergebnisse benannt.

Zur Vorbereitung der Normalisierung musste das Merkmal „Kaufkraft“ vereinheitlicht werden. Dieses

enthielt für Bürger der alten Bundesländer positive Werte (1=niedrige Kaufkraft; 9=hohe Kaufkraft)

und in den neuen Bundesländern negative Werte (-9=niedrige Kaufkraft; -1 hohe Kaufkraft). Für die

Angleichung wurde in einem „Java Snippet“ der Wert 10 für die neuen Bundesländer addiert.

Ebenfalls wurde eine Normalisierung (Abb. 1 „Normalizer“) aller Merkmale vorgenommen.

Zum Abschluss werden mit Hilfe des Fuzzy-Rule-Learner und dessen Funktion „Missing Values“

fehlende Werte aufgefüllt.

Abbildung 1: Datenvorbereitung

7

4. Knime Aufbau

Abbildung 2: Fuzzy-Rule-Learner-Aufbau

In der Abbildung 2 ist der für den Fuzzy-Rule-Learner erstellte Workflow zu sehen. In diesem sind an

den benötigten Stellen „File Reader“-Knoten zu sehen, mit denen die Daten des Szenarios eingelesen

werden. Im Bereich „data prepare“ werden die Daten wie im vorherigen Abschnitt beschrieben

vorverarbeitet.

Im oberen Verlauf für die Trainingsdaten ist der Fuzzy-Rule-Learner angeordnet. Dieser enthält

Optionen zur Auffüllung fehlender Werte, Auswahl der zu betrachtenden Merkmale/Spalten und die

Funktionen der Shrink-Funktion und Fuzzy-Norm. Die erstellten Regeln werden im Knoten „Fuzzy Rule

Predictor“ auf die Vorhersage-Datensatz angewandt. Falls einige Datensätze nicht klassifiziert werden

konnten, werden diese im „Java Snippet“ Unb. Klassen der Klasse der Nicht-Kündiger zugeordnet.

In den anschließenden Knoten wird die Vorhersage mit dem exakten Ergebnis verglichen und der

Kundenwert berechnet. Zum Schluss wird eine Benachrichtigung für die Beendigung des Vorgangs

ausgelöst.

Die Knoten „Column Filter“ Abgabe und „CSV Writer“ im oberen Bereich des Workflows dienen der

Formatierung und Ausgabe für die Abgabe der Daten im Data-Mining-Cup.

8

5. Ergebnisse

Zur Bewertung der erhaltenen Vorhersagen wird mit Hilfe der Kundenwertmatrix (siehe Tabelle 1) der

erzielte Kundenwert berechnet und mit dem optimalen Kundenwert ohne Fehlvorhersage verglichen.

Der optimaler Kundenwert beträgt 691.800 €. Im Folgenden werden die Ergebnisse erläutert, die einen

Fortschritt mit sich brachten. Eine komplette Übersicht der jeweiligen Veränderungen und deren

Ergebnisse sind in der Anhang zu finden.

In einem ersten Test des Fuzzy-Rule-Learner wurden alle Merkmale der Daten berücksichtigt und die

Einstellungen wie folgt verwendet: Missing Values „Incorp“, Fuzzy-Norm „Min/Max-Norm“ und Shrink-

Funktion „VolumeBorderBased“. Das Ergebnis war eine Fehlerquote von 11,45 % bei einem

Kundenwert von 647.859,30 € und damit einer Abweichung von 6,35 % vom Optimum. Daraufhin

wurden die Werte normalisiert, wodurch der Kundenwert auf 648.120,30 € (rel. Diff. 6,31%) bei einer

annähernd gleichen Fehlerquote von 11,46 % gesteigert werden konnte.

Während der Tests konnte die Fehlerquote auf 10,18 % gesenkt werden. Dies erfolgte mit den

folgenden Einstellungen: Missing Values „Mean“, Fuzzy-Norm „Yager[0.5]-Norm“ und Shrink-Funktion

„VolumeBorderBased“. Der Kundenwert betrug mit diesen Einstellungen 648.705,30 € bei einer

relativen Abweichung von 6,31%.

Der beste Kundenwert konnte mit den Einstellungen Missing Values „Mean“, Fuzzy-Norm „Produkt-

Norm“ und der Shrink-Funktion „VolumeBorderBased“ erzielt werden. Weiterhin wurden für diesen

Test die Merkmale Straßentyp, Anteil-Deutscher und die Psycho-, Pharma- und PKW-Indizes entfernt.

Die Ergebnisse waren ein Kundenwert von 649.225 € mit einer Fehlerquote von 11,66 % und einer

Abweichung von 6,15 %.

Um einen Vergleich mit anderen Verfahren zu ermöglichen, wurden neben dem Fuzzy Rule Learner,

auch der Decision-Tree-, Naive Bayers- und der Probabilistic Neural Network-Learner getestet. Diese

brachten bei unserem Versuchsaufbau ähnliche Ergebnisse und keine weiteren Verbesserungen. Auf

Grund des zeitlichen Rahmens verblieb jedoch keine Zeit für diese Alternativen jeweils noch weitere

Optimierungen durchzuführen.

Zusammenfassend ist der Fuzzy-Rule-Learner ein vielseitiger Algorithmus, der sowohl ordinale als auch

metrische Daten verarbeiten kann. In Knime standen weiterhin noch Optionen zur Verfügung, die die

Datenvorbereitung vereinfachten.

9

Literatur

Didacticiel - Études de cas

http://eric.univ-lyon2.fr/~ricco/tanagra/fichiers/en_Tanagra_Induction_Regles_Floues_Knime.pdf

Mixed fuzzy rule formation - M.R. Berthold

http://www.inf.uni-konstanz.de/bioml2/publications/Papers2003/Bert03_mixedFR_ijar.pdf

Influence of fuzzy norms and other heuristics on ‘‘Mixed fuzzy rule formation’’ - Thomas R. Gabriel,

Michael R. Berthold

http://www.inf.uni-

konstanz.de/bioml2/publications/Papers2004/GaBe04_mixedFRappendix_ijar.pdf

10

Anhang

Ergebnisübersicht

Information: Änderungen, die eine Verschlechterung des Ergebnisses zur Folge hatten, wurden

rückgängig gemacht.

Legende:

FQ: Fehlerquote der Vorhersage Veränderung Verbesserung

alle Spalten, Fuzzy Incorp bei Missing Values, Min/ Max Norm, VolumeBorderBased

Kunde Kündiger FQ/rel. Diff. Gewinn/Differenz

kein Angebot 8837 982 11,45% 647.859,30 €

Angebot 163 18 6,35% 43.940,70 €

+ Normalisierung


kein Angebot 8829 975 11,46% 648.120,30 €

Angebot 171 25 6,31% 43.679,70 €

+ Kaufkraft + 10 (die nur negativ Werte positiv mac hen)

kein Unterschied, Rückgängig

+ Zielspalte ordinal machen (anstatt nominal)

kein Unterschied, Rückgängig

11

Mis

sing

Val

ues

+ Fuzzy Best Guess


kein Angebot 8918 985 10,67% 648.189,60 €

Angebot 82 15 6,30% 43.610,40 €

+ Fuzzy Mean


kein Angebot 8924 977 10,53% 648.574,20 €

Angebot 76 23 6,25% 43.225,80 €

+ Min


kein Angebot 8936 983 10,47% 648.379,80 €

Angebot 64 17 6,28% 43.420,20 €

+ Max


kein Angebot 8919 985 10,66% 648.195,30 €

Angebot 81 15 6,30% 43.604,70 €

+ Zero


kein Angebot 8936 983 10,47% 648.379,80 €

Angebot 64 17 6,28% 43.420,20 €

12

+ One


kein Angebot 8919 985 10,66% 648.195,30 €

Angebot 81 15 6,30% 43.604,70 €

Shr

ink

Fun

ctio

n

+ VolumneAnchorBased


kein Angebot 8930 986 10,56% 648.214,20 €

Angebot 70 14 6,30% 43.585,80 €

+ VolumeRuleBased


kein Angebot 8959 989 10,30% 648.248,10 €

Angebot 41 11 6,30% 43.551,90 €

Fuz

zy N

orm

+ Product Norm


kein Angebot 8918 974 10,56% 648.671,40 €

Angebot 82 26 6,23% 43.128,60 €

+ Lukasiewicz Norm


kein Angebot 8962 985 10,23% 648.440,40 €

Angebot 38 15 6,27% 43.359,60 €

+ Yager[2.0] Norm


kein Angebot 8968 986 10,18% 648.430,80 €

Angebot 32 14 6,27% 43.369,20 €

13

+ Yager[0.5] Norm


kein Angebot 8981 994 10,13% 648.154,50 €

Angebot 19 6 6,31% 43.645,50 €

Spa

ltenf

ilter

+ ohne PKW- *


kein Angebot 8801 958 11,57% 648.705,30 €

Angebot 199 42 6,23% 43.094,70 €

+ ohne Anteil Deutscher


kein Angebot 8914 981 10,67% 648.342,00 €

Angebot 86 19 6,28% 43.458,00 €

+ ohne Psycho-*


kein Angebot 8902 973 10,71% 648.624,00 €

Angebot 98 27 6,24% 43.176,00 €

+ ohne Pharma-*


kein Angebot 8929 981 10,52% 648.427,50 €

Angebot 71 19 6,27% 43.372,50 €

+ ohne die 4 bislang getesteten


kein Angebot 8793 948 11,55% 649.097,70 €

Angebot 207 52 6,17% 42.702,30 €

14

+ ohne Zahlungsart

Kunde Kündiger

kein Angebot 8790 956 11,66% 648.730,20 €

Angebot 210 44 6,23% 43.069,80 €

+ ohne Stromverbrauch


kein Angebot 8753 952 11,99% 648.694,50 €

Angebot 247 48 6,23% 43.105,50 €

+ ohne Anzahl Haushalte


kein Angebot 8782 963 11,81% 648.378,00 €

Angebot 218 37 6,28% 43.422,00 €

+ ohne Anzahl Gewerbe


kein Angebot 8806 961 11,55% 648.602,40 €

Angebot 194 39 6,24% 43.197,60 €

+ ohne Regionaltyp


kein Angebot 8791 966 11,75% 648.297,90 €

Angebot 209 34 6,29% 43.502,10 €

+ ohne Kaufkraft


kein Angebot 8773 960 11,87% 648.458,10 €

Angebot 227 40 6,27% 43.341,90 €

15

+ ohne Straßentyp


kein Angebot 8777 943 11,66% 649.225,50 €

Angebot 223 57 6,15% 42.574,50 €

+ ohne Bebauungstyp


kein Angebot 8828 957 11,29% 648.903,00 €

Angebot 172 43 6,20% 42.897,00 €

+ ohne Status


kein Angebot 8769 951 11,82% 648.829,50 €

Angebot 231 49 6,21% 42.970,50 €

+ ohne Bonität


kein Angebot 8760 947 11,87% 648.953,40 €

Angebot 240 53 6,19% 42.846,60 €

+ ohne Altersstruktur


kein Angebot 8766 944 11,78% 649.119,00 €

Angebot 234 56 6,17% 42.681,00 €

+ ohne Familienstand


kein Angebot 8709 961 12,52% 648.049,50 €

Angebot 291 39 6,32% 43.750,50 €

16

V

ergl

eich

mit

ande

ren

Ver

fahr

en

Decision Tree


kein Angebot 8514 914 14,00% 648.996,60 €

Angebot 486 86 6,19% 42.803,40 €

Naive Bayes


kein Angebot 8899 969 10,70% 648.782,10 €

Angebot 101 31 6,22% 43.017,90 €

PNN


kein Angebot 8895 990 10,95% 647.839,50 €

Angebot 105 10 6,35% 43.960,50 €

17

Knime-Workspace

Befinden sich im Archiv frl-knime.zip

Präsentation

Befinden sich in frl-präsi.pdf

Documents

Fuzzy-Rule-Learner Dokumentationcleve/vorl/projects/dm/ss13/FuzzyRule/frl... · 3 1. Algorithmus 1.1. Fuzzy-Rule-Learner Der Fuzzy-Rule-Learner ist ein Algorithmus, der Regeln in