（一）余弦相似度、向量空间模型

1、相似度

• 相似度度量：计算个体间相似程度
• 相似度值越小，距离越大，相似度值越大，距离越小
• 最常用——余弦相似度
– 一个向量空间中两个向量夹角的余弦值作为衡量两个个体之间差异的大小

– 余弦值接近1，夹角趋于0，表明两个向量越相似

image image

2、例子

image

3、处理流程

• 得到了文本相似度计算的处理流程是:
– 找出两篇文章的关键词；
– 每篇文章各取出若干个关键词，合并成一个集合，计算每篇文章对于这个集合中的词的词频
– 生成两篇文章各自的词频向量；
– 计算两个向量的余弦相似度，值越大就表示越相似。

（二）TFIDF

1、词频——TF

• 假设：如果一个词很重要，应该会在文章中多次出现
• 词频——TF（Term Frequency）：一个词在文章中出现的次数
• 也不是绝对的！出现次数最多的是“的”“是”“在”，这类最常用的词，叫做停用词（stop words）
• 停用词对结果毫无帮助，必须过滤掉的词
• 过滤掉停用词后就一定能接近问题么？

• 进一步调整假设：如果某个词比较少见，但是它在这篇文章中多次出现，那么它很可能反映了这篇文章的特性，正是我们所需要的关键词

2、反文档频率——IDF

• 在词频的基础上，赋予每一个词的权重，进一步体现该词的重要性，
• 最常见的词（“的”、“是”、“在”）给予最小的权重
• 较常见的词（“国内”、“中国”、“报道”）给予较小的权重
• 较少见的词（“养殖”、“维基”）
• 将TF和IDF进行相乘，就得到了一个词的TF-IDF值，某个词对文章重要性越高，该值越大，于是排在前面的几个词，就是这篇文章的关键词。

3、计算步骤

image

4、相似文章

• 使用TF-IDF算法，找出两篇文章的关键词；
• 每篇文章各取出若干个关键词（比如20个），合并成一个集合，计算每篇文章对于这个集合中的词的词频（为了避免文章长度的差异，可以使用相对词频）；
• 生成两篇文章各自的词频向量；

• 计算两个向量的余弦相似度，值越大就表示越相似。

5、自动摘要

• 文章的信息都包含在句子中，有些句子包含的信息多，有些句子包含的信息少。"自动摘要"就是要找出那些包含信息最多的句子。
• 句子的信息量用"关键词"来衡量。如果包含的关键词越多，就说明这个句子越重要。
• 只要关键词之间的距离小于“门槛值”，它们就被认为处于同一个簇之中，如果两个关键词之间有5个以上的其他词，就可以把这两个关键词分在两个簇。

• 下一步，对于每个簇，都计算它的重要性分值。

image

• 例如：其中的簇一共有7个词，其中4个是关键词。因此，它的重要性分值等于 ( 4 x 4 ) / 7 =2.3
• 简化：不再区分"簇"，只考虑句子包含的关键词。下面就是一个例子（采用伪码表示），只考虑关键词首先出现的句子

image

6、总结

• 优点：简单快速，结果比较符合实际情况
• 缺点：单纯以“词频”做衡量标准，不够全面，有时重要的词可能出现的次数并不多
– 这种算法无法体现词的位置信息，出现位置靠前的词与出现位置靠后的词，都被视为重要性相同，这是不正确的。（一种解决方法是，对全文的第一段和每一段的第一句话，给予较大的权重。）

（三）LCS

1、LCS定义

• 最长公共子序列（Longest Common Subsequence）
• 一个序列S任意删除若干个字符得到的新序列T，则T叫做S的子序列
• 两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列
– 字符串12455与245576的最长公共子序列为2455
– 字符串acdfg与adfc的最长公共子序列为adf
• 注意区别最长公共子串（Longest Common Substring）
– 最长公共子串要求连接

2、LCS作用

• 求两个序列中最长的公共子序列算法
– 生物学家常利用该算法进行基金序列比对，以推测序列的结构、功能和演化过程。
• 描述两段文字之间的“相似度”
– 辨别抄袭，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，该方法判断修改的部分

3、求解——暴力穷举法

• 假定字符串X，Y的长度分别为m，n；
• X的一个子序列即下标序列{1,2，……，m}严格递增子序列，因此，X共有2^m 个不同子序列；同理，Y有 2ⁿ 个不同子序列;
• 穷举搜索法时间复杂度O（2^m∗ 2ⁿ );
• 对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列;
• 复杂度高，不可用！

4、求解——动态规划法

• 字符串X，长度为m，从1开始数；
• 字符串Y，长度为n，从1开始数；
• X i =<x 1 ，……，x i >即X序列的前i个字符（1<=i<=m）(X i 计作“字符串X的i前缀”)
• Y i =<y 1 ，……，y i >即Y序列的前i个字符（1<=j<=n）(Y j 计作“字符串Y的j前缀”)
• LCS(X,Y)为字符串X和Y的最长公共子序列，即为Z=<z 1 ，……，z k >
如果x_m =y_n（最后一个字符相同），则：x_m 与y_n 的最长公共子序列Z k 的最后一个字符必定为x_m (= y_n)
• 𝑧 𝑘 = x_m = y_n
• LCS(X 𝑚 ,y_n )=LCS(X𝑚−1 , Yn−1 )+x_m 不断递归，每次得出最后一个相同的字符
如果x_m = y_m

image
• 对于上面的字符串X和Y：
• x₃ = y₃=‘C’则有：LCS(BDC, ABC)=LCS(BD,AB)+‘C’
• x₅ = y₄=‘B’则有：LCS(BDCAB, ABCB)=LCS(BDCA,ABC)+‘B’
• 如果x_m≠ y_n，则LCS(X , Y_n)=LCS(X ₋₁, Y_n)，或者LCS(X , Y_n)=LCS(X , Y_n−1)
• 即LCS(X , Y_n)=max{LCS(X ₋₁, Y_n), LCS(X , Y_n−1)}
image
• 对于上面的字符串X和Y：
• x₂ ≠ y₂则有：LCS(BD, AB)=max{LCS(BD, A),LCS(B, AB)}

• x₄ ≠ y₅则有：LCS(BDCA, ABCBD)=max{LCS(BDCA, ABCB),LCS(BDC, ABCBD)}
总结：

image

5、数据结构——二维数组

• 使用二维数组C[m,n]
• C[i,j]记录序列X i 和Y j 的最长公共子序列的长度
– 当i=0或j=0时，空虚了是X i 和Y j 的最长公共子序列，故C[i,j]=0

image

• X =<A, B, C, B, D, A, B>
• Y=<B, D, C, A, B, A>
方法：
1、设计一个二维数组
2、第一个数组作为行，第二个数组作为列，其中根据公式（i=0 || j=0）第一行和第一列均为0
3、以此类推，依据公式,当(i > 0 , j>0 && xi = yi)时，最长公共子序列+1.

image
【实践】TFIDF
【实践】LCS
输入数据格式：左边右边各一个 成对出现
image.png

整个需求我们只需要写一个map就行了，不需要reduce

# -*- coding: utf-8 -*-
#!/usr/bin/python

import sys

def cal_lcs_sim(first_str, second_str):
    len_vv = [[0] * 50] * 50 #测试数据的特点所以初始化50*50数组： 输入数据不能超过50*50

    first_str = unicode(first_str, "utf-8", errors='ignore')#转为Unicode，不能转为utf-8，它们的编码字节长度不一样
    second_str = unicode(second_str, "utf-8", errors='ignore')

    len_1 = len(first_str.strip())
    len_2 = len(second_str.strip())
    #根据公式推导
    for i in range(1, len_1 + 1):
        for j in range(1, len_2 + 1):
            if first_str[i - 1] == second_str[j - 1]:
                len_vv[i][j] = 1 + len_vv[i - 1][j - 1]
            else:
                len_vv[i][j] = max(len_vv[i - 1][j], len_vv[i][j - 1])
  #最长公共子序列len_vv[len_1][len_2]   相似度公式为自己编的 ：文本相似度=(lcs * 2)/总长度
    return float(float(len_vv[len_1][len_2] * 2) / float(len_1 + len_2))


for line in sys.stdin:
    ss = line.strip().split('\t')#判断脏数据
    if len(ss) != 2:
        continue
    first_str = ss[0].strip()#得到两个字符串
    second_str = ss[1].strip()

    sim_score = cal_lcs_sim(first_str, second_str)#根据输入两个字符串，返回一个分数
    print '\t'.join([first_str, second_str, str(sim_score)])

本地测试命令：
cat lcs_input.data | python map.py
运行结果样例：

结果示例

运行脚本：

HADOOP_CMD="/usr/local/src/hadoop-1.2.1/bin/hadoop"
STREAM_JAR_PATH="/usr/local/src/hadoop-1.2.1/contrib/streaming/hadoop-streaming-1.2.1.jar"

INPUT_FILE_PATH_1="/lcs_input.data"
OUTPUT_PATH="/lcs_output"

$HADOOP_CMD fs -rmr -skipTrash $OUTPUT_PATH

# Step 1.
$HADOOP_CMD jar $STREAM_JAR_PATH \
    -input $INPUT_FILE_PATH_1 \
    -output $OUTPUT_PATH \
    -mapper "python map.py" \
    -jobconf "mapred.reduce.tasks=0" \ 不需要reduce
    -jobconf  "mapred.job.name=mr_lcs" \
    -file ./map.py