dotpy.py

T’ was a good day, today.

Implementation of two clustering algorithms from scratch (no built ins, no nada) has been sucessfully completed using python3.

Numpy and pyplot FTW!

After the initial runs and some minor bugs fixes, it's testing time!

For this purpose, an artificial dataset has been generated. The dataset was created by the concatenation of two multivariate Gaussian distributions with different parameters using the numpy.random.multivariate_normal module.

The first subset had dimension 2 and 220 observations, with mu = 1 and COV = 0.5 , whereas the second was generated from a Gaussian with mu = -1 and COV = 0.75.

The plot of the unified N = 500 dataset, is shown below with the labels properly  color-coded for each one of the subsets:

Ok, now that we’ve seen how the accurate partitioning of our data should look like, let’s forget them for a moment and put our clustering algorithms to the test!

Remember, when checking for clustering performance, we should  check back at our true labels, in order to compare and contrast.

K-means

Now let’s see how K-means has performed, in finding the hidden structure of our unified dataset.

First up, let’s start with k = 2:

Well, not bad K-means, not bad at all! The middle zone is pretty harshly discriminated, but this is only normal if we consider how the algorithm actually works. This grouping seems to minimize the sum of the intra-cluster SSE or distortion of clusters as the metric is often called.

But that was waaay easy. We selected the exact same cluster number as if we knew what was hidden in our data. Not very realistic to jest guess at once the right k for a real dataset!

Let’s now see how the K-means algorithm performs, if a not-so-ideal k is chosen upon ininntialization.

k = 3:

Ehm, ok K-means. One subset seems to kinda good and true to the first label, but what’s up with the utmost left subset? 

Or should I say, subset-S?

Well, the thing is that K-means is a simple guy; he(?) just likes things to be nice and simple. It computes distances, arranges members in the group with the center closest to them, and that’s about it. K-means behaves fair enough;

Well,  it behaves literally pretty “fair” actually.

After being told what the chosen number of k is, K-means calculates and shuffles around in space data centers (cc: centroids), in such a manner so that in the end every cluster has taken their closest data points.

It distributes the data points equally more or less to k clusters.

This actually dictates that no one cluster can have the majority of the data points, because in such an incident the efficiency measure, which is the sum of intra-cluster standard errors (datapoints Vs centroid) would not be near to minimum but instead be maximized. This comprimises the ability of the algorithm to detect the true labels.

Let’s push K-means a little bit more now and run for k = 4:

To sum up, K-means did a pretty good job in finding the 2 clusters when the correct number of k was given as input. In all other cases, K-means appears to have a tendency of making blobs out of everything!

Probably the implementation could be optimized by tweaking the error metric (something more eloquent than the sum of intra-cluster Standard errors would probably be nicer.) In essence, K-means performs hard assignments, based on a binary “yes or no” choice, for allocating the data points in groups. 

Now let’s have a look at  the softer clustering alternative, clustering using the the Mixture model of Gaussians and see how it compares.

Remember, our artificial dataset was created by the concatenation of two different Gaussians with relatively close means (mu1 = 1, Sigma = 0.5, mu2 = -1, Sigma = 0.75).

Once more, the true labels are shown in the plot below:

Back to Mixture of Gaussians.

This is a probabilistic and way more eloquent clustering  approach, and more information can be found in Bishop’s book “Pattern Recognition and Machine Learning“.

Let’s see how MoG responds to our attempts to fool it with different k :

k = 2

With k = 2, it’s a walk in the park, but K-means did pretty good here too.

Let’s move to more difficult cases:

k = 3

Yes! Actually a pretty good job!

And in the sake of avoiding cherry picking the best runs (you know it happens!), here is one not so picture-perfect but still quite decent one, with same number of k.

Still roughly two groups, ellipsoids and not blobs like in K-means and some in the grey zone allocated to a separate Gaussian.

k = 4

Now, how about that?!

Yeap, seems pretty legit to me. Still managed to seperate the data points very close to the true labels.

k = 5:

Hmm, ok now things seem to get a bit more sketchy, but still, the first group has been more or less correctly labeled.

And all the above are just when making spherical clusters out of the data points seems quite rational.

Let’s see how K-means “performs“ when exposed to circlular data:

The following artificial dataset has been created using scikit-learn’s make circles module:

# NOTE: # The artificial dataset is already centered to 0, upon generation from sklearn.datasets import make_circles X, y = make_circles(n_samples = 1000, factor = 0.3, noise = 0.05)

k = 4

Both K-means and MoG are kind of tryin’ to ”fill in a circular hole with a peg that’s square”.