Алгоритм кластеризации потока данных с изменяющимися параметрами распределения

Об авторе:

Ниссенбаум Ольга Владимировна, кандидат физико-математических наук, доцент кафедры информационной безопасности, Тюменский государственный университет; o.v.nissenbaum@utmn.ru

Аннотация:

На основании динамического ЕМ-алгоритма построен алгоритм кластеризации для потока данных, взвешенных по времени поступления. Алгоритм предназначен для кластеризации данных с нормальным распределением в, параметры которого изменяются во времени, что соответствует ситуации в реальных динамических системах, таких как компьютерные системы, сети связи и т.п. Хранения обработанных данных не требуется, алгоритм эффективно вычислим, может применяться в системах реального времени. Приведены данные вычислительного эксперимента (на имитационной модели потока c нормальной плотностью распределения кластеров), показавшие более высокое качество работы по сравнению с алгоритмом, в котором не используются весовые коэффициенты от времени, с точки зрения доли неверно распознанных точек и точности определения параметров рассчитываемых кластеров.

Список литературы:

1. Munro, J., Paterson, M. Selection and Sorting with Limited Storage // Theoretical Computer Science. 1980. Pp. 315-323.

2. Henzinger, M., Raghavan, P., Rajagopalan, S. Computing on Data Streams // Digital Equipment Corporation. SRC TN-1998-011, August 1998.

3. Barbara, D. Requirements for clustering data streams // ACM SIGKDD Explorations Newsletter. 2003. Vol. 3. №. 2. Pp. 23-27.

4. Cao, F., Zhou, A. Y. Fast clustering of data streams using graphics processors // Journal of Software. 2007. Vol. 18. №. 2. Pp. 291-302.

5. Zhu, W. H., Yin, J., Xie, Y. H. Arbitrary shape cluster algorithm for clustering data stream // Journal of Software. 2006. Vol. 17. №. 3. Pp. 379-387.

6. Chandrika, J., Ananda Kumar, K.R. Dynamic Clustering Of High Speed Data Streams // International Journal of Computer Science Issues. 2012. Vol. 9. Iss. 2. №. 1. Pp. 224-228.

7. Qian Quan, Chao-Jie Xiao, Rui Zhang. Grid-based Data Stream Clustering for Intrusion Detection // International Journal of Network Security. 2013. Vol. 15. №. 1. Jan. Pp. 1-8.

8. Ниссенбаум О.В., Присяжнюк А.С. Адаптивный алгоритм отслеживания аномальной активности в компьютерной сети на основании характерных изменений оценок альтернирующего потока // Прикладная дискретная математика. 2010. Прил. №3. С. 55-58.

9. Mingzhou Song, Hongbin Wang. Highly efficient incremental estimation of Gaussian mixture models for online data stream clustering // Proceedings of SPIE 5803. 2005. Pp. 174-183.

10. Нестеренко В.А. Эффективный алгоритм кластеризации с нефексированным числом кластеров // М-лы XI Международ. науч.-практич. конф. «Информационная безопасность». Ч.2. Таганрог: Изд-во ТТИ ЮФУ, 2010. C. 102-104.

11. Ниссенбаум О.В., Русаков С.В., Шешняева Е.С. Адаптивный алгоритм кластеризации данных с изменяющимися параметрами распределения // Новые информационные технологии в исследовании сложных структур: м-лы 9-й Российской конференции. Томск: Изд-во НТЛ, 2012. C. 107.