决策树分类..docx

实验二 决策树学习引言决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表达为一棵决策树。学习得到的决策树也能再被表达为多个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)==1WaitEs(j)~=3 Will(j)=1; elseif FS(j)==1Hun(j)==1WaitEs(j)~=3 Will(j)=1; else Will(j)=0; endend 这样就构造了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