# Birch algorithm does not cluster as expected

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?

• Maybe it's CRS. Problem? If you tried with degrees (like WGS 84), try metric. There are a pretty big difference in coordinates and both can require different threshold value. Also you can try with different python library, I strongly recommend to use scikit-learn. Apr 18, 2016 at 12:21
• ..erm, I'm clustering on basis of GPS coordinates as received from Google API, I presume they are standard-formatted. No? Apr 18, 2016 at 20:47
• Maybe paste here these coordinates, I'll try to figure this out. Apr 19, 2016 at 6:56
• dmh126 could be right: Goolge API is working with WGS84, this is a (World) Geodetic System, not a metric Apr 19, 2016 at 11:31

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

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.