JP6077979B2

JP6077979B2 - 訪問ｐｏｉ推定装置

Info

Publication number: JP6077979B2
Application number: JP2013233892A
Authority: JP
Inventors: 良彦数原; 浩之戸田; 鷲崎　誠司; 誠司鷲崎
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2013-11-12
Filing date: 2013-11-12
Publication date: 2017-02-08
Anticipated expiration: 2033-11-12
Also published as: JP2015095083A

Description

本発明は、訪問ＰＯＩ推定装置に関するものである。

ユーザがＧＰＳロガー等の装置で蓄積したＧＰＳログ履歴を利用して、どのような場所で滞在し、またどのような場所(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）を推定する装置であって、ＧＰＳログデータベース（以下、データベースをＤＢと略す）１、ＰＯＩＤＢ２、滞留点抽出部３、滞留点ＤＢ４、訪問ＰＯＩＤＢ５、パラメータ計算部６、遷移確率ＤＢ７、系列推定部８および推定結果ＤＢ９を備える。ＰＯＩは、訪問対象となる場所であり、例えば、店舗である。

滞留点抽出部３は、ＧＰＳログＤＢ１とＰＯＩＤＢ２を入力として受け取り、滞留点ＤＢ４を出力する。

ＧＰＳログＤＢ１のデータ構造の例を表１に示す。

ＧＰＳログＤＢ１には、あるユーザについてＧＰＳロガーによって取得されたログ情報（ＩＤ、日時、経度、緯度）が蓄積されている。

ＰＯＩＤＢ２のデータ構造の例を表２に示す。

ＰＯＩＤＢ２には、ユーザが訪問したＰＯＩについて、そのＩＤであるＰＯＩＩＤ、そのＰＯＩの名称、そのＰＯＩのカテゴリ、そのＰＯＩの経度、緯度などが蓄積されている。ＰＯＩＤＢ２としては既存のものを利用できる。

滞留点ＤＢ４のデータ構造の例を表３に示す。

滞留点ＤＢ４には、ユーザが滞留した領域（滞留点という）について、そのＩＤである滞留点ＩＤ、その滞留点の中心経度、中心緯度、ＧＰＳログＤＢ１における対応するログ情報に含まれる最小のＩＤである開始ＩＤ、最大のＩＤである終了ＩＤ、その滞留点に滞留した時間である滞留時間、その滞留点の次に訪問可能なＰＯＩを示すＰＯＩＩＤからなる訪問ＰＯＩ候補が蓄積される。

図２は、滞留点抽出部３の処理の流れを示す図である。

（Ｓ１−１）滞留点抽出部３は、ＧＰＳログＤＢ１を読み込み、滞留点を抽出する。この滞留点の抽出には、例えば、非特許文献１や非特許文献２記載の方法を用いることができる。滞留点抽出に必要なパラメータは予め設定されているものとする。これにより、各滞留点につき、中心経度、中心緯度、開始ＩＤ、終了ＩＤ、滞留時間などが得られる。

（Ｓ１−２）次に、各滞留点につき、ＰＯＩＤＢ２から、その滞留点の次に訪問可能なＰＯＩを示すＰＯＩＩＤからなる訪問ＰＯＩ候補を取得する。ここでは、例えば、滞留点の中心座標から一定距離の座標をもつＰＯＩのＰＯＩＩＤを取得する方法や、中心座標から近傍のＰＯＩを一定数選択し、そのＰＯＩＩＤを取得するなどの方法が考えられる。座標間の距離計算には、例えば、Ｈｕｂｅｎｙの公式やＶｉｎｃｅｎｔｙの公式を用いることができる（非特許文献２）。

（Ｓ１−３）各滞留点に滞留点ＩＤを付与し、各滞留点につき、滞留点ＩＤ、中心経度、中心緯度、開始ＩＤ、終了ＩＤ、滞留時間、訪問ＰＯＩ候補を滞留点ＤＢ４に出力する。

パラメータ計算部６は、ＰＯＩＤＢ２と訪問ＰＯＩＤＢ５を入力として受け取り、遷移確率ＤＢ７を出力する。

訪問ＰＯＩＤＢ５のデータ構造の例を表４に示す。

訪問ＰＯＩＤＢ５は、予め記録されたＧＰＳ履歴と、抽出された滞留点に対して、予めユーザが実際に訪問したＰＯＩの情報を保持している。訪問ＰＯＩＩＤは、訪問したＰＯＩのＩＤ、中心経度、中心緯度は、対応する滞留点の中心経度、中心緯度、開始時刻、終了時刻は、対応する滞留点の開始時刻、終了時刻、滞在時間は、終了時刻から開始時刻を引いた値である。

遷移確率ＤＢ７のデータ構造の例を表５に示す。

遷移確率ＤＢ７は、ＦｒｏｍカテゴリのＰＯＩを訪問したのち、ＴｏカテゴリのＰＯＩを訪問する確率に基づいてスコアを格納している。

図３は、パラメータ計算部６の処理の流れを示す図である。

（Ｓ２−１）パラメータ計算部６は、訪問ＰＯＩＤＢ５から未処理の連接ＰＯＩを取得する。連接ＰＯＩとは、例えば、同一系列においてＰＯＩ「Ａ」を訪問したあとにＰＯＩ「Ｂ」を訪問した場合のＡＢのペアを表す。その他にも、Ａの直後に訪問しあＰＯＩのみを対象にすることもできる。ここで同一系列は、例えば同じ日付を用いる。その他にも事前に設定された時刻で区切るなどの方法を用いることができる。本実施例では１日を１系列とする例を用いる。

パラメータ計算部６は、ＰＯＩＤＢ２を基に、取得した連接ＰＯＩに含まれるＰＯＩのカテゴリを取得し、遷移確率ＤＢ７のスコアを更新する。スコアの計算には、例えば、条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を用いることができる。ここでＰ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）は、ＦｒｏｍカテゴリのＰＯＩを訪問したのち、ＴｏカテゴリのＰＯＩを訪問する確率を表す。

具体的には、以下の手続きで条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を計算する。

（Ｓ２−１−ａ）全ての連接ＰＯＩに対してＰＯＩＤＢ２を用いてカテゴリを取得する。ここで、ＰＯＩ「Ａ」を訪問したあとにＰＯＩ「Ｂ」を訪問した場合、ＡのカテゴリをＦｒｏｍカテゴリ、ＢのカテゴリをＴｏカテゴリという。

（Ｓ２−１−ｂ）各Ｆｒｏｍカテゴリを対象に（Ｓ２−１−ｃ）の処理を行う。

（Ｓ２−１−ｃ）対象のＦｒｏｍカテゴリをＣ_Ｆｒｏｍとする。ＦｒｏｍカテゴリがＣ_Ｆｒｏｍ
である連接ＰＯＩを取得して総数を求める。これをＮ_{ＣＦｒｏｍ}とする。また、当該Ｃ_Ｆｒｏｍを用いて取得された連接ＰＯＩのうち、各Ｔｏカテゴリが含まれる数をそれぞれＮ_{ＣＦｒｏｍ→ＣＴｏ}とする。条件付き確率Ｐ（Ｃ_Ｔｏ／Ｃ_Ｆｒｏｍ）は、例えば、（Ｎ_{ＣＦｒｏｍ→ＣＴｏ}）／Ｎ_{ＣＦｒｏｍ}によって計算することができる。訪問がない場合にスコアがゼロになることを防ぐため、例えば予め設定した係数βを用いて、（Ｎ_{ＣＦｒｏｍ→ＣＴｏ}＋β）／（Ｎ_{ＣＦｒｏｍ}＋β｜Ｃ_Ｔｏ｜）によって計算することもできる。ここで｜Ｃ_Ｔｏ｜は、Ｔｏカテゴリの異なり数（種類数）である。以上の処理によって条件付き確率Ｐ（Ｔｏカテゴリ／Ｆｒｏｍカテゴリ）を求める。

ここでは、スコアについてはＰＯＩのカテゴリを用いた例を使って述べているが、同じ枠組みでＰＯＩそのもののスコアを用いる方法も考えられる。その場合には、Ｆｒｏｍカテゴリのカラムに対応するＰＯＩの情報を保持し、Ｔｏカテゴリのカラムに対応するＰＯＩの情報を保持すればよい。

（Ｓ２−２）未処理の連接ＰＯＩが存在する場合には（Ｓ２−１）に戻り、そうでない場合には（Ｓ２−３）に進む。

（Ｓ２−３）結果を遷移確率ＤＢ７に出力する。

系列推定部８は、ＰＯＩＤＢ２、滞留点ＤＢ４、遷移確率ＤＢ７を入力として受け取り、推定結果ＤＢ９を出力する。

推定結果ＤＢ９のデータ構造の例を表６に示す。

図４は、系列推定部８の処理の流れを示す図である。

（Ｓ３−１）系列推定部８は、滞留点ＤＢ４から未処理の系列を選択する。ここで系列は予め設定した単位を用いることができる。たとえば午前０時を区切りとする１日単位であったり、予め開始終了の時刻を設定した朝、昼、晩という単位を用いることができる。ここでは１日を単位とする例で説明する。

（Ｓ３−２）未処理の系列に含まれる各滞留点に対して訪問のもっともらしさを表す訪問確率Ｐ（ｓ_ｉ／ｘ_ｉ)を計算する。この訪問確率の計算には例えば非特許文献２記載の方法を用いることができる。ここでＮは系列の長さを表し、ｘ_ｉはｉ番目の滞留点における訪問ＰＯＩの確率変数を表し、ＰＯＩｋを訪問する場合には、ｘ_ｉ＝ｋ（ｋ＝１，…，Ｋ）
の値を取る。ここでＫはＰＯＩの総異なり数（種類数）を表す。

（Ｓ３−３）遷移確率ＤＢ７を読み込み、系列に対するもっともらしさを表す同時確率（式１）を設定する。

ここで、Ｐ（ｓ_ｉ｜ｘ_ｉ＝ｋ）（ｋ＝１,…,Ｋ）には、（Ｓ３−２）で計算した確率を用いる。また、Ｐ（ｘ_ｉ｜ｘ_ｉ−１）は、滞留点ｉ−１において訪問されたＰＯＩが与えられた際の滞留点ｉにおいて訪問されるＰＯＩの条件付き確率を表す。これには、遷移確率ＤＢ７における、対応するスコアを用いることができる。また、このスコアに限らず、上記の「ＰＯＩそのもののスコア」を用いることもできる。

図５は、この同時確率の概略図である。

この図では、Ｎ個の滞留点に対して、３種類のＰＯＩのカテゴリ (ラーメン店、コンビニ、カフェ )の訪問確率Ｐ（ｓ_ｉ／ｘ_ｉ)を各ノードの中の数字で示し、エッジにＰＯＩのカテゴリ間の遷移確率Ｐ（ｘ_ｉ｜ｘ_ｉ−１）を示している。なお、この図ではＰＯＩとＰＯＩのカテゴリを区別していないことに注意すべきである。

系列推定部８は、後述の（Ｓ３−４）では、このような情報が与えられた場合に、式（１）のＰ（ｘ）を最大化する確率変数ｘ_１，…，ｘ_Ｎを求める。すなわち、図５の例では、太字で示された確率が最大化されるような経路を選択すると解釈することができる。

本実施例では１時点前の情報（１次の情報 )を用いて式（１）を定式化したが、例えば、２時点前や３時点前などの高次の情報を用いた方法を利用することもできる。その場合には、遷移確率ＤＢ７に対応する高次の遷移確率（スコア）を保持し、利用することで実施可能である。

（Ｓ３−４）式（１）におけるＰ（ｘ）を最大化する確率変数ｘ_１，…，ｘ_Ｎの組を求める。図５の場合、例えば、ｘ_１＝１、ｘ_２＝３、…、ｘ_Ｎ−１＝３、ｘ_Ｎ＝２のような組が求まる。１はラーメン店、２はコンビニ、３はカフェに対応する。これには、例えばグリーディな探索、参考文献（G. David. Forney Jr., "The Viterbi algorithm", Proceedings of the IEEE, Vol.61, No.3, pp.268-278, 1973.）の方法などを用いることができる。そして、求めた確率変数ｘ_１，…，ｘ_Ｎと、ＰＯＩＤＢ２の情報を元に、推定結果を推定結果ＤＢ９に出力する。すなわち、推定結果ＤＢ９には、求めた確率変数ｘ_１，…，ｘ_Ｎに対応する各ＰＯＩの情報（ユーザが訪問する各ＰＯＩの情報）が格納されることとなる。

（Ｓ３−５）未処理の系列がある場合には（Ｓ３−１）に戻り、そうでない場合には処理を終了する。

以上のように、本実施の形態の訪問ＰＯＩ推定装置によれば、あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移確率ＤＢ７と、１つの系列に属する複数の滞留点のそれぞれに対して訪問のもっともらしさを表す訪問確率を計算し（Ｓ３−２）、系列に対するもっともらしさを表す同時確率の式（式（１）のＰ（ｘ））を訪問確率と遷移確率ＤＢ７のスコアを用いて生成し、同時確率を最大化する解を求め（Ｓ３−３）、ユーザが訪問するＰＯＩを解に基づいて推定する系列推定部８とを備えることで、遷移確率ＤＢ７のスコア（遷移確率）を利用したＰＯＩ推定ができ、よって、推定精度を向上させることができる。

なお、本実施の形態の訪問ＰＯＩ推定装置としてコンピュータを機能させるためのコンピュータプログラムは、半導体メモリ、磁気ディスク、光ディスク、光磁気ディスク、磁気テープなどのコンピュータ読み取り可能な記録媒体に記録でき、また、インターネットなどの通信網を介して伝送させて、広く流通させることができる。

１ＧＰＳログＤＢ
２ＰＯＩＤＢ
３滞留点抽出部
４滞留点ＤＢ
５訪問ＰＯＩＤＢ
６パラメータ計算部
７遷移確率ＤＢ
８系列推定部
９推定結果ＤＢ

Claims

ユーザが訪問するＰＯＩを推定する訪問ＰＯＩ推定装置であって、
あるＰＯＩを訪問したのちに別のＰＯＩを訪問する確率に基づいたスコアを格納する遷移確率ＤＢと、
１つの系列に属する複数の滞留点のそれぞれに対して訪問のもっともらしさを表す訪問確率を計算し、前記系列に対するもっともらしさを表す同時確率の式を前記訪問確率と前記遷移確率ＤＢのスコアを用いて生成し、前記同時確率を最大化する解を求め、前記訪問するＰＯＩを前記解に基づいて推定する系列推定部と
を備えることを特徴とする訪問ＰＯＩ推定装置。
Ｎ個の滞留点に含まれる滞留点ｉについての訪問確率をＰ（ｓ_ｉ／ｘ_ｉ)、スコアをＰ（ｘ_ｉ｜ｘ_ｉ−１）とした場合、同時確率の式は、

であることを特徴とする請求項１記載の訪問ＰＯＩ推定装置。
請求項１または２記載の訪問ＰＯＩ推定装置としてコンピュータを機能させるためのコンピュータプログラム。