Adverse results of clustering criteria

Question

I have carried out a clustering of coordinate points (longitude, latitude) and found surprising, adverse results from clustering criteria for the optimal number of clusters. The criteria are taken from the clusterCrit() package. The points which I am trying to cluster on a plot (the geographic characteristics of the data set is clearly visible) :

The full procedure was the following :

1. Carried out hierarchical clustering on 10k points and saved medoids for 2 : 150 clusters.
2. Took the medoids from (1) as seeds for kmeans clustering of 163k observations.
3. Checked 6 different clustering criteria for the optimal number of clusters.

Only 2 clustering criteria gave results that make sense for me – the Silhouette and Davies-Bouldin criteria. For both of them one should look for the maximum on the plot. It seems both give the answer “22 Clusters is a good number”. For the graphs below: on the x axis is the number of clusters and on the y axis the value of the criterion, sorry for the wrong descriptions on the image. Silhouette and Davies-Bouldin respectively :

Now let’s look at Calinski-Harabasz and Log_SS values. The maximum is to be found on the plot. The graph indicates that the higher the value the better the clustering. Such a steady growth is quite surprising, I think 150 clusters is already a quite high number. Below the plots for Calinski-Harabasz and Log_SS values respectively.

Now for the most surprising part the last two criteria. For the Ball-Hall the biggest difference between two clusterings is desired and for Ratkowsky-Lance the maximum. Ball-Hall and Ratkowsky-Lance plots respectively :

The last two criteria give completely adverse answers (the smaller the number of clusters the better) than the 3rd and 4th criteria. How is that possible? For me it seems like only the first two criteria were able to make any sense of the clustering. A Silhouette width of around 0.6 is not that bad. Should I just skip the indicators that give strange answers and believe in those that give reasonable answers?

Edit: Plot for 22 clusters

---

Edit

You can see that the data is quite nicely clustered in 22 groups so criteria indicating that you should choose 2 clusters seem to have weaknesses, the heuristic isn't working properly. It is ok when I can plot the data or when the data can be packed in less than 4 principal components and then plotted. But if not? How should I choose the number of clusters other than by using a criterion? I have seen tests which indicated Calinski and Ratkowsky as very good criteria and still they give adverse results for an seemingly easy data set. So maybe the question shouldn't be "why are the results differing" but "how much can we trust those criteria?".

Why is an euclidian metric not good? I am not really interested in the actual, exact distance between them. I understand the true distance is spheric but for all points A,B,C,D if Spheric(A,B) > Spheric(C,D) than also Euclidian(A,B) > Euclidian(C,D) which should be sufficient for for a clustering metric.

Why I want to cluster those points? I want to build a predictive model and there is a lot of information contained in the location of each observation. For each observation I also have cities and regions. But there are too many different cities and I don't want to make for example 5000 factor variables; therefore I thought about clustering them by coordinates. It worked pretty well as the densities in different regions are different and the algorithm found it, 22 factor variables would be all right. I could also judge the goodness of the clustering by the results of the predictive model but I am not sure if this would be wise computationally. Thanks for the new algorithms, I will definitely try them if they work fast on huge data sets.

Answer 1

The question you should ask yourself is this: what do you want to achieve.

All these criteria are nothing but heuristics. You judge the result of one mathematical optimization technique by yet another mathematical function. This does not actually measure if the result is good, but just whether the data fits to certain assumptions.

Now since you have a global data set in latitude and longitude euclidean distance actually is already not a good choice. However, some of these criteria and algorithms (k-means…) need this inappropriate distance function.

Some things you should try:

• Better algorithms. Try DBSCAN and OPTICS, which both don't require you to specify the number of clusters! They have other parameters, but e.g. distance and minimum number of points should be much easier to set for this data set.
• Visualization. Instead of looking at statistics of some mathematical measure, choose the best result by visual inspection! So first of all, visualize the clusters to see if the result makes any sense at all.
• Consider what you want to find. A mathematical criterion will be happy if you separate the continents. But you don't need an algorithm to do this, the continents are quite well-known already! So what do you want to discover?
• Remove outliers. Both k-means and hierarchical clustering don't like outliers that much, and you may need to increase the number of clusters to find by the number of outliers in the data (DBSCAN and OPTICS mentioned above are much more robust towards outliers).
• More appropriate distance function. The earth is approximately spherical, use the great circle distance instead of Euclidean distance.
• Try converting the data into a 3D ECEF coordinate system, if you need to use Euclidean distance. This will yield cluster centers that are below the earth surface, but it will allow clustering Alaska, and the euclidean distance is at least a lower bound of the true surface distance.

Have a look at e.g. this related question / answer on stackoverflow.

Answer 2

Longitude and latitude are angles which define points on a sphere so you should probably be looking at the Great Circle Distance or other geodesic distances between points rather than the Euclidean distance.

Also as has been mentioned, certain explicitly model-based clustering algorithms like mixture models and implicitly model-based ones like K-means, make assumptions about the shape and size of the clusters. In this situation are your expecting your data to fit an underlying model? If not then density-based methods which don't make assumptions about the shape/size of the clusters might be more appropriate.