Random Forest——随机森林
上一篇是讲到了决策树，这篇就来讲一下树的集合，随机森林。
①Aggregation Model
随机森林还是没有脱离聚合模型这块，之前学过两个aggregation model，bagging和decision tree，一个是边learning边uniform。首先是boostrap方式得到数据D1，之后训练做平均；另一个也是边learning但是做的是condition，直接用数据D做conditional切分。
bagging and decision tree
而bagging和decision tree各自都有一个很重要的特点。bagging可以减少不同gt方差的variance的作用，因为bagging是通过各自投票，大家包含的相同样本都比较多，所以大致不会差别太远，后面uniform求平均也起到了求consensus的作用。但是decision tree有点不同，每一次的切割都是切分剩下的数据，意味着每一次如果数据是不一样的切分方式就不一样，所以对不同的数据会很敏感，所以不同的D得到的variance会大一些。
但是之前说过，越不同的g是越能反应事物的本身，比如看一个人，单单从成绩方面太狭隘了，成绩和行动力结合起来才会综合，这就是像是两个g结合在一起。所以如果g越不一样表达的方面就越不一样。既然decision tree是variance大，bagging的variance小，结合起来说不定可以取得更好的成绩，于是random forest诞生了。
②Random Forest
所以random forest由两方面组成，bagging和random forest。
random forest有三个优点，1.决策树可以由不同的主机生成，效率高。2.随机森林继承了CART的有点。3.以bagging的形式结合在一起，避免了过拟合。
上面所讲的指数基本的random forest，通过boostrap抽样得到数据D1然后训练decision tree，最后做uniform。除了这种方法之外，还有另外一种方法，随机选取数据的feature，现在有100个特征，我选取30个来构成decision tree，又选择另外的30个来构成新的一棵随机数，每一棵树都不一样。比如现在是d维，那么我们只是选择_d(_d < d)维来构建决策树。也就是说_d维z空间其实就是d维x空间的一个随机子空间（subspace）,Random Forest算法的作者建议在构建CART每个分支b(x)的时候，都可以重新选择子特征来训练，从而得到更具有多样性的决策树。
所以改进一下：
subspace
上面我们讲的是随机抽取特征，除此之外，还可以将现有的特征x，通过数组p进行线性组合，来保持多样性：
这种方法得到的就不再是d的子空间集合了，而是得到线性的组合，比如在二维平面上只能是x，y维度。但是转换之后就是斜线。而不同的pi是不一样的，而且向量pi中大部分元素为零，因为我们选择的只是一部分特征，这是一种低维映射：
于是，能力又强了一点，random-subspace变成了random-combination，这里就很像是perceptron模型了。事实上我想了一会才感觉到很像......
下面的代码实现还不会用到这些，因为还是麻烦了点，之后有时间再看看改进吧。
③Out-Of-Bag Estimate
再来探讨一下对于boostrap的一些内容和理解。
我们通过了boostrap得到了数据D1，数据D1里面既有原数据D里面有的，也可能没有里面有的。红色的*就代表没有，也叫做红色表示的样本被称为out-of-bag(OOB) example。
那么他到底有多少？可以根据有关公式算一下：
1/N就是抽中的概率。那么抽不中就(1 - 1/N)，多次就是N次方了。化简一下约等于1/e。其实这里的≈不太准确，因为N -> lim是有(1 + 1/N)^N = e。
所以，是有大约百分之30的数据是抽不到的。
貌似是和之前学过validation有点像，来对比一下：
在validation里面，Dtrain是用来得到gt的，Dtrain和Dval是倍数关系，并且没有交集，而OOB里面在bag外的数据是*号的，也没有参与到decision tree的create当中。那么我们是否可以用OOB的数据来代替validation呢？其实完全可以的，因为OOB类比过去就是Dval数据。那么整一个G的performance要怎么计算？我们可以计算g的然后平均，比如当前有5个gt，我们分别计算他手下的OOB的Eval作为这个g的performance，平均即可。
这种self-validation相比于validation来说还有一个优点就是它不需要重复训练。如下图左边所示，在通过Dval选择到表现最好的g之后，还需要在Dtrain和Dval组成的所有样本集D上重新对该模型g训练一次，以得到最终的模型系数。但是self-validation在调整随机森林算法相关系数并得到最小的EooB之后，就完成了整个模型的建立，无需重新训练模型。更重要的是，random forest的self-validation在衡量G的表现上通常相当准确。
④Feature Selection
在feature选择的过程中，还有一类问题要注意。选择的过程中有可能遇到多余的问题，比如抽取到生日和年龄，这就尴尬了。另一种是不相关的。
特征选择优点：
提高效率，特征越少，模型越简单
正则化，防止特征过多出现过拟合
去除无关特征，保留相关性大的特征，解释性强
缺点：
筛选特征的计算量较大
不同特征组合过拟合是有可能出现的
容易选到无关特征，解释性差
在上一篇实现决策树的里面使用的decision stump就是一种feature selection。
问题来了，我们要怎么选择有用的特征？
其中的一种方法就是做特征重要性的排序，选择前几个。这种方法如果在线性模型里面是很好计算的，线性可分模型。如果是非线性可分的话，权值不是一一对应的，因为通常是做了feature transform的，所以权值是交叉再一起。所以非线性就会很难。
上图是linear model可以使用的，并且效果不差。只需要选择最大的权值|W|就好了。
RF中，特征选择的核心思想是random test。random test的做法是对于某个特征，如果用另外一个随机值替代它之后的表现比之前更差，则表明该特征比较重要，所占的权重应该较大，不能用一个随机值替代。相反，如果随机值替代后的表现没有太大差别，则表明该特征不那么重要，可有可无。就好像班里面学习好的突然有一天死了，老师立马就可以发现，但是对于成绩差的挂了一个学期都不一定知道。所以，通过比较某特征被随机值替代前后的表现，就能推断出该特征的权重和重要性。
问题来了，我们应该如何选择随机值来替代？
①是使用uniform或者是Gaussian插入随机值。
②是把数据的第i个特征打乱了看看打乱之后效果差别大不大。
相比起来，其实第二种更加好，因为如果本来的不是高斯分布可能就会打乱了数据的分布方式，而第二种在大体上数据的分布是不改变的。之后我们可以比较variance，大的那么就是比较重要了。
这样就又有了一个问题，我们要如何衡量改变dimension后的D和原数据D的performance呢？
①我们可以延用之前OOB的做法，打乱i个特征，对每一个维度都要训练，如何用OOB做validation评估performance与原数据D训练出来的做比较。
②RF的作者提出了一种方法，就是把permutation的操作从原来的training上移到了OOB validation上去，记为Eoob(G(p))→E(p)oob(G)。也就是说，在训练的时候仍然使用D，但是在OOB验证的时候，将所有的OOB样本的第i个特征重新洗牌，验证G的表现。
第二种方法用的很多，计算方便，主要是效果也很好啊。
⑤代码实现
Random Forest in Action
最后，我们通过实际的例子来看一下RF的特点。首先，仍然是一个二元分类的例子。如下图所示，左边是一个C&RT树没有使用bootstrap得到的模型分类效果，其中不同特征之间进行了随机组合，所以有斜线作为分类线；中间是由bootstrap（N’=N/2）后生成的一棵决策树组成的随机森林，图中加粗的点表示被bootstrap选中的点；右边是将一棵决策树进行bagging后的分类模型，效果与中间图是一样的，都是一棵树。
当t=100，即选择了100棵树时，中间的模型是第100棵决策树构成的，还是只有一棵树；右边的模型是由100棵决策树bagging起来的，如下图所示：
当t=200时：
当t=300时：
当t=400时：
当t=500时：
当t=600时：
当t=700时：
当t=800时：
当t=900时：
当t=1000时：
随着树木个数的增加，我们发现，分界线越来越光滑而且得到了large-margin-like boundary，和之前磕磕绊绊的相比光滑了不少，类似于SVM一样的效果。也就是说，树木越多，分类器的置信区间越大。
然后，我们再来看一个比较复杂的例子，二维平面上分布着许多离散点，分界线形如sin函数。当只有一棵树的时候（t=1），下图左边表示单一树组成的RF，右边表示所有树bagging组合起来构成的RF。因为只有一棵树，所以左右两边效果一致。
当t=6时：
当t=11时：
当t=16时：
当t=21时：
可以看到，当RF由21棵树构成的时候，分界线就比较平滑了，而且它的边界比单一树构成的RF要robust得多，更加平滑和稳定。
最后，基于上面的例子，再让问题复杂一点：在平面上添加一些随机噪声。当t=1时，如下图所示：
当t=6时：
当t=11时：
当t=16时：
当t=21时：
从上图中，我们发现21棵树的时候，随机noise的影响基本上能够修正和消除。这种bagging投票的机制能够保证较好的降噪性，从而得到比较稳定的结果。
经过以上三个例子，我们发现RF中，树的个数越多，模型越稳定越能表现得好。在实际应用中，应该尽可能选择更多的树。值得一提的是，RF的表现同时也与random seed有关，即随机的初始值也会影响RF的表现。
之后就是真正的代码实现了
这里使用的还是随机选择特征的方法。
首先是一个特征选择函数：
def choose_samples(self, data, k):
'''choose the feature from data
input:data, type = list
output:k
'''
n, d = np.shape(data)
feature = []
for j in range(k):
feature.append(rd.randint(0, d - 2))
index = []
for i in range(n):
index.append(rd.randint(0, n-1))
data_samples = []
for i in range(n):
data_tmp = []
for fea in feature:
data_tmp.append(data[i][fea])
data_tmp.append(data[i][-1])
data_samples.append(data_tmp)
pass
return data_samples, feature
pass
在data数据里面选择出k维的数据。
之后就是随机森林的建立了，使用的决策树是上篇文章实现的决策树，尽量做到全是自己实现的：
def random_forest(self, data, trees_num):
'''create a forest
input:data, type = list
output:trees_result, trees_feature
'''
decisionTree = tree.decision_tree()
trees_result = []
trees_feature = []
d = np.shape(data)[1]
if d > 2:
k = int(math.log(d - 1, 2)) + 1
else:
k = 1
for i in range(trees_num):
print('The ', i, ' tree. ')
data_samples, feature = self.choose_samples(data, k)
t = decisionTree.build_tree(data_samples)
trees_result.append(t)
trees_feature.append(feature)
pass
return trees_result, trees_feature
其实都很常规，最后返回的是树的数量和选取的特征。
之后就是一个切割数据和加载数据的工具函数：
def split_data(data_train, feature):
'''select the feature from data
input:data, feature
output:data, type = list
'''
m = np.shape(data_train)[0]
data = []
for i in range(m):
data_tmp = []
for x in feature:
data_tmp.append(data_train[i][x])
data_tmp.append(data_train[i][-1])
data.append(data_tmp)
return data
def load_data():
'''use the boston dataset from sklearn'''
print('loading data......')
dataSet = load_breast_cancer()
data = dataSet.data
target = dataSet.target
for i in range(len(target)):
if target[i] == 0:
target[i] = -1
dataframe = pd.DataFrame(data)
dataframe.insert(np.shape(data)[1], 'target', target)
dataMat = np.mat(dataframe)
X_train, X_test, y_train, y_test = train_test_split(dataMat[:, 0:-1], dataMat[:, -1], test_size=0.3, random_state=0)
data_train = np.hstack((X_train, y_train))
data_train = data_train.tolist()
X_test = X_test.tolist()
return data_train, X_test, y_test
load_data是把数据3,7切分，测试和训练。
然后就是预测函数和计算准确度的函数了：
def get_predict(self, trees_result, trees_feature, data_train):
'''predict the result
input:trees_result, trees_feature, data
output:final_prediction
'''
decisionTree = tree.decision_tree()
m_tree = len(trees_result)
m = np.shape(data_train)[0]
result = []
for i in range(m_tree):
clf = trees_result[i]
feature = trees_feature[i]
data = tool.split_data(data_train, feature)
result_i = []
for i in range(m):
result_i.append( list((decisionTree.predict(data[i][0 : -1], clf).keys()))[0] )
result.append(result_i)
final_predict = np.sum(result, axis = 0)
return final_predict
def cal_correct_rate(self, target, final_predict):
m = len(final_predict)
corr = 0.0
for i in range(m):
if target[i] * final_predict[i] > 0:
corr += 1
pass
return corr/m
pass
这个和之前决策树的差不多，也是调用了之前的代码。
最后就是入口函数：
def running():
'''entrance'''
data_train, text, target = load_data()
forest = randomForest()
predic = []
for i in range(1, 20):
trees, features = forest.random_forest(data_train, i)
predictions = forest.get_predict(trees, features, text)
accuracy = forest.cal_correct_rate(target, predictions)
print('The forest has ', i, 'tree', 'Accuracy : ' , accuracy)
predic.append(accuracy)
plt.xlabel('Number of tree')
plt.ylabel('Accuracy')
plt.title('The relationship between tree number and accuracy')
plt.plot(range(1, 20), predic, color = 'orange')
plt.show()
pass
if __name__ == '__main__':
running()
计算了1到20课树他们之前准确率的变化，画了对比图。
大致趋势还是可以看得出是一直不断上升，最高应该是13到15这个区间吧，但是注意到2到5棵树的时候存在了一定的颠婆，这颠婆有点厉害，个人猜测应该是采集到了某些没有用的特征导致的，后面效果好了是因为树多了效果削弱了，并且有些的特征也采集不到。这个数据维度是30维的。有时间再做一个特征重要性的选择了。
所有代码GitHub上：
https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/RandomForest