大數據之路【第十二篇】：數據挖掘--NLP文本相似度

一、詞頻----TF

• 假設：如果一個詞很重要，應該會在文章中多次出現

• 詞頻——TF（Term Frequency）：一個詞在文章中出現的次數

• 也不是絕對的！出現次數最多的是“的”“是”“在”，這類最常用的詞，叫做停用詞（stop words）

• 停用詞對結果毫無幫助，必須過濾掉的詞

• 過濾掉停用詞後就一定能接近問題麽？

• 進一步調整假設：如果某個詞比較少見，但是它在這篇文章中多次出現，那麽它很可能反映了這篇文章的特性，正是我們所需要的關鍵詞

二、反文檔頻率----IDF

• 在詞頻的基礎上，賦予每一個詞的權重，進一步體現該詞的重要性，

• 最常見的詞（“的”、“是”、“在”）給予最小的權重

• 較常見的詞（“國內”、“中國”、“報道”）給予較小的權重

• 較少見的詞（“養殖”、“維基”）

• 將TF和IDF進行相乘，就得到了一個詞的TF-IDF值，某個詞對文章重要性越高，該值越大，於是排在前面的幾個詞，就是這篇文章的關鍵詞。

計算步驟

三、LCS定義

• 最長公共子序列（Longest Common Subsequence）
• 一個序列S任意刪除若幹個字元得到的新序列T，則T叫做S的子序列
• 兩個序列X和Y的公共子序列中，長度最長的那個，定義為X和Y的最長公共子序列
    – 字元串12455與245576的最長公共子序列為2455
    – 字元串acdfg與adfc的最長公共子序列為adf
• 註意區別最長公共子串（Longest Common Substring）
   – 最長公共子串要求連接 

四、LCS作用

• 求兩個序列中最長的公共子序列演算法
    –   生物學家常利用該演算法進行基金序列比對，以推測序列的結構、功能和演化過程。
• 描述兩段文字之間的“相似度”
    –   辨別抄襲，對一段文字進行修改之後，計算改動前後文字的最長公共子序列，將除此子序列
外的部分提取出來，該方法判斷修改的部分

五、求解---暴力窮舉法

• 假定字元串X，Y的長度分別為m，n；

• X的一個子序列即下標序列{1,2，……，m}嚴格遞增子序列，因此，X共有2^m 個不同子序列；同理，Y有2^n 個不同子序列;

• 窮舉搜索法時間複雜度O(2 ^m ∗ 2^n );

• 對X的每一個子序列，檢查它是否也是Y的子序列，從而確定它是否為X和Y的公共子序列，並且在檢查過程中選出最長的公共子序列;

• 複雜度高，不可用！

六、求解---動態規劃法

• 字元串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 ? 與Y n 的最長公共子序列Z k 的最後一個字元必定為x m (= y n )

• Zk= x m = y n

七、LCS總結分析

• 屬於動態規劃問題！

八、數據結構----二維數組

• 使用二維數組C[m,n]
• C[i,j]記錄序列X i 和Y j 的最長公共子序列的長度
– 當i=0或j=0時，空虛了是X i 和Y j 的最長公共子序列，故C[i,j]=0

 例子：

• X =<A, B, C, B, D, A, B>
• Y=<B, D, C, A, B, A>

 mr_lcs mapreduce

##map.py

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

import sys

def cal_lcs_sim(first_str, second_str):
    len_vv = [[0] * 50] * 50

    first_str = unicode(first_str, "utf-8", errors='ignore')
    second_str = unicode(second_str, "utf-8", errors='ignore')

    len_1 = len(first_str.strip())
    len_2 = len(second_str.strip())

    #for a in first_str:
        #word = a.encode('utf-8')

    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])

    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)])

#run.sh

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" \
    -jobconf  "mapred.job.name=mr_lcs" \
    -file ./map.py

mr_tfidf mapreduce

##red.py
#!/usr/bin/python

import sys
import math

current_word = None
count_pool = []
sum = 0

docs_cnt = 508

for line in sys.stdin:
    ss = line.strip().split('\t')
    if len(ss) != 2:
        continue

    word, val = ss

    if current_word == None:
        current_word = word

    if current_word != word:
        for count in count_pool:
            sum += count
        idf_score = math.log(float(docs_cnt) / (float(sum) + 1))
        print "%s\t%s" % (current_word, idf_score)

        current_word = word
        count_pool = []
        sum = 0

    count_pool.append(int(val))


for count in count_pool:
    sum += count
idf_score = math.log(float(docs_cnt) / (float(sum) + 1))
print "%s\t%s" % (current_word, idf_score)

##run.sh

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="/tfidf_input.data"
OUTPUT_PATH="/tfidf_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" \
    -reducer "python red.py" \
    -file ./map.py \
    -file ./red.py