抄訳 Syntactic Clustering of the Web(1997)

December 13, 2022

2つのWeb文書から抽出したn-gramの集合を比較し、文書の包含関係と類似度を測定する。 はじめに、大文字をすべて小文字にしたり、htmlタグを除外したりして文書に前処理をかける。 次に文書\(A\)からnグラムの集合\(S(A)\)を抽出する。 このとき、文書\(A\)と\(B\)間の類似度を\(|S(A)\cap S(B)|/|S(A) \cup S(B)|\)、\(A\)の\(B\)への包含の度合いを\(|S(A) \cap S(B)|/|S(A)|\)と定義する。

計算量を減らすために、Nグラムから非負の整数へ一様にランダムに写像する関数\(\pi\)と非負の整数\(m\)をつかう手法も提案されている。 この場合、写像先の値が\(\text{MOD}_m\)が\(0\)になるNグラムのみで類似度と包含を測定する。

論文へのリンク

雑記

Nグラムで評価するので、類義語同士がまったく別の意味の単語と同様に扱われてしまう。 包含関係の定義は、包含している文書がされている文書よりも大きすぎると、実際に包含関係にあっても値が小さくなりそう。