(57)【特許請求の範囲】
【請求項１】
ユーザの軌跡データを収集する収集部と、
軌跡データに含まれる構成単位をノードとし、前記ノード間のリンクを、前記構成単位の遷移確率として定義した有向グラフを生成する生成部と、
前記遷移確率の少なくとも一部に、所定の規則に従ってノイズを入れ、ダミーとなる偽の値に変更する変更部と、を備える匿名化装置。
【請求項２】
前記生成部は、２つの地点間の移動ベクトルを前記ノードとして前記有向グラフを生成する請求項１に記載の匿名化装置。
【請求項３】
前記生成部は、地点を前記ノードとして前記有向グラフを生成する請求項１に記載の匿名化装置。
【請求項４】
前記変更部は、前記遷移確率が１のリンクを削除する請求項１から請求項３のいずれかに記載の匿名化装置。
【請求項５】
前記変更部は、前記遷移確率を、第１の閾値の範囲で増減させる請求項１から請求項４のいずれかに記載の匿名化装置。
【請求項６】
前記変更部は、前記遷移確率が第２の閾値以下のリンクを追加する請求項１から請求項５のいずれかに記載の匿名化装置。
【請求項７】
前記収集部は、同一の構成単位以降又は以前に連結されている構成単位が互いに入れ替えられた複数の軌跡データを収集する請求項１から請求項６のいずれかに記載の匿名化装置。
【請求項８】
コンピュータの制御部が、
ユーザの軌跡データを収集する収集ステップと、
軌跡データに含まれる構成単位をノードとし、前記ノード間のリンクを、前記構成単位の遷移確率として定義した有向グラフを生成する生成ステップと、
前記遷移確率の少なくとも一部に、所定の規則に従ってノイズを入れ、ダミーとなる偽の値に変更する変更ステップと、を実行する匿名化方法。
【請求項９】
請求項８に記載の匿名化方法の各ステップを前記コンピュータに実行させるための匿名化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、軌跡データの匿名化装置、匿名化方法及び匿名化プログラムに関する。
【背景技術】
【０００２】
従来、ユーザが徒歩や乗り物で移動した軌跡を、位置情報が連結された軌跡データとして表現し、検索等に利用することが提案されている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００４−１１８２９０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、ユーザから提供される軌跡データは、個人の行動履歴を表しているため、プライバシの観点から、個人が特定されないように匿名化されることが望ましい。
しかしながら、従来技術では、軌跡データの精度を落とすことにより匿名化されていたため、データの精度に起因して軌跡データの活用先が限定されていた。また、精度が低下したとしても、個人が特定される問題は依然として残っていた。
【０００５】
本発明は、活用できる情報量の減少を抑制しつつ、軌跡データを匿名化できる匿名化装置、匿名化方法及び匿名化プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る匿名化装置は、ユーザの軌跡データを収集する収集部と、軌跡データに含まれる構成単位をノードとし、前記ノード間のリンクを、前記構成単位の遷移確率として定義した有向グラフを生成する生成部と、前記遷移確率の少なくとも一部を、所定の規則に従って変更する変更部と、を備える。
【０００７】
前記構成単位は、２つの地点間の移動ベクトルであってもよい。
【０００８】
前記構成単位は、地点であってもよい。
【０００９】
前記変更部は、前記遷移確率が１のリンクを削除してもよい。
【００１０】
前記変更部は、前記遷移確率を、第１の閾値の範囲で増減させてもよい。
【００１１】
前記変更部は、前記遷移確率が第２の閾値以下のリンクを追加してもよい。
【００１２】
前記収集部は、同一の構成単位を有する複数の軌跡データについて、当該同一の構成単位以降又は以前に連結されている構成単位を互いに入れ替えて受け付けてもよい。
【００１３】
本発明に係る匿名化方法は、コンピュータの制御部が、ユーザの軌跡データを収集する収集ステップと、軌跡データに含まれる構成単位をノードとし、前記ノード間のリンクを、前記構成単位の遷移確率として定義した有向グラフを生成する生成ステップと、前記遷移確率の少なくとも一部を、所定の規則に従って変更する変更ステップと、を実行する。
【００１４】
本発明に係る匿名化プログラムは、前記匿名化方法の各ステップをコンピュータに実行させる。
【発明の効果】
【００１５】
本発明によれば、活用できる情報量の減少を抑制しつつ、軌跡データを匿名化できる。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係る匿名化装置の機能構成を示す図である。
【図２】実施形態に係る移動ベクトルの一例を示す図である。
【図３】実施形態に係る有向グラフの一例を示す図である。
【図４】実施形態に係る匿名化方法の第１の例を示す図である。
【図５】実施形態に係る匿名化方法の第２の例を示す図である。
【図６】実施形態に係る匿名化方法の第３の例を示す図である。
【図７】変形例に係る軌跡データ間での構成単位の入れ替えの一例を示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係る匿名化装置１の機能構成を示す図である。
匿名化装置１は、サーバ装置又はパーソナルコンピュータ等の情報処理装置（コンピュータ）であり、記憶部１０及び制御部２０の他、各種データの入出力デバイス等を備える。
【００１８】
記憶部１０は、ハードウェア群を匿名化装置１として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ＲＯＭ、ＲＡＭ、フラッシュメモリ又はハードディスク（ＨＤＤ）等であってよい。具体的には、記憶部１０は、本実施形態の各機能を制御部２０に実行させるプログラムを記憶する。
【００１９】
また、記憶部１０は、データ提供者であるユーザから提供される軌跡データを蓄積する。軌跡データは、例えば、ＧＰＳから得られる緯度経度情報、住所の一部、あるいは、駅、停留所又はサービスエリア等のランドマーク情報等からなる地点が連結された、地点間の移動順序を示すデータであり、複数ユーザの軌跡データが蓄積される。
【００２０】
制御部２０は、匿名化装置１の全体を制御する部分であり、記憶部１０に記憶された各種プログラムを適宜読み出して実行することにより、本実施形態における各種機能を実現している。制御部２０は、ＣＰＵであってよい。
また、制御部２０は、収集部２１と、生成部２２と、変更部２３とを備える。
【００２１】
収集部２１は、複数のユーザの軌跡データを、データ提供者から収集し、記憶部１０に記憶する。このとき、収集部２１は、地域、日付、時間帯、ユーザ属性（例えば、性別、年齢等）等の条件の指定を受け付け、これらの指定条件に合致する軌跡データを収集してよい。
【００２２】
生成部２２は、軌跡データに含まれる構成単位をノードとし、ノード間のリンクを、構成単位の遷移確率として定義した有向グラフを生成する。
ここで、グラフのノードとする構成単位は、個々の地点、又は２つの地点間の移動ベクトルである。以下、本実施形態では、移動ベクトルをノードとする場合を説明する。
【００２３】
図２は、本実施形態に係る移動ベクトルの一例を示す図である。
あるユーザが地点ａ、ｂ、ｃ、ｄ、ｅの順に移動したことを示す軌跡データが得られた場合、生成部２２は、この軌跡データ各地点間の移動を示すベクトル（ａ→ｂ、ｂ→ｃ、ｃ→ｄ、ｄ→ｅ）に分割し、これらのベクトルの連結として軌跡を表現する。
【００２４】
さらに、生成部２２は、複数の軌跡データから得られる同一のベクトルを１つのグループとして定義し、このグループをノードとする有向グラフを生成する。
ここで、有向グラフのリンクは、ベクトル間を遷移したユーザの人数又は延べ人数等で表される遷移の頻度に応じて遷移確率として定義される。
【００２５】
図３は、本実施形態に係る有向グラフの一例を示す図である。
グループＡ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆは、遷移確率が付与された有向リンクにより連結されている。
【００２６】
例えば、グループＡからグループＢに３名、グループＦに２名という遷移情報が軌跡データから得られた場合、遷移確率は、それぞれ「０．６」及び「０．４」と設定される。
このように、遷移確率によってノードが連結されることにより、人数情報が失われるので、弱い匿名化が実現される。
【００２７】
変更部２３は、有向グラフに設定されたノード間の遷移確率の少なくとも一部を、所定の規則に従って変更する。
所定の規則は、例えば、次の（１）〜（３）のいずれか又はその組み合わせが採用される。
【００２８】
（１）変更部２３は、遷移確率が１のリンクを削除する。
（２）変更部２３は、遷移確率を、第１の閾値の範囲で増減させる。
（３）変更部２３は、遷移確率が第２の閾値以下の偽のリンクを追加する。
【００２９】
図４は、本実施形態に係る匿名化方法の第１の例を示す図である。
グループＦからグループＥへの遷移確率が「１．０」であった場合、「ｂ→ｄ」から「ｄ→ａ」に必ず遷移することが把握されるため、変更部２３は、匿名化のために、このリンクを削除する。
【００３０】
図５は、本実施形態に係る匿名化方法の第２の例を示す図である。
グループＡからは、グループＢ又はグループＦへの遷移があり得る。変更部２３は、これらの遷移確率について、実際の値（「０．６」及び「０．４」）を所定量だけ増減して偽の値（例えば、双方「０．５」）とすることで、匿名化を行う。
【００３１】
図６は、本実施形態に係る匿名化方法の第３の例を示す図である。
グループＡからは、グループＢ又はグループＦへの遷移があり得る。変更部２３は、さらに、グループＡからグループＧへ所定の遷移確率で偽のリンクを追加することにより、匿名化を行う。なお、追加したリンクの元（グループＡ）から他のグループ（グループＢ及びグループＦ）へ遷移する遷移確率は、追加したリンクの遷移確率に応じて調整される。
【００３２】
以上のように、本実施形態によれば、匿名化装置１は、地点又は地点間の移動ベクトルをノードとし、軌跡データに基づくノード間の遷移確率を定義することにより、有向グラフを生成する。匿名化装置１は、この有向グラフにおける遷移確率に対して、軌跡情報の解析の問題にならない程度にノイズを入れて調整することにより、活用できる情報量の減少を抑制しつつ、軌跡データを匿名化できる。
この結果、匿名化装置１は、個々のユーザの移動履歴がトレースされることによるプライバシ侵害の虞を低減できる。
【００３３】
匿名化装置１は、有向グラフから遷移確率が１のリンクを削除する。したがって、匿名化装置１は、遷移の選択肢がない確定的な軌跡を除くことにより、ユーザの軌跡がトレースされる可能性を低減し、軌跡データを容易に匿名化できる。
【００３４】
匿名化装置１は、有向グラフにおける遷移確率を、第１の閾値の範囲で増減させる。したがって、匿名化装置１は、実際の遷移確率をダミーの値に調整することにより、ユーザの軌跡がトレースされる可能性を低減し、軌跡データを容易に匿名化できる。
【００３５】
匿名化装置１は、生成した有向グラフに対して、遷移確率が第２の閾値以下のリンクを追加する。したがって、匿名化装置１は、ダミーの軌跡情報を混ぜることにより、ユーザの軌跡がトレースされる可能性を低減し、軌跡データを容易に匿名化できる。
【００３６】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００３７】
収集部２１は、同一の構成単位（地点又は移動ベクトル）を有する複数ユーザそれぞれの軌跡データについて、この同一の構成単位以降又は以前に連結されている構成単位を互いに入れ替えて受け付けてもよい。
【００３８】
図７は、軌跡データ間での構成単位の入れ替えの一例を示す図である。
軌跡データ１（ａ→ｂ→ｃ→ｄ→ｅ）及び軌跡データ２（ｆ→ｂ→ｃ→ｇ→ｈ）は、共に構成単位である移動ベクトル「ｂ→ｃ」を有している。そこで、データ提供者は、この同一の移動ベクトル以降の軌跡を互いに入れ替え、それぞれ「ａ→ｂ→ｃ→ｇ→ｈ」及び「ｆ→ｂ→ｃ→ｄ→ｅ」として、匿名化装置１へ提供する。
【００３９】
このように、ユーザ間で軌跡データの一部を入れ替えたとしても、生成部２２により軌跡が細分化されるので、生成される有向グラフは変化しない。したがって、匿名化装置１は、データ利用者へ提供する出力を変えることなく、データ提供者から予め匿名化されたデータを受け取ることができるので、プライバシの保護をより良く保証できる。
【００４０】
前述の実施形態では、匿名化装置１は、複数ユーザの軌跡データを収集したが、これには限られず、同一ユーザの複数の軌跡データを収集して処理してもよい。
【００４１】
匿名化装置１による匿名化方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（匿名化装置１）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータ（匿名化装置１）に提供されてもよい。
【符号の説明】
【００４２】
１  匿名化装置
１０  記憶部
２０  制御部
２１  収集部
２２  生成部
２３  変更部
【図１】
0006450098.tif 000002
【図２】
0006450098.tif 000003
【図３】
0006450098.tif 000004
【図４】
0006450098.tif 000005
【図５】
0006450098.tif 000006
【図６】
0006450098.tif 000007
【図７】
0006450098.tif 000008