Gini impurity что это

Реализация и разбор алгоритма «случайный лес» на Python

Принципы работы алгоритма «случайный лес» — от загрязнения Джини и единичного дерева принятия решений до решения задачи на основе реального набора данных.

Использование готовых библиотек, таких как Scikit-Learn, позволяет легко реализовать на Python сотни алгоритмов машинного обучения.

В этой статье мы научимся создать и использовать алгоритм «случайный лес» (Random Forest) на Python. Помимо непосредственного изучения кода, мы постараемся понять принципы работы модели. Этот алгоритм составлен из множества деревьев решений, поэтому сначала мы разберёмся, как одно такое дерево решает проблему классификации. После этого с помощью алгоритма решим проблему, используя набор реальных научных данных. Весь код, используемый в этой статье, доступен на GitHub в Jupyter Notebook.

Как работает дерево решений

Дерево решений — интуитивно понятная базовая единица алгоритма случайный лес. Мы можем рассматривать его как серию вопросов да/нет о входных данных. В конечном итоге вопросы приводят к предсказанию определённого класса (или величины в случае регрессии). Это интерпретируемая модель, так как решения принимаются так же, как и человеком: мы задаём вопросы о доступных данных до тех пор, пока не приходим к определённому решению (в идеальном мире).

Базовая идея дерева решений заключается в формировании запросов, с которыми алгоритм обращается к данным. При использовании алгоритма CART вопросы (также называемые разделением узлов) определяются таким образом, чтобы ответы вели к уменьшению загрязнения Джини (Gini Impurity). Это означает, что дерево решений формирует узлы, содержащие большое количество образцов (из набора исходных данных), принадлежащих к одному классу. Алгоритм старается обнаружить параметры со сходными значениями.

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

Дерево решений для простой задачи

Начнём с проблемы простой бинарной классификации, изображённой на диаграмме.

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

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

Мы используем Scikit-Learn, чтобы создать дерево решений и обучить ( fit ) его, используя наши данные.

from sklearn.tree import DecisionTreeClassifier # Создаём и обучаем дерево принятия решений tree = DecisionTreeClassifier(random_state=RSEED) tree.fit(X, y)

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

Можно проверить точность предсказаний нашей модели:

print('Model Accuracy:', tree.score(X, y)) Model Accuracy: 1.0

Разумеется, мы получим точность 100 %, так как сообщили модели правильные ответы ( y ) и не ограничивали глубину дерева. Но следует помнить, что подобная подгонка дерева решений под тренировочные данные может спровоцировать переобучение модели.

Визуализация дерева решений

Что же на самом деле происходит при обучении дерева решений? Хороший способ понять это — визуализация модели при помощи соответствующей функции Scikit-Learn (подробнее функция рассматривается в данной статье).

Во всех узлах, кроме листьев (цветные узлы без исходящих связей), содержится 5 частей:

Вопрос о значении параметра образца. Ответ может принимать значение True или False . Это точка разделения узла, в зависимости от ответа определяется, в каком направлении вниз по дереву продвинется образец данных.
Gini : средневзвешенное загрязнение Джини должно уменьшаться по мере того, как мы движемся вниз по дереву.
Samples : количество прошедших через этот узел образцов.
Value : отношение классов, прошедших через этот узел, выраженное в абсолютных числах. К примеру, верхний узел выделил 2 образца класса 0 и 4 образца класса 1.
Class : класс большинства прошедших через узел образцов. Для листьев это прогнозируемое значение всех попадающих в эти узлы элементов.

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

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

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

Загрязнение Джини

Теперь самое время рассмотреть концепцию загрязнения Джини (математика не так уж страшна, как кажется). Загрязнение Джини — вероятность неверной маркировки в узле случайно выбранного образца. К примеру, в верхнем (корневом) узле вероятность неверной классификации образца равна 44.4 %. Это можно вычислить с помощью уравнения:

Загрязнение Джини узла n равно 1 минус сумма отношений класса к общему количеству образцов pi, возведённых в квадрат, для каждого из множества классов J (в нашем случае это всего 2 класса). Звучит сложно, поэтому покажем, как вычисляется загрязнение Джини для корневого узла:

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

Затем процесс разделения повторяется с использованием «жадной», рекурсивной процедуры, пока дерево не достигнет максимальной глубины или в каждом узле не останутся только образцы одного класса. Общевзвешенное загрязнение Джини должно уменьшаться с каждым уровнем. В нашем случае на втором уровне оно составит 0.333:

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

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

Переобучение, или почему лес лучше одного дерева

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

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

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

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

Поиск баланса между излишней и недостаточной гибкостью модели является ключевой концепцией машинного обучения и называется компромиссом между вариативностью и погрешностью (bias-variance tradeoff).

Алгоритм дерева решений переобучается, если не ограничить его максимальную глубину. Он обладает неограниченной гибкостью и может разрастаться, пока не достигнет состояния идеальной классификации, в которой каждому образцу из набора данных будет соответствовать один лист. Если вернуться назад к созданию дерева и ограничить его глубину двумя слоями (сделав только одно разделение), классификация больше не будет на 100 % верной. Мы уменьшаем вариативность за счёт увеличения погрешности.

В качестве альтернативы ограничению глубины, которое ведёт к уменьшению вариативности (хорошо) и увеличению погрешности (плохо), мы можем собрать множество деревьев в единую модель. Это и будет классификатор на основе комитета деревьев принятия решений или просто «случайный лес».

Случайный лес

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

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

Случайная выборка тренировочных образцов

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

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

Случайные наборы параметров для разделения узлов

Вторая базовая концепция случайного леса заключается в использовании определённой выборки параметров образца для разделения каждого узла в каждом отдельном дереве. Обычно размер выборки равен квадратному корню из общего числа параметров. То есть, если каждый образец набора данных содержит 16 параметров, то в каждом отдельном узле будет использовано 4. Хотя обучение случайного леса можно провести и с полным набором параметров, как это обычно делается при регрессии. Этот параметр можно настроить в реализации случайного леса в Scikit-Learn.

Случайный лес сочетает сотни или тысячи деревьев принятия решений, обучая каждое на отдельной выборке данных, разделяя узлы в каждом дереве с использованием ограниченного набора параметров. Итоговый прогноз делается путём усреднения прогнозов от всех деревьев.

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

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

Поэтому нужно не опираться на решение какого-то одного аналитика, а собрать вместе их прогнозы. Более того, как и при использовании случайного леса, нужно разрешить каждому аналитику доступ только к определённым новостным источникам, в надежде на то, что эффекты шумов будут нейтрализованы выборкой. В реальной жизни мы полагаемся на множество источников (никогда не доверяйте единственному обзору на Amazon). Интуитивно нам близка не только идея дерева решений, но и комбинирование их в случайный лес.

Алгоритм Random Forest на практике

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

Набор данных

Мы попробуем рассчитать состояние здоровья пациентов в бинарной системе координат. В качестве параметров мы используем социально-экономические и персональные характеристики субъектов. В качестве меток мы используем 0 для плохого здоровья и 1 для хорошего. Этот набор данных был собран Центром по Контролю и Предотвращению Заболеваний и размещён в свободном доступе.

Как правило 80 % работы над научным проектом заключается в изучении, очистке и синтезировании параметров из сырых данных (подробнее узнать можно здесь). Однако в этой статье мы сосредоточимся на построении модели.

В данном примере мы сталкиваемся с задачей несбалансированной классификации, поэтому простой параметр точности модели не отобразит истинной её производительности. Вместо этого мы используем площадь под кривой операционных характеристик приёмника (ROC AUC), измерив от 0 (в худшем случае) до 1 (в лучшем случае) со случайным прогнозом на уровне 0,5. Мы также можем построить указанную кривую, чтобы проанализировать модель.

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

from sklearn.ensemble import RandomForestClassifier # Создаём модель леса из сотни деревьев model = RandomForestClassifier(n_estimators=100, bootstrap = True, max_features = 'sqrt') # Обучаем на тренировочных данных model.fit(train, train_labels)

После нескольких минут обучения модель будет готова выдавать прогнозы для тестовых данных:

# Действующая классификация rf_predictions = model.predict(test) # Вероятности для каждого класса rf_probs = model.predict_proba(test)[:, 1]

Мы рассчитаем прогнозы классификации ( predict ) наряду с прогностической вероятностью ( predict_proba ), чтобы вычислить ROC AUC.

from sklearn.metrics import roc_auc_score # Рассчитываем roc auc roc_value = roc_auc_score(test_labels, rf_probs)

Результаты

Итоговое тестирование ROC AUC для случайного леса составило 0.87, в то время как для единичного дерева с неограниченной глубиной — 0.67. Если вернуться к результатам обработки тренировочных данных, обе модели покажут эффективность, равную 1.00 на ROC AUC. Этого и следовало ожидать, ведь мы предоставили готовые ответы и не ограничивали максимальную глубину каждого дерева.

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

Мы можем визуализовать кривую ROC для одиночного дерева (верхняя диаграмма) и для случайного леса в целом (нижняя диаграмма). Кривая лучшей модели стремится вверх и влево:

Случайный лес значительно превосходит по точности одиночное дерево.

Ещё один способ оценить эффективность построенной модели — матрица погрешностей для тестовых прогнозов.

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

Значимость параметра

Значимость параметра в случайном лесу — это суммарное уменьшение загрязнения Джини во всех узлах, использующих этот параметр для разделения. Мы можем использовать это значение для определения опытным путём, какие переменные более всего принимаются во внимание нашей моделью. Мы можем рассчитать значимость параметров в уже обученной модели и экспортировать результаты этих вычислений в Pandas DataFrame следующим образом:

import pandas as pd # Извлекаем значимость параметров fi = pd.DataFrame().\ sort_values('importance', ascending = False) # Выводим значения fi.head() feature importance DIFFWALK 0.036200 QLACTLM2 0.030694 EMPLOY1 0.024156 DIFFALON 0.022699 USEEQUIP 0.016922

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

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

Визуализация единичного дерева леса

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

Следующие шаги

Следующим шагом будет оптимизация случайного леса, которую можно выполнить через случайный поиск, используя RandomizedSearchCV в Scikit-Learn. Оптимизация подразумевает поиск лучших гиперпараметров для модели на текущем наборе данных. Лучшие гиперпараметры будут зависеть от набора данных, поэтому нам придётся проделывать оптимизацию (настройку модели) отдельно для каждого набора.

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

Реализацию случайного поиска для оптимизации модели можно изучить в Jupyter Notebook.

Полностью рабочий образец кода

Приведённый ниже код создан с помощью repl.it и представляет полностью рабочий пример создания алгоритма случайного леса на Python. Можете самостоятельно его запустить и попробовать поэкспериментировать, изменяя код (загрузка пакетов может занять некоторое время).

Заключение и выводы

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

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

В этой статье мы разобрали следующие ключевые концепции:

Дерево принятия решений: интуитивная модель, которая принимает решения на основе последовательности вопросов, относящихся к значениям параметров. Характеризуется низкой погрешностью и высокой вариативностью, что ведёт к переобучению на тренировочных данных.
Загрязнение Джини: величина, которую дерево решений стремится минимизировать при разделении каждого узла. Представляет возможность того, что случайно выбранный образец будет неверно классифицирован в определённом узле.
Бутстреппинг: выборка случайных наборов образцов с возмещением.
Случайный поднабор параметров: выборка случайных параметров для разделения каждого узла дерева решений.
Случайный лес: сборная модель из множества деревьев решений, использующая бутстреппинг, случайные поднаборы параметров и усреднение полученных от всех деревьев прогнозов. Является частным случаем сборной модели, использующей бэггинг.
Компромисс между вариативностью и погрешностью: ключевая проблема машинного обучения. Заключается в поиске баланса между моделями с высокой гибкостью (высокой вариативностью), которые отлично обучаются на тренировочных данных, но мало способны к обобщению на новых данных, и ригидными моделями (с высокой погрешностью), которые плохо обучаются на тренировочных сетах. Случайный лес уменьшает вариативность одиночного дерева решений, что позволяет модели лучше воспринимать новые данные.

Индекс Джини (Gini index)

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

Этот метод был разработан итальянским статистиком и демографом Коррадо Джини (1884–1965) и впервые опубликован в 1912 г. В настоящее время индекс Джини широко применяется в экономических, социальных и демографических исследованиях.

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

На рисунке показано распределение совокупного дохода страны в обществе. Диагональная прямая соответствует равномерному распределению дохода.

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

Индекс Джини численно равен отношению площади фигуры, образованной кривой Лоренца и кривой равенства (залитая область на рис.), к площади треугольника ABC. Очевидно, что он может принимать значения от 0 до 1 и будет отражать степень неравномерности распределения доходов в обществе.

В чем разница между Gini coefficient и Gini impurity

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

Есть коэффициент/индекс Джини (Gini coefficient), который используют при оценке качества классификации и регрессии. На русской странице Wiki не очень информативно, но вот на английской всё подробно: изначально это был статистический показатель степени расслоения общества данной страны или региона по отношению к какому-либо изучаемому признаку. Вычисляется как отношение площади фигуры, образованной кривой Лоренца и кривой равенства, к площади треугольника, образованного кривыми равенства и неравенства. Сейчас поясню.

Допустим, в компании работают 4 человека с суммарным доходом 8000$. Равномерное распределение дохода — это 2000$+2000$+2000$+2000$, неравномерное — 0$+0$+0$+8000$. А как оценить неравномерность, скажем, для случая 1000$+1000$+2000$+4000$? Упорядочим сотрудников по возрастанию дохода. Построим кривую (Лоренца) в координатах [процент населения, процент дохода этого населения] — идём по всем сотрудникам и откладывает точки. Для первого — [25%, 12.5%] — это сколько он составляет процентов от всего штата и сколько процентов составляет его доход, для первого и второго — [50%, 25%] — это сколько они составляют процентов и сколько процентов их доход, для первых трёх — [75%, 50%], для всех — [100%, 100%].

На. Рис. 1. построенная кривая Лоренца показана красным цветом. Кривая Лоренца, которая соответствует равномерному распределению дохода, — синяя диагональ (т.н. кривая равенства). Кривая Лоренца, которая соответствует неравномерному распределению, — зелёная (т.н. кривая неравенства). Вот площадь A, делённая на A+B=0.5, и есть коэффициент Gini.

При оценке качества классификации GINI = 2*AUCROC-1. Про AUCROC я уже как-то писал. Почему это они так связаны нигде подробно не описано. Я нашёл упоминание в работе Supervised Classification and AUC. Там всё логично: если в задаче классификации на два класса 0 и 1 интерпретировать эти числа как доходы. Но чтобы связь была именно GINI = 2*AUCROC-1, должно быть что-то типа рис. 2 (но ROC-кривая и кривая Лоренца это не одно и то же), кстати в презентации Credit Scoring and the Optimization concerning Area under the curve такая же картинка.

Есть ещё коэффициент/индекс Джини (Gini impurity), который используется в решающих деревьях при выборе расщепления. Я дал ссылку на английскую Wiki, поскольку русского аналога нет. Он тоже измеряет «равномерность», если p_i — частоты представителей разных классов в листе дерева, то коэффициент Джини для него равен

Только вот это другая равномерность, никак не связанная с рассмотренной ранее. Для первой нужно два показателя — доход и численность населения с таким доходом, а тут только проценты (частоты). В английской версии на странице Gini coefficient написано «не путать с Gini impurity» и наоборот.

Я не знаю, как лучше переводить impurity, скажем, С.П.Чистяков переводит как «загрязненность» (на мой взгляд, не очень звучит…).

Коррадо Джини (Corrado Gini, 1884), который всё это придумал был итальянским статистиком. Но кроме этого, он известный идеолог фашизмa, написал книгу «Научные основы фашизма». Прожил, кстати, довольно много — 80 лет, видимо, после войны не преследовался. Вот так бывает…

Критерии качества для построения решающих деревьев

На предыдущем занятии мы с вами познакомились с общей идеей логических методов. Здесь же продолжим эту тему и подробнее поговорим о бинарных решающих деревьях. Приведу пример такого дерева из предыдущего занятия:

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

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

с n признаками. Тогда, начиная с корневой вершины , проверяем предикат:

То есть, мы смотрим на j-й признак для вектора и сравниваем его с порогом . Если условие выполняется, идем по стрелке с отметкой 1, иначе – по стрелке с отметкой 0.

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

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

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

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

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

И, так как признак всего один, то . Остается найти только нужные пороги t.

Если бы разбиение делал я сам, то предложил бы следующее решающее дерево:

Почему именно так? В действительности, можно было бы придумать и другие варианты. Я руководствовался простым принципом: в каждой вершине порог t следует выбирать так, чтобы в одной части было как можно больше представителей только одного какого-либо класса (шаров одного цвета), а в другой – все оставшиеся. То есть, это некий критерий здравого смысла, естественная эвристика, которая сокращает глубину дерева. Но вы можете сказать, а зачем нам минимизировать глубину решающего дерева? Пусть оно получается таким, каким сделает его алгоритм. Например, будем поочередно перебирать пороги t от 0 до 19 и рано или поздно гарантированно разобьем последовательность шаров на красные и синие. Да, дерево будет значительно глубже, ну и что? Однако, здесь всегда следует помнить, что данная последовательность всего лишь обучающая выборка. Мы предполагаем использовать это дерево и для других подобных последовательностей с несколько другим распределением синих и красных шаров. Иначе, это была бы не задача машинного обучения, а просто разбиение конкретной выборки. Так вот, можно заметить, что чем меньше глубина решающего дерева, тем меньше используется порогов разбиения и тем выше, в среднем, обобщающая способность такого дерева. Именно поэтому стараются строить деревья минимальной глубины.

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

Если вернуться к моему варианту бинарного дерева, то, как я отмечал, в каждой промежуточной вершине старался порог t выбирать так, чтобы в одной части было как можно больше представителей одного класса (шаров одного цвета), а в другой как получится, т.е. все оставшиеся. Это некая эвристика. Наша цель, наделить алгоритм примерно такой же эвристикой. Как это сделать? Математики обратили свои взоры в ранние наработки самых разных формул и представили миру несколько критериев качества предикатов. Одним из популярных стала энтропия:

где — вероятность i-го класса; N – общее число классов (в нашем примере – цветов шаров). Известно, что эта величина является некой характеристикой хаотичности системы. Чем больше разнообразия, тем выше энтропия, и наоборот, чем больше порядка, тем она меньше. Ее можно естественным образом использовать для оценки характеристики текущего разбиения каждой вершины. Например:

Такую характеристику в решающих деревьях называют impurity (информативностью). Чем она меньше, тем лучше (качественнее) набор данных в вершине. И, наоборот, чем она больше, тем разнообразнее (хаотичнее) данные в вершине.

Вернемся, теперь, к примеру разбиения последовательности красных и синих шаров. Последовательность состоит из N=2 классов с вероятностями появления каждого из них:

Следовательно, impurity (в данном случае энтропия) корневой вершины дерева, равна:

Далее, мы выбираем предикат с порогом t = 12:

и получаем две подвыборки с impurity (энтропиями):

Величина 0,6 значительно меньше начального значения 0,993, а значит, во второй последовательности больше порядка, чем в исходной. И это очень хорошо. Именно этого мы и добиваемся, выбирая порог t.

Теперь, нам нужно на основе величин сформировать единый критерий (одно число), по которому мы бы судили о качестве разбиения выборки на две подвыборки. Это также можно выполнить различными способами, но часто используется следующая формула под названием информационный выигрыш (information gain):

где — число групп (подвыборок) после разбиения; — число элементов в i-й группе после разбиения; Q – критерий разбиения (предикат). Для нашего примера оценки качества разбиения корневой вершины с порогом t=12, имеем:

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

Математически поиск наилучшего предиката в текущей вершине дерева, можно записать так:

Или, в общем случае, учитывая, что мы подбираем не только пороги, но и признаки , по которым делятся объекты на две подвыборки, имеем:

А в качестве impurity, помимо энтропии также используют:

критерий Джини (Gini impurity): , здесь — вероятность (частота) появления объектов k-го класса в вершине дерева;
ошибка классификации (misclassification error): .

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