BrowseRank

概要

BrowseRankは、Microsoft Research Asia によって提案されたウェブページの重要度評価アルゴリズム

  • 従来のリンク構造ベースの手法（例：PageRank）に比べて、ユーザーの関心をより直接的に反映する点が特徴

連続時間マルコフモデル（Continuous-Time Markov Chain）

定義：

\[\pi Q = 0\]

ユーザの挙動：

  • ユーザーはページ $i$ に平均 $\frac{1}{\theta_i}$ 時間滞在し、その後ページ $j$ に遷移する確率は $P_{ij}$
  • この行動は「待ち時間（指数分布）＋確率的遷移」のセットで表現される

滞在時間の分布：

  • ユーザーのページ滞在時間は指数分布に従うと仮定：

    \[f_i(t) = \theta_i e^{-\theta_i t}\]

    （平均滞在時間 = $\frac{1}{\theta_i}$）

Q行列の定義：

  • 非対角要素 $q_{ij}$（$i \ne j$）：
\[q_{ij} = \theta_i \cdot P_{ij}\]
  • 対角要素 $q_{ii}$：
\[q_{ii} = -\sum_{j \ne i} q_{ij} = -\theta_i \cdot \sum_{j \ne i} P_{ij} = -\theta_i\]

問題点：

  • 連続時間マルコフ過程を直接扱うと、指数分布付きの確率微分方程式を解く必要があり、非常に複雑

上記問題解決のために離散時間マルコフ連鎖（DMC）に変換

  • $N_{ij}$：ページ $i$ からページ $j$ への遷移回数
  • $T_i$：ページ $i$ への滞在総時間
  • $N_i$：ページ $i$ からの遷移数

ステップ1: ダミーノードの追加

  • 意味：セッションの終了や、ジャンプ先の不明な遷移を吸収するノード
  • 実装上は、ユーザーがセッションを終了する／どこにも行かず終わるという状態をモデル化する

ステップ2: 遷移確率行列 $P$ を構築

\[P_{ij} = \frac{N_{ij}}{N_i}\]

ステップ3: 離散時間マルコフ連鎖の定常分布 $\tilde{\pi}$ を求める

\[\tilde{\pi}^T = \tilde{\pi}^T P\]
  • 通常のPageRankと同様にパワーイテレーションで求められる

ステップ4: 各ページの平均滞在時間（＝$\frac{1}{\theta_i}$）を使ってBrowseRankを求める

\[\pi_i = \frac{\frac{1}{\theta_i} \cdot \tilde{\pi}_i}{\sum_j \frac{1}{\theta_j} \cdot \tilde{\pi}_j}\]

この $\pi_i$ がBrowseRankスコア

BrowseRankを適用して実験

適用するにあたって以下の改変を加える

  • ノード間の遷移率はClickStream数（あるいはその逆数）を正規化したもの
  • 疑似ノードへの遷移率は他にエッジがないノードのみ1、それ以外は0
  • 疑似ノードからの遷移率及びランダムジャンプにおける遷移率はDirectAccess数を正規化したもの
  • $\theta$はDirectAccess数の逆数
種類 DF 指標 Spearman順位相関係数 p値 Pearson相関係数 p値
DA - 人気度 0.3390 3.5002e-28 0.1842 4.8490e-09
BR(順) 0.85 人気度 0.4005 1.2522e-39 0.1602 3.7591e-07
BR(逆) 0.85 人気度 0.4595 4.0872e-53 0.2186 3.1509e-12
DA - 知名度 0.1595 4.2521e-07 0.0283 3.7189e-01
BR(順) 0.85 知名度 0.2495 1.3924e-15 0.0512 1.0629e-01
BR(逆) 0.85 知名度 0.3159 1.7297e-24 0.0766 1.5685e-02

重み付きPageRankを適用して実験

種類 自己遷移率 DF 指標 Spearman順位相関係数 p値 Pearson相関係数 p値
DA - - 人気度 0.3390 3.5002e-28 0.1842 4.8490e-09
PR(順) 0 1 人気度 0.3620 3.5703e-32 0.0140 6.6026e-01
PR(順) 0 0.9 人気度 0.3630 2.3611e-32 0.0190 5.4918e-01
PR(順) 0.1 1 人気度 0.3630 2.3611e-32 0.0190 5.4918e-01
PR(順) 0.5 1 人気度 0.3666 5.1557e-33 0.0629 4.7257e-02
PR(順) 0.1 0.9 人気度 0.3636 1.8709e-32 0.0259 4.1435e-01
PR(逆) 0 1 人気度 0.4237 1.2734e-44 -0.0600 5.8408e-02
PR(逆) 0 0.9 人気度 0.4236 1.3217e-44 -0.0618 5.1188e-02
PR(逆) 0.1 1 人気度 0.4236 1.3217e-44 -0.0618 5.1188e-02
PR(逆) 0.5 1 人気度 0.4262 3.4528e-45 -0.0601 5.8146e-02
PR(逆) 0.1 0.9 人気度 0.4241 1.0436e-44 -0.0617 5.1523e-02
DA - - 知名度 0.1595 4.2521e-07 0.0283 3.7189e-01
PR(順) 0 1 知名度 0.3051 7.0692e-23 -0.0011 9.7262e-01
PR(順) 0 0.9 知名度 0.3062 4.8450e-23 0.0042 8.9550e-01
PR(順) 0.1 1 知名度 0.3062 4.8450e-23 0.0042 8.9550e-01
PR(順) 0.5 1 知名度 0.3096 1.4970e-23 0.0452 1.5427e-01
PR(順) 0.1 0.9 知名度 0.3075 3.0652e-23 0.0105 7.4153e-01
PR(逆) 0 1 知名度 0.3776 4.5351e-35 -0.0695 2.8280e-02
PR(逆) 0 0.9 知名度 0.3775 4.6204e-35 -0.0714 2.4281e-02
PR(逆) 0.1 1 知名度 0.3775 4.6204e-35 -0.0714 2.4281e-02
PR(逆) 0.5 1 知名度 0.3784 3.1586e-35 -0.0704 2.6321e-02
PR(逆) 0.1 0.9 知名度 0.3777 4.3971e-35 -0.0714 2.4355e-02

ClickStreamで無視されるリンクの抽出

ClickStreamでは、アクセス数が10未満のリンクは無視される

別のAPIからリンク一覧を取得し、リンクは存在するもののClickStreamでは除外されているものを固定値で適用する

種類 無いlinkの値 DF 指標 Spearman順位相関係数 p値 Pearson相関係数 p値
BR(逆) 0 0.85 人気度 0.4595 4.0872e-53 0.2186 3.1509e-12
BR(逆) $\frac{1}{9}$ 0.85 人気度 0.4495 1.2198e-50 0.1502 1.9319e-06
BR(逆) $\frac{1}{5}$ 0.85 人気度 0.4481 2.6886e-50 0.1496 2.1387e-06
BR(逆) 1 0.85 人気度 0.4461 7.8973e-50 0.1487 2.4475e-06
BR(逆) 0 0.85 知名度 0.3159 1.7297e-24 0.0766 1.5685e-02
BR(逆) $\frac{1}{9}$ 0.85 知名度 0.2424 8.9809e-15 0.0291 3.5899e-01
BR(逆) $\frac{1}{5}$ 0.85 知名度 0.2414 1.1742e-14 0.0291 3.5908e-01
BR(逆) 1 0.85 知名度 0.2400 1.6959e-14 0.0292 3.5748e-01