Clustering algorithm for data streams with changing distribution parameters

Abstract

The article contains a clustering algorithm for time-weighted data streams based on the dynamic EM-algorithm. This algorithm can be used for clustering data with the normal distribution in, the parameters of the distribution undergoing changes over time, which is the case in real dymaniv systems such as computer systems or communication nets. The author offers the results of the computational experiment (based on the imitation model with the normal density of cluster distribution), which prove better quality of the proposed algorithm as to the percent of the erroneously recognized points and precision in cluster parameters description in contrast with the algorithm which does not use the time-weighed factors.

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