(57)【要約】      （修正有）【課題】安全性指標と撹乱の指標の一方を一定にしたまま他方を向上する撹乱再構築システムを提供する。【解決手段】撹乱装置１は、相関があるレコードを入力する入力部と、属性値を撹乱する際に、撹乱済属性値と属性値とが等しい場合には、予め定めた維持確率で維持置換撹乱を行い、撹乱済属性値と属性値とが等しくない場合には、一様ランダムに選択して、属性値に対する撹乱済属性値を定める撹乱部と、を含む。再構築装置２は、撹乱済レコードに対するクロス集計を入力する入力部と、維持確率と相関を用いて遷移確率行列を生成する行列生成部と、遷移確率行列を用いてクロス集計をベイズ推定しレコードに対するクロス集計の推定値を求めるベイズ推定部と、を含む。【選択図】図１
2015230358.tif 000002
【特許請求の範囲】
【請求項１】
撹乱装置と再構築装置を含む撹乱再構築システムであって、
上記撹乱装置は、
i=2,…,nについてa(i)=πi(a(1),…,a(i-1))を満たす相関π2,…,πnがあるレコード(a(1),…,a(n))を入力する入力部と、
上記属性値a(i)を撹乱する際に、j=1,…,i-1について、上記属性値a(j)を撹乱した撹乱済属性値a’(j)と上記属性値a(j)とが等しい場合には、πi(a'(1),…,a'(i-1))の中で予め定めた維持確率ρiで維持置換撹乱を行い、上記撹乱済属性値a’(j)と上記属性値a(j)とが等しくない場合には、πi(a’(1),…,a’(i-1))の元から一様ランダムに選択して、上記属性値a(i)に対する撹乱済属性値a’(i)を定める撹乱部と、
を含み、
上記再構築装置は、
撹乱済レコード{(a'(1),…,a'(n))}に対するクロス集計を入力する入力部と、
上記維持確率ρ1,…,ρnと上記相関π2,…,πnを用いて遷移確率行列を生成する行列生成部と、
上記遷移確率行列を用いて上記クロス集計をベイズ推定し上記レコード{(a(1),…,a(n))}に対するクロス集計の推定値を求めるベイズ推定部と、
を含む撹乱再構築システム。
【請求項２】
請求項１に記載の撹乱再構築システムであって、
上記撹乱部は、
E(x)はサイズがx×xの単位行列であり、U(x)はサイズがx×xの要素がすべて１の行列であり、
【数５４】
2015230358.tif 000059
はπi(a(1),…,a(i-1))の値域の位数であり、s=2,…,nについて、対角要素のi行i列目が次式で定義され、
【数５５】
2015230358.tif 000060
対角要素以外のi行j列目の要素が次式で定義される
【数５６】
2015230358.tif 000061
遷移確率行列を用いて、上記撹乱済属性値a'(i)を定めるものである
撹乱再構築システム。
【請求項３】
請求項１又は２に記載の撹乱再構築システムであって、
上記撹乱装置は、
#Tはテーブルのレコード数であり、#M1は１番目の属性の値域の位数であり、δ0=1-ρ1であり、δ1=1+(#M1-1)ρ1であり、
【数５７】
2015230358.tif 000062
はπi(a(1),…,a(i-1))の値域の位数であり、a(1),…,a(g-1)は1≦g≦n-1に対して、
【数５８】
2015230358.tif 000063
を与えるベクトルであり、b(1),…,b(g-1)は1≦g≦n-1に対して、
【数５９】
2015230358.tif 000064
を与えるベクトルであり、kは予め定めた安全性指標であり、s=2,…,n-1について、予め定めた上記維持確率ρ1,…,ρnの関係式と次式で定義される関係式とを用いて上記維持確率ρ1,…,ρnを計算する維持確率計算部をさらに含む
【数６０】
2015230358.tif 000065
撹乱再構築システム。
【請求項４】
i=2,…,nについてa(i)=πi(a(1),…,a(i-1))を満たす相関π2,…,πnがあるレコード(a(1),…,a(n))を入力する入力部と、
上記属性値a(i)を撹乱する際に、j=1,…,i-1について、上記属性値a(j)を撹乱した撹乱済属性値a’(j)と上記属性値a(j)とが等しい場合には、πi(a'(1),…,a'(i-1))の中で予め定めた維持確率ρiで維持置換撹乱を行い、上記撹乱済属性値a’(j)と上記属性値a(j)とが等しくない場合には、πi(a’(1),…,a’(i-1))の元から一様ランダムに選択して、上記属性値a(i)に対する撹乱済属性値a’(i)を定める撹乱部と、
を含む撹乱装置。
【請求項５】
i=2,…,nについてa(i)=πi(a(1),…,a(i-1))を満たす相関π2,…,πnがあるレコード{(a(1),…,a(n))}を撹乱した撹乱済レコード{(a'(1),…,a'(n))}に対するクロス集計を入力する入力部と、
予め定めた維持確率ρ1,…,ρnと上記相関π2,…,πnを用いて遷移確率行列を生成する行列生成部と、
上記遷移確率行列を用いて上記クロス集計をベイズ推定し上記レコード{(a(1),…,a(n))}に対するクロス集計の推定値を求めるベイズ推定部と、
を含み、
上記撹乱済レコード{(a'(1),…,a'(n))}は、上記属性値a(i)を撹乱する際に、j=1,…,i-1について、上記属性値a(j)を撹乱した撹乱済属性値a’(j)と上記属性値a(j)とが等しい場合には、πi(a'(1),…,a'(i-1))の中で予め定めた維持確率ρiで維持置換撹乱を行い、上記撹乱済属性値a’(j)と上記属性値a(j)とが等しくない場合には、πi(a’(1),…,a’(i-1))の元から一様ランダムに選択して上記撹乱済属性値a’(i)を定めたものである
再構築装置。
【請求項６】
入力部が、i=2,…,nについてa(i)=πi(a(1),…,a(i-1))を満たす相関π2,…,πnがあるレコード(a(1),…,a(n))を入力する入力ステップと、
撹乱部が、上記属性値a(i)を撹乱する際に、j=1,…,i-1について、上記属性値a(j)を撹乱した撹乱済属性値a’(j)と上記属性値a(j)とが等しい場合には、πi(a'(1),…,a'(i-1))の中で予め定めた維持確率ρiで維持置換撹乱を行い、上記撹乱済属性値a’(j)と上記属性値a(j)とが等しくない場合には、πi(a’(1),…,a’(i-1))の元から一様ランダムに選択して、上記属性値a(i)に対する撹乱済属性値a’(i)を定める撹乱ステップと、
行列生成部が、上記維持確率ρ1,…,ρnと上記相関π2,…,πnを用いて遷移確率行列を生成する行列生成ステップと、
ベイズ推定部が、上記遷移確率行列を用いて上記撹乱済レコード{(a'(1),…,a'(n))}に対するクロス集計をベイズ推定し上記レコード{(a(1),…,a(n))}に対するクロス集計の推定値を求めるベイズ推定ステップと、
を含む撹乱再構築方法。
【請求項７】
請求項４に記載の撹乱装置もしくは請求項５に記載の再構築装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報をプライバシー保護のために撹乱し、撹乱された情報から統計量を求める撹乱再構築技術に関する。
【背景技術】
【０００２】
撹乱再構築とは、情報提供者が情報を提供する際に自らテーブルに対して行うプライバシー保護のための撹乱と、マイニング者が撹乱されたテーブルからクロス集計のみの統計量を取り出す再構築とからなる（非特許文献１参照）。再構築によって得られるクロス集計は元のテーブルから得られるクロス集計に対して小さい誤差で復元される。また、撹乱の程度と安全性の指標であるPk-匿名性のパラメタの関係について関係式が導出されている（非特許文献２参照）。
【０００３】
プライバシー保護データ公開技術を実現させる技術の一つである維持置換撹乱の概要を説明する。保護の対象となるデータは複数の情報提供者から集約されたデータの集合であり、テーブルとして表現される。各情報提供者からのデータはテーブル上では一行に表現され、各行をレコードと呼ぶ。各レコードはあらかじめ定められた項目に対する値から成り立っており、この項目を属性と呼ぶ。属性の取り得る範囲を属性の値域と呼ぶ。
【０００４】
表１にテーブルの例を示す。表１の例では、一行目の“性別”及び“年代”が属性であり、二行目以降の“女性, 20代”、“男性, 20代”等がレコードである。
【０００５】
【表１】
2015230358.tif 000003
【０００６】
一般的な各属性の値域がM1,…,Mn（nは自然数であり、属性の数を表す）であるテーブルについて、各属性の取り得る範囲をMi={1,…,mi}までの値に数値化したテーブルからクロス集計を求めるためには次のような操作を行う。なお、数値化とは、例えば表１において、“男性”であれば“１”を設定し、“女性”であれば“２”を設定するような変換である。上記の表１を数値化した例を以下に示す。
【０００７】
（{男性,10代},{男性,20代},{女性,10代},{女性,20代}）
=（61,45,43,50）
数値化された一般のテーブルを表２に示す。
【０００８】
【表２】
2015230358.tif 000004
【０００９】
数値化したテーブルから以下のようにしてクロス集計を求めることができる。まず、初期のクロス集計として、長さがm（=Πi=1nmi）の0ベクトル（0,…,0）を定める。次に、jを1からレコード数#Tまでの整数をわたらせて、j番目のレコード(a(j-1)n+1,a(j-1)n+2,…,ajn)に対して初期に定めた0ベクトルの
【００１０】
【数１】
2015230358.tif 000005
【００１１】
番目の要素について順次カウントする。
【００１２】
撹乱再構築とは、情報提供者が情報を提供する際に自らテーブルに対して行うプライバシー保護のための撹乱と、マイニング者が撹乱されたテーブルからクロス集計のみの統計量を取り出す再構築とからなる。このようなことが可能なのは撹乱がなされたテーブルで個々のデータの情報量が低下しても統計量としては再構築アルゴリズムによって期待される値に収束するからである。
【００１３】
撹乱では各情報提供者がデータを確率的に変化させる。テーブルにおける各属性の属性値を一定の確率のもとで維持させ、それ以外であれば属性値から一様ランダムに遷移させる。また、撹乱では属性ごとに確率を設定してレコード内の属性値を確率的に置換しプライバシー保護を図る。撹乱の操作は属性の値域Miに応じて次のようにサイズがmi×miであるような遷移確率行列Aiで表現できる。
Ai=((1-ρi)/mi)U(mi)+ρiE(mi)
ここで、U(mi)はサイズがmi×miの要素がすべて１の行列であり、E(mi)はサイズがmi×miの単位行列であり、ρiはその要素をどの程度維持するかを表す定数である。ρiは維持確率と呼ばれる。
【００１４】
遷移確率行列Aiのs行t列目の要素(Ai)stは、値がsからtに遷移する確率を意味し、具体的には以下のようになる。
【００１５】
【数２】
2015230358.tif 000006
【００１６】
上記の表１の例で、“性別”の属性の維持確率を0.2とし、“年代”の属性の維持確率を0.6とした場合に、属性“性別”の遷移確率行列A性別及び属性“年代”の遷移確率行列A年代は、具体的に以下のような形となる。
【００１７】
【数３】
2015230358.tif 000007
【００１８】
例えば、要素(A性別)12=0.4は、男性“１”から女性“２”にデータが撹乱される確率が0.4であることを意味している。
【００１９】
複数の属性に対して遷移確率行列{Ai}（i=1,…,n）が与えられている際に、レコードが撹乱後にあるレコードに遷移する確率を遷移確率行列のクロネッカー積
【００２０】
【数４】
2015230358.tif 000008
【００２１】
で表現できる。
【００２２】
行列のクロネッカー積は次のように定義される演算である。サイズがmAである正方行列A=(aij)とサイズがmBである正方行列B=(bij)に対して、クロネッカー積を次のように定める。
【００２３】
【数５】
2015230358.tif 000009
【００２４】
ここで、aijBとは行列Bのaijによるスカラー倍である。なお、行列Aと行列Bのクロネッカー積のサイズはmA×mBである。
【００２５】
上記した遷移確率行列A性別と遷移確率行列A年代とのクロネッカー積は以下のようになる。
【００２６】
【数６】
2015230358.tif 000010
【００２７】
ここで、例えば要素
【００２８】
【数７】
2015230358.tif 000011
【００２９】
は(女性,10代)から(女性,20代)にデータが撹乱される確率が0.12であることを意味する。
【００３０】
再構築では、撹乱で用いた遷移確率行列A1,…,Anのクロネッカー積
【００３１】
【数８】
2015230358.tif 000012
【００３２】
と、撹乱後のテーブルから得られるクロス集計yとからベイズ推定法に基づいて元のテーブルのクロス集計の推定を行う。推定のアルゴリズムは下記表３のようになる。
【００３３】
【表３】
2015230358.tif 000013
【００３４】
ここで、iは反復回数を表し、v1,v2はベクトルであり、v1*v2はベクトルの成分ごとの積を表し、v1/v2はベクトルの成分ごとの商を表し、|v1|L1はベクトルのL1距離、すなわち要素の絶対値の総和であり、εはあらかじめ定める収束半径である。
【００３５】
以上のクロス集計とベイズ推定法を用いた撹乱再構築法において、クロス集計の取り方を
【００３６】
【数９】
2015230358.tif 000014
【００３７】
番目の要素をカウントすることや、複数の遷移確率行列をクロネッカー積を用いて計算することを行ったが、クロス集計の要素の順番を適当に変えた場合には、遷移確率行列をクロス集計の要素の順番に合わせて変えればよい。すなわちクロス集計や遷移確率行列の形に依存せず実装できる。
【００３８】
従来のk-匿名性はテーブル形式のデータベースの保護処理において、“保護処理後のデータの中に、どのデータ行に関しても同じデータ行が自身を含めてk個以上存在する”ことであり、直観的には、どのレコードも持ち主をk人以下に絞り込めないことを保証する指標である。この指標の確率的な拡張として非特許文献２において、Pk-匿名性が定義されている。すなわちPk-匿名性を“データの持ち主を1/k以上の確信度に絞り込めない”こととして定義している。任意のテーブルTに対して、維持置換撹乱に限らず任意の遷移確率行列Aを用いて撹乱する際のkとAの関係式は以下であることが非特許文献２に記載されている。ここで、#TはテーブルTのレコード数である。また、Rはレコード空間であり、レコードの取るべき値の集合である。
【００３９】
【数１０】
2015230358.tif 000015
【００４０】
この結果を維持置換撹乱に用いれば、以下のように維持確率ρiと安全性指標kの関係式が示される。属性の値域がm1,…,mnでありレコード数が#Tのテーブルにおいて、維持確率ρ1,…,ρnでの撹乱は、
【００４１】
【数１１】
2015230358.tif 000016
【００４２】
として、Pk-匿名性を満たす。
【先行技術文献】
【非特許文献】
【００４３】
【非特許文献１】五十嵐大、千田浩司、高橋克巳、「多値属性に適用可能な効率的プライバシー保護クロス集計」、コンピューターセキュリティシンポジウム2008
【非特許文献２】五十嵐大、千田浩司、高橋克巳、「k-匿名性の確率的指標への拡張とその適用例」、コンピューターセキュリティシンポジウム2009
【発明の概要】
【発明が解決しようとする課題】
【００４４】
従来技術では、元のデータから取得したクロス集計と撹乱再構築後に取得したクロス集計とのL1距離による精度が低い場合がある。特に、属性の個数が多い場合や属性値が大きい場合に顕著である。精度を下げる一つの原因として、従来法では属性を併せて実装を行う際に現実には不要な組み合わせも扱っていることが挙げられる。例えば、属性を“年齢層”と“自動車の運転の有無”とした場合に、{(10代前半, 車を運転する)}といったあり得ない組み合わせの属性値を扱うことになる。
【００４５】
この発明の目的は、上記のような現実にはあり得ない組み合わせを扱うことがなく分析精度の高い撹乱再構築技術を提供することである。
【課題を解決するための手段】
【００４６】
上記の課題を解決するために、この発明の撹乱再構築システムは、撹乱装置と再構築装置を含む。撹乱装置は、i=2,…,nについてa(i)=πi(a(1),…,a(i-1))を満たす相関π2,…,πnがあるレコード(a(1),…,a(n))を入力する入力部と、属性値a(i)を撹乱する際に、j=1,…,i-1について、属性値a(j)を撹乱した撹乱済属性値a’(j)と属性値a(j)とが等しい場合には、πi(a'(1),…,a'(i-1))の中で予め定めた維持確率ρiで維持置換撹乱を行い、撹乱済属性値a’(j)と属性値a(j)とが等しくない場合には、πi(a’(1),…,a’(i-1))の元から一様ランダムに選択して、属性値a(i)に対する撹乱済属性値a’(i)を定める撹乱部と、を含む。再構築装置は、撹乱済レコード{(a'(1),…,a'(n))}に対するクロス集計を入力する入力部と、維持確率ρ1,…,ρnと相関π2,…,πnを用いて遷移確率行列を生成する行列生成部と、遷移確率行列を用いてクロス集計をベイズ推定しレコード{(a(1),…,a(n))}に対するクロス集計の推定値を求めるベイズ推定部と、を含む。
【発明の効果】
【００４７】
この発明の撹乱再構築技術によれば、属性の相関を使用することで現実とはあり得ない組合せを扱うことがなく撹乱再構築が行えるため、分析精度が向上する。
【図面の簡単な説明】
【００４８】
【図１】図１は、撹乱再構築システムの機能構成を例示する図である。
【図２】図２は、第一実施形態の撹乱装置の機能構成を例示する図である。
【図３】図３は、第一実施形態の再構築装置の機能構成を例示する図である。
【図４】図４は、第一実施形態の撹乱方法の処理フローを例示する図である。
【図５】図５は、第一実施形態の再構築方法の処理フローを例示する図である。
【図６】図６は、第二実施形態の撹乱装置の機能構成を例示する図である。
【図７】図７は、第二実施形態の撹乱方法の処理フローを例示する図である。
【発明を実施するための形態】
【００４９】
この発明の撹乱再構築技術は、属性に相関がある場合について、その属性の相関を利用して撹乱と再構築を行う。
【００５０】
＜属性の相関＞
テーブルに予め定められている属性には相関関係がある場合がある。まず、この相関の具体例と一般の定義について説明する。例えば、北海道・東北、関東、北陸等の地方という属性と、北海道、青森、岩手、秋田等の都道府県という属性には、地方の要素を１つ定めた時に都道府県のとるべき要素の部分集合が定まるという相関がある。具体的には、属性“地方”の値域M地方と属性“都道府県”の値域M都道府県を、
M地方={北海道・東北,関東,北陸,…}
M都道府県={北海道,青森,岩手,秋田,…}
とする。このときに、2M都道府県をM都道府県の部分集合族として以下のような写像が定まる。
π:M地方→2M都道府県
北海道・東北→{北海道,青森,岩手,秋田,宮城,山形,福島},
関東→{茨城,栃木,群馬,埼玉,千葉,東京,神奈川},
…→{…}.
【００５１】
次に属性の相関の一般化を行う。属性とその値域M1,M2,…,Mnに対して、それらの相関とは以下のように定義される写像の列{π2,…,πn}のことである。
【００５２】
【数１２】
2015230358.tif 000017
【００５３】
ここで、集合Mに対して、2Mはその部分集合族を表す。
【００５４】
相関を考慮しない従来技術の場合は、レコード（a1,…,an）とその値域M1,…,Mnに対して、
【００５５】
【数１３】
2015230358.tif 000018
【００５６】
という定写像を与えていたことになり、この相関の定義が従来の場合の拡張であることがわかる。また、2≦j≦nとj-1個のベクトル(i(1),…,i(j-1))∈M1×…×Mj-1に対して集合πj(i(1),…,i(j-1))を、
【００５７】
【数１４】
2015230358.tif 000019
【００５８】
と表記できる。逆に、
【００５９】
【数１５】
2015230358.tif 000020
【００６０】
としたときにはπj(i(1),…,i(j-1))の値域の位数を表すものとする。
【００６１】
この相関に伴い、レコードの表現の仕方が変わる。従来のレコードでは属性の値域M1,…,Mnの元を単純に並べる。一方で相関付の場合は、i(2)∈π2(i(1)),i(3)∈π3(i(1),i(2)),…,i(n)∈πn(i(1),i(2),…,i(n-1))を満足する(i(1),…,i(n))のような元を並べる。
【００６２】
この相関に伴い、クロス集計の定め方も変わる。従来のクロス集計では２つの属性の場合では、
{(1,M2の元のブロック),(2,M2の元のブロック),…,(m1,M2の元のブロック)}
という形をしている。相関を考慮した場合には、
{(1,π2(1)の元のブロック),(2,π2(2)の元のブロック),…,(m1,π2(m1)の元のブロック)}
となる。なお、この際のクロス集計を表す長さは２番目の値域M2の部分集合π2(i(1))の位数の総和になり、
【００６３】
【数１６】
2015230358.tif 000021
【００６４】
である。また、レコード(i(1),i(2))に対して、クロス集計を表す長さLのベクトルに対して
【００６５】
【数１７】
2015230358.tif 000022
【００６６】
番目をカウントさせればよい。
【００６７】
これを踏まえて、任意の属性の個数に対するクロス集計は以下のようになる。レコード(i(1),i(2),…,i(n))のクロス集計を表すベクトルの長さLは、n番目の要素の値域Mnの部分集合πn(i(1),i(2),…,i(n-1))の位数の総和になり、
【００６８】
【数１８】
2015230358.tif 000023
【００６９】
となる。また、レコード(i(1),i(2),…,i(n))に対して、クロス集計を表す長さLのベクトルに対して、
【００７０】
【数１９】
2015230358.tif 000024
【００７１】
番目をカウントさせればよい。ここで、ベクトルの大小関係(t(1),…,t(n-1))<(s(1),…,s(n-1))は辞書式順序であり、すなわち適当なa（1≦a≦n-1）が存在して、j<aに対してt(j)=s(j)とt(a)<s(a)が成立することである。
【００７２】
＜属性間に相関がある場合の撹乱方法＞
属性間に相関{π2,…,πn}がある場合に、撹乱の方法を以下のように変化させる。
【００７３】
（入力）レコード(a(1),…,a(n))∈M1×…×Mnである。ここで、a(1),…,a(n)は、a(2)∈π2(a(1)),a(3)∈π3(a(1),a(2)),…,a(n)∈πn(a(1),a(2),…,a(n-1))を満足する。
【００７４】
（出力）レコード(a(1),…,a(n))を撹乱した撹乱済レコード(a'(1),…,a'(n))∈M1×…×Mnである。
【００７５】
（ステップ１）属性値a(1)に対しては従来と同じく維持確率ρ1で維持置換撹乱を行い、属性値a(1)∈M1に対して撹乱済属性値a'(1)∈M1を定める。
【００７６】
（ステップ２）属性値a(2)∈π2(a(1))を撹乱する場合、a(1)=a'(1)であればπ2(a'(1))の中で維持確率ρ2で維持置換撹乱を行い撹乱済属性値a'(2)を定め、そうでなければπ2(a'(1))の中の元を一様ランダムに取り撹乱済属性値a'(2)を定める。
【００７７】
（ステップ３）属性値a(3)∈π3(a(1),a(2))を撹乱する場合、j=1,2に対して、a(j)=a'(j)であればπ3(a'(1),a'(2))の中で維持確率ρ3で維持置換撹乱を行い撹乱済属性値a'(3)を定め、そうでなければπ3(a'(1),a'(2))の中の元を一様ランダムに取り撹乱済属性値a'(3)を定める。
【００７８】
ステップ１からステップ３までと同様にステップ４からステップn-1までを実行し、撹乱済属性値a'(4),…,a'(n-1)を定める。
【００７９】
（ステップn）属性値a(n)∈πn(a(1),a(2),…,a(n-1))を撹乱する場合、j=1,2,…,n-1に対して、a(j)=a'(j)であればπn(a'(1),a'(2),…,a'(n-1))の中で維持確率ρnで維持置換撹乱を行い撹乱済属性値a'(n)を定め、そうでなければπn(a'(1),a'(2),…,a'(n-1))の中の元を一様ランダムに取り撹乱済属性値a'(n)を定める。
【００８０】
従来の相関がない場合の撹乱と同様に、この相関付の撹乱は遷移確率行列として表現できる。
【００８１】
最初の属性に対する遷移確率行列A1は従来と同じ遷移確率行列が定まる。
【００８２】
【数２０】
2015230358.tif 000025
【００８３】
ここで、E(m1)はサイズがm1×m1の単位行列であり、U(m1)はサイズがm1×m1の要素がすべて１の行列である。
【００８４】
２つ目の属性に対する遷移確率行列A2は各π2(i(1))×π2(j(1))ごとのブロック行列
【００８５】
【数２１】
2015230358.tif 000026
【００８６】
として表現でき、i(1)=j(1)のときには、
【００８７】
【数２２】
2015230358.tif 000027
【００８８】
であり、i(1)≠j(1)のときには、U(n1,n2)をサイズがn1×n2の要素がすべて１の行列として、
【００８９】
【数２３】
2015230358.tif 000028
【００９０】
となる。以降、同様に遷移確率行列A3,A4,…,Anが定まる。具体的にはs=2,…,nに対して遷移確率行列Asはπs(i(1),i(2),…,i(s-1))×πs(j(1),j(2),…,j(s-1))毎のブロック行列として表現できる。それぞれのブロック行列は(i(1),i(2),…,i(s-1))=(j(1),j(2),…,j(s-1))のときには、
【００９１】
【数２４】
2015230358.tif 000029
【００９２】
であり、(i(1),i(2),…,i(s-1))≠(j(1),j(2),…,j(s-1))のときには、
【００９３】
【数２５】
2015230358.tif 000030
【００９４】
となる。次に個々に定められた遷移確率行列に関して、相関を持った複数の属性についての遷移確率行列にするために、以下の行列の演算を定義する。
【００９５】
サイズがpA×pAの行列A=(aij)とpA×pA個のブロック行列で生成される行列B=(Cij)（ここでCijは行列）に対して、演算
【００９６】
【数２６】
2015230358.tif 000031
【００９７】
を以下のように定める。
【００９８】
【数２７】
2015230358.tif 000032
【００９９】
ここで、aijCijはCijのaijスカラー倍である。
【０１００】
一つの属性ごとに定めた行列に対して、A1,A2,…,Anに対して複数の属性を含めた行列は上記で定義される行列の演算を使えば、以下のように表現可能である。
【０１０１】
【数２８】
2015230358.tif 000033
【０１０２】
＜属性間に相関がある場合の再構築方法＞
属性間に相関がある場合の撹乱方法は、撹乱の際に生成した遷移確率行列
【０１０３】
【数２９】
2015230358.tif 000034
【０１０４】
を用いてベイズ推定法を行えばよく、その他の部分は従来の再構築方法と同様にして再構築することができる。
【０１０５】
＜安全性指標と維持確率の関係式＞
上記で定めた遷移確率行列
【０１０６】
【数３０】
2015230358.tif 000035
【０１０７】
に対して、安全性指標kと維持確率ρ1,…,ρnの関係式を導く。
【０１０８】
任意のテーブルTに対して、維持置換撹乱に限らず、任意の遷移確率行列Aを用いて撹乱する際のkとAの関係式は以下である（非特許文献２参照）。
【０１０９】
【数３１】
2015230358.tif 000036
【０１１０】
この関係式を用いて、相関付きの遷移確率行列の際の安全性指標kと維持確率ρ1,…,ρnの関係式を導く。
【０１１１】
まず、簡単のためにn=2の場合について説明する。以下の条件を仮定しても一般性を失わない。
【０１１２】
【数３２】
2015230358.tif 000037
【０１１３】
レコードu,u’,v,v’をそれぞれπ2(i1(1)),π2(i2(1)),π2(j1(1)),π2(j2(1))の元から選ぶ。また記号としてδ0=1-ρ1,δ1=1+(#M1-1)ρ1とする。ここで、#M1は１番目の属性の値域の位数である。
【０１１４】
kとAの関係式における最小値min(Auv’Avu’)/(Auu’Avv’)は、i1(1),i2(1),j1(1),j2(1)の値の関係により、求め方が以下のように異なる。
（ケース１）i1(1)≠j1(1)かつi2(1)≠j2(1)かつi1(1)≠j2(1)かつi2(1)≠j1(1)の場合
【０１１５】
【数３３】
2015230358.tif 000038
【０１１６】
（ケース２）i1(1)≠j1(1)かつi2(1)≠j2(1)かつi1(1)＝j2(1)かつi2(1)≠j1(1)の場合
【０１１７】
【数３４】
2015230358.tif 000039
【０１１８】
（ケース３）i1(1)≠j1(1)かつi2(1)≠j2(1)かつi1(1)＝j2(1)かつi2(1)＝j1(1)の場合
【０１１９】
【数３５】
2015230358.tif 000040
【０１２０】
（ケース４）i1(1)＝j1(1)かつi2(1)≠j2(1)かつi1(1)≠j2(1)かつi2(1)≠j1(1)の場合
【０１２１】
【数３６】
2015230358.tif 000041
【０１２２】
（ケース５）i1(1)＝j1(1)かつi2(1)≠j2(1)かつi1(1)＝j2(1)かつi2(1)≠j1(1)の場合
【０１２３】
【数３７】
2015230358.tif 000042
【０１２４】
（ケース６）i1(1)＝j1(1)かつi2(1)＝j2(1)かつi1(1)≠j2(1)かつi2(1)≠j1(1)の場合
【０１２５】
【数３８】
2015230358.tif 000043
【０１２６】
（ケース７）i1(1)＝j1(1)かつi2(1)＝j2(1)かつi1(1)＝j2(1)かつi2(1)＝j1(1)の場合
【０１２７】
【数３９】
2015230358.tif 000044
【０１２８】
最小値min(Auv’Avu’)/(Auu’Avv’)は上記のケース３、６、７を踏まえればよく、次式のようになる。
【０１２９】
【数４０】
2015230358.tif 000045
【０１３０】
一般の属性の個数の場合について以下に記す。1≦g≦n-1に対して、
【０１３１】
【数４１】
2015230358.tif 000046
【０１３２】
を与えるベクトルを(a(1),…,a(g))とし、
【０１３３】
【数４２】
2015230358.tif 000047
【０１３４】
を与えるベクトルを(b(1),…,b(g))とする。
【０１３５】
レコードu,u',v,v'をそれぞれ、
【０１３６】
【数４３】
2015230358.tif 000048
【０１３７】
とする。
【０１３８】
まず、第１要素i1(1),j1(1),i2(1),j2(1)の比較として最小値を与えるのは、以下の３つのケースのいずれかである。
（ケース３）i1(1)≠j1(1)かつi2(1)≠j2(1)かつi1(1)＝j2(1)かつi2(1)＝j1(1)の場合
（ケース６）i1(1)＝j1(1)かつi2(1)＝j2(1)かつi1(1)≠j2(1)かつi2(1)≠j1(1)の場合
（ケース７）i1(1)＝j1(1)かつi2(1)＝j2(1)かつi1(1)＝j2(1)かつi2(1)＝j1(1)の場合
【０１３９】
ケース３の場合の次のステップとして、第２要素以降での比較を行う。i1(1)≠j1(1)かつi2(1)≠j2(1)であるので、すべてのg≧2においてi1(g)≠j1(g)かつi2(g)≠j2(g)が従う。また、このときに最小値の候補を与えるのは、すべてのg≧2においてi1(g)＝j2(g)かつi2(g)＝j1(g)のとき（ここで、どこかに≠があった場合にはケース２、４、５の場合と同じようなことが起きてしまう）であり、その値は、
【０１４０】
【数４４】
2015230358.tif 000049
【０１４１】
である。
【０１４２】
ケース６の場合の次のステップとして、第２要素以降での比較を行う。i1(1)≠j2(1)かつi2(1)≠j1(1)であるので、すべてのg≧2においてi1(g)≠j2(g)かつi2(g)≠j1(g)が従う。また、このときに最小値の候補を与えるのは、すべてのg≧2においてi1(g)＝j1(g)かつi2(g)＝j2(g)のとき（ここで、どこかに≠があった場合にはケース２、４、５の場合と同じようなことが起きてしまう）であり、その値は、
【０１４３】
【数４５】
2015230358.tif 000050
【０１４４】
である。
【０１４５】
ケース７の場合の次のステップとして、第２要素以降での比較を行う。i1(2),j1(2),i2(2),j2(2)の場合について第１要素と同じく以下の３つのケースに分かれる。
（ケース７．３）i1(1)≠j1(1)かつi2(1)≠j2(1)かつi1(1)＝j2(1)かつi2(1)＝j1(1)の場合
（ケース７．６）i1(1)＝j1(1)かつi2(1)＝j2(1)かつi1(1)≠j2(1)かつi2(1)≠j1(1)の場合
（ケース７．７）i1(1)＝j1(1)かつi2(1)＝j2(1)かつi1(1)＝j2(1)かつi2(1)＝j1(1)の場合
【０１４６】
ケース７．３やケース７．６の場合にはケース３やケース６の場合と同じ処理に帰着し、最小値の候補の計算が可能である。ケース７．７の場合には、再度第３要素の比較で最小値の候補を求めればよい。
【０１４７】
以下、帰納的に求めた最小値の候補を示す。s=2,…,n-1について、
【０１４８】
【数４６】
2015230358.tif 000051
【０１４９】
及び
【０１５０】
【数４７】
2015230358.tif 000052
【０１５１】
である。以上をまとめると、最小値min(Auv’Avu’)/(Auu’Avv’)は以下のようになる。
【０１５２】
【数４８】
2015230358.tif 000053
【０１５３】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【０１５４】
［第一実施形態］
この発明の第一実施形態は、維持確率を入力として、属性間に相関のあるレコードを撹乱する撹乱装置と、撹乱されたレコードを用いたクロス集計から元のレコードに対するクロス集計の推定値を求める再構築装置とから構成される撹乱再構築システム及び方法である。
【０１５５】
第一実施形態の撹乱再構築システムは、図１に示すように、撹乱装置１と再構築装置２を含む。撹乱装置１と再構築装置２は共に通信網９に接続される。通信網９は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネット、WAN（Wide Area Network）、LAN（Local Area Network）、公衆交換電話網、専用データ回線などで構成することができる。撹乱装置１と再構築装置２との通信は暗号化等により安全性が確保された通信路であることが望ましい。また、撹乱装置１と再構築装置２とは必ずしも通信網９を介してオンラインで通信可能である必要はない。例えば、撹乱装置１が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から再構築装置２へオフラインで入力するように構成してもよい。その場合、通信網９はなくても問題ない。
【０１５６】
撹乱装置１は、図２に示すように、入力部１０、撹乱部１２及び出力部１４を例えば含む。撹乱装置１は、属性間に相関がある複数の属性と属性毎の維持確率とを入力として、その属性を撹乱した撹乱済属性を出力する。
【０１５７】
撹乱装置１は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。撹乱装置１は、例えば、中央演算処理装置の制御のもとで各処理を実行する。撹乱装置１に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。また、撹乱装置１の各処理部の少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【０１５８】
再構築装置２は、図３に示すように、入力部２０、行列生成部２２、ベイズ推定部２４及び出力部２６を例えば含む。再構築装置２は、撹乱済属性から求めたクロス集計と属性間の相関とを入力として、元の属性に対するクロス集計の推定値を出力する。
【０１５９】
再構築装置２は、例えば、中央演算処理装置（CPU: Central Processing Unit）、主記憶装置（RAM: Random Access Memory）などを有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。再構築装置２は、例えば、中央演算処理装置の制御のもとで各処理を実行する。再構築装置２に入力されたデータや各処理で得られたデータは、例えば、主記憶装置に格納され、主記憶装置に格納されたデータは必要に応じて読み出されて他の処理に利用される。また、再構築装置２の各処理部の少なくとも一部が集積回路等のハードウェアによって構成されていてもよい。
【０１６０】
図４及び図５を参照して、第一実施形態の撹乱再構築方法を説明する。
【０１６１】
ステップＳ１０において、入力部１０へ、属性間に相関があるレコード(a(1),…,a(n))∈M1×…×Mnと属性毎の維持確率ρ1,…,ρnとが入力される。レコード(a(1),…,a(n))と維持確率ρ1,…,ρnとは撹乱部１２へ送られる。ここで、M1,…,Mnは各属性値a(1),…,a(n)に対応する属性の値域である。また、i番目の属性値a(i)（2≦i≦n）は、次式を満たす。
【０１６２】
【数４９】
2015230358.tif 000054
【０１６３】
維持確率ρ1,…,ρnは必ずしも外部から入力される必要はなく、図示していない記憶部等に予め記憶しておき、必要に応じて記憶部等から読み出すように構成しても構わない。
【０１６４】
ステップＳ１２１において、撹乱部１２は、１番目の属性値a(1)に対して維持確率ρ1で維持置換撹乱を行い、撹乱済属性値a'(1)∈M1を求める。
【０１６５】
ステップＳ１２２において、撹乱部１２は、j=1,…,i-1について、属性値a(j)と撹乱済属性値a’(j)を比較する。ここで、iは当該ステップで撹乱対象とする属性のインデックスである。例えば、２番目の属性値a(2)を撹乱しようとしているときは、属性値a(1)と撹乱済属性値a’(1)を比較する。３番目の属性値a(3)を撹乱しようとしているときは、j=1,2について、属性値a(j)と撹乱済属性値a’(j)を比較する。すべてのjについて属性値a(j)と撹乱済属性値a’(j)が等しい場合にはステップＳ１２３へ処理を進める。いずれかのjについて属性値a(j)と撹乱済属性値a’(j)が等しくない場合にはステップＳ１２４へ処理を進める。
【０１６６】
ステップＳ１２３において、撹乱部１２は、πi(a’(1),…,a’(i-1))の中で維持確率ρiで維持置換撹乱を行い、属性値a(i)に対して撹乱済属性値a’(i)を定める。
【０１６７】
ステップＳ１２４において、撹乱部１２は、πi(a’(1),…,a’(i-1))の元の中で一様ランダムに選択し、属性値a(i)に対して撹乱済属性値a’(i)を定める。
【０１６８】
ステップＳ１２５において、属性値a(1),…,a(n)のすべてが撹乱済みであるか否かを確認する。未撹乱の属性がある場合にはiに1を加算した上でステップＳ１２２へ処理を戻す。すべての属性が撹乱済みであればステップＳ１４へ処理を進める。
【０１６９】
ステップＳ１４において、出力部１４から撹乱済属性値a’(1),…,a’(n)が出力される。
【０１７０】
ステップＳ２０において、入力部２０へ、撹乱済レコード{(a’(1),…,a’(n))}を用いたクロス集計と維持確率ρ1,…,ρnと相関π2,…,πnとが入力される。入力された維持確率ρ1,…,ρn及び相関π2,…,πnは行列生成部２２へ送られる。入力されたクロス集計はベイズ推定部２４へ送られる。
【０１７１】
ステップＳ２２において、行列生成部２２は、維持確率ρ1,…,ρnと相関π2,…,πnを用いて、次式で定義される遷移確率行列Aを生成する。生成された遷移確率行列Aはベイズ推定部２４へ送られる。遷移確率行列の生成方法は上述した通りである。
【０１７２】
【数５０】
2015230358.tif 000055
【０１７３】
ステップＳ２４において、ベイズ推定部２４は、クロス集計と遷移確率行列Aを用いてベイズ推定法を行い、元のレコード{(a(1),…,a(n))}に対するクロス集計の推定値を求める。クロス集計の推定値は出力部２６へ送られる。
【０１７４】
ステップＳ２６において、出力部２６からクロス集計の推定値が出力される。
【０１７５】
［第二実施形態］
この発明の第二実施形態は、安全性指標を入力として、属性間に相関のあるレコードを撹乱する撹乱装置と、撹乱されたレコードを用いたクロス集計から元のレコードに対するクロス集計の推定値を求める再構築装置とから構成される撹乱再構築システム及び方法である。
【０１７６】
第二実施形態の撹乱再構築システムは、図１に示すように、撹乱装置３と再構築装置２を含む。撹乱装置３と再構築装置２は共に通信網９に接続される。通信網９は、接続される各装置が相互に通信可能なように構成されていればよく、例えばインターネット、WAN（Wide Area Network）、LAN（Local Area Network）、公衆交換電話網、専用データ回線などで構成することができる。撹乱装置３と再構築装置２との通信は暗号化等により安全性が確保された通信路であることが望ましい。また、撹乱装置３と再構築装置２とは必ずしも通信網９を介してオンラインで通信可能である必要はない。例えば、撹乱装置３が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から再構築装置２へオフラインで入力するように構成してもよい。その場合、通信網９はなくても問題ない。
【０１７７】
撹乱装置３は、図６に示すように、第一実施形態の撹乱装置１と同様に、入力部１０、撹乱部１２及び出力部１４を例えば含み、さらに維持確率計算部１１を例えば含む。撹乱装置３は、属性間に相関がある複数の属性と安全性指標とを入力として、その属性を撹乱した撹乱済属性を出力する。
【０１７８】
図７を参照して、第二実施形態の撹乱再構築方法を説明する。以下では、上述の第一実施形態との相違点を中心に説明する。
【０１７９】
ステップＳ１０において、入力部１０へ、属性間に相関があるテーブル{(a(1),…,a(n))∈M1×…×Mn}と安全性指標kと維持確率ρ1,…,ρnの関係式とが入力される。属性値a(1),…,a(n)は第一実施形態と同様に撹乱部１２へ送られる。安全性指標kは維持確率計算部１１へ送られる。
【０１８０】
安全性指標kと維持確率ρ1,…,ρnの関係式は必ずしも外部から入力される必要はなく、図示していない記憶部等に予め記憶しておき、必要に応じて記憶部等から読み出すように構成しても構わない。
【０１８１】
ステップＳ１１において、維持確率計算部１１は、s=2,…,n-1について、下記の関係式と入力された維持確率ρ1,…,ρnの関係式とを用いて、安全性指標kから維持確率ρ1,…,ρnを計算する。維持確率ρ1,…,ρnの求め方は、線形補間法等を利用すればよい。
【０１８２】
【数５１】
2015230358.tif 000056
【０１８３】
ここで、#Tはテーブルのレコード数であり、δ0=1-ρ1,δ1=1+(#M1-1)ρ1である。また、1≦g≦n-1に対して、(a(1),…,a(g))は、
【０１８４】
【数５２】
2015230358.tif 000057
【０１８５】
を与えるベクトルであり、(b(1),…,b(g))は、
【０１８６】
【数５３】
2015230358.tif 000058
【０１８７】
を与えるベクトルである。
【０１８８】
［発明の効果］
この発明の撹乱再構築技術は、上記のように構成することにより、安全性の指標であるkの値と撹乱の指標であるρの値を、一方を一定にしたまま他方を向上することができる。つまり、以下のような効果が得られる。
１．一定の安全性指標kの値に対して、従来よりも高い維持確率ρ1,…,ρnが使用できる。
２．一定の維持確率ρ1,…,ρnの値に対して、従来よりも高い安全性指標kの値になり、安全性が向上する。
３．従来の場合、あり得ない値（例えば{10代前半,車の運転をする}といった内容のレコード）であってもクロス集計の中でカウントしていたが、この発明では相関を定めることによって予め先のようなレコードは外しているので、あり得ない値のクロス集計の値を取らなくて済む。よって、クロス集計を用いる際の省メモリ化につながる。
【０１８９】
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施形態において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１９０】
［プログラム、記録媒体］
上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１９１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１９２】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１９３】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１９４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１９５】
１、３  撹乱装置
２  再構築装置
９  通信網
１０  入力部
１１  維持確率計算部
１２  撹乱部
１４  出力部
２０  入力部
２２  行列生成部
２４  ベイズ推定部
２６  出力部
【図１】
2015230358.tif 000066
【図２】
2015230358.tif 000067
【図３】
2015230358.tif 000068
【図４】
2015230358.tif 000069
【図５】
2015230358.tif 000070
【図６】
2015230358.tif 000071
【図７】
2015230358.tif 000072