ID3决策树-资料.docVIP

决策树学习算法ID3 摘要 决策树算法构造决策树来发现数据中蕴涵的分类规则是一种逼近离散函数值的方法如何构造精度高、规模小的决策树是决策树算法的核心内容。Classification）的任务就是通过学习获得一个目标函数（Target Function）f, 将每个属性集x映射到一个预先定义好的类标号y。分类任务的输入数据是纪录的集合，每条记录也称为实例或者样例，用元组(X,y)表示，其中，X 是属性集合，y是一个特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）。 分类技术是一种根据输入数据集建立分类模型的系统方法。分类技术一般是用一种学习算法确定分类模型，该模型可以很好地拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅要很好拟合输入数据，还要能够正确地预测未知样本的类标号。因此，训练算法的主要目标就是要建立具有很好的泛化能力模型，即建立能够准确地预测未知样本类标号的模型。 分类方法的实例包括：决策树分类法、基于规则的分类法、神经网络、支持向量级、朴素贝叶斯分类方法等。 分类问题一般包括两个步骤： 1、模型构建（归纳）：通过对训练集合的归纳，建立分类模型。 2、预测应用（推论）：根据建立的分类模型，对测试集合进行测试。 决策树的基本概念 决策树是一种类似于流程图的树结构，其中，每个内部节点（非树叶节点）表示在一个属性上的测试，每个分枝代表一个测试输出，而每个树叶节点（终结点）存放一个类标号。树的最顶层节点是根节点。决策树是一种典型的分类方法，首先对数据进行处理，利用归纳算法生成可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树技术发现数据模式和规则的核心是归纳算法，归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。 决策树分类器具有很多优点：决策树的构造不需要任何领域知识或参数设置，因此适合于探测式知识发现；决策树可以处理高维数据，推理过程完全依赖于属性变量的取值特点，可自动忽略目标变量没有贡献的属性变量，也为判断属性变量的重要性，减少变量的数目提供参考，同时对噪声数据具有很好的健壮性；决策树归纳的学习和分类步骤是简单和快速的，推理过程可以表示成If Then形式，并且具有很好的准确率；获取的知识用树的形式表示是直观的，并且容易被人理解。因而，决策树归纳分类是目前应用最广泛的归纳推理算法之一，在数据挖掘中受到研究者的广泛关注。 决策树算法的应用 决策树归纳算法已经成功地应用于许多应用领域的分类，如医学、制造和生产、金融分析、天文学和分子生物学。决策树是许多商业规则归纳系统的基础。 例如，在客户关系管理应用中，利用决策树建立对理想客户的分析模型之前 ,可以将客户数据中有关客户特征的描述变量 (如 :年龄、年收入、学历、最近消费频率等 )作为输入变量 ,而将理想客户的评价变量 (如 :未来消费金额 ,是否为理想客户等 )作为目标变量。ID3算法主要针对属性选择问题，是决策树学习方法中最具影响和最为典型的算法。ID3采用贪心方法，其中决策树以自顶向下递归的分治方式构造。大多数决策树归纳算法都沿用这种自顶向下的方法，从训练元组集和它们的相关联的类标号开始构造决策树。随着树的构建，训练集递归地划分成较小的子集。算法中关键的一步是属性选择度量，即选择分裂准则。三种度量方法信息增益、增益率和Gini指标。（示例算法选择了第一种方法）( attribute_list - splitting_ attribute ； //删除划分属性 for splitting_criterion的每个输出j // 划分元组并对每个划分产生子树 设Dj是D中满足输出j的数据元组的集合；//一个划分 if Dj为空then 加一个树叶到节点N，标记为D中的多数类； else 加一个由Generate_decision_tree（Dj，attribute_list）返回的节点到节点N； end for 返回N； 上述算法基本策略中，用到三个参数D、attribute_list和Attribute_selection_method调用该算法。其中，D为数据划分；attribute_list是描述元组的属性列表；Attribute_selection_method指定选择属性的启发式过程，所选择的属性按类“最好”地区分元组。该过程使用一种属性选择度量，如信息增益和Gini指标 （1） 其中，pi是D中任意元组属于类Ci的概率，并用|Ci,D|/|D|估计。使用以2为底的对数函数，因为信息用二进位编码。Info(D)是识别D中的元组的类标号所需的平均信息量。这里，我们所具有的信息只是每个类的元组所占的百分比。In