分享

算法基础(17)| 随机森林算法基础

 ZZvvh2vjnmrpl4 2019-06-03

今天,你算法了没?

0.来源说明

作者:我爱大猫咪,shjyoudp

出处:CSDN

整理&排版:Ethon

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

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

随机森林这个算法在分类问题上效果十分的好,大多数情况下效果远要比svm,log回归,knn等算法效果好。

随机森林属于集成学习(Ensemble Learning)中的Bagging算法。在集成学习中,主要分为Bagging算法和Boosting算法。我们先看看这两种方法的特点和区别。

 Bagging(套袋法)

Bagging的算法过程如下:

从原始样本集中使用Bootstraping方法随机抽取n个训练样本,共进行k轮抽取,得到k个训练集。(k个训练集之间相互独立,元素可以有重复)

对于k个训练集,我们训练k个模型(这k个模型可以根据具体问题而定,比如决策树,knn等)。

对于分类问题:由投票表决产生分类结果;对于回归问题:由k个模型预测结果的均值作为最后预测结果。

2  Boosting(提升法)

Boosting的算法过程如下:

对于训练集中的每个样本建立权值wi,表示对每个样本的关注度。当某个样本被误分类的概率很高时,需要加大对该样本的权值。

进行迭代的过程中,每一步迭代都是一个弱分类器。我们需要用某种策略将其组合,作为最终模型。(例如AdaBoost给每个弱分类器一个权值,将其线性组合最为最终分类器。误差越小的弱分类器,权值越大)

Bagging,Boosting的主要区别:

  • 样本选择上:Bagging采用的是Bootstrap随机有放回抽样;而Boosting每一轮的训练集是不变的,改变的只是每一个样本的权重。

  • 样本权重:Bagging使用的是均匀取样,每个样本权重相等;Boosting根据错误率调整样本权重,错误率越大的样本权重越大。

  • 预测函数:Bagging所有的预测函数的权重相等;Boosting中误差越小的预测函数其权重越大。

  • 并行计算:Bagging各个预测函数可以并行生成;Boosting各个预测函数必须按顺序迭代生成。

下面是将决策树与这些算法框架进行结合所得到的新的算法:

1)Bagging 决策树 = 随机森林

2)AdaBoost 决策树 = 提升树

3)Gradient Boosting 决策树 = GBDT

3  决策树

常用的决策树算法有ID3,C4.5,CART三种。3种算法的模型构建思想都十分类似,只是采用了不同的指标。决策树模型的构建过程大致如下:

ID3,C4.5决策树的生成

输入:训练集D,特征集A,阈值eps 输出:决策树T

  1. 若D中所有样本属于同一类Ck,则T为单节点树,将类Ck作为该结点的类标记,返回T;

  2. 若A为空集,即没有特征作为划分依据,则T为单节点树,并将D中实例数最大的类Ck作为该结点的类标记,返回T

  3. 否则,计算A中各特征对D的信息增益(ID3)/信息增益比(C4.5),选择信息增益最大的特征Ag

  4. 若Ag的信息增益(比)小于阈值eps,则置T为单节点树,并将D中实例数最大的类Ck作为该结点的类标记,返回T

  5. 否则,依照特征Ag将D划分为若干非空子集Di,将Di中实例数最大的类作为标记,构建子节点,由结点及其子节点构成树T,返回T

  6. 对第i个子节点,以Di为训练集,以A-{Ag}为特征集,递归地调用1~5,得到子树Ti,返回Ti

CART决策树的生成

这里只简单介绍下CART与ID3和C4.5的区别。

CART树是二叉树,而ID3和C4.5可以是多叉树

CART在生成子树时,是选择一个特征一个取值作为切分点,生成两个子树

选择特征和切分点的依据是基尼指数,选择基尼指数最小的特征及切分点生成子树

案例

图 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  决策树的剪枝

决策树的剪枝主要是为了预防过拟合。主要思路是从叶节点向上回溯,尝试对某个节点进行剪枝,比较剪枝前后的决策树的损失函数值。最后我们通过动态规划(树形dp,acmer应该懂)就可以得到全局最优的剪枝方案。

5  随机森林(Random Forests)

随机森林是一种重要的基于Bagging的集成学习方法,可以用来做分类、回归等问题。

随机森林有许多优点:

  • 具有极高的准确率

  • 随机性的引入,使得随机森林不容易过拟合

  • 随机性的引入,使得随机森林有很好的抗噪声能力

  • 能处理很高维度的数据,并且不用做特征选择

  • 既能处理离散型数据,也能处理连续型数据,数据集无需规范化

  • 训练速度快,可以得到变量重要性排序

  • 容易实现并行化

随机森林的缺点:

  • 当随机森林中的决策树个数很多时,训练时需要的空间和时间会较大

  • 随机森林模型还有许多不好解释的地方,有点算个黑盒模型

与上面介绍的Bagging过程相似,随机森林的构建过程大致如下:

  1. 从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本,共进行n_tree次采样,生成n_tree个训练集

  2. 对于n_tree个训练集,我们分别训练n_tree个决策树模型

  3. 对于单个决策树模型,假设训练样本特征的个数为n,那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂

  4. 每棵树都一直这样分裂下去,直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝

  5. 将生成的多棵决策树组成随机森林。对于分类问题,按多棵树分类器投票决定最终分类结果;对于回归问题,由多棵树预测值的均值决定最终预测结果

模型评估 

算法模型建立后需要进行评估,以判断模型的优劣。一般使用训练集 (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) 是指在其方法中,训练集数据采用的是有放回的抽样,即已经选取为训练集的数据又被放回原来的数据集中,使得该数据有机会能被再一次抽取。用于样本数不多的情况下,效果很好。

样例代码及参数调优


采用的数据集是来自数据挖掘竞赛网站Kaggle,是一个关于泰坦尼克号,游客生存情况的调查。可以从这里下载:

https://www./c/titanic/data 

总的来说,数据集的每一行数据,差不多有11个字段,包括游客的年龄、名字、性别、买的几等仓的票等等信息,最后是他的生存情况,在这场事故中,他是死了还是幸存。 

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

1len(train_data)
2out:891

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

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


在 sklearn中,随机森林的函数模型是:

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

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

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

1def harmonize_data(titanic):
2
3
4    titanic['Age'] = titanic['Age'].fillna(titanic['Age'].median())
5
6    titanic.loc[titanic['Sex'] == 'male', 'Sex'] = 0
7
8    titanic.loc[titanic['Sex'] == 'female', 'Sex'] = 1
9
10    titanic['Embarked'] = titanic['Embarked'].fillna('S')
11
12    titanic.loc[titanic['Embarked'] == 'S', 'Embarked'] = 0
13    titanic.loc[titanic['Embarked'] == 'C', 'Embarked'] = 1
14    titanic.loc[titanic['Embarked'] == 'Q', 'Embarked'] = 2
15
16    titanic['Fare'] = titanic['Fare'].fillna(titanic['Fare'].median())    return titanic
17
18train_data = harmonize_data(train)

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

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

 1predictors = ['Pclass', 'Sex', 'Age', 'SibSp', 'Parch', 'Fare', 'Embarked']
2
3results = []
4
5sample_leaf_options = list(range(1, 500, 3))
6
7n_estimators_options = list(range(1, 1000, 5))
8groud_truth = train_data['Survived'][601:]for leaf_size in sample_leaf_options:    for n_estimators_size in n_estimators_options:
9        alg = RandomForestClassifier(min_samples_leaf=leaf_size, n_estimators=n_estimators_size, random_state=50)
10        alg.fit(train_data[predictors][:600], train_data['Survived'][:600])
11        predict = alg.predict(train_data[predictors][601:])
12
13        results.append((leaf_size, n_estimators_size, (groud_truth == predict).mean()))
14
15        print((groud_truth == predict).mean())
16
17
18print(max(results, key=lambda x: x[2]))

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

详细代码如下:

1__author__ = 'Administrator'import numpy as npimport pandas as pdfrom sklearn.ensemble import RandomForestClassifier
2
3train = pd.read_csv('E:/train.csv', dtype={'Age': np.float64},)def harmonize_data(titanic):
4
5
6    titanic['Age'] = titanic['Age'].fillna(titanic['Age'].median())
7
8    titanic.loc[titanic['Sex'] == 'male', 'Sex'] = 0
9    titanic.loc[titanic['Sex'] == 'female', 'Sex'] = 1
10
11    titanic['Embarked'] = titanic['Embarked'].fillna('S')
12
13    titanic.loc[titanic['Embarked'] == 'S', 'Embarked'] = 0
14    titanic.loc[titanic['Embarked'] == 'C', 'Embarked'] = 1
15    titanic.loc[titanic['Embarked'] == 'Q', 'Embarked'] = 2
16
17    titanic['Fare'] = titanic['Fare'].fillna(titanic['Fare'].median())    return titanic
18
19train_data = harmonize_data(train)
20
21predictors = ['Pclass', 'Sex', 'Age', 'SibSp', 'Parch', 'Fare', 'Embarked']
22results = []
23sample_leaf_options = list(range(1, 500, 3))
24n_estimators_options = list(range(1, 1000, 5))
25groud_truth = train_data['Survived'][601:]for leaf_size in sample_leaf_options:    for n_estimators_size in n_estimators_options:
26        alg = RandomForestClassifier(min_samples_leaf=leaf_size, n_estimators=n_estimators_size, random_state=50)
27        alg.fit(train_data[predictors][:600], train_data['Survived'][:600])
28        predict = alg.predict(train_data[predictors][601:])
29
30        results.append((leaf_size, n_estimators_size, (groud_truth == predict).mean()))
31
32        print((groud_truth == predict).mean())
33
34
35print(max(results, key=lambda x: x[2]))


      本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
      转藏 分享 献花(0

      0条评论

      发表

      请遵守用户 评论公约

      类似文章 更多