Web検索における
ページのグループ化
大阪教育大学大学院教育学研究科
総合基礎科学専攻
中窪 仁
はじめに
• リンク構造解析によるスコアリング
– PageRankアルゴリズム
• 「リンク行為=推薦行為」と定義
• 隣接関係を基にスコアリング
• 推薦したいページにリンクできない可能性
– 隣接関係だけではモデル化が不可能
提案
• 隣接関係を拡張したスコアリング
– Webページのグループ化
• 同一作成者による類似情報ページをグループ化
• グループ内の隣接関係を削除 = 隣接関係の拡大
– グループ化スコアリング
• グループ化済みリンク構造を基にスコアリング
– ランキング
グループ化
• ディレクトリ構造方式
A
B
D
C
E
• リンク構造方式
A
B
D
C
E
HTML Root
HTML Root
Document Root
Document Root
スコアリング
• ディレクトリ構造方式
A
F
G
H
B
D
C
E
• リンク構造方式
A
F
G
H
B
D
C
E
ランキング
• リンク構造解析と全文検索のスコアを併合
– 乗算方式
• (リンク構造解析スコア) × (全文検索スコア)
– 加算方式
• (リンク構造解析スコア) + (全文検索スコア)
実験概要
• グループ化によるランキング変化を確認
– グループ化手法
• ディレクトリ構造方式(簡易版)
– スコアリング手法
• 全文検索スコア:tf‐idf アルゴリズム
• リンク構造解析スコア:PageRankアルゴリズム
– ランキング手法
• 乗算方式・加算方式
実験対象
• NTCIR‐4テストコレクション
– 検索対象
• NW100G‐01(元HTMLデータ100GB)
– 検索語句
• NTCIR‐4 Web Task B Topics
• 300課題から197課題を有効課題として抽出
収集データ
• 全文検索スコアによるランキング
• リンク構造解析スコアによるランキング
– グループ化有無の2パターン
• 上記2項目の併合スコアによるランキング
– 乗算方式
• (全文検索スコア) × (リンク構造解析スコア)
– 加算方式
• (全文検索スコア) + (W × (リンク構造解析スコア))
• W = {1,2,3,4,5}
グループ化評価
最大スコア
最小スコア
平均スコア
分散
中央値
項目最大数
項目最小数
グループ化あり グループ化なし
3.495E-15
2.215E-11
0.278E-15
0.620E-15
1.859E-15
3.581E-15
1/∞
5.558E-28
1.883E-15
7.111E-16
565,314
179,903
1
1
評価比較(WRR)
0.10
WRR Value
0.08
tf-idf
N Weight
G Weight
N Multi
G Multi
0.06
0.04
0.02
0.00
1
11
21
31
41
51 61
Rank
71
81
91
手法別検索結果
4%
2%
0%
NPageRank
39%
8%
(none)
GPageRank
10%
tf-idf
tf-idf &
GPageRank
All
17%
20%
tf-idf &
NPageRank
NPageRank &
GPageRank
手法別傾向
グループ化あり グループ化なし
Rank変動幅
小
大
効果発揮帯
低Rank帯
高Rank帯
全文検索の影響
受けやすい
受けにくい
グループ化有無2種類のスコアを併合すれば
検索精度が向上するのではないか?
追加実験
• グループ化有無2種のスコアを併合
– 収集データ
• 加算方式
– (全文検索スコア)
+ (W1 × (グループ化ありリンク構造解析スコア))
+ (W2 × (グループ化なしリンク構造解析スコア))
– W1 = {1,3,5},W2 = {1,3,5}
評価比較(WRR)
0.120
WRR Value
0.100
0.080
tf-idf
NPageRank
WPageRank
0.060
0.040
0.020
0.000
1
11 21 31 41 51 61 71
Rank
81 91
考察
• グループ化スコアリング
– 既存手法ほど劇的な効果はない
– 既存手法では効果の低い文書に効果がある
• ランキング
– 全文検索によるランキングの底上げが可能
– 全文検索に漏れた文書の抽出は不可能
– 既存手法との併合で精度が全体的に向上
今後の課題
• グループ化スコアリング
– 別グループ化手法の有効性の確認
• ランキング
– 乗算・加算以外の併合方法の検証
– 各スコアの適正重みの検証
ありがとうございました
評価方式
• NTCIR‐4評価方式
– WRR(Weighted Reciprocal Rank)
– DCG(Discounted Cumulative Gain)
– 被検索トピック数
(Cumulative Number of Topics
for Relevant Topics were Retrieved)
– 11点平均適合率(Recall‐Precision)
手法単体(WRR)
0.08
WRR Value
0.06
tf-idf
Normal
Grouped
0.04
0.02
0.00
1
2
3
4
5
6
Rank
7
8
9
10
手法単体(DCG)
0.50
DCG Value
0.40
tf-idf
Normal
Grouped
0.30
0.20
0.10
0.00
1
2
3
4
5
6
Rank
7
8
9
10
手法単体(トピック)
50
Topics
40
tf-idf
Normal
Grouped
30
20
10
0
1
2
3
4
5
6
Rank
7
8
9
10
手法単体(11点)
Precision
0.15
0.1
tf-idf
Normal
Grouped
0.05
0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Recall
NormalPageRank(WRR)
0.10
WRR Value
0.08
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
0.06
0.04
0.02
0.00
1
2
3
4
5
6
Rank
7
8
9
10
NormalPageRank(DCG)
0.60
DCG Value
0.50
0.40
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
0.30
0.20
0.10
0.00
1
2
3
4
5
6
Rank
7
8
9
10
NormalPageRank(トピック)
50
Topics
40
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
30
20
10
0
1
2
3
4
5
6
Rank
7
8
9
10
NormalPageRank(11点)
Precision
0.15
0.1
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
0.05
0
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Recall
GroupedPageRank(WRR)
0.08
WRR Value
0.06
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
0.04
0.02
0.00
1
2
3
4
5
6
Rank
7
8
9
10
GroupedPageRank(DCG)
0.40
DCG Value
0.30
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
0.20
0.10
0.00
1
2
3
4
5
6
Rank
7
8
9
10
GroupedPageRank(トピック)
50
Topics
40
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
30
20
10
0
1
2
3
4
5
6
Rank
7
8
9
10
GroupedPageRank(11点)
0.100
Precision
0.075
乗算
加算1:1
加算2:1
加算3:1
加算4:1
加算5:1
0.050
0.025
0.000
0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0
Recall
評価比較(WRR)
0.10
WRR Value
0.08
tf-idf
N Weight
G Weight
N Multi
G Multi
0.06
0.04
0.02
0.00
1
2
3
4
5
6
Rank
7
8
9
10
評価比較(WRR‐Top100)
0.10
WRR Value
0.08
tf-idf
N Weight
G Weight
N Multi
G Multi
0.06
0.04
0.02
0.00
1
11
21
31
41
51 61
Rank
71
81
91
評価比較(DCG)
0.6
DCG Value
0.5
0.4
tf-idf
N Weight
G Weight
N Multi
G Multi
0.3
0.2
0.1
0.0
1
2
3
4
5
6
Rank
7
8
9
10
評価比較(DCG‐Top100)
1.2
DCG Value
1.0
0.8
tf-idf
N Weight
G Weight
N Multi
G Multi
0.6
0.4
0.2
0.0
1
11
21
31
41
51 61
Rank
71
81
91
評価比較(トピック)
50
Topics
40
tf-idf
N Weight
G Weight
N Multi
G Multi
30
20
10
0
1
2
3
4
5
6
Rank
7
8
9
10
評価比較(トピック‐Top100)
140
120
Topics
100
tf-idf
N Weight
G Weight
N Multi
G Multi
80
60
40
20
0
1
11
21
31
41
51 61
Rank
71
81
91
評価比較(11点)
0.12
Precision
0.10
0.08
tf-idf
N Weight
G Weight
N Multi
G Multi
0.06
0.04
0.02
0.00
0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9
Recall
1
ダウンロード

Web検索における ページのグループ化