分布式聚类算法在航空客票代理人细分中的应用

2019-08-01樊玮，张伟

中国民航大学学报 2019年3期

樊玮，张伟

（中国民航大学计算机科学与技术学院，天津 300300）

2011年，麦肯锡全球研究报告《大数据：创新、竞争和生产力的下一个前沿领域》掀起了大数据热潮。在民航领域，大数据还处于起步阶段，有许多未知的应用途径需要进一步探索和发现。

对于整个民用航空市场，随着客票代理服务范围的扩大及其市场地位的提升，客票代理人已经掌握了大部分客源[1]，是航空公司客票市场份额中最主要的来源和支撑，在客票销售领域中拥有巨大的影响力。调查数据显示，目前约75%的航空客票销售订单来自航空公司以外的销售渠道，只有约25%是由各航空公司的官方订票网站或APP 完成，其余都是通过各种在线销售代理（如携程等）完成的。客户是航空公司发展与盈利的关键所在，在当前以网络销售为主渠道的形势下，各类销售代理具有极高的市场价值。处理好航空公司与客票代理人的关系，可有效提高经济效益。

目前，大数据相关技术多应用于旅客信息的挖掘与分析[2-3]以及航线航路的优化设计[4]，对于航空客票代理人的数据挖掘较少。聚类分析是一种常用且重要的数据挖掘手段，而K-means 算法因其简单高效被广泛使用。同时，为应对大数据时代数据量急剧增长的情况，如何将传统聚类算法在其核心组件——MapReduce编程模式下实现，成为当前研究的新热点。Chu 等[5]对各类算法以MapReduce 编程模式在集群上做了运行测试，结果表明，具有统计查询特征的算法均可以在分布式集群上实现，且算法的运行速度有了明显提升。谢雪莲等[6]、江小平等[7]给出了基于Hadoop 的分布式Kmeans 算法实现策略，结果表明MapReduce 编程模型下的分布式K-means 算法拥有更快的运行速度和更好的拓展性。贾瑞玉等[8]设计实现了分布式遗传Kmeans 算法，结果表明处理大规模数据时该算法的执行效率和聚类效果均有明显提高。Yang 等[9]介绍了Cop-K-means，即一种改进K-means 算法在MapReduce 上的实现。

基于上述研究成果，为了更好地处理越来越庞大和复杂的数据，针对K-means 算法的缺陷，提出了分布式Canopy-K-means 聚类算法，以便能够快速有效地分析航空客票代理人。该算法依靠Canopy 算法进行粗聚类，从而优化传统K-means 算法随机选取聚类中心点和聚类个数、依靠主观经验的缺点。通过分布式Canopy-K-means 算法对客票代理人进行准确细致的刻画，有效挖掘航空代理人数据，为航空公司制定代理人销售计划提供参考。

1 Canopy-K-means 算法

1.1 K-means 简介及其不足

K-means 算法假设原始数据的集合为{x1，x2，…，xn}，且每个数据对象xi是一个d 维的向量。K-means 算法开始运行时，根据主观经验人为确定聚类数量k，随后从整个数据集中随机选出k 个数据对象作为K-means聚类算法的初始聚类中心。然后，K-means 聚类算法遍历整个数据集，计算每个数据对象与聚类中心的距离（如欧氏距离），将数据对象划分给与其距离最近的聚类中心所属的类中，遍历结束后，根据各类中的数据对象重新计算类的中心，作为下一次迭代的聚类中心。反复迭代多次，直至迭代次数达到用户设定次数或聚类中心的变化小于规定阈值（即聚类中心不再改变），算法结束。

K-means 聚类算法虽然十分简洁且效率极高，但仍存在一些不足，主要体现为以下3 点。

1）聚类数量k 值的选取主要依靠人工确定，这要求用户必须对数据集有充分的了解才能使选择的k值符合数据集实际情况，而该条件在绝大多数实验与应用中无法满足。

2）初始聚类中心通过随机方法选取，使聚类算法在进行多次实验时结果相差较大，不够稳定，且该选取策略极易使算法陷入局部最优解。

3）该算法对孤立数据节点异常敏感，若孤立数据节点在K-means 算法应用场景对最终结果分析无任何帮助，属于噪音数据，将会对K-means 聚类算法的收敛速度产生极大影响。

1.2 Canopy 算法

与K-means 算法不同，Canopy 算法最大的特点是不需要事先指定k 值，因此可对K-means 算法进行有效优化。与其他聚类算法相比，Canopy 聚类虽然精确度较低，但在速度上有很大优势，因此可以使用Canopy 算法先对数据进行“粗”聚类，得到k 值和初始聚类中心，然后再用K-means 进一步“细”聚类。Canopy 算法的思想及步骤如下。

1）确定两个阈值t1和t2（要求t1＞t2）。

2）算法中有1 个Canopy 集合，从数据集合中随机选出1 个数据，计算该数据到Canopy 集合中每个Canopy 的距离（集合初始为空，则将第1 个数据直接作为1 个Canopy）。

3）如果距离小于t1，则将该数据分配到该Canopy（1 个数据可以分配给多个Canopy）。

4）如果距离小于t2，则认为该数据与该Canopy 的距离已足够近，不可能成为新的Canopy，将其从数据集合中删除。

5）如果大于t1，则作为新的Canopy 加入集合。

6）重复步骤2）～步骤5），直至数据集合中的数据全部被删除。

Canopy 聚类结果如图1所示，其中包含5 个Canopy 集合，实线大圆表示t1的范围，虚线小圆表示t2的范围。

图1 Canopy 聚类示例图Fig.1 Canopy clustering instance

1.3 分布式Canopy-K-means 算法

MapReduce 编程模型主要由map 和reduce 两个部分组成，两部分任务分配到各个节点后均并行执行，节点执行结果相互之间不产生影响。程序启动后，数据被分片，然后分派到集群中各个执行map 函数的节点，map 阶段处理产生的中间结果经过重新整合后，再分配到各个执行reduce 函数的节点上。

结合Canopy 算法以及分布式MapReduce 程序处理流程，分布式Canopy-K-means 算法的设计如下：

1）通过Canopy 算法进行粗聚类，得到初始聚类中心和聚类数量k 值，将其作为输入数据传递到分布式K-means 算法中，Canopy 算法的具体实现细节见1.2部分。

2）在map 阶段每获取到1 个数据对象，计算其与所有类别聚类中心之间的欧氏距离，将数据对象划分到与其距离最近的聚类中心所代表的类中，然后将该类的标签作为key 值，将数据对象作为value 值，形成＜key，value＞键值对输出。

3）在reduce 阶段的输入数据为＜key，list（value）＞，其中key 值是类标签，list（value）是同一类数据对象的集合列表，利用式（1）计算同一类中所有数据对象属性值的均值，将其作为新的聚类中心并输出，即

其中：data 为数据对象；Ci为第i 类聚类；data 的m 维属性为（a1，a2，…，am），Ni为第i 类中数据对象的个数。

4）reduce 得到的新聚类中心与原聚类中心进行比较，判断聚类算法是否已经收敛。若新聚类中心与原聚类中心的差值不符合阈值要求，则清空原聚类中心的数据文件，将reduce 的输出结果写到中心文件中，作为下次迭代时的聚类中心，然后跳转到第二步进行迭代；若差值符合阈值要求，则运行一个没有reduce的任务将聚类结果输出，并结束程序。

该算法是一个迭代算法，第4）步要使式（2）中的函数最小化，假设原始数据的集合为{x1，x2，…，xN}，xi为d 维向量，这N 个数据点需要分为k 个分类。

其中：rnk在数据点n 被归类到分类k 时为1，否则为0；μk为第k 类聚类的中心；J 为目标函数值。K-means 算法的目标是使J 值最小，即聚类结果中数据点与其所属类的聚类中心之间的距离最小。

算法的实现需要建立2 个Job：Job1用于执行Canopy 算法，以实现粗聚类，然后将Job1产生的结果，即初始聚类中心传递到Job2中。Job2的主要任务就是执行K-means 算法，通过多次迭代，使聚类中心的变化符合阈值要求或达到预定迭代次数，算法完成。分布式Canopy-K-means 聚类算法的流程如图2所示。

图2 Canopy-K-means 算法流程图Fig.2 Flow chart of Canopy-K-means algorithm

2 数据属性

采用国内某航空公司单季度销售记录作为原始数据，处理后得到对7 000 多个代理人的销售评价结果，数据各属性含义如表1所示。

表1 数据属性Tab.1 Data attributes

表1中，代理人的出度入度之和反映了代理人的活跃度；代理人日销售额占市场销售总额的比例及其占比的标准差反映了代理人的市场地位，并可用于推测代理人的销售能力是否稳定。由于代理人之间的销售能力和综合实力差异较大，使得代理人每日销售额占比之间的差距十分悬殊，故采用异常系数来比较代理人之间的销售能力稳定性，异常系数计算方法为

其中：SD（x）为x 的标准差，mean（x）为x 的均值；代理人的平均售票价格及其标准差反映了代理人销售机票的倾向：如果代理人的平均售票价格偏低，且方差较小，则该代理人可能主要销售近程机票。代理人与代理人、乘客、航空公司之间的买卖交易占比反映了代理人的购票渠道偏好和销售渠道偏好。

3 仿真研究

3.1 实验环境

实验使用包含5 个节点的Hadoop 集群，Hadoop版本为2.5.2，各节点的性能参数如表2所示。

表2 节点性能参数Tab.2 Node performance parameters

3.2 数据预处理

由于表1所示的代理人各评价指标量纲和单位不同，数值相差较为悬殊，这将对分析结果造成影响。为消除指标之间的量纲影响，需要对数据进行标准化处理，以解决数据指标之间的可比性。采用0-1 标准化，根据指标平均值和标准差来进行规范化，即

其中：μ 为该指标的均值；σ 为该指标的标准差，经过处理的数据符合标准正态分布，即均值为0，方差为1。

3.3 实验结果分析

经过Canopy-K-means 聚类算法计算，最终将所有代理人聚集为6 类。这6 个聚类的聚类中心数据分析如图3所示。由图3可推测各类代理人的特征，从而说明分布式Canopy-K-means 算法在航空代理人细分应用上的合理性。其中：C 为航空公司，A 为代理人，P 为乘客。

从业务范围、经营规模、经销模式3 个方面划分航空客票代理人。根据航空客票代理人的销售业务范围，可将其分为两类：一类客票销售代理人主要负责国际航线或港澳台地区航线的航空客票代理销售业务；二类客票销售代理人主要负责国内除港澳台地区以外的航空客票代理销售业务。根据经营规模，可将航空客票代理人分为大型、中型和小型代理人。根据航空客票代理人的经销模式，可以将其分为批发性代理人、差旅管理公司和在线分销[10]。

图3 聚类结果分析图Fig.3 Analysis diagram of clustering results

根据图3，从代理人的活跃度、市场地位及能力、市场定位和买卖交易偏好4 个方面对聚类结果进行分析，将分析结果结合机票销售市场实际情况，对各个类别在市场中属于何种代理人身份进行推测，从而得到如表3所示结果。

对相关代理人的研究与考核表明，实验结果与考核结果相符合，证明算法具有实际应用价值，适用于销售代理人分类。

表3 各聚类特点描述及推测结果Tab.3 Characteristic description and conjectural result of each cluster

根据表3分析，首先针对第2、4 类小型的、市场占比低的代理人，需要航空公司对其进行调查、整顿，取消资质不佳、有经常拖欠票款等不良行为、业务水平低下者的代理人资格；培训其他代理人，以提高其素质和销售能力，逐渐提高其市场地位。针对第3、5、6类大型优秀代理人，航空公司可以加大技术、资金和场地投入，增强代理人的信心与忠诚度，使双方形成较为牢固的战略合作关系。同时，航空公司还可与代理人共同发现和开发高收益用户，针对该类用户制定更优质的服务策略；针对第1 类代理人，航空公司可为其制定各种优惠套餐和会员优惠，将更多的用户吸纳进来。