面向时间序列的鲁棒性半监督模糊C均值聚类

doi:10.3778/j.issn.1002-8331.2207-0445

摘要/Abstract

摘要： 针对时间序列模糊C均值聚类算法对噪声数据敏感，及其未能将数据中少量已标记数据所包含的监督信息进行有效利用的问题，提出了一种改进的鲁棒性半监督模糊C均值聚类算法。该算法中先使用马氏距离提出一种样本不确定性分析方法，并加入到半监督模糊C均值聚类建模中，以消除噪声点的影响。并改进半监督模糊C均值聚类的部分监督机制来加大已标记数据的监督能力。采用能够弹性度量时间序列相似性的时间扭曲编辑距离代替欧氏距离进行聚类。通过对7组公开的时间序列数据集进行实验对比，结果表明所提算法具有良好的聚类效果。

关键词: 时间序列, 半监督聚类, 模糊C均值聚类, 样本不确定性, 时间扭曲编辑距离

Abstract: The fuzzy C-means clustering algorithm is sensitive to noisy data, and it fails to effectively utilize the supervised information contained in the small amount of labeled data in time series data. To address these problems, the paper proposes an improved robust semi-supervised fuzzy C-means clustering algorithm（SRFCM）. Firstly, a sample uncertainty analysis method based on Mahalanobis distance is proposed, and add it to the semi-supervised fuzzy C-means clustering（SFCM） modeling to eliminate the influence of noise points. On this basis, by improving the partial supervision mechanism of SFCM, the supervision ability of labeled data is increased. And in the clustering process, the time warped edit distance（TWED）, which can elastically measure the similarity of time series, is used instead of the traditional Euclidean distance. Through the experimental comparison of 7 groups of public time series datasets, the results show that the algorithm has excellent clustering effect.

Key words: time series, semi-supervised clustering, fuzzy C-means clustering, sample uncertainty, time warping edit distance

徐久成, 侯钦臣, 瞿康林, 孙元豪, 孟祥茹. 面向时间序列的鲁棒性半监督模糊C均值聚类[J]. 计算机工程与应用, 2023, 59(8): 73-80.

XU Jiucheng, HOU Qinchen, QU Kanglin, SUN Yuanhao, MENG Xiangru. Robust Semi-Supervised Fuzzy C-Means Clustering for Time Series[J]. Computer Engineering and Applications, 2023, 59(8): 73-80.

参考文献

[1] FU T.A review on time series data mining[J].Engineering Applications of Artificial Intelligence，2011，24（1）：164-181.
[2] 李国荣，冶继民，甄远婷.基于新的鲁棒相似性度量的时间序列聚类[J].计算机应用，2021，41（5）：1343-1347.
LI G R，YE J M，ZHEN Y T.Time series clustering based on new robust similarity measure[J].Journal of Computer Applications，2021，41（5）：1343-1347.
[3] 李海林，贾瑞颖，谭观音.基于K-Shape的时间序列模糊分类方法[J].电子科技大学学报，2021，50（6）：899-906.
LI H L，JIA R Y，TAN G Y.Fuzzy classification for time series data based on K-Shape[J].University of Electronic Science and Technology，2021，50（6）：899-906.
[4] 潘金艳，高朋，高云龙，等.基于可靠性的鲁棒模糊聚类[J].控制理论与应用，2021，38（4）：516-528.
PAN J Y，GAO P，GAO Y L，et al.Reliability-based of robust fuzzy flustering[J].Control Theory & Applications，2021，38（4）：516-528.
[5] WANG L，XU P，MA Q.Incremental fuzzy clustering of time series[J].Fuzzy Sets and Systems，2021，421：62-76.
[6] D’URSO P，DE GIOVANNI L，MASSARI R.Trimmed fuzzy clustering of financial time series based on dynamic time warping[J].Annals of Operations Research，2021，299（1）：1379-1395.
[7] LUCZAK A，KALINOWSKI S.Fuzzy clustering methods to identify the epidemiological situation and its changes in European countries during COVID-19[J].Entropy，2021，24（1）：1-14.
[8] BEI H，MAO Y，WANG W，et al.Fuzzy clustering method based on improved weighted distance[J].Mathematical Problems in Engineering，2021，2021（5）：1-11.
[9] AGHABOZORGI S，SHIRKHORSHIDI A S，WAH T Y.Time-series clustering-a decade review[J].Information Systems，2015，53：16-38.
[10] DAU H A，BEGUM N，KEOGH E.Semi-supervision dramatically improves time series clustering under dynamic time warping[C]//Proceedings of the 25th ACM International，Association for Computing Machinery，New York，2016：999-1008.
[11] TOON V C，WANNES M，SEBASTIJAN D，et al.Lectur notes in computer science[M].Switzerland：Springer International，2018：179-193.
[12] HE G，PAN Y，XIA X，et al.A fast semi-supervised clustering framework for large-scale time series data[J].IEEE Transactions on Systems，2021，51：4201-4216.
[13] KEOGH E，RATANAMAHATANA C A.Exact indexing of dynamic time warping[J].Knowledge and Information Systems，2005，7（3）：358-386.
[14] MARTEAU P F.Time warp edit distance with stiffness adjustment for time series matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2008，31（2）：306-318.
[15] SERRA J，ARCOS J L.An empirical evaluation of simi-
larity measures for time series classification[J].Knowledge-Based Systems，2014，67：305-314.
[16] LIKAS A，VLASSIS N，VERBEEK J J.The global k-means clustering algorithm[J].Pattern Recognition，2003，36（2）：451-461.
[17] KANNAN S R，RAMATHILAGAM S，CHUNG P C.Effective fuzzy c-means clustering algorithms for data clustering problems[J].Expert Systems with Applications，2012，39（7）：6292-6300.
[18] BENSAID A M，HALL L O，BEZDEK J C，et al.Partially supervised clustering for image segmentation[J].Pattern Recognition，1996，29（5）：859-871.
[19] 白福均，高建瓴，宋文慧，等.半监督模糊聚类算法的研究与改进[J].通信技术，2018，51（5）：1061-1065.
BAI F J，GAO J L，SONG W H，et al.Exploration and improvement of semi-supervised fuzzy clustering algorithm[J].Communications Technology，2018，51（5）：1061-1065.
[20] SAKAMOTO Y，MIYAMOTO N.Combine Mahalanobis distance，interpolation auto encoder and classification approach for anomaly detection[R].2021.
[21] PEDRYCZ W，WALETZKY J.Fuzzy clustering with partial supervision[J].IEEE Transactions on Systems Man & Cybernetics，1997，27（5）：87-95.
[22] STEINLEY D.Properties of the Hubert-Arable adjusted Rand index[J].Psychological Methods，2004，9（3）：386-396.
[23] FOWLKES E B，MALLOWS C L.A method for comparing two hierarchical clusterings[J].Journal of the American Statistical Association，1983，78：553-569.
[24] ROSENBERG A，HIRSCHBERG J.V-measure：a conditional entropy-based external cluster evaluation[C]//Proceedings of EMNLP-CoNLL Prague，Czech Republic，2007：410-420.
[25] RADOVANOVIC A，YE X，MILANOVIC J V，et al.Application of the k-medoids partitioning algorithm for clustering of time series data[C]//Proceedings of the IEEE PES Innovative Smart Grid Technologies Europe，Hague，Netherlands，2020：645-649.
[26] SURIS F N A，BAKAR M A A，ARIFF N M，et al.Malaysia PM10 air quality time series clustering based on dynamic time warping[J].Atmosphere，2022，13（4）：503.
[27] PAPARRIZOS J，GRAVANO L.k-Shape：efficient and accurate clustering of time series[J].ACM SIGMOD Record，2015，45（1）：69-76.