More on DBSCAN

To recap, I'm attempting to implement the clustering alogorithm, DBSCAN, as a desktop VB.NET application, reading the accident data from a GML file. I've managed to do this using a modified version of the method described by Tan et al (Algoritm 8.4, p528).

The implementation requires the user to supply a value for Eps. The process is as follows:

1. read all points into an arraylist of type point (where point is a user defined class)
2. populate a distance array – containing the distance between each point and every other point
3. create array for k-dist where k = 4– i.e. for each point what is the distance to the 4th nearest neighbour?
4. flag core points – i.e. where 4-dist is <= Eps
5. flag border points – i.e. where the point is within Eps of a core point
6. by default the remaining points are noise
7. populate an array of linked core points – i.e. core points within Eps of each other
8. where core points are linked put them in the same cluster
9. add border points to same cluster as their nearest core point

(The code then generates INSERT statements that can be run against a postgreSQL database for plotting in QGIS).

The process was run using data from the Heatons North ward using values for Eps of 10m and 20m. The following images focus on a particular section of road:

With a Eps of 10m:

With an Eps of 20m:

The core points are black, border points are yellow and noise points are crosses. The number indicates the cluster ID (the 10m Eps returns 14 clusters, the 20m Eps returns 19 clusters)

With the 10m Eps there is more noise and the cluster is more focussed - at 2 junctions instead of 3. The choice of Eps is critical then.

A large view of the 10m results can be seen here.

Summary
My implementation of DBSCAN will not be the most efficient but that doesn't matter. Its the implementation of WPS that I'm interested in.

The next stage is to implement the algorithm as a WPS. The first step will be to look at the input parameters of the WPS i.e. how can I make the accident data in WFS form available to a web service?