Andrea Campagner
email: a.campagner@campus.unimib.it

Davide Ciucci

Thierry Denoeux

A general framework for evaluating and comparing soft clusterings

Keywords: Clustering analysis, Soft clustering, Evaluation, Validation, Comparison

In this article, we propose a general framework for the development of external evaluation measures for soft clustering. Our proposal is based on the interpretation of soft clustering as representing uncertain information about an underlying, unknown hard clustering. We present a general construction, based on optimal transport theory, by which any evaluation measure can be naturally extended to soft clustering. The proposed "transport-based measure" provides an objective, interval-valued comparison index that represents the range of compatibility between two soft clusterings. We study the metric and complexity properties of the proposed approach, as well as its relationship with other existing proposals. We also propose approximation and bounding algorithms that make the approach practical for large datasets. Finally, we illustrate the application of the proposed method through two computational experiments.

Introduction

Clustering analysis is an important task within machine learning and data analysis. Intuitively, the aim of clustering analysis is to detect, in an unsupervised fashion, a grouping of objects within categories, called clusters. Clustering analysis has important applications in different settings, including anomaly detection [START_REF] Ahmed | A survey of network anomaly detection techniques[END_REF], community detection [START_REF] Harenberg | Community detection in largescale networks: a survey and empirical evaluation[END_REF], and biological data analysis [START_REF] Liu | A comparison framework and guideline of clustering methods for mass cytometry data[END_REF].

One of the most important steps in clustering analysis regards the evaluation of the obtained results [START_REF] Xiong | Clustering validation measures, in: Data Clustering[END_REF]. Two main evaluation approaches can be distinguished. Internal validation indices [START_REF] Lipor | Clustering quality metrics for subspace clustering[END_REF][START_REF] Gagolewski | Are cluster validity measures (in) valid?[END_REF] evaluate the quality of a clustering result with reference to intrinsic properties of the result itself (e.g., separation of clusters). By contrast, external evaluation methods [START_REF] Lei | Ground truth bias in external cluster validity indices[END_REF] objectively assess the quality of a clustering result, by means of a comparison between two or more clusterings, one of which is usually assumed to be the correct one. In this article, we refer exclusively to external evaluation.

In the case of hard clustering, that is clustering methods in which each object is unambiguously assigned to a single cluster (e.g., k-means), several evaluation criteria have been considered [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions[END_REF]. These include the Rand index [START_REF] Rand | Objective criteria for the evaluation of clustering methods[END_REF], purity [START_REF] Schütze | Introduction to information retrieval[END_REF], information-theoretic measures [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF], or the partition distance [START_REF] Day | The complexity of computing metric distances between partitions[END_REF]. By contrast, how to properly evaluate the results of a clustering analysis is much less clear in the case of soft clustering methods, i.e., techniques that provide an explicit representation of uncertainty [START_REF] Peters | Soft clustering: Fuzzy and rough approaches and their extensions and derivatives[END_REF][START_REF] D'urso | Informational paradigm, management of uncertainty and theoretical formalisms in the clustering framework: A review[END_REF]. Several soft clustering methods have been proposed in the literature, each of which represents clustering uncertainty in different ways. In rough [START_REF] Lingras | Interval set clustering of web users with rough k-means[END_REF] clustering, clusters are represented as pairs of sets containing the objects that certainly or only possibly belong to the cluster. In probabilistic [START_REF] Bouveyron | Modelbased clustering and classification for data science: with applications in R[END_REF] and fuzzy [START_REF] Ashtari | Supervised fuzzy partitioning[END_REF][START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithms[END_REF][START_REF] Ruspini | Fuzzy clustering: A historical perspective[END_REF] clustering, the object-cluster assignment is represented through a probability distribution or fuzzy partition. In possibilistic [START_REF] Krishnapuram | A possibilistic approach to clustering[END_REF][START_REF] Ruspini | Fuzzy clustering: A historical perspective[END_REF] clustering, uncertainty is represented through possibility distributions. Finally, in evidential [START_REF] Denoeux | Evidential clustering: a review[END_REF][START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF][START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF][START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF] clustering, the uncertain object-cluster assignment is represented by belief functions. Remarkably, evidential clustering has been shown to generalize all the above mentioned methodologies [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF].

In the literature, the development of soft clustering evaluation measures has mainly focused on the extension of common measures, notably the Rand index, to the setting of fuzzy clustering [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions[END_REF][START_REF] Campello | A fuzzy extension of the rand index and other related indexes for clustering and classification assessment[END_REF][START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF], while only recently a formulation of this approach has been introduced for the more general case of evidential clustering [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. Most proposals in the literature, however, have been shown to be severely lacking in terms of satisfied properties [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF]. For example, most measures fail to be semi-metrics, hence cannot be used to check the equivalence between two clusterings. Additionally, the question of which appropriate metric properties an evaluation measure should satisfy has scarcely been studied and, consequently, the existing metrics can be hard to interpret or apply.

As a second, and most remarkable limitation, existing measures fail to properly quantify and distinguish different types of uncertainty that can arise in soft clustering [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. In particular, two relevant types of uncertainty can be distinguished: ambiguity, i.e., the inability to uniquely assign an object to a single cluster (typical of rough clustering); and partial assignment, i.e., the assignment of objects to multiple clusters, each with a given degree of membership (typical of fuzzy and probabilistic clustering). Existing evaluation measures, however, conflate these two different types of uncertainty. This issue is especially problematic for more general types of soft clustering, such as evidential clustering [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF], in which the two forms of uncertainty coexist.

We claim that the above mentioned limitations stem from a lack of understanding concerning the following two natural questions: What should be quantified by an evaluation measure for soft clustering? Which properties should such a measure have? In this article, following previous accounts in the literature [START_REF] Campagner | Orthopartitions and soft clustering: soft mutual information measures for clustering validation[END_REF][START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF], we argue that such measures have two possible aims. Since we interpret soft clustering as describing the uncertainty with respect to an underlying but unknown hard clustering, a first aim is to provide a picture of the uncertainty within the two soft clusterings to be compared. Second, such a measure should provide a way to objectively compare two clusterings or to assess the quality of a clustering with respect to a ground truth. By drawing from the previous literature [START_REF] Campagner | Orthopartitions and soft clustering: soft mutual information measures for clustering validation[END_REF][START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF], in this article we argue that a natural requirement is to adopt interval-valued measures that satisfy certain reasonable metric properties. Intuitively, the lower bound of the interval should quantify the compatibility between two soft clusterings, i.e., whether there exists a hard clustering compatible with both soft clusterings [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. By contrast, the upper bound should quantify their similarity, i.e., to which degree the two clusterings are strictly equivalent, penalizing any possible ambiguity. To provide a formal translation of these principles, we require that the lower bound should be a consistency, while the upper bound should be a metric (see Section 2.1).

In this article, we propose a general approach to address the above mentioned questions and limitations, by introducing a mathematical construction that can be applied to extend any clustering evaluation measure to the case of soft clustering. The proposed transport-based distance (see Section 3.2) relies on the interpretation of soft clustering as representing a distribution over hard clusterings (see Section 3.1). We then use construction methods from optimal transport theory [START_REF] Villani | Topics in optimal transportation[END_REF] to provide interval-valued comparison indices that can be used to objectively compare two soft clusterings in terms of their mutual consistency and equality, while providing an account of the uncertainty involved in the comparison. We provide an in-depth study of the proposed method, with respect to both its computational complexity and metric properties. Furthermore, we describe approximation techniques that can be used to reduce the computational complexity of the method and we show that some known measures previously proposed in the literature emerge as special cases of our framework (see Section 4). Finally, we illustrate the application of our approach through two simple computational experiments (see Section 5).

Background and Related Work

In the following section, we first provide basic background on metric spaces and related structures in Section 2.1. Then, we summarize some important notions related to clustering in Section 2.2. Finally, a brief review of clustering evaluation measures for soft clustering is provided in Section 2.3. Background material on belief function theory is presented in Appendix A.

Metric Spaces

Let us first recall some basic notions on metric spaces [START_REF] Sutherland | Introduction to metric and topological spaces[END_REF]. Let X be a countable set. A metric over X is a function d : X × X → R + s.t.: (M1) ∀x ∈ X, d(x, x) = 0;

(M2) ∀x, y ∈ X, x ̸ = y =⇒ d(x, y) > 0;

(M3) ∀x, y ∈ X, d(x, y) = d(y, x);

(M4) ∀x, y, z ∈ X, d(x, z) ≤ d(x, y) + d(y, z).

Metric d is normalized if max x,y∈X d(x, y) = 1. If d is a normalized metric, then its dual s = 1 -d is called a similarity over X. Several weakenings of the notion of metric have been considered in the literature. Here we recall the following:

• d is a pseudo-metric iff it satisfies (M1), (M3) and (M4);

• d is a semi-metric iff if satisfies (M1), (M2) and (M3);

• d is a meta-metric iff it satisfies (M2), (M3) and (M4);

• d is a ρ-relaxed metric (with ρ ∈ R + ) iff it satisfies (M1), (M2), (M3) and ∀x, y, z ∈ X, d(x, z) ≤ ρ (d(x, y) + d(y, z)) .
Obviously, combinations of the above concepts can be considered (e.g., a semipseudo-metric is a function satisfying only (M1) and (M3)). If d is a normalized pseudo-(resp., semi-, meta-ρ-relaxed) metric, then s = 1 -d is called a pseudo-(resp., semi-, meta-ρ-relaxed) similarity. For simplicity, in the following, we will refer to any semi-pseudo similarity as a consistency.

A metric d over X can be extended to a metric over 2 X . The resulting metric d H is called the Hausdorff metric based on d, defined as Similarly, a metric d over X can be extended to a metric over the space P(X) of probability measures over X. The resulting metric, denoted as d W , is called the Wasserstein metric (also known as Kantorovich-Rubinstein metric) [START_REF] Kantorovich | Mathematical methods of organizing and planning production[END_REF][START_REF] Villani | Topics in optimal transportation[END_REF] based on d. It is formally defined, for any two probability measures P r 1 and P r 2 on X, as

d H (A, B) = max{max a∈A d(a, B), max b∈B d(A, b)}, (1)
d W (P r 1 , P r 2 ) = min σ (x1,x2)∈X 2 σ(x 1 , x 2 )d(x 1 , x 2 ) (2) s.t. x2∈X σ(x 1 , x 2 ) = P r 1 (x 1 ) x1∈X σ(x 1 , x 2 ) = P r 2 (x 2 ) (x1,x2)∈X 2 σ(x 1 , x 2 ) = 1 ∀(x 1 , x 2 ) ∈ X, σ(x 1 , x 2 ) ≥ 0.
If d is a (pseudo-, meta-, semi-) metric then d W satisfies the same properties. The Wasserstein metric is the minimal expected distance between two distributions P r 1 and P r 2 for all joint distributions whose marginals are P r 1 and P r 2 . It can also be seen as the minimal cost of transforming one distribution into the other by moving the probability masses.

Clustering

Let X = {x 1 , ..., x n } be a set of objects. A hard clustering is a unique assignment of objects in X to clusters. Formally, a hard clustering is a mapping C : X → Ω, where Ω = {ω 1 , ..., ω k } is a set of clusters. This representation is called object-based. By an abuse of notation we identify cluster ω i with the set {x ∈ X : C(x) = ω i }. We denote by χ ωi the indicator function corresponding to ω i . Any two clusterings C 1 , C 2 that are equivalent up to a relabeling of the clusters are considered to be identical. We denote the corresponding equivalence relation by

C 1 ∼ C 2 . Example 2.1. Let X = {x 1 , . . . , x 5 } and Ω = {ω 1 , ω 2 , ω 3 }. Then, the mapping C : X → Ω s.t. C(x 1 ) = C(x 5 ) = ω 1 , C(x 2 ) = C(x 3 ) = ω 2 and C(x 4 ) = ω 3 is a hard clustering.
For simplicity, we represent C as the tuple c = (1, 2, 2, 3, 1),

where c i = j iff C(x i ) = ω j .
Given a hard clustering C, its relational representation is the equivalence relation

[C] ⊆ X × X such that ∀(x, y) ∈ X 2 , (x, y) ∈ [C] ⇔ C(x) = C(y). Obviously, C 1 ∼ C 2 iff [C 1 ] = [C 2 ].
Example 2.2. The clustering defined in Example 2.1 can be equivalently described by its relation representation

[C] = {(x 1 , x 5 ), (x 5 , x 1 ), (x 2 , x 3 ), (x 3 , x 2 )}.
As mentioned in Section 1, in soft clustering the unique assignment assumption is relaxed: the intuition is that we allow uncertainty in the assignment of objects to clusters. With reference to evidential clustering, which represents the most general framework among the ones we consider, the uncertainty about cluster assignment is represented as a Dempster-Shafer mass function (see Appendix A). Formally, using the object-based representation, an evidential clustering is a set M = {m x } x∈X , where each m x is a mass function, i.e., a mapping

m x : 2 Ω → [0, 1] such that A⊆Ω m x (A) = 1. Example 2.3. Let X and Ω be as in Example 2.1. Then M = {m xi } xi∈X defined as: m x1 ({ω 1 }) = 1; m x2 ({ω 2 }) = 1; m x3 ({ω 2 , ω 3 }) = m x3 (Ω) = 0.5; m x4 ({ω 3 }) = 1; m x5 (Ω) = 0.5, m x5 ({ω 1 }) = m x5 ({ω 2 }) = m x5 ({ω 3 }) = 1/6 is an evidential clustering.
If the mass functions m x are logical, i.e., if they are such that m x (A) = 1 for some subset A ⊆ Ω, then, the collection R = {m x } x∈X is said to be a rough clustering. For each x ∈ X, we denote the unique A ⊆ Ω s.t. m x (A) = 1 as R(x). A rough clustering can be equivalently represented by associating with each cluster ω a pair (l(ω), u(ω)) of subsets of X verifying l(ω) ⊆ u(ω). Intuitively, l(ω) contains the elements that "certainly" belong to the cluster, while u(ω) contains the elements that "possibly" belong to the cluster. The set u(ω) \ l(ω), called the boundary of the cluster, contains the elements whose assignment to cluster ω is uncertain. Finally, a rough clustering can be seen as a set of hard clusterings. Namely, a hard clustering C is compatible with R if for all x ∈ X, C(x) ∈ R(x). Then, we identify R with the set C(R) = {C : C is compatible with R}.

Example 2.4. Let X and Ω be defined as in Example 2.1. Then R defined by

R(x 1 ) = ω 1 , R(x 2 ) = ω 2 , R(x 3 ) = {ω 2 , ω 3 }, R(x 4 ) = ω 3 , R(x 5 ) = Ω is
C(R) = {(1, 2, 3, 3, 3), (1, 2, 3, 3, 2), (1, 2, 3, 3, 1), (1, 2, 2, 3, 3), (1, 2, 2, 3, 2), (1, 2, 2, 3, 1)}.
For simplicity, we denote C(R) as (1, 2, {2, 3}, 3, {1, 2, 3}).

If all m x are Bayesian, then the collection F = {m x } x∈X is a fuzzy or probabilistic clustering. Finally, if all m x are consonant, then the collection P = {m x } x∈X is a possibilistic clustering. Both fuzzy and possibilistic clustering can be represented as a collection of cluster membership vectors F = {µ x } x∈X , where µ x (ω) = A∋ω m x (A). In possibilistic clustering it is assumed that, for all x ∈ X, max ω∈Ω µ x (ω) ≤ 1, while in fuzzy clustering it is usually assumed that for all x ∈ X, ω∈Ω µ x (ω) = 1.

Example 2.5. Let X and Ω be defined as in Example 2.1. Then, F defined as

µ x1 (ω 1 ) = 1, µ x2 (ω 2 ) = 1, µ x3 (ω 2 ) = µ x3 (ω 3 ) = 0.5, µ x4 (ω 3 ) = 1 and µ x5 (ω 1 ) = µ x5 (ω 2 ) = µ x5 (ω 3 ) = 1 3 is a fuzzy clustering. P defined as µ x1 (ω 1 ) = 1, µ x2 (ω 2 ) = 1, µ x3 (ω 2 ) = µ x3 (ω 3 ) = 1, µ x4 (ω 3 ) = 1 and µ x5 (ω 1 ) = µ x5 (ω 2 ) = 1, µ x5 (ω 3 ) = 0.8 is a possibilistic clustering.
Similarly to the case of hard clustering, a relational representation can be defined also for the case of evidential clustering [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. In this case, let Θ = {s, ¬s} be the frame where s denotes that two objects are in the same cluster, and ¬s denotes the opposite event. Given an evidential clustering M , the corresponding relational representation can be obtained, for any two distinct objects (x, y) ∈ X 2 , by combining m x and m y by Dempster's rule [START_REF] Shafer | A mathematical theory of evidence[END_REF], and computing the restriction of the resulting mass function to Θ [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. The resulting mass function m x,y is then defined by

m x,y ({s}) = ω∈Ω m x (ω)m y (ω) (3a) m x,y ({¬s}) = A∩B=∅ m x (A)m y (B) -m(∅) (3b) m x,y (Θ) = A∩B̸ =∅ m x (A)m y (B) -m(s) (3c) m x,y (∅) = m x (∅) + m y (∅) -m x (∅)m y (∅). ( 3d
)
Obviously, it holds that m x,x ({s}) = 1.

Example 2.6. Let M be the evidential clustering defined in Example 2.3. Then, the relational representation [M ] of M is defined as the reflexive (i.e., m x,x (s) = 1) and symmetric (i.e., m x,y = m y,x ) closure of the relation shown in Table 1.

(Θ) (x 1 , x 2 ) 0 0 1 0 (x 1 , x 3 ) 0 0 0.5 0.5 (x 1 , x 4 ) 0 0 1 0 (x 1 , x 5 ) 0 1 6 1 3 0.5 (x 2 , x 3 ) 0 0 0 1 (x 2 , x 4 ) 0 0 1 0 (x 2 , x 5 ) 0 1 6 1 3 0.5 (x 3 , x 4 ) 0 0 0 1 (x 3 , x 5 ) 0 0 1 12 11 12
(x 4 , x 5 ) 0

1 6 1 3 0.5
For the case of fuzzy and possibilistic clustering, two alternative approaches to obtain a relational representation have been considered. In the first approach, proposed by Campello et al. [START_REF] Campello | A fuzzy extension of the rand index and other related indexes for clustering and classification assessment[END_REF], µ x,y is defined, based on a t-norm ∧ and the dual t-conorm ∨ as

µ x,y (s) = ω∈Ω µ x (ω) ∧ µ y (ω) (4a) µ x,y (¬s) = ω1̸ =ω2∈Ω µ x (ω 1 ) ∧ µ y (ω 2 ). (4b)
When ∧ = ⊗ P (i.e., the product t-norm), ∨ = ⊕ P (i.e., the bounded sum t-conorm) and {µ x } x∈X defines a fuzzy partition, then we obtain the same definition given previously for evidential clustering.

In the second approach, proposed by Hüllermeier et al. [START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF], the relational representation is defined based on a normalized metric d F on [0, 1] Ω (i.e., the set of functions Ω → [0, 1]). Then, we simply define

µ x,y (¬s; d F ) = d F (⟨µ x (ω 1 ), . . . , µ x (ω k )⟩, ⟨µ y (ω 1 ), . . . , µ y (ω k )⟩) (5a) µ x,y (s; d F ) = 1 -µ x,y (¬s; d F ). (5b)
Finally, by reference to the case of evidential clustering, we can remark that, if we interpret a soft clustering as describing our uncertainty in regard to some underlying (unknown) hard clustering, then two types of uncertainty can be distinguished. First, partial assignment, i.e., the existence of conflicting evidence supporting the assignment of an object x to two different clusters ω 1 and ω 2 , in which case we have m x ({ω 1 }) > 0 and m x ({ω 2 }) > 0. Second, ambiguity, i.e., the assignment of some mass to non-singleton events (i.e., m x (A) > 0 for some A ⊆ Ω such that |A| > 1), which describes our inability to exactly determine to which cluster an object belongs. It is easy to observe that fuzzy clustering only considers partial assignment, since all the mass is assigned to singletons. By contrast, in the case of rough clustering, only ambiguity is present.

Clustering Comparison Measures

Several measures have been defined to compare clusterings. We can distinguish between approaches that rely on the relational representation on the one hand, and on the object-based representation on the other hand. Here, we provide a survey of both families of measures for hard and soft clustering.

Relational-based Comparison Measures

Given two hard clusterings C 1 , C 2 , a sensible approach to compare them is to evaluate the number of pairs of objects (x, y) ∈ X 2 on which they agree. In particular, the Rand index is defined as the proportion of pairs of distinct objects that are either in the same cluster in C 1 and in the same cluster in C 2 , or in different clusters in C 1 and in different clusters in C 2 . Formally,

Rand(C 1 , C 2 ) = 2|{(x i , x j ) : 1 ≤ i < j ≤ n and [(x i , x j ) ∈ (A ∪ B c )]}| n(n -1) , (6)
where

A = [C 1 ]∩[C 2 ], B = [C 1 ]∪[C 2
] and (•) c is the complement operator. Other evaluation measures can be defined based on the same principle, including the Jaccard and Fowlkes-Mallows [START_REF] Fowlkes | A method for comparing two hierarchical clusterings[END_REF] indices. It is easy to show that these indices are similarities on hard clusterings, irrespective of their representation. Several extensions of the above mentioned indices to the soft clustering setting have been considered. In the case of fuzzy and possibilistic clustering, Campello et al. [START_REF] Campello | A fuzzy extension of the rand index and other related indexes for clustering and classification assessment[END_REF] proposed an approach based on extending the computation of Eq [START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithms[END_REF] to the fuzzy case, based on a t-norm ∧ and a t-conorm ∨. Similarly, Frigui et al [START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF] proposed an approach that is a special case of the formulation given by Campello et al., where ∧ = ⊗ P , ∨ = ⊕ P and only fuzzy clusterings are considered. This latter approach has also been generalized to the rough clustering setting [START_REF] Depaolini | External indices for rough clustering[END_REF], by means of a transformation from rough to fuzzy clustering. A potential flaw of the formulations proposed in [START_REF] Campello | A fuzzy extension of the rand index and other related indexes for clustering and classification assessment[END_REF][START_REF] Depaolini | External indices for rough clustering[END_REF][START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF] is that the corresponding measures fail to satisfy the properties mentioned in Section 1, hence they cannot be used to provide an objective comparison between two fuzzy or rough clusterings. In particular, since they fail to be pseudo-and semi-similarities, it can happen that Rand(F, F ) < 1 for some fuzzy clustering F . Consequently, the generalizations of the Rand index proposed in [START_REF] Campello | A fuzzy extension of the rand index and other related indexes for clustering and classification assessment[END_REF][START_REF] Depaolini | External indices for rough clustering[END_REF][START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF] cannot be directly applied to objectively compare the results of two fuzzy clustering algorithms since, even when the two algorithms report the same clustering, these measures could report a value smaller than 1, denoting a difference between them.

An alternative approach to generalize the Rand and Jaccard indices, for the case of fuzzy and possibilistic clustering, was proposed by Anderson et al. [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions[END_REF]. By adopting a matrix-based representation, the authors show that an equivalent (for the case of hard clustering) formulation of Eq (6) can be generalized to fuzzy and possibilistic clusterings, and can be computed in time O(n). Despite its favorable complexity, it has been shown that the obtained generalization of the Rand index has some non-intuitive properties. In particular, as the indices proposed in [START_REF] Campello | A fuzzy extension of the rand index and other related indexes for clustering and classification assessment[END_REF][START_REF] Depaolini | External indices for rough clustering[END_REF][START_REF] Frigui | Clustering and aggregation of relational data with applications to image database categorization[END_REF], it can fail to be a meta-similarity. Furthermore, its value is not restricted to the range [0, 1], and may even be negative: the absence of an absolute comparison scale thus makes the measure proposed in [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions[END_REF] hardly applicable for evaluating the quality of a fuzzy clustering with respect to a known ground truth, or for comparing the results of two different fuzzy clustering algorithms.

To address these limitations, for the case of the Rand index, a different approach was considered by Hüllermeier et al. [START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF]. This approach is based on an equivalent definition of the Rand index as

Rand(C 1 , C 2 ) = 2 n(n -1) 1≤i<j≤n 1 -|1 (xi,xj )∈[C1] -1 (xi,xj )∈[C2] |. (7)
Let d F be a normalized metric on [0, 1] Ω . Then, formula [START_REF] Bouveyron | Modelbased clustering and classification for data science: with applications in R[END_REF] for the Rand index can be generalized to fuzzy clustering as

Rand ′ F (P 1 , P 2 ) = 2 n(n -1) 1≤i<j≤n 1 -|µ xi,xj 1 (s; d F ) -µ xi,xj 2 (s; d F )|, (8)
where µ

xi,xj ℓ (s; d F ) for ℓ = 1, 2 are defined by [START_REF] Bassetti | On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows[END_REF]. In contrast with the previous measures, Rand ′ F is a similarity for the relational representation, and a pseudosimilarity for the object-based representation. If d F is the cosine distance, we obtain the approach proposed in [START_REF] Brouwer | Extending the Rand, adjusted Rand and Jaccard indices to fuzzy partitions[END_REF]. The approach proposed in [START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF] has been generalized to the case of evidential clustering by Denoeux et al. [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF]. Based on the relational representation of evidential clustering (see Section 2.2), the Rand index is expressed as:

Rand E (M 1 , M 2 ) = 2 n(n -1) 1≤i<j≤n 1 -d M (m xi,xj 1 , m xi,xj 2 ) ( 9
)
where d M is a normalized metric for mass functions. The authors consider, in particular, the Belief distance d B and Jousselme's distance d J , showing that the corresponding measures are pseudo-similarities for the object-based representation and similarities for the relational representation. Nonetheless, the authors of [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF] note that their approach is not completely satisfactory for the comparison of evidential clusterings, as d B does not distinguish between partial assignment and ambiguity, while d J penalizes ambiguity more than partial assignment.

Example 2.7. Let M be as in Example 2.3. Consider the pair of objects (x 2 , x 3 ), for which m x2,x3 (Ω) = 1. Furthermore, let M 1 be an evidential clustering such that m x2,x3 ({s}) = 1, and M 2 an evidential clustering such that

m x2,x3 ({s}) = m x2,x3 ({¬s}) = 0.5. Then, it holds that d B (m x2,x3 M , m x2,x3 M1 ) = d B (m x2,x3 M2 , m x2,x3
M1 ) = 0.5. Thus, Rand B does not distinguish between ambiguity and partial assignment. By contrast, it holds that

d J (m x2,x3 M , m x2,x3 M1 ) = 0.71 > 0.5 = d B (m x2,x3 M2 , m x2,x3 M1
). Thus, Rand J penalizes ambiguity more than partial assignment.

To address this issue, the authors of [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF] also propose an alternative generalization of the Rand index, based on the degree of conflict

K(m xi,xj 1 , m xi,xj 2 ) = A,B:A∩B=∅ m xi,xj 1 (A) • m xi,xj 2 (B).
The authors observe that the obtained measure, denoted as Rand K , is a consistency and suggest that a pair of measures (e.g., Rand B and Rand K ) could be used to obtain a comprehensive evaluation measure.

Object-based Comparison Measures

While the measures reviewed in Section 2.3.1 rely on the relational representation, different measures based on the object-based representation have also been proposed. This latter family of measures addresses a limitation of the previously mentioned relational representation-based measures, namely: let

M 1 , M 2 be two evidential clusterings such that M 1 ̸ = M 2 but [M 1 ] = [M 2 ]
(that is, the two clusterings are different w.r.t. the object-based representation but have identical relational representation); then, if d is a relational-based comparison measure, d(M 1 , M 2 ) = 0 (see also Corollary 4.1).

The partition distance [START_REF] Day | The complexity of computing metric distances between partitions[END_REF] for two hard clusterings C 1 , C 2 is defined as the minimum number of objects to be moved to transform

C 1 into C 2 (or, equiva- lently, C 2 into C 1 ). Assume, without loss of generality, that |Ω 1 | = |Ω 2 | (indeed, if |Ω 1 | ̸ = |Ω 2 |
, we can add empty clusters to the clustering with the smallest number of clusters). Then, the partition distance can be computed as

d π (C 1 , C 2 ) = 1 2(n -1) min τ k i=1 |ω 1 i ∆ω 2 τ (i) |, (10)
where τ is a permutation of {1, . . . , k}, ω j i is the i-th cluster in clustering C j , and ∆ is the symmetric difference operator. We can easily see that d π is a normalized metric: indeed, at most n -1 objects need to be moved between clusters to make the two clusterings equivalent and each moved object is counted twice; hence, the 2(n -1) factor in the denominator normalizes the range of d π .

An extension of the partition distance to the case of fuzzy clustering was proposed by Zhou [START_REF] Zhou | A new Mallows distance based metric for comparing clusterings[END_REF], based on the fact that the partition distance is a special case of the Wasserstein construction (see Eq. ( 2) in Section 2.1). The obtained measure is a proper generalization of the partition distance and is a metric. A similar approach was adopted by Anderson et al [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions using the earth mover's distance[END_REF], who proposed a generalization of the partition distance to fuzzy and possibilistic clusterings. While for the case of fuzzy clusterings the obtained measure is a metric, in the case of possibilistic clusterings the obtained measure is not even a meta-metric and may result in values greater than 1. Thus, it is subject to the same limitations as the generalization of the Rand index proposed in [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions[END_REF]. To our knowledge, the extension of the partition distance to rough and evidential clustering has not been considered in the literature.

A second family of object-based comparison measures is based on information theory [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF]. It includes the mutual information [START_REF] Vinh | Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance[END_REF] and the variation of information [START_REF] Meilȃ | Comparing clusterings-an information based distance[END_REF]. These approaches have been recently extended to the case of rough clustering in [START_REF] Campagner | Orthopartitions and soft clustering: soft mutual information measures for clustering validation[END_REF], based on the representation of a rough clustering R as a collection C(R) of compatible hard clusterings. Namely, the authors of [START_REF] Campagner | Orthopartitions and soft clustering: soft mutual information measures for clustering validation[END_REF] propose an interval-valued comparison measure representing the minimum and maximum values of mutual information among all pairs of hard clusterings compatible with the rough clusterings to be compared. To our knowledge, no extension of these metrics to the more general case of evidential clustering has been proposed so far.

A General Framework for Soft Clustering Evaluation Measures

As shown in the previous section, most of the research on comparison measures for soft clustering has focused on the analysis of some specific indices, while a general methodology for obtaining such measures is still missing. Furthermore, as noted in [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF], most of the existing methods fail to satisfy the metric properties described in Section 1. Consequently, they can hardly be used for the objective comparison of soft clusterings. Notably, the more principled approaches introduced in [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF] can also have some drawbacks, such as the inability to properly distinguish between different types of uncertainty arising in soft clustering.

In this section, we propose a general approach that attempts to address these limitations, based on the representation of a soft clustering as a mass function over hard clusterings. As already discussed in Section 1, this approach aims at addressing two different purposes of an evaluation measure for soft clustering, namely, uncertainty representation and objective comparison. In regard to the first aim, we will focus on interval-valued measures, as a compromise between succinctness and expressivity. Further, since a general soft clustering accounts for two different types of uncertainty (i.e., ambiguity and partial assignment), it seems reasonable to require any suitable measure to represent the full range of compatibility between two soft clusterings, varying with respect to how much we are willing to penalize ambiguity versus partial assignment. If we consider ambiguity to be completely acceptable, then the measure should quantify the compatibility between the two soft clusterings: under this constraint, the measure should arguably be a consistency, as previously discussed in [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF]. By contrast, when we consider ambiguity to be equivalent to an error, then the measure should quantify the exact equality between the two soft clusterings, and should hence be a metric (or, dually, a similarity).

In the following, we first introduce the distribution-based representation of soft clustering in Section 3.1. Then, we address the two above-mentioned aims for a soft clustering comparison measure by means of the transport-based measures (Section 3.2), which provide an objective interval-valued evaluation index based on the Wasserstein distance between two soft clusterings.

Distribution-based Representation of Soft Clustering

As mentioned at the beginning of this section, the approaches we propose are based on an alternative representation of soft clusterings as distributions over hard clusterings. Thus, intuitively, we assume that a soft clustering represents our uncertain knowledge about an underlying, unknown hard clustering.

As shown in Section 2.2, this is clearly true for the case of rough clustering: indeed, a rough clustering R can be represented as a set C(R) of hard clusterings C. Based on this observation, we extend this representation to general soft clusterings. Formally, given an evidential clustering M we define a mass function

m M as m M (R) = x∈X m x (R(x)), ( 11
)
where R is any rough clustering. That is, an evidential clustering is represented as a mass function over hard clusterings or, equivalently, as a probability distribution over rough clusterings. Given an evidential clustering M and its distribution-based representation m M , we denote by

F(M ) the collection of focal rough clusterings of m M , that is F(M ) = {R : m M (R) > 0}.
The distribution-based representation for rough, fuzzy and possibilistic clustering can then be obtained as a special case of Eq [START_REF] Day | The complexity of computing metric distances between partitions[END_REF]. Indeed, in the case of rough clustering, m M is logical (i.e., |F(m M )| = 1), while in the case of fuzzy clustering the focal rough clusterings are all singletons (i.e., hard clusterings). Finally, in the case of possibilistic clustering, the possibility distribution P oss P can equivalently be represented as a consonant mass function, i.e., the focal rough clusterings are nested. More precisely, given a fuzzy clustering F = {µ x } x , where µ x : Ω → [0, 1] is a probability distribution, we can represent it as the probability distribution on hard clusterings given by

P r F (C) = x∈X µ x (C(x)). ( 12
)
On the other hand, given a possibilistic clustering P and a t-norm ∧, we can view P as a possibility distribution over hard clusterings:

P oss P (C) = x∈X µ x (C(x)). ( 13
)
If ∧ is the product t-norm, we recover the case of fuzzy clustering.

Example 3.1. Let F, P, M be the soft clusterings defined in Examples 2.5 and 2.3. Then, P r F is defined as

P r F ((1, 2, 3, 3, 3)) = P r F ((1, 2, 3, 3, 2)) = P r F ((1, 2, 3, 3, 1)) = P r F ((1, 2, 2, 3, 3)) = P r F ((1, 2, 2, 3, 2)) = P r F ((1, 2, 3, 3, 1)) = 1 6 .
Similarly, P oss P is defined as

P oss P ((1, 2, 3, 3, 3)) = P oss P ((1, 2, 2, 3, 3)) = 0.8 P oss P ((1, 2, 3, 3, 2)) = P oss P ((1, 2, 3, 3, 1)) = 1 P oss P ((1, 2, 2, 3, 2)) = P oss P ((1, 2, 2, 3, 1)) = 1.
Finally, m M is defined as

m M ((1, 2, {2, 3}, 3, Ω)) = m M ((1, 2, Ω, 3, Ω)) = 0.25 m M ((1, 2, {2, 3}, 3, 1)) = m M ((1, 2, {2, 3}, 3, 2)) = m M ((1, 2, {2, 3}, 3, 3)) = 1 12 m M ((1, 2, Ω, 3, 1)) = m M ((1, 2, Ω, 3, 2)) = m M ((1, 2, Ω, 3, 3)) = 1 12 .
Based on the distribution-based representation, in the following section, we describe a general approach that can be used to extend a comparison measure between hard clusterings to a comparison measure between soft clusterings.

Transport-based Measures

In this section we introduce an approach to extend any clustering comparison metric to the case of soft clustering. This approach relies on the Wasserstein construction from Optimal Transport theory [START_REF] Villani | Topics in optimal transportation[END_REF] (see Section 2.1) to compute a distance between the distributional representations of the two soft clusterings to be compared. The metric properties we seek, then, directly follow from the constructions we employ.

To illustrate this idea, we recall that every evidential clustering (hence, every soft clustering) can be represented as a distribution over rough clusterings, as shown in Section 3.1. Hence, a comparison measure for soft clustering could be obtained by computing the cost of making the two distributions equivalent, by moving masses from one rough clustering to another, where the cost of such movements is determined by a base distance over rough clusterings. To define such measures, we will proceed in two steps: first, we will define a base distance over rough clusterings; then, we will extend this distance to general soft clustering using an approach based on the Wasserstein Distance.

Comparison between rough clusterings. Let d be a normalized distance over hard clusterings. Since, as mentioned in Section 1, we focus on interval-valued measures, we are interested in the definition of a pair of measures ⟨d l , d u ⟩, where 1 -d l is a consistency and d u is a metric (equivalently, 1 -d u is a similarity). Intuitively, d u should measure the equivalence between two rough clusterings by completely discounting ambiguity (i.e., treating ambiguity as if it was equivalent to an error). By contrast, 1-d l should measure the compatibility between two rough clusterings by determining whether they have a common disambiguation (i.e., a common assignment of objects to clusters). Let R 1 , R 2 be two rough clusterings and C(R 1 ), C(R 2 ) be the corresponding sets of compatible hard clusterings. We consider the following pair of measures:

d R 0 (R 1 , R 2 ) = min C1∈C(R1),C2∈C(R2) d(C 1 , C 2 ) (14a) d R 1 (R 1 , R 2 ) = d H (C(R 1 ), C(R 2 )). ( 14b
)
That is, d R 0 is the minimum possible distance obtained by considering the hard clusterings that are compatible with R 1 and R 2 , while d R 1 is the corresponding value of the Hausdorff distance

1 . It is easy to observe that d R 0 (R 1 , R 2 ) = 0 as long as there exists a hard clustering C that is compatible with both R 1 , R 2 . In contrast, d R 1 (R 1 , R 2 ) = 0 iff C(R 1 ) = C(R 2 )
. Furthermore, the following result directly follows from the definition of d R 0 , d R 1 :

Proposition 3.1. 1-d R 0 is a consistency, while d R 1 is a normalized metric (i.e., 1 -d R 1 is a similarity).
Proof. Clearly, d R 0 satisfies (M3). Similarly, d R 0 satisfies also (M1), while it fails to satisfy (M2). For the case of (M4), consider three rough clusterings

R 1 , R 2 , R 3 s.t. C(R 1 ) ∩ C(R 2 ) ̸ = ∅, C(R 2 ) ∩ C(R 3 ) ̸ = ∅, while C(R 1 ) ∩ C(R 3 ) = ∅. Then, clearly, d R
0 does not satisfy (M4). For the case of d R 1 , it suffices to note that d is a normalized metric and X is countable.

Thus, as a consequence of the previous result, d R 0 meets the requirement of not penalizing, but instead allowing and promoting ambiguity: indeed, two rough clusterings are considered equivalent as longs as they have a compatible hard clustering in common. By contrast, d R 1 fully penalizes ambiguity, equating it to an error in clustering assignment, by declaring two rough clusterings to be equivalent if and only if all their compatible hard clusterings coincide.

More generally, if we define

d R α = αd R 1 + (1 -α)d R 0 , for any α ∈ [0, 1]
, then the following result holds:

Theorem 3.1. Let α ∈ [0, 1]. Then: • If α ≥ 1 2 , d R α is a metric; • ∀ρ ≥ 1, if α ≥ 1 2ρ , d R α is a ρ-relaxed metric.
Proof. That d R α is symmetric (i.e., satisfies (M3)) is evident from the definition. Similarly, evidently for each α > 0 d R α satisfies (M1) and (M2). The result then follows from Example 2.2 and Lemma 2.3 in [START_REF] Xia | The geodesic problem in quasimetric spaces[END_REF].

Intuitively, d R α can be understood as an intermediate measure considering the relative cost associated to ambiguity to be α: that is, α can be interpreted as the ratio of the cost of ambiguity over the cost of error. Indeed, consider the case where we compare a rough clustering R with a hard clustering C. Then, if α = 0 it holds that d R α = d R 0 , which equals 0 as long as C ∈ C(R). This corresponds to assigning the cost of ambiguity to be equal to 0, since we ignore all

C ′ ∈ C(R) \ {C}. By contrast, if α = 1, then d R α = d R 1 , which equals 0 iff C(R) = {C}: in particular, if R 1 , R 2 are two rough clusterings with C(R 1 ) ⊂ C(R 2 ), then d R 1 (C, R 1 ) ≤ d R 1 (C, R 2 )
. Thus, when α = 1, the cost of ambiguity is equated to the cost of an error, as every assignment of objects to the boundary of a cluster is penalized to the same degree as the assignment to an incorrect cluster. More generally, α represents the trade-off between ambiguity and error that the specific user is willing to tolerate for the application at hand, and it should be set accordingly. Thus, a user who is willing to tolerate a certain degree of ambiguity (hence, a potentially larger number of objects assigned to the boundary of some cluster), in order to reduce the risk of clustering errors should set α closer to 0. This could make sense, for example, in medical applications where some degree of ambiguity could be tolerated if it avoids clustering together objects that correspond to patients associated with different clinical characteristics. Conversely, a user who prefers obtaining a clustering close to a hard one, and is willing to tolerate a potentially larger amount of cluster assignment errors, should set α closer to 1. Obviously, the previous discussion only provides guidelines to set the α parameter; its value should be carefully optimized to match the requirements of the application at hand. By contrast, both problems are in P if R 1 , R 2 are represented through the distribution-based representation. In this latter case, the complexity is o(k m ).

Proof. For the case of d R 0 , this can be obtained by a reduction to integer programming. Computing d R 1 (R 1 , R 2 ) is equivalent to computing the Hausdorff distance between C(R 1 ), C(R 2 ), which can be seen as a max-min 0-1 optimization problem. Since C(R 1 ), C(R 2 ) are finite, this can be transformed to a minmax 0-1 optimization problem, which is NP-HARD [START_REF] Ko | On the complexity of min-max optimization problems and their approximation[END_REF]. The second part of the theorem easily follows by noting that d R 0 , d R 1 can easily be computed by enumerating all elements in C(R 1 ), C(R 2 ). Finally, fixed parameter tractability of computing d R 0 , d R 1 derives from the two previous results.

To address the problem of computational hardness, several approximations will be described in Section 4.

Extension to general soft clusterings. The previous approach can be extended to the cases of fuzzy, possibilistic and evidential clustering, by noting that all these three forms of soft clusterings can be expressed as probability distributions over rough clusterings. For the case of evidential clustering, this has already been shown in Eq [START_REF] Day | The complexity of computing metric distances between partitions[END_REF]. For the case of fuzzy clustering, it follows from Eq (12) that any fuzzy clustering can be represented as a distribution over rough clusterings whose corresponding sets of compatible clusterings are singletons. Finally, the case for possibilistic clustering directly follows from the fact that a possibilistic clustering is an evidential clustering in which all mass functions are consonant. As a consequence, we can use an approach based on the Wasserstein Distance to extend d R 0 and d R 1 to evidential clustering. Namely, given two evidential clusterings M 1 , M 2 and their corresponding focal sets F(M 1 ), F(M 2 ), the general definition of the transport-based measure is given by

d E α (M 1 , M 2 ) = min σ (R1,R2)∈F (M1)×F (M2) σ(R 1 , R 2 )d R α (R 1 , R 2 ) (15)
s.t.

R2∈F (M2) σ(R 1 , R 2 ) = m M1 (R 1 ) R1∈F (M1) σ(R 1 , R 2 ) = m M2 (R 2 ) (R1,R2)∈F (M1)×F (M2) σ(R 1 , R 2 ) = 1 ∀(R 1 , R 2 ) ∈ F(M 1 ) × F(M 2 ), σ(R 1 , R 2 ) ≥ 0.
Intuitively, the transport-based measure based on d R α can be interpreted as the minimal cost of transforming the mass function over hard clusterings described by M 1 into the mass function described by M 2 . This cost is computed by finding the joint mass function whose marginals are equal to M 1 and M 2 , and which minimizes the expected value of d R α (R 1 , R 2 ). Due to the properties of the Wasserstein distance, it is easy to show that the following properties hold:

Theorem 3.2. Let α ∈ [0, 1]. Then, • If α ≥ 1 2 , d E α is a metric; • ∀ρ ≥ 1, if α ≥ 1 2ρ , d E α is a ρ-relaxed metric; • 1 -d E 0 is a consistency.
Proof. The result is a direct consequence of Theorem 3.1 and the properties of the Wasserstein distance.

Corollary 3.1. Let F 1 , F 2 be two fuzzy clusterings. Then,

∀α 1 , α 2 ∈ [0, 1] it holds that d E α1 (F 1 , F 2 ) = d E α2 (F 1 , F 2 ).
Proof. The result directly follows from the observation that, for a fuzzy clustering F the focal sets of m F are all singletons.

As d R α for rough clusterings, d E α can be used as an objective comparison measure for evidential clusterings. In particular, 1 -d E 0 provides a measure of consistency between two evidential clusterings, while d E 1 can be understood as an equality index for evidential clustering. Moreover, as previously discussed, d E α , with α ∈ [0, 1], can be interpreted as a measure of compatibility between two evidential clusterings, where the relative cost of ambiguity is exactly α. The transport-based measure generalizes the previous proposals in [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF], by providing a general framework to extend any hard clustering comparison measure to the setting of soft clustering, thus enabling the direct comparison of any two soft clusterings, irrespective of their representation (either relational-based or object-based) and class (based either on rough, fuzzy, possibilistic or evidential clustering). Furthermore, it also allows a more flexible trade-off between ambiguity and partial assignment or clustering errors, by controlling the ambiguity parameter α.

• For all α ∈ [0, 1] d E α (C, F ) = 0.267; • d E 0 (C, P ) = 0, d E 1 (C, P ) = 0.48; • d E 0 (C, M ) = 1 12 , d E 1 (C, M ) = 0.442. If, instead, we let d = d π we obtain: • For all α ∈ [0, 1] d E α (C, F ) = 0.23; • d E 0 (C, P ) = 0, d E 1 (C, P ) = 0.4; • d E 0 (C, M ) = 0.07, d E 1 (C, M ) = 0.37.
In regard to the computational complexity, since the problem of computing d R 0 , d R 1 is already computationally hard, it is evident that the problem of computing d E α is also computationally hard. An interesting problem, however, would be to determine whether, at least for the case of fuzzy clustering, a computationally efficient algorithm exists for solving Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF]. We leave this problem for future work. In the following section, however, we show that d E 0 and d E 1 can be efficiently bounded by means of a polynomial-time algorithm in the cases of the Rand index and the partition distance.

As a last result in this section, we study the special case where one of the clusterings to be compared is a hard clustering C. This case is particularly interesting, since it frequently arises in applications. Indeed, in many cases, e.g., when one wants to test a novel soft clustering algorithm, one uses an existing ground truth clustering C as a reference for comparison. The following theorem shows that, in this particular case, the interval-valued transport-based measure between C and an evidential clustering M can be interpreted as the lower and upper expectations of the distance between C and the unknown hard clustering partially specified by M : Theorem 3.3. Let M, C be, respectively, an evidential clustering and a hard clustering. Let d be a normalized metric over hard clusterings, and let E(d), E(d) be the lower/upper expectation of d with respect to m M . Then

d E 0 (M, C) = E(d), d E 1 (M, C) = E(d).
Proof. First, we note that for all R ∈ F(M ), it is easy to observe that under the conditions stated in the Theorem it holds that d

R 1 = max C ′ ∈C(R) d(C, C ′ ). Since C is a hard clustering, m C ({C}) = 1.
Therefore, the result follows by noting that Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF] reduces to the expectation, with respect to m M , of d R α .

Approximation Methods

In the previous section, we proposed a general approach, the transport-based measures, to extend hard clustering comparison measures to the case of soft clustering. This approach can be used to obtain objective comparison criteria, by applying the Wasserstein construction to the distribution-based representation of the soft clusterings to be compared. Nonetheless, the computation of the transport-based measure is generally intractable. For this reason, in this section, we introduce some approximation methods and algorithms. First, in Section 4.1, we describe a general approach based on sampling, which can be applied to any base distance between hard clusterings. In Sections 4.2 and 4.3, we then discuss generalizations of the Rand index and the partition distance, as representatives, respectively, of relational-based and object-based comparison measures, and we show that they can be used to approximate the transport-based measure.

Sampling-based Approximation Algorithms

In this section, we provide a general sampling-based approach that can be used to approximate the value of d E α . We start with the case of rough clustering, that is with d R 0 , d R 1 . Assume that, given two rough clusterings R 1 and R 2 , we draw s samples (C

= d H ({C i 1 } s i=1 , {C i 2 } s i=1
). It is easy to show that the following result holds:

Proposition 4.1. The following bounds hold for any t > 0:

P r(d R 1 -dR 1 > ϵ) ≤ F (d R 1 -ϵ) s (16a) P r( dR 0 -d R 0 > ϵ) ≤ 1 -1 -F (ϵ -d R 0 ) s , ( 16b
)
where F is the cumulative distribution function (CDF) of the probability distribution p R defined as

p R (t) = |{C 1 ∈ C(R 1 ), C 2 ∈ C(R 2 ) : d(C 1 , C 2 ) = t}| |d R (R 1 , R 2 )| . ( 17
)
Noting that

F (d R 1 -t) (resp., F (t -d R 1
)) is stricly less than 1, it holds that, for each ϵ, P r(d R 1 -dR 1 > ϵ) (resp. P r( dR 0 -d R 0 > ϵ)) has exponential decay in the size of the sample s.

Proof. The result directly follows from the distribution of the order statistics dR 0 , dR 1 .

Thus, even though computing ⟨d R 0 , d R 1 ⟩ is computationally hard, we can obtain good approximations of its value by a simple sampling procedure that can be easily implemented in polynomial time.

Remark. We note that, despite the previous bounds, the quality of the approximation largely depends on p R (t). In particular, the convergence in Eq (16) is correlated with the tailedness of p R defined in Eq [START_REF] Denoeux | Evidential clustering: a review[END_REF]: the heavier the tails of p R , the lower the approximation error. This can be directly understood by looking at the bounds in Eq. ( 16): indeed, if the tails of p R are thin, than F (d R 1 -ϵ) will be close to 1, thus resulting in a large approximation error.

The problem mentioned in the previous remark can be illustrated through the following example. However, the probability distribution p R will be concentrated around the expected value of 1 -Rand under the uniform distribution [START_REF] Steinley | A note on the expected value of the rand index[END_REF]. Consequently, dR 0 and dR 1 will also be close to this value with high probability. For the case of fuzzy clustering, let

d F1,F2 (v) = C1,C2:d(C1,C2)=v P r F1 (C 1 ) • P r F2 (C 2 ).
If we use a sampling procedure to estimate d E α (F 1 , F 2 ), we can obtain a stronger tail bound by applying Hoeffding's inequality: Proposition 4.2. Assume that d is a normalized metric on hard clusterings, and F 1 , F 2 are two fuzzy clusterings. Then,

P r(| dE α (F 1 , F 2 ) -d E α (F 1 , F 2 )| ≥ ϵ) ≤ 2e -2sϵ 2 . ( 18
)
Hence, the deviation has exponential decay in the size of the sample s.

Combining Eqs ( 16) and ( 18), an analogous result can be found also for the case of d E α . Indeed, we obtain: Proposition 4.3. Assume that d is a normalized metric on hard clusterings. Let dE 0 , dE 0 be the sample estimates of d E 0 , d E 1 . Then:

P r(| dE 0 -d E 0 | ≥ ϵ) ≤ 2e -2sϵ 2 (19a) P r(| dE 1 -d E 1 | ≥ ϵ) ≤ 2e -2sϵ 2 . ( 19b
)
The previous bound, however, assumes that dE 0 , dE 1 are computed by sampling pairs R 1 , R 2 of rough clusterings from the distributions m M1 , m M2 and then computing the exact values of

d R 0 (R 1 , R 2 ), d R 1 (R 1 , R 2 ).
As a consequence of Proposition 3.2, this may not be feasible when |X| is large. In such cases, a possible solution would be to compute dE 0 , dE 1 using a nested sampling procedure (i.e, first we sample a rough clustering R from m M , then we sample a hard clustering C from C(R)). In this case, however, one should expect a larger approximation error as a consequence of our previous remarks.

Finally, we note that all the above mentioned sampling-based approximation methods can easily be implemented in polynomial time, more precisely with time complexity O(n 2 s + s 3 log s), where n = |X| and s is the sample size. In particular, the cost of sampling is Θ(n 2 s), while the cost of computing the approximated transport-based distance is O(s 3 log s) [START_REF] Bassetti | On the computation of Kantorovich-Wasserstein distances between two-dimensional histograms by uncapacitated minimum cost flows[END_REF].

Bounds for the Transport-based Rand Index

In this section, we discuss a generalization of the Rand index to evidential clustering that can be computed in polynomial time. Remarkably, we will show that this alternative definition allows us to bound the transport-based measure, when we assume as base distance

d(C 1 , C 2 ) = 1 -Rand(C 1 , C 2 ).
The approach described in this section is based on the following observation: the hardness of computing the transport-based measure derives from it being defined as the Wasserstein distance between two probability distributions whose supports have size that is exponential in the size of the original soft clusterings. Thus, intuitively, the complexity could be reduced if, instead of computing the Wasserstein distance between the distributional representations of the two soft clusterings to be compared, this computation would be pushed inside the formula of the Rand index.

This intuition can be formalized by noting that the Rand Index can be seen as an instance of the Wasserstein metric. Indeed, consider two objects x, y and two hard clusterings C 1 , C 2 . Using the relational representation, which is the only information used to compute the Rand index, we can represent the hard clusterings as point masses p denote whether objects x i and x j are in the same cluster (in which case p xi,xj (s) = 1) or not (in which case p xi,xj (¬s) = 1), for hard clusterings C 1 , C 2 . Then, the Rand index can be expressed as

Rand(C 1 , C 2 ) = 2 n(n -1) 1≤i<j≤n 1 -r xi,xj , (20)
where

r xi,xj = min σ (a,b)∈Ω 2 σ(a, b)d(a, b) (21)
s.t. b∈Ω σ(a, b) = p xi,xj 1 (a) a∈Ω σ(a, b) = p xi,xj 2 (b) (a,b)∈Ω 2 σ(a, b) = 1 ∀(a, b) ∈ Ω 2 , σ(a, b) ≥ 0, with d(a, b) = 1 a̸ =b .
It can be easily seen that

r xi,xj = |p xi,xj 1 (s) -p xi,xj 2
(s)| = |p xi,xj 1 (¬s) - p xi,xj 2
(¬s)|, which coincides with Eq [START_REF] Bouveyron | Modelbased clustering and classification for data science: with applications in R[END_REF]. We note that the same approach can be equivalently applied to probabilistic and fuzzy clusterings, by simply relaxing the requirement that p (¬s)|. Thus, the approach proposed in [START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF] can be derived as a special case to our definition.

To extend the above approach to evidential clustering, we must consider a generalization of the metric d to sets on Θ. If we apply Eq [START_REF] Denoeux | Calibrated model-based evidential clustering using bootstrapping[END_REF] to the case where A, B ⊆ Θ we obtain

d 0 (A, B) = 1 A̸ =B∧A∩B=∅ (22a) d 1 (A, B) = 1 A̸ =B (22b) d α (A, B) = αd R 1 (A, B) + (1 -α)d R 0 (A, B). ( 22c
)
As shown in Section 3.2, d 1 is a metric, while 1 -d 0 is a consistency.

Based on d α we can generalize Eq [START_REF] Denoeux | EVCLUS: evidential clustering of proximity data[END_REF] to evidential clustering, obtaining

r xi,xj α = min m (A,B)∈2 Θ ×2 Θ m(A, B)d α (A, B) (23)
s.t. B∈2 Θ m(A, B) = m xi,xj 1 (A) A∈2 Θ m(A, B) = m xi,xj 2 (B) A,B∈2 Θ m(A, B) = 1 ∀A, B ∈ 2 Θ , m(A, B) ≥ 0,
where α ∈ [0, 1] represents, as in the previous sections, the relative cost of ambiguity with respect to the cost of error. The α-Rand index can then be defined as follows. be defined as above. Then,

Rand α (M 1 , M 2 ) = 2 n(n -1) 1≤i<j≤n 1 -r xi,xj α . ( 24
)
We note that, in general, α 1 ≤ α 2 =⇒ Rand α2 ≤ Rand α1 . Thus, in particular Rand 1 ≤ Rand 0 . Furthermore, in regard to the computational complexity, since the size of the frame Θ is constant, r xi,xj α can be computed for each pair (x i , x j ) ∈ X 2 in time O [START_REF] Ahmed | A survey of network anomaly detection techniques[END_REF]. Therefore, Rand α can be computed in time O(n 2 ). We note that only for the cases of Rand 0 (C, R) and Rand 0 (C, P ) does the value of the approximation coincide with the exact solution of Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF], which was computed in Examples 3.2, 3.3.

As a first result, we characterize the relationship between Rand α and Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF], showing that Rand α allows to bound the value of the latter when d = 1 -Rand:

Theorem 4.1. Let d E 0 , d E
1 be defined as in Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF], by setting d = 1 -Rand.

Then Rand 1 ≤ 1 -d E 0 ≤ Rand 0 and 1 -d E 1 ≤ 1 -d E 0 ≤ Rand 0 .
Proof. We first prove the inequality 1 Proof. The result can be easily obtained by noting that d 0 , d α , d 1 are all equivalent when restricted to {s, ¬s}.

-d E 0 ≤ Rand 0 . First, assume that M 1 , M 2 are both rough clusterings. Then d R 0 is obtained by choosing two clusterings C 1 , C 2 s.t. C 1 ∈ C(M 1 ), C 2 ∈ C(M 2 ) and d(C 1 , C 2 ) = 1-max C ′ 1 ,C ′ 2 Rand(C 1 , C 2 ). Let x i , x j , with i < j,
In terms of metric properties, the following result holds: Theorem 4.3. Assume that evidential clusterings are represented through the relational representation, and α ∈ [0, 1]. Then,

• If α ≥ 1 2 , Rand α is a similarity; • Rand 0 is a consistency; • ∀ρ ≥ 1, if α ≥ 1 2ρ , 1 -Rand α is a ρ-relaxed metric.
Proof. These claims directly derives from the properties of d α (see Theorem 3.1) and the definition of the Wasserstein distance.

By contrast, if we consider the object-based representation, then Rand α is, at most, a pseudo-similarity:

• If α ≥ 1 2 , Rand α is a pseudo-similarity; • ∀ρ ≥ 1, if α ≥ 1 2ρ , 1 -Rand α is a ρ-relaxed pseudo-metric. Proof.
To show that the claim holds, it is sufficient to observe that the map from the object-based representation to the relational representation is not injective. Indeed, as long as n < 2 k -1, to any possible m xi,xj may correspond infinitely many evidential clusterings M , since the associated multi-linear system (given by Eq (3)) is under-determined. Then clearly, for any two such M 1 , M 2 it holds that 1 -Rand α (M 1 , M 2 ) = 0. Thus, combining this result with Theorem 4.3, the claim follows.

Remark. The proof of Corollary 4.1 suggests the conjecture that Rand α may be a similarity also in terms of the relational representation, if we require n ≥ 2 k -1. While it can be easily shown by direct algebraic manipulation that this property indeed holds when k = 2, we leave the proof of this conjecture in the general case as future work.

We have seen that the cost of computing Rand α is O(n 2 ). While in general, computing the Wasserstein distance requires solving a linear programming problem, when m 1 , m 2 are normalized, for the special cases of r we can find a closed-form solution. In particular, we have the following theorem. (∅) = 0). Then:

r xi,xj 0 = 1 2 |m xi,xj 1 (s) + m xi,xj 2 (¬s) -1|+ |m xi,xj 1 (¬s) + m xi,xj 2 (s) -1| -m 1 (Θ) -m 2 (Θ)] r xi,xj 1 = 1 2 A⊆Θ |m xi,xj 1 (A) -m xi,xj 2 (A)| r xi,xj 0.5 = 1 2 |Bel xi,xj 1 (s) -Bel xi,xj 2
(s)| + |Bel xi,xj 1 (¬s) -Bel xi,xj 2 (¬s)| . Proof. Consider first r xi,xj 1
. By the definition of the Wasserstein distance and Θ, the optimal assignment is given by setting for each A ⊆ Θ m(A, A) = min{m (A)} -m(A, A), from which the formula in the theorem directly follows. For the case of r xi,xj 0.5 , we note that the optimal assignment is given by any joint mass function that maximizes

A⊆Θ m(A, A) + m(A,Θ)+m(Θ,A) setting m(A, A) = min{m xi,xj 1 (A), m xi,xj 2
(A)}, then allocating masses to sets of the form m(A, Θ), m(Θ, A), and then arbitrarily allocating the remaining mass satisfies the above mentioned maximization problem. The result then easily follows from the same arguments used for r xi,xj 1

. Finally, for the case of r xi,xj 0 we note that optimal assignment is given by any joint mass function m that maximizes A⊆Θ m(A, A) + m(A, Θ) + m(Θ, A). In particular, for any such mass function, r

xi,xj 0 = 1 iff m xi,xj 1 (A) = m xi,xj 2 (A c ) = 1, while r xi,xj 0 = 0 iff m xi,xj 1 (A)+m xi,xj 1 (Θ) = m xi,xj 2 (A)+m xi,xj 2
(Θ) = 1, for some A ⊆ Θ. The same assignment described for the case of r xi,xj 0.5 satisfies the above mentioned properties. The result then follows from algebraic manipulations and the definition of the Wasserstein distance.

Finally, as a consequence of the previous result, we obtain the following corollary.

Corollary 4.2. Let M 1 , M 2 be two evidential clusterings such that, for each pair of objects x i , x j ∈ X, m are normalized. Then, Rand 0.5 = Rand B , where Rand B is obtained by using the belief distance [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF] in Eq (9). This result explains why Rand B , defined in [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF], was found to be unable to distinguish ambiguity from partial assignment and provides an intuitive interpretation of Rand α . Indeed, as previously mentioned in Section 3.2, α can be interpreted as the (relative) cost of ambiguity. Therefore, as a consequence of Theorem 4.3, Rand B is equivalent to the case where the cost of ambiguity is α = 0.5, i.e., the same cost assigned to a uniformly randomized assignment of objects to clusters. Indeed, let m 1 be a logical mass function, and let m 2 (Ω) = 1 and m ′ 2 (s) = m ′ 2 (¬s) = 1 2 . Then, in both cases, Rand 0.5 = 1 2 . By contrast, it is easy to observe that Rand 0 conflates ambiguity and correctness: indeed, for the previous example we have Rand 0 = 1 for m 1 and m 2 . Finally, Rand 1 conflates ambiguity and error: for m 1 and m 2 , we have Rand 1 = 0. Thus, in conclusion: if we let α vary in (0, 0.5) we obtain a measure in which ambiguity interpolates between correctness and uncertainty, while if we let α vary in (0.5, 1) we obtain a measure in which ambiguity interpolates between partial assignment and error.

Bounds for the Transport-based Partition Distance

In this section, we discuss a generalized version of the partition distance which satisfies the properties we required for a comparison measure between soft clusterings. As for the Rand index, this generalization of the partition distance can be computed in polynomial time and can be used to bound the value of the transport-based measure defined in Section 3.2, when the base distance is d π (that is, the partition distance between hard clusterings).

As in the previous section, the main idea underlying the bounding approach is to push the computation of the Wasserstein distance inside the definition of the partition distance. For this purpose, we note that the partition distance can be formulated equivalently as

δ C (C 1 , C 2 ) = min w 1 2(|X| -1) k i=1 x∈X ∆(χ ω i 1 (x), χ ω w(i) 2 (x)), (25)
where χ ω (•) is the indicator function corresponding to cluster ω, and

∆(χ ω i 1 (x), χ ω w(i) 2 (x)) = |χ ω i 1 (x) -χ ω w(i) 2 (x)|
is the symmetric difference operator on indicator functions. We note that this approach cannot be directly extended to the case of evidential clustering, since an evidential clustering M is usually represented as a collection of functions {m x } x∈X , where m x : 2 Ω → [0, 1], while the formulation in Eq (25) would require a collection of functions {m ω } ω∈Ω , with m ω : X → [0, 1]. Nonetheless, the desired representation can be obtained by means of a change of frame. Indeed, for each cluster ω ∈ Ω, we consider the frame Θ ω = {ω, ¬ω} and the restriction of m x to Θ ω given by

m C↓Θω x ({ω}) = m x (ω) (26) m C↓Θω x ({¬ω})
= ∅̸ =A⊆Ω:ω / ∈A m x (A) (27) m C↓Θω
x

(Θ ω ) = A⊆Ω:{ω}⊂A m x (A) (28)
m C↓Θω x (∅) = m x (∅). (29)
If we define m ω (x) = m C↓Θω x ({ω}), then a generalization of the operator ∆ to the case of evidential clustering can easily be obtained as a solution to the Wasserstein problem, by assuming a base distance on Θ ω . If we assume the same base distances on Θ ω as given in Eqs [START_REF] D'urso | Informational paradigm, management of uncertainty and theoretical formalisms in the clustering framework: A review[END_REF], then ∆ can be computed as a solution to the optimal transport problem, obtaining the same formulation as in Theorem 4.4. Based on the definition of ∆ α , we can generalize Eq [START_REF] Gagolewski | Are cluster validity measures (in) valid?[END_REF] to the case of evidential clustering as

δ E α (M 1 , M 2 ) = min τ 1 2(n -1) k i=1 x∈X ∆ α m C↓Θ ω i 1 x , m C↓Θ ω τ (i) 2 x , (30)
where ∆ α (m 1 , m 2 ) is the distance function between mass functions that we previously defined, and τ is a permutation of {1, . . . , k}. We can remark that, when M 1 and M 2 are hard clusterings, then Eq (30) is equivalent to Eq (25), hence the former is a generalization of the partition distance to evidential clustering. Then, we characterize the relation between δ E α and transport-based measure when d = d π . As for the Rand index, we show that the measure defined in this section can be used to provide bounds for the transport-based measure: Theorem 4.5. Let d E 0 , d E 1 be defined as in Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF], by setting d to be the partition distance

d π . Then δ E 0 ≤ d E 0 ≤ δ E 1 and δ E 0 ≤ d E 0 ≤ d E 1 .
the method discussed in this section and the one introduced in Section 4.2 are quite different. Indeed, the method for the Rand index discussed in Section 4.2 has complexity which is quadratic in the number of objects, i.e., O(n 2 ). By contrast, the generalization of the partition distance introduced in this section has complexity which scales as O(n2 k + k 3 ). This means that, since in general k ≪ n, computing the (approximated) partition distance can be expected to be more computationally efficient than computing the (approximated) Rand index. Interestingly, it is easy to show that the approach proposed in [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions using the earth mover's distance[END_REF][START_REF] Zhou | A new Mallows distance based metric for comparing clusterings[END_REF] arises as a special case of our definition:

Proposition 4.5. Let F 1 , F 2 two fuzzy clusterings. Then, for each α ∈ [0, 1] δ E α (F 1 , F 2 ) = d F π (F 1 , F 2 ). Proof.
In the case of fuzzy clustering we have that, for each pair of clusters

ω 1 , ω 2 , ∆ α = m C↓Θω 1 x , m C↓Θω 2 x = |ω 1 (x) -ω 2 (x)|.
The result then follows from the definition of the fuzzy partition distance given in [START_REF] Anderson | Comparing fuzzy, probabilistic, and possibilistic partitions using the earth mover's distance[END_REF][START_REF] Zhou | A new Mallows distance based metric for comparing clusterings[END_REF].

Illustrative Experiments

In this section, we discuss two simple experiments, with the aim of illustrating the application of the proposed approach and the corresponding approximation methods. In particular, in the first experiment reported in Section 5.1, we compare five different clustering algorithms (based on the k-means clustering procedure) on a small-dimensional benchmark dataset, and we illustrate the computation of the metrics defined in Section 3, as well as its approximations introduced in Section 4. In Section 5.2, we then show through a second experiment how even for a moderately large dataset the approximations defined in Section 4 can be computed in reasonable time, and how this information can be used to bound model performance, even when the transport-based measure cannot be computed.

Iris Data

In the first experiment, we provide a simple illustration of the proposed metrics using the Iris dataset, a small-scale benchmark problem with 150 objects, four numerical features and three classes, each of which containing 50 instances. We selected this dataset as it is widely known that the three above mentioned classes are approximately linearly separable (see Figure 1). Thus, we expect any soft clustering algorithm to be able to find a clustering of the data in which most objects are precisely assigned to a single cluster. We note that, as a consequence of Theorem 3.2, this is a necessary condition for the exact versions of our proposed metrics to be computable in a reasonable time. The Iris dataset was selected specifically to allow direct computation of the exact metrics proposed in Section 3.2, without incurring running time-related bottlenecks.

For the purpose of our experiment, we considered five different clustering algorithms, all in the k-means family of algorithms. Namely, we considered: kmeans (KM), rough k-means (RKM) [START_REF] Peters | Rough clustering utilizing the principle of indifference[END_REF], fuzzy c-means (FCM) [START_REF] Bezdek | Pattern recognition with fuzzy objective function algorithms[END_REF], possibilistic c-means (PCM) [START_REF] Krishnapuram | A possibilistic approach to clustering[END_REF] and evidential c-means (ECM) [START_REF] Masson | ECM: an evidential version of the fuzzy c-means algorithm[END_REF]. For all algorithms, in order to reduce the computational complexity of computing the exact value of the measures, we set the hyper-parameters so as to obtain a soft clustering as close as possible to a hard one. In particular, for RKM we set ϵ = 1.1, for FCM and PCM we set m = 5, and for ECM we set δ = 10, β = 5, α ECM = 5. We compared the output of each algorithm with the ground truth labeling of the Iris dataset. We considered, in particular, the following metrics:

• The transport-based Rand index (T-RI);

• The transport-based partition distance (T-PD);

• The sampling-based approximations (S-RI, S-PD) of the two previous measures (see Section 4.1). The sampling-based approximations were computed based on drawing 1000 samples with replacement;

• The bounds on the Rand index (A-RI) (see Section 4.2);

• The bounds on the partition distance (A-PD) (see Section 4.3).

For all metrics, the ambiguity parameter α was set to 0.5, to obtain a balanced trade-off between ambiguity and error, with the former having half the weight of the latter. All code was implemented in Python (v. 3.8.8), using the scikit-learn (v. 0.24.1), numpy (v. 1.20.1) and scipy (v. 1.6.2) libraries2 . In particular, in the implementation of T-RI and S-RI we used as sub-routine the scikit-learn implementation of the Rand index (which has complexity O(n), where n is the number of objects), while for T-PD, S-PD, A-RI and A-PD we used custom implementations based on the algorithms described in the previous sections (in particular, we note that the complexity of A-RI is O(n 2 )). As mentioned previously, the exact transport-based measures T-RI and T-PD were computed by direct application of their definitions given in Section 3.2. This direct computation is made possible by the fact that the classes of the Iris datasets are approximately linearly separable. Indeed, even though, as claimed in Theorem 3.2, the complexity of doing so is in general exponential in the number of clusters and the number of ambiguous objects, computing T-RI and T-PD is feasible when these quantities are small, as the corresponding problems are fixed-parameter tractable.

The results of the experiment are reported in Table 2, in terms of the metrics values as well as the running time (in seconds). As shown in the table, the approximation algorithms (both the sampling-based algorithms, as well as the ad hoc algorithms for the Rand index and the partition distance) were much more efficient than the exact versions of the metrics, for all algorithms except RKM, in which the ad hoc approximation algorithms reported worse running time than the exact versions. This follows from the observation that the result of RKM was very close to a hard clustering, with only two objects not assigned to a precise cluster. The difference in performance then follows by noting that the scikit-learn implementation of the Rand index has time complexity O(n), while A-RI has time complexity O(n 2 ).

In terms of running time, we can observe that the cost of computing the exact versions of the proposed measures sharply increases when considering more general soft clustering algorithms. Indeed, the running time of T-RI and T-PD for ECM were approximately twice the respective running times for either FCM and PCM. On the other hand, the differences in running times for the approximation algorithms (S-RI, S-PD, A-RI, A-PD) were much smaller, and indeed the running times for FCM, PCM and ECM were similar.

In terms of approximation quality, even though for RKM and FCM there were no differences between the sampling-based (i.e., S-RI, S-PD) and the ad hoc algorithms (i.e., A-RI, A-PD), this was not the case for PCM and ECM. In these latter cases, the ad hoc algorithms reported lower approximation error than the sampling-based ones. This observation can be understood as a consequence of the remark in Section 4.1, in which we discussed the quality of approximation of the sampling-based algorithms. Thus, although the samplingbased methods have explicit bounds on the approximation error, the ad hoc algorithms introduced in Section 4.2 and 4.3 may yield a lower empirical approximation error in practical scenarios, as shown in this illustrative example. In particular, we note that the sampling-based approach systematically underestimated the uncertainty in clustering comparison results, by producing intervals that were narrower than those obtained by means of the ad hoc approximation algorithms. Nonetheless, both approximation methods provided consistent results, in the sense that smaller values according to one method were associated with smaller values according to the other one.

In regard to the performance of the applied clustering algorithms, we note that the proposed metrics allow a comparison of these results. For example, it could be noted that, according to all metrics, RKM reported soft clusterings that were associated with a much smaller amount of uncertainty than both PCM and ECM, which instead reported comparable results in this sense. Notably, while both RKM and FCM yielded results very similar to those obtained with the hard clustering algorithm KM, by contrast both PCM and ECM yielded slightly higher values for the upper bound values of the metrics. This observation shows that the additional amount of ambiguity and uncertainty introduced by these algorithms allowed to retrieve compatible hard clusterings closer to the ground truth class assignment than those compatible with either RKM and FCM. Nonetheless, we note that, in general, the lower bound values reported by RKM were comparable with, or better than, those reported by PCM and ECM. We can deduce from this observation that, in general, RKM may achieve results comparable to PCM and ECM in terms of accuracy, while producing, at the same time, soft clusterings having a much smaller degree of uncertainty.

Simulated data

In the second experiment, our aim is to illustrate how, even on moderately large datasets (on which the exact transport-based measure cannot be computed feasibly, as a consequence of Theorem 3.2), the approximate measures proposed in Section 4 can still be applied and used to obtain indications about the performance of different clustering algorithms, as well as to perform a comparison between their results. To this aim, we considered a synthetically-generated dataset composed of 10,000 objects and two features. Each of the objects was classified into three different classes, generated by drawing from a mixture of Gaussian distributions with a large probability of overlap, as illustrated in Figure 2.

As in the previous experiment, we applied the KM, RKM, FCM, PCM and ECM algorithms to the dataset, and we compared the results obtained by each of these algorithms with the ground-truth partition. Furthermore, we also compared the clusterings obtained by each pair of algorithms, to evaluate their results. We considered, in particular the S-RI, A-RI, S-PD and A-PD measures (see Section 5.1). As in the first experiment, for all metrics, the value of the ambiguity weight α was set to 0.5. Similarly, the sampling-based approximation measures S-RI and S-PD were computed based on the drawing of 1000 samples with replacement. In order to visualize the pairwise measure values graphically (for increased readability), we applied the multi-dimensional scaling algorithm for interval-valued data described in [START_REF] Denoeux | Multidimensional scaling of interval-valued dissimilarity data[END_REF].

The results of the experiment are reported in Figures 3 and4. As in the first experiment, we note that the sampling-based approximation methods severely under-estimated the uncertainty as compared to the ad hoc algorithms. Indeed, as shown in Figures 3 and4, the size of the circle-based representations associated with the sampling-based approaches were much smaller. This result highlights how the sampling process that underlies the computation of S-RI and S-PD might lead to an underestimation of the degree of ambiguity as compared to A-RI and A-PD, likely due to the fact that a limited amount of samples does not allow us to extensively explore the space of compatible hard clusterings. Nonetheless, despite these differences, the results of the two approximation methods were aligned, for both the Rand index and the partition distance. Indeed, in all cases, the RKM and KM algorithms were more similar to the ground truth and to each other than the remaining clustering algorithms. According to all the considered metrics, the circle-based representation of RKM was always very close to that corresponding to KM, and was also the closest one to the ground truth.

This result, together with the results of the first experiment, highlights the efficiency of the RKM algorithm, which, by allowing a limited degree of ambiguity in the assignment of objects to clusters, makes it possible to retrieve the ground truth separation of objects into classes with an higher accuracy as compared to other methods, reporting results similar to, but slightly better than, the hard clustering algorithm KM. Similarly, the ECM and PCM algorithms were found to be relatively similar according to all computed metrics, and similarly associated with a larger amount of ambiguity compared to all the other clustering algorithms. In particular, according to all the considered metrics, PCM was the algorithm that generated the clusters associated with the great-est amount of uncertainty. This result suggests that, at least for this simulated dataset, ECM might be preferable to PCM as it yields similar results in terms of accuracy (i.e., closeness to the ground truth) with, at the same time, a smaller amount of ambiguity. Nonetheless, this finding needs to be confirmed by further experiments, as it was not observed in the first experiment on the Iris dataset. Interestingly, the FCM algorithm was found to be the most dissimilar from all other clustering algorithms in the comparison. Finally, we highlight how the proposed approximation methods (both sampling-based and ad hoc) are able to provide bounds for the exact values of the comparison measures and can furthermore be used to compare two or more clustering algorithms and evaluate their quality.

Conclusion

In this article, we proposed a general framework for extending clustering comparison measures from hard clustering to evidential clustering (hence, as special cases, also to rough, fuzzy and possibilistic clustering). Our approach is based on the interpretation of soft clusterings as distributions over hard clustering, and uses optimal transport theory to provide a general construction method for evaluation and comparison measures of soft clusterings using what we called transport-based measures. We have studied the theoretical properties of this approach, in terms of metric properties and computational complexity. Furthermore, since a major limitation of the proposed approach lies in its high computational complexity, we also proposed some strategies for approximation, based on either a sampling approach or the design of alternative comparison measures (computable in polynomial time), which were shown to provide bounds for the transport-based measure.

Our contributions are summarized in Table 3, which describes, for every proposed measure, the corresponding metric properties and computational complexity. In regard to the metric properties we can observe that, compared to the existing measures previously proposed in the literature and discussed in Section 2.1, both the exact transport-based measures as well as the approximations for the Rand index and partition distance satisfy the desirable properties that were described in the introduction. Our proposal, then, extends and formalizes the previous proposals in [START_REF] Denoeux | Evaluating and comparing soft partitions: An approach based on Dempster-Shafer theory[END_REF][START_REF] Hullermeier | Comparing fuzzy partitions: A generalization of the Rand index and related measures[END_REF] by providing a theoretically grounded and general framework to enable the comparison between and across different classes of soft clustering methods. We believe that our contribution is particularly significant in this regard since, as discussed in the introduction and in Section 2.1, these properties enable the use of the proposed measures both as objective criteria

O(n2 k + k 3 )
to compare the results of any soft clustering algorithm with a known ground truth, thus allowing their external validation, and as objective criteria to compare the results of multiple soft clustering methods, possibly of different types (such as rough, fuzzy, possibilistic or evidential). Furthermore, since each of the proposed measures is based on a pair of functions, satisfying respectively the properties of being a consistency and a metric (or, dually, a similarity), the proposed measures also provide flexibility in modeling the trade-off between ambiguity and error. Consequently, they allow a greater degree of personalization to the users' needs than previous proposals. In regard to computational complexity, the proposed measures offer a trade-off between exactness of the results and computational feasibility. Indeed, whereas the transport-based measures allow the exact computation of the above mentioned evaluation and comparison criteria but are, in general, NP-HARD and thus infeasible to apply in largescale problems, the ad hoc and sampling-based approximations yield reasonable estimates of the above mentioned quantities at a reduced computational cost. Finally, to illustrate and discuss the above mentioned characteristics of the proposed measures, we have demonstrated their application through two simple experiments, in which we have described both the relationships between the transport-based measures and their approximations, as well as how these approximations can be used even in larger-scale problems.

We believe that this article could be a first step toward the development of approaches for the comparison of soft clustering algorithms. As further steps, we deem the following problems to be worthy of further investigation:

• In Section 3.2, we have shown that, in general, computing the transportbased distance is computationally hard, for both the cases of rough and evidential clustering. An important open problem would be to understand whether (and for which base distances) d E α (F 1 , F 2 ) can be computed in polynomial time, when F 1 , F 2 are fuzzy clusterings.

• In Section 4, we described algorithms for two commonly used clustering comparison measures, namely the Rand index and the partition distance. Then, we showed that these algorithms can be used to bound the value of the transport-based measure with the respective base distances. Since in specific settings other measures may be more appropriate, it would be interesting to develop approximation methods also for other common comparison measures, such as the mutual information or the Jaccard index.

• In the experiments reported in Section 5.1, we have shown that the bounding algorithms introduced in Sections 4.2 and 4.3 have lower empirical approximation error than the sampling-based procedures introduced in Section 4.1. An interesting problem would be to find a theoretical characterization of the approximation error for the bounding algorithms.

A. Background on Belief Functions

In this section, we recall the basic notions on belief function theory [START_REF] Dempster | Upper and lower probabilities induced by a multivalued mapping[END_REF][START_REF] Denoeux | Representations of uncertainty in ai: beyond probability and possibility[END_REF][START_REF] Shafer | A mathematical theory of evidence[END_REF]. Let X be a finite set and 2 X the corresponding power set. A mass function is a function m : 2 X → [0, 1] s.t.

It is easy to observe that Bel and P l are dual of each other, that is Bel(A) = 1 -m(∅) -P l(A c ) and P l(A) = 1 -m(∅) -Bel(A c ). Given two mass functions, m 1 and m 2 , we can define their combination as:

m 1 ⊕ m 2 (A) = 1 1 -K(m 1 , m 2 ) B,C:B∩C=A m 1 (B) • m 2 (C), (32)
where K(m 1 , m 2 ) = A,B:A∩B=∅ m 1 (A) • m 2 (B) is the conflict between m 1 and m 2 . If K(m 1 , m 2 ) = 1, then m 1 ⊕ m 2 is undefined. We define the focal sets of m as F(m) = {A ∈ 2 X : m(A) > 0}. If |F(m)| = 1, then m is said to be logical. If the focal sets are all singletons, then m is said to be Bayesian: in this case, m is a probability distribution and, ∀A ⊆ X, it holds that Bel(A) = P l(A). If, on the other hand, the focal sets are nested (i.e., ∀A, B ∈ F m , either A ⊆ B or B ⊆ A) then m is said to be consonant, and it can be shown that Bel is a necessity measure and P l is a possibility measure [START_REF] Denoeux | Representations of uncertainty in ai: beyond probability and possibility[END_REF].

Let f : X → R be a function. Then, we can extend the notion of expected value to the setting of belief function theory by defining the lower and upper expected value as follows:

E(f ) = A⊆X m(A) • min x∈A f (x) (33)
E(f ) = A⊆X m(A) • max x∈A f (x) (34)
Another useful notion regards the definition of distance functions between belief functions. In particular, we recall the definitions of the belief distance [START_REF] Denoeux | Inner and outer approximation of belief structures using a hierarchical clustering approach[END_REF] and the Jousselme distance [START_REF] Jousselme | Distances in evidence theory: Comprehensive survey and generalizations[END_REF], while we refer the reader to [START_REF] Jousselme | Distances in evidence theory: Comprehensive survey and generalizations[END_REF] for a more comprehensive review on the topic. Let m 1 , m 2 be two mass functions, both defined on 2 X , then:

d B (m 1 , m 2 ) = 1 2 A⊆X |Bel 1 (A) -Bel 2 (A)|, ( 35
)
d J (m 1 , m 2 ) = 1 2 ||m 1 || 2 + ||m 2 || 2 -2⟨m 1 , m 2 ⟩, (36)
where ⟨m 1 , m 2 ⟩ = A⊆X B⊆X m 1 (A)m 2 (A) |A∩B| |A∪B| and ||m|| 2 = ⟨m, m⟩.

Finally, we recall the notions of extension and restriction of a mass function. Let X, Y be two sets. We say that X is a refinement of Y (equivalently, Y is a coarsening of X) if exists a function ρ : 2 Y → 2 X such that: 1) {ρ({y}) : y ∈ Y } is a partition of X; 2) ∀A ⊆ Y , ρ(A) = y∈A ρ({y}). Given a mass function m defined on Y , the vacuous extension of m to X is defined by: ∀A ⊆ Y, m Y ↑X (ρ(A)) = m(A).

(

) 37
On the other hand, given a mass function m defined on X, the restriction of m to Y is defined by:

m X↓Y (A) = B⊆X:ρ -1 (B)=A m(B), (38)
where ρ -1 (B) = {y ∈ Y : ρ({y}) ∩ B ̸ = ∅} is the outer reduction of B.

  where d(a, B) = min b∈B d(a, b) and d(A, b) = min a∈A d(a, b). If d is a (pseudo-, meta-, semi-) metric, then d H satisfies the same properties.

  a rough clustering. Using the tuple-based notation introduced in Example 2.1, R can be equivalently represented by the set

Example 3 . 2 .

 32 Let C, R be the clusterings defined in Examples 2.1 and 2.4, and let d = 1 -Rand. Then d R 0 = 0 and d R 1 = 0.5. Thus, for every α ∈ [0, 1] it holds that d R α ∈ [0, 0.5]. In particular, for the case of α = 0.5, we have d R 0.5 = 0.25. On the other hand, if d is the partition distance d π , then d R 0 = 0 and d R 1 = 0.4. Thus, for every α ∈ [0, 1] it holds that d R α ∈ [0, 0.4]. In particular, for the case of α = 0.5, we have d R 0.5 = 0.2.By construction, d R 0 and d R 1 are well suited for the objective comparison between two soft clusterings, as they satisfy the required metric property of being (the dual of) a consistency and a metric. Unfortunately, from the computational point of view, the calculation of d R 0 and d R 1 is likely to be intractable, as shown by the following proposition. Proposition 3.2. Let R 1 , R 2 be two rough clusterings represented through, either, the object-based or relational representations. Let k = |Ω| be the number of clusters, and m = |{x ∈ X : |R(X)| ̸ = 1}|. Then, the problem of computing d R 0 and d R 1 is NP-HARD: in particular, if k is constant, then both problems are fixed-parameter tractable with respect to the parameter m.

Example 3 . 3 .

 33 Let C, F, P, M be the clusterings defined in Examples 2.1, 2.3, 2.5, and let d = 1 -Rand. Then, it holds that:

Example 4 . 1 .

 41 Let C be the hard clustering defined in Example 2.1, let R ′ be the rough clustering s.t. ∀x ∈ X, R(x) = Ω, and let d = 1 -Rand. Then, clearly, d R 0 = 0 and d R 1 = 1.

1 (

 1 masses. The solution of Eq (15) is still r xi,xj = |µ xi,xj

Definition 4 . 1 .

 41 Let α ∈ [0, 1], M 1 , M 2 be two evidential clusterings, n = |X| the number of objects and r xi,xj α

Example 4 . 2 .

 42 Let C, R, F, P, M be the clusterings defined in Examples 2.1, 2.3, 2.4 and 2.5. Then:• Rand 1 (C, R) = 0.52 and Rand 0 (C, R) = 1;• For all α ∈ [0, 1], Rand α (C, F ) = 0.79;• Rand 1 (C, P ) = 0.54 and Rand 0 (C, P ) = 1;• Rand 1 (C, M ) = 0.55 and Rand 0 (C, M ) = 0.95.

  be any pair of objects considered in the computation of Rand(C 1 , C 2 ) and consider r xi,xj C1,C2 . Note that r xi,xj C1,C2 ∈ {0, 1} and r xi,xj C1,C2 = 1 =⇒ r xi,xj 0 . Therefore, the inequality follows in the case of rough clustering. The general case for evidential clustering follows by noting that an evidential clustering is a probability distribution over rough clustering and from the definition of the Wasserstein distance. For the inequality Rand 1 ≤ 1 -d E 0 we can apply a similar technique, noting that r xi,xj C1,C2 = 0 =⇒ r xi,xj 1 = 0. Therefore, the result follows.The previous result shows that we can bound d E 0 , d E 1 by computing Rand α , which can be done in time O(n 2 ) instead of O(2 n ). We leave it as an open problem to characterize the quality of the approximation provided by Rand α , that is, to determine whether it is possible to find bounds for the approximation error ϵ = |d E α -Rand α |. Next, we study the properties of Rand α . First, we note that when M 1 , M 2 are fuzzy clusterings, the following result holds. Theorem 4.2. Let F 1 , F 2 be fuzzy clusterings. Then, for all α ∈ [0, 1], Rand α = Rand 0 = Rand 1 .

Corollary 4 . 1 .

 41 Assume that evidential clusterings are represented through the object-based representation, and α ∈ [0, 1]. Then,

Theorem 4 . 4 .

 44 Let r xi,xj α be defined as in Eq (23) and assume m

Figure 1 :

 1 Figure 1: Graphical visualization of the Iris dataset in PCA space, with respect to the first two principal components. As shown by the figure, the classes are almost linearly separable, with a small overlap between classes 1 and 2.

Figure 2 :

 2 Figure 2: Graphical representation of the synthetic dataset used in the second experiment.

Figure 3 :

 3 Figure 3: Multi-dimensional scaling representation of the pairwise S-RI (left) and A-RI (right) indices. The relative position of the circles corresponds to their similarity, while the size of the circles represents the width of the corresponding intervals.

Figure 4 :

 4 Figure 4: Multi-dimensional scaling representation of the pairwise S-PD (left) and A-PD (right) indices. The relative position of the circles corresponds to their similarity, while the size of the circles represents the width of the corresponding intervals.

  A∈2 X m(A) = 1. If m(∅) ̸ = 0, then m is unnormalized. Given a mass function m, we define the belief and plausibility functions as: Bel(A) = B:∅̸ =B⊆A m(B); P l(A) = B:B∩A̸ =∅ m(B).

Table 1 :

 1 Relational representation of the evidential clustering defined in Example 2.3.

	Pair	m(∅)	m(s)	m(¬s)	m

Table 2 :

 2 Results of the first experiment. For the Rand index higher is better, while for the partition distance lower is better.

	Metric	KM	RKM	FCM	PCM	ECM
	T-RI	0.877 (0.034s)	(0.874, 0.886) (0.802s)	0.876 (784.388s)	(0.839, 0.941) (979.053s)	(0.781, 0.944) (1394.69s)
	S-RI	-	(0.874, 0.886) (0.429s)	0.876 (11.266s)	(0.860, 0.927) (19.848s)	(0.681, 0.819) (19.845s)
	A-RI	-	(0.871, 0.889) (6.949s)	0.876 (6.924s)	(0.826, 0.966) (7.146s)	(0.747, 0.887) (7.024s)
	T-PD	0.111 (0.031s)	(0.099, 0.113) (0.803s)	0.112 (184.707s)	(0.033, 0.122) (224.31s)	(0.041, 0.229) (431.57s)
	S-PD	-	(0.100, 0.113) (0.202s)	0.112 (11.391s)	(0.072, 0.103) (13.739s)	(0.154, 0.209) (16.424s)
	A-PD	-	(0.099, 0.113) (1.807s)	0.112 (1.665s)	(0.033, 0.136) (2.926s)	(0.039, 0.221) (3.386s)

Table 3 :

 3 Summary of the proposed comparison measures and their approximations and bounds

	Measure	Section	Metric Properties	Computational Complexity
	Transport-based Measure	3.2	1 -d E 0 consistency d E 1 metric	d E 0 NP-HARD d E 1 NP-HARD
	Sampling-based Approximations	4.1	-	O(n 2 s + s 3 log s)
	Approximation for Rand index	4.2	Rand 0 consistency Rand 1 similarity	O(n 2 )
	Approximation for partition distance	4.3	1 -δ E 0 consistency δ E 1 metric

We remark that, if d R 1 was defined similarly to (14a) as max C 1 ∈C(R 1 ),C

∈C(R 2 ) d(C 1 , C 2 ), i.e., by replacing the minimum in (14a) by the maximum, then this alternative version of d R 1would not be a metric[START_REF] Campagner | Orthopartitions and soft clustering: soft mutual information measures for clustering validation[END_REF].

The code is freely accessible at https://github.com/AndreaCampagner/scikit-cautious.

Proof. The proof is similar to the one for Theorem 4.1 and is therefore omitted.

As for the case of the Rand index, we leave as open problem to find bounds for the approximation error ϵ = |d E α -δ E α |. Then, we study the properties of δ E α . It can be easily proved that δ E α satisfies the following properties:

Proof. The claims derive easily from the properties of ∆ α = r xi,xj α

, the partition distance and the Wasserstein distance.

Example 4.3. Let C, R, F, P, M be the clusterings defined in Examples 2.1, 2.3, 2.4 and 2.5. Then,

We note that for the cases of δ E 0 (C, R), δ E 0 (C, R), δ E 0 (C, M ) and δ E α (C, F ), the values of the approximation coincide with the exact solution of Eq [START_REF] Denoeux | Nn-evclus: Neural network-based evidential clustering[END_REF]. Also, δ E α can be computed in polynomial time:

Proof. Computing δ E α first requires transforming the evidential clusterings M 1 and M 2 in the representation described in Eqs ( 26)-( 29). This transformation can be performed in time O(n2 k ). As shown in Eq [START_REF] Fowlkes | A method for comparing two hierarchical clusterings[END_REF], the value of ∆ α can be computed in O(1) time. Since the value of ∆ α must be computed for each pair of clusters (ω 1 , ω 2 ) ∈ Ω 1 × Ω 2 , this requires a total time of O(k 2 ), where k = max{|Ω 1 |, |Ω 2 |}. Thus, the inner sum of Eq (30) has total complexity O(nk 2 ). Finally, Eq [START_REF] Ko | On the complexity of min-max optimization problems and their approximation[END_REF], once the values of the inner loop have been computed, can be solved through any standard algorithm for the weighted balanced assignment problem (e.g., the Hungarian method) in time O(k 3 ).

We note that, even though the term n2 k is exponential in the number of clusters k, the computation of δ E α is still polynomial in the size of the evidential clusterings M 1 , M 2 , since in general these latter have size which is exponential in k. Furthermore, we can observe that, in terms of computational complexity,