AI red teamer （人工智能红队）系列 05 – 人工智能基础 – 决策树
<p><code>决策树</code>是一种流行的 <code>监督学习</code>算法，适用于 <code>分类</code>和 <code>回归</code>任务。决策树以其直观的树状结构而著称，这使得它们易于理解和解释。从本质上讲，决策树创建了一个模型，通过学习从数据特征中推断出的简单决策规则来预测目标变量的值。</p><p>想象一下，你正试图根据天气决定是否打网球。决策树会把这个决定分解成一系列简单的问题：天气晴朗吗？有风吗？是否潮湿？根据这些问题的答案，决策树会引导你做出最终决定：打网球还是不打网球。</p>
<p>决策树由三个主要部分组成：</p>
<ul>
<li><code>根节点：</code> 它代表树的起点，包含整个数据集。</li>
<li><code>内部节点：</code> 这些节点表示数据的特征或属性。每个内部节点根据不同的决策规则分为两个或多个子节点。</li>
<li><code>叶节点：</code> 这些是树的终端节点，代表最终结果或预测。</li>
</ul>
<h2>建立决策树</h2>
<p>构建决策树需要在每个节点上选择最佳特征来分割数据。这种选择基于 <code>吉尼不纯度</code>、<code>熵</code>或 <code>信息增益</code>等度量，它们量化了拆分后产生的子集的同质性。我们的目标是创建能产生越来越纯的子集的拆分，其中每个子集中的数据点主要属于同一类别。</p>
<h3>基尼不纯度/基尼指数</h3>
<p><code>基尼不纯度</code>测量从集合中随机选择一个元素的<strong>错误分类概率</strong>。基尼不纯度越低，表示集合越纯粹。基尼不纯度的计算公式为</p>
<pre><code class="language-python">Gini(S) = 1 - Σ (pi)^2
</code></pre>
<p>Python</p>
<ul>
<li><code>S</code> 是数据集。</li>
<li><code>pi</code> 是属于 <code>i</code> 类别的元素在集合中所占的比例。</li>
</ul>
<p>考虑一个包含两个类别：A和B的数据集S。假设数据集中有30个属于类别A的实例和20个属于类别B的实例。</p>
<ul>
<li><code>A</code> 类的比例：<code>pA = 30 / (30 + 20) = 0.6</code>。</li>
<li><code>B 类的比例</code>：<code>pB = 20 / (30 + 20) = 0.4</code>。</li>
</ul>
<p>该数据集的基尼不纯度为</p>
<pre><code class="language-python">Gini(S) = 1 - (0.6^2 + 0.4^2) = 1 - (0.36 + 0.16) = 1 - 0.52 = 0.48
</code></pre>
<p>Python</p>
<h3>熵</h3>
<p><code>熵</code>表示集合的无序性或不确定性。熵越小，表示集合越均匀。熵的计算公式为</p>
<pre><code class="language-python">Entropy(S) = - Σ pi * log2(pi)
</code></pre>
<p>Python</p>
<ul>
<li><code>S</code> 是数据集。</li>
<li><code>pi</code> 是属于 <code>i</code> 类别的元素在集合中所占的比例。</li>
</ul>
<p>使用相同的数据集 S，其中包含30个属于类别A的实例和20个属于类别B的实例：</p>
<ul>
<li><code>A</code> 类的比例：<code>pA = 0.6</code>。</li>
<li><code>B 类的比例</code>：<code>pB = 0.4</code>。</li>
</ul>
<p>该数据集的熵值为</p>
<pre><code class="language-python">Entropy(S) = - (0.6 * log2(0.6) + 0.4 * log2(0.4))
= - (0.6 * (-0.73697) + 0.4 * (-1.32193))
= - (-0.442182 - 0.528772)
= 0.970954
</code></pre>
<p>Python</p>
<h3>信息增益</h3>
<p><code>信息增益</code>用于度量根据特定特征拆分数据集所实现的熵减。分割时会选择信息增益最大的特征。信息增益的计算公式为</p>
<pre><code class="language-python">Information Gain(S, A) = Entropy(S) - Σ ((|Sv| / |S|) * Entropy(Sv))
</code></pre>
<p>Python</p>
<ul>
<li><code>S</code> 是数据集。</li>
<li><code>A</code> 是用于分割的特征。</li>
<li><code>Sv</code> 是特征 <code>A</code> 具有值 <code>v</code> 的 <code>S</code> 的子集。</li>
</ul>
<p>考虑一个包含50个实例的数据集S，其中有两个类别：A和B。假设我们考虑的特征 <code>F</code> 可以有两个值：<code>1</code> 和 <code>2</code> 。数据集的分布如下：</p>
<ul>
<li>对于 <code>F = 1</code>：30 个实例，20 个 <code>A 类</code>，10 个 <code>B 类</code></li>
<li>对于 <code>F = 2</code>：20 个实例，10 个 <code>A 类</code>，10 个 <code>B 类</code></li>
</ul>
<p>首先，计算整个数据集 <code>S</code> 的熵：</p>
<pre><code class="language-python">Entropy(S) = - (30/50 * log2(30/50) + 20/50 * log2(20/50))
= - (0.6 * log2(0.6) + 0.4 * log2(0.4))
= - (0.6 * (-0.73697) + 0.4 * (-1.32193))
= 0.970954
</code></pre>
<p>Python</p>
<p>接下来，计算每个子集 <code>Sv</code> 的熵：</p>
<ul>
<li>对于 <code>F = 1</code>：
<ul>
<li><code>A</code> 类的比例：<code>pA = 20/30 = 0.6667</code>。</li>
<li><code>B 类的比例</code>：<code>pB = 10/30 = 0.3333</code>。</li>
<li>Entropy(S1) = <code>- (0.6667 * log2(0.6667) + 0.3333 * log2(0.3333)) = 0.9183</code></li>
</ul>
</li>
<li>对于 <code>F = 2</code>：
<ul>
<li><code>A</code> 类的比例：<code>pA = 10/20 = 0.5</code>。</li>
<li><code>B 类的比例</code>：<code>pB = 10/20 = 0.5</code>。</li>
<li>Entropy(S2) = <code>- (0.5 * log2(0.5) + 0.5 * log2(0.5)) = 1.0</code></li>
</ul>
</li>
</ul>
<p>现在，计算子集的加权平均熵：</p>
<pre><code class="language-python">Weighted Entropy = (|S1| / |S|) * Entropy(S1) + (|S2| / |S|) * Entropy(S2)
= (30/50) * 0.9183 + (20/50) * 1.0
= 0.55098 + 0.4
= 0.95098
</code></pre>
<p>Python</p>
<p>最后，计算信息增益：</p>
<pre><code class="language-python">Information Gain(S, F) = Entropy(S) - Weighted Entropy
= 0.970954 - 0.95098
= 0.019974
</code></pre>
<p>Python</p>
<h3>构建树</h3>
<p>树从根节点开始，根据其中一个标准（基尼不纯度、熵或信息增益）选择最能分割数据的特征。该特征成为内部节点，并为该特征的每个可能值或值范围创建分支。然后根据这些分支将数据划分为子集。这个过程会对每个子集进行递归，直到满足停止标准为止。</p>
<p>当满足以下条件之一时，树就会停止延申：</p>
<ul>
<li><code>最大深度</code>：树达到指定的最大深度，防止树变得过于复杂和可能过度拟合数据。</li>
<li><code>最小数据点数</code>：节点中的数据点数低于指定阈值，以确保分割是有意义的，而不是基于很小的子集。</li>
<li><code>纯节点</code>：节点中的所有数据点都属于同一类别，表明进一步分割不会提高子集的纯度。</li>
</ul>
<h2>举例：打网球</h2>
<p>让我们仔细研究一下 "打网球 "的例子，以说明决策树在实际中是如何工作的。</p>
<p>想象一下，你有一个数据集，其中包含历史天气状况以及您是否在这些日子里打网球。例如</p>
<table>
<thead>
<tr>
<th>PlayTennis</th>
<th>Outlook_Overcast</th>
<th>Outlook_Rainy</th>
<th>Outlook_Sunny</th>
<th>Temperature_Cool</th>
<th>Temperature_Hot</th>
<th>Temperature_Mild</th>
<th>Humidity_High</th>
<th>Humidity_Normal</th>
<th>Wind_Strong</th>
<th>Wind_Weak</th>
</tr>
</thead>
<tbody>
<tr>
<td>No</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
</tr>
<tr>
<td>Yes</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
</tr>
<tr>
<td>No</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
</tr>
<tr>
<td>No</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
</tr>
<tr>
<td>Yes</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
</tr>
<tr>
<td>Yes</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
</tr>
<tr>
<td>No</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
</tr>
<tr>
<td>Yes</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
</tr>
<tr>
<td>No</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>True</td>
<td>False</td>
</tr>
<tr>
<td>No</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
<td>True</td>
<td>False</td>
</tr>
</tbody>
</table>
<p>数据集包括以下特征：</p>
<ul>
<li><code>天气:</code> Sunny, Overcast, Rainy</li>
<li><code>温度:</code> Hot, Mild, Cool</li>
<li><code>湿度:</code> High, Normal</li>
<li><code>风:</code> Weak, Strong</li>
</ul>
<p>目标变量是 <code>打网球：</code> Yes or No。</p>
<p>决策树算法将对该数据集进行分析，以确定最能将 "是 "实例与 "否 "实例区分开来的特征。首先，它将计算每个特征的 <code>信息增益</code>或 <code>吉尼杂质</code>，以确定哪个特征能提供最有信息量的分割。</p>
<p>决策树算法将分析这个数据集以识别最佳特征，这些特征可以将“是”与“否”分开。它将首先计算每个特征的信息增益或基尼不纯度，以确定哪个特征能提供最有信息量的分割。</p>
<p>例如，算法可能会发现 <code>天气</code> 特征可提供最高的信息增益。这意味着根据晴天、阴天或雨天对数据进行拆分，可以最显著地减少熵或杂质。</p>
<p>决策树的根节点将是 <code>天气</code> 特征，并有三个分支：晴天、阴天和雨天。根据这些分支，数据集将分为三个子集。</p>
<p>接下来，算法将分析每个子集，以确定下一次拆分的最佳特征。例如，在 "晴天 "子集中，<code>湿度</code>可能会提供最高的信息增益。这将导致另一个具有 "高 "和 "正常 "分支的内部节点。</p>
<p>这一过程一直递归进行，直到满足停止标准，如达到最大深度或节点中数据点的最小数量。最终结果是一个树状结构，每个内部节点都有决策规则，叶节点则有预测结果（打网球： Yes or No）。</p>
<h2>数据假设</h2>
<p>决策树的优势之一是对数据的假设最少：</p>
<ul>
<li><code>无线性假设：</code> 决策树可以处理特征与目标变量之间的线性和非线性关系。这使得决策树比线性回归等假设线性关系的算法更加灵活。</li>
<li><code>无正态性假设：</code> 数据不需要呈正态分布。这与某些需要正态性才能做出有效推论的统计方法形成了鲜明对比。</li>
<li><code>处理异常值：</code> 决策树对异常值的处理相对稳健。由于决策树是根据特征值对数据进行分区，而不是依赖于基于距离的计算，因此异常值不太可能对决策树结构产生重大影响。</li>
</ul>
<p>这些最低限度的假设有助于决策树的多功能性，使其无需大量预处理或转换即可应用于各种数据集和问题。</p>
这公式看着头大咯
页:
[1]