1 Broder Navigational URL URL Informational Web Transactional Web Web Web 2 Broder [16] SearchLife Broder [16] Daniel [17] Broder

DEIM Forum 2010 B9-4

検索クエリ分類モデルに基づく多視点クラスタリング検索エンジンの

評価

村松

亮介

†

横山

昌平

††

福田

直樹

††

石川

博

††

†

静岡大学大学院情報学研究科

〒 432–8011 静岡県浜松市中区城北 3–5–1

††

静岡大学情報学部

〒 432–8011 静岡県浜松市中区城北 3–5–1

E-mail:

†

[email protected],

††{

yokoyama,fukuta,ishikawa

}

@inf.shizuoka.ac.jp

あらまし 本論文では Web ページ検索結果の閲覧性向上のための，検索結果のクラスタリングとラべリング手法を実

現したシステムと，その評価方法について述べる．クラスタ閲覧の手がかりとなるクラスタラベルが単一の手法で生

成されている場合，ラベル一覧にユーザの求めている語が存在しないときに，クラスタラベルが閲覧のための有用な

手がかりとならず，目的の Web ページがクラスタ内に埋もれたまま見つからないことがある. 本論文で示すシステム

では，閲覧性の向上のためにクラスタに対するラベリング手法を複数用意することで，ユーザが迅速に情報収集を行

えるようにする．クラスタリングによる検索結果表示に対する提案手法の有効性を検索クエリ分類モデルに基づいて

評価し，本システムを用いた場合に，いくつかの種類の情報収集タスクを効率的に行えることを示す．

キーワード 情報検索，データマイニング

Evaluation of a Multiple Viewpoints Clustering Search Engine Based on

a Classification Model of Search Queries

Ryosuke MURAMATSU

†

, Shohei YOKOYAMA

††

, Naoki FUKUTA

††

, and Hiroshi ISHIKAWA

††

†

Graduate School of Informatics, Shizuoka University

3–5–1 Johoku, Naka-ku, Hamamatsu-shi, Shizuoka,

432–8011 Japan

††

Department of Computer Science, Faculty of Informatics, Shizuoka University

3–5–1 Johoku, Naka-ku,

Hamamatsu-shi, Shizuoka, 432–8011 Japan

E-mail:

†

[email protected],

††{

yokoyama,fukuta,ishikawa

}

@inf.shizuoka.ac.jp

Abstract

Web search engines play important roles as a tool to obtain useful information from the web. Since

keyword-based search engines produce a long list of results that contain links to relevant web pages, approaches for

improving visibility of results to grasp an overview of the search results has investigated. In this paper, we propose

a system that clusterizes search results with multiple cluster labels for improved view of results. To make labels be a

useful guide, we provide a multi way labeling method that considers statistical features of words in documents. We

evaluate our approaches based on a search query classification model, and show our labeling methods for clustering

search system have advantages in some complex searching tasks.

Key words

infomation retrieval, data mining

1.

は じ め に

検索エンジンは，Web上の膨大な情報を検索する手段の1つ として，重要な役割を果たしている．代表的な検索エンジンで あるGoogle [1]やYahoo [2]が提供している検索エンジンの検 索結果は，ランキングに基づくリスト表示に基づいているため， 検索対象やそれに対する検索クエリの与え方によっては，ユー ザが検索結果の概観を捉えることや必要な情報をすぐに探し出 すことが難しい場合がある． 検索エンジンにおける検索結果提示の改善方法として，クラ スタリングに基づくアプローチがあり，その効果についての検 証も試みられている[3]∼[15]. しかしながら，クラスタリング に基づく検索結果の提示手法には，クラスタリングを高精度に 行うということ以外にも，クラスタへの適切なラベル付けや， 目的に応じたラベル付け手法の選択を行えるようにすることで， 改善が行える余地がある．

表 1 Broderの検索クエリ分類モデル 分類 説明 Navigational 過去に訪問済みで，明らかに知っている サイトの閲覧．検索理由はサイトの URL を入力するよりも便利であるから，また は，URL を覚えていないなどの理由から 検索がなされる． Informational Webページを読むことや眺めることで何 かを学ぶこと Transactional オンラインショッピングやファイルのダウ ンロード等の行為を伴う Web ページを検 索する 同一の検索クエリによって検索を行う場合であっても，それ ぞれのユーザの検索意図，目的，および検索対象に関する理解 度は多様である．本論文では，これらのユーザの検索意図や検 索対象に対する理解度に対して適切となるような検索結果の提 示のされ方を，１つの「視点」として定義する．クラスタリン グ結果から複数のWebページを収集したり，多義性のある検 索クエリの持つ複数の意味を分析するような，クラスタリング 結果を精査する必要があるタスクの場合，クラスタリングを別 の視点で何度もやり直すと，クラスタの構造が変化することに より，どこまでが調べた内容なのかが分からなくなってしまい， 効率的な精査ができない場合がある．そこで，本論文ではクラ スタの構造は保存したまま，クラスタのラベルを切り替えるこ とを考える．クラスタのラベルを複数の視点からそれぞれ有益 であろうと考えられるものに切り替えながらクラスタリング結 果をブラウズできるようにすることで，検索結果の精査が円滑 に進められるようにする． 本論文では，閲覧性の向上のためにクラスタに対するラベリ ング手法を複数用意する．具体的には，Webページ全体集合 と，あるクエリに対する検索結果集合という異なる2種の集合 に対する，それぞれの単語の特徴量の違いを考慮したラべリン グ手法を用意することで，検索結果中の単語の専門性，一般的 認知度の違いを反映するような，複数のラベルを同一のクラス タリング結果に対して提示できるようにする． 本論文では提案システムの評価に関して，Broder [16]が提案 するユーザの検索意図に基づく検索クエリの分類モデルを本研 究で提案する検索システムSearchLifeに適用し，ユーザビリ ティ評価実験により本システムの有効性を確認する．  本論文の構成は，次のようになっている．2.節で，本研究と 関連研究との差分を述べ，3.節で，本論文で提案する各種ラベ ルの特徴および生成方法の概略を述べる．4.節で，本論文で提 案する多視点ラベルに関するユーザビリティ評価を述べ，5.節 で，本論文で得られた成果をまとめる．

2.

関 連 研 究

2. 1 検索クエリの分類モデル 検索クエリの分類モデルに関して，Broder [16]やDaniel ら[17]はユーザの検索意図に基づく検索クエリの分類モデル を提案した．Broderは検索エンジン利用者の検索クエリを

Navigational，Informational，Transactionalの3種に分類し た．Broderの検索クエリの分類モデルを表1に示す．また，

DanielらはBroderが提案したInformationalをさらに階層的 に再定義し，また，Transactionalの代わりにResourceを定義 した．DanielらはResourceを，Webページ上で利用できるリ ソースを手に入れること，と定義した． 2. 2 検索結果のクラスタリング Web検索結果のクラスタリングに関する研究は大きく二つ に分類できる．1つは，Webページの内容に着目してクラスタ リングを行うコンテンツマイニングであり，もう1つは，Web ページのリンク情報に基づいてクラスタリングを行うストラク チャマイニングである．コンテンツマイニングを行う研究とし て，例えばZamirら[18]や成田ら[8]の研究がある．Zamirら はSuffix Treeと呼ばれるデータ構造から共通して現れる単語を 容易に発見し，その単語が出現する検索結果をまとめてクラス タを形成する手法であり，STCと呼ばれる．成田らは検索結果 の階層型排他的クラスタリングを行うシステムとしてMETAL を開発した．成田らの研究では，生成されたクラスタに対する ラベルの有用度に関して踏み込んだ検討はなされていない． また，現在Web上に公開されているクラスタリング検索エ ンジンとしてClusty [5]やCarrot2[14]がある．Clustyはメタ 検索エンジンの一種で，検索結果を階層的にクラスタリングし て，画面左にクラスタをツリー型メニューとして表示し，画面 右に選択したクラスタに属するWebページがリスト表示され る．Clustyは“Velocity”と呼ばれる独自クラスタリングエン ジンを利用しており，文書を意味のあるグループに自動組織化 する．また，2008年1月より，新機能としてremix機能が追 加された．remixとは提示されたクラスタリング結果がユーザ の意図と一致しなかった場合，つまり，ラベル一覧に求めてい る情報が存在しなかった場合に，別の観点で再クラスタリング を行う機能である．remixはユーザにとって適切なクラスタが 生成されるまで繰り返される．本論文では，クラスタ構成は一 定のまま，生成クラスタに対して性質の異なるラべリング手法 を複数用意することで，ユーザが検索結果から目的とするWeb ページ発見の支援を行う．Carrot2はオープンソースのクラス タリング検索エンジンであり，検索結果を意味を持ったカテゴ リに自動組織化する．また，Carrot2_{はクラスタリングアルゴ} リズムとしてLingo [13]およびSTC [6]を搭載している．Lingo は，まず入力文書からクラスタラベルを生成し，その後，各ラ ベルに文書を割り当てる手法である． ストラクチャマイニングを行う研究としてImafujiら[19]や 大野ら[7]の研究がある．ImafujiらはWebの構造分析を目的 としてWeb全体を対象としたマイニングを行っており，大野 らは検索結果内からの効率的な情報収集を目的として検索結果 を対象としてマイニングを行っている．大野らの研究では高い 再現率および適合率を示しているが，類似度判定手法の特性か らクラスタに分類されないページが多くなる．この問題に対し てはコンテンツマイニングによるクラスタリング手法との統合 による改善の可能性が指摘されている． 

ラベル 構築部 検索結果取得部 検索結果処理部 クラスタリング部 検索クエリ(httpリクエスト) 検索結果(XML) 名詞 ヒット件数 名詞 検索結果 idf,特徴語 検索クエリ 入力画面 Yahoo! 形態素解析 ＡＰＩ Yahoo! Web検索 ＡＰＩ 検索結果 ＤＢ 検索結果 (タイトル,サマリ URL) タイトル 検索クエリ タイトル 情報提示部 ラベル情報 検索結果 検索クエリ 検索結果 ブラウザ SearchLife 外部Webサービス 出力画面 html クラスタ情報 図 1 システム概要 2. 3 クラスタリング検索エンジンに関するユーザビリティ 評価 Zamir [6]らはクラスタリング検索エンジンとして，STCア ルゴリズムを搭載したGrouperを開発した．Zamirらは提案 システムの評価に関して，システムをWeb上に公開し，大量 のユーザのアクセスログを収集し，ユーザのシステムにおける 振る舞いに関する分析を行っている．Songhua [4]はテキスト と画像を用いた，クラスタリング検索結果提示手法を提案し た．システムのユーザビリティ評価では，被験者に検索タスク を提示し，被験者は自由に検索クエリを入力し，その解答を発 見する実験を行っている．評価指標はタスク達成時間，クリッ ク数，被験者の満足度および解答の質であり，比較システムで あるgoogleと比較して，優位であることが示されている．本 論文では，検索タスクをBroder [16]が提案した検索クエリ分 類モデルに基づいて作成し，実験の設計者が指定した検索クエ リに対する検索結果を用いて，被験者に解答を探索させる． 2. 4 Webページに対する複数スニペットの提示 検索エンジンから返される検索結果のWebページそれぞれの 要約文章(スニペット)を，複数の視点から構築しユーザに提示 する研究として，Jae-wookら[20]や高見ら[21]の研究がある． Jae-wookらは，Webページに対するパーソナライズ化された スニペットをユーザに提示する手法を提案している．Jae-wook らの手法では，ユーザの現在直面している課題からタスクモデ ルを構築し，そのモデルに基づいて，検索結果に表示される各 Webページのスニペットを構築する．タスクの干渉度を考慮 して，3種のスニペットを構築し，ユーザが状況に応じてスニ ペットを選択できる．高見らは，スニペットを，その生成方法 により2種類の軸で分類している．さらに，Webページに対し て4種類のスニペットを生成できるようにすることで，ユーザ の検索目的に適したスニペットを提示できるようにした．これ ら2つの研究は，1つのWebページに対する多角的なスニペッ トの提示を目指したものである．本論文では，検索結果クラス タという，ある類似性を持ったWebページ群に対するラベル を，複数の視点から構築できるようにすることを目的とする．

3.

多視点ラベルの構築

本論文では4種類のラべリング手法を用いる．手法1と手法 2で生成されるラベルはクラスタ内文書のいくつかに共通して 出現する単語である．前者は後者と比較してWeb上で使用頻 度が高く，後者は前者と比較してWeb上で使用頻度が低い単 語であるという特徴を持つ．手法3で生成されるラベルは手法 4のそれと比較してWebページ全体集合では使用頻度は低い が，検索クエリに対する検索結果集合中では使用頻度が高くな る単語である．手法4で生成されるラベルは手法3のそれと比 較してWebページ全体集合では使用頻度は高いが，検索結果 集合中では使用頻度が低くなる単語である．本論文では上記4 種のラベリング手法を導入することで，ユーザが検索結果クラ スタを複数の視点で閲覧可能とする多視点ラベルを構築する． （注 1） 本節では多視点ラベルの構築手法に関して述べる．以下に 本論文で提案する4種類のラベルの特徴を記す．  ラベルタイプ1 クラスタ内文書のいくつかに共通して出現し，1つの名詞から なる．ラベルタイプ1はラベルタイプ2と比較してWeb上で 使用頻度が高い単語を用いる．ラベルタイプ1は検索対象にお いてよく使われる単語の把握やそれらの単語を手掛かりとして 必要とする文書を迅速に発見できることが期待される．  ラベルタイプ2 クラスタ内文書のいくつかに共通して出現し，複数の名詞によ り構成される．ラベルタイプ2はラベルタイプ1と比較して Web上で使用頻度が低い単語を用いる．ラベルタイプ1と比 較してWeb上で使われない単語であるため，検索対象に関し て情報量が多い場合にはラベルタイプ2を見ることでより迅速 に必要となる文書を発見できることが期待される．  ラベルタイプ3 ラベルタイプ1とラベルタイプ2で用いられる単語はクラスタ 内の文書同士で共起する単語，つまり，クラスタを概観できる 可能性がある単語を用いる．一方，ラベルタイプ3では共起関 係を考慮しない単語を用いている．ラベルタイプ3で用いられ る単語はラベルタイプ4と比較してWebページ全体集合では 使用頻度は低いが，検索クエリに対する検索結果集合中では使 用頻度が高くなる単語である．例えば，ある分野に詳しいユー ザなら常識的に知っているが，その分野に関して事前に触れた ことのないユーザには理解の難しい語句を含む内容が検索結果 に含まれることがある．そのような場合に，検索クエリ集合に おいてある種「常識的」な単語であると期待されるラベルタイ プ3を閲覧することで，検索クエリの結果の閲覧に関してあら かじめ知っておくべき事項をユーザが把握するのに役立つ可能 性がある．  ラベルタイプ4 （注 1）：なお，本論文での上記のアイデアは文献 [22] および文献 [23] を拡張し たものである．文献 [9] では文章によるクラスタに対するスニペットの提示を目 的としていたが，文献 [23] では単語によるクラスタに対するラベリングを行って おり，提案システムのユーザビリティ評価に関して，異なる種類のラベルを利用 することの有効性を検証した．

表 2 本実験での検索クエリの分類 分類 説明 直接的クエリ 検索対象を直接的に示す．例えば，政党「民主党」 は検索クエリ「民主党」と表現される． 間接的クエリ 検索対象を間接的に示す．例えば，自動車「プリ ウス」は検索クエリ「トヨタ エコカー」と表現 される． 多義的クエリ 検索クエリが多くの意味を持つ．例えば，単語「さ くら」は植物，人名，楽曲名等の意味を持つ ラベルタイプ4では，ラベルタイプ3と同様に共起関係は考慮 しない単語を用いている．ラベルタイプ4は，ラベルタイプ3 と比較してWebページ全体集合では使用頻度は高いが，検索 結果集合中では使用頻度が低くなる単語である．同じような文 書が多く検索結果に含まれるような状況で特徴的な文書を含む クラスタをすばやく探し出す場合や他のクラスタとの差異を際 立たせることに利用できる可能性がある．  上記4タイプのラベル生成手法を用いることにより，ユーザ は，各自の検索要求や検索対象に関連する事項の理解の程度に 応じて，閲覧するラベルタイプを選択することで，より早く目 的のWebページを発見でき，閲覧性を向上させることができ るのではないかと考えられる． 提案システムの概要は図1のようになっている．ラベルタイ プ1およびラベルタイプ2のラベルは検索結果のクラスタリン グ過程において生成され，ラベルタイプ3およびラベルタイプ 4は統計的手法によって生成されるラベルである．詳細なクラ スタリング手法およびラベル生成手法は文献[23]に示している．

4.

多視点ラベルに関するユーザビリティ評価

本研究では生成されたクラスタに対して複数の視点でラべ リングを行っている．本節では，実験によりその効果を確認す る．本実験ではBroder [16]が提案した検索クエリの分類モデ ルを参考に検索タスクを作成する．本実験では分類モデルのう ち，Informationalに関する検索タスクを作成し，実験を行う． さらに，本実験では検索クエリを直接的クエリ，間接的クエリ， 多義的クエリの3種に分類する．本実験における検索クエリの 分類を表2に示す．本実験では，直接的クエリおよび間接的ク エリは各4タスク，多義的クエリは他の2種のクエリと比較し て，検索結果をクラスタリングすることの効果をより発揮する であろうと予測し，8タスク設定した．本実験における計3個 のタスクタイプ毎のタスクを表3から表5に示す． 4. 1 実 験 方 法 本実験では提案システムである多視点ラベル型システム(以下 「提案システム」）の他，比較システムとして提案手法のラベル タイプ1型システム(以下「比較システム1」)，Carrot2_[14](以 下「比較システム2」)およびリスト表示型システム(以下「比 較システム3」)の計4種のシステムを用意する．比較システム 2はオープンソースのクラスタリング検索エンジンであり，そ のアルゴリズムについて文献[13], [15]で述べられているため， 比較対象とした．提案システムは図2，図3および図4の3つ 図 2 ラベルタイプ 1 およびラベルタイプ 2 によるクラスタリング結 果提示 図 3 ラベルタイプ 1 およびラベルタイプ 3 によるクラスタリング結 果提示 の画面を切り替える形式となっている．各画面の左フレームに はラベルタイプ１が常に表示されており，中央フレームにラベ ルタイプ2，ラベルタイプ3およびラベルタイプ4の何れかが 表示され，ラベル一覧の上部に他のラベルタイプへのリンクが 貼られており，リンクをクリックすることで，表示ラベルタイ プが切り替わる仕組みになっている．比較システム1は図5の ように示される．比較システム1は他のラベルタイプへのリン クは貼られておらず，常にラベルタイプ1が表示されている． 比較システム2は図6,比較システム3は図7のように示され る．提案システムは画面の左フレームおよび中央フレームに， 比較システム1は左フレームにラベル一覧が表示され，ラベル をクリックすると画面の右フレームにそのクラスタ内文書が表 示される仕組みになっている．比較システム2はクラスタリン グアルゴリズムとしてデフォルトのアルゴリズムとして設定さ れているLingoを適用し，ソースをYahoo!，言語を日本に設 定した．なお，比較システム3はYahoo!デベロッパーネット ワーク[24]が提供するウェブ検索Webサービスを利用したと

表 3 タスクタイプ 1(直接的クエリ) タスク番号 実験タスク 検索クエリ 1.1 2010年サッカーワールドカップのグループリーグの組み合わ せが書かれたページを 3 ページ集めよ 「2010 サッカーワールドカップ グループリーグ組み合わせ」 1.2 鹿島アントラーズの公式ホームページを発見せよ 「鹿島アントラーズ」 1.3 探索アルゴリズムの計算量の比較に関して記述されているペー ジを 3 ページ集めよ 「探索アルゴリズム 計算量 比較」 1.4 行政刷新会議における仕分けの対象となる事業一覧が記述され ているページを 2 ページ集めよ 「行政刷新会議 仕分け対象一覧」 表 4 タスクタイプ 2(間接的クエリ) タスク番号 実験タスク 検索クエリ 2.1 漫画「ホイッスル」に関するページを 3 ページ集めよ 「サッカー 漫画」 2.2 サッカーワールドカップの初代王者を答えよ 「サッカーワールドカップ 初代王者」 2.3 ドラマ「プライド」に関するページを 2 ページ集めよ 「フジテレビ ドラマ 木村」 2.4 2009年女子プロゴルフの賞金王を答えよ 「女子ゴルフ  2009 賞金王」 表 5 タスクタイプ 3(多義的クエリ) タスク番号 実験タスク 検索クエリ 3.1 名字が「阿部」であるスポーツ選手を 3 人答えよ 「阿部」 3.2 地名に「栄」が含まれる都道府県を 5 個答えよ 「栄」 3.3 名字が「加藤」であるスポーツ選手を 3 人答えよ 「加藤」 3.4 名前が「大輔」であるスポーツ選手を 5 人答えよ 「大輔」 3.5 病気についてのページを 5 ページ集めよ 「ウイルス」 3.6 チーム名にジャイアンツが含まれるチームを 5 チーム答えよ 「ジャイアンツ」 3.7 人名にマイケルが含まれる人物を 4 人答えよ 「マイケル」 3.8 歌手に関するページを 4 ページ集めよ 「スティーブン」 図 4 ラベルタイプ 1 およびラベルタイプ 4 によるクラスタリング結 果提示 きの検索結果上位100件を順番に10件ずつ提示する．ユーザ は画面下部のリンクをクリックすることで10件ずつブラウジ ングを行う．また，4つの検索結果は共通して各文書のタイト ル，サマリ，URLが表示されている． 被験者は情報学部4年生から情報学研究科修士2年生までの 計16名である．いずれの被験者も情報系の学生であり，Web ブラウザと検索エンジンを用いた情報収集には，ある程度習熟 している．本実験では，被験者を4つのグループに分け，1つ 図 5 ラベルタイプ 1 のクラスタリング結果提示 の実験タスクに対してはそれぞれが異なるシステムを用い，各 被験者はすべてのシステムを同一回数用いることになるように した．グループ1は提案システム→比較システム1→比較シス テム2→比較システム3の順番にシステムを使用する．同様に， グループ2は比較システム1→比較システム2→比較システム 3→提案システム，グループ3は比較システム2→比較システ ム3→提案システム→比較システム1，グループ4は比較シス テム3→提案システム→比較システム1→比較システム2の順 番にシステムを使用する．被験者はタスクタイプ1およびタス

図 6 Carrot2によるクラスタリング結果提示 図 7 検索結果のリスト型表示の例 クタイプ2では各システムを1回ずつ，タスクタイプ3では， タスク数が8個なので各システムを2回ずつ使用する． 被験者に対しては合計16タスクを順番に1タスクずつ提示 する．各タスクの遂行では，本実験の設計者が設定した検索ク エリを用い，それに対する各システムの結果を提示する．他の 検索クエリによる再検索は行わず，提示した検索結果内でタス クに対する解答およびWebページを探す．また，各タスクに おいて制限時間は5分とし，制限時間を超過した場合の被験者 のタスク達成時間は300秒とする． 実験開始前にクラスタリング型検索エンジンや提案システ ムについての効果や使い方などの簡単な説明を行う．被験者は 「タスク開始」ボタンをクリックして，１つのタスクを開始し， そのタスクが終了したら画面左の「タスク終了」ボタンをク リックする．被験者は提案システムおよび比較システム1を使 用する場合，解答Webページの文書番号および発見した解答 Webページが含まれる上位クラスタの番号を記述し，比較シス テム2および比較システム3を使用する場合は解答Webペー ジの文書番号のみを記述する． 1つのタスクタイプに対する実験は続けて行い，４つのタス クが終了する毎に，各タスクにおける使用システムについての アンケートを行う．各タスクにおける使用システムについての アンケートではタスク達成のために役に立っていたと思われる システムの順番を回答させる． 本実験における評価指標はタスク達成時間およびアンケート 表 6 タスクタイプ 1 における使用システムについてのアンケート結果 システム名 1位に指名 した人数 2位に指名 した人数  3位に指名 した人数 4位に指名 した人数 提案システム 3 7 3 3 比較システム 1 6 4 4 2 比較システム 2 0 0 7 9 比較システム 3 6 4 4 2 表 7 タスクタイプ 2 における使用システムについてのアンケート結果 システム名 1位に指名 した人数 2位に指名 した人数  3位に指名 した人数 4位に指名 した人数 提案システム 7 4 3 2 比較システム 1 0 6 3 7 比較システム 2 5 6 3 2 比較システム 3 4 2 5 5 表 8 タスクタイプ 3 における使用システムについてのアンケート結果 システム名 1位に指名 した人数 2位に指名 した人数  3位に指名 した人数 4位に指名 した人数 提案システム 14 12 3 3 比較システム 1 13 11 7 1 比較システム 2 3 5 7 17 比較システム 3 2 4 14 12 表 10 タスクタイプ毎の各システムの平均支援率 タスクタイプ 提 案 シ ステム 比 較 シ ス テ ム 1 比 較 シ ス テ ム 2 比 較 シ ス テ ム 3 タイプ 1(直接的クエリ) 0.54 0.63 0.15 0.62 タイプ 2(間接的クエリ) 0.67 0.31 0.63 0.44 タイプ 3(多義的クエリ) 0.72 0.71 0.27 0.29 より算出される支援率である．タスク達成時間は１つのタスク において，被験者が「タスク開始」ボタンをクリックしてから 「タスク終了」ボタンをクリックするまでの時間である．支援率 はシステムがタスク達成のためにどれだけ役に立っていたかを 示す値として本論文で導入した指標である．1つのタスクに対 する，あるシステムの支援率の算出手順は次の通りである．ま ず，各タスクにおける使用システムについてのアンケートに対 し，1番役に立っていたと思われるシステムとされたものに3 ポイント，2番目に役に立っていたと思われるシステムとされた ものに2ポイント，3番目に役に立っていたと思われるシステ ムとされたものに1ポイント，4番目に役に立っていたと思わ れるシステムとされたものには0ポイントを各システムに与え ることとする．次に以下の式(1)を用いて1つのタスクにおけ るシステムAの支援率support(A)を求める．TotalPoint(A) は1タスクにおいてシステムAが獲得したポイントの合計で あり,Examinee(A)は1タスクにおいてシステムAを使用した 被験者数である．

support(A) = T otalP oint(A)

3× Examinee(A) (1)

4. 2 実験結果と考察

表 9 タスク毎のタスク達成状況の比較 タスク番号 提案システム (多視点ラベル) 比較システム 1(ラベルタイプ 1) 比較システム 2(Carrot) 比較システム 3(リスト) 平 均 タ ス ク 達 成 時 間 (秒) 支援率 達成人数 平 均 タ ス ク 達 成 時 間 (秒) 支援率 達成人数 平 均 タ ス ク 達 成 時 間 (秒) 支援率 達成人数 平 均 タ ス ク 達 成 時 間 (秒) 支援率 達成人数 1.1 270 0.5 3 221 0.75 3 216 0.08 3 160 0.92 4 1.2 262 0.42 2 195 0.58 4 208 0.08 3 11 0.75 4 1.3 273 0.5 2 252 0.5 3 283 0.25 3 206 0.42 4 1.4 195 0.75 3 196 0.67 2 173 0.16 4 115 0.41 4 2.1 118 0.75 4 140 0.25 4 71 0.67 4 110 0.58 4 2.2 183 0.75 3 234 0.17 2 205 0.67 2 212 0.25 2 2.3 35 0.67 4 119 0.5 4 94 0.75 4 99 0.58 4 2.4 169 0.5 3 250 0.33 1 126 0.42 4 87 0.33 4 3.1 226 0.58 2 154 0.83 3 201 0.5 3 222 0.17 3 3.2 243 0.83 3 287 0.67 2 300 0 0 288 0 1 3.3 164 0.67 3 151 0.67 4 192 0.25 2 138 0.58 3 3.4 192 0.58 3 135 0.75 4 236 0.33 2 160 0.5 4 3.5 135 0.67 4 74 0.67 4 108 0.33 4 154 0.42 4 3.6 192 0.92 4 202 0.58 3 187 0.25 4 216 0.16 4 3.7 157 0.67 4 153 0.67 4 133 0.5 3 137 0.25 4 3.8 176 0.83 4 104 0.83 4 263 0 4 236 0.25 4 均タスク達成時間，タスク達成人数および支援率を示す．平均 タスク達成時間について,制限時間である5分以内にタスクを 達成できない被験者の達成時間を300秒として平均タスク達成 時間を算出する．表6，表7および表8にタスクタイプ毎の使 用システムについてのアンケート結果を示す．タスクタイプ毎 の支援率を表10に示す． タスクタイプ1の直接的クエリにおいて，表10より，比較 システム1および比較システム3の支援率が高くなっている． 表9より，比較システム3は，4タスク全てにおいて平均タス ク達成時間が一番短く，全ての被験者がタスクを達成している． これは，検索クエリが検索対象を詳しく表現しており，曖昧性 が少ないことで，リスト表示において，解答ページが上位にラ ンキングされた結果であると考えられる．また，提案システム および比較システム1のクラスタリング手法は巨大なクラスタ が生成されることを防止するため，クラスタリングの際の指標 となるラベルは検索クエリの部分文字列ではない名詞とした． そのため，システムが適切なラベルを提示することができず， 被験者は適切なクラスタを選択することができなかったと考え られる． タスクタイプ2の間接的クエリにおいて，提案システムの支 援率が一番高くなっており，平均タスク達成時間は比較システ ム1と比較して，タイプ2の全タスクにおいて短くなってい る．また，表7より，多くの人がタスク達成のために提案シス テムが一番役に立ったと感じていることが分かる．これはラベ ルタイプ1以外のラベルタイプがタスクを達成するうえで有益 であったからであると考えられ，被験者のクリックログからも， ラベルタイプ2のラベルを基に正解ページに到達しているケー スが多く確認された． タスクタイプ3の多義的クエリにおいて，提案システムおよ び比較システム1の支援率がリスト表示型である比較システム 3と比較して高くなっている．また，表8より，多くの人がタ スク達成のために提案システムおよび比較システム1が一番役 に立ったと感じていることが分かる．リスト型表示においては， 直接的クエリや間接的クエリと比較して，検索クエリの曖昧性 が増加しており，検索結果内の解答ページ以外のページが増加 する．その結果，解答ページが上位にランキングされにくい状 態となり，線形的な探索を行う場合が多くなっている．これに 対し，クラスタリング型表示である提案システムおよび比較シ ステム1は類似文書がグループ化されているため，被験者が適 切なラベル選択を行えた場合には短時間で複数の解答ページを 収集できる．また，提案システムは比較システム1と比較して， タスク達成時間は長くなっているタスクが多くある．これは被 験者に対する実験後のインタビューにおける「提示されるラベ ル情報が多すぎて提案システムが使いにくい場合があった」， 「ラベルタイプ2のラベルを集中的に調べ過ぎてしまった」と いう指摘に関連している．ラベルタイプ2のラベルはラベルタ イプ1と比較して，多くの名詞から構成され，名詞のWeb全 体における頻出度も低い単語である．つまり，ラベルタイプ2 は単語の意味の理解容易性が低いため，検索対象について知識 が少ない被験者であると，ラベルの意味を理解することが困難 であり，解答に関連のない不要なラベルをクリックしてしまう 回数が多くなってしまったと考えられる．これに対し，ラベル タイプ1のみを表示する比較システム1のラベルは1つの名詞 から構成され，意味の理解容易性が高いため，検索対象につい て知識が少ない被験者でも，適切なラベル選択が行えたと考え られる．提案システムは他の3種と比較して，提示される情報 量も多く，ユーザが各ラベルタイプの特性を理解し，自身がど のラベルタイプを集中的に閲覧するかを判断する必要があるた め，ある程度の「慣れ」が必要である．ユーザが提案システム に習熟し，自身に適切なラベルタイプを選択できるような場合

や，逆にシステムがユーザの検索意図，目的，および検索対象 に関する理解度を判断し，適切なラベルタイプを推薦できるよ うな場合には，提案システムはより迅速な情報収集を行えると 考えられる． 以上のことから，本実験で使用した4種のシステムと3種の タスクタイプに関して，直接的クエリに関しては比較システム 3，間接的クエリに関しては提案システムが有効であると考え られる．多義的クエリに関しては，比較システム1が高い支援 率を示し，平均タスク達成時間も短いタスクが多いことから， 有効であると考えられる．また，多義的クエリに関して，提案 システムも比較システム1とほぼ同様な高い支援率を示してお り，平均タスク達成時間も比較システム1には及ばないが良好 な結果を示している． 提案システムの4種のラベルタイプの中には比較システム1 で提示するラベルタイプ1が含まれており，ユーザがシステム に習熟した場合，もしくは，システムがユーザに適切なラベル タイプを推薦できるような場合には，提案システムは比較シス テム1より有効に機能することも考えられる．本提案システム では，クラスタリングが有効となるようなタスクタイプ２およ び3のいずれでも安定して高い有効性を示している．従来のク ラスタリング検索エンジンで課題であった，検索タスクの種類 によって有効性が大きく変化してしまう問題は，本手法により 改善できたと考えられる．

5.

お わ り に

本論文では，ユーザが特定タスクのためのWebページから の情報収集の効率化を目的として検索結果の概観把握が容易 となるような検索結果をクラスタリングして提示し，生成クラ スタに対して複数の手法でラベリングを行うシステムとして SearchLifeを提案した．クラスタリングによる検索結果表示に 対するユーザビリティ評価を行い，提案システムを用いた場合 においてページ収集を効率的に行える場合があることを確認で きた． 今後の課題としては，ユーザの好みに応じてクラスタリング 手法やラべリング手法を変化させるパーソナライズ手法の実現 が挙げられる．本論文で示した実装では，複数のラベリング手 法によるラベル提示を実現しているが，画面内でのラベルの効 果的な提示方法については踏み込んだ検討をしていない．異な る手法によって得られたラベル同士を融合して1つのラベルの ように表示したり，検索語や検索タスクの種類などから適切と 考えられるラベリング手法を自動的に選択して提示する手法の 実現は，今後の課題である． 謝辞 本研究の一部は科研費基盤B(19300026)の助成を受 けたものである． 文 献 [1] Googlehttp://www.google.com/. [2] Yahoo!http://www.yahoo.com/.

[3] P. Ferragina, and A. Gulli，“A personalized search engine based on web-snippet hierarchical clustering，” WWW ’05: Special interest tracks and posters of the 14th international conference on World Wide Web，pp.801–810，ACM，2005.

[4] S. Xu, T. Jin, and F.C. Lau, “A new visual search inter-face for web browsing,” Proceedings of the Second ACM International Conference on Web Search and Data Mining, pp.152–161, ACM, 2009.

[5] Clustyhttp://www.clusty.com/.

[6] O. Zamir, and O. Etzioni, “Grouper: A dynamic cluster-ing interface to web search results,” WWW ’99: Proceed-ings of the 8th international World Wide Web Conference, pp.1361–1374, Elsevier North-Holland , Inc., 1999. [7] 大野成義，渡辺匡，片山薫，石川博，太田学，“Max flow アル ゴリズムを用いた web ページのクラスタリング方法の提案，” 日本データベース学会論文誌 (DBSJ Letters)，vol.4，no.2， pp.13–16，2005. [8] 成田宏和，太田学，片山薫，石川博，“階層的クラスタリングを 利用したメタ検索エンジンの提案，” Technical report，電子情 報通信学会技術研究報告 DE2002-61，2002. [9] 村松亮介，福田直樹，石川博，“分類階層を利用した検索エンジ ンの検索結果の構造化とその提示方法の改良，”電子情報通信学 会第 19 回データ工学ワークショップ，B6-3，2008.

[10] M.A. Hearst, and J.O. Pedersen, “Reexamining the cluster hypothesis:scater/gather on retrieval results,” SIGIR ’96, pp.76–84, ACM, 1996.

[11] P. Pantel, and D. Lin, “Document clustering with commit-tees,” SIGIR’02, pp.199–206, ACM, 2002.

[12] 成田宏和，太田学，片山薫，石川博，“Web 文書検索のための非 排他的クラスタリング手法の提案，”電子情報通信学会第 14 回 データ工学ワークショップ，2-p-01，2003.

[13] S. Osinski，J. Stefanowski, and D. Weiss，“Lingo:search re-sults clustering algorithm based on singular value decom-position，” Proceedings of the International IIS: IIPWM´04 Conference，pp.359–368，2004.

[14] Carrot2_{http://search.carrot2.org/stable/search.} [15] J. Stefanowski, and D. Weiss., “Carrot2_{and language}

prop-erties in web search results clustering,” In Proceedings of AWIC-2003, First International Atlantic Web Intelligence Conference, vol.2663 of Lecture Notes in Computer Science, pp.240–249, Springer, 2003.

[16] A. Broder, “A taxonomy of web search,” SIGIR Forum 36, vol.36, pp.3–10, ACM, 2002.

[17] D.E. Rose, and D. Levinson, “Understanding user goals in web search,” WWW ’03: Proceedings of the 13th inter-national conference on World Wide Web, pp.13–19, ACM, 2004.

[18] O. Zamir, and O. Etzioni, “Web document clustering : a feasibility demonstration,” Proceedings of the 21st annual international ACM SIGIR conference on Research and de-velopment in information retrieval, 1998.

[19] N. Imafuji, and M. Kitsuregawa, “Finding web communities by maximum flow algorithm using well-assigned edge ca-pacities,” IEICE transactions on information and systems, vol.E87-D(2), pp.407–415, 2004.

[20] J.W. Ahn, P. Brusilovsky, D. He, J. Grady, and Q. Li, “Per-sonalized web exploration with task models,” Proceeding of the 17th international conference on World Wide Web, pp.1–10, ACM, 2008. [21] 高見真也，田中克己，“検索目的に基づくスニペットの動的再生 成によるウェブ検索結果の個人適応化，”日本データベース学会 論文誌 (DBSJ Letters)，vol.6，no.2，pp.33–36，2007. [22] 村松亮介，横山昌平，福田直樹，石川博，“単語の特徴量を考 慮した検索結果クラスタに関する多視点融合型スニペットの構 築，”第 146 回データベースシステム研究発表会（iDB フォーラ ム 2008），pp.301–306，2008. [23] 村松亮介，横山昌平，福田直樹，石川博，“多視点融合型クラス タリング検索エンジンの開発と評価について，”第 148 回 デー タベースシステム・第 95 回情報学基礎 合同研究発表会，2009. [24] Yahoo!デベロッパーネットワーク http://developer.yahoo. co.jp/.