学位論文紹介

PhD Thesis Review, No. 14

半構造データに対するファセット
検索に関する研究1

はじめに半構造データは構造が明確に定義されていないデータを指し，A Study on Faceted Search for Semistructured Data

データの公開するときにしばしば利用される．半構造データのフォーマットの例としては，XML (Extensible Markup Language)[3] や JSON (JavaScript Object Notation) [5] がある．これらのフォーマットを介して，様々なデータが公開されている．例え

駒水 孝裕

ば，論文目録データの DBLP1 や Twitter2 の API で取得でき♡るデータなどがある．半構造データに対する検索は半構造データを利活用する際の重要な基本技術である．

Takahiro KOMAMIZU

半構造データに対する検索において，ユーザの検索意図が明確でない場合は検索結果が多く，ユーザが満足する結果を得るまでXML をはじめとする半構造データが普及しており，半構造データの利活用が重要な課題となってきている．半構造データのもつ柔軟性からしばしば複雑な構造が記述される．このような半構造データを利活用する上で，必要な情報を探しだす検索技術は重要な基礎技術の一つである．本研究では，探索的検索手法であるファセット検索に注目し，半構造データに対して探索的な検索を可能にする手法を提案する．まず，(1) 代表的な半構造データである XML データに対して，ファセット検索を行うためのフレームワークを提案する．また，(2) XML データは木構造だけでなくグラフ構造も記述可能であり，グラフ構造を有する半構造データに対してファセット検索を可能にする．(3) XML データの XML 部分木を検索対象として抽出する際に，人手が必要となる点について自動化することによってファセット検索を簡単に構築する手法を提案する．加えて，(4) XML データ内のテキストデータをファセット検索の文脈で活用する方法を提案する．に対話的に検索を行う必要がある．一般に検索する際のユーザの検索意図は，明瞭な検索意図と不明瞭な検索意図に大別できる．
前者の場合にはユーザが検索意図を正確にクエリで表現できれば容易に必要な情報を得ることができる．しかしながら，後者の場合には必要な情報を得るために，ユーザは探索的行動を行う必要がある．探索的行動とは，（1）クエリを作成する，(2) 検索結果を吟味する，を目的の情報を得るまで繰返すことである．
ファセット検索 [10] は探索的検索手法の一つで，ユーザの探索的行動をサポートする方法である．ファセット検索において，クエリは属性名と属性値のペアの集合で表される．属性を特にファセットと呼ぶ．ファセット検索において，検索対象データにおけるファセットの値の分布を提示することで絞り込みを行うためのヒントをユーザに表示する．ユーザは自分の興味あうファセットを選択することで絞り込みを行う．また，ユーザは選択済みのファセットを排除することで検索条件を緩めることができる．
ファセット検索は，電子商取引や文献目録の分野を中心に広く用

Semi-structured data such as XML data havebeen used in various situations in order to reuse
information not only in the services but also external applications. Utilizing semi-structured data
is an important challenge. This research especially
focuses on the exploration over semi-structured
data. Faceted search is one of the promising exploratory search methods, therefore, this research
applies faceted search to semi-structured data. In
order to construct a faceted search system, this research works on four directions: (1) a framework toconstruct a faceted search system over XML data
which is a tree-structured semi-structured data, (2)the extended framework for graph-structured semistructured data, (3) an automation scheme for extracting necessary information, and (4) utilizationof textual contents in semi-structured data.

いられている．例えば，Amazon [1] や eBay [2]，DBLP [6]，IEEE Xplore [4] などがファセット検索を用いている．
本研究では，半構造データに対する検索にファセット検索を導入することで，検索意図が曖昧なユーザに対して有効な検索システムを提供する．半構造データに対してファセット検索を適用するために，次の課題を解決する必要がある．ひとつは，(1) 検索対象となるオブジェクトの設定，次に，(2) オブジェクトに対するファセットの設定，最後に (3) 検索メカニズムである．本研究の貢献は以下のようになる．

• 半構造データに対するファセット検索を行うためのフレームワークを提案する．まず，代表的な半構造データである

XML データに対するフレームワークを実現する手法を提案する．次に，より複雑なグラフ構造を有する半構造データに対するフレームワークを実現する手法を提案する．

• ファセット検索インターフェースを構築する際の労力を低減するために，必要な情報であるオブジェクトとファセットの自動抽出手法を提案する．

• 半構造データ中にしばしば含まれる長いテキストを検索に応
♡

正 会 員

筑 波 大 学 シ ス テ ム 情 報 工 学 研 究 科

taka-coma@acm.org

1
214 - 1

http://dblp.uni-trier.de/https://twitter.com/

日本データベース学会

学位論文紹介PhD Thesis Review, No. 14

用し，効果的なファセット値を抽出する手法を提案する．

• 提案手法の被験者実験における検索タスクの決め方を提案する．探索的検索におけるタスクの探索性を表現する指標を設け，この指標に基づくタスク生成方法を提案する．
本稿の以降の構成は以下のようになる．2 節で基本事項としてファセット検索について説明する．3 節で本研究の内容について説明する．4 節で本研究における実験を紹介する．5 節で本稿のまとめと今後の課題について述べる．

2

図 1 XML データ例：文献目録．

ファセット検索
ファセット検索 [10] は属性付きオブジェクトの集合に対して，属性とその値の分布を提示することで検索結果の概要をユーザに示し，ユーザがさらに絞り込みを行うためのヒントとすることを可能にした探索的検索手法である．以下のレコード型データを用いてファセット検索について簡単に説明する．
表 1 車データベース．

車 ID

色種類値段

12黒セダン

赤セダン

150 万
200 万

3

黒SUV

300 万4

白SUV

200 万

図2

フレームワーク概要．

（車
表 1 のデータは，色，種類，値段，の三種類の属性をもつ．

2. 半構造データは複雑な構造（木構造やグラフ構造）をしていID はシステム管理用の識別子である．
）ファセット検索システム
はユーザに各属性（ファセット）の値の分布を提示する（表 2）．

る．複雑な構造に対してオブジェクトやファセットの定義を手動で与えることはデータに対する高度な知識を要求する．
そのため，それらの定義を与えることは容易ではない．

表 2 ファセット．

(a) 色(b) 種類(c) 値段

3. 半構造データはしばしば長いテキストを含んでいることがある．ファセット検索において長いテキストはファセット値と値

頻度値

頻度値

頻度しては有用ではない．しかしながら，長いテキストには有用

黒セダン

22200 万150 万21な情報が含まれていることが多く，活用するべきである．

赤21

白1300 万1SUV

本研究はこれらの課題を解決する手法を提案する．以下の節にて，それぞれの課題に対する手法を紹介する．

ユーザはファセットの内容から興味についてのアイデアを得られ

3.1

る．ユーザは得られたアイデアにもとづいて，絞り込み条件を指定する．ここでは，“色” ファセットから “黒” を選んだとする．
ファセット検索システムは車 ID 1 と 3 のレコードを検索結果としてユーザに返し，同時に，対応するファセットを提示する．こXML データに対するファセット検索

木構造で表現される半構造データである XML データにファセット検索を適用するためのフレームワークを提案する．本研究が着眼した点は，XML データ内で頻出する部分木は何らかのデータのまとまりを表すという点である．図 1 に XML データの例を示す．このデータにおいて paper 要素以下の部分木（図れらの動作をユーザが検索結果に満足するまで繰り返す．

中の点線矩形）が繰返し出現している．この頻出構造は文献を表3

半構造データに対するファセット検索手法している．提案するフレームワークはこのアイデアに基づいてオ

半構造データに対してファセット検索を適用する際に以下に示す課題がある．

ブジェクトを自動抽出する．
提案フレームワークは，構築フェイズ (Construction phase)と検索フェイズ (Retrieval phase) からなる．構築フェイズでは，

1. 半構造データにはオブジェクト及びファセットが明示されて検索対象となる XML データからオブジェクトおよびファセットいない．ファセット検索を適用するためには，オブジェクトの候補を抽出し，システム管理者に提示する．システム管理者は及びファセットを予め定義・抽出する必要がある．

提示されたオブジェクトおよびファセットの候補から実際の検索

14 - 2

日本データベース学会

学位論文紹介PhD Thesis Review, No. 14に用いるものを選別する．これによって，不要なオブジェクトやファセットを排除する．検索フェイズでは，選別されたオブジェ
クトとファセットに対してファセット検索を行うためのインターフェースを提供する．検索フェイズでは，ユーザの入力に応じて対応する XQuery を生成する仕組みを提供し検索結果および対応するファセットを取得し，ユーザに提示する．

3.2

グラフ構造データに対するファセット検索

木構造を有する XML データに対するファセット検索からの拡張として，グラフデータに対するファセット検索を可能にするフレームワークを提案する．実世界データを有するグラフデータは，個々のデータを似たような構造で持っていることが期待される．このアイデアに基づき，頻出部分グラフマイニング [7, 11]を用いて頻出する部分グラフをオブジェクトとして抽出，ファセット検索を実現する手法を提案する．フレームワークの基本骨格は，図 2 と同様であり，オブジェクト及びファセットの抽出に頻出部分グラフマイニングの技術を用いる．

3.3

図 3 検索インターフェース．

オブジェクト及びファセット自動抽出

提案フレームワークにおいて，システム管理者はオブジェクト及びファセットの候補から適切なものを選出しなければならない．この主目的は，不要なオブジェクト及びファセットをユーザインターフェースに提示しないようにするためである．しかしながら，特にデータが巨大で構造が複雑であるとき，この作業はシステム管理者にとって大きな負担となる．
本研究では，システム管理者の負担を減らすべく，オブジェクトおよびファセットを自動で選出するヒューリスティックアプ
ローチを提案する．まず，オブジェクトについては，不必要に頻出になってオブジェクトとして検出されるエラーに着目し，安定して頻出する構造をオブジェクトとして抽出する手法を提案する．次に，ファセットについては，ID のような振舞いをするファセット値を有するファセットが有用でないことが多い事実に着目し，ファセット値の頻度分布に基づく自動選出手法を提案する．
最後に，オブジェクトおよびファセットについて，選出される要素が人にとって有意である点に着目し，辞書に含まれる単語を含む要素をオブジェクト及びファセットとして抽出する．

3.4

Subsumption は単語の共起関係から単語の概念的上下関係を導出する手法である．結果として得られた概念階層の上層部をファセット値として利用することで，オブジェクト集合を徐々に絞り込むことを可能にする．
図 3 に本研究で提案するフレームワークのユーザインターフェースを示す．ユーザインターフェースは四つのコンポーネン
トからなる．一つはキーワード検索を行うためのコンポーネント（図中上部），もう一つはファセットと値を表示するコンポーネン
ト（図中左部），もう一つはオブジェクトの種類（クラス）を表示するコンポーネント（図中右部），最後は検索結果のオブジェクトを表示するコンポーネント（図中中央）である．この図は，DBLP の XML データに対して本フレームワークを適用した際の検索インターフェースである．テキストからのファセット値抽出を行ったファセットは title である．故に，図中の title のファセット値は単語からなっている．

4

テキスト値からのファセット値の抽出提案フレームワークにおいて，長いテキストをファセット値と本研究の有用性を示すために，以下の実験を行った．

してもつファセットは，システム管理者によって，あるいは，自• XML データに対する典型的な問合せ言語 XQuery を用い動的に排除されてきた．これは，長いテキストがユニークな値でた場合とファセット検索を用いた場合の比較．

あり，ファセット検索にとって有用でないからである．例として• グラフデータに対する適用可能性を示す事例検証．
• オブジェクトとファセットの自動抽出の精度実験．
• テキストからファセット値を抽出した場合の有用性を検証すは，文献データにおけるタイトルがある．しかしながら，長いテキストにも有用な情報が含まれている．文献のタイトルには文献の内容を示す内容が書いてあるはずである．本研究ではこのようるための被験者実験．

な内容を表すファセット値を抽出し，より有用なファセット検索システムを提供する．

実験

本稿ではスペースの都合上，最後の項目についてのみ説明する．

本研究では，テキストから内容を表し絞り込みに向いている本研究で行った被験者実験は，ユーザに検索タスクを与え，単語を抽出する．このよう条件を満たす単語を抽出するためユーザがタスクを達成するまでにかかった時間を計測するというに，概念階層を抽出する手法である Subsumption [9] を用いる．

ものである．そのためにまず，タスクを設計する必要がある．タ

14 - 3

日本データベース学会

学位論文紹介PhD Thesis Review, No. 14

keywordfacetedproposedlevel は意図した探索度合いを表現しにくいことが明らかになっ

450

Absolute time (sec).

た．しかしながら，本研究は速やかに目的（タスク）を達成でき400

るファセット検索インターフェースを良い検索インターフェース

350とかんがえるため，本実験は有意義であるといえる．

300

5250

まとめと今後の課題
本稿では，半構造データに対するファセット検索に関する研究

200について提案した．データ指向の半構造データがもつ特性に注目150して，ファセット検索に必要であるオブジェクト及びファセット100を抽出する手法を提案した．今後の課題は，(1) データが分散し50て存在する場合にファセット検索を行う手法の検討，(2) データ分析と組み合わせた手法，などの応用研究が考えられる．加えて，00.035 0.02

0.01 0.004 0.001 0.0048 0.003 0.002 0.001 0.00030.00110.00070.00040.00030.000370.0002

Specification level

探索的検索の評価方法についても研究の余地があると考える．

図 4 被験者実験：タスク達成時間の分布[謝辞]
筑波大学の北川博之教授，天笠俊之准教授を初めとする諸先生

スクの設計にはテンプレートに基づく設計方法 [8] を元にテンプ方やご指導くださった皆様に深く感謝致します．

レートの空欄を埋める語句を選出する方法を提案する．探索的検索の評価を行う上で，タスクがどの程度 “探索的” であるかを示す指標が必要である．これをタスクに含まれる語句の選択率ととらえた指標 specification level を提案し，specification level に基づいてタスクの空欄を埋める方法を提案する．
実験で用いたデータは DBLP の XML データで，title をテキストからファセット値抽出するファセットとした．フレームワー
クを用いることで，文献を表す部分 XML 木 (proceedings やbook など) をオブジェクトとして抽出した．
図 4 に探索度合いを変えた時のユーザのタスク達成時間の分布を示した．横軸は specification level で左に行くほど探索度合いが高く，右に行くほど探索度合いが低くなる．比較対象は，テキストからファセット値を抽出せずにファセット検索を行った場合 (faceted, 白色) とキーワード検索 (keyword, 灰色) である．
図から提案手法が最も効率的に検索出来ていることが読み取れる．特に探索度合いが高いほど，効果的であるといえる．
本実験に用いた specification level の有効性を確かめるため，specification level と実験データの相関係数を観測した（表 3）．
表 3 各種指標と specification level の相関係数．

measurement

keywordfacetedproposedtime

0.771346

0.655485

0.841967# operations

0.236971-0.411838-0.122954# keywords

0.236971-0.39138-0.063875# facets—-0.299988-0.122954

この表から specification level と時間 (time) に強い正の相関があり，specification level を変化させた時に探索時間に影響が強いことが明らかになった．一方で，キーワード検索の利用数やファセットの選択数とは相関があまりないことが観測された．故に，[文献][1] Amazon.com. http://www.amazon.com/.
[2] eBay. http://www.ebay.com/.
[3] Extensible Markup Language (XML). http://www.w3.
org/XML/.
[4] IEEE Xplore Digital Library. http://ieeexplore.
ieee.org/Xplore/home.jsp.
[5] JSON (JavaScript Object Notation). http://www.
json.org/.
[6] The DBLP Computer Science Bibliography. http://www.informatik.uni-trier.de/~ley/db/.
[7] S. Ghazizadeh and S. S. Chawathe. SEuS: Structure Extraction Using Summaries. In Discovery Science, pages
71–85, 2002.
[8] B. Kules, R. Capra, M. Banta, and T. Sierra. What do
exploratory searchers look at in a faceted search interface? In JCDL, pages 313–322, 2009.
[9] M. Sanderson and W. B. Croft. Deriving Concept Hierarchies from Text. In SIGIR, pages 206–213, 1999.
[10] D. Tunkelang. Faceted Search. Synthesis Lectures onInformation Concepts, Retrieval, and Services. Morgan& Claypool Publishers, 2009.
[11] F. Zhu, Q. Qu, D. Lo, X. Yan, J. Han, and P. S. Yu.
Mining Top-K Large Structural Patterns in a Massive
Network. PVLDB, 4(11):807–818, 2011.

駒水 孝裕 Takahiro KOMAMIZU
2011 年筑波大学システム情報工学研究科博士前期課程修了．
2015 年筑波大学システム情報工学研究科博士後期課程修了．博士（工学）．ACM 会員．日本データベース学会正会員

ファセットの選択数を基準とした被験者実験では specification

14 - 4日本データベース学会