从零基础开始参加了几场数据挖掘方面的比赛，每次比赛都会学到不少东西，自从上次在 elo 的 kernel 中看见很多人都使用 LightGBM、XGBoost，那之后我也开始用起了这些，但是却从未花时间去了解过这是究竟是什么，其内部工作原理是怎么样的，正好这段时间在参加df平台的消费者人群画像—信用智能评分这一比赛，做起了调参，但因为对其内部并不是很收悉，便准备好好学习有关树模型方面的内容，并写下这系列的博客。这里将从最基础的决策树开始讲起。
概述
决策树（decision tree）是一类常见的机器学习方法。类似于流程图，一颗决策树包含一个根节点、若干个内部节点和叶子节点，每一个树节点表示对一个特征或属性的测试，每一个分支代表一个属性的输出，每一个叶子节点对应一种决策结果。从根节点到每个叶节点的路径对应了一个判定测试序列。其学习的基本流程遵循分治（divide-and-conquer）策略。
算法
输入：训练集\\(D=\\{(x_1,y_1),(x_2,y_2),... ,(x_n,y_n)\\}\\)
属性集\\(A=\\{a_1,a_2,...,a_n\\}\\\\\\)
过程：函数\\(TreeGenerate(D,A)\\)
\\(1：生成节点 node;\\)
\\(2：if\\) $ D $ $ 中样本全属于同一类别$ $ C$ $ then$
\\(3：\\quad将\\) $ node$ \\(标 记为\\) $ C$ $ 类叶节点;$ $ return$
\\(4：end\\) $ if$
\\(5：if\\) $ A=\\emptyset $ $ OR$ $ D$ $ 中样本在A上取值相同$ $ then $
\\(6：\\quad 将node标记为叶节点，其类别标记为D中样本数最多的类；then\\)
\\(7：end\\) \\(if\\)
\\(8:从A中选择最优划分属性\\)
$9：for $ $ a_* $ \\(的每一个值\\) $ a_{*}^{v}$ $ do$
\\(10:\\quad 为node生成一个分支；令D_v表示D中在a_*上取值为a_{*}^{v} 的样本子集：\\)
$11:\\quad if $ \\(D_v\\) \\(为空\\) \\(then\\)
\\(12：\\quad\\quad将分支节点标记为叶节点，其类别标记为D中样本最多的类；return\\)
\\(13：\\quad else\\)
\\(14：\\quad\\quad以TreeGenerate(D_v,A\\) \\(\\{a_*\\})为分支节点\\)
\\(15：\\quad end\\) \\(if\\)
\\(16：end\\) \\(for\\)
输出：以\\(node\\)为节点的一颗决策树
划分选择
从上面的算法中可以看出，最重要的一步就是第8行选取最优划分，但我们该如何选取最优划分呢？这里就涉及到了信息增益的概念。在讲解信息增益前，先来了解了解信息熵和条件熵。
信息熵（information entropy）是度量样本集合纯度最常用的一种指标，它可以衡量一个随机变量出现的期望值。如果信息的不确定性越大，熵的值也就越大，出现的各种情况也就越多。
假设当前样本集合\\(D\\)中第\\(k\\)类样本所占比例为\\(p_k(k=1,2,\\cdots,|n|)\\)，则\\(D\\)的信息熵为：
\\[ Ent(D）=-\\sum_{k=1}^{|n|}p_k\\log_2p_k \\tag{1} \\]
定义：\\(0log0 = 0\\)
条件熵（conditional entropy）表示在已知随机变量X的条件下随机变量Y的不确定性。定义随机变量X给定的条件下随机变量Y的概率分布的熵：
\\[ Ent(Y|X)=\\sum_{k=1}^{n}p_kH(Y|X=x_k) \\tag{2} \\]
假定离散属性（特征）a有V个可能取值\\(\\{a^1,a^2,\\cdots,a^V\\}\\)，若使用a来对样本集D进行划分，则会产生V个分支节点，其中第\\(v\\)个分支节点包含了\\(D\\)中所有在属性（特征）a上取值为\\(a^v\\)的样本，记作\\(D^v\\)。那么，特征\\(a^v\\)的条件概率分布为 \\(\\frac{|D^v|}{|D|}\\)，我们可得信息增益（information gain）：
\\[ Gain(D,a)=Ent(D)-Ent(D|a) \\tag{3} \\\\ =Ent(D)-\\sum_{v=1}^{V}\\frac{|D^v|}{D}Ent(D^v) \\]
由上式可知，信息增益是相对于特征而言的，定义为集合\\(D\\)的信息熵与特征\\(a\\)下\\(D\\)的条件熵之差。
这里回到一开始的问题，如何选择最优划分？方法是对训练数据集\\(D\\)，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。
然而，有时存在这么一个问题，以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。对这一问题的解决方法是使用信息增益比（information gain ratio）：
特征A对训练数据集D的信息增益比\\(g_R(D,A)\\)定义为其信息增益\\(g(D,A)\\)与训练数据集D关于A的值的熵\\(H_A(D)\\)之比，即
\\[ g_R(D,A)=\\frac{g(D,A)}{H_A(D)} \\tag{4} \\]
其中，\\(H_A(D)=-\\sum_{i=1}^n\\frac{|D_i|}{|D|}log_2\\frac{|D_i|}{|D|}\\)，n是特征A取值的个数。
结语
这篇文章中介绍了决策树的一些基本理论，对于决策树的优化以及ID3、C4.5、CART的代码实现将在后面的文章中给出。
