# How to test accuracy of an unsupervised clustering model output?

I am trying to test how well my unsupervised K-Means clustering properly clusters my data. I have an unsupervised K-Means clustering model output (as shown in the first photo below) and then I clustered my data using the actual classifications.

The photo below are the actual classifications. I am trying to test, in Python, how well my K-Means classification (above) did against the actual classification.

For my K-Means code, I am using a simple model, as follows:

kmeans = KMeans(n_clusters=4, random_state=0).fit(myData)
labels = kmeans.labels_


What would be the best way for me to compare how well my unsupervised KMeans clustering model did against the actual classifications?

• since you know the actual labels, why not use this information and make it a supervised problem? – oW_ Mar 9 '17 at 0:43
• @oW_ Good point. – wogsland Mar 9 '17 at 1:12

Since you have the actual labels, you can compare them with the obtained labels and evaluate performance. Typically purity and nmi (normalized mutual information) are used. Read this (Evaluation of Clustering) document for detailed explanation.

If you don't have actual labels then you can use modularity or [Silhouette] for measuring clustering performance.

You cannot use the labels you obtain through k-means to treat the problem as a supervised classification problem. This is because k-means will assign an arbitrary label to every cluster it forms.

It would be only a matter of luck if you get the arbitrary labeling aligned in a way that the classical accuracy measure makes sense.

What you should be looking for is something called the Average Clustering Accuracy measure. This measure gives you the accuracy of your clustering no matter what the actual labeling of any cluster is, as long as the members of one clusters are together.

Disclaimer: everything I am about to write is thanks to a github script which can be found here. If you want you can skip what is coming, and directly go to the link and apply the function defined there called cluster_acc

The smart way to do it is to try to figure out what is the best setting that would yield me the maximum clustering accuracy. By setting here I mean: what labels in my prediction correspond to what labels in the ground truth.

You can do this in python using sklearn.utils.linear_assignment_.linear_assignment. This function uses the Hungarian algorithm to solve what is called a bipartite graph. Solving said graph is what I described above by 'figuring out the best setting'.

Now, I will try to explain in details how to obtain the bipartite graph, and how to obtain the cluster accuracy from the results of the Hungarian method.

1. Let y and y' be the ground truth and the predicted clustering assignments, respectively. For example, y=[1,1,1,2,2,2,3,3,3]; y'=[2,2,1,3,3,3,1,1,2]. Notice how in this example, a classical accuracy measure will give an accuracy of 11%, where the more fair clustering accuracy measure will give a 78% as will be shown
2. Construct the matrix W, which is a DxD zeros matrix where we will store points. D is the maximum value (label) among the predicted assignments and the ground truth. For the same example above, W will be 3x3.
3. Go over every pair of predicted assignment/ground truth. Add one point to every entry in W where an intersection between the rows described by y' and columns described by y takes place. For our example, this will produce: W = [1 0 2; 2 0 1; 0 3 0] (using MATLAB notation).
4. Subtract W from the maximum value it has. This will place a zero whenever the maximum value (in our case 3) takes place. This gives us our bipartite graph = [2 3 1; 1 3 2; 3 0 3].
5. Then, solving this using the sklearn function mentioned above gives us the following table of matching: [ 1 3; 2 1; 3 2]. This tells us that ones in the prediction correspond to threes in the ground truth, twos to ones, and threes to twos, which can be easily confirmed. This matching table tells us which entries in W we should take into consideration when we are measuring the accuracy
6. Finally, all we have to do is go to the entries (1,3),(2,1),and (3,2) in W and add them up, and take the average. This gives us a clustering accuracy of 78%.

Hope this was helpful, and thanks again to the authors of the attached github repository.

Another possibility to check the performance is to evaluate the confusion matrix. Therein the predicted and actual labels are compared and the classification result for each class is measured