供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征多維層次聚集算法

蕭展輝， 唐良運(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)特征多維層次聚集.

1 方法論

1.1 供應(yīng)商網(wǎng)絡(luò)結(jié)構(gòu)特征的聯(lián)機(jī)分析處理

供應(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

1.2 多維層次聚集分析

本研究通過位圖連接索引[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ù).

2 仿真實(shí)驗(yàn)

為了驗(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è)試.

2.1 多維層次聚集效率測(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

2.2 網(wǎng)絡(luò)無效節(jié)點(diǎn)的判斷性能測(cè)試

為了證明本文提出方法的使用性能，對(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í)別，從根本上提高多維層次聚集效果.

3 結(jié) 論

針對(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)特征多維層次聚集.