8.1主要步骤如下：

1.先从考虑构建一个根节点（包含所有的训练元组）开始，如果所有的元组都属于同一个类，那么这个根节点也是一个叶子节点，并给其赋上元组所属的类标签。如果这些元组不属于同一个类，则应该确定一种属性选择度量（又称为分裂规则），以达到把给定类标记的训练元组“最好地”划分成单独类的目的。这种分裂规则的选择可以通过启发式的方法或者统计学度量（如，信息增益，基尼指数）来确定。更具体地说，分裂准则指定分裂属性，并且也指出分裂点或分裂子集。

2.再确定了一个结点的分裂准则后，需要在此结点上进行测试。对于分裂准则的每个输出，测试结点生长出一个分枝，测试结点所包含的的元组也据此进行划分。有三种可能的划分情况：（1）如果分裂属性是离散值的，那么该属性的每一个已知值对应于一个分枝。（2）如果分裂属性是连续值的，那么生长出两个分枝，对应的条件分别是“属性值≤分裂点”和“属性值＞分裂点”。（3）如果一个属性是离散的，并且要求产生一棵二叉树（比如，将基尼指数作为属性选择度量），此时在测试结点上进行的是形如“属性值∈SA”的测试，其中SA是属性A的分裂子集（属性值A的已知值的子集）。相应的，二叉树的两个分枝分别对应测试结果为“yes”和“no”的元组子集。

3.对于每个结果分区上的元组，算法使用同样的过程递归地形成决策树。递归终止的条件为：

（1）如果一个结点所表示的元组属于同一类时，将此结点视为叶子结点，并用元组所属的类标号进行标记。

（2）如果没有剩余属性可以用来进一步划分元组，采用多数表决的方式，将此结点转换成树叶，并用多数类标记它。

（3）如果给定的分枝没有元组，则使用测试结点代表数据的多数类创建一个树叶。

8.4

考虑最坏情况：在每一次选择分裂属性时，都存在大量可选择的属性。因为训练元组数为|D|，所以树的最大深度为log(|D|)。在树的每一层，各个结点所代表的元组总数最多为|D|，在选择分裂属性时，最多有n个属性可以选择，所以树的每一层的计算复杂度为O（n×|D|）。所以总的计算复杂度为O（n×|D|×log|D|）。

8.6

朴素贝叶斯分类之所以被称为是“朴素”的是因为它的前提假设是类条件独立性。也就是说，一个属性值在给定类上的影响独立于其他属性的值。做此假定是为了简化计算，所以在此意义下认为它是“朴素”的。朴素贝叶斯分类的主要思想是通过贝叶斯定理求后验概率的方法最大化概率值P（X/Ci）P（Ci）（i是类标号）来对数据进行划分。一般地：

◆假定有m个类：C1，C2，...,Cm，给定一系列未知类标号的数据元组，每个元组用一个n维属性向量表示：X=（x1,x2,...,xn）（其中xi表示元组在属性Ai上的属性值）。通过贝叶斯定理，朴素贝叶斯分类器可以计算每一个类在给定某个元组X条件下的后验概率，最终把对应最大后验概率的类的类标号指派给元组X。所以，我们需要最大化，P（Ci/X）=P（X/Ci）P（Ci）/P（X）。由于P（X）对所有类为常数，所以只需要最大化P（X/Ci）P（Ci）。如果类的先验概率未知，则通常假定这些类是等概率的，即P（C1）=P（C2）=......=P（Cm），并据此对P（X/Ci）最大化。类的先验概率可以用P（Ci）=Si/S估计，其中Si是类Ci所包含的训练元组数，S是所有训练元组的总数。

◆为了降低计算P（X/Ci）的复杂性，做了类条件独立的朴素假定。给定元组的类标号，假定属性值有条件地相互独立（即属性之间不存在依赖关系）。

——如果Ak是分类属性，则P（xk/Ci）是属性Ak的值为xk的Ci类的元组数除以Ci类的元组总数。

——如果Ak是连续属性，则P（xk/Ci）可以通过高斯分布函数进行计算。

8.7

（a）基本决策树算法可以做如下修改：

◆count属性提供的是某一类元组（如department="sales",status="senior",age=

"31...35",salary="46K...50k"的元组）的计数。因此通过count属性值（即计数信息）可以计算信息增益、基尼指数等属性选择度量，从而确定给定结点上的分裂属性。

◆通过考虑count属性，确定元组中最一般地类。

（b）构造的决策树如下：

（salary=26K...30K:junior

=31K...35K:junior

=36K...40K:senior

=46K...45K:junior

=46K...50K(department=secretary:junior

=sales:senior

=systems:junior

=marketing:senior)

=66K...70K:senior)

（c）朴素贝叶斯分类的结果是“junior”。

8.11

8.12

8.14

8.16

处理类不平衡问题的方法有（1）过抽样（2）欠抽样（3）阈值移动（4）组合技术

过抽样：对正元组重复采样，使得结果训练集包含相同个数的正元组和负元组。

欠抽样：减少负元组的数量。它随机地从多数（负）类中删除元组，直到正元组和负元组的数量相等。

阈值移动：它用于对给定输入元组返回一个连续值的分类器。该方法不是操控训练元组，而是基于输出值返回分类决策。最简单的是，对于某个阈值t，满足f(X)>=t的元组X被视为正的，而其它元组被看做负的。所以，阈值移动方法移动阈值t，使得稀有类的元组容易分类（因而，降低了代价高的假阴性出现的机会）。

组合方法：采用组合分类的方法，提高分类准确性。组成组合分类器的个体分类器可以使用上面介绍的方法，如过抽样和阈值移动。

信用卡欺诈检测是典型的类不平衡问题。在设计分类器时可以考虑：采用过抽样与阈值移动相结合的方法；针对单一分类器的局限性，可以引入多分类器融合的思想；与Adaboost的学习方法相结合进行学习；采用多样化的评价指标对分类结果进行评价。st;W�8Ic�