Выявление и кластеризация шаблонных текстов в больших массивах сообщений

Аннотация

Многие сервисы используют короткие сообщения для различных целей, например, магазины рассылают акционные предложения, МЧС России информирует население при угрозе возникновения чрезвычайных ситуаций природного и техногенного характера. Выделение из общего трафика коротких текстов шаблонных сообщений можно использовать для фильтрации спама и рассылок, чтобы уберечь пользователей от мошеннических действий. Зачастую такие массивы сообщений достигают настолько больших размеров, что их хранение и обработка на одном выделенном персональном компьютере или сервере попросту невозможны. Разработаны методы эффективного выявления и кластеризации шаблонных текстов из больших массивов коротких сообщений с применением фреймворка для реализации распределенной обработки неструктурированных данных. Рассмотрены методы, позволяющие проводить кластеризацию на больших массивах сообщений с применением распределенных вычислений без предварительного получения векторных представлений текстов. Приведены алгоритмы для эффективного выявления шаблонных сообщений из больших массивов коротких текстов. Выполнено сравнение алгоритмов по производительности и качеству выявления шаблонов

Просьба ссылаться на эту статью следующим образом:

Вишняков И.Э., Иванов И.П., Каркин И.А. Выявление и кластеризация шаблонных текстов в больших массивах сообщений. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение, 2022, № 4 (141), с. 20--35. DOI: https://doi.org/10.18698/0236-3933-2022-4-20-35

Литература

[1] Кириченко К.М., Герасимов М.Б. Обзор методов кластеризации текстовой информации. Dialogue 2001. M., 2001.URL: https://www.dialog21.ru/digest/2001/articles/kirichenko (дата обращения: 20.12.2021).

[2] Apache Spark: веб-сайт. URL: https://spark.apache.org (дата обращения: 20.12.2021).

[3] Mikolov T., Chen K., Corrado G., et al. Distributed representations of words and phrases and their compositionality. Proc. 26th NIPS, 2013, vol. 2, pp. 3111--3119.

[4] Огурцов А.Н. Основы биоинформатики. Харьков, ХПИ, 2013.

[5] Hartigan J.A., Wong M.A. A K-means clustering algorithm. J. R. Stat. Soc. Ser. C Appl. Stat., 1979, vol. 28, pp. 100--108. DOI: https://doi.org/10.2307/2346830

[6] Tan P.N., Steinbach М.М., Kumar V. Introduction to data mining. New York, Addison Wesley, 2006.

[7] Гасфилд Д. Строки, деревья и последовательности в алгоритмах. СПб., Невский Диалект, 2003.

[8] Ukkonen E. On-line construction of suffix trees. Algorithmica, 1995, vol. 14, no. 3, pp. 249--260. DOI: https://doi.org/10.1007/BF01206331

[9] Sabbir A., Mohammad R.R., Motaher H., et al. An improved frequent pattern mining algorithm using suffix tree & suffix automata. Bangladesh, Dhaka, Univ. of Asia Pacific, 2014.

[10] Вирцева Н.С., Вишняков И.Э. Выявление и выделение шаблонов в массиве коротких сообщений. Наука и образование: научное издание МГТУ им. Н.Э. Баумана, 2016, № 10. DOI: 10.7463/1016.0848929

[11] Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады АН СССР, 1965, т. 163, № 4, с. 845--848.

[12] Дубанов А.В. Сравнение исходных текстов программ путем выравнивания последовательностей токенов. Инженерный журнал: наука и инновации, 2014, № 9. DOI: https://doi.org/10.18698/2308-6033-2014-9-1318

[13] Yujian L., Bo L.A. Normalized Levenshtein distance metric. IEEE Trans. Pattern Anal. Mach. Intell., 2007, vol. 29, no. 6, pp. 1091--1095. DOI: https://doi.org/10.1109/TPAMI.2007.1078

[14] Бойцов Л.М. Использование хеширования по сигнатуре для поиска по сходству. Прикладная математика и информатика, 2000, № 7, с. 135--153.

[15] Bahmani B., Moseley B., Vattani A., et al. Scalable K-Means++. Proc. VLDB Endow., 2012, vol. 5, no. 7, pp. 622--633. DOI: http://dx.doi.org/10.14778/2180912.2180915

[16] Wang Y., Gu Y., Shun J. Theoretically-efficient and practical parallel. Proc. SIGMOD’20, 2020, pp. 2555--2571. DOI: https://doi.org/10.1145/3318464.3380582

[17] Apache ML Clustering --- DBSCANCluster. commons.apache.org: веб-сайт. URL: https://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/org/apache/commons/math3/ml/clustering/DBSCANClusterer.html (дата обращения 20.12.2021).

[18] Index of /ruwiki/. dumps.wikimedia.org: веб-сайт. URL: https://dumps.wikimedia.org/ruwiki (дата обращения: 20.12.2021).

[19] Russian troll tweets. kaggle.com: веб-сайт. URL: https://www.kaggle.com/vikasg/russian-troll-tweets?select=tweets.csv (дата обращения: 20.12.2021).

[20] Apache Hadoop. hadoop.apache.org: веб-сайт. URL: https://hadoop.apache.org (дата обращения: 20.12.2021).