相似度计算常用方法综述

标签: 数据挖掘 主题相似度 向量空间模型 相似度计算 | 发表时间:2012-07-05 17:59 | 作者:editor
出处:http://stblog.baidu-tech.com

 引言

       相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算。其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系。在信息检索、网页判重、推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算。而针对不同的应用场景,受限于数据规模、时空开销等的限制,相似度计算方法的选择又会有所区别和不同。下面章节会针对不同特点的应用,进行一些常用的相似度计算方法进行介绍。

2向量空间模型

向量空间模型(Vector space model)是应用最广泛的一个基础相似度计算模型,在该模型中,每个对象映射为一个特征向量:

 

作为一个应用广泛的模型,向量空间模型在现有的很多应用中仍然起着至关重要的作用,也是很多扩展方法的基础。

3 基于hash方法的相似计算

       基于hash的相似度计算方法,是一种基于概率的高维度数据的维度削减的方法,主要用于大规模数据的压缩与实时或者快速的计算场景下,基于hash方法的相似度计算经常用于高维度大数据量的情况下,将利用原始信息不可存储与计算的问题转化为映射空间的可存储计算问题,在海量文本重复性判断方面,近似文本查询方面有比较多的应用,google的网页去重 [1],google news的协同过滤 [2,3]等都是采用hash方法进行近似相似度的计算,比较常见的应用场景Near-duplicate detection、Image similarity identification、nearest neighbor search,常用的一些方法包括I-match,Shingling、Locality-Sensitive Hashing族等方法,下面针对几种常见的hash方法进行介绍。

3.1 minhash方法介绍

       Minhash方法是Locality-sensitive hashing [4,5]算法族里的一个常用方法,基本的思想是,对于每一个对象的itemlist,将输入的item进行hash,这样相似的item具有很高的相似度被映射到相同的buckets里面,这样尽量保证了hash之后两个对象之间的相似程度和原来是高相似的,而buckets的数量是远远小于输入的item的,因此又达到降低复杂度的目的。

       minhash方法用Jaccard进行相似度的计算方法,则对于两个集合  , 的相似性的计算方法为:

当两个集合越相似,则该值越接近1,否则越接近0。用minhash方法,将一个集合映射到[0-R-1]之间的值,以相同的概率随机的抽取一个[0-R-1[的一个排列,依次排列查找第一次出现1的行。

设随机排列为43201(edcab),对于C1列,第一次出现1的行是R4,所以h(C1) = 3,同理有h(C2)=2, h(C3)=4, h(C4)=3。

通过多次抽取随机排列得到n个minhash函数h1,h2,…,hn,依此对每一列都计算n个minhash值。对于两个集合,看看n个值里面对应相等的比例,即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列,得到一个n行C列的签名矩阵。因为n可远小于R,这样在压缩了数据规模的同时,并且仍能近似计算出相似度。

3.2 simhash方法介绍

simhash方法是在大文本重复识别常用的一个方法,该方法主要是通过将对象的原始特征集合映射为一个固定长度的签名,将对象之间的相似度的度量转化为签名的汉明距离,通过这样的方式,极大限度地进行了降低了计算和存储的消耗。

3.2.1 签名计算过程

       该方法通过对输入特征集合的计算步骤可以描述如下:

  1. 将一个f维的向量V初始化为0;f位的二进制数S初始化为0;
  2. 对每一个特征:用传统的hash算法对该特征产生一个f位的签名b。对i=1到f:

      如果b的第i位为1,则V的第i个元素加上该特征的权重;

否则,V的第i个元素减去该特征的权重。 

  1. 如果V的第i个元素大于0,则S的第i位为1,否则为0;
  2. 输出S作为签名。

通过上述步骤将输入的表示对象的特征集合转化为该对象的一个签名,在完成签名之后,度量两个对象的相似度的差异即变成了对量二者的指纹的K位的差异情况。

3.2.2 汉明距离查找优化

对于如何快速查找出某一个签名是否与其存在最大差异不超过K个bit的指纹,Detecting Near-Duplicates for Web Crawling这篇论文中进行了介绍。该查找方法的基本思想是利用空间换时间的方法,该方法的依据是需要查找的两个指纹的差异很小,这样可以通过将原始指纹进行分块索引,如果两个指纹的差异很小,则合理的分块后,根据鸽笼原理,其中存在一定数量的块是一致的,通过利用相同的块进行相似的指纹的召回,只需要比对召回的块中有差异的块的bit差异,这样减少了需要比对的数量,节省了比对的时间开销。

3.3 小结

       hash方法的相似度计算的主要应用场景,一般是针对大规模数据进行压缩,在保证效果损失可接受的情况下,节省存储空间,加快运算速度,针对该方法的应用,在目前的大规模的互联网处理中,很多相似度的计算都是基于这种近似性的计算,并取得了比较好的效果。

设随机排列为43201(edcab),对于C1列,第一次出现1的行是R4,所以h(C1) = 3,同理有h(C2)=2, h(C3)=4, h(C4)=3。

通过多次抽取随机排列得到n个minhash函数h1,h2,…,hn,依此对每一列都计算n个minhash值。对于两个集合,看看n个值里面对应相等的比例,即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列,得到一个n行C列的签名矩阵。因为n可远小于R,这样在压缩了数据规模的同时,并且仍能近似计算出相似度。

4 基于主题的相似度计算

       传统的BOW(bag-of_words)模型,一般都会建立在特征独立假设的基础上,按照特征向量的匹配情况来度量对象之间的相似度,但是在实际的应用中,很多时候特征之间存在着很多的关联关系,二者在传统的BOW模型中无法解决,在这个基础上,引入了主题的概念,通过主题的思想,建立起基本特征与对象的中间层的关联关系,主题的概念的引入,主要是在原有的基本特征粒度的基础上,引入了更为丰富的隐含层特征,提高了相似性计算的效果,常用的主题分析方法包括Latent Semantic Analysis (LSA) 、 Probabilitistic Latent Semantic Analysis (PLSA)、Latent Dirichlet Allocation ( LDA)。这些方法在分类,聚类、检索、推荐等领域都有着很多的应用,并取得了比较好的效果。下面就LSA及PLSA方法进行简要介绍。

4.1 LSA简介

       LSA [6,7]模型认为特征之间存在某种潜在的关联结构,通过特征-对象矩阵进行统计计算,将高维空间映射到低纬的潜在语义结构上,构建出LSA空间模型,从而提取出潜在的语义结构,并用该结构表示特征和对象,消除了词汇之间的相关性影响,并降低了数据维度。增强了特征的鲁棒性

       LSA利用奇异值分解来进行计算,数学过程可以表述如下:

       对于 的矩阵A,其中m为特征数,n为样本数。令   ,经过奇异值分解,矩阵A可分解成3个矩阵的乘积:

其中,U、V是  和  的正交矩阵,分别称为矩阵A的奇异值对应的左、右奇异向量,  的对角矩阵,称为A的奇异标准形,其对角元素为矩阵A的奇异值。奇异值按照递减的排列构成对角矩阵 ,取 中前k个最大奇异值构成  的,取U和V最前面的k列构成  的U k  的V k,构建A的k-秩矩阵

                                                      (6)

其中,U k和V k 中的行向量分别作为特征向量和对象向量,k是降维后的维数。

4.2 plas介绍

       PLSA [8,9]模型是由Hofmann提出的用于文本检索的概率生成模型,与相比较于LSA,PLSA是基于概率模型的,并直接引入了潜在class变量 ,下面的用文本处理语言来描述该模型。

选定一篇文档的概率p(d),每篇文档以概率 属于一个主题,而给定一个主题,每一个词以概率 产生。将这个过程形成联合的概率模型表达式:

                                                (7)

                                            (8)

则:

                                       (9)

在PLSA实际的使用过程中,存在着overfit的风险,一般训练过程是通过EM算法,进行模型参数训练,获得p(z|d)、p(w|z)概率。

       PLSA和其相关的变形,在分类、聚类、检索等方面,特征相关性计算等方面,获得了广泛的应用,并取得了比较好的效果。

4.2 plas介绍

       PLSA [8,9]模型是由Hofmann提出的用于文本检索的概率生成模型,与相比较于LSA,PLSA是基于概率模型的,并直接引入了潜在class变量 z∈Z={Z 1…Z k },下面的用文本处理语言来描述该模型。

选定一篇文档的概率p(d),每篇文档以概率p(z|d)属于一个主题,而给定一个主题,每一个词以概率p(w|z) 产生。将这个过程形成联合的概率模型表达式:

在PLSA实际的使用过程中,存在着overfit的风险,一般训练过程是通过EM算法,进行模型参数训练,获得p(z|d)、p(w|z)概率。

       PLSA和其相关的变形,在分类、聚类、检索等方面,特征相关性计算等方面,获得了广泛的应用,并取得了比较好的效果。

.3 小结

       主题方法的引入,在一定程度上弥补了BOW的假设的独立性,在工业中,主题的方法也越来越多的应用到实际的机器学习中,包括在图像处理领域、传统的分类、聚类、检索等方面,都取得了比较好的效果。

总结

       相似度的计算在数据挖掘方面有着广泛的应用,根据不同的应用场景,各种方法各有其优劣特点,对于相似度效果的影响,除了方法本身之外,合理有效的特征的选择和使用也是至关重要的,同时,根据应用场景的不同,选择合理的方法,对于解决问题,有着重要的作用。

参考文献:  

1. G.S. Manku, A. Jain, A.D. Sarma. Detecting Near-Duplicates for Web Crawling. WWW2007, 2007

2. A. Das, M. Datar, A.Garg. Google News Personalization: Scalable Online Collaborative Filtering. WWW2007, 2007

3. http://en.wikipedia.org/wiki/MinHash

4. M. S. Charikar. Similarity estimation techniques from rounding algorithms. STOC’02. 2002

5. http://en.wikipedia.org/wiki/Locality-sensitive_hashing

6. K. Dave, S. Lawrence, and D. Pennock. Mining the peanut gallery: opinion extraction and semantic classification of product reviews. In Proceedings of the 22th International World Wide Web Conference, Budapest, Hungary, 2003

7. http://en.wikipedia.org/wiki/Latent_semantic_analysis

8. T. Hofmann. Probabilistic Latent Semantic Analysis. In Proceedings of the 15th Conference on Uncertainty in AI(1999).

9. Y. M kim, J. F. Pressiot M. R.Amini etc. An Extension of PLSA for Document Clustering. CIKM’08

by chenqingxuan

相关 [相似 计算 方法] 推荐:

相似度计算常用方法综述

- - 搜索研发部官方博客
       相似度计算用于衡量对象之间的相似程度,在数据挖掘、自然语言处理中是一个基础性计算. 其中的关键技术主要是两个部分,对象的特征表示,特征集合之间的相似关系. 在信息检索、网页判重、推荐系统等,都涉及到对象之间或者对象和对象集合的相似性的计算. 而针对不同的应用场景,受限于数据规模、时空开销等的限制,相似度计算方法的选择又会有所区别和不同.

Mahout中相似度计算方法介绍

- -
(转自: http://www.cnblogs.com/dlts26/archive/2012/06/20/2555772.html). 在现实中广泛使用的推荐系统一般都是基于协同过滤算法的,这类算法通常都需要计算用户与用户或者项目与项目之间的相似度,对于数据量以及数据类型不 同的数据源,需要不同的相似度计算方法来提高推荐性能,在mahout提供了大量用于计算相似度的组件,这些组件分别实现了不同的相似度计算方法.

URL相似度计算的思考

- - IT技术博客大学习
在做一些web相关的工作的时候,我们往往可能需要做一些对url的处理,其中包括对相似的url的识别和处理. 这就需要计算两个url的相似度. 那么怎么进行url相似度的计算的. 我首先想到的是把一个url看作是一个字符串,这样就简化成两个字符串相似度的计算. 字符串相似度计算有很多已经比较成熟的算法,比如“ 编辑距离算法”,该算法描述了两个字符串之间转换需要的最小的编辑次数;还有一些其他的比如“ 最长公共字串”等方法.

如何计算两个文档的相似度(一)

- - 我爱自然语言处理
前几天,我发布了一个和在线教育相关的网站: 课程图谱,这个网站的目的通过对公开课的导航、推荐和点评等功能方便大家找到感兴趣的公开课,特别是目前最火的Coursera,Udacity等公开课平台上的课程. 在发布之前,遇到的一个问题是如何找到两个相关的公开课,最早的计划是通过用户对课程的关注和用户对用户的关注来做推荐,譬如“你关注的朋友也关注这些课程”,但是问题是网站发布之前,我还没有积累用户关注的数据.

如何计算两个文档的相似度(三)

- - 我爱自然语言处理
上一节我们用了一个简单的例子过了一遍 gensim的用法,这一节我们将用 课程图谱的实际数据来做一些验证和改进,同时会用到 NLTK来对课程的英文数据做预处理. 为了方便大家一起来做验证,这里准备了一份Coursera的课程数据,可以在这里下载: coursera_corpus,总共379个课程,每行包括3部分内容:课程名\t课程简介\t课程详情, 已经清除了其中的html tag, 下面所示的例子仅仅是其中的课程名:.

海量数据相似度计算之simhash短文本查找

- - ITeye博客
在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力. 但是随着业务的增长 simhash的数据也会暴增,如果一天100w,10天就1000w了. 我们如果插入一条数据就要去比较1000w次的simhash,计算量还是蛮大,普通PC 比较1000w次海明距离需要 300ms ,和5000w数据比较需要1.8 s.

如何计算两个文档的相似度(二)

- - 我爱自然语言处理
上一节我们介绍了一些背景知识以及 gensim , 相信很多同学已经尝试过了. 这一节将从gensim最基本的安装讲起,然后举一个非常简单的例子用以说明如何使用gensim,下一节再介绍其在 课程图谱上的应用. 二、gensim的安装和使用. gensim依赖 NumPy和 SciPy这两大Python科学计算工具包,一种简单的安装方法是pip install,但是国内因为网络的缘故常常失败.

海量数据相似度计算之simhash和海明距离

- - CSDN博客架构设计推荐文章
通过  采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析. 分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法. 常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等. 这些算法对于待比较的文本数据不多时还比较好用,如果我们的爬虫每天采集的数据以千万计算,我们如何对于这些海量千万级的数据进行高效的合并去重.

文本相似度计算-google的simHash汉明距离

- - 行业应用 - ITeye博客
       针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model). 使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等. 这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理.