基于頻集的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關聯規則算法是科學解釋這些異常現象的有力武器，將其合理應用于招標采購活動中，必將為營造健康有序的招標采購環境發揮積極作用。