Дерево решений для алгоритмов машинного обучения

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

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

Преимущества деревьев решений:

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

Недостатки деревьев решений:

В обучающих данных легко генерировать сложные древовидные структуры, что приводит к переобучению. Обрезка может смягчить негативные последствия переобучения.Обычными методами являются ограничение высоты дерева и минимального количества выборок в листовых узлах.
Изучение оптимального дерева решений считается NP-полной задачей. Фактическое дерево решений строится на основе эвристического жадного алгоритма, который не может гарантировать создание глобально оптимального дерева решений (введение случайности в Random Forest может облегчить эту проблему).

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

Когда кто-то вводит новый объект, нам нужно судить о характеристиках одну за другой, поэтому процесс этого суждения можно изобразить в виде дерева, например, по характеристикам судить по очереди:

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

Конечно, если мы сначала рассмотрим богатых или небогатых, а затем белых или нет, результирующее дерево будет другим:

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

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

И «богатые, белые, красивые» деревья решений становятся:

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

Алгоритм классификации дерева решений

Анализ решений на основе алгоритма ID3

ID3 — это алгоритм классификации на основе дерева решений, разработанный Дж. Россом Куинланом в 1986 году. Алгоритм основан на теории информации и использует информационную энтропию и прирост информации в качестве эталона измерения, чтобы реализовать индукцию и классификацию данных. Использование жадной стратегии сверху вниз, основанной на получении информации, является основным методом ID3 для построения дерева решений. Основное преимущество использования алгоритма ID3 заключается в том, что масштаб установленного дерева решений относительно мал, а скорость выполнения запросов относительно высока. Этот алгоритм основан на «бритве Оккама», то есть чем меньше дерево решений, тем лучше большее. Однако в некоторых случаях алгоритм не генерирует наименьшую древовидную структуру.

количество информации

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

Событие A: Бразилия вышла в финал ЧМ-2018.
Событие B: сборная Китая вышла в финал чемпионата мира 2018 года.

Просто интуитивно понятно, что событие B более информативно, чем событие A. Причина в том, что вероятность события А очень высока, а вероятность события В очень мала. Таким образом, чем менее вероятно событие, тем больше информации мы получаем. Чем более вероятно событие, тем меньше информации мы получаем. Так:

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

Если известно, что событие Xi произошло, это означает количество информации, содержащейся или предоставленной Xi:

$H(X_i) = -\log_{a}{P(X_i)}$

Если по основанию 2, единицей измерения является бит, если по основанию e, единицей является nat, если по основанию 10, единицей измерения является det;

Например, вероятность дождя сегодня равна 0,5, тогда количество содержащейся информации равно $-\log_{2}{0.5} = 1$ бит; аналогично, вероятность нормального взлета самолета в дождливую погоду равна 0,25, тогда количество информации равно $-\log_{2}{0.25} = 2$ биты.

Информационная энтропия

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

Предположим, что X — дискретная случайная величина, диапазон значений которой равен ${x_1, x_1, ..., x_n}$ , вероятность каждого взятия равна ${p_1,p_1,...,p_n}$ , то энтропия X определяется как:

$H(X) = \sum_{i}{P(x_i)I(x_i)} = -\sum_i{P(x_i)\log_2{P(x_i)}}$

Условная энтропия

При сегментации дерева решений событие x_i Его можно рассматривать как некую метку/решение, появляющееся в образце. тогда P(x_i) Его можно заменить частотой определенной метки во всех образцах. Но мы ищем энтропию, чтобы решить, какое измерение использовать для сегментации, поэтому возникает новая концепция.Условная энтропия:

$H(X|Y) = \sum_{y \in Y}{p(y) H(X|Y=y)}$

Здесь мы думаем, что Y нужно разделить на определенное измерение, тогда y является подмножеством разреза, поэтому H(X|Y=y) является энтропией этого подмножества. Таким образом, можно считать, что условная энтропия представляет собой средневзвешенное значение/математическое ожидание энтропии каждого подмножества.

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

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

С определением информационной энтропии хорошо понимается концепция прироста информации, что означает разницу между общей информационной энтропией данных после классификации. Предположим, что в наборе признаков есть дискретный признак a, который имеет V возможных значений ${a^1,a^2,...,a^V}$ , если используется функцияприйти на пробуразделить, то будетузлы ответвления, гдеНабор образцов, содержащихся в каждом узле ветви. мы записываем как D^v . Таким образом, можно вычислить характеристикидля набора образцовПрирост информации, полученный при делении, равен:

$Gain(D,a) = H(D) - H(D|a) = H(D)-\sum_{v=1}^{V}\frac{\left |D^v \right |}{\left |D \right |}H(D^v)$

Объясняя вышеприведенную формулу, фактически информационный прирост, полученный при разделении выборки D по признаку a, равен информационной энтропии выборки D за вычетом суммы информационной энтропии каждой ветви после деления. Поскольку каждый узел ветви содержит разное количество выборок, соответствующий вес необходимо умножать при расчете информационной энтропии каждой ветви. $\frac{\left |D^v \right |}{\left |D \right |}$ , то есть большее влияние оказывает узел ответвления с большим количеством отсчетов.

Процесс алгоритма ID3

Вход: набор данных D, набор признаков A.

Выход: дерево решений ID3

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

Применение алгоритма ID3

Мы используем реальные случаи, чтобы узнать больше обо всем алгоритмическом процессе.

Процесс расчета выглядит следующим образом:

1. Сначала вычислить информационную энтропию выборки D:

$H(D)=-\frac{7}{10}log_{2}\frac{7}{10}-\frac{3}{10}log_{2}\frac{3}{10}=0.881$

2. Рассчитайте информационный прирост каждой функции для набора данных D и возьмите A1, A2 и A3 в качестве результатов тестов, выполнения домашних заданий и посещаемости, и расчет будет следующим:

$G(D,A_{1}) = H(D)-[\frac{2}{10}H(D_{1})+\frac{2}{10}H(D_{2})+\frac{4}{10}H(D_{3}) +\frac{2}{10}H(D_{4})]$

Здесь D1, D2, D3 и D4 — подмножества выборок со значениями отлично, хорошо, успешно и неудовлетворительно в D соответственно. так:

$G(D,A_{1}) = H(D)-[\frac{2}{10}*0+\frac{2}{10}*0+\frac{4}{10} * (-\frac{3}{4}log_{2}\frac{3}{4}-\frac{1}{4}log_{2}\frac{1}{4}) +\frac{2}{10}*0] = 0.539$

Аналогичные расчеты А2, А3, результаты следующие:

$G(D,A_{2}) =0.406$

$G(D,A_{3}) =0.881$

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

Python реализация алгоритма ID3

from math import log
import operator
 
 
# 计算香农熵
def calculate_entropy(data):
    label_counts = {}
    for feature_data in data:
        laber = feature_data[-1]  # 最后一行是laber
        if laber not in label_counts.keys():
            label_counts[laber] = 0
        label_counts[laber] += 1
 
    count = len(data)
    entropy = 0.0
 
    for key in label_counts:
        prob = float(label_counts[key]) / count
        entropy -= prob * log(prob, 2)
    return entropy
 
# 计算某个feature的信息增益
# index:要计算信息增益的feature 对应的在data 的第几列
# data 的香农熵
def calculate_relative_entropy(data, index, entropy):
    feat_list = [number[index] for number in data]  # 得到某个特征下所有值（某列）
    uniqual_vals = set(feat_list)
    new_entropy = 0
    for value in uniqual_vals:
        sub_data = split_data(data, index, value)
        prob = len(sub_data) / float(len(data))  
        new_entropy += prob * calculate_entropy(sub_data)  # 对各子集香农熵求和
    relative_entropy = entropy - new_entropy  # 计算信息增益
return relative_entropy
 
# 选择最大信息增益的feature
def choose_max_relative_entropy(data):
    num_feature = len(data[0]) - 1
    base_entropy = calculate_entropy(data)#香农熵
    best_infor_gain = 0
    best_feature = -1
    for i in range(num_feature):
        info_gain=calculate_relative_entropy(data, i, base_entropy)
        #最大信息增益
        if (info_gain > best_infor_gain):
            best_infor_gain = info_gain
            best_feature = i
 
return best_feature
 
def create_decision_tree(data, labels):
    class_list=[example[-1] for example in data]
    # 类别相同，停止划分
    if class_list.count(class_list[-1]) == len(class_list):
        return class_list[-1]
    # 判断是否遍历完所有的特征时返回个数最多的类别
    if len(data[0]) == 1:
        return most_class(class_list)
    # 按照信息增益最高选取分类特征属性
    best_feat = choose_max_relative_entropy(data)
    best_feat_lable = labels[best_feat] # 该特征的label
    decision_tree = {best_feat_lable: {}} # 构建树的字典
    del(labels[best_feat]) # 从labels的list中删除该label
    feat_values = [example[best_feat] for example in data]
    unique_values = set(feat_values)
    for value in unique_values:
        sub_lables=labels[:]
        # 构建数据的子集合，并进行递归
        decision_tree[best_feat_lable][value] = create_decision_tree(split_data(data, best_feat, value), sub_lables)
return decision_tree
 
# 当遍历完所有的特征时返回个数最多的类别
def most_class(classList):
    class_count={}
    for vote in classList:
        if vote not in class_count.keys():class_count[vote]=0
        class_count[vote]+=1
    sorted_class_count=sorted(class_count.items,key=operator.itemgetter(1),reversed=True)
    return sorted_class_count[0][0]
    
# 工具函数输入三个变量（待划分的数据集，特征，分类值）返回不含划分特征的子集
def split_data(data, axis, value):
    ret_data=[]
    for feat_vec in data:
        if feat_vec[axis]==value :
            reduce_feat_vec=feat_vec[:axis]
            reduce_feat_vec.extend(feat_vec[axis+1:])
            ret_data.append(reduce_feat_vec)
    return ret_data

Ссылка на ссылку:сегмент fault.com/ah/119000001…

Преимущества и недостатки алгоритма ID3

Преимущества алгоритма ID3:

Структура алгоритма проста;
Алгоритм понятен и прост для понимания;
Очень гибкий и удобный;
Неразрешимой опасности нет;
Решения можно принимать, используя статистические свойства всех обучающих примеров, что делает их устойчивыми к шуму.

Алгоритм ID3 прост, но у него много недостатков:

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

Дерево решений классификации на основе алгоритма C4.5

C4.5 - это еще один алгоритм дерева решений классификации, полученный Дж. Россом Куинланом на основе улучшения алгоритма ID3. Алгоритм C4.5 наследует преимущества алгоритма ID3, а правила классификации, созданные усовершенствованным алгоритмом, просты для понимания и обладают высокой точностью. В то же время у алгоритма есть и некоторые недостатки, например, алгоритм неэффективен, а значение подходит для наборов данных, которые могут находиться в памяти. На основе алгоритма ID3 в алгоритм C4.5 внесены следующие улучшения:

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

Каковы недостатки классификации атрибутов на основе получения информации? Предполагая, что имеется 14 выборок данных, добавьте столбец данных признаков = [1,2,3,4,5,6,7,8,9,10,11,12,13,14] в соответствии с формулой , вы можете рассчитать соответствующий прирост информации: Прирост (D, данные) = 0,940, мы обнаружили, что его соответствующий прирост информации намного больше, чем другие функции, поэтому нам нужно использовать функцию данных как разделение первого узла. Таким образом, будет сгенерировано 14 ветвей, каждая ветвь содержит только один образец, а чистота каждого узла ветвления достигла максимума, то есть результат каждого узла ветвления очень определен. Однако такое дерево решений определенно не то, что нам нужно, потому что оно вообще не обладает какой-либо способностью к обобщению. Чтобы избежать этой проблемы, мы вводим понятие коэффициента усиления и используем коэффициент усиления в качестве критерия оптимального разделения признаков.

Скорость получения информации

Также предположим, что существует набор данных D и функция a, которая имеет возможное значение ${a^1,a^2,...,a^V}$ , если набор данных D использует функцию a в качестве разделяющей функции, коэффициент усиления определяется как:

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

в:

$IV(a) = -\sum_{V}^{v=1} \frac{\left | D^v \right |}{\left |D \right |} \log2 \frac{\left | D^v \right |}{\left |D \right |}$

Давайте посмотрим на приведенную выше формулу коэффициента усиления, на самом деле IV(a) Это информационная энтропия самого признака а, то есть соответствующая информационной энтропии, полученной в соответствии с возможными значениями признака а, чем больше соответствующих типов признака а, то есть чем больше чем больше значение, тем больше значение.Таким образом, скорость усиления меньше. Таким образом, можно избежать недостатка предпочтения относительно большого количества признаков при получении информации. Однако коэффициент усиления отдает предпочтение атрибутам с небольшим количеством значений, поэтому существует «эвристическое» правило: сначала найти атрибуты с более высоким информационным приростом, чем средний уровень, из атрибутов раздела-кандидата, а затем выбрать самый высокий коэффициент усиления.

Пример применения алгоритма C4.5

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

1. Рассчитайте информационную энтропию выборки D:

$H(D)=-\frac{7}{10}log_{2}\frac{7}{10}-\frac{3}{10}log_{2}\frac{3}{10}=0.881$

2. Рассчитать информационную энтропию отдельно для каждого признака в наборе признаков:

$H(D_{1}) = \frac{2}{10}*0+\frac{2}{10}*0+\frac{4}{10} * (-\frac{3}{4}log_{2}\frac{3}{4}-\frac{1}{4}log_{2}\frac{1}{4}) +\frac{2}{10}*0 = 0.342$

$H(D_{2}) = 0.475$

$H(D_{2}) = 0$

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

$G(D,A_{1}) =0.539$

$G(D,A_{2}) =0.406$

$G(D,A_{3}) =0.881$

4. Рассчитайте метрику разделения информации H(V):

$H(A_{1}) = -\frac{2}{10} \log2\frac{2}{10} -\frac{2}{10} \log2\frac{2}{10} -\frac{4}{10} \log2\frac{4}{10} -\frac{2}{10} \log2\frac{2}{10} = 1.9219$

$H(A_{2}) = -\frac{2}{10} \log2\frac{2}{10} -\frac{3}{10} \log2\frac{3}{10} -\frac{2}{10} \log2\frac{2}{10} -\frac{3}{10} \log2\frac{3}{10} = 1.9709$

$H(A_{2}) = -\frac{7}{10} \log2\frac{7}{10} -\frac{3}{10} \log2\frac{3}{10} = 0.881$

5. В соответствии с приведенными выше результатами можно рассчитать коэффициент усиления памяти:

$IGR(A_{1}) = G(A_{1}) \div H(A_{1}) = 0.2803$

$IGR(A_{2}) = G(A_{1}) \div H(A_{2}) = 0.2058$

$IGR(A_{3}) = G(A_{1}) \div H(A_{3}) = 1$

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

Реализация алгоритма C4.5 Python

from treeNode import TreeNode
import pandas as pd
import numpy as np
 
 
class DecisionTreeC45:
 
    def __init__(self, X, Y):
        self.X_train = X
        self.Y_train = Y
        self.root_node = TreeNode(None, None, None, None, self.X_train, self.Y_train)
        self.features = self.get_features(self.X_train)
        self.tree_generate(self.root_node)
 
    def get_features(self, X_train_data):
        features = dict()
        for i in range(len(X_train_data.columns)):
            feature = X_train_data.columns[i]
            features[feature] = list(X_train_data[feature].value_counts().keys())
 
        return features
 
    def tree_generate(self, tree_node):
        X_data = tree_node.X_data
        Y_data = tree_node.Y_data
        # get all features of the data set
        features = list(X_data.columns)
 
        # 如果Y_data中的实例属于同一类，则置为单结点，并将该类作为该结点的类
        if len(list(Y_data.value_counts())) == 1:
            tree_node.category = Y_data.iloc[0]
            tree_node.children = None
            return
 
        # 如果特征集为空，则置为单结点，并将Y_data中最大的类作为该结点的类
        elif len(features) == 0:
            tree_node.category = Y_data.value_counts(ascending=False).keys()[0]
            tree_node.children = None
            return
 
        # 否则，计算各特征的信息增益，选择信息增益最大的特征
        else:
            ent_d = self.compute_entropy(Y_data)
            XY_data = pd.concat([X_data, Y_data], axis=1)
            d_nums = XY_data.shape[0]
            max_gain_ratio = 0
            feature = None
 
            for i in range(len(features)):
                v = self.features.get(features[i])
                Ga = ent_d
                IV = 0
                for j in v:
                    dv = XY_data[XY_data[features[i]] == j]
                    dv_nums = dv.shape[0]
                    ent_dv = self.compute_entropy(dv[dv.columns[-1]])
                    if dv_nums == 0 or d_nums == 0:
                        continue
                    Ga -= dv_nums / d_nums * ent_dv
                    IV -= dv_nums/d_nums*np.log2(dv_nums/d_nums)
 
                if IV != 0.0 and (Ga/IV) > max_gain_ratio:
                    max_gain_ratio = Ga/IV
                    feature = features[i]
 
            # 如果当前特征的信息增益比小于阈值epsilon，则置为单结点，并将Y_data中最大的类作为该结点的类
            if max_gain_ratio < 0:
                tree_node.feature = None
                tree_node.category = Y_data.value_counts(ascending=False).keys()[0]
                tree_node.children = None
                return
 
            if feature is None:
                tree_node.feature = None
                tree_node.category = Y_data.value_counts(ascending=False).keys()[0]
                tree_node.children = None
                return
            tree_node.feature = feature
 
            # 否则，对当前特征的每一个可能取值，将Y_data分成子集，并将对应子集最大的类作为标记，构建子结点
            # get all kinds of values of the current partition feature
            branches = self.features.get(feature)
            # branches = list(XY_data[feature].value_counts().keys())
            tree_node.children = dict()
            for i in range(len(branches)):
                X_data = XY_data[XY_data[feature] == branches[i]]
                if len(X_data) == 0:
                    category = XY_data[XY_data.columns[-1]].value_counts(ascending=False).keys()[0]
                    childNode = TreeNode(tree_node, None, None, category, None, None)
                    tree_node.children[branches[i]] = childNode
                    # return
                    # error, not should return, but continue
                    continue
 
                Y_data = X_data[X_data.columns[-1]]
                X_data.drop(X_data.columns[-1], axis=1, inplace=True)
                X_data.drop(feature, axis=1, inplace=True)
                childNode = TreeNode(tree_node, None, None, None, X_data, Y_data)
                tree_node.children[branches[i]] = childNode
                # print("feature: " + str(tree_node.feature) + " branch: " + str(branches[i]) + "\n")
                self.tree_generate(childNode)
 
            return
 
    def compute_entropy(self, Y):
        ent = 0;
        for cate in Y.value_counts(1):
            ent -= cate*np.log2(cate);
        return ent

Ссылка на ссылку:GitHub.com/Ru do-while EK/'s…

Разделение решений на основе дерева классификации и регрессии (CART)

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

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

Алгоритм CART можно использовать для создания как деревьев классификации, так и деревьев регрессии. К важным особенностям алгоритма CART относятся следующие три аспекта:

Двоичное разделение: в каждом процессе оценки выборочные данные делятся на две части. Алгоритм CART представляет собой метод двоичной рекурсивной сегментации, который делит текущую выборку на две подвыборки, так что каждый сгенерированный нелистовой узел имеет две ветви Таким образом, дерево решений, сгенерированное алгоритмом CART, представляет собой двоичное дерево с простой структурой. . Поскольку алгоритм CART представляет собой двоичное дерево, в решении каждого шага может быть только «да» или «нет», даже если функция имеет несколько значений, данные делятся на две части.
Разделение на основе одной переменной: каждое оптимальное разделение предназначено для одной переменной.
Стратегия обрезки: ключевой момент алгоритма CART также является ключевым шагом всего алгоритма на основе дерева. Процесс обрезки особенно важен, поэтому он играет важную роль в процессе создания оптимального дерева решений. Исследования показали, что важность процесса обрезки важнее, чем процесс генерации дерева.Для максимального дерева, созданного с использованием различных стандартов деления, после обрезки может быть сохранено наиболее важное разделение атрибутов, и разница невелика. Напротив, метод обрезки более важен для создания оптимального дерева.
Генерация дерева CART — это процесс рекурсивного построения бинарного дерева решений с использованием критерия минимизации квадратичной ошибки для регрессии и критерия индекса Джини для деревьев классификации для выбора признаков и создания бинарных деревьев.

Разница между ID3, C4.5, ТЕЛЕЖКОЙ

Индекс Джини

Индекс Джини — это то же понятие, что и информационная энтропия, оба из которых описывают степень хаоса. Индекс Джини Gini(D) представляет неопределенность набора D. Индекс Джини Gini(D,A) представляет собой неопределенность набора D после того, как набор данных D делится на функцию A. Чем больше индекс Джини, тем неопределенность нашего множества.Чем больше пол, тем идея в основном согласуется с понятием информационной энтропии.

Для набора выборок D, при условии наличия K классов, вероятность того, что точка выборки принадлежит k-му классу, равна p_k , то индекс Джини распределения вероятностей определяется как:

$Gini(D)=\sum_{k=1}^{K} p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2$

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

$Gini(D)=1 - \sum_{k=1}^{K}(\frac{|C_k|}{D})^2$

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

Разделите атрибут a, тогда индекс Джини атрибута a определяется как:

$Gini\_index(D,a)=\sum \limits_{v=1} ^V\frac{\left| D^v \right|}{\left| D \right|}Gini(D^v)$

Если набор данных D разделить на некоторое значение a по признаку A и получить две части D1 и D2, то коэффициент Джини множества D по признаку A равен:

$Gini\_Gini(D,a)=\frac{D_1}{D}Gini(D_1) + \frac{D_2}{D}Gini(D_2)$

Следовательно, в наборе атрибутов-кандидатов А мы выбираем атрибут с наименьшим индексом Джини после деления в качестве оптимального атрибута деления, а именно:

$a_*=\arg\limits_{a\in A} \min Gini\_index(D,a)$

Условия остановки алгоритма:

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

Пример приложения: разделение решений

Для приведенных выше дискретных данных температура тела делится на постоянную температуру и непостоянную температуру. Среди них 5 млекопитающих и 2 птицы при постоянной температуре и 3 рептилии, 3 рыбы и 2 амфибии при непостоянной температуре Мы рассчитываем индекс Джини D1 и D2, как показано ниже.

$Gini(D_1) = 1 - [(\frac{5}{7})^2+(\frac{2}{7})^2] = \frac{20}{49}$

$Gini(D_2) = 1 - [(\frac{3}{8})^2+(\frac{3}{8})^2+(\frac{2}{8})^2] = \frac{42}{64}$

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

$Gini\_Gini(A_1) = \frac{7}{15} * \frac{20}{49}+\frac{8}{15} * \frac{42}{64}$

Реализация алгоритма CART на Python

from treeNode import TreeNode
import pandas as pd
import numpy as np
 
 
class DecisionTreeCART:
 
    def __init__(self, X, Y):
        self.X_train = X
        self.Y_train = Y
        self.root_node = TreeNode(None, None, None, None, self.X_train, self.Y_train)
        self.features = self.get_features(self.X_train)
        self.tree_generate(self.root_node)
 
    def get_features(self, X_train_data):
        features = dict()
        for i in range(len(X_train_data.columns)):
            feature = X_train_data.columns[i]
            features[feature] = list(X_train_data[feature].value_counts().keys())
 
        return features
 
    def tree_generate(self, tree_node):
        X_data = tree_node.X_data
        Y_data = tree_node.Y_data
        # get all features of the data set
        features = list(X_data.columns)
 
        # 如果Y_data中的实例属于同一类，则置为单结点，并将该类作为该结点的类
        if len(list(Y_data.value_counts())) == 1:
            tree_node.category = Y_data.iloc[0]
            tree_node.children = None
            return
 
        # 如果特征集为空，则置为单结点，并将Y_data中最大的类作为该结点的类
        elif len(features) == 0:
            tree_node.category = Y_data.value_counts(ascending=False).keys()[0]
            tree_node.children = None
            return
 
        # 否则，计算各特征的基尼指数，选择基尼指数最小的特征
        else:
            # gini_d = self.compute_gini(Y_data)
            XY_data = pd.concat([X_data, Y_data], axis=1)
            d_nums = XY_data.shape[0]
            min_gini_index = 1
            feature = None
            feature_value = None
 
            for i in range(len(features)):
                # 当前特征有哪些取值
                # v = self.features.get(features[i])
                v = XY_data[features[i]].value_counts().keys()
                # 当前特征的取值只有一种
                if len(v) <= 1:
                    continue
                # 当前特征的每一个取值分为是和不是两类
                for j in v:
                    Gini_index = 0
                    dv = XY_data[XY_data[features[i]] == j]
                    dv_nums = dv.shape[0]
                    dv_not = XY_data[XY_data[features[i]] != j]
                    dv_not_nums = dv_not.shape[0]
                    gini_dv = self.compute_gini(dv[dv.columns[-1]])
                    gini_dv_not = self.compute_gini(dv_not[dv_not.columns[-1]])
                    if d_nums == 0:
                        continue
                    Gini_index += dv_nums / d_nums * gini_dv + dv_not_nums / d_nums * gini_dv_not
 
                    if Gini_index < min_gini_index:
                        min_gini_index = Gini_index
                        feature = features[i]
                        feature_value = j
 
            if feature is None:
                tree_node.category = Y_data.value_counts(ascending=False).keys()[0]
                tree_node.children = None
                return
            tree_node.feature = feature
 
            # 否则，对当前特征的最小基尼指数取值，将Y_data分成两类子集，构建子结点
            # get all kinds of values of the current partition feature
            # branches = list({feature_value, "!"+str(feature_value)})
            # branches = list(XY_data[feature].value_counts().keys())
            tree_node.children = dict()
            for i in range(2):
                # 左分支，左分支为是的分支
                if i == 0:
                    X_data = XY_data[XY_data[feature] == feature_value]
                    X_data.drop(feature, axis=1, inplace=True)
                    child_name = feature_value
                # 右分支，右分支为否的分支
                else:
                    X_data = XY_data[XY_data[feature] != feature_value]
                    child_name = "!" + str(feature_value)
                # 可能出现节点没有数据的情况吗？
                # if len(X_data) == 0:
                #     print("I'm a bug")
                #     category = XY_data[XY_data.columns[-1]].value_counts(ascending=False).keys()[0]
                #     childNode = TreeNode(tree_node, None, None, category, None, None)
                #     tree_node.children[child_name] = childNode
                #     # return
                #     # error, not should return, but continue
                #     continue
 
                Y_data = X_data[X_data.columns[-1]]
                X_data.drop(X_data.columns[-1], axis=1, inplace=True)
                # X_data.drop(feature, axis=1, inplace=True)
                childNode = TreeNode(tree_node, None, None, None, X_data, Y_data)
                tree_node.children[child_name] = childNode
                # print("feature: " + str(tree_node.feature) + " branch: " + str(branches[i]) + "\n")
                self.tree_generate(childNode)
 
            return
 
    def compute_gini(self, Y):
        gini = 1
        for cate in Y.value_counts(1):
            gini -= cate*cate
        return gini

Ссылка на ссылку:GitHub.com/Ru do-while EK/'s…

Классификация решений на основе случайного леса

Случайный лес — это классификатор, содержащий несколько деревьев решений. Алгоритм случайного леса был разработан Лео Брейманом и Адель Катлер. Случайный лес, как следует из названия, заключается в построении леса случайным образом.Лес состоит из множества деревьев решений, и между этими деревьями решений нет никакой связи.

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

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

Преимущества случайных лесов

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

Недостатки случайных лесов

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

Метод построения случайного леса

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

1. Случайная выборка

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

2. Полностью разделен

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

Далее будет представлен метод построения каждого генеалогического дерева.Шаги следующие:

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

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

Пример случайного леса

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

1. Рассмотрим каждое дерево в случайном лесу как дерево ТЕЛЕГИ Здесь есть 5 характеристик вишни, поэтому предполагается, что в случайном глубоком лесу 5 деревьев ТЕЛЕГИ.

2. Соответствующая информация о вишне определяет, к какому ценовому уровню она относится.

3. Окончательно определено, что черешня может быть реализована по первоклассной (49%) цене.

Обрезка деревьев решений

Деревья решений склонны к переоснащению, и методы, которые можно улучшить:

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

Классификация обрезки

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

Предварительная обрезка

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

Рост дерева не может быть бесконечным, поэтому необходимо задать некоторые условия.Если рост дерева вызывает определенное заданное условие, рост дерева необходимо остановить и продолжить. Эти установленные условия называются Критериями остановки.Обычно используемые условия остановки следующие:

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

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

Хотя текущее деление не может привести к повышению производительности, возможно, последующие деления, основанные на этом, могут значительно улучшить производительность?

после обрезки

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

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

Алгоритм постобрезки

Сокращение ошибок (Reduced Error Pruning, REP)

Алгоритм REP — один из самых простых методов пост-обрезки, требующий отсеченного проверочного набора для обрезки дерева решений и обучающего набора для обучения данных. Обычно одна треть доступных выборок берется в качестве проверочной выборки, а оставшиеся две трети используются в качестве обучающей выборки. Он в основном используется для предотвращения переобучения деревьев решений.

Шаги, чтобы решить, следует ли обрезать узел, следующие:

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

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

Пессимистическое сокращение ошибок (Pessimistic Pruning, PEP) (для C4.5)

Алгоритм сокращения PEP предлагается в алгоритме дерева решений C4.5, который основан на оценке ошибок обучающих данных, поэтому он не требует отдельного набора тестовых данных по сравнению с методом сокращения REP. Однако обучающие данные также вносят ошибку неправильной классификации, которая смещена в сторону обучающего набора, поэтому необходимо добавить поправку 1/2 (коэффициент штрафа с постоянной величиной 0,5), которая представляет собой отсечение сверху вниз. Причина, по которой его называют «пессимистическим», может заключаться именно в том, что каждый конечный узел будет субъективно добавлять штрафной коэффициент, чтобы «пессимистически» увеличить скорость ошибочной оценки.

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

Если классификация поддерева (с несколькими листовыми узлами) заменена листовым узлом, частота ложных срабатываний на обучающем наборе определенно увеличится, но не обязательно на новых данных. Следовательно, нам нужно добавить эмпирический штрафной коэффициент к расчету неправильной оценки поддерева. Для конечного узла он покрывает N выборок, и имеется E ошибок, тогда частота ложных срабатываний конечного узла составляет (E + 0,5)/N, и это 0,5 является штрафным коэффициентом.

Затем для поддерева с L листовыми узлами скорость неправильной оценки поддерева оценивается как:

$e = \sum_{i \in L}\frac{E_i+0.5}{N_i}=\frac{\sum_{i \in L}(E_i+0.5)}{\sum_{i \in L}N_i}=\frac{(\sum E_0.5*L)}{\sum N}$

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

$E(sub\_err\_count) - var(sub\_err\_count) > E(leaf\_err\_count)$

Как рассчитывается стандартное отклонение, которое появляется здесь?

Мы предполагаем, что поддерево имеет значение 1 для неправильной классификации выборки, значение для правильной классификации выборки равно 0, а вероятность ошибочной классификации (коэффициент неправильной оценки) поддерева равна e, тогда каждую классификацию выборки можно приблизительно рассматривать как как временной тест Бернулли, покрытие N выборок означает выполнение N независимых тестов Бернулли. Следовательно, мы можем аппроксимировать количество ошибочных суждений поддерева биномиальным распределением, которое подчиняется B(N, e), означает повторение N независимых испытаний Бернулли). Следовательно, мы можем легко оценить среднее значение и стандартное отклонение количества ошибочных классификаций для этого дерева:

$exp(subtree\_err\_count) = N * e$

$var(subtree\_err\_count)=\sqrt{N*e*(1-e)}$

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

PEP использует подход «сверху вниз», чтобы отсечь неконечные узлы, которые удовлетворяют указанным выше неравенствам. Этот алгоритм считается одним из высокоточных алгоритмов в текущем алгоритме пост-обрезки дерева решений, и в этом алгоритме все еще есть некоторые недостатки. Во-первых, алгоритм PEP является единственным алгоритмом пост-сокращения, который использует стратегию сокращения пополнения, но этот метод иногда приводит к удалению некоторых дочерних узлов узла, которые не должны быть сокращены. Хотя метод ПЭП имеет некоторые ограничения, он показывает высокую точность в практических приложениях.

Отсечение минимума ошибок (Minimum Error Pruning, MEP)

Выборка наблюдения поступает в узел t, и вероятность класса i равна:

$p_i(t)=\frac{n_i(t)+P_{xi}m}{N(t)+m}$

в, n_i(t) Указывает количество выборок, которые оцениваются как относящиеся к классу i в обучающих выборках в этом узле. $P_{xi}$ представляет априорную вероятность попадания в этот класс. N(t) представляет количество обучающих выборок в этом узле. m — параметр метода оценки.

в определенном узле E_s Метод расчета следующий:

$E_s = 1- \frac{n_c+P_{xc}m}{N+m}=\frac{N-n_c+(1-P_{xc})m)}{N+m}$

где N — количество отсчетов в ветке, где находится узел, n_c - количество выборок с наибольшим количеством категорий в узле, $P_{xc}$ Представляет априорную вероятность большинства классов.

Если вы не обрезаете, ожидайте ошибку: $E_{split-s} = sum \frac{|S_{split}|}{|S|}\times E_{split}$

когда $E_s \leq E_{split-s}$ затем удалите узел.

Сокращение стоимости и сложности (CCP) (для CART)

Качество дерева измеряется по следующей формуле:

$W_\alpha (T) = W(T) +\alpha C(T)$

В приведенной выше формуле W(T) представляет собой меру ошибки (стоимости) дерева; C(T) представляет меру размера дерева (его можно представить количеством конечных узлов дерева) . $\alpha$ Представляет собой коэффициент баланса двух, чем больше значение, тем меньше дерево, и наоборот.

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

найти несколько поддеревьев полного дерева $\{T_i,i=1,2,3,...,m\}$
Рассчитать стоимость каждого дерева отдельно $W_\alpha (T_i)$ , выберите дерево с наименьшим $W_\alpha (T_i)$ дерево.

Алгоритм обрезки CART

Вход: дерево решений, сгенерированное алгоритмом CART. T_0 .

Выход: оптимальное дерево решений T_a

алгоритм:

Предполагать
Предполагать $\alpha = +\infty$
Восходящий расчет внутреннего узла t,,а также
- Представляет поддерево с t в качестве корневого узла
- C(t) — ошибка прогноза обучающих данных, когда t — дерево с одним узлом.
- - ошибка прогноза поддерева с корнем t на обучающих данных.
- даКоличество листовых узлов
Доступ сверху вниз к внутреннему узлу t, если есть $g(t)=\alpha$ , затем выполняется отсечение, и методом мажоритарного голосования определяется листовой узел t, и получается дерево T.
Предполагать $k=k+1,\alpha _k=\alpha ,T_k=T$
Если T не дерево, состоящее из корней и поет один, вернитесь к шагу 4
последовательность поддерева с использованием перекрестной проверкивыбрать оптимальное поддерево

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

Ссылка на ссылку:

AnnoyedPictures.com/open/5AD's 4…
Лу Миндонг: Талант/решение-внезапно…

Вознаграждение автора WeChat Pay 标点符 wechat qrcode

Alipay