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.
Search WWH ::




Custom Search