{'fraction_non_alphanumeric': 0.04343437256655034, 'fraction_numerical': 0.013295647910477893, 'mean_word_length': 4.6043316631647, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Are Cluster Validity Measures (In)valid?

Internal cluster validity measures (such as the Calinski-Harabasz, Dunn, or Davies-Bouldin indices) are frequently used for selecting the appropriate number of partitions a dataset should be split into. In this paper we consider what happens if we treat such indices as objective functions in unsupervised learning activities. Is the optimal grouping with regards to, say, the Silhouette index really meaningful? It turns out that many cluster (in)validity indices promote clusterings that match expert knowledge quite poorly. We also introduce a new, well-performing variant of the Dunn index that is built upon OWA operators and the near-neighbour graph so that subspaces of higher density, regardless of their shapes, can be separated from each other better.


Introduction
An internal cluster validity index (CVI for short; see, e.g., [2,29,42,43,58]) is -in theory -a measure of how well a given partitioning of a dataset reflects the underlying structure of the modelled domain. CVIs are frequently employed as tools for selecting the appropriate number of clusters a dataset should be segmented into [43]. By re-applying some algorithm (e.g., k-means or spectral methods), one can determine the splits into 2-, 3-, 4-, . . . , disjoint and nonempty subsets, compute the corresponding CVIs, and select the partition that maximises a chosen utility measure.
Here we shall focus on the other popular use case thereof. Some practitioners utilise CVIs to compare the outputs of different algorithms on the same dataset. Is the partition that the average linkage method returned better than that yielded by the DBSCAN algorithm (provided that they are of equal cardinality)? Similarly, researchers use CVIs for evaluating new clustering algorithms the same way: a new method X ++ produces partitions that have a higher average Caliński-Harabasz indices (on some benchmark datasets) than procedures X, Y , and Z, thus "proving" its superiority. However, we would like to call this methodology into question, especially because CVIs in general constitute an extremely diverse set of measures.
Thus, we shall be interested in determining which of the popular CVIs are particularly suitable or unsuitable for judging the quality of different partitions of the same cardinality. Does a high value of a CVI make sense at all? Can it really be treated as an indicator of a useful clustering result?
To address these questions, we shall find the partitions that yield the highest possible index values, for a large number of datasets and CVIs. In other words, we will treat each CVI as an objective function to be maximised over the whole space of all possible clusterings.
Our assumption here is that a cluster validity measure can only be considered meaningful whenever it is maximised at the partitions closely resembling the reference ones. Otherwise stated, good CVIs should promote results that agree with expert knowledge.
In the course of our study, which we of course detail in the sequel, we have discovered that this is often very much not the case -see Figures 1 and 2 for two quite representative graphical examples. It turns out that some CVIs promote highly overlapping groupings while other ones work better as outlier detectors. One should thus not uncritically believe that a high value of, e.g., a generalised Dunn index GDunn_d2_D1 (see Section 2) is better than a lower one; at the bottom-right subfigures we see that this index promotes some rather random partitions as "best".   Let us note that papers introducing new CVIs are plentiful and new ones are being published on a regular basis, see, e.g., [39,40] for some recent examples. More often than not, such indices are designed to be "the best" for a given particular situation and/or they aim to "eliminate" certain deficiencies with the previous measures. Because of this, the number of CVIs to choose from can be overwhelming, see Section 2 and, e.g., [56,58], for up-to-date overviews.
This is why comprehensive, in-depth comparative studies are so important. There are quite a few interesting surveys of various properties of cluster validity measures in different contexts and settings, but we have only found [59] somewhat methodologically relevant to the task at hand. There, the performance of 8 CVIs was studied but the authors' focus seems slightly shifted towards the analysis of the stability of the solutions generated by what they call differential-evolution-particle-swarm-optimisation algorithms, which of course do not necessarily guarantee finding patterns that are optimal in the eye of a specific cluster validity measure.
Further, in [2] and [42], the authors have shown that most of the CVIs work well with spherical clusters but fail in other types of data. A CVI may fail to assign the highest evaluation to the partition that fits the data best, e.g., the reference one. The conclusion is that there is no single internal cluster validation index that outperforms the other indices everywhere. Similar conclusions were reached in [7], where a model-based study of the correlations of CVIs with carefully chosen error rates across the outputs of different clustering algorithms was conveyed. For more studies in similar spirit, see [14,33,38,43]. Note again that our task is to find the optimal partition under the guidance of a given CVI (amongst the set of all partitions), and not to assess a fixed set of particular clusterings.
We are well aware of the fact that the sheer act of optimising of CVIs is, overall, not a new idea. For instance, the within-cluster sum of squares (WCSS), which is the basis for the Caliński-Harabasz index is used as the objective function in the k-means [41] algorithm.
Other algorithms employing some goodness-of-split measures include, e.g., fuzzy c-means [5] that features a smoothened variant of WCSS, ITM (Information-Theoretic-MST; [46]) which applies a divisive scheme over an Euclidean minimum spanning tree to optimise an information-theoretic criterion, finding Gaussian mixtures via expectation-maximisation, and the generalisation of the Ward linkage in the form of the Lance-Williams formulae [35].
Nevertheless, as n data items enjoy Ω(k n ) possible k-partitionings (Stirling number of the second kind), the problem of optimising a general CVI over the whole search space is very difficult computationally (provably hard in the case of the said WCSS, see [1,25], amongst many others).
Because of this, many algorithms which are defined as minimisers/maximisers of some CVI, use a variety of simplifications, approximations, or heuristics, e.g., they optimise the objective over reduced search spaces or apply some greedy strategies. For instance, to find a partition optimising the aforementioned WCSS, Ward in [57] suggested to build a hierarchy of clusters in an agglomerative way, and Edwards and Sforza in [19] as well as Caliński and Harabasz in [8] proposed to employ some divisive schemes. However, such heuristics are usually limited to specific CVIs; in this paper we would like to go far beyond that.
Also notice that in the literature we may of course find numerous techniques constructed as a combination of different metaheuristics-based optimisation procedures and chosen cluster validity measures playing the role of objective functions, see, e.g., [13,30,34,48,52,61]. Their respective authors often claim that this way they create "new" clustering algorithms (e.g., optimise WCSS using particle swarms vs by means of differential evolution), but it is semantically not quite appropriate. Rather, they should be thought of as ways to test the performance of the optimisation algorithms themselves (with CVIs computed over particular datasets serving as benchmark objectives as in [31]).
Due to the intrinsic difficulty of optimising CVIs, it is no wonder that such a comprehensive study as the current one has not been performed yet. Interestingly, it will turn out that the methodology we have employed, despite its still being based on some approximations, is sufficient for achieving our goal.
Also it is worth mentioning that, up to date, the variety of studies of the various aspects of CVIs (which we shall review in the next section), was quite limited because of the lack of a larger, standardised benchmark set batteries. Most studies considered few datasets, either synthetic, or inherently difficult to partition (such as the UCI [17] datasets). Luckily, thanks to the recent notable efforts by the authors of [21,28,55] and our new battery that aggregates and extends them [24], studies such as this one finally become possible. Furthermore, we propose a unique approach where we account for the fact that a dataset can exhibit multiple equally valid clusterings (as discussed also in [11]).
Let us cast a glance at the structure of this paper. In Section 2 we review some of the most notable cluster validity indices. Furthermore, we propose a new, wide class of CVIs generalising the Dunn index which is based on the notion of ordered weighted averaging (OWA) operators and near-neighbour (NN) graphs. In Section 3 we describe the methodology we have applied in order to answer our main research question, including the description of the benchmark datasets used, the approach to identify the partitions that are optimal from the perspective of a given cluster validity measure, and ways to determine the extent to which they agree with expert knowledge. In Section 4 we present the results of our empirical study, e.g., explore the relationship between cluster compactness or separability and what is considered a good clustering by experts. Also, we perform a cluster analysis of clustering algorithms to determine which methods are most similar to each other. We conclude the paper in Section 5.
We shall be looking for a partition of X into k ≥ 2 nonempty, mutually disjoint clusters, with k fixed in advance. Note that a k-partition For the sake of clarity and simplicity, we will only be focused on cluster validity indices based on Euclidean distances between all pairs of points, x i −x j , or the input points and some other pivots, such as their corresponding cluster centroids, The fixation of the distance metric is not at all restrictive, as various transformations can be applied onto X at the data pre-processing stage, including variable selection, standardisation, outlier removal, feature engineering (by means of spectral/kernel-based methods), etc., see [15,16,44], amongst others.
We shall consider 52 different internal cluster validity indices like I : C k → R. Apart from the most popular, classical CVIs, we also bring forth our own proposal.
2.1. CVIs based on cluster centroids 1,2) BallHall, CalińskiHarabasz. Let µ denote the centroid of the whole X. The two following indices are based on within-cluster sum of squares (WCSS), which itself can be rewritten in terms of the squared Euclidean distances between the points and their respective centroids.
The Ball-Hall index [3] is the WCSS weighted by the cluster cardinality: Note the minus that accounts for the fact that in Section 3.3 we want all the indexes be maximised. Then the Caliński-Harabasz index [8, Eq. (3)] ("variance ratio criterion") is given by: It may be shown that the task of minimising the (unweighted) WCSS is equivalent to maximising the Caliński-Harabasz index. Hence, this index is precisely the objective function in k-means [41] and the algorithms by Ward, Edwards and Cavalli-Sforza, etc., see [8,19,57].
3) DaviesBouldin. The Davies-Bouldin [12,Def. 5] index also refers to the notion of cluster centroids. It is given as the average similarity between each cluster and its most similar counterpart (note the minus sign again): where s i is the dispersion of the i-th cluster: if |X i | > 1, it is given by [12], other choices of s i and m i,j are also suggested; here, we choose the most popular setting (used, e.g., in [2]). 4,5) Silhouette, SilhouetteW. In [54, Sec. 2], Rousseeuw proposes the notion of a silhouette as a graphical aid in cluster analysis.

Silhouettes
Denote the average dissimilarity between the i-th point and all other points in its own cluster with: and the average dissimilarity between the i-th point and all other entities in the "closest" cluster with: Then the Silhouette index is defined as the average silhouette score: with convention ±∞/∞ = 0. The same paper also defines what we call here the SilhouetteW index, being the mean of the cluster average silhouette widths: where s is the number of singletons. Note that SilhouetteW, just like BallHall, employs weighting by cluster cardinalities.

Generalised Dunn indices 6-20) GDunn_dX_DY. In [18, Eq. (3)], Dunn proposed an index defined
as the ratio between the smallest between-cluster distance and the largest cluster diameter. It has been generalised by Bezdek and Pal in [6] as: The numerator measures the between-cluster separation whilst the denominator quantifies the cluster compactness.
Function d was assumed in [6] one of: Bezdek and Pal in [18] considered also d 6 based on the Hausdorff metric but this will be omitted here as it turned out too slow to compute. On the other hand, D was chosen amongst: There are 15 different combinations of the possible numerators and denominators in our study, hence 15 different CVIs, which we will denote as GDunn_dX_DY. In particular, GDunn_d1_D1 gives the original Dunn [18] index.

CVIs based on near-neighbour graphs
assuming there are no tied distances, otherwise, some small random noise can be added).

21-50) DuNN_OWAs_OWAc.
Note that the original Dunn index (denoted GDunn_d1_D1 above) can be viewed as: Here we propose the following generalisation of the above -a generalised Dunn-type index based on the notion of the M -near-neighbour graph and ordered weighted averaging [60] operators -convex combinations (weighted sums) of ordered inputs. Namely: (10) As a measure of cluster separation we aggregate the ordered between-point distances but only provided that they are part of the near-neighbour graph. This will enable us to take the local point density into account and detect well-separable clusters of even quite sophisticated shapes. In a similar manner, cluster compactness will be based on the nearest neighbours as well.
Below we shall study pairs of OWA s and OWA c chosen amongst: • Min, • Max, • Mean, and 0 otherwise ("smooth maximum"), where q (1) ≥ q (2) ≥ · · · ≥ q (z) and ψ(·; µ, σ) denotes the probability density function of the normal distribution with expectation µ and standard deviation σ, see also [10]. For instance, DuNN_25_SMin:5_Max denotes a generalised Dunn index based on each point's 25 nearest neighbours. It uses SMin 5 as a separation measure (computed over a subset of 25n distances restricted to the pair of points belonging to different clusters) and Max as a measure of compactness (the remainder of the 25n distances comprised of point pairs belonging to the same clusters). Moreover, we will study indices like DuNN_25_Mean_Const, where the denominator is fixed at 1.
In the sequel we will consider M = 5 and M = 25. In order to keep the number of cases within reasonable limits, we will restrict ourselves to 30 different CVIs of this type (see Table 3 for a complete listing).

51,52) WCNN_M.
The within-cluster near-neighbours (WCNN) index is parametrised by M ≥ 1. It aims to reflect how many nearest neighbours of every point actually belong to the very same cluster: Ideally, WCNN(C) = 1. Hence, this is a measure of how well the clusters are separated from each other. Additionally, to prevent the formation of small clusters, we will assume WCNN(C) = −∞ whenever there is a cluster of cardinality ≤ M . Similarly as above, we shall consider M ∈ {5, 25}.

What is a valid cluster validity index?
As we have proclaimed in the introduction, our key assumption in this paper is that a meaningful cluster validity measure I should be high whenever it is asked to assess the quality of one of the reference partitions, and lower if it is applied on other clusterings. In other words, useful CVIs should encourage the results that agree with expert knowledge.
In order to be able to answer our main research question, i.e., which cluster validity measures are valid, we need the following components: • benchmark data sets for evaluating the methods (Section 3.2), • a procedure for finding the partition that maximises a given CVI on each dataset (Section 3.3), • a measure for quantifying the degree of agreement between what a CVI thinks is a good partition vs what experts have to say on this matter (Section 3.4).

Benchmark Datasets
We shall use an extensive battery of clustering benchmarks [24] 1 , which not only combines data that have already been used in a number of studies [17,20,21,28,32,55], but also features new test sets. Most importantly, each benchmark dataset comes with a set of l ≥ 1 reference labels that were assigned by experts. The case l > 1 reflects the situation where there might be multiple valid/plausible/useful partitions (compare, e.g., [11]); we are dealing with an unsupervised learning problem after all.
Further, all columns of 0 variance were removed and a tiny amount of noise (Gaussian with µ = 0 and σ equal to 10 −6 of each column's sample standard deviation) was added so as to assure the uniqueness of the clustering results.

Finding optimal partitions (w.r.t. a given CVI)
From now on we assume that the reader is familiar with the basics of the language of mathematical programming, see, e.g., [37,49] for a comprehensive overview.
For a predefined X and k, let us fix a cluster validity measure I : C k → R. Without loss in generality, we assume that the higher the I, the more useful the partition. This is because we can always take I := −I, as we have done with the Ball-Hall and Davies-Bouldin indices above.
For a given k-partition C, let NEIGHBOURS(C) denote the set of all surjections like C : [1 : n] onto → [1 : k] with C (i) = C(i) for some i and C (j) = C(j) for all j = i. In other words, it is the set of all k-partitions that can be obtained from C by relocating a single point to some other cluster.
We are interested in finding a partition which is a solution to the optimisation problem: maximise i.e., C * ∈ C k such that I(C * ) ≥ I(C) for all C ∈ C k . (12) is not unique; clusterings are defined up to a permutation of the cluster numbers (IDs). For example, a 2-partition of a 4-ary set encoded like (C(1), C(2), C(3), C(4)) = (1, 1, 2, 1) is semantically equivalent to (2, 2, 1, 2). Moreover, it might happen that a dataset exhibits a number of equally good splits. This is exactly the case when we apply WCNN_M on datasets whose M -near-neighbour graphs are disconnected and the number of connected components is greater than k. For instance, as-

Remark 1. The solution to
In general, the combinatorial optimisation problem (12) is extremely difficult to solve in practice. Enumerating all the possible solutions is virtually impossible as the number of possible partitions is equal to the Stirling number of the second kind, S(n, k) = 1 , and note that in our case 2 ≤ k n. In this paper, however, we shall make reasonable efforts towards finding the maximum of the objective (12). In essence, for each dataset we will generate dozens of "interesting" partitions (using existing state-of-the art clustering algorithms and evolutionary-based heuristics, see Section 3.5) each of which we shall then try to improve with an expansive variant of the steepest ascent hill climbing (with tabu [27] search-like memoisation) that itself guarantees to land in a local maximum of the objective (12).
The maximum of the objective (12) will be sought by means of the following variant of the hill climbing scheme. Algorithm 1. With {C 1 , . . . , C m } let us denote the set of initial candidate solutions (see Section 3.5 for more details) ordered in such a way that I(C 1 ) ≥ · · · ≥ I(C m ). For brevity of notation, we assume that I(∅) = −∞.
In: I :, C 1 , C 2 , . . . , C m , P ∈ N; 1. T = ∅; (a "tabu" list) 2. C * = C 1 ; (best solution so far) 3. for C = C 1 , C 2 , . . . , C m do: (I(C 1 ) ≥ · · · ≥ I(C m )) 3.1. p = 1; (cannot improve further) 3.5. T = T ∪ {C + }; (never visit C + again) 3.6. C = C + ; 3.7. if I(C) > I(C * ), then C * = C, else p = p + 1; 3.8. if p ≤ P , then go to step 3.2; (try to improve current C + next) 4. return C * ; It is easily seen that the algorithm guarantees that the solution returned cannot be further improved by relocating an individual point to a different cluster. Hence, the return value is definitely a local maximum, however there is of course no guarantee that the identified optimum is global. As we argue below, though, it will turn out sufficient for our purposes.
We shall set the upper bound for the number of iterations without improvement, P , to 250 (we have rarely seen any improvements beyond 100, though). This allows for the procedure to explore the area around the candidate solutions quite broadly. Note that the T set, which guarantees that no partition is considered twice, is shared across all the iterations so that the visited subspace is even broader. Hence, the search is more comprehensive than if we had restarted the whole procedure independently for each C 1 , . . . , C m and then chose the best amongst the identified local maxima.

Measuring similarity to reference partitions
For a given benchmark dataset X, let C $ 1 , C $ 2 , . . . , C $ l be the reference partitions and k 1 , . . . , k l be their respective cardinalities.
Note that any clustering method c (for example, the maximiser of the Caliński-Harabasz index or the Ward linkage) can be thought of as a function that takes X and k i on input and yields a k i -partition of X on output, i.e., c(X, k i ) ∈ C k i .
We will use the adjusted Rand index (ARI) [36,53] to measure the similarity between c(X, k i ) and C $ i . Recall that two equivalent partitions yield ARI equal to 1. Moreover, two "independent" (see [26] for discussion) clusterings have the expected ARI of 0. Negative ARIs will be replaced with 0 for better interpretability of the results.
In order to quantify the quality of the method c on X, we will evaluate its outputs against all the available reference labellings and choose the highest ARI in result: This is to account for the fact that there might be many equally valid partitions and the (unsupervised) method c should be rewarded if it identifies one of them (does not matter which one). It is worth noting that only 13 datasets have l > 1, 11 of which come with reference labellings that do not have identical cardinalities. Also, some reference partitions include noise points -these were excluded during the computations of the ARIs (after the output of c was determined, as none of the clustering methods studied features a noise point detector). Overall, this validation methodology conforms with [24].

Candidate solutions
To generate the list of candidate (initial) solutions used in Algorithm 1, we will apply many different clustering algorithms on each dataset, including: • the most popular hierarchical clustering methods (single, average, Ward, centroid, complete linkage), • Genie [23] (with different thresholds), • information-theoretic algorithms (ITM [46] as well as IcA and GIc [9]), • other methods in the well-established sklearn [50] package for Python: k-means, Gaussian mixtures, spectral clustering with different kernels, Birch (with a range of parameter values).
This gives 87 different combinations of algorithms and their setups. In Section 4 we provide some technical details about their implementations. Note that 12 of them will constitute the baseline in our empirical study below. Also, we shall utilise the following heuristic solvers: • particle swarm optimisation (via R package pso [4]), • "global" optimisation by differential evolution [51] (DEoptim [45] in R).
They pinpoint local maxima based on 3-5 restarts from different initial candidate solutions. Both of them search over the continuous space R (V k)×d in such a way that the clusters are represented by means of V k vantage points. V vantage points represent one cluster (empirically, we have determined V = 5 be a good compromise between quality and speed). In every iteration, each point is assigned to its closest vantage point, and, as a consequence, to a cluster which is represented by this vantage point. This approach allows to determine clusters of more sophisticated shapes than when simply V = 1 is utilised (as with V > 1 we consider different unions of cells in a Voronoi diagram). Additionally, to broaden the search space even further, we will pick 5 partitions completely at random, i.e., each C ∈ C k being such that C(1), . . . , C(n) being independent random variables from the discrete uniform distribution on [1 : k]. Nevertheless, starting from a random partition never turned out better than an assisted initialisation based on one of the aforementioned candidate solutions.
Most importantly, as each dataset comes with a set of reference labels given by experts, these shall be considered as well.
Overall, for each dataset, we have obtained m 100 different clusterings 2 , however, quite often there were duplicated entries, hence the effective m was in the range 30-50.
An ideal index, if it existed, would be 100% concordant with expert labels. That is, it would be impossible for the hill climbing method to improve them any further. Note that when we maximise I, the reference partitions are always amongst the initial candidate solutions which are fed to Algorithm 1. Therefore, our procedure guarantees that all the good combinations of indices and datasets must be identified. If the hill climbing method converges to a different solution, it means that I promotes some points that are less compatible with experts' opinion.
Let us stress that neither I itself, nor the procedure for maximising it, is "aware" of the existence of any external labels: only X and k are input to c, not C $ i ; this is still an unsupervised learning method. Algorithm 1 converges where it converges; the starting points are plentiful and there is a great variety of them. Reference partitions are only used at the final evaluation stage.
The correctness of our C++ implementations 3 of the cluster validity indices was verified against R packages clusterCrit 1.2.8 and clusterSim 0.49-2 (wherever applicable). Our library turned out significantly faster than the two reference ones. Moreover, we allowed for the computing of the indices incrementally (as mentioned above), which was particularly beneficial in terms of the run-time of Algorithm 1.
Overall, the computations took ca. 3 months of computing time with the use of 2 computer clusters (within the allocated resource limits we have been granted by ICM UW/PL-Grid and the School of IT at Deakin University).

Which index best agrees with expert knowledge?
Let us proceed with the evaluation of the agreement between the cluster validity indices and expert knowledge.

GDunn_dX_DY
We first focus on the 15 generalised Dunn indices [6]. To recall, GDunn indices are defined as the ratio of cluster separation (d) and compactness (D). Figure 3 gives the box-and-whisker plots for the Adjusted Rand indices across the benchmark datasets studied. We clearly see that d 1 , i.e., the pairwise minimum distance (used in the original Dunn index) outperforms the other measures. In this scenario, the Wilcoxon signed-rank test does not find the choice of D significant (α = 0.05).
Also, the measures based on d 5 are significantly worse than all other ones. Perhaps it would be better if d 5 was defined as the average squared pointcentroid distance, not just average raw distance; recall that a centroid is the point that minimises exactly the square of the Euclidean metric.  Figure 4 shows the empirical distribution of ARIs in the case of the nearneighbour versions of the Dunn index.

DuNN
For a fixed separation measure OWA s , OWA c equal to Min and Const is never significantly worse (one-sided Wilcoxon test, α = 0.05) than Max and Mean. Moreover, there is no significant difference between Min and Const, therefore, applying Ockham's razor, we conclude that the cluster compactness could be omitted whatsoever (at least as far as our selection of aggregation functions is concerned).
Setting OWA c at Const, interestingly, DuNN_25_SMin:5_Const significantly outperforms all the variants except DuNN_5_Mean_Const.
Moreover, DuNN_25_Min_Const is better than DuNN_5_Min_Const. Also note that the behaviour of Max or its smoothened version is particularly poor.

Other methods
As a base line, the above and remaining CVIs will be compared against the outputs of 12 clustering algorithms: 1-5) Average, Centroid, Complete, Ward, Single -classical agglomerative hierarchical clustering algorithms; 6-9) Genie_G0.1, Genie_G0.3, Genie_G0.5, Genie_G0.7 -the robust hierarchical clustering algorithm Genie that we have proposed in [23], with different thresholds for the Gini index of the inequity in cluster sizes; 10) ITM -greedy divisive minimiser of an information theoretic criterion over minimum spanning trees [46]; 11) GaussMix -expectation-maximisation (EM) for Gaussian mixtures with 100 restarts and each cluster having its own covariance matrix; 12) KMeans -Lloyd-like k-means algorithm with 10 restarts (note that this is a heuristic to optimise the Caliński-Harabasz index/within-cluster sum of squares).  [50]). Moreover, the implementation of ITM [46] is available from GitHub 4 . Tables 2 and 3 give the basic summary statistics on the empirical distribution of the ARIs across the 62 benchmark datasets and all the methods studied. Moreover, Figure 5 displays the boxplots.
We observe what follows: • Our Genie algorithm [22] outperforms other methods. Note that it is significantly faster than most other algorithms as it is based on the minimum spanning tree of the pairwise distance graph.
• The near-neighbour-based DuNN indices that we have proposed in this paper are much better than GDunn.
• Overall, the algorithms based on the near-neighbourhood (minimum spanning trees can be considered a variant thereof, in some sense), seem to be much more valid for clustering tasks.
• Next in line are Gaussian mixtures that detect clusters of specific (spherical) shapes.
• Of course, k-means give similar results to the Caliński-Harabasz optimiser as the former is a heuristic to optimise the latter as the objective. Also Ward is a greedy agglomerative maximiser of the same objective.
• Most other cluster validity measures seem to promote the clusterings that are not concordant to expert knowledge which calls their relevance into question.
• SilhouetteW and BallHall -the weighted-by-cluster-cardinality versions of Silhouette and CalińskiHarabasz, respectively, perform worse than their unadjusted counterparts.
• The poor performance of some methods may be partially explained by the inequality of the cluster sizes they output -some of them are prone to generating few very large clusters and a number of very small ones (perhaps even being singleton objects produced the least skewed partition sizes. However, let us note that this is not necessarily an accurate predictor of the clustering quality (see also [22] for discussion).
• Note that some datasets are inherently hard to cluster (the outputs of no algorithm matches the reference partition well); these include uci/sonar (max ARI=0.036), uci/yeast (max ARI=0.181), and uci/ionosphere (max ARI=0.401).

Clustering of clustering algorithms
Let us perform an interesting exercise where we determine a grouping of the clustering methods by means of the overall similarity of the results they generate on all the benchmark datasets. This way, we will know which methods (and CVIs) are "semantically" similar to each other.
We have computed the AR indices between all pairs of label vectors generated by all the methods (this time, reference/expert labels were not used). We used the mean, the median, or the 3rd quartile of (1.0 − ARI) to obtain a single number that summarises the "distance" between the algorithms.
We have applied the agglomerative hierarchical clustering algorithm with complete linkage so that the resulting dendrograms, which are depicted in Figure 6, are more interpretable (this will give us the maximal aggregated dissimilarities between all methods in a cluster). Note that we will be only interested in groups of algorithms that have small pairwise distances.
The majority vote of the results obtained by means of all the three dissimilarity measures gives the following "consensus" clusters, where the algorithms have quite high overall degree of similarity: • CalińskiHarabasz, KMeans, • DuNN_25_Mean_Const, DuNN_25_Mean_Min, • DuNN_5_Min_Const, DuNN_5_Min_Min, • DuNN_25_Min_Const, DuNN_25_Min_Min, DuNN_25_SMin:5_Const, Let us note that: • The above indicates again that in our task, the denominator (compactness measure) in all the generalisations of the Dunn index has no significant impact on the results. However, when CVIs are applied for the purpose of selecting the optimal number of clusters, the conclusions could be much different.
• GDunn and DuNN are not so similar, despite they both generalise the same index, Dunn. On the other hand, the latter (to recall, it is based on d 1 = Min) is similar to Single linkage (which is determined through a greedy (agglomerative) consumption of the nearest pairs of points; it can be computed based on a minimum spanning tree).
• Ward is quite similar to CalińskiHarabasz, and KMeans, which was to be expected as they tend to optimise the same objective function.

Conclusion and Future Work
We have studied whether cluster validity indices really promote partitions that reflect what experts judge as meaningful. While some measures could still be considered relevant in the task of selecting the right number of clusters, it is better not to treat them as objective functions for identifying good partitions. This is particularly the case with the Davies-Bouldin, Silhouette, Ball-Hall, and the no-near-neighbour-based versions of the generalised Dunn index.
In the future, we will verify the usability of our new near-neighbour-based generalisations of the Dunn index in the problem of choosing the meaningful number of clusters. Their advantage is that they take into account the locality of the input points as well as the relative density of the points' distribution. Certainly, more combinations of OWA operators should be studied.  GDunn_d5_D2 SilhouetteW GDunn_d5_D1 GDunn_d5_D3