(57)【要約】【課題】滞留点抽出と訪問ＰＯＩ推定の精度を向上させる。【解決手段】同時推定部１０は、滞留点候補ＤＢ４に格納された確信度、遷移スコアＤＢ７に格納されたスコア、訪問ＰＯＩ数スコアＤＢ８に格納されたスコア、ならびに、カテゴリ滞在時間パラメータＤＢ９に格納されたパラメータを用いた整数計画問題のコードを生成し、コードの解を求め、ユーザが滞留した滞留点と訪問したＰＯＩを解に基づいて推定する。【選択図】図１
2015095084.tif 000002
【特許請求の範囲】
【請求項１】
ユーザが滞留した滞留点と訪問したＰＯＩを推定する訪問ＰＯＩ推定装置であって、
滞留点候補の滞留点らしさを表す確信度を格納する滞留点候補ＤＢと、
あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移スコアＤＢと、
１つの系列において訪問されるＰＯＩの数のもっともらしさを表すスコアを格納する訪問ＰＯＩ数スコアＤＢと、
ＰＯＩのカテゴリごとに当該カテゴリのＰＯＩでの滞在時間のパラメータを格納するカテゴリ滞在時間パラメータＤＢと、
前記滞留点候補ＤＢに格納された確信度、前記遷移スコアＤＢに格納されたスコア、前記訪問ＰＯＩ数スコアＤＢに格納されたスコア、ならびに、前記カテゴリ滞在時間パラメータＤＢに格納されたパラメータを用いた整数計画問題のコードを生成し、前記コードの解を求め、前記ユーザが滞留した滞留点と前記訪問したＰＯＩを前記解に基づいて推定する同時推定部と
を備えることを特徴とする訪問ＰＯＩ推定装置。
【請求項２】
前記整数計画問題のコードは、
【数９】
2015095084.tif 000019
であり、
ｓｉ（ｉ＝１，…，Ｎ）は、滞留点候補ｉが滞留点であるかを表す変数であり、Ｎは滞留点候補ｉの総数を表すものであり、
ｘｉｋ（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ）は、滞留点候補ｉにおいて訪問したＰＯＩがｋであることを表す変数であり、ＫはＰＯＩの総種類数を表すものであり、
ｔｉｊｋｌ（ｉ＝１，…，Ｎ−１,ｊ＝ｉ＋１，…，Ｎ,ｋ＝１，…，Ｋ，ｌ＝１，…，Ｋ）は、滞留点候補ｉにおいてＰＯＩｋを訪問し、滞留点候補ｊにおいてＰＯＩｌを訪問したことを表す変数であり、
ｐｉ（ｉ＝１，…，Ｎ）は、滞留点候補ｉの滞留点らしさを表す重み係数であり、ｐｉの計算には、滞留点候補ＤＢの確信度を用い、
ｑｉｋ（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ）は、滞留点候補ｉにおいてあるＰＯＩ（訪問ＰＯＩ候補という）ｋを訪問する確からしさを表す重み係数であり、ｑｉｋの計算には、カテゴリ滞在時間パラメータＤＢのパラメータを用い、
ｒｋｌ（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ，ｌ＝１，…，Ｋ）は、訪問ＰＯＩ候補ｋを訪問した後にＰＯＩｌを訪問する確からしさを表す重み係数であり、ｒｋｌの計算には、遷移スコアＤＢのスコアを用い、
αｍ（ｍ＝１，…，Ｎ）は、系列の滞留点数ｍの確からしさを表す重み係数であり、αｍには、訪問ＰＯＩ数スコアＤＢのスコアを用いる
ことを特徴とする請求項１記載の訪問ＰＯＩ推定装置。
【請求項３】
請求項１または２記載の訪問ＰＯＩ推定装置としてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、訪問ＰＯＩ推定装置に関するものである。
【背景技術】
【０００２】
ユーザがＧＰＳロガー等の装置で蓄積したＧＰＳログ履歴を利用して、どのような場所で滞在し、またどのような場所(Point Of Interest; POI)に訪問したのかを推定する技術がある（非特許文献１、２）。
【０００３】
このような分野では、ＧＰＳログを用いてユーザが一定時間滞在した履歴の集合を滞留点として抽出し、行動分析や行動予測に用いる。非特許文献２においてはこのように抽出された滞留点について、ユーザ自身がシステムに入力した訪問ＰＯＩ履歴を併せて利用することで、訪問ＰＯＩの推定を実現している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Zheng, Y., Zhang, L., Xie, X., and Ma, W.-Y., \Mining interest-ing locations and travel sequences from GPS trajectories", Proceedings of the 18thinternational conference on World wide web, pp.791-800, 2009.
【非特許文献２】西田京介, 戸田浩之, 倉島健, 内山匡, \確率的訪問POI 分析: 時空間行動軌跡からのユーザモデリング," マルチメディア、分散、協調とモバイル(DICOMO2013)シンポジウム, 2C-6, pp. 334-345, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来技術においては以下の問題がある。
【０００６】
つまり、従来では、滞留点抽出と訪問ＰＯＩ推定をパイプライン処理で実行しており、滞留点抽出の誤りの影響を受ける。また、同様の理由で、滞留点抽出のあとに訪問ＰＯＩ推定を行っているため、訪問ＰＯＩ推定の結果を利用した滞留点抽出ができない。
【０００７】
このような問題が原因で、滞留点抽出と訪問ＰＯＩ推定の精度が低下するおそれがあった。
【０００８】
本発明は、上記の課題に鑑みてなされたものであり、その目的とするところは、滞留点抽出と訪問ＰＯＩ推定の精度を向上させた訪問ＰＯＩ推定装置を提供することにある。
【課題を解決するための手段】
【０００９】
上記の課題を解決するために、本発明は、ユーザが滞留した滞留点と訪問したＰＯＩを推定する訪問ＰＯＩ推定装置であって、滞留点候補の滞留点らしさを表す確信度を格納する滞留点候補ＤＢと、あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移スコアＤＢと、１つの系列において訪問されるＰＯＩの数のもっともらしさを表すスコアを格納する訪問ＰＯＩ数スコアＤＢと、ＰＯＩのカテゴリごとに当該カテゴリのＰＯＩでの滞在時間のパラメータを格納するカテゴリ滞在時間パラメータＤＢと、前記滞留点候補ＤＢに格納された確信度、前記遷移スコアＤＢに格納されたスコア、前記訪問ＰＯＩ数スコアＤＢに格納されたスコア、ならびに、前記カテゴリ滞在時間パラメータＤＢに格納されたパラメータを用いた整数計画問題のコードを生成し、前記コードの解を求め、前記ユーザが滞留した滞留点と前記訪問したＰＯＩを前記解に基づいて推定する同時推定部とを備えることを特徴とする。
【発明の効果】
【００１０】
本発明の訪問ＰＯＩ推定装置によれば、滞留点抽出と訪問ＰＯＩ推定の精度を向上させることができる。
【図面の簡単な説明】
【００１１】
【図１】本実施の形態に係る訪問ＰＯＩ推定装置の概略構成を示すブロック図である。
【図２】滞留点候補抽出部の処理の流れを示す図である。
【図３】パラメータ計算部の処理の流れを示す図である。
【図４】同時推定部の処理の流れを示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について図面を参照して説明する。
【００１３】
図１に示すように、本実施の形態に係る訪問ＰＯＩ推定装置は、ユーザが訪問するＰＯＩ（Point Of Interest）を推定する装置であって、ＧＰＳログデータベース（以下、データベースをＤＢと略す）１、ＰＯＩＤＢ２、滞留点候補抽出部３、滞留点候補ＤＢ４、訪問ＰＯＩＤＢ５、パラメータ計算部６、遷移スコアＤＢ７、訪問ＰＯＩ数スコアＤＢ８、カテゴリ滞在時間パラメータＤＢ９、同時推定部１０および推定結果ＤＢ１１を備える。ＰＯＩは、訪問対象となる場所であり、例えば、店舗である。
【００１４】
滞留点候補抽出部３は、ＧＰＳログＤＢ１とＰＯＩＤＢ２を入力として受け取り、滞留点候補ＤＢ４を出力する。
【００１５】
ＧＰＳログＤＢ１のデータ構造の例を表１に示す。
【表１】
2015095084.tif 000003
【００１６】
ＧＰＳログＤＢ１には、あるユーザについてＧＰＳロガーによって取得されたログ情報（ＩＤ、日時、経度、緯度）が蓄積されている。
【００１７】
ＰＯＩＤＢ２のデータ構造の例を表２に示す。
【表２】
2015095084.tif 000004
【００１８】
ＰＯＩＤＢ２には、ユーザが訪問したＰＯＩについて、そのＩＤであるＰＯＩＩＤ、そのＰＯＩの名称、そのＰＯＩのカテゴリ、そのＰＯＩの経度、緯度などが蓄積されている。ＰＯＩＤＢ２としては既存のものを利用できる。
【００１９】
滞留点候補ＤＢ４のデータ構造の例を表３に示す。
【表３】
2015095084.tif 000005
【００２０】
滞留点候補ＤＢ４には、ユーザが滞留した領域（滞留点という）について、そのＩＤである滞留点ＩＤ、その滞留点の中心経度、中心緯度、ＧＰＳログＤＢ１における対応するログ情報に含まれる最小のＩＤである開始ＩＤ、最大のＩＤである終了ＩＤ、その滞留点に滞留した時間である滞留時間、その滞留点の次に訪問可能なＰＯＩを示すＰＯＩＩＤからなる訪問ＰＯＩ候補、滞留点候補の滞留点らしさを表す確信度が蓄積される。
【００２１】
図２は、滞留点候補抽出部３の処理の流れを示す。
【００２２】
（Ｓ１−１）滞留点候補抽出部３は、ＧＰＳログＤＢ１を読み込み、滞留点を抽出する。この滞留点の抽出には、例えば、非特許文献１や非特許文献２記載の方法を用いることができる。この際、網羅的に滞留点候補を抽出するため、誤検出を許容しても可能な限り多くの滞留点候補を抽出するようなパラメータを利用する。これにより、各滞留点候補につき、中心経度、中心緯度、開始ＩＤ、終了ＩＤ、滞留時間などが得られる。
【００２３】
（Ｓ１−２）次に、各滞留点候補につき、ＰＯＩＤＢ２から、その滞留点候補の次に訪問可能なＰＯＩを示すＰＯＩＩＤからなる訪問ＰＯＩ候補を取得する。ここでは、例えば、滞留点候補の中心座標から一定距離の座標をもつＰＯＩのＰＯＩＩＤを取得する方法や、中心座標から近傍のＰＯＩを一定数選択し、そのＰＯＩＩＤを取得するなどの方法が考えられる。座標間の距離計算には、例えば、Ｈｕｂｅｎｙの公式やＶｉｎｃｅｎｔｙの公式を用いることができる（非特許文献２）。
【００２４】
（Ｓ１−３）各滞留点候補について、滞留点候補の滞留点らしさを表す確信度を計算する。この確信度の計算には、例えば、滞留点候補の経度、緯度に対する分布推定を行った場合にデータのあてはまりのよさを表す尤度などを利用することができる。具体的には非特許文献２や参考文献「Comaniciu, D. & Meer, P., "Mean Shift: A Robust Approach Toward
Feature Space Analysis", IEEE Trans. Pattern Anal. Mach. Intell., Vol.24, pp.603-
619, 2002,15」記載の方法などを用いて分布推定を行い、尤度を計算することが可能である。
【００２５】
（Ｓ１−４）各滞留点候補に滞留点ＩＤを付与し、各滞留点候補につき、滞留点ＩＤ、中心経度、中心緯度、開始ＩＤ、終了ＩＤ、滞留時間、訪問ＰＯＩ候補、確信度を滞留点ＤＢ４に出力する。
【００２６】
パラメータ計算部６は、ＰＯＩＤＢ２と訪問ＰＯＩＤＢ５を入力として受け取り、遷移確率ＤＢ７、訪問ＰＯＩ数スコアＤＢ８、カテゴリ滞在時間パラメータＤＢ９を出力する。
【００２７】
訪問ＰＯＩＤＢ５のデータ構造の例を表４に示す。
【表４】
2015095084.tif 000006
【００２８】
訪問ＰＯＩＤＢ５は、予め記録されたＧＰＳ履歴と、抽出された滞留点に対して、予めユーザが実際に訪問したＰＯＩの情報を保持している。訪問ＰＯＩＩＤは、訪問したＰＯＩのＩＤ、中心経度、中心緯度は、対応する滞留点の中心経度、中心緯度、開始時刻、終了時刻は、対応する滞留点の開始時刻、終了時刻、滞在時間は、終了時刻から開始時刻を引いた値である。
【００２９】
遷移確率ＤＢ７のデータ構造の例を表５に示す。
【表５】
2015095084.tif 000007
【００３０】
遷移確率ＤＢ７は、ＦｒｏｍカテゴリのＰＯＩを訪問したのち、ＴｏカテゴリのＰＯＩを訪問する確率に基づいてスコアを格納している。
【００３１】
訪問ＰＯＩ数スコアＤＢ８のデータ構造の例を表６に示す。
【表６】
2015095084.tif 000008
【００３２】
訪問ＰＯＩ数スコアＤＢ８は、１つの系列において訪問されるＰＯＩの数のもっともらしさを表すスコアを格納する。具体的には、各数につき、その数を示す訪問ＰＯＩ数と、対応するスコアとが格納される。
【００３３】
カテゴリ滞在時間パラメータＤＢ９のデータ構造の例を表７に示す。
【表７】
2015095084.tif 000009
【００３４】
カテゴリ滞在時間パラメータＤＢ９には、ＰＯＩについての各カテゴリに対し、滞在時間の対数値の平均（後述の対数平均パラメータμａ）と分散（後述の対数分散パラメータσａ２）が格納される。
【００３５】
図３は、パラメータ計算部６の処理の流れを示す。
【００３６】
（Ｓ２−１）パラメータ計算部６は、訪問ＰＯＩＤＢ５から未処理の連接ＰＯＩを取得する。連接ＰＯＩとは、例えば、同一系列においてＰＯＩ「Ａ」を訪問したあとにＰＯＩ「Ｂ」を訪問した場合のＡＢのペアを表す。その他にも、Ａの直後に訪問しあＰＯＩのみを対象にすることもできる。ここで同一系列は、例えば同じ日付を用いる。その他にも事前に設定された時刻で区切るなどの方法を用いることができる。本実施例では１日を１系列とする例を用いる。
【００３７】
パラメータ計算部６は、ＰＯＩＤＢ２を基に、取得した連接ＰＯＩに含まれるＰＯＩのカテゴリを取得し、遷移確率ＤＢ７のスコアを更新する。スコアの計算には、例えば、条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を用いることができる。ここでＰ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）は、ＦｒｏｍカテゴリのＰＯＩを訪問したのち、ＴｏカテゴリのＰＯＩを訪問する確率を表す。
【００３８】
具体的には、以下の手続きで条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を計算する。
【００３９】
（Ｓ２−１−ａ）全ての連接ＰＯＩに対してＰＯＩＤＢ２を用いてカテゴリを取得する。ここで、ＰＯＩ「Ａ」を訪問したあとにＰＯＩ「Ｂ」を訪問した場合、ＡのカテゴリをＦｒｏｍカテゴリ、ＢのカテゴリをＴｏカテゴリという。
【００４０】
（Ｓ２−１−ｂ）各Ｆｒｏｍカテゴリを対象に（Ｓ２−１−ｃ）の処理を行う。
【００４１】
（Ｓ２−１−ｃ）対象のＦｒｏｍカテゴリをＣＦｒｏｍとする。ＦｒｏｍカテゴリがＣＦｒｏｍ
である連接ＰＯＩを取得して総数を求める。これをＮＣＦｒｏｍとする。また、当該ＣＦｒｏｍを用いて取得された連接ＰＯＩのうち、各Ｔｏカテゴリが含まれる数をそれぞれＮＣＦｒｏｍ→ＣＴｏとする。条件付き確率Ｐ（ＣＴｏ／ＣＦｒｏｍ）は、例えば、（ＮＣＦｒｏｍ→ＣＴｏ）／ＮＣＦｒｏｍによって計算することができる。訪問がない場合にスコアがゼロになることを防ぐため、例えば予め設定した係数βを用いて、（ＮＣＦｒｏｍ→ＣＴｏ＋β）／（ＮＣＦｒｏｍ＋β｜ＣＴｏ｜）によって計算することもできる。ここで｜ＣＴｏ｜は、Ｔｏカテゴリの異なり数（種類数）である。以上の処理によって条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を求める。
【００４２】
ここでは、スコアについてはＰＯＩのカテゴリを用いた例を使って述べているが、同じ枠組みでＰＯＩそのもののスコアを用いる方法も考えられる。その場合には、Ｆｒｏｍカテゴリのカラムに対応するＰＯＩの情報を保持し、Ｔｏカテゴリのカラムに対応するＰＯＩの情報を保持すればよい。
【００４３】
（Ｓ２−２）未処理の連接ＰＯＩが存在する場合には（Ｓ２−１）に戻り、そうでない場合には（Ｓ２−３）に進む。
【００４４】
（Ｓ２−３）結果を遷移確率ＤＢ７に出力する。
【００４５】
（Ｓ２−４）訪問ＰＯＩＤＢ５から未処理の日付を取得し、該当日に訪問したＰＯＩの数（訪問ＰＯＩ数）を計算する。訪問ＰＯＩ数は、訪問ＰＯＩＤＢ５において同じ日付を持つレコード数として取得することができる。次に、訪問ＰＯＩ数を基に訪問ＰＯＩ数スコアを計算する。この計算には例えば正規分布を用いることができる。日付ｄにおける訪問ＰＯＩ数をｖｄとする。
【００４６】
（Ｓ２−５）未処理の日付がある場合には（Ｓ２−４）に戻り、そうでない場合には（Ｓ２−６）に進む。
【００４７】
（Ｓ２−６）日ごとの訪問ＰＯＩ数が正規分布に従っていると仮定し、訪問ＰＯＩ数からパラメータ推定を行い、その結果を利用して訪問ＰＯＩ数スコアを計算する。
【００４８】
平均パラメータμは、
【数１】
2015095084.tif 000010
【００４９】
によって計算する。ここでＤは日付の総異なり数を表す。
【００５０】
分散パラメータσ２は、
【数２】
2015095084.tif 000011
【００５１】
によって計算する。
【００５２】
平均パラメータと分散パラメータを利用し、ｋ回の訪問ＰＯＩ数に対する訪問ＰＯＩ数スコアαｋは、例えば正規分布の確率密度関数を用いて、
【数３】
2015095084.tif 000012
【００５３】
によって計算する。
【００５４】
そして、各訪問ＰＯＩ数スコアを訪問ＰＯＩ数スコアＤＢ８に出力する。
【００５５】
なお、ここでは訪問ＰＯＩ数スコアを正規分布の最尤推定を用いて計算したが、他にも多項分布やその他の確率分布を用いて計算する方法や各訪問ＰＯＩ数に対して人手で訪問ＰＯＩ数スコアを設定する方法が考えられる。
【００５６】
（Ｓ２−７）訪問ＰＯＩＤＢ５に含まれるＰＯＩの集合に対応するＰＯＩのカテゴリの集合のうち、未処理のカテゴリを選択する。ここで対応するカテゴリは、ＰＯＩＤＢ２から取得する。そして、訪問ＰＯＩＤＢ５から、当該カテゴリに該当するレコードを選択し、当該レコードの集合に含まれる滞在時間の情報から、当該カテゴリの平均滞在時間のパラメータを対数正規分布の最尤推定によって求める。あるカテゴリａに対応する滞留点候補ＤＢ４のレコードの滞在時間の集合を
【数４】
2015095084.tif 000013
【００５７】
と表現すると (ここでＮａはカテゴリａに対応するレコードの総数を表す）、カテゴリａの対数正規分布における対数平均パラメータμａは、
【数５】
2015095084.tif 000014
【００５８】
によって計算する。
【００５９】
また、対数分散パラメータσａ２は、
【数６】
2015095084.tif 000015
【００６０】
によって求めることができる。
【００６１】
これらのパラメータを用いることで、推定時に与えられた滞留点候補に対して滞在時間の観点で当該 POIカテゴリ訪問のもっともらしさを評価する。ここでは対数正規分布を用いる例を示したが、例えば正規分布やガンマ分布など対数正規分布以外の分布を用いることもできる。その際には、それぞれの分布の最尤推定を用いる。なお、最尤推定に限らず事前分布を用いるＭＡＰ推定など他の推定手法も利用することができる。そして、得られた対数平均パラメータと対数分散パラメータをカテゴリ滞在時間パラメータＤＢ９に出力する。
【００６２】
（Ｓ２−８）未処理のＰＯＩのカテゴリがある場合には（Ｓ２−７）に戻り、そうでない場合には処理を終了する。
【００６３】
同時推定部１０は、ＰＯＩＤＢ２、滞留点候補ＤＢ４、遷移確率ＤＢ７、訪問ＰＯＩ数スコアＤＢ８、カテゴリ滞在時間パラメータＤＢ９を入力として受け取り、推定結果ＤＢ１１を出力する。
【００６４】
推定結果ＤＢ１１のデータ構造の例を表８に示す。
【表８】
2015095084.tif 000016
【００６５】
推定結果ＤＢ１１には、ＰＯＩに関する情報、例えば、名称、中心経度、中心緯度、訪問の開始時刻、終了時刻などが格納される。
【００６６】
図４は、同時推定部１０の処理の流れを示す。
【００６７】
（Ｓ３−１）同時推定部１０は、滞留点候補ＤＢ４から未処理の系列を選択する。ここで系列は予め設定した単位を用いることができる。たとえば午前０時を区切りとする１日単位であったり、予め開始終了の時刻を設定した朝、昼、晩という単位を用いることができる。ここでは１日を単位とする例で説明する。
【００６８】
（Ｓ３−２）滞留点候補ＤＢ４、遷移スコアＤＢ７、訪問ＰＯＩ数スコアＤＢ８、カテゴリ滞在時間パラメータＤＢ９を読み込み、以下の整数計画問題のコードを生成する。
【数７】
2015095084.tif 000017
【００６９】
以下、各記号の意味と計算方法を述べる。まず探索パラメータについて説明する。
【００７０】
・ｓｉ（ｉ＝１，…，Ｎ）：滞留点候補ｉが滞留点であるかを表す変数。ここでＮは滞留点候補ｉの総数を表す。
【００７１】
・ｘｉｋ（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ）：滞留点候補ｉにおいて訪問したＰＯＩがｋであることを表す変数。ここでＫはＰＯＩの総種類数を表す。
【００７２】
・ｔｉｊｋｌ（ｉ＝１，…，Ｎ−１,ｊ＝ｉ＋１，…，Ｎ,ｋ＝１，…，Ｋ，ｌ＝１，…，Ｋ）：滞留点候補ｉにおいてＰＯＩｋを訪問し、滞留点候補ｊにおいてＰＯＩｌを訪問したことを表す変数。
【００７３】
これら探索パラメータについては、整数計画コード上では区別可能な記号であれば、必ずしも上記の記法に限定されない。
【００７４】
次に、上記変数の重み係数に利用されている記号の概要とその計算方法について説明する。
【００７５】
・ｐｉ（ｉ＝１，…，Ｎ）：滞留点候補ｉの滞留点らしさを表す重み係数。ｐｉの計算には、例えば滞留点候補ＤＢ４の確信度を用いることができる。
【００７６】
・ｑｉｋ（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ）：滞留点候補ｉにおいてあるＰＯＩ（訪問ＰＯＩ候補という）ｋを訪問する確からしさを表す重み係数。ここでは、滞留点候補ＤＢ４のうち、滞留点候補ｉに該当するレコードの訪問ＰＯＩ候補に含まれるＰＯＩを対象とする。ｑｉｋの推定には、例えば、例えばカテゴリ滞在時間パラメータＤＢ９が保持する対数正規分布のパラメータを用いて、滞留点候補ｉの滞在時間に訪問ＰＯＩ候補ｋが属するカテゴリの尤度を用いることができる。それ以外にも、例えば非特許文献２によって推定された値を用いることができる。訪問ＰＯＩ候補に含まれていないＰＯＩについては、候補から外すためにｑｉｋを０に設定するか、−９９９９９９のような絶対値が大きい負の値を設定する。
【００７７】
・ｒｋｌ（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ，ｌ＝１，…，Ｋ）：訪問ＰＯＩ候補ｋを訪問した後にＰＯＩｌを訪問する確からしさを表す重み係数。この重み係数の計算には、遷移スコアＤＢ７において、ＰＯＩｋが属するカテゴリをＦｒｏｍカテゴリ、ＰＯＩｌが属するカテゴリをＴｏカテゴリとしたレコードのスコアを用いることができる。ここでは、このようにカテゴリの推移に対応するスコアを用いるが、前述の「ＰＯＩそのもののスコア」を用いてもよい。つまり、カテゴリ分けをしないで、あるＰＯＩから別のＰＯＩを訪問する確からしさのスコアをデータベースに保持し、ｒｋｌには、訪問ＰＯＩ候補ｋを訪問した後にＰＯＩｌを訪問する場合の当該スコアを用いることもできる。
【００７８】
・αｍ（ｍ＝１，…，Ｎ）：系列の滞留点数ｍの確からしさを表す重み係数。この重み係数には、訪問ＰＯＩ数スコアＤＢ８に格納されたスコアを用いることができる
つまり、訪問ＰＯＩ数スコアＤＢ８において、滞留点数ｍの同数の訪問ＰＯＩ数に対応するスコアをαｍとして利用する。
【００７９】
また、αｍとしてガウス関数を利用できる。例えば、対象ユーザについて滞留点数の平均が５、分散が１とし平均分布で近似すると、
【数８】
2015095084.tif 000018
【００８０】
とすることができる。
【００８１】
同時推定部１０は、重み係数については上記の計算方法によって得た実数値を代入してコードを生成する。コードには、例えば、ＬＰ形式やＭＰＳ形式（参考文献：ILOG CPLEX 10.0 User’s Manual, ILOG, 2006.）を利用することが可能であり、（Ｓ３−３）で用いるソルバが利用可能な形式であれば特に形式は限定しない。
【００８２】
（Ｓ３−３）（Ｓ３−２）で生成した整数計画問題のコードをソルバを用いて求解する。このソルバには、例えばGurobi Optimizer（http://www.octobersky.jp/products/gurobi/gurobi.html）やCPLEX（http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/）といった汎用整数計画ソルバを用いることができる。
【００８３】
（Ｓ３−４）求解した結果を用いた推定結果を推定結果ＤＢ１１に出力する。つまり、ｓｉ
＝１（ｉ＝１，…，Ｎ）である滞留点候補ｉを滞留点として抽出し、また、ｘｉｋ＝１（ｉ＝１，…，Ｎ,ｋ＝１，…，Ｋ）であるＰＯＩｋを当該滞留点において訪問したＰＯＩとして解釈し、例えば、これらＰＯＩに関する情報を推定結果ＤＢ１１に出力する。
【００８４】
（Ｓ３−５）未処理の系列がある場合は（Ｓ３−１）に戻り、そうでない場合には処理を終了する。
【００８５】
以上のように、本実施の形態の訪問ＰＯＩ推定装置によれば、滞留点候補の滞留点らしさを表す確信度を格納する滞留点候補ＤＢ４と、あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移スコアＤＢ７と、１つの系列において訪問されるＰＯＩの数のもっともらしさを表すスコアを格納する訪問ＰＯＩ数スコアＤＢ８と、ＰＯＩのカテゴリごとに当該カテゴリのＰＯＩでの滞在時間のパラメータを格納するカテゴリ滞在時間パラメータＤＢ９と、滞留点候補ＤＢ４に格納された確信度、遷移スコアＤＢ７に格納されたスコア、訪問ＰＯＩ数スコアＤＢ８に格納されたスコア、ならびに、カテゴリ滞在時間パラメータＤＢ９に格納されたパラメータを用いた整数計画問題のコードを生成し（Ｓ３−２）、コードの解を求め（Ｓ３−３）、ユーザが滞留した滞留点（ｘｉｋ＝１）と訪問したＰＯＩ（ｘｉｋ＝１）を解に基づいて推定する同時推定部１０とを備えることで、滞留点抽出と訪問ＰＯＩ推定を行え、しかも、パイプライン処理でなく、整数計画問題のコードを求解しているので、滞留点抽出の誤りの影響で訪問ＰＯＩ推定の精度が低下することがなく、よって、滞留点抽出と訪問ＰＯＩ推定の精度を向上させることができる。
【００８６】
また、本実施の形態では、整数計画問題のコードを求解しているので、訪問ＰＯＩ推定の結果を利用して滞留点抽出を行っているとも言える。
【００８７】
なお、本実施の形態の訪問ＰＯＩ推定装置としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【００８８】
１  ＧＰＳログＤＢ
２  ＰＯＩＤＢ
３  滞留点候補抽出部
４  滞留点候補ＤＢ
５  訪問ＰＯＩＤＢ
６  パラメータ計算部
７  遷移スコアＤＢ
８  訪問ＰＯＩ数スコアＤＢ
９  カテゴリ滞在時間パラメータＤＢ
１０  同時推定部
１１  推定結果ＤＢ
【図１】
2015095084.tif 000020
【図２】
2015095084.tif 000021
【図３】
2015095084.tif 000022
【図４】
2015095084.tif 000023