基于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聚類算法對機場體系進行合理劃分。這對于有效發揮機場集聚模式的優勢以及利用機場體系提高航空運輸的運輸效率，進一步優化區域航空運輸的結構和布局具有現實和長遠的意義。下一步將著眼于噪聲數據的不良干擾問題，進行進一步數據清理，以優化聚類算法，提高聚類效率和質量。同時，在劃分機場體系的基礎上，探討對區域機場體系運營效率進行評價的可行性。