VRF 这个东东，在不少区块链项目中都会听到，比较火的 Algorand 和 Dfinity 的共识机制都用到了它。它的全称叫 Verifiable Random Function（随机可验证函数），那它跟一般的随机函数有什么不同？有什么用，为什么区块链需要用到 VRF？这次被我骚扰的是资深全栈工程师黄祺，他曾在 BFTF 区块链知享会中介绍区块链中 VRF 的应用。
 
在区块链中，大部分的共识算法，无论是 POW、POS，或是由他们衍生出来的 DPOS，都需要选出一堆或者一个节点来参与共识或者打包区块，这个过程虽然会有持币情况、设备配置、信誉等各种因素影响，但必须是随机的、无法被预测的。这时候就可能会用到随机算法。
 
在 BFTF 的分享沙龙上，黄祺解释，可验证随机函数可以看作是一个随机预言机（Random Oracle，RO），就是可以通过任意的一个输入，获得一个随机数输出。可验证随机函数比随机预言机多了一个非交互的零知识证明，可以用来该随机数输出的正确性，表明这个随机数的确是某个人生成的。
 
先说 RO，有两个特征：
 
 1、对于不同的 Input，Output 的值是随机的，并且均匀分布在值域范围内。
 
 2、对于相同的 Input，它得到的 Output 一定是相同的。
 
举例说明一下，假设某公链网络用普通的 RO 选节点，有可能是这样的情况：假设全网有 100 个节点，我想生成下一轮一个节点谁打包，我以某一轮的轮次作为输入，然后随机输出的值必须要是在 1-100 之间的自然数（因为网络中只有 100 个节点）。这就每一轮都选出了一个打包节点的人。
 
这里的问题是，由于输入对应的输出肯定是相同的，而输入是公开的，就使得每一轮的抽签结果变得可以被预知，攻击者可以尝试控制这个过程或者攻击特定的节点。可是如果输入不公开的话，我们要怎么保证这个输入结果没有问题呢？VRF 就用到了零知识证明，让结果“可验证”。
 
VRF 的方式是，让各个节点自己抽签，如果抽中了之后，大家可以很容易地验证这个结果确实是你生成的。具体过程有可能是这样的：假设现在是 round 10（第 10 轮），节点们可能会轮流抽签，以节点自己的私钥 + 一个全网都知道的随机数（比如是这轮的轮次 10）作为输入，生成了一个随机数（0-100）；设置一个条件：100 个节点轮流抽签，谁先抽出来的随机数大于 10，就是这一轮的打包者。假设 5 号节点抽到了 11，可是只有 5 号知道其他人不知道，因此他在广播这个随机的同时还需要广播一个零知识证明。通过零知识证明，全网只需要通过 5 号的公钥就可以验证，接受 5 号为这轮打包者。
 
So，普通 RO 在私钥 + 零知识证明的作用下，抽签过程就可以在本地进行、不公开私钥同时又可以全网验证。
 
黄祺总结，可验证随机函数一共包含四个函数：1、生成密钥，生成一个公钥私钥对；2、生成随机数输出；3、计算零知识证明；4、验证随机数输出。
 
看完上面的之后，我们大概可以明白，VRF 的目的就是要生成一个真正随机而且无法被预测的值。在区块链选出块节点的过程中，为了保证安全，随机是一个基本要求。不过，区块链选节点不单纯是随机就 OK 的，还要考虑到攻击成本等，所以共识机制往往加入算力和持币权益等影响因素，以增加攻击者的攻击成本。如果单纯使用随机算法，就很容易受到女巫攻击，攻击者可以廉价找大量的傀儡机（肉鸡）来增加自己抽中的概率。
 
这么一想，你会很容易明白为什么有那么多新型的共识算法都用到了 VRF，其实它们想达到的目的跟 POW 的答题过程有点像，都是为了找到随机而又安全地抽取出块节点。POW 被诟病的问题是功耗大和性能低，但是安全边界明显，而且比特币运行已久都没有大问题。POS 共识算法本身不需要大量算力，VRF 可又以在本地抽签，所以 POS 共识算法用 VRF 的好处是功耗比较低，而且最新的算法，验证零知识证明的速度已经非常快。有不少知名的公链项目都用到了 VRF，包括本体、Cardano （共识算法为 Ouroboros，已经迭代了 uroboros、Praos 和 Genesis 三个版本）、Dfinity 和 Algorand。
 
不同的项目用到 VRF 的不同点主要在于是怎么产生一开始的输入，以及输出要怎么用。以下是 VRF 在一些项目中的作用： 
 
 
根据本体官网，VBFT 的每轮共识中：
 
 
根据 VRF 从共识网络中选择备选提案节点，各个备选节点将独立提出备选区块；
 
 
根据 VRF 从共识网络中选择多个验证节点，每个验证节点将从网络中收集备选的区块，进行验证，然后对最高优先级的备选区块进行投票；
 
 
根据 VRF 从共识网络中选择多个确认节点，对上述验证节点的投票结果进行统计验证，并确定出最终的共识结果。
 
 
所有节点都将接收确认节点的共识结果，并在一轮共识确认后开启新的共识。
 
根据上交所技术公司的朱立解释，Algorand 和 Dfinity 的共识算法中用 VRF 的套路大概是这样的：输入值由前一个随机数（最初的随机数却是协议给定的）和某种代表高度、轮次的变量进行组合，然后用私钥对之进行签名（或者是先签名再组合），最后哈希一下得出最新的随机数。他认为：
 
 
 
“这样产生的随机数旁人很容易验证其合乎算法，"V" 就这样得到了；而哈希返回值又是随机分布的，“R” 也因此得到保证。在此过程中，为降低操纵结果的可能性，有两个注意事项：A) 签名算法应当具有唯一性，也就是用同一把私钥对同样的信息进行签名，只有一个合法签名可以通过验证——普通的非对称加解密算法一般不具备这个属性，如 SM2。如果用的签名算法没有这种 uniqueness 属性，那在生成新随机数的时候就存在通过反复多次尝试签名以挑出最有利者的余地，会降低安全性。B) 避免在生成新随机数时将当前块的数据作为随机性来源之一，比如引用本块交易列表的 merkle root 值等等，因为这样做会给出块人尝试变更打包交易顺序、尝试打包不同交易以产生最有利的新随机数的余地。在设计和检视新的共识算法时，以上两个注意事项是要特别留意的。
 
 
VRF 的返回结果可以用来公开完成节点或节点群体的选择，也可以私密地完成选择。以 Dfinity 为例，它是利用 mod 操作来唯一、公开地确定一个 Group。Algorand、Ouroboros Praos 是私密选择的范例，大致套路是对 VRF 的最新返回值，配上轮次等变量后用私钥进行签名并哈希，如果哈希值小于某个阈值，节点就可以私密地知道自己被选中。这种方法很可能在网络节点数较多时的表现会更稳定，否则幸运儿个数上下波动会较大，进而影响协议表现，包括空块和分叉。”
 
 
根据 CSDN 博主 Omni-Space 解释，Cardano 的共识机制运作如下：
 
 
 
“首先是一些术语及作用的解释：
 
 
 
在 Cardano 的运行中，时间被分为 slot。
 
 
每个 slot 只能产生一个块，若这个块有问题，或者应该产出这个块的“矿工”(也就是 stakeholder 的候选人)不在线，或者产出的块没有广播给大多数人，那么这个 slot 是当作废弃的，也就是会跳过这个 slot 的块。
 
 
图片来自黄祺《区块链中 VRF 的应用及原理解析》
 
 
多个 slot 为一个 epoch，权益的计算是以每个 epoch 开始前的历史来计算，也就是说在这个 epoch 中所产生的权益变化不影响当前的这个 epoch 中的 slot 的出块者的选择和其他和历史相关的东西。当前 epoch 中所产生的这些历史只能在以后的 epoch 中生效。
 
 
每个 epoch 的开头有个 genesis block(注意是每一个 epoch，不是整个链)，这个 genesis block 不会上链 (整个链初始的那个 genesis 会，当然这一点可以根据实现自己决定)，而是当前这个节点(矿工) 自己在内存中生成，这个 genesis block 会记录好当前这个 epoch 中的可能参与出块的 stakeholder 的候选人，及一个随机种子ρ。
 
 
stakeholder 是权益持有者，也就是潜在矿工，在 Cardano 的实现中权益 stake 并不是直接指代有多少 Ada，而是和有多少 Ada 相关联(更详细的我不是很清楚)，同时要成为一个 stakeholder 需要有 2% 的 Ada 才行。当然论文中不关注这些，直接定义了 stakeholder。而 stakeholder 并不一定要参与出块，只有记录在每个 epoch 的 genesis block 中的 stakeholder 才能参与当前 epoch 中 slot 的出块，所以记录在每个 epoch 中的 genesis block 中的 stakeholder 叫做 “stakeholder 候选人”
 
 
由这些 epoch 衔接而成的链就是由 Ouroboros 共识产生的链，这个链的基本属性和 Bitcoin 相同(如每个块包含上一个块的 hash 等等)。
 
 
Slot Leader Selection 是指根据权益占比选择按概率选择出当前 slot 的出块者。指代的是在当前的 epoch 中，按 genesis block 中记录的 stakeholder 候选人的权益分别占用的比例为这个 epoch 中的每一个 slot 选择出块者的概率(注意这个概率是独立事件，也就是有可能在同一个 epoch 中重复选出相同的人)。在论文中用函数
 
 
 
 
 
来表示按照权益占比为概率从stakeholder候选人选出该slot的出块者U。注意在论文中只是定义了这个函数具有这样的作用，在Cardano中使用了 “follow-the-satoshi(fts)” 算法(fts具有论文中定义的这个函数的性质)来选出这个slot leader也就是出块者。
 
 
secure multiparty computation (MPC) MPC协议，参与者使用一种能达成MPC的密码学协议来参与生成下一轮epoch的随机种子ρ，这个MPC协议必须是保证guarantee output delivery(G.O.D，下文会解释)。这个随机种子ρ是用于Slot Leader Selection中的。
 
 
在已有这些基础术语及作用的基础上，现在来简单介绍一下的工作流程:
 
 
 
 
如图所示，执行流程如下：(注：我并不保证这个流程是完全符合Cardano源码的实现(毕竟我没看过)，但是是符合论文的描述的)：
 
 
 
从链的真正创世块开始，硬编码进入了一些公钥和这些公钥vk对应的权益s及初始的种子ρ，之后，这个epoch会采用这些基础信息继续运行。
 
 
每个节点自己独立运行代码，根据当前epoch的种子ρ，执行F(比如 follow-the-satoshi)，把genesisblock中的权益，ρ和slot的index作为输入，根据概率获得当前这个slot应该由谁出块。
 
 
若发现是自己出块，则执行打包交易等等操作，和bitcoin没有太大区别，但是除了基础工作之外，还会生成一个随机数，但是这个随机数不放到链(块)中，而是放一个承诺(后文解释)。
 
 
若不是自己出块，则等待出块者出块并广播。收到这个块的时候就进行和bitcoin类似的检查，要是长时间未收到(超出这个slot的时间)则会认为这个slot的块废弃。
 
 
在当前epoch中不断重复2的流程直到这个epoch中的所有slot结束。
 
 
在整个epoch的过程中会产出一个在这个epoch参与出块者们(slot leaders)都共同认同的随机种子ρ。
 
 
在自己的内存里记录好这个ρ及下一个epoch参与的stakeholders，开启下一个epoch周期，进入2的流程。
 
 
以上就是 Ouroboros 大致执行的流程。”
 
 
VRF在区块链领域的运用大致如上，不过在如上场景有没有更好的解决方式，或者这个技术还能用在什么场景，还是值得讨论的问题。
 
参考文章：
 
随机选择算法
 
区块链中VRF的应用及原理解析
 
对可验证随机函数VRF的简明解释
 
简评三个基于VRF的共识算法
 
可验证随机函数VRF之Algorand算法
 
图灵奖得主Sivio Micali的Algorand区块链协议简介
 
Algorand 白皮书 1607.01341 版本
 
Cardano白皮书
 
Verifiable Random Functions
 
 
 

   
 
 

rand函数常用来制作随机,比如随机大小,随机速度,随机颜色
 但随机结果的比例分布是平均的,线性的
 
 这种完美的线性的特性是cg中容易出现的,而这会让我们的作品多一些不真实感,也显得不够细腻
 仔细观察下我们周围,石块的分布通常是几块大石子,若干中石子和大量小石子,而我们用rand随机大小的结果就是若干大石子,若干中石子和若干小石子.
 为了打破这种平均,我们可以额外控制一部分比例的物体让它们的更小
 
 根据需要可以继续细化它
 
 
 需要写成单行的可以这么干
 
 
 还可以继续拓展,如果有更好的方法欢迎交流
 Hip文件:https://pan.baidu.com/s/1HnaJi1rQcFk4_g8Nc3YNfw
 

 --END--

使用遗传算法求解多峰函数的最大值，是我的一项课程作业，做完之后，顺便把文档整理出来做个记录。全部内容如下：
 
1、问题描述
 
编程实现遗传算法，并求解多峰函数的最大值。多峰函数的表达式如下所示：
 
 用MATLAB做出函数的图像如下：
 
 
2、算法描述及实现
 
2.1、遗传算法概述
 
遗传算法(GA，Genetic Algorithm)，也称为进化算法。遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作，因此不同于其他求解最优解的算法，遗传算法不存在求导和对函数连续性的限定，采用概率化的寻优方法，不需要确定的规则就能自动获取和指导优化的搜索空间，自适应地调整搜索方向。
 
以上是对遗传算法相对抽象的总结，为了更具体形象的解释遗传算法的一般原理，我们首先介绍一些生物学上的概念：
 
①种群：不同生物个体形成的群体，生物的进化以群体的形式进行，这样的一个群体称为种群；
 
②个体：组成种群的单个生物；
 
③基因：带有遗传信息的DNA片段，可以通俗的将基因理解为一段信息，这段信息决定的生物个体的性状；
 
④表现型：根据基因形成的个体的外部表现；
 
⑤适应度：生物个体对于生存环境的适应程度，越适应那么其得以存活和繁衍的概率就越大；
 
⑥遗传：通过繁殖过程，子代将从父母双方各获取一部分基因，形成新的自己的基因，这个过程中，会发生基因的复制、交叉，也会以较低的概率发生基因突变；
 
⑦自然选择：物竞天择，适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少；
 
⑧进化：种群通过代际繁衍不断适应生存环境的过程，在这个过程中，以对外界环境的适应度为评判标准，生物的性状不断得到改良。
 
了解了这些术语的含义，我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的，即生物只能改变自己去适应环境，那么在自然选择的过程中，适应度低的个体会被淘汰，适应度高的个体被保留，高适应度的父体与母体又有更高的概率繁衍出适应度高的子代，因此在一代又一代的繁衍之后，高适应度的个体在种群中所占的比例越来越大，种群就这样完成了进化。
 
现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此，遗传算法的思路是，将要解决的问题模拟成一个生物进化的过程，通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例：
 
将(x, y)这一可能的解作为一个个体；将多峰函数的函数值f(x, y)作为个体的适应度；对(x, y)进行编码作为个体的基因；以适应度为标准不断筛选生物个体；通过遗传算子（如复制、交叉、变异等）不断产生下一代。如此不断循环迭代，完成进化。最终，根据设定的迭代次数，可得到最后一代种群，该种群中的个体适应度都较高，而多峰函数的最大值就有比较大的概率存在于这一群解中，以种群中适应度最高的个体作为问题的解，则可以说该解有比较高的概率就是我们希望求得的最优解。
 
文字述说终究还是不如图表好理解，因此还是看图吧（下图将本题与自然遗传联系了起来）：
 
 通过以上描述，我们不难看出，遗传算法不能保证一定能求得最优解，而只能以一定的概率求最优解。但是使用遗传算法时，我们可以不用关心具体如何去找最优解，要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。
 
2.2、算法的流程
 
通过上文的阐述，对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤，并一一解析：
 
第一步：随机产生一个种群，作为问题的初代解（通常，初代解可能与最优解相差较大，这是可以容忍的，只要保证初代解是随机产生的，以确保个体基因的多样性即可）；
 
第二步：寻找一种合适的编码方案对种群中的个体进行编码，可以选择如浮点数编码或二进制编码等常用编码方案（需要指出的是，不同的编码方案直接影响后续遗传算子的实现细节）；
 
第三步：以多峰函数的函数值 作为个体的适应度，计算种群中每个个体的适应度（算出的适应度将为后续的个体选择提供依据）；
 
第四步：根据适应度的高低选择参与繁衍的父体与母体，选择的原则是适应度越高的个体越可能被选中（以此不断淘汰适应度低的个体）；
 
第五步：对被选出的父体与母体执行遗传操作，即复制父体与母体的基因，并采用交叉、变异等算子产生出子代（在较大程度保留优秀基因的基础上，变异增加了基因的多样性，从而提高找到最优解的概率）；
 
第六步：根据一定的准则判断是继续执行算法，还是找出所有子代中适应度最高个体作为解返回并结束程序（判断的准则可以是设定的解的阈值、指定的迭代次数等）。
 
 
2.3、算法的编码实现
 
2.3.1、编码
 
本文采用的是二进制编码方式，这种编码方式编解码过程简单易行，相应的交叉算子、变异算子等操作用位运算即可实现。当然，它也有一定的缺点，比如连续性不够强。为保证求解的精度，本文使用14个bit为 编码，使用11个bit为 编码，两者组合成25个bit的最终结果。不难算出，该方式的编码精度可达千分位。具体的编码操作可总结为，将 或 的取值区间映射到0~2n-1这一整数范围，其中n表示编码位数， 或 在其取值区间的某点，相应的映射到整数区间中的某点，改点即为 或 的基因编码。程序如下：
 
/*
    基因编码
    gene1       输入型参数，待编码的基因段1
    gene2       输入型参数，待编码的基因段2
    gene_code   输出型参数，基因编码

    返回值：当输入的基因不符合要求时返回false，否则返回true
*/
static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code)
{
    /* 判断基因是否合法 */
    if (!is_gene_legal(gene1, gene2))
        return false;

    /* 若基因合法则对其进行编码 */
    unsigned int gene1_code = (gene1 - GENE1_RANGE_LEFT) * (GENE1_CODE_MAX - 1) / (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT);
    unsigned int gene2_code = (gene2 - GENE2_RANGE_LEFT) * (GENE2_CODE_MAX - 1) / (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT);
    
    /* 组合基因片段 */
    *gene_code = (gene1_code << 11) | gene2_code;

    return true;
}
 
2.3.2、解码
 
解码是编码的逆过程，无需赘述，程序如下：
 
/*
    基因解码
    gene_code   输入型参数，基因编码
    gene1       输出型参数，解码后的基因段1
    gene2       输出型参数，解码后的基因段2

    返回值：当输入的基因编码不符合要求时返回false，否则返回true
*/
static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2)
{
    /* 判断基因编码是否合法 */
    if (!is_gene_code_legal(gene_code))
        return false;

    /* 若基因编码合法则对其进行解码 */
    unsigned int gene1_code = GET_GENE1_CODE(gene_code);
    unsigned int gene2_code = GET_GENE2_CODE(gene_code);

    *gene1 = (double)gene1_code * (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT) / (GENE1_CODE_MAX - 1) + GENE1_RANGE_LEFT;
    *gene2 = (double)gene2_code * (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT) / (GENE2_CODE_MAX - 1) + GENE2_RANGE_LEFT;

    return true;
}
 
2.3.3、计算适应度
 
适应度函数也称评价函数，通常用于区分群体中个体好坏的标准。适应度高的，也就是优秀的个体有更大的几率参与繁衍，遗传自己的基因。一般的，适应度函数根据目标函数来确定，有时候直接将目标函数值作为适应度。这里，考虑到待求解的多峰函数，尖峰分布密集而且峰的直径很窄，这不利于遗传算法的收敛，因此本文不直接将多峰函数值作为适应度，而是利用对数函数将多峰函数进行平缓，并将平缓后的函数值作为目标函数。具体做法是，将多峰函数进行两次求对数，因此，多峰函数与适应度的关系可如下表示：
 
 用MATLAB做出适应度函数图像如下：
 
 对比前文中的图不难看出，图像得到了有效的平缓，同时不同峰之间也保持着一定的高低之别。值得一提的是，这里更主要的是给出优化遗传算法的一个思路，即可以在适应度函数上做文章。本题的适应度函数只是对多峰函数本身做了一个简单的变换，读者不妨思考一下，就本题而言有没有什么非常好的适应度函数。
 
据上文所述，适应度求值函数如下：
 
/*
    多峰函数：z = 21.5 + x *sin(4 * 3.1415926 * x) + y * sin(20 * 3.1415926 * y)
    适 应 度：log(log(z))
    约    束：-3.0 <= x <= 12.1; 4.1 <= y <= 5.8
    精    度：精确到千分位
*/
double get_fitness(const double x, const double y)
{
    return log(log(21.5 + x * sin(4 * PI * x) + y * sin(20 * PI * y)));
}
 
2.3.4、选择算子
 
本文的选择算法采用了非常常用的“轮盘赌算法”，赌盘算法的原理非常简单明了。创建赌盘时，我们将种群中所有个体的适应度求和，不妨将得到的结果称为总和适应度。然后，将每个个体的适应度除以总和适应度，然后将得到的商逐个累加，每加一次就得到赌盘的一个边界，累加完成后总和为1。如下的饼状图可以更形象的表明赌盘的原理：
 
 由上文所述，赌盘创建函数可如下编写：
 
/*
    创建赌盘
    ga      遗传算法器指针
*/
static void create_roulette(GA *ga)
{
    /* 计算赌盘中的概率 */
    ga->roulette[0] = ga->fitness[0] / ga->sum_fitness;

    for (int num = 1; num < ga->population_num - 1; num++)
    {
        ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness;
    }

    ga->roulette[ga->population_num - 1] = 1.0;
}
 
再回到选择算子，选择算子需要赌盘作为基础，其运行时，会产生一个0到1的随机数，然后在赌盘中找到该数所在的区间，这个区间对应的个体即为被选中的个体。因此，适应度越高的个体被选中的几率越大，这是合理的。当然，也存在较小的概率选出适应度较低的个体，为了避免这种情况，本文引入了竞争机制，即一次选择的过程选出2个个体，再取其中适应度较高的那个个体，具体的程序如下：
 
/*
    基因选择函数
    ga      遗传算法器指针
    返回值：返回使用轮盘赌的方式选出的个体(编号)
    说  明：选择策略为轮盘赌+随机竞争
*/
static unsigned int select(GA *ga)
{
    unsigned int index1 = 0, index2 = 0;

    /* 产生一个[0.0, 1.0]之间的浮点数 */
    double selector1 = rand() * 1.0 / RAND_MAX;
    double selector2 = rand() * 1.0 / RAND_MAX;

    /* 找出被选中的个体的索引 */
    for (; selector1 > ga->roulette[index1]; index1++);
    for (; selector2 > ga->roulette[index2]; index2++);

    return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2);
}
 
2.3.5、交叉算子
 
遗传算法的交叉操作实质上是按某种方式交换父体和母体的部分基因，常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉及算术交叉等。本文选用两点交叉法，实现过程既不复杂，也有较好的随机性，该方法可由下图示意：
 
 图中虚线指出的两个交叉点是随机产生的。具体程序如下：
 
/*
    交叉函数
    ga          遗传算法器指针
    one         输出型参数，待交叉基因
    another     输出型参数，待交叉基因
    说明：
    1.对传入的基因编码执行两点交叉操作
*/
static void cross(GA *ga, unsigned int *one, unsigned int *another)
{
    /* 1.随机产生两个交叉点的位置 */
    unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1;
    unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1;
    unsigned char min_pos = min(pos1, pos2);
    unsigned char max_pos = max(pos1, pos2);

    /* 2.截出需要交换的基因段 */
    unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1);
    unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1);
    unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1));

    /* 3.执行交叉操作 */
    *one = (*one & mask) | another_gene_seg;
    *another = (*another & mask) | one_gene_seg;
}
 
2.3.6、变异算子
 
在自然界中，基因变异可以增加个体的多样性，这对于遗传算法来说是增加了个体的随机性，可以增加找到最优解的概率。本文采用的变异算子所做的操作是随机选择基因的某一位进行反转，程序如下：
 
/*
    变异函数
    gene_code       输入型参数
    说明：
    1.对传入的基因编码执行变异操作
    2.随机选择基因编码中的一位做反转操作
*/
static void mutate(unsigned int *gene_code)
{
    unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH);
    *gene_code ^= mutate_bit;
}
 
2.3.7、繁殖函数及进化函数
 
遗传算法的主要算子都在上文中分析过了，下面要做的就是根据遗传算法的流程将这些算子整合起来以实现算法功能。在本文中，这其中涉及到两个关键的函数，即繁殖函数和进化函数。繁殖函数包括基因的复制、交叉及变异，同时本文还采用了子代竞争策略，即父代产生的两个子代个体仅保留适应度最高的，程序如下：
 
/*
    繁殖函数
    ga       遗传算法器指针
    father   从种群中选出的父体
    mother   从种群中选出的母体
    返回值：  适应度最高的子代的基因编码
    说明： 
    1.一对父体与母体将繁殖出一对子代
    2.选择出适应性更好的子代返回
*/
static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother)
{
    unsigned int son1 = ga->gene_code[father];
    unsigned int son2 = ga->gene_code[mother];

    /* 1.交叉 */
    cross(ga, &son1, &son2);

    /* 2.变异 */
    mutate(&son1);
    mutate(&son2);

    /* 3.子代竞争 */
    double son1_gene1, son1_gene2, son2_gene1, son2_gene2;
    gene_decode(son1, &son1_gene1, &son1_gene2);
    gene_decode(son2, &son2_gene1, &son2_gene2);

    return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2;
}
 
进化函数则实现了遗传算法的一次完整的迭代过程，根据上文给出的遗传算法流程图，不难进行如下编码：
 
/*
    进化函数
    ga      遗传算法器指针
*/
static void evolve(GA *ga)
{
    /* 1.申请暂存子代基因编码的内存 */
    unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int));
    
    /* 2.精英保留(将上一代中适应度最高的个体的基因编码保留) */
    descendants[0] = ga->gene_code[ga->best_individual];
    
    /* 3.选择合适的父体与母体 */
    unsigned int father = select(ga);
    unsigned int mother = select(ga);

    /* 4.繁殖(包含交叉与变异) */
    for (int num = 1; num < ga->population_num; num++)
        descendants[num] = inherit(ga, father, mother);

    /* 5.将子代记录到ga中并进行基因解码(使新一代的基因编码与基因对应) */
    for (int num = 0; num < ga->population_num; num++)
    {
        ga->gene_code[num] = descendants[num];
        gene_decode(ga->gene_code[num], &ga->gene[num].gene1, &ga->gene[num].gene2);
    }
    
    /* 5.更新种群适应度 */
    fit(ga);
    
    /* 6.更新赌盘 */
    create_roulette(ga);

    /* 7.释放之前申请的空间 */
    free(descendants);
}
 
3、运行结果及分析
 
至此，本文已经给出了一个遗传算法的C语言实现的所有关键程序。下面就调用编写的遗传算法进行测试。本文将创建含有100个个体的种群，并进行100代迭代以求解多峰函数的最大值，一次完整的调用本文实现的遗传算法的程序如下所示：
 
/* 创建遗传算法器 */
GA *ga = create_ga(get_fitness, 100);

/* 初始化遗传算法器 */
ga->init(ga);

/*迭代100代*/
for (int i = 0; i < 100; i++)
ga->evolve(ga);

/*销毁遗传算法器*/
delete_ga(ga);
 
经多次调用测试，算法执行的结果较为稳定，所得的多峰函数最大值大多在38以上，多次运行结果中最好的解为38.849744，对应的坐标为(11.625331, 5.725256)。将迭代求得的最大值用MATLAB作图如下：
 
 为验证是否找到了最优解，用MATLAB遍历求出该多峰函数在给定定义域内的最大值为38.8501，与本文求出的结果相差0.000356，可见本文实现的遗传算法表现还不算太差。
 
文中给出的程序比较散，这里给出完整程序的下载链接。

1、特征选择的几种方式
 
2、几种常见的决策树算法
 
3、过拟合处理——剪枝
 
4、连续值属性特征的处理
 
5、Bagging（代表：随机深林）
 
6、Boosting（提升）(代表：AdaBoost、GBDT、XGBoost)
 
7、决策树算法小结
 
决策树的优势力与劣势
 
 
1、特征选择的几种方式
 
决策树的最关键的问题，如何选择划分属性的顺序才能使得决策树的平均性能最好
 
举例： 
  
  
 这堆西瓜的熵是Ent(D)，按照某种属性划分之后这堆西瓜的熵是Ent(D′)，Ent(D′) <= Ent(D。这两者的差，就是这个属性对于这堆西瓜有序化的贡献。
 
1）信息熵（Entropy）
 
 
 熵（Entropy：在物理学上表示物质的混乱程度，在信息学上可以作类比。熵增加，表示信息更加混乱，熵减，表示信息更加有序。
 
2）信息增益
 
 
计算出当前属性集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益。 
 先计算根节点的信息熵： 
  
  
  
 可见：属性纹理的信息增益最大，于是它被选为划分属性，给出基于纹理对根节点进行划分的结果： 
  
 然后，决策树学习算法将对每个分支节点做进一步划分。以上图第一个分支节点(纹理=清晰)为例，该节点包含的样例集合D1中有编号为{1,2,3,4,5,6,8,10,15}的9各样例，可用属性集合为{色泽，根蒂，敲声，脐部，触感}，少了一个纹理属性。
 
3）信息增益率
 
 
4）自有信息
 
 
 根据上表数据计算自信息（属性a的可能值数目越多(即V越大)，则IV(a)的值通常会越大）：
 
 
5）基尼系数
 
 
 直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高，这和信息增益(比)是相反的。于是，对于属性集合A中，选择那个使得划分后基尼系数最小的属性作为最优划分属性。 
 例如： 
  
 
 
基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。 
 
 
2、几种常见的决策树算法
 
ID3，C4.5主要应用于分类任务，CART树，主要应用于预测任务 
  
 更多的应用场景： 
 
 
ID3
 
奥卡姆剃刀定律：当你有两个处于竞争地位的理论能得出同样的结论，那么简单的那个更好。 
 ID3算法的核心思想就是以【信息增益】来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
 
ID3的缺点： 
 1. 永远可以把N个数据分成100%纯洁的N组 
 2. 如果在『 期』这个条件下做分裂，就GG 
 
C4.5
 
C4.5是在ID3的基础上改进而提出的。ID3采用的信息增益度量存在一个缺点，它一般会优先选择有较多属性值的Feature,因为属性值多的Feature会有相对较大的信息增益?(信息增益反映的给定一个条件以后不确定性减少的程度,必然是分得越细的数据集确定性更高,也就是条件熵越小,信息增益越大).为了避免这个不足C4.5中是用【信息增益比率(gain ratio)】来作为选择分支的准则。信息增益比率通过引入一个【自信息】的项来惩罚取值较多的Feature。除此之外，C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降，
 
C4.5并不一个算法，而是一组算法—C4.5，非剪枝C4.5和C4.5规则。 
 优点：C4.5算法产生的分类规则易于理解，准确率较高。 
 缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
 
CART
 
（Classification and Regression tree）分类回归树
 
ID3中根据属性值分割数据，之后该特征不会再起作用，这种快速切割的方式会影响算法的准确率。CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用【基尼指数（Gini）】来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数，回归时使用均方差作为loss function。
 
1）、CART分类树建立算法的具体流程
 
下面我们看看CART分类树建立算法的具体流程：
 
　　　　算法输入是训练集D，基尼系数的阈值，样本个数阈值。
 
　　　　输出是决策树T。
 
　　　　我们的算法从根节点开始，用训练集递归的建立CART树。
 
　　　　1) 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
 
　　　　2) 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
 
　　　　3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数。
 
　　　　4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
 
　　　　5) 对左右的子节点递归的调用1-4步，生成决策树。
 
　　　　对于生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。
 
2）、CART回归树建立算法的具体流程
 
CART回归树和CART分类树的建立算法大部分是类似的，所以这里我们只讨论CART回归树和CART分类树的建立算法不同的地方。
 
　　　　首先，我们要明白，什么是回归树，什么是分类树。两者的区别在于样本输出，如果样本输出是离散值，那么这是一颗分类树。如果果样本输出是连续值，那么那么这是一颗回归树。
 
　　　　除了概念的不同，CART回归树和CART分类树的建立和预测的区别主要有下面两点：
 
　　　　1)连续值的处理方法不同 
 　　　　对于连续值的处理，我们知道CART分类树采用的是用基尼系数的大小来度量特征的各个划分点的优劣情况。这比较适合分类模型，但是对于回归模型，我们使用了常见的和方差的度量方式，这很好理解，被预测出错的越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。 
 　　　　CART回归树的度量目标是，对于任意划分特征A，对应的任意划分点s两边划分成的数据集D1和D2，求出使D1和D2各自集合的均方差最小，同时D1和D2的均方差之和最小所对应的特征和特征值划分点。表达式为： 
 
 
　　　　2)决策树建立后做预测的方式不同。 
 　　　　对于决策树建立后做预测的方式，上面讲到了CART分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。而回归树输出不是类别，它采用的是用最终叶子的均值或者中位数来预测输出结果
 
3、过拟合处理——剪枝
 
完整的决策树并不是一棵分类预测新数据对象的最佳树。其原因是完整的决策树对Training Data描述过于“精确”。我们知道，随着决策树的生长，决策树分枝时所处理的样本数量在不断减少，决策树对数据总体代表程度在不断下降。在对根节点进行分枝时，处理的是全部样本，再往下分枝，则是处理的不同分组下的样本。可见随着决策树的生长和样本数量的不断减少，越深层处的节点所体现的数据特征就越个性化，可能出现如上推理规则：“年收入大于50000元且年龄大于50岁且姓名叫张三的人购买了此产品”。这种过度学习从而精确反映Training Data特征，失去一般代表性而无法应用于新数据分类预测的现象，叫过度拟合（Overfitting）或过度学习。那我们应该怎么办呢？修剪！
 
常用的修剪技术有预修剪（Pre-Pruning）和后修剪（Post-Pruning）。
 
预剪枝（pre-pruning）：
 
1、预剪枝就是在构造决策树的过程中，先对每个结点在划分前进行估计，若果当前结点的划分不能带来决策树模型泛华性能的提升，则不对当前结点进行划分并且将当前结点标记为叶结点。
 
总结： 对比未剪枝的决策树和经过预剪枝的决策树可以看出：预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但是，另一方面，因为预剪枝是基于“贪心”的，所以，虽然当前划分不能提升泛华性能，但是基于该划分的后续划分却有可能导致性能提升，因此预剪枝决策树有可能带来欠拟合的风险。
 
2、事先先指定决策树的最大深度，或最小样本量，以防止决策树过度生长。前提是用户对变量聚会有较为清晰的把握，且要反复尝试调整，否则无法给出一个合理值。注意，决策树生长过深无法预测新数据，生长过浅亦无法预测新数据。
 
后剪枝（post-pruning）：
 
后剪枝就是先把整颗决策树构造完毕，然后自底向上的对非叶结点进行考察，若将该结点对应的子树换为叶结点能够带来泛华性能的提升，则把该子树替换为叶结点。
 
对比预剪枝和后剪枝，能够发现，后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险小，泛华性能往往也要优于预剪枝决策树。但后剪枝过程是在构建完全决策树之后进行的，并且要自底向上的对树中的所有非叶结点进行逐一考察，因此其训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。
 
决策树中的C4.5、C5.0、CHAID、CART和QUEST都使用了不同 剪枝策略。
 
4、连续值属性特征的处理
 
 
 对于数据集中的属性“密度”，决策树开始学习时，根节点包含的17个训练样本在该属性上取值均不同。我们先把“密度”这些值从小到大排序： 
  
 然后计算可能的属性分割点： 
  
 下面开始计算t 取不同值时的信息增益： 
  
 计算得到的各属性的信息增益值： 
  
 比较能够知道纹理的信息增益值最大，因此，“纹理”被选作根节点划分属性，下面只要重复上述过程递归的进行，就能构造出一颗决策树： 
  
 有一点需要注意的是：与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。
 
5、Bagging(代表：随机深林)
 
bagging方法bootstrap aggregating（自助聚集）的缩写，采用的是随机有放回的选择训练数据然后构造分类器，最后组合。 
 
 
随机深林
 
整个随机森林算法的过程中，有两个随机过程：
 
 
 
第一个: 【输入数据】是随机的从整体的训练数据中选取一部分作为一棵决策树的构建，而且是有放回的选取； 
 第二个: 每棵决策树的构建所需的【特征】是从整体的特征集随机的选取的;
 
 
这两个随机过程使得随机森林很大程度上避免了过拟合现象的出现。
 
过程：
 
1、从训练数据中选取n个数据作为训练数据输入，一般情况下n是远小于整体的训练数据N的，这样就会造成有一部分数据是无法被去到的，这部分数据称为袋外数据，可以使用袋外数据做误差估计。
 
2、选取了输入的训练数据的之后，需要构建决策树，具体方法是每一个分裂结点从整体的特征集M中选取m个特征构建，一般情况下m远小于M。
 
3、在构造每棵决策树的过程中，按照选取最小的基尼指数进行分裂节点的选取进行决策树的构建。决策树的其他结点都采取相同的分裂规则进行构建，直到该节点的所有训练样例都属于同一类或者达到树的最大深度。
 
4、 重复第2步和第3步多次，每一次输入数据对应一颗决策树，这样就得到了随机森林，可以用来对预测数据进行决策。
 
5、 输入的训练数据选择好了，多棵决策树也构建好了，对待预测数据进行预测，比如说输入一个待预测数据，然后多棵决策树同时进行决策，最后采用多数投票的方式进行类别的决策。
 
 
随机森林算法的注意点：
 
1、 在构建决策树的过程中是不需要剪枝的。 
 2、 整个森林的树的数量和每棵树的特征需要人为进行设定。 
 3、 构建决策树的时候分裂节点的选择是依据最小基尼系数的。
 
随机森林有很多的优点：
 
a. 在数据集上表现良好，两个随机性的引入，使得随机森林不容易陷入过拟合。
 
b. 在当前的很多数据集上，相对其他算法有着很大的优势，两个随机性的引入，使得随机森林具有很好的抗噪声能力。
 
c. 它能够处理很高维度（feature很多）的数据，并且不用做特征选择，对数据集的适应能力强：既能处理离散型数据，也能处理连续型数据，数据集无需规范化。
 
d. 在创建随机森林的时候，对generlization error使用的是无偏估计。
 
e. 训练速度快，可以得到变量重要性排序。
 
f. 在训练过程中，能够检测到feature间的互相影响。
 
g 容易做成并行化方法。
 
h. 实现比较简单。
 
6、Boosting（提升）(代表：AdaBoost、GBDT、XGBoost)
 
Bagging只是将分类器进行简单的组合，实际上，并没有发挥出分类器组合的威力来。
 
 
 
Boosting是一种提高任意给定学习算法准确度的方法。 
 Boosting的提出与发展离不开Valiant和 Kearns两位大牛的不懈努力，下面是他们的“奋斗史”： 
 Boosting的思想起源于 Valiant提出的 PAC ( Probably Approximately Correct)(可能近视正确)学习模型。Valiant和 Kearns提出了弱学习和强学习的概念： 
 弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法） 
 强学习：识别准确率很高并能在多项式时间内完成的学习算法 
 同时 ,Valiant和 Kearns首次提出了 PAC学习模型中弱学习算法和强学习算法的等价性问题,即任意给定仅比随机猜测略好的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需找到一个比随机猜测略好的弱学习算法就可以将其提升为强学习算法 ,而不必寻找很难获得的强学习算法。
 
 
 
1）、AdaBoost
 
AdaBoost通过改变样本的分布突出错分类，并进而训练弱分类器得到弱分类器的权重，最终根据权重整合在一起得到最终的强分类器。
 
Boosting这其实思想相当的简单，举个例子:
 
 
 
对一份数据集建立M个模型（比如分类），一般这种模型比较简单，称为弱分类器(weak learner)。每次分类都将上一次分错的数据权重提高一点再进行分类，这样最终得到的分类器在测试数据与训练数据上都可以得到比较好的成绩。 
 
 
 
Boosting算法基本步骤：
 
 
 
1、先对N个训练样本S1的学习得到一个弱分类器M1； 
 2、将S1中分错的样本和其他新的数据一起构成新的N个训练样本S2，再得到一个弱分类器M2； 
 3、将S1和S2中都分错的样本和其他新的数据一起构成新的N个训练样本S3，再得到一个弱分类器M3； 
 4、最终得到一堆弱分类器，可根据弱分类器的多数投票表决。 
 
 
 
2）、GBDT(Gradient Boosted Decision Tree)梯度提高决策树
 
 
 
 
首先gbdt 是通过采用加法模型（即基函数的线性组合），以及不断减小训练过程产生的残差来达到将数据分类或者回归的算法。
 
 
 
GBDT训练过程： 
  
 gbdt通过多轮迭代,每轮迭代产生一个弱分类器，每个分类器在上一轮分类器的残差基础上进行训练。对弱分类器的要求一般是足够简单，并且是低方差和高偏差的。因为训练的过程是通过降低偏差来不断提高最终分类器的精度。 
 弱分类器一般会选择为CART TREE（也就是分类回归树）。由于上述高偏差和简单的要求 每个分类回归树的深度不会很深。最终的总分类器 是将每轮训练得到的弱分类器加权求和得到的（也就是加法模型） 
  
 但是其实我们真正关注的： 
 1.是希望损失函数能够不断的减小； 
 2.是希望损失函数能够尽可能快的减小。所以如何尽可能快的减小呢？ 
 让损失函数沿着梯度方向的下降。这个就是gbdt 的 gb的核心了。 利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值去拟合一个回归树。 
 gbdt 每轮迭代的时候，都去拟合损失函数在当前模型下的负梯度。 
 这样每轮训练的时候都能够让损失函数尽可能快的减小，尽快的收敛达到局部最优解或者全局最优解。
 
 
gbdt如何选择特征?
 
其实就是CART选择特征的过程。
 
gbdt 如何构建特征 ?
 
 
 
gbdt 本身是不能产生特征的，但是我们可以利用gbdt去产生特征的组合。 
  
 如图所示，我们 使用 GBDT 生成了两棵树，两颗树一共有五个叶子节点。我们将样本 X 输入到两颗树当中去，样本X 落在了第一棵树的第二个叶子节点，第二颗树的第一个叶子节点，于是我们便可以依次构建一个五纬的特征向量，每一个纬度代表了一个叶子节点，样本落在这个叶子节点上面的话那么值为1，没有落在该叶子节点的话，那么值为 0. 
 于是对于该样本，我们可以得到一个向量[0,1,0,1,0] 作为该样本的组合特征，和原来的特征一起输入到逻辑回归当中进行训练。实验证明这样会得到比较显著的效果提升。
 
 
gbdt 如何用于分类的 ?
 
gbdt 如何用于分类：查看转载
 
3）、XGBoost（X (Extreme) GBoosted）
 
 
  
 https://blog.csdn.net/ice_martin/article/details/63683657
 
7、决策树算法小结
 
　　　　终于到了最后的总结阶段了，这里我们不再纠结于ID3, C4.5和 CART，我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。这部分总结于scikit-learn的英文文档。
 
　　　　首先我们看看决策树算法的优点：
 
　　　　1）简单直观，生成的决策树很直观。
 
　　　　2）基本不需要预处理，不需要提前归一化，处理缺失值。
 
　　　　3）使用决策树预测的代价是O(log2m)。 m为样本数。
 
　　　　4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
 
　　　　5）可以处理多维度输出的分类问题。
 
　　　　6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
 
　　　　7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。
 
　　　　8） 对于异常点的容错能力好，健壮性高。
 
　　　　我们再看看决策树算法的缺点:
 
　　　　1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
 
　　　　2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
 
　　　　3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
 
　　　　4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
 
　　　　5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。