(57)【要約】【課題】情報量の減少を最低限に抑えて情報を抽象化するための条件を効率よく導出することを可能とする。【解決手段】複数の対象属性が取り得る属性値を区分する複数の分類の組み合わせを第１の元として、当該分類をより抽象化する順序関係に基づき規定される第１の束のうち、所定の条件に基づく匿名性を満たす極小元を探索する探索処理と、対象属性ごとの分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された極小元に対応する第２の元の補集合の極小横断に基づき、新たな基準点を導出する基準点導出処理と、を含み、新たな基準点に基づく探索処理と、当該探索処理の結果に基づく基準点導出処理とを、新たな基準点が導出されなくなるまで実行し、探索された一連の極小元それぞれが示す分類の組み合わせを出力する、情報処理方法。【選択図】図１
2016053829.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサが、複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理を実行することと、
前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理を実行することと、
を含み、
プロセッサが、特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とを、前記新たな基準点が導出されなくなるまで実行し、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力する、情報処理方法。
【請求項２】
前記匿名性は、前記テーブル中において、前記２以上の対象属性それぞれの前記属性値の組み合わせが等しい前記レコードの集合を示す等価クラスのうち、レコード数が所定の数ｋ未満の前記等価クラスに対応する前記レコードを、所定の数ｔ以下の範囲で削除した場合に、当該レコードを削除した後の前記テーブル中の前記レコードに基づく前記等価クラスのそれぞれについて、レコード数が前記所定の数ｋ以上となることを条件とする、請求項１に記載の情報処理方法。
【請求項３】
前記第２の束は、前記対象属性ごとの前記分類の数の和を最大とする正の整数の有限集合の冪集合を前記第２の元として、当該第２の元の包含関係を順序関係として規定される、請求項１に記載の情報処理方法。
【請求項４】
前記第１の束における前記第１の元それぞれと、前記第２の束における前記第２の元それぞれとは、前記第１の束の最大元と前記第２の束の最小元とが対応し、かつ、前記第１の束の最小元と前記第２の束の最大元と対応するように、前記第１の束及び前第２の束それぞれの順序関係に基づき、あらかじめ対応付けられる、請求項３に記載の情報処理装置。
【請求項５】
前記第２の束において、
前記対象属性それぞれには、前記正の整数の有限集合の各要素うち、互いに異なる複数の連続した正の整数に対応した要素が関連付けられ、
当該対象属性に対応する前記複数の分類それぞれは、前記複数の連続した正の整数に対応した当該要素に基づく有限集合の部分集合に対応付けられる、請求項３に記載の情報処理装置。
【請求項６】
前記第２の束において、
前記対象属性に対応する複数の分類それぞれは、より具体化された当該分類ほど、当該対象属性に関連付けられた前記複数の連続した正の整数に対応した要素のうち、より多くの当該要素が、値のより小さい要素から順次加えられた部分集合に対応付けられる、請求項５に記載の情報処理装置。
【請求項７】
前記極小横断に対応する前記第１の元は、当該極小横断に対して、前記対象属性ごとに、当該対象属性に関連付けられた前記複数の連続した正の整数に対応した要素のうち、当該極小横断が含む当該要素よりも値の小さい他の要素が補間された、正の整数の有限集合に対応する前記第２の元に基づき特定される、請求項６に記載の情報処理装置。
【請求項８】
最初に実行される前記探索処理では、前記第１の束の最大元を前記基準点として、前記極小元が探索される、請求項１に記載の情報処理方法。
【請求項９】
前記最大元は、前記第１の束のうち、前記２以上の対象属性それぞれの前記属性値を最も抽象化する前記分類の組み合わせに対応する前記第１の元である、請求項８に記載の情報処理方法。
【請求項１０】
前記探索処理では、前記基準点から、前記２以上の対象属性のうち少なくともいずれかに対応する前記分類がより具体化される方向に向けて、前記極小元が探索される、請求項１に記載の情報処理方法。
【請求項１１】
前記探索処理では、前記２以上の対象属性のうち少なくともいずれかに対応する前記分類を、より具体化される方向に向けた二分探索に基づき、前記極小元が探索される、請求項１０に記載の情報処理装置。
【請求項１２】
前記極小横断それぞれに対応する前記第１の元のうち、前記探索処理に基づき探索済みの前記第１の元は、前記新たな基準点の候補から除かれる、請求項１に記載の情報処理方法。
【請求項１３】
前記極小横断は、前記補集合をハイパーエッジとするハイパーグラフの双対化に基づき特定される、請求項１に記載の情報処理方法。
【請求項１４】
前記探索処理と前記基準点導出処理との少なくともいずれかは、複数のプロセッサにより分散処理される、請求項１に記載の情報処理方法。
【請求項１５】
コンピュータに、
複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理と、
前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理と、
を実行させ、
特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とを、前記新たな基準点が導出されなくなるまで実行させる、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力させる、プログラム。
【請求項１６】
複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理を実行する極小元探索部と、
前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理を実行する基準点導出部と、
特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とが、前記新たな基準点が導出されなくなるまで実行された結果に基づき、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力する出力部と、
を備える、情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理方法、プログラム、及び情報処理装置に関する。
【背景技術】
【０００２】
近年では、ネットワークや各種センサ等の発達に伴い、各種情報を収集する手段が多様化しており、収集される情報も多岐に亘り、このような収集手段により収集された各種情報が様々なビジネスに活用されている。また、近年では、例えば、データマイニングと呼ばれる技術等を活用することで、個々のデータのみでは明示されておらず導き出すことが困難な情報を、データベース等のような複数のデータの集合から抽出することも可能となってきている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許出願公開第２０１０／０３３２５３７号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００４】
一方で、収集される情報の中には、個人を特定することが可能な情報も含まれており、当該個人のプライバシの保護を要する場合もある。このような課題に対して、収集された各種情報を抽象化することで匿名性を高め、個人のプライバシを保護することも可能ではあるが、情報の抽象化に伴い情報量が減少し、データの有用性が損なわれる場合もある。
【０００５】
そこで、本開示では、情報量の減少を最低限に抑えて情報を抽象化するための条件を効率よく導出することが可能な、情報処理方法、プログラム、及び情報処理装置を提案する。
【課題を解決するための手段】
【０００６】
本開示によれば、プロセッサが、複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理を実行することと、前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理を実行することと、を含み、プロセッサが、特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とを、前記新たな基準点が導出されなくなるまで実行し、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力する、情報処理方法が提供される。
【０００７】
また、本開示によれば、コンピュータに、複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理と、前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理と、を実行させ、特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とを、前記新たな基準点が導出されなくなるまで実行させる、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力させる、プログラムが提供される。
【０００８】
また、本開示によれば、複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理を実行する極小元探索部と、前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理を実行する基準点導出部と、特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とが、前記新たな基準点が導出されなくなるまで実行された結果に基づき、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力する出力部と、を備える、情報処理装置が提供される。
【発明の効果】
【０００９】
以上説明したように本開示によれば、情報量の減少を最低限に抑えて情報を抽象化するための条件を効率よく導出することが可能な、情報処理方法、プログラム、及び情報処理装置が提供される。
【００１０】
なお、上記の効果は必ずしも限定的なものではなく、上記の効果とともに、または上記の効果に代えて、本明細書に示されたいずれかの効果、または本明細書から把握され得る他の効果が奏されてもよい。
【図面の簡単な説明】
【００１１】
【図１】本開示の実施形態に係る情報処理装置が適用された情報処理システムの概略的なシステム構成の一例を示している。
【図２】テーブルの構成の一例について説明するための説明図である。
【図３】テーブルの一部の属性の属性値を一般化することで、より匿名性を高めたテーブルを生成する処理の概要について説明するための説明図である。
【図４】（ｋ，ｔ）−匿名性について説明するための説明図である。
【図５】属性の一般化階層について説明するための説明図である。
【図６】属性の一般化階層について説明するための説明図である。
【図７】一般化戦略からなる束について説明するための説明図である。
【図８】ハイパーグラフ及び横断について説明するための説明図である。
【図９】ハイパーグラフ及び横断について説明するための説明図である。
【図１０】同実施形態に係る情報処理装置の機能構成の一例について説明するための説明図である。
【図１１】対象となる属性の属性値を一般化する処理の一例について説明するための説明図である。
【図１２】対象となる属性の属性値を、入力として指定された一般化戦略と、当該属性の一般化階層とに基づき一般化する処理の処理結果の一例である。
【図１３】所望の一般化戦略が、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略か否かを判定する処理の一例について説明するための説明図である。
【図１４】般化戦略からなる束と離散集合から誘導される束との間の対応関係の一例について示した図である。
【図１５】一般化戦略からなる束の元を、離散集合から誘導される束の元に変換する処理の一例について説明するための説明図である。
【図１６】一般化戦略からなる束の元を、離散集合から誘導される束の元に変換する処理の一例について説明するための説明図である。
【図１７】離散集合から誘導される束の元を、一般化戦略からなる束の元に変換する処理の一例について説明するための説明図である。
【図１８】一般化戦略からなる束における各一般化ノードから、（ｋ，ｔ）−匿名性を満たす極小元を探索する処理の一例について説明するための説明図である。
【図１９】一般化戦略からなる束における各一般化ノードから、（ｋ，ｔ）−匿名性を満たす極小元を探索する処理の一例について説明するための説明図である。
【図２０】解析部の一連の処理の流れの一例について説明するための説明図である。
【図２１】解析部の一連の処理の流れの一例について説明するための説明図である。
【図２２】基準点導出部の処理の一例について説明するための説明図である。
【図２３】基準点導出部の処理の一例について説明するための説明図である。
【図２４】基準点導出部の処理の一例について説明するための説明図である。
【図２５】極小元探索部の処理の一例について説明するための説明図である。
【図２６】極小元探索部の処理結果の一例について説明するための説明図である。
【図２７】同実施形態に係る情報処理装置による処理の計算量について説明するための説明図である。
【図２８】変形例１に係る解析部の一連の処理の流れの一例について説明するための説明図である。
【図２９】変形例１に係る解析部の一連の処理の流れの一例について説明するための説明図である。
【図３０】変形例２に係る情報処理システムの一例について説明するための説明図である。
【図３１】変形例２に係る情報処理システムの一例について説明するための説明図である。
【図３２】同実施形態に係る情報処理装置のハードウェア構成の一例を示した図である。
【発明を実施するための形態】
【００１２】
以下に添付図面を参照しながら、本開示の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００１３】
なお、説明は以下の順序で行うものとする。
１．概要
２．用語の定義
２．１．（ｋ，ｔ）−匿名性
２．２．属性の一般化階層
２．３．一般化戦略
２．４．ハイパーグラフと横断
３．機能構成
４．処理
４．１．属性値の一般化
４．２．（ｋ，ｔ）−匿名性の判定
４．３．元の変換
４．４．極小元の探索
４．５．一連の処理の流れ
５．計算量
６．変形例
６．１．変形例１：一般化戦略の探索に係る処理負荷の軽減
６．２．変形例２：システム構成の一例
７．ハードウェア構成
８．まとめ
【００１４】
＜１．概要＞
まず、図１を参照して、本開示の実施形態に係る情報処理装置１０が適用された情報処理システム１の一例について説明したうえで、本実施形態に係る情報処理装置１０の課題について整理する。図１は、本実施形態に係る情報処理装置１０が適用された情報処理システム１の概略的なシステム構成の一例を示している。
【００１５】
図１に示すように、情報処理システム１は、例えば、各種データが蓄積されたＤＢ（データベース）５０と、ＤＢサーバ７０と、１以上のクライアント８０と、情報処理装置１０と、管理者端末３０と、一般化ＤＢ４０とを含む。なお、情報処理システム１は、一般化ＤＢ４０を参照する解析サーバ６０を含んでもよい。
【００１６】
ＤＢ５０は、所謂リレーショナルデータベースに相当し、複数の属性を含むデータをレコードとして、当該レコードを複数含むテーブルｄ１０を含んで構成される。例えば、図２は、ＤＢ５０に含まれるテーブルｄ１０の構成の一例について説明するための説明図である。なお、図２に示すテーブルｄ１０は、患者の病歴をデータとして管理するためのテーブルｄ１０の一例を示しており、当該患者の年齢、性別、及び病気等の情報を、患者ごとに管理している。
【００１７】
図２において、参照符号ｄ１１は、「属性」を示しており、個々のデータ（後述する「レコード」）が含む特徴を示す項目に相当する。また、参照符号ｄ１３は、「属性値」を示しており、属性ｄ１１の取る具体的な値に相当する。また、参照符号ｄ１５は、「レコード」であり、各属性ｄ１１に対応する属性値ｄ１３それぞれの集合からなる。なお、レコードは、行（row）やタプル（tuble）と呼ばれる場合もある。
【００１８】
また、テーブルｄ１０は、レコードｄ１５の集合である。なお、本説明では、図２に示すように、テーブルｄ１０は、属性ｄ１１ごとの属性値ｄ１３を列としてレコードｄ１５を形成し、当該レコードｄ１５を行方向に配列することで形成されているものとする。即ち、テーブルｄ１０は、各レコードｄ１５を、属性ｄ１１ごとの属性値ｄ１３の列ベクトルとしてリスト化して表現される。
【００１９】
なお、本説明では、本実施形態に係る情報処理装置１０の特徴をよりわかりやすくするために、属性ｄ１１を、識別子ｄ１１１と、準識別子ｄ１１３と、機微属性ｄ１１５とに分類して説明する。
【００２０】
識別子ｄ１１１は、各レコードｄ１５を一意に特定するための属性であり、具体的な一例として、主キー（primary  key）が挙げられる。識別子ｄ１１１の具体的な一例としては、アカウントＩＤやサービスＩＤのような、所謂ＩＤ（identifier）が挙げられる。
【００２１】
機微属性ｄ１１５は、例えば、テーブルｄ１０の特性を決定づけていると考えられる属性に相当する。具体的な一例として、図２に示すように、患者の病歴をデータとして管理するテーブルｄ１０の場合には、患者の「病気」を示す属性ｄ１１は、テーブルｄ１０を特徴づける（当該テーブルｄ１０に特徴的な）属性であり、機微属性ｄ１１５に相当する。
【００２２】
準識別子ｄ１１３は、単体では各レコードｄ１５を識別することが困難ではあるが、他の属性ｄ１１と組み合わせることで、各レコードｄ１５を一意に特定し得る、もしくは、特定のレコードｄ１５を絞り込み得る属性を示している。図２に示す例では、参照符号ｄ１１３ａ及びｄ１１３ｂで示された「年齢」及び「性別」を示す属性は、これらの属性を組み合わせることで、対象となる患者（個人）を絞り込み得ることから、準識別子ｄ１１３に相当する。
【００２３】
ＤＢサーバ７０は、ＤＢ５０を参照または更新するためのサーバである。また、クライアント８０は、ネットワークｎ１を介してＤＢサーバ７０にアクセスすることで、ＤＢ５０内のデータを参照または更新するための端末を示している。
【００２４】
情報処理装置１０は、ＤＢ５０に含まれる各テーブルのうち、少なくとも一部のテーブルｄ１０について、一部の属性ｄ１１の属性値ｄ１３を一般化（抽象化）することで、より匿名性を高めたテーブルｄ３０を生成する。
【００２５】
例えば、図３は、テーブルｄ１０の一部の属性ｄ１１の属性値ｄ１３を一般化（抽象化）することで、より匿名性を高めたテーブルｄ３０を生成する処理の概要について説明するための説明図である。なお、本説明では、情報処理装置１０の処理をわかりやすくするために、図２に示したテーブルｄ１０のように、テーブルｄ１０が所謂ユーザの個人情報を管理するテーブルである場合を例に説明する。また、機微属性ｄ１１５が個人のプライバシに関わる属性ｄ１１を示しており、準識別子ｄ１１３が個人を特定し得る属性ｄ１１であるものとして説明する。
【００２６】
具体的には、図３に示す例では、情報処理装置１０は、テーブルｄ１０における「年齢」及び「性別」を示す属性ｄ１１３ａ及びｄ１１３ｂの属性値を一般化（抽象化）している。
【００２７】
例えば、情報処理装置１０は、年齢を示す属性ｄ１１３ａの属性値ｄ１５を、１０代や２０代のように世代を示す属性値に分類することで、当該属性ｄ１１３ａの属性値ｄ１５を一般化し、年齢を示す属性値の匿名性を高めている。
【００２８】
具体的には、年齢を示す属性ｄ１１３ａの属性値の定義域を｛０，１，・・・，１２５｝、世代の定義域｛１０歳未満，１０代，２０代，・・・，９０代，１００歳以上｝とした場合に、情報処理装置１０は、年齢を示す属性値０〜９を、１０歳未満を示す属性値に対応付ける。同様に、情報処理装置１０は、年齢を示す属性値１０〜１９を、１０代を示す属性値に対応付けることとなる。
【００２９】
即ち、図３に示す例では、情報処理装置１０は、属性ｄ１１３ａの属性値のうち、２０〜２９は、２０代を示す属性値［２０，２９］に対応付け、３０〜３９は、３０代を示す属性値［３０，３９］に対応付けることで、年齢を示す属性値の匿名性を高めている。
【００３０】
同様に、情報処理装置１０は、性別を示す属性ｄ１１３ｂの属性値｛男，女，未登録｝を、性別を示す情報が登録されているか否か（即ち、性別を示す情報の登録状況）を示す属性値｛登録，未登録｝に対応付けている。具体的には、情報処理装置１０は、属性ｄ１１３ｂの属性値のうち、「男」及び「女」は、性別を示す情報が登録されていることを示す属性値「登録」に対応付けることで、性別を示す属性値の匿名性を高めている。
【００３１】
このような一般化に伴い、例えば、「ＩＤ」が「１」〜「２」で示されたレコードや、「ＩＤ」が「３」〜「４」で示されたレコードを、「年齢」及び「性別」の属性に基づき識別することが困難となる。
【００３２】
一方で、「ＩＤ」が「７」で示されたレコードは、「年齢」及び「性別」を示す属性ｄ１１３ａ及びｄ１１３ｂの属性値を一般化しても、４０代であり、かつ、性別の情報が登録されているレコードが他に存在しないため、一意に特定され得る。このことは、「ＩＤ」が「８」で示されたレコードについても同様である。そのため、情報処理装置１０は、属性値が一般化されたテーブルｄ３０のうち、上記に示した一意に特定され得るレコードを、あらかじめ決められたレコード数以下の範囲で削除する。
【００３３】
このような構成により、テーブルｄ３０中のいずれのレコードを抽出し、当該レコードに対応する患者の識別を試みたとしても、対応する患者の可能性を２通り未満に絞り込むことが困難となり、匿名性が担保される。
【００３４】
ここで、図３に示すテーブルｄ１０の例では、悪意のある第三者が「年齢」及び「性別」を基に個人を特定し得る場合には、対象となるレコードを一意に特定し得た。そのため、悪意のある第三者は、「年齢」及び「性別」の情報を基に特定の個人に対応するレコードをテーブルｄ１０中から特定し、当該特定したレコードに基づき、当該個人の「病気」という新たな情報を知り得ることとなる。なお、「年齢」及び「性別」等の既知の情報に基づき、特定の個人に対応するレコードをテーブル中から特定することを、以降では、「再識別」と記載する場合がある。
【００３５】
一方で、テーブルｄ３０に示すように、いずれのレコードを抽出したとしても、当該レコードと「年齢」及び「性別」が重複する他のレコードが存在する場合には、悪意のある第三者は、「年齢」及び「性別」を基に個人を一意に特定することが困難となる。即ち、テーブルｄ３０は、テーブルｄ１０よりも匿名性が高められていることがわかる。
【００３６】
以上のようにして、情報処理装置１０は、テーブルｄ１０について、一部の属性ｄ１１の属性値ｄ１３を一般化（抽象化）することで、より匿名性を高めたテーブルｄ３０を生成する。そして、情報処理装置１０は、生成したテーブルｄ３０を、一般化ＤＢ４０に出力する。一般化ＤＢ４０は、情報処理装置１０により生成されたテーブルｄ３０を管理するための構成である。
【００３７】
なお、本説明では、情報処理システム１の構成をよりわかりやすくするために、ＤＢ５０と一般化ＤＢ４０とを別々の構成として説明しているが、必ずしもこのような構成には限定されない。具体的な一例として、ＤＢ５０と一般化ＤＢ４０とを一つのＤＢとして構成し、当該ＤＢにおいて、テーブルｄ１０と、当該テーブルｄ１０を基に生成されたテーブルｄ３０とを管理してもよい。
【００３８】
また、管理者端末３０は、所謂ＤＢ５０や一般化ＤＢ４０の管理者が、情報処理装置１０を操作するためのインタフェースの一例である。
【００３９】
なお、ＤＢサーバ７０は、一般化ＤＢ４０中の、テーブルｄ３０を参照できるように構成されていてもよい。また、解析サーバ６０は、一般化ＤＢ４０に記憶されたテーブルｄ３０中の情報を、例えば、データマイニング等の技術を利用することで解析し、当該解析の結果を、ネットワークｎ１１を介してクライアント８０に出力してもよい。
【００４０】
以上、図１を参照して、本実施形態に係る情報処理装置１０が適用された情報処理システム１の概略的なシステム構成の一例について説明した。
【００４１】
上記に説明したように、情報処理装置１０は、ＤＢ５０に含まれる少なくとも一部のテーブルｄ１０について、一部の属性ｄ１１の属性値ｄ１３を一般化し、必要に応じて一部のレコードを削除することで、より匿名性を高めたテーブルｄ３０を生成する。
【００４２】
なお、属性値をより一般化するほど、匿名性はより高くなる傾向にある。これに対して、属性値を一般化することで、従前では識別されていた各属性値が、同じ属性値としてまとめられることになるため、個々のレコードを識別するための情報が損なわれ、情報量が減少する。そのため、属性値をより一般化するほど、データの有用性がより損なわれる傾向にある。
【００４３】
また、削除するレコード数の最大値が増大するほど、匿名性をより高くすることが可能となる傾向にある。一方で、レコードの削除が、情報量の減少につながることは言うまでもなく、削除するレコード数が増大すれば、情報量がより減少することとなる。即ち、削除するレコード数の最大値が増大するほど、母集合の範囲がより制限される可能性が高くなり、データの有用性がより損なわれる可能性がある。
【００４４】
このように、匿名性の担保と、データとしての有用性とはトレードオフの関係にある。そのため、所定の条件に基づく匿名性（後述する、（ｋ，ｔ）−匿名性）を満たし、かつ、情報量の減少を最小限に抑えることが可能な、属性値を抽象化するための条件を特定することが望ましい。
【００４５】
その一方で、複数の属性ｄ１１について属性値ｄ１３を一般化することで匿名性を担保する場合には、どの属性ｄ１１についてどこまで一般化すれば（即ち、一般化のレベルをどの程度に設定すれば）、所定の条件に基づく匿名性が担保されるかは、テーブルｄ１０内のデータ（即ち、各レコードｄ１５）に依存する。そのため、所定の条件に基づく匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な、属性値を抽象化するための条件を特定するための計算量を事前に見積もることが困難であった。
【００４６】
また、一般化の対象となる属性ｄ１１の数が増えるほど、複数の属性ｄ１１間における一般化のレベルの組み合わせの数は増大する。このような特性から、所定の条件に基づく匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な、属性値を抽象化するための条件を効率よく導出することが可能な仕組みが求められている。
【００４７】
そこで、本実施形態に係る情報処理装置１０として、所定の条件に基づく匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な、属性値を抽象化するための条件を効率よく導出することが可能な仕組みを提案する。以下に、本実施形態に係る情報処理装置１０について、さらに詳しく説明する。
【００４８】
＜２．用語の定義＞
本実施形態に係る情報処理装置１０の詳細について説明するにあたり、まず、本説明で使用する用語の定義について以下にまとめる。
【００４９】
［２．１．（ｋ，ｔ）−匿名性］
本項では、図４を参照して、匿名性の条件である（ｋ，ｔ）−匿名性について説明する。図４は、（ｋ，ｔ）−匿名性について説明するための説明図である。なお、図４に示す例は、図３と同様に、患者の病歴をデータとして管理するためのテーブルｄ１０を、「年齢」及び「性別」の属性ｄ１１３ａ及びｄ１１３ｂそれぞれの属性値を一般化することで、匿名性を高めたテーブルｄ３０を生成した場合を示している。
【００５０】
図４において、参照符号ｄ３５１〜ｄ３５５は、「年齢」及び「性別」の属性ｄ１１３ａ及びｄ１１３ｂの属性値を一般化した場合に、各属性間の属性値の組み合わせが等しい集合を示している。なお、以降の説明では、この各属性間の属性値の組み合わせが等しい集合を「等価クラス」と記載する場合がある。例えば、等価クラスｄ３５１は、「年齢」を示す属性ｄ３１３ａの属性値が、「２０代」を示す「［２０，２９］」であり、「性別」を示す属性ｄ３１３ｂの属性値が、性別を示す情報が登録されていることを示す「登録」である集合を示している。同様に、等価クラスｄ３５３は、「年齢」を示す属性ｄ３１３ａの属性値が、「３０代」を示す「［３０，３９］」であり、「性別」を示す属性ｄ３１３ｂの属性値が、性別を示す情報が登録されていないことを示す「未登録」である集合を示している。
【００５１】
ここで、テーブル中の任意の等価クラスを抽出した場合に、当該等価クラスのレコード数がいずれの場合においてもｋ以上である場合に、当該テーブルが「ｋ−匿名性（k-Anonymity）」を満たすという。即ち、ｋ−匿名性を満たすテーブルは、当該テーブル中のいずれのレコードに対して再識別が試みられたとしても、再識別の対象の候補をｋ通り未満に絞り込むことが困難である。
【００５２】
また、テーブルがｋ−匿名性を満たさない場合においても、等価クラスのレコード数がｋ未満であるようなレコードを全て削除することで、ｋ−匿名性を満たすことが可能な場合がある。このように、レコード数がｔ以下の範囲でレコードを削除することで、ｋ−匿名性を満たすことが可能な場合を、「（ｋ，ｔ）−匿名性（（k,t）-Anonymity）」を満たすという。
【００５３】
具体的な一例として、図４に示す例において、テーブルｄ１０及びｄ３０が、ｋ＝２、ｔ＝２とした（２，２）−匿名性を満たすか否かについて以下に説明する。
【００５４】
例えば、テーブルｄ１０は、「年齢」を示す属性ｄ１１３ａの属性値がそれぞれ異なる。そのため、例えば、「年齢」が「２９」、「性別」が「女」のレコードに対して再識別を試みた場合には、「ＩＤ」が「２」のレコードが一意に特定される。このことは、他のレコードについても同様である。即ち、テーブルｄ１０は、２−匿名性を満たしてないことがわかる。
【００５５】
また、テーブルｄ１０において、各レコードは、「年齢」及び「性別」の属性ｄ１１３ａ及びｄ１１３ｂに着目した場合に、各属性間の属性値の組み合わせが等しい他のレコードが存在しない。即ち、テーブルｄ１０は、レコード数が２以下の範囲でレコードの削除を行ったとしても、２−匿名性を満たさない。即ち、テーブルｄ１０は、（２，２）−匿名性を満たさないこととなる。
【００５６】
これに対して、テーブルｄ３０は、（２，２）−匿名性を満たしている。具体的には、テーブルｄ３０は、レコード数が２未満の等価クラスｄ３５４及びｄ３５３を含むため、２−匿名性は満たしていない。しかしながら、レコード数が２未満の等価クラスｄ３５４及びｄ３５３に対応するレコードを削除することで、当該レコード削除後のテーブルｄ３０は、２−匿名性を満たす。このとき、等価クラスｄ３５４及びｄ３５３に対応するレコードのレコード数は２（即ち、２以下）であるため、テーブルｄ３０は、（２，２）−匿名性を満たすこととなる。
【００５７】
以上、図４を参照して、匿名性の条件である（ｋ，ｔ）−匿名性について説明した。
【００５８】
［２．２．属性の一般化階層］
次に、図５及び図６を参照して、属性の一般化階層について説明する。図５及び図６は、属性の一般化階層について説明するための説明図である。
【００５９】
ここで、「属性の一般化階層」とは、一の属性について属性値を段階的に一般化した場合に、一般化前の属性値と一般化後の属性値との間の一般化の対応関係を階層構造（所謂、木構造）で示したものである。
【００６０】
例えば、図５は、図２に示したテーブルｄ１０のうち、「年齢」を示す属性ｄ１１３ａの属性値を一般化（抽象化）するための属性の一般化階層の一例を示している。なお、以降では、図５に示す、属性ｄ１１３ａを一般化（抽象化）するための属性の一般化階層、即ち、属性ｄ１１３ａの一般化階層を、「属性の一般化階層ｄ２１」と記載する場合がある。
【００６１】
図５に示す例では、「年齢」を示す属性ｄ１１３ａの属性値ｄ１３を２段階に分けて一般化した場合について示している。図５において、参照符号ｄ２２は、「年齢」を示す属性の属性値ｄ１３を段階的に一般化した場合の、属性の一般化階層ｄ２１における各階層の高さを示している。なお、以降では、各階層の高さを「一般化レベル」と記載する場合がある。
【００６２】
図５において、参照符号ｄ２１０は、「年齢」を示す属性が取り得る一連の属性値、即ち、定義域｛０，１，２，・・・，１２５｝で示された属性値に対応する階層を示している。なお、図５に示す属性の一般化階層ｄ２１では、「年齢」を示す属性が取り得る一連の属性値、即ち、一般化が施されていない属性値の階層ｄ２１０の一般化レベルを「０」に設定している。
【００６３】
また、参照符号ｄ２１１は、階層ｄ２１０で示された「年齢」を示す属性の一連の属性値を一般化することで、「世代」を示す属性値に分類した場合の、当該「世代」を示す属性値に対応する階層を示している。なお、図５に示す例では、「世代」を示す属性値の定義域は、｛１０歳未満，１０代，２０代，・・・，９０代，１００歳以上｝で示される。
【００６４】
また、図５に示す例では、階層ｄ２１０における属性値「０」〜「９」は、階層ｄ２１１における「１０歳未満」を示す属性値「［０，９］」に対応付けられている。即ち、属性の一般化階層ｄ２１は、階層ｄ２１０における属性値「０」〜「９」を、階層ｄ２１１における属性値「［０，９］」に一般化することを示している。同様にして、階層ｄ２１０における属性値「１０」〜「１９」は、階層ｄ２１１における「１０代」を示す属性値「［１０，１９］」に一般化されることとなる。なお、図５に示す属性の一般化階層ｄ２１では、階層ｄ２１１の一般化レベルを「１」に設定している。
【００６５】
また、参照符号ｄ２１２は、階層ｄ２１１で示された「世代」を示す属性値を、さらに一般化した属性値に分類した場合の、当該属性値に対応する階層を示している。なお、図５に示した属性の一般化階層ｄ２１では、階層ｄ２１２は、各年齢を識別しない場合の属性値を示しており、定義域は｛［０，１２５］｝となる。即ち、階層ｄ２１１の属性値を階層ｄ２１２の属性値に一般化すると、階層ｄ２１１の属性値はいずれも、階層ｄ２１２の属性値「［０，１２５］」に一般化されることとなる。なお、図５に示す属性の一般化階層ｄ２１では、階層ｄ２１２の一般化レベルを「２」に設定している。
【００６６】
このように、属性の一般化階層ｄ２１は、より一般化されるほど階層の高さが高くなるように（即ち、一般化レベルが高くなるように）構成される。
【００６７】
同様に、図６は、図２に示したテーブルｄ１０のうち、「性別」を示す属性ｄ１１３ｂの属性値を一般化（抽象化）するための属性の一般化階層の一例を示している。なお、以降では、図５に示す、属性ｄ１１３ｂを一般化（抽象化）するための属性の一般化階層、即ち、属性ｄ１１３ｂの一般化階層を、「属性の一般化階層ｄ２３」と記載する場合がある。
【００６８】
図６に示す例では、「性別」を示す属性ｄ１１３ｂの属性値ｄ１３を２段階に分けて一般化した場合について示している。図６において、参照符号ｄ２４は、「性別」を示す属性の属性値ｄ１３を段階的に一般化した場合の、属性の一般化階層ｄ２３における各階層の高さ（即ち、一般化レベル）を示している。
【００６９】
図６において、参照符号ｄ２３０は、「性別」を示す属性が取り得る一連の属性値、即ち、定義域｛男，女，未登録｝で示された属性値に対応する階層を示している。なお、図６に示す属性の一般化階層ｄ２３では、「性別」を示す属性が取り得る一連の属性値、即ち、一般化が施されていない属性値の階層ｄ２３０の一般化レベルを「０」に設定している。
【００７０】
また、参照符号ｄ２３１は、階層ｄ２３０で示された「性別」を示す属性の一連の属性値を一般化することで、「性別を示す情報の登録状況」を示す属性値に分類した場合の、当該属性値に対応する階層を示している。なお、図５に示す例では、「性別を示す情報の登録状況」を示す属性値の定義域は、｛登録，未登録｝で示される。
【００７１】
また、図６に示す例では、階層ｄ２１０における属性値「男」及び「女」は、階層ｄ２３１において「性別を示す情報が登録されている」ことを示す属性値「登録」に対応付けられている。即ち、属性の一般化階層ｄ２３は、階層ｄ２３０における属性値「男」及び「女」を、階層ｄ２３１における属性値「登録」に一般化することを示している。同様にして、階層ｄ２３０における属性値「未登録」は、階層ｄ２３１において「性別を示す情報が登録されていない」ことを示す属性値「未登録」に対応付けられている。なお、図６に示す属性の一般化階層ｄ２３では、階層ｄ２３１の一般化レベルを「１」に設定している。
【００７２】
また、参照符号ｄ２３２は、階層ｄ２３１で示された「性別を示す情報の登録状況」を示す属性値を、さらに一般化した属性値に分類した場合の、当該属性値に対応する階層を示している。なお、図６に示した属性の一般化階層ｄ２３では、階層ｄ２３２は、性別を識別しない場合の属性値を示しており、定義域を｛不明｝とすることで、各患者の性別が不明であるものと取扱った場合を示している。即ち、階層ｄ２３１の属性値を階層ｄ２３２の属性値に一般化すると、階層ｄ２３１の属性値はいずれも、階層ｄ２３２の属性値「不明」に一般化されることとなる。なお、図６に示す属性の一般化階層ｄ２３では、階層ｄ２３２の一般化レベルを「２」に設定している。
【００７３】
なお、属性の一般化階層ｄ２３は、図５を参照して説明した属性の一般化階層ｄ２１と同様に、より一般化されるほど階層の高さが高くなるように（即ち、一般化レベルが高くなるように）構成される。
【００７４】
以上、図５及び図６を参照して、属性の一般化階層について説明した。
【００７５】
［２．３．一般化戦略］
次に、テーブルｄ１０を一般化するための一般化戦略の一例について説明する。図５及び図６を参照して説明したように、複数の属性それぞれについて一般化階層が与えられている場合には、各属性に対してどの高さまで一般化を行うかの違い（即ち、各属性の一般化階層の高さの組み合わせ）により、一般化の方法が複数存在することとなる。
【００７６】
例えば、図５及び図６に示す例では、「年齢」を示す属性ｄ１１３ａの一般化階層の高さは０（年齢）、１（世代）、２（区別なし）であり、「性別」を示す属性ｄ１１３ｂの一般化階層の高さは０（性別）、１（登録状況）、２（不明（区別なし））である。ここで、「年齢」を示す属性ｄ１１３ａの一般化階層の高さをｖ１、「性別」を示す属性ｄ１１３ｂの一般化階層の高さをｖ２とした場合に、［ｖ１，ｖ２］の組み合わせは、［０，０］、［０，１］、・・・、［２，１］、［２，２］となる。このように、一般化の対象となる各属性の一般化階層の高さの組み合わせを、本説明では「一般化戦略（Generalization  Strategy）」と記載する場合がある。
【００７７】
例えば、一般化戦略［１，２］を適用した場合には、「年齢」を示す属性ｄ１１３ａの属性値は、高さが「１」の「世代」を示す属性値に一般化され、「性別」を示す属性ｄ１１３ｂの属性値は、高さが「２」の「不明（区別なし）」を示す属性値に一般化される。このように、各一般化戦略は、テーブルｄ１０における「年齢」及び「性別」を示す属性ｄ１１３ａ及びｄ１１３ｂそれぞれの属性値を一般化するための指標を示している。
【００７８】
ここで、ある一般化戦略ａと、当該一般化戦略ａの各要素のうちいずれか一つの要素（即ち、いずれか一つの属性の一般化階層の高さ）を１だけ増加させた（即ち、一階層分だけ一般化した）一般化戦略ｂの大小関係を、ａ＜ｂとする。具体的な一例として、一般化戦略［１，１］と［１，２］とは、［１，１］＜［１，２］の関係にある。同様に、一般化戦略［１，２］と［２，２］とは、［１，２］＜［２，２］の関係にある。一方で、一般化戦略［１，２］と［２，１］との間には、大小関係は定義されない。このような大小関係を順序関係として規定し、一連の一般化戦略［ｖ１，ｖ２］＝［０，０］、［０，１］、・・・、［２，１］、［２，２］を元とすることで、一般化戦略［ｖ１，ｖ２］は束（Lattice）をなす。この束を、以降では「一般化戦略からなる束」と呼ぶ場合がある。
【００７９】
例えば、図７は、一般化戦略からなる束について説明するための説明図である。図７は、図５及び図６に示した、「年齢」及び「性別」を示す属性ｄ１１３ａ及びｄ１１３ｂそれぞれの一般化階層に基づき規定される一般化戦略［ｖ１，ｖ２］を元とした、一般化戦略からなる束の一例を示している。
【００８０】
また、本説明では、半順序関係が定義されている束＜Ｌ，≦＞に対して、以下に（条件１）及び（条件２）で示す性質を満たす関数ｑを、束＜Ｌ，≦＞のクエリ関数と呼ぶ。
（条件１）ｑ：Ｌ→{０，１}；束の台集合を定義域とするブール値への写像
（条件２）任意のａ，ｂ∈Ｌに対して、ａ≦（≧）ｂならばｑ（ａ）≦（≧）ｑ（ｂ）
【００８１】
また、半順序が定義された束＜Ｌ，≦＞と、上述したクエリ関数ｑとが与えられている場合に、以下に示す（条件３）及び（条件４）を満たす元（即ち、一般化戦略）ａ＝［ｖ１，ｖ２］を、極小元と呼ぶ。
（条件３）ｑ（ａ）＝１
（条件４）任意のａ＞ｂ∈Ｌに対してｑ（ｂ）＝０
【００８２】
例えば、図７に示す例では、一般化戦略［２，２］、［２，１］、［１，２］、［１，１］、［２，０］が、クエリ関数ｑに基づき、ｑ（（ｖ１，ｖ２））＝１を満たす。また、一般化戦略［０，２］、［０，１］、［１，０］、［０，０］が、クエリ関数ｑに基づき、ｑ（（ｖ１，ｖ２））＝０を満たす。このとき、参照符号ｄ５０は、ｑ（（ｖ１，ｖ２））＝１を満たす元（即ち、一般化戦略）と、ｑ（（ｖ１，ｖ２））＝０を満たす元の境界を示しており、元［１，１］及び［２，０］が極小元となる。
【００８３】
以上、図７を参照して、テーブルｄ１０を一般化するための一般化戦略の一例と、当該一般化戦略からなる束の一例とについて説明した。
【００８４】
［２．４．ハイパーグラフと横断］
次に、図８及び図９を参照して、ハイパーグラフ及び横断について説明する。図８及び図９は、ハイパーグラフ及び横断について説明するための説明図である。
【００８５】
ハイパーグラフについて説明するにあたり、まず、図８を参照して、頂点の集合Ｖと、集合Ｖ中の２つ頂点を結ぶエッジＥからなるグラフ（Ｖ，Ｅ）について説明する。例えば、図８に示す例は、Ｖ＝｛１，２，３，４，５｝、Ｅ＝｛｛１，４｝，｛１，５｝，｛２，３｝，｛２，４｝，｛４，５｝｝となるグラフ（Ｖ，Ｅ）を示している。ここで、例えば、エッジＥ＝｛１，４｝は、頂点「１」と頂点「４」とを結ぶエッジを示している。同様に、エッジＥ＝｛２，３｝は、頂点「２」と頂点「３」とを結ぶエッジを示している。
【００８６】
これに対して、図８に示すグラフ（Ｖ，Ｅ）のエッジＥを、２つ以上の頂点を結ぶハイパーエッジＨに一般化したグラフを、ハイパーグラフ（Ｖ，Ｈ）と呼ぶ。図９は、ハイパーグラフ（Ｖ，Ｈ）の一例を示している。例えば、図９に示す例は、Ｖ＝｛１，２，３，４，５｝、Ｈ＝｛｛１，２，４｝，｛１，５｝，｛２，３，５｝，｛１，４，５｝｝となるハイパーグラフ（Ｖ，Ｈ）を示している。ここで、例えば、ハイパーエッジＨ＝｛１，２，４｝は、頂点「１」、頂点「２」、及び頂点「４」を結ぶハイパーエッジを示している。同様に、ハイパーエッジＨ＝｛１，５｝は、頂点「１」及び頂点「５」を結ぶハイパーエッジを示している。
【００８７】
次に、図９を参照して、横断について説明する。ハイパーグラフ（Ｖ，Ｈ）の任意のハイパーエッジと少なくとも一部を共有するＶの部分集合を「横断」と呼ぶ。また、横断のうち、いずれの要素を取り除いても横断とならなくなるものを「極小横断」と呼ぶ。
【００８８】
例えば、図９に示す例では、Ｖの部分集合｛１，２，４｝は、ハイパーエッジＨ＝｛｛１，２，４｝，｛１，５｝，｛２，３，５｝，｛１，４，５｝｝のいずれとも一部を共有するため、横断に相当する。また、部分集合｛１，２，４｝から、要素「４」を取り除いた部分集合｛１，２｝は、ハイパーエッジＨ＝｛｛１，２，４｝，｛１，５｝，｛２，３，５｝，｛１，４，５｝｝のいずれとも一部を共有する。このことから、部分集合｛１，２，４｝は、極小横断ではないことがわかる。
【００８９】
また、Ｖの部分集合｛１，２｝は、前述通り横断に相当するが、要素「１」及び「２」のいずれかを取り除くと、ハイパーエッジＨ＝｛｛１，２，４｝，｛１，５｝，｛２，３，５｝，｛１，４，５｝｝の少なくともいずれかと一部を共有しない状態となる。このことから、部分集合｛１，２｝は、極小横断に相当する。同様に、Ｖの部分集合｛１，５｝も、極小横断となる。
【００９０】
以上、図８及び図９を参照して、ハイパーグラフ及び横断について説明した。
【００９１】
＜３．機能構成＞
次に、図１０を参照して、本実施形態に係る情報処理装置１０の機能構成の一例について説明する。図１０は、本実施形態に係る情報処理装置１０の機能構成の一例について説明するための説明図である。
【００９２】
図１０に示すように、情報処理装置１０は、ＤＢ情報取得部１１と、ＤＢ情報出力部１２と、階層情報取得部１３と、解析部１４と、解析結果出力部１５と、一般化条件取得部１６と、ＤＢ情報変換部１７と、変換結果出力部１８とを含む。
【００９３】
ＤＢ情報取得部１１は、ＤＢ５０に含まれるテーブルのうち、処理対象となるテーブルｄ１０の情報（即ち、属性の定義情報や、各レコード等の、テーブルを形成するデータ）を、当該ＤＢ５０から取得する。なお、処理対象となるテーブルｄ１０とは、一部の属性の属性値を一般化（抽象化）することで、より匿名性を高めたテーブルｄ３０を生成するための入力情報となるテーブルを示している。ＤＢ情報取得部１１は、取得したテーブルｄ１０の情報を、ＤＢ情報出力部１２、解析部１４、及びＤＢ情報変換部１７のそれぞれに出力する。なお、ＤＢ情報取得部１１は、取得したテーブルｄ１０の情報を、図示しない記憶部に保持または記憶させることで、当該テーブルの情報を、当該記憶部を介して間接的に、ＤＢ情報出力部１２、解析部１４、及びＤＢ情報変換部１７のそれぞれに出力してもよい。
【００９４】
ＤＢ情報出力部１２は、ＤＢ情報取得部１１から処理対象となるテーブルｄ１０の情報を取得し、取得したテーブルｄ１０の情報を、管理者端末３０を介して管理者に提示する。これにより、管理者は、テーブルｄ１０のうち、属性値の一般化（抽象化）の対象となる属性や、当該属性の属性値を一般化（抽象化）するための属性の一般化階層を定義することが可能となる。
【００９５】
階層情報取得部１３は、処理対象となるテーブルｄ１０の各属性のうち、管理者端末３０を介して管理者より指定された、属性値の一般化（抽象化）の対象となる属性を示す情報と、当該属性それぞれの一般化階層を示す情報とを、当該管理者端末３０から取得する。そして、階層情報取得部１３は、取得した属性値の一般化（抽象化）の対象となる属性を示す情報と、当該属性それぞれの一般化階層を示す情報とを、解析部１４に出力する。
【００９６】
また、階層情報取得部１３は、管理者端末３０を介して管理者より指定された匿名性の条件を示す情報を、当該管理者端末３０から取得してもよい。なお、匿名性の条件を示す情報とは、例えば、（ｋ，ｔ）−匿名性の条件である、ｋ−匿名性を満たすための等価クラスに含まれるレコードのレコード数の閾値ｋと、削除するレコードのレコード数の最大値ｔとに相当する。そして、階層情報取得部１３は、管理者端末３０から取得した匿名性の条件を示す情報を、解析部１４に出力する。
【００９７】
なお、匿名性の条件を示す情報の取得元は、必ずしも管理者端末３０には限定されない。具体的な一例として、階層情報取得部１３は、情報処理装置１０内の記憶部（図示しない）にあらかじめ記憶された、匿名性の条件を示す情報を取得し、取得した当該情報を解析部１４に出力してもよい。
【００９８】
解析部１４は、ＤＢ情報取得部１１から処理対象となるテーブルｄ１０の情報を取得する。また、解析部１４は、階層情報取得部１３から、処理対象となるテーブルｄ１０の各属性のうち、属性値の一般化（抽象化）の対象となる属性を示す情報と、当該属性それぞれの一般化階層を示す情報とを取得する。また、解析部１４は、階層情報取得部１３から、匿名性の条件を示す情報を取得する。
【００９９】
解析部１４は、取得した属性値の一般化（抽象化）の対象となる属性を示す情報と、当該属性それぞれの一般化階層を示す情報とに基づき、テーブルｄ１０を、より匿名性を高めたテーブルｄ３０に変換するための一般化戦略（即ち、各属性の一般化階層の高さの組み合わせ）を規定する。なお、これにより規定される一般化戦略は、対象となる属性それぞれの属性値がより一般化（抽象化）されるように区分するための各分類の、当該対象となる属性間における組み合わせに相当する。そして、解析部１４は、既定した各一般化戦略のうち、取得した匿名性の条件を満たし、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略を抽出する。
【０１００】
そこで、上述した解析部１４の構成及び動作を、以下に詳しく説明する。図１０に示すように、解析部１４は、解析データ生成部１４１と、極小元探索部１４３と、基準点導出部１４５とを含む。
【０１０１】
解析データ生成部１４１は、属性値の一般化（抽象化）の対象となる属性それぞれの一般化階層を示す情報に基づき、各属性の一般化階層の高さの組み合わせを抽出し、抽出した各組み合わせを一般化戦略として規定する。
【０１０２】
そして、解析データ生成部１４１は、既定した各一般化戦略を元として、各一般化戦略が要素として有する各属性の一般化階層の高さをより一般化（抽象化）する順序関係（換言すると、各属性の分類をより抽象化する順序関係）に基づき、一般化戦略からなる束を規定する。このとき、解析データ生成部１４１は、例えば、ある一般化戦略ａと、当該一般化戦略ａの各要素のうちいずれか一つの要素を１だけ増加させた（即ち、一階層分だけ一般化した）一般化戦略ｂの大小関係をａ＜ｂとする順序関係に基づき、一般化戦略からなる束を規定する。
【０１０３】
具体的な一例として、解析データ生成部１４１は、図５及び図６に示した「年齢」及び「性別」のそれぞれに対応する属性の一般化階層から、図７に示した一般化戦略からなる束を規定することとなる。なお、以降では、一般化戦略からなる束における元を、特に「一般化ノード」と記載する場合がある。また、以降では、図５及び図６に示した属性の一般化階層と、図７に示した一般化戦略からなる束を対象として処理する場合を例に説明する。
【０１０４】
なお、一般化戦略からなる束が「第１の束」の一例に相当する。また、一般化戦略からなる束における各元、即ち、各属性の一般化階層の高さの組み合わせに基づき規定される一般化戦略が、「第１の元」の一例に相当する。
【０１０５】
極小元探索部１４３は、既定された一般化戦略からなる束における各一般化ノードのうち、取得した匿名性の条件（即ち、（ｋ，ｔ）−匿名性）を満たすことが可能な一般化戦略に対応する極小元を探索する。なお、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略とは、当該一般化戦略に基づきテーブルｄ１０を一般化（抽象化）した場合に、一般化後のテーブルｄ３０が、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略を示すものとする。
【０１０６】
具体的には、極小元探索部１４３は、既定された一般化戦略からなる束における一般化ノードに対応する一般化戦略が、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略か否かを判定する処理を、クエリ関数ｑとして規定している。なお、以降では、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略に対応する元（即ち、一般化ノード）を、単に「（ｋ，ｔ）−匿名性を満たす元」と記載する場合がある。
【０１０７】
そして、極小元探索部１４３は、既定された一般化戦略からなる束において、（ｋ，ｔ）−匿名性を満たすいずれかの元（一般化ノード）を基準点として、当該元の各要素のうち少なくともいずれかをより具体化する方向に向けて、（ｋ，ｔ）−匿名性を満たす極小元を探索する。
【０１０８】
具体的には、極小元探索部１４３は、（ｋ，ｔ）−匿名性を満たすことが確認された元の各要素（即ち、一般化階層の高さ）のうち、いずれかの要素をより具体化する方向にシフトさせ、当該シフト後の元が（ｋ，ｔ）−匿名性を満たす元か否かを判定する。そして、極小元探索部１４３は、シフト後の元が（ｋ，ｔ）−匿名性を満たす場合には、いずれかの要素をさらに具体化する方向にシフトさせ、シフト後の元が（ｋ，ｔ）−匿名性を満たさない場合には、いずれかの要素を一般化（抽象化）する方向にシフトさせる。このように、極小元探索部１４３は、いずれかの要素をシフトさせ、シフト後の元が（ｋ，ｔ）−匿名性を満たす元か否かを判定する処理を逐次実行することで、（ｋ，ｔ）−匿名性を満たす極小元を探索する。
【０１０９】
なお、極小元探索部１４３が、（ｋ，ｔ）−匿名性を満たす極小元を探索できれば、その探索方法は、特に限定されない。具体的な一例として、極小元探索部１４３は、所謂二分探索に基づき、（ｋ，ｔ）−匿名性を満たす極小元を探索してもよい。
【０１１０】
また、各属性それぞれの属性値を最も一般化（抽象化）する分類（一般化階層）の組み合わせを示す一般化戦略は、（ｋ，ｔ）−匿名性を満たし得る。そのため、当該一般化戦略に対応する一般化ノードは、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の基準点となり得る。具体的な一例として、図５及び図６に示した「年齢」及び「性別」のそれぞれに対応する属性の一般化階層の高さを、それぞれ「２」に設定した場合の一般化戦略に対応する一般化ノード（即ち、図７において（２，２）で示された一般化ノード）は、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の基準点となり得る。
【０１１１】
以上のように、極小元探索部１４３は、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索し、探索された極小元の情報を保持する。また、極小元探索部１４３は、（ｋ，ｔ）−匿名性を満たす極小元の探索結果を基準点導出部１４５に通知する。
【０１１２】
基準点導出部１４５は、極小元探索部１４３から、（ｋ，ｔ）−匿名性を満たす極小元の探索結果を取得する。基準点導出部１４５は、取得した当該極小元の探索結果に基づき、既定された一般化戦略からなる束において、極小元探索部１４３による探索がなされていない一般化ノードのうち、（ｋ，ｔ）−匿名性を満たす一般化ノードを導出し、導出した一般化ノードを新たな基準点の候補として、極小元探索部１４３に出力する。
【０１１３】
この新たな基準点の候補の出力を受けて、極小元探索部１４３は、当該候補を基準点として新たに（ｋ，ｔ）−匿名性を満たす極小元を探索するとともに、当該探索結果を基準点導出部１４５に出力する。
【０１１４】
なお、極小元探索部１４３が（ｋ，ｔ）−匿名性を満たす極小元を探索する処理と、当該探索結果に基づき、基準点導出部１４５が新たな基準点の候補を導出する処理との詳細については、別途後述する。
【０１１５】
以上のようにして、極小元探索部１４３は、基準点導出部１４５と相互に連携して動作し、基準点導出部１４５により新たな基準点の候補が抽出されなくなるまで、（ｋ，ｔ）−匿名性を満たす極小元を探索して保持する。そして、極小元探索部１４３は、保持された一連の極小元（即ち、探索された一連の（ｋ，ｔ）−匿名性を満たす極小元）それぞれに対応する一般化戦略を、解析結果出力部１５に出力する。
【０１１６】
解析結果出力部１５は、極小元探索部１４３により探索された一連の極小元それぞれに対応する一般化戦略を、当該極小元探索部１４３から取得する。そして、解析結果出力部１５は、取得した一連の一般化戦略を、（ｋ，ｔ）−匿名性を満たすようにテーブルｄ１０を一般化（抽象化）するための条件（即ち、一般化戦略）の候補として、管理者端末３０を介して管理者に提示する。なお、このとき提示される条件、即ち、探索された一連の極小元それぞれに対応する一般化戦略が、あらかじめ指定された（ｋ，ｔ）−匿名性を満たすようにテーブルｄ１０を一般化し、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略に相当する。
【０１１７】
一般化条件取得部１６は、解析部１４により規定された一連の一般化戦略のうち、管理者端末３０を介して管理者に指定された一般化戦略に基づき、テーブルｄ１０を一般化（抽象化）するための条件を、当該管理者端末３０から取得する。なお、テーブルｄ１０を一般化（抽象化）するための条件とは、管理者により指定された一般化戦略に基づき、各属性の属性値を一般化（抽象化）するための分類を示す情報や、（ｋ，ｔ）−匿名性の条件を示す情報に相当する。なお、以降では、テーブルｄ１０を一般化（抽象化）するための条件を、「テーブルｄ１０の一般化条件」と記載する場合がある。
【０１１８】
そして、一般化条件取得部１６は、取得したテーブルｄ１０の一般化条件を示す情報を、ＤＢ情報変換部１７に出力する。
【０１１９】
ＤＢ情報変換部１７は、ＤＢ情報取得部１１から、処理対象となるテーブルｄ１０の情報を取得する。また、ＤＢ情報変換部１７は、ＤＢ情報変換部１７から、テーブルｄ１０の一般化条件を示す情報を取得する。
【０１２０】
ＤＢ情報変換部１７は、テーブルｄ１０の一般化条件を示す情報に基づき、テーブルｄ１０の中の対象となる属性の属性値を一般化することで、当該テーブルｄ１０の情報を、より匿名性を高めたテーブルｄ３０の情報に変換する。
【０１２１】
具体的には、ＤＢ情報変換部１７は、一般化の対象となる属性の属性値を、テーブルｄ１０の一般化条件として指定された分類中の属性値に対応付けることで、当該属性の属性値を一般化する。例えば、ＤＢ情報変換部１７は、年齢を示す属性の属性値を、世代を示す属性値に対応付けることで、当該年齢を示す属性の属性値を抽象化する。
【０１２２】
また、ＤＢ情報変換部１７は、テーブルｄ１０の一般化条件として指定された（ｋ，ｔ）−匿名性の条件に基づき、属性値が抽象化されたテーブルｄ１０から、等価クラスのレコード数がｋ未満であるようなレコードを、レコード数がｔ以下の範囲で削除する。以上のようにして、ＤＢ情報変換部１７は、テーブルｄ１０の情報を、より匿名性を高めたテーブルｄ３０の情報に変換する。
【０１２３】
そして、ＤＢ情報変換部１７は、テーブルｄ１０の情報を変換することで生成されたテーブルｄ３０の情報を、変換結果出力部１８を介して一般化ＤＢ４０に出力する。変換結果出力部１８は、ＤＢ情報変換部１７により生成されたテーブルｄ３０の情報を、一般化ＤＢ４０に出力するためのインタフェースに相当する。
【０１２４】
以上、図１０を参照して、本実施形態に係る情報処理装置１０の機能構成の一例について説明した。
【０１２５】
＜４．処理＞
次に、情報処理装置１０の一連の処理の流れについて、特に、解析部１４の処理、即ち、処理対象となるテーブルｄ１０を一般化（抽象化）するための一般化戦略の候補を導出する処理に着目して、さらに詳しく説明する。なお、本説明では、解析部１４の処理として、まず、「属性値の一般化」、「（ｋ，ｔ）−匿名性の判定」、「元の変換」、及び「極小元の探索」に係る各部分処理について説明し、その後に、「一連の処理の流れ（即ち、全体的な処理の流れ）」について説明する。
【０１２６】
［４．１．属性値の一般化］
まず、図１１を参照して、テーブルｄ１０の各レコードのうち、対象となる属性の属性値を、入力として指定された一般化戦略と、当該属性の一般化階層とに基づき一般化する処理の一例について説明する。図１１は、対象となる属性の属性値を一般化する処理の一例について説明するための説明図であり、同処理のアルゴリズムを所謂プログラムコードの形式で模式的に提示した図である。なお、図１１に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。
【０１２７】
図１１に示した「getFrequentSets」関数は、入力として、変数ｖ＝（ｖ１，ｖ２，・・・，ｖｎ）で示された一般化戦略（即ち、一般化ノード）と、変数Ｔで示された処理対象となるテーブルｄ１０と、変数（Ｈ１，Ｈ２，・・・，Ｈｎ）で示された各属性の一般化階層を示す情報とを取得する。
【０１２８】
なお、（ｖ１，ｖ２，・・・，ｖｎ）のそれぞれは、互いに異なる属性に対応しており、各属性について指定された一般化階層の高さ（換言すると、当該属性の属性値を、一般化するための分類）をそれぞれ示している。同様に、（Ｈ１，Ｈ２，・・・，Ｈｎ）は、互いに異なる属性に対応しており、各属性の一般化階層をそれぞれ示している。例えば、Ｈｉ（ｖｉ）は、i番目の属性の一般化階層のうち、高さがｖｉに対応する階層（分類）を示している。
【０１２９】
具体的には、図１１に示した「getFrequentSets」関数は、入力として取得したテーブルＴの各レコードｒそれぞれを、等価クラスに割り当てる。このとき、同関数は、レコードｒの各属性の属性値をｒｉとした場合に、当該属性の一般化階層における高さｖｉの属性（分類）に一般化した場合の値ｄｉに置き換えることで、各レコードｒを割り当てるべき等価クラスを特定している。
【０１３０】
より具体的には、「getFrequentSets」関数は、テーブルＴ中の各レコードｒについて、任意の高さｖｉについて、属性値ｒｉ∈ｄｉ∈Ｈｉ（ｖｉ）を満足する値の組み合わせｄ＝（ｄ１，ｄ２，・・・，ｄｎ）を特定する。そして、同関数は、特定した値の組み合わせｄに応じて、各レコードｒを、当該値の組み合わせｄに対応する等価クラスに割り当てる。以上のようにして、同関数は、各レコードｒが割り当てられた等価クラスの集合Ｆ’を生成し、生成した集合Ｆ’を出力する。
【０１３１】
例えば、図１２は、対象となる属性の属性値を、入力として指定された一般化戦略と、当該属性の一般化階層とに基づき一般化する処理の処理結果の一例を示している。図１２に示す例は、図２に示したテーブルｄ１０の「年齢」及び「性別」を示す属性ｄ１１３ａ及びｄ１１３ｂそれぞれの属性値を一般化した場合の一例を示している。なお、図１２に示す例では、属性ｄ１１３ａ及びｄ１１３ｂそれぞれの属性値を一般化するために、図５及び図６に示した属性の一般化階層を使用し、各一般化階層の高さを「１」とした一般化ノード（１，１）に基づき、各属性値を一般化している。
【０１３２】
即ち、図１２に示す例の場合には、「getFrequentSets」関数は、テーブルｄ１０の各レコードが割り当てられた等価クラスｄ３５１〜ｄ３５５を、集合Ｆ’として出力することとなる。
【０１３３】
以上、図１１及び図１２を参照して、テーブルｄ１０の各レコードのうち、対象となる属性の属性値を、入力として指定された一般化戦略と、当該属性の一般化階層とに基づき一般化する処理の一例について説明した。
【０１３４】
［４．２．（ｋ，ｔ）−匿名性の判定］
次に、図１３を参照して、所望の一般化戦略が、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略か否かを判定する処理の一例について説明する。図１３は、所望の一般化戦略が、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略か否かを判定する処理の一例について説明するための説明図であり、同処理のアルゴリズムを所謂プログラムコードの形式で模式的に提示した図である。なお、図１３に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。
【０１３５】
図１３に示した「kAnonymityCheck」関数は、入力として、変数ｖ＝（ｖ１，ｖ２，・・・，ｖｎ）で示された一般化戦略（即ち、一般化ノード）と、（ｋ，ｔ）−匿名性の閾値（即ち、ｋ及びｔ）と、変数Ｔで示された処理対象となるテーブルｄ１０と、変数（Ｈ１，Ｈ２，・・・，Ｈｎ）で示された各属性の一般化階層を示す情報とを取得する。なお、（ｖ１，ｖ２，・・・，ｖｎ）及び（Ｈ１，Ｈ２，・・・，Ｈｎ）の定義は、図１１を参照して前述した、属性値を一般化するための「getFrequentSets」関数の場合と同様である。
【０１３６】
具体的には、図１３に示した「kAnonymityCheck」関数は、入力として取得したテーブルＴの各レコードｒを、入力として取得した一般化戦略ｖに基づき、等価クラスに割り当てる。なお、各レコードｒを等価クラスに割り当てる処理は、図１１に基づき前述した「getFrequentSets」関数に相当する。
【０１３７】
また、「kAnonymityCheck」関数は、各レコードｒが割り当てられた各等価クラスについて、レコード数が入力として取得した閾値ｋ以上か否かを判定し、レコード数がｋ未満となる等価クラスのサイズ(等価クラスの元の数)cを計上する。そして、同関数は、計上されたレコード数がｋ未満となる等価クラスのサイズｃが、入力として取得した閾値ｔ以下の場合には「真（True）」を出力し、閾値ｔを超える場合には「偽（False）」を出力する。
【０１３８】
以上、図１３を参照して、所望の一般化戦略が、（ｋ，ｔ）−匿名性を満たすことが可能な一般化戦略か否かを判定する処理の一例について説明した。
【０１３９】
［４．３．元の変換］
前述したように、情報処理装置１０の基準点導出部１４５は、一般化戦略からなる束から、極小元探索部１４３が探索した（ｋ，ｔ）−匿名性を満たす極小元の探索結果を基に、（ｋ，ｔ）−匿名性を満たす一般化ノードを、新たな基準点の候補として特定する。このとき、基準点導出部１４５は、各属性の属性値を一般化する分類の数（換言すると、各属性の一般化階層の高さ）に基づき離散集合から誘導される束を規定し、一般化戦略からなる束と当該離散集合から誘導される束との間で元を変換することで、新たな基準点の候補を特定する。
【０１４０】
そこで、本項では、まず、図１４を参照して、各属性の属性値を一般化する分類の数に基づく離散集合から誘導される束について説明し、その後、図１４〜図１７を参照して、元の変換に係る処理の一例について説明する。なお、以降では、各属性の属性値を一般化する分類の数に基づく離散集合から誘導される束を、単に、「離散集合から誘導される束」と記載する場合がある。
【０１４１】
なお、離散集合から誘導される束とは、有限集合［ｎ］：＝｛１，２，・・・，ｎ｝の冪集合をＢ（［ｎ］）とした場合に、冪集合B([n])の各元の包含関係を半順序関係として規定される束＜Ｂ（［ｎ］），⊆＞に相当する。
【０１４２】
例えば、図１４は、一般化戦略からなる束と離散集合から誘導される束との間の対応関係の一例について示した図であり、各束の間での元の対応関係を示している。なお、図１４に示す例では、図５及び図６に示した属性の一般化階層に基づく一般化戦略からなる束（図７参照）を適用した場合の一例を示している。
【０１４３】
図１４に示す例では、各属性の属性値を一般化する分類（換言すると、各属性の一般化階層のうち、属性値そのものを示す高さ「０」の階層を除いたもの）の数に基づき規定される有限集合（離散集合）の各部分集合を元として、当該部分集合間の包含関係を順序関係とすることで、離散集合から誘導される束が規定されている。具体的には、各属性の属性値を一般化する分類の数の和を最大とする正の整数の集合の各部分集合を元として、当該部分集合間の間の包含関係を順序関係とすることで、離散集合から誘導される束が規定されている。
【０１４４】
なお、図１４に示す例では、離散集合から誘導される束の正の整数の有限集合｛１，２，３，４｝のうち、要素「１」及び「２」に基づく有限集合｛１，２｝の部分集合により、図５に示した年齢を示す属性の高さ「０」〜「２」で示された各分類（即ち、一般化階層）を示している。
【０１４５】
具体的には、年齢を示す属性の一般化階層おける高さ「０」の分類（即ち、属性値そのもの）は、離散集合から誘導される束において、正の整数の部分集合｛１，２｝で示される。また、年齢を示す属性の一般化階層おける高さ「１」の分類は、離散集合から誘導される束において、正の整数の部分集合｛１｝で示される。また、年齢を示す属性の一般化階層おける高さ「２」の分類は、離散集合から誘導される束において、正の整数の部分集合｛｝（即ち、空集合）で示される。
【０１４６】
同様に、図１４に示す例では、離散集合から誘導される束の正の整数の有限集合｛１，２，３，４｝のうち、要素「３」及び「４」に基づく有限集合｛３，４｝の部分集合により、図６に示した性別を示す属性の高さ「０」〜「２」で示された各分類（即ち、一般化階層）を示している。
【０１４７】
具体的には、性別を示す属性の一般化階層おける高さ「０」の分類（即ち、属性値そのもの）は、離散集合から誘導される束において、正の整数の部分集合｛３，４｝で示される。また、性別を示す属性の一般化階層おける高さ「１」の分類は、離散集合から誘導される束において、正の整数の部分集合｛３｝で示される。また、性別を示す属性の一般化階層おける高さ「２」の分類は、離散集合から誘導される束において、正の整数の部分集合｛｝（即ち、空集合）で示される。
【０１４８】
即ち、各属性に対応する複数の分類のそれぞれは、より具体化された分類ほど、当該属性に関連付けられた、複数の連続した正の整数に対応した要素のうち、より多くの要素が、値のより小さい要素から順次加えられた部分集合に対応付けられている。
【０１４９】
なお、このとき、一般化戦略からなる束の最大元（２，２）は、離散集合から誘導される束の最小限｛｝（即ち、空集合）に対応付けられ、一般化戦略からなる束の最小元（０，０）は、離散集合から誘導される束の最大元｛１，２，３，４｝に対応付けられる。
【０１５０】
以上のようにして、離散集合から誘導される束を規定することで、一般化階層からなる束の各元（即ち、一般化ノード）が、当該離散集合から誘導される束の元に対応付けられる。
【０１５１】
具体的な一例として、図１４に示す例では、一般化戦略からなる束の一般化ノード（０，１）は、離散集合から誘導される束の元｛１，２，３｝に対応付けられる。同様に、一般化戦略からなる束の一般化ノード（２，１）は、離散集合から誘導される束の元｛３｝に対応付けられる。
【０１５２】
以上のような構成のもと、一般化戦略からなる束と、離散集合から誘導される束との間で、一方の束の元を他方の束の元に変換する処理の一例について以下に説明する。
【０１５３】
まず、図１４及び図１５を参照して、一般化戦略からなる束の元（即ち、一般化ノード）を、離散集合から誘導される束の元に変換する処理の一例について説明する。図１５は、一般化戦略からなる束の元を、離散集合から誘導される束の元に変換する処理の一例について説明するための説明図であり、同処理のアルゴリズムを所謂プログラムコードの形式で模式的に提示した図である。なお、図１５に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。
【０１５４】
図１５に示した「set」関数は、入力として、変数ｖ＝（ｖ１，ｖ２，・・・，ｖｎ）で示された一般化ノードと、（ｈ１，ｈ２，・・・，ｈｎ）で示された各属性の一般化階層の高さの最大値を示す情報とを取得する。なお、（ｖ１，ｖ２，・・・，ｖｎ）の定義は、図１１を参照して前述した、属性値を一般化するための「getFrequentSets」関数の場合と同様である。また、（ｈ１，ｈ２，・・・，ｈｎ）のそれぞれは、互いに異なる属性に対応しており、各属性の一般化階層の高さの最大値を示している。即ち、ｈｉは、ｉ番目の属性の一般化階層の高さの最大値を示していることとなる。
【０１５５】
図１５に示す「set」関数は、図１４に示した一般化戦略からなる束の元と離散集合から誘導される束の元との対応関係に基づき、一般化戦略からなる束の最小元（０，０）を入力とした場合に、離散集合から誘導される束の最大元｛１，２，３，４｝を出力する。同様に、同関数は、一般化戦略からなる束の最大元（２，２）を入力とした場合に、離散集合から誘導される束の最小限｛｝を出力する。
【０１５６】
また、一般化戦略からなる束の最小元に対して、少なくともいずれかの属性に対応する要素が加算された元を、「set」関数の入力とした場合に着目する。この場合には、同関数は、離散集合から誘導される束の最大元に対応する集合から、一般化ノードにおいて値が加算された属性に対応する要素のうち、より値の大きい要素が、当該加算分だけ削除された部分集合に対応する元を出力する。
【０１５７】
具体的な一例として、一般化戦略からなる束の最小元（０，０）に対して、性別を示す属性に対応する要素が１加算された（即ち、当該属性を１段階だけ一般化した）一般化ノード（０，１）に着目する。この場合には、離散集合から誘導される束の最大元に対応する集合｛１，２，３，４｝のうち、要素「３」と「４」とが、性別を示す属性に対応している。そのため、「set」関数は、集合｛１，２，３，４｝から、要素「３」と「４」とのうち、より大きい要素を１つだけ削除した部分集合｛１，２，３｝に対応する元を、一般化ノード（０，１）に対応する元として出力する。
【０１５８】
また、他の一例として、一般化戦略からなる束の最小元（０，０）に対して、年齢を示す属性に対応する要素が２加算された（即ち、当該属性を２段階だけ一般化した）一般化ノード（２，０）に着目する。この場合には、離散集合から誘導される束の最大元に対応する集合｛１，２，３，４｝のうち、要素「１」と「２」とが、年齢を示す属性に対応している。そのため、「set」関数は、集合｛１，２，３，４｝から、要素「１」と「２」とのうち、より大きい要素を２つだけ削除した部分集合｛３，４｝に対応する元を、一般化ノード（２，０）に対応する元として出力する。
【０１５９】
以上のようにして、「set」関数は、図１４に示した一般化戦略からなる束の元と離散集合から誘導される束の元との対応関係に基づき、入力として取得した一般化ノードｖを、離散集合から誘導される束の元Ｖ＝｛ａ１，ａ２，・・・｝に変換する。
【０１６０】
以上、図１４及び図１５を参照して、一般化戦略からなる束の元（即ち、一般化ノード）を、離散集合から誘導される束の元に変換する処理の一例について説明した。
【０１６１】
次に、図１６及び図１７を参照して、離散集合から誘導される束の元を、一般化戦略からなる束の元（即ち、一般化ノード）に変換する処理の一例について説明する。図１６及び図１７は、離散集合から誘導される束の元を、一般化戦略からなる束の元（即ち、一般化ノード）に変換する処理の一例について説明するための説明図である。また、図１７は、同処理のアルゴリズムを所謂プログラムコードの形式で模式的に提示した図である。なお、図１７に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。
【０１６２】
まず、図１６を参照して、離散集合から誘導される束の元を、一般化戦略からなる束の元（即ち、一般化ノード）に変換する処理の概要について説明する。図１４を参照するとわかるように、一般化戦略からなる束の元と、離散集合から誘導される束の元とを１対１で対応付けた場合に、離散集合から誘導される束の元全てに対して、一般化戦略からなる束の元が対応付けられるとは限らない。
【０１６３】
具体的な一例として、前述した「set」関数により、一般化戦略からなる束の元を、離散集合から誘導される束の元に変換した場合に、変換後の元として、例えば、部分集合｛１，２，４｝に対応する元や、部分集合｛１，４｝に対応する元は出力されない。そのため、「set」関数の逆変換を行ったとしても、必ずしも、離散集合から誘導される束の元全てを、一般化戦略からなる束の元に変換できるとは限らない。
【０１６４】
以上のような状況を鑑みて、図１７に示す「vec」関数は、離散集合から誘導される束の元全てを、一般化戦略からなる束におけるいずれかの元（即ち、一般化ノード）に対応付けるアルゴリズムを提供する。そこで、図１７を参照して、離散集合から誘導される束の元を、一般化戦略からなる束の元（即ち、一般化ノード）に変換する、「vec」関数の詳細について以下に説明する。
【０１６５】
図１７に示した「vec」関数は、入力として、変数Ｖ＝｛ａ１，ａ２，・・・｝で示された離散集合から誘導される束の元と、（ｈ１，ｈ２，・・・，ｈｎ）で示された各属性の一般化階層の高さの最大値を示す情報とを取得する。なお、（ｈ１，ｈ２，・・・，ｈｎ）の定義は、図１５を参照して前述した、一般化戦略からなる束の元を、離散集合から誘導される束の元に変換する「set」関数の場合と同様である。
【０１６６】
「vec」関数は、入力として取得した離散集合から誘導される束の元を、「set」関数により一般化戦略からなる束の一般化ノードが対応付けられた、離散集合から誘導される束の元のいずれかに対応付ける。具体的には、同関数は、入力として取得した元が示す正の整数の有限集合（即ち、有限集合｛１，２，３，４｝の部分集合）において、各属性に関連付けられた要素に着目して、当該要素よりも低い値を示す他の要素が欠落している場合には、当該他の要素を補間することで、他の元に対応付ける。
【０１６７】
例えば、図１６において、離散集合から誘導される束の元のうち、有限集合｛２，３｝で示された元に着目する。前述したように、図１４及び図１６に示した離散集合から誘導される束の元では、要素「１」及び「２」に基づく有限集合｛１，２｝の部分集合により、年齢を示す属性の分類が示される。即ち、有限集合｛２，３｝に着目した場合に、年齢を示す属性に関連付けられた要素は「２」であり、当該要素より低い値を示す要素「１」が欠落していることがわかる。この場合には、「vec」関数は、有限集合｛２，３｝に対して、年齢を示す属性に対応する要素「１」を補間する。
【０１６８】
また、図１４及び図１６に示した離散集合から誘導される束の元では、要素「３」及び「４」に基づく有限集合｛３，４｝の部分集合により、性別を示す属性の分類が示される。即ち、有限集合｛２，３｝に着目した場合に、性別を示す属性に関連付けられた要素は「３」であり、当該要素より低い値を示す要素は存在しない。この場合には、「vec」関数は、有限集合｛２，３｝に対して、性別を示す属性に対応する要素を新たに補完することはない。
【０１６９】
以上のようにして、「vec」関数は、離散集合から誘導される束において、有限集合｛２，３｝で示された元を、有限集合｛１，２，３｝で示された他の元に対応付ける。なお、離散集合から誘導される束において有限集合｛１，２，３｝で示された元は、図１４及び図１６に示すように、一般化戦略からなる束の一般化ノード（０，１）に対応付けられる。即ち、「vec」関数は、有限集合｛２，３｝を要素の補間により有限集合｛１，２，３｝に対応付けることで、離散集合から誘導される束において有限集合｛２，３｝で示された元を、一般化戦略からなる束の一般化ノード（０，１）に変換する。
【０１７０】
また他の一例として、図１６において、離散集合から誘導される束の元のうち、有限集合｛１，４｝で示された元に着目する。この場合には、年齢を示す属性に関連付けられた要素は「１」であり、当該要素より低い値を示す要素は存在しない。この場合には、「vec」関数は、有限集合｛１，４｝に対して、年齢を示す属性に対応する要素を新たに補間することはない。
【０１７１】
また、有限集合｛１，４｝に着目した場合に、性別を示す属性に関連付けられた要素は「４」であり、当該要素より低い値を示す要素「３」が欠落していることがわかる。この場合には、「vec」関数は、有限集合｛１，４｝に対して、性別を示す属性に対応する要素「３」を補間する。
【０１７２】
以上のようにして、「vec」関数は、離散集合から誘導される束において、有限集合｛１，４｝で示された元を、有限集合｛１，３，４｝で示された他の元に対応付ける。なお、離散集合から誘導される束において有限集合｛１，３，４｝で示された元は、図１４及び図１６に示すように、一般化戦略からなる束の一般化ノード（１，０）に対応付けられる。即ち、「vec」関数は、有限集合｛１，４｝を要素の補間により有限集合｛１，３，４｝に対応付けることで、離散集合から誘導される束において有限集合｛１，４｝で示された元を、一般化戦略からなる束の一般化ノード（１，０）に変換する。
【０１７３】
同様にして、離散集合から誘導される束において、有限集合｛１，２，４｝、｛２，３，４｝、｛２，４｝で示された各元は、有限集合｛１，２，３，４｝で示された他の元に対応付けられる。なお、離散集合から誘導される束において有限集合｛１，２，３，４｝で示された元は、図１４及び図１６に示すように、一般化戦略からなる束の一般化ノード（０，９）に対応付けられる。即ち、「vec」関数は、離散集合から誘導される束において、有限集合｛１，２，４｝、｛２，３，４｝、｛２，４｝で示された各元を、一般化戦略からなる束の一般化ノード（０，０）に変換する。
【０１７４】
以上のようにして、「vec」関数は、図１６に示すように、入力として取得した離散集合から誘導される束の元Ｖ＝｛ａ１，ａ２，・・・｝を、一般化戦略からなる束の一般化ノードｖ＝（ｖ１，ｖ２，・・・，ｖｎ）に変換する。
【０１７５】
以上、図１６及び図１７を参照して、離散集合から誘導される束の元を、一般化戦略からなる束の元（即ち、一般化ノード）に変換する処理の一例について説明した。
【０１７６】
［４．４．極小元の探索］
次に、図１８及び図１９を参照して、前述した解析部１４の極小元探索部１４３が、一般化戦略からなる束における各一般化ノードから、（ｋ，ｔ）−匿名性を満たす極小元を探索する処理の一例について説明する。図１８及び図１９は、一般化戦略からなる束における各一般化ノードから、（ｋ，ｔ）−匿名性を満たす極小元を探索する処理の一例について説明するための説明図である。
【０１７７】
まず、図１８を参照して、一般化戦略からなる束における各一般化ノードから、（ｋ，ｔ）−匿名性を満たす極小元を探索するための「AMSS(A  Most  Specific  Sentences)」関数の処理の流れについて説明する。図１８は、同処理のアルゴリズムを所謂プログラムコードの形式で模式的に提示した図である。なお、図１８に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。
【０１７８】
図１８に示した「AMSS」関数は、入力として、変数ｖ＝（ｖ１，ｖ２，・・・，ｖｎ）で示された（ｋ，ｔ）−匿名性を満たす一般化ノードと、変数Ｔで示された処理対象となるテーブルｄ１０と、変数（Ｈ１，Ｈ２，・・・，Ｈｎ）で示された各属性の一般化階層を示す情報とを取得する。なお、（ｖ１，ｖ２，・・・，ｖｎ）及び（Ｈ１，Ｈ２，・・・，Ｈｎ）の定義は、図１１を参照して前述した、属性値を一般化するための「getFrequentSets」関数の場合と同様である。
【０１７９】
「AMSS」関数は、極小元探索部１４３の動作として前述したように、一般化戦略からなる束において、（ｋ，ｔ）−匿名性を満たす元（一般化ノード）を基準点として、少なくともいずれかの要素をより具体化する方向に向けて、（ｋ，ｔ）−匿名性を満たす極小元を探索する。
【０１８０】
具体的には、「AMSS」関数は、入力として指定された（ｋ，ｔ）−匿名性を満たす一般化ノードｖを、（ｋ，ｔ）−匿名性を満たす極小元を探索するための基準点として設定する。そして、同関数は、（ｋ，ｔ）−匿名性を満たすことが確認された元の各要素（即ち、一般化階層の高さ）のうち、いずれかの要素をより具体化する方向にシフトさせ、当該シフト後の元が（ｋ，ｔ）−匿名性を満たす元か否かを判定する。なお、（ｋ，ｔ）−匿名性の判定には、図１３を参照して前述した「kAnonymityCheck」関数を使用すればよい。
【０１８１】
そして、「AMSS」関数は、シフト後の元が（ｋ，ｔ）−匿名性を満たす場合には、いずれかの要素をさらに具体化する方向にシフトさせ、シフト後の元が（ｋ，ｔ）−匿名性を満たさない場合には、いずれかの要素を一般化（抽象化）する方向にシフトさせる。このように、同関数は、いずれかの要素をシフトさせ、シフト後の元が（ｋ，ｔ）−匿名性を満たす元か否かを判定する処理を逐次実行することで、（ｋ，ｔ）−匿名性を満たす極小元を探索する。
【０１８２】
なお、図１８に示す例では、「AMSS」関数は、（ｋ，ｔ）−匿名性を満たす極小元を探索に、所謂二分探索と呼ばれる方法を用いている。
【０１８３】
ここで、図１９を参照して、図１８に示した「AMSS」関数に基づき、極小元探索部１４３が、（ｋ，ｔ）−匿名性を満たす極小元の探索に係る処理について、具体的な例を挙げて説明する。図１９に示す例は、図５及び図６に示した属性の一般化階層に基づく一般化戦略からなる束（図７参照）を適用し、最大元（２，２）を基準点とした場合の一例について示している。なお、図１９に示す境界ｄ５０は、（ｋ，ｔ）−匿名性を満たす元と、（ｋ，ｔ）−匿名性を満たさない元の境界を示しており、当該境界ｄ５０から最大元側（即ち、図面の下側）の各元が、（ｋ，ｔ）−匿名性を満たす元に相当する。もちろん、境界ｄ５０から最小元側（即ち、図面の上側）の各元は、（ｋ，ｔ）−匿名性を満たさない元に相当することは言うまでもない。
【０１８４】
図１９に示す例では、極小元探索部１４３は、まず、年齢の属性に対応する要素をより具体化する方向（即ち、一般化戦略の高さを低くする方向）にシフトさせている。即ち、極小元探索部１４３は、一般化ノード（２，２）から、年齢の属性に対応する要素をより具体化する方向にシフトさせた一般化ノード（１，２）の（ｋ，ｔ）−匿名性を判定する。ここでは、一般化ノード（１，２）は、（ｋ，ｔ）−匿名性を満たすものとする。
【０１８５】
一般化ノード（１，２）が（ｋ，ｔ）−匿名性を満たすため、極小元探索部１４３は、当該一般化ノード（１，２）から、年齢の属性に対応する要素をより具体化する方向にシフトさせた一般化ノード（０，２）の（ｋ，ｔ）−匿名性を判定する。ここでは、一般化ノード（０，２）は、（ｋ，ｔ）−匿名性を満たさないものとする。
【０１８６】
一般化ノード（０，２）は、（ｋ，ｔ）−匿名性を満たさないため、極小元探索部１４３は、一般化ノード（１，２）から、性別の属性に対応する要素をより具体化する方向にシフトさせた一般化ノード（１，１）の（ｋ，ｔ）−匿名性を判定する。ここでは、一般化ノード（１，１）は、（ｋ，ｔ）−匿名性を満たすものとする。
【０１８７】
一般化ノード（１，１）が（ｋ，ｔ）−匿名性を満たすため、極小元探索部１４３は、当該一般化ノード（１，１）から、性別の属性に対応する要素をより具体化する方向にシフトさせた一般化ノード（１，０）の（ｋ，ｔ）−匿名性を判定する。ここでは、一般化ノード（１，０）は、（ｋ，ｔ）−匿名性を満たさないものとする。
【０１８８】
なお、一般化ノード（０，１）は、一般化ノード（０，２）の判定結果に基づき、（ｋ，ｔ）−匿名性を満たさないことが既に判定されている。これは、一般化ノード（０，１）が、一般化ノード（０，２）のうち、年齢の属性に対応する要素をさらに具体化した一般化ノードに相当するためである。具体的には、（ｋ，ｔ）−匿名性を満たさない一般化ノードを、さらに具体化した他の一般化ノードは、（ｋ，ｔ）−匿名性を満たさない。そのため、一般化ノード（０，２）が（ｋ，ｔ）−匿名性を満たさないと判定された場合には、当該一般化ノード（０，２）をさらに具体化した一般化ノード（０，１）は、当該一般化ノード（０，２）の判定結果をもって、（ｋ，ｔ）−匿名性を満たさないこととなる。
【０１８９】
ここで、一般化ノード（１，１）をａとした場合に、ａ＞ｂの関係を有する一般化ノードｂは、（０，１）及び（１，０）となる。このとき、（ｋ，ｔ）−匿名性を判定する処理をクエリ関数ｑとした場合に、ａが極小元であるとは、ｑ（ａ）＝１であり、かつ、任意のａ＞ｂ∈Ｌに対してｑ（ｂ）＝０が成り立つことであった。なお、一般化ノード（０，１）については、実際にｑ（ａ）を計算しなくても、前述の通り、一般化ノード（０，２）の判定結果に基づき、ｑ（ａ）＝０であることは自明である。そのため、極小元探索部１４３は、一般化ノード（１，１）を極小元と判定し、当該一般化ノード（１，１）を出力する。
【０１９０】
以上、図１８及び図１９を参照して、極小元探索部１４３が、一般化戦略からなる束における各一般化ノードから、（ｋ，ｔ）−匿名性を満たす極小元を探索する処理の一例について説明した。
【０１９１】
［４．５．一連の処理の流れ］
次に、図２０及び図２１を参照して、前述した解析部１４が、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索し、探索された一連の極小元それぞれに対応する一般化戦略を出力する処理の一例について説明する。図２０及び図２１は、解析部１４の一連の処理の流れの一例について説明するための説明図である。
【０１９２】
図２０は、解析部１４の一連の処理の一例を示した「All-MSS（All  Most  Specific  Sentences）」関数のアルゴリズムを、所謂プログラムコードの形式で模式的に提示した図である。なお、図２０に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。
【０１９３】
図２０に示した「All-MSS」関数は、入力として、（ｋ，ｔ）−匿名性の閾値（即ち、ｋ及びｔ）と、変数Ｔで示された処理対象となるテーブルｄ１０と、変数（Ｈ１，Ｈ２，・・・，Ｈｎ）で示された各属性の一般化階層を示す情報とを取得する。なお、（Ｈ１，Ｈ２，・・・，Ｈｎ）の定義は、図１１を参照して前述した、属性値を一般化するための「getFrequentSets」関数の場合と同様である。
【０１９４】
また、図２１は、図２０に示した「All-MSS」関数の一連の処理の流れを示したフローチャートである。以下に、図２１を参照して、「All-MSS」関数の一連の処理の流れ、即ち、解析部１４の一連の処理の流れの一例について説明する。なお、本説明では、図５及び図６に示した属性の一般化階層に基づく一般化戦略からなる束（図７参照）を適用したものとして説明する。なお、この場合には、一般化戦略からなる束の各一般化ノードは、図１４及び図１６に示した離散集合から誘導される束の元に対応付けられるものとする。
【０１９５】
（ステップＳ１０１）
解析部１４は、ＤＢ情報取得部１１から処理対象となるテーブルｄ１０（即ち、Ｔ）の情報を取得する。また、解析部１４は、階層情報取得部１３から、処理対象となるテーブルｄ１０の各属性のうち、属性値の一般化（抽象化）の対象となる属性を示す情報と、当該属性それぞれの一般化階層を示す情報（即ち、（Ｈ１，Ｈ２，・・・，Ｈｎ））とを取得する。また、解析部１４は、階層情報取得部１３から、匿名性の条件を示す情報として、（ｋ，ｔ）−匿名性の閾値（即ち、ｋ及びｔ）を取得する。
【０１９６】
解析データ生成部１４１は、属性値の一般化（抽象化）の対象となる属性それぞれの一般化階層を示す情報に基づき、各属性の一般化階層の高さの組み合わせを抽出し、抽出した各組み合わせを一般化戦略として規定する。
【０１９７】
そして、解析データ生成部１４１は、既定した各一般化戦略を元として、各一般化戦略が要素として有する各属性の一般化階層の高さをより一般化（抽象化）する順序関係（換言すると、各属性の分類をより抽象化する順序関係）に基づき、一般化戦略からなる束を規定する。
【０１９８】
（ステップＳ１０３）
極小元探索部１４３は、まず、一般化戦略からなる束の最大元を基準点として、「AMSS」関数に基づき、（ｋ，ｔ）−匿名性を満たす極小元ｖを取得する。具体的には、極小元探索部１４３は、図１９に基づき前述したように、一般化戦略からなる束の最大元（２，２）を基準点とした場合に、（ｋ，ｔ）−匿名性を満たす極小元ｖ＝（１，１）を取得する。極小元探索部１４３は、（ｋ，ｔ）−匿名性を満たす極小元の探索結果として、取得した極小元ｖ＝（１，１）を基準点導出部１４５に通知する。
【０１９９】
（ステップＳ１０５）
基準点導出部１４５は、極小元探索部１４３から、（ｋ，ｔ）−匿名性を満たす極小元の探索結果として、極小元ｖ＝（１，１）を取得する。基準点導出部１４５は、取得した極小元ｖを入力として「set」関数に基づき、当該極小元ｖに対応する、離散集合から誘導される束の元Ｖを特定する。
【０２００】
例えば、図２２は、基準点導出部１４５の処理の一例について説明するための説明図であり、基準点導出部１４５が、取得した極小元ｖ＝（１，１）に対応する、離散集合から誘導される束の元を特定する処理を模式的に示している。なお、図２２において、参照符号ｄ５２は、一般化戦略からなる束に示された境界ｄ５０を、離散集合から誘導される束側に示したものである。即ち、境界ｄ５２から最小元側（即ち、図面の下側）の各元を、一般化戦略からなる束の一般化ノードに変換した場合に、当該一般化ノードは（ｋ，ｔ）−匿名性を満たすこととなる。また、境界ｄ５２から最大元側（即ち、図面の上側）の各元を、一般化戦略からなる束の一般化ノードに変換した場合に、当該一般化ノードは（ｋ，ｔ）−匿名性を満たさないこととなる。
【０２０１】
即ち、基準点導出部１４５は、取得した極小元ｖ＝（１，１）に対応する、離散集合から誘導される束の元Ｖとして、Ｖ＝｛１，３｝を特定する。
【０２０２】
次に、基準点導出部１４５は、特定した離散集合から誘導される束の元Ｖ＝｛１，３｝の補集合を導出し、導出した補集合を変数Ｃで示された集合に代入する。例えば、図２３は、基準点導出部１４５の処理の一例について説明するための説明図である。図２３に示す例では、基準点導出部１４５は、離散集合から誘導される束の元Ｖ＝｛１，３｝の補集合に対応する元｛２，４｝を導出し、導出した元｛２，４｝を集合Ｃに代入する。
【０２０３】
（ステップＳ１０７）
次いで、基準点導出部１４５は、変数Ｄで示された集合を、空集合で初期化する。なお、当該集合Ｄは、離散集合から誘導される束の各元のうち、後述する処理が既に完了している元を保持するための集合であり、当該元に対して再度処理が実行されるのを防ぐために設けられている。
【０２０４】
（ステップＳ１０９）
基準点導出部１４５は、離散集合から誘導される束の元が示す正の整数の集合から、極小横断に相当する部分集合を抽出する関数Ｔｒに対して、導出した補集合Ｃを入力する。そして、基準点導出部１４５は、関数Ｔｒの出力として、補集合Ｃの極小横断に相当する部分集合Ｔｒ（Ｃ）を取得し、当該部分集合Ｔｒ（Ｃ）の要素のうち、集合Ｄに含まれない要素に対応する離散集合から誘導される束の元を、変数Ｘで示された元として抽出する。
【０２０５】
具体的な一例として、図２３に示すように、基準点導出部１４５は、離散集合から誘導される束の元｛２，４｝の極小横断に相当する部分集合Ｔｒ（Ｃ）として、Ｔｒ（Ｃ）＝｛｛２｝，｛４｝｝を取得する。
【０２０６】
なお、関数Ｔｒは、入力された集合（例えば、補集合Ｃ）をハイパーエッジとするハイパーグラフの双対を計算する、所謂ハイパーグラフ双対化（Hypergraph  Dualization）のアルゴリズムとして知られる処理に相当する。そのため、ハイパーグラフ双対化のアルゴリズムに基づく処理であれば、関数Ｔｒの処理内容は特に限定されない。また、ハイパーグラフ双対化のアルゴリズムに基づく処理に限らず、入力された正の整数の集合から、極小横断に相当する部分集合を抽出することが可能であれば、関数Ｔｒの処理内容は特に限定されないことは言うまでもない。
【０２０７】
（ステップＳ１１１）
離散集合から誘導される束の元Ｘが存在する場合には（ステップＳ１０９、ＹＥＳ）、基準点導出部１４５は、「vec」関数に基づき、当該元Ｘに対応する、一般化戦略からなる束の一般化ノードｖを特定する。
【０２０８】
例えば、図２４は、基準点導出部１４５の処理の一例について説明するための説明図である。図２４に示す例では、基準点導出部１４５が、「vec」関数に基づき、離散集合から誘導される束の元｛２｝及び元｛４｝それぞれについて、対応する一般化戦略からなる束の一般化ノードｖを特定している。具体的には、基準点導出部１４５は、離散集合から誘導される束の元｛２｝に対応する一般化ノードとして、一般化ノードｖ＝（０，２）を特定する。同様に、基準点導出部１４５は、離散集合から誘導される束の元｛４｝に対応する一般化ノードとして、一般化ノードｖ＝（２，０）を特定する。
【０２０９】
（ステップＳ１１３）
そして、基準点導出部１４５は、特定した一般化ノードｖが、（ｋ，ｔ）−匿名性を満たすか否かを判定する。なお、（ｋ，ｔ）−匿名性を満たすか否かの判定には、前述した「kAnonymityCheck」関数を適用すればよい。
【０２１０】
（ステップＳ１１９）
特定した一般化ノードｖが（ｋ，ｔ）−匿名性を満たさない場合には（ステップＳ１１３、ＮＯ）、基準点導出部１４５は、当該一般化ノードｖの特定元である、離散集合から誘導される束の元Ｘ（即ち、「vec」関数に入力した元Ｘ）を集合Ｄに加える。例えば、図２４に示す例では、離散集合から誘導される束の元｛２｝に対応する一般化ノードｖ＝（０，２）は、（ｋ，ｔ）−匿名性を満たさない。そのため、基準点導出部１４５は、一般化ノードｖ＝（０，２）の特定元である、離散集合から誘導される束の元Ｘ＝｛２｝を集合Ｄに加える。
【０２１１】
（ステップＳ１１５）
これに対して、特定した一般化ノードｖが（ｋ，ｔ）−匿名性を満たす場合には（ステップＳ１１３、ＹＥＳ）、基準点導出部１４５は、当該一般化ノードｖを新たな基準点の候補として、極小元探索部１４３に出力する。例えば、図２４に示す例では、離散集合から誘導される束の元｛４｝に対応する一般化ノードｖ＝（２，０）は、（ｋ，ｔ）−匿名性を満たす。そのため、基準点導出部１４５は、一般化ノードｖ＝（２，０）を、新たな基準点の候補として、極小元探索部１４３に出力する。
【０２１２】
この新たな基準点の候補の出力を受けて、極小元探索部１４３は、当該候補を基準点として新たに（ｋ，ｔ）−匿名性を満たす極小元ｗを探索する。そして、極小元探索部１４３は、（ｋ，ｔ）−匿名性を満たす極小元の探索結果として、探索された極小元ｗを基準点導出部１４５に通知する。
【０２１３】
（ステップＳ１１７）
基準点導出部１４５は、取得した極小元ｗに対応する、離散集合から誘導される束の元Ｖを特定し、特定した元Ｖの補集合を集合Ｃに加える。
【０２１４】
（ステップＳ１０９）
そして、極小元探索部１４３及び基準点導出部１４５は、ステップＳ１１１〜Ｓ１１７に示された一連の処理を、部分集合Ｔｒ（Ｃ）の要素のうち、集合Ｄに含まれない要素に対応する離散集合から誘導される束の元Ｘが存在する限り継続する（ステップＳ１０９、ＹＥＳ）。
【０２１５】
例えば、図２５は、極小元探索部１４３の処理の一例について説明するための説明図であり、極小元探索部１４３が、一般化ノードｖ＝（２，０）を新たな基準点として、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合について示している。なお、図２５に示す例では、一般化ノードｖ＝（２，０）自体が、（ｋ，ｔ）−匿名性を満たす極小元に相当する。
【０２１６】
そして、離散集合から誘導される束の元Ｘが存在しない場合には（ステップＳ１０９、ＮＯ）、極小元探索部１４３は、探索された一連の（ｋ，ｔ）−匿名性を満たす極小元それぞれに対応する一般化戦略を、解析結果出力部１５に出力する。
【０２１７】
例えば、図２６は、極小元探索部１４３の処理結果の一例について説明するための説明図であり、図５及び図６に示した属性の一般化階層に基づく一般化戦略からなる束（図７参照）から探索された、（ｋ，ｔ）−匿名性を満たす極小元の一例を示している。即ち、図２６に示す例では、一般化ノード（１，１）及び（２，０）が、（ｋ，ｔ）−匿名性を満たす極小元に相当する。そのため、極小元探索部１４３は、一般化ノード（１，１）及び（２，０）に対応する一般化戦略を、解析結果出力部１５に出力することとなる。
【０２１８】
解析結果出力部１５は、極小元探索部１４３により探索された一連の極小元それぞれに対応する一般化戦略を、当該極小元探索部１４３から取得する。そして、解析結果出力部１５は、取得した一連の一般化戦略を、（ｋ，ｔ）−匿名性を満たすようにテーブルｄ１０を一般化（抽象化）するための条件（即ち、一般化戦略）の候補として、管理者端末３０を介して管理者に提示する。なお、このとき提示される条件、即ち、探索された一連の極小元それぞれに対応する一般化戦略が、あらかじめ指定された（ｋ，ｔ）−匿名性を満たすようにテーブルｄ１０を一般化し、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略に相当する。
【０２１９】
なお、ステップＳ１０９として示したように、解析部１４は、補集合Ｃをハイパーエッジとするハイパーグラフの双対を計算する処理を繰り返し計算することとなる。そのため、同処理として、ハイパーグラフの双対化が逐次的に実行可能なアルゴリズム、即ち、新たなハイパーエッジが追加されたとしても、既に双対を計算したハイパーグラフについては、再計算を必要としないアルゴリズムを適用してもよい。このようなアルゴリズムを適用することで、解析部１４は、（ｋ，ｔ）−匿名性を満たす極小元の探索に係る計算量をより削減することが可能となる。
【０２２０】
以上、図２０及び図２１を参照して、前述した解析部１４が、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索し、探索された一連の極小元それぞれに対応する一般化戦略を出力する処理の一例について説明した。
【０２２１】
＜５．計算量＞
次に、図２７を参照して、本実施形態に係る情報処理装置１０が、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の、当該探索に係る処理の計算量について説明する。図２７は、本実施形態に係る情報処理装置１０が、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の、当該探索に係る処理の計算量について説明するための説明図である。なお、本説明では、情報処理装置１０が、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の計算量を、（ｋ，ｔ）−匿名性を満たすか否かを判定するクエリ関数ｑ（即ち、「kAnonymityCheck」関数）の実行回数として説明する。また、図２７は、一例として、図５及び図６に示した「年齢」及び「性別」を示す属性の一般化階層に基づく一般化戦略からなる束を示している。
【０２２２】
まず、情報処理装置１０が、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の計算量を説明するための用語として、「入力のサイズ」、「出力のサイズ」、「ボーダー」、及び「束の幅」の定義について説明する。
【０２２３】
（入力のサイズ）
「入力のサイズ」とは、一般化戦略の表現長に相当する。入力のサイズＲｉは、一般化の対象となる属性の数ｍと、各属性の一般化階層における階層の数ｍｉとに基づき、以下に示す（式１）に基づき規定される。
【０２２４】
【数１】
2016053829.tif 000003
【０２２５】
例えば、図５示した「年齢」を示す属性の一般化階層は、高さが０、１、２の３つの階層を有しており、階層の数ｍｉ＝３となる。同様に、図６示した「性別」を示す属性の一般化階層は、高さが０、１、２の３つの階層を有しており、階層の数ｍｉ＝３となる。そのため、「年齢」及び「性別」を示す属性の属性値を一般化するための一般化戦略の数は、図２７に示した、（０，０），（０，１），・・・，（１，２），（２，２）の９つとなる。したがって、図２７に示す例では、入力のサイズＲｉ＝ｌｏｇ９となる。
【０２２６】
（出力のサイズ）
「出力のサイズ」とは、情報処理装置１０が出力する一般化戦略の数に相当し、即ち、情報処理装置１０により探索された（ｋ，ｔ）−匿名性を満たす極小元の数に相当する。
【０２２７】
図２７に示す例において、境界ｄ５０を、（ｋ，ｔ）−匿名性を満たす元と、（ｋ，ｔ）−匿名性を満たさない元の境界とした場合に、（ｋ，ｔ）−匿名性を満たす極小元は、一般化ノード（１，１）及び（２，０）の２つとなる。即ち、図２７に示す例では、出力のサイズは「２」となる。
【０２２８】
（ボーダー）
「ボーダー」とは、束上の境界にあたる一般化戦略の集合に相当し、「正のボーダー」と、「負のボーダー」とに分けられる。
【０２２９】
「正のボーダー」とは、（ｋ，ｔ）−匿名性を満たす極小な一般化戦略（即ち、（ｋ，ｔ）−匿名性を満たす極小元）の集合に相当する。図２７に示す例では、一般化ノード（１，１）及び（２，０）の集合が、正のボーダーに相当する。即ち、正ボーダーのサイズと、出力のサイズとは一致することとなる。
【０２３０】
「負のボーダー」とは、（ｋ，ｔ）−匿名性を満たさない極大な一般化戦略の集合に相当する。図２７に示す例では、一般化ノード（０，２）及び（１，０）の集合が、負のボーダーに相当する。
【０２３１】
（束の幅）
「束の幅」とは、束上の元のうち、「行き先」が最も多い元の当該行き先の数に相当する。ここで、一般化ノードＢが、一般化ノードＡの「行き先」であるとは、順序関係において、Ａ＞Ｂであり、かつ、Ａ＞Ｃ＞Ｂを満たす一般化ノードＣが存在しないことを意味する。なお、ここでノード間の関係を示す記号として「＞」を用いたが、この記号は、数値間の大小関係を示す記号ではなく、ノード間の順序関係を示しており、所謂「succeed」と呼ばれる記号に相当する。また、以降の説明では、ノード間の関係を示す記号として、「＞」、「＜」、「≧」、及び「≦」を使用した場合には、これらの記号は、数値間の大小関係を示す記号ではなく、ノード間の順序関係を示しているものとする。
【０２３２】
具体的には、図２７に示す例において、一般化ノード（１，２）の行き先は、一般化ノード（０，２）及び（１，１）であり、当該行き先の数は２つとなる。なお、図２７に示す例において、行き先の数が２つを超える一般化ノードは存在しない。そのため、図２７に示す例では、束の幅は「２」となる。
【０２３３】
（計算量）
以上を踏まえ、出力のサイズをＮ、側の幅をｗ、負のボーダーのサイズをＢ−とした場合には、情報処理装置１０が、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の計算量Ｑは、以下に示す（式２）で示される。なお、出力のサイズＮは、入力のサイズと、一般化の対象となるデータに依存する。
【０２３４】
【数２】
2016053829.tif 000004
【０２３５】
ここで、（ｋ，ｔ）−匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略、即ち、（ｋ，ｔ）−匿名性を満たす一連の極小元を特定する処理は、所謂列挙問題に相当する。このような列挙問題を解く従来のアルゴリズムは、一般的にはヒューリスティックなアルゴリズムに相当し、計算量を事前に算出することが困難であった。
【０２３６】
これに対して、本実施形態に係る情報処理装置１０は、ハイパーグラフ双対化のアルゴリズムを、探索元（即ち、（ｋ，ｔ）−匿名性を満たす極小元）を列挙するために利用している。このようなハイパーグラフ双対化のアルゴリズムには、論理的な上限が与えられているものもある。そのため、本実施形態に係る情報処理装置１０が、（ｋ，ｔ）−匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略を特定（列挙）する処理の計算量を事前に算出することが可能となる。
【０２３７】
また、本実施形態に係る情報処理装置１０の処理として説明したアルゴリズムに依れば、必ずしも全ての一般化戦略（即ち、一般化ノード）に対して、（ｋ，ｔ）−匿名性を満たすか否かの判定をおこなう必要はない。具体的な一例として、図２０〜図２６を参照して説明した例では、一般化ノード（２，１）に対して、（ｋ，ｔ）−匿名性を満たすか否かの判定を行われていないが、（ｋ，ｔ）−匿名性を満たす極小元（１，１）及び（２，０）を特定している。このように、本実施形態に係る情報処理装置１０の処理として説明したアルゴリズムに依れば、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす一連の極小元を効率よく探索（列挙）し、当該探索に係る処理の負荷を低減することが可能となる。
【０２３８】
以上、図２７を参照して、本実施形態に係る情報処理装置１０が、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす極小元を探索する場合の、当該探索に係る処理の計算量について説明した。
【０２３９】
＜６．変形例＞
次に、本実施形態に係る情報処理システム１の変形例について説明する。
【０２４０】
［６．１．変形例１：一般化戦略の探索に係る処理負荷の軽減］
まず、変形例１として、図２８及び図２９を参照して、情報処理装置１０の解析部１４が、一般化戦略からなる束から（ｋ，ｔ）−匿名性を満たす一連の極小元を探索する処理の他の一例について説明する。図２８及び図２９は、変形例１に係る解析部１４の一連の処理の流れの一例について説明するための説明図である。
【０２４１】
図２８は、変形例１に係る解析部１４の一連の処理の一例を示した「All-MSS」関数のアルゴリズムを、所謂プログラムコードの形式で模式的に提示した図である。なお、図２８に示す例は、処理の流れをわかりやすくするために一部の情報を抽象化して示しており、必ずしも特定のプログラム言語のコンパイラに基づきコンパイルできる形式で示したものではない。また、図２９は、図２８に示した「All-MSS」関数の一連の処理の流れを示したフローチャートである。
【０２４２】
なお、変形例１に係る解析部１４は、図２０及び図２１を参照して前述した実施形態に係る解析部１４の処理の一部を変更することで、（ｋ，ｔ）−匿名性を満たす一連の極小元を探索する処理の処理量を低減している。
【０２４３】
具体的には、変形例１に係る解析部１４は、一般化ノードが（ｋ，ｔ）−匿名性を満たさないと判定した場合には、この（ｋ，ｔ）−匿名性を満たさない一般化ノードを、集合Ｅに加える。この（ｋ，ｔ）−匿名性を満たさない一般化ノードからは、いずれの要素をより具体化する方向にシフトさせたとしても、シフト後の一般化ノードが（ｋ，ｔ）−匿名性を満たさない。そこで、変形例１に係る解析部１４は、（ｋ，ｔ）−匿名性を満たす極小元を探索するための新たな基準点の候補を特定した際に、当該候補と集合Ｅとを比較することで、特定した新たな基準点の候補の中から集合Ｅに含まれる一般化ノードを事前に除く。このような構成により、変形例１に係る解析部１４は、（ｋ，ｔ）−匿名性の判定に係る処理（即ち、図１３に示した「kAnonymityCheck」関数）の実行回数をより低減し、（ｋ，ｔ）−匿名性を満たす一連の極小元を探索する処理の処理量を低減する。
【０２４４】
そこで、以降では、図２９を参照して、特に、図２１に示した処理とは異なる部分に着目して、より詳しく説明する。
【０２４５】
（ステップＳ１０１〜Ｓ１０５）
ステップＳ１０１〜Ｓ１０５に係る処理は、図２１に示した例と同様のため詳細な説明は省略する。即ち、極小元探索部１４３は、まず、一般化戦略からなる束の最大元を基準点として（ｋ，ｔ）−匿名性を満たす極小元を探索する。そして、基準点導出部１４５は、探索された極小元を離散集合から誘導される元に変換し、変換された元の補集合を、集合Ｃに代入する。
【０２４６】
（ステップＳ１０７’）
次いで、基準点導出部１４５は、変数Ｄで示された集合と、変数Ｅで示された集合とを、空集合で初期化する。
【０２４７】
（ステップＳ１０９）
基準点導出部１４５は、離散集合から誘導される束の元が示す正の整数の集合から、極小横断に相当する部分集合を抽出する関数Ｔｒに対して、導出した補集合Ｃを入力する。そして、基準点導出部１４５は、関数Ｔｒの出力として、補集合Ｃの極小横断に相当する部分集合Ｔｒ（Ｃ）を取得し、当該部分集合Ｔｒ（Ｃ）の要素のうち、集合Ｄに含まれない要素に対応する離散集合から誘導される束の元を、変数Ｘで示された元として抽出する。
【０２４８】
（ステップＳ１１１）
離散集合から誘導される束の元Ｘが存在する場合には（ステップＳ１０９、ＹＥＳ）、基準点導出部１４５は、「vec」関数に基づき、当該元Ｘに対応する、一般化戦略からなる束の一般化ノードｖを特定する。
【０２４９】
（ステップＳ１２１）
次に、基準点導出部１４５は、集合Ｅと、特定した一般化ノードｖとに基づき、ｗ≧ｖの関係を満たす集合Ｅの要素ｗ（即ち、一般化ノードｗ）が存在するか否かを判定する。
【０２５０】
（ステップＳ１２３）
ｗ≧ｖの関係を満たす集合Ｅの要素ｗが存在する場合には（ステップＳ１２１、ＹＥＳ）、基準点導出部１４５は、特定された一般化ノードｖの特定元である、離散集合から誘導される束の元Ｘ（即ち、「vec」関数に入力した元Ｘ）を集合Ｄに加える。
【０２５１】
（ステップＳ１１３）
ｗ≧ｖの関係を満たす集合Ｅの要素ｗが存在しない場合には（ステップＳ１２１、ＮＯ）、基準点導出部１４５は、特定された一般化ノードｖ（ｋ，ｔ）−匿名性を満たすか否かを判定する。なお、（ｋ，ｔ）−匿名性を満たすか否かの判定には、前述した「kAnonymityCheck」関数を適用すればよい。
【０２５２】
（ステップＳ１１５）
特定した一般化ノードｖが（ｋ，ｔ）−匿名性を満たす場合には（ステップＳ１１３、ＹＥＳ）、基準点導出部１４５は、当該一般化ノードｖを新たな基準点の候補として、極小元探索部１４３に出力する。
（ステップＳ１１７）
そして、基準点導出部１４５は、取得した極小元ｗに対応する、離散集合から誘導される束の元Ｖを特定し、特定した元Ｖの補集合を集合Ｃに加える。
【０２５３】
（ステップＳ１３１）
一方で、特定した一般化ノードｖが（ｋ，ｔ）−匿名性を満たさない場合には（ステップＳ１１３、ＮＯ）、基準点導出部１４５は、ｗ＜ｖの関係を満たす集合Ｅの要素ｗが存在するか否かを判定する。
【０２５４】
（ステップＳ１３３）
ｗ＜ｖの関係を満たす集合Ｅの要素ｗが存在する場合には（ステップＳ１３１、ＹＥＳ）、基準点導出部１４５は、集合Ｅから当該要素ｗを除き、特定した一般化ノードｖを加える（即ち、Ｅ←Ｅ＼｛ｗ｝∪｛ｖ｝）。
【０２５５】
（ステップＳ１３５）
また、ｗ＜ｖの関係を満たす集合Ｅの要素ｗが存在しな場合には（ステップＳ１３１、ＮＯ）、基準点導出部１４５は、集合Ｅに、特定した一般化ノードｖを加える。
【０２５６】
（ステップＳ１３５）
そして、基準点導出部１４５は、特定された一般化ノードｖの特定元である、離散集合から誘導される束の元Ｘ（即ち、「vec」関数に入力した元Ｘ）を集合Ｄに加える。
【０２５７】
（ステップＳ１０９）
以上のようにして、極小元探索部１４３及び基準点導出部１４５は、ステップＳ１１１〜Ｓ１３７に示された一連の処理を、部分集合Ｔｒ（Ｃ）の要素のうち、集合Ｄに含まれない要素に対応する離散集合から誘導される束の元Ｘが存在する限り継続する（ステップＳ１０９、ＹＥＳ）。
【０２５８】
そして、離散集合から誘導される束の元Ｘが存在しない場合には（ステップＳ１０９、ＮＯ）、極小元探索部１４３は、探索された一連の（ｋ，ｔ）−匿名性を満たす極小元それぞれに対応する一般化戦略を、解析結果出力部１５に出力する。以降の処理は、図２１に示した例と同様のため詳細な説明は省略する。
【０２５９】
以上、図２８及び図２９を参照して、変形例１に係る解析部１４が、一般化戦略からなる束から（ｋ，ｔ）−匿名性を満たす一連の極小元を探索する処理の他の一例について説明した。上記に説明したように、変形例１に係る解析部１４は、（ｋ，ｔ）−匿名性を満たす極小元を探索するための新たな基準点の候補を特定した際に、当該候補と集合Ｅとを比較することで、特定した新たな基準点の候補の中から集合Ｅに含まれる一般化ノードを事前に除く。このような構成により、変形例１に係る解析部１４は、（ｋ，ｔ）−匿名性の判定に係る処理（即ち、図１３に示した「kAnonymityCheck」関数）の実行回数をより低減し、（ｋ，ｔ）−匿名性を満たす一連の極小元を探索する処理の処理量を低減することが可能となる。
【０２６０】
［６．２．変形例２：システム構成の一例］
次に、変形例２として、本実施形態に係る情報処理システムのシステム構成の一例について説明する。
【０２６１】
例えば、図３０は、変形例２に係る情報処理システム１の一例について説明するための説明図である。図３０において、参照符号１０’は、前述した実施形態に係る情報処理装置１０（図１参照）に相当する。即ち、図３０に示す例は、前述した実施形態に係る情報処理装置１０を、複数の情報処理装置１０１〜１０ｎにより構成される分散処理システム１０’として実現した場合について示している。
【０２６２】
前述したように、本実施形態に係る情報処理装置１０は、ＤＢ５０に記憶されたテーブルｄ１０を解析することで一般化戦略の候補を探索し、管理者から指定された一般化戦略に基づきテーブルｄ１０を、より匿名性が向上したテーブルｄ３０に変換する。このような特性から、特に、解析の対象となる属性（即ち、一般化の対象となる属性）の数や、レコード数が増大するほど、情報処理装置１０の処理負荷は増大する。
【０２６３】
そのため、前述した実施形態に係る情報処理装置１０（図１参照）を、図３０に示すように、分散処理システム１０’として構成することで、個々の情報処理装置（即ち、情報処理装置１０１〜１０ｎ）の処理負荷を軽減してもよい。この場合には、図１０に示した情報処理装置１０の各構成のうち、特に、解析部１４やＤＢ情報変換部１７の処理を、複数の情報処理装置１０１〜１０ｎにより分散処理するとよい。
【０２６４】
また、図３１は、変形例２に係る情報処理システム１の一例について説明するための説明図であり、図３１において、参照符号５０’は、前述した実施形態に係るＤＢ５０（図１参照）に相当する。即ち、図３１に示す例は、前述した実施形態に係るＤＢ５０を、複数のＤＢ５０１〜５０ｍにより構成される分散ＤＢ５０’として実現した場合について示している。
【０２６５】
特に、所謂データベースに対するデータの入出力は、当該データベースを実現するためのハードウェア（例えば、サーバやストレージ）の入出力性能に依存し、当該入出力性能がボトルネックとなる場合もある。特に、本実施形態に係る情報処理システム１では、処理対象となるテーブルｄ１０のレコード数が増大するほど、テーブルｄ１０のデータ量は増大する。そのため、テーブルｄ１０のレコード数が増大するほど、ＤＢ５０を構成するハードウェアの入出力性能がボトルネックとなり、情報処理装置１０がＤＢ５０からテーブルｄ１０の情報を取得するための時間が増大する場合がある。
【０２６６】
そのため、前述した実施形態に係るＤＢ５０（図１参照）を、図３１に示すように、分散ＤＢ５０’として構成することで、ハードウェアの入出力性能に依存するボトルネックを解消してもよい。
【０２６７】
具体的な一例として、テーブルｄ１０中の各レコードを、分散ＤＢ５０’の各データベース５０１〜５０ｍに分散して管理してもよい。このような構成により、例えば、情報処理装置１０が、分散ＤＢ５０’からテーブルｄ１０の情報（特に、テーブルｄ１０の各レコード）を取得する際に、当該情報の取得に係る時間を最大で１／ｍに短縮することも可能となる。
【０２６８】
なお、図３１に示す例では、ＤＢ５０を分散ＤＢとして構成する例について説明したが、一般化ＤＢ４０（図１参照）を分散ＤＢとして構成してもよい。即ち、一般化ＤＢ４０を分散ＤＢとして構成することで、情報処理装置１０が、テーブルｄ１０の情報に基づき生成したテーブルｄ３０の情報を一般化ＤＢ４０に出力する際に、当該一般化ＤＢ４０へのテーブルｄ３０の情報の出力に係る時間を短縮することが可能となる。
【０２６９】
また、図３０及び図３１に示す構成を組み合わせてもよい。即ち、情報処理装置１０を分散処理システム１０’として構成し、ＤＢ５０を分散ＤＢ５０’として構成してもよい。もちろん、一般化ＤＢ４０を分散ＤＢとして構成してもよい。
【０２７０】
以上、図３０及び図３１を参照して、変形例２に係る情報処理システムのシステム構成の一例について説明した。
【０２７１】
＜７．ハードウェア構成＞
次に、図３２を参照して、本開示の実施形態に係る情報処理装置１０のハードウェア構成の一例について説明する。図３２は、本実施形態に係る情報処理装置１０のハードウェア構成の一例を示した図である。
【０２７２】
図３２に示すように、本実施形態に係る情報処理装置１０は、プロセッサ９０１と、メモリ９０３と、ストレージ９０５と、通信デバイス９１１と、バス９１５とを含む。また、情報処理装置１０は、操作デバイス９０７と、報知デバイス９０９とを含んでもよい。
【０２７３】
プロセッサ９０１は、例えばＣＰＵ（Central  Processing  Unit）、ＧＰＵ（Graphics  Processing  Unit）、ＤＳＰ（Digital  Signal  Processor）又はＳｏＣ（System  on  Chip）であってよく、情報処理装置１０の様々な処理を実行する。プロセッサ９０１は、例えば、各種演算処理を実行するための電子回路により構成することが可能である。なお、前述した解析部１４や、ＤＢ情報変換部１７は、プロセッサ９０１により実現され得る。
【０２７４】
メモリ９０３は、ＲＡＭ（Random  Access  Memory）及びＲＯＭ（Read  Only  Memory）を含み、プロセッサ９０１により実行されるプログラム及びデータを記憶する。ストレージ９０５は、半導体メモリ又はハードディスクなどの記憶媒体を含み得る。
【０２７５】
操作デバイス９０７は、ユーザが所望の操作を行うための入力信号を生成する機能を有する。操作デバイス９０７は、例えばボタン及びスイッチなどユーザが情報を入力するための入力部と、ユーザによる入力に基づいて入力信号を生成し、プロセッサ９０１に供給する入力制御回路などから構成されてよい。
【０２７６】
報知デバイス９０９は、出力デバイスの一例であり、例えば、液晶ディスプレイ（ＬＣＤ：Liquid  Crystal  Display）装置、有機ＥＬ（ＯＬＥＤ：Organic  Light  Emitting  Diode）ディスプレイなどのデバイスであってよい。この場合には、報知デバイス９０９は、画面を表示することにより、ユーザに対して所定の情報を報知することができる。
【０２７７】
また、他の一例として、報知デバイス９０９は、ＬＥＤ（Light  Emitting  Diode）のように、点灯又は点滅のパターンにより、所定の情報をユーザに報知するデバイスであってもよい。また、報知デバイス９０９は、スピーカ等のように、所定の音響信号を出力することで、所定の情報をユーザに報知するデバイスであってもよい。
【０２７８】
通信デバイス９１１は、本開示の実施形態に係る情報処理装置１０が備える通信手段であり、ネットワークを介して外部装置と通信する。通信デバイス９１１は、有線または無線用の通信インタフェースである。通信デバイス９１１を、無線通信インタフェースとして構成するバイには、当該通信デバイス９１１は、通信アンテナ、ＲＦ（Radio  Frequency）回路、ベースバンドプロセッサなどを含んでもよい。
【０２７９】
通信デバイス９１１は、外部装置から受信した信号に各種の信号処理を行う機能を有し、受信したアナログ信号から生成したデジタル信号をプロセッサ９０１に供給することが可能である。
【０２８０】
バス９１５は、プロセッサ９０１、メモリ９０３、ストレージ９０５、操作デバイス９０７、報知デバイス９０９、及び通信デバイス９１１を相互に接続する。バス９１５は、複数の種類のバスを含んでもよい。
【０２８１】
また、コンピュータに内蔵されるプロセッサ、メモリ、及びストレージなどのハードウェアを、上記した情報処理装置１０が有する構成と同等の機能を発揮させるためのプログラムも作成可能である。また、当該プログラムを記録した、コンピュータに読み取り可能な記憶媒体も提供され得る。
【０２８２】
＜８．まとめ＞
以上説明したように、本実施形態に係る情報処理装置１０は、処理対象となるテーブルｄ１０中の対象となる属性それぞれについて、当該属性の属性値を段階的により一般化されるように区分するための複数の分類に基づく、当該属性の一般化階層を取得する。そして、情報処理装置１０は、当該属性間における分類の組み合わせ（即ち、一般化階層の高さの組み合わせ）を元として、当該分類をより一般化（抽象化）する順序関係に基づき、一般化戦略からなる束を規定する。
【０２８３】
情報処理装置１０は、既定した一般化戦略からなる束のうち、（ｋ，ｔ）−匿名性を満たす元を基準点として、当該元の各要素のうち、いずれかの要素をより具体化する方向にシフトさせることで、（ｋ，ｔ）−匿名性を満たす極小元を探索する。
【０２８４】
（ｋ，ｔ）−匿名性を満たす極小元を探索したら、情報処理装置１０は、探索した当該極小元に基づき、新たな基準点を導出する。具体的には、情報処理装置１０は、特定した極小元を、離散集合から誘導される束の元に変換し、変換された元の補集合から極小横断を求め、当該極小横断に対応する一般化戦略からなる束の元のうち、（ｋ，ｔ）−匿名性を満たす元を新たな基準点の候補とする。
【０２８５】
そして、情報処理装置１０は、新たな基準点に基づく（ｋ，ｔ）−匿名性を満たす極小元を探索に係る処理と、当該探索の結果に基づく新たな基準点の導出に係る処理とを、新たな基準点の候補が導出されなくなるまで実行する。以上のようにして、情報処理装置１０は、（ｋ，ｔ）−匿名性を満たす一連の極小元を探索し、探索された一連の極小元それぞれに対応する一般化戦略を出力する。なお、探索された一連の極小元それぞれに対応する一般化戦略が、（ｋ，ｔ）−匿名性を満たすようにテーブルｄ１０を一般化し、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略に相当する。
【０２８６】
なお、（ｋ，ｔ）−匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略、即ち、（ｋ，ｔ）−匿名性を満たす一連の極小元を特定する処理は、所謂列挙問題に相当する。このような列挙問題を解く従来のアルゴリズムは、一般的にはヒューリスティックなアルゴリズムに相当し、計算量を事前に算出することが困難であった。
【０２８７】
これに対して、本実施形態に係る情報処理装置１０は、ハイパーグラフ双対化のアルゴリズムを、探索元（即ち、（ｋ，ｔ）−匿名性を満たす極小元）を列挙するために利用している。このようなハイパーグラフ双対化のアルゴリズムには、論理的な上限が与えられているものもある。そのため、本実施形態に係る情報処理装置１０が、（ｋ，ｔ）−匿名性を満たし、かつ、情報量の減少を最小限に抑えることが可能な一般化戦略を特定（列挙）する処理の計算量を事前に算出することが可能となる。
【０２８８】
また、本実施形態に係る情報処理装置１０に依れば、必ずしも全ての一般化戦略（即ち、一般化ノード）に対して、（ｋ，ｔ）−匿名性を満たすか否かの判定をおこなう必要はない。そのため、本実施形態に係る情報処理装置１０に依れば、一般化戦略からなる束から、（ｋ，ｔ）−匿名性を満たす一連の極小元を探索する（列挙する）処理の負荷を、低減することが可能となる。
【０２８９】
以上、添付図面を参照しながら本開示の好適な実施形態について詳細に説明したが、本開示の技術的範囲はかかる例に限定されない。本開示の技術分野における通常の知識を有する者であれば、特許請求の範囲に記載された技術的思想の範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、これらについても、当然に本開示の技術的範囲に属するものと了解される。
【０２９０】
また、本明細書に記載された効果は、あくまで説明的または例示的なものであって限定的ではない。つまり、本開示に係る技術は、上記の効果とともに、または上記の効果に代えて、本明細書の記載から当業者には明らかな他の効果を奏しうる。
【０２９１】
なお、以下のような構成も本開示の技術的範囲に属する。
（１）
プロセッサが、複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理を実行することと、
前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理を実行することと、
を含み、
プロセッサが、特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とを、前記新たな基準点が導出されなくなるまで実行し、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力する、情報処理方法。
（２）
前記匿名性は、前記テーブル中において、前記２以上の対象属性それぞれの前記属性値の組み合わせが等しい前記レコードの集合を示す等価クラスのうち、レコード数が所定の数ｋ未満の前記等価クラスに対応する前記レコードを、所定の数ｔ以下の範囲で削除した場合に、当該レコードを削除した後の前記テーブル中の前記レコードに基づく前記等価クラスのそれぞれについて、レコード数が前記所定の数ｋ以上となることを条件とする、前記（１）に記載の情報処理方法。
（３）
前記第２の束は、前記対象属性ごとの前記分類の数の和を最大とする正の整数の有限集合の冪集合を前記第２の元として、当該第２の元の包含関係を順序関係として規定される、前記（１）または（２）に記載の情報処理方法。
（４）
前記第１の束における前記第１の元それぞれと、前記第２の束における前記第２の元それぞれとは、前記第１の束の最大元と前記第２の束の最小元とが対応し、かつ、前記第１の束の最小元と前記第２の束の最大元と対応するように、前記第１の束及び前第２の束それぞれの順序関係に基づき、あらかじめ対応付けられる、前記（３）に記載の情報処理装置。
（５）
前記第２の束において、
前記対象属性それぞれには、前記正の整数の有限集合の各要素うち、互いに異なる複数の連続した正の整数に対応した要素が関連付けられ、
当該対象属性に対応する前記複数の分類それぞれは、前記複数の連続した正の整数に対応した当該要素に基づく有限集合の部分集合に対応付けられる、前記（３）または（４）に記載の情報処理装置。
（６）
前記第２の束において、
前記対象属性に対応する複数の分類それぞれは、より具体化された当該分類ほど、当該対象属性に関連付けられた前記複数の連続した正の整数に対応した要素のうち、より多くの当該要素が、値のより小さい要素から順次加えられた部分集合に対応付けられる、前記（５）に記載の情報処理装置。
（７）
前記極小横断に対応する前記第１の元は、当該極小横断に対して、前記対象属性ごとに、当該対象属性に関連付けられた前記複数の連続した正の整数に対応した要素のうち、当該極小横断が含む当該要素よりも値の小さい他の要素が補間された、正の整数の有限集合に対応する前記第２の元に基づき特定される、前記（６）に記載の情報処理装置。
（８）
最初に実行される前記探索処理では、前記第１の束の最大元を前記基準点として、前記極小元が探索される、前記（１）〜（７）のいずれか一項に記載の情報処理方法。
（９）
前記最大元は、前記第１の束のうち、前記２以上の対象属性それぞれの前記属性値を最も抽象化する前記分類の組み合わせに対応する前記第１の元である、前記（８）に記載の情報処理方法。
（１０）
前記探索処理では、前記基準点から、前記２以上の対象属性のうち少なくともいずれかに対応する前記分類がより具体化される方向に向けて、前記極小元が探索される、前記（１）〜（９）のいずれか一項に記載の情報処理方法。
（１１）
前記探索処理では、前記２以上の対象属性のうち少なくともいずれかに対応する前記分類を、より具体化される方向に向けた二分探索に基づき、前記極小元が探索される、前記（１０）に記載の情報処理装置。
（１２）
前記極小横断それぞれに対応する前記第１の元のうち、前記探索処理に基づき探索済みの前記第１の元は、前記新たな基準点の候補から除かれる、前記（１）〜（１１）のいずれか一項に記載の情報処理方法。
（１３）
前記極小横断は、前記補集合をハイパーエッジとするハイパーグラフの双対化に基づき特定される、前記（１）〜（１２）のいずれか一項に記載の情報処理方法。
（１４）
前記探索処理と前記基準点導出処理との少なくともいずれかは、複数のプロセッサにより分散処理される、前記（１）〜（１３）のいずれか一項に記載の情報処理方法。
（１５）
コンピュータに、
複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理と、
前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理と、
を実行させ、
特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とを、前記新たな基準点が導出されなくなるまで実行させる、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力させる、プログラム。
（１６）
複数の属性を含むレコードを複数含むテーブルの当該複数の属性のうち、少なくとも２以上の属性を対象属性として、当該対象属性が取り得る属性値それぞれが段階的により抽象化されるように区分する複数の分類の、前記２以上の対象属性間における各組み合わせを第１の元として、前記分類をより抽象化する順序関係に基づき規定される第１の束のうち、前記第１の元それぞれに対応する前記分類に基づき前記テーブルを抽象化した場合に、当該テーブルの前記レコード間で、所定の条件に基づく匿名性を満たす前記第１の元を基準点として、当該匿名性を満たす極小元を探索する探索処理を実行する極小元探索部と、
前記対象属性ごとの前記分類の数に基づき規定される有限集合の各部分集合を第２の元とし、当該第２の元の包含関係を順序関係として規定される第２の束のうち、探索された前記極小元にあらかじめ対応付けられた前記第２の元の補集合を特定し、当該補集合の極小横断それぞれに対応する前記第１の元のうち、前記匿名性を満たす第１の元を新たな前記基準点として導出する基準点導出処理を実行する基準点導出部と、
特定された前記新たな基準点に基づく前記探索処理と、当該探索処理により探索される前記極小元に基づく前記基準点導出処理とが、前記新たな基準点が導出されなくなるまで実行された結果に基づき、探索された一連の前記極小元それぞれが示す前記分類の組み合わせを、前記テーブルを抽象化するための条件の候補として出力する出力部と、
を備える、情報処理装置。
【符号の説明】
【０２９２】
１      情報処理システム
１０    情報処理装置
１１    ＤＢ情報取得部
１２    ＤＢ情報出力部
１３    階層情報取得部
１４    解析部
１４１  解析データ生成部
１４３  極小元探索部
１４５  基準点導出部
１５    解析結果出力部
１６    一般化条件取得部
１７    ＤＢ情報変換部
１８    変換結果出力部
３０    管理者端末
４０    一般化ＤＢ
５０    ＤＢ
６０    解析サーバ
７０    ＤＢサーバ
８０    クライアント
【図１】
2016053829.tif 000005
【図２】
2016053829.tif 000006
【図３】
2016053829.tif 000007
【図４】
2016053829.tif 000008
【図５】
2016053829.tif 000009
【図６】
2016053829.tif 000010
【図７】
2016053829.tif 000011
【図８】
2016053829.tif 000012
【図９】
2016053829.tif 000013
【図１０】
2016053829.tif 000014
【図１１】
2016053829.tif 000015
【図１２】
2016053829.tif 000016
【図１３】
2016053829.tif 000017
【図１４】
2016053829.tif 000018
【図１５】
2016053829.tif 000019
【図１６】
2016053829.tif 000020
【図１７】
2016053829.tif 000021
【図１８】
2016053829.tif 000022
【図１９】
2016053829.tif 000023
【図２０】
2016053829.tif 000024
【図２１】
2016053829.tif 000025
【図２２】
2016053829.tif 000026
【図２３】
2016053829.tif 000027
【図２４】
2016053829.tif 000028
【図２５】
2016053829.tif 000029
【図２６】
2016053829.tif 000030
【図２７】
2016053829.tif 000031
【図２８】
2016053829.tif 000032
【図２９】
2016053829.tif 000033
【図３０】
2016053829.tif 000034
【図３１】
2016053829.tif 000035
【図３２】
2016053829.tif 000036