蕭展輝, 唐良運(yùn), 孫 剛
(1. 華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 廣州 510006; 2. 南方電網(wǎng)數(shù)字電網(wǎng)研究院有限公司 平臺(tái)安全分公司數(shù)據(jù)平臺(tái)事業(yè)部(南網(wǎng)大數(shù)據(jù)中心), 廣州 510663)
世界經(jīng)濟(jì)的快速發(fā)展有效地推動(dòng)著企業(yè)的進(jìn)步,新興信息技術(shù)在各個(gè)領(lǐng)域中的滲透,使中國產(chǎn)業(yè)變革的進(jìn)程不斷加快[1].各種供應(yīng)商的資源也逐漸發(fā)展成為企業(yè)競(jìng)爭(zhēng)的核心依據(jù).用戶需求的不斷增加與日益激烈的市場(chǎng)競(jìng)爭(zhēng),促使著企業(yè)供應(yīng)商必須開展相關(guān)的運(yùn)營和產(chǎn)品創(chuàng)新等活動(dòng),因此,有效的管理以及供應(yīng)商網(wǎng)絡(luò)已成為制造業(yè)領(lǐng)域的重點(diǎn)研究?jī)?nèi)容,同時(shí)也是學(xué)術(shù)界研究的熱點(diǎn).李民等[2]針對(duì)供應(yīng)商優(yōu)選決策過程展開研究,對(duì)兩級(jí)供應(yīng)鏈構(gòu)建多代理仿真模型,并驗(yàn)證了多種參數(shù)在供應(yīng)鏈傳播角度產(chǎn)生的影響,發(fā)現(xiàn)供應(yīng)商網(wǎng)絡(luò)中各成員之間的財(cái)務(wù)操作決策是影響供應(yīng)鏈傳播的重要因素之一.但是該方法缺少聚類分析過程,未充分考慮供應(yīng)商網(wǎng)絡(luò)的結(jié)構(gòu)特征,導(dǎo)致其應(yīng)用效果較差.李昌盛等[3]則基于聚類分析過程,提出了一種降低連接和聚集操作的新算法.該算法充分考慮了供應(yīng)商網(wǎng)絡(luò)復(fù)雜、多維層次的特點(diǎn),在原有的位圖連接索引基礎(chǔ)上,采用層次聯(lián)合代理和預(yù)先分組排序的方法,使多維層次上的連接和聚集操作轉(zhuǎn)化成事實(shí)表上的區(qū)域查詢,從而在處理多維層次聚集的同時(shí),提高了網(wǎng)絡(luò)連接和聚集的效率.然而在實(shí)際應(yīng)用中發(fā)現(xiàn),該方法中所提的聚類過程不適應(yīng)特征較多的供應(yīng)鏈網(wǎng)絡(luò).
針對(duì)上述問題,本文提出了一種供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集算法.通過Spark為數(shù)據(jù)集提供支撐,將數(shù)據(jù)存儲(chǔ)到集群機(jī)器內(nèi)存中,通過服務(wù)編號(hào)來區(qū)分不同用戶的請(qǐng)求.利用表連接操作的中間結(jié)果,在降低耗時(shí)的同時(shí),還能夠提升連接操作的利用效率.實(shí)驗(yàn)測(cè)試表明,所提算法能夠有效提升聚集效率,能更好地完成供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集.
供應(yīng)商網(wǎng)絡(luò)具有層級(jí)關(guān)系,不僅包括了制造企業(yè)和各級(jí)供應(yīng)商之間的縱向關(guān)系,還包括了供應(yīng)商和供應(yīng)商之間的橫向關(guān)系.在網(wǎng)絡(luò)結(jié)構(gòu)中,企業(yè)處于核心位置,與網(wǎng)絡(luò)中供應(yīng)商、供應(yīng)商的供應(yīng)商相互聯(lián)系、交織在一起.為了有效增加供應(yīng)商網(wǎng)絡(luò)中的分布式計(jì)算框架利用效率,本文以Spark為數(shù)據(jù)集提供支撐,并將供應(yīng)商網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)到集群機(jī)器內(nèi)存中,聯(lián)機(jī)分析處理結(jié)構(gòu)如圖1所示.
圖1中,應(yīng)用層為供應(yīng)商網(wǎng)絡(luò)的終端用戶提供接口并展示操作結(jié)果,同時(shí)還能夠通過瀏覽器進(jìn)行多維分析查詢和用戶登錄等相關(guān)操作;驅(qū)動(dòng)層主要負(fù)責(zé)處理不同處理器對(duì)應(yīng)的公共程序接口,能夠全面提升供應(yīng)商網(wǎng)絡(luò)的通用性;服務(wù)器層主要負(fù)責(zé)接收處理各供應(yīng)商根據(jù)驅(qū)動(dòng)層請(qǐng)求的操作,通過服務(wù)編號(hào)來區(qū)分處理不同供應(yīng)商的請(qǐng)求;計(jì)算層主要負(fù)責(zé)對(duì)不同的任務(wù)進(jìn)行計(jì)算,同時(shí)還能夠進(jìn)行查詢以及分析等相關(guān)工作;存儲(chǔ)層主要通過分布式儲(chǔ)存、集中式管理的方式,對(duì)供應(yīng)商數(shù)據(jù)進(jìn)行存儲(chǔ)[4].
圖1 基于Spark的聯(lián)機(jī)分析處理結(jié)構(gòu)圖Fig.1 Structure diagram of online analytical processing based on Spark
在聯(lián)機(jī)分析處理系統(tǒng)中,不同層次均對(duì)應(yīng)一種供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征,這些特征具有統(tǒng)一維度,因此,也可以將不同維度對(duì)應(yīng)的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征存儲(chǔ)為供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征維度表[5].此外,在實(shí)際應(yīng)用過程中,結(jié)合Spark內(nèi)存計(jì)算框架的主要特征和組成結(jié)構(gòu),需要進(jìn)一步減少結(jié)構(gòu)特征在供應(yīng)商網(wǎng)絡(luò)間的傳輸數(shù)量[6],并且還需要再次對(duì)供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行處理,最終將處理結(jié)果和結(jié)構(gòu)特征對(duì)應(yīng)的信息進(jìn)行存儲(chǔ),有效增加聯(lián)機(jī)分析的速度.
為了加快聯(lián)機(jī)分析處理系統(tǒng)對(duì)供應(yīng)商網(wǎng)絡(luò)不同結(jié)構(gòu)特征的處理速度,需要優(yōu)先對(duì)結(jié)構(gòu)特征進(jìn)行二次處理,并且只對(duì)相關(guān)供應(yīng)商網(wǎng)絡(luò)特征屬性進(jìn)行編碼.其中,供應(yīng)商網(wǎng)絡(luò)特征屬性編碼Di計(jì)算表達(dá)式為
(1)
式中:Li為混合編碼;h為組成成員數(shù)量.
根據(jù)供應(yīng)商網(wǎng)絡(luò)不同結(jié)構(gòu)特征的編碼處理結(jié)果,在全維度表中提取相關(guān)的結(jié)構(gòu)特征信息,并且刪除無價(jià)值的供應(yīng)商網(wǎng)絡(luò)信息.
在聯(lián)機(jī)分析處理過程中,不僅需要注重細(xì)節(jié)的處理,同時(shí)還需要特別注重供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征維度表的外鍵[7].具體注意事項(xiàng)如下:
1) 當(dāng)系統(tǒng)讀取事實(shí)表時(shí),需要避免無價(jià)值的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)屬性讀入到系統(tǒng)中,有效降低聯(lián)機(jī)分析計(jì)算量.
2) 主要借助連接標(biāo)的中間操作結(jié)果,分析不同供應(yīng)商網(wǎng)絡(luò)用戶的查詢以及使用習(xí)慣,同時(shí)還可以避免系統(tǒng)出現(xiàn)重復(fù)查詢的情況.
在Spark框架中,需要優(yōu)先預(yù)處理供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)包,并將對(duì)應(yīng)的供應(yīng)商網(wǎng)絡(luò)關(guān)聯(lián)信息同時(shí)存儲(chǔ)到RDD中.另外,需要在已有數(shù)據(jù)讀取方式的基礎(chǔ)上,進(jìn)行全新數(shù)據(jù)結(jié)構(gòu)[8]設(shè)計(jì).
對(duì)不同用戶使用系統(tǒng)的行為與方位次數(shù)等進(jìn)行統(tǒng)計(jì),同時(shí)結(jié)合Spark特性[9],將冗余供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征刪除,并且將含有新層次的維度編碼進(jìn)行轉(zhuǎn)換,為后續(xù)查詢奠定基礎(chǔ).通過Spark的RDD緩存機(jī)制[10],優(yōu)先對(duì)系統(tǒng)內(nèi)的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行緩存處理,確保供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征的查詢速度.基于Spark的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征聯(lián)機(jī)分析處理操作流程如圖2所示.
圖2 聯(lián)機(jī)分析處理流程圖Fig.2 Flow chart of online analytical processing
本研究通過位圖連接索引[11]實(shí)現(xiàn)對(duì)供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征的多維層次聚集處理.位圖連接索引是在傳統(tǒng)索引基礎(chǔ)上發(fā)展起來的,通過位圖連接索引能夠有效降低維表與事實(shí)表兩者的連接時(shí)間,確保聚集操作的有效性.在供應(yīng)商網(wǎng)絡(luò)數(shù)據(jù)倉庫中,將n個(gè)維度的數(shù)據(jù)分別表示為d1,d2,…,dn,其中,兩個(gè)或者兩個(gè)以上的位圖連接索引需要適當(dāng)執(zhí)行“與”、“或”操作.位圖連接索引對(duì)應(yīng)兩種情況,一種是元組織標(biāo)識(shí)對(duì)應(yīng)的事實(shí)表元組包含維表主碼值;另一種是元組織標(biāo)識(shí)對(duì)應(yīng)的事實(shí)表元組不包含維表主碼值.
所提出的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集算法整體思路如下:
1) 通過轉(zhuǎn)換供應(yīng)商網(wǎng)絡(luò)不同維度層次中各個(gè)維度的約束條件形成待聚集區(qū)域,并將滿足約束條件的屬性放置到對(duì)應(yīng)的文件夾中;
2) 根據(jù)分組屬性排序結(jié)果集;
3) 通過位圖連接索引,得到供應(yīng)商網(wǎng)絡(luò)不同分組的位圖;
4) 通過各個(gè)分組在位圖中的位置,選取對(duì)應(yīng)的事實(shí)表記錄,同時(shí)借助期望聚集函數(shù)進(jìn)行計(jì)算.
算法具體運(yùn)行流程如下:
1) 算法初始化,設(shè)置相應(yīng)的參數(shù);
2) 分析不同的參數(shù)查詢條件,通過結(jié)合對(duì)應(yīng)的編碼文件,即可獲取各個(gè)字段對(duì)應(yīng)的聯(lián)合代理編碼;
3) 根據(jù)編碼所在位置,將其插入到對(duì)應(yīng)的臨時(shí)表中;
4) 針對(duì)查詢結(jié)果的分組屬性,通過Kary合并算法對(duì)排序臨時(shí)表進(jìn)行分組處理;
5) 確定供應(yīng)商網(wǎng)絡(luò)分組組數(shù);
6) 通過位圖索引對(duì)各個(gè)數(shù)組中的全部記錄進(jìn)行“或”操作,進(jìn)而獲取各個(gè)分組對(duì)應(yīng)的位圖;
7) 根據(jù)分組屬性An對(duì)應(yīng)的分組值和位圖mn構(gòu)建元組(An,mn),并將其存儲(chǔ)到對(duì)應(yīng)的臨時(shí)列表中;
8) 通過PsJoin連接算法對(duì)臨時(shí)表中的分組屬性進(jìn)行連接,刪除無價(jià)值的元組,得到全新的列表;
9) 通過各個(gè)分組在位圖中的記錄,借助期望函數(shù)對(duì)其進(jìn)行計(jì)算,同時(shí)將結(jié)構(gòu)插入到聚集度量表中;
10) 刪除無價(jià)值的臨時(shí)供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征維度表[12].
由于維度表中存在的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征較少,所提算法是通過分組屬性對(duì)滿足條件的元組進(jìn)行分組,因此需要將各個(gè)分組的供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征放置到對(duì)應(yīng)的維度表中.
分析聯(lián)合代理需求,將滿足條件的元組放置到臨時(shí)表中,對(duì)應(yīng)的開銷計(jì)算表達(dá)式為
(2)
式中:B為網(wǎng)絡(luò)結(jié)構(gòu)特征元數(shù)量;Xn為多維度表中參與連接的操作維記錄數(shù)量;Yn-τ為供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征度;Xn-2τ為臨時(shí)表中參與連接的維數(shù)記錄量.
對(duì)臨時(shí)表中的全部供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行分組排列,則該部分對(duì)應(yīng)的開銷表達(dá)式為
(3)
式中:e為用來排序的供應(yīng)量網(wǎng)絡(luò)結(jié)構(gòu)特征數(shù)量;k為網(wǎng)絡(luò)結(jié)構(gòu)特征對(duì)應(yīng)組別數(shù)量.
通過位圖連接索引,計(jì)算對(duì)應(yīng)分組的位圖,則該部分的開銷計(jì)算表達(dá)式為
(4)
式中,f為事實(shí)表的記錄總數(shù).
在上述分析的基礎(chǔ)上,結(jié)合不同的開銷,利用層次聯(lián)合代理與預(yù)先分組排序的方式,將供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征的聚集操作轉(zhuǎn)換為區(qū)域查詢,同時(shí)借助位圖中對(duì)應(yīng)的訪問事實(shí)表,對(duì)全部供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征進(jìn)行多維層次聚集,得到聚集結(jié)果Z,其計(jì)算表達(dá)式為
(5)
式中:j為供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征總維數(shù);p為連接參與網(wǎng)絡(luò)維數(shù).
為了驗(yàn)證所設(shè)計(jì)供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集算法的有效性,本文設(shè)計(jì)了仿真實(shí)驗(yàn).選擇本市某大型電商企業(yè)的供應(yīng)商網(wǎng)絡(luò)運(yùn)行數(shù)據(jù)作為本次實(shí)驗(yàn)的數(shù)據(jù).元組數(shù)據(jù)為4萬條,數(shù)據(jù)量為101 GB,供應(yīng)商網(wǎng)絡(luò)覆蓋率為0.93,供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維傳輸過程延時(shí)為1.5 ms.同時(shí)將文獻(xiàn)[2]、[3]方法作為對(duì)比方法,對(duì)多維層次聚集效率與供應(yīng)商網(wǎng)絡(luò)中無效節(jié)點(diǎn)的判斷性能進(jìn)行對(duì)比測(cè)試.
為驗(yàn)證本文方法的聚集效率,實(shí)驗(yàn)以聚集響應(yīng)時(shí)間和聚集過程耗時(shí)作為測(cè)試指標(biāo).兩項(xiàng)測(cè)試指標(biāo)的取值越低,則說明供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集效率越高.3種算法的實(shí)驗(yàn)對(duì)比結(jié)果如圖3所示.
由圖3的實(shí)驗(yàn)數(shù)據(jù)可知,隨著元組數(shù)量的增加,不同方法對(duì)多維層次聚集的耗時(shí)與響應(yīng)時(shí)間也在增加.通過圖3a可知,文獻(xiàn)[2]方法的聚集響應(yīng)時(shí)間在15~28 ms之間,文獻(xiàn)[3]方法的聚集響應(yīng)時(shí)間在17~25 ms之間,而本文提出方法的聚集響應(yīng)時(shí)間在13~23 ms之間,本文方法與另兩種方法的聚集響應(yīng)時(shí)間相比最短.通過圖3b可知,文獻(xiàn)[2]方法的聚集耗時(shí)在73~100 ms之間,文獻(xiàn)[3]方法的聚集耗時(shí)在90~100 ms之間,而本文提出方法的聚集耗時(shí)在70~92 ms之間,本文方法與另兩種方法的聚集耗時(shí)相比也同樣最短.
圖3 多維層次聚集效率測(cè)試結(jié)果Fig.3 Test results of multi-dimensional hierarchical aggregation efficiency
為了證明本文提出方法的使用性能,對(duì)供應(yīng)商網(wǎng)絡(luò)中無效節(jié)點(diǎn)的判斷性能進(jìn)行實(shí)驗(yàn)測(cè)試.以文獻(xiàn)[2]方法和文獻(xiàn)[3]方法為對(duì)比方法,以電商供應(yīng)商網(wǎng)絡(luò)運(yùn)行數(shù)據(jù)為實(shí)驗(yàn)對(duì)象,重點(diǎn)測(cè)試不同方法的聚集性能.在實(shí)驗(yàn)數(shù)據(jù)中包含4個(gè)事實(shí)表和1個(gè)維表.事實(shí)表是用來記錄商務(wù)事實(shí)和相關(guān)統(tǒng)計(jì)指標(biāo)的結(jié)果表;維表是用戶分析決策的角度展示.實(shí)驗(yàn)設(shè)置元組數(shù)據(jù)數(shù)量為4萬條,無效節(jié)點(diǎn)數(shù)量最多為300個(gè),按照不同節(jié)點(diǎn)數(shù)量檔位,對(duì)不同方法的判斷能力進(jìn)行測(cè)試,測(cè)試結(jié)果如表1所示.
表1 對(duì)供應(yīng)商網(wǎng)絡(luò)中無效節(jié)點(diǎn)的判斷性能測(cè)試結(jié)果Tab.1 Judgment and performance test results of invalid nodes in supplier network
分析表1數(shù)據(jù)可知,文獻(xiàn)[2]方法無效節(jié)點(diǎn)的判斷率在84%~95%之間,文獻(xiàn)[3]方法無效節(jié)點(diǎn)的判斷率在90%~96.8%之間,而本文方法無效節(jié)點(diǎn)的判斷率始終保持在98%以上,高于兩種對(duì)比文獻(xiàn)方法.在無效節(jié)點(diǎn)數(shù)量少于150個(gè)時(shí),本文方法能夠準(zhǔn)確判斷出所有的無效節(jié)點(diǎn);在無效節(jié)點(diǎn)數(shù)量多于150個(gè)時(shí),也基本能夠判斷出絕大部分的無效節(jié)點(diǎn),判斷率為98%,判斷性能更優(yōu).實(shí)驗(yàn)結(jié)果證明,本文方法能夠更有效地篩選出供應(yīng)商網(wǎng)絡(luò)中有效的節(jié)點(diǎn),從而令有效供應(yīng)商節(jié)點(diǎn)的特征能夠被識(shí)別,從根本上提高多維層次聚集效果.
針對(duì)傳統(tǒng)供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征存在的一系列問題,文章提出一種供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集算法.將價(jià)值屬性讀入到系統(tǒng)內(nèi)存中,有效降低計(jì)算量和內(nèi)存壓力.根據(jù)系統(tǒng)需要優(yōu)先對(duì)維度層次進(jìn)行二次編碼處理,得到相關(guān)屬性編碼,根據(jù)數(shù)據(jù)列存儲(chǔ)思想,將對(duì)應(yīng)的關(guān)聯(lián)信息和細(xì)節(jié)信息同時(shí)存儲(chǔ)到RDD中.實(shí)驗(yàn)測(cè)試結(jié)果表明,所提算法能夠有效提升聚集效率,且有效提高了對(duì)供應(yīng)商網(wǎng)絡(luò)中無效節(jié)點(diǎn)的判斷性能,能夠更好實(shí)現(xiàn)供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集.