集計システム、集計処理装置、情報提供者端末、集計方法およびプログラム
【課題】データを秘匿しつつクロス集計を算出する際の、メモリ使用量を小さくする。
【解決手段】集計装置1は、各属性に対してあらかじめ定められた維持確率を端末2−0〜2−(N−1)それぞれへ送信する。その後、集計装置1は、端末それぞれから送信されてきた、該端末が維持確率と属性に対して生成した乱数とに基づいて決定した該属性のデータそれぞれを用いて、該変化後のクロス集計を算出する。さらに、集計装置1は、遷移確率行列を生成する。そして、集計装置1は、算出した変化後のクロス集計と生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する。
【解決手段】集計装置1は、各属性に対してあらかじめ定められた維持確率を端末2−0〜2−(N−1)それぞれへ送信する。その後、集計装置1は、端末それぞれから送信されてきた、該端末が維持確率と属性に対して生成した乱数とに基づいて決定した該属性のデータそれぞれを用いて、該変化後のクロス集計を算出する。さらに、集計装置1は、遷移確率行列を生成する。そして、集計装置1は、算出した変化後のクロス集計と生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、集計システム、集計処理装置、情報提供者端末、集計方法およびプログラムに関する。
【背景技術】
【0002】
近年、データベースにおける個々のデータ(例えば、情報提供者端末から取得したアンケート結果など)を統計的手法により秘匿しつつ(つまり、情報提供者端末の有効なデータを経由して抽出できないことを担保しつつ)、クロス集計結果のみを得る技術が考えられている(例えば、非特許文献1および2参照。)。
【0003】
なお、以下に、「クロス集計」と、「単純集計」とについて説明しておく。
【0004】
「単純集計」とは、テーブルに含まれている1つの属性に着目し、該着目した1つの属性のみに関してレコードを集計する集計法である。
【0005】
より具体的には、図10に示す集計結果が、単純集計を行ったときに得られた集計結果の一例である。図10に示した例では、「人数」の列の値が集計値である。
【0006】
一方、「クロス集計」とは、テーブルに含まれている複数の属性に着目し、該着目した属性すべてに関して値が等しいようなレコードを集計する集計法である。
【0007】
より具体的には、図11に示す集計結果が、「クロス集計」を行ったときに得られた集計結果の一例である。図11に示した例では、「年代」と「性別」との2つの属性に着目して、「人数」の集計値を算出している。例えば、「10代」で「男性」であるレコードの数は「4」である。
【0008】
なお、以下では、複数の属性(例えば、「10代」と「男性」)に対する値を1つの値とみなしたものを「クロス値」という。
【先行技術文献】
【非特許文献】
【0009】
【非特許文献1】R.Agrawal,R.Srikant and D.Thomas, “Privacy Preserving OLAP”,SIGMOD Conference ACM, 第251頁〜第262頁,2005
【非特許文献2】高見澤 秀久,有次 正義,「プライバシーを保護するカウント演算の多値属性分類への適用」, DEWS2007, 2007
【非特許文献3】五十嵐 大,千田 浩司,高橋 克巳,「多値属性に適用可能な効率的プライバシー保護クロス集計」,コンピュータセキュリティシンポジウム2008(2008年10月8日〜10日)
【発明の概要】
【発明が解決しようとする課題】
【0010】
しかしながら、非特許文献1および2に開示された一般的な技術においては、個々のデータを秘匿しつつ真のクロス集計の推定値を算出する際、クロス値として指定する各属性が取り得る値が多い場合、これらの技術を適用して構成した集計処理装置がクロス集計結果を算出するために要する時間が非常に長くなってしまうという問題点がある。
【0011】
また、非特許文献1および2に開示された一般的な技術においては、クロス値として指定する各属性が取り得る値が多い場合、これらの技術を適用して構成した集計処理装置がクロス集計結果を算出する際、当該算出のために集計処理装置が使用するメモリ使用量が数GB以上となってしまう場合もある。そのため、当該メモリ使用量が、該算出を行う集計処理装置が搭載しているメモリ量のうちでクロス集計結果の算出用に割当可能なメモリ量よりも多くなってしまった場合には、集計処理装置がクロス集計結果の算出を行うことをできなくなってしまうという問題点がある。
【0012】
本発明は、上述した課題を解決する集計システム、集計処理装置、情報提供者端末、集計方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【0013】
上記課題を解決するために、本発明の集計システムは、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、前記集計処理装置は、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【0014】
【数1】
【0015】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計部と、前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有し、前記情報提供者端末は、前記データを記憶する記憶部と、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更部と、前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有することを特徴とする。
【0016】
また、本発明の集計処理システムにおいては、前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0017】
また、本発明の集計システムにおいては、前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0018】
また、本発明の集計システムにおいては、前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出してもよい。
【0019】
また、本発明の集計システムにおいては、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出してもよい。
【0020】
上記課題を解決するために、本発明の集計処理装置は、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されており、該情報提供者端末から送信されてきた送信データを集計する集計処理装置であって、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【0021】
【数2】
【0022】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計部と、前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有する。
【0023】
また、本発明の集計処理装置においては、前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0024】
また、本発明の集計処理装置においては、前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0025】
また、本発明の集計処理装置においては、前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出してもよい。
【0026】
また、本発明の集計処理装置においては、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出してもよい。
【0027】
上記課題を解決するために、本発明の情報提供者端末は、集計処理装置と接続された情報提供者端末であって、当該情報提供者端末にて入力を受付けたデータを記憶する記憶部と、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とが前記集計処理装置から送信されてきた際、乱数を生成する確率変更部と、前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有する。
【0028】
上記課題を解決するために、本発明の集計方法は、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、該送信データを集計する集計方法であって、前記情報提供者端末が、前記データを記憶する記憶処理と、前記集計処理装置が、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信処理と、前記情報提供者端末が、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更処理と、前記情報提供者端末が、前記集計処理装置から送信されてきた維持確率および属性と、前記生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定処理と、前記情報提供者端末が、前記決定した送信データを前記集計処理装置へ送信するデータ送信処理と、前記集計処理装置が、
【0029】
【数3】
【0030】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出処理と、前記集計処理装置が、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計処理と、前記集計処理装置が、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定処理とを有する。
【0031】
また、本発明の集計方法においては、前記要素算出処理は、前記集計処理装置が、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する処理とし、前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する処理としてもよい。
【0032】
また、本発明の集計方法においては、前記要素算出処理は、前記集計処理装置が、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する処理とし、前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する処理としてもよい。
【0033】
また、コンピュータに実行させるプログラムであって、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されている集計処理装置に、前記情報提供者端末にて入力を受付けたデータが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信手順と、
【0034】
【数4】
【0035】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出手順と、前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計手順と、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定手順とを実行させる。
【0036】
また、本発明のプログラムにおいては、前記要素算出手順は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する手順とし、前記推定手順は、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する手順としてもよい。
【0037】
また、本発明のプログラムにおいては、前記要素算出手順は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する手順とし、前記推定手順は、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する手順としてもよい。
【発明の効果】
【0038】
本発明によれば、個々のデータを秘匿しつつ真のクロス集計の推定値を算出する際、レコード全体に対する遷移確率行列の次数として、各属性が取り得る値の2進表現を用いた場合よりも値が小さな当該各属性の取り得る値の個数を用いて真のクロス集計の推定値を算出する。
【0039】
このような構成としたため、クロス集計結果を算出するときに集計処理装置が使用するメモリ使用量を一般的な技術よりも小さくすることができる。
【0040】
さらに、メモリ使用量を抑えることにより、クロス値として指定する各属性が取り得る値が多い場合でも、集計処理のうちで最も計算量が多いレコード全体に対する遷移確率行列に対する演算を一般的な技術よりも短い時間で行うことが可能となる。
【図面の簡単な説明】
【0041】
【図1】本発明の実施形態に従った集計システムの構成を示す図である。
【図2】図1に示した集計処理装置の構成を示す図である。
【図3】図2に示した対応情報のデータ構造の一例を示す図である。
【図4】図1に示した情報提供者端末の構成を示す図である。
【図5】クロス集計による集計結果のうちの属性に対して、順番を付与したときの模式図である。
【図6】図4に示したデータ決定情報のデータ構造の一例を示す図である。
【図7】実施形態1の集計システムにおいて、真のクロス集計の推定値を算出するときの動作シーケンスを示す図である。
【図8】実施形態2の集計システムにおいて、真のクロス集計の推定値を算出するときの動作シーケンスを示す図である。
【図9】実施形態3の集計システムにおいて、分割遷移確率行列を生成するときの動作シーケンスを示す図である。
【図10】単純集計により求めた集計結果の一例を示す図である。
【図11】クロス集計により求めた集計結果の一例を示す図である。
【発明を実施するための形態】
【0042】
(実施形態1)
以下、本発明の実施形態1に従った集計システム(集計処理装置、情報提供者端末、集計方法およびプログラムを含む)を説明する。
【0043】
実施形態1の集計システムは、ある結果(データ)が得られた際に、当該結果を反映した下での事後確率を求めるための「所定の事後確率算出条件」を用いて、真のクロス集計xの推定値である「推定クロス集計」を算出する。
【0044】
なお、実施形態1は、「所定の事後確率算出条件」として、「ベイズの定理」を適用した例である。
【0045】
まず、実施形態1の集計システムの構成について説明する。
【0046】
図1に示すように、本集計システムは、集計処理装置1(以下、「集計装置1」という)と、情報提供者端末2−0〜2−(N−1)(以下、「端末2−0〜2−(N−1)」という)とを具備する。
【0047】
なお、以下では、端末2−0〜2−(N−1)の台数が「N」である場合を例に挙げて説明するが、端末2−0〜2−(N−1)の台数は1以上の自然数であればよい。
【0048】
集計装置1は、n個の属性αaそれぞれ(例えば、「年代」、「性別」など)に対する以下の式1に示す要素Apqをp行q列の要素として有する遷移確率行列Aを構成するために、集計対象となるデータが属する属性αaそれぞれに対してあらかじめ定められた維持確率ρaと、当該属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する。
【0049】
なお、「維持確率ρa」とは、端末2−0〜2−(N−1)それぞれが属性αaを撹乱(つまり、確率的な変化)した後においても、属性αaが元の値を維持する確率のことを指す。
【0050】
【数5】
【0051】
ここで、遷移確率行列Aの行の数pおよび列の数qは、以下の式2に示す値である。
【0052】
【数6】
【0053】
また、式1に示したdpaおよびdqaそれぞれは、以下の式3および式4でそれぞれ定義される。
【0054】
【数7】
【0055】
【数8】
【0056】
ここで、式3および式4にて示した「÷」は、整数の除算を示す演算記号である。また、式3および式4にて示した「%」は、剰余算を示す演算記号である。
【0057】
また、集計装置1は、レコード全体に対する遷移確率行列Aに含まれる式1に示したp行q列の要素Apqを算出する。
【0058】
ここで、各属性αaに対する「遷移確率行列Aa」とは、属性αa同士の間での変化の確率を行列形式で表現したものである。
【0059】
また、集計装置1は、端末2−0〜2−(N−1)それぞれから送信されてきた送信データT´(0)a〜T´(N−1)aを集計したクロス集計である「撹乱後のクロス集計y」を算出する。
【0060】
ここで、送信データT´(0)a〜T´(N−1)aとは、端末2−0〜2−(N−1)が、維持確率ρaと属性αaと乱数とに基づいて決定した送信データT´(0)a〜T´(N−1)aのことを指す。
【0061】
そして、集計装置1は、算出した撹乱後のクロス集計yに基づいて、「真のクロス集計x」の推定値である推定クロス集計を算出する。
【0062】
端末2−0〜2−(N−1)それぞれは、端末2−0〜2−(N−1)それぞれに対応するレコードT(0)〜T(N−1)を記憶している。例えば、端末2−0は、レコードT(0)を記憶している。
【0063】
ここで、レコードT(0)〜T(N−1)それぞれは、各属性αaのデータT(0)a〜T(N−1)aを含んでいる。例えば、レコードT(0)であれば、属性αaのデータT(0)aを含んでいる。
【0064】
なお、ここでいう「データT(0)a〜T(N−1)a」とは、例えば、属性αaが「性別」である場合、該属性αaが取り得る値Vα0 〜 VαMa-1(「男性」および「女性」)のうちのいずれか1つの値(例えば、女性)である。
【0065】
つまり、端末2−0〜2−(N−1)それぞれは、レコードT(0)〜T(N−1)それぞれを記憶することにより、データT(0)a〜T(N−1)aそれぞれを記憶している。
【0066】
なお、属性αaの数は「n」個であり、集計装置1および端末2−0〜2−(N−1)それぞれは、当該属性αaの数nを記憶している。
【0067】
なお、各属性αaは、aの値が属性αaの数n未満である場合(a<n)、「Ma」個の値(Vα0 〜 VαMa-1)を取り得る。そして、集計装置1および端末2−0〜2−(N−1)それぞれは、各属性αaが取り得る値の数Maと、各属性αaが取り得る値Vα0 〜 VαMa-1を記憶している。
【0068】
端末2−0〜2−(N−1)は、集計装置1から送信されてきた維持確率ρaおよび属性αaを用いて、当該端末2−0〜2−(N−1)がそれぞれ記憶している該端末2−0〜2−(N−1)にて入力を受付けたデータT(0)a〜T(N−1)aを確率的に変化(「撹乱」)させる。
【0069】
ここで、データT(0)a〜T(N−1)aを確率的に変化させること(撹乱)とは、集計装置1から送信されてきた維持確率ρaと属性αaと、該送信の際に生成した乱数とに基づいて、記憶しているデータのうちから集計装置1へ送信する送信データT´(0)aを決定することを指す。
【0070】
そして、端末2−0〜2−(N−1)それぞれは、確率的に変化させたデータ(つまり、維持確率ρaと属性αaと乱数とに基づいて集計装置1への送信を決定した送信データ)を、集計装置1へ送信する。
【0071】
つぎに、集計装置1が有する構成について詳細に説明する。
【0072】
図2に示すように、集計装置1は、通信部11と、要素算出部12と、集計部13と、推定部14と、記憶部15とを有する。
【0073】
通信部11は、例えば、通信モジュールで構成され、端末2−0〜2−(N−1)それぞれと任意のデータを送受信する。
【0074】
また、通信部11は、n個の各属性αaに対する遷移確率行列Aを構成するために、属性αaそれぞれに対してあらかじめ定められた維持確率ρaと当該属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する「情報送信部」である。
【0075】
また、通信部11は、端末2−0〜2−(N−1)それぞれから送信されてきた、該端末2−0〜2−(N−1)それぞれが確率的に変化させた送信データT´(0)a〜T´(N−1)aそれぞれを受信する。
【0076】
要素算出部12は、n個の各属性αaのデータを有するレコード全体に対する遷移確率行列Aに含まれる式1に示したp行q列の要素Apqそれぞれを算出する。各要素Apqの算出により、要素算出部12は、遷移確率行列Aを生成する。
【0077】
この説明例では、要素算出部12は、p行q列の要素Apqが後述する式5で表されるような正方行列の遷移確率行列Aを生成する。
【0078】
集計部13は、情報提供者端末2−0〜2−(N−1)それぞれから送信されてきた、維持確率ρaと属性αaと乱数とに基づいて決定された送信データT´(0)a〜T´(N−1)aそれぞれを集計することにより、撹乱後のクロス集計yを算出する。
【0079】
推定部14は、集計部13が算出した撹乱後のクロス集計yに基づいて、真のクロス集計xの推定値である「推定クロス集計xi+1」を算出する。なお、推定部14は、算出した推定クロス集計xi+1を、例えば、集計装置1と接続されている外部の表示装置(図示せず)などへ出力する。
【0080】
なお、実施形態1においては、推定部14は、要素算出部12が算出した遷移確率行列Aと、集計部13が算出した撹乱後のクロス集計y(変化後のクロス集計)に基づいて、「推定クロス集計xi+1」を算出する。
【0081】
また、当該推定クロス集計xi+1を算出する際、推定部14は、集計部13が算出した撹乱後のクロス集計y(変化後のクロス集計)が得られた場合の事後確率を求めるための所定の事後確率算出条件として、「ベイズの定理」を適用する。
【0082】
記憶部15は、任意のデータを記憶する。
【0083】
例えば、記憶部15は、対応情報ASを記憶している。
【0084】
図3に示すように、対応情報ASは、データが属する属性αaと、当該属性αaに対してあらかじめ定められた維持確率ρaとを対応付ける情報である。
【0085】
また、記憶部15は、データが属する属性αaの数「n」を記憶している。
【0086】
また、記憶部15は、属性αaそれぞれが取り得る値の数Maと、各属性αaが取り得る値Vα0 〜 VαMa-1を記憶している。図11に示した例においては、属性αaが「性別」である場合、その取り得る値は「男性」と「女性」とのいずれかである。
【0087】
つぎに、端末2−0〜2−(N−1)が有する構成について説明する。なお、端末2−0〜2−(N−1)とは互いに同じ構成を有するため、以下では、端末2−0の構成を例に挙げて説明する。
【0088】
図4に示すように、端末2−0は、通信部21−0と、確率変更部22−0と、送信データ決定部23−0と、記憶部24−0とを有する。
【0089】
通信部21−0は、例えば、通信モジュールで構成され、集計装置1と任意のデータを送受信する。
【0090】
通信部21−0は、集計装置1から送信されてきた、n個の属性αaそれぞれに対してあらかじめ定められた維持確率ρaと属性αaとを受信する。
【0091】
また、通信部21−0は、送信データ決定部23−0が決定した送信データT´(0)aを集計装置1へ送信する「データ送信部」である。
【0092】
なお、端末2−1〜2−(N−1)それぞれは、送信データT´(1)a〜T´(N−1)aそれぞれを集計装置1へ送信する。
【0093】
確率変更部22−0は、集計装置1から送信されてきた維持確率ρaと属性αaとを用いて、記憶部24−0が記憶しているデータT(0)aを確率的に変化させる。
【0094】
より具体的には、確率変更部22−0は、集計装置1から維持確率ρaと属性αaとが送信されてきた際、n個の属性αaそれぞれに対して、実数の値を有する「一様乱数ra(0≦ra≦1)」と、整数の値を有する「一様乱数za(0≦za≦Ma−1)」とを生成する。
【0095】
続いて、確率変更部22−0は、属性αaごとにあらかじめ定められた維持確率ρaと、該属性αaに対して生成した一様乱数raとを比較する。
【0096】
送信データ決定部23−0は、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρa以下である場合(ra≦ ρa)、該端末2−0の属性αaの正しいデータそのものであるデータT(0)aを、送信データT´(0)aとして決定する。
【0097】
また、送信データ決定部23−0は、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρaよりも大きい場合(ra> ρa)、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちから確率変更部22−0が生成した整数値を有する一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0098】
例えば、図11に示した集計結果において、図5に示すように属性αaを「性別」として、該属性αaに属する要素のうちの「男性」に「0」番の順番NBを付与しておき、該属性αaに属する要素のうちの「女性」に「1」番の順番NBを付与しておく。この場合、確率変更部22−0が生成した一様乱数zaが「1」である際、送信データ決定部23−0は、該一様乱数zaと同じ値(1)の順番NBが付与された「女性」を送信データT´(0)aとして決定する。
【0099】
さらに、送信データ決定部23−0は、集計装置1から送信されてきた維持確率ρaの値が「0」である場合、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちから確率変更部22−0が生成した整数値を有する一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0100】
記憶部24−0は、任意のデータを記憶する。
【0101】
例えば、記憶部24−0は、レコードT(0)と、属性データT(0)aとを記憶している。なお、当該レコードT(0)は、属性データT(0)aを含んでいる。
【0102】
また、記憶部24−0は、属性αaの数nを記憶している。
【0103】
さらに、記憶部24−0は、データ決定情報DTを記憶している。
【0104】
図6に示すように、データ決定情報DTは、n個の属性αaと、当該属性αaが取り得るMa個の値Vα0 〜 VαMa-1と、当該値Vα0 〜 VαMa-1それぞれに対して付与された順番NBとを対応付けて記憶している。なお、属性αaが取り得る値Vα0 〜 VαMa-1それぞれに順番NBを付与する順序は任意でよい。
【0105】
つぎに、上述した構成を有する集計システムにおいて、集計装置1が端末2−0〜2−(N−1)から送信されてきた送信データT´(0)a〜T´(N−1)aそれぞれの撹乱後のクロス集計yを算出した場合、上述した一般的な技術よりも高速かつメモリ効率が高いことを、図7に示すフローチャートを参照して説明する。
【0106】
なお、端末2−0〜2−(N−1)とは互いに同じ動作を行うため、以下では、端末2−0の動作を例に挙げて説明する。
【0107】
図7に示すように、集計装置1は、それぞれの属性αaごとにあらかじめ定められた維持確率ρa(0≦ρa≦1)と属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する(ステップS11)。
【0108】
集計装置1から送信されてきた維持確率ρaと属性αaとを受信した際、端末2−0の確率変更部22−0は、各属性αaに対して、実数の値を有する一様乱数ra(0≦ra≦1)と、整数の値を有する一様乱数za(0≦za≦Ma−1)とを生成する(ステップS12)。
【0109】
続いて、確率変更部22−0は、集計装置1から送信されてきた属性αaごとにあらかじめ定められた維持確率ρaと、該属性αaそれぞれに対して生成した実数値を有する一様乱数raとを比較する(ステップS13)。
【0110】
そして、端末2−0の送信データ決定部23−0は、当該比較の結果に応じて、集計装置1へ送信する送信データT´(0)aを決定する(ステップS14)。すると、通信部21−0は、送信データ決定部23−0が決定した送信データT´(0)aを集計装置1へ送信する。
【0111】
なお、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρa以下である場合(ra≦ ρa)、送信データ決定部23−0は、ステップS14において、該端末2−0の属性αaの正しいデータそのものであるデータT(0)aを、送信データT´(0)aとして決定する。
【0112】
また、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρaよりも大きい場合(ra> ρa)、送信データ決定部23−0は、ステップS14において、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちからステップS12にて生成した一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0113】
また、ステップS14において、送信データ決定部23−0は、集計装置1から送信されてきた維持確率ρaが「0」である場合にも、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが有する値Vα0 〜 VαMa-1のうちでza番の順番が付与された値を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0114】
図6に示した例では、属性αaが性別である場合、該属性αaのうちの「男性」に0番の順番NBが付与されていて、該属性αaのうちの要素「女性」に1番の順番NBが付与されている。この場合、一様乱数zaの値が1であれば、送信データ決定部23−0は、当該一様乱数zaと同じ値の順番NB(1番)が付与された値(女性)を送信データT´(0)aとして決定する。
【0115】
なお、維持確率ρaが小さくなるに伴って、送信データT´(0)aは一様にランダムな値に近づいていく。この場合、集計装置1が、端末2−0から送信されてきた送信データT´(0)aを用いて、該端末2−0が記憶している真のデータT(0)aを推定することは困難となる。
【0116】
なお、属性αaのk番目の値Vkaから当該属性αaのl番目の値Vlaへと変化する確率は、遷移確率行列Aklaとして表すことが可能である。この場合、各属性αaに対する遷移確率行列Aaは、各要素Aaklが以下の式5で表されるような行列であり、各属性に対する維持確率ρaと、各属性αaが取り得る値の数「Ma」とから算出できる。なお、式5におけるδklは、「クロネッカーのデルタ」である。
【0117】
【数9】
【0118】
そのため、維持確率ρaが小さくなるに伴って、式1に示した遷移確率行列Aaの要素Apq(値が変化する確率)は、一様乱数における遷移確率の値「1/Ma」に単調に近づいていく。
【0119】
さらに、維持確率ρa=0である場合、遷移確率行列Aaが有する要素Apqは、一様乱数における遷移確率の値そのものである。
【0120】
例えば、属性αaが性別である場合、当該属性αaが取り得る値の数Maは「2」(男性と女性との2つ)であるから、当該属性αaの遷移確率は「1/2」である。
【0121】
また、維持確率ρa=1である場合、遷移確率行列Aaが有する要素Apqは、真のデータT(0)a〜T(N−1)aそのものとなる。
【0122】
端末2−0〜2−(N−1)それぞれから送信データT´(0)a〜送信データT´(N−1)aが送信されてきた場合、集計装置1の集計部13は、「撹乱後のクロス集計y」を算出するために、まず、以下の式6で表される次数の横ベクトルである「撹乱後のクロス集計y」を、遷移確率行列Aaが有する全要素Apqに対して「0」を設定することにより、全要素Apqを初期化する(ステップS15)。
【0123】
【数10】
【0124】
続いて、集計部13は、端末2−0〜2−(N−1)それぞれから送信されてきた送信データT´(0)a〜T´(N−1)aについて、撹乱後のクロス集計yにおける以下の式7に示す順番が付与された要素に、1を加算していく(ステップS16)。なお、式7におけるIaは、送信データT´(0)a〜T´(N−1)aに付与されている順番NBを返すための関数である。
【0125】
【数11】
【0126】
該加算により、集計部13は、撹乱後のクロス集計yを算出する。
【0127】
すると、要素算出部12は、レコード全体に対する遷移確率行列Aの生成手法に従って、以下の式8で表されるようなp行q列の要素Apqそれぞれを有する、式6に示した次数の正方行列である、レコード全体に対する遷移確率行列Aを生成する(ステップS17)。なお、集計装置1が生成した遷移確率行列Aの行の数pおよび列の数qは、式2に示した値である。
【0128】
【数12】
【0129】
非特許文献2に開示された一般的な技術においては、遷移確率行列の次数は、以下の式9で表される。
【0130】
【数13】
【0131】
なお、式9に示した[log2Ma]は、log 2 Ma 以上の最小の整数を表す。
【0132】
一方、本発明の集計装置1においては、遷移確率行列Aの次数は式6に示した次数である。
【0133】
このように、本発明の集計装置1が撹乱後のクロス集計yの算出に用いる式6に示した次数と、一般的な技術にてクロス集計結果の算出に用いる式9に示した次数との間の差異により、集計装置1では、レコード全体に対する遷移確率行列Aに費やすメモリ使用量を、例えば、非特許文献2に開示されたような一般的な技術に比べて小さく抑えることができる。
【0134】
その後、推定部14は、要素算出部12が算出した「遷移確率行列A」と集計部13が算出した「撹乱後のクロス集計y」とを用いて推定クロス集計xi+1を算出し、該推定クロス集計xi+1を出力する(ステップS18)。なお、推定クロス集計xi+1とは、真のクロス集計xの推定値のことを指す。
【0135】
ステップS18において、推定部14は、はじめ、i=0、x0=yを初期値として、式6に示した次数を有する横ベクトルとして表される(i+1)番目の「推定クロス集計xi+1」を、xi+1=xi・((y/(xiA))At)として算出していく。
【0136】
ここで、「・」は、ベクトルの内積を示す演算記号である。また、「/」は、ベクトルの成分ごとの除算を示す演算記号である。また、Atは、行列Aの転置行列を表す。
【0137】
そして、推定部14は、ステップS18における推定クロス集計xi+1の算出を実行していて|xi+1−xi|L1 ≦εN となった場合、iに対する推定クロス集計xi+1を、真のクロス集計xの推定値として出力する。
【0138】
ここで、|xi+1−xi|L1は、(xi+1−xi)のL1ノルムであり、行列の成分ごとの差の絶対値の総和を示す演算記号である。また、εはあらかじめ設定された実数である。
【0139】
なお、ステップS18に示した処理は、ある結果(例えば、撹乱後のクロス集計y)が得られた際に、当該結果を反映した下での事後確率を求めるための「ベイズの定理」に基づいている。
【0140】
ベイズの定理を用いた場合、あるレコードの撹乱後のクロス値Qがqであること(この例では、撹乱後のクロス集計y)が既知である場合に、該レコードの真のクロス値Pがpである事後確率Pr(P=p|Q=q)は、式6に示した値をMとして、真のクロス集計をxとした場合、以下の式10で表される。
【0141】
【数14】
【0142】
さらに、クロス値Qがqである事後確率Pr(Q=q)については、以下の式11が成立する。
【0143】
【数15】
【0144】
そのため、式11に示した関係を用いると、真のクロス値Pがpである事後確率Pr(P=p)は、以下の式12で表すことができる。
【0145】
【数16】
【0146】
ここで、式10に示した関係式と、式12に示した関係式とを用いると、真のクロス集計xpは、以下の式13で表すことができる。
【0147】
【数17】
【0148】
以上より、x=x・((y/(xA))At)という方程式を得ることができる。
【0149】
ステップS18において(i+1)番目の「推定クロス集計xi+1」を算出する際、集計装置1は、上述した方程式x=x・((y/(xA))At)を用いている。
【0150】
なお、推定部14は、ステップS18においてレコード全体に対する遷移確率行列Aについての乗算を実行する。しかしながら、当該乗算を行うときの計算量は、該遷移確率行列Aが有する次数の2乗に比例して増大し、本発明の集計装置1が実行する演算のなかで最も多くの計算量を伴う演算である。しかしながら、当該集計装置1の要素算出部12は、レコード全体に対する遷移確率行列Aを算出し、例えば、非特許文献2に開示されたような一般的な技術よりも、属性αaが取り得る値の数Maに対して遷移確率行列Aが有する次数が非常に小さなものとなる。
【0151】
そのため、集計装置1においては、真のクロス集計xの推定値である推定クロス集計xi+1の算出に要する時間が一般的な技術よりも非常に短くできるとともに、該推定クロス集計xi+1を算出するときに集計装置1が使用するメモリ使用量についても小さなものとできる。
(実施形態2)
つぎに、実施形態2の集計装置1について説明する。
【0152】
実施形態2の集計装置1の構成および端末2−0〜2−(N−1)の構成それぞれは、実施形態1における集計装置1の構成および端末2−0〜2−(N−1)の構成と同じである。
【0153】
ただし、実施形態2の集計装置1は、個別に指定したクロス値に対する推定クロス集計を算出する点で、実施形態1の集計装置1と異なっている。なお、以下では、複数の属性に対する値を1つの値とみなした値であるクロス値として、ベクトルvを指定する場合を例に挙げて説明する。
【0154】
以下に、上述した集計システムにおいて、実施形態2の集計装置1が推定クロス集計xi+1を算出する動作を、図8に示すフローチャートを参照して説明する。
【0155】
図8に示すように、まず、集計装置1は、複数の属性に対する値を1つの値とみなしたクロス値として、ベクトルvを指定する入力を、入力部(図示せず)により利用者から受付ける(ステップS21)。
【0156】
なお、当該ベクトルvに含まれている各成分vaは、推定クロス集計xi+1の算出を行う際の属性αaそれぞれに対する値(例えば、図4に示した「10代」と「男性」)の指定である。
【0157】
すると、集計装置1は、属性αaごと(例えば、「年代」や「性別」)にあらかじめ定められた維持確率ρa(0≦(a≦1)と属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する(ステップS22)。
【0158】
集計装置1から維持確率ρaと属性αaとが送信されてきた場合、端末2−0の確率変更部22−0は、属性αaそれぞれに対して、実数の値を有する一様乱数ra(0≦ra≦1)と、整数の値を有する一様乱数za(0≦za≦Ma−1)とを生成する(ステップS23)。
【0159】
続いて、確率変更部22−0は、属性αaごと(例えば、「年代」や「性別」)に、集計装置1から送信されてきた維持確率ρaと、該属性αaに対して生成した実数値を有する一様乱数raとを比較する(ステップS24)。
【0160】
そして、送信データ決定部23−0は、確率変更部22−0による比較の結果に応じて、集計装置1へ送信する送信データT´(0)aを決定する(ステップS25)。
【0161】
ステップS25において、送信データ決定部23−0は、比較の結果、一様乱数raの値が維持確率ρa以下である場合(ra≦ ρa)、当該端末2−0の属性αaの正しいデータそのものであるデータT(0)aを、送信データT´(0)aとして決定する。
【0162】
また、ステップS25において、送信データ決定部23−0は、比較の結果、一様乱数raの値が維持確率ρaよりも大きい場合(ra> ρa)、または、維持確率ρaが「0」である場合、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちからステップS23にて生成した一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして集計装置1へ送信する。
【0163】
このとき、維持確率ρaが小さくなるに伴って送信データT´(0)aは一様にランダムな値に近づく。そのため、集計装置1が、端末2−0から送信されてきた送信データT´(0)aを用いて、該端末2−0が記憶している真のデータT(0)aを推定することは困難となる。
【0164】
その後、通信部21−0は、ステップS25にて送信データ決定部23−0が決定した送信データT´(0)aを集計装置1へ送信する。
【0165】
なお、端末2−1〜2−(N−1)それぞれも、それぞれの比較の結果に応じた送信データT´(1)a〜T´(N−1)aそれぞれを集計装置1へ送信する。
【0166】
端末2−0〜2−(N−1)から送信データT´(0)a〜T´(N−1)aが送信されてきた場合、集計装置1の集計部13は、「撹乱後のクロス集計y」を算出するための処理を実行する。
【0167】
集計部13は、まず、式6に示した次数の横ベクトルである撹乱後のクロス集計yを、遷移確率行列Aaが有する全要素に対して0を設定することにより、全要素を初期化する(ステップS26)。
【0168】
続いて、集計部13は、端末2−0〜2−(N−1)それぞれに対して、撹乱後のクロス集計yにおける式3に示した順番の要素に、「1」を加算していく(ステップS27)。該加算により、集計部13は、撹乱後のクロス集計yを算出する。
【0169】
さらに、集計装置1の推定部14は、各属性αaに対する遷移確率行列Aaの逆行列(Aa)-1を算出する(ステップS28)。
【0170】
逆行列(Aa)-1を算出した場合、さらに、推定部14は、各属性αaに対する値としてベクトルvに含まれている成分vaを有するレコードの数、つまり、クロス値として指定されたベクトルvに対する以下の式14に示すクロス集計を算出して出力する(ステップS29)。
【0171】
【数18】
【0172】
真のクロス集計xが与えられた場合、撹乱後のクロス集計yの期待値のベクトルE(Y)は、E(Y)=xAで表すことができる。そのため、|A|≠0である場合、E(YA-1)=E(Y)A-1=xが成立する。すなわち、yA-1は真のクロス集計xの近似であることが期待できる。
【0173】
ここで、クロネッカー積を用いると、式1に示した各要素を有するようなレコード全体に対する遷移確率行列Aは、以下の式15で表すことが可能である。
【0174】
【数19】
【0175】
式15に示した関係を用いると、クロネッカー積の性質から、遷移確率行列Aの逆行列A-1は、以下の式16で表すことができる。
【0176】
【数20】
【0177】
このことから、遷移確率行列Aと同様に、逆行列A-1が有する各成分は、以下の式17で表すことができる。
【0178】
【数21】
【0179】
そのため、真のクロス集計xは、x=yA-1という関係に基づいて推定することが可能である。
【0180】
また、逆行列A-1のp列目の各成分によって構成される縦ベクトルを縦ベクトルAp-1とした場合、(Ap-1)q = Apq-1が成立する。
【0181】
そのため、真のクロス集計xpは、逆行列A-1のp列目以外の成分を用いることなく、当該逆行列A-1のp列目の各成分を用いて、以下の式18として直接算出することが可能である。
【0182】
【数22】
【0183】
ここで、pとして、クロス値であるベクトルvに対応する以下の式19に示す数を代入する。
【0184】
【数23】
【0185】
すると、Ia(va)=dpaの関係が導出できる。そのため、真のクロス集計xpは、式14に示した値により算出することができる。
【0186】
実施形態2において推定部14が真のクロス集計xの推定値を算出する場合、推定クロス集計の算出に要する所要時間、および、該クロス集計を算出する際に使用するメモリ使用量ともに、遷移確率行列Aの次数に対して線形となる。
【0187】
なお、最終的には、各属性αaに対する値vaをそれぞれ有するようなレコードの数は、(i+1)番目の推定クロス集計xi+1における式19に示した順番が付与された要素が表している。
【0188】
以上説明したように、実施形態1及び実施形態2においては、レコード全体に対する遷移確率行列Aの次数として、各属性αaが取り得る値の数Maの2進表現よりも値が小さな各属性αaが取り得る値の個数Maを用いて、推定クロス集計を算出する。これにより、個々のデータを秘匿しつつ推定クロス集計を算出する際に、集計装置1が使用するメモリ使用量を抑えることができる。
【0189】
さらに、メモリ使用量を抑えることにより、推定クロス集計の集計処理中に最も多くの計算量を伴うボトルネックとなる、レコード全体に対する遷移確率行列Aに対する演算もより短い時間で行うことが可能となる。
(実施形態3)
上述した実施形態1において、レコード全体に対する遷移確率行列Aが有する次数Mは、例えば非特許文献2に開示されたような一般的な技術と比べ、属性αaが取り得る値の個数Maに対して非常に小さなものとすることができる。
【0190】
そのため、推定クロス集計の算出に要する時間を、一般的な技術よりも非常に短くすることができる。また、それとともに、推定クロス集計を算出するときに集計装置1が使用するメモリ使用量も小さなものとすることができる。なお、以降、レコード全体に対する遷移確率行列Aを単に、遷移確率行列Aという。
【0191】
ここで、上述した式2に示したように、遷移確率行列Aの行の数p及び列の数qはM個となる。そのため、遷移確率行列Aは、M次の正方行列である。一般的に、M次の正方行列をメモリ上に展開するときのメモリ使用量は、「正方行列の要素のサイズ×M2」となる。また、遷移確率行列Aが有する次数Mは、上述した式6に示したように、属性αaの取り得る値の個数Maを用いて表される。
【0192】
従って、属性αaの取り得る値の個数Maが多くなると、遷移確率行列Aをメモリ上に展開したときのメモリ使用量は、飛躍的に増加してしまう。
【0193】
そこで、本実施形態では、遷移確率行列Aを生成することなく、推定クロス集計を算出する場合について説明する。
【0194】
なお、本実施形態における集計システムの構成は、上述した実施形態1における構成と同様なので、ここでは、構成の説明は省略する。
【0195】
以下に、本実施形態において推定クロス集計を算出する場合の動作を説明する。
【0196】
まず、遷移確率行列Aは、クロネッカー積を用いると、上述した式15で表すことが可能である。
【0197】
そして、クロネッカー積を用いて表された遷移確率行列Aを分割したBjを設定する。以下の式20にBjを示す。なお、式20においてJは分割数であり、m-1=0とする。
【0198】
【数24】
【0199】
そして、上記の式20に示すようなBjをメモリ上に展開したとき、各Bjのサイズの総和が、予め決められ、推定クロス集計の算出用に割り当て可能なメモリサイズに収まるようにする。各Bjをメモリ上に展開したときのサイズの総和を以下の式21に示す。
【0200】
【数25】
【0201】
ここで、具体的な分割の方法としては、aの値が属性αaの数n未満である場合に(a<n)、Ba=Aaとする方法がある。以降、この方法のことを分割方法1という。つまり、分割方法1では、属性αa毎に複数の遷移確率行列を生成することとなる。以降、属性αa毎の複数の遷移確率行列のそれぞれを属性別遷移確率行列という。
【0202】
分割方法1において要素算出部12は、要素Apqを属性毎に算出する。そして、要素算出部12は、属性毎に算出された要素Apqから、複数の属性別遷移確率行列を生成する。
【0203】
そして、推定部14は、要素算出部12が算出した複数の属性別遷移確率行列と、集計部13が算出した撹乱後のクロス集計yとに基づき、上述した実施形態1におけるステップS18と同様の処理を実行する。これにより、推定クロス集計が算出される。
【0204】
また、上述した分割方法1以外にも例えば、属性別遷移確率行列をメモリ上に展開したときのサイズに基づき、少なくとも1つの属性別遷移確率行列を含む遷移確率行列である分割遷移確率行列を複数生成する方法がある。以降、この方法のことを分割方法2という。
【0205】
以下に、本実施形態の分割方法2において分割遷移確率行列を生成する場合の動作について説明する。なお、以下の説明においては、予め決められ、推定クロス集計の算出用に割り当て可能なメモリサイズをLと表記し、行列Xをメモリ上に展開したときのサイズをsizeXと表記する。
【0206】
図9は、実施形態3の集計システムにおいて、分割遷移確率行列を生成するときの動作シーケンスを示す図である。
【0207】
まず、要素算出部12は、遷移確率行列Aと同じクロネッカー積で表される行列Bを定義する。そして、aの値が属性αaの数n未満である場合に(a<n)、行列Bを構成する各Bjの初期値を以下の式22に示すように設定する(ステップS31)。つまり、この段階では、各Bjは、上述した属性別遷移確率行列となる。
【0208】
【数26】
【0209】
次に、要素算出部12は、以下の式23に示すように各Bjのサイズの総和Siを計算する(ステップS32)。なお、式23においてiは、0から始まる反復のカウンタである。
【0210】
【数27】
【0211】
次に、要素算出部12は、以下の式24に示す範囲において、以下の式25に示すような、2つのBjをクロネッカー積に置き換えた場合のサイズの増加量を算出する(ステップS33)。以降、2つのBjをクロネッカー積に置き換えた場合のサイズの増加量のことを単に増加量という。なお、ここでは、式24に示す範囲のjについて、式25に示すような計算が行われるため、複数の増加量が算出される。また、算出された複数の増加量のそれぞれは、クロネッカー積のそれぞれと対応付けられる。
【0212】
【数28】
【0213】
【数29】
【0214】
次に、要素算出部12は、算出された複数の増加量のうち、最も値の小さな増加量である最小増加量が、LとSiとの差よりも大きいかどうかを判定する(ステップS34)。
【0215】
ステップS34における判定の結果、最小増加量がLとSiとの差よりも大きな場合、要素算出部12は、行列Bを構成する各Bjのそれぞれを分割遷移確率行列とする。
【0216】
そして、要素算出部12は、分割遷移確率行列のそれぞれに含まれる属性別遷移確率行列の要素Apqを算出することにより、複数の分割遷移確率行列を生成する(ステップS35)。そして、処理が終了する。
【0217】
一方、ステップS34における判定の結果、最小増加量がLとSiとの差以下である場合には、要素算出部12は、当該最小増加量に対応するクロネッカー積を算出する(ステップS36)。
【0218】
そして、要素算出部12は、以下の式26に示す範囲において、最小増加量が算出されたjの値に応じ、以下の式27に示すように、行列Bを各Bj'で構成される行列として再定義する(ステップS37)。
【0219】
【数30】
【0220】
【数31】
【0221】
そして、ステップS32の動作へ遷移し、要素算出部12は、反復のカウンタiを1つインクリメントするとともにj'をjとして、ステップS37において再定義された行列Bを構成する各Bjのサイズの総和を計算する。
【0222】
上述したステップS32〜S37の動作は、最小増加量がLとSiとの差よりも大きくなるまで繰り返される。最小増加量がLとSiとの差よりも大きくなると、上述したステップS35で説明したように、複数の分割遷移確率行列が生成される。
【0223】
そして、推定部14は、要素算出部12にて生成された複数の分割遷移確率行列と、集計部13が算出した撹乱後のクロス集計yとに基づき、上述した実施形態1におけるステップS18と同様の処理を実行する。これにより、推定クロス集計が算出される。
【0224】
このように本実施形態の分割方法1においては、属性毎に要素Apqが算出され、その属性毎に算出された要素Apqをそれぞれ有する複数の属性別遷移確率行列が生成される。そして、クロス集計と、複数の属性別遷移確率行列とに基づいて、推定クロス推計が算出される。
【0225】
そのため、推定クロス集計を算出するときに集計装置1が使用するメモリ使用量を上述した実施形態1よりもさらに小さなものとすることができる。
【0226】
例えば、属性数を5とし、各属性の取り得る値の個数を10とした場合、Mは10となる。この場合、要素Apqのサイズを8B(バイト)とすると、1つの属性別遷移確率行列をメモリ上に展開したときのサイズは、8B×102=800Bとなる。そして、属性数が5であるため、全ての属性別遷移確率行列をメモリ上に展開したときのサイズは、4KB(800B×5)と非常に少なく済む。
【0227】
なお、本実施形態の分割方法1を用いた場合、複数の属性別遷移確率行列に基づいて推定クロス集計が算出される。そのため、上述した実施形態1のステップS18における乗算の回数が実施形態1よりも増加する。しかし、例えば高速なメモリ上に遷移確率行列Aを展開しきれず、低速なメモリへのメモリ転送が発生する場合等と比較すると、乗算の回数が数倍程度増えても、本実施形態で示したように遷移確率行列Aを分割した方が処理速度は速くなる。
【0228】
また、本実施形態の分割方法2においては、属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの属性別遷移確率行列を含む複数の分割遷移確率行列が生成される。そして、クロス集計と、複数の分割遷移確率行列とに基づいて、推定クロス推計が算出される。
【0229】
つまり、分割方法2における遷移確率行列Aの分割数は、分割方法1における遷移確率行列Aの分割数よりも少ない。そのため、上述した実施形態1のステップS18における乗算の回数の増加を分割方法1よりも少なくすることができ、処理速度をさらに速くすることができる。
【0230】
なお、本発明においては、集計処理装置1内の処理は上述の専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを集計処理装置1にて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを集計処理装置1に読み込ませ、実行するものであってもよい。集計処理装置1にて読取可能な記録媒体とは、フロッピーディスク(登録商標)、光磁気ディスク、DVD、CDなどの移設可能な記録媒体の他、集計処理装置1に内蔵されたHDD等を指す。この記録媒体に記録されたプログラムは、例えば、集計処理装置1が有する要素算出部12、集計部13および推定部14にて読み込まれ、要素算出部12、集計部13および推定部14の制御によって、上述したものと同様の処理が行われる。
【0231】
ここで、集計処理装置1が有する要素算出部12、集計部13および推定部14は、プログラムが記録された記録媒体から読み込まれたプログラムを実行するコンピュータとして動作するものである。
【0232】
なお、上述したプログラムは、情報提供者端末2−0〜2−(N−1)についても、同様に適用可能である。
【0233】
以上、実施形態1〜3を参照して本発明を説明したが、本発明は上記実施形態1〜3に限定されるものではない。本発明の構成や詳細には、本発明の要旨を逸脱しない範囲で当業者が理解し得る各種の変形が可能である。
【符号の説明】
【0234】
1 集計処理装置
11 通信部
12 要素算出部
13 集計部
14 推定部
15 記憶部
2−0〜2−(N−1) 情報提供者端末
21−0 通信部
22−0 確率変更部
23−0 送信データ決定部
24−0 記憶部
【技術分野】
【0001】
本発明は、集計システム、集計処理装置、情報提供者端末、集計方法およびプログラムに関する。
【背景技術】
【0002】
近年、データベースにおける個々のデータ(例えば、情報提供者端末から取得したアンケート結果など)を統計的手法により秘匿しつつ(つまり、情報提供者端末の有効なデータを経由して抽出できないことを担保しつつ)、クロス集計結果のみを得る技術が考えられている(例えば、非特許文献1および2参照。)。
【0003】
なお、以下に、「クロス集計」と、「単純集計」とについて説明しておく。
【0004】
「単純集計」とは、テーブルに含まれている1つの属性に着目し、該着目した1つの属性のみに関してレコードを集計する集計法である。
【0005】
より具体的には、図10に示す集計結果が、単純集計を行ったときに得られた集計結果の一例である。図10に示した例では、「人数」の列の値が集計値である。
【0006】
一方、「クロス集計」とは、テーブルに含まれている複数の属性に着目し、該着目した属性すべてに関して値が等しいようなレコードを集計する集計法である。
【0007】
より具体的には、図11に示す集計結果が、「クロス集計」を行ったときに得られた集計結果の一例である。図11に示した例では、「年代」と「性別」との2つの属性に着目して、「人数」の集計値を算出している。例えば、「10代」で「男性」であるレコードの数は「4」である。
【0008】
なお、以下では、複数の属性(例えば、「10代」と「男性」)に対する値を1つの値とみなしたものを「クロス値」という。
【先行技術文献】
【非特許文献】
【0009】
【非特許文献1】R.Agrawal,R.Srikant and D.Thomas, “Privacy Preserving OLAP”,SIGMOD Conference ACM, 第251頁〜第262頁,2005
【非特許文献2】高見澤 秀久,有次 正義,「プライバシーを保護するカウント演算の多値属性分類への適用」, DEWS2007, 2007
【非特許文献3】五十嵐 大,千田 浩司,高橋 克巳,「多値属性に適用可能な効率的プライバシー保護クロス集計」,コンピュータセキュリティシンポジウム2008(2008年10月8日〜10日)
【発明の概要】
【発明が解決しようとする課題】
【0010】
しかしながら、非特許文献1および2に開示された一般的な技術においては、個々のデータを秘匿しつつ真のクロス集計の推定値を算出する際、クロス値として指定する各属性が取り得る値が多い場合、これらの技術を適用して構成した集計処理装置がクロス集計結果を算出するために要する時間が非常に長くなってしまうという問題点がある。
【0011】
また、非特許文献1および2に開示された一般的な技術においては、クロス値として指定する各属性が取り得る値が多い場合、これらの技術を適用して構成した集計処理装置がクロス集計結果を算出する際、当該算出のために集計処理装置が使用するメモリ使用量が数GB以上となってしまう場合もある。そのため、当該メモリ使用量が、該算出を行う集計処理装置が搭載しているメモリ量のうちでクロス集計結果の算出用に割当可能なメモリ量よりも多くなってしまった場合には、集計処理装置がクロス集計結果の算出を行うことをできなくなってしまうという問題点がある。
【0012】
本発明は、上述した課題を解決する集計システム、集計処理装置、情報提供者端末、集計方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【0013】
上記課題を解決するために、本発明の集計システムは、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、前記集計処理装置は、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【0014】
【数1】
【0015】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計部と、前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有し、前記情報提供者端末は、前記データを記憶する記憶部と、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更部と、前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有することを特徴とする。
【0016】
また、本発明の集計処理システムにおいては、前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0017】
また、本発明の集計システムにおいては、前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0018】
また、本発明の集計システムにおいては、前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出してもよい。
【0019】
また、本発明の集計システムにおいては、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出してもよい。
【0020】
上記課題を解決するために、本発明の集計処理装置は、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されており、該情報提供者端末から送信されてきた送信データを集計する集計処理装置であって、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【0021】
【数2】
【0022】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計部と、前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有する。
【0023】
また、本発明の集計処理装置においては、前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0024】
また、本発明の集計処理装置においては、前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【0025】
また、本発明の集計処理装置においては、前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出してもよい。
【0026】
また、本発明の集計処理装置においては、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出してもよい。
【0027】
上記課題を解決するために、本発明の情報提供者端末は、集計処理装置と接続された情報提供者端末であって、当該情報提供者端末にて入力を受付けたデータを記憶する記憶部と、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とが前記集計処理装置から送信されてきた際、乱数を生成する確率変更部と、前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有する。
【0028】
上記課題を解決するために、本発明の集計方法は、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、該送信データを集計する集計方法であって、前記情報提供者端末が、前記データを記憶する記憶処理と、前記集計処理装置が、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信処理と、前記情報提供者端末が、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更処理と、前記情報提供者端末が、前記集計処理装置から送信されてきた維持確率および属性と、前記生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定処理と、前記情報提供者端末が、前記決定した送信データを前記集計処理装置へ送信するデータ送信処理と、前記集計処理装置が、
【0029】
【数3】
【0030】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出処理と、前記集計処理装置が、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計処理と、前記集計処理装置が、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定処理とを有する。
【0031】
また、本発明の集計方法においては、前記要素算出処理は、前記集計処理装置が、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する処理とし、前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する処理としてもよい。
【0032】
また、本発明の集計方法においては、前記要素算出処理は、前記集計処理装置が、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する処理とし、前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する処理としてもよい。
【0033】
また、コンピュータに実行させるプログラムであって、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されている集計処理装置に、前記情報提供者端末にて入力を受付けたデータが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信手順と、
【0034】
【数4】
【0035】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出手順と、前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計手順と、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定手順とを実行させる。
【0036】
また、本発明のプログラムにおいては、前記要素算出手順は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する手順とし、前記推定手順は、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する手順としてもよい。
【0037】
また、本発明のプログラムにおいては、前記要素算出手順は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する手順とし、前記推定手順は、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する手順としてもよい。
【発明の効果】
【0038】
本発明によれば、個々のデータを秘匿しつつ真のクロス集計の推定値を算出する際、レコード全体に対する遷移確率行列の次数として、各属性が取り得る値の2進表現を用いた場合よりも値が小さな当該各属性の取り得る値の個数を用いて真のクロス集計の推定値を算出する。
【0039】
このような構成としたため、クロス集計結果を算出するときに集計処理装置が使用するメモリ使用量を一般的な技術よりも小さくすることができる。
【0040】
さらに、メモリ使用量を抑えることにより、クロス値として指定する各属性が取り得る値が多い場合でも、集計処理のうちで最も計算量が多いレコード全体に対する遷移確率行列に対する演算を一般的な技術よりも短い時間で行うことが可能となる。
【図面の簡単な説明】
【0041】
【図1】本発明の実施形態に従った集計システムの構成を示す図である。
【図2】図1に示した集計処理装置の構成を示す図である。
【図3】図2に示した対応情報のデータ構造の一例を示す図である。
【図4】図1に示した情報提供者端末の構成を示す図である。
【図5】クロス集計による集計結果のうちの属性に対して、順番を付与したときの模式図である。
【図6】図4に示したデータ決定情報のデータ構造の一例を示す図である。
【図7】実施形態1の集計システムにおいて、真のクロス集計の推定値を算出するときの動作シーケンスを示す図である。
【図8】実施形態2の集計システムにおいて、真のクロス集計の推定値を算出するときの動作シーケンスを示す図である。
【図9】実施形態3の集計システムにおいて、分割遷移確率行列を生成するときの動作シーケンスを示す図である。
【図10】単純集計により求めた集計結果の一例を示す図である。
【図11】クロス集計により求めた集計結果の一例を示す図である。
【発明を実施するための形態】
【0042】
(実施形態1)
以下、本発明の実施形態1に従った集計システム(集計処理装置、情報提供者端末、集計方法およびプログラムを含む)を説明する。
【0043】
実施形態1の集計システムは、ある結果(データ)が得られた際に、当該結果を反映した下での事後確率を求めるための「所定の事後確率算出条件」を用いて、真のクロス集計xの推定値である「推定クロス集計」を算出する。
【0044】
なお、実施形態1は、「所定の事後確率算出条件」として、「ベイズの定理」を適用した例である。
【0045】
まず、実施形態1の集計システムの構成について説明する。
【0046】
図1に示すように、本集計システムは、集計処理装置1(以下、「集計装置1」という)と、情報提供者端末2−0〜2−(N−1)(以下、「端末2−0〜2−(N−1)」という)とを具備する。
【0047】
なお、以下では、端末2−0〜2−(N−1)の台数が「N」である場合を例に挙げて説明するが、端末2−0〜2−(N−1)の台数は1以上の自然数であればよい。
【0048】
集計装置1は、n個の属性αaそれぞれ(例えば、「年代」、「性別」など)に対する以下の式1に示す要素Apqをp行q列の要素として有する遷移確率行列Aを構成するために、集計対象となるデータが属する属性αaそれぞれに対してあらかじめ定められた維持確率ρaと、当該属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する。
【0049】
なお、「維持確率ρa」とは、端末2−0〜2−(N−1)それぞれが属性αaを撹乱(つまり、確率的な変化)した後においても、属性αaが元の値を維持する確率のことを指す。
【0050】
【数5】
【0051】
ここで、遷移確率行列Aの行の数pおよび列の数qは、以下の式2に示す値である。
【0052】
【数6】
【0053】
また、式1に示したdpaおよびdqaそれぞれは、以下の式3および式4でそれぞれ定義される。
【0054】
【数7】
【0055】
【数8】
【0056】
ここで、式3および式4にて示した「÷」は、整数の除算を示す演算記号である。また、式3および式4にて示した「%」は、剰余算を示す演算記号である。
【0057】
また、集計装置1は、レコード全体に対する遷移確率行列Aに含まれる式1に示したp行q列の要素Apqを算出する。
【0058】
ここで、各属性αaに対する「遷移確率行列Aa」とは、属性αa同士の間での変化の確率を行列形式で表現したものである。
【0059】
また、集計装置1は、端末2−0〜2−(N−1)それぞれから送信されてきた送信データT´(0)a〜T´(N−1)aを集計したクロス集計である「撹乱後のクロス集計y」を算出する。
【0060】
ここで、送信データT´(0)a〜T´(N−1)aとは、端末2−0〜2−(N−1)が、維持確率ρaと属性αaと乱数とに基づいて決定した送信データT´(0)a〜T´(N−1)aのことを指す。
【0061】
そして、集計装置1は、算出した撹乱後のクロス集計yに基づいて、「真のクロス集計x」の推定値である推定クロス集計を算出する。
【0062】
端末2−0〜2−(N−1)それぞれは、端末2−0〜2−(N−1)それぞれに対応するレコードT(0)〜T(N−1)を記憶している。例えば、端末2−0は、レコードT(0)を記憶している。
【0063】
ここで、レコードT(0)〜T(N−1)それぞれは、各属性αaのデータT(0)a〜T(N−1)aを含んでいる。例えば、レコードT(0)であれば、属性αaのデータT(0)aを含んでいる。
【0064】
なお、ここでいう「データT(0)a〜T(N−1)a」とは、例えば、属性αaが「性別」である場合、該属性αaが取り得る値Vα0 〜 VαMa-1(「男性」および「女性」)のうちのいずれか1つの値(例えば、女性)である。
【0065】
つまり、端末2−0〜2−(N−1)それぞれは、レコードT(0)〜T(N−1)それぞれを記憶することにより、データT(0)a〜T(N−1)aそれぞれを記憶している。
【0066】
なお、属性αaの数は「n」個であり、集計装置1および端末2−0〜2−(N−1)それぞれは、当該属性αaの数nを記憶している。
【0067】
なお、各属性αaは、aの値が属性αaの数n未満である場合(a<n)、「Ma」個の値(Vα0 〜 VαMa-1)を取り得る。そして、集計装置1および端末2−0〜2−(N−1)それぞれは、各属性αaが取り得る値の数Maと、各属性αaが取り得る値Vα0 〜 VαMa-1を記憶している。
【0068】
端末2−0〜2−(N−1)は、集計装置1から送信されてきた維持確率ρaおよび属性αaを用いて、当該端末2−0〜2−(N−1)がそれぞれ記憶している該端末2−0〜2−(N−1)にて入力を受付けたデータT(0)a〜T(N−1)aを確率的に変化(「撹乱」)させる。
【0069】
ここで、データT(0)a〜T(N−1)aを確率的に変化させること(撹乱)とは、集計装置1から送信されてきた維持確率ρaと属性αaと、該送信の際に生成した乱数とに基づいて、記憶しているデータのうちから集計装置1へ送信する送信データT´(0)aを決定することを指す。
【0070】
そして、端末2−0〜2−(N−1)それぞれは、確率的に変化させたデータ(つまり、維持確率ρaと属性αaと乱数とに基づいて集計装置1への送信を決定した送信データ)を、集計装置1へ送信する。
【0071】
つぎに、集計装置1が有する構成について詳細に説明する。
【0072】
図2に示すように、集計装置1は、通信部11と、要素算出部12と、集計部13と、推定部14と、記憶部15とを有する。
【0073】
通信部11は、例えば、通信モジュールで構成され、端末2−0〜2−(N−1)それぞれと任意のデータを送受信する。
【0074】
また、通信部11は、n個の各属性αaに対する遷移確率行列Aを構成するために、属性αaそれぞれに対してあらかじめ定められた維持確率ρaと当該属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する「情報送信部」である。
【0075】
また、通信部11は、端末2−0〜2−(N−1)それぞれから送信されてきた、該端末2−0〜2−(N−1)それぞれが確率的に変化させた送信データT´(0)a〜T´(N−1)aそれぞれを受信する。
【0076】
要素算出部12は、n個の各属性αaのデータを有するレコード全体に対する遷移確率行列Aに含まれる式1に示したp行q列の要素Apqそれぞれを算出する。各要素Apqの算出により、要素算出部12は、遷移確率行列Aを生成する。
【0077】
この説明例では、要素算出部12は、p行q列の要素Apqが後述する式5で表されるような正方行列の遷移確率行列Aを生成する。
【0078】
集計部13は、情報提供者端末2−0〜2−(N−1)それぞれから送信されてきた、維持確率ρaと属性αaと乱数とに基づいて決定された送信データT´(0)a〜T´(N−1)aそれぞれを集計することにより、撹乱後のクロス集計yを算出する。
【0079】
推定部14は、集計部13が算出した撹乱後のクロス集計yに基づいて、真のクロス集計xの推定値である「推定クロス集計xi+1」を算出する。なお、推定部14は、算出した推定クロス集計xi+1を、例えば、集計装置1と接続されている外部の表示装置(図示せず)などへ出力する。
【0080】
なお、実施形態1においては、推定部14は、要素算出部12が算出した遷移確率行列Aと、集計部13が算出した撹乱後のクロス集計y(変化後のクロス集計)に基づいて、「推定クロス集計xi+1」を算出する。
【0081】
また、当該推定クロス集計xi+1を算出する際、推定部14は、集計部13が算出した撹乱後のクロス集計y(変化後のクロス集計)が得られた場合の事後確率を求めるための所定の事後確率算出条件として、「ベイズの定理」を適用する。
【0082】
記憶部15は、任意のデータを記憶する。
【0083】
例えば、記憶部15は、対応情報ASを記憶している。
【0084】
図3に示すように、対応情報ASは、データが属する属性αaと、当該属性αaに対してあらかじめ定められた維持確率ρaとを対応付ける情報である。
【0085】
また、記憶部15は、データが属する属性αaの数「n」を記憶している。
【0086】
また、記憶部15は、属性αaそれぞれが取り得る値の数Maと、各属性αaが取り得る値Vα0 〜 VαMa-1を記憶している。図11に示した例においては、属性αaが「性別」である場合、その取り得る値は「男性」と「女性」とのいずれかである。
【0087】
つぎに、端末2−0〜2−(N−1)が有する構成について説明する。なお、端末2−0〜2−(N−1)とは互いに同じ構成を有するため、以下では、端末2−0の構成を例に挙げて説明する。
【0088】
図4に示すように、端末2−0は、通信部21−0と、確率変更部22−0と、送信データ決定部23−0と、記憶部24−0とを有する。
【0089】
通信部21−0は、例えば、通信モジュールで構成され、集計装置1と任意のデータを送受信する。
【0090】
通信部21−0は、集計装置1から送信されてきた、n個の属性αaそれぞれに対してあらかじめ定められた維持確率ρaと属性αaとを受信する。
【0091】
また、通信部21−0は、送信データ決定部23−0が決定した送信データT´(0)aを集計装置1へ送信する「データ送信部」である。
【0092】
なお、端末2−1〜2−(N−1)それぞれは、送信データT´(1)a〜T´(N−1)aそれぞれを集計装置1へ送信する。
【0093】
確率変更部22−0は、集計装置1から送信されてきた維持確率ρaと属性αaとを用いて、記憶部24−0が記憶しているデータT(0)aを確率的に変化させる。
【0094】
より具体的には、確率変更部22−0は、集計装置1から維持確率ρaと属性αaとが送信されてきた際、n個の属性αaそれぞれに対して、実数の値を有する「一様乱数ra(0≦ra≦1)」と、整数の値を有する「一様乱数za(0≦za≦Ma−1)」とを生成する。
【0095】
続いて、確率変更部22−0は、属性αaごとにあらかじめ定められた維持確率ρaと、該属性αaに対して生成した一様乱数raとを比較する。
【0096】
送信データ決定部23−0は、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρa以下である場合(ra≦ ρa)、該端末2−0の属性αaの正しいデータそのものであるデータT(0)aを、送信データT´(0)aとして決定する。
【0097】
また、送信データ決定部23−0は、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρaよりも大きい場合(ra> ρa)、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちから確率変更部22−0が生成した整数値を有する一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0098】
例えば、図11に示した集計結果において、図5に示すように属性αaを「性別」として、該属性αaに属する要素のうちの「男性」に「0」番の順番NBを付与しておき、該属性αaに属する要素のうちの「女性」に「1」番の順番NBを付与しておく。この場合、確率変更部22−0が生成した一様乱数zaが「1」である際、送信データ決定部23−0は、該一様乱数zaと同じ値(1)の順番NBが付与された「女性」を送信データT´(0)aとして決定する。
【0099】
さらに、送信データ決定部23−0は、集計装置1から送信されてきた維持確率ρaの値が「0」である場合、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちから確率変更部22−0が生成した整数値を有する一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0100】
記憶部24−0は、任意のデータを記憶する。
【0101】
例えば、記憶部24−0は、レコードT(0)と、属性データT(0)aとを記憶している。なお、当該レコードT(0)は、属性データT(0)aを含んでいる。
【0102】
また、記憶部24−0は、属性αaの数nを記憶している。
【0103】
さらに、記憶部24−0は、データ決定情報DTを記憶している。
【0104】
図6に示すように、データ決定情報DTは、n個の属性αaと、当該属性αaが取り得るMa個の値Vα0 〜 VαMa-1と、当該値Vα0 〜 VαMa-1それぞれに対して付与された順番NBとを対応付けて記憶している。なお、属性αaが取り得る値Vα0 〜 VαMa-1それぞれに順番NBを付与する順序は任意でよい。
【0105】
つぎに、上述した構成を有する集計システムにおいて、集計装置1が端末2−0〜2−(N−1)から送信されてきた送信データT´(0)a〜T´(N−1)aそれぞれの撹乱後のクロス集計yを算出した場合、上述した一般的な技術よりも高速かつメモリ効率が高いことを、図7に示すフローチャートを参照して説明する。
【0106】
なお、端末2−0〜2−(N−1)とは互いに同じ動作を行うため、以下では、端末2−0の動作を例に挙げて説明する。
【0107】
図7に示すように、集計装置1は、それぞれの属性αaごとにあらかじめ定められた維持確率ρa(0≦ρa≦1)と属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する(ステップS11)。
【0108】
集計装置1から送信されてきた維持確率ρaと属性αaとを受信した際、端末2−0の確率変更部22−0は、各属性αaに対して、実数の値を有する一様乱数ra(0≦ra≦1)と、整数の値を有する一様乱数za(0≦za≦Ma−1)とを生成する(ステップS12)。
【0109】
続いて、確率変更部22−0は、集計装置1から送信されてきた属性αaごとにあらかじめ定められた維持確率ρaと、該属性αaそれぞれに対して生成した実数値を有する一様乱数raとを比較する(ステップS13)。
【0110】
そして、端末2−0の送信データ決定部23−0は、当該比較の結果に応じて、集計装置1へ送信する送信データT´(0)aを決定する(ステップS14)。すると、通信部21−0は、送信データ決定部23−0が決定した送信データT´(0)aを集計装置1へ送信する。
【0111】
なお、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρa以下である場合(ra≦ ρa)、送信データ決定部23−0は、ステップS14において、該端末2−0の属性αaの正しいデータそのものであるデータT(0)aを、送信データT´(0)aとして決定する。
【0112】
また、確率変更部22−0による比較の結果、一様乱数raの値が維持確率ρaよりも大きい場合(ra> ρa)、送信データ決定部23−0は、ステップS14において、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちからステップS12にて生成した一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0113】
また、ステップS14において、送信データ決定部23−0は、集計装置1から送信されてきた維持確率ρaが「0」である場合にも、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが有する値Vα0 〜 VαMa-1のうちでza番の順番が付与された値を、該端末2−0の属性αaの送信データT´(0)aとして決定する。
【0114】
図6に示した例では、属性αaが性別である場合、該属性αaのうちの「男性」に0番の順番NBが付与されていて、該属性αaのうちの要素「女性」に1番の順番NBが付与されている。この場合、一様乱数zaの値が1であれば、送信データ決定部23−0は、当該一様乱数zaと同じ値の順番NB(1番)が付与された値(女性)を送信データT´(0)aとして決定する。
【0115】
なお、維持確率ρaが小さくなるに伴って、送信データT´(0)aは一様にランダムな値に近づいていく。この場合、集計装置1が、端末2−0から送信されてきた送信データT´(0)aを用いて、該端末2−0が記憶している真のデータT(0)aを推定することは困難となる。
【0116】
なお、属性αaのk番目の値Vkaから当該属性αaのl番目の値Vlaへと変化する確率は、遷移確率行列Aklaとして表すことが可能である。この場合、各属性αaに対する遷移確率行列Aaは、各要素Aaklが以下の式5で表されるような行列であり、各属性に対する維持確率ρaと、各属性αaが取り得る値の数「Ma」とから算出できる。なお、式5におけるδklは、「クロネッカーのデルタ」である。
【0117】
【数9】
【0118】
そのため、維持確率ρaが小さくなるに伴って、式1に示した遷移確率行列Aaの要素Apq(値が変化する確率)は、一様乱数における遷移確率の値「1/Ma」に単調に近づいていく。
【0119】
さらに、維持確率ρa=0である場合、遷移確率行列Aaが有する要素Apqは、一様乱数における遷移確率の値そのものである。
【0120】
例えば、属性αaが性別である場合、当該属性αaが取り得る値の数Maは「2」(男性と女性との2つ)であるから、当該属性αaの遷移確率は「1/2」である。
【0121】
また、維持確率ρa=1である場合、遷移確率行列Aaが有する要素Apqは、真のデータT(0)a〜T(N−1)aそのものとなる。
【0122】
端末2−0〜2−(N−1)それぞれから送信データT´(0)a〜送信データT´(N−1)aが送信されてきた場合、集計装置1の集計部13は、「撹乱後のクロス集計y」を算出するために、まず、以下の式6で表される次数の横ベクトルである「撹乱後のクロス集計y」を、遷移確率行列Aaが有する全要素Apqに対して「0」を設定することにより、全要素Apqを初期化する(ステップS15)。
【0123】
【数10】
【0124】
続いて、集計部13は、端末2−0〜2−(N−1)それぞれから送信されてきた送信データT´(0)a〜T´(N−1)aについて、撹乱後のクロス集計yにおける以下の式7に示す順番が付与された要素に、1を加算していく(ステップS16)。なお、式7におけるIaは、送信データT´(0)a〜T´(N−1)aに付与されている順番NBを返すための関数である。
【0125】
【数11】
【0126】
該加算により、集計部13は、撹乱後のクロス集計yを算出する。
【0127】
すると、要素算出部12は、レコード全体に対する遷移確率行列Aの生成手法に従って、以下の式8で表されるようなp行q列の要素Apqそれぞれを有する、式6に示した次数の正方行列である、レコード全体に対する遷移確率行列Aを生成する(ステップS17)。なお、集計装置1が生成した遷移確率行列Aの行の数pおよび列の数qは、式2に示した値である。
【0128】
【数12】
【0129】
非特許文献2に開示された一般的な技術においては、遷移確率行列の次数は、以下の式9で表される。
【0130】
【数13】
【0131】
なお、式9に示した[log2Ma]は、log 2 Ma 以上の最小の整数を表す。
【0132】
一方、本発明の集計装置1においては、遷移確率行列Aの次数は式6に示した次数である。
【0133】
このように、本発明の集計装置1が撹乱後のクロス集計yの算出に用いる式6に示した次数と、一般的な技術にてクロス集計結果の算出に用いる式9に示した次数との間の差異により、集計装置1では、レコード全体に対する遷移確率行列Aに費やすメモリ使用量を、例えば、非特許文献2に開示されたような一般的な技術に比べて小さく抑えることができる。
【0134】
その後、推定部14は、要素算出部12が算出した「遷移確率行列A」と集計部13が算出した「撹乱後のクロス集計y」とを用いて推定クロス集計xi+1を算出し、該推定クロス集計xi+1を出力する(ステップS18)。なお、推定クロス集計xi+1とは、真のクロス集計xの推定値のことを指す。
【0135】
ステップS18において、推定部14は、はじめ、i=0、x0=yを初期値として、式6に示した次数を有する横ベクトルとして表される(i+1)番目の「推定クロス集計xi+1」を、xi+1=xi・((y/(xiA))At)として算出していく。
【0136】
ここで、「・」は、ベクトルの内積を示す演算記号である。また、「/」は、ベクトルの成分ごとの除算を示す演算記号である。また、Atは、行列Aの転置行列を表す。
【0137】
そして、推定部14は、ステップS18における推定クロス集計xi+1の算出を実行していて|xi+1−xi|L1 ≦εN となった場合、iに対する推定クロス集計xi+1を、真のクロス集計xの推定値として出力する。
【0138】
ここで、|xi+1−xi|L1は、(xi+1−xi)のL1ノルムであり、行列の成分ごとの差の絶対値の総和を示す演算記号である。また、εはあらかじめ設定された実数である。
【0139】
なお、ステップS18に示した処理は、ある結果(例えば、撹乱後のクロス集計y)が得られた際に、当該結果を反映した下での事後確率を求めるための「ベイズの定理」に基づいている。
【0140】
ベイズの定理を用いた場合、あるレコードの撹乱後のクロス値Qがqであること(この例では、撹乱後のクロス集計y)が既知である場合に、該レコードの真のクロス値Pがpである事後確率Pr(P=p|Q=q)は、式6に示した値をMとして、真のクロス集計をxとした場合、以下の式10で表される。
【0141】
【数14】
【0142】
さらに、クロス値Qがqである事後確率Pr(Q=q)については、以下の式11が成立する。
【0143】
【数15】
【0144】
そのため、式11に示した関係を用いると、真のクロス値Pがpである事後確率Pr(P=p)は、以下の式12で表すことができる。
【0145】
【数16】
【0146】
ここで、式10に示した関係式と、式12に示した関係式とを用いると、真のクロス集計xpは、以下の式13で表すことができる。
【0147】
【数17】
【0148】
以上より、x=x・((y/(xA))At)という方程式を得ることができる。
【0149】
ステップS18において(i+1)番目の「推定クロス集計xi+1」を算出する際、集計装置1は、上述した方程式x=x・((y/(xA))At)を用いている。
【0150】
なお、推定部14は、ステップS18においてレコード全体に対する遷移確率行列Aについての乗算を実行する。しかしながら、当該乗算を行うときの計算量は、該遷移確率行列Aが有する次数の2乗に比例して増大し、本発明の集計装置1が実行する演算のなかで最も多くの計算量を伴う演算である。しかしながら、当該集計装置1の要素算出部12は、レコード全体に対する遷移確率行列Aを算出し、例えば、非特許文献2に開示されたような一般的な技術よりも、属性αaが取り得る値の数Maに対して遷移確率行列Aが有する次数が非常に小さなものとなる。
【0151】
そのため、集計装置1においては、真のクロス集計xの推定値である推定クロス集計xi+1の算出に要する時間が一般的な技術よりも非常に短くできるとともに、該推定クロス集計xi+1を算出するときに集計装置1が使用するメモリ使用量についても小さなものとできる。
(実施形態2)
つぎに、実施形態2の集計装置1について説明する。
【0152】
実施形態2の集計装置1の構成および端末2−0〜2−(N−1)の構成それぞれは、実施形態1における集計装置1の構成および端末2−0〜2−(N−1)の構成と同じである。
【0153】
ただし、実施形態2の集計装置1は、個別に指定したクロス値に対する推定クロス集計を算出する点で、実施形態1の集計装置1と異なっている。なお、以下では、複数の属性に対する値を1つの値とみなした値であるクロス値として、ベクトルvを指定する場合を例に挙げて説明する。
【0154】
以下に、上述した集計システムにおいて、実施形態2の集計装置1が推定クロス集計xi+1を算出する動作を、図8に示すフローチャートを参照して説明する。
【0155】
図8に示すように、まず、集計装置1は、複数の属性に対する値を1つの値とみなしたクロス値として、ベクトルvを指定する入力を、入力部(図示せず)により利用者から受付ける(ステップS21)。
【0156】
なお、当該ベクトルvに含まれている各成分vaは、推定クロス集計xi+1の算出を行う際の属性αaそれぞれに対する値(例えば、図4に示した「10代」と「男性」)の指定である。
【0157】
すると、集計装置1は、属性αaごと(例えば、「年代」や「性別」)にあらかじめ定められた維持確率ρa(0≦(a≦1)と属性αaとを、端末2−0〜2−(N−1)それぞれへ送信する(ステップS22)。
【0158】
集計装置1から維持確率ρaと属性αaとが送信されてきた場合、端末2−0の確率変更部22−0は、属性αaそれぞれに対して、実数の値を有する一様乱数ra(0≦ra≦1)と、整数の値を有する一様乱数za(0≦za≦Ma−1)とを生成する(ステップS23)。
【0159】
続いて、確率変更部22−0は、属性αaごと(例えば、「年代」や「性別」)に、集計装置1から送信されてきた維持確率ρaと、該属性αaに対して生成した実数値を有する一様乱数raとを比較する(ステップS24)。
【0160】
そして、送信データ決定部23−0は、確率変更部22−0による比較の結果に応じて、集計装置1へ送信する送信データT´(0)aを決定する(ステップS25)。
【0161】
ステップS25において、送信データ決定部23−0は、比較の結果、一様乱数raの値が維持確率ρa以下である場合(ra≦ ρa)、当該端末2−0の属性αaの正しいデータそのものであるデータT(0)aを、送信データT´(0)aとして決定する。
【0162】
また、ステップS25において、送信データ決定部23−0は、比較の結果、一様乱数raの値が維持確率ρaよりも大きい場合(ra> ρa)、または、維持確率ρaが「0」である場合、記憶部24−0が記憶しているデータ決定情報DTに基づいて、属性αaが取り得る値Vα0 〜 VαMa-1のうちからステップS23にて生成した一様乱数zaと同じ値を有する順番NBが付与された値(つまり、za番目に存在する値)を、該端末2−0の属性αaの送信データT´(0)aとして集計装置1へ送信する。
【0163】
このとき、維持確率ρaが小さくなるに伴って送信データT´(0)aは一様にランダムな値に近づく。そのため、集計装置1が、端末2−0から送信されてきた送信データT´(0)aを用いて、該端末2−0が記憶している真のデータT(0)aを推定することは困難となる。
【0164】
その後、通信部21−0は、ステップS25にて送信データ決定部23−0が決定した送信データT´(0)aを集計装置1へ送信する。
【0165】
なお、端末2−1〜2−(N−1)それぞれも、それぞれの比較の結果に応じた送信データT´(1)a〜T´(N−1)aそれぞれを集計装置1へ送信する。
【0166】
端末2−0〜2−(N−1)から送信データT´(0)a〜T´(N−1)aが送信されてきた場合、集計装置1の集計部13は、「撹乱後のクロス集計y」を算出するための処理を実行する。
【0167】
集計部13は、まず、式6に示した次数の横ベクトルである撹乱後のクロス集計yを、遷移確率行列Aaが有する全要素に対して0を設定することにより、全要素を初期化する(ステップS26)。
【0168】
続いて、集計部13は、端末2−0〜2−(N−1)それぞれに対して、撹乱後のクロス集計yにおける式3に示した順番の要素に、「1」を加算していく(ステップS27)。該加算により、集計部13は、撹乱後のクロス集計yを算出する。
【0169】
さらに、集計装置1の推定部14は、各属性αaに対する遷移確率行列Aaの逆行列(Aa)-1を算出する(ステップS28)。
【0170】
逆行列(Aa)-1を算出した場合、さらに、推定部14は、各属性αaに対する値としてベクトルvに含まれている成分vaを有するレコードの数、つまり、クロス値として指定されたベクトルvに対する以下の式14に示すクロス集計を算出して出力する(ステップS29)。
【0171】
【数18】
【0172】
真のクロス集計xが与えられた場合、撹乱後のクロス集計yの期待値のベクトルE(Y)は、E(Y)=xAで表すことができる。そのため、|A|≠0である場合、E(YA-1)=E(Y)A-1=xが成立する。すなわち、yA-1は真のクロス集計xの近似であることが期待できる。
【0173】
ここで、クロネッカー積を用いると、式1に示した各要素を有するようなレコード全体に対する遷移確率行列Aは、以下の式15で表すことが可能である。
【0174】
【数19】
【0175】
式15に示した関係を用いると、クロネッカー積の性質から、遷移確率行列Aの逆行列A-1は、以下の式16で表すことができる。
【0176】
【数20】
【0177】
このことから、遷移確率行列Aと同様に、逆行列A-1が有する各成分は、以下の式17で表すことができる。
【0178】
【数21】
【0179】
そのため、真のクロス集計xは、x=yA-1という関係に基づいて推定することが可能である。
【0180】
また、逆行列A-1のp列目の各成分によって構成される縦ベクトルを縦ベクトルAp-1とした場合、(Ap-1)q = Apq-1が成立する。
【0181】
そのため、真のクロス集計xpは、逆行列A-1のp列目以外の成分を用いることなく、当該逆行列A-1のp列目の各成分を用いて、以下の式18として直接算出することが可能である。
【0182】
【数22】
【0183】
ここで、pとして、クロス値であるベクトルvに対応する以下の式19に示す数を代入する。
【0184】
【数23】
【0185】
すると、Ia(va)=dpaの関係が導出できる。そのため、真のクロス集計xpは、式14に示した値により算出することができる。
【0186】
実施形態2において推定部14が真のクロス集計xの推定値を算出する場合、推定クロス集計の算出に要する所要時間、および、該クロス集計を算出する際に使用するメモリ使用量ともに、遷移確率行列Aの次数に対して線形となる。
【0187】
なお、最終的には、各属性αaに対する値vaをそれぞれ有するようなレコードの数は、(i+1)番目の推定クロス集計xi+1における式19に示した順番が付与された要素が表している。
【0188】
以上説明したように、実施形態1及び実施形態2においては、レコード全体に対する遷移確率行列Aの次数として、各属性αaが取り得る値の数Maの2進表現よりも値が小さな各属性αaが取り得る値の個数Maを用いて、推定クロス集計を算出する。これにより、個々のデータを秘匿しつつ推定クロス集計を算出する際に、集計装置1が使用するメモリ使用量を抑えることができる。
【0189】
さらに、メモリ使用量を抑えることにより、推定クロス集計の集計処理中に最も多くの計算量を伴うボトルネックとなる、レコード全体に対する遷移確率行列Aに対する演算もより短い時間で行うことが可能となる。
(実施形態3)
上述した実施形態1において、レコード全体に対する遷移確率行列Aが有する次数Mは、例えば非特許文献2に開示されたような一般的な技術と比べ、属性αaが取り得る値の個数Maに対して非常に小さなものとすることができる。
【0190】
そのため、推定クロス集計の算出に要する時間を、一般的な技術よりも非常に短くすることができる。また、それとともに、推定クロス集計を算出するときに集計装置1が使用するメモリ使用量も小さなものとすることができる。なお、以降、レコード全体に対する遷移確率行列Aを単に、遷移確率行列Aという。
【0191】
ここで、上述した式2に示したように、遷移確率行列Aの行の数p及び列の数qはM個となる。そのため、遷移確率行列Aは、M次の正方行列である。一般的に、M次の正方行列をメモリ上に展開するときのメモリ使用量は、「正方行列の要素のサイズ×M2」となる。また、遷移確率行列Aが有する次数Mは、上述した式6に示したように、属性αaの取り得る値の個数Maを用いて表される。
【0192】
従って、属性αaの取り得る値の個数Maが多くなると、遷移確率行列Aをメモリ上に展開したときのメモリ使用量は、飛躍的に増加してしまう。
【0193】
そこで、本実施形態では、遷移確率行列Aを生成することなく、推定クロス集計を算出する場合について説明する。
【0194】
なお、本実施形態における集計システムの構成は、上述した実施形態1における構成と同様なので、ここでは、構成の説明は省略する。
【0195】
以下に、本実施形態において推定クロス集計を算出する場合の動作を説明する。
【0196】
まず、遷移確率行列Aは、クロネッカー積を用いると、上述した式15で表すことが可能である。
【0197】
そして、クロネッカー積を用いて表された遷移確率行列Aを分割したBjを設定する。以下の式20にBjを示す。なお、式20においてJは分割数であり、m-1=0とする。
【0198】
【数24】
【0199】
そして、上記の式20に示すようなBjをメモリ上に展開したとき、各Bjのサイズの総和が、予め決められ、推定クロス集計の算出用に割り当て可能なメモリサイズに収まるようにする。各Bjをメモリ上に展開したときのサイズの総和を以下の式21に示す。
【0200】
【数25】
【0201】
ここで、具体的な分割の方法としては、aの値が属性αaの数n未満である場合に(a<n)、Ba=Aaとする方法がある。以降、この方法のことを分割方法1という。つまり、分割方法1では、属性αa毎に複数の遷移確率行列を生成することとなる。以降、属性αa毎の複数の遷移確率行列のそれぞれを属性別遷移確率行列という。
【0202】
分割方法1において要素算出部12は、要素Apqを属性毎に算出する。そして、要素算出部12は、属性毎に算出された要素Apqから、複数の属性別遷移確率行列を生成する。
【0203】
そして、推定部14は、要素算出部12が算出した複数の属性別遷移確率行列と、集計部13が算出した撹乱後のクロス集計yとに基づき、上述した実施形態1におけるステップS18と同様の処理を実行する。これにより、推定クロス集計が算出される。
【0204】
また、上述した分割方法1以外にも例えば、属性別遷移確率行列をメモリ上に展開したときのサイズに基づき、少なくとも1つの属性別遷移確率行列を含む遷移確率行列である分割遷移確率行列を複数生成する方法がある。以降、この方法のことを分割方法2という。
【0205】
以下に、本実施形態の分割方法2において分割遷移確率行列を生成する場合の動作について説明する。なお、以下の説明においては、予め決められ、推定クロス集計の算出用に割り当て可能なメモリサイズをLと表記し、行列Xをメモリ上に展開したときのサイズをsizeXと表記する。
【0206】
図9は、実施形態3の集計システムにおいて、分割遷移確率行列を生成するときの動作シーケンスを示す図である。
【0207】
まず、要素算出部12は、遷移確率行列Aと同じクロネッカー積で表される行列Bを定義する。そして、aの値が属性αaの数n未満である場合に(a<n)、行列Bを構成する各Bjの初期値を以下の式22に示すように設定する(ステップS31)。つまり、この段階では、各Bjは、上述した属性別遷移確率行列となる。
【0208】
【数26】
【0209】
次に、要素算出部12は、以下の式23に示すように各Bjのサイズの総和Siを計算する(ステップS32)。なお、式23においてiは、0から始まる反復のカウンタである。
【0210】
【数27】
【0211】
次に、要素算出部12は、以下の式24に示す範囲において、以下の式25に示すような、2つのBjをクロネッカー積に置き換えた場合のサイズの増加量を算出する(ステップS33)。以降、2つのBjをクロネッカー積に置き換えた場合のサイズの増加量のことを単に増加量という。なお、ここでは、式24に示す範囲のjについて、式25に示すような計算が行われるため、複数の増加量が算出される。また、算出された複数の増加量のそれぞれは、クロネッカー積のそれぞれと対応付けられる。
【0212】
【数28】
【0213】
【数29】
【0214】
次に、要素算出部12は、算出された複数の増加量のうち、最も値の小さな増加量である最小増加量が、LとSiとの差よりも大きいかどうかを判定する(ステップS34)。
【0215】
ステップS34における判定の結果、最小増加量がLとSiとの差よりも大きな場合、要素算出部12は、行列Bを構成する各Bjのそれぞれを分割遷移確率行列とする。
【0216】
そして、要素算出部12は、分割遷移確率行列のそれぞれに含まれる属性別遷移確率行列の要素Apqを算出することにより、複数の分割遷移確率行列を生成する(ステップS35)。そして、処理が終了する。
【0217】
一方、ステップS34における判定の結果、最小増加量がLとSiとの差以下である場合には、要素算出部12は、当該最小増加量に対応するクロネッカー積を算出する(ステップS36)。
【0218】
そして、要素算出部12は、以下の式26に示す範囲において、最小増加量が算出されたjの値に応じ、以下の式27に示すように、行列Bを各Bj'で構成される行列として再定義する(ステップS37)。
【0219】
【数30】
【0220】
【数31】
【0221】
そして、ステップS32の動作へ遷移し、要素算出部12は、反復のカウンタiを1つインクリメントするとともにj'をjとして、ステップS37において再定義された行列Bを構成する各Bjのサイズの総和を計算する。
【0222】
上述したステップS32〜S37の動作は、最小増加量がLとSiとの差よりも大きくなるまで繰り返される。最小増加量がLとSiとの差よりも大きくなると、上述したステップS35で説明したように、複数の分割遷移確率行列が生成される。
【0223】
そして、推定部14は、要素算出部12にて生成された複数の分割遷移確率行列と、集計部13が算出した撹乱後のクロス集計yとに基づき、上述した実施形態1におけるステップS18と同様の処理を実行する。これにより、推定クロス集計が算出される。
【0224】
このように本実施形態の分割方法1においては、属性毎に要素Apqが算出され、その属性毎に算出された要素Apqをそれぞれ有する複数の属性別遷移確率行列が生成される。そして、クロス集計と、複数の属性別遷移確率行列とに基づいて、推定クロス推計が算出される。
【0225】
そのため、推定クロス集計を算出するときに集計装置1が使用するメモリ使用量を上述した実施形態1よりもさらに小さなものとすることができる。
【0226】
例えば、属性数を5とし、各属性の取り得る値の個数を10とした場合、Mは10となる。この場合、要素Apqのサイズを8B(バイト)とすると、1つの属性別遷移確率行列をメモリ上に展開したときのサイズは、8B×102=800Bとなる。そして、属性数が5であるため、全ての属性別遷移確率行列をメモリ上に展開したときのサイズは、4KB(800B×5)と非常に少なく済む。
【0227】
なお、本実施形態の分割方法1を用いた場合、複数の属性別遷移確率行列に基づいて推定クロス集計が算出される。そのため、上述した実施形態1のステップS18における乗算の回数が実施形態1よりも増加する。しかし、例えば高速なメモリ上に遷移確率行列Aを展開しきれず、低速なメモリへのメモリ転送が発生する場合等と比較すると、乗算の回数が数倍程度増えても、本実施形態で示したように遷移確率行列Aを分割した方が処理速度は速くなる。
【0228】
また、本実施形態の分割方法2においては、属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの属性別遷移確率行列を含む複数の分割遷移確率行列が生成される。そして、クロス集計と、複数の分割遷移確率行列とに基づいて、推定クロス推計が算出される。
【0229】
つまり、分割方法2における遷移確率行列Aの分割数は、分割方法1における遷移確率行列Aの分割数よりも少ない。そのため、上述した実施形態1のステップS18における乗算の回数の増加を分割方法1よりも少なくすることができ、処理速度をさらに速くすることができる。
【0230】
なお、本発明においては、集計処理装置1内の処理は上述の専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを集計処理装置1にて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを集計処理装置1に読み込ませ、実行するものであってもよい。集計処理装置1にて読取可能な記録媒体とは、フロッピーディスク(登録商標)、光磁気ディスク、DVD、CDなどの移設可能な記録媒体の他、集計処理装置1に内蔵されたHDD等を指す。この記録媒体に記録されたプログラムは、例えば、集計処理装置1が有する要素算出部12、集計部13および推定部14にて読み込まれ、要素算出部12、集計部13および推定部14の制御によって、上述したものと同様の処理が行われる。
【0231】
ここで、集計処理装置1が有する要素算出部12、集計部13および推定部14は、プログラムが記録された記録媒体から読み込まれたプログラムを実行するコンピュータとして動作するものである。
【0232】
なお、上述したプログラムは、情報提供者端末2−0〜2−(N−1)についても、同様に適用可能である。
【0233】
以上、実施形態1〜3を参照して本発明を説明したが、本発明は上記実施形態1〜3に限定されるものではない。本発明の構成や詳細には、本発明の要旨を逸脱しない範囲で当業者が理解し得る各種の変形が可能である。
【符号の説明】
【0234】
1 集計処理装置
11 通信部
12 要素算出部
13 集計部
14 推定部
15 記憶部
2−0〜2−(N−1) 情報提供者端末
21−0 通信部
22−0 確率変更部
23−0 送信データ決定部
24−0 記憶部
【特許請求の範囲】
【請求項1】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、
前記集計処理装置は、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【数32】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、
前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計部と、
前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有し、
前記情報提供者端末は、
前記データを記憶する記憶部と、
前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更部と、
前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、
前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有することを特徴とする集計システム。
【請求項2】
請求項1に記載の集計システムにおいて、
前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出することを特徴とする集計システム。
【請求項3】
請求項2に記載の集計システムにおいて、
前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出することを特徴とする集計システム。
【請求項4】
請求項1乃至3のいずれか1項に記載の集計システムにおいて、
前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出することを特徴とする集計システム。
【請求項5】
請求項1に記載の集計システムにおいて、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出することを特徴とする集計システム。
【請求項6】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されており、該情報提供者端末から送信されてきた送信データを集計する集計処理装置であって、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【数33】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、
前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計部と、
前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有する集計処理装置。
【請求項7】
請求項6に記載の集計処理装置において、
前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する集計処理装置。
【請求項8】
請求項7に記載の集計処理装置において、
前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する集計処理装置。
【請求項9】
請求項6乃至8のいずれか1項に記載の集計処理装置において、
前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出する集計処理装置。
【請求項10】
請求項6に記載の集計処理装置において、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出する集計処理装置。
【請求項11】
集計処理装置と接続された情報提供者端末であって、
当該情報提供者端末にて入力を受付けたデータを記憶する記憶部と、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とが前記集計処理装置から送信されてきた際、乱数を生成する確率変更部と、
前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、
前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部と、を有する情報提供者端末。
【請求項12】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、該送信データを集計する集計方法であって、
前記情報提供者端末が、前記データを記憶する記憶処理と、
前記集計処理装置が、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信処理と、
前記情報提供者端末が、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更処理と、
前記情報提供者端末が、前記集計処理装置から送信されてきた維持確率および属性と、前記生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定処理と、
前記情報提供者端末が、前記決定した送信データを前記集計処理装置へ送信するデータ送信処理と、
前記集計処理装置が、
【数34】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出処理と、
前記集計処理装置が、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計処理と、
前記集計処理装置が、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定処理と、を有する集計方法。
【請求項13】
請求項12に記載の集計方法において、
前記要素算出処理は、前記集計処理装置が、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する処理であり、
前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する処理である集計方法。
【請求項14】
請求項13に記載の集計方法において、
前記要素算出処理は、前記集計処理装置が、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する処理であり、
前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する処理である集計方法。
【請求項15】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されている集計処理装置に、
前記情報提供者端末にて入力を受付けたデータが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信手順と、
【数35】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出手順と、
前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計手順と、
前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定手順とを実行させるプログラム。
【請求項16】
請求項15に記載のプログラムにおいて、
前記要素算出手順は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する手順であり、
前記推定手順は、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する手順であるプログラム。
【請求項17】
請求項16に記載のプログラムにおいて、
前記要素算出手順は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する手順であり、
前記推定手順は、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する手順であるプログラム。
【請求項1】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、
前記集計処理装置は、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【数32】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、
前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計部と、
前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有し、
前記情報提供者端末は、
前記データを記憶する記憶部と、
前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更部と、
前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、
前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有することを特徴とする集計システム。
【請求項2】
請求項1に記載の集計システムにおいて、
前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出することを特徴とする集計システム。
【請求項3】
請求項2に記載の集計システムにおいて、
前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出することを特徴とする集計システム。
【請求項4】
請求項1乃至3のいずれか1項に記載の集計システムにおいて、
前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出することを特徴とする集計システム。
【請求項5】
請求項1に記載の集計システムにおいて、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出することを特徴とする集計システム。
【請求項6】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されており、該情報提供者端末から送信されてきた送信データを集計する集計処理装置であって、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【数33】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出部と、
前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計部と、
前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有する集計処理装置。
【請求項7】
請求項6に記載の集計処理装置において、
前記要素算出部は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する集計処理装置。
【請求項8】
請求項7に記載の集計処理装置において、
前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する集計処理装置。
【請求項9】
請求項6乃至8のいずれか1項に記載の集計処理装置において、
前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出する集計処理装置。
【請求項10】
請求項6に記載の集計処理装置において、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出する集計処理装置。
【請求項11】
集計処理装置と接続された情報提供者端末であって、
当該情報提供者端末にて入力を受付けたデータを記憶する記憶部と、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とが前記集計処理装置から送信されてきた際、乱数を生成する確率変更部と、
前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、
前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部と、を有する情報提供者端末。
【請求項12】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、該送信データを集計する集計方法であって、
前記情報提供者端末が、前記データを記憶する記憶処理と、
前記集計処理装置が、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信処理と、
前記情報提供者端末が、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更処理と、
前記情報提供者端末が、前記集計処理装置から送信されてきた維持確率および属性と、前記生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定処理と、
前記情報提供者端末が、前記決定した送信データを前記集計処理装置へ送信するデータ送信処理と、
前記集計処理装置が、
【数34】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出処理と、
前記集計処理装置が、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計処理と、
前記集計処理装置が、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定処理と、を有する集計方法。
【請求項13】
請求項12に記載の集計方法において、
前記要素算出処理は、前記集計処理装置が、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する処理であり、
前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する処理である集計方法。
【請求項14】
請求項13に記載の集計方法において、
前記要素算出処理は、前記集計処理装置が、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する処理であり、
前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する処理である集計方法。
【請求項15】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されている集計処理装置に、
前記情報提供者端末にて入力を受付けたデータが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信手順と、
【数35】
で表される要素Apqをそれぞれ算出し、該算出した要素Apqを有する遷移確率行列を生成する要素算出手順と、
前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計手順と、
前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定手順とを実行させるプログラム。
【請求項16】
請求項15に記載のプログラムにおいて、
前記要素算出手順は、前記属性毎に前記要素Apqを算出し、該属性毎に算出した前記要素Apqをそれぞれ有する複数の属性別遷移確率行列を生成する手順であり、
前記推定手順は、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する手順であるプログラム。
【請求項17】
請求項16に記載のプログラムにおいて、
前記要素算出手順は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも1つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する手順であり、
前記推定手順は、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する手順であるプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2010−108488(P2010−108488A)
【公開日】平成22年5月13日(2010.5.13)
【国際特許分類】
【出願番号】特願2009−224212(P2009−224212)
【出願日】平成21年9月29日(2009.9.29)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
【公開日】平成22年5月13日(2010.5.13)
【国際特許分類】
【出願日】平成21年9月29日(2009.9.29)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】
[ Back to top ]