(57)【特許請求の範囲】
【請求項１】
データベースは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、||・||１を・のＬ１距離とし、σを所定の値として、
上記データベースに含まれる一部又は全部の属性値のそれぞれについて、下記の式により定義される分散２σ２のラプラス分布に従う値を加算する撹乱部、
【数８】
0005651568.tif 000009
を含むデータベース撹乱装置。
【請求項２】
請求項１のデータベース撹乱装置において、
上記撹乱部により撹乱されたデータベースに含まれるレコードの順序を並び替える並替部を更に含む、
データベース撹乱装置。
【請求項３】
請求項１又は２のデータベース撹乱装置において、
上記撹乱部は、上記それぞれの属性値がカテゴリ属性値である場合には、上記それぞれの属性値を所定の確率で他のカテゴリ属性値に置換する、
データベース撹乱装置。
【請求項４】
請求項１から３の何れかのデータベース撹乱装置と、
上記撹乱部により撹乱されたデータベース及び上記並替部によりレコードが並び替えられたデータベースを用いて集計処理を行う集計処理部と、
を含むデータベース撹乱システム。
【請求項５】
データベースは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、||・||１を・のＬ１距離とし、σを所定の値として、
撹乱部が、上記データベースに含まれる一部又は全部の属性値のそれぞれについて、下記の式により定義される分散２σ２のラプラス分布に従う値を加算する撹乱ステップ、
【数９】
0005651568.tif 000010
を含むデータベース撹乱方法。
【請求項６】
請求項１から３の何れかのデータベース撹乱装置の各部としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プライバシーを保護しながらデータマイニングを行う技術に関する。
【背景技術】
【０００２】
いわゆるＰｋ−匿名性を満たすデータベース撹乱技術が、特許文献１で提案されている（例えば、特許文献１参照。）。
【０００３】
Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−１００１１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１の技術は属性値がいわゆるカテゴリ属性値であることを想定しており、属性値がいわゆる数値属性値である場合には非特許文献１の技術を適用することができない。
【０００６】
この発明の課題は、属性値が数値属性値である場合にも適用することができる、Ｐｋ−匿名性を満たすデータベース撹乱装置、システム、方法及びプログラムを提供することである。
【課題を解決するための手段】
【０００７】
この発明の一態様によるデータベース撹乱装置は、データベースは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、||・||１を・のＬ１距離とし、σを所定の値として、データベースに含まれる一部又は全部の属性値のそれぞれについて、下記の式により定義される分散２σ２のラプラス分布に従う値を加算する撹乱部を備える。
【０００８】
【数１】
0005651568.tif 000002
【発明の効果】
【０００９】
属性値が数値属性値である場合にも適用することができる。
【図面の簡単な説明】
【００１０】
【図１】第一実施形態のデータベース撹乱システムを説明するためのブロック図。
【図２】第一実施形態のデータベース撹乱システムを説明するための流れ図。
【図３】第二実施形態のデータベース撹乱システムを説明するための流れ図。
【図４】データベース撹乱システムの変形例を説明するためのブロック図。
【図５】データベース撹乱システムの変形例を説明するためのブロック図。
【図６】データベース撹乱システムの変形例を説明するためのブロック図。
【図７】第一実施形態で撹乱の対象となるデータベースの例を説明するための図。
【図８】第二実施形態で撹乱の対象となるデータベースの例を説明するための図。
【発明を実施するための形態】
【００１１】
以下、図面を参照して、この発明の実施形態を説明する。
【００１２】
［第一実施形態］
第一実施形態のデータベース撹乱システムは、図１に例示するように、撹乱装置１及び集計装置２を備えている。
【００１３】
撹乱装置１は、データベース記憶部１１と、撹乱部１２と、パラメータ決定部１３とを例えば備えている。この例では、撹乱部１２は、並替部１４を備える。
【００１４】
集計装置２は、集計部２１を例えば備えている。
【００１５】
データベース記憶部１１には、撹乱の対象となるデータベースが記憶されている。データベース記憶部１１に記憶されたデータベースについての情報は、撹乱部１２に送信される。
【００１６】
データベースは、図７に例示するように、複数のレコードから構成されている。
【００１７】
各レコードは、レコード識別子と少なくとも１つの属性値とから構成されている。レコード識別子は、個人を識別する識別子であり、いわゆるレコードＩＤである。レコード識別子は、例えば氏名や氏名に対応するＩＤ番号である。
【００１８】
各属性値は、第一実施形態では、ｎ次元実数ベクトルの部分集合Ｖに含まれるベクトルであり、いわゆる数値属性値である。ｎは、１以上の整数である。ｎ＝１であり属性が例えば「中間テストの点数」や「期末テストの点数」である場合には、属性値は０から１００までの何れかの整数である。
【００１９】
撹乱部１２は、データベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、下記の式により定義される、平均μであり分散２σ２のラプラス分布に従う値を加算することによりデータベースの撹乱を行う（ステップＳ１）。撹乱されたデータベースは、並替部１４に送信される。撹乱の対象となる属性値が複数ある場合には、それらの複数の属性値を独立に撹乱してもよいし、従属に撹乱してもよい。
【００２０】
【数２】
0005651568.tif 000003
【００２１】
||・||１は・のいわゆるＬ１距離であり、・がｎ次元実数ベクトルである場合には、ベクトル・の各成分の絶対値の総和である。ｎは１以上の整数である。
【００２２】
例えば、μ＝０とする。この場合、撹乱部１２が用いるラプラス分布は以下のようになる。
【００２３】
【数３】
0005651568.tif 000004
【００２４】
以下、「ラプラス分布に従う値」について説明する。まず、ラプラス分布を含む一般の確率密度関数ｆに従う値について説明する。
【００２５】
１．「確率密度関数ｆに従う値」について
（１）確率密度関数ｆの定義域及び属性値が１次元の場合
（ｉ）累積分布関数Ｆ（ｘ）＝∫−∞ｘｆ（ｘ’）ｄｘ’を求める。
【００２６】
（ｉｉ）累積分布関数Ｆ（ｘ）の逆関数Ｆ−１を求める。
【００２７】
（ｉｉｉ）区間［０，１］上の一様乱数ｒを生成する。
【００２８】
（ｉｖ）Ｆ−１（ｒ）を「確率密度関数ｆに従う値」として出力する。
【００２９】
累積分布関数Ｆ（ｘ）や逆関数Ｆ−１が数式で得られる場合にはその数式に基づいてＦ−１（ｒ）を計算してもよいし、そうでない場合には数値計算によってＦ−１（ｒ）を計算してもよい。
【００３０】
（２）確率密度関数ｆの定義域及び属性値がｎ次元の場合
ｉ＝０，…，ｎ−１のそれぞれに対して、以下の（ｉ）（ｉｉ）を行う。
【００３１】
（ｉ）ｘ０からｘｉ−１までを固定し、ｘｉ＋１からｘｎ−１までを積分し、ｘｉだけを変数として残した確率密度関数ｆｉを求める。
【００３２】
【数４】
0005651568.tif 000005
【００３３】
（ｉｉ）確率密度関数ｆｉの定義域は１次元なので、上記「（１）確率密度関数ｆの定義域及び属性値が１次元の場合」で示した方法と同様の方法により、「確率密度関数ｆｉに従う値」を計算する。
【００３４】
ｉ＝０，…，ｎ−１のそれぞれに対して「確率密度関数ｆｉに従う値」を計算することにより、ｎ個の「確率密度関数ｆｉに従う値」が得られる。
【００３５】
上記の方法を、確率密度関数がラプラス分布の場合に当てはめると以下のようになる。
【００３６】
２．「ラプラス分布に従う値」について
（１）ラプラス分布の定義域及び属性値が１次元の場合
（ｉ）区間［０，１］上の一様乱数ｒ、区間（０，１）上の一様乱数ｂを生成する。
【００３７】
（ｉｉ）（−１）ｂσｌｏｇｒ＋μを「ラプラス分布に従う値」として出力する。
【００３８】
（２）ラプラス分布の定義域及び属性値がｎ次元の場合
（ｉ）上記「（１）ラプラス分布の定義域及び属性値が１次元の場合」で示した方法と同様の方法により、ｎ個の「ラプラス分布に従う値」であるｘ０，ｘ１，…，ｘｎ−１を計算する。
【００３９】
（ｉｉ）これらのｘ０，ｘ１，…，ｘｎ−１を「ラプラス分布に従う値」として出力する。
【００４０】
並替部１４は、撹乱部１２により撹乱されたデータベースに含まれるレコードの順序を並び替える（ステップＳ２）。レコードが並び替えられたデータベースは、集計装置２に送信される。
【００４１】
並び替えの対象となるのは、データベースに含まれる全部又は一部のレコードである。レコードの並び替えは、一様ランダムに行われてもよいし、ランダムに行われてもよいし、一部又は全部の属性値についての昇順、降順等の所定の並替規則に基づいて行われてもよい。
【００４２】
属性値の種類の数が１である場合には、属性値が属するｎ次元実数ベクトルの部分集合Ｖの元をｕ，ｖとすると、σは下記式（１）又は（２）を満たすように予め定められているとする。|Ｒ|は、データベースのレコードの数である。
【００４３】
【数５】
0005651568.tif 000006
【００４４】
属性値の種類の数が２以上である場合には、各属性値ａが属するｎ次元実数ベクトルの部分集合Ｖａの元をｕ，ｖとすると、σは下記式（３）又は（４）を満たすように予め定められているとする。
【００４５】
【数６】
0005651568.tif 000007
【００４６】
パラメータ決定部１３が、予め定められたｋに基づいて、上記（１）から（４）の式を満たすσを決定してもよい（ステップＳ０）。この場合、パラメータ決定部１３により決定されたσは、撹乱部１２に送信される。
【００４７】
このようにして撹乱されたデータベースは、いわゆるＰｋ−匿名性を満たす。ここでは、その証明を省略する。Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
【００４８】
したがって、このようにして撹乱されたデータベースは、Ｐｋ−匿名性という明確な基準で匿名性が保障される。また、撹乱前のデータベース及び撹乱後のデータベースを用いずに匿名性を保障することができる。
【００４９】
集計部２１は、撹乱装置１により撹乱されたデータベースを用いて集計処理を行う（ステップＳ３）。集計部２１は、例えば、参考文献１に記載された反復ベイズ手法等を用いて、クロス集計等の集計結果を推定する。
【００５０】
〔参考文献１〕
五十嵐大，外２名，「多値属性に適用可能な効率的プライバシー保護クロス集計」，コンピュータセキュリティシンポジウム２００８
［第二実施形態］
第一実施形態は、データベースの全ての属性値がいわゆる数値属性値である場合のデータベース撹乱システムであった。これに対して、第二実施形態は、データベースの属性値がいわゆるカテゴリ属性値を含む場合のデータベース撹乱システムである。第二実施形態で撹乱の対象となるデータベースの例を図８に示す。
【００５１】
カテゴリ属性値とは、例えば性別等の属性値であり、数値属性値とは異なり属性値の取り得る値がいくつかに制限されている属性値のことである。
【００５２】
以下、第一実施形態と異なる部分を中心に説明する。第一実施形態と同様の部分については説明を省略する。
【００５３】
第二実施形態の撹乱部１２は、図２のステップＳ１に代えて、図３のステップＳ１０，Ｓ１，Ｓ１１の処理を行う。
【００５４】
撹乱部１２は、まず、データベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値がカテゴリ属性値であるか判定する（ステップＳ１０）。
【００５５】
属性値がカテゴリ属性値でない場合には、すなわち数値属性値である場合には、撹乱部１２は、第一実施形態と同様の方法によりラプラス分布に従う値の加算を行う（ステップＳ１）。
【００５６】
属性値がカテゴリ属性値である場合には、撹乱部１２は、その属性値を所定の確率で他のカテゴリ属性値に置換する（ステップＳ１１）。具体的には、いわゆる維持確率ρの維持−置換撹乱を行う。
【００５７】
維持確率ρの維持−置換撹乱は、維持確率ρが予め定められているとして、維持確率ρでその属性値を変更せずに維持し、１−ρの確率でその属性値を他のカテゴリ属性値に置換する撹乱方法である。他のカテゴリ属性値に置換するとは、例えば属性が性別であり属性値が「男」である場合には、その属性値「男」を属性値「女」に置換することを意味する。維持確率ρの維持−置換撹乱の詳細については、特許文献１を参照のこと。
【００５８】
属性の種類の数が２以上である場合には、各属性ａの属性値が属するｎ次元実数ベクトルの部分集合Ｖａの元をｕ，ｖとすると、σ及び維持確率ρは下記式（５）を満たすように予め定められているとする。例えば、パラメータ決定部１３が、予め定められたｋに基づいて、下記式（５）の式を満たすσ及び維持確率ρを決定する（ステップＳ０）。|Ｖａ|は、属性ａのカテゴリ属性値の取り得る値の数である。
【００５９】
【数７】
0005651568.tif 000008
【００６０】
このようにして撹乱されたデータベースは、第一実施形態と同様に、いわゆるＰｋ−匿名性を満たす。ここでは、その証明を省略する。
【００６１】
したがって、このようにして撹乱されたデータベースは、第一実施形態と同様に、Ｐｋ−匿名性という明確な基準で匿名性が保障される。また、撹乱前のデータベース及び撹乱後のデータベースを用いずに匿名性を保障することができる。
【００６２】
［変形例等］
並替部１４の処理は行わなくてもよい。この場合、データベースのレコードの並び替えは行われず、撹乱部１２により撹乱されたデータベースが集計装置２に送信される。集計装置２は、受信した並び替えが行われていないデータベースに基づいて集計処理を行う。
【００６３】
撹乱部１２が撹乱装置１に備えられ、集計部２１が集計装置２に備えられていれば、他の各部はデータベース撹乱システムを構成する装置の何れに備えられていてもよい。
【００６４】
例えば、図４に例示するように、パラメータ決定部１３が集計装置２に備えられていてもよい。この場合、パラメータ決定部１３により決定されたパラメータは、撹乱装置１に送信される。
【００６５】
また、例えば、図５に示すように、データベース撹乱システムが、撹乱装置１、集計装置２及び撹乱データサーバ装置３から構成されている場合には、パラメータ決定部１３が撹乱データサーバ装置３に備えられていてもよい。この場合、パラメータ決定部１３により決定されたパラメータは撹乱装置１に送信され、撹乱装置１により撹乱されたデータベースは撹乱データサーバ装置３を経由して集計装置２に送信される。具体的には、撹乱データサーバ装置３のデータ送受信部３１が、撹乱装置１により撹乱されたデータベースを受信して、集計装置２に送信する。
【００６６】
また、図６に例示するように、データベース撹乱システムに、撹乱装置１及び集計装置２のそれぞれが複数備えられていてもよい。
データベース撹乱装置の各部間のデータの送受信は直接行われてもよいし、図示していない記憶部を介して行われてもよい。データベース撹乱システムの各装置間のデータの送受信は直接行われてもよいし、他の装置を経由して行われてもよい。
【００６７】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【００６９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７０】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【符号の説明】
【００７１】
１      撹乱装置
１１    データベース記憶部
１２    撹乱部
１３    パラメータ決定部
１４    並替部
２１    集計部
２      集計装置
【図１】
0005651568.tif 000011
【図２】
0005651568.tif 000012
【図３】
0005651568.tif 000013
【図４】
0005651568.tif 000014
【図５】
0005651568.tif 000015
【図６】
0005651568.tif 000016
【図７】
0005651568.tif 000017
【図８】
0005651568.tif 000018