前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >DTW的java实现

DTW的java实现

作者头像
张凝可
发布2019-08-22 11:02:39
1.3K0
发布2019-08-22 11:02:39
举报
文章被收录于专栏:技术圈

在日常的生活中我们最经常使用的距离毫无疑问应该是欧式距离,但是对于一些特殊情况,欧氏距离存在着其很明显的缺陷,比如说时间序列,举个比较简单的例子,序列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代码实现

代码语言:javascript
复制
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));
		
	}
	
}

主程序

代码语言:javascript
复制
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();

	}

}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016年08月24日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
语音识别
腾讯云语音识别(Automatic Speech Recognition,ASR)是将语音转化成文字的PaaS产品,为企业提供精准而极具性价比的识别服务。被微信、王者荣耀、腾讯视频等大量业务使用,适用于录音质检、会议实时转写、语音输入法等多个场景。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档