摘要：公式树模块的作用是，从训练集X和function_set中进行随机采样，生成一棵公式树，同时提供子树变异、 crossover、hoist变异和点变异的方法。
本文分享自华为云社区《公式树开源库分析》，作者：鲤鱼君 。
公式树模块的作用是，从训练集X和function_set中进行随机采样，生成一棵公式树，同时提供子树变异、 crossover、hoist变异和点变异的方法。
用到的数据结构:
terminal_stack: 存储是几元运算的一个栈
symbol_tree: lisp_tree 列表树, Lisp列表是基于广义表的结构，所以很容易将一个列表表达成树结构。 S-表达式可能以其在Lisp家族的编程语言中的使用而为人所知，约翰·麦卡锡发明LISP于1958年，首次由史蒂夫·拉塞尔实施在IBM704计算机上，它特别适合用于人工智能方案，因为它有效地处理的符号信息。
在前缀表示法，运算符在自己操作数前写。例如，表达式
被写成
例如公式：
它也可以写作：
写成S表达式就变成了这个
对应的二叉树
也就是说s表达式对应于符号树的先序遍历
算法输入:function_set[‘add’, ‘sub’, ‘mul’] , arities{2:[‘add’, ‘sub’, ‘mul’]}, method: grow , max_depth:3(2-4内的一个随机数)
画成流程图就是
给symbol_tree里面的元素赋予权重如果是算子就是0.9 不是算子就是0.1
比如tree是
那么久赋予权重
然后进行归一化就是除以sum
这里是采用轮盘赌法来选择切割点的
步骤
1）随机生成一个（0,1）内的随机值比如生成
2）找到随机值在probs中应该在的位置这里这个位置就是start的位置
3）初始化 end = start=2
如果end - start < stack那么
如果node是算子的话那么stack要加上元数
end 自身一直加一直到program最后
crossover的目的是进行子树交叉
第一步从符号树模块获得随机子树
第二步从其他符号树个体中获得随机子树
第三步获得交叉后的符号树
由p_subtree_mutation参数控制。这是一种更激进的变异策略：优胜者的一棵子树将被另一棵完全随机的全新子树代替。
hoist变异是一种对抗公式树膨胀（bloating，即过于复杂）的方法：从优胜者公式树内随机选择一个子树A，再从A里随机选择一个子树B，然后把B提升到A原来的位置，用B替代A。hoist的含义即「升高、提起」。
第一步获取一个随机子树A
第二步从子树A中获取一个子树B
第三步 把B提升到A原来的位置，用B替代A
由p_point_replace参数控制。一个随机的节点将会被改变，比如加法可以被替换成除法，变量X0可以被替换成常数-2.5。点变异可以重新加入一些先前被淘汰的函数和变量，从而促进公式的多样性。
第一步复制符号树，并获取一个随机的点
第二步遍历mutate的node节点，如果node是一个Function就替换，不是的话就加入常量或者feature
如果不是function
第一种情况
第一步：进行参数校验
第二步 获得随机种子，然后获得袋外数据和袋内数据的index
其他函数
sample_without_replacement(n_population, n_samples, random_state,method): 采样函数，随机获取袋外数据，从集合[0，n_population]中选择n_samples个数据，有放回的抽样
参数介绍
接口
先执行X的算法得到y_pred，然后根据y,y_pred以及权重计算误差
入参
属性：
目的：找到表现最好的符号树
第一步：n_programs表示种群里的一个组内有多少颗树，这里要循环n_programs次
初始化
第二步根据method的概率选择突变的类型
第三步 根据参数和第二步得到的program生成公式树
然后
这里的genome存储的是之前生成子树的过程中删掉的信息把他赋值给parents
第四步 根据sample_weight中的权重信息对特征列赋予权重。
计算袋外数据的fitness
最后循环n次就得到了n颗变异后的子树programs，它里面有两个私有属性raw_fitness_，oob_fitness_分别存储了袋内袋外数据的适用性
_verbose_reporter：控制日志输出
入参：
校验：检查X和y的长度是否一致、hall_of_fame、function_set、_arities是不是正常以及metric是不是Fitness类型 自身是否继承于TransformerMixin抽象类
然后把概率放到list里面，逐步加
然后校验_method_probs、init_method、const_range、init_depth、feature_names进行类型检查和范围检查
如果不是warm_start模式就准备好_programs和 run_details_字典
然后是对n_more_generations进行校验
循环层（从prior_generations到generations）
1）记录时间找到父类
2）并行运行程序
对数据进行合并，得到下一代变异的种群
得到种群的所有的个体的fitness和length是一个list
3）惩罚系数对fitness进行约束
4）删除被淘汰的个体
对应代码
处理early stopping
到这里循环结束，得到所有的世代。
a）首先得到hall_of_fame个索引
对最后一代的种群里所有的个体（其中属于hall_of_fame的）进行计算得到预测的值
如果指标是spearman系数的话，计算得到evaluation每一组数据的排序值
然后计算相关系数矩阵
点击关注，第一时间了解华为云新鲜技术~