Bagging是指的个体学习器间不存在强依赖关系、可同时生成的并行化方法。

Bagging基于自助采样法，给定包含Bagging - 图1个样本的数据集，我们随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过Bagging - 图2次操作，我们得到含Bagging - 图3个样本的采样集，初始训练集里有的样本在采样集里多次出现，有的则从未出现。由Bagging - 图4可知初始训练集约有Bagging - 图5的样本出现在采样集中，Bagging - 图6未出现在采样集中。

照这样，我们可采集出Bagging - 图7个含Bagging - 图8个训练样本的训练集，然后基于每个采样集训练出一个基学习器，再将这些学习器进行结合。Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。

值得一提的是，自助采样过程还给Bagging带来了另一个有点：由于每个基学习器只使用了初始训练集中约Bagging - 图9的样本，剩下的样本可用作验证集来对泛化性能进行“包外估计”。

随机森林(Random Forest)

随机森林在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择。具体来说，在随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含Bagging - 图10个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数Bagging - 图11控制了随机性的引入程度：若Bagging - 图12，则基决策树的构建与传统决策树相同；若令Bagging - 图13，则是随机选择一个属性用于划分；一般情况下，推荐值Bagging - 图14。

随机森林的训练效率常常优于纯Bagging思想的决策树群，因为在个体决策树的构建过程中，Bagging使用的是“确定型”决策树，在选择划分属性时要对结点的所有属性进行考察，而随即森林使用的“随机型”决策树则只考察一个属性子集。

可以看出，随机森林对Bagging只做了小改动，但是与Bagging中基学习器的“多样性”仅通过样本扰动（通过对初始训练样本采样）而来不同，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得集成的泛化性能可通过个体学习器之间差异度的增加而进一步提升。

Code实现

  1. # -*- coding: UTF-8 -*-
  2. import sys
  3. import math
  4. from DecisionTree import DecisionTreeClassifier
  6. def mymode(X, n_tree, n_samples):
  7.     predictions = []
  8.     for i in range(n_samples):
  9.         d = {}
  10.         for j in range(n_tree):
  11.             x = X[j][i]
  12.             if x not in d:
  13.                 d[x] = 0
  14.             d[x] += 1
  15.         res = [ (x, d[x]) for x in d ]
  16.         res = sorted(res, key=lambda x:x[1], reverse=True)
  17.         predictions.append( res[0][0] )
  18.     return predictions 
  20. def load_data(file_name):
  21.     X = []
  22.     y = []
  23.     with open(file_name, "r") as f:
  24.         for l in f:
  25.             sp = l.strip("\n").split(" ")
  26.             label = int(sp[0])
  27.             y.append(label)
  28.             fea = []
  29.             for i in range(1, len(sp)):
  30.                 fea.append( float( sp[i].split(":")[1] ) )
  31.             X.append(fea)
  32.     return (X), (y)
  34. def shuffle_in_unison(a, b):
  35.     import random
  36.     random.seed(100)
  37.     all = [ (a[i], b[i]) for i in range(len(a)) ]
  38.     random.shuffle(all)
  39.     na = [ x[0] for x in all ]
  40.     nb = [ x[1] for x in all ]
  41.     return na, nb
  43. def gini(Y):
  44.     distribution = Counter(Y)
  45.     s = 0.0
  46.     total = len(Y)
  47.     for y, num_y in distribution.items():
  48.         probability_y = float (num_y/total)
  49.         s += (probability_y)*math.log(probability_y)
  50.     return -s
  52. def gini_gain(y, y_true, y_false):
  53.     return gini(y) - (gini(y_true)*len(y_true) + gini(y_false)*len(y_false))/len(y)
  55. class RandomForestClassifier(object):
  56.     def __init__(self, n_estimators=32, max_features=lambda x: x, max_depth=20,
  57.         min_samples_split=2, bootstrap=0.632):
  58.         self.n_estimators = n_estimators
  59.         self.max_features = max_features
  60.         self.max_depth = max_depth
  61.         self.min_samples_split = min_samples_split
  62.         self.bootstrap = bootstrap
  63.         self.forest = []
  65.     def fit(self, X, y):
  66.         self.forest = []
  67.         n_samples = len(y)
  68.         n_sub_samples = int(round(n_samples*self.bootstrap))
  69.         for i in xrange(self.n_estimators):
  70.             X, y = shuffle_in_unison(X, y)
  71.             X_subset = [ X[i] for i in range(n_sub_samples) ]
  72.             y_subset = [ y[i] for i in range(n_sub_samples) ]
  74.             tree = DecisionTreeClassifier(self.max_features, self.max_depth,
  75.                                             self.min_samples_split)
  76.             tree.fit(X_subset, y_subset)
  77.             self.forest.append(tree)
  79.     def predict(self, X):
  80.         n_samples = len(X)
  81.         n_trees = len(self.forest)
  82.         predictions = [ [ 0 for i in range(n_samples) ] for j in range(n_trees) ]
  83.         for i in xrange(n_trees):
  84.             predictions[i] = self.forest[i].predict(X)
  85.         return mymode(predictions, n_trees, n_samples)
  87.     def score(self, X, y):
  88.         y_predict = self.predict(X)
  89.         n_samples = len(y)
  90.         correct = 0
  91.         for i in xrange(n_samples):
  92.             if y_predict[i] == y[i]:
  93.                 correct = correct + 1
  94.         accuracy = correct/float(n_samples)
  95.         return accuracy
  97. if __name__ == "__main__":
  98.     train_file = sys.argv[1]
  99.     test_file = sys.argv[2]
  100.     train_x, train_y = load_data( train_file )
  101.     test_x, test_y = load_data(test_file)
  102.     # print "Load data finish..."
  103.     rf = RandomForestClassifier(n_estimators=32, max_depth=20)
  104.     rf.fit(train_x, train_y)
  105.     # print "test acc:", rf.score(test_x, test_y) 
  106.     preds = rf.predict(test_x)
  108.     # print "confusion matrix:"
  109.     class_num = 0
  110.     class_map = {}
  111.     class_index = 0
  112.     for i in train_y:
  113.         if i not in class_map:
  114.             class_map[i] = class_index
  115.             class_index += 1
  116.             class_num += 1
  117.     for i in preds:
  118.         if i not in class_map:
  119.             class_map[i] = class_index
  120.             class_index += 1
  121.             class_num += 1
  122.     matrix = [ [ 0 for i in range(class_num) ] for j in range( class_num ) ]
  123.     for i in range( len(test_y) ):
  124.         actual = test_y[i]
  125.         pred = preds[i]
  126.         matrix[ class_map[ actual ] ] [ class_map[pred] ] += 1
  127.     for i in matrix:
  128.         print " ".join( [ str(x) for x in i ] )