前剪枝算法

① R语言-17决策树

是一个预测模型，分为回归决策树和分类决策树，根据已知样本训练出一个树模型，从而根据该模型对新样本因变量进行预测，得到预测值或预测的分类

从根节点到叶节点的一条路径就对应着一条规则．整棵决策树就对应着一组表达式规则。叶节点就代表该规则下得到的预测值。如下图决策树模型则是根据房产、结婚、月收入三个属性得到是否可以偿还贷款的规则。

核心是如何从众多属性中挑选出具有代表性的属性作为决策树的分支节点。

最基本的有三种度量方法来选择属性

1. 信息增益（ID3算法）

信息熵

一个信源发送出什么符号是不确定的，衡量它可以根据其出现的概率来度量。概率大，出现机会多，不确定性小；反之不确定性就大。不确定性函数f是概率P的 减函数 。两个独立符号所产生的不确定性应等于各自不确定性之和，即f(P1,P2)=f(P1)+f(P2)，这称为可加性。同时满足这两个条件的函数f是对数函数，即

在信源中，考虑的不是某一单个符号发生的不确定性，而是要考虑这个信源所有可能发生情况的平均不确定性。因此，信息熵被定义为

决策树分类过程

2、增益率（C4.5算法）
由于信息增益的缺点是：倾向于选择具有大量值的属性，因为具有大量值的属性每个属性对应数据量少，倾向于具有较高的信息纯度。因此增益率使用【信息增益/以该属性代替的系统熵（类似于前面第一步将play换为该属性计算的系统熵】这个比率，试图克服这种缺点。
g(D,A)代表D数据集A属性的信息增益，

3. 基尼指数（CART算法）

基尼指数：

表示在样本集合中一个随机选中的样本被分错的概率。越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高。

假设集合中有K个类别，则：

说明:

1. pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)

2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和

3. 当为二分类是，Gini(P) = 2p(1-p)

基尼指数是将属性A做二元划分，所以得到的是二叉树。当为离散属性时，则会将离散属性的类别两两组合，计算基尼指数。

举个例子：

如上面的特征Temperature，此特征有三个特征取值： “Hot”，“Mild”， “Cool”，
当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：

对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：

决策数分类过程

先剪枝 ：提前停止树的构建对树剪枝，构造树时，利用信息增益、统计显着性等，当一个节点的划分导致低于上述度量的预定义阈值时，则停止进一步划分。但阈值的确定比较困难。
后剪枝 ：更为常用，先得到完全生长的树，再自底向上，用最下面的节点的树叶代替该节点
CART使用代价复杂度剪枝算法 ：计算每个节点剪枝后与剪枝前的代价复杂度，如果剪去该节点，代价复杂度较小（复杂度是树的结点与树的错误率也就是误分类比率的函数），则剪去。
C4.5采用悲观剪枝 ：类似代价复杂度，但CART是利用剪枝集评估代价复杂度，C4.5是采用训练集加上一个惩罚评估错误率

决策树的可伸缩性

ID3C4.5CART都是为较小的数据集设计，都限制训练元祖停留再内存中，为了解决可伸缩性，提出了其它算法如
RainForest(雨林）：对每个属性维护一个AVC集，描述该结点的训练元组，所以只要将AVC集放在内存即可
BOAT自助乐观算法：利用统计学，创造给定训练数据的较小样本，每个样本构造一个树，导致多颗树，再利用它们构造1颗新树。优点是可以增量的更新，当插入或删除数据，只需决策树更新，而不用重新构造。

决策树的可视化挖掘
PBC系统可允许用户指定多个分裂点，导致多个分支，传统决策树算法数值属性都是二元划分。并且可以实现交互地构建树。

rpart是采用cart算法，连续型“anova”;离散型“class”;

2）进行剪枝的函数：prune()

3）计算MAE评估回归树模型误差，这里将样本划分成了训练集和测试集，testdata为测试集
rt.mae为根据训练集得到的决策树模型对测试集因变量预测的结果与测试集因变量实际值得到平均绝对误差

② 决策树的决策树的剪枝

剪枝是决策树停止分支的方法之一，剪枝有分预先剪枝和后剪枝两种。预先剪枝是在树的生长过程中设定一个指标，当达到该指标时就停止生长，这样做容易产生“视界局限”，就是一旦停止分支，使得节点N成为叶节点，就断绝了其后继节点进行“好”的分支操作的任何可能性。不严格的说这些已停止的分支会误导学习算法，导致产生的树不纯度降差最大的地方过分靠近根节点。后剪枝中树首先要充分生长，直到叶节点都有最小的不纯度值为止，因而可以克服“视界局限”。然后对所有相邻的成对叶节点考虑是否消去它们，如果消去能引起令人满意的不纯度增长，那么执行消去，并令它们的公共父节点成为新的叶节点。这种“合并”叶节点的做法和节点分支的过程恰好相反，经过剪枝后叶节点常常会分布在很宽的层次上，树也变得非平衡。后剪枝技术的优点是克服了“视界局限”效应，而且无需保留部分样本用于交叉验证，所以可以充分利用全部训练集的信息。但后剪枝的计算量代价比预剪枝方法大得多，特别是在大样本集中，不过对于小样本的情况，后剪枝方法还是优于预剪枝方法的。

③ 模型剪枝

深度学习网络模型从卷积层到全连接层存在着大量冗余的参数，大量神经元激活值趋近于0，将这些神经元去除后可以表现出同样的模型表达能力，这种情况被称为过参数化，而对应的技术则被称为模型剪枝。

网络剪枝的过程主要分以下几步：

在实践过程中我们可以感受到大的网络比小的网络更容易训练，而且也有越来越多的实验证明大的网络比小的网络更容易收敛到全局最优点而不会遇到局部最优点和鞍点的问题。解释这一想象的一个假设是大乐透假设（Lottery Ticket Hypothesis）。

在下图中，首先我们使用一个大的网络然后随机初始化一组参数，这组参数用红色表示，然后训练后得到紫色的参数，接着进行网络剪枝。我们再尝试使用剪枝的网络结构随机初始化一组参数然后训练发现这种方式没能取得剪枝得到的效果，而如果用大的网络中对应的初始化参数来初始化这个剪枝的网络结构然后再进行训练，就发现可以取得较好的效果：

大乐透假设可以用来解释这个现象，在买大乐透时买得越多就越容易中奖，同样的这里我们假设一个大的网络中包含很多小的网络，这些小的网络结构有的可以训练成功而有的不可以训练成功，只要有一个训练成功，整个大的网络结构就可以训练成功，因此我们可以把多余的网络结构剪枝掉。

与大乐透假设不同的是《Rethinking the Value of Network Pruning》这篇得出了与其看似矛盾的假设。在下表中的实验中使用了不同的模型进行试验，表中Fined-tuned表示剪枝后的模型，Scratch-E和Scratch-B表示随机初始化剪枝网络的参数后训练的模型，只是Scratch-B训练了更多的epoch。可以看到随机初始化剪枝网络的参数后训练的模型也取得了不错的效果，这样就看起来和大乐透假设的实验结果相矛盾。事实上两篇paper的作者均对这种结果进行了回应，可以在网上找到回应的内容，这里不做赘述。

在进行网络剪枝时我们可以选择剪枝权重或者剪枝神经元。下图中进行了权重的剪枝：

剪枝权重的问题是会造成网络结构的不规则，在实际操作中很难去实现也很难用GPU去加速。下图展示了对AlexNet进行weight pruning后使用不同的GPU加速的效果，折线表示了对每一层的权重的剪枝的比例，被剪掉的权重大约占比95%左右，然后使用不同GPU加速发现加速效果并不好，这是因为剪枝做成了网络结构的不规则，因此难以用GPU进行加速。在进行实验需要使用weight pruning时可以使用将被剪枝的权重设置成0的方法。

而使用Neuron pruning就不会遇到上述问题，Neuron pruning后的网络结构仍然是规则的，因此仍然可以使用GPU进行加速。

其中重点在于两个，一个是如何评估一个连接的重要性，另一个是如何在剪枝后恢复模型的性能。

由于特征的输出是由输入与权重相乘后进行加权，权重的幅度越小，对输出的贡献越小，因此一种最直观的连接剪枝方法就是基于权重的幅度，如L1/L2范数的大小。这样的方法只需要三个步骤就能完成剪枝

当然这类框架还有可以改进之处，比如Dynamic network surgery框架[4]观察到一些在当前轮迭代中虽然作用很小，但是在其他轮迭代中又可能重要，便在剪枝的基础上增加了一个spliciing操作，即对一些被剪掉的权重进行恢复，如下：

基于权重幅度的方法原理简单，但这是比较主观的经验，即认为权重大就重要性高，事实上未必如此。而另一种经典的连接剪枝方法就是基于优化目标，根据剪枝对优化目标的影响来对其重要性进行判断，以最优脑损伤(Optimal Brain Damage, OBD)方法为代表，这已经是上世纪90年代的技术了。

Optimal Brain Damage首先建立了一个误差函数的局部模型来预测扰动参数向量对优化目标造成的影响。具体来说用泰勒级数来近似目标函数E，参数向量U的扰动对目标函数的改变使用泰勒展开后如下：

其中gi是优化目标对参数u的梯度，而h是优化目标对参数u的海森矩阵。对模型剪枝的过程是希望找到一个参数集合，使得删除掉这个参数集合之后损失函数E的增加最小，由于上面的式子需要求解损失函数的海森矩阵H，这是一个维度为参数量平方的矩阵，几乎无法进行求解，为此需要对问题进行简化，这建立在几个基本假设的前提上：

经过简化后只剩下了第二项，只需要计算H矩阵的对角项。它可以基于优化目标对连接权重的导数进行计算，复杂度就与梯度计算相同了，如下：

计算完之后就可以得到连接对优化目标改变的贡献，这就是它的重要性，因此可以进行剪枝，整个流程如下：

相对于连接权重剪枝，粗粒度剪枝其实更加有用，它可以得到不需要专门的算法支持的精简小模型。对滤波器进行剪枝和对特征通道进行剪枝最终的结果是相同的，篇幅有限我们这里仅介绍特征通道的剪枝算法代表。

通道剪枝算法有三个经典思路。第一个是基于 重要性因子 ，即评估一个通道的有效性，再配合约束一些通道使得模型结构本身具有稀疏性，从而基于此进行剪枝。第二个是利用 重建误差 来指导剪枝，间接衡量一个通道对输出的影响。第三个是基于 优化目标的变化 来衡量通道的敏感性。下面我们重点介绍前两种。

Network Trimming通过激活的稀疏性来判断一个通道的重要性，认为拥有更高稀疏性的通道更应该被去除。它使用batch normalization中的缩放因子γ来对不重要的通道进行裁剪，如下图：

具体实现起来，就是在目标方程中增加一个关于γ的正则项，从而约束某些通道的重要性。

类似的框架还有

与基于权重幅度的方法来进行连接剪枝一样，基于重要性因子的方法主观性太强，而另一种思路就是基于输出重建误差的通道剪枝算法，它们根据输入特征图的各个通道对输出特征图的贡献大小来完成剪枝过程，可以直接反映剪枝前后特征的损失情况。

如上图，基于重建误差的剪枝算法，就是在剪掉当前层B的若干通道后，重建其输出特征图C使得损失信息最小。假如我们要将B的通道从c剪枝到c'，要求解的就是下面的问题，第一项是重建误差，第二项是正则项。

第一步：选择候选的裁剪通道。

我们可以对输入特征图按照卷积核的感受野进行多次随机采样，获得输入矩阵X，权重矩阵W，输出Y。然后将W用训练好的模型初始化，逐渐增大正则因子，每一次改变都进行若干次迭代，直到beta稳定，这是一个经典的LASSO回归问题求解。

第二步：固定beta求解W，完成最小化重建误差，需要更新使得下式最小。

这类方法采用训练的方式，结合各种regularizer来让网络的权重变得稀疏，于是可以将接近于0的值剪掉。Learning Structured Sparsity in Deep Neural Networks 用group Lasso进行结构化稀疏，包括filters, channels, filter shapes, depth。Data-Driven Sparse Structure Selection for Deep Neural Networks(ECCV2018)通过引入可学习的mask，用APG算法来稀疏mask达到结构化剪枝。A Systematic DNN Weight Pruning Framework using Alternating Direction Method of Multipliers(ECCV2018) 的思想类似，用约束优化中的经典算法ADMM来求解。由于每个通道的输出都会经过BN，可以巧妙地直接稀疏BN的scaling factor，比如 Learning Efficient Convolutional Networks through Network Slimming(ICCV2017) 采用L1 regularizer，Rethinking the Smaller-Norm-Less-Informative Assumption in Channel Pruning of Convolution Layers(ICLR2018) 则采用ISTA来进行稀疏。MorphNet: Fast & Simple Resource-Constrained Structure Learning of Deep Networks(CVPR2018) 也是直接利用L1 regularizer，但是结合了MobileNet中的width-multiplier，加上了shink-expand操作，能够更好的满足资源限制。

通常来说，模型在剪枝完后进行推理时不会发生变化，即对于所有的输入图片来说都是一样的计算量，但是有的样本简单，有的样本复杂，以前我们给大家介绍过动态推理框架，它们可以对不同的输入样本图配置不同的计算量，剪枝框架也可以采用这样的思路，以Runtime Neural Pruning [12]为代表。

有采用各种剪枝方法的就有和这些剪枝方法对着干的。Recovering from Random Pruning: On the Plasticity of Deep Convolutional Neural Networks 就表明了度量标准都没啥用，随机赛高。Rethinking the Value of Network Pruning(ICLR2019) 则表示剪枝策略实际上是为了获得网络结构，挑战了传统的 train-prune-finetune的剪枝流程。Pruning from Scratch 则直接用Network Slimming的方法对训练过程中的剪枝结构进行了一波分析，发现直接采用random初始化的网络权重能够获得更丰富的剪枝结构。

剪枝中我们通常遵循一些基本策略：比如在提取低级特征的参数较少的第一层中剪掉更少的参数，对冗余性更高的FC层剪掉更多的参数。然而，由于深度神经网络中的层不是孤立的，这些基于规则的剪枝策略并不是最优的，也不能从一个模型迁移到另一个模型，因此AutoML方法的应用也是非常自然的，AutoML for Model Compression(AMC)是其中的代表

从AMC: AutoML for Model Compression and Acceleration on Mobile Devices[ECCV2018]开始将强化学习引入剪枝，剪枝的研究开始套上各种Auto的帽子，玩法更是层出不穷。AutoSlim: Towards One-Shot Architecture Search for Channel Numbers先训练出一个slimmable model（类似NAS中的SuperNet Once for All: Train One Network and Specialize it for Efficient Deployment），继而通过贪心的方式逐步对网络进行裁剪。

Network Pruning via Transformable Architecture Search(NIPS2019) 则把NAS可导的一套迁移过来做剪枝。Approximated Oracle Filter Pruning for Destructive CNN Width Optimization(ICML2019)平行操作网络的所有层，用二分搜索的方式确定每层的剪枝数。Fine-Grained Neural Architecture Search 把NAS的粒度降到了通道，包含了空的操作即剪枝。还有各种拿进化来做的也就不提了。
此外，还有基于信息瓶颈的方法Compressing Neural Networks using the Variational Information Bottleneck(ICML2018)，聚类的方法Centripetal SGD for Pruning Very Deep Convolutional Networks with Complicated Structure(CPVR2019)，等等等等等......

一脉梳理下来感觉做纯的剪枝感觉很难了，对比人工设计的结构和准则，NAS出来的模型可以又小巧精度又高，剪枝也逐渐受其影响快、准、狠地寻找结构。这些效果好的结构和权重背后到底还藏着些什么

常见论文
https://www.cnblogs.com/wujianming-110117/p/12702802.html
https://zhuanlan.hu.com/p/157562088
https://zhuanlan.hu.com/p/48269250
https://zhuanlan.hu.com/p/330575000

④ 决策树剪枝(Decision Tree Pruning)

决策树的剪枝是将生成的树进行简化，以避免过拟合。

在决策树完美分割学习样例之前，停止决策树的生长。这种提早停止树生长的方法，称为预剪枝方法。
在构造决策树的同时进行剪枝。所有决策树的构建方法，都是在无法进一步降低熵的情况下才会停止创建分支的过程，为了避免过拟合，可以设定一个阈值，熵减小的数量小于这个阈值，即使还可以继续降低熵，也停止继续创建分支。
预剪枝可能会过早停止，降低决策树的准确度。

(1) 作为叶结点或作为根结点需要含的最少样本个数
(2) 决策树的层数
(3) 结点的经验熵小于某个阈值才停止

后剪枝是在决策树生长完成之后，对树进行剪枝，得到简化版的决策树。后剪枝是目前最普遍的做法。
后剪枝的剪枝过程是删除一些子树，然后用其叶子节点代替，这个叶子节点所标识的类别通过大多数原则(majority class criterion)确定。所谓大多数原则，是指剪枝过程中, 将一些子树删除而用叶节点代替,这个叶节点所标识的类别用这棵子树中大多数训练样本所属的类别来标识,所标识的类称为majority class。

对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，然后比较这替换前后两棵决策树在测试数据集中的表现，如果替换后的决策树在测试数据集中的错误比较少(小于等于），那么该子树就可以被替换成叶子节点。该算法以自底向上(bottom-up)的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

CCP 方法主要包含两个步骤:
(1)从原始决策树 T0 开始生成一个子树序列 T0 , T 1 , … , Tn .其中 ,T0为原始的整个决策树，Ti +1从 Ti 产生 , Tn 为根节点 。
在步骤 1 中 ,生成子树序列{T0 , T1 , …, Tn}的基本思想是从 T 0 开始, 裁剪 Ti 中关于训练数据集误差增加最小的分枝来得到 Ti+1 .
(2)从第 1 步产生的子树序列中 ,根据树的真实误差估计选择最佳决策树 。如何从第 1 步产生的子树序列 T0 , T1 , T2 , …中选择出 1 棵最佳决策树是 CCP 方法第 2 步的关键 .通常采用的方法有两种, 一种是 K折交叉验证(K-fold cross-validation),另一种是基于独立剪枝数据集 .

PEP 方法是 Quinlan（决策树发明者）为了克服 REP 方法需要独立剪枝数据集的缺点而提出的 ,它不需要分离的剪枝数据集 .为了提高对未来事例的预测可靠性 , PEP 方法对误差估计增加了连续性校正(continuitycorrection).
该方法是唯一一个自顶向下(Top-down)的剪枝算法。

⑤ 用python实现红酒数据集的ID3,C4.5和CART算法

ID3算法介绍
ID3算法全称为迭代二叉树3代算法（Iterative Dichotomiser 3）
该算法要先进行特征选择，再生成决策树，其中特征选择是基于“信息增益”最大的原则进行的。
但由于决策树完全基于训练集生成的，有可能对训练集过于“依赖”，即产生过拟合现象。因此在生成决策树后，需要对决策树进行剪枝。剪枝有两种形式，分别为前剪枝（Pre-Pruning）和后剪枝（Post-Pruning），一般采用后剪枝。
信息熵、条件熵和信息增益
信息熵：来自于香农定理，表示信息集合所含信息的平均不确定性。信息熵越大，表示不确定性越大，所含的信息量也就越大。
设x 1 , x 2 , x 3 , . . . x n {x_1, x_2, x_3, ...x_n}x
1

,x
2

,x
3

,...x
n

为信息集合X的n个取值，则x i x_ix
i

的概率：
P ( X = i ) = p i , i = 1 , 2 , 3 , . . . , n P(X=i) = p_i, i=1,2,3,...,n
P(X=i)=p
i

,i=1,2,3,...,n

信息集合X的信息熵为：
H ( X ) = − ∑ i = 1 n p i log ⁡ p i H(X) =- \sum_{i=1}^{n}{p_i}\log{p_i}
H(X)=−
i=1
∑
n

p
i

logp
i

条件熵：指已知某个随机变量的情况下，信息集合的信息熵。
设信息集合X中有y 1 , y 2 , y 3 , . . . y m {y_1, y_2, y_3, ...y_m}y
1

,y
2

,y
3

,...y
m

组成的随机变量集合Y，则随机变量（X，Y）的联合概率分布为
P ( x = i , y = j ) = p i j P(x=i,y=j) = p_{ij}
P(x=i,y=j)=p
ij

条件熵：
H ( X ∣ Y ) = ∑ j = 1 m p ( y j ) H ( X ∣ y j ) H(X|Y) = \sum_{j=1}^m{p(y_j)H(X|y_j)}
H(X∣Y)=
j=1
∑
m

p(y
j

)H(X∣y
j

)
由
H ( X ∣ y j ) = − ∑ j = 1 m p ( y j ) ∑ i = 1 n p ( x i ∣ y j ) log ⁡ p ( x i ∣ y j ) H(X|y_j) = - \sum_{j=1}^m{p(y_j)}\sum_{i=1}^n{p(x_i|y_j)}\log{p(x_i|y_j)}
H(X∣y
j

)=−
j=1
∑
m

p(y
j

)
i=1
∑
n

p(x
i

∣y
j

)logp(x
i

∣y
j

)
和贝叶斯公式：
p ( x i y j ) = p ( x i ∣ y j ) p ( y j ) p(x_iy_j) = p(x_i|y_j)p(y_j)
p(x
i

y
j

)=p(x
i

∣y
j

)p(y
j

)
可以化简条件熵的计算公式为:
H ( X ∣ Y ) = ∑ j = 1 m ∑ i = 1 n p ( x i , y j ) log ⁡ p ( x i ) p ( x i , y j ) H(X|Y) = \sum_{j=1}^m \sum_{i=1}^n{p(x_i, y_j)\log\frac{p(x_i)}{p(x_i, y_j)}}
H(X∣Y)=
j=1
∑
m

i=1
∑
n

p(x
i

,y
j

)log
p(x
i

,y
j

)
p(x
i

)

信息增益：信息熵-条件熵，用于衡量在知道已知随机变量后，信息不确定性减小越大。
d ( X , Y ) = H ( X ) − H ( X ∣ Y ) d(X,Y) = H(X) - H(X|Y)
d(X,Y)=H(X)−H(X∣Y)

python代码实现
import numpy as np
import math

def calShannonEnt(dataSet):
""" 计算信息熵 """
labelCountDict = {}
for d in dataSet:
label = d[-1]
if label not in labelCountDict.keys():
labelCountDict[label] = 1
else:
labelCountDict[label] += 1
entropy = 0.0
for l, c in labelCountDict.items():
p = 1.0 * c / len(dataSet)
entropy -= p * math.log(p, 2)
return entropy

def filterSubDataSet(dataSet, colIndex, value):
"""返回colIndex特征列label等于value，并且过滤掉改特征列的数据集"""
subDataSetList = []
for r in dataSet:
if r[colIndex] == value:
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
subDataSetList.append(newR)
return np.array(subDataSetList)

def chooseFeature(dataSet):
""" 通过计算信息增益选择最合适的特征"""
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)
bestInfoGain = 0.0
bestFeatureIndex = -1
for i in range(featureNum):
uniqueValues = np.unique(dataSet[:, i])
condition_entropy = 0.0

for v in uniqueValues: #计算条件熵
subDataSet = filterSubDataSet(dataSet, i, v)
p = 1.0 * len(subDataSet) / len(dataSet)
condition_entropy += p * calShannonEnt(subDataSet)
infoGain = entropy - condition_entropy #计算信息增益

if infoGain >= bestInfoGain: #选择最大信息增益
bestInfoGain = infoGain
bestFeatureIndex = i
return bestFeatureIndex

def creatDecisionTree(dataSet, featNames):
""" 通过训练集生成决策树 """
featureName = featNames[:] # 拷贝featNames，此处不能直接用赋值操作，否则新变量会指向旧变量的地址
classList = list(dataSet[:, -1])
if len(set(classList)) == 1: # 只有一个类别
return classList[0]
if dataSet.shape[1] == 1: #当所有特征属性都利用完仍然无法判断样本属于哪一类，此时归为该数据集中数量最多的那一类
return max(set(classList), key=classList.count)

bestFeatureIndex = chooseFeature(dataSet) #选择特征
bestFeatureName = featNames[bestFeatureIndex]
del featureName[bestFeatureIndex] #移除已选特征列
decisionTree = {bestFeatureName: {}}

featureValueUnique = sorted(set(dataSet[:, bestFeatureIndex])) #已选特征列所包含的类别， 通过递归生成决策树
for v in featureValueUnique:
FeatureName = featureName[:]
subDataSet = filterSubDataSet(dataSet, bestFeatureIndex, v)
decisionTree[bestFeatureName][v] = creatDecisionTree(subDataSet, FeatureName)
return decisionTree

def classify(decisionTree, featnames, featList):
""" 使用训练所得的决策树进行分类 """
classLabel = None
root = decisionTree.keys()[0]
firstGenDict = decisionTree[root]
featIndex = featnames.index(root)
for k in firstGenDict.keys():
if featList[featIndex] == k:
if isinstance(firstGenDict[k], dict): #若子节点仍是树，则递归查找
classLabel = classify(firstGenDict[k], featnames, featList)
else:
classLabel = firstGenDict[k]
return classLabel
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
下面用鸢尾花数据集对该算法进行测试。由于ID3算法只能用于标称型数据，因此用在对连续型的数值数据上时，还需要对数据进行离散化，离散化的方法稍后说明，此处为了简化，先使用每一种特征所有连续性数值的中值作为分界点，小于中值的标记为1，大于中值的标记为0。训练1000次，统计准确率均值。

from sklearn import datasets
from sklearn.model_selection import train_test_split

iris = datasets.load_iris()
data = np.c_[iris.data, iris.target]

scoreL = []
for i in range(1000): #对该过程进行10000次
trainData, testData = train_test_split(data) #区分测试集和训练集

featNames = iris.feature_names[:]
for i in range(trainData.shape[1] - 1): #对训练集每个特征，以中值为分界点进行离散化
splitPoint = np.mean(trainData[:, i])
featNames[i] = featNames[i]+'<='+'{:.3f}'.format(splitPoint)
trainData[:, i] = [1 if x <= splitPoint else 0 for x in trainData[:, i]]
testData[:, i] = [1 if x <= splitPoint else 0 for x in testData[:, i]]

decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))
print 'score: ', np.mean(scoreL)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
输出结果为：score: 0.7335，即准确率有73%。每次训练和预测的准确率分布如下：

数据离散化
然而，在上例中对特征值离散化的划分点实际上过于“野蛮”，此处介绍一种通过信息增益最大的标准来对数据进行离散化。原理很简单，当信息增益最大时，说明用该点划分能最大程度降低数据集的不确定性。
具体步骤如下：

对每个特征所包含的数值型特征值排序
对相邻两个特征值取均值，这些均值就是待选的划分点
用每一个待选点把该特征的特征值划分成两类，小于该特征点置为1， 大于该特征点置为0，计算此时的条件熵，并计算出信息增益
选择信息使信息增益最大的划分点进行特征离散化
实现代码如下：

def filterRawData(dataSet, colIndex, value, tag):
""" 用于把每个特征的连续值按照区分点分成两类，加入tag参数，可用于标记筛选的是哪一部分数据"""
filterDataList = []
for r in dataSet:
if (tag and r[colIndex] <= value) or ((not tag) and r[colIndex] > value):
newR = r[:colIndex]
newR = np.append(newR, (r[colIndex + 1:]))
filterDataList.append(newR)
return np.array(filterDataList)

def dataDiscretization(dataSet, featName):
""" 对数据每个特征的数值型特征值进行离散化 """
featureNum = dataSet.shape[1] - 1
entropy = calShannonEnt(dataSet)

for featIndex in range(featureNum): #对于每一个特征
uniqueValues = sorted(np.unique(dataSet[:, featIndex]))
meanPoint = []

for i in range(len(uniqueValues) - 1): # 求出相邻两个值的平均值
meanPoint.append(float(uniqueValues[i+1] + uniqueValues[i]) / 2.0)
bestInfoGain = 0.0
bestMeanPoint = -1
for mp in meanPoint: #对于每个划分点
subEntropy = 0.0 #计算该划分点的信息熵
for tag in range(2): #分别划分为两类
subDataSet = filterRawData(dataSet, featIndex, mp, tag)
p = 1.0 * len(subDataSet) / len(dataSet)
subEntropy += p * calShannonEnt(subDataSet)

## 计算信息增益
infoGain = entropy - subEntropy
## 选择最大信息增益
if infoGain >= bestInfoGain:
bestInfoGain = infoGain
bestMeanPoint = mp
featName[featIndex] = featName[featIndex] + "<=" + "{:.3f}".format(bestMeanPoint)
dataSet[:, featIndex] = [1 if x <= bestMeanPoint else 0 for x in dataSet[:, featIndex]]
return dataSet, featName
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
重新对数据进行离散化，并重复该步骤1000次，同时用sklearn中的DecisionTreeClassifier对相同数据进行分类，分别统计平均准确率。运行代码如下:

from sklearn.tree import DecisionTreeClassifier
import matplotlib.pyplot as plt
scoreL = []
scoreL_sk = []
for i in range(1000): #对该过程进行1000次
featNames = iris.feature_names[:]
trainData, testData = train_test_split(data) #区分测试集和训练集
trainData_tmp = .(trainData)
testData_tmp = .(testData)
discritizationData, discritizationFeatName= dataDiscretization(trainData, featNames) #根据信息增益离散化
for i in range(testData.shape[1]-1): #根据测试集的区分点离散化训练集
splitPoint = float(discritizationFeatName[i].split('<=')[-1])
testData[:, i] = [1 if x<=splitPoint else 0 for x in testData[:, i]]
decisionTree = creatDecisionTree(trainData, featNames)
classifyLable = [classify(decisionTree, featNames, td) for td in testData]
scoreL.append(1.0 * sum(classifyLable == testData[:, -1]) / len(classifyLable))

clf = DecisionTreeClassifier('entropy')
clf.fit(trainData[:, :-1], trainData[:, -1])
clf.predict(testData[:, :-1])
scoreL_sk.append(clf.score(testData[:, :-1], testData[:, -1]))

print 'score: ', np.mean(scoreL)
print 'score-sk: ', np.mean(scoreL_sk)
fig = plt.figure(figsize=(10, 4))
plt.subplot(1,2,1)
pd.Series(scoreL).hist(grid=False, bins=10)
plt.subplot(1,2,2)
pd.Series(scoreL_sk).hist(grid=False, bins=10)
plt.show()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
两者准确率分别为：
score: 0.7037894736842105
score-sk: 0.7044736842105263

准确率分布如下：

两者的结果非常一样。
（但是。。为什么根据信息熵离散化得到的准确率比直接用均值离散化的准确率还要低啊？？哇的哭出声。。）

最后一次决策树图形如下：

决策树剪枝
由于决策树是完全依照训练集生成的，有可能会有过拟合现象，因此一般会对生成的决策树进行剪枝。常用的是通过决策树损失函数剪枝，决策树损失函数表示为:
C a ( T ) = ∑ t = 1 T N t H t ( T ) + α ∣ T ∣ C_a(T) = \sum_{t=1}^TN_tH_t(T) +\alpha|T|
C
a

(T)=
t=1
∑
T

N
t

H
t

(T)+α∣T∣

其中，H t ( T ) H_t(T)H
t

(T)表示叶子节点t的熵值，T表示决策树的深度。前项∑ t = 1 T N t H t ( T ) \sum_{t=1}^TN_tH_t(T)∑
t=1
T

N
t

H
t

(T)是决策树的经验损失函数当随着T的增加，该节点被不停的划分的时候，熵值可以达到最小，然而T的增加会使后项的值增大。决策树损失函数要做的就是在两者之间进行平衡，使得该值最小。
对于决策树损失函数的理解，如何理解决策树的损失函数? - 陶轻松的回答 - 知乎这个回答写得挺好，可以按照答主的思路理解一下

C4.5算法
ID3算法通过信息增益来进行特征选择会有一个比较明显的缺点：即在选择的过程中该算法会优先选择类别较多的属性（这些属性的不确定性小，条件熵小，因此信息增益会大），另外，ID3算法无法解决当每个特征属性中每个分类都只有一个样本的情况（此时每个属性的条件熵都为0）。
C4.5算法ID3算法的改进，它不是依据信息增益进行特征选择，而是依据信息增益率，它添加了特征分裂信息作为惩罚项。定义分裂信息：
S p l i t I n f o ( X , Y ) = − ∑ i n ∣ X i ∣ ∣ X ∣ log ⁡ ∣ X i ∣ ∣ X ∣ SplitInfo(X, Y) =-\sum_i^n\frac{|X_i|}{|X|}\log\frac{|X_i|}{|X|}
SplitInfo(X,Y)=−
i
∑
n

∣X∣
∣X
i

∣

log
∣X∣
∣X
i

∣

则信息增益率为：
G a i n R a t i o ( X , Y ) = d ( X , Y ) S p l i t I n f o ( X , Y ) GainRatio(X,Y)=\frac{d(X,Y)}{SplitInfo(X, Y)}
GainRatio(X,Y)=
SplitInfo(X,Y)
d(X,Y)

关于ID3和C4.5算法
在学习分类回归决策树算法时，看了不少的资料和博客。关于这两个算法，ID3算法是最早的分类算法，这个算法刚出生的时候其实带有很多缺陷：

无法处理连续性特征数据
特征选取会倾向于分类较多的特征
没有解决过拟合的问题
没有解决缺失值的问题
即该算法出生时是没有带有连续特征离散化、剪枝等步骤的。C4.5作为ID3的改进版本弥补列ID3算法不少的缺陷：

通过信息最大增益的标准离散化连续的特征数据
在选择特征是标准从“最大信息增益”改为“最大信息增益率”
通过加入正则项系数对决策树进行剪枝
对缺失值的处理体现在两个方面：特征选择和生成决策树。初始条件下对每个样本的权重置为1。
特征选择：在选取最优特征时，计算出每个特征的信息增益后，需要乘以一个**“非缺失值样本权重占总样本权重的比例”**作为系数来对比每个特征信息增益的大小
生成决策树：在生成决策树时，对于缺失的样本我们按照一定比例把它归属到每个特征值中，比例为该特征每一个特征值占非缺失数据的比重
关于C4.5和CART回归树
作为ID3的改进版本，C4.5克服了许多缺陷，但是它自身还是存在不少问题：

C4.5的熵运算中涉及了对数运算，在数据量大的时候效率非常低。
C4.5的剪枝过于简单
C4.5只能用于分类运算不能用于回归
当特征有多个特征值是C4.5生成多叉树会使树的深度加深
————————————————
版权声明：本文为CSDN博主“Sarah Huang”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44794704/article/details/89406612

⑥ 关于剪枝的资料

1、果树修剪有冬剪和夏剪两种。2、修剪主要是剪除徒长枝、下垂枝、背上枝、过密枝、病虫枝和弱小枝，修剪可以控制结果量，使果树结果质量得到提高。3、修剪是为果树整形，梨树为三主枝疏散分层形，桃为三主枝开心形，石榴为自然圆头形。4、夏季修剪在6月至8月，只要你觉得密，可以从分枝处剪掉一部分小枝，能透光就形，但别把结果枝剪了，否则就吃不到果子了。5、冬季修剪以短剪为主，就是把枝条从顶部剪去一部分，3分之1 或2分之1 ，目的是促进果树生长，减少结果，也可以剪去部分结果枝，因为果树的结果有一个因果关系，结多了果子就小了。
果树春季复剪，是对冬剪的补充和完善，一般在果树萌芽后能清楚地辨认出花芽时进行，最好在花蕾膨大前完成。果树春季复剪要先剪成年树、弱树或开花早的品种，后剪幼龄树、旺树和开花晚的品种。另外果树春季复剪要因品种、树龄和树势等具体情况而定。其次要在修剪口涂愈伤防腐膜防止水分蒸发和营养消耗。
对于盛果期的大树，要选留饱满和叶片多的花芽，去掉瘦弱和叶片少的花芽。按生长枝和结果枝为3:1的比例，使其负载更趋合理。对于花量多的大树，要适当疏除弱枝和弱芽，多留壮枝和壮芽，更新衰老和过密的枝条。对花芽少的幼龄树，要多留花芽，疏除过密的营养枝；冬剪要配合清园，除将病弱枝带出园外集中烧毁以外还要进行全园普喷护树将军消毒杀菌保护树体安全越冬。

⑦ 模型压缩：剪枝算法

过参数化主要是指在训练阶段，在数学上需要进行大量的微分求解，去捕抓数据中的微小变化信息，一旦完成迭代式的训练之后，网络模型推理的时候就不需要这么多参数。而剪枝算法正是基于过参数化的理论基础而提出的。

剪枝算法核心思想就是减少网络模型中参数量和计算量，同时尽量保证模型的性能不受影响。

那在AI框架中，实际上剪枝主要作用在右下角的端侧模型推理应用场景中，为的就是让端侧模型更小，无论是平板、手机、手表、耳机等小型IOT设备都可以轻松使用AI模型。而实际在训练过程更多体现在剪枝算法和框架提供的剪枝API上面。

实际上大部分刚接触剪枝算法的时候，都会从从宏观层面去划分剪枝技术，主要是分为Drop Out和Drop Connect两种经典的剪枝算法，如下图所示。

1）Drop Out：随机的将一些神经元的输出置零，称之为神经元剪枝。

2）Drop Connect：随机将部分神经元间的连接Connect置零，使得权重连接矩阵变得稀疏。

下面会把剪枝的更多种方式呈现出来，可能会稍微复杂哈。从剪枝的粒度来划分，可以分为结构化剪枝和非结构化剪枝，2个剪枝结构方法。下面来看看具体的剪枝方法有4种：

细粒度剪枝、向量剪枝、核剪枝在参数量与模型性能之间取得了一定的平衡，但是网络模型单层的神经元之间的组合结构发生了变化，需要专门的算法或者硬件结构来支持稀疏的运算，这种叫做 结构化剪枝（Unstructured Pruning） 。

其中，非结构化剪枝能够实现更高的压缩率，同时保持较高的模型性能，然而会带来网络模型稀疏化，其稀疏结构对于硬件加速计算并不友好，除非底层硬件和计算加速库对稀疏计算有比较好的支持，否则剪枝后很难获得实质的性能提升。

滤波器剪枝（Filter-level）主要改变网络中的滤波器组和特征通道数目，所获得的模型不需要专门的算法和硬件就能够运行，被称为 结构化剪枝（Structured Pruning） 。结构化剪枝又可进一步细分：可以是channel-wise，也可以是filter-wise，还可以是在shape-wise。

结构化剪枝与非结构化剪枝恰恰相反，可以方便改变网络模型的结构特征，从而达到压缩模型的效果，例如知识蒸馏中的student网络模型、NAS搜索或者如VGG19和VGG16这种裁剪模型，也可以看做变相的结构化剪枝行为。

虽然剪枝算法的分类看上去很多，但是核心思想还是对神经网络模型进行剪枝，目前剪枝算法的总体流程大同小异，可以归结为三种：标准剪枝、基于子模型采样的剪枝、以及基于搜索的剪枝，如下图所示。

标准剪枝是目前最流行的剪枝流程，在Tensorflow、Pytroch都有标准的接口。主要包含三个部分：训练、剪枝、以及微调。

1） 训练 ：首先是对网络模型进行训练。在剪枝流程中，训练部分主要指预训练，训练的目的是为剪枝算法获得在特定基础SOTA任务上训练好的原始模型。

3） 微调 ：微调是恢复被剪枝操作影响的模型表达能力的必要步骤。结构化模型剪枝会对原始模型结构进行调整，因此剪枝后的模型参数虽然保留了原始的模型参数，但是由于模型结构的改变，剪枝后模型的表达能力会受到一定程度的影响。实现上，微调网络模型，参数在计算的时候先乘以该Mask，Mask为1的参数值将继续训练通过BP调整梯度，而Mask为0的部分因为输出始终为0则不对后续部分产生影响。

4） 再剪枝 ：再剪枝过程将微调之后的网络模型再送到剪枝模块中，再次进行模型结构评估和执行剪枝算法。目的是使得每次剪枝都在性能更优的模型上面进行，不断迭代式地进行优化剪枝模型，直到模型能够满足剪枝目标需求。

最后输出模型参数储存的时候，因为有大量的稀疏，所以可以重新定义储存的数据结构， 仅储存非零值以及其矩阵位置。重新读取模型参数的时候，就可以还原矩阵。

除标准剪枝之外，基于子模型采样的剪枝《EagleEye: Fast sub-net evaluation for efficient neural network pruning》最近也表现出比较好的剪枝效果。得到训练好的模型之后，进行子模型采样过程。一次子模型采样过程为：

1）对训练好的原模型中可修剪的网络结构，按照剪枝目标进行采样，采样过程可以是随机的，也可以按照网络结构的重要性或者通过KL散度计算进行概率采样。

2）对采样后的网络结构进行剪枝，得到采样子模型。子模型采样过程通常进行 次，得到 个子模型（ ≥1）, 之后对每一个子模型进行性能评估。子模型评估结束之后，选取最优的子模型进行微调以得倒最后的剪枝模型。

基于搜索的剪枝主要依靠强化学习等一系列无监督学习或者半监督学习算法，也可以是神经网络结构搜索相关理论。

给定剪枝目标之后，基于搜索的剪枝在网络结构中搜索较优的子结构，这个搜索过程往往伴随着网络参数的学习过程，因此一些基于搜索的剪枝算法在剪枝结束后不需要再进行微调。

这几年神经网络剪枝pruning作为模型压缩技术的四小龙之一，正在受到越来越多的关注。当然，各种更好的pruning参数选取方法一定还会层出不穷。另外，从趋势来看，以下几个方向值得关注：

打破固定假设 ：挑战已有的固有的假设，例如ICLR2019会议的best paper彩票假说《The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks 》的出现。还有一开始提到的对于over-parameterization，与重用已有参数是否有有益的反思非常有意思。这样的工作会给剪枝算法非常大的启发，从而根本改变解决问题的思路。

自动化剪枝 ：随着AutoML的大潮，越来越多的算法开始走向自动化。模型压缩能拉下吗？当然不能。经过前面的介绍我们知道，像ADC，RNP，N2N Learning这些工作都是试图将剪枝中部分工作自动化。如量化中的《HAQ: Hardware-Aware Automated Quantization》考虑网络中不同层信息的冗余程度不一样，所以自动化使用混合量化比特进行压缩。

与NAS融合 ：如前面模型剪枝流程中提到，剪枝算法与神经网络搜索NAS的界限已经模糊了。NAS有针对结构化剪枝进行搜索方法，如One-Shot Architecture Search是先有一个大网络，然后做减法。NAS与模型压缩两个一开始看似关系不是那么大的分支，在近几年的发展过程中因为下游任务和部署场景的需求，最后似乎会走到一块去。这两个分支今天有了更多的交集，也必将擦出更多的火花。

与GAN融合 ：这几年机器学习最火热的分支之一GAN，正在不断渗透到已有领域，在pruning中也开始有它的身影。如2019年《Towards Optimal Structured CNN Pruning via Generative Adversarial Learning》让generator生成裁剪后网络，discrimintor来判别是否属于原网络还是裁剪后网络，从而进行更有效的网络结构化裁剪。

硬件稀疏性支持 ：剪枝会给神经网络模型带来稀疏性特征，参数稀疏性在计算中会有大量的索引，所以并不能加速。现在虽然有像cuSPARSE这样的计算库，但底层硬件AI芯片本身设计并不是专门为稀疏数据处理打造的。如果能将稀疏计算和处理能力做进芯片那必将极大提高计算效率。仅2021年中国就推出了10+款基于ASIC的AI加速芯片，相信针对稀疏性场景的支持在未来会有所突破。

模型压缩算法中针对已有的模型，有：张量分解，模型剪枝，模型量化。针对新构建的网络，有：知识蒸馏，紧凑网络设计等方法。

剪枝只是模型压缩方法中的一种，它与其它模型压缩方法并不冲突，因此会与量化、蒸馏、NAS、强化学习等方法慢慢融合，这些都是很值得研究的方向。另外在上面的发展来看，打破固有的假设定义，与NAS、GAN、AutoML、RL等技术进行相互的融合，可能到最后会模糊purning方式，出现新的范式或者压缩模式也是很吸引的。

⑧ 棋类游戏的算法有哪些

棋类游戏的算法有哪些

棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。下面我来给大家讲讲各类棋类游戏的算法。

除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢?

1. 博弈与博弈树

博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如“二人零和、全信息、非偶然”博弈，也就是我们常说的零和博弈(Zero-sum Game)。所谓“零和”，就是有赢必有输，不存在双赢的结果。所谓“全信息”，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的“非偶然”，是指参与博弈的双方的决策都是“理智”的行为，不存在失误和碰运气的情况。

在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动(也可能是棋子落子)的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。

假设两个棋手(可能是两个人，也可能是两台计算机)MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树(Game Tree)。

2. 极大极小值搜索算法

极大极小值(Min-Max)搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的'最大利益(令对手的最大利益最小化)的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。

3. 负极大值搜索算法

博弈树的搜索是一个递归的过程，极大极小值算法在递归搜索的过程中需要在每一步区分当前评估的是极大值节点还是极小值节点。1975年Knuth和Moore提出了一种消除MAX节点和MIN节点区别的简化的极大极小值算法，称为负极大值算法Negamax。该算法的理论基础是：

max(a,b) = -min(-a, -b)

简单地将递归函数MiniMax()返回值取负再返回，就可以将所有的MIN 节点都转化为MAX节点，对每个节点的搜索都尝试让节点值最大，这样就将每一步递归搜索过程都统一起来。

4. “α-β”剪枝算法

有很多资料将“α-β”剪枝算法称为“α-β”搜索算法，实际上，它不是一种独立的搜索算法，而是一种嫁接在极大极小值算法和负极大值算法上的一种优化算法。“α-β”剪枝算法维护了一个搜索的极大极小值窗口：[α,β]。其中α表示在搜索进行到当前状态时，博弈的MAX一方所追寻的最大值中最小的那个值(也就是MAX的最坏的情况)。在每一步的搜索中，如果MAX所获得的极大值中最小的那个值比α大，则更新α值(用这个最小值代替α)，也就是提高α这个下限。

而β表示在搜索进行到当前状态时，博弈的MIN一方的最小值中最大的那个值(也就是MIN的最坏的情况)。在每一步的搜索中，如果MIN所获得的极小值中最大的那个值比β小，则更新β值(用这个最大值代替β)，也就是降低β这个上限。当某个节点的α≥β时，说明该节点的所有子节点的评估值既不会对MAX更有利，也不会对MIN更有利，也就是对MAX和MIN的选择不会产生任何影响，因此就没有必要再搜索这个节点及其所有子节点了。

5. 估值函数

对于很多启发式搜索算法，其“智力”的高低基本上是由估值函数(评估函数)所决定，棋类游戏的博弈树搜索算法也不例外。

估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力(棋力)、双方棋子占领的空间、落子的机动性、威胁性(能吃掉对方的棋子)、形和势等。

6. 置换表与哈希函数

置换表(transposition table)也是各种启发式搜索算法中常用的辅助算法，它是一种以空间换时间的策略，使用置换表的目的就是提高搜索效率。一般情况下，置换表中的每一项代表者一个棋局中最好的落子方法，直接查找置换表获得这个落子方法能避免耗时的重复搜索，这就是使用置换表能大幅提高搜索效率的原理。

使用置换表最大的问题是置换表的组织和查找的效率。一般来说，置换表越大，查找的命中率就越高。但这个关系不是绝对的，当置换表大小达到一定规模后，不仅不会再提高命中率，反而会因为耗时的查找操作影响算法的效率。所以置换表不是越大越好，需要根据计算机的性能以及搜索的深度选择一个合适的大小。此外，为了查找操作更高效，通常都会用可直接访问的哈希表方式组织置换表，哈希函数的性能就成为影响置换表性能的重要因素。棋类游戏普遍采用Zobrist哈希算法。