-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathrandomforest.pyx
More file actions
179 lines (137 loc) · 6.08 KB
/
Copy pathrandomforest.pyx
File metadata and controls
179 lines (137 loc) · 6.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
# distutils: language=c++
import numpy as np
cimport numpy as np
cimport cython
from numpy cimport ndarray, float64_t, int_t
from libcpp cimport bool
from libc.math cimport ceil, sqrt
cdef int predict_recursive(node, data_row):
if 'end_node' in node:
return node['y_hat']
if data_row[node['predictor']] < node['split_point']:
return predict_recursive(node['left_node'], data_row)
else:
return predict_recursive(node['right_node'], data_row)
cdef class RandomForest:
cdef list random_forest
def __cinit__(self, list random_forest):
self.random_forest = random_forest
cpdef ndarray[int_t] predict(self, ndarray[float64_t, ndim=2] data):
cdef:
ndarray[int_t] predictions = np.array([], dtype=np.int)
int prediction
size_t i
for i in range(data.shape[0]):
prediction = self.get_random_forest_prediction(data[i])
predictions = np.append(predictions, prediction)
return predictions
cdef int get_random_forest_prediction(self, data_row):
cdef ndarray[int_t] predictions = np.array([], dtype=np.int)
for tree in self.random_forest:
y_hat = predict_recursive(tree, data_row)
predictions = np.append(predictions, y_hat)
return np.bincount(predictions).argmax()
'''-------------------------------------------------------------------------------------------------------'''
cdef ndarray[float64_t, ndim=2] get_bootstrap(ndarray[float64_t, ndim=2] data):
return data[np.random.choice(data.shape[0], data.shape[0]), :]
cdef bool is_pure(ndarray[int_t, ndim=1] Y):
return np.unique(Y).size == 1
cdef add_endnode(dict node, bool left, bool right):
cdef int most_common_class
if left:
most_common_class = np.bincount(node['left'][:, -1].astype('int')).argmax()
node['left_node'] = {'end_node': True, 'y_hat': most_common_class}
del node['left']
if right:
most_common_class = np.bincount(node['right'][:, -1].astype('int')).argmax()
node['right_node'] = {'end_node': True, 'y_hat': most_common_class}
del node['right']
#@cython.wraparound(False)
@cython.boundscheck(False)
@cython.cdivision(True)
cpdef double gini_index(ndarray[float64_t, ndim=2] left, ndarray[float64_t, ndim=2] right):
cdef:
double purity = 0.0
double class_ratio
ndarray[float64_t, ndim=2] split
ndarray[int_t, ndim=1] class_counts, unique_classes
int total_classes, bi, i
for bi in range(2):
if bi == 0:
split = left
else:
split = right
class_counts = np.bincount(split[:, -1].astype('int'))
unique_classes = np.array(np.nonzero(class_counts))[0]
for i in range(unique_classes.shape[0]):
class_ratio = <double>class_counts[unique_classes[i]] / split.shape[0]
purity += class_ratio * (1 - class_ratio)
return purity
@cython.boundscheck(False)
@cython.wraparound(False)
@cython.cdivision(True)
cpdef dict get_best_split(ndarray[float64_t, ndim=2] data):
cdef:
ndarray[float64_t, ndim=2] left, right, b_left, b_right
double split_point, b_split_point, gini, b_gini = 999.9
int b_predictor, pred_i, predictor, row_i
int num_random_predictors = <int>ceil(sqrt(data.shape[1]-1)) # size of random_predictors array
ndarray[int_t, ndim=1] random_predictors = np.random.choice(data.shape[1]-1, num_random_predictors, replace=False)
for pred_i in range(random_predictors.shape[0]):
predictor = random_predictors[pred_i]
# Split data 1. For every predictor value => For every row, to get best left / right split
for row_i in range(data.shape[0]):
split_point = data[row_i][predictor]
left = data[data[:, predictor] < split_point]
right = data[data[:, predictor] >= split_point]
gini = gini_index(left, right)
if gini < b_gini:
b_gini, b_split_point, b_predictor = gini, split_point, predictor
b_left, b_right = left.copy(), right.copy()
# TODO add proportional gini change for Variable-Importance measure
return {'left': b_left, 'right': b_right, 'split_point': b_split_point, 'predictor': b_predictor, 'gini': b_gini}
cdef dict recurse_tree(dict node, int depth, int max_depth, int max_x):
cdef:
dict left_node, right_node
# CHECK Zero-Node left or right => both have same class
if node['left'].shape[0] == 0 or node['right'].shape[0] == 0:
if node['left'].shape[0] == 0:
node['left'] = node['right']
else:
node['right'] = node['left']
add_endnode(node, left=True, right=True)
if depth == 1:
return node
return
# CHECK branch depth
if depth >= max_depth:
add_endnode(node, left=True, right=True)
return
# CHECK max_x & convergence else: recurse further
if node['left'].shape[0] <= max_x or is_pure(node['left'][:, -1].astype('int')):
add_endnode(node, left=True, right=False)
else:
left_node = get_best_split(node['left'])
del node['left']
node['left_node'] = left_node
recurse_tree(node['left_node'], depth+1, max_depth, max_x)
if node['right'].shape[0] <= max_x or is_pure(node['right'][:, -1].astype('int')):
add_endnode(node, right=True, left=False)
else:
right_node = get_best_split(node['right'])
del node['right']
node['right_node'] = right_node
recurse_tree(node['right_node'], depth+1, max_depth, max_x)
# entire decision-tree
return node
# labels have to be last column
cpdef create_forest(ndarray[float64_t, ndim=2] data, int n_trees, int max_depth, int max_x):
cdef:
list random_forest = []
dict tree, root_node
size_t i
for i in range(n_trees):
root_node = get_best_split(get_bootstrap(data))
tree = recurse_tree(root_node, 1, max_depth, max_x)
random_forest.append(tree)
return RandomForest(random_forest)