Пофонемное распознавание как задача классификации рядов на множестве последовательностей элементов сложных объектов с применением усовершенствованного trie-дерева
Ключевые слова:
trie-дерево, множество последовательностей, классификация рядов на множестве последовательностей элементов сложных объектов, динамическое программирование, пофонемное распознавание речевых командАннотация
Последовательности, в том числе последовательности векторов, применимы в любых предметных областях. Последовательности скалярных значений или векторов (ряды) могут быть порождены последовательностями более высокого порядка, например: последовательностями состояний, элементов сложных объектов. Работа посвящена применению усовершенствованного trie-дерева в задаче классификации ряда на множестве последовательностей элементов сложных объектов методом динамического программирования. Рассмотрены сферы применения динамического программирования. Показано, что динамическое программирование приспособлено к многошаговым операциям вычисления аддитивных (мультипликативных) мер подобия / различия. Утверждается, что усовершенствованное trie-дерево применимо в задаче классификации ряда на множестве последовательностей элементов сложных объектов методом динамического программирования при использовании таких мер подобия / различия. Выполнен анализ иерархических представлений множеств последовательностей. Описаны преимущества, которые обеспечивает усовершенствованное trie-дерево по сравнению с традиционными представлениями других сильноветвящихся деревьев. Разработано формальное описание усовершенствованного trie-дерева. Дано пояснение ранее полученным данным о существенном приросте скорости операций добавления и удаления последовательностей в усовершенствованном trie-дереве относительно использования массива с индексной таблицей (24 и 380 раз, соответственно). Выполнена постановка задачи пофонемного распознавания речевых команд как задачи классификации ряда на множестве последовательностей элементов сложных объектов и изложен метод её решения. Разработан метод классификации ряда на множестве последовательностей элементов сложных объектов с применением усовершенствованного trie-дерева. Он исследован на примере пофонемного распознавания с иерархическим представлением словаря классов речевых команд. В этом методе распознавание речевых команд выполняют в процессе обхода усовершенствованного trie-дерева, хранящего множество транскрипций речевых команд – последовательностей транскрипционных символов, которые обозначают классы звуков. Численные исследования показали, что классификация ряда как последовательности элементов сложных объектов повышает частоту правильной классификации по сравнению с классификацией ряда на множестве рядов, а применение усовершенствованного trie-дерева сокращает затраты времени на классификацию.
Литература
2. Кнут Д.Э. Искусство программирования. Т.3: Сортировка и поиск // М.: Вильямс. 2000. 832 с.
3. Briandais R. File searching using variable-length keys // Proc. Western Joint Computer Conf. 1959. pp. 295–298.
4. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология // СПб.: Невский Диалект; БХВ-Петербург. 2003. 654 с.
5. Liao T.F., Bolano D., Brzinsky-Fay C., Cornwell B., Fasang A.E., Helske S., Piccarreta R., Raab M., Ritschard G., Struffolino E., Studer M. Sequence analysis: Its past, present, and future. Social science research. 2022. vol. 107. DOI: 10.1016/j.ssresearch.2022.102772.
6. Mathew S., Peat G., Parry E., Sokhal B.S., Yu D. Applying sequence analysis to uncover 'real-world' clinical pathways from routinely collected data: a systematic review. Journal of Clinical Epidemiology. 2024. vol. 166. DOI: 10.1016/j.jclinepi.2023.111226.
7. Громов В.А., Мазайшвили К.В., Заикин П.В., Николаев Е.Н., Бесчастнов Ю.Н., Зворыкина Е.И., Паринов А.А., Незнанов А.А. Различение хаотических и регулярных временных рядов для идентификации состояния артериовенозной фистулы // Вестник кибернетики. 2022. № 1(45). С. 72–82.
8. Ковалева К.А., Яхонтова И.М. Теория исследования и разработки методов и моделей прогнозирования временных рядов с приращением в страховании // Новые технологии. 2019. № 4. С. 239–248.
9. Зюсько К.Д. Прогноз спроса на товар с помощью нейронных сетей в условиях меняющейся размерности входных данных // Экономика и качество систем связи. 2020. № 1 (15). С. 36–41.
10. Луценко Е.В. Применение автоматизированного системно-когнитивного анализа банковских баз данных по операциям с кредитными картами для количественной оценки риска мошенничества // Научный журнал КубГАУ. 2021. № 172. С. 82–172.
11. Кузьмин В.Н., Менисов А.Б. Исследование путей и способов повышения результативности выявления компьютерных атак на объекты критической информационной инфраструктуры // Информационно-управляющие системы. 2022. № 4. С. 29–43.
12. Leichtnam L., Totel E., Prigent N., Me L. Sec2graph: Network attack detection based on novelty detection on graph structured data // Detection of Intrusions and Malware, and Vulnerability Assessment: 17th International Conference, DIMVA. Springer International Publishing, 2020. pp. 238–258.
13. Жукова Н.А. Онтологические модели трансформации данных о состоянии технических объектов // Онтология проектирования. 2019. Т. 9. № 3(33). С. 345–360.
14. Nguyen D., Luo W., Nguyen T., Venkatesh S., Phung D. Sqn2Vec: Learning Sequence Representation via Sequential Patterns with a Gap Constraint. Machine Learning and Knowledge Discovery in Databases. Proceedings of the European Conference, ECML PKDD (Part II). 2019. pp. 569–584.
15. Fradkin D., Morchen F. Mining sequential patterns for classification. Knowledge and Information Systems. 2015. № 45 (3). pp. 731–749.
16. Привалов А.Н., Смирнов В.А. Метод нечеткого сравнения строк для обнаружения фейковых сайтов // Известия ТулГУ. Технические науки. 2022. № 2. С. 184–191.
17. Blanchard P. Sequence Analysis. Encyclopedia of Research Methods. London: Sage Publications Ltd. 2020. URL: https://www.researchgate.net/publication/342232021_Sequence_Analysis (дата обращения: 15.05.2024).
18. Vanasse A., Courteau J., Courteau M., Benigeri M., Chiu Y.M., Dufour I., Couillard S., Larivée P., Hudon C. Healthcare utilization after a first hospitalization for COPD: a new approach of State Sequence Analysis based on the '6W' multidimensional model of care trajectories. BMC Health Serv. Res. 2020. vol. 20(1). DOI: 10.1186/s12913-020-5030-0.
19. Su H., Liu S., Zheng B., Zhou X., Zheng K. A survey of trajectory distance measures and performance evaluation. The VLDB Journal. 2020. № 29. pp. 3–32.
20. Калихман И.Л., Войтенко М.А. Динамическое программирование в примерах и задачах: Учеб. Пособие. М.: Высш. школа, 1979. 125 с.
21. Коган Д.И. Динамическое программирование и дискретная многокритериальная оптимизация: учебное пособие. Нижний Новгород: Изд-во Нижегородского ун-та, 2004. 150 с.
22. Баширзаде Л.И., Алиев Г.С. Применение динамического программирования для моделирования процессов принятия решений // Архивариус. 2022. № 3 (66). С. 51–55.
23. Винцюк Т.К. Анализ, распознавание и интерпретация речевых сигналов. К.: Наук. думка, 1987. 262 с.
24. Шелепов В.Ю., Дорохин О.А., Засыпкин А.В., Червин Н.А. О некоторых подходах к проблеме компьютерного распознавания устной русской речи // Труды Междунар. конф. «Знание – Диалог – Решение». 1997. Т. 1. С. 234–240.
25. Alshehri M., Coenen F., Dures K. Sub-sequence-based dynamic time warping. Proceedings of the 11th International Conference on Knowledge Discovery and Information Retrieval. 2019. pp. 274–281.
26. Deriso D., Boyd S. A general optimization framework for dynamic time warping // Optimization and Engineering. 2023. vol. 24. pp. 1411–1432.
27. Wang L., Koniusz P. Uncertainty-DTW for Time Series and Sequences. European Conference on Computer Vision (ECCV 2022). Cham: Springer Nature Switzerland. 2022. vol. 13681. pp. 176–195.
28. Bringmann K., Fischer N., Hoog I., Kipouridis E., Kociumaka T., Rotenberg E. Dynamic Time Warping // Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Publisher Society for Industrial and Applied Mathematics. 2024. pp. 208–242.
29. Jain V., Fokow V., Wicht J., Wetzker U. A Dynamic Time Warping Based Method to Synchronize Spectral and Protocol Domains for Troubleshooting Wireless Communication // IEEE Access. 2023. vol. 11. pp. 64668–64678.
30. Козлов А.В., Саввина Г.В., Шелепов В.Ю. Система пофонемного распознавания отдельно произносимых слов // Искусственный интеллект. 2003. № 1. С. 156–165.
31. Дорохина Г.В. Модификация алгоритма DTW для пофонемного распознавания слов // Проблемы искусственного интеллекта. 2015. № 0(1). С. 38–49.
32. Дорохина Г.В. Анализ методов распознавания речевых команд на основе алгоритма DTW // Труды шестого междисциплинарного семинара «Анализ разговорной русской речи» (АР3-2012) (27-28 августа 2012. г. Санкт-Петербург). 2012. С. 29–34.
33. Васильев В.И., Шевченко А.И., Эш С.Н. Принцип редукции в задачах обнаружения закономерностей: Монография. Донецк, 2009. 340 с.
34. Бурибаева А.К., Дорохина Г.В., Ниценко А.В., Шелепов В.Ю. Сегментация и дифонное распознавание речевых сигналов // Труды СПИИРАН. 2014. Т. 31. № 8. С. 20–42.
35. Дорохина Г.В., Павлюкова А.П. Модуль морфологического анализа слов русского языка // Искусственный интеллект. 2004. № 3. С. 636–642.
36. Дорохина Г.В. Патент на изобретение № UA 78806 «Устройство для хранения и поиска строковых величин и способ хранения и поиска строковых величин». собственник: Институт проблем искусственного интеллекта. Промышленная собственность. 2007. опубл. 25.04.2007.
37. Дорохина Г.В., Павлыш В.Н. Способ представления множеств последовательностей // Информатика и кибернетика. 2016. № 1(3). С. 56–64.
38. Дорохина Г.В. Сравнение затрат памяти для метода деревьев цифрового поиска и его усовершенствования // Искусственный интеллект. 2009. № 4. C. 338–343.
39. Финаев В.И., Дорохина Г.В. Применения усовершенствованных деревьев цифрового поиска // Проблемы искусственного интеллекта. 2019. № 4 (15). С. 62–77.
40. Bantay L., Abonyi J. Frequent pattern mining-based log file partition for process mining // Engineering Applications of Artificial Intelligence. 2023. vol. 123. DOI: 10.1016/j.engappai.2023.106221.
41. Xing Z., Pei J., Keogh J. A brief survey on sequence classification // SIGKDD Explor. 2010. vol. 12(1). pp. 40–48.
42. Atar R.H., Bhosale D.S. Pattern Based Sequence Classification // International Journal of Advanced Research in Science, Communication and Technology (IJARSCT). 2023. vol. 3. № 1. pp. 390–396.
43. Lazzari N., Poltronieri A., Presutti V. Classifying sequences by combining context-free grammars and OWL ontologies // European Semantic Web Conference. Cham: Springer Nature Switzerland, 2023. С. 156–173.
44. Crochemore M., Lecroq T, Liu L., Ozsu T. Encyclopedia of Database Systems. Verlag: Springer. 2009. pp. 3179–3182.
Опубликован
Как цитировать
Раздел
Copyright (c) Галина Владимировна Дорохина
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).