/tfidf-test

tf-idf算法python实现

Primary LanguagePythonApache License 2.0Apache-2.0

TF-IDF漫谈

摘要

本篇文章主要谈一谈TF-IDF算法，因为这个算法几乎处处可见，搜索排序，用户画像，以及事件热点，之所以叫漫谈是因为不涉及到很深的理论知识和算法过程，取而代之的是很多感性上的认知。

一. TF-IDF是干嘛用的

TF-IDF的核心作用就是关键词提取，而关键词提取可以服务于其他很多业务。TF-IDF算法提出应该有差不多五十个年头了，但是应用至今，因为他是一个简介有效而且理论上很有说服力的算法。接下来我会从感性到理性，从表面到本质来一步一步阐述这个算法是如何产生的。

首先，提到关键词，什么是关键词，他的定义可能比较模糊，但是他判定却相对来讲比较清晰。比如读完《西游记》，西游记的关键字是什么？“贾宝玉”、“林黛玉”？肯定不是，八杆子打不着的东西。“和尚”、“观音”？有点儿像，但是不够关键，《白蛇传》里边儿也有很多和尚也有观音。“水德星君”、“卯日星君”？好像也不是，虽然跟《西游记》相关但是不具代表性。“孙悟空”、“猪八戒”？是的，毫无疑问。

基于以上感性的认知，我们来看看关键词是什么样的：

  1. 文章中要有，像“贾宝玉”、“林黛玉”就不行。（文章中没有的但是关键的是属于更高级的概括这里不再讨论范围）
  2. 要有独特，最好别的文章中没有，像“和尚”这样的词大部分古代小说中都有，谁知道你说的是哪一部
  3. 要有代表性，“水德星君”这样的词虽然够独特，但是只看过一遍的或者看的不仔细的人很可能都忘记了。

所以感性上的理解，关键词要在文章中，别的文章最好没有，即文档分布（Inverse Document Frequency, $IDF$），本篇文章最好要多出现，即词频（Term Fraquency, $TF$）。好了，现在我们可以构建一个关键词公式了，：

$$k=\frac{TF}{IDF}$$

看起来很好，词频越高越关键，其他文档分布越少越关键，起个名字吧，cedar公式，cedar理论，但是存在两个问题，一个是在你实验之后会发现效果不是特别好，要调参，这里乘以5那里除以2，甚至开方平方求对数，等等等等，第二个是这是我们的感性认知，有没有理论依据呢？为了创建这个理论我们下了三个定义，牛顿的力学也只有三定律啊。这个如果能成为一个理论的话，自然语言处理的书会不会太厚了。我们尝试一下从信息论里找答案，因为文章的阅读本质上也是一种信息的传输。

二、TF-IDF算法的信息论依据

我们刚刚为了解决关键词的问题给关键词下了三个定义，构建了一个定性的公式。现在我们来更本质的看下这个问题，而且给一个合理的定量的公式。

刚刚我们谈到文章的阅读实际上是一种信息的传递，那么我们能不能找到一个能表示信息量大小的东西来衡量词语，信息量越大的词越关键是不是可以解决这个问题？当然可以，而且有人已经为我们找好了，这个人就叫香农，信息论的奠基人，程序员的祖师爷之一，这个信息量的度量的公式也就叫做香农熵。这个公式背后是基于怎样的思考我们不讨论（我不知道）。我们直接看看这个公式的定义：

对于任意一个随机变量 X，它的熵定义如下：

$$H(X)=-\sum P(x)\log_2{P(x)}$$

变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大。

这里的随机变量在关键词提取的任务中就是词，$P(x)$就是词$x$的概率，根据大数定律，我们可以用词在样本中出现的频率也就是词频(Term Frequency,TF)表示。单个词语的信息量我们搞定了，但是上面我们总结的司塔科定理中他还要相对于其他文章，信息论能搞定吗？能，祖师爷们早都已经把工具给我们造好了，这个工具就是互信息，（在吴军老师的《数学之美》中提到逆文档频率实际上是特定情况下关键词分布的交叉熵，因为我没找到这段话相关的证明，另外单单解释逆文档频率的话并不能表明为何是相乘的关系，所以这里就用了互信息的解释，交叉熵相关定义见附录）直接看定义：

在概率论和信息论中，两个随机变量的互信息（Mutual Information，简称>MI）或转移信息（transinformation）是变量间相互依赖性的量度。不同于相>关系数，互信息并不局限于实值随机变量，它更加一般且决定着联合分布 p(X,>Y) 和分解的边缘分布的乘积 p(X)p(Y) 的相似程度。互信息是点间互信息 （PMI）的期望值。互信息最常用的单位是bit。

一般地，两个离散随机变量 X 和 Y 的互信息可以定义为：

$$I(X;Y)=\sum_{{y\in Y}}\sum_{{x\in X}}p(x,y)\log {\left({\frac {p(x,y)}{p(x)\,p(y)}}\right)},\,\!$$

其中 $p(x,y)$ 是 $X$ 和 $Y$ 的联合概率分布函数，而$p(x)$ 和$p(y)$分别是$X$和$Y$的边缘概率分布函数。

我们把互信息公式展开一下

$$\begin{aligned} I(X;Y) & = \sum_{{y\in Y}}\sum_{{x\in X}}p(x,y)\log {\left({\frac {p(x,y)}{p(x)p(y)}}\right)} \\\ & = \sum_{{y\in Y}}\sum_{{x\in X}}p(x,y)\log {\left({\frac {p(x,y)}{p(x)} \frac{1}{p(y)}}\right)} \\\ & = - \sum_{{y\in Y}}\sum_{{x\in X}}p(x,y)\log {{p(y) }} -(-\sum_{{y\in Y}}\sum_{{x\in X}}p(x,y)\log {\left({\frac {p(x,y)}{p(x)} }\right)}) \\\ & = H(X) - H(X|Y) \\\ & = H(X) + H(Y) - H(XY) \end{aligned}$$

这里边涉及到条件熵$H(X|Y)$和联合熵$H(XY)$，我把公式整理了一下，条件熵计算公式就是第三个等号的后半部分，联合熵的计算本文不涉及到所以不展开，这两个熵的定义也不展开了，详情可以去维基看一看，中文维基给了很详细的解释。

好了，接下来可能需要一点统计学的思维，不然可能会比较绕。我们让$D={d_1,d_2,...,d_N}$作为文章集合，$W={w_1,w_2,...,w_M}$作为去重后的词集合，$N$和$M$分别是文章总数和词总数。用$d_j$表示事件从$D$中抽取一篇文档，类似的$w_i$表示事件从$W$中选择一个词。$\mathcal D$和$\mathcal W$作为定义在事件${d_1,d_2,...,d_N}$和${w_1,w_2,...,w_N}$上的随机变量

假设所有的文档都会被同等概率的抽取到，即对于$d_j \in D$，$P(d_j)=\frac{1}{N}$，那么$\mathcal{D}$的信息熵就是

$$H(\mathcal{D}) = - \sum_{d_j \in D} P(d_j)\log P(d_j) = -N \frac{1}{N}\log \frac{1}{N} = -\log \frac{1}{N} \label (10)$$

接下来我们考虑在已知包含关键词$w_i(\in W)$的文档已知的情况。让$N_i$表示包含$w_i$的文档数，还是假设这$N_i$个文档出现的概率相等，这样，对于给定$w_i$的随机变量$\mathcal D$的熵如下所示：

$$H(\mathcal {D}|w_i) = -\sum_{d_j \in D}P(d_j|w_i)\log P(d_j|w_i)=-N_i \frac{1}{N_i}\log \frac {1}{N_i} = -\log \frac {1}{N_i}$$

有两点需要注意，一个是不包含$w_i$的文档因为$P(d_j|w_i)=0$，所以在等式中消失了，另一点是条件概率的计算基于了上面的那个假设。

好了，基本工作做的差不多了，现在我们假设从整个文章集合中随机的取出一个词$w_i$，用$f_{ij}$表示文章$d_j$中词$w_i$的次数，$f_{w_i}$表示$w_i$在整个文章集合中出现的次数，文章集合中出现的总词数记为$F$，对于给定的$w_i$，被选中的概率是$\frac {\sum_jf_{ij}}{F}=\frac {f_{w_i}}{F}$。那么文章和词之间的互信息可以计算如下（互信息和条件熵的关系，在互信息的展开公式中已经给出）：

$$\begin{aligned} J(\mathcal {D}; \mathcal {W}) & = H(\mathcal {D})-H(\mathcal {D}|\mathcal {W}) \\\ & = \sum_{w_i \in W}P(w_i)(H(\mathcal {D})-H(\mathcal {D}|w_i)) \\\ & = \sum_{w_i \in W} \frac {f_{w_i}}{F}(-\log \frac {1}{N} + \log \frac {1}{N_i}) \\\ & = \sum_{w_i \in W} \frac {f_{w_i}} {F} \log \frac{N}{N_i} \\\ & = \sum_{w_i \in W} \sum_{d_j \in D} \frac {f_{ij}}{F}\log \frac {N}{N_i} \end{aligned}$$

最后的两个等式给了我们计算这个互信息的两种方式，展现的是从两个不同的方面来观察互信息，倒数第二个等式表示互信息是所有去重后词语的权重的总和，也就是相对于整个文章集合，关键词权重的总和，这里就提供了单个词语的权重计算方式。倒数第一个等式表明互信息是每篇文章中每个去重后的词的权重的总和，这里的权重就是我们所讲到的TF-IDF值大小，也就是关键程度，两个等式分别给出了相对于单篇文章和相对于整个文档集合的关键程度的计算方式。

最后提一下这种推理方式成立基于了两个假设，一个是用频率来衡量概率，另一个是对问题作了简化处理，假设

$$P(d_j)=\sum_{W(d_j)} \frac {f_{w_i}}{F} \frac {1}{N_i} \approx \frac {1}{N} \\\ P(w_i, d_j) = \frac {f_{w_i}} {F} \frac {1}{N_i} \approx \frac {f_{ij}}{F}$$

其中$W(d_j)$表示文章$d_j$包含的去重后所有词的集合。第一个假设在数据量大的情况下基本可以符合实际，而第二个假设实际上是一种很强的假设，比如我们看一个满足假设的例子，如果文章满足每个相同的词只出现一次，而且每篇文章大小相同的条件

$$\begin{aligned} P(d_j) & = \sum_{W(d_j)} \frac {f_{w_i}}{F} \frac {1}{N_i} \\\ & = \sum_{W(d_j)} \frac {1}{F} \qquad 每个文档同一个词只出现一次，所以f_{w_i} = N_i \\\ & = |W(d_j)|*\frac {1}{F} \\\ & = |W(d_j)|*\frac {1}{F} \qquad 每个文档同一个词只出现一次，每个文档长度相同，所以|W(d_j)| = \frac{F}{N} \\ & = \frac {1}{N} \end{aligned}$$

同样的，对于假设二的第二个公式：

$$\begin{aligned} P(w_i, d_j) &= \frac {f_{w_i}} {F} \frac {1}{N_i} \\\ &= \frac {1} {F} \frac {f_{w_i}}{N_i} \\\ &= \frac {f_{ij}} {F} \qquad f_{ij}取平均值 \end{aligned}$$

当然，这种条件满足假设二并不代表假设二必须要是这种条件，吴军老师在推导tf-idf公式的时候用了类似的条件，这是一个看起来很反人类的条件，这么做的原因一个是让公式可以推导下去，因为里边有很多对数计算，如果考虑很复杂的情况下很可能得不到比较好的结果。这也是TF-IDF算法会产生坏结果的原因。此外这里的互信息的计算是针对整个文档集合和整个词集合的，所以条件中$f_{ij}$取均值，当计算指定文档的指定词的权重时，我们依旧会取该文档中的$f_{ij}$

实验

这里我取了《西游记》作为实验数据，结巴分词作为分词工具，没做停用词处理，直接取词长大于2的做计算，本实验代码使用的语料可以从这里下载，下载之后可以直接用。上式中的$F$在语料固定的情况下是常数，所以程序中并没有计算它的大小，但这丝毫不会影响到关键词排序结果。

import re
import pandas
import jieba
import operator
import time
import pickle

start_time = time.time()
term_freq_dict = {}
doc_list = []
tmp_list = []
voc_list = []
with open("西游记_吴承恩_shushu8.com.txt", "r", encoding="utf-8") as f:
    while 1:
        line = f.readline()
        if line:
            if re.match(r'第[0-9]{3}', line):
                doc_list.append(tmp_list)
                voc_list += list(set(tmp_list))
                voc_list = list(set(voc_list))
                tmp_list = []
            else:
                tmp_list += jieba.lcut(line)
        else:
            break
# 计算IDF值，因为这个过程比较耗时间所以可以计算完之后保存结果用的时候直接从文件加载
# for voc in voc_list:
#     for doc in doc_list:
#         if doc.__contains__(voc):
#             try:
#                 term_freq_dict[voc] += 1
#             except KeyError:
#                 term_freq_dict[voc] = 1
#             continue
#
# import math
# term_idf_dict = {}
# for t in term_freq_dict:
#     term_idf_dict[t] = math.log2(term_freq_dict[t]/100)
#
# 保存结果
# idf_pkl = open("idf_pkl", "wb")
# pickle.dump(term_idf_dict, idf_pkl, -1)
# idf_pkl.close()
#
#加载结果，第一次运行要去掉上面的代码注释
idf_pkl_r = open("idf_pkl", "rb")
term_idf_dict = pickle.load(idf_pkl_r)
idf_pkl_r.close()

def get_keyword(num_doc):
    doc_tf_idf_dict = {}
    term_freq = pandas.value_counts(pandas.Series(doc_list[num_doc]))
    for t in term_freq.keys():
        if len(t) > 1:
            try:
                doc_tf_idf_dict[t] = -term_freq[t]*term_idf_dict[t] # TF*IDF
            except KeyError:
                pass
    sorted_list = sorted(doc_tf_idf_dict.items(), key=operator.itemgetter(1), reverse=True)  
    return sorted_list

keyword_list = get_keyword(72)
print("耗时：%s s" % int(time.time()-start_time))
print(50*"=")
print("词\t\t\t\ttf-idf")
print(50*"=")
for idx, k in enumerate(keyword_list):
    if idx < 100:
        print("%-25s\t%10s" % (k[0], str(k[1])))
        print(50*"-")
    else:
        break

这里打印了第六十章的关键字，我先不说第六十章标题是什么，可以根据关键字猜测一下

耗时：4 s
==================================================
词                              tf-idf
==================================================
女子                            63.909833713109634
--------------------------------------------------
丝绳                            30.353362134321408
--------------------------------------------------
七个                            26.855508874019844
--------------------------------------------------
浴池                            26.575424759098897
--------------------------------------------------
石桥                            23.21928094887362
--------------------------------------------------
盘丝洞                          22.575424759098897
--------------------------------------------------
衣架                            20.235574756214273
--------------------------------------------------
热水                            19.931568569324174
--------------------------------------------------
仙姑                            19.931568569324174
--------------------------------------------------
丝篷                            19.931568569324174
--------------------------------------------------
亭子                            19.182506338585604
--------------------------------------------------
土地                            18.647236713895072
--------------------------------------------------
濯垢泉                          16.931568569324174
--------------------------------------------------
虫蛭                            16.931568569324174
--------------------------------------------------
布施                            15.346005070868483
--------------------------------------------------
吊起                            15.176681067160704
--------------------------------------------------
跟头                            15.176681067160704
--------------------------------------------------
高耸                            14.5754247590989
--------------------------------------------------
翠袖                            13.931568569324174
--------------------------------------------------
鲇鱼                            13.931568569324174
--------------------------------------------------
金莲                            13.287712379549449
--------------------------------------------------
如雪                            13.287712379549449
--------------------------------------------------
古树森                          13.287712379549449
--------------------------------------------------
层厚                            13.287712379549449
--------------------------------------------------
迷本                            13.287712379549449
--------------------------------------------------
七样                            13.287712379549449
--------------------------------------------------
遥长                            13.287712379549449
--------------------------------------------------
剥得                            13.287712379549449
--------------------------------------------------
牛蜢                            13.287712379549449
--------------------------------------------------
化顿                            13.287712379549449
--------------------------------------------------
盘丝岭                          13.287712379549449
--------------------------------------------------
千个                            13.287712379549449
--------------------------------------------------
七套                            13.287712379549449
--------------------------------------------------
气球                            13.287712379549449
--------------------------------------------------
此泉                            13.287712379549449
--------------------------------------------------
玉体                            13.287712379549449
--------------------------------------------------
婆儿                            13.287712379549449
--------------------------------------------------
第七十二回                      13.287712379549449
--------------------------------------------------
汤泉                            13.287712379549449
--------------------------------------------------
女怪                            12.176681067160704
--------------------------------------------------
佳人                            12.176681067160704
--------------------------------------------------
茅屋                            12.176681067160704
--------------------------------------------------
八戒                            11.562565014319137
--------------------------------------------------
洗澡                            11.509503803151361
--------------------------------------------------
钉住                            11.287712379549449
--------------------------------------------------
跌得                            11.287712379549449
--------------------------------------------------
老鹰                            11.287712379549449
--------------------------------------------------
洗洗                            11.287712379549449
--------------------------------------------------
路边                            11.287712379549449
--------------------------------------------------
七情                            11.287712379549449
--------------------------------------------------
飘扬                            11.287712379549449
--------------------------------------------------
退步                            11.287712379549449
--------------------------------------------------
百个                            11.287712379549449
--------------------------------------------------
木香                            11.287712379549449
--------------------------------------------------
长老                            10.706634659931115
--------------------------------------------------
露出                            10.421793564997238
--------------------------------------------------
化缘                            10.117787378107137
--------------------------------------------------
绊脚                            10.117787378107137
--------------------------------------------------
打断                            10.117787378107137
--------------------------------------------------
忘形                            10.117787378107137
--------------------------------------------------
女流                            10.117787378107137
--------------------------------------------------
化斋                            9.895724753329649
--------------------------------------------------
算计                            9.583714705324557
--------------------------------------------------
水里                            9.553273713412283
--------------------------------------------------
扶师父                          9.287712379549449
--------------------------------------------------
山泉                            9.287712379549449
--------------------------------------------------
赤条条                          9.287712379549449
--------------------------------------------------
古书                            9.287712379549449
--------------------------------------------------
衣服                                   9.0
--------------------------------------------------
站立                            8.643856189774725
--------------------------------------------------
断根                            8.643856189774725
--------------------------------------------------
山岭                            8.643856189774725
--------------------------------------------------
地脉                            8.643856189774725
--------------------------------------------------
洗浴                            8.643856189774725
--------------------------------------------------
推开                            8.509503803151361
--------------------------------------------------
下水                            8.509503803151361
--------------------------------------------------
过桥                            8.117787378107137
--------------------------------------------------
桃李                            8.117787378107137
--------------------------------------------------
脊背                            8.117787378107137
--------------------------------------------------
蛾眉                            7.673002535434241
--------------------------------------------------
蜻蜓                            7.673002535434241
--------------------------------------------------
肚皮                            7.673002535434241
--------------------------------------------------
那怪                            7.547331773069059
--------------------------------------------------
名头                            7.28771237954945
--------------------------------------------------
解下                            6.947862376664824
--------------------------------------------------
不满                            6.947862376664824
--------------------------------------------------
主张                            6.947862376664824
--------------------------------------------------
洞里                            6.792269854562382
--------------------------------------------------
儿子                            6.758639517551398
--------------------------------------------------
老儿                            6.754616300987894
--------------------------------------------------
十个                            6.643856189774724
--------------------------------------------------
斋僧                            6.643856189774724
--------------------------------------------------
地积                            6.643856189774724
--------------------------------------------------
跌恼                            6.643856189774724
--------------------------------------------------
疑粉                            6.643856189774724
--------------------------------------------------
动棍                            6.643856189774724
--------------------------------------------------
开脚                            6.643856189774724
--------------------------------------------------
九处                            6.643856189774724
--------------------------------------------------
横远                            6.643856189774724
--------------------------------------------------
铺里                            6.643856189774724
--------------------------------------------------

效果还算不错，最起码看过西游记的，看了前十个词基本上就知道这一章是讲什么的，这只是一个实验性质的程序，实际情况中一般文档数量会不断增加，所以需要不断更新idf.pkl文件，同时停用词处理还是有必要的。

附：交叉熵的相关定义

在信息论中，基于相同事件测度的两个概率分布 $p$和$q$的交叉熵是指，当基于一个“非自然”（相对于“真实”分布$p$而言）的概率分布$q$进行编码时，在事件集合中唯一标识一个事件所需要的平均比特数（bit）。

基于概率分布$p$和$q$的交叉熵定义为：

$$H(p,q)= {E_{p}[-\log q]=H(p)+D_{\mathrm {KL} }(p\|q),\!}$$

其中 $H(p)$是 $p$的熵，$D_{\mathrm {KL} }(p\|q)$是从$p$到$q$的KL散度(也被称为p相对于q的相对熵)。

对于离散分布$p$和$q$，这意味着：

$${ H(p,q)=-\sum _{x}p(x)\,\log q(x).\!}$$

参考文献：

An information-theoretic perspective of tf–idf measures, Akiko Aizawa