从奇异值分解(SVD)看潜在语义索引(LSI)

1. SVD 简介

SVD中文称为“奇异值分解”，是一种矩阵分解方法。其公式如下：

定理：设A为m*n阶复矩阵，则存在m阶矩阵U和n阶矩阵V，使得：

　　    A = U*S*V’　　   其中S=diag(σi,σ2,……,σr)，σi>0 (i=1,…,r)，r=rank(A)。

其中 A 矩阵是我们初始的特征矩阵，在文本挖掘中：A就是 t (term) 行 d (document) 列的矩阵，每列是一篇文章，每行是一个单词，每个单元格的当前单词在当前文章里的出现次数。 U 是一个 t 行 r 列 的矩阵， V 是一个 r 行 d 列 的矩阵， S 是一个 r 行 r 列的对角矩阵。这里 r 的大小是 A的秩。那么U和V中分别是A的奇异向量，而S是A的奇异值。AA'的正交单位特征向量组成U，特征值组成S'S，A'A的正交单位特征向量组成V，特征值（与AA'相同）组成SS'。( 关于秩是什么，特征值是什么，这个分解是怎么得到的，可以暂不去管）

注意，这个公式是等号，也就是等号左边完全等价于等号右边。换句话说我们只是把原来的A换了一种表示形式而已，并没有丢失任何信息。就好像 24 = 2 * 3 * 4 一样。 也正是因此，如果 LSI 直接使用 SVD 的话，不仅 r 是不可控的，而且 r 很可能很大以至于起不到降维效果，事实上这样做不仅没降维而且耗费了大量的运算时间。而 SVD 作为一种矩阵分解方法，也并非仅仅用在 LSI 中。Matlab中有直接的svd函数可以使用：[U,S,V] = svd(A) 

2. LSI 对 SVD 的使用

LSI 对 SVD 做了一点改变，就是对 S 的 r 个对角线元素进行了排序，并只保留前 k 个值 ( k < r )， 后 r - k 个置零。此时，可以证明等式右边是在最小二乘意义下对等式左边的最佳近似。事实上这个过程是把数据集的特征值（在SVD中用奇异值表征）按照重要性排列，降维的过程就是舍弃不重要的特征向量的过程，而剩下的特征向量张成空间为降维后的空间。

看到这里，我们能得到最重要的启发就是，LSI 是通过舍弃不重要的特征向量来达到降维效果的，而又由于特征向量是根据矩阵运算得出的，因此 LSI 在降维的过程中不仅丢失了信息，而且还改变了信息。降维后的数据集仅仅是对原数据集的一种近似而非等价形式。且降维幅度越大，与原信息的偏离就越大。

3. LSI 的适用性

1） 特征降维

LSI 本质上是把每个特征映射到了一个更低维的子空间（sub space)，所以用来做降维可以说是天造地设。在降维这块土地上还有另一位辛勤的耕耘者那就是TFIDF，TFIDF通过一个简单的公式（两个整数相乘）得到不同单词的重要程度，并取前k个最重要的单词，而丢弃其它单词，这里只有信息的丢失，并没有信息的改变。从执行效率上 TFIDF 远远高于 LSI，不过从效果上（至少在学术界）LSI 要优于TFIDF。

不过必须提醒的是，无论是上述哪一种降维方法，都会造成信息的偏差，进而影响后续分类/聚类的准确率。 降维是希望以可接受的效果损失下，大大提高运行效率和节省内存空间。然而能不降维的时候还是不要降维（比如你只有几千篇文档要处理，那样真的没有必要降维）

2）单词相关度计算

LSI 的结果通过简单变换就能得到不同单词之间的相关度( 0 ~ 1 之间的一个实数），相关度非常高的单词往往拥有相同的含义。不过不要被“潜在语义”的名称所迷惑，所谓的潜在语义只不过是统计意义上的相似，如果想得到同义词还是使用同义词词典靠谱。LSI 得到的近义词的特点是它们不一定是同义词（甚至词性都可能不同），但它们往往出现在同类情景下（比如“魔兽” 和 “dota”)。不过事实上直接使用LSI做单词相关度计算的并不多，一方面在于现在有一些灰常好用的同义词词典，另外相对无监督的学习大家还是更信任有监督的学习（分类）得到的结果。

3）聚类

直接用 LSI 聚类的情景我还没有见过，但使用该系列算法的后续变种 PLSI, LDA 进行聚类的的确有一些。其中LDA聚类还有些道理（因为它本身就假设了潜在topic的联合概率分布），用 LSI 进行聚类其实并不合适。本质上 LSI 在找特征子空间，而聚类方法要找的是实例分组。 LSI 虽然能得到看起来貌似是聚类的结果，但其意义不见得是聚类所想得到的。一个明显的例子就是，对于分布不平均的样本集（比如新闻类的文章有1000篇，而文学类的文章只有10篇）， LSI/PLSI 得到的往往是相对平均的结果(A类500篇，B类600篇)，这种情况下根本无法得到好的聚类结果。相对传统聚类方法k-means， LSI 系列算法不仅存在信息的偏差（丢失和改变），而且不能处理分布不均的样本集。

对于 LSI/PLSI 来说，聚类的意义不在于文档，而在于单词。所以对于聚类的一种变型用法是，当 k 设的足够大时，LSI/PLSI 能够给出落在不同子空间的单词序列，基本上这些单词之间拥有较为紧密的语义联系。其实这种用法本质上还是在利用降维做单词相关度计算。