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