A Semi-supervised Affinity Propagation Clustering Method with Homogeneity Constraint
-
摘要: 以近邻反射传播 (Affinity propagation, AP) 聚类算法为基础, 提出了一种基于同类约束的半监督近邻反射传播聚类方法 (Semi-supervised affinity propagation clustering method with homogeneity constraints, HCSAP).该方法在聚类目标函数中引入同类约束项, 以保证聚类结果与同类集先验信息一致.利用最大和信任传播 (Max-sum belief propagation) 优化过程对目标函数进行求解, 导出同类约束下的吸引度 (Responsibility) 和归属度 (Availability) 的迭代方程.人工数据集和真实数据集上的实验结果表明本文所提方法的有效性.Abstract: In this paper, a semi-supervised affinity propagation (AP) clustering algorithm with homogeneity constraint, called HCSAP (semi-supervised affinity propagation clustering method with homogeneity constraints), is proposed. To keep consistency between the clustering results and the priori information about homogeneity sets, the constraint terms are introduced to the objection function of algorithm AP. With the max-sum belief propagation procedure, the objection function can be resolved into the corresponding responsibility and availability update equations. Experiments on synthetic dataset and real-world datasets indicate the effectiveness of the proposed HCSAP.
-
近邻反射传播聚类 (Affinity propagation, AP)[1]是以数据之间的相似度为基础, 通过迭代更新吸引度 (Responsibility) 和归属度 (Availability) 进行数据聚类.与K-means聚类相比, 其特点是: 1) 不需要预先指定类中心, 由吸引度和归属度的自动确定类中心; 2) 聚类的类数也不需要预先指定, 在设置好参数Preference后由算法本身自动决定聚类的类数; 3) 既适用于相似度对称的场合也适用于相似度非对称的场合, 因此应用范围更广; 4) 结合稀疏处理方式可适合于大规模数据聚类; 5) 聚类速度较快.近邻反射传播聚类已成功应用于航线规划[1]、图像分割[2]、基因组识别[3]、目标识别[4]等领域, 受到众多研究者的重视[5].
近邻反射传播聚类是一种无监督学习方法, 而在聚类分析中往往具有部分数据的先验知识, 如已知某些数据属于同一类或部分数据的标签信息等.利用好这些先验知识将有助于聚类性能的提高.将先验知识用于聚类, 一般有两种途径[6]:一类是基于相似度的半监督聚类, 即利用先验知识对数据点之间的相似度进行修改, 然后再进行聚类.如Bijral等[7]在密度距离估计的基础上, 提出一种图上最短路径的简单有效的计算方法, 并将该方法用于稠密的全连接图, 进而有效提高聚类速度.在近邻反射传播聚类范畴中, 基于相似度的半监督近邻反射传播聚类算法的工作已较为丰富.该类方法的主要特点是根据must-link和cannot-link成对约束对相似性矩阵进行局部调整. must-link成对约束是指受约束的两个点属于同一类, 而cannot-link成对约束是指受约束的两个点不在同一类中[8].
据此, 肖宇等提出了SAP算法[9]. SAP算法将cannot-link成对约束点之间的相似性度量置为 $-\infty$ , 将must-link成对约束点之间的相似性度量置为0, 同时根据最短路径调整must-link约束点和其他点之间的相似性度量.然后在新的相似度矩阵上使用近邻反射传播聚类算法.在SAP算法基础上, 张震等提出了基于分层的SAP-SC方法[10], 该方法将AP聚类过程等分成若干层聚类, 通过构造成对点约束和使用子簇标签映射进行半监督学习, 采用基于组合提升的方法将各层聚类结果加权叠加.文献[11]根据通过数据流密度变化, 以加权方式对相似性度量进行调整, 然后再进行AP聚类. Givoni等根据must-link成对约束所具有传递性和闭包特性, 提出SSAP算法[12], 该算法将具有相同标签的数据点构成同类集, 再由同类集派生出一个虚点, 利用虚点对原始相似性矩阵进行扩展.实点之间的相似性度量不变, 实点和虚点之间的相似性度量则根据实点是否包含于虚点所对应的同类集来决定.当实点是虚点所对应的同类集中的元素时, 两者之间的距离置0, 否则相似度量值置为实点与同类集中各个数据点之间相似度的最大值.同时将cannot-link成对约束点间的相似性度量置为 $-\infty$ .基于相似度的半监督近邻反射传播聚类存在以下不足: 1) 并不能保证聚类结果与成对约束一致[13].如将must-link成对约束点之间的相似性度量置0, 能提高约束点选择彼此作类中心点的可能性, 但不能保证约束点选择的中心点相同.特别地, 当数据点 $A$ , $B$ , $C$ 两两之间均存在must-link成对约束时, 如果数据点 $A$ 和 $B$ 被选为不同类别的类中心点时, 由于数据点 $C$ 和数据点 $A$ , $B$ 的相似度都为0, 因此数据点 $C$ 可以任意选择其中之一作为自己的类中心点而不会改变聚类目标函数值, 而且也会导致聚类后的调整方法失效[6].这样就会导致must-link成对约束点并不在同一类中. 2) 这种处理方式容易产生多个并列中心点, 因此可能导致更多的震荡现象[13]. 3) 相似性度量置0改变了算法适用于相似性矩阵不对称的特点.另一类是基于约束的半监督聚类, 即利用先验信息对聚类算法添加约束, 使得聚类结果与先验信息保持一致.在文献[14]中的MPCK-MEANS聚类方法在考虑簇与簇之间存在的差异的基础上, 借助于无标记数据和成对约束样本, 在进行簇指派的迭代过程中进行度量学习, 同时实现了约束聚类和局部马氏距离的学习.尹学松等在文献[15]中提出了DSCA方法, 该方法首先利用must-link成对约束和cannot-link成对约束得到投影矩阵, 在投影空间中对数据聚类得到聚类标号, 然后利用线性判别分析 (Linear discriminant analysis, LDA) 选择子空间, 最后使用基于成对约束的K均值算法对子空间中的数据聚类.基于约束的半监督聚类根据先验信息在聚类算法中添加适当的约束, 确保聚类结果与先验信息一致, 因此较之于基于相似度的半监督聚类, 基于约束的半监督策略更显有效.在近邻反射传播聚类算法范畴内, 基于约束的半监督近邻反射传播聚类算法目前还未发现有相关研究.本文以must-link成对约束为基础, 提出一种基于同类约束的半监督近邻反射传播聚类方法.
1. 近邻反射传播算法
在近邻反射传播学习算法中, 通过吸引度和归属度迭代, 让每个数据点在全体数据点集中找自己最优的类中心点, 最终使所有数据点到各自的类中心点的相似度之和最大, 同时满足一致性条件.吸引度 $r(i, j)$ 和归属度 $a(i, j)$ 迭代方程如式 (1) 和式 (2) 所示.
$ \left( {i, j} \right) = s(i, j) - \mathop {\max }\limits_{k \ne j} \left[{s(i, k) + a\left( {i, k} \right)} \right] $
(1) $ \begin{align} &a\left( {i, j} \right) =\notag\\ &\qquad \begin{cases} \min [0, r\left( {j, j} \right) + & \rm{ }\\ \qquad \mathop \sum \limits_{k \notin \left\{ {i, j} \right\}} \max \left[{0, r\left( {k, j} \right)} \right]], &j \ne i\\[2mm] \sum\limits_{k \ne j} \max \left[0, {r\left( {k, j} \right)} \right], &j = i \end{cases} \end{align} $
(2) 式中, $s(i, j)$ 为数据点 $i$ , $j$ 之间的相似度.吸引度 $r(i, k)$ 由数据点 $i$ 指向数据点 $k$ , 表示数据点 $k$ 适合作为数据点 $i$ 的类中心点的程度; 归属度 $a(i, k)$ 是从数据点 $k$ 指向数据点 $i$ , 表示数据点 $i$ 选择数据点 $k$ 作为其类代表点的合适程度.迭代开始时吸引度和归属度均初始化为0, 使每一个数据点都成为潜在的类中心点, 通过迭代使得式 (3) 所示的聚类目标函数最大化.
$ \begin{align} S\left( C \right) = \sum\limits_{i = 1}^N {{{s}}\left( {i, {c_i}} \right)} + \sum\limits_{k = 1}^N {{\delta _k}} \left( C \right) \end{align} $
(3) 式中, $c_i$ 为数据点 $i$ 的类中心点, $C$ 为由 $c_i$ 构成的分配向量, $i=1, \cdots, N$ ( $N$ 为数据点个数). $S(C)$ 为所有数据点到各自的类中心点的相似度之和. $\delta_k (C)$ 如式 (4) 所示.
$ \begin{align} {\delta _k}\left(C\right) = \begin{cases} - \infty, & {{{c}}_k} \ne k~\mbox{但}~ \exists i, ~{c_i} = k\\[2mm] 0, &\mbox{其他} \end{cases} \end{align} $
(4) 该项为一致性约束惩罚项, 若有某个数据点 $i$ 选择 $k$ 作为其类代表点, 即 $c_i=k$ , 那么数据点 $k$ 必须选择自身作为类代表点, 即 $c_k=k$ , 否则函数取值 $-\infty$ , 使数据点 $i$ 在下一次迭代中不再选择数据点 $k$ 作为自己的中心点.
各个数据点的类中心点 $c_i$ 按式 (5) 计算得到:
$ \begin{align} {c_i} = \arg \max\limits_k \left[{a\left( {i, k} \right) + \left. {r\left( {i, k} \right)} \right]} \right.\ \end{align} $
(5) 即数据点选择彼此间吸引度和归属度累加最大的数据点为自己的类中心点.
2. 同类约束近邻反射传播半监督聚类
类属相同的数据点所构成的集合称为同类集.为保证聚类结果和同类集先验信息保持一致, 在聚类目标函数中引入同类约束.并将此方法称为基于同类约束的半监督近邻反射传播聚类方法 (Semi-supervised affinity propagation clustering method with homogeneity constraints, HCSAP).
2.1 部分符号说明
为方便描述, 文中所涉及的部分符号示例说明如表 1所示.
表 1 部分符号说明Table 1 The explanation of some symbol符号 意义 $N$ 聚类数据点个数 $M$ 同类集个数 $h_1,h_2$ 数据点 $h_1,h_2$ $c_{ij}$ 变量节点, 为0表示 $j$ 不是 $i$ 的类中心点; 为1表示 $j$ 是 $i$ 的类中心点 $E_{ij}(\cdot)$ $E_j(c_{1j},\cdots,c_{Nj})$ 数据点 $j$ 的同类约束与一致性约束函数 $\rho_{ij}$ 表示变量节点 $c_{ij}$ 向函数节点 $E_j$ 所发送的标量信息 $c_i$ 数据点 $i$ 的类中心点 $P$ 全体同类集所构成的集合 $p^i$ 数据点 $i$ 所在的同类约束集 $I_i(\cdot)$ $I_i(c_{i1},\cdots,c_{iN})$ 为数据点 $i$ 的唯一性约束函数 $\alpha_{ij}$ 表示函数节点 $E_j$ 向变量节点 $ c_{ij}$ 所发送的标量信息 $\beta_{ij}$ 表示变量节点 $c_{ij}$ 向函数节点 $I_i$ 所发送的标量信息 $p_v$ 第 $v$ 个同类集 ⊕ 异或 ${{\bar P}}$ 无同类约束的数据点集 $S_{ij}(\cdot)$ 定义在数据点 $i$ , $j$ 之间的相似度函数 $s(i,j)$ 数据点 $i$ , $j$ 之间的相似度 $\eta_{ij}$ 表示函数节点 $I_i$ 向变量节点 $c_{ij}$ 所发送的标量信息 2.2 HCSAP聚类目标函数
为描述方便, 记待聚类数据点集 $W=\{1, 2$ , $\cdots$ , $N\}$ .对同类点集 $p_m\subseteq W$ , $m=1, 2, \cdots, M$ , 有 $\forall i, j\in p_m$ , $c_i=c_j$ .记 $P=\{p_m |m=1, 2, \cdots$ , $M\}$ , $\bar P = W - \bigcup\nolimits_{m = 1}^M {{p_m}} $ .
HCSAP聚类目标函数定义如下:
$ \begin{align} T\left( C \right) =&\ \sum\limits_{{c_i}_j} {{S_{ij}}{c_{ij}}} + \sum\limits_{i = 1}^N {{I_i}\left( {{c_{i1}}, \cdots, {c_{iN}}} \right)} +\notag \\ & \ \sum\limits_{j = 1}^N {{G_j}\left( {{c_{1j}}, \cdots, {c_{Nj}}} \right)} +\notag\\ &\ \sum\limits_{k = 1}^N {{F_k}\left( {{c_{{\rm{1}}k}}, \cdots , {c_{Nk}}} \right)} \end{align} $
(6) 其中,
$ {S_{ij}}= \begin{cases} 0, &{c_{ij}} = 0, \\ s\left( {i, j} \right), & {c_{ij}} = 1, \end{cases} \quad i, j = 1, \cdots, N $
(7) $ \sum\limits_{i = 1}^N {{I_i}\left( {{c_{i1}}, \cdots, {c_{iN}}} \right)} = \begin{cases} - \infty, &\sum\limits_{j = 1}^N {{c_{ij}} \ne 1} \\ 0, &\mbox{其他} \end{cases} $
(8) $ \begin{align} &\sum\limits_{j = 1}^N {{G_j}\left( {{c_{1j}}, \cdots, {c_{Nj}}} \right)} =\notag \\ &\qquad \begin{cases} - \infty, &{c_{jj}} = 0~\mbox{且}~ \exists i \ne j~~ {\rm{s.t}}{\rm{. }}~~{c_{ij}}= 1\\ 0, & {\mbox{其他}} \end{cases} \end{align} $
(9) $ \begin{align} &\sum\limits_{k = 1}^N {{F_k}\left( {{c_{{\rm{1}}k}}, \cdots, {c_{Nk}}} \right)} = \notag\\ &\quad \begin{cases} - \infty, &\exists m, \exists h_1, h_2 \in {p_m}, \\ & {\rm{s}}{\rm{.t}}{\rm{.}}~~{c_{{h_1}k}}\oplus {c_{{h_2}k}} = 1, ~~m \in \{1, \cdots, M\} \\ 0, &\mbox{其他} \end{cases} \end{align} $
(10) 与式 (3) 不同, 式 (6) 中的 $C$ 为由 $c_{ij}$ 构成的分配矩阵, 且 $c_{ij}$ 只取0或1. $\sum\nolimits_{{c_i}_j}{S_{ij}}{c_{ij}}$ 为定义在分配矩阵上的函数, 表示数据点到各自聚类中心点的距离之和. $\sum\nolimits_i{{I_i}\left({{c_{i1}}, \cdots, {c_{iN}}}\right)}$ 为唯一性约束惩罚项.唯一性约束是要求每个数据点只能有一个中心点, 即数据点只能属于某一个类.如果违背这一约束, 则函数值为 $-\infty$ . $\sum\nolimits_j {{E_j}\left({{c_{1j}}, \cdots, {c_{Nj}}}\right)}$ 为一致性约束惩罚项.一致性约束项是指如果该数据点不是中心点, 即 $c_{jj}=0$ , 那么其余数据点不可以选择该数据点为中心点.如果违反该规则, 即 $\exists i \ne j$ , 有 $c_{ij}$ $=$ $1$ , 则函数值为 $-\infty$ .该约束也要求被选作中心点的数据点必须选择自身为中心点. $\sum\nolimits_k{F_k}({c_{1k}}$ , $\cdots$ , ${c_{Nk}})$ 为同类约束惩罚项.同类约束要求同类集中的所有数据点选择的类中心点必须相同.如果同类集中存在两个数据点的中心点不相同, 即 $\exists m$ , $\exists {h_1}, {h_2}\in{p_m}$ , 使得 ${c_{{h_1}k}}\oplus{c_{{h_2}k}}=1$ , 则违反了该约束, 函数取值为 $-\infty$ , 进而保证聚类结果和同类约束相一致.
为简化因子图, 将式 (9) 和式 (10) 合并为式 (11).
$ \begin{align} &\sum\limits_{j = 1}^N {{E_j}\left( {{c_{1j}}, \cdots, {c_{Nj}}} \right)} =\notag \\ &\quad\ \begin{cases} -\infty, &{c_{jj}} = 0~\mbox{且}~ \exists i \ne j, \\ &{\rm{s}}{\rm{.t}}{\rm{. }}~~{c_{ij}}=1, ~i \in \{ 1, \cdots, N\} \\ & \mbox{或}~ \exists m, ~h_1\in {{{p}}_m}, ~{{{h}}_2} \in {{{p}}_m}, \\ & {\rm{s}}{\rm{.t}}{\rm{.}}~~ {c_{{h_1}j}}\oplus {c_{{h_2}j}} = 1, ~m \in \{ 1, \cdots , M\}\\[2mm] 0, &\mbox{其他} \end{cases} \end{align} $
(11) 则聚类目标函数变为式 (12).
$ \begin{align} T\left( C \right) =&\ \sum\limits_{{c_i}_j} {{S_{ij}}{c_{ij}}} \ +\sum\limits_{i = 1}^N {{I_i}\left( {{c_{i1}}, \cdots, {c_{iN}}} \right)} +\notag \\[2mm] &\ \sum\limits_{j = 1}^N {{E_j}\left( {{c_{1j}}, \cdots, {c_{Nj}}} \right)} \end{align} $
(12) 2.3 目标函数求解
聚类目标函数 (12) 求解是一个NP-hard寻优过程, 目前有效的求解方法是利用最大和 (max-sum) 置信传播算法求解出最优解.置信传播算法将全局函数表示为由变量节点、函数节点以及函数节点和变量节点之间的邻接所构成的因子图, 通过在变量节点和函数节点之间传递标量信息实现置信度最大化, 最终实现全局函数的最小化[16-17].变量节点 $x$ 向函数节点 $f$ 的发送的标量信息 ${{\rm{\mu}}_{x \to f}}\left(x\right)$ 如式 ${(13)}$ 所示[16]:
$ \begin{align} {{{\mu }}_{x \to {f}}}\left( x \right) = \mathop \sum \limits_{\left\{ {f'|f{{'}} \in {{ne}}\left( x \right) \setminus f} \right\}} {{{\mu }}_{f \to {x}}}\left( x \right) \end{align} $
(13) 式中, $ne(x)$ 为与变量节点 $x$ 相邻接的所有函数节点所构成的集合, ${{{\mu}}_{f\to{{x}}}}\left(x\right)$ 为函数节点 $f$ 向变量节点 $x$ 的发送的标量信息.由式 (13) 可知变量 $x$ 到函数 $f$ 的标量信息为该变量所有其他邻接函数节点发送给该变量的标量信息之和.
对函数节点向变量节点的发送的标量信息 ${{{\mu }}_{{{f}} \to {{x}}}}\left( x \right)$ 有[16-17]:
$ \begin{align} {\mu _{f \to x}}(x) =&\ \mathop {\max }\limits_{{x_1}, \cdots , {x_k}} \bigg[{f(x, {x_1}, \cdots, {x_k})} +\notag\\[2mm] & \ {\sum\limits_{\left\{ {x'|x' \in ne(f)\backslash x} \right\}} {{\mu _{x' \to f}}\left( x \right)} } \bigg] \end{align} $
(14) 式中, $ne(f)$ 为与函数节点 $f$ 相邻接的所有变量节点所构成的集合.由式 (14) 可知函数节点 $f$ 到变量 $x$ 节点的标量信息为全体邻接变量节点的发送至本函数节点标量信息和函数节点自身信息累加的最大值[18]. max-sum置信传播算法的具体内容可参见文献[16-17].
聚类目标函数 $T(C)$ 的因子图如图 1所示.其中矩形框表示函数节点, 分别和式 (7)、式 (8)、式 (11) 所示的函数相对应.圆形框表示变量节点, 即函数变量 $c_{ij}$ .变量节点和函数节点之间的信息传递如图 2所示.其中 $\rho_{ij}$ 和 $\beta_{ij}$ 为变量节点 $c_{ij}$ 向函数节点 $E_j$ , $I_i$ 所发送的信息 (变量节点 $c_{ij}$ 向函数节点 $s(i, j)$ 发送的信息为0, 图中未列出). $\alpha_{ij}$ , $\eta_{ij}$ , $s(i, j)$ 分别为函数节点 $E_j$ , $I_i$ , $S_{ij}$ 向变量节点 $c_{ij}$ 所发送的信息.
由于变量节点只取0和1两个值, 因此节点间传播的标量信息只需考虑这两种取值情况下的差值[12-13], 即:
$ \begin{align*} &\rho_{ij}=\rho_{ij}(c_{ij}=1)-\rho_{ij}(c_{ij}=0)\\[1mm] &\alpha_{ij}=\alpha_{ij}(c_{ij}=1)-\alpha_{ij} (c_{ij}=0)\\[1mm] &\beta_{ij}=\beta_{ij}(c_{ij}=1)-\beta_{ij}(c_{ij}=0)\\[1mm] &\eta_{ij}=\eta_{ij}(c_{ij}=1)-\eta_{ij}(c_{ij}=0) \end{align*} $
对于变量节点 $c_{ij}$ 至函数节点 $E_j$ 的信息 $\rho_{ij}$ , 至函数节点 $I_i$ 的信息 $\beta_{ij}$ , 由式 (13) 分别有:
$ \beta_{ij}=\alpha_{ij}+s(i, j) $
(15) $ \rho_{ij}=\eta_{ij}+s(i, j) $
(16) 函数节点 $I_i$ 到变量节点 $c_{ij}$ 的信息 $\eta_{ij}$ 和相邻节点之间的信息关系如图 3所示.
图 3 $\eta_{ij}$ 与其相关信息关系图Fig. 3 Relationship among $\eta_{ij}$ and its correlative message根据式 (14) 和图 3有 (具体推导详见附录A):
$ \begin{align} &\eta_{ij}=\eta(1)-\eta(0)=-\mathop {\max }\limits_{t \ne j} \left( {{\beta _{it}}} \right) \end{align} $
(17) 函数节点 $E_j$ 到变量节点 $c_{ij}$ 的信息 $\alpha_{ij}$ 和相邻节点之间的信息关系如图 4所示.由于 $\alpha_{ij}$ 求解与 $c_{ij}$ 在因子图中的位置以及数据点 $i$ , $j$ 和同类集之间的关系有关, 因此需要按照不同的情况予以讨论.同理, 根据式 (14) 可以推导出 $\alpha_{ij}$ 与相关信息的关系, 如式 (18) 所示 (其推导过程详见附录A).
图 4 $\alpha_{ij}$ 与其相关信息关系图Fig. 4 Relationship among $\alpha_{ij}$ and its correlative message在式 (18) 中, $p^i$ , $p^j$ 分别表示数据点 $i$ , $j$ 所在的同类集.
$ {\small \begin{align} {\alpha _{ij}} = \begin{cases} \min \left[{{\rho _{jj}} + \mathop \sum \limits_{k \in \bar P\backslash i, j} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P} \max \left[ {\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], 0} \right], \quad i \ne j, \ {\rm{ }}i \in \bar P{\rm{ }}, \ {\rm{ }}j \in \bar P\\[4mm] \min \left[{\mathop \sum \limits_{k \in {p^j}} {\rho _{kj}} + \mathop \sum \limits_{k \in \bar P\backslash i} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P - {p^j}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], 0} \right], \quad i \ne j, \ {\rm{ }}i \in \bar P{\rm{ }}, \ {\rm{ }}j \in {p^j}{\rm{ }}\\[4mm] \min \left[{\mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}} + {\rho _{jj}} + \mathop \sum \limits_{k \in \bar P\backslash j} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}}} \right], \\ \quad i \ne j, \ i \in {p^i}, \ {\rm{ }}j \in \bar P\\[4mm] \min \left[{\mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}} + \mathop \sum \limits_{k \in \bar P} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], 0} \right], \\ \quad i \ne j, \ i \in {p^i}, \ j \in {p^j}{\rm{ }}, \ {\rm{ }}{p^i} = {p^j}\\[4mm] \min \left[{\mathop \sum \limits_{k \in {p^j}} {\rho _{kj}} + \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}} + \mathop \sum \limits_{k \in \bar P} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], 0} \right], \\ \quad i \ne j, \ {\rm{ }}i \in {p^i}, \ j \in {p^j}, \ {\rm{ }}{p^i} \ne {p^j}\\[3mm] \mathop \sum \limits_{k \in {p^j}\backslash i} {\rho _{kj}} + \mathop \sum \limits_{k \in \bar P} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P - {p^j}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], \quad i = j, \ j \in {p^j}\\[3mm] \mathop \sum \limits_{k \in \bar P\backslash i} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P} \max \left[ {\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], \quad i = j, \ j \in \bar P \end{cases} \end{align}} $
(18) 为避免震荡现象, 引入阻尼因子对信息进行更新, 即对任意信息 $\mu$ , 按式 (19) 进行更新:
$ \begin{align} \mu = \lambda {\mu _{old}} + (1 - \lambda ){\mu _{new}} \end{align} $
(19) 其中, $\lambda$ 为阻尼因子, 取值范围在0~1之间.
2.4 分配矩阵计算
数据点 $i$ 类中心点 $c_i$ 是由接收信息总量最大的变量节点 $c_{ij}$ 节点所对应的 $j$ 来确定, 其计算按式 (20) 进行
$ \begin{align} {c_i} = \arg \max\limits_j \left( {{\alpha_{ij}} + {\eta _{ij}} + s(i, j)} \right) \end{align} $
(20) 由式 (16) 有
$ \begin{align} {c_i} = \arg\max\limits_j \left( {{\alpha_{ij}} + {\rho _{ij}}} \right) \end{align} $
(21) 根据式 (15)~(17) 有
$ \begin{align} {\rho _{ij}} = s(i, j) - \mathop {\max }\limits_{t \ne j} \left[ {{\alpha _{it}} + s(i, t)} \right] \end{align} $
(22) 由式 (22) 可知, $\rho_{ij}$ 仅与 $\alpha_{ij}$ 和 $s(i, j)$ 有关; 由式 (18) 可知 $\alpha_{ij}$ 仅与 $\rho_{ij}$ 有关.结合式 (21)、式 (22) 和式 (18) 可知只需迭代计算 $\alpha_{ij}$ 和 $\rho_{ij}$ 即可.对照式 (1) 和式 (2), $\rho_{ij}$ 和 $\alpha_{ij}$ 即为HCSAP的吸引度和归属度.
3. 实验及结果分析
3.1 聚类评价参数及相关设置
为验证HCSAP算法的有效性, 利用人工数据集及部分真实数据集对HCSAP算法进行了聚类测试, 并与基于距离的近邻反射传播半监督聚类SAP[5]、SSAP[6], 以及基于约束的MPCK-MEANS[13]、DSCA[14]聚类算法进行比较.
聚类数据均进行归一化处理.聚类实验前, 先按照一定的抽取率以均匀随机的方式从聚类数据中抽取一定数量的样本, 然后由这些样本的标签来构造算法中所需要的同类集和must-link成对约束. SAP、SSAP、HCSAP聚类算法中阻尼因子取值为0.9, 迭代次数取为100, 聚类初始时, 吸引度和归属度均初始化为0. MPCK-MEANS和DSCA聚类的类数取HCSAP聚类数, 其他相关参数设置与文献[13-14]相同.
每个聚类测试运行10次, 取平均值和方差进行比较.同时以HCSAP为参照, 与对比算法进行成对 $t$ 检验.聚类的评价指标采用成对 $F$ 评测指标和Pure指标, 其中成对 $F$ 评测指标计算如式 (23) 所示.
$ \begin{align} F = \frac{{2 \times x \times y}}{{ {x + y} }} \end{align} $
(23) 式中, $x$ 为准确率 (Precision), $y$ 为召回率 (Recall), 计算分别按式 (24) 和式 (25) 进行.
$ {{x}} = \dfrac{{{\rm{pairs \ correctly \ predicted \ in \ same \ cluster}}}}{{{\rm{total \ pairs \ predicted \ in \ same \ cluster}}}} $
(24) $ {{y}} = \dfrac{{{\rm{pairs \ correctly \ predicted \ in \ same \ cluster}}}}{{{\rm{total \ pairs \ in \ same \ cluster}}}} $
(25) Pure指标按式 (26) 进行计算.
$ \begin{align} {{purity}}(\Omega, \Psi ) = \frac{1}{N}\sum\limits_k {\mathop {\max }\limits_j } \left| {{\omega _k} \cap {\psi_j}} \right| \end{align} $
(26) 式中, $\Omega=\{\omega_1, \cdots, \omega_K \}$ 为分类集合, $N$ 为样本数据个数, $\Psi=\{\psi_1, \cdots, \psi_N\}$ , 为聚类集合, $\omega_k$ 为表示第 $k$ 类的数据点集合.
实验环境为戴尔XPS 8700-r398型台式电脑, 配置为Visual Studio 2012 Ultimate, Windows 7 64位操作系统, Intel酷睿i7-4790 3.4 GHz处理器, 16 GB DDR3 1 600 MHz内存.
3.2 人工数据集实验
随机产生200个二维数据, 数据集横坐标均匀分布在0~0.1之间, 其中100数据点纵坐标均匀分布在0~1.5之间, 另外100个数据点纵坐标均匀分布在2~3.5之间. SAP、SSAP、HCSAP聚类参数 (Preference) 设为相似性矩阵中值的20倍.
图 5 (a)和图 5 (b) 给出了抽取率为10 %时的SAP和HCSAP一次聚类结果.图中上三角和下三角分别为随机抽取的20个数据所构成两个同类集.即所有上三角的数据为一类, 所有下三角数据为一类.从图 5 (a)的SAP聚类结果来看, 下三角同类数据点都聚在一类中, 这与约束是一致的.但所有上三角数据点并没有聚为一类.根据聚类结果, 图中右上角中的一个被选为类中心点的上三角数据点和其他上三角点分属两个不同的类别, 因此聚类结果和先验信息并不一致.图 5 (b)给出了HCSAP聚类结果.上三角数据点被聚为一类, 下三角数据点也被聚为一类, 因此聚类结果与先验信息一致.可见采用基于同类约束的HCSAP半监督聚类方法, 能够保证聚类结果和同类集先验信息一致.
表 2列出了各算法在抽取率分别为0 %~50 %时10次聚类结果的 $F$ -评测指标和Pure指标的平均值、方差和成对 $t$ 检验值.抽取率为0时, SAP、SSAP、HCSAP都退化为近邻反射传播聚类算法. MPCK-mean、DSCA算法退化为K-means算法, 从结果可以看出AP聚类效果好于K-means.在引入先验信息后, HCSAP聚类结果的聚类F-measure参数与Pure参数即优于基于距离的SAP和SSAP算法, 也优于基于约束的MPCK-mean和DSCA算法.
表 2 人工数据上的聚类结果参数对比Table 2 Performance comparison on man-made datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 72.12 72.12 72.12 70.31 69.3 56.50 56.50 56.50 53.43 55.0 0 std (0) (0) (0) (1.3) (3.6) (0) (0) (0) (1.1) (2.1) p-value - - - 4.2E-3 6.6E-3 - - - 1.8E-1 3.4E-1 Mean 87.24 82.74 80.22 85.27 81.66 80.47 72.41 70.50 77.39 75.4 10 std (6.6) (4.7) (0.8) (5.2) (9.2) (1.7) (1.1) (2.4) (2.1) (3.7) p-value - 3.1E-2 (+) 2.2E-5 (+) 9.7E-2 6.3E-3 (+) - 3.9E-2 (+) 4.1E-5 (+) 6.4E-2 6.8E-2 Mean 96.15 80.45 81.78 90.00 88.6 95.75 72.57 73.66 90.41 76.8 20 std (1.0) (1.6) (1.8) (4.1) (4.5) (4.0) (1.6) (2.7) (0.5) (1.4) p-value - 9.4E-4 (+) 7.8E-5 (+) 9.2E-3 (+) 9.2E-3 (+) - 1.7E-7 (+) 2.3E-6 (+) 1.4E-2 (+) 7.5E-6 (+) Mean 96.24 91.24 92.47 90.36 91.33 97.58 89.00 85.74 90.06 89.6 30 std (2.0) (4.1) (5.1) (0.8) (1.6) (0.2) (6.6) (4.1) (0.2) (2.8) p-value - 4.9E-2 (+) 5.1E-2 8.4E-3 (+) 7.4E-3 (+) - 3.4E-3 (+) 9.5E-8 (+) 1.6E-2 (+) 4.7E-4 (+) Mean 96.66 88.57 87.98 90.21 89.2 97.35 88.65 86.97 90.33 90.5 40 std (1.3) (3.0) (2.7) (0.2) (4.5) (2.0) (1.2) (0.9) (0.5) (7.7) p-value - 5.7E-3 (+) 1.1E-3 (+) 6.6E-3 (+) 3.9E-3 (+) - 1.1E-4 (+) 2.4E-7 (+) 1.8E-2 (+) 7.1E-3 (+) Mean 98.05 90.34 88.84 90.70 90.8 98.25 89.65 90.45 88.87 90.0 50 std (0.2) (7.1) (1.4) (0.6) (2.3) (0.2) (2.8) (9.6) (0.7) (3.4) p-value - 5.1E-2 7.2E-4 (+) 9.0E-5 (+) 1.4E-4 (+) - 42E-4 (+) 3.7E-7 (+) 8.4E-3 (+) 6.7E-3 (+) 注:表中p-value为5 %显著性水平下的 $t$ 检验值, "+"表示HCSAP在5 %显著性水平下优于对比聚类算法."-"表示在5 %显著性水平下HCSAP劣于对比聚类算法.粗体字表示对比较优者 (下同). 3.3 标准数据集实验
从UCI数据库中选取Optdigit, Ionosphere, Iris, Pendigits和Letter-recognition数据集中的I, J, L字母数据子集1, 以及KEEL网站2中的glass, wine, wdbc数据集进行聚类实验. 表 3中给出了这些数据集的相关信息和聚类参数 (Preference) 设置.表中 $Mid$ 是相似性矩阵中值.
1 http://archive.ics.uci.edu/ml/-datasets.html
表 3 实验数据集Table 3 Dataset used in experimentItem Number of instance Dimension Class Preference Optdigit 1 797 64 10 $1\times Mid$ Iris 150 4 3 $3\times Mid$ Ionosphere 351 34 2 $10\times Mid$ Letter recogni- 2 241 16 3 $1\times Mid$ tion {I, J, L} Pendigits 3 498 16 10 $1\times Mid$ glass 214 9 6 $5\times Mid$ wine 178 13 3 $5\times Mid$ wdbc 768 8 2 $50\times Mid$ Optdigit数据集聚类结果的F-measure、Pure相关参数统计结果如表 4所示.从结果来看, 除了在20 %抽取率时, HCSAP聚类结果的F-measure参数不是最优, 但在其他抽取率时相关参数的均值都是最优的.同时Pure结果均优于其他算法.
表 4 Optdigit数据集上的聚类结果对比Table 4 Performance comparison on Optdigit datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 22.35 22.35 22.35 19.14 20.61 12.57 12.57 12.57 10.68 11.46 0 std (0) (0) (0) (1.25) (3.87) (0) (0) (0) (1.6) (0.9) p-value - - - 4.3E-3 4.9E-2 - - - 4.1E-2 (+) 4.8E-2 Mean 31.86 30.03 29.30 27.98 30.41 18.97 17.75 15.34 14.68 16.35 10 std (4.69) (1.30) (2.47) (1.50) (4.94) (5.02) (5.92) (6.1) (5.7) (2.2) p-value - 3.1E-1 3.3E-1 2.6E-1 5.1E-1 - 2.7E-1 6.1E-1 1.4E-1 9.9E-2 Mean 42.57 43.15 44.63 40.55 41.55 27.10 27.71 27.96 27.30 24.63 20 std (7.4) (8.01) (6.91) (7.65) (9.52) (9.00) (3.36) (4.86) (7.96) (8.14) p-value - 2.2E-1 6.6E-1 1.0E-1 2.9E-1 - 5.7E-1 6.7E-1 4.3E-1 7.4E-2) Mean 54.41 52.5 51.23 49.87 52.44 36.61 35.78 34.79 30.76 31.87 30 std (9.02) (2.01) (4.31) (2.44) (3.75) (2.67) (0.79) (6.6) (8.2) (7.8) p-value - 2.6E-1 1.7E-1 4.6E-2 (+) 5.7E-1 - 4.3E-1 8.7E-2 4.4E-2 (+) 2.5E-2 (+) Mean 62.67 61.35 61.22 59.57 61.24 45.85 44.46 45.20 41.85 40.27 40 std (2.39) (1.71) (1.6) (4.21) (8.34) (0.86) (3.12) (4.20) (7.14) (9.48) p-value - 4.0E-1 4.3E-1 2.9E-1 1.6E-1 - 1.7E-1 2.7E-1 7.7E-2 2.1E-2 (+) Mean 71.75 68.84 68.8 69.54 69.33 56.09 52.69 51.27 48.62 50.11 50 std (9.58) (6.32) (9.96) (8.47) (10.20) (2.45) (4.79) (2.70) (5.47) (5.50) p-value - 2.4E-1 2.4E-11 8.1E-2 9.8E-2 - 1.4E-2 (+) 1.1E-1 2.5E-3 (+) 5.8E-2 各算法在Optdigit数据集上平均运行用时如图 6所示.从图 6可以看出, 以AP为基础的半监督聚类方法速度要快于以K-MEANS为基础的半监督聚类方法.此外, 从迭代方程 (1) 和 (22) 来看, AP聚类和HCSAP聚类的吸引度迭代方程是相同的.从迭代方程 (2) 和 (18) 来看, 当 $i=j$ 时AP聚类的 $\alpha(i, j)$ 迭代操作为 $n-1$ 次max运算和 $n-2$ 次加法运算 ( $n$ 为数据点个数), 而在HCSAP中 $\alpha(i, j)$ 迭代中首先要进行检索操作, 以便进行不同的迭代.以 $j\in{p^j}$ 为例, 在迭代方程中, 运算量为 $\left|{\overline{P}}\right|+\left|{{p^j}}\right|$ 次max运算 ( $\left|\cdot\right|$ 表示集合元素个数) 和 $n-2$ 次加法运算.因 $\left|{\overline{P}}\right|+\left|{{p^j}}\right| < n-1$ , 因此HCSAP的max运算次数少于AP.
不过HCSAP增加了数据在同类集中的检索操作.同理在当 $i\ne{j}$ 时也存在相同的情况.由于检索运算时间一般少于加法运算, 且max运算复杂度要大于加法运算, 因此相比于AP而言, HCSAP最多只是增加了检索运算. AP的时间复杂度为 ${\rm O}(n^2)$ , HCSAP时间复杂度不超过 $\left({n\sum\nolimits_v{\left|{{p_v}}\right|}}\right)/2+{n^2}$ .因此HCSAP聚类时间只是略多于AP, 实验结果也表明了这一点. SAP和SSAP相比于AP聚类算法时间也较长, 主要是在相似度矩阵调整上进行了一些额外的操作, 因此运算时间要多于AP.此外由于SSAP增加了虚点, 运算量也有所增加, 因此运算时间要多于SAP算法.在空间复杂度方面, 相比于AP而言HCSAP增加了同类约束集的存储开销, 但这个存储开销要少于SAP和SSAP算法中的must-link成对约束的存储开销.
表 5 Iris数据集的聚类结果对比Table 5 Performance comparison on Iris datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 61.87 61.87 61.87 56.27 55.38 55.33 55.33 55.33 52.61 53.70 0 std (0) (0) (0) (3.1) (3.6) (0) (0) (0) (2.30) (4.81) p-value - - - 1.4E-2 2.2E-2 - - - 1.6E-1 4.8E-1 Mean 73.36 72.93 72.55 71.84 69.57 75.60 56.53 55.22 60.77 58.45 10 std (2.69) (0.93) (1.21) (6.40) (3.72) (5.3) (0.87) (4.11) (2.57) (12.72) p-value - 1.5E-4 (+) 1.3E-4 (+) 5.3E-4 (+) 2.2E-4 (+) - 1.3E-3 (+) 1.4E-3 (+) 5.6E-3 (+) 4.2E-2 (+) Mean 79.04 79.78 76.99 81.21 74.31 75.33 69.11 66.22 64.21 70.40 20 std (3.22) (8.02) (5.90) (8.3) (6.61) (7.33) (12.10) (18.9) (14.1) (11.23) p-value - 2.8E-1 1.4E-1 8.2E-1 5.4E-3 - 2.7E-1 2.3E-1 5.4E-1 9.1E-1 Mean 88.46 80.33 81.24 80.74 75.33 81.33 72.22 71.25 72.11 69.44 30 std (1.75) (9.15) (9.47) (4.4) (10.1) (2.91) (12.15) (11.41) (13.15) (10.9) p-value - 2.1E-1 3.4E-1 1.1E-2 1.2E-2 - 2.3E-1 2.0E-1 2.8E-1 1.1E-1 Mean 94.72 89.62 88.25 85.74 84.27 92.93 84.40 84.00 81.23 83.78 40 std (3.64) (3.79) (4.8) (5.9) (5.6) (5.77) (6.95) (8.3) (7.9) (9.1) p-value - 1.5E-1 4.6E-2 (+) 4.9E-1 5.9E-1 - 1.7E-1 1.1E-1 1.4E-1 2.4E-1 Mean 94.43 92.38 93.50 90.22 89.01 94.44 88.22 87.20 86.33 90.01 50 std (0.39) (1.39) (2.0) (7.1) (5.1) (0.03) (5.00) (6.89) (6.12) (10.88) p-value - 1.0E-1 1.7E-1 5.5E-1 6.4E-1 - 1.5E-1 1.2E-1 2.7E-1 1.4E-1 表 6 Ionosphere数据集上的聚类结果对比Table 6 Performance comparison on Ionosphere datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 51.96 51.96 51.96 45.89 46.31 40.35 40.35 40.35 43.48 41.25 0 std (0) (0) (0) (5.2) (3.4) (0) (0) (0) (2.50) (1.31) p-value - - - 7.3E-1 6.9E-1 - 4.4E-1 5.2E-1 1.3E-1 2.3E-1 Mean 55.24 56.74 57.30 58.21 54.21 58.21 59.38 57.66 55.24 58.00 10 std (2.45) (7.87) (1.2) (7.2) (3.6) (7.32) (2.78) (7.27) (6.17) (5.48) p-value - 3.5E-2 (-) 4.8E-2 (-) 5.4E-1 7.9E-1 - 8.2E-1 6.3E-1 5.2E-1 4.5E-1 Mean 56.45 61.13 60.34 54.29 55.12 63.41 64.12 64.30 62.34 61.25 20 std (1.97) (2.36) (1.90) (4.87) (3.57) (5.79) (3.18) (5.54) (7.53) (4.74) p-value - 5.40E-3 (-) 3.47E-2 (-) 4.4E-1 5.1E-1 - 2.8E-1 3.5E-1 6.4E-1 4.1E-1 Mean 66.61 61.16 65.14 57.02 59.54 63.74 67.20 61.42 61.28 60.11 30 std (3.25) (5.47) (3.32) (5.42) (4.14) (5.20) (1.44) (8.54) (3.15) (7.21) p-value - 2.8E-1 4.2E-1 3.3E-1 2.4E-1 - 1.9E-1 2.9E-1 1.6E-1 1.7E-1 Mean 67.61 71.68 68.50 64.71 69.87 62.66 64.04 57.99 60.34 61.23 40 std (4.23) (3.03) (1.20) (4.56) (1.57) (8.17) (7.24) (4.8) (1.36) (5.4) p-value - 2.4E-2 (-) 3.7E-2 (-) 1.7E-1 5.6E-1 - 2.5E-1 3.6E-1 2.2E-1 1.4E-1 Mean 84.16 83.17 80.26 80.66 84.78 72.53 71.33 72.55 70.21 69.88 50 std (6.12) (4.87) (2.80) (2.69) (4.31) (5.60) (7.53) (5.33) (2.42) (4.69) p-value - 3.6E-1 3.4E-1 4.7E-1 2.1E-1 - 1.9E-1 3.9E-1 2.2E-1 1.0E-1 表 7 Letter-recognition {I, J, L}上的聚类结果对比Table 7 Performance comparison on Letter-recognition datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 49.87 49.87 49.87 41.30 42.33 33.33 33.33 33.33 31.54 30.36 0 std (0) (0) (0) (1.9) (4.1) (0) (0) (0) (2.5) (3.1) p-value - - - 5.7E-2 6.9E-2 - - - 1.7E-1 1.0E-1 Mean 54.42 55.01 54.36 55.11 57.21 39.00 38.10 40.23 39.98 40.05 10 std (8.90) (2.63) (5.7) (6.4) (3.89) (8.08) (2.78) (1.4) (2.0) (3.7) p-value - 6.2E-1 2.1E-1 4.8E-1 1.2E-1 - 2.3E-1 5.6E-1 7.4E-1 6.1E-1 Mean 59.47 52.01 51.69 57.20 55.31 42.66 35.33 34.88 37.90 35.87 20 std (1.92) (5.73) (4.8) (6.8) (5.0) (9.57) (7.26) (5.8) (3.2) (2.8) p-value - 4.2E-2 (+) 3.2E-2 (+) 1.1E-1 3.1E-1 - 4.9E-2 2.3E-2 4.7E-2 2.6E-2 Mean 67.90 65.36 66.30 64.87 60.45 52.66 50.00 49.68 50.33 51.74 30 std (0.41) (6.44) (3.2) (5.6) (4.9) (1.84) (1.54) (1.74) (2.53) (3.40) p-value - 2.6E-1 3.0E-1 1.7E-1 2.6E-1 - 2.3E-1 1.2E-1 2.9E-1 5.4E-1 Mean 77.05 72.97 73.33 71.4 70.24 64.66 60.00 59.40 58.67 51.77 40 std (2.00) (4.43) (1.5) (2.6) (2.4) (8.17) (4.26) (7.26) (8.11) (14.25) p-value - 3.3E-1 4.2E-1 1.1E-1 1.5E-1 - 3.4E-1 2.9E-1 4.1E-1 5.3E-1 Mean 84.16 83.17 84.12 83.00 81.47 73.33 71.33 70.11 68.25 67.49 50 std (4.55) (7.41) (5.4) (4.9) (4.4) (2.62) (7.53) (5.1) (7.6) (5.3) p-value - 4.9E-1 5.0E-1 2.3E-1 2.3E-1 - 3.3E-1 2.8E-1 1.0E-1 4.4E-2 (+) 表 8 Pendigits数据集的聚类结果对比Table 8 Performance comparison on Pendigits datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 19.23 19.23 19.23 17.21 16.32 11.20 11.20 11.20 9.79 9.64 0 std (0) (0) (0) (1.42) (2.51) (0) (0) (0) (0.25) (0.36) p-value - - - 9.4E-3 (+) 2.8E-3 (+) - - - 3.9E-2 (+) 2.8E-2 (+) Mean 27.40 23.17 24.65 24.68 21.97 16.72 13.75 12.99 13.58 11.95 10 std (1.38) (8.62) (7.64) (9.17) (4.11) (5.03) (3.15) (2.87) (2.77) (1.44) p-value - 2.3E-1 5.6E-2 2.8E-1 5.8E-2 - 4.1E-1 9.6E-2 6.7E-1 6.1E-1 Mean 38.66 35.19 34.67 33.74 34.21 36.14 25.58 24.71 21.95 27.64 20 std (0.88) (3.67) (4.25) (5.50) (6.67) (3.13) (8.79) (3.34) (5.61) (4.13) p-value - 5.6E-1 2.4E-1 2.7E-1 3.1E-1 - 8.3E-3 2.3E-3 9.8E-4 1.9E-3 Mean 60.54 57.56 55.82 51.64 56.83 46.19 43.08 40.27 39.87 41.56 30 std (9.90) (0.26) (1.13) (4.21) (6.57) (0.54) (2.86) (3.41) (4.12) (3.49) p-value - 8.3E-1 5.3E-1 5.6E-2 6.6E-1 - 5.8E-1 4.1E-1 8.6E-2 2.9E-1 Mean 68.49 62.12 63.77 60.16 62.57 55.46 48.51 44.21 39.48 41.67 40 std (1.28) (5.29) (6.84) (3.46) (4.57) (6.09) (1.93) (1.53) (4.85) (3.34) p-value - 5.6E-1 6.8E-1 4.9E-1 1.4E-1 - 4.6E-2 (+) 5.3E-3 (+) 2.1E-4 (+) 9.4E-3 (+) Mean 75.75 66.30 67.38 67.22 64.14 65.23 53.60 54.69 55.21 53.96 50 std (4.58) (8.38) (7.52) (7.31) (5.63) (2.58) (6.82) (7.39) (4.61) (9.42) p-value - 6.1E-2 7.6E-1 4.9E-1 2.0E-1 - 3.8E-2 (+) 4.2E-2 (+) 1.6E-2 (+) 6.4E-3 (+) 表 9 glass数据集的聚类结果对比Table 9 Performance comparison on glass datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 31.02 31.02 31.02 28.66 27.14 31.66 31.66 31.66 28.51 30.69 0 std (0) (0) (0) (2.80) (3.74) (0) (0) (0) (1.90) (2.45) p-value - - - 2.63E-1 1.77E-1 - - - 2.1E-1 2.6E-1 Mean 37.24 35.85 35.62 31.89 33.57 38.00 38.00 37.15 35.46 34.76 10 std (8.90) (3.17) (4.66) (5.78) (9.51) (8.08) (2.78) (3.64) (5.21) (4.23) p-value - 6.0E-1 3.4E-1 1.9E-1 2.4E-1 - 8.4E-1 5.6E-1 3.6E-1 3.1E-1 Mean 40.98 37.80 35.70 36.44 37.15 42.66 35.33 34.36 31.93 32.19 20 std (0.06) (0.02) (0.08) (1.62) (3.48) (9.57) (7.26) (6.19) (8.42) (2.96) p-value - 1.1E-1 6.4E-2 8.3E-2 4.8E-1 - 5.4E-2 4.9E-2 (+) 2.5E-2 (+) 3.4E-2 (+) Mean 46.05 43.32 44.22 40.35 45.11 70.87 54.52 55.21 52.94 57.14 30 std (0.15) (3.21) (3.90) (5.44) (7.16) (1.50) (6.36) (4.83) (8.91) (7.88) p-value - 2.9E-1 5.2E-1 9.7E-2 4.5E-1 - 4.6E-2 (+) 2.0E-2 (+) 9.4E-3 (+) 5.6E-2 Mean 53.23 47.71 46.25 42.18 47.84 80.06 61.06 64.37 59.81 60.56 40 std (1.46) (5.89) (4.77) (4.65) (7.21) (5.00) (7.27) (8.36) (7.24) (4.98) p-value - 1.8E-1 1.3E-1 7.6E-2 5.5E-1 - 5.7E-2 1.7E-1 8.7E-3 (+) 7.68E-2 Mean 54.67 50.70 51.28 49.57 51.14 79.63 64.02 61.44 62.37 59.87 50 std (7.43) (4.98) (6.40) (7.15) (8.44) (8.83) (5.42) (6.48) (7.21) (9.18) p-value - 1.6E-1 3.6E-1 7.4E-2 6.1E-1 - 5.0E-2 (+) 4.4E-2 (+) 4.5E-2 (+) 6.9E-3 (+) 表 10 wine数据集的聚类结果对比Table 10 Performance comparison on wine datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 60.21 60.21 60.21 54.39 57.82 70.54 70.54 70.54 64.87 61.49 0 std (0) (0) (0) (5.67) (4.10) (0) (0) (0) (5.10) (6.54) p-value - - - 2.9E-1 4.6E-1 - - - 1.3E-1 9.3E-2 Mean 79.16 68.98 69.33 65.47 67.26 84.94 72.36 73.66 75.19 70.58 10 std (5.450) (3.82) (5.44) (8.21) (4.94) (8.35) (5.26) (5.87) (4.24) (6.29) p-value - 6.3E-3 (+) 9.2E-4 (+) 6.1E-3 (+) 8.1E-2 (+) - 4.7E-2 (+) 4.9E-2 (+) 6.7E-2 8.1E-3 (+) Mean 81.36 71.82 69.88 68.15 60.47 84.83 73.88 71.20 69.64 65.88 20 std (3.65) (5.49) (5.40) (8.14) (6.47) (8.22) (4.55) (6.88) (7.52) (10.37) p-value - 7.4E-2 4.8E-2 1.3E-1 9.1E-2 - 1.5E-1 8.3E-2 7.2E-2 4.3E-2 (+) Mean 84.78 83.27 80.31 81.55 82.41 92.06 89.40 85.94 90.31 88.49 30 std (2.93) (5.21) (6.40) (3.70) (7.52) (1.68) (6.34) (5.80) (1.23) (3.54) p-value - 1.8E-1 1.1E-1 3.4E-1 4.4E-1 - 1.7E-1 8.3E-2 4.6E-1 9.7E-2 Mean 90.22 84.24 80.64 81.47 72.63 95.06 89.66 88.33 90.27 87.92 40 std (2.81) (3.51) (4.36) (1.42) (0.99) (1.51) (5.82) (6.42) (8.66) (9.11) p-value - 4.0E-2 (+) 2.2E-3 (+) 3.6E-2 (+) 9.4E-3 (+) - 1.3E-1 8.4E-2 5.2E-2 4.3E-2 (+) Mean 89.76 86.68 85.85 80.74 81.69 88.82 85.74 85.63 84.22 80.75 50 std (1.99) (4.99) (6.41) (6.28) (7.11) (2.62) (7.53) (8.90) (7.24) (9.11) p-value - 2.7E-1 2.0E-1 5.7E-2 3.3E-1 - 2.7E-1 1.1E-1 3.4E-1 2.1E-1 表 11 wdbc数据集的聚类结果对比Table 11 Performance comparison on wdbc datasetSample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 52.31 52.31 52.31 48.42 47.49 55.74 55.74 55.74 51.78 52.69 0 std (0) (0) (0) (1.10) (1.67) (0) (0) (0) (0.62) (0.37) p-value - - - 4.5E-2 (+) 3.1E-2 (+) - - - 4.8E-2 (+) 5.7E-2 Mean 66.35 50.72 48.39 51.46 49.21 61.39 47.80 47.92 44.91 51.68 10 std (13.38) (1.42) (2.82) (2.6) (5.06) (11.73) (3.50) (6.41) (17.46) (14.25) p-value - 1.5E-1 9.2E-2 3.4E-1 1.1E-1 - 1.2E-1 2.4E-1 4.2E-1 2.9E-1 Mean 74.27 66.58 67.24 64.21 60.37 72.16 61.16 60.58 57.26 59.34 20 std (13.78) (14.87) (11.35) (15.87) (9.58) (14.45) (17.51) (15.68) (11.34) (8.48) p-value - 5.0E-1 6.2E-1 9.8E-2 4.1E-1 - 4.1E-1 5.4E-1 1.2E-1 2.6E-1 Mean 85.90 59.10 58.22 57.31 56.74 84.23 52.42 50.72 48.64 51.77 30 std (0. 86) (17.4) (20.55) (8.27) (4.90) (1.26) (4.28) (5.60) (4.89) (2.77) p-value - 9.0E-03 (+) 2.5E-2 (+) 5.1E-3 (+) 6.4E-3 (+) - 7.4E-04 (+) 5.6E-5 (+) 4.9E-6 (+) 1.8E-7 (+) Mean 88.09 71.83 71.27 69.58 64.96 87.39 70.61 71.33 64.99 68.41 40 std (1.35) (8.86) (7.89) (10.54) (9.73) (3.0) (8.14) (6.64) (10.37) (12.85) p-value - 4.70E-2 (+) 2.8E-2 (+) 4.2E-3 (+) 7.7E-3 (+) - 5.3E-2 5.1E-2 4.8E-3 (+) 2.5E-2 (+) Mean 87.53 84.82 84.32 81.62 82.44 88.32 84.74 80.16 75.32 72.19 50 std (7.18) (9.02) (10.33) (8.27) (9.11) (7.80) (9.83) (8.12) (10.77) (11.65) p-value - 4.8E-2 (+) 3.4E-2 (+) 8.9E-3 (+) 7.7E-3 (+) - 4.1E-2 (+) 2.2E-2 (+) 3.6E-2 (+) 1.8E-2 (+) 在设定的参数下, AP聚类效果基本上都优于K-means聚类方法.在Ionosphere数据集上, 基于距离的SAP和SSAP方法在抽取率为10 %, 20 %, 40 %时聚类结果均优于HCSAP、MPCK-MEANS和DSCA.在Iris数据集和Letter-recognition {I, J, L}数据集中, 当同类集规模稍大时, HCSAP聚类效果总体上要优于所对比的其他算法.在Pendigits、glass、wine、wdbc这四个数据集中HCSAP在F-measure和Pure均有较大优势.
诚然在聚类结果的F-measure和Pure参数的t检验中, 由于HCSAP聚类结果和对比算法聚类结果的评价参数分布区间存在重合, 因此部分p-value值均高于5 %.但综合实验结果来看, HCSAP在保证聚类结果与同类先验信息一致的同时, 也能获得较好的聚类效果.
4. 结论与展望
综合人工数据集和标准数据集聚类实验, HCSAP作为一种基于约束的半监督聚类方法, 具有聚类结果遵循同类先验知识的特点; 在同类集规模较大时, 可以提升聚类性能; HCSAP不改变相似性度量矩阵, 保留了近邻反射传播算法可用于相似性度量不对称或不满足三角不等性的场合的优点; 在时间复杂度上, HCSAP方法与AP聚类相比增加了同类集中的数据的检索操作, 但检索操作时间与同类集中数据点的个数为线性关系, 运算时间只是略有增加; 由于同类集相比于must-link成对约束集合而言, 不存在数据重复存储的情况, 因此HCSAP在空间复杂度上要优于基于must-link成对约束的方法.
HCSAP方法只适用于同类约束, 而不像SAP和SSAP方法那样既适用于同类约束也适用于非同类约束.拓展HCSAP应用范围的一种途径是采用混合策略, 即对非同类约束采用与SAP相同的方式来处理, 将非同类约束 (即cannot-link约束) 点之间的相似度设为 $-\infty$ , 再采用HCSAP进行聚类.但该处理方法虽然能够避免cannot-link成对约束点选择对方为类中心点, 但不能排除它们选择相同的数据点作为各自的类中心点.文献[10-11]指出在聚类时实现cannot-link成对约束是一个NP-complete问题, 因此cannot-link成对约束在实际应用时受到很大限制, 难以给出一般性的方法.同样, 非同类约束也是一个NP-complete问题, 如何在近邻反射传播聚类方法中引入非同类约束进而提出一般性的方法是本文今后努力的方向.
附录A ${\boldsymbol\eta}_{\boldsymbol {ij}}$ 和 ${\boldsymbol\alpha}_{\boldsymbol {ij}}$ 迭代公式推导
证明.
对于信息 $\eta_{ij}$ , 根据图 3所给出的其与函数 ${I_i}({c_{i1}}, \cdots$ , ${c_{ij}}$ , $\cdots$ , ${c_{iN}})$ 节点、变量节点 $c_{ij}$ 以及其他邻接节点之间信息的关系以及式 (14) 有:
$ \begin{align*} &{{{\eta }}_{{{ij}}}}\left( {{{{c}}_{{ij}}}} \right) =\\ &\qquad \mathop {\max }\limits_{\left\{ {{{{c}}_{{{ik}}}}, {{k}} \ne {{j}}} \right\}} \left( {{I_i}\left( {{c_{i1}}, \cdots, {c_{ij}}, \cdots, {c_{iN}}} \right) + } \sum \limits_{{{t}} \ne {{j}}} {{{\beta }}_{{{it}}}}\left( {{c_{it}}} \right)\right)\end{align*} $
当 $c_{ij}=1$ , 根据中心点唯一性约束, 分配有效时 (即函数 $I_i$ 取值为0), 则对 $\forall {k} \ne {j}$ 时, ${c_{ik}} = 0$ .
当 $c_{ij}=0$ , 根据中心点唯一性约束, $\exists t\ne j$ , s.t. ${c_{it}}=$ $1$ , 同样分配有效时 (即函数 $I_i$ 取值为0), 则对 $\forall k \ne t$ 时, $c_{ik}$ $=0$ .
$ \begin{align*} &{\eta _{ij}}\left( 0 \right) =\\ &\qquad \mathop {\max }\limits_{\left\{ {{c_{it}} = 1, {c_{ik}} = 0, k \ne t, j} \right\}} \Bigg( {I_i}\left( {{c_{i1}}, \cdots, {c_{ij}} = 0, \cdots, {c_{iN}}} \right) +\\ &\qquad {\beta _{it}}\left( 1 \right) + \mathop \sum \limits_{v \ne t, j} {\beta _{iv}}\left( 0 \right) \Bigg) =\\ &\qquad \mathop {\max }\limits_{t \ne j} \left( {{\beta _{it}}\left( 1 \right) + \mathop \sum \limits_{v \ne j, t} {\beta _{iv}}\left( 0 \right)} \right) =\\ &\qquad \mathop {\max }\limits_{t \ne j} \left( {{\beta _{it}}\left( 1 \right)} \right) + \mathop \sum \limits_{v \ne j, t} {\beta _{iv}}\left( 0 \right) \end{align*} $
则有:
$ \begin{align*} {\eta _{ij}} =&\ {\eta _{ij}}\left( 1 \right) - {\eta _{ij}}\left( 0 \right) =\\ & \mathop \sum \limits_{t \ne j} {\beta _{it}}\left( 0 \right) - \mathop {\max }\limits_{t \ne j} \left( {{\beta _{it}}\left( 1 \right)} \right) + \mathop \sum \limits_{v \ne j, t} {\beta _{iv}}\left( 0 \right) =\\ & - \mathop {\max }\limits_{t \ne j} \left( {{\beta _{it}}\left( 1 \right) - {\beta _{it}}\left( 0 \right)} \right) = - \mathop {\max }\limits_{t \ne j} \left( {{\beta _{it}}} \right)\end{align*} $
对于信息 ${\alpha_{ij}}$ , 根据图 4给出的其与函数 ${E_j}( {c_{1j}}, \cdots $ , ${c_{ij}}$ , $\cdots, {c_{Nj}})$ 节点、变量节点 $c_{ij}$ 以及其他邻接节点之间信息的关系以及式 (14) 有:
$ \begin{align*} &{\alpha _{ij}}\left( {{c_{ij}}} \right) =\\ &\qquad \mathop {\max }\limits_{\left\{ {{c_{ik}}, k \ne j} \right\}} \left( {{E_j}\left( {{c_{1j}}, \cdots, {c_{ij}}, \cdots, {c_{Nj}}} \right) + \mathop \sum \limits_{t \ne j} {\rho _{tj}}\left( {{c_{it}}} \right)} \right)\end{align*} $
当 $i \ne j$ , 且 $i \in \bar P$ , $j \in \bar P$ , 令 $c_{ij}=1$ , 由中心点一致性约束 ${E_j}\left( {{c_{1j}}, \cdots, {c_{Nj}}} \right)$ , 则必有 $c_{ij}=1$ .则
$ \begin{align*} {\alpha _{ij}}\left( 1 \right) =&\ {\rho _{jj}}\left( 1 \right) + \mathop \sum \limits_{k \in \bar P\backslash i, j} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ & \mathop \sum \limits_{{p_v} \in P} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right] \\[2mm] {\alpha _{ij}}\left( 0 \right) = &\ \max [{\alpha _{ij}}\left( {{c_{ij}} = 0, {c_{jj}} = 0} \right), \\ &\ \alpha _{ij}\left( {{c_{ij}} = 0, {c_{jj}} = 1} \right)]=\\ &\ \max \Bigg[\mathop \sum \limits_{k \ne i} {\rho _{kj}}\left( 0 \right), {\rho _{jj}}\left( 1 \right) +\end{align*} $
$ \begin{align*} &\ \mathop \sum \limits_{k \in \bar P\backslash i, j} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P} \max \Bigg[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \Bigg] \Bigg] \\[2mm] {\alpha _{ij}} =&\ {\alpha _{ij}}\left( 1 \right) - {\alpha _{ij}}\left( 0 \right) =\\ &\ \min \Bigg[{\rho _{jj}} + \mathop \sum \limits_{k \in \bar P\backslash i, j} \max \left[{{\rho _{kj}}, 0} \right] +\\ &\ \mathop \sum \limits_{{p_v} \in P} \max \Bigg[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \Bigg], 0 \Bigg]\end{align*} $
当 $i \ne j$ , 且 $i \in \bar P$ , $j \in {p^j}$ ( ${p^j} \subset P$ , 即 $j$ 包含于某个同类约束集, 下同)
$ \begin{align*} \alpha _{ij}\left( 1 \right) =&\ \mathop \sum \limits_{k \in {p^j}} {\rho _{kj}}\left( 1 \right) + \mathop \sum \limits_{k \in \bar P\backslash i} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^j}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\\ {\alpha _{ij}}\left( 0 \right) =&\ \max [{\alpha _{ij}}\left( {{c_{ij}} = 0, {c_{jj}} = 0} \right), \\ &\ \alpha _{ij}\left( {{c_{ij}} = 0, {c_{jj}} = 1} \right)]= \\ &\ \max \Bigg[\mathop \sum \limits_{k \ne i} {\rho _{kj}}\left( 0 \right), \mathop \sum \limits_{k \in {p^j}} {\rho _{kj}}\left( 1 \right) +\\ &\ \mathop \sum \limits_{k \in \bar P\backslash i} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P- {p^j}} \max \Bigg[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \Bigg] \Bigg]\\ \alpha _{ij} =&\ {\alpha _{ij}}\left( 1 \right) - {\alpha _{ij}}\left( 0 \right) =\\ &\ \min \Bigg[\mathop \sum \limits_{k \in {p^j}} {\rho _{kj}} + \mathop \sum \limits_{k \in \bar P\backslash i} \max \left[{{\rho _{kj}}, 0} \right] + \\ &\ \mathop \sum \limits_{{p_v} \in P - {p^j}} \max \Bigg[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \Bigg], 0 \Bigg] \end{align*} $
当 $i \ne j$ , 且 $i \in {p^i}$ , $j \in \bar P$
$ \begin{align*} {\alpha _{ij}}\left( 1 \right) = &\ \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}}\left( 1 \right) + {\rho _{jj}}\left( 1 \right) + \mathop \sum \limits_{k \in \bar P\backslash j} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\\ \alpha _{ij}\left( 0 \right) =&\ \max [{\alpha _{ij}}\left( {{c_{ij}} = 0, {c_{jj}} = 0} \right), \\ &\ {\alpha _{ij}}\left( {{c_{ij}} = 0, {c_{jj}} = 1} \right)]= \\ &\ \max \Bigg[\mathop \sum \limits_{k \ne i} {\rho _{kj}}\left( 0 \right), {\rho _{jj}}\left( 1 \right) +\\ &\ \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}}\left( 0 \right) + \mathop \sum \limits_{k \in \bar P\backslash j} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P- {p^i}} \max \Bigg[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \Bigg] \Bigg]\end{align*} $
$ \begin{align*} \alpha _{ij} =&\ {\alpha _{ij}}\left( 1 \right) - {\alpha _{ij}}\left( 0 \right) =\\ &\ \min \Bigg[\mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}} + {\rho _{jj}} + \mathop \sum \limits_{k \in \bar P\backslash j} \max \left[ {{\rho _{kj}}, 0} \right] +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right], \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}} \Bigg] \end{align*} $
当 $i \ne j$ , 且 $i \in{p^i}$ , ${p^i} = {p^j} $
$ \begin{align*} \alpha _{ij}\left( 1 \right) =&\ \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}}\left( 1 \right) + \mathop \sum \limits_{k \in \bar P} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\end{align*} $
由于 $c_{ij}=0$ , $i$ , $j$ 同类, 由列约束, 则 $c_{jj}$ =0.
$ \begin{align*}{\alpha _{ij}}\left( 0 \right) = {\alpha _{ij}}\left( {{c_{ij}} = 0, {c_{jj}} = 0} \right) = \mathop \sum \limits_{k \ne i} {\rho _{kj}}\left( 0 \right)\end{align*} $
当 $i \ne j$ , 且 $i \in{p^i}$ , $j \in{p^j}$ , 且 $p^i \ne p^j$ , 当 $c_{ij}=1$ , 由列约束, 必有 $c_{jj}=1$
$ \begin{align*} {\alpha _{ij}}\left( 1 \right) =&\ \mathop \sum \limits_{k \in {p^j}} {\rho _{kj}}\left( 1 \right) + \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}}\left( 1 \right) +\\ &\ \mathop \sum \limits_{k \in \bar P} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^i} - {p^j}} \max \left[ {\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\end{align*} $
由于 $c_{ij}=0$ , $i$ , $j$ 同类, 由列约束, 则 $c_{jj}=0$ .
$ \begin{align*} \alpha _{ij}\left( 0 \right) =&\ \max [{\alpha _{ij}}\left( {{c_{ij}} = 0, {c_{jj}} = 0} \right), \\ &\ \alpha _{ij}\left( {{c_{ij}} = 0, {c_{jj}} = 1} \right)]=\\ &\ \max \Bigg[\mathop \sum \limits_{k \ne i} {\rho _{kj}}\left( 0 \right), \mathop \sum \limits_{k \in {p^j}} {\rho _{kj}}\left( 1 \right) + \\ &\ \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}}\left( 0 \right) + \mathop \sum \limits_{k \in \bar P} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) \Bigg]+\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^i} - {p^j}} \max \left[ {\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\\ \alpha _{ij} =&\ {\alpha _{ij}}\left( 1 \right) - {\alpha _{ij}}\left( 0 \right) =\\ &\ \min \Bigg[\mathop \sum \limits_{k \in {p^j}} {\rho _{kj}} + \mathop \sum \limits_{k \in {p^i}\backslash i} {\rho _{kj}} +\\ &\ \mathop \sum \limits_{k \in \bar P} \max \left[{{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P - {p^i}} \max \Bigg[ {\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \Bigg], 0 \Bigg] \end{align*} $
当 $i=j$ , 且 $j\in p^j$
$ \begin{align*} \alpha _{ij}\left( 1 \right) =&\ \mathop \sum \limits_{k \in {p^j}\backslash i} {\rho _{kj}}\left( 1 \right) + \mathop \sum \limits_{k \in \bar P} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^j}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\end{align*} $
$ \begin{align*} {\alpha _{ij}}\left( 0 \right) =&\ \mathop \sum \limits_{k \ne j} {\rho _{kj}}\left( 0 \right)\\ {\alpha _{ij}} =&\ {\alpha _{ij}}\left( 1 \right) - {\alpha _{ij}}\left( 0 \right) =\\ &\ \mathop \sum \limits_{k \in {p^j}\backslash i} {\rho _{kj}} + \mathop \sum \limits_{k \in \bar P} \max \left[{{\rho _{kj}}, 0} \right] +\\ &\ \mathop \sum \limits_{{p_v} \in P - {p^j}} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right] \end{align*} $
当 $i=j$ , 且 $j \in \bar P$
$ \begin{align*} {\alpha _{ij}}\left( 1 \right) =&\ \mathop \sum \limits_{k \in \bar P\backslash i} \mathop {\max }\limits_{{c_{kj}}} {\rho _{kj}}\left( {{c_{kj}}} \right) +\\ &\ \mathop \sum \limits_{{p_v} \in P} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 1 \right), \mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}\left( 0 \right)} \right]\\ {\alpha _{ij}}\left( 0 \right) =&\ \mathop \sum \limits_{k \ne i} {\rho _{kj}}\left( 0 \right)\\ {\alpha _{ij}} =&\ {\alpha _{ij}}\left( 1 \right) - {\alpha _{ij}}\left( 0 \right) =\\ &\ \mathop \sum \limits_{k \in \bar P\backslash i} \max \left[ {{\rho _{kj}}, 0} \right] + \mathop \sum \limits_{{p_v} \in P} \max \left[{\mathop \sum \limits_{k \in {p_v}} {\rho _{kj}}, 0} \right] \end{align*} $
由此完成 $\alpha_{ij}$ , $\eta_{ij}$ 迭代公式的推导.
-
图 3 $\eta_{ij}$ 与其相关信息关系图
Fig. 3 Relationship among $\eta_{ij}$ and its correlative message
图 4 $\alpha_{ij}$ 与其相关信息关系图
Fig. 4 Relationship among $\alpha_{ij}$ and its correlative message
表 1 部分符号说明
Table 1 The explanation of some symbol
符号 意义 $N$ 聚类数据点个数 $M$ 同类集个数 $h_1,h_2$ 数据点 $h_1,h_2$ $c_{ij}$ 变量节点, 为0表示 $j$ 不是 $i$ 的类中心点; 为1表示 $j$ 是 $i$ 的类中心点 $E_{ij}(\cdot)$ $E_j(c_{1j},\cdots,c_{Nj})$ 数据点 $j$ 的同类约束与一致性约束函数 $\rho_{ij}$ 表示变量节点 $c_{ij}$ 向函数节点 $E_j$ 所发送的标量信息 $c_i$ 数据点 $i$ 的类中心点 $P$ 全体同类集所构成的集合 $p^i$ 数据点 $i$ 所在的同类约束集 $I_i(\cdot)$ $I_i(c_{i1},\cdots,c_{iN})$ 为数据点 $i$ 的唯一性约束函数 $\alpha_{ij}$ 表示函数节点 $E_j$ 向变量节点 $ c_{ij}$ 所发送的标量信息 $\beta_{ij}$ 表示变量节点 $c_{ij}$ 向函数节点 $I_i$ 所发送的标量信息 $p_v$ 第 $v$ 个同类集 ⊕ 异或 ${{\bar P}}$ 无同类约束的数据点集 $S_{ij}(\cdot)$ 定义在数据点 $i$ , $j$ 之间的相似度函数 $s(i,j)$ 数据点 $i$ , $j$ 之间的相似度 $\eta_{ij}$ 表示函数节点 $I_i$ 向变量节点 $c_{ij}$ 所发送的标量信息 
下载: 导出CSV
表 2 人工数据上的聚类结果参数对比
Table 2 Performance comparison on man-made dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 72.12 72.12 72.12 70.31 69.3 56.50 56.50 56.50 53.43 55.0 0 std (0) (0) (0) (1.3) (3.6) (0) (0) (0) (1.1) (2.1) p-value - - - 4.2E-3 6.6E-3 - - - 1.8E-1 3.4E-1 Mean 87.24 82.74 80.22 85.27 81.66 80.47 72.41 70.50 77.39 75.4 10 std (6.6) (4.7) (0.8) (5.2) (9.2) (1.7) (1.1) (2.4) (2.1) (3.7) p-value - 3.1E-2 (+) 2.2E-5 (+) 9.7E-2 6.3E-3 (+) - 3.9E-2 (+) 4.1E-5 (+) 6.4E-2 6.8E-2 Mean 96.15 80.45 81.78 90.00 88.6 95.75 72.57 73.66 90.41 76.8 20 std (1.0) (1.6) (1.8) (4.1) (4.5) (4.0) (1.6) (2.7) (0.5) (1.4) p-value - 9.4E-4 (+) 7.8E-5 (+) 9.2E-3 (+) 9.2E-3 (+) - 1.7E-7 (+) 2.3E-6 (+) 1.4E-2 (+) 7.5E-6 (+) Mean 96.24 91.24 92.47 90.36 91.33 97.58 89.00 85.74 90.06 89.6 30 std (2.0) (4.1) (5.1) (0.8) (1.6) (0.2) (6.6) (4.1) (0.2) (2.8) p-value - 4.9E-2 (+) 5.1E-2 8.4E-3 (+) 7.4E-3 (+) - 3.4E-3 (+) 9.5E-8 (+) 1.6E-2 (+) 4.7E-4 (+) Mean 96.66 88.57 87.98 90.21 89.2 97.35 88.65 86.97 90.33 90.5 40 std (1.3) (3.0) (2.7) (0.2) (4.5) (2.0) (1.2) (0.9) (0.5) (7.7) p-value - 5.7E-3 (+) 1.1E-3 (+) 6.6E-3 (+) 3.9E-3 (+) - 1.1E-4 (+) 2.4E-7 (+) 1.8E-2 (+) 7.1E-3 (+) Mean 98.05 90.34 88.84 90.70 90.8 98.25 89.65 90.45 88.87 90.0 50 std (0.2) (7.1) (1.4) (0.6) (2.3) (0.2) (2.8) (9.6) (0.7) (3.4) p-value - 5.1E-2 7.2E-4 (+) 9.0E-5 (+) 1.4E-4 (+) - 42E-4 (+) 3.7E-7 (+) 8.4E-3 (+) 6.7E-3 (+) 注:表中p-value为5 %显著性水平下的 $t$ 检验值, "+"表示HCSAP在5 %显著性水平下优于对比聚类算法."-"表示在5 %显著性水平下HCSAP劣于对比聚类算法.粗体字表示对比较优者 (下同).
下载: 导出CSV
表 3 实验数据集
Table 3 Dataset used in experiment
Item Number of instance Dimension Class Preference Optdigit 1 797 64 10 $1\times Mid$ Iris 150 4 3 $3\times Mid$ Ionosphere 351 34 2 $10\times Mid$ Letter recogni- 2 241 16 3 $1\times Mid$ tion {I, J, L} Pendigits 3 498 16 10 $1\times Mid$ glass 214 9 6 $5\times Mid$ wine 178 13 3 $5\times Mid$ wdbc 768 8 2 $50\times Mid$
下载: 导出CSV
表 4 Optdigit数据集上的聚类结果对比
Table 4 Performance comparison on Optdigit dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 22.35 22.35 22.35 19.14 20.61 12.57 12.57 12.57 10.68 11.46 0 std (0) (0) (0) (1.25) (3.87) (0) (0) (0) (1.6) (0.9) p-value - - - 4.3E-3 4.9E-2 - - - 4.1E-2 (+) 4.8E-2 Mean 31.86 30.03 29.30 27.98 30.41 18.97 17.75 15.34 14.68 16.35 10 std (4.69) (1.30) (2.47) (1.50) (4.94) (5.02) (5.92) (6.1) (5.7) (2.2) p-value - 3.1E-1 3.3E-1 2.6E-1 5.1E-1 - 2.7E-1 6.1E-1 1.4E-1 9.9E-2 Mean 42.57 43.15 44.63 40.55 41.55 27.10 27.71 27.96 27.30 24.63 20 std (7.4) (8.01) (6.91) (7.65) (9.52) (9.00) (3.36) (4.86) (7.96) (8.14) p-value - 2.2E-1 6.6E-1 1.0E-1 2.9E-1 - 5.7E-1 6.7E-1 4.3E-1 7.4E-2) Mean 54.41 52.5 51.23 49.87 52.44 36.61 35.78 34.79 30.76 31.87 30 std (9.02) (2.01) (4.31) (2.44) (3.75) (2.67) (0.79) (6.6) (8.2) (7.8) p-value - 2.6E-1 1.7E-1 4.6E-2 (+) 5.7E-1 - 4.3E-1 8.7E-2 4.4E-2 (+) 2.5E-2 (+) Mean 62.67 61.35 61.22 59.57 61.24 45.85 44.46 45.20 41.85 40.27 40 std (2.39) (1.71) (1.6) (4.21) (8.34) (0.86) (3.12) (4.20) (7.14) (9.48) p-value - 4.0E-1 4.3E-1 2.9E-1 1.6E-1 - 1.7E-1 2.7E-1 7.7E-2 2.1E-2 (+) Mean 71.75 68.84 68.8 69.54 69.33 56.09 52.69 51.27 48.62 50.11 50 std (9.58) (6.32) (9.96) (8.47) (10.20) (2.45) (4.79) (2.70) (5.47) (5.50) p-value - 2.4E-1 2.4E-11 8.1E-2 9.8E-2 - 1.4E-2 (+) 1.1E-1 2.5E-3 (+) 5.8E-2
下载: 导出CSV
表 5 Iris数据集的聚类结果对比
Table 5 Performance comparison on Iris dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 61.87 61.87 61.87 56.27 55.38 55.33 55.33 55.33 52.61 53.70 0 std (0) (0) (0) (3.1) (3.6) (0) (0) (0) (2.30) (4.81) p-value - - - 1.4E-2 2.2E-2 - - - 1.6E-1 4.8E-1 Mean 73.36 72.93 72.55 71.84 69.57 75.60 56.53 55.22 60.77 58.45 10 std (2.69) (0.93) (1.21) (6.40) (3.72) (5.3) (0.87) (4.11) (2.57) (12.72) p-value - 1.5E-4 (+) 1.3E-4 (+) 5.3E-4 (+) 2.2E-4 (+) - 1.3E-3 (+) 1.4E-3 (+) 5.6E-3 (+) 4.2E-2 (+) Mean 79.04 79.78 76.99 81.21 74.31 75.33 69.11 66.22 64.21 70.40 20 std (3.22) (8.02) (5.90) (8.3) (6.61) (7.33) (12.10) (18.9) (14.1) (11.23) p-value - 2.8E-1 1.4E-1 8.2E-1 5.4E-3 - 2.7E-1 2.3E-1 5.4E-1 9.1E-1 Mean 88.46 80.33 81.24 80.74 75.33 81.33 72.22 71.25 72.11 69.44 30 std (1.75) (9.15) (9.47) (4.4) (10.1) (2.91) (12.15) (11.41) (13.15) (10.9) p-value - 2.1E-1 3.4E-1 1.1E-2 1.2E-2 - 2.3E-1 2.0E-1 2.8E-1 1.1E-1 Mean 94.72 89.62 88.25 85.74 84.27 92.93 84.40 84.00 81.23 83.78 40 std (3.64) (3.79) (4.8) (5.9) (5.6) (5.77) (6.95) (8.3) (7.9) (9.1) p-value - 1.5E-1 4.6E-2 (+) 4.9E-1 5.9E-1 - 1.7E-1 1.1E-1 1.4E-1 2.4E-1 Mean 94.43 92.38 93.50 90.22 89.01 94.44 88.22 87.20 86.33 90.01 50 std (0.39) (1.39) (2.0) (7.1) (5.1) (0.03) (5.00) (6.89) (6.12) (10.88) p-value - 1.0E-1 1.7E-1 5.5E-1 6.4E-1 - 1.5E-1 1.2E-1 2.7E-1 1.4E-1
下载: 导出CSV
表 6 Ionosphere数据集上的聚类结果对比
Table 6 Performance comparison on Ionosphere dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 51.96 51.96 51.96 45.89 46.31 40.35 40.35 40.35 43.48 41.25 0 std (0) (0) (0) (5.2) (3.4) (0) (0) (0) (2.50) (1.31) p-value - - - 7.3E-1 6.9E-1 - 4.4E-1 5.2E-1 1.3E-1 2.3E-1 Mean 55.24 56.74 57.30 58.21 54.21 58.21 59.38 57.66 55.24 58.00 10 std (2.45) (7.87) (1.2) (7.2) (3.6) (7.32) (2.78) (7.27) (6.17) (5.48) p-value - 3.5E-2 (-) 4.8E-2 (-) 5.4E-1 7.9E-1 - 8.2E-1 6.3E-1 5.2E-1 4.5E-1 Mean 56.45 61.13 60.34 54.29 55.12 63.41 64.12 64.30 62.34 61.25 20 std (1.97) (2.36) (1.90) (4.87) (3.57) (5.79) (3.18) (5.54) (7.53) (4.74) p-value - 5.40E-3 (-) 3.47E-2 (-) 4.4E-1 5.1E-1 - 2.8E-1 3.5E-1 6.4E-1 4.1E-1 Mean 66.61 61.16 65.14 57.02 59.54 63.74 67.20 61.42 61.28 60.11 30 std (3.25) (5.47) (3.32) (5.42) (4.14) (5.20) (1.44) (8.54) (3.15) (7.21) p-value - 2.8E-1 4.2E-1 3.3E-1 2.4E-1 - 1.9E-1 2.9E-1 1.6E-1 1.7E-1 Mean 67.61 71.68 68.50 64.71 69.87 62.66 64.04 57.99 60.34 61.23 40 std (4.23) (3.03) (1.20) (4.56) (1.57) (8.17) (7.24) (4.8) (1.36) (5.4) p-value - 2.4E-2 (-) 3.7E-2 (-) 1.7E-1 5.6E-1 - 2.5E-1 3.6E-1 2.2E-1 1.4E-1 Mean 84.16 83.17 80.26 80.66 84.78 72.53 71.33 72.55 70.21 69.88 50 std (6.12) (4.87) (2.80) (2.69) (4.31) (5.60) (7.53) (5.33) (2.42) (4.69) p-value - 3.6E-1 3.4E-1 4.7E-1 2.1E-1 - 1.9E-1 3.9E-1 2.2E-1 1.0E-1
下载: 导出CSV
表 7 Letter-recognition {I, J, L}上的聚类结果对比
Table 7 Performance comparison on Letter-recognition dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 49.87 49.87 49.87 41.30 42.33 33.33 33.33 33.33 31.54 30.36 0 std (0) (0) (0) (1.9) (4.1) (0) (0) (0) (2.5) (3.1) p-value - - - 5.7E-2 6.9E-2 - - - 1.7E-1 1.0E-1 Mean 54.42 55.01 54.36 55.11 57.21 39.00 38.10 40.23 39.98 40.05 10 std (8.90) (2.63) (5.7) (6.4) (3.89) (8.08) (2.78) (1.4) (2.0) (3.7) p-value - 6.2E-1 2.1E-1 4.8E-1 1.2E-1 - 2.3E-1 5.6E-1 7.4E-1 6.1E-1 Mean 59.47 52.01 51.69 57.20 55.31 42.66 35.33 34.88 37.90 35.87 20 std (1.92) (5.73) (4.8) (6.8) (5.0) (9.57) (7.26) (5.8) (3.2) (2.8) p-value - 4.2E-2 (+) 3.2E-2 (+) 1.1E-1 3.1E-1 - 4.9E-2 2.3E-2 4.7E-2 2.6E-2 Mean 67.90 65.36 66.30 64.87 60.45 52.66 50.00 49.68 50.33 51.74 30 std (0.41) (6.44) (3.2) (5.6) (4.9) (1.84) (1.54) (1.74) (2.53) (3.40) p-value - 2.6E-1 3.0E-1 1.7E-1 2.6E-1 - 2.3E-1 1.2E-1 2.9E-1 5.4E-1 Mean 77.05 72.97 73.33 71.4 70.24 64.66 60.00 59.40 58.67 51.77 40 std (2.00) (4.43) (1.5) (2.6) (2.4) (8.17) (4.26) (7.26) (8.11) (14.25) p-value - 3.3E-1 4.2E-1 1.1E-1 1.5E-1 - 3.4E-1 2.9E-1 4.1E-1 5.3E-1 Mean 84.16 83.17 84.12 83.00 81.47 73.33 71.33 70.11 68.25 67.49 50 std (4.55) (7.41) (5.4) (4.9) (4.4) (2.62) (7.53) (5.1) (7.6) (5.3) p-value - 4.9E-1 5.0E-1 2.3E-1 2.3E-1 - 3.3E-1 2.8E-1 1.0E-1 4.4E-2 (+)
下载: 导出CSV
表 8 Pendigits数据集的聚类结果对比
Table 8 Performance comparison on Pendigits dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 19.23 19.23 19.23 17.21 16.32 11.20 11.20 11.20 9.79 9.64 0 std (0) (0) (0) (1.42) (2.51) (0) (0) (0) (0.25) (0.36) p-value - - - 9.4E-3 (+) 2.8E-3 (+) - - - 3.9E-2 (+) 2.8E-2 (+) Mean 27.40 23.17 24.65 24.68 21.97 16.72 13.75 12.99 13.58 11.95 10 std (1.38) (8.62) (7.64) (9.17) (4.11) (5.03) (3.15) (2.87) (2.77) (1.44) p-value - 2.3E-1 5.6E-2 2.8E-1 5.8E-2 - 4.1E-1 9.6E-2 6.7E-1 6.1E-1 Mean 38.66 35.19 34.67 33.74 34.21 36.14 25.58 24.71 21.95 27.64 20 std (0.88) (3.67) (4.25) (5.50) (6.67) (3.13) (8.79) (3.34) (5.61) (4.13) p-value - 5.6E-1 2.4E-1 2.7E-1 3.1E-1 - 8.3E-3 2.3E-3 9.8E-4 1.9E-3 Mean 60.54 57.56 55.82 51.64 56.83 46.19 43.08 40.27 39.87 41.56 30 std (9.90) (0.26) (1.13) (4.21) (6.57) (0.54) (2.86) (3.41) (4.12) (3.49) p-value - 8.3E-1 5.3E-1 5.6E-2 6.6E-1 - 5.8E-1 4.1E-1 8.6E-2 2.9E-1 Mean 68.49 62.12 63.77 60.16 62.57 55.46 48.51 44.21 39.48 41.67 40 std (1.28) (5.29) (6.84) (3.46) (4.57) (6.09) (1.93) (1.53) (4.85) (3.34) p-value - 5.6E-1 6.8E-1 4.9E-1 1.4E-1 - 4.6E-2 (+) 5.3E-3 (+) 2.1E-4 (+) 9.4E-3 (+) Mean 75.75 66.30 67.38 67.22 64.14 65.23 53.60 54.69 55.21 53.96 50 std (4.58) (8.38) (7.52) (7.31) (5.63) (2.58) (6.82) (7.39) (4.61) (9.42) p-value - 6.1E-2 7.6E-1 4.9E-1 2.0E-1 - 3.8E-2 (+) 4.2E-2 (+) 1.6E-2 (+) 6.4E-3 (+)
下载: 导出CSV
表 9 glass数据集的聚类结果对比
Table 9 Performance comparison on glass dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 31.02 31.02 31.02 28.66 27.14 31.66 31.66 31.66 28.51 30.69 0 std (0) (0) (0) (2.80) (3.74) (0) (0) (0) (1.90) (2.45) p-value - - - 2.63E-1 1.77E-1 - - - 2.1E-1 2.6E-1 Mean 37.24 35.85 35.62 31.89 33.57 38.00 38.00 37.15 35.46 34.76 10 std (8.90) (3.17) (4.66) (5.78) (9.51) (8.08) (2.78) (3.64) (5.21) (4.23) p-value - 6.0E-1 3.4E-1 1.9E-1 2.4E-1 - 8.4E-1 5.6E-1 3.6E-1 3.1E-1 Mean 40.98 37.80 35.70 36.44 37.15 42.66 35.33 34.36 31.93 32.19 20 std (0.06) (0.02) (0.08) (1.62) (3.48) (9.57) (7.26) (6.19) (8.42) (2.96) p-value - 1.1E-1 6.4E-2 8.3E-2 4.8E-1 - 5.4E-2 4.9E-2 (+) 2.5E-2 (+) 3.4E-2 (+) Mean 46.05 43.32 44.22 40.35 45.11 70.87 54.52 55.21 52.94 57.14 30 std (0.15) (3.21) (3.90) (5.44) (7.16) (1.50) (6.36) (4.83) (8.91) (7.88) p-value - 2.9E-1 5.2E-1 9.7E-2 4.5E-1 - 4.6E-2 (+) 2.0E-2 (+) 9.4E-3 (+) 5.6E-2 Mean 53.23 47.71 46.25 42.18 47.84 80.06 61.06 64.37 59.81 60.56 40 std (1.46) (5.89) (4.77) (4.65) (7.21) (5.00) (7.27) (8.36) (7.24) (4.98) p-value - 1.8E-1 1.3E-1 7.6E-2 5.5E-1 - 5.7E-2 1.7E-1 8.7E-3 (+) 7.68E-2 Mean 54.67 50.70 51.28 49.57 51.14 79.63 64.02 61.44 62.37 59.87 50 std (7.43) (4.98) (6.40) (7.15) (8.44) (8.83) (5.42) (6.48) (7.21) (9.18) p-value - 1.6E-1 3.6E-1 7.4E-2 6.1E-1 - 5.0E-2 (+) 4.4E-2 (+) 4.5E-2 (+) 6.9E-3 (+)
下载: 导出CSV
表 10 wine数据集的聚类结果对比
Table 10 Performance comparison on wine dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 60.21 60.21 60.21 54.39 57.82 70.54 70.54 70.54 64.87 61.49 0 std (0) (0) (0) (5.67) (4.10) (0) (0) (0) (5.10) (6.54) p-value - - - 2.9E-1 4.6E-1 - - - 1.3E-1 9.3E-2 Mean 79.16 68.98 69.33 65.47 67.26 84.94 72.36 73.66 75.19 70.58 10 std (5.450) (3.82) (5.44) (8.21) (4.94) (8.35) (5.26) (5.87) (4.24) (6.29) p-value - 6.3E-3 (+) 9.2E-4 (+) 6.1E-3 (+) 8.1E-2 (+) - 4.7E-2 (+) 4.9E-2 (+) 6.7E-2 8.1E-3 (+) Mean 81.36 71.82 69.88 68.15 60.47 84.83 73.88 71.20 69.64 65.88 20 std (3.65) (5.49) (5.40) (8.14) (6.47) (8.22) (4.55) (6.88) (7.52) (10.37) p-value - 7.4E-2 4.8E-2 1.3E-1 9.1E-2 - 1.5E-1 8.3E-2 7.2E-2 4.3E-2 (+) Mean 84.78 83.27 80.31 81.55 82.41 92.06 89.40 85.94 90.31 88.49 30 std (2.93) (5.21) (6.40) (3.70) (7.52) (1.68) (6.34) (5.80) (1.23) (3.54) p-value - 1.8E-1 1.1E-1 3.4E-1 4.4E-1 - 1.7E-1 8.3E-2 4.6E-1 9.7E-2 Mean 90.22 84.24 80.64 81.47 72.63 95.06 89.66 88.33 90.27 87.92 40 std (2.81) (3.51) (4.36) (1.42) (0.99) (1.51) (5.82) (6.42) (8.66) (9.11) p-value - 4.0E-2 (+) 2.2E-3 (+) 3.6E-2 (+) 9.4E-3 (+) - 1.3E-1 8.4E-2 5.2E-2 4.3E-2 (+) Mean 89.76 86.68 85.85 80.74 81.69 88.82 85.74 85.63 84.22 80.75 50 std (1.99) (4.99) (6.41) (6.28) (7.11) (2.62) (7.53) (8.90) (7.24) (9.11) p-value - 2.7E-1 2.0E-1 5.7E-2 3.3E-1 - 2.7E-1 1.1E-1 3.4E-1 2.1E-1
下载: 导出CSV
表 11 wdbc数据集的聚类结果对比
Table 11 Performance comparison on wdbc dataset
Sample rate Item F-measure (%) Pure (%) (%) HCSAP SAP SSAP MPCK-MEAN DSCA HCSAP SAP SSAP MPCK-MEAN DSCA Mean 52.31 52.31 52.31 48.42 47.49 55.74 55.74 55.74 51.78 52.69 0 std (0) (0) (0) (1.10) (1.67) (0) (0) (0) (0.62) (0.37) p-value - - - 4.5E-2 (+) 3.1E-2 (+) - - - 4.8E-2 (+) 5.7E-2 Mean 66.35 50.72 48.39 51.46 49.21 61.39 47.80 47.92 44.91 51.68 10 std (13.38) (1.42) (2.82) (2.6) (5.06) (11.73) (3.50) (6.41) (17.46) (14.25) p-value - 1.5E-1 9.2E-2 3.4E-1 1.1E-1 - 1.2E-1 2.4E-1 4.2E-1 2.9E-1 Mean 74.27 66.58 67.24 64.21 60.37 72.16 61.16 60.58 57.26 59.34 20 std (13.78) (14.87) (11.35) (15.87) (9.58) (14.45) (17.51) (15.68) (11.34) (8.48) p-value - 5.0E-1 6.2E-1 9.8E-2 4.1E-1 - 4.1E-1 5.4E-1 1.2E-1 2.6E-1 Mean 85.90 59.10 58.22 57.31 56.74 84.23 52.42 50.72 48.64 51.77 30 std (0. 86) (17.4) (20.55) (8.27) (4.90) (1.26) (4.28) (5.60) (4.89) (2.77) p-value - 9.0E-03 (+) 2.5E-2 (+) 5.1E-3 (+) 6.4E-3 (+) - 7.4E-04 (+) 5.6E-5 (+) 4.9E-6 (+) 1.8E-7 (+) Mean 88.09 71.83 71.27 69.58 64.96 87.39 70.61 71.33 64.99 68.41 40 std (1.35) (8.86) (7.89) (10.54) (9.73) (3.0) (8.14) (6.64) (10.37) (12.85) p-value - 4.70E-2 (+) 2.8E-2 (+) 4.2E-3 (+) 7.7E-3 (+) - 5.3E-2 5.1E-2 4.8E-3 (+) 2.5E-2 (+) Mean 87.53 84.82 84.32 81.62 82.44 88.32 84.74 80.16 75.32 72.19 50 std (7.18) (9.02) (10.33) (8.27) (9.11) (7.80) (9.83) (8.12) (10.77) (11.65) p-value - 4.8E-2 (+) 3.4E-2 (+) 8.9E-3 (+) 7.7E-3 (+) - 4.1E-2 (+) 2.2E-2 (+) 3.6E-2 (+) 1.8E-2 (+)
下载: 导出CSV
-
[1] Frey B J, Dueck D. Clustering by passing messages between data points. Science, 2007, 315(5814):972-976 doi: 10.1126/science.1136800 [2] 许晓丽, 卢志茂, 张格森, 李纯, 张琦.改进近邻传播聚类的彩色图像分割.计算机辅助设计与图形学学报, 2012, 24(4):514-519 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201204015.htmXu Xiao-Li, Lu Zhi-Mao, Zhang Ge-Sen, Li Chun, Zhang Qi. Color image segmentation based on improved affinity propagation clustering. Journal of Computer-Aided Design & Computer Graphics, 2012, 24(4):514-519 http://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201204015.htm [3] Borile C, Labarre M, Franz S, Sola C, Refrégier G. Using affinity propagation for identifying subspecies among clonal organisms:lessons from M. tuberculosis. BMC Bioinformatics, 2011, 12:224 doi: 10.1186/1471-2105-12-224 [4] 储岳中, 徐波, 高有涛, 邰伟鹏.基于近邻传播聚类与核匹配追踪的遥感图像目标识别方法.电子与信息学报, 2014, 36(12):2923-2928 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201412021.htmChu Yue-Zhong, Xu Bo, Gao You-Tao, Tai Wei-Peng. Technique of remote sensing image target recognition based on affinity propagation and kernel matching pursuit. Journal of Electronics and Information Technology, 2014, 36(12):2923-2928 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201412021.htm [5] 王开军, 张军英, 李丹, 张新娜, 郭涛.自适应仿射传播聚类.自动化学报, 2007, 33(12):1242-1246 http://www.aas.net.cn/CN/abstract/abstract15756.shtmlWang Kai-Jun, Zhang Jun-Ying, Li Dan, Zhang Xin-Na, Guo Tao. Adaptive affinity propagation clustering. Acta Automatica Sinica, 2007, 33(12):1242-1246 http://www.aas.net.cn/CN/abstract/abstract15756.shtml [6] 刘建伟, 刘媛, 罗雄麟.半监督学习方法.计算机学报, 2015, 38(8):1592-1617Liu Jian-Wei, Liu Yuan, Luo Xiong-Lin. Semi-supervised learning methods. Chinese Journal of Computers, 2015, 38(8):1592-1617 [7] Bijral A S, Ratliff N, Srebro N. Semi-supervised learning with density based distances.[Online], available:http://ttic.uchicago.edu/~nati/Publications/SemiSupDBD.pdf, October 10, 2014 [8] Wagstaff K, Cardie C. Clustering with instance-level constraints. In:Proceedings of the 17th International Conference on Machine Learning (ICML2000). Stanford:Morgan Kaufmann Publishers, 2000. 1103-1110 [9] 肖宇, 于剑.基于近邻传播算法的半监督聚类.软件学报, 2008, 19(11):2803-2813 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811005.htmXiao Yu, Yu Jian. Semi-supervised clustering based on affinity propagation algorithm. Journal of Software, 2008, 19(11):2803-2813 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811005.htm [10] 张震, 汪斌强, 伊鹏, 兰巨龙.一种分层组合的半监督近邻传播聚类算法.电子与信息学报, 2013, 35(3):645-651 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201303020.htmZhang Zhen, Wang Bin-Qiang, Yi Peng, Lan Ju-Long. Semi-supervised affinity propagation clustering algorithm based on stratified combination. Journal of Electronics and Information Technology, 2013, 35(3):645-651 http://www.cnki.com.cn/Article/CJFDTOTAL-DZYX201303020.htm [11] 张建朋, 陈福才, 李邵梅, 刘力雄.基于密度与近邻传播的数据流聚类算法.自动化学报, 2014, 40(2):277-288 http://www.aas.net.cn/CN/abstract/abstract16309.shtmlZhang Jian-Peng, Chen Fu-Cai, Li Shao-Mei, Liu Li-Xiong. Data stream clustering algorithm based on density and affinity propagation techniques. Acta Automatica Sinica, 2014, 40(2):277-288 http://www.aas.net.cn/CN/abstract/abstract16309.shtml [12] Givoni I E, Frey B J. Semi-supervised affinity propagation with instance-level constraints. In:Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS). Clearwater Beach, Florida, USA:JMLR W & CP5, 2009. 161-168 [13] 赵宪佳, 王立宏.近邻传播半监督聚类算法的分析与改进.计算机工程与应用, 2010, 46(36):168-170 http://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201036047.htmZhao Xian-Jia, Wang Li-Hong. Analysis and improvement of semi-supervised clustering algorithm based on affinity propagation. Computer Engineering and Applications, 2010, 46(36):168-170 http://www.cnki.com.cn/Article/CJFDTOTAL-JSGG201036047.htm [14] Wagstaff K, Cadrie C, Rogers S, Schroedl S. Constrained K-means clustering with background knowledge. In:Proceedings of the 18th International Conference on Machine Learning (ICML2001). Williamstown:Morgan Kaufmann Publishers, 2001. 577-584 [15] 尹学松, 胡恩良, 陈松灿.基于成对约束的判别型半监督聚类分析.软件学报, 2008, 19(11):2791-2802 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811004.htmYin Xue-Song, Hu En-Liang, Chen Song-Can. Discriminative semi-supervised clustering analysis with pairwise constraints. Journal of Software, 2008, 19(11):2791-2802 http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200811004.htm [16] Kschischang F R, Frey B J, Loeliger H A. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 2001, 47(2):498-519 doi: 10.1109/18.910572 [17] Weiss Y, Freeman W T. On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs. IEEE Transactions on Information Theory, 2001, 47(2):736-744 doi: 10.1109/18.910585 [18] Givoni I E, Frey B J. A binary variable model for affinity propagation. Neural Computation, 2009, 21(6):1589-1600 doi: 10.1162/neco.2009.05-08-785 期刊类型引用(11)
1. 王治和，常筱卿，杜辉. 基于万有引力的自适应近邻传播聚类算法. 计算机应用. 2021(05): 1337-1342 . 
百度学术2. 邱保志，张瑞霖，李向丽. 基于过滤模型的聚类算法. 控制与决策. 2020(05): 1091-1101 . 百度学术3. 征察，吉立新，高超，李邵梅，吴翼腾. 基于成对约束的偏标记数据消歧算法. 自动化学报. 2020(07): 1367-1377 . 本站查看4. 钱雪忠，王卫涛. 多维空间可调整的近邻传播聚类算法. 计算机科学与探索. 2019(01): 116-127 . 百度学术5. 曹愈远，张博文，李艳军. AP聚类改进免疫算法用于航空发动机故障诊断. 航空动力学报. 2019(08): 1795-1804 . 百度学术6. 刘璧钺，赵章焰. 基于改进LSD和AP聚类的路径边缘识别策略. 图学学报. 2019(05): 915-924 . 百度学术7. 刘自豪，张斌，祝宁，唐慧林. 基于改进AP聚类算法的自学习应用层DDoS检测方法. 计算机研究与发展. 2018(06): 1236-1246 . 百度学术8. 赵昱，陈琴，苏一丹，陈慧姣. 基于邻域相似度的近邻传播聚类算法. 计算机工程与设计. 2018(07): 1883-1888 . 百度学术9. 王卫涛，钱雪忠，曹文彬. 自适应参数调整的近邻传播聚类算法. 小型微型计算机系统. 2018(06): 1305-1311 . 百度学术10. 李晓庆，唐昊，司加胜，苗刚中. 面向混合属性数据集的改进半监督FCM聚类方法. 自动化学报. 2018(12): 2259-2268 . 本站查看11. 陈雷，肖创柏，禹晶，王真理，李学良. 基于相似性传播聚类与主成分分析的断层识别方法. 石油地球物理勘探. 2017(04): 826-833+627-628 . 百度学术其他类型引用(9)
-
下载:
计量
- 文章访问数: 2568
- HTML全文浏览量: 255
- PDF下载量: 968
- 被引次数: 20
