基于DBSCAN算法的机场体系划分方法研究

李 赞，王朝霞，隋 昊

(中国人民解放军陆军勤务学院 军事物流系， 重庆 401331)

中国是全世界机场数目第一的国家。截至2017年底，中国共有228座机场建成通航，其中有28家机场旅客吞吐量已突破千万人次。机场规模的快速扩大，使得机场之间的联系也变得愈发关键。

当前，中国已初步形成多个区域性机场体系，典型的有以北京首都机场为主体的北方(华北和东北)机场体系，以上海浦东机场为主体的华东机场体系，以广州白云机场为主体的中南机场体系。同时，以成都双流机场、重庆江北机场和昆明长水机场为主的和以西安咸阳机场、乌鲁木齐地窝堡机场为主的西南、西北2大区域性机场体系雏形也逐渐形成，呈现集群化发展趋势。

近年来，随着航空运输需求增强和区域内机场联系更加密切，机场体系相关问题得到了部分学者的关注。文献[1]通过利用模糊自修正多目标粒子群算法，分析了多机场体系进场航班调度过程中时空资源的相关情况，有效地提高了多机场终端区的时空资源利用率。文献[2]围绕航线网络，将最短路算法与搜索禁忌算法结合使用，就我国多机场体系加以改进。这些研究仅从理论上实现了机场体系多方面运营优化，而未涉及最根本的体系划分，特别是机场体系的空间分布和规划，而现有的一些对机场体系划分的研究也仅是从经济、政治、交通等方面分析区域机场体系的形成规律，并未利用这些规律对机场体系进行合理划分。

因此，本文根据机场群以空间分布为主导的集聚模式，利用基于密度的聚类算法(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)对机场地理位置数据进行聚类分析，进一步划分机场体系，旨在为区域机场体系的规划布局实施提供可用的样式参考。

1 机场体系研究现状

民用机场追求盈利最大化，其服务对象面向民航客机，提供的是集社会性和盈利性为一身的公共商品。机场体系划分除需要满足区域交通运输体系的需求外，还要求迎合区域经济发展及区域城镇发展的需求[3]。在进行机场体系配置时，需考虑以下5项原则。

1) 区位原则。旅客和货物到达与离开机场的最短时间、最低成本和最短距离构成了机场的区位要素，形成了民航运输要素的吸引与辐射空间，符合递远递减规律。同一机场体系的机场要实现空间资源的有效整合，必须具有一定的替代性和互补性，反映到具体的体系规划工作上，即表现为辐射面积和吸引空间相交的重合部分在一定程度上足够大，同时该区域中所含的运输要素要大于一定临界值[4]。

2) 服务原则。机场体系配置应满足可达性、机动性、安全性和高效性的服务要求。

3) 社会原则。机场体系配置应与社会公平、社会保障、国家管理、国防建设等要求相契合。

4) 经济原则。机场体系布局应在一定程度上满足经济可持续发展的要求，在空间布局，合理安排航空活动，使航空活动达到临界经济规模。

5) 消费原则。在一些特殊地区，如青藏高原、岛屿和丛林地区，当旅游需求足够大时，可以建立空中观光和旅游的专用机场。在经济发达地区，可以设立专门的机场进行空中运动。

在上述机场体系配置原则中，区位原则是第一要素。空间资源的优化配置和布局是首要目标。其次才是在该空间范围内，根据一定的准则选择最满意的机场组合，并确定它们之间的协同作用。

当前机场主流布局模式如表1所示[5]。可以看出，机场体系在地理区域、经济区划和行政区划上保持相对统一，并且在空间范畴上和城市群对应，而同一地理区域内的近邻机场往往有可能集聚成为同一机场群。可以看出，不论何种布局，地理空间距离要素都在机场群的形成过程中发挥了不可忽视的重要作用。以地理空间距离为核心的集聚方式，一方面有利于满足各机场间的差异化需求定位与分工合作、运营需求，另一方面，也可以促进机场群内资源的优化配置，有效提高机场群的整体运营能力[6]。

2 聚类算法

聚类是在无先验知识的情况下根据某种准则，将数据对象划分为多个簇，使得同一个簇中的对象达到较高的相似度[7]，被广泛应用于数据分析。聚类算法的选择主要取决于数据的类型、聚类的目标和运用。本文以机场体系划分为研究对象，地理集聚可作为识别机场体系最主要的依据，即在地理空间上显著邻近的机场可被视为一个集群。空间聚类是定量识别区域划分的高效方法，在地理学领域，传统的基于划分的聚类方法已经得到一定程度的应用，如郑运鹏等[8]采用K-Means算法辨别了南京市的交通热点地区。然而该聚类方式存在不足，表现为只适合在指定聚类数目下找出球状簇。现实中的机场集群往往有着多种多样的形态，基于划分的聚类方法对于非球状簇显得无能为力。所以本文引入基于密度的DBSCAN聚类算法予以改进。

DBSCAN算法[9]最初由Ester等学者提出，该算法要求在聚类中给定半径的区域内即邻域(Eps)，数据对象个数必需超过某个指定值，即邻域密度必需大于某一阈值(MinPts)，将具备高密度的区域划定为簇，可以避免空间数据库中的噪声干扰，帮助发现不受形状限制的簇。

DBSCAN算法是由样本本身的向量(坐标值)决定了其在n维空间里的绝对位置，根据Eps和MinPts两个参数的组合设置，自动构成不固定形状的、不固定规模的簇，弥补了K-Means算法忽略样本密度的不足，旨在找到密度相连数据对象的最大集合[10]。

利用DBSCAN算法不需要预先指定K值以及可以发现任意形状的簇的优势，对机场进行体系划分，可以适应各机场地理分布不均的状况，同时不受噪音点干扰，可以得到较好的聚类效果。

表1 民用机场群主流布局基本模式

3 基于DBSCAN的机场体系划分方法

3.1 划分算法描述

本文关于机场体系划分方法是基于机场体系以空间分布为主导的集聚模式，采用DBSCAN空间聚类算法，对机场进行体系划分。DBSCAN算法的具体实现流程如图1。

Algo-rithm基于密度的DBSCAN算法Input:指定半径Eps(单个机场间距)指定阈值MinPts(机场体系内单个机场数量)原始数据集D(单个机场经纬度的数据集)={x1,x2,…,xm}过程:1: 标记所有的机场经纬度样本数据对象为未访问(unvisited);2: do3: 随机选择一个未访问的对象p; 标记p为已访问(visited);4: If(p的Eps-邻域至少有MinPts个对象) Then创建新的簇C,将p合并到簇C中 同时令候选集N为p的Eps-领域中的对象集合;5: For(N中的每个邻域对象p')6: If(p'未访问) Then标记为已访问(visited);7: If(p'的Eps-邻域至少有MinPts个对象) Then将这些对象添加到候选集N中;8: If(p'还不是任何簇的成员) Then将p'添加到簇C;9: End for10: 输出C;11: Else标记p为噪声;12: Until未标记为未访问(unvisited)的对象Output:机场体系划分阶段C={C1,C2,…,Ck};

图1 DBSCAN算法流程

DBSCAN算法的关键在于Eps和MinPts这两个参数的合理设置[11]，在MinPts确定的情况下，Eps越大，构成簇的所需密度越低。当Eps一定时，MinPts越大，核心点形成越困难，噪声点越多，簇的数目相应增加。DBSCAN算法的聚类质量和距离公式的选取紧密相关，常见的距离度量方法众多，代表的有欧式距离、切比雪夫公式、曼哈顿距离等[12]。因此，本文通过设置不同Eps、MinPts参数，选择不同的距离度量公式对样本数据集进行聚类尝试，最终确定和选择聚类效果较好的参数和距离公式。相应的聚类实现流程如图2所示。

3.2 测试数据及运行结果分析

数据获取：采用DBSCAN算法基于地理位置数据对机场进行体系划分，首先要获取各机场的准确地理位置数据集，即机场所在位置的经纬度数据集，包括机场的ID以及所在位置的经度、维度3项内容，如表2所示。实验的硬件环境及软件环境如表3所示。

表2 民用机场部分经纬度数据集

表3 实验环境

距离度量方面，数据中两点之间的距离是其密度的体现，决定了他们是否可以划分为同一类。聚类质量的好坏与距离公式的选取是否适宜紧密相关。DBSCAN算法采取的是近邻思维，通常选择闵可夫斯基距离(Minkowski Distance)这一距离度量公式，来对样本距离进行计算，其定义如下：

(1)

其中，p≥1。当p=1时，为曼哈顿距离；当p=2时，为欧式距离；当p∈(2,+∞)时，为切比雪夫距离。曼哈顿距离针对两点在标准坐标系上的绝对轴距总和进行计算，而切比雪夫距离公式适用的数据维度最少为3，由于本文计算的是二维空间下的两机场样本点间最短距离，故选用欧式距离。

在数据样本呈少量、低维分布的情况下，最近邻的寻找一般选择欧式距离公式直接计算全部样本的距离。若样本量很大且呈复杂多维分布，则利用KD树或者球树方法对空间进行划分更为适合[13]。考虑本文应用的数据维度较低，并且是对历史数据点进行聚类分级，要求从数据各个维度的数值大小中体现数据点之间的差异，故选择欧式距离进行度量，其数据维度为2时定义如下：

(2)

其中，x=(x1，x2，…，xm)，y=(y1，y2，…，ym)各自代表两个2维的对象。

输入参数选择方面，对参数Eps，通常预先指定K值，然后通过观察k-dist图的方法判断Eps[14]。其中，k-dist值定义为：给定K邻域参数k，对于数据集D中的每个点，计算其映射到第k个最近邻域的距离。如果按照k-dist值的升序顺序对数据集D的点加以排序，则称该图为升序k-dist图。若是选择任意点p，将参数Eps设置为k-dist(p)，并将参数MinPts设置为k，则全部具备相等或更小的k-dist值的点都是核心点。如果能在数据集D中找到具有最大k-dist值的阈值，将得到期望的参数值。阈值点是升序后的k-dist图的第一个急剧变化的拐点。

Ester等人已通过实验表明K>4的k-dist图与K=4时的k-dist图没有显著差异，而且它们需要更多的计算。MinPts的选择有一个关键的指导公式，即MinPts≥dim+1，式中dim代表待聚类数据的维度。若设置维度为1，则每一个独立点都是一个簇，若MinPts≤2时，则与层次距离最近邻域结果相同，关于MinPts的设置都不合理，是以MinPts值的设置只能在3以上。当值选择过小时，稀疏簇中结果因为密度小于MinPts，出现边界点不被用于类的进一步扩展的情况。若该值设置过大，则密度较大的两个邻近簇有可能被归为同一簇。

故此，一般预先指定K值为4，然后根据绘制升序k-dist图[51]的方法来选择Eps，具体步骤如下：

1) 计算每一个机场位置数据样本点与其他全部点之间的球面距离；

2) 计算各点的k-dist值，随后对所有点的k-dist集合进行升序操作，得到排序后的k-距离值；

3) 将所有点的k-dist值，在Excel中用散点图显示k-dist变化趋势，如图3所示；

4) 通过观察，将急剧发生变化的位置所对应的k-dist值，确定为半径Eps的值，对于选取的民用机场经纬度数据集，对其聚类的最佳Eps值为1.9。

MinPts参数方面，在Eps保持一定的情况下，MinPts选取[3,4,5…,10]等不同数值进行聚类，聚类个数的变化呈递减趋势，对聚类结果进行观察，选择聚类个数达到最大稳定时对应的MinPts值作为最佳MinPts值。

在Eps=1.9，MinPts∈{3,4，…,10}的情况下进行反复多次聚类，观察到在Eps=1.9，MinPts=5时噪声点个数较少，聚类效果最好，聚类结果如图4所示。

从集聚结果来看，机场被分为6个集群，机场体系分布主要集中在东经100°～125°，北纬20°～45°的范围，其中簇4集群最大，分布最广。机场地理位置数据被分为6簇，各样本点类簇与“十三五”《全国民用机场布局规划》中提出的六大民用机场体系划分拥有较好的耦合性[15]。具体表现在六大机场体系区域分布的数量规模和密度与我国区域经济社会发展水平和经济地理格局基本顺应，包括有以北京为主的华北机场体系、以沈阳为主的东北机场体系、以上海为主的华东机场体系、以成都、重庆和昆明为主的西南机场体系、以广州为主的中南机场体系和以西安、乌鲁木齐为主的s西北机场体系。这种结果的吻合也印证了采用DBSCAN算法基于地理位置数据对机场进行体系划分的可行性。但也存在以下问题：① 东南沿海地区机场分布密集，导致该算法将华东部分地区和中南地区聚类为一簇，与机场体系实际划分存在偏差；② 同样是分布密度不均问题，西部地区机场分布稀疏，各机场相距甚远，采用DBSCAN算法进行聚类会导致像乌鲁木齐地窝堡机场、拉萨贡嘎机场等重要机场很可能被判定为噪声点。

4 结论

本文对机场聚类分析作了初步的探讨，借鉴机场体系以空间分布为主导的集聚模式，采用DBSCAN聚类算法对机场体系进行合理划分。这对于有效发挥机场集聚模式的优势以及利用机场体系提高航空运输的运输效率，进一步优化区域航空运输的结构和布局具有现实和长远的意义。下一步将着眼于噪声数据的不良干扰问题，进行进一步数据清理，以优化聚类算法，提高聚类效率和质量。同时，在划分机场体系的基础上，探讨对区域机场体系运营效率进行评价的可行性。