文本相似性算法

《文本相似性算法》由会员分享，可在线阅读，更多相关《文本相似性算法（8页珍藏版）》请在金锄头文库上搜索。

1、文本相似性算法在目前这个信息过载的时代，文本的相似度计算应用前景还是比较广泛的， 它可以让人们过滤掉很多相似的新闻，比如在搜索引擎上，相似度太高的页面， 只需要展示一个就行了。考试的时候，可以用这个来防作弊，同样的，论文的相 似度检查也是一个检查论文是否抄袭的一个重要办法。本次分享主要讲三个较为常用的文本相似性算法：1基于空间向量的余弦算法2. 编辑距离算法（Levenshtein距离）3. JaccardSimilarity算法及联合哈希函数使用方法1 基于空间向量的余弦算法向量空间模型的基本思想是把文档简化为以特征项（关键词）的权重为分量 的N维向量表示。这个模型假设词与词间不相关，用向量

2、来表示文本，从而简化 了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备 了可计算性。1.1 算法步骤数据预处理一文本特征项选择一加权一生成向量空间模型后计算余弦。1.2 数据预处理预处理主要是进行中文分词和去停用词。按照停用词表中的词语将语料中对 文本内容识别意义不大但出现频率很高的词、符号、标点及乱码等去掉。如，这， 的，和，会，为”等词几乎出现在任何一篇中文文本中，但是它们对这个文本所 表达的意思几乎没有任何贡献。使用停用词列表来剔除停用词的过程很简单，就 是一个查询过程：对每一个词条，看其是否位于停用词列表中，如果是则将其从 词条串中删除。读人-个 p.j卜一梓用同

3、埶l:中文文本分词流程1.3文本特征项选择及加权过滤掉常用副词、助词等频度高的词之后，根据剩下词的频度确定若干关键 词词频。频度计算参照TF公式。加权是针对每个关键词对文本特征的体现效果大小不同而设置的机制，权值 计算参照IDF公式。这里需要用到TF-IDF算法。词频(TF)-某个词在文章中的出现次数文章的总词数逆文档频率(IDF) = log(语料库的文档总数包含该词的文档数+11.4生成向量空间模型及计算余弦假设文本D1的特征项为a, b, c, d,权值分别为30, 20, 20, 10,即D1(30, 20, 20, 10)。类目C1的特征项为a, c, d, e,权值分别为40, 3

4、0, 20, 10,即C1(40, 30, 20, 10)。但是，这里D1和C1的特征项有不一致的地方, 因此还需对D1和C1的特征项进行对等。即D1的向量表示为：D1(30, 20, 20, 10, 0), C1 的向量表示为：C1(40, 0, 30, 20, 10)两个文本D1和C1之间的内容相关度Sim (D1, C1)常用向量之间夹角的余 弦值表示，公式为：松A汁血时将D1和C1的向量带人以上公式计算即可得到：Sim(D1, C1)=0.86。2编辑距离算法(Levenshtein距离)编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操 作次数。许可的编辑操作包括将一

5、个字符替换成另一个字符，插入一个字符，删 除一个字符。编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Dista nee。2.1实现过程为了更加直观的描述该算法，先以一个简单的例子加以说明。现有两个字符 串abe和abe，将字符串想象成以下的结构：abcabCabe0123a1A处b2e3它的值取决于：左边的1、上边的1、左上角的0。按照 Levenshtein distanee 的意思：上面的值和左面的值都要求加1,这样得到1+1=2。A处由于是两个a相同, 左上角的值加0。这样得到0+0=0。这是后有三个值，左边的计算后为2, 上边 的计算后为2

6、,左上角的计算为0,所以A处取他们里面最小的0。abcabcabe0123a10b2E处e3在B处会同样得到三个值，左边计算后为3,上边计算后为1,在B处由于 对应的字符为a、b,不相等，所以左上角应该在当前值的基础上加1,这样得到 1+1=2，在（3,1,2）中选出最小的为B处的值。abcab匚abe0123EL10b21e3c处C处计算后：上面的值为2,左边的值为4,左上角的：a和e不相同，所以 加1,即2+1，左上角的为3。在（2,4,3）中取最小的为C处的值。ab匚0123a1A处0D处1G处2b2B处1E处DH处1e3C处2F处1I处1I处:表示abc和abe有1个需要编辑的操作。这

7、个是需要计算出来的。2.2实现原理该算法使用了动态规划的算法策略，该问题具备最优子结构，最小编辑距离i，j 0x 二 yijx丰yij包含子最小编辑距离，有下列公式:0d = min(d +1, d +1, d )i, j i-1, j i, j-1i-1, j-1min( d+1, d +1, d +1)li-1,刀i, j-1i-1, j-1其中di-1,j+1代表字符串s2插入一个字母，di,j-1+1代表字符串si删除 一个字母，然后当xi=yj时，不需要代价，所以和上一步di-1,j-1代价相同，否 则+1，接着di,j是以上三者中最小的一项。2.3计算相似度先取两个字符串长度的最大

8、值MaxLen，用以下公式得到相似度:.需要的操作数sim = 1-MaxLen例如abc和abe需要一个操作，长度为3，所以相似度为sim=l-l/3=0.666。3 JaccardSimilarity算法及联合哈希函数使用方法JaccardSimilarity算法简单，容易实现，实际上就是两个集合的交集除以两 个集合的并集，所得的就是两个集合的相似度，直观的看就是下面这个图。数学表达式是：Sim=|S n T|/U T|基本的计算方法就是如此，而两个集合分别表示的是两个文本，集合中的兀 素实际上就是文本中出现的词语，我们需要做的就是把两个文本中的词语统计出 来，然后按照上面的公式算一下就行

9、了，其实很简单。3.1统计文本中的词语这里计算相似度，所采用的词语统计为比较简单的k-shingle算法，k是一 个变量，表示提取文本中的k个字符，这个k可以自己定义。k-shingle算法： 将长的文本分割成小的、连续的字符串集合，如连续k个字符。可以做些预处理, 去掉空字符，或将连续空字符替换为一个空字符。该算法就是从头扫描文本，然后依次把k个字符保存起来，假如有个文本内 容是abcdefg, k设为2,那得到的词语就是ab,bc,cd,de,ef,fg。得到这些词汇以后, 然后统计每个词汇的数量，最后用上面的JaccardSimilarity算法来计算相似度。3.2优化上述方法其实可以完

10、成文本比较了，但是如果是大量文本或者单个文本内容 较大，比较的时候势必占用了大量的存储空间，因为一个词汇表的存储空间大于 文本本身的存储空间，这样，我们需要进行一下优化。3.3使用特征矩阵来描述相似性文本相似度的特征矩阵：一个特征矩阵的任何一行是全局所有元素中的一个元素，任何一列是一个集 合。若全局第i个 元素出现在第j个集合里面，元素(i, j)为1,否则 为0。现有world和could两个文本，设k为2通过k-shingle拆分以后，分别变 成了 wo,or,rl,ld和co,ou,ul,ld那么他们的特征矩阵就是：词汇衆集合 1 (world)集 制 could)W010or10t10

11、Id11CO01OU01ul01通过特征矩阵，我们很容易看出来，两个文本的相似性就是他们公共的元素 除以所有的元素，也就是 1/7。在这个矩阵中，集合列上面不是 0 就是 1，其实 我们可以把特征矩阵稍微修改一下，列上面存储的是该集合中词语出现的个数， 可靠性更高一些。至此，我们已经把一个简单的词汇表集合转换成上面的矩阵了，由于第一列 的词汇表实际上是一个顺序的数列，所以我们需要存储的实际上只有后面的每一 列的集合的数据了，而且也都是整数，这样存储空间就小多了。3.4继续优化，使用hash签名对于保存上述特征矩阵，如果还嫌太浪费空间了，那么可以继续优化，如果 能将每一列数据做成一个哈希签名，我

12、们只需要比较签名的相似度就能大概的知 道文本的相似度就好了，注意，这里用了大概，也就是说这种方法会丢失掉一部 分信息，对相似度的精确性是有影响的，如果在大量需要处理的数据面前，丢失 一部分精准度而提供处理速度是可以接受的。步骤：先找到一组自定义的哈希函数 H1,H2.Hn。1. 将每一行的第一个元素，就是词汇表 hash 后得到的数字，分别于自定的 哈希函数进行运算，得到一组新的数。2. 建立一个集合(S1,S2.Sn)与哈希函数(H1,H2.Hn)的新矩阵T,并将每个元素 初始值定义为无穷大。3. 对于任何一列的集合，如果T(Hi,Sj)为0,则什么都不做。4. 对于任何一列的集合，如果T(

13、Hi,Sj)不为0,则将T(Hi,Sj)和当前值比较，更 新为较小的值。还是上面那个矩阵,使用 hash 签名以后,我们得到一个新矩阵,我们使用 了两个哈希函数：H1= (x+1)%7, H2=(3x+1)%7得到下面矩阵:词汇表集(world)集 -2(could)H1 (x+1)%7H2 (3x+1)%7wo 01011or 11024rl 21030id 31143co 40156OU 50162ul 60105然后，建立一个集合组T与哈希函数组H的新矩阵。ROW集合 1 (world)集合 2(could)H100H2g接下来，按照上面的步骤来更新这个矩阵。1. 对于集合1，他对于H1来说，他存在的元素中，H1后最小的数是1，对 于H2来说，最小的是0。2. 对于集合2，他对于H1来说，他存在的元素中，H1后最小的数是0，对 于H2来说，最小的是2。所以，矩阵更新为：ROW集合1 (world)集合 2(could)H110H20通过这个矩阵来计算相似度，只有当他们某一列完全相同的时候，我们才认 为他们有交集，否则不认为他们有交集，所以根据上面这个矩阵，我们认为集合 1和集合2的相似度为0。这就是刚刚说的大概的含义，他不能精确的表示两个 文本的相似性，得到的只是一个近似值。