8
$\begingroup$

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) :

Plot of all observations

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 :

Silhoette Criterion Plot Davies-Bouldin Criterion Plot

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.

Calinski-Harabasz Criterion Plot Log_SS Criterion Plot

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 :

Ball-Hall Criterion Plot Ratkowsky-Lance Criterion Plot

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 clusters22 cluster solution


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.

$\endgroup$
  • $\begingroup$ Can you visualize the clustering result at 22 clusters, please? $\endgroup$ – Anony-Mousse Jul 24 '13 at 16:52
  • $\begingroup$ What method did you use for the hierarchical clustering? That can substantially affect the results you get? $\endgroup$ – Hong Ooi Jul 24 '13 at 16:56
  • $\begingroup$ Helo Hong, I have used the "diana" method with the euclidian distance which should be a reasonable distance for coordinates. Also the plotted 22 cluster solution looks quite reasonable to me. $\endgroup$ – Karol Przybylak Jul 25 '13 at 14:16
  • $\begingroup$ Thanks for your answer and your advise Anony-Mousse. See my edit. $\endgroup$ – Karol Przybylak Jul 26 '13 at 13:31
  • $\begingroup$ Well, you could update your question. compare the result to say, agnes with 15 clusters and agnes with 30 clusters. While the clusers are convex, I'm not convinced this is all you need to have "nice" clusters. When is a clustering result good? There are million of convex results possible. $\endgroup$ – Anony-Mousse Jul 26 '13 at 13:36
6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.