【Python】最近开肝MIT006，附上自己的理解，不定时更新 Lec02

Z时代
2024-01-10
分类：技术分享

Document Distance

文本相似度

它常用于搜索引擎中，MIT举的例子是Google，但为了更好的理解，这里以百度为例，思路其实差不都。
例如你有一天躺在床上刷抖音的时候，刷到了一篇鸡汤，幡然醒悟励志成为一名算法大师，于是你在百度上搜索‘如何从小白成为一个算法大佬’，那么百度会给你列出这些内容
【Python】最近开肝MIT006，附上自己的理解，不定时更新 Lec02
显然百度没有搜索到与这个文本相匹配的内容，但是它给了你许多类似的搜索，与‘如何从小白成为一个算法大佬’相似的文本，这就是Document Distance所做的，不过百度肯定不只用了这个算法。

对于Document Distance算法的理解

首先这个算法有几个默认的前提

单词组成的序列（类似于你可以搜索 how to become handsome,但你不能乱输 asjkhbfjkashbfjksadg这种东西）

由字母，数字，字符组成（A-Z 0-9）

现在我有两个文本
D1 = 'the dog'
D2 = 'the cat'
如何衡量这两个文本的相似度，如果将文本抽象成一个向量，那么向量的相似度有一个东西可以衡量----内积(inner product)
内积是一个标量，反应着两个向量的'相似度',两个向量越相似，内积越大。

那么如何将文本转换成向量呢？

这里偷个懒直接上截图
【Python】最近开肝MIT006，附上自己的理解，不定时更新 Lec02
D1和D2一共有3个单词，可以抽象成一个三维坐标，每个单词为一个坐标轴，这样D1和D2就表示了出来

如何表示内积？

需要用到一点微积分的知识，而积分在离散的计算机里则为求和运算

内积公式：a∙b=a∗b∗cos⁡θ（a向量乘以b向量在a向量上的投影）
D1向量中的'The'出现了一次，长度即为1
D2向量在D1向量上'The'的投影即为D2里出现'The'的次数也为1
两者相乘可以理解为'the'这个子向量的内积，两个文本的内积即为所有单词的内积之和（类似于微积分）

'dog'在D1为1，D2在D1上'dog'的投影为0，因为D2没有dog这个word
'cat'在D1为0，D2在D1上'cat'的投影为1
可以理解为D1 = 1∗the轴 + 1∗dog轴 + 0∗cat轴组成的向量

求出D1和D2的内积为：1∗1 + 1∗0 + 0∗1 = 1

但是光用内积可以衡量两个文本的相似度吗？

再举一个例子
D3 = this is the cat
D4 = that is the dog
那么D3和D4的内积为2，而D1和D2的内积为1，但其实它们都是50%的相似度，但因为文本长度不一样，所以内积不一样。
所以需要一个统一的衡量标准，用它们的内积除以它们的长度。
【Python】最近开肝MIT006，附上自己的理解，不定时更新 Lec02
有没有觉得很熟悉？这时打开我们小学一年级的课本，发现了一个笔记

没错其实这就是两个向量夹角的余弦值
当角度为0度时（cos⁡θ = 1），两个文本完全一样，当角度为90度时（cos⁡θ = 0）两个文本完全不一样，这样就统一了meansure。

所以这个算法的完整步骤应该是

将文本划分成一个个单词

找出每个单词在每个文本中的频率

通过内积公式求出相似度

附MIT python算法实现

import math
# math.acos(x) is the arccosine of x.
# math.sqrt(x) is the square root of x.
import string
import sys
##################################
# Operation 1: read a text file ##
##################################
def read_file(filename):
"""
Read the text file with the given filename;
return a list of the lines of text in the file.
"""
try:
f = open(filename, 'r')
return f.read()
except IOError:
print "Error opening or reading input file: ",filename
sys.exit()
#################################################
# Operation 2: split the text lines into words ##
#################################################
# global variables needed for fast parsing
# translation table maps upper case to lower case and punctuation to spaces
translation_table = string.maketrans(string.punctuation+string.uppercase,
" "*len(string.punctuation)+string.lowercase)
def get_words_from_line_list(text):
"""
Parse the given text into words.
Return list of all words found.
"""
text = text.translate(translation_table)
word_list = text.split()
return word_list
##############################################
# Operation 3: count frequency of each word ##
##############################################
def count_frequency(word_list):
"""
Return a dictionary mapping words to frequency.
"""
D = {}
for new_word in word_list:
if new_word in D:
D[new_word] = D[new_word]+1
else:
D[new_word] = 1
return D
#############################################
## compute word frequencies for input file ##
#############################################
def word_frequencies_for_file(filename):
"""
Return dictionary of (word,frequency) pairs for the given file.
"""
line_list = read_file(filename)
word_list = get_words_from_line_list(line_list)
freq_mapping = count_frequency(word_list)
print "File",filename,":",
print len(line_list),"lines,",
print len(word_list),"words,",
print len(freq_mapping),"distinct words"
return freq_mapping
def inner_product(D1,D2):
"""
Inner product between two vectors, where vectors
are represented as dictionaries of (word,freq) pairs.
Example: inner_product({"and":3,"of":2,"the":5},
{"and":4,"in":1,"of":1,"this":2}) = 14.0
"""
sum = 0.0
for key in D1:
if key in D2:
sum += D1[key] * D2[key]
return sum
def vector_angle(D1,D2):
"""
The input is a list of (word,freq) pairs, sorted alphabetically.
Return the angle between these two vectors.
"""
numerator = inner_product(D1,D2)
denominator = math.sqrt(inner_product(D1,D1)*inner_product(D2,D2))
return math.acos(numerator/denominator)
def main():
if len(sys.argv) != 3:
print "Usage: docdist8.py filename_1 filename_2"
else:
filename_1 = sys.argv[1]
filename_2 = sys.argv[2]
sorted_word_list_1 = word_frequencies_for_file(filename_1)
sorted_word_list_2 = word_frequencies_for_file(filename_2)
distance = vector_angle(sorted_word_list_1,sorted_word_list_2)
print "The distance between the documents is: %0.6f (radians)"%distance
if __name__ == "__main__":
import profileprofile.run("main()")