基于空间聚类的台风轨迹提取(编辑修改稿)

基于空间聚类的台风轨迹提取(编辑修改稿)内容摘要：

8 图 3线段间距离函数的三部分 定义 1. iL 和 jL 之间的垂直距离定义如下 212 221),(  ll llLLd ji （ 1） 定义 2. iL 和 jL 之间的平行距离定义如下 ),(),( 2||1|||| llLLd ji   （ 2） 1||l 是 sp 到 is 和 ie 距离中较小值， 2||l 是 ep 到 is 和 ie 距离中较小值。 定义 3. iL 和 jL 之间的角度距离定义如下   00001 8 090| | ,|| 900),s i n (||||),(   ifL ifLLLd jjji （ 3） 另外， iiieiiis esuspesusp .,. 21  （ 4） 其中，||| | | |||.)c o s (,||||.,||||.2221 jjiijjiiiiiijiiiiiji eses eseses esesues esssu  （ 5） 定义两线段间距离如下： ),(.),(.),(.),( |||| jijijiji LLdwLLdwLLdwLLd i s t  ，其中权值 w 、 ||w 、 w 在本文中取 1。 台风轨迹分割 特征点提取 轨迹行为剧烈变化位置上的点就是特征点。 轨迹在每个特征点处分割，每个中南大学本科生毕业论文 第 3 章 轨迹聚类算法 9 分割由两相邻特征点间线段表示。 这样，轨迹就被分割为一系列线段，称线段为轨迹分割。 下图显示轨迹和它的轨迹分割。 图 33 轨迹及 其轨迹分割 理想的轨迹分割应包含两个可取的性质：准确性和简明性。 准确性指轨迹和它的轨迹分割集间的差别应尽可能的小。 简明性指轨迹分割的数目应尽可能的小。 这两个性质相互矛盾，因此需要在两者间找到一个理想平衡点。 可以采用广泛应用于信息理论的最小描述长度（ MDL）准则来发现准确性和简明性间的理想平衡点。 MDL 包含两部分： L(H)和 L(D|H)。 其中， H 指假设， D 指数据。 L(H)是假设的描述长度； L(D|H)是数据在假设的帮助下编码的描述长度。 对解释 D 的最佳假设 H 是使 L(H)和 L(D|H)之和最小时的值。 在轨迹 分割难题中，假设与特定轨迹分割集相对应。 想找到理想的轨迹分割，就是找最佳分割，也就是用 MDL 准则找最佳假设。 下图显示了 L(H)和 L(D|H)的构想。 图 34 L(H)和 L(D|H) 假定轨迹 le n iji pppppTR 321 和特征点集  c p a riccc pppp , 321 。 然后，用公式 6 规划 L(H)， )( 1cjcjpplen 表示线段 1cjcjpp 的长度。 所以， L(H)表示所有轨迹分割长度之和。   11 2 ))((log)( 1i jjp a rj cc ppl e nHL (6) 中南大学本科生毕业论文 第 3 章 轨迹聚类算法 10        11 1 12121 11 )),((l o g)),((l o g)|( i jjjjjjparjcck kkcckkcc ppppdppppdHDL  (7) 另一方面，用公式 7 规划 L(D|H)。 L(D|H)表示轨迹和它的轨迹 分割间差异之和。 对每个轨迹分割，将轨迹分割和属于分割的线段 )1( 11   jjkk ckcpp 间差异加起来。 用垂直距离和角度距离之和衡量差异。 可以不考虑平行距离，因为轨迹包围了它的轨迹分割。 长度和距离是真值。 在实践中，将真值 x 编码，假定精度为  ，使得编码数x 满足 |x x | 。 如果 x 很大，并且 xx ， 22 lo glo g)(  xxL。 这里，设  为1。 这样， )(xL 与 x2log 相等。 用线段的长度代替线段端点来定义 L(H)。 原因有二，首先，要通过他们的相互距离对线段聚类。 L(H)中的长度和距离函数，也就是线段间的垂直、平行、角度距离，在衡量相互距离上比线段端点更好。 即新定义更适合子轨迹聚类工作。 其次，不用端点的一个很重要原因是使聚类结果不受线段坐标影响。 这样，一束线段可以由低坐标位置转换到高坐标位置； 然而，距离函数应该还能正确度量相互距离。 如果用两端点的坐标值规划 L(H)，聚类结果可以被这样的转换更改。 注意， L(H)度量简明度， L(D|H)度量准确度。 因为三角不相等， L(H)会随着轨迹分割数目的增加而增加。 同时， L(D|H)显然会随着轨迹分割集偏离轨迹而增加。 前面提到，需要找到一使 L(H)+L(D|H)最小的理想分割。 解决方案的关键想法是将局部理想看做全局理想。 让 ),( jipar ppMDL 表示 ip和 jp 间轨迹的 MDL 花费，假定 ip 和 jp 是仅有的特征点。 让 ),( jinopar ppMD L 表示 ip 和 jp 间没有特征点时轨迹的 MDL 花费，即保持原有轨迹时。 ),( jinopar ppMD L 中的 L(D|H)是 0。 然后局部理想是对每个使 jki  的 k 满足),( jipar ppMDL  ),( jinopar ppMD L 的最长轨迹分割 jipp。 如果前者小于后者，选择 kp 作为特征点使得 MDL 花费更小。 而且因为简明性的缘故增大轨迹分割长度。 中南大学本科生毕业论文 第 3 章 轨迹聚类算法 11 下图五显示了近似轨迹分割算法。 对轨迹上的每个点计算 ),( jinopar ppMD L 和),( jipar ppMDL （ 5~6 行）。 如果 ),( jipar ppMDL 大于 ),( jinopar ppMD L ，将紧邻的前一个点插入到特征点集 iCP中（ 8 行）。 然后从那一点重复相同过程（ 9 行）。 否则增加后备轨迹分割的长度（ 11 行）。 算法 2：近似轨迹分割算法 近似轨迹分割算法 输入：轨迹 le n iji pppppTR 321 输出：特征点集 iCP 算法： p1 添加到 iCP； 1，长度为 1； （开始索引 +长度  leni）时 04. 当前索引 =开始索引 +长度； 05. 计算 ),( jipar ppMDL ； 06. 计算 ),( jinopar ppMD L ； 07. 如果 ),( jipar ppMDL ),( jinopar ppMD L ； 08. 将前一点添加到特征点集； 09. 开始索引 =当前索引 1，长度 =1； 10. 否则 11. 长度 =长度 +1 12. 将结束点添加到特征点集 近似算法的时间复杂度为 )(nO ， n 为轨迹长度。 中南大学本科生毕业论文 第 3 章 轨迹聚类算法 12 构造特征线段 经过上一步骤的操作，每个轨迹对应一个特征点集。 特征点集中从始 点到终点，每两个相邻特征点可以构成一小线段，即特征线段。 有时候特征点的提取也会不理想，如下图举例。 假设使 MDL 花费最小的理想分割是  51,pp。 该算法不能发现准确方案，因为他在 p4 处停止扫描，在此),( jipar ppMDL 大于 ),( jinopar ppMD L。 当然，该算法的精确性已经很高了。 图 35 特征点提取 特征线段聚类 基于密度的特征线段空间聚类 距离函数概述 距离函数是三种距离的加权和。 首先，垂直距离主要衡量从不同轨迹提取的线段间的位置差异。 其次，平行距离主要衡量从相同轨迹提取的线段间的位置差异，一个轨迹中两临近线段间的平行距离总是 0。 最后，角度距离衡量线段间方向差异。 距离函数的对称性对于避免聚类结果的模棱两可很重要。 如果距离函数是不对称的，不同聚类结果可以通过过程顺序获得。 基于密度聚类的概念 以下定义是基于密度聚类所需的 概念。 D 表示所有线段集。 改变本来为 DBSCAN算法提出的点的定义为线段的。 定义 4. 属于 D 的线段 iL 的  邻域定义为    ),(|)( jiji LLd i s tDLLN。 中南大学本科生毕业论文 第 3 章 轨迹聚类算法 13 定义 5. 如果 M inLnsLN i )( ，那么属于 D 的线段 iL 称为核心线段。 定义 6. 如果 )( ji LNL  并且 M inL nsLN j )( ，从线段 DLj 到线段 DLi 是直接密度可达的。 定义 7. 如果有一属于 D 的线段链 iijj LLLL , 11   使得 kL 从 1kL 是直接密度可达的，那么从线段 DLj 到线段 DLi 是密度可达的。 定义 8. 如果有一线段 DLk 使得线段 DLi 和线段 DLj 对 kL 是密度可达的，那么 iL 对 jL 是密度 连接的。 定义 9. 非空子集 Dc 是密度连接集，如果 c满足以下两个条件： （ 1） 对于任意属于 c的 iL 、 jL ， iL 对 jL 是 密度连接的； （ 2） 对于任意属于 D的 iL 、 jL ，如果 iL 属于 c， jL 对 iL 是密度可达的，那么 jL属于 c。 在下图描绘这些定义。 密度可达性是直接密度可达性的转化终止，其关系是不对称的。 只有核心线段是互相密度可达的。 然而，密度连接性却是对称关系。 让。