[SOLVED] 程序代写代做代考 基于编辑距离的关键点轨迹相似性计算

基于编辑距离的关键点轨迹相似性计算
1、 编辑距离简介
编辑距离又称Levenshtein距离，是指两个字符串S1和S2之间，由S1转成S2所需的最少编辑操作次数。在编辑距离方法中，比较的两字符串长度可以不一致，并且字符串中可以有多个空字符(即字符串具有稀疏的特性)。
编辑操作包括：插入、删除和替换三种操作。在基于编辑距离比较方法中，将对象轨迹视为字符串，两轨迹之间相似性就可以用编辑距离来度量。

2、 改进编辑距离算法–关键点
单纯的编辑距离直接运用到相似性分析中还有不足之处。ERP算法用真实值来度量距离，而不是将距离概化为0和1，所以该方法对噪声敏感。改进的ERP算法，采用编辑距离，定义了插入、删除和替换操作的代价函数，分析两条轨迹之间的相似性。
提出关键点的原因是ERP是以原始坐标数据计算的，每个轨迹点的坐标都作为一个元素来计算轨迹。噪声点的出现，会使得这些方法的准确率受到干扰。而采用寻找关键点方法，找出移动对象的轨迹中的关键点，然后对关键点轨迹进行轨迹挖掘和分析，提高了准确度。

3、 定义关键点轨迹
关键点的寻找应该遵循两个原则：精确度和简明性。精确度意味着原轨迹和它的关键点轨迹之间的差异应该越小越好，体现着原轨迹运动轨迹的风貌。简明性意味着关键点数量应该越少越好，体现着轨迹挖掘和分析方法的运行效率。两者是相对的，因此在协调基础上提出2个阀值A,B：
在原始轨迹上元素间，当轨迹的运行方向变化超过A时，将此时的轨迹点称为关键点；
如果轨迹中运动方向变化值都未超出阈值A，规定如果从一个关键点开始，经过B个点，仍未出现运动方向改变超出阈值A的情况,那么将第B个点视为关键点，并依次类推;

4、 关键点轨迹形成算法–KP算法
Input:轨迹 TR=p1p2p3…pi…pn，参数A和B
Output:关键点轨迹 TRkey
1Flag1=1;Flagn=1; //将轨迹开始点和结束点标为关键点
2Len=1;TRkey={}; //初始化关键点轨迹
3for(i=2;i B)
7Flagi=1;Len=1;
8else
9Flagi=0;Len=1;
10 end if
11 end for
12 for(i=1;i<=n;i++) //将关键点加入到关键点轨迹中 13if(Flagi=1) 14TRkey=TRkey∪{pi}; 15end if 16 end for 17 return TRkey//返回关键点轨迹 5、 基于编辑距离的关键点轨迹相似度计算定义编辑距离的关键是设置合理的代价值，即编辑操作应付出相应的代价值。代价值越小，两轨迹相似性越高。在关键点算法基础上，采用编辑距离来计算插入操作的代价、替换操作的代价和删除操作的代价。其中：插入操作(insert)的代价为插入的坐标与当前状态前一个坐标的欧几里德距离；替换操作(substitute)的代价为替换的2个元素之间的欧几里德距离；删除操作(delete)的代价为删除的坐标与当前状态前一个坐标的欧几里德距离；对于两条轨迹关键点构成的序列 P 和 Q， m 和 n 分别为 序列 P 和 Q 的长度，pi 为序列 P 的第 i 个元素,qj 为序列 Q 的第 j 个元素，Rest(P)为 P 中除去当前比较字符以外的其他 字符部分，Rest(Q)同理如此。六、轨迹相似度计算方法：STS算法Input:轨迹TR1=p1p2p3…pi…pn和轨迹TR2=q1q2q3…qi…qn,参数A、BOutput:两条稀疏轨迹之间的相似性 1TRkey1=KP(TR1),TRkey2= KP(TR2) //利用KP 算法寻找关键点轨迹 2if(size(TRkey1)==0)//当第一条轨迹的关键点轨迹长度为0时，直接计算插入操作代价 3 Edit(TRkey1,TRkey2)= ∑(j=1,n)insert(qj) ; //n 为 TRkey2的长度 4else if(size(TRkey2)==0)//当第二条轨迹的关键点轨迹长度为0时，直接计算删除操作代价 5 Edit(TRkey1,TRkey2)= ∑(i=1,m)delete(pi);//m 为 TRkey1的长度 6end if 7Edit(TRkey1,TRkey2)= min( Edit(Rest(TRkey1),Rest(TRkey2))+substitute(pm,qn), 9 Edit(Rest(TRkey1),TRkey2)+delete(pm,qn), 10Edit(TRkey1,Rest(TRkey2))+insert(qn) );//通过递归函数，计算得出编辑代价11 Return 1/(1+Edit(TRkey1,TRkey2)) //返回轨迹间的相似性 七、实验1. 比较 STS 算法与以原始坐标数据进行编辑距离计算的ERP算法在计算轨迹相似性的运行效率—–其实就是能得出相似度（编辑距离）就行2. 改变阈值A与B进行相似度计算，观察运行效率，找到最优值PS：ERP算法—-直接用轨迹数据计算编辑距离，数据更多，所用时间更长，噪声影响大，才用程序1，3程序1.获取轨迹数据的程序 Trajectory—–都是GPS经纬度数据程序2.需要先编写一个计算θ值的函数，计算每条原始轨迹数据间的角度再根据角度值提取关键点轨迹的数据的函数–KP算法参考：在Apache的commons组件包有一个Math的组件，它已经提供了相关的反三角函数1. import org.apache.commons.math3.util.FastMath;  2.   3. public class MathTest {  4.   5.     /** 6.      * @param args 7.      */  8.     public static void main(String[] args) {  9.         double v = 0.57735026918962576450914878050196;   //30度角  10.         double angle = Math.toDegrees(FastMath.atan(v)); //注意反正切函数返回的是弧度制的值, 这里重新转成了角度值.  11.         System.out.println(angle);  12.     }  13.   14. }  程序3.先编写insert(),substitute(),delete()函数—-采用欧氏距离，结果为真实的实数对关键点轨迹计算编辑距离（衡量相似度）的函数 使用Edit()矩阵动态递归算法参考：不同点1. package editDistance;  2. /** 3.  * 编辑距离(删除，添加，替换 得到相等字符串所需次数)算法 4.  * s = “eeba”, t=”abac” 5.  * 使用一个二维数组记录所需编辑次数(s为纵向，t为横向)， 6.     0 1 2 3 4  7.     1 1 2 3 4  8.     2 2 2 3 4  9.     3 3 2 3 4  10.     4 3 3 2 3  11.     第二列为当t取一个字符a的时候，s依次为  “”、”e”、”ee”、”eeb”、”eeba”所需的编辑距离 12.     其余的类似 13.     以动态规划角度来看，以edit(i,j)来代表矩阵中的元素，其意义为i代表s取前i个字符，j代表t取前个字符 14.     如edit(2,2)代表s=”ee”，t=”ab”的编辑距离，在矩阵中为2（代码中还有一个0行） 15.     edit(i,j)=minist(edit(i,j-1)+1, edit(i-1,j)+1, edit(i-1,j-1)+cost) 16.     edit(2,2)=minist(edit(2,1)+1, edit(1,2)+1, edit(1,1)+cost) 17.     即取(“ee”,”a”)(“e”,”ab”)(“ee”,”ab”)三个编辑距离中的最小值 18.     s.charAt(i-1)==t.charAt(j-1)时，cost=1 19.  * @author yanjie 20.  * 21.  */  22. public class EditDistance {  23.       24.     public static void main(String[] args) {  25.         String s = “eeba”, t=”abac”;  26.         int d = getEditDistance(s, t);  27.         System.out.println(d);  28.     }  29.     //返回三者最小值  30.     private static int Minimum(int a, int b, int c) {  31.         int im =  a