- 相關(guān)推薦
小議序列模式挖掘在物流中的應(yīng)用
摘 要： 當前第三方物流管理系統(tǒng)中以物流活動為對象的數(shù)據(jù)庫龐大， 難以發(fā)現(xiàn)有價值數(shù)據(jù)。為此， 本文提出一種針對物流數(shù)據(jù)分析的經(jīng)典方法： IGSP( improved sequential pa tterns)算法。該方法通過對原始序列數(shù)據(jù)庫篩選， 選出路徑序列長度大于或等于候選序列長度的路徑序列， 進而有針對性地產(chǎn)生過度候選序列， 經(jīng)約減產(chǎn)生候選序列。利用這種產(chǎn)生候選序列的方式， 能夠有效地減少候選序列數(shù)量，進而產(chǎn)生物流中有意義的規(guī)則。案例和理論分析表明， 該方法不僅縮小了掃描數(shù)據(jù)庫的規(guī)模， 而且減少了生成頻繁序列的候選序列集合。
關(guān)鍵詞： 物流管理系統(tǒng); 數(shù)據(jù)挖掘; 關(guān)聯(lián)規(guī)則; 序列模式挖掘
1 引言
目前， 數(shù)據(jù)挖掘技術(shù)[ 1] 正以前所未有的速度發(fā)展， 已廣泛應(yīng)用于政府、電力、企業(yè)、電信、金融等行業(yè)部門， 而在物流行業(yè)的應(yīng)用還不是很普遍。隨著物流信息化水平的提高， 物流戰(zhàn)略已從內(nèi)部一體化向外部一體化轉(zhuǎn)變， 供應(yīng)鏈管理已成為競爭戰(zhàn)略中非常重要的組成部分， 信息化物流網(wǎng)絡(luò)體系的應(yīng)用使數(shù)據(jù)規(guī)模不斷擴大， 產(chǎn)生巨大數(shù)據(jù)流， 使企業(yè)很難對這些數(shù)據(jù)進行高效的收集和及時決策。數(shù)據(jù)挖掘方法有效地促進企業(yè)的業(yè)務(wù)處理過程重組， 改善并強化對客戶的服務(wù)， 實現(xiàn)企業(yè)規(guī)模優(yōu)化， 有效地提高企業(yè)的競爭力。因此， 通過數(shù)據(jù)挖掘技術(shù)分析物流中的貨物流向， 對于物流企業(yè)或者物流用戶都有著至關(guān)重要的意義。
數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則技術(shù)[ 2, 3] 能夠有效地發(fā)現(xiàn)數(shù)據(jù)間的聯(lián)系， 根據(jù)已有數(shù)據(jù)預測未來發(fā)展趨勢。因此， 將關(guān)聯(lián)規(guī)則技術(shù)應(yīng)用在貨物流向分析[ 4] 中， 將產(chǎn)生一定影響。目前， 關(guān)于序列模式挖掘的研究已有很多。如基于垂直格式的候選碼生成- 測試的方法- SPADE 算法[5] ;基于模式增長的方法- prefixspan算法[ 6] 等， 還有分布式環(huán)境下序列模式挖掘算法- FMGSP[ 7] 和FMGMFI[ 8] 等。
但經(jīng)典GSP算法[9] 是產(chǎn)生關(guān)聯(lián)規(guī)則最有影響力的算法，該算法是基于Aprio ri算法的候選碼生成與測試的方法，該方法實現(xiàn)對時間約束數(shù)據(jù)(如： 規(guī)定時間的貨物運送目的地) 的挖掘， 產(chǎn)生頻繁序列， 進而生成規(guī)則。但是， GSP算法有它的缺點[ 10] :
第一，在大型數(shù)據(jù)庫中會有相當多的候選序列產(chǎn)生。因為序列中的元素是有序的，所以不同元素的交換就會產(chǎn)生很多不同的序列， 而且項目也可以是重復的， 產(chǎn)生的候選2- 序列就一共有5個： < ab> , < ba> , < aa> , < bb> , < ( ab) > 。
第二，在挖掘過程中要多次掃描數(shù)據(jù)庫。候選序列的長度每增加1,就需要掃描1次數(shù)據(jù)庫。通常， 要找出長度為L的頻繁序列， 至少要掃描L次數(shù)據(jù)庫。
第三， 在挖掘長模式時， 會產(chǎn)生巨大的候選序列。一個長模式包含很多的子模式， 每個子模式都需要生成-測試， 這將導致候選序列的數(shù)量隨著需要挖掘的序列模式的長度呈指數(shù)級增長。
為此， 本文以物流貨物流向分析為背景提出了GSP算法的改進算法IGSP算法。該算法在產(chǎn)生各個不同長度的候選序列過程中， 首先對原序列數(shù)據(jù)庫進行篩選， 選出序列長度大于或等于候選序列長度的序列， 進而有針對性地對這些序列產(chǎn)生過渡候選序列， 經(jīng)過aprior i性質(zhì)約減后產(chǎn)生候選序列。通過這種方法大大減少了候選序列的數(shù)量， 而且也降低了對于原始數(shù)據(jù)庫的掃描次數(shù)， 能夠有效地生成頻繁序列。
2 物流信息挖掘過程
在物流決策支持系統(tǒng)中首先明確挖掘的目標就是發(fā)現(xiàn)在未來物流市場上的貨物流向， 物流用戶通過該決策支持系統(tǒng)可以發(fā)現(xiàn)不同的貨主選擇把同樣的一批貨物分別運往的目的， 而物流企業(yè)可以通過物流決策支持系統(tǒng)發(fā)現(xiàn)未來的物流市場可能出現(xiàn)的變動。物流信息挖掘整個過程。
2. 1 物流信息挖掘的數(shù)據(jù)預處理和收集物流信息挖掘收集了第三方物流管理信息系統(tǒng)中的關(guān)于物流活動的大量數(shù)據(jù)。而這些數(shù)據(jù)的數(shù)據(jù)源并不相同， 為了操作方便， 把這些數(shù)據(jù)集成于數(shù)據(jù)倉庫中。在第三方物流管理信息系統(tǒng)中， 隨著物流活動的不斷發(fā)生， 從中得到的數(shù)據(jù)集也會越來越大， 因此選定數(shù)據(jù)在挖掘前，必須加以精煉處理， 辨別出需要進行分析的數(shù)據(jù)集合， 縮小挖掘范圍， 避免盲目搜索， 提高數(shù)據(jù)挖掘的效率和質(zhì)量( 見圖1數(shù)據(jù)準備和數(shù)據(jù)采集階段)。
2. 2 物流信息挖掘的結(jié)果解釋和評估將可視化工具與挖掘工具結(jié)合起來， 把每次的分析結(jié)果清晰、準確、明了的表達出來。物流決策支持系統(tǒng)經(jīng)物流用戶和物流企業(yè)使用以后， 根據(jù)用戶反饋進行結(jié)果評估( 見圖1結(jié)果表達階段)。
3 物流信息挖掘算法- IGSP算法
序列模式挖掘算法GSP是基于aprior i算法。首先通過掃描原始數(shù)據(jù)庫找出所有的頻繁1 - 序列; 然后利用連接操作通過頻繁1- 序列產(chǎn)生候選2- 序列， 再次掃描數(shù)據(jù)庫計數(shù)候選序列， 找出滿足最小支持度的頻繁2 - 序列; 用頻繁k- 序列( k! 2)產(chǎn)生候選k+ 1- 序列， 掃描數(shù)據(jù)庫找出頻繁k+ 1 序列; 重復這個操作， 直到?jīng)]有候選序列產(chǎn)生為止。該算法雖然通過aprio ri性質(zhì)進行了大幅度壓縮， 但仍避免不了頻繁掃描整個數(shù)據(jù)庫進行支持度的計算， 因此降低了整個算法的效率。
本文提出的算法IGSP, 無論是在候選序列數(shù)目上還是掃描數(shù)據(jù)庫次數(shù)上都有很大改進。算法IGSP利用序列數(shù)據(jù)庫S產(chǎn)生長度為1 的候選序列C1, 然后掃描數(shù)據(jù)庫S, 對C1 中每個項的出現(xiàn)次數(shù)計數(shù)， 確定頻繁1- 序列L1, 同時將不滿足最小支持度條件的項從S 中刪除， 并且將項數(shù)少于2的序列從S中刪除， 產(chǎn)生過渡候選2- 序列C? 2, 然后由C? 2 產(chǎn)生長度為2的候選序列C2�？梢奍G??
SP算法第一次遍歷原始數(shù)據(jù)庫之后就不再掃描原始數(shù)據(jù)庫來計算支持度， 而通過過渡序列集合C? k計算， 并且利用頻繁序列Lk- 1對C? k進行篩選， 將不符合最小支持度的元素從C? k中刪除， 最后將項數(shù)小于或等于( k- 1)的事務(wù)刪除以縮小C? k。這樣大大減少了候選2 - 序列C2 數(shù)目， 有效的縮減序列數(shù)據(jù)庫， 并減少了掃描原始數(shù)據(jù)庫的次數(shù)， 提高了算法效率。
IGSP算法形式化描述如下(略， 備索)。
4 案例分析
數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則技術(shù)就是發(fā)現(xiàn)事物之間有意義的聯(lián)系和規(guī)則， 能夠從事物數(shù)據(jù)庫、關(guān)系數(shù)據(jù)庫和其它數(shù)據(jù)存儲中的大量數(shù)據(jù)的項集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。因此， 利用關(guān)聯(lián)規(guī)則技術(shù)可以對物流中的路徑數(shù)據(jù)進行分析、挖掘， 找出頻繁出現(xiàn)的路徑信息， 以發(fā)現(xiàn)物流市場上的貨物流向及未來可能出現(xiàn)的變動。
支持度： 表示規(guī)則出現(xiàn)的頻度， support( A# B ) = P( A? B) 。
如80%的鋼材鐵板都要裝到45英尺的集裝箱里， 則定義45英尺的集裝箱的支持度為80%。
置信度： 表示規(guī)則的強度， confidence( A# B) = P( B |A) 。
如60%的40英尺的集裝箱可以同時裝A、B、C 三種貨物， 則可以定義這樣一條規(guī)則： 裝有貨物A、B 的集裝箱可以同時裝C, 則稱裝有貨物A、B 的集裝箱可以同時裝C的置信度為60%。
挖掘貨物路徑規(guī)則大概可以分為兩步： 第一， 找出所有的頻繁路徑序列。這部分由本文提出的IMGSP算法來解決。第二， 由頻繁路徑序列來生成相關(guān)聯(lián)的路徑規(guī)則。
這些規(guī)則需滿足最小支持度和最小置信度。
在第三方物流管理信息系統(tǒng)中， 數(shù)據(jù)庫D 為第三方物流管理信息系統(tǒng)中的物流活動數(shù)據(jù)庫。由于數(shù)據(jù)較多， 這里所給出的數(shù)據(jù)表中只列出了部分數(shù)據(jù)， 見表1。
表中列出了幾個屬性進行關(guān)聯(lián)規(guī)則挖掘， 這里只對物流企業(yè)管理系統(tǒng)來加以說明。假設(shè)物流企業(yè)對貨物A進行操作， 考慮時間和用戶編號等相關(guān)屬性， 收集路徑信息，轉(zhuǎn)換后得到路徑序列數(shù)據(jù)庫。
假設(shè)最小支持計數(shù)為2, 對轉(zhuǎn)換后的路徑序列數(shù)據(jù)庫采用IGSP算法挖掘頻繁路徑， 則算法的挖掘過程如下所示：
首先掃描整個序列數(shù)據(jù)庫- 表2, 對每個項計數(shù)， 產(chǎn)生長度為1的候選序列C1, 見表3。因為天津、重慶不滿足用戶規(guī)定的最小支持度， 所以生成長度為1 的頻繁序列L1 時要去掉天津、重慶， 根據(jù)算法IGSP更新路徑數(shù)據(jù)庫， 刪除包括天津、重慶的項， L1見表4。其中， SID 為1的路徑序列中去掉天津， 就成為只有一個元素的序列， 不應(yīng)該出現(xiàn)在C2 中， 故刪除S ID為1的路徑序列。同樣， 將SID為3的路徑序列縮減為包含3個元素的序列; 然后生成長度為2的過渡候選路徑序列集合C? 2, 見表5。根據(jù)性質(zhì)1和過渡候選路徑序列集合C? 2 中路徑序列出現(xiàn)次數(shù)生成長度為2的候選序列集合C2, 見表6( 略， 備索)。
在C2 中{ 上海， 南京} {廣州， 上海} {上海， 廣州} {南京，廣州} 不滿足最小支持度， 去除{上海， 南京} {廣州， 上海} {上海， 廣州} {南京， 廣州}生成長度為2的頻繁路徑序列L2, 見表7 (略， 備索)。根據(jù)算法IGSP從C? 2 中刪除包含{上海， 南京} { 廣州， 上海} { 上海， 廣州} {南京，廣州} 的項， 其中SID為2的路徑序列只包含2 個元素，SID為3的路徑序列也只包含2個元素， 而SID 為5的路徑序列只包含一個元素， 都不應(yīng)該被包含在C3 中， 故刪除S ID為2, 3和5的路徑序列， 根據(jù)算法IGSP生成長度為3的過渡候選路徑序列集合C? 3, 見表8(略， 備索) ; 然后根據(jù)性質(zhì)1和C? 3 中路徑序列出現(xiàn)次數(shù)生成C3, 見表9( 略， 備索) , 因不滿足最小支持度， 所有沒有長度為3的頻繁路徑序列產(chǎn)生， 挖掘過程結(jié)束。
分析： 算法IGSP能夠有針對性地產(chǎn)生過渡候選路徑序列， 通過aprior i性質(zhì)進一步篩選產(chǎn)生候選序列， 大大減少了候選序列的數(shù)量。如表5產(chǎn)生的過渡候選2 - 序列數(shù)目為10, 經(jīng)過篩選后產(chǎn)生候選2- 序列數(shù)目為7。假設(shè)采用算法GSP挖掘路徑數(shù)據(jù)庫表2, 產(chǎn)生候選- 2序列：
{ 北京， 廣州} {北京， 上海} {北京， 南京} {廣州， 上海} {廣州， 南京} {上海， 南京} { 廣州， 北京} {上海， 北京} { 南京，北京} {上海， 廣州} {南京， 廣州} {南京， 上海} { (北京， 廣州) } { ( 北京， 上海) } { ( 北京， 南京) } { (廣州， 上海) }
{ (廣州， 南京) } { ( 上海， 南京) } { 北京， 北京} { 上海， 上海} {廣州， 廣州} { 南京， 南京}, 共22 個2 - 候選序列。
相比之下， 算法IGSP能夠大大約減候選序列， 尤其是候選2- 序列。不僅如此， 算法IGSP在整個挖掘過程中， 僅需要掃描數(shù)據(jù)庫一次， 后面統(tǒng)計計數(shù)只需統(tǒng)計過渡候選序列即可， 減少了掃描原始數(shù)據(jù)庫的次數(shù)， 降低了I/O開銷。
5 結(jié)論
本文針對物流信息管理系統(tǒng)中貨物流向分析這一需求， 提出了物流信息挖掘算法- IGSP算法。IGSP算法基于經(jīng)典算法GSP算法改進而來， 首先根據(jù)頻繁k - 序列Lk更新數(shù)據(jù)庫， 刪除長度小于k + 1的路徑序列， 然后生成過度候選序列C? k+ 1, 進而通過aprior i性質(zhì)篩選產(chǎn)生候選序列Ck+ 1, 這樣能夠有針對性地產(chǎn)生候選序列， 大大減少了候選序列數(shù)目， 尤其是候選2- 序列。不僅如此， 算法IGSP還減少了掃描數(shù)據(jù)庫的次數(shù)， 有效地降低了I /O操作成本。雖然該算法在產(chǎn)生候選序列方面已大大壓縮， 但是當數(shù)據(jù)庫中的路徑序列長度變得很大時， 該算法仍將會產(chǎn)生很多候選碼， 效率就會相應(yīng)降低， 這也正是將本算法應(yīng)用在物流貨物流向分析而不是生物DNA分析方面的原因(路徑序列長度不像DNA序列那樣長)。
為此以后工作中， 我們將提出最大頻繁序列模式這個概念， 最大頻繁項目集中已經(jīng)隱含了所有頻繁項目集， 所以可把發(fā)現(xiàn)頻繁項目集的問題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項目集的問題。另外， 某些數(shù)據(jù)挖掘應(yīng)用僅需發(fā)現(xiàn)最大頻繁項目集， 而不必發(fā)現(xiàn)所有的頻繁項目集， 因而發(fā)現(xiàn)最大頻繁項目集對數(shù)據(jù)挖掘具有重大意義。
參考文獻：
[ 1] HAN J, KAMBER M. Data m ining C oncep ts and T echniques S econd Edition [M] . 北京： 北京機械工業(yè)出版社，2006
[ 2] PARKJ S, PSY U. An effic ient parallel data m in ing fo rassoc ia tion rules [ C ] Proc. of the 4th on In fo rm ation andKnow ledg eM anag em ent, New York: ACM Press, 1995: 31~ 36
[ 3] CH EUNG D W, HAN J, NG V T, e t a .l A fast d istr ibuted a lgo rithm for m in ing asso ciation ru les[ A]. Proc. o f the4th Interna tiona l Con ference on Parallel and D istr ibuted In fo ation System s. Los A lam itos, Ca.l , USA: IEEE Compu terSoc iety Press, 1996: 31~ 44
[ 4]徐曉飛， 鄧勝春。 基于關(guān)聯(lián)規(guī)則的零部件供應(yīng)商選擇優(yōu)化[ J] . 計算機集成制造系統(tǒng)， 2004, 10( 3) : 13~ 16
[ 5] ZAK IM. Spade: An e fficient a lgo rithm for m ining frequent sequences [ J]. M ach ine Learning, 2001, 41( 2) : 31~ 60
[ 6] PE I. J, HAN J, PINTO. H, et a.l U, & Pre fixSpan:
M in ing Sequential Patterns E ffic iently by Pre fix - ProjectedPa ttern Grow th?, IEEE T ransactions on Know ledge & Da taEng ineering, Vo .l 16, No. 1, pp. 1424 ~ 1440, January,2004
[ 7] Zhang Changha,i H u Kong fa, L iu H a idong, et a.l FMG??
SP: An E fficientM e thod o fM in ing G loba l Sequentia l Patterns[ C ]. In: Pro c o f the 4 th International Conference on fuzzysystem s and know ledg e discovery. H a inan, Ch ina: IEEECom puter So ciety, 2007: 761~ 765
[ 8]陸介平， 楊明， 孫志揮等。 快速挖掘全局最大頻繁項目集[ J] . 軟件學報， 2005, 16( 4)： 553~ 560
[ 9] SRIKANT R, AGRAWAL R. M in ing sequentia l patterns: Genera lizations and perform ance improvem ents. [ C ].
Proc. of 5th Internationa l Conference on Ex tending DatabaseTechno logy, H e idelberg: Springer, 1996: 3~ 17
[ 10]張長海， 胡孔法， 陳崚。 序列模式挖掘算法綜述[ J].揚州大學學報， 2007, 10( 1) : 41~ 46
【小議序列模式挖掘在物流中的應(yīng)用】相關(guān)文章：
淺談JIT模式在電網(wǎng)公司物流中的應(yīng)用10-26
網(wǎng)絡(luò)營銷中數(shù)據(jù)挖掘技術(shù)的應(yīng)用10-07
旅游管理中的情景模式應(yīng)用論文10-08
數(shù)據(jù)挖掘在電子商務(wù)管理中的應(yīng)用論文10-09
計算機應(yīng)用基礎(chǔ)教學在合作學習模式在中的應(yīng)用10-07
合作學習模式在初中數(shù)學中的應(yīng)用論文10-11