投稿日: その他 論文紹介

Unsupervised Semantic Similarity Computation between Terms Using Web Documents

Elias Iosif
Alexandros Potamianos
In IEEE Transactions on Knowledge and Data Engineering, Vol.22, Num.11
http://www.computer.org/csdl/trans/tk/2010/11/ttk2010111637-abs.html

概要

検索エンジンを用いて得られる情報を基に,単語間の意味的類似度を測ることを目的としている.

手法

検索エンジンのヒットカウントを用いて測る主な手法として以下の4つをあげている.以下の式中で,hits(q)qをクエリとしたときの検索ヒット数,hits(q_{1}\land q_{2})q_{1}q_{2}を共に含むページの検索ヒット数を表す.また,Nは全Webページ数である.

  1. WebJaccard(q_{1},q_{2})=\log_{2} \left( \frac{hits(q_{1}\land q_{2})}{hits(q_{1})\times hits(q_{2})-hits(q_{1}\land q_{2})} \right)

  2. WebDice(q_{1},q_{2})=\log_{2} \left( \frac{2 \times hits(q_{1}\land q_{2})}{hits(q_{1})\times hits(q_{2})} \right)

  3. WebPMI(q_{1},q_{2})=\log_{2} \left( \frac{hits(q_{1}\land q_{2})/N}{\left( hits(q_{1})/N \right) \times  \left( hits(q_{2})/N \right)} \right)

  4. NDG(q_{1},q_{2})=\frac{max \left( \log \left( hits(q_{1}) \right), \log \left( hits(q_{2})\right) \right)}{\log{N- min \left( \log \left( hits(q_{1}) \right), \log \left( hits(q_{2}) \right) \right)}}

これらに対して本論文では,検索結果のWebページの内容を用いる手法を提案している.まず,語wの検索結果の上位n件の検索結果のWeb文書中で,wの前後K語に出現する語をもとに特徴ベクトルを作る.語w_{1}w_{2}の類似度を測る際は,それぞれのベクトルのコサイン類似度を求める.
wのベクトルの要素となる語v_{i}の値の求め方として8つの方法を提案している.以下にそのうちの5つを示す.

  • Binary(B)
    v_{i}が一度以上出現していれば値が1となる.

  • Term frequency(TF)
    v_{i}wの出現頻度をそれぞれc(v_{i})c(w)としたとき,次式で表される.
    \frac{c(v_{i})}{c(w)}

  • Log of TF(LTF)
    TFで対数をとる.
    \frac{\log{\left( c(v_{i}) \right)}}{\log{\left( c(w) \right)}}

  • TF-inverse document frequency(TFIDF)
    \frac{c(v_{i})}{c(w)} \log{\frac{N}{hit(v_{i})}}

  • Log of TFIDF(LTFIDF)
    \frac{\log{\left( c(v_{i}) \right)}}{\log{\left( c(w) \right)}} \log{\frac{N}{hit(v_{i})}}

実験

実験に用いたデータは,Charles-Miller datasetと呼ばれる一般的な語からなるデータセットと,MeSH datasetと呼ばれる科学用語からなるデータセットである.論文中では,前者は1語の単語なのでword,後者は複数の単語から成る語なのでtermと呼んでいる.いずれのデータセットも,複数の語のペアとその意味的類似度のスコアが正解データとして存在する.
評価には相関係数を用いている.

実験の結果,Webの検索結果数のみを用いる4手法では,Charles-Miller datasetで最も良い手法がWebPMIで相関係数は0.69,MeSH datasetで最も良い手法がNDGで相関係数は0.41であった.
提案手法では,前後何語を調べるかというKと,検索結果の上位何件を使うかがそれぞれパラメータとして存在するので,値の違いによる相関係数の値を比較している.

  • Charles-Miller dataset
    まず,前後何語を調べるかという点では,8つの提案手法のうち多くの手法でK=1のときに最も高い相関係数となった.なおこのときの検索結果数は上位100件を用いている.K=1のときの相関係数の値は,LTFが最も高く0.72,次いでBもほぼ同じ値となっていた.
    次に検索結果を上位何件まで調べるかという点では,いずれの手法でも100件を下回ると大きく精度が下がるが,100件から1000件の間ではゆるやかな右肩上がりとなった.最も結果が良かったのは,Bで上位1000件まで用いたときで,相関係数の値は0.88であった.

  • MeSH dataset
    まず,前後何語を調べるかという点では,使用する検索結果を上位100件に固定したとき,多くの手法でKの値が2から5の間で最大値となった.8つの手法の中では,LTFIDFが他の手法よりも有意に良い結果となり,相関係数の最大値はK=3のときの0.67であった.
    次に検索結果を上位何件まで調べるかという点では,多くの手法で100件を下回ると大きく精度が下がり,800件をピークとして山なりの値をとった.ここでも,LTFIDFが他の手法よりも有意に良い結果となった.

次に,前後K語を調べる際にストップワードを除去することの影響を調べた結果,Charles-Miller datasetでは除去しない方が精度が高く,MeSH datasetでは除去した方が精度が高かった.

最後に,本論文で提案した手法はいずれも教師なしの手法であるが,教師ありの既存手法との比較を行った.その結果,Charles-Miller datasetでは提案手法の方が精度が高かった.MeSH datasetでは教師ありの方が精度が高かったが,提案手法でもそれに近い精度が出ていた.


-その他, 論文紹介
-

関連記事

Fusion Helps Diversification

Liang, Shangsong and Ren, Zhaochun and de Rijke, Maarten In Proc. of SIGIR 2014 概要 検索結果を多様化する際に、複数の検 …

Spatio-Temporal Topic Modeling in Mobile Social Media for Location Recommendation

Bo, Hu and Mohsen, Jamali and Martin, Ester In Proc. of ICDM 2013 概要 チェックインサービス等でのユーザと場所と時刻を考慮したモデル化 …

No clicks, no problem: using cursor movements to understand and improve search

Huang, Jeff White, Ryen W. Dumais, Susan In Proc. of CHI2011 概要 検索行動中のユーザのカーソルの動きに関する分析を行った。また、カーソルの …

Predicting the popularity of web 2.0 items based on user comments

He, Xiangnan and Gao, Ming and Kan, Min-Yen and Liu, Yiqun and Sugiyama, Kazunari In Proc. of SIGIR …

AutoWeb: automatic classification of mobile web pages for revisitation

Liu, Jie Xu, Wenchang Shi, Yuanchun In Proc. of MobileHCI 2012 http://dl.acm.org/citation.cfm?id=237 …