Thursday, August 5, 2010

Weighted Map Feature Clustering With Attributes

Was asked if the WeightedClusterer can cluster features not just by proximity but by proximity and attribute property value. The idea is that there should be at least one cluster per unique attribute property value. Let me explain further:

The above snapshot is a clustering of cities based on proximity and country - note that despite the proximity of Belgium and The Netherlands, two distinct clusters have been created one for BE and the other for NL - now for France - there is a cluster containing one feature over Paris, however due to the distance from Paris (at that scale) a cluster was created based on 3 cities in the south of France. Make sense ?
In the implementation of the AttrClusterer class that extends the ESRIClusterer class, we override the clusterGraphics function. This function is invoked indirectly by the Flex framework during the update of the display list. In this function, we overlay a virtual grid on the map. This grid acts as a spatial index. Features that are in the same cell will be initially clustered together. Next a process of searching and merging will be executed till no cluster overlaps another cluster. Let me explain this process; for each cluster, search the immediately adjacent cell for any overlapping cluster (that is why we need that spatial index grid :-). If a neighboring cluster is found, then the two cluster merge into one cluster and the location of the new cluster is based on the weight of each original cluster. the new cluster is spatially indexed and the original two clusters are removed. BTW, this process is guaranteed to converge to a steady state solution, so there is no need for a terminal condition like a counter. Now something of importance here is the index used to locate neighbors. The spatial index is implemented as a hash map, the cluster key is a combination of the cluster position relative to the center of the map and the cluster attribute - remember - that what started this whole implementation. You can see the application in action here. I’ve loaded the top 1000 cities by population from geonames. And like usual, you can find the source code here.

11 comments:

Unknown said...

So it clusters the points based on proximity, but what about if you want to cluster the points based on the population of each city?

Jhon Davis said...

@chris I think it should be similar when it is based on population.

Magento Themes

tania said...

@ chris, writer can clear this, who know better then us.

- Tanya
Web Design Firm

thunderhead said...

Sorry for the delay - u can cluster position and any other or combination of properties.

Magento Templates said...

Wow a great post for sure, really enjoyed as to what ever yo wrote.... Well done keep up the good work....

Magento Themes

Brendan said...

Hey Funky Cold Medina...what about a version for web mercator...could you point me in the right direction for where to modify the code. I am currently getting some continental size clusters.

I hope all is well with you!

Brendan said...

Sorry...I was being dumb...it works great in web merc...

rock on...

thunderhead said...

Glad it worked :-)

Unknown said...

I would like to extend this to not only use an image instead of a drawn graphic, but also to allow for flaring. Instead of AttrClusterSymbol extending Symbol, would it extend FlareSymbol? If so, how do I allow it to draw an image and not a graphic?

Unknown said...

Are the clusters in the map you displayed distrubuted according to the population or what.... ?

Commercial Buildings for Sale

Brendan said...

For anybody who gets an error around lines 72 - 76 in AttrClusterer.as, the property names for ESRIClusterer have changed in the new 2.5 Flex API swc.

You simply need to change to the following:

overallMinCount = Math.min(overallMinCount, cluster.graphics.length);
overallMaxCount = Math.max(overallMaxCount, cluster.graphics.length);
overallMinWeight = Math.min(overallMinCount, cluster.weight);
overallMaxWeight = Math.max(overallMaxCount, cluster.weight);


..basically just dropping the m_ prefix