计算两组标签/关键词相似度算法

我会带着你远行 2022-08-20 06:17 219阅读 0赞

#### 原文连接 [http://www.zhaochao.net/index.php/2016/02/05/14/][http_www.zhaochao.net_index.php_2016_02_05_14] ####

### 写作背景 ###

标签在互联网行业有大量的应用，给博客打标签，给商品打标签，给新闻打标签。通常每篇文章会打上多个标签，好的标签系统给后期的数据分析可以带来巨大的利处。最近想做一个基于内容的新闻简单推荐系统，其中的一个推荐权重就是两篇新闻标签的相似度，由于没什么数据挖掘和机器学习经验，自己一直在摸索，感觉自己还没有入门，先记录下来，慢慢学习。

### 应用案例 ###

比较现在有两篇文章  
**文章1**：广州车展实拍东风悦达起亚K2两厢 **标签**：起亚, 实拍, 汽车, 新闻, 广州车展, 东风, 资讯  
**文章2**：广州国际车展：北京现代首望概念车首发现场 **标签**广州, 现场, 汽车, 国际车展, 新闻, 首发, 资讯, 现代, 概念, 北京

现在要通过标签计算这两篇文章的相似度

### levenshtein distance 编辑距离算法 ###

> 编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。  
> 例如将kitten一字转成sitting：  
> sitten （k→s）  
> sittin （e→i）  
> sitting （→g）  
> 俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

#### 算法JAVA实现 ####

算法具体怎么实现在时间再分析一下，能过下面代码我们可以可到两组标签的相似度为0.19999998807907104

public static void main(String[] args) {
            String[] tag1 = { "起亚", "实拍", "汽车", "新闻", "广州车展", "东风", "资讯"};
            String[] tag2 = {
       "广州", "现场", "汽车", "国际车展", "新闻", "首发", "资讯", "现代", "概念", "北京"};
            double similar = levenshtein(tag1, tag2);
            System.out.println(similar);
    
        }
    
        public static float levenshtein(String[] str1, String[] str2) {
            // 计算两个字符串的长度。
            int len1 = str1.length;
            int len2 = str2.length;
            // 建立上面说的数组，比字符长度大一个空间
            int[][] dif = new int[len1 + 1][len2 + 1];
            // 赋初值，步骤B。
            for (int a = 0; a <= len1; a++) {
                dif[a][0] = a;
            }
            for (int a = 0; a <= len2; a++) {
                dif[0][a] = a;
            }
            // 计算两个字符是否一样，计算左上的值
            int temp;
            for (int i = 1; i <= len1; i++) {
                for (int j = 1; j <= len2; j++) {
                    if (str1[i - 1] == str2[j - 1]) {
                        temp = 0;
                    } else {
                        temp = 1;
                    }
                    // 取三个值中最小的
                    dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1, dif[i - 1][j] + 1);
    
                }
            }
            // 取数组右下角的值，同样不同位置代表不同字符串的比较
            // System.out.println("差异步骤：" + dif[len1][len2]);
            // 计算相似度
            float similarity = 1 - (float) dif[len1][len2] / Math.max(str1.length, str2.length);
    
            return similarity;
        }
    
        private static int min(int a, int b, int c) {
            int min = a < b ? a : b;
            return min < c ? min : c;
        }

### 向量空间模型(VSM)的余弦定理公式(cos) ###

编辑距离算法虽然可以计算两组标签的相似度，但是会有一个很大的问题，就是标签中的每个关键词权重是不一样的，它不能带权重计算两组标签的相似度，可以通过向量空间模型计算两组标签的空间夹角的余弦值。具体实现方法如下：  
**建立标签库**  
如下所示为我所建的标签库，其中id为标签的唯一ID，name为标签的名称，sore为标签的权重

id  name  sore
    1   新闻  1
    2   诸暨  0.730766
    3   中国  0.684373
    4   浙江  0.634607
    5   杭州  0.605594
    6   广播  0.526306
    7   我市  0.487695
    8   视频  0.444434
    9   工作  0.42062
    10  男子  0.287171

**建立标签向量**  
假如有两篇文章标签分别为  
文章1：中国，杭州，男子 ，工作  
文章2： 我市，杭州，工作

通过标签库建立向量  
文章1: (0,0,684373,0,605594,0,0,0,42062,28717)  
文章2:(0,0,0,0,605594,0,487695,0,420062,0)

向量的建立方法建立一个多维向量，维数等于向量库的记录数，向量的值为文章的标签的权重，如果没有标签则为0，上面以10个标签记录为例，不过一般标签库至少几十万，所以要建立几十万维的向量

**计算向量的cos值**

![这里写图片描述][cosTheta.png]

v1\*v2=0\*0+0\*0+ ….+28717\*0=3.8441274068E11  
||v1||=sqrt(0^2+0^2+…+28717^2)=915261.9154635464  
||v2||=sqrt(0^2+0^2+…+420062^2+0^2)=883766.1397140083

相似度: v1\*v2/(||v1||\*||v2||)=0.47524222827391666

[http_www.zhaochao.net_index.php_2016_02_05_14]: http://www.zhaochao.net/index.php/2016/02/05/14/
[cosTheta.png]: /images/20220731/33fd970b20d143c094828bd09723dbc6.png