自动化特征工程：基于遗传编程（一）

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

    基本思想及流程
    遗传编程也叫基因编程或GP，是一种从生物进化过程得到灵感的自动化生成和选择计算程序完成用户定义任务的程序，比遗传算法使用范围更广。使用遗传编程的方法进行特征构建，即是通过计算机程序自动化生成特征，并通过选择、交叉、变异等过程，最终得到相对较好的特征的过程。遗传编程方法与遗传算法流程是类似的，主要步骤如下：
step1：随机产生初始种群，每个个体表示染色体的基因型；
step2：计算每个个体的适应度，并判断是否满足优化准则，若满足，则输出最佳个体极其代表的最优解，并结束算法；若不满足，则转入下一步。
step3：根据适应度选择再生个体，适应度高的个体选中的概率高，反之，适应度低的个体被选中的概率低，甚至可能被淘汰；
step4：根据一定交叉概率和交叉方法生成子代个体；
step5：根据一定变异概率和变异方法，生成子代个体；
step6：由交叉和变异产生新一代种群，返回第二步。

      最优化准则一般根据问题的不同有不同的确定方式，通常采取如下之一作为判断条件：
1.种群中个体的最大适应度超过了设定值；
2.种群中个体的平均适应度超过了设定值；
3.世代数超过设定值；
4.种群中个体最大适应度除以平均适应度超过了设定值；


     根据算法流程，需要先基于原始特征产生候选特征。首先假定所有原始特征都是数值型的，那么经过这些特征的组合运算，我们就可以得到一个新特征，如果组合运算的规则是随机产生，那么就可以得到用于遗传编程的初始种群。一般地，用二叉树存储运算规则，叶子节点表示原始特征，非叶子节点表示数学运算符，通常有加减乘除的二元运算符和正余弦、对数、倒数等一元运算符。
    于是问题就变为，如何根据原始特征随机生成二叉树，并根据二叉树确定新的表达式计算新特征f1-fn,并使用新特征建立预测模型，通过交叉验证的方法计算模型的评价指标，如误差平方和（回归）或精确度/AUC等（分类），再与基于原始属性建立的预测模型其评价指标比较，计算减少量，以此计算个体的适应度。需要注意的是，一个二叉树就相当于一个基因，一个基因产生一个特征，一个个体包含给定长度的基因数目，代表由多个特征组合的数据集。所谓最优特征组合是与基于原始属性建立的预测模型相比较的。

     下面给出R实现的代码：

# ------------------------ 基于遗传编程方法的特征构建 -------------------------------------
# f:一元或二元运算函数
# a：第一个参数
# b：如果f是一元运算函数，则b为空，否则代表第二个参数
g <- function(f,a,b=NULL){
    if(is.null(b)) f(a)
    else{
      f(a,b)
    }
  }

# 针对常见的一元运算（正弦、余弦、对数。。。）、二元运算（+、-、×、÷）可重新定义函数，正、余弦不需处理
Dpow0_5 <- function(x)return((x-min(x)+0.01)^0.5)  
Dpow3 <- function(x)return(x^3)
Dpow2 <- function(x)return(x^2)
Dinv <- function(x)return(1*sign(x)/abs(x)+0.0001)
Dadd <- function(x,y)return(x+y)
Dsub <- function(x,y)return(x-y)
Dmul <- function(x,y)return(x*y)
Ddiv <- function(x,y)return(x*sign(y)/(abs(y)+0.0001))
Dlog <- function(x)return(sign(x)*log(abs(x)+1))


# # 测试
# g(Dmul,g(Dadd,g(sin,5),10),g(Dlog,46))

# 根据二叉树的基本形态，随机特征构建主要分为满二叉树和偏二叉树两类

# 满二叉树方式构建特征表达式，定义函数genFullTreeExp

# 定义二元运算函数集合
twoGroup <- c("Dadd","Dsub","Dmul","Ddiv")
# 定义一元运算函数集合
oneGroup <- c("cos","sin","Dlog","Dpow0_5","Dpow3","Dpow2","Dinv")

# 随机增加一元运算符,以一定概率pstd向节点v上封装一层一元运算
addoneGroup <- function(v,pstd=0.3){
  if (runif(1,0,1) < pstd){
    return(paste("g(",sample(oneGroup,1),",<",v,">)",sep = ""))
  }else{
    return(v)
  }
}

# 构建满二叉树，并生成数学表达式，genFullTreeExp函数以递归的方式将v分成两部分，
# 并依次进行二元组合，直到长度为1为止
genFullTreeExp <- function(v){
  N <- length(v)/2
  midV <- NULL
  for (i in 1:N){

    if (v=="0" && v[i+N] != "0"){
      midV <- c(midV,paste("g(",sample(oneGroup,1),",<",addoneGroup(v[i+N]),">)",sep = ""))
    }else if(v !="0" && v[i+N] == "0"){
      midV <- c(midV,paste("g(",sample(oneGroup,1),",<",addoneGroup(v),">)",sep = ""))
    }else if(v !="0" && v[i+N] != "0"){
      midV <- c(midV,paste("g(",sample(twoGroup,1),",<",addoneGroup(v),">,<",addoneGroup(v[i+N]),">)",sep = ""))
    }
  }

if (length(midV)==1)
    return(addoneGroup(midV))
  else{genFullTreeExp(midV)}
}

# # 假设原始属性的下标为1~8，nMax=10，0为虚拟特征，则从原始属性随机抽取N个属性存在selFidx中
# # 若选择的原始属性不是2的r次方个，则通过虚拟属性0占位
# nMax <- 10
# N <- sample(2:nMax, 1)
# # 定义原始数据集中属性的下标
# featureIdx = 1:8
# selFidx <- sample(c(sample(featureIdx, N, replace = T),
#                     rep(0,2^ceiling(log(N)/log(2)) - N)))
# selFidx[selFidx > 0] = paste("Xs", selFidx[selFidx > 0], sep = "")
# selFidx

#
# # 按满二叉树方式生成特征表达式
# treeExp = genFullTreeExp(selFidx)
# treeExp
# # 变量treeExp中带有"<"和">"以便提取表达式中的节点信息，去掉即可得到完整表达式
# gsub(">", "", gsub("<", "", treeExp))

# 构建偏二叉树，并生成数学表达式
genSideTreeExp <- function(v){
  # 以一定的概率p，加上n（通常为1）个一元运算符
  if(length(v)==1)return(addoneGroup(v))
  else{
    v[2]=paste("g(",sample(twoGroup,1),",<",addoneGroup(v[1]),">,<",
               addoneGroup(v[2]),">)",sep = "")
    v[1]=NA
    genSideTreeExp(as.character(na.omit(v)))
  }
}

# # 假定原始属性下标为1~8，nMax=10，则从原始属性随机选取N个属性如下
# N <- sample(2:nMax, 1)
# selFidx <- sample(featureIdx, N, replace = T)
# selFidx = paste("Xs", selFidx, sep = "")
# selFidx
#

# # 生成特征表达式
# treeExp = genSideTreeExp(selFidx)
# treeExp
# # 变量treeExp中带有"<"和">"以便提取表达式中的节点信息，去掉即可得到完整表达式
# gsub(">", "", gsub("<", "", treeExp))
#

# 随机选择满二叉树或偏二叉树，生成特征表达式randomGetTree
# 从原始数据特征，随机获取表达树
# dataName：字符串，表示所用数据集对象,通常为外部全局数据框对象
# nMax：一次最多从特征中可放回抽样次数，默认为10
randomGetTree <- function(dataName, featureIdx, nMax=10){
  # 1.随机抽取N个特征下标
  N <- sample(2:nMax, 1)
  # 2.随机决定使用满二叉树还是偏二叉树
  if(sample(c(0,1), 1) == 1){
    # 评估满二叉树，叶子节点的数量，通过生成虚拟节点，符合2^(H-1)个
    # 其中H为二叉树深度，
    # 对生成的结果随机排序，并生成特征字符向量
    selFidx <- sample(c(sample(featureIdx, N, replace = T),
                        rep(0,2^ceiling(log(N)/log(2)) - N)))
    selFidx[selFidx>0]=paste(dataName, "[,", selFidx[selFidx>0], "]", sep = "")
    treeExp = genFullTreeExp(selFidx)
  }else{
    #构建偏二叉树，并生成数学表达式
    selFidx <- sample(featureIdx, N, replace = T)
    selFidx = paste(dataName, "[,", selFidx, "]", sep = "")
    treeExp = genSideTreeExp(selFidx)
  }
  # 3.返回二叉树表达式和适应度结果
  return(treeExp)
}

# # 以iris数据集为例，随机生成特征表达式
# out = randomGetTree("iris", 1:4)
# out
# tExp = gsub(">", "", gsub("<", "", out))
# tExp
# eval(parse(text = tExp))




由于篇幅原因，未完待续！

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏1 回帖

关键词：自动化 计算机程序 Step 预测模型 遗传算法