(57)【要約】【課題】位置情報提供装置において、長時間の情報を集めたとしても、ユーザの行動経路を第三者が推定できないようにする。【解決手段】本発明の位置情報提供装置は、位置情報取得部、仮名変換部、記録部を備える。仮名変換部は、特定位置情報の中のユーザ端末を特定する情報を仮名に変更し、仮名、ユーザ端末の位置を示す情報、位置を示す情報を取得した時刻を示す情報を含む仮名位置情報を出力する。また、仮名変換部は、２つ以上のユーザ端末が、位置を示す情報を取得した時刻の差が所定の時間範囲内であって位置の差が所定の位置範囲内であることを交換条件とし、交換条件を満たす２つ以上のユーザ端末があるときに、所定の確率で仮名を交換する。記録部は、位置を示す情報を取得した時刻ごとに、ユーザ端末を特定する情報と仮名の対応関係を記録する。【選択図】図２
2014092978.tif 000002
【特許請求の範囲】
【請求項１】
複数のユーザ端末のそれぞれから、ユーザ端末を特定する情報、ユーザ端末の位置を示す情報、前記位置を示す情報を取得した時刻を示す情報を含む特定位置情報を取得する位置情報取得部と、
前記特定位置情報の中のユーザ端末を特定する情報を仮名に変更し、前記仮名、ユーザ端末の位置を示す情報、前記位置を示す情報を取得した時刻を示す情報を含む仮名位置情報を出力する仮名変換部と、
前記位置を示す情報を取得した時刻ごとに、前記ユーザ端末を特定する情報と前記仮名の対応関係を記録する記録部と、
を備え、
前記仮名変換部は、
２つ以上のユーザ端末が、位置を示す情報を取得した時刻の差が所定の時間範囲内であって位置の差が所定の位置範囲内であることを交換条件とし、前記交換条件を満たす２つ以上のユーザ端末があるときに、所定の確率で仮名を交換する
ことを特徴とする位置情報提供装置。
【請求項２】
請求項１記載の位置情報提供装置が出力した仮名位置情報のプライバシー安全度を評価する安全度評価装置であって、
前記仮名変換部は、前記交換条件を満たす２つ以上のユーザ端末があるときに、前記記録部に前記交換条件を満たすユーザ端末に対応する仮名を記録させ、
初期状態の可能経路モデルを生成し、前記記録部に記録された前記交換条件を満たすユーザ端末に対応する仮名から仮名交換系列を生成する仮名交換モデル抽出部と、
前記可能経路モデルを、前記仮名交換系列を制約条件として更新する可能経路計算部と、
更新された可能経路モデルから、前記交換条件を満たす時刻の直後ごとに各仮名が割り付けられる可能性のあるユーザ端末の数を計算し、前記プライバシー安全度として出力するプライバシー安全度出力部と、
を備え、
前記可能経路モデルは、最初に位置を示す情報を取得した時刻での各仮名と対応するユーザ端末を特定する情報、最後に前記交換条件を満たす時刻の後に各仮名と対応するユーザ端末を特定する情報、および最後以外の前記交換条件を満たす時刻の直後ごとに各仮名と対応する可能性のあるユーザ端末を特定する情報とが関連付けられたモデルであり、
前記仮名交換系列は、前記交換条件を満たす時刻ごとに、交換される可能性のある複数の仮名が列挙された系列である
ことを特徴とする安全度評価装置。
【請求項３】
請求項２記載の安全度評価装置であって、
前記可能経路計算部は、
前記交換条件を満たす時刻が早い方から順番に、前記可能経路モデルの前記交換条件を満たす時刻の直前の各仮名と対応する可能性のあるユーザ端末を特定する情報から、前記可能経路モデルの前記交換条件を満たす時刻の直後の各仮名と対応する可能性のあるユーザ端末を特定する情報を、前記仮名交換系列にしたがって限定することで、前記可能経路モデルを更新する順方向可能経路計算部と、
前記交換条件を満たす時刻が遅い方から順番に、前記可能経路モデルの前記交換条件を満たす時刻の直後の各仮名と対応する可能性のあるユーザ端末を特定する情報から、前記可能経路モデルの前記交換条件を満たす時刻の直前の各仮名と対応する可能性のあるユーザ端末を特定する情報を、前記仮名交換系列にしたがって限定することで、前記可能経路モデルを更新する逆方向可能経路計算部と、
前記順方向可能経路計算部による更新と前記逆方向可能経路計算部による更新を、前記可能経路モデルが変化しなくなるまで交互に繰り返す反復制御部と
を備えることを特徴とする安全度評価装置。
【請求項４】
位置情報取得部が、複数のユーザ端末のそれぞれから、ユーザ端末を特定する情報、ユーザ端末の位置を示す情報、前記位置を示す情報を取得した時刻を示す情報を含む特定位置情報を取得する位置情報取得ステップと、
仮名変換部が、前記特定位置情報の中のユーザ端末を特定する情報を仮名に変更し、前記仮名、ユーザ端末の位置を示す情報、前記位置を示す情報を取得した時刻を示す情報を含む仮名位置情報を出力する仮名変換ステップと
を有し、
前記仮名変換ステップは、
２つ以上のユーザ端末が、位置を示す情報を取得した時刻の差が所定の時間範囲内であって位置の差が所定の位置範囲内であることを交換条件とし、前記交換条件を満たす２つ以上のユーザ端末があるときに、所定の確率で仮名を交換し、
記録部に、前記位置を示す情報を取得した時刻ごとに、前記ユーザ端末を特定する情報と前記仮名の対応関係を記録する
ことを特徴とする位置情報提供方法。
【請求項５】
請求項４記載の位置情報提供方法で出力された仮名位置情報のプライバシー安全度を評価する安全度評価方法であって、
前記仮名変換ステップでは、前記交換条件を満たす２つ以上のユーザ端末があるときに、前記記録部に前記交換条件を満たすユーザ端末に対応する仮名を記録させ、
仮名交換モデル抽出部が、初期状態の可能経路モデルを生成し、前記記録部に記録された前記交換条件を満たすユーザ端末に対応する仮名から仮名交換系列を生成する仮名交換モデル抽出ステップと、
可能経路計算部が、前記可能経路モデルを、前記仮名交換系列を制約条件として更新する可能経路計算ステップと、
プライバシー安全度出力部が、更新された可能経路モデルから、前記交換条件を満たす時刻の直後ごとに各仮名が割り付けられる可能性のあるユーザ端末の数を計算し、前記プライバシー安全度として出力するプライバシー安全度出力ステップと、
を有し、
前記可能経路モデルは、最初に位置を示す情報を取得した時刻での各仮名と対応するユーザ端末を特定する情報、最後に前記交換条件を満たす時刻の後に各仮名と対応するユーザ端末を特定する情報、および最後以外の前記交換条件を満たす時刻の直後ごとに各仮名と対応する可能性のあるユーザ端末を特定する情報とが関連付けられたモデルであり、
前記仮名交換系列は、前記交換条件を満たす時刻ごとに、交換される可能性のある複数の仮名が列挙された系列である
ことを特徴とする安全度評価方法。
【請求項６】
請求項５記載の安全度評価方法であって、
前記可能経路計算ステップは、
前記交換条件を満たす時刻が早い方から順番に、前記可能経路モデルの前記交換条件を満たす時刻の直前の各仮名と対応する可能性のあるユーザ端末を特定する情報から、前記可能経路モデルの前記交換条件を満たす時刻の直後の各仮名と対応する可能性のあるユーザ端末を特定する情報を、前記仮名交換系列にしたがって限定することで、前記可能経路モデルを更新する順方向可能経路計算サブステップと、
前記交換条件を満たす時刻が遅い方から順番に、前記可能経路モデルの前記交換条件を満たす時刻の直後の各仮名と対応する可能性のあるユーザ端末を特定する情報から、前記可能経路モデルの前記交換条件を満たす時刻の直前の各仮名と対応する可能性のあるユーザ端末を特定する情報を、前記仮名交換系列にしたがって限定することで、前記可能経路モデルを更新する逆方向可能経路計算サブステップと、
前記順方向可能経路計算部による更新と前記逆方向可能経路計算部による更新を、前記可能経路モデルが変化しなくなるまで交互に繰り返す反復制御サブステップと
を有することを特徴とする安全度評価方法。
【請求項７】
請求項１記載の位置情報提供装置、または請求項２もしくは３記載の安全度評価装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のユーザ端末から位置を示す情報を取得し、ユーザ端末を特定する情報を仮名に変換して出力する位置情報提供装置、位置情報提供方法、提供された情報のプライバシー安全度を評価する安全度評価装置、安全度評価方法、およびそれらのプログラムに関する。
【背景技術】
【０００２】
ＧＰＳ（Global Positioning System：全地球測位システム）により取得したユーザの現在地情報を利用して、様々なサービスが提供されている。一般によく利用されるサービスを提供するための全体構成を図１に示す。ユーザ端末７００１，…，７００Ｋは、ＧＰＳ機能などの位置を示す情報を取得する機能が搭載された携帯電話などの端末であり、所定時間間隔ごとに、位置を示す情報と位置を示す情報を取得した時刻とユーザ端末を特定する情報（ＩＤ）とを対応付けて、位置情報提供装置８００に送信する。なお、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数である。
【０００３】
位置情報提供装置８００は、携帯電話事業者やインターネットプロバイダなどのサービスプロバイダが管理する装置であり、ユーザ端末から取得した情報のうち、ＩＤを仮名に変換し、位置を示す情報と位置を示す情報を取得した時刻と仮名とを対応付けて、コンテンツ提供装置９００に送信する。
【０００４】
コンテンツ提供装置９００は、コンテンツプロバイダが管理する装置であり、位置情報提供装置から取得した位置を示す情報と位置を示す情報を取得した時刻と仮名とからなる情報を利用したサービスやコンテンツを、ユーザ端末（ユーザ）に提供する。例えば、同じ時刻に同じ方向に向かって道路を進んでいるユーザがどのくらいいるか（道路の混雑状況）を解析したり、同じ時刻に近い場所にいる別のユーザを探したりするサービスを利用できる。仮名は、ユーザが特定されないようユーザのプライバシーを確保しつつ、これらのサービスを提供するための手段として利用される。
【０００５】
しかしながら、毎回同じ仮名を利用する場合、長い時間区間においてこれらの情報を集めると、その仮名のユーザの行動経路が特定できる。つまり、ユーザが公開を意図していないプライバシーに関する情報が、知らない間に第三者（コンテンツプロバイダを含む）に漏れてしまうという恐れがある。なお、サービスプロバイダは事業の特性上ユーザのプライバシーに関する情報を取得・管理することが前提となるため、サービスプロバイダにユーザのプライバシー情報が知られることは考慮しないこととする。
【０００６】
ユーザのプライバシーが第三者に漏えいしないような位置情報提供の仕組みとして、Target tracking（非特許文献１）とPseudonym change（非特許文献２）が知られている。Target tracking（非特許文献１）は、位置情報提供装置８００おいて、ユーザを特定する情報（ユーザに関する情報やＩＤ）を対応付けずに、位置情報（及び／または位置情報を取得した時刻）のみをコンテンツ提供装置９００に送信する仕組みである。ユーザを特定する情報を一切使わないため、長い時間区間の情報を集めてもユーザの行動経路を特定することは難しい。
【０００７】
Pseudonym change（非特許文献２）は、位置情報提供装置８００において、各ユーザ端末に対して複数の仮名の集合を割り当てておき、ユーザ端末から取得したＩＤを当該ユーザに割り当てられた仮名の集合のうちいずれか一つの仮名に変換してユーザに関する情報を作成し、コンテンツ提供装置９００に送信する仕組みである。つまり、時刻ごとに同じユーザに対して割り当てる仮名が（予め決められた集合の範囲内で）変化する。そのため、各ユーザに対応する仮名の集合を知らない第三者は、ユーザの行動経路を特定することが難しい。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】M. Gruteser and B. Hoh, “On the Anonymity of Periodic Location Samples”, SPC'05 Proceedings of the Second international conference on Security in Pervasive Computing, Pages 179-192.
【非特許文献２】G. Callandriello, P. Papadimitratos, J.-P. Hubaux and A. Lioy, Efficient and Robust Pseudonymous “Authentication in VANET”, ACM INTERNATIONAL WORKSHOP ON VEHICULAR AD HOC NETWORKS, 2007, Pages 19-28.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献１の技術は、ユーザを特定する情報が一切分からないため、各データ取得時間でのユーザの分布は分かるが、どのユーザがどの方向に動いたのかは分からない。したがって、取得したデータからでは、同じ時刻に同じ方向に向かって道路を進んでいるユーザがどのくらいいるか（道路の混雑状況）といった情報を解析することができない。つまり、コンテンツプロバイダが所望のサービスを提供することができないという課題がある。
【００１０】
非特許文献２の技術は、短時間区間では同じ仮名を用い、時間区間単位で使用する仮名を切り替えるようにすれば、取得したデータから同じ時刻に同じ方向に向かって道路を進んでいるユーザがどのくらいいるかを解析することも可能である。しかし、各ユーザに割り当てられる仮名は複数あるものの、他のユーザと重複しないように割り当てられる（つまり、一意性がある）ので、このことを利用すれば特定のユーザの行動経路を特定することは可能であり、ユーザの行動経路（プライバシーに関する情報）が第三者に漏えいするという課題は解決できていない。そして、この課題は、ユーザ端末−位置情報提供装置間や、位置情報提供装置−コンテンツ提供装置間の情報のやりとりの仕組みで解決せざるを得ないので、情報のやりとりの仕組みを複雑にせざるを得ない。
【００１１】
本発明は、各時刻において仮名と位置と時刻の組からなる情報（仮名位置情報）をコンテンツプロバイダに提供する構成（コンテンツプロバイダが所望のサービスを提供することができる構成）を維持し、かつ、長時間の情報を集めたとしても、ユーザの行動経路を第三者が推定できないようにできる位置情報提供装置を実現することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の位置情報提供装置は、位置情報取得部、仮名変換部、記録部を備える。位置情報取得部は、複数のユーザ端末のそれぞれから、ユーザ端末を特定する情報、ユーザ端末の位置を示す情報、位置を示す情報を取得した時刻を示す情報を含む特定位置情報を取得する。仮名変換部は、特定位置情報の中のユーザ端末を特定する情報を仮名に変更し、仮名、ユーザ端末の位置を示す情報、位置を示す情報を取得した時刻を示す情報を含む仮名位置情報を出力する。また、仮名変換部は、２つ以上のユーザ端末が、位置を示す情報を取得した時刻の差が所定の時間範囲内であって位置の差が所定の位置範囲内であることを交換条件とし、交換条件を満たす２つ以上のユーザ端末があるときに、所定の確率で仮名を交換する。記録部は、位置を示す情報を取得した時刻ごとに、ユーザ端末を特定する情報と仮名の対応関係を記録する。
【００１３】
本発明の安全度評価装置は、本発明の位置情報提供装置が出力した仮名位置情報のプライバシー安全度を評価する。安全度評価装置によってプライバシー安全度を評価するときには、位置情報提供装置の仮名変換部は、交換条件を満たす２つ以上のユーザ端末があるときに、記録部に交換条件を満たすユーザ端末に対応する仮名も記録しておく。安全度評価装置は、仮名交換モデル抽出部、可能経路計算部、プライバシー安全度出力部を備える。仮名交換モデル抽出部は、初期状態の可能経路モデルを生成し、記録部に記録された交換条件を満たすユーザ端末に対応する仮名から仮名交換系列を生成する。可能経路計算部は、可能経路モデルを、仮名交換系列を制約条件として更新する。プライバシー安全度出力部は、更新された可能経路モデルから、交換条件を満たす時刻の直後ごとに各仮名が割り付けられる可能性のあるユーザ端末の数を計算し、プライバシー安全度として出力する。ここで、可能経路モデルは、最初に位置を示す情報を取得した時刻での各仮名と対応するユーザ端末を特定する情報、最後に交換条件を満たす時刻の後に各仮名と対応するユーザ端末を特定する情報、および最後以外の前記交換条件を満たす時刻の後ごとに各仮名と対応する可能性のあるユーザ端末を特定する情報とが関連付けられたモデルである。また、仮名交換系列は、交換条件を満たす時刻ごとに、交換される可能性のある複数の仮名が列挙された系列である。
【発明の効果】
【００１４】
本発明の位置情報提供装置によれば、仮名をユーザ端末間で交換する仕組みなので、非特許文献２のように、仮名は特定のユーザ端末にのみ割り当てられるものではない。したがって、仮名とユーザ端末との対応関係は分からないようにできる。よって、非特許文献２のようにユーザ端末−位置情報提供装置間や、位置情報提供装置−コンテンツ提供装置間の情報のやりとりの仕組みで解決しなくても、各時刻においては仮名と位置と時刻の組からなる情報（仮名位置情報）をコンテンツプロバイダに提供する構成を維持し、かつ、長時間の情報を集めたとしても、ユーザの行動経路を第三者が推定できないようにできる。
【図面の簡単な説明】
【００１５】
【図１】従来の全体構成を示す図。
【図２】本発明の位置情報提供装置を含んだシステム構成を示す図。
【図３】本発明の原理を説明するための図。
【図４】本発明の位置情報提供装置の仮名初期化時の処理フローを示す図。
【図５】本発明の位置情報提供装置の位置情報提供時の処理フローを示す図。
【図６】３つの仮名に対応するユーザ端末が変わる例を示す図。
【図７】本発明の安全度評価装置、安全度評価装置を含んだ位置情報提供システムの構成例を示す図。
【図８】本発明の安全度評価装置の処理フローを示す図。
【図９】図６（Ａ）の場合の初期状態の可能経路モデルの例を示す図。
【図１０】図６の場合の仮名交換系列の例を示す図。
【図１１】図９に示した可能経路モデルを更新した例を示す図。
【図１２】図６（Ａ）に示されたように仮名が交換された場合のプライバシー安全度を示す図。
【図１３】図６（Ｂ），（Ｃ）に示されたように仮名が交換された場合の可能経路モデルを示す図。
【図１４】図６（Ｂ），（Ｃ）に示されたように仮名が交換された場合のプライバシー安全度を示す図。
【図１５】別の例での仮名交換の遷移、初期状態の可能経路モデル、仮名交換系列を示す図。
【図１６】図１５に示された例の場合の更新後の可能経路モデルを示す図。
【図１７】図１５に示された例の場合のプライバシー安全度を示す図。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１７】
図２に本発明の位置情報提供装置を含んだシステム構成を示す。位置情報提供装置１００には、Ｋ個のユーザ端末７００１，…，７００Ｋとコンテンツ提供装置９００がネットワーク経由で接続されている。ただし、Ｋは２以上の整数、ｋは１以上Ｋ以下の整数である。従来と同じように、位置情報提供装置１００は、サービスプロバイダのような事業の特性上ユーザのプライバシーに関する情報を取得・管理する事業者が運用し、コンテンツ提供装置９００は、ユーザのプライバシーに関する情報までは知らされない事業者が運用することを前提とする。
【００１８】
＜原理＞
図３は、本発明の原理を説明するための図である。図３には、時刻τ０〜τ３（τ０＜τ１＜τ２＜τ３）においてユーザ端末７００１がａ→ｂ→ｃ→ｄと移動しユーザ端末７００２がｆ→ｅ→ｃ→ｇと移動した場合の時刻ごとの位置が二次元平面で示されている。時刻τ０において例えば、ユーザ端末７００１には仮名ｐ１が対応つけられ、ユーザ端末７００２には仮名ｐ２が対応つけられているとする。そして、時刻ｔ２においてユーザ端末７００１とユーザ端末７００２は同じ位置に居合わせているので、位置情報提供装置１００は、あらかじめ定めた確率で時刻τ２のときに仮名を交換する。したがって、仮名と位置と時刻の組からなる情報（仮名位置情報）だけでは、時刻τ３のときに位置ｄに存在するユーザ端末がユーザ端末７００１かユーザ端末７００２か分からない状態にできる。
【００１９】
＜仮名初期化＞
位置情報提供装置１００は、仮名初期化部１９０、位置情報取得部１１０、仮名変換部１２０、記録部１５０を備える。図４は本発明の位置情報提供装置の仮名初期化時の処理フローを示す図である。仮名初期化部１９０は、ユーザ端末７００ｋから利用申請を示す情報を受け取り（Ｓ７９０）、ユーザ端末７００ｋに仮名を割り当て、仮名とユーザ端末７００ｋを特定する情報とを対応付けて記録部１５０に記憶する（Ｓ１９０）。例えば、ユーザ端末７００１を特定する情報をｕ１とし、割り当てられる仮名の初期値（位置情報取得の開始時刻Ｔ１であって、最初に位置を示す情報を取得する時刻τ０における仮名）をｐ１＝Ｎ０（ｕ１）とする。
【００２０】
＜位置情報提供時の各構成部の概要＞
次に位置情報提供時の各構成部の処理の概要を説明する。以下の説明で用いるτｎ（ｕｋ）は、最初に位置を示す情報を取得した時（τ０の時）を除いて、ｎ回目のユーザ端末７００ｋの位置を示す情報を取得した時刻を示している。Ｐｎ（ｕｋ）は、時刻τｎ（ｕｋ）のユーザ端末７００ｋの位置を示す情報である。Ｎｎ（ｕｋ）は、時刻τｎ（ｕｋ）の処理によってユーザ端末７００ｋに割り当てられる仮名である。
【００２１】
位置情報取得部１１０は、それぞれのユーザ端末７００ｋから、ユーザ端末を特定する情報ｕｋ、ユーザ端末の位置を示す情報Ｐｎ（ｕｋ）、位置を示す情報を取得した時刻を示す情報τｎ（ｕｋ）を含む特定位置情報を取得する。
【００２２】
仮名変換部１２０は、特定位置情報の中のユーザ端末７００ｋを特定する情報ｕｋを仮名Ｎｎ（ｕｋ）に変更し、仮名Ｎｎ（ｕｋ）、ユーザ端末７００ｋの位置を示す情報Ｐｎ（ｕｋ）、位置を示す情報を取得した時刻を示す情報τｎ（ｕｋ）を含む仮名位置情報を出力する。なお、仮名変換部１２０は、２つ以上のユーザ端末が、位置を示す情報を取得した時刻の差が所定の時間範囲内であって位置の差が所定の位置範囲内であることを交換条件とし、交換条件を満たす２つ以上のユーザ端末があるときに、所定の確率で仮名を交換する。また、出力された仮名位置情報は、リアルタイムでコンテンツ提供装置９００に送信してもよいし、所定時間分蓄積したのちに送信してもよいし、位置を示す情報の取得がすべて終了してからまとめて送信してもよい。記録部１５０は、位置を示す情報を取得した時刻ごとに、ユーザ端末を特定する情報ｕｋと仮名Ｎｎ（ｕｋ）の対応関係を記録する。
【００２３】
＜位置情報提供時の詳細＞
図５は位置情報提供時の処理をより詳細に示したフローを示す図である。より詳細に位置情報提供時の処理について説明すると以下のようになる。位置を示す情報を取得する開始時間を時刻Ｔ１、終了時刻を時刻Ｔ２とする。
【００２４】
位置情報取得部１１０は、開始時刻Ｔ１（＝τ０）に、ｋ＝１〜Ｋのそれぞれのユーザ端末７００ｋから、ユーザ端末を特定する情報ｕｋ、ユーザ端末の位置を示す情報Ｐ０（ｕｋ）、位置を示す情報を取得した時刻を示す情報τ０（ｕｋ）を含む特定位置情報を取得する（Ｓ１１１）。仮名変換部１２０は、特定位置情報の中のユーザ端末７００ｋを特定する情報ｕｋを仮名Ｎ０（ｕｋ）に変更し、仮名Ｎ０（ｕｋ）、ユーザ端末７００ｋの位置を示す情報Ｐ０（ｕｋ）、位置を示す情報を取得した時刻を示す情報τ０（ｕｋ）を含む仮名位置情報を出力する（Ｓ１２１）。
【００２５】
位置情報取得部１１０は、あらかじめ定めた測定条件に従って、時刻τｎ（ｕｋ）に、ユーザ端末７００ｋから、ユーザ端末を特定する情報ｕｋ、ユーザ端末の位置を示す情報Ｐｎ（ｕｋ）、位置を示す情報を取得した時刻を示す情報τｎ（ｕｋ）を含む特定位置情報を取得する（Ｓ１１２）。仮名変換部１２０は、２つ以上のユーザ端末が、位置を示す情報を取得した時刻の差が所定の時間範囲内であって位置の差が所定の位置範囲内であることを交換条件とし、この交換条件を満たすユーザ端末が２つ以上あるかを確認する（Ｓ１２２）。なお、「位置を示す情報を取得した時刻の差が所定の時間範囲内」、「位置の差が所定の位置範囲内」とは、時間も位置も完全に一致することは難しい（ありえない）ため、実際には同一として取り扱える範囲を定めて処理することを意味している。なお、具体的な範囲は、測定する時間間隔やユーザ端末が移動する速さ、後述するプライバシー安全度の確保などの観点から適宜定めればよい。
【００２６】
ステップＳ１２２がＹｅｓのとき、所定の確率で仮名を交換する（Ｓ１２３）。Ｎｏのときは仮名は交換しない。仮名変換部１２０は、ステップＳ１２２，Ｓ１２３の結果として、仮名Ｎｎ（ｕｋ）、ユーザ端末７００ｋの位置を示す情報Ｐｎ（ｕｋ）、位置を示す情報を取得した時刻を示す情報τｎ（ｕｋ）を含む仮名位置情報を出力する（Ｓ１２４）。
【００２７】
位置情報提供装置１００は、終了時刻Ｔ２を過ぎたかを確認する（Ｓ１０１）。ステップＳ１０１がＹｅｓの場合、処理を終了する。Ｎｏの場合、あらかじめ定めた次のタイミングでステップＳ１１２を実行する。
【００２８】
＜仮名交換の具体例１＞
図６に、３つの仮名に対応するユーザ端末が変わる例を示す。図６では、３つのユーザ端末（３つのユーザ端末を特定する情報をｕ１，ｕ２，ｕ３とする）の間で３つの仮名（３つの仮名をｐ１，ｐ２，ｐ３とする）を交換する様子を示している。図６の横の線は時刻を、縦の線は仮名ｐ１，ｐ２，ｐ３を示しており、矢印の付いた太線は、開始時刻Ｔ１から終了時刻Ｔ２までの仮名に対応するユーザ端末を特定する情報の変遷を示している。この図に示した例では、時刻ｔ１では仮名ｐ１，ｐ２に対応するユーザ端末同士が交換条件を満たし、時刻ｔ２では仮名ｐ２，ｐ３に対応するユーザ端末同士が交換条件を満たし、時刻ｔ３では仮名ｐ１，ｐ３に対応するユーザ端末同士が交換条件を満たしている。なお、この例では、２つの端末が交換条件を満たす例を示しているが、３つ以上の端末が同時に交換条件を満たしてもよい。なお、時刻ｔ１，ｔ２，ｔ３は、複数のユーザ端末において「位置を示す情報を取得した時刻の差が所定の時間範囲内」の場合の時刻なので、どの時間範囲かが区別できるように表現された時刻にすればよい。
【００２９】
図６（Ａ）は、交換条件を満たした時刻ｔ１，ｔ２，ｔ３のいずれのタイミングでも仮名が交換されなかった例を示している。図６（Ｂ）は、時刻ｔ２のタイミングの時だけ仮名が交換された例を示している。また、図６（Ｃ）は、時刻ｔ１，ｔ２，ｔ３のすべてのタイミングで仮名が交換された例を示している。例えば、図６（Ｂ）と図６（Ｃ）は、開始時刻のユーザ端末を特定する情報と仮名の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ２），（ｕ３，ｐ３）であり、終了時刻の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ３），（ｕ３，ｐ２）であり、共通する。したがって、開始時刻Ｔ１と終了時刻Ｔ２での仮名の対応関係がわかったとしても、図６（Ｂ）のように仮名が変遷したのか、図６（Ｃ）のように仮名が変遷したのかは分からない。
【００３０】
原理の説明で示したが、本発明の位置情報提供装置によれば、仮名をユーザ端末間で交換する仕組みなので、非特許文献２のように、仮名は特定のユーザ端末にのみ割り当てられるものではない。したがって、仮名とユーザ端末との対応関係は分からないようにできる。よって、非特許文献２のようにユーザ端末−位置情報提供装置間や、位置情報提供装置−コンテンツ提供装置間の情報のやりとりの仕組みで解決しなくても、各時刻においては仮名と位置と時刻の組からなる情報（仮名位置情報）をコンテンツプロバイダに提供する構成を維持し、かつ、長時間の情報を集めたとしても、ユーザの行動経路を第三者が推定できないようにできる。
【実施例２】
【００３１】
実施例２で説明する安全度評価装置は、実施例１で示した位置情報提供装置が出力した仮名位置情報のプライバシー安全度を評価する。図７に本発明の安全度評価装置、安全度評価装置を含んだ位置情報提供システムの構成例を示す。図８に本発明の安全度評価装置の処理フローを示す。位置情報提供システム１０は、位置情報提供装置１００と安全度評価装置２００を含んで構成されており、１つのハードウェアで実現してもよいし、複数のハードウェアに分けて実現してもよい。安全度評価装置２００は、仮名交換モデル抽出部２１０、可能経路計算部２２０、プライバシー安全度出力部２６０を備える。
【００３２】
本実施例では、位置情報提供装置１００は、プライバシー安全度を評価できるようにしておくために、仮名変換部１２０が、交換条件を満たす２つ以上のユーザ端末があるときには、記録部１５０に交換条件を満たすユーザ端末に対応する仮名も記録しておく。例えば、時刻ｔ１の処理において、仮名ｐ１とｐ２に対応するユーザ端末が交換条件を満たしたときには（ステップＳ１２２がＹｅｓのときには）、ステップＳ１２３において、仮名変換部１２０はｔ１と｛ｐ１，ｐ２｝を関連付けて記録部１５０に記録する処理も行っておく。
【００３３】
＜仮名交換モデル抽出部＞
仮名交換モデル抽出部２１０は、初期状態の可能経路モデルを生成し、記録部１５０に記録された交換条件を満たすユーザ端末に対応する仮名から仮名交換系列を生成する（Ｓ２１０）。ここで、初期状態の可能経路モデルは、最初に位置を示す情報を取得した時刻での各仮名と対応するユーザ端末を特定する情報、最後に交換条件を満たす時刻の後に各仮名と対応するユーザ端末を特定する情報（言い換えると、終了時刻に各仮名と対応するユーザ端末を特定する情報）、および最後以外の交換条件を満たす時刻の直後ごとに少なくとも各仮名と対応する可能性のあるユーザ端末を特定する情報を含んだモデルである。なお、「直後」とは、交換条件を満たす時刻の処理が終了した後であって、次に位置を示す情報を取得する時刻までを意味している。仮名交換系列は、交換条件を満たす時刻ごとに、交換される可能性のある複数の仮名が列挙された系列である。また、「少なくとも各仮名と対応する可能性のあるユーザ端末を特定する情報を含んだ」とは、初期状態の可能経路モデルの最後以外の交換条件を満たす時刻の直後には、実際には各仮名に対応する可能性のないユーザ端末を特定する情報を含んでいてもかまわないことを示している。これらの情報は、後述の更新の処理によって除去されるからである。
【００３４】
＜可能経路モデルと仮名交換系列の生成＞
次に、例を用いて初期状態の可能経路モデルと仮名交換系列の生成について説明する。図９に初期状態の可能経路モデルの例を、図１０に仮名交換系列の例を示す。なお、図９と図１０は、図６（Ａ）に示されたように仮名が交換された場合の初期状態の可能経路モデルと仮名交換系列を示している。
【００３５】
図９の左端の列は、開始時刻と交換条件を満たした時刻を示している。図９の左から２列目から４列目のそれぞれの列は、各時刻の直後に各仮名が割り当てられる可能性のあるユーザ端末を特定する情報を示している。なお、位置情報提供の開始時刻が朝であり、終了時刻が夜の場合、ユーザ端末は同じ位置（自宅）の可能性が高いので、開始時刻と終了時刻の仮名が異なっていたとしても、ユーザ端末は同じである可能性が高いことがコンテンツ提供装置で把握できてしまう。そこで、この例では、プライバシー安全度を、開始時刻と終了時刻の仮名が割り当てられたユーザ端末は第三者も分かっている前提で評価する。したがって、図９の開始時刻直後を示す行と、最後に交換条件を満たした時刻の直後を示す行では、割り当てられた結果を示している。その他の行は、初期状態の設定なので、すべてのユーザ端末を特定する情報が割り当てられる可能性があると設定しておけばよい。なお、実施例１に示したように記録部１５０は、位置を示す情報を取得した時刻ごとに、ユーザ端末を特定する情報ｕｋと仮名Ｎｎ（ｕｋ）の対応関係を記録しているので、開始時刻と終了時刻の対応関係は、記録部１５０の情報から分かる。
【００３６】
図１０の左側の列は、交換条件を満たした時刻を示している。右側の列は、各時刻に交換条件を満たしたユーザ端末同士に割り当てられていた仮名が示されている。前述のように仮名変換部１２０が記録部１５０に記録しているので、仮名交換系列の生成に必要な情報は、記録部１５０から取得すればよい。
【００３７】
＜可能経路計算部＞
可能経路計算部２２０は、可能経路モデルを、仮名交換系列を制約条件として更新する（Ｓ２２０）。より具体的には、以下のようにすればよい。可能経路計算部２２０は、順方向可能経路計算部２３０、逆方向可能経路計算部２４０、反復制御部２５０を備える。
【００３８】
順方向可能経路計算部２３０は、交換条件を満たす時刻が早い方から順番に、可能経路モデルの交換条件を満たす時刻の直前の各仮名と対応する可能性のあるユーザ端末を特定する情報から、可能経路モデルの交換条件を満たす時刻の直後の各仮名と対応する可能性のあるユーザ端末を特定する情報を、仮名交換系列にしたがって限定することで、可能経路モデルを更新する（Ｓ２３０）。なお、「直前」とは、前回位置を示す情報を取得した時刻から交換条件を満たす時刻の処理を行うまでを意味している。また、「直後」とは、前述のとおり、交換条件を満たす時刻の処理が終了した後であって、次に位置を示す情報を取得する時刻までを意味している。
【００３９】
逆方向可能経路計算部２４０は、交換条件を満たす時刻が遅い方から順番に、可能経路モデルの交換条件を満たす時刻の直後の各仮名と対応する可能性のあるユーザ端末を特定する情報から、可能経路モデルの交換条件を満たす時刻の直前の各仮名と対応する可能性のあるユーザ端末を特定する情報を、仮名交換系列にしたがって限定することで、可能経路モデルを更新する（Ｓ２４０）。
【００４０】
反復制御部２５０は、順方向可能経路計算部２３０による更新と逆方向可能経路計算部２４０による更新を、可能経路モデルが変化しなくなるまで交互に繰り返す（Ｓ２５１，Ｓ２５２）。より具体的には、反復制御部２５０は、必ず順方向可能経路計算部２３０の処理を先に行う。そして、得られた更新後の可能経路モデルが更新前の可能経路モデルと同じであれば可能経路計算ステップ（Ｓ２２０）の処理を終了する（Ｓ２５１）。また、異なる場合は、逆方向可能経路計算部２４０の処理を行う。そして、得られた更新後の可能経路モデルが更新前の可能経路モデルと同じであれば可能経路計算ステップ（Ｓ２２０）の処理を終了する（Ｓ２５２）。
【００４１】
＜可能経路モデルの更新＞
次に、例を示しながら、可能経路モデルの更新について説明する。ここでは、ｓ回目の更新後の可能経路モデルにおいて、時刻ｔｉで仮名ｐｋに対応するユーザ端末を特定する情報の集合をＡｓ（ｔｉ，ｐｋ）とする。なお、ｔ０＝τ０とし、時刻τ０における各仮名に対応するユーザ端末を特定する情報と、最後に交換条件を満たした後の各仮名に対応するユーザ端末を特定する情報は更新されない。
【００４２】
順方向可能経路計算部２３０は、次の処理を行えばよい。
（１）まず、Ａｓ（ｔｉ−１，ｐｋ）の制約条件を満たすように、各仮名ｐｋ（ｋ＝１，・・・，Ｋ）について相異なるユーザ端末を特定する情報を１つずつ選択する。可能な全ての組み合わせを求めて、「交換前組み合わせリスト」を作成する。
（２）次に、上記で求めた交換前組み合わせリスト中の各組み合わせについて、仮名交換系列が示す時刻ｔｉにおいて交換可能な仮名を交換した「交換後組み合わせリスト」を作成する。
（３）得られた「交換後組み合わせリスト」中の各組み合わせが、Ａｓ−１（ｔｉ，ｐｋ）の制約条件を満たすか否かを判定する。制約条件を満たす組み合わせのみを残し、制約条件を満たさない組み合わせを除いて、交換後組み合わせリストを更新する。
（４）交換前組み合わせリストと更新後の交換後組み合わせリストを合わせた組み合わせリストにより、可能経路モデルを更新する。
【００４３】
逆方向可能経路計算部２４０は、次の処理を行えばよい。
（１）まず、Ａｓ（ｔｉ＋１，ｐｋ）の制約条件を満たすように、各仮名ｐｋ（ｋ＝１，・・・，Ｋ）について相異なるユーザ端末を特定する情報を１つずつ選択する。可能な全ての組み合わせを求めて、「交換前組み合わせリスト」を作成する。
（２）次に、上記で求めた交換前組み合わせリスト中の各組み合わせについて、仮名交換系列が示す時刻ｔｉにおいて交換可能な仮名を交換した「交換後組み合わせリスト」を作成する。
（３）得られた「交換後組み合わせリスト」中の各組み合わせが、Ａｓ−１（ｔｉ，ｐｋ）の制約条件を満たすか否かを判定する。制約条件を満たす組み合わせのみを残し、制約条件を満たさない組み合わせを除いて、交換後組み合わせリストを更新する。
（４）交換前組み合わせリストと更新後の交換後組み合わせリストを合わせた組み合わせリストにより、可能経路モデルを更新する。
【００４４】
＜可能経路モデルの更新の具体例１＞
図１１に図９に示した可能経路モデルを更新した例を示す。図１１（Ａ）は順方向可能経路計算部２３０による更新後を示しており、図１１（Ｂ）は逆方向可能経路計算部２４０による更新後を示している。以下では、図１１のように更新されることを説明する。
【００４５】
順方向可能経路計算部２３０は、交換条件を満たす時刻が早い方から順番に処理を行うので、まず時刻ｔ１の行に対して次の処理を行う。
（１）図９に示されている可能経路モデルで、各仮名についてＡ１（ｔ０，ｐｊ）で取りうるＩＤは１種類ずつしかないので、可能な組み合わせは（ｕ１，ｕ２，ｕ３）のみである。ここで、各組み合わせ（（）内で括られたユーザ端末を特定する情報の集合）において、第１要素、第２要素、第３要素の順に仮名ｐ１，ｐ２，ｐ３にそれぞれ対応するユーザ端末を特定する情報を表す。よって、交換前組み合わせリストは、
（（ｕ１，ｕ２，ｕ３））
である。
（２）時刻ｔ１において交換可能な仮名は｛ｐ１，ｐ２｝なので、交換後組み合わせリストは、
（（ｕ２，ｕ１，ｕ３））
である。
（３）「交換後組み合わせリスト」中の各組み合わせが、Ａ０（ｔ１，ｐｊ）の制約条件を満たすか否かを判定する。ここでは、
ｐ１に対応するユーザ端末を特定する情報：
ｕ２  ∈Ａ０（ｔ１，ｐ１）＝｛ｕ１，ｕ２，ｕ３｝
ｐ２に対応するユーザ端末を特定する情報：
ｕ１  ∈Ａ０（ｔ１，ｐ２）＝｛ｕ１，ｕ２，ｕ３｝
ｐ３に対応するユーザ端末を特定する情報：
ｕ３  ∈Ａ０（ｔ１，ｐ３）＝｛ｕ１，ｕ２，ｕ３｝
なので、制約条件を満たす。よって、交換後組み合わせリストは変化しない。
（４）以上の処理により、交換前組み合わせリストと更新後の交換後組み合わせリストの和である組み合わせリストは、
（（ｕ１，ｕ２，ｕ３），（ｕ２，ｕ１，ｕ３））
である。よって、仮名ｐ１に対応するユーザ端末を特定する情報の集合を｛ｕ１，ｕ２｝、仮名ｐ２に対応するユーザ端末を特定する情報の集合を｛ｕ１，ｕ２｝、仮名ｐ３に対応するユーザ端末を特定する情報の集合を｛ｕ３｝に更新する。
【００４６】
そして、時刻ｔ２の行に対して次の処理を行う。
（１）上記の処理により、Ａ１（ｔ１，ｐ１）＝｛ｕ１，ｕ２｝，Ａ１（ｔ１，ｐ２）＝｛ｕ１，ｕ２｝，Ａ１（ｔ１，ｐ３）＝｛ｕ３｝である。よって、更新前組み合わせリストは、
（（ｕ１，ｕ２，ｕ３），（ｕ２，ｕ１，ｕ３））
である。
（２）時刻ｔ２において交換可能な仮名は｛ｐ２，ｐ３｝なので、交換後組み合わせリストは、
（（ｕ１，ｕ３，ｕ２），（ｕ２，ｕ３，ｕ１））
である。
（３）「交換後組み合わせリスト」中の各組み合わせが、Ａ０（ｔ２，ｐｊ）の制約条件を満たすか否かを判定する。ここでは、
ｐ１に対応するユーザ端末を特定する情報：
ｕ１  ∈Ａ０（ｔ２，ｐ１）＝｛ｕ１，ｕ２，ｕ３｝
ｕ２  ∈Ａ０（ｔ２，ｐ１）＝｛ｕ１，ｕ２，ｕ３｝
ｐ２に対応するユーザ端末を特定する情報：
ｕ３  ∈Ａ０（ｔ２，ｐ２）＝｛ｕ１，ｕ２，ｕ３｝
ｐ３に対応するユーザ端末を特定する情報：
ｕ２  ∈Ａ０（ｔ２，ｐ３）＝｛ｕ１，ｕ２，ｕ３｝
ｕ１  ∈Ａ０（ｔ２，ｐ３）＝｛ｕ１，ｕ２，ｕ３｝
なので、全て制約条件を満たす。よって、更新後の交換後組み合わせリストは、
（（ｕ１，ｕ３，ｕ２），（ｕ２，ｕ３，ｕ１））
である。
（４）交換前組み合わせリストと更新後の交換後組み合わせリストを合わせた組み合わせリストは、
（（ｕ１，ｕ２，ｕ３），（ｕ２，ｕ１，ｕ３），（ｕ１，ｕ３，ｕ２），（ｕ２，ｕ３，ｕ１））
である。よって、仮名ｐ１に対応するユーザ端末を特定する情報の集合を｛ｕ１，ｕ２｝、仮名ｐ２に対応するユーザ端末を特定する情報の集合を｛ｕ１，ｕ２，ｕ３｝、仮名ｐ３に対応するユーザ端末を特定する情報の集合を｛ｕ１，ｕ２，ｕ３｝に更新する。これらの処理によって、図１１（Ａ）に示された更新後の可能経路モデルが得られる。
【００４７】
図１１（Ａ）の可能経路モデルは図９の可能経路モデルと異なるので、反復制御部２５０は、逆方向可能経路計算部２４０の処理に進む。逆方向可能経路計算部２４０は、交換条件を満たす時刻が遅い方から順番に処理を行うので、まず時刻ｔ２の行に対して次の処理を行う。
（１）各仮名についてＡ２（ｔ３，ｐｊ）で取りうるユーザ端末を特定する情報は１種類ずつしかないので、可能な組み合わせは（ｕ１，ｕ２，ｕ３）のみである。よって、交換前組み合わせリストは、
（（ｕ１，ｕ２，ｕ３））
である。
（２）時刻ｔ３において交換可能な仮名は｛ｐ１，ｐ３｝なので、交換後組み合わせリストは、
（（ｕ３，ｕ２，ｕ１））
である。
（３）「交換後組み合わせリスト」中の各組み合わせが、Ａ１（ｔ２，ｐｊ）の制約条件を満たすか否かを判定する。ここでは、
ｐ１に対応するユーザ端末を特定する情報：
【００４８】
【数１】
2014092978.tif 000003
【００４９】
であることから、交換後組み合わせリスト中の（ｕ３，ｕ２，ｕ１）は制約条件を満たさない。よって、更新後の交換後組み合わせリストは空のリストとなる。
（４）以上の処理により、交換前組み合わせリストと更新後の交換後組み合わせリストの和である組み合わせリストは、
（（ｕ１，ｕ２，ｕ３））
である。よって、仮名ｐ１に対応するユーザ端末を特定する情報の集合を｛ｕ１｝、仮名ｐ２に対応するユーザ端末を特定する情報の集合を｛ｕ１｝、仮名ｐ３に対応するユーザ端末を特定する情報の集合を｛ｕ３｝に更新する。
【００５０】
そして、時刻ｔ１の行に対して次の処理を行う。
（１）上記の処理により、Ａ２（ｔ２，ｐ１）＝｛ｕ１｝，Ａ２（ｔ２，ｐ２）＝｛ｕ２｝，Ａ２（ｔ２，ｐ３）＝｛ｕ３｝である。よって、更新前組み合わせリストは、
（（ｕ１，ｕ２，ｕ３））
である。
（２）時刻ｔ２において交換可能な仮名は｛ｐ２，ｐ３｝なので、交換後組み合わせリストは、
（（ｕ１，ｕ３，ｕ２））
である。
（３）「交換後組み合わせリスト」中の各組み合わせが、Ａ１（ｔ１，ｐｊ）の制約条件を満たすか否かを判定する。ここでは、
ｐ１に対応するユーザ端末を特定する情報：
ｕ１  ∈Ａ１（ｔ１，ｐ１）＝｛ｕ１，ｕ２｝
ｐ２に対応するユーザ端末を特定する情報：
【００５１】
【数２】
2014092978.tif 000004
【００５２】
なので、交換後組み合わせリスト中の（ｕ１，ｕ３，ｕ２）は制約条件を満たさない。よって、更新後の交換後組み合わせリストは空のリストとなる。
（４）交換前組み合わせリストと更新後の交換後組み合わせリストを合わせた組み合わせリストは、
（（ｕ１，ｕ２，ｕ３））
である。よって、仮名ｐ１に対応するユーザ端末を特定する情報の集合を｛ｕ１｝、仮名ｐ２に対応するユーザ端末を特定する情報の集合を｛ｕ２｝、仮名ｐ３に対応するユーザ端末を特定する情報の集合を｛ｕ３｝に更新する。
【００５３】
図１１（Ｂ）の可能経路モデルは図１１（Ａ）の可能経路モデルと異なるので、反復制御部２５０は、順方向可能経路計算部２３０の処理に戻る。戻った後の順方向可能経路計算部２３０の処理の詳細は省略するが、この処理で更新後の可能経路モデルは図１１（Ｂ）と同じとなる。したがって、反復制御部２５０は、可能経路計算ステップ（Ｓ２２０）の処理を終了し、ステップＳ２６０に進む。
【００５４】
＜プライバシー安全度出力部＞
プライバシー安全度出力部２６０は、更新された可能経路モデルから、交換条件を満たす時刻の直後ごとに各仮名が割り付けられる可能性のあるユーザ端末の数を計算し、プライバシー安全度として出力する。図１２は、図６（Ａ）に示されたように仮名が交換された場合のプライバシー安全度の出力である。図６（Ａ）の例の場合は、更新後の可能経路モデルが図１１（Ｂ）に示されたとおりであり、交換条件を満たす時刻の直後ごとに各仮名が割り付けられる可能性のあるユーザ端末の数はいずれも１である。したがって、図１２のようになる。つまり、ユーザの可能経路が一意に特定できてしまい安全性が低いことが分かる。
【００５５】
本発明の安全度評価装置によれば、このように位置情報提供装置が提供した仮名位置情報のプライバシー安全度を評価できる。したがって、設計者は、プライバシー安全度が低いときには、交換条件である「位置を示す情報を取得した時刻の差が所定の時間範囲内」、「位置の差が所定の位置範囲内」の範囲を広げて交換条件を満たしやすくし、プライバシー安全度を高めるよう設計変更できる。あるいは、安全度評価装置で評価したプライバシー安全度を各ユーザにフィードバックすることにより、各ユーザは各時刻において自分のプライバシーがどの程度安全であるか（自分の行動経路がどの程度第三者に解析されやすいか）を理解した上で、コンテンツプロバイダのサービスを利用するか否かを決断することができる。
【００５６】
＜可能経路モデルの更新の具体例２＞
次に、図６（Ｂ），（Ｃ）に示されたように仮名が交換された場合の可能経路モデルの更新とプライバシー安全度を示す。図１３は図６（Ｂ），（Ｃ）のときの可能経路モデルを示す図であり、図１４はこのときのプライバシー安全度を示す図である。図６（Ｂ），（Ｃ）のときは、開始時刻での仮名とユーザ端末を特定する情報の対応関係は（ｕ１，ｐ１），（ｕ２，ｐ２），（ｕ３，ｐ３）であり、終了時刻の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ３），（ｕ３，ｐ２）である。したがって、初期状態の可能経路モデルは図１３（Ａ）のようになる。なお、仮名交換系列は、図１０と同じである。
【００５７】
まず、前述のように順方向可能経路計算部２３０の処理（順方向可能経路計算ステップ（Ｓ２３０））を行うと、図１３（Ｂ）に示された更新後の可能経路モデルが得られる。そして、図１３（Ｂ）は図１３（Ａ）とは異なるので、逆方向可能経路計算部２４０の処理（逆方向可能経路計算ステップ（Ｓ２４０））が行われ、図１３（Ｃ）に示された更新後の可能経路モデルが得られる。図１３（Ｃ）は図１３（Ｂ）と異なるので、もう一度順方向可能経路計算部２３０の処理（順方向可能経路計算ステップ（Ｓ２３０））が行われる。このとき得られる更新後の可能経路モデルは図１３（Ｃ）と同じになるので、可能経路計算ステップ（Ｓ２２０）の処理は終了する。
【００５８】
そして、図１３（Ｃ）の可能経路モデルからプライバシー安全度が求められるので、プライバシー安全度は、図１４のようになる。つまり、開始時刻での仮名とユーザ端末を特定する情報の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ２），（ｕ３，ｐ３）であり、終了時刻の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ３），（ｕ３，ｐ２）であることだけが分かる第三者には、図６（Ｂ）のように仮名が交換されたのか、図６（Ｃ）のように仮名が交換されたのか分からない。
【００５９】
＜可能経路モデルの更新の具体例３＞
次に、別の仮名交換系列での例を示す。この例では、交換条件を満たした時刻を４回にする。図１５に、別の例での仮名交換の遷移、初期状態の可能経路モデル、仮名交換系列を示す。図１６に更新後の可能経路モデルを、図１７にプライバシー安全度を示す。
【００６０】
図１５（Ａ）は、仮名交換の遷移を示す図であり、図６に比べると仮名が割り当てられた遷移の具体例（矢印が付された太い実線）は省略されているが、開始時刻でも終了時刻でも仮名とユーザ端末を特定する情報の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ２），（ｕ３，ｐ３）であることが分かる。また、時刻ｔ１では仮名ｐ２，ｐ３に対応するユーザ端末同士が交換条件を満たし、時刻ｔ２では仮名ｐ１，ｐ２に対応するユーザ端末同士が交換条件を満たし、時刻ｔ３では仮名ｐ２，ｐ３に対応するユーザ端末同士が交換条件を満たし、時刻ｔ４では仮名ｐ１，ｐ３に対応するユーザ端末同士が交換条件を満たしている。図１５（Ｂ）は、初期状態の可能経路モデルを示している。なお、この例は、時刻ｔ２直後を示す行の仮名ｐ１、ｐ２には、ユーザ端末を特定する情報としてｕ４が対応するかもしれないという前提で生成した初期状態の可能経路モデルである。図１５（Ｃ）は、仮名交換系列を示している。
【００６１】
前述のように、まず順方向可能経路計算部２３０の処理（順方向可能経路計算ステップ（Ｓ２３０））を行うと、図１６（Ａ）に示された更新後の可能経路モデルが得られる。この時点で、時刻ｔ２直後を示す行の仮名ｐ１、ｐ２に示されていたｕ４が削除されている。このように、初期状態の可能経路モデルに、実際にはありえないユーザ端末を特定する情報が加わっていたとしても更新の処理を行うことで除去される。そして、図１６（Ａ）は図１５（Ａ）とは異なるので、逆方向可能経路計算部２４０の処理（逆方向可能経路計算ステップ（Ｓ２４０））が行われ、図１６（Ｂ）に示された更新後の可能経路モデルが得られる。図１６（Ｂ）は図１６（Ａ）と異なるので、もう一度順方向可能経路計算部２３０の処理（順方向可能経路計算ステップ（Ｓ２３０））が行われる。このとき得られる更新後の可能経路モデルは図１６（Ｂ）と同じになるので、可能経路計算ステップ（Ｓ２２０）の処理は終了する。
【００６２】
そして、図１６（Ｂ）の可能経路モデルからプライバシー安全度が求められるので、プライバシー安全度は、図１７のようになる。つまり、開始時刻での仮名とユーザ端末を特定する情報の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ２），（ｕ３，ｐ３）であり、終了時刻の対応関係が（ｕ１，ｐ１），（ｕ２，ｐ２），（ｕ３，ｐ３）であることだけが分かる第三者には、３つのユーザ端末の経路は分からない。
【００６３】
図６のように交換条件を満たした時刻が３回の場合よりも、図１５のように交換条件を満たした時刻が４回の方が、ユーザ端末の経路を秘匿しやすい。つまり、交換条件を満たす回数が多くなるように長い時間区間において位置を示す情報を集めた方が、ユーザ端末の経路を秘匿しやすい。したがって、本発明の位置情報提供装置であれば、各時刻においては仮名と位置を示す情報と時刻の組からなる情報をコンテンツプロバイダに提供する構成を維持しつつ、長い時間区間においてユーザ端末の位置を示す情報を集めたとしても、ユーザの行動経路を第三者に推定されることがないようにできる。
【００６４】
＜本発明によって生じる効果＞
本発明の位置情報提供装置により提供された仮名位置情報（仮名、位置を示す情報、時刻）を用いて、ユーザ全体でのこれらの情報を統計的に解析することで何らかの有益な情報を得られることも期待できる。各時刻における位置を示す情報は、実際のあるユーザのいずれかの情報が反映されており、隣り合う時刻において取りうる可能経路は、いずれかのユーザが取った真の経路である。例えば、図３の例でτ２からτ３の区間における可能経路ｃ→ｇ，ｃ→ｄは、ユーザ端末７００１、７００２のどちらのユーザの真の経路なのかは特定できないが、一方はユーザ端末７００１、他方はユーザ端末７００２が取った真の経路であることは分かる。つまり、ユーザのプライバシーを侵害することなく実際のユーザの行動を反映した有益な解析することも可能となる。
【００６５】
［プログラム、記録媒体］
前述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６６】
また、前述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、前述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７１】
１０  位置情報提供システム              １００、８００  位置情報提供装置
１１０  位置情報取得部                  １２０  仮名変換部
１５０  記録部                          １９０  仮名初期化部
２００  安全度評価装置                  ２１０  仮名交換モデル抽出部
２２０  可能経路計算部                  ２３０  順方向可能経路計算部
２４０  逆方向可能経路計算部            ２５０  反復制御部
２６０  プライバシー安全度出力部        ７００  ユーザ端末
９００  コンテンツ提供装置
【図１】
2014092978.tif 000005
【図２】
2014092978.tif 000006
【図３】
2014092978.tif 000007
【図４】
2014092978.tif 000008
【図５】
2014092978.tif 000009
【図６】
2014092978.tif 000010
【図７】
2014092978.tif 000011
【図８】
2014092978.tif 000012
【図９】
2014092978.tif 000013
【図１０】
2014092978.tif 000014
【図１１】
2014092978.tif 000015
【図１２】
2014092978.tif 000016
【図１３】
2014092978.tif 000017
【図１４】
2014092978.tif 000018
【図１５】
2014092978.tif 000019
【図１６】
2014092978.tif 000020
【図１７】
2014092978.tif 000021