Дерево решений – это самый мощный и популярный инструмент для классификации и прогнозирования. Дерево решений представляет собой структуру, похожую на блок-схему.
ЭНТРОПИЯ
Концепция дерева решений заключается в том, что оно помогает выбрать подходящие функции для разделения дерева на части, а алгоритм, используемый для разделения, — ID3. Если построено дерево решений правильно, то глубина дерева будет меньше или больше. Для эффективного построения дерева решений мы используем концепцию энтропии.
Энтропия помогает нам построить соответствующее дерево решений для выбора лучшего сплиттера. Энтропию можно определить как меру чистоты разделения. Энтропия всегда лежит в пределах от 0 до 1.
Математическая формула энтропии выглядит следующим образом:
Здесь b — это основание, которое мы обычно принимаем равным 2 или e(euler no) = 2,718. Обычно мы используем основание 2.
Логарифм по основанию 2 обычно записывается как lg, а по основанию e — как ln.
Энтропия. Иногда также обозначается буквой «H».
Где «Pi» — это просто вероятность класса «i» в наших данных. Для простоты предположим, что у нас есть два класса: положительный класс и отрицательный класс. Поэтому «i» здесь может быть либо +, либо (-).
Итак, если у нас есть в общей сложности 10 точек, из которых 3 положительные и 7 отрицательные, то энтропия будет-
Свойства энтропии
Теперь мы рассмотрим некоторые важные свойства энтропии, мы увидим это в случае 2 классов, скажем, Y , ), однако они будут справедливы и в мультиклассовой настройке: → (𝑌 + 𝑌 - Давайте посмотрим, как значение энтропия изменяется с изменением распределения данных.
- случай 1: скажем, в нашем наборе данных D, 99% и 1%. В этом случае энтропия 𝑌 + → 𝑌 −→ H(Y) = -0,99 * lg 0,99–0,01 * lg 0,01 = 0,0801
2. случай 2: скажем, в нашем наборе данных D, 50% и 50%. В этом случае энтропия 𝑌 + → 𝑌 −→ H(Y) = -0,5 * lg 0,5–0,5 * lg 0,5 = 1
3. случай 3: скажем, в нашем наборе данных D, 0% и 100%. В этом случае энтропия H(Y) = 0
ПОЛУЧЕНИЕ ИНФОРМАЦИИ (IG)
Здесь мы хотим разделить набор данных или разделить наш набор данных D. Рассматривая внешний вид функции, мы увидели, что он может иметь три значения: солнечно, пасмурно и дождливо. Мы разделим набор данных D на основе этих категорий.
Как вы можете видеть на изображении выше, у нас есть три набора: первый набор 𝐷 1 имеет прогноз = солнечно, второй набор 𝐷 2 имеет прогноз = пасмурно, а третий набор 𝐷 3 имеет прогноз = дождливо. Теперь давайте рассчитаем значение энтропии в узле прогноза на основе целевой переменной Y. По сути, мы хотим вычислить энтропию на основе цели. Ранее мы рассчитали энтропию в узле прогноза (Y) = 0,94.
Теперь мы рассчитаем энтропию для каждого из разделенных наборов данных. 𝐷1 = 𝐻 (Y) = 0,97, 𝐷2 = 𝐻 (Y) = 0, 𝐷3 = 𝐻 (Y) = 0,97
Всего D имеет 14 точек данных. После разделения имеет 5 точек данных, имеет 4 точки данных, имеет 5 𝐷 1 𝐷 2 𝐷 3 точки данных.
Теперь прирост информации после разделения по отношению к прогнозу для цели Y равен:
IG(Y, прогноз) = 0,94 — (5/14*0,97 + 4/14*0 + 5/14*0,97)
(5/14*0,97 + 4/14*0 + 5/14*0,97) => это средневзвешенное значение энтропии по количеству точек данных в каждом наборе.
Итак, для нашего набора данных D прирост информации после разделения данных на , можно записать как
Затем информационный прирост по отношению к этому набору данных можно записать как:
Information_Gain = [Энтропия (родительский)] — [Средневзвешенная энтропия дочерних узлов
РАЗЛИЧИЕ KL
Дивергенция Кульбака-Лейблера: Дивергенция KL является мерой относительной разницы между двумя распределениями вероятностей для данной случайной величины или набора событий. Дивергенция KL также известна как относительная энтропия. Его можно рассчитать по следующей формуле:
Разница между кросс-энтропией и KL-дивергенцией заключается в том, что кросс-энтропия вычисляет общие распределения, необходимые для представления события, из распределения q вместо p, в то время как KL-дивергенция представляет собой дополнительное количество бит, необходимое для представления события из распределения. д вместо п.
Свойства KL-дивергенции:
- D(p || q) всегда больше или равно 0.
- D(p || q) не равно D(q || p). KL-дивергенция не коммуникативна.
- Если p=q, то D(p || q) равно 0
Примесь Джини
Здесь мы поговорим о примеси Джини, которая похожа на энтропию, но имеет перед ней определенные преимущества. Он представлен как (Y)
Примесь Джини для случайной величины Y, которая разбита на k наборов, скажем, , , … , есть
Сравним с энтропией. Скажем, у нас есть случайная величина Y с двумя классами. 𝑌+, 𝑌−
Случай 1: P(𝑌+) = 0,5, P(𝑌−) = 0,5, тогда 𝐼𝐺 (Y) = 1 — (0,25 + 0,25) = 0,5, H(Y) = 1
Случай 1: P(𝑌+) = 1, P(𝑌−) = 0, тогда 𝐼 𝐺 (Y) = 1 — (1 + 0) = 0, H(Y) = 0
ПОСТРОЕНИЕ ДЕРЕВА РЕШЕНИЙ
- Мы знаем об энтропии, приросте информации и примеси Джини. Давайте теперь применим их и построим дерево решений. Мы строим деревья решений, используя подход «сверху вниз», т. е. мы начинаем с набора данных в целом, а затем разбиваем их на фрагменты.
- Здесь мы будем использовать теннисный набор данных D, который имеет 9 положительных и 5 отрицательных точек данных. Таким образом, энтропия всего набора данных до разделения равна (Y) = 0,94.
- Теперь для разделения мы берем все функции одну за другой и вычисляем прирост информации.
- Скажем, сначала мы разделяем наш набор данных D с помощью Outlook и вычисляем взвешенную энтропию для этого разделенного набора данных, которая равна 0,69. Таким образом, прирост информации составляет 0,94–0,69 = 0,25. Итак, IG (Y, прогноз) = 0,25.
- Прямо сейчас мы находим разделение для корневого узла. Итак, что мы, по сути, делаем, так это вычисляем прирост информации для всех признаков, а затем выбираем тот признак, который имеет максимальный прирост информации.
- После расчета прироста информации для всех функций относительно D мы обнаруживаем, что прогноз имеет максимальный прирост информации. Таким образом, он становится корнем дерева, как показано на изображении выше. После разделения набора данных D с помощью Outlook получается три разных набора данных, скажем, и . 𝐷 1 𝐷 2 𝐷 3.
- 𝐷1 содержит 2 положительные точки и 3 отрицательные точки, 𝐷2 содержит 4 положительные точки и 0 отрицательных точек 𝐷3 и содержит 2 положительные точки и 3 отрицательные точки. Теперь мы видим, что содержит 𝐷2 только положительные точки. Такой узел называется чистым узлом, и мы не разделяем чистые узлы.
- Снова мы можем сломать 𝐷1, используя влажность, в результате получится два чистых узла. Точно так же 𝐷3 можно разделить с помощью ветра, что приведет к двум чистым узлам. Итак, по сути, мы рекурсивно разбиваем каждый узел на дочерние узлы, используя прирост информации в качестве критерия.
Теперь, когда мы должны прекратить дальнейшее разбиение узла:
- Чистый узел — мы прекращаем выращивать наше дерево, когда у нас есть чистый узел, потому что нет смысла разбивать наш узел после него.
- Мы также останавливаем разбиение, если в узле очень мало точек. Скажем, у нас есть набор данных из 10 тысяч точек, и в одном из узлов у нас есть только 2 точки — 1 положительная и другая отрицательная. Теперь, если мы разделим этот узел, мы уступим место важности одной точке данных. Эта точка данных может быть выбросом. Таким образом, мы будем переобуваться.
- Мы также прекращаем выращивать наше дерево за пределами определенной глубины, потому что по мере увеличения глубины остается все меньше и меньше точек данных. Если мы подходим к этим точкам, то мы переоснащаемся. Таким образом, в общем случае, если глубина велика, мы переоснащаемся, а если глубина мала, мы недообучаемся. глубина — это гиперпараметр, который мы находим, используя стандартные методы, такие как перекрестная проверка.
Перспективы
H(Солнечно)=-(2/5)log(2/5)-(3/5)log(3/5)=0,97
H(пасмурно)=-(4/4)log(4/4)- (0/4)log(0/4)=0
H (прогноз) = — (3/5) log (3/5) - (2/5) log (2/5) = 0,97.
Взвешенная энтропия = (5/14) * H (солнечно) + (4/14) * H (пасмурно) + (5/14) * H (дождь)
=(5/14)*0.97 + (4/14)*0 + (5/14)*0.97=0.69
Прирост информации = исходная энтропия — взвешенная энтропия
Прирост информации = 0,94–0,69 = 0,25
Температура
H(Горячий)=-(2/4)log(2/4)- (2/4)log(2/4)= 1
H(мягкая)=-(4/6)log(2/6)-(2/6)log(2/6)= 0,918
H(Холод)= — (3/4)log(3/4)-(1/4)log(1/4) =0,811
Взвешенная энтропия = (4/14) * H (высокая) + (6/14) * H (слабая) + (4/14) * H (низкая)
=(4/14)*1 + (5/14)*0.918 + (4/14)*0.811=0.9108
Прирост информации = исходная энтропия — взвешенная энтропия
Прирост информации = 0,94–0,9108 = 0,029
Влажность
H(Горячий) = -(3/7)log(3/7)- (4/7)log(4/7) = 0,98
H(мягкая) = -(6/7)log(6/7)- (1/7)log(1/7) = 0,918
Взвешенная энтропия = (7/14)*H(высокий)+ (7/14)*H(низкий)
=(1/2)*0.98 + (1/2)*0.918 = 0.787
Прирост информации = исходная энтропия — взвешенная энтропия
Прирост информации = 0,94–0,788 = 0,153
Ветрено
H(слабый) = -(3/6)log(3/6)- (3/6)log(3/6) = 0,811
H(Сильный) = -(6/8)log(6/8)- (2/8)log(2/8) = 1
Взвешенная энтропия = (8/14) * H (слабая) + (6/14) * H (сильная)
= (8/14)*0.811 + (6/14)*1=0.891
Прирост информации = исходная энтропия — взвешенная энтропия
Прирост информации = 0,94–0,891 = 0,049
Прирост информации Outlook выше, поэтому мы выбираем Outlook в качестве нашего корневого узла.
Разделение числовых признаков
Как мы работаем с числовыми функциями?
Числовые признаки носят непрерывный характер, и их нельзя рассматривать так же, как категориальные признаки. Скажем, у категориального признака было 3 категории, затем мы разделили его на три дочерних узла, но числовой признак может иметь бесчисленное множество уникальных значений.
Учтите, что 𝑓1 — это числовая характеристика со значениями, как показано на изображении выше. Теперь мы можем отсортировать значения в порядке возрастания. После сортировки мы можем выбрать значение, скажем, 2,6 из этого столбца и создать правило, согласно которому все строки, имеющие значения меньше этого порога, перейдут в левую ветвь, а в противном случае - в правую ветвь. Если в наборе данных n строк, то существует не более n различных возможностей для этого порога.
Мы берем каждое значение из столбца числовых характеристик, используем его в качестве порога и вычисляем прирост информации. Среди всех расщеплений выбираем тот, который вызвал максимальный прирост информации. Это занимает очень много времени. Также нам необходимо сравнить прирост информации с другими характеристиками прироста информации.
Стандартизируем ли мы данные в деревьях решений?
Такие алгоритмы, как логистическая регрессия, SVM, KNN, — это алгоритмы, основанные на расстоянии, поэтому стандартизация функций была очень важна для их правильной работы. Теперь деревья решений не являются методом, основанным на расстоянии. Так что стандартизация функций не важна.
Когда мы имели дело с числовыми признаками, мы сортировали столбец и выбирали пороговое значение. Таким образом, имел значение только порядок данных.
Категориальные признаки со многими возможными значениями
Предположим, в нашем наборе данных у нас есть такая функция, как PINCODE/ZIPCODE. Теперь он может содержать 1000 различных значений. С ним нельзя обращаться как с числовыми функциями, потому что мы не можем на самом деле сравнивать два ПИН-КОДА. Если мы относимся к нему как к категориальному признаку, нам нужно разделить его на различные категории, число категорий теперь может исчисляться тысячами. Каждое разделение не может содержать много точек данных. Это может быть проблематично.
Чтобы справиться с этой проблемой, мы используем технический прием, который хорошо работает на практике. По сути, мы преобразуем наши категориальные данные в числовые данные. Скажем, строка имеет PINCODE = 𝑃𝑗 и метка класса = 1, тогда нам 𝑦𝑖 нужно вычислить вероятность P(𝑦𝑖 = 1 |𝑃𝑗 ), тогда мы можем заменить PINCODE на это значение вероятности 𝑃𝑗.
Переоснащение и недообучение
Теперь давайте поговорим о случаях, когда наша модель может не соответствовать или переобучать.
Предположим, у нас есть дерево с большой глубиной, тогда может случиться так, что листовые узлы будут содержать очень мало точек. Эти точки могут быть шумными точками. Итак, в некотором смысле мы переобучаем нашу модель. Также интерпретируемость модели снижается по мере увеличения глубины дерева.
Дерево также может иметь очень маленькую глубину. Рассмотрим дерево, указанное на изображении выше, его высота равна 1. Дерево решений с высотой = 1 называется пнем решений. Скажем, у нас есть набор данных D с 200 точками, из которых 100 положительных и 100 отрицательных. Теперь мы делаем разделение на два узла, один из которых содержит 70 положительных и 30 отрицательных, а другой — 30 положительных и 70 отрицательных. Теперь оба они не являются чистыми узлами. Чтобы сделать прогноз, мы берем большинство голосов. Итак, в каком-то смысле мы недообучаемся, потому что дерево содержит очень мало узлов решений, а также нет чистых узлов.
Таким образом, если глубина слишком велика, мы переоснащаемся, а если глубина мала, мы недообучаемся. Теперь попробуем понять, что означает иметь большую или маленькую глубину геометрически. Дерево с малой глубиной по существу означает, что узлов решений очень мало. Поскольку мы знаем, что узлы принятия решений представляют собой все оси, параллельные гиперплоскостям.
Если этих гиперплоскостей очень мало, то расщепления пространства решений не так много, как показано на изображении выше. По существу, вызывая недооснащение. Если дерево имеет большую глубину, то в пространстве решений много гиперплоскостей. В результате получаются очень маленькие гиперкубоиды. По сути, вызывает переоснащение.
Сложность обучения и выполнения
Сложность времени обучения для деревьев решений составляет O (nlgn * d),
где n = # точек данных в поезде, d = # размерность.
Часть nlgn существует из-за сортировки, необходимой для функций, чтобы выбрать порог. d представляет собой количество измерений, т. е. отсутствие признаков в наборе данных.
Сложность пространства времени выполнения равна O (узлы), где узлы = #узлы
Во время выполнения нам нужно дерево в памяти для прогнозирования значений. Теперь хранение дерева решений не занимает много места. Поскольку нам нужно только хранить все узлы, то есть внутренние узлы и конечные узлы.
Сложность времени выполнения равна O(depth) , где depth = глубина дерева. Во время выполнения нам просто нужно передать нашу точку запроса через дерево решений, чтобы получить результат.
Таким образом, деревья решений чрезвычайно полезны, когда у нас есть большие объемы данных, размерность мала и т. д. Также это чрезвычайно полезно в тех случаях, когда нам требуется низкая задержка. Поскольку сложность времени выполнения была всего O (глубина).
Регрессия с использованием деревьев решений
Деревья решений также можно использовать для задач регрессии. Фактически, они очень хорошо работают для задач регрессии. В задачах классификации мы использовали прирост информации в качестве критериев, в задачах регрессии мы использовали среднеквадратичную ошибку (MSE) или медианную абсолютную ошибку (MAE) в качестве наших критериев.
Предположим, у нас есть набор данных D с функциями 𝑓1 и 𝑓2 с целевой переменной y ϵ R, теперь mse набора данных D можно рассчитать как
Теперь предположим, что мы разделили наш набор данных на 𝐷1 и 𝐷2 , поэтому мы вычислим mse для обоих этих наборов данных и возьмем их взвешенную сумму, как мы это делали в классификации, а затем возьмем разницу между взвешенной mse родительских узлов и дочерних узлов.
Мы делаем это для всех функций, и в зависимости от того, какая функция больше всего снижает нашу mse, мы выбираем эту функцию точно так же, как мы делали с получением информации.
Итак, как и в классификации, мы выбираем признаки, которые больше всего уменьшают нашу энтропию. Точно так же в регрессии мы выбираем функцию, которая больше всего снижает MSE, обе они имеют наименьшее значение 0. Мы также можем использовать MAE вместо среднего, MAE также устойчив к выбросам.
СЛУЧАИ
- Несбалансированные данные. На деревья решений сильно влияют несбалансированные данные. Это влияет, потому что на расчет энтропии или расчет mse влияет набор данных дисбаланса. Нам нужно предотвратить это либо с помощью передискретизации, либо с недостаточной выборкой.
- Большое «d»: если количество измерений увеличивается, то при каждом разбиении нам необходимо учитывать большое количество признаков и рассчитывать их информационный прирост/mse. Это может значительно увеличить время обучения. В деревьях решений мы обычно избегаем выполнения One Hot Encoding (OHE) категориальных функций, если категорий нет, потому что это значительно увеличивает количество рассматриваемых функций, что приводит к увеличению времени обучения.
- Матрица подобия: деревья решений не могут работать с матрицами подобия, потому что им явно нужны функции для вычисления энтропии/mse.
- Мультиклассовая классификация: деревья решений могут естественным образом обрабатывать мультиклассовую классификацию, нам не нужна одна, а не другие методы. Наши критерии, то есть mse/энтропия, применимы к случайным переменным, имеющим более двух возможных значений. Таким образом, их можно эффективно использовать для задач классификации нескольких классов.
- Поверхности решений: деревья решений создают нелинейные поверхности решений. Как мы видели ранее, он создает параллельные оси гиперплоскости, по существу разбивающие все пространство на гиперкубы и гиперкубоиды.
- Взаимодействие функций: деревья решений имеют встроенный механизм взаимодействия функций. Скажем, у нас есть дерево, как показано на изображении выше. Теперь, чтобы достичь крайнего левого листа, нам нужна точка запроса, которая имеет PL ‹ 3 и SL > 5. Теперь эти две функции PL и SL вместе создают взаимодействие для прогнозирования запроса. Это было невозможно в таких методах, как логистическая регрессия, где нам нужно было вручную преобразовывать признаки.
- Выбросы: выбросы могут повлиять на деревья решений, особенно если у нас есть дерево большой глубины. Деревья большой глубины могут подходить к выбросам, что делает его неустойчивым.
- Интерпретируемость: деревья решений легко интерпретируются, если глубина разумна. Все в дереве решений может быть записано в виде вложенных операторов if else. Если глубина дерева увеличивается, интерпретируемость уменьшается.
- Важность функции: важность функции можно легко рассчитать в деревьях решений. Наиболее важными функциями будут те, которые вызывают наибольшее снижение энтропии/примеси Джини. Библиотеки, такие как sklearn, используют аналогичную технику для расчета важности функций. Он поддерживает словарь для каждой функции и вычисляет общее сокращение, вызванное функцией в дереве.
