(57)【特許請求の範囲】
【請求項１】
携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索する装置であって、
携帯端末毎に、通信に係る日時刻及び基地局位置情報を対応付けた複数の通信記録を含む通信履歴を蓄積した位置情報履歴蓄積手段と、
携帯端末毎に、当該通信履歴における第１の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「短時間滞留地」を決定し、該第１の時間窓よりも長い時間幅を有する第２の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在地」を決定し、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する時系列データ生成手段と、
当該滞在滞留時系列データから所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、当該「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する短時間滞留地間遷移モデル構築手段と、
当該滞在滞留時系列データから所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、当該「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する滞在地・短時間滞留地間遷移モデル構築手段と、
当該滞在滞留時系列データについて、構築された当該「短時間滞留地」間遷移モデル及び当該「滞在地・短時間滞留地」間遷移モデルに基づいて、時系列において欠損している「短時間滞留地」を補間する短時間滞留地補間手段と、
所定の携帯端末に係る当該補間処理後の滞在滞留時系列データと、他の携帯端末に係る当該補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、前記所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索するユーザ検索手段と
を有することを特徴とする装置。
【請求項２】
前記時系列データ生成手段は、
当該通信履歴を、当該第１の時間窓と当該第２の時間窓とのそれぞれで分割する時間窓分割手段と、
当該第１の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布に基づいて「滞留」か否かを判定して、「滞留」と判定された第１の時間窓における位置の確率分布に基づいて「滞留地」を決定し、「滞留」と判定された所定数以下の連続する第１の時間窓に対し、当該滞留の所定時間以上前又は後に異なる「滞留地」を有する第１の時間窓が存在しており、且つ該連続する第１の時間窓の「滞留地」と該異なる「滞留地」とが所定距離以上離隔している場合、該連続する第１の時間窓を「短時間滞留」と判定する第１の短時間滞留判定手段と、
複数の携帯端末に係る「短時間滞留」と判定された第１の時間窓の「滞留地」の確率分布に基づいて「短時間滞留地」を決定し、「短時間滞留地」毎に当該基地局位置情報を対応付けた基地局リストを生成する基地局情報収集手段と、
当該通信履歴について、当該基地局リストに含まれる基地局が存在する場合、該基地局の基地局位置情報に、当該基地局リストで対応している「短時間滞留地」を対応付けた短時間滞留地履歴を生成する第２の短時間滞留判定手段と、
当該第２の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在」か否かを判定し、「滞在」と判定された第２の時間窓における位置の確率分布に基づいて「滞在地」を決定する滞在判定手段と、
携帯端末毎に、生成された当該短時間滞留地履歴に基づいて、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する滞在滞留時系列データ生成手段と
を有することを特徴とする請求項１に記載の装置。
【請求項３】
前記短時間滞留地補間手段は、時系列において欠損している「短時間滞留地」の候補が複数存在する場合、当該候補を間に含んだ遷移パターンの出現確率に基づく尤度が最も高くなるところの当該候補で補間することを特徴とする請求項１又は２に記載の装置。
【請求項４】
前記短時間滞留地補間手段は、当該滞在滞留時系列データにおいて隣接する「短時間滞留地」同士又は隣接する「滞在地」及び「短時間滞留地」が所定時間以上離隔している場合、当該「短時間滞留地」同士の間又は当該「滞在地」及び「短時間滞留地」の間に、欠損している「短時間滞留地」が存在すると推定することを特徴とする請求項１から３のいずれか１項に記載の装置。
【請求項５】
前記ユーザ検索手段は、２つの携帯端末間の類似度を（最長一致部分系列長）／（当該２つの携帯端末に係る補間処理後の滞在滞留時系列データのうちの長いほうの系列長）として、当該類似度が所定閾値以上の携帯端末を検索することを特徴とする請求項１から４のいずれか１項に記載の装置。
【請求項６】
前記ユーザ検索手段は、指定された検索対象の時間区間のうち、互いに所定時間以上離隔した「滞在地」に対応する時間区間の間となる時間区間について最長一致部分系列長を調査することを特徴とする請求項１から５のいずれか１項に記載の装置。
【請求項７】
前記基地局情報収集手段は、「短時間滞留地」毎に、当該基地局の基地局位置情報と、該基地局に対する接続確率とを対応付けた基地局リストを生成し、
前記第２の短時間滞留判定手段は、当該接続確率が所定値以上である基地局のみを選択して当該短時間滞留地履歴を生成する
ことを特徴とする請求項２に記載の装置。
【請求項８】
前記時間窓分割手段は、所定地域範囲における短時間滞留の時間長の平均値、最頻値又はＮ分位点（０≦Ｎ≦１）値を、第１の時間窓の時間幅に設定することを特徴とする請求項２又は７に記載の装置。
【請求項９】
広域無線通信網に接続された請求項１から８のいずれか１項に記載の装置である通信設備装置であって、
基地局識別子及び基地局位置情報を対応付けて記憶する基地局位置情報管理手段と、
携帯端末を配下に接続させる基地局から、携帯端末毎に通信に係る日時刻と当該基地局の基地局識別子とを対応付けた通信記録を収集する通信履歴収集手段とを更に有し、
前記位置情報履歴蓄積手段は、当該通信記録について、携帯端末毎に基地局識別子に対応する基地局位置情報を更に対応付けて当該通信履歴を生成する
ことを特徴とする通信設備装置。
【請求項１０】
装置に搭載されたコンピュータを、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索するように機能させるプログラムであって、
携帯端末毎に、通信に係る日時刻及び基地局位置情報を対応付けた複数の通信記録を含む通信履歴を蓄積した位置情報履歴蓄積手段と、
携帯端末毎に、当該通信履歴における第１の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「短時間滞留地」を決定し、該第１の時間窓よりも長い時間幅を有する第２の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在地」を決定し、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する時系列データ生成手段と、
当該滞在滞留時系列データから所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、当該「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する短時間滞留地間遷移モデル構築手段と、
当該滞在滞留時系列データから所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、当該「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する滞在地・短時間滞留地間遷移モデル構築手段と、
当該滞在滞留時系列データについて、構築された当該「短時間滞留地」間遷移モデル及び当該「滞在地・短時間滞留地」間遷移モデルに基づいて、時系列において欠損している「短時間滞留地」を補間する短時間滞留地補間手段と、
所定の携帯端末に係る当該補間処理後の滞在滞留時系列データと、他の携帯端末に係る当該補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、前記所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索するユーザ検索手段と
してコンピュータを機能させることを特徴とするプログラム。
【請求項１１】
装置の有するコンピュータにおけるソフトウェアの情報処理によって、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索する方法であって、
前記装置は、携帯端末毎に、通信に係る日時刻及び基地局位置情報を対応付けた複数の通信記録を含む通信履歴を蓄積した位置情報履歴蓄積手段を有し、前記方法は、
携帯端末毎に、当該通信履歴における第１の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「短時間滞留地」を決定し、該第１の時間窓よりも長い時間幅を有する第２の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在地」を決定し、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する第１のステップと、
当該滞在滞留時系列データから所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、当該「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する第２のステップと、
当該滞在滞留時系列データから所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、当該「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する第３のステップと、
当該滞在滞留時系列データについて、構築された当該「短時間滞留地」間遷移モデル及び当該「滞在地・短時間滞留地」間遷移モデルに基づいて、時系列において欠損している「短時間滞留地」を補間する第４のステップと、
所定の携帯端末に係る当該補間処理後の滞在滞留時系列データと、他の携帯端末に係る当該補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、前記所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索する第５のステップと
を有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、携帯端末を所持したユーザの滞在及び移動に関わる情報を推定する技術に関する。
【背景技術】
【０００２】
近年、携帯電話機に代表される携帯端末の多くは、ＧＰＳ(Global Positioning System)といった測位機能を備えている。これにより、ユーザは、測位を通して現在位置情報を取得できるとともに、測位結果をネットワーク経由でサーバに送信することによって、位置に応じた様々なサービス情報を受信可能となる。
【０００３】
しかしながら、ユーザの位置情報の取得のために、携帯端末においてＧＰＳ機能及びそのアプリケーションを常時又は定期的に起動させると、携帯端末の電池の消耗が早まるのみならず、携帯端末からのパケットの送出量が増大してしまう。また、それ故に、ユーザの位置情報に基づくサービスを普及させることも困難となる。
【０００４】
そのため、通信事業者側としては、携帯端末で取得された位置情報ではなく、その携帯端末を配下とする基地局の位置情報によって、携帯端末を所持したユーザの滞在に関する位置及び時間区間を推定できることが好ましい。この場合、携帯端末は常時又は定期的にＧＰＳ機能を起動させる必要もない。
【０００５】
例えば、特許文献１には、携帯端末等の移動体を配下とする基地局の位置情報の履歴を用いて、移動体の動線を分析する技術が開示されている。この技術によれば、２つの移動体における滞在地の一致と滞在時間帯の重複とに基づいて、移動体同士の接触の有無が評価される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−８５２５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１に記載されたような従来技術では、１つの携帯端末と他の携帯端末とが同行しているか、又は互いに近くを通行しているかを検知することは困難である。例えば、携帯端末を所持したユーザが電車や自動車等の移動手段によって移動している場合、他の携帯端末を所持したユーザがこのユーザと所定の時間区間において同じ移動手段に乗車しているか否か、または、他のユーザの乗車した移動手段がこのユーザの乗車した移動手段の近くを移動しているか否かを推定することは困難である。
【０００８】
このような同行又は近接位置の通行を検知し推定するためには、各ユーザの移動経路を導出して適切に比較することが重要になる。
【０００９】
そこで、本発明は、携帯端末の測位機能に頼ることなく、通信事業者設備によって取得可能な基地局位置情報を用いて、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索することができる装置、プログラム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明によれば、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索する装置であって、
携帯端末毎に、通信に係る日時刻及び基地局位置情報を対応付けた複数の通信記録を含む通信履歴を蓄積した位置情報履歴蓄積手段と、
携帯端末毎に、通信履歴における第１の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「短時間滞留地」を決定し、この第１の時間窓よりも長い時間幅を有する第２の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在地」を決定し、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する時系列データ生成手段と、
滞在滞留時系列データから所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する短時間滞留地間遷移モデル構築手段と、
滞在滞留時系列データから所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する滞在地・短時間滞留地間遷移モデル構築手段と、
滞在滞留時系列データについて、構築された「短時間滞留地」間遷移モデル及び「滞在地・短時間滞留地」間遷移モデルに基づいて、時系列において欠損している「短時間滞留地」を補間する短時間滞留地補間手段と、
所定の携帯端末に係る補間処理後の滞在滞留時系列データと、他の携帯端末に係る補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索するユーザ検索手段と
を有する装置が提供される。
【００１１】
この本発明の装置における時系列データ生成手段は、
通信履歴を、第１の時間窓と第２の時間窓とのそれぞれで分割する時間窓分割手段と、
第１の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布に基づいて「滞留」か否かを判定して、「滞留」と判定された第１の時間窓における位置の確率分布に基づいて「滞留地」を決定し、「滞留」と判定された所定数以下の連続する第１の時間窓に対し、滞留の所定時間以上前又は後に異なる「滞留地」を有する第１の時間窓が存在しており、且つ連続する第１の時間窓の「滞留地」と異なる「滞留地」とが所定距離以上離隔している場合、この連続する第１の時間窓を「短時間滞留」と判定する第１の短時間滞留判定手段と、
複数の携帯端末に係る「短時間滞留」と判定された第１の時間窓の「滞留地」の確率分布に基づいて「短時間滞留地」を決定し、「短時間滞留地」毎に基地局位置情報を対応付けた基地局リストを生成する基地局情報収集手段と、
通信履歴について、基地局リストに含まれる基地局が存在する場合、この基地局の基地局位置情報に、基地局リストで対応している「短時間滞留地」を対応付けた短時間滞留地履歴を生成する第２の短時間滞留判定手段と、
第２の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在」か否かを判定し、「滞在」と判定された第２の時間窓における位置の確率分布に基づいて「滞在地」を決定する滞在判定手段と、
携帯端末毎に、生成された短時間滞留地履歴に基づいて、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する滞在滞留時系列データ生成手段と
を有することも好ましい。
【００１２】
また、上述した実施形態では、基地局情報収集手段は、「短時間滞留地」毎に、基地局の基地局位置情報と、この基地局に対する接続確率とを対応付けた基地局リストを生成し、第２の短時間滞留判定手段は、接続確率が所定値以上である基地局のみを選択して短時間滞留地履歴を生成することも好ましい。さらに、時間窓分割手段は、所定地域範囲における短時間滞留の時間長の平均値、最頻値又はＮ分位点（０≦Ｎ≦１）値を、第１の時間窓の時間幅に設定することも好ましい。
【００１３】
また、本発明の装置における短時間滞留地補間手段は、時系列において欠損している「短時間滞留地」の候補が複数存在する場合、１つの候補を間に含んだ遷移パターンの出現確率に基づく尤度が最も高くなるところの当該候補で補間することも好ましい。
【００１４】
さらに、この短時間滞留地補間手段は、滞在滞留時系列データにおいて隣接する「短時間滞留地」同士又は隣接する「滞在地」及び「短時間滞留地」が所定時間以上離隔している場合、「短時間滞留地」同士の間又は「滞在地」及び「短時間滞留地」の間に、欠損している「短時間滞留地」が存在すると推定することも好ましい。
【００１５】
また、本発明の装置におけるユーザ検索手段は、２つの携帯端末間の類似度を（最長一致部分系列長）／（これらの２つの携帯端末に係る補間処理後の滞在滞留時系列データのうちの長いほうの系列長）として、類似度が所定閾値以上の携帯端末を検索することも好ましい。さらに、ユーザ検索手段は、指定された検索対象の時間区間のうち、互いに所定時間以上離隔した「滞在地」に対応する時間区間の間となる時間区間について最長一致部分系列長を調査することも好ましい。
【００１６】
また、本発明によれば、広域無線通信網に接続された以上に述べた装置である通信設備装置であって、
基地局識別子及び基地局位置情報を対応付けて記憶する基地局位置情報管理手段と、
携帯端末を配下に接続させる基地局から、携帯端末毎に通信に係る日時刻とこの基地局の基地局識別子とを対応付けた通信記録を収集する通信履歴収集手段とを更に有し、
位置情報履歴蓄積手段は、通信記録について、携帯端末毎に基地局識別子に対応する基地局位置情報を更に対応付けて通信履歴を生成する
ことを特徴とする通信設備装置が提供される。
【００１７】
本発明によれば、さらに、装置に搭載されたコンピュータを、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索するように機能させるプログラムであって、
携帯端末毎に、通信に係る日時刻及び基地局位置情報を対応付けた複数の通信記録を含む通信履歴を蓄積した位置情報履歴蓄積手段と、
携帯端末毎に、通信履歴における第１の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「短時間滞留地」を決定し、この第１の時間窓よりも長い時間幅を有する第２の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在地」を決定し、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する時系列データ生成手段と、
滞在滞留時系列データから所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する短時間滞留地間遷移モデル構築手段と、
滞在滞留時系列データから所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する滞在地・短時間滞留地間遷移モデル構築手段と、
滞在滞留時系列データについて、構築された「短時間滞留地」間遷移モデル及び「滞在地・短時間滞留地」間遷移モデルに基づいて、時系列において欠損している「短時間滞留地」を補間する短時間滞留地補間手段と、
所定の携帯端末に係る補間処理後の滞在滞留時系列データと、他の携帯端末に係る補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索するユーザ検索手段と
してコンピュータを機能させるプログラムが提供される。
【００１８】
本発明によれば、さらにまた、装置の有するコンピュータにおけるソフトウェアの情報処理によって、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索する方法であって、
上記装置は、携帯端末毎に、通信に係る日時刻及び基地局位置情報を対応付けた複数の通信記録を含む通信履歴を蓄積した位置情報履歴蓄積手段を有し、上記方法は、
携帯端末毎に、通信履歴における第１の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「短時間滞留地」を決定し、この第１の時間窓よりも長い時間幅を有する第２の時間窓での複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在地」を決定し、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する第１のステップと、
滞在滞留時系列データから所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する第２のステップと、
滞在滞留時系列データから所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する第３のステップと、
滞在滞留時系列データについて、構築された「短時間滞留地」間遷移モデル及び「滞在地・短時間滞留地」間遷移モデルに基づいて、時系列において欠損している「短時間滞留地」を補間する第４のステップと、
所定の携帯端末に係る補間処理後の滞在滞留時系列データと、他の携帯端末に係る補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索する第５のステップと
を有する方法が提供される。
【発明の効果】
【００１９】
本発明の装置、プログラム及び方法によれば、携帯端末の測位機能に頼ることなく、通信事業者設備によって取得可能な基地局位置情報を用いて、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索することができる。
【図面の簡単な説明】
【００２０】
【図１】実空間での携帯端末の滞在及び移動を示す概略図である。
【図２】本発明による類似移動経路ユーザ検索装置の機能構成図である。
【図３】基地局位置情報の表である。
【図４】通信履歴の表である。
【図５】通信記録に基地局位置情報を対応付けた通信履歴の表である。
【図６】第１の時間窓の開始時刻及び終了時刻を示す表である。
【図７】携帯端末毎に、図５の各行（通信記録）を図６の第１の時間窓毎に分類した表である。
【図８】第２の時間窓の開始時刻及び終了時刻を示す表である。
【図９】携帯端末毎に、図５の各行（通信記録）を図８の第２の時間窓毎に分類した表である。
【図１０】単峰性を有するか否かを判定するためのフローチャートである。
【図１１】「滞在」と判定された第２の時間窓及び対応する代表点位置情報を示す表である。
【図１２】図１１に示した第２の時間窓毎の代表点位置情報に基づいて算出された「滞在地クラスタ」の代表点位置情報を示す表である。
【図１３】「滞留」と判定された第１の時間窓及び対応する代表点位置情報を示す表である。
【図１４】図１４は、「短時間滞留」と判定された第１の時間窓及び対応する「滞留地」代表点を示す表である。
【図１５】複数の携帯端末２から「滞留」に係る情報を収集する様子を示す概略図、及び「短時間滞留地」における滞留地代表点の算出結果を示す表である。
【図１６】短時間滞留地の基地局リストを示す表である。
【図１７】第２の短時間滞留判定の結果を示す表である。
【図１８】携帯端末00001及び00002が「滞在」及び「短時間滞留」を行いながら進行する様子を示す概略図、及び生成された滞在滞留時系列データを示す表である。
【図１９】「短時間滞留地」間遷移モデルを示す表である。
【図２０】「滞在地・短時間滞留地」間遷移モデルを示す表である。
【図２１】短時間滞留地Ａ〜Ｇについての短時間滞留地間遷移モデルを示す表である。
【図２２】滞在地α及びβ並びに短時間滞留地Ａ〜Ｇについての滞在地・短時間滞留地間遷移モデルを示す表である。
【図２３】「短時間滞留地」補間の実施例を説明するための表である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施形態について、図面を用いて詳細に説明する。
【００２２】
図１は、実空間での携帯端末の滞在及び移動を示す概略図である。
【００２３】
図１によれば、ユーザに所持された携帯端末（例えば携帯電話機やスマートフォン）２は、どの位置にあってもいずれかの基地局の配下にあり、通常、当該基地局と無線通信し続けることができる。このユーザにとっては、自宅及び職場が「滞在地」となる。また、自宅、職場以外の場所であるＡ駅、Ｂ駅、Ｃ駅及びＤ駅が、電車乗降のための又は電車の停車による「短時間滞留地」となる。
【００２４】
多数の基地局３を統合する通信事業者設備（図２）は、携帯端末２毎に、空間的粒度が粗く且つ時間間隔が一定でない基地局位置情報を常時収集することができる。ここで、「空間的粒度が粗く」とは、位置情報同士の地理的な距離が比較的長いことを意味する。また、「時間間隔が一定でない」とは、位置情報の取得時間間隔が通信タイミングに依存して比較的ばらついていることを意味する。
【００２５】
広域無線通信網（携帯電話網）に接続された基地局３は、その配下に位置する携帯端末２と通信した際の日時刻（例えば通信を開始した日時刻）を通信履歴として取得する。通信履歴は、通話、メールの送受信や、Ｗｅｂページの閲覧の際に取得される。さらには、携帯端末２にインストールされたアプリケーションとサーバとの間の通信や、アプリケーション又はコンテンツのダウンロードやアップロード等の際にも取得される。
【００２６】
図２は、本発明による類似移動経路ユーザ検索装置の機能構成図である。
【００２７】
本発明による装置１は、予め蓄積された通信履歴を用いて、携帯端末２を所持したユーザの移動経路に類似した移動経路をとるユーザを検索することができる。例えば、携帯端末を所持したユーザが電車や自動車等の移動手段によって移動している際、他の携帯端末を所持したユーザがこのユーザと所定の時間区間において同じ移動手段に乗車しているか否かを推定し、類似した移動経路をとるユーザを検索することができる。または、他のユーザの乗車した移動手段がこのユーザの乗車した移動手段の近くを移動しているか否かを推定してユーザを検索することもできる。
【００２８】
このように類似移動経路をとるユーザを推定することによって、例えば、携帯端末を所持しており移動経路が類似するユーザ群に、その移動経路に応じた広告や、クーポン等のオンライン情報を配信することが可能となる。尚、装置１は、広域無線通信網（携帯電話網）に設置され、基地局３から通信履歴を適宜収集する通信設備装置であってもよい。
【００２９】
図２によれば、類似移動経路ユーザ検索用の装置１は、時間窓分割部１２１と、滞在判定部１２２と、第１の短時間滞留判定部１２３と、基地局情報収集部１２４と、第２の短時間滞留判定部１２５と、滞在滞留時系列データ生成部１２６と、短時間滞留地間遷移モデル構築部１２７と、滞在地・短時間滞留地間遷移モデル構築部１２８とを有する。これらの機能構成部は、時系列データ生成部１２として機能する。装置１は、また、短時間滞留地補間部１３１と、ユーザ検索部１３２とを有する。
【００３０】
上述した機能構成部は、装置に搭載されたコンピュータを機能させるプログラムを実行することによって実現される。また、図２によれは、各機能構成部を用いた処理の流れは、類似移動経路をとるユーザを検索する方法としても理解される。
【００３１】
さらに、装置１は、広域無線通信網（携帯電話網）に設置された通信設備装置である場合、通信履歴を取得するために、広域通信網に接続する通信インタフェース部１０と、通信履歴収集部１１１と、基地局位置情報管理部１１２と、位置情報履歴蓄積部１１３とを更に有する。ここで、通信インタフェース部１０は、類似移動経路ユーザ検索のためのクエリを受信し、検索結果を送信するインタフェースとしても機能する。以下、装置１は通信設備装置として説明する。
【００３２】
［基地局位置情報管理部１１２］
基地局位置情報管理部１１２（図２）は、基地局識別子と基地局位置情報とを対応付けて記憶する。
【００３３】
図３は、基地局位置情報の表である。基地局識別子毎に、緯度・経度の基地局位置情報が対応付けられている。図３によれば、基地局0001は、緯度が35.845度であって経度が139.502度の位置に設置されていることが理解される。また、基地局0003は、緯度35.845及び経度139.504の位置に設置されていることが理解される。尚、このような基地局位置情報は、基地局位置情報管理部１１２内に予め蓄積したものであってもよいし、通信インタフェース部１０を介して各基地局３から適宜取得するものであってもよい。
【００３４】
［通信履歴収集部１１１］
通信履歴収集部１１１（図２）は、基地局３から、当該基地局３の配下にある携帯端末２毎に日時刻及び基地局識別子といった通信記録（通信履歴）を収集する。
【００３５】
図４は、通信履歴の表である。通信履歴は、基地局３が携帯端末２からの通信を受け付けた際の一連の通信記録（ログ）である。各通信記録では、携帯端末２の「端末識別子」（アドレス、電話番号、識別番号等）毎に、「日時刻」及び「基地局識別子」が対応付けられている。
通信記録（端末識別子、日時刻、基地局識別子）
図４の通信履歴によれば、携帯端末00001は、２０１０年６月１５日１７：５４：５０に基地局0003と通信している。また、携帯端末00001は、２０１０年６月１５日１７：５７：００には基地局0001と通信している。
【００３６】
［位置情報履歴生成部１１３］
位置情報履歴生成部１１３（図２）は、基地局位置情報管理部１１１を用いて、通信記録（ログ）毎に、基地局識別子に対応する基地局位置情報を更に対応付けた通信履歴を生成し蓄積する。
【００３７】
図５は、通信記録に基地局位置情報を対応付けた通信履歴の表である。図５の表は、図４の表の基地局識別子の部分を、図３の基地局の緯度・経度情報で置き換えたものである。図５の通信履歴によれば、携帯端末00001は、２０１０年６月１５日１７：５４：５０に、緯度35.845及び経度139.504の基地局と通信したことが理解される。また、携帯端末00001は、２０１０年６月１５日１７：５７：００に、緯度35.845及び経度139.502の基地局と通信したことが理解される。
【００３８】
［時間窓分割部１２１］
時間窓分割部１２１（図２）は、位置情報履歴生成部１１３から出力された通信履歴を所定の時間窓（時間区間）で分割する。具体的には、通信履歴を構成する複数の通信記録を、日時刻が所定の時間窓に属するもの同士を集めて区分する。時間窓は、時間幅Ｔ及びシフト幅Ｓによって決定される。シフト幅Ｓの時間窓とは、開始時刻をＳだけ遅らせたものである。従ってＴ＞Ｓの場合、時間窓はＴ−Ｓだけ重畳することになる。
【００３９】
時間幅Ｔは「どの時間幅で滞在又は滞留を判定するか」を決めるパラメータである。ここで、時間窓内に所定数以上の位置情報が存在しないと滞在／移動の判定が難しい。従って、時間幅Ｔは、通信履歴の通信記録（ログ）数から判断して、時間窓内にできるだけ所定数以上の位置情報が入るように決定することが好ましい。
【００４０】
また、シフト幅Ｓは、その幅を短くすると滞在時間区間の時間解像度が増す。一方で、その幅を長くすると、時間窓の数が多くなるので計算量が増大する。従って、シフト幅Ｓは、アプリケーションの求める時間解像度及び処理時間に応じて決定されることが好ましい。
【００４１】
時間窓分割部１２１は、「短時間滞留」及び「滞在」の判定を仕分けるため、２種類の時間窓を設定する。このうち「短時間滞留」の判定では、実際の短時間滞留の時間、例えば電車等の移動手段の一時停止及び停車の時間を勘案し、より短い時間幅（第１の時間幅）を有する第１の時間窓を設定する。ここで、第１の時間幅Ｔは、時間窓内に含まれる位置情報の数を勘案して設定してもよい。さらには、第１の時間幅Ｔとして、エリア毎の短時間滞留の時間長に関する分布を取得し、同時間長の平均、最頻値又はＮ分位点（０≦Ｎ≦１）を用いてもよい。以下の実施例では、Ｔ＝５分及びＳ＝２分３０秒である第１の時間窓を採用する。
【００４２】
一方、「滞在」の判定では、時間窓内に一定数の位置情報が含まれるように第１の時間幅よりも長い時間幅（第２の時間幅）を有する第２の時間窓を設定する。以下の実施例では、Ｔ＝２０分及びＳ＝１０分である第２の時間窓を採用する。
【００４３】
図６は、第１の時間窓（Ｔ＝５分及びＳ＝２分３０秒）の開始時刻及び終了時刻を示す表である。図６によれば、時間窓１は17:50:00〜17:54:59であり、Ｔ＝00:05:00となっている。また、時間窓２は17:52:30〜17:57:29であり、時間窓１に対してＳ＝00:02:30となっていることが分かる。
【００４４】
図７は、携帯端末毎に、図５の各行（通信記録）を図６の第１の時間窓毎に分類した表である。尚、同表では、時間窓内の点（位置情報）の数が４以上のもののみが記録されている。図７によれば、携帯端末00001について、第１の時間窓１２には５個の通信記録が属し、第１の時間窓１３には４個の通信記録が属している。
【００４５】
図８は、第２の時間窓（Ｔ＝２０分及びＳ＝１０分）の開始時刻及び終了時刻を示す表である。図８によれば、時間窓１は17:50:00〜18:09:59であり、Ｔ＝00:20:00となっている。また、時間窓２は18:00:00〜18:19:59であり、時間窓１に対してＳ＝00:10:00となっていることが分かる。
【００４６】
図９は、携帯端末毎に、図５の各行（通信記録）を図８の第２の時間窓毎に分類した表である。図９によれば、携帯端末00001について、第２の時間窓１には５個の通信記録が属し、第２の時間窓２には６個の通信記録が属している。
【００４７】
［滞在判定部１２２］
滞在判定部１２２（図２）は、各携帯端末２につき、第２の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布に基づいて「滞在」か否かを判定し、「滞在」と判定された第２の時間窓における位置の確率分布に基づいて「滞在地」を決定する。具体的には、第２の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布が単峰性を有するならば「滞在」と判定し、単峰性を有さないならば「移動」と判定する。
【００４８】
ここで、単峰性とは、位置の確率分布が１つの山の形状をしている（１つのピークをなす）ことを意味する。即ち、１つの第２の時間窓（例えば２０分）に属する基地局位置の確率分布が単峰性を有する場合、この時間区間については「滞在」と判定することができる。一方、基地局位置の確率分布が、複数の山の形状をしている（複数のピークをなす）ならば多峰性を有するものとする。１つの第２の時間窓について多峰性を有する場合、この時間区間については「移動」中と判定することができる。
【００４９】
尚、滞在判定部１２２は、滞在判定に必要な最小点数（基地局位置情報数）に関する条件を設定し、最小点数に満たない第２の時間窓では、「滞在」ではないと判定してもよい。以下、最小点数を４とする。
【００５０】
図１０は、単峰性を有するか否かを判定するためのフローチャートである。
【００５１】
図１０によれば、滞在判定部１２２は、基地局の位置情報の確率分布が単峰性を有するか否かを判定するため、代表点計算処理を実行する。その結果、代表点の種類数が１個であれば単峰性を有しているので「滞在」と判定し、代表点の種類数が複数個であれば多峰性を有しているので「移動」中と判定する。
【００５２】
代表点計算処理は、各第２の時間窓に含まれる複数の位置情報について、以下のステップＳ１〜Ｓ５によって実行される。
（Ｓ１）任意の点（位置情報）を、最初の中心点とする。
（Ｓ２）中心点を中心とした第１の閾値（例えば２ｋｍ）の半径の円に含まれる点（位置情報）を用いて、重心を算出する。
（Ｓ３）次に、算出された重心と現在の中心点との差（変化量）が、第２の閾値（例えば１００ｍ）以下であるか否かを判定する。
（Ｓ４）Ｓ３において偽と判定された場合、その重心を新たな中心点とする。次いで、再びＳ２へ戻り、変化量が第２の閾値以下に収まるまで繰り返す。
（Ｓ５）Ｓ３において真と判定された場合、その重心（収束した点）を代表点とする。
【００５３】
最後に、各第２の時間窓について、収束した代表点の種類数が１個の場合には「滞在」と判定し、複数個の場合には「移動」と判定する。ここで、当該第２の時間窓について、全ての代表点が第１の閾値又は第２の閾値の半径の円周領域内に収まる場合、収束した代表点の種類数が１個であるとすることも好ましい。
【００５４】
以下、図９の第２の時間窓１について、具体的に、滞在／移動を代表点抽出処理を用いて判定する。
【００５５】
（第２の時間窓１における滞在移動判定）
（ａ）第２の時間窓１の点（35.845，139.504）に関する１回目の重心を計算する。第２の時間窓１の点（35.845，139.504）と第２の時間窓１に含まれるその他の点との距離はすべて２ｋｍ以内であるので、その他の点すべての平均をとると（35.845，139.503）となる。
（ｂ）第２の時間窓１の点（35.845，139.504）に関する２回目の重心を計算する。２回目の重心計算では、中心点を（35.845，139.503）とする。この中心点と第２の時間窓１に含まれるその他の点との距離はすべて２ｋｍ以内であるので、その他の点すべての平均をとると（35.845，139.503）となる。
（ｃ）１回目と２回目の重心計算の結果は同じであり変化量は１００ｍ以下であるので、第２の時間窓１の点（35.845，139.504）の代表点は（35.845，139.503）となる。
（ｄ）同様に、第２の時間窓１における他の点の各々について代表点を算出すると、いずれの代表点も（35.845，139.503）となる。
（ｅ）以上により、計算された代表点はいずれの点についても（35.845，139.503）であり、代表点の種類数は１であるので、第２の時間窓１は「滞在」と判定される。
【００５６】
尚、滞在判定部１２２は、第２の時間窓毎に、複数の基地局位置情報に対してカーネル密度推定(Kernel density estimation)を用いて単峰性を有するか否かを判定することも好ましい。カーネル密度推定とは、確率変数の確率密度関数を推定するべく、ある母集団の標本のデータを外挿する方法である（例えば、野村友和、「カーネル密度推定」、[online]、［平成２５年８月８日検索］、インターネット＜URL:http://www.econ.kobe-u.ac.jp/~nomura/lecture/11f/kd.pdf＞参照）。この方法によれば、カーネル関数を用いて峰となるコブを導出することができる。
【００５７】
次いで、滞在判定部１２２は、「滞在」と判定された第２の時間窓の位置情報を収集する。「滞在」と判定された第２の時間窓の代表点の数は１である。図１１は、「滞在」と判定された第２の時間窓及び対応する代表点位置情報を示す表である。図１１によれば、第２の時間窓１、２及び６が「滞在」と判定されている。
【００５８】
滞在判定部１２２は、さらに、「滞在」と判定された各第２の時間窓の複数の位置情報の重心を「滞在地クラスタ」（「滞在地」）とする。具体的には、この重心を代表点とし、互いに近接した代表点の集合を１つの「滞在地クラスタ」とする。
【００５９】
図１０に示すように、この「滞在地クラスタ」を形成する位置クラスタリング処理も、上述した滞在移動判定での処理と同様に代表点計算処理を実行する。具体的には、各第２の時間窓で抽出された代表点の位置情報について、所与の中心点から第１の閾値の範囲で重心を算出し、この重心と中心点との差（変化量）が第２の閾値に収まるまで繰り返し、最終的に得られた各位置の収束値（図１１の代表点における代表点）を、第２の時間窓毎の「滞在地クラスタ」の代表点とする。
【００６０】
図１２は、図１１に示した第２の時間窓毎の代表点位置情報に基づいて算出された「滞在地クラスタ」の代表点位置情報を示す表である。同表での代表点計算処理では、第１の閾値を２ｋｍ、第２の閾値を１００ｍとした。図１２によれば、第２の時間窓１及び２について１つの「滞在地クラスタ」が形成され、この「滞在地クラスタ」の代表点は、緯度35.845及び経度139.503であることが理解される。また、第２の時間窓６では、緯度35.862及び経度139.515の位置が別の「滞在地クラスタ」の代表点となることが理解される。
【００６１】
このように、適切に設定された第２の時間窓を利用することによって、携帯端末の測位機能に頼ることなく、基地局位置情報を用いてユーザの「滞在」状態及び「滞在地」を推定することが可能となる。
【００６２】
［第１の短時間滞留判定部１２３］
第１の短時間滞留判定部１２３（図２）は、各携帯端末２につき、
（ａ）第１の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布に基づいて「滞留」か否かを判定し、「滞留」と判定された第１の時間窓における位置の確率分布に基づいて「滞留地」を決定し、
（ｂ）「滞留」と判定された所定数以下の連続する第１の時間窓に対し、当該滞留の所定時間以上前又は後に異なる「滞留地」を有する第１の時間窓が存在しており、且つ該連続する第１の時間窓の「滞留地」と該異なる「滞留地」とが所定距離以上離隔している場合、該連続する第１の時間窓を「短時間滞留」と判定する。
【００６３】
具体的に、第１の短時間滞留判定部１２３は、まず、第１の時間窓毎に、複数の基地局位置情報に基づく位置の確率分布が単峰性を有するならば「滞留」と判定し、単峰性を有さないならば「滞留」ではないと判定する。この「滞留」判定の処理フローは、図１０を用いて説明した「滞在」判定の処理フローと同様である。即ち、図１０に示した「滞在」判定の処理フローにつき、第２の時間窓に代えて第１の時間窓を採用し、「滞在」との判定に代えて「滞留」との判定を採用したものが「滞留」判定の処理フローとなる。
【００６４】
図１３は、「滞留」と判定された第１の時間窓及び対応する代表点位置情報を示す表である。図１３によれば、携帯端末00001については、第１の時間窓１３、１７及び１８が「滞留」と判定されている。また、携帯端末00002については、第１の時間窓１３、１５、１６及び１７が「滞留」と判定されている。
【００６５】
第１の短時間滞留判定部１２３は、さらに、「滞留」と判定された各第１の時間窓の複数の位置情報の重心を「滞留地」とする。具体的には、この重心を代表点とし、互いに近接した代表点の集合を１つの「滞留地」とする。この「滞在地」を形成する位置クラスタリング処理でも、上述した滞在移動判定での処理（図１０）と同様に代表点計算処理を実行する。
【００６６】
第１の短時間滞留判定部１２３は、次いで、「滞留」と判定された所定数以下の連続する第１の時間窓に対し、当該滞留の所定時間以上前又は後に異なる「滞留地」を有する第１の時間窓が存在しており、且つこの連続する第１の時間窓の「滞留地」と、この異なる「滞留地」とが所定距離以上離隔している場合、この連続する第１の時間窓を「短時間滞留」と判定する。
【００６７】
以下の実施例では、２つ以下（即ち２つ）の連続する第１の時間窓において滞留と「判定」され、滞留の２分３０秒以上前又は滞留の２分３０秒以上後に異なる「滞留地」において滞留し、且つ「滞留地」間の距離が２ｋｍ以上離れている場合に、「短時間滞留」と判定する。
【００６８】
図１４は、「短時間滞留」と判定された第１の時間窓及び対応する「滞留地」代表点を示す表である。図１４によれば、携帯端末00001について、第１の時間窓１３並びに第１の時間窓１７及び１８が「短時間滞留」と判定されている。また、携帯端末00002について、第１の時間窓１３並びに第１の時間窓１５及び１６が「短時間滞留」と判定されている。
【００６９】
このように、適切に設定された第１の時間窓を利用することによって、携帯端末の測位機能に頼ることなく、基地局位置情報を用いてユーザの「短時間滞留」を推定することが可能となる。
【００７０】
［基地局情報収集部１２４］
基地局情報収集部１２４（図２）は、複数の携帯端末２（複数ユーザ）についての、「短時間滞留」と判定された第１の時間窓の「滞留地」の確率分布に基づいて、その重心を「短時間滞留地」（滞留地代表点）として算出し、「短時間滞留地」毎に、
（ａ）当該基地局位置情報と、（ｂ）当該基地局に対する接続確率と
を対応付けた基地局リストを生成する。ここで、「滞留」に係る情報の収集先を１つの携帯端末２（１ユーザ）に限定した場合、「短時間滞留地」において一定回数以上の接続回数を有する事例が少なくデータ収集に限度が生じるが、複数の携帯端末２（複数ユーザ）から収集すると、一定数の事例を概ね確実に収集することが可能になる。
【００７１】
図１５は、複数の携帯端末２から「滞留」に係る情報を収集する様子を示す概略図、及び「短時間滞留地」における滞留地代表点の算出結果を示す表である。また、図１６は、短時間滞留地の基地局リストを示す表である。
【００７２】
図１５によれば、短時間滞留地として、短時間滞留地１〜３が挙げられている。図１６では、例えば短時間滞留地１について、対応する３つの基地局位置情報が挙げられ、各位置情報（基地局）に接続確率が対応付けられている。例えば、短時間滞留地１の位置情報（35.848，139.506）の基地局では接続回数が２であるが、短時間滞留地１での総接続回数が２＋２＋４＝８であるから、接続確率は２／８＝０.２５０となる。
【００７３】
［第２の短時間滞留判定部１２５］
第２の短時間滞留判定部１２５（図２）は、取得された通信履歴について、短時間滞留地の基地局リスト（図１６）に含まれる基地局が存在する場合、この基地局の基地局位置情報に、この基地局リストで対応している「短時間滞留地」を対応付けた短時間滞留地履歴を生成する。即ち、この基地局識別子を短時間滞留地番号で置き換える。尚、判定に用いる短時間滞留地の基地局リストは、「短時間滞留地」に関して接続確率が所定閾値以上の基地局に限定してもよい。本実施形態では限定しない。
【００７４】
図１７は、第２の短時間滞留判定の結果を示す表である。
【００７５】
図１７によれば、携帯端末00001は、短時間滞留地１を開示時刻18:21:10から終了時刻18:21:40まで「短時間滞留」し、次に、短時間滞留地２を開示時刻18:28:20から終了時刻18:30:00まで「短時間滞留」し、その後、短時間滞留地３を開示時刻18:33:10から終了時刻18:35:20まで「短時間滞留」したことが理解される。このように、第２の短時間滞留判定結果によれば、携帯端末２が「短時間滞留」した短時間滞留履歴を取得することができる。
【００７６】
［滞在滞留時系列データ生成部１２６］
滞在滞留時系列データ生成部１２６（図２）は、携帯端末２毎に、生成された短時間滞留地履歴に基づいて、決定された「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを生成する。尚、開始時刻及び終了時刻を対応付けた「滞在地」データは、滞在判定部１２２で決定された「滞在地」を入力した基地局情報収集部１２４が、「滞在地」毎に基地局位置情報を対応付けた基地局リストを生成することによって取得される。
【００７７】
図１８は、携帯端末00001及び00002が「滞在」及び「短時間滞留」を行いながら進行する様子を示す概略図、及び生成された滞在滞留時系列データを示す表である。
【００７８】
図１８によれば、携帯端末00001について、滞在地１から短時間滞留地１を経て短時間滞留地３に至る経緯が理解される。一方、携帯端末00002についても、短時間滞留地１から短時間滞留地２を経て滞在地２に至る経緯が理解される。また、両携帯端末ともに、短時間滞留地１には開始時刻18:20:00〜終了時刻18:24:59の間滞留しており、例えば、この時刻範囲において同一の駅に滞留していたことが分かる。
【００７９】
［短時間滞留地間遷移モデル構築部１２７］
短時間滞留地間遷移モデル構築部１２７（図２）は、図１８に示したような滞在滞留時系列データから、所定頻度以上で発生する「短時間滞留地」間遷移パターンを抽出し、抽出した「短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「短時間滞留地」間遷移モデルを構築する。具体的には、「短時間滞留地」の前後に、所定閾値以上の遷移確率で出現する「短時間滞留地」を検出する。
【００８０】
図１９は、「短時間滞留地」間遷移モデルを示す表である。
【００８１】
図１９では、０．５以上の確率で出現する遷移パターンが抽出されている。ここで、図１８に示すように、滞在滞留時系列データは２種類であるので、出現確率０．５以上は、遷移パターンが１種類以上の時系列データに出現することに対応する。さらに、図１９では、平均所要時間が遷移パターン毎に対応付けて記録されている。この平均所要時間は、遷移パターン毎に、遷移元「短時間滞留地」における開始時刻及び終了時刻の中間時刻と、遷移先「短時間滞留地」における開始時刻及び終了時刻の中間時刻との差を計算し、その平均をとることによって算出される。
【００８２】
［滞在地・短時間滞留地間遷移モデル構築部１２８］
滞在地・短時間滞留地間遷移モデル構築部１２８（図２）は、図１８に示したような滞在滞留時系列データから、所定頻度以上で発生する「滞在地・短時間滞留地」間遷移パターンを抽出し、抽出した「滞在地・短時間滞留地」間遷移パターン毎に、当該遷移パターンの出現確率を対応付けた「滞在地・短時間滞留地」間遷移モデルを構築する。具体的には、「滞在地」の前後に、所定閾値以上の遷移確率で出現する「短時間滞留地」を検出する。
【００８３】
図２０は、「滞在地・短時間滞留地」間遷移モデルを示す表である。
【００８４】
図２０では、０．５以上の確率で出現する遷移パターンが抽出されている。ここでも、図１８に示すように、滞在滞留時系列データは２種類であるので、出現確率０．５以上は、遷移パターンが１種類以上の時系列データに出現することに対応する。さらに、図１９では、平均所要時間が遷移パターン毎に対応付けて記録されている。この平均所要時間は、遷移パターン毎に、遷移先／元「短時間滞留地」における開始時刻及び終了時刻の中間時刻と、遷移元／先「滞在地」における開始時刻及び終了時刻のうち、この中間時刻により近い方との差を計算し、その平均をとることによって算出される。
［短時間滞留地間遷移モデル構築の実施例］
【００８５】
ここで、短時間滞留地間遷移モデル構築の簡単な実施例を説明する。複数の携帯端末の滞在滞留時系列データについて、所定の時間（例えば５分）以内に短時間滞留地１に続いて別の短時間滞留地２が検出された場合、その遷移を記録し、短時間滞留地１について記録された全遷移におけるその遷移の数に基づいて、短時間滞留地１から短時間滞留地２への遷移確率を算出する。短時間滞留地１に関する遷移確率は合計すると1になる。以下、短時間滞留地としてＡ〜Ｇが存在する場合について、短時間滞留地間遷移モデルを構築する。
【００８６】
図２１は、短時間滞留地Ａ〜Ｇについての短時間滞留地間遷移モデルを示す表である。
【００８７】
図２１によれば、複数の携帯端末について、短時間滞留地１がＡである場合、この短時間滞留地１に続いて検出される短時間滞留地２がＢである確率は０．９であり、Ｅである確率は０．１である。従って、携帯端末は、短時間滞留地Ａに続いて９０％の確率で短時間滞留地Ｂに遷移し、残りの１０％の場合、短時間滞留地Ｅに遷移することが理解される。
［滞在地・短時間滞留地間遷移モデル構築の実施例］
【００８８】
次いで、滞在地・短時間滞留地間遷移モデル構築の簡単な実施例を説明する。携帯端末毎の滞在滞留時系列データについて、所定の時間（例えば５分）以内に滞在地１に続いて短時間滞留地２が検出された場合、その遷移を記録し、滞在地１について記録された全遷移におけるその遷移の数に基づいて、滞在地１から短時間滞留地２への遷移確率を算出する。滞在地１からの遷移確率は合計すると1になる。一方、短時間滞留地１から滞在地２への遷移モデルも同様に構築される。この場合、滞在地２への遷移確率は合計すると1になる。以下、滞在地としてα及びβが存在し、短時間滞留地としてＡ〜Ｇが存在する場合について、短時間滞留地間遷移モデルを構築する。
【００８９】
図２２は、滞在地α及びβ並びに短時間滞留地Ａ〜Ｇについての滞在地・短時間滞留地間遷移モデルを示す表である。
【００９０】
図２２によれば、ある携帯端末について、滞在地１がαである場合、この滞在地１に続いて検出される短時間滞留地２がＡである確率は０．９であり、Ｅである確率は０．１である。従って、携帯端末は、滞在地αに続いて９０％の確率で短時間滞留地Ａに遷移し、残りの１０％の場合、短時間滞留地Ｅに遷移することが理解される。
【００９１】
一方、ある携帯端末について、遷移先の滞在地２がβである場合、この滞在地２の前に検出される短時間滞留地１がＤである確率は０．９であり、Ｇである確率は０．１である。従って、滞在地βへの遷移元の９０％は短時間滞留地Ｄであり、残りの１０％は短時間滞留地Ｇであることが理解される。
【００９２】
［短時間滞留地補間部１３１］
短時間滞留地補間部１３１（図２）は、滞在滞留時系列データ生成部１２６によって生成された滞在滞留時系列データについて、構築された「短時間滞留地」間遷移モデル（図２１）及び「滞在地・短時間滞留地」間遷移モデル（図２２）に基づき、時系列データにおいて欠損している「短時間滞留地」を補間する。具体的には、滞在滞留時系列データには存在しないが、時系列に出現している「滞在地」と「短時間滞留地」との間、又は「短時間滞留地」間に高い出現確率で出現し得る「短時間滞留地」があれば、この「短時間滞留地」を補間する。
【００９３】
因みに、このような補間の必要が生じるのは、移動中の携帯端末２がいずれかの基地局３の配下に位置するとしても、電波障害物の存在や通信の混雑・輻輳等によって、必ずしも当該基地局３との接続を確立できるとは限らないためである。携帯端末２と基地局３との間で通信ができなければ、通信記録に基地局位置情報を対応付けた通信履歴（図５）を取得することができず、「滞在地」及び「短時間滞留地」の推定もできなくなる。
【００９４】
ここで、短時間滞留地補間部１３１は、滞在滞留時系列データにおいて隣接する「短時間滞留地」同士又は隣接する「滞在地」及び「短時間滞留地」が所定時間以上離隔している場合、この「短時間滞留地」同士の間又はこの「滞在地」及び「短時間滞留地」の間に、欠損した「短時間滞留地」が存在すると推定することも好ましい。
【００９５】
また、短時間滞留地補間部１３１は、時系列において欠損している「短時間滞留地」の候補が複数存在する場合、当該候補を間に含んだ遷移パターンの出現確率に基づく尤度が最も高くなるところの当該候補で補間することも好ましい。
【００９６】
図２３は、「短時間滞留地」補間の実施例を説明するための表である。
【００９７】
図２３には、「滞在地」及び「短時間滞留地」の遷移パターン１〜５が列挙されている。いずれの遷移パターンも、滞在地αから移動を開始し、複数の短時間滞留地を経て、滞在地βで移動を終了する形となっている。各パターンにつき、隣接する「滞在地」及び「短時間滞留地」並びに隣接する「短時間滞留地」同士において、（所定の時間として）５分以上時間的に離隔している場合、その間に「短時間滞留地」を補完する。
【００９８】
図２３に示すように、パターン1では、短時間滞留地Ａと短時間滞留地Ｃとが５分以上離隔しているので、両者の間に１つの短時間滞留地<1>を補間する。ここで、図２１の「短時間滞留地」間遷移モデルによれば、ＡからＣへ至る遷移は、
Ａ→Ｂ→Ｃ
のみである。即ち、Ａからの遷移先はＢ及びＥであるが、Ｃへ遷移する遷移元はＢのみである。従って、ＡとＣとの間にはＢのみが補間可能である。従って、短時間滞留地<1>として短時間滞留地Ｂが決定される。
【００９９】
次に、パターン２では、短時間滞留地Ｂと短時間滞留地Ｄとが５分以上離隔しているので、両者の間に１つの短時間滞留地<2>を補間する。図２１の「短時間滞留地」間遷移モデルによれば、ＢからＤへ至る遷移は、
Ｂ→Ｃ→Ｄ、及びＢ→Ｆ→Ｄ
の２つである。ここで、上記の各遷移を採用した遷移パターンの尤度を算出して比較し、より尤度の高い遷移を採用する。本実施例では尤度は、遷移パターンを構成する遷移要素（矢印１つ分）の遷移確率の積として算出される。各遷移要素の遷移確率は、「短時間滞留地」間遷移モデル（図２１）及び「滞在地・短時間滞留地」間遷移モデル（図２２）で決定された値とする。
【０１００】
Ｂ→Ｃ→Ｄを採用した場合の尤度P(B,C,D)は、
（１）  P(B,C,D)＝P(α,A)・ P(A→B)・P(B→C)・P(C→D)・P(D→β)
となり、Ｂ→Ｆ→Ｄを採用した場合の尤度P(B,F,D)は、
（２）  P(B,F,D)＝P(α,A)・ P(A→B)・P(B→F)・P(F→D)・P(D→β)
となる。ここで、P(X,Y)は、滞在地（短時間滞留地）Xから短時間滞留地（滞在地）Yへの遷移確率である。
【０１０１】
式（１）及び（２）の間での違いは、P(B→C)・P(C→D)の部分及びP(B→F)・P(F→D)の部分であるので、これらの部分の値を比較する。
（１ａ）  P(B→C)・P(C→D)＝０．５×０．９＝０．４５
（２ａ）  P(B→F)・P(F→D)＝０．５×０．２＝０．１０
であるので、Ｂ→Ｃ→Ｄを採用した遷移パターンの方がより高い尤度を有する。従って、短時間滞留地<2>として短時間滞留地Ｃが決定される。
【０１０２】
次に、パターン３では、ＡとＤとの間に短時間滞留地を補完する。図２１の「短時間滞留地」間遷移モデルによれば、Ａから短時間滞留地を経てＤへ至る遷移は、
Ａ→Ｂ→Ｃ→Ｄ、Ａ→Ｂ→Ｆ→Ｄ、及びＡ→Ｅ→Ｆ→Ｄ
の３つである。ここでも、上記の各遷移を採用した遷移パターンの尤度を算出して比較し、より尤度の高い遷移を採用する。
【０１０３】
Ａ→Ｂ→Ｃ→Ｄ、Ａ→Ｂ→Ｆ→Ｄ及びＡ→Ｅ→Ｆ→Ｄを採用した場合の尤度P(A,B,C,D)、P(A,B,F,D)及びP(A,E,F,D)はそれぞれ、
（３）  P(A,B,C,D)＝P(α,A)・ P(A→B)・P(B→C)・P(C→D)・P(D→β)
（４）  P(A,B,F,D)＝P(α,A)・ P(A→B)・P(B→F)・P(F→D)・P(D→β)
（５）  P(A,E,F,D)＝P(α,A)・ P(A→E)・P(E→F)・P(F→D)・P(D→β)
となる。
【０１０４】
式（３）〜（５）の間で異なる部分の値を算出し比較すると、それぞれ、
（３ａ）  P(A→B)・P(B→C)・P(C→D)＝０．４０５
（４ａ）  P(A→B)・P(B→F)・P(F→D)＝０．０９０
（５ａ）  P(A→E)・P(E→F)・P(F→D)＝０．０２０
となるので、Ａ→Ｂ→Ｃ→Ｄを採用した遷移パターンが最も高い尤度を有することが分かる。従って、短時間滞留地<3>及び<4>としてそれぞれ短時間滞留地Ｂ及びＣが決定される。
【０１０５】
次に、パターン４では、滞在地αと短時間滞留地Ｂとが５分以上離隔しているので、両者の間に１つの短時間滞留地<5>を補間する。図２２の「滞在地・短時間滞留地」間遷移モデル及び図２１の「短時間滞留地」間遷移モデルによれば、αからＢへ至る遷移は、
α→Ａ→Ｂ
の１つだけである。従って、短時間滞留地<5>として短時間滞留地Ａが決定される。
【０１０６】
最後に、パターン５では、短時間滞留地Ｃと滞在地βとが５分以上離隔しているので、Ｃとβとの間に短時間滞留地<6>を補完する。図２２の「滞在地・短時間滞留地」間遷移モデルによれば、Ｃからβへ至る遷移は、
Ｃ→Ｄ→β、及びＣ→Ｇ→β
の２つである。ここでも、上記の各遷移を採用した遷移パターンの尤度を算出して比較し、より尤度の高い遷移を採用する。
【０１０７】
Ｃ→Ｄ→β及びＣ→Ｇ→βを採用した場合の尤度P(C,D,β)及びP(C,G,β)はそれぞれ、
（６）  P(C,D,β)＝P(α,A)・ P(A→B)・P(B→C)・P(C→D)・P(D→β)
（７）  P(C,G,β)＝P(α,A)・ P(A→B)・P(B→C)・P(C→G)・P(G→β)
となる。
【０１０８】
式（６）及び（７）の間で異なる部分の値を算出し比較すると、
（６ａ）  P(C→D)・P(D→β)＝０．８１
（７ａ）  P(C→G)・P(G→β)＝０．０１
となるので、Ｃ→Ｄ→βを採用した遷移パターンがより高い尤度を有することが分かる。従って、短時間滞留地<6>として短時間滞留地Ｄが決定される。
【０１０９】
尚、短時間滞留地補間部１３１が、滞在滞留時系列データにおいて「短時間滞留地」を補間する必要がないと判断した場合、滞在滞留時系列データ、従って第２の短時間滞留判定の結果（図１７）は、そのまま出力される。
【０１１０】
［ユーザ検索部］
ユーザ検索部１３２（図２）は、所定の携帯端末に係る上記の短時間滞留地補間処理後の滞在滞留時系列データと、他の携帯端末に係る短時間滞留地補間処理後の滞在滞留時系列データとの間の最長一致部分系列長に基づいて、この所定の携帯端末の移動経路に類似した移動経路をとる携帯端末を検索する。ここで、最長一致部分系列長は、比較する２つの時系列データにおいて、例えばＡ→Ｂ→Ｃ→Ｄ→ＥとＡ→Ｃ→Ｄ→Ｅ→Ｆとにおける共通部分Ｃ→Ｄ→Ｅのように「短時間滞留地」の時系列が一致する部分の長さと定義される。
【０１１１】
具体的に、ユーザ検索部１３２は、２つの携帯端末２間の類似度を、
（８）（類似度）＝
（最長一致部分系列長）／（時系列データのうちの長いほうの系列長）
として算出し、この類似度が所定閾値以上の携帯端末を検索することができる。ここで、分母の（時系列データのうちの長いほうの系列長）とは、２つの携帯端末２に係る補間処理後の滞在滞留時系列データのうちの長いほうの系列長のことである。この（時系列データのうちの長いほうの系列長）で除することによって類似度が正規化される。また、ユーザ検索部１３２は、ユーザによって指定された検索対象の時間区間のうち、互いに所定時間以上離隔した「滞在地」に対応する時間区間の間となる時間区間について、上記の最長一致部分系列長を調査することも好ましい。
【０１１２】
一実施例として、指定された時間区間が18:20〜18:35であって、指定された携帯端末が携帯端末00001であり、この指定された時間区間における携帯端末00001の移動経路に類似した移動経路をとる１または複数のユーザを検索する。この検索においては、携帯端末00001と他のユーザとの類似度を算出し、類似度が所定閾値＝０．８以上のユーザを検索する。
【０１１３】
以下、図１７の第２の短時間滞留判定の結果が上述した補正処理後の結果であるとする。この短時間滞留判定結果によれば、携帯端末00001と携帯端末00002とは、指定時間区間18:20〜18:35における「短時間滞留地」の共通する時系列として、
短時間滞留地１，短時間滞留地２，短時間滞留地３
を有している。従って、（最長一致部分系列長）＝３となる。また、携帯端末00001及び携帯端末00002の時系列データ長もともに３なので、（時系列データのうちの長いほうの系列長）＝３である。従って、式（８）より、（類似度）＝３／３＝１を得る。類似度反知恵の所定閾値は０．８であるから、携帯端末00001と携帯端末00002との類似度は、この所定閾値以上である。従って、携帯端末00001のユーザにおける18:20〜18:35の移動経路に類似した移動経路をとるユーザの携帯端末として、携帯端末00002が検索される。
【０１１４】
以上、詳細に説明したように、本発明の装置、プログラム及び方法によれば、携帯端末の測位機能に頼ることなく、通信事業者設備によって取得可能な基地局位置情報を用いて、携帯端末を所持したユーザの移動経路に類似した移動経路をとるユーザを検索することができる。ここで、基地局位置情報では一般に、空間的粒度が粗く且つ時間間隔が一定ではないが、このような基地局位置情報を使用しても、ユーザの「滞在地」及び／又は「短時間滞留地」を時系列に並べた滞在滞留時系列データを算出することができる。特に、本発明によれば、携帯端末での測位のための処理負荷を回避しつつ、ユーザの滞在滞留時系列データの情報、更には類似移動経路をとるユーザを推定するための情報を通信事業者側のみで取得することができる。
【０１１５】
さらに、本発明によれば、通常発生し得る滞在滞留時系列データにおける欠損の存在にもかかわらず、より高い精度でユーザの移動経路を推定する。その結果、類似移動経路をとるユーザをより確実に検索することが可能となる。
【０１１６】
ここで、ユーザの移動経路に類似した移動経路をとるユーザを検索することにより提供されるサービスとして、例えば、携帯端末を所持しており移動経路が互いに類似するユーザ群に対し、その移動経路の周辺情報に即した広告やクーポン等のオンライン情報を配信することができる。これにより、配信情報の広告効果の向上が見込まれる。さらに、移動経路が集中する領域には基地局を増設する等、好適な無線通信ネットワーク設計・構築の際の判断データを提供することができる。
【０１１７】
前述した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲内での種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例示であって、何ら制約を意図するものではない。本発明は、特許請求の範囲及びその均等物によってのみ制約される。
【符号の説明】
【０１１８】
１  通信設備装置（類似移動経路ユーザ検索用の装置）
１０  通信インタフェース部
１１１  通信履歴収集部
１１２  基地局位置情報管理部
１１３  位置情報履歴蓄積部
１２  時系列データ生成部１２
１２１  時間窓分割部
１２２  滞在判定部
１２３  第１の短時間滞留判定部
１２４  基地局情報収集部
１２５  第２の短時間滞留判定部
１２６  滞在滞留時系列データ生成部
１２７  短時間滞留地間遷移モデル構築部
１２８滞在地・短時間滞留地間遷移モデル構築部
１３１  短時間滞留地補間部
１３２  ユーザ検索部
２  携帯端末
３  基地局
【図１】
0006053027.tif 000002
【図２】
0006053027.tif 000003
【図３】
0006053027.tif 000004
【図４】
0006053027.tif 000005
【図５】
0006053027.tif 000006
【図６】
0006053027.tif 000007
【図７】
0006053027.tif 000008
【図８】
0006053027.tif 000009
【図９】
0006053027.tif 000010
【図１０】
0006053027.tif 000011
【図１１】
0006053027.tif 000012
【図１２】
0006053027.tif 000013
【図１３】
0006053027.tif 000014
【図１４】
0006053027.tif 000015
【図１５】
0006053027.tif 000016
【図１６】
0006053027.tif 000017
【図１７】
0006053027.tif 000018
【図１８】
0006053027.tif 000019
【図１９】
0006053027.tif 000020
【図２０】
0006053027.tif 000021
【図２１】
0006053027.tif 000022
【図２２】
0006053027.tif 000023
【図２３】
0006053027.tif 000024