【地理空间】轨迹相似度算法（DTW、LCSS） |
您所在的位置：网站首页 › 如何用EXCEL计算两条曲线的重合度 › 【地理空间】轨迹相似度算法（DTW、LCSS） |
【地理空间】轨迹相似度算法（DTW、LCSS）
|
序列相似度
在现实生活中我们常常需要比较两串数字的相似度，比如两串数字（一维），再比如两条轨迹（二维），那么如何计算两个序列的相似度呢？有人提出了DTW算法，一种计算序列距离的方法。 DTW算法原理算法原理主要参考：https://blog.csdn.net/raym0ndkwan/article/details/45614813。 在这里只是进行更详细的分析和介绍，以两个数组为例： s1 = [1, 2, 3, 4, 5, 5, 5, 4] s2 = [3, 4, 5, 5, 5, 4] 首先将这两个数组放在矩阵中，列对应s1，行对应s2，矩阵中的数字表示s1和s2相应位置的两个数字的差值（如果是二维平面上的，就是两个点的欧几里得距离），（0,0）的位置为0，其余位置是无穷大，以此就得到了距离矩阵D： 这里分别实现了一维和二维的DTW算法 public class DTW { //一维比较 //s1 = [1, 2, 3, 4, 5, 5, 5, 4] //s2 = [3, 4, 5, 5, 5, 4] public void DTW_1(int[] s1, int[] s2) { int r = s1.length; int c = s2.length; //计算距离矩阵M int[][] D0 = new int[r + 1][c + 1]; for (int i = 0; i < r + 1; i++) { for (int j = 0; j < c + 1; j++) { if (i == 0 && j == 0) { D0[i][j] = 0; } else if (i == 0) { D0[i][j] = Integer.MAX_VALUE; } else if (j == 0) { D0[i][j] = Integer.MAX_VALUE; } else { D0[i][j] = Math.abs(s1[i - 1] - s2[j - 1]); } } } int[][] D = new int[r][c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { D[i][j] = D0[i + 1][j + 1]; } } System.out.println("距离矩阵D:"); System.out.println(Arrays.deepToString(D).replaceAll("],", "]," + System.getProperty("line.separator"))); //计算损失矩阵M int[][] MC = D0.clone(); for (int i = 1; i < r + 1; i++) { for (int j = 1; j < c + 1; j++) { MC[i][j] += Math.min(Math.min(MC[i - 1][j - 1], MC[i][j - 1]), MC[i - 1][j]); } } int[][] M = new int[r][c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { M[i][j] = MC[i + 1][j + 1]; } } System.out.println("损失矩阵M:"); System.out.println(Arrays.deepToString(M).replaceAll("],", "]," + System.getProperty("line.separator"))); System.out.println("序列距离:" + M[r - 1][c - 1]); } public void DTW_2(List coords1, List coords2) { int r = coords1.size(); int c = coords2.size(); //计算距离矩阵M double[][] D0 = new double[r + 1][c + 1]; for (int i = 0; i < r + 1; i++) { for (int j = 0; j < c + 1; j++) { if (i == 0 && j == 0) { D0[i][j] = 0; } else if (i == 0) { D0[i][j] = Double.MAX_VALUE; } else if (j == 0) { D0[i][j] = Double.MAX_VALUE; } else { D0[i][j] = coords1.get(i - 1).distance(coords2.get(j - 1)); } } } DecimalFormat df = new DecimalFormat("#.00"); double[][] D = new double[r][c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { D[i][j] = Double.parseDouble(df.format(D0[i + 1][j + 1])); } } System.out.println("距离矩阵D:"); System.out.println(Arrays.deepToString(D).replaceAll("],", "]," + System.getProperty("line.separator"))); //计算损失矩阵M double[][] MC = D0.clone(); for (int i = 1; i < r + 1; i++) { for (int j = 1; j < c + 1; j++) { MC[i][j] += Math.min(Math.min(MC[i - 1][j - 1], MC[i][j - 1]), MC[i - 1][j]); } } double[][] M = new double[r][c]; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { M[i][j] = MC[i + 1][j + 1]; } } System.out.println("损失矩阵M:"); System.out.println(Arrays.deepToString(M).replaceAll("],", "]," + System.getProperty("line.separator"))); System.out.println("序列距离:" + M[r - 1][c - 1]); } } 问题目前序列距离必须互相参照，比如只能知道两个序列和同一个序列之间，哪两个序列更为相似，序列距离单调递增，无法单纯的判断两个序列的相似程度。 LCSS算法简单的说，LCSS算法就是寻找两个序列的最大公共子序列，算法逻辑可以参考这篇文章，计算出最大公共子序列的长度之后，进行归一化处理，即可获得相似度的百分比。 LCSS实现参考上述文章之后，Java实现起来也不难，得到两条轨迹的相似度百分比。 public class LCSS { private List l1; private List l2; private List lcs = new ArrayList(); public boolean isNearby(Coordinate a, Coordinate b) { if (DistanceUtil.getDistance(a, b) < 50) return true; return false; } public void printLcs(int[][] flag, List a, int i, int j) { if (i == 0 || j == 0) return; if (flag[i][j] == 1) { printLcs(flag, a, i - 1, j - 1); lcs.add(a.get(i - 1)); } else if (flag[i][j] == 2) { printLcs(flag, a, i, j - 1); } else { printLcs(flag, a, i - 1, j); } } public double lcs(List l1, List l2) { int len1 = l1.size(); int len2 = l2.size(); int[][] c = new int[len1 + 1][len2 + 1]; int[][] flag = new int[len1 + 1][len2 + 1]; for (int i = 0; i < len1; i++) { for (int j = 0; j < len2; j++) { if (isNearby(l1.get(i), l2.get(j))) { c[i + 1][j + 1] = c[i][j] + 1; flag[i + 1][j + 1] = 1;//1='ok' } else if (c[i + 1][j] > c[i][j + 1]) { c[i + 1][j + 1] = c[i + 1][j]; flag[i + 1][j + 1] = 2;//2='left' } else { c[i + 1][j + 1] = c[i][j + 1]; flag[i + 1][j + 1] = 3;//3='up' } } } printLcs(flag, l1, len1, len2); //归一化处理 return (lcs.size() * 1.0 / Math.min(len1, len2)); } public static void main(String[] args) { List l1 = new ArrayList(); l1.add(new Coordinate(114.300, 30.1)); l1.add(new Coordinate(114.302, 30.101)); l1.add(new Coordinate(114.3023, 30.1002)); l1.add(new Coordinate(114.30235, 30.1011)); l1.add(new Coordinate(114.304, 30.1003)); List l2 = new ArrayList(); l2.add(new Coordinate(114.301, 30.1002)); l2.add(new Coordinate(114.3023, 30.1015)); LCSS lcss = new LCSS(); System.out.println(lcss.lcs(l1, l2)); } } |
接下来就是最重要的一步，通过距离矩阵D，按照公式计算损失矩阵M： M[i][j] = D[i][j] + min(M[i - 1][j - 1], M[i][j - 1], M[i - 1][j]) 将距离矩阵D的第一行第一列（除了i=0，j=0）赋值为无穷大就是排除计算它们参与最小值的计算，这样就得到了损失矩阵M： 
序列距离就是矩阵最右下角的数值，数值越接近0，相似度越高；数值越大，相似度越低。【本文地址】