8

I'm in search of a incremental spatial clustering algorithm. Here is my use case:

  • users create entries with an initial position
  • users may change the positions of existing entries

I now want to implement a decoupled service that provides clustering information of these data. The service will be notified each time a new entry has been added or an existing entry has been moved. What is a good clustering algorithm therefore? Ideally, it should scale well up to high amounts of data and if there's a trade-off between cluster quality and runtime complexity, I'm okay with degrading results, and eventually consistent results (stale results are okay for some time).

To summarize my requirements:

  • spatial clustering based on positions
  • incremental modifications on changes
  • add new positions
  • change existing positions
  • good runtime performance

Thanks in advance!

7
  • 1
    What will the clusters be used for? What do they mean? (The answers to these provide the most basic ways to select a clustering algorithm.)
    – whuber
    Jan 23, 2011 at 17:44
  • also are events rare or common? related to a population at risk? or will simply highlighting areas were people live be OK?
    – Ian Turton
    Jan 23, 2011 at 19:52
  • @whuber: The clusters will be used in order to make the items more explorable on a map (thus there might be different clusters on different zooming levels); They mean a concentration of available items in the given areas.
    – b_erb
    Jan 23, 2011 at 20:30
  • @iant: The creation of new items will happen very often, the change of the position of existing items will rarely happen. There are no detailed patterns to be expected how events occur. However, the concurrent creation of multiple items at the same time is less likely.
    – b_erb
    Jan 23, 2011 at 20:33
  • @PartlyCloudy I get the idea, but I still don't understand how clustering will help. OK, suppose you internally identify certain clusters of points. How will that affect the user interface (or, more generally, the "explorability" of the data)? Depending on how you respond, there may be solutions that are (a) extremely fast and easy to implement but which (b) are not generally considered "clustering" algorithms.
    – whuber
    Jan 23, 2011 at 21:30

2 Answers 2

5

The purpose of this clustering is to simplify the display of point symbols: when many are close together on the map, they will be replaced by a single symbol to indicate a group.

The requirements point to a need for a simple, adaptive solution: the point symbols can be updated and as the user zooms in, different symbols will appear at different places on the map (or screen) extent.

An excellent candidate clearly is a region quadtree.

There is a simpler method that will act like a region quadtree. It requires less coding, no advance creation of a data structure, but you pay a (small) price by needing to perform some on-the-fly calculations during zooming and panning. Just grid the map. Specifically, suppose there are n point symbols to be drawn within the map's current extent which has a length of dx and a height of dy. Relative to the map's origin the symbols need to be drawn at coordinates (x[i], y[i]), i = 1, 2, ..., n. Selecting a grid cellsize of c partitions the map into a grid of cells. The cell in which the location ( x, y ) belongs is in row j (y) = Floor[y / c] and column j (x) (counting from 0, with rows going from bottom to top and columns from left to right). You can consider any cell receiving two or more points to be a "cluster". The cluster symbol can be drawn at the cell's center, which has coordinates.(j + c/2, k + c/2).

This leads to the following solution, presented in pseudocode:

m = Floor(dy/c)+1
n = Floor(dx/c)+1
Dimension a[m,n] = 0
For each (x[i], y[i]) to be displayed:
    Increment( a[ j(y[i]), j(x[i]) ] )
End for
For each (x[i], y[i]) to be displayed:
    row = j(y[i])
    col = j(x[i])
    If  a[row, col] > 1:
        Draw a symbol for a cluster of k points at (c*(col+0.5), c*(row+0.5))
        a[row, col] = 0
    Else
        Draw a point symbol at (x[i], y[i])
    End if
End for

Clearly the algorithm's computing burden is O(# of points) in time and O(dx*dy/c^2) in storage. The trade-offs involved in selecting the cellsize c are:

  1. c should be as large as possible: Storage is inversely proportional to c^2: small values of c mean large amounts of RAM. (Storage can be reduced to O(# of points) by using sparse arrays or dictionaries.)

  2. c should be as large as possible: Two symbols (points or clusters) will never be any closer than c/2.

  3. c should be as small as possible: every cluster symbol represents locations no further than c/sqrt(2) away from it.

  4. c should be as small as possible: Large values of c tend to create many clusters and allow few individual points to appear.

Let's do a quick analysis of (4). As a point of departure, suppose the locations to be mapped occur uniformly at random and independently of one another. The number of cells is N (c) = (Floor(dx / c)+1) * (Floor(dy / c)+1), which--at least for larger values of c--is directly proportional to c^2. The distribution of cell counts will approximately follow a Poisson law with intensity lambda = n / N( c ) = n * c^2 / ( dx * dy ). The expected number of clusters equals

e (c) = n (1 - exp(-lambda)(1 + lambda)).

This becomes smaller as lambda shrinks to 0; that is, as the cellsize c gets smaller and smaller. The point of this analysis is that the preceding formula lets you anticipate how many clusters there might be, so you can select an initial value of c for which e (c) is below an acceptable value (while still being large enough to limit the RAM requirements). There is no closed-form solution, but a few Newton-Raphson steps will converge to one rapidly.

This approach is so dynamic--it's fast enough that the gridding and consequent clustering can be computed with each zoom and pan, and requires no precomputed data structures--that the desired "incremental modifications" as data are updated will happen automatically.

2
  • What if visually you have a group of points clustered near the 4 corners area. Wouldn't you end up with 4 clusters? Jan 24, 2011 at 17:56
  • @Kirk Actually this situation might break a large cluster into two to four clusters or individual points; it won't create artificial clusters. This can occur with a region quadtree, too. There are several solutions. One is to offset the grid origin by a random amount between 0 and -c (in both coordinates), so that such conditions do not hold permanently. Another is to create a quadtree dynamically, adapting it to the points (rather than using fixed cutpoints). Clearly this takes more coding. A good solution is to ignore the situation: is it really such a problem?
    – whuber
    Jan 24, 2011 at 19:12
1

Are you looking for something like http://dev.openlayers.org/releases/OpenLayers-2.10/examples/strategy-cluster-threshold.html? If so the code shouldn't be too hard to follow.

2
  • Do you know the name of the cluster algorithm? I can't see much only by this example.
    – b_erb
    Jan 23, 2011 at 21:01
  • Nearest neighbours algorithms should get you started. Jan 24, 2011 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.