[C++ AdaBoost] 傻陈带你用C++实现AdaBoost

前言

人工智能的算法需要许多预备知识，但时间比较紧，所以我只会对"对最后算法实现有帮助的资料"感兴趣，试着在不完全了解的情况下将这次实验完成。

数据集

这次要学习的数据集是UCI上的Polish companies bankruptcy data Data Set
数据集就是一堆数据的集合，而这次实验就是要对这个“破产公司”数据集进行分类。
这个数据集包含了5个.arff格式的文件，分别对应五年的数据。
我借鉴《Matlab读取.arff文件》的教程，用Excel查看了里面的内容，一个文件大概有七千条公司的记录，每条记录都有65个属性。其中前64个属性是实数格式，个别可能出现’?’，应该是‘不清楚’的意思；最后一个属性是0或1，代表了这条记录的类别（我猜测是破产/不破产）。
我要做的就是，用这些记录的属性和类别去给算法学习，达到能只凭属性来预测类别的程度。

AdaBoost

机器学习实战教程（十）：提升分类器性能利器-AdaBoost
网上有大把的参考资料还算庆幸，这里举了个例子。当然要短时间完全理解还是天方夜谭的。

思路

AdaBoost大致是靠调整弱分类器的权重来运作的。
弱分类器可以暂时理解为对某个属性设置一个阈值，如果达到阈值就直接归为类1，未达到就归为类0。
一开始Adaboost导入作为训练数据的记录，根据一个弱分类器来分类所有的记录。然后对比判断结果与每条记录的实际类别的差距，来纠正这个弱分类器的权重和各个记录的权重，最后就智能的学习出了由多个带权重的弱分类器合并的强分类器，同时也可以通过记录的权重来排除不必要的训练记录。

设计

• 训练模式
  • 导入训练数据
  • 对训练数据定权重D={k,k,k,…,k,k}，暂时先不知道k为多少合适，总之全员相等。
  • 加载训练数据，使用弱分类器来预测分类，最后选定误差最小的一个弱分类器开始训练
  • 给分错的数据和分对的数据分别调整数据的权重
  • 对比预测和实际，然后通过某种方式来设定分类器权重α。
  • 将带权重的弱分类器加入到强分类器中，得出强分类器的当前指标。
  • 循环迭代进行下一次训练。

难点

1.如何将.arff里的内容输入到C++程序呢？
2.k应该是多少呢？
3.如何建立初始的弱分类器？
4.某种方式是什么呢？
这些纯属代码之外的知识盲区，还是优先解决的好。

Solve 1

在前面我已经成功的用Excel查看了里面的内容，如果用记事本打开的话，数据部分其实就是用逗号分隔的记录们。
.arff文件是无法识别的，但我可以单纯的将数据部分作为新的输入文件，然后以逗号分割整个文件，得到的集合就都是数字为元素的，再以每65个为一条记录即可。

Solve 2

初始权重在AdaBoost的教程中其实已经规定，为w=1/N，作为第一次迭代时各个记录的权重。可以说非常标准了。

Solve 3

虽然AdaBoost有加强分类器的能力，但是尽量还是让弱分类器本身的误差率最小比较好。所以在AdaBoost之前，弱分类器也是要训练出来的。
因为弱分类器本身是很简单的，类似
$$H_1=\{\begin{array}{c}1,X_{35}>9.8\\ ?1,X_{35}\le 9.8\end{array}$$表示若记录的第35个属性>9.8，那么就取1，反之就取-1。
分类预测时，就看分类器的结果是正还是负，正为类1，负为类0。
所以误差率就是分错的记录占总记录数的比例。
因此很容易想到，只要在某个属性的数据范围内，遍历各种可能的阈值和方向（大还是小），取其中误差最小的即可。
例如：数据分布在-10~90之间，我可以以10为步长遍历，也就是从-10,0, … ,80,90中挑出一个分类结果最准确的阈值即可。

Solve 4

Solve 4是Adaboost的核心计算部分，先要从原理上了解才能写出相应的代码。
Adaboost算法原理分析和实例+代码（简明易懂）
1.选取一个误差率最小的弱分类器H，对所有数据分类，计算当前弱分类器的误差度。
误差度ε等于分错的样本的权值之和。
2.计算该弱分类器的权重
$$\alpha =\frac{1}{2}ln(\frac{1?\epsilon }{\epsilon })$$
3.计算分对记录和分错记录的权重
当记录被分对时，该记录新权重为：
$$D_{new}=\frac{D_{old}}{2(1?\epsilon )}$$
当记录被分错时，该记录新权重为：
$$D_{new}=\frac{D_{old}}{2\epsilon }$$

编程

因为想以实现预期效果为目标，所以运行效率和最终结果会有点不尽人意。

输入输出环境配置

数据集是以文件的形式存在的，想到输入输出都走文件渠道

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;#define LOCALint main()
{
    
#ifdef LOCAL freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endif return 0;
}

代码说明
1.若Visual Studio出现报错"freopen:This function…"，那么就在解决方案资源管理器里，右键项目名>属性>C/C++>常规>SDL检查>“是"改成"否”。
2.这段代码会使程序以input.txt作为标准输入流，然后输出会在output.txt中显示

输入数据集

?//训练集记录的结构体
struct Record
{
    bool hasValue[64];//64个属性是否存在double attr[64];//64个属性的值double weight;//记录的权重int type;//类别，0或1
};vector<Record> recs;//训练集//功能：遍历字符串str,将里面的','替换为空格
void replaceComma(string& str)
{
    for (int i = 0; i < str.length(); i++){
    if (str[i] == ',') str[i] = ' ';}
}//功能：输入训练集文件，将训练集的数据保存在recs之中
void inputRecords()
{
    Record tempRec;string line;while (!cin.eof()){
    //一行作为一条完整记录getline(cin, line);if (line == "") break;replaceComma(line);stringstream ss(line);//一行的字符串作为输入流for (int i = 0; i < 64; i++){
    //排除值为'?'的属性string tempStr;ss >> tempStr;if (tempStr != "?"){
    tempRec.hasValue[i] = true;//把string类型转化为double类型stringstream tempSS(tempStr);tempSS >> tempRec.attr[i];}elsetempRec.hasValue[i] = false;}ss >> tempRec.type;//记录的最后一个数字代表类别//记录+1recs.push_back(tempRec);}//给所有记录赋初始权重double numOfRecords = recs.size();for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    (*it).weight = 1.0 / numOfRecords;}
}

代码说明
1.vector<Record>是声明一个Record结构体的动态数组，与之配套的是迭代器vector<Record>::iterator，用来指向动态数组中的元素。
recs.size():表示动态数组的大小，也就是训练集的记录个数。
recs.push_back(Record):将一个Record结构体插入到数组的最后（自动开辟空间）。
recs.begin()->recs.end():迭代器从开始到结束，就相当于遍历了整个recs。
(*it):迭代器所指向的Record结构体元素。
2.字符串流stringstream能将一个字符串转变成同样内容的一段输入，这样做的好处是能先提取单行的一整条记录，然后以空格为分隔符，将一个个属性值直接输入到recs.attr中。

初始弱分类器

?//弱分类器的结构体
struct WeakClassfier
{
    int attrIdx;//哪个属性上的弱分类器double cap;//阈值大小bool isHigher;//方向double weight;//分类器权重WeakClassfier(int a, double c, bool h, double w){
    attrIdx = a;cap = c;isHigher = h;weight = w;}
};vector<WeakClassfier> weaks;//弱分类器们
?
//功能：在属性attrIdx(0~63)上训练一个弱分类器
void trainWeakClassifier(int attrIdx)
{
    //在所有记录的该属性上找到最大值和最小值，并且统计有效值的个数double Max = -9999;double Min = 9999;int nums = 0;for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    if ((*it).hasValue[attrIdx] == true){
    double currentValue = (*it).attr[attrIdx];nums++;if (currentValue> Max){
    Max = currentValue;}else if (currentValue < Min){
    Min = currentValue;}}}//确定合适的步长double step = (Max-Min)/10.0;//寻找准确率最大的阈值和方向double bestCap = -9999;double bestAcc = 0;bool isHigherBetter = true;for (double cap = Min + step; cap < Max; cap += step){
    //用于计算准确率的变量int correctHigher = 0;int correctLower = 0;//统计分类准确率for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    Record currentRecord = (*it);//Higher: a>=cap 为 类1//Lower: a<cap 为 类1if ((*it).attr[attrIdx] >= cap){
    correctHigher += currentRecord.type == 1 ? 1 : 0;correctLower += currentRecord.type == 0 ? 1 : 0;}else{
    correctHigher += currentRecord.type == 0 ? 1 : 0;correctLower += currentRecord.type == 1 ? 1 : 0;}}//是否比当前的弱分类器准确率更高if (correctHigher >= correctLower){
    double tempAcc = correctHigher*1.0 / nums;if (tempAcc > bestAcc){
    bestCap = cap;bestAcc = tempAcc;isHigherBetter = true;}}else{
    double tempAcc = correctLower*1.0 / nums;if (tempAcc > bestAcc){
    bestCap = cap;bestAcc = tempAcc;isHigherBetter = false;}}}weaks.push_back(WeakClassfier(attrIdx, bestCap, isHigherBetter, 1.0));
}

代码说明
1.9999的取值非常随意，请不要模仿。
2.这样训练出的分类器相当于如下函数：
$$if\left(H.isHigher==true\right),H=\{\begin{array}{c}1,attr[attrIdx]>=cap\\ ?1,attr[attrIdx]<cap\end{array}$$
$$if\left(H.isHigher==false\right),H=\{\begin{array}{c}1,attr[attrIdx]<cap\\ ?1,attr[attrIdx]>=cap\end{array}$$3.因为这里只平均取了10个阈值，所以对于数据分布范围广又在中间密集的属性，比如-80万~400万的42号属性，这个分类器容易表现不佳。

选择最好弱分类器

?//功能：弱分类器函数H，可以将传入的分类器和属性值进行计算
int funH(int weakIdx, double attrVal)
{
    WeakClassfier weak = weaks[weakIdx];if (weak.isHigher){
    if (attrVal >= weak.cap) return 1;else return -1;}else{
    if (attrVal < weak.cap) return 1;else return -1;}
}//功能：符号判别函数
int sign(double a)
{
    if (a >= 0) return 1;else return 0;
}//功能：取误差率最小的一个分类器（编号）
int getBestWeakClassfier()
{
    //初始化for (vector<WeakClassfier>::iterator wit = weaks.begin(); wit != weaks.end(); wit++){
    (*wit).errorRate = 0;}//遍历所有记录和弱分类器for (vector<Record>::iterator rit = recs.begin(); rit != recs.end(); rit++){
    Record rec = (*rit);double recWeight = (*rit).weight;for (vector<WeakClassfier>::iterator wit = weaks.begin(); wit != weaks.end(); wit++){
    int attrIdx = (*wit).attrIdx;if (!rec.hasValue[attrIdx])//若记录rec的attrIdx属性值是'?',就认定分类错误{
    (*wit).errorRate += recWeight;}else{
    if (sign(funH((*wit).attrIdx, rec.attr[attrIdx])) != rec.type){
    (*wit).errorRate += recWeight;}}}}//找出误差率errorRate最小的分类器返回int bestIdx = 0;double minErrorRate = 2;for (vector<WeakClassfier>::iterator wit = weaks.begin(); wit != weaks.end(); wit++){
    if ((*wit).errorRate < minErrorRate){
    minErrorRate = (*wit).errorRate;bestIdx = (*wit).attrIdx;}}return bestIdx;
}

代码说明
1.按照之前的算法，误差率可以通过把分错样本的权重相加得到。

调整分类器权重

//2.调整该分类器的权重weak.weight = 0.5*log((1 - weak.errorRate) / weak.errorRate);

代码说明
1.log(x)相当于ln(x)，即C++中默认为自然对数。

调整记录权重

?//功能：用该分类器再次进行分类，来调整记录的权重
void adjustRecordWeight(int attrIdx)
{
    WeakClassfier weak = weaks[attrIdx];for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    if (!(*it).hasValue[attrIdx])//若记录rec的attrIdx属性值是'?',就认定分类错误{
    (*it).weight /= 2 * weak.errorRate;}else{
    if (sign(funH(attrIdx, (*it).attr[attrIdx])) != (*it).type)//分错{
    (*it).weight /= 2 * weak.errorRate;}else//分对{
    (*it).weight /= 2 * (1 - weak.errorRate);}}}
}

重新定义强分类器

vector<WeakClassfier> strong;//一个强分类器{
    
//4.强分类器并入此弱分类器
strong.push_back(WeakClassfier(weak));
}

代码说明
1.强分类器是将各个带权重的弱分类器相加所得，所以用一个可以保存多个弱分类器结构体的数组来表示强分类器。最后计算时，依次调用其中的弱分类器即可。

强分类器分类指标

?//功能：用强分类器进行分类，得到当前强分类器各个指标
void strongClassfier()
{
    int TP = 0;//True Positive(TP)：实际为1，判定结果为1int FP = 0;//False Positive(FP)：实际为0，判定结果为1int TN = 0;//True Negative(TN)：实际为0，判定结果为0int FN = 0;//False Negative(FN)：实际为1，判定结果为0for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    Record rec = (*it);double sum = 0;for (vector<WeakClassfier>::iterator sit = strong.begin(); sit != strong.end(); sit++){
    WeakClassfier weak = (*sit);if (!rec.hasValue[weak.attrIdx])//若记录rec的attrIdx属性值是'?',就认定分类错误{
    sum -= weak.weight;}else{
    sum += funH(weak.attrIdx, rec.attr[weak.attrIdx])*weak.weight;}}if (sign(sum) == rec.type)//判定结果和实际情况相同{
    if (rec.type == 0){
    TN++;}else{
    TP++;}}else//判定结果和实际情况不同{
    if (rec.type == 0){
    FP++;}else{
    FN++;}}}//计算并输出指标cout << "------T=" << strong.size() << "------" << endl;//精确率cout << "Precision:" << TP*1.0 / (TP + FP) << endl;//召回率cout << "Recall:" << TP*1.0 / (TP + FN) << endl;//准确率cout << "Accuracy:" << (TP + TN)*1.0 / (TP + TN + FP + FN) << endl<<endl;
}

代码说明
1.指标介绍请见[AI Algorithm] 评判预测性能的四个指标

Adaboost总流程

?//功能：用所有弱分类器weaks和训练集recs，训练出一个强分类器
void Adaboost()
{
    for (int i = 0; i < TIMES; i++){
    //1.取误差率最小的一个分类器WeakClassfier& weak = weaks[getBestWeakClassfier()];//2.调整该分类器的权重weak.weight = 0.5*log((1 - weak.errorRate) / weak.errorRate);//3.用该分类器再次进行分类，来调整记录的权重adjustRecordWeight(weak.attrIdx);//4.强分类器并入此弱分类器strong.push_back(WeakClassfier(weak));//5.用强分类器进行分类，得到当前各个指标strongClassfier();}
}

代码说明
1.TIMES是迭代的次数，理论上迭代次数越多，最后对训练集的分类结果越精确。

总结

1.弱分类器的选择很重要。本代码粗糙的弱分类器最终导致弱分类器已经有强分类器的效果，无论如何修改训练集，Adaboost的迭代都失去了意义。Accuracy总是在前两次迭代就达到了稳定。
2.在三天的时间内，匆匆理解原理并完成的代码还是有很多缺陷的。这里只是提供一个大概的思路，让自己对整个流程有个大概的了解，希望各位不要严肃对待:)

源代码

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;#define LOCAL
#define TIMES 50//训练集记录的结构体
struct Record
{
    bool hasValue[64];//64个属性是否存在double attr[64];//64个属性的值double weight;//记录的权重int type;//类别，0或1
};//弱分类器的结构体
struct WeakClassfier
{
    int attrIdx;//哪个属性上的弱分类器double cap;//阈值大小bool isHigher;//方向double weight;//分类器权重double errorRate;//误差率WeakClassfier(int a, double c, bool h, double w){
    attrIdx = a;cap = c;isHigher = h;weight = w;}
};vector<Record> recs;//训练集
vector<WeakClassfier> weaks;//弱分类器们
vector<WeakClassfier> strong;//一个强分类器//功能：遍历字符串str,将里面的','替换为空格
void replaceComma(string& str)
{
    for (int i = 0; i < str.length(); i++){
    if (str[i] == ','){
    str[i] = ' ';}}}//功能：输入训练集文件，将训练集的数据保存在recs之中
void inputRecords()
{
    Record tempRec;string line;while (!cin.eof()){
    //一行作为一条完整记录getline(cin, line);if (line == "") break;replaceComma(line);stringstream ss(line);//一行的字符串作为输入流for (int i = 0; i < 64; i++){
    //排除值为'?'的属性string tempStr;ss >> tempStr;if (tempStr != "?"){
    tempRec.hasValue[i] = true;//把string类型转化为double类型stringstream tempSS(tempStr);tempSS >> tempRec.attr[i];if (tempRec.attr[i] > 1000){
    int a = 1;}}elsetempRec.hasValue[i] = false;}ss >> tempRec.type;//记录的最后一个数字代表类别//记录+1recs.push_back(tempRec);}//给所有记录赋初始权重double numOfRecords = recs.size();for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    (*it).weight = 1.0 / numOfRecords;}
}//功能：在属性attrIdx(0~63)上训练一个弱分类器
void trainWeakClassifier(int attrIdx)
{
    //在所有记录的该属性上找到最大值和最小值，并且统计有效值的个数double Max = -9999;double Min = 9999;int nums = 0;for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    if ((*it).hasValue[attrIdx] == true){
    double currentValue = (*it).attr[attrIdx];nums++;if (currentValue > Max){
    Max = currentValue;}else if (currentValue < Min){
    Min = currentValue;}}}//确定合适的步长double step = (Max - Min) / 10.0;//寻找准确率最大的阈值和方向double bestCap = -9999;double bestAcc = 0;bool isHigherBetter = true;for (double cap = Min + step; cap < Max; cap += step){
    //用于计算准确率的变量int correctHigher = 0;int correctLower = 0;//统计分类准确率for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    Record currentRecord = (*it);//Higher: a>=cap 为 类1//Lower: a<cap 为 类1if ((*it).attr[attrIdx] >= cap){
    correctHigher += currentRecord.type == 1 ? 1 : 0;correctLower += currentRecord.type == 0 ? 1 : 0;}else{
    correctHigher += currentRecord.type == 0 ? 1 : 0;correctLower += currentRecord.type == 1 ? 1 : 0;}}//是否比当前的弱分类器准确率更高if (correctHigher >= correctLower){
    double tempAcc = correctHigher*1.0 / nums;if (tempAcc > bestAcc){
    bestCap = cap;bestAcc = tempAcc;isHigherBetter = true;}}else{
    double tempAcc = correctLower*1.0 / nums;if (tempAcc > bestAcc){
    bestCap = cap;bestAcc = tempAcc;isHigherBetter = false;}}}weaks.push_back(WeakClassfier(attrIdx, bestCap, isHigherBetter, 1.0));
}//功能：弱分类器函数H，可以将传入的分类器和属性值进行计算
int funH(int weakIdx, double attrVal)
{
    WeakClassfier weak = weaks[weakIdx];if (weak.isHigher){
    if (attrVal >= weak.cap) return 1;else return -1;}else{
    if (attrVal < weak.cap) return 1;else return -1;}
}//功能：符号判别函数
int sign(double a)
{
    if (a >= 0) return 1;else return 0;
}//功能：取误差率最小的一个分类器（编号）
int getBestWeakClassfier()
{
    //初始化for (vector<WeakClassfier>::iterator wit = weaks.begin(); wit != weaks.end(); wit++){
    (*wit).errorRate = 0;}//遍历所有记录和弱分类器for (vector<Record>::iterator rit = recs.begin(); rit != recs.end(); rit++){
    Record rec = (*rit);double recWeight = (*rit).weight;for (vector<WeakClassfier>::iterator wit = weaks.begin(); wit != weaks.end(); wit++){
    int attrIdx = (*wit).attrIdx;if (!rec.hasValue[attrIdx])//若记录rec的attrIdx属性值是'?',就认定分类错误{
    (*wit).errorRate += recWeight;}else{
    if (sign(funH((*wit).attrIdx, rec.attr[attrIdx])) != rec.type){
    (*wit).errorRate += recWeight;}}}}//找出误差率errorRate最小的分类器返回int bestIdx = 0;double minErrorRate = 2;for (vector<WeakClassfier>::iterator wit = weaks.begin(); wit != weaks.end(); wit++){
    if ((*wit).errorRate < minErrorRate){
    minErrorRate = (*wit).errorRate;bestIdx = (*wit).attrIdx;}}return bestIdx;
}//功能：用该弱分类器再次进行分类，来调整记录的权重
void adjustRecordWeight(int attrIdx)
{
    WeakClassfier weak = weaks[attrIdx];for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    if (!(*it).hasValue[attrIdx])//若记录rec的attrIdx属性值是'?',就认定分类错误{
    (*it).weight /= 2 * weak.errorRate;}else{
    if (sign(funH(attrIdx, (*it).attr[attrIdx])) != (*it).type)//分错{
    (*it).weight /= 2 * weak.errorRate;}else//分对{
    (*it).weight /= 2 * (1 - weak.errorRate);}}}
}//功能：用强分类器进行分类，得到当前强分类器各个指标
void strongClassfier()
{
    int TP = 0;//True Positive(TP)：实际为1，判定结果为1int FP = 0;//False Positive(FP)：实际为0，判定结果为1int TN = 0;//True Negative(TN)：实际为0，判定结果为0int FN = 0;//False Negative(FN)：实际为1，判定结果为0for (vector<Record>::iterator it = recs.begin(); it != recs.end(); it++){
    Record rec = (*it);double sum = 0;for (vector<WeakClassfier>::iterator sit = strong.begin(); sit != strong.end(); sit++){
    WeakClassfier weak = (*sit);if (!rec.hasValue[weak.attrIdx])//若记录rec的attrIdx属性值是'?',就认定分类错误{
    sum -= weak.weight;}else{
    sum += funH(weak.attrIdx, rec.attr[weak.attrIdx])*weak.weight;}}if (sign(sum) == rec.type)//判定结果和实际情况相同{
    if (rec.type == 0){
    TN++;}else{
    TP++;}}else//判定结果和实际情况不同{
    if (rec.type == 0){
    FP++;}else{
    FN++;}}}//计算并输出指标cout << "------T=" << strong.size() << "------" << endl;//精确率cout << "Precision:" << TP*1.0 / (TP + FP) << endl;//召回率cout << "Recall:" << TP*1.0 / (TP + FN) << endl;//准确率cout << "Accuracy:" << (TP + TN)*1.0 / (TP + TN + FP + FN) << endl<<endl;
}//功能：用所有弱分类器weaks和训练集recs，训练出一个强分类器
void Adaboost()
{
    for (int i = 0; i < TIMES; i++){
    //1.取误差率最小的一个分类器WeakClassfier& weak = weaks[getBestWeakClassfier()];//2.调整该分类器的权重weak.weight = 0.5*log((1 - weak.errorRate) / weak.errorRate);//3.用该分类器再次进行分类，来调整记录的权重adjustRecordWeight(weak.attrIdx);//4.强分类器并入此弱分类器strong.push_back(WeakClassfier(weak));//5.用强分类器进行分类，得到当前各个指标strongClassfier();}
}int main()
{
    
#ifdef LOCAL freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#endif inputRecords();for (int i = 0; i < 64; i++){
    trainWeakClassifier(i);}Adaboost();return 0;
}