DTW的java实现
在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离，但是对于一些特殊情况，欧氏距离存在着其很明显的缺陷，比如说时间序列，举个比较简单的例子，序列A：1,1,1,10,2,3，序列B：1,1,1,2,10,3，如果用欧氏距离，也就是distance[i][j]=(b[j]-a[i])*(b[j]-a[i])来计算的话，总的距离和应该是128，应该说这个距离是非常大的，而实际上这个序列的图像是十分相似的，这种情况下就有人开始考虑寻找新的时间序列距离的计算方法，然后提出了DTW算法，这种方法在语音识别，机器学习方便有着很重要的作用。
这个算法是基于动态规划（DP）的思想，解决了发音长短不一的模板匹配问题，简单来说，就是通过构建一个邻接矩阵，寻找最短路径和。
还以上面的2个序列作为例子，A中的10和B中的2对应以及A中的2和B中的10对应的时候，distance[3]以及distance[4]肯定是非常大的，这就直接导致了最后距离和的膨胀，这种时候，我们需要来调整下时间序列，如果我们让A中的10和B中的10对应，A中的1和B中的2对应，那么最后的距离和就将大大缩短，这种方式可以看做是一种时间扭曲，看到这里的时候，我相信应该会有人提出来，为什么不能使用A中的2与B中的2对应的问题，那样的话距离和肯定是0了啊，距离应该是最小的吧，但这种情况是不允许的，因为A中的10是发生在2的前面，而B中的2则发生在10的前面，如果对应方式交叉的话会导致时间上的混乱，不符合因果关系。
接下来，以output[6][6](所有的记录下标从1开始，开始的时候全部置0)记录A，B之间的DTW距离，简单的介绍一下具体的算法，这个算法其实就是一个简单的DP，状态转移公式是output[i][j]=Min(Min(output[i-1][j],output[i][j-1]),output[i-1][j-1])+distance[i][j];最后得到的output[5][5]就是我们所需要的DTW距离。
java代码实现
package DTW;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.text.MessageFormat;
import java.util.ArrayList;
public class DTW_Tool {
private String filePath;
private double[][] distance;
private int[] X;
private int[] Y;
private double[][] dtw;
ArrayList<String[]> listTemp;
public DTW_Tool(String filePath){
this.filePath = filePath;
readDataFile();
}
public DTW_Tool(int[] X,int[] Y){
this.X = new int[X.length];
for(int i=0;i<X.length;i++){
this.X[i]=X[i];
}
this.Y = new int[Y.length];
for(int i=0;i<Y.length;i++){
this.Y[i]=Y[i];
}
}
private void readDataFile() {
File file = new File(filePath);
listTemp = new ArrayList<String[]>();
try{
BufferedReader in = new BufferedReader(new FileReader(filePath));
String str;
String[] strTemp;
while((str=in.readLine())!=null){
strTemp = str.split(" ");
listTemp.add(strTemp);
}
}catch(IOException e){
e.printStackTrace();
}
//利用listTemp初始化两个带比较的数列
}
public void initXAndY(){
int i;
X = new int[listTemp.get(0).length];
for(int k=0;k<listTemp.get(0).length;k++){
X[k] = Integer.parseInt(listTemp.get(0)[k]);
}
double dtw;
double minDtw = Double.MAX_VALUE;
int minDex =0;
//第一行作为模板
for(int j=1;j<listTemp.size();j++){
dtw =0;
Y = new int[listTemp.get(j).length];
for(int k=0;k<listTemp.get(j).length;k++){
Y[k] = Integer.parseInt(listTemp.get(j)[k]);
}
dtw = getDtwDist();
if(dtw<minDtw){
minDtw = dtw;
minDex = j;
}
}
/* System.out.print(minDex);*/
System.out.print(MessageFormat.format("匹配程度最高的序号为{0}，距离为{1}", minDex,minDtw));
System.out.print("-------");
for(int l=0;l<listTemp.get(minDex).length;l++){
System.out.print(listTemp.get(minDex)[l]+"---");
}
}
private double computeDistance(int x,int y){
return Math.sqrt((x-y)*(x-y));
}
private void initDistance(){//先初始化点与点之间的距离
distance = new double[X.length][Y.length];
for(int i=0;i<X.length;i++){
for(int j =0;j<Y.length;j++){
distance[i][j] = computeDistance(X[i],Y[j]);
}
}
}
private void computeDtw(){//初始化dtw数组
dtw = new double[X.length][Y.length];
initDistance();
//根据distance数组来初始化dtw数组
dtw[0][0]=0;
for(int i=0;i<X.length;i++){
for(int j=0;j<Y.length;j++){
//这里要对i,j进行判定，其实就是加入边界值的考虑
if(i>00&&j>0){
dtw[i][j]=minDist(dtw[i][j-1]+distance[i][j],dtw[i-1][j]+distance[i][j],dtw[i-1][j-1]+2*distance[i][j]);
}
else if(i==0&&j>0){
dtw[i][j] = dtw[i][j-1]+distance[i][j];
}
else if(i>0&&j==0){
dtw[i][j]= dtw[i-1][j]+distance[i][j];
}else{
dtw[i][j]=0;
}
}
}
}
public double getDtwDist(){
computeDtw();
return dtw[X.length-1][Y.length-1];
}
private double minDist(double dist1,double dist2,double dist3){
return (dist1<dist2?(dist2<dist3?dist3:(dist1>dist3?dist3:dist1)):(dist2>dist3?dist3:dist2));
}
}主程序
public class Client_DTW {
/**
* @param args
*/
public static void main(String[] args) {
/*int[] x={1,2,3,4,5,0};
int[] y={2,3,4,5,0,1};
DTW_Tool tool = new DTW_Tool(x,y);
System.out.print(tool.getDtwDist());*/
String filePath = "D:\\input\\input13.txt";
DTW_Tool tool = new DTW_Tool(filePath);
tool.initXAndY();
}
}腾讯云开发者
