1.交通聚类：编辑距离（Levenshtein距离）Java实现

1.最近工作中要实现用户车辆的行驶路线的聚类，由于所给的数据只有用户一天中交通卡口所监视的卡口名称：即青岛路-威海路-济阳路。

要通过聚类实现车辆路线的规律分析，首先要解决的是相似度问题，我们知道计算相似度可以用：空间向量距离（欧式距离，余弦相似度）等算法。可是这些在此要求中都不适应，故需要用编辑距离来解决此问题

2. 编辑距离的思想：

a.是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如：将kitten 转成 sitting:

1.sitten (k->s)

2.sittin (e –> i)

3.sitting (-> g)

俄罗斯科学家 Vladimir Levenshtein在1965年提出的这个概念

3. 问题：找出字符串的编辑距离，即把一个字符串S1最少经过多少步操作变成字符串S2，操作有三种：添加字符，删除字符，修改一个字符。

解析：首先定义一个这样的函数—edit（i,j）,它表示第一个字符串的长度为i 的子串到第二个字符串的长度为j 的子串的编辑距离。

显然有如下的动态规划公式：

1.if i == 0 且 j == 0，edit(i,j)==0

2. if i == 0 且j >0， edit(i,j )==j

3.if i >0且 j ==0 ,edit(i,j)==i

4.if i >= 1且j>=1，edit(i,j) == min{ edit (i-1,j)+1, edit(i,j-1)+1, edit(i –1,j-1)+f(i,j)} , 当第一个字符串的第i 个字符不等于第二个字符串的第j个字符时，f(i,j) =1; 否则，f(i,j) =0.

4. 上代码：

package com.dk.route;

/**

 * 编辑距离,计算文本的相似度

 * @author zzy

 *

 */

public class LevenshteinDistance {

    public static void main (String[] args){

        String str1 = "东海路与燕儿岛路路口 山东路海泊桥 山东路与抚顺路路口 辽阳西路与劲松四路路口 重庆中路与振华路路口";

        String str2 = "青岛东收费站 夏庄主站收费站 S217朱诸路-张应大朱戈 胶宁高架路三百惠桥上";

//        String str2 = "S217朱诸路-张应大朱戈";//S217朱诸路-张应大朱戈

//        String str1 = "青兰高速（双埠-管家楼）K23+800桩号增大方向";

//        String str2 = "青岛路";

//        String str1 = "山东";

        System.out.println("ld= "+ levenshteinDistance(str1, str2));

//        System.out.println("sim="+sim(str1,str2) );

    }

    private static int min(int one,int two,int three){

        int min = one;

        if (two < min){

            min = two;

        }

        if (three <min){

            min = three;

        }

        return min;

    }

    public static int levenshteinDistance(String str1,String str2){

        int d[][]; // 矩阵

        int n = str1.length();

        int m = str2.length();

        int i ; // for str1

        int j; // for str2

        char ch1;

        char ch2;

        int temp; // 记录相同字符,在某个矩阵位置值得增量,不是0就是1;

        if(n == 0){

            return m;

        }

        if (m == 0){

            return n;

        }

        d = new int [n+1][m+1];

        for ( i = 0; i < n ; i++) { // 初始化第一列

            d[i][0] = i;

        }

        for(j = 0; j<= m;j++){ // 初始化第一行

            d[0][j] = j;

        }

         for (i =1; i<= n;i++){

             ch1 = str1.charAt(i-1);

             for(j=1;j <= m;j++){

                 ch2 = str2.charAt(j-1);

                 if(ch1 == ch2){

                     temp = 0;

                 }else{

                     temp =1;

                 }

                 d[i][j] = min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+temp);

             }

         }

         return d[n][m];

    }

    public static double sim (Route initR,Route r){

        if (initR.routename == null || r.routename == null){

            return 0;

        }

        String str1 = initR.routename;

        String str2 = r.routename;

        double ld = levenshteinDistance(str1, str2);

        double strMax = Math.max(str1.length(), str2.length());

        double sim =1- ld/strMax;

//        if(ld < strMax){

//            sim = 1-ld/Math.min(str1.length(), str2.length());

//        }

//        System.out.println(initR.routename +"-------与-------" +r.routename +"的相似度=" + sim);

        return sim;

    }

}

.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: consolas, "Courier New", courier, monospace;
background-color: #ffffff;
/*white-space: pre;*/
}
.csharpcode pre { margin: 0em; }
.csharpcode .rem { color: #008000; }
.csharpcode .kwrd { color: #0000ff; }
.csharpcode .str { color: #006080; }
.csharpcode .op { color: #0000c0; }
.csharpcode .preproc { color: #cc6633; }
.csharpcode .asp { background-color: #ffff00; }
.csharpcode .html { color: #800000; }
.csharpcode .attr { color: #ff0000; }
.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}
.csharpcode .lnum { color: #606060; }

源码：https://github.com/chaoren399/dkdemo/blob/master/agenes/src/agenesdemo/LevenshteinDistance.java

巴特西

1.交通聚类：编辑距离（Levenshtein距离）Java实现

最新文章

热门文章

巴特西

1.交通聚类：编辑距离 （Levenshtein距离）Java实现

最新文章

热门文章

1.交通聚类：编辑距离（Levenshtein距离）Java实现