【知识工程】半监督类保持局部线性嵌入方法

第16卷第1期 智能系统学报 Vol.16 No.1 2021年1月 CAAI Transactions on Intelligent Systems Jan.2021 D0:10.11992tis.202003007 半监督类保持局部线性嵌入方法 邓廷权，王强 (哈尔滨工程大学数学科学学院，黑龙江哈尔滨150001) 摘要：为使局部线性嵌入(local linear embedding,LLE)这一无监督高维数据的非线性特征提取方法提取出的 特征在分类或聚类学习上更优，提出一种半监督类保持局部线性嵌入(semi-supervised class preserving local lin- ear embedding,SSCLLE)的非线性特征提取方法。该方法将半监督信息融入到LLE中，首先对标记样本近邻赋 予伪标签，增大标记样本数量。其次，对标记样本之间的距离进行局部调整，缩小同类样本间距，扩大异类样 本间距。同时在局部线性嵌入优化目标函数中增加全局同类样本间距和异类样本间距的约束项，使得提取出 的低维特征可以确保同类样本点互相靠近，而异类样本点彼此分离。在一系列实验中，其聚类精确度以及可视 化效果明显高于无监督LLE和现有半监督流特征提取方法，表明该方法提取出的特征具有很好的类保持特性。 关键词：非线性特征提取；流形学习；半监督：标记信息；聚类；可视化 中图分类号：TP181文献标志码：A文章编号：1673-4785(2021)01-0098-10 中文引用格式：邓廷权，王强.半监督类保持局部线性嵌入方法几.智能系统学报，2021,16(1)：98-107. 英文引用格式：DENGTingquan,WANG Qiang.Semi-supervised class preserving locally linear embedding.CAAItransactions on intelligent systems,2021,16(1):98-107. Semi-supervised class preserving locally linear embedding DENG Tingquan,WANG Qiang (College of Mathematical Sciences,Harbin engineering university,Harbin 150001,China) Abstract:To make local linear embedding(LLE),the nonlinear feature extraction method for unsupervised high-dimen- sional data,more optimal in classification or clustering learning,we propose a nonlinear semi-supervised class pre- serving local linear embedding (SSCLLE)feature extraction method.This method integrates semi-supervised informa- tion into LLE.First,pseudo-labels are assigned to the nearby neighbors of the labeled samples to increase the number of labeled samples.Second,the distance between the labeled samples is partially adjusted to reduce the distance between similar samples and expand the distance between heterogeneous samples.Simultaneously,the constraints of the glob- ally same sample spacing and heterogeneous sample spacing are added in the local linear embedding optimization ob- jective function so that the extracted low-dimensional features can ensure that the same sample points are near each oth- er,whereas the heterogeneous sample points are separated from each other.In a series of experiments,the clustering ac- curacy and visualization effect of the proposed method are significantly higher than those of unsupervised LLE and the existing semi-supervised flow feature extraction methods,indicating that the features extracted by this method have good class retention characteristics. Keywords:nonlinear feature extraction;manifold learning;semi-supervised;labeled information;clustering;visualiza- tion 随着信息科技的迅速发展，数据规模的爆炸 点，为数据挖掘带来了空前的挑战。特征提取作 式增长成为了大数据时代的主要特征之一。在此 为处理高维数据的有效手段，通过提取数据的低 时代背景下，数据通常具有维数高和稀疏性等特 维特性，可以将高维特征空间映射到低维特征空 间中进行数据的分析和处理，通常分为线性特征 收稿日期：2020-03-04. 基金项目：国家自然科学基金项目(11471001,61872104). 提取和非线性特征提取2种方式。非线性特征提 通信作者：王强.E-mail:1005834631@qq.com, 取不依赖于线性假设，对于处理非线性结构的数

DOI: 10.11992/tis.202003007 半监督类保持局部线性嵌入方法 邓廷权，王强 （哈尔滨工程大学 数学科学学院，黑龙江 哈尔滨 150001） 摘 要：为使局部线性嵌入（local linear embedding, LLE）这一无监督高维数据的非线性特征提取方法提取出的 特征在分类或聚类学习上更优，提出一种半监督类保持局部线性嵌入 (semi-supervised class preserving local lin￾ear embedding, SSCLLE) 的非线性特征提取方法。该方法将半监督信息融入到 LLE 中，首先对标记样本近邻赋 予伪标签，增大标记样本数量。其次，对标记样本之间的距离进行局部调整，缩小同类样本间距，扩大异类样 本间距。同时在局部线性嵌入优化目标函数中增加全局同类样本间距和异类样本间距的约束项，使得提取出 的低维特征可以确保同类样本点互相靠近，而异类样本点彼此分离。在一系列实验中，其聚类精确度以及可视 化效果明显高于无监督 LLE 和现有半监督流特征提取方法，表明该方法提取出的特征具有很好的类保持特性。 关键词：非线性特征提取；流形学习；半监督；标记信息；聚类；可视化 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2021)01−0098−10 中文引用格式：邓廷权, 王强. 半监督类保持局部线性嵌入方法 [J]. 智能系统学报, 2021, 16(1): 98–107. 英文引用格式：DENG Tingquan, WANG Qiang. Semi-supervised class preserving locally linear embedding[J]. CAAI transactions on intelligent systems, 2021, 16(1): 98–107. Semi-supervised class preserving locally linear embedding DENG Tingquan，WANG Qiang (College of Mathematical Sciences, Harbin engineering university, Harbin 150001, China) Abstract: To make local linear embedding (LLE), the nonlinear feature extraction method for unsupervised high-dimen￾sional data, more optimal in classification or clustering learning, we propose a nonlinear semi-supervised class pre￾serving local linear embedding (SSCLLE) feature extraction method. This method integrates semi-supervised informa￾tion into LLE. First, pseudo-labels are assigned to the nearby neighbors of the labeled samples to increase the number of labeled samples. Second, the distance between the labeled samples is partially adjusted to reduce the distance between similar samples and expand the distance between heterogeneous samples. Simultaneously, the constraints of the glob￾ally same sample spacing and heterogeneous sample spacing are added in the local linear embedding optimization ob￾jective function so that the extracted low-dimensional features can ensure that the same sample points are near each oth￾er, whereas the heterogeneous sample points are separated from each other. In a series of experiments, the clustering ac￾curacy and visualization effect of the proposed method are significantly higher than those of unsupervised LLE and the existing semi-supervised flow feature extraction methods, indicating that the features extracted by this method have good class retention characteristics. Keywords: nonlinear feature extraction; manifold learning; semi-supervised; labeled information; clustering; visualiza￾tion 随着信息科技的迅速发展，数据规模的爆炸 式增长成为了大数据时代的主要特征之一。在此 时代背景下，数据通常具有维数高和稀疏性等特 点，为数据挖掘带来了空前的挑战。特征提取作 为处理高维数据的有效手段，通过提取数据的低 维特性，可以将高维特征空间映射到低维特征空 间中进行数据的分析和处理，通常分为线性特征 提取和非线性特征提取 2 种方式。非线性特征提 取不依赖于线性假设，对于处理非线性结构的数 收稿日期：2020−03−04. 基金项目：国家自然科学基金项目 (11471001，61872104). 通信作者：王强. E-mail: 1005834631@qq.com. 第 16 卷第 1 期 智 能 系 统 学 报 Vol.16 No.1 2021 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2021

·99· 邓廷权，等：半监督类保持局部线性嵌入方法 第1期 据效果较好，成为当前数据挖掘的热门方向之 低维特征矩阵，Y=yy…yT,y:∈R,dm。 一。流形学习6作为一种非线性特征提取方法， 对于每个数据点，计算每一个数据点x到其 应用了流形在局部结构上与欧氏空间同胚的性 它点的欧氏距离，找到最近的k个点作为该数据 质。通过对高维数据样本的分析来挖掘隐藏的本 样本的近邻，确定数据的k近邻域。也可采用ε 质结构，从而提取有效的低维特征。然而，流形 邻域方法确定数据的近邻点。 学习方法仍然存在一些不足，例如：流形学习方 假设任一点x都可用它的k近邻通过线性权值 法忽略了数据的类别标记信息，提取的特征并不 wj=1,2,…,k加权来得到，由以下优化问题求解 是分类上的最优特征。因此，忽略标记信息而提取 线性重构的权矩阵w=wTw…w]下=(wm,为 到的特征在进行数据聚类或分类时，结果往往与 实际存在较大差异。所以希望可以使用半监督 mins(w 的方法进行学习，即少量标记信息来指导特征提 (1) 取，同时又使用大量无标记信息的数据点来刻画 S.t. =1 =1 并保持样本的局部或全局几何、线性等结构。 容易获得优化问题式(1)的最优解： 局部线性嵌入(LLE)是一种无监督的流 rG 形学习方法，直接用它提取的特征进行数据挖掘 w:-MTG.T (2) 如聚类或分类得到的结果并不是很理想。因此我 式中：G:=(gy)是一个k×k的Gram矩阵（距离矩 们希望将数据集的标记信息引入到LLE方法中 阵)；g=(G-xax-);T=(1,1,…,1)F是一个 用以提高特征提取效果。而已有的一些半监督方 k×1的全1矩阵；x表示样本x的第I个近邻点。 法，例如半监督局部线性嵌人方法(semi-super- 记g1=x-x,则g5=gag。 vised locally linear embedding,SSLLE)虽然利用了 基于局部线性重构矩阵式(2)，构造优化问题： 标记信息对特征提取进行一定的改进，但它只考 虑了近邻点的标记信息做局部调整，因此当整体 mino(Y 标记信息较低时每个近邻中将有可能出现没有标 (3) 记点的情况。这时SSLLE将失去作用并且由于 st.∑yy=∑y=0 它只考虑近邻的这种调整，当标记信息很多时它 获得高维数据X的低维嵌入Y。 们整体的区分度也不大。本文在LLE的基础上 根据样本的邻域点分布将k维行向量w:扩 利用近邻伪标签赋予得到的标记信息作局部调 充成n维行向量W,记W=[WW灯…W]P,M= 整，同时从全局角度对同类数据点和异类数据 (I-W'(I-W,则优化问题式(3)的目标函数可化 点进行全局调整，使得重构数据低维特征空间 简为r(YTMY) 时，既保持局部线性结构，又能使提取后的数据 采用拉格朗日乘子法求解优化问题式(3)，可 在低维特征空间中可以实现具有相同标记信息的 得MY=AY。即式(3)可转化为求特征值问题。 数据点互相靠近，而标记不同的数据点彼此分 实对称半正定矩阵M的最小d个非0特征值对 离，从而达到更好的特征提取结果。最后通过聚 应的特征向量按列排列时，每行做成的向量的就 类分析及可视化证明本文方法的有效性。 是对应数据的低维特征：。 1局部线性嵌入 2半监督类保持局部线性嵌入方法 由Roweis等提出的LLE是一个经典的保持 在数据挖掘任务中，监督信息为用户提供强 局部线性特性的流形学习方法，可以有效提取高 有力的数据分析基础。然而，众多实际问题只能 维数据的低维特征。其基本原理为：假设数据是 获得少量样本的监督标记。半监督机器学习方法 分布在一个流形上的，任一点均可用它的近邻点 应运而生。 经由线性重构而得到。基于局部线性表示系数， LLE是一种经典的无监督高维数据特征提取 构造优化问题使得数据在高维原始空间到低维特 方法。本文在LLE基础上提出一种半监督类保 征空间的过程中局部线性重构权值不发生变化， 持局部线性嵌入方法(SSCLLE)。该方法不仅利 获得高维数据的低维特征。 用近邻伪标签赋予得到的标记信息调整近邻数据 假设数据集X={x,2,…,x}中有n个样本点 间的距离，而且从全局角度加入了同类数据点和 x,x:∈Rm,ie[l,川，YeRd为特征提取后获得的n个 异类数据点的全局约束，使提取后的数据在低维

据效果较好，成为当前数据挖掘的热门方向之 一。流形学习[1-6] 作为一种非线性特征提取方法， 应用了流形在局部结构上与欧氏空间同胚的性 质。通过对高维数据样本的分析来挖掘隐藏的本 质结构，从而提取有效的低维特征。然而，流形 学习方法仍然存在一些不足，例如：流形学习方 法忽略了数据的类别标记信息，提取的特征并不 是分类上的最优特征。因此，忽略标记信息而提取 到的特征在进行数据聚类或分类时，结果往往与 实际存在较大差异。所以希望可以使用半监督[7-14] 的方法进行学习，即少量标记信息来指导特征提 取，同时又使用大量无标记信息的数据点来刻画 并保持样本的局部或全局几何、线性等结构。 局部线性嵌入 (LLE)[15] 是一种无监督[16] 的流 形学习方法，直接用它提取的特征进行数据挖掘 如聚类或分类得到的结果并不是很理想。因此我 们希望将数据集的标记信息引入到 LLE 方法中 用以提高特征提取效果。而已有的一些半监督方 法，例如半监督局部线性嵌入方法 (semi-super￾vised locally linear embedding, SSLLE) 虽然利用了 标记信息对特征提取进行一定的改进，但它只考 虑了近邻点的标记信息做局部调整，因此当整体 标记信息较低时每个近邻中将有可能出现没有标 记点的情况。这时 SSLLE 将失去作用并且由于 它只考虑近邻的这种调整，当标记信息很多时它 们整体的区分度也不大。本文在 LLE 的基础上 利用近邻伪标签赋予得到的标记信息作局部调 整，同时从全局[17] 角度对同类数据点和异类数据 点进行全局调整，使得重构数据低维特征空间 时，既保持局部线性结构，又能使提取后的数据 在低维特征空间中可以实现具有相同标记信息的 数据点互相靠近，而标记不同的数据点彼此分 离，从而达到更好的特征提取结果。最后通过聚 类分析及可视化证明本文方法的有效性。 1 局部线性嵌入 由 Roweis 等提出的 LLE 是一个经典的保持 局部线性特性的流形学习方法，可以有效提取高 维数据的低维特征。其基本原理为：假设数据是 分布在一个流形上的，任一点均可用它的近邻点 经由线性重构而得到。基于局部线性表示系数， 构造优化问题使得数据在高维原始空间到低维特 征空间的过程中局部线性重构权值不发生变化， 获得高维数据的低维特征。 X = {x1, x2,··· , xn} xi xi ∈ R m i ∈ [1,n] Y ∈ R n×d n 假设数据集 中有 n 个样本点 , , , 为特征提取后获得的 个 Y = [y T 1 y T 2 ··· y T n ] T yi ∈ R d 低维特征矩阵， ， ,d ≪ m 。 xi ε 对于每个数据点，计算每一个数据点 到其 它点的欧氏距离，找到最近的 k 个点作为该数据 样本的近邻，确定数据的 k 近邻域。也可采用 邻域方法确定数据的近邻点。 xi wi j, j = 1,2,··· , k w = [w T 1 w T 2 ··· w T n ] T = (wi j)k×n 假设任一点 都可用它的 k 近邻通过线性权值 加权来得到，由以下优化问题求解 线性重构的权矩阵 ，为 minε(w) = ∑n i=1 xi − ∑k j=1 wi jxj 2 s.t. ∑k j=1 wi j = 1 (1) 容易获得优化问题式 (1) 的最优解： wi = Γ TG −1 i ΓTG−1 i Γ (2) Gi = (g i l j) k×k Gram g i l j = (xi − xil)(xi − xi j) T Γ = (1,1,··· ,1)T k×1 xil xi gil = xi − xil g i l j = gil g T i j 式中： 是一个 的 矩阵 (距离矩 阵 )； ； 是一个 的全 1 矩阵； 表示样本 的第 l 个近邻点。 记 ，则 。 基于局部线性重构矩阵式 (2)，构造优化问题： minσ(Y) = ∑n i=1 yi − ∑k j=1 wi jyj 2 s.t. ∑n i=1 y T i yi = I, ∑n i=1 yi = 0 (3) 获得高维数据 X 的低维嵌入 Y。 wi Wi W = [WT 1 WT 2 ··· WT n ] T M = (I−W) T (I−W) tr( Y TMY) 根据样本的邻域点分布将 k 维行向量 扩 充成 n 维行向量 ，记 ， ，则优化问题式 (3) 的目标函数可化 简为 。 MY = λY yi 采用拉格朗日乘子法求解优化问题式 (3)，可 得 。即式 (3) 可转化为求特征值问题。 实对称半正定矩阵 M 的最小 d 个非 0 特征值对 应的特征向量按列排列时，每行做成的向量的就 是对应数据的低维特征 。 2 半监督类保持局部线性嵌入方法 在数据挖掘任务中，监督信息为用户提供强 有力的数据分析基础。然而，众多实际问题只能 获得少量样本的监督标记。半监督机器学习方法 应运而生。 LLE 是一种经典的无监督高维数据特征提取 方法。本文在 LLE 基础上提出一种半监督类保 持局部线性嵌入方法 (SSCLLE)。该方法不仅利 用近邻伪标签赋予得到的标记信息调整近邻数据 间的距离，而且从全局角度加入了同类数据点和 异类数据点的全局约束，使提取后的数据在低维 ·99· 邓廷权，等：半监督类保持局部线性嵌入方法 第 1 期

第16卷 智能系统学报 ·100· 特征空间中可以实现具有相同标记信息的数据点 CL={(x,x≠l(x)≠1(x川 互相靠近，而标号不同的数据点彼此分离，达到 分别构造同类样本项偏差和异类样本项偏差： 更好的特征提取效果。 ha=∑aa d(yy)=yyl 假设X是一个半监督数据集，其中少部分数 据样本带有标记（类别标签）。记X是有标签的 Ja.= ∑waaf6.）=-yf 数据组成的集合，1(x)e{1,2…,f是X中各数据 式中d(,y)表示低维特征y:与y之间的欧氏距离。 点所对应的标签，L=l(x),lx2),…,l(x)》,f是数据 本文的目的是要求同类样本项偏差尽量小， 集的类数。 同时确保异类样本项偏差尽可能的大。 一般情况下，X中的样本量较少。在流形学 构造半监督数据集X中每一个数据样本点的 习中，少量监督样本不能全面描述和刻画数据的 线性重构权值。利用数据中已有的标记信息以及 局部和全局流形结构，致使学习到的特征不能准 新标记的标记信息来重新调整距离矩阵，从而使 确反映数据的内在特性。本文给出一种近邻伪标 得构造的数据点的邻域更加有利于提取优质的特征。 签赋予的方法，给部分未标记样本赋予伪标签， (1-r）g,1(x）=l(x) 增大标记样本量。 (1+r)g,1(x)≠x） (4) 将所有标记样本X的各自近邻中的未标记 点设置与标记点相同的初标签，然后对这些初标 g,x和x至少一个无标号 签点进行筛选。如果这个未标记点只赋予了一个 式中0<1。 标签，则将此标签设定为这个点的伪标签。如果 从式(4)可以看出，如果2个样本有相同的类 这个未标记点有2个以上的伪标签，把这个点的 标，则将其距离缩小。如果2个样本有不同的类 所有初标签都去掉，该点依然设定为未标记点， 标，则将其距离扩大。在其他情况下，样本点间 如图1所示。 的距离保持不变。 重置式(2)中的距离矩阵为G=(g),其中 g0=8l8T。 再由(2)计算样本点的邻域局部线性重构权 矩阵由此利用标记信息得到改进后的新重构权矩 阵w=(w)0 基于以上分析，构造如下优化问题： 2 图1近邻伪标签赋值方法示意 minp(Y)= Fig.1 Schematic diagram of nearest neighbor pseudo la- 11 bel assignment method d(yi.yj)- 在图1的左图中，红色和绿色的点分别代表 (xT))eML (5) 标记点(2类)，蓝色是无标签的点。经过上述近 (1-∑(yy） (t-)eCL 邻伪标签赋值方法后，只有一类标记信息的近邻 点保留赋予的标签（右图新增加的红色点和绿色 s.t. ∑=0,2=1 点)，而有2种（或多种）标记的近邻点则依旧标为 该优化问题式(5)的目标函数由3部分组 无标记点，保持其蓝色不变（右图大圆中的2个蓝 成。第1项形式上虽然和LLE相同，但其中的重 色点)。得到的新标签数据为X,则有标签的数 构权矩阵包含了样本点的半监督信息，能够确保 据组成的集合为X=[X,X],对应的新标签集合为 提取出的特征既保持数据的局部线性结构不变 L={),1(x2),…,1(x),l(x+i…lx*}o 又能在局部上使类内（同类）数据更紧密，并对类 新增加的伪标签虽然不是真实的标签，但由 间（异类）数据进行分离的效果。第2项和第3项 于其与被标注样本具有很好的近邻关系，通过这 分别是全局同类样本偏差和全局异类样本偏差， 样的扩充可增加标记信息的量，有利于更好地描 目的是确保同类样本偏差最小，同时确保全局异 述数据的内在结构，发现样本中隐藏的鉴别能力。 类样本偏差最大，参数α∈(0,1)是2个偏差项的 为了构造出利用全局信息进行调整的优化问 平衡系数，权衡同类样本项和异类样本项对目标 题，首先定义同类数据点对集合： 函数的影响。B也是一个平衡参数，用于调节局 ML={(x,xi≠方l(x)=l(x》 部线性重构对于目标函数的影响。 和异类数据点对集合： 式（⑤）的约束条件与LLE相同，确保提取出

特征空间中可以实现具有相同标记信息的数据点 互相靠近，而标号不同的数据点彼此分离，达到 更好的特征提取效果。 X Xc l(x) ∈ {1,2,··· , f} Xc L = {l(x1),l(x2),··· ,l(xs)} 假设 是一个半监督数据集，其中少部分数 据样本带有标记 (类别标签)。记 是有标签的 数据组成的集合， 是 中各数据 点所对应的标签， ，f 是数据 集的类数。 一般情况下， Xc 中的样本量较少。在流形学 习中，少量监督样本不能全面描述和刻画数据的 局部和全局流形结构，致使学习到的特征不能准 确反映数据的内在特性。本文给出一种近邻伪标 签赋予的方法，给部分未标记样本赋予伪标签， 增大标记样本量。 将所有标记样本 Xc 的各自近邻中的未标记 点设置与标记点相同的初标签，然后对这些初标 签点进行筛选。如果这个未标记点只赋予了一个 标签，则将此标签设定为这个点的伪标签。如果 这个未标记点有 2 个以上的伪标签，把这个点的 所有初标签都去掉，该点依然设定为未标记点， 如图 1 所示。 图 1 近邻伪标签赋值方法示意 Fig. 1 Schematic diagram of nearest neighbor pseudo la￾bel assignment method Xw Xz = [Xc ,Xw] L = {l(x1),l(x2),··· ,l(xs),l(xs+1),···l(xs+t)} 在图 1 的左图中，红色和绿色的点分别代表 标记点 (2 类)，蓝色是无标签的点。经过上述近 邻伪标签赋值方法后，只有一类标记信息的近邻 点保留赋予的标签 (右图新增加的红色点和绿色 点)，而有 2 种 (或多种) 标记的近邻点则依旧标为 无标记点，保持其蓝色不变 (右图大圆中的 2 个蓝 色点)。得到的新标签数据为 ，则有标签的数 据组成的集合为 ,对应的新标签集合为 。 新增加的伪标签虽然不是真实的标签，但由 于其与被标注样本具有很好的近邻关系，通过这 样的扩充可增加标记信息的量，有利于更好地描 述数据的内在结构，发现样本中隐藏的鉴别能力。 为了构造出利用全局信息进行调整的优化问 题，首先定义同类数据点对集合： ML = { (xi , xj)|i , j,l(xi) = l(xj) } 和异类数据点对集合： CL = { (xi , xj)|i , j,l(xi) , l(xj) } 分别构造同类样本项偏差和异类样本项偏差： JML = ∑ (xi,xj)∈ML d 2 (yi , yj) = yi − yj 2 JCL = ∑ (xi,xj)∈CL d 2 (yi , yj) = yi − yj 2 d ( yi , yj ) 式中 表示低维特征 yi 与 yj 之间的欧氏距离。 本文的目的是要求同类样本项偏差尽量小， 同时确保异类样本项偏差尽可能的大。 构造半监督数据集 X 中每一个数据样本点的 线性重构权值。利用数据中已有的标记信息以及 新标记的标记信息来重新调整距离矩阵，从而使 得构造的数据点的邻域更加有利于提取优质的特征。 gi j ′ =    (1−r)gi j, l(xi) = l(xj) (1+r)gi j, l(xi) , l(xj) gi j, xi和xj至少一个无标号 (4) 式中 0<r<1。 从式 (4) 可以看出，如果 2 个样本有相同的类 标，则将其距离缩小。如果 2 个样本有不同的类 标，则将其距离扩大。在其他情况下，样本点间 的距离保持不变。 Gi ′ = (g i′ l j) g i′ l j = gil ′ gi j ′T 重置式 (2) 中的距离矩阵为 ，其中 。 w = (wi j) 再由 (2) 计算样本点的邻域局部线性重构权 矩阵由此利用标记信息得到改进后的新重构权矩 阵 。 基于以上分析，构造如下优化问题： minρ(Y) = β ∑n i=1 yi − ∑n j=1 wi jyj 2 + α ∑ (xi,xj)∈ML d 2 (yi , yj)− (1−α) ∑ (xi,xj)∈CL d 2 (yi , yj) s.t. ∑n i=1 yi = 0 , ∑n i=1 y T i yi = I (5) α ∈ (0,1) 该优化问题式 (5) 的目标函数由 3 部分组 成。第 1 项形式上虽然和 LLE 相同，但其中的重 构权矩阵包含了样本点的半监督信息，能够确保 提取出的特征既保持数据的局部线性结构不变， 又能在局部上使类内 (同类) 数据更紧密，并对类 间 (异类) 数据进行分离的效果。第 2 项和第 3 项 分别是全局同类样本偏差和全局异类样本偏差， 目的是确保同类样本偏差最小，同时确保全局异 类样本偏差最大，参数 是 2 个偏差项的 平衡系数，权衡同类样本项和异类样本项对目标 函数的影响。β 也是一个平衡参数，用于调节局 部线性重构对于目标函数的影响。 式 (5) 的约束条件与 LLE 相同，确保提取出 第 16 卷 智 能 系 统 学 报 ·100·

·101· 邓廷权，等：半监督类保持局部线性嵌入方法 第1期 的特征在低维空间中旋转平移伸缩都具有平移和 的第i行向量即为高维数据：的低维特征。 缩放不变性，其中I为d阶单位矩阵。 简记式（⑤）的目标函数为 3实验及结果分析 (Y)=Bo(Y)+aJML-(1-a)JcL (6) 为了证明本文提出的SSCLLE的性能，在加 这样，式(6)的第1部分形式上与LLE相同， 州大学欧文分校(university of california irvine,. 仍可表示为 UCI)数据集、实物数据集coil20和手写数字 -2 t(YMY) MNIST数据集上进行实验。实验结果分别与经 典的无监督流形学习方法LLE、半监督SSLLE 式中的M由式(2)、(4)确定。 方法，半监督拉普拉斯特征映射(semi-supervised 为了简化第2部分和第3部分，给定矩阵 laplacian eigenmap,SSLE)I和分类约束降维方法 Y=yy…y]T∈Rm,Z=[zz对…z]T∈Rd,则 (classification constrained dimensionality reduction. 对任意y:∈R4和zeR4,均有： CCDR)2o进行实验对比。从聚类精度和数据可 -y4-0=2-ya-2=r4z 视化角度对它们进行实验比较和分析。 在这里简单介绍3种半监督方法。基于LLE 其中A=(A)网)为n×n矩阵，则 提出的SSLLE,它的思想是结合数据拥有的部分 1, p=i,q=i 标记信息调整近邻样本点之间的距离，再利用调 1, p=j.q=j 整后的距离来重构权值矩阵。虽然SSLLE可以 (Ap -1,p=i,q=j -1,p=j.q=i 利用部分标签信息使得近邻中同类数据点距离更 0. 其他 近，异类数据点更远从而实现更好的分类以及聚 令 类效果。但由于SSLLE方法仅对近邻点之间的 (x,x)∈M 距离做调整，缺乏对全局同类异类点的考虑。当 其他 标记点较少时近邻中可能出现没有同类或异类的 (x,x)∈CL 点的情况，这时SSLLE将失去作用。而且由于它 其他 只考虑近邻的调整，当标记信息很多时它们整体 则有： 的区分度也不大。 2F》 SSLE和CCDR都是在拉普拉斯特征映射 (laplacian eigenmap,LE)的基a础上提出的半监督 会m4m-r24 方法。在这里SSLE也是一种利用信息在局部做 调凋整的方法，缺点和SSLLE类似。而CCDR是 r(YVMLY) 一种全局的调整，相较于SSLE有较好的提取 和 效果。 本文S$CLLE方法在保持局部线性结构的同 = 时，不仅利用标记信息对局部做调整，同时利用 ∑u(AY)=rYr2哈Ay (7 全局项对全局做调整。使类内数据更紧密，而对 类间数据进行分离。从而达到更好的特征提取效 tr(YVeLY) 果，以下是相关的实验验证。 因此，优化问题（⑤）的矩阵表示形式为 统一对各方法设定参数，进行特征提取。这 minp(Y)=tr(YHY) 里用聚类精度作为评判方法有效性的指标之一， s.t.Yy=I,ITY=0 利用模糊C均值(fuzzy c-means,FCM)聚类方法 式中：H=BM+aVm-(1-a)Vc;1=(1,1,…,1)T是 进行聚类分析。关于样本标签个数做以下设置： 一个n×1的全1矩阵。采用拉格朗日乘子法求 从数据集的每类样本中随机抽取S(S=5%, 解，优化问题(7)的解转化为求解HY=λY的特征 10%,…,50%)比例的数据作为已知标签样本。取 值问题。 20次实验的平均值作为最终的聚类精度。参数 计算矩阵H的前d个最小非零特征值(0≠ 表示：近邻个数为k,低维特征维度为d,SSLLE ≤2≤…≤)所对应的特征向量（列向量）P,p= 方法调节参数用r表示，SSLE方法中的参数用 1,2,…,d,将其构成矩阵Y=[12…vl,则矩阵Y v表示，CCDR方法中的参数用u表示，本文

的特征在低维空间中旋转平移伸缩都具有平移和 缩放不变性，其中 I 为 d 阶单位矩阵。 简记式 (5) 的目标函数为 ρ(Y) = βσ(Y)+αJML −(1−α)JCL (6) 这样，式 (6) 的第 1 部分形式上与 LLE 相同， 仍可表示为 σ(Y) = ∑n i=1 yi − ∑n j=1 Wi jyj 2 = tr(Y TMY) 式中的 M 由式 (2)、(4) 确定。 Y = [y T 1 y T 2 ··· y T n ] T ∈ R n×d Z = [z T 1 z T 2 ··· z T n ] T ∈ R n×d yi ∈ R d和zj ∈ R d 为了简化第 2 部分和第 3 部分，给定矩阵[10] , ， 则 对任意 ，均有： (yi − yj) T (zi − zj) = ∑d l=1 (yil −yjl)(zil −zjl) = tr(Y TA i jZ) A i j = ((A i j 其中 )pq) 为 n×n 矩阵，则 (A i j)pq =    1, p = i,q = i 1, p = j,q = j −1, p = i,q = j −1, p = j,q = i 0, 其他 令 w ML i j = { 1, (xi , xj) ∈ ML 0, 其他 w CL i j = { 1, (xi , xj) ∈ CL 0, 其他 则有： JML = ∑ (xi,xj)∈ML d 2 (yi , yj) = ∑n i, j=1 w ML i j d 2 (yi , yj) = ∑n i, j=1 w ML i j tr(Y TA i jY) = tr   Y T ( ∑n i, j=1 w ML i j A i j)Y   = tr(Y TVMLY) 和 JCL = ∑ (xi,xj)∈CL d 2 (yi , yj) = ∑n i, j=1 w CL i j d 2 (yi , yj) = ∑n i, j=1 w CL i j tr(Y TA i jY) = tr   Y T ( ∑n i, j=1 w CL i j A i j)Y   = tr(Y TVCLY) (7) 因此，优化问题 (5) 的矩阵表示形式为 minρ(Y) = tr(Y THY) s.t. Y TY = I, 1 TY = 0 H = βM +αVML −(1−α)VCL 1 = (1,1,··· ,1)T n×1 HY = λY 式中： ； 是 一个 的全 1 矩阵。采用拉格朗日乘子法求 解，优化问题 (7) 的解转化为求解 的特征 值问题。 0 , λ1 ⩽ λ2 ⩽ ··· ⩽ λd vp, p = 1,2,··· ,d Y = [v1 v2 ··· vp] Y 计算矩阵 H 的前 d 个最小非零特征值 ( ) 所对应的特征向量 (列向量) ，将其构成矩阵 ，则矩阵 的第 i 行向量即为高维数据 xi 的低维特征 yi。 3 实验及结果分析 为了证明本文提出的 SSCLLE 的性能，在加 州大学欧文分校 (university of california irvine, UCI) 数据集、实物数据集 coil_20 和手写数字 MNIST 数据集上进行实验。实验结果分别与经 典的无监督流形学习方法 LLE、半监督 SSLLE[18] 方法，半监督拉普拉斯特征映射 (semi-supervised laplacian eigenmap, SSLE)[19] 和分类约束降维方法 (classification constrained dimensionality reduction, CCDR)[20] 进行实验对比。从聚类精度和数据可 视化角度对它们进行实验比较和分析。 在这里简单介绍 3 种半监督方法。基于 LLE 提出的 SSLLE，它的思想是结合数据拥有的部分 标记信息调整近邻样本点之间的距离，再利用调 整后的距离来重构权值矩阵。虽然 SSLLE 可以 利用部分标签信息使得近邻中同类数据点距离更 近，异类数据点更远从而实现更好的分类以及聚 类效果。但由于 SSLLE 方法仅对近邻点之间的 距离做调整，缺乏对全局同类异类点的考虑。当 标记点较少时近邻中可能出现没有同类或异类的 点的情况，这时 SSLLE 将失去作用。而且由于它 只考虑近邻的调整，当标记信息很多时它们整体 的区分度也不大。 SSLE 和 CCDR 都是在拉普拉斯特征映射 （laplacian eigenmap，LE）的基础上提出的半监督 方法。在这里 SSLE 也是一种利用信息在局部做 调整的方法，缺点和 SSLLE 类似。而 CCDR 是 一种全局的调整，相较于 SSLE 有较好的提取 效果。 本文 SSCLLE 方法在保持局部线性结构的同 时，不仅利用标记信息对局部做调整，同时利用 全局项对全局做调整。使类内数据更紧密，而对 类间数据进行分离。从而达到更好的特征提取效 果，以下是相关的实验验证。 S (S = 5%, 10%,··· ,50%) 统一对各方法设定参数，进行特征提取。这 里用聚类精度作为评判方法有效性的指标之一， 利用模糊 C 均值（fuzzy c-means，FCM）聚类方法 进行聚类分析。关于样本标签个数做以下设置： 从数据集的每类样本中随机抽取 比例的数据作为已知标签样本。取 20 次实验的平均值作为最终的聚类精度。参数 表示：近邻个数为 k，低维特征维度为 d，SSLLE 方法调节参数用 r 表示，SSLE方法中的参数用 v 表示， CCDR 方法中的参数 用 u 表示，本 文 ·101· 邓廷权，等：半监督类保持局部线性嵌入方法 第 1 期

第16卷 智能系统学报 ·102· SSCLLE方法中a和B分别用a和b表示，r与 之间聚类精度各有高低。而当d为2时，虽然 SSLLE中设置相同。 SSCLLE方法在Seeds数据集的实验中的聚类精 3.1UCI中几个数据集 度并不是全部保持最高，当标记比例为5%时 实验中从UCI数据库里选3个数据集，分别 S$LLE方法仅仅略高于本文方法，在标记比例为 为Wine数据集、Seeds数据集和WDBC(wisconsin 15%以及另外2个数据集时SSCLLE的聚类精度 diagnostic breast cancer) 最高。总体实验分析可知，本文提出的半监督流 然后，分别用5种方法进行实验比较和分 形学习方法SSCLLE相比无监督方法LLE与其 析。根据特征提取的维数d做3组实验，分别设 他3种半监督方法聚类精度最高，体现出本文方 置d的值为2、3和4。每类数据随机标记5%，每 法的优势。 组实验进行20次，求聚类精度的平均值来评判 表4d=4时5种方法的平均聚类精度 5种方法的特征提取效果。表1~3分别是d值为 Table 4 Average clustering accuracy of the five 2、3和4时，各方法对3个数据集进行特征提取 methods when d=4 % 后得到的平均聚类精度。实验中，将参数设置 数据集 Wine Seeds WDBC 为：k=6,r=0.8,v=0.5,u=1,a=0.9,b=10。 比例% 5 15 5 15 5 15 LLE 92.1392.1372.4872.4884.3684.36 表1数据集信息 93.3894.2783.3183.52 Table 1 Data set information SSLLE 86.8986.87 SSLE 87.6487.7580.5780.48 79.3778.87 数据集 数据个数 属性个数 类别 CCDR 88.290.1180.4382.3875.4876.94 Wine 178 3 SSCLLE 94.1894.2783.8183.7686.9687.99 Seeds 210 7 3 对于半监督方法来说标记信息的多少会影响 WDBC 569 30 聚类的结果。这里把3组UCI数据中的每一个类 标记信息比例设置为5%、20%和40%，提取特征 表2d=2时5种方法的平均聚类精度 维数=2。图2为3个数据集在4种半监督方法 Table 2 Average clustering accuracy of the five methods when d=2 % 下的实验结果。 由图2的实验结果可以看出：3个数据集的 数据集 Wine Seeds WDBC 柱状分析图，随着数据的标记比例的增加，各个 比例% 15 15 15 半监督方法的聚类精度也在增加，符合半监督方 LLE 93.4493.44 76.23 76.23 84.7184.71 法利用越多标记信息就会提高聚类精度的设想。 SSLLE 95.1796.63 91.19191.22 89.0989.96 但明显可以看出2种基于局部标记信息进行调整 的方法SSLLE和SSLE,随着标记信息的增加聚 SSLE 95.7397.19 87.70387.91 89.75 90.9 类精度提升，相对考虑全局信息的SSCLLE与CCDR CCDR 95.6296.97 88.17190.01 85.2 90.11 不明显。而SSCLLE方法的聚类精度已经达到了 SSCLLE 96.2997.53 91.10592.19 91.5392.09 一个很高的值，明显高于CCDR,所以相对没有 CCDR提升比率那么高。总体实验分析中可以看 表3d=3时5种方法的平均聚类精度 到，在每组实验里SSCLLE方法的聚类精度基本 Table 3 Average clustering accuracy of the five methods when d=3 % 都能保持最高，证明了本方法在UCI数据上的 优势。 数据集 Wine Seeds WDBC 100 ■5%☐20%☐40% 比例/% 15 15 5 15 90 LLE 94.9493.9464.7664.7676.7776.77 80 SSLLE 94.3894.49.89.0589.1 78.0382.39 70 SSLE 93.2693.2383.8184.19 63.5175.04 50 CCDR92.9293.8186.1489.0563.6979.3 SSCLLE95.0695.3889.0590.178.2286.53 30 由表2~4数据可知：当特征空间的维数d为 3和4时，在3个数据集上SSCLLE方法的聚类精 SSLLE SSLE CCDR SSCLLE 度都比其他4种方法高，其他方法在不同数据集 (a)Wine数据集

SSCLLE 方法中 α 和 β 分别用 a 和 b 表示，r 与 SSLLE 中设置相同。 3.1 UCI 中几个数据集 实验中从 UCI 数据库里选 3 个数据集，分别 为 Wine 数据集、Seeds 数据集和 WDBC(wisconsin diagnostic breast cancer)。 k = 6,r = 0.8, v = 0.5,u = 1,a = 0.9,b = 10 然后，分别用 5 种方法进行实验比较和分 析。根据特征提取的维数 d 做 3 组实验，分别设 置 d 的值为 2、3 和 4。每类数据随机标记 5%，每 组实验进行 20 次，求聚类精度的平均值来评判 5 种方法的特征提取效果。表 1~3 分别是 d 值为 2、3 和 4 时，各方法对 3 个数据集进行特征提取 后得到的平均聚类精度。实验中，将参数设置 为： 。 表 1 数据集信息 Table 1 Data set information 数据集 数据个数 属性个数 类别 Wine 178 13 3 Seeds 210 7 3 WDBC 569 30 2 表 2 d = 2 时 5 种方法的平均聚类精度 Table 2 Average clustering accuracy of the five methods when d=2 % 数据集 Wine Seeds WDBC 比例/% 5 15 5 15 5 15 LLE 93.44 93.44 76.23 76.23 84.71 84.71 SSLLE 95.17 96.63 91.191 91.22 89.09 89.96 SSLE 95.73 97.19 87.703 87.91 89.75 90.9 CCDR 95.62 96.97 88.171 90.01 85.2 90.11 SSCLLE 96.29 97.53 91.105 92.19 91.53 92.09 表 3 d = 3 时 5 种方法的平均聚类精度 Table 3 Average clustering accuracy of the five methods when d =3 % 数据集 Wine Seeds WDBC 比例/% 5 15 5 15 5 15 LLE 94.94 93.94 64.76 64.76 76.77 76.77 SSLLE 94.38 94.49 89.05 89.1 78.03 82.39 SSLE 93.26 93.23 83.81 84.19 63.51 75.04 CCDR 92.92 93.81 86.14 89.05 63.69 79.3 SSCLLE 95.06 95.38 89.05 90.1 78.22 86.53 由表 2~4 数据可知：当特征空间的维数 d 为 3 和 4 时，在 3 个数据集上 SSCLLE 方法的聚类精 度都比其他 4 种方法高，其他方法在不同数据集 之间聚类精度各有高低。而当 d 为 2 时，虽然 SSCLLE 方法在 Seeds 数据集的实验中的聚类精 度并不是全部保持最高，当标记比例为 5% 时 SSLLE 方法仅仅略高于本文方法，在标记比例为 15% 以及另外 2 个数据集时 SSCLLE 的聚类精度 最高。总体实验分析可知，本文提出的半监督流 形学习方法 SSCLLE 相比无监督方法 LLE 与其 他 3 种半监督方法聚类精度最高，体现出本文方 法的优势。 表 4 d = 4 时 5 种方法的平均聚类精度 Table 4 Average clustering accuracy of the five methods when d=4 % 数据集 Wine Seeds WDBC 比例/% 5 15 5 15 5 15 LLE 92.13 92.13 72.48 72.48 84.36 84.36 SSLLE 93.38 94.27 83.31 83.52 86.89 86.87 SSLE 87.64 87.75 80.57 80.48 79.37 78.87 CCDR 88.2 90.11 80.43 82.38 75.48 76.94 SSCLLE 94.18 94.27 83.81 83.76 86.96 87.99 对于半监督方法来说标记信息的多少会影响 聚类的结果。这里把 3 组 UCI 数据中的每一个类 标记信息比例设置为 5%、20% 和 40%，提取特征 维数 d=2。图 2 为 3 个数据集在 4 种半监督方法 下的实验结果。 由图 2 的实验结果可以看出：3 个数据集的 柱状分析图，随着数据的标记比例的增加，各个 半监督方法的聚类精度也在增加，符合半监督方 法利用越多标记信息就会提高聚类精度的设想。 但明显可以看出 2 种基于局部标记信息进行调整 的方法 SSLLE 和 SSLE，随着标记信息的增加聚 类精度提升，相对考虑全局信息的 SSCLLE 与 CCDR 不明显。而 SSCLLE 方法的聚类精度已经达到了 一个很高的值，明显高于 CCDR，所以相对没有 CCDR 提升比率那么高。总体实验分析中可以看 到，在每组实验里 SSCLLE 方法的聚类精度基本 都能保持最高，证明了本方法在 UCI 数据上的 优势。 SSLLE SSLE CCDR SSCLLE 0 10 20 30 40 50 60 70 80 90 100 5% 20% 40% 聚类精度/% (a) Wine 数据集 第 16 卷 智 能 系 统 学 报 ·102·