私のブックマーク
Web構造マイニングとWeb視覚化
村田剛志（国立情報学研究所）
１．はじめに
Webデータにおけるパターン発見をデータマイニング技術を用いて行なうことをWebマイニングと呼ぶ。Webマイニングは、自然言語処理や機械学習、データマイニングなどの人工知能の分野にとどまらず、情報検索やデータベースなど幅広い分野と関連する複合的な研究分野である。
注目するWebデータの種類によって、Webマイニングは以下の3つに分類される。
1) Webページのコンテンツに注目し、自然言語処理やデータベースのアプローチを用いて、テキストマイニングによる情報抽出や半構造データにおける検索のモデル化などを目指すWeb内容マイニング
2) Webページ間を結ぶハイパーリンクによって構成されるグラフ構造に注目し、関連ページの発見や重要ページのランキング、グラフ構造のモデル化などを目指すWeb構造マイニング
3) Webページの閲覧によって生じる(サーバー側やクライアント側の)ログデータに注目し、ユーザプロファイルの学習やサイトにおける閲覧パターンの学習などを目指すWeb利用マイニング
Webマイニングという言葉は1990年代後半から用いられてきたが、上記の3つを意味する言葉として定着してきたのは2000年頃からである。Webマイニングのサーベイとしては以下の記事がある。
Raymond Kosala, Hendrik Blockeel. Web Mining Research: A Survey (2000)
Webマイニングは非常に幅広い研究分野であり、上記の3つ全てをカバーすることは難しい。Web内容マイニングについては、長谷川隆明氏による「私のブックマーク テキストマイニング」や特集「WWW上の情報の知的アクセスのためのテキスト処理」人工知能学会誌 Vol.19, No.3, pp.295-323 (2004)にテキストマイニングに関して紹介されている。またWeb利用マイニングについては、データマイニング全般に関する無償・商用のソフトウエアや関連会社等の情報を幅広く紹介している
KDNuggetsにおけるソフトウエア紹介や、WebKDD Workshopが参考になると思われる。
本稿では、Web構造マイニングと、Web構造理解の支援となることが期待されるWeb視覚化について、関連サイトを紹介する。
２．Web構造マイニング
Web構造マイニングの入門的な解説としては、
を参照していただきたい。Web構造マイニングの目的としては、以下のようなものがあげられる。それぞれについて関連サイトを紹介する。
(1)ランキングアルゴリズム
検索結果のページをその重要度に応じてランキングするためのアルゴリズムとして、検索エンジンGoogleが採用しているPageRankが有名である。
日本語によるものとしては、京都大学の馬場氏によるPageRankの解説が詳しい。
このようなリンクベースのランキングアルゴリズムの普及に対応して、その性質についての様々な分析がなされてきている。例えばblogサイトにおいては、トラックバックなどによって相互リンクが張られることが多いため、PageRank値が比較的高くなることが指摘されている。
また、検索エンジンの性質を利用して自己のサイトが検索結果の上位に配置されることを目指すSEO(Search Engine Optimization, 検索エンジン最適化)がビジネスとして行なわれるようになり、検索エンジンの動向に注目が集まっている。
検索エンジンの動向に関するニュースを扱うサイトとしては、Search Engine Watchや、浅井勇夫氏による検索デスクが良く知られている。
(2)特定トピックのページ抽出・Webコミュニティ発見
ハイパーリンクのグラフ構造に注目した特定トピックページの抽出やコミュニティ発見の代表的な研究としては、以下のものがある。
・Webページの有用性の基準として、特定トピックに関する情報が豊富なページ(ハブ)と、ハブへのリンクが豊富なページ(オーソリティ)を導入し、両者を相互再帰的に定義し計算するKleinbergらのHITSアルゴリズム
Jon M. Kleinberg.Authoritative Sources in a Hyperlinked Environment (1999)
・Webのスナップショットデータからの2部グラフ探索によるKumarらのコミュニティ発見
・ネットワークフロー問題における最大流・最小カット定理をWebのグラフ構造に適用したFlakeらのWebコミュニティ発見
(3)Web構造のモデル化
Webのマクロな構造に関する研究としては、ハイパーリンクによるWebページ間の結合関係を分析し、Webは蝶ネクタイ構造であると主張したBroderらの研究が有名である。Webページ間の到達可能性に関して、中心的な強連結成分(SCC)、 SCCへ到達できるが逆は不可のIN, SCCから到達できるが逆は不可のOUT, その他のTENDRILの4つの部分から構成されていることを示している。
Webのネットワーク構造の性質としては近年、”スケールフリー”や”スモールワールド”であることが指摘されてきている。両者の詳しい内容については、松尾豊氏の「スモールワールドとチャンス発見」人工知能学会誌 Vol.18, No.3, pp.288-294 (2003)や福田健介氏、栗原聡氏の「ネットワークの科学」人工知能学会誌 Vol.18, No.6, pp.716-722 (2003)の解説記事を参照していただきたい。
スケールフリーについては、Notre Dame大のBarabasiのページ
が参考になる。”Webの直径は19″と主張したNatureの論文
“Diameter of the World-Wide Web”や、インターネットのトラフィックを視覚化した画像などもある。
３．国際会議・学会など
Webに関する国際会議は非常に数多く開催されている。以下に示すのはそのごく一部である。また、”Mining the Web”(Morgan Kaufmann)の著者
Soumen Chakrabartiのホームページや、Proceedings of the National Academy of Science of the United States of AmericaのVol.101 Suppl.1 (2004)も、Webマイニング研究の最新動向をつかむ上で非常に参考になる。
International World Wide Web Conference(WWW)
ACM SIGKDD International Conference(KDD)
International Conference on Web Infomation Systems Engineering(WISE)
International Conference on Web Intelligence(WI)
Workshop on Web Mining and Web Usage Analysis(WebKDD)
Workshop on Algorithms and Models for the Web-Graph (WAW)
ACM SIGWEB
４．Web視覚化システム
Web構造マイニングとは直接関係ないが、Webページ集合をグラフとして表現する視覚化システムは、検索結果をユーザに提示するインタフェースなどにおいて非常に重要である。
Googleが2002年に公開したSOAPおよびWSDLに基づいたインターフェース
Google Web APIにより、Googleが収集したWebページのデータを好きなようにプログラミングして利用することができ、それを利用した視覚化システムが数多く開発されている。
TouchGraph
Google Set Vista
Anacubis google-enabled visual search
その他にも、Webページ集合を視覚化するシステムとしては以下のものがある。
Periscope
KartOO
Grokker2
InfoLeed
Vivisimo
Webに限らずサイバー空間の視覚化を扱ったサイトとしては、以下のサイトがある。
５．おわりに
対象のグラフ構造に注目する研究はWeb構造マイニングに限らず、例えば有機化合物などの構造における頻出部分グラフの発見や、社会学における人間のネットワークの分析などがあげられる。
人工知能研究において現実的なデータを扱う上で、構造をもったデータのマイニング手法の必要性は高まってきている。もちろん、一口にグラフ構造のデータと言っても、グラフの大きさ、辺の密度、辺の種類、ラベルの有無、ノイズの程度などは様々であり、他の研究分野における手法がそのままWebのグラフ構造に対して適用できるわけではない。Webのグラフとしての性質を理解し、広くグラフマイニングにおけるケーススタディとしてWeb構造マイニング手法を
位置づけることができれば、この研究分野の重要性はますます高まっていくものと期待される。