Немного о скрытых деревьях решений

Скрытые деревья решений (СДР, hidden decision trees, HDT) – это метод, запатентованный доктором Гранвилем и предназначенный для оценки больших объемов данных, связанных с различными операциями. Он объединяет в себе робастную логистическую регрессию (robust logistic regression) и сотни малых деревьев решений (каждое из которых представляет, например, определенный тип мошеннической операции).

Кроме того, метод обеспечивает значительные преимущества по сравнению как с логистической регрессией, так и с деревьями решений: надежность, простоту интерпретации, не требуется отсечение ветвей (tree pruning), не требуются критерии расщепления узлов (node splitting criteria). Благодаря этому, данный метод является очень мощным инструментом, реализация которого достаточно проста даже для тех, кто не имеет большого опыта в статистике.

Скрытые деревья решений – это метод, применяемый в области статистики и интеллектуального анализа данных (подобный логистической регрессии, методу опорных векторов (support vector machine, SVM), нейронным сетям или деревьям решений), предназначенный для решения задач, связанных с большими объемами данных, нелинейностью и независимыми переменными, обладающими высокой корреляцией.

Метод легко реализуется на любом языке программирования. Он более надежный, чем деревья решений или логистическая регрессия, и позволяет получить естественные конечные узлы (final nodes). Реализации обычно в значительной степени основываются на больших гранулярных хеш-таблицах (granular hash tables).

На самом деле, дерево решений не строится (поэтому и возникло название «скрытые» деревья решений), но конечный результат процедуры СДР состоит из нескольких сотен узлов множества непересекающихся малых деревьев решений. Каждое из этих родительских (невидимых) деревьев решений соответствует, например, определенному типу мошенничества в моделях для выявления мошенничества. Интерпретация проста в отличие от традиционных деревьев решений.

Данный метод был разработан в 2003 году для выявления мошенничества с кредитными картами. В настоящее время он не входит ни в один набор статистических инструментов. Часто скрытые деревья решений объединяются с логистической регрессией в гибридный оценочный алгоритм, при этом 80% операций оценивается с помощью СДР, а оставшиеся 20% – с помощью соответствующей логистической регрессии.

Скрытые деревья решений используют преимущество структуры многомерных признаков (multivariate features), обычно наблюдающихся при оценке большого количества операций, например при выявлении мошенничества. Данный метод не связан со скрытыми марковскими полями (hidden Markov fields).

Потенциальные области применения

  • Выявление мошенничества. Распознавание спама.
  • Веб-аналитика.
    • Оценка/тарификация ключевых слов (рекламные сети, платный поиск).
    • Оценка операций (клик, лайк, конверсия, действие).
    • Выявление мошенничества, связанного с кликами.
    • Оценка веб-сайта, рекламы, целевой страницы (landing page), рекламной платформы.
    • Коллективная фильтрация (аналитика социальных сетей).
    • Алгоритмы релевантности.
  • Интеллектуальный анализ текстов.
    • Алгоритмы оценки и ранжирования.
    • Выявление нарушений авторских прав.
    • Отзывы пользователей: автоматическая кластеризация.

Реализация

Представленная здесь модель используется для оценки кликов. Целью является создание прогнозных оценок, где оценка = f(отклик) (score = f(response)), т.е. оценка – это функция от отклика. Отклик иногда называют зависимой переменной в статистических и прогнозных моделях.

  • Примеры отклика:
    • Вероятность конверсии (данные о веб-трафике – строгие/нестрогие конверсии).
    • Коэффициент конверсии (conversion rate, CR).
    • Вероятность того, что операция является мошеннической.
  • Независимые переменные: признаки (feature) или правила (rule). Они имеют высокую корреляцию.

Традиционные модели по сравнению со скрытыми деревьями решений включают в себя логистическую регрессию, деревья решений и наивный байесовский классификатор (naïve Bayes).

СДР используют взаимно однозначное отображение (one-to-one mapping) между оценками и многомерными признаками. Многомерный признак – это комбинация правил, связанная с определенной операцией (т.е. вектор, определяющий, какие правила срабатывают, а какие нет) Иногда его называют вектором флагов (flag vector) или узлом (node).

Базовые характеристики СДР на основе типичного набора данных:

  • Если использовать 40 бинарных правил, то мы получим 240 потенциальных многомерных признаков.
  • Если обучающий набор данных содержит 10 миллионов операций, очевидно, мы получим, как максимум, 10 миллионов многомерных признаков, что значительно меньше чем 240.
  • 500 признаков из 10 миллионов характеризуют 80% всех операций.
  • 500 основных многомерных признаков имеют большой прогнозный потенциал.
  • Для классификации оставшихся 20% операций требуется альтернативный алгоритм.
  • Использование соседних основных многомерных признаков для оценки оставшихся 20% операций создает погрешность, потому что редкие многомерные признаки (иногда не присутствующие в обучающем наборе данных) соответствуют наблюдению, имеющему оценку ниже средней (т.к. они вызывают срабатывание многих правил выявления мошенничества).

Детали реализации

Каждый основной узел (или многомерный признак) является конечным узлом скрытого дерева решений. Нет необходимости в отсечении ветвей и критериях расщепления, потому что СДР – это простой и быстрый метод, который может использовать эффективные хеш-таблицы (где ключ = признак, значение = оценка). 500 основных узлов, используемых для классификации (т.е. оценки) 80% операций, получаются из множества срытых деревьев решений – срытых, потому что вы не использовали алгоритм дерева решений для их создания.

Оставшиеся 20% операций оцениваются с помощью альтернативного метода (обычно, с помощью логистической регрессии). Таким образом, СДР – это гибридный алгоритм, объединяющий в себе многочисленные малые, легко интерпретируемые, невидимые деревья решений (только конечные узлы) и логистическую регрессию.

Обратите внимание на то, что в логистической регрессии мы используем ограниченные коэффициенты регрессии. Эти коэффициенты зависят от 2-х или 3-х основных параметров и имеют такой же знак, что и корреляция между правилом, которое они представляют, и откликом или оценкой. Это делает регрессию нечувствительной к высоким взаимным корреляциям между «независимыми» переменными (правилами), которые на самом деле не являются таковыми в данном случае. Этот подход подобен гребневой регрессии (ridge regression), логической регрессии (logic regression) и методу Лассо (Lasso regression). Регрессия используется для точной настройки основных параметров, связанных с коэффициентами регрессии. Дальше я покажу, что хорошо разработанные приближенные решения (мы реализуем здесь приближенную логистическую регрессию) имеют почти такую же точность, как точные решения, однако могут быть при этом намного более надежными.

Объединение оценок

Мы имеем дело с двумя типами оценок:

  • 500 основных узлов обеспечивают оценку S1 для 80% операций.
  • Логистическая регрессия обеспечивает оценку S2 для 100% операций.

Чтобы объединить оценки, необходимо:

  • Масштабировать оценку S2, используя 80% операций, имеющих две оценки S1 и S Масштабировать – означает применить линейное преобразование (linear transformation) таким образом, чтобы обе оценки имели одинаковое математическое ожидание (mean) и дисперсию (variance). Пусть S3 будет результатом масштабирования S2.
  • Операции, которые нельзя оценить с помощью S1, оцениваются с помощью S.

Узлы СДР обеспечивают альтернативную сегментацию данных. Один крупный сегмент со средней оценкой соответствует нейтральным операциям (не вызывающим срабатывания правил). Сегменты с очень низкими оценками соответствуют определенным случаям мошенничества. В каждом сегменте все операции имеют одинаковую оценку. В рамках СДР реализуется другой тип сегментации по сравнению с методом главных компонент (principal component analysis, PCA) и другими методами.

История СДР

  • 2003 год. Первая версия применена для выявления мошенничества с кредитными картами.
  • 2006 год. Применение для оценки кликов и выявления мошенничества, связанного с кликами.
  • 2008 год. Более совершенные версии для работы с гранулярными и очень большими наборами данных.
    • Срытые леса (hidden forests) – множество СДР, каждое из которых применяется к кластеру коррелированных правил.
    • Иерархические СДР – с помощью СДР моделируется структура высшего порядка, а не только кластеры правил.
    • Не бинарные правила (наивный байесовский классификатор, объединенный с СДР).

Пример. Оценка веб-трафика

На рисунке ниже показано распределение оценок для системы на основе 20 правил, каждое из которых имеет низкую частоту срабатывания. Распределение обладает следующими свойствами:

  • Обратная кривая нормального распределения (reverse bell curve).
  • Оценки ниже 425 соответствуют неоплачиваемым операциям.
  • Всплеск в самом начале и в самом конце шкалы оценок.
  • 50% всех операций имеют хорошие оценки.
  • Параметры оценок:
    • Снижение на 50 пунктов соответствует снижению коэффициента конверсии на 50%.
    • Средняя оценка 650.
  • Усовершенствование модели для перехода от обратной кривой нормального распределения к обычной кривой нормального распределения:
    • Баланс между качеством операций и выявлением мошенничества.
    • Добавьте антиправила, выполните сглаживание оценок.
Пример распределения оценок на основе СДР.

Пример распределения оценок на основе СДР.

На рисунке ниже представлено сравнение оценок и коэффициентов конверсии. СДР были применены к веб-данным для оценки кликов, чтобы предсказать вероятность конверсии (под конверсией подразумевается покупка, переход или регистрация на какой-либо целевой странице). В целом мы получили достаточно хорошее соответствие.

Пики на графике могут означать:

  • Фальшивые конверсии (случаются часто, если конверсией считается простой переход).
  • Прогнозная ошибка (residual noise).
  • Модель нуждается в усовершенствовании (используйте антиправила).

Впадины могут означать:

  • Неучтенные конверсии (проблема с куки, для конверсии потребовалось слишком много времени).
  • Прогнозная ошибка.
  • Модель нуждается в усовершенствовании.

Пики и впадины также могут возникать, если вы объединяете различные типы конверсий: трафик, CTR (click-through rate) которого составляет 0,5%, вместе с трафиком, CTR которого составляет 10%.

Оценки на основе СДР для прогнозирования конверсий.

Оценки на основе СДР для прогнозирования конверсий

Заключение

СДР – это быстрый, обладающий простой реализацией алгоритм, способный эффективно обрабатывать большие наборы данных и дающий легко интерпретируемые результаты.

Алгоритм является непараметрическим и робастным. Риск переобучения достаточно мал, если выбирается не более 500 основных узлов, а для исключения нестабильных узлов применяются методы перекрестной проверки (cross validation). Алгоритм имеет встроенный простой механизм вычисления доверительных интервалов для оценок.

СДР – это гибридный алгоритм для выявления различных типов структур: линейных структур с помощью регрессии, и нелинейных – с помощью основных узлов.

По материалам Data Science Central

Перевод Станислава Петренко 

1 комментарий

  1. Yan:

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

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =