(57)【要約】      （修正有）【課題】AffinityPropagationによるデータのクラスタリングを高速かつ精度よく行う。【解決手段】ｔ回目および（ｔ＋１）回目のavailabilityおよびresponsibilityの繰返し計算対象の集合Ａｔ＋１および集合Ｒｔ＋１を求める。繰り返し計算回数ｔを１インクリメントした後のｔ回目の繰返し計算対象の集合Ａｔおよび集合Ｒｔがともに空集合となるまで、availabilityおよびresponsibilityの計算と、集合Ａｔ＋１および集合Ｒｔ＋１を求める処理とを繰り返す。集合Ａｔおよび集合Ｒｔがともに空集合となったときの１インクリメントする前の繰り返し計算回数Ｔにおけるavailabilityおよびresponsibilityに基づきクラスタリング対象の全てのデータポイントのexemplarを決定する。【選択図】図１０
2016024501.tif 000002
【特許請求の範囲】
【請求項１】
記憶部と協働してAffinity  Propagationに基づいてデータ集合のクラスタリング処理を実行する制御部を有するクラスタリング装置であって、
前記制御部は、
前記データ集合に属するデータのペアの集合を要素とする集合族のうち、ｔ回目の第１メッセージの計算対象であるｔ回目の第１集合族の各要素に属する各データペアについて、ｔ回目の前記第１メッセージを再帰的に計算し、
前記第１集合族の要素のうち、ｔ回目の第２メッセージの計算対象であるｔ回目の第２集合族の各要素に属する各データペアについて、ｔ回目の前記第２メッセージを再帰的に計算し、
ｔ回目の前記第１メッセージが第１条件を充たすか、または、ｔ回目の前記第２メッセージが第２条件を充たすかを判定し、
前記第１条件が充たされる場合に、前記第１条件を充たすｔ回目の前記第１メッセージに対応するデータペアの集合であるｔ回目の前記第１集合族の要素を（ｔ＋１）回目の前記第１集合族の要素と決定し、前記第２条件が充たされる場合に、前記第２条件を充たすｔ回目の前記第２メッセージに対応するデータペアの集合であるｔ回目の前記第１集合族の要素を（ｔ＋１）回目の前記第１集合族の要素と決定し、決定した要素からなる（ｔ＋１）回目の前記第１集合族を生成し、
ｔ回目の前記第１メッセージが第３条件を充たすか、または、ｔ回目の前記第２メッセージが第４条件を充たすかを判定し、
前記第３条件が充たされる場合に、前記第３条件を充たすｔ回目の前記第１メッセージに対応するデータペアの集合であるｔ回目の前記第２集合族の要素を（ｔ＋１）回目の前記第２集合族の要素と決定し、前記第４条件が充たされる場合に、前記第４条件を充たすｔ回目の前記第２メッセージに対応するデータペアの集合であるｔ回目の前記第２集合族の要素を（ｔ＋１）回目の前記第２集合族の要素と決定し、決定した要素からなる（ｔ＋１）回目の前記第２集合族を生成する、
ことを（ｔ＋１）回目の前記第１集合族および（ｔ＋１）回目の前記第２集合族がともに空集合となるまで、ｔを１インクリメントして繰り返し、
（ｔ＋１）回目の前記第１集合族および（ｔ＋１）回目の前記第２集合族がともに空集合になったときのｔ回目の前記第１メッセージおよびｔ回目の前記第２メッセージの和の最大値を与える前記データ集合の各要素の代表要素を前記データ集合の要素ごとに求める
ことを特徴とするクラスタリング装置。
ただし、ｔ＝０のときは、前記第１メッセージおよび前記第２メッセージはそれぞれ所定の初期値であり、前記第１集合族および前記第２集合族はそれぞれ所定の初期集合族である。
【請求項２】
記憶部と協働してAffinity  Propagationに基づいてデータ集合のクラスタリング処理を実行する制御部を有するクラスタリング装置が行うクラスタリング方法であって、
前記制御部が、
前記データ集合に属するデータのペアの集合を要素とする集合族のうち、ｔ回目の第１メッセージの計算対象であるｔ回目の第１集合族の各要素に属する各データペアについて、ｔ回目の前記第１メッセージを再帰的に計算し、
前記第１集合族の要素のうち、ｔ回目の第２メッセージの計算対象であるｔ回目の第２集合族の各要素に属する各データペアについて、ｔ回目の前記第２メッセージを再帰的に計算し、
ｔ回目の前記第１メッセージが第１条件を充たすか、または、ｔ回目の前記第２メッセージが第２条件を充たすかを判定し、
前記第１条件が充たされる場合に、前記第１条件を充たすｔ回目の前記第１メッセージに対応するデータペアの集合であるｔ回目の前記第１集合族の要素を（ｔ＋１）回目の前記第１集合族の要素と決定し、前記第２条件が充たされる場合に、前記第２条件を充たすｔ回目の前記第２メッセージに対応するデータペアの集合であるｔ回目の前記第１集合族の要素を（ｔ＋１）回目の前記第１集合族の要素と決定し、決定した要素からなる（ｔ＋１）回目の前記第１集合族を生成し、
ｔ回目の前記第１メッセージが第３条件を充たすか、または、ｔ回目の前記第２メッセージが第４条件を充たすかを判定し、
前記第３条件が充たされる場合に、前記第３条件を充たすｔ回目の前記第１メッセージに対応するデータペアの集合であるｔ回目の前記第２集合族の要素を（ｔ＋１）回目の前記第２集合族の要素と決定し、前記第４条件が充たされる場合に、前記第４条件を充たすｔ回目の前記第２メッセージに対応するデータペアの集合であるｔ回目の前記第２集合族の要素を（ｔ＋１）回目の前記第２集合族の要素と決定し、決定した要素からなる（ｔ＋１）回目の前記第２集合族を生成する、
ことを（ｔ＋１）回目の前記第１集合族および（ｔ＋１）回目の前記第２集合族がともに空集合となるまで、ｔを１インクリメントして繰り返し、
（ｔ＋１）回目の前記第１集合族および（ｔ＋１）回目の前記第２集合族がともに空集合になったときのｔ回目の前記第１メッセージおよびｔ回目の前記第２メッセージの和の最大値を与える前記データ集合の各要素の代表要素を前記データ集合の要素ごとに求める
各処理を含むことを特徴とするクラスタリング方法。
ただし、ｔ＝０のときは、前記第１メッセージおよび前記第２メッセージはそれぞれ所定の初期値であり、前記第１集合族および前記第２集合族はそれぞれ所定の初期集合族である。
【請求項３】
請求項１に記載のクラスタリング装置としてコンピュータを機能させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置などに関する。
【背景技術】
【０００２】
データ集合をクラスタへ分割するクラスタリングは、データ解析における汎用的な手法の一つである。このため、従来から、多くのクラスタリング手法が提案されている。クラスタリングを行うことにより、データ集合における代表的なデータを特定できる。クラスタリング手法の一つとして、Affinity  Propagationというクラスタリング手法が提案されている。Affinity  Propagationは、k-means法などの従来のクラスタリング手法と比較して、クラスタリングの誤差が少ない、任意の類似度、例えば非対称で三角不等式の成り立たない類似度に対応する、クラスタリング結果が初期状態に依存しないなどのメリットがある。このため、Affinity  Propagationは、多くのアプリケーションにおいて用いられている。
【０００３】
Affinity  Propagationは、クラスタリングの際に、データポイントの各ペアについて、メッセージと呼ばれる値を収束するまで再帰的に計算する。そして、Affinity  Propagationは、収束したメッセージの値から、exemplarと呼ばれる各クラスタを代表するデータポイントを求める。Affinity  Propagationの計算コストは、データ集合の要素であるデータポイントの数をＮ、クラスタリングにおける再帰的計算の繰返し回数をＴとすると、Ｏ（Ｎ２Ｔ）である。Ｏ（＊）は、ランダウ記号である。
【０００４】
すなわち、Affinity  Propagationは、データポイントの数の２乗のオーダの計算コストを要するため、計算コストの高さが問題となる。このため、Affinity  Propagationは、データポイントの数が膨大なビッグデータをデータ解析の対象とする場合、クラスタリングを行う際に、非常に多くの計算時間を要することとなる。
【０００５】
そこで、Affinity  Propagationの再帰的計算を効率化し、計算コストを削減する手法が提案されている。この手法は、メッセージの値の下限値と上限値を計算し、上限値および下限値の範囲外の値であるメッセージを再帰的計算から除外（枝刈り）し、除外されないメッセージについてのみ再帰的計算を行う。効率化手法の計算コストは、除外されなかったメッセージの数をＭ、クラスタリングにおける再帰的計算の繰返し回数をＴとすると、Ｏ（Ｎ２＋ＭＴ）である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−２４２９７４号公報
【非特許文献】
【０００７】
【非特許文献１】Brendan  J．Frey  and  Delbert  Dueck，Clustering  by  passing  messages  between  data  points，Science，2007．
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、上述の従来技術では、計算コストを削減する手法においても、メッセージが効率的に除外されなければ、ＭのオーダがＮ２に等しくなる。すなわち、計算コストを削減する手法も、オリジナルのAffinity  Propagationと比べて、計算コストの削減効果が期待できず、高速にクラスタリングをおこなえないという問題が依然として存在する。
【０００９】
本願が開示する実施形態の一例は、上記に鑑みてなされたものであって、Affinity  Propagationによるデータのクラスタリングを高速かつ精度よく行うことを目的とする。
【課題を解決するための手段】
【００１０】
本願が開示する実施形態の一例は、データ集合に属するデータのペアの集合を要素とする集合族のうち、ｔ回目の第１メッセージの計算対象であるｔ回目の第１集合族の各要素に属する各データペアについて、ｔ回目の第１メッセージを再帰的に計算する。そして、第１集合族の要素のうち、ｔ回目の第２メッセージの計算対象であるｔ回目の第２集合族の各要素に属する各データペアについて、ｔ回目の第２メッセージを再帰的に計算する。そして、ｔ回目の第１メッセージが第１条件を充たすか、または、ｔ回目の第２メッセージが第２条件を充たすかを判定する。そして、第１条件が充たされる場合に、第１条件を充たすｔ回目の第１メッセージに対応するデータペアの集合であるｔ回目の第１集合族の要素を（ｔ＋１）回目の第１集合族の要素と決定し、第２条件が充たされる場合に、第２条件を充たすｔ回目の第２メッセージに対応するデータペアの集合であるｔ回目の第１集合族の要素を（ｔ＋１）回目の第１集合族の要素と決定する。そして、決定した要素からなる（ｔ＋１）回目の第１集合族を生成する。そして、ｔ回目の第１メッセージが第３条件を充たすか、または、ｔ回目の第２メッセージが第４条件を充たすかを判定する。そして、第３条件が充たされる場合に、第３条件を充たすｔ回目の第１メッセージに対応するデータペアの集合であるｔ回目の第２集合族の要素を（ｔ＋１）回目の第２集合族の要素と決定し、第４条件が充たされる場合に、第４条件を充たすｔ回目の第２メッセージに対応するデータペアの集合であるｔ回目の第２集合族の要素を（ｔ＋１）回目の第２集合族の要素と決定する。そして、決定した要素からなる（ｔ＋１）回目の第２集合族を生成する。そして、上述の処理を（ｔ＋１）回目の第１集合族および（ｔ＋１）回目の第２集合族がともに空集合となるまで、ｔを１インクリメントして繰り返す。そして、（ｔ＋１）回目の第１集合族および（ｔ＋１）回目の第２集合族がともに空集合になったときのｔ回目の第１メッセージおよびｔ回目の第２メッセージの和の最大値を与えるデータ集合の各要素の代表要素をデータ集合の要素ごとに求める。
【発明の効果】
【００１１】
本願が開示する実施形態の一例によれば、例えば、Affinity  Propagationを高速かつ精度よく行うことができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、定義１を示す図である。
【図２】図２は、定義２を示す図である。
【図３】図３は、補助定理１を示す図である。
【図４】図４は、補助定理２を示す図である。
【図５】図５は、補助定理３を示す図である。
【図６】図６は、補助定理４を示す図である。
【図７】図７は、補助定理５を示す図である。
【図８】図８は、定理１を示す図である。
【図９】図９は、定理２を示す図である。
【図１０】図１０は、クラスタリング装置の構成の一例を示すブロック図である。
【図１１】図１１は、クラスタリング処理を示すフローチャートの一例を示す図である。
【図１２】図１２は、クラスタリング処理のアルゴリズムの一例を示す図である。
【図１３】図１３は、クラスタリングプログラムを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
実施形態の説明に先立ち、以下の説明で用いる主な記号の定義、従来手法の数理的背景の説明、実施形態の数理的背景の説明を行う。その後、実施形態を説明する。
【００１４】
［主な記号の定義］
実施形態で用いる主な記号を下表に示す。以下、従来手法の数理的背景、実施形態の数理的背景、実施形態の各説明において、同一の記号を用いる。
【００１５】
【表１】
2016024501.tif 000003
【００１６】
［従来手法の数理的背景］
以下、従来手法の数理的背景を説明する。オリジナルのAffinity  Propagationは、データポイントをクラスタリングし、クラスタを代表するexemplarを求めるクラスタリング手法である。exemplarと同一クラスタに属するデータポイントをメンバという。ｘｉをｉ番目のデータポイント（ｉ＝１，２，・・・，Ｎ）とし、Ｘ＝｛ｘ１，ｘ２，・・・，ｘＮ｝とする。Affinity  Propagationは、全データポイントｘ∈Ｘについてのペア（ｘｉ，ｘｊ）の類似度ｓ（ｘｉ，ｘｊ）を入力とし、クラスタリングの結果である各クラスタのexemplarを出力とする。なお、Affinity  Propagationの入力は、類似度に限らず、例えば負のユークリッド距離、Jaccard係数など、クラスタリング対象のデータ集合に属するデータペアの相関を定量的に示す種々の指標であってもよい。
【００１７】
Affinity  Propagationは、入力された類似度に対して、exemplarとそのメンバとの類似度を最大化するようにクラスタリングを行う。Affinity  Propagationは、availability、responsibilityと呼ばれる２つのメッセージを、全てのデータポイントのペアに対して再帰的に計算する。
【００１８】
availability：ａｔ（ｘｉ，ｘｊ）は、ｔ回目の繰返し計算におけるデータポイントｘｊからｘｉへのメッセージであり、データポイントｘｉがデータポイントｘｊのexemplarとして適切であるかを定量的に表す値である。responsibility：ｒｔ（ｘｉ，ｘｊ）は、ｔ回目の繰返し計算におけるデータポイントｘｉからデータポイントｘｊのメッセージで、データポイントｘｊがデータポイントｘｉのexemplarとして適切であるかを定量的に表す値である。availabilityおよびresponsibilityは、下記の式（１）および式（２）により、再帰的に計算される。
【００１９】
【数１】
2016024501.tif 000004
【００２０】
ここで、λは、繰返し計算の中でavailabilityおよびresponsibilityが振動することを防ぐためのダンピングファクタと呼ばれる０＜λ＜１の所定定数である。上記の式（１）におけるαｔ（ｘｉ，ｘｊ）は、propagating  availabilityと呼ぶ。また、上記の式（２）におけるρｔ（ｘｉ，ｘｊ）は、propagating  responsibilityと呼ぶ。propagating  availabilityおよびpropagating  responsibilityは、下記の式（３）および下記の式（４）により、再帰的に計算される。
【００２１】
【数２】
2016024501.tif 000005
【００２２】
なお、ｔ＝０のとき、availabilityは下記の式（５）のようになり、responsibilityは下記の式（６）のようになる。
【００２３】
【数３】
2016024501.tif 000006
【００２４】
availabilityおよびresponsibilityが上記の式（１）および上記の式（２）により再帰的に計算され、収束した後、データポイントｘｊのexemplarは、下記の式（７）により計算される。
【００２５】
【数４】
2016024501.tif 000007
【００２６】
ここで、データポイントの数をＮ、再帰的計算の繰り返し計算回数をＴとすると、オリジナルのAffinity  Propagationは、全てのデータポイントのペアについてavailabilityおよびresponsibilityを計算するため、計算コストはＯ（Ｎ２Ｔ）となる。すなわち、オリジナルのAffinity  Propagationの計算コストは、データポイントの数の２乗に比例するため、データポイントの数が多くなると非常に計算時間を要することとなる。
【００２７】
［実施形態の数理的背景］
実施形態では、ｔ回目（ｔ＝０，１，２，・・・，Ｔ（Ｔはavailabilityおよびresponsibilityが収束したときの繰返し計算回数）、以下同様）の繰返し計算において、availabilityの更新を行うデータポイントペアの集合Ａｔは、図１の定義１のように定義される。集合Ａｔは、ｔ回目の繰返し計算において、availabilityの更新を行うデータポイントペアの集合を要素とする集合族である。
【００２８】
また、実施形態では、ｔ回目の繰返し計算において、responsibilityの更新を行うデータポイントペアの集合Ｒｔは、図２の定義２のように定義される。集合Ｒｔは、ｔ回目の繰返し計算において、responsibilityの更新を行うデータポイントペアの集合を要素とする集合族である。
【００２９】
availabilityおよびresponsibilityの更新を行うデータポイントペアの集合Ａｔおよび集合Ｒｔの性質について述べる前に、メッセージの収束に関する３つの性質について示す。図３の補助定理１は、availabilityおよびresponsibilityの収束に関する性質を示す。図４の補助定理２は、propagation  availabilityの収束に関する性質を示す。図５の補助定理３は、propagation  responsibilityの収束に関する性質を示す。
【００３０】
上記の３つの性質から、ｔ回目の繰返し計算においてavailabilityの更新を行うデータポイントペアの集合Ａｔに関連して、図６の補助定理４に示す性質が成り立つ。補助定理４は、availabilityの更新対象から除外されたデータポイントペアについてavailabilityの繰返し計算をさらにおこなっても、availabilityの値は変わらない、つまり、availabilityの値が収束していることを主張する。
【００３１】
同様に、ｔ回目の繰返し計算においてresponsibilityの更新を行うデータポイントペアの集合Ｒｔに関連して、図７の補助定理５に示す性質が成り立つ。補助定理５は、responsibilityの更新対象から除外されたデータポイントペアについてresponsibilityの繰返し計算をさらにおこなっても、responsibilityの値は変わらない、つまり、responsibilityの値が収束していることを主張する。
【００３２】
以上の実施形態の数理的背景の考察から、実施形態におけるクラスタリング結果および計算コストについて、図８の定理１および図９の定理２が成り立つ。すなわち、図８の定理１に示すように、実施形態のクラスタリング結果は、オリジナルのAffinity  Propagationと同じクラスタリング結果を得る。そして、実施形態のクラスタリング処理は、更新を行うメッセージ（availabilityおよびresponsibility）の平均をＭとし、繰り返し計算回数をＴとすると、Ｏ（ＭＴ）の計算コストである。
【００３３】
すなわち、実施形態は、availabilityおよびresponsibilityの値が変わらないと予想されるデータポイントペアの集合を、availabilityおよびresponsibilityの繰り返し計算の対象から除外する（再度計算しない、再帰的な計算から除外する）。よって、実施形態は、各データポイントが属するクラスタのexemplarを求めるクラスタリング処理の計算量を削減できる。
【００３４】
［実施形態］
上記の数理的背景の考察を踏まえ、以下、本願が開示するクラスタリング装置などの実施形態を説明する。以下の実施形態は、Affinity  Propagationを用いた、データポイントのクラスタリングにおいて、全てのデータポイントペアの類似度を入力とし、全データポイントをクラスタリングした結果の各クラスタのexemplarを出力する。なお、以下の実施形態は、一例を示すに過ぎず、本願が開示する技術を限定するものではない。
【００３５】
（クラスタリング装置の構成）
図１０は、クラスタリング装置の構成の一例を示すブロック図である。クラスタリング装置１０は、クラスタリング対象の全てのデータポイントｘｋ∈Ｘについての全てのデータポイントペアの類似度ｓ（ｘｉ，ｘｊ）：ｘｉ，ｘｊ∈Ｘを入力とし、全てのデータポイントｘｋ∈Ｘのexemplarを出力する。クラスタリング装置１０は、メッセージ更新部１１、計算対象更新部１２、収束判定部１３を有する。
【００３６】
先ず、クラスタリング装置１０は、図１の定義１に基づき、ｔ回目の繰り返し計算におけるavailabilityの計算対象のデータポイントペアの集合Ａｔの初期値を求める。また、クラスタリング装置１０は、図２の定義２に基づき、ｔ回目の繰り返し計算におけるresponsibilityの計算対象のデータポイントペアの集合Ｒｔの初期値を求める。クラスタリング装置１０は、集合Ａｔおよび集合Ｒｔそれぞれの初期値をメッセージ更新部１１へ入力する。
【００３７】
メッセージ更新部１１は、ｔ回目の繰返し計算対象の集合Ａｔの全ての要素であるデータポイントペアについて、上記の式（１）、（３）、（５）によりavailability：ａｔ（ｘｉ，ｘｊ）を計算する。また、メッセージ更新部１１は、同様に、ｔ回目の繰返し計算対象の集合Ｒｔの全ての要素であるデータポイントペアについて、上記の式（２）、（４）、（６）によりresponsibility：ｒｔ（ｘｉ，ｘｊ）を計算する。そして、メッセージ更新部１１は、計算したｔ回目の繰返し計算の結果であるａｔ（ｘｉ，ｘｊ）およびｒｔ（ｘｉ，ｘｊ）を計算対象更新部１２へ入力する。
【００３８】
計算対象更新部１２は、メッセージ更新部１１から入力されたｔ回目の繰り返し計算によるavailabilityおよびresponsibilityと、（ｔ−１）回目の繰返し計算によるavailabilityおよびresponsibilityに基づき、（ｔ＋１）回目のavailabilityおよびresponsibilityの繰返し計算対象の集合Ａｔ＋１および集合Ｒｔ＋１を求める。そして、計算対象更新部１２は、繰り返し計算回数ｔを１インクリメントした後、ｔ回目のavailabilityおよびresponsibilityの繰返し計算対象の集合Ａｔおよび集合Ｒｔを収束判定部１３へ入力する。
【００３９】
収束判定部１３は、計算対象更新部１２から入力された、ｔ回目のavailabilityおよびresponsibilityの繰返し計算対象の集合Ａｔおよび集合Ｒｔがともに空集合であるか否かを判定する。収束判定部１３は、集合Ａｔおよび集合Ｒｔがともに空集合でない場合に、集合Ａｔおよび集合Ｒｔをメッセージ更新部１１へ入力する。
【００４０】
一方、クラスタリング装置１０は、集合Ａｔおよび集合Ｒｔがともに空集合である場合に、１インクリメントする前の繰り返し計算回数をＴとして、上記の式（７）に基づき、クラスタリング対象の全てのデータポイントｘｋ∈Ｘのexemplarを決定して出力する。
【００４１】
（クラスタリング処理のフロー）
図１１は、クラスタリング処理を示すフローチャートの一例を示す図である。先ず、クラスタリング装置１０は、クラスタリング対象の全てのデータポイントｘｋ∈Ｘについて、全てのデータポイントペアの類似度ｓ（ｘｉ，ｘｊ）：ｘｉ，ｘｊ∈Ｘの入力を受け付ける（ステップＳ１１）。次に、クラスタリング装置１０は、繰り返し計算回数のカウンタをｔ＝０、ｔ回目のavailabilityおよびresponsibilityの繰返し計算対象の集合Ａｔおよび集合Ｒｔを空集合に初期化する（ステップＳ１２）。次に、クラスタリング装置１０は、図１の定義１に基づき集合Ａｔの初期値を、図２の定義２に基づき集合Ｒｔの初期値を、それぞれ求める（ステップＳ１３〜Ｓ１５のループ処理）。
【００４２】
メッセージ更新部１１は、ステップＳ１３〜Ｓ１５のループ処理が終了すると、集合Ａｔの全ての要素Ａｉについて、ステップＳ１６〜Ｓ２０のループ処理を繰り返す。メッセージ更新部１１は、ステップＳ１６〜Ｓ２０のループ処理内において、上記の式（５）に基づき、集合Ａｉの各要素（ｘｊ，ｘｉ）についてavailabilityを計算するループ処理を繰り返す（ステップＳ１７〜Ｓ１９）。
【００４３】
メッセージ更新部１１は、ステップＳ１７〜Ｓ１９のループ処理およびステップＳ１６〜Ｓ２０のループ処理が終了すると、集合Ｒｔの全ての要素Ｒｉについて、ステップＳ２１〜Ｓ２５のループ処理を繰り返す。メッセージ更新部１１は、ステップＳ２１〜Ｓ２５のループ処理内において、上記の式（６）に基づき、集合Ｒｉの各要素（ｘｉ，ｘｊ）についてresponsibilityを計算するループ処理を繰り返す（ステップＳ２２〜Ｓ２４）。メッセージ更新部１１は、ステップＳ２２〜Ｓ２４のループ処理およびステップＳ２１〜Ｓ２５のループ処理が終了すると、繰り返し計算回数を示すカウンタｔを１インクリメントする（ステップＳ２６）。
【００４４】
次に、メッセージ更新部１１は、ステップＳ２６で１インクリメントしたｔに関し、集合Ａｔの全ての要素Ａｉについて、ステップＳ２７〜Ｓ３１のループ処理を繰り返す。メッセージ更新部１１は、ステップＳ２７〜Ｓ３１のループ処理内において、上記の式（１）、（３）に基づき、集合Ａｉの各要素（ｘｊ，ｘｉ）についてavailabilityを計算するループ処理を繰り返す（ステップＳ２８〜Ｓ３０）。
【００４５】
メッセージ更新部１１は、ステップＳ２８〜Ｓ３０のループ処理およびステップＳ２７〜Ｓ３１のループ処理が終了すると、ステップＳ２６で１インクリメントしたｔに関し、集合Ｒｔの全ての要素Ｒｉについて、ステップＳ３２〜Ｓ３６のループ処理を繰り返す。メッセージ更新部１１は、ステップＳ３２〜Ｓ３６のループ処理内において、上記の式（２）、（４）に基づき、集合Ｒｉの各要素（ｘｉ，ｘｊ）についてresponsibilityを計算するループ処理を繰り返す（ステップＳ３３〜Ｓ３５）。
【００４６】
計算対象更新部１２は、ステップＳ３３〜Ｓ３５のループ処理およびステップＳ３２〜Ｓ３６のループ処理が終了すると、集合Ａｔのワーク集合Ａ´および集合Ｒｔのワーク集合Ｒ´を空集合に初期化する（ステップＳ３７）。なお、ワーク集合Ａ´およびワーク集合Ｒ´は、今回の１回後である次回（ｔ＋１）回目の繰り返し計算対象の集合になる。次に、計算対象更新部１２は、集合Ａｔの全ての要素Ａｉについて、ステップＳ３８〜Ｓ４８のループ処理を繰り返す。計算対象更新部１２は、ステップＳ３８〜Ｓ４８のループ処理内において、集合Ａｉの各要素（ｘｊ，ｘｉ）について、ステップＳ３９〜Ｓ４７のループ処理を繰り返す。
【００４７】
ステップＳ４０では、計算対象更新部１２は、図１の定義１の式（８）の（１）に基づき、ａ（ｘｊ，ｘｉ）≠ａ´（ｘｊ，ｘｉ）であるか否かを判定する。なお、ａ（ｘｊ，ｘｉ）は、ステップＳ２９で求めた、ｘｊ，ｘｉ∈Ａｉに関する今回の繰り返し計算におけるavailabilityであり、ａ´（ｘｊ，ｘｉ）は今回の１回前である前回の繰り返し計算におけるavailabilityである。
【００４８】
計算対象更新部１２は、ステップＳ４０の判定がＹｅｓの場合、ステップＳ４１へ処理を移す。一方、計算対象更新部１２は、ステップＳ４０の判定がＮｏの場合、ステップＳ４４へ処理を移す。ステップＳ４１では、計算対象更新部１２は、ステップＳ３８で選択した集合ＡｉをＡ´に追加する。
【００４９】
次に、計算対象更新部１２は、図２の定義２の式（９）における（２）に基づき、ステップＳ３９で選択したデータポイントペア（ｘｊ，ｘｉ）について、ｘｊ＝ｐｊまたはｘｊ＝ｑｊであるか否かを判定する（ステップＳ４２）。なお、ステップＳ４０の判定がＹｅｓかつステップＳ４２の判定がＹｅｓであれば、図２の定義２の式（９）における（２）の条件が成立する。
【００５０】
計算対象更新部１２は、ステップＳ４２の判定がＹｅｓの場合、ステップＳ４３へ処理を移す。一方、計算対象更新部１２は、ステップＳ４２の判定がＮｏの場合、ステップＳ４４へ処理を移す。ステップＳ４３では、計算対象更新部１２は、ステップＳ３９で選択したデータポイントｘｊが属する集合ＲｊをＲ´に追加する。
【００５１】
ステップＳ４４では、計算対象更新部１２は、ステップＳ３９で選択したデータポイントペア（ｘｉ，ｘｊ）∈Ａｉについて、ｘｊ≠ｐｊかつｘｊ≠ｑｊであるか否かを判定する。計算対象更新部１２は、ステップＳ４４の判定がＹｅｓの場合、ステップＳ４５へ処理を移す。一方、計算対象更新部１２は、ステップＳ４４の判定がＮｏの場合、ステップＳ４７へ処理を移す。
【００５２】
次に、計算対象更新部１２は、ステップＳ３９で選択したデータポイントペア（ｘｉ，ｘｊ）∈Ａｉについて、ａ（ｘｊ，ｑｊ）＋ｓ（ｘｊ，ｑｊ）＜ａ（ｘｊ，ｘｉ）＋ｓ（ｘｊ，ｘｊ）であるか否かを判定する（ステップＳ４５）。なお、ステップＳ４４の判定がＹｅｓかつステップＳ４５の判定がＹｅｓであれば、図２の定義２の式（９）における（３）の条件が成立する。
【００５３】
計算対象更新部１２は、ステップＳ４５の判定がＹｅｓの場合、ステップＳ４６へ処理を移す。一方、計算対象更新部１２は、ステップＳ４５の判定がＮｏの場合、ステップＳ４７へ処理を移す。ステップＳ４６では、計算対象更新部１２は、ステップＳ３９で選択したデータポイントｘｊが属する集合ＲｊをＲ´に追加する。
【００５４】
計算対象更新部１２は、ステップＳ３９〜Ｓ４７のループ処理およびステップＳ３８〜Ｓ４８のループ処理が終了すると、集合Ｒｔの全ての要素Ｒｉについて、ステップＳ４９〜Ｓ５６のループ処理を繰り返す。計算対象更新部１２は、ステップＳ４９〜Ｓ５６のループ処理内において、集合Ｒｉの各要素（ｘｉ，ｘｊ）について、ステップＳ５０〜Ｓ５５のループ処理を繰り返す。
【００５５】
ステップＳ５１では、計算対象更新部１２は、図２の定義２の式（９）の（３）に基づき、ｒ（ｘｉ，ｘｊ）≠ｒ´（ｘｉ，ｘｊ）であるか否かを判定する。なお、ｒ（ｘｉ，ｘｊ）は、ステップＳ３４で求めた、ｘｉ，ｘｊ∈Ｒｉに関する今回の繰り返し計算におけるresponsibilityであり、ｒ´（ｘｉ，ｘｊ）は今回の１回前である前回の繰り返し計算におけるresponsibilityである。
【００５６】
計算対象更新部１２は、ステップＳ５１の判定がＹｅｓの場合、ステップＳ５２へ処理を移す。一方、計算対象更新部１２は、ステップＳ５１の判定がＮｏの場合、ステップＳ５５へ処理を移す。ステップＳ５２では、計算対象更新部１２は、ステップＳ４９で選択した集合ＲｉをＲ´に追加する。
【００５７】
次に、計算対象更新部１２は、図１の定義１の式（８）における（１）に基づき、ステップＳ５０で選択したデータポイントペア（ｘｉ，ｘｊ）∈Ｒｔについて、ｒ（ｘｉ，ｘｊ）＞０またはｒ´（ｘｉ，ｘｊ）＞０であるか否かを判定する（ステップＳ５３）。なお、ステップＳ５１の判定がＹｅｓかつステップＳ５３の判定がＹｅｓであれば、図１の定義１の式（８）における（１）の条件が成立する。
【００５８】
計算対象更新部１２は、ステップＳ５３の判定がＹｅｓの場合、ステップＳ５４へ処理を移す。一方、計算対象更新部１２は、ステップＳ５３の判定がＮｏの場合、ステップＳ５５へ処理を移す。ステップＳ５４では、計算対象更新部１２は、ステップＳ５０で選択したデータポイントｘｊが属する集合ＡｊをＡ´に追加する。
【００５９】
計算対象更新部１２は、ステップＳ５０〜Ｓ５５のループ処理およびステップＳ４９〜Ｓ５６のループ処理が終了すると、繰り返し計算回数を示すカウンタｔを１インクリメントする（ステップＳ５７）。次に、計算対象更新部１２は、ステップＳ５７で１インクリメントしたｔについての集合ＡｔをステップＳ４１、Ｓ５４で生成された集合Ａ´とし、同じく集合ＲｔをステップＳ４３、Ｓ５２で生成された集合Ｒ´とする（ステップＳ５８）。
【００６０】
次に、収束判定部１３は、ステップＳ５８で求めた次の繰り返し計算回数における集合Ａｔおよび集合Ｒｔが、ともに空集合であるか否かを判定する（ステップＳ５９）。収束判定部１３は、ステップＳ５９の判定がＹｅｓの場合、ステップＳ６０へ処理を移す。一方、収束判定部１３は、ステップＳ５９の判定がＮｏの場合、ステップＳ２７へ処理を移す。なお、収束判定部１３は、ステップＳ２７へ処理を移す際に、ステップＳ５８で求めた集合Ａｔおよび集合Ｒｔを、メッセージ更新部１１へ入力する。
【００６１】
次に、クラスタリング装置１０は、クラスタリング対象の全てのデータポイントｘｉ∈Ｘについて、ステップＳ６０〜Ｓ６２のループ処理を繰り返す。クラスタリング装置１０は、ステップＳ６０〜Ｓ６２のループ処理内のステップＳ６１において、ステップＳ６０で選択したデータポイントｘｊが属するexemplarを、ステップＳ５９の判定がＹｅｓになった際のｔの１回前の計算回数をＴとした上記の式（７）に基づき求める。クラスタリング装置１０は、ステップＳ６０〜Ｓ６２のループ処理が終了すると、ステップＳ６０〜Ｓ６２のループ処理で求めた全てのexemplarを出力する（ステップＳ６３）。クラスタリング装置１０は、ステップＳ６３が終了すると、クラスタリング処理を終了する。
【００６２】
（クラスタリング処理のアルゴリズム）
図１２は、クラスタリング処理のアルゴリズムの一例を示す図である。以下、クラスタリング処理のＡｌｇｏｒｉｔｈｍ１と、図１１に示すクラスタリング処理を示すフローチャートとの対応関係を説明する。
【００６３】
図１２に示す第０〜２行は、図１１に示すステップＳ１２に該当する。図１２に示す第３〜５行は、図１１に示すステップＳ１３〜Ｓ１５に該当する。
【００６４】
図１２に示す第６〜１０行は図１１に示すステップＳ１６〜Ｓ２０に該当し、第７〜９行はステップＳ１７〜Ｓ１９に該当し、第８行はステップＳ１８に該当する。また、図１２に示す第１１〜１５行は図１１に示すステップＳ２１〜Ｓ２５に該当し、第１２〜１４行はステップＳ２２〜Ｓ２４に該当し、第１３行はステップＳ２３に該当する。また、図１２に示す第１６行は、図１１に示すステップＳ２６に該当する。
【００６５】
図１２に示す第１７〜５４行は、図１１に示すステップＳ２７〜Ｓ５４に該当する。ここで、図１２に示す第１８〜２２行は図１１に示すステップＳ２７〜Ｓ３１に該当し、第１９〜２１行はステップＳ２８〜Ｓ３０に該当し、第２０行はステップＳ２９に該当する。また、図１２に示す第２３〜２７行は図１１に示すステップＳ３２〜Ｓ３６に該当し、第２４〜２６行はステップＳ３３〜Ｓ３５に該当し、第２５行はステップＳ３４に該当する。
【００６６】
また、図１２に示す第２８〜２９行は、図１１に示すステップＳ３７に該当する。また、図１２に示す第３０〜４４行は、図１１に示すステップＳ３８〜Ｓ４８に該当する。ここで、図１２に示す第３１〜４３行は図１１に示すステップＳ３９〜Ｓ４７に該当し、第３２〜３７行はステップＳ４０〜Ｓ４３に該当し、第３８〜４２行はステップＳ４４〜Ｓ４６に該当する。さらに、図１２に示す第３２行は図１１に示すステップＳ４０に該当し、第３３行はステップＳ４１に該当し、第３４行はステップＳ４２に該当し、第３５行はステップＳ４３に該当する。また、図１２に示す第３８行は図１１に示すステップＳ４４に該当し、第３９行はステップＳ４５に該当し、第４０行はステップＳ４６に該当する。
【００６７】
また、図１２に示す第４５〜５４行は、図１１に示すステップＳ４９〜Ｓ５６に該当し、図１２に示す第４６〜５３行は図１１に示すステップＳ５０〜Ｓ５５に該当する。ここで、図１２に示す第４７行は図１１に示すステップＳ５１に該当し、第４８行はステップＳ５２に該当し、第４９行はステップＳ５３に該当し、第５０行はステップＳ５４に該当する。
【００６８】
また、図１２に示す第５５行は図１１に示すステップＳ５７に該当し、第５６〜５７行はステップＳ５８に該当する。また、図１２に示す第５８行は、図１１に示すステップＳ５９に該当する。また、図１２に示す第５９〜６１行は、図１１に示すステップＳ６０〜Ｓ６２に該当する。
【００６９】
（実施形態による効果）
実施形態は、Affinity  Propagationにおいて、全てのデータポイントのペアに対してメッセージの繰返し計算を行うのではなく、一部のデータポイントのペアに対してのみメッセージの繰返し計算を行う。すなわち、実施形態は、繰返し計算においてメッセージの値が変更される可能性があるデータポイントのペアを求め、求めたデータポイントペアについてのメッセージのみを繰返し計算の対象とすることにより、オリジナルのAffinity  Propagationと比較して、クラスタリングの処理速度がより向上する。
【００７０】
また、実施形態は、繰返し計算においてメッセージの値が変わらないデータポイントペアに関しては、メッセージの更新をおこなわない（枝刈りする）。このため、実施形態は、オリジナルのAffinity  Propagationとクラスタリング結果が同一になる。さらに、実施形態は、ユーザによる事前のパラメータ調整を要さず、より簡易にクラスタリングができる。
【００７１】
（実施形態のシステム構成について）
図１０に示したクラスタリング装置１０の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、クラスタリング装置１０の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００７２】
また、クラスタリング装置１０においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）およびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、クラスタリング装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００７３】
また、実施形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００７４】
（プログラムについて）
また、実施形態において説明したクラスタリング装置１０のＣＰＵなどの制御装置が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、制御装置が実行する処理をコンピュータが実行可能な言語で記述した検索プログラムを作成することもできる。この場合、コンピュータが検索プログラムを実行することにより、実施形態と同様の効果を得ることができる。さらに、検索プログラムをコンピュータ読み取り可能な記録媒体に記録して、記録媒体に記録された検索プログラムをコンピュータに読み込ませて実行することにより実施形態と同様の処理を実現できる。以下に、図１０に示したクラスタリング装置１０と同様の機能を実現するプログラムを実行するコンピュータの一例を説明する。
【００７５】
図１３は、クラスタリングプログラムを実行するコンピュータを示す図である。コンピュータ１０００は、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらは、バス１０８０によって接続される。
【００７６】
図１３に示すように、メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。また、ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０３１に接続される。また、ディスクドライブインタフェース１０４０は、ディスクドライブ１０４１に接続される。ディスクドライブ１０４１には、磁気ディスクや光ディスクなどの着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０は、例えばマウス１０５１、キーボード１０５２に接続される。また、ビデオアダプタ１０６０は、例えばディスプレイ１０６１に接続される。
【００７７】
ここで、図１３に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、検索プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。
【００７８】
また、実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出す。そして、ＣＰＵ１０２０が、検索プログラムの各手順を実行する。
【００７９】
なお、クラスタリングプログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られない。すなわち、プログラムモジュール１０９３およびプログラムデータ１０９４は、着脱可能な記憶媒体に記憶され、ディスクドライブなどを介してＣＰＵ１０２０によって読み出されてもよい。
【００８０】
クラスタリングプログラムにかかるプログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）など）を介して接続された他のコンピュータに記憶されていてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出され、実行されてもよい。
【００８１】
また、クラスタリングプログラムのモジュール分割は、例えば図１０に示すメッセージ更新部１１、計算対象更新部１２、収束判定部１３およびその他の処理を実行する機能部それぞれが実行する処理単位でおこなってもよい。しかし、モジュールの分割および統合は、これに限らず、処理効率や保守性などを考慮し、適宜なされてもよい。
【００８２】
以上の実施形態ならびにその変形は、本願が開示する技術に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【００８３】
１０  クラスタリング装置
１１  メッセージ更新部
１２  計算対象更新部
１３  収束判定部
【図１】
2016024501.tif 000008
【図２】
2016024501.tif 000009
【図３】
2016024501.tif 000010
【図４】
2016024501.tif 000011
【図５】
2016024501.tif 000012
【図６】
2016024501.tif 000013
【図７】
2016024501.tif 000014
【図８】
2016024501.tif 000015
【図９】
2016024501.tif 000016
【図１０】
2016024501.tif 000017
【図１１】
2016024501.tif 000018
【図１２】
2016024501.tif 000019
【図１３】
2016024501.tif 000020