Как растут деревья в изумрудном городе.

Время прочтения: 5 мин.

Интересно, как много из нас при словах «машинное обучение» и «искусственный интеллект» многозначительно кивают, как бы говоря «да-да, я знаю, мощная штука, нажал кнопку и корабли забороздили космические просторы» или отстранённо машут руками, имея в виду «это какая-то чёрная магия, нам недоступная и мы даже боимся понять её суть». На деле же машинное обучение базируется на законах математики, статистики и т.п., а значит это можно понять или, как минимум, объяснить. Думаю, многие слышали о таком методе машинного обучения, как дерево решений. Действительно, средство крайне эффективное для различных задач классификации и регрессии. А если ещё проще, то дерево решений в одиночку или в совокупности с другими методами подскажет нам выдавать ли кредит, определит стоимость залога, ну или поможет  интернет-джину раскрыть загаданного персонажа (но это не точно).

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

X1 — Есть ли другие продукты, кроме кредита;

X2 — Выходил ли на просрочку 30+;

А также признак Y (был ли утрачен залог), который нам бы хотелось научиться определять на основании знаний о X1 и X2.

Таблица имеющихся у нас фактов, где 1 – наличие факта, 0 – отсутствие факта:

Существует несколько вариантов строить дерево, но в данной статье я расскажу об одном – энтропия, в общем понимании — мера хаотичности системы. В нашем случае она принимает значение от 0 (полное отсутствие неопределённости) до 1 (полная неопределённость) и будет показывать, насколько точно мы относим наше наблюдение к определенному классу (Y). Энтропия рассчитывается по формуле:

c- число классов, в нашем случае их два (1,0 – утрачен залог или нет).

p_i – вероятность отнесения наблюдения к конкретному классу (1,0 – утрачен залог или нет).

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

По искомому столбцу Y – получаем пять значений «1» и пять значений «0»

E_Y = 1, таким образом мы имеем полную неопределенность.

Как хорошо, что это не все наши данные и у нас есть информация признака X1, так давайте учтём её. Так как у данного признака только два значения (0 и 1), то значением, по которому мы будем разбивать наблюдения будет среднее между ними, а именно 1/2.

Если значение X1>1/2, то при таком условии залог утрачен (Y=1) по 2 наблюдениям и не утрачен (Y=0) также по 2, если X1<=1/2, то залог утрачен (Y=1) по 3 наблюдениям и не утрачен (Y=0) также по 3. Не нужно подставлять в формулу, чтобы понять, что в каждом классе энтропия также равна 1.

Тогда пускаем в бой второй признак.

Если значение X2>1/2, то при таком условии залог утрачен (Y=1) по 4 наблюдениям, а не утрачен (Y=0) по 1, если X2<=1/2, то залог утрачен (Y=1) по 1 наблюдению, а не утрачен (Y=0) также по 4.

Поскольку, мы расплатились по двум классам, наблюдений в каждом получилось по 5. Значит формула примет вид:

E_x2=-4/5*log₂(4/5)-1/5*log₂(1/5)=0.722. Такой же расчет и для второго класса (=0).

Это уже ниже 1, а значит мы снизили энтропию.

Но как компьютер понимает, какой признак взять для первого разветвления нашего дерева? Он считает Information Gain (IG), выигрыш информации. Формула проста:

IG = E(Y)-E(Y|X)

E(Y) мы уже посчитали на первом этапе, она =1. Для расчета E(Y|X) просто взвешиваем энтропию по наблюдениям, т.е. считаем сколько случаев отнесено к конкретному классу из всех наблюдений и умножаем на их энтропию.

IG для первого признака X1 считается как:

IG_x1 = 1 – (4/10 * 1  +  6/10*1) = 0

Для второго X2:

IG_x2 = 1 – (5/10 * 0.722  +  5/10*0.722) = 0.278

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

Код на Python

import pandas as pd
from sklearn import tree
import graphviz

df=pd. pd.read_csv(file)
X = df[['X1','X2']]
y = df['Y']
clf=tree.DecisionTreeClassifier(criterion='entropy')
clf.fit(X,y)
dot_data = tree.export_graphviz(clf, feature_names=list(X), filled=True,rounded=True)
graph = graphviz.Source(dot_data, format="png") 
graph

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

Конечно, этим работа с деревьями не ограничивается, нужно правильно подготавливать данные, контролировать переобучение, анализировать эффективность. Но мы здесь ради сути, и на поверку оказалось, что никакой тёмной магии в алгоритме нет и всё поддаётся восприятию и пониманию. С одной стороны, должно быть радостно, что очередной секрет для нас раскрыт, но с другой стороны как-то грустно, когда фокус раскрывают, весь магический флёр спадает и мы остаёмся один на один с холодной реальностью. А может быть и не нужно всё знать, а иначе, сняв очки, мы обнаружим, что город – то не изумрудный, Гудвин – просто человек, а у Страшилы так и нет мозгов.