階層型カテゴリを用いたウェブサイトのアクセス履歴の 時系列相関性

DEWS2005 6C-i10
階層型カテゴリを用いたウェブサイトのアクセス履歴の
時系列相関性解析
平野 真太郎†
成 凱‡
岩井原 瑞穂†
†京都大学情報学研究科 〒606-8501 京都市左京区吉田本町
‡九州産業大学情報科学部 〒813-8503 福岡市東区松香台 2-3-1
E-mail:
†{shin, iwaihara}@db.soc.i.kyoto-u.ac.jp, ‡[email protected]
あらまし インターネットにおいてどのようなコンテンツが人気があり，またどのコンテンツ同士に関連があるかといった
情報はインターネット広告会社をはじめとする非常に多くの会社が欲している情報である．しかし何十億といわれる膨大な量の
ウェブサイトを解析することは難しい．我々はウェブのインデックスといえるディレクトリ型検索システムの階層カテゴリとそ
の利用状況を用いた効率的な利用者の興味動向分析を行う．ウェブサイトの時系列の利用頻度パターンの相関性を，類似検索や
時間帯別の利用型への分類などにより階層構造を考慮して調べる．カテゴリの利用パターンの特徴，例えば朝によく利用される
カテゴリ，夜間によく利用されるなどの時間帯による利用状況，そしてカテゴリ同士の関連性などが知ることができれば，イン
ターネット広告において広告効果に見合った料金システム，ならびにより効果的な広告作成が可能になると考えられる．例えば，
表示時間に応じて料金が決める方式の場合，昼によく見られるカテゴリであれば，昼の時間帯にだけ広告を出すことによって宣
伝コストを下げるといったことも可能になる． 本稿では時間帯別の利用型分析とウェブサイトの利用頻度パターンの類似判断
手法を用いたウェブサイトの相関性解析について述べる．
キーワード 階層型カテゴリ，類似判定，アクセス履歴，ディレクトリ型検索エンジン，インターネット広告
Time-series Similarity Analysis for Web Access Log Pattern by Using
Hierarchical Category of Web
Shintaro HIRANO†
Kai CHENG‡
and Mizuho IWAIHARA‡
†Graduate School of Informatics, Kyoto University, Yoshidahonmachi, Sakyo-ku, Kyoto, 606-8501
‡Faculty of Information Science, Kyusan University Matukadai 2-3-1, Higashi-ku, Fukuoka, 813-8503
E-mail:
Abstract
†{shin, iwaihara}@db.soc.i.kyoto-u.ac.jp ‡[email protected]
Information about user interest is very useful for many applications, especially Internet Advertisement. But it is difficult to
analyze billons of web sites. To know user interest on web, we analyze directory of the web and its access log. Time-series similarity search
in similar usage patterns considering hierarchy of web category help analyzing it. We demonstrated that a special feature of the usage of
categories, for example one topic is often accessed in the morning, the other is often accessed in the night, can improve current Internet
Advertisement. We report the result of analysis by hours and ensured that categories are enabled to divide into 4 types and propose
Keyword Hierarchical Category, Similarity Search, Access Log, Directory of the Web, Internet Advertisement
1. は じ め に
情報源である．本研究の特徴は以下の３つである．
何十億といわれる膨大な量のウェブサイトを解析
す る こ と は 難 し い ． Yahoo!カ テ ゴ リ [11]や DMOZ[8]と
1.
カテゴリの階層構造を考慮したカテゴリ利用頻度
の計算
いったディレクトリ型検索システムはインターネット
の世界のインデックスを構成しているといえる．我々
2.
カテゴリの利用パターンによる類似カテゴリ分析
はディレクトリ型検索システムのインデックス構造，
3.
一 般 ISP の 実 デ ー タ に よ る 分 析
カテゴリの階層構造の利用状況分析による利用者の興
味動向分析を行う．利用状況分析には一般のインター
我々はカテゴリの階層構造を抽出するために
ネ ッ ト・サ ー ビ ス・プ ロ バ イ ダ ー (ISP)の ア ク セ ス 履 歴
Yahoo!カ テ ゴ リ を 利 用 し た ． Yahoo!は 代 表 的 な デ ィ レ
であるプロキシログを利用した．プロキシログは会員
クトリ型検索システムであり，カテゴリごとにカテゴ
利用者のウェブ上の活動を記録したものであり貴重な
リ を 持 つ ． Yahoo!カ テ ゴ リ か ら カ テ ゴ リ の 階 層 構 造 を
とりだし，カテゴリに含まれるサイト数をサイト量と
2. 関 連 研 究
し た ． そ し て 一 般 ISP の 会 員 の ア ク セ ス 履 歴 を 用 い て
インターネット広告の効果測定の手法としてユー
各カテゴリのサイト量を考慮した実際の利用頻度を調
ザーセントリックと呼ばれるものがある．これは調査
べ ， カ テ ゴ リ を 抽 出 し ISP の 会 員 利 用 者 の 興 味 の 動 向
会社が，インターネット利用者の性別などの属性を反
を分析した．
映させた調査用パネルを抽出し，測定用プログラムの
Yahoo! は ポ ー タ ル サ イ ト と し て 利 用 さ れ る こ と が
インストールを依頼して，そのアクセス履歴を解析す
多く，他のポータルサイトやニュースサイトよりもア
るというものである．複数のウェブサイトやインター
クセスが多いため，より利用者の興味を反映した高頻
ネット広告の効果を同一基準で比較できる長所を持つ
度カテゴリ抽出が期待できる．
ものである．このアクセス履歴を利用し利用者の大域
カテゴリの利用の特徴や共起関係を詳しく調べる
的 な 行 動 を 把 握 す る こ と を 目 的 と し た 研 究 [3]が あ る ．
ために様々な角度から類似するカテゴリを調べる．と
利用者が区別できる貴重なアクセス履歴を用いており，
くにカテゴリの利用頻度パターンから得たフーリエ係
類似するウェブサイトをまとめる技術であるウェブコ
数を利用した類似カテゴリ分析を行う．類似検索を利
ミ ュ ニ テ ィ [12]と ア ク セ ス 履 歴 に 残 る 検 索 結 果 を 用 い
用し同じ利用パターンを持つカテゴリを探す．
たウェブログ解析システムを提案している．
またカテゴリの利用の特徴，例えば朝によく利用さ
MSN[10]の 検 索 エ ン ジ ン の 大 量 の 利 用 結 果 を 用 い て ，
れるカテゴリ，夜間によく利用されるなどの時間帯に
利用されたクエリー間の類似性を調べる研究がある
よる利用状況，そしてカテゴリ同士の関連性などが知
[4]．各 ク エ リ ー の 時 系 列 の 利 用 デ ー タ か ら フ ー リ エ 係
ることができれば，インターネット広告において広告
数を求め，その係数を利用してクエリー間の類似性を
効果に見合った料金システム，ならびにより効果的な
ユークリッド距離によって決定している．クエリーの
広告作成が可能になると考えられる．例えば，表示時
利用周期性の発見およびバーストの発見の手法を提案
間に応じて料金が決める方式の場合，昼によく見られ
している．バーストの例としてエルビス・プレスリー
るカテゴリであれば，朝のうちに新しい広告を準備す
の 命 日 付 近 で ク エ リ ー ”elvis”が よ く 検 索 に 利 用 さ れ る
ることによって，より効率的に多くの利用者に訴える
といったことが分るという具合である．精度の良い類
ことができるようになる．昼の時間帯にだけ広告を出
似クエリー検索を行うためにインデクシングの方法と
すことによって宣伝コストを下げるといったことも可
効率の良いインデックス構造について複数手法提案し
能になる．
検証している．インデクシングに重点を置いた研究で
ま た Google[9]な ど の 検 索 エ ン ジ ン に お い て 特 定 の
ある．
クエリーの検索結果にスポンサーサイトという形で広
告を出す方法がある．例えば「C 言語」というクエリ
3. カ テ ゴ リ 利 用 頻 度
ー の 検 索 結 果 に 対 し ， C 言 語 の e-learning サ イ ト が 現
分析の基本データとなるカテゴリの時系列利用頻
れるといった具合である．クエリーとその関連するカ
度の計算方法において特徴となる 2 つの概念は次の通
テ ゴ リ (例 ． C 言 語 と 学 習 )を 時 間 軸 に よ っ て 把 握 で き
り．
れば，それを考慮した広告をだすことによってより効
•
率的な効果が期待できると考えられる．
カテゴリに含まれるウェブサイトの数．人気のあ
以下 2 章では関連研究，3 章ではカテゴリの時系列
の利用頻度の計算方法について，4 章では時間軸やカ
サイト量
るカテゴリほどサイト数が多い．
•
利用頻度
テゴリの階層構造を考慮した相関性分析について述べ，
実際に利用者によって利用された頻度．よく利用
5 章ではウェブサイトの利用頻度パターンの類似性を
されたカテゴリほど重要である．
判定する方法について述べる．6 章では実験データと
実験について説明する．実験では時間帯の利用の特徴
このサイト量を考慮した利用頻度を求める．ここで
についての調査と共起カテゴリの発見を行い提案手法
はカテゴリの利用頻度を計算する際に用いる手法につ
の評価を行った．
いて図 1 を利用して説明する．
4.1. 時 間 帯 の利 用 型 による類 似 カテゴリ解 析
スポーツ
10+(18+17)=45
時間帯別の利用状況を調べることによって，例えば
朝によく利用されるカテゴリ，夜間によく利用される
などの時間帯による利用状況，そしてカテゴリ間の共
野球
6+(5+7)= 18
サ ッカ ー
7+(3+4+3)=17
起関係などを知ることができれば，インターネット広
告において広告効果に見合った料金システム，ならび
により効果的な広告作成が可能になると考えられる．
例えば，バナー広告で一般的に利用されている表示時
セ ・リー グ
5
パ ・リー グ
7
Ｊリ ー グ
3
野球
オ リン ピック
4
ユーロ
3
サ ッカ ー
間に応じた掲載料金方式においては，昼によく見られ
るトピックであれば，朝のうちに新しい広告を準備す
サ イト量
3
4
ることによって，より効率的に多くの利用者に訴える
利用頻度
18
17
ことができるようになる．昼の時間帯にだけ広告を出
すことによって宣伝コストを下げるといったことも可
図 1． カ テ ゴ リ 利 用 頻 度 例
ま ず Yahoo! カ テ ゴ リ か ら カ テ ゴ リ の 階 層 構 造 を 抽
出する．図 1 の木構造がカテゴリの階層構造を表して
能になる．
4.2. 兄 弟 カテゴリ間 の利 用 の違 い
同一カテゴリに配置されたウェブサイトの時間軸
い る ．カ テ ゴ リ の サ イ ト 量 は 子 孫 カ テ ゴ リ の 数 で あ り ，
を 意 識 し た 兄 弟 カ テ ゴ リ (横 関 係 )の 利 用 パ タ ー ン を 比
図 1 の野球カテゴリのサイト量は 3 である．次に利用
較 す る ．例 え ば ，タ レ ン ト カ テ ゴ リ に お い て SMAP と
頻度をウェブサイトへのアクセス回数を用いて計算す
モーニング娘のサイト利用され方の比較を行う．利用
る ．図 1 の 野 球 は そ の サ イ ト 自 体 の ア ク セ ス 回 数 (6 回 )
者に違いが有ると考えられる．
と 子 で あ る セ ・ リ ー グ (5 回 )と パ ・ リ ー グ (7 回 )の ア ク
セ ス 回 数 (利 用 頻 度 )を 加 え た も の と な り 18 と な る ．つ
まり各カテゴリの利用頻度は子孫カテゴリの利用頻度
を 考 慮 し た も の に な る ．こ の デ ー タ を 分 析 単 位 (１ 時 間 ，
１ 日 ，１ 週 間 ，１ 月 )に 時 間 推 移 と 共 に 集 計 す る こ と に
よって時系列の利用頻度が計算できる．
利用頻度
兄弟カテゴリ間の利用の相違はあるのか？
図 3． 兄 弟 カ テ ゴ リ の 利 用 比 較
4.3. 親 子 カテゴリ間 の利 用 の違 い
親 子 (縦 関 係 )間 の カ テ ゴ リ の 利 用 の 違 い を 調 べ る ．
兄弟間ならびに親自身の利用のされ方の重ねあわせが
時刻
どう影響するかを調べる．
図 2． 時 系 列 利 用 頻 度 パ タ ー ン の 例
4. カ テ ゴ リ の ア ク セ ス 相 関 性 解 析
カテゴリの階層構造を利用した分析を行う．クエリ
ーは各サイトの時系列データから求めたフーリエ級数
とし各対象カテゴリとの類似性を調べる．分析結果に
よって手動によって分類されたカテゴリ階層構造の見
直しを行うことができる．利用者の違いやサーバの最
親子カテゴリ間の利用の相違はあるのか？
適な配置方法などを見つけることも可能になる．
図 4． 親 子 カ テ ゴ リ 間 比 較
階層型カテゴリの利用特徴を調べる上で，親子間にお
ける子の親への影響を調べることは重要である．
利用頻度において各時間帯の利用頻度を集計し
あ る 子 供 i の 影 響 度 が 大 き い 場 合 ，x の 特 徴 は i に 支
全体の利用頻度に占める割合を求める．最大の割合を
配されているといえる．この場合ｘと i の利用頻度パ
占める時間帯の割合が閾値を超えるとき，利用型をそ
ターンは非常に類似していることになる．また大きな
の 時 間 帯 に 決 め る ．こ れ に よ り カ テ ゴ リ を 朝 方 利 用 型 ，
影響を及ぼす子供が存在しない場合，x の特徴はすべ
昼間利用型，夜間利用型，深夜利用型に分けることが
ての子供を重ね合わせたものであるが，ｘとそれぞれ
できる．
の子供が類似している場合や，すべての子供を重ねあ
わせてはじめてｘの特徴が現れるという場合が考えら
5.2. フーリエ係 数 を用 いた類 似 判 定 手 法
れる．後者では個々のウェブサイトでは分からなかっ
2 つの利用頻度パターンをユークリッド距離関数と
た特徴がカテゴリとして扱うことで得られるものであ
閾値をもって類似を判定することができる．波形同士
り，たとえば，個々では周期があるようには見えなか
を 比 較 す る 際 に は 2 つ の 波 の 離 散 フ ー リ エ 変 換 (DFT)
ったものが重ね合わせたカテゴリの利用頻度パターン
に よ っ て 得 ら れ る フ ー リ エ 級 数 ｛ Q, T｝ を 用 い た ユ ー
を調べることによって周期を発見することができると
ク リ ッ ド 距 離 D(Q, T)を 用 い る の が 一 般 的 で あ る ．閾 値
いった具合である．
ε が 与 え ら れ ，ク エ リ ー Q に 対 し て D(Q, T) ≦ ε を 満 た
す T すべてを類似していると判定する．
4.4. カテゴリ間 の共 起 関 係 の発 見
フーリエ係数を用いた類似判定の研究における速
カテゴリ類似検索を行うことで，一見関係のないと
度 向 上 の 取 り 組 み は Agrawal ら の 研 究 [7]が 基 礎 と な っ
思われるカテゴリ間で，時系列における共起関係を調
て い る ．[7]で は 周 波 数 の 小 さ い k 個 の フ ー リ エ 係 数 を
べることが可能になる．例えば，スポーツのアテナオ
利 用 し た 下 界 (Lower Bound)の 計 算 に つ い て 述 べ て い
リンピックに関連するカテゴリが人気があったときに，
る ． GEMINI と 呼 ば れ る 下 界 距 離 計 算 と ク エ リ ー と 比
アテネへの旅行のカテゴリが付随して人気が出るとい
較する候補者検索のための多次元インデックスを利用
う関係が分かるといった具合である．このような共起
している．
関係が分ればより利用者に便利なサイト構成などに応
•
用することが可能である．
離散系に応用したフーリエ変換が離散フーリエ変
離散フーリエ変換
換 (DFT)で あ る ． 変 換 式 は 以 下 の 通 り で あ る ．
X ( fK
N )=
1
N
N −1
∑
x ( n )e
k =0
− jπk
2n
M
, k = 0,1K N − 1
た だ し ， X(f)は 周 波 数 領 域 の デ ー タ で あ り x(n)は 時
間領域の基本周期となるＮ個のデータである． fk
カテゴリ間の共起 関係の発見
図 5． カ テ ゴ リ 間 の 共 起 関 係
N
の
範 囲 が N/2 で あ る の は サ ン プ リ ン グ 定 数 に よ る も の で
(
ある． X fk
N
)は 複 素 数 に な る が ， こ れ は 周 波 数 成 分
の強さと位相を結果とするためである．周波数ごとの
5. 利 用 頻 度 パ タ ー ン に よ る 類 似 判 断 手 法
精 度 の 高 い ウ ェ ブ サ イ ト 間 の 相 関 性 検 索 (利 用 パ タ
ー ン 分 類 )を 行 う た め に 類 似 性 を 判 断 す る 必 要 が あ る ．
複素正弦関数の線形結合によって元の信号の復元が可
能である．
ベクトルの強さ P をフーリエ係数の絶対値の二乗
値で表現できる．
5.1. 時 間 帯 別 利 用 型 によるカテゴリ分 類 手 法
カテゴリの時間帯による利用型を定義する．以下の
ように一日を 6 時間刻みの時間帯に分ける．
P( fk
N
) = || X ( f k
N
 N − 1
) || 2 , k = 0 ,1 K 

 2 
１．
朝
5:00∼ 10： 59
２．
昼
11： 00∼ 16： 59
P の 大 き な フ ー リ エ 係 数 は ，大 き な エ ネ ル ギ ー を も っ
３．
夜
17： 00∼ 22： 59
たフーリエ係数であり元の波の形に大きな影響を与え
４．
深夜
23： 00∼ 4： 59
ている．このエネルギーの大きなフーリエ係数を用い
て周期性を強調した利用頻度パターンを復元すること
n
ができる．
Sim _ score( A, B ) =
5.3. バーストを用 いた類 似 カテゴリ判 定 手 法
∑ min(b ( A), b ( B))
t
t
t =1
t : ＡとＢの共起バースト 発生する時刻
「 短 期 的 に 起 き る 急 激 な 利 用 頻 度 増 加 」を バ ー ス ト と
した．バーストは利用者の短期的に盛り上がる興味を
n : 共起バーストの数
知る上で重要である．例えば，アテネオリンピックの
bt ( A) : Aの時刻tのバーストの利用頻度
ようなイベントがテレビで取り上げられスポーツに関
bt ( B ) : Bの時刻tのバーストの利用頻度
連するカテゴリの利用が大きく増えるが，イベントが
過ぎると利用も減るといった具合である．
6. 実 験 デ ー タ お よ び 実 験
バ ー ス ト は カ テ ゴ リ の 特 徴 を 示 す も の で あ り ，カ テ ゴ
本 研 究 で は Yahoo! カ テ ゴ リ と い う デ ィ レ ク ト リ 型
リ間のバーストの類似を調べることによってカテゴリ
検索エンジンのカテゴリの階層構造に注目し，それに
の類似性を判断することができる．
対する利用頻度を時間帯別に計算し利用者の興味の動
バ ー ス ト 検 出 で は ，利 用 頻 度 が 利 用 平 均 値 の 一 定 数 倍
向を分析した．また，カテゴリの親子間の利用頻度へ
を超え，かつ直前の時刻の利用頻度が利用頻度平均値
の影響度，兄弟カテゴリの利用の違いについても調べ
より低いときバーストとする．
た ．解 析 に は Perl を 利 用 し ，カ テ ゴ リ 構 造 抽 出 と テ キ
各 カ テ ゴ リ か ら バ ー ス ト を 抽 出 し ，次 の 情 報 を 取 り 出
ストタイプのプロキシログ処理行った．
す．
・
バースト発生時刻
・
バーストの発生回数
・
各時刻の利用頻度比率（平均を１とする）
ィアとニュース”といった主要なカテゴリによって構
これらの情報を用いてバーストを用いた類似判断手
成 さ れ て い る ． 興 味 の あ る コ ン テ ン ツ (リ ン ク )を 辿 っ
法を２つ提案する．
ていくことによってより詳細なカテゴリ情報にアクセ
5.3.1. 共 起 バ ー ス ト の 発 生 回 数 の 類 似 度 に よ る
6.1. 実 験 データ
Yahoo!カ テ ゴ リ は “ エ ン タ ー テ イ メ ン ト ” や “ メ デ
ス す る こ と が で き る ． Yahoo!は 手 動 に よ っ て サ イ ト が
カテゴリ分類され登録されているため，その分類は信
類似判定
カテゴリＡとカテゴリＢの共起するバーストの数
頼できると考えられ有用な情報源である．カテゴリ情
の ，Ａ と Ｂ の バ ー ス ト 総 数 に 対 す る 割 合 の 平 均 を 取 る ．
報を使うことによってカテゴリの抽出，分類のコスト
これによりバーストという特徴点に注目した，カテゴ
を省くことが出来る．
リ間の全体の類似度を求めることができる．二つの平
Yahoo!カ テ ゴ リ の 構 造 に つ い て 説 明 す る ． カ テ ゴ リ
均を取ることによってＡとＢの共通の類似度を求める
ページに含まれる主要な情報として次の 2 つがある．
ことができる．
Sim ( A, B ) =
1 NB A∩ B NB A∩ B
+
(
)
2 NB A
NBB
•
子 の カ テ ゴ リ へ の リ ン ク ．「 エ ン タ ー テ イ メ ン
ト＞芸能人，タレント＞アイドル＞イベント」
NB : バーストの発生回数
NB A∩ B : ＡとＢの共起バースト 回数
Yahoo!カ テ ゴ リ
という具合である．
•
Yahoo!登 録 サ イ ト
そ の カ テ ゴ リ に 関 す る サ イ ト で ”yahoo”を ア ド
5.3.2. 共 起 バ ー ス ト の 利 用 頻 度 加 算 に よ る 類 似
スコアによる類似判定
共起バーストの利用頻度の規模を考慮した類似判
定を行う．カテゴリＡとＢの共起バーストの各利用頻
度のうち共通部分を加算することによってバーストの
類似スコアを計算する．共起回数だけではなく二つの
カテゴリの共有利用頻度比率を用いることによってカ
テゴリの利用頻度パターンの類似を求める．
レスに含まないもの．
Yahoo!カ テ ゴ リ に お い て リ ン ク 先 は 他 の カ テ ゴ リ へ
またがることも多い．例えば「エンターテイメント→
地域情報」といった具合である．カテゴリ毎の単純な
木構造ではなく複雑な構造をしている．構造抽出にお
いて多重ハッシュを利用した．
本 研 究 で は 京 都 市 の ASTEM( 京 都 高 度 技 術 研 究 所 )
の 運 営 す る ISP， Kyoto I-net の プ ロ キ シ ロ グ を 利 用 し
て実験を行った．抽出したカテゴリの利用状況の計算
にはプロキシログを用いる．プロキシログはウェブ上
で の 利 用 者 の 活 動 (ア ク セ ス し た URL)を 時 間 順 に 保 持
し た も の で あ る ．KyotoI-net の 会 員 数 は 2 万 人 以 上 で ，
解 析 に 利 用 し た デ ー タ は 04/07/01 か ら 04/10/31 の 4 ヶ
階層構造を図 6 に示す．図に表れるカテゴリはフィル
月 分 で あ る ． Kyoto I-net で は 28 の プ ロ キ シ サ ー バ が
タ リ ン グ の 結 果 残 っ た も の で あ る ．“ 趣 味 と ス ポ ー ツ ”
稼動しており，各々が独立にプロキシログを記録して
カ テ ゴ リ の 下 に は 20 個 以 上 の 子 カ テ ゴ リ が 配 置 さ れ
い る ． 実 験 に 利 用 す る レ コ ー ド 総 数 は 148,467,531 に
ている．図を見ると親子関係，兄弟関係にあるカテゴ
も及ぶ．プロキシログに現れるファイルタイプが
リ で も 利 用 型 に 違 い が あ る こ と が 分 か る ．“ サ ッ カ ー ”
text/html で あ る も の に 限 っ た 場 合 ， そ の レ コ ー ド 数 は
の 利 用 は 74.0%が 夜 間 で 典 型 的 な 夜 間 利 用 型 で あ る ．
19,891,523 で あ り 全 体 の 13.4%を 占 め る ． 実 験 で は こ
“ プ ロ 野 球 ” は 72.4%が 深 夜 利 用 で あ る ． 一 方 で “ 高
の tex/html タ イ プ の レ コ ー ド を 利 用 し た ．
校 野 球 ” は 51.6%が 昼 間 の 利 用 で あ り ， 利 用 の 違 い が
な お Kyoto I-net か ら は 個 人 が 特 定 で き る 情 報 は 一 切
あ る こ と が 分 か る ． 格 闘 技 ， 武 術 ” は 72.4％ で 深 夜 利
削除された形式でアクセスログの提供を受けたため，
用型であった．時間帯型利用型は親子で同じになると
Kyoto I-net の 会 員 の プ ラ イ バ シ ー を 侵 害 す る こ と は な
は 限 ら ず ，“ ス ポ ー ツ ”と い う 同 一 カ テ ゴ リ に お い て も
い．
利用型が違うものがあることが分かる．
ア ク セ ス 履 歴 に 現 れ た Yahoo! カ テ ゴ リ と 登 録 サ イ
スポーツ
ト は 70,655 種 で あ っ た ．利 用 頻 度 パ タ ー ン の 類 似 分 類
を 行 う 場 合 に は 2004 年 9 月 1 日 ∼ 10 月 31 日 間 の ア ク
夜
セス履歴を利用し，もっとも精度の高い 1 時間単位の
集 計 (hour)デ ー タ を 用 い た ． グ ラ フ の 中 に は ゼ ロ が ほ
とんどで特徴を見出せないものも多かったため，集計
し た 各 カ テ ゴ リ の 持 つ 最 大 利 用 頻 度 (MAX)に よ っ て フ
深夜
ィ ル タ リ ン グ を 行 っ た (表 1 参 照 )．
夜
格闘技、武術
MAX
カテゴリ数
MAX≧ 10
12,684
MAX≧ 100
705
表 １ ． 最 大 利 用 頻 度 (MAX)に よ る フ ィ ル タ リ ン グ
予 備 実 験 で は MAX≧ 100 を 満 た す 705 種 の カ テ ゴ リ
を対象として行うことにした．
6.2. 実 験 および評 価
深夜
サッカー
朝
昼
夜
深夜
スポーツ
10.5
24.4
35.5
29.5
格闘技、武術
2.6
32.4
23.3
41.5
サッカー
0.8
16.5
74.0
8.7
野球
12.8
23.0
30.0
34.2
高校野球
9.2
51.7
30.4
8.7
プロ野球
9.0
9.7
8.9
72.4
野球
深夜
昼
プロ野球
高校野球
＊数字は割合(%)
図 6．“ ス ポ ー ツ ” カ テ ゴ リ の 時 間 帯 別 利 用 型
提案する類似判定手法を用いた利用者の興味分析
を行った．
6.2.2. 実 験 2:共 起 カ テ ゴ リ 発 見
6.2.1. 時 間 帯 別 利 用 型 の 調 査
ここでは階層構造上関係性が低いカテゴリ間の共
705 個 の カ テ ゴ リ の 時 間 帯 別 の 利 用 型 の 分 類 を 行 う ．
起関係を調べる．距離関数を用いた類似判断とバース
利 用 型 を 判 断 す る 際 に 用 い る 閾 値 を 0.3 と 0.4 に し た
トを用いた類似判定手法によって得られる相関性の強
と き の 結 果 を 6.4 に 示 す ．0.3 に お い て は ウ ェ ブ の 一 般
い 上 位 10 個 の 関 係 か ら 提 案 し た 各 手 法 の 特 長 に つ い
的な利用スタイルから夜間利用型のものが最大である．
て報告する．ランキングにおいてはスペースの関係か
4 つの利用型によく分類できているといえる．昼間利
らカテゴリの階層構造を途中省略して記述した部分が
用型の中にはディズニー映画のサイト，本屋のサイト
あ る が ，評 価 の う え で 問 題 は な い ．
（2 回目以降の出現
などがあった．
李 は 斜 体 表 示 し て い る ．）
閾値/
時間帯
0.3
0.4
朝
昼
夜
深夜
未分類
合計
17 158 292
229
9
705
16
96
140
143
310
705
表 2． 時 間 帯 別 の 利 用 型 へ の 分 類
A.フ ー リ エ 係 数 を 用 い た 類 似 判 定
表 3 を見てみると意味の近い関係は見受けられない．
これは利用の時刻が類似したことによって得られたも
のと考えられる．図 7 は一位の関係の利用頻度パター
ンである．利用頻度が少なく，利用頻度がゼロの時刻
階層カテゴリにおける時間帯別の利用型の違いを
が多いことが分かる．このような場合，類似距離の計
調 べ る た め に 閾 値 0.3 で 行 っ た 利 用 型 分 類 結 果 の 中 か
算ではフーリエ係数を求める必要は無く，利用頻度の
ら“趣味とスポーツ＞スポーツ”カテゴリを親とした
値を用いてユークリッド距離を求めれば十分である．
カテゴリ
メディアとニュース＞ビジネ
スと経済
カテゴリ
地域情報＞＞＞
鹿児島
2
コンピュータとインターネッ
ト＞情報と資料＞辞書
健康と医学＞＞
産婦人科＞病院
3
ビジネスと経済＞＞本＞＞絵
本＞クレヨンハウス
地域情報＞＞＞
大阪＞枚方
4
辞書
地域情報＞＞＞
愛知＞＞ビジネ
スと経済
1
＞タレント“という同じトピックを扱うカテゴリが
共起していることからあきらかに意味的に近い共
起関係が抽出できたことになる．8 位の共起カテゴ
リでは”芸能と人文＞デザインアート“と”ビジネ
スと経済＞ファッションとサービス＞服飾，ファッ
ション“がある．これも意味的に関係のある共起関
係であるといえる．
1
カテゴリ
コンピュータとイ
ンターネット＞＞
無料メール
ビジネスと経済＞
ショッピングとサ
ービス＞＞手芸＞
ビーズ
カテゴリ
ビジネスと経済＞＞＞ポー
タルサイト＞エキサイト
メディアとニュース＞ビジネ
スと経済＞新聞
辞書
鹿児島
7
ビジネスと経済＞＞＞中央銀
行
8
中央銀行
ビジネスと経済
＞＞本＞＞絵本
産婦人科
9
コンピュータとインターネッ
ト ＞ ＞ OS＞ WindowsCE
大阪＞枚方
3
ビーズ
趣味とスポーツ＞＞＞プロ
野球＞メディアとニュース
10
WndowsCE
地域情報＞＞＞
＞鈴鹿＞＞カー
レース
4
ビーズ
5
ビーズ
6
エンターテイメン
ト＞芸能人
エンターテイメン
ト＞芸能人
芸術と人文＞デザ
インアート
趣味とスポーツ＞＞＞プロ
野球＞メディアとニュース
趣味とスポーツ＞＞＞プロ
野球＞メディアとニュース
ビジネスと経済＞＞エンタ
ーテイメント＞タレント
ビジネスと経済＞＞＞タレ
ント＞芸能プロダクション
ビジネスと経済＞ショッピ
ングとサービス＞ファッシ
ョン
ビジネスと経済＞＞＞ソフ
トウェア＞ゲーム
5
6
産婦人科
表 3． フ ー リ エ 係 数 を 用 い た ら 類 似 距 離 に よ る
共 起 カ テ ゴ リ 上 位 10
2
600
7
500
8
利用頻度
400
9
地域情報＞＞＞愛
知＞市町村
10
芸術と人文＞デザ
インアート＞ファ
ッション
300
200
100
趣味とスポーツ＞＞＞プロ
野球＞メディアとニュース
ビジネスと経済＞買い物＞
ファッション
表 4． 類 似 度 に よ る 共 起 カ テ ゴ リ 上 位 10
0
時間(9/1∼10/31)＊1時間毎の推移
メディアとニュース＞ビジネスと経済
地域情報＞日本の地方＞九州＞鹿児島
図 7． フ ー リ エ 係 数 を 用 い た 距 離 関 数 よ り 得 ら れ た
1 位の共起カテゴリの利用頻度パターン
45
＊
エ キ サ イ ト は 実 際 の 利 用 頻 度 に +15
40
35
B.共 起 バ ー ス ト の 発 生 回 数 の 類 似 度 を 用 い た 類 似 判
定手法
1 位には“コンピュータとインターネット＞無料
サービス＞無料メール”と“ビジネスと経済＞ショ
ッピングとサービス＞インターネット・サービス＞
エキサイト”という無料メールとポータルサイトの
エキサイトが共起していることが分かる．どちらも
インターネットに関するカテゴリであり利用に関
係があると思われる．6 位の共起カテゴリは“エン
利 用 頻 度
30
25
20
15
10
5
0
時間(9/1∼10/31)＊1時間毎の推移
コンピュータとインターネット＞無料サービス＞無料メール
ビジネスと経済＞ショッピングとサービス＞インターネット・サービス＞ポータルサイト＞エキサイト
ターテイメント＞芸能人，タレント”と“ビジネス
と経済＞企業間取引＞エンターテイメント＞タレ
図 8.類 似 度 1 位 の 共 起 カ テ ゴ リ 利 用 頻 度 パ タ ー ン
ン ト ， ス タ ッ フ ” で あ っ た ．“ エ ン タ ー テ イ メ ン ト
これらの共起関係は利用頻度を無視しているこ
とから，利用頻度の低いカテゴリの共起関係をみつ
はお互いのウェブページへの直接のリンクが準備され
けることもできるというメリットがある．一方でよ
ていないことから両カテゴリを直接リンクでむすぶこ
り利用頻度の大きい，つまり人気のある共起関係を
とで利用者にとって使いやすいカテゴリ構造を構成す
優先して検出することはできない．
ることができる．このような関係を多く見つけること
によってカテゴリの再構成を行うことができると考え
C.共 起 バ ー ス ト の 利 用 頻 度 加 算 に よ る 類 似 ス コ ア 計
られる．
算を用いた類似判定
7. ま と め
カテゴリ
メディアとニュース＞
テレビ＞番組
1
カテゴリ
ビジネスと経済＞＞メ
ディアとニュース＞テ
レビ局＞テレビ朝日
テレビ局＞日本テレビ
本稿では利用者のウェブ上の行動を記録したアク
セ ス 履 歴 と WWW の イ ン デ ッ ク ス で あ る デ ィ レ ク ト リ
型検索エンジンを用いてウェブサイトのアクセス履歴
の相関性を調べる方法について述べた．
2
番組
3
番組＞アクション＞仮
面ライダー
テレビ朝日
4
5
場組み＞アクション
健康と医学
テレビ朝日
おいてはフーリエ係数とバーストを利用した手法を提
ビジネスと経済＞＞出
版＞小学館
案し検証した．今後は類似判定に用いる閾値について
6
健康と医学＞病院
出版
ークトラフィックなどのアクセス履歴解析に利用する
7
ビジネスと経済＞買物
とサービス＞＞バイク
健康と医学
地域情報＞＞＞兵庫＞
＞ 神戸
ことができる．
8
神戸
9
地域情報＞＞＞愛知＞
市町村
出版
10
芸術と人文＞デザイン
アート＞ファッション
各種情報と情報源
表 5． 類 似 ス コ ア に よ る 共 起 カ テ ゴ リ 上 位 10
70
＊
テ レ ビ 朝 日 は 実 際 の 利 用 頻 度 に +15
60
50
利 用 頻 度
40
30
20
10
0
時間(9/1∼10/31)*1時間毎の推移
ニュース>テレビ>番組>アクション>仮面ライダー
ビジネス>ショッピング>ニュースとメディア>テレビ局>テレビ朝日
表 9.意 味 の 近 い 共 起 関 係
（3 位の共起カテゴリの利用頻度パターン）
バーストの利用頻度の大きさを考慮することにより
意味の近く，かつ利用の大きい関係が見つけられると
考えられる．1 位と 2 位の共起カテゴリはテレビ番組
とテレビ局の関係が強いことを示している．3 位の仮
面ライダーの番組はテレビ朝日で放映されており，そ
の仮面ライダーを調べるためにテレビ朝日を訪れる関
係があると考えられる．両カテゴリのウェブページで
時間帯別利用型によるカテゴリ類似判定によるカ
テゴリの特徴分析を行った．また共起カテゴリ発見に
検討する必要がある．本稿で提案した手法はネットワ
文
献
[1] C. Wang and X. S. Wang “Multilevel filtering for
high dimensional nearest neighbor search,” In ACM
SIGMOD Workshop on Research issues in Data
Mining and Knowledge Discovery, 2000
[2] D. Rafiei and A. Mendelzon “Efficient retrieval of
similar time sequence using dft,” In Proceedings of
FODO, 1998
[3] J. Allan, J. Carbonell, G. Doddington, J. Yamron, and
Y. Yang: “Topic Detection and Tracking Pilot Study
Final Report,” Proceedings of the Broadcast News
Transcription and Understanding Workshop1998
[4] M. Vlachos, C. Meek and Z. Vagena“ Identifying
Similarities, Periodicities, and Bursts for Online
Search Queries,” In Proceedings of SIGMOD, 2004
[5] M. L. Hetland, “A SURVEY OF RECENT
METHODS FOR EFFICIENT RETRIEVAL OF
SIMILAR TIME SEQUENCES,” Data Mining In
Time Series Databases (Series in Machine Perception
and Artificial Intelligence) , ISBN: 9812382909,
pp23-40
[6] N. Beckmann, H.-P. Kriegel, R. Schneider, and B.
Seeger “The r*-tree: An efficient and robust access
method for points and rectangles,” In proceedings of
ACM SIGMOD, 1990
[7] R. Agrawal, C. Faloutsos, and A. Swami “Efficient
Similarity Search in Sequence Databases,” In
Proceedings of the 4 t h FODO, pp69-84, 1993
[8] DMOZ(http://dmoz.org/)
[9] Google(http://www.google.co.jp)
[10] MSN(http://www.msn.com)
[11] Yahoo!カ テ ゴ リ (http://dir.yahoo.co.jp)
[12] 大 塚 真 吾 ， 豊 田 正 史 ， 喜 連 川 優 “ Web コ ミ ュ ニ
テ ィ を 用 い た 大 域 Web ア ク セ ス ロ グ 解 析 法 の 一
提 案 ，” 情 報 処 理 学 会 研 究 報 告 ,
2003-DBS-131(Ⅱ ),pp101― 108,
2003