供應商網絡結構特征多維層次聚集算法

蕭展輝， 唐良運， 孫 剛

(1. 華南理工大學 計算機科學與工程學院， 廣州 510006； 2. 南方電網數字電網研究院有限公司 平臺安全分公司數據平臺事業部(南網大數據中心)， 廣州 510663)

世界經濟的快速發展有效地推動著企業的進步，新興信息技術在各個領域中的滲透，使中國產業變革的進程不斷加快[1].各種供應商的資源也逐漸發展成為企業競爭的核心依據.用戶需求的不斷增加與日益激烈的市場競爭，促使著企業供應商必須開展相關的運營和產品創新等活動，因此，有效的管理以及供應商網絡已成為制造業領域的重點研究內容，同時也是學術界研究的熱點.李民等[2]針對供應商優選決策過程展開研究，對兩級供應鏈構建多代理仿真模型，并驗證了多種參數在供應鏈傳播角度產生的影響，發現供應商網絡中各成員之間的財務操作決策是影響供應鏈傳播的重要因素之一.但是該方法缺少聚類分析過程，未充分考慮供應商網絡的結構特征，導致其應用效果較差.李昌盛等[3]則基于聚類分析過程，提出了一種降低連接和聚集操作的新算法.該算法充分考慮了供應商網絡復雜、多維層次的特點，在原有的位圖連接索引基礎上，采用層次聯合代理和預先分組排序的方法，使多維層次上的連接和聚集操作轉化成事實表上的區域查詢，從而在處理多維層次聚集的同時，提高了網絡連接和聚集的效率.然而在實際應用中發現，該方法中所提的聚類過程不適應特征較多的供應鏈網絡.

針對上述問題，本文提出了一種供應商網絡結構特征多維層次聚集算法.通過Spark為數據集提供支撐，將數據存儲到集群機器內存中，通過服務編號來區分不同用戶的請求.利用表連接操作的中間結果，在降低耗時的同時，還能夠提升連接操作的利用效率.實驗測試表明，所提算法能夠有效提升聚集效率，能更好地完成供應商網絡結構特征多維層次聚集.

1 方法論

1.1 供應商網絡結構特征的聯機分析處理

供應商網絡具有層級關系，不僅包括了制造企業和各級供應商之間的縱向關系，還包括了供應商和供應商之間的橫向關系.在網絡結構中，企業處于核心位置，與網絡中供應商、供應商的供應商相互聯系、交織在一起.為了有效增加供應商網絡中的分布式計算框架利用效率，本文以Spark為數據集提供支撐，并將供應商網絡數據存儲到集群機器內存中，聯機分析處理結構如圖1所示.

圖1中，應用層為供應商網絡的終端用戶提供接口并展示操作結果，同時還能夠通過瀏覽器進行多維分析查詢和用戶登錄等相關操作；驅動層主要負責處理不同處理器對應的公共程序接口，能夠全面提升供應商網絡的通用性；服務器層主要負責接收處理各供應商根據驅動層請求的操作，通過服務編號來區分處理不同供應商的請求；計算層主要負責對不同的任務進行計算，同時還能夠進行查詢以及分析等相關工作；存儲層主要通過分布式儲存、集中式管理的方式，對供應商數據進行存儲[4].

圖1 基于Spark的聯機分析處理結構圖Fig.1 Structure diagram of online analytical processing based on Spark

在聯機分析處理系統中，不同層次均對應一種供應商網絡結構特征，這些特征具有統一維度，因此，也可以將不同維度對應的供應商網絡結構特征存儲為供應商網絡結構特征維度表[5].此外，在實際應用過程中，結合Spark內存計算框架的主要特征和組成結構，需要進一步減少結構特征在供應商網絡間的傳輸數量[6]，并且還需要再次對供應商網絡結構特征進行處理，最終將處理結果和結構特征對應的信息進行存儲，有效增加聯機分析的速度.

為了加快聯機分析處理系統對供應商網絡不同結構特征的處理速度，需要優先對結構特征進行二次處理，并且只對相關供應商網絡特征屬性進行編碼.其中，供應商網絡特征屬性編碼Di計算表達式為

(1)

式中：Li為混合編碼；h為組成成員數量.

根據供應商網絡不同結構特征的編碼處理結果，在全維度表中提取相關的結構特征信息，并且刪除無價值的供應商網絡信息.

在聯機分析處理過程中，不僅需要注重細節的處理，同時還需要特別注重供應商網絡結構特征維度表的外鍵[7].具體注意事項如下：

1) 當系統讀取事實表時，需要避免無價值的供應商網絡結構屬性讀入到系統中，有效降低聯機分析計算量.

2) 主要借助連接標的中間操作結果，分析不同供應商網絡用戶的查詢以及使用習慣，同時還可以避免系統出現重復查詢的情況.

在Spark框架中，需要優先預處理供應商網絡結構數據包，并將對應的供應商網絡關聯信息同時存儲到RDD中.另外，需要在已有數據讀取方式的基礎上，進行全新數據結構[8]設計.

對不同用戶使用系統的行為與方位次數等進行統計，同時結合Spark特性[9]，將冗余供應商網絡結構特征刪除，并且將含有新層次的維度編碼進行轉換，為后續查詢奠定基礎.通過Spark的RDD緩存機制[10]，優先對系統內的供應商網絡結構特征進行緩存處理，確保供應商網絡結構特征的查詢速度.基于Spark的供應商網絡結構特征聯機分析處理操作流程如圖2所示.

圖2 聯機分析處理流程圖Fig.2 Flow chart of online analytical processing

1.2 多維層次聚集分析

本研究通過位圖連接索引[11]實現對供應商網絡結構特征的多維層次聚集處理.位圖連接索引是在傳統索引基礎上發展起來的，通過位圖連接索引能夠有效降低維表與事實表兩者的連接時間，確保聚集操作的有效性.在供應商網絡數據倉庫中，將n個維度的數據分別表示為d1，d2，…，dn，其中，兩個或者兩個以上的位圖連接索引需要適當執行“與”、“或”操作.位圖連接索引對應兩種情況，一種是元組織標識對應的事實表元組包含維表主碼值；另一種是元組織標識對應的事實表元組不包含維表主碼值.

所提出的供應商網絡結構特征多維層次聚集算法整體思路如下：

1) 通過轉換供應商網絡不同維度層次中各個維度的約束條件形成待聚集區域，并將滿足約束條件的屬性放置到對應的文件夾中；

2) 根據分組屬性排序結果集；

3) 通過位圖連接索引，得到供應商網絡不同分組的位圖；

4) 通過各個分組在位圖中的位置，選取對應的事實表記錄，同時借助期望聚集函數進行計算.

算法具體運行流程如下：

1) 算法初始化，設置相應的參數；

2) 分析不同的參數查詢條件，通過結合對應的編碼文件，即可獲取各個字段對應的聯合代理編碼；

3) 根據編碼所在位置，將其插入到對應的臨時表中；

4) 針對查詢結果的分組屬性，通過Kary合并算法對排序臨時表進行分組處理；

5) 確定供應商網絡分組組數；

6) 通過位圖索引對各個數組中的全部記錄進行“或”操作，進而獲取各個分組對應的位圖；

7) 根據分組屬性An對應的分組值和位圖mn構建元組(An，mn)，并將其存儲到對應的臨時列表中；

8) 通過PsJoin連接算法對臨時表中的分組屬性進行連接，刪除無價值的元組，得到全新的列表；

9) 通過各個分組在位圖中的記錄，借助期望函數對其進行計算，同時將結構插入到聚集度量表中；

10) 刪除無價值的臨時供應商網絡結構特征維度表[12].

由于維度表中存在的供應商網絡結構特征較少，所提算法是通過分組屬性對滿足條件的元組進行分組，因此需要將各個分組的供應商網絡結構特征放置到對應的維度表中.

分析聯合代理需求，將滿足條件的元組放置到臨時表中，對應的開銷計算表達式為

(2)

式中：B為網絡結構特征元數量；Xn為多維度表中參與連接的操作維記錄數量；Yn-τ為供應商網絡結構特征度；Xn-2τ為臨時表中參與連接的維數記錄量.

對臨時表中的全部供應商網絡結構特征進行分組排列，則該部分對應的開銷表達式為

(3)

式中：e為用來排序的供應量網絡結構特征數量；k為網絡結構特征對應組別數量.

通過位圖連接索引，計算對應分組的位圖，則該部分的開銷計算表達式為

(4)

式中，f為事實表的記錄總數.

在上述分析的基礎上，結合不同的開銷，利用層次聯合代理與預先分組排序的方式，將供應商網絡結構特征的聚集操作轉換為區域查詢，同時借助位圖中對應的訪問事實表，對全部供應商網絡結構特征進行多維層次聚集，得到聚集結果Z，其計算表達式為

(5)

式中：j為供應商網絡結構特征總維數；p為連接參與網絡維數.

2 仿真實驗

為了驗證所設計供應商網絡結構特征多維層次聚集算法的有效性，本文設計了仿真實驗.選擇本市某大型電商企業的供應商網絡運行數據作為本次實驗的數據.元組數據為4萬條，數據量為101 GB，供應商網絡覆蓋率為0.93，供應商網絡結構特征多維傳輸過程延時為1.5 ms.同時將文獻[2]、[3]方法作為對比方法，對多維層次聚集效率與供應商網絡中無效節點的判斷性能進行對比測試.

2.1 多維層次聚集效率測試

為驗證本文方法的聚集效率，實驗以聚集響應時間和聚集過程耗時作為測試指標.兩項測試指標的取值越低，則說明供應商網絡結構特征多維層次聚集效率越高.3種算法的實驗對比結果如圖3所示.

由圖3的實驗數據可知，隨著元組數量的增加，不同方法對多維層次聚集的耗時與響應時間也在增加.通過圖3a可知，文獻[2]方法的聚集響應時間在15～28 ms之間，文獻[3]方法的聚集響應時間在17～25 ms之間，而本文提出方法的聚集響應時間在13～23 ms之間，本文方法與另兩種方法的聚集響應時間相比最短.通過圖3b可知，文獻[2]方法的聚集耗時在73～100 ms之間，文獻[3]方法的聚集耗時在90～100 ms之間，而本文提出方法的聚集耗時在70～92 ms之間，本文方法與另兩種方法的聚集耗時相比也同樣最短.

圖3 多維層次聚集效率測試結果Fig.3 Test results of multi-dimensional hierarchical aggregation efficiency

2.2 網絡無效節點的判斷性能測試

為了證明本文提出方法的使用性能，對供應商網絡中無效節點的判斷性能進行實驗測試.以文獻[2]方法和文獻[3]方法為對比方法，以電商供應商網絡運行數據為實驗對象，重點測試不同方法的聚集性能.在實驗數據中包含4個事實表和1個維表.事實表是用來記錄商務事實和相關統計指標的結果表；維表是用戶分析決策的角度展示.實驗設置元組數據數量為4萬條，無效節點數量最多為300個，按照不同節點數量檔位，對不同方法的判斷能力進行測試，測試結果如表1所示.

表1 對供應商網絡中無效節點的判斷性能測試結果Tab.1 Judgment and performance test results of invalid nodes in supplier network

分析表1數據可知，文獻[2]方法無效節點的判斷率在84%～95%之間，文獻[3]方法無效節點的判斷率在90%～96.8%之間，而本文方法無效節點的判斷率始終保持在98%以上，高于兩種對比文獻方法.在無效節點數量少于150個時，本文方法能夠準確判斷出所有的無效節點；在無效節點數量多于150個時，也基本能夠判斷出絕大部分的無效節點，判斷率為98%，判斷性能更優.實驗結果證明，本文方法能夠更有效地篩選出供應商網絡中有效的節點，從而令有效供應商節點的特征能夠被識別，從根本上提高多維層次聚集效果.

3 結 論

針對傳統供應商網絡結構特征存在的一系列問題，文章提出一種供應商網絡結構特征多維層次聚集算法.將價值屬性讀入到系統內存中，有效降低計算量和內存壓力.根據系統需要優先對維度層次進行二次編碼處理，得到相關屬性編碼，根據數據列存儲思想，將對應的關聯信息和細節信息同時存儲到RDD中.實驗測試結果表明，所提算法能夠有效提升聚集效率，且有效提高了對供應商網絡中無效節點的判斷性能，能夠更好實現供應商網絡結構特征多維層次聚集.