- 相关推荐
小议序列模式挖掘在物流中的应用
摘 要： 当前第三方物流管理系统中以物流活动为对象的数据库庞大， 难以发现有价值数据。为此， 本文提出一种针对物流数据分析的经典方法： 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 案例分析
数据挖掘中关联规则技术就是发现事物之间有意义的联系和规则， 能够从事物数据库、关系数据库和其它数据存储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联和相关性。因此， 利用关联规则技术可以对物流中的路径数据进行分析、挖掘， 找出频繁出现的路径信息， 以发现物流市场上的货物流向及未来可能出现的变动。