DEIM Forum 2019 A8-3

メッセージ集約に基づく Aﬃnity Propagation の高速化
松下 朋弘†

塩川 浩昭††

北川博之††† 筑波大学システム情報工学研究科 〒 305–8577 茨城県つくば市天王台 1 丁目 1–1†† 筑波大学計算科学研究センター 〒 305–8577 茨城県つくば市天王台 1 丁目 1–1
E-mail: †matsushita@kde.cs.tsukuba.ac.jp, ††{shiokawa,kitagawa}@cs.tsukuba.ac.jp
あらましWeb データにおける情報抽出・要約にはクラスタリングが有効であることが知られている．Aﬃnity Propa-

gation は，各データポイント間でメッセージと呼ばれる実数値を収束するまで再帰的に計算することで、クラスタを代表するデータポイントを決定し，クラスタを構築するアルゴリズムである．しかし従来の手法の計算量はデータ数の 2乗に比例するため，データ数が増えると実行時間が急激に増えるという欠点がある．本稿では，大規模データを対象とした Aﬃntiy Propagation の高速化手法を提案する．提案手法は複雑な反復計算が不要なデータポイントペアを枝刈りし，それらについてはより簡潔な式でメッセージを求めることで高速化を図る．評価実験により，提案手法が従来の手法と同様のクラスタリング結果を出力しつつ、これまでの既存手法と比べて高速に処理できることを示す．
キーワード クラスタリング, Aﬃnity Propagation, 高速化
で再帰的に送り合うことで

1 はじめに
近年では Web サービスの進歩に伴い，生成されるデータ量が急激に増えている．それに伴い，複雑で大規模なデータを効果的に処理し，サービス内の複雑な現象を把握する必要性が高まっている．クラスタリングは与えられたデータをクラスタと呼ばれるいくつかの部分集合に分割することでデータセット内の隠れたパターンを見つけるデータ分析手法であり，データ分析の際に最もよく用いられる手法の一つである．
これまで多くのクラスタリングアルゴリズムが提案されてきた中で，2007 年に Frey らによって Aﬃnity Propagation [1] と呼ばれるクラスタリングアルゴリズムが提案された．この手法は，

exemplar と呼ばれるクラスタの核となるデータポイントをすべてのデータポイントの中から自動的に検出することでクラスタを構築する手法である．Aﬃnity Propagation では，データが与えられるとクラスタ数を自動で決定するため，k-means 法 [2] や

k-medoid 法 [14] などのようなこれまで提案されてきた手法とは異なり，ユーザが予め出力するクラスタ数を指定する必要がな
い．この他にも，他のクラスタリングアルゴリズムと比較してクラスタリング精度が良いこと [1, 6] や初期値依存がないことなどから，コミュニティ検索 [7, 8] やテキストデータ内の主要語句の抽出 [9, 10] など多くの場面で用いられ，近年幅広い分野から着目されているアルゴリズムである．

X = {x1 , x2 , · · · , xN } を与えられたデータポイント，s(xi , xj )を デ ー タ ポ イ ン ト xi , xj 間 の 類 似 度 ，e(xi ) を デ ー タ ポ イ
ン ト xi の exemplar と し た 時 ，Aﬃnity Propagation で は ，∑N
i=1 s(xi , e(xi )) を 最 大 化 す る よ う に exemplar を 決 定 す
る ．し か し な が ら ，exemplar の 数 は 未 定 で あ る こ と か ら ，∑N
i=1 s(xi , e(xi )) を最大化する exemplar を選択することは NP-

hard となる．この問題に対して Aﬃnity Propagation では，各
データポイント間でメッセージと呼ばれる実数値を収束するま∑N

i=1 s(xi , e(xi )) を準最大化する

exemplar を自動的に決定する．ところが，データ数を N ，反復
回数を T とした時，この計算にかかる計算量は O(N 3 T ) となり，データ数が多くなる場合において膨大な処理時間を必要とする．
この課題を解決するために Fujiwara らは，Graph-AP [4] と呼ばれる Aﬃnity propagation の高速化手法を提案した．この手法は，反復計算を行う前に収束後のメッセージの上限値と下限値を推定する事でメッセージの伝搬が不要なエッジを枝刈りすることで反復計算を行うエッジの数を削減し，高速化を図っ
た．枝刈りしたエッジのメッセージは反復計算後に再帰的な計算を行うことなく求めることができる．ゆえに，Graph-AP は従来の Aﬃnity Propagation [1] と同じクラスタリング結果を出力することができる．文献 [4] では，Graph-AP が従来の Aﬃnity

Propagation [1] と同じクラスタリング結果を出力しつつ，既存手法 [1, 3] よりも高速に処理できることを実験的に示した．しかしこの手法は，反復計算中にメッセージが収束したとしても全てのメッセージが収束するまで計算を続けなければならないた
め無駄な計算が行われている．
この問題を解決したアルゴリズムが F-AP [5] である．この手法は，反復計算を行う前に収束前のメッセージの上限値と下限値を推定する事でメッセージの伝搬が不要なエッジを枝刈りす
るだけでなく，反復計算中に収束したと判定されたメッセージに対しては以降の反復計算の対象から取り除く事でさらなる高速化を実現した．F-AP についても Graph-AP [4] と同様に従来のAﬃnity Propagation [1] と同じクラスタリング結果を出力できることが理論的に証明されている．しかし，枝刈りされなかった
データポイントペアのメッセージの中にも複雑な計算が不要なメッセージが含まれており，依然として無駄な計算が行われている．
そこで本研究では，大規模なデータを対象とした Aﬃnity

Propagation の高速化手法を提案する．

提案手法の基本的なアイデアは，各 iteration 毎に複雑な計算と表記されたとき，データポイント xi から xj ∈ X に対して送を行わずに計算できるメッセージを特定することでさらなる高速化を図る．これらの枝刈りしたメッセージは各 iteration にお信する実数値であり，xi が自身の exemplar として xj を選択し∑た場合にどれだけ N
i=1 s(xi , e(xi )) の最大化に貢献するかといける再帰計算後にまとめて計算することができる．本研究ではう情報を表している．これに対して，availability は a(xi , xj ) と実データセットと人工データセットを用いて提案手法の有効性表記されたとき，データポイント xi が X に含まれる全てのデーの検証を行い，state-of-the-art とされる手法 [5] よりも高速にタポイントから受信する実数値であり，xj が xi の exemplar と∑して選択された場合にどれだけ N
i=1 s(xi , e(xi )) の最大化に貢処理できることを示した．本研究の貢献を以下に示す．

•

高速性：提案手法は従来の Aﬃnity Propagation [1] や既存手法 [4, 5] と比較して高速に処理できることを示す（4. 2 章）．

•

スケーラビリティ：提案手法はデータ数の観点から，従来の Aﬃnity Propagation [1] と比較して優れたスケーラビリティ
を示す（4. 3 章）．

•

献するかという情報を表している．responsibility と availability
はそれぞれ以下の式で定義されている．
定義 21 (responsibility と availability) responsibility r(xi , xj )と availability a(xi , xj ) は以下のように定義される．

正確性：提案手法は高速化のためにメッセージ集約に基づ

r(xi , xj ) = (1 − λ)ρ(xi , xj ) + λr(xi , xj )く計算の簡略化を行うが，従来の Aﬃnity Propagaton [1] と同a(xi , xj ) = (1 − λ)α(xi , xj ) + λa(xi , xj )一のクラスタリング結果を出力する事ができる．本稿では定理

31 において提案手法の正確性を理論的に証明するとともに，実ここで，λ はダンピングファクタであり，0 から 1 までの値を

データを用いた評価実験を通して提案手法の正確性を実験的にとる．上記の式の中で，ρ(xi , xj ) は propagating responsibility ，

確認した（4. 4 章）．

α(xi , xj ) は propagating availability と呼ばれ，以下の式により

本研究では実データセットと人工データセットを用いて提案手計算する．

法の有効性の検証を行い，従来の Aﬃnity Propagation [1] と比較して 42.53 倍，state-of-the-art とされる手法 [5] と比較して5.59 倍の高速化を実現した．また，提案手法は従来の Aﬃnity
Propagation [1] と同じクラスタリング結果を出力できることを実験的にも確認した．

ρ(xi , xj ) =s(xi , xj ) − max {a(xi , xk ) + s(xi , xk )}(xi =| xj )

s(xi , xj ) − max {s(xi , xk )}(xi = xj )

xk =x
| j

xk =x
| j

本稿の構成は以下の通りである．まず 2 節において Aﬃnity

Propagation の概要を説明する．続いて 3 節で提案手法につい
最後に 6 節で結論を述べる．

α(xi , xj ) =∑
max{0, r(xk , xj )}} (xi =| xj )
min{0, r(xj , xj )+

2 事前知識：Aﬃnity Propagation∑
max{0, r(xk , xj )}て述べ，4 節で評価実験を示す．そして 5 節で関連研究を述べ，

xk =x| i ,xj

本節では Frey らによって提案された Aﬃnity Propagation [1]について説明する．

Aﬃnity Propagation は，与えられたデータから各データポイ
ント間の類似性を表す類似度 S = {s(xi , xj )|xi , xj ∈ X} を計算する．xi = xj の場合，s(xi , xi ) は preference と呼ばれ，一般的(xi = xj )

xk =x
| i

ダンピングファクタ λ は実際には λ = 0.5 と設定するのが一般的であると言われている [1, 4, 5]．上記の式から分かるように，

responsibility r(xi , xj ) と availability a(xi , xj ) は互いに影響を与え合っている．つまり，r(xi , xj ) は，a(xi , xj ) を計算するために用いられ，逆も同様である．

に preference は類似度の中央値もしくは最小値を設定する [1]．

反復計算を行う前に responsibility と availability の初期値

Aﬃnity Propagation では負のユークリッド距離のような距離のr0 (xi , xj )，a0 (xi , xj ) はそれぞれ以下のように設定し、全ての公理が成り立つものから jaccard 係数のような距離の公理が成り

データポイントペアに対して定義 21 が収束するまで再帰的に立たないものまで任意の類似度に対応することができる．また，

responsibility と availability を計算する．

Aﬃnity Propagation では与えられた X，S からアルゴリズムが適切なクラスタ数を自動的に決定するため，ユーザは k-means

定義 22 (各メッセージの初期値)

法 [2] 等のようにクラスタ数を予め指定する必要がない．
∑
1 節で述べたように， N
i=1 s(xi , e(xi )) を最大化することはと availability の初期値 a0 (xi , xj ) は以下のように定義される．

NP-hard である．ゆえに Aﬃnity Propagation は，各データポイ
ント間でメッセージを再帰的に伝搬することで近似解を出力する．

responsibility の初期値 r0 (xi , xj )r0 (xi , xj ) = s(xi , xj ) − max {s(xi , xk )}
xk =x
| j

a0 (xi , xj ) = 0

具体的には，各データポイント xi から X に含まれる全てのデー
すべてのデータポイント間における responsibility と avail-

タポイントに対して responsibility というメッセージを送信し，∑availability というメッセージを受信することで N
i=1 s(xi , e(xi ))ability が収束した後，データポイント xi の exemplar は以下のを準最大化する exemplar を決定する．responsibility は r(xi , xj )式で決定する．

Algorithm 1 Aﬃnity Propagation [1]似度の和を最大にするデータポイントを探索する必要がある．

Input: S
Output: exemplars for each data object in X
1: repeat2:
for each (xi , xj ) ∈ X2 do
3:compute r(xi , xj ) by Definition 21;

また，availability についても自身に伝搬されてくる正の値の4:
for each (xi , xj ) ∈ X2 do
5:compute a(xi , xj ) by Definition 21;
6: until all r(xi , xj ) and a(xi , xj ) are not updated
7: for each xi ∈ X do
8:get an exemplar e(xi ) by Definition 23;までに計算された responsibility と availability を用いて t 回目

responsibility の和を計算する必要がある．この計算を避けるた
めに提案手法では，T を反復回数として，t − 1 回目（1 < t < T ）の反復計算において定義 21 を用いた計算をする必要がないデー
タポイントペアを決定する．

•
定義 23 (exemplar の決定)

データポイント xi の exemplar

は以下の式によって決定する．

e(xi ) = arg max{r(xi , xj ) + a(xi , xj )}xj

メッセージの集約計算: 定義 21 を用いた計算が必要な

データポイントペアについてのメッセージの計算後，上記で定義したデータポイントペアのメッセージの集約計算を行う．この計算は，上記で定義したデータポイントペアの集合の中で 1 つのペアについてメッセージを計算し，その値を用いたより簡単な式によって他のデータポイントペアのメッセージを計算する．

exemplar が決定した後，exemplar として選択されなかった

3. 2，3. 3 節では，この計算方法によって各 iteration における従

データポイントはすべての exemplar との間の類似度を比較し，

来の Aﬃnity Propagation [1] と同様のメッセージ値が計算でき類似度が最大となる exemplar と同じクラスタに割り当てられる．

ることを理論的に証明する．また，そこで求めた responsibility

Aﬃnity Propagation のアルゴリズムを Algorithm1 に示す．

と availability をもとに，次の反復計算において定義 21 を用い

Aﬃnity Propagation ではデータポイントセット X と各データポた計算をする必要がないデータポイントペアを定義する．

イント間の類似度 S を入力値とし，exemplar を出力する．Aﬃn-

提案手法では，メッセージ集約に基づく反復計算の簡略化を

ity Propagation は類似度 S を元に全てのデータポイント間で行なったとしても，従来の Aﬃnity Propagation [1] と同様のク

responsibility と availability を定義 21 に基づいて計算する．こラスタリング結果を出力することができる．3. 3 節で提案手法がの再帰計算は，全てのメッセージが収束するもしくはユーザが指正確性を理論的に保証していることを示し．4. 4 節で提案手法の定する反復回数に達するまで繰り返し行う（1 行目–6 行目）．そ

正確性を実験的に示す．

の後，定義 23 のように，計算した responsibility と availabilityを用いて exemplar を決定し，クラスタを形成する（7–8 行目）．

3. 2 メッセージ集約が可能なデータポイントペアの特定

Aﬃnity Propagation では，全てデータポイント間でメッセー

提案手法では，T を反復回数として，t − 1 回目（1 < t < T ）ジの値を反復計算する必要がある．また，データ数を N としたで計算された responsibility と availability を用いて，t 回目の時，定義 21 より，各データポイント間でメッセージを計算する

反復計算において定義 21 を用いた計算をする必要がないデータ

際に O(N ) の計算量を必要とする．ゆえに，反復回数を T としポイントペアを決定する．本節では，提案手法における再帰計算

た時，Algorithm1 にかかる計算量は O(N 3 T ) である．つまり，が不要なデータポイントペアの検出方法について説明する．

実行時間はデータ数の 3 乗に比例する．ゆえに，大規模なデー

はじめに，responsibility の枝刈りについて説明する．まず，t

タセットについてクラスタリングを行う際には膨大な処理時間

回目の反復計算における responsibility の計算の際に定義 21 を用を必要とする．

いた計算が不要なデータポイントペアの集合 P R(xi , t) を定義す

3 提案手法

の計算を集約する．

3. 1 手法の概要

定義 31 (集約可能な responsibility の特定) 以下の条件を満る．提案手法では，これらのデータポイントペアの responsibility

本節では，提案手法について説明する．
提案手法の基本的なアイデアは，反復計算を行うデータポイン
トの数を削減することである．1 節で述べたように既存手法 [4,5]たすデータポイントペア (xi , xj ) は t 回目のデータポイントペアの集合 P R(xi , t) に含まれる．

P R(xi , t) = {(xi , xj )|xi =| xj and xj =| xk ∈ sum(a, s)}では，メッセージ伝搬が明らかに不要なデータポイントペアの枝刈りを反復計算が行われる前に実行することで高速化を実現

ここで，am (xi , xj ) は m 回目の反復計算におけるにおける (xi , xj )している．しかし，そこで枝刈りが行われなかったデータポインの availability の値であるとすると，トペアの中でも，定義 21 を用いた複雑な計算が不要なペアが存在することが予備実験により明らかになった．そこで本手法では，それらの計算を集約することでさらに反復計算を行うデー
タポイントペアの数を削減し，高速化を図る．具体的には，以下

sum(a, s) ={xl |xl = max{am (xi , xl ) + s(xi , xl )}} (m = 0, 1, · · · , t − 1)
xl

である．

のアプローチにより高速化を図る．

•

メッセージ集約が可能なデータポイントペアの特定: 定

義 21 より，responsibility を計算するためには availability と類

データポイントペアの集合 P R(xi , t) は以下の特性を持つ．

補題 31 P R(xi , t) に含まれるデータポイントペアの responsi-

らかである．また，ρt (xi , xj ) は，s(xi , xj ) − max {a(xi , xk ) +bility は集約計算が可能である．

s(xi , xk )} で計算することができることより，上記と同様に

証明

xk =x
| j

ここでは，P R(xi , t) に含まれるデータポイントペアのrt−1 (xi , xa ) − rt−1 (xi , xb ) = ρt (xi , xa ) − ρt (xi , xb )responsibility は類似度を用いて計算を集約できることを証明す= s(xi , xa ) − s(xi , xb )る．本証明では，P R(xi , t) に含まれる 2 組のデータポイントペ
ア (xi , xa )，(xi , xb ) について考える．

となり，

はじめに，

rt (xi , xa ) − rt (xi , xb ) = s(xi , xa ) − s(xi , xb )rt−1 (xi , xa ) − rt−1 (xi , xb ) = β
ρt−1 (xi , xa ) − ρt−1 (xi , xb ) = βが成り立つ．
以上より，t >= 1 で (xi , xa ), (xi , xb ) ∈ P R(xi , t) であるデーと仮定する．ここで，rt−1 (xi , xj ) は t − 1 回目における re-

タポイントペアの responsibility は availability と類似度の和を

sponsibility，ρt−1 (xi , xj ) は t − 1 回目における propagating

最大にするデータポイントを探索することなく計算できる． □responsibility を表す．すると，t 回目における responsibilityr(xi , xa ) と r(xi , xb ) の差は，また，P R(xi , t) の初期セット P R(xi , 1) は以下のように定義
される．

rt (xi , xa ) − rt (xi , xb ) = β

定義 32 (P R(xi , t) の初期セット) 以下の条件を満たすデーとなる．つまり，t − 1 回目における responsibility の差と t 回

タポイントペア (xi , xj ) は 1 回目のデータポイントペアの集合目における propagating responsibility の差が等しい場合は t 回

P R(xi , 1) に含まれる．

目における responsibility も同じ差の値になる．

P R(xi , 1) = {(xi , xj )|xi =| xj and xj =| xk }

はじめに t = 1 の場合について考える．t = 1 の時，responsi-

bility を計算する式は定義 21 より，

ここで xk は，

r1 (xi , xj ) = (1 − λ)ρ1 (xi , xj ) + λr0 (xi , xj )である．ここで，ρ1 (xi , xj ) は 1 回目の反復計算において計算さ

xk = max{s(xi , xk )}
xk

である．

れる propagating responsibility の値であり，r0 (xi , xj ) は xi から xj へ伝搬される responsibility の初期値である．r0 (xi , xj ) は

データポイントペアの集合 P R(xi , 1) は以下のような特性を

s(xi , xj ) − max {s(xi , xk )} で求められることから，xa , xb =
| xk

持つ．

の時，

補題 32 P R(xi , 1) に含まれるデータポイントペアの responsi-

xk =x
| j

r0 (xi , xa ) − r0 (xi , xb ) = s(xi , xa ) − s(xi , xb )bility は 1 回目の反復計算において集約計算により求めることができる．

となることがわかる．
また，ρ1 (xi , xj ) は定義 21 より，s(xi , xj ) − max {a(xi , xk ) +証明

補題 31 より明らかである．

□

xk =x
| j

s(xi , xk )} で計算することができる．ゆえに，xa , xb =| xk の時，
ρ1 (xi , xa ) − ρ1 (xi , xb ) = s(xi , xa ) − s(xi , xb )次に，提案手法における availability の枝刈りについて説明する．まず，t 回目の反復計算における availability の計算の際に定義 21 を用いた計算が不要なデータポイントペアの集合

P A(xj , t) を定義する．提案手法では，これらのデータポイントで計算することができる．

ペアの availability の計算を集約する．

以上より，t = 1 の時，

r0 (xi , xa ) − r0 (xi , xb ) = ρ1 (xi , xa ) − ρ1 (xi , xb )= s(xi , xa ) − s(xi , xb )定義 33 (集約可能な availability の特定)

以下の条件を満たすデータポイントペア (xi , xj ) はデータポイントペアの集合

P A(xj , t) に含まれる．

が成り立つことより，

P A(xj , t) =r1 (xi , xa ) − r1 (xi , xb ) = s(xi , xa ) − s(xi , xb )
つまり，r1 (xi , xa ) がわかっている場合，r1 (xi , xb ) は r1 (xi , xa )と類似度を用いて簡単に計算することができる．
次に t >= 2 の場合について考える．t >= 2 の時，rt−1 (xi , xa ) −rt−1 (xi , xb ) = s(xi , xa ) − s(xi , xb ) が成り立っていることは明{(xi , xj )|xi =| xj and rm (xi , xj ) <= 0} (m = 0, 1, · · · , t − 1)
ここで，rm (xi , xj ) は m 回目の反復計算におけるにおける (xi , xj )の responsibility の値である．
データポイントペアの集合 P A(xj , t) は以下の特性を持つ．

補題 33 P A(xj , t) に含まれるデータポイントペアの availabil-

定義 35 (responsibility の集約計算) t 回目のデータポイン

ity は集約計算が可能である．

トペア集合 P R(xi , t) に含まれるデータポイントペア (xi , xa ) の証明

ここでは，P A(xj , t) に含まれるデータポイントペアの

responsibility rt (xi , xa ) は以下の式で計算できる．
rt (xi , xa ) = rt (xi , xb ) + s(xi , xa ) − s(xi , xb )availability は定義 21 による計算を必要としないことを証明す
る．定義 21 より，xi =| xj における propagationg availabilityα(xi , xj ) は以下のように求められる．
∑
α(xi , xj ) = min{0, r(xj , xj ) +ここで，rt (xi , xa )，rt (xi , xb ) はそれぞれ t 回目の反復計算において (xi , xa ), (xi , xb ) ∈ P R(xi , t) であるデータポイントペア(xi , xa ), (xi , xb ) の responsibility の値である．

max{0, r(xk , xj )}}xk =x| i ,xj

t−1 回目において，2 つのデータポイントペア (xa , xj ), (xb , xj ) ∈P A(xj , t) の responsibility は そ れ ぞ れ rt−1 (xa , xj ) <= 0，
rt−1 (xb , xj ) <= 0 で あ る た め ，上 記 の 式 よ り，r(xa , xj ) とr(xb , xj ) はいずれも propagationg availability の値に影響を

定義 35 は以下の特性を持つ．
補題 35 定義 35 によって従来の Aﬃnity Propagation と同様の responsibility の値を計算できる．
証明□

補題 31 より明らかである．

与えないことは明らかである．ゆえに，t 回目の反復計算における propagating availability αt (xa , xj ) と αt (xb , xj ) は以下のよ
うな関係となる．

次に，提案手法における枝刈りされたデータポイントペアのavailability の計算について説明する．データポイントペアの集
合 P A(xj , t) に含まれるデータポイントペアの availability は以αt (xa , xj ) = αt (xb , xj )下の式によって計算できる．

ま た ，t − 1 回 目 に お け る (xa , xj ), (xb , xj ) の availability

定義 36 (availability の集約計算)

at−1 (xa , xj )，at−1 (xb , xj ) が at−1 (xa , xj ) = at−1 (xb , xj ) の時，ペア集合 P A(xj , t) に含まれるデータポイントペア (xa , xi ) の

t 回目の反復計算における availability at (xa , xj ) と at (xb , xj ) は

availability at (xa , xi ) は以下の式で計算できる．

at (xa , xj ) = at (xb , xj )at (xa , xi ) = at (xb , xi )が成り立つことは明らかである．

ここで，at (xi , xa )，at (xi , xb ) はそれぞれ t 回目の反復計算に

以上より，P A(xj , t) に含まれるデータポイントペアの avail-ability は，1 つのペアについてメッセージを計算し，他のデータ
ポイントペアについては自身に伝搬されてくる正の値の respon-

sibility の和を計算することなく求めることができる．

□

また，P A(xj , t) の初期セット P A(xj , 1) は以下のように定義される．
定義 34 (P A(xj , t) の初期セット)

t 回目のデータポイント

以下の条件を満たすデー

タポイントペア (xi , xj ) は 1 回目のデータポイントペアの集合

P A(xj , 1) に含まれる．

おいて (xi , xa ), (xi , xb ) ∈ P A(xj , t) であるデータポイントペア(xi , xa ), (xi , xb ) の availability の値である．
定義 36 は以下の特性を持つ．
補題 36 定義 36 によって従来の Aﬃnity Propagation と同様の availability の値を計算できる．
証明

補題 33 より明らかである．

□

最後に，提案手法の正確性について述べる．補題 31，33，35，

36 より，提案手法は以下の定理を持つ．

P R(xi , 1) = {(xi , xj )|xi =| xj and r0 (xi , xj ) <= 0}

定理 31 提案手法は常に従来の Aﬃnity Propagation [1] と同

データポイントペアの集合 P A(xj , 1) は以下のような特性をじ結果を出力する．
証明持つ．
補題 34 P A(xj , 1) に含まれるデータポイントペアの availabil-

ity は 1 回目の反復計算において集約計算により求めることができる．

定義 23 より，xi の exemplar の決定には収束した re-sponsibility と availability を用いて r(xi , xj ) + a(xi , xj ) を最大化するデータポイント xj を見つける必要がある．補題 31，

33，35，36 より，提案手法による枝刈りは responsibility とavailability の値は従来の Aﬃnity Propagation [1] と同じ値を証明

補題 33 より明らかである．

□

3. 3 メッセージの集約計算
本節では，3. 2 章において定義 21 を用いた計算が不要なデー
タポイントペアのメッセージの計算方法について説明する．

正確に出力することを理論的に証明した．ゆえに提案手法は，

r(xi , xj ) + a(xi , xj ) の値を正確に得ることができるので，従来の Aﬃnity Propagation と同様の exemplar を出力することができる．

□

はじめに，提案手法における枝刈りされたデータポイントペア

2 節で述べたように，全ての exemplar が決定すると，クラスの responsibility の計算について説明する．データポイントペア

タリング結果は一様に形成される．ゆえに定理 31 より，提案手の集合 P R(xi , t) に含まれるデータポイントペアの responsibility

法は従来の Aﬃnity Propagation [1] と同じクラスタリング結果

は以下の式によって計算できる．

を出力することができる．

Algorithm 2 Proposed Method

その後，次の反復計算において定義 21 を用いた計算が不要な

Input: S
Output: exemplars for data object in X
1: for each xi ∈ X do
2:obtain R = {X × X}\Pr based on F-AP [5];3:obtain A = {X × X}\Pa based on F-AP [5];データポイントペアを定義 31，33 に基づいて決定する（23–26

4: for each (xi , xj ) ∈ R do
5:
obtain R(xi , 1) = {(xi , xj )|(xi , xj ) ∈/ P R(xi , 1)} based on Defini-法では，枝刈りされたデータポイントペア Pr ，Pa に対して，既tion 32;

6: for each (xi , xj ) ∈ A do
7:
obtain A(xj , 1) = {(xi , xj )|(xi , xj ) ∈/ P A(xj , 1)} based on Definition 34;

8: repeat9:
for each xi ∈ X do
10:for each (xi , xj ) ∈ R(xi , t) do
11:compute r(xi , xj ) by Definition 21;
12:
for each (xi , xj ) ∈ P R(xi , t) do
13:compute r(xi , xj ) based on Definition 35;
14:
if r(xi , xj ) is not updated then15:
R = R\{(xi , xj )};16:
for each xj ∈ X do
17:for each (xi , xj ) ∈ A(xj , t) do
18:
compute a(xi , xj ) by Definition 21;
19:
for each (xi , xj ) ∈ P A(xj , t) do
20:
compute a(xi , xj ) based on Definition 36;
21:
if a(xi , xj ) is not updated then22:
A = A\{(xi , xj )};23:
for each xi ∈ R do
24:
obtain R(xi , t + 1) and P R(xi , t + 1) based on Definition 31;
25:
for each xj ∈ A do
26:
obtain A(xj , t + 1) and P A(xj , t + 1) based on Definition 33;
27:
t = t + 1;
28: until R, A = ∅29: for each (xi , xj ) ∈ Pr do
30:
get r(xi , xj ) = ρ(xi , xj );31: for each (xi , xj ) ∈ Pa do
32:
get a(xi , xj ) = α(xi , xj );33: for each xi ∈ X do
34:
get an exemplar e(xi ) by Definition 23;行目）．これにより高速化を実現する．
最後に exemplar を検出する（29–34 行目）．はじめに提案手
存手法 [4, 5] と同様の手法を用いることで反復計算を実行することなく収束後の responsibility と availability の値を計算することができる（29–32 行目）．その後，得られた responsibility とavailability を用いて exemplar を決定する（33–34 行目）．

4 評価実験
本節では，実データを用いて提案手法の有用性を実験的に評価する．ここでは以下を示す．

•

高速性：提案手法は従来の Aﬃnity Propagation [1] や既存手法 [4, 5] と比較して高速に処理できることを示す（4. 2 節）．

•

スケーラビリティ：提案手法はデータ数の観点から，従来の Aﬃnity Propagation [1] と比較して優れたスケーラビリティ
を示す（4. 3 章）．

•

正確性：提案手法は高速化のためにメッセージ集約に基づ

く計算の簡略化を行うが，従来の Aﬃnity Propagaton [1] と同一のクラスタリング結果を出力する事ができる（4. 4 節）．

4. 1 実 験 環 境
本実験では，提案手法（ここでは Proposed と記述），従来の Aﬃnity Propagation [1]（ここでは Original-AP と記述），

3. 4 アルゴリズム

Graph-AP [4]，F-AP [5] を比較した．全ての実験は CPU が提案手法のアルゴリズムを Algorithm2 に示す．提案手法では，

Intel(R) Xeon(R) E5-1620 3.5GHz，128GB RAM のサーバ上

各データポイント間の類似度 S を入力値とし，exemplar を出力で実行した．ダンピングファクタ λ は既存手法 [1, 4, 5] で推奨さする．Algorithm2 は大きく 3 つのパートに分かれており，それれている 0.5 に設定し，反復回数は 1,000 回とした．データセッ

ぞれ初期データポイントペアのセットの取得（1–7 行目），逐次

トは以下の 3 つのデータセットを用いた．

的メッセージ集約を含むメッセージの伝搬（8–28 行目），そして exemplar の検出（29–34 行目）である．

•

Perfume：このデータセットは，UCI Machine Learning

Repository(https://archive.ics.uci.edu/ml/index.php) [11]はじめに提案手法では，1 回目の反復計算において定義 21 をで公開されているものであり，20 種類の香水の匂いで構成されて用いた計算が不要なデータポイントペアを決定する（1–7 行目）．

いる．データは 28 秒の間，毎秒ハンドヘルド臭気計 (OMX-GR

既存手法である F-AP [5] と同様に提案手法でも各データポイン

sensor) を用いて得られた．データ数は 560 で次元数は 2 である．

ト間の responsibility と availability の上限値と下限値を計算し，•Geo：こ の デ ー タ セット は ，人 口 統 計 や 公 共 施

反復計算が不要なデータポイントペア Pr ，Pa を得ることで枝刈設の場所などの自治体オープンデータを公開しりを実行する（1–3 行目）．そして定義 32，34 に基づいて 1 回て い る CKAN(https://ckan.open-governmentdata.org/

目の反復計算において定義 21 を用いた計算が不要なデータポイ

dataset/401005_shinoshisetsu) [12] にある北九州市内の市

ントペアを定義する（4–7 行目）．

役所，図書館，学校等の施設情報に関するオープンデータであ

次に，再帰計算を実行する（8–28 行目）．ここでは，定義 21に基づく計算が必要と判定されたデータポイントペアセット

R(xi , t)，A(xj , t) に対して responsibility と availability を収束る．本実験ではデータの中で，緯度・経度を用いてクラスタリン
グを行なった．データ数は 1,309 である．

•

Bench：こ の デ ー タ セット は ，Clustering benchmark

するまで再帰的に更新する（10–11，17–18 行目）．次に，データ

datasets(http://cs.uef.fi/sipu/datasets/) [13] で公開されポイントペアセット P R(xi , t)，P A(xj , t) に対して定義 35，36ている人工データである．データ数は 3,000 で次元数は 2 である．

を用いて responsibility と availability を計算する（12–13 行目，全てのデータセットに対して，類似度 S は負のユークリッド

19–20 行目）．その後，既存手法 [5] と同じように，メッセージ

距離を用いた．また，preference は全ての実験において他の類似が収束したと判定されたデータポイントペアについてはその後

度の中央値に設定した．

の再帰計算を行う対象から取り除く（14–15 行目，21–22 行目）．

104

350

106

20000

Original-AP
Q-AP

18000
300

105
16000

250
104

3

10

100

Wall clock time [sec]150Wall clock time [sec]Wall clock time [sec]Wall clock time [sec]

14000

200

12000

10000

103

2

8000

10

6000
1

10
4000

50

2000
102

0
Original-AP

Graph-APF-AP

Proposed

100
500

Original-AP

図 1 実行時間 (Perfume)Graph-APF-AP

Proposed

図 2 実行時間 (Geo)Graph-APF-AP

Proposed

図 3 実行時間 (Bench)

750

1000

1250

1500
1750
# of data objects

2000

2250

2500

図 4 スケーラビリティ

AP，F-AP で得られた exemplar の中で Original-AP で得られ

表1 正 確 性

Graph-AP F-AP Proposed

た exemplar と一致したデータポイントの割合を表す．一方でPerfume (Recall)

1.00

1.00

1.00

Recall は，Original-AP で得られた exemplar の中で提案手法，

Perfume (Precision)

1.00

1.00

1.00

Geo (Recall)

1.00

1.00

1.00

Graph-AP，F-AP で得られた exemplar と一致したデータポ

Geo (Precision)

1.00

1.00

1.00

イントの割合を表す．もしも提案手法，Graph-AP，F-AP で得られた exemplar と従来の Aﬃnity Propagation で得られた

exemplar が全て一致しているならば，Precision と Recall はい
4. 2 高 速 性

ずれも 1 を示す．実験結果を表 1 に示す．ここで，Bench デー

3 種類のデータセットに対して各アルゴリズムを実行したときタセットについては，従来の Aﬃnity Propagation が 24 時間以の実行時間を図 1–3 に示す．ここで，Bench データセットにお内に実行が終了せず途中で実行を打ち切ったため，クラスタリン

いて，従来の Aﬃnity Propagation は 24 時間以内に実行が終了

グ結果が出力されていない．ゆえに結果は省略されている．表 1

しなかったため，途中で実験を打ち切った．

より，Perfume データセットと Geo データセットいずれに対し

図 1–3 より，提案手法は全てのデータセットに対して比較手ても提案手法は 1 を出力している．定理 31 より，提案手法は精法よりも高速に処理できていることがわかる．特に提案手法は，度を落とすことなく無駄な計算を省略できることが理論的に証明

従来の Aﬃnity Propagation や state-of-the-art とされる F-APされている．以上より，提案手法は従来の Aﬃnity Propagationと比較してそれぞれ最大で 42.53 倍，5.59 倍の高速化を達成しと同じクラスタリング結果を出力しつつ高速な処理が行えるこ

た．提案手法は，Graph-AP や F-AP と同様に反復計算を行うとを実験的に示した．

データポイントペアを削減したことが実行時間の短縮につながっている．また，反復計算の途中でメッセージが収束したデータポ

5 関連研究イントペアに対しては以降の反復計算を行う対象から取り除いている．さらに，3 節で述べたように，定義 21 を用いた計算が不要なデータポイントペアを集約してメッセージを求めること
でさらなる高速化を実現した．

クラスタリングは与えられたデータの中にある隠れたパターンを見つける方法としてもっとも基本的なデータ分析技術の一つであり，これまで多くのアルゴリズムが提案されてきた．

k-means 法 [2] はもっとも有名なクラスタリングアルゴリズム
4. 3 スケーラビリティの一つである．この手法はクラスタ内の centroid と呼ばれるク

データ数を変化させることで提案手法のスケーラビリティを

ラスタの重心を見つけることでユーザが指定した数のクラスタを評価した．スケーラビリティを評価するために，さらに 5 つの形成する．また，k-means 法と同じような手法として k-medoids

データセットを生成した．これらのデータセットは全て Bench

法 [14] がある．しかし，いずれのアルゴリズムもユーザが予め

データセットからランダムにそれぞれ 500，1,000，1,500，2,000，

クラスタ数を指定する必要があることやクラスタリング結果が2,500 のデータをサンプリングしたものである．実験結果を図 4

初期状態に依存してしまうという欠点がある．

に示す．図 4 より，提案手法は従来の Aﬃnity Propagation と2007 年に Frey らによって提案された Aﬃnity Propagation [1]

比較してデータ数の観点から優れたスケーラビリティを示していは，ファクタグラフ [16] 上でメッセージ伝搬を行うことでグラることがわかる．これは，4. 2 章で示したように，responsibility

フモデルの最適化を行う Belief Propagation [17, 18] を応用したと availability のメッセージ計算の際に定義 21 による計算が不クラスタリングアルゴリズムである [19]．Aﬃnity Propagation

要なデータポイントペアについて集約してメッセージを計算しは k-means 法 [2] や k-medoids 法 [14] とは異なり，ユーザがクているためである．

ラスタ数を予め指定する必要がなく，同じデータセットでは常に4. 4 正 確 性
次に，提案手法におけるクラスタリング結果の正確性を実一定の結果を出力するアルゴリズムとして近年着目され，これまで K-AP [20] や MEAP [21] など，多くの応用的な手法が提案されている．

験的に確認する．本実験では精度を評価するため Precision としかし，第 2 節で述べたように，Aﬃnity Propagation はデー

Recall [15] を用いる．ここで，Precision とは，提案手法，Graph-

タ数が大きくなるにつれて実行時間も急激に増えてしまうという欠点がある．そこで Aﬃnity Propagation を高速化した手法
がこれまでいくつか提案されてきた．

Jia らは 2008 年に FSAP [3] と呼ばれる高速化手法を提案した．FSAP は K-最近傍を用いて疎な K 近傍グラフを構築する
ことで反復計算を行うメッセージの数を削減する．また，クラスタリング精度を向上させるために，構築した K 近傍グラフにエッジを追加し，そのグラフ上で再度反復計算を行う．これにより，従来の Aﬃnity Propagation [1] と比較して処理時間の短縮を実現した．しかしこの手法はパラメータ K によって結果が異なるため，従来の Aﬃnity Propagation と同一の結果を出力する事ができない可能性がある．

Fujiwara らは，反復計算が不要なエッジを枝刈りすることでAﬃnity Propagation の高速化を図る Graph-AP [4] を提案した．Graph-AP では，各データポイント間において収束後のメッ
セージの上限値と下限値を計算し，それらの値を用いた条件式を満たさないようなデータポイント間のメッセージは反復計算を行わないことで無駄な計算を削減できる．枝刈りされたエッジのメッセージの値は反復計算をせずに求めることができるため，
従来の Aﬃnity Propagation と同じ結果を出力することができる．しかしこの手法は，反復計算中にメッセージが収束したとしても全てのメッセージが収束するまで計算を続けなければならないため無駄な計算が行われている．

Fujiwara らは Graph-AP をベースにさらなる高速化を実現す
る F-AP [5] を提案した．F-AP では，各データポイント間において収束する前の各 iteration 中のメッセージの値の上限値と下限値を推定することで，exemplar の決定に必要なエッジを限定する．また，各 iteration 中に計算されたメッセージの値が収束しているかどうかの判定を行う．もし収束していると判定された
場合は以降の反復計算を行う対象から取り除く．これらのアイ
デアにより，Graph-AP よりも高速に処理を行うことができる．
しかしこの手法は，枝刈りされなかったデータポイントペアのメッセージの中にも複雑な計算が不要なメッセージが含まれており，無駄な計算を削りきれていない．

6 おわりに本稿では，大規模データに対する Aﬃnity Propagation の高速化手法を提案した．
提案手法は，既存手法で行われていた複雑な計算を省略できるデータポイントペアを特定し，それらを集約してメッセージを求めることで高速化を図った．評価実験では，提案手法がクラスタリング精度を損なうことなく，既存手法 [1, 4, 5] よりも高速に処理できることを示した．
今後の課題として，より大規模なデータでの実験やさらなる高速化があげられる．

7 謝

辞

本 研 究 の 一 部 は JST ACT-I な ら び に JSPS 科 研 費

JP18K18057 による支援を受けたものである．

文

献[1] B. J. Frey, D. Dueck, “Clustering by Passing Messages Between Data Points,” Science, Vol. 315, No. 5814, pp. 972–976,
2007.
[2] Jain, Anil K, “Data Clustering: 50 Years beyond K-means,”
Pattern recognition letters, Vol. 31, No. 8, pp. 651–666, 2010.
[3] Y. Jia, J. Wang, C. Zhang, and X.-S. Hua, “Finding Image
Exemplars Using Fast Sparse Aﬃnity Propagation,” in Proceedings of the 16th ACM international conference on Multimedia, pp. 639–642, 2008.
[4] Y. Fujiwara, G. Irie, and T. Kitahara, “Fast Algorithm for
Aﬃnity Propagation,” in Proceedings of International Joint
Conference on Artificial Intelligence, pp. 2238–2243, 2011.
[5] Y. Fujiwara, M. Nakatsuji, H. Shiokawa, Y. Ida, and M.
Toyoda, “Adaptive Message Update for Fast Aﬃnity Propagation,” in Proceedings of ACM SIGKDD Conference on
Knowledge Discovery and Data Mining, pp. 309–318, 2015.
[6] A. Rangrej, S. Kulkarni, and A. V. Tendulkar, “Comparative
Study of Clustering Techniques for Short Text Document,” inProceedings of the 20th international conference companion
on World wide web, pp. 111–112, 2011.
[7] Z. Liu, P. Li, and Y. Zheng, and M. Sun, “Community Detection by Aﬃnity Propagationt,” Technical Report, 2008.
[8] C. Jia, Y. Jiang, and J. Yu, “Aﬃnity Propagation on Identifying Communities in Social and Biological Networks,” International Conference on Knowledge Science, Engineering andManagement, pp. 597–602, 2010.
[9] Z. Liu, P. Li, and Y. Zheng, and M. Sun, “Clustering to Find
Exemplar Terms for Keyphrase Extraction,” in Proceedingsof the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1-Volume 1, pp. 257–266, 2009.
[10] H. H. Alrehamy, and C. Walker, “SemCluster: Unsupervised Automatic Keyphrase Extraction Using Aﬃnity Propagation,” UK Workshop on Computational Intelligence, pp.
222–235, 2017.
[11] K Bache, M Lichman, “UCI Machine Learning Repository,”
2013.
[12] General Aﬀairs Planning Bureau, “Kitakyushu city facilities(common format),” 2018, https://ckan.open-governmentdata.
org/dataset/401005_shinoshisetsu.
[13] Pasi Fränti et al, “Clustering Datasets,” 2015, http://cs.
uef.fi/sipu/datasets/.
[14] K. Leonard, R. Peter J, “Clustering by Means of Medoids,”
Elsevier, pp. 405–416, 1987.
[15] C. D. Manning, P. Raghavan, and H. Schütze, “Introduction
to Information Retrieval,” Cambridge University Press, 2008.
[16] F. R. Kschischang, B. J. Frey, and H-A. Loeliger, “Factor
Graphs and the Sum-Product Algorithm,” IEEE Transactions on information theory, Vol. 47, No. 2, pp. 498–519, 2001.
[17] Y. Weiss, and W. T. Freeman, “On the Optimality of Solutions of the Max-Product Belief-Propagation Algorithm in
Arbitrary Graphs,” IEEE Transactions on information theory, Vol. 47, No. 2, pp. 736–744, 2001.
[18] A. Riazanov, y. Maximov, and M. Chertkov, “Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network
Flow,” 2018 Annual American Control Conference (ACC),
pp. 6108–6113, 2018.
[19] I. E. Givoni, and B. J. Frey, “A Binary Variable Model for
Aﬃnity Propagation,” Neural computation, Vol. 21, No. 6,
pp. 1589–1600, 2009.
[20] Z. Xiangliang, W. Wei, N. Kjetil, S. Michele, “K-AP: Generating Specified K Clusters by Eﬃcient Aﬃnity Propagation,”in Proc ICDM, pp. 1187–1192, 2010.
[21] W. Chang-Dong, L. Jian-Huang, S. Ching Y and Z. JunYong, “Multi-Exemplar Aﬃnity Propagation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.
35, Num. 9, pp. 2223–2237, 2013.