JP6588880B2

JP6588880B2 - 匿名化装置、匿名化方法、およびプログラム

Info

Publication number: JP6588880B2
Application number: JP2016194245A
Authority: JP
Inventors: 彰伍正木; 千田　浩司; 浩司千田; 長谷川　聡; 聡長谷川
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: Nippon Telegraph and Telephone Corp
Priority date: 2016-09-30
Filing date: 2016-09-30
Publication date: 2019-10-09
Anticipated expiration: 2036-09-30
Also published as: JP2018055610A

Description

この発明は、パーソナルデータの匿名化技術に関し、特に、位置情報の時系列データである軌跡情報をk-匿名化する技術に関する。

非特許文献１には、パーソナルデータを匿名化する方法として、k-匿名化という方法が記載されている。k-匿名化は、パーソナルデータの集合の中に同じ属性をもつデータが必ずk件以上存在するようにして、個体が特定される確率を1/k以下に抑える匿名化技術である。非特許文献２〜５には、位置情報の時系列データである軌跡情報に対して、k-匿名化を適用する方法が記載されている。例えば、非特許文献５では、まず、緯度・経度・時刻で表される位置情報を地図上のメッシュへマッピングすることにより、緯度・経度の汎化を行う。次に、すべての時刻で同じ緯度・経度である（すなわち同じ軌跡情報を持つ）ユーザーがk人以上いないユーザーを削除する。これにより、ある軌跡情報については必ずk人以上のユーザーが存在することになり、軌跡情報のk-匿名化を実現している。

L. Sweeney, "k-Anonymity: A Model for Protecting Privacy", International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 10(5), pp. 557-570, October 2002. O. Abul, F. Bonchi, and M. Nanni, "Never Walk Alone: Uncertainty for Anonymity in Moving Objects Databases", ICDE '08 Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, Pages 376-385, 2008. M. E. Nergiz et al., "Towards Trajectory Anonymization: a Generalization-Based Approach", Transactions on Data Privacy, vol. 2(1), pp. 47-75, 2009. C.-Y. Chow and M. F. Mokbel, "Trajectory Privacy in Location-based Services and Data Publication", ACM SIGKDD Explorations Newsletter, vol. 13(1), pp. 19-29, June 2011. R. Shigetomi-Yamaguchi et al., "Applicability of Existing Anonymization Methods to Large Location History Data in Urban Travel", IEEE International Conference on Systems, Man, and Cybernetics, 2012.

従来技術によってk-匿名化された軌跡情報は、比較的人通りが少ない領域を通ったユーザーが削除され、常時人通りが多い領域を通ったユーザーのみで構成されることになるため、ユーザー数が大きく減少してしまう傾向がある。これは、たとえ緯度・経度を汎化させても、比較的人通りが少ない領域では、複数時刻で同じ緯度・経度の組合せを持つユーザーは見出しにくいためである。

この発明の目的は、上記のような点に鑑みて、匿名化後の軌跡情報により多くのユーザーが含まれるようにk-匿名化することができる匿名化技術を提供することである。

上記の課題を解決するために、この発明の匿名化装置は、ユーザーを特定する識別子と時刻を示す情報および位置を示す情報からなる複数の位置情報とを含む軌跡情報を入力とし、その軌跡情報の時刻を示す情報および位置を示す情報それぞれを最大値と最小値との差に基づいて無次元化した無次元化位置情報を生成する無次元化部と、無次元化位置情報を複数のクラスターにクラスタリングするクラスタリング部と、無次元化位置情報に含まれる時刻を示す情報および位置を示す情報を、その無次元化位置情報が所属するクラスターの中心値に置き換えて汎化した汎化無次元化位置情報を生成する汎化部と、汎化無次元化位置情報の時刻を示す情報および位置を示す情報それぞれを最大値と最小値の差に基づいて元の次元に戻した汎化位置情報を生成する逆無次元化部と、軌跡情報から時刻を示す情報および位置を示す情報により特定されるユーザーが所定の数未満となるユーザーに関する汎化位置情報を削除した匿名化軌跡情報を生成する削除部と、を含む。

この発明によれば、位置を示す情報および時刻を示す情報について汎化して軌跡情報を匿名化することができる。これにより、従来のk-匿名化法では削除されやすかった、人通りが少ない領域を通ったユーザーのデータが維持され易くなり、結果としてk-匿名化された軌跡情報に含まれるユーザー数が増加する。

図１は、匿名化装置の機能構成を例示する図である。図２は、匿名化方法の処理手続きを例示する図である。

以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。

上述の課題を解決するためには、緯度・経度だけでなく、時刻についても汎化することが１つの方策となる。この発明の実施形態は、入力された軌跡情報をk-匿名化して匿名化軌跡情報を出力する匿名化装置である。実施形態の匿名化装置は、時刻・緯度・経度の三次元空間において近接する位置情報をグルーピングし、あるグループに属する位置情報の時刻・緯度・経度を統一し、汎化を行う。例えば、「14時59分に、A駅南口にいた」「15時01分に、A駅北口にいた」という位置情報であれば、どちらも「15時00分に、A駅にいた」のように加工する。そのために、時刻・緯度・経度の三次元空間において位置情報のクラスタリングを行い、位置情報の各属性を、所属するクラスターの中心値に置き換えるという方法を取る。

実施形態の匿名化装置は、図１に例示するように、入力部１、無次元化部２、クラスタリング部３、汎化部４、逆無次元化部５、削除部６、および出力部７を含む。この匿名化装置が、図２に例示する各ステップの処理を行うことにより実施形態の匿名化方法が実現される。

匿名化装置は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。匿名化装置は、例えば、中央演算処理装置の制御のもとで各処理を実行する。匿名化装置に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて中央演算処理装置へ読み出されて他の処理に利用される。匿名化装置の各処理部は、少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。

図２を参照して、実施形態の匿名化方法の処理手続きを説明する。

ステップＳ１において、入力部１へ、匿名化処理の対象となる軌跡情報が入力される。軌跡情報は無次元化部２へ送られる。軌跡情報は、ユーザーの位置情報の時系列データであり、例えば、ユーザーを特定する識別子、時刻を示す情報、および位置を示す情報を含む。この実施形態では、位置を示す情報は緯度および経度で表すものとして、軌跡情報は、例えば次表に示すように、ユーザーID、時刻、緯度、経度の４つの属性で構成されるものとする。例えば、次表のヘッダーを除いた１〜２行目では、ユーザーIDが「3」であるユーザーが時刻「08:00:18」には緯度「35.68367342」、経度「139.47106963」の位置にいたが、5分後の時刻「08:05:18」には緯度「35.68302667」、経度「139.47132593」の位置へ移動していたことを示している。

ステップＳ２において、無次元化部２は、入力部１から軌跡情報を受け取り、軌跡情報に含まれる時刻・緯度・経度それぞれを最大値と最小値との差に基づいて無次元化する。無次元化部２は、無次元化した位置情報（以下、無次元化位置情報と呼ぶ）をクラスタリング部３へ出力する。

無次元化を行うのは、時刻・緯度・経度は次元（単位）が異なるため、単純に三次元空間を定義することができないからである。具体的には、tを無次元化前の時刻、t'を無次元化後の時刻、latを無次元化前の緯度、lat'を無次元化後の緯度、lonを無次元化前の経度、lon'を無次元化後の経度として、次式のように、それぞれ（最大値−最小値）により除算することで無次元化する。なお、時刻tについては、例えば0時0分0秒など基準となる時刻からの経過時間を秒単位に変換して次式の計算を行う。

ただし、t_maxは時刻tの最大値、t_minは時刻tの最小値、lat_maxは緯度latの最大値、lat_minは緯度latの最小値、lon_maxは経度lonの最大値、lon_minは経度lonの最小値、α_t，α_lat，α_lonは予め与えられた所定の実数である。α_t，α_lat，α_lonは、要求される匿名性および有用性のレベルを満たすように設定すればよく、例えばα_t=α_lat=α_lon=1とする。

ステップＳ３において、クラスタリング部３は、無次元化部２が出力する無次元化位置情報を受け取り、その無次元化位置情報をN_cls（>1）個のクラスターにクラスタリングする。クラスターの個数N_clsは、要求される匿名性および有用性のレベルを満たすように設定する。クラスタリング部３は、クラスタリング後の無次元化位置情報を汎化部４へ出力する。クラスタリングの手法は、既存のいかなる方法を用いてもよいが、例えば、下記参考文献１に記載されたk-平均法を用いることができる。
〔参考文献１〕J. A. Hartigan and M. A. Wong, "Algorithm AS 136: A K-Means Clustering Algorithm", Journal of the Royal Statistical Society. Series C (Applied Statistics), Vol. 28, No. 1 (1979), pp. 100-108.

ステップＳ４において、汎化部４は、クラスタリング部３が出力するクラスタリング後の無次元化位置情報を受け取り、無次元化位置情報に含まれる時刻・緯度・経度を、その無次元化位置情報が所属するクラスターの中心値に置き換えて統一し、汎化する。汎化部４は、汎化した無次元化位置情報（以下、汎化無次元化位置情報と呼ぶ）を逆無次元化部５へ出力する。

ステップＳ５において、逆無次元化部５は、汎化部４が出力する汎化無次元化位置情報を受け取り、汎化無次元化位置情報の時刻・緯度・経度それぞれを最大値と最小値の差に基づいて元の次元に戻す。逆無次元化部５は、次元を元に戻した汎化無次元化位置情報（以下、汎化位置情報と呼ぶ）を削除部６へ出力する。具体的には、t'を逆無次元化前の時刻、tを逆無次元化後の時刻、lat'を逆無次元化前の緯度、latを逆無次元化後の緯度、lon'を無次元化後の経度、lonを逆無次元化後の経度として、次式のように、それぞれ（最大値−最小値）を乗算することで次元を元に戻す。

ステップＳ６において、削除部６は、逆無次元化部５が出力する汎化位置情報を受け取り、時刻・緯度・経度により特定されるユーザーが所定の数k（>1）以上となるように汎化位置情報を削除する。所定の数kは、要求される匿名性および有用性のレベルを満たすように設定する。具体的には、まず、前処理として、各ユーザーについて、時刻・緯度・経度が複数連続して同じものになった場合、１つのみを残して削除する。これは、時刻を汎化することで、同じユーザーが同じ時刻に複数の同じ位置に存在する位置情報をもつ状態が起こり得るが、その場合正しく匿名化ができないからである。次に、時刻・緯度・経度がすべて一致するユーザー数を集計し、そのユーザー数が所定の数k未満であるユーザーに関する汎化位置情報を削除する。これにより、ある軌跡情報を持つユーザーは必ずk人以上となり、削除後の汎化位置情報からなる軌跡情報はk-匿名性を満たすようになる。削除部６は、削除後の汎化位置情報からなる軌跡情報（以下、匿名化軌跡情報と呼ぶ）を出力部７へ出力する。

ステップＳ７において、出力部７は、削除部６が出力する匿名化軌跡情報を受け取り、その匿名化軌跡情報を出力する。

この発明の第一のポイントは、緯度・経度のみでなく、時刻についても統一化を行い、汎化することにより、k-匿名化された軌跡情報に含まれるユーザー数が増加することである。これは、所属するクラスターの中心値へ置き換えることによる時刻・緯度・経度の汎化により実現されるものである。この発明の第二のポイントは、位置情報のクラスタリングを行うためには、時刻・緯度・経度の三次元空間を定義することが必要であるところ、時刻・緯度・経度の各属性を無次元化することで三次元空間を定義したことである。

以上、この発明の実施の形態について説明したが、具体的な構成は、これらの実施の形態に限られるものではなく、この発明の趣旨を逸脱しない範囲で適宜設計の変更等があっても、この発明に含まれることはいうまでもない。実施の形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。

［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。

この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。

また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。

このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。

また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。

１入力部
２無次元化部
３クラスタリング部
４汎化部
５逆無次元化部
６削除部
７出力部

Claims

ユーザーを特定する識別子と時刻を示す情報および位置を示す情報からなる複数の位置情報とを含む軌跡情報を入力とし、その軌跡情報の時刻を示す情報および位置を示す情報それぞれを最大値と最小値との差に基づいて無次元化した無次元化位置情報を生成する無次元化部と、
上記無次元化位置情報を複数のクラスターにクラスタリングするクラスタリング部と、
上記無次元化位置情報に含まれる時刻を示す情報および位置を示す情報を、その無次元化位置情報が所属する上記クラスターの中心値に置き換えて汎化した汎化無次元化位置情報を生成する汎化部と、
上記汎化無次元化位置情報の時刻を示す情報および位置を示す情報それぞれを最大値と最小値の差に基づいて元の次元に戻した汎化位置情報を生成する逆無次元化部と、
上記軌跡情報から時刻を示す情報および位置を示す情報により特定されるユーザーが所定の数未満となるユーザーに関する汎化位置情報を削除した匿名化軌跡情報を生成する削除部と、
を含む匿名化装置。
請求項１に記載の匿名化装置であって、
上記位置を示す情報は緯度および経度からなり、tを無次元化前の時刻とし、t'を無次元化後の時刻とし、latを無次元化前の緯度とし、lat'を無次元化後の緯度とし、lonを無次元化前の経度とし、lon'を無次元化後の経度とし、t_maxを時刻tの最大値とし、t_minを時刻tの最小値とし、lat_maxを緯度latの最大値とし、lat_minを緯度latの最小値とし、lon_maxを経度lonの最大値とし、lon_minを経度lonの最小値とし、α_t，α_lat，α_lonを所定の実数とし、
上記無次元化部は、次式により、上記位置情報を無次元化するものであり、

上記逆無次元化部は、次式により、上記汎化無次元化位置情報を元の次元に戻すものである、

匿名化装置。
請求項１または２に記載の匿名化装置であって、
上記削除部は、各ユーザーについて位置情報が複数同じものが連続する場合は１つを残して削除した上で、時刻を示す情報および位置を示す情報がすべて一致するユーザーが上記所定の数未満となる上記汎化位置情報を削除するものである、
匿名化装置。
無次元化部とクラスタリング部と汎化部と逆無次元化部と削除部とを含む匿名化装置が実行する匿名化方法であって、
上記無次元化部が、ユーザーを特定する識別子と時刻を示す情報および位置を示す情報からなる複数の位置情報とを含む軌跡情報を入力とし、その軌跡情報の時刻を示す情報および位置を示す情報それぞれを最大値と最小値との差に基づいて無次元化した無次元化位置情報を生成する無次元化ステップと、
上記クラスタリング部が、上記無次元化位置情報を複数のクラスターにクラスタリングするクラスタリングステップと、
上記汎化部が、上記無次元化位置情報に含まれる時刻を示す情報および位置を示す情報を、その無次元化位置情報が所属する上記クラスターの中心値に置き換えて汎化した汎化無次元化位置情報を生成する汎化ステップと、
上記逆無次元化部が、上記汎化無次元化位置情報の時刻を示す情報および位置を示す情報それぞれを最大値と最小値の差に基づいて元の次元に戻した汎化位置情報を生成する逆無次元化ステップと、
上記削除部が、上記軌跡情報から時刻を示す情報および位置を示す情報により特定されるユーザーが所定の数未満となるユーザーに関する汎化位置情報を削除した匿名化軌跡情報を生成する削除ステップと、
を含む匿名化方法。
請求項１から３のいずれかに記載の匿名化装置としてコンピュータを機能させるためのプログラム。