VSM、TF-IDF与LSA

未分类

---

向量空间模型算法（VSM）

文本分析中有一种较为经典的方法就是向量空间模型算法（VSM）。VSM的基本思想是把文档简化为以特征项（关键词）的权重为分量的$N$维向量表示。这个模型隶属于词袋模型（bag of words model）,即文本（段落或文档）被看作是无序的词汇集合，忽略语法甚至是单词的顺序。VSM模型的缺点在于关键词之间的线性无关的假说前提，这个前提造成VSM模型无法进行语义相关的判断。但VSM使用向量来表示文本，简化了文本中的关键词之间的复杂关系，文档用十分简单的向量表示，使得模型具备可算性。p.s. 值得注意的是，并不是文档所有的单词都会被纳入到$N$维向量中，且关键词是提前选择出来的（还需要一定方法技巧）。

用$D$(document)表示文档，特征项（Term，用T表示）指出现在文档$D$中且能够代表该文档内容的基本语言单位，主要是由词或者短语构成，文档可以用特征项集表示为$D（T_1，T_2，…，T_N）$，其中$T_k$是特征项，要求满足$1\leq k\leq N$。假设一篇文档中有a、b、c、d四个特征项，那么这篇文档就可以表示为$D（a，b，c，d）$。对于其他要与之比较的文档，也将遵循这个特征项顺序。

对含有$N$个特征项的文档而言，通常会给每个特征项赋予一定权重以表示其重要程度，即$D（T_1，W_1;T_2，W_2;…，T_N，W_N）$。由于特征项的长度与顺序是固定的，我们可以将此简记为

$$D（W_1，W_2，…，W_N）$$
我们把它叫做文档$D$的权值向量表示，其中$W_k$是$T_k$的权重。

这个时候我们实际上就可使用之前熟悉的度量距离的方式来衡量两个向量（即两篇不同文档）之间的相似度了。但是，我们在这里想要着重指出权重$W_k$的具体得出方法，由此引出了TF-IDF。

TF-IDF

TF(Term Frequency)表示的是关键词（特征项）词频，对于在某一特定文档$d_j$的关键词$t_i$来说，它的词频可以表示为：

$$\mathrm{tf}_{ij} = \frac{n_{ij}}{m_j}$$
其中$m_j$为文档$d_j$中的词数，$n_{ij}$为关键词$t_i$出现的词数。

而IDF（Inverse Document Frequency）表示的是逆向文本频率，用于衡量关键词$t_i$普遍重要性的一个指标:

$$\mathrm{idf}_i = log(\frac{|D|}{|d:d \ni t_i|})$$
其中$|D|$为总文档数，$|d:d \ni t_i|$为关键词$t_i$出现过的文档数。

然后，

$$\mathrm{tfidf}_{ij} = \mathrm{tf}_{ij}·\mathrm{idf}_i$$
某一特定文档内的高关键词（特征项）频率，以及该关键词（特征项）在整个文档集合中的低文档频率，可以产生出高权重的TF-IDF。TF-IDF可以作为VSM算法中各个关键词的权重，作为权重向量的单元，计算各个文档间的相似程度。文档相似度通常使用余弦相似度。

LSA算法

之前已经讲过，VSM将各关键词之间假设为线性无关的这个前提造成VSM模型无法进行语义相关的判断，没有能力处理更复杂的一词多义、一义多词问题。而潜在语义分析（LatentSemanticAnaiysis，LSA）是一种用于自动地实现知识提取和表示的理论和方法，它通过对大量的文本集进行统计分析，从中提取出上下文的语义。在技术上，与向量空间模型类型(VSM)类似，都是采用空间向量表示文本，但通过奇异值矩阵分解（SVD）等处理，一定程度上解决了一次多义、一义多词的影响，提高了后续处理的精度。当然，LSA相比于后续的pLSA、LDA而言，效果并没有后两者那么好。但是，这是事物一步一步前进的脚步，需要了解之前的历程，才能够更好地理解后来的算法。

之前专门写过一篇关于矩阵奇异值分解的短文，详情请戳我。为了将SVD应用到文本分析中，我们需要构建一个关键词-文档（term-document）矩阵。此矩阵的行表示的是关键词，列表示的是文档。如果将每一列看成是一个关于文档的向量，那么可以看出来此处的文档向量和VSM中的文档向量还是有区别的。VSM中文档向量中的数对应着相应关键词的权重，而LSA中仅仅使用‘0’或‘1’来考察该文档是否包含该关键词。

---以下部分来源自https://www.zybuluo.com/Hederahelix/note/102857

比如有2000个文档，包含7000个关键词，LSA使用一个维度为100的向量空间（潜在语义空间）将文档和词项表示到该空间，进而在该空间进行信息检索。而将文档表示到此空间的过程就是SVD奇异值分解和降维的过程。降维是LSA分析中最重要的一步，通过降维，去除了文档中的“噪音”，也就是无关信息（比如词的误用或不相关的词偶尔出现在一起），语义结构逐渐呈现。相比传统向量空间，潜在语义空间的维度更小，语义关系更明确。因此将文档和词语都在潜在语义空间表示，我们就能计算Document-Document，Document-Term，Term-Term的相似度。

LSA的步骤如下：
1. 分析文档集合，建立Term-Document矩阵。
2. 对Term-Document矩阵进行奇异值分解。
3. 对SVD分解后的矩阵进行降维，保留前$k$个特征值，后面$r−k$个置零，也就是低阶近似。
4. 使用降维后的矩阵构建潜在语义空间，或重建Term-Document矩阵。新得到的Term-Document矩阵就是我们经过LSA模型提取低维隐含语义空间。该空间中，每个奇异值对应的是每个“语义”维度的权重，我们刚才将不太重要的权重置为零，只保留最重要的维度信息，因而可以得到文档的一种更优表达形式。

假设我们有五篇文档和一个查询：
$d1$ = Romeo and Juliet.
$d2$= Juliet: O happy dagger!
$d3$ = Romeo died by dagger.
$d4$ = "Live free or die", that’s the New-Hampshire’s motto.
$d5$ = Did you know, New-Hampshire is in New-England.
$q$ = dies, dagger.
很明显当我们查询dies, dagger的时候，$d3$应该是最相关的，因为在$d3$中同时出现dies, dagger，$d2$和$d4$各自包含一个单词紧随其后。但是$d1$和$d5$该怎么排列？我们都知道$d1$应该在$d5$之前，但是机器怎么识别呢？解决方法正是LSA，在这个例子中，$d1$中的Romeo和Juliet分别在$d2$和$d3$和单词$dagger$有关联，而单词$dagger$也是同理，对于$d1$和$d5$分别通过Romeo和New-Hampshire与dagger相联系。下面我们会通过更正式的方式来表达上述过程。

假设$A$是Term-Document矩阵，那么$A$的每列对应一篇文章，每行是一个单词。则$A$矩阵看上去是如下的样子：

\	d1	d2	d3	d4	d5
romeo	1	0	1	0	0
juliet	1	1	0	0	0
happy	0	1	0	0	0
dagger	0	1	1	0	0
live	0	0	0	1	0
die	0	0	1	1	0
free	0	0	0	1	0
new hampshire	0	0	0	1	1

很显然$B=A^TA$是Document-Document矩阵，如果文档i和j有b个相同的单词，则$B[i,j]=b$。另一方面$C=AA^T$是Term-Term矩阵，如果单词i和j同时出现在一篇文档的频数是c，则$C[i,j]=c$。很明显，矩阵B和C都是对称矩阵。我们对A做SVD分解。

$$A=U\Sigma V^T$$

其中$U$是由矩阵$B$的特征向量构成，$V$是由矩阵$C$的特征向量构成，$\Sigma$是由矩阵B的特征值的平方根构成的对角矩阵。

$$\Sigma = \begin{bmatrix} 2.285 & 0 & 0 & 0 & 0 \\ 0 & 2.201& 0 & 0 & 0 \\ 0 & 0 & 1.361 & 0 & 0 \\ 0 & 0 & 0 & 1.187 & 0 \\ 0 & 0 & 0 & 0 & 0.797 \end{bmatrix}$$
我们只保留$\Sigma$前$K$个特征值，其余替换成0形成新的矩阵$\Sigma_k$。对矩阵$U$和$V$也只保留对于$K$项。然后计算“去噪”后的矩阵$A_k$。
$$A_k=U_k\Sigma_kV^T_k$$
因此，Term-Term与Document-Document在潜在语义空间的相关性矩阵可以表示为：
$$A_kA^T_k = (U_k\Sigma_kV^T_k)(U_k\Sigma_kV^T_k)^T = U_k\Sigma_kV^T_kV_k\Sigma_k^TU_k^T = U_k\Sigma_k\Sigma_k^TU_k^T \\ A^T_kA_k = (U_k\Sigma_kV^T_k)^T(U_k\Sigma_kV^T_k) = V_k\Sigma_k^TU_k^TU_k\Sigma_kV^T_k = V_k\Sigma_k^T\Sigma_kV^T_k$$

因此我们可以把$U_k\Sigma_k$矩阵的行看作是term在潜在语义空间的坐标。同理我们认为$V_k\Sigma^T_k$的行表示了文档的坐标。
回到之前例子中，我们只取前$k=2$个特征值，则:

$$\Sigma_2 = \begin{bmatrix} 2.285 & 0 \\ 0 & 2.201 \\ \end{bmatrix} \\ $$
$$\Sigma_2 = \begin{bmatrix} 0.396 & 0.280 \\ 0.314 & 0.450 \\ 0.178 & 0.269 \\ 0.438 & 0.369 \\ 0.264 & 0.346 \\ 0.524 & 0.246 \\ 0.264 & 0.346 \\ 0.326 & 0.460 \\ \end{bmatrix}$$
$$V_2^T = \begin{bmatrix} 0.311 & 0.407 & 0.594 & 0.603 & 0.143\\ 0.363 & 0.541 & 0.200 & 0.695 & 0.229\\ \end{bmatrix} \\ $$
我们知道$U_2\Sigma_2$的行代表单词在潜在语义空间的坐标，同理$V_2\Sigma^T_2$表示文档的坐标。则：
$$romeo=\begin{bmatrix} 0.905\\0.563\end{bmatrix}, juliet=\begin{bmatrix} 0.717\\0.905\end{bmatrix}, happy=\begin{bmatrix} 0.407\\0.541\end{bmatrix}, dagger=\begin{bmatrix} 1.197\\0.494\end{bmatrix},\\ live=\begin{bmatrix} 0.603\\0.695\end{bmatrix}, die=\begin{bmatrix} 1.001\\0.742\end{bmatrix}, free=\begin{bmatrix} 0.603\\0.695\end{bmatrix}, new hampshire=\begin{bmatrix} 0.745\\0.925\end{bmatrix},\\ $$
和
$$d1=\begin{bmatrix} 0.711\\0.730\end{bmatrix}, d2=\begin{bmatrix} 0.930\\1.087\end{bmatrix}, d3=\begin{bmatrix} 1.357\\0.402\end{bmatrix}, d4=\begin{bmatrix} 1.378\\1.397\end{bmatrix}, d5=\begin{bmatrix} 0.327\\0.460\end{bmatrix}$$
因此查询die, dagger也可以表示成两个质心（的中点）：
$$q = \frac{\begin{bmatrix} 1.001\\0.742\end{bmatrix}+\begin{bmatrix} 1.197\\0.494\end{bmatrix}}{2} = \begin{bmatrix} 1.099\\0.618\end{bmatrix}$$
然后我们可以通过查询该中点和每篇文档的距离(余弦距离)：
$$\frac{d_i q}{|d_i||q|}$$
进而可以发现有用信息。下图就是所有文档、词语和查询在潜在语义空间的坐标：

对于新文档，如何计算它在潜在语义空间的坐标呢？事实上，不需要重新进行SVD分解，由：

$$A = U\Sigma V^T \\ \Rightarrow U^TA = U^TU\Sigma V^T\\ \Rightarrow \Sigma^{-1}U^TA = V^T \\ \Rightarrow V = A^TU\Sigma^{-1}$$
可以知道，新来了一个文档，将上面最后一个式子A取为一列的向量（即表示新文档），而矩阵$U与\Sigma^{-1}$都不做改变，那么可求得相对应的向量$V$（此时的$V$也只是一个向量，表示其潜在语义空间的坐标）。