统计学习方法c++实现之四 决策树

决策树

前言

决策树是一种基本的分类和回归算法,书中主要是讨论了分类的决策树。决策树在每一个结点分支规则是一种if-then规则,即满足某种条件就继续搜索左子树,不符合就去右子树,看起来是用二叉树实现对吧,实际的CART决策树就是二叉树,等会再介绍。现在先来看看决策树的理论部分。代码地址https://github.com/bBobxx/statistical-learning/blob/master/src/decisiontree.cpp

决策树相关理论

决策树的学习通常包括三个部分:特征选择决策树生成决策树修剪

特征选择

我们抛开烦人的公式和术语,用通俗的思想(没办法,本人只有通俗的思想)来理解一下,现在给你很多数据,有很多类,每个数据有n维的特征,怎么分?最简单的,不如来个全连接神经网络,把数据丢进去,让模型自己去学习去,恩.....这个办法可能是准确率最高的,但是我们这里学习的是决策树,而且有些场景根本不需要神经网络也可以分类的很准确,现在让我们用决策树解决这个问题。

首先,面对n维特征,和k个类别,仿佛无从下手。咋办呢,笨一点的办法,就从第一个特征开始,如果第一个特征有m个不同取值,那我就按这个特征取值把数据分成m份,对这份特征子集,我再选第二个特征,第二个特征比如有l个不同取值,那么对于m个子集,每个又可以最多分出l个子集(最多而不是一定,因为m某个子集中的数据的第二维特征可能取不全l个值),那么现在我们最多有\(m\times l\) 个子集,然后是第三维特征......直到第n维特征或者某个子集中的数据类别几乎一样我们就停止。对于这种分法很明显确实是个树结构对吧,只不过你的树可能是这样子的:

不好意思,弄错了,一般树结构是这样子的:

思路很简单,但是过程很复杂对吧,没错,这就是决策树,但是如果真写成上面这样也太没效率了,比如说,现在给你很多人的数据,让你分出是男是女,特征有这么几个:身高,体重,头发长短,身份证上的性别。没错最后一个特征一般不会给出的。现在开始按照上面的思路分类,就分10000个数据吧,身高的取值有十种,就当做150到190取十个数吧,体重先不谈,如果从身高这个特征开始分就能把你分吐血。聪明的同学(应该是不笨的)一眼就能看出来,我直接用最后一个特征,一下子就分出来了,就算没有最后这个特征,我用头发长短这个也可以很好的分。

没错,看出特征选择的重要了吧,这就是决策树的第一步,要先选择最具有分类能力的特征,注意每一维特征只用一次。怎么选呢,这就涉及到了信息增益(ID3决策树), 信息增益比(C4.5决策树),和基尼指数(CART决策树)。皮一下,这里就只介绍基尼指数吧,其他的就看书吧。

基尼指数:\(Gini(D,A)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)\)

其中,A代表某一维特征,D代表的数据集合,根据A是否取a将D分为\(D_1\) 和\(D_2\)两个子集,\(|D|,|D_1|,|D_2|\)分别代表各自的数量。

其中,\(Gini(D) = \sum_{k=1}^{K}\frac{|C_k|}{|D|}(1-\frac{|C_k|}{|D|})\)

\(C_k\)代表某一类,\(\frac{|C_k|}{|D|}\)代表这个集合中样本是第k类的概率。

基尼指数越大,表示样本集合的不确定性越大,我们在选取A的时候肯定希望分完后集合越确定越好,所以以后在进行特征选择的时候就需要选取基尼指数最小的那个特征。

决策树(CART)生成算法

  1. 对于当前根节点Root,对现有的样本集D,对所有的特征\(A_i\)的所有可能取值\(a_j\)计算基尼指数,选择使基尼指数最小的\(A_i\)和\(a_j\),根据样本点对\(A_i=a_j\)的测试为“是”或“否”将D分为\(D_1\)和\(D_2\)。
  2. \(D_1\)作为根节点Root的左子树的根节点Root_L的样本集,\(D_2\)作为根节点Root的右子树的根节点Root_R的样本集。
  3. 重复1,2直到结点中样本个数小于阈值,或样本集基本属于同一类,或者没有更多特征(代表已经将所有的特征都过一遍了)。

CART剪枝

请自行看书,反正我也没实现。

决策树的c++实现

代码结构

实现

这里只展示如何确定分割的特征和值

pair<int, double> DecisionTree::createSplitFeature(vector<vector<double >>& valRange){
    priority_queue<pair<double, pair<int, double>>, vector<pair<double, pair<int, double>>>, std::greater<pair<double, pair<int, double>>>> minheap;
      //pair<double, pair<int, double>> first value is Gini value, second pair (pair<int, double>) first value is split
      //axis, second value is split value
    vector<map<double, int>> dataDivByFeature(indim);  //vector size is num of axis, map‘s key is the value of feature, map‘s value is
      //num belong to feature‘value
    vector<set<double>> featureVal(indim);  //store value for each axis
    vector<map<pair<double, double>, int>> datDivByFC(indim);  //vector size is num of axis, map‘s key is the feature value and class value, map‘s value is
      //num belong to that feature value and class
    set<double> cls;  //store num of class
    for(const auto& featureId:features) {
        if (featureId<0)
            continue;
        map<double, int> dataDivByF;
        map<pair<double, double>, int> dtDivFC;
        set<double> fVal;
        for (auto& data:valRange){  //below data[featureId] is the value of one feature axis, data.back() is class value
            cls.insert(data.back());
            fVal.insert(data[featureId]);
            if (dataDivByF.count(data[featureId]))
                dataDivByF[data[featureId]] += 1;
            else
                dataDivByF[data[featureId]] = 0;
            if (dtDivFC.count(std::make_pair(data[featureId], data.back())))
                dtDivFC[std::make_pair(data[featureId], data.back())] += 1;
            else
                dtDivFC[std::make_pair(data[featureId], data.back())] = 0;
        }
        featureVal[featureId] = fVal;
        dataDivByFeature[featureId] = dataDivByF;
        datDivByFC[featureId] = dtDivFC;
    }
    for (auto& featureId: features) {  // for each feature axis
        if (featureId<0)
            continue;
        for (auto& feVal: featureVal[featureId]){  //for each feature value
            double gini1 = 0 ;
            double gini2 = 0 ;

            double prob1 = dataDivByFeature[featureId][feVal]/double(valRange.size());
            double prob2 = 1 - prob1;
            for (auto& c : cls){  //for each class
                double pro1 = double(datDivByFC[featureId][std::make_pair(feVal, c)])/dataDivByFeature[featureId][feVal];
                gini1 += pro1*(1-pro1);
                int numC = 0;
                for (auto& feVal2: featureVal[featureId])
                    numC += datDivByFC[featureId][std::make_pair(feVal2, c)];
                double pro2 = double(numC-datDivByFC[featureId][std::make_pair(feVal, c)])/(valRange.size()-dataDivByFeature[featureId][feVal]);
                gini2 += pro2*(1-pro2);
            }
            double gini = prob1*gini1+prob2*gini2;

            minheap.push(std::make_pair(gini, std::make_pair(featureId, feVal)));
        }
    }
    features[minheap.top().second.first]=-1;
    return minheap.top().second;
}

这里使用循环嵌套计算符合条件的数据的数量,效率很低,有更好方法的同学麻烦告知一下,叩拜~

原文地址:https://www.cnblogs.com/bobxxxl/p/10259049.html

时间: 01-11

统计学习方法c++实现之四 决策树的相关文章

统计学习方法笔记(1)——统计学习方法概论

1.统计学习 统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科,也称统计机器学习.统计学习是数据驱动的学科.统计学习是一门概率论.统计学.信息论.计算理论.最优化理论及计算机科学等多个领域的交叉学科. 统计学习的对象是数据,它从数据出发,提取数据的特征,抽象出数据的模型,发现数据中的知识,又回到对数据的分析与预测中去.统计学习关于数据的基本假设是同类数据具有一定的统计规律性,这是统计学习的前提. 统计学习的目的就是考虑学习什么样的模型和如何学习模型. 统计学习

统计学习方法概论

统计学习 统计学习是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科.统计学习也称为统计机器学习(statical machine learning). 统计学习的方法是基于数据构建统计模型从而对数据进行预测和分析.统计学习由监督学习.非监督学习.半监督学习和强化学习等组成. 统计学习方法包括假设空间.模型选择的准则.模型学习的算法,这些统称为统计学习方法的三要素:模型(Model).策略(Strategy).算法(Algorithm). 实现统计学习方法的步骤如下:

统计学习方法(一)(李航)

统计学习方法概论: (一),统计学习 1,统计学习的特点 2,统计学习的对象 3,统计学习的目的 4,统计学习的方法 (二),监督学习重要概念 1,输入空间,特征向量空间,输出空间 (三),统计学习三要素 1,模型 决策函数模型: 条件概率模型: 2,策略 2.1 损失函数: 2.2 经验风险最小化和结构最小化 如贝叶斯估计的最大后验概率就是一种结构风险最小化的一个例子 3,算法 (四)模型评估选择 1,训练误差和测试误差 2,过拟合 过拟合和欠拟合产生的原因及解决方式: 欠拟合的原因:模型复杂

机器学习-李航-统计学习方法学习笔记之感知机(2)

在机器学习-李航-统计学习方法学习笔记之感知机(1)中我们已经知道感知机的建模和其几何意义.相关推导也做了明确的推导.有了数学建模.我们要对模型进行计算. 感知机学习的目的是求的是一个能将正实例和负实例完全分开的分离超平面.也就是去求感知机模型中的参数w和b.学习策略也就是求解途径就是定义个经验损失函数,并将损失函数极小化.我们这儿采用的学习策略是求所有误分类点到超平面S的总距离.假设超平面s的误分类点集合为M,那么所有误分类点到超平面S的总距离为 显然损失函数L(w,b)是非负的,如果没有误分

统计学习方法:感知机

作者:桂. 时间:2017-04-16  11:53:22 链接:http://www.cnblogs.com/xingshansi/p/6718503.html 前言 今天开始学习李航的<统计学习方法>,考虑到之前看<自适应滤波>,写的过于琐碎,拓展也略显啰嗦,这次的学习笔记只记录书籍有关的内容.前段时间朋友送了一本<机器学习实战>,想着借此增加点文中算法的代码实现,以加深对内容的理解.本文梳理书本第二章:感知机(Perceptron). 1)原理介绍 2)代码实现

《统计学习方法》:EM算法重点学习以及习题。

适用场景:有隐变量的时候特别适用. EM算法主要分为两个步骤:E步和M步. 输入:选择参数的初值theta,进行迭代. E步: 每次迭代改变初值.定义Q函数.Q函数为迭代的期望值. M步: 求使E步得到的Q函数最大的theta值. 最后,重复进行E步和M步.直到最终theta值变化较小,即为收敛为止. 注意:初值为算法的选择尤为重要.初值的选择会影响结果. EM算法得到的估计序列能够最终收敛得到结果.但是收敛得到的结果并不能保证能够收敛到全局最大值或者局部最大值. EM算法在两个方面极其有用:在

机器学习-统计学习方法中多项式拟合偏导函数推导

最近在学机器学习,看了Andrew Ng 的公开课,同时学习李航博士的 <统计学习方法>在此记录. 在第十二页有一个关于多项式拟合的问题.此处,作者直接给出了所求的的偏导.这里做一下详细推导. , 此处函数模型的求偏导问题,首先看一下偏导的定义 因为此处是,所以除了Wj 外的Xi,Yi 都可以视作常数.对此求解. 推导后我们会发现所得出的公式与作者给出的答案不同 ,不过作者也给出了更正的勘误 但是我们发现还是和我推导出的答案不同.作者分母下的x上标为j+1,而我推导出的上标为2j,参考作者的勘

统计学习方法 &ndash;&gt; 支持向量机

前言 定义: 在特征空间上间隔最大的线性分类器. 核是SVM非常重要的一个特性. 支持向量机的学习策略就是间隔最大化,可形式化为一个求解凸二次规划的问题. 分类 1>线性可分支持向量机 2>线性支持向量机 3>非线性支持向量机 如果训练数据线性可分,那么可以通过硬间隔最大化,学习一个线性分类器,就是线性可分支持向量机,就是硬间隔支持向量机. 类似,如果训练数据近似线性可分,那么可以通过软间隔最大化来学习一个线性的分类器.成为软间隔支持向量机. 训练数据线性不可分的时候,就必须动用核函数来

统计学习方法文本分类

一个文本分类问题就是将一篇文档归入预先定义的几个类别中的一个或几个,而文本的自动分类则是使用计算机程序来实现这样的分类.通俗点说,就好比你拿一篇文章,问计算机这文章要说的究竟是体育,经济还是教育,计算机答不上,说明计算机弱爆了就打它的屁屁. 注意这个定义当中着重强调的两个事实. 第一,用于分类所需要的类别体系是预先确定的.例如新浪新闻的分类体系,Yahoo!网页导航的分类层次.这种分类层次一旦确定,在相当长的时间内都是不可变的,或者即使要变更,也要付出相当大的代价(基本不亚于推倒并重建一个分类系

统计学习方法笔记--监督学习

监督学习(supervised learning)的任务是学习一个模型,使模型能够对任意给定的输入,对其相应的输出做出一个好的预测,计算机的基本操作就是给定一个输入产生一个输出. 基本概念:输入空间.特征空间与输出空间 在监督学习中,将输入与输出所有可能取值的集合分别称为输入空间(input space)与输出空间(output space). 每个具体的输入是一个实例(instance),通常有特征向量(feature vector)表示.这时,所有特征向量存在的空间称为特征空间(featur