如何设计一个比较两篇文章相似性的算法?

如何设计一个比较两篇文章相似性的算法?
假如我们想得到更多的局部信息,如相似片段、相似百分比,那又该如何去做?
任何idea都可以分享

sonyanda
sonyanda
41
编辑于2012-10-16
评论 (0)链接2012-10-15 

如果是话题是否相似,一般是关键词匹配的方法

想了一种基于统计模型的算法,不知道实际效果如何:
首先收集足够多的样本,分词,统计各个词的频度(文章中出现次数 / 总词数),然后计算每个词的平均频度(频度和 / 文章数)和频度方差((频度 - 平均值) ^ 2 / (文章数 - 1))
即将每个词的出现频度建模为一个高斯随机变量。

然后对要比较的文章先分词,统计频度,然后计算对数似然比:
ln(p(A,B独立) / p(A,B同类))
= ln(p(A)P(B) / p(A,B同类))
= lnp(A) + lnp(B) - lnp(A,B同类)

将概率p用似然值P替代,根据高斯变量的特性:
lnP(A) = -1/2 * ∑((D_Ak - D_k)^2 / Sigma_k + ln(2 * PI * Sigma_k))
lnP(B) = -1/2 * ∑((D_Bk - D_k)^2 / Sigma_k + ln(2 * PI * Sigma_k))
lnP(A,B同类) = - 1/2 * ∑((D_Ak - D_Bk)^2 / Sigma_0k + ln(2 * PI * Sigma_0k))

其中D_Ak是A中词k的频度,D_Bk是B中词k的频度,D_k是平均频度,Sigma_k是方差,而Sigma_0k是某组参数,代表同类文章中的词频方差(或者说接受多接近的词频为同类),可以用人工标记训练的方法得到,也可以简单点所有的都设为一个常数,或者设为Sigma_k的一个倍数。
则对数似然比可以写为:
ln(p(A,B独立) / p(A,B同类))
= -1/2 * ∑((D_Ak - D_k)^2 / Sigma_k + ln(2 * PI * Sigma_k)) -1/2 * ∑((D_Bk - D_k)^2 / Sigma_k + ln(2 * PI * Sigma_k)) + 1/2 * ∑((D_Ak - D_Bk)^2 / Sigma_0k + ln(2 * PI * Sigma_0k))
= -1/2 * ∑((D_Ak - D_k)^2 / Sigma_k + ln(2 * PI * Sigma_k) + (D_Bk - D_k)^2 / Sigma_k + ln(2 * PI * Sigma_k) - (D_Ak - D_Bk)^2 / Sigma_0k - ln(2 * PI * Sigma_0k))

计算出的这个结果就可以当做两篇文章的相似度来看。值越小,两篇文章相似度越高;否则相似度越低。

和直接计算∑(D_Ak - D_Bk)^2的方法比起来,充分考虑了不同词的关键性作用不同,比较关键的词会有比较高的加权。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-10-15

数学之美 系列 12 - 余弦定理和新闻的分类
以下为引用原文:

2006年7月20日 上午 10:12:00
发表者:吴军,Google 研究员

余弦定理和新闻的分类似乎是两件八杆子打不着的事,但是它们确有紧密的联系。具体说,新闻的分类很大程度上依靠余弦定理。

Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻,它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点,我们需要想办法用一组数字来描述一篇新闻。

我们来看看怎样找一组数字,或者说一个向量来描述一篇新闻。回忆一下我们在“如何度量网页相关性”一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词,我们可以计算出它们的单文本词汇频率/逆文本频率值(TF/IDF)。不难想象,和新闻主题有关的那些实词频率高,TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如,词汇表有六万四千个词,分别为

  
    单词编号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作

在一篇新闻中,这 64,000 个词的 TF/IDF 值分别为

  
    单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075

如果单词表中的某个次在新闻中没有出现,对应的值为零,那么这 64,000 个数,组成一个64,000维的向量。我们就用这个向量来代表这篇新闻,并成为新闻的特征向量。如果两篇新闻的特征向量相近,则对应的新闻内容相似,它们应当归在一类,反之亦然。

学过向量代数的人都知道,向量实际上是多维空间中有方向的线段。如果两个向量的方向一致,即夹角接近零,那么这两个向量就相近。而要确定两个向量方向是否一致,这就要用到余弦定理计算向量的夹角了。

余弦定理对我们每个人都不陌生,它描述了三角形中任何一个夹角和三个边的关系,换句话说,给定三角形的三条边,我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c,对应的三个角为 A, B 和 C,那么角 A 的余弦 --

cosA

如果我们将三角形的两边 b 和 c 看成是两个向量,那么上述公式等价于

cosa

其中分母表示两个向量 b 和 c 的长度,分子表示两个向量的内积。举一个具体的例子,假如新闻 X 和新闻 Y 对应向量分别是
x1,x2,...,x64000 和 y1,y2,...,y64000,
那么它们夹角的余弦等于,

clip

当两条新闻向量夹角的余弦等于一时,这两条新闻完全重复(用这个办法可以删除重复的网页);当夹角的余弦接近于一时,两条新闻相似,从而可以归成一类;夹角的余弦越小,两条新闻越不相关。

clip04

至尊宝
至尊宝
1159
编辑于 2012-10-16
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (2)链接 • 2012-10-16
  • 0 支持
    这个方式是ok的 但是速度上会有一些问题。 – babam 2012-10-17
  • 0 支持
    数学改变生活 – 假名士真风流 2012-10-26

大家的答案我都仔细的阅读过了,首先谈谈我的想法:
对于@灵剑2012的答案,这种基于统计的方法更多的关注了文章中词频的信息,而对于词本身的信息似乎关注的不够。而@梁会的答案看似简单明了,但实现起来效率可能是个问题,因为向量本身很长,有64000维。
如果我们并不关注具体的相似片段的话,可以用hash的办法来解决,simhash算法貌似是一个简明有效的算法。算法的原理是这样的:

simhash算法的输入是一个向量,输出是一个f位的签名值。为了陈述方便,假设输入的是一个文档的特征集合,每个特征有一定的权重。比如特征可以是文档中的词,其权重可以是这个词出现的次数。simhash算法如下:
1. 将一个f维的向量V初始化为0;f位的二进制数S初始化为0;
2. 对每一个特征:用传统的hash算法对该特征产生一个f位的签名b。
对i=1到f:
如果b的第i位为1,则V的第i个元素加上特征的权重;
否则,V的第i个元素减去该特征的权重。
3. 如果V的第i个元素大于0,则S的第i位为1,否则为0;
4. 输出S作为签名。

通过计算两篇文章的签名的海明距离得出相似度。
如图:

simhash示意图

以上的所有算法我们都只关注文章的全局信息,忽略了文章的局部信息,如果我们现在需要知道文章的具体相似部分、相似片段、相似百分比,就像论文查重所做的那样,那么应该使用什么样的算法?

sonyanda
sonyanda
41
编辑于 2012-10-16
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (1)链接 • 2012-10-16
  • 0 支持
    算了hash之后就不一定距离近的仍然近了吧……至于维数过高的问题,可以用KL变换等方法预降维,而且本身64000维复杂度也不算高,每一维只算一次,不需要进行矩阵乘法之类的计算。 – 灵剑2012 2012-10-16

我觉得可以采用神经网络中hebb rule的方法。
对于任意一片文章我们都可以抽象成一个列数为Q的特征向量P=[p1,p2,p2,.....pq]
存在权重矩阵W使得Wp=a,a是一个输出向量因此可以发现一组关系为{p1,t1}{p2,t2}....{p_q,t_q}
换言之,当网络的输入参数为p=p_q时,输出应当为a=t_q
hebb rule:
W_new = W_old + αf_i(a_iq)g_j(p_jq)
推算可得W_new = W_old+t_qp_q_tranpose
(抱歉下标什么的写不出来……)
当初始W矩阵为零时可得
W=p cross t_transpose
其中P=[p1,p2,p3,p4,p5...pq] t=[t1,t2,t3,t4,t5....tq]
a=Wp_k=t_k

以下是一个例子

  
public static Vector hardlims(Vector v){
double[] a = new double[v.size()];


for(int i =0;i<v.size();i++){

a[i]=v.get(i)>0?1:-1;

}
Vector res = new DenseVector(a);
return res;

}
public static void main(String[] args){


String v1= "你好吗,我好";
String v2= "你好吗,我不舒服";
String v3 = "我好";
String v4 = "我不舒服";
Matrix W = null;
double[] d1= {1,1,1,1,-1};
double[] d2 = {1,1,1,-1,1};
double[] d3 = {0,0,1,1,-1};
double[] d4 = {0,0,1,-1,1};

Vector p1 = new DenseVector(d1);
Vector p2 = new DenseVector(d2);
//W=ΣPT=p1p1+p2p2,在这里由于预测输出值就是我们所要判定的文章特征向量所以t=p
W = p1.cross(p1).plus((p2.cross(p2)));
Vector p3 = new DenseVector(d3);
Vector p4 = new DenseVector(d4);

//a=hardlims(Wp)
Vector a1 = W.times(p1);
Vector a2 = W.times(p2);
Vector a3 = W.times(p3);
Vector a4 = W.times(p4);

System.out.println(hardlims(a1));
System.out.println(hardlims(a2));
System.out.println(hardlims(a3));
System.out.println(hardlims(a4));
}

输出结果:
{0:1.0,1:1.0,2:1.0,3:1.0,4:-1.0}
{0:1.0,1:1.0,2:1.0,3:-1.0,4:1.0}
{0:1.0,1:1.0,2:1.0,3:1.0,4:-1.0}
{0:1.0,1:1.0,2:1.0,3:-1.0,4:1.0}

可以看出输入"我好"会自动对应找出"你好吗,我好",输入"我不舒服"会自动找出"你好吗,我不舒服"

qqgeogor
编辑于 2012-10-16
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-10-16

这是目前研究比较多的领域,目前没有什么理论突破。所有的模型都是基于经典的VSM((vector space model)的cosine measure计算文章相似度。

http://www2002.org/CDROM/refereed/643/node5.html

基本思想: 文章看成一个向量,每个关键词作为一个特征,每个特征的权重基于term frequency和inverse document frequency计算出来。

这样文章的比较抽象成空间2个向量的比较,定义文章的相似度(similarity)为空间这2个向量的余弦值即可。值为1则2片文章完全相似,为0则完全不同。

google的学术论文搜索有无数,有兴趣的同学google,海量论文在此!!

http://scholar.google.com.hk/scholar?q=text+similarity++VSM&btnG=&hl=zh-CN&as_sdt=0&as_vis=1

如果是中文的VSM还需要个特殊的分词操作,把句子分成一个个的汉字单词。这方面有开源的package可以使用,英文因为本来就是单词结构无需这样的操作。

zjufish
编辑于 2012-10-16
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-10-16

一个快速、高效的Levenshtein算法实现,这个是计算两个字符串的算法,Levenshtein距离又称为编辑距离,是指两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。当然,次数越小越相似喽

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-10-17

英文也是需要分词的,英文应为词状态不同 如单复数,过去时、现在时、进行时等各种状态也需要转换为词根才进行之后的关键词统计,而且一些没有明显意义的词如‘a’,‘is’之类的也会去掉较少维度。然后会进行一些特征抽取或是降维处理,然后进行分类。文本相似性问题可以参考机器学习中文本分类,通常SVM(SUPPORT VECTOR MACHINE)和贝叶斯算法对文本分类比较有效。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-10-22
德问是一个专业的编程问答社区,请 登录注册 后再提交答案