

![0_image_0.png](0_image_0.png)

Table 1: Random matching (1%)

![0_image_1.png](0_image_1.png)

Table 2: Typical trace maximization matching (99%)

![0_image_2.png](0_image_2.png)

We can see that under random clustering, we expect 98.02% on the main diagonal which at first glance looks like a strong (non-random) match. Only applying standard random correction (Cohen, 1960) confirms this to be a pure random match (Cohen's kappa = 0). However, in a clustering context we have two objections against relying on such random corrections: as far as evaluation of cluster agreement is concerned, random corrections, such as Cohen's kappa or Hubert and Arabie's corrected rand index do not work properly, because spatial neighbors have an above-random chance of being clustered together in the absence of any cluster structure in the data. Therefore, agreement indices are too optimistic even with random correction. More importantly, in other contexts such as bagging there is no random correction available at all. If cluster sizes are (very) different, bagging cluster results will suffer because in standard trace maximization big randomly matched cells win over small cells representing non-random matches. Therefore, we are looking for a matching algorithm that does not systematically generate a strong diagonal under random conditions.

## 3. Truematch Algorithm

The problems with standard trace maximization described in the previous section result from focusing on raw counts in a situation with unequal marginal (cluster) probabilities. From other contexts, we know that this is not a good idea. Take the χ 2-test for statistical independence of two categorial variables. It is not based on raw counts. Instead, the matching table of raw counts is transformed to another unit taking the marginals into account. Let N denote the total number of observations, nk the number of observations in one row, nl the number of observations in one column and, finally, let nk,l denote the number