Github: DBScan Implementierung in Objective-C

Im Zuge meiner derzeitigen Arbeitsstelle, muss ich mich ein wenig in Objective-C rein arbeiten. Da ich nicht der große Freund von “Hello World” Programmen bin, habe ich gleich am ersten Tag versucht, mir ein Problem, welches ich gut kenne, zu nehmen und in der neuen Sprache umzusetzen. Das Ergebnis habe ich auf mein Github Account geladen. Ziel ist nun, dass sich hoffentlich ein paar Objective-C Programmierer finden, welche mal ungezwungen über den Code schauen und mir vielleicht wichtige Hinweise geben. Mir ist es sehr wichtig, ob ich die richtigen Sprachkonstrukte an den richtigen Stellen genutzt habe oder was ich hätte besser machen können.

Ich hoffe es werden sich einige finden. Bitte schreibt mich dann einfach persönlich an. Danke.

Link zur Implementierung


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…)