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

アクセスログに基づくWebページ推薦におけるLCSの利用とその解析

Title(English)

Analyses of the Effects of Utilizing Web Access Log LCS for Web Page
Recommendation

著者(和文)

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

Authors(English)

RIE YAMAMOTO, DAI KOBAYASHI, TOMOHIRO YOSHIHARA,
TAKASHI KOBAYASHI, HARUO YOKOTA

出典(和文)

Proc. of IPSJ DBWeb2006, Vol. , No. , pp. 43-50

Citation(English)

Proc. of IPSJ DBWeb2006, Vol. , No. , pp. 43-50

発行日 / Pub. date

2006, 11

権利情報 / Copyright

ここに掲載した著作物の利用に関する注意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
The copyright of this material is retained by the Information Processing
Society of Japan (IPSJ). This material is published on this web site withthe agreement of the author (s) and the IPSJ. Please be complied with
Copyright Law of Japan and the Code of Ethics of the IPSJ if any users
wish to reproduce, make derivative work, distribute or make available tothe public any part or whole thereof.

Powered by T2R2 (Science Tokyo Research Repository)

アクセスログに基づく Web ページ推薦における LCS の利用とその解析
山

元 理 絵†小 林

小 林
大†,†† 吉 原 朋 宏†隆 志††† 横 田 治 夫†††,†

近年，Web サイトによる情報発信の重要性から，ユーザのニーズに適したサイト構築や情報提供の要求が高まってきている．Web アクセスログを Web ページ推薦に用いる方法は，クライアント側に手を加える必要がなく有用であるが，これまで提案されている手法では，頻出アクセスパターンと僅かでも外れると適切な推薦ができない，あるいは順序を考慮できないといった問題点があった．我々は，それらの問題を解決するために，Web アクセスログから LCS（ Longest Common Subsequences ）を抽出してページ推薦に利用する手法である WRAPL を提案している．本稿では，実際の Web アク
セスログを用いた実験を通して WRAPL の効果を詳細に解析し，その実験結果から得られた知見を基に優先順位付け手法に対して改良を行い，その有効性を示す．

Analyses of the Effects of Utilizing Web Access Log LCS for Web Page Recommendation
R Y,† D K,†,†† T Y,† T K†††and H Y†††,†
Sophisticated websites satisfying users' requirement becomes much more important to propagate information via websites, nowadays. Web page recommendation methods using web access logs are useful forthem because they need no modication in client-side applications to meet the requirement. However, traditional methods have problems of insufficient recommendation precision caused by strict matching of accesspatterns or neglect of access sequences. To solve the problems, we are proposing 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 effects of WRAPL using actual web access logs
and propose an enhanced weighting method for it to improve the precision based on the analyses.

1.

TextExtractor

はじめに

2)

がある．ユーザの嗜好を評価するためのフィードバックとして，ページ内のテキスト部分を，文や行の単位で興味情報として抽出できるが，クライ

近年，ビジネスの場としての Web の役割と情報量の1)増大から，Web personalization が注目され ，特にユーアント側にプログラムを埋め込まなければならない等

ザの嗜好に合った Web ページをシステムがユーザにの問題点がある．

推薦し提示する Web ページ推薦が盛んに研究されて一方，アクセスログを利用する方法は，クライアン

いる．その情報収集の方法としては，閲覧した情報にト側の変更が不要であることから，様々な利用方法が対する各々のユーザの興味の有無を何らかの方法で収研究されている．当初は，相関ルールを用いた頻出共集し分析する方法や，Web サイトのアクセスログを分

起ページの組の抽出3),4) や，利用頻度に基づくリンク

析する方法などが取られる．

の接続性の評価5) ，バックトラックポイントの発見6) 等

前者の例としては，ユーザによるなぞり読みやリンのアクセス解析の研究が中心であったが，最近では，

ククリック等の特徴的なマウス操作を利用している

ユーザビリティの向上を目的とし，ユーザ行動の予測
手法7) や Web ページ推薦に関する手法8) が提案され† 東京工業大学大学院情報理工学研究科計算工学専攻ている．

Department of Computer Science, Graduate School of Information

ユーザ行動の予測手法7) では，ログ中のユーザのア

Science and Engineering, Tokyo Institute of Technology

クセスパスの統計を取ってユーザ行動をモデル化し ，†† 日本学術振興会特別研究員 DC
Research Fellow (DC), Japan Society for the Promotion of Science

全てのページに対し，現在のアクセスパスに引き続い††† 東京工業大学 学術国際情報センターてアクセスされるための条件付確率を算出することで，

Global Scientic Information and Computing Center, Tokyo Insti-

続くアクセスページを予測する．この中で，予測モデ

tute of Technology- 1-

ルの適用例の 1 つとして Web ページ推薦が挙げられセスログに基づく Web ページ推薦における LCS の利ているが，このような手法では推薦されるのは直後の用効果をより詳細に解析するために，条件及び設定をページのみに限られてしまう．さらに，サイト内のナ

変更したいくつかの実験を行うと同時に，それらの実

ビゲーションが不適切な時やサイト規模が大きい時に験結果から得られた知見を基に手法の改良を行い，そは，目的のページに到達するまでに後戻りや遠回りをの効果を調べる．

含んだり，目標が複数存在することで，多種多様なパ2.

スを取りうるため的確な推薦が難しい．
一方，相関ルールを用いて Web ページ推薦を行う手

Web アクセスログ解析への LCS の適用

本節では，我々が以前に提案してきた，アクセスロ

8)

法 では，アクセスログに apriori アルゴ リズムを適

グから LCS を抽出する方法9),10) について述べる．LCS

用して 1 セッション中で頻繁に共起するページの組を抽出するためには，まずアクセスログからユーザの集合及びページアクセスにおける相関ルールを作成

セッションを切り出し，データを精錬する必要がある．

してページを予測する．アクセスパスそのものを扱う

その後，各セッションを比較することで LCS を抽出のではなく，共起頻度の高いページ同士の関係を見てし，その頻度を集計する．

推薦を行うため，前述の直後のページの推薦に限られ2.1るという問題や，後戻りや遠回りを含む場合の問題を

リスト x の部分列とリスト y の部分列の中で両方解消することができる．しかし，この手法ではページのリストに含まれるものを共通部分列という．共通部

アクセスの順序情報を含まないため，ページ参照の順

分列の中で最も長いものを最長共通部分列（ Longest序に特徴的な傾向がある場合など ，すでにアクセスしCommon Subsequences ）と呼び，LCS と略す．

LCSたページを推薦したり，ユーザにとってもはや不要と二つのリストの中に同じ要素が同じ順序で出現したなったページを推薦することで，推薦精度を低下させものが共通部分列なので，LCS が長いということは二てしまう可能性がある．

つのリストの類似性が高いことを表す．

我々は，順序情報を考慮しないという上記の問題をこれを URL シーケンスに適用することで，アクセ解決するため，アクセスログ中のシーケンスの LCS

スシーケンスが完全に一致しない場合でも，寄り道等（ Longest Common Subsequence ）を用いることで，アの余分な情報を取り除くことにより各々のシーケンス

クセスパターンのぶれを吸収した概括的なアクセス間の類似性を発見することができると考える．

順序を利用して推薦精度を向上させる手法を提案して

2.2

いる．

2.2.1

LCS を用いた Web アクセスログ解析

ユーザセッションの抽出

これまでに，LCS を用いたアクセスログの解析手法

アクセスシーケンス解析を行う際，蓄積されているとその解析に基づくサイト構成の改善手法9) ，その場

未加工のアクセスログを精錬して，マイニングに必要

合の LCS 抽出の効率化手法10) を提案し，その有効性なデータのみを取りだし，ユーザのセッションを抽出を示してきた．Web サイト内における全てのセッショする必要がある．

ンの URL の推移をシーケンスとして抽出し，そのそサイト内におけるユーザごとの移動情報を得るため，

れぞれに対して他の全てのシーケンスとの LCS を求IP アドレスや Cookie を用いて各セッションに一意なめ，頻出アクセスパターンを発見するものである．

セッション ID を割り当てる．特に，ユーザのナビゲー

さらに，本稿の事前検討として，上述のアクセスロ

ションに合わせてリアルタイムに適切なページ推薦をグ解析によって抽出された LCS を用いて現在までの行うことを目的とする本研究においては，Cookie を

アクセス履歴から次にアクセスされるページを予測し用いることが好ましいが，これはユーザの了承を必要て推薦する手法に関して，研究会で報告を行った11) ．

とするため，Cookie 情報が利用できない場合は，複数

LCS を用いることで，アクセスパスが完全に一致しなのユーザを含む可能性があるため正確性は下がるもの

い場合でも全体のアクセスの傾向の表現が可能になるの，IP アドレスの情報などで代用する．

とともに，順序情報を保持することができるため，実セッション ID ごとに整理された URL の集合を時際の Web アクセスログを用いた実験において，相関

系列順に並べることで，各セッションで訪問者が行っルールを用いる手法と比較して推薦精度が向上した実

たアクセスの URL シーケンスを得ることができる．

験結果が得られている．しかし，事前検討であったた

アクセスログの中には，画像ファイルへのアクセス等

め実験内容とその解析が必ずしも十分でなく，予想にの解析処理を行う際に不必要な情報や目的に合わない

反する結果も含まれていた．そこで，本稿では，アク情報が多く含まれる．そのため，セッション抽出時に，- 2-

さが min.Length 以上である LCS の集合を large LCS

前処理12) によりそれらの情報を取り除く必要がある．
2.2.2

集合と呼び，LL = {lcs1 , lcs2 , · · · lcsk } で表す．また，LL

LCS の抽出

二つのシーケンスから LCS を求めるには，動的計

内の i 番目の要素が全セッション中で数え上げられた画法が用いられる．これにより長さ M の文字列 X と

回数を ci と表す．ここで，min.Count と min.Length は，

長さ N の文字列 Y の LCS を求める場合，O(MN) 時

Web サイトの持つ特性に合わせて設定するパラメータ13)

間で LCS を求めることができる ．

である．このとき，長さ n のアクティブセッション actn

ま た ，LCS を 求 め る 問 題 と 等 価 で あ る ，SEDからそれに続くユーザのページアクセスを予測する．

（ Shortest Edit Distance ）を求める問題に関して，効率

lcsi と actn の間で共通しているページを調べ，lcsi

14)

化された手法が提案されている ．この手法では，比の後半部分の中でまだアクセスされていないページが較する二つの文字列の差異が小さいほど必要とする時

あれば，そのページはその後にアクセスされる可能性

間計算量が小さくなるため，実際のデータに適用するが高いと我々は考える．なぜなら，lcsi と actn を比較と，多くの場合で O(MN) よりも大幅に小さい計算量

する際，それぞれが完全に一致する必要はなく，共通

で LCS の計算が可能になる．

要素が多く存在する場合に lcsi はそのアクセス傾向の

2.2.3

LCS の頻度集計

特徴を表現していると捉えることができるからである．

Web アクセスログから得られた各セッションを，URL

また，推薦順を決定するための推薦候補のページへを各要素に持つシーケンスとみなし，各シーケンスにの得点付けに際しては，以下のような点を考慮する必ついて総当たり的に LCS を抽出する．各 LCS の出現

要がある．まず，高い ci を持つ lcsi は，多くのセッ頻度の集計を行い，高頻度で出現する LCS パターン

ションにおいて頻繁にナビゲートされた部分シーケを発見する．

ンスであり，重視すべきである．また上述のように，

LCS 抽出のための計算においては，全てのアクセス

lcsi と一致の度合いが高い actn は同じ 傾向を示す可シーケンスに対して総当りで求めるため，セッション

能性が高いと考え，高い得点を付加する．以上を考数が大きくなるとその二乗に比例して時間計算量が増慮した上で，優先順位を付けて推薦を行うための手法

加してしまい，計算コストが大きいという問題があるとして，WRAPL-FL（ Web page Recommendation byが 9) ，本研究では，ハッシュを用いたアクセスシーケ

Access Pattern Lcs with Frequency and matched Length

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

based weighting ）法を定義する．large LCS 集合 LL と抽出手法，並列計算のためのアルゴリズム10) を用いる

長さ n のアクティブセッション actn に対し WRAPL-FL

ことで，LCS 抽出にかかわる計算量をさらに抑えるこ

法では，あるページ p の得点の算出方法として次の式ととする．

を用いる．ただし，ページ p は候補ページの集合に含3.

まれるものとする．

LCS を用いた Web ページ推薦|lcsi ∩ actn | · cαi(1)lcsi ∈ LL

本節では，2 節で説明した手順でアクセスログから

α は ci の重みであり，Web サイトの特徴からその影抽出される LCS を用いたユーザにページを推薦する

響度合いを考慮して適切に調節する．

手法11) について説明する．

3.2

抽出された LCS とアクティブセッションのマッチ

ページ推薦手法 WRAPL-FL 法

以下の手順で推薦ページの決定を行う．

ングを行って推薦候補ページを選出する．次に，それぞれのページに得点を付加することで，推薦のための優先順位を決定し，その得点が上位のページから順に(1)lcsi と actn の間で共通するページを抜き出す．

(2)

lcsi より，一番目から共通部分の最後までの要素全てを除去する．

推薦する．
3.1

X

point( p) =(3)

推薦候補ページの選出と得点付け

残ったページを推薦ページの候補とし，そのそれぞれの point に |lcsi ∩ actn | · cαi を加える．

LCS を用いた Web ページ推薦手法では，アクセス(4)

ログから抽出した LCS のそれぞれと，現在までのユー

LL の中の全ての要素に対して（ 1 ）∼（ 3 ）を行い，候補ページの中で得点の総和が上位のペー

ザのセッション (アクティブセッション ) とのマッチンジを推薦する．

グを行い，頻出 LCS の中で，ユーザの現在位置以降

ここまでで述べた，LCS を用いた推薦手法の概要に現れているページを推薦する．

を図 1 に示す．例えば ，ページ推薦のステップにお抽出された LCS の内，全セッション中において数え

いて，図のように act3 = (A, B, C) が与えられた時，上げられた回数が閾値 min.Count 以上であり，かつ長
- 3-
































    


















 








q
s

v 










}~
p o o



   yz {tvu w x









n m m

q

q

v 

q

q

q


q
q

|

q

q



q

q

q

q




j kl i,a bdcfe g h ] ` \_ [ Y Z ^ Z Y X

J@KBL
E H F G DI CTVUBWO R P Q NSM




r

図1

     "!#   !$ "/ 0132 4 5 . + * )>@?BA
8 < 9;: 7 = 6q %&('      LCS を用いた推薦

lcs1 = (A, B, C, D, E) と一致する部分は (A, B, C) であンも除外した結果，URL 数は 174，総セッション数はり，それに続くページ D, E が推薦の候補ページに加23,663 となった．

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

全セッションの内，時期が早い方の 75%を学習セッ(A, B, C) が一致するものの，共通部分の最後のページ

トとして，そこから各手法ごとに頻出パターンを抽C 以降に続くページはないため，ここから推薦候補に出した．残りの 25%の新し いセッションの集合をテ加えられるページはない．さらに，lcs3 = (B, C, E) で

ストセットとみなしてページ推薦を行い，その評価をは E となる．したがって，この例で lcs1 〜lcs3 から推行った．

薦されるページの候補は {D, E } となる．

評 価 に 用 い る 指 標 とし て ，以 下 に 定 義 さ れ る

ここでは，ページ E が 2 つの LCS で推薦候補となっprecision と coverage を用いる．

|Recom ∩ eval||Recom||Recom ∩ eval|coverage(Recom) =|eval|ている．したがって，各 LCS から算出された得点のprecision(Recom) =和がページ E の得点となる．
4.

推薦精度評価のための準備(3)

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

我々は，LCS を用いた推薦手法 WRAPL-FL 法の有ションから導かれた推薦ページの組，対象アクティブ

効性を確認するために，実際のアクセスログを使ってセッションに引き続いて実際にアクセスされたページ

実験を行い，その効果を測定すると共に，1 節で紹介の組（評価セット ）を表す．precision は推薦の正確性した Mobasher らが提案している apriori アルゴ リズムの指標であり，推薦されるページ数に対する正解ペー

によって生成される相関ルールを用いた推薦手法を簡単化した手法を実装し ，その推薦精度を比較した11) ．
本節では，実験対象として用いたデータの説明と評価
指標の定義，さらに比較手法の詳細について説明する．
4.1

(2)

ジ数の割合で表現される．また，coverage は評価セッ
トをどれだけ網羅しているかの指標であり，評価セッ
トのページ数に対する正解ページ数の割合で表現される．
ページ推薦を行うために，テストセットの各セッショ

実験対象データと評価指標

ン（テストセッション）のはじめの n ページをアクティ

実 験 対 象とし て ，The Internet Traffic Archive

ブセッション actn とみなして large LCS 集合 LL 中の(http://ita.ee.lbl.gov/) で配布されているいくつかの Web

全要素とマッチングを行う．そこから推薦ページのラ

サイトのアクセスログの内，NASA の Web サイトでンク付けを行って上位のページを推薦し，そのセッショの 1995 年 8 月 1 日から 8 月 31 日までの Web サーバ

ンの残りのページ eval と比較することで precision とへのリクエストに対するアクセスログを用いた． この
データにはセッション情報が含まれていなかったため，同一 IP アドレスからのアクセスを同一ユーザからのcoverage を求めた．
4.2

比較手法

相関ルールを用いた Web ページ推薦手法8) では，長アクセスとみなし，ページアクセスの間隔が 1,200 秒

さ n のアクティブセッション actn が与えられると要素以上のときにセッションを分割した．ログ全体の中に数 n + 1 の頻出アイテムセットを探索し，アクセスさ出現した固有 URL 数は 1,276 で，総セッション数はれた n 個のページを全て含むアイテムセットから，差

39,900 であった．ここで，各 URL のログへの出現頻分のページを推薦するという手法が提案されている．

度には大きな偏りがあったため，各セッション中の出

これは，ページの組 {A,B}，{A,B,C} がそれぞれ頻出ア

現割合が 0.5%に満たない URL を取り除き，さらに推イテムセットに含まれる時，{A,B,C} の共起頻度が高薦の評価に利用できないため長さが 3 以下のセッショ- 4- ければ，{A,B} へのページアクセスに引き続いて C へのアクセスが起こる確率も高くなるという仮定に基づ')(+*-,/.02143')(+*-,/.053')(+*-,/.02643
7+8 ,9.:02143
7+8 ,9.:053
7+8 ,9.:02643

いている．また，アクティブセッションの長さである
 

n の値を，推薦ページが見つかるまで下げていくとい

&

"$%
$" #

う方法で coverage を上げている．



いため，condence 値で順位付けを行うこととする．



LCS を用いたページ推薦手法に対する解析

5.


!

この手法では，推薦ページの順位付けを行っていな

我々は本稿の事前検討として，前節の設定で実験を



 



行ったが，比較手法の相関ルールを用いた Web ページ推薦手法の文献内で提案されている全ての改善内

図2

LCS を用いた手法と比較手法による推薦の評価

容を実装していなかったため，今回機能を追加して改めて比較を行った（ 5.1 節）．その結果，WRAPL-FL

るページ推薦の精度について，比較手法に比べ，LCS

法の優位性は実証できたが，アクティブセッション長を用いた手法で良い結果が得られていることが確認でが短い場合で長い場合に比べて良いという，予想に反きる．

する結果が得られた．そこで，本稿ではその原因につしかし，一般にアクティブセッション長 n の値を大いて解析を行うため，以下の 3 点に着目した．

きくするほど履歴から抽出されたパターンとの一致の• 今回対象とした Web サイトでは，セッション長

度合いが大きくなり，precision は改善するはずであるが，図 2 から，n が大きいものに比べ小さいもので良が短いものが大部分を占めていた．

• アクティブセッションと LCS とのマッチングにい結果が得られたことがわかる．
テスト セッション長を固定した場合の比較

おいて，一致要素数が 1 の LCS も判断材料とし5.2て用いている．

今回対象としたサイトでは，セッション長ごとのセッ• 推薦順位の決定において，LCS の出現回数とアクション数に大きな偏りがあった．セッション長が 3〜9

ティブセッションとの一致要素数のみを考慮してのテストセッションの数は順に，3189，1834，1139，

いる．

717，500，354，217 という分布になっており，短いア

これらが推薦精度に与える影響を調べるために，5.2

クセスでセッションを終えるユーザが多く，長いセッ

節〜5.4 節では実験の条件を変更して詳細な解析を行

ションの数が相対的に少なかった．

い，LCS を用いた推薦手法の特徴について調査する．

長さ n のアクティブセッションから推薦を行う際にさらに，5.5 節ではそれらから得た知見を利用し ，推は，テストセッション長が n + 1 以上である必要があ

薦精度の改善を目指す．
5.1

ることから，調査の対象となるテストセッションに差LCS を用いた手法と比較手法による推薦精度が生じ，その結果等しい条件で比較が行えなかった可の比較能性がある．そこで，ここではまず，テストセッショ

実験に用いたパラメータは，比較手法では一定の最ン長を固定して実験を行うことで，可能な限り近い条

小サポート値 0.008 を用い，要素数が 1 から 5 の頻出件で推薦精度の比較を行うことを考える．

アイテムセットを生成した．LCS を用いた手法では，

4.1 節と同様のデータに対し ，テストセッション長

min.Count を 150，min. Length を 3 として LL を作成

を 6 に固定した場合の結果を図 3 に示す．凡例中の n

し ，推薦ページの得点付けの式（ 1 ）は α = 12 の場合

は，アクティブセッション長を表している．上の 3 つを用いた． それぞれについて推薦精度を測定した結果(xed) が固定長 6 のテストセッションを用いた場合，を図 2 に示す．図中の LCS，AR はそれぞれ，LCS を

下の 3 つがテストセッション長を固定しない場合の結用いた手法，比較手法を用いた推薦に対応しており，果である．

n はアクティブセッションの長さを表す．また，図に図から，n = 2, 3 の場合には大きな差は見られない

おける各点は，推薦する上位ページの数 |Recom| を 1

が，n = 4 の場合で精度が低下しているため，テストから 14 の間で変化させた場合に対応しており，右のセッションの差は精度に影響を与えていることがわか

点ほど |Recom| が大きい場合を表している．

る．しかし， 近い条件下で精度を比較した場合にも，
n が小さいアクティブセッションからの推薦でより良

図 2 から，同じ長さのアクティブセッションに対す- 5- 

'(*),+.-0/21,34'(65+.-0/21,34'(*7,+.-0/21,34
'(*)
'(65
'(*7


 
&

"$%
$" #


!


 )6.,430)7.,/510)83,/590

$&'
&$ %


"#
!













 











 



図 5 アクティブセッション中にのマッチ位置による比較

れは，act2 と LCS のマッチングにおいて，act2 との一
 )+*-,

致要素数が 1 である LCS が全体の約 25%を占めてい)+*/.

るのに対し，一致要素数が 2 である LCS は 2%弱にと)+*-0

どまっていることに起因すると考える．一方，n = 3, 4(の結果ではほぼ全体的に，一致要素数 1 を含める場合

!

に比べ，精度の向上が確認できた．したがって，n が

大きい場合には，一般的な傾向に当てはまり，マッチ


図 3 テストセッション長を 6 に固定した場合の比較"#)2*-,430)+*-,/510

(



$&'
&$ %

)+*-,/.10の度合いが高い LCS が精度向上に影響を与えていることがわかる．








 



5.4

アクティブ セッション中のマッチ位置による比較

5.3 節のおわりで触れたように，今回対象とした Web

図 4 一致要素数が 1 のものを除いた場合の比較

サイトは規模が大きく，ユーザのアクセス行動も非常に多様であるため，アクティブセッションとの一致要い結果が得られるという傾向は変わらなかった． また，テストセッション長を 5，7 に固定した場合でも，素数が多い LCS は非常に少ない．そこで本節では，そ同様の傾向が得られた．

の中で，アクティブセッション中のどの部分が LCS と5.3

一致要素数が １の LCS を除いた場合の比較一致するとき，より精度の高い推薦が行えるかについ

WRAPL-FL 法では，図 1 中の lcs3 と act3 とのマッて調査することによって，推薦精度に与えるマッチ位

チングの例からもわかるように，一致要素数が 1 の場

置の影響を検討する．

合（つまり |lcsi ∩ actn | = 1 の場合）にもそれに続く推これまでは，テストセッションのはじめの n ページ

薦候補を選出し，得点付けを行っている．

を actn とみなしてページ推薦を行い，そのセッション

しかし，一致要素数が 1 の場合，アクティブセッショの残りの部分 eval と比較することで precision と cov-

ンと過去のパターンとのマッチ度が低いため，推薦精erage を求めてきた．しかし今回は，セッション前半

度に悪影響を与えてしまう可能性がある．そこで，一のどの部分が後半ページとの関連が深いかを調査する

致要素数が 1 の場合には得点は付加しないものとしたために，テストセッション中のはじめの 4 ページの中上で，同様に精度を測定する実験を行った．

から任意の 2 ページの全ての組み合わせを順序を変え結果を図 4 に示す．図から，一致要素数が 1 の場合ずに取り，それらに対し 5 ページ目以降の部分を評価

を判断材料から取り除くと，アクティブセッションを

セット (eval) として推薦精度を測ることとする．

長く取った場合で，短い場合に比べて良い結果が得ら

結果を図 5 に示す．凡例中の (a, b) はそれぞれ，はれることが確認できる．

じめの 4 ページ中の a，b 番目のページを順に 2 ペー

精度の順番が逆転する要因として，n = 2 のときに，ジ取り，act2 とみなした場合の結果に対応している．

一致要素数 1 も含めて推薦を行った場合に比べて精度

図より，推薦精度は (3, 4) の場合で最も良く，以下

が大きく低下していることが挙げられるであろう．こは順に (2, 4)，(1, 4)，(2, 3)，(1, 3)，(1, 2) となっている
- 6-

考

察

ことが確認できる．この結果から明らかに，アクティ

5.5.3

ブセッションの後方のページがユーザの今後のアクセ

図 6〜8 のように，得点付けの式において，li の重ス行動と深いかかわりを持つことがわかる．したがっみ（ = β ）をかなり大きくしても精度は向上する．従って，推薦を行うための履歴として用いるページの中でて，今回対象としたサイトでは，アクティブセッショ

は，前方のページに比べて後方のページを重視すべき

ン中で後方に現れるページはその後のアクセスに対しである．

て大きな関連性を持つことがわかる．

5.5

アクティブセッション中の LCS とのマッチ位

また，図 2，6〜8 より，同じ長さのアクティブセッ

置の考慮ションから推薦を行った場合，相関ルールによる推薦

5.3，5.4 節で得られた特性を利用して，アクティブに比べ提案手法が優れていることがわかる．このことセッションと LCS とのマッチングを行う際に，それから，相関ルールを用いて共起頻度のみを考慮するよらのマッチ位置を推薦ページの優先順位付けに反映さりも，順序情報を用いた方が，より正確な推薦を行う

せる方法を提案する．

ことができると考える．

5.5.1

マッチ位置を考慮した得点付け

WRAPL-FL 法を用いて推薦ページの優先順位付け

lcsi と actn とのマッチングの際に，アクティブセッを行った場合に比べ，WRAPL-FLP 法を用いた場合にション中におけるマッチ位置を考慮するために，次のはその差は狭まるものの，やはりアクティブセッショ

ようにマッチ位置重み li を定義する．前述のように，アン長を短く取った方が推薦精度が良い．一方で，アククティブセッションとのマッチ位置が後方にある LCS

ティブセッションとの一致要素数が 1 の LCS を除いの方がより重要であるため，li は後方ページが重視さた場合にアクティブセッション長が長いもので良い結れるように設定する必要がある．

果が得られた．このことから，今回対象とした Web

そこで，actn と lcsi を比較し ，actn の m ページ目

サイトでは，直前のアクセスページ（実際にリンクがが lcsi とマッチした場合，li に m を加算する．例え張られているページ ）からの推薦が最も精度が良いとば ，act4 = (A, B, C, D)，lcsi = (B, D, E) のとき，act4

いう特徴があると考える．現在この Web サイトは存中の 2,4 番目のページ B と D が lcsi と一致するため，在しないためリンク構造等を解析することはできない

li = 2 + 4 = 6 となる．

が，ページ配置が細分化，階層化されており URL 数

このようにして得られた li を，WRAPL-FL 法によが非常に多く，また短いセッションが非常に多いこと

る推薦ページの優先順位付けの式（ 1 ）に掛け合わせるから考えて，目的のページまで迷わずにナビゲートをことで新たな得点付けの式を以下で定義し，これを用するユーザが多いためにこのような傾向が現れると推いた推薦手法を WRAPL-FLP（ Web page Recommen-

測する．

dation by Access Pattern Lcs with Frequency, matched

6.

Length and Position based weighting ）法と呼ぶ．
point( p) =X

|lcsi ∩ actn | · cαi · liβ

本稿では，アクセスログ解析によって抽出した LCS(4)lcsi ∈ LLを用い，ユーザの過去のアクセス行動からそれに続く

ただし，β は li の重みである．
5.5.2

おわりに

アクセスページを推薦する手法である WRAPL につい

WRAPL-FLP 法による順位付けの評価

WRAPL-FLP 法による改良の有効性を確認するため，
LCS を用いたページ推薦手法において，推薦ページのて解析を行った．
実際のアクセスログを用いて，その一部から LCSを抽出し，残りのログに対して WRAPL-FL 法を用い

優先順位決定に，WRAPL-FL 法，WRAPL-FLP 法をて推薦するシミュレーションを行った．その際，条件用いた場合の推薦精度の比較を行った．

を限定して実験を行うことにより解析し，手法の問題

図 6〜8 はそれぞれ，長さ n のアクティブセッショ

点や改善点について検討した．さらに，それらから得ンからのページ推薦において，WRAPL-FLP 法を採用た知見を活かして推薦ページの優先順位付け方法を改した場合の結果を表している．凡例の β は，式（ 4 ）に良した WRAPL-FLP 法を提案し ，それによって推薦おける一致位置に応じた得点 li の重みを表す．すなわ

精度が向上されることを確認した．

ち，β = 0 は WRAPL-FL 法に対応している．

本研究の今後の課題について述べる．まず，本研究グラフより，アクティブセッションにおける LCS との最終的な目的は，Web サイトの利用者に対し，リアのマッチ位置を考慮することで，結果が改善されるこ

ルタイムに Web ページを推薦することであるため，今とが確認できる．

後は，計算量の見積もりや他手法との比較，さらに，- 7-


)+*-,
)+*/.
)+*10
)+*-2
)+*-3


 
(

$&'
&$ %

 
(

$&'
&$ %


"#


)+*-,
)+*/.
)+*10
)+*-2
)+*-3



!

 
(

$&'
&$ %


"#


"#

!

!























 



)*,+
)*.)*0/
)*,1
)*,2











 





図 6 一致位置の考慮による改良 (n=2)

図7





 



一致位置の考慮による改良 (n=3)

計算量を削減するための手法についても検討する必要

図8

一致位置の考慮による改良 (n=4)5) Mobasher, B., Cooley, R. and Srivastava, J.: Creating Adaptive Web Site Through Usage-Based Clus-がある．

tering of URLs, Proc. of the 99 Workshop on Knowl-

今回のシミュレーションで採用した評価方法では，edge and Data Engineering Exchange, pp. 1925

アクティブセッションより後にアクセスされたページ(1999).

全てを正解としたため，サイト内で実際にリンクが張6) Srikant, R. and Yang, Y.: Mining web logs to im-られており，直後にアクセスされやすいページを推薦

prove website organization, Proc. 10th Intl. Conf. on
WWW, pp.430437 (2001).

し ，それが正解とされるケースが多かった．しかし ，

7) Pitkow, J. and Pirolli, P.: Mining longest repeating

階層化された商業サイト等でコンテンツページを優先

subsequences to predict WWW, Proc. of the 1999

的に推薦する場合においては，サイト構造における深USENIX Annual Technical Conf. (1999).

さなどを考慮すべきであると考える．したがって，正8) Mobasher, B., Dai, H., Luo, T. and Nakagawa, M.:

解ページにも優先順位を付け，それに応じて評価する

Effective perssonalization based on association rule

等，目的に合わせて評価方法も工夫すべきであろう．

discovery from web usage data, Proc. 3rd Intl. Workshop on Web information and data management, pp.

さらに，Web サイトの規模や構造の違いによりユー

915 (2001).

ザのアクセスパターンに異なる傾向がある場合，それ宇根田純治，横田治夫：Web ログの共通シーケ
ンス解析，信学技報 DE2002-2，電子情報通信学会 (2002).
10) 戸田誠二，横田治夫：LCS を用いたアクセスログ
解析の並列処理による性能向上，第 13 回データ工学ワークショップ論文集, DEWS2004 7-B-5 (2004).
11) 山元理絵，小林 大，小林隆志，横田治夫：Web
アクセスログの LCS を用いた Web ページの推薦手法，信学技報DE2006-40，電子情報通信学会
9)に適した推薦ページの優先順位付けの方法について再考する必要がある．本手法を他の Web サイトに適用
し，サイトの特徴と推薦精度の関連性を調査することも今後の課題である．
謝辞 本研究の一部は，文部科学省科学研究費補
助金特定領域研究 (18049026)，東京工業大学 21 世紀
COE プログラム「 大規模知識資源の体系化と活用基盤構築」および独立行政法人科学技術振興機構戦略的(2006).
12) Banerjee, A. and Ghosh, J.: Concept-based cluster-

創造研究推進事業 CREST の助成により行なわれた．

ing of clickstream data, Proc. 3rd Intl. Conf. on In-

参 考 文

献

formation Technology, pp.145150 (2000).
13) Cormen, T. H., Leiserson, C. E., Rivest, R. L. and1) Eirinaki, M. and Vazirgiannis, M.: Web mining for

Stein, C.: Introduction to Algorithms, MIT Press

web personalization, ACM TOIT, pp.127 (2003).
2)(1990).

土方嘉徳：情報推薦・情報フィルタリングのためのユーザプロファイリング技術，人工知能学会
誌， Vol.19, No.3, pp.365372 (2004).

14) Wu, S., Manber, U., Myers, G. and Miller, W.:
An O(NP) sequence comparison algorithm, Information Processing Letters, Vol. 35, No. 6, pp. 3173233) Agrawal, R. and Srikant, R.: Fast Algorighms for(1990).

Mining Association Rules, Proc. of 20th Intl. Conf.
on Very Large Data Bases, pp.487499 (1994).
4) Sarawagi, S., Thomas, S. and Agrawal, R.: Integrating association rule mining with relational databasesystems: alternatives and implications, Proc. of ACM
SIGMOD Intl. Conf. on Managgement of data, pp.
343354 (1998).
- 8-E