Ein skalierbares agglomeratives Clusterverfahren basierend auf erste Nachbarschaftsbeziehungen

Abstract

Eine der revolutionären Veränderungen des 20. und 21. Jahrhunderts der Menschheit ist die Computerisierung und Digitalisierung der Welt. Tagtäglich werden große Menge von Daten erzeugt. Es ist unmöglich für uns Menschen, ohne anspruchsvolle Verfahren und Algorithmen, aus diesen enorm großen Datenmengen versteckte Strukturen (Wissen) herauszufiltern. Datamining, Machine Learning und Pattern Recognition sind ähnliche Disziplinen, mit denen man versuchen will, diese Herausforderung zu bewältigen. Da das Volumen der Daten von Sekunde zu Sekunde größer wird, brauchen wir wie nie zuvor Algorithmen, die skalierbar sind. In dieser Arbeit konzentrieren wir uns auf zwei wichtige, interdisziplinäre Lernverfahren, nämlich Supervised (Klassifikation) und Unsupervised (Clustering) Learning. Unser Ziel in dieser Arbeit ist die schrittweise Entwicklung von skalierbaren Algorithmen. Dazu erklären wir erst die Grundidee der Algorithmen und beweisen diese anschließend formal. Im nächsten Schritt beweisen wir die Korrektheit der Algorithmen. Dann analysieren wir entweder ihre Laufzeit, oder untersuchen ihr Verhalten empirisch. Wir benutzen die erste Nachbarschaftsbeziehung zwischen Punkten als Grundoperation, mit der wir weitere Algorithmen für beide Lernverfahren, nämlich Klassifikation und Clustering, schreiben.