Web検索におけるリンク構造解析
-Webサイトのグループ化と動的スコアリング中窪 仁，居 行和，佐藤 隆士
大阪教育大学大学院教育学研究科総合基礎科学専攻数理情報コース
2004/03/04-05
DEWS 2004 [I-2: 1]
1
1. 本研究の概要
•
本研究ではWeb検索結果にリンク構造解析を加味したス
コアリングを行い，Web検索精度を向上させる手法を提
案する．
•
リンク構造解析手法としてPage Rankアルゴリズムを用い，
それを利用した以下の手法を提案する．
1. グループ化したWebページ群にPage Rankアルゴリズ
ムを適用する，静的スコアリング手法．
2. 検索結果集合に対してPage Rankアルゴリズムを適
用する，動的スコアリング手法．
3. 上記2つを併合する手法．
2004/03/04-05
DEWS 2004 [I-2: 1]
2
2. Page Rankアルゴリズム
～ 特徴 ～
•
被リンク数およびリンク元Webページの品質を考慮したスコアリング法．
•
得られるスコアはWeb全体における各Webページの被参照度を表す
固定値となり，検索語に左右されない．
～ 問題点 ～
•
関連しているが隣接関係に無いWebページに対するスコアリング効果
が低下する．
例）
他サイトへのリンクが別ページにある場合
リンク先サイトがトップページ以外へのリンクを拒否している場合
2004/03/04-05
DEWS 2004 [I-2: 1]
3
3. Webページのグループ化
～ 概要 ～
•
関連する複数のWebページをグループ化し，グループ内の各Webペー
ジの隣接関係を表面上削除する.
～ 利点 ～
•
Page Rankアルゴリズム適用時，関連しているが隣接関係には無い
Webページにもスコアリング効果が期待できる．
～ 手法 ～
•
サイト毎もしくはディレクトリ毎にグループ化を行う．
•
リンク構造をグループ化に対応したものに置き換える．
2004/03/04-05
DEWS 2004 [I-2: 1]
4
4. グループ化静的スコアリングイメージ図
【例1】
【例2】
【例3】
Page A
Page F
Page B
Page A
Page C
Page D
Page G
Page E
Page F
Page B
Page A-E
Page C-E
Page C, D, E を
グループ化
↓
Page C-E
Page H
サイト境界
Page G
Page F
Page A, B, C, D, E を
グループ化
↓
Page A-E
Page G
Page H
Page H
サイト境界
サイト境界
グループ化によるPage Rankスコアの変化
例
グループ化
1
2
なし
ディレクトリ
3
サイト
2004/03/04-05
サイト内部
サイト外部
Page A
Page B
Page C
Page D
Page E
Page F
Page G
Page H
0.244
0.345
0.139
0.218
0.281
0.111
0.217
0.111
0.000
0.000
0.057
0.110
0.057
0.110
0.000
0.423
0.423
0.154
DEWS 2004 [I-2: 1]
5
5. Page Rankの動的適用
～ 概要 ～
•
検索結果集合を対象としてPage Rankアルゴリズムを適用する．
～ 利点 ～
•
検索語に特化したスコアリングを行う事が出来る．
•
各Webページ特性を生かしたスコアリングを行う事が出来る．
～ 手法 ～
•
検索の結果，得られたWebページ集合についてリンク構造を抽出する．
•
リンク構造を元に，Page Rankアルゴリズムを適用する（手順 1）．
•
リンク構造に前述のグループ化を適用し，Page Rankアルゴリズムを
適用する(手順 2)．
•
2回のPage Rankアルゴリズム適用で得られたスコアを，一定の加重
値を考慮して併合する(手順 3)．
2004/03/04-05
DEWS 2004 [I-2: 1]
6
6. 動的スコアリングイメージ図
【 手順 1 】
【 手順 2 】
Page A
Page F
Page A
Page D-F
Page D, E, F を
グループ化
↓
Page D-F
Page B
Page C
検索結果集合
Page E
Page B
グループ境界
Page C
検索結果集合
動的スコアリングで得られるPage Rankスコア
検索結果集合内
Page Rankアルゴリズム
適用範囲
Page A Page B Page C
手順
1
2
3
Page D
グループ境界
検索結果集合外
Page D
Page E
Page F
検索結果集合内
1.000
0.000
0.000
0.000
0.496
検索結果集合に一部でも含まれるグループ
0.504
0.000
0.000
1.252
0.000
0.000
0.248
※ ( 手順 3 スコア ) ＝ ( 手順 1 スコア ) + { ( 手順 2 スコア ) × 0.5 }
2004/03/04-05
DEWS 2004 [I-2: 1]
7
7. 静的・動的スコアリングの併合
～ 概要 ～
•
得られた静的・動的スコアを一定の加重値を考慮して併合することで，
更なるWeb検索精度向上を図る．
～ 考察 ～
•
静的スコアリングにより，各Webサイトおよび各Webディレクトリの特性
を生かしたスコアリングが可能．
•
動的スコアリングにより，各Webページの特性と，各Webサイトおよび
各Webディレクトリの特性を両方とも生かした，検索語に特化したスコ
アリングが可能．
•
併合により，静的・動的スコアリングそれぞれが持つ問題点を補填す
ることが可能．
2004/03/04-05
DEWS 2004 [I-2: 1]
8
8. まとめと課題
～ まとめ ～
•
静的･動的スコアリングを併合することにより，通常のPage Rankアル
ゴリズムと比べてWeb検索精度を向上させることが可能であると思わ
れる．
～ 課題 ～
•
グループ化における，サイト境界およびディレクトリ境界決定の適正な
方法についての検証．
•
検索結果集合に対するPage Rankスコア，検索結果集合にグループ
化を考慮したPage Rankスコアを元に動的スコアを算出する際の，そ
れぞれの適正加重値の検証．
•
静的スコア，動的スコアを元に最終的なランキングを行う際の，それ
ぞれの適正加重値の検証．
•
動的スコア算出の必要時間を短縮するための効果的な手法の考案．
2004/03/04-05
DEWS 2004 [I-2: 1]
9
© Copyright 2024 ExpyDoc
