Post on 12-Dec-2018
transcript
Universität HamburgFakultät für Mathematik,Informatik und Naturwissenschaften
Hausarbeit im Seminar:Verteilte Systeme und Informationssysteme
Duplikatenerkennung in XML
Danny Patrick Gerome Schubert
5schuber@informatik.uni-hamburg.de
Studiengang Master of Science Informatik
Matr.-Nr. 6747985
Fachsemester 1
Betreuer: Professor Dr. Norbert Ritter
Dipl.-Inform. Fabian Panse
Inhaltsverzeichnis 1
Inhaltsverzeichnis
1 Einleitung 3
2 XML Grundlagen 5
3 Duplikatenerkennung mittels XMLDup 73.1 Konstruktion des Bayesschen Netzes . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze . . . . . . . . . 9
3.3 Auswertung des Bayesschen Netzes . . . . . . . . . . . . . . . . . . . . . . 12
4 DogmatiX 17
5 Praktischer Vergleich zwischen XMLDup und DogmatiX 21
6 Fazit 23
Literaturverzeichnis 25
2 Inhaltsverzeichnis
3
1 Einleitung
Diese Ausarbeitung beinhaltet das Auffinden von Duplikaten innerhalb einer XML- Struk-
tur. Hierfür wird zunächst ein neu entwickelter Ansatz vorgestellt ([LCH13]), welcher auf
der Technik von Bayesschen Netzwerken basiert. Im weiteren Verlauf wird noch ein wei-
terer Ansatz mit DogmatiX vorgestellt. Dieser Ansatz beschreibt den den bis dato “state-
of-the-art“ Standard für die Erkennung von Duplikaten innerhalb einer XML-Struktur.
Warum ist es heutzutage so wichtig Duplikate aus XML-Strukturen zu filtern? Dies be-
gründet sich vor allem in der Tatsache, dass es regelrechten Drang dazu gibt, Daten zu
sammeln. Jedoch ist es aufgrund des Menschen nicht trivial jeden Datensatz nur ein-
mal zu erhalten. Dies liegt daran, dass z.B. eine Person in ein Adressbuch oder in eine
Filmdatenbank (als Schauspieler oder Regisseur) eingefügt werden soll. Nun ist es z.B.
einem Redakteur eines Systems möglich, dies in mehreren unterschiedlichen Variationen
zu notieren. So könnte einmal der Name einmal mit dem Vordernamen abgekürzt und
Nachname ausgeschrieben werden (“M. Mustermann“) abgelegt werden. Ein weiteres
mal könnte dies in umgekehrter Reihenfolge erfolgen. Die Darstellung wäre wie folgt:
“Max M.“.
Um eine solche Datenmenge, welche unnötig viele Elemente enthält zu vereinfachen,
befasst sich diese Arbeit mit der Thematik. Durch die beiden oben aufgeführten Ansätze
wird ein Gefühl dafür geschaffen, wie aufwendig und unter Umständen unabdingbar
Duplikatenerkennung sein kann.
4 1 Einleitung
5
2 XML Grundlagen
Um das Verständnis für die nachfolgenden Kapitel zu stärken, werden zunächst benö-
tigte Grundlagen und Grundbegriffe zum Thema XML erörtert. Bei XML handelt sich
um eine beschreibende Sprache für Daten. D.h. die Daten werden in eine Struktur einge-
fügt, welche grundsätzlich nach Belieben aufgebaut werden kann. Für die Struktur gibt
es eine Bedingung. Sie besagt, dass die beschreibenden Elemente in einer Baumstruktur
angeordnet werden müssen. Somit ergibt sich eine hierarchische Struktur. Nachfolgend
wird sowohl auf die Baumstruktur als auch auf die Beschreibende Sprache eingegangen.
Des Weiteren gilt syntaktische Begebenheiten für die sogenannte “Wohlgeformtheit“ ei-
nes XML-Dokuments zu beachten, jedoch werden wir diese in dieser Arbeit nicht aus-
führen.
In Listing 2.1 ist ein XML-Dokument dargestellt. Teile dieses Dokuments werden in den
nachfolgenden Kapiteln noch beispielhaft verwendet.
Listing 2.1: Beispiel XML-Format basierend auf dem Baum aus Abb. 3.1 [CHL10]
1 <?xml version=’1.0’ encoding=’UTF-8’>
2 <mv>
3 <mv1 year="1983" title="Pros and Cons">
4 <dr1>John S.</dr1>
5 <cst1>
6 <ac1>Templeton P.</ac1>
7 <ac2>H.M. Murdock</ac2>
8 </cst1>
9 </mv1>
10 </mv>
Hinweis: Die erste Zeile aus Listing 2.1 ist die Dokumenttyp-Deklaration. Sie gehört zur
Grundstruktur eines XML-Formats (somit auch zur “Wohlgeformtheit“). Um die Kor-
rektheit zu prüfen gibt es einige Validatoren, wie z.B. vom W3C.1
Wie bereits erwähnt ist die Baumstruktur bei XML vorherrschend. D.h. es gibt ein Wur-
zelelement (engl. root), welches alle anderen Elemente beinhaltet. In unserem Beispiel ist
dies das Element “mv“. Diesem Element können nun Kinder (engl. children) angehängt
werden. Solch ein Kind-Element, wie es “mv1“ darstellt, kann sowohl Attribute wie auch
wiederum untergeordnete Kind-Elemente enthalten.
1https://validator.w3.org/
6 2 XML Grundlagen
Beispiele für Attribute wären hier z.B. “year“ oder “title“. Es befindet sich innerhalb der
Elementdefinition. Es können beliebig viele Attribute an ein Element angefügt werden.
Dies gilt ebenso für die die untergeordneten Kind-Elemente von “mv1“. Es kann eben-
falls beliebig viele Elemente geben. Hier sind z.B. “dr1“ und “cst1“ aufzuführen.
Hinweis: Der hier abgebildete Fall für den Aufbau einer XML-Struktur ist sehr klein.
Diese Struktur kann je nach Wünschen beliebig groß skaliert werden.
Wurzel und Kind-Elemente werden nach dem Vorbild des beschreibenden XML-Formats
angeordnet. Jedoch fällt in Abbildung 2.1 das Schlüsselwort “Parent“ auf. Im vorherigen
Verlauf wurde bereits erläutert, dass es Kind-Elemente gibt. D.h. Elemente welche un-
tergeordnet zu einem Element eingefügt werden. Umgekehrt heißt dies nun, dass die-
ses eingefügte Element eine Elternelement (engl. parent) besitzt. Dieses Elternelement ist
das Element in der Ebene über der eines Kindes. So ist nun “cst1“ ein Kind-Element von
“mv1“ , welches zugleich das Eltern-Element darstellt (parent).
mv1
cst1
@year @title
TempletonP.
ac1 ac2
1983 ProsAndCons
H.M.Murdock
ParentChild
dr1
Abbildung 2.1: Ausschnitt von einem Baum, basierend auf Listing2.1
In diesem kleinen Exkurs im aktuellen Kapitel zum Thema XML Grundlagen wurde
auf die für diese Arbeit wichtigen Punkte eingegangen. So wurde erläutert in welchen
Darstellungsformen XML-Strukturen abgebildet werden können. Des Weiteren wurde
auf Begrifflichkeiten wie Wurzel-, Eltern- und Kind-Elemente eingegangen. Diese bilden
die Grundlage für die weiterführenden Ausführungen.
7
3 Duplikatenerkennung mittels XMLDup
Bayessche Netze (oder auch Netzwerke) sind gerichtete, azyklische Graphen. Im Bereich
der Künstlichen Intelligenz sind diese weit verbreitet. Sie finden dort in Expertensyste-
men zur Wissensrepräsentation Verwendung. In diesem Kapitel wird erörtert, wie Bayes-
sche Netze ebenfalls in einem Ansatz genutzt werden können der XMLDup genannt wird
[LCH13]. Hierbei handelt es sich um eine Methodik zum Erkennen von Duplikaten in
XML.
Zunächst wird eine Struktur gebildet, welche es ermöglicht ein XML-Format in ein Bayes-
sche’s Netz abzubilden. Im Laufe dieses Aufbaues einer Struktur wird deutlich, dass
es einen Mechanismus geben muss, welcher dabei hilft Wahrscheinlichkeiten zu bilden.
Auf diesen wird im zweiten Teil eingegangen. Im dritten Teil geht es um, dass soge-
nannte Pruning (deutsch Beschneiden\Kürzen). Mit Hilfe dieser Technik lässt sich der
Vergleichsprozess optimieren.
3.1 Konstruktion des Bayesschen Netzes
In Abbildung 3.1 sind zwei exemplarische Bäume abgebildet. Diese basieren auf dem
XML Code aus dem Listing 2.1. Bei Baum U’ wurden die Werte und Attribute leicht ver-
ändert. Der Grundsätzliche Aufbau ist jedoch gleich zum XML Listing und Baum U.
mv1
cst1
dr1
@year @title
John S.
TempletonP.
Baum U
ac1 ac2
1983 ProsAndCons
H.M.Murdock
mv1
cst1
dr1
@year @title
J. Smith
T.Peck
Baum U
ac1 ac3
1984 ProsAndCons
Murdock
ac2
B.A.Baracus
Abbildung 3.1: Beispielstruktur im Bezug auf Filme aus [CHL10]
Der nächste Schritt besteht nun daraus, die beiden Bäume zu “Mappen“ (deutsch Ab-
bilden). Das bedeutet die Bäume werden nun miteinander vereinigt. Die Vereinigung
dieser beiden XML Bäume ist in Abbildung 3.2 zu sehen.
8 3 Duplikatenerkennung mittels XMLDup
Vmv11
mv11
Cmv11
cst11
dr11
Ccst11
Vdr11
mv11[year]mv11[title]
ac1*
ac11 ac13
Vac11 Vac13
ac11[value] ac13[value]
ac**
dr11[value]
ac12
Vac12
ac12[value]
ac2*
ac21 ac23
Vac21 Vac23
ac23[value]
ac22
Vac22
ac22[value]ac21[value]
Abbildung 3.2: Beispiel eines gemappten Baumes. Dieser besteht aus Baum U und U’.
[CHL10]
In Abbildung 3.2 sehen Sie den Oberknoten “mv11". Dieser Knoten lässt schlussfolgern,
ob U ein Duplikat von U’ ist oder nicht. Um die Wahrscheinlichkeitswerte zuweisen zu
können, wird “mv11“ zunächst einmal eine binäre Zufallsvariable zugewiesen. Diese Va-
riable kann grundsätzlich nur zwei Zustände annehmen:
Tabelle 3.1: Werte, welche die Variable in mv11 annehmen kann
Wert Zustand Beschreibung
1 active Baum U und U’ sind Duplikate
0 inactive Baum U und U’ sind keine Duplikate
Der Zustand (aus Tabelle 3.1) den “mv11“ enthält, sprich ob die beiden Knoten “mv1“
Duplikate sind, ist von zwei Faktoren abhängig:
1. Sind die Attribute Duplikate oder nicht?
2. Sind die Kind-Elemente Duplikate oder nicht?
Der Knoten “Vmv11“ aus Abb. 3.2 beinhaltet die Attribute von “mv“. Ihm wird eine bi-
näre Zufallsvariable zugewiesen um aussagen zu können, ob die Attribute aus den bei-
den Bäumen gleich sind, sprich Duplikate. Selbiges gilt für den Knoten “Cmv11“. Die-
ser beinhaltet die Kind-Elemente der beiden Bäume und stellt fest ob es sich hierbei
3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze 9
ebenfalls um Duplikate handelt. Wie bei dem Knoten “Vmv11“ wird hier bei “Cmv11“
ebenfalls eine Wahrscheinlichkeit gebildet. Hierfür wird dem Knoten ebenfalls eine bi-
näre Zufallsvariable zugewiesen, die am Ende den entsprechenden Wert enthält ob die
Kinder-Elemente der beiden Bäume U und U’ tatsächlich Duplikate sind. Somit hängt
die Aussage ob es sich wirklich um ein Duplikat handelt, von den Paaren, die aus den
einzelnen Knoten der Bäume U und U’ gebildet werden, ab.
Ähnlich wird für die Knoten “dr“ und “cst“ vorgegangen. Hier werden gleichermaßen
binäre Zufallsvariablen zugewiesen. In diesem Fall sind dies “Ccst11“ und “Vdr11“. Sie
enthalten wiederum die Wahrscheinlichkeiten für die Knoten “cst1“ und “dr1“ aus den
Bäumen U und U’.
Für den Fall, dass es mehrere ähnliche Knoten vorhanden sind, wie anhand “ac**“ zu
sehen ist, wird für jeden einzelnen Knoten geprüft, ob es ein Duplikat gibt. Somit be-
nötigt jedes Element aus beiden Bäumen eine eigene binäre Variable die den Wert der
Wahrscheinlichkeit enthält. Im nächsten Schritt wird jeder Pfad aus Baum U mit jedem
Pfad aus Baum U’ auf Duplikate geprüft.
3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze
Im 3.1 wurde bereits erwähnt, dass es binäre Zufallsvariablen gibt, welche Wahrschein-
lichkeiten enthalten. Sie geben für die Knoten der zu vergleichenden Bäume U und U’
an, ob diese Duplikate sind oder nicht.
Es kann nachfolgend grundsätzlich zwischen zwei Wahrscheinlichkeitstypen unterschie-
den werden:
• A-priori-Wahrscheinlichkeiten:
Exkurs: A-priori-Wahrscheinlichkeiten sind sozusagen eine Vordefinition der Wahr-
scheinlichkeit für einen Standardisierten Zustand. Sofern nichts anderes bekannt
ist, wird diese Wahrscheinlichkeit angenommen und für Berechnungen verwendet.
[CHL10] et. al. gibt wieder, dass es Anwendungsfälle gibt, in welchen es nicht
möglich oder nicht Effizient genug wäre mit berechneten Wahrscheinlichkeiten zu
starten. Hierfür wird eine Standard-Wahrscheinlichkeit in einer Konstanten ka de-
finiert.
10 3 Duplikatenerkennung mittels XMLDup
• Zustands-Wahrscheinlichkeiten:
Es gibt zusätzlich vier Zustands-Wahrscheinlichkeiten die in [CHL10] ausgeführt
werden. Diese werden nachfolgen betrachtet:
1. CP1:
CP1 besagt, dass die Wahrscheinlichkeit für Duplikate auf Ebene der Daten
durch die einzelne paarweisen Übereinstimmungen gegeben ist.
2. CP2:
Die Wahrscheinlichkeit, dass die Kind-Elemente Duplikate sind, wird gegeben
durch die Tatsache, dass die einzelnen Kinder übereinstimmen. Im Falle einer
Unvollständigkeit der Bäume gilt umso mehr Kinder übereinstimmen, desto
größer ist die Wahrscheinlichkeit, dass die Eltern-Elemente ebenfalls überein-
stimmen.
3. CP3:
Die Wahrscheinlichkeit, dass zwei Knoten Duplikate sind, ist durch die Tatsa-
chen gegeben, indem die Kind-Elemente und Ihre Daten gleich sind.
4. CP4:
In einem Satz von Knoten, ist die Wahrscheinlichkeit für den ganzen Satz
durch die Tatsache gegeben, dass die einzelnen Paare in diesem Satz Dupli-
kate sind. Hieraus lässt sich schließen, dass umso mehr Paare Duplikate sind,
desto höher ist die Wahrscheinlichkeit für den ganzen Satz ein Duplikat zu
sein.
• Endgültige Wahrscheinlichkeit:
Nachdem alle A-priori- und Zustands-Wahrscheinlichkeiten definiert wurden, kann
durch nachfolgende Formel, die Endgültige Wahrscheinlichkeit für Duplikate der
Bäume berechnet werden. Nachstehend ist die Formel basierend auf Basis von Abb.
3.2 dargestellt.
(P (mv11 [title]) + P (mv11 [year])) steht für die Zusammengeführten Attribute des
Knoten mv1 aus den Bäumen U und U’. Der Ausdruck
(P (dr11 [title]) +
(1−
∏3i=1 (1− P (ac1i [value])) + 1−
∏3i=1 (1− P (ac2i [value]))
)× 1
2
)steht für die Kind-Elemente dr1 und cst1.
3.2 Berechnung der Wahrscheinlichkeiten für Bayessche Netze 11
Da es nur einen Director gibt, gibt es auch nur eine Wahrscheinlichkeit. Im Fall
des Knotens cst1 für die Schauspieler, gibt es eine Mehrzahl in beiden zu Verglei-
chenden Bäumen. Da diese sich im Aufbau unterscheiden, werden Sie getrennt von
einander behandelt (siehe Abb. 3.2).Zunächst werden Sie für den jeweiligen “Teil-
baum“ mittels Multiplikation berechnet und aufaddiert. Um nun die letztendliche
Wahrscheinlichkeit zu erhalten wird dieses Ergebnis mit 12 multipliziert.
Die Gesamtwahrscheinlichkeit setzt sich schlussendlich aus der Wahrscheinlichkeit
der Attribute und des zweiten Teilbaumes des Casts zusammen. Da diese ebenfalls
den Knoten mv11 aufteilen, wird dies nochmals mit 12 multipliziert. Ist das Ergeb-
nis am Ende 1 bzw. nahe 1 kann von einem Duplikat ausgegangen werden. Ist dies
nicht der Fall, so ist kein Duplikat vorhanden.
12 3 Duplikatenerkennung mittels XMLDup
3.3 Auswertung des Bayesschen Netzes
Für die Auswertung des aufgestellten Netzes von Bayes wird anschließend eine kurze
Einführung gegeben. Die Problematik, welcher sich gestellt werden muss, ist der Zeit-
faktor. Es ist notwendig das gesamte Netz zu analysieren. Hinzu kommt das für jeden
einzelnen Knoten die Wahrscheinlichkeit berechnet werden muss. Dies kann bei einer
Komplexität von O(n × n′) ein zeitraubender Vorgang sein. n und n’ stehen an dieser
Stelle für die Anzahl der Knoten, welche Verglichen werden muss. Aufgrund dieser Tat-
sache haben die Autoren [LCH13] Ansätze gefunden diesen Vorgang zu beschleunigen.
Dafür führen Sie folgende vier Unterpunkte auf:
1. Netzwerk Pruning
Pruning bedeutet wörtlich übersetzt etwas “stutzen“. In Bezug auf das Bayessche
Netz gilt es hier eine Eingrenzungsstrategie zu finden, welche verlustfrei ist. Ver-
lustfrei bedeutet bei [LCH13] et. al. das keine Duplikate verloren gehen bei der
Eingrenzung. Es sollen lediglich die Duplikate wegfallen, die einen eigens festge-
legten Schwellwert nicht erreichen.
Zunächst wird mittels dem Bottom-Up Verfahren allen Variablen der Knoten ei-
ne A-priori-Wahrscheinlichkeit zugewiesen. Durch den enormen Rechenaufwand,
der durch diesen Vorgang entstehen würde, ist die Idee nun, diese Zuweisung erst
anzuwenden, wenn diese unbedingt notwendig ist.
Bei jedem Schritt wird die Ähnlichkeit berechnet und die endgültige Gleichheit
geschätzt unter der Berücksichtigung, dass die bekannten und unbekannten Ähn-
lichkeiten den Wahrscheinlichkeitswert 1 haben. Wenn festgestellt wird, dass die
Netzwerk-Wurzelknoten-Wahrscheinlichkeit den festgelegten Schwellenwert nicht
mehr übertreffen kann, dann wird das Objektpaar abgelegt und die restlichen Be-
rechnungen werden damit vermieden. Der Algorithmus in Form von Pseudocode
ist in [LCH13, Algorithm 1.] et. al. einzusehen.
Diesem wird der gewünschte Schwellenwert und der gemappte Baum aus Abb.
3.2 übergeben. Nach der Übergabe werden zunächst die Knoten sortiert unter der
Annahme der Tatsache, dass alle Wahrscheinlichkeiten 1 betragen. Wenn der aktu-
elle Knoten einer Value (Daten) entspricht, dann wird der Wert aus der Berechnung
der Ähnlichkeit der beiden Knoten angenommen. Wenn hingegen der Knoten noch
Eltern-Elemente besitzt, dann wird die Wahrscheinlichkeit der rekursiven Berech-
nung der Eltern-Elemente entnommen. Die Beweisführung für die Richtigkeit ist
[LCH13, 4.1] et. al. zu entnehmen.
3.3 Auswertung des Bayesschen Netzes 13
Im Anschluss wird ein neuer Schwellwert berechnet, welcher auf dem übergebenen
Schwellwert und dem bisher erzielten Wert basiert. An dieser Stelle wird geprüft,
mit Hilfe der Zustandswahrscheinlichkeiten aus Kap. 3.2, wie die Wahrscheinlich-
keit am besten berechnet werden kann aufgrund der vorliegenden Daten. Nachdem
der Wert berechnet wurde, wir noch abschließend geprüft, ob der Wert für den ge-
mappten Baum weiterhin über dem Schwellwert ist und entscheidet dann ob die
Berechnung beendet wird oder nicht.
2. Effekt von Knotenanordnung beim Pruning
Es kann der Fall eintreten, wie in in Abb. 3.1, dass es unter Umständen auf einer
Seite mehr Knoten gibt als auf der anderen. So wie z.B. bei den Schauspielern. Um
hier nun nicht unnötig Rechenleistung zu verschwenden, da hier ja unter Umstän-
den früher erkannt wird, dass es sich um ein Duplikat handelt, bevor alle Knoten
verglichen wurden, muss es eine spezielle Sortierung geben. Diese basiert auf un-
terschiedlichen heuristischen Ansätzen. Diese Ansätze können sein:
a) Tiefensortierung
b) Durchschnittliche String Größe
c) Unverwechselbarkeit
Je nach Art der Gewichtung beim Sortieren kann jeder Ansatz als einzelner ver-
wendet werden oder eine Kombination aus diesen drei Ansätzen. So wird [LCH13,
4.2] et. al. darauf hingewiesen, dass sich hierdurch eine Zeitersparnis, von bis zu
60% erreichen lässt.
3. Variation des Pruning Faktors
Zu Beginn besitzt jeder Knoten die Wahrscheinlichkeit von 1. Das ist der Pruning
Faktor. Bei der Annahme, dass der Faktor gesenkt werden kann. Dies hat zur Folge,
dass das Netzwerk beschleunigt wird.
Bei der von Anfang an definierten Wahrscheinlichkeit wird der Wert 1 zunächst fest
definiert. Durch diesen Faktor wird grundsätzlich kein Paket verloren. Wird dieser
Faktor nun verkleinert, würde hier jetzt erwartet werden, dass viele Duplikate ver-
loren gehen, jedoch ist dies nicht der Fall.
4. Automatisierung der Pruning-Faktoren-Selektierung
Eine Automatisierung der Selektion des Pruning-Faktors kann nicht nur die Ar-
beit erleichtern sondern auch den Prozess der Duplikatenerkennung optimieren.
14 3 Duplikatenerkennung mittels XMLDup
Hierfür haben die Autoren [LCH13] et. al. einen Ablauf kreiert, welch dies ermög-
licht.
Dieser Ablauf besteht aus drei Schritten:
a) Zuweisen von Pruning-Faktoren an die Attribute
b) Zuweisung auf bestehenden Daten weiterentwickeln (Lernen)
c) Pruning-Faktoren für Innere Knoten
zu a.:Für die Zuweisung von Pruning-Faktoren an die Attribute stellen sich die Autoren
in [LCH13, Kap. 4.4.1] et. al. die Frage, wie die Wahrscheinlichkeit bestimmt wer-
den kann ohne alle Vergleiche berechnen zu müssen.
Die Lösung besteht darin, eine “Mapping-Funktion“ zu finden, welche die Mög-
lichkeit bietet ein Attribut als Eingabe zu bekommen und den dazugehörigen Pru-
ning Faktor zurück zu erhalten.
Hierfür werden die Attribute bestmöglich charakterisiert. So sind folgende 5 Grup-
pen entstanden:
• “Uniqueness features:“
“Uniqueness features:“ sind vorkommen, welche die Attribute auf einzigarti-
ge Art und Weise unterscheiden.
• “Format features:“
Diese Sektion, bezieht sich darauf, welche Information in den Attributen zu
finden ist. Z.B. Text, Zahlen oder beides in Kombination.
• “Content length features“
“Content length features“ vergleichen eine Durchschnittsgröße und den Infor-
mationsgehalt eines Strings, mit den in der “Mapping-Funkton“ vorhandenen
Daten.
• “Absence features“
Lediglich die Anzahl der vermissten Attribute ist hier enthalten. Attribute,
welche in mehreren Objekten vermisst werden, sollten vernachlässigt werden.
• “Occurence features“
Alleinig die Anzahl der Häufigkeit des Auftretens der Attribute wird hier ge-
messen.
zu b.:Zum Lernen für die “Mapping-Funktion“ werden Daten benötigt. Optimale Daten
für das Lernen wären hier z.B. ein Satz von Attributen mit idealen Pruning Fakto-
ren. Das es nicht sehr wahrscheinlich ist solche Datensätze zu erhalten, muss ein
3.3 Auswertung des Bayesschen Netzes 15
alternativer Ansatz dazu gefunden werden.
Die Autoren mit einem leicht modifizierten Ansatz von “Simulated annealing“:
“SA is an algorithm intended to determine the maximum (or minimum) value of
a function with several independent variables, under a fraction of the time needed
to find an absolute maximum (or minimum) in a large search space.“[LCH13, Kap.
4.4.2]
Der Unterschied besteht darin, dass neue Zustände nur akzeptiert werden, wenn
der Verlust der Anteile weniger als 10% beträgt.
So wird nun diese Methodik dafür genutzt um einen gut “gebildete“ “Mapping
Funktion“ zu erhalten, die schlussendlich für die Berechnung des Pruning Faktors
der Daten genutzt werden kann.
zu c.:Bisher behandelten die Ansätze lediglich Pruning Faktoren im Bezug auf Attribu-
te. Jedoch für die Auswertung eines Bayesschen Netzes muss der Pruning Faktor
ebenfalls für jeden Knoten erstellt werden.
An diesem Punkt bedienen sich die Autoren [LCH13] et. al. einer einfachen Lö-
sung. Sie bestimmen für jede Leaf Node den Pruning Faktor. Da diese Faktoren
als Obergrenze angesehen werden können, werden diese Werte entlang des Netz-
werks weiter gereicht, als ob Sie die tatsächlichen Wahrscheinlichkeitswerte wären.
Der an jedem Knoten berechnete Wert kann wiederum als Pruning Faktor verwen-
det werden.
16 3 Duplikatenerkennung mittels XMLDup
17
4 DogmatiX
Nachdem mit der Anwendung von Bayesschen Netzen ein neuer Ansatz für die Duplika-
tenerkennung vorgestellt wurde, wird im nachfolgenden Kapitel der bis dato “state-of-
the-art“ Ansatz für die Duplikatenerkennung in XML vorgestellt. Der Ansatz heißt Dog-
matiX. Hierbei handelt es sich um ein Frameworkaufbau für die Erkennung von XML.
Der Aufbau und Ablauf des Frameworks wird in Abb. 4.2 dargestellt. Aus dieser Ab-
bildung ergeben sich 3 Schritte, auf denen das Framework für die Erkennung von XML
Duplikaten basiert.
Schema Dirty Data
Candidate Definition
Candidate Selection
Duplicate Definition
Description Selection
Duplicate Classification
Duplicate Detection
(1) Candidate Query Exec.
Duplicate Candidates
(2) Description Query Exec.
(3) OD Generation
Object Descriptions (ODs)
(4) Comparison Reduction
(5) Comparisons
Duplicate Pairs
Duplicate Clustering
(6) Duplicate Clustering
Query Formulation
Query Formulation
Abbildung 4.1: Framework Darstellung aus [WN05]
18 4 DogmatiX
1. “Candidate Definition“
Zunächst wird mit der “Candidate Definition“ begonnen. In diesem Schritt ist das
Ziel, zu erkennen welche Objekte für den Vergleich relevant sind um dadurch be-
reits vor dem eigentlichen Vergleich, geeignete Kandidaten ausfindig zu machen.
Dies hat den Vorteil, dass die Anzahl von Vergleichen bereits reduziert wird.
So kann z.B. eine Suche nach Schauspielern gewünscht werden. Dies könnte mit-
hilfe der Bäume aus Abb. 3.1 folgenden Suchpfad ergeben: S = {/mv/cst/ac} .
Aufgrund von dieser Definition ist es nun möglich einen Satz (engl. Set) von XML
Elementen zu liefern, welches den Schauspielern entspricht. Im Bezug auf Abb. 3.1
wäre der zurück gegebene Satz an Daten aci, dass was die Bäume U und U’ an
Schauspieler enthalten. Somit hat man im ersten Schritt seine potentiellen Kandi-
daten für den Vergleich auf Duplikate erhalten.
2. “Duplicate Definition“
Bei der Identifizierung von potentiellen Kandidaten aus dem vorangegangen wird
nicht beachtet, dass es unter Umständen dazu kommen kann, dass auch nicht benö-
tigte Informationen mit identifiziert werden. Dies soll eingedämmt werden, indem
zunächst eine Definition von der Duplikat Struktur erzeugt wird. Nachdem diese
Struktur erstellt wurde, wird diese mit Hilfe von XQuery ausdrücken abgebildet.
Exkurs: XQuery ist eine Abfragesprache die auf XML basiert. Für nähere Informa-
tion können Sie gibt das W3C weiterführende Hilfe.1
Entsprechend führt [CHL10] der Objektbeschreibung wie folgt aus: <text,xpath>.
Hierbei steht die “xpath“ für den absoluten Pfad zum Knoten, welcher für einen
Duplikat Vergleich herangezogen werden soll.“text“ steht hier für die Daten sprich
die “value“ des XML-Knotens.
In Abb. 3.1 benennt der Autor aus [CHL10] die Filmeigenschaften Titel und Di-
rektor als gute Quellen um herauszufinden, ob es sich hierbei um ein Duplikat des
jeweilig anderen Baums handelt. In Tabelle 4.1 aus [CHL10] wird ersichtlich, wie
diese Beschreibung der Beziehungen zwischen den einzelnen Elementen der Bäu-
me aussehen kann:
Tabelle 4.1: Beispiel von Beziehungen zw. zwei Baumelementen aus [CHL10]
Objekt Objektbeschreibung
U {< “ProsandCons“, /mv@title >,< “JohnS.“, /mv/dr/text() >}U’ {< “ProsandCons“, /mv@title >,< “JohnS.“, /mv/dr/text() >}
1http://www.w3.org/XML/Query/
19
Da das Auffinden von Knoten, welche verglichen werden sollen, sehr aufwendig
ist, kann die Arbeit mittels heuristischer Regeln [CHL10] automatisiert werden. An-
hand des Knotens “cst1“ wird dies nachfolgend dargestellt.
a) r-Distanz Vorgänger: Vorfahren u bis zu einer bestimmten Entfernung r. Abb.
4.2 unter (a) zeigt das Ergebnis für r = 1.
b) r-Distanz Nachkommen: Nachkommen u bis zu einer bestimmten Entfernung
r. Ein Beispiel ist in Abb. 4.2 (b) zu sehen. Hier wird ebenfalls mit dem Wert r
= 1 gearbeitet.
c) k-nächstgelegene Nachkommen: Wählt die ersten Nachkommen k von u und
beginnt bei u. Fortgefahren wird mittels dem Breitensuchen-Algorithmus(engl.
Bread-First-Order). Unter (c) in Abb. 4.2 ist ein solches Bespiel mit k = 3 abge-
bildet.
Exkurs: Bei der Bread-First Order oder zu Deutsch auch Breitensuche genannt, han-
delt es sich um einen Algorithmus für das durchsuchen von Graphen. Hier wird
ein Graph von Ausgangspunkt u durchstöbert. Zuerst wird auf der durch u aus-
gewählten Ebene gesucht. Ist der Ausdruck hier nicht zu finden, so wird auf der
nächsten Unterebene gesucht. Dies wird letzten Endes solange durchgeführt, bis
der Ausdruck gefunden wurde oder nicht.
mv1
cst1@year @title
T.PeckB.A.
Baracus Murdock
1984 ProsandCons
cst1
ac3ac2ac1
T.PeckB.A.
Baracus
cst1
ac2ac1
1
2 3
(a) (b) (c)
Abbildung 4.2: Bildliche Darstellung der oben aufgeführten heuristischen Regeln aus[CHL10]
3. “Duplicate Detection“
Nach der Definition für das Suchen und Vergleichen von Duplikaten, wird nun auf
die eigentliche Erkennung dieser eingegangen. Begonnen wird nun in dem die An-
zahl von paarweisen Vergleichen reduziert wird. Die Reduzierung wird ermöglicht,
indem nach Kandidaten gesucht wird, welche die gleichen Beschreibungen enthal-
ten.
20 4 DogmatiX
Hierfür wird schlussendlich ein Filter eingesetzt. Die Logik, die hinter dem Fil-
ter steckt, ist simpel. Es wird ein Verhältnis zwischen einer Menge von gegebenen
Objektbeschreibungen und der Menge von Informationen in allen Objektbeschrei-
bungen berechnet.
Die Menge an Information wird durch eine Kombination von IDF’s (Inverse Do-
cument Frequency measure) ermittelt. Für diesen Gebrauch eignen sich die so ge-
nannten “soft IDF’s“.
Zu sehen ist es an der nachfolgenden [CHL10] Formel zur Berechnung des Wer-
tes auf Gleichheit zwischen den Bäumen U und U’ aus [CHL10].
sim(U,U ′) = softIDF (Pros andCons)
softIDF (Pros andCons) + softIDF (JohnS.) + softIDF (J.Smith)
Nach dem Filtern findet nun der eigentliche Vergleich statt. Hierfür werden die ein-
zelne Elemente der Paare verglichen. Alle Paare, welche einen definierten Schwell-
wert erreichen, werden als Duplikate deklariert. Für die Berechnung dieses Wertes
werden die Objektbeschreibungen beider Kandidaten herangezogen. Diese werden
im nächsten Schritt relativ zu den Werten der nicht ähnlichen Objektbeschreibun-
gen gesetzt und berechnet.
Bei ähnlichen Objekten wird eine normalisierte Entfernung zwischen den Daten
festgelegt. Unterbieten die normalisierten Entfernungen den Schwellwert, so han-
delt es sich hierbei um Duplikate. Für gleiche und nicht gleiche Beschreibungen
wird die Bedeutung durch die “soft IDF measure“ gegeben.
21
5 Praktischer Vergleich zwischen XMLDupund DogmatiX
Im nachfolgenden wird nun ein Vergleich zwischen XMLDup und DogmatiX dargestellt.
Die Testreihe die hier aufgeführt wird, wurde von den Autoren aus [LCH13] durchge-
führt. Sie benutzten für Ihren Test die Programmiersprache JAVA inkl. der DOM API
zum XML-Handling. Des Weiteren führten Sie Ihre Tests mittels 4 verschiedenen reeller
Datensätze durch. Für den Umfang der Daten wurden große Datensätze (z.B. CD 2) so-
wie kleine (z.B. Restaurant) zum Testen verwendet. Des Weiteren besitzen alle Datensätze
bis auf die des Restaurants 3 Ebenen. Der Datensatz des Restaurants hingegen besitzt 4
Ebenen. Für alle Durchläufe, d.h. sowohl für XMLDup wie auch DogmatiX, wurde ein
Schwellenwert von 0.5 definiert.
In Abbildung 5.1 sind die Testergebnisse für alle vier Datensätzen und beide Duplikatenerkennungs-
Methoden grafisch dargestellt. Dabei wird klar ersichtlich, dass der Ansatz der Baye-
schen Netze, welcher in XMLDup angewendet wird, einen effektiveren Weg darstellt
Duplikate zu finden.
Abbildung 5.1: Übersicht des Vergleichs zwischen XMLDup und DogmatiX für alle 4 Da-
tensätze [LCH13]
22 5 Praktischer Vergleich zwischen XMLDup und DogmatiX
Anhand der Tabelle 5.2 wird diese Aussage bekräftigt. Vor allem mit Hilfe des Faktors
für die Beschneidung von den Bäumen die in Kapitel 3.3 erläutert wird, ist ein zuverläs-
siger Faktor für einen Speed-Up bei den aufgezeigten Tests.
Tabelle 5.2: Zeitmessung der Duplikatenerkennung [LCH13]
Es bleibt zu erwähnen, dass es durchaus auch Bereiche gibt, in welchen DogmatiX
schneller ist, so z.B. zu sehen in Tabelle 5.2 bei dem “IMDB + FD“ Datensatz in Spalte
“XMLDup(np)“. Jedoch wird kein Pruning in XMLDup eingesetzt. Aufgrund der Daten-
menge ist DogmatiX schneller. Es lässt sich jedoch wiederum ein Geschwindigkeitsge-
winn gegenüber DogmatiX erzielen, indem mit dem Pruning Faktor gearbeitet wird.
In diesem Kapitel wurde anhand von Beispielen mit reellen Datensätzen gezeigt, wie
effizient und schnell XMLDup gegenüber DogmatiX ist. Es wurde verständlich gemacht,
dass es XMLDup kleinere Schwächen hat in Bezug auf sehr große Daten, sofern nicht mit
einem Pruning Faktor gearbeitet wird.
23
6 Fazit
In dieser Arbeit wurde sich mit der Thematik der Duplikatenerkennung befasst. Sie ist
ein sehr komplexes Thema. Angegangen wurde die Thematik mit Hilfe von dem neu ent-
wickelten XMLDup, sowie mit dem “state-of-the-art“ Erkennungsframework DogmatiX.
Im Laufe dieser Arbeit stellte sich heraus, dass es bei XMLDup um einen sehr interes-
sante Technik handelt um Duplikate innerhalb eines XML-Formats ausfindig zu machen.
Es verspricht einen Geschwindigkeits- sowie einen Effizienzgewinn gegenüber Dogma-
tiX. Dies wird großteils durch das Beschneiden der Baumstruktur gewährleistet.
Abschließend bleibt zu sagen, dass auch der XMLDup Ansatz kleinere Schwächen auf-
weist. So lässt sich bemerken, dass es anwendungsfallabhängig sein kann, für welchen
dieser beiden aufgezeigten Ansätze angewendet werden soll.
24 6 Fazit
25
Literaturverzeichnis
[CHL10] CALADO, Pável ; HERSCHEL, Melanie ; LEITÃO, Luís: An overview of XML
duplicate detection algorithms. In: Soft Computing in XML Data Management.Springer, 2010, S. 193–224
[LCH13] LEITAO, Luis ; CALADO, Pavel ; HERSCHEL, Melanie: Efficient and effective
duplicate detection in hierarchical data. In: Knowledge and Data Engineering,IEEE Transactions on 25 (2013), Nr. 5, S. 1028–1041
[WN05] WEIS, Melanie ; NAUMANN, Felix: DogmatiX tracks down duplicates in XML.
In: Proceedings of the 2005 ACM SIGMOD international conference on Managementof data ACM, 2005, S. 431–442