TF-IDF简介

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/5tf("this, d_{2}) = 1/7idf("this") = 0

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

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

因此可以得到 tfidf("example",d_{1}) = 0tfidf("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})

 

Advertisements

聚类算法(二)

聚类是一种无监督学习(无监督学习是指事先并不知道要寻找的内容,没有固定的目标变量)的算法,它将相似的一批对象划归到一个簇,簇里面的对象越相似,聚类的效果越好。聚类的目标是在保持簇数目不变的情况下提高簇的质量。给定一个 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^{'} + 1num[K'-1]=1C[K'-1]=dataMat[i]

注:

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

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

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

效果展示:

使用一批二维数据集合,进行流式聚类算法可以得到下图:’+’ 表示的是质心的位置,其余就是数据点的位置。通过选择不同的距离阈值 D,就可以得到不同的聚类情况。其中 ‘+’ 表示该簇质心的位置,蓝色的点表示数据点。如下图所示:

流式聚类算法1流式聚类算法2

流式聚类算法3