Аннотация

Аннотация: В статье рассматривается оригинальный подход к кластеризации одномерных потоковых данных, опирающийся на принципы кластеризации на основании плотности распределения данных в пространстве признаков. Это позволяет работать в условиях информационного шума с целью отсечения выбросов и неинформативных аномальных данных. Для реализации данного подхода был разработан алгоритм, состоящий из нескольких функциональных блоков и предполагающий поиск одномерных границ кластеров, который эффективно использует информацию о появлении новых кластеров, сохраняя только значимые элементы данных, что положительно сказывается на требованиях к вычислительным ресурсам. Для дальнейшего повышения эффективности предложенного алгоритма применен подход адаптивного разбиения данных из входного потока на фреймы различного размера с последующей обработкой на основании эвристического подхода, учитывающего особенности одномерного пространства признаков и накопительный характер информации о наличии кластеров. Результирующий алгоритм демонстрирует высокую эффективность по скорости обработки данных и используемой памяти. Его вычислительная сложность стремится к линейной с течением времени, то есть к O(n). Также авторам удалось достичь высоких показателей качества кластеризации, оцениваемых по критериям компактности и разделимости кластеров, являющихся универсальными для любых алгоритмов кластеризации на основе плотности распределения данных в пространстве признаков. Перечисленные преимущества подтверждены при помощи эксперимента над 20 наборами тестовых данных, результаты которого также приведены в рамках данной работы. Представленный алгоритм является одним из немногих алгоритмов кластеризации потоковых данных способных работать в условиях информационного шума, и при этом, оптимизированных для работы с одномерными данными. По отдельности каждая из задач кластеризации потоковых данных и кластеризации одномерных данных рассматриваются научным сообществом довольно давно, однако, их совокупность остается без должного внимания, несмотря на очевидную пользу, например, для решения задач поиска устойчивых состояний или очистки от аномальных и шумовых значений при анализе одномерных сигналов, показаний датчиков и т.п.