從奇異值分解(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 能夠給出落在不同子空間的單詞序列，基本上這些單詞之間擁有較為緊密的語義聯系。其實這種用法本質上還是在利用降維做單詞相關度計算。