6.10 练习题

1. 如果训练集有100万个实例，训练决策树（无约束）大致的深度是多少？

一个包含\(m\)个叶节点的均衡二叉树的深度等于\(log_2(m)\)，取整。通常来说，二元决策树（只做二元决策的树，就像Scikit-Learn中的所有树一样）训练到最后大体都是平衡的，如果不加以限制，最后平均每个叶节点一个实例。因此，如果训练集包含100万个实例，那么决策树的深度为\(log_2(10^6)\approx20\)层（实际上会更多一些，因为决策树通常不可能完美平衡）。

2. 通常来说，子节点的基尼不纯度是高于还是低于其父节点？是通常更高/更低？还是永远更高/更低？

一个节点的基尼不纯度通常比其父节点低。这是由于CART训练算法的成本函数。该算法分裂每个节点的方法，就是使其子节点的基尼不纯度的加权之和最小。但是，如果一个子节点的不纯度远小于另一个，那么也有可能使子节点的基尼不纯度比其父节点高，只要那个不纯度更低的子节点能够抵偿这个增加即可。举例来说，假设一个节点包含4个A类的实例和1个B类的实例，其基尼不纯度等于\(1-(\frac{1}{5})^2-(\frac{4}{5})^2 = 0.32\)。现在我们假设数据集是一维的，并且实例的排列顺序如下：A，B，A，A，A。你可以验证算法将在第二个实例后拆分该节点，从而生成两个子节点，分别包含的实例为A，B和A，A，A。第一个子节点的基尼不纯度为\(1-(\frac{1}{2})^2-(\frac{1}{2})^2=0.5\)，比其父节点要高。这是因为第二个子节点是纯的，所以总的加权基尼不纯度等于\(\frac{2}{5}\times 0.5 + \frac{3}{5} \times 0 =0.2\)，低于父节点的基尼不纯度。

3. 如果决策树过拟合训练集，减少max_depth是否为一个好主意？

是一个好主意，因为这会限制模型，使其正则化。

4. 如果决策树对训练集欠拟合，尝试缩放输入特征是否为一个好主意？

决策树的优点之一就是决策树不关心数据集是缩放还是集中，所以如果决策树不适合训练集，缩放输入特征不过是浪费时间罢了。

5. 如果在包含100万个实例的训练集上训练决策树需要一个小时，那么在包含1000万个实例的训练集上训练决策树，大概需要多长时间？

决策树的训练时间复杂度为\(O(n \times m log(m))\).所以，如果将训练集乘以1配，那么训练时间可以计算得出:

\[\begin{aligned} K &= \frac{n \times 10m \times log(10m)}{n \times m \times log(m)} \\ &= \frac{10 \times log(10m)}{log(m)} \end{aligned}\]

如果\(m=10^6\)，则\(K \approx 11.7\)

6. 如果训练集包含10万个实例，设置presort=True可以加快训练吗？

只有当数据集小于数千个实例时，预处理训练集才可以加速训练。如果包含\(10^5\)个实例，设置presort=True会显著减慢训练。

7. 为卫星数据集训练并微调一个决策树。

# 生成卫星数据集
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=10000, noise=0.4, random_state=42)

# 拆分数据集
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
len(X_train), len(X_test)

(8000, 2000)

# 使用交叉验证的网格搜索为DecisionTreeClassifier找到合适的超参数
from sklearn.model_selection import GridSearchCV
from sklearn.tree import DecisionTreeClassifier
params = {"max_leaf_nodes": list(range(2, 100)), 'min_samples_split':[2, 3, 4]}
grid_search_cv = GridSearchCV(DecisionTreeClassifier(random_state=42), params, verbose=1, cv=3)

grid_search_cv.fit(X_train, y_train)

Fitting 3 folds for each of 294 candidates, totalling 882 fits
[Parallel(n_jobs=1)]: Using backend SequentialBackend with 1 concurrent workers.
[Parallel(n_jobs=1)]: Done 882 out of 882 | elapsed:   15.7s finished

GridSearchCV(cv=3, estimator=DecisionTreeClassifier(random_state=42),
             param_grid={'max_leaf_nodes': [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
                                            13, 14, 15, 16, 17, 18, 19, 20, 21,
                                            22, 23, 24, 25, 26, 27, 28, 29, 30,
                                            31, ...],
                         'min_samples_split': [2, 3, 4]},
             verbose=1)

grid_search_cv.best_estimator_

DecisionTreeClassifier(max_leaf_nodes=17, random_state=42)

# 使用超参数对整个训练集进行训练，并测量模型在测试集上的性能
from sklearn.metrics import accuracy_score
y_pred = grid_search_cv.predict(X_test)
accuracy_score(y_test, y_pred)

0.8695

8. 按照以下步骤种植森林。

8.1 继续之前的练习，生产1000个训练集子集，每个子集包含随机挑选的100个实例。提示：使用Scikit-Learn的ShuffleSplit来实现。

from sklearn.model_selection import ShuffleSplit

n_trees = 1000
n_instances = 100

mini_sets = []

rs = ShuffleSplit(n_splits=n_trees, test_size=len(X_train) - n_instances, random_state=42)

for mini_train_index, mini_test_index in rs.split(X_train):
    X_mini_train = X_train[mini_train_index]
    y_mini_train = y_train[mini_train_index]
    mini_sets.append((X_mini_train, y_mini_train))

len(mini_sets)

1000

8.2 使用前面得到的最佳超参数值，在每个子集上训练一个决策树。在测试集上评估这1000个决策树。因为训练集更小，所以这些决策树的表现可能比第一个决策树要差一些，只能达到约80%的准确率。

from sklearn.base import clone

forest = [clone(grid_search_cv.best_estimator_) for _ in range(n_trees)]
accuracy_scores = []

for tree, (X_mini_train, y_mini_train) in zip(forest, mini_sets):
    tree.fit(X_mini_train, y_mini_train)
    y_pred = tree.predict(X_test)
    accuracy_scores.append(accuracy_score(y_test, y_pred))

import numpy as np
np.mean(accuracy_scores)

0.8054499999999999

8.3 见证奇迹的时刻到了。对于每个测试集实例，生成1000个决策树的预测，然后仅保留次数最频繁的预测（可以使用SciPy的mode()函数）。这样你在测试集上可获得大多数投票的预测结果。

Y_pred = np.empty([n_trees, len(X_test)], dtype=np.uint8)
Y_pred.shape

(1000, 2000)

Y_pred

array([[0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       ...,
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0],
       [0, 0, 0, ..., 0, 0, 0]], dtype=uint8)

for tree_index, tree in enumerate(forest):
    Y_pred[tree_index] = tree.predict(X_test)
Y_pred.shape

(1000, 2000)

from scipy.stats import mode

y_pred_majority_votes, n_votes = mode(Y_pred, axis=0)

y_pred_majority_votes, n_votes

(array([[1, 1, 0, ..., 0, 0, 0]], dtype=uint8),
 array([[951, 912, 963, ..., 919, 994, 602]]))

8.4 评估测试集上的这些预测，你得到的准确率应该比第一个模型更高（高出0.5%～1.5%）。恭喜，你已经训练出了一个随机森林分类器！

accuracy_score(y_test, y_pred_majority_votes.reshape([-1]))

0.872