供应商网络结构特征多维层次聚集算法

萧展辉， 唐良运， 孙 刚

(1. 华南理工大学 计算机科学与工程学院， 广州 510006； 2. 南方电网数字电网研究院有限公司 平台安全分公司数据平台事业部(南网大数据中心)， 广州 510663)

世界经济的快速发展有效地推动着企业的进步，新兴信息技术在各个领域中的渗透，使中国产业变革的进程不断加快[1].各种供应商的资源也逐渐发展成为企业竞争的核心依据.用户需求的不断增加与日益激烈的市场竞争，促使着企业供应商必须开展相关的运营和产品创新等活动，因此，有效的管理以及供应商网络已成为制造业领域的重点研究内容，同时也是学术界研究的热点.李民等[2]针对供应商优选决策过程展开研究，对两级供应链构建多代理仿真模型，并验证了多种参数在供应链传播角度产生的影响，发现供应商网络中各成员之间的财务操作决策是影响供应链传播的重要因素之一.但是该方法缺少聚类分析过程，未充分考虑供应商网络的结构特征，导致其应用效果较差.李昌盛等[3]则基于聚类分析过程，提出了一种降低连接和聚集操作的新算法.该算法充分考虑了供应商网络复杂、多维层次的特点，在原有的位图连接索引基础上，采用层次联合代理和预先分组排序的方法，使多维层次上的连接和聚集操作转化成事实表上的区域查询，从而在处理多维层次聚集的同时，提高了网络连接和聚集的效率.然而在实际应用中发现，该方法中所提的聚类过程不适应特征较多的供应链网络.

针对上述问题，本文提出了一种供应商网络结构特征多维层次聚集算法.通过Spark为数据集提供支撑，将数据存储到集群机器内存中，通过服务编号来区分不同用户的请求.利用表连接操作的中间结果，在降低耗时的同时，还能够提升连接操作的利用效率.实验测试表明，所提算法能够有效提升聚集效率，能更好地完成供应商网络结构特征多维层次聚集.

1 方法论

1.1 供应商网络结构特征的联机分析处理

供应商网络具有层级关系，不仅包括了制造企业和各级供应商之间的纵向关系，还包括了供应商和供应商之间的横向关系.在网络结构中，企业处于核心位置，与网络中供应商、供应商的供应商相互联系、交织在一起.为了有效增加供应商网络中的分布式计算框架利用效率，本文以Spark为数据集提供支撑，并将供应商网络数据存储到集群机器内存中，联机分析处理结构如图1所示.

图1中，应用层为供应商网络的终端用户提供接口并展示操作结果，同时还能够通过浏览器进行多维分析查询和用户登录等相关操作；驱动层主要负责处理不同处理器对应的公共程序接口，能够全面提升供应商网络的通用性；服务器层主要负责接收处理各供应商根据驱动层请求的操作，通过服务编号来区分处理不同供应商的请求；计算层主要负责对不同的任务进行计算，同时还能够进行查询以及分析等相关工作；存储层主要通过分布式储存、集中式管理的方式，对供应商数据进行存储[4].

图1 基于Spark的联机分析处理结构图Fig.1 Structure diagram of online analytical processing based on Spark

在联机分析处理系统中，不同层次均对应一种供应商网络结构特征，这些特征具有统一维度，因此，也可以将不同维度对应的供应商网络结构特征存储为供应商网络结构特征维度表[5].此外，在实际应用过程中，结合Spark内存计算框架的主要特征和组成结构，需要进一步减少结构特征在供应商网络间的传输数量[6]，并且还需要再次对供应商网络结构特征进行处理，最终将处理结果和结构特征对应的信息进行存储，有效增加联机分析的速度.

为了加快联机分析处理系统对供应商网络不同结构特征的处理速度，需要优先对结构特征进行二次处理，并且只对相关供应商网络特征属性进行编码.其中，供应商网络特征属性编码Di计算表达式为

(1)

式中：Li为混合编码；h为组成成员数量.

根据供应商网络不同结构特征的编码处理结果，在全维度表中提取相关的结构特征信息，并且删除无价值的供应商网络信息.

在联机分析处理过程中，不仅需要注重细节的处理，同时还需要特别注重供应商网络结构特征维度表的外键[7].具体注意事项如下：

1) 当系统读取事实表时，需要避免无价值的供应商网络结构属性读入到系统中，有效降低联机分析计算量.

2) 主要借助连接标的中间操作结果，分析不同供应商网络用户的查询以及使用习惯，同时还可以避免系统出现重复查询的情况.

在Spark框架中，需要优先预处理供应商网络结构数据包，并将对应的供应商网络关联信息同时存储到RDD中.另外，需要在已有数据读取方式的基础上，进行全新数据结构[8]设计.

对不同用户使用系统的行为与方位次数等进行统计，同时结合Spark特性[9]，将冗余供应商网络结构特征删除，并且将含有新层次的维度编码进行转换，为后续查询奠定基础.通过Spark的RDD缓存机制[10]，优先对系统内的供应商网络结构特征进行缓存处理，确保供应商网络结构特征的查询速度.基于Spark的供应商网络结构特征联机分析处理操作流程如图2所示.

图2 联机分析处理流程图Fig.2 Flow chart of online analytical processing

1.2 多维层次聚集分析

本研究通过位图连接索引[11]实现对供应商网络结构特征的多维层次聚集处理.位图连接索引是在传统索引基础上发展起来的，通过位图连接索引能够有效降低维表与事实表两者的连接时间，确保聚集操作的有效性.在供应商网络数据仓库中，将n个维度的数据分别表示为d1，d2，…，dn，其中，两个或者两个以上的位图连接索引需要适当执行“与”、“或”操作.位图连接索引对应两种情况，一种是元组织标识对应的事实表元组包含维表主码值；另一种是元组织标识对应的事实表元组不包含维表主码值.

所提出的供应商网络结构特征多维层次聚集算法整体思路如下：

1) 通过转换供应商网络不同维度层次中各个维度的约束条件形成待聚集区域，并将满足约束条件的属性放置到对应的文件夹中；

2) 根据分组属性排序结果集；

3) 通过位图连接索引，得到供应商网络不同分组的位图；

4) 通过各个分组在位图中的位置，选取对应的事实表记录，同时借助期望聚集函数进行计算.

算法具体运行流程如下：

1) 算法初始化，设置相应的参数；

2) 分析不同的参数查询条件，通过结合对应的编码文件，即可获取各个字段对应的联合代理编码；

3) 根据编码所在位置，将其插入到对应的临时表中；

4) 针对查询结果的分组属性，通过Kary合并算法对排序临时表进行分组处理；

5) 确定供应商网络分组组数；

6) 通过位图索引对各个数组中的全部记录进行“或”操作，进而获取各个分组对应的位图；

7) 根据分组属性An对应的分组值和位图mn构建元组(An，mn)，并将其存储到对应的临时列表中；

8) 通过PsJoin连接算法对临时表中的分组属性进行连接，删除无价值的元组，得到全新的列表；

9) 通过各个分组在位图中的记录，借助期望函数对其进行计算，同时将结构插入到聚集度量表中；

10) 删除无价值的临时供应商网络结构特征维度表[12].

由于维度表中存在的供应商网络结构特征较少，所提算法是通过分组属性对满足条件的元组进行分组，因此需要将各个分组的供应商网络结构特征放置到对应的维度表中.

分析联合代理需求，将满足条件的元组放置到临时表中，对应的开销计算表达式为

(2)

式中：B为网络结构特征元数量；Xn为多维度表中参与连接的操作维记录数量；Yn-τ为供应商网络结构特征度；Xn-2τ为临时表中参与连接的维数记录量.

对临时表中的全部供应商网络结构特征进行分组排列，则该部分对应的开销表达式为

(3)

式中：e为用来排序的供应量网络结构特征数量；k为网络结构特征对应组别数量.

通过位图连接索引，计算对应分组的位图，则该部分的开销计算表达式为

(4)

式中，f为事实表的记录总数.

在上述分析的基础上，结合不同的开销，利用层次联合代理与预先分组排序的方式，将供应商网络结构特征的聚集操作转换为区域查询，同时借助位图中对应的访问事实表，对全部供应商网络结构特征进行多维层次聚集，得到聚集结果Z，其计算表达式为

(5)

式中：j为供应商网络结构特征总维数；p为连接参与网络维数.

2 仿真实验

为了验证所设计供应商网络结构特征多维层次聚集算法的有效性，本文设计了仿真实验.选择本市某大型电商企业的供应商网络运行数据作为本次实验的数据.元组数据为4万条，数据量为101 GB，供应商网络覆盖率为0.93，供应商网络结构特征多维传输过程延时为1.5 ms.同时将文献[2]、[3]方法作为对比方法，对多维层次聚集效率与供应商网络中无效节点的判断性能进行对比测试.

2.1 多维层次聚集效率测试

为验证本文方法的聚集效率，实验以聚集响应时间和聚集过程耗时作为测试指标.两项测试指标的取值越低，则说明供应商网络结构特征多维层次聚集效率越高.3种算法的实验对比结果如图3所示.

由图3的实验数据可知，随着元组数量的增加，不同方法对多维层次聚集的耗时与响应时间也在增加.通过图3a可知，文献[2]方法的聚集响应时间在15～28 ms之间，文献[3]方法的聚集响应时间在17～25 ms之间，而本文提出方法的聚集响应时间在13～23 ms之间，本文方法与另两种方法的聚集响应时间相比最短.通过图3b可知，文献[2]方法的聚集耗时在73～100 ms之间，文献[3]方法的聚集耗时在90～100 ms之间，而本文提出方法的聚集耗时在70～92 ms之间，本文方法与另两种方法的聚集耗时相比也同样最短.

图3 多维层次聚集效率测试结果Fig.3 Test results of multi-dimensional hierarchical aggregation efficiency

2.2 网络无效节点的判断性能测试

为了证明本文提出方法的使用性能，对供应商网络中无效节点的判断性能进行实验测试.以文献[2]方法和文献[3]方法为对比方法，以电商供应商网络运行数据为实验对象，重点测试不同方法的聚集性能.在实验数据中包含4个事实表和1个维表.事实表是用来记录商务事实和相关统计指标的结果表；维表是用户分析决策的角度展示.实验设置元组数据数量为4万条，无效节点数量最多为300个，按照不同节点数量档位，对不同方法的判断能力进行测试，测试结果如表1所示.

表1 对供应商网络中无效节点的判断性能测试结果Tab.1 Judgment and performance test results of invalid nodes in supplier network

分析表1数据可知，文献[2]方法无效节点的判断率在84%～95%之间，文献[3]方法无效节点的判断率在90%～96.8%之间，而本文方法无效节点的判断率始终保持在98%以上，高于两种对比文献方法.在无效节点数量少于150个时，本文方法能够准确判断出所有的无效节点；在无效节点数量多于150个时，也基本能够判断出绝大部分的无效节点，判断率为98%，判断性能更优.实验结果证明，本文方法能够更有效地筛选出供应商网络中有效的节点，从而令有效供应商节点的特征能够被识别，从根本上提高多维层次聚集效果.

3 结 论

针对传统供应商网络结构特征存在的一系列问题，文章提出一种供应商网络结构特征多维层次聚集算法.将价值属性读入到系统内存中，有效降低计算量和内存压力.根据系统需要优先对维度层次进行二次编码处理，得到相关属性编码，根据数据列存储思想，将对应的关联信息和细节信息同时存储到RDD中.实验测试结果表明，所提算法能够有效提升聚集效率，且有效提高了对供应商网络中无效节点的判断性能，能够更好实现供应商网络结构特征多维层次聚集.