LOF объясняется шаг за шагом с помощью небольших наборов данных
Делиться
Вчера мы работали с методом обнаружения аномалий Isolation Forest.
Сегодня мы рассмотрим другой алгоритм, преследующий ту же цель. Но, в отличие от Isolation Forest, он не строит деревья.
Это называется LOF или коэффициент локального выброса.
Люди часто суммируют LOF одним предложением: находится ли эта точка в регионе с более низкой плотностью, чем ее соседи?
Это предложение на самом деле сложно понять . Я долго над ним бился.
Однако есть одна часть, которую легко понять сразу,
и мы увидим, что это становится ключевым моментом:
есть понятие соседей.
И как только мы говорим о соседях,
мы, естественно, возвращаемся к моделям, основанным на расстоянии .
Мы объясним этот алгоритм в 3 шага.
Для простоты мы снова будем использовать этот набор данных:
1, 2, 3, 9
Помните, у меня есть авторские права на этот набор данных? Мы провели с ним Isolation Forest и снова проведём LOF. И мы также можем сравнить два результата.
Шаг 1 – k соседей и k-расстояние
LOF начинается с чего-то чрезвычайно простого:
Посмотрите на расстояния между точками.
Затем найдите k ближайших соседей каждой точки.
Давайте возьмем k = 2 , чтобы свести все к минимуму.
Ближайшие соседи для каждой точки
- Точка 1 → соседи: 2 и 3
- Точка 2 → соседи: 1 и 3
- Точка 3 → соседи: 2 и 1
- Точка 9 → соседи: 3 и 2
Уже сейчас мы видим вырисовывающуюся четкую структуру:
- 1, 2 и 3 образуют плотный кластер
- 9 жизней в одиночестве, вдали от других
Расстояние k: локальный радиус
Расстояние k — это просто наибольшее расстояние среди k ближайших соседей.
И это на самом деле ключевой момент .
Потому что это единственное число говорит вам нечто очень конкретное:
локальный радиус вокруг точки.
Если k-расстояние мало, точка находится в плотной области.
Если k-расстояние велико, точка находится в разреженной области.
С помощью только этого одного измерения вы уже получите первый сигнал «изоляции».
Здесь мы используем идею «k ближайших соседей», что, конечно, напоминает нам о k-NN (классификаторе или регрессоре).
Контекст здесь другой, но расчет тот же самый.
И если вы думаете о k-средних , не смешивайте их:
«k» в аббревиатуре k-means не имеет ничего общего с «k» в данном случае.
Расчет k-расстояния
Для точки 1 два ближайших соседа — это 2 и 3 (расстояния 1 и 2), поэтому k-расстояние(1) = 2 .
Для точки 2 соседями являются 1 и 3 (оба на расстоянии 1), поэтому k-расстояние(2) = 1 .
Для точки 3 два ближайших соседа — это 1 и 2 (расстояния 2 и 1), поэтому k-расстояние(3) = 2 .
Для точки 9 соседями являются точки 3 и 2 (т.е. 6 и 7), поэтому k-расстояние(9) = 7. Это очень много по сравнению со всеми остальными.
В Excel мы можем создать матрицу парных расстояний, чтобы получить k-расстояние для каждой точки.
Шаг 2 – Расстояния достижимости
На этом этапе я просто определю вычисления здесь и применю формулы в Excel. Потому что, честно говоря, мне так и не удалось найти по-настоящему интуитивно понятный способ объяснения результатов.
Итак, что такое «расстояние достижимости»?
Для точки p и ее соседа o мы определяем это расстояние достижимости как:
досягаемость-расстояние(p, o) = макс(k-расстояние(o), расстояние(p, o))
Зачем брать максимум?
Целью расстояния достижимости является стабилизация сравнения плотности .
Если сосед o живет в очень плотной области (малое k-расстояние), то мы не хотим допускать нереально малого расстояния.
В частности, по пункту 2:
- Расстояние до 1 = 1, но k-расстояние(1) = 2 → расстояние-расстояние(2, 1) = 2
- Расстояние до 3 = 1, но k-расстояние(3) = 2 → расстояние-расстояние(2, 3) = 2
Оба соседа увеличивают расстояние достижимости.
В Excel мы сохраним матричный формат для отображения расстояний достижимости: одна точка в сравнении со всеми остальными.
Среднее расстояние достижимости
Для каждой точки мы теперь можем вычислить среднее значение, которое говорит нам: какое расстояние в среднем мне нужно проехать, чтобы добраться до моего местного района?
А теперь заметьте: точка 2 имеет большее среднее расстояние достижимости, чем точки 1 и 3.
Для меня это не так уж и интуитивно понятно!
Шаг 3 – LRD и оценка LOF
Последний шаг — это своего рода «нормализация» для нахождения показателя аномалии.
Сначала мы определяем LRD (плотность локальной достижимости), которая является просто обратной величиной среднего расстояния достижимости.
Окончательный балл LOF рассчитывается следующим образом:
Итак, LOF сравнивает плотность точки с плотностью ее соседей.
Интерпретация:
- Если LRD(p) ≈ LRD (соседей), то LOF ≈ 1
- Если LRD(p) намного меньше , то LOF >> 1. Таким образом, p находится в разреженной области.
- Если LRD(p) намного больше → LOF < 1. Таким образом, p находится в очень плотном кармане.
Я также сделал версию с большим количеством развитий и более короткими формулами.
Понимание того, что означает «аномалия» в неконтролируемых моделях
В неконтролируемом обучении нет основополагающих принципов. И именно здесь всё может стать запутанным.
У нас нет этикеток.
У нас нет «правильного ответа».
У нас есть только структура данных.
Возьмем этот небольшой пример:
1, 2, 3, 7, 8, 12
(У меня также есть на него авторские права.)
Если взглянуть интуитивно, какой из вариантов кажется вам аномалией?
Лично я бы сказал 12 .
Теперь посмотрим на результаты. LOF показывает, что выброс равен 7 .
(И вы можете заметить, что в случае k-расстояния мы бы сказали, что оно равно 12. )
Теперь мы можем сравнить Isolation Forest и LOF бок о бок.
Слева, с наборами данных 1, 2, 3, 9 , оба метода согласуются:
9 — явный выброс.
Isolation Forest дает ему самую низкую оценку,
а LOF дает ему наивысшее значение LOF.
Если присмотреться, то для Isolation Forest: 1, 2 и 3 разницы в результатах нет. А LOF даёт более высокий результат для 2. Это мы уже заметили.
С наборами данных 1, 2, 3, 7, 8, 12 ситуация меняется.
- Isolation Forest указывает на 12 как на самую изолированную точку.
Это соответствует интуиции: 12 — далеко не для всех. - Однако LOF вместо этого выделяет 7 .
Так кто же прав?
Трудно сказать.
На практике нам сначала необходимо договориться с бизнес-командами о том, что на самом деле означает «аномалия» в контексте наших данных.
Потому что при неконтролируемом обучении не существует единой истины.
Существует только определение «аномалии», которое использует каждый алгоритм.
Вот почему так важно понимать
как работает алгоритм и какие виды аномалий он предназначен для обнаружения.
Только после этого вы сможете решить, является ли метод LOF, или k-расстояния, или изолирующего леса правильным выбором для вашей конкретной ситуации.
И в этом заключается суть неконтролируемого обучения:
Разные алгоритмы рассматривают данные по-разному.
«Истинного» выброса не существует.
Только определение того, что означает выброс для каждой модели.
Вот почему понимание того, как работает алгоритм,
важнее, чем конечный результат, который он выдает.
Заключение
Оба метода — LOF и Isolation Forest — обнаруживают аномалии, но рассматривают данные с совершенно разных точек зрения.
- k-расстояние показывает, какое расстояние должна пройти точка, чтобы найти своих соседей.
- LOF сравнивает локальные плотности.
- Изолирующий лес изолирует точки, используя случайные разделения.
И даже на очень простых наборах данных эти методы могут не сработать.
Один алгоритм может пометить точку как выброс, в то время как другой выделит совершенно другую.
И вот ключевое сообщение:
При неконтролируемом обучении не существует «истинных» выбросов.
Каждый алгоритм определяет аномалии в соответствии со своей логикой.
Вот почему понимание того, как работает метод, важнее, чем число, которое он выдает.
Только тогда вы сможете выбрать правильный алгоритм для нужной ситуации и с уверенностью интерпретировать результаты.
Источник: towardsdatascience.com
