- 相關(guān)推薦
小議序列模式挖掘在物流中的應(yīng)用
摘 要： 當(dāng)前第三方物流管理系統(tǒng)中以物流活動(dòng)為對(duì)象的數(shù)據(jù)庫(kù)龐大， 難以發(fā)現(xiàn)有價(jià)值數(shù)據(jù)。為此， 本文提出一種針對(duì)物流數(shù)據(jù)分析的經(jīng)典方法： IGSP( improved sequential pa tterns)算法。該方法通過對(duì)原始序列數(shù)據(jù)庫(kù)篩選， 選出路徑序列長(zhǎng)度大于或等于候選序列長(zhǎng)度的路徑序列， 進(jìn)而有針對(duì)性地產(chǎn)生過度候選序列， 經(jīng)約減產(chǎn)生候選序列。利用這種產(chǎn)生候選序列的方式， 能夠有效地減少候選序列數(shù)量，進(jìn)而產(chǎn)生物流中有意義的規(guī)則。案例和理論分析表明， 該方法不僅縮小了掃描數(shù)據(jù)庫(kù)的規(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)鏈管理已成為競(jìng)爭(zhēng)戰(zhàn)略中非常重要的組成部分， 信息化物流網(wǎng)絡(luò)體系的應(yīng)用使數(shù)據(jù)規(guī)模不斷擴(kuò)大， 產(chǎn)生巨大數(shù)據(jù)流， 使企業(yè)很難對(duì)這些數(shù)據(jù)進(jìn)行高效的收集和及時(shí)決策。數(shù)據(jù)挖掘方法有效地促進(jìn)企業(yè)的業(yè)務(wù)處理過程重組， 改善并強(qiáng)化對(duì)客戶的服務(wù)， 實(shí)現(xiàn)企業(yè)規(guī)模優(yōu)化， 有效地提高企業(yè)的競(jìng)爭(zhēng)力。因此， 通過數(shù)據(jù)挖掘技術(shù)分析物流中的貨物流向， 對(duì)于物流企業(yè)或者物流用戶都有著至關(guān)重要的意義。
數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則技術(shù)[ 2, 3] 能夠有效地發(fā)現(xiàn)數(shù)據(jù)間的聯(lián)系， 根據(jù)已有數(shù)據(jù)預(yù)測(cè)未來發(fā)展趨勢(shì)。因此， 將關(guān)聯(lián)規(guī)則技術(shù)應(yīng)用在貨物流向分析[ 4] 中， 將產(chǎn)生一定影響。目前， 關(guān)于序列模式挖掘的研究已有很多。如基于垂直格式的候選碼生成- 測(cè)試的方法- SPADE 算法[5] ;基于模式增長(zhǎng)的方法- prefixspan算法[ 6] 等， 還有分布式環(huán)境下序列模式挖掘算法- FMGSP[ 7] 和FMGMFI[ 8] 等。
但經(jīng)典GSP算法[9] 是產(chǎn)生關(guān)聯(lián)規(guī)則最有影響力的算法，該算法是基于Aprio ri算法的候選碼生成與測(cè)試的方法，該方法實(shí)現(xiàn)對(duì)時(shí)間約束數(shù)據(jù)(如： 規(guī)定時(shí)間的貨物運(yùn)送目的地) 的挖掘， 產(chǎn)生頻繁序列， 進(jìn)而生成規(guī)則。但是， GSP算法有它的缺點(diǎn)[ 10] :
第一，在大型數(shù)據(jù)庫(kù)中會(huì)有相當(dāng)多的候選序列產(chǎn)生。因?yàn)樾蛄兄械脑厥怯行虻�，所以不同元素的交換就會(huì)產(chǎn)生很多不同的序列， 而且項(xiàng)目也可以是重復(fù)的， 產(chǎn)生的候選2- 序列就一共有5個(gè)： < ab> , < ba> , < aa> , < bb> , < ( ab) > 。
第二，在挖掘過程中要多次掃描數(shù)據(jù)庫(kù)。候選序列的長(zhǎng)度每增加1,就需要掃描1次數(shù)據(jù)庫(kù)。通常， 要找出長(zhǎng)度為L(zhǎng)的頻繁序列， 至少要掃描L次數(shù)據(jù)庫(kù)。
第三， 在挖掘長(zhǎng)模式時(shí)， 會(huì)產(chǎn)生巨大的候選序列。一個(gè)長(zhǎng)模式包含很多的子模式， 每個(gè)子模式都需要生成-測(cè)試， 這將導(dǎo)致候選序列的數(shù)量隨著需要挖掘的序列模式的長(zhǎng)度呈指數(shù)級(jí)增長(zhǎng)。
為此， 本文以物流貨物流向分析為背景提出了GSP算法的改進(jìn)算法IGSP算法。該算法在產(chǎn)生各個(gè)不同長(zhǎng)度的候選序列過程中， 首先對(duì)原序列數(shù)據(jù)庫(kù)進(jìn)行篩選， 選出序列長(zhǎng)度大于或等于候選序列長(zhǎng)度的序列， 進(jìn)而有針對(duì)性地對(duì)這些序列產(chǎn)生過渡候選序列， 經(jīng)過aprior i性質(zhì)約減后產(chǎn)生候選序列。通過這種方法大大減少了候選序列的數(shù)量， 而且也降低了對(duì)于原始數(shù)據(jù)庫(kù)的掃描次數(shù)， 能夠有效地生成頻繁序列。
2 物流信息挖掘過程
在物流決策支持系統(tǒng)中首先明確挖掘的目標(biāo)就是發(fā)現(xiàn)在未來物流市場(chǎng)上的貨物流向， 物流用戶通過該決策支持系統(tǒng)可以發(fā)現(xiàn)不同的貨主選擇把同樣的一批貨物分別運(yùn)往的目的， 而物流企業(yè)可以通過物流決策支持系統(tǒng)發(fā)現(xiàn)未來的物流市場(chǎng)可能出現(xiàn)的變動(dòng)。物流信息挖掘整個(gè)過程。
2. 1 物流信息挖掘的數(shù)據(jù)預(yù)處理和收集物流信息挖掘收集了第三方物流管理信息系統(tǒng)中的關(guān)于物流活動(dòng)的大量數(shù)據(jù)。而這些數(shù)據(jù)的數(shù)據(jù)源并不相同， 為了操作方便， 把這些數(shù)據(jù)集成于數(shù)據(jù)倉(cāng)庫(kù)中。在第三方物流管理信息系統(tǒng)中， 隨著物流活動(dòng)的不斷發(fā)生， 從中得到的數(shù)據(jù)集也會(huì)越來越大， 因此選定數(shù)據(jù)在挖掘前，必須加以精煉處理， 辨別出需要進(jìn)行分析的數(shù)據(jù)集合， 縮小挖掘范圍， 避免盲目搜索， 提高數(shù)據(jù)挖掘的效率和質(zhì)量( 見圖1數(shù)據(jù)準(zhǔn)備和數(shù)據(jù)采集階段)。
2. 2 物流信息挖掘的結(jié)果解釋和評(píng)估將可視化工具與挖掘工具結(jié)合起來， 把每次的分析結(jié)果清晰、準(zhǔn)確、明了的表達(dá)出來。物流決策支持系統(tǒng)經(jīng)物流用戶和物流企業(yè)使用以后， 根據(jù)用戶反饋進(jìn)行結(jié)果評(píng)估( 見圖1結(jié)果表達(dá)階段)。
3 物流信息挖掘算法- IGSP算法
序列模式挖掘算法GSP是基于aprior i算法。首先通過掃描原始數(shù)據(jù)庫(kù)找出所有的頻繁1 - 序列; 然后利用連接操作通過頻繁1- 序列產(chǎn)生候選2- 序列， 再次掃描數(shù)據(jù)庫(kù)計(jì)數(shù)候選序列， 找出滿足最小支持度的頻繁2 - 序列; 用頻繁k- 序列( k! 2)產(chǎn)生候選k+ 1- 序列， 掃描數(shù)據(jù)庫(kù)找出頻繁k+ 1 序列; 重復(fù)這個(gè)操作， 直到?jīng)]有候選序列產(chǎn)生為止。該算法雖然通過aprio ri性質(zhì)進(jìn)行了大幅度壓縮， 但仍避免不了頻繁掃描整個(gè)數(shù)據(jù)庫(kù)進(jìn)行支持度的計(jì)算， 因此降低了整個(gè)算法的效率。
本文提出的算法IGSP, 無論是在候選序列數(shù)目上還是掃描數(shù)據(jù)庫(kù)次數(shù)上都有很大改進(jìn)。算法IGSP利用序列數(shù)據(jù)庫(kù)S產(chǎn)生長(zhǎng)度為1 的候選序列C1, 然后掃描數(shù)據(jù)庫(kù)S, 對(duì)C1 中每個(gè)項(xiàng)的出現(xiàn)次數(shù)計(jì)數(shù)， 確定頻繁1- 序列L1, 同時(shí)將不滿足最小支持度條件的項(xiàng)從S 中刪除， 并且將項(xiàng)數(shù)少于2的序列從S中刪除， 產(chǎn)生過渡候選2- 序列C? 2, 然后由C? 2 產(chǎn)生長(zhǎng)度為2的候選序列C2�？梢奍G??
SP算法第一次遍歷原始數(shù)據(jù)庫(kù)之后就不再掃描原始數(shù)據(jù)庫(kù)來計(jì)算支持度， 而通過過渡序列集合C? k計(jì)算， 并且利用頻繁序列Lk- 1對(duì)C? k進(jìn)行篩選， 將不符合最小支持度的元素從C? k中刪除， 最后將項(xiàng)數(shù)小于或等于( k- 1)的事務(wù)刪除以縮小C? k。這樣大大減少了候選2 - 序列C2 數(shù)目， 有效的縮減序列數(shù)據(jù)庫(kù)， 并減少了掃描原始數(shù)據(jù)庫(kù)的次數(shù)， 提高了算法效率。
IGSP算法形式化描述如下(略， 備索)。
4 案例分析
數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則技術(shù)就是發(fā)現(xiàn)事物之間有意義的聯(lián)系和規(guī)則， 能夠從事物數(shù)據(jù)庫(kù)、關(guān)系數(shù)據(jù)庫(kù)和其它數(shù)據(jù)存儲(chǔ)中的大量數(shù)據(jù)的項(xiàng)集之間發(fā)現(xiàn)有趣的、頻繁出現(xiàn)的模式、關(guān)聯(lián)和相關(guān)性。因此， 利用關(guān)聯(lián)規(guī)則技術(shù)可以對(duì)物流中的路徑數(shù)據(jù)進(jìn)行分析、挖掘， 找出頻繁出現(xiàn)的路徑信息， 以發(fā)現(xiàn)物流市場(chǎng)上的貨物流向及未來可能出現(xiàn)的變動(dòng)。
支持度： 表示規(guī)則出現(xiàn)的頻度， support( A# B ) = P( A? B) 。
如80%的鋼材鐵板都要裝到45英尺的集裝箱里， 則定義45英尺的集裝箱的支持度為80%。
置信度： 表示規(guī)則的強(qiáng)度， confidence( A# B) = P( B |A) 。
如60%的40英尺的集裝箱可以同時(shí)裝A、B、C 三種貨物， 則可以定義這樣一條規(guī)則： 裝有貨物A、B 的集裝箱可以同時(shí)裝C, 則稱裝有貨物A、B 的集裝箱可以同時(shí)裝C的置信度為60%。
挖掘貨物路徑規(guī)則大概可以分為兩步： 第一， 找出所有的頻繁路徑序列。這部分由本文提出的IMGSP算法來解決。第二， 由頻繁路徑序列來生成相關(guān)聯(lián)的路徑規(guī)則。
這些規(guī)則需滿足最小支持度和最小置信度。
在第三方物流管理信息系統(tǒng)中， 數(shù)據(jù)庫(kù)D 為第三方物流管理信息系統(tǒng)中的物流活動(dòng)數(shù)據(jù)庫(kù)。由于數(shù)據(jù)較多， 這里所給出的數(shù)據(jù)表中只列出了部分?jǐn)?shù)據(jù)， 見表1。
表中列出了幾個(gè)屬性進(jìn)行關(guān)聯(lián)規(guī)則挖掘， 這里只對(duì)物流企業(yè)管理系統(tǒng)來加以說明。假設(shè)物流企業(yè)對(duì)貨物A進(jìn)行操作， 考慮時(shí)間和用戶編號(hào)等相關(guān)屬性， 收集路徑信息，轉(zhuǎn)換后得到路徑序列數(shù)據(jù)庫(kù)。
假設(shè)最小支持計(jì)數(shù)為2, 對(duì)轉(zhuǎn)換后的路徑序列數(shù)據(jù)庫(kù)采用IGSP算法挖掘頻繁路徑， 則算法的挖掘過程如下所示：
首先掃描整個(gè)序列數(shù)據(jù)庫(kù)- 表2, 對(duì)每個(gè)項(xiàng)計(jì)數(shù)， 產(chǎn)生長(zhǎng)度為1的候選序列C1, 見表3。因?yàn)樘旖颉⒅貞c不滿足用戶規(guī)定的最小支持度， 所以生成長(zhǎng)度為1 的頻繁序列L1 時(shí)要去掉天津、重慶， 根據(jù)算法IGSP更新路徑數(shù)據(jù)庫(kù)， 刪除包括天津、重慶的項(xiàng)， L1見表4。其中， SID 為1的路徑序列中去掉天津， 就成為只有一個(gè)元素的序列， 不應(yīng)該出現(xiàn)在C2 中， 故刪除S ID為1的路徑序列。同樣， 將SID為3的路徑序列縮減為包含3個(gè)元素的序列; 然后生成長(zhǎng)度為2的過渡候選路徑序列集合C? 2, 見表5。根據(jù)性質(zhì)1和過渡候選路徑序列集合C? 2 中路徑序列出現(xiàn)次數(shù)生成長(zhǎng)度為2的候選序列集合C2, 見表6( 略， 備索)。
在C2 中{ 上海， 南京} {廣州， 上海} {上海， 廣州} {南京，廣州} 不滿足最小支持度， 去除{上海， 南京} {廣州， 上海} {上海， 廣州} {南京， 廣州}生成長(zhǎng)度為2的頻繁路徑序列L2, 見表7 (略， 備索)。根據(jù)算法IGSP從C? 2 中刪除包含{上海， 南京} { 廣州， 上海} { 上海， 廣州} {南京，廣州} 的項(xiàng)， 其中SID為2的路徑序列只包含2 個(gè)元素，SID為3的路徑序列也只包含2個(gè)元素， 而SID 為5的路徑序列只包含一個(gè)元素， 都不應(yīng)該被包含在C3 中， 故刪除S ID為2, 3和5的路徑序列， 根據(jù)算法IGSP生成長(zhǎng)度為3的過渡候選路徑序列集合C? 3, 見表8(略， 備索) ; 然后根據(jù)性質(zhì)1和C? 3 中路徑序列出現(xiàn)次數(shù)生成C3, 見表9( 略， 備索) , 因不滿足最小支持度， 所有沒有長(zhǎng)度為3的頻繁路徑序列產(chǎn)生， 挖掘過程結(jié)束。
分析： 算法IGSP能夠有針對(duì)性地產(chǎn)生過渡候選路徑序列， 通過aprior i性質(zhì)進(jìn)一步篩選產(chǎn)生候選序列， 大大減少了候選序列的數(shù)量。如表5產(chǎn)生的過渡候選2 - 序列數(shù)目為10, 經(jīng)過篩選后產(chǎn)生候選2- 序列數(shù)目為7。假設(shè)采用算法GSP挖掘路徑數(shù)據(jù)庫(kù)表2, 產(chǎn)生候選- 2序列：
{ 北京， 廣州} {北京， 上海} {北京， 南京} {廣州， 上海} {廣州， 南京} {上海， 南京} { 廣州， 北京} {上海， 北京} { 南京，北京} {上海， 廣州} {南京， 廣州} {南京， 上海} { (北京， 廣州) } { ( 北京， 上海) } { ( 北京， 南京) } { (廣州， 上海) }
{ (廣州， 南京) } { ( 上海， 南京) } { 北京， 北京} { 上海， 上海} {廣州， 廣州} { 南京， 南京}, 共22 個(gè)2 - 候選序列。
相比之下， 算法IGSP能夠大大約減候選序列， 尤其是候選2- 序列。不僅如此， 算法IGSP在整個(gè)挖掘過程中， 僅需要掃描數(shù)據(jù)庫(kù)一次， 后面統(tǒng)計(jì)計(jì)數(shù)只需統(tǒng)計(jì)過渡候選序列即可， 減少了掃描原始數(shù)據(jù)庫(kù)的次數(shù)， 降低了I/O開銷。
5 結(jié)論
本文針對(duì)物流信息管理系統(tǒng)中貨物流向分析這一需求， 提出了物流信息挖掘算法- IGSP算法。IGSP算法基于經(jīng)典算法GSP算法改進(jìn)而來， 首先根據(jù)頻繁k - 序列Lk更新數(shù)據(jù)庫(kù)， 刪除長(zhǎng)度小于k + 1的路徑序列， 然后生成過度候選序列C? k+ 1, 進(jìn)而通過aprior i性質(zhì)篩選產(chǎn)生候選序列Ck+ 1, 這樣能夠有針對(duì)性地產(chǎn)生候選序列， 大大減少了候選序列數(shù)目， 尤其是候選2- 序列。不僅如此， 算法IGSP還減少了掃描數(shù)據(jù)庫(kù)的次數(shù)， 有效地降低了I /O操作成本。雖然該算法在產(chǎn)生候選序列方面已大大壓縮， 但是當(dāng)數(shù)據(jù)庫(kù)中的路徑序列長(zhǎng)度變得很大時(shí)， 該算法仍將會(huì)產(chǎn)生很多候選碼， 效率就會(huì)相應(yīng)降低， 這也正是將本算法應(yīng)用在物流貨物流向分析而不是生物DNA分析方面的原因(路徑序列長(zhǎng)度不像DNA序列那樣長(zhǎng))。
為此以后工作中， 我們將提出最大頻繁序列模式這個(gè)概念， 最大頻繁項(xiàng)目集中已經(jīng)隱含了所有頻繁項(xiàng)目集， 所以可把發(fā)現(xiàn)頻繁項(xiàng)目集的問題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項(xiàng)目集的問題。另外， 某些數(shù)據(jù)挖掘應(yīng)用僅需發(fā)現(xiàn)最大頻繁項(xiàng)目集， 而不必發(fā)現(xiàn)所有的頻繁項(xiàng)目集， 因而發(fā)現(xiàn)最大頻繁項(xiàng)目集對(duì)數(shù)據(jù)挖掘具有重大意義。
參考文獻(xiàn)：
[ 1] HAN J, KAMBER M. Data m ining C oncep ts and T echniques S econd Edition [M] . 北京： 北京機(jī)械工業(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] . 計(jì)算機(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]陸介平， 楊明， 孫志揮等。 快速挖掘全局最大頻繁項(xiàng)目集[ J] . 軟件學(xué)報(bào)， 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]張長(zhǎng)海， 胡孔法， 陳崚。 序列模式挖掘算法綜述[ J].揚(yáng)州大學(xué)學(xué)報(bào)， 2007, 10( 1) : 41~ 46
【小議序列模式挖掘在物流中的應(yīng)用】相關(guān)文章：
淺談JIT模式在電網(wǎng)公司物流中的應(yīng)用10-26
網(wǎng)絡(luò)營(yíng)銷中數(shù)據(jù)挖掘技術(shù)的應(yīng)用10-07
旅游管理中的情景模式應(yīng)用論文10-08
數(shù)據(jù)挖掘在電子商務(wù)管理中的應(yīng)用論文10-09
計(jì)算機(jī)應(yīng)用基礎(chǔ)教學(xué)在合作學(xué)習(xí)模式在中的應(yīng)用10-07
合作學(xué)習(xí)模式在初中數(shù)學(xué)中的應(yīng)用論文10-11