如何修改基本决策树算法

1、如何修改基本决策树算法，以便考虑每个广义数据元组(即每一行)的count?使用修改过的算法，构造给定数据的决策树。给定一个数据元组，它的属性department,age和salary的值分别为“systems”“2630”，和“46K50K”该元组status的朴素贝叶斯分类是什么？为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。使用上面得到的多层前馈神经网络，给定训练实例(sales,senior,3135,46K50K),给出后向传播算法一次迭代后的权重值。指出你使用的初始权重和偏倚以及学习率。解答：如何修改基本决策树算法，以便考虑每个广义数据元组(即每一行)的count？使用

2、修改过的算法，构造给定数据的决策树。给定一个数据元组，它的属性department，age和salary的值分别为“systems”，“2630”，和“46K50K”。该元组status的朴素贝叶斯分类是什么？解一：设元组的各个属性之间相互独立，所以先求每个属性的类条件概率：P(systems|junior)=(20+3)/(40+40+20+3+4+6)=23/113;P(26-30|junior)=(40+3+6)/113=49/113；P(46K-50K|junior)=(20+3)/113=23/113；*.*X=(department=system,age=2630,salary=4

3、6K50K)；P(Xljunior)=P(systemsljunior)P(26-30ljunior)P(46K-50Kljunior)=23x49x23/1133=25921/1442897=0.01796；P(systems|senior)=(5+3)/(30+5+3+10+4)=23/52;P(26-30lsenior)=(0)/53=0;P(46K-50Klsenior)=(30+10)/52=40/52；*.*X=(department=system,age=2630,salary=46K50K)；P(Xlsenior)=P(systemslsenior)P(26-30lsenior

4、)P(46K-50Klsenior)=0;P(junior)=113/165=0.68；*.*P(senior)=52/165=0.32；P(Xljunior)P(junior)=0.01796X0.68=0.01221280=0=P(Xlsenior)P(senior)；所以：朴素贝叶斯分类器将X分到junior类。解二：设元组的各属性之间不独立，其联合概率不能写成份量相乘的形式。所以已知：X=(department=system,age=2630,salary=46K50K)，元组总数为：30+40+40+20+5+3+3+10+4+4+6=165。先验概率：当status=senior时

5、，元组总数为：30+5+3+10+4=52，P(senior)=52/165=0.32；当status=junior时，元组总数为：40+40+20+3+4+6=113，P(junior)=113/165=0.68；因为status=senior状态没有对应的age=2630区间，所以：P(Xlsenior)=0；因为status=junior状态对应的partment=systems、age=2630区间的总元组数为：3，所以：P(Xljunior)=3/113；因为：P(Xljunior)P(junior)=3/113X113/165=0.0180=P(Xlsenior)P(senior)

6、；所以：朴素贝叶斯分类器将X分到junior类。为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。使用上面得到的多层前馈神经网络，给定训练实例(sales,senior,3135,46K50K),给出后向传播算法一次迭代后的权重值。指出你使用的初始权重和偏倚以及学习率。7.3.1判定树归纳7.3.1判定树归纳判定树归纳的基本算法是贪心算法，它以自顶向下递归的划分-控制方式构造判定树。算法在图7.3中，是一种著名的判定树算法ID3版本。算法的扩展将在7.3.2到7.3.6小节讨论。算法的基本策略如下：树以代表训练样本的单个结点开始（步骤1）。如果样本都在同一个类，则该结点成为树叶，并用

7、该类标号（步骤2和3）。否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，所有的属性都是分类的，即离散值。连续属性必须离散化。对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。递归划分步骤仅当下列条件之一成立停止：（a）给定结点的所有样本属于同一类（步骤2和3）。（b）没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多

8、数表决（步骤5）。这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结点样本的类分布。（c）分枝test_attribute=a没有样本（步骤11）。在这种情况下，以samples中i的多数类创建一个树叶（步骤12）。属性选择度量在树的每个结点上使用信息增益度量选择测试属性。这种度量称作属性选择度量或分裂的优劣度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或“不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目最小，并确保找到一棵简单的（但不必是最简单的）树。

9、设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类C（i=i1,.,m）。设s.是类C中的样本数。对一个给定的样本分类所需的期望信息由下式给出：ii1（s，s，,S）二乙p.log（p.）12mi2ii=1（7.1）其中，p.是任意样本属于C.的概率，并用s./s估计。注意，对数函数以2为底，因为iii信息用二进位编码。设属性A具有v个不同值何，a。可以用属性A将S划分为v个子集、，S；1v1v其中，S.包含S中这样一些样本，它们在A上具有值a.。如果A选作测试属性（即，最好的jj划分属性），则这些子集对应于由包含集合S的结点生长出来的分枝。设s.是子集S.中类.jjC.的

10、样本数。根据A划分子集的熵或期望信息由下式给出：.vS+SE（A）=工1jj（s,.,s）S1jmjj=1（7.2）S12=4S22=0s+.+s项1jmj充当第j个子集的权，并且等于子集(即，A值为a.)中的样本个数除sj以S中的样本总数。熵值越小，子集划分的纯度越高。注意，对于给定的子集S.，jI(s,S，,S)=-p.log(p.)1j2jmjij2iji=1(7.3)s其中，Pj=茴，是Sj中的样本属于q的概率。j在A上分枝将获得的编码信息是Gain(A)=I(s,s,.,s)-E(A)12m(7.4)换言之，Gain(A)是由于知道属性A的值而导致的熵的期望压缩。算法计算每个属性的信

11、息增益。具有最高信息增益的属性选作给定集合S的测试属性。创建一个结点，并以该属性标记，对属性的每个值创建分枝，并据此划分样本。例7.2判定树归纳。表7.1给出了取自AllElectronics顾客数据库数据元组训练集。(该数据取自Qui86)。类标号属性buys_computer有两个不同值(即,yes,no)，因此有两个不同的类(m=2)。设类q对应于yes，而类C2对应于no。类yes有9个样本，类no有5个样本。为计算每个属性的信息增益，我们首先使用(7.1)式，计算对给定样本分类所需的期望信息：9955I(s,s)=I(9,5)=-9log9log=0.940121421414214表

12、7.1AllElectronics顾客数据库训练数据元组RIDageincomestudentcreditratingClass:buyscomputer1=30highnofairno240mediumnofairyes540lowyesfairyes640lowyesexcellentno731.40lowyesexcellentyes8=30mediumnofairno940mediumyesfairyes1140mediumnoexcellentno下一步，我们需要计算每个属性的熵。让我们从属性age开始。我们需要观察age的每个样本值的yes和no分布。我们对每个分布计算期望信息。对

13、于age=”=30”对于age=”31.40”对于age=”40”s=211S21=3I(S115S21)=0.971I(s,s)=01222I(s,s)=0.971使用(7.2)式，如果样本按age划分，对一个给定的样本分类所需的期望信息为:545E(age)=I(s,s)+I(s,s)+I(s,s)=0.694141121141222141323因此，这种划分的信息增益是gain(age)=I(,s)一E(age)=0.246类似地，我们可以计算Gain(income)=0.029,Gain(student)=0.151和Gain(credit_rating)=0.048。由于age在属性

14、中具有最高信息增益，它被选作测试属性创建一个结点，用age标记，并对于每个属性值，引出一个分枝。样本据此划分，如图7.4所示。注意，落在分区age=“31.40”的样本都属于同一类。由于它们都属于同一类yes,因此要在该分枝的端点创建一个树叶，并用yes标记。算法返回的最终判定树如图7.2所示。mcLimestudentcreditratingclasshighhighmediumlowmedium1LUnonoyesyesfail-excellentfanfanexcellenty已呂yesiiLCumestudentcreditratingclassmediumlowlowmediumme

15、diumyesy已呂y已呂fairfairexcellentfairexcellentyesjresyesiiLCumestudentcreditratingclasshighlowmediuinhighnoyes1LUyesfanexcellentexcellentfany已呂yesyesyes图7.4:属性age具有最高信息增益，因此成为判定树根的测试属性。由每个age引出分枝，样本据此划分总而言之，判定树归纳算法已在广泛的应用领域用于分类。这种系统不使用领域知识判定树归纳的学习和分类步骤通常很快。7.4.2朴素贝叶斯分类朴素贝叶斯分类，或简单贝叶斯分类的工作过程如下：1-每个数据样本用一

16、个n维特征向量X=X1,x2,xn表示描述由属性A1,A2,An对样本的*个度量。假定有m个类C,CC。给定一个未知的数据样本X(即，没有类标号)，分类法将预测X属于具有最高后验12m概率(条件X下)的类。即，朴素贝叶斯分类将未知的样本分配给类C,当且仅当：iP(CIX)P(CIX)1jP(XIC)P(C)1jmj丰i.iijj换言之，X被指派到其P(XIC.)P(C.)最大的类c。iii“贝叶斯分类的效率如何？”理论上讲，与其它所有分类算法相比，贝叶斯分类具有最小的出错率。然而，实践中并非总是如此。这是由于对其应用的假定(如，类条件独立性)的不正确性，以及缺乏可用的概率数据造成的。然而，种种

17、实验研究表明，与判定树和神经网络分类算法相比，在某些领域，该分类算法可以与之媲美。贝叶斯分类还可以用来为不直接使用贝叶斯定理的其它分类算法提供理论判定。例如，在某种假定下，可以证明正如朴素贝叶斯分类一样，许多神经网络和曲线拟合算法输出最大的后验假定。例7.4使用朴素贝叶斯分类预测类标号:给定与例7.2判定树归纳相同的训练数据，我们希望使用朴素贝叶斯分类预测一个未知样本的类标号。训练数据在表7.1中。数据样本用属性age,income,student和credit_rating苗述。类标号属性buys_computer具有两个不同值(即，yes,no)。设q对应于类buys_computer二“

18、yes”，而C2对应于类buys_computer=“no”。我们希望分类的未知样本为：X=(age=30,income=medium,student=yes,credit_rating=fair).我们需要最大化P(XIc.)P(C.)，i=1,2。每个类的先验概率P(C.)可以根据训练样本计算：P(buys_computer=yes)=9/14=0.643P(buys_computer=no)=5/14=0.357为计算P(XICj)，i=1,2。我们计算下面的条件概率：P(age=“30”|buys_computer=“yes”)=2/9=0.222P(age=“30”|buys_computer=“no”)=3/5=0.600P(income=“medium”|buys_computer=4/9=“yes”)0.444P(income=“medium”|buys_computer=2/5=“no”)0.400P(student=“yes”|buys_computer=6/9=“yes”)0.667P(student=“yes”|buys_computer=1/5=“no”)0.200P(credit_rating=“fair”|=6/9=buys_computer=“yes”)0.667P(credit_rating=“fair”|=2/5=buys_co