决策树CART实现

c++实现决策树之CART算法

#include “LDecisionTree.h“

#include 
#include 

#include 
using std::set;

/// @brief 计算数据的熵
/// 
/// 对于任意一个随机变量 X 它的熵定义如下:
/// 变量的不确定性越大 熵也就越大 把它搞清楚所需要的信息量也就越大
/// @param[in] dataList 数据列表
/// @return 数据的熵
template
static float CalculateEntropy（IN const LArray& dataList）
{
    float entropy = 0.0f;
    map typeCountMap;
    for （int i = 0; i < dataList.Length; i++）
    {
        ++typeCountMap[dataList.Data[i]];
    }

    for （auto iter = typeCountMap.begin（）; iter != typeCountMap.end（）; iter++）
    {
        float prob = （float）（iter->second）/（float）（dataList.Length）;
        entropy -= prob * log（prob）/log（2.0f）;
    }

    return entropy;
}

static float CalculateEntropy（IN const map& dataMap）
{
    float entropy = 0.0f;

    int totalCount = 0;
    for （auto iter = dataMap.begin（）; iter != dataMap.end（）; iter++）
    {
        totalCount += iter->second;
    }

    for （auto iter = dataMap.begin（）; iter != dataMap.end（）; iter++）
    {
        float prob = （float）（iter->second）/（float）（totalCount）;
        entropy -= prob * log（prob）/log（2.0f）;
    }

    return entropy;
}


/// @brief决策树节点
struct LDecisionTreeNode
{
    LDecisionTreeNode（）
    {
        m_checkColumn = -1;
        m_pTrueChildren = 0;
        m_pFalseChildren = 0;
    }

    LDecisionTreeNode（
        IN int column 
        IN const LVariant& checkValue 
        IN LDecisionTreeNode* pTrueChildren 
        IN LDecisionTreeNode* pFalseChildren）
    {
        m_checkColumn = column;
        m_checkValue = checkValue;
        m_pTrueChildren = pTrueChildren;
        m_pFalseChildren = pFalseChildren;
    }

    LDecisionTreeNode（IN const map& resultMap）
    {
        m_resultMap = resultMap;
    }

    int m_checkColumn; ///< 需要检验的列索引
    LVariant m_checkValue; ///< 为了使结果为true 当前列必须匹配的值（如果变体是字符串则必须相等才为true 如果变体是浮点数则大于等于为true）

    LDecisionTreeNode* m_pTrueChildren; ///< 条件为true的分支节点
    LDecisionTreeNode* m_pFalseChildren; ///< 条件为false的分支节点

    map m_resultMap; ///< 当前分支的结果 除了叶节点外 在其他节点上该值都没有
};

LVariant::LVariant（）
{
    m_pValueInt = 0;
    m_pValueStr = 0;
    m_type = UNKNOWN;
}

LVariant::LVariant（IN int value）
{
    
    m_pValueInt = 0;
    m_pValueStr = 0;

    m_pValueInt = new int;
    （*m_pValueInt） = value;
    m_type = INT;
    
}

LVariant::LVariant（IN const string& value）
{
    m_pValueInt = 0;
    m_pValueStr = 0;

    m_pValueStr = new string;
    （*m_pValueStr） = value;
    m_type = STRING;
}

LVariant::LVariant（IN const LVariant& rhs）
{
    this->m_type = rhs.m_type;
    this->m_pValueInt = 0;
    this->m_pValueStr = 0;

    if （rhs.m_pValueInt != 0）
    {
        this->m_pValueInt = new int（*rhs.m_pValueInt）;
    }

    if （rhs.m_pValueStr != 0）
    {
        this->m_pValueStr = new string（*rhs.m_pValueStr）;
    }
}

LVa

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        874  2015-06-15 10:57  CART\CART.sln

    ..A..H.      8192  2015-06-15 10:57  CART\CART.suo

     文件       3445  2015-06-15 10:58  CART\CART.vcxproj

     文件       1387  2015-06-15 10:58  CART\CART.vcxproj.filters

     文件        143  2015-06-15 10:57  CART\CART.vcxproj.user

     文件       2712  2015-05-19 15:08  CART\LArray.h

     文件      22099  2015-06-12 17:18  CART\LDecisionTree.cpp

     文件       5011  2015-06-15 10:58  CART\LDecisionTree.h

     文件       4642  2015-06-15 10:57  CART\main.cpp

     文件         59  2015-06-05 11:22  CART\ReadMe.txt

     目录          0  2015-06-15 10:58  CART

----------- ---------  ---------- -----  ----

                48564                    11