(57)【要約】【課題】暗号化したデータを高速にクラスタリングできるクラスタリング装置、クラスタリング方法及びクラスタリングプログラムを提供すること。【解決手段】クラスタリング装置１は、暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理部１１と、クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出部１２と、クラスタ毎に、データセットのうち、重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理部１３と、を備える。【選択図】図１
2020095437.tif 000002
【特許請求の範囲】
【請求項１】
暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理部と、
前記クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出部と、
前記クラスタ毎に、前記データセットのうち、前記重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理部と、を備えるクラスタリング装置。
【請求項２】
前記重心算出部は、前記クラスタ毎に、前記分割処理を複数回実行した後に当該クラスタの前記重心を算出する請求項１に記載のクラスタリング装置。
【請求項３】
前記初期処理部は、前記初期レコードをランダムに選択する請求項１又は請求項２に記載のクラスタリング装置。
【請求項４】
前記分割処理部による処理結果として、複数のクラスタに重複して所属したレコードがある場合、当該レコード毎に、最も前記重心との距離が近いクラスタのみに所属させる第１調整処理を並列に実行する第１調整部を備える請求項１から請求項３のいずれかに記載のクラスタリング装置。
【請求項５】
前記分割処理部による処理結果として、いずれのクラスタにも所属しなかったレコードがある場合、当該レコード毎に、最も前記重心との距離が近いクラスタに所属させる第２調整処理を並列に実行する第２調整部を備える請求項１から請求項４のいずれかに記載のクラスタリング装置。
【請求項６】
前記分割処理部による処理結果として、所定の大きさに満たないクラスタがある場合、当該クラスタ毎に、当該クラスタに所属しているレコードを重心間の距離が最も近いクラスタに所属させる第３調整処理を並列に実行する第３調整部を備える請求項１から請求項５のいずれかに記載のクラスタリング装置。
【請求項７】
暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理ステップと、
前記クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出ステップと、
前記クラスタ毎に、前記データセットのうち、前記重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理ステップと、をコンピュータが実行するクラスタリング方法。
【請求項８】
暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理ステップと、
前記クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出ステップと、
前記クラスタ毎に、前記データセットのうち、前記重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理ステップと、をコンピュータに実行させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化されたデータセットをクラスタリングする装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来、データの匿名化手法として、例えば非特許文献１〜３に示されるように、ｋ−匿名化のアルゴリズムが数多く提案されてきた。これらの手法は、ユーザが持つデータセットをユーザ自身が匿名化することを想定しているため、全ての演算が平文で処理される。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｌ．  Ｓｗｅｅｎｅｙ，  “Ａｃｈｉｅｖｉｎｇ  ｋ−ａｎｏｎｙｍｉｔｙ  ｐｒｉｖａｃｙ  ｐｒｏｔｅｃｔｉｏｎ  ｕｓｉｎｇ  ｇｅｎｅｒａｌｉｚａｔｉｏｎ  ａｎｄ  ｓｕｐｐｒｅｓｓｉｏｎ，”  ｉｎ  Ｊ．  Ｕｎｃｅｒｔａｉｎｔｙ，  Ｆｕｚｚｉｎｅｓｓ，  ａｎｄ  Ｋｎｏｗｌｅｄｇｅ−Ｂａｓｅ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．  １０（５），  ２００２，  ｐｐ．  ５７１−５８８．
【非特許文献２】Ｋ．  ＬｅＦｅｖｒｅ，  Ｄ．  Ｊ．  ＤｅＷｉｔｔ，  ａｎｄ  Ｒ．  Ｒａｍａｋｒｉｓｈｎａｎ，  “Ｉｎｃｏｇｎｉｔｏ：  Ｅｆｆｉｃｉｅｎｔ  ｆｕｌｌ−ｄｏｍａｉｎ  ｋ−ａｎｏｎｙｍｉｔｙ，”  ｉｎ  Ｐｒｏｃ．  ｏｆ  ＳＩＧＭＯＤ  ２００５，  ２００５，  ｐｐ．  ４９−６０．
【非特許文献３】Ｋ．  ＬｅＦｅｖｒｅ  ｅｔ  ａｌ．，  “Ｍｏｎｄｒｉａｎ  ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  ｋ−ａｎｏｎｙｍｉｔｙ，”  ｉｎ  Ｐｒｏｃ．  ｏｆ  ｔｈｅ  ２２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ  （ＩＣＤＥ  ’０６），  ＩＥＥＥ，  ２００６，  ｐｐ．  ２５−３５．
【非特許文献４】Ｋｏｈｌｍａｙｅｒ  Ｆ，  Ｐｒａｓｓｅｒ  Ｆ，  Ｅｃｋｅｒｔ  Ｃ，  Ｋｕｈｎ  ＫＡ．  “Ａ  ｆｌｅｘｉｂｌｅ  ａｐｐｒｏａｃｈ  ｔｏ  ｄｉｓｔｒｉｂｕｔｅｄ  ｄａｔａ  ａｎｏｎｙｍｉｚａｔｉｏｎ，”  Ｊ  Ｂｉｏｍｅｄ  Ｉｎｆｏｒｍ  ２０１３  Ｄｅｃ  １２．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
匿名化を外部に委託する場合、又は複数機関の持つデータを併せて匿名化する場合は、データは暗号化される必要がある。例えば、非特許文献４の手法では、複数機関で匿名化を行うことを想定しているが、データ保有者がプロトコルに参加する必要がある、確定的暗号を用いる必要があり匿名性が低下する等の課題があった。
【０００５】
また、前述のｋ−匿名化アルゴリズムは、平文上では高速に実行できるが、同じアルゴリズムをそのまま暗号化されたデータに対して適用した場合、次の問題がある。
秘密計算では、データを秘匿した状態で加法及び乗法が可能なため、理論上は任意の計算が秘匿した状態で実現可能である。しかし、Ｇａｒｂｌｅｄ  Ｃｉｒｃｕｉｔ、秘密分散、準同型暗号等、いずれの計算手法を用いた場合でも処理が遅く、大規模なデータに対しては現実的な時間で目的の機能を果たすことが困難であることが知られている。
【０００６】
本発明は、暗号化したデータを高速にクラスタリングできるクラスタリング装置、クラスタリング方法及びクラスタリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明に係るクラスタリング装置は、暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理部と、前記クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出部と、前記クラスタ毎に、前記データセットのうち、前記重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理部と、を備える。
【０００８】
前記重心算出部は、前記クラスタ毎に、前記分割処理を複数回実行した後に当該クラスタの前記重心を算出してもよい。
【０００９】
前記初期処理部は、前記初期レコードをランダムに選択してもよい。
【００１０】
前記クラスタリング装置は、前記分割処理部による処理結果として、複数のクラスタに重複して所属したレコードがある場合、当該レコード毎に、最も前記重心との距離が近いクラスタのみに所属させる第１調整処理を並列に実行する第１調整部を備えてもよい。
【００１１】
前記クラスタリング装置は、前記分割処理部による処理結果として、いずれのクラスタにも所属しなかったレコードがある場合、当該レコード毎に、最も前記重心との距離が近いクラスタに所属させる第２調整処理を並列に実行する第２調整部を備えてもよい。
【００１２】
前記クラスタリング装置は、前記分割処理部による処理結果として、所定の大きさに満たないクラスタがある場合、当該クラスタ毎に、当該クラスタに所属しているレコードを重心間の距離が最も近いクラスタに所属させる第３調整処理を並列に実行する第３調整部を備えてもよい。
【００１３】
本発明に係るクラスタリング方法は、暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理ステップと、前記クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出ステップと、前記クラスタ毎に、前記データセットのうち、前記重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理ステップと、をコンピュータが実行する。
【００１４】
本発明に係るクラスタリングプログラムは、暗号化されたデータセットのレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる初期処理ステップと、前記クラスタそれぞれについて、所属するレコード全体の重心を算出する重心算出ステップと、前記クラスタ毎に、前記データセットのうち、前記重心との距離が近いレコードから順に当該クラスタに所属させる分割処理を並列に実行する分割処理ステップと、をコンピュータに実行させるためのものである。
【発明の効果】
【００１５】
本発明によれば、暗号化したデータを高速にクラスタリングできる。
【図面の簡単な説明】
【００１６】
【図１】実施形態に係るクラスタリング装置の機能構成を示すブロック図である。
【図２】実施形態に係るクラスタリング方法における分割処理のアルゴリズムを例示する図である。
【図３】実施形態に係る第１調整処理及び第２調整処理を含むアルゴリズムを例示する図である。
【図４】実施形態に係る第３調整処理及び匿名化の処理を含むアルゴリズムを例示する図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施形態の一例について説明する。
図１は、本実施形態に係るクラスタリング装置１の機能構成を示すブロック図である。
クラスタリング装置１は、サーバ装置又はパーソナルコンピュータ等の情報処理装置（コンピュータ）であり、制御部１０及び記憶部２０の他、各種データの入出力デバイス及び通信デバイス等を備える。
【００１８】
制御部１０は、クラスタリング装置１の全体を制御する部分であり、記憶部２０に記憶された各種プログラムを適宜読み出して実行することにより、本実施形態における各機能を実現する。制御部１０は、ＣＰＵであってよい。
【００１９】
記憶部２０は、ハードウェア群をクラスタリング装置１として機能させるための各種プログラム、及び各種データ等の記憶領域であり、ＲＯＭ、ＲＡＭ、フラッシュメモリ又はハードディスク（ＨＤＤ）等であってよい。具体的には、記憶部２０は、本実施形態の各機能を制御部１０に実行させるためのプログラム（クラスタリングプログラム）、及びこのプログラムが処理対象とするデータセット、各種の変数、フラグ等を記憶する。
【００２０】
制御部１０は、初期処理部１１と、重心算出部１２と、分割処理部１３と、第１調整部１４と、第２調整部１５と、第３調整部１６とを備える。制御部１０は、これらの機能部により、処理対象のデータセットを暗号化されたまま複数のクラスタに分割する。
クラスタリング装置１は、データセットの各レコードをデータ点とし、分割された各クラスタに所属する点を重心等の代表点に変更することでｋ−匿名化を実現する。
【００２１】
初期処理部１１は、暗号化されたデータセットの複数のレコードを所定数のクラスタに分割する際に、各クラスタに少なくとも１つの初期レコードを割り当てる。
初期レコードの割当方法は限定されないが、本実施形態では、処理速度を優先し、初期処理部１１は、初期レコードをランダムに選択する。
【００２２】
重心算出部１２は、クラスタそれぞれについて、所属するレコード全体の重心を算出する。
クラスタに所属するレコードは、分割処理部１３による分割処理の度に増加していく。したがって、重心は分割処理の度に更新されてもよいが、本実施形態では、処理速度を優先し、重心算出部１２は、クラスタ毎に、分割処理を複数回実行した後にクラスタの重心を算出して更新する。例えば、重心算出部１２は、繰り返し処理中の毎回の更新を省略し、所定回数の分割処理が完了した後に１回、あるいは、所定回数の分割処理が完了するまでに数回、重心を更新してもよい。
【００２３】
分割処理部１３は、クラスタ毎に、データセットのうち、重心との距離が近いレコードから順にこのクラスタに所属させる分割処理を並列に所定回数実行する。実行回数は、例えば、ｋ−匿名化におけるクラスタの最小数ｋに、適宜設定される調整数αを加算したｋ＋α回であってよい。
これにより、分割処理部１３は、重心からの距離が近いレコードを探索するという処理を、クラスタの数だけ並列化して実行し、処理速度を向上させる。
【００２４】
第１調整部１４は、分割処理部１３による処理結果として、複数のクラスタに重複して所属したレコードがある場合、該当するレコード毎に、最も重心との距離が近いクラスタのみに所属させ、他のクラスタへの所属を解除する第１調整処理を並列に実行する。
【００２５】
第２調整部１５は、分割処理部１３による処理結果として、いずれのクラスタにも所属しなかったレコードがある場合、該当するレコード毎に、最も重心との距離が近いクラスタに所属させる第２調整処理を並列に実行する。
【００２６】
第３調整部１６は、分割処理部１３による処理結果として、所定の大きさ、すなわちｋ−匿名化における最小数ｋに満たないクラスタがある場合、該当するクラスタ毎に、このクラスタに所属しているレコードを、重心間の距離が最も近い他のクラスタに所属させる第３調整処理を並列に実行する。
【００２７】
図２は、本実施形態に係るクラスタリング方法における分割処理のアルゴリズムＡを例示する図である。
アルゴリズムＡでは、暗号化されたデータセットＥ（Ｄ）、ｋ−匿名化におけるパラメータｋ、及び調整パラメータαが入力される。
【００２８】
まず、ｒｉ［０］を、データセットＥ（Ｄ）のｉ番目のレコードの値（データ点）とする。さらに、ｒｉ［ｊ］を、レコードｒｉがｊ番目のクラスタに所属している（＝Ｅ（１））か否か（＝Ｅ（０））を示すフラグとする（ステップ２）。
データセットのレコード数がｎ、クラスタ数がＫのとき、１≦ｉ≦ｎ、１≦ｊ≦Ｋにおいて、ｒｉ［ｊ］はＥ（０）に初期化される（ステップ３）。
【００２９】
また、ｄｉ［ｊ］を、ｒｉ［０］とクラスタｃｊの重心ｇ（ｃｊ）との距離とする（ステップ４）。
１≦ｉ≦ｎ、１≦ｊ≦Ｋにおいて、ｄｉ［ｊ］はＥ（∞）に初期化される（ステップ５）。
【００３０】
次に、データセットＥ（Ｄ）からＫ＝ｆｌｏｏｒ（ｎ／ｋ）個のレコードがランダムに選択される（ステップ６）。
ｉ番目のクラスタに対してｉ番目のレコードが選択されたとすると、ｒｉ［ｉ］はＥ（１）に、ｇ（ｃｉ）はＥ（ｒｉ［０］）に更新される（ステップ７）。
【００３１】
ステップ９から１５において、Ｋ個のクラスタ毎に、分割処理がｋ＋α回繰り返される。この分割処理は、クラスタの数と同数に並列化され、ステップ１２と１３とがクラスタの単位で並列実行される。
【００３２】
分割処理部１３は、クラスタｃｊに対して、重心ｇ（ｃｊ）との距離が最小となるレコードｉ’を、いずれのクラスタにも所属していないレコードの中から選択する（ステップ１２）。そして、分割処理部１３は、ｒｉ’［ｊ］及びｄｉ’［ｊ］を更新する（ステップ１３）。
【００３３】
ｋ＋α回の繰り返し処理が完了すると、クラスタｃｊには、フラグｒｉ［ｊ］がＥ（１）となっているレコードｒｉが所属している。
重心算出部１２は、全てのクラスタｃｊについて、重心ｇ（ｃｊ）を更新する（ステップ１７）。
【００３４】
なお、繰り返しの回数は、パラメータαにより調整されるが、この回数が多くなるほど、複数のクラスタに重複して所属するレコードが増加し、回数が少なくなるほど、いずれのクラスタにも所属しないレコードが増加する。
パラメータαは、状況に応じて適宜設定されるが、正しくクラスタリングされなかったレコードについては、次の処理により調整される。
【００３５】
図３は、本実施形態に係る第１調整処理及び第２調整処理を含むアルゴリズムＢを例示する図である。
【００３６】
ステップ２３〜２７の第１調整処理では、複数のクラスタに所属したレコード、すなわち、ｒｉ［ｊ］の和（１≦ｊ≦Ｋ）がＥ（０）でもＥ（１）でもないレコードｒｉが調整される。第１調整部１４は、これらのレコードを並列に処理する。
【００３７】
第１調整部１４は、各レコードｒｉについて、重心からの距離ｄｉ［ｊ］が最小のクラスタｃ’ｊを選択し（ステップ２５）、フラグｒｉ［ｊ’］をＥ（１）に、その他のフラグ∀ｒｉ［ｊ≠ｊ’］をＥ（０）に更新する（ステップ２６）。
【００３８】
ステップ２９〜３３の第２調整処理では、いずれのクラスタにも所属しないレコード、すなわち、ｒｉ［ｊ］の和（１≦ｊ≦Ｋ）がＥ（０）のレコードｒｉが調整される。第２調整部１５は、これらのレコードを並列に処理する。
【００３９】
第２調整部１５は、各レコードｒｉについて、重心からの距離が最小のクラスタｃ’ｊを選択し（ステップ３１）、フラグｒｉ［ｊ’］をＥ（１）に更新する（ステップ３２）。
【００４０】
第１調整処理及び第２調整処理が終了すると、全てのクラスタｃｊについて、重心ｇ（ｃｊ）が更新される（ステップ３４）。
【００４１】
図４は、本実施形態に係る第３調整処理及び匿名化の処理を含むアルゴリズムＣを例示する図である。
【００４２】
ステップ４３〜４７の第３調整処理では、クラスタに所属するレコードの数がｋより小さい、すなわちｒｉ［ｊ］の和（１≦ｉ≦ｎ）がＥ（ｋ）より小さいクラスタｃｊが調整される。第３調整部１６は、これらのクラスタを並列に処理する。
【００４３】
第３調整部１６は、調整対象のクラスタｃｊについて、重心間の距離が最小の他のクラスタｃ’ｈを選択し（ステップ４５）、クラスタｃｊの全レコードをクラスタｃ’ｈに所属させるため、フラグｒｉ［ｈ’］をＥ（１）に、フラグｒｉ［ｊ］をＥ（０）に更新する（ステップ４６）。
【００４４】
続いて、制御部１０は、ｋ−匿名化のため、全レコードの値ｒｉ［０］を、所属するクラスタｃｊの重心ｇ（ｃｊ）に更新する（ステップ４８〜５０）。
そして、制御部１０は、ｒｉ［０］の集合を、クラスタリングされたデータセットＥ（Ｄ’）として出力する（ステップ５１）。
【００４５】
本実施形態によれば、クラスタリング装置１は、暗号化されたデータセットのレコードをクラスタに分割する際に、はじめから分割するクラスタの数を決定し、各クラスタに少なくとも１つの初期レコードを割り当てた後、クラスタ毎に、重心との距離が近いレコードから順にこのクラスタに所属させる分割処理を並列に実行する。
【００４６】
従来のクラスタリング手法では、全てのレコードに対してどのクラスタに属するかの判定（Ａｒｇｍｉｎ）処理が必要となる。例えば、各レコードとクラスタとの距離を計算した上で所属するクラスタを決定し、クラスタの更新を行うという処理が全てのレコードに対して行われるが、このアルゴリズムは並列処理が困難であり、少なくともレコードの数だけＡｒｇｍｉｎ又はＡｒｇｍａｘの処理が必要であった。
一方、クラスタリング装置１は、各クラスタからレコードまでの距離を計算し、その後クラスタの重心を更新するため、クラスタの数と同数の並列化処理が可能となる。したがって、重心との距離が近いレコードを探索するという重い処理を並列化することで、暗号文上でもデータセットのクラスタリング（例えば、ｋ−匿名化）を高速に実行できる。
【００４７】
クラスタリング装置１は、クラスタの重心を再計算する頻度を、クラスタが更新される頻度よりも減らすことで、処理を高速化できる。なお、再計算の頻度は、クラスタリングの精度とのトレードオフにより、適宜設定されてよい。
また、クラスタリング装置１は、各クラスタの初期レコードをランダムに選択することで、処理を高速化できる。
【００４８】
クラスタリング装置１は、分割処理の結果、複数のクラスタに重複して所属したレコードがある場合、これらのレコード毎に、最も重心との距離が近いクラスタのみに所属させる第１調整処理を並列に実行する。
また、クラスタリング装置１は、分割処理の結果、いずれのクラスタにも所属しなかったレコードがある場合、これらのレコード毎に、最も重心との距離が近いクラスタに所属させる第２調整処理を並列に実行する。
さらに、クラスタリング装置１は、分割処理の結果、所定の大きさに満たないクラスタがある場合、これらのクラスタ毎に、所属しているレコードを重心間の距離が最も近い他のクラスタに所属させる第３調整処理を並列に実行する。
したがって、クラスタリング装置１は、分割処理によりクラスタリングが十分にできなかった部分を調整でき、さらに、これらの各種調整処理を並列化することで高速に実行できる。
【００４９】
以上、本発明の実施形態について説明したが、本発明は前述した実施形態に限るものではない。また、前述した実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、実施形態に記載されたものに限定されるものではない。
【００５０】
クラスタリング装置１によるクラスタリング方法は、ソフトウェアにより実現される。ソフトウェアによって実現される場合には、このソフトウェアを構成するプログラムが、情報処理装置（コンピュータ）にインストールされる。また、これらのプログラムは、ＣＤ−ＲＯＭのようなリムーバブルメディアに記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。さらに、これらのプログラムは、ダウンロードされることなくネットワークを介したＷｅｂサービスとしてユーザのコンピュータに提供されてもよい。
【符号の説明】
【００５１】
１  クラスタリング装置
１０  制御部
１１  初期処理部
１２  重心算出部
１３  分割処理部
１４  第１調整部
１５  第２調整部
１６  第３調整部
２０  記憶部
【図１】
2020095437.tif 000003
【図２】
2020095437.tif 000004
【図３】
2020095437.tif 000005
【図４】
2020095437.tif 000006