在物流RFID数据库中挖掘时空模式

　　1　引言

　　物流RFID数据的采集与积累为期不长，如何对它们进行有效开发利用的研究还处于起步状态。虽然大家都认识到这项研究工作具有重大意义，但是目前还没有寻找到适用的方法和技术。物流货物的RFID数据与乘客利用公交IC卡刷卡乘车数据有相似之处，所以考察公交IC卡数据的研究工作有一定的借鉴作用。文献中有对公交IC数据仓库结构和数据挖掘系统框架进行探讨的，利用传统的统计方法，得到某些方面的汇总信息。但是文中没有提出有效的数据挖掘技术，所以没能获取深层次的决策支持信息。与乘客乘车一样，运载的货物也处于一个时空不断变化的动态过程中，要想得到货物在路网上的运动规律，必须采用新的方法和技术。时空数据挖掘的研究给解决此类问题提供了一种新的思路。

　　时空数据挖掘即“从时空数据库中发现知识”（Knowledge　Discovery　from　Spatio—Temporal　Data　bases），是指从时空数据库中提取用户感兴趣的时空模式与特征、时空与非时空数据的普遍关系及其它一些隐含在数据库中的普遍的数据特征，它是KDD技术在时空数据库应用的延伸，是数据挖掘近几年发展起来的一个新研究领域。针对由RFID设备获取物流信息的需求，选择时空数据挖掘中的时空关联规则的方法较为合适。文献中研究移动物体时空数据预处理技术，为时空关联规则数据统计提供基础；文献中对时空关联规则算法进行研究，得到了很多有趣的时空模式。上述算法适用于提取自由移动物体活动规律的情况。而在物流系统中，货物的运送受配送车辆和线路的影响，需要对以自由移动物体为研究对象的时空关联规则进行改进，以适用于具有路线约束的货物运送时空模式的挖掘。

　　本文利用时空频繁模式挖掘的基本思想，结合物流领域的专业知识，对物流货物运送时空规律进行提取，为物流公司线路优化提供详实科学的决策依据。借助于时空关联规则挖掘中的时空频繁模式来表示货物在配送过程中的规律，如货物于某时TIi从地点A装载上车，于另一时间TIj从地点B卸载下车，这就是一个配送模式；当货物件数大于规定的阈值时，这就是一个频繁的配送模式，反映了某一部分货物的群体时空配送规律。结合有效的剪枝策略，可以获取整个物流公货物主要的时空流动规律。这是对物流RFID数据进行时空模式挖掘的新探索，为获取货物主要的时空流动规律提供了新的方法与手段。

　　2　物流RFID数据库时空模式挖掘的概念与符号定义

　　本文研究的对象是物流公司通过RFID设备获取的货物时空数据库。从某一物流公司的货物配送数据库中，可得到表1的记录形式：

 　　从表1中可以看出，物流公司通过RFID技术详细记录了货物的动态信息，包括货物从接货到到达顾客手中所经历的地点与时间。有了这些信息，可以利用关联规则挖掘哪些地点对或地点链是频繁出现的，据此可以进行物流网优化调整。

　　一个物流线路网G由一组不同的货物配送线路Ii组成，且每条线路上分布有若干装卸货物的地点Sij。可以表示为：

　　式中，G一物流线路网；L一线路集合；Ii一第i条配送线路；S一装卸站点集合；Sij一第i条配送线路上的第i个装卸点。

　　每条配送线路都有一定的发送频率。线路上任何相邻两个地点之间的一段称为线段，不同的线路之间会有部分相交或不相交的线段。货物从某一起点可能需要一次或多次转运才到达收货人的手中，形成一条装卸点序列。当某序列只包含两个装卸点，即起点与终点，说明此次配送没有中途转运；当序列包含三个及以上装卸点，即除起点与终点外，还包含中间的一个或几个转运点，说明此次配送中途进行了转运。本文借助于时空关联规则挖掘中的时空模式来表示货物在配送网中的运送情况，结合物流领域的专业知识，定义配送线路模式这一术语来表示货物在配送网中的时空状态，见定义1。

　　定义1   时空配送线路模式：带时间属性的配送路线，是由带时间属性转运点所组成的序列，货物在每个转运点上都会停留一段时间，所以时间属性采用时间TI表示。如式（2）所示：

 　　式中，R一带时间属性的转运点集合和线路集合；
　　S一转运点集合；
　　Si一第i个转运站点；
　　T一所有转运点对应的时间集合；
　　ti一第i个转运点对应的时间；
　　L一转运点涉及的配送线路集合。

　　根据式（2）中的s={s1，s2…，Sy}所含转运点数量的不同，可分为直达的配送模式，即y=2，和转运的配送模式，即y>2。

　　为了便于利用数据挖掘技术，在此用时空关联规则对配送模式的表达方式进行转换。

　　定义2   直达路线的时空关联规则：用时空关联规则的表示方法描述的直达配送模式，即货物于某一时间ti从装载点si，装载上车q1，于另一时间tj从卸载点sj卸载下车q2，就成一条配送的时空关联规则ζi记为：

　　式中，ζi一带时间属性的直达路线的时空关联规则:
　　si、sj一第i，j个装卸点；
　　ti，tj一装卸点所需时间段集合；
　　q1一装载；
　　q2一卸载；
　　sup一支持数；
　　m一满足此条时空关联规则的货物件数。

{$page$}

　　定义3   转运路径的时空关联规则：具有转运关系的两个或两个以上的直达路径时空关联规则的组合。在时间ti从线路li的装卸点si装载的货物，于另一时间tj从装卸点sj卸载，又于时间tk在装卸点sj装上线路lj的车上，再于另一时间tg从sn卸下。可用式（4）表示:

 　　为了简化，用ζ*来表示转运路径关联规则，则有:

    把除装卸点si之外同一条线路l1上的其它所有装卸点称为sielse，那么可以单独地把某个装卸点的装卸载货物情况看成一个特殊的时空关联规则。

      定义4     装载点的时空关联规则：于某一时间ti从装卸点si装载的货物，将于其后时间tielse在同配送线路的其它sielse卸载，用关联规则形式表示：

      式中的0nζi表示装载点的时空关联规则。

　　定义5   卸载点的时空关联规则：货物于先于某一时间的时间从装卸点Si装载，于时间ti在装卸点sielse卸载，用关联规则的形式表示：

　　式（6）中的Offζi、表示卸载点的时空关联规则。

　　这样装卸点、装卸点对、装卸点链在时空关联规则上就有了统一的表述方式。

　　定义6  频繁模式：当某个关联规则的支持数大于一个设定的阈值时，这条关联规则就是有趣的，是一个频繁模式。这个设定的阈值称为最小支持数，用minsup表示。对应上述各种规则就有了各自的频繁模式。频繁直达路径的关联规则是指在路线l；上，于某一时间t从装卸点s装载的货物，将于某一时间tj从装卸点sj卸载，用F=（f，I，q.）（，，q）pup=≥minsup]表示，所有的F‘组成的集合用Fζi表示。同理可得频繁转运路径Fζ*，频繁的装载点F0nζ，频繁的卸载点Foffζ等概念。

　　3　物流 

　　RFID数据库时空模式挖掘的算法设计要想在上千万条记录中找出这些有趣的时空关联规则是一件相当不容易的事情，必须依靠有效的剪枝策略。根据物流专业领域的知识，可以得到以下的性质：

　　性质1：线路]i上频繁的直达路径必然频繁的装卸点集合中。可以直观地想象，没有很多货物发运的装载点，不可能成为频繁直达路径的前项；没有很多货物到达的卸载点，不可能成为频繁直达路径的后项。

     性质2：线路]i和]j；频繁转运路径必然发生在包含在具有转运可能性的装卸点的频繁直达路径的集合中。因为频繁转运路线时空关联规则是用两个或两个以上的直达路径时空关联规则的组合进行表示，所以频繁转运路径必定出现在频繁直达路径的集合中。

      利用这些定义和性质，就可以进行物流配送数据库时空频繁模式挖掘。

　　（1）数据准备。根据物流配送数据库中的数据，得到各线路各个时段的货物装卸点OD矩阵。

　　（2）设定minsup的值，寻找满足式（8）所列条件的频繁装载点集合FOnζ.和频繁卸载点集合FOffζ，如式（9），（10）所示。

　　（3）利用性质1来寻找频繁直达路径集合。由于一条路线上会有不同的车次，所以要用一个矩阵来表示各条路线不同车次的频繁直达路径，如（11）所示。

 　　式中Fζi表示线路li上的频繁直达路径集合，Fζij表示路线li上第j个车次频繁直达路径集合。

　　（4）获取频繁转运路径集合。在频繁直达路径集合式（11）中，针对具有转运可能的装卸点，根据货物号进行跟踪，利用性质2来寻找频繁转运路径集合，如（12）所示。

 　　式中Fζ表示线路l上的频繁转运路径集合，F‘表示路线l；上第j个频繁转运路径集合。

　　4  实验及其结果分析

　　为了能简单有效地说明上述算法，我们从物流配送线路网中截取两条具有代表性的单向线路l1和l2，它们有一个共同的装卸点C。如图1所示。

{$page$}

　　第一步根据货物配送数据，得到线路l和l各个装卸点装卸货物的件数，时间精度取到小时，见表2和表3。

 　　根据车辆的出行信息，可以得到线路l1和l2各装卸点的时间列表，见表4和表5。

　　第二步在各条路线每个车次装卸点OD中，获取大于最小支持数的各频繁装卸点。在本例中，设定minsup=10，则表2和表3中频繁的装卸有（AB）、（EFC），频繁的下客装卸点（BCD）、（CG）.如图2和图3所示：

　　根据性质1可以得到线路l1上频繁的直达路径有: 

　　简记为A==>C，如图4所示。

　　线路l2上频繁的直达路径有：

       简记为C==>G，如图5所示。

       第四步在具有转运可能的装卸点c，对货物进行跟踪，搜寻出这些货物中后来又上另一辆货车的货物件数超过设定转运支持数的装卸点，如图6所示。

　　通过上述的实验，验证本文提出的物流RFID数据库时李模式挖掘方法能快速获取频繁装卸点、频繁直达路径和频繁转运路径等。这些信息就可以为库存控制和线路优化提供决策依据。

　　5 结论及展望

　　随着各种检测设备与RFID技术的投入使用，物流公司的信息部门每天都可采集并存储大量货物运送方面的数据，但是这些积累的海量物流时空数据并未得到有效的组织和利用，很多潜在的物流运送线路规律并未发现，造成了数据资源的浪费。本文提出了利用数据挖掘技术来抽取这些隐含在数据中的潜在有用的规律。但是时空数据挖掘方法在很多方面都需要进一步完善才能应用到物流领域中，本文只是在这方面做了一些探索，需要进一步研究的内容还有很多，比如时空模式的可视化，挖掘算法的智能化，挖掘结果的后处理与利用问题等。