НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o405.pdf (1600.60Кб)

УДК 519.6

1 МГТУ им. Н.Э. Баумана, Москва, Россия 2 ООО "ЭКСПЕРТЕК ИБС", Москва. Россия

Обычно классификаторы временных рядов предполагают предобработку сигналов (фильтрация сигналов от шумов, устранение артефактов и т.д.), выделение характерных признаков сигнала (амплитуда, частота, спектр и т.д.), классификацию в пространстве характерных признаков сигналов с использованием классических методов и алгоритмов классификации многомерных данных. Рассматриваем один из методов классификации временных рядов, не требующий выделения характерных признаков сигналов. Метод основан на использовании шейплетов временного ряда (time series shapelets) – небольших фрагментов этого ряда, максимально отражающих свойства одного из его классов.
Не смотря на значительное число публикаций по теории и приложениям шейплетов для классификации временных рядов, актуальной остается задача оценки эффективности этой техники. Данная публикация имеет целью исследовать эффективность ряда модификаций исходного метода шейплетов применительно к классификации многомерных рядов, что представляет собой малоисследованную задачу. Представляем постановку задачи классификации многомерного временного ряда с помощью шейплетов; изложение базового метода бинарной классификации на основе шейплетов, а также различных обобщений и предлагаемой модификации метода; программное обеспечение, реализующее модифицированный метод; результаты вычислительных экспериментов, подтверждающие эффективность принятых алгоритмических и программных решений. Показываем, что модифицированный метод и реализующее его программное обеспечение позволяют получить точность классификации, составляющую, в лучших случаях, около 85%. Время, затрачиваемое на поиск шейплета, возрастает пропорционально размерности входных данных.

1. Трофимов А.Г., Скругин В.И. Адаптивный классификатор многомерных нестационарных сигналов на основе анализа динамических паттернов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 8. Режим доступа: http://technomag.bmstu.ru/doc/151934.html (дата обращения 01.10.2015).
2. Ye L., Keogh E. Time series shapelets: a new primitive for data mining // Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD’09). ACM Publ., 2009. P. 947-956. DOI: 10.1145/1557019.1557122
3. Mueen A., Keogh E., Young N. Logical-Shapelets: An Expressive Primitive for Time Series Classi fi cation // Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11). ACM Publ., 2011. P. 1154-1162. DOI: 10.1145/2020408.2020587
4. Gordon D., Hendler D., Rokach L. Fast Randomized Model Generation for Shapelet-Based Time Series Classification. 2012. Available at: http://arxiv.org/abs/1209.5038, accessed 01.10.2015.
5. He Q., Zhuang F., Shang T., Shi Z. Fast Time Series Classification Based on Infrequent Shapelets // Proceedings of 11th International Conference on Machine Learning and Applications (ICMLA). Vol. 1. IEEE Publ., 2012. P. 215-219. DOI: 10.1109/ICMLA.2012.44
6. Lines J., Bagnall A. Alternative Quality Measures for Time Series Shapelets. Springer Berlin Heidelberg, 2012. P. 475-483. DOI:10.1007/978-3-642-32639-4_58 (Ser. Lecture Notes in Computer Science; vol. 7435.).
7. Lines J., Davis L., Hills J., Bagnall A. A Shapelet Transform for Time Series Classification // Proceedings of the 18th International Conference on Knowledge Discovery in Data and Data Mining (KDD’12). ACM Publ., 2012. P. 289-297. DOI: 10.1145/2339530.2339579
8. Zakaria J., Mueen A., Keogh E. Clustering Time Series using Unsupervised-Shapelets // Proceedings of the 12th IEEE International Conference on Data Mining (ICDM’2012). IEEE Publ., 2012. P. 785-794. DOI: 10.1109/ICDM.2012.26
9. Rakthanmanon T., Keogh E. Fast Shapelets: A Scalable Algorithm for Discovering Time Series Shapelets // Proceedings of the 13th SIAM International Conference on Data Mining (SDM’13). SIAM Publ., 2013. P. 668-676. DOI: 10.1137/1.9781611972832.74
10. Grabocka J., Schilling N., Wistuba M., Schmidt-Thieme L. Learning Time-Series Shapelets // Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’14). ACM Publ., 2014. P. 392-401. DOI:10.1145/2623330.2623613
11. Shapelet based time series classification // The University of East Anglia (UEA): website. Available at: https://www.uea.ac.uk/computing/machine-learning/shapelets, accessed 01.10.2015.
12. Чучуева И.А. Модель экстраполяции временных рядов по выборке максимального подобия // Информационные технологии. 2010. № 12. С. 43-47.
13. Левитин А.В. Алгоритмы: введение в разработку и анализ: пер. с англ. М.: Вильямс, 2006. 576 с .
14. Левинсон Дж.Дж. Тестирование ПО с помощью Visual Studio 2010: пер . с англ . М.: ЭКОМ Паблишерз, 2012. 336 с.
15. Нейгел К., Ивьен Б., Глинн Дж., Уотсон К., Скиннер М. C # и платформа . NET 4 для профессионалов: пер. с англ. М .: Вильямс , 2011. 1440 с .
16. Vail D., Veloso M. Learning from accelerometer data on a legged robot // Proceedings of the 5th IFAC/EURON Symposium on Intelligent Autonomous Vehicles, 2004. Available at: http://www.cs.cmu.edu/~coral/old/publinks/mmv/04iav-doug.pdf, accessed 01.10.2015.
17. Software for Brain Computer Interfaces and Real Time Neirosiences // OpenVibe: website. Available at: http://openvibe.inria.fr/datasets-downloads/, accessed 01.10.2015.
18. Paugam-Moisy H., Bohte S.M. Computing with spiking neuron networks // In: Handbook of Natural Computing / ed. by G. Rozenberg, T. Bäck, J.N. Kok. Springer-Verlag Berlin Heidelberg, 2012. P. 335-376. DOI: 10.1007/978-3-540-92910-9_10
19. Chang K-W., Deka, B., Hwu W-M., Roth D. Efficient Pattern-Based Time Series Classification on GPU // Proceedings of the 12th IEEE International Conference on Data Mining (ICDM’2012). IEEE Publ., 2012. P. 131-140. DOI: 10.1109/ICDM.2012.132