coding utf8 recursive implementation of decision tree def initself regressionfalse criterionnone nclassesnone self regression regression self impurity none self threshold none self columnindex none self outcome none self criterion criterion self loss none self nclasses nclasses only for classification self leftchild none self rightchild none property def isterminalself return not boolself leftchild and self rightchild def findsplitsself x get unique values in a sorted order find a point between two values find best feature and value for a split greedy algorithm sample random subset of features subset random samplelistrange0 x shape1 nfeatures maxgain maxcol maxval none none none for column in subset splitvalues self findsplitsx column for value in splitvalues if self loss is none random forest splits splitx column targety value gain self criteriontargety splits else gradient boosting left right splitdatasetx target column value returnxfalse gain xgbcriteriontarget left right self loss if maxgain is none or gain maxgain maxcol maxval maxgain column value gain return maxcol maxval maxgain def trainself x target maxfeaturesnone minsamplessplit10 maxdepthnone minimumgain0 01 try exit from recursion using assert syntax assert x shape0 minsamplessplit assert maxdepth 0 if maxfeatures is none maxfeatures x shape1 column value gain self findbestsplitx target maxfeatures assert gain is not none if self regression assert gain 0 else assert gain minimumgain self columnindex column self threshold value self impurity gain split dataset leftx rightx lefttarget righttarget splitdatasetx target column value grow left and right child self leftchild treeself regression self criterion self nclasses self leftchild train leftx lefttarget maxfeatures minsamplessplit maxdepth 1 minimumgain self rightchild treeself regression self criterion self nclasses self rightchild train rightx righttarget maxfeatures minsamplessplit maxdepth 1 minimumgain except assertionerror self calculateleafvaluetarget def trainself x target maxfeaturesnone minsamplessplit10 maxdepthnone minimumgain0 01 lossnone if not isinstancetarget dict target y target loss for gradient boosting if loss is not none self loss loss if not self regression self nclasses lennp uniquetarget y self trainx target maxfeaturesmaxfeatures minsamplessplitminsamplessplit maxdepthmaxdepth minimumgainminimumgain def calculateleafvalueself targets gradient boosting random forest mean value for regression task probability for classification task predict single row if not self isterminal if rowself columnindex self threshold return self leftchild predictrowrow else return self rightchild predictrowrow return self outcome def predictself x result np zerosx shape0 for i in rangex shape0 resulti self predictrowxi return result coding utf 8 recursive implementation of decision tree only for classification find all possible split values get unique values in a sorted order find a point between two values find best feature and value for a split greedy algorithm sample random subset of features random forest gradient boosting exit from recursion using assert syntax split dataset grow left and right child build a decision tree from training set parameters x array like feature dataset target dictionary or array like target values max_features int or none the number of features to consider when looking for the best split min_samples_split int the minimum number of samples required to split an internal node max_depth int maximum depth of the tree minimum_gain float default 0 01 minimum gain required for splitting loss function default none loss function for gradient boosting loss for gradient boosting find optimal value for leaf gradient boosting random forest mean value for regression task probability for classification task predict single row
import random

import numpy as np
from scipy import stats

from mla.ensemble.base import split, split_dataset, xgb_criterion

random.seed(111)


class Tree(object):
    

    def __init__(self, regression=False, criterion=None, n_classes=None):
        self.regression = regression
        self.impurity = None
        self.threshold = None
        self.column_index = None
        self.outcome = None
        self.criterion = criterion
        self.loss = None
        self.n_classes = n_classes  

        self.left_child = None
        self.right_child = None

    @property
    def is_terminal(self):
        return not bool(self.left_child and self.right_child)

    def _find_splits(self, X):
        
        split_values = set()

        
        x_unique = list(np.unique(X))
        for i in range(1, len(x_unique)):
            
            average = (x_unique[i - 1] + x_unique[i]) / 2.0
            split_values.add(average)

        return list(split_values)

    def _find_best_split(self, X, target, n_features):
        

        
        subset = random.sample(list(range(0, X.shape[1])), n_features)
        max_gain, max_col, max_val = None, None, None

        for column in subset:
            split_values = self._find_splits(X[:, column])
            for value in split_values:
                if self.loss is None:
                    
                    splits = split(X[:, column], target["y"], value)
                    gain = self.criterion(target["y"], splits)
                else:
                    
                    left, right = split_dataset(X, target, column, value, return_X=False)
                    gain = xgb_criterion(target, left, right, self.loss)

                if (max_gain is None) or (gain > max_gain):
                    max_col, max_val, max_gain = column, value, gain
        return max_col, max_val, max_gain

    def _train(self, X, target, max_features=None, min_samples_split=10, max_depth=None, minimum_gain=0.01):
        try:
            
            assert X.shape[0] > min_samples_split
            assert max_depth > 0

            if max_features is None:
                max_features = X.shape[1]

            column, value, gain = self._find_best_split(X, target, max_features)
            assert gain is not None
            if self.regression:
                assert gain != 0
            else:
                assert gain > minimum_gain

            self.column_index = column
            self.threshold = value
            self.impurity = gain

            
            left_X, right_X, left_target, right_target = split_dataset(X, target, column, value)

            
            self.left_child = Tree(self.regression, self.criterion, self.n_classes)
            self.left_child._train(
                left_X, left_target, max_features, min_samples_split, max_depth - 1, minimum_gain
            )

            self.right_child = Tree(self.regression, self.criterion, self.n_classes)
            self.right_child._train(
                right_X, right_target, max_features, min_samples_split, max_depth - 1, minimum_gain
            )
        except AssertionError:
            self._calculate_leaf_value(target)

    def train(self, X, target, max_features=None, min_samples_split=10, max_depth=None, minimum_gain=0.01, loss=None):
        

        if not isinstance(target, dict):
            target = {"y": target}

        
        if loss is not None:
            self.loss = loss

        if not self.regression:
            self.n_classes = len(np.unique(target['y']))

        self._train(X, target, max_features=max_features, min_samples_split=min_samples_split,
                    max_depth=max_depth, minimum_gain=minimum_gain)


    def _calculate_leaf_value(self, targets):
        
        if self.loss is not None:
            
            self.outcome = self.loss.approximate(targets["actual"], targets["y_pred"])
        else:
            
            if self.regression:
                
                self.outcome = np.mean(targets["y"])
            else:
                
                self.outcome = np.bincount(targets["y"], minlength=self.n_classes) / targets["y"].shape[0]

    def predict_row(self, row):
        
        if not self.is_terminal:
            if row[self.column_index] < self.threshold:
                return self.left_child.predict_row(row)
            else:
                return self.right_child.predict_row(row)
        return self.outcome

    def predict(self, X):
        result = np.zeros(X.shape[0])
        for i in range(X.shape[0]):
            result[i] = self.predict_row(X[i, :])
        return result