Fdr статистика и Множественные эксперименты

Fdr статистика и Множественные эксперименты Госуслуги

Обзор метрик обнаружения аномалий (плюс много дополнительной информации)

Время на прочтение

Привет, Хабр! На связи снова Юрий Кацер, эксперт по ML и анализу данных в промышленности, а также руководитель направления предиктивной аналитики в компании «Цифрум» Госкорпорации “Росатом”. До сих пор рамках рабочих обязанностей решаю задачи поиска аномалий, прогнозирования, определения остаточного ресурса и другие задачи машинного обучения в промышленности. В рамках рабочих задач мне приходится часто сталкиваться с проблемой правильной оценки качества решения задачи, и, в частности, выбора правильной data science метрики в задачах обнаружения аномалий.

Поскольку речь пойдет о метриках обнаружения аномалий, давайте сначала определимся, что такое аномалия и обнаружение аномалий. В широком смысле аномалия означает отклонение от ожидаемого поведения. Обнаружение аномалий, в свою очередь, представляет собой задачу (или методику) выявления необычных паттернов, не соответствующих ожидаемому поведению. Обнаружение аномалий необходимо в различных областях знаний и прикладных решениях, например, чтобы отслеживать проникновения в компьютерные сети, детектировать аварийные ситуации на электростанциях, выявлять мошенничества при операциях с кредитными картами в банках, определять климатические изменения, создавать системы контроля состояния здоровья и для многого другого. 

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

Временной ряд — это последовательность точек или векторов, проиндексированных в хронологическом порядке и представляющих характеристику процесса.

Пример данных типа "временной ряд"
Пример данных типа “временной ряд”

Оценить алгоритмы обнаружения аномалий совсем не просто, поскольку существует множество математических задач и различных метрик, подходящих для конкретных проблем и условий. Часто исследователи и data scientist’ы берут общепринятую метрику, такую как F1, только потому, что ее настоятельно рекомендуют для задач классификации в общем случае. Чтобы помочь избежать неправильного выбора метрик, я решил сделать обзор метрик, используемых для оценки качества решения задач обнаружения аномалий.

Про Госуслуги:  Что представляет собой идентификатор лмсз? Как его получить в егиссо

Дисклеймер: Информация в статье изложена упрощенно, а сама статья не претендует на всеобъемлющий анализ рассматриваемого вопроса.

Пример и объяснение разницы между функциями потерь, критериями, метриками

Для лучшего понимания мы на примере объясним, о какой конкретно части алгоритма обнаружения аномалий идет речь в статье. В качестве примера алгоритма возьмем следующий:

Упрощенная схема алгоритма обнаружения аномалий в общем случае
Упрощенная схема алгоритма обнаружения аномалий в общем случае

Шаг 1. Прогнозирование (модель процесса): возьмем обученную (на данных нормального режима) модель машинного обучения для прогнозирования некоего существующего сигнала на одну точку вперед в каждый момент времени. Когда модель не совпадает с реальным сигналом, можно говорить, что процесс отклоняется от нормального состояния.

Критерий обнаружения аномалии (абсолютная ошибка)
Критерий обнаружения аномалии (абсолютная ошибка)

Шаг 2. Критерий обнаружения аномалий: наш алгоритм обнаружения аномалий основан на критерии сравнения функции ошибки (абсолютной ошибки) с заранее рассчитанным (на этапе обучения) порогом. Абсолютная ошибка растет, когда данные отклоняются от нормальных значений, использованных на этапе обучения модели. Превышение порога указывает на обнаружение аномалии.

Критерий сравнения функции ошибки с заранее рассчитанным порогом
Критерий сравнения функции ошибки с заранее рассчитанным порогом

Шаг 3. Оценка алгоритмов обнаружения аномалий: именно этому шагу и необходимым для него метрикам посвящена эта статья.

Оценка алгоритмов обнаружения аномалии
Оценка алгоритмов обнаружения аномалии
  • в статье не рассматриваются функции потерь (cost functions, loss functions), оптимизируемые на этапе обучения алгоритмов машинного обучения в Шаге 1. Однако в качестве функции потерь (loss function) могут быть выбраны функции (критерий, метрика) из Шагов 2 или 3, чтобы максимально повысить качество работы модели;

  • в статье не рассматриваются критерии обнаружения аномалий из Шага 2, хотя они похожи на метрики машинного обучения;

  • статья посвящена Шагу 3  — оценке алгоритма обнаружения аномалий.

Матрица несоответствий

Матрица несоответствий
Матрица несоответствий

Как читать таблицу:

  • tp (истинно положительный): спрогнозировано аномальное значение, и это верно;

  • tn (истинно отрицательный): спрогнозировано нормальное значение, и это верно;

  • fp (ложноположительный): спрогнозировано аномальное значение, и это неверно;

  • fn (ложноотрицательный): спрогнозировано нормальное значение, и это неверно.

Задачи обнаружения аномалий

Для удобства дальнейшей систематизации метрик давайте определим задачи, которые чаще всего выделяют в проблеме обнаружения аномалий, но сначала скажем о различных типах аномалий. По количеству точек аномалии обычно делят на точечные (point) и коллективные (collective). Существуют также контекстуальные (contextual) аномалии, но коллективный и контекстуальный типы иногда объединяют в так называемый range-based тип. Но для простоты мы будем использовать термин коллективная аномалия для range-based, то есть для коллективных и контекстуальных вместе, а определение возьмем отсюда:

Коллективная аномалия — это аномалия, возникающая в виде последовательности временных точек, когда между началом и концом аномалии не существует неаномальных (нормальных) данных.

Различие между точечными и коллективными аномалиями
Различие между точечными и коллективными аномалиями

Подробнее о задаче обнаружения аномалий можно прочитать в другой моей статье.

Задача обнаружения аномалий часто трансформируется в задачу бинарной классификации (также часто называемую задачей обнаружения выбросов) и задачу обнаружения точки изменения состояния. Связь между задачами и типами аномалий показана на схеме.

Связь между задачами и типами аномалий
Связь между задачами и типами аномалий

Что это означает? При решении задачи детекции точечных аномалий мы будем использовать и оценивать алгоритмы бинарной классификации. Для коллективных аномалий мы можем использовать и оценивать как алгоритмы бинарной классификации, так и алгоритмы обнаружения точки изменения состояния (в зависимости от прочих условий или постановки бизнес-задачи). Другими словами, алгоритмы обнаружения точки изменения состояния применимы только для коллективных аномалий, потому что необходимо найти конкретную точку изменения состояния, где начинается коллективная аномалия. Однако можно интерпретировать коллективную аномалию как набор точечных аномалий, поэтому алгоритмы бинарной классификации применимы для обоих типов аномалий.

Наглядное объяснение связи между задачами и типами аномалий
Наглядное объяснение связи между задачами и типами аномалий

Классы метрик

Определив существующие задачи обнаружения аномалий, мы можем связать эти задачи с классами метрик, которые используются для оценки алгоритмов. О классах и метриках, относящихся к каждому классу, поговорим сразу после того, как посмотрим на рисунок ниже, где показана связь между задачами и классами метрик.

Связь между классами метрик и задачами
Связь между классами метрик и задачами

Итак, какие бывают классы метрик:

  • Метрики бинарной классификации: отнесение результата классификации объекта к одному из двух классов (нормальный, аномальный) с истинной (верной) меткой объекта.

Для задач обнаружения точки изменения состояния метрики бинарной классификации применяются на основе окна: проверяем, находится ли прогнозируемая точка изменения состояния в окне обнаружения, или сравниваем наложение прогнозируемого и истинного окон (положение, размер и т.д.).

Для задачи бинарной классификации метрики бинарной классификации применяются, учитывая каждую точку: проверяем правильность предсказанной метки для каждой точки.

  • Обнаружение на основе окна (вне бинарной классификации): сопоставление прогнозируемой точки изменения с окном вокруг фактической точки изменения способом, отличным от бинарной классификации.

  • Время (или номер точки) обнаружения: оценка разницы во времени (или номере точки / индексе) между прогнозируемой и фактической точками изменения состояния.

Классификация метрик обнаружения аномалий

В этом разделе покажем классификацию метрик и дадим краткую информацию о каждой из них.

Метрики обнаружения изменений
Метрики обнаружения изменений

Метрики обнаружения на основе окна (вне бинарной классификации)

Метрики оценки ошибки времени (или номера точки) обнаружения

Существует еще много подобных метрик, которые подходят для особых областей применения и процедур обнаружения точки изменения состояния (например, средняя задержка обнаружения в наихудшем случае, интегральная средняя задержка обнаружения, максимальная условная средняя задержка обнаружения, среднее время между ложными срабатываниями и другие). О них можно прочитать в монографии Sequential Analysis: Hypothesis Testing and Changepoint Detection. Эта книга посвящена таким метрикам, которые в том числе служат критериями для алгоритмов обнаружения точек изменения состояния. Кроме того, в ней также содержатся рекомендации по выбору критериев или метрик для определения точки изменения в различных случаях, например, для контроля качества:

Метрики бинарной классификации

  • FDR (fault detection rate; доля обнаруженных аномалий) = TPR (true positive rate; доля истинно положительных результатов) = Recall (Полнота) = Sensitivity (Чувствительность): отношение количества истинно положительных точек данных (точек изменения) к общему количеству истинно аномальных точек (или точек изменения) (TP+FN). Более подробная информация представлена в этой статье и в этой статье.

  • MAR (missed alarm rate; доля пропущенных срабатываний) = 1 — FDR: отношение количества ложноотрицательных точек данных (точек изменения) к общему количеству истинно аномальных точек (или точек изменения) (TP+FN).

  • Specificity (Специфичность): отношение количества истинно отрицательных точек данных (точек изменения) к общему количеству нормальных точек (TN+FP). Более подробная информация представлена в этой статье.

  • FAR (false alarm rate; доля ложных срабатываний) = FPR (false positive rate; доля ложноположительных результатов) = 1 — Специфичность: отношение количества ложноположительных точек данных (точек изменения) к общему количеству нормальных точек (TN+FP). Служит мерой того, как часто возникает ложное срабатывание.

  • G-mean (среднее геометрическое): комбинация Чувствительности и Специфичности. Более подробная информация представлена в этой статье.

  • Precision (Точность): отношение количества истинно положительных точек данных (точек изменения) к общему количеству точек, классифицированных как аномальные или точки изменения (TP+FP). Более подробная информация представлена в этой статье.

  • F-measure (F-мера): комбинация взвешенной Точности и Полноты (F1-мера представляет собой гармоническое среднее значение точности и полноты). Более подробная информация представлена в этой статье.

  • Accuracy (Точность): отношение количества правильно классифицированных точек данных (или точек изменения) к общему количеству точек данных (точек изменения). Более подробная информация представлена в этой статье.

  • ROC-AUC ROC-AUC (Receiver Operating Characteristic, area under the curve), PRC-AUC (PrecisionRecall curve, area under the curve): полезные инструменты для прогнозирования вероятности бинарного результата. Более подробная информация представлена в этой статье и в этой статье.

  • MCC (Matthews correlation coefficient; Коэффициент корреляции Мэтьюса): мера, используемая для определения качества бинарной классификации, которая учитывает все истинно положительные, истинно отрицательные, ложноположительные и ложноотрицательные результаты. Более подробная информация представлена в этой статье.

Различие метрик бинарной классификации для задач обнаружения аномалий

Для задач обнаружения точки изменения состояния:

  • tp: количество правильно обнаруженных точек изменения (# of tp).

  • fp: количество точек, неправильно определенных как точки изменения (# of fp).

  • tn: количество нормальных точек, правильно определенных как нормальные (# of tn).

  • fn: количество пропущенных точек изменения (# of fn).

Для задач обнаружения выбросов:

  • tp: количество точек данных, правильно определенных как аномальные (# of tp).

  • fp: количество нормальных точек данных, неправильно определенных как аномальные (# of fp).

  • tn: количество нормальных точек данных, правильно определенных как нормальные (# of tn).

  • fn: количество точек данных, неправильно определенных как нормальные (# of fn).

Основное различие между определением результатов tp, fp, tn, fn для обнаружения выбросов и обнаружения точек изменения состояния состоит в том, что в первом случае каждой точке присваивают аномальный или нормальный индекс, а во втором случае каждую точку изменения состояния (или каждую истинную и ложную аномалию) определяют как обнаруженную либо как пропущенную.

Больше о метриках бинарной классификации для обнаружения аномалий во временных рядах можно прочитать в этой статье.

Заключение

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

Практические реализации некоторых метрик вы можете найти в различных библиотеках, как в классических типа sklearn, так и в специализированных, например, в TSAD (метрики для поиска точек изменения) или в PyOD (метрики для точечных аномалий).

Библиография

  1. Ahmed, Mohiuddin, et al. “An investigation of performance analysis of anomaly detection techniques for big data in scada systems.” EAI Endorsed Trans. Ind. Networks Intell. Syst. 2.3 (2015): e5.

  2. Aminikhanghahi, Samaneh, and Diane J. Cook. “A survey of methods for time series change point detection.” Knowledge and information systems 51.2 (2017): 339–367.

  3. Truong, Charles, Laurent Oudre, and Nicolas Vayatis. “Selective review of offline change point detection methods.” Signal Processing 167 (2020): 107299.

  4. Artemov, Alexey, and Evgeny Burnaev. “Ensembles of detectors for online detection of transient changes.” Eighth International Conference on Machine Vision (ICMV 2015). Vol. 9875. International Society for Optics and Photonics, 2015.

  5. Tatbul, Nesime, et al. “Precision and recall for time series.” arXiv preprint arXiv:1803.03639 (2018).

Множественные эксперименты

Время на прочтение

В современном мире сложно представить развитие продукта без A/B-тестирования. Чтобы успешно запустить продукт или новую функциональность — надо грамотно спроектировать A/B, рассчитать и интерпретировать его результаты. Иногда нам требуется тестирование более чем для двух групп. В этой статье мы рассмотрим как раз такой случай — множественное тестирование:

  • поговорим о том, когда и зачем следует проводить множественные тесты;
  • рассмотрим основные методы расчёта результатов тестов и математические принципы, на которых основаны методы;
  • приведём примеры программной реализации методов; эти примеры вы сможете использовать в своих проектах.

Fdr статистика и Множественные эксперименты

Множественные эксперименты

Очевидно, что любое техническое усложнение эксперимента должно быть обосновано практической необходимостью. Это касается и множественных тестов. Если аудитория разбивается более чем на две подгруппы, вероятность получить ошибку первого рода при эксперименте нарастает экспоненциально:

$1 – (1 – \alpha)^n, $

где $n$ — число подгрупп, $\alpha$ — заданный уровень статистической значимости.
Таким образом, при добавлении всего одной дополнительной подгруппы в привычный парный тест ($n = 3$) при заданном стандартном уровне $\alpha = 0.05$ мы получаем вероятность ошибки первого рода $p = 0.14$, что значительно превышает наш заданный $\alpha = 0.05$.

Зачем же проводить множественные эксперименты, если они снижают точность результатов исследования? Причин может быть несколько:

  1. Требуется протестировать несколько изменений и их кумулятивное воздействие на продуктовые метрики. Пример — показ пользователю на странице сервиса двух новых элементов, которые по-разному расположены относительно друг друга.
  2. Изменения можно протестировать только в одном временно́м промежутке, поскольку они и взаимозависимы, и чувствительны к недельной сезонности. Пример — отключение рекламных каналов для расчёта эффекта межканальной каннибализации.
  3. Заказчик хочет как можно скорее и дешевле получить ответ, какой из вариантов следует выбрать, сэкономив при этом время разработки и внедрения эксперимента.

Если мы столкнулись с одной из таких задач и нам предстоит рассчитать статистическую значимость для теста — нужно учитывать необходимость поправки на множественное тестирование. О том, что же это такое и как это правильно сделать, и пойдёт речь ниже.

Множественные эксперименты

Основные понятия

Рассмотрим общий случай, когда мы имеем дело с $n$ гипотезами $H_{0i}$, $i = 1, …, n$ о попарном равенстве медианы или среднего $m$ подгрупп. В таком случае возможен и верный, и неверный результат исхода $H_{0i}$ $VS$ $H_{1i}$ для каждой из $i = 1, …, n$ гипотез. Представим результаты в виде confusion matrix эксперимента:

Таким образом, неверно отклонены $V$ из $R$ отклонённых основных гипотез.

Исходя из этих параметров, мы введём два важных понятия ошибок, которые контролируются при множественном тестировании: $FWER$ и $FDR$.

Групповая вероятность ошибки $FWER$ (Family-Wise Error Rate) представляет собой вероятность получить по крайней мере одну ошибку первого рода и определяется формулой:

Fdr статистика и Множественные эксперименты0).$” data-tex=”display”>

$FDR$ (False Discovery Rate) — это математическое ожидание отношения ошибок первого рода к общему количеству отклонений основной гипотезы:

Fdr статистика и Множественные эксперименты0).$” data-tex=”display”>

Рассмотрим методы контроля этих ошибок на примере стандартного продуктового кейса.

Описание кейса

В качестве простого примера рассмотрим эксперимент, в котором трём изолированным, непересекающимся группам пользователей показали три варианта страницы с предложением нажать на кнопку звонка по объявлению. В качестве основной метрики для простоты расчёта возьмём суммарное количество звонков в каждой группе.

Посмотрим на то, как же менялась исследуемая метрика:

Fdr статистика и Множественные эксперименты

Рис. 1. График динамики нажатий на кнопку звонка

Воспользуемся стандартным методом $bootstrap$, чтобы привести распределение целевой метрики в выборках к нормальному виду, и посмотрим на гистограммы и диаграммы размаха средних значений в выборках:

Fdr статистика и Множественные эксперименты

Рис. 2. Гистограмма распределения средних значений в группах

Fdr статистика и Множественные эксперименты

Рис. 3. Диаграмма размаха средних значений в группах

Судя по графикам, группа C выигрывает по количеству нажатий на кнопку звонка. Однако необходимо убедиться в статистической значимости результатов. Для этого приведём оцениваемую метрику к виду нормального распределения и воспользуемся привычным t-критерием Стьюдента для попарного сравнения групп в эксперименте, а затем — методами контроля $FWER$ и $FDR$ для учёта поправки на множественное сравнение.

Контроль FWER

Существует множество методов контроля данной ошибки, однако наиболее распространены два:

1) одношаговая процедура с одновременной корректировкой $p-value$ для всех тестируемых гипотез методом Бонферрони;

2) последовательная, итеративная корректировка $p-value$ c принятием решения на каждом шаге в соответствии с результатом методом Холма.

1. Поправка Бонферрони

Эта одношаговая процедура позволяет снизить вероятность ложноположительного результата эксперимента. Суть метода — принять альтернативную гипотезу, если:

$p ≥ \alpha / n, $

где $n$ — количество тестируемых гипотез.

Реализовать метод можно достаточно просто при помощи стандартной библиотеки $bootstrapped$:

from bootstrapped import bootstrap as bs
from bootstrapped import compare_functions as bs_cmp
from bootstrapped import stats_functions as bs_st


bs_ab_estims = bs.bootstrap_ab(np.array(group_A), np.array(group_B), 
                               bs_st.mean bs_cmp.difference, 
                               num_iterations=5000, alpha=0.05/3, 
                               iteration_batch_size=100, scale_test_by=1, 
                               num_threads=4)

bs_bc_estims = bs.bootstrap_ab(np.array(group_B), np.array(group_C), 
                               bs_st.mean bs_cmp.difference, 
                               num_iterations=5000, alpha=0.05/3, 
                               iteration_batch_size=100, scale_test_by=1, 
                               num_threads=4)

bs_ac_estims = bs.bootstrap_ab(np.array(group_A), np.array(group_C), 
                               bs_st.mean bs_cmp.difference, 
                               num_iterations=5000, alpha=0.05/3, 
                               iteration_batch_size=100, scale_test_by=1, 
                               num_threads=4) 

Получив результаты статистической оценки, можно сделать выводы, различаются группы или нет.

Основной минус подхода: чем больше подгрупп — тем меньше мощность критерия, что увеличивает вероятность принять неверную гипотезу. Например, для десяти тестов и $α_i = 0.05$ необходимо получить $p_i ≤ 5 · 10^-3$, чтобы сказать, что разница значимая. Чтобы нивелировать эти недостатки, можно выбрать метод Холма.

2. Метод Холма

Это нисходящая процедура последовательного изменения $p-value$. На первом шаге алгоритма метода реальные $p-value$ сортируются по возрастанию:

$p_1 ≤ ··· ≤ p_n,$

затем корректируется исходно заданный $\alpha$-уровень:

$ \alpha^{’}_i = \alpha / (n – i + 1), $

после чего проверяется условие $p_i ≥ \alpha^{’}_i$ и делается заключение, верна ли основная гипотеза $H_{0i}$.

Точка останова алгоритма — момент i, когда принята первая основная гипотеза $H_{0i}$, при этом принимаются и все последующие Fdr статистика и Множественные эксперименты i$” data-tex=”inline”>.
Реализовать данный метод можно при помощи процедуры $multipletests()$ из библиотеки $statsmodels$ с параметром $method=”holm”$:

from bootstrapped import bootstrap as bs
from bootstrapped import stats_functions as bs_st
from scipy.stats import ttest_ind
from statsmodels.sandbox.stats.multicomp import multipletests

bs_a = bs.bootstrap(np.array(group_A), stat_func=bs_st.mean, 
             num_iterations=10000, iteration_batch_size=300, 
             return_distribution=True)


bs_b = bs.bootstrap(np.array(group_B), stat_func=bs_st.mean, 
             num_iterations=10000, iteration_batch_size=300, 
             return_distribution=True)

bs_c = bs.bootstrap(np.array(group_C), stat_func=bs_st.mean, 
             num_iterations=10000, iteration_batch_size=300, 
             return_distribution=True)


stat_ab, p_ab = stats.ttest_ind(pd.DataFrame(bs_a), pd.DataFrame(bs_b))

stat_bc, p_bc = stats.ttest_ind(pd.DataFrame(bs_b), pd.DataFrame(bs_c))

stat_ac, p_ac = stats.ttest_ind(pd.DataFrame(bs_a), pd.DataFrame(bs_c))

print(sorted([p_ab, p_bc, p_ac]))

print("FWER: " + str(multipletests(sorted([p_ab, p_bc, p_ac]), alpha=0.05, 
                     method='holm', is_sorted = True))) 

Контроль FDR

Контроль $FDR$ означает, что выполняется условие <img src="https://habrastorage.org/getpro/habr/formulas/c0e/c1b/a7b/c0ec1ba7bf0ea209c42483ec9e05e4ee.svg" alt="$FDR = E(V/R) . При этом $FDR ≤ FWER$, т. е. вероятность получить ошибку первого рода при контроле $FDR$ снижается.

Метод Бенджамини — Хохберга

Эта восходящая процедура предполагает последовательное изменение $p-value$, предварительно отсортированных по возрастанию:

$p_1 ≤ ··· ≤ p_n.$

Затем исходный $α$-уровень корректируется по формуле:

$\alpha^{’}_i = i · \alpha / n, $

затем, как и в методе Холма, проверяется условие $p_i ≥ \alpha^{’}_i$ и делается заключение, верна ли основная гипотеза $H_{0i}$ и все последующие Fdr статистика и Множественные эксперименты i$” data-tex=”inline”>.

Метод Бенджамини — Хохберга, как и метод Холма, можно реализовать при помощи процедуры $multipletests()$:

print("FDR: " + str(multipletests([p_ab, p_bc, p_ac], alpha=0.05, 
                    method='fdr_bh', is_sorted = False))) 

Заключение

В статье мы рассказали об основных методах оценки результатов множественных тестов и привели примеры программного кода, реализующего эти методы. Мы надеемся, что вы с пользой и интересом провели время и сможете применить описанные процедуры на практике. А если у вас возникли вопросы — мы с радостью ответим на них.

Спасибо за внимание!

Оцените статью
ЕГИССО - Вход - egisso.ru
Добавить комментарий