(57)【要約】【課題】情報量の損失を低減できる一般化階層木の生成装置、方法及びプログラムを提供すること。【解決手段】生成装置１は、複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択部１１と、第２の属性が特定の値域であるレコードのうち、第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成部１２と、下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成部１３と、を備える。【選択図】図１
2018010453.tif 000002
【特許請求の範囲】
【請求項１】
複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択部と、
前記第２の属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成部と、
下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成部と、を備える一般化階層木の生成装置。
【請求項２】
前記第２生成部は、未選択の属性を選択し、当該選択した属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした前記下位階層のノードの数よりも少ない各値域内に含まれるレコード数が略均等となる前記上位階層のノードを生成し、
前記下位階層のノード及び前記上位階層のノードにおける前記第１の属性の値域の包含関係に基づいて、前記上位階層のノードの数を調整する調整部を備える請求項１に記載の一般化階層木の生成装置。
【請求項３】
前記調整部は、包含関係にある前記下位階層のノード及び前記上位階層のノードの合計数が閾値を超える場合、当該包含関係にあるノードの全値域を２つに分割して調整後のノードとし、前記合計数が前記閾値以下の場合、当該包含関係にあるノードの全値域を１つの調整後のノードとする請求項２に記載の一般化階層木の生成装置。
【請求項４】
各階層のノードの値域に対して、選択した属性の特定の値域を、一般化の条件として出力する出力部を備える請求項１から請求項３のいずれかに記載の一般化階層木の生成装置。
【請求項５】
複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択ステップと、
前記第２の属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成ステップと、
下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成ステップと、をコンピュータが実行する一般化階層木の生成方法。
【請求項６】
複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択ステップと、
前記第２の属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成ステップと、
下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成ステップと、をコンピュータに実行させるための一般化階層木の生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データセットの匿名化手法における一般化階層木の生成装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、個人を識別され得る属性を含んだデータセットにおいて、プライバシ保護の観点から、属性値の一部を一般化し、データを組み合わせても個人が特定されないようにする匿名化手法が提案されている。
例えば、ｋ匿名化と呼ばれる手法では、属性値を一般化するための一般化階層を構築する必要がある（例えば、非特許文献１〜３参照）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】原田邦彦，佐藤嘉則，  “一般化階層木の自動生成と情報エントロピーによる歪度評価を伴うｋ−匿名化手法，”  研究報告コンピュータセキュリティ（ＣＳＥＣ），  ２０１０−ＣＳＥＣ−５０（４７），  １−７，  ２０１０−０６−２４
【非特許文献２】Ｉｗｕｃｈｕｋｗｕ，  Ｔ．  ａｎｄ  Ｎａｕｇｈｔｏｎ，  Ｊ．  Ｆ．  （２００７），  “Ｋ−Ａｎｏｎｙｍｉｚａｔｉｏｎ  ａｓ  Ｓｐａｔｉａｌ  Ｉｎｄｅｘｉｎｇ：  Ｔｏｗａｒｄ  Ｓｃａｒａｂｌｅ  ａｎｄ  Ｉｎｃｒｅｍｅｎｔａｌ  Ａｎｏｎｙｍｉｚａｔｉｏｎ，”  Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ｔｈｅ  ３３ｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｖｅｒｙ  Ｌａｒｇｅ  Ｄａｔａ  Ｂａｓｅｓ，  ＶＬＤＢ，  ｐａｇｅｓ  ７４６−７５７．
【非特許文献３】Ｂｙｕｎ，  Ｊ．  −Ｗ．，  Ｋａｍｒａ，  Ａ．，  Ｂｅｒｔｉｎｏ，  Ｅ．，  ａｎｄ  Ｌｉ，  Ｎ．  （２００７），  “Ｅｆｆｉｃｉｅｎｔ  ｋ−Ａｎｏｎｙｍｉｔｙ  Ｕｓｉｎｇ  Ｃｌｕｓｔｅｒｉｎｇ  Ｔｅｃｈｎｉｑｕｅ，”  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ａｄｖａｎｃｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  ｐａｇｅｓ  １８８−２００．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、既存の手法により構築された一般化階層を用いた匿名化では、データが必要以上に一般化され情報量の損失が大きくなる場合があった。
【０００５】
本発明は、情報量の損失を低減できる一般化階層木の生成装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明に係る一般化階層木の生成装置は、複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択部と、前記第２の属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成部と、下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成部と、を備える。
【０００７】
前記第２生成部は、未選択の属性を選択し、当該選択した属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした前記下位階層のノードの数よりも少ない各値域内に含まれるレコード数が略均等となる前記上位階層のノードを生成し、前記生成装置は、前記下位階層のノード及び前記上位階層のノードにおける前記第１の属性の値域の包含関係に基づいて、前記上位階層のノードの数を調整する調整部を備えてもよい。
【０００８】
前記調整部は、包含関係にある前記下位階層のノード及び前記上位階層のノードの合計数が閾値を超える場合、当該包含関係にあるノードの全値域を２つに分割して調整後のノードとし、前記合計数が前記閾値以下の場合、当該包含関係にあるノードの全値域を１つの調整後のノードとしてもよい。
【０００９】
前記生成装置は、各階層のノードの値域に対して、選択した属性の特定の値域を、一般化の条件として出力する出力部を備えてもよい。
【００１０】
本発明に係る一般化階層木の生成方法は、複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択ステップと、前記第２の属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成ステップと、下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成ステップと、をコンピュータが実行する。
【００１１】
本発明に係る一般化階層木の生成プログラムは、複数の属性からなるデータセットに含まれる第１の属性に対して、最も相関の大きい第２の属性を選択する選択ステップと、前記第２の属性が特定の値域であるレコードのうち、前記第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となる最下位の階層のノードを生成する第１生成ステップと、下位階層のノードを統合し、当該下位階層のノードの数よりも少ない上位階層のノードを生成する第２生成ステップと、をコンピュータに実行させる。
【発明の効果】
【００１２】
本発明によれば、データセットの匿名化手法における情報量の損失が低減される。
【図面の簡単な説明】
【００１３】
【図１】実施形態に係る生成装置の機能構成を示すブロック図である。
【図２】実施形態に係る相関及び属性値の分布を表現する方法の一例を示す図である。
【図３】実施形態に係る上位階層の調整方法を例示する図である。
【図４】実施形態に係る一般化階層木の生成方法を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態の一例について説明する。
本実施形態に係る生成装置１は、複数の属性からなるデータセットにおいて、個人を識別可能な属性の組み合わせ（準識別子）に対して、属性値を一般化することにより匿名化する場合に、一般化レベル毎の属性値を定義した一般化階層木を生成する。
【００１５】
生成装置１は、制御部（例えば、ＣＰＵ）及び記憶部（例えば、ＨＤＤ）を備えたサーバ装置又はＰＣなどの情報処理装置（コンピュータ）であり、記憶部に記憶されたソフトウェア（生成プログラム）を制御部が読み込み、実行することにより、本実施形態に係る各種機能を実現する。
【００１６】
図１は、本実施形態に係る生成装置１の機能構成を示すブロック図である。
生成装置１は、選択部１１と、第１生成部１２と、第２生成部１３と、調整部１４と、出力部１５とを備える。
【００１７】
選択部１１は、入力として、評価の対象となるデータセットＤ、データセットＤに含まれる準識別子ＡＴＴＲ、及び一般化階層木を生成する対象である属性ａｔｔｒｆ∈ＡＴＴＲが与えられる。
選択部１１は、与えられた第１の属性に対して、最も相関の大きい第２の属性ａｔｔｒｇを選択する。
【００１８】
具体的には、選択部１１は、データセットＤにおける全てのレコードｒｐの属性ａｔｔｒｆの属性値ｒｐ［ａｔｔｒｆ］と、∀ａｔｔｒ∈ＡＴＴＲ＼｛ａｔｔｒｆ｝の属性値ｒｐ［ａｔｔｒ］との相関を求め、相関が最大の属性を選択する。
属性間の相関は、レコードの散布図を生成して相関係数から、あるいは、統計情報に基づく関連性の高低から求められる。例えば、属性値ｒｐ［ａｔｔｒ］の値又は値域毎のレコードについての、属性ａｔｔｒｆの属性値ｒｐ［ａｔｔｒｆ］の平均値又は中央値が最も離れる属性が選択されてよい。
【００１９】
第１生成部１２は、第２の属性が特定の値域（単一の値又は値の範囲）であるレコードのうち、第１の属性の値を区分けした各値域内に含まれるレコード数が所定の範囲となるように、最下位の階層のノードを生成する。具体的には、詰め込み問題におけるアルゴリズムが用いられ、この結果、一般化階層木における最下位の各ノードには、ある一定数以上のレコードが含まれる。
なお、本処理における各種のパラメータは、適宜ユーザからの入力を受け付けることとしてよい。
【００２０】
ここで、選択部１１及び第１生成部１２によるノードの生成手法では、ユーザからの入力に基づいて第２の属性を選択、及び一般化階層木の最下位ノードを生成するためのインタフェースを提供してもよい。
例えば、生成装置１は、相関及び属性値の分布を視覚的に表現する出力を行い、ユーザから選択入力又はパラメータ入力などを受け付ける。
【００２１】
図２は、本実施形態に係る相関及び属性値の分布を表現する方法の一例を示す図である。
この例では、着目する属性ａｔｔｒｆとしての身長を一方の軸、相関を調べる属性ａｔｔｒｑとしての性別を他方の軸としてヒートマップを作成し表示されている。
これにより、ａｔｔｒｑ（性別）の属性値毎のａｔｔｒｆ（身長）の分布に重なりが少なく、中央値又は平均値が乖離していること、すなわち相関が大きいことを、ユーザは視覚的に判断でき、さらに属性値の分布と境界線とを視認しつつ、ノードの境界の調整を適切に行うことができる。
【００２２】
第２生成部１３は、下位階層のノードを統合し、この下位階層のノードの数よりも少ない上位階層のノードを生成する。
例えば、第２生成部１３は、下位階層のノード２つを上位階層のノード１つに統合するなどの規則に従って、一般化階層木を構成してもよいが、本実施形態では、一例として以下の手順を採用する。
【００２３】
第２生成部１３は、未選択の属性を順に選択し、選択した属性が特定の値域（単一の値又は値の範囲）であるレコードのうち、第１の属性の値を区分けした各値域内に含まれるレコード数が略均等となるようにノードを生成し、調整部１４により上位階層のノードとして調整する。
ここで、第２生成部１３により生成されるノードの数は、生成済みの下位階層のノードの数よりも少ない。
【００２４】
調整部１４は、生成済みの下位階層のノード及び第２生成部１３により生成されたノードにおける第１の属性の値域の包含関係に基づいて、上位階層のノードの数を調整する。
例えば、調整部１４は、包含関係にある下位階層のノード及び上位階層のノードの合計数が閾値（例えば、４個）を超える場合、この包含関係にあるノードの全値域を２つに分割して調整後の上位階層のノードとする。一方、合計数が閾値以下の場合、包含関係にあるノードの全値域を１つの調整後のノードとする。
なお、本処理における各種のパラメータは、適宜ユーザからの入力を受け付けることとしてよい。
【００２５】
図３は、本実施形態に係る第２生成部１３及び調整部１４による上位階層の調整方法を例示する図である。
この調整方法では、第１の属性（ａｔｔｒｆ）と他の属性（ａｔｔｒｑ∈ＡＴＴＲ＼｛ａｔｔｒｆ，ａｔｔｒｇ｝）を元に、上位階層のノードを調整する。
【００２６】
例えばａｔｔｒｆ：身長、ａｔｔｒｇ：性別、ａｔｔｒｑ：既往歴とし、第１生成部１２により、「ａｔｔｒｇ（性別）＝男性」の場合に「−１６２（ｃｍ）」，「１６３−１６４」，「１６５−１６６」，「１６７」，「１６８」，…，「１７５」，「１７６−１７８」，「１７９−」というノードの区分け（Ａ）ができている。
また、第２生成部１３により、ａｔｔｒｆ及びａｔｔｒｑから、「ａｔｔｒｑ（既往歴）＝有」の場合に「−１５７」，「１５８−１６２」，「１６３−１６５」，「１６６−１７０」，「１７１−１７４」，「１７５−」というノードの区分け（Ｂ）ができている。
【００２７】
ここで、（Ａ）の区分けと（Ｂ）の区分けとで範囲の重複が合計５区分以上ある場合は、区分を２つに分割し（Ｘ）、５区分未満の場合は区分を大きい方の１つにまとめ（Ｙ）、この結果、上位階層のノードの区分け（Ｃ）が生成される。
これにより、例えば、「ａｔｔｒｇ（性別）＝男性」かつ「ａｔｔｒｑ（既往歴）＝有」のレコードの属性値ｒｐ［ａｔｔｒｆ］＝１７２は、「１７１−１７２」に一般化される。
【００２８】
出力部１５は、全ての属性を順に選択し、調整を行った後の一般化階層木を出力する。
このとき、各階層のノードの値域（一般化した属性値）に対して、選択した属性の特定の値域を、一般化の条件として合わせて出力する。
例えば、「ａｔｔｒｇ（性別）＝男性」かつ「ａｔｔｒｑ（既往歴）＝有」のレコードの属性値ｒｐ［ａｔｔｒｆ］＝１７２は、「１７１−１７２」に一般化するという情報が階層木に基づく一般化の条件として出力される。
【００２９】
図４は、本実施形態に係る生成装置１による一般化階層木の生成方法を示すフローチャートである。
【００３０】
ステップＳ１において、選択部１１は、一般化階層木を生成する対象である属性ａｔｔｒｆと、他の属性それぞれとの相関を算出する。
ステップＳ２において、選択部１１は、ステップＳ１で算出された相関が最大の属性ａｔｔｒｇを選択する。
【００３１】
ステップＳ３において、第１生成部１２は、属性ａｔｔｒｇの値域（例えば、性別の男性又は女性）毎に、一般化階層木の最下層のノードを生成する。
【００３２】
ステップＳ４において、第２生成部１３は、属性ａｔｔｒｆ，ａｔｔｒｇ以外の属性ａｔｔｒｑを選択する。
ステップＳ５において、第２生成部１３は、属性ａｔｔｒｑの値域（例えば、既往歴の有無）毎に、一般化階層木における生成済みのノードの上位階層のノードを生成する。
【００３３】
ステップＳ６において、調整部１４は、生成済みのノードと、ステップＳ５で生成されたノードとの階層間における包含関係に基づいて、上位階層のノードの数及び値域を調整する。
【００３４】
ステップＳ７において、第２生成部１３は、ステップＳ４で全ての属性を選択したか否かを判定する。この判定がＹＥＳの場合、処理はステップＳ８に移り、判定がＮＯの場合、処理はステップＳ４に戻る。
【００３５】
ステップＳ８において、出力部１５は、属性ａｔｔｒｆの一般化階層木、及びこの階層木を用いる際の一般化条件を出力する。
【００３６】
本実施形態によれば、生成装置１は、最も相関の大きい属性を選択することで、最下位の階層のノード数を最大にできるので、データセットの匿名化手法における一般化に伴う情報量の損失が低減される。
【００３７】
また、生成装置１は、一般化階層木の上位階層を生成する過程において、各属性の値に応じたノードの区分けを行った後、生成済みのノードとの包含関係に基づいてノード数を調整する。したがって、生成装置１は、各属性との関連性に基づいて、適切に一般化階層木の上位階層を生成でき、匿名化手法における一般化レベルを上げた場合の情報量の損失を低減できる。
【００３８】
さらに、生成装置１は、ノード数を調整する過程において、包含関係にあるノード数の合計を閾値と比較することにより、調整後のノード数を決定する。したがって、生成装置１は、一般化によってノード数が減少し過ぎることによる情報量の損失を抑制できる。
【００３９】
また、生成装置１は、一般化階層木と共に、この階層木を用いる際の一般化条件を合わせて出力することにより、匿名化処理を効率化できる。
【００４０】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、本実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本実施形態に記載されたものに限定されるものではない。
【００４１】
本実施形態の生成装置１が備える各機能部は、複数の情報処理装置（コンピュータ）に分散されてもよい。また、本実施形態の機能は、複数のサーバにより負荷分散させたクラウドシステムにより提供されてもよい。
【００４２】
生成装置１による生成方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００４３】
１  生成装置
１１  選択部
１２  第１生成部
１３  第２生成部
１４  調整部
１５  出力部
【図１】
2018010453.tif 000003
【図２】
2018010453.tif 000004
【図３】
2018010453.tif 000005
【図４】
2018010453.tif 000006