# Cluster location data with kmeans++

I clustered data according to latitude and longitude.Use the kmeans++ for increasing the accuracy of kmeans. But still result does not change much. Here is my db index graph for kmeans++

For kmeans

I could not decide which should be the optimal number of clusters. I also plot the sum of squares of clusters. For kmeans++

for kmeans

What should I do? Give me suggestion.

Here is the value of boot and noise using clusterboot

• 4 or 5 cluster solution, according to DB, seems worth checking for interpretability, though it is true that cluster structure is weak in your case. – ttnphns Aug 23 '17 at 21:03

k-means++ is not meant to improve the accuracy.

What k-means++ is meant to improve is the starting conditions, making k-means to be more likely to converge to a reasonably good local optimum, and faster than with random initialization; largely by ensuring that the cluster centers are not too close to each other initially.

Still, k-means++ means to preserve randomness, and you are expected to try multiple runs and keep the best result. In which case you cannot expect k-means++ to produce better results than k-means. You can only expect to get them faster (in computation), and with fewer tries.

KMeans++ is just an initialization method and it is not necessary it will give you best answers but it will improve take less iteration to converge because KMeans++ take care that initial centroid is distributed all over the data.

There are many methods available to find a optimal number of clusters but most of them require distance matrix which will take much time to compute. Simplest method that I can suggest is elbow method https://bl.ocks.org/rpgove/0060ff3b656618e9136b

I see k-means++ more of a way to initialize your clustering. Meaning how to design your initial cluster centers. There are a number of indices that can give you a better idea of how to decide on an "optimal k" than just the within groups sum of squares. For example the calinski-harabasz index is easy to understand and many times yields good results:

http://artax.karlin.mff.cuni.cz/r-help/library/fpc/html/calinhara.html

You ideally simply find the value that would maximize the index in an interval of ks. Although this is not always possible and you would look for a certain elbowish behavior, where the index stabilizes. This same R package (fpc) has many other statistics to get an idea of an optimal k, this paper gives you good info on how the indices are built and how they perform:

http://www.siam.org/proceedings/datamining/2009/dm09_067_vendraminl.pdf

The fpc package has many other goodies like methods for measuring cluster stability.

I think I misunderstood your question. I now think that by DB you mean the Davies-Bouldin index. So you are using an appropriate statistic to attack this. I would still try other indices, especially one that is silhouette based. If that still doesn't show anything usable, you could check out what number reveals more stable clusters (I already mentioned something about this). For example (this is only a sample code, tested it briefly):

clini <- 4   # initial k
clfin <- 7   # final k

### Stability of clusters on an interval of k

boot <- matrix(0,clfin-clini+1,clfin)
noise <- matrix(0,clfin-clini+1,clfin)

for (i in 1:(clfin-clini+1)){

auxboot <- matrix(0,1,clini-1+i)
auxnoise <- matrix(0,1,clini-1+i)

finalboot <- matrix(0,1,clini-1+i)
finalnoise <- matrix(0,1,clini-1+i)

for (j in 1:40){
stability <- clusterboot(YourData,B=80,bootmethod=c("boot","noise"),
clustermethod=kmeansCBI,
krange=(clini-1+i),count=FALSE)

auxboot <- stability$bootmean auxnoise <- stability$noisemean

if ( min(auxboot)>min(finalboot)){

finalboot <- auxboot
finalnoise <- auxnoise

}
}

for (k in 1:(clini-1+i)){
boot[i,k] <- finalboot[k]
noise[i,k] <- finalnoise[k]
}
}

### Results
boot
noise

If that still doesnt work for you, you could check which clustering yields best separability measures (k-means is ALMOST a mixture of gaussians), so you could use something like jeffries-matusita distance between your resulting clusters. This describes the idea behind these types of indices.

http://arxiv.org/ftp/arxiv/papers/0812/0812.1107.pdf

Here is an already written script to calculate separability indices:

https://stat.ethz.ch/pipermail/r-help/2010-May/237742.html

Although something that can be cumbersome is that the indices work for 1 clustering variable at a time.

• I will try your approach. But from your perspective can you find any optimal number from davies bouldin graph.Because I could not find any big spike(drop in value) in the graph until the end. – Diptopol Dam May 10 '13 at 14:10
• No, and I also don't see a stabilizing behavior. Are you sure you must cluster ONLY using longitude and latitude? Have you considered introducing another variable? – JEquihua May 10 '13 at 16:00
• I am trying your approach. It is taking long time.The concept of clusterboot is new to me. Can you please explain why you are using j loop 1:40? – Diptopol Dam May 11 '13 at 13:26
• Actually I was trying to cluster data according to locations .I have 64 distinct location.But data are many.I could not understand why I can't find any acceptable spike in the graph.Is it happening for lat and lon. – Diptopol Dam May 11 '13 at 13:35
• 1:40 says that for each k in 4:7 it will do 40 clusterings with different initial clusters. It will keep the best one for each k to compare them later. Here "best one" means that it is more "repetible". Repetible roughly means that If you take a random sample of your observations and you cluster on that sample you will get the same clusters you got using the complete sample minus the observations you left out. This is, you find THE SAME clusters. This would express a true pattern in your data. I didn't understand your last comment, could you explain it please? – JEquihua May 11 '13 at 16:03