TF-IDF Text-mining 演算法

TF-IDF Text-mining 演算法

此份文件為參考 Wikipedia – TF-IDF 而統整做出的中文學習心得及紀錄,如內容有誤或觀念不正確,歡迎您來信給我,謝謝!

TF-IDF 是 Term Frequency – Inverse Document Frequency 的縮寫,而在這裡的 Term 代表的是關鍵字,也就是說,此統計方法能夠以關鍵字來尋找與此關鍵字有高度相關的內文,而此方法也常為搜尋引擎所使用。

TF (Term Frequency)

現在舉個淺顯易懂的例子,如果我們現在正在打造一簡易內容搜尋系統,而現在使用者輸入一串文字作為關鍵字:the brown cow,那接下來 TF 會有兩個步驟:
1. 把不含全部 the, first, cow 三個字的文章都排除,也就是說只要文章只有 the, cow 也會被排除在外
2. 把此文章存在這些字詞的數量加總,得值便為 TF。

而接下來讓我們以數學式來定義 TF:

tf(t, d) = f_{t, d}
  • tf(t, d):詞語 t 在文件 d 當中出現的次數
    • 而 t 的出現頻率(frequency)以 f_{t, d} 表示

在 TF 當中也有幾種不太一樣的權重表示:

weighting scheme TF weight
Binary 0, 1
raw f_{t, d}
log normalization 1+\log(f_{t, d})
double normalization LaTeX

IDF (Inverse Document Frequent)

繼續剛剛的例子,你是不是也認為 the 這個詞出現的太頻繁,所以會讓 TF 失真了呢?在這個情況,TF 的值會使程式誤以為此份文件與搜尋關鍵字有高度相關。

所以說,the 很明顯地不是區分相關與否的 “好關鍵字 (Good Keyword)”,反之而言,brown, cow 這兩個詞才比較能夠區分出高度相關。

IDF 就是因為上述原因而存在的,他會檢查在文件資料庫的所有文件,並減少常出現的 Keyword 的比重。

接下來以數學式來定義 IDF:

idf(t, D) = \log\frac{N}{1+d\in D: t \in d}
  • d \in D: t \in d :表示詞語 t 在所有文件當中出現的次數,不過如果一個不存在於任何文件的詞語被輸入,此值會為 0,這會出現 Divide By Zero 的錯誤。
    因此解決此問題,通常會在分母 +1,這樣子就不會出現 Divide By Zero 了

TF-IDF (Term frequency-Inverse document frequency)

TF-IDF 的值是如此計算的:

tfidf(t, d, D) = tf(t, d) \cdot idf(t, D)

A high weight in tf–idf is reached by a high term frequency (in the given document) and a low document frequency of the term in the whole collection of documents; the weights hence tend to filter out common terms. Since the ratio inside the idf’s log function is always greater than or equal to 1, the value of idf (and tf-idf) is greater than or equal to 0. As a term appears in more documents, the ratio inside the logarithm approaches 1, bringing the idf and tf-idf closer to 0.

當 TF 值很高,而 DF 值很低,這時得到的權重值就能夠把 common terms(常見的 Bad Keyword) 濾掉。
回過頭來看 IDF 的公式,在 log 之中的分數式一定會 >=1,因此 IDF 一定是 >=0,當關鍵字出現在越多的文件當中,這個分數式值會趨近於 1,這也使 IDF 及 TF-IDF 趨近於 0。

Example

直接來看個例子,實際了解一下我們應該怎麼算 TF-IDF 吧。

假設我們有兩份文件,而以下則是這兩份文件的 Term Count Table:

A Term Count B Term Count
this 1 this 1
is 1 is 1
a 2 another 2
sample 1 example 3

那在此定義一些變數來方便說明這個例子:
– t: term 關鍵字
d_1:document 1,也就是 A
d_2:document 2,也就是 B
D:文件庫當中的所有文件

從上表當中檢查 thisd_1,可以看到 this\frac{1}{5},而在 d_2 當中,this 一詞所佔比例則為 \frac{1}{7}

tf("this", d_1)=\frac{1}{5}=0.2
tf("this", d_2)=\frac{1}{7}\approx0.14

那以 this 一詞來計算 IDF 的值在整份文件,根據公式可得:

idf("this", D)=\log(\frac{2}{2})=0

因為 D 的數量為 2,而 this 在兩份文件都有出現

接下來計算 tf-idf 的得值吧!

tfidf("this", d_1)=0.2\times0=0
tfidf("this", d_2)=0.14\times0=0

Leave a Reply

Your email address will not be published. Required fields are marked *