文字特徵抽取的向量空間模型(VSM)和TF/IDF方法

文字特徵抽取

兩組小說,一組是愛情的,另一組是科幻的。我們能否用支援向量機訓練一個模型,用來識別小說型別呢?

這個並不容易。因為支援向量機這類機器學習演算法只能接受數學裡面的向量作為輸入。如果用它來做文字分類,必須先把文字轉化成向量才行。這就是涉及到一個很重要的話題,如何把文字轉化成向量?

把文字轉化成數學模型,是用數學方法處理文字的先決條件,這個過程稱為文字特徵抽取。向量作為一種基本的數學模型,是文字特徵抽取的一種常見方法。

文字的向量空間模型(VSM)

向量空間模型中將文字表達為一個向量,看作向量空間中的一個點。

這裡寫圖片描述

詞權重

一個句子中的每個詞在決定句子的含義時貢獻度並不相同,也就是每個詞的權重不同,例如下面的句子:

Most scientists think that butterflies use the position of the sun in the sky as a kind of compass
that allows them to determine which way is north.

  • 重要的詞:butterflies, monarchs, scientists, compass
  • 不重要的詞:most, think, kind, sky

詞權重就是反映每個詞的重要性的度量。如何計算權重?下面介紹註明的TF/IDF計算方法

詞頻(tf)

一個詞在一個句子中出現的次數越多,那麼這個詞在描述這個句子的含義方面貢獻度越大,可通過下面兩個式子中的一個來計算每個詞的詞權重:

T=tfdoc_length

T = \frac {tf}{doc\_length}

文件頻率(df)

文件頻數(Document Frequency, DF)是最為簡單的一種特徵選擇演算法,它指的是在整個資料集中有多少個文字包含這個單詞。在訓練文字集中對每個特徵計一算它的文件頻次,並且根據預先設定的闌值去除那些文件頻次特別低和特別高的特徵。文件頻次通過在訓練文件數量中計算線性近似複雜度來衡量巨大的文件集,計算複雜度較低,能夠適用於任何語料,因此是特徵降維的常用方法。

在訓練文字集中對每個特徵計算它的文件頻數,若該項的DF 值小於某個閾值則將其刪除,若其DF 值大於某個閾值也將其去掉。因為他們分別代表了“沒有代表性”和“沒有區分度”2 種極端的情況。DF 特徵選取使稀有詞要麼不含有用資訊,要麼太少而不足以對分類產生影響,要麼是噪音,所以可以刪去。DF 的優點在於計算量很小,而在實際運用中卻有很好的效果。缺點是稀有詞可能在某一類文字中並不稀有,也可能包含著重要的判斷資訊,簡單捨棄,可能影響分類器的精度。

文件頻數最大的優勢就是速度快,它的時間複雜度和文字數量成線性關係,所以非常適合於超大規模文字資料集的特徵選擇。不僅如此,文件頻數還非常地高效,在有監督的特徵選擇應用中當刪除90%單詞的時候其效能與資訊增益和x2 統計的效能還不相上下。DF 是最簡單的特徵項選取方法, 而且該方法的計算複雜度低, 能夠勝任大規模的分類任務。

但如果某一稀有詞條主要出現在某類訓練集中,卻能很好地反映類別的特徵,而因低於某個設定的閾值而濾除掉,這樣就會對分類精度有一定的影響。

逆文件頻率(idf)

通常來說,如果一個詞在越多的文件中出現過,那個這個詞對某一個文件的貢獻度應該就越小,也就是通過這個詞來區分文件的區分度越小,可以用逆文件頻率(idf)來度量這個概念。先定義另一個概念,文件頻率df,表示包含某個詞的文件的數目, N表示文件的總數量。逆文件頻率計算公式如下:

I=−log(dfN)

I=-log{(\frac{df}N)}

TF/IDF

TF/IDF(term frequency/inverse document frequency) 的概念被公認為資訊檢索中最重要的發明。在搜尋、文獻分類和其他相關領域有廣泛的應用。

假定一個文件就是資訊源,該文件包含 T1,T2,…,TnT_1,T_2,…,T_n 共 n 個詞彙,每個詞彙出現了 N1,N2,…,NnN_1, N_2,…,N_n 次,詞彙在文件集中出現的文件頻率(詞彙的發生概率)分別為 D1,D2,…,DnD_1, D_2,…,D_n,那麼傳輸一個這樣的文件需要多少編碼長度呢?

假設每個詞彙的出現相互獨立,並且不考慮出現的先後順序(即把文件看作bag of words,資訊檢索模型中常見)。因此由這些詞彙組成的文件的概率為:

P(X)=DN11DN22…DNnn

P(X)=D_1^{N_1}D_2^{N_2}…D_n^{N_n}

任意隨機事件的自資訊量定義為該事件發生概率的對數的負值,設事件X的概率為P(X),那麼其自資訊定義為

I(X)=−log(P(X))

I(X)=-log(P(X))

也可以理解為某個概率的事件進行編碼所需要的最小編碼長度。

那麼,對具有這種概率的事件進行編碼,需要的編碼長度為

−log(P(X))=−log(DN11DN22…DNnn)=−N1log(D1)−N2log(D2)−…−Nnlog(Dn)

\begin{aligned}
-log(P(X)) &= -log(D_1^{N_1}D_2^{N_2}…D_n^{N_n})\\
&= -N_1log(D_1) – N_2log(D_2) – … -N_nlog(D_n)
\end{aligned}

即這篇文件理論上能夠最大極限地被壓縮到 −log(P(X))-log(P(X)) 位元,並且數學上可以證明這樣的壓縮形式是極限壓縮。

另外,也可以這樣理解,對於關鍵詞 TiT_i,文件頻率為 DiD_i,這個關鍵詞的編碼長度為 −log(Di)-log(Di),因此在文件中出現 NiN_i 次,所以,共需要編碼長度為 −Nilog(Di)-N_ilog(D_i)。而整個文件的編碼長度為

−N1log(D1)−N2log(D2)−…−Nnlog(Dn)

-N_1log(D_1) – N_2log(D_2) – … -N_nlog(D_n)

與上面的式子相同。

接下來,考察該文件中每個詞的平均編碼長度。與之對應的是熵的概念,因為在資訊理論中自資訊量是一個隨機變數,不能用來作為整個信源的資訊測度,所以引入平均自資訊量,即熵,定義為

H(X)=∑i=1n−Pilog(Pi)

H(X)=\sum_{i=1}^n-P_ilog(P_i)

即整個文件需要的編碼長度除以總詞數,即:

−N1log(D1)−N2log(D2)−…−Nnlog(Dn)N1 N2 … Nn

\frac{-N_1log(D_1) – N_2log(D_2) – … -N_nlog(D_n)}{N_1 N_2 … N_n}

在這個平均編碼長度中,每個關鍵詞都做出了不同的貢獻。我們將關鍵詞在文件中的重要性量化為對平均編碼長度的貢獻上。不難得出如下結論:越是出現次數多(詞頻高)且罕見的詞彙(文件頻率低)的關鍵詞對平均編碼長度大小的貢獻越大。

假設

K=N1 N2 … Nn

K=N_1 N_2 … N_n

對於關鍵詞Ti而言,它對平均編碼長度的貢獻為:

−Nilog(Di)K=NiKlog(1Di)

\frac{-N_ilog(D_i)}K=\frac{N_i}Klog(\frac1{D_i})

其中Ni / K為在文件中關鍵詞Ti的詞頻(TF,Term Frequency),log(1/Di)為文件中關鍵詞Ti的文件頻率倒數的對數式,稱為逆文件頻率(IDF,Inverse Document Frequency),這就是經典的TF*IDF。

這裡把文件看作資訊源,需要通過通道傳輸,而首要工作就是編碼,文件的最小編碼長度即為自資訊量,平均編碼長度為熵,而每個關鍵詞對文件的編碼都有不同的貢獻,根據貢獻的大小量化其重要性,即TF*IDF。

講起 TF/IDF 的歷史蠻有意思

IDF 的概念最早是劍橋大學的斯巴克-瓊斯[注:她有兩個姓] (Karen Sparck Jones)提出來的。斯巴克-瓊斯 1972年在一篇題為關鍵詞特殊性的統計解釋和她在文獻檢索中的應用的論文中提出IDF。

遺憾的是,她既沒有從理論上解釋為什麼權重 IDF 應該是對數函式log(D/Dw)(而不是其它的函式,比如平方根),也沒有在這個題目上作進一步深入研究,以至於在以後的很多文獻中人們提到 TF/IDF 時沒有引用她的論文,絕大多數人甚至不知道斯巴克-瓊斯的貢獻。

同年羅賓遜寫了個兩頁紙的解釋,解釋得很不好。倒是後來康乃爾大學的薩爾頓 (Salton)多次寫文章、寫書討論 TF/IDF 在資訊檢索中的用途,加上薩爾頓本人的大名(資訊檢索的世界大獎就是以薩爾頓的名字命名的)。很多人都引用薩爾頓的書,甚至以為這個資訊檢索中最重要的概念是他提出的。

當然,世界並沒有忘記斯巴克-瓊斯的貢獻,2004年,在紀念文獻學學報創刊 60 週年之際,該學報重印了斯巴克-瓊斯的大作。羅賓遜在同期期刊上寫了篇文章,用夏農的資訊理論解釋 IDF,這回的解釋是對的,但文章寫的並不好、非常冗長(足足十八頁),把一個簡單問題搞複雜了。

其實,資訊理論的學者們已經發現並指出, IDF 的概念就是一個特定條件下、關鍵詞的概率分佈的交叉熵(Kullback-Leibler Divergence)。這樣,資訊檢索相關性的度量,又回到了資訊理論。

回到開頭的問題

既然可以藉助 TF/IDF 方法計算每個關鍵詞的權重,那麼給定兩組小說,我們可以設定一個閾值,根據每個詞在這些文件中的權重(資訊量),選擇出有價值的關鍵詞,建立文件的向量特徵模型,每一篇文件都可以轉化為特徵向量。於是可以藉助傳統的機器學習方法對其進行訓練學習和資料預測了。

TF/IDF只是文字特徵抽取的方法之一,為了不同的目的,還有其它方法,回頭再慢慢討論。