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

Presentation on theme: "類似度を用いた WWW のリンク構造の解析 谷　研究室　　　　栗原　伸行."— Presentation transcript:

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

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

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

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

5 Hubs＆Authorities Hubs Authorities

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

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

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

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

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

11 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

12 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

13 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

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

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

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

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

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

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

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

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

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

23 索引語の重み付け 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

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

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

26 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 otherwise A　 = ・・・ ・・・ an1 ann

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

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

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

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

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

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

33 実験結果 http://math.nist.gov/javanumerics/jama/ HITS 類似値
類似値＋トピック値　（対象とするトピック : Matrix） １、　 ２、　 ３、　 １、　 ２、　 ３、　 １、　 ２、　 ３、　

34 実験結果 http://www.pure.cc/~winds/volleyball/sunflower/ HITS 類似値
類似値＋トピック値　（対象とするトピック : 栗原恵） １、　 ２、　 ３、　 １、　 ２、　 ３、　 １、　 ２、　 ３、　

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

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