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

Дерево решений в коде

Здравствуйте и вновь добро пожаловать на занятия по теме «Обработка данных: машинное обучение с учителем на языке Python».

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

Итак, мы начинаем с импорта библиотеки Numpy; с файла util.py импортируем функции get_data, get_xor и get_donut, чтобы можно было попробовать все эти задачи и посмотреть, как работает дерево решений. Кроме того, нам понадобится функция datetime, чтобы фиксировать время подбора решения и прогнозирования.

import numpy as np

from util import get_data, get_xor, get_donut

from datetime import datetime

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

def entropy(y):

    N = len(y)

    s1 = (y ==1).sum()

    if 0 == s1or N == s1:

        return 0

    p1 = float(s1) / N

    p0 = 1 – p1

    return-p0*np.log2(p0) – p1*np.log2(p1)

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

class TreeNode:

    def __init__(self, depth=0, max_depth=None):

       self.depth = depth

       self.max_depth = max_depth

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

    def fit(self, X,Y):

        iflen(Y) == 1 or len(set(Y)) == 1:

           self.col = None

           self.split = None

           self.left = None

           self.right = None

           self.prediction = Y[0]

        else:

            D =X.shape[1]

            cols = range(D)

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

            max_ig = 0

            best_col = None

           best_split = None

            forcol in cols:

               ig, split = self.find_split(X, Y, col)

               if ig > max_ig:

                   max_ig = ig

                   best_col = col

                   best_split = split

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

            ifmax_ig == 0:

                self.col = None

               self.split = None

               self.left = None

               self.right = None

               self.prediction = np.round(Y.mean())

           else:

               self.col = best_col

               self.split = best_split

Ипроверяем последний предельный случай – при достижении максимальной глубиныразделения прекращаются. В противном случае – делаем рекурсию. Не забывайте прикаждом прохождении добавлять единицу к текущей глубине.

                if self.depth == self.max_depth:

                   self.left = None

                   self.right = None

                   self.prediction = [

                       np.round(Y[X[:,best_col] < self.split].mean()),

                       np.round(Y[X[:,best_col] >= self.split].mean()),

                   ]

               else:

                   left_idx = (X[:,best_col] < best_split)

                   Xleft = X[left_idx]

                   Yleft = Y[left_idx]

                   self.left = TreeNode(self.depth + 1, self.max_depth)

                   self.left.fit(Xleft, Yleft)

                   right_idx = (X[:,best_col] >= best_split)

                   Xright = X[right_idx]

                   Yright = Y[right_idx]

                   self.right = TreeNode(self.depth + 1, self.max_depth)

                   self.right.fit(Xright, Yright)

Переходимк определению функции find_split. Вначале отсортируем наши Xи Y, для чего нам понадобится функция argsort:

    def find_split(self, X, Y, col):

        x_values= X[:, col]

        sort_idx= np.argsort(x_values)

        x_values= x_values[sort_idx]

        y_values= Y[sort_idx]

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

        boundaries = np.nonzero(y_values[:-1] != y_values[1:])[0]

       best_split = None

        max_ig =0

        for i inboundaries:

           split = (x_values[i] + x_values[i+1]) / 2

            ig =self.information_gain(x_values, y_values, split)

            ifig > max_ig:

               max_ig = ig

               best_split = split

        returnmax_ig, best_split

Далеепереходим к функции information_gain, вычисляющей прирост информации.

    definformation_gain(self, x, y, split):

        y0 = y[x< split]

        y1 = y[x>= split]

        N =len(y)

        y0len =len(y0)

        if y0len== 0 or y0len == N:

           return 0

        p0 = float(len(y0)) / N

        p1 = 1 –p0

        returnentropy(y) – p0*entropy(y0) – p1*entropy(y1)

Послеэтого определим функцию predict_one для предельного случая.

    def predict_one(self, x):

        ifself.col is not None and self.split is not None:

           feature = x[self.col]

            iffeature < self.split:

               if self.left:

                   p = self.left.predict_one(x)

               else:

                   p = self.prediction[0]

           else:

               if self.right:

                   p = self.right.predict_one(x)

               else:

                   p = self.prediction[1]

        else:

            p =self.prediction

        return p

Следующее – функция predict.

    def predict(self, X):

        N =len(X)

        P =np.zeros(N)

        for i inxrange(N):

            P[i]= self.predict_one(X[i])

        return P

Крометого, определим избыточный класс DecisionTree. Он имеетпрактически те же функции, но только работает на максимальной глубине.

class DecisionTree:

    def __init__(self, max_depth=None):

       self.max_depth = max_depth

Функции fit, predict и score:

    def fit(self, X, Y):

       self.root = TreeNode(max_depth=self.max_depth)

       self.root.fit(X, Y)

    def predict(self, X):

        returnself.root.predict(X)

    def score(self, X, Y):

        P =self.predict(X)

        returnnp.mean(P == Y)

Иможно переходить к функции main.

if __name__ == ‘__main__’:

    X, Y =get_data()

    idx =np.logical_or(Y == 0, Y == 1)

    X = X[idx]

    Y = Y[idx]

    # X, Y =get_xor()

    # X, Y =get_donut()

    Ntrain =len(Y) / 2

    Xtrain,Ytrain = X[:Ntrain], Y[:Ntrain]

    Xtest, Ytest= X[Ntrain:], Y[Ntrain:]

Вызываемнаш класс DecisionTree и устанавливаем таймер.

    model =DecisionTree()

    t0 =datetime.now()

   model.fit(Xtrain, Ytrain)

    print“Training time:”, (datetime.now() – t0)

    t0 =datetime.now()

    print“Train accuracy:”, model.score(Xtrain, Ytrain)

    print“Time to compute train accuracy:”, (datetime.now() – t0)

    t0 =datetime.now()

    print“Test accuracy:”, model.score(Xtest, Ytest)

    print“Time to compute test accuracy:”, (datetime.now() – t0)

Понравилась статья? Поделить с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: