(57)【要約】【課題】訪問ＰＯＩ推定の精度を向上させる。【解決手段】図５では、Ｎ個の滞留点に対して、３種類のＰＯＩのカテゴリ (ラーメン店、コンビニ、カフェ )の訪問確率Ｐ（ｓｉ／ｘｉ)を各ノードの中の数字で示し、エッジにＰＯＩのカテゴリ間の遷移確率Ｐ（ｘｉ｜ｘｉ−１）を示している。訪問ＰＯＩ推定装置は、太字で示された、同時確率が最大化されるような経路を選択する。【選択図】図５
2015095083.tif 000002
【特許請求の範囲】
【請求項１】
ユーザが訪問するＰＯＩを推定する訪問ＰＯＩ推定装置であって、
あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移確率ＤＢと、
１つの系列に属する複数の滞留点のそれぞれに対して訪問のもっともらしさを表す訪問確率を計算し、前記系列に対するもっともらしさを表す同時確率の式を前記訪問確率と前記遷移確率ＤＢのスコアを用いて生成し、前記同時確率を最大化する解を求め、前記訪問するＰＯＩを前記解に基づいて推定する系列推定部と
を備えることを特徴とする訪問ＰＯＩ推定装置。
【請求項２】
Ｎ個の滞留点に含まれる滞留点ｉについての訪問確率をＰ（ｓｉ／ｘｉ)、スコアをＰ（ｘｉ｜ｘｉ−１）とした場合、同時確率の式は、
【数２】
2015095083.tif 000010
であることを特徴とする請求項１記載の訪問ＰＯＩ推定装置。
【請求項３】
請求項１または２記載の訪問ＰＯＩ推定装置としてコンピュータを機能させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、訪問ＰＯＩ推定装置に関するものである。
【背景技術】
【０００２】
ユーザがＧＰＳロガー等の装置で蓄積したＧＰＳログ履歴を利用して、どのような場所で滞在し、またどのような場所(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）を推定する装置であって、ＧＰＳログデータベース（以下、データベースをＤＢと略す）１、ＰＯＩＤＢ２、滞留点抽出部３、滞留点ＤＢ４、訪問ＰＯＩＤＢ５、パラメータ計算部６、遷移確率ＤＢ７、系列推定部８および推定結果ＤＢ９を備える。ＰＯＩは、訪問対象となる場所であり、例えば、店舗である。
【００１２】
滞留点抽出部３は、ＧＰＳログＤＢ１とＰＯＩＤＢ２を入力として受け取り、滞留点ＤＢ４を出力する。
【００１３】
ＧＰＳログＤＢ１のデータ構造の例を表１に示す。
【表１】
2015095083.tif 000003
【００１４】
ＧＰＳログＤＢ１には、あるユーザについてＧＰＳロガーによって取得されたログ情報（ＩＤ、日時、経度、緯度）が蓄積されている。
【００１５】
ＰＯＩＤＢ２のデータ構造の例を表２に示す。
【表２】
2015095083.tif 000004
【００１６】
ＰＯＩＤＢ２には、ユーザが訪問したＰＯＩについて、そのＩＤであるＰＯＩＩＤ、そのＰＯＩの名称、そのＰＯＩのカテゴリ、そのＰＯＩの経度、緯度などが蓄積されている。ＰＯＩＤＢ２としては既存のものを利用できる。
【００１７】
滞留点ＤＢ４のデータ構造の例を表３に示す。
【表３】
2015095083.tif 000005
【００１８】
滞留点ＤＢ４には、ユーザが滞留した領域（滞留点という）について、そのＩＤである滞留点ＩＤ、その滞留点の中心経度、中心緯度、ＧＰＳログＤＢ１における対応するログ情報に含まれる最小のＩＤである開始ＩＤ、最大のＩＤである終了ＩＤ、その滞留点に滞留した時間である滞留時間、その滞留点の次に訪問可能なＰＯＩを示すＰＯＩＩＤからなる訪問ＰＯＩ候補が蓄積される。
【００１９】
図２は、滞留点抽出部３の処理の流れを示す図である。
【００２０】
（Ｓ１−１）滞留点抽出部３は、ＧＰＳログＤＢ１を読み込み、滞留点を抽出する。この滞留点の抽出には、例えば、非特許文献１や非特許文献２記載の方法を用いることができる。滞留点抽出に必要なパラメータは予め設定されているものとする。これにより、各滞留点につき、中心経度、中心緯度、開始ＩＤ、終了ＩＤ、滞留時間などが得られる。
【００２１】
（Ｓ１−２）次に、各滞留点につき、ＰＯＩＤＢ２から、その滞留点の次に訪問可能なＰＯＩを示すＰＯＩＩＤからなる訪問ＰＯＩ候補を取得する。ここでは、例えば、滞留点の中心座標から一定距離の座標をもつＰＯＩのＰＯＩＩＤを取得する方法や、中心座標から近傍のＰＯＩを一定数選択し、そのＰＯＩＩＤを取得するなどの方法が考えられる。座標間の距離計算には、例えば、Ｈｕｂｅｎｙの公式やＶｉｎｃｅｎｔｙの公式を用いることができる（非特許文献２）。
【００２２】
（Ｓ１−３）各滞留点に滞留点ＩＤを付与し、各滞留点につき、滞留点ＩＤ、中心経度、中心緯度、開始ＩＤ、終了ＩＤ、滞留時間、訪問ＰＯＩ候補を滞留点ＤＢ４に出力する。
【００２３】
パラメータ計算部６は、ＰＯＩＤＢ２と訪問ＰＯＩＤＢ５を入力として受け取り、遷移確率ＤＢ７を出力する。
【００２４】
訪問ＰＯＩＤＢ５のデータ構造の例を表４に示す。
【表４】
2015095083.tif 000006
【００２５】
訪問ＰＯＩＤＢ５は、予め記録されたＧＰＳ履歴と、抽出された滞留点に対して、予めユーザが実際に訪問したＰＯＩの情報を保持している。訪問ＰＯＩＩＤは、訪問したＰＯＩのＩＤ、中心経度、中心緯度は、対応する滞留点の中心経度、中心緯度、開始時刻、終了時刻は、対応する滞留点の開始時刻、終了時刻、滞在時間は、終了時刻から開始時刻を引いた値である。
【００２６】
遷移確率ＤＢ７のデータ構造の例を表５に示す。
【表５】
2015095083.tif 000007
【００２７】
遷移確率ＤＢ７は、ＦｒｏｍカテゴリのＰＯＩを訪問したのち、ＴｏカテゴリのＰＯＩを訪問する確率に基づいてスコアを格納している。
【００２８】
図３は、パラメータ計算部６の処理の流れを示す図である。
【００２９】
（Ｓ２−１）パラメータ計算部６は、訪問ＰＯＩＤＢ５から未処理の連接ＰＯＩを取得する。連接ＰＯＩとは、例えば、同一系列においてＰＯＩ「Ａ」を訪問したあとにＰＯＩ「Ｂ」を訪問した場合のＡＢのペアを表す。その他にも、Ａの直後に訪問しあＰＯＩのみを対象にすることもできる。ここで同一系列は、例えば同じ日付を用いる。その他にも事前に設定された時刻で区切るなどの方法を用いることができる。本実施例では１日を１系列とする例を用いる。
【００３０】
パラメータ計算部６は、ＰＯＩＤＢ２を基に、取得した連接ＰＯＩに含まれるＰＯＩのカテゴリを取得し、遷移確率ＤＢ７のスコアを更新する。スコアの計算には、例えば、条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を用いることができる。ここでＰ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）は、ＦｒｏｍカテゴリのＰＯＩを訪問したのち、ＴｏカテゴリのＰＯＩを訪問する確率を表す。
【００３１】
具体的には、以下の手続きで条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を計算する。
【００３２】
（Ｓ２−１−ａ）全ての連接ＰＯＩに対してＰＯＩＤＢ２を用いてカテゴリを取得する。ここで、ＰＯＩ「Ａ」を訪問したあとにＰＯＩ「Ｂ」を訪問した場合、ＡのカテゴリをＦｒｏｍカテゴリ、ＢのカテゴリをＴｏカテゴリという。
【００３３】
（Ｓ２−１−ｂ）各Ｆｒｏｍカテゴリを対象に（Ｓ２−１−ｃ）の処理を行う。
【００３４】
（Ｓ２−１−ｃ）対象のＦｒｏｍカテゴリをＣＦｒｏｍとする。ＦｒｏｍカテゴリがＣＦｒｏｍ
である連接ＰＯＩを取得して総数を求める。これをＮＣＦｒｏｍとする。また、当該ＣＦｒｏｍを用いて取得された連接ＰＯＩのうち、各Ｔｏカテゴリが含まれる数をそれぞれＮＣＦｒｏｍ→ＣＴｏとする。条件付き確率Ｐ（ＣＴｏ／ＣＦｒｏｍ）は、例えば、（ＮＣＦｒｏｍ→ＣＴｏ）／ＮＣＦｒｏｍによって計算することができる。訪問がない場合にスコアがゼロになることを防ぐため、例えば予め設定した係数βを用いて、（ＮＣＦｒｏｍ→ＣＴｏ＋β）／（ＮＣＦｒｏｍ＋β｜ＣＴｏ｜）によって計算することもできる。ここで｜ＣＴｏ｜は、Ｔｏカテゴリの異なり数（種類数）である。以上の処理によって条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を求める。
【００３５】
ここでは、スコアについてはＰＯＩのカテゴリを用いた例を使って述べているが、同じ枠組みでＰＯＩそのもののスコアを用いる方法も考えられる。その場合には、Ｆｒｏｍカテゴリのカラムに対応するＰＯＩの情報を保持し、Ｔｏカテゴリのカラムに対応するＰＯＩの情報を保持すればよい。
【００３６】
（Ｓ２−２）未処理の連接ＰＯＩが存在する場合には（Ｓ２−１）に戻り、そうでない場合には（Ｓ２−３）に進む。
【００３７】
（Ｓ２−３）結果を遷移確率ＤＢ７に出力する。
【００３８】
系列推定部８は、ＰＯＩＤＢ２、滞留点ＤＢ４、遷移確率ＤＢ７を入力として受け取り、推定結果ＤＢ９を出力する。
【００３９】
推定結果ＤＢ９のデータ構造の例を表６に示す。
【表６】
2015095083.tif 000008
【００４０】
図４は、系列推定部８の処理の流れを示す図である。
【００４１】
（Ｓ３−１）系列推定部８は、滞留点ＤＢ４から未処理の系列を選択する。ここで系列は予め設定した単位を用いることができる。たとえば午前０時を区切りとする１日単位であったり、予め開始終了の時刻を設定した朝、昼、晩という単位を用いることができる。ここでは１日を単位とする例で説明する。
【００４２】
（Ｓ３−２）未処理の系列に含まれる各滞留点 に対して訪問のもっともらしさを表す訪問確率Ｐ（ｓｉ／ｘｉ)を計算する。この訪問確率の計算には例えば非特許文献２記載の方法を用いることができる。ここでＮは系列の長さを表し、ｘｉは ｉ番目の滞留点における訪問ＰＯＩの確率変数を表し、ＰＯＩ  ｋを訪問する場合には、ｘｉ＝ｋ（ｋ＝１，…，Ｋ）
の値を取る。ここでＫはＰＯＩの総異なり数（種類数）を表す。
【００４３】
（Ｓ３−３）遷移確率ＤＢ７を読み込み、系列に対するもっともらしさを表す同時確率（式１）を設定する。
【数１】
2015095083.tif 000009
【００４４】
ここで、Ｐ（ｓｉ｜ｘｉ＝ｋ）（ｋ＝１,…,Ｋ）には、（Ｓ３−２）で計算した確率を用いる。また、Ｐ（ｘｉ｜ｘｉ−１）は、滞留点ｉ−１において訪問されたＰＯＩが与えられた際の滞留点ｉにおいて訪問されるＰＯＩの条件付き確率を表す。これには、遷移確率ＤＢ７における、対応するスコアを用いることができる。また、このスコアに限らず、上記の「ＰＯＩそのもののスコア」を用いることもできる。
【００４５】
図５は、この同時確率の概略図である。
【００４６】
この図では、Ｎ個の滞留点に対して、３種類のＰＯＩのカテゴリ (ラーメン店、コンビニ、カフェ )の訪問確率Ｐ（ｓｉ／ｘｉ)を各ノードの中の数字で示し、エッジにＰＯＩのカテゴリ間の遷移確率Ｐ（ｘｉ｜ｘｉ−１）を示している。なお、この図ではＰＯＩとＰＯＩのカテゴリを区別していないことに注意すべきである。
【００４７】
系列推定部８は、後述の（Ｓ３−４）では、このような情報が与えられた場合に、式 （１）のＰ（ｘ）を最大化する確率変数ｘ１ ，…，ｘＮを求める。すなわち、図５の例では、太字で示された確率が最大化されるような経路を選択すると解釈することができる。
【００４８】
本実施例では１時点前の情報（１次の情報 )を用いて式 （１）を定式化したが、例えば、２時点前や３時点前などの高次の情報を用いた方法を利用することもできる。その場合には、遷移確率ＤＢ７に対応する高次の遷移確率（スコア）を保持し、利用することで実施可能である。
【００４９】
（Ｓ３−４）式 （１）におけるＰ（ｘ）を最大化する確率変数ｘ１ ，…，ｘＮの組を求める。図５の場合、例えば、ｘ１＝１、ｘ２＝３、…、ｘＮ−１＝３、ｘＮ＝２のような組が求まる。１はラーメン店、２はコンビニ、３はカフェに対応する。これには、例えばグリーディな探索、参考文献（G. David. Forney Jr., "The Viterbi algorithm", Proceedings of the IEEE, Vol.61, No.3, pp.268-278, 1973.）の方法などを用いることができる。そして、求めた確率変数ｘ１ ，…，ｘＮと、ＰＯＩＤＢ２の情報を元に、推定結果を推定結果ＤＢ９に出力する。すなわち、推定結果ＤＢ９には、求めた確率変数ｘ１ ，…，ｘＮに対応する各ＰＯＩの情報（ユーザが訪問する各ＰＯＩの情報）が格納されることとなる。
【００５０】
（Ｓ３−５）未処理の系列がある場合には（Ｓ３−１）に戻り、そうでない場合には処理を終了する。
【００５１】
以上のように、本実施の形態の訪問ＰＯＩ推定装置によれば、あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移確率ＤＢ７と、１つの系列に属する複数の滞留点のそれぞれに対して訪問のもっともらしさを表す訪問確率を計算し（Ｓ３−２）、系列に対するもっともらしさを表す同時確率の式（式（１）のＰ（ｘ））を訪問確率と遷移確率ＤＢ７のスコアを用いて生成し、同時確率を最大化する解を求め（Ｓ３−３）、ユーザが訪問するＰＯＩを解に基づいて推定する系列推定部８とを備えることで、遷移確率ＤＢ７のスコア（遷移確率）を利用したＰＯＩ推定ができ、よって、推定精度を向上させることができる。
【００５２】
なお、本実施の形態の訪問ＰＯＩ推定装置としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。
【符号の説明】
【００５３】
１  ＧＰＳログＤＢ
２  ＰＯＩＤＢ
３  滞留点抽出部
４  滞留点ＤＢ
５  訪問ＰＯＩＤＢ
６  パラメータ計算部
７  遷移確率ＤＢ
８  系列推定部
９  推定結果ＤＢ
【図１】
2015095083.tif 000011
【図２】
2015095083.tif 000012
【図３】
2015095083.tif 000013
【図４】
2015095083.tif 000014
【図５】
2015095083.tif 000015