聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

一种简单的计算item相似度算法

2016-11-05 11:50 浏览: 1541412 次 我要评论(0 条) 字号:

      计算item之间相似度是个有意义的工作,比如词的相似度就有很多应用场景。词相似度就有很多做法,工业上现在用得最多的可能是word2vec了,还有些算语义相似度的偏学术的办法。


这里介绍一种比较简单可行的思路,不只是算词相似度,其他类型也可以。这个方法很早以前在读书时候就知道的,基本思路也是把item表示成其他item的向量之后,再用向量进行相似度计算。


怎么表示这样的关系,就变成一个可以自由控制的开放方法,最简单的办法,用item和item之间的关联度来表示向量上对应维度的强弱。而任何关联度计算公式的核心都包含两个item同时出现(共现)的程度,共现通常自由定义。比如在文本词的应用环境中,可以用同时出现在段落、文章、甚至句子。再比如商品环境中,可以定义成一定范围内的同一个人的购物清单。


于是一个itemi可以表示成所有item的向量Vi=[0.1, 0.2, 3.1, 0, 0...] 如此格式,对itemi和j的相似度就可以用Vi和Vj的相似度来表征了,比如cosine, jaccard、皮尔逊等等。使用这样的表示的好处是可以发现真正的"相似"性,因为如果两个item a,b 真的是相似,它们很可能不会出现在一个共现场景下,例如同义词在同样的环境只会选一个,或者相同功能的商品一般人只会买一个,而不会选多个。但它们都共同的和其他item同时出现过,它们和其他item的关联很可能是稳定的,但a,b之间很少共现。


这种方法简单,但算法效率并不是太高,因为算两两关联至少是个O(n^2)的复杂度。n表示item的数量。

第一步,算两两item的关联度,需要枚举所有的共现出来,再累加;复杂度是O(n^2),通常item都比较稀疏,还算能接受。

第二步,每个item表示成V之后,两两之间的V还要算一个相似度,其实是O(n^2) 再乘以V的维度数,应该是O(n^3)。


事实上也有一些加速的算法了,但我还没研究过,我自己想到一个加速第二步的办法。

首先,item表示成其他item关系,应该让尽可能保留强关联的维度,也就是V的大部分维度是0。

其次,把所有V表示出来成一个矩阵M,M肯定是对角线对称的。 V根据cosine的公式 分子是两个向量Va Vb中交集部分,那么∑(wa * wb) 在这个M上 对任意两个V 累加同行部分和同列部分 是等价的。所以我们不需要对任意两个V在每个维度单独累加,而是可以累加每个V上的二元组wi * wj 而得到,最后再除以sqrt(∑(Va) * ∑(Vb))。

       举个例子                                             a  ,   b   ,  c  , d    

                                                             a   0    0.5   0.3  0.1

                                                             b  0.5   0    0.7   0.9

                                                             c   0.3  0.7   0   0.5

                                                             d   0.1  0.9  0.5    0

     这样一个矩阵,横着看算Vc和Vd的相似度,就是a,b对应两列在c,d两行求出的交集(左下角四个元素),除再以c和d各自V的大小。这个过程也等价于右上角四个元素换个方向的计算。 那就是把 (c,d) 这样的元组 不管在哪行出现,交集全部拿出来再进行累加就行了。这样的好处是第二步的过程和第一步完全一样了,比写一个V求相似度函数要简单、方便、效率更高,可以直接加入MR框架中。


可以看到相似度其实是一种更具体的关联度,关联度上直接挖掘未必能得出比较好解释的结果。有了相似度,就可以在这种关系上进行进一步的真正的聚类团体发现。



作者:lgnlgn 发表于2015/4/5 18:42:35 原文链接
阅读:1079 评论:4 查看评论


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复