(57)【要約】【課題】個人情報を含むデータを、高速に、かつ情報損失を抑制して匿名化することを可能にした情報処理装置を提供する。【解決手段】（ｋ，１）−匿名性を充足する元データおよび匿名化データの組み合わせデータに対して、元データに含まれる複数のレコードのうち、（ｋ，ｋ）−匿名性を満たさないレコードを対象レコードとし、近傍リストを参照し、対象レコードに対応する近傍レコードの集合を抽出する近傍レコード抽出部と、（ｋ，１）−匿名性を充足する匿名化マッチンググラフにおいて、匿名化データのレコードのうち、抽出された近傍レコードと既に辺が張られているレコードと、対象レコードとの間に張られる辺を候補辺として抽出する候補辺抽出部と、（ｋ，ｋ）−匿名性の充足のために、候補辺の集合から匿名化マッチンググラフに追加する辺を１つ以上選択する辺選択部と、選択された１つ以上の辺を匿名化マッチンググラフに追加する辺追加部とを有する。【選択図】図１
2016115116.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.
【非特許文献２】T. Tassa, A. Mazza and A. Gionis,  "k-concealment: An Alternative Model of k-Type Anonymity"，Transaction on Data Privacy, 5, pp. 189-222, 2012．
【発明の概要】
【発明が解決しようとする課題】
【００１５】
非特許文献２の（ｋ，ｋ）−匿名性を満たす匿名化では、（ｋ，１）−匿名性の充足をした後に（ｋ，ｋ）−匿名性の充足を行う。これによって元データのレコードのみから辺を追加すればよく、簡単な方法で（ｋ，ｋ）−匿名性の充足が実現できる。前者のステップを（ｋ，１）−匿名性充足ステップ、後者のステップを（ｋ，ｋ）−匿名性充足ステップと呼ぶ。
（ｋ，ｋ）−匿名性充足ステップでは、Ｎ−１個の匿名化データのレコードに対する辺が、（ｋ，ｋ）−匿名性の充足のために張る辺の候補と成り得る。ただし、実際に張る辺は最大でｋ−１本であり、ｋ＜＜Ｎのとき、候補の辺の集合の多くが選択されることがない。
【００１６】
ここで、元データのレコード間で、互いのレコードを包含する匿名化データを生成したときに生じるコストを考える。このコストは、元データのレコード間の距離と考えることができる。コストの小さい匿名化データの生成が目的であるとき、元データのレコード間で距離の遠い組合せを用いることは望ましくない。また、コストの小さい匿名化データを生成するとき、距離の近いレコード群から匿名化データが作られる傾向にある。
よって、元データにおいて近傍でないレコード群、及びそれらに対する辺は、（ｋ，ｋ）−匿名性の充足のために利用されない可能性が高い。
以上のことから、非特許文献２に記載された、（ｋ，ｋ）−匿名性を充足させる匿名化は、（ｋ，ｋ）−匿名性の充足のために、匿名化マッチンググラフに張る辺の候補を匿名化データのほぼ全てのレコードから探索しており、レコード数の増加に伴って多くの計算時間を要するという課題がある。また、候補になる可能性の低い多くの辺に対しても、コストの評価を行っており、効率が悪い。
【００１７】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、個人情報を含むデータを、高速に、かつ情報損失を抑制して匿名化することを可能にした情報処理装置、情報処理方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記目的を達成するための本発明の情報処理装置は、匿名化の強度ｋ（ｋは２以上の整数）を用いてレコード間のマッチングが（ｋ，１）−匿名性を充足する、匿名化対象の元データおよび該元データから生成された匿名化データの組み合わせデータに対して、（ｋ，ｋ）−匿名性を充足させる情報処理装置であって、
前記元データに含まれる複数のレコードのうち、前記（ｋ，ｋ）−匿名性を満たさないレコードを対象レコードとし、前記元データにおける各レコードの近傍のレコードである近傍レコードを示した近傍リストを参照し、前記対象レコードに対応する前記近傍レコードの集合を抽出する近傍レコード抽出部と、
前記（ｋ，１）−匿名性を充足する前記組み合わせデータのレコード間のマッチングを表した二部グラフである匿名化マッチンググラフにおいて、前記匿名化データのレコードのうち、前記近傍レコードの集合の近傍レコードと既に辺が張られているレコードと、前記対象レコードとの間に張られる辺を候補辺として抽出する候補辺抽出部と、
前記（ｋ，ｋ）−匿名性を充足させるために、前記候補辺の集合から前記匿名化マッチンググラフに追加する辺を１つ以上選択する辺選択部と、
前記辺選択部によって選択された１つ以上の辺を前記匿名化マッチンググラフに追加する辺追加部と、
を有する構成である。
【００１９】
また、本発明の情報処理方法は、匿名化の強度ｋ（ｋは２以上の整数）を用いてレコード間のマッチングが（ｋ，１）−匿名性を充足する、匿名化対象の元データおよび該元データから生成された匿名化データの組み合わせデータに対して、（ｋ，ｋ）−匿名性を充足させる情報処理装置による情報処理方法であって、
前記元データに含まれる複数のレコードのうち、前記（ｋ，ｋ）−匿名性を満たさないレコードを対象レコードとし、前記元データにおける各レコードの近傍のレコードである近傍レコードを示した近傍リストを参照し、前記対象レコードに対応する前記近傍レコードの集合を抽出し、
前記（ｋ，１）−匿名性を充足する前記組み合わせデータのレコード間のマッチングを表した二部グラフである匿名化マッチンググラフにおいて、前記匿名化データのレコードのうち、前記近傍レコードの集合の近傍レコードと既に辺が張られているレコードと、前記対象レコードとの間に張られる辺を候補辺として抽出し、
前記（ｋ，ｋ）−匿名性を充足させるために、前記候補辺の集合から前記匿名化マッチンググラフに追加する辺を１つ以上選択し、
選択された前記１つ以上の辺を前記匿名化マッチンググラフに追加するものである。
【００２０】
さらに、本発明のプログラムは、匿名化の強度ｋ（ｋは２以上の整数）を用いてレコード間のマッチングが（ｋ，１）−匿名性を充足する、匿名化対象の元データおよび該元データから生成された匿名化データの組み合わせデータに対して、（ｋ，ｋ）−匿名性を充足させるコンピュータに、
前記元データに含まれる複数のレコードのうち、前記（ｋ，ｋ）−匿名性を満たさないレコードを対象レコードとし、前記元データにおける各レコードの近傍のレコードである近傍レコードを示した近傍リストを参照し、前記対象レコードに対応する前記近傍レコードの集合を抽出する手順と、
前記（ｋ，１）−匿名性を充足する前記組み合わせデータのレコード間のマッチングを表した二部グラフである匿名化マッチンググラフにおいて、前記匿名化データのレコードのうち、前記近傍レコードの集合の近傍レコードと既に辺が張られているレコードと、前記対象レコードとの間に張られる辺を候補辺として抽出する手順と、
前記（ｋ，ｋ）−匿名性を充足させるために、前記候補辺の集合から前記匿名化マッチンググラフに追加する辺を１つ以上選択する手順と、
選択された前記１つ以上の辺を前記匿名化マッチンググラフに追加する手順を実行させるものである。
【発明の効果】
【００２１】
本発明は、（ｋ，１）−匿名性を充足した匿名化マッチンググラフに対して、高速に、かつ情報損失を抑制した（ｋ，ｋ）−匿名性を充足させることができる。
【図面の簡単な説明】
【００２２】
【図１】本実施形態の情報処理装置の機能ブロック構成の一例を示す図である。
【図２】本実施形態の情報処理装置を実現するコンピュータのハードウェア構成の一例を示すブロック図である。
【図３】本実施形態の情報処理装置による動作手順を示すフローチャートである。
【図４】本実施形態における動作の説明において、入力される匿名化マッチンググラフの一例を示す図である。
【図５】本実施形態における動作の説明において、入力される近傍リストの一例を示す図である。
【図６】近傍レコードと、近傍レコードが辺を張る匿名化データのレコードを示した図である。
【図７】図６に示したグラフに候補辺を破線で表した図である。
【図８】対象レコードに候補辺のうちｋ−１本の辺を追加した匿名化マッチンググラフを示す図である。
【図９】本実施形態の情報処理装置の変形例の構成を示すブロック図である。
【図１０】本実施形態の情報処理装置を実現するコンピュータのハードウェア構成の変形例を示すブロック図である。
【図１１ａ】匿名化対象となる元データを表すテーブルである。
【図１１ｂ】図１１ａのテーブルをｋ＝２としてk-匿名化した場合の一例を表すテーブルである。
【図１２】図１１ａのテーブルと、図１１ａのテーブルを（ｋ，１）−匿名性を充足するように加工したテーブルとのマッチングを表す図である。
【図１３ａ】図１１ａのテーブルと、図１１ａのテーブルを（１，ｋ）−匿名性を充足するように加工したテーブルとのマッチングを表す図である。
【図１３ｂ】図１３ａに示したマッチングにおける匿名化マッチンググラフを示す図である。
【図１４】図１１ａのテーブルと、図１１ａのテーブルを（ｋ，ｋ）−匿名性を充足するように加工したテーブルとのマッチングを表す図である。
【発明を実施するための形態】
【００２３】
本発明の一実施形態について、図面を参照して詳細に説明する。
本実施形態の情報処理装置の構成を説明する。図１は、本実施形態の情報処理装置の機能ブロック構成の一例を示す図である。
図１に示すように、情報処理装置１は、近傍レコード抽出部１１と、候補辺抽出部１２と、辺選択部１３と、近追加部１４とを有する構成である。
匿名化対象のデータセット（元データ）は、オリジナルな情報内容のままで公開又は利用されることが好ましくないセンシティブ属性等を含む。このようなデータセットは、１つ以上の属性を有するレコード群からなる。また、レコード群が有する属性のうち少なくとも１つは、センシティブ属性であるものとする。以下では、匿名化対象の元データと元データから生成された匿名化データとの組み合わせのデータを、「組み合わせデータ」と称する。
図１に示す匿名化マッチンググラフ１５は、組み合わせデータが（ｋ，１）−匿名性を満たす場合の匿名化マッチンググラフに相当する。匿名化マッチンググラフ１６は、組み合わせデータが（ｋ，ｋ）−匿名性を満たす場合の匿名化マッチンググラフに相当する。
近傍リスト１７は、匿名化対象の元データにおける各レコードについて、予め決められた近傍のレコードである近傍レコードを示すリストである。近傍リストの具体例は後述する。
【００２４】
近接レコード抽出部１１は、匿名化マッチンググラフ１５、近傍リスト１７及び匿名化強度ｋ（ｋは２以上の整数）が入力されると、元データに含まれる複数のレコードのうち、（ｋ，ｋ）−匿名性を満たさないレコードを対象レコードとする。そして、近接レコード抽出部１１は、近傍リストを参照し、対象レコードに対応する近傍レコードの集合を抽出する。
候補辺抽出部１２は、匿名化マッチンググラフ１５において、近接レコード抽出部１１によって抽出された近傍レコードの集合に属する各近傍レコードに注目する。そして、候補辺抽出部１２は、注目した近傍レコードと既に辺が張られている、匿名化データのレコードを特定し、特定したレコードと対象レコードとの間に張られる辺を候補辺として抽出する。
辺選択部１３は、（ｋ，ｋ）−匿名性を充足させるために、候補辺抽出部１２によって抽出された候補辺の集合から匿名化マッチンググラフ１５に追加する辺を１つ以上選択する。近追加部１４は、辺選択部１３によって選択された１つ以上の辺を匿名化マッチンググラフ１５に追加する。
全ての対象レコードについて、（ｋ，ｋ）−匿名性を充足するように辺が追加されることで、匿名化マッチンググラフ１５が匿名化マッチンググラフ１６に更新される。上述した、図１に示す各構成の機能については、実施例を用いて、後述の動作手順で詳しく説明する。
【００２５】
上述の情報処理装置１の各構成部は、例えば、ハードウェア回路で構成されてもよい。また、情報処理装置１は、各構成部が、ネットワークを介して接続した複数の装置を用いて、構成されてもよい。また、情報処理装置１は、複数の構成部を１つのハードウェアで構成してもよい。
【００２６】
図２は図１に示した情報処理装置のハードウェア構成の一例を示すブロック図である。図２に示すように、情報処理装置１は、ＣＰＵ（Central Processing Unit）１００１と、ＲＡＭ（Random Access Memory）１００２と、ＲＯＭ（Read Only Memory）１００３と、ハードディスク等の記憶装置１００４とを含むコンピュータによって構成される。この場合、ＣＰＵ１００１が、ＲＯＭ１００３又は記憶装置１００４が記憶するコンピュータ・プログラム及び各種データをＲＡＭ１００２に読み込んで実行することで、近傍レコード抽出部１１、候補辺抽出部１２、辺選択部１３及び近追加部１４が情報処理装置１に構成される。
なお、匿名化強度ｋ、近傍リスト１７及び匿名化マッチンググラフ１５は、例えば、記憶装置１００４に格納される。また、情報処理装置１及びその各機能ブロックのハードウェア構成は、上述の構成に限定されない。
【００２７】
次に、図１に示した情報処理装置１による動作手順を、実施例を用いて説明する。図３は本実施形態の情報処理装置の動作手順を示すフローチャートである。Ｎを元データのレコード数とする。
図４は本実施形態の情報処理方法を説明するための一実施例の匿名化マッチンググラフを示す図である。図５は本実施例の近傍リストの一例を示すテーブルである。図６から図８は、図４に示した匿名化マッチンググラフに図５に示した近傍リストを適用して、辺を追加する手順を説明するための図である。図６から図８では、図４に示す元データＴ＝｛ｔ1，ｔ2，ｔ3，ｔ4，ｔ5，ｔ6｝に対して、レコードｔ3を処理対象とする場合で説明する。本実施例は、ｋ＝３の場合で（ｋ，ｋ）−匿名性の充足を説明する。
なお、図３に示すステップＬ１１１、Ｌ１１２、Ｌ１１３及びＬ１１４は、元データのうち、（ｋ，ｋ）−匿名性を満たさない各レコードに対して、（ｋ，ｋ）−匿名性を満たすまで、後述のステップＳ１０１〜Ｓ１０４の処理を繰り返すループ処理に関するものであり、以下では、その詳細な説明を省略する。
【００２８】
匿名化強度ｋの値及び図５に示す近傍リストが情報処理装置１に入力され、図４に示す匿名化マッチンググラフが匿名化マッチンググラフ１５として情報処理装置１に入力される。図３に示すように、近傍レコード抽出部１１は、近傍リストを参照して、対象レコードｔのｋ−１近傍の近傍レコードの集合Ｖを抽出する（ステップＳ１０１）。図６は、図５に示した近傍リストを参照することで、レコードｔ3の近傍レコードｔ1、ｔ2がレコードｔ3の近傍レコード群として抽出されることを示している。
候補辺抽出部１２は、近接レコード抽出部１１から近接レコード群の情報を受け取ると、匿名化マッチンググラフを参照し、ｖ1，ｖ2，・・・，ｖk-1∈Ｖに張られている匿名化データのレコードの集合Ｖ*1，Ｖ*2，・・・，Ｖ*k-1を抽出する。ここで、レコードｔとレコードｔ*との間に張られる辺を「（ｔ，ｔ*）」と表記する。続いて、候補辺抽出部１２は、Ｖ*1∪Ｖ*2∪・・・∪Ｖ*k-1の任意の要素ｖ*に対して候補辺（ｔ，ｖ*）を生成し、これらの情報から候補辺集合Ｃ＝｛（ｔ，ｖ*）｜ｖ*∈Ｖ*1∪Ｖ*2∪・・・∪Ｖ*k-1｝を生成する（ステップＳ１０２）。
図６は、近傍レコード群のうち、既に辺が張られている匿名化データのレコード群｛ｔ*1，ｔ*2，ｔ*3，ｔ*4｝が抽出されることを示している。図７は、レコードｔ３から、図６に示した、匿名化データのレコード群｛ｔ*1，ｔ*2，ｔ*4｝に辺を張った場合を破線で示している。破線で示す辺が候補辺に相当する。
【００２９】
このようにして、情報損失の増加を抑制できる可能性の高い匿名化データのレコードへの辺の抽出が実現される。また、元データのレコードには、多くてもｋ本程度の辺が張られている。そのため、対象レコードの（ｋ−１）個の近傍レコードから張られた辺のみを候補として考えればよいので、最大でｋ2又は（Ｎ−１）本の辺のみを考慮すればよい。ｋ＜＜Ｎのときは、既存の匿名化処理よりも非常に少ない候補だけが候補になる。また、Ｖ*1∪Ｖ*2∪・・・∪Ｖ*k-1に重複が多い場合、さらに少ない候補だけを考慮すればよい。
なお、ステップＳ１０１の処理について、上述の説明では、近傍レコードの集合を（ｋ−１）個の近傍レコードとしたが、｛ｋ−（対象レコードに既に張られている辺の数）｝（ただし、この計算結果が０以下になる場合はいずれの場合も０とする）としてもよい。この場合、（ｋ，１）−匿名性を充足する匿名化マッチンググラフで既に張られている辺を考慮しなくて済むので、近傍レコードの抽出処理がより早くなる。
【００３０】
辺選択部１３は、Ｃ＝｛（ｔ，ｖ*）｜ｖ*∈Ｖ*1∪Ｖ*2∪・・・∪Ｖ*k-1｝からｋ−ｄ（ｔ）本の辺を選択する。ｄ（ｔ）はレコードｔに張られた辺の数である。ｋ−ｄ（ｔ）本の辺は、辺を張ることによって生じる情報損失をコストとして計算し、コストが小さいものからｋ−ｄ（ｔ）本を選ぶ（ステップＳ１０３）。図３のステップＳ１０３では、辺選択部１３は、最近傍の辺（図３ではβで表す）を選択する場合を示している。この場合でも、対象レコードｔiについて、ループ処理Ｌ１１２〜Ｌ１１３が実行されることで、対象レコードｔiに最も近い方の辺から順にｋ−ｄ（ｔ）本の辺が選択される。
辺追加部１４は、辺選択部１３が選択した辺を匿名化マッチンググラフに張る（ステップＳ１０４）。レコードｔとレコードｔ*との間に張られる辺を「（ｔ，ｔ*）」と表記すると、図８は、（ｋ，１）−匿名性を充足する組み合わせデータの匿名化マッチンググラフに（ｔ3，ｔ*1）と（ｔ3，ｔ*4）が追加されたことを示している。
上述の処理によって、レコードｔがｔ３の場合のレコードに対する辺の追加の処理が終了する。続いて、他の対象レコードへの処理に移る。他の対象レコードについての処理も上述した説明と同様になるため、その詳細な説明を省略する。
匿名化データの全てのレコードにｋ本の辺が張られると、情報処理装置１は動作を終了する。
【００３１】
なお、本実施形態の情報処理装置が、元データから匿名化マッチンググラフ１５を生成する機能を備えていてもよい。図９は本実施形態の情報処理装置の変形例の構成を示すブロック図である。
図９に示すように、本実施形態の情報処理装置１０は、図１に示した構成の他に、グラフ生成部２１を有する。グラフ生成部２１は、元データ１９から匿名化マッチンググラフ１５を生成するマッチンググラフ生成部２２と、匿名化マッチンググラフ１５に基づいて、匿名化データを生成する匿名化データ生成部２３とを有する。匿名化対象の元データ１９は、例えば、図２に示した記憶装置１００４に格納される。
【００３２】
図２に示した、本実施形態の情報処理装置を実現するコンピュータのハードウェア構成の変形例を説明する。
情報処理装置１は、図２に示した構成の他に、入出力接続回路（ＩＯＣ：Input / Output Circuit）と、ネットワークインターフェース回路（ＮＩＣ：Network Interface Circuit）とをさらに有してもよい。
図１０は図１に示した情報処理装置を実現するコンピュータのハードウェア構成の変形例を示すブロック図である。情報処理装置６００は、ＣＰＵ６１０と、ＲＯＭ６２０と、ＲＡＭ６３０と、内部記憶装置６４０と、ＩＯＣ６５０と、ＮＩＣ６８０とを含み、コンピュータ装置を構成している。
【００３３】
ＣＰＵ６１０は、ＲＯＭ６２０からプログラムを読み込む。そして、ＣＰＵ６１０は、読み込んだプログラムに基づいて、ＲＡＭ６３０と、内部記憶装置６４０と、ＩＯＣ６５０と、ＮＩＣ６８０とを制御する。そして、ＣＰＵ６１０を含むコンピュータは、これらの構成を制御し、図１に示した、近傍レコード抽出部１１と、候補辺抽出部１２と、辺選択部１３と、辺追加部１４としての各機能を実現する。
ＣＰＵ６１０は、各機能を実現する際に、ＲＡＭ６３０又は内部記憶装置６４０を、プログラムの一時記憶として使用してもよい。
また、ＣＰＵ６１０は、コンピュータで読み取り可能にプログラムを記憶した記憶媒体７００が含むプログラムを、図示しない記憶媒体読み取り装置を用いて読み込んでもよい。あるいは、ＣＰＵ６１０は、ＮＩＣ６８０を介して、図示しない外部の装置からプログラムを受け取り、ＲＡＭ６３０に保存して、保存したプログラムを基に動作してもよい。
【００３４】
ＲＯＭ６２０は、ＣＰＵ６１０が実行するプログラム及び固定的なデータを記憶する。ＲＯＭ６２０は、例えば、Ｐ−ＲＯＭ（Programmable-ROM）又はフラッシュＲＯＭである。
ＲＡＭ６３０は、ＣＰＵ６１０が実行するプログラム及びデータを一時的に記憶する。ＲＡＭ６３０は、例えば、Ｄ−ＲＡＭ（Dynamic-RAM）である。
内部記憶装置６４０は、情報処理装置６００が長期的に保存するデータ及びプログラムを記憶する。また、内部記憶装置６４０は、ＣＰＵ６１０の一時記憶装置として動作してもよい。内部記憶装置６４０は、例えば、ハードディスク装置、光磁気ディスク装置、ＳＳＤ（Solid State Drive）又はディスクアレイ装置である。
ここで、ＲＯＭ６２０と内部記憶装置６４０は、不揮発性（non-transitory）の記憶媒体である。一方、ＲＡＭ６３０は、揮発性（transitory）の記憶媒体である。そして、ＣＰＵ６１０は、ＲＯＭ６２０、内部記憶装置６４０、又は、ＲＡＭ６３０に記憶されているプログラムを基に動作可能である。つまり、ＣＰＵ６１０は、不揮発性記憶媒体又は揮発性記憶媒体を用いて動作可能である。
【００３５】
ＩＯＣ６５０は、ＣＰＵ６１０と、入力機器６６０及び表示機器６７０とのデータを仲介する。ＩＯＣ６５０は、例えば、ＩＯインターフェースカード又はＵＳＢ（Universal Serial Bus）カードである。
入力機器６６０は、情報処理装置６００の操作者からの入力指示を受け取る機器である。入力機器６６０は、例えば、キーボード、マウス又はタッチパネルである。
表示機器６７０は、情報処理装置６００の操作者に情報を表示する機器である。表示機器６７０は、例えば、液晶ディスプレイである。
ＮＩＣ６８０は、ネットワークを介した図示しない外部の装置とのデータのやり取りを中継する。ＮＩＣ６８０は、例えば、ＬＡＮ（Local Area Network）カードである。
このように構成された情報処理装置６００は、情報処理装置１と同様の効果を得ることができる。その理由は、情報処理装置６００のＣＰＵ６１０が、プログラムに基づいて情報処理装置１と同様の機能を実現できるためである。
【００３６】
次に、本実施形態の効果について説明する。
本実施形態は、（ｋ，１）−匿名性を充足した匿名化マッチンググラフに対して（ｋ，ｋ）−匿名性を充足させる匿名化において、近傍レコードから辺が張られている匿名化データのレコードのみを辺を張る候補とすることによって、辺の候補を限定している。
元データのレコード間において、距離が近いレコードを含むように匿名化データのレコードを生成すると、その匿名化データのレコードは、情報損失が小さい可能性が高い。本実地形態のように、元データのあるレコードから辺を張るとき、そのレコードの近傍レコードが既に辺を張っている、匿名化データのレコードに対して辺を張ると、その匿名化データのレコードの情報損失の増加を抑制できる可能性が高くなる。また、近傍レコードが辺を張っている匿名化データのレコードへ張る辺のコストを小さくできる可能性が高くなる。その結果、高速に、かつ情報損失を抑制した（ｋ，ｋ）−匿名性を充足させることができる。
また、本実施形態は、（ｋ，ｋ）−匿名性を充足してからｋ−隠蔽性を充足させる情報処理装置、情報処理方法、及びコンピュータ・プログラムにおいても、それらの充足の高速化を図ることができる。
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成及び詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【００３７】
１、１０    情報処理装置
１１    近傍レコード抽出部
１２    候補辺抽出部
１３    辺選択部
１４    辺追加部
１００１    ＣＰＵ
１００２    ＲＡＭ
１００３    ＲＯＭ
１００４    記憶装置
【図１】
2016115116.tif 000003
【図２】
2016115116.tif 000004
【図３】
2016115116.tif 000005
【図４】
2016115116.tif 000006
【図５】
2016115116.tif 000007
【図６】
2016115116.tif 000008
【図７】
2016115116.tif 000009
【図８】
2016115116.tif 000010
【図９】
2016115116.tif 000011
【図１０】
2016115116.tif 000012
【図１１ａ】
2016115116.tif 000013
【図１１ｂ】
2016115116.tif 000014
【図１２】
2016115116.tif 000015
【図１３ａ】
2016115116.tif 000016
【図１３ｂ】
2016115116.tif 000017
【図１４】
2016115116.tif 000018