1.2.3. Cluster and Expand

One of the most commonly used types of data in LBS are points of interest. The user should be able to obtain points of interest that are relevant to them within the map view. The problem here is that it is difficult to know how many POIs will be found and where they will positioned. This can lead to a very cluttered map that is difficult to interact with. You will have thought about this problem previously in the maps on small displays interaction of the LBS Techniques lesson. Here, the solution to this problem will be to represent clusters of points of interest with a single symbol. Interacting with this symbol will cause it to expand and show the POIs that it represents. Hence there are two processes, clustering and expanding.

Clustering

There are many ways to cluster data sets of points. Here we describe the k-means technique. The idea is to position k points as the centers (means) of k clusters identified amoungst the set of points. k essentially defines the level of detail that is desired. The radical law can again be used to identify a suitable value. Here, we will fix a maximum value of k which is varied according to a minimum number of points required to form a cluster. The clustering algorithm works by performing two main steps over and over again until it has found a solution usually around four or five iterations are required to achieve this. The steps are:

1. Allocate - initially the centers of the clusters are defined randomly within the map space. For each POI the closest center is then identified and the POI is allocated to this.
2. Locate - for each center the mean of the points allocated to it is computed, e.g. sum of x coordinates/number of points, sum of y coordinates/number of points. The center is then moved to this position.

In the implementation here, after the solution has been found the number of points allocated to each centroid is counted. If there are fewer than a set amount (e.g. two) then the points are reallocated to their next closest center, but the center is not moved. This prevents the position of the center from being over influenced by the outlying points. You can experiment with the animation to see how the the algorithm works.

Expand

There are several ways to expand the clusters in response to the user's interaction. The technique here is to open up the clusters like a flower. The main idea in any approach is to present the POIs allocated to a center in such a way that the user can query them directly with their stylus. You can explore the basic principles of the cluster and expand approach using the animation below. Moving the slider bottom will show increase the number of points being shown. The "show clusters" option enters the cluster and expand mode.