两种重复文章识别算法——TF-IDF算法和余弦相似性

JamCh01 commented 7 years ago

简介

在爬虫爬取某些网站的文章时，经常会遇到恶意批量刷文章的行为。这些文章的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的乘积，它的值与某词语对于文章的重要性成正比。

计算方法

词频（TF）词频，顾名思义就是某个词语在文章中出现的次数。但为了避免文章长短的差异导致的差距，使用某个词出现的次数占总词数的百分比，来进行一个标准化。
逆文档率（IDF）使用逆文档率时，必须要有一个语料库。计算方法：
计算 TF-IDF = TF*IDF

余弦相似性

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

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

DEMO

给定两个句子 A：我喜欢足球，也喜欢篮球。 B：我喜欢足球，不喜欢篮球。
对句子进行分词，并统计词频

分词
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]

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

将上面的数据带入，得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

Zddup commented 6 years ago

填充词频向量的那部分代码还需要加一部分处理

for word in res:
    if word in tf_1:
        vector_1.append(tf_1[word])
        if word in tf_2:
            vector_2.append(tf_2[word])
        else:
            vector_2.append(0)
    else:
        vector_1.append(0)
        if word in tf_2:
            vector_2.append(tf_2[word])
        else:
            vector_2.append(0)

JamCh01 commented 6 years ago

@Zddup 感谢回复，在填充词频向量之前已经对句子进行了分词（cut_word）如果像您这样操作的话会将，足球，篮球的词频带入第一句，也会把中国和美国的词频带入第二句。但这样似乎并没有什么意义……？欢迎进一步探讨~

JamCh01 / jamch01.github.io