(57)【要約】【課題】データセットの属性間に相関がある場合に、精度良くクラスタリングできるクラスタリング装置、クラスタリング方法及びクラスタリングプログラムを提供すること。【解決手段】クラスタリング装置１は、データセットのレコードを構成する複数の属性それぞれについて、属性の単独での外れ値を検出し、外れ値を有するレコードを除外又は加工する第１検出部１１と、複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価部１２と、抽出された組み合わせの相関に基づいて、組み合わせにおける外れ値を検出し、外れ値を有するレコードを除外する第２検出部１３と、第１検出部１１及び第２検出部１３により外れ値が除外又は加工されたデータセットをクラスタに分割する分割部１４と、を備える。【選択図】図１
2020140423.tif 000002
【特許請求の範囲】
【請求項１】
データセットのレコードを構成する複数の属性それぞれについて、当該属性の単独での外れ値を検出し、当該外れ値を有するレコードを除外又は加工する第１検出部と、
前記複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価部と、
抽出された前記組み合わせの相関に基づいて、当該組み合わせにおける外れ値を検出し、当該外れ値を有するレコードを除外する第２検出部と、
前記第１検出部及び前記第２検出部により外れ値が除外又は加工されたデータセットをクラスタに分割する分割部と、を備えるクラスタリング装置。
【請求項２】
前記第２検出部により除外されたレコードから新たなクラスタを生成する生成部を備える請求項１に記載のクラスタリング装置。
【請求項３】
前記生成部は、前記組み合わせの相関からの乖離方向に基づいて、前記新たなクラスタを生成する請求項２に記載のクラスタリング装置。
【請求項４】
前記クラスタのそれぞれについて、各属性値を匿名化する匿名化処理部を備える請求項１から請求項３のいずれかに記載のクラスタリング装置。
【請求項５】
データセットのレコードを構成する複数の属性それぞれについて、当該属性の単独での外れ値を検出し、当該外れ値を有するレコードを除外又は加工する第１検出ステップと、
前記複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価ステップと、
抽出された前記組み合わせの相関に基づいて、当該組み合わせにおける外れ値を検出し、当該外れ値を有するレコードを除外する第２検出ステップと、
前記第１検出ステップ及び前記第２検出ステップにおいて外れ値が除外又は加工されたデータセットをクラスタに分割する分割ステップと、をコンピュータが実行するクラスタリング方法。
【請求項６】
データセットのレコードを構成する複数の属性それぞれについて、当該属性の単独での外れ値を検出し、当該外れ値を有するレコードを除外又は加工する第１検出ステップと、
前記複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価ステップと、
抽出された前記組み合わせの相関に基づいて、当該組み合わせにおける外れ値を検出し、当該外れ値を有するレコードを除外する第２検出ステップと、
前記第１検出ステップ及び前記第２検出ステップにおいて外れ値が除外又は加工されたデータセットをクラスタに分割する分割ステップと、をコンピュータに実行させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データセットをクラスタリングする装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、個人情報の保護のため、データセットを匿名化するための様々な技術が提案されている。特にｋ−匿名化に関して、例えば非特許文献１〜５のように、様々なアルゴリズムが提案されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｋ．  ＬｅＦｅｖｒｅ，  Ｄ．  Ｊ．  ＤｅＷｉｔｔ，  ａｎｄ  Ｒ．  Ｒａｍａｋｒｉｓｈｎａｎ，  “Ｍｏｎｄｒｉａｎ  ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  ｋ−ａｎｏｎｙｍｉｔｙ，”  Ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ２２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ  （ＩＣＤＥ  ’０６），  ｐｐ．  ２５−３５．  ＩＥＥＥ，  ２００６．
【非特許文献２】Ｐ．  Ｓａｍａｒａｔｉ  ａｎｄ  Ｌ．  Ｓｗｅｅｎｅｙ，  “Ｇｅｎｅｒａｌｉｚｉｎｇ  ｄａｔａ  ｔｏ  ｐｒｏｖｉｄｅ  ａｎｏｎｙｍｉｔｙ  ｗｈｅｎ  ｄｉｓｃｌｏｓｉｎｇ  ｉｎｆｏｒｍａｔｉｏｎ，”  ｉｎ  Ｐｒｏｃ．  ｏｆ  ＰＯＤＳ  １９９８，  １９９８，  ｐ．  １８８．
【非特許文献３】Ｐ．  Ｓａｍａｒａｔｉ，  “Ｐｒｏｔｅｃｔｉｎｇ  ｒｅｓｐｏｎｄｅｎｔｓ’  ｉｄｅｎｔｉｔｉｅｓ  ｉｎ  ｍｉｃｒｏｄａｔａ  ｒｅｌｅａｓｅ，”  ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  ａｎｄ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ，  ｖｏｌ．  １３，  ｎｏ．  ６，  ｐｐ．  １０１０−１０２７，  ２００１．
【非特許文献４】Ｌ．  Ｓｗｅｅｎｅｙ，  “Ａｃｈｉｅｖｉｎｇ  ｋ−ａｎｏｎｙｍｉｔｙ  ｐｒｉｖａｃｙ  ｐｒｏｔｅｃｔｉｏｎ  ｕｓｉｎｇ  ｇｅｎｅｒａｌｉｚａｔｉｏｎ  ａｎｄ  ｓｕｐｐｒｅｓｓｉｏｎ，”  ｉｎ  Ｊ．  Ｕｎｃｅｒｔａｉｎｔｙ，  Ｆｕｚｚｉｎｅｓｓ，  ａｎｄ  Ｋｎｏｗｌｅｄｇｅ−Ｂａｓｅ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．  １０（５），  ２００２，  ｐｐ．  ５７１−５８８．
【非特許文献５】Ｊ．  Ｂｙｕｎ，  Ａ．  Ｋａｍｒａ，  Ｅ．  Ｂｅｒｔｉｎｏ，  ａｎｄ  Ｎ．  Ｌｉ，  “Ｅｆｆｉｃｉｅｎｔ  ｋ−ａｎｏｎｙｍｉｚａｔｉｏｎ  ｕｓｉｎｇ  ｃｌｕｓｔｅｒｉｎｇ  ｔｅｃｈｎｉｑｕｅｓ，”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａｂａｓｅ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ａｄｖａｎｃｅｄ  Ａｐｐｌｉｃａｔｉｏｎｓ，  １８８−２００，  ２００７，  Ｓｐｒｉｎｇｅｒ．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、従来の匿名化アルゴリズムは、外れ値を考慮していないため、データセットを匿名化する際、外れ値については除外、あるいはトップ・ボトムコーディングにより大幅に丸めるといった処理が施されていた。
しかしながら、データセットの一部の属性には、例えば「身長と体重」又は「家の広さと家族構成」等、相関関係のある組み合わせが存在する。この場合、例えば、「５０ｋｇ、１８０ｃｍ」のように、それぞれの属性単独では一般的な値であっても、組み合わせることで外れ値となるデータが存在しうる。
【０００５】
従来の匿名化アルゴリズムでは、このような属性間に相関があるデータを外れ値として扱わない場合、クラスタに特異なデータが含まれてしまう恐れがある。先の例では、体重５０ｋｇ周辺のクラスタが作成されたとすると、その殆どのレコードは身長１６０ｃｍ前後の女性であると考えられるが、このクラスタに身長１８０ｃｍの男性のレコードが含まれることになる。仮に体重５０ｋｇ程度で高身長のレコードがｋ個以上存在すれば、そのようなクラスタが生成されるが、数が少ない場合には、女性が大半を占めるクラスタに痩せ型かつ高身長の男性のレコードが含まれてしまい、精度の低いクラスタが作られてしまう。
【０００６】
本発明は、データセットの属性間に相関がある場合に、精度良くクラスタリングできるクラスタリング装置、クラスタリング方法及びクラスタリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係るクラスタリング装置は、データセットのレコードを構成する複数の属性それぞれについて、当該属性の単独での外れ値を検出し、当該外れ値を有するレコードを除外又は加工する第１検出部と、前記複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価部と、抽出された前記組み合わせの相関に基づいて、当該組み合わせにおける外れ値を検出し、当該外れ値を有するレコードを除外する第２検出部と、前記第１検出部及び前記第２検出部により外れ値が除外又は加工されたデータセットをクラスタに分割する分割部と、を備える。
【０００８】
前記クラスタリング装置は、前記第２検出部により除外されたレコードから新たなクラスタを生成する生成部を備えてもよい。
【０００９】
前記生成部は、前記組み合わせの相関からの乖離方向に基づいて、前記新たなクラスタを生成してもよい。
【００１０】
前記クラスタリング装置は、前記クラスタのそれぞれについて、各属性値を匿名化する匿名化処理部を備えてもよい。
【００１１】
本発明に係るクラスタリング方法は、データセットのレコードを構成する複数の属性それぞれについて、当該属性の単独での外れ値を検出し、当該外れ値を有するレコードを除外又は加工する第１検出ステップと、前記複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価ステップと、抽出された前記組み合わせの相関に基づいて、当該組み合わせにおける外れ値を検出し、当該外れ値を有するレコードを除外する第２検出ステップと、前記第１検出ステップ及び前記第２検出ステップにおいて外れ値が除外又は加工されたデータセットをクラスタに分割する分割ステップと、をコンピュータが実行する。
【００１２】
本発明に係るクラスタリングプログラムは、データセットのレコードを構成する複数の属性それぞれについて、当該属性の単独での外れ値を検出し、当該外れ値を有するレコードを除外又は加工する第１検出ステップと、前記複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する相関評価ステップと、抽出された前記組み合わせの相関に基づいて、当該組み合わせにおける外れ値を検出し、当該外れ値を有するレコードを除外する第２検出ステップと、前記第１検出ステップ及び前記第２検出ステップにおいて外れ値が除外又は加工されたデータセットをクラスタに分割する分割ステップと、をコンピュータに実行させるためのものである。
【発明の効果】
【００１３】
本発明によれば、データセットの属性間に相関がある場合に、精度良くクラスタリングできる。
【図面の簡単な説明】
【００１４】
【図１】実施形態に係るクラスタリング装置の機能構成を示すブロック図である。
【図２】実施形態に係るクラスタリング装置の処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係るクラスタリング装置１の機能構成を示すブロック図である。
クラスタリング装置１は、サーバ装置又はパーソナルコンピュータ等の情報処理装置（コンピュータ）であり、制御部１０及び記憶部２０の他、各種データの入出力デバイス及び通信デバイス等を備える。
【００１６】
制御部１０は、クラスタリング装置１の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、本実施形態における各機能を実現する。制御部１０は、ＣＰＵであってよい。
【００１７】
記憶部２０は、ハードウェア群をクラスタリング装置１として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ＲＯＭ、ＲＡＭ、フラッシュメモリ又はハードディスク（ＨＤＤ）等であってよい。具体的には、記憶部２０は、本実施形態の各機能を制御部１０に実行させるためのプログラム（クラスタリングプログラム）、及びこのプログラムが処理対象とするデータセット、処理途中のデータ、処理結果のクラスタデータ等を記憶する。
【００１８】
制御部１０は、第１検出部１１と、相関評価部１２と、第２検出部１３と、分割部１４と、生成部１５と、匿名化処理部１６とを備える。
制御部１０は、これらの機能部により、処理対象のデータセットを複数のクラスタに分割する。また、制御部１０は、データセットの各レコードをデータ点とし、分割された各クラスタに所属する点を重心等の代表点に変更することでｋ−匿名化を実現する。
【００１９】
第１検出部１１は、データセットのレコードを構成する複数の属性それぞれについて、各属性の単独での外れ値（例えば、年齢１１０歳、身長２００ｃｍ等）を検出し、外れ値を有するレコードを、クラスタリングの対象外として除外、又はトップ・ボトムコーディング等により加工する。
【００２０】
相関評価部１２は、複数の属性について、属性間の相関を評価し、最大の相関を有する組み合わせを抽出する。
相関関係を定量的に計測する手法は様々あり、線形の相関を示す相関係数の他、非線形の相関を算出可能なＭＩＣ（Ｍａｘｉｍａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｃｏｅｆｆｉｃｉｅｎｔ）、高次元の外れ値を検出するＣＯＰ（Ｃｏｈｅｒｅｎｃｅ  Ｐｕｒｓｕｉｔ）、ＨｉＣＳ（Ｈｉｇｈ  Ｃｏｎｔｒａｓｔ  Ｓｕｂｓｐａｃｅｓ）、ＳＯＤ（Ｓｕｂｓｐａｃｅ  Ｏｕｔｌｉｅｒ  Ｄｅｇｒｅｅ）等がある。
これらの手法のいずれを採用するかは限定されず、データセットに含まれるデータの分布によって適宜選択されてよい。
【００２１】
例えば、相関係数を用いた場合、相関値｜Ｒ｜が閾値（例えば、０．４）以上の属性Ｘ，Ｙを選択する。
なお、相関係数Ｒは、
【数１】
2020140423.tif 000003
と求められ、回帰直線は、
【数２】
2020140423.tif 000004
と表される。ここで、σＸ，σＹ，σＸＹは、属性Ｘ，Ｙそれぞれの標準偏差、及びＸ，Ｙの共分散を表す。
【００２２】
第２検出部１３は、抽出された属性の組み合わせの相関に基づいて、この組み合わせにおける外れ値を検出し、外れ値を有するレコードを除外する。
外れ値の検出には、例えば、スミルノフ・グラブス検定方法、又は四分位範囲を用いた方法等が利用可能である。また、前述のように相関係数を用いた場合には、外れ値は、回帰直線を用いた信頼区間等によって検出可能である。
【００２３】
分割部１４は、第１検出部１１及び第２検出部１３により外れ値が除外又は加工されたデータセットをクラスタに分割する。
なお、分割処理は、例えば、レコード（データ点）間の距離に基づく既存の手法が利用可能である。
【００２４】
生成部１５は、第２検出部１３により除外されたレコードから新たなクラスタを生成する。例えば、生成部１５は、組み合わせの相関からの乖離方向に基づいて、新たなクラスタを生成する。
具体的には、生成部１５は、外れ値同士をクラスタにできるかを判定する。例えば、外れ値の検出に回帰直線を用いた場合、検出された外れ値は、上振れした値と下振れした値とに分けられる。分けられたそれぞれのレコード数がｋ以上の場合、ｋ−匿名化できるため、クラスタとしてデータセットに結合する。一方、レコード数がｋ未満であれば、外れ値としてレコードは削除される。
【００２５】
匿名化処理部１６は、分割部１４又は生成部１５により生成されたクラスタのそれぞれについて、各属性値をｋ−匿名化等の手法により匿名化する。なお、匿名化の手法は限定されない。
【００２６】
次に、クラスタリング方法の手順を詳述する。
図２は、本実施形態に係るクラスタリング装置１の処理手順を示すフローチャートである。
ここでは、クラスタリング装置１は、データセットをクラスタリングし、クラスタ内のレコードが識別されないように属性値を加工して匿名化する。
【００２７】
ステップＳ１において、第１検出部１１は、データセットの属性それぞれ単独での外れ値を検出する。
【００２８】
ステップＳ２において、第１検出部１１は、ステップＳ１で検出された外れ値を有するレコードを削除、又はトップ・ボトムコーディング等の処理により加工する。
【００２９】
ステップＳ３において、相関評価部１２は、データセットの属性間の相関（例えば、前述の相関係数Ｒ）を、属性の組み合わせそれぞれについて計算する。
【００３０】
ステップＳ４において、相関評価部１２は、最大の相関を有する属性の組み合わせ、又は所定以上の相関を有する複数の組み合わせを抽出する。
【００３１】
ステップＳ５において、第２検出部１３は、ステップＳ４で抽出した属性の組み合わせによる外れ値を検出し、データセットから一旦除外する。
【００３２】
ステップＳ６において、分割部１４は、外れ値を除いたデータセットをクラスタに分割する。
【００３３】
ステップＳ７において、生成部１５は、ステップＳ５で除外された外れ値を有するレコードからなるデータセットから、１つのクラスタ、又は所定のルールに従って複数のクラスタを生成する。
【００３４】
ステップＳ８において、匿名化処理部１６は、ステップＳ６及びステップＳ７で生成されたクラスタに従って、それぞれのデータセットを匿名化し、両者を結合して出力する。
【００３５】
本実施形態によれば、クラスタリング装置１は、データセットのレコードを構成する複数の属性の単独での外れ値を検出し、外れ値を有するレコードを除外又は加工した後、最大の相関を有する属性の組み合わせにおける外れ値を検出し、外れ値を有するレコードを除外してクラスタに分割する。
したがって、クラスタリング装置１は、属性それぞれ単独では判別されない組み合わせでの外れ値を、相関を考慮することにより除外できる。これにより、データセットの属性間に相関がある場合に、クラスタリングの精度が向上し、この結果、適切な匿名化が可能となる。
【００３６】
さらに、クラスタリング装置１は、属性の組み合わせにより除外された外れ値のレコードから、新たなクラスタを生成する。
したがって、クラスタリング装置１は、外れ値のレコードが一定数以上ある場合に、これらをデータセットから削除することなく、外れ値からなるクラスタとして適切に利用できる。
【００３７】
また、クラスタリング装置１は、計算された組み合わせの相関からの乖離方向、例えば回帰直線の上方か下方かの分類等に基づいて、新たなクラスタを生成する。
したがって、クラスタリング装置１は、外れ値をさらにクラスタに分割することができ、より適切なクラスタを提供できる。
【００３８】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
【００３９】
クラスタリング装置１によるクラスタリング方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００４０】
１  クラスタリング装置
１０  制御部
１１  第１検出部
１２  相関評価部
１３  第２検出部
１４  分割部
１５  生成部
１６  匿名化処理部
２０  記憶部
【図１】
2020140423.tif 000005
【図２】
2020140423.tif 000006