Метод определения периода зашумленной периодической символьной последовательности, основанный на позициях подслов в последовательности
Аннотация
Предложен метод определения периода искаженной шумом периодической последовательности. Период почти периодической последовательности — это длина наименьшего периодически повторяющегося фрагмента, образующего соответствующую обычную периодическую последовательность. Метод может быть применен для искаженных периодических последовательностей, полученных из периодических последовательностей, состоящих из, по крайней мере, восьми полных периодически повторяющихся минимальных фрагментов.
В соответствующих периодических последовательностях с шумом замены, вставки и удаления некоторые периодические фрагменты могут быть искажены из-за внесения шума. Уровень шума предполагается менее 10%, это предположение позволяет использовать оператор сдвига с окном ширины 16 и наблюдать в этом окне более двух раз каждый неповрежденный фрагмент длины 16, содержащийся в исследуемой последовательности.
Метод основан на подсчете числа символов в слове w между первыми символами ближайших одинаковых подслов длины 16. Для вычисления разностей между левыми позициями соседних одинаковых подслов используются только подслова, встретившиеся в рассматриваемом слове более двух раз. Все найденные разности располагаются в порядке возрастания и находятся квантиль 25% и медиана в последовательности разностей.
Вычислительный эксперимент показал, что 25% квантиль дает удовлетворительную оценку периода при уровне шума менее 5 %. Иногда метод дает достаточно хороший результат в случае шума от 5 до 10 %. Зависимость доли удовлетворительных оценок периода от уровня шума исследовалась для каждого типа шума отдельно, а также для смеси шумов всех трех типов в одинаковых пропорциях. Вычислительный эксперимент показал, что 25% квантиль дает более точную оценку периода, чем медиана. Предполагается улучшить метод таким образом, чтобы восстанавливать саму периодическую последовательность только по последовательности с шумом.
Литература
[2] 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. p. 2-11. (In Eng.) DOI: https://doi.org/10.1145/882082.882086
[3] He Z., Wang X.S., Lee B.S., Ling A.C.H. Mining partial periodic correlations in time series. Knowledge and Information Systems. 2008; 15(1):31-54. (In Eng.) DOI: https://doi.org/10.1007/s10115-006-0051-5
[4] 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(C):207-224. (In Eng.) DOI: https://doi.org/10.1016/j.eswa.2017.2.28
[5] Yang K.-J., Hong T.-P., Lan G.-C., Chen Y.-M. A two-phase approach for mining weighted partial periodic patterns. Engineering Applications of Artificial Intelligence. 2014; 30:225-234. (In Eng.) DOI: https://doi.org/10.1016/j.engappai.2014.1.4
[6] He R., Yang S., Yang J., Cao J. Automated Mining of Approximate Periodicity on Numeric Data: A Statistical Approach. In: Proceedings of the 2nd International Conference on Compute and Data Analysis (ICCDA 2018). ACM, New York, NY, USA; 2018. p. 20-27. (In Eng.) DOI: https://doi.org/10.1145/3193077.3194509
[7] Patel M., Modi N. A Comprehensive Study on Periodicity Mining Algorithms. In: 2016 International Conference on Global Trends in Signal Processing, Information Computing and Communication (ICGTSPICC). Jalgaon; 2016. p. 567-575. (In Eng.) DOI: https://doi.org/10.1109/ICGTSPICC.2016.7955365
[8] Aydin B., Angryk R. Spatiotemporal Frequent Pattern Mining on Solar Data: Current Algorithms and Future Directions. In: 2015 IEEE International Conference on Data Mining Workshop (ICDMW). Atlantic City, NJ; 2015. p. 575-581. (In Eng.) DOI: https://doi.org/10.1109/ICDMW.2015.10
[9] Dong S., Liu S., Zhao Y., Shao Z. An Innovative Model to Mine Asynchronous Periodic Pattern of Moving Objects. Multimedia Tools and Applications. 2019; 78(7):8943-8964. (In Eng.) DOI: https://doi.org/10.1007/s11042-018-6752-4
[10] Bjørnstad O.N., Viboud C. Timing and Periodicity of Influenza Epidemics. Proceedings of the National Academy of Sciences. 2016; 113(46):12899-12901. (In Eng.) DOI: https://doi.org/10.1073/pnas.1616052113
[11] 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; 2006. p. 874-875. (In Eng.) DOI: https://doi.org/10.1145/1183614.1183774
[12] 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; 2014. p. 490-494. Available at: https://ksiresearchorg.ipage.com/seke/seke14paper/seke14paper_9.pdf (accessed 15.1.2020). (In Eng.).
[13] 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. p. 449-460. (In Eng.) DOI: https://doi.org/10.1137/1.9,78161E+12.40
[14] 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: https://doi.org/10.3109/10425179509020866
[15] Nesterenko A.Yu. Cycle detection algorithms and their applications. Fundamentalnaya i prikladnaya matematika = Fundamental and Applied Mathematics. 2010; 16(6):109-122. Available at: https://elibrary.ru/item.asp?id=20285258 (accessed 15.1.2020). (In Russ., abstract in Eng.).
[ 16] 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. p.8. (In Eng.) DOI: https://doi.org/10.1109/ICDM.2005.152
[17] 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: https://doi.org/10.1109/TKDE.2005.114
[18] 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: https://doi.org/10.1007/s10489-008-0144-9
[19] Ukkonen E. On-line construction of suffix trees. Algorithmica. 1995; 14(3):249-260. (In Eng.) DOI: https://doi.org/10.1007/BF01206331
[20] 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: https://doi.org/10.1088/1742-6596/788/1/012019
[21] 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: https://doi.org/10.1155/2017/7949287
[22] 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: https://doi.org/10.1093/dnares/6.3.153
[23] Zhukova G.N., Smetanin Yu.G., Ulyanov M.V. Comparison of Some Algorithms for Periodicity Detection in Symbolic Sequences in the Presence of Distortions. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2019; 15(4):905-915. (In Russ., abstract in Eng.) DOI: https://doi.org/10.25559/SITITO.15.201904.905-915
[24] Smetanin Y.G., Ulyanov M.V., Pestova A.S. Entropy Approach to the Construction of a Measure of Word Symbolic Diverseness and its Application to Clustering of Plant Genomes. Mathematical Biology and Bioinformatics. 2016; 11(1):114-126. (In Russ., abstract in Eng.) DOI: https://doi.org/10.17537/2016.11.114
[25] Zhukova G.N., Smetanin Yu.G., Ulyanov M.V. A Stochastic Model of Noises for Periodic Symbol Sequences. Sovremennye informacionnye tehnologii i IT-obrazovanie = Modern Information Technologies and IT-Education. 2019; 15(2):431-440. (In Russ., abstract in Eng.) DOI: https://doi.org/10.25559/SITITO.15.201902.431-440
Это произведение доступно по лицензии 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.
