2023年6月22日发(作者：)

RandomForest随机森林算法Random Forest是加州⼤学伯克利分校的Breiman Leo和Adele Cutler于2001年发表的论⽂中提到的新的机器学习算法，可以⽤来做分类，聚类，回归，这⾥只简单介绍该算法在分类上的应⽤。Random Forest（随机森林）算法是通过训练多个决策树，⽣成模型，然后综合利⽤多个决策树的分类结果进⾏投票，从⽽实现分类。随机森林算法只需要两个参数：构建的决策树的个数t，在决策树的每个节点进⾏分裂时需要考虑的输⼊特征的个数m。算法流程1. ⽣成单棵决策树：（1）训练总样本的个数为N，则单棵决策树从N个训练集中有放回的随机抽取n个作为此单颗树的训练样本。（2）令训练样例的输⼊特征的个数为M，m远远⼩于M，则我们在每颗决策树的每个节点上进⾏分裂时，从M个输⼊特征⾥随机选择m个输⼊特征，然后从这m个输⼊特征⾥选择⼀个最好的进⾏分裂。m在构建决策树的过程中不会 改变。这⾥注意，要为每个节点随机选出m个特征，然后选择最好的那个特征来分裂。（3）每棵树都⼀直这样分裂下去，直到该节点的所有训练样例都属于同⼀类。不需要剪枝。由于之前的两个随机采样的过程保证了随机性，所以就算不剪枝，也不会出现over-fitting。 2. ⽣成t颗决策树 按照1的⽅式产⽣t颗决策树加⼊到森林中3.利⽤随机森林分类对于每个新的测试样例，综合多个决策树的分类结果来作为随机森林的分类结果。（1）⽬标特征为数字类型：取t个决策树的平均值作为分类结果。（2）⽬标特征为类别类型：少数服从多数，取单棵树分类结果最多的那个类别作为整个随机森林的分类结果。

算法1中，⽤majority vote表⽰多数投票．随机森林的泛化误差依赖于以下两个因素：RF中任意两棵树的相关度(correlation)和RF中单棵树的分类效能(strength)。关于随机性随机性主要体现在两个⽅⾯：（1）训练每棵树时，从全部训练样本中选取⼀个⼦集进⾏训练（即bootstrap取样）。⽤剩余的数据进⾏评测，评估其 误差；（2）在每个节点，随机选取所有特征的⼀个⼦集，⽤来计算最佳分割⽅式。为什么有效采⽤bagging和randomization结合的⽅法，Bagging(bootstrap aggregating)⽅法制造有差异的训练样本集，构建单棵决策树时采⽤⼀种随机⼦空间划分(random subspacemethod)的策略，从随机选择的部分属性中挑选最佳属性对内部节点进⾏属性分裂，在保证单颗树分类效能的同时，减少了各分类树之间的相关度，降低了噪声的影响，降低过拟合情况产⽣的可能，从⽽提⾼了组合分类器的性能。由于树随机⽣成的树，⼤部分的树(或许 99.9%树) 不会对学习的分类/回归问题都有意义 。但是随着很多糟糕的决策树被⽣成，其中也会有很少确实很优秀的决策树。当你要做预测的时候，新的观察到的特征随着决策树⾃上⽽下⾛下来，这样⼀组观察到的特征将会被贴上⼀个预测值/标签。⼀旦森林中的每棵树都给出了预测值/标签，所有的预测结果将被归总到⼀起，所有树的模式投票被返回做为最终的预测结果。简单来说，99.9%不相关的树做出的预测结果涵盖所有的情况，这些预测结果将会彼此抵消。少数优秀的树的预测结果将会超脱于芸芸“噪⾳”，做出⼀个好的预测。% 函数返回⼀棵决策树function [node,child_value,child_node_num]=ID3(S)%%% clear clear global node child_value child_node_num; global node child_value child_node_num %S=xlsread('');%%% DValue=S(:,1:6);

DValue=roundn(DValue,-1); CN=S(:,7); CN=num2str(CN);%将标签设为string型 for i=1:length(CN) A(i)=i; end ClassPNum=[1 2 3 4 5 6]; m=0; [node,child_value,child_node_num]=TreeNode( DValue, CN, A, ClassPNum,m );

end% ⽣成树结点% DValue--前四列数据% A--参与划分的⾏号% CN--属性值的集合（第5列数据）% ClassPNum为划分的剩余属性编号% 当前node的⽗亲结点为node{m}function [node,child_value,child_node_num]=TreeNode( DValue, CN, A, ClassPNum,m) global node child_value child_node_num n=length(node); if m>0 %如果⽗亲结点存在，将本结点的序号存⼊⽗亲结点的⼦结点序号集中 k=length(child_node_num{m}); child_node_num{m}(k+1)=n+1;

end

% 1、样本为空，则树为空 if isempty(DValue) node{ n+1 }=[]; child_value{ n+1 }=[]; child_node_num{ n+1 }=[]; return; end

% 2、⽤于划分的剩余属性为空，选择多数元组所在的类作为结点 if isempty( ClassPNum )

node{ n+1 }=find_most( CN,A ); child_value{ n+1 }=[]; child_node_num{ n+1 }=[]; return; end

% 3、样本中所有数据都属于同⼀类，将此类作为结点 CNRowNum=CN_sta( CN, A); if length( find(CNRowNum==0) )>=2 node{ n+1 }=CN(A(1)); child_value{ n+1 }=[]; child_node_num{ n+1 }=[]; return; % 4、样本中所有数据不属于同⼀类 else I=Exp( CN,A ); for i=1:length( ClassPNum )

Entropy(i)=avg_entropy( DValue(:,ClassPNum(i)), A, CN); Gain(i)=I-Entropy(i); end % 4.1、各属性的信息增益均⼩于0，选择多数元组所在的类作为结点 if max(Gain)<=0 node{ n+1 }=find_most( CN,A ); child_value{ n+1 }=[]; child_node_num{ n+1 }=[]; return; % 4.2、在信息增益最⼤的属性上进⾏划分 else maxG=find( Gain==max(Gain) ); [PValue RowNum]=type_sta( DValue(:,ClassPNum(maxG(1))), A ); node{ n+1 }=ClassPNum(maxG(1)); child_value{ n+1 }=PValue; child_node_num{ n+1 }=[]; ClassPNum(maxG)=[]; % 删除ClassPNum(maxG)--已经进⾏划分的属性 for i=1:length(PValue) [node,child_value,child_node_num]=TreeNode( DValue, CN, RowNum{i}, ClassPNum,n+1 ); end return; end endend% A--参与划分的⾏号% DValue--数据集的前四列% 本函数⽤于统计参与划分的⾏⼤多数属于哪⼀个类function most_type=find_most( CN,A ) TypeName={'1','2','3'}; CNRowNum=CN_sta( CN, A); n=max(CNRowNum); maxn=find( CNRowNum==n ); most_type=TypeName{maxn};end% 计算属性P的熵% A--参与计算的⾏号，即计算的⾏范围% Attri--求属性Attri的熵% CN--类别属性值function entropy=avg_entropy( Attri, A, CN ) k=0;entropy=0; n=length(A); I=Exp( CN,A ); [PValue,RowNum]=type_sta( Attri, A ); for i=1:length( PValue ) CI=Exp( CN, RowNum{i}); entropy=entropy-length( RowNum{i} )/n*CI; endend% 计算样本分类的期望% A--参与计算的⾏号% Attri--求期望的属性值的集合function I=Exp(CN,A) CNRowNum=CN_sta( CN, A ); n=length(A); I=0; for i=1:3 if CNRowNum(i)>0 P(i)=CNRowNum(i)/n; I=I-P(i)*log2( P(i) ); end endend% 统计属性的取值及各取值对应的⾏号集合% A为参与统计的记录的⾏号集合% Attri为属性值的集合function [PValue,RowNum]=type_sta( Attri, A) k=1; PValue=Attri( A(1) ); RowNum{1}=A(1); for i=2:length(A) n1=find( PValue==Attri( A(i) ) ); if isempty(n1) k=k+1; PValue(k)=Attri( A(i) ); RowNum{k}=A(i); else n2=length( RowNum{n1} ); RowNum{n1}(n2+1)=A(i); end end

end% 统计类别属性的取值及各取值对应的⾏号集合% A为参与统计的记录的⾏号集合% CN为类别属性值的集合function CNRowNum=CN_sta( CN, A) CNRowNum=[0 0 0]; TypeName={'1','2'}; for i=1:length( A ) if strcmp( CN(A(i)),TypeName{1}) CNRowNum(1)=CNRowNum(1)+1; elseif strcmp( CN(A(i)),TypeName{2} ) CNRowNum(2)=CNRowNum(2)+1; else CNRowNum(3)=CNRowNum(3)+1; end end

endclear all;rnode=cell(3,1);%3*1的单元数组rchild_value=cell(3,1);%3*1的单元数组rchild_node_num=cell(3,1);%3*1的单元数组sn=600; %随机可重复的抽取sn个样本tn=10; %森林中决策树的棵树S=xlsread('');%% 样本训练采⽤随机森林和ID3算法构建决策森林 for j=1:tn Sample_num=randi([1,1000],1,sn);%从1⾄1000内随机抽取sn个样本 SData=S(Sample_num,:); [node,child_value,child_node_num]=ID3(SData); rnode{j,1}=node; rchild_value{j,1}=child_value; rchild_node_num{j,1}=child_node_num; end

%% 样本测试 T=xlsread(''); %TData=roundn(T,-1); TData=roundn(T,-1); len=length(TData(:,1));%测试样本的数⽬ type=zeros(len,1); for j=1:len %统计函数，对输⼊的测试向量进⾏投票，然后统计出选票最⾼的标签类型输出 [type(j)]=statistics(tn,rnode,rchild_value,rchild_node_num,TData(j,:)); end

xlswrite('',[T type]);%输出测试报告

function [type] = statistics(tn,rnode,rchild_value,rchild_node_num,PValue) TypeName={'1','2','3'}; TypeNum=[0 0 0];

for i=1:tn %对测试向量进⾏投票，共有tn棵树 [type]=vote(rnode,rchild_value,rchild_node_num,PValue,i); if strcmp( type,TypeName{1}) TypeNum(1) = TypeNum(1) + 1; elseif strcmp( type,TypeName{2}) TypeNum(2) = TypeNum(2) + 1; else TypeNum(3) = TypeNum(3) + 1; end end maxn=find( TypeNum==max(TypeNum) ); type=str2num(TypeName{maxn(1)});end

function [type] = vote(rnode,rchild_value,rchild_node_num,PValue,j) n=1; %从树的根结点（即node{1}）开始查找 k=0;

while ~isempty(rchild_node_num{j,1}{n})%不为空则进⼊循环 for i=1:length(rchild_value{j,1}{n}) if PValue(rnode{j,1}{n})==rchild_value{j,1}{n}(i) n=rchild_node_num{j,1}{n}(i); k=0; break; end

end

if i==length(rchild_value{j,1}{n}) % 若这个值在分类器中不存在，则取其最近的值进⾏分类 PValue(rnode{j,1}{n})=PValue(rnode{j,1}{n})+0.1*k; PValue=roundn(PValue,-1); end

k=(-1)^k*( abs(k)+1 );

end type=rnode{j,1}{n}; type=rnode{j,1}{n}; end