欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

大数据之路【第十二篇】:数据挖掘--NLP文本相似度

程序员文章站 2022-05-18 12:12:34
一、词频 TF • 假设:如果一个词很重要,应该会在文章中多次出现 • 词频——TF(Term Frequency):一个词在文章中出现的次数 • 也不是绝对的!出现次数最多的是“的”“是”“在”,这类最常用的词,叫做停用词(stop words)• 停用词对结果毫无帮助,必须过滤掉的词 • 过滤掉 ......

一、词频----tf

• 假设:如果一个词很重要,应该会在文章中多次出现


• 词频——tf(term frequency):一个词在文章中出现的次数


• 也不是绝对的!出现次数最多的是“的”“是”“在”,这类最常用的词,叫做停用词(stop words)

• 停用词对结果毫无帮助,必须过滤掉的词


• 过滤掉停用词后就一定能接近问题么?


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

二、反文档频率----idf

• 在词频的基础上,赋予每一个词的权重,进一步体现该词的重要性,


• 最常见的词(“的”、“是”、“在”)给予最小的权重


• 较常见的词(“国内”、“中国”、“报道”)给予较小的权重


• 较少见的词(“养殖”、“维基”)


• 将tf和idf进行相乘,就得到了一个词的tf-idf值,某个词对文章重要性越高,该值越大,于是排在前面的几个词,就是这篇文章的关键词。


计算步骤

大数据之路【第十二篇】:数据挖掘--NLP文本相似度

 

 

 

三、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

大数据之路【第十二篇】:数据挖掘--NLP文本相似度

七、lcs总结分析

大数据之路【第十二篇】:数据挖掘--NLP文本相似度

 

• 属于动态规划问题!

 

 

八、数据结构----二维数组

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

大数据之路【第十二篇】:数据挖掘--NLP文本相似度

 

 

 例子:

• x =<a, b, c, b, d, a, b>
• y=<b, d, c, a, b, a>

大数据之路【第十二篇】:数据挖掘--NLP文本相似度

 

 

 

 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