論文 / 著書情報
Article / Book Information
論題(和文)

大規模商用サイトログを用いたWebページ推薦手法 WRAPL の評価と考察

Title(English)

Applying Web Pagfe Recommendation Methods to Access Logs of aCommercial Site

著者(和文)

山元理絵, 吉原朋宏, 小林大, 小林隆志, 横田治夫

Authors(English)

Rie YAMAMOTO, Tomohiro YOSHIHARA, Dai KOBAYASHI, Takashi
KOBAYASHI, Haruo YOKOTA

掲載誌(和文)DEWS2007論文集

Citation(English)

Proceedings of DEWS2007

Vol, no, pages

Vol. , No. , pp. L4-1

発行日 / Pub. date2007, 3

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2007 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2007 L4-1

大規模商用サイトログを用いた
Web ページ推薦手法 WRAPL の評価と考察
山元

理絵†

吉原

朋宏†

小林

大†,††

小林

隆志†††

横田

治夫†††,†† 東京工業大学大学院情報理工学研究科計算工学専攻 〒 152–8552 東京都目黒区大岡山 2–12–1†† 日本学術振興会特別研究員 DC††† 東京工業大学学術国際情報センター 〒 152–8550 東京都目黒区大岡山 2–12–1
E-mail: †{yamamoto,yoshihara,††daik}@de.cs.titech.ac.jp, †††tkobaya@gsic.titech.ac.jp, †††,†yokota@cs.titech.ac.jp
あらまし

近年，ビジネスの場としての Web の役割と情報量の増大から，Web パーソナライゼーション が注目され，中でもユーザの嗜好に合った Web ページをシステムがユーザに推薦し提示する Web ページ推薦の要求が高まってきている．Web アクセスログを Web ページ推薦に用いる方法は，クライアント側に手を加える必要がなく，またユーザの匿名性を保持したまま利用できるため有用である．我々はこれまでに， Web アクセスログから LCS（Longest Common

Subsequences）を抽出して Web ページ推薦に利用する手法である WRAPL を提案してきた. 本稿では， 実際の大規模商用サイトのアクセスログを用いて， WRAPL の有効性を評価し考察する．
キーワード

Web，アクセスログ解析，Longest Common Subsequences，Web パーソナライゼーション，Web ページ

推薦

Applying Web Pagfe Recommendation Methods
to Access Logs of a Commercial Site
Rie YAMAMOTO† , Tomohiro YOSHIHARA† , Dai KOBAYASHI†,†† , Takashi KOBAYASHI††† , andHaruo YOKOTA†††,†† Department of Computer Science, Graduate School of Information Science and Engineering,Tokyo Institute of Technology 2–12–1 Ookayama, Meguro-ku, Tokyo 152–8552, Japan†† Research Fellow (DC), Japan Society for the Promotion of Science††† Global Scientiﬁc Information and Computing Center, Tokyo Institute of Technology
2–12–1 Ookayama, Meguro-ku, Tokyo 152–8550, Japan

E-mail: †{yamamoto,yoshihara,††daik}@de.cs.titech.ac.jp, †††tkobaya@gsic.titech.ac.jp, †††,†yokota@cs.titech.ac.jp
Abstract Sophisticated websites satisfying users’ requirements becomes much more important to propagate information via
websites, nowadays. Web page recommendation methods using web access logs are useful for them because they need no
modiﬁcation in client-side applications to meet the requirements. We have proposed WRAPL as a method of extracting LCSs
(Longest Common Subsequences) from web access logs and using them to recommend web pages for an active session. In
this paper, we analyze the eﬀects of WRAPL using actual web access logs of a large-scale commercial site.
Key words Web, Access Log Analysis, Longest Common Subsequences, Web personalization, Web Page Recommendation

1. は じ め に

Web パーソナライゼーションは一般的に (i) データの収集，(ii) 前処理，(iii) 解析，(iv) 推薦や動的なサイト構造変更等のア

近年，ビジネスの場としての Web の役割と情報量の増大かクションの手順で行われ，(i) のデータの収集では，ユーザから

ら，コンテンツ推薦やサイト構造の動的な変更を行う Web パーの入力による情報や Web アクセスログ等が利用される．後者はソナライゼーション [1] が注目され，特にユーザの嗜好に合っユーザの行動パターンや傾向を抽出することが可能であるため，た Web ページをシステムがユーザに推薦し提示する Web ペー

さまざまな分野，目的で研究が行われている [2]．Web パーソナジ推薦が求められている．

ライゼーションを行う際に最も重要な要因となる (iii) の手順に

おいて，Web 利用マイニングを用いる方法では，基本的にユーシャルパターンの抽出を用いた学習項目推薦システム [3] では，

ザのアクセスログのみで解析を行うことが可能であり，ユーザ

それぞれのパターンから求めた推薦順位を融合して最終的な順

による情報の入力や，ページ・コンテンツの評価を必要としな位を決定し推薦を行う．しかし，その最終的な順位決定の詳細

いといった利点がある．

な方法については言及されていない．また，学生の学習レベル

そこで，本研究では Web 利用マイニングに基づく Web パー

等，アクセスログ以外からの情報も利用している．

ソナライゼーションに焦点を当てる．Web パーソナライゼー

相関ルールを用いた Web ページ（URL）推薦手法 [4], [5] でションのための Web 利用マイニング方法として，[1] では， 相は，アクティブユーザの現在までのアクセスページと共起頻度

関ルール発見，シーケンシャルパターン発見，クラスタリング，の高いページが推薦される．[4] では，パターン中で未出現のクラシフィケーションを挙げている．

ページが読み込まれるとその場でルールを作成するため，新規

しかし，相関ルールやクラスタリングを用いた既存の研のページアクセスに対しても推薦が可能となるが，そのコスト

究 [3]〜[7] では，ページアクセスの順序情報を考慮していないは大きく，またユーザは最初にブックマークの情報を提供する

ため，ページ参照の順序に特徴的な傾向がある場合など，すで必要がある．[5] では，アクティブユーザの現在までのアクセスにアクセスしたページを推薦したり，ユーザにとってもはや不ページに対し，段階的に相関ルールと比較することによって，要となったページを推薦することで，推薦精度を低下させてし共起頻度の高いページを効率的に推薦できることが示されてまう可能性がある．

いるが，推薦に用いるルールは必ず最後のアクセスページを含

我々は，順序情報を考慮しないという上記の問題を解決する
ため，アクセスログ中のシーケンスの LCS（Longest Common

む必要があるため，その頻度が低い場合には適切な推薦が行えない．

Subsequences）を用いることで，アクセスパターンのぶれを吸[6] では，相関ルールとシーケンシャルパターン，さらにそ収した概括的なアクセス順序を利用して推薦精度を向上させるの派生である連続シーケンシャルパターンを用いた Web ペー

手法を提案してきた [8], [9]．

ジ推薦において，精度を比較している．相関ルールを用いた手

LCS を用いることで，アクセスパスが完全に一致しない場

法 [5] におけるマイニングのフェーズを他の 2 つのパターンに合でも全体のアクセス傾向の表現が可能になるとともに，順序置き換えて実験を行った結果として，Web prefetching 等のタス情報を保持することができるため，実際の Web アクセスログ

クには連続シーケンシャルパターンが最適であり，一般的なアを用いた実験において，Mobasher らの相関ルールを用いる手

プリケーションには相関ルールとシーケンシャルパターンを用法 [5], [6] と比較して推薦精度が向上した実験結果が得られているのが適していると結論付けている．

いる．

クラスタリングを用いた Web ページ推薦手法 [7] では，遺伝

しかしながら，我々のこれまでの報告では，NASA の Web サ

的アルゴリズムを用いることにより，少ないパラメタで初期段

イトの 1995 年 8 月という古いアクセスログに対して実験を行っ階のクラスタ作成を行うことができる．しかし，類似度やメンていたため，以下のような問題があった．

バシップ等の計算で複数の方法が挙げられており，そのそれぞ• 動的な Web ページの構築方法の普及により Web サイト
構成の傾向が異なる．

• 検索エンジンの普及によりアクセス傾向が異なる可能性がある．

• 対象ページ群が既に存在しないため実際に推薦される
ページがユーザにとって有用かどうかを評価できない．
そこで本稿では，現存する大規模商用サイトの実際のアクセ
スログに対し， 我々の提案する LCS を利用した Web ページ推薦手法 WRAPL （Web page Recommendation by Access PatternLcs）を適用することで，その有用性と推薦される結果について評価し考察する．また，実際の Web サイトが持つ特徴を調査し，アクセス傾向や推薦されるページの特徴などを把握することで，Web サイトの持つ特徴を考慮した推薦対象を検討する．
以降ではまず，次節で関連研究について述べ，3. 節において，我々の提案手法である WRAPL に関して説明する．4. 節で，大規模商用サイトの実際のアクセスログに対し WRAPL を適用す
る実験で用いるデータの説明と，その結果に対する考察を行った後，5. 節で本稿のまとめと今後の課題に関して述べる．

れにトレードオフ関係があるため，対象とするデータによって適切な方法の選択が難しいと考える．

3. WRAPL: アクセスログから抽出した LCS を利用した Web ページ推薦
本節では，我々がこれまでに提案してきた Web アクセスログ
から抽出した LCS を用いてユーザに Web ページを推薦する手法である WRAPL [8], [9] について説明する．WRAPL では，推薦のための準備として，ある一定期間中のアクセスログを学習のためのデータとして用い，3. 1 節で述べる手順で LCS を抽出する．推薦においては，抽出された LCS を用いて，3. 2 節のようにして推薦ページを決定する．

3. 1 Web アクセスログからの LCS 抽出
3. 1. 1 Web アクセスログと LCS
リスト x の部分列とリスト y の部分列の中で両方のリストに含まれるものを共通部分列という．共通部分列の中で最も長いものを最長共通部分列（Longest Common Subsequences）と呼び，LCS と略記する（注 1）．
これをアクセスログから抽出した， ユーザのアクセスシーケ

2. 関 連 研 究ンス群に適用することで，寄り道等の余分な情報を取り除いた，

教育システムのアクセスログからの，相関ルールやシーケン（注 1）：LCSS と表現される場合もある．

A B C D E

F , A, B, C, D , E

F , A, B, C, D , E

B, G, C, E

B C E
B, G, C, E

U ser sessi onc++lcs 3 B, C, E

lcs 4 D , E

lcs 5 F , B, E

5
3
3

L C S

act 3 A B C

Recommendation
candidatelcs 1

A B C D E

D

lcs 2

A D B C

E

lcs 3

B C E

(c1 = 2)( c 2 = 4)(c3 = 5)p o i n t ( D)
= 3* 2p o i n t (E )= 3* 2 + 2 *5

C, D , F , E, C

lcs1 A, B, C, D , E 2
lcs2 A, D , B, C
4

Act i v e sessi on



A, C

ci




Access log

A, B, C, D , E, Fc++

IP1 “B”
IP2 “A”
IP1 “G”
IP1 “C”
IP3 “A”
IP2 “C”
IP1 “E”

L C S

図 1 Web アクセスログの LCS を利用した Web ページ推薦

共通の傾向を発見することが可能となる．

抽 出 さ れ た LCS の 内 ，全 セッション 中 に お い て 数 え 上

3. 1. 2 ユーザセッションと LCS の抽出

げ ら れ た 回 数 が 閾 値 min.Count 以 上 で あ り，か つ 長 さ がWeb 利用マイニングを行うためには，まず蓄積されている未min.Length 以上である LCS の集合を Large LCS 集合と呼び，加工のアクセスログを精錬して，サイト内におけるユーザ毎のLL = {lcs1 , lcs2 , · · · lcsk } で表す．また，LL 内の i 番目の要素

移動情報である，ユーザセッションを抽出する必要がある．

が全セッション中で数え上げられた回数を ci と表す．ここで，ユーザセッションは， 各セッションでユーザがアクセスした

min.Count と min.Length は，Web サイトの持つ特性に合わせてURL のシーケンスであり， 各セッションに一意なセッション

設定するパラメータである．このとき，長さ n のアクティブ

ID を割り当て，アクセスログから，セッション ID ごとに整理

セッション actn からそれに続くユーザのページアクセスを予測された URL の集合を時系列順に抽出することで作成する．

する．

セッション ID には，Cookie を用いることが一般的ではある

LCS は，2 つのセッションから共通部分を抜き出すことでそが，Cookie を使用できない環境や複数のサーバをまたがる場合

れらに共通する傾向を表す．そのため，lcsi とアクティブセッには，クライアントの IP アドレスなどを利用する．

ションを比較して傾向の類似性を調べる際，それぞれが完全に

このように取り出されたユーザセッション中の任意の 2 つの一致する必要はなく，共通要素が多く存在する場合に，lcsi はセッションから LCS を求める問題は，SED（Shortest Edit Dis-

そのアクセスの特徴を表現しているとみなすことができる．しtance）を求める問題に還元することができる．SED は，長さたがって，lcsi と actn の間で共通しているページを調べ，lcsi

M ，N のシーケンス A， B の各要素を X，Y 軸上に並べたときの後半部分の中でまだアクセスされていないページがあれば，の，(0,0) から (M,N) までの最短距離として求められる．移動

そのページはその後にアクセスされる可能性が高いといえる．

距離が 0 となる部分の要素のみを抜き出したものが LCS であ以上を踏まえ，WRAPL では，以下の手順で推薦ページの決るため，我々は，この問題に関して効率化された手法 [10] を用定を行う．

いる．この手法では，比較する二つの文字列の差異が小さいほ（ 1 ） lcsi と actn の間で共通するページを抜き出す．

ど必要とする時間計算量が小さくなるため，実際のデータに適（ 2 ） lcsi より，一番目から共通部分の最後までの要素全て

用すると，単純に動的計画法を用いて計算する場合に比べ，大を除去する．

幅に小さい計算量での LCS の抽出が可能になる．

（ 3 ） 残ったページ {p1 , p2 , · · · , pk } を推薦ページの候補とし，これらの処理を，Web アクセスログから得られた全てのセッ

そのそれぞれの point に f (lcsi , actn , p j ) を加える．

ションの全組み合わせに対して行い， 各 LCS の出現頻度の集（ 4 ） LL 中の全ての要素に対して（1）∼（3）を行い，候補計を行うことで，高頻度で出現する LCS パターンを発見する．

ページの中で得点の総和が上位のページを推薦する．ただし，

この計算は，全てのユーザセッションの全組み合わせに対して行うため，セッション数が大きくなるとその二乗に比例して

f (lcsi , actn , p j ) はある候補ページ p j に対する得点計算のための関数とし，具体的な計算式については 3. 2. 2 節で述べる．

時間計算量が増加してしまい，計算コストが大きいという問題

ここまでで述べた，LCS を用いた推薦手法の概要を図 1 にがある [11]．本研究では，ハッシュを用いたアクセスシーケン

示す．例えば，ページ推薦のステップにおいて，図のように

スのフィルタリング手法やインクリメンタルな LCS 抽出手法，

act3 = (A, B, C) が与えられた時，lcs1 = (A, B, C, D, E) と一致す

並列計算のためのアルゴリズム [12] を用いることで，LCS 抽出

る部分は (A, B, C) であり，それに続くページ D, E が推薦の候補にかかわる計算量をさらに抑えている．

ページに加えられる．また lcs2 = (A, D, B, C) については，同様

3. 2 LCS を利用した Web ページ推薦に (A, B, C) が一致するものの，共通部分の最後のページ C 以降

3. 2. 1 推薦候補ページの選出と推薦ページの決定に続くページはないため，ここから推薦候補に加えられるペー

WRAPL では，アクセスログから抽出した LCS のそれぞれジはない．さらに，lcs3 = (B, C, E) では E となる．したがって，と，現在までのユーザセッション（アクティブセッション）とこの例で lcs1 〜lcs3 から推薦されるページの候補は {D, E} となのマッチングを行い，頻出 LCS の中で，ユーザの現在位置以降

る．ここでは，ページ E が 2 つの LCS で推薦候補となっていに現れているページを推薦する．

る．したがって，各 LCS から算出された得点の和がページ E

表 1 検索条件等のパラメタを含む URL の考慮

0.4 5

内容

除外

0.4

絞込条件（業態，場所，予算，距離），検索タイプ，

0.3 5

特集テーマ，路線検索 [路線，駅]，地図検索 [大／小]0.3

表示様式（表示順），絞込み条件（日時，詳細条件），

0.2 5

リンク元，文字コード

precision考慮

エリア（地方，県，都市），表示様式（件数，ページ），W R A P L
A R

W R A P L (re m )A R (re m )

0.2
0.15

の得点となる．

0.1

3. 2. 2 推薦候補ページの順位決定手法
推薦候補ページの優先順位を決定する方法として，我々はこれまでに，WRAPL-FL 法 [8] と，その拡張である WRAPL-FLP

0.05
0

0

0.02

0.04

0.06

法 [9] を提案してきた．ここでは，WRAPL-FLP 法を説明する．
推薦順を決定するための推薦候補ページへの得点付けに際し

0.08
c o v e ra g e

0.1

0.12

0.14

0.16

図 2 WRAPL-FLP 法と相関ルールを用いた手法の比較ては，以下のような点を考慮する必要があると考える．まず，高い ci を持つ lcsi は，多くのセッションにおいて頻繁にナビ集やコンテンツページ，エリア別ページや，検索ページなどへゲートされたアクセスパスの部分シーケンスであり，重視すべのリンクがあり，そこから各レストランページへの直接のリンきである．また前述のように，lcsi と一致の度合いが高い actn

クが張られている．検索結果の表示ページなどに代表されるは同じ傾向を持つ可能性が高いと考え高い得点を付加する．さ

動的ページへのアクセスが多く，その場合，検索条件によってらに，アクティブセッション中の後方ページは，それに続くア

URL は変化するため，ユーザのアクセス行動は非常に多様でクセスと関連性が高い [9] ため，後方ページが一致する LCS をあった．我々のこれまでの報告では，動的に生成されるページ

重視する．

へのアクセスは解析対象の URL から除外したが，今回は，こ以上の 3 点を考慮した上で，各候補ページの得点計算のた

れらのページも対象とした．

めの方法として，FLP（Frequency, matched Length and Position

サイトの構造から，各々のレストランページへのアクセスにbased weighting）法を定義する．Large LCS 集合 LL と長さ n の比べ，トップページや検索ページ等の上位階層の Web ページ

アクティブセッション actn に対し FLP 法では，あるページ p

へのアクセスが圧倒的に多い．そのため，無数に存在するレスの得点の算出方法として次の式を用いる．ただし，ページ p は

トランページの推薦を目的とする場合，条件を限定せずに十分

候補ページの集合に含まれるものとする．

な量のパターンを抽出するためには，膨大な量のアクセスログ

point(p) =∑|lcsi ∩ p actn | · cαi ·liγ

(1)lcsi ∈LL

ここで ∩ p は，以下を満たす演算子とする．要素 p，シーケン
ス l，a に対し，l ∩ p a は l と a の LCS であり，かつ l 内のその

LCS の全ての要素より後ろに必ず p が現れるシーケンスを表す．li はマッチ位置重みを表し，アクティブセッション中の後方ページが lcsi と一致する場合に大きくなるように設定する．
また，α，γ はそれぞれ ci と li の重みであり，Web サイトの特徴からその影響度合いを考慮して適切に調節する．

4. 大規模商用サイトにおけるアクセスログの解析
本節では，大規模商用サイトの実際のアクセスログに対し，の解析が必要となる．
そこで今回は，解析対象から各レストランページを除外し，特集ページの推薦を目的として，特集ページへのアクセスを 1
回以上含むセッションのみを対象とし，推薦の評価に利用できない長さが 3 以下のセッションも除外した．
また，固有 URL 数を削減するため，路線検索や地図検索などのページにおけるパラメタや，検索ページ URL 中に含まれる，cgi に対するパラメタの内，不要なものを除外することを考える．全てのパラメタを考慮するのではなく，出現頻度が高く，またユーザの嗜好やアクセスの傾向を反映し得ると予測できるパラメタのみに限定し，それ以外のものを除外することで，URL を再構成した（表 1）．その結果，ログ全体の中に出現する固有 URL 数は 7 日分で 77,007 となった．

WRAPL を適用し，その有効性を評価する実験に関して説明す

4. 2 WRAPL の適用とその結果る．また，推薦結果やサイトの持つ特徴に対して考察を行った

4. 1 節のデータに WRAPL-FLP 法を適用し，相関ルールを用後，異なるアプローチについて検討する．

4. 1 実験対象データ

いた Web ページ推薦手法 [5] との比較を行った．

4 日分のアクセスログ（10 月 16 日〜19 日，19,974 セッショ

実験対象として，商品紹介を行う大規模商用サイト “ぐるなン）を学習セットとしてそこから LCS を抽出し，また，続く 3び”（http://www.gnavi.co.jp/）の Web サイトにおける，2006 年日分のアクセスログ（10 月 20 日〜22 日，14,951 セッション）

10 月 16 日から 10 月 22 日までの Web サーバへのリクエスト

をテストセットとして評価を行った（注 2）．

に対するアクセスログを用いた．
おおまかなサイトの構造としては，トップページの中に，特（注 2）：19 日と 20 日にまたがる 13 セッションは評価対象から除いた．

4 日分のログから，WRAPL では，抽出した LCS の内カウン「大阪版トップページ」の 5 つが推薦ページに含まれる場合に，トが 100 以上のものを Large LCS 集合として推薦に利用し，相それらを推薦候補から除外し，|Recom| + 1 位以下のページを繰

関ルールを用いた手法では，最小サポート値を 0.005 としてアり上げて推薦する方法についても推薦精度を計測した．結果をプリオリアルゴリズムで相関ルールを抽出したものを利用した．

図 2 中の実線（rem）で示す．この結果，トップページやエリ

推薦精度の評価に当たり，我々は文献 [5] と同様に，テスト

ア毎のトップページなどの頻出ナビゲーションページを Recom

セット中でアクティブセッションに続いてアクセスされたペーから除去することで，推薦の精度が低下することが分かる．

ジはユーザが好ましいと思う Web ページであるとみなす．そ4. 3 抽出された LCS の特徴とその利用効果

こで，評価に用いる指標として，以下に定義される precision と以下では，抽出された LCS にはどのようなものがあり，まcoverage を用いた．precision は適合率であり，推薦されるペー

たどのような特徴があるかについて述べる．さらに，ユーザにジ数に対する正解ページ数の割合で表現される．また，coverage

とってより有用な情報の推薦を目的とし，その特徴を利用する

は再現率であり，評価セットのページ数に対する正解ページ数

ことで期待できる効果について議論する．

の割合で表現される．

|Recom ∩ eval||Recom||Recom ∩ eval|coverage(Recom) =|eval|

precision(Recom) =特徴的なアクセスパターンを発見するために，前節の実験で用いた 7 日分のセッションから，1,504,887 本の LCS を抽出

(2)
(3)

した．
得られた LCS を調査したところ，長さが 3〜5 程度のものが大部分であった．また，上位階層への後戻りや，検索ページに

ここで，Recom，eval はそれぞれ対象アクティブセッションか

おいて固有 URL 数を削減するために除外したパラメタの影響ら導かれた推薦ページの組，対象アクティブセッションに引きで，同じページを複数回含む LCS も多く見られた．

続いて実際にアクセスされたページの組（評価セット）を表す．

LCS カウントは，トップページを 3 回繰り返すパターンがページ推薦を行うために，テストセットの各セッション（テ

最大の 15,297,317 となり，それ以降の分布には大きな偏りがストセッション）のはじめの n ページをアクティブセッション

あった．全体的にカウントの小さい LCS が大部分を占めており，

actn とみなして，Large LCS 集合 LL 中の全要素とマッチング

LCS カウントが 100 以上のものは，全体の 1.3%程度であった．

を行う．そこから推薦ページの順位付けを行って上位のページ

アクセスの傾向を見ると，トップページ ↔ 特集／検索ページ

を推薦し，そのセッションの残りのページ eval と比較すること↔ レストランページ間の往復を行うユーザが非常に多く見られで precision と coverage を求めた．

た．これは，条件に合うレストランページの閲覧や比較を行う

アクティブセッション長を 2 とした場合の結果を図 2 に示ために多くのユーザがこのようなアクセス行動を取ったためです．凡例中の WRAPL，AR はそれぞれ，提案手法，比較手法あると考える．したがって，トップページや特集／検索ページ

である相関ルールを用いた手法を用いて推薦を行った場合の結等のナビゲーションページのアクセス頻度が高くなる．

果に対応している．グラフ中の各点は，推薦する上位ページの

WRAPL 等の，Web アクセスログのマイニングを利用した推数 |Recom| を 1 から 14 の間で変化させた時の結果に対応して薦手法では，多くの場合，パターンの出現頻度に応じて推薦おり，右の点ほど |Recom| が大きいを場合を表している．ここページの順位付けが行われるため，複数のパターンに頻繁にで，相関ルールを用いた手法では，actn 中に同じ URL が含ま含まれるページ，すなわちナビゲーションページ等のアクセスれる場合には推薦ができず，また actn 中に含まれるページを推頻度の高いページが推薦されやすくなる．一方で，アクセスパ

薦することもない．したがって，今回の実験では，条件を揃えターンに特徴的な傾向があるものの，アクセス頻度そのものがて比較を行うために，セッションの初めから重複のない n ペー

低い Web ページは推薦されにくい．

ジを取って actn とし，WRAPL では actn 中に含まれるページは推薦しないこととする．

これまでの評価では，ユーザに常に何らかのページを推薦す
ることを前提に，各テストセッションに対し，アクティブセッ

図 2 からは，WRAPL と既存手法の間で優位な差は確認できション長に達したとき必ず推薦を行い，それを評価した．こなかった．そこで，実際に推薦されているページを比較したとの場合，そのセッションの特徴が出現する前にナビゲーション

ころ，どちらの場合においても，アクセス頻度が高い，トップページ等へのアクセスを含むことで適切な推薦が難しかったり，ページ等のインデックスページ（以降では，これらのページを

また，セッションが特徴的なアクセスパターンを持つときにも，ナビゲーションページと呼ぶ）が推薦ページの上位に入ることそれに合致するルールの後半部分にナビゲーションページが含が多かった．我々は，ナビゲーションページばかりが推薦されまれる場合には，それらのページばかりが推薦されてしまう

ることは，ユーザにとって有益ではないと考えるが，これらの可能性がある．そのため，ルールの持つ特徴を反映し，適切なナビゲーションページを基点として各特集ページへ移動し，比Web ページ推薦を行うためには，特徴的な傾向を表す推薦ルー

較検討を行うユーザ（セッション）が多いことを考慮すると，

ルと同様の傾向を示すユーザのみに対し，そのルールを用いてこれらのページは解析対象から除くべきではないと判断する．

推薦する，絞込み推薦を行うべきであると考える．

そこで，LCS の抽出と推薦ページの得点付けはこれまでと同

そのような方式において，提案手法で利用している LCS が有様に行い，特にアクセス頻度の高い「トップページ」，「関東版

効であるかを議論するために，抽出した LCS から得られた特トップページ」，「関西版トップページ」，「東京版トップページ」，

徴的なアクセスパターンを基に，アクティブユーザが，各 LCS

表 2 LCS，相関ルールそれぞれのヒット率の比較
ユーザの特徴推薦されるページ

関東版トップ (→) 女性が喜ぶレストラン特集
関東版トップ (→) デートで行くお店特集
ぐるなび食べ放題トップ (→) 焼肉・ステーキ特集
ぐるなび食べ放題トップ (→) 今月の食べ放題特集

ヒット率

ヒット率

（順序あり）（順序なし）

デートで行くお店特集

0.09770.0797

女性が喜ぶレストラン特集

0.0762

0.0565

今月の食べ放題特集

0.26760.2112

焼肉・ステーキ特集

0.06750.0721

ぐるなびシニアトップ (→) ゆっくりと落ち着けるお店特集

今月のおすすめレストラン特集

0.39130.3600

ぐるなびシニアトップ (→) 今月のおすすめレストラン特集

ゆっくりと落ち着けるお店特集

0.13330.1250

落ち着いた大人の個室特集

0.1124

0.0967

トップ (→) カップル向け個室特集
トップ (→) 落ち着いた大人の個室特集

カップル向け個室特集

0.08570.0828

女性が喜ぶレストラン特集

0.03690.0172

トップ (→) 女性が喜ぶレストラン特集

記念日&誕生日に行きたいお店特集

0.06290.0597

関東版トップ (→) デートで行くお店特集

記念日&誕生日に行きたいお店特集

0.07140.0484

デートで行くお店特集

0.07250.0484トップ (→) 記念日&誕生日に行きたいお店特集

関東版トップ (→) 記念日&誕生日に行きたいお店特集

中の初めの数ページへアクセスしたとき，それに続くページをユーザに推薦できるかどうかを検証する．

4. 4 考察4. 2 節の実験では，ナビゲーションページを推薦候補から除評価に際し，7 日分から抽出した LCS を調査し，長さ 3 の去した結果，推薦精度が悪くなるという結果を得た．トップ

LCS の中から，特集ページを 2 ページ以上含み，かつ 3 ページ

ページや地域トップページなどのナビゲーションページがシー

目が特集ページであるものを選択し，特徴的なルールとみなしケンスの途中に含まれることは，例えば，一旦トップページにて利用した．

戻ってから，別のページに移動するなど頻繁に起こることであLCS を想定した場合の実験として，先述の 3 日分（10 月り，我々はそのような行動は推薦の際の特徴として捉えるべき20 日〜22 日）のテストセッションの内，長さが 3 以上のもの

行動であると考えていた．しかしながら，近年検索サイトの普（14,371 セッション）の中で，該当する LCS の初めの 2 ページ

及により，ユーザはトップページからトップダウンにレストラ

が順番通りにアクセスされているセッションに対象を限定し，ンページを探し始めるだけではなく，レストランページから閲

その中で初めの 2 ページに引き続き，該当する LCS の最後の覧をはじめ，各階層のナビゲーションページまで戻って，サイ特集ページがアクセスされているセッションの割合（ヒット率）

ト構造を確認しながら閲覧する場合がある．また，今回対象とを求めた．また，相関ルールを想定して，順序を考慮せずに初したような，多数の商品を紹介する商用サイトの場合，商品をめの 2 ページを含むセッションを対象とし，同様の実験を行っ比較検討する段階で，ナビゲーションページや検索ページに頻た．結果を表 2 に示す．なお，表中のユーザの特徴欄の (→) は繁に戻ってくることなどから，ナビゲーションページ含むルー

LCS の場合の順序を示す．相関ルールの場合には，これらの 2

ルが多く抽出されてしまい，結果として，ナビゲーションペー

ページのアクセス順は考慮されていない．

ジが上位に推薦されてしまった．

表から，大半は 10%前後のヒット率であることが確認できる．

4. 3 節の実験では，それぞれのルールのヒット率は低いながまた，LCS に対応するアクセスの順序を考慮した場合のヒッ

らも，全てのユーザに対して常に推薦する方法ではなく，特徴ト率は，相関ルールに対応する順序を考慮しない場合のヒット的な傾向を表す推薦ルールに合致するユーザのみに，そのルー率よりも，1 件を除いて若干ながら良いという結果が得られてルを用いて推薦する絞込み推薦の効果を示すことができたと考いる．

える．本稿の実験では，各ルールを個別に評価したが，実際はさらに，「ぐるなびシニアトップ」から，ぐるなびシニア以下の複数のルールを同時に適用できるため，推薦の精度は向上する「今月のおすすめレストラン」と「ゆっくりと落ち着けるお店」

ものと考える．そのためにも，実際に絞込み推薦を実現するたへのアクセスや，「ぐるなび食べ放題トップ」から，ぐるなび食めのアルゴリズムを検討する必要があると考える．

べ放題以下の「今月の食べ放題特集」と「焼肉・ステーキ特集」

次に，絞込み推薦がカバーできるユーザの割合について考察

へのアクセスのように，アクセス順によってヒット率が大幅にする．表 2 において，順序あり，なしの場合の各ルールにおけ変わるルールが存在することも確認できた．

る平均対象セッション数はそれぞれ 221，261 であり，最大のこのような場合，単なる共起関係では区別をすることはできルールでも 406，513 セッションに留まった．この結果についず，順序の情報が必要となる．本稿での実験では，2 ページのて解析を行うために，同様の 3 日分の 14,371 セッションを対アクセスから推薦を行うため，相関ルールとの差は顕著ではな

象に，個々の特集ページについて，それらを含むセッションの

いが，2，3 ページ目の順序が入れ替わることでヒット率に大き割合を求めた．出現頻度が最も高い 4 つの特集ページと，そのな差が生じるルールがあることから考えても，推薦に至るペー

割合を表 3 に示す．1〜4 位のページが出現するセッションの数

ジ数が増えることで，LCS と相関ルールの差は明確になると考はそれぞれ 876，661，488，402 であり，全セッション数に対える．

して非常に小さい値となっている．3 日分のアクセスログに出表3

出現頻度が上位の特集ページを含むセッションの割合

直感的・主観的な評価を行うことができると考える．

出現順位（内容）割合

手法の改善に関して，レストランページの推薦や，より高速

1 位（今月の食べ放題特集）

0.061

かつ精度の高い推薦を行うためには，十分な量のログからの2 位（記念日 & 誕生日に行きたいお店特集）

0.046

LCS の抽出，目的に合った LCS の選択や限定を行うアルゴリ

3 位（少人数でもやっぱり個室特集）

0.034

4 位（お誕生日特典特集）

0.028

ズムが必要となる．そのためにも，より高速に効率よく LCS を抽出し，アクティブセッションとのマッチングを行う必要がある．また，本稿では，ページをナビゲーションページ，レスト

現する特集ページが 484 種類と多数であることも考慮し，これ

ランページ，特集ページの 3 種類に分類し，それぞれを区別しらの特集ページに対するアクセスは，大きな偏りがなく分布したが，より詳細な分類を加え，その分類を，LCS 抽出や推薦のていると判断する．これによって，絞込み推薦でカバー可能な際に利用することで，より高度な推薦が可能になると考える．

ユーザの割合が小さくなったと考える．前提としている条件が

例えば，レストランページの推薦を目的とし，料理カテゴリな異なるため，単純に比較をすることはできないが，直感的な推どを用いて分類（抽象化）を行うなどの応用が考えられる．実薦方法として，最頻出特集ページの推薦を考える場合，ヒット

際のサイトのログを分析し，これらの応用を検討することも今

率は表 3 中の “割合” と同程度の値になると予測できるため，表後の課題である．

2 の多くの場合で，より高いヒット率が達成されていることがさらに，今回比較対象とした，Web 利用マイニングの一種で確認できる． 現状では，絞込み推薦でカバーできるユーザの割ある相関ルールを用いた Web ページ推薦手法以外にも，協調合は小さいが，今後は，それぞれの特集ページに対する特徴的

フィルタリングを用いた [13] などの推薦手法とも比較を行ってなルールを考慮し，それらを組み合わせることで，より多くのいきたい．

ユーザをカバーできるようになると考える．

5. お わ り に
5. 1 ま と め
本研究では，Web 利用マイニングに基づく Web パーソナライゼーションに焦点を当て，Web 利用マイニング手法として，アクセスシーケンスが完全に一致しない場合でも全体のアクセスの傾向の表現が可能である，LCS（Longest Common

Subsequences）に着目し，LCS を用いた Web ページ推薦手法である WRAPL を提案してきた．
本稿では，これまで比較的古く，現存しない Web サイトのログを用いて評価してきた WRAPL を，大規模な商用サイトの新
しいアクセスログに適用することで，WRAPL による Web ペー
ジ推薦の効果を議論し，また，Web サイトの持つ特徴を調査することで，異なるアプローチである絞込み推薦を考案した．
実験の結果から，現在の Web サイトでは，動的ページや検索サイトの普及から，WRAPL や相関ルールを用いた既存手法，
単に適用しただけでは，サイトトップページやコンテンツ毎のトップページなどのナビゲーションページを推薦しやすいことが分かった．そこで，抽出された LCS の中で特徴的ないくつかのルールに対して，対象とするユーザを限定して推薦を行う方法について検討し，その中で，LCS の持つ順序情報は推薦に良い影響を与えることを確認した．

5. 2 今後の課題
本研究の今後の課題として，まず絞込み推薦の実現と評価に向け，利用すべきルールの選定条件や推薦を行うための合致度
合いの条件，適用のためのアルゴリズムなどを調査する必要があると考える．また，その結果として推薦されたページが，ユー
ザにとって有用であったかどうかを評価するために，被験者実験を行うことも有意であると考える．本研究の目標は，ユーザにとって有用なページを推薦することであるため，被験者実験を通して，評価指標による客観的な評価のみでは判断が難しい，

謝

辞

本研究で利用したアクセスログの御提供ならびに初期加工に御協力いただきました，株式会社ぐるなびの 福島常浩氏， 古木信司氏，岡本拓明氏に深く感謝致します．また， 本研究の一
部は，文部科学省科学研究費補助金特定領域研究 (18049026)，
東京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化と活用基盤構築」および独立行政法人科学技術振興機構戦略的創造研究推進事業 CREST の助成により行なわれた．
文

献[1] Magdalini Eirinaki and Michalis Vazirgiannis. Web mining for web
personalization. ACM Transactions on Internet Technology(TOIT),
Vol. 3, No. 1, pp. 1–27, 2003.
[2] 大塚真吾, 喜連川優. Web アクセスログとその利活用. 人工知能
学会誌, Vol. 21, No. 4, pp. 410–415, 2006.
[3] Andrej Kristoﬁc and Mária Bieliková. Improving adaptation in Webbased educational hypermedia by means of knowledge discovery. In
Proceedings of the 16th ACM Conference on Hyertext and Hypermedia, pp. 184–192, 2005.
[4] Xiaobin Fu, Jay Budzik, and Kristian J. Hammond. Mining navigation history for recommendation. In Intelligent User Interfaces, pp.
106–112, 2000.
[5] Bamshad Mobasher, Honghua Dai, Tao Luo, and Miki Nakagawa.
Eﬀective personalization based on association rule discovery fromWeb usage data. In Proceedings of the 3rd International Workshop
on Web information and data management, pp. 9–15, 2001.
[6] Bamshad Mobasher, Honghua Dai, Tao Luo, and Miki Nakagawa.
Using sequential and non-sequential patterns in predictive Web usage
mining tasks. In Proceedings of the IEEE International Conferenceon Data Mining (ICDM’02), pp. 669–672, 2002.
[7] Olfa Nasraoui and Chris Petenes. An intelligent web recommendation engine based on fuzzy approximate reasoning. In Proceedingsof the IEEE International Conference on Fuzzy Systems, pp. 1116–
1121, 2003.
[8] 山元理絵, 小林大, 小林隆志, 横田治夫. Web アクセスログの LCSを用いた web ページの推薦手法. 信学技報 DE2006-40, 電子情報通信学会, 2006.
[9] 山元理絵, 小林大, 吉原朋宏, 小林隆志, 横田治夫. アクセスログに基づく Web ページ推薦における LCS の利用とその解析. In
Proceedings of the IPSJ DBWeb2006, pp. 43–50, 2006.

[10] Sun Wu, Udi Manber, Gene Myers, and Webb Miller. An O(NP)sequence comparison algorithm. Information Processing Letters,Vol. 35, No. 6, pp. 317–323, 1990.
[11] 宇根田純治, 横田治夫. Web ログの共通シーケンス解析. 信学技
報 DE2002-2, 電子情報通信学会, 2002.
[12] 戸田誠二, 横田治夫. LCS を用いたアクセスログ解析の並列処理による性能向上. 第 13 回データ工学ワークショップ論文集,
DEWS2004 7-B-5, 2004.
[13] Greg Linden, Brent Smith, and Jeremy York. Industry report:
Amazon.com recommendations: Item-to-item collaborative ﬁltering.
IEEE Distributed Systems Online, Vol. 4, No. 1, 2003.