Klassifizierung von Pilzen

Pilzesammler müssen sich gut auskennen, um sich nicht dem Risiko einer Vergiftung auszusetzen. Deshalb dürfen nur Pilze gesammelt werden, die eindeutig erkannt werden. Trotzdem ist es interessant, zunächst nur einmal danach zu fragen, ob man einen essbaren oder einen Pilz vor sich hat. Hierzu wurde 1981 für amerikanische Pilze ein Datensatz öffentlich zugänglich gemacht. Er ist zu finden auf dem Machine Learning Repository des Center for Machine Learning and Intelligent Systems in Irvine, Kalifornien.

Jeder Pilz ist durch 22 Merkmale charakterisiert und zusätzlich als essbar oder giftig eingeordnet. Die Merkmale betreffen Aussehen und Farbe, Geruch, Fundort und das Vorkommen zusammen mit weiteren Pilzen. Die Merkmale sind alle in nominalen Ausprägungen erfasst worden.

Für die Anwendung und Bewertung von verschiedenen Klassifizierungsverfahren wird der Datensatz unterteilt in Trainingsdaten und Testdaten. Der Datensatz wurde in datagalep als DataFrame eingelesen.

   julia> head(datagalep)
   6×24 DataFrame. Omitted printing of 15 columns
   │ Row │ id    │ class  │ a1     │ a2     │ a3     │ a4     │ a5     │ a6     │ a7     │
   │     │ Int64 │ String │ String │ String │ String │ String │ String │ String │ String │
   ├─────┼───────┼────────┼────────┼────────┼────────┼────────┼────────┼────────┼────────┤
   │ 1   │ 1     │ p      │ x      │ s      │ n      │ t      │ p      │ f      │ c      │
   │ 2   │ 2     │ e      │ x      │ s      │ y      │ t      │ a      │ f      │ c      │
   │ 3   │ 3     │ e      │ b      │ s      │ w      │ t      │ l      │ f      │ c      │
   │ 4   │ 4     │ p      │ x      │ y      │ w      │ t      │ p      │ f      │ c      │
   │ 5   │ 5     │ e      │ x      │ s      │ g      │ f      │ n      │ f      │ w      │
   │ 6   │ 6     │ e      │ x      │ y      │ y      │ t      │ a      │ f      │ c
   │

   julia> nall = size(datagalep, 1)
   8124

   julia> p = 0.02; # Auswahlwahrscheinlichkeit für das Testset

   julia> ntest = floor(Int, bign * p) # Größe Testset
   162

   julia> ids = collect(1:bign);

   julia> idsix = shuffle([trues(ntest); falses(bign - ntest)]);

   julia> dattest = datagalep[idsix, :];

   julia> dattraining = datagalep[.!idsix, :];

   julia> atlcagalep = setdiff(names(dattraining), [:id, :class])
   22-element Array{Symbol,1}:
	:a1 
	:a2 
	:a3 
	:a4 
	:a5 
	:a6 
	:a7 
	:a8 
	:a9 
	:a10
	:a11
	:a12
	:a13
	:a14
	:a15
	:a16
	:a17
	:a18
	:a19
	:a20
	:a21
	:a22

Von den insgesamt 8124 Datensätzen sind also 7962 in den Trainingsdaten und 162 in den Testdaten. atlcagalep enthält die Liste der Merkmale.

Nächste Nachbarn

Die Trainingsdaten sind bei diesem Verfahren direkte Vergleichsdaten für die Merkmalsvektoren, die klassifiziert werden sollen. Bei der Klassifizierung durch nächste Nachbarn werden für jeden Merkmalsvektor $r$ die $k$ nächsten Nachbarn innerhalb der Vergleichsdaten betrachtet. $k$ ist eine kleine Zahl, die teilerfremd zu der Zahl der Klassen ist. Der Merkmalsvektor $r$ wird derjenigen Klasse zugeordnet, die am häufigsten unter den $k$ nächsten Nachbarn vertreten ist.¹

Aus den Vergleichsdaten können Datensätze entfernt werden, die gleichsam im inneren einer Wolke von Datensätzen einer selben Klasse liegen. Dadurch wird die Zuordnung schneller. Dies tut der Konstruktor Kn.Classifier. Das mit dem Konstruktor erzeugte Objekt wird an die Funktion Kn.mcrate übergeben zur Berechnung der Rate falscher Zuordnungen. Kn.manhattan ist die Vergleichsfunktion für zwei Merkmalsvektoren. Sie liefert für nominale Daten die Zahl nicht übereinstimmender Merkmalswerte. Kn.Create ist ein Schalter zur Auswahl des Konstruktors (= programmiertechnisches Detail).

   julia> clobjkn = Kn.Classifier(dattraining, atlcagalep, Kn.manhattan, 1, Kn.Create);
   size ixfalse: 1692 selixfalse: 20
   size ixfalse: 1782 selixfalse: 20
   size ixfalse: 107 selixfalse: 21

   julia> size(clobjkn.dfset)
   (76, 24)
   
   julia> Kn.mcrate(clobjkn, 1, dattest)
   0//1

Die Vergleichsdaten umfassen lediglich 76 Datensätze. Dennoch gelingt es, die Merkmalsvektoren der Testdaten alle richtig zu klassifizieren, auch wenn nur ein nächster Nachbar für den Vergleich berücksichtigt wird.

Naive Bayes

Der Bayes-Schätzer schätzt anhand der Trainingsdaten bedingte Wahrscheinlichkeiten für die Zugehörigkeit eines Merkmalsvektors zu den Klassen. Beim sogenannten naiven Bayes-Verfahren wird unterstellt, dass die Merkmale statistisch unabhängig voneinander sind. Auch wenn dies in konkreten Anwendungen in der Regel nicht erfüllt ist, liefert das Verfahren brauchbare Schätzwerte und einen Wert für eine Wahrscheinlichkeit, dass die Schätzung zutrifft.² Auch hier wertet ein Konstruktor die Trainingsdaten aus: Nb.Classifier.

   julia> clobjnb = Nb.ClassifierDiscrete(dattraining, atlcagalep);

   julia> Nb.mcrate(clobjnb, dattest)
   id: 206	pred: e, is: p	p: 0.761759
   id: 1704	pred: e, is: p	p: 0.972972
   id: 1917	pred: e, is: p	p: 0.682604
   id: 1990	pred: e, is: p	p: 0.931189
   id: 2479	pred: e, is: p	p: 0.903301
   id: 3398	pred: e, is: p	p: 0.978988
   id: 5465	pred: e, is: p	p: 0.999198
   id: 5572	pred: e, is: p	p: 0.993965
   id: 5806	pred: e, is: p	p: 0.610889
   id: 7534	pred: p, is: e	p: 0.510299
   5//81

Die Fehlerquote liegt hier bei 5 unter 81 also 6,2 Prozent. Gerade im Falle von Pilzen möchte man kein Risiko eingehen und daher nur Schätzungen verwenden mit einer besonders sicheren Zuordnung.

   julia> Nb.mcrate(clobjnb, dattest, 0.9995)
   (0//1, 25//162)

Legt man die Schwelle auf den Wert von 0.9995, um falsche Zuordnungen auszuschließen, muss in 25 von 162 Fällen eine Entscheidung offen bleiben, d.h. etwas mehr als 15 Prozent der Pilze würden sicherheitshalber nicht verwendet, obwohl sie möglicherweise eßbar sind. Wir werden sehen, dass bei der Berücksichtigung von einer kleineren Zahl von Merkmalen bessere Ergebnisse erzielt werden können.

Entscheidungbaum

In einem Entscheidungsbaum ist jedem Knoten ein Merkmal zugeordnet, das für eine Entscheidung in diesem Knoten herangezogen wird. Solange durch einen Knoten nicht alle Elemente der Trainingsdaten genau einer Klasse angehören und solange die Menge der aufzuteilenden Daten nicht zu klein ist, wird der Knoten in weitere Zweige aufgeteilt.³ In den Endknoten oder Blättern gehören schließlich alle Elemente einer selben Klasse an, oder ihre Zahl ist so klein, dass eine weitere Unterteilung nicht sinnvoll erscheint.

   julia> clobjt = Td.Tree(dattraining, atlcagalep);
   tree a5 Info: 0.90583
   tree a20 Info: 0.14446
   tree a22 Info: 0.26901
   tree a3 Info: 0.81128
   tree a8 Info: 0.67895

Die Entscheidung, welches Merkmal zur Aufteilung eines Knotens verwendet wird, wird anhand des Zuwachses an Information getroffen, der durch die Aufteilung erreicht wird. Der entstandene Baum hat insgesamt fünf Verzweigungen. Die gesamte Struktur des Baumes zeigt Td.printtree

   julia> Td.printtree(clobjt)
   a5: total:    7962
   a5:p-p    251
   a5:f-p   2113
   a5:n
   a5:n/a20:n-e   1317
   a5:n/a20:w
   a5:n/a20:w/a22:g-e    282
   a5:n/a20:w/a22:w-e    187
   a5:n/a20:w/a22:l
   a5:n/a20:w/a22:l/a3:n-e     24
   a5:n/a20:w/a22:l/a3:c-e     24
   a5:n/a20:w/a22:l/a3:w-p      8
   a5:n/a20:w/a22:l/a3:y-p      8
   a5:n/a20:w/a22:p-e     38
   a5:n/a20:w/a22:d
   a5:n/a20:w/a22:d/a8:b-e      7
   a5:n/a20:w/a22:d/a8:n-p     32
   a5:n/a20:k-e   1274
   a5:n/a20:o-e     48
   a5:n/a20:b-e     48
   a5:n/a20:r-p     70
   a5:n/a20:h-e     47
   a5:n/a20:y-e     47
   a5:c-p    188
   a5:m-p     36
   a5:l-e    390
   a5:s-p    563
   a5:a-e    390
   a5:y-p    570

Der Baum hat 24 Pfade und eine maximale Tiefe von 5 und klassifiziert alle Merkmalsvektoren der Testdaten korrekt. Von den 22 Variablen in den Daten genügen fünf für die Klassifizierung: a5, a20, a22 a3, a8.

julia> Td.mcrate(clobjt, dattest)
0//1

Die Übersicht über den Datensatz enthält eine Beschreibung der Merkmale. Das Merkmal a5 ist der Geruch in folgenden Ausprägungen:

odor: almond=a, anise=l, creosote=c, fishy=y, foul=f, musty=m, none=n, pungent=p, spicy=s

Das Merkmal a5 ist an prominenter Stelle im Entscheidungsbaum, der zuverlässig die Giftigkeit von Pilzen bewertet. Im Wald mag es jedoch schwierig sein, den Geruch eines Pilzes festzustellen und beispielsweise zwischen ‚Mandel‘, ‚Anis‘ und ‚würzig‘ zu unterscheiden.

Daher wird hier ein weiterer Entscheidungsbaum aufgebaut, der dieses Merkmal nicht heranzieht.

   julia> clobjt2 = Td.Tree(dattraining, atlsa5);
   tree a20 Info: 0.47907
   tree a8 Info: 0.43628
   tree a21 Info: 0.33201
   tree a2 Info: 0.30888
   tree a11 Info: 0.99964
   tree a8 Info: 0.36552
   tree a21 Info: 0.32756
   tree a10 Info: 0.46905
   tree a2 Info: 0.31991
   tree a11 Info: 1.0
   tree a8 Info: 0.19515
   tree a9 Info: 0.69832
   tree a22 Info: 0.45948
   tree a3 Info: 0.70075
   tree a11 Info: 0.57879
   
   julia> Td.printtree(clobjt2)
   a20: total:    7962
   a20:n
   a20:n/a8:b-e   1615
   a20:n/a8:n
   a20:n/a8:n/a21:v
   a20:n/a8:n/a21:v/a10:e
   a20:n/a8:n/a21:v/a10:e/a2:f
   a20:n/a8:n/a21:v/a10:e/a2:f/a11:e-e     24
   a20:n/a8:n/a21:v/a10:e/a2:f/a11:b-p     24
   a20:n/a8:n/a21:v/a10:e/a2:s-p     54
   a20:n/a8:n/a21:v/a10:e/a2:y-p     32
   a20:n/a8:n/a21:v/a10:t-e     48
   a20:n/a8:n/a21:s-p    109
   a20:n/a8:n/a21:y-e     24
   a20:w
   a20:w/a9:g-e     96
   a20:w/a9:w
   a20:w/a9:w/a22:g-e     94
   a20:w/a9:w/a22:w-e     92
   a20:w/a9:w/a22:l
   a20:w/a9:w/a22:l/a3:n-e     23
   a20:w/a9:w/a22:l/a3:c-e     24
   a20:w/a9:w/a22:l/a3:w-p      7
   a20:w/a9:w/a22:l/a3:y-p      4
   a20:w/a9:w/a22:p-e     40
   a20:w/a9:w/a22:d
   a20:w/a9:w/a22:d/a11:c-p     18
   a20:w/a9:w/a22:d/a11:b-e      8
   a20:w/a9:w/a22:d/a11:?-p     32
   a20:w/a9:e-e     93
   a20:w/a9:b-p   1696
   a20:w/a9:p-e     95
   a20:w/a9:y-p     20
   a20:k
   a20:k/a8:b-e   1573
   a20:k/a8:n
   a20:k/a8:n/a21:v
   a20:k/a8:n/a21:v/a2:f
   a20:k/a8:n/a21:v/a2:f/a11:e-e     22
   a20:k/a8:n/a21:v/a2:f/a11:b-p     23
   a20:k/a8:n/a21:v/a2:s-p     56
   a20:k/a8:n/a21:v/a2:y-p     32
   a20:k/a8:n/a21:s-p    111
   a20:k/a8:n/a21:y-e     23
   a20:o-e     48
   a20:b-e     48
   a20:u-e     42
   a20:r-p     72
   a20:h
   a20:h/a8:b-p   1544
   a20:h/a8:n-e     48
   a20:y-e     48
   
   size(clobjt2)
   (37, 7)

Der neue Entscheidungsbaum ist größer und enthält jetzt 37 Pfade. Die maximale Tiefe beträgt 7. Die Liste der Variablen ist: a20, a8, a9, a21, a22, a2, a11. Durch den Verzicht auf a5 müssen nun also sieben, statt fünf Merkmalen ausgewertet werden. Auch für diesen Baum sind alle Zuordnungen für die Testdaten korrekt.

 julia> Td.mcrate(clobjt2, dattest)
0//1

Möchten wir die Zahl der Merkmale auf sechs verringern und verzichten wir auf das Merkmal a2, ergibt sich ein Baum mit 44 Pfaden und einer maximalen Tiefe von wiederum 7. Ein Datensatz aus den Testdaten wird nicht richtig zugeordnet. Setzen wir eine Schwelle für die Bestimmtheit des Ergebnisses, so werden in diesem Fall Knoten, die mehr als eine Klasse enthalten, ausgeschlossen. Es gibt jetzt keine fehlerhaften Zuordnungen mehr, aber für 2,5% der Datensätze ist die Zuordnung unklar.

   julia> clobjt3 = Td.Tree(dattraining, atlopt2);
   tree a20 Info: 0.4823
   tree a8 Info: 0.4286
   tree a21 Info: 0.3382
   tree a22 Info: 0.2665
   tree a9 Info: 0.24631
   a11: e 14
   a11: e 14
   a11: e 14
   tree a8 Info: 0.36969
   tree a21 Info: 0.3277
   tree a22 Info: 0.13997
   tree a9 Info: 0.25756
   a11: e 13
   a11: e 14
   a11: e 13
   tree a9 Info: 0.43033
   a11: b 27
   a11: b 27
   tree a8 Info: 0.19079
   tree a9 Info: 0.69558
   tree a22 Info: 0.46193
   tree a21 Info: 0.70767
   tree a21 Info: 0.57879

   julia> size(clobjt3)
   (44, 7)

   julia> Td.mcrate(clobjt3, dattest)
   1//162

Naive Bayes (reprise)

Wie oben erwähnt, wird für den Aufau des Entscheidungsbaums der Informationsgehalt der Merkmale untersucht. Diesen kann man sich auch für den Bayes-Schätzer zu Nutze machen (siehe Tabelle). Der Informationsgehalt des Merkmals a5 ist mit Abstand am größten. Es folgt ein breites Mittelfeld, in dem sich a20 und a9 noch etwas absetzen. Die Merkmale a3, a2, a17, a6, a10 und a16 tragen bezogen auf die gesamten Trainingsdaten nur wenig Information.

   julia> dfinfo = sort(Td.infodf(dattraining, atlcagalep), :info, rev = true)
   22×3 DataFrame
   │ Row │ variable │ h        │ info       │
   │     │ Symbol   │ Float64  │ Float64    │
   ├─────┼──────────┼──────────┼────────────┤
   │ 1   │ a5       │ 0.093227 │ 0.905893   │
   │ 2   │ a20      │ 0.51682  │ 0.4823     │
   │ 3   │ a9       │ 0.582498 │ 0.416622   │
   │ 4   │ a19      │ 0.680688 │ 0.318433   │
   │ 5   │ a12      │ 0.713776 │ 0.285344   │
   │ 6   │ a13      │ 0.727893 │ 0.271227   │
   │ 7   │ a14      │ 0.745405 │ 0.253715   │
   │ 8   │ a15      │ 0.757077 │ 0.242044   │
   │ 9   │ a8       │ 0.769967 │ 0.229154   │
   │ 10  │ a21      │ 0.797033 │ 0.202088   │
   │ 11  │ a4       │ 0.807628 │ 0.191492   │
   │ 12  │ a22      │ 0.844362 │ 0.154758   │
   │ 13  │ a11      │ 0.864387 │ 0.134733   │
   │ 14  │ a7       │ 0.897625 │ 0.101495   │
   │ 15  │ a1       │ 0.950626 │ 0.0484943  │
   │ 16  │ a18      │ 0.961087 │ 0.0380338  │
   │ 17  │ a3       │ 0.963069 │ 0.0360517  │
   │ 18  │ a2       │ 0.971027 │ 0.0280932  │
   │ 19  │ a17      │ 0.975024 │ 0.0240961  │
   │ 20  │ a6       │ 0.984842 │ 0.014278   │
   │ 21  │ a10      │ 0.991336 │ 0.00778473 │
   │ 22  │ a16      │ 0.99912  │ 0.0        │

Wendet man den Bayes-Schätzer nur mit den Merkmalen a5, a20 und a9 an, nimmt die Fehlerrate auf 1 Prozent ab.

   julia> clobjnbi3 = Nb.ClassifierDiscrete(dattraining, [:a5, :a20, :a9])
   Main.NaiveBayes.ClassifierDiscrete
   attributes: Symbol[:a5, :a20, :a9]
   dfprob: 2×6 DataFrame. Omitted printing of 4 columns
   │ Row │ class  │ pc       │
   │     │ String │ Float64  │
   ├─────┼────────┼──────────┤
   │ 1   │ p      │ 0.482542 │
   │ 2   │ e      │ 0.517458 │

   julia> Nb.mcrate(clobjnbi3, dattest)
   id: 4534   	pred: p, is: e	p: 0.77995
   id: 5127   	pred: e, is: p	p: 0.967108
   1//81

   julia> 1 / 81
   0.012345679012345678

Mit den Merkmalen, die in den Entscheidungsbaum eingehen, erhält man ebenfalls ein gutes Klassifizierungsergebnis.

   julia> clobjnbtree = Nb.ClassifierDiscrete(dattraining, [:a5, :a20, :a22, :a3, :a8])
   Main.NaiveBayes.ClassifierDiscrete
   attributes: Symbol[:a5, :a20, :a22, :a3, :a8]
   dfprob: 2×8 DataFrame. Omitted printing of 6 columns
   │ Row │ class  │ pc       │
   │     │ String │ Float64  │
   ├─────┼────────┼──────────┤
   │ 1   │ p      │ 0.482542 │
   │ 2   │ e      │ 0.517458 │

   julia> Nb.mcrate(clobjnbtree, dattest)
   id: 5274   	pred: p, is: e	p: 0.695801
   id: 5548   	pred: p, is: e	p: 0.695801
   1//81

julia> VERSION
v"1.0.2"

1. Kubat: An Introduction to Machine Learning. Springer: Cham 2015, S. 43 ↩

2. Kubat: An Introduction to Machine Learning. Springer: Cham 2015, S. 25 ↩

3. Kubat: An Introduction to Machine Learning. Springer: Cham 2015, S. 117 ↩