MIDAS — новое направление поиска аномалий

Таким горячим темам машинного обучения, как автономные транспортные средства, генеративно-состязательная сеть (GAN) и распознавание лиц уделяется значительное внимание средств массовой информации. Однако, есть ещё одна, не менее важная проблема, над которой работают ученые, — поиск аномалий. От обнаружения сетевых ошибок до финансового мошенничества поиск аномалий помогает защитить предприятия, частных лиц и интернет-сообщества. Улучшая алгоритмы поиска аномалий, исследователи разработали новый подход под названием MIDAS.

Что есть MIDAS?

В Национальном университете Сингапура кандидат PhD Сиддхарт Бхатия и его команда разработали MIDAS, новый подход к поиску аномалий, который превосходит известные подходы как по скорости, так и по точности.

Сиддхартх Бхаба (Siddharth-Bhatia) из Национального университета Сингапура
Сиддхартх Бхаба (Siddharth-Bhatia) из Национального университета Сингапура

MIDAS расшифровывается как Microcluster-Based Detector of Anomalies in Edge Streams (Микрокластерный детектор аномалий в пограничных потоках). Как следует из названия, MIDAS обнаруживает аномалии микрокластеров или внезапные группы подозрительно похожих ребер на графиках. Одним из основных преимуществ MIDAS является его способность находить эти аномалии в режиме реального времени со скоростью, во много раз превышающей скорость современных существующих моделей.

Реальные случаи использования аномалий в графиках

Проще говоря, обнаружение аномалий — это практика поиска закономерностей или выбросов, которые отличаются от того, что вы ожидаете увидеть в наборе данных. Это может помочь нам найти и устранить вредоносный контент. «Обнаружение аномалий на графиках является критической проблемой для обнаружения подозрительного поведения в бесчисленных системах», — говорит Сиддхарт. «Некоторые из этих систем включают обнаружение вторжений, поддельные рейтинги и финансовое мошенничество».

Эта технология может помочь социальным сетям, таким как Twitter и Facebook, обнаруживать поддельные профили, используемые для спама и фишинга. Он даже может быть использован, чтобы помочь следователям выявить сексуальных хищников в интернете. «Используя MIDAS, мы можем найти аномальные ребра и узлы в динамическом (эволюционирующем во времени) графике”,-говорит Сиддхарт. “В Twitter и Facebook сети твитов и сообщений можно рассматривать как эволюционирующий во времени график, и мы можем найти вредоносные сообщения и поддельные профили, найдя аномальные края и узлы в этих графиках.”

Некоторые другие общие случаи обнаружения аномалий включают в себя:

  • Спам-фильтры
  • Обнаружение мошенничества с кредитными картами
  • Предварительная обработка набора данных
  • Сетевая безопасность
  • Модерация контента в социальных сетях

MIDAS превосходит ихвестные современные подходы

«Обнаружение аномалий является хорошо изученной проблемой, и большинство предлагаемых подходов сосредоточены на статических графах», — говорит Сиддхарт. «Однако, большинство графов реального мира динамические по своей природе, и методы, основанные на статических связях, могут пропускать временные аномалии характеристик графиков».

MIDAS, прежде всего, предназначен для поиска аномалий в режиме реального времени, что позволяет немедленно начать противодействие и уменьшить последствия вредоносных действий, например, заблокировать мошеннические покупки по кредитным картам.

“Кроме того, поскольку число вершин по мере обработки потока ребер, может увеличиваться нам нужен алгоритм, который использует постоянную память в размере графа”, — объясняет Сиддхарт. «Кроме того, мошеннические или аномальные события во многих приложениях происходят в микрокластерах или внезапно прибывающих группах подозрительно похожих границ, например, атаки отказа в обслуживании в данных сетевого трафика и поведение блокировки.”

“Используя принципиальную систему проверки гипотез», — говорит Сиддхарт, «Мидас дает теоретические границы ложноположительной вероятности, чего не дают уже известные методы.”

Как был протестирован Midas?

Сиддхарт и его коллеги продемонстрировали потенциал MIDAS в задачах безопасности в социальных сетях и поисках следов взлома. Для поиска аномалий использовались следующие наборы данных:

  • Поиски вторжения в Darpa (4.5 миллионов коммуникаций IP-IP)
  • Набор данных безопасности Twitter (2,6 миллиона твитов, связанных с событиями безопасности в 2014 году)
  • Твиты во время проведения Чемпионат Мира В Twitter (1.7 миллионов твитов во время Чемпионата мира по футболу 2014 года)

Чтобы сравнить производительность MIDAS, команда использовала следующие базовые показатели:

Поскольку AUC measure имеет значение 0,17, довольно низкое, на наборе данных Darpa, для измерения точности времени исполнения и реальную эффективность методом каманда использовала методику SEDANSPOT.

Результаты

MIDAS обнаруживает микро-кластерные аномалии на 48% точнее и в 644 раза быстрее, чем основные современные методы.

“Наши экспериментальные результаты показывают, что MIDAS превосходит по точности основные подходы подходы на 42-48% (в пересчете на AUC)”, — говорит Сиддхарт. «Кроме того, MIDAS обрабатывает данные в 162-644 раза быстрее, чем исходные подходы.”

Перспективы улучшения MIDAS

“Мы применили MIDAS для потока, а именно для быстрого поиска многоаспектных групповых аномалий в потоке», — говорит Сиддхарт. “В мульти-потоке мы находим аномалии на многоаспектных данных, имеющих как категориальные, так и числовые атрибуты.”

Сиддхарт и его команда говорят, что M-Stream, с точки зрения точности и скорости, превосходит несколько популярных обще признанных алгоритмов, например, Sklearn, Isolation Forest и Local Outlier Factor. Однако их работа с M-Stream в настоящее время находится только в стадии исследования.

«Учитывая производительность MIDAS, мы думаем, что это станет новым основным подходом и будет весьма полезно для поиска аномалий», — говорит Сиддхарт. «Кроме того, будет интересно изучить, какой вклад может внести MIDAS в другие приложения.”


Если вы заинтересовались и хотите детально познакомиться с MIDAS, прочитайте оригинальную статью Сиддхартха. Кроме того, можно загрузить код и наборы данных для своих экспериментов с Github.

По мотивам: Introducing MIDAS: A New Baseline for Anomaly Detection in Graphs

CC BY-NC 4.0 MIDAS — новое направление поиска аномалий, опубликовано К ВВ, лицензия — Creative Commons Attribution-NonCommercial 4.0 International.


Респект и уважуха

Добавить комментарий