竞赛资料源码-为机器学习的入门者提供多种基于实例的TensorFlow以及自编函数(AnFany)的ML算法程序。.zip

# Decision Tree Theory 决策树主要包括ID3，C4.5以及CART。下面给出三种算法的说明：  C4.5是ID3的改进版，而CART是最常用的，因此本文主要介绍CART。 *** ### CART 首先看下面表格中的示例数据(随机生成，仅供参考)。其中类似年龄，身高，月收入为连续变量，学历，工作为离散变量。 + 如果把**动心**视为目标变量，此问题为**分类问题**。 + 如果把**动心度**视为目标变量，此问题为**回归问题**。 |编号|年龄|学历|工作|月收入(k)|身高(cm)|动心|动心度| |:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| |0001|24|专科|国企|5|175|**N**|0.56| |0002|35|博士|国企|13|180|**N**|0.49| |0003|27|硕士|私企|13|173|**Y**|0.76| |0004|23|硕士|私企|5|180|**N**|0.67| |0005|30|硕士|国企|5|166|**N**|0.58| |0006|22|硕士|国企|13|166|**Y**|0.60| |0007|28|博士|国企|5|175|**Y**|0.73| |0008|38|博士|私企|19|180|**N**|0.40| |0009|23|专科|私企|13|175|**N**|0.52| |0010|30|博士|国企|13|173|**Y**|0.88| CART的目的是生成一个类似下面这样的树：分类树或者回归树。  叶子节点若为Y或者N，是分类树；若是数字，则为回归树。下面分别讲述回归树和分类树的生成方式： * **分类树** ID3算法使用**信息增益**来选择特征，信息增益大的优先选择，这种方式会使得特征值较多的特征容易被选择【*示例数据中的学历可能会比工作优先选择，因为学历有3个值，而工作有2个值*】。 在C4.5算法中，采用了**信息增益比**来选择特征，改进了ID3容易选择特征值多的特征的问题。C4.5也是优先选择较大的。 上述2者都是基于信息论的**熵**模型的，这里面会涉及对数运算，因此计算成本较大。 CART分类树算法使用**基尼系数**，既减少了计算成本，又保留了熵这种运算形式的优点。基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。 + **基尼系数** 对于一个样本集合**S**，假设其包含**m**个不同的值，这**m**个值可看作**m**个不同的类。其中由**类i**组成的集合为**Si**，那么对于属于**类i**的样本点**k**而言，其概率为**P(k)=集合Si的样本个数除去集合S的样本个数**。则基于概率分布的基尼指数定义如下： <a href="http://www.codecogs.com/eqnedit.php?latex=\bg_white&space;\fn_phv&space;{\color{Blue}&space;\mathbf{G(S)}&space;=&space;\mathbf{1}&space;-&space;\sum_{\mathrm{i}=1}^{\mathrm{m}}(\frac{|\mathbf{S_{i}}|}{|\mathbf{S}|})^{2}}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\bg_white&space;\fn_phv&space;{\color{Blue}&space;\mathbf{G(S)}&space;=&space;\mathbf{1}&space;-&space;\sum_{\mathrm{i}=1}^{\mathrm{m}}(\frac{|\mathbf{S_{i}}|}{|\mathbf{S}|})^{2}}" title="{\color{Blue} \mathbf{G(S)} = \mathbf{1} - \sum_{\mathrm{i}=1}^{\mathrm{m}}(\frac{|\mathbf{S_{i}}|}{|\mathbf{S}|})^{2}}" /></a> 其中符号||为计算集合内元素个数的符号，对于m等于2的情况，上面的式子等价与 <a href="http://www.codecogs.com/eqnedit.php?latex=\bg_white&space;\fn_phv&space;{\color{Blue}&space;\mathbf{G(S)}&space;=&space;\mathbf{2}\mathbf{P(k)}*(\mathbf{1}-\mathbf{P(k)})}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\bg_white&space;\fn_phv&space;{\color{Blue}&space;\mathbf{G(S)}&space;=&space;\mathbf{2}\mathbf{P(k)}*(\mathbf{1}-\mathbf{P(k)})}" title="{\color{Blue} \mathbf{G(S)} = \mathbf{2}\mathbf{P(k)}*(\mathbf{1}-\mathbf{P(k)})}" /></a> 如果样本集合**S**，被某个规则R划分为n个数据子集，分别为S1， S2，……， Sn，则此时的计算基尼系数公示如下： <a href="http://www.codecogs.com/eqnedit.php?latex=\bg_white&space;\fn_phv&space;{\color{Blue}&space;\mathbf{G(S,&space;R&space;)}&space;=&space;\sum_{\mathrm{\mathbf{j=1}}}^{\mathrm{\mathbf{n}}}\frac{\mathbf{|Sj|}}{\mathbf{|S|}}\mathbf{G(Sj)}}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\bg_white&space;\fn_phv&space;{\color{Blue}&space;\mathbf{G(S,&space;R&space;)}&space;=&space;\sum_{\mathrm{\mathbf{j=1}}}^{\mathrm{\mathbf{n}}}\frac{\mathbf{|Sj|}}{\mathbf{|S|}}\mathbf{G(Sj)}}" title="{\color{Blue} \mathbf{G(S, R )} = \sum_{\mathrm{\mathbf{j=1}}}^{\mathrm{\mathbf{n}}}\frac{\mathbf{|Sj|}}{\mathbf{|S|}}\mathbf{G(Sj)}}" /></a> 在CART算法中，上述n的值一定为2。因为每一次分裂，都是把数据集合一分为二。 针对离散、连续的变量，下面给出具体的计算基尼系数的步骤： + **离散变量：以工作为例** 1. 将数据集合D分为**Dg1=D(学历=国企)**以及**Dg2=D(学历!=国企)**，其中Dg1中动心构成的集合为**Mg1**；Dg2中动心构成的集合为**Mg2**; 此时的基尼系数计算如下： <a href="http://www.codecogs.com/eqnedit.php?latex=\\&space;{\color{Blue}&space;\boldsymbol{Mg1=[N,&space;N,&space;N,Y,Y,Y]}}\\&space;\\&space;{\color{Blue}&space;\boldsymbol{Mg2=[N,&space;N,N,Y]}}\\&space;\\&space;{\color{Blue}&space;\mathbf{G(D,gongzuo=guoqi)=\frac{|Mg1|}{|D|}G(Mg1)&plus;\frac{|Mg2|}{|D|}G(Mg2)}}\\&space;\\&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;={\color{Blue}&space;\boldsymbol{\frac{6}{10}[1-(\frac{3}{6})^{2}-(\frac{3}{6})^{2}]&plus;\frac{4}{10}[1-(\frac{3}{4})^{2}-(\frac{1}{4})^{2}]}}\\&space;\\&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;={\color{Blue}&space;\boldsymbol{0.45}}" target="_blank"><img src="http://latex.codecogs.com/gif.latex?\\&space;{\color{Blue}&space;\boldsymbol{Mg1=[N,&space;N,&space;N,Y,Y,Y]}}\\&space;\\&space;{\color{Blue}&space;\boldsymbol{Mg2=[N,&space;N,N,Y]}}\\&space;\\&space;{\color{Blue}&space;\mathbf{G(D,gongzuo=guoqi)=\frac{|Mg1|}{|D|}G(Mg1)&plus;\frac{|Mg2|}{|D|}G(Mg2)}}\\&space;\\&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;={\color{Blue}&space;\boldsymbol{\frac{6}{10}[1-(\frac{3}{6})^{2}-(\frac{3}{6})^{2}]&plus;\frac{4}{10}[1-(\frac{3}{4})^{2}-(\frac{1}{4})^{2}]}}\\&space;\\&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;\cdots&space;={\color{Blue}&space;\boldsymbol{0.45}}" title="\\ {\color{Blue} \boldsymbol{Mg1=[N, N, N,Y,Y,Y]}}\\ \\ {\color{Blue} \boldsymbol{Mg2=[N, N,N,Y]}}\\ \\ {\color{Blue} \mathbf{G(D,gongzuo=guoqi)=\frac{|Mg1|}{|D|}G(Mg1)+\frac{|Mg2|}{|D|}G(Mg2)}}\\ \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots ={\color{Blue} \boldsymbol{\frac{6}{10}[1-(\frac{3}{6})^{2}-(\frac{3}{6})^{2}]+\frac{4}{10}[1-(\frac{3}{4})^{2}-(\frac{1}{4})^{2}]}}\\ \\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots ={\color{Blue} \boldsymbol{0.45}}" /></a> 因为工作只有2个变量，因此按照工作为私企和工作为国企的基尼系数是相同的。 + **连续变量：以月收入为例** 1. 首先将月收入的值去重后，按照从小到大的排列顺序为[5, 13, 19],相邻的数值取平均值得到序列[9, 16]。类似于离散变量的情况，以9为例：将数据集分为Dn9=D(月收入<9)以及Dm9=D(月收入>9)，相应的动心组成的集合分别为**Mn9,Mm9**。 下面给出计算基尼系数的过程： <a href="http://www.codecogs.com/eqnedit.php?latex=\\&space;{\color{Blue}&space;\boldsymbol{Mn9=[N,&space;N,&space;N,Y]}}\\&space;\\&space;{\color{Blu