シードセット

参照共起分析の
Webディレクトリへの適用
NTT未来ねっと研究所
○原田昌紀風間一洋佐藤進也
[email protected]
研究の背景
サーチエンジン
Webディレクトリ
＝ロボット＋全文検索エンジン
○ Webページ単位で詳細な ○
検索ができる。
○ 網羅性が高い。
○
× 質の低いWebページが
検索される（スパムもある）。 ×
＝人手で収集、評価、分類
Webサイト単位で階層的に
分類されている。
完成度の高いWebサイト
のみが登録されている。
網羅性が低い。
維持と構築に要する
人的コストが問題。
ロボットが収集したデータを利用して、
Webディレクトリの構築を自動化できないか？
発表の概要
研究の目的とアプローチ
関連研究
Webディレクトリ拡大手順の提案
関連Webサイト発見アルゴリズム（２種類）
評価実験
まとめ
本研究の目的とアプローチ
目的：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サイトを除去する。
１．大域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/＊
２．関連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
：
３．重複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サイトを発見する。
ステップ３で比較可能な関連度を出力する。
(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万個
実験１：精度の評価
関連Webサイトが正しいカテゴリに配置されるか？

各カテゴリから、評価用Webサイトを一つずつ取り出す。

それらを除いたWebディレクトリに拡大手順を施す。

評価用Webサイトが発見されたときの精度を評価。
精度＝
元々のカテゴリで発見された評価用Webサイト
評価用Webサイトのうち発見されたもの
注意：元々Webディレクトリに登録されていたWebサイトのみを評価。
実験１：精度の評価結果
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サイトが発見
されやすい。
実験１：シードセットサイズと発見精度
登録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
実験２-1：適合度の評価
被験者：ネットワーク分野の研究者８名。
カテゴリ：被験者がよく知っている分野を２つ。
関連Webサイトのトピックとの適合性を判断。
 適合する
＋２点
 どちらかといえば適合する
＋１点
 評価不能（アクセスできないなど）０点
 どちらかといえば適合しない
－１点
 適合しない
－２点

カテゴリの適合度＝関連Webサイト全体の平均点
注意：分類精度の評価とは異なる。
実験２-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
カテゴリ
× アート/映画/洋画
○ /音楽/ビートルズ
○ニュース/新聞
実験２-1：適合度の評価
適合度の低いカテゴリがある理由

リンク集における分類と、Webディレクトリの分類の不一致。
例：アート/映画/洋画…邦画のWebサイトが発見される。

近傍Webグラフが小さい
カテゴリでは、少数の関
連Webサイトしか得られ
ない。
シードセット中に被参照
数の大きいWebサイト
が一つは必要。
関連Webサイトの適合度
2.5
2
1.5
1
0.5
0
0
5000
10000
近傍Webグラフのサイズ
15000
実験２-２：重要度の評価
登録する価値があるWebサイトが発見されるか？

知名度、信頼性、情報量、オリジナリティ、デザインで判断。
 登録すべき
＋２点
 どちらかといえば登録すべき
＋１点
 評価不能（アクセスできないなど）
０点
 どちらかといえば登録すべきでない
－１点
 登録すべきではない
－２点
各カテゴリで重要度（平均点）を比較


シードセットのWebサイト。
発見された関連Webサイトのうち、「適合する」あるいは
「どちらかといえば適合する」Webサイト
実験２-２：重要度の評価結果
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/ にてデモシステムを公開予定。

Download Report