(57)【要約】    【課題】k-member クラスタリングにおいて、より類似性の高いサンプルが同一のクラスターに分類されるようにして、情報の損失量を従来よりも低減する。    【解決手段】メンバシップの制約条件を、一つのサンプルが複数のクラスターに帰属できるように従来のk-member クラスタリングをファジィ化する。そのとき、ファジィメンバシップはクラスターからの距離をもとに（残存メンバシップ）×（類似度）で推定する。クラスターの核となる個体の近傍にメンバシップが高い順にk 個まで個体を結合する。クラスターの核となる個体の探索と核の近傍の個体の探索とを、未結合の個体がk 個未満になるまで繰り返すことにより、匿名化レベルがk のファジィk-member クラスタリングを実現する。【選択図】図１
2013239118.tif 000002
【特許請求の範囲】
【請求項１】
多変量データの集合が与えられたとき、コンピュータが類似するｋ個のデータをまとめたクラスターにそれらのデータを分類し、各データが同一クラスターに属する他のデータと識別できないように匿名化するクラスタリング方法であって、
各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして前記メンバシップ度と関連付けられ、完全な帰属に対応するメンバシップ度からそのデータが帰属する１以上のクラスターのメンバシップ度の総計を差引いた残存メンバシップを算出できるように構成され、かつ、あるデータと他のデータとの類似度が高いほど近く定められたデータ間距離と関連付けられており、
前記コンピュータが、
（１）前記集合に属する一つのデータｒ１を選択し、
（２）どのクラスターにも帰属しないデータのうちデータｒ１から最も遠い距離にあるデータｒ２を探索し、そのクラスターに完全に帰属するメンバシップ度をデータｒ２に与えて前記クラスターの核とし、
（３）データｒ２以外のデータであって残存メンバシップがゼロ（０）でないデータのうちで、
帰属度＝（前記データの残存メンバシップ）×（データｒ２との類似度）
で算出される帰属度が最も大きいものから順次（ｋ−１）個のデータを前記データｒ２と同一のクラスターのメンバーとし、
（４）最後に前記クラスターのメンバーとされたデータを前記（１）における新たなデータｒ１として前記（２）および（３）の処理を実行し、前記集合の各データが少なくともある程度いずれかのクラスターに帰属するまで前記（１）〜（３）を繰り返すデータ匿名化用クラスタリング方法。
【請求項２】
請求項１に記載のクラスタリング方法により生成された各クラスターの代表値をそれぞれ算出し、各多変量データを、そのデータが属するクラスターの代表値で置換するデータ匿名化方法。
【請求項３】
前記代表値は、各クラスターに属するデータの平均として算出される請求項２に記載のデータ匿名化方法。
【請求項４】
前記類似度は、各データをそのデータが属するクラスターの代表値に集約する際の情報損失量ILc の逆数１／ILcとして算出される請求項２または３に記載のデータ匿名化方法。
【請求項５】
前記メンバシップ度は、
【数１】
2013239118.tif 000013
（utrはデータｒがクラスターtに帰属するメンバシップ度、ILtr はデータr をr が属するクラスターの代表値で置換するときの情報損失量、σは定数）
で算出される請求項２〜４の何れか一つの記載のデータ匿名化方法。
【請求項６】
多変量データの集合が入力されたとき、類似するｋ個のデータをまとめたクラスターにそれらのデータを分類し、各データが同一クラスターに属する他のデータと識別できないように匿名化して出力するクラスタリング装置であって、
各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして前記メンバシップ度と関連付けられ、完全な帰属に対応するメンバシップ度からそのデータが帰属する各クラスターへのメンバシップ度の総計を差引いた残存メンバシップを算出できるように構成され、かつ、あるデータと他のデータとの類似度が高いほど近く定められたデータ間距離と関連付けられており、
（１）前記集合に属する一つのデータｒ１を選択する選択部と、
（２）どのクラスターにも帰属しないデータのうちデータｒ１から最も遠い距離にあるデータｒ２を探索し、そのクラスターに完全に帰属するメンバシップ度をデータｒ２に与えて前記クラスターの核とするクラスター核探索部と、
（３）データｒ２以外のデータであって残存メンバシップがゼロ（０）でないデータのうちで、
帰属度＝（前記データの残存メンバシップ）×（データｒ２との類似度）
で算出される帰属度が最も大きいものから順次（ｋ−１）個のデータを前記データｒ２と同一のクラスターのメンバーとするクラスター生成部と、
（４）最後に前記クラスターのメンバーとされたデータを前記選択部に新たなデータｒ１として選択させ、前記クラスター核探索部に新たな核Ｓ２ａを探索させ、前記クラスター生成部にＳ２ａを核とするクラスターを生成させ、前記集合の各データが少なくともある程度いずれかのクラスターに帰属するまで前記選択部、前記クラスター核探索部および前記クラスター生成部がデータを処理するように順序立てる手順管理部とを備えるデータ匿名化用クラスタリング装置。
【請求項７】
多変量データの集合が与えられたとき、類似するｋ個のデータをまとめたクラスターにそれらのデータを分類し、各データが同一クラスターに属する他のデータと識別できないように匿名化する処理をコンピュータに実行させるクラスタリング処理のプログラムであって、
各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして前記メンバシップ度と関連付けられ、完全な帰属に対応するメンバシップ度からそのデータが帰属する各クラスターへのメンバシップ度の総計を差引いた残存メンバシップを算出できるように構成され、かつ、あるデータと他のデータとの類似度が高いほど近く定められたデータ間距離と関連付けられており、
（１）前記集合に属する一つのデータｒ１を選択する選択部と、
（２）どのクラスターにも帰属しないデータのうちデータｒ１から最も遠い距離にあるデータｒ２を探索し、そのクラスターに完全に帰属するメンバシップ度をデータｒ２に与えて前記クラスターの核とするクラスター核探索部と、
（３）データｒ２以外のデータであって残存メンバシップがゼロ（０）でないデータのうちで、
帰属度＝（前記データの残存メンバシップ）×（データｒ２との類似度）
で算出される帰属度が最も大きいものから順次（ｋ−１）個のデータを前記データｒ２と同一のクラスターのメンバーとするクラスター生成部と、
（４）最後に前記クラスターのメンバーとされたデータを前記選択部に新たなデータｒ１として選択させ、前記クラスター核探索部に新たな核Ｓ２ａを探索させ、前記クラスター生成部にＳ２ａを核とするクラスターを生成させ、前記集合の各データが少なくともある程度いずれかのクラスターに帰属するまで前記選択部、前記クラスター核探索部および前記クラスター生成部がデータを処理するように順序立てる手順管理部としての各部の処理をコンピュータに実行させるデータ匿名化用クラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、データ匿名化を実現するクラスタリング方法、装置およびプログラムに関する。より詳細には、多変量データの集合が与えられたとき、各データに対してk 個以上の類似したデータが存在するように匿名化するk −匿名化に係るクラスタリング方法、装置およびプログラムに関する。
【背景技術】
【０００２】
情報技術（IT）は非常に発展しているが、一方で情報過多への対処が望まれており、例えば大量のサンプル（個体）の特性をそれぞれ表すデータ（観測値）からある傾向を取り出すデータマイニング用のITサポートツールが提案されている。
しかし、ユーザは必ずしも上述したようなITサポートツールの恩恵を受けるとは限らない。なぜならば、ユーザは個人情報の漏洩を心配し、個人情報の提供を控えることがあるためである。プライバシー保護データマイニングは、ユーザが個人情報の漏洩を恐れることなくIT サポートを利用するための有効な方法である。
プライバシー保護データマイニングは、個人が特定されない方法でデータマイニングを実現する手法である（たとえば、非特許文献１参照）。
【０００３】
データマイニングに用いる各サンプルから個人が特定されないことを保証する技術の一つとして、k −匿名化が知られている。k −匿名化ではすべてのサンプルが少なくともk −１個の他のサンプルと区別できないように集約される（たとえば、非特許文献２参照）。
匿名化後のデータを用いてデータマイニングを行う者の立場からすると、データを集約して匿名化する際に、なるべく情報の損失が少ないことが望ましい。そのためには、互いに類似性の高いk 個以上のサンプルを同一のクラスターに分類することが望ましい。同一のクラスターに属するサンプルは、匿名化のために同一の値を有する代表サンプルに集約されるところ、各サンプルの類似性が高ければ集約の前後の差が小さいからである。したがって、k −匿名化の過程は、クラスタリングと密接な関連がある。一般に、クラスタリングは、同じグループ（クラスター）に属するサンプルがお互いに類似するように、多変量データをいくつかのグループに分類する処理である。
【０００４】
k −匿名化はk 個以上のサンプルを持つクラスターを探索し、各クラスターの観測値をプロトタイプ（代表値）にまとめることで実現できる。k-member クラスタリングはk −匿名化を目的としたクラスター抽出のためのクラスタリングモデルであって、各クラスターに属するサンプルの数がk またはk より少し大きくなるように分類する手法である（たとえば、非特許文献３参照）。
従来のクラスタリングモデルの多くは、あらかじめ決めたクラスター数でクラスター抽出を行うが、クラスターサイズ（各クラスター内の個体数）を調整することはできない。一方、k-member クラスタリングはクラスターサイズをあらかじめ決めておいてクラスター抽出を行う。
【０００５】
ここで、k −匿名化を実現するクラスタリングとして従来用いられている手法を説明しておく。非特許文献３のように、Byun らは効率的な欲張りk-member クラスタリングアルゴリズムを提案した。
いま、個体の集合をSとする。各個体は数値的な観測値であってもよいし、カテゴリー観測値、即ち、どのカテゴリーに属するかを示す値のみで表されていてもよいし、両者が混在していてもよい。各クラスターがk 個以上の個体を含むという条件のもとで、個体をクラスターに分割する。従来の欲張りk-member クラスタリングアルゴリズムでは、以下の手順で個体の分割を行う。
【０００６】
１．匿名化レベルk を決め、個体r をランダムに選択する。ここで、匿名化レベルk を定めるとは、各個体をk −１個の他の個体と区別できないように集約して併合することを意味する。即ち、k は集約（併合）の度合いを表す。
２．クラスター番号t を０にする。｜S｜＞k の間、以下を繰り返す。ただし、｜S｜は集合Sの要素（サンプル）の数である。
（ａ）個体r をr から最も遠い個体と置き換え、S からr を削除する。
（ｂ）t ＝t ＋１とする。個体r を核としてクラスターGt を生成する。
（ｃ）｜Gt｜＜k を満たすかぎりにおいて、以下の（i）、（ii）を繰り返す。
（i）クラスターGt の最近傍の個体r を探索する。
（ii）r をクラスターGt に加え、S からr を削除する。
３．｜S｜＞０の間、以下を繰り返す。
（ａ）S から個体r をランダムに選択する。
（ｂ）r の最近傍クラスターGt を探索する。
（ｃ）r をクラスターGt に加え、S からr を削除する。
【０００７】
k −匿名性が実現されているとき、それぞれのクラスターにおけるプロトタイプは数値的観測の場合は区間値で、カテゴリー観測の場合は混合されたカテゴリーで与えられる。この集約の過程は最短距離（または単連結）法と本質的に似ている。
個体の間の類似度、および個体とクラスターの間の類似度は、観測値の特性に基づいて、任意の尺度を使用できる。
たとえば、非特許文献３では、個体と個体、または個体とクラスターを併合した際の情報の損失量を類似度の尺度としている。前述のアルゴリズム中で、最近傍は、数値的観測の区間またはカテゴリー観測の併合カテゴリーの数の和が、併合後に最小になるように選択されている。併合によりクラスターGc が構築されるとすると、情報の損失量ILc は、数値的観測の区間またはカテゴリー観測の併合カテゴリーの数の和を用いて、以下のように計算される。
【０００８】
【数１】
2013239118.tif 000003
Sizei は多変量データのある変量、即ちある数値属性i の領域の大きさで、maxci、minciはそれぞれGc の最大値と最小値である。TCj はカテゴリーの特徴Cj の領域によって定義された分類木で、H（TCj）は分類木Tの高さである。Λ（∪Cj ）はGc の偏差を計算している。もしH（T ）が１ならば、第２項は異なるカテゴリーの数になる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】C. C. Aggarwal and P. S. Yu, Privacy-Preserving Data Mining: Models and Algorithms, Springer-Verlag, New York, 2008.
【非特許文献２】L. Sweeney, "k-anonymity: a model for protecting privacy," International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, vol.10, no.5, pp.557-570, 2002.
【非特許文献３】J. W. Byun, A. Kamra, E. Bertino and N. Li, "Efficient k-anonymization using clustering techniques," International Conference on Database Systems for Advanced Applications, LNCS-4.4.4.3, pp.188-200, Springer, 2007.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来から知られているk−匿名化の方法は効率よく、即ち、短い計算時間でデータの匿名化が行えるものの、以下の好ましくない側面がある。
（１）データが残り少なくなった終盤のステップで、とても広いクラスターを抽出することがある。そのため、k 個以上の個体を集約する際の情報の損失量が極端に増加する。
（２）ノイズ、即ち他のデータと相関の低い外れ値を含むデータ集合の場合、外れ値をクラスターの核に用いることがあり、そのためにデータの凝集度が小さい領域にクラスターを構築してしまうことがある。
（３）上述の特性のために、匿名化後のデータを用いたデータマイニングの精度が低下してしまう。
【００１１】
このため、
（１）データが残り少なくなった終盤のステップでも、情報の損失量が小さいクラスターを抽出することが望まれている。
（２）ノイズの影響を減らすために、外れ値をクラスターの核としたクラスターが凝集度の大きい領域を過度に侵さないことが望まれている。
この発明は、以上のような事情を考慮してなされたものであって、クラスターの境界付近にあるデータが複数のクラスターに帰属できるようにファジィメンバシップを導入することで、情報の損失量を従来よりも低減する手法を提供するものである。
【課題を解決するための手段】
【００１２】
この発明は、多変量データの集合が与えられたとき、コンピュータが類似するｋ個のデータをまとめたクラスターにそれらのデータを分類し、各データが同一クラスターに属する他のデータと識別できないように匿名化するクラスタリング方法であって、各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして前記メンバシップ度と関連付けられ、完全な帰属に対応するメンバシップ度からそのデータが帰属する１以上のクラスターのメンバシップ度の総計を差引いた残存メンバシップを算出できるように構成され、かつ、あるデータと他のデータとの類似度が高いほど近く定められたデータ間距離と関連付けられており、前記コンピュータが、（１）前記集合に属する一つのデータｒ１を選択し、（２）どのクラスターにも帰属しないデータのうちデータｒ１から最も遠い距離にあるデータｒ２を探索し、そのクラスターに完全に帰属するメンバシップ度をデータｒ２に与えて前記クラスターの核とし、
（３）データｒ２以外のデータであって残存メンバシップがゼロ（０）でないデータのうちで、帰属度＝（前記データの残存メンバシップ）×（データｒ２との類似度）で算出される帰属度が最も大きいものから順次（ｋ−１）個のデータを前記データｒ２と同一のクラスターのメンバーとし、（４）最後に前記クラスターのメンバーとされたデータを前記（１）における新たなデータｒ１として前記（２）および（３）の処理を実行し、前記集合の各データが少なくともある程度いずれかのクラスターに帰属するまで前記（１）〜（３）を繰り返すデータ匿名化用クラスタリング方法を提供する。
また異なる観点から、この発明は多変量データの集合が入力されたとき、類似するｋ個のデータをまとめたクラスターにそれらのデータを分類し、各データが同一クラスターに属する他のデータと識別できないように匿名化して出力するクラスタリング装置であって、
各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして前記メンバシップ度と関連付けられ、完全な帰属に対応するメンバシップ度からそのデータが帰属する各クラスターへのメンバシップ度の総計を差引いた残存メンバシップを算出できるように構成され、かつ、あるデータと他のデータとの類似度が高いほど近く定められたデータ間距離と関連付けられており、（１）前記集合に属する一つのデータｒ１を選択する選択部と、（２）どのクラスターにも帰属しないデータのうちデータｒ１から最も遠い距離にあるデータｒ２を探索し、そのクラスターに完全に帰属するメンバシップ度をデータｒ２に与えて前記クラスターの核とするクラスター核探索部と、（３）データｒ２以外のデータであって残存メンバシップがゼロ（０）でないデータのうちで、帰属度＝（前記データの残存メンバシップ）×（データｒ２との類似度）で算出される帰属度が最も大きいものから順次（ｋ−１）個のデータを前記データｒ２と同一のクラスターのメンバーとするクラスター生成部と、（４）最後に前記クラスターのメンバーとされたデータを前記選択部に新たなデータｒ１として選択させ、前記クラスター核探索部に新たな核Ｓ２ａを探索させ、前記クラスター生成部にＳ２ａを核とするクラスターを生成させ、前記集合の各データが少なくともある程度いずれかのクラスターに帰属するまで前記選択部、前記クラスター核探索部および前記クラスター生成部がデータを処理するように順序立てる手順管理部とを備えるデータ匿名化用クラスタリング装置を提供する。
さらに異なる観点から、この発明は多変量データの集合が与えられたとき、類似するｋ個のデータをまとめたクラスターにそれらのデータを分類し、各データが同一クラスターに属する他のデータと識別できないように匿名化する処理をコンピュータに実行させるクラスタリング処理のプログラムであって、各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして前記メンバシップ度と関連付けられ、完全な帰属に対応するメンバシップ度からそのデータが帰属する各クラスターへのメンバシップ度の総計を差引いた残存メンバシップを算出できるように構成され、かつ、あるデータと他のデータとの類似度が高いほど近く定められたデータ間距離と関連付けられており、（１）前記集合に属する一つのデータｒ１を選択する選択部と、（２）どのクラスターにも帰属しないデータのうちデータｒ１から最も遠い距離にあるデータｒ２を探索し、そのクラスターに完全に帰属するメンバシップ度をデータｒ２に与えて前記クラスターの核とするクラスター核探索部と、（３）データｒ２以外のデータであって残存メンバシップがゼロ（０）でないデータのうちで、帰属度＝（前記データの残存メンバシップ）×（データｒ２との類似度）で算出される帰属度が最も大きいものから順次（ｋ−１）個のデータを前記データｒ２と同一のクラスターのメンバーとするクラスター生成部と、（４）最後に前記クラスターのメンバーとされたデータを前記選択部に新たなデータｒ１として選択させ、前記クラスター核探索部に新たな核Ｓ２ａを探索させ、前記クラスター生成部にＳ２ａを核とするクラスターを生成させ、前記集合の各データが少なくともある程度いずれかのクラスターに帰属するまで前記選択部、前記クラスター核探索部および前記クラスター生成部がデータを処理するように順序立てる手順管理部としての各部の処理をコンピュータに実行させるデータ匿名化用クラスタリングプログラムを提供する。
また、この発明は、前述のクラスタリング方法により生成された各クラスターの代表値をそれぞれ算出し、各多変量データを、そのデータが属するクラスターの代表値で置換するデータ匿名化方法を提供する
【発明の効果】
【００１３】
この発明において、各データは、１以上のクラスターにファジィ理論のメンバシップ度を有して完全にまたはある程度帰属し得るものとして、（各データの残存メンバシップ）×（クラスターの核との類似度）で算出される帰属度が最も大きいものから順次その核のクラスターにクラスタリングされるので、クラスターの境界付近にあるデータが複数のクラスターに帰属でき、一つのデータが一つのクラスターにのみ帰属する従来の手法に比べて情報の損失量を低減することができる。
この発明によるクラスタリング装置、クラスタリングプログラムも同様の作用効果を奏する。また、この発明によるデータ匿名化方法は、前述のクラスタリング方法を適用することによって、情報損失量の少ない匿名化データを得ることができる。
【図面の簡単な説明】
【００１４】
【図１】この発明のクラスタリング方法である、ファジィk-member クラスタリングアルゴリズムの手順を示すフローチャートである。
【図２】この発明のクラスタリング方法の有効性を示す数値実験に用いた人工データを示すグラフである。
【図３】図２の人工データを用いた数値実験の結果を示すグラフである。
【図４】この発明のクラスタリング方法を協調フィルタリングに適用した数値実験の結果を示すグラフである。
【図５】この発明のクラスタリング装置のハードウェア構成を示すブロック図である。
【発明を実施するための形態】
【００１５】
以下、この発明の好ましい態様について説明する。
この発明によるデータ匿名化方法において、前記代表値は、各クラスターに属するデータの平均として算出されてもよい。
さらに、前記類似度は、データをあるクラスターc に加える際の情報損失量ILc の逆数１／ILcとして算出されてもよい。このようにすれば、あるデータをクラスターc に併合してクラスターc の代表値に集約する際の情報損失が小さいほど大きな類似度が得られる。
またさらに、前記メンバシップ度は、
【数２】
2013239118.tif 000004
（utrはデータｒがクラスターtに帰属するメンバシップ度、ILtr はデータr をr が属するクラスターの代表値で置換するときの情報損失量、σは定数）で算出されてもよい。このようにすれば、情報損失量がファジィメンバシップの計算方法でよく用いられるベル型分布のメンバシップ度が得られる。
この発明の好ましい態様は、ここで示した複数の態様のうち何れかを組み合わせたものも含む。
【００１６】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
≪ファジィk-member クラスタリングとそのアルゴリズム≫
クラスタリングに関する多くの研究で、ノイズ感度と初期値問題の観点からクリスプな分割（クラスターへの帰属がゼロ（０）または１の二値であるクラスタリング）よりもファジィな分割の方が優れていると示されている（たとえば、J. C. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum Press, 1981.、J. B. MacQueen, "Some methods of classification and analysis of multivariate observations," Proc. of 5th Berkeley Symposium on Math. Stat. and Prob., pp. 281-297, 1967. 参照）。前述の課題を解決するために、発明者はこのようなファジィ分割の特性に着目した。データ匿名化クラスタリング方法は、非特許文献３のクリスプなk-memberクラスタリングのアルゴリズムにファジィ分割の手法を導入したものである。
【００１７】
いま、n個の個体に関する数量的観測値からなるベクトルxr（r＝１,…,n）があるとする。そして、ベクトルxrがC 個のクラスターに分割されるとする。各クラスターのプロトタイプはそのクラスターに属するベクトルxrの中心点（平均ベクトルbt）で与えられる。utr を個体r がクラスターt に帰属するメンバシップ度とし、C 個のクラスターを抽出する。FCM の目的関数Ｌfcmはクラスター内の誤差の総和である。
【００１８】
【数３】
2013239118.tif 000005
【００１９】
クリスプな分割では、各個体は１つのクラスターにのみ帰属することができ、utr ∈｛０，１｝と以下の関係が成立している。
【数４】
2013239118.tif 000006
【００２０】
この発明に係るファジィな分割では、メンバシップ度を緩和し、utr ∈［０，１］として複数のクラスターへ所属できるようにする。ファジィメンバシップ度はクラスターからの距離に基づいて推定されるが、クリスプな分割と同様に、以下の条件も満たさなければならない。
【数５】
2013239118.tif 000007
θ（θ>１）はファジィ度の重みを表わす。
【００２１】
この発明のデータ匿名化クラスタリング、即ち、ファジィメンバシップを導入した欲張りファジィk-member クラスタリングのアルゴリズムは、以下のとおりである。図１は、そのアルゴリズムを示すフローチャートである。以下、図１のステップ番号と対照させながらアルゴリズムを説明する。
【００２２】
１．初期化の処理を行う。個体i の残存メンバシップをui とする。すべてのui を１にし、終了フラグを“False”にする（ステップＳ１１）。匿名化レベルk を決め、個体r をランダムに選択する（ステップＳ１３）。クラスター番号t をゼロ（０）にする（ステップＳ１５）。
【００２３】
２．次に、集合Sの要素（個体）のクラスタリングを実行する。終了フラグが“False”かつ｜S｜＞０の間、以下を繰り返す（ステップＳ１７）。ただし、｜S｜は集合S の要素数であって、いずれかのクラスターにクラスタリングされた個体は集合S から削除されていく。
（ａ）個体r をS内でr から最も遠い個体と置き換え、S からr を削除する（ステップＳ１９）。
（ｂ）t ＝t ＋１とする。個体r を核としてクラスターGt を生成する。クラスターGt の要素r のファジィメンバシップutr ＝１とし、残存メンバシップur ＝０とする（ステップＳ２３）。
【００２４】
（ｃ）終了フラグが“False”かつ｜Gt｜＜k の間、以下を繰り返す（ステップＳ２５）。
（i）残存メンバシップがur＞０のすべての個体のうちで、クラスターGt の最近傍の個体r を探索する（ステップＳ２７）。
（ii）最近傍の個体r をクラスターGt に加える（ステップＳ２９）。r ∈S ならばS からr を削除する（ステップＳ３１）。個体r の残存メンバシップを更新する（ステップＳ３３）。ur ＝ur - utr
（iii）ui ＞０となる個体が残っていなければ（ステップＳ３５）、終了フラグを“True”とする（ステップＳ３７）。
アルゴリズムの２（ａ）、即ちステップＳ１９で、クラスターGt の核（メンバシップ度が１）となる個体が選ばれる。次にファジィメンバシップの計算に基づいて近傍の個体がクラスターに併合される。まず、アルゴリズムの２（ｃ）（i）、即ちステップＳ２７では
帰属度＝（残存メンバシップui）×（類似度sit）
を計算し、最近傍を探す。アルゴリズムの２（ｃ）（ii）におけるステップＳ３３は、個体r とクラスターGt との距離を考慮したファジィメンバシップutr の推定に関わる。これらのファジィ操作は個体が境界を越えて複数のクラスターに帰属することを可能にする。すなわち、ある個体に関して、最初のクラスターへのメンバシップが小さければ、二つ目以降のクラスターに帰属することができるということである。
【００２５】
類似度sitの計算やファジィメンバシップutr の計算には、さまざまな尺度を用いることができる。たとえば、個体とクラスターの類似度としては、非特許文献３で用いられた情報の損失量ILcの逆数である１／ILcが利用できる。また、ファジィメンバシップの計算方法としては、以下のベル型分布のメンバシップ関数が利用できる。
【数６】
2013239118.tif 000008
ILtr は個体rとクラスターtとの併合後の情報損失である。σはベル型分布関数の広がりを調整する
【００２６】
以上のように、それぞれの個体をファジィメンバシップ度でクラスターに割り当てる。残存メンバシップ度がゼロ（０）より大きく、クラスター内の情報損失の総和が小さくなる場合は、他のクラスターにも帰属させることができる。同一の個体を複数のクラスターで共有するのを許可することで、データが残り少なくなった終盤のステップにおいてもコンパクトなクラスターを抽出できる。大きな情報損失がなく、個体の匿名化を行うこともできる。新しい匿名化手法は、従来のデータマイニングアルゴリズムと組み合わせることで、プライバシー保護データマイニングにおいても有効である。
【００２７】
この発明は、コンピュータが前述したデータ匿名化クラスタリング方法を実行し、入力された多変量データの集合を処理してクラスタリングを実行する装置として捉えることもできる。また、コンピュータが前述したデータ匿名化クラスタリング方法を実行するためのプログラムとして捉えることもできる。
図５は、この発明のクラスタリング装置のハードウェア構成を示すブロック図である。図５に示すように、前記装置は、データのクラスタリング処理を実行するＣＰＵ１１、処理プログラムを格納するＲＯＭ１３、ワークエリアを提供するＲＡＭ１５および処理の指示を受付けて例えば表示用データを出力する入出力回路１７を備える。
【００２８】
≪協調フィルタリングにおける欠測値の推定≫
続いて、ファジィk-member クラスタリングの具体的な応用例の一つとしての協調フィルタリングについて述べる。
協調フィルタリングは情報フィルタリング技術の一種で、情報過多を軽減するのに使われている。購買履歴データのようなユーザの選好履歴を比べてユーザ近傍を探索することにより個別の推薦を実現する処理である。協調フィルタリングの問題空間は評価値行列で与えられる。前記評価値行列の要素は複数のユーザが与えた複数アイテムの評価の行列である。
【００２９】
いま、ユーザ−アイテム間の評価値行列をX ＝[xij ]とし、その要素 xij をユーザ i，i ＝１，…，n によって与えられたアイテムj，j ＝１，…，m の数値評価であるとする。通常、ユーザはm 個のアイテムのうち、一部のみを評価する。即ち、評価値行列は通常欠測値を含んでいる。協調フィルタリングは、その欠測値（対象ユーザへのアイテムの適用性）を予測し、その予測に基づいて、未評価のアイテムで対象ユーザが好むと予想されるアイテムの推薦を行う。
協調フィルタリングは、通信販売業者のウェブサイト等、多くの実用的なシステムに適用されている。そして、個人化された推薦モデルはユーザと供給者の両方にとって有益であることが示されている。
【００３０】
GroupLensは、メモリベースの協調フィルタリングの基本的な処理方法である。詳細は、J. L. Herlocker, J. A. Konstan, A. Borchers and J. Riedl, "An algorithmic framework for performing collaborative filtering," Proc. of Conference on Research and Development in Information Retrieval, 1999. あるいは、J. A. Konstan, B. N. Miller, D. Maltz, J.L. Herlocker, L. R. Gardon and J. Riedl, "Grouplens: applying collaborative filtering to usenet news," Communications of the ACM, vol.4.0, no.3, pp.77-87, 1997. を参照されたい。
GroupLensではまずユーザの評価値の相関係数を用いてユーザ類似度を計算する。次に、対象とするユーザに対する新しいアイテムの適用性を、他のユーザが既に与えた評価の類似度の重みつき平均によって予測する。より具体的に説明すると、対象ユーザのユーザ近傍を、ユーザの評価値間の相関係数から求め、抽出している。そして、欠測値yij ≒xij は以下のようにユーザ間の類似度（相関係数）を重みとした予測値算出法を用いて求める。
【００３１】
【数７】
2013239118.tif 000009
ria はユーザi とa の評価値の間の相関係数であり、^xi はユーザi の評価値の平均である。GroupLens では元の評価値（xaj ）のかわりにユーザごとの平均からの偏差（xaj −^xa ）を用いる。これはユーザごとの評価値の偏りによる影響を軽減するためである。実用システムにおいては、効率化のために、ユーザ近傍のかわりにアイテム近傍（例えば、G. Linden, B. Smith and J. York, “Amazon.com recommendations: item-to-item collaborative filtering,” IEEE Internet Computing, Jan-Feb, pp.76-80, 2003. 参照）が使われることもある。
【００３２】
クラスタリングアルゴリズムを協調フィルタリングに適用する研究も盛んに行われており、あるユーザグループで好まれているアイテムを探索するのに局所的なクラスター構造が使われる。従来の階層的またはk-means のようなクラスタリングモデルはサイズが異なるクラスターが抽出されるが、k-member クラスタリングは等しいサイズのクラスターを抽出するため欠測値の推定に効果的である。k-member クラスタリング後のすべてのクラスターは等しいサイズで、しかもコンパクトであるという点において、k-means のようなクラスタリングモデルに比べて集約時の無駄な情報損失が低減される。しかし、前述したような課題があるため、さらなる情報損失の低減が望まれている。
【００３３】
≪欠測値の扱い≫
欠測値を含んだ不完全データからクラスターを抽出するとき、いくつかの戦略を使うことができる。例えば、R. J. Hathaway, and J. C. Bezdek, "Fuzzy c- means clustering of incomplete data," IEEE Trans. Syst., Man, Cybern., vol.B31, pp. 735-74.4., 2001. を参照されたい。
完全データのみを利用する戦略（WDS ）は欠測値をもつ個体を除去し、すべての要素が観測されているデータだけでクラスター分析を行う。しかし、協調フィルタリングではたいていの個体が欠測値を含んでいるため、WDS は役に立たない。部分的距離戦略（PDS ）は簡潔だが強力なモデルである。PDS は欠測値によらず計算効率がよく、情報損失は少ない。個体間距離は観測値のみを考慮して計算する。
以下に述べる数値実験では、PDS の概念に基づいて欠測値を取り扱った。
【００３４】
≪実験例≫
本章ではいくつかの実験結果を示す。以下の実験において、全ての属性を匿名化するべき準識別子と考える。
≪実験例１：k-匿名化と情報損失≫
はじめに、人工データによる例を示す。図２に示した人工データ集合は、３次元観測値（２つの数値と１つのカテゴリー属性）を持った３０個体からなる。
カテゴリー属性は３つのカテゴリーと高さ１の分類木でできている。すなわち、すべてただひとつのレベルにある。
【００３５】
図３はクリスプなk-member クラスタリングモデルとファジィk-member クラスタリングモデルによるクラスター分割を比較したものである。匿名性レベルk は６とした。本実験では、併合段階における最近傍は従来のk-member クラスタリングと同様に選んだ。クラスターからの距離は前述の式（１）で与えられる情報損失量ILcで測る。情報損失が最小になる最近傍の個体は一つずつクラスターに併合される。クリスプなk-member クラスタリングでは、各個体は一つのクラスターに割り当てられ、図３（ａ）のように６個の個体で構成される５個のクラスターが逐次的に抽出された。
ファジィk-member クラスタリングでは、個体がファジィメンバシップ度でクラスターへ割り当てられる。本実験では、改良した尺度を使って最近傍を選択する。
【００３６】
【数８】
2013239118.tif 000010
１/ILc はクラスターc との類似性である。残存メンバシップ値ur がゼロ（０）でないデータは、情報損失が小さければ複数のクラスターに帰属する可能性がある。
クラスターt の最近傍r のファジィ度合いutr は次のようなベル型分布（正規分布）のメンバシップ関数で計算される。
【００３７】
【数９】
2013239118.tif 000011
【００３８】
ILtr は併合後の情報損失である。σ はベル型分布関数（正規分布）の広がりを調整する。本実験ではσ ＝２とした。残存メンシップ値ur はur ＝ur −utr で更新される。個体が複数のクラスターに割り当てられるようにすると、ファジィk-member クラスタリングは６個のクラスターを逐次的に抽出した。図３（ｂ）のように各クラスターは６個の個体で構成されている。４つの個体はクラスター２(□）と６(×）で共有され、２つの個体はクラスター３(△）と５(＋）で共有されている。
【００３９】
【表１】
2013239118.tif 000012
【００４０】
表１では式（１）で計算したクラスターごとの情報損失ILcを比較している。クラスター１から４はクリスプでもファジィでも同じ情報損失となった。これは、クリスプな分割でもファジィな分割でもデータの割り当てが同じ観点で行われているからである。しかし、クリスプな分割のクラスター５は他のクラスターより情報損失が大きい。
図３（ａ）に示すように、クラスター５(＋）はとても広く分布している。特に、x2 はすべての範囲に広がっている。すなわち、匿名化データは属性に関するすべての情報を失う。その理由は、クラスターの中核をなすデータは早い段階で割り当てられ、最後のステップで残るのはノイズデータだけとなるためである。この例はクリスプなモデルがノイズの影響を大きく受けることを示唆している。一方、ファジィなモデルは最後のステップ(クラスター５，６）でもコンパクトなクラスターを抽出することができた。個体を複数のクラスターで共有することを許したからである。
提案したファジィな手法はノイズの影響を受けずにコンパクトなk-member クラスターを抽出するのに役立つ。
【００４１】
≪実験例２：欠測値の推定≫
次に、提案したクラスタリングモデルを欠測値の推定に適用する。比較実験に用いたのはIris データ集合である。４属性（m＝4 )、１５０個のサンプル（n＝150 ）で３つのクラスター（Setosa: 50 samples, Versicolour:50 samples, Virginica: 50 samples）に分かれている。このデータ集合は分類能力を評価するのによく使われるが、本実験ではGroupLens に基づく欠測値推定の能力を評価するために用いる。
テストサンプルから５０個をランダムに選び、それぞれ４つの属性のうち１つを欠測させる。データを匿名化する前に、不完全データ集合は各属性が平均ゼロ（０）、分散１となるように正規化した。そして、クリスプなk-member クラスタリングとファジィk-member クラスタリングを匿名性レベルk ＝2 ，3 ，5 ，6 ，15 ，25 ，30 ，50 と変えて適用した。クラスター分割を考えるときに,データサンプルは所属するクラスターの平均値で匿名化した。ファジィk-member クラスタリングでは,各サンプルを最大のメンバシップを持つクラスターに所属させた。GroupLens の予測アルゴリズムを匿名化データ集合に適用し、クリスプとファジィの予測能力を比較した。図４は欠測値推定の誤差を比較したものである。実験は初期値を変えて１０回ずつ行い、その平均値を図に示した。推定誤差は正規化前の空間に一般化し直したデータを使い計算した。図４はファジィな手法の方がクリスプな手法よりも性能が良いことと、GroupLens の予測アルゴリズムは従来のクリスプなk-member クラスタリングよりもファジィk-member クラスタリングと組み合わせて使うべきであることを示している。
【００４２】
以上のように、この明細書では、データのk-匿名化を達成する基本的な手法として、ファジィ化したk-member クラスタリングを説明した。ファジィな手法においては、それぞれの個体をファジィメンバシップ度でクラスターに割り当てる。残存メンバシップ値がゼロ（０）より大きく、クラスター内の情報損失の総和が小さくなる場合は他のクラスターに帰属させることができる。同一の個体を複数のクラスターで共有するのを許可することで、データが残り少なくなった終盤のステップにおいてもコンパクトなクラスターを抽出できる。大きな情報損失がなく、個体の匿名化を行うことができる。新しい匿名化手法は従来の推薦アルゴリズムと組み合わせることで、プライバシー保護協調フィルタリングにおいても有効であることが示せた。
【００４３】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００４４】
１１：ＣＰＵ
１３：ＲＯＭ
１５：ＲＡＭ
１７：入出力回路
【図１】
2013239118.tif 000014
【図２】
2013239118.tif 000015
【図３】
2013239118.tif 000016
【図４】
2013239118.tif 000017
【図５】
2013239118.tif 000018