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

Web検索における
ページのグループ化
大阪教育大学大学院教育学研究科
総合基礎科学専攻
中窪仁
はじめに
• リンク構造解析によるスコアリング
– ＰａｇｅＲａｎｋアルゴリズム
• 「リンク行為＝推薦行為」と定義
• 隣接関係を基にスコアリング
• 推薦したいページにリンクできない可能性
– 隣接関係だけではモデル化が不可能
提案
• 隣接関係を拡張したスコアリング
– Ｗｅｂページのグループ化
• 同一作成者による類似情報ページをグループ化
• グループ内の隣接関係を削除＝隣接関係の拡大
– グループ化スコアリング
• グループ化済みリンク構造を基にスコアリング
– ランキング
グループ化
• ディレクトリ構造方式
Ａ
Ｂ
Ｄ
Ｃ
Ｅ
• リンク構造方式
Ａ
Ｂ
Ｄ
Ｃ
Ｅ
ＨＴＭＬＲｏｏｔ
ＨＴＭＬＲｏｏｔ
ＤｏｃｕｍｅｎｔＲｏｏｔ
ＤｏｃｕｍｅｎｔＲｏｏｔ
スコアリング
• ディレクトリ構造方式
Ａ
Ｆ
Ｇ
Ｈ
Ｂ
Ｄ
Ｃ
Ｅ
• リンク構造方式
Ａ
Ｆ
Ｇ
Ｈ
Ｂ
Ｄ
Ｃ
Ｅ
ランキング
• リンク構造解析と全文検索のスコアを併合
– 乗算方式
• （リンク構造解析スコア） × （全文検索スコア）
– 加算方式
• （リンク構造解析スコア）＋（全文検索スコア）
実験概要
• グループ化によるランキング変化を確認
– グループ化手法
• ディレクトリ構造方式（簡易版）
– スコアリング手法
• 全文検索スコア：ｔｆ‐ｉｄｆアルゴリズム
• リンク構造解析スコア：ＰａｇｅＲａｎｋアルゴリズム
– ランキング手法
• 乗算方式・加算方式
実験対象
• ＮＴＣＩＲ‐４テストコレクション
– 検索対象
• ＮＷ１００Ｇ‐０１（元ＨＴＭＬデータ１００ＧＢ）
– 検索語句
• ＮＴＣＩＲ‐４ＷｅｂＴａｓｋＢＴｏｐｉｃｓ
• ３００課題から１９７課題を有効課題として抽出
収集データ
• 全文検索スコアによるランキング
• リンク構造解析スコアによるランキング
– グループ化有無の２パターン
• 上記２項目の併合スコアによるランキング
– 乗算方式
• （全文検索スコア） × （リンク構造解析スコア）
– 加算方式
• （全文検索スコア）＋（Ｗ × （リンク構造解析スコア））
• Ｗ＝｛１，２，３，４，５｝
グループ化評価
最大スコア
最小スコア
平均スコア
分散
中央値
項目最大数
項目最小数
グループ化ありグループ化なし
３.４９５Ｅ-１５
２.２１５Ｅ-１１
０.２７８Ｅ-１５
０.６２０Ｅ-１５
１.８５９Ｅ-１５
３.５８１Ｅ-１５
１／∞
５.５５８Ｅ-２８
１.８８３Ｅ-１５
７.１１１Ｅ-１６
５６５,３１４
１７９,９０３
１
１
評価比較（ＷＲＲ）
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
手法別傾向
グループ化ありグループ化なし
Ｒａｎｋ変動幅
小
大
効果発揮帯
低Ｒａｎｋ帯
高Ｒａｎｋ帯
全文検索の影響
受けやすい
受けにくい
グループ化有無２種類のスコアを併合すれば
検索精度が向上するのではないか？
追加実験
• グループ化有無２種のスコアを併合
– 収集データ
• 加算方式
– （全文検索スコア）
＋（Ｗ１ × （グループ化ありリンク構造解析スコア））
＋（Ｗ２ × （グループ化なしリンク構造解析スコア））
– Ｗ１＝｛１，３，５｝，Ｗ２＝｛１，３，５｝
評価比較（ＷＲＲ）
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
考察
• グループ化スコアリング
– 既存手法ほど劇的な効果はない
– 既存手法では効果の低い文書に効果がある
• ランキング
– 全文検索によるランキングの底上げが可能
– 全文検索に漏れた文書の抽出は不可能
– 既存手法との併合で精度が全体的に向上
今後の課題
• グループ化スコアリング
– 別グループ化手法の有効性の確認
• ランキング
– 乗算・加算以外の併合方法の検証
– 各スコアの適正重みの検証
ありがとうございました
評価方式
• ＮＴＣＩＲ‐４評価方式
– ＷＲＲ（ＷｅｉｇｈｔｅｄＲｅｃｉｐｒｏｃａｌＲａｎｋ）
– ＤＣＧ（ＤｉｓｃｏｕｎｔｅｄＣｕｍｕｌａｔｉｖｅＧａｉｎ）
– 被検索トピック数
（ＣｕｍｕｌａｔｉｖｅＮｕｍｂｅｒｏｆＴｏｐｉｃｓ
ｆｏｒＲｅｌｅｖａｎｔＴｏｐｉｃｓｗｅｒｅＲｅｔｒｉｅｖｅｄ）
– １１点平均適合率（Ｒｅｃａｌｌ‐Ｐｒｅｃｉｓｉｏｎ）
手法単体（ＷＲＲ）
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
手法単体（ＤＣＧ）
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
手法単体（１１点）
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
ＮｏｒｍａｌＰａｇｅＲａｎｋ（ＷＲＲ）
0.10
WRR Value
0.08
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
0.06
0.04
0.02
0.00
1
2
3
4
5
6
Rank
7
8
9
10
ＮｏｒｍａｌＰａｇｅＲａｎｋ（ＤＣＧ）
0.60
DCG Value
0.50
0.40
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
0.30
0.20
0.10
0.00
1
2
3
4
5
6
Rank
7
8
9
10
ＮｏｒｍａｌＰａｇｅＲａｎｋ（トピック）
50
Topics
40
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
30
20
10
0
1
2
3
4
5
6
Rank
7
8
9
10
ＮｏｒｍａｌＰａｇｅＲａｎｋ（１１点）
Precision
0.15
0.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
ＧｒｏｕｐｅｄＰａｇｅＲａｎｋ（ＷＲＲ）
0.08
WRR Value
0.06
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
0.04
0.02
0.00
1
2
3
4
5
6
Rank
7
8
9
10
ＧｒｏｕｐｅｄＰａｇｅＲａｎｋ（ＤＣＧ）
0.40
DCG Value
0.30
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
0.20
0.10
0.00
1
2
3
4
5
6
Rank
7
8
9
10
ＧｒｏｕｐｅｄＰａｇｅＲａｎｋ（トピック）
50
Topics
40
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
30
20
10
0
1
2
3
4
5
6
Rank
7
8
9
10
ＧｒｏｕｐｅｄＰａｇｅＲａｎｋ（１１点）
0.100
Precision
0.075
乗算
加算１：１
加算２：１
加算３：１
加算４：１
加算５：１
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
評価比較（ＷＲＲ）
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
評価比較（ＷＲＲ‐Ｔｏｐ１００）
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
評価比較（ＤＣＧ）
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
評価比較（ＤＣＧ‐Ｔｏｐ１００）
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
評価比較（トピック‐Ｔｏｐ１００）
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
評価比較（１１点）
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

Download Report