Интервью по машинному обучению хорошей памяти - дерево решений

машинное обучение

1. Что такое дерево решений

1.1 Основная идея дерева решений

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

image

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

1.2 Процесс роста «дерева»

Дерево решений принимает решения на основе структуры «дерева».На данный момент мы столкнемся с двумя проблемами:

  • Как растет «дерево».
  • Когда это "дерево" перестанет расти?

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

Когда это "дерево" перестанет расти?

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

1.3 Как растет «дерево»

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

Мы можем абстрагироваться от выбора масс, что вводит понятие чистоты.Подумайте и об этом.Выбор масс означает более высокую чистоту. Ну, если немного глубже, это включает в себя предложение:Чем ниже информационная энтропия, тем выше чистота. Я полагаю, что все слышали о понятии "энтропия" более или менее. В общем, информационная энтропия используется для измерения "количества содержащейся информации". Если атрибуты образцов одинаковы, это заставит людей почувствовать, что это содержит Информация очень разовая, и нет никакой дифференциации.Наоборот, атрибуты образцов разные, поэтому количество содержащейся информации много.

Как только я попадаю сюда, у меня начинает болеть голова, потому что вот-вот введут формулу информационной энтропии, которая на самом деле очень проста:

Ent(D)=-\sum_{k=1}^{|y|}p_klog_2p_k

Pk представляет: доля выборок k-го класса в текущем наборе выборок D равна Pk.

получение информации

Без лишних слов переходим непосредственно к формуле:

image

Меня не волнует, если вы этого не понимаете.Простое предложение: информационная энтропия до деления — информационная энтропия после деления. Указывает на «шаг» в направлении чистоты.

Что ж, с предыдущими знаниями мы можем начать рост «дерева».

1.3.1 Алгоритм ID3

Объяснение: Рассчитайте информационную энтропию в корневом узле, а затем разделите и рассчитайте информационную энтропию его узлов по очереди в соответствии с атрибутами.Используйте информационную энтропию корневого узла -- информационная энтропия узла атрибута = прирост информации, и сортировать их в порядке убывания в соответствии с приростом информации.Это первый атрибут деления и т. д., который дает форму дерева решений, то есть, насколько оно «длинное».

Если вы не понимаете, вы можете проверить примеры изображений, которыми я поделился, в сочетании с тем, что я сказал, вы можете понять:

  1. Первая картинка.jpg
  2. Вторая картинка.jpg
  3. Третья картинка.jpg
  4. Четвертая картинка.jpg

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

1.3.2 C4.5

Для решения проблемы прироста информации вводится коэффициент прироста информации:

Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}

в:

IV(a)=-\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}

Чем больше количество возможных значений атрибута а (т. е. больше V), тем больше значение IV(а). **Сущность коэффициента прироста информации: это штрафной параметр, умноженный на основе прироста информации. Когда число признаков велико, параметр штрафа мал, когда число признаков мало, параметр штрафа велик. ** Есть один недостаток:

  • Недостаток: скорость получения информации смещена в сторону функций с меньшим количеством значений.

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

1.3.3 Алгоритм CART

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

Gini(D)=\sum_{k=1}^{|y|}\sum_{k_{'}\neq k}p_{k}p_{k^{'}}=1-\sum_{k=1}^{|y|}{p_k}^2

Представляет вероятность того, что случайно выбранная выборка в наборе выборок будет неправильно классифицирована. Например, если сейчас в мешке несколько шаров 3-х цветов, если вы протянете руку и вытащите 2 шара, то вероятность того, что цвета разные, вы теперь понимаете.Чем меньше Джини(D), тем выше чистота набора данных D.

Например

Если предположить наличие признака «образование», то этот признак имеет три значения признака: «бакалавриат», «магистр», «доктор»,

При использовании признака «образовательного образования» для разделения выборки D существует три значения деления, поэтому есть три возможных множества деления, а разделенные подмножества следующие:

1. Пункт разделения: «Бакалавриат», подмножество после раздела: {Бакалавриат}, {Магистр, доктор философии}

2. Точка деления: «Магистр», подмножество после деления: {магистр}, {бакалавриат, доктор философии}

3. Точка деления: «Магистр», подмножество после деления: {доктор философии}, {бакалавриат, магистр}}

Для каждого из вышеперечисленных подразделений она может быть рассчитана на основеРазделить функцию = некоторое значение функцииЧистота разделения выборки D на два подмножества:

Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_2)+\frac{|D_2|}{|D|}Gini(D_2)

таким образомДля признака с несколькими значениями (более 2) необходимо вычислить чистоту Gini(D, Ai) подмножества после деления выборки D с каждым значением в качестве точки разделения (где Ai представляет возможность значение функции А)

Затем найдите деление с наименьшим индексом Джини из всех возможных делений Джини (D, Ai).Точка деления этого деления является наилучшей точкой деления для использования признака A для разделения выборки D. В этот момент оно может вырасти в «большое дерево».

1.3.4 Три разных дерева решений

  • ID3: Атрибуты со многими значениями облегчают очистку данных, а их прирост информации больше.

    Результат обучения — огромное и неглубокое дерево: неразумно.

  • C4.5: Используйте скорость прироста информации вместо прироста информации.

  • CART: Замените энтропию коэффициентом Джини, чтобы минимизировать примеси, а не максимизировать прирост информации.

2. Почему древовидная структура не нуждается в нормализации?

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

Поскольку древовидные структуры (такие как деревья решений, RF) не нуждаются в нормализации, то почему не-древовидные структуры, такие как Adaboost, SVM, LR, Knn, KMeans и им подобные, нуждаются в нормализации.

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

3. Разница между деревом решений классификации и деревом решений регрессии

Дерево классификации и регрессии (CART) — это тип дерева решений. Алгоритм CART можно использовать для создания дерева классификации или дерева регрессии. Процесс построения дерева немного отличается.

дерево регрессии:

Дерево регрессии CART предполагает, что дерево является бинарным деревом и непрерывно делит функции. Например, текущий узел дерева разбивается на основе j-го собственного значения, и выборки с собственным значением меньше s делятся на левое поддерево, а выборки больше s делятся на правое поддерево.

R_1(j,s)=\{x|x^{(j)}\leq s\} and R_2(j,s)=\{x|x^{(j)}>s\}

Дерево регрессии CART по существу делит выборочное пространство в измерении признаков, и оптимизация этого деления пространства является NP-трудной задачей, поэтому в модели дерева решений для ее решения используется эвристический метод. Целевая функция, созданная типичным деревом регрессии CART:

\sum_{x_i\in R_m}(y_i-f(x_i))^2

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

min_{j,s}[min_{c_1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c_2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]

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

Справочная статья:Подробное объяснение классических алгоритмов: дерево решений классификации CART, дерево регрессии и дерево модели.

4. Как обрезать дерево решений

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

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

Справочная статья:Дерево решений и создание дерева решений и обрезка

5. Реализация кода

Гитхаб:GitHub.com/NLP-love/ml…

【Машинное обучение легко понять серия статей】

3.png

автор:@mantchs

Гитхаб:GitHub.com/NLP-love/ml…

Приглашаются все желающие присоединиться к обсуждению! Улучшайте этот проект вместе! Номер группы: [541954936]NLP面试学习群

Категории