1 引言

近红外分析技术近年来发展迅速,其具有快速、高效、无损的特点,已被广泛应用于烟草、食品、石油、医药等领域^[1-5]。近红外光谱分析技术利用近红外光谱提取物质信息对物质进行定性和定量分析。在定性分析中,近红外光谱分析技术主要用于真伪鉴别、品种识别、质量等级识别、产地识别等。烟叶产地识别在卷烟生产计算机辅助设计和维护中起着重要作用。传统的烟叶产地的识别方法主要有专家感官评吸法、化学成分鉴别法,专家感官评吸法因主观因素导致识别准确率较低,化学成分鉴别法会产生较大的工作量。为解决这些问题,有研究者采用近红外模式识别方法对烟叶产地进行鉴别。如Hana等^[6]采用神经元网络算法建立了近红外光谱烟叶产地识别模型,对美国一些地区的烟叶进行分类研究。束茹欣等^[7]利用主成分分析(PCA)结合支持向量机(SVM)算法通过近红外光谱对烟叶产地进行分类。施丰成等^[8]采用偏最小二乘法-判别分析(PLS-DA)算法对国内一些烟叶产区的烟叶近红外光谱数据建立烟叶产地识别模型。随机森林算法(RF)在其他领域的分类识别中应用较为广泛^[9-11],但在烟叶产地识别中的应用还很少见。本文将随机森林算法应用于近红外烟叶产地识别中。随机森林是一种基于Bagging机制的集成分类算法。随机森林识别模型是由高维近红外光谱数据构建的,由于决策树节点分裂候选变量的随机选取,高维特征中的噪声、无关变量和冗余变量导致了随机森林包含大量的“弱决策树”,这些“弱决策树”消耗大量内存空间,并且降低随机森林的分类准确性。因此,在修剪随机森林的规模时,如何既要保证决策树多样性,又要提高决策树的准确性显得尤为关键。

现有的随机森林修剪方法有边缘函数修剪法^[12]、分类间隔加权法^[13]、差异度测度法^[14]。这些方法首先按照某种方式对决策树排序,然后根据自身的目标函数,将决策树逐一递归加入最优子集,但是逐一递归方式计算繁琐,且在搜索过程中不一定收敛到全局最优解。为了简化搜索过程并在全局上把控最优解,本文提出采用改进的自适应遗传算法对随机森林进行修剪。自适应遗传算法在一定程度上改善了遗传算法因固定的交叉和变异概率而导致早熟和收敛慢的问题^[15],但是在选择操作上却没有自适应改变。选择操作对于改善种群的优良程度具有显著效果,在种群进化过程中占据极其重要的位置。因此,如何优化选择操作也值得研究者关注。

针对上述问题,本文提出了改进的基于自适应遗传算法的修剪随机森林算法(AGARFP)。在选择操作上提出基于多轮轮盘赌法和锦标赛法相结合的选择算子,并采用改进的自适应遗传算法对随机森林进行修剪,期望在缩减随机森林规模的同时能提高模型识别准确率。

2 基于自适应遗传算法的修剪随机森林算法

2.1 随机森林

随机森林是由多棵决策树 hX,θi(i=1,2,…,m)组成的集成学习方法,其中h(·)表示决策树基分类器,X为待测样本,θ_i为独立同分布随机向量,θ_i决定了决策树的生长过程,m为随机森林的规模。该算法首先采用Bootstrap重采样法获得m个有差异的训练集。然后,运用随机子空间策略和分类与回归树(CART)算法构建单棵决策树。采用Bagging机制生成含有m棵决策树的随机森林,根据投票法判别样本的最终类别归属。即

H(x)=argmaxY∑i=1mIhX,θk=Y,(1)

式中H(x)为随机森林模型,Y为目标类别变量,I·为示性函数,argmax_Y表示 ∑i=1mIhX,θk=Y的最大值对应的类别Y的取值。随机森林的样本选择和节点分裂候选属性均具有随机性,这种随机性既保证了决策树的多样性,又降低了单棵决策树的预测能力。因此,从随机森林中优选出预测能力强的决策树集合来提高随机森林的整体预测水平极为关键。

2.2 改进的自适应遗传算法的选择算子

自适应遗传算法的遗传操作主要有:选择、交叉和变异。选择操作主要有轮盘赌法和锦标赛法,轮盘赌法使种群中的每个个体都有机会被选择,从而保证了种群的多样性。但是这种概率形式致使该算子误差较大,导致有时适应度高的个体不被选择,降低了种群的收敛速度^[16]。锦标赛法选择算子的收敛速度快,增加了优良个体被选择的概率,克服了轮盘赌法适应度高的个体不能被保留的缺陷,但该算子易早熟,全局收敛效果不够理想^[17]。

为了发挥自适应遗传算法交叉、变异的优势,并改善自适应遗传算法的选择操作,本课题组改进了自适应遗传算法的选择算子。改进的选择算子综合了轮盘赌法子代的多样性和锦标赛法收敛速度快的优势,根据种群进化程度,设置不同的选择算子和最优保存策略。该算子首先计算个体适应度值的标准差,然后通过多次实验调节阈值,并根据随机森林规模和分类准确率进行综合比较,确定适应度值标准差阈值α=0.05。当种群中个体适应度值的标准差小于阈值α时,说明此时种群分布比较集中,具备一定的全局收敛能力,选用锦标赛法选择算子和严格的种群保留策略,可以加快种群的收敛速度。否则,选用轮盘赌法和宽松的种群保留策略来保证种群的多样性。基于自适应遗传算法的修剪随机森林算法的流程图如图1所示。

图 1. 基于自适应遗传算法的修剪随机森林算法流程图

Fig. 1. Flow chart of AGARFP

下载图片 查看所有图片

改进的选择算子步骤如下。

步骤1:初始化父代种群Z=a1,a2,…,aM,每条染色体的适应度大小为F_ai,其中i=1,2,…,M。

步骤2:计算个体适应度值的标准差σ=∑i=1MFbi-F̅b2/M,其中F_bi为第i条染色体的适应度大小, F̅b=∑i=1MF_bi/n,设置阈值α。若σ>α,跳转到步骤3;否则,跳转到步骤4。

步骤3:计算每条染色体被选择的概率P_bi=F_bi/∑i=1MF_bi,根据P_bi将 0,1划分为M个子区间。转动M轮,产生M个落在 0,1之间的随机数。统计各子区间的分布情况D=d1,d2,…,dM,取最大值d_i=max d1,d2,…,dM所对应的染色体b_i,加入集合A中。重复该过程,直到 A=M。群体A中的染色体按其适应度值降序排序,将前5%的个体不进行交叉、变异操作直接替换子代后5%的个体。

步骤4:将种群Z'=b1,b2,…,bM随机等分成若干组,随机且有放回地选取两组中的最优个体加入集合B中。重复该过程,直到 A=M。群体A中的染色体按其适应度值降序排序,将前15%的个体不进行交叉、变异操作直接替换子代后15%的个体。

2.3 基于自适应遗传算法的修剪随机森林算法

采用改进的自适应遗传算法对随机森林进行修剪,随机森林修剪方法和步骤如下。

步骤1:采用Bootstrap重采样方法生成m个有差异的训练集F=F1,F2,…,Fm。每个训练集包含k个特征n个样本,即F_i=f11…f1k︙︙fn1…fnk。对每个训练集采用CART算法生成决策树,运用Bagging机制构造随机森林。

步骤2: 基于自适应遗传算法的修剪随机森林算法,具体步骤如下。

1) 染色体编码:采用二进制编码方式初始化种群Z=a1,a2,…,aM,每条染色体代表一个随机森林分类器,每个决策树代表一个基因。 “1”表示决策树被选择,“0”表示决策树不被选择。

2) 适应度评估:算法目标为获取分类准确率最高时的基分类器集合,因此将自适应遗传算法的适应度函数定义为

F=1n∑i=1nsi,(2)

式中i=1,2,…,n;n为训练集的长度;样本s_i若被预测正确则为“1”,反之为“0”。

3) 选择:选择操作采用2.2节所述方法。

4) 交叉和变异:采用两点交叉和单点变异,交叉概率P_c和变异概率P_m分别为

Pc=Pc1-Pc1-Pc2f'-favgfmax-favg,f'≥favgPc1,f'<favg,(3)Pm=Pm1-Pm1-Pm2fmax-ffmax-favg,f≥favgPm1,f<favg,(4)

式中P_c1=0.9,P_c2=0.5,交叉概率保持在[0.5,0.9],f'为交叉操作的两个个体中较大的适应度值,f_avg为群体平均适应度值,f_max为群体最大适应度值,P_m1=0.1,P_m2=0.01,变异概率保持在[0.01,0.1],f为变异个体适应度值。

5) 重复步骤2)、3)、4),直至达到最大迭代代数N,算法停止。

3 实验部分

3.1 数据来源及样本制备

收集了300个由卷烟企业提供的来自云南、山东、福建、湖南、广东共5个不同烟产地的烟叶样本,根据各个省份的烟叶生态条件、种植区域、规模及品种布局,收集不同主栽品种的正常生长的烟叶,保证了样本的代表性。为了保证样本的均匀性,每个产区样本采集60个,其中随机选取45个样本作为训练集,15个样本作为测试集。使用丹麦FOSS公司生产的Foss DS2500型光谱仪,采用漫反射方式采集烟叶样本的光谱数据,分辨率为8 nm,扫描范围为1100~2500 nm,扫描波长间隔为5 nm。每个烟叶样本置于烘箱中于40 ℃干燥2 h,磨粉过60目(60目=250 μm)筛,每个样本称取20 g装于袋中密封,待测。

3.2 数据预处理

采用Norris Gap一阶导数加5个数据点平滑的光谱预处理方法,使用Unscrambler 9.7软件对数据进行预处理。

3.3 参数设置

通过Bootstrap重采样方法获得200个样本集,对每个样本集运用CART算法生成决策树,构建包含200棵决策树的随机森林,即染色体长度为200。初始化种群大小为30,最大遗传代数为150代。

4 结果分析

4.1 选择算子性能对比

为了验证选择算子的性能,以测试集作为实验样本,将所提自适应选择算子与轮盘赌法选择算子、锦标赛法选择算子做比较,结果如图2所示。表1为不同选择算子的收敛速度、最优解对比结果。

图 2. 基于不同选择算子的遗传算法适应度进化曲线。(a)轮盘赌法选择算子;(b)锦标赛法选择算子;(c)所提自适应选择算子

Fig. 2. Evolution curves of fitness for genetic algorithms with different selection operators. (a) Roulette method selection operator; (b) tournament method selection operator; (c) proposed adaptive selection operator

下载图片 查看所有图片

由图2可知,在一定迭代次数内,适应度值随迭代次数的增加逐步上升。原因是准确性强的个体所占比重逐步提高,展现了自适应遗传算法全局优化搜索的优势。结合表1可知:锦标赛法选择算子在收敛速度上展现了明显的优势,但最优解不够理想,表明了该算子易早熟,难以收敛到最优解;轮盘赌法的收敛速度最低,但最优解表现良好,该算子收敛速度慢,不易陷入局部最优;自适应选择算子在保持了较快收敛速度的前提下,最优解达到了0.9467,高于采用其他两种选择算子的自适应遗传算法。综合对比来看,所提出的选择算子不但收敛速度较快,而且拥有比较理想的最优解。

4.2 模型识别性能对比

采用改进的自适应遗传算法对随机森林进行修剪,最优染色体编码为“1”的基因共71个,编码为“0”的基因共129个,即修剪随机森林规模为71时,适应度值最大。图3为随机森林规模与分类准确度的关系。

图 3. 随机森林规模与分类准确度的关系

Fig. 3. Relationship between random forest size and classification accuracy

下载图片 查看所有图片

由图3可知:当随机森林的规模小于136时,分类精度明显较低,这是由于较少的基分类器无法组成实现目标结果的强分类器组合,基分类器存在不均匀性,所以投票选取的结果不具有代表性;当树的数量达到136个时,分类准确度达到最大;但随着基分类器的数量增加,分类准确度逐渐下降,原因是基分类器之间开始出现冗余,降低了随机森林的分类能力。为了体现Bagging机制以及修剪随机森林的优势,分别采用CART决策树、随机森林和基于自适应遗传算法的修剪随机森林模型对样本进行分类,并与SVM、PLS-DA和相似分类法(SIMCA)进

行比较,结果如表2所示。随机森林与基于自适应遗传算法的修剪随机森林的分类效果图如图4所示。

由表2结合图4分析可知:单个CART决策树的分类效果最差,分类准确率仅为73.33%;基于自适应遗传算法的修剪随机森林和随机森林分别在决策树数量为71和136时的分类准确度最高,分别为94.67%和92.00%;与随机森林相比,基于自适应遗传算法的修剪技术不但使决策树的规模缩减了65个,且分类准确率提高了2.67%。随机森林规模的缩小使得模型运行占用内存空间减少。随机森林和基于自适应遗传算法的修剪随机森林的分类准确率要高于SVM、径向基函数神经网络(RBFNN)的分类准确率,这也说明了随机森林分类器在处理高维数据时的优势,特别是在处理含有大量噪声的光谱数据时,表现出了较好的容噪能力。同时,与PLS-DA和簇类独立软模式法(SICMCA)相比,应用所提方法进行烟叶产地识别获得了更好的效果,表明所提方法在处理烟叶产地分类问题时具有可行性。

图 4. 随机森林与基于自适应遗传算法的修剪随机森林的分类效果图。(a)随机森林;(b)基于自适应遗传算法的修剪随机森林

Fig. 4. Classification effect diagrams of RF and AGARFP. (a) RF; (b) AGARFP

下载图片 查看所有图片

5 结论

提出了基于自适应遗传算法的修剪随机森林算法,并建立了烟叶产地识别模型。该算法改进了自适应遗传算法的选择算子,既提高了模型的收敛速度又避免了早熟问题;同时采用改进的自适应遗传算法对随机森林规模进行修剪,保证了随机森林的分类准确率,并且缩减了随机森林的规模。实验结果表明,应用所提算法建立的烟叶产地分类模型的分类准确率更高,模型更加简单,说明了所提算法的可行性。这为卷烟生产计算机辅助系统提供了较好的烟叶产地识别模型。如何结合实际应用进一步降低算法时间复杂度,提高模型效率是未来研究的重点。