The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014

大規模異分野データ横断検索における
時空間情報を用いた疑似適合性フィードバック

2E5-OS-25b-2

Spatio-Temporal Pseudo Relevance Feedbackfor Large-Scale and Heterogeneous Scientific Data Search System
竹内 伸一∗1

赤星 祐平∗1

Bun Theang Ong∗1

杉浦 孔明∗1

是津 耕司∗1

Shin’ichi Takeuchi

Yuhei Akahoshi

Bun Theang Ong

Komei Sugiura

Koji Zettsu∗1

独立行政法人 情報通信研究機構

National Institute of Information and Communications Technology

As larger and larger amounts of data are harvested, ﬁnding just the right piece of information out of this noisy
and heterogeneous ocean of data remains challenging. Many widely adopted scientiﬁc data search engines continue
to be mainly based on text semantics. However, it is not uncommon in scientiﬁc big data applications to facecollected data that do not possess text information. In this scenario, search engines fail to retrieve potentiallyrelevant data. In this work, we propose a novel pseudo relevance feedback method based on spatio-temporaland text (STT) information for scientiﬁc big data: STT-PRF. Although STT-PRF may simultaneously use STT
information, we show that the missing values in space, time or/and the text are handled eﬃciently. We tested our
STT-PRF method using the Pangaea repository. Experimental evaluations show that STT-PRF outperforms thestandard baseline methods.

1.

はじめに

する．人手によって得られたキーワードと検索結果の対応情報
を次回以降の検索に反映させることで精度の向上を図る．疑似適合性フィードバック (Pseudo Relevance Feedback, PRF)
[3, 4] は RF の人手による部分を省略し，検索結果上位を仮に適合している文書とみなして入力クエリと併用する，クエリ拡
張手法のひとつである．PRF の拡張については様々な研究がなされており，テキスト情報の活用としては協調的タグ付けシ
ステムによるセマンティックアノテーションを用いたクエリ拡
張 [5] がある．また，マイクロブログのテキスト情報を活用した動的な PRF[6, 7] では，時間情報の有用性が示されている．
筆者らはこれまでに，社会学と自然科学など全く異なる分
野間のデータを組み合わせることで新たな科学的知見を得ることを目的とした，異分野データ横断検索システム Cross-DB
Search System [8] を開発してきた．本稿では Cross-DB Search
System の検索性能向上のため，テキスト情報に加えて時空間
情報を併用した科学データ検索のためのクエリ拡張手法を提案する．本稿は以下のように構成されている．第 2. 節で提案手法である時空間情報を併用する疑似適合性フィードバックと，そのためのデータセット間時空間距離の定義について述べる．
第 3. 節で性能評価実験と空間クエリ拡張例について述べ，第4. 節でまとめと今後の課題について述べる．

Jim Gray によって提唱された「第四のパラダイム」は今日の科学研究手法のありかたについて，実験科学，理論科学，計算科学を経てデータ中心科学に到ったとしている [1]．第三のパラダイムにおいて個別に収集され分析されていた様々な科学
データを集約し，それらを分析することで新たな科学的知見を発見するという考えは，増大する今日の計算資源によって実現が可能となった新しい科学的探求として今後発展していくと考えられる．一方で観測された科学データの共有や再利用，そのためのメタデータ定義，さらにはデータの蓄積，参照方法など解決すべき課題もあり，そのために国際的，学際的な連携が必要である．
科学データを再利用する際に最低限必要となるのが，それらのメタデータを管理するインデックスであり，またそれに基づいて科学者が必要とするデータを検索するシステムである．
World Data System (WDS) ∗1 や Pangaea ∗2 は地質学や海洋学など地球科学の分野に特化した科学データ検索のポータルを提供している．
Web ページや文書データと大きく異なる科学データの特徴
として，テキスト情報が豊富でない点がある．数値や画像がデータ本体であり，テキスト情報は題目や作成者名，ある程度の概要文などに限定される．このためテキスト情報に基づく従来の検索システムでは，本来なら入力されたキーワードに関係するデータを発見できない可能性がある．一方でメタデータからは収録された際の時空間情報や対象とするパラメータなど，
テキスト以外の情報も多く含まれており，これらを活用することによってテキスト情報の不足を補うことが可能であると考えられる．
適合性フィードバック (Relevance Feedback, RF)[2] は検索システムの精度向上手法のひとつで，ユーザーは提示された検索結果のなかから入力したキーワードと関連するものを選択

2.

本節では提案手法である時空間情報を用いた疑似適合性フィードバック (Spatio-Temporal and Text Pseudo RelevanceFeedback, STT-PRF) について述べる．STT-PRF はテキス
ト情報のみを用いる PRF に対し，時空間情報を活用するよう拡張したものである．

2.1

STT-PRF を用いた科学データ検索システム

図 1 に STT-PRF を用いた検索システムの概略図を示す．
検索部はユーザーからのキーワード入力を受け取り，テキストクエリとしてインデックスから一度目の検索を行う．テキスト
スコア計算部は各データセットのテキストクエリに対するス
コア ϕk の計算を行い，スコア上位のデータセットから順に結連絡先: 〒 619-0289 京都府相楽郡精華町光台 3-5 (独) 情報通信研究機構 ユニバーサルコミュニケーション研究所∗1∗2

時空間情報を用いた疑似適合性フィード
バック

http://www.icsu-wds.org/
http://www.pangaea/de/1

The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
ト y とクエリ中のデータセット y ′ との間の空間/時間情報に関する距離を定める必要がある．本節ではデータセットの時空間情報に基づく距離について述べる．
データセットの時空間情報は始点 xb および終点 xe の対で与えられる．時間情報に関してはそれぞれ開始時刻および終了
時刻が相当し，例えば 1990 年から 2000 年に得られたデータで構成されるデータセットであれば (xb , xe ) = (1990, 2000)となる．空間情報に関しては，緯度について南端および北端
が，経度について西端および東端が相当する．
上記で定めた始終点に基づいてデータセットの時空間情報を正規分布で近似する．このときその平均 µ および分散 Σ は，
始終点 xb および xe から得られる一様分布の平均および分散に基づき果として検索部に返される．本稿では ϕk としてデータセットとテキストクエリの TF-IDF ベクトル間のコサイン距離を用いた．
System Input
Text Query
Text Query

Search Engine

Query Search
DS
DSSpace Query
Constructor

Space Score
Calculator

Time Query
Constructor

Text Query
Constructor

Time Score
Calculator

Time QuerySpace Query

Text Score
Calculator

Text QuerySTT Query
Constructor

STT ScoreCalculator

STT Query
STT Query(4)1(xe − xb )2 .
12

(5)

DS Index

Query Search
DS
DS

Σ=

System Outputと定める．時間情報は 1 次元の，空間情報は 2 次元の正規分布として表現される．データセット yi と yj 間の空間/時間距
離を正規分布間のバタチャリヤ距離 [9] と定める．二つの連続
分布 p および q 間のバタチャリヤ距離は式 (6) で示され

図 1: STT-PRF の概略図(∫

次にクエリ拡張を行う．通常の PRF と同様に検索結果の上
位 L 件を適合していると仮定し，仮適合データセット集合 YLを決定する．PRF と共通するテキストクエリ構築部は，YL に含まれるデータセットのテキスト情報を追加のテキストクエリ
としてクエリの再構築を行う．STT-PRF はさらに YL から構
築される空間クエリとして YL 中の各データセットの空間情報の集合を用い，同様に時間情報の集合を時間クエリとする．これらを統合して空間/時間/テキストクエリ (STT クエリ) を構築し，それに基づいて二度目の検索を行う．
二度目の検索ではインデックス内の各データセットに対し，
空間/時間/テキストクエリに対するスコアが計算される．仮適
合データセット集合 YL から作成した空間/時間クエリに対す
るデータセット y の空間スコア ϕs (y) および時間スコア ϕt (y)はそれぞれ式 (1) および (2) で与えられる．

d(p, q) = − ln)√p(x)q(x)dx ,(6)正規分布 yi および yj を用いた場合は式 (7) のように変形される．

[

d(yi , yj ) =

]

−1
1
1
(µi − µj )⊤(Σi + Σj )(µi − µj )
8
2

{

1
+ ln
2

det( 12 (Σi + Σj ))

}

√

.

(7)

det(Σi ) det(Σj )ϕs (y) = exp{−( minds (y, y ′ ))2 },′(1)

一般的に検索システムへの入力としての時空間情報は結果の絞り込みに用いられ，その始終点内に含まれる結果のみを返す
ことが多い．データセット間の距離を定義することで，クエリに対する距離計算が可能となり結果のランキング等が実現できる．

ϕt (y) = exp{−( mindt (y, y ′ ))2 }.
′

(2)

3.

y ∈YL

y ∈YL

ϕ(y) = ws ϕs (y) + wt ϕt (y) + ϕk (y).

評価実験

本節では提案手法である STT-PRF の性能評価実験について述べる．自然科学分野のデータセットを検索対象として複数のキーワードで検索を行い，検索結果から求めた評価指標でSTT-PRF の有効性を示す．

ここで y ′ は YL に含まれるデータセットを表し，ds およびdt は 2.2 節で述べる二つの空間/時間情報の間の距離を表す．
データセット y の時空間およびテキストスコアから得られる
統合スコア ϕ(y) を式 (3) に示す．

3.1

実験条件

表 1 に評価実験で用いた 20 個の検索キーワードを示す．検索キーワードは自然科学に関するもので，科学分野のオント
ロジー，最近の研究分野，実際の検索キーワードの 3 種からそれぞれ収集した．科学分野のオントロジーとして，SWEET
Ontology ∗3 内のコンセプト名から 7 個を用いた．SWEET
Ontology は科学分野全体をカバーする包括的なオントロジー
であるが，今回は地球科学および環境科学の分野から選択した．
最近の研究動向由来のキーワードとして，Microsoft Academic
Search ∗4 の環境科学分野のキーワードから 6 個を選択した．

(3)

ここで ws および wt は空間情報および時間情報に対する重みを表す．二度目の検索ではインデックス中の各データセットに対し統合スコアの計算を行い，統合スコア上位のデータセット
からから順に結果として検索部に返す．

2.2

1(xe + xb ),2µ=

データセット間の時空間距離

PRF は二度目の検索でもテキストクエリのみを用いるが，STT-PRF では空間/時間クエリを併用する．各クエリとイン
デックス中の各データセット間のスコアはそれぞれ式 (1) および (2) で与えられるが，これに際しスコア計算対象データセッ∗3 http://sweet.jpl.nasa.gov/ontology/∗4 http://academic.research.microsoft.com/

2

The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014
実際の検索キーワードとして Google Trends ∗5 の科学分野内のキーワードおよび Cross-DB の検索キーワード履歴から 7個を選択した．

R@n =

SWEET

MSAS

GoogleTrends & Cross-DB

global climate
natural gas
ocean current
black carbon
ozone holeash ﬂow

atmospheric circulationinterannual variability
sea level pressure
water quality
carbon cycle
particulate matter
boreal forest

DCG@n,
IDCG@n

DCG@n

=

r1 +

n
∑
ri
i=2

log2 i

ここで rel(n) は n 番目のデータセットがキーワードに関連すれば 1 を，しなければ 0 を返す関数である．

∗5

tp@n
,
tp@n + f p@n

性能評価

表 2 に概要削減率を変化させた場合の 20 キーワードに対する性能評価指標の平均値を示す．表中の ave. #hit は平均デー
タセット検出数である．ST-PRF は概要が 50% 以上削減されている場合，平均データセット検出数，R@30，AP においてbaseline を上回る性能を示す．これはテキスト情報が不足しが
ちな科学データ検索において，時空間情報を用いたクエリ拡張を行うことでテキスト情報では対象外とされたデータを発見することが可能となったことを意味する．一方で nDCG@30 お
よび P@30 は baseline に及ばない場合もあるが，その差は大きくなく，また ST-PRF がクエリ拡張のための手法でありリランキングは目的としていないためでもある．
表 2: 各手法の性能比較
手法

100% 削減

99% 削減98% 削減95% 削減90% 削減80% 削減(8).

50% 削減ここで ri はランキング第 i 番目のデータセットの関連度を表
し，IDCG@n はランキングが関連度の大きい順に並んだ理想的な場合の DCG@n を表す．同様に検索結果上位 n 件でのP@n および R@n はそれぞれ以下の式で与えられる．

P@n =

(11)

n=1

検索対象の科学データとして Pangaea が持つデータセットを用いた．Pangaea のデータセット検索システムを用いて表 1
内の各キーワードで検索を行い，得られた検索結果の上位 120
件をそれぞれのキーワードに対する検索対象のデータセット集合とした．各データセットには環境科学分野の修士号を持つ作業者 1 名によって 4 段階の関連度が付与されている．関連度
はキーワードとデータセットが全く関連しない場合は 0 が，非常に関連する場合は 3 が，その中間の場合に 1 または 2 があてられる．さらに関連度が 2 または 3 のデータセットをキーワードに関連すると見なし，0 または 1 のデータセットをキーワードに関連しないと見なした．
STT-PRF は空間/時間/テキストの全てについてクエリ拡張を行えるが，一部についてのみ行うことも可能である．評
価実験では時間情報のみクエリ拡張を行う場合 (T-PRF)，空間情報のみの場合 (S-TRF)，時空間情報の場合 (ST-PRF) の3 種類について性能評価を行い，クエリ拡張を行わない場合(baseline) の結果と比較して時空間情報を活用することの有効性を示す．クエリ拡張に用いる仮適合データセット数 L は 10とし，空間情報および時間情報に対する重み ws ，wt は予備実験の結果からそれぞれ 0.370 および 0.074 とした．さらに実験に用いるキーワード毎のデータセット集合に対し，一定割合でデータセットの概要情報の削減を行う．本稿では削減率を100%，99%，98%，95%，90%，80%，50% および 0% とした．例えば削減率 100% はデータセット集合中の全データセッ
トから概要が削除されていることを意味し，この場合残るテキスト情報は題目及び著者名のみとなる．
本稿では性能評価に用いる指標として nDCG@30，Precision@30(P@30)，Recall@30(R@30) 及び Average Precision(AP) を用いた．nDCG はランク付けされた検索結果が関連度順にどれだけ並んでいるかを表し，上位 n 件から求める
nDCG@n は式 (8) によって定義される．

=

1 ∑rel(n)P@n,
N
N

AP =

3.2

nDCG@n(10)

ここで tp@n および f p@n はそれぞれ上位 n 件までの真陽性，偽陽性を表す．本実験では検索対象となる総データ数が判明しており，f n@ALL は全件での偽陰性を表す．Average
Precision は式 (11) で定義される．

表 1: 評価実験用キーワード

marine biology
sedimentacid rain
aerosol
global warming
air pollution
southern oscillation

tp@n,
tp@n + f n@ALL

0% 削減

baseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFbaseline
T-PRF
S-PRF
ST-PRFave. #hit
11.64
16.50
16.50
18.93
12.29
17.21
19.93
22.36
12.71
17.93
21.07
23.79
14.43
22.79
28.50
33.36
16.79
26.29
32.71
37.57
22.50
34.14
37.43
45.00
38.79
51.36
51.00
59.86
66.43
76.43
71.36
79.00

nDCG@30
0.54
0.47
0.49
0.46
0.61
0.53
0.59
0.56
0.75
0.67
0.63
0.60
0.68
0.58
0.59
0.58
0.69
0.58
0.62
0.61
0.73
0.67
0.71
0.70
0.82
0.80
0.84
0.82
0.82
0.79
0.82
0.81

P@30
0.35
0.31
0.33
0.33
0.39
0.36
0.40
0.39
0.40
0.36
0.42
0.41
0.38
0.38
0.37
0.38
0.38
0.39
0.37
0.37
0.45
0.45
0.46
0.46
0.55
0.47
0.53
0.50
0.60
0.53
0.53
0.50

R@30
0.07
0.08
0.08
0.09
0.07
0.08
0.11
0.12
0.07
0.08
0.13
0.14
0.09
0.12
0.18
0.20
0.10
0.15
0.19
0.20
0.16
0.19
0.22
0.23
0.35
0.33
0.40
0.41
0.51
0.49
0.50
0.50

AP
0.08
0.10
0.12
0.12
0.08
0.11
0.14
0.14
0.09
0.11
0.14
0.15
0.10
0.13
0.18
0.19
0.12
0.14
0.20
0.21
0.16
0.18
0.23
0.24
0.29
0.33
0.38
0.38
0.53
0.54
0.56
0.55

(9)
また，S-PRF の性能は T-PRF を上回る傾向にある．これは検索対象であるデータセット集合の時空間情報保有率に依存する

http://www.google.com/trends/

3

The 28th Annual Conference of the Japanese Society for Artificial Intelligence, 2014と考えられる．例えばキーワードが “atmospheric circulation”の場合，全 120 データセット中時間情報を持つものは 33 件であるのに対し，空間情報をもつものは 115 件と大きく異なる．これは Pangaea から得られたデータセットに共通する傾向であり，その他のキーワードに関しても同様であった．これらのことから PRF の性能が検索対象のテキスト情報保有率に依存することと同じように，ST-PRF は検索対象の時空間情報保有率に依存することがわかる．

3.3

空間クエリ拡張例

図 2 から 4 に空間クエリ拡張による検索結果の変化例を示す．図 2 はキーワード “natural gas “ に対するデータセット
集合の空間分布を表す．図中の緑丸は関連のあるデータセットの中心点を，赤菱は関連のないデータセットの中心点を表す．
このとき，前者は主に北アメリカに分布し，後者はそれ以外の場所に分布する傾向がみられる．図 3 はテキスト情報による
1 回目の検索結果で得られたデータセットの分布を示す．検索結果として関連しないデータセット 1 件を含む 5 件が得られ，
これを空間クエリとして 2 回目の検索が行われる．1 回目の検索結果でキーワードに関連する結果が空間クエリに多く含まれており，これらに対して空間スコア ϕs が高いものが 2 回目の検索で得られることになる．空間クエリ追加後の検索結果を図4 に示す．北アメリカに分布するデータセットによって，その近辺の関連するデータセットが新たに検索されていることが分かる．

図 3: テキスト情報のみによる検索結果 (=空間クエリ)

図 4: 空間クエリ追加後の検索結果[2] I. Ruthven and M. Lalmas, “A survey on the use of relevance
feedback for information access systems,” The Knowledge Engineering Review, Vol. 18, No. 2, pp. 95–145. Jun. 2003.
[3] C. Carpineto and G. Romano, “A survey of automatic query
expansion in information retrieval,” ACM Computing Surveys,
Vol. 44, No. 1, pp.1:1–1:50, Jan. 2012.

図 2: ”natural gas” の検索対象データセット集合

4.

[4] C. Buckley, G. Salton, and J. Allan, “Automatic retrieval withlocality information using SMART,” in Proc of the 1st Text Retrieval Conference (TREC-1), pp.59–72. 1992.

まとめ[5] C. Lioma, M. F. Moens, and L. Azzopardi, “Collaborative annotation for pseudo relevance feedback,” in Proc. of the ECIR’
08 Workshop onf Exploiting Semantic Annotations in Information Retrieval, pp.25–35. 2008.

本稿では検索対象のテキスト情報を用いてクエリ再構築，再検索を行う疑似適合性フィードバックに対し，クエリ再構築の対象を時空間情報へと拡大した STT-PRF を提案した．また，そのために必要となる時空間情報に基づくデータセット間の距離を，正規分布間のバタチャリヤ距離に基づいて定義した．評
価実験によって，テキスト情報が不十分な場合における提案手法による時空間情報を用いた再検索の有効性が示された．
今後の課題としては，時空間距離定義を活用したデータセッ
トのクラスタリング，時空間以外の情報を用いた疑似適合性
フィードバック (X-PRF)，Cross-DB への応用による異分野
検索時の傾向の調査などがある．

[6] L. Chen, L. Chun, L. Ziyu, and Z. Quan, “Hybrid pseudorelevance feedback for microblog retrieval,” Journal of Information Service, Vol. 39, No. 6, pp.773–788. Dec. 2013.
[7] S. Whiting, I. A. Klampanos, and J. M. Jose, “Temporal pseudorelevance feedback in microblog retrieval,” in Advances in Information Retrieval, ser. Lecture Notes in Computer Science,Vol. 7224, pp.522-526. 2012.
[8] Eloy Gonzales, Bun Theang Ong, and Koji Zettsu, “Searching
Inter-disciplinary Scientific Big Data based on Latent Correlation Analysis,” in Proc. of the IEEE International Conference
on Big data, pp. 6–9. Santa Clara, US. Oct. 2013.

参考文献[9] A. Bhattacharrya, “On a measure of divergence between two statistical populations defined by their probability distributions”,
Bulletin of the Calcutta Mathematical Society Vol. 35, pp.99–
109. 1943.

[1] Tony Hey, Stewart Tansley, and Kristin Tolle (eds.), “The Fourth
Paradigm: Data-Intensive Scientific Discovery”, Microsoft Research, 2009.

4