Information Technology Reference
In-Depth Information
a
dom
(
A
)
b
dom
(
B
)
p
V
\{
A
,
B
}
A
i
=
a
i
=
p
V
A
i
=
a
i
V
A
i
V
\{
A
,
B
}
A
i
2.1. Falls
A
i
=
a
i
·
p
V
\{
A
,
B
}
A
i
=
a
i
p
V
V
A
i
A
i
V
\{
A
,
B
}
=
A
i
=
a
i
·
p
V
\{
B
}
A
i
=
a
i
p
V
\{
A
}
A
i
V
\{
A
}
A
i
V
\{
B
}
so entferne die Kante
(
A
,
B
)
aus E (gilt ebenfalls für
(
B
,
A
)
).
4. Gib G zurück.
Der im Schritt 2.1. durchgeführte Unabhängigkeitstest nutzt den folgenden Sach-
verhalt in ungerichteten Graphen aus: Das Fehlen einer Kante (
A
,
B
) in einem un-
gerichteten Graphen
G
=(
V
,
E
) bedeutet, dass eben jene beiden Knoten
A
und
B
durch alle anderen Knoten u-separiert werden:
A
,
B
V
,
A
=
B
:
(
A
,
B
)
/
E
A
G
B
|
V
\{
A
,
B
}
Da der Graph
G
eine Unabhängigkeitskarte bezüglich einer gegebenen Verteilung
p
V
sein soll, muss sichergestellt sein, dass alle ableitbaren u-Separationen auch als
bedingte Unabhängigkeiten in
p
V
gelten. Die Separation
A
G
B
|
V
\{
A
,
B
} in
G
muss also folgende Korrespondenz in
p
V
haben:
P
(
A
,
B
|
V
\{
A
,
B
})=
P
(
A
|
V
\{
A
,
B
}) ·
P
(
B
|
V
\{
A
,
B
})
Durch Äquivalenzumformungen (zweimal mit
P
(
V
\{
A
,
B
}) multiplizieren) erhal-
ten wir das in Schritt 2.1. genutzte Testkriterium:
P
(
A
,
B
|
V
\{
A
,
B
})=
P
(
A
|
V
\{
A
,
B
}) ·
P
(
B
|
V
\{
A
,
B
})
P
(
V
)=
P
(
A
|
V
\{
A
,
B
}) ·
P
(
V
\{
A
})
P
(
V
) ·
P
(
V
\{
A
,
B
})=
P
(
V
\{
B
}) ·
P
(
V
\{
A
})
Die so resultierende Unabhängigkeitskarte ist offensichtlich minimal: Es kann keine
weitere Kante entfernt werden (denn wir haben ja alle getestet), ohne eine ungültige
bedingte Unabhängigkeit zu kodieren.
Algorithmus 24.4 (Minimale ger. Unabh.karte anhand einer Verteilung)
Eingabe:
Eine Verteilung p
V
über einer
Menge V
= {
A
1
,...,
A
n
}
von Attributen.
Ausgabe:
Minimale gerichtete Unabhängigkeitskarte G
=(
V
,
E
)
von p
V
.
1.
Bestimme eine beliebige Attributordnung A
1
,...,
A
n
.
2.
Finde für jedes A
i
eine minimale Vorgängermenge
i
,dieA
i
(bedingt)
unabhängig von
{
A
1
,...,
A
i
1
}\
i
macht.
