Сравнение основных алгоритмов поиска циклов в символьных последовательностях при наличии искажений
Аннотация
В последние годы разработано множество новых алгоритмов для поиска повторяющихся фрагментов в символьных последовательностях с шумом, а также для определения длины периода. Интерес к этим алгоритмам обусловлен тем, что символьные последовательности, полученные на основе реальных данных, не являются периодическими в обычном смысле, а лишь до какой-то степени похожи на них. Для анализа скрытой периодичности в последовательностях, полученных из реальных данных, используется идея представления последовательности как результата внесения искажений в обычную периодическую последовательность.
Наличие искажений замены символа на какой-то другой, вставки или удаления символа не позволяет использовать традиционные алгоритмы поиска длины периода для анализа такой символьной последовательности. Более того, само понятие периодичности последовательности при наличии искажений требует отдельного определения, поскольку обычное понятие периода в этом случае неприменимо. В статье приводятся определения символьной и сегментной периодичности, а также скрытого повторяющегося фрагмента. Кратко описаны алгоритмы CONV, WARP, STNR и алгоритм группы исследователей под руководством Е.Короткова, указана вычислительная сложность алгоритмов CONV, WARP и STNR. Также приведены оценки значимости получаемых в результате работы этих методов значений длины периода.
Рассматриваемые алгоритмы сравниваются между собой по устойчивости к шуму разных типов (замена, вставка, удаление символа, а также их комбинация). Все методы позволяют выявить с некоторой долей уверенности скрытый период, если уровень шума менее 0.1. Алгоритм CONV позволяет определять скрытый период и при большем уровне шума, но при условии, что есть только шум замены. Остальные алгоритмы дают хорошие результаты и в случае шумов всех трех типов. Самым устойчивым к шуму алгоритмом оказался STNR.
Литература
[2] Parthasarathy S., Mehta S., Srinivasan S. Robust Periodicity Detection Algorithms. In: Proceedings of the 15th ACM international conference on Information and knowledge management (CIKM ’06). Association for Computing Machinery, New York, NY, USA, pp. 874-875. (In Eng.) DOI: 10.1145/1183614.1183774
[3] Salvador S., Chan P. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis. 2007; 11(5):561-580. (In Eng.) DOI: 10.3233/IDA-2007-11508
[4] Otunba R., Lin J. APT: Approximate Period Detection in Time Series. In: Proceedings of the 26th International Conference on Software Engineering & Knowledge Engineering (SEKE). Vancouver, Canada, July 1-3, 2014, pp. 490-494. Available at: https://ksiresearchorg.ipage.com/seke/seke14paper/seke14paper_9.pdf (accessed 10.08.2019). (In Eng.)
[5] Lin J., Keogh E., Lonardi S., Chiu B. A Symbolic Representation of Time Series, with Implications for Streaming Algorithms. In: Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery (DMKD’03). Association for Computing Machinery, New York, NY, USA, 2003, pp. 2-11. (In Eng.) DOI: 10.1145/882082.882086
[6] Pommerening K. Finding the Period of a Periodic Sequence. 2009, pp. 1-6. Available at: https://www.staff.uni-mainz.de/pommeren/MathMisc/Periods.pdf (accessed 28.07.2019). (In Eng.)
[7] Vlachos M., Yu P., Castelli V. On Periodicity Detection and Structural Periodic Similarity. In: Proceedings of the 2005 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, 2005, pp. 449-460. (In Eng.) DOI: 10.1137/1.9781611972757.40
[8] Otunba R., Lin J., Senin P. MBPD: Motif-Based Period Detection. In: Peng WC. et al. (eds) Pacific-Asia Conference on Knowledge Discovery and Data Mining. Trends and Applications in Knowledge Discovery and Data Mining. PAKDD 2014. Lecture Notes in Computer Science, vol. 8643. Springer, Cham, 2014, pp. 793-804. (In Eng.) DOI: 10.1007/978-3-319-13186-3_71
[9] Rao K.P., Gayathri M. Noise Resilient Periodicity Mining in Time Series Data Bases. International Journal of Computer Science and Network Security. 2014; 14(7):41-44. Available at: http://paper.ijcsns.org/07_book/201407/20140707.pdf (accessed 28.07.2019). (In Eng.)
[10] JishaKrishnan, Chitharanjan K. Periodicity detection algorithms in time series databases-a survey. International Journal of Computer Science & Engineering Technology. 2013; 4(1):22-28. Available at: http://www.ijcset.com/docs/IJCSET13-04-01-013.pdf (accessed 28.07.2019). (In Eng.)
[11] Sujatha B., Pandian S. C. Noise Removal in Distributed Time Series Database Using Predominant Pattern Distribution Model. IOSR Journal of Engineering. 2013; 3(2):06-13. (In Eng.) DOI: 10.9790/3021-03220613
[12] Ma Sh., Hellerstein J.L. Mining Partially Periodic Event Patterns with Unknown Periods. In: Proceedings 17th International Conference on Data Engineering. Heidelberg, Germany, 2001, pp. 205-214. (In Eng.) DOI: 10.1109/ICDE.2001.914829
[13] Sujatha B., Pandian S. C. Multiplex Tree Pruning for Periodic Pattern Mining. International Journal of Soft Computing. 2014; 9(1):37-43. (In Eng.) DOI: 10.36478/ijscomp.2014.37.43
[14] Grossi R., Italiano G.F. Suffix trees and their applications in string algorithms. In: Proceedings of the 1st South American Workshop on String Processing. 1993, pp. 57-76. (In Eng.)
[15] Chanda A.K., Ahmed C.F., Samiullah Md., Leung C.K. A new framework for mining weighted periodic patterns in time series databases. Expert Systems with Applications. 2017; 79:207-224. (In Eng.) DOI: 10.1016/j.eswa.2017.02.028
[16] Chanda A.K., Saha S., Nishi M.A., Samiullah Md., Ahmed C.F. et al. An efficient approach to mine flexible periodic patterns in time series databases. Engineering Applications of Artificial Intelligence. 2015; 44:46-63. (In Eng.) DOI: 10.1016/j.engappai.2015.04.014
[17] Yuan Q., Zhang W., Zhang C., Geng X., Cong G., Han J. PRED: Periodic Region Detection for Mobility Modeling of Social Media Users. In: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining (WSDM’17). Association for Computing Machinery, New York, NY, USA, 2017, pp. 263-272. (In Eng.) DOI: 10.1145/3018661.3018680
[18] Yuan Q., Shang J., Cao X., Zhang C., Geng X., Han J. Detecting Multiple Periods and Periodic Patterns in Event Time Sequences. In: Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (CIKM ’17). Association for Computing Machinery, New York, NY, USA, 2017, pp. 617-626. (In Eng.) DOI: 10.1145/3132847.3133027
[19] Han J., Dong G., Yin Y. Efficient mining of partial periodic patterns in time series database. In: Proceedings 15th International Conference on Data Engineering (Cat. No.99CB36337), Sydney, NSW, Australia, 1999, pp. 106-115. (In Eng.) DOI: 10.1109/ICDE.1999.754913
[20] Berndt D.J., Clifford J. Using Dynamic Time Warping to Find Patterns in Time Series. In: KDD-94:AAAI-94 Workshop on Knowledge Discovery in Databases. 1994; 10(16):359-370. Available at: https://aaai.org/Papers/Workshops/1994/WS-94-03/WS94-03-031.pdf (accessed 28.07.2019). (In Eng.)
[21] Grassly N.C., Fraser C. Seasonal infectious disease epidemiology. Proceedings of the Royal Society of London B: Biological Sciences. 2006; 273(1600):2541-2550. (In Eng.) DOI: 10.1098/rspb.2006.3604
[22] Xylogiannopoulos K.F., Karampelas P., Alhajj R. Analyzing very large time series using suffix arrays. Applied Intelligence. 2014; 41(3):941-955. (In Eng.) DOI: 10.1007/s10489-014-0553-x
[23] Nesterenko A.Yu. Cycle detection algorithms and their applications. Fundamentalnaya i prikladnaya matematika. 2010; 16(6):109-122. Available at: https://elibrary.ru/item.asp?id=20285258& (accessed 28.07.2019). (In Russ., abstract in Eng.)
[24] Brent R.P. An improved Monte Carlo factorization algorithm. BIT Numerical Mathematics. 1980; 20(2):176-184. (In Eng.) DOI: 10.1007/BF01933190
[25] Elfeky M.G., Aref W.G., Elmagarmid A.K. Periodicity detection in time series databases. IEEE Transactions on Knowledge and Data Engineering. 2005; 17(7):875-887. (In Eng.) DOI: 10.1109/TKDE.2005.114
[26] Elfeky M.G., Aref W.G., Elmagarmid A.K. WARP: time warping for periodicity detection. In: Fifth IEEE International Conference on Data Mining (ICDM'05), Houston, TX, 2005, pp. 8. (In Eng.) DOI: 10.1109/ICDM.2005.152
[27] Rasheed F., Alhajj R. STNR: A suffix tree based noise resilient algorithm for periodicity detection in time series databases. Applied Intelligence. 2010; 32(3):267-278. (In Eng.) DOI: 10.1007/s10489-008-0144-9
[28] Ukkonen E. On-line construction of suffix trees. Algorithmica. 1995; 14(3):249-260. (In Eng.) DOI: 10.1007/BF01206331
[29] Korotkov E.V., Korotkova M.A. Developing New Mathematical Method for Search of the Time Series Periodicity with Deletions and Insertions. Journal of Physics: Conference Series. 2017; 788(1):012019. (In Eng.) DOI: 10.1088/1742-6596/788/1/012019
[30] Frenkel F.E., Korotkova M.A., Korotkov E.V. Database of Periodic DNA Regions in Major Genomes. BioMed Research International. 2017; 2017:7949287. (In Eng.) DOI: 10.1155/2017/7949287
[31] Korotkov E.V. et al. Latent Periodicity Regions in Amino Acid Sequences. Molekuliarnaia Biologiia = Molecular Biology. 1999; 33(4):611-617. (In Eng.)
[32] Chaley M.B., Korotkov E.V., Skryabin K.G. Method Revealing Latent Periodicity of the Nucleotide Sequences Modified for a Case of Small Samples. DNA Research. 1999; 6(3):153-163. (In Eng.) DOI: 10.1093/dnares/6.3.153
[33] Korotkova M.A., Korotkov E.V., Rudenko V.M. Latent periodicity of protein sequences. Journal of Molecular Modeling. 1999; 5(6):103-115. (In Eng.) DOI: 10.1007/s008940050122
[34] Korotkov E.V., Korotkova M.A. Latent periodicity of DNA sequences from some human gene regions. DNA Sequence. 1995; 5(6):353-358. (In Eng.) DOI: 10.3109/10425179509020866
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
