决策树算法对应的测试函数

华电北风吹

天津大学认知计算与应用重点实验室

修改日期:2015/8/15

决策树是一种特别简单的机器学习分类算法。决策树想法来源于人类的决策过程。举个最简单的例子,人类发现下雨的时候,往往会有刮东风,然后天色变暗。对应于决策树模型,预测天气模型中的刮东风和天色变暗就是我们收集的特征,是否下雨就是类别标签。构建的决策树如下图所示

决策树模型构建过程为,在特征集合中无放回的依次递归抽选特征作为决策树的节点——当前节点信息增益或者增益率最大,当前节点的值作为当前节点分支出来的有向边(实际上主要选择的是这些边,这个由信息增益的计算公式就可以得到)。对于这个进行直观解释

来说一个极端情况,如果有一个特征下,特征取不同值的时候,对应的类别标签都是纯的,决策者肯定会选择这个特征,作为鉴别未知数据的判别准则。由下面的计算信息增益的公式可以发现这时候对应的信息增益是最大的。

g(D,A)=H(D)-H(D|A)

g(D,A):表示特征A对训练数据集D的信息增益

H(D):表示数据集合D的经验熵

H(D|A):表示特征A给定条件下数据集合D的条件熵。

反之,当某个特征它的各个取值下对应的类别标签均匀分布的时候H(D|A)最大,又对于所有的特征H(D)是都一样的。因此,这时候的g(D,A)最小。

总之一句话,我们要挑选的特征是:当前特征下各个取值包含的分类信息最明确。

下面我们来看一个MATLAB编写的决策树算法,帮助理解

树终止条件为

1、特征数为空

2、树为纯的

3、信息增益或增益率小于阀值

一、模型训练部分

训练模型主函数:

function decisionTreeModel=decisionTree(data,label,propertyName,delta)

global Node;

Node=struct(‘level‘,-1,‘fatherNodeName‘,[],‘EdgeProperty‘,[],‘NodeName‘,[]);
BuildTree(-1,‘root‘,‘Stem‘,data,label,propertyName,delta);
Node(1)=[];
model.Node=Node;
decisionTreeModel=model;

递归构建决策树部分

function BuildTree(fatherlevel,fatherNodeName,edge,data,label,propertyName,delta)

global Node;
sonNode=struct(‘level‘,0,‘fatherNodeName‘,[],‘EdgeProperty‘,[],‘NodeName‘,[]);
sonNode.level=fatherlevel+1;
sonNode.fatherNodeName=fatherNodeName;
sonNode.EdgeProperty=edge;
if length(unique(label))==1
    sonNode.NodeName=label(1);
    Node=[Node sonNode];
    return;
end
if length(propertyName)<1
    labelSet=unique(label);
    k=length(labelSet);
    labelNum=zeros(k,1);
    for i=1:k
        labelNum(i)=length(find(label==labelSet(i)));
    end
    [~,labelIndex]=max(labelNum);
    sonNode.NodeName=labelSet(labelIndex);
    Node=[Node sonNode];
    return;
end
[sonIndex,BuildNode]=CalcuteNode(data,label,delta);
if BuildNode
    dataRowIndex=setdiff(1:length(propertyName),sonIndex);
    sonNode.NodeName=propertyName{sonIndex};
    Node=[Node sonNode];
    propertyName(sonIndex)=[];
    sonData=data(:,sonIndex);
    sonEdge=unique(sonData);

    for i=1:length(sonEdge)
        edgeDataIndex=find(sonData==sonEdge(i));
        BuildTree(sonNode.level,sonNode.NodeName,sonEdge(i),data(edgeDataIndex,dataRowIndex),label(edgeDataIndex,:),propertyName,delta);
    end
else
    labelSet=unique(label);
    k=length(labelSet);
    labelNum=zeros(k,1);
    for i=1:k
        labelNum(i)=length(find(label==labelSet(i)));
    end
    [~,labelIndex]=max(labelNum);
    sonNode.NodeName=labelSet(labelIndex);
    Node=[Node sonNode];
    return;
end

计算决策树下一个节点特征

function [NodeIndex,BuildNode]=CalcuteNode(data,label,delta)

LargeEntropy=CEntropy(label);
[m,n]=size(data);
EntropyGain=LargeEntropy*ones(1,n);
BuildNode=true;
for i=1:n
    pData=data(:,i);
    itemList=unique(pData);
    for j=1:length(itemList)
        itemIndex=find(pData==itemList(j));
        EntropyGain(i)=EntropyGain(i)-length(itemIndex)/m*CEntropy(label(itemIndex));
    end
    % 此处运行则为增益率,注释掉则为增益
    % EntropyGain(i)=EntropyGain(i)/CEntropy(pData);
end
[maxGainEntropy,NodeIndex]=max(EntropyGain);
if maxGainEntropy<delta
    BuildNode=false;
end

计算熵

function result=CEntropy(propertyList)

result=0;
totalLength=length(propertyList);
itemList=unique(propertyList);
pNum=length(itemList);
for i=1:pNum
    itemLength=length(find(propertyList==itemList(i)));
    pItem=itemLength/totalLength;
    result=result-pItem*log2(pItem);
end

二、模型预测

下面这个函数是根据训练好的决策树模型,输入测试样本集合和特征名,对每个测试样本预测输出结果。

function label=decisionTreeTest(decisionTreeModel,sampleSet,propertyName)

lengthSample=size(sampleSet,1);
label=zeros(lengthSample,1);
for sampleIndex=1:lengthSample
    sample=sampleSet(sampleIndex,:);
    Nodes=decisionTreeModel.Node;
    rootNode=Nodes(1);
    head=rootNode.NodeName;
    index=GetFeatureNum(propertyName,head);
    edge=sample(index);
    k=1;
    level=1;
    while k<length(Nodes)
        k=k+1;
        if Nodes(k).level==level
            if strcmp(Nodes(k).fatherNodeName,head)
                if Nodes(k).EdgeProperty==edge
                    if Nodes(k).NodeName<10
                        label(sampleIndex)=Nodes(k).NodeName;
                        break;
                    else
                        head=Nodes(k).NodeName;
                        index=GetFeatureNum(propertyName,head);
                        edge=sample(index);
                        level=level+1;
                    end
                end
            end
        end
    end
end

由于训练好的决策树模型里面保存的是节点名,所以在预测的时候需要将节点名对应的特征得到。下面这个函数是为了方便得到特征维数序号。

function result=GetFeatureNum(propertyName,str)
result=0;
for i=1:length(propertyName)
    if strcmp(propertyName{i},str)==1
        result=i;
        break;
    end
end

三、决策树实验

这是很多书本上都有的一个例子,可以看出预测结果准确率100%。

clear;clc;

% OutlookType=struct(‘Sunny‘,1,‘Rainy‘,2,‘Overcast‘,3);
% TemperatureType=struct(‘hot‘,1,‘warm‘,2,‘cool‘,3);
% HumidityType=struct(‘high‘,1,‘norm‘,2);
% WindyType={‘True‘,1,‘False‘,0};
% PlayGolf={‘Yes‘,1,‘No‘,0};
% data=struct(‘Outlook‘,[],‘Temperature‘,[],‘Humidity‘,[],‘Windy‘,[],‘PlayGolf‘,[]);

Outlook=[1,1,3,2,2,2,3,1,1,2,1,3,3,2]‘;
Temperature=[1,1,1,2,3,3,3,2,3,3,2,2,1,2]‘;
Humidity=[1,1,1,1,2,2,2,1,2,2,2,1,2,1]‘;
Windy=[0,1,0,0,0,1,1,0,0,0,1,1,0,1]‘;

data=[Outlook Temperature Humidity Windy];
PlayGolf=[0,0,1,1,1,0,1,0,1,1,1,1,1,0]‘;
propertyName={‘Outlook‘,‘Temperature‘,‘Humidity‘,‘Windy‘};
delta=0.1;
decisionTreeModel=decisionTree(data,PlayGolf,propertyName,delta);

label=decisionTreeTest(decisionTreeModel,data,propertyName);

版权声明:本文为博主原创文章,未经博主允许不得转载。

时间: 08-13

决策树算法对应的测试函数的相关文章

scikit-learn决策树算法类库使用小结

参考:http://www.cnblogs.com/pinard/p/6056319.html 之前对决策树的算法原理做了总结,包括决策树算法原理(上)和决策树算法原理(下).今天就从实践的角度来介绍决策树算法,主要是讲解使用scikit-learn来跑决策树算法,结果的可视化以及一些参数调参的关键点. 1. scikit-learn决策树算法类库介绍 scikit-learn决策树算法类库内部实现是使用了调优过的CART树算法,既可以做分类,又可以做回归.分类决策树的类对应的是Decision

Spark机器学习(6):决策树算法

1. 决策树基本知识 决策树就是通过一系列规则对数据进行分类的一种算法,可以分为分类树和回归树两类,分类树处理离散变量的,回归树是处理连续变量. 样本一般都有很多个特征,有的特征对分类起很大的作用,有的特征对分类作用很小,甚至没有作用.如决定是否对一个人贷款是,这个人的信用记录.收入等就是主要的判断依据,而性别.婚姻状况等等就是次要的判断依据.决策树构建的过程,就是根据特征的决定性程度,先使用决定性程度高的特征分类,再使用决定性程度低的特征分类,这样构建出一棵倒立的树,就是我们需要的决策树模型,

决策树算法

利用ID3算法来判断某天是否适合打网球. (1)类别属性信息熵的计算由于未分区前,训练数据集中共有14个实例, 其中有9个实例属于yes类(适合打网球的),5个实例属于no类(不适合打网球), 因此分区前类别属性的熵为: (2)非类别属性信息熵的计算,若先选择Outlook属性. (3)Outlook属性的信息增益为: (4)同理计算出其他3个非类别属性的信息增益,取最大的那个属性作为分裂节点,此例中最大的是Outlook,进而得到如下图所示: (5)上图中,针对sunny中的子训练数据集分支,

R(rattle)实现决策树算法

使用R实现决策树分析 决策树算法也是数据挖掘的核心算法之一,使用树形结构模型进行知识表达.非叶子节点为分支条件,叶子节点为决策条件. 分支算法主要使用的信息增益,这里不再详述.本篇案例主要也是使用weather数据集建立决策树模型,使用Rattle的model工具栏的Tree选项,rattle包的安装如下: > install.packages("rattle") 1.使用rattle建立决策树模型 在data工具栏加载weather数据集后,点击执行按钮,然后转到model工具

算法干货----决策树算法中的熵与信息增益

什么是决策树?为什么要用决策树? 决策树是一种二分树,或是多分数.对于大量数据的细分工作有很大帮助.在日常生活中,决策树的算法可谓是每天都在用.小到用户分类,大到辅助决策.实际上他的使用很多. 至于为什么要用到决策树,个人认为就是因为这种算法简单.代码实现起来主要就是IF-ELSE就可以实现.可这一算法的发展也是从ID3--->C4.5----->C5.0. 它的主要步骤就两个:1,建树 2,剪树 如何建树,就是如何分你的数据,按照哪种特性?比如人口统计数据,是按年龄,身高,体重,学历....

如何实现并应用决策树算法?

本文对决策树算法进行简单的总结和梳理,并对著名的决策树算法ID3(Iterative Dichotomiser 迭代二分器)进行实现,实现采用Python语言,一句老梗,“人生苦短,我用Python”,Python确实能够省很多语言方面的事,从而可以让我们专注于问题和解决问题的逻辑. 根据不同的数据,我实现了三个版本的ID3算法,复杂度逐步提升: 1.纯标称值无缺失数据集 2.连续值和标称值混合且无缺失数据集 3.连续值和标称值混合,有缺失数据集 第一个算法参考了<机器学习实战>的大部分代码,

决策树算法原理

转载于:http://www.cnblogs.com/pinard/p/6050306.html (楼主总结的很好,就拿来主义了,不顾以后还是多像楼主学习) 决策树算法在机器学习中算是很经典的一个算法系列了.它既可以作为分类算法,也可以作为回归算法,同时也特别适合集成学习比如随机森林.本文就对决策树算法原理做一个总结,上篇对ID3, C4.5的算法思想做了总结,下篇重点对CART算法做一个详细的介绍.选择CART做重点介绍的原因是scikit-learn使用了优化版的CART算法作为其决策树算法

决策树算法总结

决策树算法实际就是一个不断分割训练数据集使其成为数据子集的过程.这种分类或回归模型成树形结构,这也是其被成为决策树算法的主要原因.决策树算法最主要的问题是如何分裂原始数据集使其数据集包含的类别纯度越来越高,于是前辈们引入了熵和信息增益等概念.下面来总结一下决策树算法的主要步骤: step1.计算目标属性(类别的熵): step2.选择一个属性分裂数据集,也即计算信息增益: step3.根据各属性的信息增益,选择最佳的分类属性,对数据集进行分裂: step4.判断剩余的数据集是否都属于同一类别,以

机器学习算法之决策树算法

该节主要是把<机器学习实战>书上第三章关于决策树的相关代码照样子实现了一遍.对其中一些内容作了些补充,对比ID3与C45区别,同时下载了一个大样本集实验决策树的准确率. 首先,对于决策树的原理,很多很好的博客值得一看: 从决策树学习谈到贝叶斯分类算法.EM.HMM 决策树算法总结 这两个已经详解了关于决策树的所有,慢慢品读吧. 下面是书上外加添加的部分程序,首先是tree.py里面的程序: import operator from math import log # calculate the