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

張正義，崔 健

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

1 引言

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

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

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

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

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

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

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

通過Apriori并行算法得到頻繁模式后，各數(shù)據(jù)類的結(jié)果經(jīng)過合并分析得到的物流頻繁路徑結(jié)果，該結(jié)果通過采用物流網(wǎng)絡(luò)中頻繁路徑的某些性質(zhì)獲取，具體性質(zhì)主要分三種，分別為：

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

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

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

2.2 Fuzzy c-means算法及并行化實現(xiàn)

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

(1)

(2)

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

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

(3)

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

(4)

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

循環(huán)部分：根據(jù)預(yù)設(shè)閾值進(jìn)行準(zhǔn)則函數(shù)的判斷，當(dāng)準(zhǔn)則函數(shù)滿足預(yù)設(shè)閾值時，循環(huán)結(jié)束，反之則繼續(xù)執(zhí)行循環(huán)。

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

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

2.3 改進(jìn)Apriori算法及并行化實現(xiàn)

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

表1 事務(wù)數(shù)據(jù)庫

1)對事務(wù)數(shù)據(jù)庫進(jìn)行遍歷后儲存于數(shù)組

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

2)遍歷數(shù)組X中產(chǎn)生的頻繁項集

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

表2 頻繁項集

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

3)產(chǎn)生備選頻繁相集

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

改進(jìn)Apriori算法的優(yōu)勢在于：①通過對數(shù)據(jù)庫的一次性掃描有效降低系統(tǒng)I/O的負(fù)載，提升算法的運行效果；②在數(shù)組中儲存相應(yīng)的頻繁集和支持度方便后續(xù)強關(guān)聯(lián)規(guī)則快速產(chǎn)生；③強關(guān)聯(lián)規(guī)格可通過數(shù)組中依次儲存的頻繁相集順序進(jìn)行判定，根據(jù)判定結(jié)果能夠輕易分辨是由候選頻繁項集產(chǎn)生還是由原數(shù)據(jù)產(chǎn)生，便于在應(yīng)用中進(jìn)行針對性的選擇。

MapReduce模型最大的優(yōu)勢為wed數(shù)據(jù)的詞頻挖掘，改進(jìn)Apriori算法完全滿足其性質(zhì)，基于MapReduce的改進(jìn)Apriori并行算法流程圖如圖2所示。

圖2 改進(jìn)Apriori并行算法流程圖

3 實驗結(jié)果與分析

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

在不同支持度，相同事務(wù)數(shù)的條件下進(jìn)行獲取頻繁相集需要的時間對比，事務(wù)數(shù)為5000，對比結(jié)果如圖3所示。

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

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

在相同支持度，不同事務(wù)數(shù)的條件下進(jìn)行獲取頻繁相集需要的時間對比，支持度為0.05。對比結(jié)果如圖4所示。

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

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

在相同支持度條件下進(jìn)行強關(guān)聯(lián)規(guī)則的對比實驗，設(shè)最小支持度為0.1，遍歷數(shù)據(jù)庫中所有記錄，結(jié)果如表3所示。

表3 強關(guān)聯(lián)規(guī)則對比結(jié)果統(tǒng)計表

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

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

表4 文獻(xiàn)[5]算法運行結(jié)果統(tǒng)計表

表5 文獻(xiàn)[6]算法運行結(jié)果統(tǒng)計表

表6 本文算法運行結(jié)果統(tǒng)計表

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

4 結(jié)論

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