《数学之美》XI笔记——如何确定网页和查询的相关性

今天，由于商业搜索引擎已经有了大量的用户点击数据，因此对搜索相关性贡献最大的是根据用户常见搜索点击网页的结果得到的概率模型，但除了用户点击的数据以外，都可以归纳为一下四类：

• 完备的索引。如果没有索引，再好的搜索引擎也找不到
• 对网页质量的度量，如PageRank
• 用户偏好。
• 确定一个网页的相关性。

TF-IDF度量关键词权重

如短语“原子能的应用”，可分为“原子能”，“的”，“应用”

1.使用“单文本词频（TF，Term Frequency）”

如某网页共1000个词，其中“原子能”，“的”，“应用”分别出现2次，35次，5词。
那么词频分别是0.002，0.035，0.005
加和为0.042就是相关网页和查询“原子能的应用”的单文本词频

因此度量网页和查询的相关性就有了一个简单的做法，是直接使用各个关键词在网页中出现的总词频：
$TF_{1}+TF_{2}+\cdots+TF_{N}$

上面方法的问题：

• 上面关键词词频中“的”占的比重最大，但对于区分网页主题却没有任何帮助，这种词我们称为“停止词”（stop word）

• 关键词“原子能”比“应用”更能体现网页主题

所以基于上面的问题，我们需要给关键词设置权重，权重应该要区分出来哪些此对主题预测的能力强（停止词的权重为0）

权重“逆文本频率指数（IDF）”

IDF，Inverse Document Frequency
公式为$log(\frac{D}{D_{w}})$
其中D为全部网页数量，$D_{w}$位关键词在$D_{w}$个网页中出现过。

设D为10亿
如停止词“的”在10亿个网页中都出现过的话，权重就位0了
而原子能出现的较少，如果为200万，那么它的IDF就为8.96了

用IDF给TF加权得到TF-IDF公式：
$TF_{1}\times IDF_{1}+TF_{2}\times IDF_{2}+\cdots+TF_{N}\times IDF_{N}$

TF-IDF是公认的信息检索中最重要的发明

TF-IDF的信息论依据

根本上来讲，关键词的重要程度主要反映关键词携带信息量的大小：
$I(w)=-P(w)logP(w)$
$\ \ \ \ \ \ \ \ =-\frac{TF(w)}{N}log\frac{TF(w)}{N}=\frac{TF(w)}{N}log\frac{N}{TF(w)}$
其中，N为语料库的大小，TF(w)为语料库中关键词w出现的次数

忽略常数N得：
$I(w)=TF(w)log\frac{N}{TF(w)}$

上面公式存在的问题：
如果两个词出现的次数相同，一个在一篇文章中，一个比较分散，那么显然第一个词有更高的分辨率，权重应该更大

做出理想假设：

• 每个文献大小基本相同，均为M个词，即$M=\frac {N}{D}=\frac{\sum_{w}TF(w)}{D}$
• 一个关键词一旦在文献中出现，不论次数是多少，贡献都相同，这样一个词在一个文献中出现$c(w)=\frac{TF(w)}{D(w)}$次；$c(w)<M$

所以：
$I(w)=TF(w)log\frac{N}{TF(w)}=TF(w)log\frac{MD}{c(w)D(w)}$

$TF-IDF=TF(w)log(\frac{D}{D_{w}})$

可以看出TF-IDF和信息量之间的差异是$TF(w)log\frac{M}{c(w)}$，所以TF-IDF
公式可以整理为：
$TF-IDF=I(w)-TF(w)log\frac{M}{c(w)}$

一个词的信息量越多，TF-IDF越大，w命中的文献中w出现的平均次数越多，TF-IDF越大。这与信息论相符合。