データ匿名化の方法と装置
【課題】データ匿名化装置とその方法を提供する。
【解決手段】データ匿名化装置１は、複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニット１０と、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニット１２と、完全グラフを少なくともｋ個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニット１４と、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニット１６と、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニット１８とを備える。
【解決手段】データ匿名化装置１は、複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニット１０と、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニット１２と、完全グラフを少なくともｋ個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニット１４と、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニット１６と、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニット１８とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ保護の技術分野に関し、特に、データ匿名化のための方法と装置に関する。
【背景技術】
【０００２】
社会の情報化が発展するにつれて、データ共有はますます広く普及してきている。しかしながら、攻撃者が、共有されるデータ・レコードのエントリから個人あるいは組織の秘密情報を取得し或いは推測する可能性があり、それは個人のプライバシーと組織の機密などの保護すべきデータに対するセキュリティ脅威をもたらす。
【０００３】
一般に、各種のデータレコード（テーブル形式のデータレコード等）の属性は、４つのカテゴリに分類することができる。
個人の姓名やＩＤや会社の登記名称などの、対象を直接識別することができる明示的識別情報。
個人の年齢、性別、学歴、出生地や会社のカテゴリおよび所在地などの、関連する外部情報と組み合わせて対応する対象を推測するのに用いることができる準識別情報（quasi-identifiers）。
収入と病歴等の、一般に秘密保持を望む機密情報（sensitive attributes）。
情報開示が一般的に対象にほとんど影響を及ぼさない、非機密情報（non-sensitive attributes）。
【０００４】
機密情報の値がデータ分析のために保存されるべきであると仮定すると、データ匿名化は、機密データを所有する個人の身元を隠すための操作を意味する。個人または組織のプライバシーを保護するために、明示的な識別情報は、例えば、”＊”と置き換えられて、一般に完全に隠されるか削除される。非機密情報は、完全に公開することができる。準識別情報は、関連する外部情報と組み合わせて対応する対象を推測するのに必要なデータレコードの最小の集合と見なすことができ、そのため、保護することが必要である。しかしながら、準識別情報が明示的な識別情報として完全に隠され或いは削除されれば、データレコードが対象に関する有益な情報を提供することができないので、最終的に取得されるデータレコード内に含まれる情報は、ほとんど完全に失われることになる。この場合、そのようなデータレコードはもはや使用価値を有しない。
【０００５】
従って、データレコード保護は、主に、データレコードの可用性を下げることなく、如何に情報の損失をできるだけ少なくし、如何に潜在的な攻撃脅威からデータレコード内の準識別情報を保護するかに焦点を置く。この点から、データ匿名化(Anonymization)技術が提案されている。２つの基本的なデータ匿名化技術が存在する。
１）一般化（Generalization）；多くの準識別情報、属性あるいは属性値をそれらの一般化されたバージョンと置き換える。例えば、都市名「北京」と「上海」を国名「中国」に一般化する。
２）抑制（Suppression）；多くの準識別情報、属性あるいは属性値を”＊”などのような文字と符号に置き換える。抑制は、一般化の特殊な例と見なすことができる。
【０００６】
一般化の処理において、情報の損失は避けられない。抑制は情報の完全消失を引き起こすだろう。情報の損失を減らすために、様々な匿名化方法が提案されており、その中で広く使用されているのは、ｋ−匿名化方法と呼ばれている。テーブルＡＴ内の各レコードについて、所定の準識別情報に関して少なくともｋ−１個のそれと同一の他のレコードが存在すれば、テーブルＡＴはｋ−匿名性である。最適化されたｋ−匿名化方法は、テーブルＴなどの所定のデータレコードについて、最小の情報の損失のために、準識別情報Ｑを考慮に入れてｋ−匿名性テーブルＡＴを計算する。
【０００７】
ｋ−匿名化方法の重要な１つは、クラスタリングに基づいたｋ−匿名化方法である。それは２つの基本手順を含んでいる。まず、データレコードは、クラスタリングによって、それぞれ少なくともｋ個のレコードを有する複数のクラスタに分割される。その後、各クラスタは、クラスタ内の全てのレコードの準識別情報が同じ値を有するように一般化される。この方法によれば、互いに関連したレコードは、単一のクラスタへ分割できる。また、得られるクラスタを別々に一般化できる。クラスタリングなしのグローバルな一般化と比較して、このクラスタリングに基づいた局所的な一般化はより多くの情報を保持し、情報の損失を縮小する。最適化されたクラスタリング処理は、さらに情報の損失を縮小できる適切な方法でデータレコードを適切にクラスタに分割できる。
したがって、クラスタリングに基づいたｋ−匿名化方法は、情報の損失を最小限にしながら最適の方法でどのようにレコードを分割するかという、クラスタリングの問題を有している。
【０００８】
上記の問題に対して、従来のクラスタリングに基づいたｋ−匿名化方法は、一般に局所的な最適化アプローチを採用する。非特許文献１は、レコード分割について局所的な最適化方法を使用する、ｋ−匿名のための多項式時間近似アルゴリズムを提供する。特許文献１は、全ての一般化バージョンを考慮して任意の度量について最適解を見出すｋ−匿名のための動的プログラミング方法を提供する。
【０００９】
これまでの方法においては、レコードのクラスタリングと一般化は、情報の損失の局所的最適化を考慮して実行される。非特許文献１に開示される方法は、頂点である各レコードについて、ボトムアップクラスタリングを実行する。具体的には、そのようなボトムアップ方法においては、まず、任意の頂点をサブグラフと見なす。
ｋ個未満の頂点を含む任意のサブグラフについて、頂点（ｕ）が、他の頂点に向かう何れの有向辺とも接続していなければ、指向性の辺（ｕ、ｖ）が生成される。ここで、ｖは頂点ｕに最も近いｋ−１個の近接する頂点の１つである（例えば、属性または属性値から計算された距離が最も近い）。
この処理において、ループフリー状態を満足し、かつどんな頂点も他の頂点に向かうただ１つの有向辺を有する（しかし、その頂点に向かう１つ以上の他の頂点が存在する）ことを保証することが必要である。任意の有向グラフに含まれる頂点が少なくともｋ個になるまで、上記の処理が繰り返される。
その後、辺の方向が削除され、有向グラフが無向グラフに変換される。max（２ｋ−１、３ｋ−５）以上の頂点を有するグラフについて（上記方法によって取得される何れのグラフも木と見なすことができる）、頂点（ｘ）が、グラフからランダムに選択され、サブツリーと頂点ｘを合併するためのルートノードと見なされる。このようにして、グラフは、それぞれｋより大きいサイズを有する２つのサブグラフに分解される。そのような分解ができない場合、頂点の数の条件をそれぞれ満足する２つの部分にグラフを分解することができるまで、同様の処理を行うことにより他の頂点（ｙ）を選択する。最終的に取得される各サブグラフに含まれる頂点がmax（２ｋ−１、３ｋ−５）未満となるまで、上記処理が繰り返される。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】US20100027780 A1, “Systems andmethods for anonymizing personally identifiable information associated withepigenetic information”
【非特許文献】
【００１１】
【非特許文献１】G. Aggarwal, A. Feder, K.Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu, ApproximationAlgorithms for k-Anonymity, Journal of Privacy Technology, 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記ボトムアップ方法によれば、ツリーの構築中に、頂点とそれらの隣接が、順番あるいはシーケンス制御メカニズムなしでランダムに選択される。max（２ｋ−１、３ｋ−５）以上の頂点（ラージコンポーネント（ｌａｒｇｅ ｃｏｍｐｏｎｅｎｔ）と称する）を有するグラフの分解において、情報の損失の最適化は考慮されない。さらに、これらの方法は、主に、全てのレコード或いは頂点を含む大局的な最適化を考慮せず、情報の損失の局所的最適化に焦点を置く。そのような局所的最適化はある程度まで情報の損失を減らすことができるけれども、大局的な状況が考慮されないので、大局的最適化を実現することができない。引き起こされる情報の損失は、厳しい要求を有する後続のデータ分析にとってなお受け入れがたい。
【００１３】
大局的最適化と情報損失のさらなる低減を実現することができるデータ匿名化方法が必要となっている。
【課題を解決するための手段】
【００１４】
本発明によるデータ匿名化装置は、複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニットと、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニットと、完全グラフを少なくともｋ（所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニットと、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニットと、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニットとを備え、２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする。
【００１５】
本発明によるデータ匿名化方法は、複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ステップと、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ステップと、完全グラフを少なくともｋ（ｋは所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットステップと、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ステップと、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ステップとを備え、２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする。
【発明の効果】
【００１６】
本発明によるデータ匿名化装置と方法によれば、レコード分割／クラスタリング処理はトップダウン方法で実行される。そして、念入りに定められたシーケンス制御メカニズムを用いることによって、グラフ内の辺は決められた順番にカットされる。ラージコンポーネントを分解する際にも、辺は決められた順番にカットされる。このようにして、局所的最適化だけでなく大局的な最適化も実現することができ、情報の損失をさらに低減することが可能となる。
【図面の簡単な説明】
【００１７】
本発明の上記および他の特徴、並びに効果は、図面を参照して説明された下記の好適な実施例からさらに明らかになるであろう。
【図１】本発明の好ましい実施の形態によるデータ匿名化装置の概略構成を示すブロック図である。
【図２】図１のデータ匿名化装置におけるラージコンポーネント分解ユニットの概略構成を示すブロック図である。
【図３】本発明の好ましい実施の形態によるデータ匿名化方法を説明するフローチャートである。
【図４】図３のデータ匿名化方法におけるラージコンポーネント分解手順を説明するフローチャートである。
【図５】本発明の好ましい実施の形態によるレコードに対する完全グラフ構築処理を示す概略図である。
【図６】本発明の好ましい実施の形態によるシーケンス制御メカニズムが導入される辺カット処理を示す概略図である。
【図７】本発明の好ましい実施の形態によるラージコンポーネント分解処理を示す概略図である。
【図８】本発明の好ましい実施の形態によるレコード分割の最終結果を概略的に示す図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。しかしながら、本発明は以下の実施の形態に限定されるものではない。本発明の基本概念の説明を明確にするため、本発明の解決方法に関連する構成要素、機能あるいはステップだけを図示する。既存の技術、機能、構成要素あるいはステップの詳細な記述は、以下の説明では省略している。
【００１９】
図１は、本発明の好ましい実施の形態によるデータ匿名化装置１のブロック図を示している。データ匿名化装置１は、データレコードの匿名バージョンを取得するために、複数のデータレコードの匿名化を行うよう構成されている。ここで、「データレコード」、「レコード」また「レコード項目」等の用語は、同じ意味を有し、互いに交換して使用可能である。
【００２０】
本発明の好ましい実施の形態によれば、データ匿名化装置１は、例えば、準識別情報を含んでいるデータレコードを主に考慮する。
ｋ−匿名化方法（ここで、ｋは所定の自然数）を取り入れ、データ匿名化装置１は、準識別情報に起因するプライバシー漏洩を回避し、同時に情報の損失を最小限にするために、例えば、複数データレコードを含むテーブルＴから、一般化によってｋ−匿名性テーブルＡＴを生成する。
背景技術において記述したように、明示的識別情報は直接隠すか削除することができ、非機密情報は保護を必要としない。準識別情報は、関連する外部情報と組み合わせて対応する対象を推測するのに必要なデータレコードの最小の集合と見なすことができる。したがって、準識別情報については保護する必要がある。
準識別情報は、多次元的であり、多数の属性を含んでいる。例えば、準識別情報は、Q={A1, A2, …Am}と表わすことができる。ここで、A1, A2, …, Amは、準識別情報の個々の属性を示している。あるいは、準識別情報は、例えば、Q={Rec ID，A1, A2, …Am} 又はQ={Rec ID，A1-value1, A2-value1, …Am-valuem}等の形式で表わすことができる。ここで、ＲｅｃＩＤは、全データレコードにおける準識別情報の索引を示し、valueは、それぞれ対応する属性の値を示している。
以下に、「データレコード」、「レコード」、「レコード項目」等の用語は、準識別情報のレコードを指すものとする。しかしながら、本発明は上記に限定されず、他のどんなデータレコードの匿名化と保護に適用することが可能である。さらに、以下の説明では、ｋ−匿名化方法を例としてあげているけれども、本発明は、クラスタリングに基づくどのようなデータ匿名化方法にも適用可能である。
【００２１】
データレコードは、リストまたはテーブルなどの様々な形式を有する。データレコードは、レコード記録ユニット２０内に格納されている。
図１に示すように、レコード記憶ユニット２０は、データ匿名化装置１によってアクセス可能なスタンド・アロンのユニットであってもよいし、あるいはデータ匿名化装置１の一部分であってもよい。
データ匿名化装置１は、複数のデータレコード中の各２つのレコード間の距離を計算するための距離計算ユニット１０と、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築するための完全グラフ構築ユニット１２と、完全グラフを少なくともｋ個の頂点を含む複数のコンポーネント（ｃｏｍｐｏｎｅｎｔ）に分割するために、辺の重み順に辺を順番にカットするための辺カットユニット１４と、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するためのラージコンポーネント分解ユニット１６と、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化するための一般化ユニット１８とを含んでいる。
ここで、２ｋ−１個を超える頂点を含むコンポーネントを「ラージコンポーネント」と称し、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントを「クラスタ」と称する。
一般化ユニット１８は、辺カットユニット１４とラージコンポーネント分解ユニット１６両方によって取得された各クラスタの頂点に対応するレコードを一般化する。本発明において、コンポーネントはそれぞれ木である。
【００２２】
距離計算ユニット１０は、レコード記憶ユニットに格納される各レコードの名称、属性あるいは属性値に基づいてレコードの間の距離を計算するように構成されている。
例えば、定められた基準に従って各レコードの名称あるいは属性を量子化し、量子化された値に基づいてレコードの間の距離を計算することが可能である（例えば、周知のユークリッド距離アルゴリズムを用いることによって）。なお、可能であれば、計算された距離は、距離記憶装置（図示せず）に格納してもよい。
【００２３】
完全グラフ構築ユニット１２は、全てのレコードを含む完全グラフを構築するように構成されている。すなわち、任意の２つのレコードの間には辺が存在する。
上述したように、本発明によれば、トップダウン方式のレコード分割／クラスタリング処理が、構築が各レコードから開始される既存技術のボトムアップ処理の代わりに採用される。
このように、完全グラフが本発明に導入される。完全グラフは、２つの任意のレコードの間の距離を含んでいる。
全てのレコードは、完全グラフを分割あるいは分解することにより、トップダウン方法で、それぞれサブグラフあるいはコンポーネント（各サブグラフはここでコンポーネントと見なすことができる）に分割される。
なお、可能であれば、構築された完全グラフは、記憶装置（図示せず）に格納してもよい。
【００２４】
辺カットユニット１４は、それぞれの重みに従って辺をソートし、かつそれらの重みの降順に辺をカットするように構成されている。
この方法においては、任意に頂点の隣接値を選択することによりコンポーネントが構築される既存方式とは対照的に、局所的最適化を確保しながら大局的最適化を達成するために、シーケンス制御メカニズム（sequential control mechanism）が本発明に導入されている。
例えば、３つのレコード「修士」、「博士」および「エンジニア」について、定められた基準に基づいて、「修士」と「博士」の間の距離は、「修士」と「エンジニア」の間の距離より短く、「博士」と「エンジニア」の間の距離が最長であると判定される。
この場合、辺カットの処理において、「博士」と「エンジニア」の間の辺がまずカットされ、その後、「修士」と「エンジニア」の間の辺がカットされ、「修士」と「博士」の間の辺が保持される。
この方法で、「修士」と「博士」を含むサブグラフあるいはコンポーネントが、「エンジニア」から分離される。
【００２５】
辺の連続的なカットにおいて、辺カットユニット１４は、以下の条件の１つが満足されれば、辺をカットするように構成されている。
１）辺がブリッジであり（すなわち、辺がカットされると、その辺を含むグラフが２つのサブグラフに分割される）、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む。
２）辺がブリッジではない（すなわち、辺がカットされても、その辺を含むグラフが２つのサブグラフに分割されない）。
【００２６】
辺カットユニット１４の動作については、具体例と図を参照して後述する。
なお、辺カットユニット１４からの結果出力は、辺カット結果記憶ユニット（図示せず）に格納してもよい。
【００２７】
辺カットユニット１４の動作後に取得されるいくつかのコンポーネントは、ｋ個以上で２ｋ−１個以下の頂点を含む可能性がある。そのようなコンポーネントの各々は分解をそれ以上必要としないクラスタと見なされる。
他方、辺カットユニット１４の動作後に取得されるいくつかのコンポーネントは、２ｋ−１個を超える頂点を含む。そのようなコンポーネントは、ラージコンポーネントと称され、分解された各部分に含まれる頂点の数がｋ個と２ｋ−１個の間となるように、分解する必要がある、
本発明の好ましい実施の形態によれば、ラージコンポーネントの分解のために以下の２つの方法を採用する。
１）既存技術における何れかの適切な方法を用いる。その詳細な説明については、本発明を必要以上に不明瞭としないために省略する。
２）既存のランダムマージ方法と異なり、辺カット処理において用いられるものと類似するシーケンス制御メカニズムを、大局的最適化と情報の損失を考慮して導入する。これについては、以下においてさらに説明する。
【００２８】
図２は、図１のデータ匿名化装置１におけるラージコンポーネント分解ユニット１６の構成を示すブロック図である。
ラージコンポーネント分解ユニット１６は、ｋ中心頂点検出ユニット１６０と、サブコンポーネント距離計算ユニット１６２と、サブコンポーネント完全グラフ構築ユニット１６４と、サブコンポーネント完全グラフ辺カットユニット１６６およびマージユニット１６８を含む。ここで、サブコンポーネントはそれぞれ木である。
【００２９】
本発明の好ましい実施の形態によれば、ｋ中心頂点（k-central-vertex）がラージコンポーネント分解に導入される。頂点が削除される時、取得される各サブコンポーネント（これらはサブグラフとも見なすことができる）が多くてもｋ−１個の頂点を含んでいれば、コンポーネント内の頂点は、ｋ中心頂点と定義される。
ここで、以下の補題（Lemma）を導入する。
補題（Lemma）
２ｋ−１個を超える頂点を有するコンポーネントについて、ｋ中心頂点は１つだけ存在する。
【００３０】
証明（Proof）
２ｋ−１個を超える頂点を有する１つのコンポーネント内に、上記のように定義される２つのｋ中心頂点ｖ１、ｖ２が存在すると仮定する。
ｖ１とｖ２の間の辺がカットされると、取得される各サブコンポーネントは多くてもｋ−１個の頂点を有する。それでは、ラージコンポーネントは、多くても２ｋ−２個のノードを有することになり、上記の仮定と矛盾する。これにより、上記補題が成立することが証明される。
【００３１】
ｋ中心頂点検出ユニット１６０は、各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントあるいはサブグラフを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするように構成されている。
【００３２】
サブコンポーネント距離計算ユニット１６２は、各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するように構成されている。本発明の好ましい実施の形態によれば、ｋ中心頂点は除外されるので、取得される各サブコンポーネントは多くてもｋ−１個の頂点を含んでいる。従って、サブコンポーネントのそれぞれを分解する必要はない。そのため、ラージコンポーネント分解処理において、各サブコンポーネントの全体をそのサブコンポーネントの中心によって表すことができる。サブコンポーネントの中心は、サブコンポーネントに含まれる頂点に対応するレコードの量子化された値或いは属性値の平均値あるいは中央値、あるいは他の適切な度量である。２つのサブコンポーネントの中心間の距離についても、適切な既存の方法（例えば、ユークリッド距離アルゴリズム）の何れかを用いることにより計算することができる。
【００３３】
本発明の好ましい実施の形態によれば、上述したように、トップダウン式の分割／クラスタリング処理をラージコンポーネント分解にも導入し、それによって、大局的最適化を保証している。ラージコンポーネント分解ユニット１６内のサブコンポーネント完全グラフ構築ユニット１６４は、サブコンポーネント全体を頂点として用いる。それにより、サブコンポーネント完全グラフ構築ユニット１６４は、各サブコンポーネントを頂点として用いることにより、具体的には、計算された各サブコンポーネントの中心を頂点として用い、全ての２つの頂点を辺で接続することにより、完全グラフを構築するように構成されている。
このような構築されたグラフにおいて、頂点は、対応するサブコンポーネントのサイズ（すなわち、サブコンポーネントに含まれる頂点の数）によってそれぞれ重み付けされ、辺は、２つの対応するサブコンポーネント中心間の距離によってそれぞれ重み付けされる。
【００３４】
連続カット方法は、ラージコンポーネント分解にも導入される。辺カットユニット１４の上記動作と同様に、サブコンポーネント完全グラフ辺カットユニット１６６は、辺の重みの順に辺を連続してカットし、サブコンポーネントを複数のクラスタに分割するように構成されている。各クラスタに含まれる全ての頂点の重みの和は、ｋ以上で２ｋ−１以下である。
【００３５】
サブコンポーネント完全グラフ辺カットユニット１６６は、辺の重みの降順に辺を連続してカットする。辺の連続カット処理において、以下の条件の１つが満足されれば、サブコンポーネント完全グラフ辺カットユニット１６６は辺をカットする。
１）辺がブリッジであり（すなわち、辺がカットされると、その辺を含むグラフが２つのサブグラフに分割される）、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない（すなわち、辺がカットされても、その辺を含むグラフが２つのサブグラフに分割されない）。
【００３６】
サブコンポーネント完全グラフ辺カットユニット１６６の動作については、具体例と図を参照して後述する。
【００３７】
サブコンポーネント完全グラフ辺カットユニット１６６の動作完了後、クラスタの１つに先に除外されたｋ中心頂点をマージすることが必要となる。マージユニット１６８は、ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージするように構成されている。ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタはさらに２つのクラスタへ分解され、その結果、各クラスタに含まる全ての頂点の重みの和は、ｋと等しくなる。
【００３８】
ラージコンポーネント分解ユニット１６によって取得されたクラスタは、辺カットユニット１４によって取得されたクラスタと共に、レコード分割／クラスタリングの結果を構成する。結果として得られた各クラスタに含まれる頂点或いはレコードの数は、ｋ以上で２ｋ−１以下である。なお、可能であれば、結果として得られたレコードは、レコード分割記憶装置（図示せず）に格納してもよい。
【００３９】
一般化ユニット１８は、結果として得られた各クラスタ毎に、頂点に対応するレコードを一般化するように構成されている。その結果、各クラスタ内のレコードは互いに分割することができなくなる。一般化ユニット１８は、周知のどのような一般化方法も用いることが可能である。一例として、複数の数値については、それらの最小公倍数として一般化することが可能である。例えば、値２、４、１０は、２０として一般化することが可能である。
他の例として、複数の都市名称は、これらの都市が属している州の名称として一般化することが可能である。例えば、都市名称「成都（Chengdu）」、「綿陽（Mianyang）」および「楽山（Leshan）」は、州名称「四川（Sichuan）」として一般化することが可能である。一般に、異なる属性は、それらが属するカテゴリの最下位のレベルとして一般化することができる。これにより、それらの属性は互いに分割することができなくなり、同時に情報の損失を最小限に保つ。なお、一般化ユニット１８からの結果出力は、匿名テーブルあるいはリスト等のような様々な形式で匿名のレコード記憶ユニット（図示せず）に格納される。
【００４０】
以上、本発明の好ましい実施の形態によるデータ匿名化装置１について説明した。
図３は、本発明の好ましい実施の形態によるデータ匿名化方法３００を説明するフローチャートである。このデータ匿名化方法３００はデータ匿名化装置１によって実行される。
ステップ３０２で、複数のデータレコードを含むテーブル内の２つのレコードごとの間の距離を計算する。
ステップ３０４で、頂点として各レコードを用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する。
ステップ３０６で、完全グラフを少なくともｋ個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする。
ステップ３０８で、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むラージコンポーネントを複数のクラスタに分解する。
ステップ３１０で、得られた各クラスタ内のレコードを互いに分割することができないように、各クラスタの頂点に対応するレコードを一般化する。
【００４１】
図４は、図３のデータ匿名化方法３００におけるラージコンポーネント分解ステップ３０８を示すフローチャートである。
ステップ４０２で、２ｋ−１個を超える頂点を含む各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットする。
ステップ４０４で、各サブコンポーネントの中心と、２つのサブコンポーネント中心間の距離を計算する。
ステップ４０６で、計算された各サブコンポーネントの中心を頂点として用い、対応するサブコンポーネントのサイズによって頂点に重みを付け、全ての２つの頂点を辺で接続し、２つの対応するサブコンポーネント中心間の距離によって辺に重みを付けることにより、各サブコンポーネントを頂点する完全グラフを構築する。
ステップ４０８で、辺の重みの順に辺を連続してカットして、サブコンポーネントを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和をｋ以上２ｋ−１以下とする。
ステップ４１０で、ｋ中心頂点に距離が最も近いクラスタにｋ中心頂点をマージし、マージされたクラスタに含まれる全ての頂点の重みの和が２ｋに等しければ、各クラスタに含まる全ての頂点の重みの和がｋと等しくなるように、クラスタをさらに２つのクラスタに分解する。
【００４２】
本発明の実施の形態をさらに明確に示すために、実施の形態による具体例について、図５〜図８を参照して以下に説明する。これらの具体例は、本発明の好ましい実施の形態を例示するためだけのものであり、本発明を制限するものではない。
【００４３】
例えば、１０個のデータレコードT=[Q0, Q1, …, Q9], Qi={A1, A2, …, Am},i={0, 2, .., 9}を含むテーブルがあるものとする。ここで、ｍは自然数である。ｋ（＝２）−匿名テーブルを形成するために、これらの１０のデータレコードを匿名化する必要がある。
【００４４】
まず、距離計算ユニット１０が、ユークリッド距離アルゴリズムを用いることによって、全ての２つのＱ０、Ｑ１、…、Ｑ９の間の距離を計算する。その後、完全グラフ構築ユニット１２が完全グラフを構築する。
【００４５】
図５は、本発明の好ましい実施の形態による完全グラフ構築を示す概略図である。図５に示すように、図の左側は、レコードの複数の頂点を示している。
図５の右側に示すような完全グラフを形成するために、これらの頂点を２つずつ辺で接続する。説明の便宜上、２つの頂点間の各辺の長さがその辺の重み（すなわち、２つの頂点に対応する２つのレコード間の距離）を表わすものと仮定する。
【００４６】
次に、辺カットユニット１４が、前述の条件に従って辺の重みの降順に辺をカットする。図６は、本発明の好ましい実施の形態によるシーケンス制御メカニズムが導入される辺カット処理を示す概略図である。図６から分かるように、Ｑ３とＱ８の間の辺edge３８が最も長く、最大の重みを有する。Ｑ０とＱ４の間の辺edge０４が２番めに長く、・・・、Ｑ８とＱ９の間の辺edge８９が最も短い。
【００４７】
まず、辺カットユニット１４は、辺edge３８が上述した２つの条件を満足するかどうかを判定する。この具体例において、辺edge３８はブリッジではないので、カットされる。次に、辺カットユニット１４は、辺edge０４が２つの条件を満足するかどうかを判定する。辺edge０４はブリッジではないので、カットされる。
Ｑ０とＱ１の間の辺edge０１が２つの状態を満足するかどうかを判定するまで、辺カットユニット１４はそのような動作を継続する。
辺edge０１がカットされれば、グラフが２つのコンポーネントあるいはサブグラフに完全に分割されるので、辺edge０１はブリッジである。従って、結果として得られる２つのコンポーネントがそれぞれ少なくともｋ個の頂点を有するかどうかを判定することが必要となる。図示のように、辺edge０１のカットから得られた２つのコンポーネントは、それぞれ６個の頂点と４個の頂点を含んでいる。よって、辺カットユニット１４は辺edge０１をカットする。
Ｑ０とＱ９の間の辺edge０９が２つの条件を満足するかどうかを判定する時、辺カットユニット１４は、辺edge０９がカットされれば、完全グラフのコンポーネントがさらに２つの部分に分けられると判定する。
よって、得られる２つの部分が、それぞれ少なくともｋ個の頂点を有するかどうかを判定することが再び必要となる。図示のように、辺edge０９のカットから得られた２つの部分は、１個および５個の頂点をそれぞれ含んでいる。従って、条件を満足しない。よって、辺カットユニット１４は辺edge０９をカットしない。このようにして、図６の右下部分に示すように、部分ＣＱ１、ＣＱ２、ＣＱ３およびＣＱ４が最終的に取得される。
【００４８】
ここで、部分ＣＱ２、ＣＱ３およびＣＱ４は、それぞれ２個の頂点を含んでおり、したがってそれ以上分解を必要としない。すなわち、各部分ＣＱ２、ＣＱ３、ＣＱ４はクラスタである。しかしながら、部分ＣＱ１は、４つの頂点Ｑ０、Ｑ７、Ｑ８およびＱ９を含んでおり、その数は２ｋ（＝２）−１より大きい、したがって分解する必要がある。それゆえ、ラージコンポーネント分解ユニット１６は、部分ＣＱ１についてラージコンポーネント分解処理を実行する。
図７は、本発明の好ましい実施の形態によるラージコンポーネント分解処理を示す概略図である。
まず、ｋ中心頂点検出ユニット１６０が、ｋ中心頂点を検出する。図示のように、ラージコンポーネントＣＱ１のｋ中心頂点は、頂点Ｑ９である。そこで、頂点Ｑ９に接続される全ての辺をカットし、個々の分離したサブコンポーネントを取得する。この具体例においては、図７の２番目の部分図に示すように、各サブコンポーネントはただ１個の頂点を含んでいる。しかしながら、これは便宜上例として示しているだけであり、他の状況においては、各サブコンポーネントが１つ以上の頂点を含む場合もある。
【００４９】
各サブコンポーネントが１つのみ頂点を含んでいるので、計算ユニット１６２は、サブコンポーネント中心として頂点の代表値を直接用いて、サブコンポーネント中心の間の距離を計算する。サブコンポーネント完全グラフ構築ユニット１６４は、図７の３番目の部分図に示すように、ｋ中心頂点以外の全てのサブコンポーネント中心を接続し、全てのサブコンポーネントを含む完全グラフを取得する。サブコンポーネント完全グラフ辺カットユニット１６６は、図７の４番目の部分図に示すように、上述した２つの条件に従って、辺の重み（すなわち、図において示される辺の長さ）に基づいてＱ０とＱ７の間の辺をカットし、他の辺をカットしない。マージユニット１６８は、図７の５番目の部分図に示すように、頂点Ｑ９を左のコンポーネントにマージし、４つの頂点を含むクラスタを取得する。これにより、マージユニット１６８は、図７の６番目の部分図に示すように、Ｑ７とＱ８の間の辺をカットし、それぞれ２つの頂点を含む２つのクラスタを取得する。
【００５０】
図８は、本発明の好ましい実施の形態によるレコード分割の最終結果を概略的に示す。
本発明の好ましい実施の形態によるｋ（＝２）−匿名化方法により、レコードＱ０−Ｑ９はそれぞれ２つのレコードを含む５個のクラスタに分割される。
その後、一般化ユニット１８は、各クラスタについて一般化を実行し、ｋ−匿名性テーブルAT=[AQ0, AQ1, …, AQ4]を取得する。ここで、ＡＱｉは、各クラスタにおけるレコードの一般化された値を表わす。
【００５１】
以上、本発明の好ましい実施の形態によるデータ匿名化装置と方法について説明した。上記説明において、本発明の好ましい実施の形態を、具体例だけで図示しているが、そのことは、本発明が上記の手順とユニット構成に限定されることを意味するものではない。必要に応じて、これらの手段と要素を調整し、取捨選択し、組み合わせることも可能である。さらに、これらの手順と要素のいくつかは、本発明の発明概念を実現するうえで必要不可欠ではない。このように、本発明に必須の技術的特徴は、上記の特定の具体例ではなく、本発明の発明概念を実現するための最小の必要条件にのみ限定される。
【００５２】
以上、本発明についてその好適な実施例を参照して説明したが、当該技術に精通した当業者には、本発明の精神と範囲から逸脱することなく他の様々な修正、変更、追加を行うことが可能なことは明らかであろう。したがって、本発明の範囲は上記の具体的な実施例に限定されず、付記した請求項によってのみ限定される。
【００５３】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００５４】
（付記１）
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニットと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニットと、
完全グラフを少なくともｋ（所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニットと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニットと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニットとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化装置。
【００５５】
（付記２）
前記辺カットユニットは、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする付記１に記載のデータ匿名化装置。
【００５６】
（付記３）
前記辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする付記１に記載のデータ匿名化装置。
【００５７】
（付記４）
前記ラージコンポーネント分解ユニットが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ユニットと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ユニットと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ユニットと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットユニットと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージユニットとを
備えることを特徴とする付記１に記載のデータ匿名化装置。
【００５８】
（付記５）
前記サブコンポーネント完全グラフ辺カットユニットは、辺の重みに従って辺をソートし、それらの重みの降順に辺をカットすることを特徴とする付記４に記載のデータ匿名化装置。
【００５９】
（付記６）
前記サブコンポーネント完全グラフ辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つのサブグラフに分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つのサブグラフに分割されないなら、辺はブリッジでない
ことを特徴とする
付記４に記載のデータ匿名化装置。
【００６０】
（付記７）
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ステップと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ステップと、
完全グラフを少なくともｋ（ｋは所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットステップと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ステップと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ステップとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化方法。
【００６１】
（付記８）
前記辺カットステップにおいて、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする付記７に記載のデータ匿名化方法。
【００６２】
（付記９）
前記辺カットステップにおいて、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする付記７に記載のデータ匿名化方法。
【００６３】
（付記１０）
前記ラージコンポーネント分解ステップが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ステップと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ステップと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ステップと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットステップと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージステップとを
含むことを特徴とする付記７に記載のデータ匿名化方法。
【００６４】
（付記１１）
前記サブコンポーネント完全グラフ辺カットステップにおいて、辺の重みに従って辺をソートし、それらの重みの降順に辺をカットすることを特徴とする付記１０に記載のデータ匿名化方法。
【００６５】
（付記１２）
前記サブコンポーネント完全グラフ辺カットステップにおいて、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つのサブグラフに分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つのサブグラフに分割されないなら、辺はブリッジでない
ことを特徴とする
付記１０に記載のデータ匿名化方法。
【符号の説明】
【００６６】
１：データ匿名化装置
１０：距離計算ユニット
１２：完全グラフ構築ユニット
１４：辺カットユニット
１６：ラージコンポーネント分解ユニット
１８：一般化ユニット
２０：レコード記録ユニット
１６：ラージコンポーネント分解ユニット
１６０：ｋ中心頂点検出ユニット
１６２：サブコンポーネント距離計算ユニット
１６４：サブコンポーネント完全グラフ構築ユニット
１６６：サブコンポーネント完全グラフ辺カットユニット
１６８：マージユニット
【技術分野】
【０００１】
本発明は、データ保護の技術分野に関し、特に、データ匿名化のための方法と装置に関する。
【背景技術】
【０００２】
社会の情報化が発展するにつれて、データ共有はますます広く普及してきている。しかしながら、攻撃者が、共有されるデータ・レコードのエントリから個人あるいは組織の秘密情報を取得し或いは推測する可能性があり、それは個人のプライバシーと組織の機密などの保護すべきデータに対するセキュリティ脅威をもたらす。
【０００３】
一般に、各種のデータレコード（テーブル形式のデータレコード等）の属性は、４つのカテゴリに分類することができる。
個人の姓名やＩＤや会社の登記名称などの、対象を直接識別することができる明示的識別情報。
個人の年齢、性別、学歴、出生地や会社のカテゴリおよび所在地などの、関連する外部情報と組み合わせて対応する対象を推測するのに用いることができる準識別情報（quasi-identifiers）。
収入と病歴等の、一般に秘密保持を望む機密情報（sensitive attributes）。
情報開示が一般的に対象にほとんど影響を及ぼさない、非機密情報（non-sensitive attributes）。
【０００４】
機密情報の値がデータ分析のために保存されるべきであると仮定すると、データ匿名化は、機密データを所有する個人の身元を隠すための操作を意味する。個人または組織のプライバシーを保護するために、明示的な識別情報は、例えば、”＊”と置き換えられて、一般に完全に隠されるか削除される。非機密情報は、完全に公開することができる。準識別情報は、関連する外部情報と組み合わせて対応する対象を推測するのに必要なデータレコードの最小の集合と見なすことができ、そのため、保護することが必要である。しかしながら、準識別情報が明示的な識別情報として完全に隠され或いは削除されれば、データレコードが対象に関する有益な情報を提供することができないので、最終的に取得されるデータレコード内に含まれる情報は、ほとんど完全に失われることになる。この場合、そのようなデータレコードはもはや使用価値を有しない。
【０００５】
従って、データレコード保護は、主に、データレコードの可用性を下げることなく、如何に情報の損失をできるだけ少なくし、如何に潜在的な攻撃脅威からデータレコード内の準識別情報を保護するかに焦点を置く。この点から、データ匿名化(Anonymization)技術が提案されている。２つの基本的なデータ匿名化技術が存在する。
１）一般化（Generalization）；多くの準識別情報、属性あるいは属性値をそれらの一般化されたバージョンと置き換える。例えば、都市名「北京」と「上海」を国名「中国」に一般化する。
２）抑制（Suppression）；多くの準識別情報、属性あるいは属性値を”＊”などのような文字と符号に置き換える。抑制は、一般化の特殊な例と見なすことができる。
【０００６】
一般化の処理において、情報の損失は避けられない。抑制は情報の完全消失を引き起こすだろう。情報の損失を減らすために、様々な匿名化方法が提案されており、その中で広く使用されているのは、ｋ−匿名化方法と呼ばれている。テーブルＡＴ内の各レコードについて、所定の準識別情報に関して少なくともｋ−１個のそれと同一の他のレコードが存在すれば、テーブルＡＴはｋ−匿名性である。最適化されたｋ−匿名化方法は、テーブルＴなどの所定のデータレコードについて、最小の情報の損失のために、準識別情報Ｑを考慮に入れてｋ−匿名性テーブルＡＴを計算する。
【０００７】
ｋ−匿名化方法の重要な１つは、クラスタリングに基づいたｋ−匿名化方法である。それは２つの基本手順を含んでいる。まず、データレコードは、クラスタリングによって、それぞれ少なくともｋ個のレコードを有する複数のクラスタに分割される。その後、各クラスタは、クラスタ内の全てのレコードの準識別情報が同じ値を有するように一般化される。この方法によれば、互いに関連したレコードは、単一のクラスタへ分割できる。また、得られるクラスタを別々に一般化できる。クラスタリングなしのグローバルな一般化と比較して、このクラスタリングに基づいた局所的な一般化はより多くの情報を保持し、情報の損失を縮小する。最適化されたクラスタリング処理は、さらに情報の損失を縮小できる適切な方法でデータレコードを適切にクラスタに分割できる。
したがって、クラスタリングに基づいたｋ−匿名化方法は、情報の損失を最小限にしながら最適の方法でどのようにレコードを分割するかという、クラスタリングの問題を有している。
【０００８】
上記の問題に対して、従来のクラスタリングに基づいたｋ−匿名化方法は、一般に局所的な最適化アプローチを採用する。非特許文献１は、レコード分割について局所的な最適化方法を使用する、ｋ−匿名のための多項式時間近似アルゴリズムを提供する。特許文献１は、全ての一般化バージョンを考慮して任意の度量について最適解を見出すｋ−匿名のための動的プログラミング方法を提供する。
【０００９】
これまでの方法においては、レコードのクラスタリングと一般化は、情報の損失の局所的最適化を考慮して実行される。非特許文献１に開示される方法は、頂点である各レコードについて、ボトムアップクラスタリングを実行する。具体的には、そのようなボトムアップ方法においては、まず、任意の頂点をサブグラフと見なす。
ｋ個未満の頂点を含む任意のサブグラフについて、頂点（ｕ）が、他の頂点に向かう何れの有向辺とも接続していなければ、指向性の辺（ｕ、ｖ）が生成される。ここで、ｖは頂点ｕに最も近いｋ−１個の近接する頂点の１つである（例えば、属性または属性値から計算された距離が最も近い）。
この処理において、ループフリー状態を満足し、かつどんな頂点も他の頂点に向かうただ１つの有向辺を有する（しかし、その頂点に向かう１つ以上の他の頂点が存在する）ことを保証することが必要である。任意の有向グラフに含まれる頂点が少なくともｋ個になるまで、上記の処理が繰り返される。
その後、辺の方向が削除され、有向グラフが無向グラフに変換される。max（２ｋ−１、３ｋ−５）以上の頂点を有するグラフについて（上記方法によって取得される何れのグラフも木と見なすことができる）、頂点（ｘ）が、グラフからランダムに選択され、サブツリーと頂点ｘを合併するためのルートノードと見なされる。このようにして、グラフは、それぞれｋより大きいサイズを有する２つのサブグラフに分解される。そのような分解ができない場合、頂点の数の条件をそれぞれ満足する２つの部分にグラフを分解することができるまで、同様の処理を行うことにより他の頂点（ｙ）を選択する。最終的に取得される各サブグラフに含まれる頂点がmax（２ｋ−１、３ｋ−５）未満となるまで、上記処理が繰り返される。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】US20100027780 A1, “Systems andmethods for anonymizing personally identifiable information associated withepigenetic information”
【非特許文献】
【００１１】
【非特許文献１】G. Aggarwal, A. Feder, K.Kenthapadi, R. Motwani, R. Panigrahy, D. Thomas, and A. Zhu, ApproximationAlgorithms for k-Anonymity, Journal of Privacy Technology, 2005.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記ボトムアップ方法によれば、ツリーの構築中に、頂点とそれらの隣接が、順番あるいはシーケンス制御メカニズムなしでランダムに選択される。max（２ｋ−１、３ｋ−５）以上の頂点（ラージコンポーネント（ｌａｒｇｅ ｃｏｍｐｏｎｅｎｔ）と称する）を有するグラフの分解において、情報の損失の最適化は考慮されない。さらに、これらの方法は、主に、全てのレコード或いは頂点を含む大局的な最適化を考慮せず、情報の損失の局所的最適化に焦点を置く。そのような局所的最適化はある程度まで情報の損失を減らすことができるけれども、大局的な状況が考慮されないので、大局的最適化を実現することができない。引き起こされる情報の損失は、厳しい要求を有する後続のデータ分析にとってなお受け入れがたい。
【００１３】
大局的最適化と情報損失のさらなる低減を実現することができるデータ匿名化方法が必要となっている。
【課題を解決するための手段】
【００１４】
本発明によるデータ匿名化装置は、複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニットと、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニットと、完全グラフを少なくともｋ（所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニットと、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニットと、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニットとを備え、２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする。
【００１５】
本発明によるデータ匿名化方法は、複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ステップと、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ステップと、完全グラフを少なくともｋ（ｋは所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットステップと、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ステップと、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ステップとを備え、２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする。
【発明の効果】
【００１６】
本発明によるデータ匿名化装置と方法によれば、レコード分割／クラスタリング処理はトップダウン方法で実行される。そして、念入りに定められたシーケンス制御メカニズムを用いることによって、グラフ内の辺は決められた順番にカットされる。ラージコンポーネントを分解する際にも、辺は決められた順番にカットされる。このようにして、局所的最適化だけでなく大局的な最適化も実現することができ、情報の損失をさらに低減することが可能となる。
【図面の簡単な説明】
【００１７】
本発明の上記および他の特徴、並びに効果は、図面を参照して説明された下記の好適な実施例からさらに明らかになるであろう。
【図１】本発明の好ましい実施の形態によるデータ匿名化装置の概略構成を示すブロック図である。
【図２】図１のデータ匿名化装置におけるラージコンポーネント分解ユニットの概略構成を示すブロック図である。
【図３】本発明の好ましい実施の形態によるデータ匿名化方法を説明するフローチャートである。
【図４】図３のデータ匿名化方法におけるラージコンポーネント分解手順を説明するフローチャートである。
【図５】本発明の好ましい実施の形態によるレコードに対する完全グラフ構築処理を示す概略図である。
【図６】本発明の好ましい実施の形態によるシーケンス制御メカニズムが導入される辺カット処理を示す概略図である。
【図７】本発明の好ましい実施の形態によるラージコンポーネント分解処理を示す概略図である。
【図８】本発明の好ましい実施の形態によるレコード分割の最終結果を概略的に示す図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。しかしながら、本発明は以下の実施の形態に限定されるものではない。本発明の基本概念の説明を明確にするため、本発明の解決方法に関連する構成要素、機能あるいはステップだけを図示する。既存の技術、機能、構成要素あるいはステップの詳細な記述は、以下の説明では省略している。
【００１９】
図１は、本発明の好ましい実施の形態によるデータ匿名化装置１のブロック図を示している。データ匿名化装置１は、データレコードの匿名バージョンを取得するために、複数のデータレコードの匿名化を行うよう構成されている。ここで、「データレコード」、「レコード」また「レコード項目」等の用語は、同じ意味を有し、互いに交換して使用可能である。
【００２０】
本発明の好ましい実施の形態によれば、データ匿名化装置１は、例えば、準識別情報を含んでいるデータレコードを主に考慮する。
ｋ−匿名化方法（ここで、ｋは所定の自然数）を取り入れ、データ匿名化装置１は、準識別情報に起因するプライバシー漏洩を回避し、同時に情報の損失を最小限にするために、例えば、複数データレコードを含むテーブルＴから、一般化によってｋ−匿名性テーブルＡＴを生成する。
背景技術において記述したように、明示的識別情報は直接隠すか削除することができ、非機密情報は保護を必要としない。準識別情報は、関連する外部情報と組み合わせて対応する対象を推測するのに必要なデータレコードの最小の集合と見なすことができる。したがって、準識別情報については保護する必要がある。
準識別情報は、多次元的であり、多数の属性を含んでいる。例えば、準識別情報は、Q={A1, A2, …Am}と表わすことができる。ここで、A1, A2, …, Amは、準識別情報の個々の属性を示している。あるいは、準識別情報は、例えば、Q={Rec ID，A1, A2, …Am} 又はQ={Rec ID，A1-value1, A2-value1, …Am-valuem}等の形式で表わすことができる。ここで、ＲｅｃＩＤは、全データレコードにおける準識別情報の索引を示し、valueは、それぞれ対応する属性の値を示している。
以下に、「データレコード」、「レコード」、「レコード項目」等の用語は、準識別情報のレコードを指すものとする。しかしながら、本発明は上記に限定されず、他のどんなデータレコードの匿名化と保護に適用することが可能である。さらに、以下の説明では、ｋ−匿名化方法を例としてあげているけれども、本発明は、クラスタリングに基づくどのようなデータ匿名化方法にも適用可能である。
【００２１】
データレコードは、リストまたはテーブルなどの様々な形式を有する。データレコードは、レコード記録ユニット２０内に格納されている。
図１に示すように、レコード記憶ユニット２０は、データ匿名化装置１によってアクセス可能なスタンド・アロンのユニットであってもよいし、あるいはデータ匿名化装置１の一部分であってもよい。
データ匿名化装置１は、複数のデータレコード中の各２つのレコード間の距離を計算するための距離計算ユニット１０と、各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築するための完全グラフ構築ユニット１２と、完全グラフを少なくともｋ個の頂点を含む複数のコンポーネント（ｃｏｍｐｏｎｅｎｔ）に分割するために、辺の重み順に辺を順番にカットするための辺カットユニット１４と、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するためのラージコンポーネント分解ユニット１６と、各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化するための一般化ユニット１８とを含んでいる。
ここで、２ｋ−１個を超える頂点を含むコンポーネントを「ラージコンポーネント」と称し、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントを「クラスタ」と称する。
一般化ユニット１８は、辺カットユニット１４とラージコンポーネント分解ユニット１６両方によって取得された各クラスタの頂点に対応するレコードを一般化する。本発明において、コンポーネントはそれぞれ木である。
【００２２】
距離計算ユニット１０は、レコード記憶ユニットに格納される各レコードの名称、属性あるいは属性値に基づいてレコードの間の距離を計算するように構成されている。
例えば、定められた基準に従って各レコードの名称あるいは属性を量子化し、量子化された値に基づいてレコードの間の距離を計算することが可能である（例えば、周知のユークリッド距離アルゴリズムを用いることによって）。なお、可能であれば、計算された距離は、距離記憶装置（図示せず）に格納してもよい。
【００２３】
完全グラフ構築ユニット１２は、全てのレコードを含む完全グラフを構築するように構成されている。すなわち、任意の２つのレコードの間には辺が存在する。
上述したように、本発明によれば、トップダウン方式のレコード分割／クラスタリング処理が、構築が各レコードから開始される既存技術のボトムアップ処理の代わりに採用される。
このように、完全グラフが本発明に導入される。完全グラフは、２つの任意のレコードの間の距離を含んでいる。
全てのレコードは、完全グラフを分割あるいは分解することにより、トップダウン方法で、それぞれサブグラフあるいはコンポーネント（各サブグラフはここでコンポーネントと見なすことができる）に分割される。
なお、可能であれば、構築された完全グラフは、記憶装置（図示せず）に格納してもよい。
【００２４】
辺カットユニット１４は、それぞれの重みに従って辺をソートし、かつそれらの重みの降順に辺をカットするように構成されている。
この方法においては、任意に頂点の隣接値を選択することによりコンポーネントが構築される既存方式とは対照的に、局所的最適化を確保しながら大局的最適化を達成するために、シーケンス制御メカニズム（sequential control mechanism）が本発明に導入されている。
例えば、３つのレコード「修士」、「博士」および「エンジニア」について、定められた基準に基づいて、「修士」と「博士」の間の距離は、「修士」と「エンジニア」の間の距離より短く、「博士」と「エンジニア」の間の距離が最長であると判定される。
この場合、辺カットの処理において、「博士」と「エンジニア」の間の辺がまずカットされ、その後、「修士」と「エンジニア」の間の辺がカットされ、「修士」と「博士」の間の辺が保持される。
この方法で、「修士」と「博士」を含むサブグラフあるいはコンポーネントが、「エンジニア」から分離される。
【００２５】
辺の連続的なカットにおいて、辺カットユニット１４は、以下の条件の１つが満足されれば、辺をカットするように構成されている。
１）辺がブリッジであり（すなわち、辺がカットされると、その辺を含むグラフが２つのサブグラフに分割される）、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む。
２）辺がブリッジではない（すなわち、辺がカットされても、その辺を含むグラフが２つのサブグラフに分割されない）。
【００２６】
辺カットユニット１４の動作については、具体例と図を参照して後述する。
なお、辺カットユニット１４からの結果出力は、辺カット結果記憶ユニット（図示せず）に格納してもよい。
【００２７】
辺カットユニット１４の動作後に取得されるいくつかのコンポーネントは、ｋ個以上で２ｋ−１個以下の頂点を含む可能性がある。そのようなコンポーネントの各々は分解をそれ以上必要としないクラスタと見なされる。
他方、辺カットユニット１４の動作後に取得されるいくつかのコンポーネントは、２ｋ−１個を超える頂点を含む。そのようなコンポーネントは、ラージコンポーネントと称され、分解された各部分に含まれる頂点の数がｋ個と２ｋ−１個の間となるように、分解する必要がある、
本発明の好ましい実施の形態によれば、ラージコンポーネントの分解のために以下の２つの方法を採用する。
１）既存技術における何れかの適切な方法を用いる。その詳細な説明については、本発明を必要以上に不明瞭としないために省略する。
２）既存のランダムマージ方法と異なり、辺カット処理において用いられるものと類似するシーケンス制御メカニズムを、大局的最適化と情報の損失を考慮して導入する。これについては、以下においてさらに説明する。
【００２８】
図２は、図１のデータ匿名化装置１におけるラージコンポーネント分解ユニット１６の構成を示すブロック図である。
ラージコンポーネント分解ユニット１６は、ｋ中心頂点検出ユニット１６０と、サブコンポーネント距離計算ユニット１６２と、サブコンポーネント完全グラフ構築ユニット１６４と、サブコンポーネント完全グラフ辺カットユニット１６６およびマージユニット１６８を含む。ここで、サブコンポーネントはそれぞれ木である。
【００２９】
本発明の好ましい実施の形態によれば、ｋ中心頂点（k-central-vertex）がラージコンポーネント分解に導入される。頂点が削除される時、取得される各サブコンポーネント（これらはサブグラフとも見なすことができる）が多くてもｋ−１個の頂点を含んでいれば、コンポーネント内の頂点は、ｋ中心頂点と定義される。
ここで、以下の補題（Lemma）を導入する。
補題（Lemma）
２ｋ−１個を超える頂点を有するコンポーネントについて、ｋ中心頂点は１つだけ存在する。
【００３０】
証明（Proof）
２ｋ−１個を超える頂点を有する１つのコンポーネント内に、上記のように定義される２つのｋ中心頂点ｖ１、ｖ２が存在すると仮定する。
ｖ１とｖ２の間の辺がカットされると、取得される各サブコンポーネントは多くてもｋ−１個の頂点を有する。それでは、ラージコンポーネントは、多くても２ｋ−２個のノードを有することになり、上記の仮定と矛盾する。これにより、上記補題が成立することが証明される。
【００３１】
ｋ中心頂点検出ユニット１６０は、各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントあるいはサブグラフを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするように構成されている。
【００３２】
サブコンポーネント距離計算ユニット１６２は、各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するように構成されている。本発明の好ましい実施の形態によれば、ｋ中心頂点は除外されるので、取得される各サブコンポーネントは多くてもｋ−１個の頂点を含んでいる。従って、サブコンポーネントのそれぞれを分解する必要はない。そのため、ラージコンポーネント分解処理において、各サブコンポーネントの全体をそのサブコンポーネントの中心によって表すことができる。サブコンポーネントの中心は、サブコンポーネントに含まれる頂点に対応するレコードの量子化された値或いは属性値の平均値あるいは中央値、あるいは他の適切な度量である。２つのサブコンポーネントの中心間の距離についても、適切な既存の方法（例えば、ユークリッド距離アルゴリズム）の何れかを用いることにより計算することができる。
【００３３】
本発明の好ましい実施の形態によれば、上述したように、トップダウン式の分割／クラスタリング処理をラージコンポーネント分解にも導入し、それによって、大局的最適化を保証している。ラージコンポーネント分解ユニット１６内のサブコンポーネント完全グラフ構築ユニット１６４は、サブコンポーネント全体を頂点として用いる。それにより、サブコンポーネント完全グラフ構築ユニット１６４は、各サブコンポーネントを頂点として用いることにより、具体的には、計算された各サブコンポーネントの中心を頂点として用い、全ての２つの頂点を辺で接続することにより、完全グラフを構築するように構成されている。
このような構築されたグラフにおいて、頂点は、対応するサブコンポーネントのサイズ（すなわち、サブコンポーネントに含まれる頂点の数）によってそれぞれ重み付けされ、辺は、２つの対応するサブコンポーネント中心間の距離によってそれぞれ重み付けされる。
【００３４】
連続カット方法は、ラージコンポーネント分解にも導入される。辺カットユニット１４の上記動作と同様に、サブコンポーネント完全グラフ辺カットユニット１６６は、辺の重みの順に辺を連続してカットし、サブコンポーネントを複数のクラスタに分割するように構成されている。各クラスタに含まれる全ての頂点の重みの和は、ｋ以上で２ｋ−１以下である。
【００３５】
サブコンポーネント完全グラフ辺カットユニット１６６は、辺の重みの降順に辺を連続してカットする。辺の連続カット処理において、以下の条件の１つが満足されれば、サブコンポーネント完全グラフ辺カットユニット１６６は辺をカットする。
１）辺がブリッジであり（すなわち、辺がカットされると、その辺を含むグラフが２つのサブグラフに分割される）、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない（すなわち、辺がカットされても、その辺を含むグラフが２つのサブグラフに分割されない）。
【００３６】
サブコンポーネント完全グラフ辺カットユニット１６６の動作については、具体例と図を参照して後述する。
【００３７】
サブコンポーネント完全グラフ辺カットユニット１６６の動作完了後、クラスタの１つに先に除外されたｋ中心頂点をマージすることが必要となる。マージユニット１６８は、ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージするように構成されている。ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタはさらに２つのクラスタへ分解され、その結果、各クラスタに含まる全ての頂点の重みの和は、ｋと等しくなる。
【００３８】
ラージコンポーネント分解ユニット１６によって取得されたクラスタは、辺カットユニット１４によって取得されたクラスタと共に、レコード分割／クラスタリングの結果を構成する。結果として得られた各クラスタに含まれる頂点或いはレコードの数は、ｋ以上で２ｋ−１以下である。なお、可能であれば、結果として得られたレコードは、レコード分割記憶装置（図示せず）に格納してもよい。
【００３９】
一般化ユニット１８は、結果として得られた各クラスタ毎に、頂点に対応するレコードを一般化するように構成されている。その結果、各クラスタ内のレコードは互いに分割することができなくなる。一般化ユニット１８は、周知のどのような一般化方法も用いることが可能である。一例として、複数の数値については、それらの最小公倍数として一般化することが可能である。例えば、値２、４、１０は、２０として一般化することが可能である。
他の例として、複数の都市名称は、これらの都市が属している州の名称として一般化することが可能である。例えば、都市名称「成都（Chengdu）」、「綿陽（Mianyang）」および「楽山（Leshan）」は、州名称「四川（Sichuan）」として一般化することが可能である。一般に、異なる属性は、それらが属するカテゴリの最下位のレベルとして一般化することができる。これにより、それらの属性は互いに分割することができなくなり、同時に情報の損失を最小限に保つ。なお、一般化ユニット１８からの結果出力は、匿名テーブルあるいはリスト等のような様々な形式で匿名のレコード記憶ユニット（図示せず）に格納される。
【００４０】
以上、本発明の好ましい実施の形態によるデータ匿名化装置１について説明した。
図３は、本発明の好ましい実施の形態によるデータ匿名化方法３００を説明するフローチャートである。このデータ匿名化方法３００はデータ匿名化装置１によって実行される。
ステップ３０２で、複数のデータレコードを含むテーブル内の２つのレコードごとの間の距離を計算する。
ステップ３０４で、頂点として各レコードを用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する。
ステップ３０６で、完全グラフを少なくともｋ個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする。
ステップ３０８で、各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むラージコンポーネントを複数のクラスタに分解する。
ステップ３１０で、得られた各クラスタ内のレコードを互いに分割することができないように、各クラスタの頂点に対応するレコードを一般化する。
【００４１】
図４は、図３のデータ匿名化方法３００におけるラージコンポーネント分解ステップ３０８を示すフローチャートである。
ステップ４０２で、２ｋ−１個を超える頂点を含む各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットする。
ステップ４０４で、各サブコンポーネントの中心と、２つのサブコンポーネント中心間の距離を計算する。
ステップ４０６で、計算された各サブコンポーネントの中心を頂点として用い、対応するサブコンポーネントのサイズによって頂点に重みを付け、全ての２つの頂点を辺で接続し、２つの対応するサブコンポーネント中心間の距離によって辺に重みを付けることにより、各サブコンポーネントを頂点する完全グラフを構築する。
ステップ４０８で、辺の重みの順に辺を連続してカットして、サブコンポーネントを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和をｋ以上２ｋ−１以下とする。
ステップ４１０で、ｋ中心頂点に距離が最も近いクラスタにｋ中心頂点をマージし、マージされたクラスタに含まれる全ての頂点の重みの和が２ｋに等しければ、各クラスタに含まる全ての頂点の重みの和がｋと等しくなるように、クラスタをさらに２つのクラスタに分解する。
【００４２】
本発明の実施の形態をさらに明確に示すために、実施の形態による具体例について、図５〜図８を参照して以下に説明する。これらの具体例は、本発明の好ましい実施の形態を例示するためだけのものであり、本発明を制限するものではない。
【００４３】
例えば、１０個のデータレコードT=[Q0, Q1, …, Q9], Qi={A1, A2, …, Am},i={0, 2, .., 9}を含むテーブルがあるものとする。ここで、ｍは自然数である。ｋ（＝２）−匿名テーブルを形成するために、これらの１０のデータレコードを匿名化する必要がある。
【００４４】
まず、距離計算ユニット１０が、ユークリッド距離アルゴリズムを用いることによって、全ての２つのＱ０、Ｑ１、…、Ｑ９の間の距離を計算する。その後、完全グラフ構築ユニット１２が完全グラフを構築する。
【００４５】
図５は、本発明の好ましい実施の形態による完全グラフ構築を示す概略図である。図５に示すように、図の左側は、レコードの複数の頂点を示している。
図５の右側に示すような完全グラフを形成するために、これらの頂点を２つずつ辺で接続する。説明の便宜上、２つの頂点間の各辺の長さがその辺の重み（すなわち、２つの頂点に対応する２つのレコード間の距離）を表わすものと仮定する。
【００４６】
次に、辺カットユニット１４が、前述の条件に従って辺の重みの降順に辺をカットする。図６は、本発明の好ましい実施の形態によるシーケンス制御メカニズムが導入される辺カット処理を示す概略図である。図６から分かるように、Ｑ３とＱ８の間の辺edge３８が最も長く、最大の重みを有する。Ｑ０とＱ４の間の辺edge０４が２番めに長く、・・・、Ｑ８とＱ９の間の辺edge８９が最も短い。
【００４７】
まず、辺カットユニット１４は、辺edge３８が上述した２つの条件を満足するかどうかを判定する。この具体例において、辺edge３８はブリッジではないので、カットされる。次に、辺カットユニット１４は、辺edge０４が２つの条件を満足するかどうかを判定する。辺edge０４はブリッジではないので、カットされる。
Ｑ０とＱ１の間の辺edge０１が２つの状態を満足するかどうかを判定するまで、辺カットユニット１４はそのような動作を継続する。
辺edge０１がカットされれば、グラフが２つのコンポーネントあるいはサブグラフに完全に分割されるので、辺edge０１はブリッジである。従って、結果として得られる２つのコンポーネントがそれぞれ少なくともｋ個の頂点を有するかどうかを判定することが必要となる。図示のように、辺edge０１のカットから得られた２つのコンポーネントは、それぞれ６個の頂点と４個の頂点を含んでいる。よって、辺カットユニット１４は辺edge０１をカットする。
Ｑ０とＱ９の間の辺edge０９が２つの条件を満足するかどうかを判定する時、辺カットユニット１４は、辺edge０９がカットされれば、完全グラフのコンポーネントがさらに２つの部分に分けられると判定する。
よって、得られる２つの部分が、それぞれ少なくともｋ個の頂点を有するかどうかを判定することが再び必要となる。図示のように、辺edge０９のカットから得られた２つの部分は、１個および５個の頂点をそれぞれ含んでいる。従って、条件を満足しない。よって、辺カットユニット１４は辺edge０９をカットしない。このようにして、図６の右下部分に示すように、部分ＣＱ１、ＣＱ２、ＣＱ３およびＣＱ４が最終的に取得される。
【００４８】
ここで、部分ＣＱ２、ＣＱ３およびＣＱ４は、それぞれ２個の頂点を含んでおり、したがってそれ以上分解を必要としない。すなわち、各部分ＣＱ２、ＣＱ３、ＣＱ４はクラスタである。しかしながら、部分ＣＱ１は、４つの頂点Ｑ０、Ｑ７、Ｑ８およびＱ９を含んでおり、その数は２ｋ（＝２）−１より大きい、したがって分解する必要がある。それゆえ、ラージコンポーネント分解ユニット１６は、部分ＣＱ１についてラージコンポーネント分解処理を実行する。
図７は、本発明の好ましい実施の形態によるラージコンポーネント分解処理を示す概略図である。
まず、ｋ中心頂点検出ユニット１６０が、ｋ中心頂点を検出する。図示のように、ラージコンポーネントＣＱ１のｋ中心頂点は、頂点Ｑ９である。そこで、頂点Ｑ９に接続される全ての辺をカットし、個々の分離したサブコンポーネントを取得する。この具体例においては、図７の２番目の部分図に示すように、各サブコンポーネントはただ１個の頂点を含んでいる。しかしながら、これは便宜上例として示しているだけであり、他の状況においては、各サブコンポーネントが１つ以上の頂点を含む場合もある。
【００４９】
各サブコンポーネントが１つのみ頂点を含んでいるので、計算ユニット１６２は、サブコンポーネント中心として頂点の代表値を直接用いて、サブコンポーネント中心の間の距離を計算する。サブコンポーネント完全グラフ構築ユニット１６４は、図７の３番目の部分図に示すように、ｋ中心頂点以外の全てのサブコンポーネント中心を接続し、全てのサブコンポーネントを含む完全グラフを取得する。サブコンポーネント完全グラフ辺カットユニット１６６は、図７の４番目の部分図に示すように、上述した２つの条件に従って、辺の重み（すなわち、図において示される辺の長さ）に基づいてＱ０とＱ７の間の辺をカットし、他の辺をカットしない。マージユニット１６８は、図７の５番目の部分図に示すように、頂点Ｑ９を左のコンポーネントにマージし、４つの頂点を含むクラスタを取得する。これにより、マージユニット１６８は、図７の６番目の部分図に示すように、Ｑ７とＱ８の間の辺をカットし、それぞれ２つの頂点を含む２つのクラスタを取得する。
【００５０】
図８は、本発明の好ましい実施の形態によるレコード分割の最終結果を概略的に示す。
本発明の好ましい実施の形態によるｋ（＝２）−匿名化方法により、レコードＱ０−Ｑ９はそれぞれ２つのレコードを含む５個のクラスタに分割される。
その後、一般化ユニット１８は、各クラスタについて一般化を実行し、ｋ−匿名性テーブルAT=[AQ0, AQ1, …, AQ4]を取得する。ここで、ＡＱｉは、各クラスタにおけるレコードの一般化された値を表わす。
【００５１】
以上、本発明の好ましい実施の形態によるデータ匿名化装置と方法について説明した。上記説明において、本発明の好ましい実施の形態を、具体例だけで図示しているが、そのことは、本発明が上記の手順とユニット構成に限定されることを意味するものではない。必要に応じて、これらの手段と要素を調整し、取捨選択し、組み合わせることも可能である。さらに、これらの手順と要素のいくつかは、本発明の発明概念を実現するうえで必要不可欠ではない。このように、本発明に必須の技術的特徴は、上記の特定の具体例ではなく、本発明の発明概念を実現するための最小の必要条件にのみ限定される。
【００５２】
以上、本発明についてその好適な実施例を参照して説明したが、当該技術に精通した当業者には、本発明の精神と範囲から逸脱することなく他の様々な修正、変更、追加を行うことが可能なことは明らかであろう。したがって、本発明の範囲は上記の具体的な実施例に限定されず、付記した請求項によってのみ限定される。
【００５３】
さらに、上記実施形態の一部又は全部は、以下の付記のようにも記載されうるが、これに限定されない。
【００５４】
（付記１）
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニットと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニットと、
完全グラフを少なくともｋ（所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニットと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニットと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニットとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化装置。
【００５５】
（付記２）
前記辺カットユニットは、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする付記１に記載のデータ匿名化装置。
【００５６】
（付記３）
前記辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする付記１に記載のデータ匿名化装置。
【００５７】
（付記４）
前記ラージコンポーネント分解ユニットが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ユニットと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ユニットと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ユニットと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットユニットと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージユニットとを
備えることを特徴とする付記１に記載のデータ匿名化装置。
【００５８】
（付記５）
前記サブコンポーネント完全グラフ辺カットユニットは、辺の重みに従って辺をソートし、それらの重みの降順に辺をカットすることを特徴とする付記４に記載のデータ匿名化装置。
【００５９】
（付記６）
前記サブコンポーネント完全グラフ辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つのサブグラフに分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つのサブグラフに分割されないなら、辺はブリッジでない
ことを特徴とする
付記４に記載のデータ匿名化装置。
【００６０】
（付記７）
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ステップと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ステップと、
完全グラフを少なくともｋ（ｋは所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットステップと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ステップと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ステップとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化方法。
【００６１】
（付記８）
前記辺カットステップにおいて、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする付記７に記載のデータ匿名化方法。
【００６２】
（付記９）
前記辺カットステップにおいて、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする付記７に記載のデータ匿名化方法。
【００６３】
（付記１０）
前記ラージコンポーネント分解ステップが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ステップと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ステップと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ステップと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットステップと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージステップとを
含むことを特徴とする付記７に記載のデータ匿名化方法。
【００６４】
（付記１１）
前記サブコンポーネント完全グラフ辺カットステップにおいて、辺の重みに従って辺をソートし、それらの重みの降順に辺をカットすることを特徴とする付記１０に記載のデータ匿名化方法。
【００６５】
（付記１２）
前記サブコンポーネント完全グラフ辺カットステップにおいて、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つのサブグラフに分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つのサブグラフに分割されないなら、辺はブリッジでない
ことを特徴とする
付記１０に記載のデータ匿名化方法。
【符号の説明】
【００６６】
１：データ匿名化装置
１０：距離計算ユニット
１２：完全グラフ構築ユニット
１４：辺カットユニット
１６：ラージコンポーネント分解ユニット
１８：一般化ユニット
２０：レコード記録ユニット
１６：ラージコンポーネント分解ユニット
１６０：ｋ中心頂点検出ユニット
１６２：サブコンポーネント距離計算ユニット
１６４：サブコンポーネント完全グラフ構築ユニット
１６６：サブコンポーネント完全グラフ辺カットユニット
１６８：マージユニット
【特許請求の範囲】
【請求項１】
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニットと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニットと、
完全グラフを少なくともｋ（所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニットと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニットと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニットとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化装置。
【請求項２】
前記辺カットユニットは、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする請求項１に記載のデータ匿名化装置。
【請求項３】
前記辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする請求項１に記載のデータ匿名化装置。
【請求項４】
前記ラージコンポーネント分解ユニットが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ユニットと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ユニットと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ユニットと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットユニットと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージユニットとを
備えることを特徴とする請求項１に記載のデータ匿名化装置。
【請求項５】
前記サブコンポーネント完全グラフ辺カットユニットは、辺の重みに従って辺をソートし、それらの重みの降順に辺をカットすることを特徴とする請求項４に記載のデータ匿名化装置。
【請求項６】
前記サブコンポーネント完全グラフ辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つのサブグラフに分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つのサブグラフに分割されないなら、辺はブリッジでない
ことを特徴とする
請求項４に記載のデータ匿名化装置。
【請求項７】
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ステップと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ステップと、
完全グラフを少なくともｋ（ｋは所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットステップと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ステップと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ステップとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化方法。
【請求項８】
前記辺カットステップにおいて、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする請求項７に記載のデータ匿名化方法。
【請求項９】
前記辺カットステップにおいて、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする請求項７に記載のデータ匿名化方法。
【請求項１０】
前記ラージコンポーネント分解ステップが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ステップと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ステップと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ステップと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットステップと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージステップとを
含むことを特徴とする請求項７に記載のデータ匿名化方法。
【請求項１】
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ユニットと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ユニットと、
完全グラフを少なくともｋ（所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットユニットと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ユニットと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ユニットとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化装置。
【請求項２】
前記辺カットユニットは、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする請求項１に記載のデータ匿名化装置。
【請求項３】
前記辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする請求項１に記載のデータ匿名化装置。
【請求項４】
前記ラージコンポーネント分解ユニットが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ユニットと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ユニットと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ユニットと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットユニットと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージユニットとを
備えることを特徴とする請求項１に記載のデータ匿名化装置。
【請求項５】
前記サブコンポーネント完全グラフ辺カットユニットは、辺の重みに従って辺をソートし、それらの重みの降順に辺をカットすることを特徴とする請求項４に記載のデータ匿名化装置。
【請求項６】
前記サブコンポーネント完全グラフ辺カットユニットは、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各コンポーネントに含められる頂点の重みの和が、少なくともｋである。
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つのサブグラフに分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つのサブグラフに分割されないなら、辺はブリッジでない
ことを特徴とする
請求項４に記載のデータ匿名化装置。
【請求項７】
複数のデータレコード中の２つのレコード毎の間の距離を計算する距離計算ステップと、
各レコードを頂点として用い、全ての２つの頂点を辺で接続し、２つの対応するレコードの間の距離で辺に重みを加えることにより、全てのレコードを含む完全グラフを構築する完全グラフ構築ステップと、
完全グラフを少なくともｋ（ｋは所定の自然数）個の頂点を含む複数のコンポーネントに分割するために、辺の重み順に辺を順番にカットする辺カットステップと、
各クラスタに含まれる頂点の数がｋ個と２ｋ−１個の間となるように、２ｋ−１個を超える頂点を含むコンポーネントを複数のクラスタに分解するラージコンポーネント分解ステップと、
各クラスタ内のレコードを互いに区別することができないように、各クラスタの頂点に対応するレコードを一般化する一般化ステップとを備え、
２ｋ−１個を超える頂点を含むコンポーネントをラージコンポーネントとし、ｋ個以上で２ｋ−１以下の頂点を含むコンポーネントがクラスタとする
ことを特徴とするデータ匿名化方法。
【請求項８】
前記辺カットステップにおいて、辺の重みに従って辺をソートし、かつそれらの重みの降順に辺をカットすることを特徴とする請求項７に記載のデータ匿名化方法。
【請求項９】
前記辺カットステップにおいて、以下の条件の１つが満足されれば、辺をカットする
１）辺がブリッジであり、かつ、辺をカットした後に得られる各サブグラフが少なくともｋ個の頂点を含む
２）辺がブリッジではない
ここで、辺をカットすると、その辺を含むグラフが２つの個別の区分に分割されるなら、辺はブリッジであり、
辺をカットしても、その辺を含むグラフが２つの個別の区分に分割されないなら、辺はブリッジでない
ことを特徴とする請求項７に記載のデータ匿名化方法。
【請求項１０】
前記ラージコンポーネント分解ステップが、
各ラージコンポーネントにおけるｋ中心頂点を検出し、かつｋ中心頂点以外の複数のサブコンポーネントを取得するために、検出されたｋ中心頂点と接続されている全ての辺をカットするｋ中心頂点検出ステップと、
各サブコンポーネントの中心を計算し、かつ２つのサブコンポーネント中心間の距離を計算するサブコンポーネント距離計算ステップと、
各サブコンポーネントの中心を頂点として用い、頂点を対応するサブコンポーネントのサイズ（サブコンポーネントに含まれるレコードの頂点の数によって表わされる）によって重み付けし、全ての２つの頂点を辺で接続し、辺を２つの対応するサブコンポーネント中心間の距離によって重み付けすることにより、サブコンポーネント完全グラフを構築するサブコンポーネント完全グラフ構築ステップと、
辺の重みの順に辺を連続してカットし、サブコンポーネント完全グラフを複数のクラスタに分割し、各クラスタに含まれる全ての頂点の重みの和を、ｋ以上で２ｋ−１以下とするサブコンポーネント完全グラフ辺カットステップと、
ｋ中心頂点に距離が最も近いクラスタに対してｋ中心頂点をマージし、ｋ中心頂点とマージされたクラスタに含まれる全ての頂点の重みの和が、２ｋに等しければ、クラスタを２つのクラスタに分解し、各クラスタに含まる全ての頂点の重みの和をｋと等しくするマージステップとを
含むことを特徴とする請求項７に記載のデータ匿名化方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−２２３１５（Ｐ２０１２−２２３１５Ａ）
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−１３７１８５（Ｐ２０１１−１３７１８５）
【出願日】平成２３年６月２１日（２０１１．６．２１）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２４年２月２日（２０１２．２．２）
【国際特許分類】
【出願番号】特願２０１１−１３７１８５（Ｐ２０１１−１３７１８５）
【出願日】平成２３年６月２１日（２０１１．６．２１）
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]