# how to compute clustering error properly

true = c(1,1,1,2)
pred1 = c(1,1,2,2)
pred2 = c(1,1,2,3)


Suppose my dataset has two clusters, after using two clustering algorithms, one gives pred1 and the other gives pred2. If I simply compute the accuracy, pred1 is better. But pred2 correctly isolated the last sample into a cluster.

What measure should I use?

Normalized Mutual Information (NMI) would be a good option. NMI is a widely used metric in the context of clustering and information theory for evaluating the quality of clustering algorithms. It measures the mutual information between cluster assignments and true labels, normalized by the entropy of each, to assess the alignment between the clustering and the true distribution of data. The NMI is given by:

$$NMI(X,Y) = \frac{2 \cdot I(X; Y)}{H(X) + H(Y)}$$

where:

• $$I(X;Y)$$ is the mutual information between the true labels $$X$$ and the predicted labels $$Y$$,
• $$H(X)$$ is the entropy of the true labels,
• $$H(Y)$$ is the entropy of the predicted labels.

The mutual information $$I(X;Y)$$ quantifies the amount of information obtained about one random variable through observing the other random variable. It's calculated as:

$$I(X;Y) = \sum_{x \in X} \sum_{y \in Y} p(x, y) \log\left(\frac{p(x, y)}{p(x)p(y)}\right)$$

where $$p(x,y)$$ is the joint probability distribution of $$X$$ and $$Y$$, and $$p(x)$$ and $$p(y)$$ are the marginal probability distributions of $$X$$ and $$Y$$, respectively.

The entropy $$H(X)$$ of a random variable $$X$$ measures the amount of uncertainty or disorder and is given by:

$$H(X) = -\sum_{x \in X} p(x) \log(p(x))$$

In R:

library(aricode)
true <- c(1,1,1,2)
pred1 <- c(1,1,2,2)
pred2 <- c(1,1,2,3)

aricode::NMI(true,pred1)
[1] 0.3112781

aricode::NMI(true,pred2)
[1] 0.5408521


According to NMI, pred2 performs better at capturing the true structure of your dataset than pred1,