(57)【要約】【課題】データを秘匿しつつクロス集計を算出する際の、メモリ使用量を小さくする。【解決手段】集計装置１は、各属性に対してあらかじめ定められた維持確率を端末２−０〜２−（Ｎ−１）それぞれへ送信する。その後、集計装置１は、端末それぞれから送信されてきた、該端末が維持確率と属性に対して生成した乱数とに基づいて決定した該属性のデータそれぞれを用いて、該変化後のクロス集計を算出する。さらに、集計装置１は、遷移確率行列を生成する。そして、集計装置１は、算出した変化後のクロス集計と生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する。【選択図】図１
2010108488.tif 000002
【特許請求の範囲】
【請求項１】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、
前記集計処理装置は、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【数３２】
2010108488.tif 000034
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出部と、
前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計部と、
前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有し、
前記情報提供者端末は、
前記データを記憶する記憶部と、
前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更部と、
前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、
前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有することを特徴とする集計システム。
【請求項２】
請求項１に記載の集計システムにおいて、
前記要素算出部は、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出することを特徴とする集計システム。
【請求項３】
請求項２に記載の集計システムにおいて、
前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出することを特徴とする集計システム。
【請求項４】
請求項１乃至３のいずれか１項に記載の集計システムにおいて、
前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出することを特徴とする集計システム。
【請求項５】
請求項１に記載の集計システムにおいて、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出することを特徴とする集計システム。
【請求項６】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されており、該情報提供者端末から送信されてきた送信データを集計する集計処理装置であって、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【数３３】
2010108488.tif 000035
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出部と、
前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計部と、
前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有する集計処理装置。
【請求項７】
請求項６に記載の集計処理装置において、
前記要素算出部は、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する集計処理装置。
【請求項８】
請求項７に記載の集計処理装置において、
前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する集計処理装置。
【請求項９】
請求項６乃至８のいずれか１項に記載の集計処理装置において、
前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出する集計処理装置。
【請求項１０】
請求項６に記載の集計処理装置において、
前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出する集計処理装置。
【請求項１１】
集計処理装置と接続された情報提供者端末であって、
当該情報提供者端末にて入力を受付けたデータを記憶する記憶部と、
前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とが前記集計処理装置から送信されてきた際、乱数を生成する確率変更部と、
前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、
前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部と、を有する情報提供者端末。
【請求項１２】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、該送信データを集計する集計方法であって、
前記情報提供者端末が、前記データを記憶する記憶処理と、
前記集計処理装置が、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信処理と、
前記情報提供者端末が、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更処理と、
前記情報提供者端末が、前記集計処理装置から送信されてきた維持確率および属性と、前記生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定処理と、
前記情報提供者端末が、前記決定した送信データを前記集計処理装置へ送信するデータ送信処理と、
前記集計処理装置が、
【数３４】
2010108488.tif 000036
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出処理と、
前記集計処理装置が、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計処理と、
前記集計処理装置が、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定処理と、を有する集計方法。
【請求項１３】
請求項１２に記載の集計方法において、
前記要素算出処理は、前記集計処理装置が、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成する処理であり、
前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する処理である集計方法。
【請求項１４】
請求項１３に記載の集計方法において、
前記要素算出処理は、前記集計処理装置が、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する処理であり、
前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する処理である集計方法。
【請求項１５】
入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されている集計処理装置に、
前記情報提供者端末にて入力を受付けたデータが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信手順と、
【数３５】
2010108488.tif 000037
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出手順と、
前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計手順と、
前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定手順とを実行させるプログラム。
【請求項１６】
請求項１５に記載のプログラムにおいて、
前記要素算出手順は、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成する手順であり、
前記推定手順は、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する手順であるプログラム。
【請求項１７】
請求項１６に記載のプログラムにおいて、
前記要素算出手順は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する手順であり、
前記推定手順は、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する手順であるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、集計システム、集計処理装置、情報提供者端末、集計方法およびプログラムに関する。
【背景技術】
【０００２】
近年、データベースにおける個々のデータ（例えば、情報提供者端末から取得したアンケート結果など）を統計的手法により秘匿しつつ（つまり、情報提供者端末の有効なデータを経由して抽出できないことを担保しつつ）、クロス集計結果のみを得る技術が考えられている（例えば、非特許文献１および２参照。）。
【０００３】
なお、以下に、「クロス集計」と、「単純集計」とについて説明しておく。
【０００４】
「単純集計」とは、テーブルに含まれている１つの属性に着目し、該着目した１つの属性のみに関してレコードを集計する集計法である。
【０００５】
より具体的には、図１０に示す集計結果が、単純集計を行ったときに得られた集計結果の一例である。図１０に示した例では、「人数」の列の値が集計値である。
【０００６】
一方、「クロス集計」とは、テーブルに含まれている複数の属性に着目し、該着目した属性すべてに関して値が等しいようなレコードを集計する集計法である。
【０００７】
より具体的には、図１１に示す集計結果が、「クロス集計」を行ったときに得られた集計結果の一例である。図１１に示した例では、「年代」と「性別」との２つの属性に着目して、「人数」の集計値を算出している。例えば、「１０代」で「男性」であるレコードの数は「４」である。
【０００８】
なお、以下では、複数の属性（例えば、「１０代」と「男性」）に対する値を１つの値とみなしたものを「クロス値」という。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ｒ．Ａｇｒａｗａｌ，Ｒ．Ｓｒｉｋａｎｔ  ａｎｄ  Ｄ．Ｔｈｏｍａｓ，  “Ｐｒｉｖａｃｙ  Ｐｒｅｓｅｒｖｉｎｇ  ＯＬＡＰ”，ＳＩＧＭＯＤ  Ｃｏｎｆｅｒｅｎｃｅ  ＡＣＭ，  第２５１頁〜第２６２頁，２００５
【非特許文献２】高見澤  秀久，有次  正義，「プライバシーを保護するカウント演算の多値属性分類への適用」，  ＤＥＷＳ２００７，  ２００７
【非特許文献３】五十嵐  大，千田  浩司，高橋  克巳,「多値属性に適用可能な効率的プライバシー保護クロス集計」，コンピュータセキュリティシンポジウム２００８（２００８年１０月８日〜１０日）
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、非特許文献１および２に開示された一般的な技術においては、個々のデータを秘匿しつつ真のクロス集計の推定値を算出する際、クロス値として指定する各属性が取り得る値が多い場合、これらの技術を適用して構成した集計処理装置がクロス集計結果を算出するために要する時間が非常に長くなってしまうという問題点がある。
【００１１】
また、非特許文献１および２に開示された一般的な技術においては、クロス値として指定する各属性が取り得る値が多い場合、これらの技術を適用して構成した集計処理装置がクロス集計結果を算出する際、当該算出のために集計処理装置が使用するメモリ使用量が数ＧＢ以上となってしまう場合もある。そのため、当該メモリ使用量が、該算出を行う集計処理装置が搭載しているメモリ量のうちでクロス集計結果の算出用に割当可能なメモリ量よりも多くなってしまった場合には、集計処理装置がクロス集計結果の算出を行うことをできなくなってしまうという問題点がある。
【００１２】
本発明は、上述した課題を解決する集計システム、集計処理装置、情報提供者端末、集計方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明の集計システムは、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、前記集計処理装置は、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【００１４】
【数１】
2010108488.tif 000003
【００１５】
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出部と、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計部と、前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有し、前記情報提供者端末は、前記データを記憶する記憶部と、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更部と、前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有することを特徴とする。
【００１６】
また、本発明の集計処理システムにおいては、前記要素算出部は、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【００１７】
また、本発明の集計システムにおいては、前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【００１８】
また、本発明の集計システムにおいては、前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出してもよい。
【００１９】
また、本発明の集計システムにおいては、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出してもよい。
【００２０】
上記課題を解決するために、本発明の集計処理装置は、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されており、該情報提供者端末から送信されてきた送信データを集計する集計処理装置であって、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信部と、
【００２１】
【数２】
2010108488.tif 000004
【００２２】
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出部と、前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計部と、前記集計部が生成したクロス集計と、前記要素算出部が生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定部とを有する。
【００２３】
また、本発明の集計処理装置においては、前記要素算出部は、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【００２４】
また、本発明の集計処理装置においては、前記要素算出部は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成し、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出してもよい。
【００２５】
また、本発明の集計処理装置においては、前記推定部は、前記集計部が生成したクロス集計に対して、該クロス集計が得られた場合の事後確率を求めるための条件である所定の事後確率算出条件を適用することにより、前記推定クロス集計を算出してもよい。
【００２６】
また、本発明の集計処理装置においては、前記推定部は、前記集計部が生成したクロス集計と、前記要素算出部が算出した遷移確率行列の逆行列とに基づいて、前記推定クロス集計を算出してもよい。
【００２７】
上記課題を解決するために、本発明の情報提供者端末は、集計処理装置と接続された情報提供者端末であって、当該情報提供者端末にて入力を受付けたデータを記憶する記憶部と、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とが前記集計処理装置から送信されてきた際、乱数を生成する確率変更部と、前記集計処理装置から送信されてきた維持確率および属性と、前記確率変更部が生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定部と、前記送信データ決定部が決定した送信データを前記集計処理装置へ送信するデータ送信部とを有する。
【００２８】
上記課題を解決するために、本発明の集計方法は、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と、該情報提供者端末から送信されてきた送信データを集計する集計処理装置とを具備する集計システムにおいて、該送信データを集計する集計方法であって、前記情報提供者端末が、前記データを記憶する記憶処理と、前記集計処理装置が、前記データが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信処理と、前記情報提供者端末が、前記集計処理装置から維持確率と属性とが送信されてきた際、乱数を生成する確率変更処理と、前記情報提供者端末が、前記集計処理装置から送信されてきた維持確率および属性と、前記生成した乱数とに基づいて、前記記憶しているデータのうちから該集計処理装置へ送信する前記送信データを決定する送信データ決定処理と、前記情報提供者端末が、前記決定した送信データを前記集計処理装置へ送信するデータ送信処理と、前記集計処理装置が、
【００２９】
【数３】
2010108488.tif 000005
【００３０】
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出処理と、前記集計処理装置が、前記情報提供者端末から送信されてきた送信データを集計したクロス集計を生成する集計処理と、前記集計処理装置が、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定処理とを有する。
【００３１】
また、本発明の集計方法においては、前記要素算出処理は、前記集計処理装置が、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成する処理とし、前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する処理としてもよい。
【００３２】
また、本発明の集計方法においては、前記要素算出処理は、前記集計処理装置が、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する処理とし、前記推定処理は、前記集計処理装置が、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する処理としてもよい。
【００３３】
また、コンピュータに実行させるプログラムであって、入力を受付けたデータのうちから決定した送信データを送信する情報提供者端末と接続されている集計処理装置に、前記情報提供者端末にて入力を受付けたデータが属する属性に対してあらかじめ定められた維持確率と、前記属性とを前記情報提供者端末へ送信する情報送信手順と、
【００３４】
【数４】
2010108488.tif 000006
【００３５】
で表される要素Ａpqをそれぞれ算出し、該算出した要素Ａpqを有する遷移確率行列を生成する要素算出手順と、前記情報提供者端末から送信されてきた、前記維持確率と前記属性と該情報提供者端末が生成した乱数とに基づいて該情報提供者端末が決定した送信データを集計したクロス集計を生成する集計手順と、前記生成したクロス集計と、前記生成した遷移確率行列とに基づいて、真のクロス集計の推定値である推定クロス集計を算出する推定手順とを実行させる。
【００３６】
また、本発明のプログラムにおいては、前記要素算出手順は、前記属性毎に前記要素Ａpqを算出し、該属性毎に算出した前記要素Ａpqをそれぞれ有する複数の属性別遷移確率行列を生成する手順とし、前記推定手順は、前記生成したクロス集計と、前記生成した複数の属性別遷移確率行列とに基づいて、前記推定クロス推計を算出する手順としてもよい。
【００３７】
また、本発明のプログラムにおいては、前記要素算出手順は、前記属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの前記属性別遷移確率行列を含む複数の分割遷移確率行列を生成する手順とし、前記推定手順は、前記生成したクロス集計と、前記生成した複数の分割遷移確率行列とに基づいて、前記推定クロス推計を算出する手順としてもよい。
【発明の効果】
【００３８】
本発明によれば、個々のデータを秘匿しつつ真のクロス集計の推定値を算出する際、レコード全体に対する遷移確率行列の次数として、各属性が取り得る値の２進表現を用いた場合よりも値が小さな当該各属性の取り得る値の個数を用いて真のクロス集計の推定値を算出する。
【００３９】
このような構成としたため、クロス集計結果を算出するときに集計処理装置が使用するメモリ使用量を一般的な技術よりも小さくすることができる。
【００４０】
さらに、メモリ使用量を抑えることにより、クロス値として指定する各属性が取り得る値が多い場合でも、集計処理のうちで最も計算量が多いレコード全体に対する遷移確率行列に対する演算を一般的な技術よりも短い時間で行うことが可能となる。
【図面の簡単な説明】
【００４１】
【図１】本発明の実施形態に従った集計システムの構成を示す図である。
【図２】図１に示した集計処理装置の構成を示す図である。
【図３】図２に示した対応情報のデータ構造の一例を示す図である。
【図４】図１に示した情報提供者端末の構成を示す図である。
【図５】クロス集計による集計結果のうちの属性に対して、順番を付与したときの模式図である。
【図６】図４に示したデータ決定情報のデータ構造の一例を示す図である。
【図７】実施形態１の集計システムにおいて、真のクロス集計の推定値を算出するときの動作シーケンスを示す図である。
【図８】実施形態２の集計システムにおいて、真のクロス集計の推定値を算出するときの動作シーケンスを示す図である。
【図９】実施形態３の集計システムにおいて、分割遷移確率行列を生成するときの動作シーケンスを示す図である。
【図１０】単純集計により求めた集計結果の一例を示す図である。
【図１１】クロス集計により求めた集計結果の一例を示す図である。
【発明を実施するための形態】
【００４２】
（実施形態１）
以下、本発明の実施形態１に従った集計システム（集計処理装置、情報提供者端末、集計方法およびプログラムを含む）を説明する。
【００４３】
実施形態１の集計システムは、ある結果（データ）が得られた際に、当該結果を反映した下での事後確率を求めるための「所定の事後確率算出条件」を用いて、真のクロス集計ｘの推定値である「推定クロス集計」を算出する。
【００４４】
なお、実施形態１は、「所定の事後確率算出条件」として、「ベイズの定理」を適用した例である。
【００４５】
まず、実施形態１の集計システムの構成について説明する。
【００４６】
図１に示すように、本集計システムは、集計処理装置１（以下、「集計装置１」という）と、情報提供者端末２−０〜２−（Ｎ−１）（以下、「端末２−０〜２−（Ｎ−１）」という）とを具備する。
【００４７】
なお、以下では、端末２−０〜２−（Ｎ−１）の台数が「Ｎ」である場合を例に挙げて説明するが、端末２−０〜２−（Ｎ−１）の台数は１以上の自然数であればよい。
【００４８】
集計装置１は、ｎ個の属性αaそれぞれ（例えば、「年代」、「性別」など）に対する以下の式１に示す要素Ａpqをｐ行ｑ列の要素として有する遷移確率行列Ａを構成するために、集計対象となるデータが属する属性αaそれぞれに対してあらかじめ定められた維持確率ρaと、当該属性αaとを、端末２−０〜２−（Ｎ−１）それぞれへ送信する。
【００４９】
なお、「維持確率ρa」とは、端末２−０〜２−（Ｎ−１）それぞれが属性αaを撹乱（つまり、確率的な変化）した後においても、属性αaが元の値を維持する確率のことを指す。
【００５０】
【数５】
2010108488.tif 000007
【００５１】
ここで、遷移確率行列Ａの行の数ｐおよび列の数ｑは、以下の式２に示す値である。
【００５２】
【数６】
2010108488.tif 000008
【００５３】
また、式１に示したｄpaおよびｄqaそれぞれは、以下の式３および式４でそれぞれ定義される。
【００５４】
【数７】
2010108488.tif 000009
【００５５】
【数８】
2010108488.tif 000010
【００５６】
ここで、式３および式４にて示した「÷」は、整数の除算を示す演算記号である。また、式３および式４にて示した「％」は、剰余算を示す演算記号である。
【００５７】
また、集計装置１は、レコード全体に対する遷移確率行列Ａに含まれる式１に示したｐ行ｑ列の要素Ａpqを算出する。
【００５８】
ここで、各属性αaに対する「遷移確率行列Ａa」とは、属性αa同士の間での変化の確率を行列形式で表現したものである。
【００５９】
また、集計装置１は、端末２−０〜２−（Ｎ−１）それぞれから送信されてきた送信データＴ´（０）a〜Ｔ´（Ｎ−１）aを集計したクロス集計である「撹乱後のクロス集計ｙ」を算出する。
【００６０】
ここで、送信データＴ´（０）a〜Ｔ´（Ｎ−１）aとは、端末２−０〜２−（Ｎ−１）が、維持確率ρaと属性αaと乱数とに基づいて決定した送信データＴ´（０）a〜Ｔ´（Ｎ−１）aのことを指す。
【００６１】
そして、集計装置１は、算出した撹乱後のクロス集計ｙに基づいて、「真のクロス集計ｘ」の推定値である推定クロス集計を算出する。
【００６２】
端末２−０〜２−（Ｎ−１）それぞれは、端末２−０〜２−（Ｎ−１）それぞれに対応するレコードＴ（０）〜Ｔ（Ｎ−１）を記憶している。例えば、端末２−０は、レコードＴ（０）を記憶している。
【００６３】
ここで、レコードＴ（０）〜Ｔ（Ｎ−１）それぞれは、各属性αaのデータＴ（０）a〜Ｔ（Ｎ−１）aを含んでいる。例えば、レコードＴ（０）であれば、属性αaのデータＴ（０）aを含んでいる。
【００６４】
なお、ここでいう「データＴ（０）a〜Ｔ（Ｎ−１）a」とは、例えば、属性αaが「性別」である場合、該属性αaが取り得る値Ｖα0 〜 ＶαMa-1（「男性」および「女性」）のうちのいずれか１つの値（例えば、女性）である。
【００６５】
つまり、端末２−０〜２−（Ｎ−１）それぞれは、レコードＴ（０）〜Ｔ（Ｎ−１）それぞれを記憶することにより、データＴ（０）a〜Ｔ（Ｎ−１）aそれぞれを記憶している。
【００６６】
なお、属性αaの数は「ｎ」個であり、集計装置１および端末２−０〜２−（Ｎ−１）それぞれは、当該属性αaの数ｎを記憶している。
【００６７】
なお、各属性αaは、ａの値が属性αaの数ｎ未満である場合（ａ＜ｎ）、「Ｍa」個の値（Ｖα0 〜 ＶαMa-1）を取り得る。そして、集計装置１および端末２−０〜２−（Ｎ−１）それぞれは、各属性αaが取り得る値の数Ｍaと、各属性αaが取り得る値Ｖα0 〜 ＶαMa-1を記憶している。
【００６８】
端末２−０〜２−（Ｎ−１）は、集計装置１から送信されてきた維持確率ρaおよび属性αaを用いて、当該端末２−０〜２−（Ｎ−１）がそれぞれ記憶している該端末２−０〜２−（Ｎ−１）にて入力を受付けたデータＴ（０）a〜Ｔ（Ｎ−１）aを確率的に変化（「撹乱」）させる。
【００６９】
ここで、データＴ（０）a〜Ｔ（Ｎ−１）aを確率的に変化させること（撹乱）とは、集計装置１から送信されてきた維持確率ρaと属性αaと、該送信の際に生成した乱数とに基づいて、記憶しているデータのうちから集計装置１へ送信する送信データＴ´（０）aを決定することを指す。
【００７０】
そして、端末２−０〜２−（Ｎ−１）それぞれは、確率的に変化させたデータ（つまり、維持確率ρaと属性αaと乱数とに基づいて集計装置１への送信を決定した送信データ）を、集計装置１へ送信する。
【００７１】
つぎに、集計装置１が有する構成について詳細に説明する。
【００７２】
図２に示すように、集計装置１は、通信部１１と、要素算出部１２と、集計部１３と、推定部１４と、記憶部１５とを有する。
【００７３】
通信部１１は、例えば、通信モジュールで構成され、端末２−０〜２−（Ｎ−１）それぞれと任意のデータを送受信する。
【００７４】
また、通信部１１は、ｎ個の各属性αaに対する遷移確率行列Ａを構成するために、属性αaそれぞれに対してあらかじめ定められた維持確率ρaと当該属性αaとを、端末２−０〜２−（Ｎ−１）それぞれへ送信する「情報送信部」である。
【００７５】
また、通信部１１は、端末２−０〜２−（Ｎ−１）それぞれから送信されてきた、該端末２−０〜２−（Ｎ−１）それぞれが確率的に変化させた送信データＴ´（０）a〜Ｔ´（Ｎ−１）aそれぞれを受信する。
【００７６】
要素算出部１２は、ｎ個の各属性αaのデータを有するレコード全体に対する遷移確率行列Ａに含まれる式１に示したｐ行ｑ列の要素Ａpqそれぞれを算出する。各要素Ａpqの算出により、要素算出部１２は、遷移確率行列Ａを生成する。
【００７７】
この説明例では、要素算出部１２は、ｐ行ｑ列の要素Ａpqが後述する式５で表されるような正方行列の遷移確率行列Ａを生成する。
【００７８】
集計部１３は、情報提供者端末２−０〜２−（Ｎ−１）それぞれから送信されてきた、維持確率ρaと属性αaと乱数とに基づいて決定された送信データＴ´（０）a〜Ｔ´（Ｎ−１）aそれぞれを集計することにより、撹乱後のクロス集計ｙを算出する。
【００７９】
推定部１４は、集計部１３が算出した撹乱後のクロス集計ｙに基づいて、真のクロス集計ｘの推定値である「推定クロス集計ｘi+1」を算出する。なお、推定部１４は、算出した推定クロス集計ｘi+1を、例えば、集計装置１と接続されている外部の表示装置（図示せず）などへ出力する。
【００８０】
なお、実施形態１においては、推定部１４は、要素算出部１２が算出した遷移確率行列Ａと、集計部１３が算出した撹乱後のクロス集計ｙ（変化後のクロス集計）に基づいて、「推定クロス集計ｘi+1」を算出する。
【００８１】
また、当該推定クロス集計ｘi+1を算出する際、推定部１４は、集計部１３が算出した撹乱後のクロス集計ｙ（変化後のクロス集計）が得られた場合の事後確率を求めるための所定の事後確率算出条件として、「ベイズの定理」を適用する。
【００８２】
記憶部１５は、任意のデータを記憶する。
【００８３】
例えば、記憶部１５は、対応情報ＡＳを記憶している。
【００８４】
図３に示すように、対応情報ＡＳは、データが属する属性αaと、当該属性αaに対してあらかじめ定められた維持確率ρaとを対応付ける情報である。
【００８５】
また、記憶部１５は、データが属する属性αaの数「ｎ」を記憶している。
【００８６】
また、記憶部１５は、属性αaそれぞれが取り得る値の数Ｍaと、各属性αaが取り得る値Ｖα0 〜 ＶαMa-1を記憶している。図１１に示した例においては、属性αaが「性別」である場合、その取り得る値は「男性」と「女性」とのいずれかである。
【００８７】
つぎに、端末２−０〜２−（Ｎ−１）が有する構成について説明する。なお、端末２−０〜２−（Ｎ−１）とは互いに同じ構成を有するため、以下では、端末２−０の構成を例に挙げて説明する。
【００８８】
図４に示すように、端末２−０は、通信部２１−０と、確率変更部２２−０と、送信データ決定部２３−０と、記憶部２４−０とを有する。
【００８９】
通信部２１−０は、例えば、通信モジュールで構成され、集計装置１と任意のデータを送受信する。
【００９０】
通信部２１−０は、集計装置１から送信されてきた、ｎ個の属性αaそれぞれに対してあらかじめ定められた維持確率ρaと属性αaとを受信する。
【００９１】
また、通信部２１−０は、送信データ決定部２３−０が決定した送信データＴ´（０）aを集計装置１へ送信する「データ送信部」である。
【００９２】
なお、端末２−１〜２−（Ｎ−１）それぞれは、送信データＴ´（１）a〜Ｔ´（Ｎ−１）aそれぞれを集計装置１へ送信する。
【００９３】
確率変更部２２−０は、集計装置１から送信されてきた維持確率ρaと属性αaとを用いて、記憶部２４−０が記憶しているデータＴ（０）aを確率的に変化させる。
【００９４】
より具体的には、確率変更部２２−０は、集計装置１から維持確率ρaと属性αaとが送信されてきた際、ｎ個の属性αaそれぞれに対して、実数の値を有する「一様乱数ｒa（０≦ｒa≦１）」と、整数の値を有する「一様乱数ｚa（０≦ｚa≦Ｍa−１）」とを生成する。
【００９５】
続いて、確率変更部２２−０は、属性αaごとにあらかじめ定められた維持確率ρaと、該属性αaに対して生成した一様乱数ｒaとを比較する。
【００９６】
送信データ決定部２３−０は、確率変更部２２−０による比較の結果、一様乱数ｒaの値が維持確率ρa以下である場合（ｒa≦ ρa）、該端末２−０の属性αaの正しいデータそのものであるデータＴ（０）aを、送信データＴ´（０）aとして決定する。
【００９７】
また、送信データ決定部２３−０は、確率変更部２２−０による比較の結果、一様乱数ｒaの値が維持確率ρaよりも大きい場合（ｒa＞ ρa）、記憶部２４−０が記憶しているデータ決定情報ＤＴに基づいて、属性αaが取り得る値Ｖα0 〜 ＶαMa-1のうちから確率変更部２２−０が生成した整数値を有する一様乱数ｚaと同じ値を有する順番ＮＢが付与された値（つまり、ｚa番目に存在する値）を、該端末２−０の属性αaの送信データＴ´（０）aとして決定する。
【００９８】
例えば、図１１に示した集計結果において、図５に示すように属性αaを「性別」として、該属性αaに属する要素のうちの「男性」に「０」番の順番ＮＢを付与しておき、該属性αaに属する要素のうちの「女性」に「１」番の順番ＮＢを付与しておく。この場合、確率変更部２２−０が生成した一様乱数ｚaが「１」である際、送信データ決定部２３−０は、該一様乱数ｚaと同じ値（１）の順番ＮＢが付与された「女性」を送信データＴ´（０）aとして決定する。
【００９９】
さらに、送信データ決定部２３−０は、集計装置１から送信されてきた維持確率ρaの値が「０」である場合、記憶部２４−０が記憶しているデータ決定情報ＤＴに基づいて、属性αaが取り得る値Ｖα0 〜 ＶαMa-1のうちから確率変更部２２−０が生成した整数値を有する一様乱数ｚaと同じ値を有する順番ＮＢが付与された値（つまり、ｚa番目に存在する値）を、該端末２−０の属性αaの送信データＴ´（０）aとして決定する。
【０１００】
記憶部２４−０は、任意のデータを記憶する。
【０１０１】
例えば、記憶部２４−０は、レコードＴ（０）と、属性データＴ（０）aとを記憶している。なお、当該レコードＴ（０）は、属性データＴ（０）aを含んでいる。
【０１０２】
また、記憶部２４−０は、属性αaの数ｎを記憶している。
【０１０３】
さらに、記憶部２４−０は、データ決定情報ＤＴを記憶している。
【０１０４】
図６に示すように、データ決定情報ＤＴは、ｎ個の属性αaと、当該属性αaが取り得るＭa個の値Ｖα0 〜 ＶαMa-1と、当該値Ｖα0 〜 ＶαMa-1それぞれに対して付与された順番ＮＢとを対応付けて記憶している。なお、属性αaが取り得る値Ｖα0 〜 ＶαMa-1それぞれに順番ＮＢを付与する順序は任意でよい。
【０１０５】
つぎに、上述した構成を有する集計システムにおいて、集計装置１が端末２−０〜２−（Ｎ−１）から送信されてきた送信データＴ´（０）a〜Ｔ´（Ｎ−１）aそれぞれの撹乱後のクロス集計ｙを算出した場合、上述した一般的な技術よりも高速かつメモリ効率が高いことを、図７に示すフローチャートを参照して説明する。
【０１０６】
なお、端末２−０〜２−（Ｎ−１）とは互いに同じ動作を行うため、以下では、端末２−０の動作を例に挙げて説明する。
【０１０７】
図７に示すように、集計装置１は、それぞれの属性αaごとにあらかじめ定められた維持確率ρa（０≦ρa≦１）と属性αaとを、端末２−０〜２−（Ｎ−１）それぞれへ送信する（ステップＳ１１）。
【０１０８】
集計装置１から送信されてきた維持確率ρaと属性αaとを受信した際、端末２−０の確率変更部２２−０は、各属性αaに対して、実数の値を有する一様乱数ｒa（０≦ｒa≦１）と、整数の値を有する一様乱数ｚa（０≦ｚa≦Ｍa−１）とを生成する（ステップＳ１２）。
【０１０９】
続いて、確率変更部２２−０は、集計装置１から送信されてきた属性αaごとにあらかじめ定められた維持確率ρaと、該属性αaそれぞれに対して生成した実数値を有する一様乱数ｒaとを比較する（ステップＳ１３）。
【０１１０】
そして、端末２−０の送信データ決定部２３−０は、当該比較の結果に応じて、集計装置１へ送信する送信データＴ´（０）aを決定する（ステップＳ１４）。すると、通信部２１−０は、送信データ決定部２３−０が決定した送信データＴ´（０）aを集計装置１へ送信する。
【０１１１】
なお、確率変更部２２−０による比較の結果、一様乱数ｒaの値が維持確率ρa以下である場合（ｒa≦ ρa）、送信データ決定部２３−０は、ステップＳ１４において、該端末２−０の属性αaの正しいデータそのものであるデータＴ（０）aを、送信データＴ´（０）aとして決定する。
【０１１２】
また、確率変更部２２−０による比較の結果、一様乱数ｒaの値が維持確率ρaよりも大きい場合（ｒa＞ ρa）、送信データ決定部２３−０は、ステップＳ１４において、記憶部２４−０が記憶しているデータ決定情報ＤＴに基づいて、属性αaが取り得る値Ｖα0 〜 ＶαMa-1のうちからステップＳ１２にて生成した一様乱数ｚaと同じ値を有する順番ＮＢが付与された値（つまり、ｚa番目に存在する値）を、該端末２−０の属性αaの送信データＴ´（０）aとして決定する。
【０１１３】
また、ステップＳ１４において、送信データ決定部２３−０は、集計装置１から送信されてきた維持確率ρaが「０」である場合にも、記憶部２４−０が記憶しているデータ決定情報ＤＴに基づいて、属性αaが有する値Ｖα0 〜 ＶαMa-1のうちでｚa番の順番が付与された値を、該端末２−０の属性αaの送信データＴ´（０）aとして決定する。
【０１１４】
図６に示した例では、属性αaが性別である場合、該属性αaのうちの「男性」に０番の順番ＮＢが付与されていて、該属性αaのうちの要素「女性」に１番の順番ＮＢが付与されている。この場合、一様乱数ｚaの値が１であれば、送信データ決定部２３−０は、当該一様乱数ｚaと同じ値の順番ＮＢ（１番）が付与された値（女性）を送信データＴ´（０）aとして決定する。
【０１１５】
なお、維持確率ρaが小さくなるに伴って、送信データＴ´（０）aは一様にランダムな値に近づいていく。この場合、集計装置１が、端末２−０から送信されてきた送信データＴ´（０）aを用いて、該端末２−０が記憶している真のデータＴ（０）aを推定することは困難となる。
【０１１６】
なお、属性αaのｋ番目の値Ｖkaから当該属性αaのｌ番目の値Ｖlaへと変化する確率は、遷移確率行列Ａklaとして表すことが可能である。この場合、各属性αaに対する遷移確率行列Ａaは、各要素Ａaklが以下の式５で表されるような行列であり、各属性に対する維持確率ρaと、各属性αaが取り得る値の数「Ｍa」とから算出できる。なお、式５におけるδklは、「クロネッカーのデルタ」である。
【０１１７】
【数９】
2010108488.tif 000011
【０１１８】
そのため、維持確率ρaが小さくなるに伴って、式１に示した遷移確率行列Ａaの要素Ａpq（値が変化する確率）は、一様乱数における遷移確率の値「１／Ｍa」に単調に近づいていく。
【０１１９】
さらに、維持確率ρa＝０である場合、遷移確率行列Ａaが有する要素Ａpqは、一様乱数における遷移確率の値そのものである。
【０１２０】
例えば、属性αaが性別である場合、当該属性αaが取り得る値の数Ｍaは「２」（男性と女性との２つ）であるから、当該属性αaの遷移確率は「１／２」である。
【０１２１】
また、維持確率ρa＝１である場合、遷移確率行列Ａaが有する要素Ａpqは、真のデータＴ（０）a〜Ｔ（Ｎ−１）aそのものとなる。
【０１２２】
端末２−０〜２−（Ｎ−１）それぞれから送信データＴ´（０）a〜送信データＴ´（Ｎ−１）aが送信されてきた場合、集計装置１の集計部１３は、「撹乱後のクロス集計ｙ」を算出するために、まず、以下の式６で表される次数の横ベクトルである「撹乱後のクロス集計ｙ」を、遷移確率行列Ａaが有する全要素Ａpqに対して「０」を設定することにより、全要素Ａpqを初期化する（ステップＳ１５）。
【０１２３】
【数１０】
2010108488.tif 000012
【０１２４】
続いて、集計部１３は、端末２−０〜２−（Ｎ−１）それぞれから送信されてきた送信データＴ´（０）a〜Ｔ´（Ｎ−１）aについて、撹乱後のクロス集計ｙにおける以下の式７に示す順番が付与された要素に、１を加算していく（ステップＳ１６）。なお、式７におけるＩaは、送信データＴ´（０）a〜Ｔ´（Ｎ−１）aに付与されている順番ＮＢを返すための関数である。
【０１２５】
【数１１】
2010108488.tif 000013
【０１２６】
該加算により、集計部１３は、撹乱後のクロス集計ｙを算出する。
【０１２７】
すると、要素算出部１２は、レコード全体に対する遷移確率行列Ａの生成手法に従って、以下の式８で表されるようなｐ行ｑ列の要素Ａpqそれぞれを有する、式６に示した次数の正方行列である、レコード全体に対する遷移確率行列Ａを生成する（ステップＳ１７）。なお、集計装置１が生成した遷移確率行列Ａの行の数ｐおよび列の数ｑは、式２に示した値である。
【０１２８】
【数１２】
2010108488.tif 000014
【０１２９】
非特許文献２に開示された一般的な技術においては、遷移確率行列の次数は、以下の式９で表される。
【０１３０】
【数１３】
2010108488.tif 000015
【０１３１】
なお、式９に示した［log2Ma］は、log 2 Ma 以上の最小の整数を表す。
【０１３２】
一方、本発明の集計装置１においては、遷移確率行列Ａの次数は式６に示した次数である。
【０１３３】
このように、本発明の集計装置１が撹乱後のクロス集計ｙの算出に用いる式６に示した次数と、一般的な技術にてクロス集計結果の算出に用いる式９に示した次数との間の差異により、集計装置１では、レコード全体に対する遷移確率行列Ａに費やすメモリ使用量を、例えば、非特許文献２に開示されたような一般的な技術に比べて小さく抑えることができる。
【０１３４】
その後、推定部１４は、要素算出部１２が算出した「遷移確率行列Ａ」と集計部１３が算出した「撹乱後のクロス集計ｙ」とを用いて推定クロス集計ｘi+1を算出し、該推定クロス集計ｘi+1を出力する（ステップＳ１８）。なお、推定クロス集計ｘi+1とは、真のクロス集計ｘの推定値のことを指す。
【０１３５】
ステップＳ１８において、推定部１４は、はじめ、ｉ＝０、ｘ0＝ｙを初期値として、式６に示した次数を有する横ベクトルとして表される（ｉ＋１）番目の「推定クロス集計ｘi+1」を、ｘi+1＝ｘi・（（ｙ／（ｘiＡ））Ａt）として算出していく。
【０１３６】
ここで、「・」は、ベクトルの内積を示す演算記号である。また、「／」は、ベクトルの成分ごとの除算を示す演算記号である。また、Ａtは、行列Ａの転置行列を表す。
【０１３７】
そして、推定部１４は、ステップＳ１８における推定クロス集計ｘi+1の算出を実行していて｜ｘi+1−ｘi｜L1 ≦εN となった場合、ｉに対する推定クロス集計ｘi+1を、真のクロス集計ｘの推定値として出力する。
【０１３８】
ここで、｜ｘi+1−ｘi｜L1は、（ｘi+1−ｘi）のＬ１ノルムであり、行列の成分ごとの差の絶対値の総和を示す演算記号である。また、εはあらかじめ設定された実数である。
【０１３９】
なお、ステップＳ１８に示した処理は、ある結果（例えば、撹乱後のクロス集計ｙ）が得られた際に、当該結果を反映した下での事後確率を求めるための「ベイズの定理」に基づいている。
【０１４０】
ベイズの定理を用いた場合、あるレコードの撹乱後のクロス値Ｑがｑであること（この例では、撹乱後のクロス集計ｙ）が既知である場合に、該レコードの真のクロス値Ｐがｐである事後確率Ｐｒ（Ｐ＝ｐ｜Ｑ＝ｑ）は、式６に示した値をＭとして、真のクロス集計をｘとした場合、以下の式１０で表される。
【０１４１】
【数１４】
2010108488.tif 000016
【０１４２】
さらに、クロス値Ｑがｑである事後確率Ｐｒ（Ｑ＝ｑ）については、以下の式１１が成立する。
【０１４３】
【数１５】
2010108488.tif 000017
【０１４４】
そのため、式１１に示した関係を用いると、真のクロス値Pがｐである事後確率Ｐｒ（Ｐ＝ｐ）は、以下の式１２で表すことができる。
【０１４５】
【数１６】
2010108488.tif 000018
【０１４６】
ここで、式１０に示した関係式と、式１２に示した関係式とを用いると、真のクロス集計ｘpは、以下の式１３で表すことができる。
【０１４７】
【数１７】
2010108488.tif 000019
【０１４８】
以上より、ｘ＝ｘ・（（ｙ／（ｘＡ））Ａt）という方程式を得ることができる。
【０１４９】
ステップＳ１８において（ｉ＋１）番目の「推定クロス集計ｘi+1」を算出する際、集計装置１は、上述した方程式ｘ＝ｘ・（（ｙ／（ｘＡ））Ａt）を用いている。
【０１５０】
なお、推定部１４は、ステップＳ１８においてレコード全体に対する遷移確率行列Ａについての乗算を実行する。しかしながら、当該乗算を行うときの計算量は、該遷移確率行列Ａが有する次数の２乗に比例して増大し、本発明の集計装置１が実行する演算のなかで最も多くの計算量を伴う演算である。しかしながら、当該集計装置１の要素算出部１２は、レコード全体に対する遷移確率行列Ａを算出し、例えば、非特許文献２に開示されたような一般的な技術よりも、属性αaが取り得る値の数Ｍaに対して遷移確率行列Ａが有する次数が非常に小さなものとなる。
【０１５１】
そのため、集計装置１においては、真のクロス集計ｘの推定値である推定クロス集計ｘi+1の算出に要する時間が一般的な技術よりも非常に短くできるとともに、該推定クロス集計ｘi+1を算出するときに集計装置１が使用するメモリ使用量についても小さなものとできる。
（実施形態２）
つぎに、実施形態２の集計装置１について説明する。
【０１５２】
実施形態２の集計装置１の構成および端末２−０〜２−（Ｎ−１）の構成それぞれは、実施形態１における集計装置１の構成および端末２−０〜２−（Ｎ−１）の構成と同じである。
【０１５３】
ただし、実施形態２の集計装置１は、個別に指定したクロス値に対する推定クロス集計を算出する点で、実施形態１の集計装置１と異なっている。なお、以下では、複数の属性に対する値を１つの値とみなした値であるクロス値として、ベクトルｖを指定する場合を例に挙げて説明する。
【０１５４】
以下に、上述した集計システムにおいて、実施形態２の集計装置１が推定クロス集計ｘi+1を算出する動作を、図８に示すフローチャートを参照して説明する。
【０１５５】
図８に示すように、まず、集計装置１は、複数の属性に対する値を１つの値とみなしたクロス値として、ベクトルｖを指定する入力を、入力部（図示せず）により利用者から受付ける（ステップＳ２１）。
【０１５６】
なお、当該ベクトルｖに含まれている各成分ｖaは、推定クロス集計ｘi+1の算出を行う際の属性αaそれぞれに対する値（例えば、図４に示した「１０代」と「男性」）の指定である。
【０１５７】
すると、集計装置１は、属性αaごと（例えば、「年代」や「性別」）にあらかじめ定められた維持確率ρa（０≦(a≦１）と属性αaとを、端末２−０〜２−（Ｎ−１）それぞれへ送信する（ステップＳ２２）。
【０１５８】
集計装置１から維持確率ρaと属性αaとが送信されてきた場合、端末２−０の確率変更部２２−０は、属性αaそれぞれに対して、実数の値を有する一様乱数ｒa（０≦ｒa≦１）と、整数の値を有する一様乱数ｚa（０≦ｚa≦Ｍa−１）とを生成する（ステップＳ２３）。
【０１５９】
続いて、確率変更部２２−０は、属性αaごと（例えば、「年代」や「性別」）に、集計装置１から送信されてきた維持確率ρaと、該属性αaに対して生成した実数値を有する一様乱数ｒaとを比較する（ステップＳ２４）。
【０１６０】
そして、送信データ決定部２３−０は、確率変更部２２−０による比較の結果に応じて、集計装置１へ送信する送信データＴ´（０）aを決定する（ステップＳ２５）。
【０１６１】
ステップＳ２５において、送信データ決定部２３−０は、比較の結果、一様乱数ｒaの値が維持確率ρa以下である場合（ｒa≦ ρa）、当該端末２−０の属性αaの正しいデータそのものであるデータＴ（０）aを、送信データＴ´（０）aとして決定する。
【０１６２】
また、ステップＳ２５において、送信データ決定部２３−０は、比較の結果、一様乱数ｒaの値が維持確率ρaよりも大きい場合（ｒa＞ ρa）、または、維持確率ρaが「０」である場合、記憶部２４−０が記憶しているデータ決定情報ＤＴに基づいて、属性αaが取り得る値Ｖα0 〜 ＶαMa-1のうちからステップＳ２３にて生成した一様乱数ｚaと同じ値を有する順番ＮＢが付与された値（つまり、ｚa番目に存在する値）を、該端末２−０の属性αaの送信データＴ´（０）aとして集計装置１へ送信する。
【０１６３】
このとき、維持確率ρaが小さくなるに伴って送信データＴ´（０）aは一様にランダムな値に近づく。そのため、集計装置１が、端末２−０から送信されてきた送信データＴ´（０）aを用いて、該端末２−０が記憶している真のデータＴ（０）aを推定することは困難となる。
【０１６４】
その後、通信部２１−０は、ステップＳ２５にて送信データ決定部２３−０が決定した送信データＴ´（０）aを集計装置１へ送信する。
【０１６５】
なお、端末２−１〜２−（Ｎ−１）それぞれも、それぞれの比較の結果に応じた送信データＴ´（１）a〜Ｔ´（Ｎ−１）aそれぞれを集計装置１へ送信する。
【０１６６】
端末２−０〜２−（Ｎ−１）から送信データＴ´（０）a〜Ｔ´（Ｎ−１）aが送信されてきた場合、集計装置１の集計部１３は、「撹乱後のクロス集計ｙ」を算出するための処理を実行する。
【０１６７】
集計部１３は、まず、式６に示した次数の横ベクトルである撹乱後のクロス集計ｙを、遷移確率行列Ａaが有する全要素に対して０を設定することにより、全要素を初期化する（ステップＳ２６）。
【０１６８】
続いて、集計部１３は、端末２−０〜２−（Ｎ−１）それぞれに対して、撹乱後のクロス集計ｙにおける式３に示した順番の要素に、「１」を加算していく（ステップＳ２７）。該加算により、集計部１３は、撹乱後のクロス集計ｙを算出する。
【０１６９】
さらに、集計装置１の推定部１４は、各属性αaに対する遷移確率行列Ａaの逆行列（Ａa）-1を算出する（ステップＳ２８）。
【０１７０】
逆行列（Ａa）-1を算出した場合、さらに、推定部１４は、各属性αaに対する値としてベクトルｖに含まれている成分ｖaを有するレコードの数、つまり、クロス値として指定されたベクトルｖに対する以下の式１４に示すクロス集計を算出して出力する（ステップＳ２９）。
【０１７１】
【数１８】
2010108488.tif 000020
【０１７２】
真のクロス集計ｘが与えられた場合、撹乱後のクロス集計ｙの期待値のベクトルＥ（Ｙ）は、Ｅ（Ｙ）＝ｘＡで表すことができる。そのため、｜Ａ｜≠０である場合、Ｅ（ＹＡ-1）＝Ｅ（Ｙ）Ａ-1＝ｘが成立する。すなわち、ｙＡ-1は真のクロス集計ｘの近似であることが期待できる。
【０１７３】
ここで、クロネッカー積を用いると、式１に示した各要素を有するようなレコード全体に対する遷移確率行列Ａは、以下の式１５で表すことが可能である。
【０１７４】
【数１９】
2010108488.tif 000021
【０１７５】
式１５に示した関係を用いると、クロネッカー積の性質から、遷移確率行列Ａの逆行列Ａ-1は、以下の式１６で表すことができる。
【０１７６】
【数２０】
2010108488.tif 000022
【０１７７】
このことから、遷移確率行列Ａと同様に、逆行列Ａ-1が有する各成分は、以下の式１７で表すことができる。
【０１７８】
【数２１】
2010108488.tif 000023
【０１７９】
そのため、真のクロス集計ｘは、ｘ＝ｙＡ-1という関係に基づいて推定することが可能である。
【０１８０】
また、逆行列Ａ-1のｐ列目の各成分によって構成される縦ベクトルを縦ベクトルＡp-1とした場合、（Ａp-1）q ＝ Ａpq-1が成立する。
【０１８１】
そのため、真のクロス集計ｘpは、逆行列Ａ-1のｐ列目以外の成分を用いることなく、当該逆行列Ａ-1のｐ列目の各成分を用いて、以下の式１８として直接算出することが可能である。
【０１８２】
【数２２】
2010108488.tif 000024
【０１８３】
ここで、ｐとして、クロス値であるベクトルｖに対応する以下の式１９に示す数を代入する。
【０１８４】
【数２３】
2010108488.tif 000025
【０１８５】
すると、Ｉa（ｖa）＝ｄpaの関係が導出できる。そのため、真のクロス集計ｘpは、式１４に示した値により算出することができる。
【０１８６】
実施形態２において推定部１４が真のクロス集計ｘの推定値を算出する場合、推定クロス集計の算出に要する所要時間、および、該クロス集計を算出する際に使用するメモリ使用量ともに、遷移確率行列Ａの次数に対して線形となる。
【０１８７】
なお、最終的には、各属性αaに対する値ｖaをそれぞれ有するようなレコードの数は、（ｉ＋１）番目の推定クロス集計ｘi+1における式１９に示した順番が付与された要素が表している。
【０１８８】
以上説明したように、実施形態１及び実施形態２においては、レコード全体に対する遷移確率行列Ａの次数として、各属性αaが取り得る値の数Ｍaの２進表現よりも値が小さな各属性αaが取り得る値の個数Ｍaを用いて、推定クロス集計を算出する。これにより、個々のデータを秘匿しつつ推定クロス集計を算出する際に、集計装置１が使用するメモリ使用量を抑えることができる。
【０１８９】
さらに、メモリ使用量を抑えることにより、推定クロス集計の集計処理中に最も多くの計算量を伴うボトルネックとなる、レコード全体に対する遷移確率行列Ａに対する演算もより短い時間で行うことが可能となる。
（実施形態３）
上述した実施形態１において、レコード全体に対する遷移確率行列Ａが有する次数Ｍは、例えば非特許文献２に開示されたような一般的な技術と比べ、属性αaが取り得る値の個数Ｍaに対して非常に小さなものとすることができる。
【０１９０】
そのため、推定クロス集計の算出に要する時間を、一般的な技術よりも非常に短くすることができる。また、それとともに、推定クロス集計を算出するときに集計装置１が使用するメモリ使用量も小さなものとすることができる。なお、以降、レコード全体に対する遷移確率行列Ａを単に、遷移確率行列Ａという。
【０１９１】
ここで、上述した式２に示したように、遷移確率行列Ａの行の数ｐ及び列の数ｑはＭ個となる。そのため、遷移確率行列Ａは、Ｍ次の正方行列である。一般的に、Ｍ次の正方行列をメモリ上に展開するときのメモリ使用量は、「正方行列の要素のサイズ×Ｍ2」となる。また、遷移確率行列Ａが有する次数Ｍは、上述した式６に示したように、属性αaの取り得る値の個数Ｍaを用いて表される。
【０１９２】
従って、属性αaの取り得る値の個数Ｍaが多くなると、遷移確率行列Ａをメモリ上に展開したときのメモリ使用量は、飛躍的に増加してしまう。
【０１９３】
そこで、本実施形態では、遷移確率行列Ａを生成することなく、推定クロス集計を算出する場合について説明する。
【０１９４】
なお、本実施形態における集計システムの構成は、上述した実施形態１における構成と同様なので、ここでは、構成の説明は省略する。
【０１９５】
以下に、本実施形態において推定クロス集計を算出する場合の動作を説明する。
【０１９６】
まず、遷移確率行列Ａは、クロネッカー積を用いると、上述した式１５で表すことが可能である。
【０１９７】
そして、クロネッカー積を用いて表された遷移確率行列Ａを分割したＢjを設定する。以下の式２０にＢjを示す。なお、式２０においてＪは分割数であり、ｍ-1＝０とする。
【０１９８】
【数２４】
2010108488.tif 000026
【０１９９】
そして、上記の式２０に示すようなＢjをメモリ上に展開したとき、各Ｂjのサイズの総和が、予め決められ、推定クロス集計の算出用に割り当て可能なメモリサイズに収まるようにする。各Ｂjをメモリ上に展開したときのサイズの総和を以下の式２１に示す。
【０２００】
【数２５】
2010108488.tif 000027
【０２０１】
ここで、具体的な分割の方法としては、ａの値が属性αaの数ｎ未満である場合に（ａ＜ｎ）、Ｂa＝Ａaとする方法がある。以降、この方法のことを分割方法１という。つまり、分割方法１では、属性αa毎に複数の遷移確率行列を生成することとなる。以降、属性αa毎の複数の遷移確率行列のそれぞれを属性別遷移確率行列という。
【０２０２】
分割方法１において要素算出部１２は、要素Ａpqを属性毎に算出する。そして、要素算出部１２は、属性毎に算出された要素Ａpqから、複数の属性別遷移確率行列を生成する。
【０２０３】
そして、推定部１４は、要素算出部１２が算出した複数の属性別遷移確率行列と、集計部１３が算出した撹乱後のクロス集計ｙとに基づき、上述した実施形態１におけるステップＳ１８と同様の処理を実行する。これにより、推定クロス集計が算出される。
【０２０４】
また、上述した分割方法１以外にも例えば、属性別遷移確率行列をメモリ上に展開したときのサイズに基づき、少なくとも１つの属性別遷移確率行列を含む遷移確率行列である分割遷移確率行列を複数生成する方法がある。以降、この方法のことを分割方法２という。
【０２０５】
以下に、本実施形態の分割方法２において分割遷移確率行列を生成する場合の動作について説明する。なお、以下の説明においては、予め決められ、推定クロス集計の算出用に割り当て可能なメモリサイズをＬと表記し、行列Ｘをメモリ上に展開したときのサイズをｓｉｚｅＸと表記する。
【０２０６】
図９は、実施形態３の集計システムにおいて、分割遷移確率行列を生成するときの動作シーケンスを示す図である。
【０２０７】
まず、要素算出部１２は、遷移確率行列Ａと同じクロネッカー積で表される行列Ｂを定義する。そして、ａの値が属性αaの数ｎ未満である場合に（ａ＜ｎ）、行列Ｂを構成する各Ｂjの初期値を以下の式２２に示すように設定する（ステップＳ３１）。つまり、この段階では、各Ｂjは、上述した属性別遷移確率行列となる。
【０２０８】
【数２６】
2010108488.tif 000028
【０２０９】
次に、要素算出部１２は、以下の式２３に示すように各Ｂjのサイズの総和Ｓiを計算する（ステップＳ３２）。なお、式２３においてｉは、０から始まる反復のカウンタである。
【０２１０】
【数２７】
2010108488.tif 000029
【０２１１】
次に、要素算出部１２は、以下の式２４に示す範囲において、以下の式２５に示すような、２つのＢjをクロネッカー積に置き換えた場合のサイズの増加量を算出する（ステップＳ３３）。以降、２つのＢjをクロネッカー積に置き換えた場合のサイズの増加量のことを単に増加量という。なお、ここでは、式２４に示す範囲のｊについて、式２５に示すような計算が行われるため、複数の増加量が算出される。また、算出された複数の増加量のそれぞれは、クロネッカー積のそれぞれと対応付けられる。
【０２１２】
【数２８】
2010108488.tif 000030
【０２１３】
【数２９】
2010108488.tif 000031
【０２１４】
次に、要素算出部１２は、算出された複数の増加量のうち、最も値の小さな増加量である最小増加量が、ＬとＳiとの差よりも大きいかどうかを判定する（ステップＳ３４）。
【０２１５】
ステップＳ３４における判定の結果、最小増加量がＬとＳiとの差よりも大きな場合、要素算出部１２は、行列Ｂを構成する各Ｂjのそれぞれを分割遷移確率行列とする。
【０２１６】
そして、要素算出部１２は、分割遷移確率行列のそれぞれに含まれる属性別遷移確率行列の要素Ａpqを算出することにより、複数の分割遷移確率行列を生成する（ステップＳ３５）。そして、処理が終了する。
【０２１７】
一方、ステップＳ３４における判定の結果、最小増加量がＬとＳiとの差以下である場合には、要素算出部１２は、当該最小増加量に対応するクロネッカー積を算出する（ステップＳ３６）。
【０２１８】
そして、要素算出部１２は、以下の式２６に示す範囲において、最小増加量が算出されたｊの値に応じ、以下の式２７に示すように、行列Ｂを各Ｂj'で構成される行列として再定義する（ステップＳ３７）。
【０２１９】
【数３０】
2010108488.tif 000032
【０２２０】
【数３１】
2010108488.tif 000033
【０２２１】
そして、ステップＳ３２の動作へ遷移し、要素算出部１２は、反復のカウンタｉを１つインクリメントするとともにｊ'をｊとして、ステップＳ３７において再定義された行列Ｂを構成する各Ｂjのサイズの総和を計算する。
【０２２２】
上述したステップＳ３２〜Ｓ３７の動作は、最小増加量がＬとＳiとの差よりも大きくなるまで繰り返される。最小増加量がＬとＳiとの差よりも大きくなると、上述したステップＳ３５で説明したように、複数の分割遷移確率行列が生成される。
【０２２３】
そして、推定部１４は、要素算出部１２にて生成された複数の分割遷移確率行列と、集計部１３が算出した撹乱後のクロス集計ｙとに基づき、上述した実施形態１におけるステップＳ１８と同様の処理を実行する。これにより、推定クロス集計が算出される。
【０２２４】
このように本実施形態の分割方法１においては、属性毎に要素Ａpqが算出され、その属性毎に算出された要素Ａpqをそれぞれ有する複数の属性別遷移確率行列が生成される。そして、クロス集計と、複数の属性別遷移確率行列とに基づいて、推定クロス推計が算出される。
【０２２５】
そのため、推定クロス集計を算出するときに集計装置１が使用するメモリ使用量を上述した実施形態１よりもさらに小さなものとすることができる。
【０２２６】
例えば、属性数を５とし、各属性の取り得る値の個数を１０とした場合、Ｍは１０となる。この場合、要素Ａpqのサイズを８Ｂ（バイト）とすると、１つの属性別遷移確率行列をメモリ上に展開したときのサイズは、８Ｂ×１０2＝８００Ｂとなる。そして、属性数が５であるため、全ての属性別遷移確率行列をメモリ上に展開したときのサイズは、４ＫＢ（８００Ｂ×５）と非常に少なく済む。
【０２２７】
なお、本実施形態の分割方法１を用いた場合、複数の属性別遷移確率行列に基づいて推定クロス集計が算出される。そのため、上述した実施形態１のステップＳ１８における乗算の回数が実施形態１よりも増加する。しかし、例えば高速なメモリ上に遷移確率行列Ａを展開しきれず、低速なメモリへのメモリ転送が発生する場合等と比較すると、乗算の回数が数倍程度増えても、本実施形態で示したように遷移確率行列Ａを分割した方が処理速度は速くなる。
【０２２８】
また、本実施形態の分割方法２においては、属性別遷移確率行列のそれぞれがメモリ上に展開されるときのサイズに基づき、それぞれが少なくとも１つの属性別遷移確率行列を含む複数の分割遷移確率行列が生成される。そして、クロス集計と、複数の分割遷移確率行列とに基づいて、推定クロス推計が算出される。
【０２２９】
つまり、分割方法２における遷移確率行列Ａの分割数は、分割方法１における遷移確率行列Ａの分割数よりも少ない。そのため、上述した実施形態１のステップＳ１８における乗算の回数の増加を分割方法１よりも少なくすることができ、処理速度をさらに速くすることができる。
【０２３０】
なお、本発明においては、集計処理装置１内の処理は上述の専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを集計処理装置１にて読取可能な記録媒体に記録し、この記録媒体に記録されたプログラムを集計処理装置１に読み込ませ、実行するものであってもよい。集計処理装置１にて読取可能な記録媒体とは、フロッピーディスク（登録商標）、光磁気ディスク、ＤＶＤ、ＣＤなどの移設可能な記録媒体の他、集計処理装置１に内蔵されたＨＤＤ等を指す。この記録媒体に記録されたプログラムは、例えば、集計処理装置１が有する要素算出部１２、集計部１３および推定部１４にて読み込まれ、要素算出部１２、集計部１３および推定部１４の制御によって、上述したものと同様の処理が行われる。
【０２３１】
ここで、集計処理装置１が有する要素算出部１２、集計部１３および推定部１４は、プログラムが記録された記録媒体から読み込まれたプログラムを実行するコンピュータとして動作するものである。
【０２３２】
なお、上述したプログラムは、情報提供者端末２−０〜２−（Ｎ−１）についても、同様に適用可能である。
【０２３３】
以上、実施形態１〜３を参照して本発明を説明したが、本発明は上記実施形態１〜３に限定されるものではない。本発明の構成や詳細には、本発明の要旨を逸脱しない範囲で当業者が理解し得る各種の変形が可能である。
【符号の説明】
【０２３４】
１  集計処理装置
１１  通信部
１２  要素算出部
１３  集計部
１４  推定部
１５  記憶部
２−０〜２−（Ｎ−１）  情報提供者端末
２１−０  通信部
２２−０  確率変更部
２３−０  送信データ決定部
２４−０  記憶部
【図１】
2010108488.tif 000038
【図２】
2010108488.tif 000039
【図３】
2010108488.tif 000040
【図４】
2010108488.tif 000041
【図５】
2010108488.tif 000042
【図６】
2010108488.tif 000043
【図７】
2010108488.tif 000044
【図８】
2010108488.tif 000045
【図９】
2010108488.tif 000046
【図１０】
2010108488.tif 000047
【図１１】
2010108488.tif 000048