HistoryPaper: ユーザー個人のブラウザ履歴からの代表ページ選択とマガジンスタイルレイアウト
理学専攻

情報科学コース 松枝知香 (指導教員：伊藤貴之)

概要1

表 1: 各長方形領域の理想的なアスペクト比表示タイプ
横 / 縦 (画像位置)

ブラウザの閲覧履歴は，ユーザ自身の行動や，獲得した知識についての情報を含んでいる．そのためインターネットを毎日利用する人の閲覧履歴を要約することは，その人の行動や知識の要約につながると考えら

画像有(上)0.9，1.6 (左)3.0，3.8

画像無1.0，3.8，5.0

れる．しかし，現在のブラウザに実装されている閲覧約の目的で代表文書を選出する手法として，tf-idf 法

履歴の表示方法だけでは，そのような情報を有用活用によって測った重要度の高い文書を重複を避けて抽出することは簡単ではない．本研究では，1 日の閲覧履することで，満足度の高い結果がでる傾向があること歴の中で特に重要であると判断した Web ページ群をが知られている [1]．本手法ではこの知見を利用して，抽出し，それらを新聞のようにレイアウトすることで，閲覧履歴を構成する Web ページ群に対して文書内容ユーザーの毎日の行動や獲得知識を要約表示するシスの類似度に基づくクラスタリングを適用し，各クラステムを提案する．提案手法ではまず，閲覧履歴を構成タの中から最も重要度の高いものを選ぶことで，履歴する Web ウェブ群を文書内容でクラスタリングし，続の要約となる Web ページ群を構成する．以下に代表

いて検索キーワード，アクセス貴重度から定義される重要度を算出して各クラスタから代表 Web ページをWeb ページ群の選出手法を示す．
まずはじめに１日の履歴にある全ての Web ページ選出する．続いて，最近の Web サイトに多く採用さの内容を対象として，以下の文書クラスタリング手法れているマガジンスタイルを模倣するレイアウトアルを用いて n 個のクラスタに分類する．

ゴリズムによって，代表 Web ページ群を一画面に配1. Web ページの内容を Bag-of-Words 表現に変換置して一覧表示する．

2. 潜在的意味解析で Bag-of-Words を次元削減

マガジンスタイル23. 潜在的意味空間に位置する各 Web ページを最短

マガジンスタイルは，その名の通り雑誌のようなレ距離法を用いてクラスタリングイアウトのことである．様々な大きさの四角形を多数続いて各クラスタについて，検索キーワードのうち画面上に敷き詰め，その中に文字や画像を当てはめて当該 Web ページに載っているキーワードの延べ数とコンテンツを表示させるこのスタイルは，普段から雑アクセスの貴重度を考慮し各クラスタの代表ページを誌を読むユーザにとっても見慣れたものであり，多く決定する．また，クラスタに含まれる Web ページののコンテンツが詰まっていてもコンテンツの内容を理延べ数をクラスタの重要度とし，代表ページを配置す解しやすい．

る際に専有する面積を決定するときに利用する．

マガジンスタイルは俗称であり，それがどのようなレイアウトであるかの明確な定義は我々の知る限り見3.2当たらない．そのため自身の観察結果にもとづいて，3.2.1

本研究におけるマガジンスタイルの生成方針を以下のレイアウトアルゴリズム
予備実験

マガジンスタイルのレイアウトアルゴリズムの開発ように定義した．に先立ち，我々は Squalified Treemap[2] による配置を定義 (1) カラムレイアウト試みた．その結果，2 章のマガジンスタイルの定義のうち，Treemap は定義 (1)(2) を満たすが，定義 (3)(4)

定義 (2) 重要な記事ほどスペースが大きいを満たすことが難しいことがわかった．

定義 (3) 各長方形領域のアスペクト比は表 1 に準ずる

3.2.2

定義 (4) 同じ大きさの長方形領域が複数隣り合わさる

3

提案手法

3.1

代表 Web ページの選出

Web ページ群のデータ構造

本節でのアルゴリズムの説明に先立ち，以下のようにクラスタの集合を定義する．

• R: クラスタの集合 (3.1 節に示した処理で生成する)本手法ではまず，1 日の履歴を構成する各 Web ペー• G: 1 個以上のクラスタで構成されるクラスタグループの集合

ジの重要度を計算し，その結果から履歴を要約するための代表 Web ページ群を選出する．ここで文書群の要1

また，以下の変数を定義する．

ペースの左上に仮配置を行う (図 2 1.(a)(b))．左下にできたスペースにできるだけ適応する |G| の• |S|: 集合 S に含まれる集合の数要素の組み合わせを選び，左下の面積占有度と |G|• areaS : 集合 S 全体の面積占有度• priorityS : 集合 S 全体の合計クラスタ重要度の要素の組み合わせの差が１番小さい組み合わせを選ぶ (図 2 1.(a)(b) 3.)．

• ratioS : 集合 S 全体のアスペクト比群 (表 1 参照)• typeR : クラスタ画像の有無• W , H: 配置に用いる画面の横幅，縦幅 (定数)2. |G| が 3 以上の場合 1. を繰り返す．|G| が 2 以下の場合，同じ G の要素は縦もしくは横に等分割• Wmin ， Hmin : 各クラスタが配置される長方形領域の最小横幅，縦幅 (定数)3.2.3する (図 2 4.)．G の要素の組み合わせであれば面積占有度の比率に縦もしくは横分割する (図 2 5.

6.)．

クラスタのグループ化

本手法では以下の式を満たす場合に Ri と Rj の 2 ク

4

実行結果

ラスタを同一グループに所属させる (図 1(1))．ただし，4.1

アルゴリズムの適用

Ri が既に他のグループに所属している場合，typeRi とtypeRj が違う場合には，この処理を適用しない．
priorityRj ≤ ⌈(priorityRi × 1.2)⌉(1)

図 3: 配置結果
図 1: 面積占有度の算出

3.2.4

図 1 のデータを用いて，提案手法を実行した例を図3 に示す．画面全体を大きく縦に分割し，それをさらに分割して，重要度に応じた面積を割り当てて各ペー各クラスタの面積占有度

各クラスタの重要度をデフォルメした値を，配置する

ジを表示していることがわかる．また，同じ大きさの長方形領域の面積占有度として算出する．各クラスタ

ページを並べたレイアウトが随所に見られることがわの重要度をそのまま面積占有度としない理由は，3.2.1かる．以上により，提案手法が 2 章で論じた定義に近節であげた問題点を解決するためである．

areaRi =3.2.5

priorityRi

WH

priority R Wmin Hmin

いレイアウトを実現できていることがわかる．

4.2

(2)

ユーザテスト

20 代女性 10 人に HistoryPaper を実際に利用して配置アルゴリズムもらい，ユーザアンケートを行った．その結果 9 人のユーザが，HistoryPaper を用いることによって数日前に行ったが既に忘れていた行動を思い出すことがあったと答え，HistoryPaper が 1 日を振り返ることの一助になることがわかった．

参考文献[1] Genest, P. E., et al. A symbolic summarizer for
the update task of tac 2008. In Proceedings ofthe First Text Analysis Conference, Gaithersburg, Maryland, USA. National Institute of

図 2: レイアウトアルゴリズム

Standards and Technology. (2008)1. 面積占有度の平均が最大であるクラスタグループを抜き出し，表 1 で取りうるすべての比率でス[2] Bruls, M. et al, Squarified treemaps, Data Visualization 2000, 33-42 (2000).
2