Page 224 - 《软件学报》2021年第12期

3888 Journal of Software 软件学报 Vol.32, No.12, December 2021

ܧ ଵ ܧ ௜ ܧ ே
ܫ ଵ
… …
ܿ ଵଵ ܿ ଵ௜ ܿ ௜ே
ܵ ଵଵ ܵ ଵ௜ ܵ ଵே
ܫ ௜
…
…
…
… …
ܿ ௜ଵ ܿ ௜௜ ܿ ௜ே
ܵ ௜ଵ ܵ ௜௜ ܵ ௜ே
ܫ ே
…
…
…
… …
ܿ ேଵ ܿ ே௜ ܿ ேே
ܵ ேଵ ܵ ே௜ ܵ ேே

(1) 标准 AP 算法二元变量因子图
ܧ ଵ ܧ ௜ ܧ ே ܧ ௝
ܫ ଵ
ߩ ௜௝ ሺܿ ௜௝ ሻ ߙ ௜௝ ሺܿ ௜௝ ሻ
… …
ܿ ଵଵ ܿ ଵ௜ ܿ ௜ே
ߝ ௜௝ ሺܿ ௜௝ ሻ ߚ ௜௝ ሺܿ ௜௝ ሻ
ܵ ଵଵ ܵ ଵ௜ ܵ ଵே ܵ ௜௝ ܿ ௜௝ ܫ ௜
ܫ ௜
ߟ ௜௝ ሺܿ ௜௝ ሻ
…
…
…
… …
ܿ ௜ଵ ܿ ௜௜ ܿ ௜ே (a)非对角线上变量信息传递
ܵ ௜௜ ܧ ୧
ܵ ௜ଵ ܵ ௜௜ ܵ ௜ே
ܫ ே
ߝ ௜௜ ሺܿ ௜௜ ሻ
…
…
…
ߩ ௜௜ ሺܿ ௜௜ ሻ
… … ߙ ௜௜ ሺܿ ௜௜ ሻ
ܿ ேଵ ܿ ே௜ ܿ ேே
ߛ ௜௞ ሺܿ ௜௜ ሻ ߚ ௜௜ ሺܿ ௜௜ ሻ
ܨ ଵ
ܵ ேଵ ܵ ே௜ ܵ ேே
ܨ ௞ ܿ ௜௜ ܫ ௜
߮ ௜௞ ሺܿ ௜௜ ሻ ߟ ௜௜ ሺܿ ௜௜ ሻ
ܨ ௞
(b)对角线上变量信息传递
ܨ ே
(2) 加入新约束的 AP 算法因子图及其信息传递
Fig.2 Factor graph of the AP method
图 2 AP 算法二元变量因子图及其改进后的因子图
在图 2(1)中,{c ij } N×N 中的 c ij 属于{0,1},c ij =1 表示点 j 是点 i 的聚类中心.标准 AP 算法需要满足两个聚类约
束条件:一个是聚类中心的唯一性,即一个点只能属于一个类(图 2(1)中约束 I);另一个是聚类中心的存在性,即
当一个点是另一个点的聚类中心时,该点必然是自己的聚类中心(图 2(1)中约束 E).基于这两个约束,AP 算法通
过在因子图上的信息传递更新使得全局函数 S(C)最大,其具体定义见公式(2).
⎧ ⎪ 0, ∑ h = 1
ij
() = ⎨
Ic : i j
i
⎪ ⎩ −∞ , otherwise
⎧ 0, c = max h
() = ⎨
Ec : j jj i ij (2)
j
⎩ −∞ , otherwise
( ) + ∑
Max : ( ) = SC ∑ S c + ij ij E c : j ∑ I c : i
( )
j
i
, ij j i
针对这一 NP 难问题,依据 max-sum 算法 [12,19] 可推导出 AP 算法的迭代更新公式.在 AP 算法中,有两种重要
的消息在样本点间传递,分别是吸引度(responsibility)和归属度(availability),在算法中表现为吸引度矩阵 R=
{r(i,j)} N×N 和归属度矩阵 A={a(i,j)} N×N ,其更新公式如下: