原⽂连接
写作背景
标签在互联⽹⾏业有⼤量的应⽤，给博客打标签，给商品打标签，给新闻打标签。通常每篇⽂章会打上多个标签，好的标签系统给后期的数据分析可以带来巨⼤的利处。最近想做⼀个基于内容的新闻简单推荐系统，其中的⼀个推荐权重就是两篇新闻标签的相似度，由于没什么数据挖掘和机器学习经验，⾃⼰⼀直在摸索，感觉⾃⼰还没有⼊门，先记录下来，慢慢学习。
应⽤案例
⽐较现在有两篇⽂章
⽂章1：⼴州车展实拍东风悦达起亚K2两厢 标签：起亚, 实拍, 汽车, 新闻, ⼴州车展, 东风, 资讯
⽂章2：⼴州国际车展：北京现代⾸望概念车⾸发现场 标签⼴州, 现场, 汽车, 国际车展, 新闻, ⾸发, 资讯, 现代, 概念, 北京
现在要通过标签计算这两篇⽂章的相似度
levenshtein distance 编辑距离算法大运重卡
编辑距离（Edit Distance），⼜称Levenshtein距离，是指两个字串之间，由⼀个转成另⼀个所需的最少编辑操作次数。许可的编辑操作包括将⼀个字符替换成另⼀个字符，插⼊⼀个字符，删除⼀个字符。⼀般来说，编辑距离越⼩，两个串的相似度越⼤。
安耐驰润滑油例如将kitten⼀字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
算法JAVA实现
算法具体怎么实现在时间再分析⼀下，能过下⾯代码我们可以可到两组标签的相似度为0.19999998807907104
长城汽车最新款suvpublic 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)
编辑距离算法虽然可以计算两组标签的相似度，但是会有⼀个很⼤的问题，就是标签中的每个关键词
权重是不⼀样的，它不能带权重计算两组标签的相似度，可以通过向量空间模型计算两组标签的空间夹⾓的余弦值。具体实现⽅法如下：
建⽴标签库gps定位拆除
如下所⽰为我所建的标签库，其中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值
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
发布评论