Lehre

 

Klausureinsicht XML

xml-klausur

Wordle aus dem Inhalt der XML-Klausur

Die Klausureinsicht zur Klausur im 1. Prüfungszeitraum WS2015/16 findet am 8. März von 10 bis 11 Uhr in Raum 1110 (Uni Hochhaus) statt. Bitte amtlichen Lichtbildausweis zur Identifikation mitbringen.

Masterseminar WS2015/16

Masterseminar zum Thema record linkageIn diesem Semester wollen wir uns im Masterseminar mit dem Thema record linkage beschäftigen. Beim record linkage (auch als data matching, data linkage, entity resoluation, object identification oder field matching bekannt) geht es um das Aufspüren von identischen Objekten, häufig Personeneinträgen. Für das Seminar ist dabei alle Schritte des Matching-Prozesses von Interesse, von einzelnen Techniken der Vorverarbeitung bis hin zur Evaluation von Algorithmen. Die Evaluation von record linkage Algorithmen ist relativ schwer, da die ground truth in der Regel nicht bekannt ist und man daher Fehler simulieren muss.

Für unsere Forschung ist das Thema sowohl im Bereich des Semantic Web, wo identische Resourcen in unterschiedlichen Linked Open Data Beständen auftreten, als auch für unsere Kooperation mit den Historikern, die z.B. bei der Demographieforschung große Mengen von Personeneinträgen aus unterschiedlichen Quellen abgleichen müssen, relevant.

Einen guten Überblick über das Thema gibt das Buch »Data Matching« von Peter Christen, an dessen Aufbau wir uns im Seminar orientieren wollen.

Die Teilnehmer des Seminars sollen sich in ein Unterthema (z.B. String-Vergleiche) einarbeiten. Das entsprechende Kapitel des Buches mit der dazugehörigen Literaturliste dient als Startpunkt. Im Laufe des Semesters soll das Unterthema den Kommilitonen in einem Vortrag präsentiert werden. Gegen Ende des Semesters erwarten wir eine Ausarbeitung zu dem Unterthema im Umfang von ca. 10 Seiten.

Einen festen Vorbesprechungstermin gibt es (noch) nicht, bei Interesse bitte bei Dr. Jesper Zedlitz melden.

Sommersemester 2014

Im Sommersemester 2014 bieten wir folgende Lehrveranstaltungen an:

Kommunikationssysteme

Kommunikationssysteme ist eine Pflichtveranstaltung im Informatik-Bachelor-Studium. Sie besteht aus der Vorlesung und Übung. Die Vorlesung findet im CAP 2 Hörsaal C

  • dienstags um 12 Uhr und
  • mittwochs um 8 Uhr

statt. Die Vorlesungsfolien sind im OLAT zu finden.

Für die Übung gibt es zwei Termine:

  • Dienstag 8 Uhr und
  • Dienstag 16 Uhr

Beide Übungen finden im CAP 2 Hörsaal B statt. Für die Teilname an der Übung ist es erforderlich, sich im iLearn für die Übung anzumelden.

Links

Web-Technologien

Die Kurs Web-Technologien ist eine Veranstaltung für das Informatik-Master-Studium. Die Vorlesung findet donnerstags um 8 Uhr in CAP 2 Hörsaal B statt. Die Übung wird zweiwöchentlich angeboten. Sie findet im CAP 4 Raum 709 statt. Folgende Termine sind geplant:  5. Mai, 19. Mai, 2. Juni, 16. Juni und 30. Juni.  Es bietet sich an, einen eigenen Laptop mit zur Übung zu bringen, um die gezeigten Beispiele sofort selbst nachvollziehen zu können.

Links

Academic Writing

In dieser Veranstaltung geht es um den inhaltlichen Aufbau, die systematische Erstellung und die sprachliche und typographische Gestaltung von technischen Texten, insbesondere von technischen Abschlussarbeiten, Veröffentlichungen und den zugehörigen technischen Präsentationen. Es soll gezeigt werden, wie Denkgewohnheiten, die bei der Formulierung technischer Inhalte zu unklaren Ergebnissen führen, überwunden werden können. Der Modul umfasst mehrere Schreibübungen, deren Korrektur durch Diskussion im Plenum erfolgt.

Vorlesung und Übung finden donnerstags von 12 Uhr bis 16 Uhr im Unihochhaus Raum 1304 a statt.

Links

Bachelorarbeit: Anreicherung von Linked Data

Als Linked Data mit Techniken des Semantic Web zur Verfügung gestellte Daten bieten durch ihre maschinelle Interpretierbarkeit und die Möglichkeit, sie mit anderen Daten verbinden zu können, einen enormen Mehrwert im Vergleich zu traditionellen, abgeschlossenen Datensammlungen. Leider wird die Möglichkeit der maschinelle Interpretierbarkeit und der Verknüpfung dadurch genommen, dass Informationen in Textform (statt durch Individuen und Object Properties) angegeben werden. Man betrachte z.B. folgende Angaben zu einer Person:

  • Ort: Neustadt a. d. Aisch
  • Beruf: Tischlermeister
  • Datum: Ostern 1905

Mit allen drei Zeichenketten “Neustadt a. d. Aisch”, “Tischlermeister”, “Ostern 1905” kann eine Maschine nichts anfangen. Selbst ein Nutzer, der kein Deutsch kann, wird bereits Schwierigkeiten mit diesen Angaben haben. Im Sinn des Semantic Web ist das nicht.  Statt des Textes “Neustadt a. d. Aisch” wäre ein Verknüpfung zu dem entsprechenden Ortsindividuum, das diesen eindeutig beschreibt, besser, z.B. http://d-nb.info/gnd/4041928-9, http://gov.genealogy.net/NEUSCHJN59HN, opengeodb:21560 oder BLO:1470. Beim der Angaben des Berufes wäre es sinnvoll, eine Verknüpfung auf den Beruf “Tischler” in einer Taxonomie von Berufen anzugeben. So könnte die Person auch dann gefunden werden, wenn man nach “Handwerker” oder “jemand, der mit Holz arbeitet” sucht.  Zur Datumsangabe “Ostern 1905″ sollte 1905-04-23”  ergänzt werden, damit die Information maschineninterpretierbar wird.

Es ist klar, dass diese Anreicherung nicht vollautomatisch sein kann. Entwickelt werden soll ein Programm, dass einem Nutzer Vorschläge macht, welche Identifikation am wahrscheinlichsten ist. Gibt es mehrere Möglichkeiten (man denke an die Ortsangaben “Neustadt”), so soll dem Nutzer eine Liste von Vorschlägen bekommen, sortiert nach ihrer Wahrscheinlichkeit. Dabei kann man z.B. mit farblichen Kennzeichnungen arbeiten. Wurde für einen Text nur ein Vorschlag ermittelt, und hat dieser eine sehr hohe Wahrscheinlichkeit (z.B. >0.90), so wird der Datensatz als grün gekenntzeichnet. Gelb werden Datensätze gekennzeichnet, bei denen nur ein unscharfer oder mehrere ähnlich wahrscheinliche Treffer gefunden wurden. Rot könnten solche Datensätze markiert werden, für die kein vernünftiger Vorschlag gemacht werden kann. Auf dieser Weise kann ein Bearbeiter einfach auswählen, mit welcher Art von Problemen er sich beschäftigen möchte.

Indem man im Hintergrund im Programm Buch darüber führt, wie oft sich ein Nutzer für den ersten, zweiten usw. Vorschlag entschieden hat, kann man eine Bewertung angeben, wie gut der Algorithmus und enthaltene Heuristiken funktionieren.

Primär soll das Programm im Rahmen des Kiel Academic Index eingesetzt werden, in dem alle an der Universität Lehrenden von 1665 bis 2015 verzeichnet werden. Mit bereits 3.000 vorhandenen Personen bietet sich genug Material zum Testen der Algorithmen. Aber auch der Einsatz für weitere historische Daten ist vorstellbar, so dass man eine noch breitere Datenbestand zum Testen zur Verfügung hat.

Während es für die Identifikation von Ortsangaben bereits an der Arbeitsgruppe eine Arbeit läuft, gibt es für Zeitangaben und Berufsangaben noch etwas zu tun.

 

Bachelorarbeit: Extraktion von Datenstrukturen als Adressen

Bei der Arbeit mit semantischen Daten taucht immer wieder das Problem auf, dass Daten unterschiedlich modelliert wurden. Dabei kann z.B. in der einen Ontologien eine Data Property (ein Text) und in der anderen Ontologien Object Properties (Zusammenhänge zwischen Objekten) verwendet werden. Algorithmen, die ein Matching zwischen den Ontologien herstellen könnten, liefern aufgrund der unterschiedlichen Strukturen kein Ergebnis. Eine Kombination und Weiternutzung der Informationen – wie sie ganz im Sinne des Semantic Web wünschenswert wäre – wird so verhindert.

diagramm_adressen

Im Rahmen dieser Arbeit soll am Beispiel historischer Adressinformationen ein Algorithmus zur Analyse der Werte einer Data Property und der Erzeugung passender Klassen und Object Properties entwickelt werden. Hier einige Beispiel, um mit welcher Art von Werten man rechnen kann:

4 
5 
Am Wall 54 
Wilthen. Straße 16, III 
Wilthener Staße 13 
Wilthener Str. 21, Hths II 
Wilthener Str. 38, II 
Wilthener Str. 8, Eg 
Hannov. Str. 19A 
Burgwall 78 c 
Bredenbecksgang 5b 
Anstaltsstraße (Torhaus) 
Schlesw. Chausee 154 (Krankenhaus) 
Seidau 391 (Hammermühle) 
Torstr. 10/11 
Körliner Str. 4b 

Aus der Literatur sind regelbasierte und stochastische Ansätze (Hidden Markov Models) bekannt, mit denen man Adressen analysieren kann. Einer oder mehrere dieser Ansätze sollen implementiert und bewertet werden.

Im Vergleich zu bisherigen Arbeiten zur Verarbeitung von Adressen hat das hier zu bearbeitende Problem folgende Unterschiede:

  • Da es sich um historische Daten handelt, kann nicht auf ein heutiges Straßen- oder Postleitzahlenverzeichnis zugegriffen werden, welches in den meisten Arbeiten eine zentrale Rolle spielt.
  • Historische Adressbezeichnungen halten sich in der Regel an keine heute gültigen Muster.
  • Es ist bereits bekannt, aus welchem Ort (jedoch im Einzelfall nicht aus welchem Ortsteil) die Adressen stammen. Die meisten Probleme, die sich aus der Identifikation des Ortes (und meist der Postleitzahl) ergeben, entfallen somit.

Für die Bearbeitung der Aufgabe ist es nicht unbedingt notwendig, sich mit OWL, RDF oder sonstigen Semantic Web Techniken auszukennen. Die Grundkonzepte Class, Data Property und ObjectProperty sind aus anderen Sprachen geläufig, weitergehende Kenntnisse werden nicht benötigt.

Es steht ein ausreichend großer Korpus (Beispieladressen) zur Verfügung, so dass auch empirische Untersuchungen möglich sind, die eine Ausarbeitung abrunden würden.

Literatur

  • Srihari, Yang, Govindaraju: „Information Theoretic Analysis of Postal Address Fields for Automatic Address Interpretation“
  • Christen, Belacic: „Automated Probabilistic Address Standardisation and Verification“
  • Abbasi: „Information Extraction Techniques for Postal Address Standardization“

Rückschau: Seminar “Semantische Technologien” im Sommer 2013

puzzle-3dWir haben alle viel dazugelernt – in unserem Seminar “Semantische Technologien” im Sommersemester 2013. Dieses Themengebiet ist ja nun schon seit einiger Zeit im Zentrum der Arbeiten der AG Kommunikationssysteme, und es wird auch noch länger dort bleiben. Umso wichtiger, daß wir uns gegenseitig immer wieder um Kenntnisse zum Stand der Technik bereichern.

Zu diesem Seminar haben die folgenden Personen mit den folgenden Themen beigetragen (Ausarbeitungen zum Download):

Happy reading!

 

Bachelorarbeit: Darstellung von Linked Open Data

Linking Open Data cloud diagram, by Richard Cyganiak and Anja Jentzsch. lod-cloud.net/

Linking Open Data cloud diagram, by Richard Cyganiak and Anja Jentzsch. lod-cloud.net/

Im Semantic Web steht in der Linked Open Data Cloud eine große Menge an Informationen zur Verfügung, die jedoch in ihrer RDF-Form (in diesem Format liegen die Daten in der Regel vor) für einen Menschen nur sehr schwer lesbar sind. Man benötigt also eine Aufbereitung in Form von HTML-Seiten oder Grafiken (SVG oder auf HTML5-Canvas gezeichnet). Dabei gibt es zwei Orte, an denen diese Aufbereitung passieren kann: Server oder Client (sprich: Webbrowser).

Serverseitig: Erstellung von HTML-Code in einer Webanwendung

Bei der serverseitigen Aufbereitung werden die RDF-Daten von einer oder mehrerer Datenquellen innerhalb der Webanwendung (z.B. mit Java geschrieben) mit Hilfe einer Bibliothek zur RDF-Verarbeitung (z.B. das Jena-Framework) eingelesen und passender HTML-Code generiert. Diese wird dann per HTTP an den Client geschickt, wo der HTML-Code wie üblich im Browser dargestellt wird. Ebenso gut lässt sich statt HTML-Code SVG-Code für eine Grafik generieren.

Ein offensichtlicher Vorteil einer serverseitigen Lösung ist es, dass die “rohen” RDF-Daten den Server nicht verlassen. Da bei Linked Open Data sowieso von einem freien Zugang zu den Daten ausgegangen werden kann, ist dies hier jedoch kein wirkliches Problem.

Clientseitig: Lesen von RDF-Daten und Ändern des DOM-Baums

Bei einer clientseitigen Lösung liest der Webbrowser per Javascript RDF-Daten von einer oder mehrerer Datenquellen ein. Aufgrund der same origin policy benötigt man ggf. noch einen Proxy beim Betreiber der Webanwendung. Es mag mit Hilfe neuartiger Technologien (wie Websockets) möglich sein, dass es mittlerweile einfacher geht. Es gibt bereits einige Javascript-Bibliotheken zum Verarbeiten von RDF aus denen man wählen kann. Auch die Anfrage von SPARQL-Servern mit Hilfe von Javascript scheint möglich zu sein.

Bachelorarbeiten

Im Rahmen von zwei Bachelorarbeiten sollen beide Varianten implementiert werden, um einen Vergleich zu ermöglichen. Die Vor- und Nachteile beider Ansätze dürften bei der praktischen Umsetzung relativ gut deutlich werden. Das Anwendungsszenario ist ein Verzeichnis aller Professoren der CAU, dessen Daten als Linked Open Data für das Jubiläum im Jahr 2015 erarbeitet werden. Neben den lokal vorliegenden RDF-Daten der Professoren besteht durch Verbindungen mit der GND, DBPedia und weiteren Datenquellen die Möglichkeit, auch mit Verknüpfungen innerhalb der Linked Open Data Cloud zu experimentieren.

Bachelorarbeit: Optimierung der Reaktionszeit einer AJAX Webanwendung

HTML5 (Urheber: W3C)Von Nutzern bei der Arbeit mit Webanwendungen besonders störend wahrgenommen sind verzögerte Reaktionen des Systems. Durch die Verwendung von JavaScript und asynchronen Aufrufen hat sich im Vergleich zum klassischen HTML-Seitenaufruf schon viel getan. Aber auch hier muss oft auf Reaktionen des Servers gewartet werden. Dabei werden schon kleine Wartezeiten als lästig empfunden, längere Wartezeiten führen zu wiederholtem Absenden, da eine Störung vermutet wird.

Bei einem AJAX-Aufruf werden in der Regel nur sehr wenige Daten verschickt, das Senden und Empfangen dauert dementsprechend nicht lange. Bei mobilen Anwendungen fällt jedoch die Paketlaufzeit unangenehm auf. Egal wie klein das Datenpaket ist, der Weg zum Server und zurück – und damit die Reaktion des Systems –  dauern eine gefühlte Ewigkeit.

Mit HTML5 haben einige Techniken in den Browser Einzug gehalten, die Besserung versprechen. So lassen sich z.B. Daten schnell im Local Storage ablegen und im Hintergrund mit dem Server synchronisieren. Selbst wenn das etwas länger dauert, merkt es der Benutzer nicht. Er kann (un-)gewohnt schnell weiterarbeiten.

Im Rahmen der Bachelorarbeit soll untersucht werden, wie eine existierende Webanwendung, die bei den Benutzereingaben stark auf JavaScript setzt, mit Hilfe dieser neuen Techniken benutzerfreundlichen gemacht werden kann. Welche Techniken bieten welchen Vorteil? Muss die Server-Anwendung angepasst werden oder lassen sich die Optimierungen transparent einbauen? Lassen sich diese Optimierungen auch auf andere Webanwendungen übertragen?

Seminar »Technik des Semantic Web«

semantic_web„Semantic Web“ und „Linked Open Data“ (LOD) sind momentan heiße Themen sowohl in der Forschung als auch in der Wirtschaft und sogar in der Politik. Linked Data liegen in Form sogenannter Triples (Subjekt, Prädikat, Objekt) vor. Insgesamt geht es bei LOD um große Datenmengen: Bereits vor zwei Jahren umfasste die sogenannte „LOD-Cloud“ mehr als 31 Milliarden Triples.1

In diesem Seminar wollen wir uns mit der Technik hinter Semantic Web und Linked Data beschäftigen. Welche Software kommt zum Einsatz, um die Datenmengen des Semantic Webs zu speichern? Wie kann man auf die Daten zugreifen, und wie kann man Anfragen formulieren? Welche Technik verwenden bekannte Dienste für ihre „semantischen“ Daten?

Die gängige Abfragesprache für Linked Data ist SPARQL. In einem Vortrag sollen uns diese Sprache und ihre Besonderheiten vorgestellt werden.

Triples werden mit Hilfe von Triplestores gespeichert. Vier Opensource-Projekte, die damit werben, auch mit sehr große Datenmengen performant umgehen zu können, sind bigdata, owlim, Apache Jena und der Virtuoso Universal Server

Wie funktionieren diese Triplestores? Welche Besonderheiten in der Architektur des Triplestores gibt es, so dass schnelle Abfragen auch auf großen Datenmengen möglich sind? Wie werden Daten eingefügt/geändert? Was für Anfragen kann man an einen Triplestore stellen? Welche Art von automatisiertem Schlussfolgern (Reasoning) wird unterstützt?

Eine weitere Möglichkeit der Ablage von Linked Data ist ein Mapping auf existierende Datenbanken. In der Regel handelt es sich dabei um relationale Datenbanken, aber auch ein Mapping auf immer mehr in Mode kommende „No-SQL“-Datenbanken ist denkbar.

Zwei bekannte Projekte und Informations-Anbieter im Bereich LOD sind Wikidata und DBpedia. Welche Technik (Triplestore oder Mapping?) verwenden sie? Wie kann man auf die Daten zugreifen? Wie wird Information hinzugefügt?

Organisatorisches

Eine Vorbesprechung findet am 28.10.2013, 14:00 Uhr, im Raum 1110 (Uni-Hochhaus 11. Stock) statt.

 

¹ http://lod-cloud.net/state/ Version 0.3 vom 19. September 2011
² Diese vier Triplestores wurden im Rahmen des Berlin SPARQL Benchmarks verglichen.

Blogsatz: Auf Blogsuche mit dem Krabbler

web-crawlerIm Rahmen eines Praktikums habe ich die Aufgabe übernommen,  für das Blogsatz-Projekt einen Crawler zu entwickeln, welcher potentielle Blogkandidaten aufspürt. Hierzu sollte Bixo verwendet werden.

Was ist Bixo?

Bixo ist ein open source Toolkit, welches es ermöglicht, Webmining zu betreiben und Webseiten zu crawlen. Dieses Toolkit verwendet, wie auch der andere Teil von blogsatz, das Framework Cascading, damit das Ergebnis auch Cloud-tauglich ist.

Was macht einen Blogkandidaten aus?

Wir haben uns darauf verständigt, dass das Augenmerk zunächst auf .edu-Domains gelegt wird, da die Wahrscheinlichkeit, dass es sich bei Webseiten aus solchen Domains um wissenschaftliche Seiten handelt, höher ist als bei x-beliebigen Adressen.

Weiterhin werden vorerst nur Blogs berücksichtigt, die in der englischen Sprache verfasst wurden, da sich die spätere Bewertung auf englische Blogposts konzentriert.

Der Ablauf

In einer MySQL-Datenbank sind Seed-URLs (Start-URLs) hinterlegt, mit denen der Crawler beginnt. Ausgehend von diesen URLs hangelt sich der Crawler über die auf den Seiten enthaltenen Links auf weitere Seiten des Blogs. Links, die auf externe Seiten verweisen, werden zunächst nicht verfolgt, sondern werden als Seed-URLs in der Datenbank hinterlegt, so dass diese bei einem der nächsten Crawl-Durchläufe bearbeitet werden.

Auf jeder Seite wird eine Identifizierung der benutzen Sprache durchgeführt. Dies hat sich jedoch im Laufe der Entwicklung als nicht besonders einfach herausgestellt. Bixo bietet zwar durch Apache Tika eine Methode an, die die Sprache identifizieren soll, allerdings erhält man hiermit recht häufig keine sichere Aussage. Daher mussten weiter Methoden her. Die zweite Methode basiert auf der Buchstabenhäufigkeit auf der betreffenden Seite. Die auftauchenden Buchstaben werden gezählt und nach Häufigkeit sortiert zu einem String zusammengesetzt. Anschließend wird die Levenshtein-Distanz zu den Buchstabenhäufigkeits-Strings verschiedener Sprachen bestimmt. Für die Sprache Deutsch sieht dieser folgendermaßen aus: ENISRATDHULCGMOBWFKZPVJYXQ.

Hier wird nun die Sprache mit der geringsten Distanz als Ergebnis genommen. In den ersten Durchläufen hat sich gezeigt, dass die ermittelte Sprache bei einer Distanz < 10 meistens korrekt ist. Da die beiden Methoden jedoch weiterhin bei einigen Seiten keine sichere Ausgabe liefern konnten, wurde eine dritte Methode implementiert, die aus dem HTML-tag das ‘lang‘-Attribut extrahiert. Hierbei ist jedoch zu beachten, dass viele Webentwickler dieses Attribut erst gar nicht oder aber fehlerhaft setzen. So ist z.B. oft ‘lang=“en“’ zu finden, auch wenn die eigentliche Sprache der Seite Deutsch ist. Dies ist auch der Grund dafür, dass diese Methode nicht primär bzw. als einzige verwendet wird.

Flowchart - Erkennen der Sprache

Erkennen der Sprache

Neben der Erkennung der Sprache ist auch zusätzlich wichtig, zu erkennen, ob es sich bei der vorhandenen Webseite um einen Blog handelt. Hierbei haben wir uns zunächst auf die Erkennung von WordPress-Blogs beschränkt, da diese einfach durch das Vorkommen von ‘wp-content’ im head des HTML-Codes zu erkennen sind. Hierfür wird der Tika-Sax-Parser und der xPath-Ausdruck “/xhtml:html/xhtml:head/xhtml:link/@*” verwendet.

Die dritte Bedingung – dass es sich um einen Blog mit .edu-Domain handelt – wird durch einen simplen regulären Ausdruck an der URL geprüft:

http(s)?://(.+\.)+(edu).*

Aus den Ergebnissen ergibt sich nachfolgend des Attribut ‘candidate’, welches angibt, ob es sich bei der gecrawlten Seite um einen potentiellen Kandidaten handelt oder nicht. Diese Ergebnisse werden zusammen mit dem Inhalt der Webseite und dem Datum des Crawlens in eine weitere Tabelle ‘crawled’ geschrieben, welche später als Quelle für die weitere Verarbeitung dient.

Ausblick

Das Crawlen an sich wurde umgesetzt. Dies kann jedoch noch verbessert werden, indem die Analyse des HTML-Codes in verschiedene Cascading Pipes verteilt wird, wodurch in der Cloud eine höhere Geschwindigkeit erreicht werden kann. Weiterhin könnte implementiert werden, dass nicht nur WordPress-Blogs erkannt werden.

Für einen späteren produktiven Einsatz wäre natürlich auch noch wünschenswert, dass die Erkennung der Sprache weiter optimiert werden würde.