random forest что это
Модель Random Forest для классификации, реализация на c#
Доброго времени суток, читатель. Random Forest сегодня является одним из популярнейших и крайне эффективных методов решения задач машинного обучения, таких как классификация и регрессия. По эффективности он конкурирует с машинами опорных векторов, нейронными сетями и бустингом, хотя конечно не лишен своих недостатков. С виду алгоритм обучения крайне прост (в сравнении скажем с алгоритмом обучения машины опорных векторов, кому мало острых ощущений в жизни, крайне советую заняться этим на досуге). Мы же попробуем в доступной форме разобраться в основных идеях, заложенных в Random Forest (бинарное дерево решений, бутстреп аггрегирование или бэггинг, метод случайных подпространств и декорреляция) и понять почему все это вместе работает. Модель относительно своих конкурентов довольно таки молодая: началось все со статьи 1997 года в которой авторы предлагали способ построения одного дерева решений, используя метод случайных подпространств признаков при создании новых узлов дерева; затем был ряд статей, который завершился публикацией каноничной версии алгоритма в 2001 году, в котором строится ансамбль решающих деревьев на основе бутстреп агрегирования, или бэггинга. В конце будет приведен простой, совсем не шустрый, но крайне наглядный способ реализации этой модели на c#, а так же проведен ряд тестов. Кстати на фотке справа вы можете наблюдать настоящий случайный лес который произрастает у нас тут в Калининградской области на Куршской косе.
Бинарное дерево решений
Начать следует с дерева, как с основного структурного элемента леса, но в контексте изучаемой модели. Изложение будет строится на предположении, что читатель понимает, что из себя представляет дерево, как структура данных. Построение дерева будет выполняться примерно по алгоритму CART (Classification and Regression Tree), который строит бинарные деревья решений. Кстати тут на хабре есть годная статья по построению таких деревьев на базе минимизации энтропии, в нашем варианте это будет частным случаем. Итак представьте себе пространство признаков, допустим двумерное, что бы было легче визуализировать, в котором задано множество объектов двух классов. 
Введем ряд обозначений. Обозначим множество признаков следующим образом:
Для каждого признака можно выделить множество его значений, основываясь либо на обучающем множестве, либо используя другую априорную информацию о задаче, обозначим следующим образом конечное множество значений признака:
Так же необходимо ввести так называемую меру неоднородности множества относительно его меток. Представьте, что некоторое подмножество обучающего множества состоит из 5 красных и 10 синих объектов, тогда мы можем утверждать, что в этом подмножестве вероятность вытянуть красный объект будет 1/3, а синий 2/3. Обозначим следующим образом вероятность k-ого класса в некотором подмножестве обучающего множества:
Таким образом мы задали эмпирическое дискретное вероятностное распределение меток в подмножестве наблюдений. Мерой неоднородности этого подмножества будем называть функцию следующего вида, где K(A) — общее количество меток подмножества A:
Мера неоднородности задается таким образом, что бы значение функции по возможности возрастало при увеличении разношерстности набора, достигая своего максимума тогда, когда набор состоит из одинакового количества всевозможных меток, и минимума в случае если набор состоит только из меток одного класса (еще раз советую взглянуть на энтропийный пример с картинками).
Перечислим возможные критерии остановки: достигнута максимальная глубина узла; вероятность доминирующего класса в разбиении превышает некоторый порог (я использую 0.95); количество элементов в подмножестве меньше некоторого порога. В итоге у нас получится разбиение всего множества на (гипер)прямоугольники, и каждое такое подмножество множества обучения будет ассоциировано с одним листом дерева, а все внутренние узлы представляют из себя одно из условий разбиения; или другими словами некоторый предикат. У текущего узла, левый потомок ассоциирован с теми элементами множества, для которых предикат верен, а правый соответственно с тему для которых предикат возвращает ложь. Выглядит это примерно следующим образом:
Итак мы получили дерево, как же принять на нем решение? Нам не составит труда определить к какому из подмножеств обучающего множества принадлежит любой входной образ, по мнению конкретного дерева решений. Далее нам остается только выбрать доминирующий класс в данном подмножестве и вернуть его клиенту, либо вернуть вероятностное распределение меток в данном подмножестве.
Кстати на счет задачи регрессии. Описанный способ построения дерева легко меняется с задачи классификации на задачу регрессии. Для этого необходимо заменить меру неоднородности на некоторую меру ошибки прогнозирования, например на среднеквадратичное отклонение. А при принятии решения вместо доминирующего класса используется среднее значение целевой переменной.
Вроде с деревьями все порешали. Мы не будем останавливаться на плюсах и минусах этого метода, в википедии есть хороший список. Но в конце хочется добавить иллюстрацию из книги An Introduction to Statistical Learning про разницу линейных моделей и деревьев.
Данная иллюстрация показывает разницу между линейной моделью и бинарным деревом решений, как видите в случае линейной разделимости, в общем дерево будет показывать менее точный результат нежели простой линейный классификатор.
Bootstrap aggregating или bagging
Перейдем к следующей идейной составляющей random forest’а. Итак название BAGging, образовано от Bootstrap AGgregating. В статистике под бутстрепом понимают как способ оценки стандартной ошибки статистик выборочного вероятностного распределения, так и способ семплирования выборок из набора данных основанный на методе Монте-Карло.
Декорреляция
Думаю уже понятно как получить просто лес: сгенерируем некоторое количество бутстреп выборок и обучим дерево решений на каждой из них. Но тут существует небольшая проблема, почти все деревья будут более или менее одинаковой структуры. Давайте проведем эксперимент, возьмем множество с двумя классами и 32-мя фичами, построим 1000 деревьев решений на бутстреп семплах, и посмотрим на вариативность предиката корневого узла.
Мы видим что из 1000 деревьев 22-ой признак (очевидно значение фичи одно и тоже) встречается в 526 деревьях, и почти во всех дочерние ноды одинаковые. Другими словами деревья скоррелированны относительно друг друга. Получается, что нет смысла строить 1000 деревьев, если достаточно всего нескольких, а чаще всего одного или двух. А теперь давайте попробуем при построении дерева использовать при разделении каждого узла только некоторый небольшой случайный набор признаков из множества всех признаков, скажем 7 случайных из 32.
Как видите, распределение значительно изменилось в сторону большего разнообразия деревьев (кстати не только в корневом узле, но и в дочерних), что и было целью такого трюка. Теперь 22 признак встречается только в 158 случаях. Выбор «7 случайных из 32 признаков» обоснован эмпирическим наблюдением (я так и не нашел автора этого наблюдения), и в задачах классификации это как правило квадратный корень из общего количества признаков. Другими словами деревья стали менее скореллированными, а процесс называется декорреляция.
Такой метод, в общем, называется Random subspace method и применяется не только для деревьев решений, но и для других моделей, таких как нейросети.
В общем как то так выглядел бы обычный ровный лес, и декоррелированный. 
Перейдем к реализации. Еще раз хочу напомнить, что приведенный мной пример не является быстрой реализацией random forest’а, а носит учебный лишь характер, призванной помочь понять основные идеи модели. Например тут вы найдете пример годной и шустрой имплементации, но к сожалению менее понятной.
Комментарии я буду вставлять там где необходимо прямо в коде, что бы не разбивать классы на куски.
Единица наблюдения в моем случае представляется следующим классом.
Для каждого узла дерева необходимо хранить информацию о предикате, который используется для принятия решения о классификации.
Рассмотрим класс бинарного решающего дерева.
Остановимся на норме, используемой в классе решающего дерева.
Ну и осталось рассмотреть только сам класс random forest.
Заключение и ссылки
Если вы смотрели в код, то могли заметить, что в дереве есть функция для записи структуры и условий в dot формат, который визуализируется программой GraphVis. Если запустить случайный лес со следующими параметрами на вышеупомянутом множестве:
То следующий код поможет нам визуализировать этот лес:
Давайте глянем на некоторые из них, они получаются совсем разные благодаря декорреляции.
Алгоритм классификации Random Forest на Python
Случайный лес (Random forest, RF) — это алгоритм обучения с учителем. Его можно применять как для классификации, так и для регрессии. Также это наиболее гибкий и простой в использовании алгоритм. Лес состоит из деревьев. Говорят, что чем больше деревьев в лесу, тем он крепче. RF создает деревья решений для случайно выбранных семплов данных, получает прогноз от каждого дерева и выбирает наилучшее решение посредством голосования. Он также предоставляет довольно эффективный критерий важности показателей (признаков).
Случайный лес имеет множество применений, таких как механизмы рекомендаций, классификация изображений и отбор признаков. Его можно использовать для классификации добросовестных соискателей кредита, выявления мошенничества и прогнозирования заболеваний. Он лежит в основе алгоритма Борута, который определяет наиболее значимые показатели датасета.
Алгоритм Random Forest
Давайте разберемся в алгоритме случайного леса, используя нетехническую аналогию. Предположим, вы решили отправиться в путешествие и хотите попасть в туда, где вам точно понравится.
Итак, что вы делаете, чтобы выбрать подходящее место? Ищите информацию в Интернете: вы можете прочитать множество различных отзывов и мнений в блогах о путешествиях, на сайтах, подобных Кью, туристических порталах, — или же просто спросить своих друзей.
Предположим, вы решили узнать у своих знакомых об их опыте путешествий. Вы, вероятно, получите рекомендации от каждого друга и составите из них список возможных локаций. Затем вы попросите своих знакомых проголосовать, то есть выбрать лучший вариант для поездки из составленного вами перечня. Место, набравшее наибольшее количество голосов, станет вашим окончательным выбором для путешествия.
Вышеупомянутый процесс принятия решения состоит из двух частей.
Технически Random forest — это метод (основанный на подходе «разделяй и властвуй»), использующий ансамбль деревьев решений, созданных на случайно разделенном датасете. Набор таких деревьев-классификаторов образует лес. Каждое отдельное дерево решений генерируется с использованием метрик отбора показателей, таких как критерий прироста информации, отношение прироста и индекс Джини для каждого признака.
Любое такое дерево создается на основе независимой случайной выборки. В задаче классификации каждое дерево голосует, и в качестве окончательного результата выбирается самый популярный класс. В случае регрессии конечным результатом считается среднее значение всех выходных данных ансамбля. Метод случайного леса является более простым и эффективным по сравнению с другими алгоритмами нелинейной классификации.
Как работает случайный лес?
Алгоритм состоит из четырех этапов:
Поиск важных признаков
Random forest также предлагает хороший критерий отбора признаков. Scikit-learn предоставляет дополнительную переменную при использовании модели случайного леса, которая показывает относительную важность, то есть вклад каждого показателя в прогноз. Библиотека автоматически вычисляет оценку релевантности каждого признака на этапе обучения. Затем полученное значение нормализируется так, чтобы сумма всех оценок равнялась 1.
Такая оценка поможет выбрать наиболее значимые показатели и отбросить наименее важные для построения модели.
Случайный лес использует критерий Джини, также известный как среднее уменьшение неопределенности (MDI), для расчета важности каждого признака. Кроме того, критерий Джини иногда называют общим уменьшением неопределенности в узлах. Он показывает, насколько снижается точность модели, когда вы отбрасываете переменную. Чем больше уменьшение, тем значительнее отброшенный признак. Таким образом, среднее уменьшение является необходимым параметром для выбора переменной. Также с помощью данного критерия можете быть отображена общая описательная способность признаков.
Сравнение случайных лесов и деревьев решений
Создание классификатора с использованием Scikit-learn
Вы будете строить модель на основе набора данных о цветках ириса, который является очень известным классификационным датасетом. Он включает длину и ширину чашелистика, длину и ширину лепестка, и тип цветка. Существуют три вида (класса) ирисов: Setosa, Versicolor и Virginica. Вы построите модель, определяющую тип цветка из вышеперечисленных. Этот датасет доступен в библиотеке scikit-learn или вы можете загрузить его из репозитория машинного обучения UCI.
Random Forest, метод главных компонент и оптимизация гиперпараметров: пример решения задачи классификации на Python
У специалистов по обработке и анализу данных есть множество средств для создания классификационных моделей. Один из самых популярных и надёжных методов разработки таких моделей заключается в использовании алгоритма «случайный лес» (Random Forest, RF). Для того чтобы попытаться улучшить показатели модели, построенной с использованием алгоритма RF, можно воспользоваться оптимизацией гиперпараметров модели (Hyperparameter Tuning, HT).
Кроме того, распространён подход, в соответствии с которым данные, перед их передачей в модель, обрабатывают с помощью метода главных компонент (Principal Component Analysis, PCA). Но стоит ли вообще этим пользоваться? Разве основная цель алгоритма RF заключается не в том, чтобы помочь аналитику интерпретировать важность признаков?
Да, применение алгоритма PCA может привести к небольшому усложнению интерпретации каждого «признака» при анализе «важности признаков» RF-модели. Однако алгоритм PCA производит уменьшение размерности пространства признаков, что может привести к уменьшению количества признаков, которые нужно обработать RF-моделью. Обратите внимание на то, что объёмность вычислений — это один из основных минусов алгоритма «случайный лес» (то есть — выполнение модели может занять немало времени). Применение алгоритма PCA может стать весьма важной частью моделирования, особенно в тех случаях, когда работают с сотнями или даже с тысячами признаков. В результате, если самое важное — это просто создать наиболее эффективную модель, и при этом можно пожертвовать точностью определения важности признаков, тогда PCA, вполне возможно, стоит попробовать.
Теперь — к делу. Мы будем работать с набором данных по раку груди — Scikit-learn «breast cancer». Мы создадим три модели и сравним их эффективность. А именно, речь идёт о следующих моделях:
1. Импорт данных
Для начала загрузим данные и создадим датафрейм Pandas. Так как мы пользуемся предварительно очищенным «игрушечным» набором данных из Scikit-learn, то после этого мы уже сможем приступить к процессу моделирования. Но даже при использовании подобных данных рекомендуется всегда начинать работу, проведя предварительный анализ данных с использованием следующих команд, применяемых к датафрейму ( df ):
Фрагмент датафрейма с данными по раку груди. Каждая строка содержит результаты наблюдений за пациентом. Последний столбец, cancer, содержит целевую переменную, которую мы пытаемся предсказать. 0 означает «отсутствие заболевания». 1 — «наличие заболевания»
2. Разделение набора данных на учебные и проверочные данные
Например, если есть миллионы строк, можно разделить набор, выделив 90% строк на учебные данные и 10% — на проверочные. Но исследуемый набор данных содержит лишь 569 строк. А это — не так уж и много для тренировки и проверки модели. В результате для того, чтобы быть справедливыми по отношению к учебным и проверочным данным, мы разделим набор на две равные части — 50% — учебные данные и 50% — проверочные. Мы устанавливаем stratify=y для обеспечения того, чтобы и в учебном, и в проверочном наборах данных присутствовало бы то же соотношение 0 и 1, что и в исходном наборе данных.
3. Масштабирование данных
Прежде чем приступать к моделированию, нужно выполнить «центровку» и «стандартизацию» данных путём их масштабирования. Масштабирование выполняется из-за того, что разные величины выражены в разных единицах измерения. Эта процедура позволяет организовать «честную схватку» между признаками при определении их важности. Кроме того, мы конвертируем y_train из типа данных Pandas Series в массив NumPy для того чтобы позже модель смогла бы работать с соответствующими целевыми показателями.
4. Обучение базовой модели (модель №1, RF)
Сейчас создадим модель №1. В ней, напомним, применяется только алгоритм Random Forest. Она использует все признаки и настроена с использованием значений, задаваемых по умолчанию (подробности об этих настройках можно найти в документации к sklearn.ensemble.RandomForestClassifier). Сначала инициализируем модель. После этого обучим её на масштабированных данных. Точность модели можно измерить на учебных данных:
Если нам интересно узнать о том, какие признаки являются самыми важными для RF-модели в деле предсказания рака груди, мы можем визуализировать и квантифицировать показатели важности признаков, обратившись к атрибуту feature_importances_ :
Визуализация «важности» признаков
Показатели важности признаков
5. Метод главных компонент
После того, как число используемых компонент превышает 10, рост их количества не очень сильно повышает объяснённую дисперсию
Этот датафрейм содержит такие показатели, как Cumulative Variance Ratio (кумулятивный размер объяснённой дисперсии данных) и Explained Variance Ratio (вклад каждой компоненты в общий объём объяснённой дисперсии)
Каждая компонента — это линейная комбинация исходных переменных с соответствующими «весами». Мы можем видеть эти «веса» для каждой компоненты, создав датафрейм.
Датафрейм со сведениями по компонентам
6. Обучение базовой RF-модели после применения к данным метода главных компонент (модель №2, RF + PCA)
Теперь мы можем передать в ещё одну базовую RF-модель данные X_train_scaled_pca и y_train и можем узнать о том, есть ли улучшения в точности предсказаний, выдаваемых моделью.
Модели сравним ниже.
7. Оптимизация гиперпараметров. Раунд 1: RandomizedSearchCV
После обработки данных с использованием метода главных компонент можно попытаться воспользоваться оптимизацией гиперпараметров модели для того чтобы улучшить качество предсказаний, выдаваемых RF-моделью. Гиперпараметры можно рассматривать как что-то вроде «настроек» модели. Настройки, которые отлично подходят для одного набора данных, для другого не подойдут — поэтому и нужно заниматься их оптимизацией.
Начать можно с алгоритма RandomizedSearchCV, который позволяет довольно грубо исследовать широкие диапазоны значений. Описания всех гиперпараметров для RF-моделей можно найти здесь.
Мы будем заниматься подбором следующих гиперпараметров:
Результаты работы алгоритма RandomizedSearchCV
Теперь создадим столбчатые графики, на которых, по оси Х, расположены значения гиперпараметров, а по оси Y — средние значения, показываемые моделями. Это позволит понять то, какие значения гиперпараметров, в среднем, лучше всего себя показывают.
Анализ значений гиперпараметров
Если проанализировать вышеприведённые графики, то можно заметить некоторые интересные вещи, говорящие о том, как, в среднем, каждое значение гиперпараметра влияет на модель.
8. Оптимизация гиперпараметров. Раунд 2: GridSearchCV (окончательная подготовка параметров для модели №3, RF + PCA + HT)
После применения алгоритма RandomizedSearchCV воспользуемся алгоритмом GridSearchCV для проведения более точного поиска наилучшей комбинации гиперпараметров. Здесь исследуются те же гиперпараметры, но теперь мы применяем более «обстоятельный» поиск их наилучшей комбинации. При использовании алгоритма GridSearchCV исследуется каждая комбинация гиперпараметров. Это требует гораздо больших вычислительных ресурсов, чем использование алгоритма RandomizedSearchCV, когда мы самостоятельно задаём число итераций поиска. Например, исследование 10 значений для каждого из 6 гиперпараметров с кросс-валидацией по 3 блокам потребует 10⁶ x 3, или 3000000 сеансов обучения модели. Именно поэтому мы и используем алгоритм GridSearchCV после того, как, применив RandomizedSearchCV, сузили диапазоны значений исследуемых параметров.
Итак, используя то, что мы выяснили с помощью RandomizedSearchCV, исследуем значения гиперпараметров, которые лучше всего себя показали:
Здесь мы применяем кросс-валидацию по 3 блокам для 540 (3 x 1 x 5 x 6 x 6 x 1) сеансов обучения модели, что даёт 1620 сеансов обучения модели. И уже теперь, после того, как мы воспользовались RandomizedSearchCV и GridSearchCV, мы можем обратиться к атрибуту best_params_ для того чтобы узнать о том, какие значения гиперпараметров позволяют модели наилучшим образом работать с исследуемым набором данных (эти значения можно видеть в нижней части предыдущего блока кода). Эти параметры используются при создании модели №3.
9. Оценка качества работы моделей на проверочных данных
Теперь можно оценить созданные модели на проверочных данных. А именно, речь идёт о тех трёх моделях, описанных в самом начале материала.
Проверим эти модели:
Создадим матрицы ошибок для моделей и узнаем о том, как хорошо каждая из них способна предсказывать рак груди:
Результаты работы трёх моделей
Здесь оценивается метрика «полнота» (recall). Дело в том, что мы имеем дело с диагнозом рака. Поэтому нас чрезвычайно интересует минимизация ложноотрицательных прогнозов, выдаваемых моделями.
Учитывая это, можно сделать вывод о том, что базовая RF-модель дала наилучшие результаты. Её показатель полноты составил 94.97%. В проверочном наборе данных была запись о 179 пациентах, у которых есть рак. Модель нашла 170 из них.
Итоги
Это исследование позволяет сделать важное наблюдение. Иногда RF-модель, в которой используется метод главных компонент и широкомасштабная оптимизация гиперпараметров, может работать не так хорошо, как самая обыкновенная модель со стандартными настройками. Но это — не повод для того, чтобы ограничивать себя лишь простейшими моделями. Не попробовав разные модели, нельзя сказать о том, какая из них покажет наилучший результат. А в случае с моделями, которые используются для предсказания наличия у пациентов рака, можно сказать, что чем лучше модель — тем больше жизней может быть спасено.
Уважаемые читатели! Какие задачи вы решаете, привлекая методы машинного обучения?