CN109886352B - 一种空域复杂度无监督评估方法 - Google Patents

Abstract

本发明涉及一种空域复杂度无监督评估方法，步骤为：通过处理扇区运行数据得到原始复杂度样本，每一条样本对应某一扇区在某一时段内的运行态势，利用核主成分分析方法KCPA，将原始复杂度样本非线性映射至无限维的再生核希尔伯特空间中，再将这些无限维样本转换至最大化复杂度评估信息量的低维子空间中，从中抽取出满足用户需求贡献率的m个主成分；接着设计一种多种输入参数可调的聚类算法，用户基于所要评估的扇区运行特点按需配置复杂度等级数量、各复杂度等级样本比例以及初始聚类中心，经过聚类实验得到各个原始样本等级聚类结果，最终完成空域复杂度无监督评估。

Description

一种空域复杂度无监督评估方法

技术领域

本发明属于空域复杂度评估领域，具体涉及一种空域复杂度无监督评估方法。

背景技术

空域复杂度评估作为衡量空域运行态势、管制员工作压力的关键手段，是航空交通运行调控的基础。由于影响因素众多，不同因素间耦合关联复杂，且标定样本很难获取，空域复杂度的准确评估被公认为航空领域的挑战性问题。

针对空域复杂度评估，国内外学者提出了多种方法，包括米兰理工大学Prandini教授等[[1]Prandini M,Hu J H.A probabilistic approach to air trafficcomplexity evaluation[C]//Proceedings of the Joint 48th IEEE Conference onDecision and Control and 28th Chinese Control Conference,Shanghai,China,December 16-18,2009.]提出的航班冲突概率指标、法国国立民航大学Delahaye教授等[[2]Puechmorel S,Delahaye D.New trends in air traffic complexity[C]//Proceedings of the 2009ENRI International Workshop on ATM/CNS(EIWAC),Tokyo,Japan,March 5-6,2009.]提出的Lyapunov指数指标，但计算角度的单一性导致对复杂度的度量较为片面。此外还有如Gianazza教授[[3]Gianazza D.Forecasting workload andairspace configuration with neural networks and tree search methods[J].Artificial Intelligence,2010,174:530-549.]提出的利用神经网络研究空域复杂度，但基于机器学习的空域复杂度评估模型的性能严重依赖标定样本。而空域复杂度的样本标定需要空中交通管制专家在细致查看管制信息的基础上进行人工标定，获取成本很高。此外，由于空域静态结构与运行机理的动态演变，已有标定样本会陆续过期，当需要训练新的复杂度评估模型时，很难保证有标定样本可用，导致了模型的可靠性严重降低。

发明内容

本发明技术解决问题：克服现有技术的不足，提供一种空域复杂度无监督评估方法，通过核主成分分析挖掘原始样本各维度的非线性耦合关系，准确提取能够最大化复杂度评估信息量的主成分，进一步设计可按需定制的主成分聚类方法，最终实现无监督条件下空域复杂度的准确评估。

本发明技术解决方案：一种空域复杂度无监督评估方法，主要包括：样本数据KPCA降维、主成分聚类、扇区复杂度评估验证步骤。

第一步，从扇区运行数据中得到原始复杂度样本，其中每一条样本对应某一扇区在某一时段内的运行态势，利用核主成分分析方法即KCPA，将原始复杂度样本非线性映射至无限维的再生核希尔伯特空间中，再将这些无限维样本转换至最大化复杂度评估信息量的低维(不超过10维)子空间中，最后从中抽取出满足用户需求贡献率的m个主成分；

第二步，针对第一步得到的降维样本集，设计一种多种输入参数可调的聚类算法，用户基于所要评估的扇区运行特点按需配置参数大小，通过该聚类算法得到各个原始样本等级聚类结果，完成空域复杂度无监督评估。

所述第一步具体实现如下：

首先基于高斯核函数将原始样本非线性映射至超高维样本空间(ReproducingKernel Hilbert Space，RKHS)中，令高斯核函数为k，某一条原始样本x被映射至RKHS后为k(x,·)，通过将数据向无限维空间映射，找到分割数据的高维超平面；

具体求解表达式为：

max tr(V^Tk(X,·)Hk^T(X,·)V)

s.t.V^Tk(X,·)Hk^T(X,·)V＝Λ

V^TV＝I

k(X,·)＝[k(x₁,·),k(x₂,·),…k(x_i,·),,k(x_n,·)]

k(x_i,·)(1≤i≤n，n为样本数量)为无穷维样本，

V∈R^∞×n，为所需求解的样本转换矩阵，其中m为样本降维后的维度，则主成分V^Tk(X,·)＝W^Tk(X,·)^Tk(X,·)＝W^TK，即将样本从无限维空间转换至最大复杂度评估信息量的低维子空间中，将求解V的问题转化为求解W的问题。

求解W的具体表达式为：

max tr(W^TKHKW)

s.t.W^TKHKW＝Λ

W^TW＝I

其中，

为去均值矩阵，1为元素全为1的n维列向量，T表示转置；W为特征向量。

通过求解，得W＝[w₁,w₂,…,w_m]，则求出第p个主成分的贡献率为

λ_p为第p个特征值,1≤p≤m。最终从大到小得排序，提取满足贡献率的m个主成分。

所述多种输入参数可调的聚类算法的实现如下：

(1)根据主成分设置初始簇中心参数，初始簇中心参数包括复杂度等级数量、各复杂度等级样本比例以及初始聚类中心；

(2)初始簇中心为聚类算法提供不同复杂度等级簇所处样本空间位置的指导信息。由于“航空器数量”、“航空器密度”这两个因素与复杂度有着强烈的正向关联，且“航空器数量”也是当前空管系统中唯一的被实际用于衡量扇区复杂度的指标。因此，本发明提出参照“航空器数量”与“航空器密度”两个因素来设置初始簇中心参数。该参数设置方法为，首先对原始样本进行排序，排序标准为“航空器数量”从低到高，对于“航空器数量”因素取值相同的样本，按“航空器密度”从低到高排序；接着按照设置的复杂度等级数量、各复杂度等级样本比例参数，基于排序后样本初步划分样本的复杂度等级；然后将该样本集整体映射到高维核空间后，求解每一复杂度等级样本簇对应m个主成分的均值，作为初始簇中心。再按照设置的复杂度等级数量、各复杂度等级样本比例参数，基于排序后样本初步划分样本的复杂度等级；

(3)根据(2)设定的复杂度等级个数、各等级包含样本数量、各等级样本簇初始中心进行聚类，得到各个原始样本等级聚类结果。

本发明的原理：

为从原始样本中挖掘扇区复杂度评估知识，需对样本进行降维，抽取能够准确表征扇区复杂度评估知识的主成分，降低复杂度评估难度。采用非线性的PCA方法——KPCA，先将原始样本非线性映射至超高维样本空间中，再由此转换至最大化复杂度评估信息量的低维子空间中，获得在统计上不相关的主成分。

设计了一项多种输入参数可调的聚类算法，能够根据所评估扇区运行特点实现按需配置。参数包括复杂度等级数量、各复杂度等级样本比例，以及初始簇中心。其中，初始簇中心为聚类算法提供不同复杂度等级簇所处样本空间位置的指导信息。

本发明提出利用m个主成分来设置初始簇中心参数。该参数设置方法为，首先对原始样本进行排序，排序标准为第一主成分从低到高，对于第一主成分取值相同的样本，按第二主成分从低到高排序，对于第二主成分取值相同的样本，按第三主成分从低到高排序，以此类推；接着按照设置的复杂度等级数量、各复杂度等级样本比例参数，基于排序后样本初步划分样本的复杂度等级；然后将该样本集整体映射到高维核空间后，求解每一复杂度等级样本簇对应m个主成分的均值，作为初始簇中心。最终根据上述初步划分样本的复杂度等级个数、各等级包含样本数量、各等级样本簇初始中心进行聚类，得到原始样本复杂度等级聚类结果。

本发明与现有技术相比的优点在于：

(1)本发明提出了一种基于核主成分分析的空域复杂度无监督评估方法，在不依赖标定样本的基础上通过主成分提取与主成分聚类对指定空域的复杂度等级进行划分，解决了由标定样本采集困难所导致的空域复杂度难以准确评估的问题。

(2)本发明采用的核主成分分析方法能够从多维因素中提取最大化空域复杂度评估知识的主成分；所设计的主成分聚类方法能够根据实际空域运行特点进行配置，满足模型用户对于不同扇区复杂度评估的具体要求。

附图说明

图1为本发明的空域运行复杂度无监督评估方法流程图；

图2为本发明的空域运行复杂度无监督评估结果图，其中(a)为扇区GY01，(b)扇区：GY02，(c)扇区：KM03，(d)扇区：CD02。

具体实施方式

下面通过具体实施例并结合附图对本发明做进一步的详细描述。

如图1所示，本发明的一种空域运行复杂度无监督评估方法，具体包含以下几个步骤：

步骤一：KPCA降维。

影响扇区复杂度的关键因素多达数十个，各因素对于扇区复杂度评估任务的信息贡献程度不同，且耦合关联复杂，所蕴含复杂度评估知识重叠。以上特点使得在无监督条件下提取扇区复杂度评估知识非常困难。为从高维原始样本中挖掘扇区复杂度评估知识，需对样本进行降维，抽取能够准确表征扇区复杂度评估知识的主成分，降低复杂度评估难度。

主成分分析(Principal Component Analysis，PCA)是挖掘高维样本数据中主成分的常用方法。然而，传统PCA的主成分提取过程是线性的，不适用于各维度间非线性耦合的扇区复杂度样本。因此本文采用非线性的PCA方法——KPCA，先将原始样本非线性映射至超高维样本空间中，再由此转换至最大化复杂度评估信息量的低维子空间中，获得在统计上不相关的主成分。KPCA步骤如下。

首先，基于高斯核函数将原始样本映射至无限维的再生核希尔伯特空间(Reproducing Kernel Hilbert Space，RKHS)中。令该核函数为k，某一条原始样本x被映射至RKHS后为k(x,·)。继而在RKHS中通过样本维度转换获得主成分，求解主成分的表达式如下。

max tr(V^Tk(X,·)Hk^T(X,·)V)

s.t.V^Tk(X,·)Hk^T(X,·)V＝Λ

V^TV＝I

通过上式求解出V。具体各个变量的定义如下：

式中，

是所评估扇区的原始样本集，n为样本数量，d为样本维度。X中各行均已作z-score标准化处理，即样本的各个维度均已作去量纲处理。

是所需求解的样本转换矩阵，即由k(X,·)转换得到的主成分为V^Tk(X,·)，m为样本降维后的维度，即所获得的主成分个数。I为单位矩阵。

为去均值矩阵，

1为元素全为1的n维列向量。

为任一对角矩阵。需说明，k(x_i,·)(1≤i≤n)为无穷维样本，无法直接基于式(X)求解V。由此，特别令

W为特征向量，则主成分V^Tk(X,·)＝W^Tk(X,·)^Tk(X,·)＝W^TK，其中，

为核矩阵，K中各个元素k(x_i,x_j)能够通过以x_i和x_j为自变量的明确函数式计算得到。于是，求解V的问题转化为求解W的问题，如下式。

max tr(W^TKHKW)

s.t.W^TKHKW＝Λ

W^TW＝I

通过上式求解出W。具体各个变量的定义如下：

易知，上式的解为W＝[w₁,w₂,…,w_m]，其中w_i(1≤p≤m)为KHK第p个特征值λ_p对应的特征向量(令KHK的特征值为λ_j,1≤j≤n，且λ_j≥λ_j+1,1≤j≤n-1)，也对应第p个主成分。第p个主成分的贡献率为

该贡献率正比于第p个主成分的样本方差，可用于衡量主成分重要程度与挑选主成分。

步骤二：主成分聚类

通过KPCA提取出m个主成分后，若直接采用传统聚类算法处理扇区复杂度样本，则会忽略掉实际空管中不同扇区对于复杂度等级划分的差异性要求。因此，设计了一项多种输入参数可调的聚类算法，能够根据所评估扇区运行特点实现按需配置。

参数包括复杂度等级数量、各复杂度等级样本比例，以及初始簇中心。其中，初始簇中心为聚类算法提供不同复杂度等级簇所处样本空间位置的指导信息。由于“航空器数量”、“航空器密度”这两个因素与复杂度有着强烈的正向关联，且“航空器数量”也是当前空管系统中唯一的被实际用于衡量扇区复杂度的指标。因此，我们提出参照“航空器数量”与“航空器密度”两个因素来设置初始簇中心参数。该参数设置方法为，首先对原始样本进行排序，排序标准为“航空器数量”从低到高，对于“航空器数量”因素取值相同的样本，按“航空器密度”从低到高排序；接着按照设置的复杂度等级数量、各复杂度等级样本比例参数，基于排序后样本初步划分样本的复杂度等级；然后将该样本集整体映射到高维核空间后，求解每一复杂度等级样本簇对应m个主成分的均值，作为初始簇中心。接着，按照设置的复杂度等级数量、各复杂度等级样本比例、初始簇中心参数，通过下述算法完成聚类，得到原始样本聚类结果。

具体聚类算法步骤如下：

算法输入：扇区复杂度等级个数，各等级包含样本数量(总和应为原始样本集大小)，各等级样本簇初始中心

算法输出：各条样本所属复杂度等级

算法流程：

1.计算各簇中心

2.将各条样本分配至簇中心离其最近的簇中

3.设所有簇为“未处理簇”

4.设clu为“未处理簇”中复杂度等级最低的簇

5.WHILE TRUE

6.IF clu为“未处理簇”中复杂度等级最低的簇

7.设cluneighbor为比clu复杂度等级高一级的簇

8.ELSE IF clu为“未处理簇”中复杂度等级最高的簇

9.设cluneighbor为比clu复杂度等级低一级的簇

10.END IF

11.计算各条样本的Bef值。样本x的Bef值为Bef(x)＝d_x→clu-d_{x→cluneighbor}，其中d_x→clu为x与clu中心之间的距离

12.IF clu的簇大小小于用户为其设定的大小

13.按Bef由小到大的次序从cluneighbor中挑选出m条样本，将它们加入clu(m为clu的簇大小与用户为其设定的大小之间差值的绝对值)

14.ELSE IF clu的簇大小大于用户为其设定的大小

15.按Bef由大到小的次序从clu中挑选出m条样本，将它们加入cluneighbor

16.ELSE

17.END IF

18.设clu不为“未处理簇”

19.IF仍存在两个(含)以上的“未处理簇”

20.IF clu最近曾被设为“未处理簇”中复杂度等级最低的簇

21.设clu为“未处理簇”中复杂度等级最高的簇

22.ELSE IF clu最近曾被设为“未处理簇”中复杂度等级最高的簇

23.设clu为“未处理簇”中复杂度等级最低的簇

24.ELSE

25.END IF

26.ELSE

27.跳出WHILE循环

28.END IF

29.END WHILE

在上述程序叙述的同时，采用语言流程图进行说明，即(1)计算各簇中心，将各条样本分配至簇中心离其最近的簇中，进入(2)；

(2)设所有簇为“未处理簇”，设clu为“未处理簇”中复杂度等级最低的簇，进入(3)；

(3)判断是否有跳出条件，若无，进入(4)；否则结束进程；

(4)如果clu为“未处理簇”中复杂度等级最低的簇，则设cluneighbor为比clu复杂度等级高一级的簇，进入(6)；否则进入(5)；

(5)如果clu为“未处理簇”中复杂度等级最高的簇，则设cluneighbor为比clu复杂度等级低一级的簇，进入(6)；

(6)计算各条样本的Bef值。样本x的Bef值为Bef(x)＝d_x→clu-d_{x→cluneighbor}，其中d_x→clu为x与clu中心之间的距离；

(7)如果clu的簇大小小于用户为其设定的大小，则按Bef由小到大的次序从cluneighbor中挑选出m条样本，将它们加入clu(m为clu的簇大小与用户为其设定的大小之间差值的绝对值)，进入(9)；否则进入(8)；

(8)如果clu的簇大小大于用户为其设定的大小，则按Bef由大到小的次序从clu中挑选出m条样本，将它们加入cluneighbor，进入(9)；

(9)设clu不为“未处理簇”；

(10)如果仍存在两个及两个以上的“未处理簇”，进入(11)，否则进入(12)；

(11)如果clu最近曾被设为“未处理簇”中复杂度等级最低的簇，则设clu为“未处理簇”中复杂度等级最高的簇，进入(13)；否则进入(12)；

(12)如果clu最近曾被设为“未处理簇”中复杂度等级最高的簇，则设clu为“未处理簇”中复杂度等级最低的簇，进入(13)；

(13)返回(3)。

空域运行复杂度无监督评估实验

本发明设置基于4个扇区(扇区代码：GY01、GY02、KM03、CD02)在2010年7月28日8：00～24:00GMT的运行数据进行复杂度评估实验。这一数据集包含3840(960分钟*4扇区)条复杂度样本，其中的每一条样本对应某一个扇区在某一分钟内的运行态势。为验证所提出的扇区复杂度无监督评估方法的准确性，对4个扇区样本的复杂度等级进行标定，包括低复杂度、中复杂度、高复杂度三种。

接着，分别通过步骤一的KPCA降维和步骤二的主成分聚类进行实验，得到基于主成分聚类的复杂度等级划分结果，根据实验结果判定所提模型的评估性能。

表1显示了从各扇区样本所提取主成分的贡献率。对任意扇区，前两个主成分贡献率之和均超过88％，因此仅抽取前两个主成分(m＝2)即能够保留原始样本蕴含的绝大部分复杂度评估知识。图2展示了扇区复杂度无监督评估的结果。在(a)为扇区GY01，(b)扇区：GY02，(c)扇区：KM03，(d)：CD02扇区，4个扇区样本集上实验的结果显示可以看出，无监督模型在4个扇区样本集上平均评估准确率高达74％，说明所本发明具有很好的扇区复杂度无监督评估性能，能够为空域划分、流量管理等空管业务提供可靠的技术支撑。

表1扇区样本提取主成分贡献率表

以上虽然描述了本发明的具体实施方法，但是本领域的技术人员应当理解，这些仅是举例说明，在不背离本发明原理和实现的前提下，可以对这些实施方案做出多种变更或修改，因此，本发明的保护范围由所附权利要求书限定。

Claims (2)

1.一种空域复杂度无监督评估方法，其特征在于，包括：样本数据KPCA降维、主成分聚类步骤；

第一步，从扇区运行数据中得到原始复杂度样本，其中每一条样本对应某一扇区在某一时段内的运行态势，利用核主成分分析方法即KPCA，将原始复杂度样本非线性映射至无限维的再生核希尔伯特空间中，再将这些无限维样本转换至最大化复杂度评估信息量的低维子空间中，最后从中抽取出满足用户需求贡献率的m个主成分，即各条原始样本被降维成m维样本；

第二步，针对降维样本集，设计一种多种输入参数可调的聚类算法，用户基于所要评估的扇区运行特点按需配置复杂度等级数量、各复杂度等级样本比例以及初始聚类中心，得到各个原始样本等级聚类结果，最终完成空域复杂度无监督评估；

所述第一步具体实现如下：

首先基于高斯核函数将原始样本非线性映射至超高维样本空间Reproducing KernelHilbert Space，即RKHS中，令高斯核函数为k，某一条原始样本x被映射至RKHS后为k(x，·)，通过将数据向无限维空间映射，找到分割数据的高维超平面；

具体求解表达式为：

max tr(V^Tk(X，·)Hk^T(X，·)V)

s.t.V^Tk(X，·)Hk^T(X，·)V＝Λ

V^TV＝I

k(X，·)＝[k(x₁，·)，k(x₂，·)，…k(x_i，·)，k(x_n，·)]

k(x_i，·)为无穷维样本，1≤i≤n，n为样本数量；V＝k(X，·)W，

则主成分V^Tk(X，·)＝W^Tk(X，·)^Tk(X，·)＝W^TK，即将样本从无限维空间转换至最大复杂度评估信息量的低维子空间中，将求解V的问题转化为求解W的问题，

求解W的具体表达式为：

max tr(W^TKHKW)

s.t.W^TKHKW＝Λ

W^TW＝I

通过求解，得W＝[w₁，w₂，...，w_m]，则求出第p个主成分的贡献率为

最终从大到小得排序，提取满足贡献率的m个主成分，λ_p为第p个特征值。

2.根据权利要求1所述的空域复杂度无监督评估方法，其特征在于：所述第二步，多种输入参数可调的聚类算法的实现如下：

(1)根据主成分设置初始簇中心参数，初始簇中心参数包括复杂度等级数量、各复杂度等级样本比例以及初始聚类中心；

(2)初始簇中心为聚类算法提供不同复杂度等级簇所处样本空间位置的指导信息；按照“航空器数量”与“航空器密度”两个因素来设置初始簇中心参数，然后按照设置的复杂度等级数量、各复杂度等级样本比例参数，基于排序后样本初步划分样本的复杂度等级；然后将该样本集整体映射到高维核空间后，求解每一复杂度等级样本簇对应m个主成分的均值，作为初始簇中心；

(3)根据(2)的复杂度等级个数、各等级包含样本数量、各等级样本簇初始中心进行聚类，得到各个原始样本等级聚类结果。

Images