- 相关推荐
小议序列模式挖掘在物流中的应用
摘 要： 当前第三方物流管理系统中以物流活动为对象的数据库庞大， 难以发现有价值数据。为此， 本文提出一种针对物流数据分析的经典方法： 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