ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПРИМЕНЕНИЯ МЕТОДА ДИНАМИЧЕСКОЙ ТРАНСФОРМАЦИИ ВРЕМЕННОЙ ШКАЛЫ ДЛЯ КЛАСТЕРИЗАЦИИ ВРЕМЕННЫХ РЯДОВ
DOI:
https://doi.org/10.5281/zenodo.19231078Ключевые слова:
кластеризация временных рядов, динамическая трансформация временной шкалы, понижение размерности, гибридные методы, машинное обучение.Поддерживающие организации
Лицензия
Аннотация
Статья посвящена актуальной проблематике повышения эффективности алгоритмов кластеризации временных рядов. Актуальность работы обусловлена не только необходимостью обработки растущих объемов информации из таких сфер, как финансы, интернет вещей, биоинформатика и мониторинг промышленного оборудования, но и потребностью в более глубоком понимании скрытой структуры этих данных. Цель исследования заключается в системном улучшении понимания внутренней структуры временных рядов и, как следствие, в разработке более точных, устойчивых и вычислительно эффективных алгоритмов для их кластерного анализа. В качестве методологической основы проводится всесторонний анализ современных методов кластеризации, акцентирующий внимание на двух ключевых аспектах: оценке структурных сходств между рядами и техниках декомпозиции временных рядов на составные компоненты (тренд, сезонность, шум). Особое внимание в работе уделяется критически важному вопросу выбора адекватной метрики расстояния, поскольку от нее напрямую зависит качество и интерпретируемость итоговых кластеров. Детально исследуется потенциал и ограничения метрики динамической трансформации временной шкалы (DTW), способной учитывать нелинейные искажения по временной оси. Основной теоретический вклад статьи заключается в предложении и обосновании гибридных подходов, которые интегрируют классические алгоритмы кластеризации (такие как K‑средних или иерархическая кластеризация), основанные на метрике DTW, с передовыми методами нелинейного снижения размерности, в частности, с алгоритмом Uniform Manifold Approximation and Projection (UMAP). Такая комбинация позволяет визуализировать и кластеризовать данные в низкоразмерном пространстве, сохраняющем существенные геометрические отношения, что повышает качество группировки и скорость вычислений. Кроме того, в работе отдельно рассматриваются стратегии оптимизации обработки длинных временных рядов, направленные на снижение вычислительной сложности без значительной потери информативности. Практическая ценность исследования подтверждается серией вычислительных экспериментов на синтетических и реальных наборах данных. Представленные результаты наглядно демонстрируют сравнительные преимущества предложенных гибридных методик перед традиционными подходами в терминах точности кластеризации, устойчивости к шуму и вычислительной эффективности. Таким образом, работа вносит значимый вклад в развитие методов интеллектуального анализа временных рядов, предлагая новые, более мощные инструменты для извлечения знаний из данных.
Скачивания
Библиографические ссылки
1. Peker K. Subsequence time series (STS) clustering techniques for meaningful pattern discovery. 2005. 360 - 365. 10.1109/KIMAS.2005.1427109.
2. Jain A.K. Data Clustering: 50 Years Beyond K-Means. Pattern Recognition Letters, 2010. 31(8), 651-666.
3. Murtagh F. Methods of Hierarchical Clustering / F. Murtagh, P. Contreras // ArXiv. 2011. pp. 1-21. URL: https://arxiv.org/pdf/1105.0121.pdf (дата обращения: 27.01.2025).
4. Giorgino T. Computing and Visualizing Dynamic Time Warping Alignments in R: The Dtw Package. Journal of Statistical Software. 2009. 31 (7). 1-24.
5. Kislyakov A., Tikhonuyk N. Principles for Development of Predictive Stability Models of Social and Economic Systems on the basis of DTW // First Conference on Sustainable Develop-ment: Industrial Future of Territories (IFT 2020), 2020. vol. 208, no 08001. DOI: 10.1051/e3sconf/202020808001.
6. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Second Edition // Publisher: Springer, 2017. 745 р.
7. Draganov A., Jørgensen J. Nellemann K., Mottin D., Assent I. Berry T., Aslay C. ActUp: Analyzing and Consolidating tSNE and UMAP. 2023. 10.48550/arXiv.2305.07320.
8. Aghabozorgi S., Seyed Shirkhorshidi A., Wah T. Y. Time-series clustering – A decade review // Information Systems. 2015. Vol. 53. pp. 16-38.
9. Schwenke L., Atzmueller M. Making Time Series Embeddings More Interpretable in Deep Learning: Extracting Higher-Level Features via Symbolic Approximation Representations. The International FLAIRS Conference Proceedings. 2023. 36 p. 10.32473/flairs.36.133107.
10. Serrà, J., Arcos J.L. A Competitive Measure to Assess the Similarity between Two Time Series. In: Agudo, B.D., Watson, I. (eds) Case-Based Reasoning Research and Development. ICCBR 2012. Lecture Notes in Computer Science, 2012. vol 7466. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32986-9_31.
11. Sakoe H., Chiba S. Dynamic programming algorithm optimization for spoken word recognition. // Transactions on ASSP. 1978. № 26. P. 43-49.
12. Salvador S., Chan P. Toward Accurate Dynamic Time Warping in Linear Time and Space. Intelligent Data Analysis. 2004. 11. 70-80.
13. Keogh E. Exact indexing of dynamic time warping. In 28th International Conference on Very Large Data Bases. Hong Kong. 2002. pp 406-417.
14. McInnes L., Healy J., Melville J. Umap: Uniform manifold aProximation and projection for dimension reduction, 2018. //arXiv preprint arXiv:1802.03426.
15. Becht E. et al. Dimensionality reduction for visualizing single-cell data using UMAP //Nature biotechnology, 2019, Т. 37, №. 1, P. 38-44.
16. Kullback, S., Leibler R.A. On Information and Sufficiency. The Annals of Mathematical Statistics, 1951. 22(1), 79-86.
17. Srivastava A. DTW+S: Shape-based Comparison of Time-series with Ordered Local Trend. 2023 10.48550/arXiv.2309.03579.
18. Zhu Z., Peng Q., Guan X. A time series clustering method based on hypergraph partitioning. 2016. 27-31. 10.1109/PIC.2016.7949461.
References
1. Peker K. (2005) Subsequence time series (STS) clustering techniques for meaningful pattern discovery. 360 - 365. 10.1109/KIMAS.2005.1427109.
2. Jain A.K. (2010) Data Clustering: 50 Years Beyond K-Means. Pattern Recognition Letters. 31(8), 651-666.
3. Murtagh F. (2011) Methods of Hierarchical Clustering / F. Murtagh, P. Contreras // ArXiv, pp. 1-21. URL: https://arxiv.org/pdf/1105.0121.pdf (дата обращения: 27.01.2025).
4. Giorgino T. (2009) Computing and Visualizing Dynamic Time Warping Alignments in R: The Dtw Package. Journal of Statistical Software, 31 (7). 1-24.
5. Kislyakov A., Tikhonuyk N. (2020) Principles for Development of Predictive Stability Models of Social and Economic Systems on the basis of DTW // First Conference on Sustainable Develop-ment: Industrial Future of Territories (IFT 2020), vol. 208, no 08001. DOI: 10.1051/e3sconf/202020808001.
6. Hastie T., Tibshirani R., Friedman J. (2017) The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Second Edition // Publisher: Springer, 745 р.
7. Draganov A., Jørgensen J. Nellemann K., Mottin D., Assent I. Berry T., Aslay C. (2023) ActUp: Analyzing and Consolidating tSNE and UMAP. 10.48550/arXiv.2305.07320.
8. Aghabozorgi S., Seyed Shirkhorshidi A., Wah T. Y. (2015) Time-series clustering - A decade review // Information Systems, Vol. 53. pp. 16-38.
9. Schwenke L., Atzmueller M. (2023) Making Time Series Embeddings More Interpretable in Deep Learning: Extracting Higher-Level Features via Symbolic Approximation Representations. The International FLAIRS Conference Proceedings. 36 p. 10.32473/flairs.36.133107.
10. Serrà, J., Arcos J.L. (2012) A Competitive Measure to Assess the Similarity between Two Time Series. In: Agudo, B.D., Watson, I. (eds) Case-Based Reasoning Research and Development. ICCBR 2012. Lecture Notes in Computer Science, vol 7466. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32986-9_31.
11. Sakoe H., Chiba S. (1978) Dynamic programming algorithm optimization for spoken word recognition. // Transactions on ASSP, № 26. P. 43-49.
12. Salvador S., Chan P. (2004) Toward Accurate Dynamic Time Warping in Linear Time and Space. Intelligent Data Analysis, 11. 70-80.
13. Keogh E. (2002) Exact indexing of dynamic time warping. In 28th International Conference on Very Large Data Bases. Hong Kong, pp 406-417.
14. McInnes L., Healy J., Melville J. (2018) Umap: Uniform manifold aProximation and projection for dimension reduction, 2018. //arXiv preprint arXiv:1802.03426.
15. Becht E. et al. (2019) Dimensionality reduction for visualizing single-cell data using UMAP //Nature biotechnology, Т. 37, №. 1, P. 38-44.
16. Kullback, S., Leibler R.A. (1951) On Information and Sufficiency. The Annals of Mathematical Statistics, 22(1), 79-86.
17. Srivastava A. (2023) DTW+S: Shape-based Comparison of Time-series with Ordered Local Trend. 10.48550/arXiv.2309.03579.
18. Zhu Z., Peng Q., Guan X. (2016) A time series clustering method based on hypergraph partitioning, pp. 27-31. 10.1109/PIC.2016.7949461.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.
Статьи журнала «Новое в экономической кибернетике» находятся в открытом доступе и распространяются в соответствии с условиями Лицензионного Договора с Донецким Государственным университетом, который бесплатно предоставляет авторам неограниченное распространение и самостоятельное архивирование.
