Entwurf und Implementierung eines Verfahrens zur Analyse komplexer Daten insbesondere auf strukturelle Ähnlichkeit

Inhaltsverzeichnis

1 Einführung

2 Grundlagen
2.1 Eigenschaften komplexer Datentypen
2.1.1 Komplexe Datentypen und ihre primitiven Bestandteile
2.1.2 Das XML-Transport-Dokumentformat
2.1.3 Feste und lose Strukturen
2.1.4 Das RDF-System zur Beschreibung von Ressourcen
2.2 Distanz-Berechnungsvorschriften in Räumen
2.2.1 Suchräume
2.2.2 Edit-Distanzen
2.2.3 Werte-Distanzen
2.2.4 PlusMinus- Ähnlichkeit
2.2.5 Bildung von Teilmengen
2.3 Logische Kombination der Distanzwerte
2.3.1 Aussagenlogik
2.3.2 Prädikatenlogik
2.4 Abfragesprachen mit Datenstrukturen
2.4.1 Abfragesprachen
2.4.2 Datenstrukturen
2.4.3 Bekannte Ansätze auf Datenstrukturen
2.4.4 Ontologien

3 Problemstellung und Abgrenzung
3.1 Problemstellung
3.2 Existierende Ansätze
3.3 Abgrenzung
3.3.1 Baumsignaturen
3.3.2 Similarity Join Frameworks
3.3.3 Tamino & XXL Ontologie
3.3.4 Kernel-Funktionen

4 Lösungsansatz (Konzept)
4.1 Das SimSearch Framework
4.1.1 SimSearch CMD-Engine
4.1.2 Grafische Darstellung der Suchergebnisse
4.2 Strukturelle Ähnlichkeitssuche
4.2.1 Lineare-Baumsignatur (Herleitung)
4.2.2 Strukturelle Ähnlichkeitssuche (Berechnung)
4.3 Inhaltliche Ähnlichkeitssuche
4.3.1 Das abstrakte Datenschema (Herleitung)
4.3.2 Inhaltliche Ähnlichkeitssuche (Berechnung)
4.4 (Teil)Baum- Ähnlichkeitssuche
4.4.1 Bottom-Up Gleichheitssuche
4.4.2 Bottom-Up Ähnlichkeitssuche

5 Lösungsansatz (Validierung)
5.1 Externe Komponenten (Laufzeit)
5.2 Eigene Komponenten (Laufzeit & Validierung)

6 Zusammenfassung und Ausblick
6.1 Zusammenfassung
6.2 Ausblick

Stichwortverzeichnis

Literaturverzeichnis

1. Einführung

”Auf Ähnlichkeit,nicht auf Gleichheit ist alles Klassifizieren oder die Sprache aufgebaut, auf Ähnlichkeit, nicht auf Gleichheit all unser Urteilen oder die Anwendung der Sprache. Alle Logik aber, auch die Algebra der Logik, geht von dem mathematischen Begriff der Gleichheit aus und ist darum eine gefährliche Wissenschaft. Um nicht zu weit abzuschweifen, sei nur kurz erwähnt, daß auch der Begriff oder das Gefühl der Kontinuität aus dem Gefühle der Ähnlichkeit allein entsteht.“ - Fritz Mauthner, 1906

Immer wieder wird man redensartlich daran erinnert, keine Äpfel mit Birnen zu vergleichen, und dennoch wird dieser Vergleich öfter als vielleicht angenommen gezogen. Ein derartiger Vergleich wird täglich sowohl bei der Wahl substitutiver Güter als auch bei der Nutzung von Suchmaschinen und der dort angezeigten Ergebnisse angewendet. Im Allgemeinen wird er seit jeher bei der Klassifizierung von Gegenständen des reellen Lebens gezogen, indem durch eine Teilmenge gemeinsamer Eigenschaften irgendwelche Gegenstände zu einer Gruppe von Elementen einer bestimmten Klasse zusammengefasst werden. Durch Generalisierung werden diese Mengen anschließend in größere und durch Spezifizierung in kleinere Mengen unterteilt.

Herkömmliche Suchalgorithmen setzen jedoch die Kenntnis der Eigenschaften voraus. Sie bieten lediglich die Möglichkeit, diejenigen Elemente als Suchergebnis zu identifizieren, welche sowohl den innerhalb der Suchanfrage definierten Kriterien genügen als auch über eine einheitliche Menge von Eigenschaften verfügen. Dabei werden meist harte Grenzen gezogen, welche bei Nichterfüllung den Ausschluss aus der Ergebnismenge bedeuten. Ge- nau das disqualifiziert bestehende Suchalgorithmen in vielen Anwendungsfällen.

Einige dieser Fälle haben die hier vorliegende Arbeit motiviert. Zum Beispiel im Be- reich der Konstruktion von Automobilteilen besteht gleich an mehreren Stellen Bedarf für unscharfe Suchalgorithmen. Angefangen bei der Angebotserstellung, welche an einen Kostenvoranschlag gekoppelt ist, bis hin zur Standardisierung von Bauteilen lassen sich erhebliche Zeit- und Kostenersparnisse durch das automatisierte Auffinden ähnlicher Auf- träge oder Produkte erzielen. In [Ent06, S. 16] wird der Angebotsprozess am Beispiel eines Automobilzulieferers ausführlich geschildert. In jener Arbeit wird besonders auf das hohe Einsparpotential innerhalb der Konzept- und Designphase hingewiesen. Dort entstehen Kosten in Verbindung mit Kostenvoranschlägen sowie prototypischen Lösungsansätzen und lassen sich durch die Suche ähnlicher Aufträge und Konstruktionsdaten minimieren. Sowohl Aufträge als auch Produkte samt Konstruktionsdaten werden innerhalb der EDV durch komplexe Daten abgebildet und sollen als solche vergleichbar gemacht werden. Dies ist eine größere Herausforderung als der Vergleich primitiver Datentypen, weil die Anzahl der Attribute und die Größe ihrer Wertebereiche nicht von vornherein bekannt sind.

Diese Arbeit gliedert sich wie folgt: Als erstes wird der Unterschied zwischen primitiven und komplexen Daten und der daraus entstehenden Komplexität erläutert. Anschließend werden die mathematischen und algorithmischen Grundlagen zur Ähnlichkeits- bzw. Di- stanzmessung dargestellt. Diese erlauben es, sich dem abstrakten Begriff der Ähnlichkeit wissenschaftlich zu nähern und diesen programmatisch erfassbar zu machen. Weil metrische Ähnlichkeits- bzw. Distanz-Berechnungsverfahren sowie Abfragesprachen mit Datenstrukturen eher den Grundlagen als der Abgrenzung zuzurechnen sind, aber auch zum Teil komplette Ähnlichkeits-Messverfahren enthalten, sind die erläuternden Aus- führungen durch teilweise Vorwegnahme der Abgrenzung entsprechend umfangreich. Anschließend folgt eine Beschreibung und Auseinandersetzung mit der Problemstellung. Dabei werden vorhandene Algorithmen zur Ähnlichkeitsmessung vorgestellt sowie deren Anwendbarkeit geprüft. Danach findet eine Unterteilung der Problemstellung in inhaltli- che und strukturelle Ähnlichkeit statt. Diese Unterteilung bedarf unterschiedlicher Her- angehensweisen und schafft Raum für die Schwerpunktsetzung auf die strukturelle Ähn- lichkeitsanalyse. Im darauf folgenden Kapitel 4 wird ein eigener Ansatz zu struktureller und inhaltlicher sowie der (Teil)Baum- Ähnlichkeitssuche vorgestellt. Dieser wird in Kapi- tel 5 validiert. Zum Schluss folgt eine Zusammenfassung der erzielten Ergebnisse und der Ausblick auf die semantische Erwartbarkeit.

2 Grundlagen

2.1 Eigenschaften komplexer Datentypen

2.1.1 Komplexe Datentypen und ihre primitiven Bestandteile

”Alle guten Worte dieser Welt bestehen dochnuraus Buchs taben.“-Tse-Tang

Komplexe Daten und komplexe Datentypen bezeichnet man als solche vorwiegend zur Abgrenzung von primitiven Datentypen. Während der Begriff der Komplexität die Ei- genschaft eines Systems oder Modells umfasst, welches sein Gesamtverhalten als nicht beschreibbar definiert, selbst wenn alle Informationen über seine Einzelkomponenten und Wechselwirkungen bekannt sind [Här[08]], sind dagegen komplexe Datentypen durch die Bekanntheit aller Einzelkomponenten hinreichend beschrieben. Der Begriff der Komple- xität steht hier somit nur im Kontrast zum Begriff der Einfachheit bzw. der Primitivität, aus welchem sich die Bezeichnung der primitiven Datentypen ableitet.

Während primitive Datentypen nur einen einzigen binären Wert aufweisen, welcher entweder den Flags¹, Zahlen oder Zeichen oder Zeichenketten zugeordnet werden kann, können komplexe Datentypen, ähnlich den komplexen Zahlen, aus mehreren Werten be- stehen. Eine genaue Unterteilung verschiedener Kategorien sowie deren Klassifizierung und Gruppierung ist in der folgenden Seminararbeit ausgeführt worden: ”Analysevon komplexen Produkt- und Prozess-Datentypen zur Unterstützung wissensintensiver Prozesse“ [Nie[09], S.11].

In der hier vorliegenden Arbeit steht der hierarchische Aufbau komplexer Daten und Datentypen, welcher als Baum betrachtet ausschließlich primitive Blattknoten aufweist, im Vordergrund. Diese können wiederum zu komplexen Elementknoten zusammengefügt werden. Diese Art des Aufbaus und der Serialisierung komplexer Objekte entspricht auch dem Ansatz des allgemeinen XML-Transport-Dokumentformats, auf welches im Folgenden näher eingegangen wird, weil es als Grundlage zum Vergleich komplexer Daten innerhalb dieser Arbeit dient.

2.1.2 Das XML-Transport-Dokumentformat

XML ist eine erweiterbare Auszeichnungssprache (eXtensible Markup Language) und dient dem plattform- und implementationsunabhängigen Austausch von Dokumenten. So- wohl wegen der Fähigkeit, verschiedenste Quellen zu integrieren, als auch wegen der ma- schinellen und menschlichen Lesbarkeit wird XML allgemein als der Standard der Zukunft angesehen [Guh02]. XML-Dokumente können in der Regel den höchsten Komp]lexitätsgrad aufweisen und sind auch nur an sehr wenige strukturelle Bedingungen geknüpft.² Diese Eigenschaft macht sie für strukturelle Untersuchungen besonders interessant, da gröbere strukturelle Unterschiede feststellbar sind, während bei vielen strukturellen Bedingungen diese Unterschiede nur noch sehr geringfügig ausfallen. Die strukturellen Bedingungen sei- tens XML beschränken sich lediglich auf das Hinterlegen der Daten in einer Baumstruktur mit ausgezeichnetem Wurzelelement. Inhaltlich werden die Datensätze bei XML als Enti- täten bezeichnet und als eine Zeichenkette, umgeben von Auszeichnungselementen (Mar- kup), gespeichert. Dieser Ansatz erlaubt beliebige Kombinationen primitiver Datentypen, weil sich diese immer als Zeichenketten repräsentieren lassen. Außerdem wird dadurch die Lesbarkeit der XML-Dokumente für Menschen sichergestellt. Die Auszeichnungselemente dienen einerseits der Zuordnung der Stringrepräsentation der Entitäten zu frei wählba- ren Klassen, andererseits können die Entitäten ebenfalls auf dieser Ebene mit weiteren Attributen versehen werden. Da, wo den frei gewählten Auszeichnungs-Tags bestimmte primitive Datentypen eindeutig zugeordnet werden können, kann diese Zuordnung inner- halb einer Dokumenttypdefinition-Datei (DTD) zwecks Validierung vorgenommen werden. Die DTD trägt somit einen semantischen Mehrwert zur reinen XML-Datei bei und erlaubt über die Zeichenketten-Repräsentation weiterreichende Vergleiche.

2.1 EIGENSCHAFTEN KOMPLEXER DATENTYPEN 5

Weil Attribute auch in Form einwertiger Elemente gespeichert werden können, wird an dieser Stelle eine Unterscheidung zwischen der Daten- und der Metaebene vorgenommen, welche eher stilistischer als struktureller oder inhaltlicher Natur ist. Da diese Unterscheidung somit für den strukturellen und inhaltlichen Vergleich nicht von Bedeutung ist, stellt eine vereinheitlichte Behandlung von Attributen eine Voraussetzung für das innerhalb dieser Arbeit vorgestellte SimSearch Framework dar. Da weitergehende XML-Kenntnisse im Rahmen dieser Arbeit nicht zwingend vorausgesetzt werden, wird an dieser Stelle auf die entsprechenden Ausführungen verwiesen.³

2.1.3 Feste und lose Strukturen

Die geringe strukturelle Einschränkung komplexer Datentypen und daraus folgend auch deren Abbildung durch XML erlaubt es, dass Sammlungen von Entitäten gleichen Typs an beliebiger Stelle des XML-Baums⁴ auftreten können. Solche Sammlungen (Collections) weisen gegenüber festen Strukturen den elementaren Unterschied auf, dass ihre Größe so- wie ihre strukturelle Singnatur von der variablen Anzahl der Elemente der jeweiligen Ausprägung einer Sammlung abhängig ist. Feste Strukturen dagegen zeichnen sich durch eine festgelegte Anzahl von Entitäten aus, welche bei objektorientierter Programmierung (OOP) der serialisierbaren⁵ Attributmenge einer Klassendefinition entsprechen. Diese fun- giert bei Klassendefinitionen mit fester Attributmenge als eine Art Gatter, welches defi- nierte Wertebereiche für elementare oder komplexe Komponenten festsetzt. Werden dem Gatter keine Collections hinzugefügt, so können diese Gatter strukturell nicht voneinander abweichen. Sind diese Bedingungen dagegen nicht erfüllt, d. h. die Komponente enthält Collections, so handelt es sich bei der zu betrachtenden Komponente um eine lose Struk- tur.

Abschließend sei noch erwähnt, dass feste Strukturen selbst auch als Collections heteroge- ner Komponenten mit fester Elementenanzahl betrachtet werden können, was jedoch dem Grundcharakter der flexiblen Elementenanzahl sowie der Verwaltung homogener Objekt- klassen der Collections widersprechen würde und deshalb nicht als sinnvoll zu erachten ist.

2.1.4 Das RDF-System zur Beschreibung von Ressourcen

Das System zur Beschreibung von Ressourcen RDF (Resource Description Framework) dient der Beschreibung und Verknüpfung von Wissensbeständen. Es wurde ursprünglich zur Beschreibung von Metadaten der Online-Inhalte entwickelt, um im Zuge des Seman- tischen Webs eine bessere Klassifizierung der im Netz verfügbaren Inhalte vornehmen zu können. Dieser Ansatz wird jedoch in voller Konsequenz nur seitens der Verfechter des Semantischen Webs und der Ontologen verfolgt, wodurch es vorwiegend in Bereichen ein- gesetzt wird, in denen heterogene Entitäten zu großen Wissensbasen verknüpft werden.⁶ RDF adressiert die Ressourcen über eine eindeutige URI (Uniform Resource Identifier).⁷ Dies ermöglicht die Aufnahme und Abbildung heterogener komplexer Entitäten sowie die Abbildung der zwischen den Entitäten bestehenden Relationen unter einheitlicher Be- handlung von semantischen und syntaktischen Informationen über die Entitäten. Dies ist ein Vorteil gegenüber reinem XML-Gebrauch, denn es herrschen klare Richtlinien über den Gebrauch und den Speicherort von Metadaten und Attributen. Das ist bei XML nicht der Fall, weil Metadaten teils weggelassen, teils in externen Dateien, wie der DTD, und teils in Attributen, sowohl als Erweiterung der Markup-Tags als auch als einwertige Elemente, gespeichert werden können. Der wohl entscheidende Vorteil des Einsatzes von RDF be- ruht in der maschinellen Auswertbarkeit der Dokumente, bei welcher sogenannte Reasoner eingesetzt werden. Diese erlauben die Ableitung von Informationen, welche nicht explizit vorliegen, sich jedoch aus einer Kombination der innerhalb der Daten vorhandenen Be- stände erschließen lassen. Dies wirkt sich einerseits vorteilhaft auf den Speicherverbrauch aus, weil Informationen, die gewissen Gesetzmäßigkeiten folgen, nicht explizit gespeichert werden müssen, sondern als Regeln, welche die Reasoner berücksichtigen, hinterlegt wer- den. Andererseits lassen sich höchst komplexe Abfragen formulieren, welche sogar von implizit vorhandenen, ableitbaren Informationen Gebrauch machen können. Hier bleibt noch anzumerken, dass RDF die Daten als wahre Aussagen über die Ressourcen in Form eines Tripels aus Subjekt, Prädikat, Objekt speichert. Das Subjekt ist dabei die Ressour- ce, über die etwas ausgesagt wird, das Prädikat kennzeichnet eine Eigenschaft, welche dem Subjekt zugesprochen wird, und das Objekt ist der Wert der Eigenschaft, die entwe- der elementar oder eine andere Ressource sein kann. Dies führt dazu, dass der zugrunde liegenden Datenstruktur ein gerichteter Graph entspricht.

2.2 Distanz-Berechnungsvorschriften in Räumen

Ähnlichkeit schafft Freunde, die Differenzen halten sie zusammen“ - Unbekannt ”

2.2.1 Suchräume

Suchräume dienen als Grundlage für eine spezielle Implementierung von Suchalgorithmen. Im Folgenden werden die wichtigsten Raum-Begriffe erläutert:

Metrische Räume

Die Bezeichnung des Raumes leitet sich von der den Raum definierenden mathematischen Funktion, der Metrik ab. Diese ordnet je zwei Elementen eines Raums einen positiven, reellen Wert als deren Abstand zu. Formal wird der metrische Raum als eine Abbildung d : X×X → R definiert. Diese bezeichnet man als Metrik auf X, wenn folgende Bedingungen erfüllt sind [Zez06, S.8], [Cha01, S.278]:

1 Nicht-Negativität ∀x, y ∈ D, d(x, y) ≥ 0

2 Symmetrie ∀x, y ∈ D, d(x, y) = d(x, y)

3 Reflexivität ∀x ∈ D, d(x, x) = 0

4 Positivität ∀x, y ∈ D, x = y ⇒ d(x, y) > 0

5 Dreiecksungleichung ∀x, y, z ∈ D, d(x, z) ≤ d(x, y) + d(y, z)

Die Postulate 3 und 4 können zum Postulat der Identität zusammengefasst werden: 3+4 Identität ∀x,y ∈ D, x = y ⇔ d(x,y) = 0

In einigen Fällen, wie beispielsweise der Betrachtung von Distanzen zwischen zwei Po- sitionen innerhalb einer Stadt mit Einbahnstrasse, kann es vorkommen, dass die Bedin- gung der Symmetrie nicht eingehalten wird. In diesen Fällen wird von der sogenann- ten Quasi-Metrik gesprochen. Andererseits kann eine Quasi-Metrik z. B. durch das Be- trachten der mittleren Distanz zwischen Hin- und Rückweg (d_sym(x, z) = (da_sym(x, y) + da_sym(y,x))/2) in eine Metrik umgeformt werden. Ferner existieren Metriken mit ver- schärfter Dreiecksungleichung-Bedingung, welche jedoch aus spezifischen - in der Evolu- tionstheorie auftauchenden - Problemen abgeleitet sind und hier nicht weiter betrachtet werden müssen. Unterschieden wird ferner zwischen diskreter und kontinuierlicher Di- stanz. Da einerseits die Computer durch die begrenzte Wortlänge, die zum Ausdruck beliebig genauer Werte stets einen ”Flaschenhals“darstellt,kontinuierlicheDistanznicht beliebig genau unterscheiden können, und weil die Unterscheidung einer endlichen Anzahl von Ähnlichkeitsabstufungen völlig hinreichend für die Sicht des Endnutzers erscheint, wird im Rahmen der rechnergestützten Ähnlichkeitsanalyse und damit dieser Diplomarbeit von diskreter Distanz als Distanz gesprochen. Die Ähnlichkeit wird im Rahmen dieser Diplomarbeit als ein Prozentsatz zwischen 0% und 100% angegeben und bildet damit einen Komplementärwert⁸ zu der diskreten Distanz. Damit sind zwei Werte maximal unterschiedlich, wenn die Distanz 100% und die Ähnlichkeit 0% beträgt, und andersherum identisch, wenn die Ähnlichkeit 100% und die Distanz 0% beträgt.

Im Rahmen dieser Diplomarbeit sowie des SimSearch Frameworks wird noch eine andere Art der Differenzierung der Ähnlichkeit vorgeschlagen und als PlusMinus Ähnlichkeit bezeichnet (s. S. 22).

Vektor-Raum Mehrdimensionale Räume, auf denen sich eine Metrik definieren lässt, kön- nen auch häufig als Vektor-Räume aufgefasst werden [Cha01, S. 281]. Dabei werden die Ausprägungen der Attributwerte auf mehrdimensionale Räume projiziert. Die Projektion wird erreicht, indem jedem Attribut eines Objekts eine Dimension zugewiesen wird und dessen Ausprägung einen Punkt innerhalb dieser Dimension darstellt. Ausgehend vom einem Objekt mit n Attributen stellt die Gesamtheit der Ausprägungen seiner Attribute somit einen Punkt in einem n-dimensionalen Raum dar. Dies erlaubt ebenfalls die Definiti- on der Distanz dieser Komponenten als die Länge des Vektors zwischen den Komponenten zugeordneter Punkte (siehe 2.2.1).

Lp Raume Im Allgemeinen wird durch die sogenannten Lp-Räume eine Reihe von Räu- men definiert, welche unterschiedliche Eigenschaften aufweisen und damit besondere Vor- aussetzungen an die Berechnung der Distanz stellen. Um das Wesen und die damit zu- sammenhängenden Paradigmen besser verstehen zu können, werden diese zusammen mit den Distanzvorschriften im Rahmen des Unterkapitels 2.2.1 Lp-Räumen“ auf Seite 10 beschrieben.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Beispieldatensatz - Nano Example

Grundlagen der Distanz Ermittlung

Der Suchalgorithmus des SimSearch Frameworks arbeitet auf diskreter Basis. Dabei wird ein Durchschnittswert aller feststellbar ähnlichen Attribute zweier Dokumente ge- messen. Dieser wird bei ungerader Teilung gerundet, wodurch das Ergebnis weiterhin dis- kret bleibt. Dies führt dazu, dass die Distanz zwischen zwei Punkten zu einem gewissen Grad von der Anzahl der Attribute (und damit der Dimensionen) sowie von den jeweils für diese Attribute bekannten maximalen und minimalen Wertausprägungen abhängt. Der durch die Rundung verursachte Fehler kann jedoch höchstens ein Prozent des gemessenen Ähnlichkeits-Wertes ausmachen. Diese Herangehensweise entspricht der Distanzmessung innerhalb Euklidischer Räume. Die Distanzvorschrift kann jedoch im Rahmen der Ähn- lichkeitssuche auch innerhalb eines anderen Raumes mit der dort zugehörigen Distanz- funktion durchgeführt werden. Die Berechnung der Distanz in einem zweidimensionalen Raum kann leicht veranschaulicht werden, da dieser auch als euklidische Ebene bezeichnet wird und somit den meisten als das Koordinatensystem geläufig ist.

In der Abbildung 1 werden zwei Komponenten dargestellt. Beide weisen zwei Attribu- te auf. Die eine Komponente hat bei beiden Attributen den Wert 1 und die andere bei beiden den Wert 2. Damit stellen die beiden Punkte die Koordinaten der Komponenten bei räumlicher Betrachtung dar. Unter der Annahme, dass die Wertebereiche beider At- tribute zwischen 0 und 3 liegen, kann die Distanz sowohl räumlich als auch rechnerisch ermittelt werden.

Räumliche Ermittlung der Distanz Betrachtet man die Diagonale zwischen dem Ursprung und dem Punkt (3,3), so entspricht die Entfernung zwischen den Koordinaten der bei- den Komponenten genau einem Drittel der Länge der Diagonalen. Würden die Punkte aufeinander liegen, so wäre die Entfernung gleich 0. Würden die Punkte stattdessen im Ursprung und auf dem Punkt (3,3) liegen, so wäre die Entfernung maximal. Die Distanz entspricht damit dem Abstand zwischen beiden Punkten, während die Ähnlichkeit durch den Rest der Diagonalen repräsentiert wird. Damit beträgt die Ähnlichkeit 2/3 und die Distanz 1/3.

Rechnerische Ermittlung der Distanz - SimSearch Die Differenz beträgt bei beiden Attribu- ten 1. Die maximal mögliche Differenz beträgt 3. Um die Distanz berechnen zu können, müssen beide Werte in Relation gesetzt werden. Dies wird erreicht, indem von der maxi- malen Längendifferenz (LD) die vorliegende subtrahiert und durch die maximale geteilt wird. Das Ergebnis gleicht der Ähnlichkeit, weshalb dieses noch von 1 subtrahiert wer- den muss. Auch dies ergibt eine Ähnlichkeit von (3 − 1)/3 = 2/3 und eine Distanz von 1 − 2/3 = 1/3.

Rechnerische Ermittlung der Distanz - Pythagoras Die Berechnung innerhalb des SimSearch Frameworks kann, gegenüber der üblichen Rechenvorschrift für den Abstand zweier Punk- te in der Ebene, vereinfacht durchgeführt werden. Dies geschieht aufgrund der Kenntnis der maximalen und minimalen Wertausprägung bestimmter Klassen von Attributen. Soll- te diese Information nicht verfügbar sein, so muss die Distanz mithilfe des Satzes von Pythagoras berechnet werden. Die Distanz beider Komponenten beträgt damit:

Abbildung in dieser Leseprobe nicht enthalten

Dadurch entspricht die Distanz einem Drittel der höchstmöglichen Distanz, wodurch die Ähnlichkeit ebenfalls 2/3 beträgt.

Ermittlung der Distanz in Lp-Räumen Wie bereits angesprochen, ist der Euklidische Raum nur einer von vielen bekannten Räumen. Der Parameter p ist eine beliebige reelle Zahl größer oder gleich 1. Mit n wird die Anzahl der Dimensionen festgelegt. Mit xi wird, bezogen auf das vorherige Beispiel, das i-te Attribut referenziert. Damit lässt sich eine sogenannte p-Norm definieren:

Abbildung in dieser Leseprobe nicht enthalten

Aus dieser Norm lassen sich Metriken ableiten. Diese werden auch als Minkowski Metriken bezeichnet.⁹ Es besteht ein Zusammenhang zwischen der bislang dargestellten DistanzBerechnungsvorschrift und der aus der Norm ableitbaren Metrik.

Die erste Metrik mit p = 1, wird auch als Manhattan-Metrik bezeichnet. Die zugrunde liegende Rechenvorschrift lautet:

Abbildung in dieser Leseprobe nicht enthalten

Die Distanz zwischen zwei komplexen Komponenten gleicht damit der Summe aller zwischen den Attributen bestehenden Differenzen. Im Rahmen des Beispiels 1 ist dies die Summe (2 − 1) + (2 − 1) = 2. Die Bezeichnung als Manhattan-Metrik ist darauf zurückzuführen, dass statt der Luftlinie zwischen zwei Punkten ein Umweg über ein diskretes Gitternetz, vergleichbar mit dem Straßengitter Manhattans, zurückgelegt werden muss. Die zweite Metrik mit p = 2, entspricht genau der Berechnung des Pythagoras und damit der Distanz innerhalb der schon gezeigten Euklidischen Ebene. Dies kann durch Einsetzen der 2 in die Norm Gleichung nachgewiesen werden:

Abbildung in dieser Leseprobe nicht enthalten

Mit n = 2 entspricht damit die Gleichung der unter |xi|2 (2.3) ”RechnerischeErmittlungderDi- stanz - Pythagoras“ definierten Distanzgleichung. Mit zunehmendem p lassen sich weitere Räume und Distanzfunktionen unterscheiden (siehe [Zez06]).

Abbildung in dieser Leseprobe nicht enthalten

2.2.2 Edit-Distanzen

Die Differenz zweier Objekte kann als die Anzahl von Operationen ausgedrückt werden, welche dazu nötig sind, um das eine Objekt in das andere zu überführen. Dies ist genau die Kernfunktionalität von Edit-Distanzen. Die Edit-Distanzen können je nachdem, ob es sich bei den Objekten um linear oder hierarchisch strukturierte Objekte handelt, in zwei Kategorien unterteilt werden. Im Folgenden werden die beiden Kategorien separat behandelt.

Lineare Edit-Distanzen

Levenshtein Distanz Die Levenshtein Distanz misst die Anzahl der verschiedenen Opera- tionen Ersetzung, Einfügung und Löschung, die zur Transformation einer Zeichenkette in eine andere benötigt werden. Die Entscheidung, ob und welche Operation beim Betrachten zweier Zeichen die kostengünstigste Alternative darstellt, wird mithilfe einer zweidimen- sionalen Matrix vollzogen. Diese enthält die Information über bislang aufgelaufene Kosten, welche mit jeder Operation erhöht werden. Stimmen zwei Symbole nicht überein, so wird die bislang aufgelaufene Summe der Kosten um den Kostenbetrag, der zu dem Zeitpunkt kostengünstigsten Operation erhöht. Die Berechnung wird mit Injizierung der ersten Zeile und der ersten Spalte mit einer von 0 bis zu der jeweiligen Länge der Zeichenkette plus eins fortlaufenden Zahlenreihe begonnen [San83, S.18ff]. Anschließend wird die Matrix spal- tenweise durchiteriert. Für jeden Eintrag wird dabei folgende rekursive Distanzfunktion aufgerufen:

Abbildung in dieser Leseprobe nicht enthalten

Dies erlaubt eine differenzierte Gewichtung der Operationen, da die Kosten für die Ope- rationen separat vergeben werden können. Um diese jedoch sinnvoll differenziert vergeben zu können, sind Kenntnisse über die Semantik der Daten vorausgesetzt. Die Levenshtein Distanz kommt auch im Rahmen des SimSearch Frameworks beim Vergleich primiti- ver Datentypen unterhalb einer bestimmten LD zum Einsatz. Da dies keine besonderen Vorkenntnisse über die Daten voraussetzt, bleiben die Operationen gleichgewichtet.

Hamming-Distanz Die Hamming-Distanz (HD) wurde ursprünglich zur Erkennung von Missständen bei der digitalen Übertragung von Nachrichten eingeführt. Dabei werden je zwei Nachrichten gleicher Länge bitweise verglichen und die Anzahl der Bits, welche nicht identisch gewesen sind, als Hamming-Distanz ausgegeben [Boo02, S. 354]. Dieser Ansatz lässt sich auch für Zeichen anderer endlicher Alphabete verallgemeinern. Die HammingDistanz lässt sich wie folgt formalisieren. Gegeben seien zwei Vektoren:

v := (v₁, v₂, . . . , v_n)

w := (w₁, w₂, . . . , w_n)

Die Hamming-Distanz d(v, w) der Vektoren v und w entspricht der Anzahl der Zeichen, in denen sich v und w unterscheiden:

Abbildung in dieser Leseprobe nicht enthalten

Die hier vorgenommene Zuordnung der Hamming-Distanz zu den linearen Edit-Distanzen ist darauf zurückzuführen, dass die Differenz zwischen den Eingabemengen durch eine eingeschränkte Operationsmenge (Überschreibung der nicht übereinstimmenden Symbole einer der Mengen mit insert / delete) zum selben Ergebnis führt wie die bloße Zählung der nicht übereinstimmenden Symbole. Dieser Ansatz berücksichtigt auch keine Nachbarschaft von Objekten [Boo02, S.354]. Dies ist darin begründet, dass jedes einzelne Zeichen, unabhängig von dessen Position, gleichgewichtet wird. Dieser Sachverhalt lässt sich mit folgenden binären Folgen veranschaulichen:

(a) 1100100000

(b) 1100010000

(c) 1100000001

Den binären Folgen (b) und (c) wird mit dem ursprünglichen Ansatz die gleiche Distanz (2) zu (A) zugeordnet. Dieser Sachverhalt repräsentiert zumeist jedoch nur unzureichend die tatsächliche Distanz. In den meisten Fällen bedeutet die Setzung eines weiteren Bits eine Verdopplung des bislang bestehenden Wertbereichs. Dennoch existieren auch Da- tenstrukturen, bei denen aus der Reihenfolge der gesetzten Bits keine Rückschlüsse auf Unterschiede in der Distanz von Objekten gezogen werden können. Ein Vertreter dieser Gattung ist das Boolsches Array. Dieses speichert Eigenschaften von Objekten, welche nach beliebigen Kriterien sortiert sein können. Dieser und ähnliche Fälle stellen jedoch eine Seltenheit bei der Betrachtung gängiger Datentypen dar. Es ist verbreiteter, die Po- sition eines Bits innerhalb eines Datentyps als zusätzliche Information zu verwenden.¹⁰ In diesen Fällen empfiehlt sich eher der Einsatz einer generalisierten Hamming-Distanz [Boo02, S.355] zur Messung der Distanz auf der Bitebene. Diese wird im Folgenden be- schrieben.

Generalisierte Hamming-Distanz Während der eben vorgestellte Ansatz eine sehr begrenzte Operationsmenge aufweist, wird bei der generalisierten Hamming-Distanz (GHD) die Operationsmenge dahingehend erweitert, dass über den Distanzwert ebenfalls eine Aussage zu der Nachbarschaft von Objekten getroffen werden kann. Diese wird um die Shift-Operation erweitert, welche den Transfer eines Bits an eine benachbarte Position effizienter erlaubt als das Löschen und neu Einfügen. Die Differenz wird bei GHD zwischen der Ausgangs(source BS ) und der Zielmenge (target BT ) folgendermaßen bestimmt:

Beide Mengen werden zunächst durch eine natürliche Zahl repräsentiert. Diese Zahl stellt für jedes gesetzte Bit dessen Position (Wertigkeit) dar. Die Repräsentationen werden im Folgenden als S und T bezeichnet. Ferner wird eine Funktion N (X) eigeführt, welche die Anzahl der nicht 0-Elemente einer Menge X zurückliefert. Dabei gilt N (BS ) = N (S). Das Ziel ist die Berechnung der Distanz d(S, T ) mithilfe einer Kostenfunktion c(i, j), wel- che die minimalen Kosten der Transformation der ersten i 1-Bits von BS in die ersten j 1-Bits von BT misst, wobei 1 ≤ i ≤ N (BS ) und 1 ≤ j ≤ N (BT ) ist. Diese Funk- tion wird auf den Bitmengen BS und BT aufgerufen: c(N (BS ), N (BT )). Da die GHD sowie die HD Bitfolgen fester Länge betrachten, können Einfüge- sowie Löschoperationen nicht zu einer Veränderung der Bitfolgen-Länge führen. Diese Operationen bewirken in diesem Fall eine Umkehrung des Bits an einer Position beim Einfügen von 0 zu 1 und beim Löschen von 1 zu 0. Die Berechnung der Kostenfunktion wird für das Einfügen als c(i, j) = cI + c(i, j − 1) im Fall si < tj respektive c(i, j) = cI + c(i − 1, j) für den Fall si > ij für die Löschoperation definiert. Ferner wird eine Shift-Operation angewandt, wenn der Abstand der Positionen zweier gleicher Bits innerhalb ihrer Komplementär-Bit-Folgen relativ gering ist. Dieser Abstand wir als (△) symbolisiert und deren Kosten als eine nicht- negative, monoton steigendie Kostenfunktion cS (△) referenziert. Die Kostenfunktion der Shift-Operation hängt einerseits von der Anzahl der Shift-Operationen ab und wird ande- rerseits in einen relativen Bezug zu den Kosten der Löschung und des Einfügens gesetzt, damit ein Bereich definiert werden kann, in welchem die Shift-Operation kostengünstiger ausfällt als eine Kombination aus cI und cD .

Die Berechnung des Algorithmus kann effizient mithilfe der dynamischen Program- mierung implementiert werden. Da im Rahmen des SimSearch Frameworks stets die Zeichenketten als Repräsentation von Werten betrachtet werden, weil die XML-Daten ohne weitere Betrachtung der DTD als solche hinterlegt werden, wird auf weitere Spezi- fizierungen des Algorithmus an dieser Stelle nicht eingegangen (siehe [Boo02]).

Hierarchische Edit-Distanzen

Wie bereits im Abschnitt 2.1.2 beschrieben wurde, können XML-Dokumente als Bäume aufgefasst werden. Da Bäume hierarchisch und nicht linear strukturiert sind, wird im Fol- genden von Baum-Edit-Distanzen gesprochen. Diese messen die Distanz zweier Bäume als die Anzahl von Einfügeoperationen, Löschoperationen oder Umbenennoperationen auf Knoten [Guh02, S. 288]. So wie bei der Levenshtein Distanz wird auch hier die Distanz als die Sequenz von Transformations-Operationen mit minimalen Kosten definiert, welche nötig sind, um einen Baum in einen anderen zu überführen. Guha und Liang weisen in [Guh02, S. 288] und [Lia05, S. 1] darauf hin, dass die Berechnung der Edit-Distanz sich als sehr kostspielig erwiesen hat. Deshalb wird auch zur Messung der Distanz zwischen Bäumen dort nahegelegt, die Distanz-Messung mithilfe der Einführung von Heuristiken¹¹ durchzuführen. Die Gesamtheit der dort eingesetzten Maßnahmen wird als Approximate XML Join bezeichnet und im Rahmen eines Frameworks implementiert. Das wird zur Abgrenzung des in dieser Arbeit präsentierten eigenen Ansatzes in 3.2 noch einmal auf- gegriffen.

2.2.3 Werte-Distanzen

Mithilfe der Werte-Distanzen wird die Differenz zweier Objekte aus der Differenz der Sub- bausteine abgeleitet. Die Berechnung der Differenz kann dabei sowohl linear, auf der Folge von direkten Teilkomponenten einer Komponente, als auch über die Erkennung von Mus- tern innerhalb der Teilkomponenten erfolgen. Ferner lassen sich die Teilkomponenten auch als Punkte eines mehrdimensionalen Raumes durch trigonometrische Werte-Distanzen dif- ferenzieren. Sollten Abhängigkeiten der Teilkomponenten untereinander einbezogen wer- den, so wird auch mit quadratischen Werte-Distanzen ein entsprechender Ansatz vorge- stellt. Das Unterkapitel wird mit Distanzvorschriften auf Mengen abgeschlossen.

Lineare Werte-Distanzen

Minkowski-Distanz Die Minkowski-Distanz definiert eine Familie metrischer Funktionen zur Messung der L-Distanzen [Zez06, S. 10]. Sie ähnelt der p-Norm zur Ableitung von Me- triken, welche anhand des Beispiels 1 (s. S. 10) veranschaulicht wurde. Die Minkowski-Dis- tanz spezifiziert die p-Norm auf n-dimensionalen Vektoren reeller Zahlen wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Es sei angemerkt, dass damit der Aspekt der Distanz als der Betrag der Differenz zweier Werte hinzugefügt wird. Dies entspricht einem zusätzlichen Schritt, welcher im Zusammenhang mit der p-Norm außerhalb der Gleichung durchgeführt wurde.

SimSearch-Distanz Die innerhalb des SimSearch Frameworks angewendete Distanzfunktion wurde bereits vorgestellt. Jetzt wird noch ihre Einordnung zu den linearen WerteDistanzen sowie eine formale Berechnungsvorschrift dargestellt.

Wie bereits erwähnt, profitiert die SimSearch-Distanz von der Kenntnis der minimalen und maximalen Wertausprägung bestimmter Attribute. Dadurch wird der Wertebereich, der den jeweiligen Datentypen zugrunde liegt, solange entsprechend eingeschränkt, bis das System durch die Aufnahme einer kleineren oder größeren Wertausprägung den Wertbereich an neue Gegebenheiten anpasst.

Abbildung in dieser Leseprobe nicht enthalten

Da das System eigenständig prüft, welche Attribute eines Datensatzes mit welchen Attributen eines anderen verglichen werden können, kann die formale Definition nur für Attribute angegeben werden, welche vom System als passende Vergleichskandidaten akzeptiert worden sind. Deshalb kann angenommen werden, dass die Attribute jeweils passende Datentypen aufweisen. Ferner wird statt der Distanz direkt die Ähnlichkeit berechnet, weshalb der Wert von 1 subtrahiert werden muss. Damit lässt sich die SimSearch-Distanz für reelle Zahlen wie folgt definieren:

Sei I der Datentyp des i-ten Attributs

mx(I) sei der maximale Wert des Datentyps I

mi(I) sei der minimale Wert des Datentyps I

(x1, ..., xn) seien die Attribute eines Dokumentes A

(y1, ..., ym) seien die Attribute eines Dokumentes B

Abbildung in dieser Leseprobe nicht enthalten

Zur Berechnung der Distanz auf Zeichenketten wird innerhalb der Rechenvorschrift Leven- shtein mit einbezogen. Dies geschieht unterhalb einer als Schwellwert (Threshold) ausge- wiesenen maximalen Längendifferenz. Aufgrund dessen kann der Zeichenketten-Ähnlichkeit- Algorithmus (SSC) nicht direkt den Werte-Distanzen zugeordnet werden (s. S 90).

Sequenzalignment und Pattern Matching

Unter dem Sequenzalignment wird eine aus der Bioinformatik stammende Methodik ver- standen, welche dazu dient, Zeichenketten aufeinander abzugleichen (synonym: alignie- ren). Dabei sollen die Muster einer Zeichenkette in anderen wiedergefunden werden, wes- halb das Verfahren zu einen Teilgebiet der Mustererkennung (Pattern Matching) gehört. Es kann zwischen zwei Informationen bezüglich des Alignments unterschieden werden. Zum einen kann eine globale Übereinstimmung mehrerer Teilmuster beider Sequenzen durch eine positive Zahl ausgedrückt werden. Zum Anderen kann ein Teilbereich inner- halb beider Sequenzen lokalisiert werden, welcher besonders hohe Übereinstimmungen aufweist.

Im Folgenden wird ein bekannter Algorithmus zum Pattern Matching angegeben sowie zwei weitere, welche die Probleme des globalen und lokalen Sequenzalignment lösen:

Knuth Morris Pratt (KMP) Der Algorithmus Knuth Morris Pratt sucht die Position einer Zeichenkette M der Länge m innerhalb einer anderen, längeren Zeichenkette T der Län- ge n. Es ist leicht, einen naiven brute-force Ansatz für dieses Problem anzugeben. Um die Zeichenkette M (Muster) innerhalb der Zeichenkette T (Text) finden zu können, muss lediglich das Muster M an jeder Stelle der Zeichenkette T angelegt werden und die m Zei- chen der Muster-Zeichenkette mit den durch sie maskierten m Zeichen der Zeichenkette T verglichen werden. Sollte das Muster mit den Zeichen nicht übereinstimmen, so wird das Muster weitergeschoben und wieder alle m Zeichen beider Zeichenketten verglichen. Dieser Ansatz erfordert jedoch beim Nichtvorhandensein des Musters innerhalb der Zeichenkette (worst-case) m × n Vergleiche.

Der KMP Algorithmus profitiert gegenüber dem brute-force Ansatz von der Kennt- nis des bislang untersuchten Präfixes im Falle des Abbruchs beim mi-ten Zeichen. Der Algorithmus weiß demnach nicht nur, ob, sondern auch wieweit die beim Abbruch vergli- chenen Zeichenketten miteinander übereingestimmt haben. Um diese Information sinnvoll nutzen zu können, wird eine Fehlerfunktion auf dem Muster berechnet, welche pro Posi- tion innerhalb des Musters angibt, um wie viele Zeichen weitergesprungen werden kann, da der Vergleich an dieser Position nicht erfolgreich ausfallen kann. Zur Berechnung der Fehlerfunktion wird das Muster einmal mit sich selbst verglichen und dabei die Länge der Wiederholungen des Präfixes des Musters gespeichert. Sollte ein Teil des Musters dem Präfix des Musters entsprechen, so kann aus der Länge der Übereinstimmung darauf geschlossen werden, dass bei einem Abbruch des Vergleichs bei der Wiederholung des Prä- fixes innerhalb des Musters, die gespeicherte Position der Anzahl der Zeichen entspricht, welche übersprungen werden können. Dadurch kann sowohl eine Teilmenge der n Zeichen aus T , als auch eine Teilmenge der m Zeichen aus M vor überflüssigem Vergleich bewahrt werden. Dies verbessert die Laufzeit auf O(n + m).

Needleman-Wunsch und Smith-Waterman Der Needleman-Wunsch Algorithmus ermöglicht die Berechnung des globalen Sequenzalignments (GSA). Die Berechnung ähnelt stark der linearen Edit-Distanz nach Levenshtein. Aufgrund des bioinformatorischen Hintergrunds sollen jedoch sogenannte Gaps (Lücken) zugelassen werden. Dies lässt eher den evolu- tionären Vergleich von DNS (DNA) Sequenzen zu [Nee69, S. 443]. Im Unterschied zu Levenshtein werden die Kosten einer Operation nicht frei vergeben, sondern mittels einer Kostenfunktion berechnet.

Während die ursprüngliche Definition des Needleman-Wunsch-Algorithmus keine MatrixRekurrenzen enthalten hat, wurden diese in einem Dokument von Waterman, Smith und Beyer erstmals eingeführt [MSW76].

Der Smith-Waterman-Algorithmus dagegen berechnet das lokale Sequenzalignment (LSA), welches jedoch unter bestimmten Bedingungen auch durch Backtracking mithilfe des Needleman-Wunsch-Algorithmus berechnet werden kann. Dabei sollen zwei Teilsequenzen zweier Zeichenketten lokalisiert werden, die im Rahmen beider Zeichenketten die höchste Übereinstimmung aufweisen. Da, wie anfangs erwähnt, die Lösung des GSA und LSA nur im Rahmen der Bioinformatik und damit für eine sehr begrenzte Teilmenge von Zei- chenketten (DNS-Strukturen) von Bedeutung ist, wird an dieser Stelle auf allgemeinere Metriken näher eingegangen.

Trigonometrische Werte-Distanzen

Als trigonometrische Werte-Distanz wird im Folgenden speziell das Kosinusmaß betrachtet. Dieses berechnet die Ähnlichkeit zweier Vektoren als deren Winkel bezüglich des Nullvektors [Sch06, S. 34] und kann wie folgt definiert werden:

Abbildung in dieser Leseprobe nicht enthalten

Der hiermit ermittelte Ähnlichkeitswert hat einen Wertebereich zwischen [-1,1]. Um das Ergebnis den Ergebnissen bislang vorgestellter Distanz-/ Ähnlichkeits-Werte anzupassen, muss dieses noch zusätzlich halbiert und anschließend 0,5 addiert werden. Zur Ermittlung der Distanz braucht dieser Wert, so wie auch bei allen anderen zwischen 0 und 1 normierten Verfahren, von 1 subtrahiert zu werden [Sch06, S. 232].

Das Kosinusmaß wird häufig im Zusammenhang mit der Berechnung der Distanz von Zeichenketten, welche aus mehreren Termen bestehen, angeführt. In der letzten Zeit gewinnt dieses Verfahren im Rahmen der immer populärer werdenden Kernel-Funktionen zunehmend an Bedeutung (s. S. 46).

Quadratische Werte-Distanzen

Die quadratischen Werte-Distanzen zeichnen sich dadurch aus, dass sie Zusammenhänge zwischen den einzelnen Dimensionen eines Vektors berücksichtigen können. Diese Anfor- derung wird bei denjenigen Datentypen gestellt, bei welchen die Aussagekraft eines At- tributes von weiteren Attributen vervollständigt wird. Dies ist z. B. bei Bildobjekten der Fall. Inwieweit ein Bild als rot eingestuft werden kann, wird nicht nur anhand des Anteils der roten, sondern auch der Orange und Magenta Farbanteile bestimmt. Im Unterschied zu linearen Werte-Distanzen werden die quadratischen Werte-Distanzen mit einer qua- dratischen n × n Matrix M multipliziert. Die Einflussnahme der einzelnen Dimensionen aufeinander wird durch einen Wert zwischen 0 und 1 repräsentiert, welcher entlang der Diagonalen gespiegelt innerhalb der quadratischen Matrix abgelegt wird [Zez06, S. 11]. Formal kann die quadratische Werte-Distanz wie folgt definiert werden:

x und y seinen zwei n-Dimensionale Vektoren.

Abbildung in dieser Leseprobe nicht enthalten

Auch wenn bereits eine Reihe effizienter Algorithmen zur Berechnung quadratischer Di- stanz vorgelegt werden konnte, ist die Berechnung dieser immer noch sehr CPU-intensiv (siehe [Sei98, Abstract]). Es wird deshalb empfohlen, die Berechnung - wie bei der hier- archischen Edit-Distanz - durch die Einführung von Heuristiken zu beschleunigen. Da im Rahmen des SimSearch Frameworks XML-Daten untersucht werden, welche selten als Grundlage zu Kodierung von Medieninhalten verwendet werden, spielt die Betrach- tung von Zusammenhängen zwischen den Attributen an dieser Stelle eine rein theoretische Bedeutung (siehe [Sei98]).

Mengen-Werte-Distanzen

Die Ähnlichkeit bzw. Distanz kann auch bei disjunkten Mengen direkt berechnet werden. Eine einfache Berechnungsvorschrift hierzu wurde bereits anfangs des Jahrhunderts von Paul Jaccard angegeben. Der nach ihm benannte Jaccard-Koeffizient misst die Ähnlichkeit zweier Mengen und lässt sich wie folgt formalisieren:

A und B seien zwei Mengen

Abbildung in dieser Leseprobe nicht enthalten

Analog kann die Distanz-Metrik angegeben werden:

Abbildung in dieser Leseprobe nicht enthalten

Darüber hinaus kann dieser Ansatz auch für n-Mengen angegeben werden: M₁ ... M_n seien n-Mengen

Abbildung in dieser Leseprobe nicht enthalten

Die Anwendung des Jaccard-Koeffizienten wird an dieser Stelle wegen ihrer Einfachheit anschaulich demonstriert:

A sei die Menge {1, 2, 3, 4, 5, 6}

B sei die Menge {1, 2, 3, 7, 8, 9}

Dann beträgt die Ähnlichkeit beider Mengen gemessen mit dem Jaccard-Koeffizienten

Abbildung in dieser Leseprobe nicht enthalten

Auffällig an dem Ergebnis ist, dass die erwartete Ähnlichkeit (ohne Betrachtung der Di- stanzen zwischen den nicht übereinstimmenden Elementen) 0,5 betragen sollte, da die Mengen genau zur Hälfte identisch sind. Dieser Missstand ist auf der Vereinigung der Mengen im Divisor zurückzuführen. Um diesem entgegenzuwirken, wurde die als Dice’s- Koeffizient bekanntgewordene Erweiterung eingeführt. Diese ist definiert als:

Abbildung in dieser Leseprobe nicht enthalten

und erlaubt in dem hier vorliegenden Beispiel die Erreichung der erwarteten Ähnlichkeit:

Abbildung in dieser Leseprobe nicht enthalten

2.2.4 PlusMinus-Ahnlichkeit

Beim inhaltlichen Vergleich zweier komplexer Komponenten wird versucht, die Attribute einer komplexen Komponente auf die Attribute der anderen möglichst passend abzubil- den. Sollte eine Abbildung gefunden werden, so wird von einem Mapping (Zuordnung) der Attribute gesprochen. Da die Anzahl der Attribute, die die Komponenten beschrei- ben, unterschiedlich sein kann, besteht damit eine Menge an Attributen, zwischen denen kein Mapping zustande kommen kann. Dem Postulat der Symmetrie kann entnommen werden, dass die Ähnlichkeit bzw. Differenz unabhängig davon, welche der beiden Kom- ponenten mehr Attribute aufweist, derselbe Ähnlichkeits-Wert zugeordnet werden muss. Um dem Endnutzer die Information, welche der beiden Komponenten mehr Attribute zum Vergleich aufweisen, nicht vorzuenthalten, wird an dieser Stelle die Differenzierung der beiden Ausgangsmengen vorgeschlagen. Im Falle des Vergleichs eines Dokumentes mit einer verhältnismäßig geringen Anzahl an Attributen mit einem attributreicheren Doku- ment wird die Ähnlichkeit mit einen negativen Vorzeichen versehen. Da der Betrag dieses Wertes dennoch dem Wert entspricht, welcher bei der Betrachtung beider Komponenten in umgekehrter Reihenfolge zustande kommen würde, kann an dieser Stelle weiterhin von Symmetrie gesprochen werden. Es wird noch gezeigt, dass die PlusMinus- Ähnlichkeit des SimSearch Frameworks auch alle anderen Postulate des Metrischen Raumes einhält und damit bei dieser von einer echten Metrik gesprochen werden kann. Entsprechend kann auch bei struktureller Ähnlichkeit zwischen Ähnlichkeit großer Teilkomponenten mit Teil- komponenten einer größeren, auch diese Struktur aufweisenden Datei, der strukturellen Übereinstimmung zwischen zwei Dateien oder dem Enthalten von strukturell gleichen oder ähnlichen Komponenten anderer Dateien unterschieden werden.

Die Ergebnismenge im Rahmen des Frameworks wird in Form einer linear sortierten Menge dargestellt. Unter der Voraussetzung¹², dass die Ähnlichkeiten als diskrete Pro- zentwerte ausgedrückt werden, kann eine Aufteilung der Menge in einen Bereich von 0% bis 100% sowie einen von -99% bis -1% vorgenommen werden. Bei zentraler Anordnung identischer Elemente innerhalb dieser Skala werden weitere Elemente absteigend nach der positiven Ähnlichkeit links, und absteigend nach der negativer Ähnlichkeit rechts angezeigt. Diese Darstellung lässt damit die Unterbringung einer weiteren Information zu, welche über die reine Ähnlichkeit hinausgeht. Da die inhaltliche Ähnlichkeit nur den Unterschied der Anzahl der Vergleichsattribute aufweist, wird der Bereich demnach so unterteilt, dass absteigend ähnliche Komponenten mit größerer Attributenanzahl links und die mit kleinerer rechts stehen. Der Nutzer profitiert bei dieser Darstellung von der zusätzlichen Information der Komplexität der ausgewiesenen Dokumente.

2.2.5 Bildung von Teilmengen

Partitionierung

Mit Partitionierung wird im Rahmen der Mengenlehre die Unterteilung einer Menge in nichtleere, disjunkte Teilmengen bezeichnet [Cha01, S. 296]. In der Informatik bezeich- net man als Partition eine allgemeine Ansammlung von Daten und gleichzeitig die von Betriebssystemen verwendete Einteilung für physikalische Laufwerke. Sie bietet Raum für die Unterteilung des Suchraumes und ermöglicht damit Speicherstrukturen. Dadurch stellt sie eines der fundamentalen Prinzipien zur Einteilung der Daten dar. In der Literatur werden drei Partitionierungsverfahren zur Ähnlichkeitssuche hervorgehoben (siehe [Zez06, S. 20]). Die Objekte werden in Ähnlichkeitsbereiche unterteilt, wodurch die Bereich-Suche ermöglicht wird. Das erste Verfahren heisst Ball-Partitionierung (engl. Ball Partitioning) und unter- teilt den Suchraum in Objekte, welche bezüglich eines Pivot Elementes über einer zuvor berechneten, mittleren Distanz dm liegen (S₂), und solche, deren Distanz kleiner ist als dm (S₁). Da hierbei die mittlere Distanz erst ermittelt werden muss und anschließend der Suchraum in nur zwei, in etwa zur Hälfte gleichelementrige Räume unterteilt wird, findet im Rahmen des SimSearch Frameworks eine etwas abgeänderte Variante dieses Partitionierungsansatzes statt.

Das zweite Partitionierungsverfahren wird als Generalisierte-Hyperebenen-Partitionierung (engl. Genaralized Hyperplane Partitioning) bezeichnet. Dieses Verfahren unterteilt den Suchraum ebenfalls in zwei disjunkte Bereiche. Diesmal jedoch nicht anhand eines, sondern anhand zweier Pivot Elemente. Diese stellen beliebig gewählte Elemente dar. Die Unterteilung entsteht entlang eines imaginären, mittig orthogonal zu dem zwischen den Pivot Elementen bestehenden Distanzvektor stehenden Teilungs-Vektors. Dieser entsteht, indem alle Komponenten in Abhängigkeit davon, welcher der Pivot Elemente diesen näher sind, einem der Suchräume zugewiesen werden.

Das dritte Verfahren unterteilt die Ebene in drei Suchräume S₁, S₂, S₃. Dabei wird ähnlich wie bei Ball-Partitionierung vorgegangen, allerdings mit dem Unterschied, dass der mittlere Distanzradius dm um p verkürzt wird. Der gekürzte Bereich stellt den ersten Suchraum S₁ dar. Der zweite Suchraum S₂ entspricht einem Ring, welcher einer Ball- Partition mit dem Distanzradius dm + p abzüglich der Partition S₁gleicht. Dieser Such- raum wird im Rahmen des Verfahrens ausgeschlossen. Aufgrund des Ausschlusses wird das Verfahren auch als Mitte-Ausschluss-Partitionierung (Excluded Middle Partitioning) bezeichnet. Der dritte Suchraum S₃ besteht aus allen übrigen Elementen.

Das SimSearch Framework definiert Distanzbereiche in Form von Ähnlichkeitsrelationen. Diese Relationen werden für primitive Datentypen (Attribute) nicht gespeichert, sondern mit dem SSC-Algorithmus¹³ berechnet. SSC liefert einen Ähnlichkeitswert, über den eine eindeutige Zuordnung zu einer der Ähnlichkeitsrelationen möglich ist. Da seitens des Nutzers beliebig viele (n) Ähnlichkeitsrelationen vergeben werden können, entspricht eine Ähnlichkeitsrelation mit dem höchsten Ähnlichkeitswert bei räumlicher Betrachtung einer Ball-Partition S₁. Alle weiteren entsprechen weiter angesiedelten Ringen mit höheren Distanzradien und damit weiteren S₂, ..., Sn Suchräumen.

Clustering

Unter Cluster Analyse - beziehungsweise dem Clustern - wird eine Unterteilung einer Menge in Teilmengen verstanden, welche über ähnliche Eigenschaften verfügen. Dabei findet eine Art Klassifizierung oder auch Kategorisierung bzw. Segmentierung der vor- handenen Objekte statt ([Ber99b, S. 141], [Bal07, S. 1]). Sowohl beim ”Clustern“alsauch bei der Partitionierung werden demnach Mengen in kleinere Mengen unterteilt. Bei der Partitionierung werden die Mengen jedoch nur so unterteilt, dass eine spätere Suche durch Einschränkung des Suchbereichs vereinfacht wird. Beim ”Clustern“dagegenistdieUnter- teilung mit der semantischen Bedeutung der Daten verbunden. Aufgrund hoher Abstrak- tion und Bündelung der Informationen gehört das ”Clustern“auchzuAufgaben,welche jenseits von Mengenlehre und Speicherstrukturen von allen Menschen täglich durchge- führt werden. Das Sortieren der Post oder Zeitschriftenabos, die Unterteilung der Wäsche in bunte oder weiße, die Kategorisierung der Schallplattensammlung und viele andere Tä- tigkeiten setzen eine sinnvolle Unterteilung und damit Cluster Analyse voraus ([Ber99b, S. 135]).

Dimensionsreduktion

Als ”Dimensioncurse“,alsoFluchderDimensionalität,werdenProblemebezeichnet,wel- che im Umgang mit hoch dimensionalen Räumen auftreten.¹⁴ Mehrere Verfahren wurden vorgeschlagen, um diesen auszuweichen. Unter anderen: Z-Ordering [Lie08, S. 2], Locality Senitive Clustering, Singular Value Decomposition (SVD) [Yu02, S. 19], Reduktion und Hashing [Yu02, S. 6] sowie die Hilbert Kurve [Yu02, S. 20]. Beim letztgenannten werden je zwei Dimensionen mittels einer Hilbert Kurve zu einer Dimension kleiner skaliert. Auch der Einsatz von Supernodes des X-tree (siehe 2.4.3) dient zur Reduktion des Fluches [Yu02, S. 14]. So genannte Raumfüllungs-Kurven bieten die Möglichkeit, eine totale Ordnung auf Punkten mehrdimensionaler Räume zu erreichen, wodurch diese in eine Dimension gebracht werden können.¹⁵

Das SimSearch Framework verwendet einen eigenen Ansatz der Dimensionsreduktion. Dieser basiert auf Bildung von Signaturen (s. S. 55). Ferner wird das bekannte Hashing eingesetzt. Da sonst von keinem der hier erwähnten Verfahren Gebrauch gemacht wurde, seien diese nur der Vollständigkeit halber erwähnt, sie werden jedoch nicht weiter be- handelt. Abschliessend sei noch erwähnt, dass im Rahmen der Kernel Funktionen (siehe auch 3.3.4) ein umgekehrter Ansatz zu beobachten ist. Dort findet eine Abbildung eines gegebenen Vektor-Raums in einen höher dimensionalen Vektor-Raum statt (siehe [Bal06, S. 1] [Cha01, S. 10]). Die Vorteile ergeben sich anschließend aus einfacheren Berechnungsvorschriften, welche parallel¹⁶ ausgeführt werden können.

2.3 Logische Kombination der Distanzwerte

Wie bereits im Abschnitt 2.1.1 gezeigt wurde, können komplexe Daten als eine hierar- chische Zusammenstellung primitiver Daten betrachtet werden. Daraus resultierend kann die Ähnlichkeit zweier komplexer Datensätzte auch aus der Ähnlichkeit ihrer primitiven Bestandteile unter Berücksichtigung ihrer hierarchischen Anordnung hergeleitet werden. Die Distanz der primitiven Werte kann relativ einfach unter Berücksichtigung der für die jeweiligen Attribute geltenden minimalen und maximalen Werte ermittelt werden.¹⁷ Die Kombination der Zwischenergebnisse stellt einen weiteren Parameter dar, welcher sich auf das Gesamtergebnis auswirkt. Da eine detaillierte Behandlung aller mathematischen Grundlagen den Rahmen der Arbeit sprengen würde, wird im Folgenden die Aussagenlo- gik als essentielle Grundlage - nur das Thema betreffend - umrissen. Die Prädikatenlo- gik wird aufgrund ihres geringeren Bekanntheitsgrades und ihres Einsatzes innerhalb des SimSearch Frameworks ausführlicher behandelt.

2.3.1 Aussagenlogik

Die Aussagenlogik erlaubt eine logische Verknüpfung von Wahrheitswerten von Elemen- taraussagen. Eine Elementaraussage kann nur entweder wahr oder falsch sein. Über lo- gische Verbindung mehrerer Elementaraussagen durch Junktoren kann eine komplexere Aussage formuliert werden, welche nach Substitution der Elementaraussagen durch ihre Wahrheitswerte ihrerseits ebenfalls entweder wahr oder falsch ist. Die Junktoren stellen damit als logische Verknüpfung das Bindeglied von Aussagen dar und ermöglichen die Formulierung logischer Aussagen.

Innerhalb des Unterkapitels 2.2.1 wurden zwei Verfahren zur rechnerischen Ermittlung der Distanz vorgeführt. Während die Berechnung der Distanz mithilfe des Satzes von Py- thagoras keinen Gebrauch von der Aussagenlogik macht¹⁸, wurde bei der ausführlichen Beschreibung der SimSearch Distanz im Unterkapitel 2.2.3 darauf hingewiesen, dass die Berechnung der Distanz von Zeichenketten die Ergebnisse zweier Ansätze kombiniert. Da der Zeichenketten-Vergleichsalgorithmus (SSC) zwei Fallunterscheidungen beinhaltet, wurde auf die algorithmische Formulierung (S. 90) verwiesen und damit die Aussagenlogik indirekt mit einbezogen.

2.3.2 Pr ädikatenlogik

Die Prädikatenlogik ermöglicht die Beantwortung einer indirekt gestellten Frage durch das Auffinden von Kombinationen innerhalb einer Wissensbasis, welche den innerhalb der Frage formulierten Bedingungen genügen. Sie stellt damit eine Erweiterung der Aussagenlogik dar. Sie erweitert diese um Quantoren, Funktions- und Prädikatensymbole. Durch Quantoren kann ausgedrückt werden, dass eine Eigenschaft für alle Objekte gilt oder dass ein Objekt existiert, welches diese Eigenschaft aufweist. Durch Funktions- und Prädikatensymbole kann dagegen ausgedrückt werden, in welchen Beziehungen Objekte zueinander stehen oder welche Eigenschaften diese aufweisen [Sch99, S. 51].

Bei der Auswertung einer logischen Aussage müssen alle in der Aussage formulierten Va- riablen innerhalb der zur Auswertung gestellten Daten die Variablen belegen können, was die Auswertung auf einen homogenen Datenbereich¹⁹ einschränkt. Eine prädikatenlogische Aussage dagegen erlaubt die Einbeziehung heterogener Datentypen. Durch den Einsatz des All Quantors und des Existenz Quantors wird die Menge aller Daten auf die Menge derjenigen Daten automatisch reduziert, welche die zur Auswertung nötigen Prädikat - Belegungen enthalten.

Die Prädikatenlogik kann durch prädikatenlogische Resolution auch dazu genutzt werden, neues, nicht explizit gespeichertes Wissen zu generieren und dieses bei der Auswertung einzubeziehen. Dies ähnelt der Vererbung von Eigenschaften im Rahmen von OOP, basiert jedoch auf Verknüpfung von logischen Aussagen, wodurch es sich eher um Kategorisierung als um ”hartverdrahtete“Klassifizierunghandelt. Da innerhalb des SimSearch Frameworks heterogene Datentypen verglichen werden, kön- nen mithilfe der Prädikatenlogik Aussagen über zufällige Daten formuliert werden, welche beim Nachweis gewisser Eigenschaften automatisch resultiert²⁰ werden können. Dies erlaubt auch polymorphe²¹ Verknüpfungen von Komponentenklassen, wodurch Abweichungen bei der Bezeichnung von Attributklassen ohne Änderungen des Datensatzes durch Substitution umgangen werden können.

[...]

---

¹ Wahrheitswerte, eindeutige Zuordnungsparameter [Nie09]. 3

² Siehe Kapitel ”KlassifizierungvonDatentypen“[Nie[09],S.10 ].

³ ”TransportDokumente:XML“[Nie[09],S.17 ].

⁴ Außer der Blattposition bei Attributen i. S. v. XML [W3C06], [w3s10]. 5 Sequentiell hintereinander schreibbare, nicht transiente Attribute.

⁵ Vergleiche:

⁶ ”IntelligentsearchonXMLdata“[Bla[03],S.120 ].

⁷ Siehe hierzu auch [Nie09, S. 24] und in voller Ausführlichkeit [BL].

⁸ Ähnlichkeit=1-Distanz.

⁹ Diese werden im Zusammenhang mit der Minkowski Distanz auf S. 16 noch mal aufgegriffen.

¹⁰ Zum Aufbau gängiger Datentypen siehe [Nie09].

¹¹ Die Erlangung zufriedenstellender Ergebnisse unter Wissens- und Zeitmangel [Gig00]. 3 )= 3 ×4 12 =2 Ferner existiert auch eine Erweiterung des Koeffizienten für Vektoren [Zez[06], S. 14 ]. Diese wird als Tanimoto Ähnlichkeit bezeichnet und kann wie folgt angegeben werden:

¹² Die Voraussetzung ist innerhalb des SimSearch Frameworks erfüllt.

¹³ Dieser wird auf Seite 90 dargestellt.

¹⁴ [Yu02, S. 9], [Lie08, S. 1], [R.W98, S. 1], [Gra06, S. 51].

¹⁵ Dies wird bei [Yu02] auf Seite 21 und 23 anschaulich dargestellt.

¹⁶ Meist auf GPU’s (Graphics Prozessing Unit).

¹⁷ Dies wurde bereits mehrmals und für das Framework in 2.2.1 und 2.2.3 auf den Seiten 10 und 16 gezeigt.

¹⁸ Die Berechnung kann rein mathematisch erfolgen.

¹⁹ Reduziert auf bestimmte Datentypen.

²⁰ Auswertung einer prädikatenlogischen Aussage.

²¹ Zum Beispiel WEIGHT ↔ GEWICHT oder MENSCH ← MUSIKER.