TF/IDF算法(转载)

—— 一直说TF－IDF，终于开始做真正的TF－IDF。

TF/IDF（term frequency/inverse document frequency) 的概念被公认为信息检索中最重要的发明。

一。TF/IDF描述单个term与特定document的相关性

TF(Term Frequency): 表示一个term与某个document的相关性。
公式为这个term在document中出现的次数除以该document中所有term出现的总次数.

IDF（Inverse Document Frequency）表示一个term表示document的主题的权重大小。主要是通过包含了该term的docuement的数量和docuement set的总数量来比较的。出现的次数越多，权重越小。
公式是log(D/Dt) D是docuemnt set的总数量， Dt是包含了该term的document的总数。

这样，根据关键字k1,k2,k3进行搜索结果的相关性就变成TF1*IDF1 + TF2*IDF2 + TF3*IDF3。比如document1的term总量为1000，k1,k2,k3在document1出现的次数是100，200，50。包含了 k1, k2, k3的docuement总量分别是
1000， 10000，5000。document set的总量为10000。
TF1 = 100/1000 = 0.1
TF2 = 200/1000 = 0.2
TF3 = 50/1000 = 0.05
IDF1 = log(10000/1000) = log(10) = 2.3
IDF2 = log(10000/100000) = log(1) = 0;
IDF3 = log(10000/5000) = log(2) = 0.69
这样关键字k1,k2,k3与docuement1的相关性= 0.1*2.3 + 0.2*0 + 0.05*0.69 = 0.2645
其中k1比k3的比重在document1要大，k2的比重是0.

TF/IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵（Kullback-Leibler Divergence).

二。用TF/IDF来描述document的相似性。
假如document1和document2的term的TF/IDF分别是t11，t12,t13,…t1n和t21,t22,t23,…,t2n.他们之间的相似性可以用余弦定理来表示。则：
cos(d1,d2) = d1和d2的内积/(d1的长度*d2的长度) = (t11*t21 + t12*t22 + t13*t23 + … + t1n*t2n)/(|d1|*|d2|).
d1 = sqrt(t11*t11 + t12*t12 + t13*t13 + … + t1n*t1n);
夹角越大，相似性越大。为1则表示d1和d2一致。

在今日我们可以从网络上吸收大量资讯，有时候一堆文章看不完。如果我们想要吸收资讯，时间却又不够的时候，使用电脑帮我们过滤资讯，或是用电脑帮我们做个总整理，是个方法。如果今天手中有一篇文章，我们想要用电脑帮我们找出这篇文章最重要的关键字，要怎麽做呢？在资讯检索 (IR: Information Retrieval)领域里面，有个基础的方法，入门必学的方法，就是使用 TF 和 IDF (TF: Term Frequency, IDF: Inverse Document Frequency)。使用这两个估计值，可以让电脑具有计算重要关键字的能力，进而节省我们的时间。
接下来让我们看看，TF 和 IDF 个是甚麽东西呢？TF 全名是Term Frequency，也就是某个关键字出现的次数，譬如说某篇文章里面，「电脑」这个词出现很多次，或是「使用者需求」这个词出现很多次，那麽这些词句的出现频率，就会很高。一篇文章中出现很多次的词句，必定有其重要性。譬如说一篇论述「人工智慧」的文章，「人工智慧」这个词句再文章中出现的频率也一定很高。然而为甚麽除了 TF (Term Frequency) 以外，还要有 IDF (Inverse Document Frequency) 呢？
让我们先想想，如果单使用某个字词出现的频率，来判断一篇文章最重要的关键字，会有甚麽困难。首先，我们会遇到一些常用字词，出现的频率也很高，会和重要字词出现的频率一样高，让电脑因此无法分辨出，哪些是常用字词，那些是重要字词。如果就英文来说，有个规则是语言学家 (linguist) 归纳出来的规则，叫做 Zipf’s Law

引述中文维基百科的一段介绍如下：

从根本上讲, 齐夫定律 可以表述为, 在自然语言的 语素库 里, 一个单词出现的频率与它在频率表里的排名成 反比. 所以, 频率最高的单词出现的频率大约是出现频率第二位的单词的 2 倍，而出现频率第二位的单词则是出现频率第四位的单词的2倍。这个定律被作为任何与 power law probability distributions 有关的事物的参考。 这个 “定律” 是 Harvard linguist George Kingsley Zipf (IPA [z?f])发表的。
比如, 在 Brown 语库， “the” 是最常见的单词，它在这个语库中出现了大约 7 %（10 万单词中出现 69971 次）。正如齐夫定律中所描述的一样，出现次数为第二位的单词 “of” 占了整个语库中的 3.5% (36411次), 之後的是”and” (28852次). 仅仅 135 但此项就占了 Brown 语库的一半。

所以我们现在知道问题在哪边了。如果只用词句出现的频率来判断某一篇文章里面最重要的关键字，我们可能会找到常用字，而不是最重要的字，像是英文里面的 “the”、”a”、”it”，都是常常出现的字，但是通常一篇文章里面最重要的字不是这些字，即使那些重要的字出现的频率也很高。
这个时候我们要怎麽办呢？IDF 在这个时候就帮上忙了。在了解 IDF 之前，我们先了解 DF 是甚麽。DF 就是Document Frequency，也就是说，如果今天我们手中有固定 N 篇文章，某个关键字的 Document Frquency (DF)，就是说这个关键字在 N 篇文章里面出现了几次。Inverse Document Frequency (IDF) 则是把 DF 取倒数，如此一来，一个数字乘以 IDF，就等於是除以 DF 的意思。
有了 TF 和 IDF 以後，我们就可以计算 TF 乘上 IDF，对每一个关键字都算出一个分数。这个分数的高低，就代表了这个关键字在某篇文章中的重要程度。为甚麽我们说这样子可以找出重要的字，而不是常出现的字呢？因为 TF 会把某篇文章中，出现最多次的排在第一位，其次的排在第二位，以此类推。然而乘上 IDF 以後，也就是除以 DF，那些常常出现的字，像是英文中的 “the”、”a”、”it”，因为每一篇文章都会出现，所以 DF 就大。DF 大，取倒数之後的 IDF 就小，IDF 小，乘上 TF 以後，虽然”the”、”a”、”it”在某篇文章中出现的频率很高，但是因为 IDF 小，TF * IDF 一相乘，重要性就变低了，我们 (电脑程式) 就不会把这些常出现的字，误认为是重要的字了！
真正重要的字会得到甚麽样子的分数呢？如果这篇文章刚好在讲 AI，”AI” 出现很多次，因此 “AI” 在这篇文章里面的 TF 很高。然而我们电脑资料库里面的 N 篇文章，并不是每一篇都在讲 AI，也因此”AI”可能只有在 N 篇文章里面的某 3 篇文章出现，因此 DF 只有 3，IDF 变成 0.33，假设我们 N = 100 有 100 篇文章在资料库里面，其他常出现字像是 “the” 每一篇都出现，DF 就是 100，IDF 就是 0.01。所以 “AI” 的 IDF 会比 “the” 的 IDF 高，假设这篇文章中 “AI” 和 “the” 两个字出现的次数刚好一样，乘上 IDF 以後，”AI” 这个字的分数就比 “the” 这个字的分数来的高，电脑也就会判断 “AI” 是这篇文章重要的关键字，而 “the” 这个字并不是这篇文章的重要关键字。
所以经由 TF * IDF，我们可以计算某个关键字，在某篇文章里面的重要性。从这一个方向，我们可以计算一篇文章中重点的字有哪些，帮我们做一篇文章的总整理。从相反的方向，我们可以给定关键字，然後再每一篇文章里面为这个关键字计算一次 TF * IDF，然後比较哪一篇文章，这个关键字是最具重要性的，用这个方法找出和一个关键字最相关的文章。不管是从文章找出重点字词，或是由关键字找相关文章，TF * IDF 都是个基本且不错的方法。会写程式又还没?试过这个方法的读者，或许可以亲自试试看，不过可能要先自己准备文章资料库 (corpus)，或是从网际网路上面用网页撷取器 (crawler) 存几篇有兴趣的网页，然後把 HTML 标签清理乾净，剩下纯文字，就可以用这个方法来小试身手罗！
我们也可以比较一下人类和电脑的不同。电脑做数学数字的计算，或是执行固定的步骤 ，非常擅长，速度也很快。人类可以了解一个字的意思，读完一篇文章以後，了解了意思，之後要找这篇文章最重要的关键字，是从「意义」开始，回忆出或做出结 论，这篇文章重要的关键字是甚麽。
然而如果要电脑也遵照这个方向，先了解字的意义，再了解文章的意义，然後在做出结论，这篇文章的重要关键字，反而困难，因为要了解字的意义，电脑需要先有一个语意网路 (Semantic Network)，或是知识的分类关系树 (Ontology)，把字句依照语意分门别类，有如生物里面的「界门纲目科属种」一般的关系分类，才有办法了解一个字和其他字的关系。之後要了解一篇文章，又必须要了解一个句子，牵涉到自然语言处理 (NLP: Natural language Processing) 的问题，像是从句子里面找出主词、动词、和受词，以及补语，分辨出子句和主句，代名词的指称，以及前後文判断产生不同的剖析 (parsing)。了解完一句，才能了解整篇文章。

因此，TF * IDF 对於电脑来说，计算速度快，工程也不浩大，不用大型计算机就可以计算。这边也可以顺便提到 strong AI 和 weak AI 的关系。如果就工程的角度，TF * IDF 是个好方法，it works! 节省我们的时间，或是解决大问题中的一个小环节。然而 strong AI 在这边会提出「中文房间」(Chinese Room) 的论证，也就是说，电脑能够找出重要关键字，是否就代表电脑真的「知道」(understand) 关键字的意义呢？
中文房间 (Chinese Room) 简单地说，就是一个人关在房间里面，只留两个窗口，一个地方会送纸条出来，另一个地方会送纸条出去。房间里面有一本手册，里面写满对照表，记载者看到甚麽英文字，就应该输出甚麽中文字，以及一些指令的对照，譬如说窗口送一个指令说 COMBINE，就把两个中文字写在一起才送出去。接着我们在外面就开始送英文句子进去这个房间，另一个窗口就会有这句话的中文翻译跑出来。然而这个论证想要坦讨的就是，虽然这个房间看起来像是会把英文翻译成中文，但是在房间里面的那个操作人员并不懂中文，他指是按照指令，还有手册里面的对照表，机械式地动作，可是外面看起来像是这个房间会英翻中，因此这个房间应该懂得中文才对。
在这边我的看法是，也许就近程来看，我们只要有可以解决问题的解答就可以，不管电脑是否真的懂 (understand) 字的意义。然而长期来说，如果我们真的需要具有人类的智力的电脑出现，能够真的懂而不是行为上看起来懂，那麽就要仔细探讨中文房间这种论证。也许生物的方法，像是计算神经科学的方法，是一个方向。
我们可能又会问，神经元只有动作电位和静止两个状态，怎麽能了解意义？但是只有一个神经元，或许没办法了解意义，全部大脑的神经元交互作用，意义可能就因此被了解了！其中的奥妙，就是计算神经科学?试要解答的问题之一。有兴趣的读者也可以一起从人脑开始，解决 strong AI 的问题。或是有数学的高手，也许某一个数学理论，可以很漂亮地解决意义了解的问题也说不定，像是 manifolds，具有一个集合使用不同面向来观看的特性，同时具有 Global 和 Local 的性质，是个不错的候选选项。从这个方向去解决 strong AI 也是另一个可能性。总之，继续努力研究就是了