類似度を用いた WWW のリンク構造の解析 谷　研究室　　　　栗原　伸行

目標 WWWのリンク構造の解析を行い、 自分の求めているトピックを正確に探し出す。 HITSアルゴリズムの改善を提案し実験を行う。

目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察

目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察

Hubs＆Authorities Hubs Authorities

The HITS algorithmの特徴 J. Kleinberg. 1998 各Webコンテンツの内容に立ち入らず、 サイト間のリンク構造の解析のみで、 適切な情報を抽出する。 適切な情報･･･Hub、Authorityページ集合

The HITS algorithm root set の入力 base set の作成 Authority や Hub に重みをつける。

The HITS algorithm root set の入力 base set の作成 Authority や Hub に重みをつける。

The HITS algorithm root set の入力 base set の作成 Authority や Hub に重みをつける。

The HITS algorithm root set の入力 base set の作成 Authority や Hub に重みをつける。

Updated of hubs and authority authority weight : Xp hub weight :Yp (each page p∈V) Xp = Σ　Yq　　←authority weight increased Yq = Σ　Xp　　← hub weight increased q1 ・・・ Yq1 ・・・ pn Yqn qn Xpn　=　Yq1 + ･･･ + Yqn q→p q→p

Updated of hubs and authority Xp1 authority weight : Xp hub weight :Yp (each page p∈V) Xp = Σ　Yq　　←authority weight increased Yq = Σ　Xp　　← hub weight increased q1 ・・・ Xpn ・・・ pn qn Yq1　=　Xp1 + ･･･ + Xpn q→p q→p

Update hubs and authority A : adjacency matrix (隣接行列) a11 a1n ・・・ 1 if page i points to page j 0 otherwise aij A　 = ・・・ ・・・ ann an1 　　　　　　　　　１　０　１　１　０　　　 　　　　　　　　　２　０　０　１　１ 　　　　　　　　　３　０　０　０　１ 　　　　　　　　　４　０　０　０　０　　 1 3 A ＝ 2 4

Update hubs and authority １　　２　　　０　１　１　０　　　１ ２　　２　　　０　０　１　１　　　１ ３　　１　　　０　０　０　１　　　１ ４　　０　　　０　０　０　０　　　１ 　　Hub authority Weight weight 1 3 ＝ 2 4

Update hubs and authority １　　０　　　０　０　０　０　　　２ ２　　２　　　１　０　０　０　　　２ ３　　４　　　１　１　０　０　　　１ ４　　３　　　０　１　１　０　　　０ 1 3 ＝ 2 4 HubWeight AuthorityWeight 　　　０　　　０　　　０　　　０　　　１ 　　６１　　１９　　　６　　　２　　　１　　 　１３６　　４２　　１３　　　４　　　１ 　１０８　　３３　　１０　　　３　　　１　　 収束回数１３回 … ← ← ← ←

HITSアルゴリズムの問題点 base set に本来のトピックとはまったく関係のないページが含まれており、そのページが密なリンク構造である場合、高いweightを与えてしまう。(topic drift 問題)

目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察

HITSアルゴリズムの改善着目点 リンクを張っている、張られているページと内容があまりにも違うならば、weightを低くしても良いのではないか？ →ページ間に類似値を導入 (Bharat et al, SIGIR’98) 自分の探したいトピックがページ内に含まれているのならばweightを高くしても良いのではないか？ →topic値を導入

目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察

２つのサイトの類似値 各ページの索引語の抽出 索引語の重み付け 各ページをベクトル空間で表記 各ベクトル間の類似値を求める 文章検索ではポピュラーな方法

索引語の抽出 索引語 : その文書を特徴付けるための単語 索引語の抽出 : 各文書を形態素解析を行い 動詞、名詞、英単語を抽出 索引語の抽出 : 各文書を形態素解析を行い　　　　　　 　　　　　　　　　 　 動詞、名詞、英単語を抽出 今日 / は / 晴れ / です /。 / しかし / 、 / 明日 / は /晴れ / か / 雨 / か / わかり / ま / せん /。 今日は晴れです。 しかし、明日は晴れか雨かわかりません。

索引語の抽出 索引語 : その文書を特徴付けるための単語 索引語の抽出 : 各文書を形態素解析を行い 動詞、名詞、英単語を抽出 今日 晴れ 索引語の抽出 : 各文書を形態素解析を行い　　　　　　 　　　　　　　　　 　 動詞、名詞、英単語を抽出 今日 晴れ 。 明日 雨 わかる 今日 / は / 晴れ / です /。 /しかし / 、 / 明日 / は /晴れ /か / 雨 / か / わかり / ま / せん /。

索引語の重み付け D１ 今日 d11 : 1/6 × 2/1 = 1/3 晴れ W1 : 今日 d12 : 2/6 × 2/2 = 1/3 。 明日 雨 わかる d11 : 1/6 × 2/1 = 1/3 d12 : 2/6 × 2/2 = 1/3 d13 : 1/6 × 2/1 = 1/3 d14 : 1/6 × 2/1 = 1/3 d15 : 1/6 × 2/1 = 1/3 W1 : 今日 W2 : 晴れ W3 : 明日 W4 : 雨 W5 : わかる たまたま今回は1/3になってしまう。 D１ D1…Dn ： 対象となるサイト TFij : 索引語頻度 W1…Wm : 抽出された索引語 IDFj : 文章頻度の逆数 dij : WiのDjにおける重み dij = TFij × IDFj

各ページをベクトル空間で表記 索引語の重みを要素としてベクトルで表現 d1j d2j dｊ = ・・・ dmj d1 = D１ 1/3 d2j d1 = dｊ　= ・・・ dmj D１ dj : ページDjにおけるベクトル表記 dij : 索引語wiのサイトDjにおける重み

各ベクトル間の類似値を求める ベクトル間の類似度 : コサイン尺度 cos(di,dj) = di ・ dj / ||di|| ||dj||

HITSアルゴリズムの改善 aij 1 if page i points to page j 0 otherwise A = aij a1n ・・・ aij 1 if page i points to page j 0 otherwise A　 = ・・・ ・・・ an1 ann a11 a1n ・・・ aij cos(di,dj) if page i points to page j 0 otherwise A　 = ・・・ ・・・ an1 ann

目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察

Topic値 トピック値 : ページ内にトピックが含まれてい るならば一定の値を与える。 Topic（ｊ） = 1 + cos(di,dj) 　　　　　　 　るならば一定の値を与える。 Topic（ｊ） = 1 + cos(di,dj) 1 if　Topic ∈　ｄj otherwise いろいろな値を使い実験を行い統計などをとり、適切な値を見つけなければならないが a11 a1n ・・・ cos(di,dj)･Topic(ｊ) 　　　　　　　　　　　 if page i points to page j 0 otherwise aij A　 = ・・・ ・・・ an1 ann

目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察

実験方法 1 １、HITS ２、類似値を用いたHITS ３、類似値＋Topic値を用いたHITS root set の収集方法 : １つURLからリンクを たどり収集 たどる方法 : 幅優先 root set のサイズ : 100 base setのサイズ : 1000～5000

実験方法 1 R B ・･････････ ・・・ ・・・・・・・・・・・・・・・・

実験プログラム概要 GetURL.class Analysis.class Similarity.class 茶筌を使用 Similarity.class Jamaを使用 CalculateMatrix.class 各Weightの出力

実験結果 http://math.nist.gov/javanumerics/jama/ HITS 類似値 類似値＋トピック値　（対象とするトピック : Matrix） １、　http://www.netlib.org/lapack/index.html ２、　http://www.netlib.org/linpack/readme ３、　http://www.mathworks.com/ １、　http://www.mathworks.com/company/pressroom/index.shtml/article/439/index.shtml ２、　http://www.mathworks.com/company/pressroom/index.shtml/article/439/siteindex.shtml ３、　http://www.mathworks.com/company/pressroom/index.shtml/article/439/search １、　http://www.mathworks.com/company/pressroom/index.shtml/article/435/index.shtml ２、　http://www.mathworks.com/company/pressroom/index.shtml/article/435/siteindex.shtml ３、　http://www.mathworks.com/company/pressroom/index.shtml/article/435/search

実験結果 http://www.pure.cc/~winds/volleyball/sunflower/ HITS 類似値 類似値＋トピック値　（対象とするトピック : 栗原恵） １、　http://www.jva.or.jp/jva/schedule.html ２、　http://www.jva.or.jp/topics/index.html ３、　http://www.jva.or.jp/jva/index.html １、　http://www.jva.or.jp/japan/motoko/20040127.html ２、　http://www.jva.or.jp/japan/motoko/20031224.html ３、　http://www.jva.or.jp/japan/motoko/20031210.html １、　http://momocan1111.hp.infoseek.co.jp/megu/ ２、　http://momocan1111.hp.infoseek.co.jp/azusa/redrockets_members.html ３、　http://momocan1111.hp.infoseek.co.jp/megu/vleague.html

考察 幾つかのケースを除いて、今実験では目に見えた差を得ることが出来なかった。 ・WWWにおいてページの内容はリンク構造 だけで判断可能？ 　　だけで判断可能？ ・類似度・トピック値においてそれぞれチュー 　　ニングを行うことで精度の向上が可能？

考察 文章検索の手法の有効性 トピックの意味 索引語の抽出方法 base setの作成方法 文章検索の有効性 ・webページにおいて、1文は本なんかに比べるとはるかに短い。 ・句読点がはっきりと存在しない。 トピックの意味 ・多義性のある単語ではより一般的な意味の方によってしまう。 索引語の抽出方法 ・形態素解析を行いばらばらに抽出したわけだが、より意味的に抽出する。 Basesetの作成方法 今回、深さ１で考えて見たがより深くして考えて見る。