22nd Fuzzy System Symposium (Sapporo, Sept. 6-8, 2006)

6B1-1

 広告動的配信システムへのマルコフモデルと  の応用   内野英治 Ý           森田博彦 Ý 

下野雅芳 ÝÝ      

Ý 財団法人ファジィシステム研究所

ÝÝ 株式会社キューブス       

        

                                     

インターネットの普及により，膨大な量の情報が容易に手に入るようになった反面，利用者が必要な情報に辿り着くのに時間がかかるようになった． 広告は，閲覧したホームページ上に自動的に掲示されるもので，利用者のニーズと一致すれば，短時間で目的の情報に辿り着くことができる．しかし多くの広告は，利用者の興味を全く無視して強制的に掲示しているだけである．
筆者らは，利用者が次に見たい情報を予測し，それに関する広告を配信する  広告配信システムを，およびマルコフモデルを応用して実現した．その効果を確認したのでここに報告する
ポータルサイトの利用者は，見たいカテゴリのボタンをクリックして情報を検索する．ポータルサーバーはカテゴリのクリック履歴をデータベースに保存し，利用者の興味の変化を解析できる．

マルコフモデルによる記述

ユーザが次に見るカテゴリーは，それまでにユーザが見たカテゴリー，すなわちユーザがそれまでに閲覧したカテゴリの履歴に影響を受ける．カテゴリ間の遷移は式!" に示される状態遷移確率行列 # で記述することが出来る$  

 

 %



 

  $ ! &     $ !

 $ ! &     !"&"'"

ここで，   はカテゴリ  からカテゴリ  へ遷移する確率を表している． は全カテゴリ数である．状態遷
移確率   は確率の条件式 &" と '" を満たしている．

                    広告配信モデル

はじめに         β            

             

マルコフモデルの作成

マルコフモデル (!) を作成するには，カテゴリの閲覧履歴データから状態遷移確率を推定しなければならない．
いま，時刻 % から時刻  までの状態遷移の履歴を         とする． は時刻  における状態である．
 を全カテゴリ数，状態   $  から状態  $  への遷移の回数を   とすると，履歴が         となる確率は，
¼  ½

½ ¾ 

$½ 

 "
  *"である．ただし，初期状態は与えられているものとする．   の推定値は最尤推定法により 次のように求めることができる．

$  +"マルコフモデルを用いた広告配信方法

具体的な広告配信方法としては，静的配信モデルと確率的配信モデルが考えられる．
静的配信モデルは，過去に利用者がそれぞれのカテゴリを訪問した回数の累積値に応じた分布により，広告を配信する方法である．確率的配信モデルは & つに分けられ，状態遷移確率に基づき，遷移確率が最も高いカテゴリの広告を配信する方法と，遷移確率に基づいて乱数を発生させ，次に遷移すると予想されるカテゴリの広告を配信する方法に分かれる．

重み付きマルコフモデル
マルコフモデルを用いた広告配信システムの欠点は，モデルの作成に多くの遷移履歴データを必要とすることである．そこで，モデル作成に要する時間を削減する方法として，重み付きマルコフモデルを用いた広告配信システムを提案する．

61



‫ޓ‬

多数の履歴データ
ᱜ
‫⸃ ޓ‬
‫₸ ޓ‬

ᱜ
‫⸃ ޓ‬
‫₸ ޓ‬





ユーザごとにログイン〜ログアウト間で区切る(セッションの特定)








 ᤨ‫ޓ‬㑆

セッション単位の履歴データ

図 &, 正解率の経時変化A

BCDEFઍ⴫ࡑ࡞ࠦࡈࡕ࠺࡞૞ᚑ඙㑆G

図 ', 代表マルコフモデ
ル作成区間別予測正解率

セッションごとのマルコフモデル作成

デル作成時期の影響を調べるため，それぞれ異なる過去の７つの区間で代表マルコフモデルを作成し，データの存在する最新の区間で予測正解率を評価した結果を図 'に示す．図 & および ' より，本システムが，0%23% ％の正解率で，ユーザが次に移るカテゴリを予測しているのがわかる．

ベクトル量子化

代表マルコフモデル

図 !, 代表マルコフモデルの作成手順

おわりに

重み付きマルコフモデルは，あらかじめ用意しておいた数個のマルコフモデル（代表マルコフモデル）を線形加算することにより，新たなマルコフモデルを作成する手法である．
まず，多数の履歴データ 各ユーザのカテゴリの遷移履歴データ" から各ユーザ毎のマルコフモデルを作成する．作成したモデルの遷移確率行列をベクトル量子化する．代表マルコフモデルの作成手順を図 ! に示す．本研究においては，代表マルコフモデルの作成に用いるベクトル量子化として，(&) を用いた．
ユーザモデルは，ログイン開始からの少ない履歴デー
タで作成された仮のユーザーのマルコフモデルと，各代表マルコフモデルとの類似度を計算し，その類似度に応じた重みで線形加算することにより推定する．

広告配信モデルの評価

ユーザが時刻 において閲覧した  ページのカテゴリを"，代表マルコフモデルが予測して配信した広告のカテゴリを - " として，正解率を以下のように定義する．

.
$


Æ.

Æ" - "" $" - ""       /"0" 利用者のカテゴリ遷移過程が，マルコフ過程で示されると仮定し，これを  広告配信システムに応用した．これにより従来の静的な配信モデルに比べ，ユーザの動きをダイナミックに予測する動的広告配信システムが実現できた．
システム実装時に予想されるサーバーの負荷を軽減するため，個々のユーザのマルコフモデルを，あらかじめ求めた代表マルコフモデルから推定する方法を提案し，その有効性を確かめた．
今後は実システムでの検証データを蓄積し，代表マルコフモデルの数の最適化や，モデルの更新頻度などを検討していく予定である．

謝辞
本研究を進めるにあたり，ご協力いただきました石垣忠平氏，玉井康博氏に感謝致します．また本研究は，財団法人福岡県産炭地域振興センターの委託事業として実施されたものである．

参考文献(!)  4 5 6  1  #  4   
74 ,
8 4 9 4 : !;0!
(&)
 7  44   <4 =   >= = = 9 4 :  &%%%

ここで，は広告を配信した最終時刻である．また， 連絡先〒 3&%2%%/0 飯塚市川津 /3%2*!
 !" を閲覧    は，  ! 時刻でカテゴリ
財団法人ファジィシステム研究所
し， 時刻でカテゴリ" を閲覧する確率を示す．
内野英治> ,%;*32&*2&00! 5?,%;*32&*2'%%&
個々の評価例として，ユーザ 1+0 を例に，正解率が2 4, @  2 =経時変化する様子を図 & に示す．また，代表マルコフモ62