Деревья и алгоритмы их обработки

Добавил пользователь Владимир З.
Обновлено: 19.09.2024

Презентация на тему: " 24.09.2008Деревья1 Структуры и алгоритмы обработки данных, 1 Лекция 5 ДЕРЕВЬЯ 1.Определения дерева, леса, бинарного дерева. Скобочное представление 2.Спецификация." — Транскрипт:

1 Деревья1 Структуры и алгоритмы обработки данных, 1 Лекция 5 ДЕРЕВЬЯ 1.Определения дерева, леса, бинарного дерева. Скобочное представление 2.Спецификация дерева, леса, бинарного дерева 3.Естественное соответствие бинарного дерева и леса 4.Обходы бинарных деревьев и леса

3 Деревья3 a dbc hjfg k ei Дерево – конечное множество Т, состоящее из одного или более узлов, таких, что а) имеется один специально обозначенный узел, называемый корнем данного дерева; б) остальные узлы (исключая корень) содержатся в m 0 попарно не пересекающихся множествах Т 1, Т 2. Т m, каждое из которых, в свою очередь, является деревом. Деревья Т 1, Т 2. Т m называются поддеревьями данного дерева. Определение (рекурсивное)

4 Деревья4 Дерево T = (корень, T 1, T 2, …, T m ) Терминология: узел, лист, отец, сын, брат, предок, потомок Уровень узла (рекурсивно): 1)корень имеет уровень 1; 2)другие узлы имеют уровень, на единицу больший их уровня в содержащем их поддереве этого корня. где T i – поддерево корня дерева T, такое, что a T i. a dbc hjfg k ei

7 Деревья7 Скобочное представление дерева и леса: ::= пусто |, ::= ( ). ( 0 a ( 1 b ( 2 i 2 ) ( 2 j 2 ) 1 ) ( 1 c ( 2 h 2 ) 1 ) ( 1 d ( 2 e 2 ) ( 2 f ( 3 k 3 ) 2 ) ( 2 g 2 ) 1 ) 0 ) a dbc hjfg k ei

8 Деревья8 Бинарные деревья Бинарное дерево конечное множество узлов, которое либо пусто, либо состоит из корня и двух непересекающихся бинарных деревьев, называемых правым поддеревом и левым поддеревом. a b a b (a (b ) ) ( a (b )) Скобочное представление бинарного дерева (БД): ::= |, ::=, ::= ( ).

9 Деревья9 (a (b (d Λ (h Λ Λ)) (e Λ Λ)) (c (f (i Λ Λ) (j Λ Λ)) (g Λ (k (l Λ Λ) Λ)))) Правила упрощения скобочной записи БД : 1. ( ) ( ), 2. ( ) ( ) (a (b (d (h)) (e)) (c (f (i) (j)) (g (k (l))))) a cb fd h e j g ik l

10 Деревья10 2. Спецификация дерева, леса, бинарного дерева Tree of α = Tree (α) Tree (α) ::= ( Корень(α), Forest (α) ) Forest (α) ::= L_list (Tree (α)) Базовые операцииАксиомы 1) Root: Tree α; 2) Listing: Tree Forest; 3) ConsTree: α Forest Tree А 1 ) Root (ConsTree (u, f)) = u; А 2 ) Listing (ConsTree (u, f)) = f; А 3 ) ConsTree (Root (t), Listing (t)) = t, ( u: α; f: Forest (α); t: Tree (α))

11 Деревья11 Функциональная спецификация структуры данных бинарного дерева BinaryTree (α) BT (α) Базовые функцииАксиомы 1) Root: NonNullBT α; 2) Left: NonNullBT BT; 3) Right: NonNullBT BT; 4) ConsBT: α BT BT NonNullBT; 5) Null: BT Boolean; 6) : BT A 1 ) Null ( ) = true; A 1 ') Null (b) = false; A 2 ) Null (ConsBT (u, b1, b2)) = false; A 3 ) Root (ConsBT (u, b1, b2)) = u; A 4 ) Left (ConsBT (u, b1, b2)) = b1; A 5 ) Right (ConsBT (u, b1, b2)) = b2; A 6 ) ConsBT (Root (b), Left (b), Right (b)) = b ( u: α, b: NonNullBT (α), b1, b2: BT (α))

12 Деревья12 Естественное соответствие бинарного дерева и леса Представление леса бинарным деревом: Пусть лес F типа Forest задан как список деревьев T i типа Tree (для i 1..m): F = (Т 1 Т 2. Т m ). Head (F) = Т 1 Tail (F) = (Т 2. Т m ). Head (F) = (Root (Head (F)), Listing (Head (F)) Лес F = совокупность трех частей: 1) корня первого дерева Root (Head (F)), 2) леса поддеревьев первого дерева Listing (Head (F)), 3) леса остальных деревьев Tail (F).

13 Деревья13 … Т1Т1 Т2Т2 Т3Т3 ТmТm лес F = (Т 1 Т 2. Т m ). БД(F)

14 Деревья14 = B(F) B(T 1 \r 1 ) r1r1 B(T 2 \r 2 ) B(T 3 \r 3 ) B(T m \r m ) r2r2 r3r3 rmrm r i = Root(T i )

15 Деревья15 Бинарное дерево B (F), представляющее лес F: B (F) if Null (F) then else ConsBT (Root (Head (F)), B (Listing (Head (F))), B (Tail (F))).

18 Деревья18 procedure обходКЛП (b: BTree); begin if not Null (b) then begin посетить (Root (b)); обходКЛП (Left (b)); обходКЛП (Right (b)); end end ; 4. Обходы бинарных деревьев и леса Обходы БД

19 Деревья19 procedure обходЛКП (b: BTree);procedure обходЛПК (b: BTree); begin if not Null (b) then begin обходЛКП (Left (b)); обходЛПК (Left (b)); посетить (Root (b)); обходЛПК (Right (b)); обходЛКП (Right (b)); посетить ( Root (b)); end end;end

20 Деревья20 Варианты терминологии 1) КЛП, ЛКП, ЛПК [14]; 2) прямой, обратный, концевой [10]; 3) прямой, симметричный, обратный [13]; 4) сверху вниз, слева направо, снизу вверх [5], [6]; 5) префиксный (PreOrder), инфиксный (InOrder), постфиксный (PostOrder) [5], [6].

21 Деревья21 Обход бинарного дерева, представляющего арифметическое выражение с бинарными операциями Арифметическое выражение (a + b) * c d / (e + f * g) – */ +c ba d+ *e fg 1) КЛП префиксная запись: * + a b c / d + e * f g ; 2) ЛКП инфиксная запись (без скобок): a + b * c d / e + f * g ; 3) ЛПК постфиксная запись: a b + c * d e f g * + /.

22 Деревья22 Обходы леса Прямой порядок: а) посетить корень первого дерева; б) пройти поддеревья первого дерева (в прямом порядке); в) пройти оставшиеся деревья леса (в прямом порядке). procedure PreOrder (F: Forest); begin if not Null (F) then begin посетить (Root (Head (F)); PreOrder (Listing (Head (F))); PreOrder (Tail (F)); end end

23 Деревья23 … Т1Т1 Т2Т2 Т3Т3 ТmТm лес F = (Т 1 Т 2. Т m ). БД(F) Соответствие обходов леса и бинарного дерева

24 Деревья24 Обратный порядок: а) пройти поддеревья первого дерева (в обратном порядке) Listing (Head (F)) ; б) посетить корень первого дерева Root (Head (F)) ; в) пройти оставшиеся деревья (в обратном порядке) Tail (F). Концевой порядок: а) пройти поддеревья первого дерева (в концевом порядке) Listing (Head (F)) ; б) пройти оставшиеся деревья (в концевом порядке) Tail (F) ; в) посетить корень первого дерева Root (Head (F)).

25 Деревья25 Примеры a b c d e f g h i j k l m n a d b e g c j c f j c h i k i l m n Лес: БД:

26 Деревья26 КЛП a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) КЛП: a d e j k f l b g h c i m n (a (d (e (j (k)) (f (l)) (b (g (h)) (c (i (m (n))))))

27 Деревья27 Замечания 1.Обход в глубину 2.Порядок престолонаследования (см. также - Агата Кристи)

28 Деревья28 ЛКП a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) ЛКП: d j k e l f a g h b m n i c (a (d (e (j (k)) (f (l)) (b (g (h)) (c (i (m (n))))))

29 Деревья29 Замечания 1.Обход БД слева направо 2.Обход в лесу – снизу вверх

30 Деревья30 ЛПК a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) ЛПК: k j l f e d h g n m i c b a (a (d (e (j (k)) (f (l)) (b (g (h)) (c (i (m (n))))))

Двоичное дерево поиска. Итеративная реализация.

Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (root), узлы, находящиеся в самом низу дерева и не имеющие потомков называют листьями (leaves). Ветви узла называют потомками (descendants). По отношению к своим потомкам узел является родителем (parent) или предком (ancestor). Также, развивая аналогию, имеются сестринские узлы (siblings – родные братья или сёстры) – узлы с общим родителем. Аналогично, у узла могут быть дяди (uncle nodes) и дедушки и бабушки ( grandparent nodes). Такие названия помогают понимать различные алгоритмы.

Двоичное дерево. На этом рисунке узел 10 корень, 7 и 12 его наследники. 6, 9, 11, 14 - листья. 7 и 12, также как и 6 и 9 являются сестринскими узлами, 10 - это дедушка узла 6, а 12 - дядя узла 6 и узла 9

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

Двоичное дерево поиска (далее ДДП) – это несбалансированное двоичное дерево, в котором элементы БОЛЬШЕ корневого размещаются справа, а элементы, которые МЕНЬШЕ размещаются слева.

Такое размещение – слева меньше, справа больше – не обязательно, можно располагать элементы, которые меньше, справа. Отношение БОЛЬШЕ и МЕНЬШЕ – это не обязательно естественная сортировка по величине, это некоторая бинарная операция, которая позволяет разбить элементы на две группы.

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

ЗАМЕЧАНИЕ: мы рассматриваем случай, когда в дереве все значения разные и не равны NULL. Деревья с повторяющимися узлами рассмотрим позднее.

Обычно в качестве типа данных мы используем void* и далее передаём функции сравнения через указатели. В этот раз будем использовать пользовательский тип и макросы.

Сначала, как обычно, напишем функцию, которая создаёт новый узел. Она принимает в качестве аргументов значение и указатель на своего родителя. Корневой элемент не имеет родителя, значение указателя parent равно NULL.

Разберёмся со вставкой. Возможны следующие ситуации

1) Дерево пустое. В этом случае новый узел становится корнем ДДП.
2) Новое значение меньше корневого. В этом случае значение должно быть вставлено слева. Если слева уже стоит элемент, то повторяем эту же операцию, только в качестве корневого узла рассматриваем левый узел. Если слева нет элемента, то добавляем новый узел.
3) Новое значение больше корневого. В этом случае новое значение должно быть вставлено справа. Если справа уже стоит элемент, то повторяем операцию, только в качестве корневого рассматриваем правый узел. Если справа узла нет, то вставляем новый узел.

Пусть нам необходимо поместить в ДДП следующие значения

10 7 9 12 6 14 11 3 4

Первое значение становится корнем.

Второе значение меньше десяти, так что оно помещается слева.

Число 9 меньше 10, так что узел должен располагаться слева, но слева уже стоит значение. 9 больше 7, так что новый узел становится правым потомком семи.

Число 12 помещается справа от 10.

6 меньше 10 и меньше 7.

Добавляем оставшиеся узлы 14, 3, 4, 11

Функция, добавляющая узел в дерево

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

Проверяем, если дерево пустое, то вставляем корень

Проходим по дереву и ищем место для вставки

Пока не дошли до пустого узла

Если значение больше, чем значение текущего узла

Если при этом правый узел не пустой, то за корень теперь считаем правую ветвь и начинаем цикл сначала

Если правой ветви нет, то вставляем узел справа

Также обрабатываем левую ветвь

Рассмотрим результат вставки узлов в дерево. Очевидно, что структура дерева будет зависеть от порядка вставки элементов. Иными словами, форма дерева зависит от порядка вставки элементов.

Если элементы не упорядочены и их значения распределены равномерно, то дерево будет достаточно сбалансированным, то есть путь от вершины до всех листьев будет одинаковый. В таком случае максимальное время доступа до листа равно log(n), где n – это число узлов, то есть равно высоте дерева.

Но это только в самом благоприятном случае. Если же элементы упорядочены, то дерево не будет сбалансировано и растянется в одну сторону, как список; тогда время доступа до последнего узла будет порядка n. Это слабая сторона ДДП, из-за чего применение этой структуры ограничено.

Дерево, которое получили вставкой чередующихся возрастающей и убывающей последовательностей (слева) и полученное при вставке упорядоченной последовательности (справа)

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

Поиск в дереве

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

Аналогично, можно найти максимальный элемент

Опять же, если дерево хорошо сбалансировано, то поиск минимума и максимума будет иметь сложность порядка log(n), а в случае плохой балансировки стремится к n.

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

Удаление узла

С уществует три возможных ситуации.

Алгоритмы, связанные с деревом решений - подробное описание и реализация ID3 и C4.5

Предисловие

В этом блоге записано использование python Реализуйте две модели алгоритма, связанные с деревьями решений - ID3, C4.5. Набор данных, используемый для обучения модели:Adult. Хотя в пакете Sklearn есть реализации этих алгоритмов, прекрасно реализовать их снова в соответствии с идеями алгоритмов. Среди них сладкое и кислое - это самопознание (оно может улучшить определенные навыки написания кода и отладки),Подробный адрес реализации кода на GitHub。

1. Осуществите подготовительные работы-какие

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

Древо решений да На основе функций Модель классификации для выборки можно понимать как условное распределение вероятностей класса при заданном характеристическом условии. Образец, подлежащий классификации То есть заданное характеристическое значение, Этикетка будет предсказана То есть вероятность того, что данный класс условий собственного значения является наибольшим, то есть классу, к которому он принадлежит. Дерево решений теперь служит способом разделения пространства функций. Размерность пространства признаков - это количество объектов в наборе данных. Пространство признаков делится по алгоритму ID3 или C45, и каждый разделенный интервал пространства признаков соответствует метке категории с наибольшей вероятностью появления. принадлежать count-based тип. Листовые узлы дерева решений представляют метку класса в наборе данных, а внутренние узлы представляют характеристики выбора и разделения.

1.2 Концепции, которые необходимо знать

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

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

Тогда энтропия случайной величины X определяется как:

Условная энтропия: Представляет неопределенность случайной величины Y при условии известной случайной величины X-H (Y | X)

H (Y | X) - математическое ожидание энтропии условного распределения вероятностей Y на X при заданных условиях X.

, где p (x) представляет вероятность появления X = x

Получение информации: Как правило, обычно используемые методы для выбора признаков - это критерий хи-квадрат, перекрестная энтропия и получение информации. G (D, A) представляет степень, в которой неопределенность классификации набора данных уменьшается путем выбора признака A, тем больше уменьшение , Чем ниже неопределенность классификации набора данных. Указывает, что функция A лучше влияет на классификацию набора данных D.

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

Для набора образцов D случайная величина X является категорией выборки, то есть, предполагая, что в выборке есть k категорий, вероятность каждой категории равна | Ck | / | D |, где | Ck | представляет количество выборок категории k, | D | представляет общее количество выборок

Коэффициент сбора информации: Получение информации смещено в сторону выбора функций с большим количеством значений. Перед лицом непрерывных данных (таких как вес, рост, возраст, расстояние и т. Д.), Или каждый столбец данных не имеет очевидной классификации (самый крайний пример этого столбца уникален), в данном случае для характеристики Чем больше его значение, тем легче получить наборы под-данных с меньшим количеством категорий на основе этого разделения функций. Причина в том, что чем больше значение признака, чем меньше значение H (D | A) в это время, тем больше выигрыш в информации, поэтому тем легче его выбрать во время выбора признака. Причина малого H (D | A) может быть основана на приведенной выше формуле H(D|A) Происхождение рассуждений. В ответ на эту проблему коэффициент усиления информации используется для корректировки усиления информации.

Коэффициент передачи информации = параметр штрафа * коэффициент передачи информации

где Штрафной параметр Величина, обратная HA (D), то есть величина, обратная Info в приведенной выше формуле, Обратите внимание, что расчет Info и H (D | A) производится по разным формулам расчета.
Если значение, соответствующее определенной функции, слишком велико, расчет информации будет слишком большим, а обратная величина будет маленькой, то есть параметр штрафа слишком мал, а коэффициент усиления информации = параметр штрафа * информация Получение, то есть определенная степень наказания за получение информации.

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

где pk представляет собой вероятность того, что выбранный образец принадлежит категории k, а вероятность того, что этот образец будет классифицирован, составляет (1-pk)
Предположим, что в наборе образцов есть K категорий. Случайно выбранный образец может принадлежать к любой из этих k категорий, поэтому категории добавляются

Вышеупомянутая формула представляет собой вычисление индекса Джини для набора выборки D, где Ck представляет собой подмножество выборки, принадлежащее K-й категории в D, а K - количество категорий в метке набора данных.

Джини (D, A) представляет индекс Джини набора D при условии свойства A.
Поскольку дерево, построенное в алгоритме CART, является двоичным деревом, два подмножества после пространства признаков всех двоичных деревьев, разделенных признаком A, - это D1, D2.
где Gini(D) Представляет неопределенность набора данных D, Gini(D,A) Представляет неопределенность набора данных D после A = сегментация. Так что выбирайте при выборе функций Gini(D)-Gini(D,A) больше.

1.3 Основные шаги и причины построения дерева решений

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

2 Конкретный процесс внедрения - как

Шаг 1 Предварительная подготовка данных

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

Детальный анализ набора данных
Из-за проблемы с формой отметки здесь перехват zxhohai Схема описания атрибутов набора данных блоггера.

Загружено с Файл описания набора данных для взрослых adult.name Можно видеть, что набор данных содержит 8 дискретных функций и 6 непрерывных атрибутов.
8 дискретных функций: workclass Всего 8 значений; education Всего 16 значений; marital-status 7 значений; occupation Всего 14 значений; relationship Всего 6 значений; race Есть 5 значений; sex Есть два значения; native-country Всего 41 значение.
6 непрерывных функций.

Обработка непрерывных объектов
Поскольку существует много непрерывных функций, с одной стороны, алгоритм ID3 более склонен к выбору функций с большим количеством значений. С другой стороны, при выборе этой функции для разделения легко принимать решения У более мелкого дерева больше ветвей, что приводит к серьезным проблемам с перебором. так что Требуется выполнить сегментированную дискретную обработку для непрерывных функций 。

Конкретно как выполнить сегментированную дискретную обработку . —— Деревья решений C4.5 и ID3 поддерживают форму деревьев с несколькими ветвями, в то время как CART поддерживает только двоичные деревья.
, расположите значения непрерывных объектов в порядке возрастания, а затем возьмите среднюю точку Qi между ними по порядку
Рассчитайте информационное усиление набора данных после того, как будет взято значение Qi этой функции, и возьмите точку отсечения с наибольшей скоростью информационного прироста. Точка разделения Qi, Qi - дерево правой ветви.
Для объектов, значения дискретных объектов которых превышают определенное число, значения также можно снова дискретно обрабатывать в сегментах.

Step2 обработка данных

Импорт данных и пропущенные значения, обработка повторяющихся значений

Просмотр распределения непрерывных данных

Непрерывная обработка данных об объектах
Вот общий метод обработки ID3 и C45, а метод обработки алгоритма CART представляет собой непрерывную двухдискретную функцию. Главное отличие После выбора функции для ID3 и C45 последующие поддеревья больше не будут использовать эту функцию для разделения, в то время как CART является непрерывной двухдискретной функцией, то есть после того, как значение функции разделено на два, каждая подобласть Снова выберите оптимальную характеристику и оптимальную точку разделения.
Конечно, для алгоритмов ID3 и C45 здесь также могут быть выбраны другие методы разделения, которые можно разделить на несколько сегментов. КОРЗИНА должна быть разделена на две части.

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

Шаг 3 Выбор функции

Здесь алгоритмы ID3 и C45 реконструируются в шаблон, и для вызова необходимо передать только имя функции для выбора функции select_func.
, где ID3 - Выберите максимальное количество информации Разделен на функции; C45 - это Выберите максимальный коэффициент передачи информации Характеристики разделены.

Шаг 4 Рекурсивно создайте связующее дерево (создание сверху вниз)

Идеи алгоритмов ID3 и C45 (онлайн-скриншоты)

Достичь 1 - построить узел дерева решений:

Реализация 2-связующего дерева:

алгоритм обрезки step5

Сокращение в основном предназначено для решения проблемы переобучения модели, вызванной классификацией дерева решений. Есть два способа Обрезка и случайный лес . Случайный лес будет подробно описан в следующей статье.
5.1 Описание

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

5.2 Понимание

1. Обрезка дерева решений достигается за счет минимизации функции стоимости дерева решений. Формула функции стоимости дерева решений:

где количество конечных узлов дерева T равно | T |, t - конечный узел дерева T, конечный узел имеет Nt точек выборки, а точки выборки k-типа имеют Ntk A, k = 1,2, . K, Ht (T) - эмпирическая энтропия на листовом узле t, а α≥0 - гиперпараметр. Листовой узел может быть разделен на точки выборки из нескольких категорий из-за ошибок, поэтому существует листовой узел с K точками выборки. Среди них формула эмпирической энтропии Ht (T) находится наверху.
2. Функция стоимости дерева решений Ca(T) Понимание
C | T | представляет ошибку прогнозирования модели на обучающих данных, Я до сих пор не понимаю, почему формула C | T | , Гипотеза: C | T | - неопределенность модели относительно количества выборок, оставшихся после обучающих данных. | T | представляет сложность модели, взвешенную параметром a C | T | и | T | Влияние между ними - сложность модели и соответствие модели обучающим данным. Модель слишком сложна и ее легко переоснастить, и значение a необходимо скорректировать, чтобы уменьшить сложность. Это достигается обрезкой. В процессе обрезки значение a и изменение | T | Идея динамического программирования необходима для решения оптимального значения.
3. Понимание из идеи модели обучения машинного обучения. Ca(T)
Обучение модели дерева решений C(T) Максимальное правдоподобие оценивается как:

Функция стоимости - это регуляризованная оценка максимального правдоподобия, а процесс сокращения заключается в постоянном минимизации функции стоимости.
Обычный термин можно понимать как a|T| .

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

Идентификатор Metodicheskie-materialy/Nelineinye-dinamicheskie-struktury-dannyh-v-C-Derevya-Elektronnyi-resurs-metod-ukazaniya-70945/1/Симонова Е.В. Линейные динамические структуры данных в С не соответствует правильному Файл архива электронных ресурсов. Это могло произойти по одной из следующих причин:

URL текущей страницы неверен. Если Вы попали сюда извне архива электронных ресурсов, то, возможно, адрес набран неправильно или поврежден.
Вы ввели недопустимый ID в форму — пожалуйста, повторите попытку.

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

Читайте также: