(57)【特許請求の範囲】
【請求項１】
各ユーザが各アイテムを採用した時刻を表す行動履歴データが与えられたときに、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出する観測者検出装置であって、
前記行動履歴データから、各アイテムが、多くのユーザが採用しているアイテムであるかどうかを表すターゲット変数と、各アイテムについての、各ユーザが前記アイテムについて前記観測者として適しているかどうか、又は適している度合いを表す特徴ベクトルとを生成する入力部と、
各アイテムの前記ターゲット変数と、各アイテムの前記特徴ベクトルとに基づいて、前記特徴ベクトルに基づいて前記アイテムが多くのユーザが採用しているアイテムであるか否かを分類するための分類器のパラメータベクトルを学習する学習部と、
前記学習部によって学習された前記分類器のパラメータベクトルの要素を選択する特徴選択部と、
前記特徴選択部によって選択された前記パラメータベクトルの要素に対応するユーザの集合を、前記観測者の集合として出力する出力部と、
を含む観測者検出装置。
【請求項２】
前記特徴選択部は、前記学習部によって学習された前記分類器のパラメータベクトルの要素を選択し、選択した要素の数が、入力された観測者数未満であれば、前記分類器のパラメータベクトルを学習する際に用いるハイパーパラメータを変更して、前記学習部による学習を繰り返させる請求項１記載の観測者検出装置。
【請求項３】
前記学習部は、前記分類器のパラメータベクトル、各アイテムの前記ターゲット変数、及び各アイテムの前記特徴ベクトルを用いて表される損失関数、及び前記分類器のパラメータベクトルに関する正則化項を含む目的関数を最小化するように、前記分類器のパラメータベクトルを学習する請求項１又は２記載の観測者検出装置。
【請求項４】
各アイテムの前記特徴ベクトルは、前記アイテムについて前記観測者として適しているか否かを判断するための閾値に基づいて求められ、
前記学習部は、前記アイテム及び前記閾値をサンプリングし、サンプリングされた前記アイテムについての前記ターゲット変数、及びサンプリングされた前記閾値に基づいて求められる前記アイテムの前記特徴ベクトルからなる入出力ペアに基づいて、前記目的関数を最小化するように、前記分類器のパラメータベクトルを更新することを繰り返す請求項３記載の観測者検出装置。
【請求項５】
各ユーザが各アイテムを採用した時刻を表す行動履歴データが与えられたときに、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出する観測者検出装置における観測者検出方法であって、
入力部が、前記行動履歴データから、各アイテムが、多くのユーザが採用しているアイテムであるかどうかを表すターゲット変数と、各アイテムについての、各ユーザが前記アイテムについて前記観測者として適しているかどうか、又は適している度合いを表す特徴ベクトルとを生成し、
学習部が、各アイテムの前記ターゲット変数と、各アイテムの前記特徴ベクトルとに基づいて、前記特徴ベクトルに基づいて前記アイテムが多くのユーザが採用しているアイテムであるか否かを分類するための分類器のパラメータベクトルを学習し、
特徴選択部が、前記学習部によって学習された前記分類器のパラメータベクトルの要素を選択し、
出力部が、前記特徴選択部によって選択された前記パラメータベクトルの要素に対応するユーザの集合を、前記観測者の集合として出力する
観測者検出方法。
【請求項６】
コンピュータを、請求項１〜請求項４の何れか１項に記載の観測者検出装置の各部として機能させるためのプログラム。
【請求項７】
請求項６に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、観測者検出装置、方法、プログラム、及びコンピュータ読み取り可能な記録媒体に係り、特に、行動履歴データから、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出する観測者検出装置、方法、プログラム、及びコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
ユーザの行動履歴データに基づき，流行する情報を予測する問題を考える。ここでいう情報とは購買行動における商品やサービス、ソーシャルネットワーク上で投稿される発言や情報、画像、映像などを指し、以後これらを総称してアイテムと呼ぶことにする。これらアイテムの流行予測は、マーケティングや研究開発における戦略立案といった組織レベルの問題から、限りある商品が流行して在庫切れになる前に予約や購入するなど個人レベルの問題まで幅広く応用される。これら流行予測に関連する手法がいくつか提案されている。例えば非特許文献１、２は、将来流行するアイテムを予測する手法を提案している。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Kupavskii, A.; Ostroumova, L.; Umnov, A.; Usachev, S.; Serdyukov, P.;Gusev, G.; Kustarev, A. "Prediction of retweet cascade size over time" . In Proceedings of the 21st ACM International Conference on Information and Knowledge Management (CIKM),2335-2338, 2012.
【非特許文献２】Menjo, T.; Yoshikawa, M. "Trend prediction in social bookmark service using time series of bookmarks". In Proceedings of WWW2008Workshop on Social Search and Mining, 2008.
【非特許文献３】Hannon, J.; McCarthy, K.; Smyth, B. "Finding useful users on twitter: twittomender the followee recommender". Advances in Information Retrieval, 784-787, 2011.
【非特許文献４】Armentano, M. G.; Godoy, D.; Amandi, A. A. "Followee recommendation based on text analysis of micro-blogging activity". Information systems, Vol. 38, No. 8, 1116-1127, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明では流行するアイテムを早期に発見するユーザを検出することを目的とする。こうしたユーザの検出は例えばソーシャルメディア上で有用である。ソーシャルメディアにはユーザ間で取得したアイテムを共有する機能がある。前述の検出されたユーザと情報を共有することで、将来流行が予想されるアイテムを、検出したユーザを経由して入手できる。このようなユーザを以後観測者と呼ぶ。
【０００５】
こうした本発明の目的は上記で挙げた非特許文献１、２のようなアイテムそのものの流行予測とは異なる。また非特許文献３、４ではデータから有用なユーザを抽出する手法を提案しているが、その基準はユーザとの嗜好の近さであるため、こちらも本発明の目的とは異なる。
【０００６】
本発明は、上記の事情を鑑みて成されたものであり、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出することができる観測者検出装置、方法、プログラム、及びコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明に係る観測者検出装置は、各ユーザが各アイテムを採用した時刻を表す行動履歴データが与えられたときに、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出する観測者検出装置であって、前記行動履歴データから、各アイテムが、多くのユーザが採用しているアイテムであるかどうかを表すターゲット変数と、各アイテムについての、各ユーザが前記アイテムについて前記観測者として適しているかどうか、又は適している度合いを表す特徴ベクトルとを生成する入力部と、各アイテムの前記ターゲット変数と、各アイテムの前記特徴ベクトルとに基づいて、前記特徴ベクトルに基づいて前記アイテムが多くのユーザが採用しているアイテムであるか否かを分類するための分類器のパラメータベクトルを学習する学習部と、前記学習部によって学習された前記分類器のパラメータベクトルの要素を選択する特徴選択部と、前記特徴選択部によって選択された前記パラメータベクトルの要素に対応するユーザの集合を、前記観測者の集合として出力する出力部と、を含んで構成されている。
【０００８】
また、本発明に係る観測者検出方法は、各ユーザが各アイテムを採用した時刻を表す行動履歴データが与えられたときに、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出する観測者検出装置における観測者検出方法であって、入力部が、前記行動履歴データから、各アイテムが、多くのユーザが採用しているアイテムであるかどうかを表すターゲット変数と、各アイテムについての、各ユーザが前記アイテムについて前記観測者として適しているかどうか、又は適している度合いを表す特徴ベクトルとを生成し、学習部が、各アイテムの前記ターゲット変数と、各アイテムの前記特徴ベクトルとに基づいて、前記特徴ベクトルに基づいて前記アイテムが多くのユーザが採用しているアイテムであるか否かを分類するための分類器のパラメータベクトルを学習し、特徴選択部が、前記学習部によって学習された前記分類器のパラメータベクトルの要素を選択し、出力部が、前記特徴選択部によって選択された前記パラメータベクトルの要素に対応するユーザの集合を、前記観測者の集合として出力する。
【０００９】
また、本発明に係るプログラムは、コンピュータを、上記の観測者検出装置の各部として機能させるためのプログラムである。
【００１０】
また、本発明に係るコンピュータ読み取り可能な記録媒体は、上記のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００１１】
本発明の観測者検出装置、方法、プログラム、及びコンピュータ読み取り可能な記録媒体によれば、行動履歴データから、ターゲット変数と特徴ベクトルとを生成し、アイテムが多くのユーザが採用しているアイテムであるか否かを分類するための分類器のパラメータベクトルを学習し、学習された分類器のパラメータベクトルの要素を選択し、対応するユーザの集合を、観測者の集合とすることにより、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出することができる、という効果が得られる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施の形態に係る観測者検出装置の構成を示すブロック図である。
【図２】本発明の実施の形態に係る観測者検出装置の観測者検出処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１４】
＜本発明の実施の形態に係る概要＞
まず、本発明の実施の形態における概要を説明する。本発明の実施の形態では行動履歴を表すデータとしてイベント集合
0006614030.tif 000002
が得られている状況を想定する。ここで(ｉe，ｕe，ｔe)は ｅ番目のイベントであり、ユーザｕe∈Ｕがアイテムｉe∈Ｉを時刻ｔe≦Ｔで採用することを表している。ここでいう採用とは、例えば購買履歴における商品の購入や、ソーシャルメディア上での発言などの情報を共有する機能の使用などを指す。Ｉはアイテム集合、Ｕはユーザ集合、Ｔはイベント集合が記録されている時刻の終端である。また｜・｜は集合の元の個数を表すとする。
【００１５】
このようなデータが与えられた元で、本発明の実施の形態では人気アイテムの分類問題を考える。人気アイテムの定義としては、例えば、(1)採用された回数が全体の上位ｓ％であるアイテム、(2)一定の回数ｖ以上採用されたアイテム、などが考えられるが、イベント集合Ｅでの採用回数によって、各アイテムが、多くのユーザが採用している人気アイテムかそうでないか区別できれば良いとする。また各アイテムの特徴ベクトルとしては、各要素がユーザ集合Ｕに対応するＵ次元ベクトルとして定義する。特徴ベクトルの各要素の値は、対応するユーザが当該アイテムについて観測者として適しているかどうかや、適している度合いなどを表現している必要がある。本発明の実施の形態では、人気アイテムを他のユーザよりも早く採用する傾向があるユーザを観測者として抽出したい。そのため、ユーザがアイテムを採用する順位や時間の情報から、人気アイテムの特徴ベクトルの各要素が、早く採用するユーザで大きな値を、遅く採用するユーザで小さな値をそれぞれ取るように定義すれば良い。具体例は後述する。
【００１６】
このように定義された分類問題における特徴選択によって、ユーザ集合Ｕの部分集合である観測者集合Ｏ⊂Ｕを抽出する。特徴選択手法としては、分類問題に使用できる方法であれば良い。例えば、Ｌ1正則化やＬ0正則化と、線形分類器とを使用する方法や、決定木やランダムフォレストと、ジニ係数などの情報基準とを組み合わせた方法などが挙げられる。
【００１７】
＜観測者検出装置の構成＞
次に、本発明の実施の形態に係る観測者検出装置の構成について説明する。図１に示すように、本実施の形態に係る観測者検出装置１００は、ＣＰＵと、ＲＡＭと、後述する観測者検出処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この観測者検出装置１００は、機能的には図１に示すように入力部１０と、学習部２０と、特徴選択部３０と、出力部４０とを備えている。
【００１８】
入力部１０は、取得したい観測者数ｄと、行動履歴データとしてのイベント集合Ｅとを受け付ける。また使用する特徴選択手法と分類器に応じて、イベント集合Ｅを学習用の入力データ集合に変換する。
【００１９】
本実施の形態では、Ｌ1正則化と線形分類器を用いた特徴選択手法を使用する場合を例に説明する。
【００２０】
線形分類器は損失関数にパラメータと特徴ベクトルの線形結合を含む分類器であり、例として、ロジスティック回帰やプロビット回帰、サポートベクトルマシンなどが挙げられる。以下では、ロジスティック回帰の例を適宜説明する。
【００２１】
イベント集合Ｅを、線形分類器に学習させる入力データ集合に変換する。入力データ集合は、各アイテムが、多くのユーザが採用しているアイテムであるかどうかを表すターゲット変数からなるターゲット変数集合と、各アイテムについての、各ユーザが前記アイテムを早期に採用したかどうかを表す特徴ベクトルからなる特徴ベクトル集合とから構成される。
【００２２】
まず、人気アイテムの定義に従い、各アイテムが人気かどうかを表すターゲット変数集合
0006614030.tif 000003
を計算する。例えば、後述する(1)式のように人気アイテムを定義する場合、
0006614030.tif 000004
をアイテムｉの総採用回数が全アイテム中で上位ｓ％の人気アイテムとなった場合１、それ以外の場合０をとる２値変数として定義する。
【００２３】
次に、特徴ベクトルを定義する。前述のように特徴ベクトルの各要素はユーザに対応し、各要素はそのユーザが当該アイテムについて観測者として適しているかどうか、あるいは適している度合いを表現するように定義する。
【００２４】
一例として、アイテムを採用した順位に基づき２値ベクトルとして特徴ベクトルを構成する例を示す。まず、ユーザｕがアイテムｉを採用した順位を表す
0006614030.tif 000005
を計算する。なお最初にアイテムｉを採用したユーザｕの順位は
0006614030.tif 000006
とする。この順位を元に以下の特徴ベクトル集合
0006614030.tif 000007
を定義する。アイテムｉに対応する特徴ベクトル
0006614030.tif 000008
の各要素は、
【００２５】
【数１】
0006614030.tif 000009
【００２６】
で表される。ここでｚは後述する確率分布 p(z)に従う確率変数であり、どの順位までのユーザを特徴として使用するか決める閾値としての役割を果たす。ｘi,u(z)は閾値ｚに依存して決まる。以下では、（１）式の特徴ベクトルを使用する場合を説明する。
【００２７】
次に入力データ集合
0006614030.tif 000010
の元で損失関数を定義する。損失関数は入力データ集合とパラメータで定義される関数であり、入力データ集合の誤分類が小さいほど小さな値を取る関数として表される。例えば、前述の入力データ集合
0006614030.tif 000011
に対する損失関数の具体例としては、
【００２８】
【数２】
0006614030.tif 000012
【００２９】
が考えられる。このとき線形分類器にロジスティック回帰を使用する場合、各アイテムの損失
0006614030.tif 000013
は、
【００３０】
【数３】
0006614030.tif 000014
【００３１】
で表現される。
σ(・)はシグモイド関数、
0006614030.tif 000015
は｜Ｕ｜＋１次元パラメータベクトルであり、第一要素ｗ0はベクトル全体の位置を定めるバイアスパラメータである。また、（２）式の損失関数は確率分布p(z)の期待値をとることで定義されている。
【００３２】
p(z)は正または非負の値をとる確率分布であれば良い。例えば、ワイブル分布、ガンマ分布、対数正規分布などが考えられる。例えば以下に示すワイブル分布の場合、その確率密度関は、
【００３３】
【数４】
0006614030.tif 000016
【００３４】
で定義される。ここでkは形状パラメータ、θは尺度パラメータである。なおワイブル分布のような非負の値をとる確率分布の場合、ちょうどz=0をとるとき対応するxi(z)は第一要素以外の要素が全て0をとるベクトルになる。こうしたベクトルの影響を排除したい場合、正の値をとる確率分布を使用すれば良い。ワイブル分布のような連続型確率分布の場合、ちょうどz=0をとる確率は0であるため、後述する学習部20ではこうしたベクトルの影響をほぼ無視できる。またp(z)としてｍでのみ1を取るデルタ関数 δ(z−m)を指定すると、（２）式の損失関数は期待値を含まない以下の形で書くことができる。
【００３５】
【数５】
0006614030.tif 000017
【００３６】
分類器の学習では、目的関数の最小化問題を解くことで解ベクトル
0006614030.tif 000018
を得る。Ｌ1正則化を使用する場合、目的関数は損失関数とＬ1正則化項の和として定義される。例えば、（２）式を損失関数として使用する場合、目的関数は以下のように定義される。
【００３７】
【数６】
0006614030.tif 000019
【００３８】
ここで、
0006614030.tif 000020
はバイアスパラメータｗ0を除く｜Ｕ｜次元パラメータベクトルであり、
0006614030.tif 000021
はＬ1正則化項、λ＞０はその正則化パラメータである。Ｌ1正則化によって解ベクトル
0006614030.tif 000022
はｗ0を除きλが大きいほどゼロの要素が多い疎なベクトルになりやすい。Ｌ1正則化による特徴選択では、この非ゼロ要素として残った要素に対応する特徴を分類上有用な特徴として選択する。本発明の実施の形態の場合、残った正値を取る要素に対応するユーザは、人気アイテムを早く採用することが多く、人気でないアイテムを早く採用することが少ないことを意味している。逆に、負値を取る要素に対応するユーザは、人気でないアイテムを早く採用することが多く、人気アイテムを早く採用することが少ないことを意味している。ゆえに、解ベクトルの要素のうち、正値をとる要素に対応するユーザを観測者として抽出すれば良いことになる。
【００３９】
また、（６）式の代わりに以下の最小化問題を解いても良い。
【００４０】
【数７】
0006614030.tif 000023
【００４１】
こちらは
0006614030.tif 000024
のとりうる値が非負の実数値をとる｜Ｕ｜次元空間
0006614030.tif 000025
上に制約されていると仮定している。この場合、特徴として残る要素は全て正値をとるため、0以外の値を取る解ベクトルの要素を全て観測者として抽出すれば良いことになる。以下では（７）式を解く場合を例に説明する。
【００４２】
学習部２０は、各アイテムの前記ターゲット変数と、各アイテムの特徴ベクトルとに基づいて、以下に説明するように、特徴ベクトルに基づいてアイテムが多くのユーザが採用しているアイテムであるか否かを分類するための線形分類器を学習し、線形分類器を学習することで得られるパラメータベクトルを出力する。
【００４３】
本実施の形態では、学習部２０は、線形分類器のパラメータベクトル、各アイテムのターゲット変数、及び各アイテムの特徴ベクトルを用いて表される損失関数、及び線形分類器のパラメータベクトルに関する正則化項を含む目的関数を最小化する上記（７）式の最小化問題を解くために、最適化アルゴリズムを実行して、線形分類器のパラメータベクトルを学習する。上記（７）式の損失関数の項にはp(z)に関する期待値が含まれているため、確率的最適化アルゴリズムを使用することが考えられる。例えば、確率的勾配法や、Forward Backward Splittingなどが挙げられるが、ここではAdagrad(非特許文献５：Duchi, D.; Hazan, E.; Singer, Y. "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization". Journal of Machine Learning Research, Vol. 12, 2121 −2159, 2011.)とRegularized Dual Averaging(RDA)(非特許文献６：Xiao, L. "Dual Averaging Methods for Regularized Stochastic Learning and Online Optimization". Journal of Machine Learning Research, Vol. 11, 2543 −2596, 2010.)を使用した確率的最適化アルゴリズム Ada-RDAを用いて（７）式の最小化問題を解く場合を説明する。
【００４４】
Ada-RDAは適当に初期化した
0006614030.tif 000026
から始め、値を繰り返し更新することで解ベクトルを得る学習アルゴリズムである。ｎステップにおいて、まず入出力ペア
0006614030.tif 000027
を１つサンプリングする。アイテムｉはアイテム集合Ｉからランダムに、確率変数ｚはp(z)に従ってそれぞれサンプリングされる。サンプリングされた入出力ペアによって、パラメータベクトルは現時点の値
0006614030.tif 000028
を使い、目的関数を最小化する以下の最小化問題を解くことでパラメータベクトルが更新される。
【００４５】
【数８】
0006614030.tif 000029
【００４６】
ここでη＞０は特徴ベクトル全体の学習率を調整するハイパーパラメータである。
0006614030.tif 000030
は
【００４７】
【数９】
0006614030.tif 000031
【００４８】
で定義される。ここでｇn,uはｎステップでの勾配ベクトル
0006614030.tif 000032
のｕ番目の要素を示す。ロジスティック回帰の場合、勾配ベクトルは、
【００４９】
【数１０】
0006614030.tif 000033
【００５０】
で表される。
【００５１】
Ｈnは対角行列
0006614030.tif 000034
であり、ベクトル
0006614030.tif 000035
は以下で定義される。
【００５２】
【数１１】
0006614030.tif 000036
【００５３】
なおハイパーパラメータ
0006614030.tif 000037
は
0006614030.tif 000038
を満たすよう設定する。これら変数によって定義された上記（８）式の最小化問題を解くことで、ｕ＝１,…，｜Ｕ｜について以下の更新式が得られる。
【００５４】
【数１２】
0006614030.tif 000039
【００５５】
sign(・)は符号関数、[・]+はヒンジ関数である。
【００５６】
学習部２０は、サンプリングされた入出力ペアに基づいて、上記（１２）式、（１３）式に従って、線形分類器のパラメータベクトルを更新する。この更新を繰り返し終了条件を満たすまで繰り返す。繰り返し終了条件としては例えば十分な反復回数を設定しておき、その回数だけ繰り返すなどが挙げられる。繰り返し終了条件を満たせば更新を終了し、その時点で得られたパラメータベクトルを解ベクトル
0006614030.tif 000040
として出力する。
【００５７】
なお、ここまでで導入したハイパーパラメータ
0006614030.tif 000041
はパラメータベクトル
0006614030.tif 000042
とともに事前に初期化しておく必要があるが、交差確認法などを利用することで複数候補の中から選ぶことができる。
【００５８】
特徴選択部３０は、学習部２０で得た解ベクトルの非ゼロ要素を選択する。なお、本実施の形態のように、Ｌ1正則化を用いる手法では、学習部２０の出力結果が指定した観測者数ｄを得るための条件を満たさない場合がある。その場合は学習部２０に戻り、条件を変更して再度実行する．
【００５９】
具体的には、得られた解ベクトル
0006614030.tif 000043
の非ゼロ要素数と取得したい観測者数ｄを比較する。非ゼロ要素数がｄ未満であれば、ハイパーパラメータλをより小さい値に初期化して、学習部２０に戻ってやり直す。非ゼロ要素数がｄであれば、解ベクトル
0006614030.tif 000044
をそのまま出力する。非ゼロ要素数がｄより大きければ、ｄと一致するように、解ベクトル
0006614030.tif 000045
の非ゼロ要素のうち、小さい順に要素を０にしてから出力する。
【００６０】
出力部４０は、以下の式のように解ベクトルの非ゼロ要素に対応するユーザ集合を観測者集合Ｏとして検出して出力する。
【００６１】
【数１３】
0006614030.tif 000046
【００６２】
＜本発明の実施の形態に係る観測者検出装置の作用＞
次に、本発明の実施の形態に係る観測者検出装置１００の作用について説明する。
【００６３】
入力部１０において、観測者数ｄの指定と、行動履歴データであるイベント集合Ｅを受け付けると、観測者検出装置１００は、図２に示す観測者検出処理ルーチンを実行する。
【００６４】
まず、ステップＳ１００において、入力部１０は、受け付けたイベント集合Ｅから、ターゲット変数集合を作成する。次に、ステップＳ１０１において、入力部１０は、受け付けたイベント集合Ｅから、ユーザが観測者に適しているかどうか、又は適している度合いを表す特徴ベクトル集合を作成する。
【００６５】
次に、ステップＳ１０２において、学習部２０は、パラメータベクトル
0006614030.tif 000047
とハイパーパラメータ
0006614030.tif 000048
とを初期化する。
【００６６】
ステップＳ１０４では、学習部２０は、上記ステップＳ１００、Ｓ１０１で得られたターゲット変数集合及び特徴ベクトル集合から、入出力ペア
0006614030.tif 000049
を１つサンプリングする。
【００６７】
ステップＳ１０６では、学習部２０は、上記ステップＳ１０４でサンプリングした入出力ペア
0006614030.tif 000050
と、
ハイパーパラメータ
0006614030.tif 000051
とに基づいて、上記（１２）式、（１３）式に従って、パラメータベクトル
0006614030.tif 000052
を更新する。
【００６８】
ステップＳ１０８では、学習部２０は、予め定められた繰り返し終了条件を満たしか否かを判定し、繰り返し終了条件を満たしていない場合には、上記ステップＳ１０４へ戻る。一方、繰り返し終了条件を満たした場合には、ステップＳ１１０へ進む。
【００６９】
ステップＳ１１０では、特徴選択部３０は、上記ステップＳ１０６で最終的に得られたパラメータベクトル
0006614030.tif 000053
の非ゼロ要素の数が、指定された観測者数ｄ未満であるか否かを判定する。非ゼロ要素の数が、指定された観測者数ｄ未満である場合には、ステップＳ１１２において、特徴選択部３０は、ハイパーパラメータλを小さく更新して、上記ステップＳ１０４へ戻る。
【００７０】
一方、非ゼロ要素の数が、指定された観測者数ｄ以上である場合には、ステップＳ１１４において、特徴選択部３０は、非ゼロ要素の数が、指定された観測者数ｄであるパラメータベクトル
0006614030.tif 000054
をそのまま出力する。あるいは、非ゼロ要素数がｄより大きければ、ｄと一致するように、パラメータベクトル
0006614030.tif 000055
の非ゼロ要素のうち、小さい順に要素を０にしてから出力する。
【００７１】
ステップＳ１１６では、出力部４０が、非ゼロ要素に対応するユーザ集合を観測者集合Ｏとして検出して出力し、観測者検出処理ルーチンを終了する。
【００７２】
＜実施例＞
本発明の実施の形態に係る手法を評価するために、ユーザの行動履歴データが記録された11データセットを用いて実験を行った。イベント集合に含まれるアイテムのうち、採用回数の多い上位ｓ＝１０％のアイテムを人気アイテムとして定義する。また、ｍ＝１０人までにアイテムを採用する観測者を探す状況を考える。９０％を訓練データ、１０％をテストデータとしてランダムに１０分割して、訓練とテストを入れ替えながら評価する。訓練データから観測者を選択した後、テストデータ内の各アイテムについて最初のｍ＝１０人のユーザに選んだ観測者が１人でも含まれていれば人気アイテムだと判定する。実際に人気アイテムだった場合正解、そうでなかった場合を不正解としてＦ値を計算する。
【００７３】
選択する観測者数を１人から１００人まで変化させて観測者数-Ｆ値曲線を描き、そのArea Under Curve(AUC)の値で評価する。
【００７４】
比較手法としてイベント集合から以下の値が大きいユーザを順に観測者として選ぶ5つの手法を用意した。
【００７５】
N adoptions:ユーザの採用回数。
N followers:ユーザが採用した後に同じアイテムを採用したユーザ数の合計値。
N early: ｍ人のユーザが採用する前にアイテムを採用した回数。
N early-pos: ｍ人のユーザが採用する前に人気アイテムを採用した回数。
N early-pos/neg: N early-posをｍ人のユーザが採用する前に人気でないアイテムを採用した回数で割った値。
【００７６】
上記設定のもとで、実験結果を表１に示す。太字は９５％水準の両側ｔ検定において、太字以外の手法よりも有意に良い結果だったことを意味する。
【００７７】
【表１】
0006614030.tif 000056
【００７８】
なお、Proposedは本発明においてp(z)にデルタ関数δ(z−m)(m=10)を使用した場合、Proposed with data augmentationは p(z)にワイブル分布を使用した場合（パラメータ (k,θ)は5交差確認法で選択）をそれぞれ表す。全てのデータセットで本発明の実施の形態に係る手法が最も高い精度を達成しており、比較手法よりも適切な観測者を選択できていることを示唆している。
【００７９】
以上説明したように、本実施の形態に係る観測者検出装置によれば、行動履歴データから、ターゲット変数集合と特徴ベクトル集合とからなる入力データ集合を生成し、アイテムが多くのユーザが採用しているアイテムであるか否かを分類するための分類器のパラメータベクトルを学習し、学習された分類器のパラメータベクトルの要素を選択し、対応するユーザの集合を、観測者の集合とすることにより、将来多くのユーザが採用するアイテムを早期に採用するユーザである観測者の集合を検出することができる。
【００８０】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００８１】
例えば、上記実施の形態では、観測者数dの単一の集合のみ検出する場合を説明したが、観測者数が１からＤまでの、複数の観測者集合
0006614030.tif 000057
を一度に検出するように容易に変形できる。Ｌ1正則化による特徴選択の場合、まず予め正則化パラメータの集合
0006614030.tif 000058
を用意しておく。その中で最小のＪで学習したときＤ個以上のパラメータが生き残ることを確認した上で、各ｊで特徴選択部３０と同じ処理を行う。この場合検出したい
0006614030.tif 000059
の中で欠損している集合が出てくるが、特徴選択部３０で行ったように、欠損している集合については、より大きな非ゼロ要素数をもつ解ベクトルの要素を小さい順に削減することで補完すればよい。
【００８２】
また、正則化と線形分類器を用いた特徴選択手法を使用する場合を例に説明したが、これに限定されるものではなく、例えば、決定木やランダムフォレストと、ジニ係数などの情報基準とを組み合わせた方法を使用するようにしてもよい。決定木やランダムフォレストを使用する場合、学習部２０は、学習を行った後、スコア計算を行い、特徴ごとのスコア値を出力するようにすればよい。
【００８３】
また、上述の観測者検出装置は、内部にコンピュータシステムを有しているが、コンピュータシステムは、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００８４】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００８５】
１０   入力部
２０   学習部
３０   特徴選択部
４０   出力部
１００ 観測者検出装置
【図１】
0006614030.tif 000060
【図２】
0006614030.tif 000061