机器学习之随机森林

集成学习，判别模型，多分类与回归，正则化的极大似然估计

随机森林主页：https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm#inter

套袋法(bagging)

该方法的第一步就是用数据集（用抽样法创建而成）创建多个模型。在抽样法中，每个生成的训练集由原始数据集的随机次级样本组成。每个训练集都和原始数据集一样大小，但有些记录会重复几次，有些记录则完全不出现。然后，整个原始数据集会被用作测试集。这样，如果原始数据集的大小为N，那么每个生成的训练集大小也为N，特殊记录的数量大约为（2N/3），测试集的大小也是N。

第二步就是用和生成的不同数据集中一样的算法构建多个模型。在这一步中，我们讨论一下随机森林。不像决策树中，每个节点在将错误最小化的最佳特征处分裂，在随机森林中，我们选择各个特征的一个随机抽样用以构建最佳节点。之所以是随机，是因为：即便是用套袋法，当决策树选择一个最佳特征之处分裂时，最终会是相同的结构和相互关联的预测。但在各个特征的随机子集处分裂后再套袋（bagging）意味着根据子树的预测之间的相关性较低。

在每个分叉点要搜索的特征数量被指定为随机森林算法的一个参数。

这样，在随机森林 bagging 中，用记录中的随机样本构造每个决策树，用预测器的随机样本构造每个分裂。

特点：

在当前所有算法中，具有极好的准确率/It is unexcelled in accuracy among current algorithms；

能够有效地运行在大数据集上/It runs efficiently on large data bases；

能够处理具有高维特征的输入样本，而且不需要降维/It can handle thousands of input variables without variable deletion；

能够评估各个特征在分类问题上的重要性/It gives estimates of what variables are important in the classification；

在生成过程中，能够获取到内部生成误差的一种无偏估计/It generates an internal unbiased estimate of the generalization error as the forest building progresses；

对于缺省值问题也能够获得很好得结果/It has an effective method for estimating missing data and maintains accuracy when a large proportion of the data are missing

随机森林是机器学习方法中的Leatherman（多功能折叠刀）。你几乎可以把任何东西扔给它。它在估计推断映射方面做的特别好，从而不需要类似SVM一样过多的调参。

优点:

不易过拟合，可能比Bagging和Boosting更快。由于在每次划分时只考虑很少的属性，因此它们在大型数据库上非常有效。有很好的方法来填充缺失值，即便有很大一部分数据缺失，仍能维持很高准确度。给出了变量重要性的内在估计，对于不平衡样本分类，它可以平衡误差。可以计算各实例的亲近度，对于数据挖掘、检测离群点和数据可视化非常有用。

随机森林方法被证明对大规模数据集和存在大量且有时不相关特征的项（item）来说很有用

缺点：

在某些噪声较大的分类和回归问题上会过拟合。对于有不同级别的属性的数据，级别划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产生的属性权值是不可信的。

1. 概念

决策树

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。常见的决策树算法有C4.5、ID3和CART。
信息、熵以及信息增益

如果带分类的事物集合可以划分为多个类别当中，则某个类（xi）的信息可以定义如下:

　　I(x)用来表示随机变量的信息，p(xi)指是当xi发生时的概率。

　　熵是用来度量不确定性的，当熵越大，X=xi的不确定性越大，反之越小。对于机器学习中的分类问题而言，熵越大即这个类别的不确定性更大，反之越小。

　　信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好。
随机决策树

我们知道随机森林是将其他的模型进行聚合，但具体是哪种模型呢？从其名称也可以看出，随机森林聚合的是分类（或回归）树。一颗决策树是由一系列的决策组合而成的，可用于数据集的观测值进行分类。

如果一个观测值为length=45,blue eye,legs=2,那么它将被划分为红色

随机森林

引入的随机森林算法将自动创建随机决策树群。由于这些树是随机生成的，大部分的树(甚至 99.9%)对解决你的分类或回归问题是没有有意义。
投票

当你要做预测的时候，新的观察值随着决策树自上而下走下来并被赋予一个预测值或标签。一旦森林中的每棵树都给有了预测值或标签，所有的预测结果将被归总到一起，所有树的投票返回做为最终的预测结果。

简单来说，99.9%不相关的树做出的预测结果涵盖所有的情况，这些预测结果将会彼此抵消。少数优秀的树的预测结果将会脱颖而出，从而得到一个好的预测结果。

随机森林

2. 基本思路

2.1 步骤

创建随机向量
使用随机向量建立多个决策树
组合决策树

2.2 每棵树生成规则

如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本（这种采样方式称为bootstrap sample方法），作为该树的训练集；从这里我们可以知道：每棵树的训练集都是不同的，而且里面包含重复的训练样本（理解这点很重要）。
如果每个样本的特征维度为M，指定一个常数m<<M，随机地从M个特征中选取m个特征子集，每次树进行分裂时，从这m个特征中选择最优的；
每棵树都尽最大程度的生长，并且没有剪枝过程。

2.3 问题

“随机“

随机森林的随机有两层意思。
- 训练样本选取随机。虽然每一棵树的训练样本个数都是样本总数N，但是每一个样本的随机选取都是有放回的选取。这样，每一颗树的训练样本几乎都不相同。
- 特征选取随机。假设训练数据有M个特征，随机森林的每一颗树只选取m（m< M）个特征用于构建决策树。每一颗树选取的特征可能都不完全相同。
”森林“
- “森林”我们很好理解，一棵叫做树，那么成百上千棵就可以叫做森林了，这样的比喻还是很贴切的，其实这也是随机森林的主要思想–集成思想的体现。
为什么要随机抽样训练集？

如果不进行随机抽样，每棵树的训练集都一样，那么最终训练出的树分类结果也是完全一样的，这样的话完全没有bagging的必要；
为什么要有放回地抽样？

如果不是有放回的抽样，那么每棵树的训练样本都是不同的，都是没有交集的，这样每棵树都是”有偏的”，都是绝对”片面的”（当然这样说可能不对），也就是说每棵树训练出来都是有很大的差异的；而随机森林最后分类取决于多棵树（弱分类器）的投票表决，这种表决应该是”求同”，因此使用完全不同的训练集来训练每棵树这样对最终分类结果是没有帮助的，这样无异于是”盲人摸象”。

两个随机性的引入对随机森林的分类性能至关重要。由于它们的引入，使得随机森林不容易陷入过拟合，并且具有很好得抗噪能力（比如：对缺省值不敏感）。

随机森林分类效果（错误率）与两个因素有关：
- 森林中任意两棵树的相关性：相关性越大，错误率越大；
- 森林中每棵树的分类能力：每棵树的分类能力越强，整个森林的错误率越低。

2.3 参数

森林中树的数量：一般建议取很大
m的大小：推荐m的值为M的均方根。

减小特征选择个数m，树的相关性和分类能力也会相应的降低；增大m，两者也会随之增大。所以关键问题是如何选择最优的m（或者是范围），这也是随机森林唯一的一个参数。主要依据计算袋外错误率oob error（out-of-bag error）。

3. 袋外错误率（oob error）

可以在内部进行评估，也就是说在生成的过程中就可以对误差建立一个无偏估计。

我们知道，在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的oob样本。

在构建每棵树时，我们对训练集使用了不同的bootstrap sample（随机且有放回地抽取）。所以对于每棵树而言（假设对于第k棵树），大约有1/3的训练实例没有参与第k棵树的生成，它们称为第k棵树的oob样本。

而这样的采样特点就允许我们进行oob估计，它的计算方式如下：

　　（note：以样本为单位）

对每个样本，计算它作为oob样本的树对它的分类情况（约1/3的树）。
然后以简单多数投票作为该样本的分类结果。
最后用误分个数占样本总数的比率作为随机森林的oob误分率。

oob误分率是随机森林泛化误差的一个无偏估计，它的结果近似于需要大量计算的k折交叉验证。

4. 使用方法

4.1 特征选择

随机森林的一个最好用例是特征选择。尝试很多个决策树变量的一个副产品就是，你可以检查变量在每棵树中表现的是最佳还是最糟糕。当一些树使用一个变量，而其他的不使用这个变量，你就可以对比信息的丢失或增加。实现的比较好的随机森林工具能够为你做这些事情，所以你需要做的仅仅是去查看那个方法或参数。

4.2 分类

随机森林也很善长分类问题。它可以被用于为多个可能目标类别做预测，它也可以在调整后输出概率。你需要注意的一件事情是过拟合。

随机森林容易产生过拟合，特别是在数据集相对小的时候。当你的模型对于测试集合做出“太好”的预测的时候就应该怀疑一下了。避免过拟合的一个方法是在模型中只使用有相关性的特征，比如使用之前提到的特征选择。

4.3 回归

随机森林也可以用于回归问题。

我发现，不像其他的方法，随机森林非常擅长于分类变量或分类变量与连续变量混合的情况。

5. 实例

描述：

根据已有的训练集已经生成了对应的随机森林，随机森林如何利用某一个人的年龄（Age）、性别（Gender）、教育情况（Highest Educational Qualification）、工作领域（Industry）以及住宅地（Residence）共5个字段来预测他的收入层次。

收入层次 :

　　　　Band 1 : Below $40,000

　　　　Band 2: $40,000 – 150,000

　　　　Band 3: More than $150,000

　　随机森林中每一棵树都可以看做是一棵CART（分类回归树），这里假设森林中有5棵CART树，总特征个数N=5，我们取m=1（这里假设每个CART树对应一个不同的特征）。

CART 1 : Variable Age

　　 rf1

CART 2 : Variable Gender

　　 rf2

CART 3 : Variable Education

　　 rf3

CART 4 : Variable Residence

　　 rf4

CART 5 : Variable Industry

　　 rf5

　　我们要预测的某个人的信息如下：

  　　1. Age : 35 years ; 2. Gender : Male ; 3. Highest Educational Qualification : Diploma holder; 4. Industry : Manufacturing; 5. Residence : Metro.

　　根据这五棵CART树的分类结果，我们可以针对这个人的信息建立收入层次的分布情况：

　　最后，我们得出结论，这个人的收入层次70%是一等，大约24%为二等，6%为三等，所以最终认定该人属于一等收入层次（小于$40,000）。

6. Scikit-learn实现随机森林

6.1 以函数f(x)=log(x)为例

import numpy as np
import pylab as pl


#
x = np.random.uniform(1, 100, 1000)
y = np.log(x) + np.random.normal(0, .3, 1000)

pl.scatter(x, y, s=1, label="log(x) with noise")

pl.plot(np.arange(1, 100), np.log(np.arange(1, 100)), c="b", label="log(x) true function")
pl.xlabel("x")
pl.ylabel("f(x) = log(x)")
pl.legend(loc="best")
pl.title("A Basic Log Function")
pl.show()

6.2 简单python示例

from sklearn.datasets import load_iris
from sklearn.ensemble import RandomForestClassifier
import pandas as pd
import numpy as np

iris = load_iris()
df = pd.DataFrame(iris.data, columns=iris.feature_names)
df['is_train'] = np.random.uniform(0, 1, len(df)) <= .75
df['species'] = pd.Categorical.from_codes(iris.target, iris.target_names)
df.head()

train, test = df[df['is_train']==True], df[df['is_train']==False]

features = df.columns[:4]
clf = RandomForestClassifier(n_jobs=2)
y, _ = pd.factorize(train['species'])
clf.fit(train[features], y)

preds = iris.target_names[clf.predict(test[features])]
pd.crosstab(test['species'], preds, rownames=['actual'], colnames=['preds'])

6.3 与其他机器学习分类算法进行对比

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from sklearn.cross_validation import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_moons, make_circles, make_classification
from sklearn.neighbors import KNeighborsClassifier
from sklearn.svm import SVC
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier, AdaBoostClassifier
from sklearn.naive_bayes import GaussianNB
from sklearn.lda import LDA
from sklearn.qda import QDA

h = .02  # step size in the mesh

names = ["Nearest Neighbors", "Linear SVM", "RBF SVM", "Decision Tree",
         "Random Forest", "AdaBoost", "Naive Bayes", "LDA", "QDA"]
classifiers = [
    KNeighborsClassifier(3),
    SVC(kernel="linear", C=0.025),
    SVC(gamma=2, C=1),
    DecisionTreeClassifier(max_depth=5),
    RandomForestClassifier(max_depth=5, n_estimators=10, max_features=1),
    AdaBoostClassifier(),
    GaussianNB(),
    LDA(),
    QDA()]

X, y = make_classification(n_features=2, n_redundant=0, n_informative=2,
                           random_state=1, n_clusters_per_class=1)
rng = np.random.RandomState(2)
X += 2 * rng.uniform(size=X.shape)
linearly_separable = (X, y)

datasets = [make_moons(noise=0.3, random_state=0),
            make_circles(noise=0.2, factor=0.5, random_state=1),
            linearly_separable
            ]

figure = plt.figure(figsize=(27, 9))
i = 1
# iterate over datasets
for ds in datasets:
    # preprocess dataset, split into training and test part
    X, y = ds
    X = StandardScaler().fit_transform(X)
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=.4)

    x_min, x_max = X[:, 0].min() - .5, X[:, 0].max() + .5
    y_min, y_max = X[:, 1].min() - .5, X[:, 1].max() + .5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))

    # just plot the dataset first
    cm = plt.cm.RdBu
    cm_bright = ListedColormap(['#FF0000', '#0000FF'])
    ax = plt.subplot(len(datasets), len(classifiers) + 1, i)
    # Plot the training points
    ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap=cm_bright)
    # and testing points
    ax.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap=cm_bright, alpha=0.6)
    ax.set_xlim(xx.min(), xx.max())
    ax.set_ylim(yy.min(), yy.max())
    ax.set_xticks(())
    ax.set_yticks(())
    i += 1

    # iterate over classifiers
    for name, clf in zip(names, classifiers):
        ax = plt.subplot(len(datasets), len(classifiers) + 1, i)
        clf.fit(X_train, y_train)
        score = clf.score(X_test, y_test)

        # Plot the decision boundary. For that, we will assign a color to each
        # point in the mesh [x_min, m_max]x[y_min, y_max].
        if hasattr(clf, "decision_function"):
            Z = clf.decision_function(np.c_[xx.ravel(), yy.ravel()])
        else:
            Z = clf.predict_proba(np.c_[xx.ravel(), yy.ravel()])[:, 1]

        # Put the result into a color plot
        Z = Z.reshape(xx.shape)
        ax.contourf(xx, yy, Z, cmap=cm, alpha=.8)

        # Plot also the training points
        ax.scatter(X_train[:, 0], X_train[:, 1], c=y_train, cmap=cm_bright)
        # and testing points
        ax.scatter(X_test[:, 0], X_test[:, 1], c=y_test, cmap=cm_bright,
                   alpha=0.6)

        ax.set_xlim(xx.min(), xx.max())
        ax.set_ylim(yy.min(), yy.max())
        ax.set_xticks(())
        ax.set_yticks(())
        ax.set_title(name)
        ax.text(xx.max() - .3, yy.min() + .3, ('%.2f' % score).lstrip('0'),
                size=15, horizontalalignment='right')
        i += 1

figure.subplots_adjust(left=.02, right=.98)
plt.show()

比对图：