之前因为做过随机森林方面的项目，对随机森林有过研究，但理论这块还不是很深入，代码倒是看了不少，这里写下这篇博客，说说对随机森林的一些理解，以及附上了一份代码注释。
1. 随机森林
随机森林属于非传统式的机器学习算法，由多颗决策树组成，每棵决策树处理的是一个训练样本子集。训练阶段，通过决策树的节点分裂来筛选特征，层层对样本进行细分，直至将每个训练样本子集分类正确，测试阶段，直接基于训练出的特征进行样本分类，所以测试速度较快（但训练速度较慢）。属于“傻瓜式”的策略（这点和adaboost很像很像），以下部分是标准随机森林训练阶段的大致流程。
1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。 2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m << M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。 3. 决策树形成过程中每个节点都要按照步骤2来分裂，一直到不能够再分裂为止（就是收敛）。所谓不能再分裂，就是全部到达叶子节点，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点就是叶子节点。 4. 按照步骤1~3建立大量的决策树，便构成了随机森林。
从上面的步骤可以看出，随机森林的随机性体现在每颗数的训练样本是随机的，树中每个节点的分类属性也是随机选择的。有了这2个随机的保证，随机森林就不会产生过拟合的现象了。
给出一份某位朋友在论坛中提问的代码，关于文本分类的，刚好符合我上面描述的情况，我新添加了注释，与朋友们分享，里面肯定有很多问题，请不吝赐教啊！！！
2. 代码
</pre><pre name="code" class="cpp">#include <iostream>#include <fstream>#include <sstream>#include "random_forest.h"using namespace std;vector<decision_tree*> alltrees;// 森林（决策树集合）vector<TupleData>trainAll,train,test;// 样本集vector<int>attributes;// 属性集（元素为属性序号）inttrainAllNum = 0;inttestAllNum = 0;intMaxAttr;// 属性总数int*ArrtNum;// 属性个数集（元素为属性最大值）unsigned intF;inttree_num = 100;// 决策树个数const intleafattrnum = -1;// 叶子节点的属性序号intTP= 0,FN= 0,FP= 0,TN= 0,TestP= 0,TestN= 0;// 读入数据void init(char * trainname, char * testname){trainAllNum= readData(trainAll, trainname);testAllNum= readData(test, testname);calculate_attributes();double temp= (double)trainAllNum;temp= log(temp)/log(2.0);F= (unsigned int)floor(temp+0.5)+1;if(F>MaxAttr) F = MaxAttr;}// 初始化训练样本子集void sub_init(){// 选取决策树的训练样本集合RandomSelectData(trainAll, train);// 计算样本属性个数calculate_ArrtNum();}// 读数据int readData(vector<TupleData> &data, const char* fileName){ifstream fin;fin.open(fileName);string line;int datanum=0;// 每行数据作为一个样本while(getline(fin,line)){TupleData d;istringstream stream(line);string str;// 设置每个样本的标签和内容while(stream>>str){if(str.find('+')==0){d.label='+';}else if(str.find('-')==0){d.label='-';}else{int j=stringtoint(str);d.A.push_back(j);}}data.push_back(d);datanum++;}fin.close();return datanum;}// 生成根节点的训练样本子集void RandomSelectData(vector<TupleData> &data, vector<TupleData> &subdata){int index;subdata.clear();int d = 0;while (d < trainAllNum){index = rand() % trainAllNum;subdata.push_back(data.at(index));d++;}}// 计算属性序列void calculate_attributes(){// 每个样本必须具有相同的属性个数TupleData d = trainAll.at(0);MaxAttr = d.A.size();attributes.clear();// 建立属性集合attributes,元素为属性序号for (int i = 0; i < MaxAttr; i++){attributes.push_back(i);}// 初始化属性最大值序列，，元素为属性最大值ArrtNum = new int[MaxAttr];}// 字符串转化为intint stringtoint(string s){int sum=0;for(int i=0; s[i]!='\0';i++){int j=int(s[i])-48;sum=sum*10+j;}return sum;}// 计算ArrtNum元素值void calculate_ArrtNum(){for(int i = 0; i < MaxAttr; i++) ArrtNum[i] = 0;// ArrtNum元素值为属性最大值for (vector<TupleData>::const_iterator it = train.begin(); it != train.end(); it++){int i = 0;for (vector<int>::const_iterator intt=(*it).A.begin(); intt!=(*it).A.end();intt++){int valuemax=(*intt)+1;if(valuemax>ArrtNum[i]) ArrtNum[i]=valuemax;i++;}}}// 计算熵double Entropy(double p, double s){double n = s – p;double result = 0;if (n != 0)result += – double(n) / s * log(double(n) / s) / log(2.0);if (p != 0)result += double(-p) / s * log(double(p) / s) / log(2.0);return result;}// 训练一棵决策树int creat_classifier(decision_tree *&p, const vector<TupleData> &samples, vector<int> &attributes){if (p == NULL)p = new decision_tree();// 根据样本真实类别，输出叶子节点类别if (Allthesame(samples, '+')){p->node.label = '+';p->node.attrNum = leafattrnum;p->childs.clear();return 1;}if (Allthesame(samples, '-')){p->node.label = '-';p->node.attrNum = leafattrnum;p->childs.clear();return 1;}// 如果属性序列为空，当前节点就为叶子节点if (attributes.size() == 0){p->node.label = Majorityclass(samples);p->node.attrNum = leafattrnum;p->childs.clear();return 1;}// 计算当前节点的最优属性p->node.attrNum = BestGainArrt(samples, attributes);// 中间节点无标签p->node.label = ' ';// 计算子节点候选属性集合，候选集合元素越来越少vector<int> newAttributes;for (vector<int>::iterator it = attributes.begin(); it != attributes.end(); it++)if ((*it) != p->node.attrNum)newAttributes.push_back((*it));// 初始化样本子集，建立maxvalue个样本子集，也就说明该节点有maxvalue个子节点// 为什么不建立一个阈值，进行二分类？int maxvalue = ArrtNum[p->node.attrNum];vector<TupleData>* subSamples = new vector<TupleData>[maxvalue];for (int i = 0; i < maxvalue; i++)subSamples[i].clear();// 将样本集合分为样本子集for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++){// 对样本进行分类，分别分到maxvalue个子节点中// p->node.attrNum是当前节点的最优属性序号// (*it).A.at(p->node.attrNum)正是子节点的序号// 基于当前节点最优属性，计算当前样本的归类subSamples[(*it).A.at(p->node.attrNum)].push_back((*it));}decision_tree *child;for (int i = 0; i < maxvalue; i++){child = new decision_tree;if (subSamples[i].size() == 0)child->node.label = Majorityclass(samples);elsecreat_classifier(child, subSamples[i], newAttributes);p->childs.push_back(child);}delete[] subSamples;return 0;}// 计算节点处的信息增益int BestGainArrt(const vector<TupleData> &samples, vector<int> &attributes){int attr,bestAttr = 0,p = 0,s = (int)samples.size();// 计算正样本个数for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++){if ((*it).label == '+')p++;}double infoD;double bestResult = 0;// 计算初始熵infoD = Entropy(p, s);vector<int> m_attributes;// 随机确定候选属性集RandomSelectAttr(attributes, m_attributes);// 遍历属性（即主题），通过信息增益筛选最优属性for (vector<int>::iterator it = m_attributes.begin(); it != m_attributes.end(); it++){attr= (*it);double result = infoD;// 第attr个属性的最大属性值int maxvalue = ArrtNum[attr];// 正负样本集int* subN= new int[maxvalue];int* subP= new int[maxvalue];int* sub= new int[maxvalue];for (int i = 0; i < maxvalue; i++){subN[i] = 0;subP[i] = 0;sub[i] = 0;}// 基于特定属性，对当前训练样本进行分类// 属性计算这一步的确没有，属性值直接存储在样本中for (vector<TupleData>::const_iterator jt = samples.begin(); jt != samples.end(); jt++){if ((*jt).label == '+')subP[(*jt).A.at(attr)] ++;elsesubN[(*jt).A.at(attr)] ++;sub[(*jt).A.at(attr)]++;}// 计算特定属性下信息增益（相对熵）double SplitInfo = 0;for(int i = 0; i < maxvalue; i++){double partsplitinfo;partsplitinfo = -double(sub[i])/s*log(double(sub[i])/s)/log(2.0);SplitInfo= SplitInfo+partsplitinfo;}double infoattr = 0;for (int i = 0; i < maxvalue; i++){double partentropy;partentropy= Entropy(subP[i], subP[i] + subN[i]);infoattr= infoattr+((double)(subP[i] + subN[i])/(double)(s))*partentropy;}result = result – infoattr;result = result / SplitInfo;// 寻找最优属性if (result > bestResult){bestResult= result;bestAttr= attr;}delete[] subN;delete[] subP;delete[] sub;}if (bestResult == 0){bestAttr=attributes.at(0);}return bestAttr;}void RandomSelectAttr(vector<int> &data, vector<int> &subdata){int index;unsigned int dataNum=data.size();subdata.clear();if(dataNum<=F){for (vector<int>::iterator it = data.begin(); it != data.end(); it++){int attr = (*it);subdata.push_back(attr);}}else{set<int> AttrSet;AttrSet.clear();while (AttrSet.size() < F){index = rand() % dataNum;if (AttrSet.count(index) == 0){AttrSet.insert(index);subdata.push_back(data.at(index));}}}}bool Allthesame(const vector<TupleData> &samples, char ch){for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++)if ((*it).label != ch)return false;return true;}// 确定节点中哪个类别样本个数最多char Majorityclass(const vector<TupleData> &samples){int p = 0, n = 0;for (vector<TupleData>::const_iterator it = samples.begin(); it != samples.end(); it++)if ((*it).label == '+')p++;elsen++;if (p >= n)return '+';elsereturn '-';}// 测试阶段char testClassifier(decision_tree *p, TupleData d){// 抵达叶子节点if (p->node.label != ' ')return p->node.label;// 节点处最优属性int attrNum = p->node.attrNum;// 错误样本if (d.A.at(attrNum) < 0)return ' ';// 确定分支return testClassifier(p->childs.at(d.A.at(attrNum)), d);}void testData(){for (vector<TupleData>::iterator it = test.begin(); it != test.end(); it++){printf("新样本\n");if((*it).label=='+') TestP++;else TestN++;int p = 0, n = 0;for(int i = 0; i < tree_num; i++){if(testClassifier(alltrees.at(i), (*it))=='+') p++;else n++;}if(p>n){if((*it).label=='+') TP++;else FP++;}else{if((*it).label=='+') FN++;else TN++;}}}void freeClassifier(decision_tree *p){if (p == NULL)return;for (vector<decision_tree*>::iterator it = p->childs.begin(); it != p->childs.end(); it++){freeClassifier(*it);}delete p;}void freeArrtNum(){delete[] ArrtNum;}void showResult(){cout << "Train size:"<< trainAllNum<<endl;cout << "Test size:"<<testAllNum<<endl;cout << "True positive:" << TP << endl;cout << "False negative:"<< FN<<endl;cout << "False positive:"<<FP<<endl;cout << "True negative:"<<TN<<endl;}int main(int argc, char **argv){char * trainfile=argv[1];char * testfile=argv[2];srand((unsigned)time(NULL));// 初始化样本init("1.txt", "2.txt");// 训练阶段for(int i = 0; i < tree_num; i++){printf("第 %d 棵决策树训练开始\n", i);// 每棵树的训练样本子集sub_init();// 训练每棵决策树decision_tree * root=NULL;creat_classifier(root, train, attributes);// 建立森林alltrees.push_back(root);printf("第 %d 棵决策树训练完毕\n", i);}// 测试阶段testData();for (vector<decision_tree *>::const_iterator it = alltrees.begin(); it != alltrees.end(); it++){freeClassifier((*it));}freeArrtNum();showResult();system("pause");return 0;}3. 总结谁也不跟谁一辈子，有些事情没必要记在心上。
