(57)【特許請求の範囲】
【請求項１】
ユーザの目的地となる訪問スポットを予測する目的地予測装置であって、
緯度、経度、及び測位時間の組からなる前記ユーザの移動軌跡の移動軌跡集合と、前記ユーザが訪問した訪問スポット、前記訪問スポットのカテゴリ、及び前記訪問スポットの訪問時間の組の系列である訪問地系列の訪問地系列集合とに基づいて、前記ユーザの移動軌跡から目的地を予測するための予測モデルを学習する目的地予測学習部と、
前記ユーザが移動した緯度、経度、及び測位時間の組からなる入力移動軌跡と、前記入力移動軌跡における出発地となる訪問スポットと、前記学習された予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットを予測する予測実施部と、
を含み、前記目的地予測学習部は、前記訪問スポットの訪問回数と、前記訪問地系列集合に基づく緯度経度空間を分割して得られる分割領域である地域メッシュにおける、前記訪問スポットの前記地域メッシュに含まれる訪問スポットの訪問回数と、前記地域メッシュに含まれるスポット数とに基づいて、前記地域メッシュの各々について、前記地域メッシュ内における訪問スポットの各々の訪問確率を学習するメッシュ内目的地予測学習部を含む、目的地予測装置。
【請求項２】
前記目的地予測学習部は、
前記移動軌跡集合の前記移動軌跡の各々から、前記ユーザが一定以上滞留した点である滞留点を抽出し、
前記滞留点と、前記訪問地系列集合とから、前記滞留点における滞留開始時刻から滞留終了時刻までの間に、前記ユーザが訪問した訪問スポットの訪問時刻が含まれる場合に、前記滞留点と前記訪問スポットとを対応付けることにより、前記滞留点と前記訪問スポットと前記訪問スポットのカテゴリとを対応付けた訪問地カテゴリ学習データを生成し、
前記移動軌跡集合の前記移動軌跡の各々について、前記移動軌跡を、前記滞留点における滞留開始時刻から滞留終了時刻までの間に含まれない、分割移動軌跡に分割して、分割移動軌跡集合を生成し、
前記分割移動軌跡集合に含まれる前記分割移動軌跡の各々について、前記分割移動軌跡の前後の訪問スポットのカテゴリを表すカテゴリ遷移データを生成し、
前記分割移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記分割移動軌跡を、前記地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するセグメンテーション前処理部と、
前記生成されたカテゴリ遷移データに基づいて、カテゴリ間の遷移確率であるカテゴリ遷移確率を学習する目的地カテゴリ予測学習部と、
前記メッシュ遷移系列データに基づいて、出発地となる前記地域メッシュから現在地となる前記地域メッシュまでのメッシュ遷移系列データから、推定対象の前記地域メッシュが目的地となる確率を予測するための推定器を学習する目的地メッシュ予測学習部と、
前記セグメンテーション前処理部により得られた前記メッシュ遷移系列データに基づいて、時間帯毎に、前記時間帯において各地域メッシュを訪問する確率を表す確率分布を学習する時間帯別メッシュ分布学習部と、
を更に含む請求項１に記載の目的地予測装置。
【請求項３】
前記予測実施部は、
前記入力移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記入力移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するメッシュ変換部と、
前記メッシュ変換部により出力されたメッシュ遷移系列データに基づいて、目的地の候補が含まれる前記地域メッシュの集合である目的地メッシュ候補集合を出力する目的地メッシュ予測部と、
前記目的地メッシュ候補集合に含まれる地域メッシュの各々に対して、前記目的地予測学習部によって学習された前記予測モデルに基づいて、前記地域メッシュ内における訪問スポットの訪問確率を推定するメッシュ内目的地予測部と、
訪問スポットが所属するカテゴリが予め格納されたスポットデータベースから、前記入力移動軌跡における出発地となる訪問スポットが所属する出発スポットカテゴリを取得する出発スポットカテゴリ取得部と、
前記出発スポットカテゴリ取得部により取得された出発スポットカテゴリと、予め学習された前記予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットのカテゴリである目的地カテゴリを推定する目的地カテゴリ予測部と、
前記入力移動軌跡に含まれる現在地の測位時間と、予め学習された前記予測モデルとに基づいて、前記現在地の測位時間が属する時間帯に前記ユーザが各地域メッシュを訪問する確率を表すメッシュ訪問分布を推定する時間帯別メッシュ分布推定部と、
前記目的地メッシュ予測部により推定された前記目的地メッシュ候補集合と、前記メッシュ内目的地予測部により前記地域メッシュの各々に対して推定された前記地域メッシュ内における訪問スポットの訪問確率と、前記目的地カテゴリ予測部により推定された目的地カテゴリと、前記時間帯別メッシュ分布推定部により推定された前記メッシュ訪問分布とを統合した結果に基づいて、前記目的地メッシュ候補集合に含まれる地域メッシュ内の訪問スポットのうち、前記ユーザの目的地となる訪問スポットを推定する確率統合部と、
を含む請求項１又は請求項２に記載の目的地予測装置。
【請求項４】
ユーザの目的地となる訪問スポットを予測する目的地予測装置における目的地予測方法であって、
目的地予測学習部が、緯度、経度、及び測位時間の組からなる前記ユーザの移動軌跡の移動軌跡集合と、前記ユーザが訪問した訪問スポット、前記訪問スポットのカテゴリ、及び前記訪問スポットの訪問時間の組の系列である訪問地系列の訪問地系列集合とに基づいて、前記ユーザの移動軌跡から目的地を予測するための予測モデルを学習するステップと、
予測実施部が、前記ユーザが移動した緯度、経度、及び測位時間の組からなる入力移動軌跡と、前記入力移動軌跡における出発地となる訪問スポットと、前記学習された予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットを予測するステップと、
を含み、前記目的地予測学習部が学習するステップは、前記訪問スポットの訪問回数と、前記訪問地系列集合に基づく緯度経度空間を分割して得られる分割領域である地域メッシュにおける、前記訪問スポットの前記地域メッシュに含まれる訪問スポットの訪問回数と、前記地域メッシュに含まれるスポット数とに基づいて、前記地域メッシュの各々について、前記地域メッシュ内における訪問スポットの各々の訪問確率を学習するステップを含む、目的地予測方法。
【請求項５】
前記目的地予測学習部が学習するステップは、
セグメンテーション前処理部が、前記移動軌跡集合の前記移動軌跡の各々から、前記ユーザが一定以上滞留した点である滞留点を抽出ステップ、
前記セグメンテーション前処理部が、前記滞留点と、前記訪問地系列集合とから、前記滞留点における滞留開始時刻から滞留終了時刻までの間に、前記ユーザが訪問した訪問スポットの訪問時刻が含まれる場合に、前記滞留点と前記訪問スポットとを対応付けることにより、前記滞留点と前記訪問スポットと前記訪問スポットのカテゴリとを対応付けた訪問地カテゴリ学習データを生成するステップと、
前記セグメンテーション前処理部が、前記移動軌跡集合の前記移動軌跡の各々について、前記移動軌跡を、前記滞留点における滞留開始時刻から滞留終了時刻までの間に含まれない、分割移動軌跡に分割して、分割移動軌跡集合を生成するステップと、
前記セグメンテーション前処理部が、前記分割移動軌跡集合に含まれる前記分割移動軌跡の各々について、前記分割移動軌跡の前後の訪問スポットのカテゴリを表すカテゴリ遷移データを生成するステップと、
前記セグメンテーション前処理部が、前記分割移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記分割移動軌跡を、前記地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するステップと、
目的地カテゴリ予測学習部が、前記生成されたカテゴリ遷移データに基づいて、カテゴリ間の遷移確率であるカテゴリ遷移確率を学習するステップと、
目的地メッシュ予測学習部が、前記メッシュ遷移系列データに基づいて、出発地となる前記地域メッシュから現在地となる前記地域メッシュまでのメッシュ遷移系列データから、推定対象の前記地域メッシュが目的地となる確率を予測するための推定器を学習するステップと、
時間帯別メッシュ分布学習部が、前記セグメンテーション前処理部により得られた前記メッシュ遷移系列データに基づいて、時間帯毎に、前記時間帯において各地域メッシュを訪問する確率を表す確率分布を学習するステップと、
を更に含む請求項４に記載の目的地予測方法。
【請求項６】
前記予測実施部が予測するステップは、
メッシュ変換部が、前記入力移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記入力移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するステップと、
目的地メッシュ予測部が、前記メッシュ変換部により出力されたメッシュ遷移系列データに基づいて、目的地の候補が含まれる前記地域メッシュの集合である目的地メッシュ候補集合を出力するステップと、
メッシュ内目的地予測部が、前記目的地メッシュ候補集合に含まれる地域メッシュの各々に対して、前記目的地予測学習部によって学習された前記予測モデルに基づいて、前記地域メッシュ内における訪問スポットの訪問確率を推定するステップと、
出発スポットカテゴリ取得部が、訪問スポットが所属するカテゴリが予め格納されたスポットデータベースから、前記入力移動軌跡における出発地となる訪問スポットが所属する出発スポットカテゴリを取得するステップと、
目的地カテゴリ予測部が、前記出発スポットカテゴリ取得部により取得された出発スポットカテゴリと、予め学習された前記予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットのカテゴリである目的地カテゴリを推定するステップと、
時間帯別メッシュ分布推定部が、前記入力移動軌跡に含まれる現在地の測位時間と、予め学習された前記予測モデルとに基づいて、前記現在地の測位時間が属する時間帯に前記ユーザが各地域メッシュを訪問する確率を表すメッシュ訪問分布を推定するステップと、
確率統合部が、前記目的地メッシュ予測部により推定された前記目的地メッシュ候補集合と、前記メッシュ内目的地予測部により前記地域メッシュの各々に対して推定された前記地域メッシュ内における訪問スポットの訪問確率と、前記目的地カテゴリ予測部により推定された目的地カテゴリと、前記時間帯別メッシュ分布推定部により推定された前記メッシュ訪問分布とを統合した結果に基づいて、前記目的地メッシュ候補集合に含まれる地域メッシュ内の訪問スポットのうち、前記ユーザの目的地となる訪問スポットを推定するステップと、
を含む請求項４又は請求項５に記載の目的地予測方法。
【請求項７】
コンピュータを、請求項１〜請求項３のいずれか１項に記載の目的地予測装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、目的地予測装置、方法、及びプログラムに係り、特に、ユーザの目的地を精度よく予測するための目的地予測装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
携帯電話やスマートフォンなどの普及によって、ＧＰＳやＷｉ−ｆｉ（Ｒ）、Ｂｌｕｅｔｏｏｔｈ（Ｒ）、携帯基地局等に基づくユーザの位置情報に関する測位データの取得は非常に容易になった。この測位データを用いて、移動中のユーザが目指している場所である目的地を抽出することができれば、情報推薦や生活支援など幅広いサービスに応用可能である。
【０００３】
これまで、非特許文献１などにより、緯度、経度、及び時間の組の系列である移動軌跡からユーザの目的地を予測する目的地予測技術が提案されてきた。
【０００４】
また、非特許文献２などにより、訪問地の系列を学習して目的地を予測する目的地予測技術が提案されてきた。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Andy Yuan Xue, Rui Zhang, Yu Zheng, Xing Xie, Jin Huang, Zhenghua Xu: Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. ICDE 2013: 254-265.
【非特許文献２】Anastasios Noulas, Salvatore Scellato, Neal Lathia, Cecilia Mascolo: Mining User Mobility Features for Next Place Prediction in Location-Based Services. ICDM 2012: 1038-1043
【非特許文献３】Yu Zheng, Lizhu Zhang, Xing Xie, Wei-Ying Ma:Mining interesting locations and travel sequences from GPS trajectories. WWW 2009: 791-800
【非特許文献４】Wikipedia foundation,“ジオハッシュ”［2015年9月4日確認］,URL:https://ja.wikipedia.org/wiki/%E3%82%B8%E3%82%AA%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述した従来手法のうち、移動軌跡のみを利用する従来手法は、滞在地についての情報を考慮しないので、どのお店に向かっているか等の詳細な予測ができない。また、スポットの訪問系列のみを利用する従来手法は、移動軌跡による出発地から現在地までの間の情報を利用して精度向上することができない。
【０００７】
本発明は、上記問題点を解決するために成されたものであり、ユーザの目的地となる訪問スポットを、精度よく予測することができる目的地予測装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、第１の発明に係る目的地予測装置は、ユーザの目的地となる訪問スポットを予測する目的地予測装置であって、緯度、経度、及び測位時間の組からなる前記ユーザの移動軌跡の移動軌跡集合と、前記ユーザが訪問した訪問スポット、前記訪問スポットのカテゴリ、及び前記訪問スポットの訪問時間の組の系列である訪問地系列の訪問地系列集合とに基づいて、前記ユーザの移動軌跡から目的地を予測するための予測モデルを学習する目的地予測学習部と、前記ユーザが移動した緯度、経度、及び測位時間の組からなる入力移動軌跡と、前記入力移動軌跡における出発地となる訪問スポットと、前記学習された予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットを予測する予測実施部と、を含んで構成されている。
【０００９】
また、第１の発明に係る目的地予測装置において、前記目的地予測学習部は、前記移動軌跡集合の前記移動軌跡の各々から、前記ユーザが一定以上滞留した点である滞留点を抽出し、前記滞留点と、前記訪問地系列集合とから、前記滞留点における滞留開始時刻から滞留終了時刻までの間に、前記ユーザが訪問した訪問スポットの訪問時刻が含まれる場合に、前記滞留点と前記訪問スポットとを対応付けることにより、前記滞留点と前記訪問スポットと前記訪問スポットのカテゴリとを対応付けた訪問地カテゴリ学習データを生成し、前記移動軌跡集合の前記移動軌跡の各々について、前記移動軌跡を、前記滞留点における滞留開始時刻から滞留終了時刻までの間に含まれない、分割移動軌跡に分割して、分割移動軌跡集合を生成し、前記分割移動軌跡集合に含まれる前記分割移動軌跡の各々について、前記分割移動軌跡の前後の訪問スポットのカテゴリを表すカテゴリ遷移データを生成し、前記分割移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記分割移動軌跡を、前記地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するセグメンテーション前処理部と、前記生成されたカテゴリ遷移データに基づいて、カテゴリ間の遷移確率であるカテゴリ遷移確率を学習する目的地カテゴリ予測学習部と、前記メッシュ遷移系列データに基づいて、出発地となる前記地域メッシュから現在地となる前記地域メッシュまでのメッシュ遷移系列データから、推定対象の前記地域メッシュが目的地となる確率を予測するための推定器を学習する目的地メッシュ予測学習部と、前記訪問地系列集合に基づいて、前記地域メッシュの各々について、前記地域メッシュ内における訪問スポットの各々の訪問確率を学習するメッシュ内目的地予測学習部と、前記セグメンテーション前処理部により得られた前記メッシュ遷移系列データに基づいて、時間帯毎に、前記時間帯において各地域メッシュを訪問する確率を表す確率分布を学習する時間帯別メッシュ分布学習部と、を含むようにしてもよい。
【００１０】
また、第１の発明に係る目的地予測装置において、前記予測実施部は、前記入力移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記入力移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するメッシュ変換部と、前記メッシュ変換部により出力されたメッシュ遷移系列データに基づいて、目的地の候補が含まれる前記地域メッシュの集合である目的地メッシュ候補集合を出力する目的地メッシュ予測部と、前記目的地メッシュ候補集合に含まれる地域メッシュの各々に対して、前記目的地予測学習部によって学習された前記予測モデルに基づいて、前記地域メッシュ内における訪問スポットの訪問確率を推定するメッシュ内目的地予測部と、訪問スポットが所属するカテゴリが予め格納されたスポットデータベースから、前記入力移動軌跡における出発地となる訪問スポットが所属する出発スポットカテゴリを取得する出発スポットカテゴリ取得部と、前記出発スポットカテゴリ取得部により取得された出発スポットカテゴリと、予め学習された前記予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットのカテゴリである目的地カテゴリを推定する目的地カテゴリ予測部と、前記入力移動軌跡に含まれる現在地の測位時間と、予め学習された前記予測モデルとに基づいて、前記現在地の測位時間が属する時間帯に前記ユーザが各地域メッシュを訪問する確率を表すメッシュ訪問分布を推定する時間帯別メッシュ分布推定部と、前記目的地メッシュ予測部により推定された前記目的地メッシュ候補集合と、前記メッシュ内目的地予測部により前記地域メッシュの各々に対して推定された前記地域メッシュ内における訪問スポットの訪問確率と、前記目的地カテゴリ予測部により推定された目的地カテゴリと、前記時間帯別メッシュ分布推定部により推定された前記メッシュ訪問分布とを統合した結果に基づいて、前記目的地メッシュ候補集合に含まれる地域メッシュ内の訪問スポットのうち、前記ユーザの目的地となる訪問スポットを推定する確率統合部と、を含むようにしてもよい。
【００１１】
第２の発明に係る目的地予測方法は、ユーザの目的地となる訪問スポットを予測する目的地予測装置における目的地予測方法であって、目的地予測学習部が、緯度、経度、及び測位時間の組からなる前記ユーザの移動軌跡の移動軌跡集合と、前記ユーザが訪問した訪問スポット、前記訪問スポットのカテゴリ、及び前記訪問スポットの訪問時間の組の系列である訪問地系列の訪問地系列集合とに基づいて、前記ユーザの移動軌跡から目的地を予測するための予測モデルを学習するステップと、予測実施部が、前記ユーザが移動した緯度、経度、及び測位時間の組からなる入力移動軌跡と、前記入力移動軌跡における出発地となる訪問スポットと、前記学習された予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットを予測するステップと、を含んで実行することを特徴とする。
【００１２】
また、第２の発明に係る目的地予測方法において、前記目的地予測学習部が学習するステップは、セグメンテーション前処理部が、前記移動軌跡集合の前記移動軌跡の各々から、前記ユーザが一定以上滞留した点である滞留点を抽出ステップ、前記セグメンテーション前処理部が、前記滞留点と、前記訪問地系列集合とから、前記滞留点における滞留開始時刻から滞留終了時刻までの間に、前記ユーザが訪問した訪問スポットの訪問時刻が含まれる場合に、前記滞留点と前記訪問スポットとを対応付けることにより、前記滞留点と前記訪問スポットと前記訪問スポットのカテゴリとを対応付けた訪問地カテゴリ学習データを生成するステップと、前記セグメンテーション前処理部が、前記移動軌跡集合の前記移動軌跡の各々について、前記移動軌跡を、前記滞留点における滞留開始時刻から滞留終了時刻までの間に含まれない、分割移動軌跡に分割して、分割移動軌跡集合を生成するステップと、前記セグメンテーション前処理部が、前記分割移動軌跡集合に含まれる前記分割移動軌跡の各々について、前記分割移動軌跡の前後の訪問スポットのカテゴリを表すカテゴリ遷移データを生成するステップと、前記セグメンテーション前処理部が、前記分割移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記分割移動軌跡を、前記地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するステップと、目的地カテゴリ予測学習部が、前記生成されたカテゴリ遷移データに基づいて、カテゴリ間の遷移確率であるカテゴリ遷移確率を学習するステップと、目的地メッシュ予測学習部が、前記メッシュ遷移系列データに基づいて、出発地となる前記地域メッシュから現在地となる前記地域メッシュまでのメッシュ遷移系列データから、推定対象の前記地域メッシュが目的地となる確率を予測するための推定器を学習するステップと、メッシュ内目的地予測学習部が、前記訪問地系列集合に基づいて、前記地域メッシュの各々について、前記地域メッシュ内における訪問スポットの各々の訪問確率を学習するステップと、時間帯別メッシュ分布学習部が、前記セグメンテーション前処理部により得られた前記メッシュ遷移系列データに基づいて、時間帯毎に、前記時間帯において各地域メッシュを訪問する確率を表す確率分布を学習するステップと、を含むようにしてもよい。
【００１３】
また、第２の発明に係る目的地予測方法において、前記予測実施部が予測するステップは、メッシュ変換部が、前記入力移動軌跡に含まれる緯度及び経度の組を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、前記入力移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換するステップと、目的地メッシュ予測部が、前記メッシュ変換部により出力されたメッシュ遷移系列データに基づいて、目的地の候補が含まれる前記地域メッシュの集合である目的地メッシュ候補集合を出力するステップと、メッシュ内目的地予測部が、前記目的地メッシュ候補集合に含まれる地域メッシュの各々に対して、前記目的地予測学習部によって学習された前記予測モデルに基づいて、前記地域メッシュ内における訪問スポットの訪問確率を推定するステップと、出発スポットカテゴリ取得部が、訪問スポットが所属するカテゴリが予め格納されたスポットデータベースから、前記入力移動軌跡における出発地となる訪問スポットが所属する出発スポットカテゴリを取得するステップと、目的地カテゴリ予測部が、前記出発スポットカテゴリ取得部により取得された出発スポットカテゴリと、予め学習された前記予測モデルとに基づいて、前記ユーザの目的地となる訪問スポットのカテゴリである目的地カテゴリを推定するステップと、時間帯別メッシュ分布推定部が、前記入力移動軌跡に含まれる現在地の測位時間と、予め学習された前記予測モデルとに基づいて、前記現在地の測位時間が属する時間帯に前記ユーザが各地域メッシュを訪問する確率を表すメッシュ訪問分布を推定するステップと、確率統合部が、前記目的地メッシュ予測部により推定された前記目的地メッシュ候補集合と、前記メッシュ内目的地予測部により前記地域メッシュの各々に対して推定された前記地域メッシュ内における訪問スポットの訪問確率と、前記目的地カテゴリ予測部により推定された目的地カテゴリと、前記時間帯別メッシュ分布推定部により推定された前記メッシュ訪問分布とを統合した結果に基づいて、前記目的地メッシュ候補集合に含まれる地域メッシュ内の訪問スポットのうち、前記ユーザの目的地となる訪問スポットを推定するステップと、を含むようにしてもよい。
【００１４】
第３の発明に係るプログラムは、コンピュータを、上記第１の発明に係る目的地予測装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１５】
本発明の目的地予測装置、方法、及びプログラムによれば、移動軌跡集合と、訪問地系列集合とに基づいて、ユーザの移動軌跡から目的地を予測するための予測モデルを学習し、入力移動軌跡と、出発地となる訪問スポットと、学習された予測モデルとに基づいて、ユーザの目的地となる訪問スポットを予測することにより、ユーザの目的地となる訪問スポットを、精度よく予測することができる、という効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施の形態に係る目的地予測装置の構成を示すブロック図である。
【図２】セグメンテーション前処理部３０の処理により得られるデータの一例を示す図である。
【図３】スポットデータベース４６のテーブル構成及びデータベースを用いた検索の一例を示す図である。
【図４】本発明の実施の形態に係る目的地予測装置における目的地予測学習処理ルーチンを示すフローチャートである。
【図５】本発明の実施の形態に係る目的地予測装置における予測実施処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１８】
＜本発明の実施の形態に係る目的地予測装置の構成＞
【００１９】
まず、本発明の実施の形態に係る目的地予測装置の構成について説明する。図１に示すように、本発明の実施の形態に係る目的地予測装置１００は、ＣＰＵと、ＲＡＭと、後述する目的地予測学習処理ルーチン、及び予測実施処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この目的地予測装置１００は、機能的には図１に示すように演算部２０と、出力部６０とを備えている。
【００２０】
演算部２０は、目的地予測学習部２１と、予測実施部２２とを含んで構成されている。
【００２１】
目的地予測学習部２１は、セグメンテーション前処理部３０と、目的地カテゴリ予測学習部３２と、目的地メッシュ予測学習部３４と、メッシュ内目的地予測学習部３６と、時間帯別メッシュ分布学習部３８とを含んで構成されている。
【００２２】
目的地予測学習部２１は上記各部の処理によって、緯度、経度、及び測位時間の組からなる特定のユーザの移動軌跡の移動軌跡集合と、当該特定のユーザが訪問した訪問スポット、訪問スポットのカテゴリ、及び訪問スポットの訪問時間の組の系列である訪問地系列の訪問地系列集合とに基づいて、当該特定のユーザの移動軌跡から目的地を予測するための予測モデルを学習する。
【００２３】
ここで、カテゴリ間の遷移確率であるカテゴリ遷移確率、推定対象の緯度経度空間を分割して得られる分割領域である地域メッシュが目的地となる確率を予測するための推定器、地域メッシュ内における訪問スポットの各々の訪問確率、及び時間帯において各地域メッシュを訪問する確率を表す確率分布、の各々が予測モデルの一例であり、以下これらを総称したものを予測モデルと記載する。
【００２４】
予測実施部２２は、メッシュ変換部４０と、目的地メッシュ予測部４２と、メッシュ内目的地予測部４４と、スポットデータベース４６と、出発スポットカテゴリ取得部４８と、目的地カテゴリ予測部５０と、時間帯別メッシュ分布推定部５２と、確率統合部５４とを含んで構成されている。
【００２５】
予測実施部２２は、特定のユーザが移動した緯度、経度、及び測位時間の組からなる入力移動軌跡と、入力移動軌跡における出発地となる訪問スポットと、当該特定のユーザについて学習された予測モデルとに基づいて、当該特定のユーザの目的地となる訪問スポットを予測する。なお、目的地予測学習部２１における特定のユーザと、予測実施部２２における特定のユーザは同一のユーザである。
【００２６】
次に、目的地予測学習部２１の各部の詳細な処理について説明する。目的地予測学習部２１は、移動軌跡集合と、訪問地系列集合とを受け付けて各部の処理を行う。
【００２７】
セグメンテーション前処理部３０は、受け付けた移動軌跡集合、及び訪問地系列集合を用いて以下の第１〜第５の処理を行う。
【００２８】
セグメンテーション前処理部３０は、第１の処理として、移動軌跡集合の移動軌跡の各々から、ユーザが一定以上滞留した点である滞留点を抽出する。滞留点は、緯度、経度、滞留開始時間、滞留終了時間の組である。滞留点の抽出には、非特許文献３などで提案されている手法が利用可能である。
【００２９】
セグメンテーション前処理部３０は、第２の処理として、第１の処理で抽出された滞留点と、訪問地系列集合とから、抽出された滞留点の各々について、当該滞留点における滞留開始時刻から滞留終了時刻までの間に、ユーザが訪問した訪問スポットの訪問時刻が含まれる場合に、当該滞留点と訪問スポットとを対応付けることにより、滞留点と訪問スポットと訪問スポットのカテゴリとを対応付けた訪問地カテゴリ学習データを生成する。
【００３０】
セグメンテーション前処理部３０は、第３の処理として、移動軌跡集合の移動軌跡の各々について、当該移動軌跡を、滞留点における滞留開始時刻から滞留終了時刻までの間に含まれない、分割移動軌跡に分割して、分割移動軌跡集合を生成する。
【００３１】
セグメンテーション前処理部３０は、第４の処理として、分割移動軌跡集合に含まれる分割移動軌跡の各々について、訪問地カテゴリ学習データに含まれる訪問スポットのカテゴリを用いて、当該分割移動軌跡の前後の訪問スポットのカテゴリを表すカテゴリ遷移データ（遷移前カテゴリ、及び遷移後カテゴリの組）を生成する。
【００３２】
セグメンテーション前処理部３０は、第５の処理として、分割移動軌跡に含まれる緯度及び経度の組の各々を、地域メッシュに変換することにより、分割移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換する。緯度及び経度から地域メッシュへの変換方法としては、非特許文献４などで示される手法が利用可能である。
【００３３】
目的地カテゴリ予測学習部３２は、セグメンテーション前処理部３０で生成されたカテゴリ遷移データに基づいて、カテゴリ間の遷移確率であるカテゴリ遷移確率を、カテゴリのペアの各々について学習する。遷移前カテゴリｃｓから遷移後カテゴリｃｄに遷移するカテゴリ遷移確率ｐ（ｃｄ|ｃｓ）は以下（１）式に従って求める。
【００３４】
【数１】
0006543180.tif 000002
【００３５】
ここで、αはスムージングパラメータであり、具体的に、α＝１．０などと設定する。
【００３６】
目的地メッシュ予測学習部３４は、セグメンテーション前処理部３０により得られたメッシュ遷移系列データに基づいて、出発地となる地域メッシュから現在地となる地域メッシュまでのメッシュ遷移系列データから、推定対象の地域メッシュが目的地となる確率を予測するための推定器を学習する。具体的には、メッシュ遷移系列データから、出発地となる地域メッシュから現在地となる地域メッシュまでのメッシュ遷移系列Ｔが与えられた際に、推定対象の地域メッシュｎｄを目的地として訪問する確率Ｐ（ｎｄ｜Ｔ）を推定する推定器を学習する。推定器の学習には、非特許文献１などで提案されている手法が利用可能である。
【００３７】
メッシュ内目的地予測学習部３６は、訪問地系列集合とスポットＤＢ（図示省略）とに基づいて、地域メッシュｎｄの各々について、地域メッシュｎｄ内における訪問スポットｚｋの訪問確率ｐ（ｚｋ｜ｎｄ）を以下（２）式に従って学習する。
【００３８】
【数２】
0006543180.tif 000003
【００３９】
ここで、βはスムージングパラメータであり、具体的に、β＝１．０などと設定する。地域メッシュｎｄに含まれるスポット数は、スポットＤＢから、地域メッシュｎｄを検索クエリとした際の検索結果の行数とする。
【００４０】
時間帯別メッシュ分布学習部３８は、セグメンテーション前処理部３０により得られたメッシュ遷移系列データに基づいて、以下（３）式に従って、時間帯ｔ毎に、時間帯ｔにおいて各地域メッシュｎｄを訪問する確率を表す確率分布ｐ（ｎｄ｜ｔ）を学習する。時間帯ｔは、例えば「平日・午前」、「平日・午後」、「休日・午前」、「休日・午後」などと指定する。
【００４１】
【数３】
0006543180.tif 000004
【００４２】
次に、予測実施部２２の各部の詳細な処理について説明する。予測実施部２２は、入力移動軌跡と、入力移動軌跡における出発地となる訪問スポット（以下、出発訪問スポットと称する）と、目的地予測学習部２１で学習された予測モデルとを受け付けて各部の処理を行う。
【００４３】
メッシュ変換部４０は、入力移動軌跡に含まれる緯度及び経度の組の各々を、緯度経度空間を分割して得られる分割領域である地域メッシュに変換することにより、入力移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換する。ここでは、上記セグメンテーション前処理部３０の第５の処理と同様の手法により、入力移動軌跡Ｔをメッシュ遷移系列データに変換する。
【００４４】
目的地メッシュ予測部４２は、メッシュ変換部４０により出力されたメッシュ遷移系列データと、目的地予測学習部２１で学習された、地域メッシュが目的地となる確率を予測するための推定器とに基づいて、目的地の候補が含まれる地域メッシュの集合である目的地メッシュ候補集合を出力する。例えば、推定器を用いて、入力軌跡Ｔが与えられた時の目的地メッシュｎｄの確率p（ｎｄ|Ｔ）を求め、求めた確率が上位Ｋ個の目的地メッシュを目的地メッシュ候補集合Ｎｄｅｓｔとする。パラメータＫは具体的には１００などとする。
【００４５】
メッシュ内目的地予測部４４は、目的地メッシュ予測部４２から出力された目的地メッシュ候補集合Ｎｄｅｓｔに含まれる地域メッシュｎｄに対して、目的地予測学習部２１のメッシュ内目的地予測学習部３６によって学習された地域メッシュ内における訪問スポットｚｋの訪問確率ｐ（ｚｋ｜ｎｄ）に基づいて、目的地メッシュ候補集合Ｎｄｅｓｔに含まれる地域メッシュｎｄ内における訪問スポットｚｋの訪問確率ｐ（ｚｋ｜ｎｄ）を推定する。
【００４６】
スポットデータベース４６は、図５に示すように、訪問スポットのスポット名、緯度、経度、及び訪問スポットが所属するカテゴリからなる各レコードによって構成されている。例えば、出発訪問スポットを入力として、スポットデータベース４６を検索することにより、出発訪問スポットに対応するカテゴリが出力される。
【００４７】
出発スポットカテゴリ取得部４８は、出発訪問スポットを用いてスポットデータベース４６を検索し、入力移動軌跡における出発訪問スポットが所属する出発スポットカテゴリを取得する。
【００４８】
目的地カテゴリ予測部５０は、出発スポットカテゴリ取得部により取得された出発スポットカテゴリと、目的地予測学習部２１の目的地カテゴリ予測学習部３２によって学習されたカテゴリ間の遷移確率であるカテゴリ遷移確率とに基づいて、ユーザの目的地となる訪問スポットのカテゴリである目的地カテゴリを推定する。具体的には、すべての訪問スポットのカテゴリｃｄの各々について、カテゴリ遷移確率を用いて、出発スポットカテゴリｃｓから当該カテゴリｃｄに遷移する確率ｐ（ｃｄ｜ｃｓ）を求め、目的地カテゴリの推定結果として出力する。
【００４９】
時間帯別メッシュ分布推定部５２は、入力移動軌跡における現在地の測位時間と、目的地予測学習部２１の時間帯別メッシュ分布学習部３８によって学習された時間帯において各地域メッシュを訪問する確率を表す確率分布とに基づいて、現在地の測位時間が属する時間帯ｔｃにユーザが各地域メッシュｎｄを訪問する確率を表すメッシュ訪問分布ｐ（ｎｄ｜ｔｃ）を推定する。
【００５０】
確率統合部５４は、目的地メッシュ予測部４２により推定された目的地メッシュ候補集合と、メッシュ内目的地予測部４４により地域メッシュの各々に対して推定された地域メッシュ内における訪問スポットの訪問確率と、目的地カテゴリ予測部５０により推定された目的地カテゴリの推定結果と、時間帯別メッシュ分布推定部５２により推定されたメッシュ訪問分布とを統合した結果に基づいて、目的地メッシュ候補集合に含まれる地域メッシュ内の訪問スポットのうち、ユーザの目的地となる訪問スポットを推定する。具体的には、目的地メッシュ候補集合Ｎｄｅｓｔに含まれる地域メッシュｎｄ内の訪問スポットｚｄから、下記（４）式で計算される確率が最大になる訪問スポットｚｄを目的地として出力する。
【００５１】
【数４】
0006543180.tif 000005
【００５２】
または、以下（５）式で計算される確率が最大になる訪問スポットｚｄを目的地として出力するようにしても良い。
【００５３】
【数５】
0006543180.tif 000006
【００５４】
ここで、γには０．７５などの値を設定する。
【００５５】
＜本発明の実施の形態に係る目的地予測装置の作用＞
【００５６】
次に、本発明の実施の形態に係る目的地予測装置１００の作用について説明する。
【００５７】
まず、目的地予測学習処理ルーチンについて説明する。目的地予測学習部２１が、移動軌跡集合と、訪問地系列集合とを受け付けると、目的地予測装置１００は、図４に示す目的地予測学習処理ルーチンを実行する。
【００５８】
ステップＳ１００では、受け付けた移動軌跡集合の移動軌跡の各々から、ユーザが一定以上滞留した点である滞留点を抽出する。
【００５９】
ステップＳ１０２では、ステップＳ１００で抽出された滞留点と、受け付けた訪問地系列集合とから、抽出された滞留点の各々について、当該滞留点における滞留開始時刻から滞留終了時刻までの間に、ユーザが訪問した訪問スポットの訪問時刻が含まれる場合に、滞留点と訪問スポットとを対応付けることにより、当該滞留点と訪問スポットと訪問スポットのカテゴリとを対応付けた訪問地カテゴリ学習データを生成する。
【００６０】
ステップＳ１０４では、受け付けた移動軌跡集合の移動軌跡の各々について、当該移動軌跡を、滞留点における滞留開始時刻から滞留終了時刻までの間に含まれない、分割移動軌跡に分割して、分割移動軌跡集合を生成する。
【００６１】
ステップＳ１０６では、ステップＳ１０４で生成された分割移動軌跡集合に含まれる分割移動軌跡の各々について、ステップＳ１０２で生成された訪問地カテゴリ学習データに含まれる訪問スポットのカテゴリを用いて、当該分割移動軌跡の前後の訪問スポットのカテゴリを表すカテゴリ遷移データを生成する。
【００６２】
ステップＳ１０８では、ステップＳ１０６で生成されたカテゴリ遷移データに基づいて、上記（１）式に従って、カテゴリ間の遷移確率であるカテゴリ遷移確率を、カテゴリのペアの各々について学習する。
【００６３】
ステップＳ１１０では、ステップＳ１０４で生成された分割移動軌跡集合に含まれる分割移動軌跡の各々について、当該分割移動軌跡に含まれる緯度及び経度の組の各々を、地域メッシュに変換することにより、当該分割移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換する。
【００６４】
ステップＳ１１２では、ステップＳ１１０で得られたメッシュ遷移系列データに基づいて、推定対象の地域メッシュが目的地となる確率を予測するための推定器を学習する。
【００６５】
ステップＳ１１４では、受け付けた訪問地系列集合に基づいて、地域メッシュｎｄの各々について、地域メッシュｎｄ内における訪問スポットｚｋの訪問確率ｐ（ｚｋ｜ｎｄ）を上記（２）式に従って学習する。
【００６６】
ステップＳ１１６では、ステップＳ１１０で得られたメッシュ遷移系列データに基づいて、上記（３）式に従って、時間帯ｔ毎に、時間帯ｔにおいて各地域メッシュｎｄを訪問する確率を表す確率分布ｐ（ｎｄ｜ｔ）を学習する。
【００６７】
次に、予測実施処理ルーチンについて説明する。予測実施部２２が、入力移動軌跡と、出発訪問スポットとを受け付けると、目的地予測装置１００は、図５に示す予測実施処理ルーチンを実行する。また、目的地予測学習部２１で予め学習された予測モデルが与えられているものとする。
【００６８】
ステップＳ２００では、受け付けた入力移動軌跡に含まれる緯度及び経度の組の各々を、地域メッシュに変換することにより、入力移動軌跡を、地域メッシュ及び測位時間の組の系列であるメッシュ遷移系列データに変換する。
【００６９】
ステップＳ２０２では、ステップＳ１００で出力されたメッシュ遷移系列データと、目的地予測学習部２１で学習された、地域メッシュが目的地となる確率を予測するための推定器とに基づいて、目的地の候補が含まれる地域メッシュの集合である目的地メッシュ候補集合Ｎｄｅｓｔを出力する。
【００７０】
ステップＳ２０４では、ステップＳ２０２で出力された目的地メッシュ候補集合Ｎｄｅｓｔに含まれる地域メッシュｎｄに対して、目的地予測学習部２１で学習された地域メッシュ内における訪問スポットｚｋの訪問確率ｐ（ｚｋ｜ｎｄ）に基づいて、目的地メッシュ候補集合Ｎｄｅｓｔに含まれる地域メッシュｎｄ内における訪問スポットｚｋの訪問確率ｐ（ｚｋ｜ｎｄ）を推定する。
【００７１】
ステップＳ２０６では、受け付けた出発訪問スポットを用いてスポットデータベース４６を検索し、入力移動軌跡における出発地スポットが所属する出発スポットカテゴリを取得する。
【００７２】
ステップＳ２０８では、ステップＳ２０６で取得された出発スポットカテゴリと、目的地予測学習部２１で学習されたカテゴリ間の遷移確率であるカテゴリ遷移確率とに基づいて、ユーザの目的地となる訪問スポットのカテゴリである目的地カテゴリを推定する。
【００７３】
ステップＳ２１０では、受け付けた入力移動軌跡における現在地の測位時間と、目的地予測学習部２１で学習された時間帯において各地域メッシュを訪問する確率を表す確率分布とに基づいて、現在地の測位時間が属する時間帯ｔｃにユーザが各地域メッシュｎｄを訪問する確率を表すメッシュ訪問分布ｐ（ｎｄ｜ｔｃ）を推定する。
【００７４】
ステップＳ２１２では、ステップＳ２０２で推定された目的地メッシュ候補集合と、ステップＳ２０４で地域メッシュの各々に対して推定された地域メッシュ内における訪問スポットの訪問確率と、ステップＳ２０８で推定された目的地カテゴリの推定結果と、ステップＳ２１０で推定されたメッシュ訪問分布とを統合した結果に基づいて、目的地メッシュ候補集合Ｎｄｅｓｔに含まれる地域メッシュｎｄ内の訪問スポットｚｄから、上記（４）式で計算される確率が最大になる訪問スポットｚｄを目的地として予測し、出力部６０に予測結果を出力して処理を終了する。
【００７５】
以上説明したように、本発明の実施の形態に係る目的地予測装置によれば、移動軌跡集合と、訪問地系列集合とに基づいて、ユーザの移動軌跡から目的地を予測するための予測モデルを学習し、入力移動軌跡と、出発地となる訪問スポットと、学習された予測モデルとに基づいて、ユーザの目的地となる訪問スポットを予測することにより、ユーザの目的地となる訪問スポットを、精度よく予測することができる。
【００７６】
また、本発明の実施の形態に係る手法では、訪問スポットのカテゴリを利用するので、未訪問の目的地についても、予測を実施できる。
【００７７】
また、本発明の実施の形態に係る手法は、計測機器によって得られたユーザの位置情報の測位結果と測位時間の系列である移動軌跡データから、ユーザが目指している場所である目的地を予測可能な手法であり、情報推薦、生活支援などに利用可能である。
【００７８】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７９】
例えば、図１に示す構成要素の動作をプログラムとして構築し、目的地抽出装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００８０】
また、構築されたプログラムをハードディスクやフレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【符号の説明】
【００８１】
２０   演算部
２１   目的地予測学習部
２２   予測実施部
３０   セグメンテーション前処理部
３２   目的地カテゴリ予測学習部
３４   目的地メッシュ予測学習部
３６   メッシュ内目的地予測学習部
３８   時間帯別メッシュ分布学習部
４０   メッシュ変換部
４２   目的地メッシュ予測部
４４   メッシュ内目的地予測部
４６   スポットデータベース
４８   出発スポットカテゴリ取得部
５０   目的地カテゴリ予測部
５２   時間帯別メッシュ分布推定部
５４   確率統合部
６０   出力部
１００ 目的地予測装置
【図１】
0006543180.tif 000007
【図２】
0006543180.tif 000008
【図３】
0006543180.tif 000009
【図４】
0006543180.tif 000010
【図５】
0006543180.tif 000011