居民地是地形图的重要要素之一^[1]，其数量和分布有助于判断地区的自然条件、土地利用、政治经济和文化发展等状况。而面状居民地又是中小比例尺地形图上居民地的一种重要的表达形式^[2]。随着比例尺的减小，受地图表达的限制，需要对居民地进行选取操作。可以说，居民地选取质量的好坏直接影响着地图的科学性和使用价值^[3]。

目前居民地选取方法主要分为两类：一是纯粹的数学和模型算法，如基于遗传算法的选取方法^[4]、基于Circle原理的选取方法^[5]、基于Kohonen的选取方法^[6]、基于Voronoi图的选取方法^[7]、基于属性权重模型的选取方法^[8-9]等；二是智能化的方法，即基于知识的方法，如专家系统^[10]、基于规则推理^[11]等。居民地的选取主观性较强，选取的思维过程是模糊的、不确定的，难以形式化表达为精确的自动选取模型^[12]，尤其是对面状居民地的选取。因此，第1类建立精确模型的方法对于单一分布的点群选取效果较好，但对于环境稍复杂的面状居民地选取适用性较弱。从理论上讲要解决居民地自动选取的问题，应该从智能化方法上寻找突破口。第2类方法中，传统的制图综合专家系统和基于规则推理的方法，受到知识获取瓶颈的制约，一直难以有效地应用^[13-14]。但也有一些实质性成果面世，文献[15—16]提出了基于案例类比推理和基于决策树的道路网智能选取方法，计算机通过对专家选取案例的学习进行相似道路网的自动选取，该方法某种程度上突破了知识获取与形式化表达的瓶颈。

上述研究极大地推动了居民地选取的发展，但进一步研究发现，居民地选取方法还存在以下几个问题：①基于算法和模型的方法暂时无法形式化反映专家在居民地选取过程中复杂的思维过程；②文献[15]中基于案例类比的方法中案例匹配机制研究得还不够深入，且在灵活性等方面还有较大提升空间；③文献[16]中方法在案例较少时难以构建决策树，易受噪声影响。

针对以上不足，本文沿用案例类比的思想，结合KNN算法进行居民地的案例类比选取。首先把制图专家对居民地交互选取结果作为案例对象，采用三元法对其进行描述、属性赋值以及归一化处理后构建源案例库；然后采用逐步消元法对居民地最佳属性组合进行选择判定，并训练数据确定KNN算法的最佳K值；最后，基于案例推理方法，结合KNN算法，将新案例与源案例库检索匹配，得出决策结果，进而指导居民地的自动选取，达到学习专家综合知识并模仿专家综合结果的目的，同时在一定程度上使得选取结果更加符合人类的认知习惯，增强地图的可读性。

1 案例推理和KNN算法原理 1.1 案例推理基本原理

长期以来，制图专家知识的表达一直是制约制图综合发展的瓶颈^[17]。这是因为专家在进行交互式综合时，除了有显性的制图综合规则外，还隐性包含了制图专家自身的制图经验，难以形式化表达。基于案例推理CBR(case-based reasoning)符合制图者的心理认知过程，如图 1所示。具体是指在进行问题求解时，使用以前求解类似问题的经验和获取的知识来推理，并且将新获取的知识形成新的案例加入到案例库中去，从而通过不断充实案例库来丰富系统的经验^[18]。

CBR基于以下两条原则：①相似的问题有相似的解决方法；②同类的问题会再次发生^[17]。这与制图综合的情况相符合。与基于模型推理和基于规则推理相比，案例推理降低了知识的获取难度，简化了问题的求解途径，提高了推理的制图效率，不需要得出像规则那样准确和抽象的知识，而是直接使用隐含的难以提取规则的专家案例，且以获取新案例的方式实现自学习，系统维护简单。

1.2 KNN算法基本思想

KNN是基于统计模式的有监督学习的类比算法^[19]，其核心思想是：首先对整个案例库检索，逐个进行计算，算出待求解的目标案例与案例库中的源案例之间的相似度，然后选择K个相似度高的源案例，依次统计出这K个案例对象的所属类别，找出包含最多个数的类别作为案例分类决策的结果^[20]。

KNN在居民地案例推理中具体定义如下：

定义1：专家选取居民地案例集合X：X={X₁, X₂, …, X_n}，其中X_i是集合X中第i个居民地案例，n为居民地案例的总个数。

定义2：待决策居民地案例集合Y：Y={Y₁, Y₂, …, Y_n}，其中Y_i是集合Y中第i个居民地案例，n为居民地案例的总个数。

定义3：专家选取居民地案例X_i={a_i1, a_i2, …a_ir, …, a_im}, 其中a_ir为专家选取居民地案例X_i的第r个属性，m为每个案例的属性总个数。

定义4：待决策居民地案例Y_j={b_j1, b_j2, …b_ir, …, b_jm}, 其中b_jr为待决策案例Y_i的第r个属性，m为每个案例的属性个数。

定义5：待决策居民地案例Y_j与专家选取居民地案例X_i之间的相似值的计算采用欧氏距离表达，即公式

定义6：待决策居民地案例Y_j的K个最近邻对象集合

式中，MAX_k表示待决策居民地案例Y_j与所有专家选取居民地案例相似度按从小到大排序的第K个距离值。

KNN算法直观，易于实现，且在案例较少时也能做出决策。与泛化案例构建案例库的简单类比推理和采用决策树提取隐含规则方法相比，KNN算法不需要产生额外的数据来描述规则，它的规则就是案例本身。它并不严格要求数据的一致性，在一定程度上允许存在噪声。噪声数据是指制图专家由于疲劳、注意力不集中等原因导致的居民地选取的错误结果。这些噪声数据加入案例库后，若采用简单类比推理和归纳推理等方法的学习机制会直接影响案例推理的效果。KNN根据待分类样本的K个近邻样本来预测待分类案例的类别，在一定程度上能有效避免噪声的影响，从而使案例分类决策更准确。

2 居民地案例的设计与构建 2.1 居民地案例的描述

在进行基于案例推理时，首先需要将专家选取结果转化为专家选取案例。本文采用三元表示法，由制图综合案例对象(Object-O)、特征(Feature-F)以及综合标记(Label-L)组成的一条记录表示制图综合案例。其形式化的表示为

式中，案例对象(O)是指具体操作的居民地对象，如FID_068、FID_066；特征(F)也称为描述性项或属性，包含居民地自身信息的描述以及通过空间分析获得的居民地所处的制图环境的描述，现总结6个居民地属性指标^[21-22]，如居民地行政等级(grade)、居民地面积(area)、邻近道路等级(neighbor roads grade，NRG)、最近居民地距离(nearest habitation distance，NHD)、邻近居民地等级差(nearest habitation grade difference，NHG)、居民地密度(density)等来反映居民地自身属性，居民地与居民地之间的关系以及居民地与其他要素之间的关系；综合标记(L)是指居民地所处的综合操作，例如选取(S)、删除(D)，合并(H)等，其中删除(D)在案例显示时应表示为面要素降维到点要素，为方便表示，文中将降维标记为删除，如表 1所示。

采用三元描述法，对专家选取居民地数据进行统一，确保在进行案例匹配时新的目标案例能够在源案例库中匹配到综合结果，方便数据的检索、存储和管理。

2.2 居民地属性的赋值、归一化处理

不同变量的量纲不同，为了消除量纲的影响，便于KNN相似度的计算，需对居民地属性赋值并进行归一化处理。居民地属性类型主要包括两种：数值型和字符型。

首先考虑字符型属性的处理，其中为方便计算将居民地行政等级数值化为4个等级，从1到4分别对应市(一级)、区(二级)、镇(三级)、村庄(四级)。居民地行政等级赋值并进行归一化处理，如表 2所示：

对于数值型属性，采用min-max标准化(min-max normalization)使结果值映射到[0-1]之间。转换函数如下

式中，max为样本属性数据的最大值；min为样本属性数据的最小值。

对area、NRG、NRD属性特征进行归一化处理后结果如表 3所示：

2.3 居民地属性的筛选

居民地选取本身顾及属性较多，属性选择的判定对于选取结果的好坏起到决定性作用，而属性的选择与数据类型、制图专家的主观判断密切相关。本文采用逐步消元法解决居民地属性选取多少和选取哪些的问题，并用十折交叉验证的方法得出分类正确百分比。十折交叉验证是将数据集分成10份，轮流将其中9份作为训练数据，1份作为测试数据，进行试验，得出相应的正确率，10次结果正确率的平均值最终试验结果^[23]。逐步消元法的具体步骤是:首先从训练数据完整的属性集中移除单个属性，余下属性形成一个属性子集，对每个属性子集进行十折交叉验证，通过对比分类正确率确定最佳对象的属性子集，按照这种方式重复，即在逐步减少属性数量的同时进行十折交叉验证，记录分类正确的百分比，结果如表 4所示。

从试验结果可以看出，当属性个数为4且属性组成为area、grade、NRG、density时分类正确率最高。由此确定参与决策的属性，并依此整理专家选取结果数据，构建居民地源案例库。

3 基于KNN算法的居民地案例匹配

基于KNN算法实现案例匹配的一般步骤为：

(1) 训练数据，确定最佳K值。

(2) 根据距离函数计算待分类居民地x与源案例库每个训练样本的距离，选择与案例样本距离最小的K个样本作为x的K个最近邻。

(3) 根据K个最近邻判断出x所属类别。

判断的依据是，设选取(S)个数为m，删除(D)个数为n，合并(H)个数为p，K=m+n+p，其中函数max(a, b)为a、b二者最大值：①若m>max(n, p)，则待处理居民地综合操作结果为选取(S)；②若n>max(m, p)，则待处理居民地综合操作结果为删除(D)；③若p>max(m, n)，则待处理居民地综合操作结果为合并(H)；④若m=n=p，则属于模糊结果，交由专家处理，进行人工交互判断，问题解决后与①、②、③决策案例一起存入源案例库作为更新案例，实现案例的自学习。

3.1 K值的选择

KNN算法中K值决定了分类模型的好坏，K值太小会导致分类精度下降，K值过大会导致误差过大从而影响分类的效率^[24]。本文采用控制变量法和十折交叉验证训练数据样本，通过查全率(recall)、查准率(precision)、F₁测度值和分类正确率4个指标来判断最佳K的取值^[23]。评价指标值越大，说明此时的K近邻模型的分类性能越好，案例匹配的精度越高。以选取操作为例公式如下

查全率度量分类器正确预测正例的比例，查全率越高，分类的误判率越低；查准率确定分类模型为正例的部分记录中实际为正例的记录所占的比例；F₁测度值是查全率和查准率的调和均值，即在认为二者具有同等重要作用的前提下，将二者结合为一个指标。现将训练数据(206个案例)中不同K值试验结果如表 5所示:

由推理结果可以看出，当训练样本个数为206，K=4时，采用KNN算法进行案例分类正确率最高。

3.2 最佳K值的确定

文献[25]研究发现最佳K值一定程度上与案例的规模存在关联，即K取训练样本的2%时可以取得的分类效果最好。为了进一步探寻本文居民地选取案例类比推理最佳K值的选择与案例库规模的关系，本文采取不同的K值对其应用效果进行了大量的测试，并采用不同的案例个数进行验证，依据3.1节提供的方法，依次确定每组训练数据的最佳K值，试验结果如表 6所示。

分析试验结果发现，针对当前居民地数据，最佳K值与案例样本的总数确实存在一定的相关关系，验证了文献[24]的结论，即K取训练样本的2%时可以取得的分类效果最好。

4 试验与分析 4.1 试验流程

因大比例尺地图中居民地综合面临的算子较多，如选取、合并、典型化、融合、位移等，本文暂不予以考虑。本文主要针对中小比例尺面状居民地数据，采用基于KNN算法和案例推理进行居民地选取，其基本步骤与流程如图 2所示。

图 2所示技术路线图中主要包括以下5个步骤：

(1) 专家案例描述。对制图专家的居民地选取结果通过三元法进行结构化描述，构建专家选取居民地案例。

(2) 数值转换。将居民地案例输入，对案例进行属性赋值、归一化等数值转换处理。

(3) 案例属性筛选。采用逐步消元法，确定参与决策的最佳属性组合。构建格式统一的源案例库。

(4) 案例匹配。训练数据，确定最佳K值，启动类比推理和KNN检索机制，将每个待处理居民地案例与源案例库中的案例进行匹配，根据匹配结果得出解决方案，并依据解决方案指导居民地的选取。

(5) 人工处理。若KNN检索中判断案例类别个数相等，此时机器无法做出判决，需进行人工处理。将人工处理后的居民地数据源与成功匹配的居民地数据一起作为新案例加入到源案例库中。

4.2 试验与分析

为了验证本文提出的居民地智能选取方法的有效性和优势性，利用居民地数据进行了相关试验。依据流程设计试验如下：以综合的比例尺为1:10万至1:20万，北京及其周边602个专家交互选取居民地作为源案例库，如图 3所示。

将制图环境相似的涿州市附近150个居民地作为试验案例，部分如图 4所示。数据预处理完成后，进行试验案例与源案例库的KNN检索匹配，依据3.2节的结论可知，此时最佳K值为12。图 5为KNN试验自动综合的结果，专家交互选取结果如图 6所示。图中居民地选取的对象标记为红色，删除居民地对象标记为灰白色，蓝色为合并居民地对象。从图中可以看出，图 5与图 6对应居民地颜色大部分一致，即综合结果总体相似度很高，只存在少量不一致的情况。

为检验KNN算法综合结果的科学性和准确性，对此方法结果与图 6专家交互选取结果进行详细对比与分析。为方便比较，仅显示居民地要素，如图 7、图 8所示，相关数据统计见表 7。

分析试验对比结果可知，与专家交互选取结果相比，采用基于KNN的案例推理方法综合后的居民地基本上保持了其分布特征，取得了较好的综合效果。在复杂的制图环境下，决策正确率达89.33%，且忠于专家经验，很大程度上还原了专家的制图水平。仅存在极少量与专家选取不一致的综合结果，部分如图 7、图 8箭头所示，进一步分析发现该部分居民地处在专家判断标准的边缘，存在不可避免的模糊性，导致错误的产生。

进一步研究发现，基于案例推理的居民地选取效果高度依赖源案例库数据的质量。制图专家对居民地交互选取过程中，由于疲劳、注意力不集中、视觉误差、操作失误等原因，会造成居民地选取的操作结果出现错误。这些被称作噪声的错误案例加入到源案例库后会直接影响学习效果，最终影响指导解决新任务的质量。本文提出的基于KNN的案例推理方法与依据案例归纳出规则的基于决策树方法相比，抗噪能力更强，在一定程度上能够允许噪声的存在，能有效弥补目前案例推理模型在制图综合应用中抗噪能力弱的缺点。

传统的决策树方法中每一个根节点到叶子节点的分枝都是一条由案例演绎归纳得到的规则，如图 9(a)所示，为无噪声专家居民地综合简单决策树示意图。若加入错误的案例即噪声，如：将行政等级grade为3，面积area为658 956.7 m²的居民地案例由选取错操作为合并，则会归纳出错误的规则，如图 9(b)灰色标志决策所示。而案例推理模型是已解决的新问题不断加入到案例库中，这种“滚雪球”式的发展会指导更多的案例进而造成更多错误决策。

而由1.2节KNN算法基本思想可知，KNN算法是K个案例参与决策待处理案例结果，故决策时个别噪声的存在对判断结果影响甚微，即基于KNN的案例推理模型在一定程度上受噪声案例影响较小。为证明本文算法在抗噪方面的优势性，设计试验在源案例库中分别添加不同比例随机噪声进行对比试验，二者决策正确率具体统计结果如表 8所示，对比趋势图如图 10所示。

分析试验结果可知，KNN算法更稳定。随着噪声数据的加入，决策树方法正确率受影响较大，而使用KNN算法的决策正确率相对稳定，可见KNN算法在随机噪声干扰下鲁棒性更强，有效弥补了目前案例推理模型在制图综合应用中抗噪能力弱的缺点。

5 结论

本文提出一种基于KNN案例推理的居民地选取方法，该方法直接以制图专家对居民地交互选取结果作为案例对象，利用案例类比推理和KNN算法完成了居民地选取从已有专家案例到未知结果决策的转化，达到了学习专家综合知识并模仿专家综合结果的目的。本文方法决策正确率高，受噪声影响相对较小，有效弥补了目前案例推理模型在制图综合应用中抗噪能力弱的缺点，且不需要提取规则；同时能有效利用专家经验，一定程度上降低制图综合的难度，为智能化自动综合提供了新思路。

本文案例之间相似度是根据案例的所有属性计算的，KNN计算时默认每个属性的作用都相同，即被赋予相同权重。如何进一步优化KNN算法，对案例属性合理赋权值，使得案例推理对居民地选取结果准确率更高，是本文进一步的研究方向。