2006年度 WINGS発表リンク構造を考慮したベクトル空間法による Webグラフ分割手法に関する研究発表者佐々木雄一１．背景 • WWW上には膨大な量のページ・文書検索エンジンの問題 query answer 検索エンジン 1 2 3 約11.5億 query 検索エンジン answer 1 2 膨大な検索結果 4 57 3 6： 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．実験 • 実験結果１単連結法を用いた距離重みなしリンクベクトルから得られる結果併合ページ数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ページのグループ構成への影響に関する実験調査 • クラスタリング手法の検討 • 他手法との実験比較 • 文書内容の導入 • 多くのデータに対する応用 • コンテンツ内容の調査