Hintergrund

Datenverarbeitung erfordert häufig das Zusammenfassen von Daten in Gruppen ähnlicher Inhalte (Clustering), das Zuordnen neuer Daten zu einer passenden Gruppe (Klassifizierung) oder das Erkennen von Daten, die keiner der bestehenden Gruppen zugeordnet werden können (Anomalieerkennung). In all diesen Fällen ist es notwendig, die Ähnlichkeit von Daten messen zu können. Anwendungsbereiche sind unter anderem Datensicherheit (z.B. Erkennen von Schadsoftware) und Machine-Learning-Algorithmen.

Projektinhalt und Ziele

In diesem Projekt werden Datenkompressionsmethoden (wie "Packen" oder "Zippen") so angepasst, dass sie zur Messung der Unterschiede zwischen Dateien verwendet werden können. Bei der Komprimierung entstehen neben den komprimierten Daten auch Regeln, die später beim Dekomprimieren benötigt werden. Indem man diese Regeln auf andere Dateien anwendet, können Rückschlüsse auf die Ähnlichkeit der ursprünglichen und der "fremden" Datei gezogen werden. Mithilfe von Metriken werden daraus Messgrößen für Dateiähnlichkeit abgeleitet.

Die zentralen Ziele und Aufgaben des Projekts umfassen:

• Die Identifizierung von Kompressionsalgorithmen, bei denen eine klare Trennung zwischen komprimierten Daten und Wiederherstellungsregeln möglich ist bzw. bei denen dies am effizientesten erreicht werden kann.
• Die Anwendung von Metriken auf die durch die Kompressionsvorschriften erzeugten Daten, um Ähnlichkeiten messen zu können. Zudem soll erforscht werden, welche dieser Metriken am besten mit etablierten Klassifizierungs- und Clustering-Algorithmen harmonieren.
• Die Entwicklung eines funktionierenden Prototyps, der auf den Erkenntnissen des Projekts basiert und sich diese zu Nutze macht.

Methodik

Das Projekt ist in mehrere Phasen unterteilt:

1. Zunächst wird der aktuelle Forschungsstand zum geplanten Vorhaben erhoben.
2. Kompressionsalgorithmen werden identifiziert, bei denen eine Trennung zwischen Daten und Wiederherstellungsregeln möglich ist (z.B. Huffman-, Tunstall- oder arithmetische Kodierung). Daraus werden geeignete Algorithmen für die Messung von Ähnlichkeiten abgeleitet. Metriken (Umrechnungsformeln) werden verwendet, um aus den beim Komprimieren anfallenden Rohdaten nützliche Ähnlichkeitsmaße zu erzeugen. Verschiedene Metriken (z.B. Jensen-Shannon-Divergenz, Hellingerabstand) werden auf ihre Eignung hin untersucht.
3. Um bestmögliche Ergebnisse zu erzielen, werden die entwickelten Algorithmen und Metriken getestet, sowie bereits bestehende Algorithmen modifiziert oder kombiniert.
4. Es wird untersucht, wie gut verschiedene Klassifizierungs- und Clustering-Algorithmen mit den verwendeten Metriken zusammenarbeiten.
5. Die gewonnenen Erkenntnisse werden in ein Computerprogramm integriert und damit ein praxistaugliches Werkzeug für Klassifizierungsaufgaben zur Verfügung gestellt.

Ergebnis

Die korrekte Identifikation, Zuordnung und Kategorisierung von Daten und Dateien sind grundlegende Aufgaben in der Informatik. Ähnlichkeiten zwischen den Daten zu identifizieren ist jedoch eine wesentliche Voraussetzung für solche Aufgaben. Dafür geeignete Messkriterien zu finden, ist oft schwierig. Das vorliegende Projekt geht hier neue Wege und zieht Methoden der Datenkompression für die Messung von Ähnlichkeit heran. Die gewonnenen Erkenntnisse werden über wissenschaftliche Publikationen zugänglich gemacht und in einen Software-Prototyp zur Klassifizierung von Daten integriert.