(57)【要約】      （修正有）【課題】匿名化処理を効率化する情報処理装置を提供する。【解決手段】情報処理装置１０は、匿名化対象のデータである元データのレコードと元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、マッチンググラフにおいてレコード間の関係を示す辺を匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、抽出した近傍辺の情報をまとめた近傍辺リストを生成する辺抽出部１１と、近傍辺リストを基に、匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択する辺選択部１２と、選択された辺を匿名化マッチンググラフに追加する辺追加部１３と、辺を追加後の匿名化マッチンググラフを基に、近傍辺の候補を更新する辺更新部１４とを含む。【選択図】図１
2016115020.tif 000002
【特許請求の範囲】
【請求項１】
匿名化対象のデータである元データのレコードと、前記元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、前記マッチンググラフにおいてレコード間の関係を示す辺を、前記匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、前記抽出した近傍辺の情報をまとめた近傍辺リストを生成する辺抽出手段と、
前記近傍辺リストを基に、前記匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択する辺選択手段と、
前記選択された辺を前記匿名化マッチンググラフに追加する辺追加手段と、
前記辺を追加後の前記匿名化マッチンググラフを基に、近傍辺の候補を更新する辺更新手段と、
を含む情報処理装置。
【請求項２】
前記辺更新部が、
更新後の前記近傍辺の候補の数として、前記匿名化の匿名化強度から、前記匿名化マッチンググラフにおける前記匿名化データのレコードに張られた辺の数を引いた値を用いる
請求項１に記載の情報処理装置。
【請求項３】
前記辺更新部が、
前記近傍辺の候補の数として、固定の値を用いる
請求項１に記載の情報処理装置。
【請求項４】
前記辺抽出部が、
前記近傍辺の抽出に索引を用いる
請求項１ないし３のいずれ１項に記載の情報処理装置。
【請求項５】
前記辺抽出部が、
前記検索として、ｋｄ−ｔｒｅｅを用いる
請求項４に記載の情報処理装置。
【請求項６】
所定の匿名化強度を充足するまで、前記匿名化マッチンググラフに辺を追加する
請求項１ないし５のいずれか１項に記載の情報処理装置。
【請求項７】
匿名化対象のデータである元データのレコードと、前記元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、前記マッチンググラフにおいてレコード間の関係を示す辺を、前記匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、前記抽出した近傍辺の情報をまとめた近傍辺リストを生成し、
前記近傍辺リストを基に、前記匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択し、
前記選択された辺を前記匿名化マッチンググラフに追加し、
前記辺を追加後の前記匿名化マッチンググラフを基に、近傍辺の候補を更新する
情報処理方法。
【請求項８】
匿名化対象のデータである元データのレコードと、前記元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、前記マッチンググラフにおいてレコード間の関係を示す辺を、前記匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、前記抽出した近傍辺の情報をまとめた近傍辺リストを生成する処理と、
前記近傍辺リストを基に、前記匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択する処理と、
前記選択された辺を前記匿名化マッチンググラフに追加する処理と、
前記辺を追加後の前記匿名化マッチンググラフを基に、近傍辺の候補を更新する処理と
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理に関し、特に、個人の情報（プライバシー情報）を扱う情報処理装置、情報処理方法及びプログラムに関する。
【背景技術】
【０００２】
近年、様々なサービスにおいて、個人に関するプライバシー情報（個人情報）が、情報処理装置に蓄積されるようになっている。このようなプライバシー情報として、例えば、健康管理データ、診療履歴、又はレセプト（診療報酬明細書）のような、ヘルスケア（健康管理）に関するデータが、挙げられる。あるいは、プライバシー情報として、移動履歴又は無線アクセスポイントの利用履歴のような、人又は端末の移動又は滞在に関する位置の情報が、挙げられる。例えば、プライバシー情報であるレセプトは、生年、性別、傷病名、及び薬剤名といった属性のデータを含むレコードから構成されたデータセット（集合）として、情報処理装置に、蓄積される。このようなプライバシー情報は、プライバシー保護の観点から、オリジナルな情報（元の情報）内容で公開又は利用されることが、好ましくない。
【０００３】
ここで、生年又は性別のように個人を特徴付け、他の属性との組合せを基に個人を特定する可能性のある属性は、「準識別子」と呼ばれる。また、傷病名又は薬剤名のように、他人に知られたくない属性は、「センシティブ属性（機微情報：ＳＡ（Sensitive Attribute）、又は、ＳＡ（Sensitive Value）」」と呼ばれる。なお、名前のように単独で個人を特徴づける属性は、ユーザ識別子（ユーザＩＤ：User Identifier）となる。
【０００４】
このようなプライバシー情報は、プライバシー侵害の懸念がなければ、有益性の高い二次活用をもたらす。ここで、二次活用（二次利用）とは、例えば、プライバシー情報を生成又は蓄積しているサービス事業者とは異なる第三者にプライバシー情報を提供し、その第三者が、プライバシー情報をサービスで利用することである。あるいは、二次活用とは、第三者に対して、プライバシー情報を提供し、分析などのアウトソーシングを依頼することである。プライバシー情報の二次活用は、プライバシー情報の分析又は研究を促進し、分析結果又は研究結果を用いたサービスの強化につながる。したがって、二次活用を基に、第三者も、プライバシー情報の持つ高い有益性を享受することができる。
【０００５】
例えば、第三者として想定し得るものとして、製薬会社がある。製薬会社は、診療情報を基に、薬品の共起関係又は相関関係などを、分析できる。しかし、製薬会社にとって、診療情報を入手することは、一般的に、困難である。しかし、診療情報を用いると、製薬会社は、薬品がどのように利用されているのかを知ることができ、さらに、利用状態を分析することができる。
【０００６】
しかしながら、このようなプライバシー情報を含むデータセット（例えば、診療情報）は、プライバシー侵害の懸念から、積極的には、二次活用がなされていない。
【０００７】
例えば、サービスの利用者を一意に識別するユーザ識別子（ユーザＩＤ）と、１つ以上のセンシティブ情報とを含むレコードを含むデータセットが、サービス提供者の情報処理装置に蓄積されているとする。ここで、ユーザ識別子が付与されたままでセンシティブ情報を含むデータセットが第三者に提供された場合、その第三者は、ユーザ識別子を用いて、サービスの利用者を特定できる。そのため、このような提供では、プライバシー侵害の問題が、発生する可能性がある。
【０００８】
また、ユーザ識別子を取り除くが、準識別子を１つ以上含む複数のレコードを含むデータセットが、第三者に提供された場合について考える。この場合、第三者は、準識別子の組合せに基づいて、個人を特定できてしまう場合がある。すなわち、たとえ、ユーザ識別子を取り除いたデータセットでも、準識別子の組合せに基づいて、ある個人を特定可能な場合、プライバシー侵害が、発生する可能性がある。
【０００９】
このような特性を有するプライバシー情報のデータセットを、本来の有用性をある程度保ちながら、プライバシーを保護した形態に変換する技術が望まれている。このような技術として、匿名化技術（Anonymization）が知られている（例えば、特許文献１ないし４、非特許文献１及び２を参照。）。
【００１０】
特許文献２に記載の技術は、データの粒度を変更する匿名化に関する技術である。また、特許文献３に記載の技術は、距離的に近い（近傍）の候補の匿名化に関する技術である。また、特許文献４に記載の技術は、クラスタリングの匿名化に関する技術である。
【００１１】
特許文献２ないし４に記載の匿名化は、それぞれ有効であるが、広く用いられている匿名性の指標として“ｋ−匿名性”がある（例えば、非特許文献１及び特許文献１を参照）。
【００１２】
非特許文献１には、広く用いられる匿名性指標である“ｋ−匿名性”が、記載されている。ここで、ｋ−匿名性とは、全てのレコードに対し、匿名化対象のデータセットの中に、同じ準識別子（又は準識別子の組）を有するレコードが、少なくともｋ個以上存在することを保証する指標である。また、匿名化対象のデータセットに、係るｋ−匿名性を充足させる技術は、“ｋ−匿名化”と呼ばれる。つまり、ｋ−匿名化は、同じ準識別子（又は準識別子の組）を有するレコードが、匿名化対象のデータセットの中に少なくともｋ個以上存在するように、対象となるレコードの準識別子を変換する。ここで用いられる変換処理としては、一般化又は切り落とし等の処理が、知られている。一般化処理とは、元の（オリジナルの）詳細な情報を、抽象化された情報に変換する処理である。また、切り落とし処理とは、元の詳細な情報を削除する処理である。
【００１３】
また、特許文献１には、ｋ−匿名化を利用する技術が、記載されている。特許文献１に記載された技術は、ユーザ端末から受信したデータを、暗号化などを用いて変換してから格納し、格納したデータを復号してからｋ−匿名性を満たすよう加工して、サービス提供者のサーバに送信する。
【００１４】
上記のとおり、ｋ−匿名化は、同じ準識別子と関連付けられたレコードの数が、ｋ個以上となることを保証する匿名化である。言い換えると、ｋ−匿名化は、ｋ個以上のレコードを加工し、同一化することに基づいて、個人に対するレコードを、少なくともｋ個よりも少ない候補に絞り込むことができないように加工する。この動作を基に、ｋ−匿名化は、レコードの識別又は特定を困難にする。よって、ｋ−匿名性は、レコードの識別の困難さを表す指標とも言える。
【００１５】
図３は、プライバシー情報の一例を示す図である。図３に示すプライバシー情報は、属性として、名前（Name）、年齢（Age）、郵便番号（Zipcode）、及び病気（Disease）を含む。そして、例えば、名前（Name）の属性が、ユーザ識別子である。年齢（Age）及び郵便番号（Zipcode）の属性が、準識別子である。また、病気（Disease）の属性が、センシティブ属性である。
【００１６】
図４は、図３に示すプライバシー情報を、ｋ＝２としてｋ−匿名化した匿名化後の情報の一例を示す図である。図４に示す匿名化後の情報は、明示的な識別子（ユーザ識別子）である属性の名前（Name）が排除（削除）され、準識別子を加工されることで、ｋ＝２のｋ−匿名性が充足されている。図４では、図３に示すＡｌｉｃｅ、Ｂｏｂ、及びＣａｒｏｌのレコードが、同一の準識別子の組を持つように、準識別子が加工されている。同様に、Ｄａｖｉｄ及びＥｖｅのレコードは、同一の準識別子の組を持つように、準識別子が加工されている。具体的には、図４の匿名化において、属性の年齢（Age）の値は、範囲を表す値に加工されている。また、５つの桁を持つ属性の郵便番号（Zipcode）は、同一の値を持つ桁の値がそのまま残され、異なる値を持つ桁の値は、「＊」で置き換えられている。
【００１７】
このように、属性の値は、所定の匿名性を満たすために、曖昧な値に加工される。この属性の値を曖昧な値に加工する動作に基づいて、情報の損失が、生じる。この情報の損失の度合いは、“情報損失”、又は“情報損失量”と呼ばれる。また、情報損失の尺度として、ＮＣＰ（Normalized Certainty Penalty）、ＥＭ（Entropy Measure）、又はＤＭ（Distortion Metric）などの指標が、広く知られている。
【００１８】
ｋ−匿名性以外の匿名性指標として、（ｋ，１）−匿名性（(k,1)-anonymity）、（１，ｋ）−匿名性（(1,k)-anonymity）、（ｋ，ｋ）−匿名性 （(k,k)-anonymity）、ｋ−隠蔽性（k-concealment）という指標が、知られている（例えば、非特許文献２を参照）。
【００１９】
これらの匿名性指標は、元の情報であるデータセット（Ｔ）に含まれるレコード（ｔ）と、匿名化後のデータセット（Ｔ＊）に含まれるレコード（ｔ＊）とのマッチングに基づく、匿名性の指標である。ここで、ある匿名化作用素Ａを仮定し、その匿名化作用素Ａにおいて、“Ａ（ｔ）⊆ｔ＊”との関係が成り立つとき、ｔとｔ＊とは“マッチする”、又は、ｔとｔ＊とには、“マッチングが存在する”とする。なお、以下、「データセット」を単に「データ」と呼ぶ場合もある。また、「匿名化後のデータセット」を、単に、「匿名化データセット」又は「匿名化データ」と呼ぶ。なお、以下、匿名化の元となるプライバシー情報は、「元データ」又は「元データセット」と呼ぶ。なお、元データは、匿名化処理の対象となる。そのため、以下の説明において、元のデータからユーザ識別子を削除した状態のデータも、「元データ」と呼ぶ。
【００２０】
（ｋ，１）−匿名性とは、匿名化データ（Ｔ＊）の任意のレコード（ｔ＊）に、ｋ個以上の元データ（Ｔ）のレコード（ｔ）がマッチする（｜｛ｔ｜Ａ（ｔ）⊆ｔ＊｝｜≧ｋ）ことを保証する指標である。
【００２１】
図７は、図３に示すプライバシー情報を、ｋ＝２の（ｋ，１）−匿名性を充足するように匿名化した場合の、元データと匿名化データとのマッチングの一例を示す図である。
【００２２】
（１，ｋ）−匿名性とは、元データセット（Ｔ）の任意のレコード（ｔ）とｋ個以上の匿名化データ（Ｔ＊）のレコード（ｔ＊）とがマッチすることを保証する指標である。
【００２３】
図５は、図３に示すプライバシー情報（元データ）と、図３に示すプライバシー情報をｋ＝２の（１，ｋ）−匿名性を充足するように匿名化した匿名化データとのマッチングの一例を示す図である。図５において、例えば、Ａｌｉｃｅのレコードは、匿名化データの１番目及び３番目のレコードとマッチしている。このように、図５は、各元データのレコードと、ｋ個（ここではｋ＝２）の匿名化データのレコードとが、マッチすることを表している。
【００２４】
図６は、図５におけるマッチングを示すグラフ（匿名化マッチンググラフ）である。図６に示すように、元データと匿名化データのレコードとの間のマッチングは、元データ及び匿名化データの各レコードを頂点とし、マッチングを辺とする二部グラフで表すことができる。以下、この二部グラフを、匿名化マッチンググラフと呼ぶ。
【００２５】
（ｋ，ｋ）−匿名性とは、（ｋ，１）−匿名性と（１，ｋ）−匿名性との両方を、同時に満たすことを保証する指標である。
【００２６】
図８は、図３に示すプライバシー情報を、ｋ＝２の（ｋ，ｋ）−匿名性を充足するように匿名化した場合の、元データと匿名化データとのマッチングの一例を示す図である。
【００２７】
ｋ−隠蔽性とは、（ｋ，１）−匿名性のマッチングを構成する匿名化マッチンググラフの辺が、完全マッチングとなることを保証する指標である。
【００２８】
ここで、完全マッチングとは、マッチングを示す二部グラフの辺の集合が、すべての頂点を接続可能、かつ、端点を共有しない辺の集合となることである。
【００２９】
完全マッチングをより詳細に説明する。二部グラフにおいて、一方のデータを元データとし、他方のデータを匿名化データとする。そして、各レコードを頂点として、マッチングが存在するレコードの頂点間に辺を張り、二部グラフを構成する。ここで、１つの完全マッチングは、元データのレコードと匿名化データのレコードとの全単射となる。言い換えると、ある元データのレコードには、固有の匿名化データのレコードが存在するということである。
【００３０】
非特許文献２に記載の技術は、ｋ−隠蔽性を充足させる匿名化についての技術である。そして、非特許文献２に記載の匿名化は、マッチングに基づく匿名化である。非特許文献２に記載の技術は、まず、元データから、元データと同じ準識別子の組を持つ匿名化データを生成する。そして、非特許文献２に記載の技術は、元データのレコードと匿名化データのレコードとのマッチングに基づいて、完全マッチングの二部グラフを生成する。
【００３１】
この二部グラフに対する辺の追加は、追加された辺の端点となる元データのレコードとマッチングを成り立たせるように、他の端点である匿名化データのレコードを匿名化する操作に相当する。つまり、辺の追加に基づいて、匿名化データは、加工される。その結果、情報損失が、生じる。
【００３２】
非特許文献２に記載の匿名化技術は、次のように、辺を追加する３つのステップを用いて、情報損失が小さくなるように、ｋ−隠蔽性を充足させる。すなわち、非特許文献２に記載の技術は、第一のステップで、辺の追加を用いて、情報損失が小さい（ｋ，１）−匿名性を充足させる。そして、非特許文献２に記載の技術は、第二のステップで、辺の追加を用いて、情報損失が小さい（ｋ，ｋ）−匿名性を充足させる。そして、非特許文献２に記載の技術は、第三のステップで、辺の追加を用いて、情報損失が小さいｋ−隠蔽性を充足させる。
【先行技術文献】
【特許文献】
【００３３】
【特許文献１】特開２０１１−１８０８３９号公報
【特許文献２】特開２０１２−０２２３１５号公報
【特許文献３】特開２０１４−１０９９３４号公報
【特許文献４】特開２０１３−２３９１１８号公報
【非特許文献】
【００３４】
【非特許文献１】Latanya Sweeney, "k-Anonymity: A Model for Protecting Privacy", International Journal on Uncertainty, Fussiness and Knowledge-based Systems, Volume 10, Issue 05, pp.555-570, October 2002.
【非特許文献２】Tamir Tassa, Arnon Mazza and Aristodes Gionis, "k-Concealment: An Alternative Model of k-Type Anonymity", Transactions on Data Privacy, 5, pp. 189-222, 2012.
【発明の概要】
【発明が解決しようとする課題】
【００３５】
ここで、データセットが、Ｎ個のレコードを含むとする。この場合、非特許文献２に記載の（ｋ，１）−匿名性を満たす匿名化は、Ｎ個の匿名化データのレコードに対して、それぞれ、Ｎ−１個の元データのレコードからｋ−１個のレコードを選択し、選択したレコードに辺を張る（追加する）必要がある。このとき、辺の追加に基づく情報損失の小さい方からｋ−１個の辺が、選択されること望ましい。
【００３６】
これは、次のような理由のためである。新たに辺を１つ追加すると、追加された辺に対応して、匿名化データの属性値は、加工される。あるいは、匿名化データの属性値は、加工された状態が記録される。この加工に基づいて情報損失が、生じる。情報損失は、少ない方が望ましい。そのため、情報損失の小さな辺が、選択されることが望ましいためである。
【００３７】
非特許文献２において、情報損失の小さい辺を明らかにするために、追加の候補となる辺（候補辺）は、その候補辺を匿名化データのレコードに追加した場合に生じる情報損失を示す値（以下、情報損失の値をコストと呼ぶ）を持っている。非特許文献２に記載の（ｋ，１）−匿名性を満たす匿名化技術は、このコストに基づいて、追加する辺を選択する。
【００３８】
また、辺の追加に基づき、匿名化データのレコードの属性値は、加工される。そのため、辺の追加に基づき、各辺のコストが、変化する。そのため、辺の追加に伴い、辺のコストを更新する必要が生じる。
【００３９】
非特許文献２の（ｋ，１）−匿名性を満たす匿名化の技術は、１つのレコードにｋ−１本の辺を張るために、すべてのレコードを対象として、コストの計算及び更新を行う。非特許文献２の（ｋ，１）−匿名性を満たす匿名化の技術は、コストの計算及び更新を、Ｎ個の全てのレコードに対して行う必要がある。つまり、非特許文献２に記載の技術は、匿名化の処理として、Ｏ（ｋｎ２）程度の計算コストが必要である。ここで、Ｏ（・）は、計算理論に用いられるランダウのＯ−記法である。
【００４０】
このように、非特許文献２に記載の技術は、データ数の増加に伴って計算時間が非常に大きくなってしまうという問題点があった。
【００４１】
なお、特許文献１ないし４及び非特許文献１に記載の技術は、匿名化の方法が異なるため、上記問題点を解決できない。
【００４２】
本発明の目的は、上記の問題点を解し、匿名性の処理を効率化する情報処理装置、情報処理方法及びプログラムを提供することにある。
【課題を解決するための手段】
【００４３】
本発明の一形態における情報処理装置は、匿名化対象のデータである元データのレコードと、元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、マッチンググラフにおいてレコード間の関係を示す辺を、匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、抽出した近傍辺の情報をまとめた近傍辺リストを生成する辺抽出手段と、近傍辺リストを基に、匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択する辺選択手段と、選択された辺を匿名化マッチンググラフに追加する辺追加手段と、辺を追加後の匿名化マッチンググラフを基に、近傍辺の候補を更新する辺更新手段と、を含む。
【００４４】
本発明の一形態におけるデータ処理方法は、匿名化対象のデータである元データのレコードと、元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、マッチンググラフにおいてレコード間の関係を示す辺を、匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、抽出した近傍辺の情報をまとめた近傍辺リストを生成し、近傍辺リストを基に、匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択し、選択された辺を匿名化マッチンググラフに追加し、辺を追加後の匿名化マッチンググラフを基に、近傍辺の候補を更新する。
【００４５】
本発明の一形態におけるプログラムは、匿名化対象のデータである元データのレコードと、元データの匿名化後のデータである匿名化データのレコードとの関連を示すグラフである匿名化マッチンググラフを基に、マッチンググラフにおいてレコード間の関係を示す辺を、匿名化マッチンググラフに追加した場合の情報損失の量を示すコストが低い方から所定の数の辺である近傍辺を抽出し、抽出した近傍辺の情報をまとめた近傍辺リストを生成する処理と、近傍辺リストを基に、匿名化データに含まれるレコードに対する近傍辺の候補から、最もコストが低い辺である最近傍辺を選択する処理と、選択された辺を匿名化マッチンググラフに追加する処理と、辺を追加後の匿名化マッチンググラフを基に、近傍辺の候補を更新する処理とをコンピュータに実行させる。
【発明の効果】
【００４６】
本発明に基づけば、匿名性の処理を効率化するとの効果を奏することができる。
【図面の簡単な説明】
【００４７】
【図１】図１は、本発明における第１の実施の形態に係る情報処理装置の構成の一例を示すブロック図である。
【図２】図２は、第１の実施の形態に係る情報処理装置の別の構成の一例を示すブロック図である。
【図３】図３は、プライバシー情報の一例を示す図である。
【図４】図４は、図３に示すプライバシー情報を、ｋ＝２としてｋ−匿名化した匿名化後の情報の一例を示す図である。
【図５】図５は、図３に示すプライバシー情報と、図３に示すプライバシー情報をｋ＝２の（１，ｋ）−匿名性を充足するように匿名化した匿名化データとのマッチングの一例を示す図である。
【図６】図６は、図５におけるマッチングを示す匿名化マッチンググラフである。
【図７】図７は、図３に示すプライバシー情報を、ｋ＝２の（ｋ，１）−匿名性を充足するように匿名化した場合の、元データと匿名化データとのマッチングの一例を示す図である。
【図８】図８は、図に示すプライバシー情報を、ｋ＝２の（ｋ，ｋ）−匿名性を充足するように匿名化した場合の、元データと匿名化データとのマッチングの一例を示す図である。
【図９】図９は、初期状態の匿名化マッチンググラフの一例を示す図である。
【図１０】図１０は、第１の実施形態の説明に用いるコストグラフの一例を示す図である。
【図１１】図１１は、第１の実施形態の説明に用いる近傍辺リストの一例を示す図である。
【図１２】図１２は、ｋ−１近傍辺を示すコストグラフである。
【図１３】図１３は、レコード１の近傍辺と、近傍辺のコストとを示す図である。
【図１４】図１４は、更新後の匿名化マッチンググラフを示す図である。
【図１５】図１５は、更新後のコストグラフである。
【図１６】図１６は、第１の実施の形態に係る辺更新部における近傍辺リストの更新を示す図である。
【図１７】図１７は、更新したコストを反映したコストグラフである。
【図１８】図１８は、更新後の匿名化マッチンググラフである。
【図１９】図１９は、更新後のコストグラフである。
【図２０】図２０は、更新後の匿名化マッチンググラフである。
【図２１】図２１は、更新後のコストグラフである。
【図２２】第１の実施の形態に係る情報処理装置の動作の一例を示したフローチャートである。
【発明を実施するための形態】
【００４８】
次に、本発明の実施の形態について、図面を参照して詳細に説明する。
【００４９】
なお、各図面は、本発明の実施形態を説明するものである。ただし、本発明は、各図面の記載に限られるわけではない。また、各図面の同様の構成には、同じ番号を付し、その繰り返しの説明を、省略する場合がある。
【００５０】
また、以下の説明に用いる図面において、本発明の説明に関係しない部分の構成については、記載を省略し、図示しない場合もある。
【００５１】
（第１の実施の形態）
ここで、まず、本発明における第１の実施の形態の説明における前提及び用語について整理する。
【００５２】
本実施の形態における匿名化の対象のデータセット（元データ）は、オリジナルな情報内容を公開又は利用されることが好ましくない属性（センシティブ属性）を含むデータセットである。このデータセットは、１つ以上の属性を含むレコードの集合である。そして、レコードが、少なくとも１つ以上のセンシティブ属性を含む。本実施の形態は、レコードが含むセンシティブ情報に関連する個人を特定されないようにデータセット（元データ）を匿名化し、匿名化後のデータセット（匿名化データ）を生成する。
【００５３】
また、本実施形態が扱う匿名性は、特に制限はない。ただし、以下の説明では、本実施の形態は、匿名性の一例として、（ｋ，１）−匿名性を用いて説明する。また、ｋの値に制限はない。ただし、以下の説明では、一例として、ｋ＝４を用いる。つまり、匿名化強度は、「４」である。
【００５４】
また、データセットが含むレコードの数は、特に制限はない。ただし、以下の説明では、データセットは、５つのレコードを含む。また、レコードの変数として、“ｔ”を用いる。元データのｉ番目のレコードは、ｔｉである。匿名化データのｉ番目のレコードは、ｔ＊ｉである。また、元データ及び匿名化後データの、各レコードの集合を、（Ｔ）及び（Ｔ＊）とする。
【００５５】
「匿名化マッチンググラフ」とは、元データのレコード（ｔ）と匿名化データのレコード（ｔ＊）とのマッチングを示すグラフである。本実施の形態が扱うグラフは、元データのレコード（ｔ）と匿名化データのレコード（ｔ＊）とのマッチングを示すことができれば、特に制限はない。ただし、以下の説明において、本実施の形態は、匿名化マッチンググラフの一例として、二部グラフを用いる。二部グラフを用いた場合、匿名化マッチンググラフにおいて、頂点は、レコードを示す。また、頂点を結ぶ辺が、レコード（頂点）間のマッチングを示す。つまり、辺の端点は、レコードである。そして、辺は、変数「ｅ」及び頂点（端点）となるレコードを用いて示す。例えば、レコードｔ１とｔ＊２とのマッチングを示す辺は、辺ｅ（ｔ１、ｔ＊２）である。なお、匿名化マッチンググラフへの辺の追加は、辺を張るとも呼ぶ。このように、グラフにおける辺は、マッチング関係を示す要素である。
【００５６】
また、初期状態の匿名化マッチンググラフは、元データセットのレコードｔと匿名化データセットのレコードｔ＊との１対１マッチング状態の二部グラフとする。つまり、各レコードは、初期状態で１つ辺が張られている。そのため、（ｋ，１）−匿名性を充足させるためには、本実施形態は、レコードｔ＊に、ｋ−１個の辺を追加する。
【００５７】
図９は、初期状態の匿名化マッチンググラフの一例を示す図である。
【００５８】
「辺の追加」とは、匿名化マッチングに含まれるレコード間に、新たな辺を追加することである。
【００５９】
「コスト」とは、辺を、匿名化マッチンググラフに追加する場合に発生する情報損失である。なお、追加のコストが低い辺を、「近い辺」又は「近傍の辺」と呼ぶ。例えば、近傍の辺とは、比較となる他の辺に比べ、追加する場合のコストが低い辺である。
【００６０】
「コストグラフ」とは、あるレコードと他のレコードとのコスト（そのレコード間の辺を追加した場合の情報損失）を表すグラフである。例えば、コストグラフは、あるレコードを中心に示し、他のレコードをそのレコードからコストに比例した距離に配置して示す。つまり、コストグラフにおけるレコード間の距離は、コストを示す。例えば、コストグラフにおいて距離が近いレコードは、そのレコード間の辺を加える場合のコストが、低い。なお、本実施形態は、元データのレコードと匿名化データのレコードの辺を扱う。そのため、コストグラフが示すコストは、匿名化データのレコードと元データのレコードの辺に対するコストである。
【００６１】
図１０は、本実施形態の説明に用いるコストグラフの一例を示す図である。図１０に示すコストグラフは、匿名化データのレコード１（ｔ＊１）に対する、元データのレコード２（ｔ２）ないしレコード５（ｔ５）のコストを示している。図１０において、各丸が、レコードを示す。ただし、中央の１を付した丸が、匿名化データのレコード１（ｔ＊１）である。その他の４つの丸が、元データのレコード（ｔ２ないしｔ５）である。
【００６２】
「矩形Ｒ（ｔ＊）」は、コストグラフにおいて、匿名化データのレコード（ｔ＊）を基に形成された矩形である。矩形Ｒ（ｔ＊）は、匿名化される範囲のレコードを示す。なお、上記のとおり、初期状態は、元データのレコードと匿名化データのレコードとが、繋がった状態である。そのため、矩形Ｒ（ｔ＊）の初期状態は、コストグラフにおける１つの匿名化データのレコード（ｔ＊）を含む矩形である。
【００６３】
「集合Ｏ（ｔ＊）」は、匿名化データセットの匿名化データのレコードｔ＊に張られた辺の他の端点となっている元データのレコード（ｔ）の集合である。
【００６４】
例えば、匿名化データセットのレコードｔ＊１が、元データセットのレコードｔ１及びｔ２への辺を持つ場合は、次のようになる。すなわち、Ｒ（ｔ＊１）は、ｔ＊１（又は、ｔ１してもよい）とｔ２とを含むＭＢＲ（Minimum Bounding Rectangle）となる。また、Ｏ（ｔ＊１）は、Ｏ（ｔ＊１）＝｛ｔ１，ｔ２｝となる。ここで、｛｝は、集合の要素を示す。
【００６５】
ここで、匿名化データのレコードｔ＊に、元データのレコードとの新たに辺を追加する場合を考える。ただし、匿名化データのレコードｔ＊は、既に、辺が追加されているとする。例えば、上記のように、匿名化データのレコードｔ＊１が、元データのレコードｔ１及びｔ２に辺が張られているとする。つまり、矩形Ｒ（ｔ＊１）が、Ｏ（ｔ＊１）＝｛ｔ１，ｔ２｝からなるＭＢＲが形成済みとする。このとき、匿名化データのレコードｔ＊１に辺を追加するコストは、矩形Ｒ（ｔ＊１）に対して、辺を追加するコストとなる。例えば、辺を追加するレコードｔ４のコストが、レコードｔ＊１に対して辺を追加するコストより、レコードｔ＊２に対して辺を追加するコストの方が低いとする。つまり、レコードｔ４は、レコードｔ＊１よりレコードｔ＊２に近いとする。この場合、レコードｔ４に辺を追加するコストは、レコードｔ＊１に対するコストではなく、レコードｔ＊２に対するコストとなる。
【００６６】
また、情報損失は、少ない方が望ましい。つまり、辺の追加で発生するコストは、低い方が望ましい。つまり、追加する辺としては、近傍の辺が、望ましい。反対に、Ｒ（ｔ＊１）、つまりレコードｔ１及びｔ２から遠いレコードを端点とする辺は、追加コストが高く、追加が望ましくない。
【００６７】
そこで、レコードｔ＊に新たに追加する辺の候補の集合である候補辺集合μ（ｔ＊）は、レコードｔとして、Ｏ（ｔ＊）の所定範囲、つまり、近傍辺の集合を考えればよい。
【００６８】
「ｋ−１近傍辺」とは、あるレコードに対し、コストが低い（情報損失が少ない）辺を上位とした場合において、上位の１番からｋ−１番までの辺のことである。本実施形態は、候補辺集合μ（ｔ＊）として、ｋ−１近傍辺の集合を用いる。
【００６９】
「近傍辺リスト」とは、レコード（頂点）から所定の数の上位の近傍辺の情報を保存するリストである。なお、近傍辺リストは、各レコードに対する近傍辺の情報を保存すればよい。そのため、近傍辺リストは、辺の情報として、各レコードに対して、辺の他方の端点となる頂点（レコード）を保存する。
【００７０】
「ｋ−１近傍辺リスト」とは、上位ｋ−１個を近傍辺のリストである。近傍辺リストの各レコードに対応する辺の集合が、その辺に対する候補辺集合μ（ｔ＊）となる。なお、ここで「ｋ−１」となるのは、各レコードは、初期状態で、１つの辺が張られているためである。
【００７１】
図１１は、本実施の形態の説明に用いる近傍辺リストの一例を示す図である。図１１に示す近傍辺リストは、ｋ＝４の場合のｋ−１近傍辺リストである。図１１において、ＩＤは、レコードの番号である。例えば、図１１に示す近傍辺リストの１行目は、匿名化データのレコード１（ｔ＊１）の上位３（＝４−１）個の近傍辺が、辺ｅ（ｔ＊１、ｔ２）、辺ｅ（ｔ＊１、ｔ３）、及び辺ｅ（ｔ＊１、ｔ４）であることを示す。
【００７２】
次に、図面を参照して、本発明における第１の実施形態について説明する。
【００７３】
図１は、本発明における第１の実施の形態に係る情報処理装置１０の構成の一例を示すブロック図である。
【００７４】
情報処理装置１０は、元データと匿名化データとのマッチングを表す匿名化マッチンググラフを処理対象とする。より詳細には、情報処理装置１０は、所定の匿名性（匿名化強度）を充足するように、二部グラフ形式で表された匿名化マッチンググラフにおける辺を処理し、匿名化マッチンググラフを更新する。
【００７５】
そのため、図１に示すように、情報処理装置１０は、辺抽出部１１と、辺選択部１２と、辺追加部１３と、辺更新部１４とを含む。
【００７６】
辺抽出部１１は、匿名化データに対するｋ−１近傍辺を抽出する。つまり、辺抽出部１１は、近傍辺リストを生成する。
【００７７】
辺選択部１２は、近傍辺リスト又は近傍辺の集合から、追加する辺を選択する。近傍辺の集合については、後述する。
【００７８】
辺追加部１３は、選択された辺を匿名化マッチンググラフに追加する。
【００７９】
辺更新部１４は、追加された辺を基に、近傍辺の集合を更新する。
【００８０】
次に、図面を参照して、情報処理装置１０の各構成の詳細について説明する。
【００８１】
以下の説明は、図９に示す匿名化マッチンググラフを初期状態とする。そして、説明の対象を匿名化データのレコードｔ＊１とする。つまり、情報処理装置１０は、元データＴ＝｛ｔ１，ｔ２，ｔ３，ｔ４，ｔ５｝に対して、匿名化データのレコードｔ＊１から張られる辺を処理の対象とする。
【００８２】
辺抽出部１１は、匿名化データのレコードに対する、ｋ−１近傍辺を抽出し、近傍リストを生成する。
【００８３】
辺抽出部１１は、ｋ−１近傍辺を抽出するために、コストを用いる。すなわち、辺抽出部１１は、ｋ−１近傍辺のための計算として、元データのレコードと匿名化データのレコードと全ての組合せとなる辺に対して、その辺を匿名化マッチンググラフに追加する場合に生じる情報損失（コスト）を計算する。そして、辺抽出部１１は、ｋ−１近傍辺として、それぞれの匿名化データのレコードに対する計算結果の中から、コストが低い方からｋ−１個の辺を抽出する。ここで、ｋ−１個となるのは、既に説明した通り、初期状態の辺を除いているためである。
【００８４】
辺抽出部１１は、情報損失の計算として、各種の計算を用いることができる。例えば、辺抽出部１１は、コストグラフにおけるレコード間の距離計算、又は、類似度計算を用いてもよい。
【００８５】
また、辺抽出部１１は、それらの計算において、計算を高速化する手法、例えば、索引を用いてもよい。ここでの索引とは、データベースの分野において用いられている索引のことであるである。この索引は、インデックス（Index）とも呼ばれ、データを保存する表への処理（特にデータを取り出す処理）を高速化するためのデータ構造である。
【００８６】
さらに、辺抽出部１１は、索引に用いるデータ構造として、木構造（例えば、Ｂ−木（Binary tree or Balanced tree）又はｋｄ−木（kd-tree：k dimensional-tree））を用いてもよい。
【００８７】
ここで、初期状態における匿名化データのレコードｔ＊ｉのｋ−１近傍辺の集合をη（ｔ＊ｉ）とする。なお、η（ｔ＊ｉ）は、コストに基づいて順序付けされたリストで表されても良い。
【００８８】
図１０は、匿名化データのレコードｔ＊１における、全ての元データのレコードとの辺のコストを表すコストグラフである。ただし、図１０は、既に説明した通り、初期状態で張られている辺ｅ（ｔ１，ｔ＊１）を表示していない。
【００８９】
図１１は、すべての匿名化データのレコードに対するｋ−１近傍辺の集合η（ｔ＊ｉ）を列挙した近傍辺リストである。ただし、既に説明した通り、ｋの値は、ｋ＝４である。図１１は、各辺を端点のレコード用いて示している。例えば、図１１の１行目は、辺ｅ（ｔ＊１、ｔ２）と、辺ｅ（ｔ＊１、ｔ３）と、辺ｅ（ｔ＊１、ｔ４）とを示す。また、図１１に示すｋ−１近傍辺は、左から、コストの低い順に、コストに基づいて順序付けされて示されている。
【００９０】
図１２は、図１１の１行目に示す匿名化データのレコードｔ＊１のｋ−１近傍辺を示すコストグラフである。
【００９１】
辺選択部１２は、（ｋ，１）−匿名性を充足させるために、近傍辺リスト又は後ほど説明する近傍辺の集合を基に、匿名化データのレコードｔ＊１から元データのレコード（ｔ）に対して追加する辺（最近傍辺β）を選択する。辺選択部１２は、コストがより低い辺を選択することが望ましい。
【００９２】
例えば、図１１に示す近傍辺リストは、コストの順に辺を並べている。そのため、辺選択部１２は、レコードｔ＊１に対して選択する最近傍辺βとして、匿名化データのレコードｔ＊１から元データのレコードｔ２への辺ｅ（ｔ２，ｔ＊１）を選択する。
【００９３】
辺追加部１３は、辺選択部１２が選択した辺（最近傍辺β）を匿名化マッチンググラフに追加する。辺追加部１３は、一般的な二部グラフへの辺追加の処理を用いて辺を追加すればよい。そのため、辺追加部１３の詳細な説明を省略する。
【００９４】
辺更新部１４は、辺追加部１３に基づく辺の追加に対応し、近傍辺の集合を抽出し、さらに近傍辺の集合を更新する。
【００９５】
辺更新部１４の処理をさらに詳細に説明する。
【００９６】
初期状態において、図９に示すように、元データのレコード（ｔｉ）と匿名化データのレコード（ｔ＊ｉ）とが、辺を作っている。つまり、元データのレコードの集合Ｏ（ｔ＊ｉ）の要素は、（Ｏ（ｔ＊ｉ）＝｛ｔｉ｝）である。また、ｔ＊ｉに張る辺の候補辺集合μ（ｔ＊ｉ）は、ｋ−１近傍辺の集合η（ｔ＊ｉ）である。
【００９７】
ここで、候補辺集合μ（ｔ＊ｉ）から選択された辺、つまり、コストが最も低い（最小）である最近傍辺βが、β＝（ｔｊ，ｔ＊ｉ）とする。
【００９８】
最近傍辺βをレコードｔｊとレコードｔ＊ｉと間に張ると、集合Ｏ（ｔ＊ｉ）の要素は、Ｏ（ｔ＊ｉ）＝｛ｔｉ，ｔｊ｝となる。矩形Ｒ（ｔ＊ｉ）は、ｔ＊ｉとｔ＊ｊとを含むＭＢＲである。また、ｔ＊ｉの候補辺集合μ（ｔ＊ｉ）は、μ（ｔ＊ｉ）＝μ（ｔ＊ｉ）∪η（ｔ＊ｊ）＼ｔｊとなる。ここで、“＼”は、差集合を示す。
【００９９】
そして、辺更新部１４は、上記の新たな候補辺集合μ（ｔ＊ｉ）に基づいて、コストを再計算（更新）する。より具体的には、辺更新部１４は、矩形Ｒ（ｔ＊ｉ）と各レコードとの距離（コスト）を再計算（更新）する。
【０１００】
そして、辺更新部１４は、コストの計算後、ｋ−１近傍辺の集合η（ｔ＊ｉ）において、コストが低い方から上位ｋ−｜Ｏ（ｔ＊ｉ）｜番目までの辺を残す。つまり、辺更新部１４は、ｋ−１近傍辺の集合η（ｔ＊ｉ）において、コストが低い方の順番がｋ−｜Ｏ（ｔ＊ｉ）｜を超えた辺を削除する。ここで、｜Ｏ（ｔ＊ｉ）｜は、集合Ｏ（ｔ＊ｉ）の要素の数を表す。
【０１０１】
なお、境目となるコストの値が同じ辺が、複数ある場合、辺更新部１４は、コストを用いた判断では、残す辺をｋ−｜Ｏ（ｔ＊ｉ）｜個に絞れない。その場合、辺更新部１４は、同じ値の辺を、全て、ｋ−１近傍辺の集合η（ｔ＊ｉ）に残してもよい。あるいは、辺更新部１４は、所定の手法（例えば、ランダムに選択、又はラウンドロビン）を用いて、上記の数となるように辺を選択してもよい。
【０１０２】
なお、本実施の形態は、必ずしも、ｋ−１近傍辺の集合η（ｔ＊ｉ）の要素の数を更新しなくてもよい。つまり、本実施の形態は、ｋ−１近傍辺の集合η（ｔ＊ｉ）の要素を、上位のｋ−｜Ｏ（ｔ＊ｉ）｜個に絞らなくてもよい。また、例えば、辺更新部１４は、計算の簡単化のために、常に、上位ｋ−１件を残してもよい。
【０１０３】
情報処理装置１０は、上記の処理を、指定された匿名化強度、つまり、（ｋ、１）−匿名性を充足するまで繰り返す。
【０１０４】
次に、図面を参照して、情報処理装置１０が、匿名化データのレコードｔ＊１にｋ−１本の辺を追加する動作ついて説明する。以下、既に説明した内容も含むが、煩雑さを避けるため、繰り返しであることの説明を省略する。
【０１０５】
初期状態の匿名化マッチンググラフは、図９に示すとおりである。
【０１０６】
また、初期状態における、ｔ＊１に対する各レコードのコストは、図１０に示すコストグラフのとおりである。
【０１０７】
辺抽出部１１は、近傍辺リストを抽出する。図１１に示す近傍辺リストは、このとき抽出される近傍辺リストである。
【０１０８】
また、図１２は、ｔ＊１に関するｋ−１近傍の辺と、各辺のコストとを示したコストグラフである。図１２において、近傍辺リストに含まれない辺（辺ｅ（ｔ５、ｔ＊１））は、表示されていない。
【０１０９】
辺選択部１２は、コストを基に、追加する辺（最近傍辺β）を選択する。
【０１１０】
図１３は、図１１に示す近傍辺リストから、レコード１（ｔ＊１）の近傍辺と、近傍辺のコストと合わせて示した図である。
【０１１１】
図１３から明らかなとおり、辺選択部１２は、最近傍辺βとして、コストが最も低い辺ｅ（ｔ２，ｔ＊１）を選択する。
【０１１２】
辺追加部１３は、選択された辺を、匿名化マッチンググラフに追加する。
【０１１３】
図１４は、辺追加部１３が、辺選択部１２が選択した辺ｅ（ｔ２，ｔ＊１）を匿名化マッチンググラフに追加した後の、更新後の匿名化マッチンググラフを示す図である。
【０１１４】
その後、辺更新部１４は、近傍辺リストを更新する。
【０１１５】
図１５は、辺更新部１４の更新処理に伴い、更新されたコストを示すコストグラフである。図１５は、Ｒ（ｔ＊１）として、レコード１とレコード２とを含む矩形を示す。また、図１５は、レコード２からの辺を破線で示す。例えば、レコード１とレコード４の辺のコストは、０．４である。レコード２とレコード４の辺のコストは、０．２である。つまり、Ｒ（ｔ＊１）に対するレコード４のコストは、０．２である。
【０１１６】
図１６は、辺更新部１４における近傍辺リストを基に作成した近傍辺の集合の更新を示す図である。
【０１１７】
既に説明した通り、辺抽出部１１が、近傍辺リスト１６１を抽出する。辺選択部１２が、候補辺集合μ（ｔ＊１）（今の場合、近傍辺の集合η（ｔ＊１）は、図１６に示す表１６２）を基に、最もコストが低いレコード２を選択する。辺追加部１３が、レコード２に関する辺を匿名化マッチンググラフに追加する。
【０１１８】
辺更新部１４は、Ｒ（ｔ＊１）を基に、近傍辺の集合η（ｔ＊１）を更新する。具体的な、辺更新部１４は、次のように動作する。
【０１１９】
辺更新部１４は、近傍辺の集合（表１６２）からレコード２を削除する。そして、辺更新部１４は、レコード２の近傍辺の集合（表１６３）を抽出する。そして、辺更新部１４は、レコード１に近傍辺の集合（表１６２）とレコード２の近傍辺の集合（表１６３）との和集合（表１６４）を作成する。複数の表に同じレコードが含まれる場合、辺更新部１４は、最小のコストを選択する。そして、辺更新部１４は、コストが低い方から、２個のレコードを選択し、更新した近傍辺の集合（表１６５）とする。つまり、図１６に示す表１６５は、更新された近傍辺の集合である。辺選択部１２は、更新された近傍辺の集合から辺を選択する。
【０１２０】
ここで、辺更新部１４が、２個のレコードを選択するのは、次の理由のためである。レコード２に関する辺が追加されたため、集合Ｏ（ｔ＊１）は、Ｏ（ｔ＊１）＝｛ｔ１，ｔ２｝となっている。つまり、｜Ｏ（ｔ＊ｉ）｜の値は、２である。また、ｋの値は、４である。そのため、近傍辺の集合のレコード数は、ｋ−｜Ｏ（ｔ＊ｉ）｜＝２となるためである。
【０１２１】
図１７は、更新したコストを反映したコストグラフである。なお、図１７において、削除した辺ｅ（ｔ３，ｔ＊１）を一点鎖線で示した。
【０１２２】
このように、情報処理装置１０は、１本目の辺を追加する。
【０１２３】
情報処理装置１０は、上記と同様の動作を、匿名化データのレコードｔ＊１に、４本（追加する辺としては、３（ｋ（＝４）−１）本の辺が張られるまで、繰り返す。
【０１２４】
情報処理装置１０は、同様に、ｔ＊１に、２本目の追加の辺を張る。
【０１２５】
図１６及び図１７から明らかなように、辺選択部１２は、レコードｔ４への辺を、最近傍辺βとして、選択する。そして、辺追加部１３は、選択された辺ｅ（ｔ４，ｔ＊１）を、匿名化マッチンググラフに追加する。
【０１２６】
図１８は、この更新後の匿名化マッチンググラフである。
【０１２７】
図１９は、辺ｅ（ｔ４，ｔ＊１）の追加を反映したコストグラフである。図１９において、レコード５のコストを、０．１であるとした。また、レコード３のコストは、０．３である。
【０１２８】
情報処理装置１０は、同様に、ｔ＊１に、３本目（＝ｋ−１）の追加の辺を張る。つまり、情報処理装置１０は、最後の辺を追加する。
【０１２９】
図１９から明らかなとおり、辺選択部１２は、レコードｔ５を、最近傍辺βとして、選択する。そして、辺追加部１３は、選択された辺ｅ（ｔ５，ｔ＊１）を、匿名化マッチンググラフに追加する。
【０１３０】
図２０は、この更新後の匿名化マッチンググラフである。
【０１３１】
図２１は、辺ｅ（ｔ５，ｔ＊１）の追加を反映したコストグラフである。
【０１３２】
情報処理装置１０は、以上の動作を基に、匿名化データのレコードｔ＊１に３（＝ｋ−１）本の辺を追加する。つまり、レコードｔ＊１は、４（ｋ＝４）本の辺が張られた。そのため、情報処理装置１０は、匿名化データのレコードｔ＊１に対する処理を終了する。
【０１３３】
そして、情報処理装置１０は、匿名化データの他のレコードを処理する。匿名化データの他のレコードへの処理は、レコードｔ＊１と同様のため、説明を省略する。
【０１３４】
次に、図面を参照して、情報処理装置１０の動作について、説明する。
【０１３５】
図２２は、本実施形態の情報処理装置１０の動作の一例を示すフローチャートである。
【０１３６】
まず、辺抽出部１１が、匿名化データの各レコードに関するｋ−１近傍辺を抽出し、近傍辺リストを生成する（ステップＳ１０１）。
【０１３７】
図２２において、Ｎは、レコードの数である。また、ｉ及びｊは、繰り返し処理における制御変数である。
【０１３８】
ｉは、レコードに対する制御変数である。つまり、情報処理装置１０は、ｉ＝０で最初のレコードを処理し、ｉが１増えると、次にレコードの処理を実行する。情報処理装置１０は、制御変数ｉを用いて、全ての匿名化データのレコードを処理する（ステップＳ１０２〜Ｓ１０２Ｅ）。
【０１３９】
ｊは、匿名化に対する制御変数である。情報処理装置１０は、ｊの値を０からｋ−１まで増やしながら、匿名性を満足するように以下で説明する処理を繰り返す（ステップＳ１０３〜Ｓ１０３Ｅ）。
【０１４０】
辺選択部１２は、候補辺集合μ（ｔ＊）（又は、近傍辺の集合）から、匿名化データのレコードｔ＊に対する最近傍辺（β）を選択する（ステップＳ１０４）。
【０１４１】
次に、辺追加部１３は、匿名化マッチンググラフに、辺選択部１２が選択した辺（β）を追加する（ステップＳ１０５）。
【０１４２】
辺更新部１４が、追加した辺βに基づいて、近傍辺の集合を更新する（ステップＳ１０６）。
【０１４３】
次に、第１の実施の形態の効果について説明する。
【０１４４】
このように、第１の実施形態に係る情報処理装置１０は、匿名性の処理が効率化するという効果を得ることができる。
【０１４５】
その理由は、次のとおりである。
【０１４６】
辺抽出部１１が、匿名化の処理対象の匿名化データのレコードに対する所定の数の上位の数の近傍辺を抽出し、近傍辺リストを生成する。そして、辺選択部１２が、近傍辺リストを基に、匿名化のために追加する辺を選択する。そのため、情報処理装置１０は、匿名化マッピンググラスに追加する辺の候補の処理を削減できるためである。
【０１４７】
また、辺追加部１３が、選択された辺を匿名化マッピンググラフに追加後、辺更新部１４が、更新された後のコストを再計算し、コストの低い方から所定の数の近傍辺に集合を作成又は更新する。そして、これ以降、辺選択部１２は、作成又は更新された近傍辺の集合から、追加する辺を選択する。そのため、情報処理装置１０は、常に、コストを最適にしながら、辺の選択の処理を削減できるためである。
【０１４８】
［変形例］
以上の説明した情報処理装置１０は、次のように構成される。
【０１４９】
例えば、情報処理装置１０の各構成部は、ハードウェア回路で構成されても良い。
【０１５０】
また、情報処理装置１０は、各構成部が、ネットワークを介して接続した複数の装置を用いて、構成されても良い。
【０１５１】
また、情報処理装置１０は、複数の構成部を１つのハードウェアで構成しても良い。
【０１５２】
また、情報処理装置１０は、ＣＰＵ（Central Processing Unit）と、ＲＯＭ（Read Only Memory）と、ＲＡＭ（Random Access Memory）とを含むコンピュータ装置として実現してもよい。情報処理装置１０は、上記構成に加え、さらに、入出力接続回路（ＩＯＣ：Input / Output Circuit）と、ネットワークインターフェース回路（ＮＩＣ：Network Interface Circuit）とを含むコンピュータ装置として実現しても良い。
【０１５３】
図２は、本変形例に係る情報処理装置６００の構成の一例を示すブロック図である。
【０１５４】
情報処理装置６００は、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０と、内部記憶装置６４０と、ＩＯＣ６５０と、ＮＩＣ６８０とを含み、コンピュータ装置を構成している。
【０１５５】
ＣＰＵ６１０は、ＲＯＭ６２０からプログラムを読み込む。そして、ＣＰＵ６１０は、読み込んだプログラムに基づいて、ＲＡＭ６３０と、内部記憶装置６４０と、ＩＯＣ６５０と、ＮＩＣ６８０とを制御する。そして、ＣＰＵ６１０を含むコンピュータは、これらの構成を制御し、図１に示す、辺抽出部１１と、辺選択部１２と、辺追加部１３と、辺更新部１４しての各機能を実現する。
【０１５６】
ＣＰＵ６１０は、各機能を実現する際に、ＲＡＭ６３０又は内部記憶装置６４０を、プログラムの一時記憶として使用しても良い。
【０１５７】
また、ＣＰＵ６１０は、コンピュータで読み取り可能にプログラムを記憶した記憶媒体７００が含むプログラムを、図示しない記憶媒体読み取り装置を用いて読み込んでも良い。あるいは、ＣＰＵ６１０は、ＮＩＣ６８０を介して、図示しない外部の装置からプログラムを受け取り、ＲＡＭ６３０に保存して、保存したプログラムを基に動作しても良い。
【０１５８】
ＲＯＭ６２０は、ＣＰＵ６１０が実行するプログラム及び固定的なデータを記憶する。ＲＯＭ６２０は、例えば、Ｐ−ＲＯＭ（Programmable-ROM）又はフラッシュＲＯＭである。
【０１５９】
ＲＡＭ６３０は、ＣＰＵ６１０が実行するプログラム及びデータを一時的に記憶する。ＲＡＭ６３０は、例えば、Ｄ−ＲＡＭ（Dynamic-RAM）である。
【０１６０】
内部記憶装置６４０は、情報処理装置６００が長期的に保存するデータ及びプログラムを記憶する。また、内部記憶装置６４０は、ＣＰＵ６１０の一時記憶装置として動作しても良い。内部記憶装置６４０は、例えば、ハードディスク装置、光磁気ディスク装置、ＳＳＤ（Solid State Drive）又はディスクアレイ装置である。
【０１６１】
ここで、ＲＯＭ６２０と内部記憶装置６４０は、不揮発性（non-transitory）の記憶媒体である。一方、ＲＡＭ６３０は、揮発性（transitory）の記憶媒体である。そして、ＣＰＵ６１０は、ＲＯＭ６２０、内部記憶装置６４０、又は、ＲＡＭ６３０に記憶されているプログラムを基に動作可能である。つまり、ＣＰＵ６１０は、不揮発性記憶媒体又は揮発性記憶媒体を用いて動作可能である。
【０１６２】
ＩＯＣ６５０は、ＣＰＵ６１０と、入力機器６６０及び表示機器６７０とのデータを仲介する。ＩＯＣ６５０は、例えば、ＩＯインターフェースカード又はＵＳＢ（Universal Serial Bus）カードである。
【０１６３】
入力機器６６０は、情報処理装置６００の操作者からの入力指示を受け取る機器である。入力機器６６０は、例えば、キーボード、マウス又はタッチパネルである。
【０１６４】
表示機器６７０は、情報処理装置６００の操作者に情報を表示する機器である。表示機器６７０は、例えば、液晶ディスプレイである。
【０１６５】
ＮＩＣ６８０は、ネットワークを介した図示しない外部の装置とのデータのやり取りを中継する。ＮＩＣ６８０は、例えば、ＬＡＮ（Local Area Network）カードである。
【０１６６】
このように構成された情報処理装置６００は、情報処理装置１０と同様の効果を得ることができる。
【０１６７】
その理由は、情報処理装置６００のＣＰＵ６１０が、プログラムに基づいて情報処理装置１０と同様の機能を実現できるためである。
【０１６８】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成及び詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１６９】
１０    情報処理装置
１１    辺抽出部
１２    辺選択部
１３    辺追加部
１４    辺更新部
６００    情報処理装置
６１０    ＣＰＵ
６２０    ＲＯＭ
６３０    ＲＡＭ
６４０    内部記憶装置
６５０    ＩＯＣ
６６０    入力機器
６７０    表示機器
６８０    ＮＩＣ
７００    記憶媒体
【図１】
2016115020.tif 000003
【図２】
2016115020.tif 000004
【図３】
2016115020.tif 000005
【図４】
2016115020.tif 000006
【図５】
2016115020.tif 000007
【図６】
2016115020.tif 000008
【図７】
2016115020.tif 000009
【図８】
2016115020.tif 000010
【図９】
2016115020.tif 000011
【図１０】
2016115020.tif 000012
【図１１】
2016115020.tif 000013
【図１２】
2016115020.tif 000014
【図１３】
2016115020.tif 000015
【図１４】
2016115020.tif 000016
【図１５】
2016115020.tif 000017
【図１６】
2016115020.tif 000018
【図１７】
2016115020.tif 000019
【図１８】
2016115020.tif 000020
【図１９】
2016115020.tif 000021
【図２０】
2016115020.tif 000022
【図２１】
2016115020.tif 000023
【図２２】
2016115020.tif 000024