Information Technology Reference
In-Depth Information
G = m
G = w
p
orig
R =rR= r
R =rR= r
S
=
s
0
0
0.01
0.04
S = s
0.2
0.3
0.09
0.36
Tabe l l e 24 . 2 : Dre id imens i ona l e Be i sp i e l ve r t e i lung
3. Beginne mit G
=(
V
, )
und füge für jedes A
i
eine Kante von
jedem Knoten in
i
nach A
i
ein.
4. Gib G zurück.
Beispiel 24.5
Betrachten wir die in Tabelle 23.1 auf Seite 362 gegebene dreidimensionale
Ve r t e i l ung , d i e a l s Ta b e l l e 24 . 2 h i e r no c h e i nma l wi ed e rh o l t i s t . Es s e i d i e f o l g end e Kno t en -
ordnung angenommen:
G S R
Wir wissen aus Abschnitt 23.1.2 (und den Verteilungen in Abbildung 23.1), dass in der
Ve r t e i l ung p
GSR
nur die folgende (bedingte) Unabhängigkeit gilt (und natürlich deren sym-
metrisches Gegenstück):
S
p
GSR
R | G
Beginnen wir nun, die Mengen
i
zu finden. Wir beginnen mit jeweils allen Vorgängern als
Kandidatenmenge:
i
= {
A
1
,...,
A
i
1
}
.DannwerdenwirsovieleAttributewiemöglich
aus
i
entfernen, bis die bedingte Unabhängigkeit nicht mehr erfüllt wäre. Diese noch resul-
tierenden Attribute werden die Eltern von A
i
.Eskannsein,dasskeineinzigesAttributaus
der initialenMenge
i
entfernt werden kann, dann werden alle Vorgänger von A
1
,...,
A
i
1
von A
i
seine Eltern.
1.
G
besitzt keine Vorgänger, demnach ist (und bleibt)
G
=
.
2. Für
S
beginnen wir mit
S
= {G}
.Dieerste(undeinzigeReduktionvon
S
ist
diejenige zur leeren Menge. Folglich testen wir, ob
S
p
GSR
G |
gilt. Dem ist nicht
so, wie man leicht nachprüft. Andere Möglichkeiten,
S
zu setzen, gibt es nicht, also
bleibt es bei der initialen Belegung
S
= {G}
.
3. Wir starten mit
R
= {
G
,
S
}
und prüfen die drei folgenden Möglichkeiten auf Gül-
tigkeit:
R
p
GSR
S
|
G,
R
p
GSR
G
|
S
und
R
p
GSR
G, S
|
Die einzig gültige Unabhängigkeit ist
R
p
GSR
S
|
G
,waszu
R
= {
G
}
führt.
Folglich erhalten wir den folgenden Graphen, der in diesem Fall nicht nur eine minimale
Unabhängigkeitskarte, sondern auch eine perfekte Karte ist:
S
G
R
Schlussendlich können wir die beiden zentralen Strukturen definieren, die man
unter dem Oberbegriff
Graphische Modelle
zusammenfasst.