# Soft-ECM: An extension of Evidential C-Means for complex data

Armel Soubeiga, Thomas Guyet, Violaine Antoine

► To cite this version:

Armel Soubeiga, Thomas Guyet, Violaine Antoine. Soft-ECM: An extension of Evidential C-Means for complex data. FUZZ-IEEE 2025 - International Conference on Fuzzy Systems, Jul 2025, Reims, France. hal-05162452

HAL Id: hal-05162452

https://inria.hal.science/hal-05162452v1

Submitted on 15 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Soft-ECM: An extension of Evidential C-Means
for complex data*

Armel Soubeiga, Clermont Auvergne INP, ENSM
St Etienne, UMR 6158 CNRS, LIMOS,
armel.soubeiga@uca.fr

Thomas Guyet, AISTRO SIGHT/Inria, UCBL, HCL
thomas.guyet@inria.fr

Violaine Antoine, Clermont Auvergne INP, ENSM
St Etienne, UMR 6158 CNRS, LIMOS
violaine.antoine@uca.fr

## Abstract

Clustering based on belief functions has been gaining increasing attention in the machine learning community due to its ability to effectively represent uncertainty and/or imprecision. However, none of the existing algorithms can be applied to complex data, such as mixed data (numerical and categorical) or non-tabular data like time series. Indeed, these types of data are, in general, not represented in a Euclidean space and the aforementioned algorithms make use of the properties of such spaces, in particular for the construction of barycenters. In this paper, we reformulate the *Evidential C-Means (ECM)* problem for clustering complex data. We propose a new algorithm, *Soft-ECM*, which consistently positions the centroids of imprecise clusters requiring only a semi-metric. Our experiments show that *Soft-ECM* present results comparable to conventional fuzzy clustering approaches on numerical data, and we demonstrate its ability to handle mixed data and its benefits when combining fuzzy clustering with semi-metrics such as DTW for time series data.

**keywords:** Evidential clustering, credal partition, time series data, optimization

## 1 Introduction

In numerous real-world applications, only partial information is available for objects, and in these cases hard clustering can result in poor accuracy. To address this problem and capture the degree of ambiguity regarding the class membership of the objects, soft clustering variants have been proposed, including Fuzzy C-Means [BEF84] and Evidential C-Means [MD08]. These variants allow to describe the uncertainty and/or imprecision in the partition. Fuzzy C-Means (FCM) [BEF84] is based on fuzzy set theory, while Evidential C-Means (ECM) clustering is based on belief function theory [MD08]. ECM allows objects to belong not only to singleton clusters of the solution set Ω, but also to any subset of Ω (i.e. *meta-clusters*) with different belief masses. This additional flexibility over FCM provides a deeper insight into the data and improves robustness against outliers. However, ECM was originally designed for tabular data and it handles only quantitative attributes, i.e. data in a vector space. Indeed, ECM is based on Euclidean distance: the problem formulation assumes the capability to compute barycenters as a mean position of cluster elements. However, this is not always feasible. In order to adapt ECM to different types of data, variants have been proposed. Among these variants, ECMdd [ZMPL15] and

<footnote>*This article has been published in the proceedings of the IEEE conference on Fuzzy Systems (Fuzz), 2025</footnote>
RECM [MD09] use relational similarity measures, while CECM [AQMD12] introduces clustering constraints to better guide data partitioning and employs a specific Mahalanobis distance for each cluster. ECM+ [AAK25] improves the center definition when Mahalanobis distances are used. Other variants, such as CatECM [DMACM19], are designed for categorical data. Credal C-Means (CCM) [LPDM15] and Belief C-Means (BCM) [LDMP12] modify how objects are assigned to meta-clusters. These approaches reconsider the computation of cluster centers by considering distances between objects and clusters, avoiding the arithmetic mean approximation, which improves accuracy for highly uncertain data. Furthermore, some data types are not tabular, such as time series for which hard clustering methods have already been adapted [PFW+14]. To the best of our knowledge, no evidential clustering methods have yet been proposed to handle such data.

In this paper, we propose Soft-ECM, a new algorithm that reformulates the ECM problem as a constrained multi-class clustering, where singleton clusters and meta-clusters (imprecise clusters) are individually optimized. In contrast to the classical ECM approach, meta-clusters are here treated like singleton clusters, allowing greater flexibility in dealing with uncertainties. A new constraint on meta-cluster barycenters ensures that they are positioned consistently with those of singleton clusters. In this way, Soft-ECM is more flexible, and allows the use of non-Euclidean dissimilarity measures. This makes it possible to deal with complex data, such as mixed data (tabular data with both quantitative and qualitative features) or even non-tabular data such as time series.

## 2 Background of Evidential C-Means (ECM)

ECM is an algorithm based on the notions of uncertainty and imprecision defined in the theory of belief functions. This theory, also known as Dempster-Shafer theory [Sha76], provides powerful tools for modeling partial information. Considering $\omega$ as a variable defined in finite set $\Omega = \{\omega_1, \dots, \omega_c\}$, partial knowledge of the true value of $\omega$ can be represented by a mass function $m$, defined from power set $2^\Omega$ to $[0, 1]$ and satisfying: $\sum_{A \subseteq \Omega} m(A) = 1$. The quantity $m(A)$ is then interpreted as the amount of belief assigned to any subset $A \subseteq \Omega$, and $A$ is called a focal element if $m(A) > 0$. When $m(A) = 1$, we have a certain belief. When $m(A) > 0$ and $|A| > 1$, we have an imprecise belief.

For the ECM clustering problem [MD08], Masson and Denœux consider $\mathbf{X} = \{\mathbf{x}_1, \dots, \mathbf{x}_n\}$ a set of $n$ individuals described in $\mathbb{R}^p$ to be grouped into a set of $c$ “pure” or “singleton” clusters, denoted $\Omega = \{\omega_1, \dots, \omega_c\}$. The result of ECM is then the assignment of each example $\mathbf{x}_i \in \mathbf{X}$ to a subset $A \subseteq \Omega$ by a mass $m_i(A) \in \mathbb{R}_+$. When $A$ has a cardinality $|A| > 1$, an example is classified imprecisely to all clusters of this set. In this case, $A$ is designated as a *meta-cluster*.

ECM minimizes the following intra-cluster inertia:<fnref n="1" />

$$ J_{ECM}(\mathbf{M}, \mathbf{V}) = \sum_{i=1}^{n} \sum_{A \subseteq \Omega \setminus \emptyset} |A|^{\alpha} m_i(A)^{\beta} d^2(\mathbf{x}_i, \bar{\mathbf{v}}_A) + \sum_{i=1}^{n} \delta^2 m_i(\emptyset)^{\beta}, \quad (1) \\ \text{subject to } \sum_{A \subseteq \Omega} m_i(A) = 1 \quad \forall i \in [n]. $$

with $\mathbf{M} = \{m_i(A) \mid i \in [n], A \subseteq \Omega\}$ the credal partition, $\mathbf{V} = \{\mathbf{v}_{\omega_j}\}_{j \in [c]}$ singleton clusters centroids, $\{\bar{\mathbf{v}}_A\}_{A \subseteq \Omega}$ the centroids of clusters and meta-clusters; and $d$ the Euclidean distance.

Fig. 1 illustrates a soft clustering, ECM considers only the green dashed lines in its optimization problem and the position of the meta-cluster is computed as the barycenter of the centroids of singleton clusters.

The hyperparameter $\beta > 0$ controls the spread of the final partition: as the value of $\beta$ increases, the mass functions of the partition have degrees of belief distributed over all

<footnote n="1">¹Refer to the paper [MD08] for the minimization scheme.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 1: Illustration of a 2-cluster evidential clustering. Examples are represented in green. Points in blue $v_{\omega_1}$ and $v_{\omega_2}$ indicate cluster centers, $\omega_1$ and $\omega_2$. The red point $v_{\{\omega_1, \omega_2\}}$ is the center of meta-cluster $\{\omega_1, \omega_2\}$. This point is both the barycenter of examples belonging in the meta-cluster $\{\omega_1, \omega_2\}$; and the barycenter of $v_{\omega_1}$ and $v_{\omega_2}$. The fine dotted lines indicate the distances considered in computing the new clustering inertia.</figcaption></figure>

subsets $A \subseteq \Omega$. The coefficient $|A|^\alpha$ controls the imprecision of the credal partition. If $\alpha > 0$ is large, then subsets with high cardinalities are penalized more than singletons. Thus, the degrees of belief are increased for singletons and decreased for other subsets. Finally, the hyperparameter $\delta$ corresponds to the minimal atypicity distance. When the distance between an example and the empty set is above this threshold, it is considered atypical.

It is worth noting that, in ECM, the centroids of the meta-clusters are not in $V$. The centroid of a meta-cluster $A \subseteq \Omega$, $|A| > 1$, is computed as the isobarycenter of the centroids associated with the singleton clusters:

$$ \bar{v}_A = \frac{1}{|A|} \sum_{\omega_k \in A} v_{\omega_k}. \qquad (2) $$

This definition of a barycenter is correct when the data are in a Euclidean space. Nonetheless, it cannot be use for complex data such as categorical, non-numerical or non-tabular data, for which we might wish to use non-euclidean dissimilarity measures.<fnref n="2" />

## 3 Soft Evidential C-Means (Soft-ECM) Approach

We propose to reformulate the ECM problem in a more generic way, so that the evidential clustering problem can be solved with dissimilarity measures other than Euclidean distance. Intuitively, our approach relaxes the definition of meta-cluster centroid as the explicit isobarycenter of singletons' centroids. In Fig. 1, the meta-cluster centroid $v_{\{A,B\}}$ is constrained by both being as close as the barycenter of its examples (green dashed lines) and being as close as barycenter of the singletons clusters centroids (red dashed lines).

In this section, $X = \{x_1, \dots, x_n\}$ denotes a set of objects in $\mathbb{X}$ (e.g., time series) and $d$ denotes a semi-metric between these objects.<fnref n="3" /> In a classical way [PFW+14], we can then define the barycenter of a set of objects as an element of $\mathbb{X}$ that minimizes inertia. More formally, the barycenter, $v_E$, of the subset $E \subseteq X$ is defined as follows:

$$ v_E = \underset{\boldsymbol{x} \in \mathbb{X}}{\operatorname{argmin}} \sum_{e \in E} d(e, \boldsymbol{x}). \qquad (3) $$

<footnote n="2">²The properties of Euclidean distance in required by ECM to define both the function to be optimized (1) and the meta-cluster centroids (2).</footnote>

<footnote n="3">³A semi-metric is a symmetric, positive and defined dissimilarity measure, but it does not necessarily hold the triangular inequality.</footnote>
Then, the Soft-ECM problem is formalized as the following constrained minimization problem:

$$
\begin{equation}
\begin{aligned}
\min_{\mathbf{M},\mathbf{V}} & J^{\alpha,\beta,\delta}(\mathbf{M},\mathbf{V}) = \sum_{i=1}^{n} \sum_{A \subseteq \Omega \setminus \emptyset} |A|^{\alpha} m_i(A)^{\beta} d(\mathbf{x}_i, \mathbf{v}_A) + \sum_{i=1}^{n} \delta^2 m_i(\emptyset)^{\beta} \\
\text{subject to} & \sum_{A \subseteq \Omega} m_i(A) = 1, \forall i \in [n], \\
& \mathbf{v}_A = \underset{\mathbf{x} \in \mathcal{X}}{\operatorname{argmin}} \sum_{\omega_k \in A} d(\mathbf{v}_{\{\omega_k\}}, \mathbf{x}), \forall A \subseteq \Omega.
\end{aligned}
\tag{4}
\end{equation}
$$

In this formulation, $\mathbf{M} = (m_i(A))_{i \in [n]}$ represents the mass functions on a focal element $A \subseteq \Omega$, while $\mathbf{V} = \{\mathbf{v}_A\}_{A \subseteq \Omega \setminus \emptyset}$ corresponds to the barycenters of all singleton clusters and meta-clusters. In contrast to ECM formulation (1), which focused on the optimization of cluster positions only and defined the positions of meta-clusters by (2), here we optimize both. The second constraint enforces the centroid of each meta-cluster $A$ to be the barycenter of the cluster centroids ($\mathbf{v}_{\omega_k}$ where $\omega_k \in A$). We find again the expression of the equation that defines the barycenter (see (3)).

**Proposition 1.** Provision $\mathcal{X} = \mathbb{R}^p$ and $d$ is the squared Euclidean distance, the problems of (1) and (4) are equivalent.

*Proof.* From the definition of the notion of barycenter in Equation 3, and in the case where $d$ is the Euclidean distance, we have the equivalence between:

1. $\mathbf{v}_A = \underset{x \in \mathcal{X}}{\operatorname{argmin}} \sum_{\omega_k \in A} d(\mathbf{v}_{\{\omega_k\}}, x)$ (inertia minimization),

2. $\mathbf{v}_A$ is the centroid of clusters or meta-clusters (by the properties of barycenters).

We now define the mapping $\bar{\cdot}: \mathbb{R}^{p \times c} \mapsto \mathbb{R}^{p \times 2^c}$ which constructs a set of centroids for all clusters and meta-clusters from the centroids of pure clusters. Its inverse, denoted $\cdot: \mathbb{R}^{p \times 2^c} \mapsto \mathbb{R}^{p \times c}$, selects only the centroid corresponding to pure a cluster from the set of all centroids. Then, for any $\mathbf{M}$ and $\mathbf{V}$, we have:

$$
\begin{align}
J_{ECM}(\mathbf{M}, \mathbf{V}) &= J^{\alpha, \beta, \delta}(\mathbf{M}, \bar{\mathbf{V}}) \nonumber \\
J^{\alpha, \beta, \delta}(\mathbf{M}, \mathbf{V}) &= J_{ECM}(\mathbf{M}, \bar{\mathbf{V}}) \tag{5}
\end{align}
$$

This simply expresses the fact that, although the parameters of $J_{ECM}$ only take into account the centroids of pure clusters, the objective function actually involves the centroids of both pure clusters and meta-clusters (when computed using the Euclidean distance).

It is then easy to verify that $\bar{\mathbf{V}} = \mathbf{V}$.

Having introduced these notions, we can now prove the proposition above by contradiction.

**Let us start by proving that (1) $\Leftarrow$ (4).** Suppose that $\mathbf{M}^*$ and $\mathbf{V}^*$ are the optimum of $J^{\alpha,\beta,\delta}(\mathbf{M},\mathbf{V})$ as defined in Equation 4, and assume that there exists a better solution than $(\mathbf{M}^*, \mathbf{V}^*)$ for minimizing $J_{ECM}$. Let $(\mathbf{M}', \mathbf{V}')$ denote such a solution, i.e., $J_{ECM}(\mathbf{M}', \mathbf{V}') < J_{ECM}(\mathbf{M}^*, \mathbf{V}^*)$. Then, using the equalities from (5) on both sides of the inequality, we obtain: $J^{\alpha,\beta,\delta}(\mathbf{M}', \bar{\mathbf{V}}') < J^{\alpha,\beta,\delta}(\mathbf{M}^*, \bar{\mathbf{V}}^*)$, and therefore: $J^{\alpha,\beta,\delta}(\mathbf{M}', \bar{\mathbf{V}}') < J^{\alpha,\beta,\delta}(\mathbf{M}^*, \mathbf{V}^*)$.

Moreover, we can verify that $(\mathbf{M}', \bar{\mathbf{V}}')$ is a valid solution of Equation 4. Indeed: The constraints on the sum of masses are trivially satisfied since $(\mathbf{M}', \mathbf{V}')$ was a solution of Equation 1, which includes these constraints on $\mathcal{M}$. The second set of constraints is also satisfied, because by construction of $\bar{\mathbf{V}}'$, the additional elements are barycenters of the pure clusters, and in the Euclidean case, such barycenters are the points that minimize inertia (see above).
Thus, $(M', \bar{\mathcal{V}}')$ would be a better solution than the supposed optimum of Soft-ECM, which is impossible. We conclude that there exists no better solution than $(M^*, \mathcal{V}^*)$ for $J_{ECM}$.

Let us new prove that (1) ⇒ (4). The reverse direction can be shown symmetrically.

We thus conclude that the two minimization problems are equivalent in the Euclidean setting.

<figure><img src="image_3.png" /></figure>

# 4 Optimization Scheme for Soft-ECM

The Soft-ECM problem is a bi-level optimization problem [DZ20], i.e. an optimization problem in which parameters are themselves defined by another optimization problem.

We propose a heuristic that relaxes the hard constraint of identifying the meta-clusters barycenters into an additional numerical constraint in the global minimization function. The relaxed minimization problem of Soft-ECM then becomes:

$$ 
\begin{aligned}
\min_{M, \mathcal{V}} & \sum_{i=1}^{n} \sum_{A \subseteq \Omega \setminus \emptyset} |A|^{\alpha} m_i(A)^{\beta} d(\mathbf{x}_i, \mathbf{v}_A) + \sum_{i=1}^{n} \delta^2 m_i(\emptyset)^{\beta} \\
& + \lambda \sum_{A \subseteq \Omega \setminus \emptyset} \sum_{\omega_k \in A} d(\mathbf{v}_{\{\omega_k\}}, \mathbf{v}_A), \\
\text{subject to} & \quad \sum_{A \subseteq \Omega} m_i(A) = 1, \quad \forall i \in [n].
\end{aligned}
\quad (6) $$

While the first and second terms are similar to those of ECM, the third term imposes the additional constraint of consistency between the barycenters of the $(\{\omega_k\})_{k \in [c]}$ clusters and those of meta-clusters. The new hyperparameter $\lambda \ge 0$ adjusts the importance given to this constraint. The higher $\lambda$, the more the solution respects the inter-clusters positioning constraint.

We can use an alternating optimization scheme to solve the relaxed Soft-ECM optimization problem (see Algorithm 1), with the following two steps alternating (until convergence or a fixed number of iterations):

1) **Optimization of M, with V fixed.** The credal partition $M$, which minimizes the objective function, is computed using the expression below:

$$ 
\begin{aligned}
m_i(A) &= \frac{|A|^{-\frac{\alpha}{\beta-1}} d(\mathbf{x}_i, \mathbf{v}_A)^{-\frac{1}{\beta-1}}}{\sum_{B \neq \emptyset} |B|^{-\frac{\alpha}{\beta-1}} d(\mathbf{x}_i, \mathbf{v}_B)^{-\frac{1}{\beta-1}} + \delta^{-\frac{2}{\beta-1}}}, \\
m_i(\emptyset) &= 1 - \sum_{A \neq \emptyset} m_i(A).
\end{aligned}
\quad (7) $$

This solution was proposed for ECM [MD08] and is still valid for Soft-ECM. Indeed, the term added to the objective function does not depend on $M$, so the optimization with respect to $M$ of the problem in (6) is the same as the problem in (1).

2) **Optimization of V, with M fixed.** The optimization of (6) when $M$ is fixed is equivalent to the following unconstrained optimization problem:

$$ \operatorname*{argmin}_{\mathcal{V}} \sum_{A \subseteq \Omega \setminus \emptyset} \left( \sum_{i=1}^{n} |A|^{\alpha} m_i(A)^{\beta} d(\mathbf{x}_i, \mathbf{v}_A) + \lambda \sum_{\omega_k \in A} d(\mathbf{v}_{\{\omega_k\}}, \mathbf{v}_A) \right). \quad (8) $$

We adopt a different approach from ECM and use a numerical method (gradient descent) to find an approximate solution. The use of optimization tools based on automatic
differentiation allows to solve this problem efficiently. We note that the optimization of this function requires the differentiability of *d*.

Soft-ECM converges after a finite number of iterations as $J^{\alpha,\beta,\delta,\lambda}$ decreases at each step and is a positive function. Indeed, updating the credal partition **M** with Lagrange multipliers does not increase the objective function $J^{\alpha,\beta,\delta,\lambda}$ [MD08]. Regarding the optimization with respect to **V**, the gradient descent ensure to not increase the objective function.

<caption>**Algorithm 1: Soft-ECM Algorithm**</caption>

**Input:** {$\mathbf{x}_1, \dots, \mathbf{x}_n$}: $n$ objects in $\mathbb{X}^n$.
**Parameters:**
$c$: number of clusters
$\alpha > 0, \beta > 1$: weightings for belief
$\delta > 0$: threshold for outliers
$\lambda > 0$: consistency importance between barycenters
$\epsilon, \xi > 0$: convergence thresholds
$\rho$: learning rate
**Initialization:**
$\mathbf{v}^0$: Initialize $c$ prototypes randomly
$\mathbf{v}_A^0$: Compute the mean of $\mathbf{v}^0$ for $|A| > 1$
$t \leftarrow 0$
**Repeat**
| (1) Compute the credal partition **M** using (7);
| (2) Update the prototype vector:
|   $\theta \leftarrow 0$
|   **Repeat**
|   | $\mathcal{V}^{\theta+1} = \mathcal{V}^{\theta} - \rho \nabla_{\mathcal{V}} J^{\alpha,\beta,\delta,\lambda}(\mathbf{M}, \mathcal{V}^{\theta})$;
|   |   $\theta \leftarrow \theta + 1$;
|   **Until** $\|\mathcal{V}^{\theta+1} - \mathcal{V}^{\theta}\| < \xi$;
|   $t \leftarrow t + 1$;
| **Until** $\|\mathbf{M}^t - \mathbf{M}^{t-1}\| < \epsilon$;
**Output:** Optimal solution **M** and $\mathcal{V}$.

# 5 Experiments

In this section, we present the results of several experiments. First, we demonstrate the ability of Soft-ECM to perform clustering comparable to ECM on a classic toy problem. Next, we compare various fuzzy clustering methods with our approach using real-world datasets of different types, including tabular data (numerical and categorical) and time series. Finally, we showcase the clustering of synthetic time series to illustrate how our approach addresses the challenges of fuzzy clustering on complex data with a semi-metric.

## 5.1 Experiments with Synthetic Data

We compare the behavior of Soft-ECM and ECM on a classic dataset, *Diamond* [MD08]. It consists of twelve objects (see Fig. 2a), where objects 1 to 11 being normal, and object 12 is an outlier. Soft-ECM and ECM were run with the same parameters: $\alpha = \frac{1}{6}$, $\beta = 2$, $\delta = 11$ and, for Soft-ECM, $\lambda = 1.5$. The data were partitioned into $c = 2$ clusters. Fig. 2b and Fig. 2c depict the $2^c$ cluster masses (focal elements) —$m(\omega_1)$, $m(\omega_2)$, $m(\Omega)$, and $m(\emptyset)$— for ECM and Soft-ECM, respectively.
<figure><img src="image_4.png" /><figcaption>(a) Données initiales</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(c) Soft-ECM ($\lambda = 1.5$)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(b) ECM</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(d) Soft-ECM ($\lambda = 3.5$)</figcaption></figure>

<caption>Figure 2: Illustration of the Diamond dataset clustering [MD08]. (a) illustration of raw data. (b), (c) and (d) mass distributions for each example for ECM and Soft-ECM. A high mass indicates cluster or meta-cluster membership.</caption>

Objects 1 to 5 and 8 to 11 are assigned to two distinct clusters by ECM and Soft-ECM, while object 12 is identified as an outlier. For objects 6 and 7, ECM assigns most of the mass to the ignorance (meta-cluster) $\Omega$, as they are located near the centroid of $\Omega$, which is defined as the average of the centroids of $\omega_1$ and $\omega_2$ (see Fig. 2b). In contrast, Soft-ECM optimizes this centroid more effectively, with most belief mass assigned to $\omega_2$ for object 7 (cf. Fig. 2c). When we increase $\lambda$, until 3.5 with this dataset, it further constrains inter-cluster positioning. As shown in Fig. 2d, object 6 was then classified into the $\omega_1$, consistent with the results obtained by the authors in (BCM) [LDMP12] and aligned the raw data.

## 5.2 Experiments and Comparisons with Real-World Data

### 5.2.1 Experimental Setting

We evaluate here the performance of Soft-ECM against ECM and its state-of-the-art variants, using nine publicly available real-world datasets.<fnref n="4" /> The datasets are of different types (numerical, categorical or time series). Tab. 1 summarizes the characteristics of the datasets.

Soft-ECM is implemented in Python and based on PyTorch [PGC+17] for solving (8).<fnref n="5" /> Benchmark algorithms used to evaluate the performance of our algorithm include ECM for numerical data, Evidential C-Means for categorical data (CatECM [DMACM19]), and Evidential C-Medoids (ECMdd [ZMPL15]) for the relational format of data. Additionally, we compare our results with a hard clustering approach, specifically K-means and its variants K-modes and TimeSeriesKMeans (TSKmeans [FAT+14]).

Each algorithm was executed 10 times for each of the following parameter settings: $\alpha = 2.0$, $\delta = 10$, $\beta \in \{1.1, 1.2, ..., 2.0\}$, $\lambda \in \{1.0, 2.0, ..., 10.0\}$. Each run was stopped upon convergence to a stationary value with $\epsilon = 10^{-3}$. The number of subsets for meta-clusters was limited to 2 for the sake of interpretability and computation time. For each dataset, the number of clusters corresponds to the prior number of clusters. For credal

<footnote n="4">⁴https://archive.ics.uci.edu, https://www.timeseriesclassification.com/</footnote>

<footnote n="5">⁵Code available: https://gitlab.inria.fr/tguyet/ecm-ts.</footnote>
<table><caption>Table 1: Experimental dataset characteristics, n: number of objects, p: number of dimensions and c: number of clusters.</caption><thead><tr><th>Data</th><th>n</th><th>p</th><th>c</th><th>Length</th><th>Metric(s)</th><th>Inputs</th></tr></thead><tbody><tr><td>Abalone</td><td>4 177</td><td>8</td><td>3</td><td>-</td><td>Euclidean</td><td>Numerical</td></tr><tr><td>Ecoli</td><td>336</td><td>7</td><td>8</td><td>-</td><td>Euclidean</td><td>Numerical</td></tr><tr><td>Glass</td><td>214</td><td>9</td><td>6</td><td>-</td><td>Euclidean</td><td>Numerical</td></tr><tr><td>Breast Cancer (BC)</td><td>286</td><td>9</td><td>2</td><td>-</td><td>Hamming</td><td>Categorical</td></tr><tr><td>Lung</td><td>32</td><td>56</td><td>3</td><td>-</td><td>Hamming</td><td>Categorical</td></tr><tr><td>Soybean</td><td>47</td><td>35</td><td>4</td><td>-</td><td>Hamming</td><td>Categorical</td></tr><tr><td>ERing</td><td>30</td><td>4</td><td>6</td><td>65</td><td>Euclidean, Soft-DTW</td><td>Time series</td></tr><tr><td>BasicMotions (BM)</td><td>40</td><td>6</td><td>4</td><td>100</td><td>Euclidean, Soft-DTW</td><td>Time series</td></tr><tr><td>AtrialFibrillation (AF)</td><td>15</td><td>2</td><td>3</td><td>640</td><td>Euclidean, Soft-DTW</td><td>Time series</td></tr></tbody></table>

partitions, the pignistic [MD08] transformation was applied to convert them into hard partitions. Euclidean, Soft-DTW and Hamming metrics were used for clustering numerical, temporal and categorical data respectively (see Tab. 1). They are all differentiable.

### 5.2.2 Analysis of $\lambda$ Parameter

In this section, we examine the sensitivity of Soft-ECM results to the new parameter $\lambda$ on each dataset. We use the average normalized specificity as the internal validity index of a credal partition, as defined by (9), following the approach proposed in [MD08], where $0 \le N^*(c) \le 1$.

$$N^*(c) = \frac{1}{n \log_2(c)} \sum_{i=1}^{n} \sum_{A \in 2^{\Omega} \setminus \emptyset} m_i(A) \log_2|A| \quad (9)$$

Fig. 3 illustrates the normalized specificity ($N^*$) computed for Soft-ECM with several combinations of $\lambda$ and $\beta$ values on real-world datasets. We can observe that the values of $\lambda$ and $\beta$ have a significant impact. Selecting appropriate values for $\lambda$ on each dataset improves the performance of Soft-ECM. These first results show no evident trend in the evolution of $N^*$ and, at this stage, we recommend a tuning of the $\lambda$ parameter for each dataset, for instance via a grid search.

### 5.2.3 Comparison with other Algorithms on Real-World Datasets

For each dataset, the values of parameters $\beta$ and $\lambda$ that minimize the non-specificity ($N^*$) are selected for the credal partitions. Next, we compute the mean and standard deviation ($\sigma$) of two standard performance measures —accuracy and Rand Index (RI) [HA85]— across 10 executions.

Tab. 2 shows the performances obtained for each algorithm on each dataset. The accuracy is calculated using a prior known class of data. Indeed, for each algorithm and each dataset, we calculated the mean and standard deviation statistics in mean($\sigma$) format in Tab. 2 (according to parameters defined in Sec. 5.2.1 and those selected in Sec. 5.2.2).

The results show that Soft-ECM performs well across different data types, both in terms of RI and accuracy. For numerical data, Soft-ECM achieves competitive results, often close to or better than *ECM* and *K-Means*, with an average RI of 56.6% and accuracy of 51.6%. However, it shows slightly higher variability in performance, according to $\sigma$. On categorical data, Soft-ECM outperforms *K-Modes* and *CatECM* in many cases, though its performance varies across iterations, with higher $\sigma$ values. For time series datasets, where
<figure><img src="image_8.png" /><figcaption>Figure 3: Normalized specificity (N*) of Soft-ECM wrt parameters β and λ on 9 real-world datasets.</figcaption></figure>

<table><caption>Table 2: Clustering average performance (Rand Index on the left and Accuracy on the right) of algorithms on real datasets. Figures in parentheses are standard deviations. Bold numbers indicate best results by dataset. “-” refers to inappropriate algorithms for a given dataset.</caption><thead><tr><th></th><th>ECM</th><th>ECMdd</th><th>CatECM</th><th>Soft-ECM</th><th>K-Mesms</th><th>K-Modes</th><th>TSKmeans</th><th>ECM</th><th>ECMdd</th><th>CatECM</th><th>Soft-ECM</th><th>K-Means</th><th>K-Modes</th><th>TSKmeans</th></tr></thead><tbody><tr><td>Ablalone</td><td><strong>0.58 (0.00)</strong></td><td>0.58 (0.02)</td><td>-</td><td>0.57 (0.03)</td><td>0.55 (0.02)</td><td>-</td><td>-</td><td>0.51 (0.00)</td><td>0.50 (0.01)</td><td>-</td><td><strong>0.52 (0.02)</strong></td><td>0.49 (0.03)</td><td>-</td><td>-</td></tr><tr><td>Ecoli</td><td>0.89 (0.004)</td><td>0.83 (0.05)</td><td>-</td><td>0.81 (0.06)</td><td><strong>0.89 (0.02)</strong></td><td>-</td><td>-</td><td>0.82 (0.002)</td><td>0.74 (0.05)</td><td>-</td><td>0.71 (0.07)</td><td><strong>0.82 (0.03)</strong></td><td>-</td><td>-</td></tr><tr><td>Glass</td><td>0.64 (0.05)</td><td>0.63 (0.06)</td><td>-</td><td>-</td><td><strong>0.66 (0.005)</strong></td><td>0.64 (0.03)</td><td>-</td><td>0.55 (0.04)</td><td>0.54 (0.05)</td><td>-</td><td><strong>0.59 (0.002)</strong></td><td>0.57 (0.02)</td><td>-</td><td>-</td></tr><tr><td>BC</td><td>-</td><td>0.58 (0.00)</td><td>0.58 (0.00)</td><td><strong>0.58 (0.01)</strong></td><td>-</td><td>0.58 (0.00)</td><td>-</td><td>-</td><td>0.70 (0.00)</td><td>0.70 (0.00)</td><td><strong>0.71 (0.01)</strong></td><td>-</td><td>0.70 (0.00)</td><td>-</td></tr><tr><td>Lung</td><td>-</td><td>0.52 (0.06)</td><td>0.55 (0.06)</td><td>0.48 (0.12)</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.50 (0.03)</td><td>0.49 (0.05)</td><td>0.47 (0.07)</td><td>-</td><td><strong>0.53 (0.00)</strong></td><td>-</td></tr><tr><td>Soybean</td><td>-</td><td>0.79 (0.11)</td><td>0.91 (0.06)</td><td><strong>0.91 (0.02)</strong></td><td>-</td><td>0.91 (0.12)</td><td>-</td><td>-</td><td>0.70 (0.10)</td><td>0.87 (0.10)</td><td>0.70 (0.12)</td><td>-</td><td>1.00 (0.00)</td><td>-</td></tr><tr><td>ERing (Ecol.)</td><td>-</td><td>0.85 (0.04)</td><td>-</td><td>0.78 (0.04)</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.67 (0.08)</td><td>-</td><td>0.56 (0.08)</td><td>-</td><td>-</td><td><strong>0.81 (0.05)</strong></td></tr><tr><td>BM (Ecol.)</td><td>-</td><td>0.45 (0.10)</td><td>-</td><td><strong>0.57 (0.09)</strong></td><td>-</td><td>-</td><td>-</td><td>-</td><td><strong>0.47 (0.02)</strong></td><td>-</td><td>0.41 (0.05)</td><td>-</td><td>-</td><td>0.40 (0.02)</td></tr><tr><td>AF (Ecol.)</td><td>-</td><td>0.42 (0.04)</td><td>-</td><td>0.50 (0.07)</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.47 (0.02)</td><td>-</td><td><strong>0.51 (0.08)</strong></td><td>-</td><td>-</td><td>0.46 (0.04)</td></tr><tr><td>ERling (SoftDTW)</td><td>-</td><td><strong>0.90 (0.03)</strong></td><td>-</td><td>0.76 (0.02)</td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.70 (0.07)</td><td>-</td><td>0.55 (0.03)</td><td>-</td><td>-</td><td><strong>0.80 (0.06)</strong></td></tr><tr><td>BM (SoftDTW)</td><td>-</td><td>0.56 (0.05)</td><td>-</td><td><strong>0.59 (0.09)</strong></td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.47 (0.06)</td><td>-</td><td><strong>0.47 (0.07)</strong></td><td>-</td><td>-</td><td>0.40 (0.03)</td></tr><tr><td>AF (SoftDTW)</td><td>-</td><td>0.47 (0.08)</td><td>-</td><td><strong>0.53 (0.09)</strong></td><td>-</td><td>-</td><td>-</td><td>-</td><td>0.49 (0.06)</td><td>-</td><td><strong>0.50 (0.08)</strong></td><td>-</td><td>-</td><td>0.47 (0.00)</td></tr></tbody></table>

both Euclidean and Soft-DTW metrics are used, Soft-ECM demonstrates competitive performance, often surpassing TSKmeans, especially with Soft-DTW metrics on Accuracy. Overall, Soft-ECM performs well in about 83% of cases across different data types, and proves its versatility across multiple data types and metrics.

In conclusion, this experimentation confirms that Soft-ECM achieves comparable or superior performance to the benchmark algorithms used in this comparative experimentation. This is beyond the result of the Proposition 1, demonstrating the usefulness of a flexible problem formulation. In addition, it offers the advantage of a better fuzzy representation in uncertain data contexts.

## 5.3 Experiments with Time Series Data

Regarding time series datasets, a Euclidean metric and a semi-metric, the Dynamic Time Warping (DTW), are experimented. DTW is particularly useful for datasets with time series of different lengths or where there is temporal flexibility between instances of the same class. Since DTW is not a metric, new approaches have adapted clustering algorithms to DTW [PFW+14]. However, to our knowledge, no method performs credal partitioning of time series using DTW.
<figure><img src="image_9.png" /><figcaption>Figure 4: On top, plot of mass obtained using $L_2$ distance. On bottom, mass graph obtained by Soft-DTW.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 5: Illustration of the three-cluster raw-data on top: *Cylinder* (3 series in blue), *Bell* (3 series in green) and *Funnel* (3 series in red). On bottom, mass plot obtained by clustering with Soft-DTW for 2 classes (*Bell* and *Funnel*) and mixed examples (*Bell+Funnel*).</figcaption></figure>

In this section, we present the results of two experiments obtained on artificial time series analysis. They illustrate the relevance and ability of our algorithm to perform fuzzy partitioning of time series using DTW, or more specifically Soft-DTW [CB17], which is its differentiable version.

In a first experiment, we use classic synthetic time series, named *Cylinder-Bell-Funnel*, illustrated in Fig. 5. The dataset includes 50 items of each class. These items are grouped according to index: from 1 to 50, from 51 to 100 and from 101 to 150, to ease interpretation of the mass plots. To illustrate the flexibility of Soft-ECM, we applied it with two dissimilarity measures: the $L_2$ metric and the Soft-DTW semi-metric.

The results are shown in Fig. 4. The mass plots illustrate the expected partitioning for this dataset with $c = 3$. When we use the $L_2$ metric, the algorithm fails to identify the correct clusters. Indeed, the examples are assigned equal masses for the three clusters, whatever the true behavior of the time series. In contrast, with Soft-DTW, each expected cluster is mainly assigned to a singleton cluster, representing a better clustering. This experiment demonstrates that our algorithm effectively addresses the problem of fuzzy partitioning of time series, exploiting the advantages of Soft-DTW.

In a second experiment, we aim to demonstrate the advantages of fuzzy clustering for these time series. The previous task can be easily addressed using the DBA (DTW Barycenter Averaging) algorithm [PFW+14], but would not consider situations where time series could be fuzzily assigned to several classes because they mix two behaviors. In this experiment, we therefore used class *Bell*, class *Funnel* and a new class constructed by combining series *Bell+Funnel* ($M$-shaped time series).

Fig. 5 depicts the results obtained by Soft-ECM clustering with $c = 2$ and a Soft-DTW metric. We can see that the algorithm identifies two classes (here, the *Bell* and *Bell+Funnel* classes), and the third class is identified as a mixture of the first two. For other initializations, the algorithm identified sometimes *Bell* and *Funnel* as the two main clusters. These two results are acceptable for this synthetic data. Of particular interest is to show the ability of the model to identify examples as mixtures of the other two. This demonstrates that Soft-ECM is able to identify meaningful meta-clusters of time series.
# 6 Conclusion

In this paper, we have proposed a generalization of the Evidential C-Means algorithm, named Soft-ECM, to provide a fuzzy clustering solution adapted to complex data and not necessarily defined in a Euclidean space. Experimental results show that Soft-ECM is able to produce comparable or even superior performance to benchmark algorithms. Furthermore, we have shown the capability of Soft-ECM to effectively achieve a fuzzy clustering with new types of data and compared a semi-metric, such as time series with a Dynamic Time Warping. In addition, a major advantage for uncertain data analysis is its ability to offer a more effective representation of fuzziness. Although this extension introduces new hyperparameters and is based on a numerical solution scheme, the flexibility provided by Soft-ECM in the use of a semi-metric and the improved computation of meta-cluster barycenters highlight its relevance for a wide scope of problems. However, the sensitivity to the parameter $\lambda$ remains a limitation of the method. We now plan to improve the relaxation of the problem using bi-level optimization. In addition, an extension of experiments to other complex datasets are development directions for further evaluation of the robustness and efficiency of the algorithm.

# Acknowledgements

V. Antoine and A. Soubeiga acknowledge the support received from the Agence Nationale de la Recherche of the French government through the program 16-IDEX-0001 CAP 20-25.

# References

[AAK25] Benoît Albert, Violaine Antoine, and Jonas Koko. ECM+: An improved evidential c-means with adaptive distance. *Fuzzy Sets and Systems*, 498:109168, 2025.

[AQMD12] Violaine Antoine, Benjamin Quost, Marie-Hélène Masson, and Thierry Denœux. CECM: Constrained evidential C-Means algorithm. *Computational Statistics & Data Analysis*, 56(4):894–914, 2012.

[BEF84] James C. Bezdek, Robert Ehrlich, and William Full. FCM: The fuzzy C-Means clustering algorithm. *Computers & Geosciences*, 10(2):191–203, 1984.

[CB17] Marco Cuturi and Mathieu Blondel. Soft-DTW: a differentiable loss function for time-series. In *Proceedings of the International Conference on Machine Learning (ICML)*, volume 70, pages 894–903, 2017.

[DMACM19] Abdoul Jalil Djiberou Mahamadou, Violaine Antoine, Gregory J. Christie, and Sylvain Moreno. Evidential clustering for categorical data. In *Proceedings of the International Conference on Fuzzy Systems (FUZZ-IEEE)*, pages 1–6, 2019.

[DZ20] Stephan Dempe and Alain Zemkoho. Bilevel optimization. In *Optimization and its applications*, volume 161. Springer, 2020.

[FAT$^{+}$14] Adil Fahad, Najlaa Alshatri, Zahir Tari, Abdullah Alamri, Ibrahim Khalil, Albert Y. Zomaya, Sebti Foufou, and Abdelaziz Bouras. A survey of clustering algorithms for big data: Taxonomy and empirical analysis. *IEEE Transactions on Emerging Topics in Computing*, 2(03):267–279, 2014.

[HA85] Lawrence Hubert and Phipps Arabie. Comparing partitions. *Journal of classification*, 2:193–218, 1985.
[LDMP12] Zhun-Ga Liu, Jean Dezert, Grégoire Mercier, and Quan Pan. Belief C-Means: An extension of fuzzy C-Means algorithm in belief functions framework. *Pattern Recognition Letters*, 33(3):291-300, 2012.

[LPDM15] Zhun-Ga Liu, Quan Pan, Jean Dezert, and Grégoire Mercier. Credal C-Means clustering method based on belief functions. *Knowledge-Based Systems*, 74:119-132, 2015.

[MD08] Marie-Hélène Masson and Thierry Denœux. ECM: An evidential version of the fuzzy c-means algorithm. *Pattern Recognition*, 41(4):1384-1397, 2008.

[MD09] Marie-Hélène Masson and Thierry Denœux. RECM: Relational evidential C-Means algorithm. *Pattern Recognition Letters*, 30(11):1015-1026, 2009.

[PFW+14] François Petitjean, Germain Forestier, Geoffrey I Webb, Ann E Nicholson, Yanping Chen, and Eamonn Keogh. Dynamic time warping averaging of time series allows faster and more accurate classification. In *Proceedings of the International conference on data mining (ICDM)*, pages 470-479, 2014.

[PGC+17] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in PyTorch. In *Proceedings of the Conference on Neural Information Processing Systems (NIPS)*, 2017.

[Sha76] Glenn Shafer. *A mathematical theory of evidence*, volume 42. Princeton university press, 1976.

[ZMPL15] Kuang Zhou, Arnaud Martin, Quan Pan, and Zhunga Liu. Evidential relational clustering using medoids. In *Proceedings of the International Conference on Information Fusion (Fusion)*, pages 413-420, 2015.