DEIM Forum 2009 A2-2

ODP とブックマークを利用したユーザプロファイル自動選択手法
神原 義明†
藤田博††

大石哲也†

長谷川隆三††

峯恒憲††

越村 三幸††† 九州大学大学院 システム情報科学府，〒 819-0395 福岡県福岡市西区元岡 744†† 九州大学大学院 システム情報科学研究院
E-mail: †kambara@ar.is.kyushu-u.ac.jp
あらまし

インターネットが急速に普及し，ユーザが目的のページを探すためにサーチエンジンを利用する機会が増えた．しかし，目的のページが検索結果の上位に存在しないことも多い．この問題を解決するための研究として，個人化検索 (Personalized Search) がある．個人化検索にはユーザの興味・関心を表すユーザプロファイルが必要であり，それはユーザの保有する文書などを分析することで生成される．我々は，Open Directory Project(ODP) を利用したユーザプロファイル作成手法及び，ブックマークを利用した個人化検索システムの検討を行ってきた．本稿では，個人化検索システムの拡張として，ユーザプロファイルの自動選択手法を提案し，実験の結果を示す．
キーワード

情報推薦, Personalized Search, Web 検索支援, ユーザプロファイル

A Method for Automatically Selecting User Profiles Created by ODPand Bookmarks
Yoshiaki KAMBARA† , Tetsuya OISHI† , Ryuzo HASEGAWA†† ,Hiroshi FUJITA†† , Tsunenori MINE†† , and Miyuki KOSHIMURA††† Graduate School of Information Science and Electrical Engineering, Kyushu University†† Faculty of Information Science and Electrical Engineering, Kyushu University
E-mail: †kambara@ar.is.kyushu-u.ac.jp
Abstract The user often uses search engines to search for his/her intended pages in the Internet. However, theintended pages do not always exist on the higher rank of the results. The personalized search is a promising approach
to solve this problem. In the personalized search, user profiles, which are often created from the documents of theuser to present his/her interests, are well used. We have proposed a method for generating user profiles based on
Open Directory Project (ODP) and a personalized search system using bookmarks as the documents for profiling.
This paper discusses a method for automatically selecting user profiles so as to enhance the system.
Key words Information Recommendation, Personalized Search, Web Retrieval Support, User Profiles

1. は じ め に合，たとえ上位に目的のページが存在しても必要数に満たないインターネットが急速に普及し，これに伴い Web 空間は年々ていくが，下位であるほど不必要なページが多く混在し，目的肥大化してきている．このような状況の中，目的の Web ペーなど不十分なことがある．ユーザはこれを補うために下位を見のページを探し出すのは困難になる．

ジを素早く探すために Web サーチエンジンを利用する機会がこれらの問題を解決するために，ユーザの「必要なもの」「興多くなっている．Web サーチエンジンの多くは，多数のユーザ味」に合わせた検索を行う技術，つまり個人化検索（Person-が求める Web ページを上位に表示している．

alized Search）が研究されている．個人化検索を行うためにしかし，検索時に利用する語句の多くは検索結果のページ数が莫大となる．仮にユーザの目的とするページが下位に存在すはユーザの興味・関心を分析し，ユーザプロファイル（UserProfile, UP）として表現しなければならない．

れば，ユーザが目的のページを探し出すのは困難である．また，ユーザの興味・関心を分析する対象として，ユーザが保有すユーザがある目的に関連するページだけを大量に探したい場

る Personal Document(文書)，具体的には E-mail やユーザの過去の閲覧ページ履歴などがある．
本研究におけるユーザプロファイル作成手法では Open Di-rectory Project（ODP）（注 1）を利用する．
ODP を検索システムに利用する研究は現在までにいくつか存在している．しかし，これらの多くは Web ページが ODPのどのカテゴリに属すかという情報を利用しており，ODP に属する Web ページの内容にまで着目したものはない．そこで
我々は，Web ページの内容そのものにも着目することで，より細かい情報を取得する．

図 1 Open Directory Project

我々は上記のユーザプロファイル作成手法を用いた個人化検表 1 ユーザプロファイル (例)索システムとして，Personal Document にブックマークを用いたシステムを提案した [10]．しかし，このシステムは検索の際，使用するユーザプロファイルをユーザが選択していた．この負ユーザ

アート

スポーツ

コンピュータ

A

0.4

0.1

0.5

B

0.2

0.7

0.1

担を軽減するため，本稿ではユーザプロファイルの自動選択手法を提案する．更に，上記のシステムに組み込み，評価実験を行う．と最も近い保存ノードを決定，もしくは作成する．そして新たな特徴語を保存し，不要ノードの削除や統合を行ってプロファ

2. 関 連 研 究

イルの更新をする．

[3] や [4] ではクエリを曖昧，半曖昧，明確と分類して研究を岩崎らのシステムは，ユーザの細かい興味状況に対応した検行っている．また Z. Dou らは，ユーザプロファイルは使用す索結果を返すことができる．しかし，ユーザが曖昧なクエリ

る Personal Document により性質が変化する特徴を持つと述を用いて検索を行った場合，正しく興味を判断できるとは限らべており，この特徴を長期的ユーザプロファイル（日常的な趣味・興味など），短期的ユーザプロファイル（その場限りの調べものなど）と表現した [5]．更に，長期的ユーザプロファイルと短期的ユーザプロファイルは同時に対応することが困難なた
め，[3] や [4] によるクエリの分類を基にそれぞれの特徴を調べるない．本研究では，ブックマークのフォルダごとにユーザプロファイルを作成する．そして，ユーザが目的に合わせて使用するユーザプロファイルを選択することで，曖昧なクエリにも対応した個人化検索を行う．

3. ODP を利用したユーザプロファイル作成実験を行った．その結果，明確なクエリには短期的ユーザプロファイルを，曖昧，半曖昧なクエリには長期的ユーザプロファイルを利用すると効果が高いことを示した．本研究では，ブックマークを利用することで長期的ユーザプロファイルに特化したシステムを提案する．
ユーザプロファイリングの技術の研究としては [6] [1] などがある．F.Qiu らは，ユーザのクリック履歴に基づいて ODP の最上位カテゴリごとに評価を与え，ユーザプロファイルを作成した [6]．これは，長期的ユーザプロファイルに特化したシステムである．Sieg らは，ユーザの振る舞い（Web 閲覧履歴やブックマークなど）から作成・更新するオントロジーベースのユーザプロファイルを開発した [1]．
岩崎らは，検索結果から df の平方根をとった TF-IDF 法を用いて興味語を抽出した [8]．更に，これを基に木構造を持つプロファイルを作成し，クエリに応じて自動的に興味状態を判断する検索システムを開発した [9]．木構造の各ノードはユーザの興味状態を表し，興味語が保存される．ユーザが検索を行った時，システムは検索結果から抽出した特徴語の出現ページ数とプロファイルの各ノードの興味語を基に興味ノードを決定す3. 1 Open Directory ProjectOpen Directory Project(ODP) は，Web ページを階層的なカテゴリ（話題）に分類した世界最大の Web ディレクトリである．図 1 に ODP の概要を示す．

ODP では，人手によって Web ページをその内容に該当するカテゴリに分類する．このことから，ODP の Web ページに出現する単語は，Web ページが属するカテゴリ（話題）に関連する可能性が非常に高い．また，人手によって Web ページが分類されているためカテゴリが細かい．また，原則として 1 つのページは 1 つのカテゴリにしか登録されない（注 2）．
本研究で提案するユーザプロファイル作成法は，ODP のこのような性質を利用する．

3. 2 ユーザプロファイル作成
本研究のユーザプロファイルは，ODP の最上位カテゴリ（注 3）をインデックスとし，各カテゴリへの興味を数値で表したベクトルで表現される．
表 1 はカテゴリが「アート」「スポーツ」「コンピュータ」の3 つであった場合の例である．ユーザ A は「スポーツ」にはある．この興味ノードとその親ノードの興味語を基に検索結果の各ページの重要度が決定され，Reranking が行われる．ユーザが検索結果からあるページを閲覧した場合，そのページの特徴（注 2）：例外： 地域 に関する内容の場合， 地域 とそれ以外の 2 箇所に登録されることがある（注 3）：「アート」,「オンラインショプ」,「ゲーム」,「コンピュータ」,「スポーツ」,「ニュース」,「ビジネス」,「レクリエーション」,「家庭」,「科学」,「各（注 1）：Open Directory Project: http://www.dmoz.org/

種資料」,「健康」,「社会」,「地域」の 14 項目

表 2 単語の出現例

まり興味がないが「アート」と「コンピュータ」には同程度の単語興味を持っている．一方，ユーザ B は「スポーツ」に大きな興味を持っており，他の 2 つにはあまり興味を持っていない．こアート

スポーツ

t1

サッカー

234

コンピュータ1t2

本

15813のようなベクトルがユーザプロファイルである．
次に，提案手法におけるユーザプロファイル作成の手順を

表 3 エントロピー Hti と基本評価値 wti示す．

Htiwti

t1

サッカー

0.48

1.11

t2

本1.54

0.05

単語

【手順 1】ODP の出現単語分析

・ODP からの単語抽出領域
まず，ODP の各カテゴリから，そのカテゴリに出現する単語表 4 単語の重みを形態素解析ツール MeCab（注 4）を用いて抽出する．この際，単単語

アート

スポーツ

コンピュータ語の抽出領域として 2 通りが考えられる．1 つは，カテゴリに

t1

サッカー0.06

1.020.03

属している Web ページの内容そのものを抽出領域とする．もt2

本0.020.010.02

う 1 つは，ODP の各カテゴリに付与された，カテゴリに属するページを表すタイトルと紹介文を抽出領域とする．前者は出ゴリにのみ出現するとき，このエントロピー Hti は最小値 0 を現する単語数が多くなりより詳しくそのページの特徴を捉えらとる．エントロピー Hti を用いて以下の式 (2) の通り基本評価れる．しかし，不要な語や一般的な語などのノイズが増える．

値 wti を定義する．

後者は，出現単語数こそ少ないが，そのページを端的に表す単語が抽出できる．この理由から，本手法では後者の抽出領域を利用している．

wti = log(Nc ) − Hti(2)

基本評価値 wti は単語 ti が特定のカテゴリ内で偏って出現す・単語の重み計算
次に，抽出した単語 ti の各カテゴリ cj に対する重み W (ti , cj )を計算する．重みとは，単語の各カテゴリに対する関連度のことである．例えば，単語「野球」を考える．
「野球」はカテゴリ「スポーツ」への関連が高く，W ( 野球 , スポーツ ) はるほど大きな値をとる．このことにより，偏りが大きい単語はそのカテゴリを特徴付ける単語として有用である．
以上で求められた基本評価値 wti と出現割合 Pti (cj ) を基に，カテゴリ cj に対する単語 ti の重み W (ti , cj ) を以下の式 (3) で定義する．

高い値をとる．しかし，カテゴリ「アート」に対しては関連が低いため，W ( 野球 , アート ) は低い値となる．本手法でW (ti , cj ) = Pti (cj ) × wti(3)は，ODP の最上位カテゴリの Web ページ群から抽出した単語
この式を ODP 内の全ての出現単語 ti に用いて重みを算出の出現頻度を基に各カテゴリへの重みを算出する．
あるカテゴリに偏って多く出現する単語はそのカテゴリへのする．

関連性が高く，カテゴリを特徴付ける単語として有用である．

表 2 に単語の出現例を，表 3 に算出したエントロピーと基本

一方，様々なカテゴリに同頻度で出現する単語は各カテゴリへ評価値を示す．カテゴリ「スポーツ」に偏った単語 t1 のエントの関連性が低く，特定のカテゴリを特徴付ける単語としては有ロピー Ht1 は 0.48 と小さい値をとり，基本評価値 wt1 は式 (2)用でない．

より 1.11 となる．一方，単語 t2（本）は各カテゴリに似通った

そこで，カテゴリでの単語 ti の出現の偏りをエントロピーを頻度で出現している．この場合，エントロピー Ht2 は 1.54 と用いて求め，各単語 ti がカテゴリを特徴付けるために有用かど

最大値 log(3) = 1.59 に近い値となり，基本評価値 wt2 は 0.05

うかを評価した基本評価値 wti を算出する．式 (1) に単語 ti のと小さい値になる．
得られた基本評価値 wti を基に式 (3) を用いて計算した重みエントロピー Hti を表す．

Hti = −X

を表 4 に示す．表 4 から，特定のカテゴリで偏って出現する単Pti (cj ) × log(Pti (cj ))(1)j

語「サッカー」は，それ自身が多く出現するカテゴリに対して重みが大きくなり，そのカテゴリへの関連度が大きくなる．ま•n(ti , cj )：カテゴリ cj 内の単語 ti の出現頻度

た，どのカテゴリにも均等に出現する単語「本」はどのカテゴ•

Nti =リに対しても重みは小さくなる．

P

jn(ti , cj )：全カテゴリにおける単語 ti の総出現頻度•

Pti (cj ) = n(ti , cj )/Nti ：全カテゴリにおけるカテゴリ

cj 内の単語 ti の出現割合
単語 ti が全カテゴリで等しく出現するとき，即ち Pti (cj ) =【手順 2】

Personal Document の出現単語抽出

本手法ではユーザプロファイルを作成するために，ユーザの興味が現れる文書（Personal Document）を用いる．ここでは，ODP での単語抽出と同様に，Personal Document に出現した1/Nc (j = 1 · · · Nc , Nc：カテゴリの総数) のとき，エントロピー単語（User Term：ut）が抽出される．

Hti は最大値 log(Nc ) をとる．また，単語 ti がある 1 つのカテ

【手順 3】 ユーザプロファイル作成
手順 1 で計算した重み W (ti , cj ) と手順 2 で抽出した User

（注 4）：MeCab：http://mecab.sourceforge.net/

Term を用いて，以下の式 (4) でユーザプロファイルのカテゴ

ジベクトルの作成手法は 3. 2 節のユーザプロファイル作成手法

表 5 Personal Document の単語出現頻度（例）
サッカー本

413出現頻度と同様だが，抽出領域として SNIPPET（検索結果に表示される各ページの説明文）を利用する．そして，これらのページベ
クトルの平均をとることで，検索クエリの特徴を表すクエリベ

リ値 Ucj を定義する．本手法では，この値をユーザのカテゴリcj への興味の度合いとする．
Ucj =

X

Nuti × W (uti , cj )クトル QV を作成する．
この際，比較のため 3 つの領域から平均をとった．

(4)i

QV1 検索結果の上位 10 件
QV2 検索結果の上位 5 件と 20 位〜25 位
QV3 検索結果の上位 10 件と 40 位〜50 位•uti：User Term•

Nuti ：単語 uti の Personal Document 内での出現頻度

ブックマークの特徴を反映させるためのブックマークベクト

カテゴリ値 Ucj は uti のカテゴリ cj への重みと uti の Per-

ル BV を作成する．ブックマークベクトル BV は 2 種の手法

【2】

sonal Documents 内での出現頻度の積を全ての uti で足し合わせたものである．

により作成した．

BV1 各ユーザプロファイルの高い値を考慮

全てのカテゴリに関して式 (4) を適用すると，最終的にユーザプロファイルは以下のベクトル UP で表現される．尚，ユー

BV2 BV1 に加え，各フォルダのページ登録数を考慮(6) にブックマークベクトルの計算式を示す．

ザプロファイルは |UP| = 1 となるように正規化して用いる．

UP = [Uc1 , Uc2 , · · · , UcNc ]ブックマークからユーザの特徴を反映する

(5)

bvj =


 0

して，Personal Document で「サッカー」と「本」の 2 つの単

aj =語の出現頻度は表 5 の通りである．この場合のユーザプロファ
イルを式 (4) を用いて求めると UP = [0.12, 0.99, 0.08] となる．
カテゴリ「スポーツ」の値が他に比べて大きいので，このユーaj(6)k

手順 1 で利用した例におけるユーザプロファイルの計算例と語のみが抽出された場合を考える．Personal Document での単X

(bmupkj < 0.5)

1

(bmupj >= 0.5 かつ BV1 のとき)

xk

(bmupkj >= 0.5 かつ BV2 のとき)

xk =BMUPk のページ登録数
BMUPk の平均ページ登録数【3】

ユーザプロファイルの自動選択を行う

ザプロファイルを持つユーザは「スポーツ」への興味が大きいことになる．

4. ユーザプロファイルの自動選択手法
4. 1 背景【1】で算出されたクエリベクトル QV と，【2】で算出された BV をそれぞれ大きさ 1 で正規化する．そして，これらを各要素ごとに掛け合わせることで特徴ベクトルを作る．

従来の我々のシステム [10] は，上記の提案手法を使用し，ユー最後に，ユーザのブックマークの各フォルダから作成した

ザのブックマークにおける各フォルダごとにユーザプロファイル

ユーザプロファイル BMUPk と，上記の手法で作成した特徴を作成する．ここで，作成したユーザプロファイルを BMUPk

ベクトルのコサイン類似度を算出する．この類似度が高いユー（k = 1, . . . , n，n : ブックマーク内の未分類を含むフォルダ数）

ザプロファイル BMUPk を Reranking の際に用いる．ただし，とする．検索の際にユーザがユーザプロファイルを選択するこ

類似度 (0〜1) が 0.6 未満の場合は「該当なし」と判断する．ことにより，検索結果の精度を向上させていた．の場合，永田が提案した手法 [7] （ユーザが検索結果で最初にしかし，この作業はユーザの負担になる上，ユーザがクエリクリックしたページからユーザプロファイルを作成する）によと目的に沿ったユーザプロファイルを選択できるとも限らない．

り Reranking を行う．

例えば，検索クエリが「Google」などの明確なクエリである場

5. 評 価 実 験合は，選ばれるべきユーザプロファイルは 1 つにしぼられるだ
ろう．だが「マック」という検索クエリは，「マクドナルド」と

5. 1 目的「マッキントッシュ」の 2 つの意味が考えられる．このように

4. 節で提案したユーザプロファイル自動選択手法を評価する．

複数の意味が考えられる曖昧なクエリであった場合は，ユーザユーザの検索目的と合致したユーザプロファイルが選択されてプロファイルを一意に選択することは難しくなる．このことかいるか，システムを利用した Reranking の結果が良いかの 2 点ら，ユーザがより簡単に精度の高い検索を利用できるように，に着目し検証を行う．

ユーザプロファイルの自動選択手法を考えた．

4. 2 ユーザプロファイル自動選択手法

5. 2 実 験 手 順
実験を行うにあたり，数名の協力者からブックマーク，クエ以下に，本手法の流れを示す．

リ，クエリの目的，ユーザが手動で選択する場合のユーザプロ【1】

ファイルのデータを頂いた．これらを用いて 10 件のクエリに検索クエリから特徴を抽出する

まず，検索結果の各ページのページベクトルを計算する．ペー対して実験を行う．

表 6 各 UP 選択手法における評価値の平均

ザプロファイルの中には手動で選択したユーザプロファイルよ上位 10 位り結果が良くなるものもあった．ユーザが持つブックマークのUP 選択手法

上位 20 位MAP 向上率 MAP 向上率

フォルダへのイメージと実際に登録されている Web ページ，検初期検索

0.702–

0.660–

手動

0.822

1.170.792

1.20

QV1(1)

0.578

0.82

0.559

0.85

QV1(2)

0.769

1.100.687

1.04

QV1BV1(1)

0.652

0.93

0.614

0.93

QV1BV1(2) 0.769

1.100.687

1.04

今回は，クエリベクトルを作成する際に検索結果をそのまま索の目的のページの特徴が噛み合っていない場合にこのような現象が起こると考えられる．今後，このようなユーザプロファイルがどんな特徴を持つクエリに存在し，どのように対処できるのかを考察する必要がある．

QV1BV2(1)

0.578

0.82

0.551

0.83

利用していた．今後は，検索結果の各ページの特徴を算出し，QV1BV2(2)

0.621

0.88

0.592

0.90

各カテゴリに偏ったページの数などを利用することにより，クQV2(1)

0.621

0.88

0.592

0.90

エリの特徴をより明確して，ユーザプロファイルの自動選択のQV2(2)

0.592

0.84

0.587

0.89

精度を上げていく．

QV2BV1(1)

0.623

0.89

0.609

0.92

QV2BV1(2) 0.740

1.05

0.682

1.03

QV2BV2(1)

0.621

0.88

0.592

0.90

QV2BV2(2)

0.592

0.84

0.587

0.89

QV3(1)

0.578

0.82

0.551

0.83の紹介と，ブックマークから作成したユーザプロファイルの自QV3(2)

0.641

0.91

0.605

0.92

動選択手法の提案を行った．

QV3BV1(1)

0.640

0.91

0.610

0.92

実験の結果，初期検索結果より良い結果を出すユーザプロQV3BV1(2)

0.592

0.84

0.587

0.89

ファイルの選択はできるものの，ユーザが手動で選択するユーQV3BV2(1)

0.578

0.82

0.551

0.83

ザプロファイルが最も良い結果を示していた．しかし，ユーザ

QV3BV2(2)

0.621

0.88

0.592

0.90

6. お わ り に
本稿では，ODP を利用したユーザプロファイルの作成手法が手動で選択したユーザプロファイルより結果が良くなるユーザプロファイルも存在した．今後は，システムが抽出するクエ

まず，3. 2 節の手法に基づきブックマークから各ユーザプロリの特徴とユーザが意図するクエリの目的が一致するように，ファイルを作成しておく．次に，クエリを入力し，初期検索をユーザプロファイル自動選択手法を改善していく必要がある．

行う．そして，4. 節で提案した手法に基づきシステムで使用すまた，今回の実験はデータ数が少なくため，個人化検索シスるユーザプロファイルを決定し，Reranking を行う．検索結果テムとして多くのユーザに利用してもらい，明確な指標に基づは提案手法のクエリベクトル QV とブックマークベクトル BVいてシステムの改善に取り組んでいきたい．の組み合わせによる 18 パターンに加え，ユーザが手動でユーザプロファイルを選択する場合，初期検索の 20 パターンが存在する．これらの検索結果における上位 10 位と上位 20 位の謝辞 本研究は科研費（20240003）の助成を受けたものである．

Mean Average Precision（MAP）とそれらの向上率を計算することで評価を行う．検索結果の各ページの評価は，クエリの目的に沿うか沿わないかの 2 値で判断する．

5. 3 結果・考察
表 6 に各評価値の平均を示す．UP 選択手法における括弧内の数字は特徴ベクトルとの類似度が高いユーザプロファイル 1
位 2 位を表している．
この結果を見ると，提案手法では QV1(2)，QV1BV1(2)，QV2BV1(2) が MAP 向上率が高い．これは，初期検索と比べると結果が良くなってはいるが，手動で選択したユーザプロファイルを用いた結果には劣っている．このことから，よりユーザの意図やクエリの意味を抽出し，手動で選択するユーザプロファイルを自動で選べるようにする必要性が確認できた．
提案手法のそれぞれのパターンを細かく検証すると，クエリベクトル QV においては検索結果の上位の情報のみを利用した QV1 の精度が良い．ブックマークベクトル BV においては，ユーザのブックマーク内にある Web ページの傾向を利用したBV1（Web ページ登録数は利用しない）が良い結果を示していた．
更に実験結果を細かく見ていくと，自動で選択されたユー

文

献[1] A.Sieg, B Mobasher R.Burke. Web Search Personalization
with Onotological User Profiles. In Proc. of CIKM ’07, 2007.
[2] L.Page, S.Brin, R.Motwani, and T.Winograd. The PageRank Citation Ranking: Bringing Order to the Web.
http://google.stanford.edu/˜backrub/pageranksub.ps, 1998.
[3] P.A.Chirita, C.Firan, and W.Nejdl. Summarizing local context to personalize global web search. In Proc. of CIKM ’06,
2006.
[4] P.A.Chirita, W.Nejdl, R.Paiu, and C.Kohlschütter. Usingodp metadata to personalize search. In Proc. of SIGIR ’05,2005.
[5] Z.Dou, R.Song, and J.Wen. A Largescale Evaluation andAnalysis of Personalized Search Strategies. WWW 2007,
2007.
[6] F.Qiu, and J.Cho. Automatic identification of user interestfor personalized search. WWW 2006, 2006.
[7] 永田 廣人 他. ODP を利用したユーザプロファイル作成と個別化検索システムの提案. JAWS2007, 2007.
[8] 岩崎 周造 他. 興味単語を用いた個人化 Web 検索. 情報システ
ムソサイエティ誌, 2007 年総合大会特別号, p.76, 2007.
[9] 岩崎 周造 他. 構造化プロファイルを用いた個人化 Web 検索システム. DEWS2008 B2-6, 2008.
[10] 神原 義明 他. ODP とブックマークを利用した個人化検索シス
テム. JAWS2008, 2008.