"AffinityPropagationに基づきクラスタリングを行うクラスタリング装置であって、データペアの類似度を入力として、該データペアのメッセージの上限ちと下限値を記憶手段に出力する上限値下限値計算手段と、前記記憶手段から前記メッセージの上限値と下限値を取得し、グラフ構造を生成して前記記憶手段に出力するグラフ計算手段と、前記記憶手段から前記グラフ構造を取得し、グラフにおけるエッジに対応する前記エッジの収束値を繰り返し演算により求め、該記憶手段に格納する繰り返し計算手段と、前記記憶手段から前記エッジの収束値を取得し、エッジではないデータペアの収束値を求め、該記憶手段に格納する収束値計算手段と、前記記憶手段の全てのデータペアの収束値から各データポイントのexemplarを求めるexemplar計算手段と、を有することを特徴とするクラスタリング装置。AffinityPropagationに基づきクラスタリングを行うクラスタリング方法であって、上限値下限値計算手段が、データペアの類似度を入力として、該データペアのメッセージの上限ちと下限値を記憶手段に出力する上限値下限値計算ステップと、グラフ計算手段が、前記記憶手段から前記メッセージの上限値と下限値を取得し、グラフ構造を該記憶手段に出力するグラフ計算ステップと、繰り返し計算手段が、前記記憶手段から前記グラフ構造を取得し、グラフにおけるエッジに対応する前記エッジの収束値を繰り返し演算により求める繰り返し計算ステップと、収束値計算手段が、前記記憶手段から前記エッジの収束値を取得し、エッジではないデータペアの収束値を求め、該記憶手段に格納する収束値計算ステップと、exemplar計算手段が、前記記憶手段の全てのデータペアの収束値から各データポイントのexemplarを求めるexemplar計算ステップと、を行うことを特徴とするクラスタリング方法。コンピュータを、請求項1記載のクラスタリング装置の各手段として機能させるためのクラスタリングプログラム。しかし、AffinityPropagationの一つの弱点として計算時間があげられる。すなわち、データポイントの数が多くなった場合、AffinityPropagationによりクラスタリングを行うには非常に計算時間を要する。そのため、AffinityPropagationにおいて再帰的にメッセージの値を計算するには、データポイントの2乗の計算コストを要する。この問題を解決するために、Jiaらにより近年FSAPが提案された文献:YangqingJiaandJingdongWangandChangshuiZhangandXianShengHuaFindingimageexemplarsusingfastsparseaffinitypropagationACMIntconfMultimedia2008。しかし、FSAPは高速にクラスタリングを行うことができるが、クラスタリングの結果がオリジナルのAffinityPropagationの結果と異なるという弱点がある。高速なクラスタリングと引き換えにクラスタリングの結果を犠牲にするのは、アプリケーションの観点から好ましくない。本発明は、上記の点に鑑みなされたもので、オリジナルのAffinityPropagationとクラスタリング結果が同じで、かつ、より高速なクラスタリングを行うことが可能なクラスタリング装置及び方法及びプログラムを提供することを目的とする。上記の課題を解決するために、本発明は、AffinityPropagationに基づきクラスタリングを行うクラスタリング装置であって、データペアの類似度を入力として、該データペアのメッセージの上限ちと下限値を記憶手段に出力する上限値下限値計算手段と、前記記憶手段から前記メッセージの上限値と下限値を取得し、グラフ構造を生成して前記記憶手段に出力するグラフ計算手段と、前記記憶手段から前記グラフ構造を取得し、グラフにおけるエッジに対応する前記エッジの収束値を繰り返し演算により求め、記憶手段に出力する繰り返し計算手段と、前記記憶手段から前記エッジの収束値を取得し、エッジではないデータペアの収束値を求め、前記記憶手段に出力する収束値計算手段と、前記記憶手段の全てのデータペアの収束値から各データポイントのexemplarを求めるexemplar計算手段と、を有する。上記のように、本発明では、収束値を計算するのに不必要なデータペアを枝刈りして、高速に収束値を計算することにより、オリジナルのAffinityPropagationの手法より高速にクラスタリングできる。また、枝刈りされたデータペアの収束値を、枝刈りされなかったデータペアの収束値から計算することにより、クラスタリング結果はオリジナルのAffinityPropagationと同じである。さらに、本発明においては、ユーザがパラメータ調整を行う必要がない。以下図面と共に、本発明の実施の形態を説明する。図1は、本発明の一実施の形態におけるクラスタリング装置の構成を示す。同図に示すクラスタリング装置は、上限値/下限値計算部10、グラフ計算部20、繰り返し計算部30、収束値計算部40、exemplar計算部50から構成される。なお、各計算部はメモリ図示せずを有し、計算結果を格納するものとする。上限値/下限値計算部10は、データペアの類似度を入力とし、データペアのメッセージの上限値と下限値を出力し、メモリに格納する。グラフ計算部20は、メモリからメッセージの上限値と下限値を取得し、グラフ構造を生成してメモリに出力する。繰り返し計算部30は、メモリからグラフ構造を取得しグラフにおけるエッジの収束値をメモリに出力する。収束値計算部40は、メモリからエッジの収束値を取得して、エッジでないデータペアの収束値をメモリに出力する。exemplar計算部50は、メモリから全てのデータペアの収束値を取得し、各データポイントのexemplarを出力する。まず、本明細書で必要となる背景知識を説明する。以下に、本明細書における主な記号の定義を示す。AffinityPropagation、はデータをクラスタリングし、クラスタを代表するexemplarを求めるクラスタリング手法である。AffinityPropagationの入力はデータペアの類似度sijである。ここで、類似度に対する制約はない。例えば、負のユークリッド距離でもよいし、Jaccard係数などでもよい。与えられた類似度に対してAffinityPropagationはexemplarとそのメンバの間の類似度を最大化するようにクラスタリングを行う。AffinityPropagationでは、responsibilityとavailabilityと呼ばれるメッセージをデータペアで再帰的に計算する。responsibilityrijはデータポイントiからjのメッセージで、データポイントjがデータポイントiのexemplarとしてどれほど適切であるかを表す値である。availabilityaijは、データポイントjからiのメッセージで、データポイントiがデータポイントjのexemplarとして選ぶことがどれほど適切であるかを表す値である。responsibilityとavailabilityははじめ0に初期化され、これらの値は以下の式により再帰的に収束するまで計算され、メモリに格納される。rijρijλrijaijαijλaij1ここでλは繰り返し計算の中でresponsibilityとavailabilityが振動するのを防ぐためのダンピングファクタと呼ばれるものであり、ρijとαijは本明細書にてそれぞれpropagationresponsibilityとpropagatingavailabilityと呼ぶ値である。ρijとαijは以下の式から計算する。データポイントiのexemplarは以下の式から計算する。argmaxrijaijj12...N4ここでNとTをそれぞれデータポイントの数と再帰的計算の繰り返し回数としたときに、オリジナルのAffinityPropagationにおける計算コストはOとなる。この計算コストはデータポイントの数の2乗に比例するため、データポイントの数が多くなると非常に計算時間を要する。本発明の詳細を述べる前に、まず概要について説明する。クラスタリングの速度を上げるために本発明では、グラフ計算部20において疎なグラフ構造GVEを生成し、メモリに格納する。ここでVはデータポイントに対応し、Eはデータペアの一部とする。この構造を用いることにより収束値を高速に計算できる。これはpropagatingresponsibilityとpropagatingavailabilityの計算がグラフのエッジのみに限定されるからである。グラフのエッジを計算するために、上限値下限値計算部10において、収束時におけるresponsibilityとavailabilityの上限値と下限値を計算し、メモリに保持する。メモリに保持された上限値と下限値を使って収束値を計算するのに必要なエッジを特定することができる。さらに、必要なエッジの収束値から枝刈りされたエッジの収束値を計算することができる。そのため収束後に枝刈りされたエッジの収束値を計算できるので、結果オリジナルのAffinityPropagationと同じクラスタリング結果を求めることができる。次に、グラフ構造の作り方について詳細に述べる。本発明では、上限値下限値計算部10において、responsibilityとavailabilityの上限値と下限値を計算するが、これらを求めるために以下の補助定理を示す。<補助定理1>収束後responsibilityとavailabilityの値はそれぞれrijρijとaijαijとなる。証明:前述の式1により明らか。この補助定理を用いることにより、responsibilityとavailabilityの上限値と下限値を計算できる。上限値下限値計算部10は、上限値と下限値を類似度を用いて以下のように計算する。定義1:収束時における上限値と下限値、ととを以下のように計算する。なお、ここで、ととの性質を示すために以下の補助定理を示す。<補助定理2>グラフGにおける任意のデータポイントiとjにおいてとが収束後に成り立つ。証明まず、となることを示す。式1からaijαijとなる。もし、i≠jであれば、となる。これは、だからである。もし、ijであればとなる。これは、だからである。次に、であることを示す。これは、補助定理1と式2とから明らかである。最後に、であることを示す。これは補助定理1と式3と、から明らかである。本発明のグラフ計算部20では、上記の上限値と下限値を用いて疎なグラフ構造を作る。定式的にはグラフのエッジは以下の定義に従って作られる。定義2:Vがデータポイントに対応するグラフGにおいて、以下の条件を満たすときのみノードiとjとの間にエッジを張る。このグラフ構造における性質を示すために以下の二つの補助定理3,4を示す。<補助定理3>任意のノードペアiとjにおいてavailabilityの収束値はの条件を満たすresponsibilityのみを用いて計算できる。証明:補助定理1から収束後aijαijとなる。もし、があるノードペアに成り立てば、収束後にそのノードペアのresponsibilityの値は式3におけるとの値には影響しない。<補助定理4>任意のノードペアiとjにおいてresponsibilityの収束値は、の条件を満たすavailabilityのみを用いて計算できる。証明:補助定理1から収束後rijρijとなる。もし、i≠jであれば、式2より収束後にとなる。であるため、もし、が成り立てば、そのノードペアに対してとなる。そのためそのノードペアのavailabilityの値はresponsibilityの値に影響しない。また、もしijであればresponsibilityの値は式2より類似度のみから計算できる。補助定理3と4から以下の補助定理5が成り立つ。<補助定理5>任意のノードペアiとjにおいてグラフGを用いてメッセージの収束値は正確に計算できる。証明:補助定理3,4から明らか。次に、本発明におけるクラスタリングの手順について述べる。図2は、本発明の一実施の形態におけるアルゴリズムを示し、図3にフローチャートを示す。図2において、まず、定義1を用いて、収束値の上限値と下限値を計算する1~3行目。当該処理は上限値下限値計算部10で行われる。そして定義2を用いて疎なグラフ構造を構築する4~8行目。当該処理はグラフ計算部20で行われる。補助定理5からわかるとおり、全てのノードのペアの収束値はグラフのエッジに対応するペアの収束値から計算できるので、グラフのエッジに対応するペアの収束値を繰り返し計算から求める9~13行目。当該処理は繰返し計算部30で行われ、各繰り返し演算の結果はメモリに格納される。そして、繰り返し計算の後で、メモリから繰り返し演算結果を取得して、グラフをエッジを張っていないペアの収束値を計算しメモリに格納する14~16行目。当該処理は収束計算部40で行われる。そして、メモリから全てのデータペアの収束値を取得し、全てのノードに対してexemplarを計算する17~19行目。当該処理はexemplar計算部50で行われる。なお、図2に示すアルゴリズムをプログラムとして構築し、クラスタリング装置として利用されるコンピュータにインストールして実行させることが可能である。最後に、本発明に対して理論的な解析を行う。なお、個々でMをグラフにおけるエッジの数とする。すなわち、MEである。定理1:収束後において、本発明のクラスタリング結果はオリジナルのAffinityPropagationのクラスタリング結果と同じになる。証明:補助定理5より明らか。定理2:本発明における計算コストはOである。証明:本発明においては、まず全てのデータペアに対して上限値と下限値を計算し、グラフ構造を構築する。上限値と下限値はデータペアの類似度からのみ求められるので、これらにはOの計算コストを要する。そしてグラフの全てのエッジに対してその収束値を繰り返し計算で求める。これにはOの計算コストを要する。そして最後にエッジを張っていないノードペアに対して収束値を計算し、最後にexemplarを計算する。これらにはそれぞれOとOの計算コストを要する。そのため本発明における計算コストはOである。なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更応用が可能である。"