基于编辑距离的关键点轨迹相似性计算
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
1 Flag1=1;Flagn=1; //将轨迹开始点和结束点标为关键点
2 Len=1;TRkey={}; //初始化关键点轨迹
3 for(i=2;i
7 Flagi=1;Len=1;
8 else
9 Flagi=0;Len=1;
10 end if
11 end for
12 for(i=1;i<=n;i++) //将关键点加入到关键点轨迹中
13 if(Flagi=1)
14 TRkey=TRkey∪{pi};
15 end 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、B
Output:两条稀疏轨迹之间的相似性
1 TRkey1=KP(TR1),TRkey2= KP(TR2) //利用KP 算法寻找关键点轨迹
2 if(size(TRkey1)==0)
//当第一条轨迹的关键点轨迹长度为0时，直接计算插入操作代价
3 Edit(TRkey1,TRkey2)= ∑(j=1,n)insert(qj) ; //n 为 TRkey2的长度
4 else if(size(TRkey2)==0)
//当第二条轨迹的关键点轨迹长度为0时，直接计算删除操作代价
5 Edit(TRkey1,TRkey2)= ∑(i=1,m)delete(pi) ; //m 为 TRkey1的长度
6 end if
7 Edit(TRkey1,TRkey2)= min( Edit(Rest(TRkey1),Rest(TRkey2))+substitute(pm,qn),
9 Edit(Rest(TRkey1),TRkey2)+delete(pm,qn),
10 Edit(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