Journal Home > Volume 29 , Issue 2
Tsinghua Science and Technology 2024, 29(2): 343-355 https://doi.org/10.26599/TST.2023.9010036
Open Access | Issue | Published: 22 September 2023

Evolutionary Multi-Tasking Optimization for High-Efficiency Time Series Data Clustering

Show Author's Information Rui Wang1,2,  Wenhua Li2( ),  Kaili Shen3,  Tao Zhang2,  Xiangke Liao4
Xiangjiang Laboratory, Changsha 410205, China
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Ant Group Co., Ltd., Hangzhou 310000, China
College of Computer Science and Technology, NUDT, Changsha 410073, China
Keywords:
time series clustering, evolutionary multi-tasking, multifactorial optimization, clustering validity index, distance measure
Cite this article:
Wang R, Li W, Shen K, et al. Evolutionary Multi-Tasking Optimization for High-Efficiency Time Series Data Clustering. Tsinghua Science and Technology, 2024, 29(2): 343-355. https://doi.org/10.26599/TST.2023.9010036
Download citation
EndNote(RIS)
BibTeX

61

Views

21

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

Time series clustering is a challenging problem due to the large-volume, high-dimensional, and warping characteristics of time series data. Traditional clustering methods often use a single criterion or distance measure, which may not capture all the features of the data. This paper proposes a novel method for time series clustering based on evolutionary multi-tasking optimization, termed i-MFEA, which uses an improved multifactorial evolutionary algorithm to optimize multiple clustering tasks simultaneously, each with a different validity index or distance measure. Therefore, i-MFEA can produce diverse and robust clustering solutions that satisfy various preferences of decision-makers. Experiments on two artificial datasets show that i-MFEA outperforms single-objective evolutionary algorithms and traditional clustering methods in terms of convergence speed and clustering quality. The paper also discusses how i-MFEA can address two long-standing issues in time series clustering: the choice of appropriate similarity measure and the number of clusters.


menu
Abstract
Full text
Outline
About this article

Evolutionary Multi-Tasking Optimization for High-Efficiency Time Series Data Clustering

Show Author's information Rui Wang1,2, Wenhua Li2( ), Kaili Shen3, Tao Zhang2, Xiangke Liao4
Xiangjiang Laboratory, Changsha 410205, China
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Ant Group Co., Ltd., Hangzhou 310000, China
College of Computer Science and Technology, NUDT, Changsha 410073, China

Abstract

Time series clustering is a challenging problem due to the large-volume, high-dimensional, and warping characteristics of time series data. Traditional clustering methods often use a single criterion or distance measure, which may not capture all the features of the data. This paper proposes a novel method for time series clustering based on evolutionary multi-tasking optimization, termed i-MFEA, which uses an improved multifactorial evolutionary algorithm to optimize multiple clustering tasks simultaneously, each with a different validity index or distance measure. Therefore, i-MFEA can produce diverse and robust clustering solutions that satisfy various preferences of decision-makers. Experiments on two artificial datasets show that i-MFEA outperforms single-objective evolutionary algorithms and traditional clustering methods in terms of convergence speed and clustering quality. The paper also discusses how i-MFEA can address two long-standing issues in time series clustering: the choice of appropriate similarity measure and the number of clusters.

Keywords: time series clustering, evolutionary multi-tasking, multifactorial optimization, clustering validity index, distance measure

References(48)

[1]
S. Aghabozorgi, A. S. Shirkhorshidi, and T. Y. Wah, Time-series clustering–a decade review, Inf. Syst., vol. 53, pp. 16–38, 2015.
DOI Google Scholar
[2]
B. Yang, Y. Yang, Q. Li, D. Lin, Y. Li, J. Zheng, and Y. Cai, Classification of medical image notes for image labeling by using MinBERT, Tsinghua Science and Technology, vol. 28, no. 4, pp. 613–627, 2023.
DOI Google Scholar
[3]
M. Ahmed, R. Seraj, and S. M. S. Islam, The k-means algorithm: A comprehensive survey and performance evaluation, Electronics, vol. 9, no. 8, p. 1295, 2020.
DOI Google Scholar
[4]
E. Schubert, J. Sander, M. Ester, H. P. Kriegel, and X. Xu, DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN, ACM Trans. Database Syst., vol. 42, no. 3, p. 19, 2017.
DOI Google Scholar
[5]
P. Contreras and F. Murtagh, Hierarchical clustering, in Handbook of Cluster Analysis, C. Hennig, M. Meila, F. Murtagh, and R. Rocci, eds. New York, NY, USA: Chapman and Hall/CRC, 2015, pp. 124–145.
[6]
U. Maulik, S. Bandyopadhyay, and A. Mukhopadhyay, Multiobjective Genetic Algorithms for Clustering: Applications in Data Mining and Bioinformatics. Berlin, Germany: Springer, 2011.
DOI
[7]
F. Wang, X. Wang, and S. Sun, A reinforcement learning level-based particle swarm optimization algorithm for large-scale optimization, Inf. Sci., vol. 602, pp. 298–312, 2022.
DOI Google Scholar
[8]
K. Zhu, J. Li, and H. Baoyin, Trajectory optimization of the exploration of asteroids using swarm intelligent algorithms, Tsinghua Science and Technology, vol. 14, no. S2, pp. 7–11, 2009.
DOI Google Scholar
[9]
W. Li, G. Zhang, X. Yang, Z. Tao, and H. Xu, Sizing a hybrid renewable energy system by a coevolutionary multiobjective optimization algorithm, Complexity, vol. 2021, p. 8822765, 2021.
DOI Google Scholar
[10]
L. Li, L. Jiao, J. Zhao, R. Shang, and M. Gong, Quantum-behaved discrete multi-objective particle swarm optimization for complex network clustering, Pattern Recogn., vol. 63, pp. 1–14, 2017.
DOI Google Scholar
[11]
W. Li, R. Wang, T. Zhang, M. Ming, and K. Li, Reinvestigation of evolutionary many-objective optimization: Focus on the Pareto knee front, Inf. Sci., vol. 522, pp. 193–213, 2020.
DOI Google Scholar
[12]
U. Maulik and S. Bandyopadhyay, Genetic algorithm-based clustering technique, Pattern Recogn., vol. 33, no. 9, pp. 1455–1465, 2000.
DOI Google Scholar
[13]
W. Li, T. Zhang, R. Wang, B. Wang, Y. Song, and X. Li, A knee-point driven multi-objective evolutionary algorithm for flexible job shop scheduling, in Proc. 2019 IEEE Symp. Series on Computational Intelligence, Xiamen, China, 2019, pp. 1716–1722.
DOI Google Scholar
[14]
J. Handl and J. Knowles, Evolutionary multiobjective clustering, in Proc. 8th Int. Conf. on Parallel Problem Solving from Nature, Birmingham, UK, 2004, pp. 1081–1091.
DOI Google Scholar
[15]
E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, vol. 26, no. 5, pp. 646–663, 2021.
DOI Google Scholar
[16]
O. Arbelaitz, I. Gurrutxaga, J. Muguerza, J. M. Pérez, and I. Perona, An extensive comparative study of cluster validity indices, Pattern Recogn., vol. 46, no. 1, pp. 243–256, 2013.
DOI Google Scholar
[17]
J. Handl and J. Knowles, Multi-objective clustering and cluster validation, in Multi-Objective Machine Learning, Y. Jin, ed. Berlin, Germany: Springer, 2006, pp. 21–47.
DOI
[18]
R. Wang, S. Lai, G. Wu, L. Xing, L. Wang, and H. Ishibuchi, Multi-clustering via evolutionary multi-objective optimization, Inf. Sci., vol. 450, pp. 128–140, 2018.
DOI Google Scholar
[19]
W. Li, T. Zhang, R. Wang, S. Huang, and J. Liang, Multimodal multi-objective optimization: Comparative study of the state-of-the-art, Swarm Evol. Comput., vol. 77, p. 101253, 2023.
DOI Google Scholar
[20]
A. Gupta, Y. S. Ong, and L. Feng, Multifactorial evolution: Toward evolutionary multitasking, IEEE Trans. Evol. Comput., vol. 20, no. 3, pp. 343–357, 2016.
DOI Google Scholar
[21]
W. Li, R. Wang, T. Zhang, M. Ming, and H. Lei, Multi-scenario microgrid optimization using an evolutionary multi-objective algorithm, Swarm Evol. Comput., vol. 50, p. 100570, 2019.
DOI Google Scholar
[22]
Y. Liu, T. Özyer, R. Alhajj, and K. Barker, Integrating multi-objective genetic algorithm and validity analysis for locating and ranking alternative clustering, Informatica, vol. 29, no. 1, pp. 33–40, 2005.
Google Scholar
[23]
M. Kim and R. S. Ramakrishna, New indices for cluster validity assessment, Pattern Recogn. Lett., vol. 26, no. 15, pp. 2353–2363, 2005.
DOI Google Scholar
[24]
G. Gan, C. Ma, and J. Wu, Data Clustering: Theory, Algorithms, and Applications, 2nd ed. Alexandria, VA, USA: SIAM, 2007.
DOI
[25]
H. Li, X. Wu, X. Wan, and W. Lin, Time series clustering via matrix profile and community detection, Adv. Eng. Inf., vol. 54, p. 101771, 2022.
DOI Google Scholar
[26]
A. Blázquez-García, A. Conde, U. Mori, and J. A. Lozano, A review on outlier/anomaly detection in time series data, ACM Comput. Surv., vol. 54, no. 3, p. 56, 2021.
DOI Google Scholar
[27]
S. Salvador and P. Chan, Toward accurate dynamic time warping in linear time and space, Intelligent Data Analysis, vol. 11, no. 5, pp. 561–580, 2007.
DOI Google Scholar
[28]
J. Hu, Y. Pan, T. Li, and Y. Yang, Tw-co-MFC: Two-level weighted collaborative fuzzy clustering based on maximum entropy for multi-view data, Tsinghua Science and Technology, vol. 26, no. 2, pp. 185–198, 2021.
DOI Google Scholar
[29]
R. A. Armstrong, Should Pearson’s correlation coefficient be avoided? Ophthalmic Physiol. Opt., vol. 39, no. 5, pp. 316–327, 2019.
DOI Google Scholar
[30]
Y. Zhang, Y. Li, J. Song, X. Chen, Y. Lu, and W. Wang, Pearson correlation coefficient of current derivatives based pilot protection scheme for long-distance LCC-HVDC transmission lines, Int. J. Electr. Power Energy Syst., vol. 116, p. 105526, 2020.
DOI Google Scholar
[31]
S. Liu, Q. Lin, L. Feng, K. C. Wong, and K. C. Tan, Evolutionary multitasking for large-scale multiobjective optimization, IEEE Trans. Evol. Comput., .
DOI Google Scholar
[32]
E. Osaba, J. Del Ser, A. D. Martinez, and A. Hussain, Evolutionary multitask optimization: A methodological overview, challenges, and future research directions, Cogn. Comput., vol. 14, no. 3, pp. 927–954, 2022.
DOI Google Scholar
[33]
K. K. Bali, Y. S. Ong, A. Gupta, and P. S. Tan, Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-II, IEEE Trans. Evol. Comput., vol. 24, no. 1, pp. 69–83, 2020.
DOI Google Scholar
[34]
P. T. H. Hanh, P. D. Thanh, and H. T. T. Binh, Evolutionary algorithm and multifactorial evolutionary algorithm on clustered shortest-path tree problem, Inf. Sci., vol. 553, pp. 280–304, 2021.
DOI Google Scholar
[35]
A. Gupta, Y. S. Ong, L. Feng, and K. C. Tan, Multiobjective multifactorial optimization in evolutionary multitasking, IEEE Trans. Cybern., vol. 47, no. 7, pp. 1652–1665, 2017.
DOI Google Scholar
[36]
Y. S. Ong and A. Gupta, Evolutionary multitasking: A computer science view of cognitive multitasking, Cogn. Comput., vol. 8, no. 2, pp. 125–142, 2016.
DOI Google Scholar
[37]
Y. Yuan, Y. S. Ong, A. Gupta, P. S. Tan, and H. Xu, Evolutionary multitasking in permutation-based combinatorial optimization problems: Realization with TSP, QAP, LOP, and JSP, in Proc. 2016 IEEE Region 10 Conf., Singapore, 2016, pp. 3157–3164.
DOI Google Scholar
[38]
L. Zhou, L. Feng, J. Zhong, Y. S. Ong, Z. Zhu, and E. Sha, Evolutionary multitasking in combinatorial search spaces: A case study in capacitated vehicle routing problem, in Proc. 2016 IEEE Symp. Series on Computational Intelligence, Athens, Greece, 2016, pp. 1–8.
DOI Google Scholar
[39]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002.
DOI Google Scholar
[40]
A. Mukhopadhyay, U. Maulik, and S. Bandyopadhyay, A survey of multiobjective evolutionary clustering, ACM Comput. Surv., vol. 47, no. 4, p. 61, 2015.
DOI Google Scholar
[41]
W. Gong, Z. Cai, and D. Liang, Adaptive ranking mutation operator based differential evolution for constrained optimization, IEEE Trans. Cybern., vol. 45, no. 4, pp. 716–727, 2015.
DOI Google Scholar
[42]
J. Zhang and L. Xing, An improved genetic algorithm for the integrated satellite imaging and data transmission scheduling problem, Comput. Oper. Res., vol. 139, p. 105626, 2022.
DOI Google Scholar
[43]
R. Lu, H. Shen, Z. Feng, H. Li, W. Zhao, and X. Li, HTDeT: A clustering method using information entropy for hardware Trojan detection, Tsinghua Science and Technology, vol. 26, no. 1, pp. 48–61, 2021.
DOI Google Scholar
[44]
X. Li and H. Liu, Greedy optimization for K-means-based consensus clustering, Tsinghua Science and Technology, vol. 23, no. 2, pp. 184–194, 2018.
DOI Google Scholar
[45]
X. Chang, D. Tao, and X. Chao, Multi-view self-paced learning for clustering, in Proc. 24th Int. Conf. on Artificial Intelligence, Buenos Aires, Argentina, 2015, pp. 3974–3980.
Google Scholar
[46]
W. Li, T. Zhang, R. Wang, and H. Ishibuchi, Weighted indicator-based evolutionary algorithm for multimodal multiobjective optimization, IEEE Trans. Evol. Comput., vol. 25, no. 6, pp. 1064–1078, 2021.
DOI Google Scholar
[47]
W. Li, X. Yao, T. Zhang, R. Wang, and L. Wang, Hierarchy ranking method for multimodal multiobjective optimization with local Pareto fronts, IEEE Trans. Evol. Comput., vol. 27, no. 1, pp. 98–110, 2023.
DOI Google Scholar
[48]
X. Yao, W. Li, X. Pan, and R. Wang, Multimodal multi-objective evolutionary algorithm for multiple path planning, Comput. Ind. Eng., vol. 169, p. 108145, 2022.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 21 March 2023
Revised: 10 April 2023
Accepted: 19 April 2023
Published: 22 September 2023
Issue date: April 2024

Copyright

© The author(s) 2024.

Acknowledgements

This work was supported by the Open Project of Xiangjiang Laboratory (No. 22XJ02003) and the National Natural Science Foundation of China (No. 62122093).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return