Birch algorithm does not cluster as expected

Question

I'm using Birch algorithm from scipy-learn Python package for clustering a set of points in one small city in sets of 10.

I use following code:

no = len(list_of_points)/10
brc = Birch(branching_factor=50, n_clusters=no, threshold=0.05,compute_labels=True)

In my idea, I would always end up with sets of 10 points. In my case now, I have 650 points to cluster, and n_clusters is 65.

But, my problem is that with too low threshold I end up with 1 address a cluster, just a tiny bigger threshold - 40 addresses per cluster.

What am I doing wrong here?

Answer 1

I've done some research. I took some points in two coordinate systems non metric (WGS84) and metric (Poland 1992).

I used this code:

from scipy import loadtxt
from sklearn.cluster import Birch
import matplotlib.pyplot as plt

data84 = loadtxt("/home/damian/workspace/84.csv", delimiter=",")
data90 = loadtxt("/home/damian/workspace/90.csv", delimiter=",")

brc = Birch(threshold=0.5)

Then I fit our model with metric data:

brc.fit(data90)

And plot the results, where crosses were my points and circles were my subclusters:

c = brc.subcluster_centers_
plt.plot(data90[:,0], data90[:,1], '+')
plt.plot(c[:,0], c[:,1], 'o')
plt.show()

This is what I got:

You can see, that threshold value was too small, because it found subcluster in each point.

Definition of threshold:

The radius of the subcluster obtained by merging a new sample and the closest subcluster should be lesser than the threshold. Otherwise a new subcluster is started.

So in this case we need to increase this value.

For:

brc = Birch(threshold=5000)

it was much better:

And the WGS84 points for threshold 0.5:

brc = Birch(threshold=0.5)
brc.fit(data84)

Only one subcluster, not good. But in this case we should decrease threshold value, so for 0.05:

brc = Birch(threshold=0.05)
brc.fit(data84)

We've got nice results.

Conclusion:

CRS matters. You need to find a proper threshold value, depends to your data coordinate systems and distance between points. If you have non metric CRS, threshold should be relatively smaller than with the metric system. You have to know difference between meters and degrees, if the distance between two points is equal to 10000m, it will be less than 1 degree in WGS84. Check google to more accurate values.

Also there are more points than n_clusters value. It's ok, there are not centroids of clusters, but subclusters. If you try to predict something, or print labels, it will classify your point to one of n_clusters areas (or print points classified to 0,1,2,...,n_clusters label).

If you don't want to try different parameters, you can always take another algorithm. Very simple and common algorithm for clustering is K-means algorithm.

http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html

It should find n clusters for your data without care about thresholds etc.