JP4273300B2

JP4273300B2 - Ｗｅｂアクセスログ解析方法

Info

Publication number: JP4273300B2
Application number: JP2002319293A
Authority: JP
Inventors: 治夫横田; 純治宇根田
Original assignee: Tokyo Institute of Technology NUC
Current assignee: Tokyo Institute of Technology NUC
Priority date: 2002-11-01
Filing date: 2002-11-01
Publication date: 2009-06-03
Anticipated expiration: 2022-11-01
Also published as: JP2004152209A

Description

【０００１】
【発明の属する技術分野】
本発明は、Webサイトへのアクセスログの解析方法に関し、特に、Longest Common Subsequence（LCS）アルゴリズムを用いたWebアクセスログ解析方法に関するものである。
【０００２】
【従来の技術】
現在、Webサイトは広報・広告・マーケティングの手段として極めて重要な位置を占めている。Webサイトを開設し企業情報・商品情報を発信することはもはや企業の発展にとって必要不可欠な要件である。
【０００３】
現在は情報が氾濫している時代であり、ユーザは無数にあるWebサイトから自分の望む情報を効率良く獲得しようとする。もし、サイトの構成が悪くユーザに必要な情報が不透明であればユーザは即座に情報探索をあきらめ次のサイトヘ移ることになる。
【０００４】
このような状況の中で、Webサイトヘのアクセス状況を的確に把握し発信したい情報が受け手に確実に届いているかどうかを見極めることはWebサイト管理者の最も重要な仕事の一つである。その手法の一つとしてWebのアクセスログ解析がある。管理者はアクセスログの解析結果から取り出す情報を意思決定材料として、ユーザのニーズにあったサイト構築を行うことができる。
【０００５】
従来のアクセスログ解析のアプローチには、ページ別アクセス頻度、時間別、期間別アクセス頻度、訪問者の使用しているOS、ブラウザの種類の集計、Webサイトのアクセス元の集計などが存在する。これらの解析手法によってサイト管理者はアクセス頻度の高いページ、時間帯別アクセス状況、自サイトへのアクセス元などを知ることができる。これらの情報も管理者にとって重要な要素の一つであるが、それだけでは訪問者がどのようにサイトを巡回する傾向にあるのか判断できない。
【０００６】
すなわち、これまでのアクセスログの解析は、ユーザが通った（部分）ルート（URLの推移）が同一であるかどうかの判定はできるが、似たルートの中で、よく現れる共通パターンを抽出しては来なかった。
【０００７】
あるルートα＝（ａ１，ａ２，ａ３，…，ａｎ）について、ルート（ａｉ，ａｉ＋１，…，ａｊ）（１≦ｉ≦ｊ≦ｎ）を満たすものを部分ルートと呼ぶが、長さｎのルートに関してはｎ（ｎ−１）／２通りの部分ルートが存在する。部分ルートの統計からは、ある二地点間、三地点間における推移の頻度や、ノードの独立性の高さ、ページ間の推移の頻度も分かる。これらの情報を統合すれば、ある程度ユーザのたどるアクセスルートのパターン( 以下、「アクセスパターン」という。 )を知ることはできる。
【０００８】
しかしながら、多くのWebサイトではユーザが欲しい情報を探索している場合に、ページ間の移動を頻繁に行いサーチとバックトラック操作を繰り返すのが一般的である。その際に残されるアクセスログは必ずしも連続性を持った情報ではない。ユーザがサーチを行った結果として残されるログは、サーバへリクエストされたものであり、すでにユーザ側にファイルのキャッシュがあれば当然ログとしては残されない。
【０００９】
バックトラックポイントの説明として例を示す。図５のようにな階層構造をもったサイトをあるユーザのサーチした結果に残されたログが（A1,B1,C1,C2,B4）であったとする。このとき、ブラウザのキャッシュ機能を考慮に入れれば、このユーザが実際にサーチしたルートは（A1,B1,C1,B1,C2,B1,A1,B4）となるはずである。ここではバックトラックポイントはユーザの情報探索中に元来たノードへ戻る折り返し地点のことを指す。この例では（C1,C2）の２点がバックトラックポイントである。
【００１０】
このように、一般的にサーチ時に様々な寄り道はつきものである。すなわち、部分ルートからだけでは単純に２地点間のつながりの深さを知ることはできても、ユーザの一連の操作である真に頻出のアクセスパターンを見つけることは困難である。
【００１１】
以下、Webのページ構造を簡単化のためにリンクによる木構造にみたて（本来は、リンクによるグラフになっている）、ページに番号をふって説明を行う。根から深さを増すごとにA,B,C,D,Eとし、同じ深さのページに関して木の左から右へB1,B2,B3とする。
【００１２】
例えば、二人のユーザを想定して、それぞれのユーザのあるWebのアクセスルートが、ルートβ（A1,B1,C1,D1,E1）とルートγ（A1,B1,C2,D1,E1）であったとすると、従来の技術では、この二つのルートはまったく別なルートとして集計されることになる。
【００１３】
しかし、Webの構成を考える上では、二つのルートの中で、A1,B1,D1,E1が共通であるという情報は重要である。
【００１４】
これまで、アクセス頻度の高いページ間のリンクを可視化して表現する等の手法はあったが、それでは頻出の共通ルートを抽出することはできない。
【００１５】
具体的には、大浦らによる、特定の問い合わせサイトにおいて、ユーザセッションのクラスタ化により問い合わせ拡張支援を行う手法についての実験報告がなされている（例えば、非特許文献１参照。）。これは、サイト内のページをアイテムとするセッションベクトルを用いてクラスタリングし、関連性の高いアイテムを分析する手法である。この手法はYahoo！などの検索サイト、あるいはAmazonなどの問い合わせサイトといった、インデックスページとコンテンツページが明確に分かれており整然とした階層構造を持ったWebサイトにおいて非常に有効であった。しかし、インデックスページとコンテンツページが混在する一般的なサイトでは、セッションベクトルとすべきアイテムのレベルが並列ではなく、一般的に決めることが困難である。また、アクセスログのみを用いて解析を行うツールと比較すると解析の前処理のコストが大きい。
【００１６】
又、ユーザのクリック操作のビジュアル化を目的とする様々なツールを用いて視覚的にWebサイトのアクセス状況を示し、解析、改善を支援する研究も多数報告されている。アクセスログを２次元グラフで表現しユーザのアクセスパターンを視覚化する研究、ユーザの頻出操作パターンを発見するためのマイニングシステムの研究などが行われている（例えば、非特許文献２，３，４，５参照。）。
【００１７】
Webサイトの再構成の研究ではRamakrishnan等（例えば、非特許文献６参照。）によるユーザのターゲットページまでのバックトラックポイントの減少を目的とする解析手法が提案されている。しかし、ユーザ操作はランダム性に富み、操作状況やネットワークの状態が完全にユーザごとに異なるため、アクセスログのみからバックトラックポイントと目的のページを区別することは容易ではない。
【００１８】
【非特許文献１】
大浦勇亮、喜連川優：Webアクセスログのクラスタリングによる問い合わせ拡張に関する検討：ｉタウンページ上での実験、電子情報通信学会データ工学ワークショップ DEWS, A2-1,2002.
【００１９】
【非特許文献２】
Bowo Prasetyo, Iko Pramudiono, Katsumi Takahashi, Masashi Toyoda, Masaru Kitsuregawa: “Naviz: User Behavior Visualization of Dynamic Page”, 電子情報通信学会データ工学ワークショップ DEWS, C5-3,2002.
【００２０】
【非特許文献３】
Pitkow,J. and K. Bharat. WebViz: “A Tool for World-Wide Web Access Log Analysis”, In Proceedings of First International Conference on the World-Wide Web 1994.
【００２１】
【非特許文献４】
M.Spiliopoulou and L.C.Faulstich: “A Web Utilization Miner”, In Proc. of EDBT Workshop WebDB98,Valencia,Spain,1998 Springer Verlag.
【００２２】
【非特許文献５】
Cugini,J. and J.Scholtz: “VISVIP:3D Visualization of Paths through Web Sites”, In Proceedings of International Workshop on Web-Based Information Visualization (WebVis’99)., pp.259-263. IEEE Computer Society, September 1-3 1999.
【００２３】
【非特許文献６】
Ramakrishnan Srikant, and Yinghui Yang,: “Mining Web Logs to Improve Website Organization”, ACM 1-58113-348 pp.430-437 ACM, May 2001.
【００２４】
【発明が解決しようとする課題】
本発明は、かかる従来技術の問題点に鑑み為されたものであり、Webアクセスログを基にして、訪問者（ユーザ）ごとのセッションにおいてアクセスされたＵＲＬの推移、すなわちユーザのアクセスルートを解析し、ユーザのアクセスシーケンスの高頻度なパターンを把握する方法を提供することにより、Webサイトの管理者がサイトの構成上の問題点を的確に知り、Web構成の改善や、Webの広告配置の戦略の策定等に利用することができるようにすることを目的とする。
【００２５】
【課題を解決するための手段】
本発明は、プログラムされたコンピュータによって、 Web アクセスログに基づいてユーザのアクセスパターンを解析する Web アクセスログ解析方法に関し、本発明の上記目的は、前記コンピュータが、前記 Web アクセスログから Web ページ間の移動情報を構成するために必要なリクエストファイル以外のファイルを取り除いてから各ユーザのセッション毎のアクセスルートを求めるとともに、前記 Web の構成と比較して明らかにシーケンスになり得ないアクセスルートを解析対象から取り除く処理（以下、「前処理」という。）を前記プログラムによって行うステップと、前記前処理で求めた各ユーザのセッション毎のアクセスルートの中から選んだ任意の二つのアクセスルートについて、ＬＣＳアルゴリズムを用いて前記二つのアクセスルートに共通するアクセスパターンを前記プログラムによって抽出するステップと、前記前処理で得られたすべてのアクセスルートについて前記ＬＣＳアルゴリズムを用いて抽出した共通するアクセスパターンのうち、最も頻度が多いものを頻出アクセスパターンとして前記プログラムによって抽出するステップとを具備することによって達成される。
【００２６】
前記前処理のステップにおいて、前記Ｗｅｂページ間の移動情報を構成するために必要なリクエストファイルの一例としてはＨＴＭＬファイルが挙げられる。
【００２７】
【発明の実施の形態】
本発明は、多くのユーザがアクセスするWebサイトにおいて、その構成をユーザのアクセス履歴を基に改善する手法に関して、ユーザのアクセスログの解析にLongest Common Subsequenceアルゴリズムを用いることで、従来不可能であったアクセス履歴の頻出パターンを抽出し、より効率のよいWebの構成を可能にするためのものである。
【００２８】
従来、遺伝子構造の解析などでは、頻出パターンを検出するためにLongest Common Subsequence(LCS)アルゴリズムがよく用いられている。しかし、これまでLCSはWebのアクセスログ解析には用いられてはこなかった。
【００２９】
リストxの部分系列zとリストyの部分系列zのなかで両方のリストに共通に含まれるものを共通部分系列（Common Subsequence）という。共通部分系列のなかでもっとも長いものを最大共通部分系列という。最大共通部分系列は英語では、Longest Common Subsequenceと呼ばれ、頭文字をとってLCSという。例えば、X＝(A,F,B,D,E)とY＝(A,B,C,D,E)のLCS(X,Y)は(A,B,D,E)である。なお、(A,B,C)とは、あるユーザが、A、B、Cという順にWebサイト内のページをアクセスしたときのアクセスルートを表すものとする。
【００３０】
一般的なLCS計算アルゴリズムを数１示す。系列XiとYjのLCSの長さをC[i,j]に格納する。
【００３１】
【数１】

ここでconstract()はC[M,N]からLCSを構成するアルゴリズムであるがここでは省略する。LCSアルゴリズムは、Mの文字列とNの文字列の計算量はO(MN)時間で解くことができる。
【００３２】
２つのリストの中に同じ要素が同じ順序で出現したものが共通部分系列なので、最大共通部分系列(LCS)が長いということは、２つのリストの類似性が高いと解釈できる。例えば、上の例ではXとYのLCSの長さは４である。両方の文字列の長さに対してこの長さは十分に大きい。
【００３３】
よって２つのリストは類似性が高いと判断できる。LCSの特徴として、実際に(A,B,D,E)というリストはX，Yともに連続して出現しておらず部分列として出現していることがあげられる。つまり、連続していなくとも類似性が高ければ共通シーケンスとして拾って来ることができる。
【００３４】
この発明の着眼点は以下の通りである。すなわち、Webサイトをアクセスする場合、目的とする情報を含むページに行き着くまでに試行錯誤を行うことになるが、そのパスはユーザごとに異なる。しかし、多くのユーザで共通するパターンも存在することは容易に想像できる。共通する部分を切り出すことでユーザの動向を判定し、例えば一連のアクセスの中で共通しない部分が構造として不適当であると判断することも可能となる。
【００３５】
以下、図面を参照して、本発明について詳細に説明する。
【００３６】
図１は本発明の概念を示す図である。
【００３７】
ユーザ１はインターネット２を介してWebサイト３にアクセスし、希望するWebページ４を閲覧するが、ユーザによってアクセスするページやそのアクセス順序が異なる。そこで、複数のユーザ１が利用するWebサイト３において、そのユーザのアクセスログを取得し（１０）、解析を行う場合に、LCSアルゴリズムを適用することで、アクセス履歴の頻出パターンを抽出し、より効率のよいWebの構成に改善することが可能となる（３０）。なお、アクセスログを解析する前段階の処理として、セッションIDを用いたユーザのトラッキングとWebの構造を前提としたデータ選択と精錬を行う。これをここでは「前処理」と呼ぶ（２０）。これは、多数のアクセスログにそのままLCSアルゴリズムを適用したのでは効率が悪いため、LCSアルゴリズムを適用する前にアクセスログに対して前処理を行い、効率を改善するためである。
【００３８】
図２は本発明に係る Webアクセスログ解析方法の全体の流れを示すフローチャートである。
【００３９】
まず、Webサーバにおいてユーザのアクセスログを取得し（ステップＳ１０）、後述の前処理を行い（ステップＳ２０）、ＬＣＳによる解析を行い（ステップＳ３０）、頻出アクセスパターンを抽出し、それを基にしてWebサイトの改善を行うものである（ステップＳ４０）。
【００４０】
次に、前述の「前処理」について詳細に説明する。
【００４１】
まず、前処理の手順を説明する前に、前処理の基本となる「セッションIDを用いたユーザのトラッキング」と「データ選択と精錬」についての考え方を説明しておく。
【００４２】
（1）アクセスログの前処理
Webの一般的なアクセスログは、一例として
『210.72.28.xx--[13/Jan/2002:06:35:37+0900]”GET/^~yokota/index.html…』のようになっており、“IPアドレス”、“アクセス時刻”、“リクエストパス”、“リモートホスト名”、“使用しているOSおよびブラウザの種類”、“ドメイン名”などが情報として含まれている。更に、リファレンス情報やCookie ID等も含まれることもある。
【００４３】
（1-a）セッションIDを用いたユーザのトラッキング
訪問者がどのようにサイト内を巡回したかという情報を得るためには訪問者ごとのリクエストURLを一つのまとまった集合としてユーザごとのクリックストリームに整理する必要がある。このためIPによってユーザを区別することになるが、それだけではプライベートIPのアクセス先から複数アクセスがあった場合に誰がアクセスしたかを区別することはできない。そこで、このIPを完全にユニークなものにするための技術であるセッションIDを用いる。
【００４４】
まずWebサイトの訪問者にはセッションIDというユニークなIDが割りあてられる。以下にセッションIDを用いた場合に残されるWebログの一例を示す。
【００４５】
『210.172.228.xx.234059345803948534--［13/Jan/2002:06:35:37＋0900］”GET…』
このセッションIDは、ユーザ側にクッキー（Cookie）として保存するか、またはURLに埋め込むかの二通りの手法がある。
【００４６】
クッキーを用いるのが最適であるが、ユーザ側で拒否される可能性を考えると信頼性はURLに埋め込む方が高い。これによりセッションサポート機能で任意の数の変数をリクエスト間で受取ることが可能となる。
【００４７】
セッションID 自体が有限な数の集合である以上、完全にユニークであるとは言い切れないが、確率的に事実上ユニークと考えても差し支えない。さらに、セッションが変わることでも異なるセッションIDが配布されるため同一ユーザからの時間をおいたアクセスの区別も可能となる。一般的に一つのセッションは同一ユーザから30分以上リクエストがない場合に別セッションとみなされる。
【００４８】
以上の技術を用いることによりIP別に整理されたパスの集合は個々の訪問者のとったクリックストリームとみなすことができる。本発明ではこれらのユーザセッションを単位として各LCSを計算していくことにより、ユーザのアクセスパターンを抽出する。
【００４９】
（１−ｂ）データ選択と精錬
必要なデータは、ユーザセッションごとの一連のリクエストＵＲＬである。そのため個々のユーザを区別するためのＩＰアドレスと使用ＯＳ、ホスト名、ドメイン名、また、アクセスルート抽出に用いるリクエストＵＲＬとリファレンスＵＲＬ、さらにルート構成と解析の際に重要となる各リクエスト時刻が必要である。これら素データはＷｅｂサーバのアクセス記録であるため、クライアント側の操作状況や使用ブラウザの機能、あるいはネットワークの状態によって欠損値が多く発生する性質を持っている。例えば、一つのユーザセッションとして複数のウィンドウを開いている場合には、セッションＩＤだけでは、アクセスシーケンスを追うことができない。ログ中のリファレンスＵＲＬを用いることでシーケンスを構成できる場合もあるが、Ｗｅｂの構成と比較して明らかにシーケンスになり得ないアクセスルートは、解析対象から取り除く必要がある。よって、より正確なアクセスルートを抽出するためには前処理として前述のような不必要なデータを除く必要がある。本発明では、この作業を「データを精錬する。」と呼ぶこととする。
【００５０】
以上を前提として、前処理の手順を図３に基づいて説明する。
【００５１】
まず、ユーザがWebサーバへアクセスした際、ログには様々な種類のリクエストファイルが残されているが、Webページ間の移動情報を構成するために必要なものはHTMLファイルのみであり、それ以外の画像ファイル、音声ファイルなどは必要としない。そこでHTML以外のリクエストファイルを除去する必要がある（ステップＳ２１）。
【００５２】
個々のユーザごとのセッションに分類するため前述したセッションIDを用いたユニークなIPアドレス、クライアントの使用OS、ブラウザ、ホスト名、ドメイン名等の情報から同一ユーザの特定を行う（ステップＳ２２）。この際に欠損値があるデータは質の悪いデータとして対象から外す。
【００５３】
ユーザを特定したら、そのユーザについてWebの構成と比較して明らかにシーケンスになり得ないアクセスルートを解析対象から取り除く、「データの精錬」を行う（ステップＳ２３）。データ格納後、ユーザのページ間の移動情報であるアクセスルートを抽出する。アクセスルートにはアクセス元であるリファレンスURLとアクセスしたページのURLの相互を補間させる。以上により、すべてのユーザについての精錬されたアクセスルートを抽出し、前処理を終了する。
なお、「 Web の構成と比較して明らかにシーケンスになり得ないアクセスルートを解析対象から取り除く、」であるが、これは、「シーケンスとなりうる」とコンピュータが自動的に判断したアクセスルート以外のものを「明らかにシーケンスになり得ない」ものとして排除する趣旨である。
具体的には、 Web サーバ上のページの構成を参照して、構成上アクセスされたページの間にリンクがある場合、または、直接のリンクが無くても、何段かのリンクの後にそのページにリンクされる場合には、その間がキャッシュされていて飛んでいると考え、やはり「シーケンスとなりうる」とコンピュータが判断する。
このように、構造的に何らかの（間があいていたりバックトラックしたりしても）つながりがあるような場合は、「シーケンスとなりうる」と判断するが、そうでない場合（構造上全く関係が無い程度に離れている場合）には、「明らかにシーケンスになり得ない」とコンピュータが判断する。
【００５４】
（2）LCSによるログ解析
次に、前処理された各ユーザのセッション毎のアクセスルートについてLCSアルゴリズムによる解析を行う。まず抽出した各アクセスルートをURL単位の列集合とみなす。そして各ルートごとに総あたり的にLCSアルゴリズムを適用し、全ての組合せのLCSの抽出を行う。作成したLCSテーブルについて各LCSの統計を行い、高頻度なアクセスパターンの特定を試みる。そのアルゴリズムは以下の数２のようになり、計算量はセッション数をSとするとO（S²）となる。
【００５５】
【数２】

なお、図４は本発明に係るＬＣＳアルゴリズムによるアクセスログ解析のフローチャートである。図中、ステップＳ３３のＬＣＳ計算は前述の数１のプログラムによって行われる。また、ステップＳ３７の集計は、前記数２のプログラムによって行われる。
【００５６】
例として、数３のような6セッションにより構成されたアクセスルート集合例（route［0］，…，route［5］）を考える。
【００５７】
【数３】

まず、route[I]とroute[J]の間において、I=0,J=1としてＬＣＳ計算を行う（ステップＳ３３）。それをＩ行Ｊ列のＬＣＳテーブルの（０行、１列）に格納する（ステップＳ３４）。本実施例では（A,C,E）となる。次に、J=2として（ステップＳ３２）、route[0]とroute[2]の間でＬＣＳ計算を行い、それをＬＣＳテーブルの（０行、２列）に格納する（ステップＳ３４）。本実施例では（A,C,D,E）となる。
【００５８】
このようにして、J=5まで計算を行うと、今度は、I=1として、J=0から5までのＬＣＳ計算を行い、ＬＣＳテーブルに格納する。以下、I=5まですべての組み合わせについてＬＣＳ計算を行う。
【００５９】
この例に対するＬＣＳテーブルは次の表１のようになる。
【００６０】
【表１】

次に、抽出した全LCSの集計を行う（ステップＳ３７）。これらをアクセスルートLCS集合と呼ぶことにする。上の例に対するアクセスルートLCS集合は、
｛（ACE，8），（AD，2），（ABCE，1），（ACDE，1）｝
となる。この例では（A，C，E）というLCSが最頻出であるという結果が得られた。しかし、実際にA→C→Eと連続してたどったルートはない。それにもかかわらず、（A，C，E）という頻出アクセスパターンが抽出されたことはLCSによるアクセスログ解析のもつ大きな特徴である。
【００６１】
次に、Webサイトの管理者はこの情報を基にして、Webサイトの改善計画を作成する（ステップＳ３８）。例えば、Web管理者が発信したい情報を含むページに誘導したい場合には、高頻度のＬＣＳ内にあるページ（上記の例ではA,C,Eのいずれかのページ）において、目的とするページへ誘導するリンク等を用意したり、シーケンスの間にそのページを含むように構成する方法が考えられる。また、ＬＣＳでグループ化されたページ群はアクセスされやすい一連のページであるため、そのいずれかのページに流れに沿ったバナー広告を置くことで、効率的にユーザの目に留めることができる。
【００６２】
【発明の効果】
これまでのアクセスログ解析で使われていた部分ルートでは分からなかったユーザのアクセス動向を抽出することが可能となり、Webサイトの構成をユーザの動向に合わせて最適化するのに有効な情報を得ることが可能となる。
【図面の簡単な説明】
【図１】本発明の概念図である。
【図２】全体の処理の流れを示すフローチャートである。
【図３】前処理のフローチャートである。
【図４】ＬＣＳ解析のフローチャートである。
【図５】ユーザのサーチ例を示す図である。
【符号の説明】
１ユーザ（訪問者）
２インターネット
３Ｗｅｂサイト
４Ｗｅｂページ

Claims

プログラムされたコンピュータによって、Webアクセスログに基づいてユーザのアクセスルートのパターン（以下、「アクセスパターン」という。）を解析するWebアクセスログ解析方法において、
該方法は、前記コンピュータが、
前記 Web アクセスログから Web ページ間の移動情報を構成するために必要なリクエストファイル以外のファイルを取り除いてから各ユーザのセッション毎のアクセスルートを求めるとともに、前記 Web の構成と比較して明らかにシーケンスになり得ないアクセスルートを解析対象から取り除く処理（以下、「前処理」という。）を前記プログラムによって行うステップと、
前記前処理で求めた各ユーザのセッション毎のアクセスルートの中から選んだ任意の二つのアクセスルートについて、ＬＣＳアルゴリズムを用いて前記二つのアクセスルートに共通するアクセスパターンを前記プログラムによって抽出するステップと、
前記前処理で得られたすべてのアクセスルートについて前記ＬＣＳアルゴリズムを用いて抽出した共通するアクセスパターンのうち、最も頻度が多いものを頻出アクセスパターンとして前記プログラムによって抽出するステップと、
を具備するものであることを特徴とするWebアクセスログ解析方法。
前記 Web ページ間の移動情報を構成するために必要なリクエストファイルがＨＴＭＬファイルであることを特徴とする請求項１に記載の Web アクセスログ解析方法。