参照共起分析の
Webディレクトリへの適用
NTT未来ねっと研究所
○原田昌紀 風間一洋 佐藤進也
[email protected]
研究の背景
サーチエンジン
Webディレクトリ
=ロボット+全文検索エンジン
○ Webページ単位で詳細な ○
検索ができる。
○ 網羅性が高い。
○
× 質の低いWebページが
検索される(スパムもある)。 ×
=人手で収集、評価、分類
Webサイト単位で階層的に
分類されている。
完成度の高いWebサイト
のみが登録されている。
網羅性が低い。
維持と構築に要する
人的コストが問題。
ロボットが収集したデータを利用して、
Webディレクトリの構築を自動化できないか?
発表の概要
研究の目的とアプローチ
関連研究
Webディレクトリ拡大手順の提案
関連Webサイト発見アルゴリズム(2種類)
評価実験
まとめ
本研究の目的とアプローチ
目的:Webディレクトリの自動拡大の実現
アプローチ


各カテゴリに分類されたWebサイト群を元に、
ロボットで収集したデータから、
それらに関連するWebサイトを発見し、
登録Webサイト数を増大させる。
ハイパーリンクによる参照関係の解析を応用
 与えられたWebサイト群に関連し、
重要度の高いWebサイトを発見する
ことが狙い。
関連研究: テキストの自動分類
テキストの自動分類

テキストをあらかじめ決められたカテゴリに分類する。
ハイパーテキストの自動分類


ノードをあらかじめ決められたカテゴリに分類する。
近傍のノードの分類結果によって補正する。
問題点


多数のカテゴリへの高精度の分類は困難。
Web上のテキストは多様であり、特に難しい。
テキストの自動分類によるWebディレクトリ構築は困難。
→テキストの内容を用いない方法を検討する。
関連研究:特定トピックのオーソリティ発見
HITS [Kleinberg1998]

トピックを表すキーワード
の検索結果の近傍から
オーソリティとハブを抽出。
・・・
・・・
ハブ
オーソリティ
オーソリティ…多数のハブから参照される、重要なWebページ。
ハブ…多数のオーソリティを参照する、リンク集的なWebページ。
カテゴリ名によるオーソリティ発見…詳細な分類には不向き。
例:ゲーム全般
/ゲーム/
ゲーム販売店
/ショッピング/趣味とおもちゃ/ゲーム/
ゲーム開発企業 /ビジネス/エンターテインメント/ゲーム/
関連研究: 関連Webページ発見手法
参照共起関係

共通のリンク元でハイパーリンクの位置がL以内にあること。
関連Webページ
L以内
L以内
:
リンク6
リンク7
リンク8
リンク9
:
シードWebページ
関連Webページ
関連Webページ
関連Webページ発見アルゴリズム

与えられたWebページと関連するオーソリティを発見する。
→ Webディレクトリに登録すべきWebサイトを発見できる。
Webディレクトリ拡大手順
1. 大域Webグラフを作成する。
2. 各カテゴリで関連Webサイトを発見する。
3. 重複したWebサイトを除去する。
1.大域Webグラフの作成
ロボットで大量のWebページを収集し、それらの
参照関係からWebグラフを作成する。
WWWサーバ間のハイパーリンクのみ辺とする。
Webサイトを点としたWebグラフを作成。


Webディレクトリにおける検索の単位。
実装では同じサーバで同じパスを持つファイル群を
Webサイトとみなした。
http://www.ntt.co.jp/product/
http://www.ntt.co.jp/product/index-j.html
http://www.ntt.co.jp/product/product.html
http://www.ntt.co.jp/product/*
2.関連Webサイト発見アルゴリズムの適用
各カテゴリに登録されているWebサイト群に、
それらと関連するオーソリティを加える。
例:ビジネス/食品/飲料/酒類
http://www.asahibeer.co.jp/
http://www.gekkeikan.co.jp/
http://www.kirin.co.jp/
http://www.moritakk.com/
http://www.ozeki.co.jp/
http://www.sapporobeer.co.jp/
http://www.suntory.co.jp/
関連Webサイト発見
アルゴリズムを適用
http://www.asahibeer.co.jp/
http://www.gekkeikan.co.jp/
http://www.kirin.co.jp/
http://www.moritakk.com/
http://www.ozeki.co.jp/
http://www.sapporobeer.co.jp/
http://www.suntory.co.jp/
http://www.budweiser.co.jp/
http://www.takara.co.jp/
http://www.heineken.co.jp/
http://www.kirin-seagram.co.jp/
http://j-entertain.co.jp/guiness/
http://www.kizakura.co.jp/
http://www.hakutsuru.co.jp/
:
関連度
22.1
19.5
14.4
12.5
11.8
8.8
8.2
:
3.重複Webサイトの削除
重複して発見されたWebサイトは関連度が最大の
カテゴリのみに残す。
ビジネス/食品/飲料
http://www.cocacola.co.jp/
http://www.morinagamilk.co.jp/
http://www.nestle.co.jp/
http://www.ucc.co.jp/
http://www.yakult.co.jp/
http://www.ajinomoto.co.jp/
http://www.nipponham.co.jp/
http://www.sangaria.co.jp/
http://www.dydo.co.jp/
http://www.ucc.co.jp/
http://www.cclemon.com/
:
関連度
9.9
8.9
8.4
8.1
7.7
5.8
:
ビジネス/食品/食材・調味料
http://www.hanamaruki.co.jp/
http://www.heiwa-food.co.jp/
http://www.soysauce.or.jp/
http://www.kagome.co.jp/
http://www.marukome.co.jp/
関連度
http://www.ajinomoto.co.jp/ 11.1
http://www.nipponham.co.jp/ 9.2
http://www.higeta.co.jp/
8.3
http://www.takeya-miso.co.jp/ 7.7
http://nitanda.com/
5.9
http://www.aohata.co.jp/
5.7
:
:
関連Webサイト発見アルゴリズム
関連Webページ発見アルゴリズムを拡張。


複数のシードに関連するWebサイトを発見する。
ステップ3で比較可能な関連度を出力する。
(1) Companion+

シードセットの近傍にHITSを適用し、オーソリティを発見。
(2) MultiCocitation

多くのシードと参照共起関係にあるWebサイトを発見。
(1) Companion+
Companion+[豊田2000]を複数シードに拡張。

シードセット全体の近傍からオーソリティを発見する。
(近傍:参照元Webサイト+参照共起関係にあるWebサイト)

関連度=
(オーソリティスコア)2
×近傍Webサイト数
シードセット
(2) MultiCocitation
Cocitation[Dean1998]を複数シードに拡張。

多くの異なるシードと参照共起関係にあるWebサ
イトを発見。
関連度=参照共起関係にあるシードの数 +
Σ
0.1× シードと参照共起する回数
シード
シードセット
関連Webサイト(関連度: 1.3)
関連Webサイト(関連度: 2.2)
評価実験: 対象データ
Webディレクトリ

Open Directory Projectの日本語カテゴリ
http://dmoz.org/World/Japanese/
 登録Webサイト数
6,143URL
 カテゴリ数
702
大域Webグラフ

サーチエンジンODINの検索対象Webページ
 Webディレクトリの登録サイトを起点として収集。
 総Webページ数
約1130万URL
辺となるハイパーリンク 約1350万本
辺の起点 約80万個,辺の終点 約110万個
実験1: 精度の評価
関連Webサイトが正しいカテゴリに配置されるか?

各カテゴリから、評価用Webサイトを一つずつ取り出す。

それらを除いたWebディレクトリに拡大手順を施す。

評価用Webサイトが発見されたときの精度を評価。
精度=
元々のカテゴリで発見された評価用Webサイト
評価用Webサイトのうち発見されたもの
注意:元々Webディレクトリに登録されていたWebサイトのみを評価。
実験1:精度の評価結果
0.9
0.8
MultiCocitation
0.7
Companion+
精度
0.6
0.5
0.4
0.3
各カテゴリで最大N件の関連Web
サイトを発見した場合の精度
0.2
0.1
0
5
10
15
20
25
30
N
MultiCocitationは実用的な精度を達成。
Companion+ではトピックドリフトが発生。
 被参照数の大きいシードにのみ関連するWebサイトが発見
されやすい。
実験1:シードセットサイズと発見精度
登録Webサイト数が大きいカテゴリでは精度が低下
シード数が大きいカテゴリは、他のカテゴリの関連Web
サイトを奪うことがある。
→関連度の定義に改善の余地がある。
Companion+
MultiCocitation
1
0.9
0.8
精度(N=20)

0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
1~5
6~10
11~15
16~20
シードセットサイズ
21~25
実験2-1: 適合度の評価
被験者:ネットワーク分野の研究者8名。
カテゴリ:被験者がよく知っている分野を2つ。
関連Webサイトのトピックとの適合性を判断。
 適合する
+2点
 どちらかといえば適合する
+1点
 評価不能(アクセスできないなど) 0点
 どちらかといえば適合しない
-1点
 適合しない
-2点

カテゴリの適合度=関連Webサイト全体の平均点
注意:分類精度の評価とは異なる。
実験2-1: 適合度の評価
Companion+ 平均0.99
MultiCocitation 平均1.44
カテゴリによって適合度の高低がある。

適合度
Companion+
MultiCocitation
2
1.8
1.6
1.4
1.2
1
0.8
0.6
0.4
0.2
0
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
カテゴリ
× アート/映画/洋画
○ /音楽/ビートルズ
○ニュース/新聞
実験2-1: 適合度の評価
適合度の低いカテゴリがある理由

リンク集における分類と、Webディレクトリの分類の不一致。
例:アート/映画/洋画…邦画のWebサイトが発見される。

近傍Webグラフが小さい
カテゴリでは、少数の関
連Webサイトしか得られ
ない。
シードセット中に被参照
数の大きいWebサイト
が一つは必要。
関連Webサイトの適合度
2.5
2
1.5
1
0.5
0
0
5000
10000
近傍Webグラフのサイズ
15000
実験2-2: 重要度の評価
登録する価値があるWebサイトが発見されるか?

知名度、信頼性、情報量、オリジナリティ、デザインで判断。
 登録すべき
+2点
 どちらかといえば登録すべき
+1点
 評価不能(アクセスできないなど)
0点
 どちらかといえば登録すべきでない
-1点
 登録すべきではない
-2点
各カテゴリで重要度(平均点)を比較


シードセットのWebサイト。
発見された関連Webサイトのうち、「適合する」あるいは
「どちらかといえば適合する」Webサイト
実験2-2:重要度の評価結果
Companion+の評価

シードセット 平均1.00
Companion+ 平均0.96
MultiCocitation 平均0.74
被参照数の大きいWebサ
イトを発見しやすい。
→トピックに適合していれ
ば、重要なWebサイト。
MultiCocitationの評価


網羅的なリンク集の影響
で、重要度の低いWebサ
イトを発見しやすい。
シードセットの重要度と正
の相関がある。
関連Webサイトの重要度
2
1.5
1
0.5
0
-1
-0.5
0
1
-1
-1.5
シードセットの重要度
2
まとめと今後の課題
関連Webページ発見アルゴリズムを拡張し、
Webディレクトリの自動拡大を実現した。


多数のカテゴリを持つWebディレクトリでも、高い精度で
関連Webサイトを発見できた。
シードセットの重要度が高いときには、トピックに適合し、
重要度の高いWebサイトを発見できた。
今後の課題


適合度と重要度を両立するアルゴリズムの検討。
カテゴリ間の関係(階層構造)の利用。
http://odin.ingrid.org/ にてデモシステムを公開予定。
ダウンロード

シードセット