机器学习笔记——决策树_机器学习决策树笔记

作者：Li_阴宅 | 2024-07-16 09:03:33

踩

机器学习决策树笔记

一.什么是决策树

1.1 直观理解决策树

决策树是一种基本的分类与回归方法。决策树由结点和有向边组成，其中结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类别。

我们可以把决策树直观地理解成一个问问题的机器，每到达一个内部结点就开始根据结点里的特征来对样本进行提问，接着根据样本的回答做出决策进入下一层，直到到达叶结点。举个例子，假设有一个特征是天气，它有三个特征值，分别是晴天，阴天，雨天。

当进入到决策结点时，会根据结点中的特征对样本提问，比如样本的天气是晴天，就会进入对应到晴天的下一层结点。

1.2 如何构建决策树

以上是用决策树对样本进行预测，那么我们该如何构建一个决策树呢？我们希望构建的决策树具有良好的泛化能力，那就希望我们对每个结点的特征都有合理的选择。不同的特征选择顺序构建出来的决策树的分类效果也不同。

大致的构建思路是：从根结点开始遍历没被使用过的特征，如果某一特征对于原本混乱的样本的划分最有序，便采用这个特征作为决策结点（可以看作一种贪心思想），然后递归到它的子节点，然后不断重复这过程，直到决策树构建完毕。

举个例子，假设有十个样本，每个样本都有三个特征值，分别是天气，温度，湿度，这三个特征共同决定是否举办篮球赛。现在分别用这三个特征对样本进行划分。（随便造的数据，真实性不可靠）

对天气进行划分

对温度进行划分

对湿度进行划分

想要知道哪个特征对样本的划分效果更好，就要引入一个概念——熵。

二.特征划分

2.1 熵

熵可以理解为样本类别的混乱程度，混乱程度越高，熵就越大，反之则越小。

假设样本类别的不纯度(概率密度)为 $P(X=x_i)=p_i ,i=1,2,...,n$

则熵的计算公式为 $H(X)=-\sum_{i=1}^kp_i\ log_{2}p_i$

举个例子

由图可 $p_0=\frac{1}{2},p_1=\frac{1}{2}$

计算其熵为 $H(X)\ =\ -\sum_{i=1}^{2}p_i\ log_{2}p_i$

$= -(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})$

$=1$

2.2 条件熵

如何计算特征划分后的熵呢，我们引入条件熵的概念。

假设在某一特征条件 $y_i$ 下结点集合 $x_i$ 的概率分布为 $P(X=x_i,Y=y_i)=p_{ij},i=1,2,...,n$

我们定义条件熵为 $H(Y|X)=\sum_{i=1}^{k}p_iH(Y|X=x_i)$

对于特征取温度时

我们有 $p_0=\frac{3}{10}$ , $p_1=\frac{3}{10}$ , $p_2=\frac{4}{10}$

因此条件熵为 $H(Y|X)=\sum_{i=1}^{3}p_iH(Y|X=x_i)$

$=p_0H(Y|X=x_0)+p_1H(Y|X=x_1)+p_2H(Y|X=x_2)$ $=\frac{3}{10} (-(\frac{1}{3}log_{2}{\frac{1}{3}}+\frac{2}{3}log_{2}{\frac{2}{3}}))+\frac{3}{10} (-(\frac{1}{3}log_{2}{\frac{1}{3}}+\frac{2}{3}log_{2}{\frac{2}{3}}))+\frac{4}{10} (-(\frac{2}{4}log_{2}{\frac{2}{4}}+\frac{2}{4}log_{2}{\frac{2}{4}}))$