Web検索における リンク構造解析を利用した ランキング法

Web検索における
リンク構造解析を利用した
ランキング法
中窪 仁† 佐藤隆士‡
†大阪教育大学大学院総合基礎科学専攻
‡大阪教育大学情報処理センター
発表内容








背景
研究目的
関連研究
提案手法
考察
実験概要
まとめ
今後の課題
背景
WWW空間上には膨大な情報が存在
 膨大な情報から必要な情報のみを抽出す
ることは困難
 情報抽出支援ツールであるWeb検索シス
テムを利用
 Web検索システムの検索精度は未だ十分
ではない

研究目的

現在のWeb検索システム
– Webページ本文と検索語句による全文検索
– Webページ間のリンク構造解析による文書抽出
Webページ特有の情報であるリンク構造を利用
した手法を提案
 Web検索システムの精度向上を図る

関連研究
- PageRankアルゴリズム(1) -

PageRankアルゴリズム
– Webページ間のリンク構造にランダムウォー
クモデルを適用
– WWW空間上の全Webページへの遷移確率
をもとにスコアリング
関連研究
- PageRankアルゴリズム(2) -

PageRankアルゴリズム例
90
30
30
30
30
15
15
45
15
15
15
関連研究
- PageRankアルゴリズム(3) -

PageRankアルゴリズムの特徴
– WWW空間上の各Webページの被参照度を
示す固定値
– 検索語句によって左右されない静的スコア

PageRankアルゴリズムの問題点
– リンク構造上隣接していないWebページへの
影響が減少
関連研究
- HITSアルゴリズム(1) -

HITSアルゴリズム
– リンク構造を利用して検索語句に対して適切
なコミュニティを抽出
– “authority”

検索語句に関する的確な情報を持つWebページ
集合
– “hub”
 リンク構造上,“authority”に含まれるWebページ
と隣接関係を持つWebページ集合
関連研究
- HITSアルゴリズム(2) -

HITSアルゴリズム例
auth: 0.408
hub: 0.000
auth: 0.000
hub: 0.408
auth: 0.816
hub: 0.000
auth: 0.000
hub: 0.816
auth: 0.408
hub: 0.000
auth: 0.000
hub: 0.408
関連研究
- HITSアルゴリズム(3) -

HITSアルゴリズムの特徴
– “authority”,“hub”の二種類のスコアを算出
– 検索語句によって左右される動的スコア

HITSアルゴリズムの問題点
– 常に適切なコミュニティを抽出できるとはかぎ
らない
提案手法概要(1)

提案概要
Webページ本文と検索語句による全文検索結果
+
リンク構造解析による静的スコアリング
+
リンク構造解析による動的スコアリング
Web検索システムの精度向上
提案手法概要(2)

提案手法手順
Corpus
Result
全文検索スコア
Link Structure
Data
動的スコア#1
動的スコア#2
静的スコア
グループ化
スコアリング
ランキング
Webページのグループ化(1)

Webページのグループ化
– Webページ群をグループとして扱う
– グループの定義
 同一の作成者が作成し,類似分野の情報を持つと
思われるWebページ群
– グループ化手法
 「類似分野の情報は同一の親を持つ部分木であ
る」と仮定
 ディレクトリ構造,リンク構造の二通りのアプローチ
Webページのグループ化(2)

ディレクトリ構造方式
B
A
C
D

ディレクトリ構造を木構
造とみなしてグループ化

リンク構造解析が不要
作成者のディレクトリ分
類法によってグループ
の質が変化

ルート
:グループ
E
Webページのグループ化(3)

リンク構造方式

B
A
C
D
ルート
E
:グループ
リンク構造を木構造とみ
なしてグループ化
作成者の意図通りにグ
ループ化が可能
 リンク構造によるグルー
プ化は難易度が高い

静的スコアリング(1)

静的スコアリング
– 小規模コミュニティのスコアリングが目的
– グループ化済みのリンク構造についてスコア
リング
– スコアリングにはPageRankアルゴリズムを
使用
静的スコアリング(2)

静的スコアリング例
F
A
B
G
C
D
ディレクトリ
構造方式
H
E
:Webサイト
(A..Eはグループ化例と同じ構造を持つ)
F
グ
ル
ー
プ
化
F
リンク
構造方式
A
BC
G
DE
H
AB
G
CDE
H
静的スコアリング(3)

静的スコア例
Grouping
Method
A
B
C
No
0.26 0.15 0.26
0.38
Dir.
0.22
0.22
Link
Page
D
E
0.11 0.11
0.22
0.36
F
0.00
0.00
0.00
G
0.06
0.09
0.22
グループからリンクされている
Webサイト外ページのスコアが増加
リンク構造上隣接関係にない
Webページへの影響度が増加
H
0.06
0.09
0.22
静的スコアリング(4)

静的スコア例
Grouping
Method
A
B
C
No
0.26 0.15 0.26
0.38
Dir.
0.22
0.22
Link
Page
D
E
0.11 0.11
0.22
0.36
F
0.00
0.00
0.00
G
0.06
0.09
0.22
グループ化によりスコアが均一化
本来のリンク構造が表す各Webページの
特性が失われている
H
0.06
0.09
0.22
動的スコアリング(1)

動的スコアリング
– 全文検索結果集合に含まれるリンク構造につ
いてスコアリング
– スコアリングにはPageRankアルゴリズムを
使用
– グループ化適用の前後二種のスコアを算出

グループ化適用前を#1,適用後を#2とする
動的スコアリング(2)

動的スコアリング#1(グループ化適用前)
– 全文検索結果集合内での有用なWebページ
の抽出が目的

動的スコアリング#2(グループ化適用後)
– 全文検索結果集合内のWebページを含む小
規模コミュニティのスコアリングが目的
– 動的スコアリング#1からスコアリング範囲を
グループ単位まで拡張
動的スコアリング(3)

動的スコアリング例
#1
#2
U
V
W
Y
X
:結果集合
Z
グ
ル
ー
プ
化
:グループ
U
V
W
XYZ
動的スコアリング(4)

動的スコア例
#
1
2
Page
U
V
W
X
Y
Z
1.00 0.00 0.00 0.00 0.00 0.00
0.50
0.50 0.00 0.00
各Webページの特性を明確に示す
スコアリングが可能
動的スコアリング(5)

動的スコア例
#
1
2
Page
U
V
W
X
Y
Z
1.00 0.00 0.00 0.00 0.00 0.00
0.50
0.50 0.00 0.00
複数のWebページにスコアリングされている
検索結果集合内Webページのみスコアを適用することにより
最終的なランキング時のノイズ混入を防止しつつ評価可能
ランキング(1)

ランキング
– 得られたスコアを最適な手法をもって併合
 全文検索結果
– 検索語句に特化したスコア

静的スコア
– 各Webページ特性の大まかなスコア

動的スコア#1
– 検索語句に特化,各Webページ特性の明確なスコア

動的スコア#2
– 検索語句に特化,各Webページ特性の大まかなスコア
ランキング(2)

スコア併合手法
– 各スコアにそれぞれ一定の重みを付け,加算
Score ( p )  w r Retrieval ( p)  w s Static( p)  w d Dynamic( p)
w : Weight ( w r  w d  w s , wd1  w d2 )
Retrieval ( p ) : Full - text S earch S core of Document p.
Static( p ) : S taticS core of Document p.
D1 ( p ) : Dynamic S core of Document p without Grouping.
D2 ( p ) : Dynamic S core of Document p with Grouping.
Dynamic( p )  w d1 D1 ( p )  w d2 D2 ( p )
提案手法考察

考察
– 検索語句を含むWebページを高評価
– 類似情報を持つであろう小規模コミュニティを
考慮
Web検索システムの精度向上が可能
実験概要(1)

実験対象データ(NTCIR*テストコレクション)
– 検索対象
 NW100G-01
– 100GbyteのHTMLデータ
– 上記HTMLデータに含まれるリンク構造データ

URI総数:約2370万ページ
– HTMLデータのあるもの:約1100万ページ

リンク総数:約8000万リンク
– 検索語句
 トピック総数:153トピック
* NII-NACSIS Test Collection for IR Systems Project
情報検索システム評価用テストコレクション構築プロジェクト
実験概要(2)

実験環境
– ハードウェア
 CPU:Pentium4 2.4GHz
 Memory:1Gbyte
– OS
 FreeBSD
実験概要(3)

プロトタイプ
– 全文検索プログラム
 グラムベースインデクスによる検索システム
 スコアリングには tf・idf 法を使用
– グループ化プログラム
 ディレクトリ構造方式にてグループ化
– PageRankスコア算出プログラム
 HTMLデータのないWebページも算出
実験概要(4)

収集データ
– グループ化

グループ作成手法を検討しつつ数パターン
– 静的スコア


グループ化適用前のスコア
グループ化適用後のスコア
– 動的スコア

全文検索結果上位5000件分のスコア
– ランキング

各スコアの重みを検討しつつ数パターン
実験結果(1)

全文検索システム
– 処理時間
 前処理:20時間
 インデクス作成処理:15時間
 検索処理平均値:72ミリ秒/語
 検索処理中央値:26ミリ秒/語
– 処理結果
 インデクスサイズ:約30Gbyte
実験結果(2)

グループ化
– 処理結果
 グループ総数:約467万グループ
 最大値 21468ページ/グループ
 最小値
1ページ/グループ
 平均値
5ページ/グループ
 中央値
1ページ/グループ
実験結果(3)

PageRankスコア算出
– 処理時間(算出対象:約2400万ページ)
 前処理:20時間
 算出:45分(未収束,50ループ)
– 処理結果
 スコア最大値:0.0002352483
 スコア最小値:0.0000000000
 スコア中央値:0.0000000084
 スコア平均値:0.0000000422
まとめ
リンク構造解析を利用したランキング法と
して,静的・動的スコアリング法を提案
 検索語句を含むWebページに重点をおき
つつ,小規模コミュニティを考慮可能

ランキング時の各スコアの重みを検討することで
興味深い結果が得られると思われる
今後の課題
提案手法についての実験
 精度に関するデータ収集・検討
 ランキング時の重み最適値の検討
 Webページグループ化手法の検討
 処理コスト低減手法の検討

ご静聴ありがとうございました