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

При реализации алгоритма классификации дерева решений возникают две основные проблемы:

Как выбрать, какую функцию разделить на каждом узле?

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

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

Когда перестать разделяться?

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

  • Когда узел полностью представляет собой примеры из того же класса
  • Когда дерево достигает максимальной глубины
  • Когда улучшение показателя чистоты ниже порогового значения
  • Когда количество примеров в узле ниже порогового значения (например, в классе не кошка есть 7 собак и 1 кошка)

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

Энтропия

Энтропия — это способ измерения примесей. Формула выглядит следующим образом:

где pi — вероятность того, что результатом будет i. А ниже представлена ​​связь между p и E(p) в задаче бинарной классификации.

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

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

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

  • P(кот) = n(кот)/n(примеры) = 5/10 = 0,5
  • H (кошка) = -P (кошка) * log2 (P (кошка)) - P (собака) * log2 (P (собака)) = -0,5 * log2 (0,5) - 0,5 * log2 (0,5) = 1
  • P(пойнти и кошка) = 4/5 = 0,8
  • P(дискета и кошка) = 1/5 = 0,2
  • H(пойнт и кошка) = -p(пойнт и кошка)*log2(p(пойнт и кошка))-p(пойнт, а не кошка)*log2(p(пойнт, а не кошка)) = -0,8*log2(0,8 )-0,2*log2(0,2) = 0,72
  • H(указатель и кошка) = -p(дискета и кошка)*log2(p(дискета и кошка))-p(дискета, а не кошка)*log2(p(дискета, а не кошка)) = -0,2*log2(0,2 )-0,8*log2(0,8) = 0,72
  • w(точка и кошка) = n(точка) / n(примеры) = 5/10 = 0,5
  • w(дискета и кошка) = n(дискета) / n(примеры) = 5/10 = 0,5
  • IG = H(кошка)-(w(пойнт и кошка)*H(пойнт и кошка) + w(дискета и кошка)*H(дискета и кошка)) = 1 -(0,5*0,72+0,5*0,72) = 0,28

Что, если форма уха имеет заостренную, овальную или гибкую форму?

Используя горячее кодирование, создайте 3 бинарных объекта (заостренные, овальные и гибкие), которые принимают только 0 (не заостренные/овальные/гибкие) или 1 (заостренные/овальные). /floppy) в качестве значения.

Дерево решений для непрерывной переменной

Например, если у нас есть весовая переменная для 10 примеров: 7,2, 7,6, 8,4, 8,8, 9,2, 10,2, 11, 15, 18, 20

Поэтому мы берем все значения, которые находятся посередине между отсортированным списком обучения. Если у нас есть 10(N) обучающих примеров, нам нужно протестировать 9(N-1) различных возможных значений порога.

  1. Средняя точка 1 = (7,2+7,6)/2 = 7,4 -> вычислить IG (вес ≤ 7,4)
  2. Средняя точка 2 = (7,6+8,4)/2 = 8 -> вычислить IG (вес ≤ 8)
  3. Средняя точка 3 = (8,4+8,8)/2 = 8,4 -> вычислить IG (вес ≤ 8,4)
  4. Средняя точка 4 = (8,8+9,2)/2 = 9 -> вычислить IG (вес ≤ 9)
  5. Средняя точка 5 = (9,2 + 10,2)/2 = 9,7 -> вычислить IG (вес ≤ 9,7)
  6. Средняя точка 6 = (10,2 + 11)/2 = 10,6 -> вычислить IG (вес ≤ 10,6)
  7. Середина 7= (11+15)/2 = 13 -> вычислить IG(вес ≤ 13)
  8. Средняя точка 8 = (15+18)/2 = 16,5 -> вычислить IG (вес ≤ 16,5)
  9. Середина 9= (18+20)/2 = 19 -> вычислить IG(вес ≤ 19)

Затем выберите максимальный информационный прирост в качестве порога.

Процесс обучения дерева решений

  1. Начните со всех примеров в корневом узле.
  2. Рассчитайте прирост информации для всех возможных признаков и выберите тот, который дает наибольший прирост информации.
  3. Разделите набор данных в соответствии с выбранным объектом и создайте левую и правую ветви.
  4. Продолжайте разбивать до тех пор, пока не выполните критерии остановки.

Набор данных

Набор данных доступен через Kaggle, используя несколько функций для аутентификации счетов. Есть четыре входных функции: дисперсия, асимметрия, эксцесс, энтропия и класс выходных функций (0 и 1). Всего 1372 экземпляра.

import numpy as np # linear algebra
import pandas as pd # data processing, CSV file I/O (e.g. pd.read_csv)

df = pd.read_csv("/kaggle/input/bill_authentication/bill_authentication.csv")
df.head()

df.shape # (1372,5)

Классификатор дерева решений

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

# Split features and labels
X=df.drop('Class', axis=1)
y=df['Class']
# Train test split
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X,y, train_size = 0.8, random_state=13)
# Train the model
from sklearn.tree import DecisionTreeClassifier 
model = DecisionTreeClassifier(
    criterion = 'gini',
    splitter = 'best'
)
model.fit(X_train, y_train)

Затем строим дерево решений:

# Tree plotting
from matplotlib import pyplot as plt
from sklearn import tree
plt.figure(figsize=(40,30))
tree.plot_tree(
    model,
    feature_names=['Variance','Skewness', 'Curtosis', 'Entropy'], 
    class_names = ['Not authentic','Authentic'],
    filled = True
)
plt.show()

Предсказание модели

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

# Model prediction
y_pred = model.predict(X_test)

Оценка модели

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

#Model evaluation
from sklearn.metrics import confusion_matrix,classification_report, accuracy_score, ConfusionMatrixDisplay
acc = accuracy_score(y_pred,y_test)
cm = confusion_matrix(y_test,y_pred)
cm_display = ConfusionMatrixDisplay(confusion_matrix = cm)
# Demo the evaluation
print('Accuracy:',acc)
print(classification_report(y_test,y_pred))
cm_display.plot()
plt.show()

На сегодняшней статье все, полный код можно посмотреть на Github или Kaggle. Большое спасибо!