改进利用蚁群规则挖掘算法进行遥感影像分类

吴孔江，曾永年，靳文凭，何丽丽，李 静

中南大学 地球科学与信息物理学院 空间信息技术与可持续发展研究中心，湖南 长沙 410083

1 引 言

遥感信息提取是遥感应用分析的基础，是遥感数据转换为可用地理信息的技术核心［1－2］。因此，遥感影像分类方法的研究一直是遥感科学领域的重要研究内容之一。近年来，众多研究人员在遥感分类方面作了大量的研究，提出了许多遥感分类新方法。但当区域景观较为复杂、空间异质性较高时，现有的遥感影像分类方法往往难以获得较高的分类精度。然而，人工智能方法与技术在处理复杂对象时具有较为明显的优势，目前遥感信息提取中正不断汲取和集成人工智能领域的研究成果，智能化已成为遥感数据处理与信息提取的时代特征［3］。文献［4］提出的蚁群智能算法是智能理论和方法的典型代表之一，它是通过模拟蚂蚁群体觅食寻径行为的抽象而提出的一种基于群体智能的启发式仿生进化算法［5］，已经成功应用于旅行商问题、区位选址、线状目标简化等多个领域［6－8］。基于蚁群算法的规则挖掘最初由文献［9］提出，该算法主要是利用蚁群觅食原理在数据库中搜索最优规则。文献［10—13］等尝试性地将蚁群分类规则挖掘算法引入遥感影像分类。研究表明，该算法能够获得比极大似然法、决策树法等传统分类算法更好的分类效果。这是因为蚁群算法具有以下优势：该算法利用了正反馈原理，在一定程度上可以加快进化过程；智能个体之间不断进行信息交流和传递，具有较强的发现最优解的能力；同时，蚁群规则挖掘算法是一种无参数分类的智能算法，具有较强的鲁棒性，不会由于一个或者某几个智能个体的故障而影响到整个问题的求解。但简单的蚁群算法也存在一些缺陷，如容易陷入局部最优解、收敛慢和计算时间长等问题［9，14］，所挖掘出来的规则往往较多且复杂，不利于分类工作的进行和分类效率的提高。因此，如何在较短的时间内发现具有更强的预测能力，包括更少的规则集以及形式更简单的分类规则是值得研究的问题。

为了探索在短时间内发现更优的分类规则，提高分类精度，本文将变异算子引入蚁群规则挖掘算法中，同时在信息素浓度更新上采取自适应调整策略，试图改进已有的蚁群规则挖掘算法，并与传统规则挖掘算法进行对比分析，验证改进型的蚁群规则挖掘算法在遥感影像分类应用中的优势。以长沙市2006年TM影像为试验数据，分别对其分类精度和效率进行了分析与评价。

2 Ant－miner算法

文献［9］提出的蚁群规则挖掘算法（Ant－miner）将蚂蚁构造规则的过程分为3个阶段［9］。首先，从一条空路径开始重复选择属性节点增加到路径上，直到得到一条完整路径，即构造了一条分类规则；然后，进行规则的剪枝，移去多余不相关的属性节点，避免分类规则对样本的过度拟合；最后，更新所有路径上的信息素浓度，对下一只蚂蚁构造规则施加影响。

在Ant－miner算法的遥感影像分类规则挖掘中，算法的目的是从训练样本中挖掘出分类规则，每个蚂蚁不断寻找分类规则，最终挖掘出一个最优的规则集，其中属性节点对应遥感影像训练样本波段的离散值，类节点对应目标地类。路径为属性节点和类节点的连线，其中每个属性节点最多出现一次且必须有类节点，如图1所示，每条路径即为一条分类规则。规则挖掘中每个规则的形式一般为：if〈conditions〉then〈class〉，规则中的conditions包含一组属性节点（termij，其中i为条件属性数，j为属性i的取值个数）条件集合，一般表示为term1and term2and…，而每一个term就是一个〈attribute operation value〉，如〈波段1＜20.5〉；class定义了样本的预测类，这些样本的预测属性满足规则条件所定义的所有条件［15］。

由于Ant－miner算法在规则剪枝和部分参数设置等方面操作过于简单，在进行较为复杂的工作如遥感分类时，往往难以获得理想的结果。

图1 分类规则对应的路径Fig.1 Route corresponding to classification rule

3 Ant－miner算法改进

3.1 Ant－miner算法存在的问题分析

蚁群算法具有较强的发现最优解能力，且具有较好的鲁棒性。但Ant－miner算法也有一些系统本身所具有的不足，主要表现如下［14，16－17］：

（1）蚁群系统的一个比较大的风险就是容易收敛于局部最优解。这是因为，在蚁群系统中，蚂蚁更多地采用自然的方式来执行信息素的更新，即每个蚂蚁一旦获得某个解，不管质量如何，都会依据该解来进行全局信息素更新。这样会引起在搜索初期蚂蚁的运动是随机的，获得的解并不一定是最优解，这会使得一些较差路径上信息素增强，对后续蚂蚁进行错误引导，从而导致规则的质量不高。

（2）Ant－miner算法往往需要较长的搜索时间，主要原因是在进化的初始阶段，各个路径上的信息素差别很小，同时在信息素浓度更新时，信息素挥发系数一般采用相同的固定值，虽然对全局信息素进行了更新，但对下只蚂蚁选择路径时所产生的影响效果并不明显，蚂蚁的运动很随机，特别在遥感分类试验中，波段数据量大且土地覆盖类型复杂，更难在短时间内发现最优路径。只有经过较长一段时间，才能使得较好的路径上信息素浓度高于其他路径，随着这一过程的进行，路径上的信息量差别越来越明显，从而得到最优路径。

（3）Ant－miner算法最初只考虑了可用规则集的预测准确度，没有考虑规则的精简性，所挖掘出来的规则往往较多且复杂。采用逐个去掉每个属性节点的规则剪枝策略，使得到的最终规则不一定是最精简的最优解，这就需要更多更复杂的规则来提升规则集的预测准确度。

3.2 蚁群规则挖掘算法的改进

本文在Ant－miner算法的基础上对信息素浓度更新函数进行优化，对挥发系数进行自适应调整，对剪枝后的规则执行变异，以期在短时间内挖掘出更优规则集。

3.2.1 信息素浓度更新的改进

式中，τij为条件属性节点的信息素浓度，当第一只蚂蚁开始构造路径时，所有属性节点的信息素浓度被初始化为相同的值；ρ为信息素的挥发系数；Q为分类规则的有效性，其衡量公式为

式中，TP表示满足规则条件，所属于的类别与规则预测类别相同的记录数量；FN表示不满足规则条件，所属于的类别与规则预测类别相同的记录数量；TN表示不满足规则条件，所属于的类别与规则预测类别不同的记录数量；FP表示满足规则条件，所属于的类别与规则预测类别不同的记录数量。

其次，对原有算法中的信息素挥发系数ρ进行改进。一般来讲，ρ（0＜ρ＜1）过小会使信息素在少数路径上聚集过多，造成后来的蚂蚁绝大部分选择局部最优路线，降低算法全局最优解的搜索能力；ρ过大又会使各条路径上的信息素难以在较短的时间内区别开来，导致算法收敛速度缓慢，从而延长计算时间。因此，ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度。在Ant－miner算法中，ρ设为一个简单的固定值，使得蚂蚁搜索时间较长且不易得到最优规则，从而影响分类结果的精度和效率。本文对ρ进行自适应调整，取ρ的初始值ρ（0）＝0，当算法求得的最优解在多次循环内没有明显的改进时，采取调整参数策略。在本文遥感分类试验中，经过对样本数据的分析并反复试验，得到最优系数值为0.95，如下式

式中，ρmin为最小值。

对ρ采取自适应调整，一方面使得蚂蚁在走过的路径上留下的信息素能够较为平稳缓和地增加，避免增加的太快对后续蚂蚁造成影响而陷入局部最优解；另一方面，当算法多次循环无明显改进时，能够加大蚂蚁走过路径上信息量的挥发，启发后续蚂蚁寻找其他路径，加大搜索范围。这样既可以保留上次搜索得到的有效信息，在较好区域可以进行更精细的搜索，加快算法收敛，又可以保证大范围搜索的有效性。

3.2.2 变异算子的引进

为了加快进化过程，缩短计算时间，变异策略被引入到蚁群算法求解旅行商、图像处理等问题当中，并取得了较好的效果［16－20］，但在遥感分类方面的应用则未见报道。因此，本文将变异算子引入蚁群算法中，以提高某个蚂蚁搜索到的规则的质量，并缩短计算时间。具体方法为，对于剪枝后的规则，执行单点变异，即随机选择某个属性节点，用这个属性节点对应属性的另一个属性节点取代原有属性节点从而构成新的规则，如果新规则的有效性大于原有规则，则进行变异，否则不进行变异。这个操作简单，且只需很短的时间，却能扩大搜索范围，提高修剪后的规则质量，从而可以加快算法收敛速度。变异算子的形式化描述如下。

3.3 改进蚁群规则挖掘算法过程

改进蚁群规则挖掘算法的过程如图2所示。在迭代运算过程中，每只蚂蚁都构造出一条规则，经过规则修剪后执行变异，得到有效性好而且形式简单的规则，这些规则当中有效性最好的由于其信息素浓度逐渐增强而得以保留，并添加到最优规则集中，其他有效性较差的规则被丢弃。训练样本集则进行相应修改，符合最优规则条件的样本将从训练样本集中移除，这实质上是一种序列覆盖算法，这样得到新的样本集，开始下一次迭代。在下一次迭代运算前，更新信息素浓度，此时所有属性节点的信息素浓度将被重新初始化。当多次循环最优解无明显改进时，信息素挥发系数按照公式（4）进行自适应调整。直到剩余的训练样本数小于预定的样本数M。

图2 改进蚁群规则挖掘算法原理Fig.2 Principle of rule mining based on improved ant colony algorithm

4 遥感影像分类试验

基于蚁群算法的遥感分类主要由3部分组成：分类规则挖掘、土地覆盖分类和分类精度评价。分类规则主要通过蚁群算法从训练数据中挖掘出来，本文中蚁群规则挖掘算法是在Visual Studio 2008环境中用C＃语言编程实现的。土地覆盖分类则是根据蚁群算法挖掘出来的分类规则对遥感影像分类。分类精度评价是用验证样本数据对分类结果进行检验评价。由于蚁群规则挖掘算法只能处理离散化的数据，尽管遥感数据各波段的值为0～255的离散值，但波段的区间过多，会影响蚁群算法的效率和规则的质量，因此，在建立规则之前需要将训练数据集进行离散化，即将各波段数据划分为有限的区间。本文采用基于信息熵的离散化方法离散遥感影像波段值［21］。

4.1 试验区与数据

试验中采用的数据是2006年11月1日获取的长沙市地区的TM卫星数据，经过影像拼接、几何校正、辐射校正和影像裁剪等预处理后，选取的研究范围为长沙城区，分辨率为30m，选择的波段为1～5波段和7波段，共6个波段数据。图3为本研究区域5、4、3波段所合成的假彩色影像图。以研究区域2006年1∶50 000的土地利用现状图为参考，结合同期IKONOS影像数据，通过目视解译获取不同土地利用类型，以此作为本文遥感影像的训练区选取及分类精度评价的先验数据。辅助参考数据为该研究区域数字化地形图等。

训练样本的选择直接影响蚁群算法挖掘的规则质量，进而影响分类结果。通过野外调查和对照土地利用现状数据，采用分层随机采样的方法来获取训练样本和验证数据集，如表1所示。确定的土地利用覆盖类型分别为：水体、建设用地、林地、裸地和农业用地，训练数据集的样本数为1010，验证数据集的样本数为1204。

表1 训练样本和验证样本Tab.1 The training data and test data

图3 长沙市区TM影像5、4、3假彩色合成图Fig.3 TM image（5、4、3）false color composite graph of Changsha city

4.2 分类规则挖掘与试验结果

在运用蚁群算法挖掘遥感影像分类规则时，离散化后的各波段值作为蚂蚁路径的属性节点，分类类别作为蚂蚁路径的类节点，每条路径对应一条分类规则。本试验利用改进的蚁群规则挖掘算法共获得了11条分类规则，利用Ant－miner算法共获得了23条分类规则，表2列出了部分分类规则，其中B1、B2、…、B5和B7分别对应波段1、波段2、…、波段5和波段7。根据所获得的分类规则，对试验影像进行分类，分类结果见图4（a）和图4（b）。同时，用相同的训练样本数据对影像用决策树法和极大似然方法进行了分类，分类结果见图4（c）和图4（d）。

表2 改进蚁群算法和Ant－miner算法挖掘的部分分类规则Tab.2 Part of classification rules from improved ant colony algorithm and Ant－miner algorithm

图4 长沙市区TM影像土地覆盖分类结果图Fig.4 Land cover classification results of Changsha city TM image

4.3 分类精度评价

为了对比这4种方法的精度，用验证样本数据对改进蚁群算法、Ant－miner算法、决策树法和极大似然方法分别进行了精度评价，得到混淆矩阵如表3、表4、表5、表6所示。对比表3、表4和表6，可以看出基于改进蚁群算法的分类结果比极大似然分类法的总体精度提高了7.31%，Kappa系数提高了0.093 5；基于Ant－miner算法的分类结果比极大似然分类法的总体精度提高5.15%，Kappa系数提高了0.065 7，说明蚁群智能分类方法能较为真实地反映实际的土地利用覆盖类型。对比表3和表4，可以看出基于改进蚁群算法的分类结果比Ant－miner算法总体精度提高了2.16%，Kappa系数提高了0.027 8，特别对林地和裸地分类精度提高较多，说明本文所提出的改进策略是可行的、有效的。对比表4、表5和表6，可以看出基于改进蚁群算法的分类结果比决策树法总体精度提高了4.82%，Kappa系数提高了0.062；基于Ant－miner算法的分类结果比决策树法总体精度提高了2.66%，Kappa系数提高了0.034 2，说明蚁群规则挖掘算法用于分类较传统的决策树算法也有一定优势。

表3 长沙市区改进蚁群算法遥感土地覆盖分类精度评价Tab.3 Accuracy assessment on improved ant colony algorithm land cover classification of Changsha city

表4 长沙市区Ant－miner算法遥感土地覆盖分类精度评价Tab.4 Accuracy assessment on Ant－miner algorithm land cover classification of Changsha city

表5 长沙市区决策树法遥感土地覆盖分类精度评价Tab.5 Accuracy assessment on Decision tree algorithm land cover classification of Changsha city

表6 长沙市区极大似然法遥感土地覆盖分类精度评价Tab.6 Accuracy assessment on ML algorithm land cover classification of Changsha city

为了进一步体现基于蚁群算法的遥感分类的优势，以及本文对算法改进的可靠性。对决策树法、Ant－miner算法和改进蚁群算法所挖掘出来的规则进行对比，3种方法的所有规则个数和平均term的个数如表7所示。对比表7可以看出，改进蚁群算法所挖掘出来的规则数目大大减少，同时单个规则也较为简洁。与决策树和Antminer相比，本文算法不仅能发现预测能力更强的规则集，而且在形式上也更简单，包括更少规则的规则集和更短的规则。同时，表8对比了改进蚁群算法和Ant－miner算法的计算时间，改进蚁群算法比Ant－miner算法的计算时间缩短5.41s，计算效率相对提高43%，试验结果充分说明改进蚁群算法能够有效的节省计算时间，大大提高了分类效率。

表7 3种算法挖掘的规则个数和平均规则数Tab.7 The mining rules number and the average number of rules by three of the algorithm

表8 改进蚁群算法和Ant－miner算法的计算时间Tab.8 The calculation time of improved ant－miner and ant－miner s

5 结 论

（1）蚁群智能算法具有较强的鲁棒性、自适应性、非线性和正反馈机制，能够为遥感数据的智能化处理提供一种有效的方法和途径，因此在进行复杂的遥感影像分类时具有较为明显的优势。但简单蚁群算法也存在容易陷入局部最优解、收敛慢和计算时间长等问题，为了解决这些问题，本文在Ant－miner算法基础上改进信息素浓度更新策略，引进变异算子，提出了基于改进蚁群规则挖掘算法，相对于Ant－miner算法和决策树方法而言，改进蚁群规则挖掘算法能够发现更好的分类规则，包括更强的预测能力，有更短的规则和更少的规则集。

（2）将改进蚁群规则挖掘算法应用于长沙市城区的遥感影像分类，取得了较为理想的分类结果。并与Ant－miner算法、决策树法和极大似然法进行了对比研究，其中改进蚁群算法总体精度为90.78%，Kappa系数为0.882 1；Ant－miner算法总体精度为88.62%，Kappa系数为0.854 3；决策树法总体精度为85.96%，Kappa系数为0.820 1；极大似然法总体精度为83.47%，Kappa系数为0.788 6。这表明改进蚁群算法比Ant－miner算法、决策树法和极大似然法的分类精度更高。同时，试验结果还表明，改进蚁群算法比Ant－miner算法的计算时间缩短5.41s，计算效率相对提高43%，充分说明改进蚁群算法能够有效地节省计算时间，提高分类效率。

（3）蚁群算法为遥感数据分类提供了一种新的方法，但蚁群算法用于遥感数据处理还处于起步阶段，对该算法进行进一步的优化和完善将是以后研究中的重点。目前该算法只能处理离散化的数据，无需离散化而直接应用蚁群算法进行计算是下一步的研究目标。

［1］ WILKINSOMG G.Results and Implications of a Study of Fifteen Years of Satellite Image Classification Experiments［J］.IEEE Transaction on Geoscience and Remote Sensing，2005，43（3）：433－440.

［2］ ZHENG Zhong，ZENG Yongnian，LIU Huimin，et al.The Errors Analysis of Combined Classifier Based on Parallel Structure［J］.Remote Sensing Technology and Application，2011，26（3）：340－347.（郑忠，曾永年，刘慧敏，等.并联结构组合分类器的误差分析［J］.遥感技术与应用，2011，26（3）：340－347.）

［3］ MA Jianwen，LI Qiqing，HASIBAGAN，et al.Remote Sensing Data Processing Method and Program Design［M］.Beijing：Science Press，2005：1－20.（马建文，李启青，哈斯巴干，等.遥感数据智能处理方法与程序设计［M］.北京：科学出版社，2005：1－20.）

［4］ COLOMI A，DORIGO M，MANIEZZO V.Distributed Optimization by Ant Colonies［C］∥Proceedings of the 1st European Conference on Artificial Life.Paris：Elsevier Publishing，1991：134－142.

［5］ LU D，WENG Q.A Survey of Image Classification Methods and Techniques for Improving Classification Performances［J］.International Journal of Remote Sensing，2007，28（5）：824－849.

［6］ DORIGO M，GAMBARDELLA L M.Ant Colony System：A Cooperative Learning Approach to the Traveling Salesman Problem［J］.IEEE Transactions on Evolutionary Computation，1997，1（1）：53－66.

［7］ ZHAO Yuan，ZHANG Xinchang，KANG Tingjun.A Parallel Ant Colony Optimization Algorithm for Site Location［J］.Acta Geodaetica et Cartographica Sinica，2010，39（3）：322－327.（赵元，张新长，康停军.并行蚁群算法及其在区位选址中的应用［J］.测绘学报，2010，39（3）：322－327.）

［8］ ZHENG Chunyan，GUO Qingsheng，HU Huake.The Simplification Model of Linear Objects Based on Ant Colony Optimization Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2011，40（5）：635－638.（郑春燕，郭庆胜，胡华科.基于蚁群优化算法的线状目标简化模型［J］.测绘学报，2011，40（5）：635－638.）

［9］ PARPINELL R S，LOPES H S，FREITAS A A.Data Mining with an Ant Colony Optimization Algorithm［J］.IEEE Transaction on Evolutionary Computation，2002，6（4）：321－332.

［10］ WANG Shugen，YANG Yun，LIN Ying，et al.Automatic Classification of Remotely Sensed Images Based on Artificial Ant Colony Algorithm［J］.Computer Engineering and Applications，2005，41（29）：77－80.（王树根，杨耘，林颖，等.基于人工蚁群优化算法的遥感图像自动分类［J］.计算机工程与应用，2005，41（29）：77－80.）

［11］ YE Zhiwei，ZHENG Zhaobao，WAN Youchuan，et al.A Novel Approach for Feature Selection Based on Ant Colony Optimization Algorithm［J］.Geomatics and Information of Wuhan University，2007，32（12）：1127－1130.（叶志伟，郑肇葆，万幼川，等.基于蚁群优化的特征选择新方法［J］.武汉大学学报：信息科学版，2007，32（12）：1127－1130.）

［12］ LIU Xiaoping，LI Xia，HE Jinqiang，et al.Classification of Remote Sensing Images Based on Ant Colony Optimization［J］.Journal of Remote Sensing，2008，12（2）：253－262.（刘小平，黎夏，何晋强，等.基于蚁群智能的遥感影像分类新方法［J］.遥感学报，2008，12（2）：253－262.）

［13］ DAI Qin，LIU Jianbo.Research on Remote Sensing Image Classification Using Ant Colony Optimization Based Classification Rule Mining Algorithm ［J］.Computer Engineering and Application，2008，44（15）：12－14.（戴芹，刘建波.基于蚁群优化分类规则挖掘的遥感图像分类研究［J］.计算机工程与应用，2008，44（15）：12－14.）

［14］ DORIGO M，MANIEZZO V，COLORNI A.Ant System：An Autocatalytic Optimizing Process［R］.Milan：Politecnico di Milano，1991.

［15］ ZHANG Weijiao，LIU Chunhuang，YIN Xiaofeng.Application Research on Data Mining Using Ant Colony Algorithm［J］.Computer Engineering and Applications，2004，40（28）：171－173.（张惟皎，刘春煌，尹晓峰.蚁群算法在数据挖掘中的应用研究［J］.计算机工程与应用，2004，40（28）：171－173.）

［16］ LI Shiyong.Ant Conoly Algorithm and Application［M］.Harbin：Harbin Institute of Technology Press，2004.（李士勇.蚁群算法及其应用［M］.哈尔滨：哈尔滨工业大学出版社，2004.）

［17］ WU Zhenglong，Wang Rujing，Teng Mingui，et al.Mining Classification Rule Based on Colony Algorithm ［J］.Computer Engineering and Application，2004，40（2）：30－33.（吴正龙，王儒敬，滕明贵，等.基于蚁群算法的分类规则挖掘算法［J］.计算机工程与应用，2004，40（20）：30－33.）

［18］ MICHALEWICCZ Z.Genetic Algorithms＋Data Structures＝Evolution Programs［M］.2nd ed.New York：Springer Verlag，1994.

［19］ WU Qinghong，ZHANG Jihui，XU Xinhe.An Ant Colony Algotithm with Mutation Features［J］.Journal of Computer Research and Development，1999，36（10）：1240－1245.（吴庆洪，张记会，徐心和.具有变异特征的蚁群算 法 ［J］.计 算 机 研 究 与 发 展，1999，36（10）：1240－1245.）

［20］ LIU Shuo，WU Honggan，WEN Qingke.Segmentation of Remote Sensing Image Based on a Combination of Genetic Algorithm and Ant Colony Algorithm［J］.Geomatics and Information of Wuhan University，2009，34（6）：679－683.（刘朔，武红敢，温庆可.基于遗传和蚁群组合算法优化的遥感图像分割［J］.武汉大学学报：信息科学版，2009，34（6）：679－683.）

［21］ XIE Hong，CHENG Haozhong，NIU Dongxiao.Discretization of Continuous Attributes in Rough Set Theory Based on Information Entropy［J］.Chinese Journal of Computers，2005，28（9）：1570－1574.（谢宏，程浩忠，牛东晓.基于信息熵的粗糙集连续属性离散化算法［J］.计算机学报，2005，28（9）：1570－1574.）