基于C++实现Adaboost分类算法（附带决策树分类算法作为演示工具）

这里的代码为本人学习过程中的一些练习，并且本人还在不断的学习中，如果读者有更好的想法，欢迎评论区留言或私信本人，笔者一定洗耳恭听。除此之外，如果代码注释有不明确的地方，也欢迎评论区留言或私信本人，如果笔者看到，就会修改或增加注释，方便广大读者。
除此之外，这份代码默认存在下面这条语句，望读者注意

using namespace std;

这个代码的算法使用了经典的算法，其思想十分具有价值，我将它转化为C++语言，便于编程者更好理解。

除此之外，虽然算法并非我创造的，但我自己还是有一丁点微不足道的思考的，我的思考主要在这个方向：用C++的数据类型以及一些标准库将原本的数据映射为可以用C++编程的数据，还有一些对代码的设计，这些东西相比于算法本身，虽然微不足道，但如果能帮助到读者有所进步，万分荣幸。

这份代码附带了决策树分类算法作为weak_type（弱分类器），但如果你想使用其他算法作为weak_type，算法需要具有如下共有方法：

weak_type(vector sample_set, vector lable,vector attr_size, int k, vector power);

参数意义如下
（1）sample_set：样本矩阵（m行n列，m个属性，n个样本，每一个样本算作一个向量，简单来说，sample_set.size() == n），在笔者的代码中，所有属性都是被当作整数处理的，这里使用了数字 “不同” 的特征，如：身高有三类：高、中、低，那么就可以用 0、1、2 表示它们
（2）lable：标签向量，大小为n，样本sample_set[i]的标签是lable[i]
（3）attr_size：属性的种类数量，如：第 i 类属性：身高有三类：高、中、低，那么，attr_size[i] = 3
（4） k ：这个参数的意义在于，控制弱分类器的精度，也就是有多 “弱” ，比如决策树的层数
（5）power：每个样本的权重
*（6）这个特别重要！！！：同时需要在构造函数里完成对分类器的训练（可以调用内部方法，也可以直接在构造函数中实现，但要求构造完成后，对象有一个可以用的分类器）

这个方法的作用是：用训练好的分类器对样本进行分类

int Test(vector sample);

参数 sample：用于测试的样本
返回分类器判断的类别

这个方法的作用是：返回用sample_set训练分类器中，分类错误的所有样本在sample_set中的下标

vector get_error();

注意：如果不拷贝决策树算法，请删除模板参数中weak_type的缺省值，同时删除对相关头文件的引入

#pragma once
#include
#include"Decision_Tree.hpp"
namespace wx {
	//模板参数：weak_type弱分类器，N代表是N分类模型
	template>
	class AdaBoost {
	public:
		//构造函数
		//样本集合sample，标签lable，每种属性的种类数量，以及相关参数k（弱分类器的迭代次数或精度，换言之：弱分类器究竟有多弱？）,e强分类器最终的误差允许
		AdaBoost(vector>& sample, vector& lable, vector& attr_size, int k, double e)
			:_sample(sample), _lable(lable), _attr_size(attr_size), _k(k), _e(e)
		{
			m = attr_size.size();
			n = lable.size();
			_k = _k > m ? (m+1) : _k;
			Train();
		}
		//接下来开始训练
		void Train() {
			//1、初始化权值
			vector _power(n, 1.0 / (double)n);
			while (1) {
				//创建this_time_error
				vector this_time_error;
				//2
				//(a)创造一个弱分类器，由于底层设计，创建即训练
				weak_type Gm(_sample, _lable, _attr_size, _k, _power);
				//(b)计算Gm的分类误差率
				double em = 0.0;
				for (auto& e : Gm.get_error()) {
					em += _power[e];
				}
				//(c)计算Gm的系数
				double am = 0.5 * log2((1 - em) / em);
				//(d)更新训练数据集的权值分布
				//先求出泛化因子
				double Zm = 0.0;
				//空间换时间，提升效率
				vector Gmxi(n, 0);
				for (int i = 0; i < n; ++i) {
					Gmxi[i] = Gm.Test(_sample[i]);
					double yi = 0;//定义符号函数yi
					if (_lable[i] == Gmxi[i]) {
						yi = 1.0;//分类正确
					}
					else {
						yi = -1.0;
					}
					Zm += _power[i] * exp(-am * yi);
				}
				vector D(n, 0.0);
				for (int i = 0; i < n; ++i) {
					double yi = 0;//定义符号函数yi
					if (_lable[i] == Gmxi[i]) {
						yi = 1.0;
					}
					else {
						yi = -1.0;
					}
					D[i] = _power[i] / Zm * exp(-am * yi);
				}
				//更新权值
				_power = D;
				_weak_power.push_back(am);
				//3，把Gm加入强分类器中，试试效果，并得到误分类率，判断循环是否退出
				_strong_algorithm.push_back(Gm);
				for (int i = 0; i < n; ++i) {
					int t = Test(_sample[i]);
					if (t == _lable[i]) {
						//分类正确，可以走了
					}
					else {
						//加入错误列表
						this_time_error.push_back(i);
					}
				}
				double e = ((double)this_time_error.size() / (double)n);
				if (e <= _e) {
					//创建error_list并退出
					error_list = this_time_error;
					break;
				}
			}
		}
		//对给定数据进行分类
		int Test(vector t) {
			if (t.size() != m) {
				throw m;
			}
			//每一个弱分类器都进行分类并投票
			vector results(m, 0.0);
			for (int i = 0; i < _strong_algorithm.size(); ++i) {
				results[_strong_algorithm[i].Test(t)] += _weak_power[i];
			}
			//最终选择投票最多的选项
			int result = 0;
			double mm = results[0];
			for (int i = 0; i < m; ++i) {
				if (mm < results[i]) {
					result = i;
					mm = results[i];
				}
			}
			return result;
		}
	private:
		vector _strong_algorithm;//最终的强分类器
		vector _weak_power;//强分类器中，各个弱分类器的权重
		vector> _sample;//样本矩阵
		vector _lable;//样本标签向量
		vector _attr_size;//属性种类数量
		int _k = 0;//k次截止
		double _e = 0;//误差小于e截止
		int m; //属性数量
		int n; //样本数量
		vector error_list;	//错误列表
	};
}

#pragma once
#include
#include
#include
#include
namespace wx {
	using namespace std;

	//结点类
	struct Tree_node {
		unordered_map attr;//这个结点的第i个属性所属的类别
		int this_attr;//这个结点确定分类的属性，如果是叶子结点，则确定最后的类型
		vector data;//这个结点剩余的样本序号
		vector child;//子结点指针，下标即代表种类
		Tree_node* parent;//父结点指针
		double entropy = 0;//该结点信息增益(比)
		vector error_list;//错误列表
		//构造函数给上
		Tree_node() {}
		//给一个确定叶子结点的方法
		bool is_leaf() {
			return child.size() == 0;
		}
	};

	//模板声明：type_size：标签种类数量,handler_t：算法选择，可选ID3、C4_5
	template
	class Decision_Tree {
	public:
		//生成决策树，参数：
		// 样本矩阵（m行n列，m个属性，n个样本，每一个样本算作一个向量，vector> sample）
		// 标签向量（vector lable，lable.size() == n，每个样本有一个）
		// 各个属性的种类数量向量（vector attr_size, attr_size.size() == m，每个属性有一个）
		// 精度：double e/决策树高度：int k
		// 样本权重向量（缺省为 1 向量）：vector power，power.size() == n
		//
		Decision_Tree(vector>& sample, vector& lable, vector& attr_size, int k, vector power)
			:_sample(sample), _lable(lable), _attr_size(attr_size), _k(k), _kore(0)
		{
			m = attr_size.size();
			n = lable.size();
			_power = power;
			_k = _k > m ? m : _k;
			Train();
		}
		Decision_Tree(vector>& sample, vector& lable, vector& attr_size, double e, vector power)
			:_sample(sample), _lable(lable), _attr_size(attr_size), _e(e), _kore(1)
		{
			m = attr_size.size();
			n = lable.size();
			_power = power;
			_k = m;
			Train();
		}
		//修改k
		bool re_k(int k) {
			_k = k;		//修改k的值
			_kore = 0;	//修改为k作用
			return true;
		}
		//修改e
		bool re_e(double e) {
			_e = e;
			_kore = 1;//同理
			return true;
		}
		//修改权重向量
		bool re_power(vector& power) {
			if (power.size() == n) {
				_power = power;
				return true;
			}
			return false;
		}
		//训练树
		void Train() {
			//获取每一个属性的信息量，选择最大的作为根结点
			root = new Tree_node;
			vector root_data(n);//毫无疑问root拥有所有数据
			for (int i = 0; i < n; ++i) {
				root_data[i] = i;
			}
			unordered_map mp;//根结点不具备任何属性
			vector used(m, 0);//已经使用过的属性
			_train(*root, nullptr, root_data, mp, _k - 1, used);

		}
		//对给定数据进行分类
		int Test(vector t) {
			//要求是一个维度相同的样本
			if (t.size() != m) {
				throw m;
			}
			Tree_node* ptr = root;
			while (!(ptr->is_leaf())) {
				ptr = ptr->child[t[ptr->this_attr]];
			}
			return ptr->this_attr;
		}
		vector get_error() {
			return error_list;
		}
	private:
		void _train(Tree_node& node, Tree_node* pr, vector& node_data, unordered_map attr, int k, vector used) {
			//对结点初始化
			node.parent = pr;//根结点父结点是null
			node.data = node_data;//该结点具有的数据
			node.attr = attr;//当前结点具有的属性
			//递归结束条件
			if (_kore) {
				//这里是e
				if (pr->entropy < _e) {
					vector tmp(type_size, 0);//tmp的下标是标签，数据是这个标签的数量，取最多的作为类型
					for (auto& i : node_data) {
						tmp[_lable[i]] += _power[i];
					}
					int t = 0;
					double mm = tmp[0];
					for (int i = 1; i < type_size; ++i) {
						if (mm < tmp[i]) {
							mm = tmp[i];
							t = i;
						}
					}
					node.this_attr = t;//确定最后的类型
					node.entropy = 0.0;//由于叶子结点不进行分类，所以收益为0；
					//构造error_list
					for (auto& e : node_data) {
						if (_lable[e] != node.this_attr) {
							node.error_list.push_back(e);
							error_list.push_back(e);
						}
					}
					return;
				}
			}
			//这里是k(剩余的可使用属性个数)
			if (k == 0) {
				vector tmp(type_size, 0);
				for (auto& i : node_data) {
					tmp[_lable[i]] += _power[i];
				}
				int t = 0;
				double mm = tmp[0];
				for (int i = 1; i < type_size; ++i) {
					if (mm < tmp[i]) {
						mm = tmp[i];
						t = i;
					}
				}
				node.this_attr = t;
				//构造error_list
				for (auto& e : node_data) {
					if (_lable[e] != node.this_attr) {
						node.error_list.push_back(e);
						error_list.push_back(e);
					}
				}
				return;
			}
			//除此之外，分类完成也可以作为退出递归的条件
			int E = node_data[0];
			for (auto& i : node_data) {
				if (_lable[i] != _lable[E]) {
					break;
				}
				if (i == node_data[node_data.size() - 1]) {
					//证明所有的标签都相等
					node.this_attr = _lable[E];
					node.entropy = 0;
					return;
				}
			}

			//走到这里说明没有结束，还得继续分
			//计算每一个种类的熵，选择最大的
			double mm = 0.0;//无论如何，信息增益不可能小于0吧
			int sub = -1;//最大者的下标
			for (int i = 0; i < m; ++i) {
				//首先要明确的一点，不能用之前用过的属性
				if (used[i] == 1)
					continue;
				double tmp = func(_sample, _lable, type_size, i, node_data, _attr_size[i], _power);
				if (tmp > mm) {
					sub = i;
					mm = tmp;
				}
			}
			//确定当前结点的决策属性
			node.entropy = mm;
			node.this_attr = sub;
			//已经使用过sub属性了，所以它的子结点就不能用了
			used[sub] = 1;
			//当前结点的子结点指针，完成递归
			for (int i = 0; i < _attr_size[sub]; ++i) {
				Tree_node* child = new Tree_node;
				//确定下一代结点具有的属性
				unordered_map child_attr = attr;//在其他属性上，子结点有着跟父结点相同的属性
				child_attr[sub] = i;//在当前结点确定的属性上，子结点的属性应当每个属性都有
				//下一代结点具有的样本
				vector child_data;
				for (auto& e : node_data) {
					if (_sample[e][sub] == i) {
						child_data.push_back(e);
					}
				}
				//加入到当前结点的子指针列表
				node.child.push_back(child);
				_train(*child, &node, child_data, child_attr, k - 1, used);
			}
			if (node.is_leaf()) {
				node.entropy = 0.0;
				//构造error_list
				for (auto& e : node_data) {
					if (_lable[e] != node.this_attr) {
						node.error_list.push_back(e);
						error_list.push_back(e);
					}
				}
			}
		}
		vector> _sample;//样本矩阵
		vector _lable;//样本标签向量
		vector _attr_size;//属性种类数量
		vector _power;//样本权重向量
		int _k = 0;//k层截止
		double _e = 0;//func(特征i)小于e截止
		int _kore = 0;//0代表用k，1代表用e
		function_t func;//算法：比较熵的仿函数
		int m; //属性数量
		int n; //样本数量
		Tree_node* root = nullptr;//根结点
		vector error_list;	//错误列表
	};



	class ID3 {
	public:
		//数据集中，第i个属性的信息增益，其中，H(D)是上一层的经验熵，node_data表示本层的剩余结点下标，这里的attr_size仅表示第i个属性的种类数目
		double operator()(vector>& sample, vector& lable, int type_size, int i, vector& node_data, int attr_size, vector power) {
			//计算HD
			double HD = 0;
			vector tmp(type_size);//标签数量的空间
			for (auto& e : node_data) {
				tmp[lable[e]] += power[e];
			}
			//计算D的大小
			double D_count = 0.0;
			for (auto& e : power) {
				D_count += e;
			}
			for (auto& e : tmp) {
				if(e != 0)
					HD += -(e / D_count * log2(e / D_count));
			}
			//计算HDA
			vector> count(attr_size);
			for (auto& e : node_data) {
				count[sample[e][i]].push_back(e);//第e个变量的第i个属性的类别，存放这个变量的下标
			}
			//计算特征 i 对应集合 node_data 的经验条件熵，然后求和
			double HDA = 0;
			for (auto& Di : count) {
				double sum = 0;
				if (Di.size() == 0) {
					continue;//如果该种类没有数据，跳过即可
				}
				//求出每个标签的样本数量
				unordered_map mp;
				double Di_count = 0.0;
				for (auto& Dik : Di) {
					mp[lable[Dik]] += power[Dik];
					Di_count += power[Dik];
				}
				//求和
				for (auto& k : mp) {
					if (k.second != 0) 
						sum += (k.second / Di_count * log2(k.second / Di_count));
				}
				//汇总到 HDA 里面
				HDA += -(Di_count / D_count * sum);
			}
			return HD - HDA;//返回信息增益
		}
	};

	class C4_5 {
	public:
		double operator()(vector>& sample, vector& lable, int type_size, int i, vector& node_data, int attr_size, vector power) {
			ID3 f;
			//定义信息增益gR(DA)
			double gRDA = f(sample, lable, type_size, i, node_data, attr_size, power);
			//定义sample关于属性i的熵HA(D)
			double HAD = 0.0;
			vector Di_count(attr_size, 0.0);
			double D_count = 0.0;
			for (auto& e : node_data) {
				Di_count[sample[e][i]] += power[e];
				D_count += power[e];
			}
			for (auto& e : Di_count) {
				if (e != 0)
					HAD += -(e / D_count * log2(e / D_count));
			}
			//返回信息增益率
			return gRDA / HAD;
		}
	};
}

#include
#include"Adaboost.hpp"
#include"Decision_Tree.hpp"
using namespace wx;


int main() {
	//先检验以下决策树
	//数据集合，0代表不合格，1代表合格
	vector> sample{ {0,0,2},{0,2,0},{1,1,1},{1,0,2},{1,1,2}
		, { 0,0,1 }, { 1,0,1 }, { 1,0,0 }, { 1,2,0 }, { 0,1,0 } };
	//数据标签
	vector lable{ 0,0,0,0,0,0,1,1,0,0 };
	//每一个属性的种类数量
	vector attr_size{ 2,3,3 };
	vector power(sample.size(), 1);
	Decision_Tree<2, C4_5> tree(sample, lable, attr_size, 4, power);
	AdaBoost<2> t(sample, lable, attr_size, 2, 0);
	return 0;
}