# Comparative analysis of multidimensional sequential trajectories clustering methods

Armel Soubeiga, Violaine Antoine, Sylvain Moreno

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

## To cite this version:

Armel Soubeiga, Violaine Antoine, Sylvain Moreno. Comparative analysis of multidimensional sequential trajectories clustering methods. 2025. hal-05061916

HAL Id: hal-05061916

https://hal.science/hal-05061916v1

Preprint submitted on 9 May 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Comparative analysis of multidimensional sequential trajectories clustering methods

Armel Soubeiga<sup>a,*</sup>, Violaine Antoine<sup>a</sup>, Sylvain Moreno<sup>b</sup>

<sup>a</sup>University of Clermont Auvergne, CNRS, Mines of Saint-Etienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Fd, Clermont-Ferrand, France

<sup>b</sup>School of Interactive Arts and Technology, Simon Fraser University, Vancouver, Canada

## Abstract

Multidimensional sequence analysis is a central method widely used in social science research to identify underlying relationships between two or more trajectories observed simultaneously. This paper presents an extensive review of the existing methods for trajectory analysis, characterized by discrete or categorical longitudinal data, and provides an overview of their applications and differences in social science. The study focuses on non-parametric sequential clustering approaches, and compare various similarity measures applied on multidimensional sequences for both hard and soft clustering methods. Ccost and Cdist, two similarity measures for multivariate sequences have proven to be the most effective, but they are based on major assumptions concerning the interdependence of dimensions.

**Keywords:** Social Science trajectories, Care Trajectories, Hard and Soft Relational Clustering, Multidimensional Sequence Analysis, Time Series, Longitudinal Data

## 1. Introduction

Over recent decades, longitudinal data and time series datasets have multiplied in the form of panels, biographical surveys, and studies measured according to time or age. The larger volume of data collected presents new opportunities and new challenges in analyzing these data. Trajectory analysis, which is a major perspective in computational sciences for analyzing longitudinal data, allows us to study the evolution of markers such as behavior, event, or another measure of interest repeated over time. In practice, there are many methods for analyzing trajectories, and they can be applied to a variety of fields and themes. Depending on the research question and the data type, these methods can be modelling approaches or individual-centered statistical approaches, such as clustering. Clustering methods offer a unique advantage in identifying hidden patterns and structures within complex datasets, particularly in trajectory analysis. Trajectory clustering thus provides a detailed and understandable description of trajectory patterns between objects. Numerous researches have highlighted the importance of trajectory clustering in healthcare [1, 2].

The literature review on trajectory clustering studies reveals several definitions and formulations of trajectories, with no clear and comprehensive categorization of the different trajectory

<footnote>*Corresponding author.</footnote>

<footnote>Email addresses: armel.soubeiga@uca.fr (Armel Soubeiga), violaine.antoine@uca.fr (Violaine Antoine)</footnote>
types. Moreover, while review works generally focus on temporal and spatial trajectories, few comparative methodological and empirical papers have been published describing non-parametric clustering on sequential trajectories. Recently, [3] conducted an empirical comparison of two methods for multidimensional sequential trajectories, noted multichannel sequence clustering, using the Swiss Household Panel. These methods are sequential analyses by status combination and by cost combination, whereas the literature identifies five main methods [4]. In addition, their work highlights limitations such as selecting only complete sequences without missing data, relying on a single, relatively simple dataset, restricting the approach to one clustering algorithm, and using only edit distance-based measurement functions for computing sequence dissimilarities.

Our work extends their work by offering a comprehensive empirical comparison of the multidimensional sequential trajectories methods in the literature. These methods include the relational clustering, a medoid-based procedure applicable to non-metric proximity data, and methods inspired by multidimensional scaling. In addition to the two approaches mentioned above [3], we also examine the distance combination approach [5], the cluster combination approach [5], and the globally interdependent multiple sequence analysis approach [6]. In relational clustering, the measure of dissimilarity between pairs of trajectories is crucial [7]. We generate dissimilarity measures using different sets of trajectories and dissimilarity functions. In the literature, sequential clustering most often uses hard clustering algorithms as Ascending Hierarchical Classification (CAH) or Partitioning Around Medoids (PAM), both of which are relational clustering techniques using medoids. However, in many real-world applications, trajectory data can be ambiguous or uncertain, and in such cases, hard clustering may lead to insufficient accuracy. To address this issue and capture the degree of ambiguity, we add to the review two additional medoid-based soft relational partitioning algorithms [8, 9]. These variants allow expressing uncertainty and/or imprecision in clustering. The comparison is performed on different real datasets from various domains and simulated datasets were considered in this study. The main contributions can be summarized as follows:

1. We provide a review of the existing works in trajectory clustering, and propose a contextual background for the formulations and definitions of trajectories.

2. Rather than citing works chronologically, we draw up a road map categorizing these methods according to whether they work directly on the raw data, indirectly with features extracted from the raw data, or indirectly with models built from the raw data, with a focus on sequential trajectory clustering methods.

3. We propose an analysis of the most representative multidimensional sequential trajectory (MST) clustering methods, highlighting aspects of data, method process, application advantages and limitations. We also introduce a new approach to MST clustering based on multi-view relational clustering.

4. Finally, we highlight current challenges in MST clustering as well as the main opportunities for future work.

The subsequent sections of this paper are structured as follows. First, Section 2 presents a review of trajectory data and the main associated clustering methods. Next, Section 3 focuses on an extended analysis of clustering methods applied to sequential trajectories. Section 4 explores specific clustering methods for multidimensional sequential trajectories. In Section 5, an experimental comparison of multidimensional methods is conducted to evaluate their performance.
Finally, the Section 6 discusses the results obtained and highlights implications and perspectives for future work.

## 2. Review of trajectory data and clustering methods

### 2.1. Diverse formulations of trajectory definitions

Trajectory data is commonly represented as continuous repeated-measure data, such as continuous time series or continuous longitudinal data. Trajectory data can be differentiated based on sources as Global Positioning System (GPS), Global System for Mobile Communications (GSM), geolocated social networks, Radio-Frequency Identification (RFID), and WiFi based data. Trajectory data is generally examined in terms of the movements of people and objects, but can also include activities and events of objects [10]. Robette Nicolas introduced social trajectories, used in fields such as health, psychology, and sociology [4]. Trajectory data is part of contextual data representations, incorporating temporal or spatial properties. Although often treated as time series, trajectory data have more properties: they are ordered, spatial (location, orientation, speed, direction), dynamic (constantly changing), multidimensional, heterogeneous (comprising multiple variables from diverse sources), and temporal (repeated measures). Considering these properties, we can define four main types of trajectory, as illustrated in Figure 1. Sequential trajectories involve the ordering of events or states. Temporal trajectories concern the tracking of data over time. Spatial trajectories refer to the tracking of data in space. Finally, spatio-temporal trajectories cover the tracking of data in both space and time.

<figure><img src="image_3.png" /><figcaption>Figure 1: Possible classification of the different types of trajectories.</figcaption></figure>

Sequential trajectory refers to the order of events or states over time. It generally relates to categorical or discrete longitudinal data and categorical or discrete time series [4]. It is used in the human sciences and most often characterizes human trajectory or life course, such as care trajectory, consumption trajectory, etc, [4]. In sequential trajectories, time may not always be explicitly defined, and the trajectory is constructed based on a sequence of categorical measurements.

Temporal trajectory refers to the timeline of events of an object. Generally referred to as a movement trajectory, temporal trajectories are related to continuous time series data and often to continuous longitudinal data.

Spatial trajectories generally refer to a sequence of observations or measurements related to the location of an object. These trajectories are often treated similarly to spatio-temporal trajectories, but a spatial trajectory is essentially a trace generated by a moving object in geographic space [11]. Most research on trajectory clustering focuses on relational clustering [11].
Spatio-temporal or geometric-temporal trajectory refers to both the spatial and temporal in-
formation of an object or system, as it moves and changes over time in a given environment.
Spatial-temporal data is increasingly becoming universal as a result of the widespread use of GPS,
GSM, and RFID.

## 2.2. Diverse formulations for trajectory Clustering

Trajectory clustering methods are broadly categorized into non-parametric (feature-based or raw-data-based) and parametric (model-based) approaches [12]. Non-parametric approaches, which make no assumptions about data distribution, assign trajectories to clusters based on proximity or object data, while parametric approaches use probability models to infer cluster membership. Feature-based methods extract key features for clustering, while raw-data-based approaches work directly with the data, preserving its longitudinal structure. Model-based methods, on the other hand, rely on statistical models for clustering. Non-parametric methods, particularly raw-data-based approaches, are effective for complex trajectory data, allowing relational clustering algorithms to directly handle longitudinal patterns without assuming underlying distributions. Figure 2 illustrates the three major approaches: (a) feature-based, (b) raw-data-based, and (c) model-based.

<figure><img src="image_4.png" /><figcaption>Figure 2: Three trajectory clustering approaches: (a) feature-based, (b) raw-data-based, (c) model-based.</figcaption></figure>

Overview of trajectory clustering methods shows that some methods are based on object data, whereas the most methods are based on proximity data (relational clustering), i.e. a matrix of dissimilarities or distances between objects. Naturally, algorithms in the latter category can also be applied to object data after computing a distance matrix. Relational clustering approaches thus offer greater adaptability and allow the use of non-Euclidean distance metrics. This flexibility facilitates the efficient clustering of complex data, such as temporal, spatial and sequential data, which present hidden structures. Such data, which cannot be represented in a Euclidean space, are not compatible with object-based algorithms that are based on the properties of Euclidean spaces. Using an optimal distance function adapted to each type trajectory data or to each dimension in data considerably improves clustering performance [13].
Figure 3 illustrates the categorization of the main relational clustering algorithms frequently used for trajectory clustering [10]. Hierarchical methods produce a dendrogram, a nested structure of successive groups of input data. In contrast, partitioning methods generally aim to provide a unique partition of the data into a fixed number of clusters, often by locally optimizing an objective function. Partitioning methods can be hard partitioning, such as Partitioning Around Medoids (PAM) [14], or soft partitioning, which includes fuzzy algorithms, such as Fuzzy c-medoids algorithm (FCMdd) [8]. Soft partitioning methods also include evidential clustering algorithms, such as Evidential c-medoids [9].

<figure><img src="image_5.png" /><figcaption>Figure 3: An overview of relational clustering algorithms.</figcaption></figure>

## 2.3. *Trajectory similarity measures*

Computing the similarity between pairs of trajectories is a fundamental operation in trajectory analytics that is necessary for distance-based clustering of trajectories (cf. Section 2.2). The similarity, used to determine the distance between two trajectories, can be defined as the cost of transforming one trajectory into another based on a specific similarity function.

Prior research has reviewed four basic measures, including Euclidean distance (ED), Dynamic Time Warping (DTW), Longest Common Subsequence (LCS), and Fréchet distance [15]. Recent work presents an empirical comparative evaluation of popular trajectory similarity functions [16, 7]. Comparisons are based on several criteria, including metric and non-metric properties. A distance function is metric if it respects uniqueness, symmetry, non-negativity and triangle inequality. Another distinction is between discrete and continuous measures, depending on the format of the trajectories. Finally, criteria such as point offset or length variation, as well as robustness to noise, outliers and missing data, are also taken into account.

We propose a classification of the most important and commonly used similarity measures based on the type and format of the trajectories (see Figure 4). For distance measures within the same category, theoretically, they have the same targeted information type (continuous or categorical) and the same requirement of trajectory data type (sequential, temporal only, or spatio-temporal trajectories).

It is worth noting that this classification is not unique, and many other aspects can be used to connect and distinguish those distance measures. For example, ED [7], DTW [15], STLC
<figure><img src="image_6.png" /><figcaption>Figure 4: Categorization of trajectory distance measures.</figcaption></figure>

(spatio-temporal linear combine) [7], Fréchet distance [15, 16], spatio-temporal Euclidean distance (STED)[7], and spatial locality in-between polylines (SLIP) are all derived by calculating the Euclidean distance between certain parts of the given two trajectories. While edit distance on real sequence (EDR) [16], edit distance with real penalty (ERP)[16], edit distance with projections (EDwP) [7], LCS, and spatio-temporal longest common subsequence (STLCSS) [15, 7] actually reflect the proportion of the two trajectories that are close to each other based on a distance function. From the perspective of the use of distance functions, they can be grouped into the $L_{p-norm}$ family (ED, optimal matching (OM), DTW, STLC, Fréchet distance, STED and SLIP) and edit distance family (EDR, ERP, EDwP, LCS and STLCSS) [17].

# 3. Review of sequential trajectory clustering

## 3.1. Related sequential trajectory data

Sequential trajectories or categorical sequences are used to describe the evolutionary state of the process under study. In social sciences, sequences are defined through longitudinal categorical or discrete data. In computer science, sequential trajectories are defined as categorical time series. Longitudinal and time series data are confusing when it comes to analyze trajectory data. There are no strict and formal definitions on which a large number of data analysts agree. In the literature, only a brief definition is sometimes given [18]. Thus, we propose the following definitions (cf. Figure 5): time series data refer to observations (values) of a single object collected over an extended time period. Cross-sectional data, in contrast, consists of observations (values) of multiple objects at a single time point. Longitudinal data (or panel data), involves multiple objects observed at multiple time points. Longitudinal data are often referred to as cross-sectional time series, because they incorporate both temporal information based on multiple objects.
<figure><img src="image_7.png" /><figcaption>Figure 5: Illustration of categorical or discrete time series and longitudinal data.</figcaption></figure>

Categorical or discrete longitudinal data and time series, can be structured as a three-dimensional tensor $\mathbf{X}$ defined by items $N$, variables $M$, and time points $T$, where each cell $x_{jt}^{(i)} \in \mathbb{Z}$ represents a finite measurement for object $i$ at time $t$ on feature $j$. Both longitudinal and time series data can be balanced or unbalanced ($T^{(i)} = T$), spaced equally or unequally in time, and impacted by missing data, with $T^{(i)} \le T$. Specific properties of longitudinal data allow for a lag, or the temporal difference $|T_t^{(i)} - T_l^{(i)}|$ between two objects. Longitudinal data can be formatted as long or wide. Wide format accommodates balanced data and places all subject $i$ data in one row, while long format uses one row per observation. When $M > 1$, we refer to multidimensional (in contrast to unidimensional) longitudinal data or multivariate (versus univariate) time series. In this case, the trajectories studied are multidimensional sequential trajectories. However, in this section, we focus first on one-dimensional sequential trajectories for $M = 1$.

## 3.2. Related works on sequential trajectory clustering

Model-based clustering approaches was early work for sequential trajectory clustering. Commonly used techniques include latent class modeling approaches, i.e. growth mixture modeling (GMM), group-based trajectory modeling (GBTM), latent class analysis (LCA) and latent transition analysis (LTA). Indeed, latent class modeling approaches have long been used in the social sciences and in healthcare [1]. Other model-based clustering approach including Markov models (MM) and its variants, have been studied in the literature [19].

Feature-based clustering approaches are often explored first for trajectory clustering, because they simplify the complexity related to the temporal dimension. Feature extraction transforms data into a cross-sectional tabular format. Although most extraction methods are generic, the specific features extracted generally depend on the application. For sequential trajectories, extracted features can include entropy measures such as Gini dispersion, Shannon, Chebycheff, and other measures such as, uncertainty coefficient, Pearson measure, Sakoda measure, $\Phi^2$-measure, see [20]
for a detailed review of candidate features. Feature-based clustering approaches use both existing object-based clustering algorithms and existing relational clustering algorithms. In work on evidential clustering of chronic pain trajectories from discrete and categorical time series, Soubeiga, A. and al. [2], combined feature extraction and feature selection techniques.

State-of-the-art of Row-data-based clustering of sequential trajectory shows that the most popular works are often extensions of traditional clustering algorithms to consider the temporal dimension (object-based clustering), or relational clustering algorithms with adapted similarity measures[4]. Table 1 summarizes the strengths and limitations of the model-based, feature-based, and row-data-based clustering approaches, highlighting the key advantages and challenges of each method.

<table><caption>Table 1: Strengths and limitations of sequential trajectory clustering approaches.</caption><thead><tr><td>Approach</td><td>Strengths</td><td>Limitations</td></tr></thead><tbody><tr><td>Model-based</td><td><ul><li>Directly models the underlying dynamics.</li><li>Good at handling noise and uncertainty using probabilities.</li></ul></td><td><ul><li>Assumptions about the model can be too strict.</li><li>Sensitive to model specification.</li></ul></td></tr><tr><td>Feature-based</td><td><ul><li>Extracts useful features (statistical summaries, metrics) to simplify comparison.</li><li>Reduced dimensionality helps with analysis and interpretation.</li></ul></td><td><ul><li>May lose fine dynamic or structural details.</li><li>Clustering quality depends heavily on the chosen features.</li><li>Requires a solid feature engineering.</li></ul></td></tr><tr><td>Row data-based (Including distance-based and object-based)</td><td><ul><li>Uses raw data, preserving all inherent information.</li><li>Flexible in choosing similarity measures (distance, alignment, ...).</li></ul></td><td><ul><li>Computation-intensive, especially for large datasets or long series.</li><li>Needs careful selection of the distance measure to properly reflect similarity.</li></ul></td></tr></tbody></table>

Our work focuses on Row-data-based clustering of sequential trajectory using relational or proximity data (distance-based methods) and we propose a comparative framework of multidimensional sequential trajectories clustering. In a distance-based cluster approach, trajectories are clustered based on their pairwise similarity. This approach comprises two main steps. The first step consists of a sequential analysis, including the extraction and processing of sequences and the calculation of proximity data between sequences. The main goal of sequence analysis is the knowledge discovery from event or state sequences describing trajectories. The second step consists in applying a clustering algorithm based on these relational data. The advantage of a distance-based approach is that domain knowledge can be taken into account in specifying the distance measure to capture the
relevant properties of the trajectories. Another advantage is that the pairwise distances between trajectories yields a hierarchy which provides additional information on the sequential trajectory.

In the next subsections, we describe the steps to cluster sequential trajectories. Figure 6 summarizes the de various stages.

<figure><img src="image_8.png" /><figcaption>Figure 6: General framework of raw-data distance-based sequential trajectory clustering.</figcaption></figure>

### 3.2.1. Sequential trajectory data processing

Sequence mining and/or construction from categorical or discrete longitudinal or time series data is the first step in the sequential trajectory analysis. But in many instances, sequences are not directly present or visible in the data, and have to be reconstructed. Sequence construction is a laborious task, due to the nature of trajectory data. Moreover, the literature contains few references to help identify the main formats and types of structure of sequential data. The following ontology can be used to define and describe the main formats and representations of sequences. Indeed, the main difference between sequences is that they contain states or events [4]. Both are referred to as status at a point in time. It is also important to determine whether status alignment is based on an internal temporal reference (where temporality is explicitly defined) or on an external reference (where temporality is missing). Based on the characteristics of trajectory source data, we can highlight the following commonly used sequential representations:

* The states sequence (STS) format: STS is an intuitive and common representation where successive states of an individual are listed in consecutive columns. Each column typically corresponds to a predetermined time unit, but it can also handle sequences without time references.

* The state permanence sequence (SPS) format: in SPS, each distinct state in the sequence is paired with its duration. In one variant, state/duration pairs are enclosed in parentheses.

* The distinct successive state (DSS) format: DSS provides more compact representations by listing only one of several identical successive states.

* The vertical time-stamped event (TSE) format: TSE lists the events experienced by an individual along with the time of occurrence, allowing sequences of events to be constructed easily from this format. Events are listed from the first significant change of state, instead of starting with the initial state.

Consider the treatment trajectory of patient *i* with a serious chronic pathology, where their care pathway is tracked monthly for one year from diagnosis. The variable *j* records the patient's care status for each month of follow-up. Different representations of their treatment sequence $S_j^{(i)}$ are shown in Figure 7. Each state in the sequence is chosen from a finite domain or alphabet
$\Sigma = \{D, C, T, S\}$, which defines the set of all possible care statuses that a patient can experience during follow-up. $|\Sigma|$ is the number of states in the alphabet, i.e. the cardinality.

<figure><img src="image_9.png" /><figcaption>Figure 7: Examples of Sequence data representations.</figcaption></figure>

In sequential analysis, it has been shown that the methods used to handle missing data have a significant impact on the results. For sequential clustering, the choice of imputation method directly affects the dissimilarity measure and can even determine which measure should be used. The three most common strategies for addressing missing data in sequences are: treating missing data as an additional state in the alphabet, imputing it, or simply deleting any missing data. The first strategy is generally applied to non-random missingness, where its presence is meaningful, as opposed to missing completely at random or missing at random. Gap coding treats missing values as distinct states, creating a separate alphabet for them. Imputation can be simple (mean, median, mode) or multiple. Multiple imputation, based on predictive methods such as random forest or multinomial regression models, considers the longitudinal nature of the data, allowing covariates, including time-dependent ones, to be included in the model.

### 3.2.2. Sequential trajectory similarity functions

A measure of sequential dissimilarity quantitatively assesses the degree of dissimilarity between two sequences, providing insights into their resemblance. Sequential trajectory dissimilarity measures can be classified into three categories [4]: i) Distribution-based measures; ii) Attribute-based measures counting common attributes across sequences; and iii) Edit distances, which assess the cost of operations required to transform one sequence into another.

**Distances between probability distributions.** The first approach distributions-based used to measure the dissimilarity between sequences is based on the representation of the longitudinal states as distribution vectors. For example, in the example sequence in Figure 7, the state distribution is (4/12, 2/12, 3/12, 3/12). Given these distribution vectors, the dissimilarity between two sequences is evaluated via Euclidean or Chi-square (Chi) distance. The squared Chi-square measure weights the squared differences for each state by the inverse of the overall proportion of time spent for the state, gives more importance to a rare state than to a frequent state. Chi-square is sensitive to the duration parameter and robust for sequencing and timing. Let $p_k|s_1$ be the proportion of time spent in state $k$ in sequence $s_1$, and $p_k$ the overall proportion of time spent in state $k$, the Chi distance reads as follows:
$$d_{Chi}(s_1, s_2) = \sum_{k=1}^{|\Sigma|} \frac{(p_{k|s_1} - p_{k|s_2})^2}{p_k}. \qquad (1)$$

**Distances based on counts of common attributes or attribute-based.** These are dis-similarity measures based on the common subsequences which LCS measure. They are adapted to handle transitions between state while they take into account the order in the sequence. They are also able to handle sequences of different lengths. If $A(s_1, s_2)$ is the number of common attributes, between sequence $s_1$ and $s_2$ then the sequences are close for a large value of $A(s_1, s_2)$ and dissimilarity measure is as follows:

$$d(s_1, s_2) = A(s_1, s_1) + A(s_2, s_2) - 2A(s_1, s_2). \qquad (2)$$

The dissimilarity is maximal when $A(s_1, s_2) = 0$, i.e., when the two sequences have no common attribute. We can mention two attribute-based dissimilarities introduced by C. Elzinga [21] in Sequence similarity: the longest common prefix (LCP) and the longest common subsequence (LCS). LCP use the number of successive common positions starting from the beginning of the sequences, that can be noted $A_p(s_1, s_2)$. A derivative of LCP is the reversed longest common prefix or longest common suffix (RLCP). It looks for the common elements from the end rather than from the beginning of the sequences. For LCS, it use the number of common consecutive states in the subsequence $A_s(s_1, s_2)$. Thus in the same way, the Simple Hamming distance measures the dissimilarity between two sequences by the number of positions with non-matching states. It applies only to pairs of sequences of the same length and is very sensitive to timing mismatches. We get the Hamming distance with Equation 2 by using $A_h(s_1, s_2)/2$ as proximity measure, where $A_h(s_1, s_2)$ is the number of no-matching positions.

**Edit distances or optimal matching (OM).** OM transforms the sequence $s_1$ into the sequence $s_2$ using three possible operations: insertion, deletion, and substitution. Dissimilarity is computed as the cost associated to the smallest number of operations. Let $A_i = A_1, ..., A_\ell$ be a set sequence of actions (insertion, deletion and substitution) of length $\ell$ to transform the sequence $s_1$ to $s_2$. And $A_i(E^k, E^{k'})$ is the action for aligning $E^k$, the $k^{th}$ state of $s_1$ against $E^{k'}$, the $k'^{th}$ state of $s_2$. We can use several possible action sequences to match the two sequences. Considering this, let $A_i^j = A_1^j, ..., A_{\ell_j}^j$, be the set of all possible transformations and $\gamma(A_i^j) \in \mathbb{R}_0^+$ the cost of each action or elementary transformation. The OM dissimilarity is then:

$$d_{OM}(s_1, s_2) = \min_j \sum_{i=1}^{\ell_j} \gamma(A_i^j). \qquad (3)$$

The method seems simple and relatively intuitive, but the choice of the costs is a delicate operation. Generally insertion and delete actions have the same cost and are called indel action. Substitution costs can be theoretical or empirical, for the empirical case, the costs are determined from the estimated transition rates. Among the main variants of OM, we can mention Generalised Hamming distance and Levenshtein II. The generalised Hamming distance does not allow indels while Levenshtein II distance discards substitutions and measures the distance by counting the number of indels necessary to transform one sequence into another. Dynamic Hamming distance (DHD) [22] focuses on OM without indels, such as generalized Hamming, and proposed that
substitution costs should depend on the position *t* in the sequence. Localised OM [23] aims to make indel costs dependent on the two adjacent states. The motivation is that inserting or deleting a state similar to its neighbors would only change the length of the spell in that state, without affecting the sequencing. Other edit distances have been proposed for specific sequences. For example, the Time Warp Edit Distance (TWED) is a distance measure for matching discrete time series with temporal elasticity [24].

### 3.2.3. Relational clustering of sequential trajectory

Sequential analysis allows the construction of trajectories from categorical longitudinal data or categorical time series (sequential processing) and the measurement of similarities between these trajectories (sequential similarity), as shown in Figure 8. Relational clustering allows to group objects from the distance matrix between trajectories obtained with the dissimilarity measure. In the literature, sequential trajectory clustering are often based on algorithms like Ascending Hierarchical Classification (CAH) with usually Ward aggregation method or Partitioning Around Medoids (PAM) [4], and are both relational clustering techniques using medoids. In this work, we include two soft relational partitioning algorithms, as fuzzy and evidential clustering, presented in Figure 3. We used medoid-based versions of soft clustering algorithms such as relational fuzzy c-medoids (FCMdd) [8] and relational evidential c-medoids (ECMdd) [9]. Medoid-based clustering offers the advantage of not requiring the distance or dissimilarity matrices between trajectories to be Euclidean, as is the case with mean-based clustering approaches or c-mean relational algorithms. Indeed, this will enable us to explore and use several optimal distance functions for each trajectory dimension.

## 4. Review of multidimensional sequential trajectory clustering

Figure 8 illustrates the clustering process of sequential trajectories, from raw longitudinal data to the final partitioning. The framework integrates both unidimensional and multidimensional sequential trajectory clustering (MST). It follows a structured pipeline, starting with data preprocessing, followed by similarity computation, and finally relational clustering and cluster validation.

<figure><img src="image_10.png" /><figcaption>Figure 8: Illustration of the clustering process of sequential trajectories.</figcaption></figure>

### 4.1. Definitions and concepts of multidimensional sequential trajectory

Let $\chi$ be a three-tensor multichannel sequence data constituted a set of *N* individuals in $\mathbb{Z}^{N \times M \times T}$. The trajectory $\tau^{(i)}$ of an individual *i* can be defined as the set of sequences $S_j$ (see
Figure 9), with $j = 1, \dots, M$. The sequence $S_j$ of the variable $j$ is a list of states or events $E_t^{(k)}$, ordered by $t = 1, \dots, T^{(i)}$ chosen from a finite alphabet $\Sigma$ (sequence domain), with $k = 1, \dots, \Sigma$. An alphabet is the set of all possible states that can appear in the sequences. A sequence $S_j$ can be represented as a succession of pairs $(E_t, T_t)$, with $E_t$ representing a state and $T_t$ a date of state measurement.

<figure><img src="image_11.png" /><figcaption>Figure 9: Illustration of a sequence extraction ($S^{(i)}$) and a trajectory or pathway construction ($\tau^{(i)}$) from multidimensional longitudinal data $\chi$.</figcaption></figure>

## 4.2. Review of row-data-based clustering for MST

In multidimensional sequence analysis (processing multiple sequences and/or computing similarities between them), it is often complex to simplify successive sequence elements into a unique and limited set of states. Methodological adaptations is then necessary to handle the diversity and complexity of the status [3]. The concept of measuring similarity in sequences has traditionally focused on unidimensional data. However, the extension to multidimensional sequences has been explored, and adapted measures, such as LCS or DTW are used to compare multidimensional sequential trajectories. Clustering methods for multidimensional sequential trajectory found in the literature can be grouped into five main categories.

**Combination of states (Cstat).** Cstat consists of creating a new state variable that combines the simple states composing each dimension [3]. For example, in the case of the care trajectories defined in Section 3.2.1, one can notice that the care status variable is a result of combinations of states. Possible non-combined states would include: diagnosed/not diagnosed, on treatment/not on treatment; suppressed infection/infection not suppressed, in care/not in care. But in certain cases, this can quickly lead to a large alphabet, i.e. a very large set of states. Thus, in the case of four dimensions each containing three simple states, the combined variable would potentially have $3 \times 3 \times 3 \times 3 = 81$ states. Such an extension of the alphabet may be impractical with optimal matching when it comes to setting substitution costs specifically adapted to each pair of states.

**Combination of costs (Ccost).** Ccost method, most common and often called multiple sequence analysis (MSA) or multichannel sequence analysis (MCSA), is based on combining the costs of substitution matching actions between different dimensions. A possible combination is to
sum or average the costs defined for each dimension [3], or to apply weighted sum [25]. In practice, taking into account multiple dimension within an OM framework, as defined by equation 3, is relatively simple and only requires adapting the substitution costs and the indel costs, so that they reflect the relationship between equivalent dimension. The multichannel version of these terms can be expressed as follows:

$$ \Gamma^{sub}(E^k, E^{k'}) = \frac{\sum_{c=1}^{N^c} \gamma^{sub^c}(E^k, E^{k'})}{N^c}; \quad \Gamma^{ind}(E^k, E^{k'}) = \frac{\sum_{c=1}^{N^c} \gamma^{ind^c}(E^k, E^{k'})}{N^c}. \quad (4) $$

with $N^c$ the number of channel or dimension, and $(E^k, E^{k'}) \in \Sigma^c$ the alphabet of each dimension studied. $\gamma^{sub^c}$ and $\gamma^{ind^c}$ are respectively the specific substitution and indel cost matrices associated with each dimension studied.

**Combination of distance (Cdist).** Cdist method consists of computing a distance matrix for each sequence dimension separately, then combining them into a single distance matrix by a linear combination [26].

**Combination of clusters (Cclust).** Cclust method uses sequence clustering created separately for each sequence dimension and then deriving the joint final cluster from clustering constructed for each dimension [26]. This approach is not widely adopted because of its limites to generate a large number of clusters, which quickly become sparse as the number of dimensions increases.

**Globally Interdependent Multiple Sequence Analysis (GIMSA) [6].** GIMSA method computes a distance matrix for each dimension, then uses multidimensional scaling (MDS) followed by multiple factor analysis techniques like symmetrical or canonical Partial Least Squares (PLS). First, Optimal Matching (OM) or another dissimilarity measure calculates distances within each dimension. Next, MDS reduces the dimensionality of each dissimilarity matrix, mapping objects while preserving pairwise distances. Given a multiple dissimilarity matrix D, MDS finds the largest eigenvalues of each matrix and, symmetric PLS combines them to maximize covariance, based for their linear relationships and structural strength.

### 4.3. Characteristics and taxonomy

Cstat, Ccost, Cdist, Cclust, and GIMSA methods can be systematically compared and classified according to the criteria multidimensionality, parsimony and interdependence [4] in Table 2. Multidimensionality refers to the explicit and flexible contribution of each sequential dimension to the final clustering results. Cstat method masks dimensions by combining multiple sequences into a single one. For example, it is not possible to have specific parameters for each dimension, or to evaluate the impact of each dimension on the results. Parsimony refers to the question of whether a method can produce a limited number of trajectory clusters. Cclust method leads to a high number of clusters. Interdependence refers to the consideration of relationships between dimensions. In Cdist, the relationship between multiple sequences is hidden. Methods Cstat and Ccost, focus on the dependency between dimensions transversely, at each point of the sequence. In Clust and GIMSA methods, the focus is on the dependency between dimensions via global sequences. We can also categorize methods according to the type of approach. This is the step at which multidimensionality is taken into account in the diagram in figure 8. Distance matrices are
computed independently for each dimension in Cdist, Cclust and GIMSA, and different dissimilarity measures can be used. The dissimilarity matrix for each sequence can be computed based on the same distance function. Different distance functions can be used for each sequence dimension [4]. For the Ccost method, it is relatively related to the OM distance family.

<table><caption>Table 2: Taxonomy of multidimensional sequence analysis strategies.</caption><thead><tr><th>Methods</th><th>Multidimensional Parsimony</th><th>Interdependence</th><th>Type</th></tr></thead><tbody><tr><td>1 - Combination of states (Cstat)</td><td><strong>No</strong></td><td>Yes</td><td>Processing</td></tr><tr><td>2 - Combination of costs (Ccost)</td><td>Yes</td><td>Yes</td><td>Similarity</td></tr><tr><td>3 - Combination of distance (Cdist)</td><td>Yes</td><td>Yes</td><td>Clustering</td></tr><tr><td>4 - Combination of clusters (Cclust)</td><td>Yes</td><td><strong>No</strong></td><td><strong>No</strong></td></tr><tr><td>5 - Globally Interdependent Multiple Sequence Analysis (GIMSA)</td><td>Yes</td><td>Yes</td><td>Similarity</td></tr></tbody></table>

# 5. Experimental comparison of multidimensional methods

## 5.1. *Experimental setting*

To compare the performance of the five MST clustering methods, both synthetic and real datasets described by categorical, ordinal, and discrete sequences are considered. Several dissimilarity matrices were computed in line with the recommendations of the five approaches (Section 4) to account for multichannel sequences. Among the most commonly used methods for treating missing data in sequences, described in Section 3.2.1, multiple imputation via the random forest model or adding a new status for missing values were explored. Motivated to the literature [25], we use the following dissimilarity measures. For synthetic data, we use optimal matching with substitution costs based on transition rates. For real data, the optimal distance for each dimension is selected from among OM, HAM, TWED, LCS, CHI2, and EUCLID. All matrices were normalized based on overall dispersion, i.e. in each matrix, dissimilarities $d(e_k, e_{k'})$ are normalized as $d(e_k, e_{k'})/T$, where $T = \sum_{k=1}^{n} d(e_k, g)$, and $g$ is the overall prototype of the matrix, computed as $l = \arg\min_{1 \le h \le h' \le n} \sum_{k=1}^{n} d(e_k, e_{h'})$.

Relational clustering algorithms, as described in Section 3.2.3, are used to partition the dissimilarity matrices generated by each approach, according to 8 workflow. The relational hard clustering algorithms CAH and PAM is applied to these proximity data to obtain a set of groups $\mathcal{G} = (G_1, \dots, G_K)$. FCMdd is also applied to these matrices to initially produce a fuzzy partition into $K$ fuzzy clusters. Subsequently, a hard partition $\mathcal{G} = (G_1, \dots, G_K)$ is derived from this fuzzy partition by defining the hard cluster $G_k(k = 1, \dots, K)$ as $G_k = \{\mathbf{x}_i : u_{ik} \ge u_{im} \quad \forall m \in \{1, \dots, K\}\}$. ECMdd is similarly applied to these similarity matrices to initially establish a credal partition into $2^K$ credal clusters. Then, a hard partition $\mathcal{G} = (G_1, \dots, G_{2^K})$ is derived from this credal partition by a pignistic transformation [9]. The quantity $u_{ik}$ represents the membership degree of object
$\mathbf{x}_i(i = 1, \dots, n)$ in fuzzy cluster $k(k = 1, \dots, K)$. The quantity $m_{ik}$ indicates the membership belief of object $\mathbf{x}_i(i = 1, \dots, n)$ in credal cluster $k(k = 1, \dots, 2^K)$. Each relational clustering algorithm was run (until the convergence to a stationary value of the adequacy criterion) 50 times and the best result was selected according to the adequacy criterion (minimum of the objective function).

To compare the clustering results, an external criteria, such as the corrected Rand index (CR), and internal criteria, like the Average Silhouette Width (ASW) and Hubert's C (HC) index, are considered. Clustering validation criteria include CR [-1, 1] and ASW [-1, 1], both maximized for better clustering, and HC [0, 1], minimized for closer alignment with the ideal partition. The experiments were conducted on a high-performance computing (HPC) server. The server is equipped with two AMD EPYC 7452 32-Core processors, offering a total of 64 physical cores with hyper-threading, and 512 GB of RAM. These powerful hardware specifications enabled efficient and accurate execution of the experiments, ensuring reliable results. The programs were implemented using R version 3.6.3.

## 5.2. Synthetic categorical longitudinal data

We simulated data for two multidimensional sequential trajectories characterized by longitudinal categorical and/or ordinal data sets. First one dataset includes two independent variables, a three-modality categorical variable and a four-modality ordinal variable, while the second one contains four variables comprising two correlated ordinal variables with three and four modalities and two independent categorical variables with three and four modalities. Each data set contains 150 objects split into four groups of different sizes, distributed according to distinct probability distributions. More details on the model simulations are available in Appendix A.

We build the sequences of each trajectory, containing 2 and 4 sequences respectively. Dissimilarity between pairs of sequences is calculated using the OM measure for both datasets. Depending to MST, one or more dissimilarity matrices are calculated for each trajectory. For the Cstat, Ccost and GIMSA methods, a single dissimilarity matrix is obtained. Cdist and Cclust, in contrast, generate one dissimilarity matrix per sequence. The CAH, PAM, FCMdd and ECMdd clustering algorithms were applied to the dissimilarity matrices to obtain a four-cluster partition, whether hard, fuzzy or credal. The hard cluster partitions (obtained from the fuzzy or credal partition transformation, or obtained directly from CAH and PAM) were compared with the class partition known a priori. Table 3 shows the performance of the CAH, PAM, FCMdd and ECMdd clustering algorithms for each of the Cstat, Ccost, Cdist, Cclust and GIMSA multidimensional sequential approaches. Performance was evaluated using the CR index.

Table 3 shows that Cdist method performed the best on both synthetic datasets, achieving the highest values of the Rand index. This means that this method successfully clustered multidimensional data in a manner consistent with the real class structure. Among the algorithms used by the Cdist method, PAM performed best on synthetic dataset 1, with a value of 0.674, while ECMdd performed best on synthetic dataset 2, with a value of 0.663. These algorithms were able to find the optimal cluster medoids, taking into account the different dissimilarities between the variables. The other methods and algorithms exhibited lower or similar performance, depending on the variance between variables and between classes.
<table><caption>Table 3: Performance of the multidimensional sequential clustering approaches on the synthetic datasets: The Rand index.</caption><thead><tr><th rowspan="2">Methods</th><th colspan="4">Synthetic dataset 1</th><th colspan="4">Synthetic dataset 2</th></tr><tr><th>CAH</th><th>PAM</th><th>FCMdd</th><th>ECMdd</th><th>CAH</th><th>PAM</th><th>FCMdd</th><th>ECMdd</th></tr></thead><tbody><tr><td>Cstat</td><td>0.583</td><td>0.605</td><td>0.554</td><td>0.628</td><td>0.582</td><td>0.588</td><td>0.572</td><td>0.607</td></tr><tr><td>Ccost</td><td>0.528</td><td>0.612</td><td>0.282</td><td>0.645</td><td>0.576</td><td>0.596</td><td>0.496</td><td>0.612</td></tr><tr><td>Cdist</td><td>0.593</td><td>0.674</td><td>0.500</td><td>0.602</td><td>0.590</td><td>0.606</td><td>0.471</td><td>0.663</td></tr><tr><td>Cclust</td><td>0.575</td><td>0.614</td><td>0.502</td><td>0.637</td><td>0.529</td><td>0.612</td><td>0.501</td><td>0.649</td></tr><tr><td>GIMSA</td><td>0.594</td><td>0.594</td><td>0.567</td><td>0.502</td><td>0.529</td><td>0.608</td><td>0.507</td><td>0.643</td></tr></tbody></table>

### 5.3. The biofam dataset

The biofam dataset<fnref n="1" /> contains individuals aged 30 or over at the time of the survey. The dataset examines trajectories of family life between the ages of 15 and 30, focusing on aspects such as residence status, marital status, and parenthood. This random sample of 2,000 individuals provides 16 years of follow-up per individual, resulting in 32,000 observations for each of the three dimensions.

In this study, we aimed to obtain a five-class clustering using two different configurations for dissimilarity calculation. The first configuration applied standard OM across all dimensions, while the second used LCS for residence status, CHI2 for parenthood, and OM for marital status. This choice is motivated by the characteristics of the variables and similarity measures. The CAH, PAM, FCMdd, and ECMdd clustering algorithms were applied to the dissimilarity matrices to generate hard, fuzzy, and credal partitions into five clusters, which were compared through internal performance criteria, ASW and HC. Table 4 and Table 5 show the performance of the CAH, PAM, FCMdd and ECMdd clustering algorithms for each of the Cstat, Ccost, Cdist, Cclust and GIMSA multidimensional sequential approaches. Performance was evaluated using the ASW and HC index.

<table><caption>Table 4: Performance of the multidimensional sequential clustering approaches on the biofam dataset with Standard OM dissimilarity function.</caption><thead><tr><th rowspan="2">Methods</th><th colspan="2">CAH</th><th colspan="2">PAM</th><th colspan="2">FCMdd</th><th colspan="2">ECMdd</th></tr><tr><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th></tr></thead><tbody><tr><td>Cstat</td><td>0.344</td><td>0.139</td><td>0.433</td><td>0.089</td><td>0.318</td><td>0.165</td><td>0.433</td><td>0.089</td></tr><tr><td>Ccost</td><td>0.367</td><td>0.093</td><td>0.394</td><td>0.087</td><td>0.330</td><td>0.101</td><td>0.356</td><td>0.092</td></tr><tr><td>Cdist</td><td>0.369</td><td>0.017</td><td>0.404</td><td>0.025</td><td>0.376</td><td>0.097</td><td>0.336</td><td>0.037</td></tr><tr><td>Cclust</td><td>0.363</td><td>0.091</td><td>0.399</td><td>0.083</td><td>0.337</td><td>0.096</td><td>0.403</td><td>0.079</td></tr><tr><td>GIMSA</td><td>0.339</td><td>0.097</td><td>0.362</td><td>0.156</td><td>0.260</td><td>0.252</td><td>0.357</td><td>0.154</td></tr></tbody></table>

Tables 4 and 5 compare the performance of multidimensional sequential clustering methods on the biofam dataset. The Table 4 is based on OM dissimilarities for all dimensions, while the Table 5 uses OM, LCS and CIH2 dissimilarities for each of the three dimensions. The PAM and ECMdd algorithms display the highest performance in terms of silhouettes (ASW) and stability (HC) of the final partitions. For the Cstat method, PAM and ECMdd show similar ASW and HC values,

<footnote n="1">¹https://rdrr.io/cran/TraMineR/man/biofam.html</footnote>
<table><caption>Table 5: Performance of the multidimensional sequential clustering approaches on the biofam dataset with Standard OM, LCS and CHI2 dissimilarities functions.</caption><thead><tr><th rowspan="2">Methods</th><th colspan="2">CAH</th><th colspan="2">PAM</th><th colspan="2">FCMdd</th><th colspan="2">ECMdd</th></tr><tr><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th></tr></thead><tbody><tr><td>Cdist</td><td>0.474</td><td>0.042</td><td>0.508</td><td>0.048</td><td>0.515</td><td>0.055</td><td>0.687</td><td>0.097</td></tr><tr><td>Cclust</td><td>0.405</td><td>0.059</td><td>0.454</td><td>0.041</td><td>0.410</td><td>0.051</td><td>0.322</td><td>0.074</td></tr><tr><td>GIMSA</td><td>0.325</td><td>0.102</td><td>0.362</td><td>0.156</td><td>0.260</td><td>0.252</td><td>0.209</td><td>0.150</td></tr></tbody></table>

at 0.433 and 0.089 respectively. In contrast, for the Cdist method and the ECMdd algorithm, these values are 0.687 and 0.097 respectively. Considering the ASW and HC performance criteria separately, the Cstat and Cdist methods perform best in the 4 table, while in the 5 table, the Cdist method stands out.

## 5.4. American youth (AY) dataset

The National Longitudinal Survey of Youth (1979 – 2012) is a project tracking the transition to adulthood trajectory of young Americans on various life aspects from 1979 to 2012 with an annual survey<fnref n="2" />. The sample includes 12,685 participants and 243,071 observations, with an average follow-up of over 19 years per individual. In this work, we identified life trajectory typologies for these young people by considering multiple dimensions, including social, economic, health, education, and employment aspects. Twelve categorical sequences, each with two to eight status, were considered. We retained data for 10,532 individuals with at least 12 years of follow-up to ensure homogeneous sequence durations, facilitating multi-channel method comparisons. Sequences for poverty and employability status had 13% and 16% missing data, respectively. In one configuration, missing data were treated as possible values, adding an NA status to the alphabet. In another, a random forest model was used to impute missing data. Standard OM (with constant substitution and insertion costs) was applied to all dimensions for similarity measures. Life trajectories were grouped into three classes, and CAH, PAM, FCMdd, and ECMdd clustering algorithms were applied to create hard, fuzzy, and credal partitions into three clusters. The hard partitions were compared using internal performance criteria, ASW and HC. Tables 6 and 7 present the performance of the CAH, PAM, FCMdd and ECMdd clustering algorithms for each of the Cstat, Ccost, Cdist, Cclust and GIMSA multidimensional sequential approaches using extended alphabet and multiple imputation to treat missing data. Performance was evaluated using the ASW and HC indices.

Tables 6 and 7 present the performance of sequential multidimensional clustering methods on AY dataset using the OM dissimilarity function with respectively an extended alphabet and multiple imputation for the treatment of missing data. The Cclust method seems to show the best results in terms of ASW index values in both tables (0.530 and 0.497) followed by the Cdist approach. The FCMdd clustering algorithm performs best for the two approaches Cclust and Cdist in both tables, in opposition to the ECMdd algorithm which performs lowest compared to all approaches in both tables. We can also observe that although the Cclust method shows superior performance when missing data is processed with an alphabet extension (in Tables 6), and in Tables 7, methods Cdist and Cclust show improved performance, i.e. when missing data is treated by multiple imputation.

<footnote n="2">²https://www.nlsinfo.org/</footnote>
<table><caption>Table 6: Performance of the multidimensional sequential clustering approaches on the American youth dataset with Standard OM dissimilarity function with the extended alphabet.</caption><thead><tr><th rowspan="2">Methods</th><th colspan="2">CAH</th><th colspan="2">PAM</th><th colspan="2">FCMdd</th><th colspan="2">ECMdd</th></tr><tr><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th></tr></thead><tbody><tr><td>Cstat</td><td>0.119</td><td>0.306</td><td>0.083</td><td>0.250</td><td>0.158</td><td>0.171</td><td>-0.042</td><td>0.644</td></tr><tr><td>Ccost</td><td>0.274</td><td>0.117</td><td>0.234</td><td>0.217</td><td>0.297</td><td>0.084</td><td>0.111</td><td>0.236</td></tr><tr><td>Cdist</td><td>0.396</td><td>0.105</td><td>0.342</td><td>0.207</td><td>0.399</td><td>0.087</td><td>0.212</td><td>0.225</td></tr><tr><td>Cclust</td><td>0.502</td><td>0.108</td><td>0.523</td><td>0.097</td><td>0.530</td><td>0.092</td><td>0.223</td><td>0.272</td></tr><tr><td>GIMSA</td><td>0.110</td><td>0.338</td><td>0.124</td><td>0.318</td><td>0.188</td><td>0.280</td><td>0.078</td><td>0.252</td></tr></tbody></table>

<table><caption>Table 7: Performance of the multidimensional sequential clustering approaches on the American youth dataset with Standard OM dissimilarity function with multiple imputation.</caption><thead><tr><th rowspan="2">Methods</th><th colspan="2">CAH</th><th colspan="2">PAM</th><th colspan="2">FCMdd</th><th colspan="2">ECMdd</th></tr><tr><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th></tr></thead><tbody><tr><td>Cstat</td><td>0.133</td><td>0.291</td><td>0.037</td><td>0.300</td><td>0.178</td><td>0.170</td><td>-0.170</td><td>0.745</td></tr><tr><td>Ccost</td><td>0.277</td><td>0.186</td><td>0.279</td><td>0.161</td><td>0.298</td><td>0.065</td><td>0.094</td><td>0.248</td></tr><tr><td>Cdist</td><td>0.385</td><td>0.089</td><td>0.391</td><td>0.154</td><td>0.402</td><td>0.069</td><td>0.288</td><td>0.071</td></tr><tr><td>Cclust</td><td>0.480</td><td>0.096</td><td>0.495</td><td>0.095</td><td>0.497</td><td>0.089</td><td>0.199</td><td>0.226</td></tr><tr><td>GIMSA</td><td>0.102</td><td>0.349</td><td>0.118</td><td>0.318</td><td>0.195</td><td>0.264</td><td>0.070</td><td>0.263</td></tr></tbody></table>

### 5.5. Primary Biliary Cirrhosis (PBC) dataset

Available on UCI Machine Learning<fnref n="3" />, these data are from 312 patients with PBC. The initial protocol included visits at 6 months, 1 year, and with visits due to worsening health. We search for typologies of treatment trajectories by simultaneously considering the maximum amount of categorical information to extract treatment sequences for each patient. We applied dissimilarity measures adapted to each sequence refers to [17]. Matching subsequences function was used for binary variable sequences to handle missing values and alignment issues. CHI2 was applied to sequences of categorized age and gender, considering only state frequencies. OMslen was used for other variables to account for sequence length variability. We considered survival status (alive, transplanted, deceased) as the a prior class partition to compare multidimensional sequential methods. Performance was evaluated using the CR index. The CAH, PAM, FCMdd, and ECMdd algorithms were applied to dissimilarity matrices, generating hard, fuzzy, and credal partitions into three clusters. The hard partitions were compared with the known a priori class partition. Table 8 shows the performance of the CAH, PAM, FCMdd and ECMdd clustering algorithms for each of the Cstat, Ccost, Cdist, Cclust and GIMSA multidimensional sequential approaches. Performance was evaluated using the CR index.

Table 8 presents the performance of multidimensional sequential clustering methods on PBC dataset, using the dissimilarity functions DHD, CHI2 and OMslen. The Rand Index measures the similarity between the clusters obtained by the clustering algorithms. We observe that for this dataset, the Cclust method obtains the slightly highest values on two of the four clustering algorithms (CAH, FCMdd). However, the Cdist method shows a slightly high performance for the

<footnote n="3">³https://archive.ics.uci.edu/ml/index.php</footnote>
<table><caption>Table 8: Performance of the multidimensional sequential clustering approaches on the Primary Biliary Cirrhosis dataset with DHD, CHI2, and OMslen dissimilarity functions: The Rand index.</caption><thead><tr><th>Methods</th><th>CAH</th><th>PAM</th><th>FCMdd</th><th>ECMdd</th></tr></thead><tbody><tr><td>Cdist</td><td>0.428</td><td>0.425</td><td>0.474</td><td>0.537</td></tr><tr><td>Cclust</td><td>0.477</td><td>0.475</td><td>0.503</td><td>0.532</td></tr><tr><td>GIMSA</td><td>0.424</td><td>0.517</td><td>0.463</td><td>0.508</td></tr></tbody></table>

ECMdd clustering algorithm and values approaching Cclust for the CAH and PAM algorithms, although it is slightly lower for FCMdd. Overall, the Cclust method seems to perform best for these data, closely followed by Cdist.

# 6. Results and discussion

## 6.1. Comparative analysis and discussion

In this section, we propose a comparative analysis of methods Cstat, Ccost, Cdist, Cclust, and GIMSA, state-of-the-art of row-data-base relational clustering approaches for MST. We used several MST characterized by real and simulated datasets, composed of categorical/ordinal/discrete time series and longitudinal data, with different dimensions and time lengths, see Table 9. The dissimilarity matrices were computed using either a single dissimilarity function for all trajectory dimensions, or different dissimilarity functions, has a strong impact clustering results. In this context, Studer and Ritschard [17] have formulated guidelines, aimed at orienting the appropriate selection of the measure. We use critical difference plots based on classical Friedman and Nemenyi non-parametric statistical tests [27], to analyze the differences in performance (RI, ASW and HC) of the single-view relational clustering algorithms (CAH, PAM, FCMdd, ECMdd) for each MST clustering method (Cstat, Ccost, Cdist, Cclust, GIMSA).

<table><caption>Table 9: Characteristics of differences between datasets and run-times by method, #Σ corresponds to the maximum alphabet in all dimensions.</caption><thead><tr><th rowspan="2">Datasets</th><th rowspan="2">Nrow</th><th rowspan="2">Ncol</th><th rowspan="2">#Σ</th><th rowspan="2">K</th><th colspan="5">Times (mins)</th><th rowspan="2">Measures</th></tr><tr><th>Cstat</th><th>Ccost</th><th>Cdist</th><th>Cclust</th><th>GIMSA</th></tr></thead><tbody><tr><td>Synthetic 1</td><td>150</td><td>2</td><td>4</td><td>4</td><td>0.008</td><td>0.010</td><td>0.011</td><td>0.014</td><td>0.012</td><td>OM</td></tr><tr><td>Synthetic 2</td><td>150</td><td>4</td><td>4</td><td>4</td><td>0.011</td><td>0.012</td><td>0.022</td><td>0.031</td><td>0.023</td><td>OM</td></tr><tr><td>Biofam: Cf. 1</td><td>2000</td><td>3</td><td>3</td><td>5</td><td>0.033</td><td>0.370</td><td>0.040</td><td>0.451</td><td>0.022</td><td>OM</td></tr><tr><td>Biofam: Cf. 2</td><td>2000</td><td>3</td><td>3</td><td>5</td><td></td><td></td><td>0.064</td><td>0.747</td><td>0.022</td><td>OM, LCS, CHI2</td></tr><tr><td>AY</td><td>10532</td><td>12</td><td>9</td><td>3</td><td>0.435</td><td>0.321</td><td>0.058</td><td>0.676</td><td>0.454</td><td>OM</td></tr><tr><td>AY imputation</td><td>10532</td><td>12</td><td>9</td><td>3</td><td>0.371</td><td>0.478</td><td>0.020</td><td>0.786</td><td>0.879</td><td>OM</td></tr><tr><td>PBC</td><td>312</td><td>8</td><td>5</td><td>3</td><td></td><td></td><td>0.064</td><td>0.121</td><td>0.075</td><td>NMS, OMslen, CHI2</td></tr></tbody></table>

The RI-based critical difference diagram presented in Figure 10(a), allows us to observe that there is no significant difference between methods, however the Cclust is the best of all followed closely by Cdist. The ASW-based critical difference diagram is shown in Figure 10(b). The figure shows that Cdist is the best approach of all, followed by Cclust, but the two approaches are not significantly different. The Ccost, Cstat and GIMSA approaches are clearly less accurate. We observe that Cdist and Cclust are both significantly different from the approaches Ccost, Cstat and GIMSA. In the HC-based critical difference diagram shown in figure 11, we can see that Cdist
is the most stable, followed by Cclust. GIMSA and Cstat remain the least stable. We can conclude that, in the majority of cases on experimental data, Cdist method performs best and more robustly, followed by Cclust. Methods Ccost, Cstat and GIMSA are ranked respectively after these.

<figure><img src="image_12.png" /><figcaption>Figure 10: Critical difference diagram between Cstat, Ccost, Cdist, Cclust and GIMSA based on (a) Rand Index, (b) Average Silhouette Width.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>Figure 11: Critical difference diagram between Cstat, Ccost, Cdist, Cclust and GIMSA based on Hubert's C.</figcaption></figure>

However, a critical review can also be made of the differences between these five methods. Indeed, these approaches differ in their theoretical background and are selected according to the specific goals of MST analysis, each offering a unique perspective for understanding multiple sequential data. For example, the differentiation criteria presented in Section 4.3, i.e. multidimensionality, parsimony, type and local and global interdependence, can or cannot be appropriate depending on the research questions or data. Another main distinction can be the assumption of independence of the dimensions assumed by Ccost and Cdist methods. They assume implicitly that the sequential measurements (status) were done independently in each dimension (sequences) [26]. We can wish to use Ccost and Cdist even if dimension independence is not effective, for example because the costs and distances obtained are simpler to interpret. In such cases, it is crucial to be conscious of the constraints imposed by the procedure on costs for Ccost and on dissimilarities for Cdist.

A comparison of the temporal complexities of the approaches (Table 9) shows that the Cdist method has generally lower computation times than the others. In detail, we observe that the Cstat method is generally the fastest for small datasets, and its runtime increases with dataset size. Ccost method has variable run times, and Cclust method generally has the highest run times of all methods, particularly for large datasets. Run times for the GIMSA method are generally comparable to those of Cstat and Ccost. The missing data processing method (state extension or multiple imputation) has an impact on time complexity and differs from methods. Multiple imputation appears to reduce the time complexity of the Cstat and Cdist methods, but increases the runtime of the Ccost, Cclust and GIMSA methods. Moreover, although the main focus of this work was on the comparison between these five approaches, the procedure we have presented can serve as a guide for performing multidimensional sequential trajectory clustering. The work also
contributes to the comparison of hard (CAH and PAM) and soft (FCMdd and ECMdd) clustering
algorithms in the context of sequential trajectory analysis. We can thus see on Figure 12 of the
critical difference diagram, that the PAM algorithm is the best, followed by ECMdd, and CAH
is the least performing of all. However, although we can classify them, these differences are not
statistically significant for PAM, ECMdd and FCMdd.

<figure><img src="image_14.png" /><figcaption>Figure 12: Critical difference diagram between clustering algorithms CAH, PAM, FCMdd and ECMdd based on Rand Index.</figcaption></figure>

However, the comparative analysis framework implemented has certain limitations. Although we have exploited simulated and real datasets that are very different from each other, and studied different scenarios of these data, we cannot claim to have taken into account all possible situations of MST. In addition, choices related to the clustering algorithms and dissimilarity measures used could have been different, which could have led to alternative conclusions. For dissimilarity measures, although a large variety of measures exist, we concentrated on those that are sensitive to the differences characteristic of each dimension of our data.

## 6.2. Exploring multi-view relational methods for MST clustering

Cdist is the most powerful and robust method for MST clustering according to Section 6.1, even though its main limitation is the ignorance of dimension correlation. Our approach aims to extend Cdist into a collaborative dimensional framework with relevance weights for each dimension, which we named Codist (distance collaborative). In contrast to Cdist, Codist matches all columns of the classification Table 2, because it provides a global interdependence of the dimensions (distance matrices) and, more importantly, allows direct interpretability of the clustering results, which no method presented in this work offers.

To evaluate the performance of Codist approach against methods presented in this review (Section 4), we conducted experiments on eDOL datasets [2], using multi-relational clustering algorithms, namely MRDCA-RWL [28], MRFCMdd [29], and MECMdd[30]. These algorithms enable collaboration between dimensions within a paradigm of relevance weight learning for each dimension in each cluster, facilitating post-clustering interpretation of results. MRDCA, introduced by F. de Carvalho and al. [28], extends dynamic hard clustering to relational data by leveraging multiple dissimilarity matrices. It has two variants, MRDCA-RWL and MRDCA-RWG, which estimate relevance weights either locally for each cluster or globally for the entire partition. However, MRDCA assumes a strict assignment of objects to clusters, which may not be suitable for real-world data that often contains uncertainty, imprecision, and inconsistency [31]. To address this limitation, F. de Carvalho and al. [29] proposed the multiple relational fuzzy c-medoids (MR-FCMdd) algorithm, which extends FCMdd [8]. MRFCMdd assigns relevance weights using two
approaches: MRFCMdd-RWL, which computes weights locally for each matrix in each cluster, and MRFCMdd-RWG, which determines weights globally for the entire clustering process. Similarly, Soubeiga and al. [30] introduced the multi-view evidential c-medoids clustering with adaptive weightings (MECMdd), based on the ECMdd algorithm [9]. This method also has two variants, MECMdd-RWL with local weighting and MECMdd-RWG for global weighting. Beyond medoid-based approaches, several other multi-view relational clustering methods exist, as illustrated in Figure 13. For example, Frigui and al. [32] introduced the CARD algorithm, which applies fuzzy clustering principles to aggregate multiple dissimilarity matrices while learning relevance weights for each matrix within each cluster.

<figure><img src="image_15.png" /><figcaption>Figure 13: Review of Multi-Relational clustering.</figcaption></figure>

eDOL is a project aimed at innovating in the management of chronic pain, with the aim of determining care trajectory patterns. Data are collected via a mHealth application, where patients complete weekly barometric surveys assessing pain, fatigue, mood, stress, sleep, body comfort, sporting activities and non-sporting activities (8 dimensions or features). Values for each variable are on a scale from 0 to 10. These data are complex, subjective and imprecise, and can be treated either as categorical time series (CTS), or discrete time series (DTS), [2]. We worked on data from 636 patients, extracted from eDOL in June 2023, totaling 14,090 self-reported care events, with an average follow-up of 5 months and a total duration of approximately 19 months. We used dissimilarity measures adapted to discrete time series, the time warp edit distance (TWED) for all eight dimensions. The TWED distance, noted $\delta_{\lambda,\nu}$, measures the minimum cost of operations needed to transform one discrete sequence into another. Its computation has a complexity of $O(n^2)$. It depends on two parameters: $\lambda > 0$, which penalizes time gaps, and $\nu \in [0, 1]$, which controls its elasticity. The default parameters $\nu = 0.5$ and $\lambda = 0.5$ are used. Previous work using feature-based clustering on barometer data identified three clusters [2], through careful research involving several iterations, and we also considered two clusters in this work.

The same setting contexts of the single-view relational algorithms (defined in section 5.1) have been used for the application framework of the multi-view relational algorithms. The PAM,
FCMdd, and ECMdd single-view relational clustering algorithms were applied to the dissimilarity matrices obtained from Cstat, Ccost, Cdist, Cclust and GIMSA. For the new Codist method, corresponding multi-view relational clustering algorithms, include MRDCA-RWL, MRFCMdd-RWL and MECMdd-RWL were applied to the dissimilarity matrices. we used the variants with a relevance weight for each locally estimated dissimilarity matrix.

<table><caption>Table 10: Performance of the multidimensional sequential clustering approaches on the eDOL dataset with TWED dissimilarity function.</caption><thead><tr><th rowspan="2">Methods</th><th colspan="2">PAM/MRDCA-RWL</th><th colspan="2">FCMdd/MRFCMdd-RWL</th><th colspan="2">ECMdd/MECMdd-RWL</th></tr><tr><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th><th>ASW</th><th>HC</th></tr></thead><tbody><tr><td>Cstat</td><td>0.477</td><td><strong>0.033</strong></td><td>0.372</td><td>0.298</td><td>0.449</td><td>0.251</td></tr><tr><td>Ccost</td><td>0.560</td><td>0.154</td><td>0.462</td><td>0.417</td><td>0.345</td><td>0.214</td></tr><tr><td>Cdist</td><td>0.348</td><td>0.066</td><td><strong>0.505</strong></td><td><strong>0.155</strong></td><td>0.568</td><td>0.155</td></tr><tr><td>Cclust</td><td>0.160</td><td>0.399</td><td>0.471</td><td>0.302</td><td>0.432</td><td>0.189</td></tr><tr><td>GIMSA</td><td>0.200</td><td>0.497</td><td>0.341</td><td>0.417</td><td>0.504</td><td>0.284</td></tr><tr><td>Codist</td><td><strong>0.568</strong></td><td>0.130</td><td>0.501</td><td>0.201</td><td><strong>0.585</strong></td><td><strong>0.100</strong></td></tr></tbody></table>

Table 10 presents the performance using ASW and HC indices. We show that Codist combined with evidential clustering (MECMdd) offers the best performance and robustness, achieving the high compactness (ASW=0.585) and stability (HC = 0.100), making it the most efficient approach. We obtain two singletons clusters, *Cl_1* and *Cl_2*, and an imprecise cluster {*Cl_1*, *Cl_2*}, intermediate between the two clusters, named *Cl_uncertain*. Analysis of dimension relevance weights, in Figure 14, shows that cluster *Cl_2* groups patients with chronic pain trajectory related to sleep and mood, while *Cl_1* groups patients with chronic pain trajectory related to stress and fatigue. Patients belonging to the uncertain cluster exhibit characteristics common to both clusters. In addition to considering global interdependence between dimensions, learning the relevance weights of dimension is a major advantage of Codist method, both in terms of performance and explainability of results. In Cstat, Ccost, Cdist, Cclust, and GIMSA methods, this explicative task is performed with other tools like SHapley Additive exPlanations (SHAP) [33] after the clustering process.

## 7. Conclusions

In this work, we propose a review of trajectory clustering methods. In this context, we provide diverse formulations of definitions and methods of trajectory clustering in a first part. In a second part, we discuss sequential trajectory clustering methods, focusing on a comparative analysis of multidimensional methods. Four types of trajectory are thus highlighted, including sequential, temporal, spatial and spatio-temporal trajectories. Common clustering methods are organized into three main categories, depending upon whether they work directly with the raw-data, indirectly with features extracted from the raw-data, or indirectly with models built from the raw-data. The most recent studies on clustering multidimensional sequential trajectories (MST) based directly on raw data have been grouped into five main methods: additive (Ccost or Cdist), combinative (Cstat or Cclust) or factorial analysis (GIMSA).

In the light of critical and experimental analysis of the real and simulated MST datasets considered, the Cdist method is the best performing and most robust, followed by the Cclust method.
<figure><img src="image_16.png" /><figcaption>Figure 14: Visualization of the feature weights on eDOL dataset for the best partition based on MECMdd-RWL algorithm.</figcaption></figure>

However, we have demonstrated that Cdist assumes dimension independence and hides the relationship between dimensions, and that Cclust is not parsimonious in terms of the final number of clusters. It is important to be aware of these limitations when choosing these methods. We have also proposed to explore the Codist method, an extension of Cdist, which is more efficient and addresses the limitations of the Cdist method. Codist also has the advantage of learning dimensional relevance weights, allowing clustering results to be explained. This work also contributes to the comparison of hard (CAH and PAM) and soft (FCMdd and ECMdd) clustering algorithms in the context of sequential trajectory analysis. When data are complex and subjective, soft algorithms, particularly ECMdd, perform well and offer a finer representation of uncertainty.

Although the initial results illustrate the performance of the Codist method, these promising findings open up significant opportunities for further development and application. In summary, while there is room for improvement in the methods presented in this paper, the main opportunity for future work on MST clustering lies in the development of new evidential clustering algorithms. These algorithms could effectively represent uncertainty and imprecision, enable collaboration across multi-dimensional or multi-sequence data using an object-based approach, and extend their applicability to non-Euclidean data spaces to handle complex and temporal data. Additionally, future developments could focus on learning relevance weights for each dimension, enhancing the interpretability of the algorithm. An object-based algorithm would also eliminate the transformation step currently used by multi-relational clustering methods like Codist for proximity matrix computation, streamlining the process and improving efficiency. These advancements would significantly broaden the scope and impact of MST clustering in real-world applications.
Acknowledgments

The authors acknowledge the support received from the French National Research Agency under the Investments for the Future program (16-IDEX-0001 CAP 20-25). The authors wish to express their thanks to the Analgesia Institute for providing the eDOL dataset.

Availability of data and materials

Simulated and public data, and R code for the experiments, are included in GitHub repository.

References

[1] Nadia Deville-Stoetzel, Isabelle Gaboury, Djamal Berbiche, and Mylaine Breton. Profiling patterns of patient experiences of access and continuity at team-based primary healthcare clinics (canada): a latent class analysis. *International Journal for Equity in Health*, 23(1), October 2024.

[2] Armel Soubeiga, Violaine Antoine, Alice Corteval, Nicolas Kerckhove, Sylvain Moreno, Issam Falih, and Jules Phalip. Clustering and interpretation of time-series trajectories of chronic pain using evidential c-means. *Expert Systems with Applications*, 260:125369, 2025.

[3] Kevin Emery and André Berchtold. Comparison of two approaches in multichannel sequence analysis using the swiss household panel. *Longitudinal and Life Course Studies*, 14(4):592–623, 2023.

[4] Nicolas Robette. *L'Analyse statistique des trajectoires: Typologies de séquences et autres approches*. Ined Éditions, Paris, France, 2021. Ined Éditions.

[5] Philippe Blanchard. Multi-dimensional biographies. explaining disengagement through sequence analysis. In *Proceedings of the 3rd ECPR Conference*, pages 8–10, Budapest, Hungary, 9 2005.

[6] Nicolas Robette, Xavier Bry, and Eva Lelièvre. A global interdependence approach to multidimensional sequence analysis. *Sociological Methodology*, 45(1):1–44, 2015.

[7] Han Su, Shuncheng Liu, Bolong Zheng, Xiaofang Zhou, and Kai Zheng. A survey of trajectory distance measures and performance evaluation. *The VLDB Journal*, 29:3–32, 2020.

[8] R. Krishnapuram, A. Joshi, and Liyu Yi. A fuzzy relative of the k-medoids algorithm with application to web document and snippet clustering. In FUZZ-IEEE'99. 1999 IEEE International Fuzzy Systems. Conference Proceedings (Cat. No.99CH36315), volume 3, pages 1281–1286 vol.3, 1999.

[9] Kuang Zhou, Arnaud Martin, Quan Pan, and Zhunga Liu. Evidential relational clustering using medoids. *2015 18th International Conference on Information Fusion (Fusion)*, pages 413–420, 2015.

[10] Jean Damascene Mazimpaka. Trajectory data mining: A review of methods and applications. *Journal of Spatial Information Science*, 13, 12 2016.

[11] Dianfeng Qiao, Xinyu Yang, Yan Liang, and Xiaohui Hao. Rapid trajectory clustering based on neighbor spatial analysis. *Pattern Recognition Letters*, 156:167–173, 2022.

[12] Saeed Aghabozorgi, Ali Seyed Shirkhorshidi, and Teh Ying Wah. Time-series clustering – a decade review. *Information Systems*, 53:16–38, 10 2015.

[13] Francisco de A.T. de Carvalho, Yves Lechevallier, and Filipe M. de Melo. Partitioning hard clustering algorithms based on multiple dissimilarity matrices. *Pattern Recognition*, 45(1):447–464, 2012.

[14] Leonard Kaufman and Peter J. Rousseeuw. *Finding Groups in Data: An Introduction to Cluster Analysis*. Wiley, New York, 1990.

[15] Kevin Toohey and Matt Duckham. Trajectory similarity measures. *ACM SIGSPATIAL Special*, 7:43–50, 5 2015.

[16] Yaguang Tao, Alan Both, Rodrigo I. Silveira, Kevin Buchin, Stef Sijben, Ross S. Purves, Patrick Laube, Dongliang Peng, Kevin Toohey, and Matt Duckham. A comparative analysis of trajectory similarity measures. https://doi.org/10.1080/15481603.2021.1908927, 58:643–669, 2021.

[17] Matthias Studer and Gilbert Ritschard. What matters in differences between life trajectories: A comparative review of sequence dissimilarity measures. *Journal of the Royal Statistical Society Series A: Statistics in Society*, 179(2):481–511, 07 2015.

<footnote n="4">⁴https://github.com/armelsoubeiga/review-of-trajectory-clustering</footnote>
[18] Daniel G. Zelterman. Longitudinal and time-series analysis. In *Studying Human Populations: An Advanced Course in Statistics*, pages 335–370. Springer New York, New York, NY, 2008.

[19] Shi Zhong and Joydeep Ghosh. A unified framework for model-based clustering. *The Journal of Machine Learning Research*, 4:1001–1037, 2003.

[20] Ángel López-Oriona and José A. Vilar. Analyzing categorical time series with the r package ctsfeatures. *Journal of Computational Science*, 76:102233, 2024.

[21] Cees H. Elzinga. Sequence similarity - a non-aligning technique. *Sociological Methods & Research*, 32:3–29, 8 2003.

[22] Laurent Lesnard. Setting cost in optimal matching to uncover contemporaneous socio-temporal patterns. *Sociological Methods & Research*, 38(3):389–419, 2010.

[23] Matissa Hollister. Is optimal matching suboptimal? *Sociological Methods & Research*, 38(2):235–264, 2009.

[24] Pierre François Marteau. Time warp edit distance with stiffness adjustment for time series matching. *IEEE Transactions on Pattern Analysis and Machine Intelligence*, 31:306–318, 2009.

[25] Jacques Antoine Gauthier, Eric D. Widmer, Philipp Bucher, and Cédric Notredame. Multichannel sequence analysis applied to social science data. http://dx.doi.org/10.1111/j.1467-9531.2010.01227.x, 40:1–38, 7 2010.

[26] Gilbert Ritschard, Tim F. Liao, and Emanuela Struffolino. Strategies for multidomain sequence analysis in social research. *Sociological Methodology*, 53(2):288–322, 2023.

[27] Janez Demšar. Statistical comparisons of classifiers over multiple data sets. *The Journal of Machine Learning Research*, 7:1–30, 2006.

[28] Francisco de A.T. de Carvalho, Yves Lechevallier, and Filipe M. de Melo. Partitioning hard clustering algorithms based on multiple dissimilarity matrices. *Pattern Recognition*, 45(1):447–464, 2012.

[29] Francisco de A.T. de Carvalho, Yves Lechevallier, and Filipe M. de Melo. Relational partitioning fuzzy clustering algorithms based on multiple dissimilarity matrices. *Fuzzy Sets and Systems*, 215:1–28, 2013. Theme: Clustering.

[30] Armel Soubeiga, Violaine Antoine, and Sylvain Moreno. Multi-view relational evidential c-medoid clustering with adaptive weighted. In *2024 IEEE 11th International Conference on Data Science and Advanced Analytics (DSAA)*, pages 1–10, 2024.

[31] Patric Bosc and Henri Prade. An introduction to the fuzzy set and possibility theory-based treatment of flexible queries and uncertain or imprecise databases. In D. Dubois and H. Prade, editors, *Uncertainty Management in Information Systems: From Needs to Solutions*, pages 285–324. Springer, Berlin, Germany, 1997.

[32] Hichem Frigui, Cheul Hwang, and Frank Chung-Hoon Rhee. Clustering and aggregation of relational data with applications to image database categorization. *Pattern Recognition*, 40(11):3053–3068, 2007.

[33] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, *Advances in Neural Information Processing Systems*, volume 30. Curran Associates, Inc., 2017.