program辅导 、讲解 c++，java 程序设计
we want to implement random forest for classification from scratch based on the decision tree. The algorithm of the random forest is shown below.
Algorithm15.1RandomForestforRegressionorClassification. 1.For6=1toB:
(a)DrawabootstrapsampleZ*ofsizeN fromthetrainingdata.
(b)Growarandom-foresttreeTotothebootstrappeddata,byre- cursivelyrepeatingthefollowingstepsfo reachterminalnodeo f
thetree,untiltheminimumnodesizeminisreached. i.Selectm variablesatrandomfromthepvariables.
ii.Pickthebestvariable/split-pointamongthem. ii.Splitthenodeintotwodaughternodes.
2.Outputtheensembleoftrees{To}I. Tomakeapredictionatanewpointx:
Regression:f F (x)=B E B , T6(x).
Classification:LetC(x)betheclasspredictionofthebthrandom-forest tree.Thenf ( x ) =majorityvote{C(x)}₽.
This task consists of two parts, a short essay, and programming.
Part I, you need to write a short essay to answer the following questions.
1. Please compare Decision Tree method, and Random Forest for classification task. If necessary, please include references properly.
)
2. Please illustrate how you could implement random forest with the help of python class DecisionTree . You can write some pseudo code for better illustration. [The short essay should be around 500 words. ]
Part II Implementation of Random forest from scratch.
1. Implement the decision tree
First, you should write a class that implements the decision tree for a classification task. You will need this to fit the Random Forest later.
In [ ]:
In [ ]:
class DecisionTree:
def __init__(self, num_classes=None, max_depth=3, cost_fn=cost_misclassification, min_leaf_instances=1):
self.max_depth = max_depth
self.root = None
self.cost_fn = cost_fn
self.num_classes = num_classes #stores the total number of classes
self.min_leaf_instances = min_leaf_instances #minimum number of instances in a leaf for termination
#maximum dept for termination
#stores the root of the decision tree
#stores the cost function of the decision tree
def fit(self, data, labels ):
pass #pass in python 3 means nothing happens and the method here is empty
def predict(self, data_test): pass
In [ ]:
import numpy as np
#%matplotlib notebook
%matplotlib inline
import matplotlib.pyplot as plt
from IPython.core.debugger import set_trace np.random.seed(1234)
2. Let's start work on the implementation of random forest.
The skeleton of python class randomforest is provided. Please, implement the two important python methods, fit , and predict . Below is the description for the arguements,
We are creating a random forest regressor, although the same code can be slightly modified to create a classifier. To start out, we need to know what our black box takes as input to yield the output (prediction) so we need to know the parameters that define our random forest : x: independent variables of training set. To keep things minimal and simple I am not creating a separate fit method hence the base class constructor will accept the training set.
x or y : the random and corresponding dependent variables necessary for supervised learning (Random forest is a supervised learning technique)
n_trees : number of uncorrelated trees we ensemble to create the random forest.
n_features : the number of features to sample and pass onto each tree, this is where feature bagging happens. It can either be "sqrt" , "log2" or an integer. In case of sqrt, the number of
features sampled to each tree is square root of total features and log base 2 of total features in case of log2.
sample_size : the number of rows randomly selected and passed onto each tree. This is usually equal to total number of rows but can be reduced to increase performance and decrease correlation of trees in some cases (bagging of trees is a completely separate machine learning technique) depth: depth of each decision tree. Higher depth means more number of splits which increases the over fitting tendency of each tree but since we are aggregating several uncorrelated trees, over fitting of individual trees hardly bothers the whole forest.
min_leaf : minimum number of samples required in a node to cause further split. Lower the min_leaf, higher the depth of the tree. cost_fn : objective function for decision tree.
class RandomForest():
def __init__(self, depth=10, min_leaf=5, n_trees = 8, n_features='log2', sample_sz = 20, cost_fn =cost_misclassification):
np.random.seed(12)
self.depth, self.min_leaf = depth, min_leaf
self.n_trees = n_trees
self.sample_sz, self.n_features = sample_sz, n_features self.cost_fn = cost_fn
def fit(self, x, y):
#---------- fit training data with the help of function __create_tree__ -----# # --- implete step 1 -------#
pass
def __create_tree__(self):
#---------- create and return one decision tree ---------------------#
#--- implete (a) and (b) of step 1 in random forest the algorithm in this python method ---- # # return DecisionTree(...)
pass
def predict(self, x):
#---------- return the predicted probability for test data ----------# pass
## Load data
from sklearn import datasets
dataset = datasets.load_iris()
x, y = dataset['data'], dataset['target']
(num_instances, num_features), num_classes = x.shape, np.max(y)+1 inds = np.random.permutation(num_instances)
#train-test split)
x_train, y_train = x[inds[:100]], y[inds[:100]]
x_test, y_test = x[inds[100:]], y[inds[100:]]
In [ ]:
In [ ]: In [ ]:
Only use the first two features as the x and y axis for the 2D visualization.
Use different shape to represent training data and testing data.
Use different color to represent different labels.
Use different shape to mark correct prediction and misclassificaiton for testing samples. Include a legend for the above symbols.
#----- (1) we fit the tree to the training data and predict on the test data. ---##
# ----(2) visualization for results ------------------------------------------
The intention of this post is to make students and ourselves more familiar with the general working of random forests for it’s better application and debugging in future. Random forests have many more parameters and associated complexities that could not be covered in a single post by me. To study a more robust and wholesome code I suggest you read the sklearn module’s random forest code which is open source.
Part 3 Experiments and visualization.
In this section, you need to use the self-implemented random forest to build classification model for Iris dataset.
(1) We fit the random forest to the training data and predict on the test data. Please also report the test accuracy. [It should be about or higher than 96%] Please use gini index as the cost function.
(2) Please visualize the result using scattered plots, with the following elements.