王鵬 皮水江

關(guān)鍵詞： 大數(shù)據(jù); 最優(yōu)選取算法; 招標方案; 大數(shù)據(jù)處理; 聚類; 投影尋蹤模型

中圖分類號： TN919?34; TV511 ? ? ? ? ? ? ? ? 文獻標識碼： A ? ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）04?0105?04

Optimal bidding scheme selection algorithm based on big data

WANG Peng， PI Shuijiang

（Chongqing University of Technology， Chongqing 400054， China）

Abstract： The traditional bidding scheme selection algorithm makes the optimal bidding scheme selection by establishing the index attribute matrix and intuitive fuzzy linear evaluation model， and does not consider the timing of big data processing， resulting in low efficiency and poor accuracy of the selected results. Therefore， an optimal bidding scheme selection algorithm based on big data is put forward. All the bidding schemes are clustered. The big data processing process of bidding schemes is accelerated by means of big data sampling. The Single method is selected to cluster the results of big data sampling， so as to determine the centroid orientation for the natural cluster of big data. The mean value updating method is adopted to modify the centroid orientation for the natural cluster of big data， so as to determine the actual centroid orientation for the natural cluster of big data. On this basis， the classification and clustering of the bidding schemes are conducted. The projection tracing model is constructed to select the optimal bidding scheme. The experimental results show that the proposed algorithm has a clustering error of less than 7%， accuracy of as high as 93%， and a great advantage in computing speed.

Keywords： big data; optimal selection algorithm; bidding scheme; big data processing; clustering; projection tracing model

0 ?引 ?言

招標工作中，管理者需要對大量的招標文件實施排序，選取最優(yōu)招標方案[1]。而最優(yōu)招標方案會受到投標公司經(jīng)濟、技術(shù)以及環(huán)境等多方面的影響，是一個較為復雜的問題[2]。最優(yōu)招標方案選取是工程建設的基礎，對工程建設計劃的圓滿實現(xiàn)具有重要意義，因此，如何有效、快速、準確地選取最優(yōu)招標方案一直是眾多公司關(guān)注的重點。

文獻[3]采用大數(shù)據(jù)分析方法進行資源數(shù)據(jù)庫的信息融合和優(yōu)化訪問設計，結(jié)合自適應均衡博弈和灰色關(guān)聯(lián)度分析，得到方案選取的綜合決策模型，該模型每次迭代都需要進行節(jié)點間通信，效率較低。文獻[4]通過建立指標屬性矩陣和直覺模糊線性評價模型進行最優(yōu)招標方案選取，其沒有考慮大數(shù)據(jù)處理上的時間性，選取結(jié)果效率低、準確性差。文獻[5]基于模糊綜合分析和Gale?shapley理論提出了一個二階段的招投標優(yōu)化策略，該策略需要選取大量的代表點，耗時長、穩(wěn)定性較差。針對上述情況，提出基于大數(shù)據(jù)的最優(yōu)招標方案選取算法，對全部招標方案進行聚類，通過抽樣加快對招標方案大數(shù)據(jù)的處理;根據(jù)招標方案聚類結(jié)果，構(gòu)建投影尋蹤模型實現(xiàn)最優(yōu)招標方案的選取。

1 ?基于大數(shù)據(jù)的最優(yōu)招標方案選取算法

1.1 ?招標大數(shù)據(jù)聚類

1.1.1 ?大數(shù)據(jù)抽樣

為了加快對大數(shù)據(jù)集的聚類分析，通常會采用抽樣的處理方式[6]。在對招標方案進行抽樣時，抽取出的小方案集應與大方案集保持一致，即均涵蓋全部自然簇，則大數(shù)據(jù)樣本[s]可用下式進行獲?。?/p>

[s=f×n+nni×log1δ+ ? ? nnilog1δ2+2×f×ni×log1δ] ?（1）

式中，[f]，[n]，[ni]和[δ]分別表示抽取到指定招標方案的比例、招標方案量、簇[Ci]的范疇以及概率，其中，[0≤f≤1]。式（1）主要表示的是在簇[Ci]內(nèi)，根據(jù)[1-δ]（[0≤δ≤1]）的概率抽取[f×ni]以上個方案所組成的大數(shù)據(jù)樣本[s]的規(guī)模。

假設[n=100 000]，[ni=1 000]，[δ=0.2]，[f=0.1]，則方案簇[Ci]中抽取的樣本方案集[s]規(guī)模為11 962;假設[n=100 000]，與[δ=0.2]不變，[f=0.05]，[ni=50]，則方案簇[Ci]中抽取的樣本方案集[s]規(guī)模為6 440。

在全部招標方案中，簇[Ci]所占比例較小，只占1%。一般情況下，同一個工程的招標方案類別不會超過10%，若簇[Ci]的大小滿足10%，則可以通過更小規(guī)模的抽樣達到目的;如果[f]值較小，則抽樣同樣可更小。

為了方便聚類，本文對由全部招標方案組成的、大小為[n]的方案集[D]實施規(guī)模一致的[M]次大數(shù)據(jù)抽樣。將大數(shù)據(jù)抽取的方案樣本集[Di]的大小設定為[ni]。實施大數(shù)據(jù)抽樣操作需遵守以下條件：

[Di∩Dj=?ni=njni×M?n] ? （2）

同時，不同大數(shù)據(jù)抽樣之間不存在關(guān)聯(lián)。式中，[i=1，2，…，M]，[i≠j]，[M∈Z]。

1.1.2 ?確定大數(shù)據(jù)自然簇質(zhì)心方位

1） 對大數(shù)據(jù)抽樣進行聚類

假設由全部招標方案構(gòu)成的方案集包含[k]個類別，方案集的一個抽樣包含[k′]個類別，并且[1≤k′<k]，對此類抽樣進行聚類操作，構(gòu)成[k]個小簇，那么其中的一個簇將被分裂。對大數(shù)據(jù)抽樣進行聚類時選用Single方法[7]。采用歐氏距離對比招標方案間的雷同度，其運算過程如下：

[dis=xi-xj2] ? （3）

式中，[xi]，[xj]分別表示大數(shù)據(jù)特征空間內(nèi)數(shù)據(jù)點的坐標。

各招標方案抽樣的聚類大小一致，由于對招標方案抽樣實施聚類操作時均是單獨操作，因此招標方案的[M]個大數(shù)據(jù)抽樣能夠進行聚類處理。在對運行時間無指定要求的情況下，不同招標方案大數(shù)據(jù)抽樣進行聚類操作時可同時進行串行處理。

2） 重整大數(shù)據(jù)抽樣聚類結(jié)果

對全部抽樣實施聚類操作，可以得到[k×M]個小簇。對各小簇的均值進行運算，公式為：

[xi=1nij=1nixij] ?（4）

式中，[xi]，[ni]，[xij]分別表示簇[Ci]的數(shù)據(jù)屬性均值、數(shù)據(jù)規(guī)模以及[Ci]內(nèi)某一個樣本的屬性。

簇[Ci]通過均值能夠獲取新方案集[A]，該方案集的大小用[k×M]描述。通過Single法對新方案集[A]實施聚類操作，能夠得到[k]個簇，即以[k]個大簇替代[k×M]個小簇。通過對該[k]個大簇均值的運算能夠獲取自然簇質(zhì)心的方位。

1.1.3 ?均值更新與大數(shù)據(jù)聚類

由于第1.1.2節(jié)的運算中對方案集[D]的應用并不全面，所以獲取的大數(shù)據(jù)自然簇質(zhì)心的方位與大數(shù)據(jù)自然簇質(zhì)心的實質(zhì)方位必然會存在一定的差距[8]。因此需對大數(shù)據(jù)自然簇質(zhì)心的方位實施修改以確定大數(shù)據(jù)自然簇質(zhì)心的實質(zhì)方位。

對比[k]個初始質(zhì)心的距離，根據(jù)最小距離的分類原則，能夠?qū)⒄袠朔桨竅D]內(nèi)剩余的方案樣本全部分類到距離最小的簇內(nèi)。最小距離的分類原則為：

[c=argmaxi-xΔ-xi2] ?（5）

式中，[xi]，[xΔ]和[c]分別表示簇[Ci]數(shù)據(jù)屬性的均值、未確定類別的樣本屬性以及已確定的類別。

依照大數(shù)據(jù)自然簇質(zhì)心的實質(zhì)方位對招標方案集實施劃分聚類時，在無指定條件的情況下，通過式（5）中所描述的最小距離的分類原則，按照招標方案與簇質(zhì)心的距離進行招標大數(shù)據(jù)聚類。

1.2 ?最優(yōu)招標方案的選取

通過上述過程實現(xiàn)招標大數(shù)據(jù)的聚類后，再用投影尋蹤方法[9]進行最優(yōu)招標方案的選取，詳細操作過程如下：

設定招標方案聚類后投影尋蹤問題的多指標樣本集為：

[ei，ji=1，2，…，m;j=1，2，…，n] ? ?（6）

式中，[m]和[n]分別表示大數(shù)據(jù)樣本數(shù)量和指標數(shù)量。

構(gòu)建投影尋蹤模型：

1） 數(shù)據(jù)預處理。針對越大越優(yōu)的指標和越小越優(yōu)的指標，分別應用[e?i，j=ei，jemaxj]和[e′i，j=1-ei，jemaxj]處理。其中，[emaxj]表示第[j]個指標的最大值。

2） 構(gòu)造投影指標函數(shù)。為獲取投影方向優(yōu)化的規(guī)則，構(gòu)建投影指標函數(shù)[Qa]，在指標為極大值的情況下，獲取最優(yōu)投影方向。投影指標函數(shù)為：

[Qa=Sz×Dz] ? （7）

式中：[Sz]表示類間散開度，等同于[Zi]的標準差，通過式（8）的運算能夠得到;[Dz]表示類內(nèi)密集度，等同于[Zi]的局部密度，通過式（9）的運算能夠得到。

[Sz=i=1mZi-Z2m-112] （8）

[Dz=i=1mj=1mR-rij×IR-rij] （9）

式中：[Z]，[R]和[rij]分別表示序列[Zi， i=1，2，…，m]的均值、通過招標方案特征獲取的局部寬度參數(shù)以及點間距。一般情況下，局部寬度參數(shù)為[0.1×Sz]，[rij=Zi-Zj]。若[rij]不大于[R]，則按照類內(nèi)計算，相反則按照差異類計算;[IR-rij]為單位階躍函數(shù)，若[R≥rij]，則函數(shù)值為1，相反為0。

3） 確定最優(yōu)投影方向。對下述的優(yōu)化模型進行求解運算可以獲取最優(yōu)投影方向，優(yōu)化模型的目標函數(shù)如下：

[max Qa=maxSz×Dz] （10）

2 ?實驗分析

實驗以某項水利工程的招標為例[10]，詳細的參考評價指標如表1所示。

為了驗證本文提出的基于大數(shù)據(jù)的最優(yōu)招標方案選取算法的速度優(yōu)勢，分別使用本文算法、基于OSCK的最優(yōu)招標方案選取算法和基于直覺模糊集的最優(yōu)招標方案選取算法對不同規(guī)模的招標方案進行最優(yōu)選取，記錄不同算法使用的時間并進行對比，結(jié)果如圖1所示。

對圖1進行分析可知，在數(shù)據(jù)量未達到100 MB時，三種不同算法所需的時間差距較小，均未超過5 s。然而隨著數(shù)據(jù)量的不斷增大，本文算法的速度優(yōu)勢逐漸體現(xiàn)出來，當數(shù)據(jù)量達到2 048 MB時，使用本文算法進行最優(yōu)招標方案選取花費8.27 s;使用基于OSCK的最優(yōu)招標方案選取算法花費17.95 s;使用基于直覺模糊集的最優(yōu)招標方案選取算法花費22.32 s。實驗結(jié)果表明，使用本文算法進行最優(yōu)招標方案選取耗時較短，具有一定的速度優(yōu)勢。實驗為了測試本文算法的聚類效果，分別使用本文算法、基于OSCK的最優(yōu)招標方案選取算法和基于直覺模糊集的最優(yōu)招標方案選取算法對表1中的招標工程進行聚類，得到的誤差結(jié)果如圖2所示。

對圖2進行分析能夠得到，使用不同算法進行最優(yōu)招標方案選取時，在數(shù)據(jù)規(guī)模未超過300 MB時，三種算法的聚類效果相差較小，誤差均未達到4%。隨著數(shù)據(jù)規(guī)模的不斷擴大，三種算法之間的聚類誤差也逐漸加大，當數(shù)據(jù)規(guī)模達到2 048 MB時，本文算法的聚類誤差接近7%，聚類效果最優(yōu);基于OSCK的最優(yōu)招標方案選取算法的聚類誤差接近10%，聚類效果次之;基于直覺模糊集的最優(yōu)招標方案選取算法的聚類誤差接近12%，聚類效果誤差最大。實驗結(jié)果表明，使用本文算法進行最優(yōu)招標方案選取時對招標方案的聚類效果最佳。

實驗為了驗證本文算法在處理大數(shù)據(jù)集時的準確性，分別使用本文算法、基于OSCK的最優(yōu)招標方案選取算法和基于直覺模糊集的最優(yōu)招標方案選取算法進行100次的最優(yōu)招標方案選取試驗，對比不同算法的準確度，如圖3所示。

分析圖3可知，使用三種不同算法進行實驗時，隨著實驗次數(shù)的增加，三種算法的準確率都在逐漸下降，然而與其他兩種算法相比，本文算法準確率下降較平緩。當實驗次數(shù)達到100次時，本文算法準確率維持在93%，基于OSCK的最優(yōu)招標方案選取算法的準確率為80%，基于直覺模糊集的最優(yōu)招標方案選取算法的準確率為76%。實驗結(jié)果表明，使用本文算法進行最優(yōu)招標方案選取時的準確率較高，穩(wěn)定性較好。

3 ?結(jié) ?論

本文提出基于大數(shù)據(jù)的最優(yōu)招標方案選取算法，對招標方案進行大數(shù)據(jù)聚類，根據(jù)大數(shù)據(jù)聚類結(jié)果構(gòu)建投影尋蹤模型實現(xiàn)最優(yōu)招標方案的選取。在聚類過程中，通過大數(shù)據(jù)抽樣加快對招標方案大數(shù)據(jù)處理進程，解決了傳統(tǒng)最優(yōu)招標方案選取算法進行大數(shù)據(jù)處理過程中存在的效率低、穩(wěn)定性差等問題。實驗結(jié)果表明本文算法具有速度快，準確率高等優(yōu)點。

參考文獻

[1] 曹陽，錢曉東.基于局部關(guān)鍵節(jié)點的大數(shù)據(jù)聚類算法[J].計算機工程與科學，2016，38（7）：1338?1343.

CAO Yang， QIAN Xiaodong. A big data clustering algorithm based on local key nodes [J]. Computer engineering & science， 2016， 38（7）： 1338?1343.

[2] 李曉峰.云平臺中大數(shù)據(jù)并行聚類方法優(yōu)化研究仿真[J].計算機仿真，2016，33（7）：327?330.

LI Xiaofeng. Optimization and simulation research on parallel clustering method of big data in cloud platform [J]. Computer simulation， 2016， 33（7）： 327?330.

[3] 史金梅，夏偉.基于大數(shù)據(jù)分析的學生最優(yōu)選課方案模型的設計與實現(xiàn)[J].現(xiàn)代電子技術(shù)，2017，40（14）：30?32.

SHI Jinmei， XIA Wei. Design and implementation of student′s most preferred course project model based on big data analysis [J]. Modern electronics technique， 2017， 40（14）： 30?32.

[4] 郭磊，王軍，安曉偉.基于直覺模糊集的水利工程評標辦法[J].南水北調(diào)與水利科技，2016，14（5）：189?193.

GUO Lei， WANG Jun， AN Xiaowei. Bidding evaluation model of water conservancy and hydropower project based on theory of intuitionistic fuzzy set [J]. South?to?north water transfers and water science & technology， 2016， 14（5）： 189?193.

[5] 丁斅，盛昭瀚，劉慧敏.基于模糊綜合分析和Gale?Shaplev理論的重大工程二階段招投標機制研究[J].中國管理科學，2017，25（2）：147?154.

DING Xiao， SHENG Zhaohan， LIU Huimin. A two?stage method for mega projects bidding system based on fuzzy analytic hierarchy process and Gale?Shapley strategy [J]. Chinese journal of management science， 2017， 25（2）： 147?154.

[6] 馬良，馬穎亮，劉新科.基于“招標?投標”策略的艦艇編隊協(xié)同反導優(yōu)化[J].火力與指揮控制，2015，40（5）：95?98.

MA Liang， MA Yingliang， LIU Xinke. Fleet cooperative anti?missile optimization based on strategy of "invite public bidding" [J]. Fire control & command control， 2015， 40（5）： 95?98.

[7] 王應權(quán).長大鐵路隧道施工通風方案選擇及優(yōu)化[J].地下空間與工程學報，2015，11（z1）：359?366.

WANG Yingquan. The selection and optimization of ventilation scheme for long railway tunnel construction [J]. Chinese journal of underground space and engineering， 2015， 11（S1）： 359?366.

[8] LEE S， JIN Y， JANG G， et al. Optimal bidding of a microgrid based on probabilistic analysis of island operation [J]. Energies， 2016， 9（10）： 814.

[9] SADEGHI?MOBARAKEH A， MOHSENIAN?RAD H. Optimal bidding in performance?based regulation markets： an MPEC analysis with system dynamics [J]. IEEE transactions on power systems， 2017， 32（2）： 1282?1292.

[10] 宋俊芳，陳烽，何磊，等.運動目標最優(yōu)角點選擇算法[J].科學技術(shù)與工程，2016，16（12）：113?119.

SONG Junfang， CHEN Feng， HE Lei， et al. A new algorithm for selecting optimal corner point of moving target [J]. Science technology and engineering， 2016， 16（12）： 113?119.