摘要 决策树是一种使用信息增益度选择测试属性的分类方法。本文通过对ID3算法的分析，利用凸函数的相关知识化简信息增益度的计算复杂度，从而提高决策树的构造效率。 关键词 决策树；ID3算法；教学测评
中图分类号TP3 文献标识码A 文章编号 1674-6708（2012）79-0227-01
1 ID3算法简介
ID3算法由Quinlan于1979年提出。其基本思想是：在对训练集进行分类时，以信息熵为度量，用于决策树节点的属性选择，每次优先选取信息量最多的属性对数据进行划分，以构造一颗熵值下降最快的决策树，每个叶子节点对应的实例集中的实例属于同一类。
设样本数据集T有s个样本，每个样本都有u个评估属性，m个类别。评估属性划分T成v个子集，其中中包含样本，属于第类的样本数为（i=1，2，...m）。则有：子集的信息熵：I（）==
属性的信息熵为：E（）=信息增益为： Gain（）=I（T）- E（）
2 ID3算法的优点和不足
优点：运用信息论知识选择属性，理论清晰；容易生成IF-THEN语句；对于离散型样本数据处理功能强；ID3自顶向下搜索，节省系统资源，计算时间与样本大小。
不足：ID3算法在选择分类属性时往往选择了取值较多的属性；ID3算法只能处理离散型数据，若分析必须先进行离散化；用ID3算法创建决策树时必须知道所有内部节点。
