5.词项相似度分析

5.词项相似度分析

将从分析词项相似度入手,或者更准确的说,将从分析单独的单词标识相似度入手。虽然词项相似度分析没有在实际应用中大量使用,但是仍可以作为理解文本相似度分析的一个很好的出发点。当然,一些应用程序和用例(如自动填充程序、拼写检查和文本校正器)也会使用词项相似度分析中的部分技术来纠正拼写错误的词项。在这里,将选取一些单词并计算它们之间的相似度,然后应用不同的单词标识方法了距离度量进行相似度分析。将使用如下单词标识方法:

  • 字符向量化。
  • 字符(Bag of Character)袋向量化。

字符向量化是非常简单的过程,它将词项的每个字符映射到唯一的对应数字。可以使用以下代码来实现:

import numpy as np
from scipy.stats import itemfreq
 
def vectorize_terms(terms):
    terms = [term.lower() for term in terms]
    terms = [np.array(list(term)) for term in terms]
    terms = [np.array([ord(char) for char in term])
                for term in terms]
    return terms

该函数输入一列单词或词项,并返回相应的字符向量。字符袋向量化与词袋模型非常类似,区别是在这里会计算单词中每个字符的频率。字符袋向量化过程中不考虑字符序列或单词序列。以下函数可以帮助我们完成上述过程:

from scipy.stats import itemfreq
 
def boc_term_vectors(word_list):
    word_list = [word.lower() for word in word_list]
    unique_chars = np.unique(
                        np.hstack([list(word)
                        for word in word_list]))
    word_list_term_counts = [{char: count for char, count in itemfreq(list(word))}
                             for word in word_list]
     
    boc_vectors = [np.array([int(word_term_counts.get(char, 0))
                            for char in unique_chars])
                   for word_term_counts in word_list_term_counts]
    return list(unique_chars), boc_vectors

在这个函数中,输入的单词或词项,然后从所有单词中提取出特殊字符。与词袋模型类似,这就是特征列表,不同的是,在词袋模型中特殊词(而不是字符)才是特征。有了 unique_chars 的这个列表之后,就可以得到所有单词中每个字符的计数,并构建字符袋向量。

可以在下面的代码段中看到前述函数的应用。将使用四个示例词项,并计算它们之间的相似度:

root = 'Believe'
term1 = 'beleive'
term2 = 'bargain'
term3 = 'Elephant'   
 
terms = [root, term1, term2, term3]
 
vec_root, vec_term1, vec_term2, vec_term3 = vectorize_terms(terms)
print ('''
root: {}
term1: {}
term2: {}
term3: {}
'''.format(vec_root, vec_term1, vec_term2, vec_term3))

结果:

root: [ 98 101 108 105 101 118 101]
term1: [ 98 101 108 101 105 118 101]
term2: [ 98  97 114 103  97 105 110]
term3: [101 108 101 112 104  97 110 116]
features, (boc_root, boc_term1, boc_term2, boc_term3) = boc_term_vectors(terms)
print ('Features:', features)
print ('''
root: {}
term1: {}
term2: {}
term3: {}
'''.format(boc_root, boc_term1, boc_term2, boc_term3))

结果:

Features: ['a''b''e''g''h''i''l''n''p''r''t''v']
 
root: [0 1 3 0 0 1 1 0 0 0 0 1]
term1: [0 1 3 0 0 1 1 0 0 0 0 1]
term2: [2 1 0 1 0 1 0 1 0 1 0 0]
term3: [1 0 2 0 1 0 1 1 1 0 1 0]

可以看到如何轻松的将文本转换为数字向量表示形式。现在,要使用几个距离度量来计算根词和前面代码段中其他三个词之间的相似度。有很多距离指标可以用来计算和度量相似度。将介绍以下五个度量:

  • 汉明距离(Hamming distance)。
  • 曼哈顿距离(Manhattan distance)。
  • 欧几里距离(Euclidean distance)。
  • 莱文斯坦编辑距离(Levenshtein edit distance)。
  • 余弦距离(Cosin额 distance)和相似度。

下面将介绍每个距离度量的概念,并使用 numpy 数组来实现必要的计算和数学公式。之后,通过计算示例词项的相似度来具体介绍每个距离度量概念。首先,设置一些必要的变量以存储根词项,其他词项以及它们的向量化表示,如下代码所示:

# build the term vectors here   
root_term = root
root_vector = vec_root
root_boc_vector = boc_root
 
terms = [term1, term2, term3]
vector_terms = [vec_term1, vec_term2, vec_term3]
boc_vector_terms = [boc_term1, boc_term2, boc_term3]

现在,以及做好了计算相似度度量的准备,将使用词项及其向量表示来测量相似度。

汉明距离

汉明距离在信息和通信领域官方使用,它是非常流行的距离度量方法。汉明距离是两个长度相等的字符之间的测量距离。它的正式定义是两个长度相等的字符串之间互异字符或符号的位置的数量。考虑长度为 n 的两个词项 u 和 v,汉明距离的数学表达式为:

可以通过将不匹配的数目除以词项的总数来获得归一化的汉明距离,如下所示:

其中,n 表示词项的长度。

以下函数可以计算两个词项之间的汉明距离,还可以计算归一化距离:

def hamming_distance(u, v, norm=False):
    if u.shape != v.shape:
        raise ValueError('The vectors must have equal lengths.')
    return (u != v).sum() if not norm else (u != v).mean()

现在,使用以下代码来衡量词根项和其他词项之间的汉明距离:

# HAMMING DISTANCE DEMO
for term, vector_term in zip(terms, vector_terms):
    print ('Hamming distance between root: {} and term: {} is {}'.format(root_term,
                                                                term,
                                                                hamming_distance(root_vector, vector_term, norm=False)))

结果:

Hamming distance between root: Believe and term: beleive is 2
Hamming distance between root: Believe and term: bargain is 6
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-5-be6181236c26> in <module>()
      3     print ('Hamming distance between root: {} and term: {} is {}'.format(root_term,
      4                                                                 term,
----5                                                                 hamming_distance(root_vector, vector_term, norm=False)))
      6
      7
 
<ipython-input-1-2034efa805fain hamming_distance(u, v, norm)
      1 def hamming_distance(u, v, norm=False):
      2     if u.shape != v.shape:
----3         raise ValueError('The vectors must have equal lengths.')
      4     return (u != v).sum() if not norm else (u != v).mean()
 
ValueError: The vectors must have equal lengths.
for term, vector_term in zip(terms, vector_terms):
    print ('Normalized Hamming distance between root: {} and term: {} is {}'.format(root_term,
                                                                term,
                                                                round(hamming_distance(root_vector, vector_term, norm=True), 2)))
Normalized Hamming distance between root: Believe and term: beleive is 0.29
Normalized Hamming distance between root: Believe and term: bargain is 0.86
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-6-2474b1c55a95in <module>()
      2     print ('Normalized Hamming distance between root: {} and term: {} is {}'.format(root_term,
      3                                                                 term,
----4                                                                 round(hamming_distance(root_vector, vector_term, norm=True), 2)))
      5
      6
 
<ipython-input-1-2034efa805fain hamming_distance(u, v, norm)
      1 def hamming_distance(u, v, norm=False):
      2     if u.shape != v.shape:
----3         raise ValueError('The vectors must have equal lengths.')
      4     return (u != v).sum() if not norm else (u != v).mean()
 
ValueError: The vectors must have equal lengths.

从前面的输出可以看出,在忽略大小写的情况下,'Believe' 和 'beleive' 最为相似,其汉明距离为 2 或 0.29 (归一化汉明距离),与 'bargain' 一词的汉明距离值为 6 或 0.86 (这里,数值越小,词项越相似)。词项 'Elephant' 则引发了程序异常,因为该词的长度是 8,而词根 'Believe' 的长度为 7,所以不能计算汉明距离,因为汉明的假设前提是距离长度相等。

曼哈顿距离

曼哈顿距离度量在概念上类似于汉明距离,区别是曼哈顿距离计算两个字符串的每个位置上对应字符之间的差值,而不是计算不匹配字符的数量。曼哈顿距离也称为城市街区距离、L1范数、计程车度量,正式定义是基于严格水平或垂直路径的网格中两个点之间的距离,而非通常计算的欧几里得对角距离,其数学表示为:

其中,u 和 v 是长度为 n 的两个词项。与汉明距离相同,这里的假设前提是两个词项的长度相同。还可以通过绝对差的和除以词项长度来计算曼哈顿归一化距离。表达式如下:

其中,n 是词项 u 和 v 的长度,以下函数有助于计算曼哈顿距离,也可以计算曼哈顿归一化距离:

def manhattan_distance(u, v, norm=False):
    if u.shape != v.shape:
        raise ValueError('The vectors must have equal lengths.')
    return abs(u - v).sum() if not norm else abs(u - v).mean()

现在,使用上述函数计算根词项和其他词项之间的曼哈顿距离,如下代码所示:

# MANHATTAN DISTANCE DEMO
for term, vector_term in zip(terms, vector_terms):
    print ('Manhattan distance between root: {} and term: {} is {}'.format(root_term,
                                                                term,
                                                                manhattan_distance(root_vector, vector_term, norm=False)))

结果:

Manhattan distance between root: Believe and term: beleive is 8
Manhattan distance between root: Believe and term: bargain is 38
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-14-b8740bf6df30> in <module>()
      3     print ('Manhattan distance between root: {} and term: {} is {}'.format(root_term,
      4                                                                 term,
----5                                                                 manhattan_distance(root_vector, vector_term, norm=False)))
      6
      7
 
<ipython-input-11-f76af5f725e0> in manhattan_distance(u, v, norm)
      1 def manhattan_distance(u, v, norm=False):
      2     if u.shape != v.shape:
----3         raise ValueError('The vectors must have equal lengths.')
      4     return abs(u - v).sum() if not norm else abs(u - v).mean()
 
ValueError: The vectors must have equal lengths.
for term, vector_term in zip(terms, vector_terms):
    print ('Normalized Manhattan distance between root: {} and term: {} is {}'.format(root_term,
                                                                term,
                                                                round(manhattan_distance(root_vector, vector_term, norm=True),2)))

结果:

Normalized Manhattan distance between root: Believe and term: beleive is 1.14
Normalized Manhattan distance between root: Believe and term: bargain is 5.43
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-15-d5f6b06389a1> in <module>()
      2     print ('Normalized Manhattan distance between root: {} and term: {} is {}'.format(root_term,
      3                                                                 term,
----4                                                                 round(manhattan_distance(root_vector, vector_term, norm=True),2)))
      5
      6
 
<ipython-input-11-f76af5f725e0> in manhattan_distance(u, v, norm)
      1 def manhattan_distance(u, v, norm=False):
      2     if u.shape != v.shape:
----3         raise ValueError('The vectors must have equal lengths.')
      4     return abs(u - v).sum() if not norm else abs(u - v).mean()
 
ValueError: The vectors must have equal lengths.

从这些结果可以看出,正如预期的那样,在忽略大小写的情况下,'Believe' 和 ‘beleive’ 之间的距离相似度最高,距离度量的分为 8 或 1.14,与 'bargain' 一词的距离度量得分为 38 或 5.43(这里得分越小,词约相似)。词项 'Elephant' 则在运行中产生错误,因为它与根词项的长度不同,就像之前在计算汉明距离时一样。

欧几里得距离

欧几里得距离也称为欧几里得范数,L2 范数或 L2 距离,它的正式定义是两点之间最短的直线距离。数学上可以表示为:

其中,u 和 v 两点是场景中的向量化文本词项,每个长度都为 n。以下函数有助于计算两个词项之间的欧几里得距离:

def euclidean_distance(u,v):
    if u.shape != v.shape:
        raise ValueError('The vectors must have equal lengths.')
    distance = np.sqrt(np.sum(np.square(u - v)))
    return distance

现在,使用上述函数计算词项之间的欧几里得距离,如下代码所示:

# EUCLIDEAN DISTANCE DEMO
for term, vector_term in zip(terms, vector_terms):
    print ('Euclidean distance between root: {} and term: {} is {}'.format(root_term,
                                                                term,
                                                                round(euclidean_distance(root_vector, vector_term),2)))

结果:

Euclidean distance between root: Believe and term: beleive is 5.66
Euclidean distance between root: Believe and term: bargain is 17.94
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-18-ac390028bdbb> in <module>()
      3     print ('Euclidean distance between root: {} and term: {} is {}'.format(root_term,
      4                                                                 term,
----5                                                                 round(euclidean_distance(root_vector, vector_term),2)))
      6
 
<ipython-input-17-654771f3cf5din euclidean_distance(u, v)
      1 def euclidean_distance(u,v):
      2     if u.shape != v.shape:
----3         raise ValueError('The vectors must have equal lengths.')
      4     distance = np.sqrt(np.sum(np.square(u - v)))
      5     return distance
 
ValueError: The vectors must have equal lengths.

从上述输出可以看出,'Believe' 和 ‘beleive’ 这两个词最相似,得分为 5.66,‘bargain’ 得分为 17.94,‘Elephant’ 则给出了一个 ValueError,因为这里也是测量字符串相等时的长度。

莱文斯坦编辑距离

莱文斯坦编辑距离通常也称为莱文斯坦距离,属于基于编辑距离的度量,它用于根据字符差异来测量两个字符串之间的距离——类似于汉明距离的度量概念。两个词项之间的莱文斯坦编辑距离可以定义为通过添加、删除或替换将一个词项转变成另一个词项所需的最少编辑次数。这些替代是基于字符的替代,其中单次操作可以编辑单个字符。此外,如前所述,这两个词项的长度在这里不必相对。在数学上,可以将两个词项之间的莱文斯坦编辑距离表示为 ldn,v(|u|,|v|),其中,u 和 v 是词项,而 |u| 和 |v| 使其长度。该距离可以用于下公式表示:

其中,i 和 j 是词项 u 和 v 的索引。上面最小项的第三个方程包含一个由 Cui≠vi 表示的成本函数,它具有如下限制条件:

上式为指示函数,它说明了匹配两个词项的对应字符所需的成本(该方程代表了匹配操作或不匹配操作)。上一个最小值中的第一个方程表示删除操作,第二个方程表示插入操作。这样,函数 ldn,v(i,j) 就涵盖了前面提到的插入、删除和添加所有操作,它表示在词项 u 的第 i 个字母到词项 v 的第 j 个字母之间的莱文斯坦编辑距离。对于莱文斯坦编辑距离还有几个有趣的边界条件:

  • 两个词项之间编辑距离的最小值是两个词项长度的差值。
  • 两个词项之间编辑距离的最大值可以是较大词项的长度。
  • 如果两个词项完全一样,则编辑距离为零。
  • 当且仅当两个词项具有相同的长度时,两个词项之间莱文斯坦编辑距离的上线为汉明距离。
  • 莱文斯坦编辑距离作为距离度量也满足三角不等式特性。

有很多种计算莱文斯坦编辑距离的方法,在这里,以两个词项为例介绍莱文斯坦编辑距离计算。考虑根词项 'believe' 和另一个词项 'beleive'(在计算中忽略大小写)。两者的编辑距离应为 2,因为需要进行以下两个操作完成 ‘beleive’ 到词项的变换:

  • 'beleive' → 'beliive'(将 e 替换为 i)。
  • ‘beleive’ → 'believe'(替换为 e)。

为了实现这一点,需要构建一个矩阵,它可以通过比较第一词项的每个字符和第二词项的每个字符,计算两个词项所有字符之间的莱文斯坦距离。为了便于计算,遵循一种动态规划方法,根据最终计算结果的到两个此项之间的编辑距离。对于给定的两个词项,这里的算法应生成的莱文斯坦编辑距离如表:

  b e l i e v e
b 0 1 2 3 4 5 6
e 1 0 1 2 3 4 5
l 2 1 0 1 2 3 4
e 3 2 1 1 1 2 3
i 4 3 2 1 2 2 3
v 5 4 3 2 2 2 3
e 6 5 4 3 2 3 2

由表可见,对词项中的没对字符都计算编辑距离,如前所述,图中突出显示的最终编辑距离值即为两个词项之间的实际编辑距离。该算法也称为瓦克纳-费舍尔(Wagner-Fischer)算法,如果想了解更多细节,可以参考瓦格纳(R. Wagner)和费舍尔(M. Fischer)的 “字符串到字符校正问题”(The String-to-String Correction Problem)一文。

上述算法使用的是 O(mn) 空间,因为它们虽然包含整个距离矩阵,但是只需存储前一行和当前的距离行便足以获得最终结果。将在代码中执行相同的操作,同时也会将结果存储在一个矩阵中,以便于在最后将其显示出来。以下函数可以实现莱文斯坦编辑距离计算:

import copy
import pandas as pd
import numpy as np
 
def levenshtein_edit_distance(u, v):
    # convert to lower case
    = u.lower()
    = v.lower()
    # base cases
    if == v: return 0,0
    elif len(u) == 0return len(v),0
    elif len(v) == 0return len(u),0
    # initialize edit distance matrix
    edit_matrix = []
    # initialize two distance matrices
    du = [0* (len(v) + 1)
    dv = [0* (len(v) + 1)
    # du: the previous row of edit distances
    for in range(len(du)):
    
        du[i] = i
    # dv : the current row of edit distances   
    for in range(len(u)):
    
        dv[0= + 1
        # compute cost as per algorithm
    
        for in range(len(v)):
        
            cost = 0 if u[i] == v[j] else 1
            dv[j + 1= min(dv[j] + 1, du[j + 1+ 1, du[j] + cost)
        # assign dv to du for next iteration
    
        for in range(len(du)):
        
            du[j] = dv[j]
        # copy dv to the edit matrix
    
        edit_matrix.append(copy.copy(dv))
    # compute the final edit distance and edit matrix   
    distance = dv[len(v)]
    edit_matrix = np.array(edit_matrix)
    edit_matrix = edit_matrix.T
    edit_matrix = edit_matrix[1:,]
    edit_matrix = pd.DataFrame(data=edit_matrix,
                               index=list(v),
                               columns=list(u))
    return distance, edit_matrix

该函数返回两个词项 u 和 v 之间最终的莱文斯坦编辑距离以及完整的编辑矩阵,其中 u 和 v 是我们的输入。请记住,需要以原始字符串格式,而不是以它们的向量表示来传递词项。此外,在这里不考虑字符串的大小写,并将所有字符全部转换为小写。

以下代码段使用上述函数来计算示例词项之间的莱文斯坦编辑距离:

# LEVENSHTEIN EDIT DISTANCE DEMO
for term in terms:
    edit_d, edit_m = levenshtein_edit_distance(root_term, term)
    print ('Computing distance between root: {} and term: {}'.format(root_term,
                                                                    term))
    print ('Levenshtein edit distance is {}'.format(edit_d))
    print ('The complete edit distance matrix is depicted below')
    print (edit_m)
    print ('-'*30)

结果:

Computing distance between root: Believe and term: Believe
Levenshtein edit distance is 0
The complete edit distance matrix is depicted below
0
------------------------------
Computing distance between root: Believe and term: beleive
Levenshtein edit distance is 2
The complete edit distance matrix is depicted below
   b  e  l  i  e  v  e
b  0  1  2  3  4  5  6
e  1  0  1  2  3  4  5
l  2  1  0  1  2  3  4
e  3  2  1  1  1  2  3
i  4  3  2  1  2  2  3
v  5  4  3  2  2  2  3
e  6  5  4  3  2  3  2
------------------------------
Computing distance between root: Believe and term: bargain
Levenshtein edit distance is 6
The complete edit distance matrix is depicted below
   b  e  l  i  e  v  e
b  0  1  2  3  4  5  6
a  1  1  2  3  4  5  6
r  2  2  2  3  4  5  6
g  3  3  3  3  4  5  6
a  4  4  4  4  4  5  6
i  5  5  5  4  5  5  6
n  6  6  6  5  5  6  6
------------------------------
Computing distance between root: Believe and term: Elephant
Levenshtein edit distance is 7
The complete edit distance matrix is depicted below
   b  e  l  i  e  v  e
e  1  1  2  3  4  5  6
l  2  2  1  2  3  4  5
e  3  2  2  2  2  3  4
p  4  3  3  3  3  3  4
h  5  4  4  4  4  4  4
a  6  5  5  5  5  5  5
n  7  6  6  6  6  6  6
t  8  7  7  7  7  7  7
------------------------------

从上述输出可以看出,'Believe' 和 'beleive' 彼此很接近,编辑距离为 2,‘Believe’ 与 ‘bargain’ 'Elephant' 之间的距离为 6,表示总共需要 6 个编辑距离。通过编辑距离矩阵可以更详细地了解算法如何通过每次迭代计算距离。

余弦距离和相似度

余弦距离是一个可以从余弦相似推导出的度量,反之亦然。考虑两个词项,它们以向量化形式表示,余弦相似度给出了当它们在内积空间中为非零正量时,它们之间角度的余弦值。因此具有相似方向的词项向量将拥有更接近于 1 (cos0o) 的相似度得分,表示向量在相同方面上彼此非常接近(它们之间的夹角接近零度)。相似度得分接近 0 (cos90o) 则表示两个词项向量的夹角接近直角,它们是无关词项。相似度得分接近 -1 (cos180o) 表示彼此是完全相反的词项。如图,其中 u 和 v 是在向量空间中的词项向量。

可以从向量的位置看出它们的关系,这些图可以更清楚地显示出向量彼此靠近还是彼此远离的,它们之间夹角的余弦值给出了余弦相似度度量。可以将余弦相似度正式定义为两个词项向量 u 和 v 的点积除以它们的 L2 范数的乘积。在数学上,可以使用如下表达式表示两个向量之间的点积:

其中 θ 是 u 和 v 之间的角度,|| u || 表示向量 u 的 L2 范数,|| v || 表示向量 v 的 L2 范数,可以从上面的公式导出余弦相似度的表达式:

其中 cs(u,v) 是 u 和 v 之间的余弦相似度得分,这里 ui 和 vi 是两个向量的各类特征或组件,这些特征或组件的总数为 n。在示例中,将使用字符包向量化来构建这些词项向量,n 表示待分析的所有词项的特殊字符的数量。在这里需要注意一件很重要的事情,那就是通常余弦相似度得分的范围从 -1 到 +1,但是如果使用字符袋(基于字符频率)或词袋(基于词频),那么分数的范围将会是从 0 到 1,因为词频向量永远不会是负的,所以两个向量之间的角度不能超过 90o。可用如下公式来表示 余弦距离:

其中 cs(u,v) 表示词项向量 u 和 v 之间的余弦距离。以下函数给出了基于上述公式实现余弦距离的计算过程:

def cosine_distance(u, v):
    distance = 1.0 - (np.dot(u, v) /
                        (np.sqrt(sum(np.square(u))) * np.sqrt(sum(np.square(v))))
                     )
    return distance

接下来,将使用之前创建的字符袋表示来测试示例词项之间的相似度,如下代码段所示:

# COSINE DISTANCESIMILARITY DEMO
for term, boc_term in zip(terms, boc_vector_terms):
    print ('Analyzing similarity between root: {} and term: {}'.format(root_term,
                                                                      term))
    distance = round(cosine_distance(root_boc_vector, boc_term),2)
    similarity = 1 - distance                                                          
    print ('Cosine distance  is {}'.format(distance))
    print ('Cosine similarity  is {}'.format(similarity))
    print ('-'*40)

结果:

Analyzing similarity between root: Believe and term: beleive
Cosine distance  is -0.0
Cosine similarity  is 1.0
----------------------------------------
Analyzing similarity between root: Believe and term: bargain
Cosine distance  is 0.82
Cosine similarity  is 0.18000000000000005
----------------------------------------
Analyzing similarity between root: Believe and term: Elephant
Cosine distance  is 0.39
Cosine similarity  is 0.61
----------------------------------------

这些向量表示不考虑字符的顺序,因此 "Believe" 一词和 "beleive" 的相似度为 1.0 或 100% 完全相似,因为它们有着具有相同频率的相同字符。可以看出将其与 WordNet 这样的语义字典组合使用的好处,即可以在用户键入拼写错误的单词时,通过测量单词之间的相似度来提供语义上和语法上正确的单词,从而提供正确的拼写建议。在这里,可以尝试使用不同的特征,如同时提取两个字符并计算其频率来构建词项向量,而非示例中所示的使用单个字符的频率构建向量。这样就对词语中的部分字符顺序加入了考量。当测量大文件或长句子之间的相似度时,这种距离度量十分有效。

原文地址:https://www.cnblogs.com/dalton/p/11354018.html