两种重复文章识别算法

简介

在爬虫爬取某些网站的文章时,经常会遇到恶意批量刷文章的行为。这些文章的url不尽相同,无法使用url进行过滤。这就导致了抓取了大量的,重复数据。但数学告诉我们,这事儿简单。

当然,不仅仅可以去除重复的文章。反过来讲,也可以归类近似的文章。

TF-IDF

TF-IDF 实现原理

在介绍之前,是否还有其他方式实现这种过滤重复的方法?

有,统计文章的词频( TF )。按照常理我们认为,某个词重复的次数在文章中占比很大,我们就有理由相信这个词是文章的关键词( Key Word )。

对,这是一个很好的方法,我是用 jieba 分词,将简介中的那段话进行分词,我们一起看看结果。

import jieba
article = '''在爬虫爬取某些网站的文章时,
经常会遇到恶意批量刷文章的行为。
这些文章的url不尽相同,无法使用url进行过滤。
这就导致了抓取了大量的,重复数据。但数学告诉我们,这事儿简单。
'''
res = jieba.lcut_for_search(article)
print(Counter(res))

# Counter({',': 4, '。': 4, '的': 4, '文章': 3, '这': 2, 'url': 2, '了': 2, '不尽': 1, '爬虫': 1, '不尽相同': 1, '进行': 1, '爬取': 1, '经常': 1, '过滤': 1, '这些': 1, '会': 1, '数据': 1, '无法': 1, '我们': 1, '相同': 1, '时': 1, '简单': 1, '重复': 1, '抓取': 1, '批量': 1, '行为': 1, '网站': 1, '遇到': 1, '刷': 1, '恶意': 1, '某些': 1, '在': 1, '大量': 1, '事儿': 1, '导致': 1, '数学': 1, '使用': 1, '告诉': 1, '就': 1, '但': 1})

好吧,先忽略标点符号。那最多出现的就是这个字。类如这种词,在句中并无具体意义,我们将这种词称为停止词

在统计词频时,我们需要略过这种无意义的停止词。

假设文章爬虫重复这几个词的词频相同。根据一般认知,文章这个词的出现频率要比其他两个要高(在其他正常的文章中)。这就使我们无法确认文章是否是这篇文章的关键词。

这里,我们知道了 TF 是什么意思,接下来是 IDF 。

如果某个词十分少见,但在某篇文章中多次出现,那么这个词在很大程度上反映了这篇文章的主题。

在统计学中,我们对每个词语分配一个权重。如果这个词十分常见,那么这个权重值就会低;反之,则高。

这个权重值,就被成为逆文档频率(Inverse Document Frequency)

TF-IDF 算法,即就是 TF 与 IDF 的乘积,它的值与某词语对于文章的重要性成正比。

计算方法

  1. 词频(TF) 词频,顾名思义就是某个词语在文章中出现的次数。但为了避免文章长短的差异导致的差距,使用某个词出现的次数占总词数的百分比,来进行一个标准化。

  2. 逆文档率(IDF) 使用逆文档率时,必须要有一个语料库。计算方法:

$$ \ IDF=\ log(\frac{all}{contain + 1}) $$

其中 all 表示 the-num-of-articles-in-the-train-set contain 表示 the-num-of-articles-that-contain-words

  1. 计算 TF-IDF = TF * IDF

余弦相似性

余弦相似性(通过计算两个向量的夹角余弦值来评估他们的相似度。)

根据向量坐标,绘制在空间中,求得夹角的Cos值。Cos值越接近1,则说明夹角越小,即两向量相似。 更多

DEMO

  1. 给定两个句子 A: 我喜欢足球,也喜欢篮球。 B: 我喜欢足球,不喜欢篮球。

  2. 对句子进行分词,并统计词频

分词
A:我/ 喜欢/ 足球/ ,/ 也/ 喜欢/ 篮球 /。
B:我/ 喜欢/ 足球/ ,/ 不/ 喜欢/ 篮球/ 。

出现的所有的词语:
我/ 喜欢/ 足球 / 篮球/ 也/ 不

词频
A:我:1,喜欢:2,足球:1,篮球:1,也:1,不:0
B:我:1,喜欢:2,足球:1,篮球:1,也:1,不:1

词频向量
A:[1, 2, 1, 1, 0]
B:[1, 2, 1, 1, 1]

好了,这里我们就可以开始计算相似性了。 计算公式如下:

$$ \cos (\theta ) =\frac{\sum ^{n}_{i=1} A _{i} B _{i}}{\sqrt{\sum ^{n}_{i=1}( A _{i})^2+\sqrt{\sum ^{n}_{i=i}( B _{i}) ^2}}} $$

将上面的数据带入,得0.9354(保留四位小数)θ约为21.4300°(保留四位小数)。 那么,我们可以说A句和B句十分的相似。

Python

# -*- coding: utf8 -*-
import math
import jieba.analyse
article_a = '我喜欢中国,也喜欢美国。'
article_b = '我喜欢足球,不喜欢篮球。'

def cut_word(article):
    # 这里使用了 TF - IDF 算法,所以分词结果会有些不同-> https://github.com/fxsjy/jieba#3 -关键词提取
    res = jieba.analyse.extract_tags(
        sentence=article, topK=20, withWeight=True)
    return res

def tf_idf(res1=None, res2=None):
    # 向量,可以使用list表示
    vector_1 = []
    vector_2 = []
    # 词频,可以使用dict表示
    tf_1 = {i[0]: i[1] for i in res1}
    tf_2 = {i[0]: i[1] for i in res2}
    res = set(list(tf_1.keys()) + list(tf_2.keys()))

    # 填充词频向量
    for word in res:
        if word in tf_1:
            vector_1.append(tf_1[word])
        else:
            vector_1.append(0)
            if word in tf_2:
                vector_2.append(tf_2[word])
            else:
                vector_2.append(0)

    return vector_1, vector_2

def numerator(vector1, vector2):
    #分子
    return sum(a * b for a, b in zip(vector1, vector2))

def denominator(vector):
    #分母
    return math.sqrt(sum(a * b for a,b in zip(vector, vector)))

def run(vector1, vector2):
    return numerator(vector1,vector2) / (denominator(vector1) * denominator(vector2))

vectors =  tf_idf(res1=cut_word(article=article_a), res2=cut_word(article=article_b))
# 相似度
similarity = run(vector1=vectors[0], vector2=vectors[1])
# 使用 arccos 计算弧度
rad = math.acos(similarity)
print(similarity, rad)

# 0.2157074518785444 1.353380046633586