Clusterverfahren
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. Dazu ist es sinnvoll, zunächst eine übersichtliche Zahl von Klassen zur Verfügung zu haben, in die man die Pilze einteilen kann, um dann später eine feinere Unterscheidung vorzunehmen. 1981 wurde 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.
Der Datensatz wird in einen sogenannten DataFrame eingelesen. Die Datenquelle ist hier ein Feather-File könnte aber genausogut eine Textdatei im CSV-Format sein.
julia> fileagalep = "../../data/UCI/agaricus-lepiota.feather"
"../../data/UCI/agaricus-lepiota.feather"
julia> datagalep = DataFrame(load(fileagalep))
8124×24 DataFrame. Omitted printing of 16 columns
│ Row │ id │ class │ a1 │ a2 │ a3 │ a4 │ a5 │ a6 │
│ │ Int64 │ String │ String │ String │ String │ String │ String │ String │
├──────┼───────┼────────┼────────┼────────┼────────┼────────┼────────┼────────┼
│ 1 │ 1 │ p │ x │ s │ n │ t │ p │ f │
│ 2 │ 2 │ e │ x │ s │ y │ t │ a │ f │
│ 3 │ 3 │ e │ b │ s │ w │ t │ l │ f │
│ 4 │ 4 │ p │ x │ y │ w │ t │ p │ f │
│ 5 │ 5 │ e │ x │ s │ g │ f │ n │ f │
⋮
│ 8119 │ 8119 │ p │ k │ y │ n │ f │ f │ f │
│ 8120 │ 8120 │ e │ k │ s │ n │ f │ n │ a │
│ 8121 │ 8121 │ e │ x │ s │ n │ f │ n │ a │
│ 8122 │ 8122 │ e │ f │ s │ n │ f │ n │ a │
│ 8123 │ 8123 │ p │ k │ y │ n │ f │ y │ f │
│ 8124 │ 8124 │ e │ x │ s │ n │ f │ n │ a │
Der Beitrag Klassifizierung von Pilzen zeigt verschiedene Verfahren zur Klassifizierung, die eine Entscheidung über die Essbarkeit unterstützen.
Um zu einer übersichtlichen Zahl von Klassen zu gelangen, können Clusterverfahren weiterhelfen. Voraussetzung ist, dass sich zwischen je zwei Elementen eine Ähnlichkeit oder ein Grad der Verschiedenheit angeben lässt.
Der Datensatz zu den Pilzen umfasst insgesamt etwas mehr als 8100 Elemente. Für die Clusterung wird zunächst für jedes Paar die Ähnlichkeit oder der Grad der Verschiedenheit bestimmt. Der Aufwand hierfür wächst quadratisch mit der Zahl der Elemente. Da sich die Struktur aber auch schon bei einer Teilmenge des Datensatzes erkennen lässt, ist es sinnvoll, das Verfahren auf eine solche Teilmenge anzuwenden. Hier wurden 406 Elemente zufällig ausgewählt.
julia> using Random
julia> nall = size(datagalep, 1)
8124
julia> pcluster = 0.05 # Auswahlwahrscheinlichkeit für das Clusterset
0.05
julia> datagacluster = datagalep[randsubseq(1:nall, pcluster), :]
406×24 DataFrame. Omitted printing of 16 columns
│ Row │ id │ class │ a1 │ a2 │ a3 │ a4 │ a5 │ a6 │
│ │ Int64 │ String │ String │ String │ String │ String │ String │ String │
├─────┼───────┼────────┼────────┼────────┼────────┼────────┼────────┼────────┤
│ 1 │ 5 │ e │ x │ s │ g │ f │ n │ f │
│ 2 │ 36 │ e │ x │ f │ y │ t │ l │ f │
│ 3 │ 38 │ p │ x │ y │ n │ t │ p │ f │
│ 4 │ 64 │ e │ b │ y │ y │ t │ l │ f │
│ 5 │ 88 │ e │ x │ s │ w │ t │ l │ f │
⋮
│ 401 │ 8062 │ p │ k │ s │ n │ f │ s │ f │
│ 402 │ 8070 │ e │ k │ s │ n │ f │ n │ a │
│ 403 │ 8073 │ p │ k │ y │ e │ f │ f │ f │
│ 404 │ 8080 │ p │ k │ y │ e │ f │ f │ f │
│ 405 │ 8091 │ p │ k │ s │ n │ f │ f │ f │
│ 406 │ 8115 │ p │ f │ y │ c │ f │ m │ a │
Cr.manhattan ist die Vergleichsfunktion für zwei
Merkmalsvektoren. Sie liefert für nominale Daten die
Zahl nicht übereinstimmender Merkmalswerte. Im folgenden Beispiel unterscheiden
sich die Elemente 17 und 212 in 15 Merkmalen, sie sind einander also eher
unähnlich. Das Ergebnis wird anders ausfallen, wenn Sie es selbst berechnen, da
die Elemente in datagacluster zufällig ausgewählt sind.
julia> include("../../misc-jl/Clusters.jl"); Cr = Clusters
julia> row017 = datagacluster[17, :];
julia> row212 = datagacluster[212, :];
julia> Cr.manhattan(row017, row212, atlcagalep)
15.0
Für die Clusterung ist weiter festzulegen, wie der Abstand zwischen zwei Clustern und bestimmt werden soll. Beispielsweise kann man festlegen, dass jeweils die einander am nächsten liegenden Elemente aus und gesucht werden. Ihr Abstand soll dann der Abstand der Cluster sein. Dieses Verfahren wird single linkage genannt. complete linkage heißt das Verfahren, bei dem man die am weitesten voneinander entfernten Elemente heranzieht. Einen mittleren Abstand zwischen einem bestehenden Cluster zu einem neuen Cluster , der aus und gebildet wird, erhält man aus der rekursiven Berechnung der Abstände nach:
und : Größe der Cluster und
und : Abstände der Paare
und .
Um die Clusterung durchzuführen, wird ein Objekt vom Typ Cluster erzeugt.
Es umfasst eine Knotenliste und eine Distanztabelle. Dem Konstruktor aus dem
Modul Clusters Code werden als Argumente übergeben:
der Datensatz, eine Funktion zur Bestimmung der
Abstände und eine Liste der relevanten Attribute. Hier werden alle Attribute
herangezogen außer der ID und der Klasse.
julia> atlcagalep = setdiff(names(datagalep), [:id, :class])
julia> crobj = Cr.Cluster(datagacluster, Cr.manhattan, atlcagalep)
Für den Typ Cluster ist die Funktion iterate definiert, wobei ein
Interationsschritt jeweils einem Clusterschritt entspricht.
function iterate(cl::Cluster)
nnodes = cl.nodes
(nnodes < 2) && @warn("Cannot reset cluster object")
return cl, nnodes
end
function iterate(cl::Cluster, nnodes::Int)
if nnodes == 1
return nothing
else
mergeavlinkage!(cl)
return cl, cl.nnodes
end
end
Über eine einfache Schleife können jetzt die Elemente in crobj geclustert
werden. Dabei wird über eine Comprehension gleich ein Array erzeugt, der Werte für die nicht
erklärte Streuung in jedem Schritt enthält.
Die Funktion Cr.variance berechnet die nicht erklärte Streuung.
julia> clvar = [Cr.variance(cl) for cl in crobj]
406-element Array{Float64,1}:
0.0
1.7495288151715682e-5
3.4990576303431364e-5
5.248586445514705e-5
6.998115260686273e-5
8.747644075857841e-5
0.0001049717289102941
⋮
0.46940064473041054
0.5349035998983205
0.7585496123545623
0.7862650550406312
0.9732654230546622
1.0019818693912548
Alternativer Code mit der gleichen Funktion:
julia> clvar = Float64[]
0-element Array{Float64,1}
julia> for cl in crobj
push!(clvar, Cr.variance(cl))
end
Die nicht erklärte Streung wächst, je größer die Cluster werden.
Bei elf und sieben verbleibenden Clustern hat die Kurve jeweils einen Knick:
Je nach Fragestellung, die eventuell vorgibt, wieviele Cluster gebildet werden sollen, sind elf oder sieben Cluster ein guter Ausgangspunkt für einen weiteren Analyseschritt.
Das zeigt sich auch im Dendrogramm. Von jedem Element geht ein Pfad aus, der
zeigt, mit welchem anderen Element es zu einem Cluster zusammengeführt wird. Es
ergibt sich eine Baumstruktur.
Hier sind zwei Versionen eines Dendrogramms gezeigt. Zunächst
eine Darstellung, welche die Struktur deutlich zeigt, dann eine Darstellung, bei
der die Varianz auf der Ordinate aufgetragen ist. Siehe Funktionen
plotstructdendrogram und plotdendrogram in Clusters.
Fragen, Anregungen und Hinweise zu Julia oder zu dieser Seite sind willkommen per E-Mail .
julia> VERSION
v"1.1.0"