CART决策树和随机森林

CART

1. 分裂规则

•  将现有节点的数据集分裂成两个子集，计算每个子集的Gini index
• 子集的Gini index：gini_{child}=\sum_{i=1}^K p_{i} \sum_{i' \neq i} p_{i'}=1-\sum_{i=1}^K p_{i}^2 ， 其中K表示分类的类别个数，p_{i}表示类别为i的样本在子集中的比例，Gini index可以理解为该子集中的数据被错误分类的期望损失
• 分裂后总的Gini index：gini_s= \frac{N_1}{N}gini_{child_1}+\frac{N_2}{N}gini_{child_2} ，其中N为分裂之前的样本数，N_1和N_2为分裂之后两个子集的样本数
• 记分裂前的节点的数据集的Gini index为gini_p，选取使得gini_s相对于gini_p减少最多的特征和分裂点进行分裂

2. 减少过拟合

• 设置树的最大深度(max_depth in sklearn.tree.DecisionTreeClassifier)
• 设置每个叶子节点的最少样本个数(min_samples_leaf in sklearn.tree.DecisionTreeClassifier)
• 剪枝

3. 样本均衡问题

• 若样本的类别分布极不均衡，可对每个类别i赋予一个权重w_i ，样本较少的类赋予较大的权重(class_weight in sklearn.tree.DecisionTreeClassifier)
• 此时算法中所有用到类别样本个数的地方均转换成类别样本权重和。例如p_{i}={w_{i}m_i}/{\sum_{i=1}^K w_{i}m_i} ，其中m_i为在子集中类别为i的样本个数。此时分裂后总的Gini index为gini_s=\frac{weight\_sum(N_1)}{weight\_sum(N)}gini_{child_1}+\frac{weight\_sum(N_2)}{weight\_sum(N)}gini_{child_2}

4. 回归问题

• 和分类问题相似，只是将分裂规则中的Gini index变为了Mean Squared Error，即MSE_{child}=\frac{1}{N_{child}}\sum_{j \in child}(y_j-\bar{y}_{child})^2

---

Random Forest

1. 随机性

• 在建立每个新的决策树的时候通过bootstrap方法(bootstrap in sklearn.ensemble.RandomForestClassifier)从N个训练样本中有放回地随机选出一定数量(max_samples in sklearn.ensemble.RandomForestClassifier)的样本进行训练
• 在每次进行节点分裂的时候从所有特征中随机选取部分特征进行查找(max_features in sklearn.ensemble.RandomForestClassifier)

2. 样本均衡问题

• 同CART一样，样本较少的类赋予较大的权重(class_weight in sklearn.ensemble.RandomForestClassifier)
• 需要注意的是权重对于bootstrap的使用并没有影响，即bootstrap方法始终是等概率地从N个样本中选择，sklearn中的源码如下：
• if forest.bootstrap: n_samples = X.shape[0] if sample_weight is None: curr_sample_weight = np.ones((n_samples,), dtype=np.float64) else: ### 若class_weight为'balanced'或dict类型，此时的样本权重中已经包含了类别权重 curr_sample_weight = sample_weight.copy() indices = _generate_sample_indices(tree.random_state, n_samples) #bootstrap sample_counts = np.bincount(indices, minlength=n_samples) curr_sample_weight *= sample_counts #根据新的样本集合中每个原始样本出现的次数来调整样本权重 ### 若class_weight为'subsample'或'balanced_subsample'，根据类别权重调整样本权重 if class_weight == 'subsample': with catch_warnings(): simplefilter('ignore', DeprecationWarning) curr_sample_weight *= compute_sample_weight('auto', y, indices) elif class_weight == 'balanced_subsample': curr_sample_weight *= compute_sample_weight('balanced', y, indices) tree.fit(X, y, sample_weight=curr_sample_weight, check_input=False) else: tree.fit(X, y, sample_weight=sample_weight, check_input=False)

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  if forest.bootstrap:     n_samples = X.shape[0]     if sample_weight is None:         curr_sample_weight = np.ones((n_samples,), dtype=np.float64)     else:         ### 若class_weight为'balanced'或dict类型，此时的样本权重中已经包含了类别权重         curr_sample_weight = sample_weight.copy()     indices = _generate_sample_indices(tree.random_state, n_samples) #bootstrap     sample_counts = np.bincount(indices, minlength=n_samples)     curr_sample_weight *= sample_counts #根据新的样本集合中每个原始样本出现的次数来调整样本权重     ### 若class_weight为'subsample'或'balanced_subsample'，根据类别权重调整样本权重     if class_weight == 'subsample':         with catch_warnings():             simplefilter('ignore', DeprecationWarning)             curr_sample_weight *= compute_sample_weight('auto', y, indices)     elif class_weight == 'balanced_subsample':         curr_sample_weight *= compute_sample_weight('balanced', y, indices)       tree.fit(X, y, sample_weight=curr_sample_weight, check_input=False) else:     tree.fit(X, y, sample_weight=sample_weight, check_input=False)

3. OOB(out-of-bag estimate)

• 对每一个训练样本z_i=(x_i, y_i)，使用训练数据中没有该样本的那些决策树构建该样本的随机森林预测
• 针对所有训练样本计算预测准确率(oob_score_ in sklearn.ensemble.RandomForestClassifier)
• 只有bootstrap设为True时OOB才是有效的

4. 特征重要性

• 在CART决策树构建过程中使用某特征进行分裂导致的Gini index的总的减少越多，那么认为该特征的重要性就越大
• 随机森林中的特征重要性是各个决策树中的特征重要性总和或平均(feature_importances_ in sklearn.ensemble.RandomForestClassifier)