一种用于航空货运代理人信用等级分析的货检数据挖掘方法

崔学婷，柯永忠，孙茂鹏，司义品，高 杰

(1.北京航空航天大学，北京 100191;2天信达信息技术有限公司，北京 100022)

航空货运安检过程中，开箱检查环节非常重要，耗时费力。为了在保障航空安全的同时，提高安检效率，对不同信用评级的货运代理人的货物可采用“差异化安检”。对于信用评级低的代理人，提高开包率，重点检查；而信用评级高的代理人，提高过检便利性，从而在整体上提高安检效率。目前，对航空货运代理人的信用评级方法主要有层次分析法和扣分法。这两种算法在数据获取的便利性和评价时效性上，都有其局限性，见表1。

表1 算法对比

针对以上两种算法的局限性，笔者提出利用货运安检数据进行代理人信用评级分析。随着安检信息系统的广泛使用，积累了大量的货运安检数据，易于获取，且时效性高。因是未标记数据，需采用聚类的方法。其中K-Means算法[12]常被用于用户画像，或企业信用评级等领域。但K-Means算法也存在两点不足：对初始簇的中心敏感，以及针对不规则聚类簇效果差，无法保证所得结果是用户指定分类。为了解决这两个问题，提高聚类的准确性，笔者采用半监督学习的约束种子K-Means方法。在传统K-Means算法的基础上，通过引入少量带标记数据，来得到符合用户需求的聚类效果。

1 K-Means聚类

K-Means算法以各类样本中心代表该簇，初始中心是随机选择的，重复计算多次，过程如下：

①K-Means算法首先从样本集中随机选择K个样本，作为初始聚类中心，代表K个簇。C={C1,C2,…,Ci,…,Ck}为K个聚类中心。假设样本集为X={X1，X2，…，Xj，…，Xn}且Xj∈Rm，m为样本维度。计算每个样本Xj到中心点的距离d(Xj,Ci):

(1)

公式(1)中，g表示数据的第g维。

②每个样本点都有其对应的距离最近的中心点，将该样本点划分到该中心点所在簇中，全部分类后重新计算各个簇的中心。记第i类数据为Xi={Xi1，Xi2，…，Xip，…，Xiq}，其中q表示该样本规模，新的中心Ci计算式为：

(2)

③得到新的中心点后，通过公式(1)(2)重复以上步骤，直到各个簇的中心点不再变化。此时得到的中心点即为最终聚类中心，样本点所属的簇即为该样本的分类标记。

2 约束种子K-means算法

约束种子K-Means算法的思想是：在判断某个样本是否属于某个类时，依然采用与中心的距离来判断；对于已经有标签的样本，将它们固定好属于哪个类，这些带标签的样本，确定了各个类初始的聚类中心；而对于其他不带标签的数据，则根据其与各类中心的距离来判断。

该算法主要分为5个步骤进行：①根据带标记的数据，计算每个类的初始中心；②计算每个未标记样本到K个中心的距离；③选择距离最小的类作为该样本的类；④重新计算各类中心；⑤重复2步～4步，直到所有类中心都不再变化，或达到最大迭代值。

2.1 导入带标记数据

由货检信息系统的货运安检数据，统计后得到代理人的数据，经航空货运安检相关人士对部分典型的数据进行标记，如对安检件数很多(该代理人体量大)，开包率很小，危险品数很小，开包结果良好的代理人评为优；对安检件数很少，开包率却很高，危险品数较多，开包结果较差，存在大量移交、退运、暂扣的包裹等，这类代理人被标记为差；此外选一些各项指标处于中等级别的代理人，标记为中。将这些已标记的数据，导入到将进行聚类分析的无标记数据中，共同作为半监督聚类的输入数据。

2.2 根据带标记数据计算初始类中心

在K-Means算法中，初始K个聚类中心是随机值，因此聚类结果受初始值影响，并非每次结果都一致，且K-Means算法按照数据本身的特点来分类，因此其得到的结果可能并未与用户想要的分类效果一致。在原始代理人数据上增加一个属性，表示代理人级别。行业专家标记过的数据，在级别属性中分别填入相应的数值，其他未标记的数据该属性为空值。将全部这些数据作为约束种子K-Means算法的输入，具体计算过程如下：

①找到所有带标记的数据，并找到所有分类T={T1,T2,…,Ti,…,Tk}。

②对每一个分类Ti，找出所有级别属性为Ti的已标记数据Xj={Xj1,Xj2,…,Xjm,…,Xjn}，其中{j1,j2,…,jm,…,jn}为代理人级别为Ti的已标记数据在原始数据集中的下标，n为该类别已标记数据的个数。

③Ti分类的初始中心为

(3)

④由式(3)计算得到的所有的类别的初始中心，C={CT1,CT2,…,CTm,…,CTk}，由上述初始中心集，代替K-Means算法中的K个随机初始中心。

2.3 对未标记数据重复K-Means过程

对未标记数据运用K-Means算法中的式(1)，计算到每个中心点的距离，选取距离最近的中心点，将其分到该中心点所在分类后，重新计算各类中心。对其中一个类Ti，对所有属于该簇的数据，包括已标记数据和未标记数据，运用公式(3)计算新的类中心CTi。对每个类都得到新的中心点后，重复上述步骤，不断更新类的中心，直到各类的中心点不再变化，得到最终的聚类中心，未标记数据所属簇的类别，即为该代理人所对应的级别。

3 实验及结果分析

3.1 数据准备

本研究获取某机场2017年的5 300余条货检数据，经过数据清洗和统计相关的数值后，得到160余条代理人数据。航空货检数据字段说明，见表2中第1列是货检数据字段名称，第2列是字段中文解释，第3列是货检数据示例。

表2 货检数据字段说明

3.2 K值选择

运行约束种子K-Means算法前，首先要设置类簇的个数，即K值，确定数据被分为几个簇。轮廓系数在算法中是评判结果优劣的方法，设定分类数K后，计算对应的轮廓系数Sk，求取最大值。此时的K值则为最佳的聚类数目，同时最大的Sk被称作最佳聚类轮廓系数，此时的聚类结果认为是最佳聚类。如图1所示，K为3时轮廓系数最大。

图1 轮廓系数与不同类簇数之间的关系

3.3 聚类及对比实验

笔者利用货运安检系统数据，引入少量已标记数据，采用半监督约束种子K-Means聚类算法进行分析。作为对照分析，用传统K-Means算法进行了聚类分析。为了能直观地对比聚类效果，选取货检总件数、开包数量、危险品数量3个维度进行可视化展示。见图2和图3。

从图2可以看出，当K为3时，K-Means会将危险品率高的，开包率高的代理人分在两个不同的簇中，如图中黑圈标出的两个代理人，这显然不符合实际的评价标准。危险品率高的和开包率高的代理人，都应属于评级低的级别。引入带标记数据，运用约束种子K-Means算法后的聚类结果，如图3所示，可以看出，当代理人体量较小时，开包率高的与危险品数目比例高的代理人都划分为信用低的评级，这个分类结果更符合现实中的意义。

图2 K-Means聚类结果 图3 约束种子K-Means聚类结果

为了进一步说明约束种子K-Means算法，对聚类效果的改进，用ARI(adjusted rand index)指标来进行衡量。Vinh等指出ARI指标是目前最好的聚类评价指标。ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况越吻合。首先准备一部分带标记的代理人数据，作为测试集。用两种方法分别进行聚类，将标记结果与测试集中的原有标记进行比较，计算ARI指标。由表3可看出，约束种子K-Means的ARI数值更高，即该算法给出的评级结果与代理人的实际信用等级水平更接近。

表3 ARI指标对比

4 结束语

笔者目的是找到一种更加客观、实时地对航空货运代理人信用等级进行评估的方法。利用航空货运安检信息系统的数据，采用半监督学习的约束种子K-Means聚类方法，对航空货运代理人进行评级。

具体而言，利用半监督约束种子K-Means聚类算法，对航空货运代理人的安检数据进行分析，聚类结果可以有效地将代理人分为若干类。为了表明半监督约束种子K-Means算法的优越性，笔者对比了此算法与K-Means的聚类结果。半监督约束种子K-Means聚类的准确率比K-Means高；另外，通过对代理人的评级，可以直观地得到各代理人的信用水平，从而为合理安排安检资源，提高效率提供了合理建议；可以追踪每周代理人信用水平的变化，给予鼓励或督促改进，从而可以为代理人的监管，提供科学合理的支撑。