Random Forest

Random Forest——随机森林

上一篇是讲到了决策树,这篇就来讲一下树的集合,随机森林。

①Aggregation Model

随机森林还是没有脱离聚合模型这块,之前学过两个aggregation model,bagging和decision tree,一个是边learning边uniform。首先是boostrap方式得到数据D1,之后训练做平均;另一个也是边learning但是做的是condition,直接用数据D做conditional切分。

Random Forest
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

所以random forest由两方面组成,bagging和random forest。
Random Forest

random forest有三个优点,1.决策树可以由不同的主机生成,效率高。2.随机森林继承了CART的有点。3.以bagging的形式结合在一起,避免了过拟合。
Random Forest

上面所讲的指数基本的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)的时候,都可以重新选择子特征来训练,从而得到更具有多样性的决策树。
Random Forest

所以改进一下:
Random Forest
subspace

上面我们讲的是随机抽取特征,除此之外,还可以将现有的特征x,通过数组p进行线性组合,来保持多样性:
Random Forest

这种方法得到的就不再是d的子空间集合了,而是得到线性的组合,比如在二维平面上只能是x,y维度。但是转换之后就是斜线。而不同的pi是不一样的,而且向量pi中大部分元素为零,因为我们选择的只是一部分特征,这是一种低维映射:
Random Forest

于是,能力又强了一点,random-subspace变成了random-combination,这里就很像是perceptron模型了。事实上我想了一会才感觉到很像......
Random Forest

下面的代码实现还不会用到这些,因为还是麻烦了点,之后有时间再看看改进吧。

③Out-Of-Bag Estimate

再来探讨一下对于boostrap的一些内容和理解。
我们通过了boostrap得到了数据D1,数据D1里面既有原数据D里面有的,也可能没有里面有的。红色的*就代表没有,也叫做红色表示的样本被称为out-of-bag(OOB) example。

Random Forest

那么他到底有多少?可以根据有关公式算一下:
Random Forest

1/N就是抽中的概率。那么抽不中就(1 - 1/N),多次就是N次方了。化简一下约等于1/e。其实这里的≈不太准确,因为N -> lim是有(1 + 1/N)^N = e。
所以,是有大约百分之30的数据是抽不到的。
貌似是和之前学过validation有点像,来对比一下:
Random Forest

在validation里面,Dtrain是用来得到gt的,Dtrain和Dval是倍数关系,并且没有交集,而OOB里面在bag外的数据是*号的,也没有参与到decision tree的create当中。那么我们是否可以用OOB的数据来代替validation呢?其实完全可以的,因为OOB类比过去就是Dval数据。那么整一个G的performance要怎么计算?我们可以计算g的然后平均,比如当前有5个gt,我们分别计算他手下的OOB的Eval作为这个g的performance,平均即可。
Random Forest

这种self-validation相比于validation来说还有一个优点就是它不需要重复训练。如下图左边所示,在通过Dval选择到表现最好的g之后,还需要在Dtrain和Dval组成的所有样本集D上重新对该模型g训练一次,以得到最终的模型系数。但是self-validation在调整随机森林算法相关系数并得到最小的EooB之后,就完成了整个模型的建立,无需重新训练模型。更重要的是,random forest的self-validation在衡量G的表现上通常相当准确。
Random Forest

④Feature Selection

在feature选择的过程中,还有一类问题要注意。选择的过程中有可能遇到多余的问题,比如抽取到生日和年龄,这就尴尬了。另一种是不相关的。

Random Forest

特征选择优点:
提高效率,特征越少,模型越简单
正则化,防止特征过多出现过拟合
去除无关特征,保留相关性大的特征,解释性强

缺点:
筛选特征的计算量较大
不同特征组合过拟合是有可能出现的
容易选到无关特征,解释性差

Random Forest

在上一篇实现决策树的里面使用的decision stump就是一种feature selection。
问题来了,我们要怎么选择有用的特征?
Random Forest

其中的一种方法就是做特征重要性的排序,选择前几个。这种方法如果在线性模型里面是很好计算的,线性可分模型。如果是非线性可分的话,权值不是一一对应的,因为通常是做了feature transform的,所以权值是交叉再一起。所以非线性就会很难。
Random Forest

上图是linear model可以使用的,并且效果不差。只需要选择最大的权值|W|就好了。
RF中,特征选择的核心思想是random test。random test的做法是对于某个特征,如果用另外一个随机值替代它之后的表现比之前更差,则表明该特征比较重要,所占的权重应该较大,不能用一个随机值替代。相反,如果随机值替代后的表现没有太大差别,则表明该特征不那么重要,可有可无。就好像班里面学习好的突然有一天死了,老师立马就可以发现,但是对于成绩差的挂了一个学期都不一定知道。所以,通过比较某特征被随机值替代前后的表现,就能推断出该特征的权重和重要性。
问题来了,我们应该如何选择随机值来替代?
①是使用uniform或者是Gaussian插入随机值。
②是把数据的第i个特征打乱了看看打乱之后效果差别大不大。

相比起来,其实第二种更加好,因为如果本来的不是高斯分布可能就会打乱了数据的分布方式,而第二种在大体上数据的分布是不改变的。之后我们可以比较variance,大的那么就是比较重要了。
Random Forest

这样就又有了一个问题,我们要如何衡量改变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

⑤代码实现

Random Forest in Action

最后,我们通过实际的例子来看一下RF的特点。首先,仍然是一个二元分类的例子。如下图所示,左边是一个C&RT树没有使用bootstrap得到的模型分类效果,其中不同特征之间进行了随机组合,所以有斜线作为分类线;中间是由bootstrap(N’=N/2)后生成的一棵决策树组成的随机森林,图中加粗的点表示被bootstrap选中的点;右边是将一棵决策树进行bagging后的分类模型,效果与中间图是一样的,都是一棵树。


Random Forest

当t=100,即选择了100棵树时,中间的模型是第100棵决策树构成的,还是只有一棵树;右边的模型是由100棵决策树bagging起来的,如下图所示:


Random Forest

当t=200时:
Random Forest

当t=300时:


Random Forest

当t=400时:
Random Forest

当t=500时:
Random Forest

当t=600时:
Random Forest

当t=700时:
Random Forest

当t=800时:


Random Forest

当t=900时:
Random Forest

当t=1000时:
Random Forest

随着树木个数的增加,我们发现,分界线越来越光滑而且得到了large-margin-like boundary,和之前磕磕绊绊的相比光滑了不少,类似于SVM一样的效果。也就是说,树木越多,分类器的置信区间越大。

然后,我们再来看一个比较复杂的例子,二维平面上分布着许多离散点,分界线形如sin函数。当只有一棵树的时候(t=1),下图左边表示单一树组成的RF,右边表示所有树bagging组合起来构成的RF。因为只有一棵树,所以左右两边效果一致。


Random Forest

当t=6时:


Random Forest

当t=11时:
Random Forest

当t=16时:


Random Forest

当t=21时:
Random Forest

可以看到,当RF由21棵树构成的时候,分界线就比较平滑了,而且它的边界比单一树构成的RF要robust得多,更加平滑和稳定。
最后,基于上面的例子,再让问题复杂一点:在平面上添加一些随机噪声。当t=1时,如下图所示:
Random Forest

当t=6时:
Random Forest

当t=11时:


Random Forest

当t=16时:
Random Forest

当t=21时:
Random Forest

从上图中,我们发现21棵树的时候,随机noise的影响基本上能够修正和消除。这种bagging投票的机制能够保证较好的降噪性,从而得到比较稳定的结果。
经过以上三个例子,我们发现RF中,树的个数越多,模型越稳定越能表现得好。在实际应用中,应该尽可能选择更多的树。值得一提的是,RF的表现同时也与random seed有关,即随机的初始值也会影响RF的表现。
Random Forest

之后就是真正的代码实现了
这里使用的还是随机选择特征的方法。
首先是一个特征选择函数:

  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课树他们之前准确率的变化,画了对比图。


Random Forest

Random Forest

Random Forest

大致趋势还是可以看得出是一直不断上升,最高应该是13到15这个区间吧,但是注意到2到5棵树的时候存在了一定的颠婆,这颠婆有点厉害,个人猜测应该是采集到了某些没有用的特征导致的,后面效果好了是因为树多了效果削弱了,并且有些的特征也采集不到。这个数据维度是30维的。有时间再做一个特征重要性的选择了。

所有代码GitHub上:
https://github.com/GreenArrow2017/MachineLearning/tree/master/MachineLearning/RandomForest

上一篇:支持向量机(Support Vector Machine)


下一篇:Decision Tree