机器学习——随机森林（RF）算法
英文证明信随机森林定义
随机森林是⼀种⽐较新的模型。经典的机器学习模型是神经⽹络，有半个多世纪的历史了。神经⽹络预测精确，但是计算量很⼤。上世纪⼋⼗年代Breiman等⼈发明分类树的（Breiman et al. 1984），通过反复⼆分数据进⾏分类或回归，计算量⼤⼤降低。2001年Breiman把分类树组合成随机森林（Breiman 2001a），即通过对数据集的采样⽣成多个不同的数据集，并在每⼀个数据集上训练出⼀颗分类树，最终结合每⼀颗分类树的预测结果作为随机森林的预测结果。随机森林在运算量没有显著提⾼的前提下提⾼了预测精度。随机森林对多元公线性不敏感，结果对缺失数据和⾮平衡的数据⽐较稳健，可以很好地预测多达⼏千个解释变量的作⽤
（Breiman 2001b），被誉为当前最好的算法之⼀（Iverson et al. 2008）。
随机森林顾名思义，是⽤随机的⽅式建⽴⼀个森林，森林⾥⾯有很多的决策树组成，随机森林的每⼀棵决策树之间是没有关联的。在得到森林之后，当有⼀个新的输⼊样本进⼊的时候，就让森林中的每⼀棵决策树分别进⾏⼀下判断，看看这个样本应该属于哪⼀类（对于分类算法），然后看看哪⼀类被选择最多，就预测这个样本为那⼀类。随机森林可以既可以处理属性为离散值的量，⽐如ID3算法，也可以处理属性为连续值的量，⽐如C4.5算法。另外，随机森林还可以⽤来进⾏⽆监督学习聚类和异常点检测。
随机森林的构造过程：
1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择⼀个样本，然后返回继续选择)。这选择好了的N个样本⽤来训练⼀个
决策树，作为决策树根节点处的样本。
2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满⾜条件m << M。然后从这m
个属性中采⽤某种策略（⽐如说信息增益）来选择1个属性作为该节点的分裂属性。
幸福是奋斗出来的
3. 决策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下⼀次该节点选出来的那⼀个属性是刚刚其⽗节点分裂时⽤
过的属性，则该节点已经达到了叶⼦节点，⽆须继续分裂了）。⼀直到不能够再分裂为⽌。注意整个决策树形成过程中没有进⾏剪枝。
4. 按照步骤1~3建⽴⼤量的决策树，这样就构成了随机森林了。
在建⽴每⼀棵决策树的过程中，有两点需要注意采样与完全分裂。
⾸先是两个随机采样的过程，random forest对输⼊的数据要进⾏⾏、列的采样。对于⾏采样，采⽤有放回的⽅式，也就是在采样得到的样本集合中，可能有重复的样本。假设输⼊样本为N个，那么采样的样本也为N个。这样使得在训练的时候，每⼀棵树的输⼊样本都不是全部的样本，使得相对不容易出现over-fitting。然后进⾏列采样，从M个feature中，选择m个（m << M）。六级听力满分多少
之后就是对采样之后的数据使⽤完全分裂的⽅式建⽴出决策树，这样决策树的某⼀个叶⼦节点要么是⽆法继续分裂的，要么⾥⾯的所有样本的都是指向的同⼀个分类。⼀般很多的决策树算法都⼀个重要的步骤——剪枝，但是这⾥不这样⼲，由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。
下⾯，讲⼀下如何⽤代码实现随机森林。
代码实现流程：
（1） 导⼊⽂件并将所有特征转换为float形式
（2） 将数据集分成n份，⽅便交叉验证
（3） 构造数据⼦集（随机采样），并在指定特征个数（假设m个，⼿动调参）下选取最优特征
（4） 构造决策树
（5） 创建随机森林（多个决策树的结合）
（6） 输⼊测试集并进⾏测试，输出预测结果
（1）导⼊⽂件并将所有特征转换为float形式
#加载数据
def loadCSV(filename):
dataSet=[]
with open(filename,'r') as file:
ader(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(t(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:
internatleft,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
2016年5月7日
#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):
shield
return predict(tree['left'],row)
el:
return tree['left']
el:otherthan
if isinstance(tree['right'],dict):
三级考试成绩查询
return predict(tree['right'],row)
el:
return tree['right']
# predictions=t(predictions)
对以上代码的⼀点总结：
训练部分：假设我们取datat中的m个feature来构造决策树，⾸先，我们遍历m个feature中的每⼀个feature，再遍历每⼀⾏，通过spilt_loss函数（计算分割代价）来选取最优的特征及特征值，根据是否⼤于这个特征值进⾏分类（分成left,right两类），循环执⾏上述步骤，直⾄不可分或者达到递归限值（⽤来防⽌过拟合），最后得到⼀个决策树tree。
测试部分：对测试集的每⼀⾏进⾏判断，决策树tree是⼀个多层字典，每⼀层为⼀个⼆分类，将每⼀⾏按照决策树tree中的分类索引index⼀步⼀步向⾥层探索，直⾄不出现字典时探索结束，得到的值即为我们的预测值。
