·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]提出一种增强型半监督聚类集成框架 (incre￾mental 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 卷