TF-IDF简介

May 26, 2017 zr9558 Leave a comment

tf-idf，英语的全称叫做 term frequency-inverse document frequency，它是文本挖掘领域的基本技术之一。tf-idf 是一种统计的方法，用来评估一个词语在一份语料库中对于其中一份文件的重要程度。词语的重要性会随着它在该文件中出现的次数而增加，但是也会同时随着它在语料库中其他文件出现的次数而减少。

假设一份语料集合是 D，那么语料集中文件的个数就是 N=|D|，第 j 份文件用 $d_{j}$ 来表示，其中 $1\leq j\leq |D|$ 。同时假设在语料库中出现的所有词语的集合是 $\{t_{i},1\leq i\leq T\}$ 。

（一）词频的定义以及基本性质

从直觉上来说，如果某一个词语在一份文件中重复出现了多次，那么这个词语在这份文件中的重要性就会显著增加。在给定的一份文件 $d_{j}$ 里面，词频（term frequency）指的是语料库中的一个词语 $t_{i}$ 在该文件中出现的频率。词频通常定义为：

$tf(t_{i},d_{j}) = \frac{n_{i,j}}{\sum_{k}n_{k,j}},$

其中， $n_{i,j}$ 指的是词语 $t_{i}$ 在文件 $d_{j}$ 中的出现次数，而分母 $\sum_{k}n_{k,j}$ 则是文件 $d_{j}$ 中所有的词语的出现次数之和。

备注：如果某个词语在该文件中没有出现过，那么该词语在这个文件中的词频就是零。

词频除了以上的基本定义之外，还有其他的各种形式：

二值表示： $tf(t_{i},d_{j}) = \mathcal{I}(t_{i}\in d_{j})$ ，其中 $\mathcal{I}$ 是指示函数，

计数表示： $tf(t_{i},d_{j}) = n_{i,j},$

概率表示： $tf(t_{i},d_{j}) = n_{i,j}/\sum_{k}n_{k,j},$

对数表示： $tf(t_{i},d_{j}) = 1$ + $\log(n_{i,j}),$

double normalization K表示： $tf(t_{i},d_{j}) = K$ + $(1-K)n_{i,j}/\max_{k}n_{k,j}$ ，其中 $K \in (0,1)$ ，或者 K 直接取值为 0.5 即可。

（二）逆向文件频率的定义以及基本性质

除了词频之外，还有逆向文件频率（inverse document frequency）这个概念，它是用来描述一个词语普遍性的指标。通常来说，如果某个词语在绝大多数甚至所有的文件中都出现过，例如一些常见的停用词，那么该词语的重要性就要降低，因为它在语料集中十分普遍。因此，逆向文件频率的定义通常就是：

$idf(t_{i},D) = \log(\frac{|D|}{|\{d\in D: t_{i}\in d\}|}),$

其中，N=|D| 是语料库中文件的总数， $|\{d\in D: t_{i}\in d\}|$ 表示的是在语料库中包含词语 $t_{i}$ 的文件个数，也就是说 $n_{i,j}\neq 0$ 的文件个数。

备注：如果该词语不在语料库中，会导致分母是零，因此在一般情况下会使用 $1$ + $|\{d\in D: t_{i}\in d\}|$ 。

逆向文件频率除了以上的基本定义之外，还有以下几种常见的计算方法：假设 $n_{i} = |\{d\in D: t_{i}\in d\}|$ ，

唯一性表示：1

逆向文件频率： $\log(\frac{|D|}{n_{i}})=-\log(\frac{n_{i}}{|D|})=-log(p(t_{i}|d)),$

光滑的逆向文件频率： $\log(1$ + $\frac{|D|}{n_{i}}),$

概率化逆向文件频率： $\log(\frac{|D|-n_{i}}{n_{i}}).$

（三）TF-IDF 的定义和基本性质

那么，为了描述词语 $t_{i}$ 在文件 $d_{j}$ 中的重要性，tf-idf 的定义就可以写成：

$tfidf(t_{i},d_{j})=tf(t_{i},d_{j})\times idf(t_{i},D).$

通常来说，tf-idf 倾向于过滤掉常见的词语，而保留重要的词语。

下面：我们来通过一个案例来看 tf-idf 是如何进行计算的。

假设语料集中有两份文档，分别是 Document 1 和 Document 2，出现的词语个数如下表示：

Example

通过这幅图可以直接计算出 “this” 这个词语在各个文件中的重要性程度：

$tf("this",d_{1}) = 1/5$ ， $tf("this, d_{2}) = 1/7$ ， $idf("this") = 0$ ，

因此可以得到 $tdidf("this",d_{1}) = tfidf("this,d_{2}) = 0$ 。原因是 “this” 这个词语在两个文件中都出现了，是一个常见的词语。

$tf("example",d_{1}) = 0$ ， $tf("example", d_{2}) = 3/7$ , $idf("example") = \log(2)$ ，

因此可以得到 $tfidf("example",d_{1}) = 0$ ， $tfidf("example",d_{2}) = 3\log(2)/7$ 。原因是 “example” 这个词语在第一份文件中没有出现，第二份文件中出现了。

（四）向量空间模型

空间向量模型是把一个文件表示成向量的代数模型，文件与文件之间的相似度使用向量之间的角度来进行比较。

假设语料库中所有词语的个数是 T，第 j 个文件是 $d_{j}$ ，查询是 q，它们用向量表示就是：

$d_{j} = (w_{1,j},w_{2,j},...,w_{T,j})\in \mathbb{R}^{T}$

$q = (w_{1,q},w_{2,q},...,w_{T,q})\in \mathbb{R}^{T}$

每个维度对应了一个相应的词语。如果该词语没有出现在该文件中，那么向量中所对应的位置就是零。在这里，比较经典的一种做法就是选择 tf-idf 权重，也就是说第 j 个文件的向量是按照如下规则选择的， $w_{i,j}=tfidf(t_{i},d_{j}), w_{i,q}=tfidf(t_{i},q), 1\leq i\leq T$ 。

那么文件 $d_{j}$ 和查询 q 之间的相似度就可以定义为：

$sim(d_{j},q)=\frac{d_{j}\cdot q}{||d_{j}||\cdot||q||}.$

其中分子指的是两个向量的内积，分母指的是两个向量的欧几里得范数的乘积。

备注：在词组计数模型（Term Count Model）中，也可以简单的考虑词语出现的次数即可： $w_{i,j}=tf(t_{i},d_{j})$ 。

数据挖掘与机器学习

聚类算法（二）

May 16, 2017 zr9558 Leave a comment

聚类是一种无监督学习（无监督学习是指事先并不知道要寻找的内容，没有固定的目标变量）的算法，它将相似的一批对象划归到一个簇，簇里面的对象越相似，聚类的效果越好。聚类的目标是在保持簇数目不变的情况下提高簇的质量。给定一个 m 个对象的集合。把这 m 个对象划分到 K 个区域，每个对象只属于一个区域。所遵守的一般准则是：同一个簇的对象尽可能的相互接近或者相关，而不同簇的对象尽可能的区分开。之前已经介绍过 KMeans 算法与 bisecting KMeans 算法，在这里介绍一个流式的聚类算法。

流式聚类算法（One Pass Cluster Algorithm）

既然是流式的聚类算法，那么每个数据只能够进行一次聚类的操作。有一个简单的思路就是对于每一个未知的新样本，如果它与某个类足够相似，那么就把这个未知的新样本加入这个类；否则就自成为一个新的类。如下图所示：

SinglePass 聚类原理

基于以上思路，我们可以设计一个流式的聚类算法。假设 dataMat 是一个 m 行 n 列的一个矩阵，每一行代表一个向量，n 代表向量的维度。i.e. 在 n 维欧几里德空间里面有 m 个点需要进行聚类。

流式聚类的算法细节：

参数的设定：

$K$ 表示在聚类的过程中允许形成的簇的最大个数；

$D$ 表示距离的阀值，在这里两个点之间的距离可以使用 $L^{1}, L^{2}, L^{\infty}$ 范数；

聚簇的质心定义为该类中所有点的平均值。i.e. 如果该类中的点是 $A[0],A[1],\cdot\cdot\cdot,A[n-1]$ ，那么质心就是 $\sum_{i=0}^{n-1}A[i]/n$ ；

第 j 个聚簇中元素个数用 $num[j]$ 表示。

方法：

Step 1：对于 $dataMat[0]$ 而言，自成一类。i.e. 质心就是它本身 $C[0]=dataMat[0]$ ，该聚簇的元素个数就是 $num[0]=1$ ，当前所有簇的个数是 $K^{'}=1$ 。

Step 2: 对于每一个 $1\leq i\leq m-1$ ，进行如下的循环操作：

假设当前有 $K^{'}$ 个簇，第 j 个簇的质心是 $C[j]$ ，第 j 个簇的元素个数是 $num[j]$ ，其中 $0\leq j\leq K^{'}-1$ 。

计算 $d= \min_{0\leq j\leq K^{'}-1}Distance(dataMat[i],C[j])$ ，其中的 Distance 可以是欧几里德空间的 $L^{1},L^{2},L^{\infty}$ 范数，对应的下标是 $j^{'}$ 。i.e. $j'=argmin_{0\leq j\leq K'-1}Distance(dataMat[i],C[j])$ 。

（i）如果当前 $K'=K$ 或者 $d\leq D$ ，则把 $dataMat[i]$ 加入到第 $j^{'}$ 个聚簇。也就是说：

质心更新为 $C[j'] \leftarrow (C[j']*num[j]$ + $dataMat[i])/(num[j]$ + $1)$ ，

元素的个数更新为 $num[j'] \leftarrow num[j']$ + $1$ 。

（ii）否则， $dataMat[i]$ 需要自成一类。i.e. $K^{'} \leftarrow K^{'}$ + $1$ ， $num[K'-1]=1$ ， $C[K'-1]=dataMat[i]$ 。

注：

（1）数据的先后顺序对聚类的效果有一定的影响。

（2）该算法的时间复杂度与簇的个数是相关的，通常来说，如果形成的簇越多，对于一个新的样本与质心的比较次数就会越多。

（3）如果设置簇的最大个数是一个比较小的数字的时候，那么对于一个新的样本，它需要比较的次数就会大量减少。如果最小距离小于 D 或者目前已经达到最大簇的个数的话，那么把新的样本放入某个类。此时，可能会出现某个类由于这个新的样本导致质心偏移的情况。如果设置 $K$ 很大，那么计算的时间复杂度就会增加。因此，在保证计算实时性的时候，需要考虑到 $K$ 的设置问题。