DEIM Forum 2016 E1-6

同一閲覧・検索意図に合致する Web ページ群の発見と再訪問ページ推薦武田 裕介†

大島 裕明†

田中 克己†† 京都大学大学院情報学研究科 〒 606–8501 京都府京都市左京区吉田本町
E-mail: †{takeda,ohshima,tanaka}@dl.kuis.kyoto-u.ac.jp
あらまし 本論文では，過去に検索・閲覧した Web ページの中から，現在閲覧中の Web ページの情報要求と同じ情報要求の元で検索・閲覧されたページ群を発見しユーザに推薦する手法を提案する．再訪問に失敗しているユーザに対してこのようなページを推薦することで再訪問を支援する．再訪問に失敗しているユーザが探しているページは現在の情報要求を満たすページである．従って，その時の情報要求と同じ情報要求の元で過去に検索・閲覧されたページ群の中に目的のページが存在すると考えられる．このような Web ページを発見するために，クエリの類似度やリンク構
造，閲覧時刻の近接性といった検索・閲覧行動に関係する複数ページ間の関係を使用する．計算時間の削減と精度の向上のために閲覧したページを分割し，現在と関連するページ集合の中から目的のページを探しだす手法を提案する．
キーワード

再発見，再訪問

1. は じ め に
近年の Web の発達に伴い，Web には大量の情報が蓄積されてきた．Web 上を検索・閲覧することで様々な情報を得ることが可能になった．以前に閲覧した Web ページを再び閲覧しようとすることも多い．訪問したページの内 44%が再訪問であったり [16]，33%のクエリが再発見のためのもの [19] であるという報告もある．このことからもユーザはページを日常的に再訪

ページへのアクセス方法に
関する記憶
再生可能
再認可能
再認不可能

-.//&&0&0)1.')*"+,"'2!"##$$%$%&!"#$%&'&%()*"+,"'+,#-,.#)-".

'()*$%

再認不可能

再認可能

再生可能

ページの存在に関する記憶問していることが分かる．しかし，以前に発行した検索クエリ

図 1: ページを閲覧したこととページヘのアクセス方法の記憶を忘れたり，どのリンクをたどったかを忘れたりして，以前にに基づく閲覧ページの分類

閲覧したページの再訪問に失敗することがある．
ページを再訪問するためには，Web ブラウザのブックマー

前に「喫煙の罰則について調べる」という情報要求で訪問した

ク機能を利用したり，閲覧履歴を参照したりするという方法がページである．現在の情報要求も「喫煙の罰則について調べる」

ある．しかし，ブックマークしていないページであってももうということである．このようなことから，現在閲覧中のページ

一度閲覧したいと思うページは存在する．また，ページ単位のの同位ページの中に目的のページが存在すると考えた．

ブックマークでは，作業中の文脈や閲覧した複数のページ間のユーザがどのようなページの再訪問を試みて，どのような場関係が失われ，文脈を考慮した再訪問ができないという問題点

合にページの再訪問に失敗するのかということをページに関すがある．閲覧履歴を参照するにしても，ユーザは大量のページ

る記憶に基いて図 1 のように分類した．ページの記憶量は以下を閲覧するので，閲覧履歴の中から目的のページを探しだすこの独立する 2 軸によって表すことができると考えた．（1） ペーとは困難であると考えられる．

ジを閲覧したことに関する記憶：そのページを閲覧したという本研究では，ユーザが過去に閲覧したページの中から，現在行為に関する記憶を意味する．ページ内容を覚えているかどうの情報要求と同じ情報要求を満たすために閲覧されたページをかは関係ない．（2） ページのアクセス方法に関する記憶：そ推定する手法を提案する．これは，現在閲覧しているページののページを訪れるために用いたクエリや，どのようなリンクを同位ページを推定する手法を提案するといえる．同位ページと辿ったかというアクセス方法に関する記憶を意味する．心理学

は同じ情報要求を満たすために訪問されたページを意味する．

の分野において忘却度合いは “再生” と “再認” を用いてしばし

このようなページを推薦することで再訪問支援を行う．

ば分類されており [21]，本研究においてもこれに従った．以上

例えばシンガポールの公共の場における喫煙の罰則についての 2 軸を用いて閲覧したページを分類した．(1) Failed：ユー

調べたユーザがいると想定する．このユーザがその 1 週間後にザはそのページを覚えており，再訪問を試みることがある．し

喫煙の罰則についての情報を見直すために，以前に訪れた禁煙

かし，検索クエリやどのリンクをたどれば良いかといったアクの罰則に関するページの再訪問を試みた．しかし，以前とは少セス方法を忘れてしまっており，再訪問ができずに苦戦する．

し異なる検索クエリを発行してしまい目的のページが検索結ページ推薦を切望すると考えられるので本研究ではこのケー

果ページに現れなかった．結果，以前に訪問したページの再訪スに注目した．(2) Unconscious：ユーザはそのページを訪問し問に失敗した．このとき，再訪問しようとしていたページは以たことすら忘れてしまっている．しかし，そのページが推薦されれば訪問したことを思い出し（再認する），再訪問すると有ろうページを推薦する手法を提案した．Tyler ら [23] は以前の用か判断できる．ユーザはページの存在を忘れているのでもしクエリと検索結果を考慮して検索結果を再ランキングする手法

推薦されなくても不自由は感じない．(3) Succeeded：ユーザはを提案した．

そのページを再訪問することができる．しかし，時間がかかる

再発見のためのシステムに関する研究は以下のものがあためページ推薦による支援を望むことがある．もしページ推薦

る [2], [5], [7], [9], [10], [11], [12], [13], [14], [20]．Kawase ら [10]

されなかったとしてもそのページに再訪問することができるのは次に再閲覧するページを推定して表示するシステムを提で問題はない．Completely forgot ケースや Succeeded-but-forgot

案した．彼らはブラウザの履歴情報を利用して評価を行った．

ケースに分類されるページをユーザは再認できないので，再訪ユーザが閲覧したページが再訪問のときに，それ以前の閲覧問のための推薦としては望まないと考えた．

ページを利用して再訪問したページを予測できるかということ

現在閲覧中のページと同じ情報要求で閲覧・検索されたペーをログベースで評価した．本研究では，ユーザアンケートによジを推定するために，検索クエリやリンクによるページ遷移，り，再発見に困っている時とその時に推薦して欲しいページと閲覧時刻近接性といったユーザの検索・閲覧行動を利用する．

いう情報を収集して評価を行った．Kawase ら [9] はまた検索エ

実際の推薦アプリケーションとして使用する際には計算速度もンジン，オンラインブックマーク，オンラインアノテーション

重要である．閲覧ページをセッション毎に分割し，現在と関連という 3 つの再発見手法の違いを評価した．彼らはブックマー

するセッションで閲覧されたページから現在閲覧中のページと

クとアノテーションが検索を行うよりも有用であるという知同じ情報要求で閲覧・検索されたページを推定する．これによっ見を得た．さらに，アノテーションはページ内容の再認というて計算速度が早くなるだけでなく，精度の向上が想定される．

点でブックマークよりも有用であるという知見を得た．Morris

提案手法の有用性を確かめるためのユーザ実験から以下のよ

ら [14] は閲覧履歴をトピックとクエリによって階層化し，表示

うな知見が得られた．(1) 現在閲覧中のページの同位ページのするシステムを提案した．Aula ら [2] はサムネイルとタイトル

推薦は再訪問におおよそ有用である．(2) リンクの遷移と閲覧を表示することがページの再認に有用であるという知見を得た．

時刻近接性を用いた同位ページ推定手法はベースライン手法を

Teevan ら [20] は視覚的なスニペットを提案し，これがテキス上回った．(3) クエリの類似度を用いた同位ページ推定手法はトスニペットよりも小さく再訪問に有用であると分析した．Li

セッション分割と関連セッションの取得が完全に成功したと仮ら [11] や deng ら [5] はコンテキストを利用して閲覧履歴を改定した場合にベースライン手法を上回った．(4) セッション分割

良する手法を提案した．Mackay ら [12] はランドマークを付けと関連セッションの取得は精度の向上に有用である．

ることができるブックマーク機能を提案した．ランドマークは

2. 関 連 研 究

ページの気になる文章にハイライトを付けることができる機能であり，そのページを再訪問した際にもハイライトは表示されJones と Klinkner [8] はクエリを goal，mission，session に分る．Web ブラウザの Firefox1 で使用されている Frecency アルゴ

類した．session は一定時間行動がなかった場合に分割されるもリズム [7] はページをどれくらい最近閲覧したか，どの程度頻のである．goal とは極小の情報要求を差し，1 つ以上のクエリ

繁に閲覧したかということを考慮したページのスコアを付けるによって構成される．mission とは関連する情報要求の集合を

アルゴリズムである．このスコアはロケーションバーでの推薦

差し，1 つ以上の goal によって構成される．

においてランキングを付ける際などに利用される．

再発見・再検索時のユーザの行動の分析を行った研究は以下のものが挙げられる [1], [3], [6], [15], [17], [18], [22], [23]．Nishi-

3. 再訪問のための同位ページ

moto ら [15] は，再発見の際の三つの問題点を挙げた．それは最3. 1 問 題 定 義

初の検索の際には重要だと思わなかったことが重要になること，本研究において取り組む再発見問題について定義する．URI に

閲覧のコンテキストが失われること，発見時と再発見時では知よって識別されるページ集合 P = {p1 , . . . , pm } がある．これらは識が異なっていることである．Teevan [18] は以前と同じクエリ

ユーザの n 回のページ訪問 V = {v1 , . . . , vn }, m <= n, page(vk ) ∈ Pを入力することができても，検索エンジンはいつも同じ結果をの 間 に 閲 覧 さ れ た ペ ー ジ で あ る ．ま た ，訪 問 順 序 の 集 合

返すとは限らないという問題点を示唆している．Capra [3] は，

I = {i(v1 ), . . . ,i(vn )} がある．i(vk ) は 1 から始まり，ページ

再発見の種類について Exact，Path，Subset，Move の 4 種類に訪問が行われるたびに 1 増加する．このとき，再発見に有用な分類した．Tyler ら [22] は再検索を行う際のクエリと元のクエ

ページ順に pi ∈ P をランキングするという問題を解く．入出力

リでは，再発見を行う際のクエリのほうが良いクエリとなっては以下の通りとなる．

いることを分析した．Pu ら [17] は発見時と再発見時の検索の入力

行動を比較をした．再発見時にはより多くのクエリ，サーチエ

P = {p1 , · · · , pm }, V = {v1 , . . . , vn }, I = {i(v1 ), . . . ,i(vn )},ブラウザにより取得されるユーザの全ての閲覧・検索行動(P, <= ), <= ⊂ P × P,

ンジンを使用するという知見を得ている．Adar ら [1] は，ペー出力ジが再訪問されるのが以前の訪問からどれくらい時間が経って<= は P の全順序を表す．この問題定義は Kawase ら [10] のものと類似している．彼らは次 (n+1) に閲覧するであろうページをからなのかによって，ページが特徴付けられるということを分析した．Eirinaki ら [6] は PageRank とマルコフモデルを用いてユーザの行動を推定し，次あるいはその少し先に閲覧するであ（注 1）：http://www.mozilla.jp/firefox/

#%!

"information need"browsed page

information about sightseeing
spot in Singapore!

Q!

類似

p

: 閲覧中

is-a!

is-a!

近い時刻に閲覧Link!

#$! information about#&! information about

Merlion Park!

visited-for!

answer-for!
visited-for!

p1!

p! : 推薦される

Q’!

Marina Bay Sands!

answer-for! answer-for!

p2!

p1

p2

同位

[クエリ類似度]
p3!

p1

p3

p2

p3

同位

[リンクによるページ遷移]

p1

p2

p3

t!

同位

[閲覧時刻近似性]

p4 !

図 3: 同位ページを推定するための検索・閲覧行動
currently browsed!

previously browsed!

図 2: 情報要求と閲覧ページの関係を表すグラフ

3. 3 再訪問のための同位ページ
ページ pi とページ p j がある情報要求 n と visited-for 関係に推定しているのに対して，本研究は現在推薦してほしいページ

あるとき， pi と p j は n において同位であると定義する．同位を推定することを目的としている．上記の問題を解くことで得関係集合 Rcoordinate は下記の用に表される．

られる上位 k 件のページを推薦する．

3. 2 情報要求と閲覧ページ
本研究では現在閲覧中のページと同じ情報要求の元で閲覧・

Rcoordinate = {(pi , p j , n) | pi , p j ∈ P, n ∈ N,
(pi , n) ∈ Evisited-for , (p j , n) ∈ Evisited-for }検索されたページに注目したページ再訪問手法を提案する．な

同位ページは、ある情報要求 n 上での同値関係とみなすことがぜ，このようなページを推薦するのが良いのかを説明するためでき，反射律，対称律，推移律を満たす．本研究の目的は現在に，まずユーザの情報要求と閲覧したページの関係について述

閲覧中のページの同位ページを以前に閲覧したページの中からべる．ユーザの情報要求と閲覧したページの関係は図 2 のよう推定することで達成されると考えた．前節で述べた例についてに表される．ユーザの今までの情報要求全ての集合を N ，閲覧も， p1 と p3 は同位ページの関係にある．

した全ての Web ページの集合を P とすると，その関係は有向

3. 4 実際の同位ページの推定手法

非巡回グラフ G = (N ∪ P, E) によって表すことができる．ここ

ユーザの情報要求を正しく推定することは困難であり，情報

でエッジ集合 E は，E = Evisited-for ∪ Eanswer-for ∪ Eis-a と表され要求の階層構造を求めることは難しい．実際に同位ページを推る．それぞれのエッジ集合は以下のように表す．

薦するにあたり，情報要求の階層構造とそれぞれの情報要求のEvisited-for B {(n, p) | n ∈ N, p ∈ P, n is visited-for p} ⊂ N × P

内容には焦点をあてない．例えば，図 2 において， p1 と p3 はEanswer-for B {(n, p) | n ∈ N, p ∈ P, n is answer-for p} ⊂ Evisited-for

n2 において同位である．実際に同位ページを推薦する際には，

Eis-a B {(ni , n j ) | ni ∈ N, n j ∈ N, ni is-a n j } ⊂ N × N
Evisited-for と Eanswer-for は無向エッジ集合であり， Eis-a は有向n2 が n1 の is-a 関係や n2 がマーライオン公園の情報を調べるという情報要求であることを推定しない． p1 と p3 が何らかの情報要求の元で同位関係にあるということだけを推定する．

エッジ集合である．ページと情報要求の間には visited-for 関係，

3. 5 同位ページを推定するための検索・閲覧行動

answer-for 関係が存在する．ページ p と情報要求 n が visited-for

以下に述べる 3 つの検索・閲覧行動を用いて同位ページを関係にあるとは，ページ p が情報要求 n を満たすために閲覧さ推定する．これらの検索行動によって閲覧されたページは同位れたということを意味する．ページ p と情報要求 n が answer-for

ページである可能性が高いと考えた．図 3 は上記の 3 つの検関係にあるとは，ページ p と情報要求 n を満たすことができる

索・閲覧行動による同位ページの推定方法を表している．図にということを意味する．

おいて p1 を再訪問した際に p2 もしくは p3 を推薦することが情報要求と情報要求の間には is-a 関係が存在する．情報要求

ni に対して情報要求 n j が is-a 関係にあるということは，ni が n j

再訪問に有用であると考えた．

a ) クエリ類似度のサブクラスであることを意味する．従って，(ni , p) ∈ Evisited-for

情報要求は検索クエリという形で表現されるので，類似するかつ (ni , n j ) ∈ Eis-a のとき，(n j , p) ∈ Evisited-for となる．これはクエリは同じ情報要求を達成するために発行されることが多い

visited-for 関係を answer-for 関係に置き換えても成立する．

と考えられる．類似するクエリを用いて閲覧されたページは同

例えば，マーライオンパークの情報を知るという情報要求 n2

位ページの可能性が高いと考えた．

の元で以前にページ p3 を閲覧し，情報を得たユーザがいるとすb ) リンクによるページ遷移る．このとき，n2 と p3 は answer-for の関係にある．このユーあるページの複数のリンクをクリックしてページを訪問する

ザが 1 週間後にマーライオンパークの情報を確認しようとペーことがある．このとき同じ情報要求を達成するために複数のジ p1 を閲覧したとする．このとき，n2 と p1 は visited-for 関

ページが開かれることもある．これらのページは同位ページの係にある．ページ p1 が目的のページではなかったとする．こ

可能性が高いと考えた．

のとき，ユーザは n2 を満たすことのできるページを探していc ) 閲覧時刻近接性

る．n2 と answer-for 関係にあるページ p3 を推薦すればよい．

2 つのページを連続的に閲覧したとする．このとき，2 つ目にanswer-for 関係を汎化したものが visited-for 関係なので， p1 と閲覧したページは 1 つ目のページの記憶が頭のなかに残っていp3 はどちらも情報要求 n2 と visited-for 関係にある．

る状態で閲覧される．このとき，何らかの情報要求を満たすた

したページの内容を比べることがある．このように，近い時間

す．N = {n1 , n2 , · · · , nl } とすると E は E ⊂ {(n, p)|n ∈ N, p ∈ P′ }=と表される無向エッジ集合である．目的ノード n とページノーに閲覧されたページは同位ページである可能性があると考えた．

ド p の間のエッジは， p と n が visited-for 関係にあるというこめに頭の中に残っている 1 つ目のページの内容と 2 つ目に閲覧

4. 同位ページの推定とを示す．もし，ある 2 ページが同じ目的ノードにエッジを貼っていたら，それらのページは同位関係にあると推定される．

現在閲覧中のページの同位ページを以下の流れで推定する．

この need-page グラフを用いて推定すべきことは現在閲覧中（1） ページ訪問集合をセッションに分割する（2） 現在のセッのページの同位ページがどのページであるかである．同位ペーションに関連するセッションを選ぶ．（3） 選んだセッション

ジの推定のためにページ内容とユーザの閲覧・検索行動に関すの中から現在閲覧中のページの同位ページを推定する．

る以下の 3 つの仮定を立てた．(1) 2 ページ間の同位関係が複セッション Sk ⊂ V はページ訪問集合の部分集合である．ペー数の観点から推定されているなら，これらのページはより同位

ジ訪問集合を分割することでセッション集合 S = {S1 , · · · , Sl }らしいと推定される．(2) 同位ページの同位ページは同位ペーが生成される．このとき， S1 ∪ S2 ∪ · · · ∪ Sl = V であり，任意ジである可能性がある．(3) 類似するページは同位ページであの Si , S j ∈ S において Si ∩ S j = ∅ である．

る可能性が高い．作成された 2 部グラフに対して Generalized

現 在 閲 覧 中 の ペ ー ジ を pbro ，以 前 に 閲 覧 し た ペ ー ジ を

Co-HITS アルゴリズム [4] を適用することでこれらの仮定を反pk ∈ P とすると現在閲覧中のページの同位ページらしさ

映できる．グラフの作成に閲覧・検索行動から推定される同位Coordinate(pbro , pk ) ⊂ [0, 1] のスコアによって今までに閲覧し関係，アルゴリズムの初期値としてページ内容から推定されるたページ pk をランキングすることが目標である．

同位関係を反映させることで，上記の仮定を満たした推定を行

4. 1 セッション分割
閲覧ページをセッション毎に分割する利点は (1) 計算時間のうことが可能である．

4. 4 検索・閲覧行動に基づくグラフ構築

短縮 (2) 精度の向上である．本手法ではユーザがページを閲覧

クエリ類似度，リンクによるページ遷移，閲覧時刻近接性そするたびに推薦するページが変化する．従って計算時間は出来

れぞれ用いて 3 つの need-page グラフを構築する．目的ノード

る限り短縮したほうが良い．セッション分割をすることによっ集合とエッジ集合について，各グラフについて述べる．ページて計算の対象が少なくなるので，計算時間が減少する．現在のノードは全てのグラフで現在のセッションに関連するセッショ

セッションに関連しないセッションを取り除くことで，推薦しンに属する，以前に閲覧したページ集合 P′ となっている．

て欲しいページの候補となるページの数が減少する．これは結4. 4. 1 クエリ類似度に関するグラフ

果的に精度の向上につながると考えられる．

2 組の検索クエリが類似しているとする．それらのクエリか

しかし，セッション分割・推定には推薦してほしいページをらリンクによる遷移を行って閲覧したページは同位ページらしとりこぼすという欠点がある．推薦して欲しいページを含む

いという仮定に基いてグラフを構築する．Q を現在のセッショセッションを推定できなければ，そのページを推薦できない．

ンに関連するセッションで発行されたクエリの集合とする．そ関連するセッションを選ぶ際には厳しすぎる閾値を設定するこれぞれのクエリ q ∈ Q に対して ansk (q) を上位 k 件の検索結とは好ましくないと考えられる．本研究では 30 分以上ユーザ

果ページのリスト [p1 , p2 , · · · , pk ] とする．クエリ q に対するの操作がない場合にセッション分割を行った．

特徴ベクトル f (q) は s(p1 ) · s(p2 ) · · · · · s(pk ) から生成される

4. 2 関連するセッションの取得

tf ベクトルである． s(p) はページのスニペットを指す．グラフ

現在のセッション Scur に関連するセッションを取得するた

G = (N ∪ P′ , E) は以下のように定義される．

め に ，セッション 毎 に 特 徴 ベ ク ト ル f (Sk ) を 作 成 す る ．特徴ベクトルはセッションに属するページの単語頻出度の和∑によって表現する． f (Sk ) = p i ∈S k tf(pi ) であり，tf(pi ) は
ペ ー ジ pi の 単 語 頻 出 度 ベ ク ト ル で あ る ．こ の と き ，現 在のセッションに関連するセッションに属するページ集合 P′
は セッション 間 の 類 似 度 に よって 次 の よ う に 求 め ら れ る ．

P′ = {p|p ∈ Sk , Sk ∈ S, Sk , Scur , sim( f (Scur ), f (Sk )) >= θ session }sim( f 1 , f 2 ) は 2 つの特徴ベクトル f 1 ， f 2 のコサイン類似度を表す．このようなページ集合 P′ の中から現在閲覧中のページの同位ページを推定する．

N = {n = (qi , q j )|qi ∈ Q, q j ∈ Q,i < j, sim( f (qi ), f (q j )) >= θ query }E = {(n, p)|qi ∈ Q, q j ∈ Q,i < j, n = (qi , q j ), p ∈ ans∗ (qi ) ∪ ans∗ (q j )}ans(q) に対して ans∗ (q) = ans(q) ∪ {p′ |p′ は ans(q) からリンク
遷移によって訪問したページ } とする. 後述する実験では k = 10とした．θ query ∈ [0, 1] は二つのクエリが類似しているかどうかを判断する閾値である．

4. 4. 2 リンクによるページ遷移に関するグラフ
リンクに関するグラフでは同じページからリンクによる遷移を行って閲覧したページは全て同位ページらしいと仮定して，4. 3 同位ページの推定グラフを構築する．従って，目的ノードはリンク元のページ数同位ページを発見するために 2 部グラフである need-page グ

だけ作成される．同じページからリンクされたページに対して，

ラフ G = (N ∪ P′ , E) を定義する． N は目的ノード集合であり，P′ は以前に閲覧したページの集合の内，現在のセッションと関連するセッションとして取得されたセッションに属するページの集合である (N ∩ P′ = ∅)．直感的には目的ノードは情報要求を表

同じ目的ノードとのエッジを張る．グラフ G = (N ∪ P′ , E) は
以下のように表される．

N = {p ∈ P′ |∃pi , p −−−−→ pi , pi ∈ P′ },l ink

E = {(n, p)|n ∈ N, p ∈ P′ , n −−−−→ p},l ink

る．sim′ (p, p′ ) = (1 − a) · sim( f (p), f (p′ )) + a · sim( f (t(p)), f (t(p′ ))) ．

a ∈ [0, 1] はページ内容とタイトルのどちらを重視するか決めるパラメータで，大きいほどタイトルを重視する．x i と yi の初期値は

pi −−−−→ p j はページ pi から p j へのリンクによるページ遷移が以下のように計算する．x 0i = ∑あったことを表す.

|N | は目的ノードの総数を指す．

l inksim’(page(v n ), p i )p k ∈ P ′ sim’(page(v n ), p k ), yi0 = | N1 | ,4. 4. 3 閲覧時刻近接性に関するグラフ

4. 5. 2 エッジの重み

閲覧時刻近接性に関するグラフでは，あるページの内容にエッジの重みは以下のように計算する．クエリの類似度に関する記憶が残っている内に閲覧されたページにエッジを張関しては，全てのエッジの重みを均等に扱う．エッジを張る際

る．Memory(p,t) をページ p ∈ P の時刻 t における記憶量，にすでに閾値を用いて枝刈りをしているので，全てのエッジ

Browsing(t) を時刻 t において閲覧中のページ，isBrowsing(p,t)の重みが等しいと考えた．したがって次のように計算される．

を Browsing(t) = p ならば 1，そうでないならば 0 を返す関数

w j i = count1ef (n j ) , wi j = count1ef (p i ) ．countef (pi ) は pi に張られているエッジの本数を指す．

とする．グラフ G = (N ∪ P′ , E) は以下のように表される．

pn

np

リンクに関するグラフではリンクの回数によって以下のように

N = {p|p ∈ P′ }E = {(n, p)|n ∈ N, p ∈ P′ , Memory(n,t) · isBrowsing(p,t) >= 0}

エッジの重みを設定する．ページ A からページ B にリンクを 5 回，
ページ C にリンクを 1 回，ページ D にリンクを 4 回行ったとする．

Memory(p,t) は isBrowsing(p,t) が 1 の 時 に 値 が 増 え ，

この時，ページ B に対してページ D のほうがページ C よりも同位

isBrowsing(p,t) が 0 の時に値が減る関数である．人の記憶にはページらしいと考えられる．このような理由から次のようにエッcount(p j −−−−→ p i )nppn
l i nkジの重みを設定する．w j i = ∑′ count(p −−−−→ p ) , wi j =限界があるのでこの関数の値には上限値がある．

4. 5 Generalized Co-HITS アルゴリズムの適応
上記で構築した各グラフ G = (N ∪ P′ , E) に，Generalized

Co-HITS アルゴリズムを適用する．Generalized Co-HITS アル
ゴリズムは，ページノード pi ∈ P′ の値 x i ∈ [0, 1] と目的ノー∑

count(p j −−−−→ p i )pk ∈ Pjl i nkk→ p j ) は，ページ pi から−−−−→ p i ) ．count(pi −−−−l ink

l i nkp k ∈ N count(p kl i nkページ p j へのリンクによる遷移があった回数を指す．
閲覧時刻近接性に関するグラフでは，あるページの内容のド ni ∈ N の値 yi ∈ [0, 1] をエッジにそって伝播していくアルゴ

記憶量の多さとページの閲覧時間を考慮してエッジの重みをリズムである． x i の値が高いほど pi が現在閲覧中のページの設定する．例えばページ A を 30 秒閲覧して，次に別のタブに同位ページらしいと言える．具体的には以下の計算式によって∑
np
x i と yi の値を更新する． x i = (1 − λ p )x 0i + λ p n j ∈ N w j i y j ，∑pn
y j = (1 − λ n )y 0j + λ n p i ∈P ′ wi j x i ．x 0i は pi の初期値，y 0j は
∑ 0 ∑ 0np
pn
n j の初期値であり， x i = y j = 1 である．w j i および wi j

開いていたページ B をタブを切り替えることによって表示しnp

た．しかし，ページ B が想定していたページと異なっていた．
そこで 3 秒閲覧しただけで別のタブに開いていたページ C を
タブを切り替えることによって表示し，30 秒閲覧した．ペーはエッジの重みであり，w j i は n j から pi へのエッジの重みで
∑
∑
pn
np
ある．また， p i ∈P ′ w j i = n j ∈ N wi j = 1 である．λ p ∈ [0, 1]

ジ B は少しの間しか閲覧されていないので，ページ A の内容

および λ n ∈ [0, 1] は初期値の x 0i ， y 0j をどの程度重視するかを

ジ C はどちらも 30 秒間閲覧されており，ページ A の内容を表すパラメータであり，値が小さいほど， x 0i ， y 0j を重要であ頭の中に置きながらページ C を閲覧したと考えることができるとみなす．上記のアルゴリズムは共通の目的ノードに対してる．このようなことを考慮してエッジの重みを以下の様に設定∫

エッジが張られたページノードの値が近いものになる．

する．w j i = ∑4. 5. 1 初 期 値
ページノードの初期値はそのページが現在閲覧中のページと同じ情報要求の元で開かれたかを表す．ページが現在閲覧中のと比較しながら閲覧されたとは考えにくい．ページ A とペー

np∫ t now∑0nk ∈ Nt now
Memory(n j , t )·isBrowsing(p i , t )dt
0 ∫
t now
Memory(n j , t )·isBrowsing(p k , t )dt
pk ∈ P′ 0pn, wi j =Memory(n j , t )·isBrowsing(p i , t )dt∫ t now．ここで，t now は現在
Memory(n k , t )·isBrowsing(p i , t )dt0

時刻を指す．

ページと類似していればしているほど同じ情報要求の元で開か

4. 6 グラフの結合れたと考えた．ページの類似度を計算する際にはページの中身

それぞれのグラフを結合することでそれぞれの閲覧・検索行

だけでなく，タイトルも使用した．これは，Web ページの中に動を考慮したグラフを生成することができる．グラフを結合す

は Google Maps などの，主に Javascript で構成されたページがる際には概念ノードの数がグラフによって異なるので初期値とあり，ページの内容（HTML）がそのページの内容を正しく表

エッジの重みの与え方に工夫が必要である．G = (N Q ∪ P′ , E Q )していない場合があるからである．ページ p に対する特徴ベクをクエリ類似度に関するグラフ，G = (N L ∪ P′ , E L ) をリンク

トル f (p) はページのテキストによって生成される tf ベクトルによるページ遷移に関するグラフ G = (N F ∪ P′ , E F ) を閲覧

である．t(p) をページ p のタイトルとするとページタイトル t

時刻近接性に関するグラフとする．このとき，3 つの閲覧・検に対する特徴ベクトル f (t) をタイトルの N-Gram ベクトルとし索行動を考慮したグラフ G = (N ∪ P′ , E) をを作成する．なお，

た．タイトルはページ本文に比べて短く，ページと同様に形態

目的ノード集合は N = {n|n ∈ (N Q ∪ N L ∪ N F )} であり，エッ

素解析を行ってベクトルを作ると次元数がとても小さくなるのジ集合は E = {(n, p)|(n, p) ∈ (E Q ∪ E L ∪ E F )}である．ページ

で N-Gram を用いた．実験では N = 2 とした．

ノードの初期値はそれぞれのグラフのページノードの初期値

ページ p と p′ 間の類似度 sim′ (p, p′ ) は下記の様に計算されと同じである．目的ノード ni の値 x i は x i = 1/3|N Q | if ni ∈N Q , 1/3|N L | if ni ∈ N L , 1/3|N F | if ni ∈ N F と表される．目的

表 1: アンケート内容（メモ再現タスクの各トピック終了時）
メモ再現タスクでページを推薦して欲しかった場面を思い浮かべノードからページノードへのエッジの重みはそれぞれのグラフて下さい．そのときの状況について以下の質問に答えてください．

の重みと同じである．ページノードから目的ノードへのエッジ
pn・ どのページを閲覧していましたか．

の重みは wi j = ∑・ どのページを推薦して欲しかったですか．

w′i j

pn

′ pn
nk ∈ N w i kとなる．ここで w ′ i j はグラフ結pn

合前のエッジの重みを表す．
グラフの結合後，Generalized Co-HITS アルゴリズムを適用

・ 推薦して欲しいページのアクセス方法を覚えていますか．
・ 推薦して欲しいページを閲覧したことを覚えていますか．

することで，ページノード pi ∈ P′ の値としてに入力ページ

アンケートはメモ再現時に閲覧しているページに対して，どに対する同位ページらしさの値 x i が求まるこれにより，全のページ推薦して欲しいかという情報を得るために行った．まての以前に閲覧したページ pk ∈ P と現在閲覧中のページとた，推薦して欲しいページに関する記憶についても質問した．

の同位ページらしさのスコア Coordinate(pbro , pk ) が決まる．

アンケート内容は表 1 に示す．また，推薦して欲しいページにCoordinate(pbro , pk ) は pk ∈ P′ のとき x k であり，pk < P′ のと関する記憶については，1. 章で述べたように，アクセス方法にき 0 となる．このスコアを用いて閲覧ページをランキングし，関する記憶と閲覧したことに関する記憶について再認不可，再推薦するページを決定する．

認可，再生可のどれにあたるか聞いた．

5. 実

験

5. 2 評価

5. 2. 1 評 価 手 法

提案手法が有効であるかを検証するためにユーザ実験を行っ

実験では閲覧・検索ログよりユーザ毎に 3. 1 で示した問題のた．目的はいつ，どのページを推薦して欲しいかというデータ入力にあたる，ユーザの閲覧・検索行動が得られる．また，アを取得することである．実験を行うために詳細な閲覧履歴や検ンケートにより，次の組の集合 Dcor = {(v1bro , p1rec ), · · · } が得ら

索・閲覧行動を記録する Firefox の拡張機能を実装した．

れる．
（ 1 ）vibro ∈ V : ページ pirec を推薦して欲しい際に閲覧して

5. 1 実 験 内 容

いたページ.（ 2 ）pirec ∈ P: 推薦して欲しいページ．この集合に実験は 25 名の参加者を雇い実施した．被験者は，18〜25 歳

おいて，あるページを閲覧しているときに推薦して欲しいペーの京都大学に所属している学生であり，日本語を母国語として

ジの数が 2 つ以上になる場合がある．このとき，推薦してほしいる．被験者が普段から使用しているパソコンに Firefox の拡いページ全てを推薦することを考えている．評価を行うために張機能をインストールした．拡張機能は被験者の閲覧行動を記

Dcor から少し変更した集合 D ′ cor = {(v1bro , P1rec ), · · · } を下記の録するものである．実験は網羅的な情報を Web を閲覧・検索に用に定義する．

よって収集してメモを作成してもらい，その 1，2，4 週間後にそのメモを再現するためにもう一度 Web を閲覧・検索してもら

vibro ∈ V bro ,Pirec = {pkrec |(vibro , pkrec ) ∈ Dcor }うというものである．スケジュールは以下の通りである．

ここで，V bro = {vi |(vi , pi ) ∈ D ′ cor } は推薦して欲しい際に閲覧メモ再現の 4 週間以上前 ：拡張機能のインストール

していたページのページ訪問集合である．上記の組を正解デー

被験者が普段から使用しているパソコンに Firefox の拡張

タとみなした．どのページを推薦するか決定するためにランキ機能をインストールする．この瞬間より，被験者の閲覧・ングを計算する際には，ページ訪問 vb を現在閲覧中のページ

検索履歴の取得が開始する．

とみなして計算を行った（max(I) = i(vb ) ）．閲覧ページのラン

メモ再現の 4，2，1 週間前 ：メモ作成タスク

キングは提案手法と後述するベースライン手法を用いて行う．

それぞれ，4 個のトピックに関して Firefox を用いて情報をページ pkrec ∈ Prec を正解ページとみなして，このランキングの集める．各トピック 30 分間の検索・閲覧を行う．各トピッ

平均適合率（AP）を求めた．これを正解各組毎に求めその平均

クで検索・閲覧した内容に関する紙のメモを作成する．

値を評価値とした．これは一般に MAP(Mean Average Precision)

メモ再現日 ：メモ再現タスク
メモ作成タスクで情報を集めたトピックの内 4 トピックにと言われる評価値である．MAP を用いる理由は，推薦して欲しいページ全てを発見することを目的としているからである．

関するメモを各トピック 20 分間で再現する．各トピックに

5. 2. 2 提案手法の適応

関するメモの再現が終了するごとに，アンケートに答える．

セッション分割と推定に関して，次の 3 つ状況で提案手法をトピックは合計 12 個用意し，うち 4 個は再訪問タスクを行わな適応した．
（ 1 ）セッション分割と推定を行わない（ 2 ）セッショいダミートピックである．再訪問タスクを行うトピックは（1）ン分割と推定を行う（ 3 ）セッション分割と推定が完全に成功しTravel （2） Food （3） Health （4） Purposeless の 4 つのカテた．以上の各状況において，メモ作成タスクで閲覧したページ

ゴリに分類され，各カテゴリに 2 トピック含まれる．メモを再に対して 4. 4 節で示したようにグラフを構築する．グラフはそ

現するトピックはタスク 1〜3 のいずれか 2 つのタスクから，それぞれの単一の検索・閲覧行動に基づくグラフと全てを結合しれぞれ 2 トピックずつ選んだ．トピック行う順番に関しては，たグラフの計 4 つを作成した．構築したそれぞれのグラフに順序効果が出ないように考慮した．トピックは複数の情報を探

generalized Co-HITS アルゴリズムを適用し，各ページに与えらすものを行ってもらった．

れた値順にランキングを行った．

DEC + DTM

0.25
0.2

MAP

DEC + DTM

0.1

00
ALL (#=204)

Similarity

Failed(#=62)

Query simirality

Time-consuming(#=64)

Link navigation

Unconscious(#=73)

Focus time adjacency

MAP

DEC + DTM

0.1

0.2

0.3

0.4

Completely-forgot(#=19)

Query + Link + Focus

Error bar: SEM!

0.5
λp!

0.6

0.7

0.8

0.9

Query simirality(a=0)

Link navigation(a=0)

Nearness of focus time (a=0.1)

Query + Link + Focus (a=0.1)1

図 5: λ p を変化させた時の MAP の値a ) 全体の評価
セッション分割と推定ありの図における一番左の 6 つの MAPについて見る．これは，正解データセットの分割を行わずに，全ALL (#=204)

Similarity

Failed(#=62)

Query simirality

Time-consuming(#=64)

Link navigation

Unconscious(#=73)

Focus time adjacency

Completely-forgot(#=19)

Query + Link + Focusての正解データセットに対して，提案手法を全て適応した際のMAP を表している．閾値に関するパラメータは θ session = 0.3，(b) セッション分割と推定あり
0.55
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

0.15

0.05

(a) セッション分割と推定なし
0.55
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

0.3

Error bar: SEM!

MAP

MAP

0.55
0.5
0.45
0.4
0.35
0.3
0.25
0.2
0.15
0.1
0.05
0

Error bar: SEM!

θ query = 0.6 を用いた．ベースライン手法の MAP と比べて，リンクに関するグラフと閲覧時刻近接性に関するグラフ，全てをマージしたグラフの MAP の方が高い値をとった．しかし，クエリ類似度に関するグラフではベースライン手法を下回った．
ユーザは 1ヶ月の間に平均 1000 ページを閲覧しており，240 もALL (#=204)

Similarity

Failed(#=62)

Query simirality

Time-consuming(#=64)

Link navigation

Unconscious(#=73)

Focus time adjacency

Completely-forgot(#=19)

Query + Link + Focusのクエリを発行している．この状況で，クエリ類似度に関する(c) セッション分割と推定が完璧にできた場合グラフを作成すると莫大な数の目的ノードが作成される．巨大図 4: 推薦して欲しいページのタイプ別の MAP．各ブロックですぎるグラフが作成されてしまい，HITS が上手に作用しなかっ

左の 2 つがベースライン手法によるもの．

たため，このような結果になったと考えられる．

5. 2. 3 ベースライン手法
Kawase ら [10] の手法とページ類似度による手法を用いた．
Kawase らはランキング手法と伝播手法を組合せた手法を提案した．ランキング手法は（1） LRU：どれだけ最近閲覧したか（2） MFU：どれだけ頻繁に閲覧しているか（3） DEC：LRUと MFU の組み合わせの 3 つからなる，ページにスコアを付ける手法である．ランキング手法によって計算された値は伝播手法で遷移行列（TM）を使用することによって伝播される．遷
移行列は直感的にあるページを閲覧した後にどのページを閲覧しているかを表す．これによってランキング手法によって高い値になったページの後に閲覧されたページのスコアが高くなる．

Kawase らは遷移行列をセッション内でのページの閲覧順序を考慮して作成した．これらの手法を試したところ DEC+DTM
を用いた手法がもっとも良い結果になった．DTM とは同じセッション内でページ x の後にページ y が閲覧された場合 x から yへの値持ち， x と y の訪問順序が離れているほどその値が低くなる遷移行列を作成する手法である．
ページ類似度ベースの手法は現在閲覧中のページとの類似度
順に閲覧ページをランキングするものである．これは 4. 5. 1 節で述べた提案手法のアルゴリズムにおける初期値と等価である．

5. 2. 4 評 価 結 果
セッション分割と指定なし，セッション分割と推定あり，セッション分割と推定が正確にできたと仮定した場合の 3 種類の

MAP に関するグラフを図 4 に示す．それぞれのグラフは推薦して欲しいページを記憶に関する分類にしたがって分類し，それぞれの分類毎に MAP を計算したものを表している．

上述の条件に対してパラメータ λ p を 0 から 1 まで変化させた際の MAP を図 5 に示す．図 5 においてクエリの類似度を用いたグラフ以外は上に凸なグラフになっている．これは，クエリの類似度を用いたグラフ以外は初期値と伝播手法の両方が重要であるということを意味する．

b ) セッション分割に関する評価
図 4 における 3 つのグラフを比べると，セッションが正確にできればできるほど精度が上がっていることが分かる．つまり，セッション分割を行い，現在のセッションと関連するセッショ
ンを選ぶことが計算時間の短縮だけでなく，精度の向上にも大きく寄与していることが分かる．現在のセッション分割手法はとてもナイーブなものであるので，再考の価値はあると考えられる．セッション分割が完全にできた場合，クエリ類似度に関するグラフの手法でもベースラインを上回っている．これは，セッションが完全に分割されていると，作成される目的ノードの数が爆発的に増えないからであると考えられる．

c ) ページの記憶に関する評価
推薦して欲しいページの分類別に MAP を見ると，Failed ケース，succeeded ケースでは提案手法がベースライン手法を上回っている．しかし，Unconscious ケースや Forgot ケースではベー
スライン手法と変化があまり見られない．Unconscious ケース
や Forgot ケースのページはメモ再現の際にその存在を再生できていないページである．存在を再生できていないページを探そうとすることはないので，そのようなページと類似するようなページにすらたどり着いていない場合も多く存在すると考えられる．存在を再生出来ていな場合，そのページが満たす情報要精度の向上に有用であることが分かった．

MAP

0.35

Error bar: SEM!

0.3

謝辞 本研究の一部は，文部科学省科学研究費補助金（課題0.25

番号 15H01718，24680008）によるものです．ここに記して謝0.2

意を表します．

0.15

文

0.1
0.05
0
1 week (#=66)

2 weeks (#=60)

4 weeks (#=78)

DEC + DTM

Simirality

Query simirality

Link navigation

Focus time adjacency

Query + Link + Focus

図 6: 再訪問期間別の MAP
求も発生しなかったことも多いと考えられる．この場合，現在閲覧中のページの同位ページの中に正解ページが無い場合も多く考えられる．これらのケースの問題解決のためには，情報要求の階層構造や似て異なる度について考える必要がある．

d ) 再訪問間隔に関する評価
再訪問の期間別に計算した MAP を図 6 に示す．期間による

MAP の目立った違いはないように見受けられる．また，再訪問の期間が 1，2，4 週間のとき，メモ作成タスクで閲覧した 38%，

39%，30%のページがメモ再現タスクで再訪問されていた．もし以前に閲覧したページを再訪問できていなくとも，提案手法が目的のページを推定できていることが分かる．

5. 3 考察

上述の実験では，提案手法の有用性が概ね示された．本研究には他に以下の問題が残されている．（1） ページ内容が一定
時間毎に変わってしまう Web ページが存在する．このようなページを推薦しても，ユーザにとっては有用でない場合が多い．
（2） 本研究ではページを推薦するタイミングについて議論していない．一つの方法として，ユーザが表示ページを切り替える
度に推薦を行うということが考えられる．つねにページ推薦が行われるのは煩わしいというユーザもいる．また，推薦するタイミングによって推薦して欲しいページの種類は異なる．適切なタイミングで適切なページを推薦する必要がある．（3） 推薦するページの対象は以前に閲覧したページに限る必要はない．
以前に閲覧していないページを推薦するために，他のユーザの閲覧行動における同位関係を使用するということが考えられる．

6. お わ り に
本論文では，再訪問に有用なページが現在閲覧中のページの同位ページであるを推薦する手法を提案した．我々は，再訪問に失敗しているユーザに注目した．現在閲覧中のページの同位ページを発見するために，まず閲覧ページをセッションに分割した．次に現在のセッションに関連するセッションを選び，選んだセッションに含まれるページの中から現在閲覧中のページの同位ページを推定した．同位ページの推定には，クエリ類似度，リンクによるページ遷移，閲覧時刻近接性という 3 つの閲
覧・検索行動を使用した．実験の結果，提案手法がある程度有用であることがわかった．リンクによるページ遷移と閲覧時刻
近接性を用いた手法はベースライン手法を上回った．クエリ類
似度を用いた手法はセッション分割が完全になされたと仮定した場合には有効に働いた．セッション分割は計算時間の短縮と

献[1] E. Adar, J. Teevan, and S. T. Dumais. Large scale analysis of web
revisitation patterns. In CHI2008, pages 1197–1206, 2008.
[2] A. Aula, R. M. Khan, Z. Guan, P. Fontes, and P. Hong. A comparisonof visual and textual page previews in judging the helpfulness of web
pages. In WWW2010, pages 51–60, 2010.
[3] R. G. Capra III. An investigation of finding and refinding information on the web. PhD thesis, Virginia Polytechnic Institute and State
University, 2006.
[4] H. Deng, M. R. Lyu, and I. King. A generalized co-hits algorithm
and its application to bipartite graphs. In KDD2009, pages 239–248,
2009.
[5] T. Deng, L. Zhao, and L. Feng. Enhancing web revisitation by contextual keywords. In ICWE2013, pages 323–337, 2013.
[6] M. Eirinaki, M. Vazirgiannis, and D. Kapogiannis. Web path recommendations based on page ranking and markov models. In
WIDM2005, pages 2–9, 2005.
[7] https://developer.mdozilla.org/en-US/docs/Mozilla/Tech/Placesd/
Frecency_algorithm.
[8] R. Jones and K. L. Klinkner. Beyond the session timeout: automatic hierarchical segmentation of search topics in query logs. In
CIKM2008, pages 699–708, 2008.
[9] R. Kawase, G. Papadakis, E. Herder, and W. Nejdl. The impact ofbookmarks and annotations on refinding information. In HT2010,
pages 29–34, 2010.
[10] R. Kawase, G. Papadakis, E. Herder, and W. Nejdl. Beyond the usual
suspects: context-aware revisitation support. In HT2011, pages 27–
36, 2011.
[11] I. Li, J. Nichols, T. Lau, C. Drews, and A. Cypher. Here’s what i did:sharing and reusing web activity with actionshot. In CHI2010, pages
723–732, 2010.
[12] B. MacKay, M. Kellar, and C. Watters. An evaluation of landmarks
for re-finding information on the web. In CHI’05 extended abstracts,
pages 1609–1612, 2005.
[13] M. Mayer. Web history tools and revisitation support: A survey of existing approaches and directions. Foundations and Trends in HumanComputer Interaction, 2(3):173–278, 2009.
[14] D. Morris, M. Ringel Morris, and G. Venolia. Searchbar: a searchcentric web history for task resumption and information re-finding.
In CHI2008, pages 1207–1216, 2008.
[15] I. Nishimoto and M. Toda. Process-recollective refinding on the web.
In WI2006, pages 883–892, 2006.
[16] H. Obendorf, H. Weinreich, E. Herder, and M. Mayer. Web page revisitation revisited: implications of a long-term click-stream study ofbrowser usage. In CHI2007, pages 597–606, 2007.
[17] H.-T. Pu and X.-Y. Jiang. A comparison of how users search on web
finding and re-finding tasks. In 2011 iConference, pages 446–451,
2011.
[18] J. Teevan. The re: search engine: simultaneous support for finding
and re-finding. In UIST2007, pages 23–32, 2007.
[19] J. Teevan, E. Adar, R. Jones, and M. A. Potts. Information reretrieval: repeat queries in yahoo’s logs. In SIGIR2007, pages 151–
158, 2007.
[20] J. Teevan, E. Cutrell, D. Fisher, S. M. Drucker, G. Ramos, P. André,
and C. Hu. Visual snippets: summarizing web pages for search andrevisitation. In CHI, pages 2023–2032, 2009.
[21] E. Tulving and F. I. Craik. The Oxford handbook of memory, pages
8–9. Oxford University Press, 2000.
[22] S. K. Tyler and J. Teevan. Large scale query log analysis of refinding. In WSDM2010, pages 191–200, 2010.
[23] S. K. Tyler, J. Wang, and Y. Zhang. Utilizing re-finding for personalized information retrieval. In CIKM2010, pages 1469–1472, 2010.