Dissertation: Semantische Datenintegration - Dr.-Ing. Birgit Kieler

München 2020, ISBN 978-3-7696-5265-9, 138 S., PDF-Download

(identisch mit / identical with: Wissenschaftliche Arbeiten der Fachrichtung Geodäsie und Geoinformatik der Universität Hannover ISSN 0174-1454, Nr. 359, Hannover 2020)

Kurzfassung

Datenintegration, Datenaustausch und Datenaktualisierungen sind im wissenschaftlichen Umfeld nach wie voraktuelle Themen. Geoinformationen werden zur Unterstützung in vielen Entscheidungen in Politik, Wirtschaft,Verwaltung, aber auch im Alltag benötigt. Im Datenintegrationsprozess verursacht das Kombinieren verschie-dener Datensätze aufgrund struktureller, geometrischer und semantischer Unterschiede erhebliche Probleme.In der vorliegenden Arbeit wurde ein zweistufiges Zuordnungsverfahren entwickelt, das einen Beitrag zur geo-metrischen und semantischen Datenintegration leistet. Im ersten Schritt wurde ein Objektzuordnungsverfahrenentwickelt, das Objektkorrespondenzen durch die geometrische Überlagerung zweier Datensätze mit Polygonob-jekten bestimmen kann. Mit Hilfe eines Gesamtähnlichkeitsmaß, das sich aus geometrischen und semantischenParametern zusammensetzt, werden die vom Verfahren identifizierten Objektrelationen bewertet. Das Verfahrenkann sowohl einfache (1:1) als auch komplexe (1:n, n:1, n:m) Relationen durch Aggregation von Nachbarobjektenbestimmen.Das Objektzuordnungsverfahren wurde in drei verschiedenen Testgebieten mit vier unterschiedlichen Datensät-zen getestet. Es kann Datensätze mit verschiedenen Maßstäben, z.B. 1:1.000 bis 1:25.000 berücksichtigen. Eswurden Datensätze untersucht, die semantisch vergleichbare, aber auch verschiedenartige Objekte besitzen. Ei-ne Besonderheit ist, dass Datensätze nicht als Partition vorliegen müssen, sondern auch Objektüberlagerungeninnerhalb der Datensätze zugelassen sind, auch wenn dies den Suchraum vergrößert.Durch den Vergleich mit manuell erstellten Referenzzuordnungen zeigt sich im Ergebnis, dass die im Objektzu-ordnungsverfahren verwendeten sehr einfachen Ähnlichkeitsmaße und festgelegten Schwellwerte in allen Testge-bieten sehr hohe Zuordnungsqualitäten erzielen können, in zwei Fällen sogar über 92 %. Und je ähnlicher sich dieMaßstäbe der Datensätze sind, desto vollständiger sind auch die richtigen Zuordnungen. Das bedeutet, dass dasVerfahren nur sehr wenige falsche Relationen identifiziert und somit für unterschiedliche Datensätze einsetzbarist.Im zweiten Schritt des Verfahrens erfolgt die Zuordnung der Objektklassen auf Schemaebene. Dazu werden ausden Ergebnissen der Objektzuordung Häufigkeitswerte abgeleitet und pro Testgebiet in vier unterschiedlichenMatrizen zusammengefasst. Neben Relationsanteilen wurden auch datensatzbezogene prozentuale Flächenanteileberechnet, die besonders bei großen Maßstabsunterschieden Vorteile bieten. Aufgrund verschiedener Sichtweisenkönnen Häufigkeitsmatrizen auch als bipartite Graphen betrachtet werden.Für die Zuordnung der Objektklassen wurden existierende Graphalgorithmen verwendet. Neben dem Ansatzdes Maximalen Matchings, das nur 1:1 -Schemarelationen in quadratischen Matrizen bestimmen kann, wurdeein heuristisches Verfahren entwickelt, das den Ansatz des Minimalen-2-Schnitts rekursiv anwendet. Mit demHeuristischen Verfahren können zusätzlich einseitig komplexe Schemarelationen bestimmt werden. Als Ergebnisentstehen in der Zuordnungsmatrix rechteckige Cluster, die sich nicht schneiden und nur pro Zeile und Spalteeine Zuordnung zulassen.Die Zuordnung der Objektklassen entspricht einer Unterteilung eines Graphen inkTeile, was einNP-vollständig-es Problem beschreibt, für das nach heutigem Kenntnisstand kein Algorithmus mit polynomieller Laufzeit exis-tiert. Um die nicht garantiert optimalen Ergebnisse des Näherungsverfahrens bewerten zu können, wurdenverschiedene ganzzahlige lineare Optimierungsverfahren entwickelt und mit dem existierenden Optimierer (IBMILOG CPLEX Interactive Optimizer 12.5.1.0) gelöst. Das primäre Optimierungsziel ist die Maximierung derHäufigkeiten innerhalb der Cluster, um die Zuordnung der Objektklassen durch die identifizierten Objektrela-tionen zu bestätigen. Zusätzlich wurde das Erzeugen von ausgewogenen Clustern hinsichtlich der Zellenanzahlpro Cluster als zweites Optimierungsziel eingefügt. Beide Ziele wurden kombiniert, einerseits gleichgewichtetund andererseits durch Einführung eines Ziels als harte Bedingung. Die Lösung mit der größten Durchschnitts-häufigkeit pro Zelle wird als beste Lösung ausgewählt.In den Ergebnissen zeigt sich, dass das Heuristische Verfahren beim Vergleich in den Kategorien Rechenzeit,Schnittmenge zum Matrixgesamtinhalt und zur Referenzzuordnung gegenüber den anderen Verfahren den erstenPlatz belegt. Die Optimierungsverfahren belegen aufgrund der sehr langen Rechenzeiten den zweiten Platz. DerVergleich der Heuristischen Lösungen mit den besten Optimierungslösungen zeigt, dass in allen Testgebietendie optimalen Lösungen mehr als 91% der Heuristischen Lösungen bestätigen. Das Näherungsverfahren stelltsomit einen effizienten Ansatz dar, um das Problem der Objektklassenzuordnung auf Schemaebene automatischzu lösen.

Data-Matching, Schema-Matching, Optimierung, ganzzahlige lineare Programmierung

Abstract

Data integration, exchange and updates are still challenging subjects in the current scientific context. Spati-al data are necessary to assist in political, economical, administrative, or common everyday life’s decisions.The combination of different datasets causes significant problems due to structural, geometric, and semanticdifferences during the data integration process.In this thesis a two-step matching approach has been developed to make a contribution to geometric and semanticdata integration. The first step consists of a data matching process in order to derive object correspondencesby the geometrical overlay of two polygon object datasets. Using a total similarity measure, composed fromgeometric and semantic parameters, object relations identified by the matching approach are being evaluated. Itis possible to determine as well simple (1:1) as complex (1:n, n:1, n:m) relations by aggregation of neighbouringobjects in the proposed approach.The data matching approach has been tested on three test areas consisting of four different datasets. It is possibleto handle datasets with different scales, ranging from 1:1.000 to 1:25.000. The examined datasets consist as wellof semantic similar as dissimilar objects. As a special feature datasets do not have to be presented as a partitionof the plane but object overlays within the datasets are allowed, even though the search area is expanded bythis.The usage of simple similarity measures and specified thresholds shows in comparison to manually createdreference data very good matching results in all three test areas, in two cases even higher than 92%. The moresimilar the scales of the datasets are, the more complete are the correct matches. That means, the presentedapproach does identify only few wrong relations and thus can be applied to different datasets.The second step comprises the matching of object classes on schema level. To achieve this frequency values arederived from the results of the data matching and subsequently summarized in four different matrices per testarea. Beside object relation values, also area based percentage values were calculated to offer benefits whendealing with large scale differences. These frequency matrices can also be considered as bipartite graphs.For the matching of the object classes existing graph algorithms were used. Besides the maximum matchingapproach that can only process square matrices and identifies simple 1:1 object relations, a heuristical approach,that uses the minimum-2-cut approach recursively has been developed. This heuristic approach allows to calcu-late additionally one-side complex 1:n/n:1 schema relations. As a result rectangular clusters that do not intersectand allow only one matching per row and column are created in the frequency matrices.The matching of object classes corresponds with the subdivision of a graph in k parts. That describes anNP-complete problem that can not be solved with an algorithm in polynomial time. To evaluate the notguaranteed optimal results of the approximation process different integer linear optimization approaches havebeen developed and solved with the existing optimizer (IBM ILOG CPLEX Interactive Optimizer 12.5.1.0). Theprimary optimization objective is the maximization of frequencies within the clusters to confirm the matchingof the object classes with the identified object relations. Additionally a second objective has been defined togenerate balanced clusters concerning the number of cells. Both objectives have been combined, on the one handwith a cost function and on the other hand by introducing one criteria as a hard constraint. The solution withthe highest average frequency per cell is selected as best solution.The results show the heuristic approach as the best concerning computing time, intersection to total contentof the matrix and to the manually created reference matchings in comparison to the other approaches. Theoptimization approaches are second place due to long computing times. Comparing the heuristic solutions withthe best solutions of the optimization approaches more than 91% of the heuristic results are confirmed by theresults of the optimization approaches in all test areas. The approximation approach represents an efficientapproach to solve the matching of object classes on schema level automatically.

Keywords:

data-matching, schema-matching, optimization, integer linear programming