熵：对平均不确定性的度量：
互信息：指两个事件集合之间的相关性。两个事件X和Y的互信息定义为：
其中，H(X, Y) 是联合熵(Joint Entropy)，其定义为：
平均互信息：得知特征Y的信息而使得对标签X的信息的不确定性减少的程度。\
熵与互信息的关系：
决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处的熵值为零，此时每个叶节点中的实例都属于同一类。是有监督学习。
建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数建立决策树主要有一下三种算法：ID3，C4.5，CART。
特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：g(D,A)=H(D) - H(D|A)。显然，这即为训练数据集D和特征A的互信息。遍历所有特征，选择信息增益最大的特征作为当前的分裂特征。
信息增益率：gr(D,A)= g(D,A) / H(A)
Gini系数：
考察Gini系数的图像、熵、分类误差率三者之间的关系 ，将f(x)=-lnx在x=1处一阶展开，忽略高阶无穷小，得到 f(x) ≈1-x。
ID3：
取值多的属性，更容易使数据更纯，其信息增益更大。训练得到的是一棵庞大且深度浅的树：不合理。 C4.5 ：
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
CART： 一个属性的信息增益(率)/gini指数越大，表明属性对样本的熵减少的能力更强，这个属性使得数据由不确定性变成确定性的能力越强。
假定样本的总类别为K个。 对于决策树的某叶结点，假定该叶结点含有样本数目为n，其中第k类的样本点数目为nk，k=1,2....K。 若某类样本nj=n而n1,n2,...,nk=0，称该结点为纯结点；若各类样本数目n1=n2=...=nk=n/K，称该样本为均结点。 纯结点的熵Hp=0，最小；均结点的熵Hu=lnK，最大。 对所有叶结点的墒求和，该值越小说明对样本的分类越精确。 各叶结点包含的样本数目不同，可使用样本数加权求熵和评价函数：
由于该评价函数越小越好，所以，可以称之为“损失函数”。
决策树对训练属于有很好的分类能力，但对未知的测试数据未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。
由完全树T0开始，剪枝部分结点得到T1，再次剪枝部分结点得到T2...直到仅剩树根的树Tk；在验证数据集上对这k个树分别评价，选择损失函数最小的树Ta。
根据原损失函数：
叶结点越多，决策树越复杂，损失越大，故加以修正：
假定当前对以r为根的子树剪枝：剪枝后，只保留r本身而删掉所有的叶子 考察以r为根的子树：令剪枝后的损失函数=剪枝前的损失函数，求得a。
对于给定的决策树T0: 计算所有内部节点的剪枝系数; 查找最小剪枝系数的结点，剪枝得决策树Tk ; 重复以上步骤，直到决策树Tk只有1个结点; 得到决策树序列T0T1T2...TK ; 使用验证样本集选择最优子树。 使用验证集做最优子树的标准，可以使用评价函数。
Bagging算法（英语：Bootstrap aggregating，引导聚集算法），又称装袋算法，是机器学习领域的一种团体算法。Bagging算法可与其他分类、回归算法结合，提高其准确率、稳定性的同时，通过降低结果的方差，避免过拟合的发生。
Bagging是通过结合几个模型降低泛化误差的技术。主要想法是分别训练几个不同的模型，然后让所有模型表决测试样例的输出。 这是机器学习中常规策略的一个例子，被称为模型平均（model averaging）。采用这种策略的技术被称为集成方法。
bootstrap aggregation 从样本集中重采样(有重复的)选出n个样本在所有属性上，对这n个样本建立分类器(ID3、C4.5、CART、SVM、Logistic 回归等)，重复以上两步m次，即获得了m个分类器，将数据放在这m个分类器上，最后根据这m 个分类器的投票结果，决定数据属于哪一类。
随机森林在bagging基础上做了修改。
从样本集中用Bootstrap采样选出n个样本；从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；重复以上两步m次，即建立了m棵CART决策树，这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类。
当然可以使用决策树作为基本分类器，但也可以使用SVM、Logistic回归等其他分类器，习惯上，这些分类器组成的“总分类器”，仍然叫做随机森林。
多个分类器的投票机制包括：一票否决、少数服从多数、有效多数（加权）。
如果一个问题存在弱分类器，则可以通过梯度提升的方法得到强分类器。
