记录

jstat
jmap

• 案例
  内存泄露分析

决策树算法

什么是决策树？

决策树算法是从数据中提取用于决策&预测的树形结构，因此称为决策树。例如
瓜的好坏，与纹理（清晰、模糊）、根蒂（蜷缩、稍蜷、硬挺）、色泽（青绿、乌黑、浅白）、触感（硬滑、软粘）这些特征相关，瓜的相关数据可能会生成如下的决策树，非叶子结点为特征名称、叶子结点为结果：

那么在预测时，如果一个瓜的纹理为模糊时，就是坏瓜
那么怎么生成决策树呢，有基于信息熵选择特征的ID3、C4.5算法以及基于基尼系数选择特征的CART算法。

基于信息熵选择特征的决策树算法

熵的概念最早起源于物理学，是用于度量一个热力学系统的无序程度。在信息论和概率统计里面，熵是对不确定性的测量，熵越大，不确定性越高。使用如下公式来计算信息熵：
$D = -\sum P_ilog_2P_i$，其中 $P_i$为概率
ID3和C4.5是基于信息熵的两种算法，这两种算法去选择使数据信息熵减少效果最好的特征，熵减少的幅度越大，那么代表这个特征越重要，我们要把重要特征放在树的顶端，这样构造的决策树比较有效率。

ID3 和C4.5

ID3算法，每次去选择信息熵减少幅度最大的特征、C4.5则使用减少的百分比来衡量。
假如有如下数据：

通过如下步骤来选择构造决策树的第一个特征。

• 计算整体数据的信息熵：
  买电脑的概率为 $P_1=4/6$，不买电脑的概率为 $P_2=2/6$，那么整体数据的信息熵为
  $D = - (P_1 * log_2P_1 + P_2 * log_2P_2) = -(4/6 * log_2 4/6 + 2/6 * log_2 2/6)$
• 计算各个特征对应的条件信息熵
  以性别为例：
  男生的概率为 $P_m = 5/6$
  男生中买的电脑的概率为 $P_{m1} = 3/5$, 不买电脑的概率为 $P_{m2} = 2/5$
  女生的概率为 $P_f = 1/6$
  女生中买的电脑的概率为 $P_{f1} = 1/1$, 不买电脑的概率为 $P_{f2} = 0/1$
  性别对应的条件熵为则是
  $D_{sex} = P_m * (- P_{m1} log_2P_{m1} - P_{m2} log_2P_{m2}) + P_f * (- P_{f1} log_2P_{f1} - P_{f2} log_2P_{f2}) $
  以同样的方式，我们可以得到 学生的条件熵 $D_{student}$以及民族对应的条件熵 $D_{nation}$
  对于ID3算法，它是看信息熵减少的量：
  $Gain_{sex} = D - D_{sex}$
  $Gain_{student} = D - D_{student}$
  $Gain_{nation} = D - D_{nation}$
  上面三个值谁大，就选择对应的特征。
  对于C4.5算法，是信息熵的减少百分比幅度，去除一下 $D$
  $Gain_{sex} = (D - D_{sex}) / D$
  $Gain_{student} = (D - D_{student} ) / D $
  $Gain_{nation} = (D - D_{nation} ) /D $
• 数据划分
  通过选择的特征，将原来的数据集分成两部分。

参考资料