基于改進(jìn)Apriori算法的倉(cāng)庫(kù)貨物關(guān)聯(lián)度分析

趙 峰，劉小倩

(安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山 243032)

隨著經(jīng)濟(jì)的持續(xù)穩(wěn)定發(fā)展，現(xiàn)代物流業(yè)也日益呈現(xiàn)出高速發(fā)展的狀態(tài).然而物流行業(yè)在快速發(fā)展中也存在著許多問題亟待解決，體現(xiàn)尤為明顯的就是物流倉(cāng)儲(chǔ)業(yè).2018年我國(guó)社會(huì)物流總額增速有所放緩，約降低0.2%，全年社會(huì)物流總額為283.1×104億元.同年我國(guó)社會(huì)物流總費(fèi)用增速提高，增長(zhǎng)了9.8%，全年社會(huì)物流總費(fèi)用為13.3×104億元，運(yùn)輸費(fèi)用比率有所降低，而倉(cāng)儲(chǔ)費(fèi)用和管理費(fèi)用的比率呈現(xiàn)上升狀態(tài)，社會(huì)物流總費(fèi)用與GDP的比率為14.8%.在費(fèi)用構(gòu)成方面，2018年保管費(fèi)用即倉(cāng)儲(chǔ)費(fèi)用金額為4.6×104億元，增速同比提高7.1%，相較去年增長(zhǎng)了13.8%.根據(jù)數(shù)據(jù)分析得出，我國(guó)物流倉(cāng)儲(chǔ)業(yè)的發(fā)展仍然還有待改進(jìn)：1)由于經(jīng)濟(jì)的快速發(fā)展，消費(fèi)市場(chǎng)呈現(xiàn)多樣性的特點(diǎn)，傳統(tǒng)倉(cāng)庫(kù)逐漸不能滿足客戶的需求，導(dǎo)致傳統(tǒng)倉(cāng)儲(chǔ)企業(yè)盈利效益差；2)我國(guó)人口眾多，人均倉(cāng)儲(chǔ)用地面積相對(duì)較小導(dǎo)致倉(cāng)儲(chǔ)用地成本增加，倉(cāng)儲(chǔ)行業(yè)面臨著巨大的成本壓力；3)我國(guó)物流技術(shù)的發(fā)展仍存在許多壁壘，物流標(biāo)準(zhǔn)和物流效率稀缺.在這些宏觀環(huán)境影響下微觀層面同樣存在問題：1)Q卷煙配送中心倉(cāng)庫(kù)內(nèi)部貨物放置混亂，沒有明確的倉(cāng)庫(kù)出入庫(kù)制度，將貨物隨機(jī)儲(chǔ)存至空缺貨位，導(dǎo)致出庫(kù)速度慢效率低；2)Q卷煙配送中心倉(cāng)庫(kù)內(nèi)部無明確的區(qū)域劃分，空缺的通道和區(qū)域隨意擺放著貨物、包裝盒、托盤甚至出入庫(kù)機(jī)械與雜物，導(dǎo)致倉(cāng)庫(kù)整體顯得紊亂無序；3)Q卷煙配送中心倉(cāng)庫(kù)工作人員缺乏員工工作操作標(biāo)準(zhǔn)的培訓(xùn)，員工素質(zhì)有待提高，導(dǎo)致工作效率低下.因此，本文根據(jù)上述問題，研究分析傳統(tǒng)的Apriori算法并進(jìn)行改進(jìn)，比較傳統(tǒng)Apriori算法與改進(jìn)Apriori算法的效率，運(yùn)用改進(jìn)的Apriori算法分析倉(cāng)庫(kù)內(nèi)貨物品種的關(guān)聯(lián)度，通過降低揀選貨物的時(shí)間來縮短出庫(kù)作業(yè)的時(shí)間，進(jìn)一步提高響應(yīng)客戶的速度，從而增強(qiáng)揀貨效率，提高倉(cāng)庫(kù)的經(jīng)濟(jì)效益.

貨位優(yōu)化是用來確定品種規(guī)格的恰當(dāng)儲(chǔ)存方式，在恰當(dāng)儲(chǔ)存方式下的空間儲(chǔ)位分配.GyuLee和Sung[1]等人提出了一個(gè)系統(tǒng)化的整合方法并延伸了相關(guān)儲(chǔ)存指派策略，以最小化行程時(shí)間與揀選延遲將其分為兩個(gè)階段來模擬，并采用多目標(biāo)進(jìn)化算法求解；Jason和Shih[2]等人提出了一種基于群體遺傳算法的訂單批處理方法使揀貨系統(tǒng)的批數(shù)最小化，結(jié)果表明所提出的啟發(fā)式策略優(yōu)于現(xiàn)有的訂單批處理策略；Y.Zhang[3]提出了一種相關(guān)存儲(chǔ)分配策略的多種解決方案，運(yùn)用一種包含預(yù)處理和兩個(gè)分支過程的csas算法提出了求和種子聚類算法和靜態(tài)種子聚類算法來尋找項(xiàng)目集；李永偉，劉樹安[4]等人建立了以入庫(kù)作業(yè)過程中工作人員行走總路程最小為目標(biāo)的貨位優(yōu)化模型，將傳統(tǒng)遺傳算法同啟發(fā)式算法相結(jié)合對(duì)模型進(jìn)行求解；李鵬飛，馬航[5]提出以出入庫(kù)效率和貨架穩(wěn)定性為優(yōu)化因素的貨位優(yōu)化模型，采取病毒協(xié)同遺傳算法對(duì)優(yōu)化模型進(jìn)行優(yōu)化；李珍萍，陳星藝等人[6]研究了基于自動(dòng)引導(dǎo)機(jī)器人(AGV)的貨到人揀選模式下智能倉(cāng)庫(kù)系統(tǒng)補(bǔ)貨階段的儲(chǔ)位分配問題，以同一貨架上的各種商品之間的關(guān)聯(lián)度之和最大化為目標(biāo)函數(shù)建立了補(bǔ)貨階段儲(chǔ)位分配問題的整數(shù)規(guī)劃模型；谷君[7]以YH公司成品倉(cāng)庫(kù)為研究對(duì)象，主要通過數(shù)學(xué)建模方法、遺傳算法以及Flexsim仿真方法對(duì)該倉(cāng)庫(kù)的自動(dòng)化立體倉(cāng)儲(chǔ)區(qū)進(jìn)行貨位優(yōu)化.

Apriori算法應(yīng)用層面十分廣泛，也引發(fā)了眾多學(xué)者對(duì)其進(jìn)行研究.杜永興，高迪[8]等人提出基于荒漠草原數(shù)據(jù)多樣性關(guān)聯(lián)規(guī)則改進(jìn)的算法，并在此基礎(chǔ)上增加判斷數(shù)據(jù)集，減少候選項(xiàng)集的產(chǎn)生，減少大量的時(shí)間消耗，提高改進(jìn)的Apriori算法的效率；趙峰，劉博妍[9]利用改進(jìn)的Apriori算法對(duì)某高校計(jì)算機(jī)學(xué)院學(xué)生的成績(jī)進(jìn)行挖掘分析，發(fā)現(xiàn)不同學(xué)科之間的關(guān)聯(lián)關(guān)系，給予學(xué)校管理指導(dǎo)方向；曾子賢，鞏青歌[10]等人在現(xiàn)有Apriori算法改進(jìn)優(yōu)化思想的基礎(chǔ)上，結(jié)合矩陣、改進(jìn)頻繁模式樹和計(jì)算候選集頻數(shù)優(yōu)化策略提出了一種改進(jìn)的關(guān)聯(lián)規(guī)則挖掘算法—MIFP-Apriori算法；孫帥，劉子龍[11]針對(duì)Apriori算法存在的缺陷利用概率理論與有效的參數(shù)設(shè)置，在原有Apriori算法基礎(chǔ)上，提出一種基于概率事務(wù)壓縮的關(guān)聯(lián)規(guī)則改進(jìn)算法；郭鵬，蔡騁[12]針對(duì)某高校學(xué)生的學(xué)習(xí)狀況和培養(yǎng)方案的改進(jìn)需求，提出一種基于改進(jìn)K-means和引入興趣度Apriori算法的學(xué)生課程成績(jī)分析方法；文武，郭有慶[13]針對(duì)Apriori算法存在效率低、內(nèi)存損耗大等問題，提出一種基于遺傳算法來尋找頻繁項(xiàng)集的(GNA)算法，利用交叉算子產(chǎn)生候選項(xiàng)集和變異算子篩選頻繁項(xiàng)集，避免多次掃描數(shù)據(jù)庫(kù)的同時(shí)，減少冗余.雖然Apriori算法在數(shù)據(jù)挖掘領(lǐng)域的應(yīng)用性很廣泛，但是其缺陷仍然顯而易見，在算法運(yùn)行的過程中，需要多次往返地掃描事務(wù)數(shù)據(jù)庫(kù)，直接導(dǎo)致產(chǎn)生大量冗余的候選集項(xiàng)目，嚴(yán)重影響了算法運(yùn)行的效率.所以目前關(guān)于Apriori算法的研究已經(jīng)集中到對(duì)其進(jìn)行改進(jìn)運(yùn)用的階段：本文在經(jīng)典Apriori算法的基礎(chǔ)上對(duì)其進(jìn)行改進(jìn)，增加判斷候選集標(biāo)的條件，減少掃描次數(shù)，提高算法效率.

1 Apriori算法簡(jiǎn)介

隨著大數(shù)據(jù)時(shí)代的到來，信息量以爆炸的速度增長(zhǎng)，為了更好地汲取有用的信息從而產(chǎn)生了大數(shù)據(jù)、云儲(chǔ)存和云計(jì)算等技術(shù)，數(shù)據(jù)挖掘也應(yīng)運(yùn)而生.在數(shù)據(jù)挖掘中，關(guān)聯(lián)規(guī)則的挖掘應(yīng)用廣泛，例如人們?nèi)粘＝佑|網(wǎng)購(gòu)時(shí)的商品推送、搜索引擎進(jìn)行數(shù)據(jù)搜索、公司進(jìn)行營(yíng)銷分析等.在關(guān)聯(lián)規(guī)則挖掘算法中，Apriori算法是最先被提出的，也是應(yīng)用發(fā)展前景最為廣泛的[14].Apriori算法通過關(guān)聯(lián)規(guī)則來分析研究對(duì)象的關(guān)聯(lián)程度，根據(jù)關(guān)聯(lián)程度來分析貨物的相關(guān)程度，再依據(jù)相關(guān)程度將相關(guān)程度高的對(duì)象進(jìn)行鄰近配置，從而縮短相關(guān)操作的時(shí)間，提高相關(guān)操作的效率.

Apriori算法是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法，其中頻繁項(xiàng)集為所有支持度大于或者等于最小支持度的項(xiàng)集，它對(duì)挖掘?qū)ο蟮念l繁項(xiàng)集進(jìn)行分析并得出事件關(guān)聯(lián)程度，其關(guān)鍵思想是通過候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來挖掘頻繁項(xiàng)集.該算法的關(guān)聯(lián)規(guī)則屬于單維、單層以及布爾關(guān)聯(lián)規(guī)則.Apriori算法的基本操作流程是找出所有的頻繁項(xiàng)目集，生成所有頻繁集使用遞歸的方法，這些項(xiàng)集出現(xiàn)的頻繁性即支持度必須大于或者等于預(yù)定義的最小支持度，然后由算法得出的頻繁項(xiàng)目集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足設(shè)定的最小支持度和最小置信度，一旦這些規(guī)則被生成，只有大于人工設(shè)定的最小置信度的規(guī)則才會(huì)被保留，最后根據(jù)算法產(chǎn)生的關(guān)聯(lián)規(guī)則分析事件相關(guān)性程度.

Apriori算法通過使用逐層搜索的迭代方法進(jìn)而發(fā)現(xiàn)頻繁項(xiàng)目集，每個(gè)x項(xiàng)目集是探索下一個(gè)項(xiàng)目集即(x+1)項(xiàng)集的依據(jù)，以此迭代直到求出符合最小支持度的最終頻繁項(xiàng)目集.Apriori算法的第一步是通過自連接獲取頻繁項(xiàng)目集的候選集，第一輪的候選集就是原始數(shù)據(jù)集A中的項(xiàng)，而剩下每一次的候選集則是由前一次獲得的頻繁項(xiàng)目集自連接得到，而頻繁項(xiàng)目集由候選集進(jìn)行剪枝得到；第二步是對(duì)候選集進(jìn)行剪枝，如果候選集的每一條記錄S的支持度小于預(yù)設(shè)的最小支持度，那么此記錄就會(huì)被自動(dòng)剪掉，另外，如果一條記錄的子集中包含不是頻繁項(xiàng)目集的記錄也會(huì)被剪掉；算法的終止條件是自連接得到的已經(jīng)不再是頻繁集，最后一次得到的頻繁項(xiàng)目集則為最終結(jié)果.所以，Apriori算法的具體流程為掃描事務(wù)記錄，找出所有存在的頻繁項(xiàng)目集1，記該項(xiàng)目集為K1，然后依據(jù)K1找頻繁項(xiàng)目集2的集合K2，K2找K3，以此類推，直到不能再找到任何頻繁x項(xiàng)目集，最后再在所有的頻繁項(xiàng)目集中找出強(qiáng)規(guī)則，得出關(guān)聯(lián)程度高的研究對(duì)象，產(chǎn)生客戶感興趣的關(guān)聯(lián)規(guī)則，用以指導(dǎo)實(shí)際的操作目的.算法操作步驟如下：

1)Begin

2)Scanning database and counting;

3)If 1階候選項(xiàng)目集>Minimum support

4) 則產(chǎn)生1階頻繁項(xiàng)目集;

5)Else delete

6)依此規(guī)則，迭代計(jì)算;

7)If 不再產(chǎn)生頻繁項(xiàng)目集

8) 則End;

9)Else 繼續(xù)迭代計(jì)算.

2 Apriori算法的改進(jìn)

由上述研究中闡述的流程可表明經(jīng)典的Apriori算法存在較大缺陷即算法效率問題，因?yàn)樵诜磸?fù)掃描數(shù)據(jù)庫(kù)的過程中有許多不必比較的項(xiàng)目或者項(xiàng)目集重復(fù)比較[15].在依據(jù)x階頻繁項(xiàng)目集產(chǎn)生x+1階候選頻繁項(xiàng)目集時(shí),會(huì)形成大量的冗余項(xiàng)集，所以在x+1階候選頻繁項(xiàng)目集中剪枝非頻繁項(xiàng)目集的步驟需要進(jìn)行改進(jìn)；在連接過程中相同的項(xiàng)目集重復(fù)使用多次，此步驟也需要進(jìn)行改進(jìn).

針對(duì)上述經(jīng)典Apriori算法的缺陷提出相應(yīng)的改進(jìn)方法：若某個(gè)元素要成為k維項(xiàng)目集中的一元素，該元素在k-1階頻繁項(xiàng)目集中的數(shù)量必須達(dá)到k-1個(gè)，否則不可能生成k維項(xiàng)目集.因此，在迭代搜索過程中，根據(jù)k-1步形成的k-1維頻繁項(xiàng)目集來產(chǎn)生k維候選項(xiàng)目集，并在形成k-1維頻繁項(xiàng)目集時(shí)對(duì)該項(xiàng)目集中的元素個(gè)數(shù)進(jìn)行計(jì)數(shù)處理，如若項(xiàng)目集元素的數(shù)量達(dá)不到k-1個(gè)則刪除該元素，從而能去除由該元素形成的大規(guī)格的所有項(xiàng)目集組合.根據(jù)以上改進(jìn)思路得到候選項(xiàng)目集后，可以對(duì)數(shù)據(jù)庫(kù)A中的每一個(gè)項(xiàng)目進(jìn)行掃描，若該項(xiàng)目中至少含有候選項(xiàng)目集Ck中的一元素則保留該項(xiàng)目，否則把該事物記錄與數(shù)據(jù)庫(kù)末端沒有作刪除的項(xiàng)目記錄進(jìn)行交換，并對(duì)移到數(shù)據(jù)庫(kù)末端的項(xiàng)目記錄作刪除標(biāo)記，整個(gè)數(shù)據(jù)庫(kù)掃描結(jié)束后產(chǎn)生新的事務(wù)數(shù)據(jù)庫(kù)D′.因此隨著k的增大，D′中項(xiàng)目記錄量極大地縮減，可直接節(jié)約輸入輸出開銷.在實(shí)際情況中，由于客戶一次一般可能只購(gòu)買幾件商品，因此這種方法可以剔除大量的交易記錄，并且在剩余的項(xiàng)目中做更高維的數(shù)據(jù)挖掘是可以節(jié)約大量的時(shí)間.下面為改進(jìn)的Apriori算法流程操作步驟：

1) Begin

2) Scanning database and counting;

3) If 1階候選項(xiàng)目集> Minimum support

4) 則產(chǎn)生1階頻繁項(xiàng)目集;

5) Else delete

6) 連接1階頻繁項(xiàng)目集產(chǎn)生2階候選項(xiàng)目集;

7) If 2階候選項(xiàng)目集>Minimum support

8) 則產(chǎn)生2階候選頻繁項(xiàng)目集;

9) Else delete

10)Counting 2階候選頻繁項(xiàng)目集中元素出現(xiàn)的次數(shù)；

11) If 出現(xiàn)次數(shù)>=2;

12) 則保留為2階頻繁項(xiàng)目集;

13) Else delete 此元素;

14) 依次規(guī)則，迭代計(jì)算;

15) If 不再產(chǎn)生頻繁項(xiàng)目集

16) 則End;

17) Else 繼續(xù)迭代計(jì)算.

3 改進(jìn)Apriori算法的應(yīng)用

本文根據(jù)Q卷煙配送中心客戶對(duì)倉(cāng)庫(kù)貨物的訂貨情況，運(yùn)用改進(jìn)后的Apriori算法分析客戶訂貨時(shí)的習(xí)慣訂貨行為與組合，幫助Q卷煙配送中心倉(cāng)庫(kù)部門提高出入庫(kù)效率，增加倉(cāng)庫(kù)的收益.

3.1 算法運(yùn)行

為了驗(yàn)證Apriori算法的有效性，將其運(yùn)用在分析Q卷煙配送中心倉(cāng)庫(kù)貨物品種的關(guān)聯(lián)性上，從而進(jìn)一步分析客戶訂貨時(shí)的習(xí)慣訂貨行為，指導(dǎo)倉(cāng)庫(kù)在貨物貨位入庫(kù)時(shí)能根據(jù)客戶的訂貨習(xí)慣將貨物品種關(guān)聯(lián)度高的貨物鄰近擺放，提高揀貨速度，縮短揀貨時(shí)間，增強(qiáng)倉(cāng)庫(kù)工作效率，給Q卷煙配送中心帶來良好的經(jīng)濟(jì)效益.表1為Q卷煙配送中心客戶一周的訂貨品種及數(shù)量，由于篇幅限制只截取部分訂貨數(shù)據(jù)，通過分析客戶一周訂貨表中的數(shù)據(jù)，運(yùn)用改進(jìn)的Apriori算法運(yùn)算得出客戶訂貨品種的關(guān)聯(lián)性.

實(shí)際數(shù)據(jù)信息如下：3 779個(gè)客戶，117類訂貨品種.而表1截取了部分客戶訂貨數(shù)據(jù)為5個(gè)客戶及23個(gè)品種的訂貨數(shù)量，空缺部分指客戶對(duì)此類貨物品種的訂貨數(shù)量為0.根據(jù)客戶數(shù)據(jù)以及改進(jìn)的Apriori算法，運(yùn)用Matlab對(duì)改進(jìn)的Apriori算法進(jìn)行編程求解出貨物品種的關(guān)聯(lián)度.設(shè)置支持度和置信度均為0.9，最大規(guī)則數(shù)為1000，得出如下部分關(guān)聯(lián)規(guī)則.

表2為關(guān)聯(lián)規(guī)則的部分截取表格，由算法挖掘得出關(guān)聯(lián)格則如表1可知，客戶訂t類貨物的同時(shí)也會(huì)訂z類貨物、s類貨物，訂z類貨物的同時(shí)也會(huì)訂s類和t類貨物；訂ai類貨物的同時(shí)也會(huì)訂s類、t類和z類，剩下的規(guī)則以此類推.根據(jù)以上的關(guān)聯(lián)規(guī)則將關(guān)聯(lián)度高的貨物放置在鄰近的貨位上，可以極大的縮短出入庫(kù)時(shí)間，提高倉(cāng)庫(kù)工作效率.

表1 客戶一周訂貨數(shù)據(jù)表(單位：條)

表2 關(guān)聯(lián)規(guī)則表

s->t,ai(94.7341%,96.159%)ag->t(91.3469%,99.8265%)s,ag->t(90.7912%,99.9417%)t->s,ai(94.7341%,95.5431%)s->t,bz(91.3205%,92.6941%)t,ag->s(90.7912%,99.3917%)ai->s,t(94.7341%,98.9771%)t->s,bz(91.3205%,92.1003%)s->z,ag(90.606%,91.9688%)s,t->ai(94.7341%,96.548%)bz->s,t(91.3205%,98.8259%)z->s,ag(90.606%,91.5508%)s,ai->t(94.7341%,99.9163%)s,t->bz(91.3205%,93.069%)ag->s,z(90.606%,99.0168%)t,ai->s(94.7341%,99.3065%)s,bz->t(91.3205%,99.8264%)s,z->ag(90.606%,92.5656%)s->z,ai(94.6017%,96.0247%)t,bz->s(91.3205%,99.3379%)s,ag->z(90.606%,99.7378%)z->s,ai(94.6017%,95.5882%)z->ag(91.2411%,92.1925%)z,ag->s(90.606%,99.3039%)ai->s,z(94.6017%,98.8388%)ag->z(91.2411%,99.7108%)s->t,z,ag(90.5531%,91.9151%)s,z->ai(94.6017%,96.6477%)s->z,bz(91.1617%,92.5329%)t->s,z,ag(90.5531%,91.3264%)

3.2 算法性能分析

改進(jìn)前后的算法支持度及置信度一致，但算法運(yùn)行的時(shí)間不同，改進(jìn)前的算法運(yùn)行時(shí)間為 57.537 951 s，改進(jìn)后的算法時(shí)間為20.323 541 s，算法運(yùn)行時(shí)間縮短了一半.這是因?yàn)轭l繁候選集出現(xiàn)后，都會(huì)事先進(jìn)行計(jì)數(shù)，如若本次頻繁候選集階數(shù)的數(shù)目不一致則刪除此候選集，大大縮短了項(xiàng)目記錄量，對(duì)于下一次事務(wù)掃描則可以節(jié)約輸入輸出開銷.因此，這種刪除方式可以實(shí)現(xiàn)大量的項(xiàng)目記錄在挖掘中被剔除出來，時(shí)間將呈倍數(shù)的減少.見圖1.

圖1 算法性能圖

4 結(jié) 語(yǔ)

本文運(yùn)用改進(jìn)的Apriori算法研究分析Q卷煙配送中心貨物品種的關(guān)聯(lián)度，介紹了傳統(tǒng)的Apriori算法在數(shù)據(jù)挖掘中的廣泛性和經(jīng)典性，說明其在商品搜索，數(shù)據(jù)引擎，市場(chǎng)營(yíng)銷中的作用，進(jìn)而分析在使用過程中Apriori算法存在缺陷使得算法效率低下，因此對(duì)傳統(tǒng)的Apriori算法進(jìn)行改進(jìn)，縮減項(xiàng)目元素，極大減少I/0開銷，算法效率得到提升.根據(jù)算法得到的關(guān)聯(lián)規(guī)則可以分析得出Q卷煙配送中心倉(cāng)庫(kù)貨物品種的關(guān)聯(lián)度，再依據(jù)預(yù)先設(shè)定的支持度和置信度確定客戶在訂貨時(shí)購(gòu)買一種貨物品種后，極有可能會(huì)購(gòu)買哪種貨物品種，由此指導(dǎo)Q卷煙配送中心倉(cāng)庫(kù)部門貨物擺放，將關(guān)聯(lián)度高的貨物品種放置在臨近的位置，縮短找貨拿取時(shí)間，提高出入庫(kù)效率，從而增加Q卷煙配送中心的經(jīng)濟(jì)效益.今后可以根據(jù)周轉(zhuǎn)率以及車輛容量限制等分析具體的貨位分配，周轉(zhuǎn)率高的貨物組合可放置離出入口近的貨架，以此類推.