научное издание МГТУ им. Н.Э. Баумана
НАУКА и ОБРАЗОВАНИЕ
Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211. ISSN 1994-0408
# 10, октябрь 2016
DOI: 10.7463/1016.0848929
SE-BMSTU...o131.pdf
(1218.22Кб)
| УДК 004.021 | 1 МГТУ им. Н.Э. Баумана, Москва, Россия  |
Проблема поиска шаблонов в произвольном множестве коротких текстовых сообщений актуальна при выявлении и анализе автоматически генерируемых сообщений, в том числе рекламных и вредоносных. Под шаблоном понимается последовательность символов, часть которых фиксирована, а часть может принимать произвольные значения.
Поиск шаблонов включает этапы предобработки сообщений из входного множества, выделения групп похожих сообщений, вероятно относящихся к одному шаблону, и определения структуры шаблона по найденным группам. Предобработка сообщения заключается в его разделении на слова, после чего возможна замена на специальные символы слов, заведомо относящихся к переменным частям шаблонов (дат, адресов, гиперссылок и т.п.). Для выделения групп похожих сообщений используется метод, основанный на использовании модифицированного алгоритма построения FP-дерева с последующим уточнением результатов с помощью кластеризации. Данный метод демонстрирует приемлемое время выполнения при высоких показателях точности и полноты (значение F-меры в ряде тестов близко к максимуму) Выделение структуры шаблона, то есть его постоянных и переменных частей, производится путём множественного выравнивания сообщений, относящихся к одной группе.
Классификация произвольного сообщения подразумевает его отнесение к одному из выделенных шаблонов. Сообщение должно быть отнесено к шаблону, если в нём присутствуют все постоянные части этого шаблона в заданном порядке. Выбор шаблонов-кандидатов для сопоставления производится на основе оценки близости шаблона с входным сообщением. Предварительное тестирование трёх различных способов оценки близости (по количеству совпадающих слов, по расстоянию до сообщения и по счёту за выравнивание) позволило оценить эффективность их использования с точки зрения времени выполнения и точности классификации. В результате был предложен способ формирования списка шаблонов-кандидатов, последовательно использующий метрическую и основанную на счёте за выравнивание оценки.
Интерес для дальнейших исследований представляет задача автоматического поиска оптимальных параметров алгоритмов в зависимости от массива входных сообщений, а также более детальное изучение влияния предобработки сообщений на качество результатов.
1. Vermij, E.P. Genetic sequence alignment on a supercomputing platform. Thesis…MSc. Delft: DelftUniversityofTechnology, 2011. 87 p.
2. Дубанов А.В. Сравнение исходных текстов программ путем выравнивания последовательностей токенов // Инженерный журнал: наука и инновации. 2014. № 9(33). DOI: 10.18698/2308-6033-2014-9-1318
3. Burrows S., Tahaghoghi S.M.M., Zobel J. Efficient plagiarism detection for large code repositories // Software: Practice and Experience. 2007. Vol. 37. №. 2. Pp. 151-176. DOI: 10.1002/spe.750
4. Schleimer S., Wilkerson D. S., Aiken A. Winnowing: local algorithms for document fingerprinting // SIGMOD’03: Proc. of the 2003 ACM SIGMOD intern. conf. on management of data. N.Y.: ACM, 2003. Pp.76-85. DOI: 10.1145/872757.872770
5. Gunawardena T., Lokuhetti M., Pathirana N., Ragel R., Deegalla S. An automatic answering system with template matching for natural language questions // ICIAFs: Proc. 5th Intern. Conf. on information and automation for sustainability. Piscataway: IEEE, 2010. Pp. 353-358. DOI: 10.1109/ICIAFS.2010.5715686
6. Han J., Pei J., Yin Y. Mining Frequent Patterns without Candidate Generation // Newsletter ACM SIGMOD Record. 2000. Vol. 29. № 2. Pp.1-12. DOI: 10.1145/335191.335372
7. Gupta G., Strehl A., Ghosh J. Distance Based Clustering of Association Rules // Intelligent Engineering Systems Through Artificial Neural Networks: Proceedings of Artificial neural networks in engineering conf. (ANNIE). N.Y.: ASME Press, 1999. Pp. 759–764.
8. De Amorim R.C. Feature Relevance in Ward’s Hierarchical Clustering Using the Lp Norm // Journal of Classification. 2015. Vol. 32. № 1. Pp. 46-62. DOI: 10.1007/s00357-015-9167-1
9. Manning C.D., Raghavan P., Schutze H. Hierarchical Clustering // Manning C.D., Raghavan P., Schutze H. Introduction to Information Retrieval. Camb.: Cambridge Univ. Press, 2009, pp. 377-401. DOI: 10.1017/CBO9780511809071
10. Neuwald A.F., Altschul S.F. Bayesian Top-Down Protein Sequence Alignment with Inferred Position-Specific Gap Penalties // PLoS Computational Biology. 2016. Vol. 12. №. 5. Pp. 1-21. DOI: 10.1371/journal.pcbi.1004936
11. Pearson W.R., Lipman D.J. Improved tools for biological sequence comparison // Proc. of the National Academy of Sciences. 1988. Vol. 85. № 8. Pp. 2444-2448. DOI: 10.1073/pnas.85.8.2444
Публикации с ключевыми словами: кластеризация, короткие сообщения, классификация сообщений, выравнивание последовательностей, FP-дерево
Публикации со словами: кластеризация, короткие сообщения, классификация сообщений, выравнивание последовательностей, FP-дерево
Смотри также:
Тематические рубрики:
| Авторы |
| Пресс-релизы |
| Библиотека |
| Конференции |
| Выставки |
| О проекте |
| Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00) |
|
 |
|||
| © 2003-2024 «Наука и образование» Перепечатка материалов журнала без согласования с редакцией запрещена Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00) | |||||
