一般地，一个决策树包含一个根节点，若干个内部节点和若干个叶节点，叶结点对应决策结果，其他每个节点对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集，从根节点到每个叶节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强，处理未见实例能力强的决策树。

信息熵

信息熵是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占比例为pk(1,2,..|y|),则D的信息熵定义为

其中Ent(D)的值越小，则D的纯度越高。

信息增益

假定离散属性a有V个可能的取值a1,a2,...,aV,若使用a来对样本集D进行划分，则会产生V个分支节点，其中第v个分支节点包含了D中所有在属性a上取值为av的样本，记为Dv,根据信息熵的公式，在考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重|Dv|/|D|,即样本数越多的分支节点的影响越大，于是可计算出用属性a对样本集D进行划分所获得的”信息增益”。

一般而言，信息增益越大，则意味着使用属性a来进行划分所得的”纯度提升”越大。因此，我们可以用信息增益来进行决策树的划分属性选择。

实例分析

以下表的数据为例：其中有17个训练正例，学习目标是预测是不是好瓜的决策树。分类目标|Y|=2

信息熵计算得

上述实现代码为

close all;

clear all;

clc;

data = csvread('watermelon2.0.csv');

InforGain = gain(data);

function InforGain = gain(data)

[m, n] = size(data);

InforGain = zeros(n-1,2);

labels = data(:,n);

for i=1:n

tmp{i} = [];

percen{i} = [];

col = data(:,i);

unicol = unique(col);

%计算每一列有几类，并把每一类的信息熵和比例存储起来

for j = 1:length(unicol)

num = length(find(col==unicol(j)));

pnum = length(find(col==unicol(j) & labels == 1));

rate = pnum/num;

if i==7

rate = num/length(labels);

end

gain = -(rate*log2(rate)+(1-rate)*log2(1-rate));

tmp{i}=[tmp{i} gain];

percen{i}=[percen{i} num/length(col)];

end

end

%整体信息熵

InforEntropy = tmp{length(tmp)}(1);

%将NAN转化为0

for i = 1:length(tmp)

tmp{i}(isnan(tmp{i})) = 0;

%disp(tmp{i});

end

%求每一个属性列的信息增益

for i = 1:length(percen)-1

InforGain(i,:) = [i,roundn(InforEntropy-sum(tmp{i}.*percen{i}),-3)];

disp(InforEntropy-sum(tmp{i}.*percen{i}));

end

11.2.3  处理增益和干扰容限

1．处理增益Gp

在扩频系统中，传输信号经过扩频和解扩的处理，系统的抗干扰性能得到提高，这种扩频处理得到的好处，称之为扩频系统的处理增益，其定义为接收相关处理器输出与输入信噪比的比值，即

由此可见，直扩系统的处理增益为扩频信号射频带宽与传输的信息带宽的比值，或为伪随机码速率与信息速率的比值，即直扩信号的扩频倍数。在一般情况下，发送信息的带宽是不变的，要提高扩频系统的抗干扰能力，就应该提高扩频系统的处理增益，即提高扩频用的伪随机码的速率。

当处理增益提高到一定程度时，不能再靠提高伪随机码速率的方法来提高系统的处理增益，而应考虑用别的办法，比如可以降低信息速率，而且可能更为有效一些。

2．干扰容限Mj

所谓干扰容限，是指在保证系统工作正常的条件下，接收机能够承受的干扰信号比有用信号高出的分贝数。用Mj表示

式中 为系统内部损耗； 为系统正常工作时要求的最小输出信噪比； 即系统的处理增益。

干扰容限直接反映了扩频系统接收机可能抵抗的极限干扰强度，即只有当干扰机的干扰功率超过干扰容限时，才能对扩频系统形成干扰。因而干扰容限往往比处理增益更确切地反映系统的抗干扰能力。

3．码分多址

多址接入或多址联接是多用户无线通信网中按用户地址进行连接的问题。在移动通信系统中，基站覆盖区内存在许多移动台，移动台必须能识别基站发射的信号中哪一个是发给自己的信号，基站也必须从众多的移动台发射信号中识别出每一个移动台所发射的信号。由此可见，多址(接入)技术在数字蜂窝移动通信中占有重要的地位。

多址接入方式的数学基础是信号的正交分割原理。无线电信号可以表达为时间、频率和码型的函数，即可写作：

其中是码型函数， 是时间 和频率 的函数。

当以传输信号的载波频率不同来区分信道建立多址接入时，称为频分多址方式(FDMA)；当以传输信号存在的时间不同来区分信道建立多址接入时，称为时分多址方式(TDMA)；当以传输信号的码型不同来区分信道建立多址接入时，称为码分多址方式(CDMA)。图11-4分别给出了N个信道的FDMA、TDMA和CDMA的示意图。

CDMA(Code Division Multiple Access)是使用一组正交(或准正交)的伪随机噪声(PN)序列(简称伪随机码)通过相关处理来实现多个用户共享空间传输的频率资源和同时入网接续的功能，即码分多址。CDMA只能由扩频调制来完成，而扩频调制并不意味着CDMA。

CDMA的特点包括以下几点：

CDMA系统的许多用户共享同一频率。

通信容量大。

由于信号被扩展在一较宽频谱上，因而可以减小多径衰落。

在CDMA系统中，信道数据速率很高。

平滑的软切换和有效的宏分集。

低信号功率谱密度。

图11-5为DS-CDMA系统的原理图。

各用户的数据字符先使用各自的特征波形进行扩频，然后用载频的调频信号对扩频信号进行调制，再发射到无线信道中去。因此，接收信号可表示为：

其中 为第i个用户的数据信息，取值 1； 为第i个用户的扩频波形，取值 1； 为第i个用户的载波幅值； 为第i个用户的载波的随机相位，在 内均匀分布； 为第i个用户的随机时延，在 内均匀分布； 为码元间隔； 为加性高斯白噪声。

假定针对第 个用户的数据字符进行解扩和解调。为此，接收信号 分别乘以 和 。令接收机与第 个用户的信号正确同步，则可以求得相关接收机的输出 。

【责任编辑：董书 TEL：(010)68476606】

点赞 0

使用数据集 西瓜数据集3

共8属性 6离散2连续 离散属性用1，2，3代表不同的取值 因为实在不太会用Matlab处理文本(真想趁才刚学转头去学Python)

编号

1色泽

2根蒂

3敲声

4纹理

5脐部

6触感

1

青绿

蜷缩

浊响

清晰

凹陷

硬滑

2

乌黑

稍蜷

沉闷

稍糊

稍凹

软粘

3

浅白

硬挺

清脆

模糊

平坦

无

由于不知道去哪弄用文本画树的工具，所以只能用matlab自带的树形结构，只有形状，具体信息还是要去看代码运行的结果，不过重点是明白算法是怎么回事！

这个是6离散属性生成的决策树，和书上的一样 就是丑了点

这个是6离散2连续属性生成的决策树，这个还不错，可以看出和书上一样！具体划分保存在了treeres中

由于第一幅图节点太多，这里只贴第二幅图的treeres属性

– 第一行 代表每个节点(先根遍历来编号)

– 第二行 非叶节点-该节点最优划分属性 叶节点-分类属性

– 第三行 父节点划分到此节点用的属性

– 第四行 如果是连续参数，则记录阀值

–

1

2

3

4

5

6

7

8

‘纹理’

‘密度’

‘好瓜’

‘坏瓜’

‘触感’

‘坏瓜’

‘好瓜’

‘坏瓜’

[]

‘清晰’

‘小于’

‘大于’

‘稍糊’

‘硬滑’

‘软粘’

‘模糊’

[]

[]

0.381

0.381

[]

[]

[]

[]

先是主程序的代码，主要做了一些初始化和最后的树形显示

生成决策树从TreeGenerate进入

%{

x:样本属性 连续变量直接用数值,离散变量用1，2，3区别

y:样本分类值 1-好 2-不好

tree:生成的树形结构，用数组表示 按先根遍历编号 值为父节点编号 1为根节点

treeleaf:标记是否为叶子节点

treeres:每组3个变量

1:如果是叶子节点则记录分类 如果是非叶节点记录当前节点的分类属性

2:离散属性直接记录父节点分类的具体属性 连续属性1-小于 2-大于

3:如果是连续属性，记录阀值，离散属性为0

ptr:节点数目累加变量

%}

global x y fenlei1 fenlei xigua;

global tree treeleaf treeres ptr;

x = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A1:Q8');

y = xlsread('C:\Users\icefire\Desktop\ml\西瓜3.xlsx', 'sheet1', 'A9:Q9');

%西瓜属性的中文标识

fenlei1={'色泽', '根蒂', '敲声', '纹理', '脐部' ,'触感','密度','含糖率'};

fenlei={

'青绿','蜷缩', '浊响', '清晰', '凹陷', '硬滑','小于','小于';

'乌黑', '稍蜷', '沉闷', '稍糊', '稍凹', '软粘','大于','大于';

'浅白', '硬挺', '清脆', '模糊', '平坦', '无','无','无';

};

xigua = {'好瓜','坏瓜'};

[m,n]=size(y);

%为set集合提前分配空间 集合中存放所有样本的编号

for i=n:-1:1

set(i) = i;

end

%为tree相关变量提前分配空间

tree=zeros(1,100);

treeleaf=zeros(1,100);

treeres=cell(3,100);

ptr = 0;

%{

手动设置的变量:修改输入数据时要收到修改

pf：属性的编号，按顺序编号

pu：属性是连续还是离散的0-离散 1-连续

pt：属性对应的分类数，连续属性用不着(可以设为0)

%}

pf=[1 2 3 4 5 6 7 8];

pu=[0 0 0 0 0 0 1 1];

pt=[3 3 3 3 3 2 0 0];

%主递归程序

TreeGenerate(0,set,pf,pu,pt);

%绘制树形 仅有树形

treeplot(tree(1:ptr));

%{

parent:父节点编号

curset:当前的样本编号集合

pf:当前的属性编号集合

%}

function TreeGenerate(parent,curset,pf,pu,pt)

global x y xigua fenlei1 fenlei;

global tree treeleaf treeres ptr;

%新增一个节点，并记录它的父节点

ptr=ptr+1;

tree(ptr)=parent;

cur = ptr;

%递归返回情况1:当前所有样本属于同一类

n = size(curset);

n = n(2);

%计算当前y的取值分类及各有多少个 如果只有一类表示属于同一类

cury=y(curset); %通过当前样本编号从所有样本中选出当前样本

y_data=unique(cury); %集合去重

y_nums=histc(cury,y_data); %统计各个取值各多少个

if(y_nums(1)==n)

treeres{1,ptr} = xigua{y_data};

treeleaf(cur) = 1;

return;

end

%递归返回情况2:

属性已经全部划分还有不同分类的样本，或者所有样本属性一致但是分类不同(这时就是有错误的样本)

pfn=size(pf); %记录当前属性个数

tmp_para = x(pf,curset(1));

f = 1;

classy = y(curset(1));

sum=zeros(1,2);

for i=1:n

if isequal(tmp_para , x(pf,curset(i)))

t = (classy == y(curset(i)));

sum(t) = sum(t)+1;

else

f=0;

break;

end

end

if(f == 1 || pfn(2) == 0)

treeres{1,cur} = xigua{(sum(2)>=sum(1))+1};

treeleaf(cur) = 1;

return;

end

%主递归

%实现了4个最优属性选择方法,使用了相同的参数与输出:信息增益，增益率，基尼指数，对率回归

%具体参数介绍间函数具体实现

%因为是相同的参数与输出，直接该函数名就能换方法

[k, threshold] = entropy_paraselect(curset,pf,pu);

curx = x(pf,:); %通过属性编号从样本总体中选取样本(已经分类的离散属性不再需要)

p_num=pf(k); %记录当前属性的具体编号

treeres{1,cur} = fenlei1{p_num};%记录当前节点的分类属性

%离散与连续属性分别处理

if(pu(k)) %连续属性

%连续属性只会分为两类 大于阀值一类 小于阀值一类 分类后继续递归

num = [1 1];

tmp_set = zeros(2,100);

for i=1:n

if(curx(k,curset(i))>=threshold)

tmp_set(1,num(1))=curset(i);

num(1) = num(1)+1;

else

tmp_set(2,num(2))=curset(i);

num(2) = num(2)+1;

end

end

for i=1:2

%由于用数组存编号，会有0存在，将样本分开后与当前的样本求交集 把0去掉

ttmp_set = intersect(tmp_set(i,:),curset);

treeres{2,ptr+1} = fenlei{i,p_num}; %记录分类具体属性

treeres{3,ptr+1} = threshold; %记录阀值

TreeGenerate(cur,ttmp_set,pf,pu,pt);

end

else

%离散型分类要按每个取值分，就算某个取值下样本为0，也要标记为当前样本下最多的一个分类

tpt=pt(k); %该属性对应多少情况

pf(:,k)=[]; %离散属性只分一次，用完就从集合中去掉

pu(:,k)=[];

pt(:,k)=[];

%记录每种属性取值下对应的正反例各是多少

num = ones(1,tpt);

tmp_set = zeros(tpt,100);

n=size(curset);

for i=1:n(2)

tmp_set(curx(k,curset(i)),num(curx(k,curset(i))))=curset(i);

num(curx(k,curset(i))) = num(curx(k,curset(i)))+1;

end

%然后按每种取值递归

for i=1:tpt

ttmp_set = intersect(tmp_set(i,:),curset);

n = size(ttmp_set);

%如果该取值下没有样本，不进行递归，标记为当前样本下最多的一个分类

if(n(2)==0)

ptr=ptr+1;

tree(ptr)=cur;

treeres{1,ptr} = xigua{(y_nums(2)>y_nums(1))+1};

treeres(2,ptr) = i;

treeres{2,ptr} = fenlei{i,p_num};

else

treeres{2,ptr+1} = fenlei{i,p_num}; %记录分类具体属性

TreeGenerate(cur,ttmp_set,pf,pu,pt);

end

end

end

end

%{

信息增益选择

curset:当前样本集合

pf：当前属性的编号

pu：当前属性是连续还是离散的0-离散 1-连续

输出

n：最优属性

threshold:连续属性返回阀值

%}

function [n, threshold] = entropy_paraselect(curset,pf,pu)

global x y;

%通过样本编号与属性获取当前需要的样本

curx = x(pf,curset);

cury = y(curset);

pn = size(pf); %剩余属性数

all = size(cury); %当前样本总数

max_ent = -100; %为ent设初值，要最大值，所以设为一个很小的数

minn=0; %记录最优的属性编号

threshold = 0;

for i=1:pn(2)

if(pu(i) == 1)%连续性变量 %具体方法书上有

con_max_ent = -100;

con_threshold = 0;

xlist = sort(curx(i,:),2);

%计算n-1个阀值

for j=all(2):-1:2

xlist(j) = (xlist(j)+xlist(j-1))/2;

end

%从n-1个阀值中选最优 (循环过程中ent先递减后递增 其实只要后面的ent比前面的大就可以停止循环)

for j=2:all(2)

cur_ent = 0;

%计算各类正负例数

nums = zeros(2,2);

for k=1:all(2)

nums((curx(i,k)>=xlist(j))+1,cury(k)) = nums((curx(i,k)>=xlist(j))+1,cury(k)) + 1;

end

%计算ent 连续属性只分两种情况

for k=1:2

if(nums(k,1)+nums(k,2) > 0)

p=nums(k,1)/(nums(k,1)+nums(k,2));

cur_ent = cur_ent + (p*log2(p+0.00001)+(1-p)*log2(1-p+0.00001))*(nums(k,1)+nums(k,2))/all(2);

end

end

%记录该分类最优取值

if(cur_ent>con_max_ent)

con_max_ent = cur_ent;

con_threshold = xlist(j);

end

end

%如果该最优取值比当前总的最优还要优，记录

if(con_max_ent > max_ent)

max_ent=con_max_ent;

minn = i;

threshold = con_threshold;

end

else

%离散型

%除了分类数多了 其他一样

cur_ent = 0;

set_data=unique(curx(i,:));

setn=size(set_data);

nums = zeros(10,2);

for j=1:all(2)

nums(curx(i,j),cury(j))=nums(curx(i,j),cury(j))+1;

end

for j=1:setn(2)

if((nums(set_data(j),1)+nums(set_data(j),2))>0)

p=nums(set_data(j),1)/(nums(set_data(j),1)+nums(set_data(j),2));

cur_ent = cur_ent +(p*log2(p+0.00001)+(1-p)*log2(1-p+0.00001))*(nums(set_data(j),1)+nums(set_data(j),2))/all(2);

end

end

if(cur_ent > max_ent)

minn = i;

max_ent = cur_ent;

end

end

end

n = minn;

threshold = threshold * pu(n);

end

参考http://blog.csdn.net/icefire_tyh/article/details/52081556