Project jAIL: DBScan Implementierung

Seit einigen Wochen nun, habe ich das erste Clustering Verfahren zu Project jAIL hinzugefügt. In diesem Artikel möchte ich dieses ein wenig näher beleuchten und EINE Lösung anhand von verschiedenen Code Snippets aus der eigentlichen Implementierung vorstellen.

1. Allgemein

DBScan ist ein Verfahren um numerische Daten in eine unbestimmte Anzahl von Klassen (Cluster) einzuordnen. Diese Einordnung wird durch Bestimmung der Verbundheit aller Daten zu einander erreicht. Zwei Punkte, welche in einem multidimensionalen Raum repräsentiert werden, sind verbunden oder “Nachbarn”, wenn der Abstand zueinander in einem bestimmten Bereich liegt. Um den Abstand zu berechnen, werden Distanzmetriken, wie zum Beispiel die Euklidische Distanz, eingesetzt. Um Datenpunkte einem Cluster zuzuordnen, muss zuerst ein Kernpunkt ermittelt werden. Dafür werden zuerst alle Nachbarn eines ausgewählten Punktes bestimmt. Liegt die Anzahl dieser dann über einen Mindestwert, ist der Punkt ein Kernpunkt. Wenn nicht, wird er als Rauschpunkt eingeordnet und nicht mehr betrachet. Um einen Cluster zu bilden, ermittelt man nun auch alle Nachbarn der Nachbarn des Kernpunktes. Alle nun gefunden Punkte, die wiederum über der Mindestanzahl an Elementen liegen, werden zusätzlich rekursiv untersucht, um so alle Punkte die “dicht” beieinander liegen,ausgehend vom Kernpunkt, zu ermitteln und einem Cluster zuzuordnen. Die Clusterzuordnung wird nun solange ausgeführt, bis alle Punkte entweder als Rauschpunkte identifiziert wurden oder einem Cluster zugeordnet sind. (more…)


Projekt jAIL: Komposition von Problemlösungen

Seit mehr als einem Jahr arbeite ich nun freizeitmäßig an einer eigenen Java Bibliothek für verschiedenste mathematische Probleme. Diese Erweiterung, zur normalen java.lang.Math, sollte Leuten helfen, denen es reichte verschiedenste Bibliotheken für einen Aspekt in ihrem Projekt einzuarbeiten. Da ich viel mit meinem Studium beschäftigt bin, musste leider auch dieses Projekt ein bisschen in Hintergrund verschwinden. Nun da ich Ferien habe und mich die Lust wieder gepackt hat, überkam es mich nur mit allerhand neuen Ideen. Da diese den Rahmen einer normalen „Java Mathe Bibliothek“ sprengen würde, nahm ich eine kleine Umbenennung von einst MathLib zu jAIL vor. In diesem kleinen Post möchte ich dieses Projekt kurz einmal vorstellen und wie ich mir die Zukunft gut vorstellen kann.

Was ist Projekt jAIL?

Die Abkürzung jAIL steht kurz für „Java Algorithm Implementation Library“ und wenn das Wort als Ganzes betrachtet wird, kann es auch als das englische Wort für Gefängnis übersetzt werden. Beides trifft im Großen und Ganzen zu, wobei das letztere, in diesem Kontext, als ein Zusammenschluss vieler kleiner Teile in einem Paket gesehen wird. (Die Inhalte beschränken sich auf folge Themen):
Der Inhalt schließt folgende Themen ein:

  • Algorithmen aus unterschiedlichsten Gebieten der Mathematik, Informatik oder auch Wirtschaftsinformatik
  • Datenstrukturen zur Speicherung, Indexierung und besseren Handhabung von Daten
  • Laden von Daten aus verschiedensten Dateitypen geplant
  • (uvm.) (Erweiterungen nicht ausgeschlossen)

Warum solch ein Projekt, es gibt doch schon viele Lösungen zu diesen Themen?

Die große Intension für mich, ein solches Projekt zu starten, ist einfach auch selber aktiv zu werden, nicht einfach nur kopieren und nicht wissen wie etwas funktioniert. Ich möchte einfach verstehen wie man Probleme mit der Programmiersprache Java löst, um so ein besseres Verständnis 1. für Java zu bekommen und durch Tipps von Nutzern/Lesern besseren Java-Code zu schreiben und 2. Für Algorithmen und wie ich mit wenig Informationen, solche in eine Programmiersprache übersetze.

Für wen ist Projekt jAIL?

Das Projekt richtet sich an alle diejenigen, welche in den oben genannten Gebieten sich zu Hause fühlen und EINE Lösung, der vielen im Netz existierenden, zu einem Problem benötigen und in ihrem Projekt verwenden wollen. Unsere Lösungen sind nicht DIE Lösungen, aber ein Anfang.

Wer entwickelt Projekt jAIL?

Ins Leben gerufen habe ich das Projekt und den einen oder anderen, konnte ich schon eine Mitwirkung schmackhaft machen. Da jAIL aber ein Open-Source Projekt ist, ist es für jeden gedacht, der mitmachen möchte, um diese Bibliothek mit „Leben“ zu befüllen.

Sind die Lösungen in jAIL hoch optimiert?

Natürlich gibt es an ein paar Stellen Verbesserungen, darum ist dieses Projekt auch Open-Source. Jeder der eine Meinung hat, wie man etwas verbessern kann oder wo es noch Fehler geben könnte, ist gerne gehört und kann sich entweder direkt bei mir melden oder einfach bei Posts zu aktuellen Themen oder Erweiterungen in diesem Blog einen Kommentar hinterlassen. Umso mehr Leute daran arbeiten und ihre Vorschläge einreichen, umso besser sind auch die Algorithmen, also mitmachen lohnt sich.

Wie oft kommen Erweiterungen oder Verbesserungen?

Das kann sehr unterschiedlich geschehen. Da ich noch hauptberuflich Student bin und mich auch darauf konzentriere, werde ich wohl so wie ich Zeit habe neue Lösungen oder Themen hochladen. Da kann ich aber nur von mir sprechen. Es ist hauptsächlich ein Freizeitprojekt und soll auch als solches gesehen werden.

Wie kann ich teilnehmen?

Da es ein Open-Source Projekt auf Github ist, sollte das alles kein Problem sein. Natürlich werden ich und ein paar andere kontrollieren was hochgeladen wird. Am liebsten wäre mir aber, wenn sich interessierte Leute einfach bei mir melden würden und ihre möglichen Erweiterungen mit mir besprechen würden. Möchten ja nicht das mehrere Leute an einem arbeiten.

Source-Code: http://www.github.com/sichvoge/jAIL/