【随机森林】随机森林的 原理/ 样例实现/ 参数调优 分析及 Python代码实现

决策树

1.决策树与随机森林都属于机器学习中监督学习的范畴，主要用于分类问题。 

决策树算法有这几种：ID3、C4.5、CART，基于决策树的算法有bagging、随机森林、GBDT等。 

决策树是一种利用树形结构进行决策的算法，对于样本数据根据已知条件或叫特征进行分叉，最终建立一棵树，树的叶子结节标识最终决策。新来的数据便可以根据这棵树进行判断。随机森林是一种通过多棵决策树进行优化决策的算法。

2.案例： 

图 1 是一棵结构简单的决策树，用于预测贷款用户是否具有偿还贷款的能力。贷款用户主要具备三个属性：是否拥有房产，是否结婚，平均月收入。每一个内部结节都表示一个属性条件判断，叶子结节表示贷款用户是否具有偿还能力。 

这里说的属性，也就是算法中的特征，对应于数据表就是字段。 

这里说的可以偿还/不能偿还，就是一种分类问题。

3.决策树特征选取： 

从上图我们可以看到，第一个节点使用“拥有房产”作为条件，也就是特征。那么我们为什么第一个条件选择“拥有房产”呢，选择的条件和依据是什么呢？下面介绍基尼系数： 

基尼指数是另一种数据的不纯度的度量方法，其公式为： 

该公式可以用数学公式证明： 

x+y=1 

f=1-(x^2+y^2) 

f(x)=1-x^2-(1-x)^2=-2x^2+2x 

曲线为： 

根据上图可以看到，当x越靠近0或者1时，系数越小，代表数据纯度越高。有就是中间的某类数据占的比重比较大，也符合我们的认识。 

其中 c 表示数据集中类别的数量，Pi 表示类别 i 样本数量占所有样本的比例。 从该公式可以看出，当数据集中数据混合的程度越高，基尼指数也就越高。当数据集 D 只有一种数据类型，那么基尼指数的值为最低 0。 

如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为： 

其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。 

对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据。公式如下： 

在决策树选择特征时，应选择基尼指数增益值最大的特征，作为该结节分裂条件。 

另一个，和基尼系数类似，可采用信息熵，熵的概念物理上都学过，越无序，熵越大，不做多解释： 

假设在样本数据集 D 中，混有 c 种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的结节。在数据集中，可以计算出该数据中的信息熵： 

上图为分析信息增益的计算公式，可以看出和基尼系数大体类似。 

如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为： 

其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。 

对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据。公式如下： 

在决策树选择特征时，应选择基尼指数增益值最大的特征，作为该结节分裂条件。

4.剪枝： 

分为预剪枝和后剪枝。 

预剪枝提前结束决策树的省长，后剪枝效果更好，但是后剪枝会浪费在叔的生长过程中的计算。

5.集中决策树的区别： 

1） ID3 

是最早提出的一种决策树方法，使用上述信息增益的方式建立。 

缺点：只能处理离散型属性，并且对倾向于选择取值较多的属性； 

2） C4.5 

使用增益率对信息增益进行扩充，以解决偏向取值较多的属性的问题。另外它可以处理连续型属性。 

3） CART 

CART中用于选择变量的不纯性度量是Gini指数； 

如果目标变量是标称的，并且是具有两个以上的类别，则CART可能考虑将目标类别合并成两个超类别（双化）； 

如果目标变量是连续的，则CART算法找出一组基于树的回归方程来预测目标变量。

随机森林

1.随机森林原理： 

随机森林由Leo Breiman（2001）提出的一种分类算法，它通过自助法（bootstrap）重采样技术，从原始训练样本集N中有放回地重复随机抽取n个样本生成新的训练样本集合训练决策树，然后按以上步骤生成m棵决策树组成随机森林，新数据的分类结果按分类树投票多少形成的分数而定。其实质是对决策树算法的一种改进，将多个决策树合并在一起，每棵树的建立依赖于独立抽取的样本。 

单棵树的分类能力可能很小，但在随机产生大量的决策树后，一个测试样本可以通过每一棵树的分类结果经统计后选择最可能的分类。 

随机森林大致过程如下： 

1）从样本集中有放回随机采样选出n个样本； 

2）从所有特征中随机选择k个特征，对选出的样本利用这些特征建立决策树（一般是CART，也可是别的或混合）； 

3）重复以上两步m次，即生成m棵决策树，形成随机森林； 

4）对于新数据，经过每棵树决策，最后投票确认分到哪一类。 

2.随机森林特点： 

随机森林有很多优点： 

1） 每棵树都选择部分样本及部分特征，一定程度避免过拟合； 

2） 每棵树随机选择样本并随机选择特征，使得具有很好的抗噪能力，性能稳定； 

3） 能处理很高维度的数据，并且不用做特征选择； 

4） 适合并行计算； 

5） 实现比较简单； 

缺点： 

1） 参数较复杂； 

2） 模型训练和预测都比较慢。 

3.使用： 

随机森林算法在大部分数据处理软件中都有实现，使用时可以直接调用，只需指定所需参数。 

随机森林模型训练前要设置的参数较多，按PAI平台的实现有如下几个： 

o 算法类型：（可选）可供选择的算法类型有id3算法、cart算法、c4.5算法以及默认情况下的将上述三种算法均分的混合算法 

o 树的数目：森林中树的个数, 范围(0, 1000] 

o 随机属性个数：（可选）单颗树在生成时，每次选择最优特征，随机的特征个数。可供选择的类型有logN，N/3，sqrtN，N四种类型，其中N为属性总数 

o 树最大深度：（可选）单颗树的最大深度，范围[1, ∞)，-1表示完全生长。 

o 叶子节点最少记录数：（可选）叶节点数据的最小个数。最小个数为2 

o 叶子节点最少记录百分比：（可选）叶节点数据个数占父节点的最小比例，范围[0,100]，-1表示无限制。默认-1 

o 每棵树最大记录数：（可选）森林中单颗树输入的随机数据的个数。范围为(1000, 1000000] 

4.模型评估： 

算法模型建立后需要进行评估，以判断模型的优劣。一般使用训练集 (training set) 建立模型，使用测试集 (test set) 来评估模型。对于分类算法评估指标有分类准确度、召回率、虚警率和精确度等。而这些指标都是基于混淆矩阵 (confusion matrix) 进行计算的。 

混淆矩阵用来评价监督式学习模型的精确性，矩阵的每一列代表一个类的实例预测，而每一行表示一个实际的类的实例。以二分类问题为例，如下表所示： 

其中 

P (Positive Sample)：正例的样本数量。 

N (Negative Sample)：负例的样本数量。 

TP (True Positive)：正确预测到的正例的数量。 

FP (False Positive)：把负例预测成正例的数量。 

FN (False Negative)：把正例预测成负例的数量。 

TN (True Negative)：正确预测到的负例的数量。 

根据混淆矩阵可以得到评价分类模型的指标有以下几种。 

分类准确度，就是正负样本分别被正确分类的概率，计算公式为： 

召回率，就是正样本被识别出的概率，计算公式为： 

虚警率，就是负样本被错误分为正样本的概率，计算公式为： 

精确度，就是分类结果为正样本的情况真实性程度，计算公式为： 

评估方法有保留法、随机二次抽样、交叉验证和自助法等。 

保留法 (holdout) 是评估分类模型性能的最基本的一种方法。将被标记的原始数据集分成训练集和检验集两份，训练集用于训练分类模型，检验集用于评估分类模型性能。但此方法不适用样本较小的情况，模型可能高度依赖训练集和检验集的构成。 

随机二次抽样 (random subsampling) 是指多次重复使用保留方法来改进分类器评估方法。同样此方法也不适用训练集数量不足的情况，而且也可能造成有些数据未被用于训练集。 

交叉验证 (cross-validation) 是指把数据分成数量相同的 k 份，每次使用数据进行分类时，选择其中一份作为检验集，剩下的 k-1 份为训练集，重复 k 次，正好使得每一份数据都被用于一次检验集 k-1 次训练集。该方法的优点是尽可能多的数据作为训练集数据，每一次训练集数据和检验集数据都是相互独立的，并且完全覆盖了整个数据集。也存在一个缺点，就是分类模型运行了 K 次，计算开销较大。 

自助法 (bootstrap) 是指在其方法中，训练集数据采用的是有放回的抽样，即已经选取为训练集的数据又被放回原来的数据集中，使得该数据有机会能被再一次抽取。用于样本数不多的情况下，效果很好。

其它类似算法

1.Bagging 

Bagging算法与随机森林类似，区别是每棵树都使用所有特征，而不是只选择部分特征。该算法过程如下： 

1）从样本集中随机采样选出n个样本； 

2）在所有属性上，对这n个样本建立分类器（CART or SVM or …）； 

3）重复以上两步m次，即生成m个分类器（CART or SVM or …）； 

4）将数据放在这m个分类器上跑，最后投票确认分到哪一类。

2.GBDT 

GBDT（Gradient Boosting Decision Tree）是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终结果。被认为是泛化能力较强的一种算法。 

GBDT是一个应用很广泛的算法，可以用来做分类、回归。GBDT还有其他名字，比如MART（Multiple Additive Regression Tree），GBRT（Gradient Boosting Regression Tree），Tree Net等。 

GBDT与C4.5等分类树不同，它是回归树。区别在于，回归树的每个结点（不一定是叶子结点）都会得到一个预测值，以年龄为例，该预测值等于属于这个结点的所有人年龄的平均值。分支时穷举每个特征找到最好的一个进行分支，但衡量最好的标准不再是信息增益，而是最小化均方差，如 （每个人的年龄 – 预测年龄）^2的总和 / N。也就是被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最可靠的分支依据。分支直到每个叶子结点上人的年龄都唯一或者达到预设的终止条件（如叶子个数上限）。若最终叶子结点上人的年龄不唯一，则以结点上所有人的平均年龄做为该叶子结点的预测年龄。 

梯度迭代（Gradient Boosting），即通过迭代多棵树来共同决策。GBDT的核心就在于，每棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能等到真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12 岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子结点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。 

GBDT具体实现请自行查阅。

样例代码及参数调优

数据集： 

我们的数据集是来自一个著名的数据挖掘竞赛网站，是一个关于泰坦尼克号，游客生存情况的调查。可以从这里下载：https://www.kaggle.com/c/titanic/data 

上面的一张图，是我从官网上下载的，总的来说，里面的每一行数据，差不多有11个字段，包括游客的年龄、名字、性别、买的几等仓的票等等信息，最后是他的生存情况，在这场事故中，他是死了还是幸存。 

不想解释了，直接读入数据吧

import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier
train = pd.read_csv("E:/train.csv", dtype={"Age": np.float64},)
train.head(10)
           

稍微分析一下，我们就可以筛选出对一个游客的生存与否有关的变量：Pclass, Sex, Age, SibSp，Parch，Fare, Embarked. 一般来说，游客的名字，买的船票号码对其的生存情况应该影响很小。

len(train_data)
out:891
           

我们共有891条数据，将近900条，我们使用600条作为训练数据，剩下的291条作为测试数据，通过对随机森林的参数不断调优，找出在测试结果上，预测最为精确的随机森林模型。 

在具体的实验之前，我们看一下使用随机森林模型，需要注意哪几个变量： 

在 sklearn中，随机森林的函数模型是：

RandomForestClassifier(bootstrap=True, class_weight=None, criterion='gini',
            max_depth=None, max_features='auto', max_leaf_nodes=None,
            min_samples_leaf=1, min_samples_split=2,
            min_weight_fraction_leaf=0.0, n_estimators=10, n_jobs=1,
            oob_score=False, random_state=None, verbose=0,
            warm_start=False)
           

参数分析 

A. max_features： 

随机森林允许单个决策树使用特征的最大数量。 Python为最大特征数提供了多个可选项。 下面是其中的几个： 

Auto/None ：简单地选取所有特征，每颗树都可以利用他们。这种情况下，每颗树都没有任何的限制。 

sqrt ：此选项是每颗子树可以利用总特征数的平方根个。 例如，如果变量（特征）的总数是100，所以每颗子树只能取其中的10个。“log2”是另一种相似类型的选项。 

0.2：此选项允许每个随机森林的子树可以利用变量（特征）数的20％。如果想考察的特征x％的作用， 我们可以使用“0.X”的格式。 

max_features如何影响性能和速度？ 

增加max_features一般能提高模型的性能，因为在每个节点上，我们有更多的选择可以考虑。 然而，这未必完全是对的，因为它降低了单个树的多样性，而这正是随机森林独特的优点。 但是，可以肯定，你通过增加max_features会降低算法的速度。 因此，你需要适当的平衡和选择最佳max_features。 

B. n_estimators： 

在利用最大投票数或平均值来预测之前，你想要建立子树的数量。 较多的子树可以让模型有更好的性能，但同时让你的代码变慢。 你应该选择尽可能高的值，只要你的处理器能够承受的住，因为这使你的预测更好更稳定。 

C. min_sample_leaf： 

如果您以前编写过一个决策树，你能体会到最小样本叶片大小的重要性。 叶是决策树的末端节点。 较小的叶子使模型更容易捕捉训练数据中的噪声。 一般来说，我更偏向于将最小叶子节点数目设置为大于50。在你自己的情况中，你应该尽量尝试多种叶子大小种类，以找到最优的那个。

下面我们对上面提到的三个参数，进行调优，首先参数A，由于在我们的这个数据中，数据段总共只有七八个，所以我们就简单的选取所有的特征，所以我们只需要对剩下的两个变量进行调优。 

在sklearn自带的随机森林算法中，输入的值必须是整数或者浮点数，所以我们需要对数据进行预处理，将字符串转化成整数或者浮点数：

def harmonize_data(titanic):
    # 填充空数据 和 把string数据转成integer表示
    # 对于年龄字段发生缺失，我们用所有年龄的均值替代
    titanic["Age"] = titanic["Age"].fillna(titanic["Age"].median())
    # 性别男： 用0替代
    titanic.loc[titanic["Sex"] == "male", "Sex"] = 0
    # 性别女： 用1替代
    titanic.loc[titanic["Sex"] == "female", "Sex"] = 1

    titanic["Embarked"] = titanic["Embarked"].fillna("S")

    titanic.loc[titanic["Embarked"] == "S", "Embarked"] = 0
    titanic.loc[titanic["Embarked"] == "C", "Embarked"] = 1
    titanic.loc[titanic["Embarked"] == "Q", "Embarked"] = 2

    titanic["Fare"] = titanic["Fare"].fillna(titanic["Fare"].median())

    return titanic

train_data = harmonize_data(train)
           

上面的代码是对原始数据进行清洗，填补缺失数据， 把string类型数据转化成int数据 

下面的工作，我们开始划分训练数据和测试数据，总的数据有891个，我们用600个训练数据集，剩下的291个作为测试数据集。

# 列出对生存结果有影响的字段
predictors = ["Pclass", "Sex", "Age", "SibSp", "Parch", "Fare", "Embarked"]
# 存放不同参数取值，以及对应的精度，每一个元素都是一个三元组(a, b, c)
results = []
# 最小叶子结点的参数取值
sample_leaf_options = list(range(1, 500, 3))
# 决策树个数参数取值
n_estimators_options = list(range(1, 1000, 5))
groud_truth = train_data['Survived'][601:]

for leaf_size in sample_leaf_options:
    for n_estimators_size in n_estimators_options:
        alg = RandomForestClassifier(min_samples_leaf=leaf_size, n_estimators=n_estimators_size, random_state=50)
        alg.fit(train_data[predictors][:600], train_data['Survived'][:600])
        predict = alg.predict(train_data[predictors][601:])
        # 用一个三元组，分别记录当前的 min_samples_leaf，n_estimators， 和在测试数据集上的精度
        results.append((leaf_size, n_estimators_size, (groud_truth == predict).mean()))
        # 真实结果和预测结果进行比较，计算准确率
        print((groud_truth == predict).mean())

# 打印精度最大的那一个三元组
print(max(results, key=lambda x: x[2]))
           

总的来说，调参对随机森林来说，不会发生很大的波动，相比神经网络来说，随机森林即使使用默认的参数，也可以达到良好的结果。在我们的例子中，通过粗略的调参，可以在测试集上达到84%的预测准确率，我觉得效果应该出乎我的意料吧。 

附上全部代码：（运行时间比较久）

__author__ = 'Administrator'
import numpy as np
import pandas as pd
from sklearn.ensemble import RandomForestClassifier

train = pd.read_csv("E:/train.csv", dtype={"Age": np.float64},)


def harmonize_data(titanic):
    # 填充空数据 和 把string数据转成integer表示

    titanic["Age"] = titanic["Age"].fillna(titanic["Age"].median())

    titanic.loc[titanic["Sex"] == "male", "Sex"] = 0
    titanic.loc[titanic["Sex"] == "female", "Sex"] = 1

    titanic["Embarked"] = titanic["Embarked"].fillna("S")

    titanic.loc[titanic["Embarked"] == "S", "Embarked"] = 0
    titanic.loc[titanic["Embarked"] == "C", "Embarked"] = 1
    titanic.loc[titanic["Embarked"] == "Q", "Embarked"] = 2

    titanic["Fare"] = titanic["Fare"].fillna(titanic["Fare"].median())

    return titanic

train_data = harmonize_data(train)

predictors = ["Pclass", "Sex", "Age", "SibSp", "Parch", "Fare", "Embarked"]
results = []
sample_leaf_options = list(range(1, 500, 3))
n_estimators_options = list(range(1, 1000, 5))
groud_truth = train_data['Survived'][601:]

for leaf_size in sample_leaf_options:
    for n_estimators_size in n_estimators_options:
        alg = RandomForestClassifier(min_samples_leaf=leaf_size, n_estimators=n_estimators_size, random_state=50)
        alg.fit(train_data[predictors][:600], train_data['Survived'][:600])
        predict = alg.predict(train_data[predictors][601:])
        # 用一个三元组，分别记录当前的 min_samples_leaf，n_estimators， 和在测试数据集上的精度
        results.append((leaf_size, n_estimators_size, (groud_truth == predict).mean()))
        # 真实结果和预测结果进行比较，计算准确率
        print((groud_truth == predict).mean())

# 打印精度最大的那一个三元组
print(max(results, key=lambda x: x[2]))
           

在讲随机森林前，我先讲一下什么是集成学习。集成学习通过构建并结合多个分类器来完成学习任务。集成学习通过将多个学习器进行结合，常可获得比单一学习器更好的泛化性能。

考虑一个简单例子：在二分类任务中，假定三个分类器在三个测试样本上的表现如下图，其中√表示分类正确，×表示分类错误，集成学习的结果通过投票法产生，即“少数服从多数”。如下图，在（a）中，每个分类器都只有66.6%的精度，但集成学习却达到了100%；在（b）中，三个分类器没有差别，集成之后性能没有提高；在(c)中，每个分类器的精度都只有33.3%，集成学习的结果变得更糟。这个简单地例子显示出：要获得好的集成，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，即学习器不能太差，并且要有“多样性”，即学习器间具有差异。

根据个体学习器的生成方式，目前的集成学习方法大致可分为两大类，即个体学习器之间存在强依赖关系，必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系，可同时生成的并行化方法；前者的代表是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）

Bagging与随机森林

要得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立，虽然这在现实任务中很难做到，但我们可以设法使基学习器尽可能具有较大的差异。

在我的实验中，使用“自助采样法”：给定包含m个样本的数据集，我们先随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下次采样时该样本仍有可能被选中，这样，经过m次随机操作，我们得到含m个样本的采样集，初始训练集中有的样本在采样集里多次出现，有的则从未出现。

按照这种方法，我们可以采样出T个含m个训练样本的采样集，然后基于每个采样集训练处一个基学习器，再将这些基学习器进行结合，这就是Bagging的基本流程。在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。

随机森林是Bagging的一个扩展。随机森林在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机属性选择（即引入随机特征选择）。传统决策树在选择划分属性时时在当前节点的属性集合（假定有d个属性）中选择一个最优属性；而在随机森林中，对基决策树的每个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。这里的参数k控制了随机性的引入程度：若令k=d,则基决策树的构建与传统决策树相同；若令k=1，则是随机选择一个属性进行划分。

在这篇文章中，我们只讲随机森林的分类部分。随机森林用于分类时，即采用n个决策树分类，将分类结果用简单投票法得到最终分类，提高分类准确率。

对于决策树不太了解的童鞋，可以看我的上一篇博客：决策树原理及Python代码实现

简单来说，随机森林就是对决策树的集成，但有两点不同：

（1）采样的差异性：从含m个样本的数据集中有放回的采样，得到含m个样本的采样集，用于训练。这样能保证每个决策树的训练样本不完全一样。

（2）特征选取的差异性：每个决策树的n个分类特征是在所有特征中随机选择的（n是一个需要我们自己调整的参数）

随机森林需要调整的参数有：

（1）    决策树的个数

（2）    特征属性的个数

（3）    递归次数（即决策树的深度）

下面，讲一下如何用代码实现随机森林。

代码实现流程：

（1）    导入文件并将所有特征转换为float形式

（2）    将数据集分成n份，方便交叉验证

（3）    构造数据子集（随机采样），并在指定特征个数（假设m个，手动调参）下选取最优特征

（4）    构造决策树

（5）    创建随机森林（多个决策树的结合）

（6）    输入测试集并进行测试，输出预测结果

（1）    导入文件并将所有特征转换为float形式

#加载数据
def loadCSV(filename):
    dataSet=[]
    with open(filename,'r') as file:
        csvReader=csv.reader(file)
        for line in csvReader:
            dataSet.append(line)
    return dataSet
 
#除了判别列，其他列都转换为float类型
def column_to_float(dataSet):
    featLen=len(dataSet[0])-1
    for data in dataSet:
        for column in range(featLen):
            data[column]=float(data[column].strip())
           

（2）    将数据集分成n份，方便交叉验证

#将数据集分成N块，方便交叉验证
def spiltDataSet(dataSet,n_folds):
    fold_size=int(len(dataSet)/n_folds)
    dataSet_copy=list(dataSet)
    dataSet_spilt=[]
    for i in range(n_folds):
        fold=[]
        while len(fold) < fold_size:   #这里不能用if，if只是在第一次判断时起作用，while执行循环，直到条件不成立
            index=randrange(len(dataSet_copy))
            fold.append(dataSet_copy.pop(index))  #pop() 函数用于移除列表中的一个元素（默认最后一个元素），并且返回该元素的值。
        dataSet_spilt.append(fold)
    return dataSet_spilt
           

（3）    构造数据子集（随机采样），并在指定特征个数（假设m个，手动调参）下选取最优特征

#构造数据子集
def get_subsample(dataSet,ratio):
    subdataSet=[]
    lenSubdata=round(len(dataSet)*ratio)
    while len(subdataSet) < lenSubdata:
        index=randrange(len(dataSet)-1)
        subdataSet.append(dataSet[index])
    #print len(subdataSet)
    return subdataSet
 
#选取任意的n个特征，在这n个特征中，选取分割时的最优特征
def get_best_spilt(dataSet,n_features):
    features=[]
    class_values=list(set(row[-1] for row in dataSet))
    b_index,b_value,b_loss,b_left,b_right=999,999,999,None,None
    while len(features) < n_features:
        index=randrange(len(dataSet[0])-1)
        if index not in features:
            features.append(index)
    #print 'features:',features
    for index in features:
        for row in dataSet:
            left,right=data_spilt(dataSet,index,row[index])
            loss=spilt_loss(left,right,class_values)
            if loss < b_loss:
                b_index,b_value,b_loss,b_left,b_right=index,row[index],loss,left,right
    #print b_loss
    #print type(b_index)
    return {'index':b_index,'value':b_value,'left':b_left,'right':b_right}
           

（4）    构造决策树

#构造决策树
def build_tree(dataSet,n_features,max_depth,min_size):
    root=get_best_spilt(dataSet,n_features)
    sub_spilt(root,n_features,max_depth,min_size,1) 
    return root
           

（5）    创建随机森林（多个决策树的结合）

#创建随机森林
def random_forest(train,test,ratio,n_feature,max_depth,min_size,n_trees):
    trees=[]
    for i in range(n_trees):
        subTrain=get_subsample(train,ratio)
        tree=build_tree(subTrain,n_features,max_depth,min_size)
        #print 'tree %d: '%i,tree
        trees.append(tree)
    #predict_values = [predict(trees,row) for row in test]
    predict_values = [bagging_predict(trees, row) for row in test]
    return predict_values
           

（6）    输入测试集并进行测试，输出预测结果

#预测测试集结果
def predict(tree,row):
    predictions=[]
    if row[tree['index']] < tree['value']:
        if isinstance(tree['left'],dict):
            return predict(tree['left'],row)
        else:
            return tree['left']
    else:
        if isinstance(tree['right'],dict):
            return predict(tree['right'],row)
        else:
            return tree['right']
   # predictions=set(predictions)
           

对以上代码的一点总结：

训练部分：假设我们取dataset中的m个feature来构造决策树，首先，我们遍历m个feature中的每一个feature，再遍历每一行，通过spilt_loss函数（计算分割代价）来选取最优的特征及特征值，根据是否大于这个特征值进行分类（分成left,right两类），循环执行上述步骤，直至不可分或者达到递归限值（用来防止过拟合），最后得到一个决策树tree。

测试部分：对测试集的每一行进行判断，决策树tree是一个多层字典，每一层为一个二分类，将每一行按照决策树tree中的分类索引index一步一步向里层探索，直至不出现字典时探索结束，得到的值即为我们的预测值。