专利名称：基于线路聚类的gps数据压缩存储方法
技术领域：
本发明涉及一种基于线路聚类的GPS数据压缩存储方法，用于交通运输业运输线 路GPS数据的压缩存储，属于数据库技术领域。
背景技术：
数据压缩分为有损压缩和无损压缩两种，有损压缩可以损失一部分原始数据的信 息；无损压缩则要求原始数据的信息一点都不能损失，压缩数据能够完整地还原为原始数 据。本发明基于线路聚类的GPS数据压缩存储方法属于无损压缩方法。目前一般的无损压缩方法都是把原始数据文件看作一个字节流，通过重新编码或 者寻找重复出现的串来进行压缩，例如rar。这种方法有两个缺点，一是对于特定类型的数 据，无法利用到其独有的某些性质来为压缩服务；二是不支持实时的写入和读取。

发明内容
本发明旨在针对交通运输线路的GPS数据具有大量重复的特点，提出基于线路聚 类的GPS数据压缩存储方法，可以随时压缩新数据，同时支持数据的实时写入和读取。本发明的技术方案是基于线路聚类的GPS数据压缩存储方法，用于交通运输线 路数据处理，其程序是步骤1 读取一条新的GPS数据X ；步骤2 如果X与聚类数据CF中某个聚类线段L的距离足够接近，转到步骤8 ；否 则进入下一步骤；步骤3 将X以原始的未压缩的数据格式写入未压缩的数据UD ；步骤4 如果未压缩的数据UD的大小超过了某个预定义的数值，进入下一步骤；否 则转到步骤9，程序结束；步骤5 对数据UD进行聚类分析，寻找新的近似拟合线段；步骤6 如果找到新的线段方程，将其以聚类信息文件格式写入聚类数据CF，进入 下一步骤；否则转到步骤9，程序结束。步骤7 把UD中的每一条数据作为新的输入数据X，并把UD清空，返回步骤1 ；步骤8 计算数据X的压缩格式，并将其以压缩数据文件格式写入压缩数据CD ；步骤9:结束。所述聚类线段由聚类分析算法获得，所述聚类分析算法如下步骤21 用基于密度的聚类方法，去除异常点；步骤22 利用向量夹角的方法，找出初始的r个分类好的点集；步骤23 对每个点集都进行m维线性拟合，得到r条线段；步骤24:对除了异常点的每个数据点，根据它到r条线段的距离进行重新归类，得 到r个新的点集；步骤25 利用类似k-means的思路，检查每个非异常点的归类是否改变，如果改变，转到步骤23 ；如果不改变，则进入下一步骤；步骤26 将得到的r条线段以聚类信息文件格式写入聚类数据CF。3.如权利要求1所述的GPS数据压缩存储方法，其特征在于所述GPS数据的存 储格式分为聚类信息文件、压缩数据文件和未压缩的数据三种；所述聚类信息文件存储在文件“终端号.line”里，该文件分为两个部分第一部 分是概要信息，共8个字节，前4个字节表明这个聚类文件共计有多少个线段r，后4个字节 表明每个线段的维数m;第二部分是r个m维线段，每个线段用16(m+l)个字节来表示，前 16m字节，分别表示m个维度上的直线斜率和截距，最后的16个字节，是前m个斜率和截距 值的累加；所述压缩数据文件存储在文件“终端号.cpr”里，该文件分为索引区和存储区，所 述索引区分为三个部分前4个字节表明日期索引的项数h ；后面是h个索引项数据，每个 索引项数据最前面4个字节表示日期，中间8个字节长整型数表示该索引项所代表一天的 数据在文件中的起始位置，后4个字节整数表明这个日期对应的数据的大小；所述存储区 对应于索引项按天存储压缩的GPS数据；所述未压缩的数据存储在文件“终端号.pos”里，该文件是按时间顺序简单存储的 原始数据。本发明基于线路聚类的GPS数据压缩存储方法具有以下优点1、节约了数据的存储空间。由于压缩以后的数据存储的主要是与特定模式的差 值，而不是完整的原始数据，所以存储空间大大减小，只有原来的50%不到。2、本存储方法支持数据的实时读取和存储。对于新产生的数据，这个算法可以根 据已有的一些聚类信息，直接把新数据变为压缩格式写入压缩文件；而若想访问某些数据， 也可以根据数据文件中的索引结构读取对应的压缩数据，并还原为原始的数据格式。这一 点是相比于rar等针对数据文件的压缩算法的主要优点。3、为了压缩数据而从原始数据集中挖掘出来的数据模式，本身也可以作为某种 “概化”的数据，为高层的数据分析服务。比如，如果想分析一下某辆公交车的运行情况，那 么就不用再从原始数据重新分析了，这种模式已经在压缩阶段就被挖掘出来了。


图1是本发明压缩存储方法的程序图；图2a是本发明压缩存储方法的聚类信息文件存储格式图；图2b是图2a中线段i的详细存储格式图；图3a是本发明压缩存储方法的压缩数据文件存储格式图；图3b是图3a中每个存储区的压缩数据存储格式图。
具体实施例方式本发明基于线路聚类的GPS数据压缩存储方法(如图1所示)分为两部分程序，第 一部分为聚类分析程序，是对未分类数据进行聚类分析，以识别出部分交通运输线路。第二 部分为比较拟合程序，是对采集的新数据运用第一部分程序已获得的聚类结果进行分类， 如果能够被某一段线路较好地近似拟合，那么就以压缩格式存储；否则就暂时存储在未压缩的数据里，有待运用第一部分程序进行聚类分析。在最初任何线路都没被识别出来的时 候，所有新数据都是被存在未压缩部分的，直到未压缩数据的大小超过了一定限度，触发了 第一部分程序运行对其进行聚类分析，部分被聚类的数据就可以以压缩格式存储了。聚类分析程序的算法步骤如下l、m维线性拟合给出n 个 m 维向
我们可以用一组线性参数方程来拟合这组向量
假设... , Xn对应的参数值分别为、，t2，. . .，tn，我们需要确定一
组 使得目标函数
最小化。我们解方程组％ 祉可以求得名——乂 j=i , 2、m维点与m维线段的距离对于一条用参数表示的m维直线L = (kit+lv k2t+b2, ... , kmt+bm)，如果对t的取 值范围进行限定，令te [tfflin, t_]，那么就得到了一条m维空间中的线段。对于一个给定 的m维点X = (Xl，x2，...，xffl)，如果我们想用线段L上的某一个点对其进行近似，可以对目
标函数g⑴二t(V+、-x)2进行最小化。当不限制t的范围时，解一次方程—=0，可
以求得当
时，g(t)取得最小值g(t。pt)。如果t的范围受到了限制，
t e [tmin，tmax]，那么当 t。pt g [tmin，tmax]时，g(t)的最小值仍然是 g(t。pt)，如果 t。pt > tmax， 那么g(t)的最小值是g(t_)，如果t。pt<tmin，那么g(t)的最小值是g(tmin)。对于给定的 点X和线段L，我们记g(t)的最小值为d(X，L)，对应的t值为td。3、通过聚类分析找到公交线路的拟合线段寻找线路的拟合线段分为三步。 第一步用基于密度的聚类方法，去除异常点。任何两个点Xi = (xn, x12, ... , xlm)，X2 = (x21, x22, ... , x2m)，我们可以定义它们之
间的距离为街不，
，其中0 i为各个维的权重，引入它是为了使各个维的
差值分布范围基本一样，以免某些维因为取值范围较小而失去作用。在初始的时候，每个点 自己属于单独的一个类，如果某两个类之中有两个点的距离小于某个我们设定的阈值，那 么就把这两个类合并为一个类，不断进行这个过程，直到类的数目不再变化为止。最后检查 所有的类，如果有的类含有的点数量很少，那么我们就可以认为这个类里的点是异常点，予 以去除。
第二步找出初始的聚类中心。这里的关键问题是需要把位置点分为几个类，每个类内的点应该可以较好地用直 线段来拟合。我们的方法是这样的首先把位置点信息按照时间的先后排序，得到的点序列 为XpX,,... ,Xn;从Xi出发，向前走b个点，计算向量P = Xb-Xi，再向前走b个点，计算向量 P' =X2b_Xb，如果向量P和P'的夹角小于一定的阈值，那么我们就认为X2，...，&是 近似分布在一条直线上的，然后令P = Xm-Xi，继续以b个点为单位向前探索，直到发现某个 P' = Xib-X(i_1)b与P的夹角大于设定的阈值，那么肯定从X(i_1)b，. . . ,XiW之中某个点开始， 线路走向发生了转折我们对其中的每个点X做检测，计算向量xib-x与X-Xi的夹角，使得夹 角最大化的那个点X就是转折点。这样就识别出了可以拟合一条线段的点，X” X2，. . .，X。 从X的后一个点重新开始上述过程，最后就可以把所有的点都分到几条线段上。我们假设 上述过程可以把初始点集划分为r个集合，G” G2，. . .，4。我们对每个集合分别进行线性 拟合，就得到了 r条直线，我们把每条直线的t值设定为W，65535]，就得到了 r条线段L” L2，...，Lp这个可以作为初始的聚类中心。在对&进行线性拟合的过程中，还需要指定& 中每个点对应的t值。假设&中的点按时间顺序排列为XnX2，...，X。，那么&对应的、设
60000,. ^ 为2500 + 17Tr(广 1)。第三步，用类似k-means的方法对拟合线段进行修正。根据得到的L2，. . .，Lr,对每一个点X计算重新计算分类，把X加入到其距离最 近的那个线段所代表的类中去。再根据新的聚类结果，计算出新的‘ L2，. . .，Lp重复这 个过程，直到所有点的分类都不再改变为止。比较拟合程序的步骤如下1、对新数据的比较和存储对于一条新接收的位置数据X，我们查看所有已被发现的线段L，计算X与L的距 离，选择距离最小的那条线段。如果最小距离小于某个预定的值，那么我们就把它以“线段 编号+参数t+差值”的方式来存储；如果最小距离比预定的阈值大，那么我们认为它还不 是一个目前可以分类的点，暂时先以完整的格式存储在未压缩的数据中。对于以压缩格式存储的数据，它主要由三部分组成，线段编号1，参数t和差值。线 段编号是指预先通过聚类的方法找到的线段的编号，这个我们用一个字节来存，最多可以 表示256条不同的线段，这个是够用的，因为一个公交线路实际分的段数是要远远小于这 个数字的。参数t用两个字节来存储，表示0 65535。通过1和t可以确定一个点X的近 似值X’。在1和t之后，我们只记录X和X’的差值，因为一般来说X和X’已经很接近了， 所以它们的差值相对于原始数据来说，存储代价会小很多。而且由于有1和t，根据差值就 可以把原始数据无损地恢复回来。假设要存储的差值数据为DX = (dXl，dx2, . . . , dxffl)，这个差值我们用一个位流bs 来表示，dXl，dx2，. . .，dxm的值存在bs中，bs分为m个部分，每个部分前面4位表示这个差 值需要用多少位来表示，大小为0 15，根据前面4位的指示，我们读入后面的相应位数据， 这是用补码表示的整数，这样就取得了 dXi的值。每个差值位流bs占用整数个字节，比如 可能实际用到的位流只需要29位，那么也用完整的4个字节来存。这个是为了使压缩文件的结构严整，防止因一条记录发生错误而波及到后面的记录。2、数据的存储格式每个GPS终端的存储数据分为三部分，分别存在三个文件里。1)聚类信息文件，存储在文件“终端号.line”里。该文件分为两个部分第一部 分是概要信息，共8个字节，前4个字节表明这个聚类文件共计有多少个线段r，后4个字 节表明每个线段的维数m;第二部分是r个m维线段，每个线段用16(m+l)个字节来表示， 前16m字节，分别表示m个维度上的直线斜率和截距，最后的16个字节，是前m个斜率和截 距值的累加。聚类信息文件的结构可参见图2。图2a是完整的聚类信息文件结构图，图2b 是线段在文件中的详细格式，图2b中的每个存储单元都表示一个8字节双精度浮点数。2)压缩数据文件，存储在文件“终端号.cpr”里。该文件分为索引区和存储区，索 引区分为三个部分前4个字节表明日期索引的项数h ；后面紧跟了 h个索引项，每个索引 项索引某一天数据在文件中的位置，4个字节分别表示年、月、日、周，中间8个字节长整型 数表示该索引项所代表一天的数据在文件中的起始位置，是从文件头开始算起的字节数， 后4个字节整型数表明数据的大小，单位是记录数；存储区对应于索引项按天存储的压缩 格式GPS数据。压缩文件格式见图3。图3a是压缩文件的整体结构，图3b是一条压缩数据 记录的格式。每个数据存储区一般都存储了多条压缩格式的记录。3)暂时未压缩的数据，存储在文件“终端号.pos”里。是原始数据的按时间顺序 的简单存储。3、对压缩数据的访问 对于压缩的数据，可以根据给定的日期-时间间隔，进行部分访问。被压缩的数据 都是按照时间顺序进行存储的，而且在开头根据日期做了索引，根据给定的时间间隔，我们 可以根据日期索引把日期在时间间隔以内的数据块读出来，在去掉第一个块中处于起始时 间以前的数据和最后一个块中处于终止时间以后的数据，就得到了在指定时间范围内的数 据。
权利要求
基于线路聚类的GPS数据压缩存储方法，用于交通运输线路数据处理，其特征在于包括如下程序，步骤1读取一条新的GPS数据X；步骤2如果X与聚类数据CF中某个聚类线段L的距离足够接近，转到步骤8；否则进入下一步骤；步骤3将X以原始的未压缩的数据格式写入未压缩的数据UD；步骤4如果未压缩的数据UD的大小超过了某个预定义的数值，进入下一步骤；否则转到步骤9，程序结束；步骤5对数据UD进行聚类分析，寻找新的近似拟合线段；步骤6如果找到新的线段方程，将其以聚类信息文件格式写入聚类数据CF，进入下一步骤；否则转到步骤9，程序结束；步骤7把UD中的每一条数据作为新的输入数据X，并把UD清空，返回步骤1；步骤8计算数据X的压缩格式，并将其以压缩数据文件格式写入压缩数据CD；步骤9结束。
2.如权利要求1所述的GPS数据压缩存储方法，其特征在于所述聚类线段由聚类分 析算法获得，所述聚类分析算法如下步骤21 用基于密度的聚类方法，去除异常点；步骤22 利用向量夹角的方法，找出初始的r个分类好的点集；步骤23 对每个点集都进行m维线性拟合，得到r条线段；步骤24 对除了异常点的每个数据点，根据它到r条线段的距离进行重新归类，得到r 个新的点集；步骤25 利用类似k-means的思路，检查每个非异常点的归类是否改变，如果改变，转 到步骤23 ；如果不改变，则进入下一步骤；步骤26 将得到的r条线段以聚类信息文件格式写入聚类数据CF。
3.如权利要求1所述的GPS数据压缩存储方法，其特征在于所述GPS数据的存储格 式分为聚类信息文件、压缩数据文件和未压缩的数据三种；所述聚类信息文件存储在文件“终端号.line”里，该文件分为两个部分第一部分是 概要信息，共8个字节，前4个字节表明这个聚类文件共计有多少个线段r，后4个字节表 明每个线段的维数m;第二部分是r个m维线段，每个线段用16(m+l)个字节来表示，前16m 字节，分别表示m个维度上的直线斜率和截距，最后的16个字节，是前m个斜率和截距值的 累加；所述压缩数据文件存储在文件“终端号.cpr”里，该文件分为索引区和存储区，所述索 引区分为三个部分前4个字节表明日期索引的项数h ；后面是h个索引项数据，每个索引 项数据最前面4个字节表示日期，中间8个字节长整型数表示该索引项所代表一天的数据 在文件中的起始位置，后4个字节整数表明这个日期对应的数据的大小；所述存储区对应 于索引项按天存储压缩的GPS数据；所述未压缩的数据存储在文件“终端号.pos”里，该文件是按时间顺序简单存储的原始 数据。
全文摘要
本发明涉及一种基于线路聚类的GPS数据压缩存储方法，适用于交通运输业运输线路尤其是公交线路GPS数据的压缩存储，它由历史数据的线路聚类和新数据按聚类存储两个程序组成；通过对部分历史数据进行分析，对于某特定的车辆，找出其每天的行驶线路，用数条直线段(也就是折线)来拟合，然后转换历史数据和新数据的存储格式，将它们由完整的格式转化为“最接近的路线+与该路线的差值”来表示，从而达到压缩存储空间的目的。与传统的数据压缩软件相比，本发明具有节约数据存储空间，能支持压缩数据的实时写入与读取等优点。
文档编号G01S19/01GK101894135SQ201010205500
公开日2010年11月24日 申请日期2010年6月10日 优先权日2009年6月15日
发明者张 荣, 方标新, 汪卫, 解春欣 申请人:复旦大学;上海交通投资信息科技有限公司