Webページのグループ化による 静的動的スコアリング

Presentation on theme: "Webページのグループ化による 静的動的スコアリング"— Presentation transcript:

1 Webページのグループ化による 静的動的スコアリング
大阪教育大学大学院 教育学研究科 数理情報コース 中窪仁

2 他の手法と全文検索を併用し，精度向上を図る
背景 WWW空間上には膨大な情報が存在 必要な情報のみの抽出は困難 ロボット型Web検索システム 大量の情報を蓄積 全文検索により必要と思われる情報を抽出 全文検索のみによる検索精度向上は困難 他の手法と全文検索を併用し，精度向上を図る

3 関連研究 リンク構造解析による手法 PageRankアルゴリズム HITSアルゴリズム 各Webページの有用性を示す
Scam Web*1の影響を受けにくい HITSアルゴリズム 類似情報をもつWebページ群の抽出が可能 *1 Scam Web: Webページのスコアをあげるため，複数ダミーページからリンクを行う構造

4 PageRankアルゴリズム概要 基本概念 スコアの特徴 ランダムウォークモデル リンク行為＝リンク先Webページの推薦
検索語句に左右されない静的スコア

5 HITSアルゴリズム概要 基本概念 スコアの特徴 Webページを2種類の観点で評価 類似情報をもつWebページ群を抽出可能
情報源として有用なWebページ（Authority） リンク集として有用なWebページ（Hub） スコアの特徴 類似情報をもつWebページ群を抽出可能 検索語句に左右される動的スコア

6 各既存手法の問題点 PageRankアルゴリズム HITSアルゴリズム リンク行為＝推薦行為？ 既知の問題
特定ページ以外へのリンクを拒否するWebサイト 掲示板などの揮発性情報 HITSアルゴリズム 既知の問題 常に適切なコミュニティを抽出できるとは限らない

7 × 各既存手法の問題点 解決案 PageRankアルゴリズム 問題発生の原因 問題解決案 リンク構造上隣接関係を基にしていること
再帰的に解決されるリンク構造上隣接関係を考慮 アルゴリズムの拡張 リンク構造の拡張 リンク元 リンク先 × 中継点 中継によりリンク元の影響力が減衰

8 各既存手法の問題点 解決案 HITSアルゴリズム 問題発生の原因 問題解決案 検索語句に関係ないWebページが考慮されること
アルゴリズム適用対象の精査 検索語句との関連性を考慮 アルゴリズム 適用範囲 検索語句に無関係のWebページが存在 全文検索 結果集合

9 提案手法 グループ化 静的/動的スコアリング ランキング Webページを一定法則においてグループ化 グループ化を併用しリンク構造解析を適用
複数スコアの併合により最終評価を決定

10 提案システム 全文検索スコア スコアリング 動的スコア#1 グループ化 動的スコア#2 静的スコア ランキング リンク構造データ
全文検索結果 スコアリング 文書データ ランキング リンク構造データ 動的スコア#1 静的スコア グループ化 動的スコア#2

11 グループ化 目的 基本概念 リンク構造上隣接関係の拡張 Webページ集合への意味付与 類似情報をもつWebページ集合をグループ化
類似情報：同一作成者/同一コンテンツ扱い 2種類の方式：ディレクトリ構造/リンク構造 グループ内リンク構造を削除

12 グループ化アルゴリズム ディレクトリ構造方式 リンク構造方式 B C E D A B C E D A HTML Root HTML Root
Document Root Document Root

13 静的スコアリング 目的 基本概念 Webページの重要度を決定 PageRankアルゴリズム問題点を軽減 スコアリング対象は全Webページ
グループ化済みリンク構造を解析/評価

14 静的スコアリング例 ディレクトリ構造方式 リンク構造方式 B C E D A H G F B C E D A H F G B C E D A
Web Site Web Site

15 動的スコアリング 目的 基本概念 検索語句依存のWebページ重要度を決定 HITSアルゴリズム問題点を軽減
スコアリング対象は全文検索結果集合 グループ化なしリンク構造を解析/評価（#1） グループ化ありリンク構造を解析/評価（#2）

16 動的スコアリング例 動的スコア#1 動的スコア#2 U Y U Y V W X Z V W X Z Retrieved Documents

17 ランキング 目的 基本概念 複数スコアを併合し，最終的なスコアを決定 各スコアの特性を生かす併合方式を採用 各スコアの粒度を揃えた上で併合
重み付け加算を利用 重み係数の適正値は実験により決定 各スコアの粒度を揃えた上で併合 各スコアに累乗根を適用

18 実験 目的 実験項目 提案手法の有効性を検証 既存手法との比較検証 グループ化評価 全文検索/静的/動的スコア単体評価
併合スコア評価/重み係数最適値検証

19 プロトタイプ 全文検索 リンク構造解析 可変長グラムベースインデクス tf-idf法+確率モデルによるスコアリング
スコアリング結果上位2500件を抽出 リンク構造解析 PageRankアルゴリズムによるスコアリング

20 検索対象 NTCIR-4 Web テストコレクション*2 文書データ リンク構造データ NW100G-01（元HTMLデータ100GB分）
Webページ総数：約1100万Webページ リンク構造データ リンク総数：約8000万リンク *2 NTCIR: 情報検索システム評価用テストコレクション構築プロジェクト （NII-NACSIS Test Collection for IR Systems）

21 検索課題 NTCIR-4 Web Task B Formal Run 本実験で利用した検索課題 検索課題総数：300課題
有効課題数：197課題 本実験で利用した検索課題 検索課題数：77課題 NTCIR-4 Webにおける有効課題より抽出 全文検索による抽出文書数が一定数以上の検索課題

22 評価手法 Weighted Reciprocal Rank（WRR） Discounted Cumulative Gain（DCG）
高適合文書の抽出ランクを評価 Discounted Cumulative Gain（DCG） 適合文書抽出の連続性を評価 11点平均適合率（適合率，再現率） 特定再現率における適合率を評価 累積適合課題数 適合文書抽出課題数を評価

23 グループ化処理結果 グループあたりWebページ数に偏り グループ化手法の再検討が必要 グループあたりリンク数に影響する可能性 Webページ数
最小値 1 平均値 5 最大値 30,466 中央値 グループあたりWebページ数に偏り グループあたりリンク数に影響する可能性 グループ化手法の再検討が必要

24 > < グループ化処理結果比較 静的スコアリング：ノード数減/リンク数減 動的スコアリング：ノード数減/リンク数増
なし あり ノード数 23,670,000 4,500,000 192,500 124,041 リンク数 79,700,000 18,140,000 95,848 120,292 > < 静的スコアリング：ノード数減/リンク数減 動的スコアリング：ノード数減/リンク数増 提案手法において期待した処理結果

25 各スコアリング結果比較 グループ化によるスコアの平均化 →適合文書の抽出能力低下 全文検索 静的スコア 動的スコア グループ化 － なし
あり 最小値 2.283 7.314E-9 3.344E-8 6.846E-5 7.675E-5 平均値 10.389 4.223E-8 2.223E-7 4.000E-4 6.369E-4 最大値 30.260 2.613E-4 4.199E-7 4.863E-1 5.687E-2 中央値 9.482 8.386E-9 2.261E-7 7.012E-5 5.101E-4 グループ化によるスコアの平均化 →適合文書の抽出能力低下

26 最大値：グループ化なし > グループ化あり 最小値：グループ化なし < グループ化あり
各スコアリング結果比較 全文検索 静的スコア 動的スコア グループ化 － なし あり 最小値 2.283 7.314E-9 3.344E-8 6.846E-5 7.675E-5 平均値 10.389 4.223E-8 2.223E-7 4.000E-4 6.369E-4 最大値 30.260 2.613E-4 4.199E-7 4.863E-1 5.687E-2 中央値 9.482 8.386E-9 2.261E-7 7.012E-5 5.101E-4 < > グループ化有無でスコア分布傾向が変化 最大値：グループ化なし > グループ化あり 最小値：グループ化なし < グループ化あり

27 各スコアリング評価 Weighted Reciprocal Rank
グループ化あり静的スコア単体では 適合文書抽出不可能

28 各スコアリング評価 Weighted Reciprocal Rank
動的スコアはランクにより優位性が変化

29 静的スコアリング評価結果詳細 手法別 適合文書抽出課題数
未抽出 グループ化有無 グループ化なし グループ化なし グループ化あり グループ化あり グループ化なし：61% / グループ化あり：13%

30 動的スコアリング評価結果詳細 手法別 適合文書抽出課題数
未抽出 グループ化有無 グループ化なし グループ化なし グループ化あり グループ化あり グループ化なし：32% / グループ化あり：31%

31 各スコアリング手法特徴 静的スコアリング グループ化なし グループ化あり スコアの分布範囲 広 狭 スコアリング効果発揮帯 高ランク帯
低ランク帯 ランクへの影響度 高 低 適合課題中の占有率 82% 18% 動的スコアリング 同等 42% 58%

32 スコア併合式検討 各スコア単体ではランクへの影響が微小 グループ化有無でスコアの特徴が正反対 特定のスコアをベースにスコア併合を行う
全文検索スコアをベースと扱う グループ化有無ともに併合を行う グループ化なし静的スコアを考慮

33 検討後スコア併合式 併合スコア（p） = Wr×全文検索スコア（p） ＋静的スコア（p） ＋動的スコア（p）
静的スコア（p） = Ws1×グループ化なし静的スコア（p） 　　＋Ws2×グループ化あり静的スコア（p） 動的スコア（p） = Wd1×動的スコア#1（p） 　　＋Wd2×動的スコア#2（p）

34 適正重み係数調査結果 (Wr, Ws1, Ws2, Wd1, Wd2) [ Rank ]
Wr = {1, 2}, Wx = {0, 1, 2}, x∈{s1, s2, d1, d2} … … … … 動的スコアなし 動的スコア#1 or #2 単体 動的スコア併合

35 vs. “tf-idf+PageRank” Weighted Reciprocal Rank
+6% +180%

36 vs. “tf-idf+PageRank” 11点平均適合率
+140% +6%

37 提案手法考察 グループ化 手法 効果 グループ化の有効性を確認 グループ化手法については再検討が必要 各グループの粒度に格差
静的スコアリング：ノード数減/リンク数減 動的スコアリング：ノード数減/リンク数増 グループ化の有効性を確認 グループ化手法については再検討が必要

38 ランキングを大きく変動させることは不可能
提案手法考察 静的スコアリング グループ化適用によるスコアへの影響 スコア適用先が変更 グループ化なしスコアと異なる文書にスコアリング スコアの平均化 ランキングへの影響度が減少 既存手法では抽出できない文書を抽出可能 ランキングを大きく変動させることは不可能

39 提案手法考察 動的スコアリング 精度面で非常に劣る結果 各スコアリングの特徴 グループ化手法検討後に再実験が必要 不適合文書を多く抽出
グループ化精度の影響 各スコアリングの特徴 #1：既存手法と同様の文書に僅かな影響力 #2：既存手法と異なる文書に大きな影響力 グループ化手法検討後に再実験が必要

40 提案手法考察 ランキング 評価結果 スコア併合式/適正重み係数 提案手法による精度向上を確認 動的スコアを併合しない算出式が最良結果
グループ化精度の影響 既存手法に比べ6%程度の精度向上 スコア併合式/適正重み係数 今回の実験では決定不可能 提案手法による精度向上を確認

41 まとめ グループ化によるランキング手法を提案 今後の課題 各提案手法の有効性を確認 提案手法による精度向上を確認 グループ化手法の再検討
スコア併合式/適正重み係数の検討

42 ありがとうございました

43 付録

44 PageRankアルゴリズム例 100 50 53 50 9 3

45 HITSアルゴリズム例 スコアリング Root 適用手順 H: 0 A: 0.408 A: 0.816 H: 0.408 A: 0 Base

46 スコア併合式 併合スコア（p） = Wr×全文検索スコア（p） ＋Ws×静的スコア（p） ＋Wd×動的スコア（p）
動的スコア（p） = Wd1×動的スコア#1（p） 　　＋Wd2×動的スコア#2（p）

47 評価方式 NTCIR-4 Web Task B 適合判定結果 多値適合レベル 適合文書 不適合文書 高適合，適合，部分適合，不適合の4レベル

48 処理時間 全文検索 所要時間 全文検索用インデクス作成 2080min. 検索課題あたり平均検索時間 707msec. リンク構造解析
ドキュメントID→PageRankスコア算出用データ 40min. グループ化なし静的スコアリング 1004min. グループ化あり静的スコアリング 4min. PageRankスコア算出結果→ドキュメントID 14min. グループ化なし動的スコアリング 16min. グループ化あり動的スコアリング 20min.

49 ディスク /メモリ使用量 全文検索 外部記憶使用量 元データ 100GB インデクス 30.2GB リンク構造解析 リンク構造データ
PageRankスコア算出用データ 1.5GB 内部記憶使用量 PageRankスコア算出プログラム 1.6GB

50 各スコアリング評価 Discounted Cumulative Gain

51 各スコアリング評価 累積適合課題数

52 各スコアリング評価 11点平均適合率

53 各スコアリング評価比較 全文検索 静的スコア 動的スコア グループ化 － × ○ WRR 10 0.03090 0.03510
100 DCG 累積課題 9 1 29 23 2 8

54 各スコアリング評価比較 Weighted Reciprocal Rank

55 各スコアリング評価比較 Discounted Cumulative Gain

56 各スコアリング評価比較 累積適合課題数

57 スコア粒度調整 全文検索スコア リンク構造解析スコア 2乗根を適用 101のオーダーに圧縮 （対応範囲：１～１００） 16乗根を適用
最小値： 最大値： リンク構造解析スコア 最小値： E-9 最大値： E-1 2乗根を適用 101のオーダーに圧縮 （対応範囲：１～１００） 16乗根を適用 10-1のオーダーに圧縮 （対応範囲：1～1.0E-16）

58 全文検索スコアベース 静的スコアリング評価比較
グループ化 － × ○ ×○ WRR 10 100 DCG 累積課題 9 17 8 29 37

59 全文検索スコアベース評価比較 Weighted Reciprocal Rank

60 全文検索スコアベース評価比較 Discounted Cumulative Gain

61 全文検索スコアベース評価比較 累積適合課題数

62 全文検索スコアベース評価比較 11点平均適合率

63 全文検索スコアベース評価比較 Weighted Reciprocal Rank

64 全文検索スコアベース評価比較 Discounted Cumulative Gain

65 全文検索スコアベース評価比較 累積適合課題数

66 適正重み係数調査結果 上位3パターン 全文 検索 提案手法 （1,1,1,0,0） （2,2,1,0,0） （1,1,2,0,0） WRR
10 100 DCG 累積課題 9 17 29 37

67 上位3パターン評価結果比較 Weighted Reciprocal Rank

68 上位3パターン評価結果 Discounted Cumulative Gain

69 上位3パターン評価結果 累積適合課題数

70 上位3パターン評価結果 11点平均適合率

71 Vs tf-idf+PageRank Discounted Cumulative Gain

72 Vs tf-idf+PageRank 累積適合課題数