Manifold Community Site: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

jonno — Fri, 14 Nov 2008 18:39:38 GMT

Okay first of all - I want this with a passion :- http://ubicomp.algoritmi.uminho.pt/local/concavehull.html and have been doing a little experimentation with knn in python - still nowhere near yet though.

The same site also has documentation & VB6 Code for the following algorithms which I think are pretty neat

DBScan + SNN

http://ubicomp.algoritmi.uminho.pt/local/

I don't have the time at the moment to translate the code into something more .NET but it should be a doddle for all you old hands out there.

I am leaving my current role next Friday and am entering an "Arc/MapInfo Solution Provider zone" - whilst I am hopeful that I can introduce Manifold to all and sundry, I can't see myself doing much with Manifold unless it's in my spare time for the next 6 months or so.

So I am handing the baton over on this one.

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

ColinD — Fri, 14 Nov 2008 19:09:49 GMT

FWIW this is my hack to create a boundary around a set of points. I'm sorry but I forget who the author was of the original join points script.

I'm sure someone can improve on this.

Attachments:
CreatePointsBoundary.map

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

mdsumner — Fri, 14 Nov 2008 19:28:09 GMT

You could achieve similar results with either Shape Hull, or Distance Network and Bounded Areas.

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

jonno — Fri, 14 Nov 2008 19:35:15 GMT

Mike,

Was that to me or Colin???

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

mdsumner — Fri, 14 Nov 2008 19:37:02 GMT

Sorry, you jonno - I've not looked at Colin's post. Here's what I just finished with Distance network (attached).

EDIT: I've emailed the author to get the Mathematica code, I'm keen to explore that too.

Attachments:
DistanceNetwork.map

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

jonno — Fri, 14 Nov 2008 19:43:45 GMT

Now that's what I call neat - been wracking my Brains all Day today [and yesterday] trying to get something like this working.

Quick Question - How much trial and error is involved with getting the Dist Nw parameter just right??

DBScan looks good though

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

mdsumner — Fri, 14 Nov 2008 20:30:29 GMT

The distance you need is just long enough to straddle the smallest distance you want connected.

I just use the tracker to get a rough stab and start there. Note that with a lot of points you want to get the number as close to ideal as possible, to minimize the number of links created.

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

ColinD — Sat, 15 Nov 2008 11:43:47 GMT

I've given the Distance Network method a go on a real set of 450k points and while I can get a reasonable network for a final area, the Bounded Areas transform takes too long. I bailed out at 20% after an hour.

Quad, 64-bit XP, 8GB RAM

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

jonno — Sat, 15 Nov 2008 12:06:08 GMT

Came to that conclusion about an hour ago myself - Darn!!! - It seemed to be going in the right direction

RE: Point Cluster Analysis - DBScan(Density-Based Spatial Clustering of Applications with Noise) + SNN ( Shared Near Neighbours) + "Concave Hull"

ColinD — Sat, 15 Nov 2008 12:31:16 GMT

Well, have you tried the method I've been using (I had already used it for the 450k points). It's a bit tedious to start with but does give some control over the ambiguities as to what edge inflections you want to include/exclude.