决策树中，每一个内节点就是测试属性 x i x_i xi，每一个边就是去选择属性 x i x_i xi的值，每一个叶节点就会去预测 Y Y Y（西瓜书就是以西瓜的一些特征来预测西瓜的好坏，老师上课讲的PPT上就是用一些人的特点来预测是否偷税漏税的） 也就是说，决策树在理论上应该是能够表示输入属性的任何函数，但是这就会产生一个问题：如果这个决策树过于庞大，以至于他把每一个训练数据都精准的分开了，这会产生生么后果呢？答案当然是过拟合，这棵树已经可能没有泛化能力了。我们就是想要找一棵合适大小的树，并且这棵树能比较准确的预测验证集上的数据。显然，决策树也可能欠拟合，就是当节点数的大小实在是太小时就会发生欠拟合，因为样本的类别根本不能很好的区分开。 老师PPT上的一个算法（构造树）：
A←下一个结点node的最好属性把A作为决策属性赋给结点node对A的每一个取值，创建一个新的儿子结点node把相应的训练样本分到叶结点如果训练样本被很好的分类，则停止，否则在新的叶结 点上重复上述过程 那么我们就会提出疑问，什么样的属性才是最好的呢？我们肯定是希望这个属性切分下去，直接就能把数据分成一半正例一半反例，这样我们就一个属性就齐活了。但是我们并不可能直接这样完成。但是我们能够使用熵来刻画我们选取的属性的好坏。 H ( x ) = − ∑ i = 1 N P ( x = i ) l o g 2 P ( x = i ) H ( X ∣ y = j ) = − ∑ i = 1 N P ( x = i ∣ y = j ) l o g 2 P ( x = i ∣ y = j ) H ( X ∣ Y ) = ∑ j ∈ V a l ( y ) P ( y = j ) H ( X ∣ y = j ) I ( X ; Y ) = H ( X ) − H ( X ∣ Y ) = H ( Y ) − H ( Y ∣ X ) = H ( X ) + H ( Y ) − H ( X , Y ) H(x)=-\sum\limits_{i=1}^{N}P(x=i)log_2P(x=i)\\H(X|y=j)=-\sum\limits_{i=1}^{N}P(x=i|y=j)log_2P(x=i|y=j)\\H(X|Y)=\sum\limits_{j\in Val(y)}P(y=j)H(X|y=j)\\I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y) H(x)=−i=1∑NP(x=i)log2P(x=i)H(X∣y=j)=−i=1∑NP(x=i∣y=j)log2P(x=i∣y=j)H(X∣Y)=j∈Val(y)∑P(y=j)H(X∣y=j)I(X;Y)=H(X)−H(X∣Y)=H(Y)−H(Y∣X)=H(X)+H(Y)−H(X,Y) 证明： H ( X ) − H ( X ∣ Y ) = H ( Y ) − H ( Y ∣ X ) H(X)-H(X|Y)=H(Y)-H(Y|X) H(X)−H(X∣Y)=H(Y)−H(Y∣X) H ( X ) − H ( X ∣ Y ) = − ∑ i = 1 N P ( x = i ) l o g 2 P ( x = i ) − ∑ j ∈ V a l ( y ) P ( y = j ) H ( X ∣ y = j ) = − ∑ i = 1 N P ( x = i ) l o g 2 P ( x = i ) + ∑ j ∈ V a l ( y ) P ( y = j ) ∑ i = 1 N P ( x = i ∣ y = j ) l o g 2 P ( x = i ∣ y = j ) = − ∑ x ∈ V a l ( x ) P ( x ) l o g 2 P ( x ) + ∑ y ∈ V a l ( y ) P ( y ) ∑ x ∈ V a l ( x ) P ( x ∣ y ) l o g 2 P ( x ∣ y ) = − ∑ x ∈ V a l ( x ) ∑ y ∈ V a l ( y ) P ( x , y ) l o g 2 P ( x ) + ∑ y ∈ V a l ( y ) ∑ x ∈ V a l ( x ) P ( y ) P ( x ∣ y ) l o g 2 P ( x ∣ y ) = ∑ y ∈ V a l ( y ) ∑ x ∈ V a l ( x ) P ( x , y ) l o g 2 P ( x ∣ y ) P ( x ) = ∑ y ∈ V a l ( y ) ∑ x ∈ V a l ( x ) P ( x , y ) l o g 2 P ( x , y ) P ( x ) P ( y ) = H ( Y ) − H ( Y ∣ X ) H(X)-H(X|Y)\\=-\sum\limits_{i=1}^{N}P(x=i)log_2P(x=i)-\sum\limits_{j\in Val(y)}P(y=j)H(X|y=j)\\=-\sum\limits_{i=1}^{N}P(x=i)log_2P(x=i)+\sum\limits_{j\in Val(y)}P(y=j)\sum\limits_{i=1}^{N}P(x=i|y=j)log_2P(x=i|y=j)\\=-\sum\limits_{x\in Val(x)}P(x)log_2P(x)+\sum\limits_{y\in Val(y)}P(y)\sum\limits_{x\in Val(x)}P(x|y)log_2P(x|y)\\=-\sum\limits_{x\in Val(x)}\sum\limits_{y\in Val(y)}P(x,y)log_2P(x)+\sum\limits_{y\in Val(y)}\sum\limits_{x\in Val(x)}P(y)P(x|y)log_2P(x|y)\\=\sum\limits_{y\in Val(y)}\sum\limits_{x\in Val(x)}P(x,y)log_2\frac{P(x|y)}{P(x)}\\=\sum\limits_{y\in Val(y)}\sum\limits_{x\in Val(x)}P(x,y)log_2\frac{P(x,y)}{P(x)P(y)}=H(Y)-H(Y|X) H(X)−H(X∣Y)=−i=1∑NP(x=i)log2P(x=i)−j∈Val(y)∑P(y=j)H(X∣y=j)=−i=1∑NP(x=i)log2P(x=i)+j∈Val(y)∑P(y=j)i=1∑NP(x=i∣y=j)log2P(x=i∣y=j)=−x∈Val(x)∑P(x)log2P(x)+y∈Val(y)∑P(y)x∈Val(x)∑P(x∣y)log2P(x∣y)=−x∈Val(x)∑y∈Val(y)∑P(x,y)log2P(x)+y∈Val(y)∑x∈Val(x)∑P(y)P(x∣y)log2P(x∣y)=y∈Val(y)∑x∈Val(x)∑P(x,y)log2P(x)P(x∣y)=y∈Val(y)∑x∈Val(x)∑P(x,y)log2P(x)P(y)P(x,y)=H(Y)−H(Y∣X)下面我们就是用熵来表示 S S S的混杂程度 H ( S ) = − p + l o g 2 p + − p − l o g 2 p − H(S)=-p_+log_2p_+-p_-log_2p_- H(S)=−p+log2p+−p−log2p−，在选择切分点时，我们就是取选择信息增益最大的点（ G a i n = E n t r o p y ( p ) − ( ∑ n i n E n t r o p y ( i ) ) Gain=Entropy(p)-(\sum\frac{n_i}{n}Entropy(i)) Gain=Entropy(p)−(∑nniEntropy(i))）增益越大，我们会发现切完之后的样本就会更纯了。
树停止：（1）节点上的所有节点都属于一个类别（2）节点上的样本属性值相似（3）提早结束（当实例的数量少于某些阀值的时候；实例的分布与可用特征无关；扩展这个点已经不能使分得的纯度更纯了）
Occam’s Razor：当两个模型的误差几乎相同的时候，我们选择尽可能小的那个模型进行输出 C o s t ( M o d e l , D a t a ) = C o s t ( D a t a ∣ M o d e l ) + C o s t ( M o d e l ) Cost(Model,Data)=Cost(Data|Model)+Cost(Model) Cost(Model,Data)=Cost(Data∣Model)+Cost(Model)，这个基本上就是数据+正则项那个啊！！！
当有特征缺失时，我们仍然可以做决策树，我们就乘一个权重就好了（比如有10个数据，3个正例，7个反例，我们计算 E n t r o p y ( P a r e n t ) = − 0.3 l o g 0.3 − 0.7 l o g 0.7 = 0.8813 Entropy(Parent)=-0.3log0.3-0.7log0.7=0.8813 Entropy(Parent)=−0.3log0.3−0.7log0.7=0.8813，某一个特征中一个样本缺失，我们现在只有该特征Yes正反例分别是0,3个，该特征NO正反例2,4个， E n t r o p y ( C h i l d r e n ) = 0.3 E n t r o p y ( Y e s ) + 0.6 E n t r o p y ( N o ) = 0.551 Entropy(Children)=0.3Entropy(Yes)+0.6Entropy(No)=0.551 Entropy(Children)=0.3Entropy(Yes)+0.6Entropy(No)=0.551，最后 G a i n = 0.9 ( Δ E n t r o p y ) = 0.3303 Gain=0.9(\Delta Entropy)=0.3303 Gain=0.9(ΔEntropy)=0.3303）
引用：哈工大机器学习PPT、西瓜书
