How to find similarity matrix from a confusion matrix?

Question

How to find similarity matrix from a confusion matrix of a multiclass classification?

For example in this paper: Exploiting confusion matrices for automatic generation of topic hierarchies and scaling up multi-way classifiers

On page 7, how to get the similarity matrix from the confusion matrix?

Also, I would like to know if there's any other method.

Answer 1

The $L_1$ distance is also called Manhattan distance. Between two vectors $\boldsymbol{p}$ and $\boldsymbol{q}$ it is defined as:

$$d(\boldsymbol{p}, \boldsymbol{q}) = \sum_{i=1}^n|p_i - q_i|$$

The $L_2$ distance is the Euclidean distance:

$$d(\boldsymbol{p},\boldsymbol{q}) = \sqrt{\sum_{i=1}^n(p_i-q_i)^2}$$

However, on figure 5, the distance matrix is not calculated with Euclidean distance, but it seems to me that squared Euclidean distance was attempted:

$$d^2(\boldsymbol{p}, \boldsymbol{q}) = (p_1 - q_1)^2 + (p_2 - q_2)^2 + \ldots + (p_n - q_n)^2$$

Here's a small script in R where you can verify the computation:

conf.matrix <- t(matrix(c(4,0,6,0, 0,4,6,0, 0,0,7,3, 0,0,4,6), nrow=4))

# Manhattan distance (L1 norm)
figure.4 <- dist(conf.matrix, method = 'manhattan', diag = TRUE)
print(figure.4)
   1  2  3  4
1  0         
2  8  0      
3  8  8  0   
4 12 12  6  0

# Euclidean distance (L2 norm)
figure.5 <- dist(conf.matrix, method = 'euclidean', diag = TRUE)
print(figure.5)
         1        2        3        4
1 0.000000                           
2 5.656854 0.000000                  
3 5.099020 5.099020 0.000000         
4 7.483315 7.483315 4.242641 0.000000

# Squared euclidean distance (note that it is not fully matching figure 5)
print((figure.5)^2)
   1  2  3  4
1  0         
2 32  0      
3 26 26  0   
4 56 56 18  0

I didn't go through the paper but notice that with these norms you are calculating distances and not similarities. There are many ways to define distances and similarities and this is completely dependent on what you want to achieve with the data. You can get an idea by taking a look at the definition of a metric.