データベース撹乱パラメータ設定装置、方法及びプログラム並びにデータベース撹乱システム
【課題】属性値が数値である場合にも適用することができる、Ｐｋ−匿名性を満たすデータベース撹乱技術に用いられるパラメータを決定する技術を提供する。
【解決手段】下記式を満たすパラメータｐを決定する。
このパラメータｐは、テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることによりテーブルの撹乱を行うとしてデータベース撹乱技術に用いられる。
【解決手段】下記式を満たすパラメータｐを決定する。
このパラメータｐは、テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることによりテーブルの撹乱を行うとしてデータベース撹乱技術に用いられる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プライバシーを保護しながらデータマイニングを行う技術に関する。
【背景技術】
【０００２】
いわゆるＰｋ−匿名性を満たすデータベース撹乱技術及びそのデータベース撹乱技術で用いられるパラメータ決定技術が、特許文献１で提案されている（例えば、特許文献１参照。）。
Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１１−１００１１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１の技術は属性値がいわゆるカテゴリ属性値であることを想定しており、属性値がいわゆる数値属性値である場合には非特許文献１の技術を適用することができない。
【０００５】
この発明の課題は、属性値が数値属性値である場合にも適用することができる、Ｐｋ−匿名性を満たすデータベース撹乱パラメータ設定装置、方法及びプログラム並びにデータベース撹乱システムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様によるデータベース撹乱装置は、テーブルは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｒ|をレコードの数とし、ｅｓｓ ｉｎｆ・を・の本質的下限として、テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることによりテーブルの撹乱を行うデータベース撹乱装置に用いられる、パラメータｐを決定するデータベース撹乱パラメータ決定装置であって、下記式を満たすパラメータｐを決定するパラメータ決定部を含む。
【０００７】
【数１】
【発明の効果】
【０００８】
属性値が数値属性値である場合にも適用することができる。
【図面の簡単な説明】
【０００９】
【図１】第一実施形態のデータベース撹乱システムを説明するためのブロック図。
【図２】第一実施形態のデータベース撹乱システムを説明するための流れ図。
【図３】第二実施形態のデータベース撹乱システムを説明するための流れ図。
【図４】データベース撹乱システムの変形例を説明するためのブロック図。
【図５】データベース撹乱システムの変形例を説明するためのブロック図。
【図６】データベース撹乱システムの変形例を説明するためのブロック図。
【図７】第一実施形態で撹乱の対象となるデータベースの例を説明するための図。
【図８】第二実施形態で撹乱の対象となるデータベースの例を説明するための図。
【図９】第一実施形態のパラメータの決定方法を説明するための流れ図。
【図１０】第二実施形態のパラメータの決定方法を説明するための流れ図。
【図１１】第二実施形態のパラメータの決定方法を説明するための流れ図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、この発明の実施形態を説明する。
【００１１】
［第一実施形態］
第一実施形態のデータベース撹乱システムは、図１に例示するように、撹乱装置１及び集計装置２を備えている。
撹乱装置１は、データベース記憶部１１と、撹乱部１２と、パラメータ決定部１３とを例えば備えている。この例では、撹乱部１２は、並替部１４を備える。パラメータ決定部１３が、特許請求の範囲のデータベース撹乱パラメータ決定装置に対応している。
【００１２】
集計装置２は、集計部２１を例えば備えている。
データベース記憶部１１には、撹乱の対象となるデータベースが記憶されている。データベース記憶部１１に記憶されたデータベースについての情報は、撹乱部１２に送信される。
データベースは、図７に例示するように、複数のレコードから構成されている。
【００１３】
各レコードは、レコード識別子と少なくとも１つの属性値とから構成されている。レコード識別子は、個人を識別する識別子であり、いわゆるレコードＩＤである。レコード識別子は、例えば氏名や氏名に対応するＩＤ番号である。
各属性値は、第一実施形態では、ｎ次元実数ベクトルの部分集合Ｖに含まれるベクトルであり、いわゆる数値属性値である。ｎは、１以上の整数である。ｎ＝１であり属性が例えば「中間テストの点数」や「期末テストの点数」である場合には、属性値は０から１００までの何れかの整数である。
【００１４】
撹乱部１２は、データベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行うことによりデータベースの撹乱を行う（ステップＳ１）。撹乱されたデータベースは、並替部１４に送信される。撹乱の対象となる属性値が複数ある場合には、それらの複数の属性値を独立に撹乱してもよいし、従属に撹乱してもよい。
【００１５】
確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱とは、例えばデータベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、確率密度関数Ａａ（ｐ）ｖ，ｖ’に従う値を加算することや、後述する維持確率ρの維持−置換撹乱を行うことを意味する。
【００１６】
確率密度関数Ａａ（ｐ）ｖ，ｖ’は、例えば下記式により定義される平均μであり分散２σ２のラプラス分布である。この場合、所定のパラメータｐは、σである。
【数２】
||・||１は・のいわゆるＬ１ノルムである。
【００１７】
例えば、μ＝０とする。この場合、撹乱部１２が用いるラプラス分布は以下のようになる。
【数３】
【００１８】
以下、「ラプラス分布に従う値」について説明する。まず、ラプラス分布を含む一般の確率密度関数ｆに従う値について説明する。ここでは表記の簡略化のために、確率密度関数ｆと書く。確率密度関数ｆは上記確率密度関数Ａａ（ｐ）ｖ，ｖ’と同じと考えてよい。
１．「確率密度関数ｆに従う値」について
（１）確率密度関数ｆの定義域及び属性値が１次元の場合
（ｉ）累積分布関数Ｆ（ｘ）＝∫−∞ｘｆ（ｘ’）ｄｘ’を求める。
（ｉｉ）累積分布関数Ｆ（ｘ）の逆関数Ｆ−１を求める。
（ｉｉｉ）区間［０，１］上の一様乱数ｒを生成する。
（ｉｖ）Ｆ−１（ｒ）を「確率密度関数ｆに従う値」として出力する。
累積分布関数Ｆ（ｘ）や逆関数Ｆ−１が数式で得られる場合にはその数式に基づいてＦ−１（ｒ）を計算してもよいし、そうでない場合には数値計算によってＦ−１（ｒ）を計算してもよい。
【００１９】
（２）確率密度関数ｆの定義域及び属性値がｎ次元の場合
ｉ＝０，…，ｎ−１のそれぞれに対して、以下の（ｉ）（ｉｉ）を行う。
（ｉ）ｘ０からｘｉ−１までを固定し、ｘｉ＋１からｘｎ−１までを積分し、ｘｉだけを変数として残した確率密度関数ｆｉを求める。
【数４】
（ｉｉ）確率密度関数ｆｉの定義域は１次元なので、上記「（１）確率密度関数ｆの定義域及び属性値が１次元の場合」で示した方法と同様の方法により、「確率密度関数ｆｉに従う値」を計算する。
ｉ＝０，…，ｎ−１のそれぞれに対して「確率密度関数ｆｉに従う値」を計算することにより、ｎ個の「確率密度関数ｆｉに従う値」が得られる。
【００２０】
上記の方法を、確率密度関数がラプラス分布の場合に当てはめると以下のようになる。
２．「ラプラス分布に従う値」について
（１）ラプラス分布の定義域及び属性値が１次元の場合
（ｉ）区間［０，１］上の一様乱数ｒ、区間（０，１）上の一様乱数ｂを生成する。
（ｉｉ）（−１）ｂσｌｏｇｒ＋μを「ラプラス分布に従う値」として出力する。
【００２１】
（２）ラプラス分布の定義域及び属性値がｎ次元の場合
（ｉ）上記「（１）ラプラス分布の定義域及び属性値が１次元の場合」で示した方法と同様の方法により、ｎ個の「ラプラス分布に従う値」であるｘ０，ｘ１，…，ｘｎ−１を計算する。
（ｉｉ）これらのｘ０，ｘ１，…，ｘｎ−１を「ラプラス分布に従う値」として出力する。
【００２２】
並替部１４は、撹乱部１２により撹乱されたデータベースに含まれるレコードの順序を並び替える（ステップＳ２）。レコードが並び替えられたデータベースは、集計装置２に送信される。
【００２３】
並び替えの対象となるのは、データベースに含まれる全部又は一部のレコードである。レコードの並び替えは、一様ランダムに行われてもよいし、ランダムに行われてもよいし、一部又は全部の属性値についての昇順、降順等の所定の並替規則に基づいて行われてもよい。
【００２４】
パラメータ決定部１３は、撹乱部２のステップＳ０の処理の前に、パラメータｐを決定する（ステップＳ０）。決定されたパラメータｐは、撹乱部２に送信される。
【００２５】
例えば、確率密度関数Ａａ（ｐ）ｖ，ｖ’が一般の確率密度関数であり、属性値の数が１である場合には、パラメータ決定部１３は、パラメータｐを以下の式（１）を満たすように決定する。ｋはセキュリティパラメータであり、|Ｒ|はデータベースのレコードの数であり、ｅｓｓ ｉｎｆ・は・の本質的下限である。撹乱前の属性値ｖ，ｕの定義域をＶとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’とする。
【数５】
【００２６】
関数ｆ（ｘ）の定義域をχとすると、関数ｆ（ｘ）の本質的下限ｅｓｓ ｉｎｆ ｆ（ｘ）は、具体的には以下のように書ける。μ（｛ｆ＜ｂ｝）を、関数ｆ（ｘ）＜ｂとなる領域の測度（例えば、面積又は体積）とする。下記式のＲは実数を意味する。
【数６】
【００２７】
例えば、確率密度関数Ａａ（ｐ）ｖ，ｖ’が一般の確率密度関数であり、属性値の数が１以上である場合には、パラメータ決定部１３は、パラメータｐを以下の式（２）を満たすように決定する。属性ａに対応する確率密度関数をＡａ（ｐ）ｖ，ｖ’として、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとする。
【数７】
【００２８】
例えば、確率密度関数Ａ（ｐ）ｖ，ｖ’が平均μであり分散２σ２のラプラス分布であり、属性値の種類の数が１である場合には、パラメータ決定部１３は、パラメータであるσを下記式（３）又は（４）を満たすよう定める。
【数８】
【００２９】
属性値の種類の数が１以上である場合には、パラメータ決定部１３は、パラメータであるσを下記式（５）又は（６）を満たすように定める。
【数９】
【００３０】
パラメータ決定部１３は、例えばいわゆる二分法により、上記式（１）から（６）の何れかを満たすパラメータｐ又はσを決定する。以下、図９を参照して、確率密度関数Ａａ（ｐ）ｖ，ｖ’が平均μであり分散２σ２のラプラス分布であり、属性値の種類の数が１である場合を例に挙げて、二分法を用いてこの場合のパラメータであるσを決定する方法を説明する。
【００３１】
まず、パラメータ決定部１３は、σ＝１とする（ステップＳ０１）。
【００３２】
パラメータ決定部１３は、下記式（７）によりｋ’を計算する（ステップＳ０２）。下記式（７）は、上記式（４）に対応するものである。
【数１０】
【００３３】
パラメータ決定部１３は、計算されたｋ’と所望のｋとを比較する（ステップＳ０３）。
パラメータ決定部１３は、ｋ’がｋ以上であれば、σｍａｘ＝σとする（ステップＳ０４）。すなわち、σの値を、変数σｍａｘに代入する。その後、ステップＳ０６に進む。
【００３４】
パラメータ決定部１３は、ｋ’がｋ以上でなければ、σ＝２σとする（ステップＳ０５）。すなわち、現在のσの値を２倍した値を新たなσの値とする。その後、ステップＳ０２に進む。
パラメータ決定部１３は、区間［０，σｍａｘ］で、上記式（７）を評価式とする二分法によりｋが所望の値になるまで反復計算して最適なσを求める（ステップＳ０６）。
【００３５】
このようにして撹乱されたデータベースは、いわゆるＰｋ−匿名性を満たす。ここでは、その証明を省略する。Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
したがって、このようにして撹乱されたデータベースは、Ｐｋ−匿名性という明確な基準で匿名性が保障される。また、撹乱前のデータベース及び撹乱後のデータベースを用いずに匿名性を保障することができる。
【００３６】
集計部２１は、撹乱装置１により撹乱されたデータベースを用いて集計処理を行う（ステップＳ３）。集計部２１は、例えば、参考文献１に記載された反復ベイズ手法等を用いて、クロス集計等の集計結果を推定する。
〔参考文献１〕
五十嵐大，外２名，「多値属性に適用可能な効率的プライバシー保護クロス集計」，コンピュータセキュリティシンポジウム２００８
【００３７】
［第二実施形態］
第一実施形態は、データベースの全ての属性値がいわゆる数値属性値である場合のデータベース撹乱システムであった。これに対して、第二実施形態は、データベースの属性値がいわゆるカテゴリ属性値を含む場合のデータベース撹乱システムである。第二実施形態で撹乱の対象となるデータベースの例を図８に示す。
カテゴリ属性値とは、例えば性別等の属性値であり、数値属性値とは異なり属性値の取り得る値がいくつかに制限されている属性値のことである。
【００３８】
以下、第一実施形態と異なる部分を中心に説明する。第一実施形態と同様の部分については説明を省略する。
第二実施形態の撹乱部１２は、図２のステップＳ１に代えて、図３のステップＳ１０，Ｓ１，Ｓ１１の処理を行う。
【００３９】
撹乱部１２は、まず、データベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値がカテゴリ属性値であるか判定する（ステップＳ１０）。
【００４０】
属性値がカテゴリ属性値でない場合には、すなわち数値属性値である場合には、撹乱部１２は、第一実施形態と同様の方法によりラプラス分布に従う値の加算を行う（ステップＳ１）。
属性値がカテゴリ属性値である場合には、撹乱部１２は、その属性値を所定の確率で他のカテゴリ属性値に置換する（ステップＳ１１）。具体的には、いわゆる維持確率ρの維持−置換撹乱を行う。
【００４１】
維持確率ρの維持−置換撹乱は、維持確率ρが予め定められているとして、維持確率ρでその属性値を変更せずに維持し、１−ρの確率でその属性値を他のカテゴリ属性値に置換する撹乱方法である。他のカテゴリ属性値に置換するとは、例えば属性が性別であり属性値が「男」である場合には、その属性値「男」を属性値「女」に置換することを意味する。維持確率ρの維持−置換撹乱の詳細については、特許文献１を参照のこと。
【００４２】
確率密度関数Ａａ（ｐ）ｖ，ｖ’が平均μ分散２σ２のラプラス分布であり、属性の種類の数が２以上である場合には、パラメータ決定部１３は、パラメータであるσ及び維持確率ρは下記式（８）を満たすように決定する。|Ｖａ|は、属性ａのカテゴリ属性値の取り得る値の数である。
【数１１】
【００４３】
ｋという１つのパラメータからσ及びρの２つのパラメータを決定する場合には、σ＝ｆ（ρ）というρからσが定まる関数、又は、ρ＝ｇ（σ）というσからρが定まる関数を予め定めておいて、σ及びρを１つのパラメータに基づくものと見なしてσ及びρを決定する。
【００４４】
まず、例えばσ＝ｆ（ρ）＝ｔａｎ（（π／４）（１−ρ））とした場合の説明をする。この場合のｋの評価式は、以下のようになる。
【数１２】
この場合、図１０に示すように、パラメータ決定部１３は、まず区間［０，１］で、評価式を上記式（９）とする二分法によりｋが所望の値となるまで反復計算して最適なρを求める（ステップＳ０７）。
【００４５】
その後、パラメータ決定部１３は、求まったρに基づいて、σ＝ｆ（ρ）＝ｔａｎ（（π／４）（１−ρ））を計算する（ステップＳ０８）。
【００４６】
つぎに、例えばρ＝ｇ（σ）＝ｆＬ０，１／２（σ）とした場合を説明する。ｆＬ０，１／２（σ）は、以下のように定義される。
【数１３】
【００４７】
この場合のｋの評価式は、以下のようになる。
【数１４】
この場合、図１１に示すように、まず、パラメータ決定部１３は、第一実施形態のステップＳ０１からステップＳ６と同様の方法により、適切なσを決定する。
【００４８】
すなわち、パラメータ決定部１３は、σ＝１とする（ステップＳ０１）。
パラメータ決定部１３は、上記式（９）によりｋ’を計算する（ステップＳ０２）。
パラメータ決定部１３は、計算されたｋ’と所望のｋとを比較する（ステップＳ０３）。
パラメータ決定部１３は、ｋ’がｋ以上であれば、σｍａｘ＝σとする（ステップＳ０４）。すなわち、σの値を、変数σｍａｘに代入する。その後、ステップＳ０６に進む。
【００４９】
パラメータ決定部１３は、ｋ’がｋ以上でなければ、σ＝２σとする（ステップＳ０５）。すなわち、現在のσの値を２倍した値を新たなσの値とする。その後、ステップＳ０２に進む。
パラメータ決定部１３は、区間［０，σｍａｘ］で、上記式（１０）を評価式とする二分法によりｋが所望の値になるまで反復計算して最適なσを求める（ステップＳ０６）。
【００５０】
その後、パラメータ決定部１３は、求まったσに基づいて、ρ＝ｇ（σ）＝ｆＬ０，１／２（σ）を計算する（ステップＳ０９）。
このようにして撹乱されたデータベースは、第一実施形態と同様に、いわゆるＰｋ−匿名性を満たす。ここでは、その証明を省略する。
【００５１】
したがって、このようにして撹乱されたデータベースは、第一実施形態と同様に、Ｐｋ−匿名性という明確な基準で匿名性が保障される。また、撹乱前のデータベース及び撹乱後のデータベースを用いずに匿名性を保障することができる。
【００５２】
［変形例等］
パラメータ決定部１３は、二分法によらなくても、パラメータを決定することができる。パラメータ決定部１３は、例えば以下のようにしてパラメータσを決定することができる。
maxu,v∈V(||u-v||1)をｍと表記し、c=(k-1)/(|R|-1)とおけば、上記式（４）は、
c≦exp(-2m/σ)
ln c≦-2m/σ
σ≦-2m/ln c
と変形することができる。したがって、パラメータ決定部１３は、数値計算である二分法を用いなくても例えば下記の式によりσを計算することができる。
【数１５】
【００５３】
パラメータ決定部１３は、同様にして、属性値の種類の数が１以上である場合には、下記式によりσを計算することができる。
【数１６】
【００５４】
並替部１４の処理は行わなくてもよい。この場合、データベースのレコードの並び替えは行われず、撹乱部１２により撹乱されたデータベースが集計装置２に送信される。集計装置２は、受信した並び替えが行われていないデータベースに基づいて集計処理を行う。
撹乱部１２が撹乱装置１に備えられ、集計部２１が集計装置２に備えられていれば、他の各部はデータベース撹乱システムを構成する装置の何れに備えられていてもよい。
【００５５】
例えば、図４に例示するように、パラメータ決定部１３が集計装置２に備えられていてもよい。この場合、パラメータ決定部１３により決定されたパラメータは、撹乱装置１に送信される。
【００５６】
また、例えば、図５に示すように、データベース撹乱システムが、撹乱装置１、集計装置２及び撹乱データサーバ装置３から構成されている場合には、パラメータ決定部１３が撹乱データサーバ装置３に備えられていてもよい。この場合、パラメータ決定部１３により決定されたパラメータは撹乱装置１に送信され、撹乱装置１により撹乱されたデータベースは撹乱データサーバ装置３を経由して集計装置２に送信される。具体的には、撹乱データサーバ装置３のデータ送受信部３１が、撹乱装置１により撹乱されたデータベースを受信して、集計装置２に送信する。
【００５７】
また、図６に例示するように、データベース撹乱システムに、撹乱装置１及び集計装置２のそれぞれが複数備えられていてもよい。
データベース撹乱装置の各部間のデータの送受信は直接行われてもよいし、図示していない記憶部を介して行われてもよい。データベース撹乱システムの各装置間のデータの送受信は直接行われてもよいし、他の装置を経由して行われてもよい。
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５９】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６０】
［追加の変形例］
なお、確率密度関数Ａａ（ｐ）ｖ，ｖ’は、例えば、下記式により定義される分散２σ２のラプラス分布による区間［α，β］の有界ノイズ関数、又は、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であってもよい。
【数１７】
α，βはα＜βの関係を満たす任意の実数である。例えば、定義域Ｖａの区間を［α，β］とする。
【００６１】
ラプラス分布及び正規分布等の確率密度関数ｆ（ｘ）による区間［α，β］の有界ノイズ関数とは、γをγ∈［α，β］として、あるγに応じて定まるδγに対して、γ＋ｘが区間［α，β］に属するｘに対しては（すなわち、区間［α−γ，β−γ］のｘに対しては）ｆγ（ｘ）＝ｆ（ｘ）／δγ、γ＋ｘが区間［α，β］に属しないｘに対しては（すなわち、区間［α−γ，β−γ］の範囲外のｘに対しては）ｆγ（ｘ）＝０となる確率密度関数ｆγのことである。確率密度関数ｆγに従う値のことを、確率密度関数ｆ（ｘ）による有界ノイズと表現してもよい。
【００６２】
確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散２σ２のラプラス分布による区間［α，β］の有界ノイズ関数である場合には、パラメータ決定部１３は、確率密度関数Ａａ（ｐ）ｖ，ｖ’が分散２σ２のラプラス分布である場合と同様にして、パラメータであるσを定める。すなわち、この場合、パラメータ決定部１３は、パラメータであるσを上記式（３）から（１０）を満たすよう定める。
【００６３】
また、確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であり、属性値の種類の数が１である場合には、パラメータ決定部１３は、下記式を満たすパラメータσを決定する。
【数１８】
【００６４】
また、確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であり、属性値の種類の数が１以上である場合には、パラメータ決定部１３は、下記式を満たすパラメータσを決定する。
【数１９】
【００６５】
さらに、第二実施形態において、確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であり、属性値の種類の数が１以上である場合には、パラメータ決定部１３は、上記式（８）から（１０）に代えて、それぞれ下記式（８’）から（１０’）を満たすパラメータを決定してもよい。
【数２０】
【００６６】
【数２１】
【００６７】
【数２２】
【符号の説明】
【００６８】
１ 撹乱装置
１１ データベース記憶部
１２ 撹乱部
１３ パラメータ決定部
１４ 並替部
２１ 集計部
２ 集計装置
【技術分野】
【０００１】
この発明は、プライバシーを保護しながらデータマイニングを行う技術に関する。
【背景技術】
【０００２】
いわゆるＰｋ−匿名性を満たすデータベース撹乱技術及びそのデータベース撹乱技術で用いられるパラメータ決定技術が、特許文献１で提案されている（例えば、特許文献１参照。）。
Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１１−１００１１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、特許文献１の技術は属性値がいわゆるカテゴリ属性値であることを想定しており、属性値がいわゆる数値属性値である場合には非特許文献１の技術を適用することができない。
【０００５】
この発明の課題は、属性値が数値属性値である場合にも適用することができる、Ｐｋ−匿名性を満たすデータベース撹乱パラメータ設定装置、方法及びプログラム並びにデータベース撹乱システムを提供することである。
【課題を解決するための手段】
【０００６】
この発明の一態様によるデータベース撹乱装置は、テーブルは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｒ|をレコードの数とし、ｅｓｓ ｉｎｆ・を・の本質的下限として、テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることによりテーブルの撹乱を行うデータベース撹乱装置に用いられる、パラメータｐを決定するデータベース撹乱パラメータ決定装置であって、下記式を満たすパラメータｐを決定するパラメータ決定部を含む。
【０００７】
【数１】
【発明の効果】
【０００８】
属性値が数値属性値である場合にも適用することができる。
【図面の簡単な説明】
【０００９】
【図１】第一実施形態のデータベース撹乱システムを説明するためのブロック図。
【図２】第一実施形態のデータベース撹乱システムを説明するための流れ図。
【図３】第二実施形態のデータベース撹乱システムを説明するための流れ図。
【図４】データベース撹乱システムの変形例を説明するためのブロック図。
【図５】データベース撹乱システムの変形例を説明するためのブロック図。
【図６】データベース撹乱システムの変形例を説明するためのブロック図。
【図７】第一実施形態で撹乱の対象となるデータベースの例を説明するための図。
【図８】第二実施形態で撹乱の対象となるデータベースの例を説明するための図。
【図９】第一実施形態のパラメータの決定方法を説明するための流れ図。
【図１０】第二実施形態のパラメータの決定方法を説明するための流れ図。
【図１１】第二実施形態のパラメータの決定方法を説明するための流れ図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、この発明の実施形態を説明する。
【００１１】
［第一実施形態］
第一実施形態のデータベース撹乱システムは、図１に例示するように、撹乱装置１及び集計装置２を備えている。
撹乱装置１は、データベース記憶部１１と、撹乱部１２と、パラメータ決定部１３とを例えば備えている。この例では、撹乱部１２は、並替部１４を備える。パラメータ決定部１３が、特許請求の範囲のデータベース撹乱パラメータ決定装置に対応している。
【００１２】
集計装置２は、集計部２１を例えば備えている。
データベース記憶部１１には、撹乱の対象となるデータベースが記憶されている。データベース記憶部１１に記憶されたデータベースについての情報は、撹乱部１２に送信される。
データベースは、図７に例示するように、複数のレコードから構成されている。
【００１３】
各レコードは、レコード識別子と少なくとも１つの属性値とから構成されている。レコード識別子は、個人を識別する識別子であり、いわゆるレコードＩＤである。レコード識別子は、例えば氏名や氏名に対応するＩＤ番号である。
各属性値は、第一実施形態では、ｎ次元実数ベクトルの部分集合Ｖに含まれるベクトルであり、いわゆる数値属性値である。ｎは、１以上の整数である。ｎ＝１であり属性が例えば「中間テストの点数」や「期末テストの点数」である場合には、属性値は０から１００までの何れかの整数である。
【００１４】
撹乱部１２は、データベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行うことによりデータベースの撹乱を行う（ステップＳ１）。撹乱されたデータベースは、並替部１４に送信される。撹乱の対象となる属性値が複数ある場合には、それらの複数の属性値を独立に撹乱してもよいし、従属に撹乱してもよい。
【００１５】
確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱とは、例えばデータベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、確率密度関数Ａａ（ｐ）ｖ，ｖ’に従う値を加算することや、後述する維持確率ρの維持−置換撹乱を行うことを意味する。
【００１６】
確率密度関数Ａａ（ｐ）ｖ，ｖ’は、例えば下記式により定義される平均μであり分散２σ２のラプラス分布である。この場合、所定のパラメータｐは、σである。
【数２】
||・||１は・のいわゆるＬ１ノルムである。
【００１７】
例えば、μ＝０とする。この場合、撹乱部１２が用いるラプラス分布は以下のようになる。
【数３】
【００１８】
以下、「ラプラス分布に従う値」について説明する。まず、ラプラス分布を含む一般の確率密度関数ｆに従う値について説明する。ここでは表記の簡略化のために、確率密度関数ｆと書く。確率密度関数ｆは上記確率密度関数Ａａ（ｐ）ｖ，ｖ’と同じと考えてよい。
１．「確率密度関数ｆに従う値」について
（１）確率密度関数ｆの定義域及び属性値が１次元の場合
（ｉ）累積分布関数Ｆ（ｘ）＝∫−∞ｘｆ（ｘ’）ｄｘ’を求める。
（ｉｉ）累積分布関数Ｆ（ｘ）の逆関数Ｆ−１を求める。
（ｉｉｉ）区間［０，１］上の一様乱数ｒを生成する。
（ｉｖ）Ｆ−１（ｒ）を「確率密度関数ｆに従う値」として出力する。
累積分布関数Ｆ（ｘ）や逆関数Ｆ−１が数式で得られる場合にはその数式に基づいてＦ−１（ｒ）を計算してもよいし、そうでない場合には数値計算によってＦ−１（ｒ）を計算してもよい。
【００１９】
（２）確率密度関数ｆの定義域及び属性値がｎ次元の場合
ｉ＝０，…，ｎ−１のそれぞれに対して、以下の（ｉ）（ｉｉ）を行う。
（ｉ）ｘ０からｘｉ−１までを固定し、ｘｉ＋１からｘｎ−１までを積分し、ｘｉだけを変数として残した確率密度関数ｆｉを求める。
【数４】
（ｉｉ）確率密度関数ｆｉの定義域は１次元なので、上記「（１）確率密度関数ｆの定義域及び属性値が１次元の場合」で示した方法と同様の方法により、「確率密度関数ｆｉに従う値」を計算する。
ｉ＝０，…，ｎ−１のそれぞれに対して「確率密度関数ｆｉに従う値」を計算することにより、ｎ個の「確率密度関数ｆｉに従う値」が得られる。
【００２０】
上記の方法を、確率密度関数がラプラス分布の場合に当てはめると以下のようになる。
２．「ラプラス分布に従う値」について
（１）ラプラス分布の定義域及び属性値が１次元の場合
（ｉ）区間［０，１］上の一様乱数ｒ、区間（０，１）上の一様乱数ｂを生成する。
（ｉｉ）（−１）ｂσｌｏｇｒ＋μを「ラプラス分布に従う値」として出力する。
【００２１】
（２）ラプラス分布の定義域及び属性値がｎ次元の場合
（ｉ）上記「（１）ラプラス分布の定義域及び属性値が１次元の場合」で示した方法と同様の方法により、ｎ個の「ラプラス分布に従う値」であるｘ０，ｘ１，…，ｘｎ−１を計算する。
（ｉｉ）これらのｘ０，ｘ１，…，ｘｎ−１を「ラプラス分布に従う値」として出力する。
【００２２】
並替部１４は、撹乱部１２により撹乱されたデータベースに含まれるレコードの順序を並び替える（ステップＳ２）。レコードが並び替えられたデータベースは、集計装置２に送信される。
【００２３】
並び替えの対象となるのは、データベースに含まれる全部又は一部のレコードである。レコードの並び替えは、一様ランダムに行われてもよいし、ランダムに行われてもよいし、一部又は全部の属性値についての昇順、降順等の所定の並替規則に基づいて行われてもよい。
【００２４】
パラメータ決定部１３は、撹乱部２のステップＳ０の処理の前に、パラメータｐを決定する（ステップＳ０）。決定されたパラメータｐは、撹乱部２に送信される。
【００２５】
例えば、確率密度関数Ａａ（ｐ）ｖ，ｖ’が一般の確率密度関数であり、属性値の数が１である場合には、パラメータ決定部１３は、パラメータｐを以下の式（１）を満たすように決定する。ｋはセキュリティパラメータであり、|Ｒ|はデータベースのレコードの数であり、ｅｓｓ ｉｎｆ・は・の本質的下限である。撹乱前の属性値ｖ，ｕの定義域をＶとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’とする。
【数５】
【００２６】
関数ｆ（ｘ）の定義域をχとすると、関数ｆ（ｘ）の本質的下限ｅｓｓ ｉｎｆ ｆ（ｘ）は、具体的には以下のように書ける。μ（｛ｆ＜ｂ｝）を、関数ｆ（ｘ）＜ｂとなる領域の測度（例えば、面積又は体積）とする。下記式のＲは実数を意味する。
【数６】
【００２７】
例えば、確率密度関数Ａａ（ｐ）ｖ，ｖ’が一般の確率密度関数であり、属性値の数が１以上である場合には、パラメータ決定部１３は、パラメータｐを以下の式（２）を満たすように決定する。属性ａに対応する確率密度関数をＡａ（ｐ）ｖ，ｖ’として、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとする。
【数７】
【００２８】
例えば、確率密度関数Ａ（ｐ）ｖ，ｖ’が平均μであり分散２σ２のラプラス分布であり、属性値の種類の数が１である場合には、パラメータ決定部１３は、パラメータであるσを下記式（３）又は（４）を満たすよう定める。
【数８】
【００２９】
属性値の種類の数が１以上である場合には、パラメータ決定部１３は、パラメータであるσを下記式（５）又は（６）を満たすように定める。
【数９】
【００３０】
パラメータ決定部１３は、例えばいわゆる二分法により、上記式（１）から（６）の何れかを満たすパラメータｐ又はσを決定する。以下、図９を参照して、確率密度関数Ａａ（ｐ）ｖ，ｖ’が平均μであり分散２σ２のラプラス分布であり、属性値の種類の数が１である場合を例に挙げて、二分法を用いてこの場合のパラメータであるσを決定する方法を説明する。
【００３１】
まず、パラメータ決定部１３は、σ＝１とする（ステップＳ０１）。
【００３２】
パラメータ決定部１３は、下記式（７）によりｋ’を計算する（ステップＳ０２）。下記式（７）は、上記式（４）に対応するものである。
【数１０】
【００３３】
パラメータ決定部１３は、計算されたｋ’と所望のｋとを比較する（ステップＳ０３）。
パラメータ決定部１３は、ｋ’がｋ以上であれば、σｍａｘ＝σとする（ステップＳ０４）。すなわち、σの値を、変数σｍａｘに代入する。その後、ステップＳ０６に進む。
【００３４】
パラメータ決定部１３は、ｋ’がｋ以上でなければ、σ＝２σとする（ステップＳ０５）。すなわち、現在のσの値を２倍した値を新たなσの値とする。その後、ステップＳ０２に進む。
パラメータ決定部１３は、区間［０，σｍａｘ］で、上記式（７）を評価式とする二分法によりｋが所望の値になるまで反復計算して最適なσを求める（ステップＳ０６）。
【００３５】
このようにして撹乱されたデータベースは、いわゆるＰｋ−匿名性を満たす。ここでは、その証明を省略する。Ｐｋ−匿名性は、データベースの各レコードと、その各レコードに対応する個人とを１／ｋ以上の確率で結びつけることができないという性質である。
したがって、このようにして撹乱されたデータベースは、Ｐｋ−匿名性という明確な基準で匿名性が保障される。また、撹乱前のデータベース及び撹乱後のデータベースを用いずに匿名性を保障することができる。
【００３６】
集計部２１は、撹乱装置１により撹乱されたデータベースを用いて集計処理を行う（ステップＳ３）。集計部２１は、例えば、参考文献１に記載された反復ベイズ手法等を用いて、クロス集計等の集計結果を推定する。
〔参考文献１〕
五十嵐大，外２名，「多値属性に適用可能な効率的プライバシー保護クロス集計」，コンピュータセキュリティシンポジウム２００８
【００３７】
［第二実施形態］
第一実施形態は、データベースの全ての属性値がいわゆる数値属性値である場合のデータベース撹乱システムであった。これに対して、第二実施形態は、データベースの属性値がいわゆるカテゴリ属性値を含む場合のデータベース撹乱システムである。第二実施形態で撹乱の対象となるデータベースの例を図８に示す。
カテゴリ属性値とは、例えば性別等の属性値であり、数値属性値とは異なり属性値の取り得る値がいくつかに制限されている属性値のことである。
【００３８】
以下、第一実施形態と異なる部分を中心に説明する。第一実施形態と同様の部分については説明を省略する。
第二実施形態の撹乱部１２は、図２のステップＳ１に代えて、図３のステップＳ１０，Ｓ１，Ｓ１１の処理を行う。
【００３９】
撹乱部１２は、まず、データベース記憶部１１から読み込んだデータベースに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値がカテゴリ属性値であるか判定する（ステップＳ１０）。
【００４０】
属性値がカテゴリ属性値でない場合には、すなわち数値属性値である場合には、撹乱部１２は、第一実施形態と同様の方法によりラプラス分布に従う値の加算を行う（ステップＳ１）。
属性値がカテゴリ属性値である場合には、撹乱部１２は、その属性値を所定の確率で他のカテゴリ属性値に置換する（ステップＳ１１）。具体的には、いわゆる維持確率ρの維持−置換撹乱を行う。
【００４１】
維持確率ρの維持−置換撹乱は、維持確率ρが予め定められているとして、維持確率ρでその属性値を変更せずに維持し、１−ρの確率でその属性値を他のカテゴリ属性値に置換する撹乱方法である。他のカテゴリ属性値に置換するとは、例えば属性が性別であり属性値が「男」である場合には、その属性値「男」を属性値「女」に置換することを意味する。維持確率ρの維持−置換撹乱の詳細については、特許文献１を参照のこと。
【００４２】
確率密度関数Ａａ（ｐ）ｖ，ｖ’が平均μ分散２σ２のラプラス分布であり、属性の種類の数が２以上である場合には、パラメータ決定部１３は、パラメータであるσ及び維持確率ρは下記式（８）を満たすように決定する。|Ｖａ|は、属性ａのカテゴリ属性値の取り得る値の数である。
【数１１】
【００４３】
ｋという１つのパラメータからσ及びρの２つのパラメータを決定する場合には、σ＝ｆ（ρ）というρからσが定まる関数、又は、ρ＝ｇ（σ）というσからρが定まる関数を予め定めておいて、σ及びρを１つのパラメータに基づくものと見なしてσ及びρを決定する。
【００４４】
まず、例えばσ＝ｆ（ρ）＝ｔａｎ（（π／４）（１−ρ））とした場合の説明をする。この場合のｋの評価式は、以下のようになる。
【数１２】
この場合、図１０に示すように、パラメータ決定部１３は、まず区間［０，１］で、評価式を上記式（９）とする二分法によりｋが所望の値となるまで反復計算して最適なρを求める（ステップＳ０７）。
【００４５】
その後、パラメータ決定部１３は、求まったρに基づいて、σ＝ｆ（ρ）＝ｔａｎ（（π／４）（１−ρ））を計算する（ステップＳ０８）。
【００４６】
つぎに、例えばρ＝ｇ（σ）＝ｆＬ０，１／２（σ）とした場合を説明する。ｆＬ０，１／２（σ）は、以下のように定義される。
【数１３】
【００４７】
この場合のｋの評価式は、以下のようになる。
【数１４】
この場合、図１１に示すように、まず、パラメータ決定部１３は、第一実施形態のステップＳ０１からステップＳ６と同様の方法により、適切なσを決定する。
【００４８】
すなわち、パラメータ決定部１３は、σ＝１とする（ステップＳ０１）。
パラメータ決定部１３は、上記式（９）によりｋ’を計算する（ステップＳ０２）。
パラメータ決定部１３は、計算されたｋ’と所望のｋとを比較する（ステップＳ０３）。
パラメータ決定部１３は、ｋ’がｋ以上であれば、σｍａｘ＝σとする（ステップＳ０４）。すなわち、σの値を、変数σｍａｘに代入する。その後、ステップＳ０６に進む。
【００４９】
パラメータ決定部１３は、ｋ’がｋ以上でなければ、σ＝２σとする（ステップＳ０５）。すなわち、現在のσの値を２倍した値を新たなσの値とする。その後、ステップＳ０２に進む。
パラメータ決定部１３は、区間［０，σｍａｘ］で、上記式（１０）を評価式とする二分法によりｋが所望の値になるまで反復計算して最適なσを求める（ステップＳ０６）。
【００５０】
その後、パラメータ決定部１３は、求まったσに基づいて、ρ＝ｇ（σ）＝ｆＬ０，１／２（σ）を計算する（ステップＳ０９）。
このようにして撹乱されたデータベースは、第一実施形態と同様に、いわゆるＰｋ−匿名性を満たす。ここでは、その証明を省略する。
【００５１】
したがって、このようにして撹乱されたデータベースは、第一実施形態と同様に、Ｐｋ−匿名性という明確な基準で匿名性が保障される。また、撹乱前のデータベース及び撹乱後のデータベースを用いずに匿名性を保障することができる。
【００５２】
［変形例等］
パラメータ決定部１３は、二分法によらなくても、パラメータを決定することができる。パラメータ決定部１３は、例えば以下のようにしてパラメータσを決定することができる。
maxu,v∈V(||u-v||1)をｍと表記し、c=(k-1)/(|R|-1)とおけば、上記式（４）は、
c≦exp(-2m/σ)
ln c≦-2m/σ
σ≦-2m/ln c
と変形することができる。したがって、パラメータ決定部１３は、数値計算である二分法を用いなくても例えば下記の式によりσを計算することができる。
【数１５】
【００５３】
パラメータ決定部１３は、同様にして、属性値の種類の数が１以上である場合には、下記式によりσを計算することができる。
【数１６】
【００５４】
並替部１４の処理は行わなくてもよい。この場合、データベースのレコードの並び替えは行われず、撹乱部１２により撹乱されたデータベースが集計装置２に送信される。集計装置２は、受信した並び替えが行われていないデータベースに基づいて集計処理を行う。
撹乱部１２が撹乱装置１に備えられ、集計部２１が集計装置２に備えられていれば、他の各部はデータベース撹乱システムを構成する装置の何れに備えられていてもよい。
【００５５】
例えば、図４に例示するように、パラメータ決定部１３が集計装置２に備えられていてもよい。この場合、パラメータ決定部１３により決定されたパラメータは、撹乱装置１に送信される。
【００５６】
また、例えば、図５に示すように、データベース撹乱システムが、撹乱装置１、集計装置２及び撹乱データサーバ装置３から構成されている場合には、パラメータ決定部１３が撹乱データサーバ装置３に備えられていてもよい。この場合、パラメータ決定部１３により決定されたパラメータは撹乱装置１に送信され、撹乱装置１により撹乱されたデータベースは撹乱データサーバ装置３を経由して集計装置２に送信される。具体的には、撹乱データサーバ装置３のデータ送受信部３１が、撹乱装置１により撹乱されたデータベースを受信して、集計装置２に送信する。
【００５７】
また、図６に例示するように、データベース撹乱システムに、撹乱装置１及び集計装置２のそれぞれが複数備えられていてもよい。
データベース撹乱装置の各部間のデータの送受信は直接行われてもよいし、図示していない記憶部を介して行われてもよい。データベース撹乱システムの各装置間のデータの送受信は直接行われてもよいし、他の装置を経由して行われてもよい。
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００５８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５９】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６０】
［追加の変形例］
なお、確率密度関数Ａａ（ｐ）ｖ，ｖ’は、例えば、下記式により定義される分散２σ２のラプラス分布による区間［α，β］の有界ノイズ関数、又は、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であってもよい。
【数１７】
α，βはα＜βの関係を満たす任意の実数である。例えば、定義域Ｖａの区間を［α，β］とする。
【００６１】
ラプラス分布及び正規分布等の確率密度関数ｆ（ｘ）による区間［α，β］の有界ノイズ関数とは、γをγ∈［α，β］として、あるγに応じて定まるδγに対して、γ＋ｘが区間［α，β］に属するｘに対しては（すなわち、区間［α−γ，β−γ］のｘに対しては）ｆγ（ｘ）＝ｆ（ｘ）／δγ、γ＋ｘが区間［α，β］に属しないｘに対しては（すなわち、区間［α−γ，β−γ］の範囲外のｘに対しては）ｆγ（ｘ）＝０となる確率密度関数ｆγのことである。確率密度関数ｆγに従う値のことを、確率密度関数ｆ（ｘ）による有界ノイズと表現してもよい。
【００６２】
確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散２σ２のラプラス分布による区間［α，β］の有界ノイズ関数である場合には、パラメータ決定部１３は、確率密度関数Ａａ（ｐ）ｖ，ｖ’が分散２σ２のラプラス分布である場合と同様にして、パラメータであるσを定める。すなわち、この場合、パラメータ決定部１３は、パラメータであるσを上記式（３）から（１０）を満たすよう定める。
【００６３】
また、確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であり、属性値の種類の数が１である場合には、パラメータ決定部１３は、下記式を満たすパラメータσを決定する。
【数１８】
【００６４】
また、確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であり、属性値の種類の数が１以上である場合には、パラメータ決定部１３は、下記式を満たすパラメータσを決定する。
【数１９】
【００６５】
さらに、第二実施形態において、確率密度関数Ａａ（ｐ）ｖ，ｖ’が、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であり、属性値の種類の数が１以上である場合には、パラメータ決定部１３は、上記式（８）から（１０）に代えて、それぞれ下記式（８’）から（１０’）を満たすパラメータを決定してもよい。
【数２０】
【００６６】
【数２１】
【００６７】
【数２２】
【符号の説明】
【００６８】
１ 撹乱装置
１１ データベース記憶部
１２ 撹乱部
１３ パラメータ決定部
１４ 並替部
２１ 集計部
２ 集計装置
【特許請求の範囲】
【請求項１】
テーブルは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｒ|をレコードの数とし、ｅｓｓ ｉｎｆ・を・の本質的下限として、上記テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行うデータベース撹乱装置に用いられる、上記パラメータｐを決定するデータベース撹乱パラメータ決定装置において、
下記式を満たすパラメータｐを決定するパラメータ決定部
【数２３】
を含むデータベース撹乱パラメータ決定装置。
【請求項２】
請求項１のデータベース撹乱パラメータ決定装置において、
α，βをα＜βの関係を満たす任意の実数とし、上記定義域Ｖａは区間［α，β］であるとして、
上記確率密度関数Ａａ（ｐ）ｖ，ｖ’は、下記式により定義される分散２σ２のラプラス分布又はそのラプラス分布による区間［α，β］の有界ノイズ関数であるとし、上記パラメータｐは上記σであるとし、||・||１を・のＬ１ノルムとして、
【数２４】
上記パラメータ決定部は、下記式を満たすパラメータσを決定する、
【数２５】
データベース撹乱パラメータ決定装置。
【請求項３】
請求項２のデータベース撹乱パラメータ決定装置において、
上記データベース撹乱装置は、上記それぞれの属性値の属性ａがカテゴリ属性である場合には、上記それぞれの属性値ｖを所定の確率１−ρで他のカテゴリ属性値に置換し、
上記パラメータｐは、上記σ及び上記ρであり、
|Ｖａ|を属性ａのカテゴリ属性値の取り得る値の数として、上記パラメータ決定部は、下記式を満たすパラメータσ及びρを決定する、
【数２６】
データベース撹乱パラメータ決定装置。
【請求項４】
請求項１のデータベース撹乱パラメータ決定装置において、
α，βをα＜βの関係を満たす任意の実数とし、上記定義域Ｖａは区間［α，β］であるとして、
上記確率密度関数Ａａ（ｐ）ｖ，ｖ’は、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であるとし、上記パラメータｐは上記σであるとし、||・||１を・のＬ１ノルムとして、
上記パラメータ決定部は、下記式を満たすパラメータσを決定する、
【数２７】
データベース撹乱パラメータ決定装置。
【請求項５】
請求項４のデータベース撹乱パラメータ決定装置において、
上記データベース撹乱装置は、上記それぞれの属性値の属性ａがカテゴリ属性である場合には、上記それぞれの属性値ｖを所定の確率１−ρで他のカテゴリ属性値に置換し、
上記パラメータｐは、上記σ及び上記ρであり、
|Ｖａ|を属性ａのカテゴリ属性値の取り得る値の数として、上記パラメータ決定部は、下記式を満たすパラメータσ及びρを決定する、
【数２８】
データベース撹乱パラメータ決定装置。
【請求項６】
テーブルは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｒ|をレコードの数とし、ｅｓｓ ｉｎｆ・を・の本質的下限として、上記テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行うデータベース撹乱装置に用いられる、上記パラメータｐを決定するデータベース撹乱パラメータ決定方法において、
パラメータ決定部が、下記式を満たすパラメータｐを決定するパラメータ決定ステップ、
【数２９】
を含むデータベース撹乱パラメータ決定方法。
【請求項７】
請求項１から５のデータベース撹乱パラメータ決定装置と、
上記データベース撹乱装置と、
を含むデータベース撹乱システム。
【請求項８】
請求項１から５の何れかのデータベース撹乱パラメータ決定装置の各部としてコンピュータを機能させるためのプログラム。
【請求項１】
テーブルは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｒ|をレコードの数とし、ｅｓｓ ｉｎｆ・を・の本質的下限として、上記テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行うデータベース撹乱装置に用いられる、上記パラメータｐを決定するデータベース撹乱パラメータ決定装置において、
下記式を満たすパラメータｐを決定するパラメータ決定部
【数２３】
を含むデータベース撹乱パラメータ決定装置。
【請求項２】
請求項１のデータベース撹乱パラメータ決定装置において、
α，βをα＜βの関係を満たす任意の実数とし、上記定義域Ｖａは区間［α，β］であるとして、
上記確率密度関数Ａａ（ｐ）ｖ，ｖ’は、下記式により定義される分散２σ２のラプラス分布又はそのラプラス分布による区間［α，β］の有界ノイズ関数であるとし、上記パラメータｐは上記σであるとし、||・||１を・のＬ１ノルムとして、
【数２４】
上記パラメータ決定部は、下記式を満たすパラメータσを決定する、
【数２５】
データベース撹乱パラメータ決定装置。
【請求項３】
請求項２のデータベース撹乱パラメータ決定装置において、
上記データベース撹乱装置は、上記それぞれの属性値の属性ａがカテゴリ属性である場合には、上記それぞれの属性値ｖを所定の確率１−ρで他のカテゴリ属性値に置換し、
上記パラメータｐは、上記σ及び上記ρであり、
|Ｖａ|を属性ａのカテゴリ属性値の取り得る値の数として、上記パラメータ決定部は、下記式を満たすパラメータσ及びρを決定する、
【数２６】
データベース撹乱パラメータ決定装置。
【請求項４】
請求項１のデータベース撹乱パラメータ決定装置において、
α，βをα＜βの関係を満たす任意の実数とし、上記定義域Ｖａは区間［α，β］であるとして、
上記確率密度関数Ａａ（ｐ）ｖ，ｖ’は、分散σ２の正規分布による区間［α，β］の有界ノイズ関数であるとし、上記パラメータｐは上記σであるとし、||・||１を・のＬ１ノルムとして、
上記パラメータ決定部は、下記式を満たすパラメータσを決定する、
【数２７】
データベース撹乱パラメータ決定装置。
【請求項５】
請求項４のデータベース撹乱パラメータ決定装置において、
上記データベース撹乱装置は、上記それぞれの属性値の属性ａがカテゴリ属性である場合には、上記それぞれの属性値ｖを所定の確率１−ρで他のカテゴリ属性値に置換し、
上記パラメータｐは、上記σ及び上記ρであり、
|Ｖａ|を属性ａのカテゴリ属性値の取り得る値の数として、上記パラメータ決定部は、下記式を満たすパラメータσ及びρを決定する、
【数２８】
データベース撹乱パラメータ決定装置。
【請求項６】
テーブルは複数のレコードを含み、各レコードはレコード識別子及び少なくとも１つの属性値を含み、ｋをセキュリティパラメータとし、|Ｒ|をレコードの数とし、ｅｓｓ ｉｎｆ・を・の本質的下限として、上記テーブルに含まれる一部又は全部の属性値のそれぞれについて、そのそれぞれの属性値ｖの属性をａとし、撹乱前の属性値ｖ，ｕの定義域をＶａとし、撹乱後の属性値ｖ’，ｕ’の定義域をＶ’ａとして、所定のパラメータｐにより定まる確率密度関数Ａａ（ｐ）ｖ，ｖ’に基づく撹乱を行い撹乱後の属性値ｖ’とすることにより上記テーブルの撹乱を行うデータベース撹乱装置に用いられる、上記パラメータｐを決定するデータベース撹乱パラメータ決定方法において、
パラメータ決定部が、下記式を満たすパラメータｐを決定するパラメータ決定ステップ、
【数２９】
を含むデータベース撹乱パラメータ決定方法。
【請求項７】
請求項１から５のデータベース撹乱パラメータ決定装置と、
上記データベース撹乱装置と、
を含むデータベース撹乱システム。
【請求項８】
請求項１から５の何れかのデータベース撹乱パラメータ決定装置の各部としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１３−１０１３２４（Ｐ２０１３−１０１３２４Ａ）
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願番号】特願２０１２−２２４７４３（Ｐ２０１２−２２４７４３）
【出願日】平成２４年１０月１０日（２０１２．１０．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２５年５月２３日（２０１３．５．２３）
【国際特許分類】
【出願日】平成２４年１０月１０日（２０１２．１０．１０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]