基于并行Apriori的鐵路物流配送FPMA

張正義，崔 健

(1. 西安航空學院，陜西西安 710077；2. 長安大學，陜西西安 710064)

1 引言

在當下的物流領域，針對鐵路物流配送頻繁路徑數據的挖掘分析通常采用RFID、GPS等信息技術，對于貨物運輸的路徑規律和物流配送的優化有十分重要的意義[1-2]。目前大多采用關聯規則算法進行頻繁項集的挖掘分析，但隨著物流行業的快速發展，傳統的數據挖掘算法面對類型多且數據量龐大的現實，已經很難適應當前的物流配送環境[3-4]。因此，很多專業提出利用處理平臺完成傳統算法的并行化方案，唐兵等研究的基于MPI和OpenMP混合編程的非負矩陣分解并行算法，將基于MPI的消息傳遞模型的優勢與基于OpenMP的共享存儲模型的優勢相結合的方法，提高了運行的加速比和計算效率[5]；彭自然等研究的一種在多核嵌入式平臺上實現FFT的快速并行算法，將靜態多項式奇偶項的不同特點代入數據計算中，以此提高并行算法運行速度[6]。雖然以上兩種并行算法都能通過算法并行化提高計算機對龐大數據的處理速度，同時結合物流網絡對頻繁路徑挖掘的特點，一定程度解決目前物流配送頻繁路徑挖掘等問題。

但是，在算法運行過程中的速度和效率還達不到理想的效果，為了提升并行算法的計算速度，提高運行效率和頻繁徑路挖掘的精準度，保證物流管理者能清晰地了解貨物流向，本文提出的基于并行Apriori的鐵路物流配送頻繁路徑挖掘算法，綜合利用Fuzzy c-means算法和改進Apriori算法實現鐵路物流配送頻繁路徑的有效挖掘，進而幫助物流管理者實時了解物流配送的狀況，對物流環節進行優化，有效降低物流配送運輸成本。

2 基于并行Apriori的鐵路物流配送頻繁路徑挖掘算法

2.1 基于Fuzz c-means的Apriori并行算法

對數據集中的頻繁項集利用逐層搜索的迭代方式進行分析的算法為Apriori算法，具有便捷、易實現等優勢。Apriori算法要求對數據集進行多次掃描，在生成每個頻繁候選集的過程中，必須對該數據集進行一次全面掃描，如果生成的頻繁項集長度為S，則掃描次數通常為S+1次。當計算機處理較大數據集時，當計算機內存容量有限時，系統I/O會出現負載過大的情況，從而導致Apriori算法的運行效率降低，不利于頻繁模式挖掘[7]。

Apriori算法的并行化通過編輯模型MapReduce實現，具備提高Apriori算法運行效率的作用。Apriori算法可挖掘分析整體數據集中的頻繁模式，就物流配送來說，某些局部區域存在偏少的路徑數據，致使該區域為頻繁路徑的序列，因其不能滿足最小支持度而在整體頻繁路徑挖掘分析過程中被忽略[8]。基于此，本文將基于Fuzzy c-means的Apriori并行算法建立在Hadoop數據處理平臺之上，利用Fuzzy c-means算法對數據集進行聚類分析，根據內部相似度將數據集劃分出多類具有較高相似度的數據簇，利用Apriori算法對所包含的頻繁模式進行分類，然后對合并后的數據進行分類分析，得到每個區域的頻繁路徑序列[9]。利用Hadoop中的子項目 MapReduce和Mahout，利用大數據的處理特性，實現算法的并行性，以此提升算法的處理效率和適應性，具體算法流程圖如圖1所示。

圖1 基于Fuzzy c-means的Apriori并行算法流程圖

通過Apriori并行算法得到頻繁模式后，各數據類的結果經過合并分析得到的物流頻繁路徑結果，該結果通過采用物流網絡中頻繁路徑的某些性質獲取，具體性質主要分三種，分別為：

1)運輸貨物時，沒有重復的移動路徑，因此在最終的路徑數據中，回路不可能出現。

2)如果在兩條頻繁路徑中存在一條為另一條子路徑時，該子路徑應被舍去。例：頻繁路徑K1=〈a1，a2，…，ae〉和頻繁路徑K2=〈b1，b2，…，bf〉，如果整數e和f滿足f>e，且a1=b1，a2=b2，…，ae=bf，則K2的子路徑為K1，合并K1、K2，在最終結果中只顯示頻繁路徑K2。

3)分析合并是根據物流網絡特有的特點進行，從兩方面表現，即：①網絡中任意相鄰的兩點在路徑序列中都是相鄰的，假定甲點和丙點之間不相鄰，需要通過乙點或丁點連接，則在最終頻繁路徑結果中就不能出現甲→丙，只允許出現甲→乙→丙或者甲→丁→丙。②如果一條頻繁路徑舍去第一個節點的子路徑為另一條頻繁路徑的S-1序列，設頻繁路徑甲→乙→丙和乙→丙→丁，那么就能夠合并成甲→乙→丙→丁。基于上述物流路徑性質，分析了合并后的頻繁路徑序列，從而實現最終的物流頻繁路徑序列。

2.2 Fuzzy c-means算法及并行化實現

Fuzzy c-means算法是一種其具有明確的數學理論依據和可行性高的常用聚類算法，Fuzzy c-means聚類算法需要提前預設一些參數，如聚類類別參數和終止條件閾值參數等，利用聚類中心與距離度量數據的相似度對聚類中心進行持續更新，將原始數據集劃分為多個數據簇，數據簇之間秉承著對內相似度高，對外相似度低的原則[10]。Fuzzy c-means算法采用模糊理論的觀點，利用數據對每個數據簇的歸屬程度體現各數據簇的歸屬概率，其思想表示為：

(1)

(2)

1)對算法進行初始化，確定聚類數據簇T，n≥T≥2，n表示數據總量，初始化隸屬度矩陣可描述為U=[uij]，以U表示，初始化聚類中心可描述為T=[ti]，以T表示。

2)對聚類中心向量T進行更新，公式為

(3)

3)對隸屬度矩陣U(s)，U(s+1)進行更新，公式為

(4)

Fuzzy c-means算法的并行化完成是利用Hadoop平臺的Mabout實現的，在算法的并行化過程由循環部分和循環體部分組成。

循環部分：根據預設閾值進行準則函數的判斷，當準則函數滿足預設閾值時，循環結束，反之則繼續執行循環。

循環體部分：主要作用是實現算法的計算過程，算法運行效率利用Fuzzy c-means Combiner任務得以提升。

初始聚類中心點文件和輸入數據文件為Fuzzy c-means算法的核心輸入，初始中心點為設置參數在原始數據集中自動提取的n個值。經過對上次中心點和新輸入數據的計算，獲得新的聚類中心，并將其保存到新的中心點文件路徑；Fuzzyc-means Mapper數據 setup函數讀取，采用預設方法對數據根據就近原則進行劃分到聚類中心簇中；根據Mapper任務的輸出結果，Fuzzy c-means Combiner進行整合后得到最終輸出。

2.3 改進Apriori算法及并行化實現

改進的Apriori算法的原理是通過數組儲存的數據降低數據庫的掃描次數，根據表1的事務數據庫詳細介紹算法獲取頻繁項集順序。

表1 事務數據庫

1)對事務數據庫進行遍歷后儲存于數組

TID為項目集的唯一標識符，根據標識符把遍歷后的數據存儲于數組X中，同一標識符中不一樣單項間隔符號為“，”，不同的標識符間隔符號為“；”，則X[ ]={I1，I2;I3，I4;I2，I5，I6}。

2)遍歷數組X中產生的頻繁項集

參照預設的最小支持度產生的頻繁多種項集進行數組X遍歷，在數組{X1，X2，…，Xn}內存儲產生的項集及相應的支持度，其中n用來描述項目集的長度。項目集與支持度之間的分割符號為“、”，不同的項集之間分隔符號為“；”，根據表1的事務數據庫設最小支持度為0.2后產生頻繁項集，即：

表2 頻繁項集

把頻繁項集存儲進數組中，即X1[ ]={I1、0.26；I2、0.9；I5、0.6}。

3)產生備選頻繁相集

備選k相集通過數組X(k-1)與其自己連接來生成，將生成的備選相集根據最小支持度生成頻繁k相集，對比Xk數組中相集，若數組中無相集，則根據產生的順序依次儲存于Xk數組內。

改進Apriori算法的優勢在于：①通過對數據庫的一次性掃描有效降低系統I/O的負載，提升算法的運行效果；②在數組中儲存相應的頻繁集和支持度方便后續強關聯規則快速產生；③強關聯規格可通過數組中依次儲存的頻繁相集順序進行判定，根據判定結果能夠輕易分辨是由候選頻繁項集產生還是由原數據產生，便于在應用中進行針對性的選擇。

MapReduce模型最大的優勢為wed數據的詞頻挖掘，改進Apriori算法完全滿足其性質，基于MapReduce的改進Apriori并行算法流程圖如圖2所示。

圖2 改進Apriori并行算法流程圖

3 實驗結果與分析

本文利用Hadoop數據處理平臺進行實驗，采用的服務器為聯想System x3650 M5(5462I05)，開發工具為Qt Design Studio 2.0版本，通過Java和HDFS完成語言編碼和數據存儲。為驗證本文算法的優越性，分別采用本文算法與文獻[5]基于MPI和OpenMP混合編程的非負矩陣分解并行算法和文獻[6]一種在多核嵌入式平臺上實現FFT的快速并行算法進行性能比較。實驗中所需進行挖掘實驗的數據庫為包含53647條記錄和23614個事務集的微軟實例數據庫Adventure Works-DW。事務標識符為OrderNumber，事務項為Model。

在不同支持度，相同事務數的條件下進行獲取頻繁相集需要的時間對比，事務數為5000，對比結果如圖3所示。

圖3 不同支持度條件下獲取頻繁項集所需時間對比

由圖3可知，本文算法在不同支持度情況下獲取頻繁項集所需時間最少、波動最小，說明本文算法在運行過程中速度更快，穩定性更高。

在相同支持度，不同事務數的條件下進行獲取頻繁相集需要的時間對比，支持度為0.05。對比結果如圖4所示。

圖4 不用事務數條件下獲取頻繁項集所需時間對比

由圖4可知，在支持度相同，事務數不同的條件下，隨著事務數的逐漸增加，三種算法的執行時間都在隨之增加，但是本文算法從起始速度和執行時間增長幅度明顯較小，表明本文算法可有效提高關聯規則挖掘的運行效率。

在相同支持度條件下進行強關聯規則的對比實驗，設最小支持度為0.1，遍歷數據庫中所有記錄，結果如表3所示。

表3 強關聯規則對比結果統計表

由表3可知，在相同支持度條件下，本文算法能夠以最短的時間快速找到所需求的強關聯規則，且本文算法找出的強關聯規則和頻繁項集個數最少，對比兩種并行算法，表明文獻[5]算法比本文算法多找了76個冗余頻繁項集，文獻[6]算法比本文算法多找了47個冗余頻繁項集，實驗驗證，本文算法挖掘頻繁項集的效率更好。

為了更詳細地驗證本文算法在物流頻繁路徑挖掘中的有效性，基于相同條件下的運行結果詳細測試，設最小支持度為0.75，頻繁序列中的項目數為5，數據集不變，運行結果如表4到表6所示。

表4 文獻[5]算法運行結果統計表

表5 文獻[6]算法運行結果統計表

表6 本文算法運行結果統計表

由表4到表6可知，文獻[5]算法獲取的頻繁序列數為8條，各頻繁序列在數據集中的頻次為7200-9900；文獻[6]算法獲取的頻繁序列數為14條，各頻繁序列在數據集中的頻次為5100-9800，而本文算法類1和類2的頻繁序列總和為4001條，各頻繁序列在數據集中的頻次為2600-5300，并且本文算法類1中的頻次與兩種對比并行算法存在著較大的差距，表明文獻[5]和文獻[6]的算法中不涵蓋數據類1的結果，可以理解在算法運行過程中，如果某區域的物流配送路徑在全局數據集中分量很小，那么兩種對比的并行算法就很容易忽略掉該區域在頻繁徑路的挖掘，導致該區域的有物流路徑在最后的結果中不能得到體現，而在物流配送的實際應用中，所有物流路徑都非常重要，因此，本文算法在頻繁徑路的挖掘中的精確度更高，也更具備實際應用價值。

4 結論

本文基于Fuzzc-means的Apriori并行算法實現鐵路物流配送頻繁路徑挖掘，利用Hadoop數據處理平臺和數據挖掘技術進行物流配送環節中產生的龐大數據信息的挖掘分析，為了提升數據處理速度、運行效率和精準度，對Fuzzy c-means算法與改進Apriori算法進行并行化，實現對鐵路物流配送中龐大數據的挖掘分析，滿足當前對物流路徑頻繁模式的挖掘需求。在后續的研究中，需要進一步對物流頻繁路徑進入配送中心等決策性問題展開研究。