信息熵(Entropy)
设$Y$是取有限个值的离散随机变量，其概率分布为：
$$ P(Y = y_i) = p_i,\quad i = 1, 2, 3, ..., n $$则随机变量$Y$的熵的定义为：
$$ H(Y) = -\sum_{i=1}^n p_i\log_bp_i $$根据对数的底$b$的不同，熵的单位不同。当$b$为2时，单位为比特(bit)，当$b$为e时，单位为纳特(nat)。
熵被认为是不确定性的度量。很显然当系统内只有一个事件且该事件必定发生时，熵取最小值为0。当系统内各事件发生概率相同时，熵取最大值$\log_bn$，此时系统内的不确定性最高。特别的，当$p_i$为0时，$p_i \log_bp_i$为0。
条件熵(Conditional Entropy)
条件熵表示基于某条件下的信息熵。定义为：
$$ H(Y|X) = \sum_{i=1}^np_iH(Y|X = x_i) $$这里的$p_i=P(X = x_i),\quad i = 1,2,3,...,n$。$H(Y|X = x_i)$为$X$取$x_i$时，$Y$的信息熵。
信息增益(Information Gain, IG)
信息增益等于信息熵减去条件熵。即：
$$ IG(Y, X) = H(Y) - H(Y|X) $$可以理解为在知道变量$X$后，$Y$的不确定性减少了多少。
决策树的ID3算法中采用信息增益作为特征选择标准。
信息增益比(Information Gain Ratio)
信息增益的缺点在于会偏向取值数目较多的特征，而信息增益比则可以克服该缺点：
$$ IG_{Ratio}(Y, X) = {IG(Y, X) \over H(X)} $$即用信息增益除以特征的信息熵（在这里一般把分母部分称作特征$X$的固有值，但是计算方式和信息熵是一样的）。
决策树的C4.5算法中采用信息增益比作为特征选择标准。
基尼指数(Gini Index)
基尼指数描述的是随机抽取两个样本，其类别不一致的概率（不纯的度量），即：
$$ Gini(Y) = \sum_{i=1}^n p_i(1-p_i) = 1 - \sum_ip_i^2 $$从而可以知道：
$$ Gini(Y|X) = \sum_{i=1}^np_iGini(Y|X = x_i) $$这里，$p_i=P(X = x_i),\quad i = 1,2,3,...,n$。
决策树的CART算法中的分类树采用基尼指数作为特征选择标准。特别的，CART算法生成的是二叉树，故上面的公式中的$n$为2。