Привет, Хабр! Сегодня речь пойдет о предсказании будущего, поведении людей, математике и котиках.
Зачем предсказывать поведение?
В повседневной жизни, общаясь с людьми, мы всегда смотрим на поведение собеседника. Поведение человека может много о нем сказать: о его воспитании, привычках, увлечениях, принципах и о личности в целом. Для нас, как для социальных существ, это очень важная информация, так как мы делаем выводы о человеке: можно ли ему доверять, на что обратить внимание, стоит ли с ним вообще иметь дело. Для нас, как для работников сферы информационной безопасности, это очень важная информация, так как мы можем делать выводы: можно ли ему доверять, на что обратить внимание, стоит ли с ним вообще иметь дело.
![? ?](https://habrastorage.org/getpro/habr/upload_files/786/056/00a/78605600a1cd79cc1552ed2b08ef2f2d.jpg)
Причем здесь информационная безопасность? Согласитесь, гораздо лучше знать о потенциальной угрозе и контролировать ее, чем постфактум узнать об утечке секретных данных. И как раз в моменте "знать о потенциальной угрозе" мы возвращаемся к тому, что мы можем делать выводы о поведении человека. Давайте введем формальное определение: поведением называется определенный сложившийся набор качеств во взаимодействии с окружающей средой.
А можем ли мы сопоставить набор качеств с набором поступков и действий, которые могли бы быть важны для ИБ? Конечно, ведь в повседневной жизни мы делаем вывод о человеке на основе того, что он делает и говорит. Таким образом, мы приходим к выводу: поведенческие качества персоны определяются поступками и действиями, и наоборот, поступки и действия персоны определяются её поведением.
Что такое поведение?
После того, как мы узаконили отношения "Поведение - Действия", встает вопрос: "А что с этим делать, и как нам это поможет поймать негодяя?". Ответ находится в состоянии суперпозиции: он и прост, и сложен одновременно. Но мы не ищем простых путей, поэтому вводим в игру математику и определяем поведение как случайный процесс. Как мы знаем, случайный процесс - это некоторая функция, значениями которой являются случайные величины. Держим в голове, что "поведение - это действия" и углубляемся в специфику решения задачи в условиях модуля UBA (User Behavior Analytics).
Наши случайные величины на самом деле - параметры, которые рассчитываются на основе действий и коммуникаций сотрудника на рабочей станции. Собирается и обрабатывается информация о переписке в корпоративной почте, а также в мессенджерах. Интересует нас в переписке сотрудника почти всё: направление переписки - входящая или исходящая, количество отправленных файлов, является ли собеседник внутренним пользователем или же это кто-то вне компании, и так далее. Вся эта информация (и даже больше) используется в расчете показателей поведения. Сколько человек отправляет файлов, сколько получает, его активность внутри компании, активность, направленная за пределы компании, суточная активность, его деловой диапазон. Каждый день эти показатели пересчитываются на основе окна предыдущих 7 дней.
Посмотрим на примере, как же выглядит поведение человека глазами бездушной машины и беспристрастной математики. Возьмем значения показателя внешней активности. Очень интересный показатель для офицера службы безопасности: а вдруг всплеск внешней активности связан с тем, что сотрудник пытается слить секретные данные компании конкурентам? Итак, мы берем значения показателя внешней активности за 80 дней и визуализируем, банально соединяя точки значений.
![](https://habrastorage.org/getpro/habr/upload_files/96f/a2b/424/96fa2b424f902ededd4a5e799fabafde.png)
Рисунок 1 - Исходная функция показателя внешней активности
Первые шаги Фурье
Как же мы собираемся предсказывать? В момент проработки постановки задачи возникла гипотеза: поведение сотрудника циклично. Значит, если мы докажем периодичность поведения, то сможем его предсказывать. Периодичность может быть за совершенно разные периоды времени: день, неделя, месяц. В решении задач выявления периодичности используются совершенно разные методики: скользящие средние, статистический анализ временных рядов (выявление тренда и сезонности) и т.д. Но одним из главных инструментов является гармонический анализ, в частности, анализ Фурье, который и будет применяться в дальнейшей разработке задачи.
Анализом Фурье называют разложение сложных периодических сигналов на элементарные гармонические составляющие, а также оценку или измерение их характеристик. Основывается анализ на преобразовании Фурье. Формальное определение: преобразование Фурье - это математическая операция, которая преобразует функцию от времени в частотные компоненты. В основе этого преобразования лежит простая идея: почти любую периодическую функцию можно представить суммой отдельных гармонических составляющих (ряда Фурье) - синусоид и косинусоид с различными амплитудами A, периодами Т и, следовательно, частотами ω. Гармонические составляющие, они же гармоники, - это некоторые функции вида
- частота k-ой гармоники.
![](https://habrastorage.org/getpro/habr/upload_files/abe/8bb/b80/abe8bbb80720f2a735c6e0b41d39ae53.png)
Рисунок 2 - комикс xkcd (с)
Продолжим с математикой: ряд Фурье записывается следующим образом:
Преобразование Фурье в обыкновенном своем виде содержит экспоненту, в степени которой мнимая единица
, (прим. - множитель (так называемый нормировочный множитель, который становится необходимым в момент перехода к дискретному спектру) перед интегралом может разниться от источника к источнику, что связано, во-первых, с разными подходами к нормировке, а во-вторых, с возможностью корректного выведения формулы обратного преобразования),
поэтому, чтобы избавиться от комплексных чисел, используют косинус-преобразование Фурье. Прямое:
и обратное:
Дискретное преобразование Фурье в общем виде имеет следующий вид. Прямое преобразование:
обратное преобразование:
После разложения сигнала (то есть нашей "функции поведения") каждому периоду будет соответствовать гармоника. Из формул выше Xn и будет соответствовать значению вклада гармоники. Эти гармонические составляющие будут иметь различный вклад в общий вес функции, поэтому, выделяя гармоники с максимальным весом вклада, мы выделяем периоды, которые наиболее явно проявляются в поведении. Это в общих словах и в теории. А вот на практике мы столкнулись с множеством нюансов, о которых мы дальше поговорим.
~~~Так как задача решается в R - среде вычислений с открытым исходным кодом, то существует множество библиотек для решения самого разного рода задач. А популярная тема гармонического анализа и вовсе породила с пару десятков пакетов, которые мы и испытывали в разных комбинациях в нашем коде предсказания поведения.~~~
Быстрое преобразование Фурье
На практике чистое преобразование Фурье мало кто использует, потому что это достаточно долгий процесс, требующий много вычислительной мощности, так как сложность простого преобразования Фурье составляет O(N^2), так называемая квадратичная сложность. Это значит, что количество операций будет зависеть от размера входной выборки n как n*n. Поэтому зачастую используют Быстрое Преобразование Фурье (БПФ), сложность которого O(NlogN), что куда лучше квадратичной. Предложенный в 1965 году Дж. В. Кули и Джоном Тьюки алгоритм достигает таких показателей за счет использования симметрии задачи. Вообще говоря, БПФ - это набор алгоритмов, позволяющих упростить вычисление ДПФ.
![](https://habrastorage.org/getpro/habr/upload_files/04a/56a/7dd/04a56a7dd41086147dc0f1db8e20ad44.jpg)
Рисунок 3 - мем с просторов
Спектр
Раньше уже упоминался момент расчета вклада гармоник в общий вес функции, и у этого есть свое название - спектр. Спектральный анализ - один из методов обработки сигналов, который позволяет выявить частотный состав сигнала. Напомним, что каждая гармоника соответствует некоему периоду. Соответственно, выдвигая гипотезу о существовании закономерностей поведения, мы бы хотели увидеть на этих спектрах превалирующие составляющие, которые наиболее полно описывают весь сигнал. Что это значит?
Возвращаемся к идее, что периодический сигнал может быть разложен на простые составляющие, где каждая гармоника отвечает за свою частоту. И каждая гармоника имеет свой вклад, то есть описывает определенный процент сигнала. Мораль такова: если несколько гармоник достаточно полно описывают сигнал, то справедлив вывод, что мы можем с некоторой вероятностью судить о закономерности поведения. Человеческим языком - человек ведет себя закономерно, наша гипотеза верна, и мы всё можем спрогнозировать!
Но вернемся к теории: вообще говоря, спектр периодического сигнала - дискретный и для наших данных за 85 дней будет иметь следующий вид.
![Исследования > Прогнозирование поведения пользователя > спектр.png Исследования > Прогнозирование поведения пользователя > спектр.png](https://habrastorage.org/getpro/habr/upload_files/300/0cd/060/3000cd0604275fb1f775cd297133b662.png)
Рисунок 4 - спектр исходного сигнала
На рисунке зачеркнута половина гармоник. Это очень важно обозначить в явном виде, потому что согласно теореме Котельникова, максимальная частота гармоники должна быть такой, чтобы на нее приходилось как минимум два отсчета, поэтому число гармоник равно половине числа отсчетов дискретного сигнала. Для выборки размера N отсчетов количество гармоник равно N/2. Уже тут мы видим выделяющиеся гармоники, но для хоть сколько-то точного анализа и последующего прогнозирования это, конечно, не годится. Стоит отметить, что первая гармоника на графике - не должна учитываться в последующих исследованиях, поскольку это период самого сигнала, то есть отражает цикл всего сигнала в 85 дней, а это особой информации не несет. Поэтому правильный спектр будет выглядеть следующим образом:
![](https://habrastorage.org/getpro/habr/upload_files/1d2/5e7/44c/1d25e744c663f511c40c825edc01cbd4.png)
Рисунок 5 - правильный спектр исходного сигнала
Чтобы перейти от частоты к периоду, следует воспользоваться формулой, известной со школьных времен:
Так получается, например, что графически первая гармоника (фактически - вторая) соответствует 1/2 всего сигнала: 40 дням.
Оконное преобразование Фурье
Но даже если построить простой спектр за меньшее количество времени, например за месяц, это все равно не будет нести в себе сакральное знание периодичности. Поэтому работаем дальше. Ведь искать месячную периодичность в сигнале "длительностью" месяц - бессмысленно. Но есть выход - оконное преобразование Фурье. Суть оконного преобразования Фурье заключается в разбиении исходного сигнала на короткие временные промежутки, к которым к каждому по отдельности применяется преобразование Фурье. Формально это выглядит так:
Существуют разные виды оконных функций: прямоугольное, треугольное, преобразование Гаусса, Хеннинга, Хэмминга, Чебышёва и еще много-много разных оконных функций, носящих имена известных (и не очень) ученых. Отличаются они способами реализации улучшения частотного спектра на границе разрыва.
![](https://habrastorage.org/getpro/habr/upload_files/600/cc6/f69/600cc6f69cfe643426a4d58750b8da14.png)
Рисунок 6 - пример некоторых оконных функций
В нашем случае мы используем самое обычное прямоугольное окно, так как вопрос контролирования боковых лепестков (частей сигнала на границах разрыва) актуален скорее для обработки аудио для исключения дефектов сигнала. В нашей задаче разрыв не влияет на данные. На практике это реализовывается применением преобразования Фурье к окну в n дней с шагом в i дней. Мы брали n = 30 и i = 15 (в дальнейшем i = 7). Такие числа берутся из бизнес-контекста. В рабочем процессе есть основные периоды - месяц, две недели и неделя. В бизнес-контексте есть предположение, что будут доминировать именно гармоники, соответствующие таким периодам, поскольку они соответствуют периодам рабочих процессов. Например, обычная неделя → спринты → бухгалтерия за месяц. Ожидалось, что такая периодичность проявится и на тестовых данных (которые, напомним, представляют собой показатель внешней активности персоны).
В итоге мы получаем 8 спектров, в каждом из которых свои доминирующие гармоники. Но радоваться всё еще рано. А вообще корректна ли такая игра со спектрами и частотами? Давайте это докажем. Формально нам нужно доказать следующее: вклад максимальных гармоник определяет норму (объем) исходной функции (показателя поведения). Под - катом математическое доказательство этого факта.
Доказательство
У нас есть функция на дискретном множестве. Мы ее продолжаем на всю числовую прямую, ступеньками или отрезками соединяя значения в точках. Получаем интегрируемую с квадратом на всей прямой хорошую функцию f.
Такие функции образуют гильбертово пространство функций, интегрируемых с квадратом функций. На этом пространстве можно корректно задать линейный оператор - преобразование Фурье. В нашем случае функция начинается в нуле. Чтобы избавиться от комплексно-значности ее преобразования Фурье, мы допустим, что она принимает значения и при отрицательных значениях аргумента. Сделаем ее четной. В этом случае, мнимая часть преобразования Фурье равна нулю и остается только косинус преобразование.
Мы знаем, что по теореме Планшереля преобразование Фурье сохраняет норму функции. Сопряженное пространство образов преобразования Фурье (проще говоря, спектров) тоже представляет из себя пространство интегрируемых с квадратом функций, поскольку преобразование Фурье является унитарным оператором.
Представим спектр в виде двух слагаемых (три макс. гармоники + остальные).
Их скалярное произведение равно 0, т.е. они ортогональны.
Также для L_2 справедливо равенство Парсеваля (аналог теоремы Пифагора для функций), т.о.:
прямо определяет вклад в исходную функцию. ЧТД.
Применение теории на практике
Разобравшись с математикой, давайте посмотрим, как на самом деле эти гармоники описывают сигнал:
1) Выбираем в каждом окне по 3 гармоники с максимальным вкладом.
Для нашего примера они будут такие:
|
---|
2) Считаем процентный вклад трех максимальных гармоник от 100%.
3) Строим график динамики изменения процента вклада "по ходу скольжения" окна.
![](https://habrastorage.org/getpro/habr/upload_files/4eb/a57/34f/4eba5734f00a9e4c694e3040abfdff7e.png)
Рисунок 7 - график динамики изменения процентного вклада 3 максимальных гармоник в сигнал
Мы видим, что в среднем процент вклада держится больше 50%. Наиболее выделяется окно с 64% под номером 6. Попробуем восстановить разложенный сигнал в данном окне по 1-ой, 3-ей и 4-ой гармонике.
![](https://habrastorage.org/getpro/habr/upload_files/1cd/4d3/9cd/1cd4d39cd030b805b218117907ba8268.png)
Рисунок 8 - построение графика поведения по максимальным гармоникам окна сигнала
Итак, на Рис. 8 мы видим сигнал, построенный по трем максимальным гармоникам, в наложении на реальный сигнал. Где-то они совпадают достаточно точно, и пик активности "трех-максимально-гармонического" сигнала совпадает с фактическими данными, где-то он пророчит пики, которых де-факто не случилось. Всё же наша функция описывает сигнал лишь на 64%.
И наконец... Прогнозирование!
На основе полученной информации попробуем спрогнозировать поведение персоны. Прогнозировать можно было бы разными способами: брать 3 самые популярные гармоники по всем окнам сигнала, брать максимальные гармоники за период, вводимый вручную в зависимости от решаемой задачи (взгляд в будущее использование фичи), прогнозировать на две недели/месяц вперед... и так далее, очень много комбинаций временных промежутков, на которых брать гармоники и на которые прогнозировать. В итоге, мы остановились на гипотезе, которая заключается в следующем алгоритме:
выбираем окно с максимальным процентным вкладом 3 максимальных гармоник,
определяем по процентному вкладу, на какой период мы будем прогнозировать:
где K - количество дней, на которые будет строиться прогноз; V - наибольший процентный вклад трех максимальных по спектру гармоник; W - размер окна;
строим функцию прогноза по 3 максимальным гармоникам выбранного окна.
В нашем случае входные данные таковы:
"рабочее" окно - номер 6 (35-65 дни);
максимальные гармоники - 1, 3 и 4 (2 недели, 10 дней, 6 дней);
процентный вклад - 64%;
период предсказания - 20 дней.
![](https://habrastorage.org/getpro/habr/upload_files/e87/f9e/4f5/e87f9e4f5773cc8761a14c5ff36b2d4b.png)
Рисунок 9 - фактические значения, аппроксимация и прогнозная модель
Для того чтобы оценить степень достоверности прогноза, посчитаем точность прогнозной модели. Точность рассчитываем по формуле
В нашем примере точность составила 80%. Таким образом поведение, предсказанное моделью на 20 дней вперед, совпадает с реальными значениями на 80%.
Выводы
Мы разработали методику предсказания будущего поведения персоны с использованием методик спектрального анализа, в частности, с использованием преобразования Фурье. Конечно, есть куда расти, где усовершенствовать и что уточнить.
Авторы
Исследовательская группа центра продуктов Dozor «РТК-Солар»:
Рябова Татьяна, аналитик,
Максим Бузинов, руководитель
Литературные источники
1) Зельдович, Я. Б. Элементы прикладной математики : учебное пособие / Я. Б. Зельдович, А. Д. Мышкис. — 5-е изд. — Москва : ФИЗМАТЛИТ, 2008. — 592 с. — ISBN 978-5-9221-0775-4,
2) Кандидов В.П., Чесноков С.С., Шленов С.А.. Дискретное преобразование Фурье : учебно-методическое пособие. — Москва : МГУ имени М.В. Ломоносова, 2019. — 89 с. — ISBN 978-5-8279-0179-2,
3) Марпл С.Л. (мл).Цифровой спектральный анализ и его приложения: Пер. с англ. — Москва : Мир, 1990. — 584 с., — ISBN 5-03-001191-9.,
4) Отнес, Р.К. Прикладной анализ временных рядов : Основные методы / Р. Отнес, Л. Эноксон; Пер. с англ. В. И. Хохлова. - Москва : Мир, 1982. - 428 с. : ил.; 22 см.; ISBN B Пep. : 2 р.