(57)【特許請求の範囲】
【請求項１】
Affinity  Propagationに基づきクラスタリングを行うクラスタリング装置であって、
データペアの類似度を入力として、該データペアのresponsibilityの上限値、および、該データペアのavailabilityの上限値と下限値を記憶手段に出力する上限値/下限値計算手段と、
前記記憶手段から前記メッセージの上限値と下限値を取得し、データペア［ｉ，ｊ］のresponsibilityの上限値がゼロ以上、または、availabilityの上限値と類似度の和が、ｋがｊと異なるデータペア［ｉ，ｋ］におけるavailabilityの下限値と類似度の和の最大値以上との条件を満たす場合に、ノードｉとｊとの間にエッジを張ったグラフ構造を生成して該記憶手段に出力するグラフ計算手段と、
前記記憶手段から前記グラフ構造を取得し、グラフにおけるエッジに対応する前記エッジの収束値を繰り返し演算により求め、該記憶手段に格納する繰り返し計算手段と、
前記記憶手段から前記エッジの収束値を取得し、エッジではないデータペアの収束値を求め、該記憶手段に格納する収束値計算手段と、
前記記憶手段の全てのデータペアの収束値から各データポイントのexemplarを求めるexemplar計算手段と、
を有することを特徴とするクラスタリング装置。
【請求項２】
Affinity  Propagationに基づきクラスタリングを行うクラスタリング方法であって、
上限値/下限値計算手段が、データペアの類似度を入力として、該データペアのresponsibilityの上限値、および、該データペアのavailabilityの上限値と下限値を記憶手段に出力する上限値/下限値計算ステップと、
グラフ計算手段が、前記記憶手段から前記メッセージの上限値と下限値を取得し、データペア［ｉ，ｊ］のresponsibilityの上限値がゼロ以上、または、availabilityの上限値と類似度の和が、ｋがｊと異なるデータペア［ｉ，ｋ］におけるavailabilityの下限値と類似度の和の最大値以上との条件を満たす場合に、ノードｉとｊとの間にエッジを張ったグラフ構造を生成して該記憶手段に出力するグラフ計算ステップと、
繰り返し計算手段が、前記記憶手段から前記グラフ構造を取得し、グラフにおけるエッジに対応する前記エッジの収束値を繰り返し演算により求める繰り返し計算ステップと、
収束値計算手段が、前記記憶手段から前記エッジの収束値を取得し、エッジではないデータペアの収束値を求め、該記憶手段に格納する収束値計算ステップと、
exemplar計算手段が、前記記憶手段の全てのデータペアの収束値から各データポイントのexemplarを求めるexemplar計算ステップと、
を行うことを特徴とするクラスタリング方法。
【請求項３】
コンピュータを、
請求項１記載のクラスタリング装置の各手段として機能させるためのクラスタリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クラスタリング装置及び方法及びプログラムに係り、特に、Affinity Propagationに基づきクラスタリングを行うためのクラスタリング装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
クラスタリングによるデータの解析は汎用的なツールの一つである。そのため今まで多くのクラスタリング手法が提案されている。クラスタリングはデータの集合が与えられたとき、それらをクラスタに分割することが目的である。クラスタリングを行うことにより、データ集合における代表的なものを見つけたりすることができる。
【０００３】
クラスタリング技術として、近年、データポイントの間でメッセージと呼ばれる値を再帰的に収束するまで計算し、収束したメッセージの値からexemplarと呼ばれるクラスタを代表するデータを求める方法がある（例えば、非特許文献１参照）。非特許文献１のAffinity Propagationは、今までのk-means法などのクラスタリング手法と比較して、
（１）クラスタリングの誤差が少ない；
（２）非対称で三角不等式の成り立たない類似度に対応；
（３）クラスタリング結果が初期状態に依存しない；
等のメリットがある。そのためAffinity Propagationは多くのアプリケーションにおいて用いられている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Brendon J. Frey and Delbert Dueck, Clustering by passing messages between data points, Science.2007.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、Affinity Propagationの一つの弱点として計算時間があげられる。すなわち、データポイントの数が多くなった場合、Affinity Propagationによりクラスタリングを行うには非常に計算時間を要する。そのため、Affinity Propagationにおいて再帰的にメッセージの値を計算するには、データポイントの２乗の計算コストを要する。
【０００６】
この問題を解決するために、Jiaらにより近年FSAPが提案された（文献：Yangqing Jiaand Jingdong Wang and Changshui Zhang and Xian-Sheng Hua, Finding image exemplars using fast sparse affinity propagation , ACM Int. conf. Multimedia (ACM MM), 2008）。しかし、FSAPは高速にクラスタリングを行うことができるが、クラスタリングの結果がオリジナルのAffinity Propagationの結果と異なるという弱点がある。高速なクラスタリングと引き換えにクラスタリングの結果を犠牲にするのは、アプリケーションの観点から好ましくない。
【０００７】
本発明は、上記の点に鑑みなされたもので、オリジナルのAffinity Propagationとクラスタリング結果が同じで、かつ、より高速なクラスタリングを行うことが可能なクラスタリング装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記の課題を解決するために、本発明は、Affinity  Propagationに基づきクラスタリングを行うクラスタリング装置であって、
データペアの類似度を入力として、該データペアのresponsibilityの上限値、および、該データペアのavailabilityの上限値と下限値を記憶手段に出力する上限値/下限値計算手段と、
前記記憶手段から前記メッセージの上限値と下限値を取得し、データペア［ｉ，ｊ］のresponsibilityの上限値がゼロ以上、または、availabilityの上限値と類似度の和が、ｋがｊと異なるデータペア［ｉ，ｋ］におけるavailabilityの下限値と類似度の和の最大値以上との条件を満たす場合に、ノードｉとｊとの間にエッジを張ったグラフ構造を生成して該記憶手段に出力するグラフ計算手段と、
前記記憶手段から前記グラフ構造を取得し、グラフにおけるエッジに対応する前記エッジの収束値を繰り返し演算により求め、該記憶手段に格納する繰り返し計算手段と、
前記記憶手段から前記エッジの収束値を取得し、エッジではないデータペアの収束値を求め、該記憶手段に格納する収束値計算手段と、
前記記憶手段の全てのデータペアの収束値から各データポイントのexemplarを求めるexemplar計算手段と、を有する。
【発明の効果】
【０００９】
上記のように、本発明では、収束値を計算するのに不必要なデータペアを枝刈りして、高速に収束値を計算することにより、オリジナルのAffinity Propagationの手法より高速にクラスタリングできる。
【００１０】
また、枝刈りされたデータペアの収束値を、枝刈りされなかったデータペアの収束値から計算することにより、クラスタリング結果はオリジナルのAffinity Propagationと同じである。
【００１１】
さらに、本発明においては、ユーザがパラメータ調整を行う必要がない。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施の形態におけるクラスタリング装置の構成図である。
【図２】本発明の一実施の形態におけるアルゴリズムである。
【図３】本発明の一実施の形態におけるクラスタリングのフローチャートである。
【発明を実施するための形態】
【００１３】
以下図面と共に、本発明の実施の形態を説明する。
【００１４】
図１は、本発明の一実施の形態におけるクラスタリング装置の構成を示す。
【００１５】
同図に示すクラスタリング装置は、上限値／下限値計算部１０、グラフ計算部２０、繰り返し計算部３０、収束値計算部４０、exemplar計算部５０から構成される。なお、各計算部はメモリ（図示せず）を有し、計算結果を格納するものとする。
【００１６】
上限値／下限値計算部１０は、データペアの類似度を入力とし、データペアのメッセージの上限値と下限値を出力し、メモリに格納する。
【００１７】
グラフ計算部２０は、メモリからメッセージの上限値と下限値を取得し、グラフ構造を生成してメモリに出力する。
【００１８】
繰り返し計算部３０は、メモリからグラフ構造を取得しグラフにおけるエッジの収束値をメモリに出力する。
【００１９】
収束値計算部４０は、メモリからエッジの収束値を取得して、エッジでないデータペアの収束値をメモリに出力する。
【００２０】
exemplar計算部５０は、メモリから全てのデータペアの収束値を取得し、各データポイントのexemplarを出力する。
【００２１】
まず、本明細書で必要となる背景知識を説明する。
【００２２】
以下に、本明細書における主な記号の定義を示す。
【００２３】
【表１】
0005547128.tif 000002
Affinity Propagation、はデータをクラスタリングし、クラスタを代表するexemplarを求めるクラスタリング手法である。Affinity Propagationの入力はデータペアの類似度
s[i, j]  (i, j = 1,2,…,N)
である。ここで、類似度に対する制約はない。例えば、負のユークリッド距離でもよいし、Jaccard係数などでもよい。
【００２４】
与えられた類似度に対してAffinity Propagationはexemplarとそのメンバの間の類似度を最大化するようにクラスタリングを行う。Affinity Propagationでは、responsibilityとavailabilityと呼ばれるメッセージをデータペアで再帰的に計算する。responsibility r[i, j]はデータポイントiからjのメッセージで、データポイントjがデータポイントiのexemplarとしてどれほど適切であるかを表す値である。availability a[i, j]は、データポイントjからiのメッセージで、データポイントiがデータポイントjのexemplarとして選ぶことがどれほど適切であるかを表す値である。responsibilityとavailabilityははじめ０に初期化され、これらの値は以下の式により再帰的に収束するまで計算され、メモリに格納される。
【００２５】
r[i, j] = (1−λ)ρ[i, j]+λr[i, j]
a[i, j] = (1−λ)α[i,j] +λa[i, j]                          （１）
ここでλは繰り返し計算の中でresponsibilityとavailabilityが振動するのを防ぐためのダンピングファクタと呼ばれるものであり、ρ[i, j]とα[i, j]は本明細書にてそれぞれpropagation responsibilityとpropagating availabilityと呼ぶ値である。ρ[i, j]とα[i, j]は以下の式から計算する。
【００２６】
【数１】
0005547128.tif 000003
データポイントiのexemplarは以下の式から計算する。
【００２７】
arg max{r[i,j]+a[i,j] : j= 1,2,…,N}                        （４）
ここでNとTをそれぞれデータポイントの数と再帰的計算の繰り返し回数としたときに、オリジナルのAffinity Propagationにおける計算コストはO(N2T)となる。この計算コストはデータポイントの数の２乗に比例するため、データポイントの数が多くなると非常に計算時間を要する。
【００２８】
本発明の詳細を述べる前に、まず概要について説明する。
【００２９】
クラスタリングの速度を上げるために本発明では、グラフ計算部２０において疎なグラフ構造G=[V,E]を生成し、メモリに格納する。ここでVはデータポイントに対応し、Eはデータペアの一部とする。この構造を用いることにより収束値を高速に計算できる。これはpropagating responsibilityとpropagating availabilityの計算がグラフのエッジのみに限定されるからである。グラフのエッジを計算するために、上限値/下限値計算部１０において、収束時におけるresponsibilityとavailabilityの上限値と下限値を計算し、メモリに保持する。メモリに保持された上限値と下限値を使って収束値を計算するのに必要なエッジを特定することができる。さらに、必要なエッジの収束値から枝刈りされたエッジの収束値を計算することができる。そのため収束後に枝刈りされたエッジの収束値を計算できるので、結果オリジナルのAffinity Propagationと同じクラスタリング結果を求めることができる。
【００３０】
次に、グラフ構造の作り方について詳細に述べる。
【００３１】
本発明では、上限値/下限値計算部１０において、responsibilityとavailabilityの上限値と下限値を計算するが、これらを求めるために以下の補助定理を示す。
【００３２】
＜補助定理１＞
収束後responsibilityとavailabilityの値はそれぞれr[i, j]=ρ[i, j]とa[i, j]=α[i, j]となる。
【００３３】
・証明：
前述の式（１）により明らか。
【００３４】
この補助定理を用いることにより、responsibilityとavailabilityの上限値と下限値を計算できる。上限値/下限値計算部１０は、上限値と下限値を類似度を用いて以下のように計算する。
【００３５】
・定義１：
収束時における上限値と下限値、
【００３６】
【数２】
0005547128.tif 000004
と
【００３７】
【数３】
0005547128.tif 000005
と
【００３８】
【数４】
0005547128.tif 000006
を以下のように計算する。
【００３９】
【数５】
0005547128.tif 000007
なお、ここで、
【００４０】
【数６】
0005547128.tif 000008
と
【００４１】
【数７】
0005547128.tif 000009
と
【００４２】
【数８】
0005547128.tif 000010
の性質を示すために以下の補助定理を示す。
【００４３】
＜補助定理２＞
グラフGにおける任意のデータポイントiとjにおいて
【００４４】
【数９】
0005547128.tif 000011
と
【００４５】
【数１０】
0005547128.tif 000012
が収束後に成り立つ。
【００４６】
・証明
まず、
【００４７】
【数１１】
0005547128.tif 000013
となることを示す。式（１）からa[i,j]=α[i,j]となる。もし、i ≠ jであれば、
【００４８】
【数１２】
0005547128.tif 000014
となる。これは、
【００４９】
【数１３】
0005547128.tif 000015
だからである。もし、i = jであれば
【００５０】
【数１４】
0005547128.tif 000016
となる。これは、
【００５１】
【数１５】
0005547128.tif 000017
だからである。
【００５２】
次に、
【００５３】
【数１６】
0005547128.tif 000018
であることを示す。これは、補助定理１と式（２）と
【００５４】
【数１７】
0005547128.tif 000019
から明らかである。
【００５５】
最後に、
【００５６】
【数１８】
0005547128.tif 000020
であることを示す。これは補助定理１と式（３）と、
【００５７】
【数１９】
0005547128.tif 000021
から明らかである。
【００５８】
本発明のグラフ計算部２０では、上記の上限値と下限値を用いて疎なグラフ構造を作る。定式的にはグラフのエッジは以下の定義に従って作られる。
【００５９】
・定義２：
Vがデータポイントに対応するグラフGにおいて、以下の条件を満たすときのみノードiとjとの間にエッジを張る。
【００６０】
【数２０】
0005547128.tif 000022
このグラフ構造における性質を示すために以下の二つの補助定理３，４を示す。
【００６１】
＜補助定理３＞
任意のノードペアiとjにおいてavailabilityの収束値は
【００６２】
【数２１】
0005547128.tif 000023
の条件を満たすresponsibilityのみを用いて計算できる。
【００６３】
・証明：
補助定理１から収束後a[i,j]=α[i,j]となる。もし、
【００６４】
【数２２】
0005547128.tif 000024
があるノードペアに成り立てば、収束後にそのノードペアのresponsibilityの値は式（３）における
【００６５】
【数２３】
0005547128.tif 000025
と
【００６６】
【数２４】
0005547128.tif 000026
の値には影響しない。
【００６７】
＜補助定理４＞
任意のノードペアiとjにおいてresponsibilityの収束値は、
【００６８】
【数２５】
0005547128.tif 000027
の条件を満たすavailabilityのみを用いて計算できる。
【００６９】
・証明：
補助定理１から収束後r[i,j]=ρ[i,j]となる。もし、i≠jであれば、式（２）より収束後に
【００７０】
【数２６】
0005547128.tif 000028
となる。
【００７１】
【数２７】
0005547128.tif 000029
であるため、もし、
【００７２】
【数２８】
0005547128.tif 000030
が成り立てば、そのノードペアに対して
【００７３】
【数２９】
0005547128.tif 000031
となる。そのためそのノードペアのavailabilityの値はresponsibilityの値に影響しない。また、もしi = jであればresponsibilityの値は式（２）より類似度のみから計算できる。
【００７４】
補助定理３と４から以下の補助定理５が成り立つ。
【００７５】
＜補助定理５＞
任意のノードペアiとjにおいてグラフGを用いてメッセージの収束値は正確に計算できる。
【００７６】
・証明：
補助定理３，４から明らか。
【００７７】
次に、本発明におけるクラスタリングの手順について述べる。
【００７８】
図２は、本発明の一実施の形態におけるアルゴリズムを示し、図３にフローチャートを示す。
【００７９】
図２において、まず、定義１を用いて、収束値の上限値と下限値を計算する（１〜３行目）。当該処理は上限値/下限値計算部１０で行われる。そして定義２を用いて疎なグラフ構造を構築する（４〜８行目）。当該処理はグラフ計算部２０で行われる。補助定理５からわかるとおり、全てのノードのペアの収束値はグラフのエッジに対応するペアの収束値から計算できるので、グラフのエッジに対応するペアの収束値を繰り返し計算から求める（９〜１３行目）。当該処理は繰返し計算部３０で行われ、各繰り返し演算の結果はメモリに格納される。そして、繰り返し計算の後で、メモリから繰り返し演算結果を取得して、グラフをエッジを張っていないペアの収束値を計算しメモリに格納する（１４〜１６行目）。当該処理は収束計算部４０で行われる。そして、メモリから全てのデータペアの収束値を取得し、全てのノードに対してexemplarを計算する（１７〜１９行目）。当該処理はexemplar計算部５０で行われる。
【００８０】
なお、図２に示すアルゴリズムをプログラムとして構築し、クラスタリング装置として利用されるコンピュータにインストールして実行させることが可能である。
【００８１】
最後に、本発明に対して理論的な解析を行う。
【００８２】
なお、個々でMをグラフにおけるエッジの数とする。すなわち、M=|E|である。
【００８３】
・定理１：収束後において、本発明のクラスタリング結果はオリジナルのAffinity Propagationのクラスタリング結果と同じになる。
【００８４】
証明：補助定理５より明らか。
【００８５】
・定理２：本発明における計算コストはO(N2+MT)である。
【００８６】
証明：本発明においては、まず全てのデータペアに対して上限値と下限値を計算し、グラフ構造を構築する。上限値と下限値はデータペアの類似度からのみ求められるので、これらにはO(N2)の計算コストを要する。そしてグラフの全てのエッジに対してその収束値を繰り返し計算で求める。これにはO(MT)の計算コストを要する。そして最後にエッジを張っていないノードペアに対して収束値を計算し、最後にexemplarを計算する。これらにはそれぞれO(N2-M)とO(N2)の計算コストを要する。そのため本発明における計算コストはO(N2+MT)である。
【００８７】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００８８】
１０  上限値/下限値計算部
２０  グラフ計算部
３０  繰り返し計算部
４０  収束値計算部
５０  exemplar計算部
【図１】
0005547128.tif 000032
【図２】
0005547128.tif 000033
【図３】
0005547128.tif 000034