Hard and soft clustering of categorical time series based on two novel distances with an application to biological sequences

• Published in: Information sciences 2023-05, Vol.624, p.467-492
• Main Authors: López-Oriona, Ángel, Vilar, José A., D’Urso, Pierpaolo
• Format: Article
• Language: English
• Subjects: Association measures; Biological sequences; Categorical time series; Fuzzy clustering; Hard clustering
• ISSN: 0020-0255; 1872-6291
• DOI: 10.1016/j.ins.2022.12.065

Two novel distances between categorical time series are introduced. Both of them measure discrepancies between extracted features describing the underlying serial dependence patterns. One distance is based on well-known association measures, namely Cramer’s v and Cohen’s κ. The other one relies on the so-called binarization of a categorical process, which indicates the presence of each category by means of a canonical vector. Binarization is used to construct a set of innovative association measures which allow to identify different types of serial dependence. The metrics are used to perform crisp and fuzzy clustering of nominal series. The proposed approaches are able to group together series generated from similar stochastic processes, achieve accurate results with series coming from a broad range of models and are computationally efficient. Extensive simulation studies show that both hard and soft clustering algorithms outperform several alternative procedures proposed in the literature. Two applications involving biological sequences from different species highlight the usefulness of the introduced techniques.