2006年度 WINGS発表 リンク構造を考慮したベクトル空間法による Webグラフ分割手法に関する研究 発表者 佐々木 雄一 1.背景 • WWW上には膨大な量のページ ・ 文書検索エンジンの問題 query answer 検索エンジン 1 2 3 約11.5億 query 検索エンジン answer 1 2 膨大な 検索結果 4 57 3 6: 1万 文書検索で目的にたどり着くのは難しい! 1.背景 • 膨大な量のページをどう扱うか? ・ グループ化を行う input グループB Webページ グループ化 システム output グループA グループC • 検索文字列以外の類似情報 • 情報の位置づけ 本研究では どのようにWebページからグループを構成するか? について扱う. 2.研究概要 • ベクトル空間法 • Webページからの自動的なグループ構成を行うための一般的手法 • 文書内容の類似度を計算する方法 文書di ベクトル空間 2つのベクトルのコサインを計算 [x1,x2,…,xn] [x1,x2,…,xn] 文書dj [y1,y2,…,yn] θ di θが近いほど類似 dj [y1,y2,…,yn] 文書内の単語の頻度 ベクトル空間法はリンク構造を考えていない 本論文ではリンク構造も考える 発表の流れ 1. 2. 3. 4. 5. 関連研究 提案手法 実装 実験 おわりに 3.関連研究 • リンク構造からのコミュニティ抽出に関する研究 – 参照の共起性に基づくWebコミュニティ発見手法 [村田 01] • リンクと文書両方の情報を用いたクラスタリング手法 に関する研究 – リンクと文書両方を考慮に入れたクラスタリングサーチエン ジンHyPursuit [Weiss 96] • 巨大なネットワークからのコミュニティ抽出に関する研 究 – ネットワーク分割に関する評価値Modularity Q を応用した 高速コミュニティ発見手法 [Clauset 04] 4.提案手法 • リンク構造も考慮に入れたベクトル空間法 どのように 扱うのか? 文書の内容 リンク構造 文書ベクトル Di ×α リンクベクトルLi [x1,x2,…,xn] [y1,y2,…,yn] [e1,e2,…,en] [f1,f2,…,fn] ×(1-α) : : : : [z1,z2,…,zn] [g1,g2,…,gn] Content-Linkベクトル Pi Di , (1 )Li 4.提案手法 • どのようにリンクベクトルを扱うのか? 適切にリンクを用いてグループ構築ができなければならない 村田の手法の完全二部グラフ構造を拡張利用 • 村田の手法におけるWebコミュニティ • 熱心な支持者(fans)から共通に張られているリンクを利用 • fansから形成される完全二部グラフ構造をWebコミュニティとして抽出 完全二部グラフ構造 fans Webコミュニティ 4.提案手法 • 完全二部グラフ構造からのWebコミュニティ 抽出の限界 • 完全二部グラフ構造という制約が厳しい • 現実のWebコミュニティは様々なリンク構造をもっている 完全二部グラフ構造 完全二部グラフ構造 Webコミュニティ Webコミュニティ fans fans 完全二部グラフ構造という制約が厳しい 完全二部グラフ構造という制約を緩和する必要がある 4.提案手法 • 完全二部グラフ構造を柔軟に解釈した b ,b ,b ,b からをリンクを1つ介している Webコミュニティ抽出 1 2 3 4 [1, 1, 1, 1] b1 fans p1 b2 [1, 1, 1, 1] p2 b3 fansから与えられる リンクベクトル p3 b4 [1, 1, 1, 2] 得られる類似度の表 b4からをリンクを 2つ介している p1 p2 p3 p1 ― 1.0 0.945 • p1とp2は酷似している p2 1.0 ― 0.945 • p1とp3はp1とp2に比べて似ていない p3 0.945 0.945 ― リンクベクトルを用いることで 完全二部グラフの構造を引継ぎ,さらに柔軟に解釈できる 4.提案手法 • 基準ページの配置 基準ページの問題 同じ向き 様々な位置に基準ページを配置 b5 基準ページ [1, 1, 1, 1] b1 fans b2 b8 [2, 2, 2, 2] p1 p2 p3 b3 b1 p1 b2 b4 p2 p3 b3 p1とp3の類似度が1 b4 b7 p1とp2とp3はWebコミュニティを構成 完全二部グラフを与えるようなWebページ だけを基点にするのは適切ではない b6 多くの視点を基にグループ構築 を判断することができる 4.提案手法 1 • リンクベクトルの提案 1 b Webページpi,基準ページbj 基準ページの総数k個 4 bjからpiに到達するまで辿る最短のリンクの数fn(pi,bj) 1 2 3 3 Li fn( pi , b1 ), fn( pi , b2 ),, fn( pi , bk ) pi = bj のときfn(pi,bj)=0とし 基準ページもリンクベクトルの式に含む 1 2 2 3 リンクベクトル 1 0 3 3 4.提案手法 • リンクベクトルのカスタマイズ 標準リンクベクトル リンク介した数を要素をとしてもつリンクベクトル score 1 score 2 +1 +1 score 3 • 1つリンクを介す度にベクトルの構成要 素が1ずつ加算される +1 カスタマイズ1 リンクの次数を考慮に入れた要素をもつリンクベクトル score x • 次数が高いほどリンクを介する加算値 が小さくなる score x + (1/ki+1/kj) +(1/ki+1/kj) • コミュニティの周りのページがグループ を構成しやすくなる 次数kj 次数ki • 次数重みベクトルと呼ぶことにする カスタマイズ2 リンクを介した数に重みをつけたリンクベクトル • リンクを辿るほど加算値が小さくなる score 1 +r r < 1.0 score 1+r +r2 +r2 score 1+r+r2 • リンクを辿る数を少なくしてもグループ 構成への影響を小さくできる • 距離重みベクトルと呼ぶことにする 5.実装 • リンク構造からグループを構築するための実装 実装言語はJavaで, グラフ構造を扱うためJavaパッケージのJUNGを使用した • 提案手法の実装 ‐ リンクベクトルの実装 ‐ カスタマイズされたリンクベクトルの実装 • クラスタリング手法の実装 ‐ 初歩的な階層クラスタリング手法である単連結法と完全連結法の実装 単連結法 最も類似した頂点を併合に用いる 完全連結法 最も類似していない頂点を併合に用いる 6.実験 • 実験設定 リンクベクトルがWebページに対してどのようなグループ構成をするのかを調 べる 実験に使う手法 • 単連結法を用いた距離重みなしベクトル • 単連結法を用いた次数重みベクトル • 単連結法を用いてr=0.8としたときの距離重みベクトル • 完全連結法を用いた距離重みなしベクトル 距離重みなしベクトルとは,標準のリンクベクトルと同じ 6.実験 • 実験設定 実験対象のデータ アメリカの政治に関するブログのリンク構造データ • 1490のWebページのリンク構造に関するデータをもつ • 1490のページのうち,758個が民主党,732個が共和党寄りのWebページ • 91%のリンクは同一コミュニティと結びついている その他の実験設定 200個のWebページが併合される毎に,サイズ10 以上のグループのデータを記録した すべてのWebページを基準ページとした 6.実験 • 実験結果1 単連結法を用いた距離重みなしリンクベクトルから得られる結果 併合ページ数200 民主の数 24 22 11 0 0 併合ページ数769 併合ページ数600 共和の数 1 2 0 68 11 民主党のグループができた 良い 混在するグループができた 悪い 民主の数 212 5 1 0 0 共和の数 7 214 15 15 12 民主の数 共和の数 316 9 10 413 2つのメイングループが併合され 1つになる直前 リンクベクトルを用いることで民主党,共和党の どちらかが大半を占めるグループが構成された 6.実験 • 実験結果2(カスタマイズ手法との比較) 2つのメイングループが併合されるまでのページ併合数 距離重みなしベクトル 併合ページ数769 民主の数 共和の数 316 9 10 413 次数重みベクトル 併合ページ数441 民主の数 147 11 0 21 0 0 距離重みなしベクトル 769 max 次数重みベクトル 441 距離重みベクトル 661 距離重みベクトル 併合ページ数661 共和の数 62 0 108 30 17 10 民主の数 共和の数 262 14 9 334 0 10 同一コミュニティに属するWeb ページをより多く含んでいる 次数重みベクトルでは早い段階でメイングループが併合した 原因 異なるコミュニティに属するハブ構造をもつWebページ同士の類似度が高くなったため 6.実験 • 実験結果2(カスタマイズ手法との比較) 距離重みなしベクトルと距離重みベクトルの比較 ページ併合数 距離重みなしベクトル 民主の数 400 32 30 2 600 212 5 共和の数 2 1 112 7 214 r=0.8とした距離重みベクトル 民主の数 共和の数 65 33 2 1 2 149 241 5 10 247 r=0.8の距離重みベクトルは距離重みなしベクトルに比べて大きなグループを構成した 原因 リンクを辿るほどリンクベクトルのスコアの特徴が失われたため 6.実験 • 実験結果3(単連結法と完全連結法の比較) ■ 単連結法と完全連結法の特徴を強く示した結果が得られた - 単連結法の特徴 大きなグループがさらに大きなグループを構築しやすくなる - 完全連結法の特徴 大きなグループ同士が結びつきにくくなり,過剰にグループができる ページ併合数 単連結法が構成する グループ数 完全連結法が構成する グループ数 200 5 4 400 7 5 600 5 13 800 1 22 989 1 1 ■ 完全連結法では最後の方まで2つのメイングループは併合されなかった 2つのメイングループが併合されるまでのページ併合数 単連結法 769 同一コミュニティに属するWeb max 完全連結法 960 ページを十分含んでいる 実験では最も良い結果を得ている 6.実験 • 実験結果4(単連結法と完全連結法の比較) • メイングループが1つになる直前 - 四角は民主党,丸は共和党を表す - 同じ色は同一グループを表す 単連結法を用いた実験結果 完全連結法を用いた実験結果 7.おわりに • まとめ • Content-Linkベクトル提案 • リンクベクトルの設計 • リンクベクトルのカスタマイズ • Webページのリンク構造への実験と考察 7.おわりに • 今後の課題 • 計算量の改善 • 基準ページの選択とWebページのグループ構成へ の影響に関する実験調査 • クラスタリング手法の検討 • 他手法との実験比較 • 文書内容の導入 • 多くのデータに対する応用 • コンテンツ内容の調査
© Copyright 2024 ExpyDoc