实验二决策树学习
引言
决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表达为一棵决策树。学习得到的决策树也能再被表达为多个if-then的规则，以提高可读性。这种学习算法是最流行的归纳推理算法之一，已经被成功地应用到从学习医疗诊断到学习评估贷款申请的信用风险的广阔领域。本文用决策树学习算法解决饭店排队问题，学习判断什么情况下在饭店就餐需要等待的规则或函数。
问题描述
饭店排队问题的目标属性为：WillWait
判定属性有10个，依次为：
Alternate：附近是否有一个合适的候选饭店。
Bar：饭店中是否有舒适的酒吧区域值得排队等待。
Fri / Sat：在星期五和星期六为真。
Hungry：是否饿了。
Patrons：饭店中有多少人（其值可取None、Some和Full）。
Price：饭店价格区间（¥，¥ ¥ ，¥ ¥ ¥ ）。
Raining：天是否下雨。
Reservation：是否预定。
Type：饭店类型（French，Italian，Thai，burger）。
WaitEstimate：主人对等待的估计（0-10分钟，10-30，30-60，或>60）
生成学习所需要的训练样例，分析训练样例数目与学习精度的关系以及训练样例的分布与学习精度的关系；对判定属性为连续值或者判定属性缺少部分值进行处理，解决过度拟合问题。
模型建立与求解
首先将判断属性值离散化，数值化，对于只有两个取值的属性，赋值为0和1，对取值为三个值的属性，赋值为0，1，2，对取值为四个值的属性，赋值为0，1，2，3。利用随机数生成器随机生成各个判定属性的属性值，并人为设定条件，给出每组特征的目标属性值，取样例的一部分作为训练样例，剩余部分作为测试样例，利用决策树算法对测试样例的目标属性值进行预测并将其与人为判定的目标属性值进行比较，得出决策树算法目标属性判定的准确率，这里用的是C4.5决策树算法来进行实验，模型求解是通过matlab实现的。
仿真实验与结果分析
1.构造训练样例和测试样例
对于10个判定属性，用rand（）函数随机生成m个属性值，然后根据生成的属性值，人为判定目标属性值，这里人为判定的条件为：
for j=1:m
if Alter(j)==1 && Bar(j)==1 && Hun(j)==1 && Pat(j)~=2
Will(j)=1;
elseif Res(j)==1&&WaitEs(j)~=3
Will(j)=1;
elseif FS(j)==1&&Hun(j)==1&&WaitEs(j)~=3
Will(j)=1;
else
Will(j)=0;
end
end
这样就构造了m个经过人为判定的一组训练样例，为了更好地
检验算法，这里又构造了n个完全随机的训练样例，作为噪声训练样例与之前经过人为判定的m个训练样例一起作为实验的训练样例。用同样的方法构造w个测试样例。
2.算法测试
1）属性均为离散，m=100，n=10，w=1000-10000
这里取100个经过人工判定的训练样例，10个噪声训练样例共110个样例作为训练样例，测试样例w以1000的间隔分别取1000-10000个，其中每个w取10组数据，通过取平均值计算算法准确性，结果如下图：
可以看出：虽然此时测试样例的数目为1000-10000，但算法的准确率都在0.8左右，说明在训练样例一定的情况下，算法的准确率不
因测试样例数目而改变。
2）属性均为离散，m=10-200，n=0，w=10000
这里取10000个经过人工判定的测试样例，训练样例m以10的间隔分别取10-200个，其中每个m取50组数据，通过取平均值计算算法准确性，结果如下图：
可以看出：此时算法的准确率随着训练样例数目的增加而提高。
3）属性均为离散，m=1000-20000，n=0，w=10000
这里取10000个经过人工判定的测试样例，训练样例m以1000的间隔分别取1000-20000个，其中每个m取50组数据，通过取平均值计算算法准确性，结果如下图：
可以看出：此时算法的准确率随着训练样例数目的增加呈现波动，尤其是当训练样例数目大于16000时，准确率出现下降，这说明当训练样例过多时，可能出现过拟合现象，当然也有可能是因为生成的随机数的问题。
4）属性均为离散，m=1000，n=100-2000，w=10000
这里取10000个经过人工判定的测试样例，1000个经过人工判定的训练样例，噪声样例数量以100的间隔分别取100-2000，其中每个n取50组数据，通过取平均值计算算法准确性，结果如下图：
可以看出：此时算法的准确率随着噪声数量的增加而出现明显的下降。
5）属性WaitEstimate为连续（取0-100的随机数值），m=100-2000，n=0,w=10000
这里取10000个经过人工判定的测试样例，训练样例数量以100的间隔分别取100-2000，其中每个m取10组数据，通过取平均值计算算法准确性，结果如下图：
可以看出：此时算法的准确率总体上时随着训练样例数目的增多而增大的，但是由于属性值是由随机数生成的原因，导致个别区域的准确率有一定波动。此外，还可以发现此时算法的准确率只在70%左右，且算法的运行需要较长时间，这应该是因为有连续属性WaitEstimate的缘故，算法需要将连续属性进行处理，通过划分将连续属性分成不同的段，从而将其离散化，这个过程应该会耗费比较长的时间，至于算法准确率不高可能是因为此时训练样例的数目还是偏少，但实验中再增加训练样例数量会带来更大的时间开销。
结语
通过此次实验，让我对决策树学习算法有了更深的了解，实验研究了训练样例的生成问题，分析了训练样例数量、训练样例分布与学习精度的关系，算法也解决了属性值连续的问题，且对于过度拟合问
