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.

DBScan Ablauf

Algorithmus:

  1. Berechnung der Distanzmatrix.
  2. Ermitteln eines Kernpunktes durch ausfindig machen aller Punkte die in einem bestimmten Bereich eines ausgewählten Punktes liegen. Ist die Anzahl der ermittelten Punkte kleiner als ein vorher gesetzter Mindestwert, dann ist der ausgewählte Punkt ein Rauschpunkt und Schritt 2 wird mit einem neuen Punkt wiederholt. Wenn die Mindestanzahl gegeben ist, ist ein Kernpunkt gefunden.
  3. Erweitern der Nachbarn des Kernpunktes mit allen Punkten, welche wiederum in dem Bereich der einzelnen Nachbarpunkte liegen.
  4. Hinzufügen ALLER Nachbarn und des Kernpunktes zu einem Cluster.
  5. wiederholen von Schritt 2, falls Punkte existieren, welche noch keinem Cluster zugeordnet sind.

2. Berechnung der Distanzmatrix

Wie der Name schon verrät soll diese Matrix alle Distanzen zwischen allen Punkten enthalten. Dafür wird aus einer Menge D das Kreuzprodukt D \times D von Punkten p, wobei p \in D, gebildet und zu jedem Paar die Distanz d(p_i,p_j), (1 \leq i,j \leq \left| D \right|) berechnet. Als Distanzfunktion sei hier die Euklidische Distanz anzunehmen.

Für die Euklidische Distanz zweier Punkte p_i und p_j, welche in einem n-dimensionalen Raum liegen, gilt allgemein:

d(p_i,p_j) = \sqrt{\sum \limits _{k =1}^n ({p_i}_k - {p_j}_k)^2}

Punktpaare entlang der Diagonalen müssen dabei nicht berücksichtigt werden (i \ne j) da ihre Entfernung immer 0 betragen. Die Entfernung zwischen einem symmetrischen Paar (p_i,p_j) und (p_j,p_i) ist die gleiche. Mit diesem Wissen ist klar, dass es sich hier um eine symmetrische Matrix handelt und es ausreicht nur die obere (i > j) oder untere (i < j) Hälfte zu berechnen. In Zeile 16/17, im unteren Code, wird nur die berechnete Distanz in das gegenüberliegende Paar kopiert, um somit die vollständige Matrix zu kalkulieren. Alle Punkte, welche berücksichtigt werden, sind in der eigentlichen Implementation als globale Variable ptrArray gespeichert.

/**
 * Computes the distance matrix for a collection of points. Because it is a
 * symmetric matrix, we only need to compute the upper half of the matrix
 * and copies the value to the symmetric position.
 * @return computed distance matrix which contains all distances between points
 */
private double[][] computeDistanceMatrix() {
  int numberOfPoints = ptrArray.length;
  double[][] distMatrix = new double[numberOfPoints][numberOfPoints];

  for(int row = 0; row < numberOfPoints; row++) {
    for(int col = row; col < numberOfPoints; col++) {
      if(row == col) {
        distMatrix[row][col] = 0;
      } else {
        distMatrix[row][col] = distMatrix[col][row]
                 = distFunction.calculate(ptrArray[row], ptrArray[col]);
      }
    }
  }

  return distMatrix;
}

3. Ermitteln aller Nachbarn eines Punktes

In diesem Schritt sollen alle Nachbarpunkte ermittelt werden, welche sich in einem bestimmten Bereich \epsilon befinden. Hier spielt die vorher berechnete Distanzmatrix eine große Rolle. Der übergebene Parameter stellt die Spaltennummer des derzeitigen Punktes, welcher untersucht werden soll, in der Distanzmatrix dar. Nun wird jede Zeile dieser Spalte untersucht, ob der sich enthaltene Wert unter dem \epsilon liegt. Wenn das der Fall ist, wird der in der Zeile positionierte Punkt als Nachbar identifiziert.

/**
 * Finds all neighbors from a given point which are in a specific area.
 *
 * @param point_id point position in the computed distance matrix
 * @param eps defines the area in which a neighbor point should be
 *
 * @return list of neighbor point ids, which are related to a given point
 */
private List<Integer> findNeighbors(final int point_id) {
  List<Integer> result = new ArrayList<Integer>();

  for(int ptrIndex = 0; ptrIndex < distanceMatrix.length; ptrIndex++) {
    if((point_id != ptrIndex) && (distanceMatrix[ptrIndex][point_id] < eps)) {
      result.add(ptrIndex);
    }
  }

  return result;
}

4. Bilden einer Nachbarschaftskette zum Konstruieren des eigentlichen Clusters

Dies ist der letzte Schritt. Als erstes wird der Kernpunkt zu einem neuen Cluster hinzugefügt. Um nun eine Kette zu bilden, müssen alle Nachbarn dieses Punktes noch einmal auf Punkte in der “direkten Nachbarschaft” überprüft werden (Zeile 24). Ist die Anzahl der ermittelten Nachbarpunkte eines der Nachbarn nun über oder gleich einer bestimmten Mindestanzahl an Punkten, wird die Liste der Nachbarn des Kernpunktes mit der Liste der ermittelten Nachbarpunkte vereint (Zeile 27). Damit erweitert sich natürlich auch die untersuchte Liste, die mit der for-Schleife durchgegangen wird (Zeile 17). Der gerade ausgewählte Nachbar wird dann, falls er noch keinem Cluster zugeordnet wurde, zu dem neu erstellten hinzugefügt.

/**
 * Creates the cluster with all points which is the current visited point and all
 * his neighbors and neighbors of the neighbors. Is one of the point already in
 * any cluster, this point will be ignored.
 *
 * @param p current visited point
 * @param n neighbors of {@code p}
 *
 * @return a cluster containing all points which are "near" to each other
 */
private Cluster expandCluster(final Point p, final List<Integer> n) {
  Cluster c = new Cluster();

  c.addPoint(p);
  pointsMappedToCluster.add(p);

  for(int index = 0; index < n.size(); index++) {     
    int np_id = n.get(index);     
    Point np = ptrArray[np_id];     
    
    if(!visitedPoints.contains(np)) {       
      visitedPoints.add(np);       
      
      List<Integer> neighbors = findNeighbors(np_id);       

      if(neighbors.size() >= minPtr) {
        merge(n, neighbors);
      }
    }

    if(!pointsMappedToCluster.contains(np)) {
      c.addPoint(np);
    }
  }

  return c;
}

5. Der eigentliche Start

Alle Schritte zuvor waren nur Teil des weiter unten dargestellten Codes. Dieser stellt die eigentlich Ausführung des DBScan Algorithmus dar, vorausgesetzt die Distanzmatrix wurde schon ermittelt. In dem eigentlichen ersten Schritt, werden alle Punkte aus einer Liste von Ausgangspunkten untersucht. Jeder von ihnen wird nur einmal als Kernpunkt und damit als besucht eingestuft. Von diesem Punkt aus, werden alle Nachbarn, wie in 3. erklärt, ermittelt. Falls die Anzahl der Nachbarn nun unter einer Mindestanzahl liegen, wird der gerade besuchte Punkt als Rauschpunkt identifiziert. Ist das nicht der Fall, wird der Cluster nach 4. gebildet. Am Ende sollten alle Punkte entweder einem Cluster oder einer Liste von Rauschpunkten zugeordnet sein.

/**
 * Computes the DBScan algorithm.
 *
 * @return list of computed cluster
 */
private List<Cluster> computeDbscan() {
  int numberOfPoints = ptrArray.length;

  pointsMappedToCluster = new ArrayList<Point>(numberOfPoints);
  visitedPoints = new ArrayList<Point>(numberOfPoints);
  noisePoints = new ArrayList<Point>();

  List<Cluster> resultCluster = new ArrayList<Cluster>();

  for(int index = 0; index < numberOfPoints; index++) {
    Point current = ptrArray[index];

    if(!visitedPoints.contains(current)) {
      visitedPoints.add(current);

      List<Integer> neighbors = findNeighbors(index);

      if(neighbors.size() < minPtr) {
        noisePoints.add(current);
      } else {
        Cluster c = expandCluster(current, neighbors);

        resultCluster.add(c);
      }
    }
  }

  return resultCluster;
}

Kommentar schreiben

4 Kommentare.

  1. Christian

    Hi Philipp,

    also in meinem nächsten Post ist geplant mal genauer so etwas an einem Beispiel auszuführen. Werde mich da auf das Clustern von Dokumenten beziehen. Ob ich aber einen Vergleich mit anderen Clustering-Verfahren anstrebe weiß ich noch nicht. Da ich bzw. bei DBScan keine genaue Anzahl an Klassen angebe, aber bei k-Means. Ich denke da dürfte es schwierig sein gute Ergebnisse heraus zu filtern um somit einen Vergleich anzustreben. Aber wenn es mal dein Wunsch ist, könnt ich es trotzdem mal versuchen?!

    Grüße
    Christian

  2. Philipp

    Hi Christian,

    Coole Post! Hast du ein Beispiel auf echten Daten? Mich würde interessieren, wie man die Parameter für DBSCAN schätzt und welche Cluster im vergleich zu anderen Verfahren gefunden werden (k-Means, EM, …). Ich habe vor einiger Zeit schon einmal gesucht, aber leider wird der Algorithmus meist nur auf Spielbeispielen gezeigt.

    Grüße,
    Philipp.

  3. Christian

    Hey Hans,

    ich musste wirklich erst einmal überlegen was du damit meinst, dass ich keine Generics nutze, denn ich nutze sie. Wenn du mal in die eigentlich Implementierung schaust, sind sie da. Leider hab ich hier wohl den Fehler gemacht, das größer und kleiner nicht in HTML schreibweise zu machen, so dass er mir alles zwischen den beiden Zeilen einfach nicht mit anzeigt ^^ Werde es natürlich so schnell wie möglich korrigieren. Danke für deinen Hinweis ;)

  4. Hans

    Warum verdammt nochmal sind deine Datenstrukturen eigentlich nicht generisch? Die Verwendung von Rawtypes in Java ist _die_ Ursache für schwierig zu findende Bugs schlechthin.

Kommentar schreiben


*