第3章：决策树分类器 - 理论

作者：Savan Patel
时间：2017年5月11日
原文：原文：https://medium.com/machine-learning-101/chapter-3-decision-trees-theory-e7398adac567

H = 熵

迎阅读监督学习的第三个基本分类算法。决策树。像前面的章节（第1章：朴素贝叶斯和第2章：SVM分类器）一样，本章也分为两部分：理论和编码练习。

在这一部分，我们将讨论理论和决策树背后的工作。我们将看到算法的一些数学方面，即熵和信息增益。在第二部分中，我们修改了sklearn库中决策树分类器的垃圾邮件分类代码。我们将比较Naive Bayes和SVM的准确性。

拒绝和招聘的黑暗面！

0.动机

假设我们有以下两个类的图，由黑色圆圈和蓝色方块表示。是否可以绘制一条分离线？也许没有。

你能为这些类画出单一分界线吗？

我们需要不止一行，分成几类。与下图类似的东西：

对于x的阈值和y的阈值，我们需要两条线。

我们在这里需要两条线，一条线根据x的阈值分离，另一条线条用于y的阈值。

正如您现在猜到的那样，决策树会尝试做什么。

决策树分类器通过识别行重复地将工作区域（绘图）划分为子部分。（重复，因为可能存在两个相同类别的远距离区域，如下图所示）。

image.png

那么什么时候终止？

它要么分成纯粹的类（只包含单个类的成员）
满足分类器属性的一些标准。

我们很快就会看到这两点。

在以下部分中，我们定义了与决策树相关的几个术语，然后使用示例示例执行这些计算。

1.杂质

在上面的部门中，我们明确地分类了。但如果我们有以下案例怎么办？

杂质是指我们将一个阶级划分为另一个阶段的痕迹。这可能是由于以下原因引起的

我们没有可用的功能来分类。
我们容忍一定比例的杂质（我们停止进一步分割）以获得更快的性能。（准确性和性能之间总是存在折衷）。

例如，在第二种情况下，当我们剩下x个较少数量的元素时，我们可以停止我们的除法。这也称为基尼杂质。

基于一些功能划分

2.熵

熵是元素的随机性程度，换句话说，它是**杂质的量度。****在数学上，它可以借助于项目的概率来计算：

p(x) 是项目x的概率

它是概率乘以项目x概率的对数的负和。

例如，
如果我们在投掷事件中将项目作为骰子面部出现次数为1123，
则熵为
   p（1）= 0.5 
   p（2）= 0.25 
   p（3）= 0.25 
entropy =  - （0.5 * log（0.5） ）） - （0.25 * log（0.25）） - （0.25 * log（0.25）
        = 0.45

3.信息增益

假设我们有多个功能来划分当前工作集。我们应该选择什么功能进行划分？或许可以减少杂质。

假设我们将类划分为多个分支，如下所示，任何节点的信息增益定义为

信息增益（n）= 
  熵（x） - （[加权平均] *熵（特征的子项））

这需要一点解释！

假设我们有以下课程与初级合作

112234445

假设我们根据属性划分它们：可以被2整除

image.png

根
熵：0.66 左子熵：0.45，加权值=（4/9）* 0.45 = 0.2 
右子熵：0.29，加权值=（5/9）* 0.29 = 0.16
信息增益 = 0.66  -  [0.2 + 0.16] = 0.3

如果我们将决策作为素数而不是除以2，那么检查我们得到的信息增益**。****对于这种情况哪一个更好？

每个阶段的决策树选择提供最佳信息增益的决策树。当信息增益为0表示该功能根本不分割工作集。

如果你喜欢这个，请点击心脏（❤）图标并传播这个词。

让我们解决一个例子

现在您已经了解了关于决策树的基本知识，让我们解决一些示例并了解它的工作原理。

假设我们有以下数据可以在各种条件下打高尔夫球。

image.png

现在如果天气状况如下：

展望：多雨，温度：凉爽，湿度：高，风：虚假

我们应该打高尔夫吗？

我们在开始时有结果，因为NNYYYNYN（Y =是和N =否）按给定顺序拍摄。此根节点处的熵为0.3
现在尝试划分各种预测器的前景，温度，湿度和Windy。
计算每种情况下的信息增益。哪一个信息获得最高？
例如，如果我们基于Outlook划分，我们将划分为
Rainy：NNN（entropy = 0）
Sunny：YYN（entropy = 0.041）
阴天：YY（entropy = 0）
因此，信息增益= 0.3  -  [0 +（3/8）* 0.041 + 0] 
                    = 0.28
尝试其他案例。
基于Outlook划分时，信息增益最大。
现在Rainy和Overcast的杂质是0.我们在这里停下来。
接下来我们需要将Sunny分开，
如果我们除以Windy，我们将获得最大的信息收益。
Sunny 
YYN 
  Windy？是的：N 
         否：YY
所以决策树看起来像下图所示的东西。
没有预测数据是
Outlook：Rainy，Temperature：Cool，Humidity：High，Windy：False
根据结果从树上流下来，我们首先检查Rainy？
所以答案是否定的，我们不打高尔夫球。

image.png

最后的想法

基于最大信息增益有效划分是决策树分类器的关键。然而，在现实世界中，数百万个数据在实际上不可行时划分为纯类（可能需要更长的训练时间），因此当满足某些参数（例如杂质百分比）时，我们停在树节点中的点。我们将在编码练习中看到这一点。

在接下来的部分，我们将使用Python中sklearn库代码决策树分类。我们将通过容忍一些杂质来调整一些参数以获得更高的准确度。

我希望本节有助于理解Decision树分类器背后的工作。