(57)【要約】  データの有用性を損なうことなく、匿名化する技術を提供する。Mを属性の数、Nをレコードの数、pをマスター属性の数、Lを互いに異なるp個のマスター属性の値の組の数とし、M×Nの匿名化対象テーブルから、p個のマスター属性の値の組が互いに異なる、L個の匿名化対象テーブルのレコードを含むM×Lの部分テーブルを生成する重複排除部と、部分テーブルから、p個のマスター属性を対象として部分テーブルを匿名化したM×Lの匿名化済部分テーブルを生成する匿名化部と、匿名化対象テーブルと匿名化済部分テーブルから、p個のマスター属性を対象として匿名化対象テーブルを匿名化したM×Nの匿名化済テーブルを生成する重複復元部とを含む。
2020175306.tif 000002
【特許請求の範囲】
【請求項１】
Mを属性の数を表す2以上の整数、Nをレコードの数を表す1以上の整数、pをマスター属性の数を表す1以上M以下の整数、Lを互いに異なるp個のマスター属性の値の組の数を表す1以上N以下の整数とし、
M×Nの匿名化対象テーブルから、p個のマスター属性の値の組が互いに異なる、L個の前記匿名化対象テーブルのレコードを含むM×Lの部分テーブルを生成する重複排除部と、
前記部分テーブルから、p個のマスター属性を対象として前記部分テーブルを匿名化したM×Lの匿名化済部分テーブルを生成する匿名化部と、
前記匿名化対象テーブルと前記匿名化済部分テーブルから、p個のマスター属性を対象として前記匿名化対象テーブルを匿名化したM×Nの匿名化済テーブルを生成する重複復元部と、
を含む匿名化装置。
【請求項２】
請求項１に記載の匿名化装置であって、
レコード番号を前記匿名化対象テーブルに含まれるレコードを識別する番号とし、
前記重複排除部は、p個のマスター属性の値の組が同一である前記匿名化対象テーブルのレコードのレコード番号の集合と、当該集合の要素であるキーの値の組をレコードとする2×Lの重複レコード番号テーブルを生成するものであり、
前記重複復元部は、前記重複レコード番号テーブルを用いて、前記匿名化済テーブルを生成するものである
ことを特徴とする匿名化装置。
【請求項３】
Mを属性の数を表す2以上の整数、Nをレコードの数を表す1以上の整数、pをマスター属性の数を表す1以上M以下の整数、Lを互いに異なるp個のマスター属性の値の組の数を表す1以上N以下の整数とし、
匿名化装置が、M×Nの匿名化対象テーブルから、p個のマスター属性の値の組が互いに異なる、L個の前記匿名化対象テーブルのレコードを含むM×Lの部分テーブルを生成する重複排除ステップと、
前記匿名化装置が、前記部分テーブルから、p個のマスター属性を対象として前記部分テーブルを匿名化したM×Lの匿名化済部分テーブルを生成する匿名化ステップと、
前記匿名化装置が、前記匿名化対象テーブルと前記匿名化済部分テーブルから、p個のマスター属性を対象として前記匿名化対象テーブルを匿名化したM×Nの匿名化済テーブルを生成する重複復元ステップと、
を含む匿名化方法。
【請求項４】
請求項１または２に記載の匿名化装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、匿名化技術に関する。
【背景技術】
【０００２】
近年、データマイニングにおいてプライバシーを保護しながら結果を得ることができるプライバシー保護データマイニングと呼ばれる技術が注目されている。このような技術として、非特許文献１に記載のk-匿名化や非特許文献２に記載のPk-匿名化がある。【０００３】
これらの匿名化技術の処理対象は、図１に示すようなテーブルである。ここで、テーブルとは、M（Mは2以上の整数）個の属性に対して、その値の組であるレコードをN（Nは1以上の整数）個含むデータである。また、レコードのことを行、ある属性（例えば、氏名）の値の組のことを列という。例えば、図１のテーブルの１行目は、（Aさん, 男, 30代, コンビニ, 150）であり、１列目は（Aさん, Cさん, Eさん, Aさん, Bさん, Dさん, Eさん）である。また、テーブルのサイズをM×Nと表す。例えば、図１のテーブルは5×7のテーブル（M=5、N=7）である。テーブルに含まれる属性値のことをテーブルの要素という。【０００４】
非特許文献１や非特許文献２に記載の匿名化技術が匿名化対象とする属性のことをマスター属性、それ以外の属性、つまり、匿名化技術が匿名化対象としない属性のことを履歴属性という。また、あるマスター属性に対する属性値の組、すなわち、列を削除することを属性削除という。属性削除は匿名化技術の一例である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Latanya Sweeney, “k-anonymity: a model for protecting privacy”, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, Vol.10, Issue 5, October 2002.
【非特許文献２】五十嵐大，千田浩司，高橋克巳，“k-匿名性の確率的指標への拡張とその適用例”，コンピュータセキュリティシンポジウム２００９(CSS2009)，pp.1-6，2009年10月.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１や非特許文献２に記載の匿名化技術では、マスター属性の値の組と履歴属性の値の組が１対１に対応する特殊なレコードから構成されるテーブルを対象として匿名化処理を行い、データを保護する。そのため、例えば、図１のテーブルに対して、マスター属性を氏名、性別、年代の３つの属性、履歴属性を購入店舗、購入金額の２つの属性としてk-匿名化を用いて匿名化しようとすると、このままでは適用することができない。この問題を解決する方法として、テーブルを分割して匿名化する方法を以下説明する。【０００７】
ある１つの履歴属性に着目し、その値ごとにテーブルを分割することを考える。購入店舗に着目すると、図１は、図２に示す２つのテーブル（すなわち、コンビニでの購入履歴を示すテーブルとスーパーでの購入履歴を示すテーブル）に分割することができる。図２の２つのテーブルは図１のテーブルと等価であり、図２の２つのテーブルと図１のテーブルが表す情報に差はない。このように図１のテーブルを分割して得られる、図２の２つのテーブルは、いずれもマスター属性の値の組と履歴属性の値の組が１対１に対応するテーブルとなるが、氏名を属性削除し、k=3として性別、年代でk-匿名化を行うと、いずれのテーブルもマスター属性の値の組が同一であるレコードを3以上含むことがないため、図３に示す、すべてのレコードが削除された２つのテーブルが得られる。ここで、網掛けされた箇所が匿名化された要素を表す。その結果、図１のテーブルを匿名化して得られるテーブルは、図４のテーブルのように、すべてのレコードが削除されたテーブルとなる。【０００８】
このように１つの履歴属性に着目し、その値ごとにテーブルを分割してそれぞれのテーブルを匿名化する方法では、一般に分割して得られるテーブルに含まれるレコードの数が元のテーブルに含まれるレコードの数より少なくなるため、削除されるレコードの数が多くなってしまい、データ（図１のテーブル）の有用性が損なわれてしまう結果となる。【０００９】
また、別の例として、氏名を属性削除し、k=2として性別、年代でk-匿名化を行うと、図５に示すように、コンビニでの購入履歴を示すテーブルについては１つのレコードが削除されたテーブル、スーパーでの購入履歴を示すテーブルについてはレコードが削除されていないテーブルが得られる。その結果、図１のテーブルを匿名化して得られるテーブルは、図６のテーブルのように、１つのレコードが削除されたテーブルとなる。図６のテーブルをみるとわかるように、Eさんのスーパーでの購入履歴のデータは匿名化後も残る一方で、コンビニでの購入履歴のデータは削除されてしまい、Eさんに関するデータの組み合わせ関係が崩れてしまう。【００１０】
このように１つの履歴属性に着目し、その値ごとにテーブルを分割してそれぞれのテーブルを匿名化する方法では、データの組み合わせ関係が崩れることによっても、データ（図１のテーブル）の有用性が損なわれてしまう結果となる。【００１１】
そこで本発明は、データの有用性を損なうことなく、匿名化する技術を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明の一態様は、Mを属性の数を表す2以上の整数、Nをレコードの数を表す1以上の整数、pをマスター属性の数を表す1以上M以下の整数、Lを互いに異なるp個のマスター属性の値の組の数を表す1以上N以下の整数とし、M×Nの匿名化対象テーブルから、p個のマスター属性の値の組が互いに異なる、L個の前記匿名化対象テーブルのレコードを含むM×Lの部分テーブルを生成する重複排除部と、前記部分テーブルから、p個のマスター属性を対象として前記部分テーブルを匿名化したM×Lの匿名化済部分テーブルを生成する匿名化部と、前記匿名化対象テーブルと前記匿名化済部分テーブルから、p個のマスター属性を対象として前記匿名化対象テーブルを匿名化したM×Nの匿名化済テーブルを生成する重複復元部とを含む。
【発明の効果】
【００１３】
本発明によれば、データの有用性を損なうことなく、匿名化することが可能になる。
【図面の簡単な説明】
【００１４】
【図１】匿名化対象テーブルの一例を示す図である。
【図２】テーブルを分割して匿名化する方法を説明する図である。
【図３】テーブルを分割して匿名化する方法を説明する図である。
【図４】テーブルを分割して匿名化する方法を説明する図である。
【図５】テーブルを分割して匿名化する方法を説明する図である。
【図６】テーブルを分割して匿名化する方法を説明する図である。
【図７】匿名化装置１００の構成の一例を示すブロック図である。
【図８】匿名化装置１００の動作の一例を示すフローチャートである。
【図９】重複排除部１１０の構成の一例を示すブロック図である。
【図１０】重複排除部１１０の動作の一例を示すフローチャートである。
【図１１】匿名化対象テーブルの一例を示す図である。
【図１２】符号化済テーブルの生成過程で得られるテーブルの一例を示す図である。
【図１３】符号化済テーブルの一例を示す図である。
【図１４】重複レコード番号テーブルの生成過程で得られるテーブルの一例を示す図である。
【図１５】重複レコード番号テーブルの生成過程で得られるテーブルの一例を示す図である。
【図１６】重複レコード番号テーブルの生成過程で得られるテーブルの一例を示す図である。
【図１７】重複レコード番号テーブルの一例を示す図である。
【図１８】部分テーブルの生成過程で得られるテーブルの一例を示す図である。
【図１９】部分テーブルの生成過程で得られるテーブルの一例を示す図である。
【図２０】部分テーブルの一例を示す図である。
【図２１】匿名化済部分テーブルの一例を示す図である。
【図２２】匿名化済テーブルの一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１６】
＜第１実施形態＞
Mを属性の数を表す2以上の整数、Nをレコードの数を表す1以上の整数、pをマスター属性の数を表す1以上M以下の整数、Lを互いに異なるp個のマスター属性の値の組の数を表す1以上N以下の整数とする。匿名化装置１００は、M×Nの、匿名化の処理対象となるテーブル（匿名化対象テーブル）から、p個のマスター属性を対象として匿名化対象テーブルを匿名化したM×Nの匿名化済テーブルを生成する。
【００１７】
以下、図７〜図８を参照して匿名化装置１００について説明する。図７は、匿名化装置１００の構成を示すブロック図である。図８は、匿名化装置１００の動作を示すフローチャートである。図７に示すように匿名化装置１００は、重複排除部１１０、匿名化部１２０、重複復元部１３０、記録部１９０を含む。記録部１９０は、匿名化装置１００の処理に必要な情報を適宜記録する構成部である。記録部１９０は、例えば、匿名化対象テーブルなど匿名化装置１００が処理する過程で生成するテーブルを記録する。
【００１８】
図８に従い匿名化装置１００の動作について説明する。
【００１９】
Ｓ１１０において、重複排除部１１０は、M×Nの匿名化対象テーブルを入力とし、匿名化対象テーブルから、p個のマスター属性の値の組が互いに異なる、L個の匿名化対象テーブルのレコードを含むM×Lの部分テーブルを生成し、部分テーブルを出力する。以下、図９〜図１０を参照して重複排除部１１０について説明する。図９は、重複排除部１１０の構成を示すブロック図である。図１０は、重複排除部１１０の動作を示すフローチャートである。図９に示すように重複排除部１１０は、符号化済テーブル生成部１１１、重複レコード番号テーブル生成部１１３、部分テーブル生成部１１５を含む。
【００２０】
図１０に従い重複排除部１１０の動作について説明する。
【００２１】
Ｓ１１１において、符号化済テーブル生成部１１１は、匿名化対象テーブルから、p個のマスター属性の値の組であるレコードをN個含むp×Nのマスター属性テーブルを生成し、当該マスター属性テーブルの値を符号化したp×Nの符号化済テーブルを生成する。以下、各テーブルの具体例を用いて説明する。まず、符号化済テーブル生成部１１１は、図１１の匿名化対象テーブルから、図１２のマスター属性テーブルを生成する。次に、符号化済テーブル生成部１１１は、図１２のマスター属性テーブルから、図１３の符号化済テーブルを生成する。符号化済テーブルは、値が同じマスター属性テーブルの要素には同じ整数値を割り当てるという規則に従い符号化することにより得られるテーブルである。
【００２２】
Ｓ１１３において、重複レコード番号テーブル生成部１１３は、Ｓ１１１で生成した符号化済テーブルから、p個のマスター属性の値の組が同一である匿名化対象テーブルのレコードのレコード番号の集合と、当該集合の要素（例えば、当該集合の最小値）であるキーの値の組をレコードとする2×Lの重複レコード番号テーブルを生成する。ここで、レコード番号とは、匿名化対象テーブルに含まれるレコードを識別する番号のことである。以下、各テーブルの具体例を用いて説明する。まず、重複レコード番号テーブル生成部１１３は、図１３の符号化済テーブルから、図１４のレコード番号付き符号化済テーブルを生成する。レコード番号付き符号化済テーブルは、レコード番号の列を符号化済テーブルに追加することにより得られる(p+1)×Nのテーブルである。次に、重複レコード番号テーブル生成部１１３は、図１４のレコード番号付き符号化済テーブルから、図１７の重複レコード番号テーブルを生成する。その際、重複レコード番号テーブル生成部１１３は、例えば、図１５に示すマップ構造を用いた2×Nのテーブルや図１６に示すマップ構造を用いた2×Lのテーブルを生成し、重複レコード番号テーブルを生成する。ここで、マップ構造とは、一つの属性に対して、複数の当該属性の値を１つにまとめて格納するデータ構造である。例えば、図１５では、符号化データという属性に対して、[1, 2, 3]、[4, 5, 6]などのような複数の値が１つの要素として格納されている。
【００２３】
Ｓ１１５において、部分テーブル生成部１１５は、匿名化対象テーブルとＳ１１３で生成した重複レコード番号テーブルから、部分テーブルを生成する。以下、各テーブルの具体例を用いて説明する。まず、部分テーブル生成部１１５は、図１１の匿名化対象テーブルから、図１８のレコード番号付き匿名化対象テーブルを生成する。レコード番号付き匿名化対象テーブルは、レコード番号の列を匿名化対象テーブルに追加することにより得られる(M+1)×Nのテーブルである。次に、部分テーブル生成部１１５は、図１８のレコード番号付き匿名化対象テーブルと図１７の重複レコード番号テーブルから、図２０の部分テーブルを生成する。その際、部分テーブル生成部１１５は、例えば、図１９のレコード番号付き部分テーブルを生成し、部分テーブルを生成する。
【００２４】
Ｓ１２０において、匿名化部１２０は、Ｓ１１０で生成した部分テーブルを入力とし、部分テーブルから、p個のマスター属性を対象として部分テーブルを匿名化したM×Lの匿名化済部分テーブルを生成し、匿名化済部分テーブルを出力する。以下、各テーブルの具体例を用いて説明する。匿名化部１２０は、図２０の部分テーブルから、図２１の匿名化済部分テーブルを生成する。図２１の匿名化済部分テーブルは、氏名を属性削除、住所及び年齢を一般化、k=2としてk-匿名化することにより、得られる。
【００２５】
なお、匿名化には、属性削除、一般化、k-匿名化の他、Pk-匿名化を用いてもよい。また、レコードの順番（上下）を入れ替えるレコードシャッフルを用いてもよい。レコードシャッフルのようにレコードの順番を入れ替える処理を含む匿名化を行う場合、匿名化部１２０は、レコード番号の遷移を表すテーブルを生成する。
【００２６】
Ｓ１３０において、重複復元部１３０は、匿名化対象テーブルとＳ１２０で生成した匿名化済部分テーブルとＳ１１０で生成した重複レコード番号テーブルを入力とし、匿名化対象テーブルと匿名化済部分テーブルから、重複レコード番号テーブルを用いて、匿名化済テーブルを生成し、匿名化済テーブルを出力する。以下、各テーブルの具体例を用いて説明する。重複復元部１３０は、図２１の匿名化済部分テーブルから、図２２の匿名化済テーブルを生成する。
【００２７】
なお、Ｓ１２０においてレコードの順番を入れ替える処理を含む匿名化が行われた場合、重複復元部１３０は、匿名化対象テーブルとＳ１２０で生成した匿名化済部分テーブルとＳ１１０で生成した重複レコード番号テーブルとＳ１２０で生成したレコード番号の遷移を表すテーブルを入力とし、匿名化対象テーブルと匿名化済部分テーブルから、重複レコード番号テーブルとレコード番号の遷移を表すテーブルを用いて、匿名化済テーブルを生成し、匿名化済テーブルを出力する。
【００２８】
本発明の実施形態によれば、データの有用性を損なうことなく、匿名化することが可能になる。
【００２９】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００３０】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【００３１】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成部）を実現する。
【００３２】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００３３】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００３４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００３５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００３８】
上述の本発明の実施形態の記載は、例証と記載の目的で提示されたものである。網羅的であるという意思はなく、開示された厳密な形式に発明を限定する意思もない。変形やバリエーションは上述の教示から可能である。実施形態は、本発明の原理の最も良い例証を提供するために、そして、この分野の当業者が、熟考された実際の使用に適するように本発明を色々な実施形態で、また、色々な変形を付加して利用できるようにするために、選ばれて表現されたものである。すべてのそのような変形やバリエーションは、公正に合法的に公平に与えられる幅にしたがって解釈された添付の請求項によって定められた本発明のスコープ内である。
【図１】
2020175306.tif 000003
【図２】
2020175306.tif 000004
【図３】
2020175306.tif 000005
【図４】
2020175306.tif 000006
【図５】
2020175306.tif 000007
【図６】
2020175306.tif 000008
【図７】
2020175306.tif 000009
【図８】
2020175306.tif 000010
【図９】
2020175306.tif 000011
【図１０】
2020175306.tif 000012
【図１１】
2020175306.tif 000013
【図１２】
2020175306.tif 000014
【図１３】
2020175306.tif 000015
【図１４】
2020175306.tif 000016
【図１５】
2020175306.tif 000017
【図１６】
2020175306.tif 000018
【図１７】
2020175306.tif 000019
【図１８】
2020175306.tif 000020
【図１９】
2020175306.tif 000021
【図２０】
2020175306.tif 000022
【図２１】
2020175306.tif 000023
【図２２】
2020175306.tif 000024
【国際調査報告】
2020175306.tif 000025
2020175306.tif 000026
2020175306.tif 000027
2020175306.tif 000028