无线射频识别(RFID)系统的频繁路径挖掘研究.doc

1 无线射频识别 RFID 系统的频繁路径挖掘研究 摘要 在现代物流系统中 由 RFID 技术产生的大量物品的路径信息占用了过多的存储空间 难以有效检索 使用路径编 码 pid 的方法来记录路径信息 减少存储空间 并方便地检索路径信息 在路径编码的基础上 通过挖掘频繁路径编码来 挖掘频繁路径 可以有效降低存储空间大小 提高挖掘算法的速度 能够有效地挖掘记录移动物品的数据立方体中的频繁 路径信息 关键字 无线射频识别 RFID 路径编码 数据压缩 频繁路径挖掘 Research on Mining Frequency Path in Radio Frequent Identification RFID System Abstract The volume of path data of moving objects collected by RFID is massive and hard to be searched in the modern logistic management system Using path code denote as pid in this paper to replace the path data can not only compress the volume of data but also decrease the storage space greatly and make the path searching more easily Base on pid using mining frequency pid to mining frequency path can also decrease the storage space and increase the speed of mining algorithm This method can be used in mining frequency path in the cube which used in moving objects applications Keywords Radio Frequent Identification path coding data compress mining frequency path 0引言引言 无线射频识别技术 1 Radio Frequent Identification 简称 RFID 引入到物流与供应链管理中 带来了 管理效率的极大提高 但在现代物流中 存在有大量的移动物品 RFID 技术可以自动记录这些物品的移 动痕迹 产生海量的路径信息 通过对路径信息的处理 用户可以全程监控物品的流动情况 提高库存 的流动速度 减少管理人员 降低成本 基于以上因素 近年来国家加大了 RFID 的投入 以提高我国物 流管理的效能 并且建立了国家 RFID 技术标准 2 在货物上所附贴的 RFID 标签中电子产品编码 3 Electronic Product Code 简称 EPC 具有全球唯一性 能够通过部署在物流各个环节的 RFID 阅读器读 取货物的电子产品编码 对这些信息进行清理 可以得到货物从生产到运输到销售各环节的移动情况 从而产生路径信息 通过对这些路径信息进行有效地分析与挖掘 RFID 系统可以对供应链中货物实现有 效地跟踪和监控 掌握实时的物流信息 提高管理效率 降低人力 物力成本 RFID 技术在物流及供应链领域应用方面 文献 4 初步讨论了如何建立海量的 RFID 数据集的数据仓 库以及在数据仓库中进行简单的数据分析工作 同时分析了物品在供应链中的移动特点 在移动的初期 物品是以包的形式一起移动 提出了 RFID 数据记录的是物品移动的原始信息 而分析人员常常使用的是 高度抽象后的路径信息 根据以上的特点 作者给出了 RFID 数据仓库的体系结构 RFID 数据压缩的关 键思想等 文献 5 中 作者给出了一种为商品流建立数据仓库的方法 FlowCube 不同于普通的数据立方 体的概念 FlowCube 将物品的属性分成了非路径维 2 和路径信息两个部分 使用路径信息作为度量 可以用来处理移动物品 为 RFID 数据的 OLAP 提供了一 个有用的工具 FlowCube 中的路径信息没有压缩 所以信息量过大 同时在进行数据分析时要同时考虑路径信息的 多个参数 难以建立高效算法 本文在路径编码 6 的基础之上加以改进 通过直接挖掘频繁路径编码来有 效地挖掘频繁路径 可以降低算法的复杂度 提高算法的效率 1 相关概念 定义 1 路径段 stage 是 location duration 形式的元组 其中 location 表示 RFID 阅读器的位 置 duration 表示物品在阅读器作用范围内的停留时间 路径 path 由若干有序的路径段元组组成 具 有 l1 d1 l2 d2 ln dn 的形式 第 i 个路径段 i stage 表示路径中的第 i 个 location duration 元 组 路径长度 length 表示路径中的 location duration 元组个数 j 长度路径前缀 j prefix 表示路径的前 j 个 location duration 元组 例 1 假设路径 p l1 d1 l2 d2 l3 d3 l4 d4 路径长度 length p 4 3 stage p l3 d3 3 prefix p l1 d1 l2 d2 l3 d3 定义 2 假设 P 是所有路径的集合 其中最长的路径长度为 maxlength 现将所有路径的第 i 段取出 i 1 2 maxlength 根据得到的 location 和 duration 取值进行分类 给予每个类一个整数编码 称为第 i 段路径段编码 记为 idi 表示第 i 段段编码的任意整数编码 将某条路径所有的路径段的段编码合并 得到该路径的路径编码 记为 pid id1 id2 idn n 为该条路径长度 定理 1 路径编码与路径一一对应 证明 由定义 1 可知 假设路径 P l1 d1 l2 d2 ln dn 其中 li di 由定义 2 所定义的路径 段编码 可以得到 idi 将这些路径段编码合并 就得到了 P 的路径编码 反之 对于一个路径编码 pid id1 id2 idn 由定义 2 可知 每个 idi都能够得到一个相应的 li di 将这些路径段合并 可得到路径 不同的路径肯定至少有一个路径段不同 那么它们的路径编码至少有一个段编码不同 反之亦然 定理 得证 定义 3 路径编码长度指路径编码中的段编码整数取值或者 表示路径到此结束 的段编码的 个数 其它的段编码取值用 表示 如路径编码 2 表示路径长度为 4 第 2 段路径段编码为 2 的路 径编码 路经编码长度为 1 表示路径长度为 2 路径编码长度为 1 定义 4 Info 表的记录具有如下的形式 EPC list d1 dm m1 mi 其中 EPC list 指 那些在 d1 dm维上具有相同属性值的物品的 EPC 集合 m1 mi是这些物品的度量值 Info 表其实就是 普通数据立方体所使用的数据表 3 定义 5 EPC pid 表的记录具有如下形式 EPC length pid 其中 EPC 表示电子产品编码 length 表示 EPC 所标识的物品的路径长度 pid 表示路径编码 定义 6 Stage 表 Stage 表具有 maxlength 个子表 每个子表 i Stage 的记录具有如下形式 idi location duration count 其中 idi表示第 i 段编码 location 表示阅读器位置 duration 表示物品在阅读器 作用范围内的停留时间 count 表示第 i 段路径段编码为 idi的物品的个数 例 2 设有 3 种物品 它们的 EPC 分别为 epc1 epc2和 epc3 移动路径分别为 p1 l1 1 l2 1 l3 2 p2 l1 1 l2 2 p3 l1 2 l2 1 l3 1 这 3 个物品的 Stage 表和 EPC pid 表如表 1 和表 2 所示 表 1 Stage 表 1 Stage2 Stage3 Stage id1locationdurationcountid2locationdurationcountid3locationdurationcount 0l1120l2120l321 1l1211l2211l311 表 2 EPC pid 表 EPClengthpid epc130 0 0 epc220 1 epc331 0 1 例 2 表示了路径转化为路径编码的情况 由例 2 可以看出 路径编码和路径是一一对应的 并且路 径编码可以通过 Stage 表和 EPC pid 表还原出路径 路径也可以通过这两张表得到相应的路径编码 2段编码概率表 Stage probability 为了提高频繁路径编码的挖掘速度 本文提出了段编码概率表 Stage probability 的概念 本节将 说明 Stage probabilty 表的结构 构造算法和在频繁路径编码挖掘中的作用 2 1 Stage probability 表的结构表的结构 类似于 Stage 表 Stage probability 表也包含 maxlength 个子表 对于第 i 个子表 具有两部分 1 权值 2 段编码概率 1 Stage probability 表的权值 W1取值为 1 00 设 i Stage probability 表的权值为 Wi 那么 i 1 Stage probability 表的权值 Wi 1的计算如式 1 所示 式 1 1 1 i ii i count id WW count id 即 i 1 Stage probability 表的权值表示路径长度大于或等于 i 1 的物品的数目与路径长度大于或等 于 i 的物品的数目的比值 设第 i 段路径编码有 这 k 个不同的整数编码 使用 id probability 1 i id 2 i id k i id j i id j 1 2 k 表示第 i 段段编码的概率 id probability 计算如式 2 所示 j i id 4 id probability 式 2 j i id 1 j i k l i l count id count id 即 第 段的某个段编码概率 id probability 为段编码为的物品的数量比上第 段的 j i id j i id j i id 段编码不是 的所有物品的数量 2 2 段编码概率表的构造段编码概率表的构造 段编码概率表的构造分为两步 1 由 Info 表的非路径维属性和用户输入的条件得到 EPC 的集合 2 由 EPC 集合和 EPC pid 表得到段编码概率表 段编码概率表如算法 1 所示 算法 1 Construct Stage probability 输入 Info 表 I 物品选择条件 L EPC pid 表 Ep 输出 段编码概率表 SP 步骤 1 根据输入的表 I 和选择条件 L 得到 EPC 集合 S 步骤 2 建立 SP 1 逐一读取 S 中的 EPC 根据 Ep 表中的 EPC 与 pid 的对应信息 count pid 最终得到 聚集后的路径编码数据库 Ec 2 for i 1 to maxlength do call Construct i Stage probability 3 return SP Construct i Stage probability 1 计数 Ec 中所有的 1 2 j i idjk 2 icount id 1 k l i l count id 3 根据公式 1 和 Wi 1 求出 Wi W1 1 00 1 icount id 4 根据公式 2 求出 id probability j i id1 2 jk 5 return i Stage probability 分析 分析 根据 Info 表和选择条件 L 得到 EPC 集合 已有多种方法解决 7 13 本文的研究重点在于如何 根据聚集后的路径编码的计数得到段编码转移概率表 由本节讨论的算法 1 可知 能够求得所有的 i Stage probability 子表 例 3 假设有由 EPC pid 表得到的聚集后的路径编码数据库如表 3 所示 表 3 聚集后的路径编码数据库 5 pidcountpidcountpidcount 07002 121602 1 1 06 17002 221602 1 2 048 224002 1 0182 1 0 136 0 02402 1 1182 1 1 136 1 02402 1 21442 1 2 1144 2 08002 1 0 062 1 2 2144 1 建立 1 Stage probability count 0 700 240 940 count 1 700 240 940 count 2 2400 800 2160 2160 18 18 144 6 6 48 36 36 144 144 8120 count id1 940 940 8120 10000 W1 1 00 id probability 0 0 940 0 094 0 1 2 10000 count countcountcount 同理 id probability 1 0 094 id probability 2 0 812 得到的 1 Stage probability 表如表 4 所示 表 4 1 Stage probability 1 Stage probability W1 id probability 012 1 00 0 0940 0940 812 2 同理 计算 2 Stage probability 3 Stage probability 4 Stage probability 如表 5 所示 表 5 Stage probability 的后 3 个子表 2 Stage probability3 Stage probability4 Stage probability W2id probabilityW3id probabilityW4id probability 0120120120 62 0 210 450 35 0 10 0 100 100 80 0 70 0 140 540 34 6 2 3 Stage probability 表的作用表的作用 Stage probability 表在挖掘频繁路径编码的时候可以用来判断路径编码是否频繁 减少搜索空间加快 搜索速度 不妨设有路径编码 pid pid 的最后一个非 的段编码为 那么该路径编码的最大可能支 k n id 持度 max supp 由式 3 计算得出 max supp pid id probability 式 3 k n id 1 n i i W 如例 3 中的路径编码数据库 求 pid 2 的最大可能支持度 得到 max supp pid 0 80 1 00 0 62 0 10 0 0496 可以在得到频繁路径编码前检查路径编码支 持度时不用遍历数据库 直接算出最大可能支持度 若最大可能支持度小于最小支持度阈值 就可以直 接得到该路径编码不频繁的结论 减少搜索数据库的次数 3频繁路径挖掘算法频繁路径挖掘算法 路径编码中的段编码具有顺序性 可以看成是一种特殊的序列 挖掘频繁路径的算法可以借鉴挖掘 频繁序列的算法 本文在 GSP 算法 14 和 PrefixSpan 算法 15 基础上 结合路径编码的特点 提出 pid GSP 和 pid PrefixSpan 两种改进的频繁路径编码挖掘算法 3 1 pid GSP 算法算法 pid GSP 算法是基于 GSP 算法的频繁路径编码挖掘算法 利用候选集得到所有的频繁路径编码 pid GSP 算法形式描述如算法 2 所示 算法 2 pid GSP 算法 输入 路径编码数据库 Ec Stage probability 表 SP 最小支持度阈值 min sup 输出 频繁路径编码集 FP step1 找出编码长度为 1 的频繁路径编码 存入集合 L1 step2 令 i 1 step3 从 Li中选择两个编码长度为 i 的频繁路径编码 合并成长度为 i 1 的路径编码 检查是否频繁 若频繁存入集合 Li 1 如此直到找到所有的编码长度为 i 1 的频繁路径编码 step4 若 Li 1非空 i 转 step3 否则 转 step5 step5 FP L1 L2 Li return FP 下面用例 3 中的路径编码数据库来说明算法 2 如何挖掘频繁路径编码的 找寻编码长度为 1 的频繁 路径编码过程如表 6 所示 括号外实数表示最大可能支持度 括号内实数表示实际支持度 若最大可能 支持度小于最小支持度阈值 就说明该路径编码不频繁 就不用再通过遍历数据库去求实际支持度了 这里假设最小支持度阈值取 0 10 7 表 6 求编码长度为 1 的频繁路径编码的过程 0 0 094 0 0 1302 0 128 0 0 0062 0 0 006 1 0 094 1 0 279 0 276 1 0 0062 1 0 023 2 0 812 0 812 2 0 217 0 216 2 0 0496 2 0 015 得到集合 L1 2 0 812 0 0 128 1 0 276 2 0 216 再由集合 L1求出集合 L2 L2 2 1 0 276 2 2 0 216 合并 L1 L2 得到 FP 2 0 812 0 0 128 1 0 276 2 0 216 2 1 0 276 2 2 0 216 3 2 pid PrefixSpan 算法算法 定义 7 设路径编码为 pid id1 id2 idn 取 i n i 长度路径编码前缀记为 i prefix pid id1 id2 idi 该路径编码前缀的路径编码后缀为 suffix i prefix pid idi 1 idi 2 idn 例 4 设 pid 0 1 0 2 0 1 3 prefix pid 0 1 0 suffix 3 prefix pid 2 0 1 pid PrefixSpan 算法基于 PrefixSpan 算法 利用模式增长的方式最终得到所有的频繁路径编码 pid PrefixSpan 算法形式描述如算法 3 所示 算法 3 pid PrefixSpan 算法 输入 路径编码数据库 Ec Stage probability 表 SP 最小支持度阈值 min sup 输出 频繁路径编码集 FP step1 找出编码长度为 1 的频繁路径编码作为频繁路径编码前缀 找出这些频繁路径编码前缀的频繁 路径编码后缀数据库 i 1 频繁路径编码前缀存入集合 FP step2 从后缀数据库中找出编码长度为 1 的频繁路径编码 与相应的路径编码前缀合并 产生新的编 码长度为 i 1 频繁路径编码前缀并存入集合 FP step3 再由 step2 中的频繁路径编码前缀得到频繁路径编码后缀数据库 若后缀数据库为空 转 step4 否则 i 转 step2 step4 return FP 以例 3 中的路径编码数据库为例 说明算法 34 的过程 取最小支持度阈值为 0 10 表 7 表示了编码 长度为 1 的频繁路径编码前缀及其频繁路径编码后缀数据库 表 7 编码长度为 1 的频繁路径编码前缀及其频繁路径编码后缀数据库 frequent prefixfrequent suffix 2 0 812 0 0 128 1 0 276 2 0 216 0 0 128 1 0 276 2 0 216 此时 FP 2 0 812 0 0 128 1 0 276 2 0 216 合并表 7 中可以合并的前缀与后缀 得 到编码长度为 2 的频繁路径编码前缀及其频繁路径编码后缀数据库 如表 8 所示 8 表 8 编码长度为 2 的频繁路径编码前缀及其频繁路径编码后缀数据库 frequent prefixfrequent suffix 2 1 0 276 2 2 0 216 FP 2 0 812 0 0 128 1 0 276 2 0 216 2 1 0 276 2 2 0 216 后缀数据库为空 算法 结束 4实验结果分析实验结果分析 为了进一步验证基于路径编码和聚集后的路径编码数据库的路径信息压缩性以及频繁路径编码挖掘 算法的准确性等 实验环境是基于 Windows XP SP2 内存为 512M CPU 为 PIV 2 8 GHz 实验环节使用 Visual C 6 0 编写 所采用的实验数据为基于某 RFID 物流管理系统中的数据 实验 1 是关于路径编码和聚集后的路径编码数据库的存储空间大小与原始数据库的存储空间大小的 比较 实验结果如图 1 所示 可见路径编码能够有效压缩路径信息的存储空间大小 聚集后的路径编码 数据库存储空间大小与原始路径信息和路径编码的存储空间相比是极小的 0 500 1000 1500 2000 2500 3000 3500 100050001000050000 物品数量 单位 千 存储大小 单位 兆字节 原始的路径信息使用路径编码聚集后的路径编码数据库 图 1 存储空间比较 实验 2 是关于 pid GSP 算法 pid PrefixSpan 算法与直接对原始路径信息进行挖掘的程序运行时间的 比较 实验结果如图 2 所示 通过实验发现 pid GSP 算法和 pid PrefixSpan 算法运行时间相差极小 而 直接挖掘原始路径信息运行时间与这两个算法差别较大 主要是因为由 EPC pid 表得到聚集后的路径编 码数据库用时大大低于由原始路径信息求得聚集后的路径数据库所消耗的时间 又由参考文献 6 中的构 造路径编码的算法可知 路径编码可以在物流网络中物品移动的同时得到 物品离开物流网络时 基本 9 已经得到了该物品的路径编码 挖掘频繁路径编码的工作几乎不会由于生成路径编码而被延误 所以 可以通过在路径编码数据库的基础上挖掘频繁路径编码 来代替直接在原始路径信息的基础上挖掘频繁 路径 0 500 1000 1500 2000 2500 3000 100050001000050000 物品数量 单位 千 运行时间 单位 秒 pid GSP算法pid PrefixSpan算法直接挖掘路径信息 图 2 运行时间比较 5结束语结束语 随着 RFID 在现代物流管理中的广泛应用 将产生大量物品的路径信息 如何对这些海量的路径信息 进行有效的分析与挖掘 来全程监控物品的流动情况 提高效率 本文提出利用路径编码 pid 的方法来记 录路径信息 减少存储空间 并方便地检索路径信息 在路径编码的基础上 提出了 pid GSP 算法和 pid PrefixSpan 算法 2 种基于频繁路径编码的频繁路径挖掘算法 通过挖掘频繁路径编码来挖掘频繁路径 有 效地降低了存储空间大小 提高了挖掘算法的速度 能够有效地挖掘记录移动物品的数据立方体 如 FlowCube 中的频繁路径信息 算法分析与实验结果表明 本文提出基于繁路径编码的频繁路径挖掘算 法效率较高 有效地减少了存储空间大小 提高了挖掘速度 下一步工作是建立一种可以快速响应路径 与路径编码相互转化工作的算法 来提高本文所提出的方法的实用性 参考文献 1 CHAWATHE S S KRISHNAMURTHY V RAMACHANDTAN S SMRMA S Managing RFID data C Proceedings of the 30th Int Conf on Very Large Data Bases San Fransisco Morgan Kaufmann 2004 1189 1195 2 科技部 信息产业部等十五个部委 中国射频识别 RFID 技术政策白皮书 2006 3 http www epcglobalinc org 4 GONZALEZ H HAN J LI X KLABJAN D Warehousing and analyzing massive RFID data sets C Proceedings of International Conference on Data Engineering ICDE 06 Heidelberg Germany Springer 2006 83 5 GONZALEZ H HAN J LI X FlowCube Constructing RFID flowcubes for multi dimensional analysis of commodity flows C Proceedings 2006 Int Conf Very Large Data Bases VLDB 06 San Fransisco Morgan Kaufmann 2006 834 845 6 陈竹西 胡孔法 陈崚 基于路径编码方法的 RFID 数据压缩存储技术研究 扬州大学学报 自然科学版 7 STOCKINGER K Bitmap indices for speeding up high dimensional data analysis C Proceedings of the 13th Int l Conf on 10 DEXA Heidelberg Germany Springer 2002 881 890 8 WU K KOEGLER W CHEN J SHOSHANI A Using bitmap index for interactive exploration of large datasets C Proceedings of the 15th International Conference on Scientific aStatistical Database Management SSDBM Los Alamitos IEEE Computer Society Press 2003