参照共起分析の Webディレクトリへの適用 NTT未来ねっと研究所 ○原田昌紀　風間一洋　佐藤進也 harada@ingrid.core.ntt.co.jp

研究の背景 サーチエンジン Webディレクトリ ロボットが収集したデータを利用して、 Webディレクトリの構築を自動化できないか？ ＝ロボット＋全文検索エンジン ○　Webページ単位で詳細な 　　検索ができる。 ○　網羅性が高い。 ×　質の低いWebページが 　　検索される（スパムもある）。 Webディレクトリ ＝人手で収集、評価、分類 ○　Webサイト単位で階層的に 　　分類されている。 ○　完成度の高いWebサイト 　　のみが登録されている。 ×　網羅性が低い。 維持と構築に要する 人的コストが問題。 ロボットが収集したデータを利用して、 Webディレクトリの構築を自動化できないか？

発表の概要 研究の目的とアプローチ 関連研究 Webディレクトリ拡大手順の提案 関連Webサイト発見アルゴリズム（２種類） 評価実験 まとめ

本研究の目的とアプローチ 目的：Webディレクトリの自動拡大の実現 アプローチ 各カテゴリに分類されたWebサイト群を元に、 ロボットで収集したデータから、 それらに関連するWebサイトを発見し、 登録Webサイト数を増大させる。 ハイパーリンクによる参照関係の解析を応用 与えられたWebサイト群に関連し、 重要度の高いWebサイトを発見する ことが狙い。

関連研究： テキストの自動分類 テキストの自動分類 ハイパーテキストの自動分類 問題点 多数のカテゴリへの高精度の分類は困難。 関連研究：　テキストの自動分類 テキストの自動分類 テキストをあらかじめ決められたカテゴリに分類する。 ハイパーテキストの自動分類 ノードをあらかじめ決められたカテゴリに分類する。 近傍のノードの分類結果によって補正する。 問題点 多数のカテゴリへの高精度の分類は困難。 Web上のテキストは多様であり、特に難しい。 テキストの自動分類によるWebディレクトリ構築は困難。 →テキストの内容を用いない方法を検討する。

関連研究:特定トピックのオーソリティ発見 HITS [Kleinberg1998] トピックを表すキーワード の検索結果の近傍から オーソリティとハブを抽出。 オーソリティ…多数のハブから参照される、重要なWebページ。 ハブ…多数のオーソリティを参照する、リンク集的なWebページ。 カテゴリ名によるオーソリティ発見…詳細な分類には不向き。 ･･･ ･･･ ハブ オーソリティ 例：ゲーム全般 /ゲーム/ 　　ゲーム販売店 /ショッピング/趣味とおもちゃ/ゲーム/ 　　ゲーム開発企業 /ビジネス/エンターテインメント/ゲーム/

関連研究: 関連Webページ発見手法 参照共起関係 関連Webページ発見アルゴリズム 共通のリンク元でハイパーリンクの位置がL以内にあること。 関連Webページ発見アルゴリズム 与えられたWebページと関連するオーソリティを発見する。 →　Webディレクトリに登録すべきWebサイトを発見できる。 : リンク6 リンク7 リンク8 リンク9 シードWebページ L以内 関連Webページ

Webディレクトリ拡大手順 1. 大域Webグラフを作成する。 2. 各カテゴリで関連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サイト発見アルゴリズムの適用 例：ビジネス/食品/飲料/酒類 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.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サイトの削除 重複して発見された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.cclemon.com/ ： 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/ http://www.nipponham.co.jp/ http://www.higeta.co.jp/ http://www.takeya-miso.co.jp/ http://nitanda.com/ http://www.aohata.co.jp/ ： 関連度 9.9 8.9 8.4 8.1 7.7 5.8 ： 関連度 11.1 9.2 8.3 7.7 5.9 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ディレクトリ 大域Webグラフ Open Directory Projectの日本語カテゴリ 評価実験：　対象データ 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サイトのうち発見されたもの 注意：元々Webディレクトリに登録されていたWebサイトのみを評価。

実験１：精度の評価結果 各カテゴリで最大N件の関連Web サイトを発見した場合の精度 MultiCocitationは実用的な精度を達成。 Companion+ではトピックドリフトが発生。 被参照数の大きいシードにのみ関連するWebサイトが発見されやすい。

実験１：シードセットサイズと発見精度 登録Webサイト数が大きいカテゴリでは精度が低下

実験２-1： 適合度の評価 被験者：ネットワーク分野の研究者８名。 カテゴリ：被験者がよく知っている分野を２つ。 実験２-1：　適合度の評価 被験者：ネットワーク分野の研究者８名。 カテゴリ：被験者がよく知っている分野を２つ。 関連Webサイトのトピックとの適合性を判断。 適合する ＋２点 どちらかといえば適合する ＋１点 評価不能（アクセスできないなど）　　０点 どちらかといえば適合しない －１点 適合しない －２点 カテゴリの適合度＝関連Webサイト全体の平均点 注意：分類精度の評価とは異なる。

実験２-1： 適合度の評価 Companion+ 平均0.99 MultiCocitation 平均1.44 実験２-1：　適合度の評価 Companion+ 平均0.99 MultiCocitation 平均1.44 カテゴリによって適合度の高低がある。 × アート/映画/洋画 ○ /音楽/ビートルズ ○ニュース/新聞

実験２-1： 適合度の評価 適合度の低いカテゴリがある理由 リンク集における分類と、Webディレクトリの分類の不一致。 実験２-1：　適合度の評価 適合度の低いカテゴリがある理由 リンク集における分類と、Webディレクトリの分類の不一致。 例：アート/映画/洋画…邦画のWebサイトが発見される。 近傍Webグラフが小さい カテゴリでは、少数の関 連Webサイトしか得られ ない。 シードセット中に被参照 数の大きいWebサイト が一つは必要。

実験２-２： 重要度の評価 登録する価値があるWebサイトが発見されるか？ 各カテゴリで重要度（平均点）を比較 実験２-２：　重要度の評価 登録する価値があるWebサイトが発見されるか？ 知名度、信頼性、情報量、オリジナリティ、デザインで判断。 登録すべき ＋２点 どちらかといえば登録すべき ＋１点 評価不能（アクセスできないなど） 　０点 どちらかといえば登録すべきでない －１点 登録すべきではない －２点 各カテゴリで重要度（平均点）を比較 シードセットのWebサイト。 発見された関連Webサイトのうち、「適合する」あるいは「どちらかといえば適合する」Webサイト

実験２-２：重要度の評価結果 Companion+の評価 シードセット 平均1.00 Companion+ 平均0.96 被参照数の大きいWebサ イトを発見しやすい。 →トピックに適合していれ 　ば、重要なWebサイト。 MultiCocitationの評価 網羅的なリンク集の影響 で、重要度の低いWebサ イトを発見しやすい。 シードセットの重要度と正 の相関がある。 シードセット 平均1.00 Companion+ 平均0.96 MultiCocitation 平均0.74

まとめと今後の課題 関連Webページ発見アルゴリズムを拡張し、 Webディレクトリの自動拡大を実現した。 今後の課題 適合度と重要度を両立するアルゴリズムの検討。 カテゴリ間の関係(階層構造)の利用。 http://odin.ingrid.org/　にてデモシステムを公開予定。

関連研究: 特定トピックのオーソリティ発見 HITS [Kleinberg1998] サーチエンジンの検索結 果の近傍Webグラフから オーソリティとハブを抽出。 オーソリティスコア順に 検索結果を出力。 オーソリティ…多数のハブから参照される、重要なWebページ。 ハブ…多数のオーソリティを参照する、リンク集的なWebページ。 ハブ オーソリティ オーソリティスコア ハブスコア 高 低 ･･･

Companion+とCompanion++ シードセット全体の近傍からオーソリティを発見する。 （近傍:参照元Webサイト+参照共起関係にあるWebサイト） ハイパーリンクの選別と重み付けでHITSの精度を改善。 関連度＝（オーソリティスコア）2×近傍Webサイト数 Companion++ 各シードの近傍から オーソリティを発見する。 関連度＝ ΣCompanion+の関連度 シードセット シード

Cocitation++とMultiCocitation Cocitation++　[Dean&Henzinger1998]を拡張 各シードと多数回参照共起関係にあるWebサイトを発見。 関連度＝ Σシードと参照共起する回数 MultiCocitation 多くの異なるシードと参照共起関係にあるWebサイトを発見。 　関連度＝参照共起関係にあるシードの数 + 　　0.1×(Cocitation++の関連度) シード シードセット Cocitation++ MultiCocitation 関連度： 3 関連度： 1.3 関連度： 2 関連度： 2.2

関連研究: Webグラフの参照関係の分析 HITS [Kleinberg1998] オーソリティスコア順に 検索結果を出力。 オーソリティ…多数のハブから参照される、重要なWebページ。 ハブ…多数のオーソリティを参照する、リンク集的なWebページ。 ハブ オーソリティ オーソリティスコア ハブスコア 高 低 ･･･

関連研究: 特定トピックのオーソリティ発見 ARC：Automatic Resource Compilation [Chakrabarti1998] HITSの精度を改善：　アンカーテキストでリンクを重みづけ。 トピックを表すキーワードから、オーソリティを発見する。 カテゴリによっては商用Webディレクトリに匹敵する 品質のWebサイトのリストが得られる。 （例:“Sushi”） 問題点 詳細なカテゴリをキーワードで表すのは難しい。 例： 　ゲーム全般 /ゲーム/ 　ゲーム販売店 /ショッピング/趣味とおもちゃ/ゲーム/ 　ゲーム開発企業 /ビジネス/エンターテインメント/ゲーム/