一种融合遗传算法和决策树算法的知识提取方法

摘要

一种融合遗传算法和决策树算法的知识提取方法，涉及基于遥感影像的分类、数据挖掘等领域。本发明包括准备遥感分类结果与分类特征数据；分层随机抽取训练样本集；初始化遗传算法，通过随机产生的基因组合和样本构建决策树，模拟随机森林的随机特征和随机样本特性；对构建的任意一棵决策树筛选感兴趣类别的规则链，并根据规则获取分类结果；将筛选的分类结果与现有分类结果进行比对计算错误率作为评估函数的适应度，记录规则链和对应的错误率；迭代遗传算法至指定次数或满足收敛条件，将一系列规则按错误率从小到大排序，将错误率最小的规则作为显式知识。本发明能有效地将隐式知识转化为可理解的显式知识，具有一定的可重复性和鲁棒性。

说明书

技术领域

本发明涉及一种融合遗传算法和决策树算法的知识提取方法，涉及基于遥感影像的分类、数据挖掘等技术领域。

背景技术

随着Google Earth Engine等云平台的兴起，基于不同数据和算法的遥感分类结果不断增加。在应用这些遥感分类结果方面，现有方法多在这些结果中选取样本，并继续基于具有黑箱属性的算法产生新的分类结果。在这个过程中，分类相关的知识通过样本隐式地传递给新的分类，而人们无法获取、理解和应用这些知识，从而阻碍了认知的进步。

在这些具有黑箱属性的算法中，决策树分类接近于人对事物的简单描述。以遥感分类中的水体识别为例，人们通过归一化水体指数(NDWI)的阈值threshold可分离水体和非水体，这一方式可简化表述为NDWI>threshold，而决策树算法产生的规则形式与此相同。对于阈值，人们的阈值通过大量实践总结而来，决策树的阈值通过算法计算得到。那么，在现有分类结果的基础上构建决策树，可获取其中的知识。

由于决策树的构建使用了贪心搜索策略，无法保证全局最优，即提取的知识存在偏差。通过样本随机和特征随机的方式，以一系列决策树组合而成的随机森林算法具备相对决策树更好的分类表现。但是，聚合了一系列决策树的随机森林算法给出的规则过于繁冗。

发明内容

为了解决从现有分类结果中获取可理解的显式知识的问题，本发明提供一种融合遗传算法和决策树算法的知识提取方法。本发明以遗传算法模拟样本随机和特征随机，并创建一系列决策树以筛选其规则，可以将隐式知识有效转化为人们可以理解的显式知识。

本发明为解决技术问题所采用的技术方案如下：

本发明的一种融合遗传算法和决策树算法的知识提取方法，包括以下步骤：

步骤一、准备现有遥感分类结果数据与遥感分类特征数据，利用Google EarthEngine云平台获取遥感分类结果区域的遥感分类特征影像作为遥感分类特征数据；

步骤二、根据现有遥感分类结果数据以分层随机抽样方式获取训练样本集；

步骤三、初始化遗传算法，取基因数量为遥感分类特征数量；通过遗传算法的迭代产生的不同基因组合模拟随机森林算法的特征随机；

步骤四、创建遗传算法的评估函数，并在此函数中以随机抽样方式在训练样本集中获取样本，所获取的样本比例介于50％到90％之间，用于模拟随机森林算法的样本随机；

步骤五、在遗传算法的评估函数中，以随机特征和随机样本构建决策树，提取该决策树产生的规则；

步骤六、在遗传算法的评估函数中，遍历该决策树产生的规则，并筛选与感兴趣地类相关的规则；参照这些规则对相关遥感分类特征进行分类，以获取随机特征和随机样本下感兴趣地类规则所对应的分类结果；

步骤七、在遗传算法的评估函数中，将基于规则得到的分类结果与现有遥感分类结果进行比较，根据规则链计算得到的分类结果与现有遥感分类结果采用逐像素比较的方式计算错误率，并将该错误率作为评估函数的适应度；

步骤八、重复步骤三至步骤七迭代遗传算法，直至达到指定迭代次数或满足收敛条件时停止迭代，得到一系列规则和对应的错误率；按错误率从小到大对规则进行排序，得到最贴近现有遥感分类结果的规则，将错误率最小的规则作为显式知识。

进一步的，步骤一中，选择2020年吉林向海国家级自然保护区的部分湿地解译结果作为现有遥感分类结果数据；利用Google Earth Engine云平台获取2020年吉林向海国家级自然保护区的5月到10月的Sentinel-1SAR影像、Sentinel-2MSI影像并分别进行中值合成，计算各分类特征并与波段特征合并为遥感分类特征影像，得到遥感分类特征数据。

进一步的，步骤二中，利用R语言raster包的sampleStratified函数，根据现有遥感分类结果数据以分层随机抽样方式进行随机抽样；对2020年吉林向海国家级自然保护区的湿地和非湿地类别按照等比例进行随机采集，得到总样本容量为20000的训练样本集；用rowFromCell函数和colFromCell函数遍历训练样本集，根据位置获取样本对应的特征。

进一步的，步骤三中，利用R语言genalg包rbga.bin函数初始化遗传算法；基因数量设为分类特征数量，种群规模设为200，迭代次数设为100，变异率设为0.01。

进一步的，步骤四中，编写遗传算法的evalFunc函数，利用R语言createDataPartition函数获取75％的样本用于训练决策树，剩余部分直接丢弃，以此模拟样本随机。

进一步的，步骤五中，在evalFunc函数中，利用R语言rpart包的rpart函数构建决策树，得到特征随机和样本随机情况下的一棵决策树。

进一步的，步骤六中，在evalFunc函数中，遍历该决策树的产生规则，选取湿地有关的规则对遥感分类特征数据进行分类，得到分类结果。

进一步的，步骤七中，在evalFunc函数中，将按规则得到的分类结果与现有遥感分类结果进行比较，并计算错误率作为evalFunc函数的适应度。

进一步的，步骤八中，运行rbga.bin函数，不断迭代优化，直至达到指定迭代次数或满足收敛条件时停止迭代，得到一系列规则和对应的错误率，错误率最小的规则即为表征湿地的显式知识。

本发明的有益效果是：

本发明基于现有遥感分类结果与遥感分类特征，以分层随机抽样方式获取训练样本集，利用遗传算法模拟随机森林算法的特征随机和样本随机，通过随机产生的基因组合和随机选取部分样本构建决策树以获取其分类规则；对于构建的任意一棵决策树，筛选感兴趣类别所对应的规则链，并根据规则获取分类结果，将按规则得到的分类结果与现有分类结果之间的错误率作为评估函数的适应度，从而使遗传算法向最优规则方向(即与现有分类结果最贴近的方向)迭代演化。通过对感兴趣类别所对应的规则按照错误率排序，即可得到最优规则(可理解的显式知识)。

本发明能有效地将隐式知识转化为可理解的显式知识，解决从现有分类结果中获取可理解的显式知识的问题以及解决了仅使用决策树算法获取知识所带来的偏差和使用随机森林算法获取的知识过于繁冗而不可用的问题。

本发明一种融合遗传算法和决策树算法的知识提取方法快捷有效，具有可重复性和鲁棒性，对遥感分类、数据挖掘等领域具有极其重要的意义。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施例共同用于解释本发明，并不构成对本发明的限制。在附图中：

图1为2020年吉林向海国家级自然保护区的部分湿地解译结果作为现有遥感分类结果数据。

图2为在特征随机和样本随机情况下构建的一棵决策树。

图3为决策树对应规则得到的分类结果。

图4为遗传算法逐代的最小错误率。

图5为本发明的一种融合遗传算法和决策树算法的知识提取方法提取到的显式知识对应的分类结果和现有的湿地解译数据。

图6为仅使用决策树算法得到的分类结果和现有的湿地解译数据。

具体实施方式

以下结合附图对本发明作进一步详细说明。

本发明的一种融合遗传算法和决策树算法的知识提取方法，主要包括以下步骤：

步骤一、准备现有遥感分类结果数据与遥感分类特征数据，其中，利用GoogleEarth Engine云平台获取遥感分类结果区域的遥感分类特征影像作为遥感分类特征数据。其中，所说的现有遥感分类结果数据在遥感中指的是矢量或栅格形式的解译结果，而在数据挖掘中指的是真值数据集。

具体为：选择2020年吉林向海国家级自然保护区的部分湿地解译结果作为现有遥感分类结果数据(如图1所示)；利用Google Earth Engine云平台获取2020年吉林向海国家级自然保护区的5月到10月的Sentinel-1SAR影像、Sentinel-2MSI影像并分别进行中值合成，计算各分类特征并与波段特征合并为遥感分类特征影像，得到遥感分类特征数据。其中，各分类特征可由用户指定，主要包括波段特征、指数特征、纹理特征等。

步骤二、根据现有遥感分类结果数据以分层随机抽样方式获取训练样本集。其中，所说的现有遥感分类结果数据包含感兴趣类别的分类结果，主要有二分类和多分类等形式。

具体为：利用R语言raster包的sampleStratified函数，根据现有遥感分类结果数据以分层随机抽样方式进行随机抽样；对2020年吉林向海国家级自然保护区的湿地和非湿地类别按照等比例(容量比为1:1)进行随机采集，得到总样本容量为20000的训练样本集；使用rowFromCell函数和colFromCell函数遍历训练样本集，根据位置获取样本对应的特征。

步骤三、初始化遗传算法，取基因数量为遥感分类特征数量；通过遗传算法的迭代产生的不同基因组合即可模拟随机森林算法的特征随机。

具体为：利用R语言genalg包rbga.bin函数初始化遗传算法。基因数量设为分类特征数量，种群规模设为200，迭代次数设为100，变异率设为0.01。其中，通过遗传算法的迭代产生的不同基因组合即可模拟随机森林算法的特征随机。

步骤四、创建遗传算法的评估函数，并在此函数中以随机抽样方式在训练样本集中获取样本，所获取的样本比例介于50％到90％之间，用于模拟随机森林算法的样本随机。

具体为：编写遗传算法的evalFunc函数，其中利用R语言createDataPartition函数获取75％的样本用于训练决策树，剩余部分直接丢弃，以此模拟样本随机。

步骤五、在遗传算法的评估函数中，以随机特征和随机样本构建决策树，提取该决策树产生的规则。

具体为：在evalFunc函数中，利用R语言rpart包的rpart函数构建决策树，得到特征随机和样本随机情况下的一棵决策树。如图2所示，该决策树使用rpart.plot包进行绘制，叶节点1表示湿地、叶节点2表示非湿地。

步骤六、在遗传算法的评估函数中，遍历该决策树产生的规则，并筛选与感兴趣地类相关的规则；参照这些规则对相关遥感分类特征进行分类，以获取随机特征和随机样本下感兴趣地类规则所对应的分类结果。其中，对决策树的规则进行遍历，选择感兴趣类别的叶节点对应的规则链作为潜在知识。

具体为：在evalFunc函数中，遍历该决策树的产生规则，选取湿地有关的规则对遥感分类特征数据进行分类，即规则“VV≥-17&B2/B4≥0.76”和规则“VV≥-17&B2/B4<0.76&(B8-B6)/(B8+B6)<0.046”，VV表示Sentinel-1卫星的VV波段(垂直发射、垂直接收)，B2表示Sentinel-2卫星的波段2(蓝波段)，B4表示Sentinel-2卫星的波段4(红波段)，B6表示Sentinel-2卫星的波段6(红边波段2)，B8表示Sentinel-2卫星的波段8(近红外波段)，得到分类结果(如图3所示)。

步骤七、在遗传算法的评估函数中，将基于规则得到的分类结果与现有遥感分类结果进行比较，根据规则链计算得到的分类结果与现有遥感分类结果采用逐像素比较的方式计算错误率，并将该错误率作为评估函数的适应度。对于数据挖掘，根据规则链计算的分类结果与真值数据集比较计算错误率，并将该错误率作为适应度值。

具体为：在evalFunc函数中，将按规则得到的分类结果与现有遥感分类结果进行比较，并计算错误率作为evalFunc函数的适应度。在多个案例区情况下，取最大错误率作为evalFunc函数的适应度。此处案例区(2020年吉林向海国家级自然保护区)的错误率为32.3％。同时，将规则和对应的错误率保存到文件。

步骤八、迭代遗传算法，即重复步骤三至步骤七，直至达到指定迭代次数或满足收敛条件时停止迭代，得到一系列规则和对应的错误率；按照错误率从小到大对规则进行排序，即可得到最贴近现有遥感分类结果的规则，将错误率最小的规则作为显式知识。

具体为：运行rbga.bin函数，不断迭代优化，直至达到指定迭代次数或满足收敛条件时停止迭代，得到一系列规则和对应的错误率。错误率最小的规则即为表征湿地的显式知识“(B5<1501&VH/VV>＝1.521&(B3-B11)/(B3+B11)>＝-0.457)”，其中，B3表示Sentinel-2卫星的波段3(绿波段)，B5表示Sentinel-2卫星的波段5(红边波段1)，B11表示Sentinel-2卫星的波段11(短波红外波段1)，VH表示Sentinel-1卫星的VH波段(垂直发射、水平接收)，此时错误率为11.8％。迭代过程中逐代最小错误率如图4所示。若仅使用决策树算法的错误率为14.8％，获取的规则为“B11<2637&B8-B4-B3>＝-1145&B8A<2993&B8>＝328&elevation<169”和“B11<2637&B8-B4-B3>＝-1145&B8A>＝2993&(B3-B12)/(B3+B12)>＝-0.216”。其中，elevation表示高程值，B8A表示Sentinel-2卫星的8A波段(红边波段4)，B12表示Sentinel-2卫星的波段12(短波红外波段2)，仅使用决策树得到的分类规则和本发明获取的显式知识对应的分类结果分别如图5和图6所示。若使用随机森林算法，其规则可达上千条，无法满足知识的可理解性。因此，无论从错误率方面，还是所获取知识的可理解性方面，本发明均具有显著优势。

以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，根据本发明的技术方案及其发明构思加以等同替换或改变，都应涵盖在本发明的保护范围之内。