AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (3.8 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

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
Show Author Information

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 clusteringevolutionary multi-taskingmultifactorial optimizationclustering validity indexdistance measure

References

[1]
S. Aghabozorgi, A. S. Shirkhorshidi, and T. Y. Wah, Time-series clustering–a decade review, Inf. Syst., vol. 53, pp. 16–38, 2015.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[12]
U. Maulik and S. Bandyopadhyay, Genetic algorithm-based clustering technique, Pattern Recogn., vol. 33, no. 9, pp. 1455–1465, 2000.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[24]
G. Gan, C. Ma, and J. Wu, Data Clustering: Theory, Algorithms, and Applications, 2nd ed. Alexandria, VA, USA: SIAM, 2007.
Crossref
[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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
[29]
R. A. Armstrong, Should Pearson’s correlation coefficient be avoided? Ophthalmic Physiol. Opt., vol. 39, no. 5, pp. 316–327, 2019.
Crossref 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.
Crossref 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., .
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref 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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 2,
April 2024
Pages 343-355
DOI: 10.26599/TST.2023.9010036
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

515

Views

79

Downloads

2

Crossref

1

Web of Science

2

Scopus

0

CSCD

Altmetrics
Received: 21 March 2023
Revised: 10 April 2023
Accepted: 19 April 2023
Published: 22 September 2023
© The author(s) 2024.

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