关于决策树的介绍很多，我用sas宏写了一个决策树算法（ID3）,主要是印证一下想法。决策树作为一种非参方法，比较符合人的推理，因此很容易被理解，借助信息熵这个评判标准就可以进行迭代。
决策树可以用来判断变量的重要性，完成后可以导出规则。
从机器学习的角度来说，归纳的粒度是重要的，既要有很好的识别度（分类），又要有一定的泛化能力，因此适合的拟合水平是生长或剪枝要考虑的主要问题。
下个版本计划做的改进:
1、对连续变量进行切分点寻找
2、决策树的预剪枝规则改进（信息增益率:c4.5、记录数:过小的记录可以考虑不生长、纯度:不必非得是纯的）
3、算法运算时间的检查（本来觉得EM跑的太慢，但自己写了也发现的确比较耗时）

例子可以见youtube的这个视频（要翻墙） https://www.youtube.com/watch?v=eKD5gxPPeY0
先给两张图:我觉得图1是决策树比较清晰的一个结构，而图2对于叶子节点分类的表示也很醒目
图1、决策树的结构示例

图2、决策树叶子节点的分类表示（血槽）

以下是根据Youtube视频中提的例子进行代码实现:
图3、数据集

图4、决策树的生长




输入数据集后，使用sas宏进行实现：
主要使用两个逻辑库
1、tree用于保存迭代表(iter)以及stack表来控制迭代过程
图5.tree库

图6.iter表

图7.stack表

2、tree_tmp保存每个数据集的 _vlist表(变量列表)和_vlev表(变量水平列表)。
图8.tree_tmp库

**********************以下是主程序*****************************
第一部分：数据预处理（set_des这个宏在前面的文章里）
/*1数据集描述*/
%set_des(work,dt,10)
/*2描述修改*/
data set_des;
set set_des;
if name eq 'play' then cls_indi=.;
run;
/*3将分类变量和目标变量分别存入宏*/
%let tar=play;
proc sql noprint;
select name into :cv_list separated by ' '
from set_des
where cls_indi=1;
select distinct(nobs) into :vobs
from set_des;
quit;
/*4将数据集重新命名，以便迭代*/
data dt_1;
set dt;
keep &cv_list &tar;
run;

第二部分：初始化部分数据
/*tree库放迭代的结果*/
/*tree_tmp库放迭代的中间结果*/
/*1初始化iter表*/
%var_ent(dt_1,&tar);
data tree.iter;
length set_from set_name $ 100;
iter=1;
set_from="dt_1";
set_name="dt_1";
set_recs=symget('vobs')+0;
set_ent=symget("&tar._ent")+0;
run;
/*2初始化stack表*/
data tree.stack;
length set_from set_name var_name $ 100;
if 0 then do;
set_from='a';
set_name='a';
var_name='a';
iter=0;
set_recs=0;
p=0;
set_ent=0;
weight_ent=0;
end;
if set_from eq '' then delete;
run;
/*3创建竞争变量列表*/
proc sql noprint;
create table tree_tmp.dt_1_vlist as
select lower(name) as var_cand from sashelp.vcolumn
where libname='WORK' and memname='DT_1'
and lower(name) ne "&tar";
quit;
data tree_tmp.dt_1_vlist;
length var_cand $ 100;
set tree_tmp.dt_1_vlist;
run;

第三部分：迭代
/*options mprint mlogic symbolgen;*/
/*限定迭代次数，进行迭代*/
%macro split(times);
/*根据iter表进行迭代*/
%do iter=1 %to ×
proc sql noprint;
select count(*) into :_sets_tem
from tree.iter
where iter=&iter;
quit;
%let sets=%sysfunc(left(&_sets_tem));
%if &sets > 0 %then %do;
proc sql noprint;
select set_name into :set1-:set&sets
from tree.iter
where iter=&iter;
quit;
/*对本轮迭代中的数据集进行遍历*/
%do xi=1 %to &sets;
/*获取现有变量的水平- 拆分后有些变量水平可能消失了*/
/*查询当前数据集的变量水平，使用当前循环的数据集作为参数
并且查询了以数据集名字命名的竞争列表set_vlist
*/
%cur_lev(&&set&xi);
/*cur_lev生成了以数据集命名的水平列表 set_lev*/
/*对数据集的所有变量及水平遍历，放入stack表*/
%vvar(&&set&xi,&iter);
%cp(&&set&xi,&iter);
%end;
%end;
%end;
%mend;
%split(5)

**********************相关的宏及解释*************************
宏1:vvar 对所有变量遍历
/*数据集变量_水平 vvar*/
/*1遍历所有变量*/
/*参数：迭代次数 数据集*/
%macro vvar(set,iter,vlib=tree_tmp);
/*先查询该数据集的竞争变量列表*/
proc sql noprint;
select count(*) into :_vars_tem
from &vlib..&set._vlist;
quit;
%let vars=%sysfunc(left(&_vars_tem));
/*如果竞争变量表不为空，则执行变量的遍历*/
%if &vars > 0 %then %do;
proc sql noprint;
select var_cand into :var1-:var&vars
from &vlib..&set._vlist;
quit;
%do j=1 %to &vars;
/*对变量的每个水平进行遍历*/
/*参数传递：迭代次数 数据集名 变量名*/
%vlev(&set,&&var&j,&iter);
%end;
%end;
%mend;


宏2：vlev 对变量的所有水平遍历
/*遍历变量的水平*/
%macro vlev(set,var,iter,vlib=tree_tmp);
/*遍历当前变量的所有水平*/
proc sql noprint;
select count(*) into :_lev_tem
from &vlib..&set._lev
where var_cand="&var"
;
quit;
%let lev=%sysfunc(left(&_lev_tem));
proc sql noprint;
select level into :lev1-:lev&lev
from &vlib..&set._lev
where var_cand="&var"
;
quit;
/*生成niter=iter+1*/
%let niter_tem=%eval(&iter+1);
%let niter=%sysfunc(left(&niter_tem));
/*根据变量水平生成一些数据集*/
%do k=1 %to &lev;
/*命名分裂数据集*/
data &var.&&lev&k.._&niter.;
set &set nobs=mobs;
/*获取分裂前数据集的记录数*/
if _n_=1 then call symput('mobs',mobs);
&var._s='_'||left(&var);
if &var._s="&&lev&k";
run;
/*同步生成数据集的变量列表：从分裂前数据集继承*/
data &vlib..&var.&&lev&k.._&niter._vlist;
set &vlib..&set._vlist;
if var_cand="&var" then delete;
run;
/*获取分裂数据集的记录数*/
proc sql noprint;
select count(*) into :_setobs
from &var.&&lev&k.._&niter.;
quit;
/*获取分裂数据集的熵*/
/*tar是全局宏变量，且不会和局部冲突*/
%var_ent(&var.&&lev&k.._&niter.,&tar);
data stack_tem;
length set_from set_name var_name $ 100;
iter=&iter;
set_from=symget('set');
set_name="&var.&&lev&k.._&niter.";
set_recs=symget('_setobs')+0;
p=&_setobs/&mobs;
set_ent=symget("&tar._ent")+0;
weight_ent=p*set_ent;
var_name=symget("var");
run;
/*将分裂数据集的信息写入stack表中*/
proc append base=tree.stack data=stack_tem;
run;
%end;
%mend;

宏3：cur_lev 生成当前数据集的水平变量（随着裂变有些变量水平可能会消失）
/*cur_lev*/
%macro cur_lev(set,vlib=tree_tmp);
/*先查询该数据集的竞争变量列表*/
proc sql noprint;
select count(*) into :_vars_tem
from &vlib..&set._vlist;
quit;
%let vars=%sysfunc(left(&_vars_tem));
/*如果竞争变量表不为空，则执行变量的遍历*/
%if &vars > 0 %then %do;
proc sql noprint;
select var_cand into :var1-:var&vars
from &vlib..&set._vlist;
quit;
%do i=1 %to &vars;
data _tmp&i;
length level $ 100;
set &set(keep=&&var&i);
level='_'||&&var&i;
var_cand="&&var&i";
keep var_cand level;
run;
%end;
data &vlib..&set._lev;
length var_cand $ 100;
set _tmp1-_tmp&vars;
run;
%end;
%dsort(&vlib..&set._lev, var_cand level);
%mend;


宏4：cp 判断继续迭代或终止
/*判别宏*/
/*对于每个数据集，在循环*/
%macro cp(set,iter);
/*取出数据集根据所有可能拆分的进行分析*/
data comp1;
set tree.stack;
/*取出本轮的数据集*/
if iter=&iter and set_from="&set";
run;
/*sort是对sort过程简写的宏*/
%sort(comp1,var_name);
/*根据变量进行熵的汇总*/
data comp2;
set comp1;
by var_name;
if first.var_name then ent_sum=0;
ent_sum+weight_ent;
if last.var_name  then output;
keep set_from var_name iter ent_sum;
run;
/*取出熵最小的变量（则熵增最大）*/
%sort(comp2,iter ent_sum)
data tem;
length set_from var_name $ 100;
set comp2;
by iter;
if first.iter;
run;
/*将本次循环胜利的变量输入win_var保存*/
proc append base=tree.win_var data=tem;
run;
/*将本次所有循环的变量都放到detail中*/
data tree.win_vars_detail;
set comp2;
run;
/*将数据集的熵和分裂后的熵比较，如果符合条件则写入iter表，进入下一次迭代*/
proc sql noprint;
create table tem1 as
select a.var_name,b.set_ent-a.ent_sum as ent_gap
from tem as a left join
tree.iter as b on a.set_from=b.set_name;
quit;
/*写入宏变量*/
data _null_;
set tem1;
call symput('ent_gap',ent_gap);
call symput('win_var',var_name);
run;
/*纯子集的熵增为0*/
%if &ent_gap > 0.001 %then %do;
data tem2;
set tree.stack(where=(set_from="&set" and var_name="&win_var"));
iter=iter+1;
keep set_from set_name iter set_recs set_ent;
run;
proc append base=tree.iter data=tem2;
run;
%end;
%mend;

************************以下是结尾及一些解释***************************
解释:iter表中的结果可以构成一个树状结构，每个数据集都有其父节点名称，所以可以根据迭代层级从下往上构建数。
另外这个例子中可以划分成纯子集，所以信息增益的阈值随便设一个大于0的数就可以，但是实际上这样容易过分生长。
结果：根据例子，D1-D14是测试集，最后有D15 Outlook(Rain) Humidity(High) Wind(Weak) Play(?)，预测play就是一个决策过程。
根据前面得到了决策路径，D15的outlook变量是第一重要的，所以先根据它转到了rain这个分支，接下来wind变量是最重要的，根据wind-weak直接可以得到类标签（yes），所以猜测John会去玩。
这个例子还有一些简化的地方，outlook,humidity,wind三个变量基本上认为是可以完全描述事件的三个正交变量，事实上获得这个条件本身就是不容易的。
图9.John的决策路径