O-LDS: оптимизация пространства поиска для ускорения алгоритма оценки локальной плотности (Local Density Score)

Обнаружение аномалий - это одна из самых важных задач технологии интеллектуального анализа данных (DataMining) и обнаружения знаний в базах данных. Эта задача решается во многих важных прикладных областях, таких как обнаружение атак (Intrusion Detection), обнаружения мошенничества (Fraud Detection), в том числе с кредитными картами, обнаружения аномалий в медицине (Medical Anomaly Detection), обнаружение злоупотреблений и др. В настоящее время проводится много исследований по решению этой задачи, но большинство полученных решений имеет высокую вычислительную сложность, что затрудняет использование таких решений в задачах с большим количеством данных [1]. В данной работе предложен новый алгоритм O-LDS, который имеет значительно меньшую вычислительную сложность по сравнению с известными - алгоритмом оценки локальной плотности (Local density score, LDS) [2] и алгоритмом фактора локального отклонения (Local Outlier Factor, LOF) [3]. Для оценки производительности алгоритма O-LDS использовался набор данных CHAMELEON [4], [5], содержащий данные сложной формы в двухмерном пространстве. Алгоритм O-LDS применяется для обнаружения аномалий в задаче обнаружения атак на информационные ресурсы с использованием реальных наборов данных ADFA [6]. Практические исследования показывают, что предложенный алгоритм не только реализует точное обнаружение аномалий, но и работает быстрее до 20 раз и более, чем алгоритмы LDS, LOF.