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

Slides:



Advertisements
Similar presentations
静岡大学情報学研究科 戸根木千洋 ユーザーイメージ収集 インターフェースの開発. 2 目次 背景と目的 研究の構成 研究の詳細 イメージ収集インターフェースの提案 映画イメージ収集システムの開発 システムの評価 今後の課題.
Advertisements

Software Engineering Laboratory, Department of Computer Science, Graduate School of Information Science and Technology, Osaka University 1 ソフトウェア部品推薦のための.
静脈画像を鍵とする暗号化手 法に関する研究 大山研究室 安藤のぞみ. 研究の背景、目的 近年、バイオメトリクス認証が注目されて いる 静脈は身体内部の情報 → 偽造に強い 環境に左右されることが少ない 利用者の心理的抵抗が軽減される オープンなネットワークへのバイオメトリ クス認証の適用 : Double.
電子書籍の検索機能の改善 木下研究室 201002713 鴫原 善寿. 背景 スマートフォンなどの携帯端末の普及と ともに電子書籍に注目が浴びた。中でも amazon の kindle など電子書籍の専用端末も 現れた。 電子書籍はデータなので本棚もいらず、 持ち運びも容易になるなど様々な恩恵を もたらした。
OWL-Sを用いたWebアプリケーションの検査と生成
ユーザーイメージ収集 インターフェイスの開発
円形管における3次元骨組解析への適用事例 平成16年9月17日 (株)アイエスシイ 犬飼隆義.
遺伝的アルゴリズムにおける ランドスケープによる問題のクラス分類
Building text features for object image classification
点対応の外れ値除去の最適化によるカメラの動的校正手法の精度向上
XHTML構文検証手法における スクリプト要素の静的解析アルゴリズム
国内線で新千歳空港を利用している航空会社はどこですか?
秘密のリンク構造を持つグラフのリンク解析
分散コンピューティング環境上の Webリンク収集システムの実装
参照共起分析の Webディレクトリへの適用
神奈川大学大学院工学研究科 電気電子情報工学専攻
時空間データからのオブジェクトベース知識発見
リンク構造を考慮したベクトル空間法によるWebグラフ分割手法に関する研究
卒業論文 最終発表 WWW情報検索 ナビゲーションシステムの設計と実装
卒業論文 最終発表 WWW情報検索 ナビゲーションシステムの設計と実装
卒業論文 最終発表 WWW情報検索 ナビゲーションシステムの設計と実装
マイクロシミュレーションにおける 可変属性セル問題と解法
テキストの類似度計算
第7章 データベース管理システム 7.1 データベース管理システムの概要 7.2 データベースの格納方式 7.3 問合せ処理.
大阪教育大学大学院教育学研究科 総合基礎科学専攻 中窪 仁
PlanetLab における 効率的な近隣サーバ選択法
高山建志 五十嵐健夫 テクスチャ合成の新たな応用と展開 k 情報処理 vol.53 No.6 June 2012 pp
3次元剛体運動の理論と シミュレーション技法
Java ソフトウェア部品検索システム SPARS-J のための リポジトリ自動更新機能の実現
サーバ負荷分散におけるOpenFlowを用いた省電力法
プログラム実行履歴を用いたトランザクションファンクション抽出手法
静的情報と動的情報を用いた プログラムスライス計算法
ベイジアンネット混合モデルによる 強化学習エージェントの方策改善
環境リスクマネジメントに関する 検索システム
第14章 モデルの結合 修士2年 山川佳洋.
WWW上の効率的な ハブ探索法の提案と実装
プリムのアルゴリズム 重み付きグラフG=(V,E)の任意の点集合 U⊂Vに対して一方の端点がUの中にあり、他方の端点がV-Uの中にあるような枝の中で最小の重みを持つものをlとすれば、枝lを含むような最小木が存在する。
The Web as a graph 末次 寛之 清水 伸明.
第7回 授業計画の修正 中間テストの解説・復習 前回の補足(クロックアルゴリズム・PFF) 仮想記憶方式のまとめ 特別課題について
TIME SIGNAL: 集合知を利用した赤信号点灯時間の取得手法
Internet広域分散協調サーチロボット の研究開発
Javaを対象としたソフトウェア部品 検索システムSPARS-Jの実験的評価
階層的位置表現への 広域化ビュー適用における追尾性向上
2018/9/10 ACL読み会 名古屋大学大学院 M2 佐藤・松崎研 土居裕典.
“SFC SUBWAY Maniacs” プロジェクト計画書
類似度を用いた WWW のリンク構造の解析 谷 研究室    栗原 伸行.
Webコミュニティ概念を用いた Webマイニングについての研究 A study on Web Mining Based on Web Communities 清水 洋志.
エピソード記憶に訴えるBookmarkless Bookmarkの実現
複数特徴量の重み付け統合による一般物体認識
片方向通信路を含む ネットワークアーキテクチャに於ける 動的な仮想リンク制御機構の設計と実装
Javaソフトウェア部品検索システムSPARS-Jの実験的評価
背景 課題 目的 手法 作業 期待 成果 有限体積法による汎用CFDにおける 流体構造連成解析ソルバーの計算効率の検証
○ 後藤 祥1,吉田 則裕2 ,井岡 正和1 ,井上 克郎1 1大阪大学 2奈良先端科学技術大学院大学
早稲田大学大学院 基幹理工学研究科 情報理工学専攻 後藤研究室 修士1年 魏 元
SIFTとGraph Cutsを用いた 物体認識及びセグメンテーション
ISO23950による分散検索の課題と その解決案に関する検討
構造的類似性を持つ半構造化文書における頻度分析
プログラムスライスを用いた凝集度メトリクスに基づく 類似メソッド集約候補の順位付け手法
設計情報の再利用を目的とした UML図の自動推薦ツール
メソッドの同時更新履歴を用いたクラスの機能別分類法
A-17 検索履歴のプライバシーを秘匿した ユーザクラスタリング
資料3-2 平成26年度 第3回技術委員会資料 次年度テーマの検討
欠陥検出を目的とした類似コード検索法 吉田則裕,石尾隆,松下誠,井上克郎 大阪大学 大学院情報科学研究科
わかりやすいパターン認識 第6章 特徴空間の変換 6.5 KL展開の適用法 〔1〕 KL展開と線形判別法 〔2〕 KL展開と学習パターン数
Webページタイプによるクラスタ リングを用いた検索支援システム
エイリアス関係を考慮した Javaプログラム用静的スライシングツール
学籍番号: 氏名:峯村孝征 指導教員:小林泰秀 准教授
識別子の読解を目的とした名詞辞書の作成方法の一試案
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

静的スコアリング例 ディレクトリ構造方式 リンク構造方式 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

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

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

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

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

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

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

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

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

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

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

各スコアリング結果比較 グループ化によるスコアの平均化 →適合文書の抽出能力低下 全文検索 静的スコア 動的スコア グループ化 - なし あり 最小値 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 グループ化によるスコアの平均化 →適合文書の抽出能力低下

最大値:グループ化なし > グループ化あり 最小値:グループ化なし < グループ化あり 各スコアリング結果比較 全文検索 静的スコア 動的スコア グループ化 - なし あり 最小値 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 < > グループ化有無でスコア分布傾向が変化 最大値:グループ化なし > グループ化あり 最小値:グループ化なし < グループ化あり

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ありがとうございました

付録

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

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

スコア併合式 併合スコア(p) = Wr×全文検索スコア(p) +Ws×静的スコア(p) +Wd×動的スコア(p) 動的スコア(p) = Wd1×動的スコア#1(p)   +Wd2×動的スコア#2(p)

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

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

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

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

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

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

各スコアリング評価比較 全文検索 静的スコア 動的スコア グループ化 - × ○ WRR 10 0.03090 0.03510 0.00162 0.00325 100 0.03895 0.04307 0.00043 0.00619 0.00492 DCG 0.19169 0.21926 0.00866 0.02417 0.43771 0.65954 0.02146 0.09893 0.09364 累積課題 9 1 29 23 2 8

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

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

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

スコア粒度調整 全文検索スコア リンク構造解析スコア 2乗根を適用 101のオーダーに圧縮 (対応範囲:1~100) 16乗根を適用 最小値: 2.2831 最大値: 30.2596 リンク構造解析スコア 最小値: 7.3143E-9 最大値: 4.8634E-1 2乗根を適用 101のオーダーに圧縮 (対応範囲:1~100) 16乗根を適用 10-1のオーダーに圧縮 (対応範囲:1~1.0E-16)

全文検索スコアベース 静的スコアリング評価比較 グループ化 - × ○ ×○ WRR 10 0.03090 0.09665 0.02960 0.10314 100 0.03895 0.10574 0.03872 0.11225 DCG 0.19169 0.56869 0.18330 0.56989 0.43771 1.31375 0.43811 1.32008 累積課題 9 17 8 29 37

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

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

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

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

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

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

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

適正重み係数調査結果 上位3パターン 全文 検索 提案手法 (1,1,1,0,0) (2,2,1,0,0) (1,1,2,0,0) WRR 10 0.03090 0.103139 100 0.03895 0.112253 0.112279 0.112088 DCG 0.19169 0.569888 0.568694 0.566949 0.43771 1.320078 1.314444 1.316460 累積課題 9 17 29 37

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

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

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

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

Vs tf-idf+PageRank Discounted Cumulative Gain

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