BagClust1 algorithm of Dudoit and Fridlyand (2003), the combination scheme for fuzzy clustering of Dimitriadou et al. (2002) or *truecluster* (Oehlschl¨agel, 2007b).

Truecluster is an algorithmic framework for robust scalable clustering with model selection that combines the idea of bagging with information theoretical model selection along the lines of AIC (Akaike, 1973, 1974) and BIC (Schwarz, 1978). In order to calculate its cluster information criterion (CIC), truecluster requires a reliable cluster matching algorithm. The truematch algorithm presented here was designed to play that role. The organization of the paper is as follows: in Section 2, we show an undesirable feature of the standard approach to cluster matching. In Section 3, we present the truematch algorithm. In Section 4, we demonstrate the benefits of the truematch algorithm within the truecluster framework. In Section 5, we use simulation to compare truematch against standard trace maximization matching and in Section 6, we discuss our results.

## 2. What'S Wrong With Trace Maximization Of The Matching Table

The standard aproach to cluster matching is searching for that permutation of cluster labels that minimizes the euclidean distance to a reference cluster solution. This criterion has been suggested for fuzzy consensus clustering (Gordon and Vichi, 2001; Dimitriadou et al., 2002),
as well as for crisp consensus clustering (Strehl and Ghosh, 2002) or crisp cluster bagging Dudoit and Fridlyand (2003, BagClust1). In the crisp case, this criterion is simply trace maximization of matching table counts: cross-tabulating class memberships of two solutions and then permuting rows/columns of the matching table until the trace becomes maximal.

To our knowledge, cluster publications and software differ in the algorithms used to obtain trace maximization, but do not question the euclidean criterion per se.

For example, Dimitriadou et al. (2002) suggested a recursive heuristic to approximate trace maximization. It is known that trying all permutations has time complexity O(K!), where K denotes the number of clusters. The *Hungarian method* improves on this and achieves polynomial time complexity O(K3). Kuhn (1955) published a pencil and paper version, which was followed by J.R. Munkres' executable version (Munkres, 1957) and extended to non-square matrices by Bourgeois and Lassalle (1971). For a list of further algorithmic approaches to this so-called linear sum assignment problem or *weighted bipartite* matching, see Hornik (2005).

However, scalablility is not the only quality aspect of a matching algorithm. An important statistical feature of a matching algorithm is the following: if we match two random partitions, the matching algorithm should not systematically align the two partitions. We now show that the classic trace maximization does not generally possess this feature.

Assume a cluster algorithm that claims to identify an outlier in a sample of size N = 100 but which actually declares one case as 'outlying' by random. Now assume a procedure that draws two bootstrap samples and clusters them into 99% 'normal' cases and one 'outlier'. In 1% of such procedures, the outlier picked in the second sample will randomly match the outlier picked in the first sample. In such cases, trace maximization matching will lead to a matching table as shown in Table 1. In the other 99%, there will be no match, whichby trace maximization—gives a matching table like that shown in Table 2. The resulting expected matching table is shown in Table 3.