（一）余弦相似度、向量空間模型
1、相似度
? 相似度度量：計(jì)算個(gè)體間相似程度
? 相似度值越小巩搏，距離越大，相似度值越大趾代，距離越小
? 最常用——余弦相似度
– 一個(gè)向量空間中兩個(gè)向量夾角的余弦值作為衡量兩個(gè)個(gè)體之間差異的大小
– 余弦值接近1贯底，夾角趨于0，表明兩個(gè)向量越相似
2撒强、例子
3禽捆、處理流程
? 得到了文本相似度計(jì)算的處理流程是:
– 找出兩篇文章的關(guān)鍵詞笙什；
– 每篇文章各取出若干個(gè)關(guān)鍵詞，合并成一個(gè)集合睦擂，計(jì)算每篇文章對(duì)于這個(gè)集合中的詞的詞頻
– 生成兩篇文章各自的詞頻向量得湘；
– 計(jì)算兩個(gè)向量的余弦相似度，值越大就表示越相似顿仇。
（二）TFIDF
1淘正、詞頻——TF
? 假設(shè)：如果一個(gè)詞很重要，應(yīng)該會(huì)在文章中多次出現(xiàn)
? 詞頻——TF（Term Frequency）：一個(gè)詞在文章中出現(xiàn)的次數(shù)
? 也不是絕對(duì)的臼闻！出現(xiàn)次數(shù)最多的是“的”“是”“在”鸿吆，這類最常用的詞，叫做停用詞（stop words）
? 停用詞對(duì)結(jié)果毫無幫助述呐，必須過濾掉的詞
? 過濾掉停用詞后就一定能接近問題么惩淳？
? 進(jìn)一步調(diào)整假設(shè)：如果某個(gè)詞比較少見，但是它在這篇文章中多次出現(xiàn)乓搬，那么它很可能反映了這篇文章的特性思犁，正是我們所需要的關(guān)鍵詞
2、反文檔頻率——IDF
? 在詞頻的基礎(chǔ)上进肯，賦予每一個(gè)詞的權(quán)重激蹲，進(jìn)一步體現(xiàn)該詞的重要性，
? 最常見的詞（“的”江掩、“是”学辱、“在”）給予最小的權(quán)重
? 較常見的詞（“國內(nèi)”、“中國”环形、“報(bào)道”）給予較小的權(quán)重
? 較少見的詞（“養(yǎng)殖”策泣、“維基”）
? 將TF和IDF進(jìn)行相乘，就得到了一個(gè)詞的TF-IDF值抬吟，某個(gè)詞對(duì)文章重要性越高萨咕，該值越大，于是排在前面的幾個(gè)詞拗军，就是這篇文章的關(guān)鍵詞任洞。
3、計(jì)算步驟
4发侵、相似文章
? 使用TF-IDF算法，找出兩篇文章的關(guān)鍵詞妆偏；
? 每篇文章各取出若干個(gè)關(guān)鍵詞（比如20個(gè)）刃鳄，合并成一個(gè)集合，計(jì)算每篇文章對(duì)于這個(gè)集合中的詞的詞頻（為了避免文章長度的差異钱骂，可以使用相對(duì)詞頻）叔锐；
? 生成兩篇文章各自的詞頻向量挪鹏；
? 計(jì)算兩個(gè)向量的余弦相似度，值越大就表示越相似愉烙。
5讨盒、自動(dòng)摘要
? 文章的信息都包含在句子中，有些句子包含的信息多步责，有些句子包含的信息少返顺。"自動(dòng)摘要"就是要找出那些包含信息最多的句子。
? 句子的信息量用"關(guān)鍵詞"來衡量蔓肯。如果包含的關(guān)鍵詞越多遂鹊，就說明這個(gè)句子越重要。
? 只要關(guān)鍵詞之間的距離小于“門檻值”蔗包，它們就被認(rèn)為處于同一個(gè)簇之中秉扑，如果兩個(gè)關(guān)鍵詞之間有5個(gè)以上的其他詞，就可以把這兩個(gè)關(guān)鍵詞分在兩個(gè)簇调限。
? 下一步舟陆，對(duì)于每個(gè)簇，都計(jì)算它的重要性分值耻矮。
? 例如：其中的簇一共有7個(gè)詞秦躯，其中4個(gè)是關(guān)鍵詞。因此淘钟，它的重要性分值等于 ( 4 x 4 ) / 7 =2.3
? 簡化：不再區(qū)分"簇"宦赠，只考慮句子包含的關(guān)鍵詞。下面就是一個(gè)例子（采用偽碼表示）米母，只考慮關(guān)鍵詞首先出現(xiàn)的句子
6勾扭、總結(jié)
? 優(yōu)點(diǎn)：簡單快速，結(jié)果比較符合實(shí)際情況
? 缺點(diǎn)：單純以“詞頻”做衡量標(biāo)準(zhǔn)铁瞒，不夠全面妙色，有時(shí)重要的詞可能出現(xiàn)的次數(shù)并不多
– 這種算法無法體現(xiàn)詞的位置信息，出現(xiàn)位置靠前的詞與出現(xiàn)位置靠后的詞慧耍，都被視為重要性相同身辨，這是不正確的。（一種解決方法是芍碧，對(duì)全文的第一段和每一段的第一句話煌珊，給予較大的權(quán)重。）
（三）LCS
1泌豆、LCS定義
? 最長公共子序列（Longest Common Subsequence）
? 一個(gè)序列S任意刪除若干個(gè)字符得到的新序列T定庵，則T叫做S的子序列
? 兩個(gè)序列X和Y的公共子序列中，長度最長的那個(gè)，定義為X和Y的最長公共子序列
– 字符串12455與245576的最長公共子序列為2455
– 字符串a(chǎn)cdfg與adfc的最長公共子序列為adf
? 注意區(qū)別最長公共子串（Longest Common Substring）
– 最長公共子串要求連接
2蔬浙、LCS作用
? 求兩個(gè)序列中最長的公共子序列算法
– 生物學(xué)家常利用該算法進(jìn)行基金序列比對(duì)猪落，以推測序列的結(jié)構(gòu)、功能和演化過程畴博。
? 描述兩段文字之間的“相似度”
– 辨別抄襲笨忌，對(duì)一段文字進(jìn)行修改之后，計(jì)算改動(dòng)前后文字的最長公共子序列俱病，將除此子序列外的部分提取出來官疲，該方法判斷修改的部分
3、求解——暴力窮舉法
? 假定字符串X庶艾，Y的長度分別為m袁余，n；
? X的一個(gè)子序列即下標(biāo)序列{1,2咱揍，……颖榜，m}嚴(yán)格遞增子序列，因此煤裙，X共有2m 個(gè)不同子序列掩完；同理，Y有 2n 個(gè)不同子序列;
? 窮舉搜索法時(shí)間復(fù)雜度O（2m? 2n );
? 對(duì)X的每一個(gè)子序列硼砰，檢查它是否也是Y的子序列且蓬，從而確定它是否為X和Y的公共子序列，并且在檢查過程中選出最長的公共子序列;
? 復(fù)雜度高题翰，不可用恶阴！
4、求解——?jiǎng)討B(tài)規(guī)劃法
? 字符串X豹障，長度為m冯事，從1開始數(shù)；
? 字符串Y血公，長度為n昵仅，從1開始數(shù)；
? X i =<x 1 累魔，……摔笤，x i >即X序列的前i個(gè)字符（1<=i<=m）(X i 計(jì)作“字符串X的i前綴”)
? Y i =<y 1 ，……垦写，y i >即Y序列的前i個(gè)字符（1<=j<=n）(Y j 計(jì)作“字符串Y的j前綴”)
? LCS(X,Y)為字符串X和Y的最長公共子序列吕世，即為Z=<z 1 ，……梯投，z k >
如果xm =yn（最后一個(gè)字符相同）寞冯，則：xm 與yn 的最長公共子序列Z k 的最后一個(gè)字符必定為xm (= yn)
? ?? ?? = xm = yn
? LCS(X ?? ,yn )=LCS(X???1 , Yn?1 )+xm 不斷遞歸渴析，每次得出最后一個(gè)相同的字符
如果xm = ym
? 對(duì)于上面的字符串X和Y：
? x3 = y3=‘C’則有：LCS(BDC, ABC)=LCS(BD,AB)+‘C’
? x5 = y4=‘B’則有：LCS(BDCAB, ABCB)=LCS(BDCA,ABC)+‘B’
? 如果xm≠ yn晚伙，則LCS(X , Yn)=LCS(X ?1, Yn)吮龄，或者LCS(X , Yn)=LCS(X , Yn?1)
? 即LCS(X , Yn)=max{LCS(X ?1, Yn), LCS(X , Yn?1)}
? 對(duì)于上面的字符串X和Y：
? x2 ≠ y2則有：LCS(BD, AB)=max{LCS(BD, A),LCS(B, AB)}
? x4 ≠ y5則有：LCS(BDCA, ABCBD)=max{LCS(BDCA, ABCB),LCS(BDC, ABCBD)}
總結(jié)：
5、數(shù)據(jù)結(jié)構(gòu)——二維數(shù)組
? 使用二維數(shù)組C[m,n]
? C[i,j]記錄序列X i 和Y j 的最長公共子序列的長度
– 當(dāng)i=0或j=0時(shí)咆疗，空虛了是X i 和Y j 的最長公共子序列漓帚，故C[i,j]=0
? X =<A, B, C, B, D, A, B>
? Y=<B, D, C, A, B, A>
方法：
1、設(shè)計(jì)一個(gè)二維數(shù)組
2午磁、第一個(gè)數(shù)組作為行尝抖，第二個(gè)數(shù)組作為列，其中根據(jù)公式（i=0 || j=0）第一行和第一列均為0
3迅皇、以此類推昧辽，依據(jù)公式,當(dāng)(i > 0 , j>0 && xi = yi)時(shí)，最長公共子序列+1.
【實(shí)踐】TFIDF
【實(shí)踐】LCS
輸入數(shù)據(jù)格式：左邊右邊各一個(gè) 成對(duì)出現(xiàn)
整個(gè)需求我們只需要寫一個(gè)map就行了登颓，不需要reduce
# -*- coding: utf-8 -*-
#!/usr/bin/python
import sys
def cal_lcs_sim(first_str, second_str):
len_vv = [[0] * 50] * 50 #測試數(shù)據(jù)的特點(diǎn)所以初始化50*50數(shù)組： 輸入數(shù)據(jù)不能超過50*50
first_str = unicode(first_str, "utf-8", errors='ignore')#轉(zhuǎn)為Unicode搅荞，不能轉(zhuǎn)為utf-8，它們的編碼字節(jié)長度不一樣
second_str = unicode(second_str, "utf-8", errors='ignore')
len_1 = len(first_str.strip())
len_2 = len(second_str.strip())
#根據(jù)公式推導(dǎo)
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])
#最長公共子序列l(wèi)en_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')#判斷臟數(shù)據(jù)
if len(ss) != 2:
continue
first_str = ss[0].strip()#得到兩個(gè)字符串
second_str = ss[1].strip()
sim_score = cal_lcs_sim(first_str, second_str)#根據(jù)輸入兩個(gè)字符串框咙，返回一個(gè)分?jǐn)?shù)
print '\t'.join([first_str, second_str, str(sim_score)])
本地測試命令：
cat lcs_input.data | python map.py
運(yùn)行結(jié)果樣例：
運(yùn)行腳本：
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
