(57)【要約】【課題】大量のＵＲＬからＵＲＬ情報のみを用いて、ページ単位に同様の内容を持つＷｅｂページをグループとして抽出する。【解決手段】本発明は、入力されたアクセスログからＵＲＬを抽出し、ＵＲＬを文字列と見做し、各部位毎に部分文字列として分割し、出現する部分文字列に基づいて、特徴ベクトルを生成し、特徴ベクトル間の類似度を求め、特徴ベクトル間の類似度に基づいてクラスタリングを行い、生成されたクラスタに含まれるＵＲＬをＷｅｂページグループとして抽出し、出力する。【選択図】図１
2010123000.tif 000002
【特許請求の範囲】
【請求項１】
アクセスログから、異なるＵＲＬであるが、同じＷｅｂページ、あるいは、同じ種類のＷｅｂページをグループとして抽出する方法であって、
アクセスログ入力手段が、入力された前記アクセスログからＵＲＬを抽出しＵＲＬ記憶手段に格納するＵＲＬ抽出ステップと、
文字列分割手段が、前記ＵＲＬ記憶手段から前記ＵＲＬを読み出して、該ＵＲＬを文字列と見做し、各部位毎に部分文字列として分割する文字列分割ステップと、
特徴ベクトル算出手段が、出現する前記部分文字列に基づいて、特徴ベクトルを生成し、特徴ベクトル記憶手段に格納する特徴ベクトル算出ステップと、
類似度算出手段が、前記特徴ベクトル記憶手段から特徴ベクトルを読み出して、特徴ベクトル間の類似度を求め、類似度記憶手段に格納する類似度算出ステップと、
クラスタリング手段が、前記類似度記憶手段から特徴ベクトル間の類似度を読み出してクラスタリングを行い、生成されたクラスタに含まれるＵＲＬをＷｅｂページグループとして抽出し、ＵＲＬ分類記憶手段に出力するクラスタリングステップと、
を行うことを特徴とするＷｅｂページグループ抽出方法。
【請求項２】
文字列分割ステップにおいて、
前記ＵＲＬの部分文字列としてホスト部、ドメイン部、ディレクトリ部、クエリ部毎に分割し、
前記特徴ベクトル算出ステップにおいて、
前記部分文字列の出現頻度によって前記特徴ベクトルを求める
請求項１記載のＷｅｂページグループ抽出方法。
【請求項３】
アクセスログから、異なるＵＲＬであるが、同じＷｅｂページ、あるいは、同じ種類のＷｅｂページをグループとして抽出するＷｅｂページグループ抽出装置であって、
入力された前記アクセスログからＵＲＬを抽出しＵＲＬ記憶手段に格納するＵＲＬ抽出手段と、
前記ＵＲＬ記憶手段から前記ＵＲＬを読み出して、該ＵＲＬを文字列と見做し、各部位毎に部分文字列として分割する文字列分割手段と、
出現する前記部分文字列に基づいて、特徴ベクトルを生成し、特徴ベクトル記憶手段に格納する特徴ベクトル算出手段と、
前記特徴ベクトル記憶手段から特徴ベクトルを読み出して、特徴ベクトル間の類似度を求め、類似度記憶手段に格納する類似度算出手段と、
前記類似度記憶手段から特徴ベクトル間の類似度を読み出してクラスタリングを行い、生成されたクラスタに含まれるＵＲＬをＷｅｂページグループとして抽出し、ＵＲＬ分類記憶手段に出力するクラスタリング手段と、
を有することを特徴とするＷｅｂページグループ抽出装置。
【請求項４】
文字列分割手段は、
前記ＵＲＬの部分文字列としてホスト部、ドメイン部、ディレクトリ部、クエリ部毎に分割する手段を含み、
前記特徴ベクトル算出手段は、
前記部分文字列の出現頻度によって前記特徴ベクトルを求める手段を含む
請求項３記載のＷｅｂページグループ抽出装置。
【請求項５】
請求項３または４のいずれかに記載のＷｅｂページグループ抽出装置を構成する各手段としてコンピュータを機能させるためのＷｅｂページグループ抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、Ｗｅｂページグループ抽出方法及び装置及びプログラムに係り、特に、アクセスログ等に含まれる大量のＵＲＬが与えられた際に、ＵＲＬに異なりはみられるものの、同様の内容を持つＷｅｂページを一つのグループとして抽出するためのＷｅｂページグループ抽出方法及び装置及びプログラムに関する。
【背景技術】
【０００２】
アクセスログの解析の際には、ＵＲＬに基づきどのページにどのようなアクセスが行われているかを分析する。このとき、異なるＵＲＬであるが、同じＷｅｂページへの、あるいは同じ種類のＷｅｂページへのアクセスとして処理をすべきＵＲＬが存在する。
【０００３】
異なるＵＲＬであるが、同じＷｅｂページとして扱うべきものには、負荷分散などを目的としたミラーページなど同じ内容を持つＷｅｂページがあげられる。このようなページは、Ｗｅｂ閲覧者にとっては同じＷｅｂページであり、異なるＵＲＬであっても同じＵＲＬへのアクセスとして処理しなければ解析の精度は低下する。
【０００４】
また、同じ種類のＷｅｂページとしては、同種類の多数の項目についてそれぞれにＷｅｂページが存在する場合などがあげられる。
【０００５】
例えば、ＥＣ(Electronic Commerce)サイトにおいて数多くの商品に対し、個別に商品詳細情報のＷｅｂページが準備されていることがある。このようなページは、ログ解析の目的によっては、個別のＷｅｂページへのアクセスとするよりも、ある一つの種類のＷｅｂページヘのアクセスとして処理することで解析の精度が向上する。
【０００６】
以上のようなことから、異なるＵＲＬであるが、同じＷｅｂページ、あるいは同じ種類の情報を持つＷｅｂページからなるグループを抽出し、一つのＷｅｂページのアクセスとして解析対象とする必要がある。
【０００７】
アクセスログに含まれるＵＲＬに対し、手作業で同じＷｅｂページ、あるいは同じ種類のＷｅｂページからなるグループを抽出することは困難である。
【０００８】
これに対し、同様の内容を持つＷｅｂサイトの抽出方法としてはミラーサイト群の発見方法等がある。この方法は、大量Ｗｅｂページ集合からＷｅｂサイトのトップページとなるページを推定し、Ｗｅｂページ集合について推定したトップページと、それにリンクしたページからサイト集合を決定し、このサイト集合に対し、サイズが一定値以上のサイトを処理対象として絞り込み、サイトが持つリンク文字列、アンカー文字列、内部／外部リンク情報のファイルを作成する。この中から同じ特徴を持つサイトペアをミラーサイトとして選択し、ミラーサイト候補ペアの類似度からミラーサイトペアを検出する（例えば、特許文献１参照）。
【特許文献１】特開２００４−２６４９２６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、前述した同一Ｗｅｂサイトの抽出方法には、次のような問題がある。
【００１０】
（１）同一Ｗｅｂサイトの抽出方法は、アクセスログに含まれるＵＲＬと、ＵＲＬが指し示すＷｅｂページに含まれるリンク構造などを利用して、同一サイトを発見するものである。このため、アクセスログを解析する際には、必ずしも含まれるＵＲＬにアクセスされた時点でのＷｅｂページが取得できるとは限らず、Ｗｅｂページに含まれる情報を利用することができない場合も多い。このような場合には重複するＷｅｂページ抽出ができないという問題がある。
【００１１】
（２）また、上記の抽出方法は、サイトを単位として同一サイトの発見を目指すものである。このため、同じ内容を持つＷｅｂページには必ずしもサイト全体のミラーサイトに含まれるものとは限らず、あるサイトにおいてアクセスが集中する特定のページだけに重複ページが準備されていることも多い。このような場合には、必ずしもサイト全体が重複しているとは限らず、重複するＷｅｂページが抽出できないという問題がある。
【００１２】
（３）また、上記の抽出方法は、完全に同一のＷｅｂページを抽出するものであり、同じ種類の情報へのアクセスだと考えられるＷｅｂページは抽出できない。
【００１３】
上記のように、従来の方法は、アクセスログ解析の際には、Ｗｅｂページが取得されていなくてはならず、サイト単位での抽出方法であるという問題がある。
【００１４】
本発明は、上記の点に鑑みなされたもので、大量のＵＲＬからＵＲＬ情報のみを用いて、ページ単位に同様の内容を持つＷｅｂページをグループとして抽出することが可能なＷｅｂページグループ抽出方法及び装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
図１は、本発明の原理を説明するための図である。
【００１６】
本発明（請求項１）は、アクセスログから、異なるＵＲＬであるが、同じＷｅｂページ、あるいは、同じ種類のＷｅｂページをグループとして抽出する方法であって、
アクセスログ入力手段が、入力されたアクセスログからＵＲＬを抽出しＵＲＬ記憶手段に格納するＵＲＬ抽出ステップ（ステップ１）と、
文字列分割手段が、ＵＲＬ記憶手段からＵＲＬを読み出して、該ＵＲＬを文字列と見做し、各部位毎に部分文字列として分割する文字列分割ステップ（ステップ２）と、
特徴ベクトル算出手段が、出現する部分文字列に基づいて、特徴ベクトルを生成し、特徴ベクトル記憶手段に格納する特徴ベクトル算出ステップ（ステップ３）と、
類似度算出手段が、特徴ベクトル記憶手段から特徴ベクトルを読み出して、特徴ベクトル間の類似度を求め、類似度記憶手段に格納する類似度算出ステップ（ステップ４）と、
クラスタリング手段が、類似度記憶手段から特徴ベクトル間の類似度を読み出してクラスタリングを行い、生成されたクラスタに含まれるＵＲＬをＷｅｂページグループとして抽出し、ＵＲＬ分類記憶手段に出力するクラスタリングステップ（ステップ５）と、を行う。
【００１７】
また、本発明（請求項２）は、文字列分割ステップ（ステップ２）において、
ＵＲＬの部分文字列としてホスト部、ドメイン部、ディレクトリ部、クエリ部毎に分割し、
特徴ベクトル算出ステップ（ステップ３）において、
部分文字列の出現頻度によって特徴ベクトルを求める。
【００１８】
図２は、本発明の原理構成図である。
【００１９】
本発明（請求項３）は、アクセスログから、異なるＵＲＬであるが、同じＷｅｂページ、あるいは、同じ種類のＷｅｂページをグループとして抽出するＷｅｂページグループ抽出装置であって、
入力されたアクセスログからＵＲＬを抽出しＵＲＬ記憶手段３に格納するＵＲＬ抽出手段２と、
ＵＲＬ記憶手段３からＵＲＬを読み出して、該ＵＲＬを文字列と見做し、各部位毎に部分文字列として分割する文字列分割手段４１と、
出現する部分文字列に基づいて、特徴ベクトルを生成し、特徴ベクトル記憶手段５に格納する特徴ベクトル算出手段４２と、
特徴ベクトル記憶手段５から特徴ベクトルを読み出して、特徴ベクトル間の類似度を求め、類似度記憶手段６に格納する類似度算出手段４３と、
類似度記憶手段６から特徴ベクトル間の類似度を読み出してクラスタリングを行い、生成されたクラスタに含まれるＵＲＬをＷｅｂページグループとして抽出し、ＵＲＬ分類記憶手段７に出力するクラスタリング手段と４４、を有する。
【００２０】
また、本発明（請求項４）は、文字列分割手段４１においては、
ＵＲＬの部分文字列としてホスト部、ドメイン部、ディレクトリ部、クエリ部毎に分割する手段を含み、
特徴ベクトル算出手段４２は、
部分文字列の出現頻度によって特徴ベクトルを求める手段を含む。
【００２１】
また、本発明（請求項５）は、請求項３または４のいずれかに記載のＷｅｂページグループ抽出装置を構成する各手段としてコンピュータを機能させるためのＷｅｂページグループ抽出プログラムである。
【発明の効果】
【００２２】
上記のように本発明によれば、大量のＵＲＬからＵＲＬ情報のみを用い、異なるＵＲＬを持つが同じＷｅｂページ、あるいは／及び、同じ種類のＷｅｂページをグループとして抽出できる。Ｗｅｂページのグループを抽出することで、それらのＷｅｂページへのアクセスを同一Ｗｅｂページへのアクセスとして扱うことができ、アクセスログ解析の精度向上が期待できる。
【発明を実施するための最良の形態】
【００２３】
以下、図面と共に本発明の実施の形態を説明する。
【００２４】
図３は、本発明の一実施の形態におけるＵＲＬ分類装置の構成を示す。
【００２５】
同図に示すＵＲＬ分類装置は、アクセスログ入力部２、ＵＲＬ記憶部３、ＵＲＬ分類部４、特徴ベクトル記憶部５、類似度記憶部６、ＵＲＬ分類記憶部７から構成される。
【００２６】
アクセスログ入力部２は、収集されたアクセスログ１が入力されると、当該アクセスログからＵＲＬを抽出し、ＵＲＬ記憶部３に格納する。
【００２７】
ＵＲＬ分類部４は、文字列分割部４１、特徴ベクトル算出部４２、類似度算出部４３、クラスタリング部４４から構成される。文字列分割部４１は、ＲＬ記憶部３からＵＲＬを読み出して、当該ＵＲＬに含まれる文字列を各部位ごとに分割し、特徴ベクトル算出部４２は部分文字列を計数し、ＵＲＬ特徴ベクトルを求め、類似度算出部４３はＵＲＬ特徴ベクトル間の類似度を算出し、クラスタリング部４４はクラスタリングを行い、その結果をＵＲＬ分類記憶部７に格納する。
【００２８】
以下に上記の構成における動作を説明する。
【００２９】
図４は、本発明の一実施の形態におけるＵＲＬ分類部の動作のフローチャートである。
【００３０】
ステップ１０１）まず、文字列分割部４１において、ＵＲＬ記憶部３からアクセスログを読み出して、図５に示すようなアクセスログに含まれる各ＵＲＬについて、含まれる文字列を各部位毎に分割し、さらにディレクトリ部については１階層毎に、クエリ部については１パラメータ毎に分割して抽出する。
【００３１】
以下に分割例を示す。
【００３２】
ＵＲＬ例：
http://www.xxx.yuu/path1/path2/path3?param1=value1&param2=value2
分割例：
host部  ［www］
domain部  ［xxx.yyy］
directory部  ［path1,path2,path3］
query部  ［param1=value1,param2=value2］
ステップ１０２）特徴ベクトル算出部４２は、ＵＲＬに含まれる部分文字列を計数し、それに基づいてＵＲＬ特徴ベクトルを求め、特徴ベクトル記憶部５に格納する。この際、異なる部位に含まれる部分文字列は異なる部分文字列として扱う。
【００３３】
なお、ベクトルの成分数は、対象全ＵＲＬのhost部に生起する全ての部分文字列の種類数ｐ、同じくdomain部、path部、query部毎に生起する全ての部分文字列の種類数ｑ、ｒ、ｓを足し合わせて（ｐ＋ｒ＋ｓ＝Ｎ）Ｎ個である。
【００３４】
図６に示す１３個のＵＲＬ例が与えられたとき、算出されるＵＲＬ特徴ベクトルの一部を図７に示す。
【００３５】
図６のＵＲＬ例では、部分文字列の種類数は、
host部：４、domain部：５、directory部：１１、query部：５
であり、次元数２５の特徴ベクトルにより表される。
【００３６】
なお、図７〜図９における番号は図６の同じ行番号のＵＲＬを示すものとする。
【００３７】
ステップ１０３）  次に、類似度算出部４３は、特徴ベクトル記憶部５からＵＲＬ特徴ベクトルを読み出して、当該ＵＲＬ特徴ベクトル間の類似度を算出し、類似度記憶部６に格納する。
【００３８】
類似度算出部４３における、２つのＵＲＬ特徴ベクトルの類似度sim(a,b)の算出方法にはいくつかの手法が考えられる。例えば、２つのＵＲＬ特徴ベクトル間の内積を利用することができる。図８に図６のＵＲＬリストの各々の２つのＵＲＬ類似度を示す。類似度記憶部６には、図８に示すＵＲＬ特徴ベクトル間距離が格納されることになる。
【００３９】
ステップ１０４）  クラスタリング部４４は、類似度記憶部６から類似度（ＵＲＬ特徴ベクトル間距離）を読み出して、類似するＵＲＬ特徴ベクトルを同じクラスタにまとめる。クラスタにまとめる手法としては、いくつかの手法が考えられるが、例えば、最短距離法を利用することができる（参考文献：岸田和明、"文書クラスタリングの技法:文献レビュー"， Library and Information Science, no.49, pp.33-75 (2003)）。なお、ベクトルの類似度が高いものほど近くに位置するベクトルと考えられる。
【００４０】
以下に最短距離法によるクラスタリング手法を示す。
【００４１】
１）  全ＵＲＬ特徴ベクトルを個別に初期クラスタとし、処理を開始する。
【００４２】
２）  まとめられたクラスタと他のクラスタとの距離を、２つのクラスタに属する対象のうち、最も近い対象間の距離をクラスタ間類似度として再計算する。
【００４３】
上記の１）、２）のステップを予め設定した閾値以下の距離を持つクラスタがなくなるまで繰り返す。
【００４４】
図９に図６のＵＲＬリストのクラスタリング結果の樹形図を示す。同じクラスタに含まれるＵＲＬ特徴ベクトルを持つＵＲＬグループを、同じ内容を持つwebページとして抽出し、ＵＲＬ分類記憶部７に格納する。
【００４５】
図９において、線に示されている位置に閾値が設定されているとすると、
ＵＲＬ番号１と２；
ＵＲＬ番号９，１０と１１；
ＵＲＬ番号３，４と５；
ＵＲＬ番号６，７と８；
ＵＲＬ番号１２；
ＵＲＬ番号１３；
の７つのクラスタが得られる。これは、期待するＵＲＬグループと同じである。
【００４６】
上記のような処理を行うことにより、アクセスログに含まれる大量のＵＲＬからＵＲＬ情報のみ（ＵＲＬの内容には関与せず）を用い、異なるＵＲＬを持つが、同じＷｅｂページ、あるいは／及び、同じ種類のＷｅｂページをグループとして抽出できる。
【００４７】
なお、上記の図３に示す装置の構成要素の動作をプログラムとして構築し、Ｗｅｂページグループ抽出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００４８】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または配布することが可能である。
【００４９】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【産業上の利用可能性】
【００５０】
本発明は、Ｗｅｂページの検索する技術に適用可能である。
【図面の簡単な説明】
【００５１】
【図１】本発明の原理を説明するための図である。
【図２】本発明の原理構成図である。
【図３】本発明の一実施の形態におけるＷｅｂページグループ抽出装置の構成図である。
【図４】本発明の一実施の形態におけるＵＲＬ分類部の詳細な処理を示すフローチャートである。
【図５】本発明の一実施の形態におけるＵＲＬ文字列の例である。
【図６】本発明の一実施の形態におけるＵＲＬリストの具体例である。
【図７】本発明の一実施の形態におけるＵＲＬ特徴ベクトルの具体例である。
【図８】本発明の一実施の形態におけるＵＲＬ特徴ベクトル間距離の具体例である。
【図９】本発明の一実施の形態におけるクラスタリング結果の例である。
【符号の説明】
【００５２】
１  アクセスログ
２  ＵＲＬ抽出手段、アクセスログ入力部
３  ＵＲＬ記憶手段、ＵＲＬ記憶部
４  ＵＲＬ分類部
５  特徴ベクトル記憶手段
６  類似度記憶手段
７  ＵＲＬ分類記憶手段
４１  文字列分割手段、文字列分割部
４２  特徴ベクトル算出手段、特徴ベクトル算出部
４３  類似度算出手段、類似度算出部
４４  クラスタリング手段、クラスタリング部
【図１】
2010123000.tif 000003
【図２】
2010123000.tif 000004
【図３】
2010123000.tif 000005
【図４】
2010123000.tif 000006
【図５】
2010123000.tif 000007
【図６】
2010123000.tif 000008
【図７】
2010123000.tif 000009
【図８】
2010123000.tif 000010
【図９】
2010123000.tif 000011