Question

如何修改基本决策树算法，以便考虑每个广义数据元组

Answer 1

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