这里的代码为本人学习过程中的一些练习，并且本人还在不断的学习中，如果读者有更好的想法，欢迎评论区留言或私信本人，笔者一定洗耳恭听。除此之外，如果代码注释有不明确的地方，也欢迎评论区留言或私信本人，如果笔者看到，就会修改或增加注释，方便广大读者。
除此之外，这份代码默认存在下面这条语句，望读者注意
using namespace std;
这个代码的算法使用了经典的算法，其思想十分具有价值，我将它转化为C++语言，便于编程者更好理解。
2、我做了什么除此之外，虽然算法并非我创造的，但我自己还是有一丁点微不足道的思考的，我的思考主要在这个方向：用C++的数据类型以及一些标准库将原本的数据映射为可以用C++编程的数据，还有一些对代码的设计，这些东西相比于算法本身，虽然微不足道，但如果能帮助到读者有所进步，万分荣幸。
如果你是为了使用这份代码这份代码附带了决策树分类算法作为weak_type（弱分类器），但如果你想使用其他算法作为weak_type，算法需要具有如下共有方法：
1、具有如下参数的构造方法weak_type(vector<vector> sample_set, vector<int> lable,vector<int> attr_size, int k, vector<double> 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<int> sample);
参数 sample：用于测试的样本
返回分类器判断的类别
这个方法的作用是：返回用sample_set训练分类器中，分类错误的所有样本在sample_set中的下标
vector<int> get_error();
注意：如果不拷贝决策树算法，请删除模板参数中weak_type的缺省值，同时删除对相关头文件的引入
#pragma once
#include#pragma once
#include> 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<vector<int>>& sample, vector<int>& lable, vector<int>& attr_size, int k, vector<double> 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<vector<int>>& sample, vector<int>& lable, vector<int>& attr_size, double e, vector<double> 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<int>& power) {
if (power.size() == n) {
_power = power;
return true;
}
return false;
}
//训练树
void Train() {
//获取每一个属性的信息量，选择最大的作为根结点
root = new Tree_node;
vector<int> root_data(n);//毫无疑问root拥有所有数据
for (int i = 0; i < n; ++i) {
root_data[i] = i;
}
unordered_map<int, int> mp;//根结点不具备任何属性
vector<int> used(m, 0);//已经使用过的属性
_train(*root, nullptr, root_data, mp, _k - 1, used);
}
//对给定数据进行分类
int Test(vector<int> 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<int> get_error() {
return error_list;
}
private:
void _train(Tree_node& node, Tree_node* pr, vector<int>& node_data, unordered_map<int, int> attr, int k, vector<int> used) {
//对结点初始化
node.parent = pr;//根结点父结点是null
node.data = node_data;//该结点具有的数据
node.attr = attr;//当前结点具有的属性
//递归结束条件
if (_kore) {
//这里是e
if (pr->entropy < _e) {
vector<double> 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<double> 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<int, int> child_attr = attr;//在其他属性上，子结点有着跟父结点相同的属性
child_attr[sub] = i;//在当前结点确定的属性上，子结点的属性应当每个属性都有
//下一代结点具有的样本
vector<int> 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<vector<int>> _sample;//样本矩阵
vector<int> _lable;//样本标签向量
vector<int> _attr_size;//属性种类数量
vector<double> _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<int> error_list; //错误列表
};
class ID3 {
public:
//数据集中，第i个属性的信息增益，其中，H(D)是上一层的经验熵，node_data表示本层的剩余结点下标，这里的attr_size仅表示第i个属性的种类数目
double operator()(vector<vector<int>>& sample, vector<int>& lable, int type_size, int i, vector<int>& node_data, int attr_size, vector<double> power) {
//计算HD
double HD = 0;
vector<double> 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<vector<int>> 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<int, double> 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<vector<int>>& sample, vector<int>& lable, int type_size, int i, vector<int>& node_data, int attr_size, vector<double> 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<double> 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欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）