Аннотация

Аннотация: В данной статье предлагается новый подход к решению задачи кластеризации с отсечением выбросов, неинформативных аномальных данных и прочего информационного шума для потоковых данных в пространстве признаков любой размерности и с памятью всех обработанных точек данных. Для реализации поставленной задачи была разработана оригинальная модификация алгоритма DBSCAN, использующая гибридный подход к поиску границ кластеров произвольной формы и определению, находится ли каждая из точек данных внутри или снаружи такой границы. При разработке были применены как технологии машинного обучения, так и математические методы, в частности метод вычисления выпуклой оболочки конечного набора точек в n-мерном пространстве Quickhull. Результирующий алгоритм состоит из нескольких блоков, активирующихся в зависимости от природы распределения данных полученных из входного потока. Применение разработанного алгоритма гарантирует создание замкнутой границы кластера произвольной формы. Использование механизма адаптивного разбиения на фреймы, позволяет проводить кластеризацию данных разной размерности и больших объемов, с памятью всех входящих точек. В результате авторам удалось создать модификацию алгоритма DBSCAN для потоковых данных эффективного по скорости выполнения и используемой памяти. Для иллюстрации прироста эффективности разработанной модификации алгоритма по сравнению с классическим вариантом DBSCAN проведена расчетная оценка производительности и требований к памяти. Правильность полученных оценок подтверждена экспериментально. Представленная модификация алгоритма DBSCAN для потоковых данных не только, позволяет получить общий прирост производительности при более низких требованиях к памяти по сравнению с классическим алгоритмом DBSCAN, но и имеет функциональные преимущества, связанные с возможностью эффективной работы с потоковыми данными при наличии информационного шума. Указанные преимущества делают представленную модификацию алгоритма DBSCAN полезной для решения сложных задач в системах обработки потоковых данных как, например, поиск корреляций и аномалий в статистических показателях распределенных систем сбора данных или для обнаружения устойчивых состояний моделей массового обслуживания, применяемых в логистике и на транспорте.