如何修改基本决策树算法.doc

a) 如何修改基本决策树算法，以便考虑每个广义数据元组（即每一行）的count？b) 使用修改过的算法，构造给定数据的决策树。c) 给定一个数据元组，它的属性department，age和salary的值分别为“systems”，“2630”，和“46K50K”。该元组status的朴素贝叶斯分类是什么？1. 为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。2. 使用上面得到的多层前馈神经网络，给定训练实例（sales，senior，3135，46K50K），给出后向传播算法一次迭代后的权重值。指出你使用的初始权重和偏倚以及学习率。解答：(a) 如何修改基本决策树算法，以便考虑每个广义数据元组（即每一行）的count？(b) 使用修改过的算法，构造给定数据的决策树。(c) 给定一个数据元组，它的属性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=46K50K)； P(X|junior)=P(systems|junior)P(26-30|junior)P(46K-50K|junior)=234923/1133=25921/1442897=0.01796；P(systems|senior)=(5+3)/(30+5+3+10+4)=23/52;P(26-30|senior)=(0)/53=0;P(46K-50K|senior)=(30+10)/52=40/52； X=(department=system,age=2630,salary=46K50K)； P(X|senior)=P(systems|senior)P(26-30|senior)P(46K-50K|senior)=0; P(junior)=113/165=0.68； P(senior)=52/165=0.32； P(X|junior)P(junior)=0.017960.68=0.01221280=0=P(X|senior)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时，元组总数为：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(X|senior)=0；因为status=junior状态对应的partment=systems、age=2630区间的总元组数为：3，所以：P(X|junior)=3/113；因为：P(X|junior)P(junior)=3/113113/1650.0180=P(X|senior)P(senior)；所以：朴素贝叶斯分类器将X分到junior类。(d) 为给定的数据设计一个多层前馈神经网络。标记输入和输出层节点。(e) 使用上面得到的多层前馈神经网络，给定训练实例（sales，senior，3135，46K50K），给出后向传播算法一次迭代后的权重值。指出你使用的初始权重和偏倚以及学习率。7.3.1 判定树归纳判定树归纳的基本算法是贪心算法，它以自顶向下递归的划分-控制方式构造判定树。算法在图7.3中，是一种著名的判定树算法ID3版本。算法的扩展将在7.3.2到7.3.6小节讨论。算法的基本策略如下：n 树以代表训练样本的单个结点开始（步骤1）。n 如果样本都在同一个类，则该结点成为树叶，并用该类标号（步骤2和3）。n 否则，算法使用称为信息增益的基于熵的度量作为启发信息，选择能够最好地将样本分类的属性（步骤6）。该属性成为该结点的“测试”或“判定”属性（步骤7）。在算法的该版本中，所有的属性都是分类的，即离散值。连续属性必须离散化。n 对测试属性的每个已知的值，创建一个分枝，并据此划分样本（步骤8-10）。n 算法使用同样的过程，递归地形成每个划分上的样本判定树。一旦一个属性出现在一个结点上，就不必该结点的任何后代上考虑它（步骤13）。n 递归划分步骤仅当下列条件之一成立停止：(a) 给定结点的所有样本属于同一类（步骤2和3）。(b) 没有剩余属性可以用来进一步划分样本（步骤4）。在此情况下，使用多数表决（步骤5）。这涉及将给定的结点转换成树叶，并用样本中的多数所在的类标记它。替换地，可以存放结点样本的类分布。(c) 分枝test_attribute = a i没有样本（步骤11）。在这种情况下，以samples中的多数类创建一个树叶（步骤12）。属性选择度量在树的每个结点上使用信息增益度量选择测试属性。这种度量称作属性选择度量或分裂的优劣度量。选择具有最高信息增益（或最大熵压缩）的属性作为当前结点的测试属性。该属性使得对结果划分中的样本分类所需的信息量最小，并反映划分的最小随机性或 “不纯性”。这种信息理论方法使得对一个对象分类所需的期望测试数目最小，并确保找到一棵简单的（但不必是最简单的）树。设S是s个数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci (i = 1,., m)。设si是类Ci中的样本数。对一个给定的样本分类所需的期望信息由下式给出： (7.1)其中，pi是任意样本属于Ci的概率，并用si /s估计。注意，对数函数以2为底，因为信息用二进位编码。设属性A具有v个不同值a1 ,., av。可以用属性A将S划分为v个子集S1 ,., Sv；其中，Sj包含S中这样一些样本，它们在A上具有值aj。如果A选作测试属性（即，最好的划分属性），则这些子集对应于由包含集合S的结点生长出来的分枝。设sij是子集Sj中类Ci的样本数。根据A划分子集的熵或期望信息由下式给出： (7.2)项充当第j个子集的权，并且等于子集（即，A值为aj）中的样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。注意，对于给定的子集Sj， (7.3)其中，是Sj中的样本属于Ci的概率。在A上分枝将获得的编码信息是 (7.4)换言之，Gain(A)是由于知道属性A的值而导致的熵的期望压缩。算法计算每个属性的信息增益。具有最高信息增益的属性选作给定集合S的测试属性。创建一个结点，并以该属性标记，对属性的每个值创建分枝，并据此划分样本。例7.2 判定树归纳。表7.1给出了取自AllElectronics顾客数据库数据元组训练集。（该数据取自Qui86）。类标号属性buys_computer有两个不同值（即, yes, no），因此有两个不同的类(m = 2)。设类C1对应于yes，而类C2对应于no。类yes有9个样本，类no有5个样本。为计算每个属性的信息增益，我们首先使用(7.1)式，计算对给定样本分类所需的期望信息：表7.1 AllElectronics顾客数据库训练数据元组RIDageincomestudentcredit_ratingClass: buys_computer1=30highnofairno240mediumnofairyes540lowyesfairyes640lowyesexcellentno731.40lowyesexcellentyes8=30mediumnofairno940mediumyesfairyes1140mediumnoexcellentno下一步，我们需要计算每个属性的熵。让我们从属性age开始。我们需要观察age的每个样本值的yes和no分布。我们对每个分布计算期望信息。对于age = ”40”s11 = 2s12 = 4s13 = 3s21 = 3s22 = 0s23 = 2I(s11, s21) = 0.971I(s12, s22) = 0I(s13, s23) = 0.971使用(7.2)式，如果样本按age划分，对一个给定的样本分类所需的期望信息为：因此，这种划分的信息增益是类似地，我们可以计算Gain(income) = 0.029, Gain(student) = 0.151和Gain(credit_rating) = 0.048。由于age在属性中具有最高信息增益，它被选作测试属性。创建一个结点，用age标记，并对于每个属性值，引出一个分枝。样本据此划分，如图7.4所示。注意，落在分区age = “31.40”的样本都属于同一类。由于它们都属于同一类yes，因此要在该分枝的端点创建一个树叶，并用yes标记。算法返回的最终判定树如图7.2所示。图7.4：属性age具有最高信息增益，因此成为判定树根的测试属性。由每个age引出分枝，样本据此划分总而言之，判定树归纳算法已在广泛的应用领域用于分类。这种系统不使用领域知识。判定树归纳的学习和分类步骤通常很快。7.4.2 朴素贝叶斯分类朴素贝叶斯分类，或简单贝叶斯分类的工作过程如下：1. 每个数据样本用一个n维特征向量表示，描述由属性对样本的n个度量。2. 假定有m个类。给定一个未知的数据样本X（即，没有类标号），分类法将预测X属于具有最高后验概率（条件X下）的类。即，朴素贝叶斯分类将未知的样本分配给类Ci ，当且仅当：这样，我们最大化。其最大的类Ci称为最大后验假定。根据贝叶斯定理(7.5)式), (7.6)3 由于P(X) 对于所有类为常数，只需要最大即可。如果类的先验概率未知，则通常假定这些类是等概率的；即，。并据此对只最大化。否则，我们最大化。注意，类的先验概率可以用计算；其中，si是类C中的训练样本数，而s是训练样本总数。4 给定具有许多属性的数据集，计算的开销可能非常大。为降低计算的开销，可以做类条件独立的朴素假定。给定样本的类标号，假定属性值条件地相互独立。即，在属性间，不存在依赖关系。这样， （7.7）概率,.,可以由训练样本估值，其中，(a) 如果Ak是分类属性，则；其中sik 是在属性Ak 上具有值xk 的类Ci 的训练样本数，而si 是Ci中的训练样本数。(b) 如果是连续值属性，则通常假定该属性服从高斯分布。因而， （7.8）其中，给定类Ci的训练样本属性Ak的值，是属性Ak的高斯密度函数，而分别为平均值和标准差。5 为对未知样本X分类，对每个类Ci，计算。样本X被指派到类Ci，当且仅当：换言之，X被指派到其最大的类Ci。“贝叶斯分类的效率如何？”理论上讲，与其它所有分类算法相比，贝叶斯分类具有最小的出错率。然而，实践中并非总是如此。这是由于对其应用的假定（如，类条件独立性）的不正确性，以及缺乏可用的概率数据造成的。然而，种种实验研究表明，与判定树和神经网络分类算法相比，在某些领域，该分类算法可以与之媲美。贝叶斯分类还可以用来为不直接使用贝叶斯定理的其它分类算法提供理论判定。例如，在某种假定下，可以证明正如朴素贝叶斯分类一样，许多神经网络和曲线拟合算法输出最大的后验假定。例7.4 使用朴素贝叶斯分类预测类标号：给定与例7.2判定树归纳相同的训练数据，我们希望使用朴素贝叶斯分类预测一个未知样本的类标号。训练数据在表7.1中。数据样本用属性age, income, student和credit_rating描述。类标号属性buys_computer具有两个不同值（即，yes, no）。设C1对应于类buys_computer = “yes”，而C2对应于类buys_computer = “no”。我们希望分类的未知样本为：我们需要最大化，i = 1,2。每个类的先验概率可以根据训练样本计算：P(buys_computer = yes) = 9/14 = 0.643P(buys_computer = no) = 5/14 = 0.357为计算， 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 = “yes”)= 4/9 = 0.444P(income = “medium” | buys_computer = “no”)= 2/5 = 0.400P(student = “yes” | buys_computer = “ yes”)= 6/9 = 0.667P(student = “yes” | buys_computer = “no”)= 1/5 = 0.200P(credit_rating = “fair” | buys_computer = “yes”)= 6/9 = 0.667P(credit_rating = “fair” | buys_computer = “no”)= 2/5 = 0.400使用以上概率，我们得到：P(X |