(57)【要約】【課題】適切な分析精度を出すことができるように数値属性値を含むデータの匿名化を可能にする。【解決手段】本匿名化データ生成方法は、（Ａ）データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、（Ｂ）上記グループに属するデータブロックの数値属性値を、上記グループについての数値属性値で置換する処理を含む。【選択図】図３
2015090617.tif 000002
【特許請求の範囲】
【請求項１】
データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、前記複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、
前記グループに属するデータブロックの数値属性値を、前記グループについての数値属性値で置換する
処理を含み、コンピュータにより実行される匿名化データ生成方法。
【請求項２】
前記グループに属するデータブロックの機密属性値を削除する
処理をさらに含む請求項１記載の匿名化データ生成方法。
【請求項３】
前記所定の条件が、機密属性値の種類数の下限値を含み、
前記抽出する処理は、
前記グループ化未了の第１のデータブロックを含み且つ前記１つのメッシュ要素に含まれるデータブロックの集合における機密属性値の種類が、前記機密属性値の種類の下限値以上となっているか判断する
処理を含む請求項１又は２記載の匿名化データ生成方法。
【請求項４】
前記抽出する処理は、
前記グループ化未了の第１のデータブロックを含み且つ前記１つのメッシュ要素に含まれるデータブロックの第２の集合についての機密属性値の度数分布が、前記所定の条件を満たすか判断し、
前記データブロックの第２の集合についての機密属性値の度数分布が前記所定の条件を満たさない場合には、前記所定の条件を満たすように前記データブロックの第２の集合から第２のデータブロックを除外することでデータブロックのグループを生成する
処理を含む請求項１乃至３のいずれか１つ記載の匿名化データ生成方法。
【請求項５】
前記抽出する処理は、
前記データブロックのグループから、前記機密属性値の度数分布が前記所定の条件を満たす上で必須となるデータブロック以外の第３のデータブロックを抽出する処理
を含み、
データブロックの他のグループを抽出する処理において、前記第３のデータブロックが他の種類のメッシュにおけるメッシュ要素において抽出される
請求項１乃至４のいずれか１つ記載の匿名化データ生成方法。
【請求項６】
メッシュ要素の境界を共有しないように、前記複数種類のメッシュを生成する
処理をさらに含む請求項１乃至５のいずれか１つ記載の匿名化データ生成方法。
【請求項７】
これまでに生成されたメッシュの境界のうち最も近い境界との距離が最大となり、且つ前記これまでに生成されたメッシュの格子点との距離が最大となる基準点を選択し、
選択された前記基準点及び前記メッシュ要素のサイズに基づきメッシュを生成する
処理をさらに含む請求項１乃至５のいずれか１つ記載の匿名化データ生成方法。
【請求項８】
データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、前記複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、
前記グループに属するデータブロックの数値属性値を、前記グループについての数値属性値で置換する
処理を、コンピュータに実行させるための匿名化データ生成プログラム。
【請求項９】
データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、前記複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出するグループ化処理部と、
前記グループに属するデータブロックの数値属性値を、前記グループについての数値属性値で置換する匿名化処理部と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、情報の匿名化技術に関する。
【背景技術】
【０００２】
複数の情報提供者から収集した、数値属性値を含むレコード群を、各レコードの情報提供者識別子（以下、単にＩＤと略す）を秘密にして、他者に開示又は提供したい場合がある。このとき、ＩＤを削除して開示又は提供しても、特徴ある数値属性値を有するレコードについては他者が情報提供者を推定できてしまう場合がある。
【０００３】
例えば、個人の位置データの収集者が、情報提供者が分からない形で、分析者に位置データを提供することを考える。ここで、収集者としては位置データについてのサービス提供者、分析者としてはクラウドサービス提供者又はデータ二次利用者（例えば人口密度調査会社など）などが考えられる。
【０００４】
ここで、収集者が収集した位置データが図１に示すものであるとする。図１の例では、各レコードには、行番号と、ＩＤと、Ｘ（緯度）と、Ｙ（経度）とが含まれる。ここでは、各レコードは、Ａ、Ｂ及びＣの３人のいずれかの位置データを表しており、全部で７レコードある。すなわち、同じＩＤのレコードが複数回出現する場合がある。なお、ＩＤは、個人のユーザＩＤである場合もあれば、測定機器のＩＤである場合もある。また、所属する組織のＩＤである場合もある。
【０００５】
図１に示されるデータを地図上にプロットすると、例えば図２に示すようになる。分析者は、図１及び図２のようなデータが得られれば、分析に役立てることができる。例えば、Ａ宅及びＢ宅付近に人が集まっていることが分かる。
【０００６】
しかしながら、例えば、収集者が情報提供者との間で、匿名化しない限り他者にデータを提供しないという契約を結んでいる状況が考えられる。情報提供者は、特定の時期にどこにいたかを収集者以外に知られたくないなどの理由で、匿名化を希望する場合がある。
【０００７】
一方、分析者はＩＤ等の情報提供者の情報を利用しない場合もある。位置データの提供者が誰かを知らなくても人口密度調査のような分析はできるためである。
【０００８】
このような場合、収集者は図１のデータに対して匿名化を行って、情報提供者の推定を困難にすれば良い。
【０００９】
収集者による単純な匿名化方式として、ＩＤを削除する方式がある。図１からＩＤを削除したデータを分析者が見ても、どのレコードが誰のデータなのかそのままでは分からない。しかし、位置データから情報提供者を推定可能なレコードがあるという問題がある。
【００１０】
図１からＩＤを削除したデータを図２のように地図上にプロットすると、例えば第１レコードの位置データ（Ｘ，Ｙ）＝（６，２）はＡ宅内であることが分かってしまう。すなわち、ＩＤが削除されたデータしか見ることのできない分析者であっても、第１レコードの情報提供者がＡであることが推定できてしまい、十分に匿名化されているとは言い難い。同様に、第７レコード以外は匿名化が不十分である。
【００１１】
従来技術として、事前に定められた、重なりのない複数の数値範囲をグループとして把握し、各グループ内のレコード群をそれらの統計値に変換する方法がある。
【００１２】
この従来技術では、緯度及び経度に基づいて地域をメッシングし、各メッシュ要素内のレコード群についての統計値を計算し、それを開示又は提供する。
【００１３】
統計値としては、例えば「メッシュ要素Ｍ１には３レコード」というように、メッシュ要素毎のレコード数が用いられる。もしくは、各レコードのＩＤを削除し、位置をメッシュ要素の中心点に変換しても良い。
【００１４】
例えば、図１の各レコードを一辺「５」のメッシュ要素によりグループ分けし、変換する場合を考える。その場合、例えば（Ｘ，Ｙ）＝（[5, 10), [0, 5)）などが１つのメッシュ要素、すなわちグループとなる。このメッシュ要素を仮にＭ１０と名付けると、図１では第１レコードのみがＭ１０に分類される。よって、「メッシュＭ１０には１レコードあった」ことが開示される、あるいは第１レコードが（Ｘ，Ｙ）＝（7.5, 2.5）（Ｍ１０の中心点）に変換され開示されることになる。
【００１５】
この従来技術では、メッシュサイズが十分大きければ匿名性に問題は生じないが、メッシュサイズを小さくすると匿名性が脅かされるという問題がある。例えば、メッシュ要素Ｍ１０が、もしＡ宅の敷地内に包含された場合（例えば、Ａ宅の敷地が（Ｘ，Ｙ）＝（[2, 10], [0, 6]）の場合など）、メッシュ要素Ｍ１０に分類されたレコードの情報提供者はＡだと推定できてしまう。メッシュサイズを小さくするほど、特定のＩＤしか存在し得ないような地域にメッシュ要素が包含される可能性が高くなる。
【００１６】
一方、メッシュサイズを大きくするほど、位置の一般化度合いが大きくなり、分析者による分析の精度に大きな悪影響を与えるという問題がある。例えば、統計調査では一辺約１ｋｍのメッシュ要素が使われることがあるが、その結果だけを使う限り１ｋｍ単位より詳細な地域に関する分析結果を出すことは一般的にはできない。
【００１７】
このように、この従来技術は、匿名性を担保するためにメッシュサイズを十分に大きくしなければならず、分析の精度に大きな悪影響を与えるという問題がある。
【００１８】
また、グループを生成する別の従来技術として、事前に決めた値ｄ及びｋに対し、大きさｄ未満の範囲内に、ｋ個以上のレコードが含まれるように、且つ別の範囲と重ならないように範囲の位置を調整し、その範囲に基づきグループ化する技術がある。
【００１９】
この従来技術は対象データとして互いに異なるＩＤを有するレコード群を前提にしており、その場合は適切な匿名性が担保されるが、図１のように同じＩＤのレコードが複数存在し得るデータに対しては十分な匿名性を担保できないという問題がある。
【００２０】
例えば、この従来技術の一部を適用し、図１の各レコードを一辺「５」未満の矩形（ｄ＝(5, 5)）で、３個以上（ｋ＝３）のレコードが含まれるようグループ分けする場合を考える。この場合、例えばレコード｛１，２，３｝を含む矩形Ｒ４３:（Ｘ，Ｙ）＝（[2, 6], [2, 4]）と、レコード｛４，５，６｝を含む矩形Ｒ４９:（Ｘ，Ｙ）＝（[2, 6], [8, 10]）の２つのグループができる。しかし、上でも述べた例と同じように、特定のＩＤしか存在し得ないような地域に矩形が包含される可能性がある。例えば矩形Ｒ４３がＡ宅の敷地内に包含された場合には、矩形Ｒ４３に分類されたレコード｛１，２，３｝の情報提供者がＡだと推定できてしまう。
【００２１】
一般的に、図１のように同じＩＤのレコードが複数存在するレコード群をも取り扱うことができる手法の方が適用範囲が広くて良い。例えば、組織が情報提供者の場合は特に、複数の測定機器のデータに同じＩＤ（すなわち組織ＩＤ）が記録される場合もある。また、ＩＤが同じ複数のレコードの存在を許すことで多くのレコードを一度に分析できるようになり、分析精度の向上が望める。しかしながら、この従来技術は、特殊な対象データでしか匿名性を担保できず、適用できる場面が少ないという問題がある。
【００２２】
さらに、グループ化する別の従来技術として、ＩＤのような機密属性値の種類が各グループ内でｌ種類以上ある（すなわちｌ−多様性を満たす）ようにする技術がある。この従来技術はグループを事前に決めた大きさ未満の範囲内にすることが難しいという問題がある。事前に決めた大きさ未満の範囲内にできないと、分析の精度に大きな悪影響を与えるという問題がある。
【先行技術文献】
【非特許文献】
【００２３】
【非特許文献１】O. Abul, F. Bonchi, and M. Nanni. Never Walk Alone: Uncertainty for Anonymity in Moving Objects Databases. In Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, pp.376-385 (2008).
【非特許文献２】A. Machanavajjhala, J. Gehrke, D. Kifer, M. Venkitasubramaniam. l-Diversity: Privacy Beyond k-Anonymity. ACM Transactions on Knowledge Discovery from Data, Vol. 1, Issue 1, Article No. 3, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００２４】
従って、本技術の目的は、一側面によれば、適切な分析精度を出すことができるように数値属性値を含むデータの匿名化を可能にするための技術を提供することである。
【課題を解決するための手段】
【００２５】
本発明に係る匿名化データ生成方法は、（Ａ）データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、（Ｂ）上記グループに属するデータブロックの数値属性値を、上記グループについての数値属性値で置換する処理を含む。
【発明の効果】
【００２６】
一側面によれば、適切な分析精度を出すことができるように数値属性値を含むデータを匿名化できるようになる。
【図面の簡単な説明】
【００２７】
【図１】図１は、データの一例を示す図である。
【図２】図２は、データと他のデータとの重ね合わせの一例を示す図である。
【図３】図３は、本実施の形態に係る情報処理装置の構成例を示す図である。
【図４】図４は、第１データ格納部に格納されるデータの一例を示す図である。
【図５】図５は、本実施の形態における処理フローを示す図である。
【図６】図６は、メッシュ生成処理の処理フローを示す図である。
【図７】図７は、２種類のメッシュが生成された状態を示す図である。
【図８】図８は、メッシュの基準点のばらつきを表す図である。
【図９】図９は、複数種類のメッシュのメッシュ要素の重なりを示す図である。
【図１０】図１０は、グループ生成処理の処理フローを示す図である。
【図１１】図１１は、１番目のメッシュについての分類結果の例を示す図である。
【図１２】図１２は、レコード群Ｒｓ抽出処理の処理フローを示す図である。
【図１３】図１３は、除外処理の処理フローを示す図である。
【図１４】図１４は、除外処理において生成される度数分布表の一例を示す図である。
【図１５】図１５は、除外処理において生成される度数分布表の一例を示す図である。
【図１６】図１６は、除外処理において生成される度数分布表の一例を示す図である。
【図１７】図１７は、除外処理において生成される度数分布表の一例を示す図である。
【図１８】図１８は、除外処理において生成される度数分布表の一例を示す図である。
【図１９】図１９は、除外処理において生成される度数分布表の一例を示す図である。
【図２０】図２０は、レコード群Ｒｓ抽出処理の処理フローを示す図である。
【図２１】図２１は、譲渡可能レコードの抽出処理の処理フローを示す図である。
【図２２】図２２は、抽出処理において生成される度数分布表の一例を示す図である。
【図２３】図２３は、抽出処理において生成される度数分布表の一例を示す図である。
【図２４】図２４は、抽出処理において生成される度数分布表の一例を示す図である。
【図２５】図２５は、抽出処理において生成される度数分布表の一例を示す図である。
【図２６】図２６は、抽出処理において生成される度数分布表の一例を示す図である。
【図２７】図２７は、メッシュとグループの対応付けテーブルの一例を示す図である。
【図２８】図２８は、譲れるレコード及び譲れないレコードの区別を行うためのグループデータテーブルの一例を示す図である。
【図２９】図２９は、行番号とグループＩＤの対応付けテーブルの一例を示す図である。
【図３０】図３０は、メッシュとグループの対応付けテーブルの一例を示す図である。
【図３１】図３１は、譲れるレコード及び譲れないレコードの区別を行うためのグループデータテーブルの一例を示す図である。
【図３２】図３２は、行番号とグループＩＤの対応付けテーブルの一例を示す図である。
【図３３】図３３は、２番目のメッシュについての分類結果の例を示す図である。
【図３４】図３４は、メッシュとグループの対応付けテーブルの一例を示す図である。
【図３５】図３５は、譲れるレコード及び譲れないレコードの区別を行うためのグループデータテーブルの一例を示す図である。
【図３６】図３６は、行番号とグループＩＤの対応付けテーブルの一例を示す図である。
【図３７】図３７は、３番目のメッシュについての分類結果の例を示す図である。
【図３８】図３８は、グループ化処理の結果の一例を示す図である。
【図３９】図３９は、処理結果の一例を示す図である。
【図４０】図４０は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００２８】
図３に、本発明の実施の形態に係る情報処理装置１００の機能ブロック図を示す。情報処理装置１００は、第１データ格納部１１０と、設定データ格納部１２０と、グループ化処理部１３０と、第２データ格納部１４０と、匿名化処理部１５０と、第３データ格納部１６０と、出力部１７０と、メッシュ生成部１８０と、第４データ格納部１９０とを有する。
【００２９】
第１データ格納部１１０は、例えば図４に示すような匿名化前のデータを格納している。図４の例では、各レコード（データブロックとも呼ぶ）は、ＩＤと、Ｘ（緯度）と、Ｙ（経度）と、速さと含む。行番号は、以下の説明のために付されている。
【００３０】
また、設定データ格納部１２０は、生成すべきメッシュの種類数ｘと、メッシュ要素のサイズｄと、度数分布についての条件（度数分布パターンとも呼ぶ）と、第１データ格納部１１０に格納されているデータのうちの機密属性（例えばＩＤ属性。機微属性とも呼ぶ。）及び数値属性（例えば緯度Ｘ及び経度Ｙを含む位置データ）の指定とが格納される。度数分布パターンは、最小種類数ｌと、減衰率ａとを含む。最小種類数ｌは２以上の整数であり、減衰率ａは１以下の正の実数である。例えば、ｌ種類のＩＤについて度数の多い順にｎ番目の度数がｎ−１番目の度数のａ倍以上であるという度数分布パターンが条件として設定される。
【００３１】
グループ化処理部１３０は、設定データ格納部１２０及び第４データ格納部１９０に格納されているデータを用いて、第１データ格納部１１０に格納されているレコード群をグループ化する処理を行い、処理結果を第２データ格納部１４０に格納する。匿名化処理部１５０は、グループ化の結果に基づき、各グループに属するレコードの数値属性値を変換する処理を行い、処理結果を第３データ格納部１６０に格納する。出力部１７０は、第３データ格納部１６０に格納されているデータを、他のコンピュータ、表示装置や印刷装置などに出力する。
【００３２】
メッシュ生成部１８０は、設定データ格納部１２０に格納されているメッシュの種類数ｘ及びメッシュ要素のサイズｄに従って、メッシュのデータを生成し、第４データ格納部１９０に格納する。
【００３３】
メッシュ要素のサイズｄは、各数値属性で張られる空間においてメッシュ要素の辺の長さを表す正の数値列である。たとえば、数値属性が（Ｘ，Ｙ）の２次元なら、ｄ＝（６，６）などと設定される。
【００３４】
メッシュの種類数ｘは、自然数である。例えば、異なるメッシュを６種類使うなら、ｘ＝６となる。本実施の形態では、メッシュはｎ次元矩形メッシュ（ｎは数値属性の数）とする。なお、メッシュは複数のメッシュ要素を含み、メッシュ要素間の境界（壁とも呼ぶ）は、２次元であれば辺であり、３次元であれば平面であり、４次元以上であれば超平面となる。また、メッシュは一般的には、三角形メッシュや六角形メッシュなど、数値属性の値がどのメッシュ要素に該当するかすぐに計算できるような規則に従っていれば、矩形に限らない。
【００３５】
次に、図５乃至図３９を用いて、情報処理装置１００の処理内容について説明する。
【００３６】
メッシュ生成部１８０は、メッシュ生成処理を実行し、生成されたメッシュのデータを、第４データ格納部１９０に格納する（図５：ステップＳ１）。メッシュ生成処理については、図６乃至図９を用いて説明する。
【００３７】
まず、メッシュ生成部１８０は、メッシュの空のリストＭを生成する（図６：ステップＳ１１）。また、メッシュ生成部１８０は、原点（０，０）をリストＭに追加する（ステップＳ１３）。まず、メッシュ要素の１辺の長さが「１」であるメッシュを生成するものとする。従って、以降の処理では、基準の点についての各次元の値域が［０，１）に入るメッシュが、リストＭに追加される。
【００３８】
そして、メッシュ生成部１８０は、リストＭに含まれるメッシュの種類数｜Ｍ｜は、指定された種類数ｘに達したか否かを判断する（ステップＳ１５）。ステップＳ１３の直後であれば、｜Ｍ｜＝１であり、例えばｘ＝６であるとすると、この条件を満たしていない。
【００３９】
ステップＳ１５の条件を満たしていない場合には、メッシュ生成部１８０は、リストＭに属する各メッシュの境界のうち最も近い境界との距離が最大となる点Ｐ’を選択する（ステップＳ１９）。
【００４０】
本実施の形態では、リストＭに含まれるメッシュの種類数｜Ｍ｜に応じた点（基準点とも呼ぶ）を発生させる。すなわち、ｃ＝ceil（log2（｜Ｍ｜＋１））（ceilは天井関数）と定義して、点（２-c，２-c）を基点として、［０，１）内を幅２-c+1で変動させた点を生成する。最初は、｜Ｍ｜＝１なので、ｃ＝１となる。従って、（１／２，１／２）のみが生成される。
【００４１】
さらに、メッシュ生成部１８０は、選択された点Ｐ’のうち、リストＭに属する各メッシュの格子点のうち近い格子点との距離が最大となる点のメッシュをリストＭに追加する（ステップＳ２１）。最初は、基準点が（１／２，１／２）となるメッシュがリストＭに追加される。そして処理はステップＳ１５に戻る。
【００４２】
この状態では、図７に示すようなメッシュが生成されたことになる。なお、まだメッシュ要素の辺の長さは「１」のままである。
【００４３】
ステップＳ１５において、リストＭに含まれるメッシュの種類数｜Ｍ｜が、指定された種類数ｘに達した場合には、メッシュ生成部１８０は、メッシュ要素のサイズｄから、各メッシュを設定し、第４データ格納部１９０に格納する（ステップＳ２３）。そして処理は呼び出し元の処理に戻る。
【００４４】
上で述べた例では、｜Ｍ｜＝２で次にステップＳ１９に移行すると、ｃ＝２となるので、Ｐ＝｛（１／４，１／４），（１／４，３／４），（３／４，１／４），（３／４，３／４）｝が生成される。この段階では、どの点も、リストＭに含まれる各メッシュの格子点からの距離は同じなので、ステップＳ２１では、いずれかの点、例えばｐ＝（１／４，１／４）を選び、リストＭに追加する。すなわち、Ｍ＝｛（０，０），（１／２，１／２），（１／４，１／４）｝となる。
【００４５】
さらに、｜Ｍ｜＝３で次にステップＳ１９に移行すると、ｃ＝２のままとなる。従って、前回と同じＰが生成されるが、（３／４，１／４）及び（１／４，３／４）は、（１／４，１／４）のメッシュの辺上に載るので、それより距離が遠い（３／４，３／４）が採用される。ステップＳ２１でも、ｐ＝（３／４，３／４）が選択されて、リストＭに追加される。すなわち、Ｍ＝｛（０，０），（１／２，１／２），（１／４，１／４），（３／４，３／４）｝となる。
【００４６】
さらに、｜Ｍ｜＝４で次にステップＳ１９に移行すると、ｃ＝３となるので、Ｐ＝｛（１／８，１／８）、（１／８，３／８），．．．，（３／８，１／８），（３／８，３／８），．．．，（７／８，７／８）｝が生成される。Ｐに含まれる点のうち、リストＭの各メッシュの格子点のうち、近い点と距離が最大となる点の１つであるｐ（１／８，５／８）をリストＭに追加する。なお、近い格子点との距離が最大とは、たとえば、最も近い格子点とのユークリッド距離が最大で、それが同じ場合次に近い格子点とのユークリッド距離が最大で、といったように以降同様に各格子点との距離を比較して決める。例を挙げると、点（１／８，５／８）の最も近い点の１つである（１／４，１／４）との距離は１０1/2／８だが、（１／８，３／８）の最も近い点（１／４，１／４）との距離は２1/2／８であり、距離が短い後者の点は採用されない。そうすると、Ｍ＝｛（０，０），（１／２，１／２），（１／４，１／４），（３／４，３／４），（１／８，５／８）｝となる。
【００４７】
さらに、｜Ｍ｜＝５で次にステップＳ１９に移行すると、ｃ＝３のままとなる。そして同様に処理すると、（５／８，１／８）が選択されて、Ｍ＝｛（０，０），（１／２，１／２），（１／４，１／４），（３／４，３／４），（１／８，５／８），（５／８，１／８）｝となる。ここで、｜Ｍ｜＝ｘ＝６となり、ｄ＝（６，６）から、以下のようなメッシュの基準点が生成される。Ｍ＝｛（０，０），（３，３），（３／２，３／２），（９／２，９／２），（３／４，１５／４），（１５／４，３／４）｝。そして、処理は呼び出し元の処理に戻る。
【００４８】
図６の処理フローでは、メッシュの境界を共有しないように、ずらしてメッシュを生成するようにしている。このようにずらしてメッシュを生成することで、以下で述べるグループ化処理で、固定のメッシュ要素単位でグループ化を行うが、多様なグループ化が可能になる。
【００４９】
なお、上で述べた基準点は、図８に示すようにばらつくようになる。２次元の矩形格子を採用しているので、メッシュがそれぞれ少しずつずらして生成されていることがこの図からも分かる。なお、図中の数字は生成順番を示している。また、図９に、実際のメッシュの重なり状態を示している。ここでは６番目に生成されるメッシュのメッシュ要素までを１つずつ示しているが、メッシュ要素の境界は共有されていない。
【００５０】
なお、図６の処理フローは、リストＭに含まれるメッシュから最も遠い位置のメッシュをリストＭに追加している処理とも言える。最も遠い位置の定義としては、以下のようなものとなる。
【００５１】
すなわち、リストＭと、２つのメッシュｍ１及びｍ２を入力として、Ｍからｍ２の方がｍ１よりも遠い場合には−１を、ｍ１の方がｍ２より遠い場合には１を、ｍ１とｍ２が同じ遠さの場合には０を返す関数ｃｍｐ（Ｍ，ｍ１，ｍ２）：｛−１，０，１｝を用意して、最も遠いメッシュの集合Ｆは、Ｆ＝｛ｍ｜∀ｍ’，ｃｍｐ（Ｍ，ｍ，ｍ’）≧０｝で定義される。
【００５２】
例えば、図６の処理フローにおけるステップＳ１９及びＳ２１の処理をｃｍｐ（Ｍ，ｍ１，ｍ２）に当てはめると、以下のようになる。
１．ｍ１及びｍ２それぞれの任意の境界（辺）と、リストＭの各メッシュの境界の中で最も近い境界との距離をｄ１及びｄ２としたとき、ｄ１＜ｄ２なら−１を返し、ｄ１＞ｄ２なら１を返す。
２．ｍ１及びｍ２それぞれの基準点と、リストＭに含まれる各メッシュの格子点の中で１番目に近い頂点との距離をｄ１及びｄ２としたとき、ｄ１＜ｄ２なら−１を返し、ｄ１＞ｄ２なら１を返す。
３．そうでない場合、２と同様に、２番目に近い格子点との距離の比較を行って条件に合うか判断し、...、｜Ｍ｜番目に近い格子点との距離の比較を行って条件に合うか判断する、ということを繰り返し、条件にあった時点で−１又は１を返す。
４．そうでなければ０を返す。
【００５３】
このような関数ｃｍｐによってＦを求め、その中から基準点が最も原点に近いメッシュを選択すればよい。
【００５４】
図５の処理フローの説明に戻って、グループ化処理部１３０は、第１データ格納部１１０に格納されているレコードに対して、第４データ格納部１９０及び設定データ格納部１２０に格納されているデータに従って、グループ生成処理を実行する（ステップＳ３）。グループ生成処理については、図１０乃至図３８を用いて説明する。
【００５５】
まず、グループ化処理部１３０は、第４データ格納部１９０におけるリストＭから、未処理のメッシュｍを１つ特定する（図１０：ステップＳ３１）。そして、グループ化処理部１３０は、第１データ格納部１１０に格納されているレコード群を、特定されたメッシュｍのメッシュ要素で分類する（ステップＳ３３）。
【００５６】
具体的には、各レコードに対してメッシュ要素識別子（ＩＤ）を算出し、ＩＤと行番号との対応関係表を生成する。例えば、メッシュ要素ＩＤは、ｆｌｏｏｒ（（数値属性−ｍ）／ｄ）として算出する。なお、ｆｌｏｏｒは床関数である。例えば、図４における行番号「８」のレコードは（Ｘ，Ｙ）＝（６，５）であり、ｍ＝（０，０），ｄ＝（６，６）であるから、（ｆｌｏｏｒ（（６−０）／６），ｆｌｏｏｒ（（５−０）／６））＝（１，０）がメッシュ要素ＩＤとなる。
【００５７】
以上のような処理を行うと、図１１に示すような分類がなされる。図１１の例では、３つのメッシュ要素に、各レコードが分類されている。
【００５８】
次に、グループ化処理部１３０は、レコードを含むメッシュ要素のうち、未処理のメッシュ要素ｓを１つ特定する（ステップＳ３５）。例えば、メッシュ要素ＩＤ（０，０）のメッシュ要素を特定する。
【００５９】
そして、グループ化処理部１３０は、特定されたメッシュ要素ｓ内において譲れないレコードとして第２データ格納部１４０に登録されているレコード以外のレコードＲａを抽出する（ステップＳ３７）。最初の場合には、譲れないレコードとして登録されているレコードは存在しない。但し、以下で述べる処理では譲れないレコードとして登録されているレコードが存在する場合には、当該レコードを除外してレコードＲａを特定する。最初の例では、Ｒａ＝｛１，２，３，４，５，６，７｝となる。
【００６０】
その後、グループ化処理部１３０は、レコード群Ｒｓ抽出処理を実行する（ステップＳ３９）。このレコード群Ｒｓ抽出処理については、図１２乃至図１９を用いて説明する。なお、この処理が終了すると、処理は端子Ａを介して図２０の処理に移行する。
【００６１】
まず、グループ化処理部１３０は、レコードＲａについての度数分布を生成し、レコードＲａにはｌ種類以上のＩＤ属性値が含まれるか判断する（ステップＳ１３３）。レコードＲａにｌ種類以上のＩＤ属性値が含まれない場合には、グループ化処理部１３０は、レコード群Ｒｓを空に設定する（ステップＳ１３８）。そして、処理は呼び出し元に戻る。ｌ種類以上のＩＤ属性値が含まれていない場合には、グループ化を行うことができないので、呼び出し元の処理に戻る。
【００６２】
一方、レコードＲａにｌ種類以上のＩＤ属性値が含まれる場合には、グループ化処理部１３０は、レコードＲａについての度数分布が、度数分布パターンにおける条件ａ（＝減衰率）を満たしているか判断する（ステップＳ１３４）。ｌ＝３及びａ＝０．５が設定されているものとする。度数が大きい順に並べて、ｎ番目の度数が、ｎ−１番目の度数のａ＝０．５以上であることが条件となっている。例えば｛Ｂ：２，Ａ：１，Ｃ：１｝という度数分布が得られた場合には、この条件を満たしている。
【００６３】
減衰率ａを用いるのは、度数分布の偏りが大きすぎるグループを作らない、すなわち安全性を高めるためである。減衰率ａは、ｌ種類以上あっても偏りが大きすぎる度数分布となるグループを許さないようにするための条件である。例えば、度数分布が｛Ａ：１００，Ｃ：１｝（Ａが１００個、Ｃが１個の意味）となるレコードを含む範囲を考える。この範囲は２種類のＩＤを含むので、この範囲が特定の１つのＩＤしか存在し得ないような地域に包含されることはない。しかし、度数の９９％以上がＡであり、この範囲のほとんどがＡしか存在し得ないような地域である可能性がある。そうであった場合、この範囲を開示すると、この範囲のほとんどのレコードがＡから提供されたことを推定しやすく問題となるからである。
【００６４】
レコードＲａについての度数分布が、度数分布パターンにおける条件を満たしている場合には、グループ化処理部１３０は、レコード群Ｒｓに、レコードＲａを全て設定する（ステップＳ１３６）。そして、処理は呼出元の処理に戻る。
【００６５】
一方、レコードＲａについての度数分布が、度数分布パターンにおける条件を満たしていない場合には、グループ化処理部１３０は、除外処理を実行する（ステップＳ１３５）。条件ｌを満たしていれば、条件ａを満たすようにレコードを除外することが可能である。従って、除外処理を実行する。除外処理については、図１３乃至図１９を用いて説明する。
【００６６】
そして、グループ化処理部１３０は、予め定められているルールに従って、除外処理で決定された数の除外すべきレコードを特定して、レコードＲａから除外して、残余をレコード群Ｒｓに設定する（ステップＳ１３７）。所定のルールは、例えばランダムといったような単純な方法でよい。
【００６７】
ここで、除外処理について説明する。まず、グループ化処理部１３０は、レコードＲａについて度数分布表Ｆを生成し、度数の昇順に整列させる（図１３：ステップＳ１４１）。上で述べた例では、除外処理は行われないので、ここでは図１４に示すような度数分布表Ｆが生成されたものとする。また、ｌ＝４且つａ＝０．５であるものとする。
【００６８】
そして、グループ化処理部１３０は、変数ｐを初期化し（ステップＳ１４３）、変数ｉを０に初期化する（ステップＳ１４５）。その後、グループ化処理部１３０は、ｉが度数分布表Ｆの行数｜Ｆ｜より小さいか判断する（ステップＳ１４７）。ｉが度数分布表Ｆの行数｜Ｆ｜より小さい場合には、グループ化処理部１３０は、ｉ＋ｌ−１が｜Ｆ｜より小さいか判断する（ステップＳ１４９）。ｉ＋ｌ−１が｜Ｆ｜より小さい場合には、グループ化処理部１３０は、変数ｐに対してＦ［ｉ］を代入する（ステップＳ１５１）。Ｆ［ｉ］は、Ｆのｉ＋１行目の度数である。ｉ＝０であれば、変数ｐには、Ｆの１行目の度数「１」が代入される。
【００６９】
一方、ｉ＋ｌ−１が｜Ｆ｜以上であれば、グループ化処理部１３０は、変数ｐに、ｍｉｎ（Ｆ［ｉ］，ｆｌｏｏｒ（ｐ／ａ））を代入する（ステップＳ１５３）。ｍｉｎ（Ａ，Ｂ）は、ＡとＢのうち小さい方を出力する関数である。
【００７０】
ステップＳ１５１又はＳ１５３の後に、グループ化処理部１３０は、Ｆ［ｉ］に、Ｆ［ｉ］−ｐを代入する（ステップＳ１５５）。ｉ＝０の時に、Ｓ１４９を実行すると、度数分布表Ｆは、図１５のようになる。
【００７１】
その後、グループ化処理部１３０は、変数ｉを１インクリメントし（ステップＳ１５７）、処理はステップＳ１４７に戻る。
【００７２】
２回目のステップＳ１４７では、｜Ｆ｜＝５，ｉ＝１であるから、ｉ＜｜Ｆ｜となる。また、ｌ＝４であるので、ｉ＋ｌ−１＜｜Ｆ｜となる。従って、ステップＳ１５１でｐ＝３であり、Ｆ［１］＝３−３＝０となる。そうすると、度数分布表Ｆは、図１６のようになる。その後ｉ＝２となる。
【００７３】
３回目のステップＳ１４７では、｜Ｆ｜＝５，ｉ＝２であるから、ｉ＜｜Ｆ｜となる。また、ｌ＝４であるので、ｉ＋ｌ−１＜｜Ｆ｜とはならず、ステップＳ１５３に移行して、ａ＝０．５及びｐ＝３であるから、ｍｉｎ（Ｆ［ｉ］＝４，ｆｌｏｏｒ（ｐ／ａ）＝６）＝４となる。従って、Ｆ［２］＝４−４＝０となる。そうすると、度数分布表Ｆは、図１７のようになる。その後ｉ＝３となる。
【００７４】
４回目のステップＳ１４７では、｜Ｆ｜＝５、ｉ＝３であるから、ｉ＜｜Ｆ｜となる。また、ｌ＝４であるので、ｉ＋ｌ−１＜｜Ｆ｜とはならず、ステップＳ１５３に移行して、ａ＝０．５及びｐ＝４であるから、ｍｉｎ（Ｆ［ｉ］＝９，ｆｌｏｏｒ（ｐ／ａ）＝８）＝８となる。従って、Ｆ［３］＝９−８＝１となる。そうすると、度数分布表Ｆは、図１８のようになる。その後ｉ＝４となる。
【００７５】
５回目のステップＳ１４７では、｜Ｆ｜＝５、ｉ＝４であるから、ｉ＜｜Ｆ｜となる。また、ｌ＝４であるので、ｉ＋ｌ−１＜｜Ｆ｜とはならず、ステップＳ１５３に移行して、ａ＝０．５及びｐ＝８であるから、ｍｉｎ（Ｆ［ｉ］＝１０，ｆｌｏｏｒ（ｐ／ａ）＝１６）＝１０となる。従って、Ｆ［４］＝１０−１０＝０となる。そうすると、度数分布表Ｆは、図１９のようになる。その後ｉ＝５となる。
【００７６】
６回目のステップＳ１４７では、｜Ｆ｜＝５、ｉ＝５であるから、ｉ＜｜Ｆ｜が成り立たなくなる。そうすると、処理は呼出元の処理に戻る。すなわち、この時点における度数分布表Ｆ（図１９）が、除外すべきレコードを示している。ここでは、ＩＤが「Ｅ」のレコードを１つ除外することになる。除外するレコードについては、上で述べたように、ランダムに選択すればよい。
【００７７】
図１０の端子Ａを介して図２０の処理の説明に移行する。なお、上で述べていた例のように、Ｒａ＝｛１，２，３，４，５，６，７｝の場合、ｌ及びａの条件を満たすので、Ｒａ＝Ｒｓとなる。
【００７８】
グループ化処理部１３０は、レコード群Ｒｓが空であるか判断する（ステップＳ４１）。レコード群Ｒｓが空であると、グループ化は行われないので、処理はステップＳ５５に移行する。
【００７９】
一方、レコード群Ｒｓが空でない場合には、グループ化処理部１３０は、レコード群Ｒｓに未グルーピングのレコードが存在するか否かを判断する（ステップＳ４３）。未グルーピングのレコードが存在しない場合には、新たなグループの生成をわざわざ行うことはないので、処理はステップＳ５５に移行する。
【００８０】
一方、レコード群Ｒｓに未グルーピングのレコードが存在する場合には、グループ化処理部１３０は、レコード群Ｒｓでグループを生成する（ステップＳ４５）。Ｒｓ＝｛１，２，３，４，５，６，７｝が１つのグループとなる。
【００８１】
そして、グループ化処理部１３０は、生成されたグループに対して譲渡可能レコードの抽出処理を実行する（ステップＳ４７）。すなわち、生成されたグループのうち、度数分布パターンを満たす上で必須のレコード以外のレコードを抽出する処理を実行する。より具体的には、図２１乃至図２６を用いて説明する。
【００８２】
まず、グループ化処理部１３０は、レコードＲｓについて度数分布表Ｆを生成し、度数の昇順に整列させる（図２１：ステップＳ１７１）。処理を分かり易くするために、図２２に示すような度数分布表Ｆが生成されたものとする。
【００８３】
そして、グループ化処理部１３０は、変数ｃｉに｜Ｆ｜−ｌを設定し、変数ｍｉｎに、ｃｅｉｌ（Ｆ［ｃｉ］＊ａ）を設定する（ステップＳ１７３）。ｃｅｉｌ（ｘ）は天井関数であり、実数ｘに対してｘ以上の最小の整数を出力する関数である。Ｆ［ｉ］は度数分布表Ｆのｉ＋１行目の度数を表し、｜Ｆ｜は度数分布表Ｆの行数を表す。ｃｉ＝５−４＝１であり、ｍｉｎ＝ｃｅｉｌ（２＊０．５）＝１となる。
【００８４】
また、グループ化処理部１３０は、変数ｉを０に初期化し、変数ｍａｘを０に初期化する（ステップＳ１７５）。
【００８５】
その後、グループ化処理部１３０は、ｉ＜｜Ｆ｜であるか判断する（ステップＳ１７７）。ｉ＜｜Ｆ｜であれば、グループ化処理部１３０は、変数ｃを初期化する（ステップＳ１７９）。その後、グループ化処理部１３０は、ｉ＜ｃｉであるか判断する（ステップＳ１８１）。ｉ＝０であれば、ｃｉ＝１であるからこの条件は満たされている。
【００８６】
ｉ＜ｃｉであれば、グループ化処理部１３０は、ｃに０を設定する（ステップＳ１８３）。そうすると、グループ化処理部１３０は、Ｆ［ｉ］に、Ｆ［ｉ］−ｃを設定する（ステップＳ１８５）。Ｆ［ｉ］＝１であり、ｃ＝０であるから、Ｆ［ｉ］＝１となる。その後、グループ化処理部１３０は、ｉを１インクリメントし（ステップＳ１８７）、処理はステップＳ１７７に戻る。
【００８７】
ｉ＝１になると、ステップＳ１８１では、ｉ＜ｃｉは成り立たなくなるので、グループ化処理部１３０は、ｉ＋１＝｜Ｆ｜であるか判断する（ステップＳ１８９）。ｉ＝１であれば、ｉ＋１＝２であるから、この条件を満たさない。ステップＳ１８９の条件を満たさない場合には、グループ化処理部１３０は、ｃに、ｃｅｉｌ（Ｆ［ｉ＋１］＊ａ）を代入する（ステップＳ１９１）。ｃ＝ｃｅｉｌ（Ｆ［２］＊０．５）＝２となる。そして、グループ化処理部１３０は、ｍａｘ＜ｃであるか判断する（ステップＳ１９３）。ｍａｘ＝０であるからこの条件を満たす。そうすると、グループ化処理部１３０は、ｍａｘにｃを代入する（ステップＳ１９７）。すなわち、ｍａｘ＝ｃ＝２となる。その後、処理はステップＳ１８５に移行する。従って、２回目のステップＳ１８５では、Ｆ［１］＝２−２＝０となる。従って、図２３に示すような度数分布表Ｆになる。
【００８８】
ｉ＝２になると、ステップＳ１８１では、ｉ＜ｃｉは成り立たなくなるので、ステップＳ１８９に移行する。但し、ｉ＋１＜｜Ｆ｜であるから、ステップＳ１９１に処理は移行し、ｃ＝ｃｅｉｌ（Ｆ［３］＊０．５）＝２となる。ｍａｘ＝２であるから、ｍａｘ＜ｃの条件を満たしていない。そうすると、グループ化処理部１３０は、ｃにｍｉｎを代入する（ステップＳ１９５）。ｍｉｎ＝１であるから、ｃ＝１となる。そして処理はステップＳ１８５に移行して、３回目のステップＳ１８５では、Ｆ［２］＝３−１＝２となる。従って、図２４に示すような度数分布表Ｆになる。
【００８９】
ｉ＝３になると、ステップＳ１８１では、ｉ＜ｃｉは成り立たないので、ステップＳ１８９に移行する。但し、ｉ＋１＜｜Ｆ｜であるから、ステップＳ１９１に処理は移行し、ｃ＝ｃｅｉｌ（Ｆ［４］＊０．５）＝３となる。ｍａｘ＝２でｃ＝３であるから、ｍａｘ＜ｃの条件を満たしている。従って、ｍａｘ＝ｃ＝３となる。そして、４回目のステップＳ１８５では、Ｆ［３］＝４−３＝１となる。従って、図２５に示すような度数分布表Ｆとなる。
【００９０】
ｉ＝４になると、ステップＳ１８１では、ｉ＜ｃｉは成り立たないので、ステップＳ１８９に移行する。ｉ＋１＝｜Ｆ｜を満たすので、ステップＳ１９５に処理は移行し、ｃ＝ｍｉｎ＝１となる。そして処理はステップＳ１８５に移行して、５回目のステップＳ１８５では、Ｆ［４］＝Ｆ［４］−ｃ＝５−１＝４となる。従って、図２６に示すような度数分布表Ｆが得られる。
【００９１】
その後ｉ＝５になると、ステップＳ１７７ではｉ＜｜Ｆ｜の条件を満たさなくなるので、処理は呼出元の処理に戻る。従って図２６に示すように、ＩＤがＡの１レコード、ＩＤがＣの２レコード、ＩＤがＤの１レコード、及びＩＤがＥの４レコードが、譲渡可能なレコードとして特定されたことになる。
【００９２】
図２０の処理の説明に戻って、グループ化処理部１３０は、ステップＳ４７の処理結果に基づき、予め定められているルールに従って、譲渡可能なレコードを具体的に特定する（ステップＳ４９）。所定のルールについては、例えばランダムであっても良いし、行番号が大きい順番であっても良い。
【００９３】
上で述べた例では、Ｒｓ＝｛１，２，３，４，５，６，７｝のうち、譲れるレコードは｛２，４，６，７｝であり、譲れないレコードは｛１，３，５｝となる。
【００９４】
ここまでの処理によって、第２データ格納部１４０には、図２７乃至図２９のデータが格納される。図２７は、グループ化が行われたメッシュ及びメッシュ要素ＩＤとグループＩＤ（Ｇ＿ＩＤ）との対応付けを行うテーブルを表している。グループＩＤについてはユニークになるようにシリアルに番号付けする例を示している。また、図２８では、グループＩＤに対応付けて、当該グループに属するレコードのうち譲れないレコードの行番号集合と、譲れるレコードの行番号集合とが登録されるようになっている。さらに、図２９は、行番号とグループＩＤとの対応付けを示している。
【００９５】
そして、グループ化処理部１３０は、他のグループから譲ってもらったレコードが存在しているか否かを判断する（ステップＳ５１）。他のグループにグループ化されていたが、譲れるレコードに分類されていて今回生成されたグループに属するレコードが存在する場合には、所属グループを変更することになる。従って、他のグループから譲ってもらったレコードが存在している場合には、グループ化処理部１３０は、第２データ格納部１４０において、譲渡元グループから、譲ってもらったレコードの行番号を削除する（ステップＳ５３）。一方、他のグループから譲ってもらったレコードが存在していない場合には、処理はステップＳ５５に移行する。
【００９６】
そして、グループ化処理部１３０は、未処理のメッシュ要素が存在するか判断する（ステップＳ５５）。未処理のメッシュ要素が存在する場合には、処理は端子Ｂを介して図１０のステップＳ３５に戻る。一方、未処理のメッシュ要素が存在しない場合には、グループ化処理部１３０は、未処理のメッシュが存在するか否かを判断する（ステップＳ５７）。未処理のメッシュが存在する場合には、処理は端子Ｃを介して図１０のステップＳ３１に戻る。一方、未処理のメッシュが存在しない場合には、処理は呼び出し元の処理に戻る。
【００９７】
なお、上で述べた例では、メッシュ（０，０）についてメッシュ要素ＩＤ（１，０）に対する処理に移行する。但し、Ｒａ＝｛８｝となるので、ｌ及びａの条件を満たさないので、Ｒｓは空に設定されて、グループ化は行われない。
【００９８】
また、メッシュ（０，０）についてメッシュ要素ＩＤ（１，１）に対する処理に移行する。この場合、Ｒａ＝｛９，１０，１１，１２｝となって、ｌ及びａの条件を満たすので、Ｒａ＝Ｒｓ＝｛９，１０，１１，１２｝が設定され、グループもそのまま生成される。なお、譲渡可能レコードの抽出処理（図２１）を実行すると、｛１２｝が譲れるレコードに特定されるので、譲れないレコードは｛９，１０，１１｝となる。
【００９９】
ここまで処理すると、第２データ格納部１４０には、図３０乃至図３２に示すようなデータが格納される。図３０は、図２７の後の状態を表しており、グループＩＤ「２」が、メッシュ（０，０）及びメッシュ要素ＩＤ（１，１）に付与されている。また、図３１は、図２８の後の状態を表しており、グループＩＤ「２」について、上で述べたように、譲れないレコードの行番号集合｛９，１０，１１｝、及び譲れるレコードの行番号集合｛１２｝が示されている。図３２は、図２９の後の状態を表しており、グループＩＤ「２」についての行のデータが追加されている。
【０１００】
次に、メッシュ（３，３）の処理に移行して、レコードの分類を行うと、図３３のような分類結果が得られる。２つのメッシュ要素に分類されたことが分かる。
【０１０１】
まず、メッシュ要素ＩＤ（−１，０）のメッシュ要素に分類されたレコードを処理する。レコード｛１，２｝は、ｌ及びａの条件を満たさないので、メッシュ要素ＩＤ（０，０）の処理に移行する。
【０１０２】
そうすると、｛３，４，５，６，７，８，９，１０，１１，１２｝のうち、これまでに生成されたグループにおいて譲れないレコードは｛１，３，５，９，１０，１１｝であるから、Ｒａ＝｛４，６，７，８，１２｝となる。このＲａはｌ及びａの条件を満たすので、Ｒａ＝Ｒｓとなる。
【０１０３】
Ｒｓの中にはレコード｛８｝が含まれているので、Ｒｓでグループを生成することになる。さらに、譲渡可能レコードの抽出処理（図２１）を実行すると、譲れるレコードは｛７，８｝と特定され、譲れないレコードは｛４，６，１２｝となる。なお、これらは図３１から分かるように既にグループ化されているので、各グループから譲ってもらうことになる。
【０１０４】
そうすると、第２データ格納部１４０に格納されるデータは、図３４乃至図３６に示すようなデータに更新される。図３４は、図３０の後の状態を表しており、グループＩＤに対応付けてメッシュ（３，３）のメッシュ要素ＩＤ（０，０）が追加されている。さらに、図３５は、図３１の後の状態を表しており、グループＩＤ「３」に対応付けて、譲れないレコード｛４，６，１２｝、及び譲れるレコード｛７，８｝が登録されている。レコード｛８｝以外は、他のグループから譲ってもらったので、グループ「１」及び「２」から、それらのグループの行番号が削除されている。図３６は、図３２の後の状態を表しており、レコード｛８｝が新たに追加され、譲ってもらったレコードについてのグループＩＤが変更になっている。
【０１０５】
さらに、メッシュ（３／２，３／２）についての処理に移行する。そうすると、図３７に示すような分類結果が得られる。図３７からも分かるように、メッシュ要素ＩＤ（−１，０）（０，１）（１，１）はｌ及びａの条件を満たさない。メッシュ要素ＩＤ（０，０）の場合には、これまでに生成されたグループにおいて譲れないレコードは｛１，３，４，５，６，９，１０，１１，１２｝であるから、Ｒａ＝｛２，７，８｝となる。これは、ｌ及びａの条件を満たすので、Ｒａ＝Ｒｓとなる。但し、｛２，７，８｝は皆グルーピング済みであるので、新たなグループが生成されないことになる。
【０１０６】
以下、他のメッシュについて処理を行っても、新たにグループが生成されることはない。
【０１０７】
以上の処理結果を、平面上に表したのが図３８である。図３８において、三角はＩＤ「Ａ」のレコードを表し、×はＩＤ「Ｂ」のレコードを表し、丸はＩＤ「Ｃ」のレコードを表し、このような記号の脇の番号は行番号を表す。
【０１０８】
グループ「１」は矩形１００１に対応し、レコード｛１，２，３，５｝が所属する。また、グループ「２」は矩形１００２に対応し、レコード｛９，１０，１１｝が所属する。グループ「３」は矩形１００３に対応し、レコード｛４，６，７，８，１２｝が所属する。このように、重なっている領域部分に含まれるレコードを分け合っており、各矩形において特定のＩＤのみが所属することはない。
【０１０９】
図５の処理の説明に戻って、匿名化処理部１５０は、第２データ格納部１４０に格納されているデータから、グループ毎に匿名化を実行し、処理結果を第３データ格納部１６０に格納する（ステップＳ５）。例えば、グループに対応するメッシュ要素の中心点に、そのグループに所属するレコードが存在するようにデータを変換すると共に、機密属性であるＩＤを削除する。例えば、図４に示したレコード群の場合には、図３９に示すようなデータが得られる。図４の（Ｘ，Ｙ）が、メッシュ要素の中心座標で置換されていることが分かる。このように匿名化されて、個々のレコードが特定されることはない。
【０１１０】
そして、出力部１７０は、第３データ格納部１６０に格納されているデータを、出力装置（例えば表示装置、印刷装置やネットワークで接続された他のコンピュータ）に出力する（ステップＳ７）。
【０１１１】
以上のように処理を行えば、匿名性と分析精度を両立したデータを開示することができるようになる。また、メッシュ生成は高速に行われるので、全体の匿名化処理をも高速に行える。
【０１１２】
多様性の条件ｌを満たすようにグルーピングされたレコードだけが開示されるが、各グループには機密属性値についてｌ種類以上あるので、各グループのレコードが特定のＩＤしか存在し得ないようなメッシュ要素に包含されることはなく、匿名性が担保される。
【０１１３】
また、開示される各メッシュ要素は大きさｄ未満となるため、小さいｄを指定することで高精度な分析を期待される。但し、ｄが小さいほどいずれのメッシュ要素にも分類されないレコードが増え、そのようなレコードは開示されないため、ｄを小さくし過ぎても良くない。
【０１１４】
さらに、複数種類のメッシュで多様性の条件ｌを満たすか否かを判定するため、多様性ｌの条件を満たさないレコード数を減らすことができる。これは、開示されるレコード数を増やす、つまり分析に使えるデータ量が増えることになるので、高精度な分析が期待される。
【０１１５】
以上本発明の実施の形態を説明したが、本発明はこの実施の形態に限定されるものではない。例えば、図３に示した機能ブロック図は一例であって、プログラムモジュール構成やファイル構成とは一致しない場合もある。処理フローについても、処理結果が変わらない限り、ステップの順番を入れ替えたり、複数ステップを並列に実行するようにしても良い。
【０１１６】
なお、図６のメッシュ生成処理は一例であって、他の手順で同様のメッシュを生成しても良いし、さらに異なる態様のメッシュを生成するようにしても良い。予め単位サイズのメッシュを所定種類だけ生成しておき、サイズｄに応じてサイズ変換を行うようにしても良い。
【０１１７】
なお、上で述べた情報処理装置１００は、例えばコンピュータ装置であって、図４０に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１１８】
以上述べた本実施の形態をまとめると、以下のようになる。
【０１１９】
本実施の形態に係る匿名化データ生成方法は、（Ａ）データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、（Ｂ）上記グループに属するデータブロックの数値属性値を、上記グループについての数値属性値で置換する処理を含む。
【０１２０】
機密属性値の度数分布が所定の条件を満たすデータブロックのグループが生成されるので、確実な匿名化がなされる。また、複数種類のメッシュを用いることで、いずれかのメッシュのメッシュ要素でグループ化が行われる可能性があるため、開示されないデータブロックの数を減らすことができる。すなわち、分析に用いることができるデータ量が増加し、分析精度が向上する。また、メッシュ要素のサイズについても調整可能であり、この点についても分析精度向上の要因となる。メッシュ要素のサイズは、メッシュの各種類について同じにする場合もある。さらに、任意の位置にグループ化のための範囲を規定することによりグループ化を行う場合に比して処理が高速化される。
【０１２１】
さらに、本匿名化データ生成方法は、上で述べたグループに属するデータブロックの機密属性値を削除する処理をさらに含むようにしても良い。これによって安全なデータを開示できるようになる。
【０１２２】
さらに、上で述べた所定の条件が、機密属性値の種類数の下限値を含む場合もある。この場合、上で述べた抽出する処理は、（ａ１）グループ化未了の第１のデータブロックを含み且つ上記１つのメッシュ要素に含まれるデータブロックの集合における機密属性値の種類が、機密属性値の種類の下限値以上となっているか判断する処理を含むようにしても良い。このようにすれば、秘匿化の安全性が高まる。
【０１２３】
さらに、上で述べた抽出する処理は、（ａ２）グループ化未了の第１のデータブロックを含み且つ上記１つのメッシュ要素に含まれるデータブロックの第２の集合についての機密属性値の度数分布が、所定の条件を満たすか判断し、（ａ３）データブロックの第２の集合についての機密属性値の度数分布が所定の条件を満たさない場合には、所定の条件を満たすようにデータブロックの第２の集合から第２のデータブロックを除外することでデータブロックのグループを生成する処理を含むようにしても良い。例えば、データブロックの第２の集合についての機密属性値の種類数が、その下限値以上となっていれば、適切なデータブロックを除外することで度数分布の条件を満たすようになる場合もある。
【０１２４】
また、上で述べた抽出する処理は、（ａ４）データブロックのグループから、機密属性値の度数分布が所定の条件を満たす上で必須となるデータブロック以外の第３のデータブロックを抽出する処理を含むようにしても良い。この場合、データブロックの他のグループを抽出する処理において、第３のデータブロックが他の種類のメッシュにおけるメッシュ要素において抽出される場合もある。このようにすれば、第３のデータブロックが他のグループ生成に用いられるので、削除されてしまうデータブロックを削減することができるようになる。
【０１２５】
なお、本実施の形態に係る匿名化データ生成方法は、（Ｃ）メッシュ要素の境界を共有しないように、複数種類のメッシュを生成する処理をさらに含む場合もある。このようにすれば、匿名化されないデータブロックをより効率的に削減できるようになる。
【０１２６】
また、本実施の形態に係る匿名化データ生成方法は、（Ｄ）これまでに生成されたメッシュの境界のうち最も近い境界との距離が最大となり、且つこれまでに生成されたメッシュの格子点との距離が最大となる基準点を選択し、（Ｅ）選択された基準点及びメッシュ要素のサイズに基づきメッシュを生成する処理をさらに含むようにしても良い。このようにすれば、匿名化されないデータブロックをより効率的に削減できるようになる。
【０１２７】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０１２８】
以下、本実施の形態に係る付記を記す。
【０１２９】
（付記１）
データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、前記複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、
前記グループに属するデータブロックの数値属性値を、前記グループについての数値属性値で置換する
処理を含み、コンピュータにより実行される匿名化データ生成方法。
【０１３０】
（付記２）
前記グループに属するデータブロックの機密属性値を削除する
処理をさらに含む付記１記載の匿名化データ生成方法。
【０１３１】
（付記３）
前記所定の条件が、機密属性値の種類数の下限値を含み、
前記抽出する処理は、
前記グループ化未了の第１のデータブロックを含み且つ前記１つのメッシュ要素に含まれるデータブロックの集合における機密属性値の種類が、前記機密属性値の種類の下限値以上となっているか判断する
処理を含む付記１又は２記載の匿名化データ生成方法。
【０１３２】
（付記４）
前記抽出する処理は、
前記グループ化未了の第１のデータブロックを含み且つ前記１つのメッシュ要素に含まれるデータブロックの第２の集合についての機密属性値の度数分布が、前記所定の条件を満たすか判断し、
前記データブロックの第２の集合についての機密属性値の度数分布が前記所定の条件を満たさない場合には、前記所定の条件を満たすように前記データブロックの第２の集合から第２のデータブロックを除外することでデータブロックのグループを生成する
処理を含む付記１乃至３のいずれか１つ記載の匿名化データ生成方法。
【０１３３】
（付記５）
前記抽出する処理は、
前記データブロックのグループから、前記機密属性値の度数分布が前記所定の条件を満たす上で必須となるデータブロック以外の第３のデータブロックを抽出する処理
を含み、
データブロックの他のグループを抽出する処理において、前記第３のデータブロックが他の種類のメッシュにおけるメッシュ要素において抽出される
付記１乃至４のいずれか１つ記載の匿名化データ生成方法。
【０１３４】
（付記６）
メッシュ要素の境界を共有しないように、前記複数種類のメッシュを生成する
処理をさらに含む付記１乃至５のいずれか１つ記載の匿名化データ生成方法。
【０１３５】
（付記７）
これまでに生成されたメッシュの境界のうち最も近い境界との距離が最大となり、且つ前記これまでに生成されたメッシュの格子点との距離が最大となる基準点を選択し、
選択された前記基準点及び前記メッシュ要素のサイズに基づきメッシュを生成する
処理をさらに含む付記１乃至５のいずれか１つ記載の匿名化データ生成方法。
【０１３６】
（付記８）
データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、前記複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出し、
前記グループに属するデータブロックの数値属性値を、前記グループについての数値属性値で置換する
処理を、コンピュータに実行させるための匿名化データ生成プログラム。
【０１３７】
（付記９）
データ格納部に格納されており且つ各々機密属性値と数値属性値とを含む複数のデータブロックにおける各数値属性で張られる空間における複数種類のメッシュの各々について、前記複数のデータブロックのうち、当該メッシュの１つのメッシュ要素に含まれ且つグループ化未了の第１のデータブロックを含み且つ機密属性値の度数分布が所定の条件を満すデータブロックのグループを抽出するグループ化処理部と、
前記グループに属するデータブロックの数値属性値を、前記グループについての数値属性値で置換する匿名化処理部と、
を有する情報処理装置。
【符号の説明】
【０１３８】
１１０  第１データ格納部
１２０  設定データ格納部
１３０  グループ化処理部
１４０  第２データ格納部
１５０  匿名化処理部
１６０  第３データ格納部
１７０  出力部
１８０  メッシュ生成部
１９０  第４データ格納部
【図１】
2015090617.tif 000003
【図２】
2015090617.tif 000004
【図３】
2015090617.tif 000005
【図４】
2015090617.tif 000006
【図５】
2015090617.tif 000007
【図６】
2015090617.tif 000008
【図７】
2015090617.tif 000009
【図８】
2015090617.tif 000010
【図９】
2015090617.tif 000011
【図１０】
2015090617.tif 000012
【図１１】
2015090617.tif 000013
【図１２】
2015090617.tif 000014
【図１３】
2015090617.tif 000015
【図１４】
2015090617.tif 000016
【図１５】
2015090617.tif 000017
【図１６】
2015090617.tif 000018
【図１７】
2015090617.tif 000019
【図１８】
2015090617.tif 000020
【図１９】
2015090617.tif 000021
【図２０】
2015090617.tif 000022
【図２１】
2015090617.tif 000023
【図２２】
2015090617.tif 000024
【図２３】
2015090617.tif 000025
【図２４】
2015090617.tif 000026
【図２５】
2015090617.tif 000027
【図２６】
2015090617.tif 000028
【図２７】
2015090617.tif 000029
【図２８】
2015090617.tif 000030
【図２９】
2015090617.tif 000031
【図３０】
2015090617.tif 000032
【図３１】
2015090617.tif 000033
【図３２】
2015090617.tif 000034
【図３３】
2015090617.tif 000035
【図３４】
2015090617.tif 000036
【図３５】
2015090617.tif 000037
【図３６】
2015090617.tif 000038
【図３７】
2015090617.tif 000039
【図３８】
2015090617.tif 000040
【図３９】
2015090617.tif 000041
【図４０】
2015090617.tif 000042