第13卷第5期 智能系统学报 Vol.13 No.5 2018年10月 CAAI Transactions on Intelligent Systems Oct.2018 D0:10.11992/tis.201703013 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20170702.1547.026html 结合稀疏表示与约束传递的半监督谱聚类算法 赵晓晓，周治平 (江南大学物联网技术应用教育部工程研究中心，江苏无锡214122) 摘要：针对半监督谱聚类不能有效处理大规模数据，没有考虑约束传递不能充分利用有限约束信息的问题， 提出一种结合稀疏表示和约束传递的半监督谱聚类算法。首先，根据约束信息生成约束矩阵，将其引入到谱聚 类中；然后，将约束集合中的数据作为地标点构造稀疏表示矩阵，近似获得图相似度矩阵，从而改进约束谱聚 类模型：同时，根据地标点的相似度矩阵生成连通区域，在每个连通区域内动态调整近邻点，利用约束传递进 一步提高聚类准确率。实验表明，所提算法和约束谱聚类相比，在算法效率方面具有明显优势，且准确率没有 明显下降：和快速谱聚类方法相比，在聚类准确率上有所提升。 关键词：数据挖掘：聚类分析：谱聚类：半监督学习：稀硫表示：约束传递 中图分类号：TP18 文献标志码：A文章编号：1673-4785(2018)05-0855-09 中文引用格式：赵晓晓，周治平.结合稀疏表示与约束传递的半监督谱聚类算法L.智能系统学报，2018,13(5)：855-863. 英文引用格式：ZHAO Xiaoxiao,ZHOU Zhiping.A semi-supervised spectral clustering algorithm combined with sparse representa- tion and constraint propagation[J CAAI transactions on intelligent systems,2018,13(5):855-863. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation ZHAO Xiaoxiao,ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education,Jiangnan University,Wuxi 214122,China) Abstract:The semi-supervised spectral clustering algorithm does not deal with large-scale datasets effectively and does not fully utilize the constraint information because it does not consider the constraint propagation.To address these drawbacks,this paper proposes a semi-supervised spectral clustering algorithm that combines sparse representation and constraint propagation.The algorithm first generates the constraint matrix according to the constraint information,intro- duces it into the spectral clustering,and then constructs a sparse representation matrix by taking the data points in the constrained sets as the landmarks to approximate the graph similarity matrix,thereby revising the constrained spectral clustering model.Meanwhile,the connected region is generated according to the similarity matrix of the landmark data points,and the neighboring nodes are dynamically adjusted in each connected region.The clustering accuracy is further improved using the constraint propagation.Experimental results show that the proposed method is more efficient than constrained spectral clustering algorithms,and their accuracy levels are similar.Moreover,its clustering accuracy ex- ceeds those of the fast spectral clustering algorithms. Keywords:data mining;cluster analysis;spectral clustering;semi-supervised learning;sparse representation;constraint propagation 谱聚类作为聚类分析一种有效的方法，建立 收稿日期：2017-03-10.网络出版日期：2017-07-02 在谱图划分的基础上，可将数据集从原始空间转 基金项目：国家自然科学基金项目(61373126). 通信作者：赵晓晓.E-mail:6l519050I9@vip,jiangnan.edu.cn. 换到低维特征空间，使原始数据变成线性可分四
DOI: 10.11992/tis.201703013 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20170702.1547.026.html 结合稀疏表示与约束传递的半监督谱聚类算法 赵晓晓，周治平 （江南大学 物联网技术应用教育部工程研究中心，江苏 无锡 214122） 摘 要：针对半监督谱聚类不能有效处理大规模数据，没有考虑约束传递不能充分利用有限约束信息的问题， 提出一种结合稀疏表示和约束传递的半监督谱聚类算法。首先，根据约束信息生成约束矩阵，将其引入到谱聚 类中；然后，将约束集合中的数据作为地标点构造稀疏表示矩阵，近似获得图相似度矩阵，从而改进约束谱聚 类模型；同时，根据地标点的相似度矩阵生成连通区域，在每个连通区域内动态调整近邻点，利用约束传递进 一步提高聚类准确率。实验表明，所提算法和约束谱聚类相比，在算法效率方面具有明显优势，且准确率没有 明显下降；和快速谱聚类方法相比，在聚类准确率上有所提升。 关键词：数据挖掘；聚类分析；谱聚类；半监督学习；稀疏表示；约束传递 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2018)05−0855−09 中文引用格式：赵晓晓, 周治平. 结合稀疏表示与约束传递的半监督谱聚类算法[J]. 智能系统学报, 2018, 13(5): 855–863. 英文引用格式：ZHAO Xiaoxiao, ZHOU Zhiping. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation[J]. CAAI transactions on intelligent systems, 2018, 13(5): 855–863. A semi-supervised spectral clustering algorithm combined with sparse representation and constraint propagation ZHAO Xiaoxiao，ZHOU Zhiping (Engineering Research Center of Internet of Things Technology Applications Ministry of Education, Jiangnan University, Wuxi 214122, China) Abstract: The semi-supervised spectral clustering algorithm does not deal with large-scale datasets effectively and does not fully utilize the constraint information because it does not consider the constraint propagation. To address these drawbacks, this paper proposes a semi-supervised spectral clustering algorithm that combines sparse representation and constraint propagation. The algorithm first generates the constraint matrix according to the constraint information, introduces it into the spectral clustering, and then constructs a sparse representation matrix by taking the data points in the constrained sets as the landmarks to approximate the graph similarity matrix, thereby revising the constrained spectral clustering model. Meanwhile, the connected region is generated according to the similarity matrix of the landmark data points, and the neighboring nodes are dynamically adjusted in each connected region. The clustering accuracy is further improved using the constraint propagation. Experimental results show that the proposed method is more efficient than constrained spectral clustering algorithms, and their accuracy levels are similar. Moreover, its clustering accuracy exceeds those of the fast spectral clustering algorithms. Keywords: data mining; cluster analysis; spectral clustering; semi-supervised learning; sparse representation; constraint propagation 谱聚类作为聚类分析一种有效的方法，建立 在谱图划分的基础上，可将数据集从原始空间转 换到低维特征空间，使原始数据变成线性可分[1] ， 收稿日期：2017−03−10. 网络出版日期：2017−07−02. 基金项目：国家自然科学基金项目 (61373126). 通信作者：赵晓晓. E-mail：6151905019@vip.jiangnan.edu.cn. 第 13 卷第 5 期 智 能 系 统 学 报 Vol.13 No.5 2018 年 10 月 CAAI Transactions on Intelligent Systems Oct. 2018
·856· 智能系统学报 第13卷 目前已广泛应用于图像分割、人脸识别等领域。 明，本文算法对这些大规模数据具有较好适应 另一方面，半监督学习是机器学习领域的研究热 性，且在有效降低算法复杂度的同时，保证了约 点，已被用于解决实际问题6，在聚类分析中引 束谱聚类算法结果的准确率。 入一些监督信息来指导聚类过程，能够提高聚类 准确率。 1算法基本原理 半监督聚类算法的约束信息包括“必连”和 1.1约束NCut算法 “勿连”约束集合，引入这些约束信息可指导聚类 对于数据集X={x1,x:∈R,数据之间的相 过程。目前，针对半监督谱聚类算法已有大量的 似度矩阵为W,度矩阵D为对角阵，其内元素表 研究，Kamvar等m根据约束关系调整数据之间的 相似度，将调整后的相似度矩阵用于改进谱聚 示为Da=∑W规范化拉普拉斯矩阵表示为L=一 类，但是不能充分利用初始有限的约束关系；蒋 D-1PWD-1r,I表示单位矩阵。 伟进等劉提出一种纠错式主动学习成对约束算 标准NCut的目标函数为 法，将挖掘到的监督信息用于调整数据点之间的 argminv'Lv,s.t.yy =1,vL1 (1) 距离矩阵，但约束集合对聚类结果影响较大；丁 世飞等通过优化高斯核参数和引入成对约束信 式中v表示松弛化的类指示向量。 息来调整相似度矩阵，但过多的约束信息会对聚 假设已知“必连”约束集合M与“勿连”约束集 类准确率造成负面的影响；Cucuringu等"ol将“必 合C,文献[11]根据约束信息生成约束矩阵Q,可 连”和“勿连”约束矩阵均视为图拉普拉斯矩阵，把 表示为 约束聚类转化为广义特征值问题，针对2类划分 (x,x)∈M 效率和准确率显著提高。王翔等提出一种柔性 Q -1,(x,x)eC (2) 0, 约束谱聚类框架，引入大量硬约束和软约束信息 无约束信息 建立新的约束优化问题，有效提高聚类准确率， 通过式(3)来衡量Q中约束关系与v的一致程度： 但是不具备约束关系传递。基于约束信息的半监 ov-> (3) 督聚类算法，通常能获取数据的约束关系是非常 1j1 有限的，通过约束传递来获得大量可靠的成对约 定义软约束v∈R,QER",如果数据x,和x,是 束信息，可显著提高半监督聚类的性能。余志文 同一类，那么Q为正；否则为负。Q的绝对值表示 等2提出一种增强型半监督聚类集成框架(incre- 约束权重，vQ的值越大，表明v与Q中的约束信 mental semi-supervised clustering ensemble,ISSCE), 息就越一致。基于上述软约束，不一定要严格满 采用卢志武等提出的约束传递方法，即基于 足每个指定的约束条件，忽略部分约束信息可降 k近邻图的标签传播方法，将少量标签样本的监 低计算开销，通过用户指定阈值来确定约束的下 督信息传递给未标签样本，但如果相似度错误反 界值，即vQy≥a。 映数据点之间的相似性，会造成约束关系的错误 约束NCut的目标函数为 传递。传统的谱聚类及上述大部分半监督谱聚类 argminy Lv,s.t.yQv>a.vy=1.vL1 (4) 算法均需要存储数据的相似度矩阵且对拉普拉斯 上述问题可转化为求解矩阵的特征向量)， 矩阵进行特征分解，空间和时间的计算复杂度比 但是空间和时间复杂度分别为0(2)和0()，对于 较高，在处理大规模数据集时计算代价难以承受。 大规模数据集，计算复杂度过高；而且不具备约 为了提升谱聚类的扩展性，蔡登等1提出基于地 标点表示的谱聚类算法，通过数据点与地标点之 束传递功能，不能充分利用有限的约束信息。 间的相似度矩阵乘积来近似得到整体数据点的相 1.2依据稀疏表示的相似度矩阵 似度矩阵，然后利用近似性质实现快速特征分解。 蔡登等提出基于图稀疏表示的谱聚类算 本文将采用基于地标点近似表示的方法，通 法，通过地标点的线性组合来实现所有数据点 过稀疏表示构造的相似度矩阵对柔性约束谱聚类 X的近似表示X≈YZ。对于给定的任一数据点 算法模型进行改进，并且根据约束集合内地标 x,其近似数据点e,可以表示为 点的关系，利用Tarjan算法自动检测连通区域， (5) 在每个连通区域内部动态调整近邻点，传递约束 1 关系，从而更新稀疏表示矩阵提高聚类准确率。 式中：y,是Y∈Rwp的列向量，Z是ZeRw的第j行 在5个大规模标准数据集上进行实验的结果表 第i列元素
目前已广泛应用于图像分割、人脸识别等领域[2-3]。 另一方面，半监督学习是机器学习领域的研究热 点，已被用于解决实际问题[4-6] ，在聚类分析中引 入一些监督信息来指导聚类过程，能够提高聚类 准确率。 半监督聚类算法的约束信息包括“必连”和 “勿连”约束集合，引入这些约束信息可指导聚类 过程。目前，针对半监督谱聚类算法已有大量的 研究，Kamvar 等 [7]根据约束关系调整数据之间的 相似度，将调整后的相似度矩阵用于改进谱聚 类，但是不能充分利用初始有限的约束关系；蒋 伟进等[8]提出一种纠错式主动学习成对约束算 法，将挖掘到的监督信息用于调整数据点之间的 距离矩阵，但约束集合对聚类结果影响较大；丁 世飞等[9]通过优化高斯核参数和引入成对约束信 息来调整相似度矩阵，但过多的约束信息会对聚 类准确率造成负面的影响；Cucuringu 等 [10]将“必 连”和“勿连”约束矩阵均视为图拉普拉斯矩阵，把 约束聚类转化为广义特征值问题，针对 2 类划分 效率和准确率显著提高。王翔等[11]提出一种柔性 约束谱聚类框架，引入大量硬约束和软约束信息 建立新的约束优化问题，有效提高聚类准确率， 但是不具备约束关系传递。基于约束信息的半监 督聚类算法，通常能获取数据的约束关系是非常 有限的，通过约束传递来获得大量可靠的成对约 束信息，可显著提高半监督聚类的性能。余志文 等 [12]提出一种增强型半监督聚类集成框架 (incremental semi-supervised clustering ensemble，ISSCE)， 采用卢志武等[ 1 3 ]提出的约束传递方法，即基于 k 近邻图的标签传播方法，将少量标签样本的监 督信息传递给未标签样本，但如果相似度错误反 映数据点之间的相似性，会造成约束关系的错误 传递。传统的谱聚类及上述大部分半监督谱聚类 算法均需要存储数据的相似度矩阵且对拉普拉斯 矩阵进行特征分解，空间和时间的计算复杂度比 较高，在处理大规模数据集时计算代价难以承受。 为了提升谱聚类的扩展性，蔡登等[14]提出基于地 标点表示的谱聚类算法，通过数据点与地标点之 间的相似度矩阵乘积来近似得到整体数据点的相 似度矩阵，然后利用近似性质实现快速特征分解。 本文将采用基于地标点近似表示的方法，通 过稀疏表示构造的相似度矩阵对柔性约束谱聚类 算法模型[11]进行改进，并且根据约束集合内地标 点的关系，利用 Tarjan 算法[15]自动检测连通区域， 在每个连通区域内部动态调整近邻点，传递约束 关系，从而更新稀疏表示矩阵提高聚类准确率。 在 5 个大规模标准数据集上进行实验的结果表 明，本文算法对这些大规模数据具有较好适应 性，且在有效降低算法复杂度的同时，保证了约 束谱聚类算法结果的准确率。 1 算法基本原理 1.1 约束 NCut 算法 X = {xi} n i=1 , xi ∈ R d Dii = ∑ j Wi j L = I− D −1/2W D−1/2 对于数据集 ，数据之间的相 似度矩阵为 W，度矩阵 D 为对角阵，其内元素表 示为 ，规范化拉普拉斯矩阵表示为 ，I 表示单位矩阵。 标准 NCut 的目标函数为 argmin v∈Rn v T Lv, s.t.v T v = 1, v⊥1 (1) 式中 v 表示松弛化的类指示向量。 Q 假设已知“必连”约束集合 M 与“勿连”约束集 合 C，文献[11]根据约束信息生成约束矩阵 ，可 表示为 Qi j= 1, (xi , xj) ∈ M −1, (xi , xj) ∈ C 0, 无约束信息 (2) 通过式 (3) 来衡量 Q 中约束关系与 v 的一致程度： v TQv = ∑n i=1 ∑n j=1 vivjQi j (3) v ∈ R n Q ∈ R n×n xi xj Q Q v TQv Q v TQv ⩾ α 定义软约束 ， ，如果数据 和 是 同一类，那么 为正；否则为负。 的绝对值表示 约束权重， 的值越大，表明 v 与 中的约束信 息就越一致。基于上述软约束，不一定要严格满 足每个指定的约束条件，忽略部分约束信息可降 低计算开销，通过用户指定阈值来确定约束的下 界值，即 。 约束 NCut 的目标函数为 argmin v∈ n v T Lv, s.t.v TQv ⩾ α, v T v = 1, v⊥1 (4) O ( n 2 ) O ( n 3 ) 上述问题可转化为求解矩阵的特征向量[11] ， 但是空间和时间复杂度分别为 和 ，对于 大规模数据集，计算复杂度过高；而且不具备约 束传递功能，不能充分利用有限的约束信息。 1.2 依据稀疏表示的相似度矩阵 X ≈ YZ xi xˆi 蔡登等[14]提出基于图稀疏表示的谱聚类算 法，通过地标点的线性组合来实现所有数据点 X 的近似表示 。对于给定的任一数据点 ，其近似数据点 可以表示为 xˆi = ∑p j=1 Zjiyj (5) yj Y ∈ R d×p Zji Z ∈ R 式中： 是 的列向量， 是 p×n的第 j 行 第 i 列元素。 ·856· 智 能 系 统 学 报 第 13 卷
第5期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·857· 如果x越接近y,Z:会越大，如果y,不在数据 L,和Lp分别表示在同一个连通区域内的数 点x:的r近邻内，可设Z:为0，所以可生成一个稀 据p:和p,的r近邻集合，P,P∈Ta,i,je{1,2,…,T。 疏表示矩阵Z。Yo∈R表示Y的子矩阵，由x的 因为矩阵Z具有高度稀疏性，在同一个连通区域 r近邻组成，Z计算见式(6)： 内的两个数据点p:和p,可能并没有共同近邻点。 K(xiy;) Zi= 所以可考虑对于T内的任一数据点P,将其他数 ∑OKxJ7) i∈1,2，…，n,j∈(i） (6) 据点peT的近邻点也作为p:的近邻点： 式中：K(是核函数，较常用的是高斯核函数 Lp Lm ULp:U...ULnl,ie1.2.....ITal (9) - K(xy)=e;o表示带宽。 根据式(8)、(9)进行约束关系的传递，对矩阵2进 在获得矩阵Z后，可以构造两种形式的图，即 行更新： G=ZZ和S=ZZT,计算立=DPZ,D为对角矩 (i,pj)=lookup Vec (10) 阵，其内元素D=∑乙，所以规范化图的相似度 式中：ieLp,peTa,freq:=freq,i是p,的近邻点， 它出现的频率freq:等于按照升序排列后的频率 矩阵可表示为G=2r2eRam和3=22r∈Rxp,计算 freqz,存储在向量degree Vec中。 G的时间复杂度为O(pm2),计算$的时间复杂度为 2.2 依据稀疏表示的可扩展半监督NCut算法 O(np2)(pn). 根据1.2节所提出的基于稀疏表示建立的相 似度矩阵可知，G=22是数据X的规范化相似度 2所提算法 矩阵，经过2.1节的约束关系传递，已经实现对矩 2.1约束关系传递 阵2的更新，相似度矩阵G也随着更新，且包含更 将在“必连”和“勿连”约束集合中的数据点视 多的约束信息，能够有效地提高聚类结果。 为地标点，其个数为P。根据约束关系生成一个 依据稀疏表示的约束NCut目标函数可表示为 p×p的相似度矩阵，利用Tarjan算法检测强连通 arg miny'Lv,s.t.yOv>a,v'v =1,v11 (11) 区域，会生成多个连通区域；对每个连通区域，动 式中L=I-GeR是规范化的图拉普拉斯矩阵。 态调整其内数据的近邻点，进行约束关系的传 基于文献[11]提出的方法，上述问题的求解 递，对基于地标点近似表示方法中的稀疏表示矩 可以松弛为一般的特征值求解问题： 阵2进行更新。 Lv=A(2-BD)v (12) 根据约束信息所生成的相似度矩阵，利用 式中B是a的下界。 Tarjan算法检测生成H个强连通区域，可表示为 求解式(12)特征向量的时间复杂度为O(π)， T={TUT2UUTa},其中ae(1,2,…,},T1=p, 所以在处理大规模数据集时计算负担过大。为了 T表示第a个连通区域，包含T个数据点，T:表示 使该方法具有可扩展性，能较好地适应于大规模 T的补集，T≡{p.∈Tlp。生T,同一个连通区域内 数据集，根据1.2可知，基于稀疏表示的方法还可 的数据之间相似度最大，在不同连通区域的数据 之间的相似度最小，设置为 以构造另外一种规范化图，其相似度矩阵表示为 2-&hb 3=22T∈Rw,若能将S引入到上述约束NCut的 (7 目标函数中，可以大大降低求解特征向量的时间 每个数据点均有r个近邻点，L.∈R表示 复杂度。因此可将veR表示为2Tu,其中ueRP。 在T内每个数据点与其近邻点之间的稀疏表示矩 将v=2u代入到式(11)。改进后的可扩展约束 阵2集合，依次计算每个近邻点i∈{1,2，…，的出 NCut目标函数可表示为 现次数freq,并且按照升序进行排列，生成一个 argminu Au,s.t.uOu>a,uSu =1,1TSu=0 (13) ER m维的向量degree Vec=(freqr,freq,…,freqm),m是 式中：A=3-$3,0=Z02。 L近邻点出现次数不同的个数，出现次数较多的 该模型等价于式(I1)所表示的约束NCut目 近邻点是P。∈T最近的邻居点，依据线性插值策 标函数，但是有两个改进：一是规范化的拉普拉 略，生成一个m维的lookupVec向量： 斯矩阵LeRm变为矩阵A∈RPP;二是约束矩阵 max-min min+freq x- m≠1 lookupVec.= m-1 (8) QeR变为0∈RP,因为p《n,有效降低了计算 (max,m=1 复杂度。同样和文献[11]所提出的约束Ncut模型 式中：min和max分别表示Lz.中最大和最小相似 相比，一方面，通过地标点所构造的稀疏表示矩 度，∈{1,2，…，m}。 阵来近似获得相似度矩阵，避免对整个数据进行
xi yj Zji yj xi Zji Y⟨i⟩ ∈ R d×r xi Zji 如果 越接近 ， 会越大，如果 不在数据 点 的 r 近邻内，可设 为 0，所以可生成一个稀 疏表示矩阵 Z。 表示 Y 的子矩阵，由 的 r 近邻组成， 计算见式 (6)： Zji = K(xi , yj) ∑ j ′∈⟨i⟩ K(xi , yj ′ ) , i ∈ 1,2,··· ,n, j ∈ ⟨i⟩ (6) K(·) K(xi , yj) = e −∥xi−y j∥ 2σ2 σ 式中： 是核函数，较常用的是高斯核函数 ； 表示带宽。 G =Z T Z S = ZZT Zˆ = D −1/2Z Dii = ∑ j Zi j Gˆ =Zˆ T Zˆ ∈ R n×n Sˆ = Zˆ Zˆ T ∈ R p×p Gˆ O ( pn2 ) Sˆ O ( np2 ) (p ≪ n) 在获得矩阵 Z 后，可以构造两种形式的图，即 和 ，计算 ， D 为对角矩 阵，其内元素 ，所以规范化图的相似度 矩阵可表示为 和 ，计算 的时间复杂度为 ，计算 的时间复杂度为 。 2 所提算法 2.1 约束关系传递 p× p Zˆ 将在“必连”和“勿连”约束集合中的数据点视 为地标点，其个数为 p。根据约束关系生成一个 的相似度矩阵，利用 Tarjan 算法检测强连通 区域，会生成多个连通区域；对每个连通区域，动 态调整其内数据的近邻点，进行约束关系的传 递，对基于地标点近似表示方法中的稀疏表示矩 阵 进行更新。 |H| T ≡ {T1 ∪T2 ∪ ··· ∪Ta} a ∈ {1,2,··· ,|H|} |T| = p Ta T|a| T ′ a Ta T ′ a ≡ { p ′ a ∈ T|p ′ a < Ta } 根据约束信息所生成的相似度矩阵，利用 Tarjan 算法检测生成 个强连通区域，可表示为 ，其中 ， ， 表示第 a 个连通区域，包含 个数据点， 表示 的补集， ，同一个连通区域内 的数据之间相似度最大，在不同连通区域的数据 之间的相似度最小，设置为 Zˆ ( pi , pj ) = { 1, { pi ∈ Ta|pj ∈ Ta } 0, { pi ∈ Ta|pj ∈ T ′ a } (7) LTa ∈ R r×|Ta| Ta Zˆ i ∈ {1,2,··· ,r} freqi degreeVec = ( freq1 ′ ,freq2 ′ ,··· ,freqm′ ) LTa pa ∈ Ta 每个数据点均有 r 个近邻点， 表示 在 内每个数据点与其近邻点之间的稀疏表示矩 阵 集合，依次计算每个近邻点 的出 现次数 ，并且按照升序进行排列，生成一个 m 维的向量 ，m 是 近邻点出现次数不同的个数，出现次数较多的 近邻点是 最近的邻居点，依据线性插值策 略，生成一个 m 维的 lookupVec 向量： lookupVeci ′ = min+freqi ′ × max−min m−1 , m , 1 max, m = 1 (8) LTa i ′ ∈ {1,2,··· ,m} 式中：min 和 max 分别表示 中最大和最小相似 度， 。 Lpi Lpj pi pj pi , pj ∈ Ta i, j ∈ {1,2,··· ,|Ta|} pi pj Ta pi pj ∈ Ta pi 和 分别表示在同一个连通区域内的数 据 和 的 r 近邻集合， ， 。 因为矩阵 Z 具有高度稀疏性，在同一个连通区域 内的两个数据点 和 可能并没有共同近邻点。 所以可考虑对于 内的任一数据点 ，将其他数 据点 的近邻点也作为 的近邻点： Lpi = { Lp1 ∪ Lp2 ∪ ··· ∪ Lp|a| } , i ∈ 1,2,··· ,|Ta| (9) 根据式 (8)、(9) 进行约束关系的传递，对矩阵 Zˆ 进 行更新： Zˆ ( i, pj ) = lookupVeci ′ (10) i ∈ Lpj pj ∈ Ta freqi = freqi ′ pj freqi freqi ′ degreeVec 式中： ， ， ，i 是 的近邻点， 它出现的频率 等于按照升序排列后的频率 ，存储在向量 中。 2.2 依据稀疏表示的可扩展半监督 NCut 算法 Gˆ =Zˆ T Zˆ Zˆ Gˆ 根据 1.2 节所提出的基于稀疏表示建立的相 似度矩阵可知， 是数据 X 的规范化相似度 矩阵，经过 2.1 节的约束关系传递，已经实现对矩 阵 的更新，相似度矩阵 也随着更新，且包含更 多的约束信息，能够有效地提高聚类结果。 依据稀疏表示的约束 NCut 目标函数可表示为 argmin v∈Rn v T Lv¯ , s.t.v TQv ⩾ α, v T v = 1, v⊥1 (11) L¯ = I−Gˆ ∈ R 式中 n×n是规范化的图拉普拉斯矩阵。 基于文献[11]提出的方法，上述问题的求解 可以松弛为一般的特征值求解问题： Lv = λ(Q−βI) v (12) 式中 β 是α的下界。 O ( n 3 ) Sˆ = Zˆ Zˆ T ∈ R p×p Sˆ v ∈ R n Zˆ Tu u ∈ R p v = Zˆ Tu 求解式 (12) 特征向量的时间复杂度为 ， 所以在处理大规模数据集时计算负担过大。为了 使该方法具有可扩展性，能较好地适应于大规模 数据集，根据 1.2 可知，基于稀疏表示的方法还可 以构造另外一种规范化图，其相似度矩阵表示为 ，若能将 引入到上述约束 NCut 的 目标函数中，可以大大降低求解特征向量的时间 复杂度。因此可将 表示为 ，其中 。 将 代入到式 (11)。改进后的可扩展约束 NCut 目标函数可表示为 argmin u∈Rp u TAu, s.t.u TQuˆ ⩾ α,u TSuˆ = 1,1 TSuˆ = 0 (13) A = Sˆ −SˆSˆ, 式中： Qˆ = ZQˆ Zˆ T。 L ∈ R n×n A ∈ R p×p Q ∈ R n×n Qˆ ∈ R p×p p ≪ n 该模型等价于式 (11) 所表示的约束 NCut 目 标函数，但是有两个改进：一是规范化的拉普拉 斯矩阵 变为矩阵 ；二是约束矩阵 变为 ，因为 ，有效降低了计算 复杂度。同样和文献[11]所提出的约束 Ncut 模型 相比，一方面，通过地标点所构造的稀疏表示矩 阵来近似获得相似度矩阵，避免对整个数据进行 第 5 期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·857·
·858· 智能系统学报 第13卷 特征分解，大大降低算法的复杂度，能够很好地 根据lookupVec更新2； 适应于大规模数据集；另一方面，在连通区域内 end for 部进行约束关系传递，更新矩阵2，改进模型即式 5)依据约束关系生成约束矩阵Q,计算 (13)中S和A也随着更新，可以充分利用初始有限 3=22r,0=202r; 的约束信息，提高聚类的准确率。 6)求解Ox=ySx的最大特征值ymx; 为了求解式(13)，引入拉格朗日乘子，可扩展 7)ifB>ymax,类label的向量V=O; 约束NCut问题转化为 8)else求解式(16)的特征向量； A(u.Ap)=uAu-a(u'Qu-a)-u(u"Su-1)(14) 9)找出所有正特征值所对应的特征向量{u, 需要满足KKT条件，即 1 {u中每个元素乘 Au-AOu-uSu=0 (15) u Su uQu >a 10)去掉{u中与1S不正交的特征向量； uSu =1 I1)计算uA,寻找m个特征向量使Au,最 1TSu=0 小，m=min{k-1,lu,并把这些特征向量作为 ≥0 V的列向量； A(u"Qu-a)=0 12)计算V=2rV(I-VrAV),并对其进行k- 当A=0时，式(15)变为Au-S=0,意昧着并 means聚类。 没有考虑相关约束信息，所以为了充分使用约束 2.3算法复杂度分析 信息，只考虑>0的情况，即⑨u=a。 基于地标点近似表示的谱聚类算法需要构造 假设B=-兑式(15)变为 稀疏矩阵Z,该步骤的时间复杂度为O(pm),对矩 Au=a(0-BS)u 阵Z进行奇异值分解获得相似度矩阵的特征向 (16) 量，该步骤的时间复杂度为O(p3+p2m)；所提算法 通过求解式(16)的特征值和特征向量，计算复杂 也要构造矩阵Z,生成个连通区域进行近邻点 度远远降低。 约束关系传递的时间复杂度为O(⑩，计算矩阵 还需要考虑如何设置参数B和α，由于矩阵 S的时间复杂度为0(p2m,求解式(16)的特征值计 A是半正定的，可得 算复杂度为0(p),远远小于文献[11]约束谱聚类 F(@-B的)u=A(a-B)≥0 算法特征分解所需要的时间复杂度On),p≤n, 即参数B是a的下界值，a作为约束的下界值，所以 计算2Q2T的时间复杂度为O(kp2+kpm)。 只需要指定参数B值即可，参数B可调意味着算法 对噪声等额外信息的处理更加灵活。为了保证 3实验与分析 式(16)有i个有意义的特征向量，需要满足B<Y, 3.1实验环境 其中y,表示Ox=y3x的第i个最大的特征值。 为了验证本文算法的性能，选取规模较大的 算法结合稀疏表示与约束传递的半监督谱 数据集进行实验，依次为物体图像数据集 聚类算法 COIL100,人脸数据集CMU-PIE,手写数字数据 输入数据集X,约束集合M和C,聚类个 集USPS、MNIST和UCI标准库中的森林植被类 数k,参数B; 数据集CoverType,数据集的特性如表1所示。仿 输出类label。 真实验基于MATLAB2014b平台，计算机的硬件 1)将在约束集合内的p个点选为地标点，并 配置为Intel i7-4770CPU3.40GHz、16 GB RAM. 作为矩阵U的列向量； 表1实验数据集的特性 2)根据式(6)构造Z,并计算2=D-12Z Table 1 Experimental datasets features 3)使用Tarjan算法，根据地标点之间的约束 关系计算连通区域CC; 数据集 数据集个数 类 维数 4)for每个连通区域CCdo: COIL100 7200 100 1024 计算连通区域的邻接子矩阵L; USPS 9298 10 256 根据近邻点出现频率的次数构建向量Iook- CMU-PIE 11554 68 1024 upVec; MNIST 70000 10 784 根据式(9)将约束关系传递给该区域内剩余 CoverType 581012 7 54 数据点；
Zˆ Sˆ A 特征分解，大大降低算法的复杂度，能够很好地 适应于大规模数据集；另一方面，在连通区域内 部进行约束关系传递，更新矩阵 ，改进模型即式 (13) 中 和 也随着更新，可以充分利用初始有限 的约束信息，提高聚类的准确率。 为了求解式 (13)，引入拉格朗日乘子，可扩展 约束 NCut 问题转化为 Λ(u, λ, µ) = u TAu−λ ( u TQuˆ −α ) −µ ( u TSuˆ −1 ) (14) 需要满足 KKT 条件，即 Au−λQuˆ −µSuˆ = 0 (15) u TQuˆ ⩾ α u TSuˆ = 1 1 TSuˆ = 0 λ ⩾ 0 λ ( u TQuˆ −α ) = 0 λ = 0 Au−µSuˆ = 0 λ > 0 u TQuˆ = α 当 时，式 (15) 变为 ，意味着并 没有考虑相关约束信息，所以为了充分使用约束 信息，只考虑 的情况，即 。 β = − µ λ 假设 ，式 (15) 变为 Au = λ ( Qˆ −βSˆ ) u (16) 通过求解式 (16) 的特征值和特征向量，计算复杂 度远远降低。 还需要考虑如何设置参数 β 和α，由于矩阵 A 是半正定的，可得 λu T ( Qˆ −βSˆ ) u = λ(α−β) ⩾ 0 β α α β β β < γi γi Qˆ x = γSˆ x 即参数 是 的下界值， 作为约束的下界值，所以 只需要指定参数 值即可，参数 可调意味着算法 对噪声等额外信息的处理更加灵活。为了保证 式 (16) 有 i 个有意义的特征向量，需要满足 ， 其中 表示 的第 i 个最大的特征值。 算法 结合稀疏表示与约束传递的半监督谱 聚类算法 β 输入 数据集 X，约束集合 M 和 C，聚类个 数 k，参数 ； 输出 类 label。 1) 将在约束集合内的 p 个点选为地标点，并 作为矩阵 U 的列向量； Zˆ =D −1/2 2) 根据式 (6) 构造 Z，并计算 Z ； 3) 使用 Tarjan 算法，根据地标点之间的约束 关系计算连通区域 CC； 4) for 每个连通区域 CC do： 计算连通区域的邻接子矩阵 LTa； 根据近邻点出现频率的次数构建向量 lookupVec； 根据式 (9) 将约束关系传递给该区域内剩余 数据点； 根据 lookupVec 更新 Zˆ ； end for Q Sˆ = Zˆ Zˆ T Qˆ = ZQˆ Zˆ T 5) 依据约束关系生成约束矩阵 ，计算 ， ； Qˆ x = γSˆ 6) 求解 x的最大特征值 γmax； 7) if β ⩾ γmax，类 label 的向量 V =Ø； 8) else 求解式 (16) 的特征向量 u； { u + i } { u + i } √ 1 uiSuˆ i 9) 找出所有正特征值所对应的特征向量 ， 中每个元素乘 ； { u + i } 1 10) 去掉 中与 TSˆ不正交的特征向量； u T i Aui u T i Aui m = min{ k−1, { u + i } } V 11) 计算 ，寻找 m 个特征向量使 最 小 ， ，并把这些特征向量作为 的列向量； V (r) = Zˆ TV ( I−V TAV) 12) 计算 ，并对其进行 kmeans 聚类。 2.3 算法复杂度分析 Z O(pn) O ( p 3 + p 2n ) |H| O(r|H|) Sˆ O ( p 2n ) O ( p 3 ) O(n 3 ), p ≪ n ZQˆ Zˆ T O ( kp2 +kpn) 基于地标点近似表示的谱聚类算法需要构造 稀疏矩阵 ，该步骤的时间复杂度为 ，对矩 阵 Z 进行奇异值分解获得相似度矩阵的特征向 量，该步骤的时间复杂度为 ；所提算法 也要构造矩阵 Z，生成 个连通区域进行近邻点 约束关系传递的时间复杂度为 ，计算矩阵 的时间复杂度为 ，求解式 (16) 的特征值计 算复杂度为 ，远远小于文献[11]约束谱聚类 算法特征分解所需要的时间复杂度 ， 计算 的时间复杂度为 。 3 实验与分析 3.1 实验环境 为了验证本文算法的性能，选取规模较大的 数据集进行实验，依次为物体图像数据 集 COIL100，人脸数据集 CMU-PIE，手写数字数据 集 USPS、MNIST 和 UCI 标准库中的森林植被类 数据集 CoverType，数据集的特性如表 1 所示。仿 真实验基于 MATLAB2014b 平台，计算机的硬件 配置为 Intel i7-4770 CPU 3.40 GHz、16 GB RAM。 表 1 实验数据集的特性 Table 1 Experimental datasets features 数据集 数据集个数 类 维数 COIL100 7 200 100 1 024 USPS 9 298 10 256 CMU-PIE 11 554 68 1 024 MNIST 70 000 10 784 CoverType 581 012 7 54 ·858· 智 能 系 统 学 报 第 13 卷
第5期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·859· 本文算法和文献[11]的约束谱聚类方法CSP, PC算法相比，本文算法在CMU-PIE数据集上 文献[14]的基于地标点采样的快速谱聚类算法 ACC、NMⅡ分别提升了79.12%和38.58%.在Cov- LSC-R和LSC-K,文献[I5]所提出的针对大规模数 erType数据集上ACC和NMI分别提升了15.02% 据集的半监督谱聚类算法SC-PC进行对比，LSC- 和39.94%。因为在处理高维数据时，采用稀疏表 R是通过随机采样来获取p个地标点，LSC-K是 示能够过滤一些异常点和噪声，同时指定约束下 利用k-means算法来获得p个地标点。须指出， 界，可去除一些噪声等约束关系的负面影响。因 由于CSP算法在CMU-PIE、MNIST和Cover- 此，引入约束信息来改变谱聚类算法的目标函 Type数据集上计算负担过大，并没有进行相关实 数，并通过在连通区域内进行约束关系传递，能 验的比较。 够有效提高聚类的准确率。 鉴于比较的公平性，具体的参数设置如下：其 表2各数据集实验结果 中文献[14-15]和本文算法的地标点个数p均设置 Table 2 Experimental results of different datasets 为1000，所有算法中k-means部分的迭代次数均 数据集 算法 ACC NMI 时间/s 设置为500，所有稀疏表示矩阵构造过程中的近 CSP 0.67390.8237 19656.02 邻点个数r设置为5。约束的下界即参数B=Boyk-1, 其中A=05+04x号为0：=5：的第k-1个最 LSC-K0.54560.7632 4.13 COIL100 LSC-R0.4896 0.7315 2.33 大的特征值。 SC-PC 0.59680.7718 2.59 通过数据集中每个样本预定义的类标签来实 现对聚类结果的评价，采用聚类准确率ACC和归 本文 0.66600.7975 3.51 一化互信息NM两种度量指标对聚类结果进 CSP 0.86440.8049 26932.75 行评估和比较分析。两个评价指标的取值范围均 LSC-K0.77530.7915 1.19 是在0~1之间，值越大表示聚类效果越好。 USPS LSC-R0.75240.7541 0.62 3.2实验分析 SC-PC 0.80740.7697 0.75 各种算法在上述数据集的实验结果如表2 本文 0.84350.7731 1.88 所示。 CSP 根据表2可以看出，约束谱聚类算法CSP在 LSC-K 0.0956 0.2126 COL100和USPS两个数据集上的ACC和NMI 5.39 均取得最佳结果，因为其考虑引入约束矩阵建立 CMU-PIE LSC-R 0.09360.2148 4.48 约束优化问题，提高聚类准确率，但是在上述两 SC-PC 0.17240.2623 4.84 个数据集上的运行时间太长，耗时将近5~7h,对 本文 0.30880.3635 6.45 于更大的数据集CMU-PIE、MNIST和Cover- CSP Type数据集，计算负担过大，没能进行验证。本 LSC-K0.72700.7222 12.58 文算法在COIL100和USPS数据集的ACC分别 MNIST LSC-R0.5890 0.5911 8.80 为0.6660和0.8435，NMI指标分别为0.7975和 SC-PC 0.73440.6978 11.08 0.7731,和CSP相比稍有降低；但从运行时间上， 本文 0.78390.6728 24.98 本文算法的运行时间仅在秒级别，耗时分别为 CSP 3.51s和1.88s,远远少于CSP的运行时间，而且 在包含581012个样本的大规模CoverType数据 LSC-K 0.2552 0.0673 355.11 集上运行时间只需要747.36s,所以本文算法基于 CoverType LSC-R 0.22900.0681 78.18 稀疏表示矩阵来建立相似度矩阵，降低了矩阵分 SC-PC0.2563 0.0721 149.71 解的复杂度，提高了半监督聚类算法的可扩展性。 本文0.29480.1009 747.36 另一方面，本文算法和LSC-K、LSC-R、SC-PC 三种均为提升谱聚类的效率的算法，即快速谱聚 为了分析初始约束信息对聚类结果的影响， 类算法相比，在准确率ACC和归一化互信息NM 添加了地标点个数p(对应半监督聚类中能获取的 两个指标上有所提高，且在CMU-PIE和Cover- 初始约束信息)对聚类指标影响的对比实验。同 Type数据集上两个指标具有明显的提升；和SC 样，CSP算法只在USPS和COIL1O0两个数据集
本文算法和文献[11]的约束谱聚类方法 CSP， 文献[14]的基于地标点采样的快速谱聚类算法 LSC-R 和 LSC-K，文献[15]所提出的针对大规模数 据集的半监督谱聚类算法 SC-PC 进行对比，LSCR 是通过随机采样来获取 p 个地标点，LSC-K 是 利用 k-means 算法来获得 p 个地标点。须指出， 由于 CSP 算法在 CMU-PIE、MNIST 和 CoverType 数据集上计算负担过大，并没有进行相关实 验的比较。 β = β0γk−1 β0 = 0.5+0.4× p n γk−1 Qˆ x = γSˆ x k−1 鉴于比较的公平性，具体的参数设置如下：其 中文献[14-15]和本文算法的地标点个数 p 均设置 为 1 000，所有算法中 k-means 部分的迭代次数均 设置为 500，所有稀疏表示矩阵构造过程中的近 邻点个数 r 设置为 5。约束的下界即参数 ， 其中 ， 为 的第 个最 大的特征值。 通过数据集中每个样本预定义的类标签来实 现对聚类结果的评价，采用聚类准确率 ACC 和归 一化互信息 NMI 两种度量指标[14]对聚类结果进 行评估和比较分析。两个评价指标的取值范围均 是在 0~1 之间，值越大表示聚类效果越好。 3.2 实验分析 各种算法在上述数据集的实验结果如表 2 所示。 根据表 2 可以看出，约束谱聚类算法 CSP 在 COIL100 和 USPS 两个数据集上的 ACC 和 NMI 均取得最佳结果，因为其考虑引入约束矩阵建立 约束优化问题，提高聚类准确率，但是在上述两 个数据集上的运行时间太长，耗时将近 5~7 h，对 于更大的数据集 CMU-PIE、MNIST 和 CoverType 数据集，计算负担过大，没能进行验证。本 文算法在 COIL100 和 USPS 数据集的 ACC 分别 为 0.666 0 和 0.843 5，NMI 指标分别为 0.797 5 和 0.773 1，和 CSP 相比稍有降低；但从运行时间上， 本文算法的运行时间仅在秒级别，耗时分别为 3.51 s 和 1.88 s，远远少于 CSP 的运行时间，而且 在包含 581 012 个样本的大规模 CoverType 数据 集上运行时间只需要 747.36 s，所以本文算法基于 稀疏表示矩阵来建立相似度矩阵，降低了矩阵分 解的复杂度，提高了半监督聚类算法的可扩展性。 另一方面，本文算法和 LSC-K、LSC-R、SC-PC 三种均为提升谱聚类的效率的算法，即快速谱聚 类算法相比，在准确率 ACC 和归一化互信息 NMI 两个指标上有所提高，且在 CMU-PIE 和 CoverType 数据集上两个指标具有明显的提升；和 SCPC 算法相比，本文算法在 CMU-PIE 数据集上 ACC、NMI 分别提升了 79.12% 和 38.58%，在 CoverType 数据集上 ACC 和 NMI 分别提升了 15.02% 和 39.94%。因为在处理高维数据时，采用稀疏表 示能够过滤一些异常点和噪声，同时指定约束下 界，可去除一些噪声等约束关系的负面影响。因 此，引入约束信息来改变谱聚类算法的目标函 数，并通过在连通区域内进行约束关系传递，能 够有效提高聚类的准确率。 为了分析初始约束信息对聚类结果的影响， 添加了地标点个数 p(对应半监督聚类中能获取的 初始约束信息) 对聚类指标影响的对比实验。同 样，CSP 算法只在 USPS 和 COIL100 两个数据集 表 2 各数据集实验结果 Table 2 Experimental results of different datasets 数据集 算法 ACC NMI 时间/s COIL100 CSP 0.673 9 0.823 7 19 656.02 LSC-K 0.545 6 0.763 2 4.13 LSC-R 0.489 6 0.731 5 2.33 SC-PC 0.596 8 0.771 8 2.59 本文 0.666 0 0.797 5 3.51 USPS CSP 0.864 4 0.804 9 26 932.75 LSC-K 0.775 3 0.791 5 1.19 LSC-R 0.752 4 0.754 1 0.62 SC-PC 0.807 4 0.769 7 0.75 本文 0.843 5 0.773 1 1.88 CMU-PIE CSP — — — LSC-K 0.095 6 0.212 6 5.39 LSC-R 0.093 6 0.214 8 4.48 SC-PC 0.172 4 0.262 3 4.84 本文 0.308 8 0.363 5 6.45 MNIST CSP — — — LSC-K 0.727 0 0.722 2 12.58 LSC-R 0.589 0 0.591 1 8.80 SC-PC 0.734 4 0.697 8 11.08 本文 0.783 9 0.672 8 24.98 CoverType CSP — — — LSC-K 0.255 2 0.067 3 355.11 LSC-R 0.229 0 0.068 1 78.18 SC-PC 0.256 3 0.072 1 149.71 本文 0.294 8 0.100 9 747.36 第 5 期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·859·
·860· 智能系统学报 第13卷 上实现。p依次取200、500、800和1000。不同 0.30 …LSC-K +LSC-R 算法ACC和NMI的对比实验结果分别如图1、2 0.28 SC-PC 6本文算法 所示。 0.26 0.75 CSP 0.70 LSC-K 0.24 +LSC-R im- 0.65 SC-PC 。本文算法 0.22 0. <0.55 …0 020.30.40.50.60.70.80.90×10 参数p个数 0.50 (e)CoverType数据集 0.45 图1不同算法的ACC比较 0.4 0.20.30.4 050.60.70.80.9i0×10 Fig.1 Comparison of the ACCs of different algorithms 参数p个数 (a)COL100数据集 0.90 0.95r ◆CSP CSP 0.90 -LSC-K 0.85 LSC-K +LSC-R LSC-R -SC-PC 0.85 SC-PC 0.80本文算法 合本文算法 0 0.75 0.70 0.70 0.65 0.20.30.40.50.60.70.80.910×10 0.6 0.6 0.20.30.4 0.50.60.7 0.80.910×10 参数p个数 参数p个数 (b)USPS数据集 (a)C0L100数据集 0.90r 0.40 o LSC-K CSP 0.35 …o-LSC-K -+LSC-R 0.85 +LSC-R SC-PC 0.30 --SC-PC 合本文算法 0.80 合本文算法 三0.75 0.20 0.70 0.15 0.65 0.109 0.203040.50.60.70.80.90×10 0.0 0.6 0.20.30.4 0.50.60.70.80.90×10 参数p个数 参数p个数 (c)CMU-PIE数据集 (b)USPS数据集 0.40 0.85f LSC-K OLSC-K 0.80 +LSC-R 0.35 -LSC-R -SC-PC 0 SC-PC 0.75 合本文算法 0.30 合本文算法 2025 0.651 0 0.20 0.60 0.55 0.15 0.5 0.2030.40.50.60.70.80.9i0×10 0.1 0.20.30.4 050.60.70.80.90×10 参数p个数 参数p个数 (d)MNIST数据集 (c)CMU-PIE数据集
上实现。p 依次取 200、500、800 和 1 000。不同 算法 ACC 和 NMI 的对比实验结果分别如图 1、2 所示。 LSC-K LSC-R SC-PC 本文算法 0.20 0.22 0.24 0.26 0.28 0.30 ACC 参数 p 个数 (e) CoverType 数据集 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0×103 图 1 不同算法的 ACC 比较 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Fig. 1 Comparison of the ACCs of different algorithms 0.40 0.45 0.50 0.55 0.60 0.65 0.70 0.75 参数 p 个数 ACC CSP LSC-K LSC-R SC-PC 本文算法 CSP LSC-K LSC-R SC-PC 本文算法 0.65 0.60 0.70 0.75 0.80 0.85 0.90 0.95 ACC 0.05 0.10 0.15 0.20 0.25 0.30 0.35 0.40 ACC LSC-K LSC-R SC-PC 本文算法 (a) COIL100 数据集 参数 p 个数 (b) USPS 数据集 参数 p 个数 (c) CMU-PIE 数据集 ×103 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0×103 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0×103 LSC-K LSC-R SC-PC 本文算法 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 ACC 参数 p 个数 (d) MNIST 数据集 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0×103 0.65 0.70 0.75 0.80 0.85 0.90 参数 p 个数 NMI 0.65 0.60 0.70 0.75 0.80 0.85 0.90 NMI 0.10 0.15 0.20 0.25 0.30 0.35 0.40 NMI (a) COIL100 数据集 (b) USPS 数据集 (c) CMU-PIE 数据集 CSP LSC-K LSC-R SC-PC 本文算法 CSP LSC-K LSC-R SC-PC 本文算法 LSC-K LSC-R SC-PC 本文算法 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ×103 参数 p 个数 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ×103 参数 p 个数 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ×103 ·860· 智 能 系 统 学 报 第 13 卷
第5期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·861· 0.75 参考文献： 0.70 [1]VON Luxburg U.A tutorial on spectral clustering[J].Stat- 0.65 istics and computing,2007,17(4):395-416. 20.60 [2]SHI Jianbo,MALIK J.Normalized cuts and image seg- 0.55 LSC-K mentation[J.IEEE transactions on pattern analysis and +LSC-R 0.50 -BSC-PC machine intelligence,2000,22(8):888-905. 合本文算法 [3]HU Han,FENG Jianjiang,YU Chuan,et al.Multi-class 0.45品203040506070809i0*10 constrained normalized cut with hard,soft,unary and pair- 参数p个数 (d)MNIST数据集 wise priors and its applications to object segmentation[J]. 0.12r IEEE transactions on image processing,2013,22(11): LSC-K 4328-4340. 0.11 +LSC-R [4]刘建伟，刘媛，罗雄麟.半监督学习方法】.计算机学报 0.10 -SC-PC 6本文算法 2015,38(8):1592-1617. LIU Jianwei,LIU Yuan,LUO Xionglin.semi-supervised 0.084 learning methods[J].Chinese journal of computers,2015. 0.07 38(8):1592-1617 0.06 [5]ALUSH A,FRIEDMAN A,Goldberger J.Pairwise clus- 020304050.6070.809i0*10 0.0 tering based on the mutual-information criterion[J].Neuro- 参数p个数 computing,.2016,182:284-293 (e)CoverType数据集 [6]FORESTIER G,WEMMERT C.Semi-supervised learn- 图2不同算法的NMⅡ比较 ing using multiple clusterings with limited labeled data[J]. Fig.2 Comparison of the NMIs of different algorithms Information sciences,2016,361-362:48-65. 由图1可知，本文算法在5个数据集上的ACC [7]KAMVAR S D,KLEIN D,MANNING C D.Spectral 比LSC-K、LSC-R和SC-PC三种算法都要高，随 learning[C]//Proceedings of the 18th International Joint 着参数p个数增加，每种算法的ACC也随着增 Conference on Artificial Intelligence.Acapulco,Mexico, 2003:561-566. 加，说明ACC受p的选取影响很大。由图2可 知，在NMI指标上，本文算法和快速谱聚类算法 [8]蒋伟进，许字晖，王欣.基于谱图和成对约束的主动半监 相比，在CMU-PIE和CoverType两个数据集上具 督聚类算法[U.控制与决策，2013,28(6)：904-908. 有明显的优越性，同样随着p个数增多，每种算法 JIANG Weijin,XU Yuhui,WANG Xin.Active semi-su- 的NMI都随着提高。总的来说，在p的不同取值 pervised clustering algorithm based-on pair-wise con- 情况下，本文算法能取得最好的聚类效果。 straints[J].Control and decision,2013,28(6):904-908. [9]DING Shifei,JIA Hongjie,ZHANG Liwen,et al.Re- 4结束语 search of semi-supervised spectral clustering algorithm based on pairwise constraints[J].Neural computing and ap- 随着规模庞大、结构复杂数据的不断出现， plications,.2014,241):211-219 对其聚类往往耗费大量的时间，同时多数半监督 [10]CUCURINGU M.KOUTIS I,CHAWLA S.et al.Simple 谱聚类算法存在没有充分利用初始约束信息的问 and scalable constrained clustering:a generalized spectral 题。本文通过稀疏表示改进约束谱聚类算法的目 method[C]//Proceedings of the 19th International Confer- 标函数，根据初始约束信息生成连通区域，在每 ence on Artificial Intelligence and Statistics.Cadiz,Spain, 个连通区域内动态调整近邻点进行约束关系传 2016:445-454. 递。实验结果表明，本文算法在提高聚类准确率 [11]WANG Xiang,QIAN Buyue,DAVIDSON I.On con- 的同时能有效降低聚类复杂度，能够较好地适用 strained spectral clustering and its applications[J].Data 于大规模数据集。但是本文算法的聚类准确率受 mining and knowledge discovery,2014,28(1):1-30. 采样地标点的个数和选取方法影响比较大，接下 [12]YU Zhiwen,LUO Peinan,YOU J,et al.Incremental 来可以针对该问题开展进一步的研究工作。 semi-supervised clustering ensemble for high dimension-
由图 1 可知，本文算法在 5 个数据集上的 ACC 比 LSC-K、LSC-R 和 SC-PC 三种算法都要高，随 着参数 p 个数增加，每种算法的 ACC 也随着增 加，说明 ACC 受 p 的选取影响很大。由图 2 可 知，在 NMI 指标上，本文算法和快速谱聚类算法 相比，在 CMU-PIE 和 CoverType 两个数据集上具 有明显的优越性，同样随着 p 个数增多，每种算法 的 NMI 都随着提高。总的来说，在 p 的不同取值 情况下，本文算法能取得最好的聚类效果。 4 结束语 随着规模庞大、结构复杂数据的不断出现， 对其聚类往往耗费大量的时间，同时多数半监督 谱聚类算法存在没有充分利用初始约束信息的问 题。本文通过稀疏表示改进约束谱聚类算法的目 标函数，根据初始约束信息生成连通区域，在每 个连通区域内动态调整近邻点进行约束关系传 递。实验结果表明，本文算法在提高聚类准确率 的同时能有效降低聚类复杂度，能够较好地适用 于大规模数据集。但是本文算法的聚类准确率受 采样地标点的个数和选取方法影响比较大，接下 来可以针对该问题开展进一步的研究工作。 参考文献： VON Luxburg U. A tutorial on spectral clustering[J]. Statistics and computing, 2007, 17(4): 395–416. [1] SHI Jianbo, MALIK J. Normalized cuts and image segmentation[J]. IEEE transactions on pattern analysis and machine intelligence, 2000, 22(8): 888–905. [2] HU Han, FENG Jianjiang, YU Chuan, et al. Multi-class constrained normalized cut with hard, soft, unary and pairwise priors and its applications to object segmentation[J]. IEEE transactions on image processing, 2013, 22(11): 4328–4340. [3] 刘建伟, 刘媛, 罗雄麟. 半监督学习方法[J]. 计算机学报, 2015, 38(8): 1592–1617. LIU Jianwei, LIU Yuan, LUO Xionglin. semi-supervised learning methods[J]. Chinese journal of computers, 2015, 38(8): 1592–1617. [4] ALUSH A, FRIEDMAN A, Goldberger J. Pairwise clustering based on the mutual-information criterion[J]. Neurocomputing, 2016, 182: 284–293. [5] FORESTIER G, WEMMERT C. Semi-supervised learning using multiple clusterings with limited labeled data[J]. Information sciences, 2016, 361-362: 48–65. [6] KAMVAR S D, KLEIN D, MANNING C D. Spectral learning[C]//Proceedings of the 18th International Joint Conference on Artificial Intelligence. Acapulco, Mexico, 2003: 561–566. [7] 蒋伟进, 许宇晖, 王欣. 基于谱图和成对约束的主动半监 督聚类算法[J]. 控制与决策, 2013, 28(6): 904–908. JIANG Weijin, XU Yuhui, WANG Xin. Active semi-supervised clustering algorithm based-on pair-wise constraints[J]. Control and decision, 2013, 28(6): 904–908. [8] DING Shifei, JIA Hongjie, ZHANG Liwen, et al. Research of semi-supervised spectral clustering algorithm based on pairwise constraints[J]. Neural computing and applications, 2014, 24(1): 211–219. [9] CUCURINGU M, KOUTIS I, CHAWLA S, et al. Simple and scalable constrained clustering: a generalized spectral method[C]//Proceedings of the 19th International Conference on Artificial Intelligence and Statistics. Cadiz, Spain, 2016: 445–454. [10] WANG Xiang, QIAN Buyue, DAVIDSON I. On constrained spectral clustering and its applications[J]. Data mining and knowledge discovery, 2014, 28(1): 1–30. [11] YU Zhiwen, LUO Peinan, YOU J, et al. Incremental semi-supervised clustering ensemble for high dimension- [12] 0.50 0.45 0.55 0.60 0.65 0.70 0.75 NMI 0.05 0.08 0.07 0.06 0.09 0.10 0.11 0.12 NMI (d) MNIST 数据集 (e) CoverType 数据集 LSC-K LSC-R SC-PC 本文算法 LSC-K LSC-R SC-PC 本文算法 参数 p 个数 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0×103 参数 p 个数 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0×103 图 2 不同算法的 NMI 比较 Fig. 2 Comparison of the NMIs of different algorithms 第 5 期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·861·
·862· 智能系统学报 第13卷 al data clustering[J].IEEE transactions on knowledge and 作者简介： data engineering,2016,28(3):701-714. 赵晓晓，女，1993年生，硕士研究 [13]LU Zhiwu,PENG Yuxin.Exhaustive and efficient con- 生，主要研究方向为数据挖掘。 straint propagation:a graph-based learning approach and its applications[J].International journal of computer vis- ion,2013.103(3):306-325. [14]CAI Deng,CHEN Xinlei.Large scale spectral clustering via landmark-based sparse representation[J].IEEE trans- 周治平，男，1962年生，教授，博 actions on cybernetics,2015,45(8):1669-1680. 土，主要研究方向为智能检测、自动化 [15]SEMERTZIDIS T,RAFAILIDIS D,STRINTZIS M G,et 装置、网路安全。发表学术论文80余篇。 al.Large-scale spectral clustering based on pairwise con- straints[J].Information processing and management, 2015,51(5):616-624. 机电一体化、控制和机器人技术国际会议(ICMCR2019) 2019 2nd International Conference on Mechatronics,Control and Robotics (ICMCR 2019) 2019 2nd International Conference on Mechatronics,Control and Robotics will be held in Fukuoka Insti- tute of Technology,Fukuoka,during February 23-25,2019.It aims to provide a forum for researchers,practi- tioners,and professinals from the industry,academia and government who are working in the field of mechatronics,con- trol and robotics to discourse on research and development,professional practice in related fields. ICMCR 2019 is also the Annual Meeting of JOACE editorial board,so it also serves to bring authors and editors of JOACE together to communicate face to face and discuss their latest research results and future development of JOACE. Best Presentation Award:Selection of the best paper will be made at the conference based on both the technical content and presentation.The winner will be chosen by the Session Chair in consultaton with the Conference Chairs and the Best Presentation Certificate will be awarded
al data clustering[J]. IEEE transactions on knowledge and data engineering, 2016, 28(3): 701–714. LU Zhiwu, PENG Yuxin. Exhaustive and efficient constraint propagation: a graph-based learning approach and its applications[J]. International journal of computer vision, 2013, 103(3): 306–325. [13] CAI Deng, CHEN Xinlei. Large scale spectral clustering via landmark-based sparse representation[J]. IEEE transactions on cybernetics, 2015, 45(8): 1669–1680. [14] SEMERTZIDIS T, RAFAILIDIS D, STRINTZIS M G, et al. Large-scale spectral clustering based on pairwise constraints[J]. Information processing and management, 2015, 51(5): 616–624. [15] 作者简介： 赵晓晓，女，1993 年生，硕士研究 生，主要研究方向为数据挖掘。 周治平，男，1962 年生，教授，博 士，主要研究方向为智能检测、自动化 装置、网络安全。发表学术论文 80 余篇。 机电一体化、控制和机器人技术国际会议（ICMCR 2019） 2019 2nd International Conference on Mechatronics, Control and Robotics (ICMCR 2019) 2019 2nd International Conference on Mechatronics, Control and Robotics will be held in Fukuoka Institute of Technology, Fukuoka, during February 23–25, 2019. It aims to provide a forum for researchers, practitioners, and professinals from the industry, academia and government who are working in the field of mechatronics, control and robotics to discourse on research and development, professional practice in related fields. ICMCR 2019 is also the Annual Meeting of JOACE editorial board, so it also serves to bring authors and editors of JOACE together to communicate face to face and discuss their latest research results and future development of JOACE. Best Presentation Award: Selection of the best paper will be made at the conference based on both the technical content and presentation. The winner will be chosen by the Session Chair in consultaton with the Conference Chairs and the Best Presentation Certificate will be awarded. ·862· 智 能 系 统 学 报 第 13 卷
第5期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·863· 可信网络交易系统的理论创新与实践推进 《网络交易风险控制理论》书评 王怀清 香港城市大学信息系统学系，中国香港 随着电子商务的迅猛发展，网络交易遭受恶意攻击、网络钓鱼以及交易欺诈等愈加严重。网络交易平台 的关键技术、监管能力及手段明显不足。蒋昌俊教授领衔的科研团队对可信网络交易系统的理论和实践进 行了多年深入的研究，取得了一系列可喜的研究成果，并收于《网络交易风险控制理论》一书。该书对网 络交易系统的现状进行了深入总结，对学术界和工业界常用的可信保障技术进行了全面介绍，并提出了具 有“行为”特色的认证机制，以及一系列的基于模型的风险防控方法。该书内容丰富、资料翔实、逻辑严密， 是基于信息学科研究网络交易风险防控的一本好书。 近年来，随着网络技术的发展，以及“互联网+”相关政策的支持，网络交易作为新的商业模式发展异常 迅速。据中国互联网络信息中心统计，截至2017年12月，我国网民规模达7.72亿，其中，网络购物用户达 5.53亿，相较2016年增长了14.3%，占网民总体的69.1%；使用网上支付的用户规模也达5.31亿。网络交易 的持续高速发展也带了诸多的安全问题，比如恶意攻击、木马劫持等对网络交易造成了巨大的伤害，其中， 2017年遇到网络钓鱼以及各类交易欺诈的用户占比较2016年有所升高，快递服务和电商网站相关维权搜索 量占比最大。据360猎网平台分析，金融理财诈骗是举报数量最多的类型，虚假购物紧随其后。针对上述问 题，蒋昌俊教授及其团队经过多年的研究，在相关项目的支持下，取得了有价值的成果，并汇总成《网络交 易风险控制理论》一书，该书研究内容系统全面，研究特色凸显，是目前笔者读到的基于信息学科研究网络 交易风险控制的第一本专著。 《网络交易风险控制理论》研究内容系统全面，由蒋昌俊教授和于汪洋博士合著，于2018年3月出版， 该书从信息技术角度，介绍了网络交易风险防控的理论和相关技术，首次将行为认证引入网络交易的可信 保障，开展了行为认证技术在网络交易系统中的应用研究，形成了网络交易支付系统风险防控关键技术的 整套理论与方法，并研制了大规模网络交易风险防控系统平台。 全书共分为8章。第1章介绍了目前国内外网络交易的现状，对学术界、业界常用的可信保障技术进行 了全面的总结，并提出了相关问题，指出传统的安全技术和身份认证方法已不足以应对开放网络环境下新 的风险挑战，研究基于行为的认证理论有望取得创新性的成果。第2章则介绍了该书中用到的领域内基本 知识，为后面章节的展开进行铺垫，其中，形式化模型是重要的一环，因为要对并发的网络交易系统行为进 行准确地刻画，Pi网、自动机等形式化模型必不可少。对于网络交易这一并发软件系统，其行为是依托于 业务流程的，所以对于网络交易流程的刻画至关重要，因而该书第3章着重介绍了业务系统的相关知识，并 突出了作者团队提出的基于Peti网的两种形式化模型，这些成果均已发表于国内外知名期刊，具有一定的 影响力。第4章、第5章则开始涉及基于行为的认证理论，针对软件系统的行为认证和用户的行为认证，作 者提出了大量创新性的理论和方法，融合了服务器端和客户端的可信认证，同时也涉及测试技术、系统评估 和身份认证等现有的风险防控技术。基于上述理论，作者研究团队开发了大规模网络交易风险防控系统平 台，监控技术是核心。第6章介绍了监控平台的框架、核心技术和异常处理机制等。 随着国内互联网金融经济的发展，互联网征信受到越来越多的重视。征信也是风险防控的重要一环，对 用户信用的掌握可以有效减少网络交易的风险。因此，第7章主要介绍了征信系统的基本原理和架构。最 后，作者用了3个案例研究来结束该书。总的来说，该书内容丰富，覆盖全面，结构清晰，逻辑通顺，将网络 交易风险控制的现状、理论、方法进行了科学的整理和阐述。 该书研究特色凸显，一大特色是提出了网络交易风险防控的行为认证技术，建立了交易系统行为和用户 行为的规范与模式，通过采集和分析用户在系统中的行为足迹，建立了基于模型的行为认证机制，有效提高
可信网络交易系统的理论创新与实践推进 ——《网络交易风险控制理论》书评 王怀清 香港城市大学信息系统学系，中国 香港 随着电子商务的迅猛发展，网络交易遭受恶意攻击、网络钓鱼以及交易欺诈等愈加严重。网络交易平台 的关键技术、监管能力及手段明显不足。蒋昌俊教授领衔的科研团队对可信网络交易系统的理论和实践进 行了多年深入的研究，取得了一系列可喜的研究成果，并收于《网络交易风险控制理论》一书。该书对网 络交易系统的现状进行了深入总结，对学术界和工业界常用的可信保障技术进行了全面介绍，并提出了具 有“行为”特色的认证机制，以及一系列的基于模型的风险防控方法。该书内容丰富、资料翔实、逻辑严密， 是基于信息学科研究网络交易风险防控的一本好书。 近年来，随着网络技术的发展，以及“互联网+”相关政策的支持，网络交易作为新的商业模式发展异常 迅速。据中国互联网络信息中心统计，截至 2017 年 12 月，我国网民规模达 7.72 亿，其中，网络购物用户达 5.53 亿，相较 2016 年增长了 14.3%，占网民总体的 69.1%；使用网上支付的用户规模也达 5.31 亿。网络交易 的持续高速发展也带了诸多的安全问题，比如恶意攻击、木马劫持等对网络交易造成了巨大的伤害，其中， 2017 年遇到网络钓鱼以及各类交易欺诈的用户占比较 2016 年有所升高，快递服务和电商网站相关维权搜索 量占比最大。据 360 猎网平台分析，金融理财诈骗是举报数量最多的类型，虚假购物紧随其后。针对上述问 题，蒋昌俊教授及其团队经过多年的研究，在相关项目的支持下，取得了有价值的成果，并汇总成《网络交 易风险控制理论》一书，该书研究内容系统全面，研究特色凸显，是目前笔者读到的基于信息学科研究网络 交易风险控制的第一本专著。 《网络交易风险控制理论》研究内容系统全面，由蒋昌俊教授和于汪洋博士合著，于 2018 年 3 月出版， 该书从信息技术角度，介绍了网络交易风险防控的理论和相关技术，首次将行为认证引入网络交易的可信 保障，开展了行为认证技术在网络交易系统中的应用研究，形成了网络交易支付系统风险防控关键技术的 整套理论与方法，并研制了大规模网络交易风险防控系统平台。 全书共分为 8 章。第 1 章介绍了目前国内外网络交易的现状，对学术界、业界常用的可信保障技术进行 了全面的总结，并提出了相关问题，指出传统的安全技术和身份认证方法已不足以应对开放网络环境下新 的风险挑战，研究基于行为的认证理论有望取得创新性的成果。第 2 章则介绍了该书中用到的领域内基本 知识，为后面章节的展开进行铺垫，其中，形式化模型是重要的一环，因为要对并发的网络交易系统行为进 行准确地刻画，Petri 网、自动机等形式化模型必不可少。对于网络交易这一并发软件系统，其行为是依托于 业务流程的，所以对于网络交易流程的刻画至关重要，因而该书第 3 章着重介绍了业务系统的相关知识，并 突出了作者团队提出的基于 Petri 网的两种形式化模型，这些成果均已发表于国内外知名期刊，具有一定的 影响力。第 4 章、第 5 章则开始涉及基于行为的认证理论，针对软件系统的行为认证和用户的行为认证，作 者提出了大量创新性的理论和方法，融合了服务器端和客户端的可信认证，同时也涉及测试技术、系统评估 和身份认证等现有的风险防控技术。基于上述理论，作者研究团队开发了大规模网络交易风险防控系统平 台，监控技术是核心。第 6 章介绍了监控平台的框架、核心技术和异常处理机制等。 随着国内互联网金融经济的发展，互联网征信受到越来越多的重视。征信也是风险防控的重要一环，对 用户信用的掌握可以有效减少网络交易的风险。因此，第 7 章主要介绍了征信系统的基本原理和架构。最 后，作者用了 3 个案例研究来结束该书。总的来说，该书内容丰富，覆盖全面，结构清晰，逻辑通顺，将网络 交易风险控制的现状、理论、方法进行了科学的整理和阐述。 该书研究特色凸显，一大特色是提出了网络交易风险防控的行为认证技术，建立了交易系统行为和用户 行为的规范与模式，通过采集和分析用户在系统中的行为足迹，建立了基于模型的行为认证机制，有效提高 第 5 期 赵晓晓，等：结合稀疏表示与约束传递的半监督谱聚类算法 ·863·
·864· 智能系统学报 第13卷 了网络交易风险防控的实时性，降低了误判率，克服了交易欺诈的高辨识和强实时的难题。其中，行为认证 的核心技术在于形式化模型的构建。在当前人工智能和大数据的背景下，使用形式化方法进行建模和分析 必不可少，基于严格的数学定义和分析可以最大程度地发现问题并解决问题，不仅能发现已知的缺陷，还能 发现未知的缺陷，为风险防控的高效实施提供模型基础。蒋昌俊教授及其团队在形式化领域耕耘多年，有 着深厚的理论积淀，尤其在Pei网的理论和应用方面，成就斐然，培养了一大批杰出人才。将适于刻画并发 系统的Peri网应用于网络交易系统的风险防控，水到渠成。同时，该书也不拘泥于Petri网这一种形式化模 型，根据不同的应用场景，行为认证技术也涉及了自动机、马尔科夫模型等广泛使用的理论和方法，为网络 交易的风险防控奠定了坚实的理论基础。 除了理论上的创新，该书的研究还进行了工业实践方面的探索，并卓有成效。据我所知，蒋昌俊教授领 衔的团队在进行上述理论研究的过程中，得到了国家自然科学基金委和科技部多个项目的支持，并与国内 领先的网络交易平台（支付宝、快钱、中国工商银行等单位）建立了良好的合作关系。对于支付宝等网络交 易企业来说，在进行海量交易的同时，如何高效准确地对每笔交易进行风险判别，是亟待解决的问题，而传 统的以数字证书为核心的安全技术已不足以应对。该书的研究恰好契合了业界的需要，作者所在团队的科 研人员与支付宝等知名企业进行了长期的合作研究，部分人员常驻支付宝，将理论研究的成果进行实践应 用，与企业共同对风控系统进行升级和优化，攻克了大规模、高并发、强实时交易的若干关键问题，并搭建了 大规模分布式的网络交易风险防控平台。这是产学研结合的不错尝试，是在企业业务场景和技术基础上， 借力高校的理论创新优势，向前迈进的一步，对交易风险的精准判定和瞬时识别具有重要的意义。 网络交易已成为国民经济的重要组成部分，其中的安全可信问题越发凸显，如何在技术层面有效控制风 险是一个关键的科学问题。该著作的研究紧紧契合这一科学问题，将网络交易风险控制的现状、理论、方法 进行了科学的整理和阐述，既有现有的成熟技术，又有独创的理论方法，对互联网金融风险控制具有很强的 启发、借鉴和指导作用，同时对信息技术领域的相关研究人员、学者也具有参考价值，对计算机软件理论与 软件安全专业的学生也不失为一本开拓视野的参考书。 笔者非常愿意将此书推荐给对网络交易风险防控感兴趣的学者及工业界。同时，感谢作者在这一领域 所进行的研究，期盼作者能够出更多的优秀成果
了网络交易风险防控的实时性，降低了误判率，克服了交易欺诈的高辨识和强实时的难题。其中，行为认证 的核心技术在于形式化模型的构建。在当前人工智能和大数据的背景下，使用形式化方法进行建模和分析 必不可少，基于严格的数学定义和分析可以最大程度地发现问题并解决问题，不仅能发现已知的缺陷，还能 发现未知的缺陷，为风险防控的高效实施提供模型基础。蒋昌俊教授及其团队在形式化领域耕耘多年，有 着深厚的理论积淀，尤其在 Petri 网的理论和应用方面，成就斐然，培养了一大批杰出人才。将适于刻画并发 系统的 Petri 网应用于网络交易系统的风险防控，水到渠成。同时，该书也不拘泥于 Petri 网这一种形式化模 型，根据不同的应用场景，行为认证技术也涉及了自动机、马尔科夫模型等广泛使用的理论和方法，为网络 交易的风险防控奠定了坚实的理论基础。 除了理论上的创新，该书的研究还进行了工业实践方面的探索，并卓有成效。据我所知，蒋昌俊教授领 衔的团队在进行上述理论研究的过程中，得到了国家自然科学基金委和科技部多个项目的支持，并与国内 领先的网络交易平台 (支付宝、快钱、中国工商银行等单位) 建立了良好的合作关系。对于支付宝等网络交 易企业来说，在进行海量交易的同时，如何高效准确地对每笔交易进行风险判别，是亟待解决的问题，而传 统的以数字证书为核心的安全技术已不足以应对。该书的研究恰好契合了业界的需要，作者所在团队的科 研人员与支付宝等知名企业进行了长期的合作研究，部分人员常驻支付宝，将理论研究的成果进行实践应 用，与企业共同对风控系统进行升级和优化，攻克了大规模、高并发、强实时交易的若干关键问题，并搭建了 大规模分布式的网络交易风险防控平台。这是产学研结合的不错尝试，是在企业业务场景和技术基础上， 借力高校的理论创新优势，向前迈进的一步，对交易风险的精准判定和瞬时识别具有重要的意义。 网络交易已成为国民经济的重要组成部分，其中的安全可信问题越发凸显，如何在技术层面有效控制风 险是一个关键的科学问题。该著作的研究紧紧契合这一科学问题，将网络交易风险控制的现状、理论、方法 进行了科学的整理和阐述，既有现有的成熟技术，又有独创的理论方法，对互联网金融风险控制具有很强的 启发、借鉴和指导作用，同时对信息技术领域的相关研究人员、学者也具有参考价值，对计算机软件理论与 软件安全专业的学生也不失为一本开拓视野的参考书。 笔者非常愿意将此书推荐给对网络交易风险防控感兴趣的学者及工业界。同时，感谢作者在这一领域 所进行的研究，期盼作者能够出更多的优秀成果。 ·864· 智 能 系 统 学 报 第 13 卷
