類似度を用いた 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 1. 2. 3. root set の入力 base set の作成 Authority や Hub に重みをつける。 The HITS algorithm 1. 2. 3. root set の入力 base set の作成 Authority や Hub に重みをつける。 R The HITS algorithm 1. 2. 3. root set の入力 base set の作成 Authority や Hub に重みをつける。 B R The HITS algorithm 1. 2. 3. root set の入力 base set の作成 Authority や Hub に重みをつける。 B R Updated of hubs and authority p1 authority weight : Xp hub weight :Yp (each page p∈V) q1 Yq1 ・ ・ ・ qn Yqn Xpn = Yq1 + ･･･ + Yqn Xp = Σ Yq ←authority weight increased Yq = Σ Xp ← hub weight increased q→p q→p ・ ・ ・ pn Updated of hubs and authority authority weight : Xp hub weight :Yp (each page p∈V) Xp1 q1 Xpn ・ ・ ・ qn Yq1 = Xp1 + ･･･ + Xpn Xp = Σ Yq ←authority weight increased Yq = Σ Xp ← hub weight increased q→p q→p p1 ・ ・ ・ pn Update hubs and authority A : adjacency matrix (隣接行列) a11 A = ・ ・ ・ an1 1 3 ・・・ a1n aij 1 if page i points to page j 0 otherwise ・ ・ ・ ann １ ２ A ＝ ３ 2 4 ４ ０ ０ ０ ０ １ ０ ０ ０ １ １ ０ ０ ０ １ １ ０ Update hubs and authority ２ ２ ２ ＝ ３ １ ４ ０ Hub Weight １ 1 3 2 4 ０ ０ ０ ０ １ ０ ０ ０ １ １ ０ ０ ０ １ １ ０ １ １ １ １ authority weight Update hubs and authority 1 3 １ ２ ３ 2 4 ４ ０ ０ ０ ２ １ ０ ＝ ４ １ １ ３ ０ １ ０ ０ ０ １ ０ ０ ０ ０ AuthorityWeight … ０ ０ ０ ６１ １９ ６ ← ← ← １３６ ４２ １３ １０８ ３３ １０ ２ ２ １ ０ HubWeight ０ ２ ← ４ ３ １ １ １ １ HITSアルゴリズムの問題点 base set に本来のトピックとはまったく関係 のないページが含まれており、そのページが 密なリンク構造である場合、高いweightを与 えてしまう。(topic drift 問題) 目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察 HITSアルゴリズムの改善着目点 リンクを張っている、張られているページと内 容があまりにも違うならば、weightを低くして も良いのではないか？ →ページ間に類似値を導入 (Bharat et al, SIGIR’98) 自分の探したいトピックがページ内に含まれ ているのならばweightを高くしても良いので はないか？ →topic値を導入 目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察 ２つのサイトの類似値 各ページの索引語の抽出 索引語の重み付け 各ページをベクトル空間で表記 各ベクトル間の類似値を求める 索引語の抽出 索引語 : その文書を特徴付けるための単語 索引語の抽出 : 各文書を形態素解析を行い 動詞、名詞、英単語を抽出 今日は晴れです。 しかし、明日は晴れ か雨かわかりませ ん。 今日 / は / 晴れ / です /。 / しかし / 、 / 明日 / は /晴れ / か / 雨 / か / わかり / ま / せん /。 索引語の抽出 索引語 : その文書を特徴付けるための単語 索引語の抽出 : 各文書を形態素解析を行い 動詞、名詞、英単語を抽出 今日 / は / 晴れ / です /。 /しかし / 、 / 明日 / は /晴れ /か / 雨 / か / わかり / ま / せん /。 今日 晴れ 。 明日 晴れ 雨 わかる 。 索引語の重み付け 今日 晴れ 。 明日 晴れ 雨 わかる 。 W1 : 今日 W2 : 晴れ W3 : 明日 W4 : 雨 W5 : わかる 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 D１ D1…Dn ： 対象となるサイト W1…Wm : 抽出された索引語 dij : WiのDjにおける重み dij = TFij × IDFj TFij : 索引語頻度 IDFj : 文章頻度の逆数 各ページをベクトル空間で表記 索引語の重みを要素としてベクトルで表現 d1j d2j dｊ = ・ ・ ・ dmj d11 : 1/3 d12 : 1/3 d13 : 1/3 d14 : 1/3 d15 : 1/3 D１ dj : ページDjにおけるベクトル表記 dij : 索引語wiのサイトDjにおける重み d1 = 1/3 1/3 1/3 1/3 1/3 各ベクトル間の類似値を求める ベクトル間の類似度 : コサイン尺度 cos(di,dj) = di ・ dj / ||di|| ||dj|| HITSアルゴリズムの改善 a11 A = ・・・ ・ ・ ・ ・ ・ ・ an1 a11 A = ・ ・ ・ an1 a1n aij 1 if page i points to page j 0 otherwise ann ・・・ a1n ・ ・ ・ ann aij cos(di,dj) 0 if page i points to page j otherwise 目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察 Topic値 トピック値 : ページ内にトピックが含まれてい るならば一定の値を与える。 if Topic ∈ ｄj Topic（ｊ） = 1 + cos(di,dj) otherwise 1 a11 A = ・ ・ ・ an1 ・・・ a1n ・ ・ ・ ann aij cos(di,dj)･Topic(ｊ) if page i points to page j 0 otherwise 目次 HITSアルゴリズムの紹介 HITSアルゴリズムの改善点 ・類似値の導入 ・Topic値の導入 実験・考察 実験方法 1 １、HITS ２、類似値を用いたHITS ３、類似値＋Topic値を用いたHITS root set の収集方法 : １つURLからリンクを たどり収集 たどる方法 : 幅優先 root set のサイズ : 100 base setのサイズ : 1000～5000 実験方法 1 R B ・･････････ ・・・ ・・・・・・・・・・・・・・・・ 実験プログラム概要 GetURL.class URL入力 Analysis.class 茶筌を使用 Similarity.class Jamaを使用 CalculateMatrix.class 各Weightの出力 実験結果 http://math.nist.gov/javanumerics/jama/ HITS １、 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 類似値＋トピック値 （対象とするトピック : Matrix） １、 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の作成方法
© Copyright 2024 ExpyDoc
