决策树

决策树:分类决策树模型使一种对实例进行分类的树形结构。决策树由节点和有向边组成，节点有两种类型：内部节点和叶节点。内部节点表示一个特征和属性，叶节点表示一个类。
特征选择:特征选择在于选取对训练数据具有分类能力的特征。通常特征选择的准则是信息增益或信息增益比。
信息熵:熵是表示随机变量不确定性的度量。由定义可知，熵只依赖于X的分布，而与X的取值无关。熵越大，随机变量的不确定性越大。

信息熵.png

条件熵.png

信息增益.png

信息增益比.png

决策树的生成

• ID3算法：在决策树各个节点上应用信息增益准则选择特征，递归构建决策树。该算法只有决策树的生成，所以该算法生成的树容易产生过拟合。
• C4.5算法：与ID3相似，在生成决策数的过程中，用信息增益比来选择特征。