一、随机森林简介
1. 装袋
装袋（bagging）又称自助聚集（bootstrap aggregating），是一种根据均匀概率分布从数据集中重复抽样（有放回的）的技术。每个自助样本集都和原始数据集一样大。由于抽过程是有回放的，因此一些样本可能在同一训练数据集总出现多次，而其它一些却可能被忽略。一般来说，自助样本
大约包含63%的原训练数据，因为每一样本抽样到
的概率为
，如果N 足够大，这个概率将收敛于
。训练过k 个分类器后，测试样本被指派到得票最高的类。
为了说明装袋如何进行，考虑表1给出的数据集。设x 表示一维属性，y 表示类标号。假设使用这样一个分类器，它是仅包含一层的二叉决策树，具有一个测试条件x≤k ,其中k是使得叶节点熵最小的分裂点。这样的树也称为是决策树桩（decision stump）。
X | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|
Y | 1 | 1 | 1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
表1 用于构建装袋组合分类器的数据集例子
不进行装袋，能产生的最好的决策树桩的分裂点为x≤0.35或x≤0.75。无论选择哪一个，树的准确率最多为70%。假设我们在数据集上应用10个自助样本集的装袋过程，图1给出了每轮装袋选择的训练样本。在每个表的右边，给出了分类器产生的决策边界。
图1 装袋的例子
通过对每个基分类器所作的预测使用多数表决来分类表1给出的整个数据集。表2给出了预测结果。由于类标号是-1或 1，因此应用多数表决等价于对y 的预测值求和，然后考察结果的符号。注意，组合分类器完全正确地分类了原始数据集中的10个样本。
轮 | x=0.1 | x=0.2 | x=0.3 | x=0.4 | x=0.5 | x=0.6 | x=0.7 | x=0.8 | x=0.9 | x=1.0 |
|---|---|---|---|---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
4 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
5 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
6 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
7 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
8 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
9 | -1 | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
10 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
和 | 2 | 2 | 2 | -6 | -6 | -6 | -6 | 2 | 2 | 2 |
符号 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
实际类 | 1 | 1 | 1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 |
表2 使用装袋方法构建组合分类器的例子
前面的例子也说明了使用组合方法的有一个优点：增强了目标函数的表达功能。即使每核基分类器都是一个决策树桩，组合的分类器也能表示一棵深度为2的决策树。
装袋通过降低基分类器方差改善了泛化误差。装袋的性能依赖于基分类器的稳定性。如果基分类器是不稳定的，装袋有助于减低训练数据的随机波动导致的误差；如果基分类器是稳定的，即对训练数据集中的微小变化是鲁棒的，则组合分类器的误差主要是由基分类器的偏倚所引起的。在这种情况下，装袋可能不会对基分类器的性能有显著改善，装袋甚至可能降低分类器的性能，因为每个训练集的有效容量比原数据集大约小37%。
最后，由于每一个样本被选中的概率都相同，因此装袋并不侧重于数据集中的任何特定实例。因此，用于噪声数据，装袋不太受过分拟合的影响。
2. 随机森林
随机森林（random forest）是一类专门为决策树分类器设计的组合方法。它组合多棵决策树作出的预测，其中每棵树都是基于随即向量的一个独立集合产生的，如图2所示。随机森林采用一个固定的概率分布来产生随机向量。使用决策树装袋是随机森林的特例，通过随机地从原训练集中有回放地选取N个样本，将随机性加入到构建模型的过程中。整个模型构建过程中，装袋也是用同样的均匀概率分布来产生它的自助样本。
图2 随机森林
已经从理论上证明，当树的数目足够大时，随机森林的泛化误差的上界收敛于下面的表达式（公式1）：
其中
是树之间的平均相关系数，
是度量树型分类器的“强度”的量。一组分类器的强度是指分类器的平均性能，而性能以分类器的余量（M）用概率算法度量：
其中
是根据某随机变量
构建的分类器对
作出的预测类。余量越大，分类器正确预测给定的样本
的可能性就越大。公式1是相当直观的，随着树的相关性增加或组合分类器的强度降低，泛化误差的上界趋向于增加。随机化有助于减少决策树之间的相关性，杏儿改善组合分类器的泛化误差。
每棵决策树都使用一个从某固定概率分布产生的随机向量。可以使用多种方法将随机向量合并到树的增长过程中。第一种方法是随机选择F 个输入特征来对决策树的节点进行分裂。这样，分裂节点的决策是根据这F 个选定的特征，而不是考察所有可用的特征来决定。然后，让树完全增长而不进行任何修剪，这可能有助于减少结果树的偏倚。树构建完毕之后，就可以使用多数表决的方法来组合预测。这种方法称为Forest-RI，其中RI指随机输入选择。为了增加随机性，可以使用装袋来为Forest-RI产生自助样本。随机森林的强度趋向于随着输入特征数F 的增加而提高。作为折中，通常选取特征的数目为
,其中
是输入特征数。由于在每一个节点仅仅需要考察特征的一个子集，这种方法将显著减少算法运行的时间。
如果原始特征
的数目太小，则很难选择一个独立的随机特征集合来建立决策树。一种加大特征空间的办法是创建输入特征的线性组合。具体地说，在每一个节点，新特征通过随机选择L 个输入特征来构建。这些输入特征用区间[-1,1]上的均匀分布产生的系数进行线性组合。在每个节点，产生F 个这种随机组合的新特征，并且从中选择最好的来分裂节点。这种方法称为Forest-RC。
生成随机树的第三种方法是：在决策树的每一个节点，从F个最佳划分中随机选择一个。除非F 足够大，否则这种方法可能产生比Forest-RI和Forest-RC相关性更强的树。这种方法也没有Forest-RI和Forest-RC节省运行时间，因为算法需要在决策树的每个节点考察所有的分裂特征。
二、MADlib的随机森林相关函数
1. 训练函数
（1）语法
随机森林训练函数具有以下格式：
代码语言：javascript复制forest_train(training_table_name,
output_table_name,
id_col_name,
dependent_variable,
list_of_features,
list_of_features_to_exclude,
grouping_cols,
num_trees,
num_random_features,
importance,
num_permutations,
max_tree_depth,
min_split,
min_bucket,
num_splits,
surrogate_params,
verbose,
sample_ratio
)（2）参数
参数名称 | 数据类型 | 描述 |
|---|---|---|
training_table_name | TEXT | 包含培训数据的表的名称。 |
output_table_name | TEXT | 包含生成模型的表的名称。会创建三个表，名称基于训练函数中output_table_name参数的值。三个输出表列分别如表4-表6所示。 |
id_col_name | TEXT | 包含训练数据中id信息的列名。 |
dependent_variable | TEXT | 包含用于训练输出的列名。分类输出Boolean、integer或text类型，而回归输出float类型的值。 |
list_of_features | TEXT | 用作预测的逗号分隔的特征列名。可以是“*”，说明将所有列用作预测的特征列（除在下一个参数中包含的列外）。类别列可以是Boolean、integer或text类型。 |
list_of_features_to_exclude | TEXT | 排除在预测列表以外的逗号分隔的列名字符串。如果dependent_variable参数是一个表达式（包括列名的转换），那么这个列表中应该包含dependent_variable表达式中的列，否则那些列将包含在特征中，结果将生成无意义的树。 |
grouping_cols（可选） | TEXT | 缺省值为NULL，逗号分隔的分组列名，每个分组会建立一个随机森林。 |
num_trees（可选） | INTEGER | 缺省值为100，随机森林模型中产生的决策树的最大数目。实际产生的决策树数量可能稍有不同。 |
num_random_features（可选） | INTEGER | 每次分裂随机选择的特征数。分类树的缺省值为sqrt(n)，否则为n/3。 |
importance（可选） | BOOLEAN | 缺省值为true，是否计算变量的重要性。如果设置为true，将在分组模型表（<model_table>_group）中输出分类特征和连续特征的变量重要性。计算变量重要性将增加函数的运行时间。 |
num_permutations（可选） | INTEGER | 缺省值为1。计算变量重要性时，每个特征值的重排次数。一个特征变量的重要性是通过重排变量的随机值计算的，计算预测精度的下降（使用OOB采样）。设置大于1的值将计算多个重要性的平均值，这会增加总体运行时间。大多数情况下，缺省值1对计算重要性已经足够。 |
max_depth（可选） | INTEGER | 缺省值为10。一棵树中任意节点的最大深度，根节点的深度为0。 |
min_split（可选） | INTEGER | 缺省值为20。试图分裂的节点中必须存在的最小观测数。 |
min_bucket（可选） | INTEGER | 缺省值为min_split/3。任何终端节点的最小观测数。如果只指定min_bucket和min_split之一，则min_split被设置成min_bucket * 3，或者min_bucket被设置成min_split / 3。 |
num_splits（可选） | INTEGER | 缺省值为100。连续特征值被离散时，计算分裂边界的个数。这个全局参数用于计算连续特征的拆分的结果。较大值会导致更好的预测，但也会增加处理时间。 |
surrogate_params（可选） | TEXT | 逗号分隔的键值对字符串，用于控制树中每个节点的代理拆分行为。可指定max_surrogates，缺省值为0，指定每个节点存储的代理数量。 |
verbose（可选） | BOOLEAN | 缺省值为false。是否提供训练结果的详细输出。 |
sample_ratio（可选） | DOUBLE PRECISION | 缺省值为1，范围是(0,1]。如果sample_ratio小于1，bootstrap样本小于用于在森林中每棵树训练的预期值。一个接近0的比率可能导致只有根节点的树。这允许用户快速对该功能进行实验。 |
表3 forest_train函数参数说明
注意，影响内存使用的主要参数有：树的深度，特征数量，每个特征值（由num_splits控制）。如果碰到VMEM限制，考虑减小一个或多个参数。
训练函数生成的模型表包含以下列：
列名 | 数据类型 | 描述 |
|---|---|---|
gid | INTEGER | 分组ID。 |
sample_id | INTEGER | bootstrap样本id |
tree | bytea8 | 以二进制格式存储的训练树模型。 |
表4 forest_train函数模型输出表列说明
训练函数在产生输出表的同时，还会创建一个名为<model_table>_summary的概要表，具有以下列：
列名 | 数据类型 | 描述 |
|---|---|---|
Method | TEXT | 'forest_train' |
is_classification | BOOLEAN | 分类模型为True。 |
source_table | TEXT | 源表名。 |
model_table | TEXT | 模型表名。 |
id_col_name | TEXT | ID列名 |
dependent_varname | TEXT | 因变量。 |
independent_varname | TEXT | 自变量。 |
cat_features | TEXT | 类别特征名。 |
con_features | TEXT | 连续特征名。 |
grouping_col | INT | 分组列名。 |
num_trees | INT | 模型产生的决策树数量。 |
num_random_features | INT | 每次分裂随机选择的特征数。 |
max_tree_depth | INT | 随机森林中任意树的最大深度。 |
min_split | INT | 要分割的节点中的最小观测数。 |
min_bucket | INT | 任何终端节点的最小观测数。 |
num_splits | INT | 连续变量的桶数。 |
verbose | BOOLEAN | 是否显示debug信息。 |
importance | BOOLEAN | 是否计算变量重要性。 |
num_permutations | INT | 计算变量重要性时，每个特征值的重排次数，缺省值为1。 |
num_all_groups | INT | 分组数。 |
num_failed_groups | INT | 失败的分组数。 |
total_rows_processed | BIGINT | 所有分组处理的总行数。 |
total_rows_skipped | BIGINT | 由于缺少值或失败，所有组中跳过的行总数。 |
dependent_var_levels | TEXT | 对于分类，因变量的不同值。 |
dependent_var_type | TEXT | 因变量数据类型。 |
表5 forest_train函数概要输出表列说明
名为<model_table>_group的分组表具有以下列：
列名 | 数据类型 | 描述 |
|---|---|---|
Gid | INTEGER | 唯一标识一组分组列值的组ID。 |
<...> | TEXT | 分组列，取决于grouping_cols输入可能有多个列。 |
Success | BOOLEAN | 标识分组是否成功。 |
cat_levels_in_text | TEXT[] | 分类变量的序号。 |
cat_n_levels | INTEGER[] | 每个分类变量的级别。 |
oob_error | DOUBLE PRECISION | 随机森林模型的无袋误差。 |
cat_var_importance | DOUBLE PRECISION[] | 分类特征变量的重要性，顺序与<model_table>_summary表中cat_features列的顺序对应。 |
con_var_importance | DOUBLE PRECISION[] | 连续特征变量的重要性，顺序与<model_table>_summary表中cat_features列的顺序对应。 |
表6 forest_train函数分组输出表列说明
2. 预测函数
预测函数给出新样本的所属类别估计。
（1）语法
代码语言：javascript复制forest_predict(random_forest_model,
new_data_table,
output_table,
type)（2）参数
参数名称 | 数据类型 | 描述 |
|---|---|---|
forest_model | TEXT | 模型表名。 |
new_data_table | TEXT | 包含被预测数据的表名。 |
output_table | TEXT | 预测结果输出表 |
Type（可选） | TEXT | 缺省值为'response'。对于回归模型，输出总是依赖变量的预测值。对于分类模型，类型变量可以是“response”，将分类预测作为输出，或者是“概率”，给出类概率作为输出。对于因变量的每个值，在输出表中添加一个有概率的列。 |
表7 forest_predict函数参数说明
3. 显示函数
‘get_tree’函数提供了随机森林中单一决策树的图形化表示。输出可以是dot格式，或者是一个简单的文本格式。dot格式可以使用GraphViz等程序进行可视化。
（1）语法
代码语言：javascript复制get_tree(forest_model_table,
gid,
sample_id,
dot_format,
verbose)还有一个显示函数输出为每个内部节点选择的替代分裂点：
代码语言：javascript复制get_tree_surr(forest_model_table,
gid,
sample_id)输出包含决策树中每个内部节点的替代分裂点列表。节点按ID按升序排序。对每一个替代分裂点，输出提供代理拆分的变量和阈值，并提供主拆分和替代拆分之间的行数。最后，还列出主拆分的大多数分支中存在的行数。只有比大多数分支表现更好的替代分裂才被使用。当主变量具有空值时，使用代理变量计算该节点的拆分。如果所有代理变量都为null，则使用多数分支计算一个元组的拆分。
（2）参数
参数名称 | 数据类型 | 描述 |
|---|---|---|
forest_model_table | TEXT | 模型表名。 |
gid | INTEGER | 分组ID。 |
sample_id | INTEGER | Bootstrap样本ID。 |
dot_format（可选） | BOOLEAN | 缺省值为TRUE，使用dot格式，否则输出文本格式。 |
Verbose（可选） | BOOLEAN | 缺省值为FALSE。如果设置为TRUE，dot格式输出中包含附加信息，如不纯度、样本大小、每个因变量的权重行数、被剪枝的分类或预测等。输出总是返回文本形式，对于dot格式，可以重定向输出到客户端文件，然后使用可视化程序处理。 |
表8 get_tree函数参数说明
三、随机森林示例
我们将利用MADlib的决策树相关函数解决根据天气情况预测是否打高尔夫球的问题。问题描述及其已知数据参见“MADlib——基于SQL的数据挖掘解决方案（21）——分类之KNN”。
1. 准备输入数据
代码语言：javascript复制drop table if exists dt_golf;
create table dt_golf (
id integer not null,
"outlook" text,
temperature double precision,
humidity double precision,
windy text,
class text
);
insert into dt_golf (id,"outlook",temperature,humidity,windy,class) values
(1, 'sunny', 85, 85, 'false', 'don''t play'),
(2, 'sunny', 80, 90, 'true', 'don''t play'),
(3, 'overcast', 83, 78, 'false', 'play'),
(4, 'rain', 70, 96, 'false', 'play'),
(5, 'rain', 68, 80, 'false', 'play'),
(6, 'rain', 65, 70, 'true', 'don''t play'),
(7, 'overcast', 64, 65, 'true', 'play'),
(8, 'sunny', 72, 95, 'false', 'don''t play'),
(9, 'sunny', 69, 70, 'false', 'play'),
(10, 'rain', 75, 80, 'false', 'play'),
(11, 'sunny', 75, 70, 'true', 'play'),
(12, 'overcast', 72, 90, 'true', 'play'),
(13, 'overcast', 81, 75, 'false', 'play'),
(14, 'rain', 71, 80, 'true', 'don''t play');2. 运行随机森林训练函数
代码语言：javascript复制drop table if exists train_output, train_output_group, train_output_summary;
select madlib.forest_train('dt_golf', -- source table
'train_output', -- output model table
'id', -- id column
'class', -- response
'"outlook", temperature, humidity, windy', -- features
null, -- exclude columns
null, -- grouping columns
20::integer, -- number of trees
2::integer, -- number of random features
true::boolean, -- variable importance
1::integer, -- num_permutations
8::integer, -- max depth
3::integer, -- min split
1::integer, -- min bucket
10::integer -- number of splits per continuous variable
); 3. 查看输出
查看概要输出表：
代码语言：javascript复制x on
select * from train_output_summary;结果：
代码语言：javascript复制-[ RECORD 1 ]--------- -----------------------------------------------
method | forest_train
is_classification | t
source_table | dt_golf
model_table | train_output
id_col_name | id
dependent_varname | class
independent_varnames | "outlook",windy,temperature,humidity
cat_features | "outlook",windy
con_features | temperature,humidity
grouping_cols |
num_trees | 20
num_random_features | 2
max_tree_depth | 8
min_split | 3
min_bucket | 1
num_splits | 10
verbose | f
importance | t
num_permutations | 1
num_all_groups | 1
num_failed_groups | 0
total_rows_processed | 14
total_rows_skipped | 0
dependent_var_levels | "don't play","play"
dependent_var_type | text
independent_var_types | text, text, double precision, double precision查看分组输出表：
代码语言：javascript复制select * from train_output_group;结果：
代码语言：javascript复制-[ RECORD 1 ]------ ----------------------------------------
gid | 1
success | t
cat_n_levels | {3,2}
cat_levels_in_text | {overcast,sunny,rain,false,true}
oob_error | 0.64285714285714285714
cat_var_importance | {-0.208452380952381,-0.223511904761905}
con_var_importance | {-0.258988095238095,-0.250178571428571}4. 获取森林中单个树的dot格式显示
代码语言：javascript复制x off
select madlib.get_tree('train_output',1,2);结果：
代码语言：javascript复制 get_tree
---------------------------------------------------------
digraph "Classification tree for dt_golf" {
"0" [label="humidity <= 80", shape=ellipse];
"0" -> "1"[label="yes"];
"0" -> "2"[label="no"];
"2" [label=""don't play"",shape=box];
"1" [label="windy in {false}", shape=ellipse];
"1" -> "3"[label="yes"];
"3" [label=""play"",shape=box];
"1" -> "4"[label="no"];
"4" [label=""outlook" in {overcast}", shape=ellipse];
"4" -> "9"[label="yes"];
"9" [label=""play"",shape=box];
"4" -> "10"[label="no"];
"10" [label=""don't play"",shape=box];
} //---end of digraph---------
(1 row)5. 获取树的文本格式显示
代码语言：javascript复制select madlib.get_tree('train_output',1,2,false);结果：
代码语言：javascript复制 get_tree
---------------------------------------------------------------------------
-------------------------------------
- Each node represented by 'id' inside ().
- Each internal nodes has the split condition at the end, while each
leaf node has a * at the end.
- For each internal node (i), its child nodes are indented by 1 level
with ids (2i 1) for True node and (2i 2) for False node.
- Number of (weighted) rows for each response variable inside [].'
The response label order is given as ['"don't play"', '"play"'].
For each leaf, the prediction is given after the '-->'
-------------------------------------
(0)[ 3 11] humidity <= 80
(1)[ 1 11] windy in {false}
(3)[0 9] * --> "play"
(4)[1 2] "outlook" in {overcast}
(9)[0 2] * --> "play"
(10)[1 0] * --> "don't play"
(2)[2 0] * --> "don't play"
(1 row)6. 为相同的输入数据预测输出类别
代码语言：javascript复制drop table if exists prediction_results;
select madlib.forest_predict('train_output',
'dt_golf',
'prediction_results',
'response');
x off
select id, estimated_class, class
from prediction_results join dt_golf using (id)
order by id;结果：
代码语言：javascript复制 id | estimated_class | class
---- ----------------- ------------
1 | don't play | don't play
2 | don't play | don't play
3 | play | play
4 | play | play
5 | play | play
6 | don't play | don't play
7 | play | play
8 | don't play | don't play
9 | play | play
10 | play | play
11 | play | play
12 | play | play
13 | play | play
14 | don't play | don't play
(14 rows)7. 预测的数据输出类别概率
代码语言：javascript复制drop table if exists prediction_prob;
select madlib.forest_predict('train_output',
'dt_golf',
'prediction_prob',
'prob');
x off
select id, "estimated_prob_play", class
from prediction_prob join dt_golf using (id)
order by id;结果：
代码语言：javascript复制 id | estimated_prob_play | class
---- --------------------- ------------
1 | 0.15 | don't play
2 | 0.15 | don't play
3 | 0.8 | play
4 | 0.6 | play
5 | 0.8 | play
6 | 0.3 | don't play
7 | 0.85 | play
8 | 0.15 | don't play
9 | 0.8 | play
10 | 0.75 | play
11 | 0.65 | play
12 | 0.85 | play
13 | 0.9 | play
14 | 0.3 | don't play
(14 rows)
