1.决策树
决策树是应用广泛的一种归纳推理算法。在分类问题中，决策树算法基于特征对样本进行分类，构成一棵包含一系列if-then规则的树，在数学上可以将这棵树解释为定义在特征空间与类空间上的条件概率分布。
决策树的主要优点是分类速度快、训练数据可包含错误、模型具有可读性，目前已被成功应用到医疗诊断、贷款风险评估等领域。
2.sklearn中自带的决策树方法
class sklearn.tree.DecisionTreeClassifier(criterion='gini', splitter='best', max_depth=None, min_samples_split=2,min_samples_leaf =1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None,class_weight=None, presort=False)
主要参数说明如下：
①criterion:默认为"gini"，用来衡量分类的质量。支持的标准有"gini"与"entropy"，"gini"代表的是Gini impurity(不纯度)，"entropy"代表的是information gain（信息增益）。
②splitter:默认为"best"，一种用来在节点中选择分类的策略。支持的策略有"best"，选择最好的分类，"random"选择最好的随机分类。
③max_features:有int,float,string or None三类值，默认为None，表示在进行分类时需要考虑的特征数。
3.ID3算法
（1）相关概念
①信息熵
设X为一个可取有限个值{x1，x2，...，xn}的离散随机变量，其概率分布为Pi=P(X=xi)，则随机变量X的信息熵定义为：
上式中，对数log以2为底，熵的单位是比特(bit)，以自然对数e为底，熵的单位是纳特(nat)。信息熵越大，表示不确定性越强。
②条件信息熵
假设X的概率分布为pi=PX(X=xi)，Y在X条件下的条件概率分布为pj|i=PY|X(yj |xi)，条件信息熵H(Y|X)定义为：
③信息增益
g(D, A)=H(D)-H(D |A)
信息增益用来量化分类的不确定性降低的程度，即熵降低的程度。所以在选择切分特征时，先计算每个特征的信息增益，选择信息增益最大的特征作为切分特征。
所以ID3算法是依据信息增益做特征选择。
（2）ID3算法的实现
【注】决策树可视化需要安装GraphViz，并将软件的安装路径添加到主机环境变量中。
（3）ID3的缺点
①实例各特征的取值必须是离散值，而不能是连续实数值（例如销量只能是“高”、“低”，而不能是具体数值）。
②预测目标只能为离散值，不能是连续实数值，因此只能处理分类问题，而不能处理回归问题。
4.C4.5算法
依据信息增益选择切分特征时，如果一个特征的可取值较多，通常它的信息增益更大，该特征则会被优先选择，这对于可取值较少的特征不公平。为避免这样的问题，可以以信息增益比为指标来选择切分特征，信息增益比实质上就是在信息增益的基础上对可取值较多的特征做出一定的“惩罚”。
C4.5算法就是依据信息增益比来选择特征的。
