Всё началось с использования ML в BigQuery — оказалось это совсем не больно, и очень эффективно.
Мы в GFN.RU используем модель K-Means для поиска аномалий в работе сервиса. Ведь невозможно кожаному мешку смотреть десятки графиков по тысячам игр ежедневно. Пусть электрический болван подсказывает куда нужно глянуть.
В поиске аномалий с таким подходом есть проблема: если метрика является метрикой второго и более высокого порядка, то K-Means может сообщить об аномалии, хотя, аномалии как таковой нет, а есть шум. Пример метрики второго порядка — среднее время пользователя на сайте. Очевидно, она зависит от количества пользователей. Таким образом, перед тем, как скармливать метрики в K-Means, их нужно отфильтровать от шумов.
Если по простому - определить на базе какой минимальной выборки нужно считать AVG чтоб ему верить.
Это можно сделать различными способами, но я, сторонник использования минимума инструментов — раз уж BQ, то BQ, и нужно, чтоб инструмент был по максимуму универсален - поменяли выборку метрики, а всё остальное осталось таким же. BQ полностью подходит для этой задачи.
Итак, 0-гипотеза — метрика изменяется в допустимых пределах (за базу возьмем 5%).
Необходимо найти количество замеров, при которых изменение метрики будет находиться в нужных пределах. При этом, сделать это в виде нескольких тестов, чтоб более точно проверить гипотезу.
Начнем с выборки данных :
with data as (select somemetric as metric
from dataset.data
order by RAND())
select * from data;Здесь всё просто и понятно - взяли данные, перемешали их.
Теперь нам необходимо эти данные разбить на тесты (группы). Я для этого использую метод остатка от деления. Берем какое-либо значение, делим на необходимое количество групп. Остаток от деления будет номером группы. В данном случае в качестве исходного значения брем номер строки в отсортированном списке и делим на 1000 групп.
with data as (select somemetric as metric
from dataset.data
order by RAND())
select *, mod(rn, 1000) as num
from (select metric, row_number() over () as rn
from (select metric from data where metric is not null)
)На выходе получили :
Значение метрики.
Номер строки (он нам дальше понадобится).
Номер группы (от 1 до 1000) или номер теста.
Теперь нам нужно найти в каждой группе значение среднего для разного количества элементов. Первое, что приходит в голову - конечно - сделать несколько циклов и посчитать. Но, в SQL циклы не приветствуются. Выражение должно векторизоваться, и тут нам на помощь приходит скользящее среднее.
Мы внутри каждой группы считаем скользящее среднее по значениям от начала группы и до её конца. В итоге, скользящее среднее для 10-й строки - это будет среднее внутри группы из 10 элементов, для 20-й строки - для 20 элементов и так далее.
with data as (select somemetric as metric from dataset.data
order by rand())
select *,
avg(metric)
over (partition by num order by rn ROWS BETWEEN UNBOUNDED PRECEDING and CURRENT ROW ) as rolling_avg,
ROW_NUMBER() over (partition by num order by rn) as in_row
from (
select *, mod(rn, 1000) as num
from (select metric, row_number() over () as rn
from (select metric from data where metric is not null)
))Следующим этапом мы считаем расхождение скользящего среднего между текущей и предыдущей строчкой. Процент расхождения и есть процент шума.
with data as (select somemetric as metric from dataset.data
order by rand())
select *,
ABS(1 -
SAFE_DIVIDE(rolling_avg,
lag(rolling_avg) over (partition by num order by in_row asc))) as avg_div
from (
select *,
avg(metric)
over (partition by num order by rn ROWS BETWEEN UNBOUNDED PRECEDING and CURRENT ROW ) as rolling_avg,
ROW_NUMBER() over (partition by num order by rn) as in_row
from (
select *, mod(rn, 1000) as num
from (select metric, row_number() over () as rn
from data
))
)Итак, в avg_div у нас есть процент расхождения среднего между двумя соседними показателями.
Осталось его округлить, обрезать и найти в какой обычно строке из 1000 тестов у нас появляется допустимое расхождение.
with data as (select somemetric as metric from dataset.data
order by rand())
select distinct round_div, round(avg(in_row) over ( partition by round_div)) as average_row
from (
select cast(round(avg_div * 100) as int64) as round_div, *
from (select *
from (
select *,
ABS(1 -
SAFE_DIVIDE(rolling_avg,
lag(rolling_avg) over (partition by num order by in_row asc))) as avg_div
from (
select *,
avg(metric)
over (partition by num order by rn ROWS BETWEEN UNBOUNDED PRECEDING and CURRENT ROW ) as rolling_avg,
ROW_NUMBER() over (partition by num order by rn) as in_row
from (
select *, mod(rn, 1000) as num
from (select metric, row_number() over () as rn
from data
))
))
where avg_div is not null
order by avg_div desc))
where round_div<5 order by round_div desc limit 1 Собственно и всё : округлили процент расхождений, нашли среднюю строчку в которой достигается нужное расхождение.
Все метрики второго порядка, которые основаны на данных с меньшим количеством - просто отбрасываем - т.к. они с высокой долей вероятности будут обусловлены шумом.
Само собой метрики первого порядка нужно анализировать отдельно - совсем не значит, что если у нас по какой-то группе замер из 2 единиц, то это не аномалия - точнее среднее - конечно же шум и не аномалия, но то, что сегодня 2 единицы данных - вполне может быть аномалией, если обычно ежедневно по 200 единиц.
На закуску: готовая к использованию сторка: https://github.com/GFNRussia/bqmlalerts/blob/main/stat_sig.sql
