算法的数学原理

DecisionTree算法没有过多的数学原理，如果说有的话，就是在划分选择那里不同的划分选择会有不同形式的计算
方式。。决策树中的主要数学知识源于信息论理论。就是著名的科学家香农提出并作出重要贡献的信息论。

划分选择
信息增益(ID3算法)
信息熵是度量样本集合纯度最常用的一种指标。源于信息论，如果学过信息论的同学就很容易理解了，没有学过
信息论的同学可以借一本信息论基础的书籍都会有介绍。有些教程会说如果对数学原理不是很感兴趣，或者不能
理解数学公式的话可以跳过这一节，但是我不建议这样做，其实所有的知识都是由一个一个知识点组成的，特别
难的问题可能只是它的知识点比较多，这个时候不要逃避，去攻克一个又一个的小知识点我们才能有所成长。比如
这里的信息熵我们可以花上两个小时读一下信息论的知识，就会对整个决策树算法有了不同的理解方式，如果总是
逃避自己没有学过的知识那进步是非常缓慢的，我们要对未知的知识怀有挑战心，而不是畏惧心。这不仅是我给大
家的建议，同时也是给我自己的督促，大部分的时候我也会畏惧，我也会懒惰，所以遇到新知识要有征服的欲望而
不是逃跑，这对我们正在学习任何知识都是必要的。

闲话少说，回到信息熵。

U中的类别越多代表需要确定某种类型所需要的信息量就会越多，也就是H(U)也会越大，这就是信息量的直观理解

信息增益率(C4.5)
实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种票好可能带来的不利影响，可以不直接使用
信息增益，而是使用信息增益率来选择最优的划分属性。
信息增益率(Information gain ratio)的定义如下：

基尼指数(CART)
CART决策树使用了基尼指数来选择划分属性。基尼系数是1943年美国经济学家阿尔伯特·赫希曼根据洛伦兹曲线所定义的
判断收入分配公平程度的指标。基尼系数是比例数值，在0和1之间，是国际上用来综合考察居民内部收入分配差异状况的
一个重要分析指标。关于这部分内容可以参考
Classification_and_Regression_Trees
这本书里有详细介绍，这里不做为重点讨论。

总之，上述三种算法的整体思想是一样的，就是通过划分属性来一步一步构建决策树，不同的地方在于划分的方法有所差异，我们在编程序过程中就可以根据不同的划分标准使用不同的函数。但整体的思路不变。

剪枝处理
剪枝是决策树学习算法解决“过拟合”问题的主要手段。在决策树学习中，也就是决策树的构建过程中，为了尽量
正确分类训练样本，结点划分过程将不断重复，有时候会造成分支过多，这时就是过拟合了，在神经网络学习过程
中可以通过提前结束训练或正则化方法来解决过拟合问题，在决策树学习中通常采用剪枝操作。剪枝操作又分为两种情况：预剪枝和后剪枝。下面分别阐述这两种方法。

预剪枝
预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化能力的
提升，则停止划分，将当前节点标记为叶子节点。如何判断泛化性能提升呢？可以利用机器学习算法的评估方法(如
留出法)对剪枝前和剪枝后的性能进行评估，如果剪枝可以提高学习器的泛化性能，那么就进行剪枝操作，否则不进
行剪枝操作。

后剪枝
后剪枝先从训练集中生成一棵完整的决策树，然后分别考虑各个节点，如果去掉该节点后的决策树泛化能力更强那就
将此节点去掉即进行了剪枝操作，反之不进行剪枝操作。

以一个实例来进行讲解算法
C++实现
经过上面的原理介绍和细节的探讨估计大家已经指导决策树是怎样进行目标分类的了。
这里面我构建了一个DecisionTree的类，

DecisionTree说明文档
class DedisionTree
{
public:
        struct Attr    //每一列的属性
        {
            int colIndex;
            string Attribute;
            int typeNum;   //属性取值的个数
            vector<string> AttributeValue;
            map<string, unsigned char>  typeMap; //属性取值对应的整数值;
        };
        struct TreeNode
        {   //节点信息
            string Attribute;   //此节点对应的属性
            bool LeafNode; //如果是叶子节点，此值反映分类结果。 //其他情况都是0;
            vector<TreeNode*> children; //孩子节点的地址。
            map<string, TreeNode*> AttributeLinkChildren;  
            //属性指向孩子节点，也就是对应的树形结构中的树枝
        };     
       //attributes
        cv::Mat trainDataMat;
        vector<vector<string>> predictedDataMat;
        //MatInfo trainMatrixInfo;
        TreeNode *root;  //根节点
        vector<Attr> vectorAttr; //存储所有的矩阵信息，但不存储矩阵。

        //functions
        DecisionTree();    //默认构造函数
        int ReadTrainDataFile(string fileAddress);  //数据预处理
        TreeNode* BuildTree(cv::Mat &data, vector<Attr> &dataAttr, string AlgorithmName); 
        // 指定是哪种算法
        vector<vector<string>> ReadPredictedDataFile(string fileAddreess);
        vector<string> Predicted(TreeNode* root, vector<vector<string>> &pData);  
        //返回值为int类型表示数据的分类。
        ～DecisionTree();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
TreeNode
TreeNode 结构体用来存储树的节点信息， Attribute 是std::string类型的数据用来存储当前节点的属性名称，如果该节点是中间节点(分支节点)，那么该值就是对应的属性名称，如果该节点是叶子节点，那么该值就是对应的分类结果。
**Attr **
Attr 结构体用来存储每一种属性的信息，包括这种属性有多少种不同的离散值,如下表所示表示根据不同的信息得出是否去打高尔夫的简单数据，以第一列数据为例，第一列表示天气属性，那么这一列信息对应着一个Attr结构，Attribute在这里的值就是Outlook，LeafNode及是标志，是否为叶子节点，如果是叶子节点，那么Attr存储的是最后一行分类的某个结果，比如说yes，children存储的是孩子节点的地址，AttributeLinkChildren存储的是孩子节点和属性值的映射关系，仍然以第一列数据为例，如果Outlook的结果是sunny那么此时指向sunny对应的叶子节点的地址。

trainDataMat
cv::Mat trainDataMat 存储训练集的数据，此结构由函数ReadTrainDataFile()生成

predictedDataMat
vector<vector<string> > predictedDataMat存储的是待预测的数据矩阵，此矩阵由vector<vector<string>> ReadPredictedDataFile()函数生成

root
TreeNode *root 该属性存储决策树的根节点地址

vectorAttr
vector<Attr> vectorAttr; 存储所有的属性信息

DecisionTree() 默认构造函数

ReadTrainDataFile()
int ReadTrainDataFile(string fileAddress)
此函数执行读取训练数据的功能，输入值为待训练的数据集的地址，数据集的文件要求是必须为csv文件，关于csv文件参考百度百科 并且第一行的属性名称行是不能省略的，如下图的红色部分。此函数内部运行结束直接生成trainDataMat和vectorAttr数据，这两个数据在后面的操作中非常重要。

BuildTree()
TreeNode* BuildTree(cv::Mat &data, vector<Attr> &dataAttr, string AlgorithmName)
此函数用于生成决策树，函数的返回值是决策树根节点的地址，需要将此值返回给root属性，留给后面的预测时使用。

data 是训练集数据，类型为OpenCV中的Mat类型，对应类中的trainDataMat
dataAttr 是训练数据的属性信息，对应类中的vectorAttr
AlgorithmName 是需要指定的决策树划分节点属性类型的方法，这个类中只支持ID3、C4_5、和Gini这三种方法。
ReadPredictedDataFile()
vector<vector<string>> ReadPredictedDataFile(string fileAddreess);
此函数执行读取待预测数据信息的功能，函数输入为待预测的数据，输出为字符串格式的矩阵。同样该文件是csv文件格式，但和ReadTrainDataFile有所差别就是该数据集不需要第一行的属性信息，如果有第一行的属性信息程序可能会出错，同时也不需要最后一列的标签列，对应的该矩阵的列数一定比训练矩阵的列数少1，行数没有限制。此函数输入的文件格式如下图,

Predicted()
vector<string> Predicted(TreeNode* root, vector<vector<string>> &pData)
此函数执行预测的功能,函数的输入参数包括根节点地址root和预测数据矩阵pData。

Example
下面是简单的应用举例

输入数据说明
该类的两次输入分别是训练集和预测的测试集，并且都是csv格式的文件，此外目前算法只支持离散数据的分类，对于连续性数据不能使用，且每一列的属性个数不得多于255种，这是因为在程序设计中，每一列的数据个数的这个属性是采用uchar数据类型，所以不能多于255种，当然我们也可以根据自己的实际情况进行更改。程序的执行流程如下图所示

    //生成决策树对象
    DecisionTree myDecisionTree; 
    //读取训练集数据并对训练数据进行操作
    myDecisionTree.ReadTrainDataFile("data.csv");  
    //构建决策树,需要指明决策树划分的方法：ID3、C4.5、CART这三种
    myDecisionTree.root = myDecisionTree.BuildTree(myDecisionTree.trainDataMat, myDecisionTree.vectorAttr, "ID3");
    //
    vector<string> result;
    vector<vector<string>> predictedData;
    //对待预测数据进行读取并进行处理
    predictedData = myDecisionTree.ReadPredictedDataFile("pre.csv");
    //预测结果
    result = myDecisionTree.Predicted(myDecisionTree.root, predictedData);
1
2
3
4
5
6
7
8
9
10
11
12
13
在最后一步的预测中也可以不额外开辟 predictedData数据，因为在ReadPredictedDataFile()函数执行过程中已经备份一份数据到对象的predictedDataMat属性中，所以按照下面的方法会节省空间和时间
result = myDecisionTree.Predicted(myDecisionTree.root, myDecisionTree.predictedDataMat);直接调用对象中的数据即可。

～DecisionTree()
～DecisionTree() 为构析函数

总结程序的优缺点
最开始的版本我刚刚开始学习C++，所以对于内存溢出的问题还不是特别敏感，所以在DecisionTree 类中动态开辟的内存空间都没有手动释放掉，主要是决策树的构建过程中开辟了许多堆空间，所以最终的版本需要加一个DestroyTree()函数将构建决策树过程中手动开辟的内存空间都释放掉。将内存泄漏的问题解决掉。还有程序中我遗留了四个问题 1.C4.5算法 2.CART算法 3.预剪枝 4. 后剪枝 这4个部分我还没有完成，我会慢慢完善所有功能，目前的版本只支持了ID3算法，其他算法也预留了函数位置，但是函数是空的，在调用过程中肯定会出错。

程序运行实例
#include "DecisionTree.hpp"
int main()
{
    string fileAddress;
    cout << "请输入文件的地址：";
    cin >> fileAddress;
    //cout << sizeof(unsigned int) << endl;
    DecisionTree myDecisionTree;
    myDecisionTree.ReadTrainDataFile(fileAddress);
    myDecisionTree.root = myDecisionTree.BuildTree(myDecisionTree.trainDataMat, myDecisionTree.vectorAttr, "ID3");

    //查看经过处理的样本矩阵
    // cout << myDecisionTree.dataMat << endl;
    cv::FileStorage fs("out.yml", cv::FileStorage::WRITE);
    int t = int(myDecisionTree.vectorAttr.size());
    for (int i = 0; i < t; i++)
    {
        fs << "Attribute" << myDecisionTree.vectorAttr[i].Attribute;
        fs << "typeNum" << myDecisionTree.vectorAttr[i].typeNum;
        // fs << "AttribureValue";
        for (int j = 0; j < myDecisionTree.vectorAttr[i].AttributeValue.size(); j++)
        {
            fs << "value "<< myDecisionTree.vectorAttr[i].AttributeValue[j];
        }
    }
    fs << "dataMat" << myDecisionTree.trainDataMat;
    fs.release();

    //进行预测
    vector<string> result;
    vector<vector<string>> predictedData;
    predictedData = myDecisionTree.ReadPredictedDataFile("pre.csv");
    result = myDecisionTree.Predicted(myDecisionTree.root, predictedData);
    cout << "预测的结果如下：" << endl;
    for (int i = 0; i < result.size(); i++)
    {
        cout << result[i] << endl;
    }
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
DecisionTree源代码
如果你是刚刚接触C++也不懂文件的依赖关系，也不懂的怎么用makefile编译，仅仅是想调用一下这个Decision用
一下的话，我建议你可以把我源代码中的DecisionTree的头文件和cpp文件放到你的工程里，然后include 头文件即可。

在下才疏学浅，很多地方还需要做的更好，如果有任何建议，请不吝赐教，我的昵称是PiggyGaGa，名为小猪嘎嘎。git同名。
欢迎留言。文章中有些内容借鉴周志华老师的西瓜书中的内容，仅当学习使用。
掌管天堂的空之王者，于地狱唱响荣光之歌！
————————————————
版权声明：本文为CSDN博主「小猪嘎嘎」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/luoluonuoyasuolong/article/details/78696829