随机森林
1 什么是随机森林？
随机森林就是用随机的方式建立一个森林，在森林里有很多决策树组成，并且每一棵决策树之间是没有关联的。当有一个新样本的时候，我们让森林的每一棵决策树分别进行判断，看看这个样本属于哪一类，然后用投票的方式，哪一类被选择的多，作为最终的分类结果。在回归问题中，随机森林输出所有决策树输出的平均值。随机森林既可以用于分类也可以用于回归。
2 随机森林有什么特点
1）对于很多种资料，它可以产生高准确度的分类器；
2）它可以处理大量的输入变数；
3）它可以在决定类别时，评估变数的重要性；
4）在建造森林时，它可以在内部对于一般化后的误差产生不偏差的估计；
5）它包含一个好方法可以估计遗失的资料，并且，如果有很大一部分的资料遗失，仍可以维持准确度；
6）它提供一个实验方法，可以去侦测variable interactions；
7）对于不平衡的分类资料集来说，它可以平衡误差；
8）它计算各例中的亲近度，对于数据挖掘、侦测离群点（outlier）和将资料视觉化非常有用；
9）它可被延伸应用在未标记的资料上，这类资料通常是使用非监督式聚类。也可侦测偏离者和观看资料；
10）学习过程是很快速的。
3 随机森林的基础知识
1）信息、熵、信息增益
这三个基本概念是决策树的根本，是决策树利用特征来分类时，确定特征选取顺序的依据。理解了它们，决策树你也就了解了大概。
信息
引用香农的话来说，信息是用来消除随机不确定性的东西。当然这句话虽然经典，但是还是很难去搞明白这种东西到底是个什么样，可能在不同的地方来说，指的东西又不一样。对于机器学习中的决策树而言，如果带分类的事物集合可以划分为多个类别当中，则某个类（xi）的信息可以定义如下:
I(x)用来表示随机变量的信息，p(xi)指是当xi发生时的概率。
熵
熵是用来度量不确定性的，当熵越大，X=xi的不确定性越大，反之越小。对于机器学习中的分类问题而言，熵越大即这个类别的不确定性更大，反之越小。
条件熵
条件熵是用来解释信息增益而引入的概念，概率定义：随机变量X在给定条件下随机变量Y的条件熵，对定义描述为：X给定条件下Y的条件概率分布的熵对X的数学期望，在机器学习中为选定某个特征后的熵，公式如下：
信息增益
信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好，在概率中定义为：待分类的集合的熵和选定某个特征的条件熵之差（这里只的是经验熵或经验条件熵，由于真正的熵并不知道，是根据样本计算出来的），公式如下：
2）决策树
决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。常见的决策树算法有C4.5、ID3和CART。
3）集成学习
集成学习通过建立几个模型组合的来解决单一预测问题。它的工作原理是生成多个分类器/模型，各自独立地学习和作出预测。这些预测最后结合成单预测，因此优于任何一个单分类的做出预测。
随机森林的生成
每棵树的按照如下规则生成：
1、用N来表示训练用例（样本）的个数，M表示特征数目。
2、输入特征数目m，用于确定决策树上一个节点的决策结果；其中m应远小于M。
3、从N个训练用例（样本）中以有放回抽样的方式，取样N次，形成一个训练集（即bootstrap取样），并用未抽到的用例（样本）作预测，评估其误差。
4、对于每一个节点，随机选择m个特征，决策树上每个节点的决定都是基于这些特征确定的。根据这m个特征，计算其最佳的分裂方式。
5、每棵树都会完整成长而不会剪枝，这有可能在建完一棵正常树状分类器后会被采用）
随机森林构建
决策树相当于一个大师，通过自己在数据集中学到的知识对于新的数据进行分类。但是俗话说得好，一个诸葛亮，玩不过三个臭皮匠。随机森林就是希望构建多个臭皮匠，希望最终的分类效果能够超过单个大师的一种算法。
那随机森林具体如何构建呢？有两个方面：数据的随机性选取，以及待选特征的随机选取。
1.数据的随机选取： 首先，从原始的数据集中采取有放回的抽样，构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。第二，利用子数据集来构建子决策树，将这个数据放到每个子决策树中，每个子决策树输出一个结果。最后，如果有了新的数据需要通过随机森林得到分类结果，就可以通过对子决策树的判断结果的投票，得到随机森林的输出结果了。如下图，假设随机森林中有3棵子决策树，2棵子树的分类结果是A类，1棵子树的分类结果是B类，那么随机森林的分类结果就是A类
2.待选特征的随机选取 与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选取最优的特征。这样能够使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。
本实验中随机森林用于回归的具体步骤：
1、从训练集中随机抽取一定数量的样本，作为每棵树的根节点样本；
2、在建立决策树时，使用最小方差作为分裂规则，即随机抽取一定数量的候选属性，根据候选属性和对应的特征值划分成两个数据集，两个数据集的方差和越小，该属性越适合作为分裂节点；
3、建立好随机森林以后，对于测试样本，进入每一颗决策树进行回归输出，每一颗决策树输出的均值作为最终结果。
使用随机森林解决波斯顿房价
接下来，我们会使用自己构建的随机森林来预测波斯顿的房价，这是一个回归问题。 该数据集是一个回归问题。每个类的观察值数量是均等的，共有 506 个观察，13 个输入变量和1个输出变量。 每条数据包含房屋以及房屋周围的详细信息。其中包含城镇犯罪率，一氧化氮浓度，住宅平均房间数，到中心区域的加权距离以及自住房平均房价等等。 CRIM：城镇人均犯罪率。 ZN：住宅用地超过 25000 sq.ft. 的比例。 INDUS：城镇非零售商用土地的比例。 CHAS：查理斯河空变量（如果边界是河流，则为1；否则为0）。 NOX：一氧化氮浓度。 RM：住宅平均房间数。 AGE：1940 年之前建成的自用房屋比例。 DIS：到波士顿五个中心区域的加权距离。 RAD：辐射性公路的接近指数。 TAX：每 10000 美元的全值财产税率。 PTRATIO：城镇师生比例。 B：1000（Bk-0.63）^ 2，其中 Bk 指代城镇中黑人的比例。 LSTAT：人口中地位低下者的比例。 MEDV：自住房的平均房价，以千美元计。
通过完成作业，你将会学到： 1、如何构建回归树； 2、如何利用回归树建立集成模型（随机森林）；3、如何评估模型效果。
不要单独创建一个文件，所有的都在这里面编写（在TODO后编写），不要试图改已经有的函数名字 （但可以根据需求自己定义新的函数）
在本次项目中，你将会用到以下几个工具：
sklearn。具体安装请见：http://scikit-learn.org/stable/install.html sklearn包含了各类机器学习算法和数据处理工具，包括本项目需要使用的词袋模型，均可以在sklearn工具包中找得到。numpy，数据处理库：www.numpy.orgjoblib，这是一个可以简单地将Python代码转换为并行计算模式的软件包，详情见https://pypi.org/project/joblib/
1.载入需要的包和数据
#导入需要用到的算法库 import numpy as np from numpy import * import random from sklearn.model_selection import train_test_split from sklearn.datasets import load_boston from sklearn.metrics import r2_score from joblib import Parallel, delayed import warnings warnings.filterwarnings('ignore')
# TODO：导入波斯顿数据并简单探查数据 boston = load_boston()
label_dict={"1":0,"2":3,"3":2} list(label_dict.keys())[list(label_dict.values()).index(sorted(list(label_dict.values()))[-1])]
'2'2.构建自己的随机森林
随机森林模型整体是一个myrf的类，所有的参数都包含再类中的成员变量和成员函数中。
需要同学通过补全各个模块的代码使随机森林能按照回归树的策略建立起来。
class myrf: # 存放树的列表 trees = [] # 随机种子 random_state = 0 # 树的个数 n_estimators = 10 # 最大特征数 max_features = 10 # 最大深度 max_depth = 10 # 切分新节点所需的最小阈值 min_change = 0.001 # 当前树的数量 cur_tree = 0 # 最小分割 min_samples_split = 0 # 叶子内节点的最小数目 min_samples_leaf = 0 # 每次建树时所用的样本占总样本的比例 sample_radio = 0.9 # 每次建树时所并行化处理器的个数 n_jobs = 10 # 计算y的方差 # 本来是要除总样本数的，考虑到对于所有的叶子来说，总样本数都是一致的，所以不除也可以。 def get_varience(self, dataSet): return np.var(dataSet[:,-1])*shape(dataSet)[0] ## TODO：计算y的均值 def get_mean(self,dataSet): return # 根据特征和特征值，把样本划分成高于该特征值的部分和低于该特征值的部分 def SplitDataSet(self, dataSet,feature,value): ## TODO：将数据集dataSet 按特征feature从小到大排序 dataSet = ## TODO：将数据集按特征值划分成高于特征值的部分和低于该特征值两个数据集 return # 选取最优的特征和特征值边界 def select_best_feature(self, dataSet): #计算特征的数目 feature_num=dataSet.shape[1]-1 features=np.random.choice(feature_num,self.max_features,replace=False) # 最好分数 bestS=inf; # 最优特征 bestfeature=0; # 最优特征的分割值 bestValue=0; S=self.get_varience(dataSet) ## TODO：判断样本数量是否足够，如果样本量少于最小分割，或者样本量少于叶子内节点的最小数目，就返回数据集的平均值结束程序 if : return None, # 遍历所有特征， for feature in features: ## TODO：将数据集按特征feature从小到大排序 dataSet = # 遍历数据集中的数据，控制叶子节点数目 for index in range(shape(dataSet)[0]-1): ## TODO: 排除dataSet数据集中的重复值 if : continue #将数据集按index分为前后两部分 data0 = dataSet[0:index+1, :] data1 = dataSet[index+1:, :] #判断样本数量是否足够，如果样本量少于最小分割，或者样本量少于叶子内节点的最小数目，就跳到下一个循环 if shape(data0)[0] < self.min_samples_leaf or shape(data1)[0] < self.min_samples_leaf: continue; #将两个数据集分别求取方差并加和作为新的分数 newS=self.get_varience(data0)+self.get_varience(data1) #如果最好分数大于新的分数，将新的分数赋值给最好分数，保证方差越小越好 if bestS>newS: bestfeature=feature bestValue=dataSet[index][feature] # print(bestfeature, bestValue) bestS=newS #如果误差不大就退出，说明无法分割 if (S-bestS)<self.min_change: return None,self.get_mean(dataSet) # print(bestfeature, bestValue) return bestfeature,bestValue # 搭建单颗决策树 def createTree(self, dataSet, max_level, flag = 0): if flag == 0: seqtree = self.cur_tree+1 self.cur_tree = seqtree; print('正在搭建第',seqtree,'棵树...') #选择最适合的特征和值来构建树 bestfeature,bestValue=self.select_best_feature(dataSet) if bestfeature==None: if flag == 0: print('第',seqtree,'棵树搭建完成！') return bestValue retTree={} max_level-=1 if max_level<0: #控制深度 return self.get_mean(dataSet) retTree['bestFeature']=bestfeature retTree['bestVal']=bestValue ## TODO: 使用self.SplitDataSet将数据集按bestfeature和bestValue分割成左右两棵树数据集 lSet,rSet= # 使用self.createTree将左右两棵树数据集构建成树 retTree['right']=self.createTree(rSet,self.max_depth,1) retTree['left']=self.createTree(lSet,self.max_depth,1) if flag == 0: print('第',seqtree,'棵树搭建完成！') return retTree # 初始化随机森林 def __init__(self, random_state, n_estimators, max_features, max_depth, min_change = 0.001, min_samples_split = 0, min_samples_leaf = 0, sample_radio = 0.9, n_jobs = 10): self.trees = [] self.random_state = random_state np.random.seed(self.random_state) self.n_estimators = n_estimators self.max_features = max_features self.max_depth = max_depth self.min_change = min_change self.min_samples_leaf = min_samples_leaf self.min_samples_split = min_samples_split self.sample_radio = sample_radio self.n_jobs = n_jobs # 向森林添加单棵决策树 def get_one_tree(self, dataSet): X_train, X_test, y_train, y_test = train_test_split(dataSet[:,:-1], dataSet[:,-1], train_size = self.sample_radio, random_state = self.random_state) X_train=np.concatenate((X_train,y_train.reshape((-1,1))),axis=1) self.trees.append(self.createTree(X_train,self.max_depth)) # 并行化搭建随机森林 def fit(self, X, Y): #树的个数，预测时使用的特征的数目，树的深度 dataSet = np.concatenate((X, Y.reshape(-1,1)), axis = -1) Parallel(n_jobs=self.n_jobs, backend="threading")(delayed(self.get_one_tree)(dataSet) for _ in range(self.n_estimators)) #预测单个数据样本 def treeForecast(self,tree,data): if not isinstance(tree,dict): return float(tree) if data[tree['bestFeature']]>tree['bestVal']: if type(tree['left'])=='float': return tree['left'] else: return self.treeForecast(tree['left'],data) else: if type(tree['right'])=='float': return tree['right'] else: return self.treeForecast(tree['right'],data) # 单决策树预测结果 def createForeCast(self,tree,dataSet): seqtree = self.cur_tree+1 self.cur_tree = seqtree; print('第'+str(seqtree)+'棵树正在预测...\n') l=len(dataSet) predict=np.mat(zeros((l,1))) for i in range(l): predict[i,0]=self.treeForecast(tree,dataSet[i,:]) print('第'+str(seqtree)+'棵树预测完成!') return predict ## TODO: 使用self.createForestCast函数更新预测值函数 def unpdate_predict(self, predict, tree, X): predict+= # 随机森林预测结果 def predict(self,X): self.cur_tree = 0; l=len(X) predict=np.mat(zeros((l,1))) Parallel(n_jobs=self.n_jobs, backend="threading")(delayed(self.unpdate_predict)(predict, tree, X) for tree in self.trees) # 对多棵树预测的结果取平均 predict/=self.n_estimators return predict # 获取模型分数 def get_score(self,target, X): return r2_score(target, self.predict(X))
3.实例化随机森林并对boston数据进行训练、预测
# rf2 = mycache(random_state=2, n_estimators=10, max_features=3, max_depth=10, min_change=0.001, min_samples_split=20, n_jobs=10) rf1 = myrf(random_state=2, n_estimators=10, max_features=3, max_depth=10, min_change=0.001, min_samples_split=20, n_jobs=-1) ## TODO: 使用rf1的fit函数对训练特征数据boston.data和训练目标变量boston.target进行训练
正在搭建第1棵树... 正在搭建第2棵树... 正在搭建第3棵树... 正在搭建第4棵树... 第2棵树搭建完成！ 正在搭建第5棵树... 第1棵树搭建完成！ 第3棵树搭建完成！正在搭建第6棵树... 正在搭建第7棵树... 第4棵树搭建完成！ 正在搭建第8棵树... 第5棵树搭建完成！ 第7棵树搭建完成！ 正在搭建第9棵树... 第6棵树搭建完成！正在搭建第10棵树... 第8棵树搭建完成！ 第10棵树搭建完成！ 第9棵树搭建完成！
## TODO：使用rf1的get_score函数对boston.target和boston.data进行预测并评价结果
第1棵树正在预测... 第2棵树正在预测... 第1棵树预测完成! 第3棵树正在预测... 第4棵树正在预测... 第5棵树正在预测... 第5棵树预测完成! 第6棵树正在预测... 第3棵树预测完成! 第7棵树正在预测... 第7棵树预测完成! 第8棵树正在预测... 第2棵树预测完成! 第8棵树预测完成! 第4棵树预测完成! 第9棵树正在预测... 第9棵树预测完成! 第10棵树正在预测... 第10棵树预测完成! 第6棵树预测完成!