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