(57)【特許請求の範囲】
【請求項１】
データ撹乱装置とデータ再構築装置とを備えるデータ撹乱・再構築システムであって、
Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数、撹乱させる属性の番号がすべての保持する属性の番号よりも小さくなるように属性の番号を付与したとし、
前記データ撹乱装置は、
Ｋ個の属性を有するＮ個のレコードからなる初期テーブルを、一部の属性は属性値を撹乱させて他の属性は属性値を保持する遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）を生成し、
前記データ再構築装置は、
撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとする値域計算部と、
保持された属性の属性値の組み合わせｐごとに、前記遷移確率行列Ａの成分から、撹乱された属性の遷移確率を用いてＱ×Ｑの部分遷移確率行列Ａｐを生成する行列生成部と、
保持された属性の属性値の組み合わせｐごとに、前記クロス集計Ｙの成分から、保持された属性の属性値の組み合わせがｐであるクロス集計の値を用いてＱ次のベクトルＹｐを生成するベクトル生成部と、
保持された属性の属性値の組み合わせｐごとに、反復ベイズ法を用いて、撹乱させた属性に対する再構築されたクロス集計を示すＱ次のベクトルＸｐを前記部分遷移確率行列Ａｐと前記ベクトルＹｐから求め、すべてのベクトルＸｐを用いてクロス集計Ｘを再構築する反復ベイズ部と
を備える
データ撹乱・再構築システム。
【請求項２】
Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数とし、
Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）は、Ｋ個の属性を有するＮ個のレコードからなる初期テーブルを、一部の属性は属性値を撹乱させて他の属性は属性値を保持する遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計とし、
撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとする値域計算部と、
保持された属性の属性値の組み合わせｐごとに、前記遷移確率行列Ａの成分から、撹乱された属性の遷移確率を用いてＱ×Ｑの部分遷移確率行列Ａｐを生成する行列生成部と、
保持された属性の属性値の組み合わせｐごとに、前記クロス集計Ｙの成分から、保持された属性の属性値の組み合わせがｐであるクロス集計の値を用いてＱ次のベクトルＹｐを生成するベクトル生成部と、
保持された属性の属性値の組み合わせｐごとに、反復ベイズ法を用いて、撹乱させた属性に対する再構築されたクロス集計を示すＱ次のベクトルＸｐを前記部分遷移確率行列Ａｐと前記ベクトルＹｐから求め、すべてのベクトルＸｐを用いてクロス集計Ｘを再構築する反復ベイズ部と
を備えるデータ再構築装置。
【請求項３】
Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数、‖はベクトルを連結する記号とし、
Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）は、Ｋ個の属性を有するＮ個のレコードからなる初期テーブルを、一部の属性は属性値を撹乱させて他の属性は属性値を保持する遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計とし、
撹乱させる属性の番号がすべての保持する属性の番号よりも小さくなるように属性の番号を付与したとし、
撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとし、保持された属性の属性値の組み合わせの数を保持属性の値域Ｓとする値域計算部と、
ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ｉ行ｊ列目の成分が前記遷移確率行列Ａの（ｐ＋ｉ）行（ｐ＋ｊ）列目の成分であるＱ×Ｑの部分遷移確率行列Ａｐを生成する行列生成部と、
ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ベクトルＹｐ＝（ｙｐ，ｙｐ＋１，…，ｙｐ＋Ｑ−１）を生成するベクトル生成部と、
ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、反復ベイズ法を用いて、ベクトルＸｐ＝（ｘｐ，ｘｐ＋１，…，ｘｐ＋Ｑ−１）を前記部分遷移確率行列Ａｐと前記ベクトルＹｐから求め、再構築されたクロス集計ＸをＸ０‖Ｘ１‖…‖Ｘ（Ｓ−１）×Ｑとする反復ベイズ部と
を備えるデータ再構築装置。
【請求項４】
請求項２または３記載のデータ再構築装置であって、
Ｔは行列またはベクトルの転置を示す記号とし、
前記反復ベイズ部は、
ベクトルＹｐをベクトルＸｐ（０）、ｉ＝０とする成分初期化手段と、
【数１７】
0005683425.tif 000018
のようにＸｐ（ｉ＋１）を求める成分計算手段と、
ベクトルＸｐ（ｉ＋１）とベクトルＸｐ（ｉ）とのすべての要素の差の絶対値の合計があらかじめ定めた範囲外の場合にｉにｉ＋１を代入して前記成分計算手段の処理を繰返し、前記範囲内の場合にベクトルＸｐ（ｉ＋１）を、ベクトルＸｐとする成分繰返し制御手段と、
を備える
ことを特徴とするデータ再構築装置。
【請求項５】
値域計算部、行列生成部、ベクトル生成部、反復ベイズ部を備えたデータ再構築装置を用いたデータ再構築方法であって、
Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数とし、
Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）は、Ｋ個の属性を有するＮ個のレコードからなる初期テーブルを、一部の属性は属性値を撹乱させて他の属性は属性値を保持する遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計とし、
値域計算部が、撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとする値域計算ステップと、
行列生成部が、保持された属性の属性値の組み合わせｐごとに、前記遷移確率行列Ａの成分から、撹乱された属性の遷移確率を用いてＱ×Ｑの部分遷移確率行列Ａｐを生成する行列生成ステップと、
ベクトル生成部が、保持された属性の属性値の組み合わせｐごとに、前記クロス集計Ｙの成分から、保持された属性の属性値の組み合わせがｐであるクロス集計の値を用いてＱ次のベクトルＹｐを生成するベクトル生成ステップと、
反復ベイズ部が、保持された属性の属性値の組み合わせｐごとに、反復ベイズ法を用いて、撹乱させた属性に対する再構築されたクロス集計を示すＱ次のベクトルＸｐを前記部分遷移確率行列Ａｐと前記ベクトルＹｐから求め、すべてのベクトルＸｐを用いてクロス集計Ｘを再構築する反復ベイズステップと
を有するデータ再構築方法。
【請求項６】
値域計算部、行列生成部、ベクトル生成部、反復ベイズ部を備えたデータ再構築装置を用いたデータ再構築方法であって、
Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数、‖はベクトルを連結する記号とし、
Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）は、Ｋ個の属性を有するＮ個のレコードからなる初期テーブルを、一部の属性は属性値を撹乱させて他の属性は属性値を保持する遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計とし、
撹乱させる属性の番号がすべての保持する属性の番号よりも小さくなるように属性の番号を付与したとし、
値域計算部が、撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとし、保持された属性の属性値の組み合わせの数を保持属性の値域Ｓとする値域計算ステップと、
行列生成部が、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ｉ行ｊ列目の成分が前記遷移確率行列Ａの（ｐ＋ｉ）行（ｐ＋ｊ）列目の成分であるＱ×Ｑの部分遷移確率行列Ａｐを生成する行列生成ステップ、
ベクトル生成部が、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ベクトルＹｐ＝（ｙｐ，ｙｐ＋１，…，ｙｐ＋Ｑ−１）を生成するベクトル生成ステップと、
反復ベイズ部が、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、反復ベイズ法を用いて、ベクトルＸｐ＝（ｘｐ，ｘｐ＋１，…，ｘｐ＋Ｑ−１）を前記部分遷移確率行列Ａｐと前記ベクトルＹｐから求め、再構築されたクロス集計ＸをＸ０‖Ｘ１‖…‖Ｘ（Ｓ−１）×Ｑとする反復ベイズステップと
を有するデータ再構築方法。
【請求項７】
請求項５または６記載のデータ再構築方法であって、
Ｔは行列またはベクトルの転置を示す記号とし、
前記反復ベイズステップは、
ベクトルＹｐをベクトルＸｐ（０）、ｉ＝０とする成分初期化サブステップと、
【数１８】
0005683425.tif 000019
のようにＸｐ（ｉ＋１）を求める成分計算サブステップと、
ベクトルＸｐ（ｉ＋１）とベクトルＸｐ（ｉ）とのすべての要素の差の絶対値の合計があらかじめ定めた範囲外の場合にｉにｉ＋１を代入して前記成分計算サブステップを繰返し、前記範囲内の場合にベクトルＸｐ（ｉ＋１）を、ベクトルＸｐとする成分繰返し制御サブステップと、
を有する
ことを特徴とするデータ再構築方法。
【請求項８】
請求項２から４のいずれかに記載のデータ再構築装置としてコンピュータを動作させるためのデータ再構築プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータベースにおける個別データを確率的手法により秘匿しつつ統計値のみを得るデータ撹乱・再構築システム、データ再構築装置、データ再構築方法、データ再構築プログラムに関する。
【背景技術】
【０００２】
従来、データベースにおける個別データを確率的手法により秘匿しつつクロス集計結果のみを再構築して得る技術として、非特許文献１の方法がある。非特許文献１に示されているような撹乱・再構築法は、データに対し撹乱と呼ばれる確率的な処理を行うことでプライバシーを保護し、統計値を得る際には再構築と呼ばれるステップを経ることで統計値を復元する手法である。撹乱処理はデータを提供する提供者が自身で行うことが可能であるため、管理者に対してもプライバシーを保護できる。この撹乱・再構築法の中でも、維持置換撹乱と呼ばれる撹乱処理と、クロス集計と呼ばれる統計量を得るための反復ベイズ法という再構築処理を組み合わせた手法は、セキュア関数計算に比べ計算効率が良い。また、ｋ−匿名法と比較した際も同等のプライバシー保護度合いを得つつより精度の良い統計値を得られることが実験で示されている（非特許文献２）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】五十嵐大, 千田浩司, 高橋克巳, “多値属性に適用可能な効率的プライバシー保護クロス集計”, CSS2008, 2008.
【非特許文献２】永井彰, 五十嵐大, 濱田浩気, 松林達史, “クロネッカー積を含む行列積演算の最適化による効率的なプライバシ保護データ公開技術”, SCIS, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、従来技術には、秘匿データの取り得る値の範囲が大きくなると再構築の処理コストが急激に増大するという課題がある。維持置換撹乱と反復ベイズ法の組み合わせでは反復ベイズ法における計算量が支配的であり、その計算量はデータの取りうる値の広さ、すなわち全属性値の組み合わせ数に強く依存している。そのため例えば１歳刻みの年齢等データの値域が広い場合、計算量が膨大となるため、非特許文献１などに提案されている幾つかの高速化手法を用いても、現実的な時間で実行できない場合が存在する。
【０００５】
本発明は、秘匿されたデータを再構築するための処理コストを低減することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のデータ撹乱・再構築システムは、データ撹乱装置とデータ再構築装置とを備える。まず、Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数とする。データ撹乱装置は、Ｋ個の属性を有するＮ個のレコードからなる初期テーブルを、一部の属性は属性値を撹乱させて他の属性は属性値を保持する遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）を生成する。データ再構築装置は、値域計算部、行列生成部、ベクトル生成部、反復ベイズ部を備える。値域計算部は、撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとする。行列生成部は、保持された属性の属性値の組み合わせｐごとに、遷移確率行列Ａの成分から、撹乱された属性の遷移確率を用いてＱ×Ｑの部分遷移確率行列Ａｐを生成する。ベクトル生成部は、保持された属性の属性値の組み合わせｐごとに、クロス集計Ｙの成分から、保持された属性の属性値の組み合わせがｐであるクロス集計の値を用いてＱ次のベクトルＹｐを生成する。反復ベイズ部は、保持された属性の属性値の組み合わせｐごとに、反復ベイズ法を用いて、撹乱させた属性に対する再構築されたクロス集計を示すＱ次のベクトルＸｐを部分遷移確率行列ＡｐとベクトルＹｐから求め、すべてのベクトルＸｐを用いてクロス集計Ｘを再構築する。
【０００７】
なお、例えば、撹乱させる属性の番号がすべての保持する属性の番号よりも小さくなるように属性の番号を付与したとすれば、値域計算部、行列生成部、ベクトル生成部、反復ベイズ部は、以下のように構成すればよい。値域計算部は、撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとし、保持された属性の属性値の組み合わせの数を保持属性の値域Ｓとする。行列生成部は、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ｉ行ｊ列目の成分が遷移確率行列Ａの（ｐ＋ｉ）行（ｐ＋ｊ）列目の成分であるＱ×Ｑの部分遷移確率行列Ａｐを生成する。ベクトル生成部は、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ベクトルＹｐ＝（ｙｐ，ｙｐ＋１，…，ｙｐ＋Ｑ−１）を生成する。反復ベイズ部は、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、反復ベイズ法を用いて、ベクトルＸｐ＝（ｘｐ，ｘｐ＋１，…，ｘｐ＋Ｑ−１）を部分遷移確率行列ＡｐとベクトルＹｐから求め、再構築されたクロス集計ＸをＸ０‖Ｘ１‖…‖Ｘ（Ｓ−１）×Ｑとする。
【発明の効果】
【０００８】
本発明のデータ撹乱・再構築システムによれば、従来の方法との等価性が証明できた方法を用いて、データ再構築装置が、属性値を保持する属性の属性値の組み合わせごとに、それぞれ別々に再構築を行うことができる。したがって、従来と同様の結果が得られ、かつ、再構築の処理コストを低減できる。
【図面の簡単な説明】
【０００９】
【図１】本発明の処理の対象となるテーブルの例を示す図。
【図２】本発明のデータ撹乱・再構築システムの構成例を示す図。
【図３】本発明のデータ撹乱・再構築システムの処理フロー例を示す図。
【図４】反復ベイズ部１４０の機能構成例を示す図。
【図５】反復ベイズ部１４０の処理フロー例を示す図。
【発明を実施するための形態】
【００１０】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１１】
図１は、本発明の処理の対象となるテーブルの例を示す図である。図１（Ａ）は撹乱処理を行う前の初期のテーブルの例であり、図１（Ｂ）はクロス集計をした状態のテーブルの例である。初期のテーブルには、国籍、趣味、年齢、性別などの属性があり、各行のレコードには、各属性に対する属性値が記載されている。クロス集計とは、あるテーブルに対し同じ属性の組み合わせが幾つあるのかを数え上げたものである。例えば図１（Ａ）のテーブルに対するクロス集計は図１（Ｂ）のようになる。
【００１２】
本明細書では、Ｋは属性の数を示す２以上の整数、Ｎはレコードの数を示す２以上の整数、Ｍはすべての属性値の組み合わせの数、ｋは属性の番号を示す０以上Ｋ−１以下の整数、Ｍｋはｋ番目の属性の取り得る属性値の数を示す１以上の整数、‖はベクトルを連結する記号、Ｔは行列またはベクトルの転置を示す記号とする。なお、ＭとＭｋには、Ｍ＝Ｍ０・Ｍ１・…・ＭＫ−１の関係がある。
【００１３】
図２に本発明のデータ撹乱・再構築システムの構成例を示す。また、図３に本発明のデータ撹乱・再構築システムの処理フロー例を示す。図２のデータ撹乱・再構築システムは、ネットワーク９００で接続されたデータ撹乱装置２００とデータ再構築装置１００とを備える。なお、データ撹乱装置２００とデータ再構築装置１００とのデータの授受を何らかの記録媒体で行う場合には、ネットワーク９００を介して接続しておく必要はない。また、データ撹乱装置２００とデータ再構築装置１００とを同一の装置で構成してもよい。この場合も、ネットワークは必要ない。
【００１４】
撹乱・再構築の対象となる初期テーブルは、Ｋ個の属性を有するＮ個のレコードからなるとする。データ撹乱装置２００は、初期テーブルを、遷移確率行列Ａを用いて撹乱させた撹乱テーブルに対するクロス集計Ｙ＝（ｙ０，ｙ１，…，ｙＭ−１）を生成する（Ｓ２００）。クロス集計Ｙは、ネットワーク９００を介してデータ再構築装置１００に送信される。遷移確率行列Ａは、初期テーブルの一部の属性は属性値を撹乱させ、他の属性は属性値を保持する。遷移確率行列Ａには、すべての属性のすべての属性値に対して、撹乱によって遷移する属性値の確率が定義されている。ｋ番目の属性において、撹乱前の属性値ａが撹乱後に属性値ｂとなる確率をＡ（ｋ）ａｂと表現すると、
【００１５】
【数１】
0005683425.tif 000002
【００１６】
である。なお、属性値を保持する属性の場合は、ａ＝ｂの場合にＡ（ｋ）ａｂ＝１、ａ≠ｂの場合にＡ（ｋ）ａｂ＝０と設定すればよい。
【００１７】
データ再構築装置１００は、値域計算部１１０、行列生成部１２０、ベクトル生成部１３０、反復ベイズ部１４０、記録部１９０を備える。記録部１９０は、クロス集計Ｙと遷移確率行列Ａとを記録する。値域計算部１１０は、撹乱された属性の属性値の組み合わせの数を準識別子全体の値域Ｑとし、保持された属性の属性値の組み合わせの数を保持属性の値域Ｓとする（Ｓ１１０）。例えば、撹乱させる属性の数をｔ（ｔは１以上Ｋ−１以下の整数）とし、撹乱させる属性の番号ｋが０≦ｋ≦ｔ−１の整数となり、保持する属性の番号ｋがｔ≦ｋ≦Ｋ−１の整数となるように属性の番号を付与したとする。この場合には、Ｑ＝Ｍ０・Ｍ１・…・Ｍｔ−１、Ｓ＝Ｍｔ・Ｍｔ＋１・…・ＭＫ−１となる。なお、Ｍ＝Ｑ・Ｓなので、値域Ｓの計算は省略してもよい。
【００１８】
行列生成部１２０は、保持された属性の属性値の組み合わせｐごとに、遷移確率行列Ａの成分から、撹乱された属性の遷移確率を用いてＱ×Ｑの部分遷移確率行列Ａｐを生成する（Ｓ１２０）。なお、保持された属性の属性値の組み合わせｐは、Ｓ通り存在するので、Ｑ×Ｑの部分遷移確率行列ＡｐはＳ個生成される。ここで、撹乱させる属性の番号ｋが０≦ｋ≦ｔ−１となり、保持する属性の番号ｋがｔ≦ｋ≦Ｋ−１となるように属性の番号を付与した場合の具体例を示す。この場合は、保持された属性の属性値の組み合わせを示す値ｐは、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×ＱのようにＳ個のＱの倍数とする。そして、行列生成部１２０は、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ｉ行ｊ列目の成分が遷移確率行列Ａの（ｐ＋ｉ）行（ｐ＋ｊ）列目の成分であるＱ×Ｑの部分遷移確率行列Ａｐを生成ればよい。
【００１９】
ここで、保持された属性の属性値の組み合わせを示す値ｐについて、補足説明をする。まず、ｑを属性値の組み合わせを示す番号（撹乱させる属性も保持する属性も含めた属性値全体の組み合わせを示す番号）とし、組み合わせｑのときのｋ番目の属性の属性値をｑ（ｋ）とする。なお、属性値の組み合わせはＭ通り存在するので、ｑはＭ種類の番号であり、クロス値と呼ぶ。クロス値ｑは、
【００２０】
【数２】
0005683425.tif 000003
【００２１】
のように定義すればよく、この場合クロス値ｑは０以上Ｍ−１以下の整数である。そして、保持された属性の属性値の組み合わせを示す値ｐを、ｑをＱで除した商にＱを乗算した値と定義すれば、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑとなる。そして、ｐが同じ値となるクロス値ｑは、保持された属性の属性値の組み合わせが同じである。
【００２２】
ベクトル生成部１３０は、保持された属性の属性値の組み合わせｐごとに、クロス集計Ｙの成分から、保持された属性の属性値の組み合わせがｐであるクロス集計の値を用いてＱ次のベクトルＹｐを生成する（Ｓ１３０）。撹乱させる属性の番号ｋが０≦ｋ≦ｔ−１となり、保持する属性の番号ｋがｔ≦ｋ≦Ｋ−１となるように属性の番号を付与した場合であれば、ベクトル生成部１３０は、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、ベクトルＹｐ＝（ｙｐ，ｙｐ＋１，…，ｙｐ＋Ｑ−１）を生成すればよい。
【００２３】
反復ベイズ部１４０は、保持された属性の属性値の組み合わせｐごとに、反復ベイズ法を用いて、撹乱させた属性に対する再構築されたクロス集計を示すＱ次のベクトルＸｐを部分遷移確率行列ＡｐとベクトルＹｐから求め、すべてのベクトルＸｐを用いてクロス集計Ｘを再構築する（Ｓ１４０）。撹乱させる属性の番号ｋが０≦ｋ≦ｔ−１となり、保持する属性の番号ｋがｔ≦ｋ≦Ｋ−１となるように属性の番号を付与した場合であれば、反復ベイズ部１４０は、ｐ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑごとに、反復ベイズ法を用いて、ベクトルＸｐ＝（ｘｐ，ｘｐ＋１，…，ｘｐ＋Ｑ−１）を部分遷移確率行列ＡｐとベクトルＹｐから求め、再構築されたクロス集計ＸをＸ０‖Ｘ１‖…‖Ｘ（Ｓ−１）×Ｑとすればよい。
【００２４】
次に、反復ベイズ部１４０についてさらに詳細に説明する。図４には反復ベイズ部１４０の機能構成例を、図５には反復ベイズ部１４０の処理フロー例を示す。反復ベイズ部１４０は、初期設定手段１４１、繰返し手段１４２、Ｙｐ確認手段１４３、成分初期化手段１４５、成分計算手段１４６、成分繰返し制御手段１４７、出力手段１４９を備える。この説明でも、撹乱させる属性の番号ｋが０≦ｋ≦ｔ−１となり、保持する属性の番号ｋがｔ≦ｋ≦Ｋ−１となるように属性の番号を付与したとする。
【００２５】
初期設定手段１４１は、ｐに０を代入する（Ｓ１４１）。繰返し手段１４２は、ｐ＝Ｍかを確認し、Ｙｅｓの場合は後述のステップＳ１４９に進み、Ｎｏの場合は後述のステップＳ１４３に進む（Ｓ１４２）。ステップＳ１４２がＮｏの場合、Ｙｐ確認手段１４３は、Ｙｐのすべての要素が０かを確認し、Ｙｅｓの場合は後述のステップＳ１４４に進み、Ｎｏの場合は後述のステップＳ１４５に進む（Ｓ１４３）。なお、図５の“０Ｑ”は、Ｑ個の要素すべてが０であることを意味している。
【００２６】
ステップＳ１４３がＮｏの場合、成分初期化手段１４５は、ベクトルＹｐをベクトルＸｐ（０）とし、ｉ＝０とする（Ｓ１４５）。成分計算手段１４６は、
【００２７】
【数３】
0005683425.tif 000004
【００２８】
のようにＸｐ（ｉ＋１）を求める（Ｓ１４６）。成分繰返し制御手段１４７は、ベクトルＸｐ（ｉ＋１）とベクトルＸｐ（ｉ）とのすべての要素の差の絶対値の合計があらかじめ定めた範囲かを確認する（Ｓ１４７）。あらかじめ定めた範囲とは、例えば、あらかじめ定めた許容誤差未満であることなどである。範囲外の場合（ステップＳ１４７がＮｏの場合）には、成分繰返し制御手段１４７は、ｉにｉ＋１を代入してステップＳ１４６に戻る（Ｓ１４８）。範囲内の場合（ステップＳ１４７がＹｅｓの場合）には後述のステップＳ１４４に進む。
【００２９】
繰返し手段１４２は、ステップＳ１４３がＹｅｓだった場合にはベクトルＹｐをベクトルＸｐとし、ステップＳ１４７がＹｅｓだった場合にはベクトルＸｐ（ｉ＋１）をベクトルＸｐとする。そして、繰返し手段１４２は、ｐにｐ＋Ｑを代入し、ステップＳ１４２に戻る（Ｓ１４４）。ステップＳ１４２がＹｅｓの場合、出力手段１４９は、クロス集計ＸをＸ０‖Ｘ１‖…‖Ｘ（Ｓ−１）×Ｑとして出力する（Ｓ１４９）。
【００３０】
従来の反復ベイズ法の計算量が
【００３１】
【数４】
0005683425.tif 000005
【００３２】
であるのに対し、本発明の反復ベイズ部の計算量のオーダーは、
【００３３】
【数５】
0005683425.tif 000006
【００３４】
となる。また、本発明の反復ベイズ部の場合、乗算回数は、
【００３５】
【数６】
0005683425.tif 000007
【００３６】
である。例えば、保持属性の値域Ｓが１千万通り、準識別子全体の値域Ｑが２千通り、レコード数Ｎが２０万件、最も値域の広い属性の地域Ｍｋが２千通りだとすると、従来に比べ、計算量が約１５０分の１になる。
【００３７】
＜証明＞
以下に、本発明のデータ再構築装置であれば従来の反復ベイズ法と同様の結果が得られることを示す。属性の番号の付与方法、クロス値の定義、保持属性だけでの組み合わせを示す値の決め方自体は証明には影響しないので、説明を簡単にするため次のよう定める。属性の番号の付与方法は、撹乱させる属性の番号ｋが０≦ｋ≦ｔ−１となり、保持する属性の番号ｋがｔ≦ｋ≦Ｋ−１となるように属性の番号を付与したとする。また、ｃとｄとｑをクロス値（撹乱させる属性も保持する属性も含めた属性値全体の組み合わせを示す番号）とし、クロス値ｃのときのｋ番目の属性の属性値をｃ（ｋ）、クロス値ｄのときのｋ番目の属性の属性値をｄ（ｋ）、クロス値ｑのときのｋ番目の属性の属性値をｑ（ｋ）とする。そして、クロス値ｑは、
【００３８】
【数７】
0005683425.tif 000008
【００３９】
のように定義する。また、保持属性だけでの組み合わせを示す値ｐｑは、クロス値ｑをＱで除した商にＱを乗算した値とする。この場合、ｐｑ＝０，Ｑ，２×Ｑ，…，（Ｓ−１）×Ｑとなる。
【００４０】
保持属性の属性値は変化しないことから、ｔ≦ｋ≦Ｋ−１であるｋ番目の属性では、属性値ａと属性値ｂとが異なるようなすべてのａとｂの組に対して、遷移確率Ａ（ｋ）ａｂは０である。
【００４１】
撹乱によってクロス値ｃからクロス値ｄに遷移する確率Ａｃｄは、
【００４２】
【数８】
0005683425.tif 000009
【００４３】
であるので、ｔ≦ｋ≦Ｋ−１のすべてのｋについてｃ（ｋ）＝ｄ（ｋ）ならば、Ａｃｄ≠０が成り立つ。また、ｔ≦ｋ≦Ｋ−１のすべてのｋについてｃ（ｋ）＝ｄ（ｋ）ならば、保持された属性の属性値の組み合わせを示す値ｐは同じである。したがって、遷移確率行列Ａは、ｐｃとｐｄが異なるようなすべてのｃとｄの組に対して、Ａｃｄ＝０であるという拘束条件を満たすことが分かる。なお、上述の保持属性だけでの組み合わせを示す値の決め方から、ｄがｐｃ以上（ｐｃ＋Ｑ）未満の場合に、ｐｄがｐｃと同一となることに注意されたい。
【００４４】
また、従来の反復ベイズ法で計算する組み合わせｃのときのＭ次のベクトルＸｃ（ｉ＋１）は、
【００４５】
【数９】
0005683425.tif 000010
【００４６】
のように計算される。この式に上述の拘束条件を用いると、
【００４７】
【数１０】
0005683425.tif 000011
【００４８】
が成り立つ。また、同様に、
【００４９】
【数１１】
0005683425.tif 000012
【００５０】
が成り立ち、ｐｃ≦ｄ＜（ｐｃ＋Ｑ）ならばｐｄ＝ｐｃなので、
【００５１】
【数１２】
0005683425.tif 000013
【００５２】
が成り立つ。この式の右辺の分母の部分をベクトルと行列で表すと、
【００５３】
【数１３】
0005683425.tif 000014
【００５４】
となる。ただし、［Ｘ］ｄは、ベクトルＸのｄ番目の要素を表す。さらに同様に以下が成立する。
【００５５】
【数１４】
0005683425.tif 000015
【００５６】
左辺をベクトル表記で書けば、
【００５７】
【数１５】
0005683425.tif 000016
【００５８】
である。したがって、上述のステップＳ１４５〜Ｓ１４８（図５参照）での結果は、従来と同様の結果となることが分かる。
【００５９】
【数１６】
0005683425.tif 000017
【００６０】
したがって、上述のステップＳ１４３（図５参照）のようにＹｐのすべての要素が０の場合に、ステップＳ１４５〜Ｓ１４８の処理を省略できることも分かる。よって、本発明の方式の結果は、従来と同様の結果となっている。
【００６１】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６２】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００６３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００６４】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６７】
本発明は、プライバシー保護などのデータの秘密管理に利用することができる。
【符号の説明】
【００６８】
１００  データ再構築装置                １１０  値域計算部
１２０  行列生成部                      １３０  ベクトル生成部
１４０  反復ベイズ部                    １４１  初期設定手段
１４２  繰返し手段                      １４３  Ｙｐ確認手段
１４５  成分初期化手段                  １４６  成分計算手段
１４７  成分繰返し制御手段              １４９  出力手段
１９０  記録部                          ２００  データ撹乱装置
９００  ネットワーク
【図１】
0005683425.tif 000020
【図２】
0005683425.tif 000021
【図３】
0005683425.tif 000022
【図４】
0005683425.tif 000023
【図５】
0005683425.tif 000024