基于频集的Apriori关联规则算法在招标采购活动中的应用

汤 骏

（南通市公共资源交易中心，江苏 南通 226001）

0 引 言

目前，我国政府投资项目主要通过公开招投标方式确定合格承包商（供应商）。由于种种原因，招标采购活动还存在诸多亟待解决的难题，例如采购需求设置不合理、不公平，评审组织工作不规范、评审结论不科学，打击招投标违法犯罪行为手段有限、效率不高,等等。随着我国招标采购过程电子化的推进，这些不合规现象逐渐被伴随产生的数据“证据”锚定和记录了下来，但这些宝贵的数据资源一直处于“沉睡”或者“休眠”状态，未能有效利用。究其原因，一方面，多数招标采购交易平台建立初期缺乏数据结构化、标准化意识，导致数据信息严重碎片化、断裂化、冗余化，常规的技术手段难以有效挖掘、整理、利用；另一方面，招标采购数据间“隐变量”和“不定量”较多，加之相互干扰，其内在逻辑关系隐藏较深，很难科学、可信、直观解读。随着信息技术的发展，人工智能、大数据、云计算技术的大力推广，如何通过技术手段，有效挖掘数据背后隐藏的真相，探寻信息表象迷雾下的内在规律，成为招标采购管理部门亟待研究的课题，也取得了一些成果。但智能交易领域最后也是最难攻克的堡垒——智能评审（也称“无人评审”），还鲜有成功案例，用计算机彻底取代人类评委实现“精准秒评”，仍停留在研究探索阶段。鉴于此，基于“循例评审”原理，笔者提出一种结合Apriori关联规则算法的“计算机智能评审”方案，探讨关联规则算法在招标采购活动中的应用实践。

1 关联规则算法概述

关联规则分析（association rule analysis）也称购物篮分析（market basket analysis），最早是为发现超市销售数据中不同商品之间的关联关系而建立的。例如，美国的沃尔玛超市发现，啤酒与尿布两种看似风马牛不相及的商品，销售额竟然呈正相关。究其原因，美国的男人们在为小孩买尿布时，常常顺便带回他们喜欢的啤酒，这背后蕴含的就是关联规则。应用关联规则进行关联分析，能够发现存在于大量无序数据集间的相关性，从而通过客观描述事件中特定属性同时出现的概率分布，得出看似“不相关现象”之间的内在关联。

关联规则挖掘技术已在商业营销、金融服务、天气预测、交通管理等行业广泛应用，显示出强大的生命力。在公共资源交易领域，海量的交易数据之间存在深度和广泛的“隐性关联”关系，恰当运用关联规则技术可发现许多隐藏在数据表象之下有价值的信息。

1.1 Apriori算法原理

常用的关联规则算法有FP-growth、DHP、Partition、FUP、CD算法等。其中，Apriori算法目前应用最广泛，是一种以挖掘布尔关联规则为目标的算法，是挖掘频繁项集和关联规则的经典算法。Apriori的本意是“来自以前”，即使用先验知识或者假设。Apriori算法的主要思想是：找出数据集中最大的频繁项集，利用得到的最大频繁项集与预先设定的最小置信度阈值生成强关联规则，再通过逐层搜索方式进行反复迭代完成算法过程。

1.2 Apriori算法工作流程

Apriori算法主要流程是，先通过连接产生候选集，再进行支持度计算，最终通过剪枝生成频繁项集。具体流程如下：

（1）已知数据集合D，支持度阈值α，找出最大的频繁项集k。

（2）扫描数据集合D，罗列所有可能的数据集合，作为候选频繁项集1（k=1，频繁项集0为空集）。

（3）筛选频繁项集k。

1）扫描数据集合D，计算候选频繁k项集的支持度。

2）去除候选频繁k项集里支持度低于阈值α的数据集（剪枝过程），得到频繁项集k。如得到的频繁项集k为空，则直接返回，频繁项集k-1的集合为算法结果，算法终止。

3）基于频繁k项集，连接生成候选频繁k+1项集（连接过程）。令k=k+1，转入步骤2），直至计算的支持度高于阈值α，此时得到的项集即为频繁项集，算法终止。

从上述工作流程可看出，Apriori算法每一次迭代都要遍历整个数据集，当数据集量级庞大、数据种类较多时，计算效率较低。为此，计算机科学家提出了FP-growth、GSP、CBA等改进计算效率的新算法。但是，Apriori算法易于编码实现，在当今分布式计算引擎技术支持下，牺牲一定的时间和算力资源开销是可以接受的。

1.3 Apriori算法的评价指标

Apriori算法计算频繁项集的评价指标主要有三个：支持度、置信度和提升度。

（1）支持度（Support）是指全部事务中，项集中{X，Y}同时出现的概率，该指标通过最小阈值（Minsup）的设定，剔除那些“出现概率”较低的无意义的规则。

（2）置信度（Confidence）是指在关联规则的先决条件X发生的情况下，关联结果Y发生的概率，即含有X的项集条件下，同时含有Y的可能性，也就是X和Y同时发生的个数占仅仅X发生个数的比例。

（3）提升度（Lift）是指在含有X的条件下同时含有Y的可能性与无条件下含有Y的可能性之比，即在Y自身出现的可能性P（Y）的基础上，X出现对于Y“出现概率”的提升程度。

恰当地选用和计算这三个评价指标，有利于判断Apriori算法的有效性。

2 Apriori关联规则算法在招标采购活动中的应用实践

2.1 算法处理流程与应用场景

近年来，不少学者利用复杂网络和关联规则算法在招标采购活动中取得了一些研究成果。汪浩然、陈辉基于关联规则挖掘技术，构建了招标投标失信行为预警分析模型，实现了对各类主体的失信行为分类预警的目的[1]；樊群、殷静等借助大数据技术建立了基于复杂网络的社团检测模型和多目标群智能关联规则挖掘模型，刻画出围标串标的交易轨迹和行为特点，为监管部门建立围标串标防御机制提供了技术支撑[2]。

其实，基于频集的Apriori关联规则算法在招标采购活动中的应用远不止这些。凡涉及频度相关的数据集，均可建立关联规则数学模型，再通过支持度、置信度和提升度等评价指标予以进一步校正，最终得出有价值的结论[3]。

Apriori关联规则算法处理的工作流程如图1所示。表1则列举了基于频集的Apriori关联规则算法在招标采购活动中的一些主要的应用场景。

表1 Apriori关联规则算法在招标采购活动中的应用场景

图1 Apriori关联规则算法的处理流程

2.2 关联法则在“智能评审”中的应用案例

2.2.1 基于“循例评审”的“智能评审”原理

简单来说，“循例评审”的基本思想是假定待评审项目与先前已评审项目的主要特征、招标邀约条件、投标项目响应程度相同，则可将先前项目的评审结论作为待评审项目的评审结论。也就是说，招标的外部条件和投标的内部条件没有大的变化，其评审结论应当可以“参考先例”，而“先例”的确定主要通过Apriori关联规则算法来实现。

根据“循例评审”的基本思想，问题就转化为要找到交易数据中“项目主要特征”“招标邀约条件”“投标响应程度”和“评审结论”等因素的频集，再通过支持度、置信度和提升度等评价指标判断新旧项目之间的关联关系。符合“强关联”预期的，则达到了“旧结论”代替“新评审”的目的，即实现计算机智能评审，其实质是基于Apriori关联规则的机器学习算法实现。

2.2.2 Apriori算法实现“智能评审”的过程

（1）建立招标项目特征指标集合

我国建筑行业招投标在设置招标邀约条件时有严格的制度规范，必须遵循《招标投标法》、《招投标实施条例》、《建筑工程施工总承包企业资质等级标准》（以下简称《标准》）、《注册建造师执业管理办法》（以下简称《办法》）等文件规定。建筑工程施工总承包资质分为特级、一级、二级、三级，项目负责人资格等级分为一级、二级，招标人主要根据建筑高度、建筑面积和单跨跨度等项目特征指标和上述有关规定来设置招标邀约条件。

由此建立项目特征指标集合，即P={p1，p2，p3，p4}。其中：P为项目特征指标频集，p1为建筑高度，p2为建筑面积，p3为单跨跨度，p4为工程预算造价。项目特征指标集合的取值依据及取值范围列于表2。

表2 招标项目特征指标数据集

（2）建立招标邀约条件指标集合

同理，建立招标邀约条件指标集合，即Q={q1，q2，q3，q4，q5，q6}，式中：Q为招标邀约条件指标集合，q1为企业资质等级，q2为项目负责人资格等级，q3为企业业绩，q4为项目负责人业绩，q5为评标办法，q6为企业获奖情况。招标邀约条件指标集合的取值依据及取值范围列于表3。

表3 招标邀约条件指标数据集

（3）建立投标响应程度指标集合

投标响应程度指标主要涉及投标企业资质等级、业绩、项目负责人资格等级等指标，即R={r1，r2，r3，r4，r5，r6，r7，r8}。其中：R为投标响应程度指标，r1为投标企业资质等级，r2为项目负责人资格等级，r3为投标企业业绩，r4为投标企业获奖情况，r5为投标项目负责人业绩，r6为其他资格审查材料，r7为技术标函，r8为商务报价标函。投标响应程度指标集合取值依据与取值范围列于表4。

（4）利用Apriori算法进行频集计算

招标项目特征指标、招标邀约条件指标和投标响应程度指标分别建立完成后，就可配对组合，再设置阈值并进行频集计算。配对方法是分别建立“项目特征与招标邀约条件组合”“招标邀约条件与投标响应程度组合”等对应关联组合。按照Apriori算法规则计算得到频集组合结果如表5、表6所示。

从排列组合的角度来看，最彻底的方式是历遍所有“项目特征—招标邀约条件—投标响应程度”的组合情况，然后依次统计各种组合出现的频率。但是，由于三个组合共有51种指标（其中项目特征指标14个，招标邀约条件指标15个，投标响应程度指标22个），那么组合的数量较为巨大。从表5、表6的招标采购实践来看，2018—2020年期间，“项目特征—招标邀约条件—投标响应程度”组合数只有12种，且三者之间存在强关联关系。也就是说即使是不同的组合之间，差别也较为微小，如T6与T7之间，在招标邀约条件设置中，就是奖项等级的差别（T6要求省级奖项，T7则要求市级奖项）。同理，S6与S7之间在涉及投标响应程度方面，也仅存在提供奖项的差别而已。

表5 项目特征与招标邀约条件频集结果

表6 招标邀约条件与投标响应程度频集结果

（5）评审结果的“循例获取”

表5、表6计算的频集组合约有12种，这12种组合就是过去三年来招标采购频度最高、最常见的评标本构模型（本构模型本为描述应力张量与应变张量的力学概念，这里用于表示采购频度与得分间的一一对应关系）。统计12种组合下的评标结果，建立“投标企业评标得分—频集组合”一一对应的样本数据库，就能为待评审项目提供直接得分的参考依据。

以房屋建筑工程施工总承包招标项目为例，从南通市来看，参加房建项目投标单位一般不超过70家，招标人的项目特征与邀约条件组合数为12种，投标人的投标响应程度组合一般也不超过12种。即便是在同样的项目特征与招标邀约条件组合约束下，同一个投标企业在投标文件编制方面也有一定的差异（主要是施工组织设计部分表述方面的微小差异），即投标文件文本并非一成不变，存在3~4种随机组合，这是完全可以理解的。对于企业而言，即便是同一类型的项目，基于投标策略的考虑和不同的投标文件制作者的技术、水平的差异，不会一直照搬原有的投标文件“模板”。在此前提下，房建工程项目投标企业得分样本总数大约是40320种（40320=70×12×12×4）即理论上至少要对40 320份投标文件进行“样本标定”评审，最终才可形成企业得分样本数据库。当然，由于不同的项目特征与招标邀约条件组合之间、招标邀约条件与投标响应程度组合之间差别本就不大，实际评审工作量不是累积计算关系，而是差别修正关系。

例如，某企业曾在2019年5月参与南通市某大楼房屋建筑工程施工总承包招标，其招标邀约条件与投标响应程度满足S8组合条件（T8，r12，r21，r31，R6，R7，R8），当时的技术方案得分是86分。2020年6月，该企业参与海安市某大厦建筑工程承包招标，其招标邀约条件与投标响应组合条件为S6。根据Apriori算法进行第一次迭代、第二次迭代并连续进行剪枝，得到最终的频繁项集S9（T9，r12，r21，r31，R6，R7，R8）。比较S9和S8差别在于T9置换了T8（也就是用q12替换p11），比较两者招标文件中评标办法规定，分值校正为2分。因此，本次投标得分为84分（商务得分因为报价差异，一般应当重新计算并校正）。

3 结 语

现象的背后有真相，真相的背后是规律。随着法律法规的日益完善，我国的招标采购管理正迈入法制化、规范化进程。但是，不可否认，招投标市场依然存在诸多不正常现象。比如：少数企业盘踞市场，长期高频中标；有的评委针对特定企业持续给出异常分值，明显有违正态分布规律；一些行业的投标企业总是“老几家”，他们“伴随出现”“抱团投标”，外来企业难以参与有效竞争；等等。这些现象可以直观地被感知，但是难以转化为法律可以采信的证据链。正所谓“频度过高、必有蹊跷”。这就需要招标采购行业的管理者借助信息化手段，通过数据挖掘、模型建立和趋势推演，去解析这些“看似明显违规、实际难以固定”的数据表象下隐含的规律。基于频集的Apriori关联规则算法是科学解释这些异常现象的有力武器，将其合理应用于招标采购活动中，必将为营造健康有序的招标采购环境发挥积极作用。