Обнаружение совпадений между ботами в Dota 2 с помощью Isolation Forests

Обнаружение совпадений между ботами в Dota 2 с помощью Isolation Forests

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

О Isolation Forest

Предложено Zhou et. al. В 2015 году изоляционный лес - это новый подход к обнаружению аномалий, который использует следующие свойства аномалий:

(i) Большинство точек в наборе данных не являются аномальными.

(ii) Аномалии обычно сильно отличаются от остального набора данных.

Модель включает в себя построение леса двоичных деревьев классификации, аналогичного алгоритму случайных лесов, за исключением того, что вместо классификации точек данных дерево изоляции рекурсивно разбивает набор данных, чтобы изолировать данный экземпляр. Из-за вышеупомянутых свойств требуется меньше секций для отделения аномальных точек данных от остальной части набора данных по сравнению с неаномальными точками. Следующий рисунок, взятый из их статьи, прекрасно иллюстрирует эту особенность:

В результате путь, пройденный через дерево изоляции до аномальной точки, намного короче, чем путь к нормальной точке. Когда деревья в изолированном лесу вместе производят более короткие [чем обычно] длины пути для конкретной точки, модель может сказать (с некоторой уверенностью), что точка является аномальной. Чтобы дать оценку аномалии, ограниченную от 0 до 1, длина пути нормализуется с использованием средней длины пути неудачного поиска в типичном двоичном дереве поиска.

У использования этого метода перед традиционными методами обнаружения аномалий есть немало плюсов:

(i) Быстро, с линейной временной сложностью. Вычислительные затраты невысоки, поскольку не требуются измерения расстояния или плотности, и фактически поощряется построение частичных деревьев на основе данных с частичной выборкой.

(ii) Легко обрабатывает многомерные данные и может принимать нерелевантные атрибуты.

(iii) Низкая стоимость памяти.

Обнаружение матчей между ботами в Dota 2

Благодаря хорошим людям, эта модель легко доступна для использования в R, а также в Python, первый в виде собственного пакета IsolationForest, а второй - в пакете scikit-learn.

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

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

Люди создают учетные записи ботов для автоматической игры в эти матчи по двум основным причинам:

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

(ii) Повышение рейтинга навыков существующей учетной записи (позволяя команде с этой учетной записью выиграть)

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

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

API OpenDota предоставляет нам необходимую игровую статистику; на самом деле намного больше, чем нам нужно. В этом случае мы получаем только основную информацию о матче, такую ​​как статистика игроков (убийства, смерти, передачи, нанесенный урон и т. Д.) И продолжительность матча. На основе статистики игроков мы получаем фактические характеристики, которые будем использовать в модели: агрегированные характеристики победившей и проигравшей команд, то есть средние значения и стандартные отклонения для каждого показателя в каждой команде. Мы не хотим рассматривать статистику игроков оптом, поскольку сами по себе они мало что рассказывают нам об игре.

Мы заполняем модель 5800 случайно выбранными совпадениями, устанавливая максимальный размер подвыборки равным 0,2 от обучающего набора, а количество оценок - 1000. Подвыборка важна, потому что деревья лучше всего работают с меньшими размерами выборки - это также противодействует проблеме маскирования. , когда группа аномалий маскирует собственное присутствие.

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

Модель работает очень хорошо, с AUC 1 на тестовом наборе - с порогом 0,6 мы можем точно классифицировать все совпадения ботов без каких-либо ложных срабатываний. Такой результат мог быть возможен из-за небольшого набора данных, а также резкой разницы между совпадениями ботов и обычными совпадениями, что упрощает выделение аномальных точек.

Чтобы просмотреть код, использованный в этом блоге, посетите страницу этого проекта на github.