分类

分类任务的输入数据是记录的集合，每条记录也称实例或样例，用元组(x,y)来表示，其中x是属性的集合，而y是一个特殊的属性，指出样例的类标号。

类标号在分类中是离散属性，回归确是一种预测建模任务，其中目标属性y是连续的。

概念
分类任务就是通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y。
目标函数也称分类模型，具有以下目的:

• 描述性建模。分类模型可以作为解释性工具，用于区分不同类中的对象。

• 预测性建模。分类模型还可以用于预测未知记录的类标号，可以看做一个黑箱，当给定未知记录的属性集上的值时，它自动赋予未知标本类标号。

决策树

决策树是一种由节点和有向边组成的层次结构，树中包含三种结点。

• 根节点，没有入边，但有零条或多条出边。

• 内部结点，恰有一条入边和两条或多条出边。

• 叶节点或终结点，恰有一条入边，但没有出边。

Hunt算法

递归方式建立决策树。
设Dt是与结点t相关联的训练记录集，而y={y1，y2,……，yc}是类标号，Hunt算法的递归定义如下。
(1)如果Dt中所有记录都属于同一个类yt，而t是叶结点，用yt标记。

(2)如果Dt中包含属于多个类的记录，则选择一个属性测试条件，将记录划分为较小的子集。对于测试条件的每个输出，创建一个子女结点，并根据测试结果将Dt中的记录分布到子女结点中，然后对于每个子女结点，递归调用该算法。
如下图，根节点的左子女为叶结点，标记为“拖欠贷款者=否”。对于右子女，递归调用Hunt算法，直到所有记录都属于同一个类为止。每次递归调用所形成的决策树显示如下

附加条件
(1)算法的第二步所创建的子女结点可能为空，即不存在这些结点相关联的记录。如果没有一个训练记录包含与这样的结点相关联的属性值组合，这时，该结点成为叶结点，类标号为其父节点上训练记录中的多数类。

(2)第二步，如果与Dt相关联的所有记录都具有相同的属性值，则不可能进一步划分这些记录，在这种情况下，该结点为叶结点，其标号与该结点相关联的训练记录中的多数类。

设计问题

(1)如何分裂训练记录？树增长过程的每个递归步都必须选择一个属性测试条件，将记录划分成较小子集。算法必须提供为不同类型的属性值测试条件的方法，并且提供评估每种测试条件的客观度量。

(2)如何停止分裂过程？需要有结束条件，以终止决策树的生长过程。一个可能的策略是分裂结点，直到所有的记录都属于同一个类，或者所有记录都具有相同的属性值。

表示属性测试条件的方法

决策树归纳算法必须为不同类型的属性提供表示属性测试条件和对应输出的方法。

• 二元属性 二元属性测试条件产生两个可能输出
  

  
  
  

• 标称属性 由于标称属性有多个属性值，它的测试条件可以用两种方法表示。对于多路划分，其输出数取决于该属性不同属性值的个数。另一方面，某些决策树算法只产生二元划分，它们考虑创建k个属性值的二元划分的所有2^(k-1)-1种方法
  

  
  
  

• 序数属性 序数属性也可以产生二元或多路划分，只要不违背序数属性值的有序性，就可以对属性值进行分组。
  

  
  
  

• 连续属性 对于连续属性来说，测试条件是可以具有二元输出的比较测试(A