Information Technology Reference
In-Depth Information
Der K2-Algorithmus
Die vorgestellte K2-Metrik berechnet auf Basis einer gegebenen Datenbank von Bei-
spielfällen
D
die Güte eines Netzkandidaten
B
S
.Wirhabengesehen,dassdieMenge
aller Netzkandidaten
B
R
für eine gegebene Attributmenge
R
viel zu groß wird, um
jeden einzelnen Kandidaten separat zu betrachten. Daher muss die Suche so gestaltet
sein, dass nur eine rechentechnisch verträglich große Teilmenge von B
R
durchsucht
werden muss.
Der im Folgenden vorgestellte Algorithmus verwendet als Bewertungsfunktion
die K2-Metrik und als Suchheuristik eine gierige Suche (engl.
greedy search
). Auf
den Knoten (Attributen) muss eine topologische Ordnung
5
erklärt sein.
Die Suche beginnt mit einem „Netz“, das ausschließlich aus
n
isolierten Knoten
besteht. Die Elternmengen pa
(
A
i
)
sind also zu Beginn leer. Die Indizierung mit 1
i
n
stelle die topologische Ordnung dar. Die Funktion
q
i
ist definiert als lokaler
K2-Wert des Knotens
A
i
mit der angenommenen Elternattributmenge
M
:
q
i
(
M
)=
K2
local
(
A
i
|
D
)
mit pa
(
A
i
)=
M
Es werden dann nacheinander für alle Knoten
A
i
die Elternmengen pa
(
A
i
)
nach
folgendem Prinzip bestimmt:
1. Es wird für den elternlosen Knoten
A
i
das Gütemaß
q
i
(
)
bestimmt.
2. Danach werden alle Vorgängerknoten
{
A
1
,...,
A
i
1
}
einzeln nacheinander als
potentieller Elternknoten eingefügt und das Gütemaß neu berechnet. Es sei
Y
derjenige Knoten, der die beste Güte erreicht:
Y
= argmax
1
l
i
1
q
i
({
A
l
})
Diese beste Güte habe den Wert
g
=
q
i
({
Y
}).
3. Ist dieser Wert
g
besser als
q
i
(),sowirdderKnoten
Y
permanent als Elternk-
noten eingefügt: pa(
A
i
)={
Y
}
4. Die Schritte 2 und 3 werden wiederholt, um die Elternmenge zu erweitern, bis
entweder keine potentiellen Elternknoten mehr vorhanden sind, kein Knoten
die Güte verbessert oder eine (vorher anzugebende) Maximalanzahl von El-
ternknoten erreicht ist.
Algorithmus 24 zeigt den Ablauf vollständig als Pseudocode. Abbildung 26.3
zeigt den Ablauf an einem Beispiel.
5
Der Begriff der topologischen Ordnung wurde in Definition 23.33 auf Seite 371 eingeführt.
